The Polynomial van der Waerden Theorem
[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, 1988) 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^*$.
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
There is a purely combinatorial proof of the Gen Poly VDW theorem, though it is not stated in the literature:
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.
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, 1988) 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^*$.
- If $|\sigma| < |\tau|$ then $\sigma \preceq \tau$.
- 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.
posted by Luca at 1:40 PM
5 comments
