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:
— 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’.
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:
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.
where 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 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
— 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 8 Let be abelian groups. A map is a polynomial map of degree if it is constant. For each , the map is a polynomial map of degree if 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 10 Let 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.
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.
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 13 Let 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 1 For 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 2 For 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 15 Let denote the collection of all triples as in Definition 12 where commutes with every map and, for each , the set consists of homomorphisms.
Theorem 16 For 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 17 Let be an abelian group. Call a subset polynomially rich if 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 .