ON HALES–JEWETT’S THEOREM

Giuseppe Pirillo

Summary. We prove that, for every finite semigroup S, there exist elements a_{1}, a_{2}, …, a_{k}, a_{k+1} of S and integers i_{1}, i_{2}, …, i_{k} such that

a_{1} · x^{i_{1}} · a_{2} · x^{i_{2}} · . . . · a_{k} · x^{i_{k}} · a_{k+1} = a_{1} · y^{i_{1}} · a_{2} · y^{i_{2}} · . . . · a_{k} · y^{i_{k}} · a_{k+1}

for each x, y of S.

We refer to [1] for the notion of (combinatorial) line as well as for the other combinatorial concepts we use in the sequel.

The following theorem of Hales–Jewett is well-known.

Theorem ([2]). Given any finite set A and any integer r there exists an integer N = N(A, r) such that for each n ≥ N(A, r) in any coloring of A^{n} there is always a monochromatic line.

In [1], Graham presented an interesting algebraic application of the theorem: for every finite commutative semigroup S, there exist an element a of S and an integer n such that

a · x^{n} = a · y^{n}

for each x, y of S, i.e., a · x^{n} is independent of x (shortly, we speak of the constant word a · x^{n} for S).

Trivially, there are finite non-commutative semigroups without constant word of type a · x^{n}, such as, for example, the semigroup D presented by the following Cayley table

\begin{aligned}& u & v \\ u & u & v \\ v & u & v \end{aligned}

True, for this semigroup the word x · u is constant, i.e., for this semigroup a particular case of the word x^{n} · b (“dual” of a · x^{n}) is constant. But the semigroup D′ presented by the following Cayley table

\begin{aligned}& u & v \\ u & u & u \\ v & v & v \end{aligned}

1

shows that x^{n} · b is not a constant word for each finite semigroup.

Again, the direct product D × D′, where D and D′ are as previously described, is a semigroup without constant word of type a · x^{n} and without a constant word of type x^{n} · b.

After some other considerations like the previous ones, the following question naturally arises: given any finite semigroup, does there exist a sort of constant word for it?

The following proposition gives us the answer.

Proposition. For any finite semigroup S there exist an integer k, a (k + 1)-tuple a_{1}, a_{2}, …, a_{k}, a_{k+1} of elements of S, and a k-tuple i_{1}, i_{2}, …, i_{k} of integers such that

a_{1} · x^{i_{1}} · a_{2} · x^{i_{2}} · . . . · a_{k} · x^{i_{k}} · a_{k+1}

is independent of x, i.e., it is a constant word for S.

Proof. Consider S both as an alphabet and as a set of colors. From Hales–Jewett’s theorem there exists an integer N(S, |S|) such that for each integer n ≥ N(S, |S|) and each |S|-coloring of S^{n}, a line of S^{n} is monochromatic.

This is true, in particular, when each element

(x_{1}, x_{2}, …, x_{n})

of S^{n} is colored by

x_{1} · x_{2} · . . . · x_{n},

i.e., the product in S of x_{1}, x_{2}, …, x_{n}.

Now, if the monochromatic line is the diagonal, then the conclusion follows immediately.

If the monochromatic line is not the diagonal, then the lengths of the “lakes” of the non-fixed coordinates (there is always such a coordinate) give us the integer i_{j}, and the elements a_{j} are easily obtained by looking at the fixed coordinates.

References

1. R. L. Graham, Rudiments of Ramsey theory, CBMS Regional Conference Series in Mathematics, vol. 45, American Mathematical Society,, Providence, R.I., 1981.

2. A. W. Hales and R. I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222–229.

I.A.G.A.-I.A.M.I., Consiglo Nazionale Delle Recerche, viale Morgagni 67/A, I-50134 Firenze, Italy