Two New Extensions of the Hales-Jewett Theorem

Randall McCutcheon^{∗} Department of Mathematics University of Maryland College Park, MD 20742 randall@math.umd.edu Submitted: June 30, 2000; Accepted: September 28, 2000

Abstract: We prove two extensions of the Hales-Jewett coloring theorem. The first is a polynomial version of a finitary case of Furstenberg and Katznelson’s multiparameter elaboration of a theorem, due to Carlson, about variable words. The second is an “idempotent” version of a result of Carlson and Simpson. MSC2000: Primary 05D10; Secondary 22A15.

For k, N ∈ N, let W_{k}^{N} denote the set of length-N words on the alphabet {0, 1, ⋯, k − 1}. A variable word over W_{k}^{N} is a word w(x) of length N on the alphabet {0, 1, ⋯, k − 1, x} in which the letter x appears at least once. If w(x) is a variable word and i ∈ {0, 1, …, k − 1}, we denote by w(i) the word that is obtained by replacing each occurrence of x in w(x) by an i. The Hales-Jewett theorem states that for every k, r ∈ N, there exists N = N(k, r) ∈ N such that for any partition W_{k}^{N} = ⋃_{i=1}^{r} C_{i}, there exist j, 1 ≤ j ≤ r, and a variable word w(x) over W_{k}^{N} such that {w(i) : i ∈ {0, 1, …, k − 1}} ⊂ C_{j}.

1. Finitary extensions.

In [BL], V. Bergelson and A. Leibman provided a “polynomial” version of the Hales-Jewett theorem. In order to formulate their result, we must develop some terminology. Let l ∈ N. A set-monomial (over N^{l}) in the variable X is an expression m(X) = S_{1} × S_{2} × ⋯ × S_{l}, where for each i, 1 ≤ i ≤ l, S_{i} is either the symbol X or a nonempty singleton subset of N (these are called coordinate coefficients). The degree of the monomial is the number of times the symbol X appears in the list S_{1}, ⋯, S_{l}. For example, taking l = 3, m(X) = {5} × X × X is a set-monomial of degree 2, while m(X) = X × {17} × {2} is a set-monomial of degree 1. A set-polynomial is an expression of the form P (X) = m_{1}(X) ∪ m_{2}(X) ∪ ⋯ ∪ m_{k}(X), where k ∈ N and m_{1}(X), ⋯, m_{k}(X) are set-monomials. The degree of a set-polynomial is the largest degree of its set-monomial “summands”, and its constant term consists of the “sum” of

∗The author acknowledges support from the National Science Foundation via a post doctoral fellowship administered by the University of Maryland. those m_{i} that are constant, i.e. of degree zero. Finally, we say that two set polynomials are disjoint if they share no set-monomial summands in common.

Let F(S) denote the family of non-empty finite subsets of a set S. Any nonempty set polynomial p(A) determines a function from F(N) to F(N^{l}) in the obvious way (interpreting the symbol × as Cartesian product and the symbol ∪ as union). Notice that if P (X) and Q(X) are disjoint set-polynomials and B ∈ F(N) contains no coordinate coefficients of either P or Q then P (B) ∩ Q(B) = ∅.

Here now is the Bergelson-Leibman coloring theorem.

Theorem 1.1. Let l ∈ N and let P be a finite family of set-polynomials over N^{l} whose constant terms are empty. Let I ⊂ N be any finite set and let r ∈ N. There exists a finite set S ⊂ N, with S ∩ I = ∅, such that if F( ⋃_{P ∈P} P (S)) = ⋃_{i=1}^{r} C_{i} then there exists i, 1 ≤ i ≤ r, some non-empty B ⊂ S, and some A ⊂ ⋃_{P ∈P} P (S) with A ∩ P (B) = ∅ for all P ∈ P and {A ∪ P (B) : P ∈ P} ⊂ C_{i}.

Although the “polynomial” nature of Theorem 1.1 is at once clear, it is not immediately obvious that it includes the Hales-Jewett theorem as a special case, so we shall give a different formulation, and derive it from Theorem 1.1.

Let k, N, d ∈ N. We denote by M_{k}^{N}(d) the set of all function ϕ : {1, 2, …, N}^{d} → {0, 1, …, k − 1}. When d = 2, one may identify this with the set of N × N matrices with entries belonging to {0, 1, …, k − 1}, so in general we shall refer to the members of M_{k}^{N}(d) as matrices, even when d > 2. A variable matrix over M_{k}^{N}(d) is a function ψ : {1, 2, …, N}^{d} → {0, 1, …, k − 1, x} for which x appears in the range. The support of ψ is the set ψ^{−1}(x); that is, the set of locations in the matrix where the symbol x appears. If ψ is a variable matrix over M_{k}^{N}(d), ψ is said to be standard if its support has the form B^{d} for some B ⊂ {1, 2, …, N}.

We shall also consider multi-variable matrices ψ : {1, 2, …, N}^{d} → {0, 1, …, k − 1, x_{1}, x_{2}, …, x_{t}}. In this case we require that all the x_{i} appear in the range, and we call ψ^{−1}(x_{i}) the ith support of ψ. If ψ is a t-variable matrix then ψ gives rise, via substitution, to a function w(x_{1}, …, x_{t}) : {0, …, k − 1} → M_{k}^{N}(d), and we will often refer to this induced w instead of to ψ when dealing with variable matrices.

We require the following nonconventional notion of addition of matrices. We will introduce this notion in the context of dimension 2, although the obvious analogs are valid in arbitrary dimension. Let w = (w_{ij})_{i,j=1}^{M} and y = (y_{ij})_{i,j=1}^{M} be matrices (variable or otherwise). If there exist disjoint sets W and Y, whose union is {1, …, M}^{2}, such that w_{ij} = 0 for (i, j) ∈ W and y_{ij} = 0 for (i, j) ∈ Y, then we define w + y = (z_{ij})_{i,j=1}^{M}, where z_{ij} = w_{ij} if (i, j) ∈ Y and z_{ij} = y_{ij} if (i, j) ∈ W. If however there exists (i, j) ∈ {1, …, M}^{2} such that w_{ij} ≠ 0 ≠ y_{ij} then the sum w + y is undefined.

Theorem 1.2 The following are equivalent:

(a) Theorem 1.1.

(b) Let d ∈ N and let (P_{i}(X))_{i=1}^{t} be pairwise disjoint set-polynomials over N^{d} having empty constant term and let J be any finite subset of N containing all coordinate coefficients represented in the P_{i}’s. Let k, r ∈ N. There exists N ∈ N having the property that if M_{k}^{N}(d) = ⋃_{i=1}^{r} C_{i} then there exists a set B ⊂ {1, 2, …, N} \ J, a variable matrix w(x_{1}, …, x_{t}), and n, with 1 ≤ n ≤ r, such that

(i) The ith support of w_{i} is P_{i}(B), 1 ≤ i ≤ t,

(ii) {w(i_{1}, …, i_{t}) : i_{j} ∈ {0, 1, …, k − 1}, 1 ≤ j ≤ t} ⊂ C_{n}, and

(iii) w is 0 on J^{d}.

(c) Let k, r, d ∈ N. There exists N such that for every partition M_{k}^{N}(d) = ⋃_{i=1}^{r} C_{i} there is a standard variable matrix w(x) over M_{k}^{N}(d) such that {w(i) : i ∈ {0, 1, …, k− 1}} lies in one cell C_{j}.

Proof. First we show (a) implies (b). Choose b ∈ N with 2^{b} ≥ k and consider the set

P = { ⋃_{s=1}^{t} (E_{s} × P_{s}(X)) : E_{s} ⊂ {1, …, b}, 1 ≤ s ≤ t}.

P is a finite family of set polynomials over N^{d+1}. Let I = J ∪ {1, …, b} and let l = d + 1. Now pick a finite subset S ⊂ N as guaranteed by Theorem 1.1. Notice in particular that S ∩ I = ∅. Pick N ∈ N such that S ∪ I ⊂ {1, …, N}. Suppose that M_{k}^{N}(d) = ⋃_{i=1}^{r} C_{i}. Form a map π : F({1, …, b} × {1, …, N}^{d}) → M_{k}^{N}(d) as follows:

(π(A))(a_{1}, …, a_{d}) = min { ∑_{(j,a_{1},...,a_{d})∈A} 2^{j−1}, k − 1}.

Now put D_{i} = π^{−1}(C_{i}), 1 ≤ i ≤ r. Then F( ⋃_{P ∈P} P (S)) ⊂ ⋃_{i=1}^{r} D_{i} so there exist B ⊂ S and A ⊂ ⋃_{P ∈P} P (S) with A ∩ P (B) = ∅ for all P ∈ P (in particular A ∩ ({1, …, b} × P_{i}(B)) = ∅, 1 ≤ i ≤ t) and such that for some z, 1 ≤ z ≤ r,

{A ∪ ⋃_{s=1}^{t} (E_{s} × P_{s}(B)) : E_{s} ⊂ {1, …, b}, 1 ≤ s ≤ t} ⊂ D_{z}.

Define a variable matrix ψ = w(x_{1}, …, x_{t}) over M_{k}^{N}(d) by

1. ψ((a_{1}, …, a_{d})) = x_{i} if (a_{1}, …, a_{d}) ∈ P_{i}(B), and

2. ψ((a_{1}, …, a_{d})) = π(A)(a_{1}, …, a_{d}) otherwise. (Recall that the sets {P_{i}(B) : 1 ≤ i ≤ t} are pairwise disjoint, owing to the fact that the P_{i}’s are pairwise disjoint and B contains no coordinate coefficients of any P_{i}.)

The ith support of w is clearly P_{i}(B), 1 ≤ i ≤ t. Now for any i_{1}, …, i_{t} ∈ {0, 1, …, k − 1}, we pick sets E_{s} ⊂ {1, … b} such that ∑_{n∈E_{s}} 2^{n−1} = i_{s}, 1 ≤ s ≤ t, and note that

w(i_{1}, …, i_{t}) = π(A) + ∑_{s=1}^{t} π(E_{s} × P_{s}(B)) = π(A ∪ ⋃_{s=1}^{t} (E_{s} × P_{s}(B))) ∈ C_{z}.

Since J ⊂ I, S ∩ I = ∅ and A ⊂ ⋃_{P ∈P} P (S), we have A ∩ ({1, …, b} × J^{d}) = ∅, so that w is zero on J^{d}.

This finishes the proof that (a) implies (b). Letting t = 1 and P_{1}(X) = X^{d}, one sees that (b) implies (c). Therefore all that remains is to show (c) implies (a).

Let {Q_{1}, ⋯, Q_{t}} be the family of all set-monomials that appear in any of the set-polynomials of P, and write Q_{i}(X) = S_{1}^{(i)} × ⋯ × S_{d}^{(i)}, where each S_{j}^{(i)} is either a singleton or the symbol X. Let k = 2^{t} and put d = l.

Let N be as promised by (c) and choose y ∈ N larger than all coordinate coefficients in question and larger than any member of I. Set S = {y + 1, …, y + N}. Suppose now that F( ⋃_{P ∈P} P (S)) = ⋃_{i=1}^{r} C_{i}.

Let Y be the family of t-tuples of subsets of {1, …, N}^{d}. We identify Y with M_{k}^{N}(d) by

(A_{1}, …, A_{t}) ↔ w if and only if w(i_{1}, …, i_{d}) = ∑_{s=1}^{t} 2^{1_{As} ((i_{1},...,i_{d}))}.

Our next task is to construct a map π sending Y (and thus, effectively, M_{k}^{N}(d)) to F( ⋃_{s=1}^{t} Q_{s}(S)) = F( ⋃_{P ∈P} P (S)). First we define π for t-tuples of sets, one of which is a singleton and the rest of which are empty. Suppose then that i is fixed, A_{j} = ∅ for i ≠ j and A_{i} = {(a_{1}, …, a_{d})}. Recall that Q_{i}(X) = S_{1}^{(i)} × ⋯ S_{d}^{(i)}, where some of the S_{j}^{(i)} are singletons and some are X. Let T = {j : S_{j}^{(i)} = X}. Suppose that for all j ∈ {1, …, d} \ T, a_{j} = min {a_{i} : i ∈ T }. If this condition is not met, we set π((A_{1}, ⋯, A_{t})) = ∅. If the condition is met, put b_{j} = S_{j}^{(i)} if S_{j}^{(i)} is a singleton and b_{j} = a_{j} + y if S_{j}^{(i)} = X, 1 ≤ j ≤ d, and set π(A_{1}, …, A_{t}) = {(b_{1}, …, b_{d})}. We now extend π to the desired domain by requiring that π(A_{1} ∪ B_{1}, …, A_{t} ∪ B_{t}) = π(A_{1}, …, A_{t}) ∪ π(B_{1}, …, B_{t}). (This extension is unique.)

We now confirm that π has the following two properties. First, if C ⊂ {1, …, N}, then letting B = C + y = {c + y : c ∈ C}, fixing i and putting A_{i} = C^{d} and A_{j} = ∅ for all j ≠ i, π(A_{1}, …, A_{t}) = Q_{i}(B). Second, if A_{i} ∩ B_{i} = ∅ for all i, π((A_{1}, …, A_{t})) ∩ π((B_{1}, …, B_{t})) = ∅.

We now use the map π to draw back the partition. Namely, let D_{i} = π^{−1}(C_{i}), 1 ≤ i ≤ r. Then Y = ⋃_{i=1}^{r} D_{i}. But Y is identified with M_{k}^{N}(d), so by (c) there exists a standard variable matrix w(x) and some z, 1 ≤ z ≤ r, such that W = {w(i) : i ∈ {0, 1, …, k − 1}} ⊂ D_{z}. (After the identification, of course.)

Let C^{d} be the support of w(x). Let (A_{1}, …, A_{t}) be the member of Y that is identified with w(0). Then A_{i} ∩ C^{d} = ∅ for 1 ≤ i ≤ t, so that π((A_{1}, …, A_{t})) ∩ π((C^{d}, …, C^{d})) = ∅. Moreover, in Y, W takes the form

W = {(A_{1}, …, A_{t}) ∪ (F_{1}, …, F_{t}) : F_{i} ∈ {∅, C^{d}}, 1 ≤ i ≤ t}.

Let A = π((A_{1}, …, A_{t})) and let B = C +y. Let P ∈ P and choose a set E ⊂ {1, …, t} such that P (X) = ⋃_{i∈E} Q_{i}(X). Next put F_{j} = C^{d} if j ∈ E and F_{j} = ∅ otherwise. Then (A_{1}, …, A_{t}) ∪ (F_{1}, …, F_{t}) ∈ W. But π(W) ⊂ C_{z}, so (A ∪ ⋃_{i∈E} Q_{i}(B^{d})) ∈ C_{z}.

Formulations (a) and (b) in Theorem 1.2 are more powerful, on the surface, than formulation (c) and hence it is good to have them on hand for some applications, but formulation (c) has aesthetic advantages. For one, when d = 1 it gives precisely the Hales-Jewett theorem.

We now shift our focus slightly. Let A be a finite field and let n ∈ N. Then A^{n} is a vector space over A. A translate of a t-dimensional vector subspace of A^{n} is called a t-space. The following theorem was proved by Graham, Leeb and Rothschild ([GLR]).

Theorem 1.3 Let r, n, t ∈ N. There exists N = N(r, n, t) such that for any r-coloring of the n-spaces of A^{N} there exists a t-space V such that the family of n-spaces contained in V is monochromatic.

We mention this result because it is so well known. It is not quite in keeping with our theme, namely extensions of the Hales-Jewett theorem, but if we restrict attention to a certain sub-class of n-spaces, the situation becomes much more “Hales-Jewett-like”.

Recall that a variable word over W_{k} is a word on the alphabet {1, 2, ⋯, k, x} in which the symbol x appears at least once. An n-variable word is a word on the alphabet {1, ⋯, k, x_{1}, ⋯, x_{n}} in which all the x_{i}’s occur and for which no occurrence of x_{i+1} precedes an occurrence of x_{i}, 1 ≤ i ≤ n−1. If w(x_{1}, ⋯, x_{n}) is an n-variable word over W_{k}^{M} then the set {w(t_{1}, t_{2}, ⋯, t_{n}) : 1 ≤ t_{i} ≤ k, i = 1, ⋯, n} will be called the space associated with w. (Notice now that if k = p^{s} for some prime p and s ∈ N and we identify {0, 1, …, k −1} with a field A having p^{s} elements, choose a basis {v_{1}, ⋯, v_{M}} for A^{M} and identify the word w_{1}w_{2} ⋯ w_{M} with the vector ∑_{i=1}^{M} w_{i}v_{i}, then the space associated with an n-variable word is indeed an n-space in A^{N}. However, not all n-spaces can be obtained in this way.)

If w is a t-variable word and v is an n-variable word and the space associated with v is contained in the space associated with w, v will be called an n-subword of w. Another way of seeing this is, if w(y_{1}, ⋯, y_{t}) is a t-variable word then the n-variable subwords of it (in the variables x_{1}, ⋯, x_{n}) are of the form w(z_{1}, ⋯, z_{t}), where z_{1} ⋯ z_{t} is an n-variable word over W_{k}(t).

The following theorem is a finitary consequence of a generalization of T. Carlson’s theorem ([C, Lemma 5.9]) due to H. Furstenberg and Y. Katznelson (see [FK, Theorem 3.1]). It extends the Hales-Jewett theorem in the following sense. If we call regular words (that is, elements of W_{k}^{M}) 0-variable words, then the Hales-Jewett theorem corresponds to the case n = 0, t = 1 of Theorem 1.4.

Theorem 1.4 Let k, r, n, t ∈ N be given. There exists M = M(k, r, n, t) such that for every r-cell partition of the n-variable words over W_{k}^{M} there exists a t-variable word all of whose n-subwords lie in the same cell.

We seek now to give a polynomial analog of Theorem 1.4. To this end, let k, N, d, n ∈ N and suppose we have non-empty sets B_{i} ⊂ {1, …, N}, 1 ≤ i ≤ n, with B_{1} < ⋯ < B_{n}. (Here and elsewhere in this paper, we write A < B where A and B are non-empty finite subsets of N when a < b for all a ∈ A and b ∈ B.) If w(x_{1}, ⋯, x_{n^{d}}) is an n^{d}-variable matrix over M_{k}^{N}(d) whose supports are the sets B_{i_{1}} × B_{i_{2}} × ⋯ × B_{i_{d}}, 1 ≤ i_{1}, …, i_{d} ≤ n, then w is said to be a standard n^{d}-variable matrix. The space associated with w is {w(i_{1}, …, i_{n^{d}}) : i_{1}, …, i_{n^{d}} ∈ {0, 1, …, k−1}}.

If n_{1} ≤ n_{2}, w_{1} is a standard n_{1}^{d}-variable matrix, w_{2} is a standard n_{2}^{d}-variable matrix, and the space associated with w_{1} is contained in the space associated with w_{2}, then we will say that w_{1} is a submatrix of w_{2}.

Our main theorem in this section is Theorem 1.7. This theorem will be a version of Theorem 1.4 valid in any finite dimension d. However, in order to simplify the proof notationally, we will take d to be 2. We need two lemmas for the proof.

Lemma 1.5 Let R, k, T ∈ N. There exists M = M(R, k, T) ∈ N having the following property: Let E denote the set of matrices (a_{ij})_{i,j=1}^{T +M} such that

(a) (a_{ij})_{i,j=1}^{T +M} is a standard n^{2}-variable matrix, and

(b) a_{ij} ∈ {0, 1, …, k −1} if either i > T or j > T (that is, all the supports of (a_{ij})_{i,j=1}^{T +M} lie in {1, …, T }^{2}). Then for any R-coloring γ of E there exists a (2T +1)-variable matrix w(x_{1}, …, x_{2T +1}) = (b_{ij})_{i,j=1}^{T +M} over M_{k}^{T +M}(2) that satisfies:

(1) b_{ij} = 0 if (i, j) ∈ {1, …, T }^{2}.

(2) There exists a non-empty set B ⊂ {T + 1, …, T + M} such that the supports of w are {i} × B and B × {i}, i ∈ {1, …, T }, B × B.

(3) For any standard n^{2}-variable matrix m = (c_{ij})_{i,j=1}^{T +M} satisfying c_{ij} = 0 if (i, j) ∉ {1, …, T }^{2}, the set {m + w(i_{1}, …, i_{2T +1}) : i_{j} ∈ {0, 1, …, k − 1}, 1 ≤ j ≤ 2T + 1} is γ-monochromatic.

Proof. Let P_{i}(X), 1 ≤ i ≤ 2T + 1, denote the set polynomials {i} × X and X × {i}, i ∈ {1, …, T }, and X×X. These are pairwise disjoint set-polynomials (in fact, distinct set-monomials). Let G be the set of all standard n^{2}-variable matrices over M_{k}^{T} (2). Let J = {1, …, T }, t = 2T + 1, r = R^{|G|} + 1, d = 2, and put M = N − T, where N is the number guaranteed by Theorem 1.2 (b). Let γ be an R-coloring of E.

We now construct a (R^{|G|} + 1)-cell partition of M_{k}^{N}(2). For (d_{ij})_{i,j=1}^{N}, (f_{ij})_{i,j=1}^{N} ∈ M_{k}^{N}(2), we write (d_{ij})_{i,j=1}^{N} ∼ (f_{ij})_{i,j=1}^{N} if for every standard n^{2}-variable matrix m = (e_{ij})_{i,j=1}^{T +M} satisfying e_{ij} = 0 for all (i, j) ∉ {1, …, T }^{2}, we have γ(m + (d_{ij})_{i,j=1}^{N}) = γ(m + (f_{ij})_{i,j=1}^{N}), in the sense that if either side of this expression is defined then so is the other and they are equal. (Hence in particular all matrices that have a non-zero entry for any index point in {1, …, T }^{2} are relegated to the same equivalence class. The other equivalence classes are characterized by the value of γ at |G| points, hence the equivalence classes of ∼ form an r-cell partition.)

According to the conditions whereby M was chosen, there exists a non-empty set B ⊂ {1, …, N} \ J = {T + 1, …, T + M} and a variable matrix w(x_{1}, …, x_{2T +1}) = (b_{ij})_{i,j=1}^{T +M} such that the supports of w are P_{i}(B), 1 ≤ i ≤ 2T + 1, and the set {w(i_{1}, …, i_{2T +1}) : i_{j} ∈ {0, 1, …, k − 1}, 1 ≤ j ≤ 2T + 1} lies entirely in a single equivalence class of ∼ and such that moreover b_{ij} = 0 for all (i, j) ∈ J^{2} = {1, …, T }^{2}. The variable matrix thus chosen satisfies (1), (2) and (3).

Our second lemma is a finitary version of a theorem proved independently by Milliken ([Mi]) and Taylor ([T]). Recall that if A is a set then F(A) is the family of nonempty finite subsets of A. We write F = F(N) as a kind of shorthand. Recall that for α, β ∈ F, we write α < β if max α < min β. For k ∈ N, and a sequence (α_{i})_{i=1}^{∞} ⊂ F, we write F U(< α_{i} >_{i=1}^{∞}) = {⋃_{i∈A} α_{i} : A ∈ F}. (F U stands for “finite unions.” One may consider the set of finite unions of a finite sequence as well, of course.) If G ⊂ F, let G_{<}^{k} be the set of k-tuples (α_{1}, …, α_{k}) in G^{k} for which α_{1} < α_{2} < ⋯ α_{k}. The Milliken-Taylor theorem states that for any finite partition F_{<}^{k} = ⋃_{i=1}^{r} C_{i}, there exists j, with 1 ≤ j ≤ r, and a sequence (α_{i})_{i=1}^{∞}, with α_{1} < α_{2} < ⋯, such that (F U(< α_{i} >_{i=1}^{∞}))_{<}^{k} ⊂ C_{j}.

We shall not need the full strength of the Milliken-Taylor theorem, but only the following finitary version of it.

Lemma 1.6 Let r, n, t ∈ N. There exists L = L(r, n, t) ∈ N such that if {(α_{,} …, α_{n}) : ∅ ≠ α_{i} ⊂ {1, …, L}, α_{1} < α_{2} < ⋯ < α_{n}} = ⋃_{i=1}^{r} C_{i} then there exist non-empty sets α_{i} ⊂ {1, …, L}, 1 ≤ i ≤ t, with α_{1} < α_{2} < ⋯ < α_{t}, and j, 1 ≤ j ≤ r, with (F U(< α_{i} >_{i=1}^{t}))_{<}^{n} ⊂ C_{j}.

Here now is the main theorem of this section.

Theorem 1.7 Let k, r, n, t, d ∈ N. There exists N = N(k, r, n, t, d) such that for every r-cell partition of the standard n^{d}-variable matrices over M_{k}^{N}(d), there exists a standard t^{d}-variable matrix over M_{k}^{N}(d) all of whose standard n^{d}-variable submatrices lie in the same cell.

Before giving the proof of Theorem 1.7, let us make a few remarks about notation and also Lemma 1.5. First, the object E defined in the lemma consists of variable words with supports in {1, …, T }^{2}, and the variable word that is found must have zero entries over {1, …, T }^{2}. We note that there is nothing remarkable here about the set {1, …, T }^{2}. Once M has been chosen, any set S^{2} ⊂ {1, …, M + T }^{2} where |S| = T, would serve just as nicely in this capacity. This is a simple result of the fact that standard variable matrices remain such upon permuting the indices {1, …, M + T }.

Next, the lemma as stated applies to M_{k}^{T +M}(2) and variable words over it. In our application of it, we shall be applying it in the context of an isomorphic copy of M_{k}^{T +M}, namely the space determined by an appropriate standard (M + T)^{2}-variable matrix. Notationally, it is convenient to write such a variable matrix with a matrix of variables, namely as w((x_{ij})_{i,j=1}^{T +M}), where it is understood that the variable x_{ij} has support B_{i} × B_{j} for some non-empty sets B_{1} < B_{2} < ⋯ < B_{T +M}. When applying Lemma 1.6 to the space associated with the variable matrix, it is important to note that if (m_{ij}) is a standard n^{2}-variable matrix over M_{k}^{T +M}(2), then w((m_{ij})_{i,j=1}^{T +M}) becomes, upon substitution, a standard n^{2}-variable matrix. Moreover, all standard n^{2}-variable matrices over the space in question arise in this fashion.

Proof of Theorem 1.7 Recall that our plan is to confine ourselves in the proof to the d = 2 case. The changes necessary to extend the proof to general d are minor and rather obvious, but it will be difficult enough to keep track of all the symbols in two dimensions, so we opt to simplify.

Let L = L(r, n, t) be as guaranteed by Lemma 1.6. We now use Lemma 1.5 iteratively. Let M_{1} = M(r, k, L − 1). Having chosen M_{1}, …, M_{s−1}, let M_{s} = M(r, k, L − s + M_{1} + M_{2} + ⋯ + M_{s−1}). Continue until M_{L} = M(r, k, M_{1} + ⋯ + M_{L−1}) has been chosen. For i = 1, 2, …, L, let N_{i} = M_{1} + ⋯ + M_{i}, and put N = N_{L}.

Suppose now we are given an r-coloring γ of the standard n^{2}-variable matrices over M_{k}^{N}(2). By virtue of the way M_{L} was chosen, we can find a non-empty set B_{L} ⊂ {N_{L−1} +1, …, N_{L}} and a (2N_{L−1} +1)-variable matrix W_{L} that has zero entries on {1, …, N_{L−1}}^{2} and whose supports are {i} × B_{L} and B_{L} × {i}, 1 ≤ i ≤ N_{L−1}, and B_{L} × B_{L}, with the following property: for every standard n^{2}-variable matrix m over M_{k}^{N}(2) whose entries are zero except possibly on {1, …, N_{L−1}}^{2}, the value of γ on m + w_{L}(i_{1}, ⋯, i_{2N_{L−1}+1}) remains constant as the i_{j}’s move independently over {0, 1, …, k − 1}.

We now restrict attention to the space, call it S_{L−1}, of matrices p + f, where p has zero entries except possibly on {1, …, N_{L−1}}^{2} and f is in the range of w_{L}. This space may be realized as the space associated with an appropriately chosen standard (N_{L−1} + 1)^{2}-variable matrix, hence is isomorphic to M_{k}^{N_{L−1}+1}, and so the remarks made prior to the proof apply. Namely, we can use Lemma 1.5 in this space. Specifically, since M_{L−1} = M(r, k, N_{L−2} + 1), we can find a non-empty set B_{L−1} ⊂ {N_{L−2} +1, …, N_{L−1}} and a variable matrix w_{L−1}(x_{1}, …, x_{2(N_{L−1}+1)+1}) over S_{L−1} with the following properties. (This part is somewhat tedious, as one must be very careful to interpret Lemma 1.5 correctly in this specialized context of a space that is merely isomorphic to M_{k}^{N}(2).)

1. Let w_{L−1} = (b_{ij}) and let w_{L} = (c_{ij}). If (i, j) ∉ {1, …, N_{L−1}}^{2}, and c_{ij} ∈ {0, 1, …, k − 1}, then b_{ij} = c_{ij}.

2. b_{ij} = 0 for all (i, j) ∈ ({1, …, N_{L−2}} ∪ B_{L})^{2}.

3. The supports of w_{L−1} are the sets {i}×B_{L−1} and B_{L−1}×{i}, i ∈ {1, …, N_{L−2}}, B_{L} × B_{L−1}, B_{L−1} × B_{L}, and B_{L−1} × B_{L−1}.

4. Let m = (d_{ij}) be any standard n^{2}-variable matrix such that d_{ij} = 0 for every (i, j) ∉ ({1, …, N_{L−2}} ∪ B_{L})^{2}. Then the value of γ remains constant on m + w_{L−1}(i_{1}, …, i_{2N_{L−1}+3}) as the i_{j}’s run over {0, 1, …, k − 1} independently.

At the next stage we restrict attention to the space, call it S_{L−2}, of matrices of the form p + f where f is in the range of w_{L−1} and p is constant on each of the sets:

a. {(i, j)}, (i, j) ∈ {1, …, N_{L−2}}^{2},

b. {i} × B_{L} and B_{L} × {i}, i ∈ {1, …, N_{L−2}},
c. B_{L} × B_{L},

while being zero elsewhere.

This space is isomorphic to M_{k}^{N_{l−2}+2}, and so by the way M_{L−2} was picked, Lemma 1.5 applies. The variable word (over S_{L−2}) w_{L−2} that is found will have 2N_{L−3} + 5 variables and its supports will be {i} × B_{L−2} and B_{L−2} × {i} for i ∈ {1, …, N_{L−3}}, B_{L−1} × B_{L−2}, B_{L−2} × B_{L−1}, B_{L} × B_{L−2}, B_{L−2} × B_{L}, and B_{L−2} × B_{L−2}. Here ∅ ≠ B_{L−2} ⊂ {N_{L−3} + 1, …, N_{L−2}}. w_{L−2} will have zero entries in ({1, …, N_{L−3}} ∪ B_{L} ∪ B_{L−1})^{2}. w_{L−2} will agree with w_{L−1} on those indices (i, j) lying outside of {1, …, N_{L−2}}^{2} on which w_{L−1} takes a value in {0, 1, …, k − 1}. Finally if m = (d_{ij}) is any standard n^{2}-variable matrix such that d_{ij} = 0 for every (i, j) ∉ ({1, …, N_{L−3}}∪ B_{L} ∪ B_{L−1})^{2}, then the value of γ remains constant on m + w_{L−2}(i_{1}, …, i_{2N_{L−2}+5}) as the i_{j}’s run over {0, 1, …, k − 1} independently.

Continue choosing sets B_{i} and variable matrices w_{i}. By the time w_{1} is chosen, it’s supports will be on B_{i} × B_{1} and B_{1} × B_{i}, 2 ≤ i ≤ L, and B_{1} × B_{1}, where B_{1} ⊂ {1, … N_{1}}. w_{1} will have zero entries on B_{i} × B_{j}, 2 ≤ i, j ≤ L, and will agree with w_{2} elsewhere (that is, on the entries of w_{2} that are in {0, 1, …, k − 1}) outside of {1, …, N_{1}}^{2}. w_{1} will have the property that for every standard n^{2}-variable matrix m, whose entries are constant over each set B_{i} × B_{j}, 2 ≤ i, j ≤ L, and zero elsewhere, the value of γ on m + w_{1}(i_{1}, …, i_{2L+1}) remains constant as the i_{j}’s move independently over {0, 1, …, k − 1}.

Finally, let v((x_{ij})_{i,j=1}^{L}) be the standard L^{2}-variable matrix that agrees with w_{1} for those indices on which w_{1} takes a value in {0, 1, …, k −1}, and whose variables x_{ij} have supports B_{i} × B_{j}, respectively, 1 ≤ i, j ≤ L. The construction we have followed gives v the following property: if (h_{ij})_{i,j=1}^{L} and (s_{ij})_{i,j=1}^{L} are standard n^{2}-variable

matrices whose supports are identical, then γ(v((h_{ij})_{i,j=1}^{L})) = γ(v((s_{ij})_{i,j=1}^{L})). In demonstrating this, we may assume without loss of generality that the two L × L matrices in question differ at only one entry, say at position (x, y). Clearly h_{xy} and s_{xy} are in {0, 1, …, k − 1}.

Suppose for convenience that x ≤ y. One may show that there exist matrices p_{1}, p_{2} and m = (d_{ij}) such that

1. p_{1} and p_{2} are each in the range of w_{x}.

2. m is a standard n^{2}-variable matrix with d_{ij} = 0 if (i, j) ∉ ({1, … N_{x−1}}∪B_{L} ∪ B_{L−1} ∪ ⋯ ∪ B_{x+1})^{2}.

3. m + p_{1} = v((h_{ij})_{i,j=1}^{L}) and m + p_{2} = v((s_{ij})_{i,j=1}^{L}).

Indeed, put U = ({1, … N_{x−1}} ∪ B_{L} ∪ B_{L−1} ∪ ⋯ ∪ B_{x+1})^{2}. Let m coincide with v((h_{ij})_{i,j=1}^{L}) on U and have zero entries on U^{c}, then let p_{1} coincide with v((h_{ij})_{i,j=1}^{L}) on U^{c}, and have zero entries on U. p_{2} is chosen similarly, but with respect to v((s_{ij})_{i,j=1}^{L}).

According to the criteria by which w_{x} was chosen, γ(m + p_{1}) = γ(m + p_{2}), as required.

Let us take stock of the situation. We have found a standard L^{2}-variable matrix v with the property that the value of γ on its standard n^{2}-variable sub-matrices v((h_{ij})_{i,j=1}^{L}) depends only on the location of the supports of the variables in the underlying matrix (h_{ij})_{i,j=1}^{L}. Now, these variables are always supported on sets A_{i} × A_{j}, 1 ≤ i, j ≤ n, where each A_{i} ⊂ {1, …, L} is non-empty and A_{1} < A_{2} < ⋯ < A_{n}. In other words, the function γ restricted to the standard n^{2}-variable submatrices of v is the lift of an r-coloring γ′ of the set (F({1, …, L}))_{<}^{n}. By the choice of L, there thus exist non-empty sets C_{i} ⊂ {1, …, L}, 1 ≤ i ≤ t, with C_{1} < C_{2} < ⋯ < C_{t}, such that γ′ is constant on the family of n-tuples (A_{1}, ⋯, A_{n}), where A_{i} ∈ F U({C_{1}, …, C_{t}}), 1 ≤ i ≤ n, and A_{1} < A_{2} < ⋯ < A_{n}. Let now (h_{ij})_{i,j=1}^{L} be any standard t^{2}-variable matrix over M_{k}^{L}(2) whose supports lie on C_{i} × C_{j}, 1 ≤ i ≤ t. Then v((h_{ij})_{i,j=1}^{L}) is a standard t^{2}-variable matrix over M_{k}^{N}(2) whose standard n^{2}-variable submatrices are γ-monochromatic.

Theorem 1.7 extends the Bergelson-Leibman coloring theorem in the sense that if one defines zero-variable matrices to be matrices with entries in {0, 1, …, k − 1} then Theorem 1.2 (c) is precisely the case n = 0, t = 1 of Theorem 1.7.

2. Infinitary extensions.

Let k ∈ N and let w(x) be a variable word over W_{k}. If the first letter of w(x) is x, then we say that w(x) is a left-sided variable word. The following “infinitary” Hales-Jewett theorem is due to T. Carlson and S. Simpson.

Theorem 2.1 ([CS]) Let k, r ∈ N and suppose W_{k} = ⋃_{i=1}^{r} C_{i}. Then there exists z, with 1 ≤ z ≤ r, a variable word w_{1}(x), and a sequence of left-sided variable words (w_{i}(x))_{i=2}^{∞} such that for all N ∈ N and all i_{1}, ⋯, i_{N} ∈ {0, 1, …, k − 1}, w_{1}(i_{1})w_{2}(i_{2}) ⋯ w_{N}(i_{N}) ∈ C_{z}.

Furstenberg and Katznelson indicated a similar theorem (see the remark following Theorem 2.5 in [FK]).

Theorem 2.2 Let k, r ∈ N and suppose W_{k} = ⋃_{i=1}^{r} C_{i}. Then there exists z, with 1 ≤ z ≤ r, and a sequence of variable words (w_{i}(x))_{i=1}^{∞} such that for all N ∈ N, all b_{1}, b_{2}, …, b_{N} ∈ N with b_{1} < b_{2} < ⋯ < b_{N}, and all i_{1}, ⋯, i_{N} ∈ {0, 1, …, k − 1}, w_{b_{1}}(i_{1})w_{b_{2}}(i_{2}) ⋯ w_{b_{N}} (i_{N}) ∈ C_{z}.

Theorem 2.2 is stronger in the sense that one gets more products in the desired cell, but Theorem 2.1 is stronger in the sense that the variable words, excepting the first one, are required to be left-sided. One aesthetic advantage of left variable words is that the determination of the words becomes somewhat more canonical. So, for example, if one were given that w_{1}(2)w_{2}(1) = 225612114 and w_{1}(1)w_{2}(2) = 125622124, where w_{2}(x) is known to be a left variable word, we immediately determine that w_{1}(x) = x256 and w_{2}(x) = x21x4. Such a conclusion would not be warranted in the event w_{2}(x) is not known to be a left variable word.

We remark that Hindman’s theorem ([H1]) follows from Theorem 2.2. In this section we shall prove the following result, which strengthens Theorem 2.1 in a manner having the spirit of Theorem 2.2.

Theorem 2.3 Let k, r ∈ N and suppose W_{k} = ⋃_{i=1}^{r} C_{i}. Then there exists z, with 1 ≤ z ≤ r, a variable word w_{1}(x), and a sequence of left-sided variable words (w_{i}(x))_{i=2}^{∞} such that for all N ∈ N, all b_{1}, b_{2}, …, b_{N} ∈ N with 1 = b_{1} < b_{2} < ⋯ < b_{N}, and all i_{1}, ⋯, i_{N} ∈ {0, 1, …, k − 1}, w_{b_{1}}(i_{1})w_{b_{2}}(i_{2}) ⋯ w_{b_{N}} (i_{N}) ∈ C_{z}.

The semigroup operation on W_{k} extends to its Stone-Čech compactification βW_{k} in such a way as to make βW_{k} a compact left topological semigroup, that is, a compact Hausdorff semigroup such that for fixed f ∈ βW_{k}, the map g → gf is continuous. We exploit the algebraic structure of compact left topological semigroups in the proof of Theorem 2.3. Much of the material we need may be found in [BJM] and [HS]. Be warned, however. What we call “left topological” is referred to as “right topological” in these sources. (There is no unanimous agreement in the literature on the left-right terminology. We say left topological because the semigroup operation is continuous in the left variable.)

The following lemma of R. Ellis serves as the starting point.

Lemma 2.4 ([E, Corollary 2.10]; see also [BJM, Theorem I.3.11] or [HS, Theorem 2.5].) Any compact left topological semigroup S possesses an idempotent.

Let S be a compact left topological semigroup and let J ⊂ S be non-empty. If SJ = {sj : s ∈ S, j ∈ J} ⊂ J then J is said to be a left ideal. If JS ⊂ J then J is said to be a right ideal. If J is both a left and a right ideal then we call J a two-sided ideal. Any closed (left, right or two-sided) ideal, itself being a compact semigroup, contains idempotents by Lemma 2.4. If J is a left ideal of S that is minimal among left ideals with respect to inclusion, then we call J a minimal left ideal.

The easy proof of the following lemma will be omitted.

Lemma 2.5 Let S be a compact left topological semigroup.

(a) For any x ∈ S, Sx is a closed left ideal, hence if J is minimal among closed left ideals then J is minimal among all left ideals.

(b) Suppose I ⊂ S is a two-sided ideal. Then I contains every minimal left ideal of S.

(c) There exists a closed left ideal that is minimal among closed left ideals.

Taking part (c) and part (a) together, we get that minimal left ideals exist and they are closed.

Proofs of the following proposition may be found in [BJM, Theorem I.2.12], [HS, Theorem 1.38] and [M1, Proposition 2.3.1].

Proposition 2.6 Let S be a compact left topological semigroup and let θ ∈ S be an idempotent. The following two conditions are equivalent:

(a) θ belongs to a minimal left ideal.

(b) The only idempotent ϕ ∈ S for which ϕθ = θϕ = ϕ is ϕ = θ.

An idempotent that possesses property (a), and hence property (b), of the proposition above is called a minimal idempotent. According to Lemma 2.5 (b), therefore, any two-sided ideal contains every minimal idempotent.

Lemma 2.7 (See, eg., [BJM, Corollary I.3.12] or [HS, Theorem 2.9].) Let S be a compact left topological semigroup. If R ⊂ S is a right ideal then R contains a minimal right ideal.

Theorem 2.8 Let S be a compact left topological semigroup. If θ ∈ S is a minimal idempotent and R ⊂ S is a right ideal then there exists an idempotent ϕ ∈ R with θϕ = θ.

Proof. By Lemma 2.7, R contains a minimal right ideal J. Let L be a minimal left ideal with θ ∈ L. Then LJ is a 2-sided ideal and hence contains θ by Lemma 2.5 (b). That is, there exists y ∈ J and l ∈ L such that ly = θ. Since J is a minimal right ideal, yJ = J. Hence there exists r ∈ J such that yr = y. Then θr = (ly)r = l(yr) = ly = θ. Let ϕ = rθr. Clearly ϕ ∈ R. We now have ϕ^{2} = (rθr)(rθr) = r(θr)rθr = r(θr)θr = rθ^{2}r = rθr = ϕ, so ϕ is idempotent. Finally, θϕ = θ(rθr) = (θr)(θr) = θ^{2} = θ, as required.

In our application of Theorem 2.8, we shall not utilize idempotence of ϕ.

Theorem 2.9 (See [FK, Theorem 2.1]. Also [HS, Theorem 2.23] or [M1, Theorem 2.3.2].) Let S be a compact left topological semigroup and let θ ∈ S be a minimal idempotent. If k ∈ N and G ⊂ S^{k} is a closed semigroup containing (θ, θ, ⋯, θ) then (θ, θ, ⋯, θ) is a minimal idempotent of G.

Proof. Any idempotent in S^{k} is clearly of the form (ϕ_{1}, ⋯, ϕ_{k}), where ϕ_{i} ∈ S is idempotent. Suppose (ϕ_{1}, ⋯, ϕ_{k}) ∈ G is idempotent with

(ϕ_{1}, ⋯, ϕ_{k})(θ, ⋯, θ) = (θ, ⋯, θ)(ϕ_{1}, ⋯, ϕ_{k}) = (ϕ_{1}, ⋯, ϕ_{k}).

Then ϕ_{i}θ = θϕ_{i} = ϕ_{i}, 1 ≤ i ≤ k. But θ ∈ S is minimal, so ϕ_{i} = θ, 1 ≤ i ≤ k. In other words, (ϕ_{1}, ⋯, ϕ_{k}) = (θ, ⋯, θ). Hence (θ, ⋯, θ) has property (b) of Proposition 2.6, so that (θ, ⋯, θ) is a minimal idempotent of G.

If X is a compact Hausdorff space then it is easily shown that X^{X} with the product topology forms a compact left topological semigroup under composition. If k ∈ N, (X^{X})^{k} will as well. The following easy lemma is contained in equation (2.3) of [FK]. For another proof, see [M1, Lemma 2.3.3].

Lemma 2.10 Let X be a compact space and let k ∈ N. If A, B ⊂ (X^{X})^{k} and A consists of k-tuples of continuous functions then (\overline{A})(\overline{B}) ⊂ \overline{AB}.

Let k ∈ N. We are finally prepared to introduce the version of the Stone-Čech compactification of W_{k} that we will be using. Let X = {0, 1}^{W_{k}∪{e}}, where e is the empty word. (e is an identity for W_{k}). Give X the product topology, so that in particular X is compact. Next embed W_{k} in X^{X} as follows: for w ∈ W_{k} let T_{w} ∈ X^{X} be defined by T_{w}γ(v) = γ(vw), where γ ∈ X and v ∈ W_{k}.

One may easily show that {T_{w}}_{w∈W_{k}} is a W_{k}-action by continuous self-maps of X. That is, T_{w} ∘ T_{v} = T_{wv}. We let S be the closure in X^{X} of {T_{w} : w ∈ W_{k}}. That is, S = \overline{\{T_{w}\}_{W_{k}}}; the enveloping semigroup of \{T_{w} : w ∈ W_{k}\}. According to Lemma 2.10, S is a subsemigroup of (X^{X}) and hence itself forms a compact left topological semigroup. In fact, S can be shown to be the Stone-Čech compactification of W_{k} (see [HS, Theorem 19.15]). We will not use that fact, however.

The following lemma will help facilitate the proof of Theorem 2.3 to follow. For w = (w_{1}, ⋯, w_{k}) ∈ W_{k}^{k}, let us write T_{w} = (T_{w_{1}}, ⋯, T_{w_{k}}) ∈ S^{k}.

Lemma 2.11 Let E ⊂ W_{k}^{k} and suppose (ϕ_{0}, ϕ_{1}, …, ϕ_{k−1}) ∈ \overline{\{T_{w} : w ∈ E\}} ⊂ S^{k}. For any γ_{1}, …, γ_{m} ∈ X and any a_{1}, …, a_{m} ∈ W_{k} there exists (w_{0}, w_{1}, …, w_{k−1}) ∈ E such that for all r, 1 ≤ r ≤ m, and all j ∈ {0, 1, …, k − 1}, γ_{r}(a_{r}w_{j}) = ϕ_{j}γ_{r}(a_{r}).

Proof. U = {(θ_{1}, …, θ_{k}) ∈ S^{k} : θ_{j}γ_{r}(a_{r}) = ϕ_{j}γ_{r}(a_{r}), 1 ≤ r ≤ m, j ∈ {0, 1, …, k−1}} is an open neighborhood of (ϕ_{0}, …, ϕ_{k−1}). Simply pick w = (w_{0}, …, w_{k−1}) ∈ E with T_{w} ∈ U.

We are now ready to prove Theorem 2.3. The method employed is an adaptation of that used in [FK].

Proof of Theorem 2.3 Since W_{k} = ⋃_{i=1}^{r} C_{i}, we have S = ⋃_{i=1}^{r} \overline{\{T_{w} : w ∈ C_{i}\}}. Pick a minimal idempotent θ ∈ S and choose z, with 1 ≤ z ≤ r, such that θ ∈ \overline{\{T_{w} : w ∈ C_{z}\}}. Put γ = 1_{C_{z}} ∈ X. One checks that θγ(e) = 1.

Let I′ ⊂ W_{k}^{k} be the set of all k-tuples (w(1), ⋯, w(k)), where w(x) is a variable word. Let G′ = I′ ∪ {(w, ⋯, w) : w ∈ W_{k}}, and let J′ be the set of all k-tuples (w(1), ⋯, w(k)), where w(x) is a left-sided variable word. Then G′ is a subsemigroup of W_{k}^{k} and I′, J′ are subsemigroups of G′ satisfying G′I′ ⊂ I′, I′G′ ⊂ I′ and J′G′ ⊂ J′.

Let now G = \overline{\{T_{w}\}_{G′}} ⊂ S^{k}, I = \overline{\{T_{w}\}_{I′}} ⊂ G and J = \overline{\{T_{w}\}_{J′}} ⊂ G. By Lemma 2.10, G is a compact left topological semigroup containing {(f, f, ⋯, f) : f ∈ S}, I is a two-sided ideal in G, and J is a closed right ideal in G.

By Theorem 2.9, (θ, ⋯, θ) is a minimal idempotent in G, therefore I, being a two-sided ideal in G, contains (θ, ⋯, θ). Moreover, by Theorem 2.8 there exists (ϕ_{0}, ϕ_{1}, …, ϕ_{k−1}) ∈ J such that θϕ_{i} = θ, i ∈ {0, 1, …, k − 1}.

We now use Lemma 2.11 iteratively. Choose a variable word w_{1}(x) such that

\begin{matrix}γ(w_{1}(t_{1})) = θγ(e) = 1 and \\ ϕ_{j}θγ(w_{1}(t_{1})) = θϕ_{j}θγ(e) = θγ(e) = 1, j, t_{1} ∈ \{0, 1, …, k − 1\}. \end{matrix}

Next choose a left-sided variable word u_{2}(x) such that

θγ(w_{1}(t_{1})u_{2}(t_{2})) = ϕ_{t_{2}}θγ(w_{1}(t_{1})) = 1, t_{1}, t_{2} ∈ {0, 1, …, k − 1}.

Then choose a variable word v_{2}(x) such that

\begin{matrix}γ(w_{1}(t_{1})u_{2}(t_{2})v_{2}(t_{2})) = θγ(w_{1}(t_{1})u_{2}(t_{2})) = 1 and \\ ϕ_{j}θγ(w_{1}(t_{1})u_{2}(t_{2})v_{2}(t_{2})) = θϕ_{j}θγ(w_{1}(t_{1})u_{2}(t_{2})) = θγ(w_{1}(t_{1})u_{2}(t_{2})) = 1 \end{matrix}

for all j, t_{1}, t_{2} ∈ {0, 1, …, k − 1}.

Let w_{2}(x) = u_{2}(x)v_{2}(x). Then w_{2}(x) is a left-sided variable word. Moreover,

γ(w_{1}(t_{1})w_{2}(t_{2})) = 1 and ϕ_{j}θγ(w_{1}(t_{1})w_{2}(t_{2})) = 1, j, t_{1}, t_{2} ∈ {0, 1, …, k − 1}.

Suppose that left-sided variable words w_{2}(x), w_{3}(x), …, w_{m}(x) have been chosen so that letting

\begin{matrix}T_{m} = \{w_{1}(t) & : t ∈ \{0, 1, …, k − 1\}\} ∪ \{w_{1}(t_{0})w_{s_{1}}(t_{1})w_{s_{2}}(t_{2}) ⋯ w_{s_{r}}(t_{r}) : r ∈ N, \\ 2 ≤ s_{1} < s_{2} < ⋯ < s_{r} ≤ m, t_{1}, …, t_{r} ∈ \{0, 1, …, k − 1\}\}, \end{matrix}

one has

γ(w) = ϕ_{j}θγ(w) = 1, w ∈ T_{m}, j ∈ {0, 1, …, k − 1}.

Choose a left-sided variable word u_{m+1}(x) such that for all t ∈ {0, 1, …, k − 1} and w ∈ T_{M}, θγ(wu_{m+1}(t)) = ϕ_{t}θγ(w) = 1. Next choose a variable word v_{m+1}(x) such that for all w ∈ T_{m} and t, j ∈ {0, 1, …, k − 1},

\begin{matrix}γ(wu_{m+1}(t)v_{m+1}(t)) = θγ(wu_{m+1}(t)) = 1 and \\ ϕ_{j}θγ(wu_{m+1}(t)v_{m+1}(t)) = θϕ_{j}θγ(wu_{m+1}(t)) = θγ(wu_{m+1}(t)) = 1. \end{matrix}

Let w_{m+1}(x) = u_{m+1}(x)v_{m+1}(x). Then w_{m+1}(x) is a left-sided variable word. If we now define T_{m+1} by analogy with T_{m}, one may easily see that γ(w) = ϕ_{j}θγ(w) = 1 for all w ∈ T_{m+1} and j ∈ {0, 1, …, k − 1}. Hence the induction may proceed.

At this stage we are done, because the T_{m}’s contain all the words we are looking for and they are all contained in C_{z}.

3. Four open problems.

In this section we discuss a few further extensions of the Hales-Jewett theorem and ask several related questions that we do not at the moment know the answer to. For starters, consider the following weak form of the Carlson-Simpson theorem.

Theorem 3.1 Let k, r ∈ N and suppose W_{k} = ⋃_{i=1}^{r} C_{i}. Then there exists j, with 1 ≤ j ≤ r, and a sequence of variable words (w_{i}(x))_{i=1}^{∞} such that for all N ∈ N and all i_{1}, ⋯, i_{N} ∈ {0, 1, …, k − 1}, w_{1}(i_{1})w_{2}(i_{2}) ⋯ w_{N}(i_{N}) ∈ C_{j}.

This theorem is just like Theorem 2.1 except none of the variable words are required to be left-sided. A polynomial version of Theorem 3.1 was given in [M2]. We’ll formulate it in dimension 2 for ease of notation.

Recall that for k, N ∈ N, M_{k}^{N}(2) denotes the set of N × N matrices (a_{ij})_{i,j=1}^{N}, where a_{ij} ∈ {0, 1, …, k − 1} for all pairs (i, j). Put M_{k} = ⋃_{N=1}^{∞} M_{k}^{N}(2). Suppose we are given an increasing sequence (R_{i})_{i=1}^{∞} of natural numbers (let R_{0} = 0), and a sequence of non-empty sets B_{i} ⊂ {R_{i−1}+1, R_{i−1}+2, ⋯, R_{i}}. For every (l, m) ∈ N×N, let a_{lm} be the symbol x_{ij} if (l, m) ∈ B_{i} × B_{j}. Otherwise, let a_{lm} ∈ {0, 1, …, k − 1}. Then V ((x_{ij})_{i,j=1}^{∞}) = (a_{lm})_{l,m∈N} will be called a standard N × N-variable matrix over M_{k}. For fixed m ∈ N, the matrix V_{m}((x_{ij})_{i,j=1}^{m}) = (a_{lm})_{l,m=1}^{R_{m}} is a standard m^{2}-variable matrix over M_{k}^{R_{m}}(2).

The variable matrix V_{m} induces a natural injection (t_{ij})_{i,j=1}^{m} → V_{m}((t_{ij})_{i,j=1}^{m}) from M_{k}^{m} to M_{k}^{R_{m}}. Here V_{m}((t_{ij})_{i,j=1}^{m}) is the R_{m} × R_{m} matrix which results by substituting t_{ij} for the symbol x_{ij} in the matrix V_{m}((x_{ij})_{i,j=1}^{m}) = (a_{ij})_{i,j=1}^{R_{m}} constructed above. Hence, the N × N matrix V ((x_{ij})_{i,j=1}^{∞}) = (a_{lm})_{l,m∈N}, together with the sequence (R_{m})_{m=1}^{∞}, induces such maps for all m; in other words, induces an injection of M_{k} into M_{k} (which takes m × m matrices to R_{m} × R_{m} matrices). We call the image of such a map an M_{k}-ring. Specifically, the M_{k}-ring generated by the sequence (R_{m})_{m=1}^{∞} and the variable matrix V ((x_{ij})_{i,j=1}^{∞}) = (a_{lm})_{l,m∈N}.

Theorem 3.2 ([M2]) Let k ∈ N. For any finite partition M_{k} = ⋃_{i=1}^{r} C_{i}, one of the cells C_{i} contains an M_{k}-ring.

In order to derive Theorem 3.1 from Theorem 3.2, consider the map Δ : M_{k} → W_{k} defined by Δ((a_{ij})_{i,j=1}^{N}) = a_{11}a_{22} ⋯ a_{NN}. If now W_{k} = ⋃_{i=1}^{r} C_{i} then M_{k} = ⋃_{i=1}^{r} Δ^{−1}(C_{i}) and for some z, 1 ≤ z ≤ r, Δ^{−1}(C_{z}) contains an M_{k}-system generated by a standard N × N-variable matrix V ((x_{ij})_{i,j=1}^{∞}) = (a_{lm})_{l,m∈N}. Letting B_{i} × B_{j} be the support of the variable x_{ij}, let for i ∈ N w_{i}(x) be the variable word that lies along the diagonal from (R_{i−1} + 1, R_{i−1} + 1) to (R_{i}, R_{i}), with x replacing x_{ii}. That is, w_{i}(x) = w_{1}w_{2} ⋯ w_{s}, where s = R_{i} − R_{i−1} and for 1 ≤ t ≤ s and l = R_{i−1} + t, w_{t} = a_{ll} if a_{ll} ∈ {0, 1, …, k − 1} and w_{t} = x if a_{ll} = x_{ii}. One may easily check now that for all N ∈ N and all i_{1}, i_{2}, …, i_{N} ∈ {0, 1, …, k − 1}, w_{1}(i_{1})w_{2}(i_{2}) ⋯ w_{N}(i_{N}) = Δ(V ((t_{ij})_{i,j=1}^{N})) ∈ C_{z}. Here t_{ij} ∈ {0, 1, …, k − 1} are defined by t_{jj} = i_{j} with t_{ij}, i ≠ j, arbitrary.

It is also easy to see from this derivation what changes to Theorem 3.2 are required in order to obtain the stronger Theorem 2.1 as a consequence. In order for w_{i}(x) to be a left-sided variable word, i ≥ 2, it must be the case that the point (R_{i−1} +1, R_{i−1} +1) lies in the support of x_{ii}. That is, R_{i−1} + 1 ∈ B_{i}. An M_{k}-system that meets this requirement for i ≥ 2 will be called special.

Question 3.3 Is it that case that for k ∈ N and any finite partition of M_{k}, some cell contains a special M_{k}-system?

One can easily formulate a version of Theorem 3.2 that would extend Theorem 2.2 as well. Let 0 = R_{0} < R_{1} < ⋯ < R_{N} ∈ N and let V = (a_{ij})_{i,j=1}^{R_{N}} ∈ M_{k}^{R_{N}} (2). Let ∅ ≠ α ⊂ {1, 2, …, N}. We define the α-collapse of V with respect to (R_{1}, …, R_{N}) to be the T × T matrix, where T = ∑_{i∈α}(R_{i} − R_{i−1}), that is obtained by removing the rows and columns in positions ⋃_{i∈{1,...,N}\α}{R_{i−1}+1, …, R_{i}} from V and “collapsing” together what is left.

This is probably best demonstrated by example. In this example, N = 3, R_{1} = 2, R_{2} = 4 and R_{3} = 5, while α = {1, 3}.

( \begin{matrix}0 & 1 & 2 & 3 & 1 \\ 0 & 3 & 1 & 2 & 1 \\ 1 & 2 & 1 & 1 & 0 \\ 1 & 0 & 3 & 3 & 1 \\ 2 & 2 & 2 & 0 & 3 \end{matrix} ) → ( \begin{matrix}0 & 1 & ∗ & ∗ & 1 \\ 0 & 3 & ∗ & ∗ & 1 \\ ∗ & ∗ & ∗ & ∗ & ∗ \\ ∗ & ∗ & ∗ & ∗ & ∗ \\ 2 & 2 & ∗ & ∗ & 3 \end{matrix} ) → ( \begin{matrix}0 & 1 & 1 \\ 0 & 3 & 1 \\ 2 & 2 & 3 \end{matrix} ) .

Of course, this collapsing notion may be formalized, as well. Write α = {a_{1}, … a_{s}} where a_{1} < a_{2} < ⋯ < a_{s}. Put a_{0} = 0. (b_{ij})_{i,j=1}^{T} is the α-collapse of V, where if (m, n) ∈ T × T, and i, j, b and c are chosen with 0 ≤ i, j < s, b ∈ {1, …, R_{a_{i+1}} − R_{a_{i}}}, and c ∈ {1, …, R_{a_{j+1}} − R_{a_{j}}}, such that m = ∑_{t=0}^{i}(R_{a_{t}} − R_{a_{t}−1}) + b and n = ∑_{t=0}^{j}(R_{a_{t}} − R_{a_{t}−1}) + c, then b_{mn} = a_{xy}, where x = R_{a_{i}} + b and y = R_{a_{j}} + c.

A collapsible M_{k}-system consists of an M_{k}-system N generated by an increasing sequence (R_{m})_{m=1}^{∞} ⊂ N and a standard N×N-variable matrix V ((x_{ij})_{i,j=1}^{∞}), together with all the α-collapses with respect to (R_{1}, …, R_{m}) of every R_{m} × R_{m} matrix in N, for all m ∈ N and ∅ ≠ α ⊂ {1, …, m}.

Question 3.4 Is it that case that for k ∈ N and any finite partition of M_{k}, some cell contains a collapsible M_{k}-system?

We may combine elements of Questions 3.3 and 3.4 to formulate a version of Theorem 3.2 that would extend Theorem 2.3, also. A special M_{k}-system, together with all of it’s α-collapses for which 1 ∈ α, will be called a special collapsible M_{k}- system. (One should note however that a special collapsible system need not be a collapsible system.)

Question 3.5 Is it that case that for k ∈ N and any finite partition of M_{k}, some cell contains a special collapsible M_{k}-system?

Again, we remind the reader that we have formulated Questions 3.3-5 in two dimensions for convenience only. We suspect that the obvious versions of each for arbitrary finite dimension are all true.

We wrap things up with two final questions dealing with possible infinitary extensions of Theorem 1.7.

Given k, n ∈ N and an M_{k}-ring N generated by a sequence (R_{m})_{m=1}^{∞} and a standard N × N-variable matrix V ((x_{ij})_{i,j=1}^{∞}) = (a_{lm})_{l,m∈N}, denote by N [n] the set of standard n^{2}-variable matrices that are submatrices of V_{m}((x_{ij})_{i,j=1}^{m}) for some m.

Question 3.6 Let k, r, n ∈ N. Supposing M_{k}[n] = ⋃_{i=1}^{r} C_{i}, is it the case that there must exist i, 1 ≤ i ≤ r, and an M_{k}-ring N such that N [n] ⊂ C_{i}?

The one-dimensional analogue of Question 3.6 is precisely [FK, Theorem 3.1]. It is possible to go even further. As just one example, Bergelson, A. Blass and

Hindman have proved a theorem [BBH, Theorem 7.1] which stands in relation to [FK, Theorem 3.1] precisely as Theorem 2.2 stands in relation to Theorem 3.1. A two dimensional version of their result (dealing with standard variable words over collapsible systems) would stand in a similar relation to Question 3.6. We leave formulation of this and other conjectures along these lines to the reader.

References

[BBH] V. Bergelson, A. Blass and N. Hindman, Partition theorems for spaces of variable words, Proc. London Math. Soc. (3) 68 (1994), 449-476.

[BL] V. Bergelson and A. Leibman, Set polynomials and a polynomial extension of Hales-Jewett theorem. Ann. Math. (2) 150 (1999), 33-75.

[BJM] J. Berglund, H. Junghenn and P. Milnes, Analysis on Semigroups, Wiley, N.Y., 1989.

[C] T. Carlson, Some unifying principles in Ramsey theory, Discrete Math. 68 (1988), 117-169.

[CS] T. Carlson and S. Simpson, A dual form of Ramsey’s theorem, Adv. in Math. 53 (1984) 265-290.

[E] R. Ellis, Lectures on topological dynamics, Benjamin, New York, 1969.

[FK] H. Furstenberg and Y. Katznelson, Idempotents in compact semigroups and Ramsey theory, Israel J. Math. 68 (1989), 257-270.

[GLR] R. Graham, K. Leeb, B. Rothschild, Ramsey’s theorem for a class of categories, Adv. Math. 8 (1972), 417-433.

[HJ] A.W. Hales and R.I. Jewett, Regularity and positional games, Trans. AMS 106 (1963), 222-229.

[H1] N. Hindman, Finite sums from sequences within cells of a partition of N, J. Combinatorial Theory (Series A) 17 (1974) 1-11.

[HS] N. Hindman and D. Strauss, Algebra in the Stone-Čech compactification –Theory and Applications, de Gruyter, Berlin, 1998.

[M1] R. McCutcheon, Elemental Methods in Ergodic Ramsey Theory, L. Notes in Math. 1722, Springer, Berlin, 1999.

[M2] R. McCutcheon, An infinitary version of the polynomial Hales-Jewett theorem, Israel J. Math. To appear.

[Mi] K. Milliken, Ramsey’s Theorem with sums or unions, J. Combinatorial Theory (Series A) 18 (1975) 276-290.

[T] A. Taylor, A canonical partition relation for finite subsets of ω, J. Combinatorial Theory (Series A) 21 (1976), 137-146.

Department of Mathematics University of Maryland College Park, MD 20742 U.S.A.