Neil Hindman
email: nhindman@aol.com

Dona Strauss
email: d.strauss@hull.ac.uk

HAL is

Combining extensions of the Hales-Jewett

Theorem with Ramsey Theory in other structures

Neil Hindman * Dona Strauss † Luca Q. Zamboni ‡

Abstract

The Hales-Jewett Theorem states that given any finite nonempty set A and any finite coloring of the free semigroup S over the alphabet A there is a variable word over A all of whose instances are the same color. This theorem has some extensions involving several distinct variables occurring in the variable word. We show that, when combined with a sufficiently well behaved homomorphism, the relevant variable word simultaneously satisfies a Ramsey-Theoretic conclusion in the other structure. As an example we show that if τ is the homomorphism from the set of variable words into the natural numbers which associates to each variable word w the number of occurrences of the variable in w, then given any finite coloring of S and any infinite sequence of natural numbers, there is a variable word w whose instances are monochromatic and τ (w) is a sum of distinct members of the given sequence.

Our methods rely on the algebraic structure of the Stone-Čech compactification of S and the other semigroups that we consider. We show for example that if τ is as in the paragraph above, there is a compact subsemigroup P of βN which contains all of the idempotents of βN such that, given any p ∈ P , any A ∈ p, and any finite coloring of S, there is a variable word w whose instances are monochromatic and τ (w) ∈ A.

We end with a new short algebraic proof of an infinitary extension of the Graham-Rothschild Parameter Sets Theorem.

Introduction

Given a nonempty set A (or alphabet) we let A + be the set of all finite words w = a 1 a 2 • • • a n with n ≥ 1 and a i ∈ A. The quantity n is called the length of w and denoted |w|. The set A + is naturally a semigroup under the operation of concatenation of words, known as the free semigroup over A. For each u ∈ A + and a ∈ A, we let |u| a be the number of occurrences of a in u. For u, w ∈ A + we say u and w are Abelian equivalent, and write u ∼ Ab w, whenever |u| a = |w| a for all a ∈ A. As is customary, we will identify the elements of A with the length one words over A.

Throughout this paper we will let A be a nonempty set, let S 0 = A + be the free semigroup over A, and let v (a variable) be a letter not belonging to A. By a variable word over A we mean a word w over A ∪ {v} with |w| v ≥ 1. We let S 1 be the set of variable words over A. If w ∈ S 1 and a ∈ A, then w(a) ∈ S 0 is the result of replacing each occurrence of v by a. For example if A = {a, b, c} and w = avbvva, then w(a) = aabaaa while w(c) = acbcca. A finite coloring of a set X is a function from X to a finite set. A subset A of X is monochromatic if the function is constant on A.

Theorem 1.1 (A. Hales and R. Jewett). Assume that A is finite. For each finite coloring of S 0 there exists a variable word w such that {w(a) : a ∈ A} is monochromatic.

Proof. [5, Theorem 1]. Some extensions of the Hales-Jewett Theorem, including for example Theorem 1.3 or the Graham-Rothschild Parameter Sets Theorem [START_REF] Graham | Ramsey's Theorem for n-parameter sets[END_REF], involve the notion of n-variable words. Definition 1.2. Let n ∈ N and v 1 , v 2 , . . . , v n be distinct variables which are not members of A.

(a) An n-variable word over A is a word w over A ∪ {v 1 , v 2 , . . . , v n } such that |w| vi ≥ 1 for each i ∈ {1, 2, . . . , n}.

(b) If w is an n-variable word over A and x = (x 1 , x 2 , . . . , x n ), then w( x) is the result of replacing each occurrence of v i in w by x i for each i ∈ {1, 2, . . . , n}.

(c) If w is an n-variable word over A and u = l 1 l 2 • • • l n is a length n word, then w(u) is the result of replacing each occurrence of v i in w by l i for each i ∈ {1, 2, . . . , n}.

(d) A strong n-variable word is an n-variable word such that for each i ∈ {1, 2, . . . , n -1}, the first occurrence of v i precedes the first occurrence of v i+1 .

(e) S n is the set of n-variable words over A and S n is the set of strong nvariable words over A. The notation above does not reflect the dependence on the alphabet A.

We note that if m, n ∈ ω and m < n, then for each w ∈ S n and each u ∈ S n m , the word w(u) belongs to S m .

The following is a first simple example of a multivariable extension of the Hales-Jewett Theorem: Theorem 1.3. Assume that A is finite. Let S 0 be finitely colored and let n ∈ N. There exists w ∈ S n such that {w( x) : x ∈ A n } is monochromatic.

Theorem 1.3 follows immediately from Theorem 1.1 applied to the alphabet A n , replacing each occurrence of v 1 in the variable word over

A n by v 1 v 2 • • • v n .
It is also a consequence of Theorem 2.10, which constitutes one of the main results of this paper. (See the paragraph immediately following Theorem 5.1.) Theorem 1.3 also follows directly from Theorem 1.5 later in this section which we regard as an algebraic extension of Theorem 1.3.

It is natural to ask the following question. Assume that A is finite. Let S ∞ be the set of infinite words over A∪{v i : i ∈ N} in which each v i occurs and assume that A N is finitely colored. Must there exist w ∈ S ∞ such that {w( x) : x ∈ A N } is monochromatic, where w( x) has the obvious meaning? As long as |A| ≥ 2, the answer is easily seen to be "no", using a standard diagonalization argument: One has that |A N | = |S ∞ | = c, so one may inductively color two elements of A N for each w ∈ S ∞ so that there exist x and y in A N with the color of w( x) and w( y) different. (When one gets to w, fewer than c things have been colored and there are c distinct values of w( x) possible.)

The following simplified version of the Graham-Rothschild Parameter Sets Theorem constitutes yet another fundamental multivariable extension of the Hales-Jewett Theorem. It was shown in [START_REF] Carlson | An infinitary extension of the Graham-Rothschild Parameter Sets Theorem[END_REF]Theorem 5.1] that the full version as stated in [START_REF] Graham | Ramsey's Theorem for n-parameter sets[END_REF] can be easily derived from the version stated here. After identifying the elements of A with the length 1 words over A, one sees that Theorem 1.1 is exactly the m = 0 and n = 1 case of Theorem 1.4. Notice also that Theorem 1.3 is actually equivalent to Theorem 1.4 in the special case of m = 0. In fact if w ∈ S n , σ is a permutation of {1, 2, . . . , n} and u is the result of replacing each v i in w by v σ(i) for each i ∈ {1, 2, . . . , n}, then {u( x) :

x ∈ A n } = {w( x) : x ∈ A n }.
In this paper we shall be mostly concerned with cases of Theorem 1.4 with m = 0 and arbitrary n ∈ N. (We are not concerned with m > 0 because the natural versions of our main theorems are not valid for m > 0. We shall discuss this point at the end of Section 2.) Accordingly, from this point on until Section 6 we will not be concerned with the order of occurrence of the variables.

In contrast to Theorem 1.3, the Graham-Rothschild Parameter Sets Theorem does not appear to be deducible directly from the Hales-Jewett Theorem; at least we know of no such proof. In Section 6 we present a new purely algebraic proof of an infinitary extension of Theorem 1.4.

Our main results in this paper deal with obtaining n-variable words satisfying the Hales-Jewett Theorem and simultaneously relating to Ramsey-Theoretic results in some relevant semigroup. The paper is organized as follows:

In Section 2 we present our main theorems relating S n with other structures. In Section 3 we determine precisely which homomorphisms from S n to (N, +) satisfy the hypotheses of our main theorem of Section 2, namely Theorem 2.10.

As consequences of the results of Section 2 we establish that for k ∈ N, the set of points (p 1 , p 2 , . . . , p k ) ∈ (βN) k with the property that whenever B i ∈ p i for i ∈ {1, 2, . . . , k}, the k-tuple (B 1 , B 2 , . . . , B k ) satisfies the conclusions of one of those theorems, is a compact subsemigroup of (βN) k containing the idempotents of (βN) k (or the minimal idempotents, depending on the theorem). The details of these results will be presented in Section 4.

In Section 5 we restrict our attention to versions of the Hales-Jewett Theorem. Letting

R n = {p ∈ βS 0 : (∀B ∈ p)(∃w ∈ S n )({w( x) : x ∈ A n } ⊆ B)}. We show that each R n is a compact ideal of βS 0 , that R n+1 R n for each n ∈ N, and that c K(βS 0 ) ∞ n=1 R n .
In Section 6 we present a new fully algebraic proof of an infinitary extension of the Graham-Rothschild Parameter Sets Theorem. This new proof is a significant simplification of the original.

The statements and proofs of the results in this paper use strongly the algebraic structure of the Stone-Čech compactification of a discrete semigroup. We now present a brief description of this structure. For more details or for any unfamiliar facts encountered in this paper, we refer the reader to [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Part I]. All topological spaces considered herein are assumed to be Hausdorff.

Let S be a semigroup. For each s ∈ S, ρ s : S → S and λ s : S → S are defined by ρ s (x) = xs and λ s (x) = sx. If S is also a topological space, S is said to be right topological if the map ρ s is continuous for every s ∈ S. In this case, the set of elements s ∈ S for which λ s is continuous, is called the topological center of S.

The assumption that S is compact and right topological has powerful algebraic implications. S has a smallest two sided ideal K(S) which is the union of all of the minimal right ideals, as well as the union of all of the minimal left ideals. The intersection of any minimal left ideal and any minimal right ideal is a group. In particular, S has idempotents. Any left ideal of S contains a minimal left ideal of S, and any right ideal of S contains a minimal right ideal of S. So the intersection of any left ideal of S and any right ideal of S contains an idempotent. An idempotent in S is said to be minimal if it is in K(S). This is equivalent to being minimal in the ordering of idempotents defined by p ≤ q if pq = qp = p. If q is any idempotent in S, there is a minimal idempotent p ∈ S for which p ≤ q.

Given a discrete semigroup (T, •), let βT = {p : p is an ultrafilter on T }. We identify the principal ultrafilter e(x) = {A ⊆ T : x ∈ A} with the point x ∈ T and thereby pretend that T ⊆ βT . A base for the topology of βT consists of the clopen sets A for all A ⊆ T , where A = {p ∈ βT : A ∈ p}. The operation • on T extends to an operation on βT , also denoted by • making (βT, •) a right topological semigroup with T contained in its topological center. So, given p, q ∈ βT , p • q = lim s→p lim t→q s • t, where s and t denote elements of T . If A ⊆ T ,

A ∈ p•q if and only if {x ∈ T : x -1 A ∈ q} ∈ p, where x -1 A = {y ∈ T : x•y ∈ A}. If (T, +
) is a commutative discrete semigroup, we will use + for the semigroup operation on βT , even though βT is likely to be far from commutative. In this case, we have that A ∈ p + q if and only if {x ∈ T : -x + A ∈ q} ∈ p, where -x + A = {y ∈ T : x + y ∈ A}.

A set D ⊆ T is piecewise syndetic if and only if D ∈ p for some p ∈ K(βT ) and is central if and only D ∈ p for some idempotent p ∈ K(βT ). We will also need the following equivalent characterization of piecewise syndetic sets: D is piecewise syndetic if and only if there exists a finite subset G of T with the property that for every finite subset F of T there exists x ∈ T such that F x ⊆ t∈G t -1 D. (See [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Theorem 4.40].) Given a sequence x n ∞ n=1 and m ∈ N, we set F P ( x n ∞ n=m ) = { t∈F x t : F ∈ P f (N) and min F ≥ m}, where P f (N) is the set of finite nonempty subsets of N and the products are computed in increasing order of indices. Then If γ is a function from the discrete semigroup T to a compact space C, then γ has a continuous extension from βT to C, which we will also denote by γ. If γ : T → W , where W is discrete, we will view the continuous extension as taking βT to βW , unless we state otherwise. If γ : T → C is a homomorphism from T into a compact right topological semigroup C, with γ[T ] contained in the topological center of C, then the continuous extension γ : βT → C is a homomorphism by [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Corollary 4.22].

We end this section with a few simple illustrations of how the algebraic structure described above may be applied to derive simple algebraic proofs of some of the results discussed earlier including for instance the Hales-Jewett Theorem. We begin with the following theorem whose proof is based on an argument due to Andreas Blass which first appeared in [START_REF] Bergelson | Partition theorems for spaces of variable words[END_REF].

Theorem 1.5. Let T be a semigroup and let S be a subsemigroup of T . Let F be a nonempty set of homomorphisms mapping T to S which are equal to the identity on S.

(1) Let p be a minimal idempotent in βS. Let q be an idempotent in βT for which q ≤ p. Then ν(q) = p for every ν ∈ F .

(2) For any finite subset F 0 of F and any central subset D of S, there is a central subset Q of T such that, for every t ∈ Q, {ν(t) : ν ∈ F 0 } ⊆ D.

(3) For any finite subset F 0 of F and any finite coloring of S, there is a central subset Q of T such that, for every t ∈ Q, {ν(t) : ν ∈ F 0 } is monochromatic.

Proof.

(1) For each ν ∈ F , ν(q) ≤ ν(p) = p and so, since ν(q) ∈ βS, ν(q) = p.

(2) Pick a minimal idempotent p ∈ βS such that D ∈ p. By [6, Theorem 1.60], pick a minimal idempotent q ∈ βT such that q ≤ p. Then ν(q) = p for every ν ∈ F 0 . Hence, if Q = ν∈F0 ν -1 [D], then Q ∈ q.

(3) Pick a minimal idempotent p ∈ βS and let D be a monochromatic member of p.

We note that the above theorem provides an algebraic proof of Theorem 1.3 and hence of the Hales-Jewett Theorem. In fact, put S = S 0 , T = S 0 ∪ S n and

F = {h x : x ∈ A n }, where h x (w) = w( x) if w ∈ S n w if w ∈ S 0 .
Then by Theorem 1.5

we deduce that for any finite coloring of S 0 there exists a central subset

Q of T such that for every w ∈ Q, {w( x) : x ∈ A n } is monochromatic. Pick q ∈ K(βT ) with Q ∈ q.
Then since S n is an ideal of T it follows that S n ∈ q. So for any

w ∈ S n ∩ Q we have {w( x) : x ∈ A n } is monochromatic.
We conclude this section with two additional simple corollaries of Theorem 1.5 that will not be needed in the rest of the paper.

Corollary 1.6. Let T be a semigroup and let S be a subsemigroup of T . Let F be a finite nonempty set of homomorphisms mapping T to S which are equal to the identity on S. Let D be a piecewise syndetic subset of S. Then ν∈F ν -1 [D] is a piecewise syndetic subset of T .

Proof. By [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Theorem 4.43], we may pick s ∈ S for which s -1 D is a central subset of S. We can choose a minimal idempotent p in βS for which s -1 D ∈ p, and we can then choose a minimal idempotent q in βT for which q ≤ p, by [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Theorem 1.60]. By Theorem 1.5(1), ν(q) = p for every ν ∈ F . Hence, if

Q = ν∈F ν -1 [s -1 D], then Q ∈ q. Now
sQ is a piecewise syndetic subset of T , because sQ ∈ sq and sq ∈ K(βT ). We claim that sQ

⊆ ν∈F ν -1 [D]. In fact, let x ∈ sQ, pick t ∈ Q such that x = st, and let ν ∈ F . Then ν(x) = ν(st) = sν(t) ∈ s(s -1 D) ⊆ D.
In the following corollary, we use the abbreviated notation P for P (p) for P belonging to an idempotent p.

Corollary 1.7. Let T be a semigroup and let S be a subsemigroup of T . Let F be a finite nonempty set of homomorphisms from T onto S which are equal to the identity on S. Let p be a minimal idempotent in βS and let P ∈ p. Let q be a minimal idempotent of βT for which q ≤ p and let

Q = ν∈F ν -1 [P ]. Then Q ∈ q.
There is an infinite sequence w n ∞ n=1 of elements of Q such that for each H ∈ P f (N) and each ϕ : H → F , t∈H ϕ(t)(w t ) ∈ P , where the product is computed in increasing order of indices.

Proof. Choose w 1 ∈ Q. Let m ∈ N and assume we have chosen w t m t=1 in Q such that whenever ∅ = H ⊆ {1, 2, . . . , m} and ϕ : H → F , t∈H ϕ(t)(w t ) ∈ P . Note that this hypothesis is satisfied for m = 1. Let E = { t∈H ϕ(t)(w t ) : ∅ = H ⊆ {1, 2, . . . , m} and ϕ : H → F } .

Then E ⊆ P . Let R = P ∩ y∈E y -1 P . Then R ∈ p so ν∈F ν -1 [R] ∈ q. Pick w m+1 ∈ ν∈F ν -1 [R] and note that w m+1 ∈ Q.

To verify the hypothesis let ∅ = H ⊆ {1, 2, . . . , m + 1} and let ϕ :

H → F . If m + 1 /
∈ H, the conclusion holds by assumption, so assume that m + 1 ∈ H. If H = {m + 1}, then w m+1 ∈ ϕ(m + 1) -1 [P ], so assume that {m + 1} H and let G = H \ {m + 1}. Let y = t∈G ϕ(t)(w t ). Then w m+1 ∈ ϕ(m + 1) -1 [y -1 P ] so t∈H ϕ(t)(w t ) = yϕ(m + 1)(w m+1 ) ∈ P .

Combining structures

Throughout this section, and up until Section 6, A is a fixed non-empty finite alphabet. Most of the results in this paper involve families of well behaved homomorphisms between certain semigroups: Definition 2.1. Let n ∈ N and let ν : S n → S 0 be a homomorphism. We shall say that ν is S 0 -preserving if ν(uw) = uν(w) and ν(wu) = ν(w)u for every u ∈ S 0 and every w ∈ S n .

Note that if x ∈ A n , then the function h x : S n → S 0 defined by h x (w) = w( x) is an S 0 -preserving homomorphism. Also, the function δ : S n → S 0 which simply deletes all occurrences of variables is an S 0 -preserving homomorphism. As another example, assume that n ≥ 2 and define µ : S n → S n where µ(w) is obtained from w by replacing each occurrence of v 2 by v 1 v 2 . Given x ∈ A n , h x •µ is an S 0 -preserving homomorphism which cannot be obtained by composing those of the kind mentioned previously; in fact |h x •µ(w)| > |w| for each w ∈ S n . Definition 2.2. Let S, T , and R be semigroups such that S ∪ T is a semigroup and T is an ideal of S ∪ T . Then a homomorphism τ : T → R is said to be S-independent if, for every w ∈ T and every u ∈ S, τ (uw) = τ (w) = τ (wu).

In most cases, the above definition will be applied to the case S = S 0 and T = S n for some n ∈ N. We shall see later in Lemma 3.3 that if n ∈ N, R is a cancellative commutative semigroup, and τ : S n → R is an S 0 -independent homomorphism, then τ (w) = τ (w ) whenever |w| vi = |w | vi for each i ∈ {1, 2, . . . , n}.

For reasons which will be made clear in Section 3, we will primarily be concerned with S 0 -independent homomorphisms from S n to (N, +) of the form τ (w) = |w| vi for some i ∈ {1, 2, . . . , n}.

Lemma 2.3. Let S and T be semigroups such that S ∪ T is a semigroup and T is an ideal of S ∪ T . Let φ : T → C be an S-independent homomorphism from T into the topological center of a compact right topological semigroup C. Then φ extends to a continuous homomorphism from βT into C, which we shall also denote by φ. For every q ∈ βT and every p ∈ βS, φ(q) = φ(pq) = φ(qp).

Proof. The fact that φ extends to a continuous homomorphism is [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Corollary 4.22]. Let p ∈ βS and q ∈ βT be given. In the following expressions let s and t denote members of S and T respectively. Since φ is continuous on βT and since both pq and qp are in βT by [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Corollary 4.18], we have that

φ(pq) = φ(lim s→p lim t→q st) = lim s→p lim t→q φ(st) = lim t→q φ(t) = φ(q)
and similarly

φ(qp) = φ(lim t→q lim s→p ts) = lim t→q lim s→p φ(ts) = lim t→q φ(t) = φ(q).
Theorem 2.4. Let S and T be semigroups such that S ∪ T is a semigroup and T is an ideal of S ∪ T . Let φ : T → C be an S-independent homomorphism from T into a compact right topological semigroup C with φ[T ] contained in the topological center of C and denote also by φ its continuous extension to βT . Let F be a finite nonempty set of homomorphisms from S ∪ T into S which are each equal to the identity on S, and let D be a piecewise syndetic subset of S. Let p be an idempotent in φ[βT ], and let U be a neighborhood of p in C. There exists w ∈ T such that φ(w) ∈ U and ν(w) ∈ D for every ν ∈ F .

Proof. Since D is piecewise syndetic in S, pick by [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Theorem 4.43] some s ∈ S such that s -1 D is central in S and pick a minimal idempotent r ∈ βS such that s -1 D ∈ r.

Let V = φ -1 [{p}]. Since φ is a continuous homomorphism from βT to C, V is a compact subsemigroup of βT . By Lemma 2.3, V r is a left ideal of V and
rV is a right ideal of V . Pick an idempotent q ∈ V r ∩ rV and note that q ≤ r in βT . By Theorem 1.5(1), ν(q) = r for every ν ∈ F .

Since s -1 D ∈ r we have that for each ν ∈ F , ν -1 [s -1 D] ∈ q. Since U is a neighborhood of p, pick R ∈ q such that φ[ R ] ⊆ U . Pick w ∈ R ∩ ν∈F ν -1 [s -1 D]. Then φ(sw) = φ(w) ∈ U and for ν ∈ F , ν(w) ∈ s -1 D so ν(sw) = sν(w) ∈ D.
We obtain the first result that was stated in the abstract as a corollary to Theorem 2.4.

to βN. Given a ∈ A, define f a : S 0 ∪ S 1 → S 0 by f a (w) = w(a) if w ∈ S 1 w if s ∈ S 0 ,
and let F = {f a : a ∈ A}. Then F is a finite nonempty set of homomorphisms from S 0 ∪ S 1 into S 0 which are each equal to the identity on S 0 . Pick by [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Lemma 5.11] an idempotent p ∈ βN such that F S( x n ∞ n=1 ) ∈ p. Pick any q ∈ K(βS 0 ) and pick D ∈ q which is monochromatic. Note that τ [S 1 ] = N so by [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Exercise 3.4

.1], τ [βS 1 ] = βN. Therefore, p ∈ τ [βS 1 ]. Consequently, Theorem 2.4 applies with U = F S( x n ∞ n=1 ).
Corollary 2.6. Let n ∈ N. Let φ : S n → C be an S 0 -independent homomorphism from S n into a compact right topological semigroup C with φ[S n ] contained in the topological center of C and denote also by φ the continuous extension to βS n . Let F be a finite nonempty set of S 0 -preserving homomorphisms from S n into S 0 , let D be a piecewise syndetic subset of S 0 , let p be an idempotent in φ[βS n ], and let U be a neighborhood of p in C. There exists w ∈ S n such that φ(w) ∈ U and ν(w) ∈ D for every ν ∈ F .

Proof. Let S = S 0 , let T = S n , and for ν ∈ F , extend ν to S 0 ∪ S n by defining ν to be the identity on S 0 . Then Theorem 2.4 applies.

Lemma 2.7. Let (T, •) be a discrete semigroup and let m, n ∈ N. Let φ :

S n → × m i=1 T be an S 0 -independent homomorphism. Then φ extends to a continuous S 0 -independent homomorphism φ :

βS n → × m i=1 βT . Moreover if p = (p 1 , p 2 , . . . , p m ) is an idempotent in × m
i=1 βT with the property that whenever B i ∈ p i for each i ∈ {1, 2, . . . , m}, there exists w ∈ S n such that

φ(w) ∈ × m i=1 B i , then p ∈ φ[βS n ]. Proof. Let C = × m i=1 βT . Regarding φ as an S 0 -independent homomorphism from S n into the right topological semigroup C, we see that φ[S n ] is contained in × m i=1 T which in turn is contained in the topological center of C by [6, Theorem 2.22].
Hence by [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Corollary 4.22], φ extends to a continuous homomorphism from βS n into C. To see that the extension is S 0 -independent, let u ∈ S 0 and let p ∈ βS n . Then, letting s denote a member of S n , we have

φ(up) = φ(lim s→p us) = lim s→p φ(us) = lim s→p φ(s) = φ(lim s→p s) = φ(p)
and similarly, φ(pu) = φ(p). Now assume that p = (p 1 , p 2 , . . . , p m ) is an idempotent in × m i=1 βT and whenever B i ∈ p i for each i ∈ {1, 2, . . . , m}, there exists w ∈ S n such that

φ(w) ∈ × m i=1 B i , To see that p ∈ φ[βS n ] let (B 1 , B 2 , . . . , B m ) ∈ × m i=1 p i , and let G (B1,...,Bm) = {w ∈ S n : φ(w) ∈ × m i=1 B i } .
Then by assumption,

G = {G (B1,...,Bm) : (B 1 , B 2 , . . . , B m ) ∈ × m i=1 p i } has the finite intersection property so one may pick q ∈ βS n such that G ⊆ q. Then p = φ(q) ∈ φ[βS n ].
Theorem 2.8. Let (T, •) be a discrete semigroup and let m, n ∈ N. Let p = (p 1 , p 2 , . . . , p m ) be an idempotent in × m i=1 βT . For i ∈ {1, 2, . . . , m} let τ i be an S 0 -independent homomorphism from S n to T . Assume that whenever B i ∈ p i for each i ∈ {1, 2, . . . , m}, there exists w ∈ S n such that τ 1 (w), τ 2 (w), . . . , τ m (w) ∈ × m i=1 B i . Let D be a piecewise syndetic subset of S 0 and let F be a finite nonempty set of S 0 -preserving homomorphisms from S n to S 0 . Then whenever B i ∈ p i for each i ∈ {1, 2, . . . , m}, there exists w ∈ S n such that ν(w) ∈ D for each ν ∈ F and for each i ∈ {1, 2, . . . , m}, τ i (w)

∈ B i . Proof. Define φ : S n → × m i=1 T by φ(w) = τ 1 (w), τ 2 (w), . . . , τ m (w) .
Then φ is an S 0 -independent homomorphism and hence by Lemma 2.7, φ extends to a continuous S 0 -independent homomorphism φ : βS n → × m i=1 βT and p ∈ φ[βS n ]. The result now follows from Corollary 2.6.

Corollary 2.9. Let k, n ∈ N with k < n and let T be the set of words over {v 1 , v 2 , . . . , v k } in which v i occurs for each i ∈ {1, 2, . . . , k}. Given w ∈ S n let τ (w) be obtained from w by deleting all occurrences of elements of A as well as all occurrences of v i for k < i ≤ n deleted. Let y t ∞ t=1 be a sequence in T , let F be a finite nonempty set of S 0 -preserving homomorphisms from S n to S 0 , and let D be a piecewise syndetic subset of S 0 . There exists w ∈ S n such that ν(w) ∈ D for all ν ∈ F and τ (w) ∈ F P ( y t ∞ t=1 ).

Proof. As noted in the introduction, we can pick an idempotent p ∈ βT such that F P ( y t ∞ t=1 ) ∈ p. Since τ is an S 0 -independent homomorphism from S n onto T , Theorem 2.8 applies with m = 1. Theorem 2.10 involves a matrix with entries from Q or Z. In order to ensure that matrix multiplication is distributive, we assume that T is commutative and write the operation as +.

Theorem 2.10. Let (T, +) be a commutative semigroup, let k, m, n ∈ N, and let M be a k × m matrix. If T is not cancellative assume that the entries of M come from ω. If T is isomorphic to a subsemigroup of a direct sum of copies of (Q, +) (so that multiplication by members of Q makes sense), assume that the entries of M come from Q. Otherwise assume that the entries of M come from Z. For i ∈ {1, 2, . . . , m} let τ i be an S 0 -independent homomorphism from S n to

T . Define a function ψ on S n by ψ(w) =      τ 1 (w) τ 2 (w) . . . τ m (w)      . Let p = (p 1 , p 2 , . . . , p k )
be an idempotent in × k i=1 βT with the property that whenever

B i ∈ p i for each i ∈ {1, 2, . . . , k}, there exists z ∈ ψ[S n ] such that M z ∈ × k i=1 B i .
Let F be a finite nonempty set of S 0 -preserving homomorphisms from S n to S 0 and let D be a piecewise syndetic subset of S 0 . Then whenever B i ∈ p i for each i ∈ {1, 2, . . . , k}, there exists w ∈ S n such that ν(w) ∈ D for every ν ∈ F and The following corollary provides sufficient conditions for applying Theorem 2.10. Corollary 2.12. Let m, n ∈ N with m ≤ n. Let M be an m×m lower triangular matrix with rational entries. Assume that the entries on the diagonal are positive and the entries below the diagonal are negative or zero. Let p = (p 1 , p 2 , . . . , p m ) be an idempotent in × m i=1 βN. For i ∈ {1, 2, . . . , m} let τ i = n j=1 α i,j µ j where each α i,j ∈ Q. Assume that for each i ∈ {1, 2, . . . , m} we can choose t(i) ∈ {1, 2, . . . , n} such that α i,t(i) > 0, if l ∈ {1, 2, . . . , m} and l > i, then α i,t(l) = 0, and if l ∈ {1, 2, . . . , m} and l < i, then α i,t(l) ≤ 0. Then each τ i is an S 0independent homomorphism from S n to Q. Let F be a nonempty finite set of S 0 -preserving homomorphisms from S n to S 0 and let D be a piecewise syndetic subset of S 0 . Whenever B i ∈ p i for each i ∈ {1, 2, . . . , m}, there exists w ∈ S n such that ν(w) ∈ D for each ν ∈ F and

M ψ(w) ∈ × k i=1 B i . Proof. If T is not cancellative, let G = T . If T is isomorphic to a subsemigroup of i∈I Q for some set I, assume that T ⊆ i∈I Q and let G = i∈I Q. Otherwise let G be
M      τ 1 (w) τ 2 (w) . . . τ m (w)      ∈ × m i=1 B i . Proof. Define ψ : S n → Q m by ψ(w) =    τ 1 (w) . . . τ m (w)   .
We wish to apply Theorem 2.10 with T = Q. For this we need to show that whenever

B i ∈ p i for i ∈ {1, 2, . . . , m}, there exists z ∈ ψ[S n ] such that M z ∈ × m i=1 B i . So let B i ∈ p i for i ∈ {1, 2, . . . , m}.
We show first that for each r ∈ N, there exists z ∈ (rN) m such that M z ∈ × m i=1 B i , so let r ∈ N be given. Note that M -1 is lower triangular with positive diagonal entries and nonnegative entries below the diagonal. (Probably the easiest way to see this is to solve the system of equations M z = x by back substitution. Alternatively we may write M = D(I + N ) where D is diagonal with positive entries and N is a strictly lower triangular matrix (all of whose non-zero entries are negative) verifying

N m = O. Setting x = -N in 1 -x m = (1 -x)(1 + x + x 2 + • • • x m-1 ) gives (I + N ) -1 = I + m-1
j=1 (-1) j N j . Hence (I + N ) -1 is lower triangular with 1s along the diagonal and nonnegative entries below the diagonal. Multiplying (I +N ) -1 by D -1 on the right gives the desired result.) Let c ∈ N be such that all entries of cM -1 are nonnegative integers. By [6, Lemma 6.6] rcN ∈ p i for each i ∈ {1, 2, . . . , m} so pick x i ∈ B i ∩ rcN.

Letting z = M -1 x one has that z ∈ (rN) m and M z ∈ × m i=1 B i . Now assume we have chosen t(i) for i ∈ {1, 2, . . . , m} as in the statement of the corollary. Pick d ∈ N such that dα i,j ∈ Z for each i ∈ {1, 2, . . . , m} and each j ∈ {1, 2, . . . , n} and let δ i,j = dα i,j . Let

J = {1, 2, . . . , n} \ {t(1), t(2), . . . , t(m)} . Let s = m i=1 δ i,t(i) and pick r ∈ N such that s divides r and r > max s j∈J |δ i,j | : i ∈ {1, 2, . . . , m} . Pick z ∈ (rN) m such that M z ∈ × m i=1 B i .
We shall produce w ∈ S n such that ψ(w) = z by determining µ j (w) for each j ∈ {1, 2, . . . , n}. (To be definite, we then let w

= n j=1 v µj (w) j .) For j ∈ J, let µ j (w) = s. Let µ t(1) (w) = d z 1 δ 1,t(1)
-j∈J δ 1,j s δ 1,t [START_REF] Bergelson | Partition theorems for spaces of variable words[END_REF] and note that m l=2 δ l,t(l) divides µ t(1) (w) and by the choice of r, µ t(1) (w) > 0, as is, of course, required. Now let k ∈ {2, 3, . . . , m} and assume that for each i ∈ {1, 2, . . . , k -1}, we have chosen µ t(i) (w) ∈ N such that m l=i+1 δ l,t(l) divides µ t(i) (w). Then let

µ t(k) (w) = d z k δ k,t(k) - k-1 i=1 δ k,t(i) δ k,t(k) µ t(i) (w) -j∈J s δ k,j δ k,t(k)
.

Then µ t(k) (w) ≥ 1 δ k,t(k) (dz k -j∈J sδ k,j ) > 0 and, if k < m, then m l=k+1 δ l,t(l) divides µ t(k) (w).
It is now a routine matter to verify that for k ∈ {1, 2, . . . , m}, τ

k (w) = k i=1 α k,t(i) µ t(i) (w) + j∈J α k,j µ j (w) = z k .
The sufficient conditions in Corollary 2.12 on the coefficients α i,j of the homomorphisms τ i apply to all lower triangular matrices with positive diagonal entries and entries below the diagonal less than or equal to zero. A complete solution to the problem of which matrices and which S 0 -independent homomorphisms satisfy the hypotheses of Theorem 2.10 seems quite difficult. The following simple example illustrates that one cannot get necessary and sufficient conditions on the coefficients of the homomorphisms τ i valid for all lower triangular matrices with positive diagonal entries and entries below the diagonal less than or equal to zero.

Theorem 2.13. Let M = 1 0 -1 1 , let N = 1 0 0 1 , let τ 1 = 2µ 1 + µ 2
and let τ 2 = µ 1 + 2µ 2 .

(1) If p 1 and p 2 are any idempotents in βN, B 1 ∈ p 1 , and B 2 ∈ p 2 , F is a finite set of S 0 -preserving homomorphisms from S 2 to S 0 , and D is a piecewise syndetic subset of S 0 , then there exists w ∈ S 2 such that

M τ 1 (w) τ 2 (w) ∈ × 2 i=1 B i and ν(w) ∈ D for each ν ∈ F . ( 2
)
z 2 ∈ B 2 ∩ 3N and pick z 1 > z 2 in B 1 ∩ 3N. Let k 1 = 1 3 z 1 -1 3 z 2 and let k 2 = 13 1 3 z 1 -1 3 z 2 . Let w = v k1 1 v k2 2 so that µ 1 (w) = 1 3 z 1 -1 3 z 2 and µ 2 (w) = 1 3 z 1 + 2 3 z 2 . Then τ 1 (w) = z 1 , τ 2 (w) = z 1 + z 2 , and M τ 1 (w) τ 2 (w) = z 1 z 2 .
(

) Let B 1 = F S( 2 4n ∞ n=1 ) and let B 2 = F S( 2 4n+2 ∞ n=1 ) 2
. By [6, Lemma 5.11] pick idempotents p 1 and p 2 in βN such that B 1 ∈ p 1 and B 2 ∈ p 2 . Suppose we have some w ∈ S 2 and elements z 1 ∈ B 1 and

z 2 ∈ B 2 such that N τ 1 (w) τ 2 (w) = z 1 z 2 . Then 2z 1 -z 2 = 3µ 1 (w) > 0 and 2z 2 -z 1 = 3µ 2 (w) > 0 so z 2 < 2z 1 and z 1 < 2z 2 . Pick F, G ∈ P f (N) such that z 1 = t∈F 2 4t and z 2 = t∈G 2 4t+2 . Let m = max F and let k = max G. Then 2 4m ≤ z 1 < 2 4m+1 and 2 4k+2 ≤ z 2 < 2 4k+3 . Then 2 4m+2 > 2z 1 > z 2 ≥ 2 4k+2 so m ≥ k + 1. Also 2 4k+4 > 2z 2 > z 1 ≥ 2 4m ≥ 2 4k+4 , a contradiction.
A k × m matrix M is image partition regular over N if and only if, whenever N is finitely colored, there is some z ∈ N m such that the entries of M z are monochromatic. This class includes all triangular (upper or lower) matrices with rational entries and positive diagonal entries. See [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Theorem 15.24] for half an alphabet of characterizations of matrices that are image partition regular over N.

Corollary 2.14. Let k, m, n ∈ N with m ≤ n. Let M be a k × m matrix with rational entries which is image partition regular over N. Let p be a minimal idempotent in βN and let p = (p, p, . . . , p) ∈ × k i=1 βN. Let σ be an injection from {1, 2, . . . , m} to {1, 2, . . . , n}. For i ∈ {1, 2, . . . , m} let τ i = µ σ(i) . Let F be a nonempty finite set of S 0 -preserving homomorphisms from S n to S 0 and let D be a piecewise syndetic subset of S 0 . Then whenever B ∈ p there exists w ∈ S n such that ν(w) ∈ D for each ν ∈ F and

M      τ 1 (w) τ 2 (w) . . . τ m (w)      ∈ × k i=1 B .
Proof. We note that the mapping w → τ 1 (w), τ 2 (w), . . . , τ m (w) defines an S 0 -independent homomorphism from S n onto N m . So in order to apply Theorem 2.10, we must verify that whenever B i ∈ p for each i ∈ {1, 2, . . . , k},

there exists z ∈ N m such that M z ∈ × k i=1 B i .
We then pick w ∈ S n such that τ i (w) = z i for each i ∈ {1, 2, . . . , m}, which one may do because σ is injective.

Now k i=1 B i ∈ p so B = k i=1 B i is central in N. By [6, Theorem 15.24(h)] there exists z ∈ N m such that M z ∈ B k .
Corollary 2.14 applies to a much larger class of matrices than Corollary 2.12, but is more restrictive in that the same minimal idempotent must occur in each coordinate. Suppose we have a k × m matrix M which is image partition regular over N. If we knew that whenever B 1 , B 2 , . . . , B k are central subsets of N, there exist z ∈ N m with M z ∈ × k i=1 B i , then in Corollary 2.14 we could allow p = (p 1 , p 2 , . . . , p k ) to be an arbitrary minimal idempotent in × k i=1 βN. We shall see now that this fails.

Theorem 2.15. Let M = 1 1 1 2
. Then M is image partition regular over

N. For x ∈ N let φ(x) = max{t ∈ ω : 2 t ≤
N such that M x y ∈ B 0 × B 2 . Let n = φ(x + y). Then 2 n ≤ x + y < 2 n+1 so y < 2 n+1 -x and thus 2y < 2 n+2 -2x so x + 2y < 2 n+2 -x < 2 n+2 and thus φ(x + 2y) ∈ {n, n + 1}.
Note also that Corollary 2.14 is more restrictive than Corollary 2.12 in that the idempotent p is required to be minimal. It is well known and easy to see that F S( 2 2t ∞ t=1 ) does not contain any three term arithmetic progression. Consequently, if

M =   1 0 1 1 1 2   ,
then the assumption in Corollary 2.14 that the idempotent p is minimal cannot be deleted.

We remarked in the introduction that we are not concerned with the instances of Theorem 1.4 with m > 0 because the natural versions of our results in this section are not valid. The results in this section apply to all piecewise syndetic subsets of S 0 . In particular, they apply to central subsets. It was shown in [START_REF] Carlson | An infinitary extension of the Graham-Rothschild Parameter Sets Theorem[END_REF]Theorem 3.6] that, given a ∈ A, there is a central set D ∈ S 1 such that there is no w ∈ S 2 with {w(av 1 ), w(v 1 a)} ⊆ D.

Homomorphisms satisfying our hypotheses

In Corollary 2.12 we produced S 0 -independent homomorphisms from S n to Q as linear combinations of the functions µ i with coeffients from Q. We shall see in Corollary 3.5 that if T is commutative and cancellative, then the only S 0independent homomorphisms ϕ : S n → T are of the form ϕ(w) = n i=1 µ i (w)•a i where each a i is in the group of differences of T .

In Corollary 2.14 we used S 0 -independent homomorphisms τ i = µ σ(i) from S n to N and the surjection w → τ 1 (w), τ 2 (w), . . . , τ m (w) from S n onto N m . We show in Corollary 3.8 that if T = N, then these are essentially the only choices for τ i satisfying the hypotheses of Theorem 2.10.

Recall that throughout this section A is a fixed nonempty finite alphabet. Definition 3.1. Let n ∈ N. For w ∈ S n , let w ∈ {v 1 , v 2 , . . . , v n } + be obtained from w by deleting all occurrences in w of letters belonging to A. Lemma 3.2. Fix n ∈ N. Let (T, +) be a cancellative semigroup and let ϕ : S n → T be an S 0 -independent homomorphism. Then ϕ(w) = ϕ(w ) for all w ∈ S n .

Proof. It suffices to show that if w 1 , w 2 ∈ S n and u ∈ S 0 , then ϕ(w

1 uw 2 ) = ϕ(w 1 w 2 ). Let v = v 1 v 2 • • • v n . On one hand ϕ(vw 1 uw 2 v) = ϕ(v) + ϕ(w 1 uw 2 ) + ϕ(v)
, and on the other hand ϕ(vw

1 uw 2 v) = ϕ(vw 1 u) + ϕ(w 2 v) = ϕ(vw 1 ) + ϕ(w 2 v) = ϕ(vw 1 w 2 v) = ϕ(v) + ϕ(w 1 w 2 ) + ϕ(v).
The result now follows. (ii) Let ε be the empty word. If x, y ∈ (A ∪ {v 1 , v 2 , . . . , v n }) + , w ∈ (A ∪ {v 1 , v 2 , . . . , v n }) + ∪ {ε} and xyw ∈ S n , then yxw ∈ S n and ϕ(yxw) = ϕ(xyw).

Then given l 1 , l 2 , . . . , l m ∈ A ∪ {v 1 , v 2 , . . . , v n } by (i) we have ϕ(l 1 l 2 • • • l m ) = ϕ(l 2 l 3 • • • l m l 1 ) and by (ii) we have ϕ(l 1 l 2 l 3 • • • l m ) = ϕ(l 2 l 1 l 3 • • • l m ).
To establish (i), we have ϕ(xw) + ϕ(xwx) = ϕ(xwxwx) = ϕ(xwx) + ϕ(wx), whence ϕ(xw) = ϕ(wx). Note that we are using here that T is commutative.

For (ii), let v = v 1 v 2 • • • v n . Then, using (i) twice, ϕ(v) + ϕ(xyw) + ϕ(v) = ϕ(vxywv) = ϕ(vx) + ϕ(ywv) = ϕ(xv) + ϕ(ywv) = ϕ(xvywv) = ϕ(xvy) + ϕ(wv) = ϕ(vyx) + ϕ(wv) = ϕ(vyxwv) = ϕ(v) + ϕ(yxw) + ϕ(v).
The result now follows.

We remark that Lemma 3.3 does not hold in general if T is not commutative. For example, consider the homomorphism ϕ : S 3 → S 2 where ϕ(w) is the word in S 2 obtained from w by deleting all occurrences of the variable v 3 in addition to all letters belonging to A. Then S 2 is cancellative and ϕ is an S 0independent homomorphism. However, ϕ(v

1 v 2 v 3 ) = v 1 v 2 = v 2 v 1 = ϕ(v 2 v 1 v 3 ) yet v 1 v 2 v 3 ∼ Ab v 2 v 1 v 3 .
Theorem 3.4. Fix n ∈ N. Let (T, +) be a cancellative and commutative semigroup and let ϕ : S n → T be an S 0 -independent homomorphism. Then there exists a homomorphism f :

N n → T such that ϕ(w) = f µ 1 (w), µ 2 (w), . . . , µ n (w) for all w ∈ S n . Proof. Define f : N n → T by f (x 1 , x 2 , . . . , x n ) = ϕ(v x1 1 v x2 2 • • • v xn n )
. By Lemma 3.3, f is as required.

Corollary 3.5. Let n ∈ N, let (T, +) be a commutative and cancellative semigroup, let G be the group of differences of T , and let ϕ be an S 0 -independent homomorphism from S n to T . There exist a 1 , a 2 , . . . , a n in G such that for each

w ∈ S n , ϕ(w) = n i=1 µ i (w) • a i .
Proof. Pick a homomorphism f : N n → T as guaranteed by Theorem 3.4. For j ∈ {1, 2, . . . , n}, define z [j] ∈ N n by, for i ∈ {1, 2, . . . , n}, z

[j] i = 2 if i = j 1 if i = j . (1)
Let 1 = (1, 1, . . . , 1) ∈ N n . Let c = f ( 1 ) and for j ∈ {1, 2, . . . , n}, let a j = f ( z [j] ) -c. Then

(n + 1) • c = f (n + 1, n + 1, . . . , n + 1) = n j=1 f ( z [j] ) = ( n j=1 a j ) + n • c so c = n j=1 a j . We claim that f (x 1 , x 2 , . . . , x n ) = n j=1 x j • a j for all (x 1 , x 2 , . . . , x n ) ∈ N n .
To see this we proceed by induction on

n j=1 x j . If n j=1 x j = n then (x 1 , x 2 , . . . , x n ) = 1 whence f (x 1 , x 2 , . . . , x n ) = c = n j=1 a j = n j=1 1 • a j . Next let N ≥ n and suppose that f (x 1 , x 2 , . . . , x n ) = n j=1 x j • a j for all (x 1 , x 2 , . . . , x n ) ∈ N n with n j=1 x j ≤ N. Let (x 1 , x 2 , . . . , x n ) ∈ N n be such that n j=1 x j = N + 1. Pick j ∈ {1, 2, . . . , n} such that x j ≥ 2. Then f (x 1 , x 2 , . . . , x n ) + f ( 1 ) = f (x 1 , . . . , x j-1 , x j -1, x j+1 , . . . , x n ) + f ( z [j] ).
Since f ( z [j] ) -f ( 1 ) = a j it follows by our induction hypothesis that

f (x 1 , x 2 , . . . , x n ) = j-1 i=1 x i • a i + (x j -1) • a j + n i=j+1 x i • a i + a j = n i=1 x i • a i .
Consequently, for all w ∈ S n , ϕ(w) = f µ 1 (w), µ 2 (w), . . . , µ n (w) = n j=1 µ j (w) • a j .

In the proof of the next lemma, we shall use the fact that if n ∈ N, f : N n → N is a homomorphism, x, y [1] , y [2] , . . . , y [n] ∈ N n , α 1 , α 2 , . . . , α n ∈ Z, and x = n i=1 α i y [i] , then

f ( x) = n i=1 α i f ( y [i] ) .
We note that if α i ≤ 0, then f is not defined at α i y [i] . So to verify the above equality, let I = {i ∈ {1, 2, . . . , n} : α i < 0} and let J = {i ∈ {1, 2, . . . , n} : α i > 0}. Then

x

+ i∈I (-α i ) y [i] = i∈J α i y [i] so f ( x) + i∈I (-α i )f ( y [i] ) = i∈J α i f ( y [i] ) so f ( x) = i∈I∪J α i f ( y [i] ) = n i=1 α i f ( y [i]
) . Lemma 3.6. Let n ∈ N and f : N n → N be a surjective homomorphism. Then there exists i ∈ {1, 2, . . . , n} such that f ( x) = x i for each x = (x 1 , x 2 , . . . , x n ) ∈ N n , i.e., f is the projection onto the i'th coordinate.

Proof. We begin by showing that f ( 1 ) = 1 where 1 = (1, 1, . . . , 1). Since f is surjective, it suffices to show that f ( x) ≥ f ( 1 ) for each x = (x 1 , x 2 , . . . , x n ) ∈ N n . For each r ∈ N we have that r x = (r -1) 1 + 1 + r(x 1 -1), 1 + r(x 2 -1), . . . , 1 + r(x n -1) . 1) or equivalently that r f ( x) -f ( 1) > -f ( 1 ). As r is arbitrary we deduce that f ( x) -f ( 1 ) ≥ 0 as claimed.

It follows that rf

( x) = f (r x) > f (r -1) 1 = (r -1)f (
For each j ∈ {1, 2, . . . , n} let z [j] = (z

[j] 1 , z [j] 2 , . . . , z [j] n ) ∈ N n be as in (1). As n j=1 z [j] = (n + 1) 1 we have n j=1 f ( z [j] ) = f (n + 1) 1) = n + 1. It follows that there exists a unique k ∈ {1, 2, . . . , n} such that f ( z [k] ) = 2 and f ( z [j] ) = 1
for all j = k. Without loss of generality, we may assume that f ( z [1] ) = 2 and f ( z [j] ) = 1 for all j ∈ {2, 3, . . . n}.

Let x = (x 1 , x 2 , . . . , x n ) ∈ N n . We will show that f ( x) = x 1 . We first note that (n + 1) x = n i=1 (nx i - n j=1 j =i x j ) z [i] . Therefore (n + 1)f ( x) = (nx 1 - n j=2 x j ) • 2 + n i=2 (nx i - n j=1 j =i x j ) • 1
and thus (n + 1)f ( x) = (n + 1)x 1 .

Corollary 3.7. Let n, m ∈ N. For i ∈ {1, 2, . . . , n} and j ∈ {1, 2, . . . , m} let π i : N n → N and π j : N m → N denote the projections onto the i'th and j'th coordinates respectively. Assume that f : N n → N m is a surjective homomorphism. For i ∈ {1, 2, . . . , m}, let f i = π i • f . Then there is an injection σ : {1, 2, . . . , m} → {1, 2, . . . , n} such that for each i ∈ {1, 2, . . . , m}, f i = π σ(i) .

In particular m ≤ n.

Proof. By hypothesis each f i : N n → N is a surjective homomorphism. Thus by Lemma 3.6, there exists a mapping σ : {1, 2, . . . , m} → {1, 2, . . . , n} such that

f i ( x) = π σ(i) ( x) = x σ(i) for each x ∈ N n . But as f is surjective, it follows that σ is injective. Corollary 3.8. Let n, m ∈ N.
For each i ∈ {1, 2, . . . , m} let τ i : S n → N be an S 0 -independent homomorphism. If the mapping w → τ 1 (w), τ 2 (w), . . . , τ m (w) takes S n onto N m , then there exists an injection σ : {1, 2, . . . , m} → {1, 2, . . . , n} such that τ i = µ σ(i) for each i ∈ {1, 2, . . . , m}. In particular we must have m ≤ n.

Proof. By Theorem 3.4, for each i ∈ {1, 2, . . . , m}, pick a homomorphism f i :

N n → N such that τ i (w) = f i µ 1 (w), µ 2 (w), . . . , µ n (w) for each w ∈ S n . Define f : N n → N m by f ( x) = f 1 ( x), f 2 ( x), . . . , f m ( x) .
We claim that f is surjective, so let y ∈ N m be given and pick w ∈ S n such that τ 1 (w), τ 2 (w), . . . , τ m (w) = y. For j ∈ {1, 2, . . . , n}, let x j = |w| vj . Then f ( x) = y.

By Corollary 3.7, pick an injection σ : {1, 2, . . . , m} → {1, 2, . . . , n} such that for each i ∈ {1, 2, . . . , m}, f i = π σ(i) . Let w ∈ S n be given and let x = (|w| v1 , |w| v2 , . . . , |w| vn ), Then for i ∈ {1, 2, . . . , m}, τ i (w

) = f i ( x) = x σ(i) = |w| v σ(i) .
4 Compact subsemigroups of (βN) k Then P is a compact subsemigroup of C containing all the idempotents of φ[βS n ].

Proof. It is clear that P is compact. By Corollary 2.6, P contains all the idempotents in φ[βS n ]. To see that P is a subsemigroup of C, let p, q ∈ P . Let U be an open neighborhood of pq and let D be a piecewise syndetic subset of S 0 . By [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Theorem 4.43] pick s ∈ S 0 such that s -1 D is central and pick a minimal idempotent r in βS 0 such that s

-1 D ∈ r. Pick a neighborhood V of p such that ρ q [V ] ⊆ U . Since (s -1 D) ∈ r, it is piecewise syndetic so pick w ∈ S n such that φ(w) ∈ V and ν(w) ∈ (s -1 D) for each ν ∈ F .
Then φ(w)q ∈ U and φ(w) is in the topological center of C so pick a neighborhood

Q of q such that λ φ(w) [Q] ⊆ U . For each ν ∈ F , ν(w) -1 (s -1 D) ∈ r. Let E = ν∈F ν(w) -1 (s -1 D) . Then E ∈ r so E is piecewise syndetic in S 0 . Pick u ∈ S n such that φ(u) ∈ Q and ν(u) ∈ E for each ν ∈ F . Then φ(swu) = φ(w)φ(u) ∈ U and for each ν ∈ F , ν(swu) = sν(w)ν(u) ∈ D.
In the next results we focus on (βN) k and S 0 -independent homomorphisms from S n onto N m , so by Corollary 3.8 we may assume that we have m ≤ n and are dealing with S 0 -independent homomorphisms τ i from S n to N defined by τ i (w) = |w| v σ(i) for some injection σ : {1, 2, . . . , m} → {1, 2, . . . , n}. Definition 4.2. Let k, m, n ∈ N with m ≤ n, let M be a k × m matrix with entries from Q, let F be a finite nonempty set of S 0 -preserving homomorphisms from S n to S 0 , and let σ be an injection from {1, 2, . . . , m} to {1, 2, . . . , n}. P M,F, σ = { p ∈ × k i=1 βN : whenever D is a piecewise syndetic subset of S 0 and for all i ∈ {1, 2, . . . , k} , B i ∈ p i , there exists w ∈ S n such that (∀ν ∈ F )(ν(w) ∈ D) and

M    µ σ(1) (w) . . . µ σ(m) (w)    ∈ × k i=1 B i }
Recall that for x ∈ A n we have defined the S 0 -preserving homomorphism h x : S n → S 0 by h x (w) = w( x). We are particularly interested in the set {h x : x ∈ A n } because of the relationship with the Hales-Jewett Theorem. We see now that if F = {h x : x ∈ A n }, then P M,F, σ does not depend on σ. We keep σ in the notation because there are S 0 -preserving homomorphisms which are not of the form h x . Theorem 4.3. Let k, m, n ∈ N with m ≤ n, let M be a k × m matrix with entries from Q, let F = {h x : x ∈ A n }, and let σ and η be injections from {1, 2, . . . , m} to {1, 2, . . . , n}. Then P M,F, σ = P M,F, η .

Proof. It suffices to show that P M,F, σ ⊆ P M,F, η , so let p ∈ P M,F, σ . To see that p ∈ P M,F, η , let D be a piecewise syndetic subset of S 0 and for i ∈ {1, 2, . . . , k}, let B i ∈ p i . Pick w ∈ S n such that for all x ∈ A n , h x (w) ∈ D and

M    µ σ(1) (w) . . . µ σ(m) (w)    ∈ × k i=1 B i .
Define δ : {σ(1), σ(2), . . . , σ(m)} → {1, 2, . . . , n} by, for i ∈ {1, 2, . . . , m}, δ σ(i) = η(i) and extend δ to a permutation of {1, 2, . . . , n}. Define w ∈ S n by w

= w(v δ(1) v δ(2) • • • v δ(n) ). Then for j ∈ {1, 2, . . . , n}, µ j (w) = µ δ(j) (w ) so for i ∈ {1, 2, . . . , m}, µ σ(i) (w) = µ δ(σ(i)) (w ) = µ η(i) (w ) and thus M    µ η(1) (w ) . . . µ η(m) (w )    = M    µ σ(1) (w) . . . µ σ(m) (w)    ∈ × k i=1 B i .
Now let x ∈ A n be given and define z ∈ A n by, for i ∈ {1, 2, . . . , n},

z i = x δ(i) . Then h x (w ) = h z (w) ∈ D. If one lets C = (βN) k and defines φ on S n by φ(w) = M    µ σ(1) (w) . . . µ σ(m) (w)   , one
may not be able to invoke Theorem 4.1 to conclude that P M,F, σ is a semigroup because φ may not take S n to C. Consider, for example, M =

Lemma 4.4. Let k, m, n ∈ N with m ≤ n, let M be a k × m matrix with entries from Q, and let F be a finite nonempty set of S 0 -preserving homomorphisms from S n to S 0 . Let σ be an injection from {1, 2, . . . , m} to {1, 2, . . . , n}. If P M,F, σ = ∅, then P M,F, σ is a compact subsemigroup of (βN) k .

Proof. Assume that P M,F, σ = ∅. We begin by showing that P M,F, σ is compact. Let p = (p 1 , p 2 , . . . , p k ) ∈ (βN) k \ P M,F, σ and pick piecewise syndetic D ⊆ S 0 and B i ∈ p i for each i ∈ {1, 2, . . . , k} such that there is no w ∈ S n with ν(w) ∈ D for all ν ∈ F and

M    µ σ(1) (w) . . . µ σ(m) (w)    ∈ × k i=1 B i ; then × k i=1 B i is a neighborhood
of p which misses P M,F, σ so P M,F, σ is closed and hence compact.

To see that P M,F, σ is a semigroup, let p, q ∈ P M,F, σ . Let D be a piecewise syndetic subset of S 0 and for each i ∈ {1, 2, . . . , k}, let B i ∈ p i + q i . By [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Theorem 4.43], pick s ∈ S 0 such that s -1 D is central in S 0 and pick a minimal idempotent r ∈ βS 0 such that s -1 D ∈ r. For each i ∈ {1, 2, . . . , k}, let

C i = {x ∈ N : -x + B i ∈ q i }
and note that C i ∈ p i . Then as (s -1 D) ∈ r, we deduce that (s -1 D) is central and hence in particular piecewise syndetic. Since p ∈ P M,F, σ , pick w ∈ S n such that ν(w) ∈ (s -1 D) for all ν ∈ F and

M    µ σ(1) (w) . . . µ σ(m) (w)    = z ∈ × k i=1 C i . Let G = ν∈F ν(w) -1 (s -1 D) . Then G ∈ r
so G is piecewise syndetic in S 0 . Also q ∈ P M,F, σ and for each i ∈ {1, 2, . . . , k},

-z i + B i ∈ q i so pick u ∈ S n such that ν(u) ∈ G for each ν ∈ F and M    µ σ(1) (u) . . . µ σ(m) (u)    = y ∈ × k i=1 (-z i + B i ). Given ν ∈ F , ν(wu) = ν(w)ν(u) ∈ s -1 D so ν(swu) = sν(wu) ∈ D. Finally M    µ σ(1) (swu) . . . µ σ(m) (swu)    = M    µ σ(1) (wu) . . . µ σ(m) (wu)    = M    µ σ(1) (w) + µ σ(1) (u) . . . µ σ(m) (w) + µ σ(m) (u)    = z + y ∈ × k i=1 B i . Theorem 4.5. Let m, n ∈ N with m ≤ n.
Let M be an m × m lower triangular matrix with rational entries. Assume that the entries on the diagonal are positive and the entries below the diagonal are negative or zero. Let F be a finite nonempty set of S 0 -preserving homomorphisms from S n to S 0 . Let σ be an injection from {1, 2, . . . , m} to {1, 2, . . . , n}. Then P M,F, σ is a compact subsemigroup of (βN) m containing the idempotents of (βN) m .

Proof. Let k = m. By Corollary 2.12, P M,F, σ contains the idempotents of (βN) k so in particular P M,F, σ = ∅. The result now follows by Lemma 4.4.

Theorem 4.6. Let k, m, n ∈ N with m ≤ n. Let M be a k×m matrix with rational entries which is image partition regular over N. Let F be a finite nonempty set of S 0 -preserving homomorphisms from S n to S 0 . Let σ be an injection from {1, 2, . . . , m} to {1, 2, . . . , n}. Then P M,F, σ is a compact subsemigroup of (βN) k containing {(p, p, . . . , p) ∈ (βN) k : p is a minimal idempotent of βN}.

Proof. By Corollary 2.14, P M,F, σ contains {(p, p, . . . , p) ∈ (βN) k : p is a minimal idempotent of βN} so Lemma 4.4 applies.

If M = 1 1 1 2
and F is a finite nonempty set of S 0 -preserving homomorphisms from S n to S 0 , then by Theorem 4.6 we have that P M,F, σ contains {(p, p) : p is a minimal idempotent of βN} but by Theorem 2.15, P M,F, σ does not contain {(p 1 , p 2 ) : p 1 and p 2 are minimal idempotents of βN}.

Given a finite coloring of a semigroup, at least one of the color classes must be piecewise syndetic, so results concluding that piecewise syndetic sets have a certain property guarantee the corresponding conclusion for finite colorings. We see now a situation where the conclusions are equivalent -a fact that has interesting consequences for both versions. Theorem 4.7. Let n ∈ N, let τ be an S 0 -independent homomorphism from S n to N, and let B ⊆ N. The following statements are equivalent.

(a) Whenever S 0 is finitely colored, there exists w ∈ S n such that {w( x) : x ∈ A n } is monochromatic and τ (w) ∈ B.

(b) Whenever D is a piecewise syndetic subset of S 0 , there exists w ∈ S n such that {w( x) :

x ∈ A n } ⊆ D and τ (w) ∈ B.
Proof. It is trivial that (b) implies (a), so assume that (a) holds and let D be a piecewise syndetic subset of S 0 . Note that for each r ∈ N, there is some m ∈ N such that whenever the length m words in S 0 are r-colored, there is some w ∈ S n of length m such that {w( x) : x ∈ A n } is monochromatic and τ (w) ∈ B. (If there is a bad r-coloring ϕ m of the length m words for each m then ∞ m=1 ϕ m is a bad r-coloring of S 0 .) Since D is piecewise syndetic, pick finite nonempty G ⊆ S 0 such that for every finite nonempty subset H of S 0 there exists s ∈ S 0 with Hs ⊆ t∈G t -1 D. Let r = |G| and pick m ∈ N such that whenever the length m words in S 0 are r-colored, there is some w ∈ S n such that {w( x) : x ∈ A n } is monochromatic and τ (w) ∈ B. Let H be the set of length m words in S 0 and pick s ∈ S 0 such that Hs

⊆ t∈G t -1 D. For u ∈ H pick ϕ(u) ∈ G such that us ∈ ϕ(u) -1 G. Pick w ∈ S n of length m and t ∈ G such that for all x ∈ A n , ϕ w( x) = t and τ (w) ∈ B. Let w = tws. Then for x ∈ A n , w ( x) = t w( x) s ∈ D and τ (w ) = τ (w) ∈ B.
If n = 1, the following corollary yields the statement in the second paragraph of the abstract.

Corollary 4.8. Let n ∈ N, let τ be an S 0 -independent homomorphism from S n onto N, and let Q = {p ∈ βN : whenever S 0 is finitely colored and B ∈ p, there exists w ∈ S n such that {w( x) : x ∈ A n } is monochromatic and τ (w) ∈ B}. Then Q is a compact subsemigroup of βN containing all of the idempotents.

Proof. Let k = m = 1, let M = (1), and let F = {h x : x ∈ A n }. By Corollary 3.8, pick σ(1) ∈ {1, 2, . . . , n} such that τ = µ σ [START_REF] Bergelson | Partition theorems for spaces of variable words[END_REF] . By Theorem 4.5, P M,F, σ is a compact subsemigroup of βN containing all of the idempotents and by Theorem 4.7, Q = P M,F, σ .

Recall that a set of sets B is said to be partition regular if whenever F is a finite set of sets and F ∈ B, there exist A ∈ F and B ∈ B such that B ⊆ A. Corollary 4.9. Let n ∈ N and let τ be an S 0 -independent homomorphism from S n to N. Let B = {B ⊆ N : whenever D is a piecewise syndetic subset of S 0 , there exists w ∈ S n such that {w( x) : x ∈ A n } ⊆ D and τ (w) ∈ B}. Then B is partition regular.

Proof. By Theorem 4.7, B = {B ⊆ N : whenever S 0 is finitely colored, there exists w ∈ S n such that {w( x) : x ∈ A n } is monochromatic and τ (w) ∈ B}. It is routine to show that if k ∈ N, B i ⊆ N for each i ∈ {1, 2, . . . , k}, and k i=1 B i has the property that whenever S 0 is finitely colored, there exists w ∈ S n such that {w( x) : x ∈ A n } is monochromatic and τ (w)

∈ k i=1 B i , then some B i ∈ B.
Since the intersection of any collection of compact semigroups having the finite intersection property is a compact semigroup, it follows that there exists a smallest compact subsemigroup of (βN) k containing the idempotents of (βN) k . Question 4.10. Let k ∈ N, let M be the k × k identity matrix, and let σ be the identity function on {1, 2, . . . , k}.

(a) If F = {h x : x ∈ A k }, is P M,F, σ the smallest compact subsemigroup of (βN) k containing the idempotents of (βN) k ? (b) If not, does there exist a finite nonempty set F of S 0 -preserving homomorphisms such that P M,F, σ is the smallest compact subsemigroup of (βN) k containing the idempotents of (βN) k ? Question 4.11. Let k ∈ N and let M and N be k × k lower triangular matrices with positive diagonal entries and nonpositive entries below the diagonal. Do there exist a finite nonempty set F of S 0 -preserving homomorphisms from S k to S 0 and a permutation σ of {1, 2, . . . , k} such that P M,F, σ = P N,F, σ ?

Because of Question 4.10, we are interested in the smallest compact subsemigroup of (βN) k containing the idempotents of (βN) k .

Given a compact right topological semigroup T , we let E(T ) be the set of idempotents in T . If I is a set and for each i ∈ I, T i is a compact right topological semigroup, then E(× i∈I T i ) = × i∈I E(T i ) because the operation in × i∈I T i is coordinatewise. Also by [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Theorem 2.23

] K(× i∈I T i ) = × i∈I K(T i ) so that E K(× i∈I T i ) = × i∈I E K(T i ) .
Definition 4.12. Let T be a compact right topological semigroup and let A ⊆ T . Then J T (A) is the smallest compact subsemigroup of T containing A.

We next show that J (βN) k E((βN) k ) = J βN (E(βN))

k for k ∈ N and that a similar result applies to the minimal idempotents. Notice that in general

J T1×T2 (A 1 × A 2 ) ⊆ J T1 (A 1 ) × J T2 (A 2
). But equality need not always hold even in the case that T 1 = T 2 and A 1 = A 2 . For example, let A + be the free semigroup on the alphabet A = {a, b}, and T = βA + . Then, identifying the letters of A with the length one words so that A is a subset of T , we have

J T (A) × J T (A) = T × T while J T ×T (A × A) = c T ×T {(u, w) ∈ A + × A + : |u| = |w|}.
Theorem 4.13. Let T 1 and T 2 be compact right topological semigroups and for i ∈ {1, 2} let A i be a nonempty subset of T i with

A i ⊆ {ab : a, b ∈ A i }. Then J T1×T2 (A 1 × A 2 ) = J T1 (A 1 ) × J T2 (A 2 ). Proof. As J T1 (A 1 ) × J T2 (A 2 ) is a compact subsemigroup of T 1 × T 2 containing A 1 × A 2 we have immediately that J T1×T2 (A 1 × A 2 ) ⊆ J T1 (A 1 ) × J T2 (A 2 ). So it remains to show that J T1 (A 1 ) × J T2 (A 2 ) ⊆ J T1×T2 (A 1 × A 2 ). Let Y = {q ∈ J T2 (A 2 ) : (p, q) ∈ J T1×T2 (A 1 × A 2 ) for all p ∈ A 1 }.
Then Y is compact and A 2 ⊆ Y . Further, let q 1 , q 2 ∈ Y and p ∈ A 1 , and write p = p 1 p 2 with p 1 , p 2 ∈ A 1 . Then (p 1 , q 1 ), (p 2 , q 2 ) ∈ J T1×T2 (A 1 × A 2 ) and hence (p 1 , q 1 )(p 2 , q 2 ) = (p,

q 1 q 2 ) ∈ J T1×T2 (A 1 × A 2 ). Thus Y is a compact subsemigroup of J T2 (A 2 ) containing A 2 so Y = J T2 (A 2 ). Now let X = {x ∈ J T1 (A 1 ) : {x} × J T2 (A 2 ) ⊆ J T1×T2 (A 1 × A 2 )}. Then X is compact and if p ∈ A 1 , then {p} × J T2 (A 2 ) = {p} × Y ⊆ J T1×T2 (A 1 × A 2 ), so A 1 ⊆ X. We next claim that X is a semigroup. In fact, let x 1 , x 2 ∈ X and set Z = {z ∈ J T2 (A 2 ) : (x 1 x 2 , z) ∈ J T1×T2 (A 1 × A 2 )}.
Then Z is compact. Let q ∈ A 2 and write q = q 1 q 2 with q 1 , q 2 ∈ A 2 . Then (x 1 , q 1 ), (x 2 , q 2 ) ∈ J T1×T2 (A 1 × A 2 ) and hence (x 1 x 2 , q) ∈ J T1×T2 (A 1 × A 2 ). Thus Z contains A 2 . Finally, let z 1 , z 2 ∈ Z. Then since z 1 , z 2 ∈ J T2 (A 2 ) and x 1 , x 2 ∈ X we deduce that (x 1 , z 1 ), (x 2 , z 2 ) ∈ J T1×T2 (A 1 ×A 2 ) implying that (x 1 x 2 , z 1 z 2 ) ∈ J T1×T2 (A 1 ×A 2 ) and hence z 1 z 2 ∈ Z. Thus Z is a compact subsemigroup of J T2 (A 2 ) containing A 2 and hence Z = J T2 (A 2 ) from which it follows that x 1 x 2 ∈ X. Having shown that X is compact subsemigroup of J T1 (A 1 ) containing A 1 we deduce that X = J T1 (A 1 ). In conclusion,

J T1 (A 1 ) × J T2 (A 2 ) = X × J T2 (A 2 ) ⊆ J T1×T2 (A 1 × A 2 ) as required. Notice in particular that if for i ∈ {1, 2}, A i is a nonempty subset of E(T i ), then A i ⊆ {ab : a, b ∈ A i }, so J T1×T2 (A 1 × A 2 ) = J T1 (A 1 ) × J T2 (A 2 ).
Corollary 4.14. Let k ∈ N. The smallest compact subsemigroup of (βN) k containing the idempotents of (βN) k is J βN E(βN)

k . The smallest compact subsemigroup of (βN) k containing the minimal idempotents of (βN) k is J βN E(K(βN)) k .

Proof. By Theorem 4.13 and induction,

J (βN) k ((E(βN)) k ) = J βN E(K(βN))
k and we already observed that the set of idempotents of (βN) k is E(βN) k . The second conclusion is essentially the same.

We note now that the version of Theorem 4.13 for infinite products is also valid.

Theorem 4.15. Let I be an infinite set. For each i ∈ I, let T i be a compact right topological semigroup and let A i be a nonempty subset of T i such that

A i ⊆ {ab : a, b ∈ A i }. Then J × i∈I Ti (× i∈I A i ) = × i∈I J Ti (A i ). Proof. Let Y = × i∈I T i . For each i ∈ I, choose e i ∈ A i . Given F ∈ P f (I), let Y F = × i∈F T i , let Z F = × i∈I\F T i , let X F = { x ∈ × i∈I J Ti (A i ) : (∀i ∈ I \ F )(x i = e i )} , and let B F = { x ∈ × i∈I A i : (∀i ∈ I \ F )(x i = e i )}.
We shall show that for each F ∈ P f (I), X F ⊆ J Y (× i∈I A i ). Let F ∈ P f (I) be given. Now X F is topologically and algebraically isomorphic to

× i∈F J Ti (A i ) × × i∈I\F {e i } ,
B F is topologically and algebraically isomorphic to × i∈F A i × × i∈I\F {e i }, and × i∈I\F {e i } ⊆ J Z F (× i∈I\F {e i }). So using Theorem 4.13 we have

X F ≈ × i∈F J Ti (A i ) × × i∈I\F {e i } ⊆ J Y F (× i∈F A i ) × J Z F (× i∈I\F {e i }) = J Y F ×Z F (× i∈F A i × × i∈I\F {e i }) ≈ J Y (B F ) ⊆ J Y (× i∈I A i ) . Next we claim that × i∈I J Ti (A i ) ⊆ c Y F ∈P f (I) X F . To see this, let z ∈ × i∈I J Ti (A i ) and let U be a neighborhood of z in Y . Pick F ∈ P f (I) and for each i ∈ F , pick a neighborhood V i of z i in T i such that i∈F π -1 i [V i ] ⊆ U . Define x ∈ Y by x i = z i if i ∈ F e i if i ∈ I \ F . Then x ∈ U ∩ X F . Therefore × i∈I J Ti (A i ) ⊆ J Y (× i∈I A i ). Since × i∈I J Ti (A i
) is a compact semigroup con- taining × i∈I A i , the reverse inclusion is immediate.

The curious reader may wonder what the situation is with respect to the smallest semigroup containing a given set. Given a semigroup T and a nonempty subset A of T , let J T (A) be the smallest subsemigroup of T containing A, that is the set of all finite products of members of A in any order allowing repetition. If T 1 and T 2 are any semigroups and A 1 and A 2 are nonempty subsets of T 1 and T 2 respectively such that

A i ⊆ {ab : a, b ∈ A i } for i ∈ {1, 2}, then J T1×T2 (A 1 × A 2 ) = J T1 (A 1 ) × J T2 (A 2
). This follows from the proof of Theorem 4.13 by omitting all references to the topology. However, the analogue of Theorem 4.15 need not hold. To see this, let T be the set of words over the alphabet {a n : n ∈ N} that have no adjacent occurrences of any one letter. Given u, w ∈ T , then u • w is ordinary concatenation unless u = xa n and w = a n y for some n ∈ N and some x, y ∈ T ∪ {∅}, in which case u • w = xa n y. Let A be the set of idempotents in T , that is A is the set of length one words. Then J T

(A) = T but { x ∈ × ∞ n=1 T : {|x n | : n ∈ N} is bounded} is a proper subsemigroup of × ∞ n=1 T containing the idempotents.

Compact ideals of (βS) k

In this section we deal with results related to the Hales-Jewett Theorem and its extensions by themselves. The first result here is motivated by the following theorem characterizing image partition regular matrices.

∈ N m such that M x ∈ D k . (c) For every central subset D of N, { x ∈ N m : M x ∈ D k } is central in N m .
Proof. These are statements (a), (h), and (i) of [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Theorem 15.24].

As a consequence of Theorem 2.10 (with k = m = 1, T = N, M = (1), τ = µ 1 , F = {h x : x ∈ A n }, and p any idempotent in βN) we have that whenever D is piecewise syndetic in S 0 and n ∈ N, there exists w ∈ S n such that {w( x) : x ∈ A n } ⊆ D. Since whenever S 0 is finitely colored, one color class must be piecewise syndetic, we see that Theorem 1.3 follows. And, since central sets are piecewise syndetic, we have that whenever D is central in S 0 and n ∈ N, there exists w ∈ S n such that {w( x) : x ∈ A n } ⊆ D. Proof. Let T = S n ∪ S 0 and extend each ν ∈ F to all of T by defining ν to be the identity on S 0 . By Theorem 1.5(2), pick a central subset

Q of T such that for each t ∈ Q, {ν(t) : ν ∈ F } ⊆ D}. Since S n is an ideal of T , Q ∩ S n is central in S n and Q ∩ S n ⊆ {w ∈ S n : (∀ν ∈ F )(ν(w) ∈ D)}.
We conclude this section by investigating ideals related to the extensions of the Hales-Jewett Theorem.

Definition 5.3. For n ∈ N, R n = {p ∈ βS 0 : (∀B ∈ p)(∃w ∈ S n )({w( x) : x ∈ A n } ⊆ B)} .
There are numerous ways to use known results to show that each R n = ∅. From the point of view of this paper, it is probably easiest to invoke Theorem 2.10 as discussed above. (2) whenever C n,r is r-colored, there exists w ∈ S m n such that {w( x) : x ∈

A n } is monochromatic.
Proof. This is the "main theorem" of [START_REF] Deuber | A restricted version of Hales-Jewett's theorem[END_REF].

( x) : x ∈ A n+1 } ⊆ C n,ri . Thus E ∩ R n+1 = ∅.
As in the proof of Theorem 5.7, let R = {D ⊆ S 0 : whenever D is finitely colored, there exists w ∈ S n such that {w( x) : x ∈ A n } is monochromatic}. It suffices to show that E ∈ R so let k ∈ N and let ϕ : E → {1, 2, . . . , k}. Pick i such that r i ≥ k. Then ϕ |Di : D i → {1, 2, . . . , r i } so pick w ∈ S m(r i ) n such that ϕ is constant on {w( x) : x ∈ A n }.

A simpler proof of an infinitary extension

We set out in this section to provide a proof of [2, Theorem 2.12] applied to the simpler description of n-variable words which we have been using. As defined in Thus it suffices to show that each p t ∈ β S t . We proceed by induction on t. For t = 0, we have p 0 ∈ βS 0 = β S 0 . Now assume that t + 1 < α and p t ∈ β S t . We need to show that S t+1 ∈ p t+1 . We begin by observing that if w ∈ S t then S t+1 ⊆ w -1 S t+1 from which it follows that S t ⊆ {w ∈ T t+1 : w -1 S t+1 ∈ p t+1 }. Now since S t ∈ p t we have that {w ∈ T t+1 : w -1 S t+1 ∈ p t+1 } ∈ p t or equivalently that S t+1 ∈ p t p t+1 . The result now follows from the fact that p t+1 ≤ p t and hence in particular p t+1 = p t p t+1 .

We now introduce some new notation. We fix a nonempty (possibly infinite) alphabet A together with an infinite sequence of symbols {x 1 , x 2 , x 3 , . . .} each of which is not a member of A ∪ {v i : i ∈ N}. We let A (0) = A and for m ∈ N, we let A (m) = A ∪ {x 1 , x 2 , . . . , x m }. For each m ∈ ω we let S (m) denote the free semigroup over A (m) . For each i ∈ N we let S (m) i denote the set of all i-variable words over the alphabet A (m) and let S (m) i denote the set of all strong i-variable words over A (m) . T (j) i will denote the free semigroup of all words over the alphabet A (j) ∪ {v 1 , v 2 , . . . , v i }. Also, for each j ∈ ω, let S i . Then T (j) is the set of all words over A (j) ∪ {v i : i ∈ N}.

To each u = u 1 u 2 • • • u m ∈ T (j) with |u| = m we associate a morphism h u : j∈ω T (j) → j∈ω T (j) where for each w ∈ j∈ω T (j) , h u (w) is obtained from w by replacing each occurrence of v i in w by u i for each i ∈ {1, 2, . . . , m}. We also denote by h u its continuous extension taking β( j∈ω T (j) ) to β( j∈ω T (j) ). Also, for each i, j ∈ N we define the morphism, τ (j) i : T (j) → T (j-1) where τ (j) i (w) is the word obtained from w by replacing every occurrence of x j by v i and leaving all other symbols unchanged. We also denote by τ (j) i the continuous extension of τ (j) i taking βT (j) to βT (j-1) . Note that τ Proof. We will show that G (m) i is the intersection of a minimal right ideal and a minimal left ideal of βS ) and τ ) and K(βS

(m+1) i-1 ) = K(βT (m+1) i-1
) (Lemma 6.3 with the underlying alphabet taken to be A (m+1) ), it follows that τ Definition 6.8. Let i, j, m ∈ ω, with j < i. X (m) i,j will denote the set of words in S (m) i j in which v j occurs only as the last letter. Lemma 6.9. Let m, n ∈ N and let p = p 0 , p 1 , p 2 , . . . , p n be a reductive sequence of height n + 1 over A (m) . Let p n+1 be a minimal idempotent in βS

(f) S 0 =

 0 S 0 . (g) If m ∈ ω = N ∪ {0} and m < n, then S n m is the set of u ∈ S m such that |u| = n. (h) If m ∈ ω and m < n, then S n m is the set of u ∈ S m such that |u| = n.

Theorem 1 . 4

 14 (R. Graham and B. Rothschild). Assume that A is finite. Let m, n ∈ ω with m < n and let S m be finitely colored. There exists w ∈ S n such that {w(u) : u ∈ S n m } is monochromatic. Proof. [4, Section 7].

∞

  m=1 F P ( x n ∞n=m ) is a compact semigroup so there is an idempotent p with F P ( x n ∞ n=m ) ∈ p for every m. (See [6, Lemma 5.11].) If the operation is denoted by +, we write F S( x n ∞ n=m ) = { t∈F x t : F ∈ P f (N) and min F ≥ m}. Given an idempotent p and B ∈ p let B (p) = {x ∈ B : x -1 B ∈ p}. Then B (p) ∈ p and for each x ∈ B (p), one has that x -1 B (p) ∈ p. (See [6, Lemma 4.14]). If there is no risk of confusion, we will sometimes write B for B (p).

Corollary 2 . 5 .

 25 Define τ : S 1 → N by τ (w) = |w| v1 , let S 0 be finitely colored, and let x n ∞ n=1 be a sequence in N. There exists w ∈ S 1 such that {w(a) : a ∈ A} is monochromatic and τ (w) ∈ F S( x n ∞ n=1 ). Proof. Let S = S 0 , let T = S 1 , and let C = βN. Then τ [S 1 ] is contained in the topological center of C. Denote also by τ the continuous extension taking βS 1

  the group of differences of T . In each case we define an S 0independent homomorphism φ :S n → × k j=1 G. by φ(w) = M ψ(w). Let C = × kj=1 βG. Then by Lemma 2.7, φ extends to an S 0 -independent homomorphism φ : βS n → C and p ∈ φ[βS n ]. The rest now follows from Corollary 2.6. Definition 2.11. Let n ∈ N and let j ∈ {1, 2, . . . , n}. Define µ j : S n → N by µ j (w) = |w| vj .

Lemma 3 . 3 .

 33 Fix n ∈ N. Let (T, +) be a cancellative and commutative semigroup and let ϕ : S n → T be an S 0 -independent homomorphism. For each w 1 , w 2 ∈ S n we have ϕ(w 1 ) = ϕ(w 2 ) whenever w 1 ∼ Ab w 2 . Proof. Assume w 1 , w 2 ∈ S n and w 1 ∼ Ab w 2 . Let m = |w 1 | = |w 2 |. We show that ϕ(w 1 ) = ϕ(w 2 ) which in turn implies that ϕ(w 1 ) = ϕ(w 2 ) by Lemma 3.2. The result is immediate in case n = 1 for in this case w 1 = w 2 = v m 1 . So let us assume that n ≥ 2 in which case m ≥ 2. Since the symmetric group on m-letters is generated by the 2-cycle (1, 2) and the m-cycle (1, 2, . . . , m) it suffices to show (i) If x, w ∈ (A ∪ {v 1 , v 2 , . . . , v n }) + and xw ∈ S n , then wx ∈ S n and ϕ(wx) = ϕ(xw).

Theorem 4 . 1 .

 41 Let n ∈ N, let C be a compact right topological semigroup, let φ : S n → C be an S 0 -independent homomorphism for which φ[S n ] is contained in the topological center of C, denote also by φ the continuous extension from βS to C, and let F be a finite nonempty set of S 0 -preserving homomorphisms from S n into S 0 . Let P = p ∈ φ[βS n ] : for every neighborhood U of p and every piecewise syndetic subset D of S 0 (∃w ∈ S n ) φ(w) ∈ U and (∀ν ∈ F )(ν(w) ∈ D) .

Theorem 5 . 1 .

 51 Let k, m ∈ N and let M be a k × m matrix with entries from Q. The following statements are equivalent. (a) M is image partition regular over N. (b) For every central subset D of N, there exists x

Theorem 5 . 2 .

 52 Let n ∈ N and let D be a central subset of S 0 . Let F be a finite nonempty set of S 0 -preserving homomorphisms from S n into S 0 . Then {w ∈ S n : (∀ν ∈ F )(ν(w) ∈ D)} is central in S n .

Theorem 5 . 4 .

 54 Let n ∈ N. Then R n is a compact two sided ideal of βS 0 . Now let n ∈ N. We will show that B ∩ R n = ∅. Let R = {D ⊆ S 0 : whenever D is finitely colored, there exists w ∈ S n such that {w( x) : x ∈ A n } is monochromatic}. Notice that R is partition regular. It suffices to show that B ∈ R, for then by[START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF] Theorem 3.11] there exists p ∈ βS 0 such that B ∈ p and p ⊆ R so that p ∈ B ∩ R n . So let r ∈ N and let ϕ : B → {1, 2, . . . , r}. Pick m as guaranteed by Lemma 5.6 for r and n. The ϕ is an r-coloring of S m! 0 so pick w ∈ S m! n such that {w( x) : x ∈ A n } is monochromatic. Since {B∩R n : n ∈ N} is a collection of closed sets with the finite intersection property, we have that B ∩ ∞ n=1 R n = ∅. Theorem 5.8 (Deuber, Prömel, Rothschild, and Voigt). Let n, r ∈ N. There exist m ∈ N and C n,r ⊆ S m 0 such that (1) there does not exist w ∈ S m n + 1 with {w( x) : x ∈ A n+1 } ⊆ C n,r and

Theorem 5 . 9 .

 59 Let n ∈ N. Then R n+1 R n . Proof. For each r ∈ N pick m(r) and C n,r as guaranteed for r and n by Theorem 5.8. Choose an increasing sequence r i ∞ i=1 such that the sequence m(r i ) ∞ i=1 is strictly increasing and let D i = C n,ri for each i. Let E = ∞ i=1 D i . There does not exist w ∈ S n+1 such that {w( x) : x ∈ A n+1 } ⊆ E because any such w would have to have length m(r i ) for some i, and then one would have {w

=

  S(j) , and letT (j) = ∞ i=1 T (j)

6 .

 6 Let m ∈ ω, let i ∈ N \ {1}, and assume that p

. 1 .

 1 Definition 6.7. For α ∈ N∪{ω}, a reductive array of height α over A is an α×ω array of minimal idempotents p For each m ∈ ω the sequence p (m) i i<α is a reductive sequence of height α over A(m) . each m ∈ N.

3 .

 3 For each m ∈ ω and i < α with i ≥ 2, p (m) i is the identity of the group G

( 1 )( 2 )

 12 for which p n+1 ≤ p n . Let j ∈ ω with j ≤ n and let u =u 1 u 2 • • • u n+1 ∈ S (m) n + 1 j . If u / ∈ X (m) n+1,j , then h u (p n+1 ) = p j . If u ∈ X (m) n+1,j , then for w ∈ T (m+1) n , h u τ (m+1) n+1 (w) = τ (m+1) j h u (w) . Proof. (1) Assume u / ∈ X (m)n+1,j . We have that h u (p n+1 ) and h u (p n ) are both idempotents in βS(m) j and h u (p n+1 ) ≤ h u (p n ) because h u is a homomorphism. Assume first that j < n and let s = u 1 u 2 • • • u n . Then s ∈ S (m) n j so h s (p n ) = p j and since h s and h u agree on S (m) n , h u (p n ) = p j . If j = n, then u = v 1 v 2 • • • v n u n+1 so h u is the identity on S (m) nand again h u (p n ) = p j . Consequently, h u (p n+1 ) ≤ p j and p j is minimal in βS (m) j so h u (p n+1 ) = p j .

( 2 )

 2 It suffices to show that hu τ (m+1) n+1 (l) = τ (m+1) j h u (l) for each l ∈ A (m+1) ∪ {v 1 , v 2 , . . . , v n }. Now h u τ (m+1) n+1 (x m+1 ) = h u (v n+1 ) = u n+1 = v j and τ (m+1) j h u (x m+1 ) = τ

  ) = v j . If l ∈ A (m) , then both sides leave

  There exist idempotents p 1 and p 2 in βN and sets B 1 ∈ p 1 and B 2 ∈ p 2 Let p 1 and p 2 be idempotents in βN, and let B 1 ∈ p 1 and B 2 ∈ p 2 be given. By Theorem 2.8, it suffices to show that there exists w ∈ S 2 such By [6, Lemma 6.6], 3N ∈ p 1 and 3N ∈ p 2 . Pick

	for which there does not exist w ∈ S 2 such that N	τ 1 (w) τ 2 (w)	∈ × 2 i=1 B i .
	Proof. (1) that M	τ 1 (w) τ 2 (w)	∈ × 2 i=1 B i

  x} and for i ∈ {0, 1, 2, 3} let B i = {x ∈ N : φ(x) ≡ i (mod 4)}. Then B 0 and B 2 are central and there do not exist x and y ∈ N such that M x y ∈ B 0 × B 2 .

Proof. By

[START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF] Theorem 15

.5] M is image partition regular over N. Since N = 3 i=0 B i some B i is central. But then, by

[START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF] Lemma 15.23.2]

, each B i is central. Suppose we have some x, y ∈

This work was supported in part by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).

Proof. We have that R n = ∅ and it is trivially compact. Let p ∈ R n and let q ∈ βS 0 . To see that R n is a left ideal, let B ∈ qp. Pick u ∈ S 0 such that u -1 B ∈ p and pick w ∈ S n such that {w( x) : x ∈ A n } ⊆ u -1 B. Then uw ∈ S n and {(uw)( x) : x ∈ A n } ⊆ B.

To see that R n is a right ideal, let B ∈ pq. Pick w ∈ S n such that {w( x) :

x ∈ A n } ⊆ {u ∈ S 0 : u -1 B ∈ q}. Pick u ∈ x∈A n w( x) -1 B. Then wu ∈ S n and {(wu)( x) : x ∈ A n } ⊆ B.

. We claim first that B is not piecewise syndetic, so that B ∩ c K(βS 0 ) = ∅. We need to show that there is no G ∈ P f (S 0 ) such that for all F ∈ P f (S 0 ) there exists x ∈ S 0 such that F x ⊆ t∈G t -

this paper, what is called the set of n-variable words in [START_REF] Carlson | An infinitary extension of the Graham-Rothschild Parameter Sets Theorem[END_REF], is what we call the set of strong n-variable words where we take D = E = {e} in [START_REF] Carlson | An infinitary extension of the Graham-Rothschild Parameter Sets Theorem[END_REF], take the function T e to be the identity, and let v n = (e, ν n ) for n ∈ N. As we remarked earlier, in [2, Theorem 5.1] it was shown that the version of the Graham-Rothschild that we are using here is sufficient to derive the full original version as used in [START_REF] Carlson | An infinitary extension of the Graham-Rothschild Parameter Sets Theorem[END_REF] and [START_REF] Graham | Ramsey's Theorem for n-parameter sets[END_REF]. Using that simplified notion, Corollary 6.13 implies [2, Theorem 2.12] and has a vastly simpler proof.

The first few results apply to an arbitrary nonempty alphabet A. For the results of this section, except for Corollary 6.14, we do not need to assume that A is finite.

Also we set T 0 = S 0 and T = i∈ω T i .

Note that for n ∈ N, S n is a proper subset of T n and that T n ⊆ T n+1 .

Definition 6.2. For α ∈ N ∪ {ω}, a reductive sequence of height α over A is a sequence of minimal idempotents p t t<α with p t ∈ E K(βS t ) such that for each i, j ∈ ω with 0 ≤ j < i < α one has p i ≤ p j and h u (p i ) = p j for each u ∈ S i j .

Lemma 6.3. Let i ∈ ω. Then K(βS i ) = K(βT i ).

Proof. We have that S i is an ideal of T i so by [START_REF] Hindman | Algebra in the Stone-Čech compactification: theory and applications[END_REF]Corollary 4.18] βS i is an ideal of βT i . Therefore K(βT i ) ⊆ βS i so that by [6, Theorem 1.65] K(βS i ) = K(βT i ).

Lemma 6.4. Let k, m ∈ ω with k < m and let p ∈ E(βS k ). There exists q ∈ E K(βS m ) such that q < p.

Proof. We have βS m ∪ βS k ⊆ T m . Pick q ∈ E K(βT m ) such that q ≤ p. By Lemma 6.3, q ∈ K(βS m ) and since βS k ∩ βS m = ∅, q = p. Lemma 6.5. Let α ∈ N ∪ {ω} and let p t t<α be a reductive sequence of height α. For each t < α, p t ∈ E K(β S t ) .

Proof. Since each p t is an idempotent, it suffices to show that p t ∈ K(β S t ). Given t < α, S t is a right ideal of S t so β S t is a right ideal of βS t and thus

Lemma 6.10. Let q ∈ E K(βS 0 ) and let r ∈ E K(βS 1 ) such that r < q. There is a reductive array p

, we may let p (m) 0 be the unique member of E K(βT

. By Lemma 6.4, we may pick p

We need to show that for each u ∈ S (m) 1 0 , h u (p n+1 . This is required by Definition 6.7(3), so the uniqueness is satisfied. Let m < ω be given. We need to show that p

n . And by Lemma 6.6 we have that p

Now let 0 ≤ j < i < n + 2 and let u ∈ S (m) i j . We need to show that

. If i < n + 1, this holds by assumption, so assume that

n+1,j , then by Lemma 6.9, h u (p

33

Then we have that s ∈ S (m) n j -1 ⊆ S (m+1) n j -1 and hence h u (p

j-1 . Combined with Lemma 6.9, we have that

Finally, assume that j = 1. Then

Combining Lemma 6.10 and Theorem 6.11 we obtain: Corollary 6.12. For each p ∈ E K(βS 0 ) there is a reductive array p (2) for each n ∈ N, p n is a minimal idempotent of β S n ;

(3) for each n ∈ N, p n ≤ p n-1 ;

(4) for each n ∈ N, each j ∈ {0, 1, . . . , n -1}, and each u ∈ S n j , h u (p n ) = p j . Further, p 1 can be any minimal idempotent of βS 1 such that p 1 ≤ p 0 .

Proof. Let p (m) i m<ω i<ω be as guaranteed by Corollary 6.12 and for each i < ω let p i = p (0) i . By Lemma 6.5 each p n ∈ E K(β S n ) .

For several stronger combinatorial consequences of Corollary 6.13, see Sections 3 and 4 of [START_REF] Carlson | An infinitary extension of the Graham-Rothschild Parameter Sets Theorem[END_REF].

To derive the following extension of Theorem 1.4, we need to restrict to a finite alphabet.