Tag Archive

[This is the second part of Bill Gasarch's guest post on "polynomial" versions of van der Waerden's theorem. -- Luca]

This is a the second of two Guest Postings on the Polynomial VDW Theorem. This one is on the Multi-dimensional Poly VDW Theorem.

Our starting point is VDW’s theorem, which is the same starting point Luca had in his postings on Szemeredi’s theorem (here, here, here, here, and here) and I had in my first posting.

VDW:
For all $c,k\in N$, for any $c$-coloring $COL:Z \rightarrow [c]$ there exists $a,d\in Z$, $d\ne 0$, such that

$COL(a) = COL(a+d) = COL(a+2d) = \cdots = COL(a+(k-1)d).$

What would a multidimensional version of VDW look like? What would a multidimensional version of Poly VDW look like? Before stating that, we give corollaries to both to provide the flavor.

Corollary of Two-dimensional VDW:
For all $c$, for any $c$-coloring $COL: Z\times Z\rightarrow [c]$, there exists a square with all corners the same color. (Formally there exists $a,b,d$,$d\ne 0$, such that

$COL(a,b)=COL(a+d,b)=COL(a,b+d)=COL(a+d,b+d).$

Think of this as

$COL((a,b)+d(0,0))=COL((a,b)+d(1,0))=$
$COL((a,b)+d(0,1))=COL((a,b)+d(1,1)).$)

Corollary of Two-dimensional Poly VDW:
For all $c$, for any $c$-coloring $COL: Z\times Z\rightarrow [c]$, there exists a rectangle with all corners the same color where the side is the square of its length. (Formally there exists $a,b,d$, $d\ne 0$, such that
$COL(a,b)=COL(a+d,b)=COL(a,b+d^2)=COL(a+d,b+d^2).$
Think of this as
$COL((a,b)+(0,0))=COL((a,b)+d(1,0))=$
$COL((a,b)+d^2(0,1))=COL((a,b)+d(1,0)+d^2(0,1)).$)

In the full Multidimensional theorems the set $\{ (0,0), (0,1), (1,0), (1,1) \}$ will be replaced by an arbitrary finite set.

Multidimensional VDW:
Let $e\in N$. Let $F=\{\overline f_1, \overline f_2, \ldots, \overline f_k\}$ be a finite set of points in $Z^e$ (e.g., $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ for the square case in the corollary to Multidim VDW). For all $c$, for any $c$-coloring $COL: Z^e\rightarrow [c]$, there exists $\overline a\in Z^e$, $d\in N$, $d\ne0$, such that
$COL(\overline a + d\overline f_1)= COL(\overline a + d\overline f_2) = \cdots =COL(\overline a + d\overline f_k).$

This was proven by Furstenberg and Weiss (Topological dynamics and combinatorial number theory, Journal d’Analyse Mathematique, Vol. 34, 61–85, 1978); however, it was later observed that it follows from the (ordinary) Hales-Jewitt Theorem.

Furstenberg and Katznelson also proved a density version of the Multidimensional VDW Theorem (An ergodic Szemeredi’s theorem for commuting transformations, Journal d’Analyse Mathematique, Vol. 34, 275–291, 1978). Roughly speaking, if $A\subseteq Z^d$ is dense enough then there exists $\overline a\in Z^e$, $d\in N$, $d\ne 0$ such that $\{ \overline a+d\overline f \mid f\in F \}\subseteq A$.

Consider the functions

$\overline a + d\overline f_1, \overline a + d\overline f_2, \cdots, \overline a + d\overline f_k.$

One may consider replacing these functions with a more complicated function of $d$ and $\overline f_1, \ldots, \overline f_k$. This leads to the following theorem.

Multidimensional Poly VDW:
Let $e,r\in n$. Let $p: Z^r \rightarrow Z^e$. Let $F=\{\overline f_1, \overline f_2, \ldots, \overline f_s\}$ be a finite set of points in $Z^r$. Let $f_i = (f_{i1},\ldots,f_{ir}).$ For all $c$, for any $c$-coloring $COL: Z^e\rightarrow [c]$, there exists $\overline a\in Z^e$, $d\in Z^r$, $d=(d_1,\ldots,d_r)$, $d\ne \overline 0$, such that

$COL(\overline a + P(d_1f_{11},d_2f_{12},\ldots,d_rf_{1r}))= COL(\overline a + P(d_1f_{21},d_2f_{22},\ldots,d_rf_{2r}))$
$=COL(\overline a + P(d_1f_{31},d_2f_{r2},\ldots,d_rf_{3r}))$
$\vdots$
$COL(\overline a + P(d_1f_{s1},d_2f_{r2},\ldots,d_rf_{sr}))$

This was first proven by Bergelson and Leibman (Polynomial extensions of van der Waerden’s and Szemeredi’s theorems, Journal of the American Math Society 1996, Vol. 9, 725–753.

They actually proved a density version.

There is an alternative proof by Bergelson and Liebman (Set-polynomials and Polynomial extension of the Hales-Jewett Theorem, Annals of Math, Vol. 150, 1999, 33-75.}

The proof is in two steps

• Prove the Poly Hales-Jewett Theorem (henceforth Poly HJ). (This proof is not elementary.)
• Prove Multi-dimensional Poly VDW Theorem from Poly HJ. (This part was elementary.)

There is a purely combinatorial proof of the Multi-dimensional Poly VDW Theorem, though it is not stated in the literature:

• Walters has a combinatorial proof of Poly HJ in the paper of his mentioned in my last post.
• As noted above, Bergelson and Leibman showed how to get from the Poly HJ theorem to the Multi-dimensional Poly VDW theorem.

Putting all this together there is an elementary proof of the Multi-dimensional Poly VDW theorem. There is a general version as well, similar to the Gen Poly VDW from
my last post, but I won’t state it here.

These types of theorems have been generalized in Polynomial Szemeredi theorems for countable modules over integral domains and finite fields by Bergelson, Leibman, and McCutcheon, Journal d’Analyse Mathematique, Vol 95, 243–296, 2005.

There has also been some work on restricting what $d$ or $\overline d$ could be in the above theorems. We state the easiest of such theorems. It is derivable from the (ordinary) Hales-Jewitt theorem.

VDW’s with $d$ restricted:
Let $C\subseteq N$. Let $D$ be the set of all sums of distinct elements of $C$. For all $c,k\in N$, for any $c$-coloring $COL:Z \rightarrow [c]$ there exists $a\in Z$, $d\in D$, $d\ne 0$, such that

$COL(a) = COL(a+d) = COL(a+2d) = \cdots = COL(a+(k-1)d).$

More complicated versions of this for multidimensional polynomials were proven by Bergelson and McCutcheon (An Ergodic IP Polynomial Szemeredi Theorem by Bergelson and McCutcheon. Memoirs of the American Math Society, Vol 46, 2000.

Open Problems:

1. Consider the one-dimensional VDW theorem over the reals. Is there an easy analytic proof of this, or of some subcases of it?
2. If we allow polynomials with constant term what happens. More concretely: For all finite sets $F\subseteq Z[x]$, determine $c$ such that:
   • For any $c$-coloring $COL:Z\rightarrow [c]$ there exists $a,d\in Z$, $d\ne 0$, such that $\{ a+p(d) \mid p\in F\}$ is monochromatic.
   • There exists a $c+1$-coloring $COL:Z\rightarrow [c]$ such that for all $a,d\in Z$, $d\ne 0$, $\{ a+p(d) \mid p\in F\}$ is not monochromatic.

3. Everything I’ve mentioned above except the Poly HJ theorem has a density analoge that is difficult to proof. Find easier proofs. This is not well defined since it depends on how you define `easier’. Combinatorial may be one definition, but those can be rough too.

I would like to thank Alexander Leibman for his help in preparing this post.

[Bill Gasarch, known online for his frequent contributions to the Complexity Blog and for his liberal USE of capital LETTERS, has been reading about the "polynomial" and "multi-dimensional" versions of van der Waerden's theorem (the original theorem being "linear" and "one-dimensional") and he is going to tell us about it. Enjoy. -- Luca]

Guest Posting by William Gasarch (gasarch@cs.umd.edu)

This is a one of two Guest Posting on the Polynomial van der Waerden Theorem (henceforth Poly VDW). This posting is on the one-dimensional Poly VDW; however,my next posting will be on the Multidimensional Poly VDW. Throughout this posting `Poly VDW’ means `One Dimensional Poly VDW’

Our starting point is VDW’s theorem, which is the same starting point Luca had in his postings on Szemeredi’s theorem. (here, here, here, here, and here.) But I go in a different direction.

VDW’s:
For all $c,k\in N$, for any $c$-coloring $COL:Z \rightarrow [c]$, there exists $a,d\in Z$, $d\ne 0$, such that

$COL(a) = COL(a+d) = COL(a+2d) = \cdots = COL(a+(k-1)d).$

The original proof ofVDW’s Theorem was an induction on the following ordering $\omega^2$ on $(k,c)$

$(1,1)<(1,2)<\cdots<(2,1)<(2,2)<\cdots<(3,1)<(3,2)<\cdots.$

For example the proof of $(4,2)$ depends on the theorem being true for $(3,L)$ where $L$ is very large. Shelah (Primitive recursive bounds for van der Waerden numbers, Journal of the American Math Society, Vol 1, 1-15, 198 has a proof that avoids this type of induction and hence yields a much slower growth rate for the VDW numbers (which we are not discussing here).

Consider the functions

$a, a+d, a+2d, \ldots, a+(k-1)d.$

One may consider replacing $d, 2d, 3d, \ldots, (k-1)d$ with polynomials in $d$. This leads to the following theorem.

Poly VDW:
For all $c\in N$, for all $p_1,\ldots,p_k \in Z[x]$ such that $(\forall i)[p_i(0)=0]$, for any $c$-coloring $COL:Z\rightarrow [c]$ there exists $a,d\in Z$, $d\ne 0$, such that

$COL(a) = COL(a+p_1(d)) = COL(a+p_2(d)) = \cdots = COL(a+p_k(d)).$

The condition $(\forall i)[p_i(0)=0]$ is needed since if the $p_i$’s were constants the theorem would be false. It is an open problem to look at particular sets of polys with constant term.

This was first proven by Bergelson and Leibman (Polynomial extensions of van der Waerden’s and Szemeredi’s theorems, Journal of the American Math Society, Vol. 9, 1996, 725–753.)

The proof uses ergodic (non-elementary) techniques. They actually proved a density version.

Density Poly VDW:
For all $p_1,\ldots,p_k \in Z[x]$ such that $(\forall i)[p_i(0)=0]$, for all sets $A\subseteq Z$ of positive density, there exists $a,d\in Z$, $d\ne 0$, such that

$a, a+p_1(d), a+p_2(d),\ldots, a+p_k(d)\in A. $

Walters has a purely combinatorial proof of the Poly VDW Theorem (Combinatorial Proofs of the Polynomial van der Waerden Theorem and the Polynomial Hales-Jewitt Theorem Journal of the London Math Society, Vol 61, 2000, 1-12.)

The proof used an $\omega^\omega$ ordering as follows.

For every finite set $F\subseteq Z[x]$ such that $(\forall p\in F)[p(0)=0]$ we associate a tuple $(n_e,\ldots,n_1)$ where the largest degree polynomial in $F$ is degree $e$, and, for all $i$, $1\le i\le e$, $n_i$ is the number of different coefficients of $x^i$ that occur in polynomials of degree $i$ in $F$.

Let $PVDW(n_e,\ldots,n_1)$ mean that Poly VDW holds for all sets of polys $F$ of type $(n_e,\ldots,n_1)$. The ordinary VDW theorem can be viewed as $\bigwedge_{i=1}^\infty PDVW(i)$.

The Poly VDW is proven by induction on the following $\omega^\omega$-ordering. Let $\sigma, \tau \in N^*$.

1. If $|\sigma| < |\tau|$ then $\sigma \preceq \tau$.
2. If $|\sigma|=|\tau|$ then order lexicographically. (e.g., $(2,3,4,999,10^{100}) < (2,3,5,1,0,0)$)

Having stated the Poly VDW one can now state a version of VDW over any infinite Commutative Ring $R$ (think Reals).

Gen Poly VDW:
Let $R$ any infinite commutative ring. For all $c\in N$, for all $p_1,\ldots,p_k \in R[x]$ such that $(\forall i)[p_i(0)=0]$, for any $c$-coloring $COL: R\rightarrow [c]$ there exists $a,d\in R$, $d\ne 0$, such that

$COL(a) = COL(a+p_1(d)) = COL(a+p_2(d)) = \cdots = COL(a+p_k(d)).$

This was proven by by Bergelson and Liebman (Set-polynomials and Polynomial extension of the Hales-Jewett Theorem, Annals of Math, Vol. 150, 1999, 33-75.}

The proof is in two steps

• Prove the Poly Hales-Jewett Theorem (henceforth Poly HJ). (This proof is not elementary.)
• Prove Gen Poly VDW from Poly HJ.
  (This part was elementary.)

There is a purely combinatorial proof of the Gen Poly VDW theorem, though it is not stated in the literature:

• Walters has a combinatorial proof of the Poly Hales Jewitt Theorem in the paper of his mentioned above.

• As noted above, Bergelson and Leibman showed how to get from the Poly HJ Theorem to the Gen Poly VDW Theorem.

Coda 1:
Green and Tao proved that the set of primes has arbitrarily long arithmetic progressions.

More recently, Tao and Ziegler: have shown the following:

For any $p_1,\ldots, p_k \in Z[x]$ such that $(\forall i)[p_i(0)=0]$, there exists $a,d\in Z$, $d\ne 0$, such that

$a, a+p_1(d), a+p_2(d), \cdots a+p_k(d)$ are all prime

Coda 2:
The Maryland Math Olympiad is in two parts. Part I is 25 multiple choice questions (but some are quite hard). If you do well on part I then you can take part II which is 5 problems that need proof. We try to number the problems in order of difficulty. I placed the following problem on the 2006 High School Maryland Math Olympiad, as problem 5:

Let $COL$ be a 3-coloring of $\{1,\ldots,2006\}$. Show that there exists $x,y$ such that $COL(x)=COL(y)$ and $|x-y|$ is a square.

Of the 240 students who took the exam around 180 tried this one. Of those 5 got it right and 10 got partial credit. The proof I had in mind (which is the one the students used who got it right) is not a scaled down version of the proof of the poly VDW. I leave it to the reader to see if they can prove this.