The van der Corput difference theorem (or trick) was develop (unsurprisingly) by van der Corput, and deals with uniform distribution of sequences in the torus.

Theorem 1 (van der Corput trick)Let be a sequence in a torus . If for every the sequence is uniformly distributed on , then so is .

In 1987, Bergelson observed that a similar trick works in Hilbert spaces and it is this version which turned out to be amazingly useful in ergodic theory (unfortunately for Bergelson, following his own example, everyone keeps calling it the *van der Corput trick*). Here is a consequence of the “Hilbertian” van der Corput trick of Bergelson:

Theorem 2Let be a measure preserving system, let and let . Ifholds with for every , then (1) holds with .

Then in 1996, Bergelson and Leibman adapted the same ideology to topological dynamics. Unfortunately, they didn’t explicitly state an analogue of the difference theorem in topological dynamics (such an explicit statement is Lemma 8.5 in this paper). While it is quite a stretch to call such an analogue as a van der Corput trick (so far from uniform distribution it is) it still expresses the same idea of exploiting the “derivatives” in order to obtain a result about the “original function”.

Here I take this analogy one step further, and using the connection between topological dynamics and arithmetic Ramsey theory powered by piecewise syndetic sets, I will present an arithmetic analogue of the van der Corput trick in . First it will be convenient to have the following definition:

Definition 3Let and . We say that the family is afamily of multiple recurrenceif for any finite coloring (i.e. partition) of the natural numbers there exists such that the setis monochromatic.

Theorem 4 (Arithmetic van der Corput trick)Let and be such that . Assume that for any finite set the familyis a family of multiple recurrence. Then the family is a family of multiple recurrence as well.

In this post I will give a proof of Theorem 4 and then I will illustrate its power by deriving from it a short proof of the polynomial van der Waerden theorem of Bergelson and Leibman.

** — 1. Piecewise syndetic sets and multiple recurrence — **

In my previous post I presented some properties of piecewise syndetic sets. In particular Theorem 10 hints that piecewise syndetic sets can be used as a bridge between topological dynamics and arithmetic Ramsey theory. The following observation refines that theorem.

Proposition 5Let . The following are equivalent:

- For any finite coloring of there are two numbers of the same color such that .
- For any piecewise syndetic set there are such that .
- For any piecewise syndetic set there exists such that the set
is piecewise syndetic.

- For any finite coloring of there exists such that the set
is piecewise syndetic.

We will now extend the scope of Proposition 5 to multiple recurrence. Start by recalling the statement of the celebrated van der Waerden’s theorem on arithmetic progressions (I have mentioned this theorem a few times before in this blog and in particular presented three different proofs):

Theorem 6 (van der Warden’s theorem)For any finite coloring of the natural numbers and any there exist such that the setis monochromatic (i.e. all its elements are colored with the same color).

Sets of the form are called *arithmetic progressions* and thus van der Waerden’s theorem can be formulated in a compact form as “any finite coloring of yields arbitrarily long monochromatic arithmetic progressions”. In the spirit of Proposition 5, there are three other equivalent formulations of the van der Waerden theorem using the notion of piecewise syndetic sets:

Proposition 7The following statements are equivalent:

- Theorem 6
- Any piecewise syndetic set contains arbitrarily long arithmetic progressions.
- For any piecewise syndetic set there exists such that the set
is piecewise syndetic.

- For any finite coloring of there exists such that the set
is piecewise syndetic.

While the original proof of van der Waerden’s theorem was combinatorial in nature, Furstenberg and Weiss obtained a different proof using topological dynamics. This dynamical proof was the starting point for an amazing extension of van der Waerden’s theorem, obtained by Bergelson and Leibman, allowing the common difference to be taken from the image of any polynomial (with constant term). In fact their result is even more general:

Theorem 8 (Polynomial van der Waerden theorem)Let be such that for each . For any finite coloring of there exist such that the setis monochromatic.

One can extend Theorem 8 in the spirit of Propositions 5 and 7. Instead, we will develop a more general framework: we will call a *pattern on * a collection of finite subsets of . Elements of a pattern may be called *configurations*. The pattern is *shift invariant* if for every and also . We say that the pattern is *monochromatic* if for every finite coloring of there exists which is monochromatic.

Theorem 9Let be a shift invariant pattern. Then the following are equivalent:

- is monochromatic.
- For every there exists such that for any coloring of the interval with colors there exists contained in which is monochromatic.
- For every piecewise syndetic set there exists such that .
- For every piecewise syndetic set there exists such that the set
is piecewise syndetic.

*Proof:* Clearly (4)(3)(1). We will prove (1)(2)(4) and this will finish the proof.

Assume satisfies (1) and let . Suppose, for the sake of a contradiction, that for every there exists a coloring without a monochromatic configuration in . Extend all the to colorings of the whole by assigning for all . Then take a convergent subsequence of in the compact metric space and call the limit . It should be clear that (i.e. it does not color any natural number with the “color” ). Using (1) we can now find some configuration which is monochromatic with respect to . Let be such that and agree on the set . We conclude that is monochromatic for the coloring which is a contradiction, and hence (2) holds.

Next we prove the implication (2)(4). Assume that (2) holds and let be an arbitrary piecewise syndetic set. Let and be a syndetic and a thick set, respectively, such that . Let be such that and let be a coloring such that for every . Let be provided by (2) and let and observe that is a thick set, and hence a piecewise syndetic set. Let be the coloring defined by . In view of Corollary 4 from the previous post there exists a piecewise syndetic set such that is constant.

Now, let be the coloring defined by for some (hence all) . From the construction of (i.e. using (2)) we conclude that there exists some configuration such that is constant. Let be the value of . It follows that and hence . On the other hand, , and , so . We conclude that finishing the proof.

In particular we obtain the following equivalent characterization of families of multiple recurrence, defined in Definition 3.

Corollary 10Let and . The family is a family of multiple recurrence if and only if for every piecewise syndetic set there exists such that the setis piecewise syndetic.

** — 2. Proof of the combinatorial van der Corput trick — **

*Proof of Theorem 4:* Let be a finite coloring of . We need to show that there exists and such that

Find such that is piecewise syndetic. We proceed inductively, finding sequences

- of colors in
- in
- and of piecewise syndetic sets

where (and we set ). Assume we have already constructed , , and . Using the hypothesis with (and Theorem 9) one can find and a piecewise syndetic set such that

Then invoking Corollary 4 from the previous post one can find a color such that is piecewise syndetic. This finishes the construction of the four sequences; we now show that (3) holds.

Let be arbitrary and let be arbitrary. Since , in view of (4) we have that . Adding the same number on both sides we can rewrite this as

Iterating this equation for we conclude that

Since and for every we conclude that (3) holds as desired.

Now take any for which (such pair must exist since takes only finitely many values), take arbitrary and let and . It follows that . Since , also , establishing (2) and hence finishing the proof.

We kept things in for simplicity, but the proof above extends effortlessly to any commutative semigroup (and even to non-commutative situations as well, but we will not pursue this possibility here).

Definition 11Let and be commutative semigroups and let and . We say that is afamily of multiple recurrenceif for any finite coloring of there exists and such that the set is monochromatic.

Theorem 12 (Generalized arithmetic van der Corput trick)Let and be commutative semigroups, let and let be such that . Assume that for any finite set the familyis a family of multiple recurrence. Then the family is a family of multiple recurrence as well.

** — 3. Polynomial van der Waerden — **

In this section we prove Theorem 8, using the arithmetic van der Corput trick. We will invoke the PET induction scheme (Polynomial Exhaustion Technique, sometimes it also means Polynomial Ergodic Theorem), which shows that by performing the operation from Theorem 4 one can reduce any polynomial family to the singleton which is trivially a family of multiple recurrence. The PET induction was first developed by Bergelson (in the same paper where the Bergelson-van der Corput trick first came to life). It was then used (in an extended form) to prove the polynomial van der Waerden theorem and is now a standard technique.

Definition 13 (PET induction)Two polynomials areequivalentif they have the same degree and leading coefficient, in other words, if has degree strictly smaller than . Given a finite family of polynomials, let be the maximal degree of the and, for each let be the number of equivalence classes in of polynomials of degree . The vector is called thecharacteristic vectorof . We order the characteristic vectors by letting if and only if either or both and the maximum for which satisfies .

Observe that since , the characteristic vector is unique.

Example 1

- The family has characteristic vector , the family has characteristic vector .
- According to the ordering of the characteristic vectors we have and .

The proof of Theorem 8 now proceeds by induction on the characteristic vector of ; all we need to show is that the family

has a strictly smaller characteristic vector when has the smallest degree.

Indeed, we denote by the degree of (so that and for each ) and let be the equivalence class of . Notice that, for every and every , the polynomial is equivalent to and both have the same degree as . Next, observe that whenever , the polynomial is equivalent to if and only if is equivalent to . Finally note that if , then the degree of and is strictly smaller than . It follows from the observations above that the characteristic vector of satisfies for any and . Therefore the characteristic vector of is strictly smaller than that of and this finishes the proof.