The Multi-dimensional Polynomial van der Waerden Theorem
[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
There is a purely combinatorial proof of the Multi-dimensional Poly VDW Theorem, though it is not stated in the literature:
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:
I would like to thank Alexander Leibman for his help in preparing this post.
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:
- Consider the one-dimensional VDW theorem over the reals. Is there an easy analytic proof of this, or of some subcases of it?
- 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.
- 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.
- 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.
posted by Luca at 8:48 PM
3 comments
