## New polynomial and multidimensional extensions of classical partition results

Vitaly Bergelson, John Johnson and I recently uploaded to the arXiv a paper entitled “New polynomial and multidimensional extensions of classical partition results“. In this post I will give some motivating examples for the results in the paper.

To keep things as concrete as possible, I will establish parallels to our results in the paper using known generalizations of the classical van der Waerden’s theorem on arithmetic progressions:

Theorem 1 (van der Waerden) For any finite partition of the natural numbers ${{\mathbb N}=C_1\cup\cdots\cup C_r}$, there exists some ${i\in[r]=\{1,\dots,r\}}$ for which ${C_i}$ contains arbitrarily long arithmetic progressions, i.e., for every ${k\in{\mathbb N}}$, there are ${a,b\in{\mathbb N}}$ such that

$\displaystyle ja+b\in C_i\qquad\forall j\in[k]\ \ \ \ \ (1)$

— 1. Extensions to commutative semigroups —

Van der Waerden’s theorem has been extended to higher dimensions (i.e., to ${{\mathbb N}^d}$) by Galai/Grünwald (The proof was first obtained by T. Grünwald who never published it. He later changed his name to Galai, to whom the result is attributed in this book. To further add to the confusion, Rado mistakenly attributes the theorem to G. Grünwald, who was an analyst and died during the WWII). The analogue of an arithmetic progression on ${{\mathbb N}^d}$ is a square grid’.

Theorem 2 (Grünwald) For any ${d\in{\mathbb N}}$ and any finite partition ${{\mathbb N}^d=C_1\cup\cdots\cup C_r}$, there exists some ${i\in[r]}$ for which ${C_i}$ contains arbitrarily long square grids, i.e., for every ${k\in{\mathbb N}}$, there are ${a\in{\mathbb N},{\bf b}\in{\mathbb N}^d}$ such that

$\displaystyle {\bf j}a+{\bf b}\in C_i\qquad\forall {\bf j}\in[k]^d$

Here and in this post (and in the paper) we use bold font for elements of the cartesian product ${X^d}$ of a set ${X}$ with itself ${d}$ times (for ${d>1}$).

On a different direction, van der Waerden’s theorem was extended by Brauer, who guarantees that not only an arithmetic progression but also its common difference, all belong to the same cell of the partition:

Theorem 3 (Brauer) For any finite partition of the natural numbers ${{\mathbb N}=C_1\cup\cdots\cup C_r}$ and any ${k\in{\mathbb N}}$, there exists some ${i\in[r]}$ and ${a,b\in{\mathbb N}}$ such that

$\displaystyle \begin{array}{lrr}a&\in C_i\\ja+b&\in C_i&\forall j\in[k]\end{array}$

A recurring theme in Ramsey theory is that of completing the square’, where one takes two extensions of a theorem in different directions and finds a common extension of both. In the situation at hands, it is not quite clear how to even formulate a theorem which implies both Theorems 2 and 3. One of the motivations for our paper was precisely to find (and prove) such a result.

Theorem 4 For any ${d,k\in{\mathbb N}}$, any ${{\bf c}\in{\mathbb N}^d}$ and any finite partition ${{\mathbb N}^d=C_1\cup\cdots\cup C_r}$, there exists some ${i\in[r]}$ and ${{\bf a},{\bf b}\in{\mathbb N}^d}$ such that

$\displaystyle \begin{array}{lrr}{\bf a}&\in C_i\\{\bf j}\langle{\bf c},{\bf a}\rangle+{\bf b}&\in C_i&\forall{\bf j}\in[k]^d\end{array}$

where ${\langle\cdot,\cdot\rangle}$ denotes the usual inner product.

A way to better appreciate Theorem 4 is to see it within a suitable abstract version. The idea is to realize that all semigroups homomorphisms from ${{\mathbb N}}$ to itself are given by multiplication with a fixed integer. Therefore, one can replace multiplications with arbitrary homomorphisms and obtain a generalization of van der Waerden’s theorem for arbitrary commutative semigroups:

Theorem 5 (van der Waerden for commutative semigroups) Let ${G,H}$ be commutative semigroups. For any finite partition ${G=C_1\cup\cdots\cup C_r}$ and for every finite set ${F}$ of semigroup homomorphisms from ${H}$ to ${G}$, there exists ${i\in[r]}$ and ${a\in H,b\in G}$ such that

$\displaystyle f(a)+b\in C_i\qquad\forall f\in F$

When ${G=H={\mathbb N}}$, this reduces to Theorem 1. When ${G={\mathbb N}^d}$ and ${H={\mathbb N}}$, we recover Theorem 2.

Theorem 5 can be derived from Hales-Jewett’s theorem (I presented the proof of a somewhat stronger version in a previous post). Now it is easy to formulate an extension of Brauer’s theorem along the same lines:

Theorem 6 (Brauer’s theorem for commutative semigroups) Let ${G}$ be a commutative semigroup. For any finite partition ${G=C_1\cup\cdots\cup C_r}$ and for every finite set ${F}$ of semigroup homomorphisms from ${G}$ to itself, there exists ${i\in[r]}$ and ${a,b\in G}$ such that

$\displaystyle \begin{array}{lrr}a&\in C_i\\f(a)+b&\in C_i&\forall f\in F\end{array}$

Setting ${G={\mathbb N}}$ we recover Theorem 3; and setting ${G={\mathbb N}^d}$ one obtains Theorem 4.

— 2. Extensions to polynomial configurations —

Another important extension of van der Waerden’s theorem is the polynomial van der Waerden’s theorem of Bergelson and Leibman. In fact their theorem is multidimensional (so also extenting Galai’s theorem).

Theorem 7 (Bergelson-Leibman) For any ${d\in{\mathbb N}}$ and any finite partition ${{\mathbb Z}^d=C_1\cup\cdots\cup C_r}$, there exists some ${i\in[r]}$ for which ${C_i}$ contains arbitrarily long polynomial progressions, i.e., for every ${k\in{\mathbb N}}$ and polynomials ${f_1,\dots,f_k:{\mathbb Z}^d\rightarrow{\mathbb Z}^d}$ with ${f({\bf0})={\bf0}}$, there are ${{\bf a},{\bf b}\in({\mathbb Z}\setminus\{0\})^d}$ such that

$\displaystyle f_j({\bf a})+{\bf b}\in C_i\qquad\forall j\in[k]$

It is not difficult to find a common extension of Theorems 3 and 7 for ${d=1}$ (a simpler version of this common extension, when also ${k=1}$ is this theorem from a previous post in this blog; the same proof presented there works for the case with general ${k}$). In the paper we also establish an extension for higher dimension ${d}$. In order to formulate such a common extension we will first state a version of the polynomial van der Waerden theorem for abelian groups:

Definition 8 Let ${G,H}$ be abelian groups. A map ${f:H\rightarrow G}$ is a polynomial map of degree ${0}$ if it is constant. For each ${d\in{\mathbb N}}$, the map ${f}$ is a polynomial map of degree ${d}$ if it is not a polynomial map of lower degree and, for each ${h\in H}$, the derivative ${f_h:x\mapsto f(x+h)-f(x)}$ is a polynomial map of degree at most ${d-1}$. We denote by ${\mathbb{P}(H,G)}$ the set of all polynomial maps ${f:H\rightarrow G}$ such that ${f(0)=0}$.

In the same way that Theorem 5 can be deduced from Hales-Jewett’s theorem, the following theorem can be derived from the polynomial Hales-Jewett’s theorem:

Theorem 9 (Polynomial van der Waerden for abelian groups) Let ${G,H}$ be abelian groups. For any finite partition ${G=C_1\cup\cdots\cup C_r}$ and for every finite set ${F\subset\mathbb{P}(H,G)}$, there exists ${i\in[r]}$ and ${a\in H\setminus\{0\},b\in G}$ such that

$\displaystyle f(a)+b\in C_i\qquad\forall f\in F$

Theorem 7 follows from Theorem 9 by letting ${G=H={\mathbb Z}^d}$. The common extension of Theorems 3 and 9 is:

Theorem 10 Let ${G}$ be an abelian groups. For any finite partition ${G=C_1\cup\cdots\cup C_r}$ and for every finite set ${F\subset\mathbb{P}(G,G)}$, there exists ${i\in[r]}$ and ${a,b\in G\setminus\{0\}}$ such that

$\displaystyle \begin{array}{lrr}a&\in C_i\\f(a)+b&\in C_i&\forall f\in F\end{array}$

— 3. ${(m,p,c)}$-sets —

A far reaching extension of Brauer’s theorem is Rado’s theorem, classifying all homogeneous systems of linear equations which are partition regular over ${{\mathbb N}}$. Rado’s theorem has an equivalent form, that of Deuber’s theorem, which expresses solutions of linear systems as linear configurations, the so-called ${(m,p,c)}$-sets.

Theorem 11 (Deuber) For any finite partition of the natural numbers ${{\mathbb N}=C_1\cup\cdots\cup C_r}$ and any ${m,p,c\in{\mathbb N}}$, there exists some ${i\in[r]=\{1,\dots,r\}}$ and ${{\bf s}=(s_0,\dots,s_m)\in{\mathbb N}^{m+1}}$ such that

$\displaystyle \begin{array}{lcr}cs_0&\in C_i\\js_0+cs_1&\in C_i&\forall j\in[p]\\j_0s_0+j_1s_1+cs_2&\in C_i&\forall j_0,j_1\in[p]\\\qquad \vdots\qquad\qquad\qquad\ddots&\vdots&\vdots\qquad\\ j_0s_0+\cdots+j_{m-1}s_{m-1}+cs_m&\in C_i&\forall j_0,\dots,j_{m-1}\in[p]\end{array}$

Observe that Brauer’s theorem can be recovered from Deuber’s theorem by setting ${m=c=1}$. In order to obtain a common extension of Theorems 2 and 11, and indeed of Theorems 7 and 11, it is convenient to interpret Deubers configurations in a different light.

Definition 12 Let ${G}$ be a commutative semigroup, let ${m\in{\mathbb N}}$ and let ${c:G\rightarrow G}$ be a homomorphism. For each ${j=1,\dots,m}$, let ${F_j}$ be a finite set of maps from ${G^j}$ to ${G}$. Finally, let ${\vec F=(F_1,\dots,F_m)}$. For ${{\bf s}=(s_1,\dots,s_m)\in G^{m+1}}$, the ${(m,\vec F,c)}$-set generated by ${{\bf s}}$ is the set

$\displaystyle D(m,\vec F,c;{\bf s})=\left\{\begin{array}{lr}c(s_0)\\f(s_0)+c(s_1)&:f\in F_1\\ f(s_0,s_1)+c(s_2)&:f\in F_2\\ \qquad\vdots\qquad\qquad\ddots&\vdots\quad\\f(s_0,\dots,s_{m-1})+c(s_m)&\qquad:f\in F_m \end{array}\right\}$

Our main theorems in the paper give sufficient conditions on a triple ${(m,\vec F,c)}$ over a commutative semigroup ${G}$ so that for every finite partition of ${G}$, one of the cells contains an ${(m,\vec F,c)}$-set. Since the precise sufficient conditions are rather technical, I will now state two corollaries of our main results:

Theorem 13 Let ${G}$ be a countable commutative semigroup and let ${(m,\vec F,c)}$ be as in Definition 12. Assume that at least one of the following holds:

• The map ${c}$ is the identity map and, for each ${j=1,\dots,m}$, the set ${F_j}$ consists of homomorphisms.
• ${G}$ is a group, the image of ${c}$ has finite index in ${G}$ and, for each ${j=1,\dots, m}$, ${F_j\subset\mathbb{P}(G^j,G)}$.

Then ${(m,\vec F,c)}$-sets are partition regular, i.e., for any finite partition ${G=C_1\cup\cdots\cup C_r}$ there exists ${i\in[r]}$ and ${{\bf s}\in G^{m+1}}$ such that ${D(m,\vec F,c;{\bf s})\subset C_i}$.

To get a flavor of the power of Theorem 13, consider the following example, which is not too hard to derive from the IP polynomial Szemerédi theorem of Bergelson and McCutcheon (with the help of the coloring trick of Bergelson.)

Example 1 For any finite partition of the natural numbers ${{\mathbb N}=C_1\cup\cdots\cup C_r}$, there exist ${i,j\in[r]}$ such that

• ${\{x,y,y+x,y+x^2\}\subset C_i}$ for some ${x,y\in{\mathbb N}}$,
• ${\{z,z+x^2,z+y^2,z+x+y,z+xy\}\subset C_j}$ for some ${x,y,z\in{\mathbb N}}$.

We now give a (previously unknown) corollary of Theorem 13, to be compared with the previous example:

Example 2 For any finite partition of the natural numbers ${{\mathbb N}=C_1\cup\cdots\cup C_r}$, there exists some ${i\in[r]}$ for which ${C_i}$ contains a configuration of the form

$\displaystyle \{x,y,y+x,y+x^2,\quad z,z+x^2,z+y^2,z+x+y,z+xy\}$

— 4. Inner partition regularity and open questions —

The main breakthrough of Deuber’s proof of Rado’s theorem (introducing and using ${(m,p,c)}$-sets) was the inner partition regularity of ${(m,p,c)}$-rich sets:

Theorem 14 (Deuber) Let ${A\subset{\mathbb N}}$ and assume that, for every triple ${(m,p,c)\in{\mathbb N}^3}$, there exists an ${(m,p,c)}$-set inside ${A}$. Then, for any finite partition ${A=C_1\cup\cdots\cup C_r}$ there exists ${i\in[r]}$ such that for every ${(m,p,c)\in{\mathbb N}^3}$, the set ${C_i}$ contains an ${(m,p,c)}$-set.

Deuber obtained inner partition regularity as a corollary of a finitistic version of partition regularity. In the case of ${(m,p,c)}$-sets, the finitistic version is this theorem whose proof I presented in my previous post on this subject.

We obtained in the paper an analogue result for certain triples ${(m,\vec F,c)}$:

Definition 15 Let ${\Lambda}$ denote the collection of all triples ${(m,\vec F,c)}$ as in Definition 12 where ${c}$ commutes with every map ${\tilde c:G\rightarrow G}$ and, for each ${j=1,\dots,m}$, the set ${F_j}$ consists of homomorphisms.

Theorem 16 For every ${(m,\vec F,c)\in\Lambda}$ and ${r\in{\mathbb N}}$ there exists ${(M,\vec H,C)\in\Lambda}$ such that for any partition of a ${(M,\vec H,C)}$-set into ${r}$ cells, one of the cells contains an ${(m,\vec F,c)}$-set.

We were unable to establish a corresponding result when the ${F_j}$‘s are allowed to contain polynomial maps. In particular, the following conjecture remains open:

Conjecture 17 Let ${G}$ be an abelian group. Call a subset ${A\subset G}$ polynomially rich if it contains an ${(m,\vec F,c)}$-set for every triple ${(m,\vec F,c)}$ where ${m\in{\mathbb N}}$, ${c:G\rightarrow G}$ is the identity map and ${F_i\subset\mathbb{P}(G^j,G)}$.

Then, for every finite partition of a polynomially rich set, one of the cells is still polynomially rich.

While the main feature of Rado’s theorem is arguably to establish many partition regular configurations, it is particularly nice for being an `if and only if’ result. One could hope to get necessary and sufficient conditions for ${(m,\vec F,c)}$-sets to be partition regular as well. Unfortunately, it seems quite hard to do so in this generality. Even in the simplest unknown situation we have no answer to the following problem: Find necessary and sufficient condition on a homomorphism ${\Phi:({\mathbb Z}^2)^d\rightarrow({\mathbb Z}^2)^k}$ so that for any finite partition ${{\mathbb Z}^2=C_1\cup\cdots\cup C_r}$ there exists ${i\in[r]}$ and ${x_1,\dots,x_d\in C_i}$ so that ${\Phi(x_1,\dots,x_d)={\bf0}\in({\mathbb Z}^2)^k}$.