The Hales-Jewett theorem is one of the most fundamental results in Ramsey theory, implying the celebrated van der Waerden theorem on arithmetic progressions, as well an its multidimensional and IP versions. One interesting property of the Hales-Jewett’s theorem is that it is a set theoretical statement, having no structure, and hence making it versatile for applications. Recently I realized that there exists an equivalent formulation of this theorem using some algebraic structure, and indeed it can be seen as an analogue of van der Waerden’s theorem. The main purpose of this post is to establish that equivalence. In an initial section I present the deduction of the multidimensional van der Waerden from the Hales-Jewett theorem, both to set the mood and to set the stage to later establish the analogy between van der Waerden’s theorem and the equivalent formulation of the Hales-Jewett theorem.
In a previous post I gave some motivation for, stated and proved the Hales-Jewett theorem and derived a few consequences of it. For convenience I will recall its statement here, starting with a few definitions.
Definition 1 Let . We denote by the set . Let be an element not in (some authors take for concreteness, this can become confusing at some point so I will use an abstract element ). A variable word in is an element which is not in (so the must appear somewhere in ). Given a variable word and a letter we denote by the element of obtained from be replacing each instance of with .
For instance, if and , then examples of variable words are , , but not . Using these words we have , and .
Definition 2 Let and let be a variable word in . The combinatorial line induced by is the set .
Using the word from above, the combinatorial line it induces is
It should be clear that the set can be replaced with any other set of cardinality .
The second formulation of Hakes-Jewett theorem does not require much set up
- For a set , we denote by the family of finite subsets of .
- Let , and . We define
where if and if .
is contained in a single cell of the partition, where the union is to be taken coordinatewise.
This formulation is in this site as well as in this book by McCutcheon, but in both places the formulation is a little misleading, making it seem like is only a singleton, in other words, it seems to deal with the configuration
Another equivalent formulation of Hales-Jewett theorem is an infinitistic version:
there exists a monochromatic combinatorial line.
Unlike van der Waerden or Szemerédi’s theorems, where one needs a compactness argument to deduce the finitistic version from the infinitistic one, Theorems 3 and 6 are readily seen to be equivalent, since the object colored in the infinitistic version is simply the union of all .
Similarly, there is an equivalent infinitistic formulation of Theorem 5:
is contained in a single cell of the partition.
— 1. Van der Waerden type theorem for commutative semigroups —
As mentioned in the introduction, the Hales-Jewett theorem is a set theoretical result and therefore it can be applied to any structure. We first deduce from it the multidimensional IP van der Warden theorem. Recall that the IP set generated by a set is the set of all finite sums .
where form the canonical basis of .
Proof: Let be the infinite set which generates the IP-set . Let and define the function the following way: If , we can write each uniquely as
with . We let
This will induce a finite coloring of by coloring with the color of . Let be the variable word which generates a monochromatic combinatorial line with respect to this coloring. Let be the nonempty set . Let , note that and let (where is the sequence we obtain from replacing each in with ).
I claim that the set is exactly and hence it is monochromatic. Indeed, given , let
Let be the sequence obtained from by replacing each with . Then
A careful analysis of the previous proof reveals a much more general result which holds for any commutative semigroup, and indeed for an even more general setting. The definition below of a partial semigroup is only one among many reasonable structures weaker than semigroup. For the purposes of this post I only need partial semigroups to include the class of all semigroups, and the structure from Example 2 below.
Definition 9 (Partial semigroup) Let be a set, let and let be an operation. The triple is a partial semigroup if it satisfies the following properties:
- For any , then in the sense that either both sides are undefined or both are defined and equal.
- For any and there exists such that is defined.
Observe that the second condition implies that is infinite. A partial semigroup is commutative if for every .
Example 1 Every infinite semigroup is a partial semigroup with .
Proof: We use induction on . For the claim is trivial. Assume now we are have found satisfying the claim. Let be the an enumeration of all the sums of the form with (and so ). Using the second condition of the definition of partial semigroup we can find some such that the sum is defined for all . Thus all the sums with are well defined as desired.
Definition 11 Let be partial semigroups and let . We say that is a partial semigroup homomorphism if for any for which is defined, also is defined and equals .
Observe that when and are semigroups, then a partial semigroup homomorphism is just a semigroup homomorphism.
Definition 12 Let be a partial semigroup and let . We say that is the identity of if for every , is defined and equals . We will denote the identity by .
Observe that if an identity exists it is unique.
Theorem 13 Let be a commutative partial semigroup, let be a semigroup and let be homomorphisms from to . For any finite coloring of there exist (if has no identity then simply ) and such that the set is monochromatic.
Proof: Given a finite coloring , let be given by Theorem 3 for (the number of homomorphisms) and (the number of colors/cells in the partition). Let be distinct arbitrary elements given by Lemma 10, so that all sums among those elements are defined. Let be arbitrary and let be map
Now we can partition into cells by letting for each . Applying the Hales-Jewett Theorem we can now find a variable word whose corresponding combinatorial line lies within a single .
Let be the nonempty set of the positions of the wild card and let . Let and let , which is well defined by the construction of in Lemma 10. Finally observe that is exactly the image of the monochromatic combinatorial line under the map , and hence is contained in as desired.
Observe that Theorem 8 is a direct corollary of Theorem 13. Indeed, an IP-set is the image of a homomorphism from the partial semigroup from Example 2 (without the identity ), and the configuration can be written as , where and is the set of homomorphisms
We could have required to be only a partial semigroup, but then we need to put some constraint on the homomorphisms so that the sum of their images is defined (such a restriction is essential, otherwise one can take two disjoint copies of a semigroup and make the identity map from to each of the copies. In that situation is never defined!).
— 2. Proof of the equivalency —
First we see how Theorem 3 implies Theorem 5. Unfortunately one can not simply apply Theorem 13, as we need some extra information about and in the conclusion of that theorem. However, the information needed can be extracted from the proof of Theorem 13 provided above.
Let , let and let . Let and identify with . Let be given by Theorem 3.
For each let be the homomorphism .
Assume we are given a finite coloring of , we will go through the proof of Theorem 13 above, letting for each . Letting be the identity for we find
for some , nonempty and . Observe that we can write and each . Hence, letting we have that is disjoint from each .
Finally, observe that
We now prove the other direction, i.e. that Theorem 5 implies Theorem 3. Let and assume first that for some . Then we apply Theorem 5 with this and and we get . Again we associate with (the set of same cardinality) (in other words, fix an arbitrary bijection between them).
Given a partition we can induce a partition of by putting in if and only if , where .
Invoking Theorem 5 we can now find and disjoint from all the such that
for some . This means that for every , the word , where for and for . But this forms the combinatorial line generated by the variable word where for and for . This finishes the proof for the case when .
For general , notice that if Theorem 3 is true for some , then it must be true for as well. To see this, simply map all the letters to .
More precisely, let first be such that for some . We have already showed that Theorem 3 is true for . Let and let given by the Hales-Jewett theorem for . Given a partition , we can induce a partition by letting if and only if , where if and otherwise. If is a variable word which produces a combinatorial line contained in for some (and such variable word exists by the previous argument), then the variable word , defined by if and otherwise, generates a combinatorial word in .
This finishes the proof.