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 , there exists some for which contains arbitrarily long arithmetic progressions, i.e., for every , there are such that

** — 1. Extensions to commutative semigroups — **

Van der Waerden’s theorem has been extended to higher dimensions (i.e., to ) 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 is a square `grid’.

Theorem 2 (Grünwald)For any and any finite partition , there exists some for which contains arbitrarily long square grids, i.e., for every , there are such that

Here and in this post (and in the paper) we use **bold font** for elements of the cartesian product of a set with itself times (for ).

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 and any , there exists some and such that

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 4For any , any and any finite partition , there exists some and such thatwhere 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 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 be commutative semigroups. For any finite partition and for every finite set of semigroup homomorphisms from to , there exists and such that

When , this reduces to Theorem 1. When and , 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 be a commutative semigroup. For any finite partition and for every finite set of semigroup homomorphisms from to itself, there exists and such that

Setting we recover Theorem 3; and setting 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 and any finite partition , there exists some for which contains arbitrarily long polynomial progressions, i.e., for every and polynomials with , there are such that

It is not difficult to find a common extension of Theorems 3 and 7 for (a simpler version of this common extension, when also is this theorem from a previous post in this blog; the same proof presented there works for the case with general ). In the paper we also establish an extension for higher dimension . 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 8Let be abelian groups. A map is apolynomial mapof degree if it is constant. For each , the map is apolynomial map of degreeif it is not a polynomial map of lower degree and, for each , the derivative is a polynomial map of degree at most . We denote by the set of all polynomial maps such that .

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 be abelian groups. For any finite partition and for every finite set , there exists and such that

Theorem 7 follows from Theorem 9 by letting . The common extension of Theorems 3 and 9 is:

Theorem 10Let be an abelian groups. For any finite partition and for every finite set , there exists and such that

** — 3. -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 . Rado’s theorem has an equivalent form, that of Deuber’s theorem, which expresses solutions of linear systems as linear configurations, the so-called -sets.

Theorem 11 (Deuber)For any finite partition of the natural numbers and any , there exists some and such that

Observe that Brauer’s theorem can be recovered from Deuber’s theorem by setting . 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 12Let be a commutative semigroup, let and let be a homomorphism. For each , let be a finite set of maps from to . Finally, let . For , the-set generated byis the set

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

Theorem 13Let be a countable commutative semigroup and let be as in Definition 12. Assume that at least one of the following holds:

- The map is the identity map and, for each , the set consists of homomorphisms.
- is a group, the image of has finite index in and, for each , .
Then -sets are partition regular, i.e., for any finite partition there exists and such that .

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 1For any finite partition of the natural numbers , there exist such that

- for some ,
- for some .

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

Example 2For any finite partition of the natural numbers , there exists some for which contains a configuration of the form

** — 4. Inner partition regularity and open questions — **

The main breakthrough of Deuber’s proof of Rado’s theorem (introducing and using -sets) was the inner partition regularity of -rich sets:

Theorem 14 (Deuber)Let and assume that, for every triple , there exists an -set inside . Then, for any finite partition there exists such that for every , the set contains an -set.

Deuber obtained inner partition regularity as a corollary of a finitistic version of partition regularity. In the case of -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 :

Definition 15Let denote the collection of all triples as in Definition 12 where commutes with every map and, for each , the set consists of homomorphisms.

Theorem 16For every and there exists such that for any partition of a -set into cells, one of the cells contains an -set.

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

Conjecture 17Let be an abelian group. Call a subsetpolynomially richif it contains an -set for every triple where , is the identity map and .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 -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 so that for any finite partition there exists and so that .

Pingback: Measure preserving actions of affine semigroups and {x+y,xy} patterns | I Can't Believe It's Not Random!