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
Theorem 3 (Hales-Jewett) For any
there exists some
such that for any finite partition of
into
pieces, one of the pieces contains a combinatorial line.
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
Definition 4
- For a set
, we denote by
the family of finite subsets of
.
- Let
,
and
. We define
where
if
and
if
.
Theorem 5 (Hales-Jewett, again) For any
there exists
such that for any partition of
into
cells there exist
with
nonempty and disjoint from each
, such that the configuration
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
Such a result is trivially a corollary of Theorem 5, but I do not know if it implies it (or, equivalently, Theorem 3).
Another equivalent formulation of Hales-Jewett theorem is an infinitistic version:
Theorem 6 (Infinite Hales-Jewett) Let
. For any finite coloring of
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:
Theorem 7 (Infinite Hales-Jewett, again) For any
and any finite partition of
, there exist
with
nonempty and disjoint from each
, such that the configuration
is contained in a single cell of the partition.
Again it should be clear that Theorems 5 and 7 are indeed equivalent.
— 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
.
Theorem 8 (IP-Multidimensional van der Waerden) Let
be an IP-set, let
and let
be a finite coloring. Then there exist some
,
and
such that
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
.
Example 2 Let
, let
be the family of all pairs of disjoint sets, and let
be the union. It is easy to check that this is a commutative partial semigroup.
Lemma 10 Let
be an infinite commutative partial semigroup, denoted additively, and let
. Then there exist
such that for any
the sum
is defined.
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
with .
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 —
In this section we prove that Theorems 3 and 5 are equivalent.
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.
Pingback: A proof of Deuber’s theorem using Hales-Jewett’s theorem | I Can't Believe It's Not Random!
Pingback: New polynomial and multidimensional extensions of classical partition results | I Can't Believe It's Not Random!
Pingback: An arithmetic van der Corput trick and the polynomial van der Waerden theorem | I Can't Believe It's Not Random!