An arithmetic van der Corput trick and the polynomial van der Waerden theorem

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 {(x_n)_{n\in{\mathbb N}}} be a sequence in a torus {{\mathbb T}^d:={\mathbb R}^d/{\mathbb Z}^d}. If for every {h\in{\mathbb N}} the sequence {(x_{n+h}-x_n)_{n\in{\mathbb N}}} is uniformly distributed on {{\mathbb T}^d}, then so is {(x_n)_{n\in{\mathbb N}}}.

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 2 Let {(X,mu,T)} be a measure preserving system, let {k\in{\mathbb N}} and let {p_1,\dots,p_k:{\mathbb N}\rightarrow{\mathbb Z}}. If

\displaystyle  \lim_{N\rightarrow\infty}\frac1N\sum_{n=1}^N\int_Xf_0\cdot\prod_{p\in{\mathcal P}}T^{p(n)}f_pd\mu=0\qquad \text{ for any }f_p\in L^\infty(X) \ \ \ \ \ (1)

holds with {{\mathcal P}=\Big\{p_\ell(n+h)-p_1(n):\ell\in[k]\Big\}\cup\Big\{p_\ell(n)-p_1(n):\ell\in[k]\Big\}} for every {h\in{\mathbb N}}, then (1) holds with {{\mathcal P}=\{p_1,\dots,p_k\}}.

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 {{\mathbb N}}. First it will be convenient to have the following definition:

Definition 3 Let {k\in{\mathbb N}} and {p_1,\dots,p_k:{\mathbb N}\rightarrow{\mathbb Z}}. We say that the family {\{p_1,\dots,p_k\}} is a family of multiple recurrence if for any finite coloring (i.e. partition) of the natural numbers there exists {a,n\in{\mathbb N}} such that the set

\displaystyle \big\{a,a+p_1(n),\dots,a+p_k(n)\big\}

is monochromatic.

Theorem 4 (Arithmetic van der Corput trick) Let {k\in{\mathbb N}} and {p_1,\dots,p_k:{\mathbb N}\rightarrow{\mathbb Z}} be such that {p_i(0)=0}. Assume that for any finite set {F\subset{\mathbb N}\cup\{0\}} the family

\displaystyle \Big\{x\mapsto p_i(x+h)-p_1(x)-p_i(h)\mid h\in F,i\in\{1,\dots k\}\Big\}

is a family of multiple recurrence. Then the family {\{p_1,\dots,p_k\}} 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 5 Let {R\subset{\mathbb N}}. The following are equivalent:

  • For any finite coloring of {{\mathbb N}} there are two numbers {x,y} of the same color such that {x-y\in R}.
  • For any piecewise syndetic set {A\subset{\mathbb N}} there are {x,y\in A} such that {x-y\in R}.
  • For any piecewise syndetic set {A\subset{\mathbb N}} there exists {r\in R} such that the set

    \displaystyle \big\{y\in A:\text{exists }x\in A\text{ such that }x-y=r\big\}

    is piecewise syndetic.

  • For any finite coloring of {{\mathbb N}} there exists {r\in R} such that the set

    \displaystyle \big\{y\in{\mathbb N}:\text{exists }x\text{ of the same color as }y\text{ such that }x-y=r\big\}

    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 {k\in{\mathbb N}} there exist {a,d\in{\mathbb N}} such that the set

\displaystyle \{a,a+d,a+2d,\dots,a+kd\}

is monochromatic (i.e. all its elements are colored with the same color).

Sets of the form {\{a,a+d,a+2d,\dots,a+kd\}} are called arithmetic progressions and thus van der Waerden’s theorem can be formulated in a compact form as “any finite coloring of {{\mathbb N}} 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 7 The following statements are equivalent:

  • Theorem 6
  • Any piecewise syndetic set contains arbitrarily long arithmetic progressions.
  • For any piecewise syndetic set {A} there exists {d\in{\mathbb N}} such that the set

    \displaystyle \big\{a\in{\mathbb N}:\{a,a+d,a+2d,\dots,a+kd\}\subset A\big\}

    is piecewise syndetic.

  • For any finite coloring of {{\mathbb N}} {A} there exists {d\in{\mathbb N}} such that the set

    \displaystyle \big\{a\in{\mathbb N}:\{a,a+d,a+2d,\dots,a+kd\}\text{ is monochromatic}\big\}

    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 {0} constant term). In fact their result is even more general:

Theorem 8 (Polynomial van der Waerden theorem) Let {p_1,\dots,p_k\in{\mathbb Z}[x]} be such that {p_i(0)=0} for each {i=1,\dots,k}. For any finite coloring of {{\mathbb N}} there exist {a,d\in{\mathbb N}} such that the set

\displaystyle \big\{a,a+p_1(d),a+p_2(d),\dots,a+p_k(d)\big\}

is 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 {{\mathbb N}} a collection {{\mathcal C}} of finite subsets of {{\mathbb N}}. Elements of a pattern {{\mathcal C}} may be called configurations. The pattern is shift invariant if for every {P\in{\mathcal C}} and {n\in{\mathbb N}} also {P+n\in{\mathcal C}}. We say that the pattern {{\mathcal C}} is monochromatic if for every finite coloring of {{\mathbb N}} there exists {P\in{\mathcal C}} which is monochromatic.

Theorem 9 Let {{\mathcal C}} be a shift invariant pattern. Then the following are equivalent:

  1. {{\mathcal C}} is monochromatic.
  2. For every {r\in{\mathbb N}} there exists {N\in{\mathbb N}} such that for any coloring of the interval {[1,N]} with {r} colors there exists {P\in{\mathcal C}} contained in {[1,N]} which is monochromatic.
  3. For every piecewise syndetic set {A\subset{\mathbb N}} there exists {P\in{\mathcal C}} such that {P\subset A}.
  4. For every piecewise syndetic set {A\subset{\mathbb N}} there exists {P\in{\mathcal C}} such that the set

    \displaystyle \big\{n\in{\mathbb N}:P+n\subset A\big\}

    is piecewise syndetic.

Proof: Clearly (4){\Rightarrow}(3){\Rightarrow}(1). We will prove (1){\Rightarrow}(2){\Rightarrow}(4) and this will finish the proof.

Assume {{\mathcal C}} satisfies (1) and let {r\in{\mathbb N}}. Suppose, for the sake of a contradiction, that for every {N\in{\mathbb N}} there exists a coloring {\chi_N:[1,N]\rightarrow[r]} without a monochromatic configuration in {{\mathcal C}}. Extend all the {\chi_N} to colorings of the whole {{\mathbb N}} by assigning {\chi_N(x)=0} for all {a>N}. Then take a convergent subsequence of {(\chi_N)_{N\in{\mathbb N}}} in the compact metric space {\{0,1,\dots,r\}^{\mathbb N}} and call the limit {\chi}. It should be clear that {\chi:{\mathbb N}\rightarrow[r]} (i.e. it does not color any natural number with the “color” {0}). Using (1) we can now find some configuration {P\in{\mathcal C}} which is monochromatic with respect to {\chi}. Let {N\in{\mathbb N}} be such that {\chi_N} and {\chi} agree on the set {P}. We conclude that {P} is monochromatic for the coloring {\chi_N} which is a contradiction, and hence (2) holds.

Next we prove the implication (2){\Rightarrow}(4). Assume that (2) holds and let {A} be an arbitrary piecewise syndetic set. Let {S} and {T} be a syndetic and a thick set, respectively, such that {A=S\cap T}. Let {r} be such that {S-[r]={\mathbb N}} and let {\chi:{\mathbb N}\rightarrow[r]} be a coloring such that {x+\chi(x)\in S} for every {x\in{\mathbb N}}. Let {N} be provided by (2) and let {\tilde T:=\{x\in{\mathbb N}:[x+1,x+N+r]\subset T\}} and observe that {\tilde T} is a thick set, and hence a piecewise syndetic set. Let {\tilde\chi:{\mathbb N}\rightarrow[r]^N} be the coloring defined by {\tilde\chi(x)=\big(\chi(x+1),\dots,\chi(x+N)\big)}. In view of Corollary 4 from the previous post there exists a piecewise syndetic set {B\subset\tilde T} such that {\tilde\chi|_B} is constant.

Now, let {\chi':[1,N]\rightarrow[r]} be the coloring defined by {\chi'(x)=\chi(b+x)} for some (hence all) {b\in B}. From the construction of {N} (i.e. using (2)) we conclude that there exists some configuration {P\in{\mathcal C}} such that {\chi'|_P} is constant. Let {i\in[r]} be the value of {\chi'(P)}. It follows that {\chi(B+P)=i} and hence {B+P+i\subset S}. On the other hand, {B\subset\tilde T}, {P\subset[N]} and {i\leq r}, so {B+P+i\subset T}. We conclude that {(B+i)+P=B+P+i\subset A} finishing the proof. \Box

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

Corollary 10 Let {k\in{\mathbb N}} and {p_1,\dots,p_k:{\mathbb N}\rightarrow{\mathbb Z}}. The family {\{p_1,\dots,p_k\}} is a family of multiple recurrence if and only if for every piecewise syndetic set {A\subset{\mathbb N}} there exists {n\in{\mathbb N}} such that the set

\displaystyle \Big\{a\in{\mathbb N}:\{a,a+p_1(n),\dots,a+p_k(n)\}\subset A\Big\}

is piecewise syndetic.

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

Proof of Theorem 4: Let {{\mathbb N}=C_1\cup\cdots\cup C_r} be a finite coloring of {{\mathbb N}}. We need to show that there exists {t\in[r]} and {a,n\in{\mathbb N}} such that

\displaystyle  \big\{a,a+p_1(n),\dots,a+p_k(n)\big\}\subset C_t \ \ \ \ \ (2)

Find {t_0\in[r]} such that {A_0:=C_{t_0}} is piecewise syndetic. We proceed inductively, finding sequences

  • {(t_i)_{i\geq0}} of colors in {[r]}
  • {(n_i)_{i\geq1}} in {{\mathbb N}}
  • {(A_i)_{i\geq0}} and {(B_i)_{i\geq1}} of piecewise syndetic sets

such that {A_i\subset C_{t_i}} and for any {i>j} we have

\displaystyle \bigcup_{\ell=1}^k\Big(A_i+p_\ell\big(n(j,i)\big)\Big)\subset A_j\ \ \ \ \ (3)

where {n(j,i)=n_{j+1}+\cdots+n_i} (and we set {n(i,i)=0}). Assume we have already constructed {(t_i)_{i=0}^{m-1}}, {(n_i)_{i=1}^{m-1}}, {(A_i)_{i=0}^{m-1}} and {(B_i)_{i=1}^{m-1}}. Using the hypothesis with {F=\big\{n(j,m-1):j\in\{0,\dots,m-1\}\big\}} (and Theorem 9) one can find {n_m\in{\mathbb N}} and a piecewise syndetic set {B_m\subset{\mathbb N}} such that

\displaystyle  \bigcup_{j=0}^{m-1}\bigcup_{\ell=1}^k\Big(B_m+p_\ell\big(n(j,m)\big)-p_1(n_m)-p_\ell\big(n(j,m-1)\big)\Big)\subset A_{m-1} \ \ \ \ \ (4)

Then invoking Corollary 4 from the previous post one can find a color {t_m\in[r]} such that {A_m:=\big(B_m-p_1(n_m)\big)\cap C_{t_m}} is piecewise syndetic. This finishes the construction of the four sequences; we now show that (3) holds.

Let {i>j} be arbitrary and let {\ell\in\{1,\dots,k\}} be arbitrary. Since {A_i\subset B_i-p_1(n_i)}, in view of (4) we have that {A_i+p_\ell\big(n(j,i)\big)-p_\ell\big(n(j,i-1)\big)\subset A_{i-1}}. Adding the same number on both sides we can rewrite this as

\displaystyle A_i+p_\ell\big(n(j,i)\big)\subset A_{i-1}+p_\ell\big(n(j,i-1)\big)

Iterating this equation for {i-1,i-2,\dots,j} we conclude that

\displaystyle  \begin{array}{rcl}  A_i+p_\ell\big(n(j,i)\big)&\subset& A_{i-1}+p_\ell\big(n(j,i-1)\big)\\&\subset& A_{i-2}+p_\ell\big(n(j,i-2)\big)\\&\vdots&\vdots\\&\subset&A_j+p_\ell\big(n(j,j)\big) \end{array}

Since {n(j,j)=0} and {p_\ell(0)=0} for every {\ell} we conclude that (3) holds as desired.

Now take any {i>j} for which {t_i=t_j} (such pair must exist since {t} takes only finitely many values), take {a\in A_i} arbitrary and let {n=n(j,i)} and {t=t_i=t_j}. It follows that {\{a+p_1(n),\dots,a+p_k(n)\}\subset A_j\subset C_t}. Since {A_i\subset C_t}, also {a\in C_t}, establishing (2) and hence finishing the proof. \Box

We kept things in {{\mathbb N}} 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 11 Let {(S,+)} and {(G,+)} be commutative semigroups and let {k\in{\mathbb N}} and {p_1,\dots,p_k:S\rightarrow G}. We say that {\{p_1,\dots,p_k\}} is a family of multiple recurrence if for any finite coloring of {G} there exists {a\in G} and {d\in S} such that the set {\{a,a+p_1(d),\dots,a+p_k(d)\}} is monochromatic.

Theorem 12 (Generalized arithmetic van der Corput trick) Let {(S,+)} and {(G,+)} be commutative semigroups, let {k\in{\mathbb N}} and let {p_1,\dots,p_k: S\rightarrow G} be such that {p_i(0)=0}. Assume that for any finite set {F\subset S\cup\{0\}} the family

\displaystyle \Big\{x\mapsto p_i(x+h)-p_1(x)-p_i(h)\mid h\in F,i\in\{1,\dots k\}\Big\}

is a family of multiple recurrence. Then the family {\{p_1,\dots,p_k\}} 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 {\{x\mapsto0\}} 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 {p_1,p_2\in{\mathbb Z}[x]} are equivalent if they have the same degree and leading coefficient, in other words, if {p_2-p_1} has degree strictly smaller than {p_2}. Given a finite family {P=\{p_1,\dots,p_k\}} of polynomials, let {d} be the maximal degree of the {p_i} and, for each {j=1,\dots,d} let {s_j} be the number of equivalence classes in {P} of polynomials of degree {j}. The vector {(s_1,\dots,s_d)} is called the characteristic vector of {P}. We order the characteristic vectors by letting {(s_1,\dots,s_d)<(\tilde s_1,\dots,\tilde s_{\tilde d})} if and only if either {d<\tilde d} or both {d=\tilde d} and the maximum {j} for which {s_j\neq\tilde s_j} satisfies {s_j<\tilde s_j}.

Observe that since {s_d>0}, the characteristic vector is unique.

Example 1

  • The family {\{x,2x-1,3x,x^3+2x^2,x^3+1\}} has characteristic vector {(3,0,1)}, the family {\{x,x+2,x+7,3x,x^2\}} has characteristic vector {(2,1)}.
  • According to the ordering of the characteristic vectors we have {(1,2,3)<(0,0,0,1)} and {(9,3,5,2,4)<(1,7,6,2,4)}.

The proof of Theorem 8 now proceeds by induction on the characteristic vector of {P=\{p_1,\dots,p_k\}}; all we need to show is that the family

\displaystyle \Delta_F P:=\Big\{x\mapsto p_i(x+h)-p_1(x)-p_i(h)\mid h\in F,i\in\{1,\dots k\}\Big\}

has a strictly smaller characteristic vector when {p_1\in P} has the smallest degree.

Indeed, we denote by {e} the degree of {p_1} (so that {s_e\geq1} and {s_j=0} for each {j<e}) and let {Q\subset P} be the equivalence class of {p_1}. Notice that, for every {p\in P\setminus Q} and every {h\in{\mathbb N}}, the polynomial {n\mapsto p(n)-p_1(n)} is equivalent to {n\mapsto p(n+h)-p_1(n)-p(h)} and both have the same degree as {p}. Next, observe that whenever {p,p'\in P\setminus Q}, the polynomial {n\mapsto p(n)-p_1(n)} is equivalent to {n\mapsto p'(n)-p_1(n)} if and only if {p} is equivalent to {p'}. Finally note that if {p\in Q}, then the degree of {p(n)-p_1(n)} and {p(n+h)-p_1(n)-p(h)} is strictly smaller than {e}. It follows from the observations above that the characteristic vector {(\tilde s_1,\dots,\tilde s_d)} of {\Delta_F P} satisfies {\tilde s_j=s_j} for any {j>e} and {\tilde s_e=s_e-1}. Therefore the characteristic vector of {\Delta_F P} is strictly smaller than that of {P} and this finishes the proof.

Advertisements

About Joel Moreira

PhD Student at OSU in Mathematics. I'm portuguese.
This entry was posted in Combinatorics, Ramsey Theory, Tool and tagged , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s