New York Journal of Mathematics

New York J. Math. 6 (2000) 73–86.

Continuous Homomorphisms on βℕ and Ramsey Theory

Dennis Davenport, Neil Hindman, Imre Leader, and Dona Strauss

Abstract. We consider the question of the existence of a nontrivial continuous homomorphism from (βℕ, +) into ℕ^{∗} = βℕ\ℕ. This problem is known to be equivalent to the existence of distinct p and q in ℕ^{∗} satisfying the equations p + p = q = q + q = q + p = p + q. We obtain certain restrictions on possible values of p and q in these equations and show that the existence of such p and q implies the existence of p, q, and r satisfying the equations above and the additional equations r = r + r, p = p + r = r + p, and q = q + r = r + q. We show that the existence of solutions to these equations implies the existence of triples of subsets of ℕ satisfying an unusual Ramsey Theoretic property. In particular, they imply the existence of a subset A with the property that whenever it is finitely colored, there is a sequence in the complement of A, all of whose sums two or more terms at a time are monochrome. Finally we show that there do exist sets satisfying finite approximations to this latter property.

Contents

1. Introduction 73 2. Special Two and Three Element Subsemigroups of βℕ 75 3. Ramsey Theoretic Consequences 77 4. A Finitary Ramsey Theoretic Approximation 81 References 85

1. Introduction

In 1979, van Douwen asked (in [5], published much later) whether there are topological and algebraic copies of the right topological semigroup (βℕ, +) contained in ℕ^{∗} = βℕ\ℕ. This question was answered in [15], where it was in fact established that if φ is a continuous homomorphism from βℕ to ℕ^{∗}, then φ[βℕ] is finite. Whether one can have such a continuous homomorphism with |φ[βℕ]| > 1 is a difficult open question which we address in this paper.

Received December 4, 1999. Mathematics Subject Classification. 05D10, 22A30. Key words and phrases. continuous homomorphism, Ramsey Theory, Stone-Čech

compactification.

73^{ISSN 1076-9803/00}

Another old and difficult problem in the algebra of βℕ was solved in 1996 by E. Zelenuk [16] who showed that there are no nontrivial finite groups contained in ℕ^{∗}. (See [10, Section 7.1] for a presentation of this proof.) Using Zelenuk’s Theorem, it is not hard to show that there is a nontrivial continuous homomorphism from βℕ to ℕ^{∗} if and only if there exist distinct p and q in ℕ^{∗} such that p + p = q = q + q = q + p = p + q. (See [10, Corollary 10.20].) It is in this guise that we shall be investigating the continuous homomorphism problem.

The question of which finite semigroups can exist in ℕ^{∗} has implications for a large class of semigroups of the form βS. It is not hard to prove that any finite semigroup in ℕ^{∗} is contained in ℍ = ⋂_{n∈ℕ} cl_{βℕ}(2^{n}ℕ). Now if S is any infinite discrete semigroup which is right cancellative and weakly left cancellative, S^{∗} contains copies of ℍ [10, Theorem 6.32]. Thus a finite semigroup which occurs in ℕ^{∗} also occurs in S^{∗}, if S is any semigroup of this kind.

The conjecture that ℕ^{∗} contains no elements of finite order, other than idempotents, has implications about the nature of possible continuous homomorphisms from βS into ℕ^{∗}, where S is any semigroup at all. If C is any compact subsemigroup of ℕ^{∗}, its topological center Λ(C) = {x ∈ C : λ_{x} : C → C is continuous} contains only elements of finite order[12, Corollary 6.8]. It follows that, if this conjecture is true, then any continuous homomorphism from βS into ℕ^{∗} must map all the elements of S to idempotents.

We write ℕ for the positive integers and ω for the nonnegative integers. Given a set X, P_{f}(X) is the set of finite nonempty subsets of X. The points of βℕ are the ultrafilters on ℕ and the topology of βℕ is defined by choosing the sets of the form \overline{A} = \{p ∈ βℕ : A ∈ p\}, where A ⊆ ℕ, as a basis for the open sets. Then each set \overline{A} is clopen in βℕ and \overline{A} = cl_{βℕ}A. The operation + on βℕ is the extension of ordinary addition on ℕ making (βℕ, +) into a right topological semigroup (meaning that for all p ∈ βℕ, the operation ρ_{p} : βℕ → βℕ defined by ρ_{p}(q) = q+p is continuous) with ℕ as its topological center (which is the set of points x such that the function λ_{x} : βℕ → βℕ defined by λ_{x}(q) = x + q is continuous). Given p, q ∈ βℕ and A ⊆ ℕ, A ∈ p + q if and only if {x ∈ ℕ : −x + A ∈ q} ∈ p, where −x + A = {y ∈ ℕ : x + y ∈ A}. See [10] for an elementary introduction to the compact right topological semigroup (βℕ, +).

In Section 2 we present some restrictions on possible values of p and q solving the equations p + p = q = q + q = q + p = p + q. We further establish that the existence of such a two element semigroup in ℕ^{∗} implies the existence of a three element semigroup {p, q, r} where p + p = q = q + q = q + p = p + q, r + r = r, p = p + r = r + p, and q = q + r = r + q (and consequently, the existence of a nontrivial continuous homomorphism from βℕ to ℕ^{∗} implies the existence of such a semigroup).

In Section 3 we show that the existence of the three element semigroup described above implies the existence of a triple of disjoint subsets of ℕ satisfying a strong infinitary Ramsey Theoretic property. A simpler consequence of this property is the following assertion. If there is a nontrivial continuous homomorphism from βℕ into ℕ^{∗}, then there is a subset A of ℕ with the property that, whenever A is finitely colored, there must exist a sequence ⟨x_{n}⟩_{n=1}^{∞} in ℕ\A such that

{∑_{t∈F} x_{t} : F ∈ P_{f}(ℕ) and |F | ≥ 2}

Continuous Homomorphisms on βℕ and Ramsey Theory 75

is a monochrome subset of A. (When we refer to a “k-coloring” of a set X we mean a function ϕ : X → {1, 2, …, k}. The assertion that a set B is “monochrome” is the assertion that ϕ is constant on B.)

We concentrate on this simple assertion for the remainder of the paper. While it is not known whether any set satisfying such a property exists, we hope to popularize the search for a set satisfying that property (or the search for a proof that no such set exists). We do establish that certain classes of sets do not have that property.

In Section 4, we show that sets satisfying arbitrary finite approximations to this simpler Ramsey Theoretic property do exist.

2. Special Two and Three Element Subsemigroups of βℕ

Given idempotents r and s in ℕ^{∗}, one says that r ≤_{R} s if and only if r = s+r, r ≤_{L} s if and only if r = r + s, and r ≤ s if and only if r = s + r = r + s. If k ∈ ℕ and one has distinct idempotents r_{1} ≤ r_{2} ≤ … ≤ r_{k} (which exist by [10, Theorem 9.23]), then {r_{1}, r_{2}, …, r_{k}} is a k element subsemigroup of ℕ^{∗}. However, by [10, Corollary 10.20], the existence of a nontrivial continuous homomorphism from βℕ to ℕ^{∗} is equivalent to the existence of a finite subsemigroup of ℕ^{∗} whose elements are not all idempotents, and also equivalent to the existence of a two element subsemigroup of ℕ^{∗} whose elements are not all idempotents. Such a subsemigroup is necessarily of the form {p, q}, where p + p = q = q + q = q + p = p + q. Curiously, Zelenuk’s Theorem implies that if p + p = q, then one of the equations p + q = q, q + p = q, or q + q = q implies the others.

Lemma 2.1. Let p and q be elements of ℕ^{∗}. If p + p = q and any one of p + q, q + p, or q + q is equal to q, then p + p = q = q + q = p + q = q + p.

Proof. If p = q, then the conclusion is trivial, so assume that p ≠ q. Note that q + p = p + p + p = p + q. If q = q + p, then q + q = q + p + p = q + p = q. So assume that q = q + q. Then {q, q + p} is a subgroup of ℕ^{∗}, so by Zelenuk’s Theorem [10, Theorem 7.17], q = q + p. □

Next we show that the existence of such a two element subsemigroup of ℕ^{∗} implies the existence of a particular three element subsemigroup of ℕ^{∗}, exactly two of whose members are idempotents. The existence of this semigroup yields the sets with the strong Ramsey Theoretic property that we have discussed. To say that an idempotent r is ≤_{R}-maximal means that whenever r ≤_{R} s, one also has s ≤_{R} r.)

Theorem 2.2. Let p and q be distinct elements of ℕ^{∗} such that p + p = q = q + q = p + q = q + p. Then there exist distinct p′, q′, and r′ in ℕ^{∗} such that p′ + p′ = q′ = q′ + q′ = p′ + q′ = q′ + p′, r′ + r′ = r′, p′ + r′ = r′ + p′ = p′, and q′ + r′ = r′ + q′ = q′. Further, the idempotent r′ can be chosen to be ≤_{R}-maximal in ℤ^{∗} = βℤ\ℤ.

Proof. We observe that it suffices to produce distinct p′, q′, and r′ in ℤ^{∗}, with r′ ≤_{R}-maximal in ℤ^{∗}, satisfying the specified equations. To see this notice that by [10, Exercise 4.3.5], both ℕ^{∗} and −ℕ^{∗} are left ideals of βℤ. Thus, either p′, q′, and r′ are all in ℕ^{∗} as desired, or they are all in −ℕ^{∗}. In the latter event, let p′′ = −p′, q′′ = −q′, and r′′ = −r′. Then p′′, q′′, and r′′ are distinct members of ℕ^{∗} and, by [10, Lemma 13.1], they satisfy the specified equations. It is easy to verify that r′′ is also ≤_{R}-maximal in ℤ^{∗}.

Since q + p = p + p we have that p is not right cancelable in βℤ so by [10, Theorem 8.18], there is an idempotent r ∈ ℤ^{∗} such that r + p = p. Notice that if s is any idempotent with r ≤_{R} s, then s + p = s + r + p = r + p = p.

We consider first the possibility that there is some ≤_{R}-maximal idempotent s ≥_{R} r in ℤ^{∗} such that p + s = p. Then s + p = p, s + q = s + p + q = p + q = q, and q + s = q + p + s = q + p = q. Further, since s + p = p, s ≠ p and s ≠ q. Thus, letting r′ = s, p′ = p, and q′ = q, we are done.

Now assume that for every ≤_{R}-maximal idempotent s ≥_{R} r in ℤ^{∗}, p + s ≠ p. Pick by [10, Theorem 2.12], a ≤_{R}-maximal idempotent r′ such that r ≤_{R} r′. Then, as noted above, r′ + p = p. Let p′ = p + r′ and let q′ = q + r′. Then immediately p′ + r′ = p′ and q′ + r′ = q′. Also r′ + p′ = r′ + p + r′ = p + r′ = p′ and r′ + q′ = r′ + q + r′ = r′ + p + q + r′ = p + q + r′ = q + r′ = q′. Further p′ + p′ = p + r′ + p + r′ = p + p + r′ = q + r′ = q′ and q′ + p′ = q + r′ + p + r′ = q + p + r′ = q + r′ = q′. Consequently, by Lemma 2.1, p′ + q′ = q′ + q′ = q′.

To complete the proof we need to show that p′, q′, and r′ are all distinct. For this, it suffices to show that p′ ≠ q′. (For then r′ + p′ = p′, p′ + p′ = q′, and q′ + p′ = q′ so r′ ≠ q′ and r′ ≠ p′.) So suppose instead that p′ = q′, that is, p + r′ = q + r′. Then by [10, Theorem 9.4 and Lemma 9.5] there is an idempotent s ≥_{R} r′, necessarily ≤_{R}-maximal, such that either p = q + s or q = p + s. If we had q + s = p, then we would have q + p = q + q + s = q + s = p, a contradiction. Thus q = p + s and so p + p = p + s.

Now, by [10, Corollary 6.20] there is some x ∈ βℤ such that p = x+s or s = x+p. Suppose first that p = x + s. Then p + s = x + s + s = x + s = p, a contradiction since s ≥_{R} r′ and we are assuming that for every ≤_{R}-maximal idempotent s ≥_{R} r′, p + s ≠ p. Thus, s = x + p so, since r ≤_{R} s, p = s + p = x + p + p = x + q and so p + q = x + q + q = x + q = p, a contradiction. □

Theorem 2.3. Let p and q be distinct elements of ℕ^{∗} such that p+p = q = q +q = p + q = q + p. Then p is not a member of any subgroup of βℕ. In particular, p is not a member of the smallest ideal K(βℕ) of βℕ.

Proof. Suppose that p is a member of a subgroup G of ℕ^{∗} with identity r. Then q is an idempotent in G and so q = r and thus q + p = p, a contradiction. For the “in particular” conclusion, recall that the smallest ideal of any compact right topological semigroup is the union of groups [10, Theorems 2.7 and 2.8]. □

We have not been able to show that q ∉ K(βℕ). However, it is not even known whether there is any p ∈ βℕ\K(βℕ) with p + p ∈ K(βℕ). See [9] for information about the question of whether K(βℕ) is prime or semiprime.

In [1, Theorem 2.2] it was shown that if p ∈ ℕ^{∗} and p generated a finite subsemigroup of ℕ^{∗}, then p could not be distinguished from an idempotent by means of a continuous homomorphism into a compact topological group. In the current context we have a stronger, yet very simple, result. Notice for example that the requirement that “every idempotent is a right identity” is satisfied by any minimal left ideal [10, Lemma 1.30].

Lemma 2.4. Let p and q be distinct elements of ℕ^{∗} such that p + p = q = q + q = p + q = q + p and let (T, ·) be a semigroup in which every idempotent is a left identity or every idempotent is a right identity. If φ is a homomorphism from any semigroup containing {p, q} to T, then φ(p) = φ(q).

Proof. Assume without loss of generality that every idempotent in T is a right identity of T. Then φ(p) = φ(p) · φ(q) = φ(p + q) = φ(q). □

3. Ramsey Theoretic Consequences

We show in this section that the existence of a continuous homomorphism from βℕ to ℕ^{∗} implies the existence of disjoint subsets of ℕ satisfying a strong infinitary Ramsey Theoretic property.

Definitions 3.1. Let ⟨x_{n}⟩_{n=1}^{∞} be a sequence in ℕ, then

(1) F S(⟨x_{n}⟩_{n=1}^{∞}) = {∑_{n∈F} x_{n} : F ∈ P_{f}(ℕ)}.

(2) F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) = {∑_{n∈F} x_{n} : F ∈ P_{f}(ℕ) and |F | ≥ 2}.

(3) If k ∈ ℕ, F S_{k}(⟨x_{n}⟩_{n=1}^{∞}) = {∑_{n∈F} x_{n} : F ∈ P_{f}(ℕ) and |F | = k}.

Similarly, if ⟨x_{t}⟩_{t=1}^{m} is a finite sequence, we shall let

F S_{≥2}(⟨x_{t}⟩_{t=1}^{m}) = {∑_{t∈F} x_{t} : ∅ ≠ F ⊆ {1, 2, …, m} and |F | ≥ 2}.

Recall [10, Theorem 5.12] that a set A ⊆ ℕ is a member of some idempotent in βℕ if and only if there is some sequence ⟨x_{n}⟩_{n=1}^{∞} with F S(⟨x_{n}⟩_{n=1}^{∞}) ⊆ A. Part of this assertion is imitated in the following theorem.

Theorem 3.2. Let p, q, and r be elements of ℕ^{∗} such that p + p = q = q + q = q + p = p + q, r + r = r, r + p = p + r = p, and q + r = r + q = q. Let A ∈ q, B ∈ r, and C ∈ p. Then there exist sequences ⟨x_{n}⟩_{n=1}^{∞} and ⟨y_{n}⟩_{n=1}^{∞} in ℕ such that (1) F S(⟨y_{n}⟩_{n=1}^{∞}) ⊆ B,

(2) for all n ∈ ℕ and all z ∈ F S(⟨y_{n}⟩_{n=1}^{∞}) ∪ {0}, x_{n} + z ∈ C (and in particular {x_{n} : n ∈ ℕ} ⊆ C ), and

(3) for all w ∈ F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) and all z ∈ F S(⟨y_{n}⟩_{n=1}^{∞}) ∪ {0}, w + z ∈ A (and in particular F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) ⊆ A).

Proof. Let

Â = {a ∈ A : −a + A ∈ p ∩ q ∩ r} ,
B̂ = {b ∈ B : −b + A ∈ q , −b + B ∈ r, and − b + C ∈ p}, and
Ĉ = {c ∈ C : −c + A ∈ p ∩ q and − c + C ∈ r} .

Since q = q + p = q + q = q + r, we have that Â ∈ q. Since q = r + q, r = r + r, and p = r + p, we have that B̂ ∈ r. Since q = p + p = p + q and p = p + r, we have that Ĉ ∈ p. Next we claim that

if a ∈ Â, then −a + Â ∈ p ∩ r;
if b ∈ B̂, then −b + Ĉ ∈ p and −b + B̂ ∈ r; and
if c ∈ Ĉ, then −c + Â ∈ p and −c + Ĉ ∈ r.

We verify the second of these assertions, the other two being similar.

Let b ∈ B̂. Given x ∈ ℕ, x ∈ −b+Ĉ if and only if b+x ∈ C, −(b+x)+A ∈ p∩q, and −(b + x) + C ∈ r. That is

−b + Ĉ = −b + C ∩ {x : −x + (−b + A) ∈ p ∩ q} ∩ {x : −x + (−b + C) ∈ r} .

Now −b + C ∈ p. Also, −b + A ∈ q = p + q = p + p, so that

{x : −x + (−b + A) ∈ p ∩ q} ∈ p.

And −b + C ∈ p = p + r, so that {x : −x + (−b + C) ∈ r} ∈ p.

Similarly −b+B̂ = −b+B∩{x : −x+(−b+A) ∈ q}∩{x : −x+(−b+B) ∈ r}∩{x : −x + (−b + C) ∈ p}. We have that −b + B ∈ r. Also {x : −x + (−b + A) ∈ q} ∈ r because −b+A ∈ q = r+q; {x : −x+(−b+B) ∈ r} ∈ r because −b+B ∈ r = r+r; and {x : −x + (−b + C) ∈ p} ∈ r because −b + C ∈ p = r + p.

We now construct the sequences ⟨x_{n}⟩_{n=1}^{∞} and ⟨y_{n}⟩_{n=1}^{∞}. Choose x_{1} ∈ Ĉ. Then −x_{1} + Ĉ ∈ r so choose y_{1} ∈ B̂ ∩ (−x_{1} + Ĉ). Inductively, let m ∈ ℕ and assume that we have chosen ⟨x_{t}⟩_{t=1}^{m} and ⟨y_{t}⟩_{t=1}^{m} so that

(i) for each n ∈ {1, 2, …, m}, x_{n} ∈ Ĉ,

(ii) for each F ⊆ {1, 2, …, m} with |F | ≥ 2, ∑_{n∈F} x_{n} ∈ Â,
(iii) for ∅ ≠ G ⊆ {1, 2, …, m}, ∑_{t∈G} y_{t} ∈ B̂,

(iv) for each n ∈ {1, 2, …, m} and ∅ ≠ G ⊆ {1, 2, …, m}, x_{n} + ∑_{t∈G} y_{t} ∈ Ĉ,

(v) for ∅ ≠ F, G ⊆ {1, 2, …, m} with |F | ≥ 2, ∑_{t∈F} x_{t} + ∑_{t∈G} y_{t} ∈ Â.

All hypotheses are satisfied for m = 1, (ii) and (v) vacuously.

Now, given z ∈ F S(⟨x_{t}⟩_{t=1}^{m}) we have that either z ∈ Ĉ or z ∈ Â, and so −z +Â ∈ p. Given w ∈ F S(⟨y_{t}⟩_{t=1}^{m}), w ∈ B̂ so that −w + Ĉ ∈ p. Given z ∈ F S(⟨x_{t}⟩_{t=1}^{m}) and w ∈ F S(⟨y_{t}⟩_{t=1}^{m}), we have that either z + w ∈ Ĉ or z + w ∈ Â, and so −(z + w) + Â ∈ p. Thus we may choose

x_{m+1} ∈ Ĉ ∩ ⋂_{z∈F S(⟨x_{t}⟩_{t=1}^{m})}(−z + Â)
∩ ⋂_{w∈F S(⟨y_{t}⟩_{t=1}^{m})}(−w + Ĉ)
∩ ⋂_{z∈F S(⟨x_{t}⟩_{t=1}^{m})} ⋂_{w∈F S(⟨y_{t}⟩_{t=1}^{m})}(−(z + w) + Â) .

Given n ∈ {1, 2, …, m + 1}, we have x_{n} ∈ Ĉ, and so −x_{n} + Ĉ ∈ r. Given w ∈ F S(⟨y_{t}⟩_{t=1}^{m}), we have w ∈ B̂ and so −w + B̂ ∈ r. Given n ∈ {1, 2, …, m + 1} and w ∈ F S(⟨y_{t}⟩_{t=1}^{m}) we have that x_{n} + w ∈ Ĉ and so −(x_{n} + w) + Ĉ ∈ r. Given z ∈ F S_{≥2}(⟨x_{t}⟩_{t=1}^{m+1}) and w ∈ F S(⟨y_{t}⟩_{t=1}^{m}) we have that z + w ∈ Â and so −(z + w) + Â ∈ r. Thus we may choose

y_{m+1} ∈ B̂ ∩ ⋂_{n=1}^{m+1}(−x_{n} + Ĉ) ∩ ⋂_{w∈F S(⟨y_{t}⟩_{t=1}^{m})}(−w + B̂)
∩ ⋂_{n=1}^{m+1} ⋂_{w∈F S(⟨y_{t}⟩_{t=1}^{m})}(−(x_{n} + w) + Ĉ)
∩ ⋂_{z∈F S_{≥2}(⟨x_{t}⟩_{t=1}^{m+1})} ⋂_{w∈F S(⟨y_{t}⟩_{t=1}^{m})}(−(z + w) + Â) .

All induction hypotheses can be easily verified. □

The following is the strong Ramsey Theoretic property which we have discussed.

Corollary 3.3. Assume that there is a continuous homomorphism from βℕ to ℕ^{∗}. Then there exist disjoint subsets A, B, and C of ℕ such that, whenever F is a finite partition of A, G is a finite partition of B, and H is a finite partition of C, there exist F ∈ F, G ∈ G, and H ∈ H, and sequences ⟨x_{n}⟩_{n=1}^{∞} and ⟨y_{n}⟩_{n=1}^{∞} in ℕ such that

(1) F S(⟨y_{n}⟩_{n=1}^{∞}) ⊆ G, (2) for all n ∈ ℕ and all z ∈ F S(⟨y_{n}⟩_{n=1}^{∞}) ∪ {0}, x_{n} + z ∈ H (and in particular

{x_{n} : n ∈ ℕ} ⊆ H), and

(3) for all w ∈ F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) and all z ∈ F S(⟨y_{n}⟩_{n=1}^{∞}) ∪ {0}, w + z ∈ F (and in particular F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) ⊆ F).

Proof. Assume that there is a continuous homomorphism from βℕ to ℕ^{∗}. Then by [10, Corollary 10.20] and Theorem 2.2, we may pick distinct p, q, and r in ℕ^{∗} such that p + p = q = q + q = q + p = p + q, r + r = r, r + p = p + r = p, and q + r = r + q = q. Pick pairwise disjoint A ∈ q, B ∈ r, and C ∈ p. Let F be a finite partition of A, let G be a finite partition of B, and let H be a finite partition of C. Pick F ∈ F, G ∈ G, and H ∈ H such that F ∈ q, G ∈ r, and H ∈ p. Apply Theorem 3.2. □

We now consider a much simpler consequence of the statement in Corollary 3.3.

Definitions 3.4. For A ⊆ ℕ, let Ψ(A) be the statement: “For each k ∈ ℕ, whenever A is k-colored, there exists an increasing sequence ⟨x_{n}⟩_{n=1}^{∞} in ℕ\A such that F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) is monochrome.”

Notice that any set A satisfying Ψ is automatically an IP set. That is, there is a sequence ⟨y_{n}⟩_{n=1}^{∞} such that F S(⟨y_{n}⟩_{n=1}^{∞}) ⊆ A. To see this note that, given any sequence ⟨x_{n}⟩_{n=1}^{∞}, if y_{n} = x_{2n} + x_{2n+1}, then F S(⟨y_{n}⟩_{n=1}^{∞}) ⊆ F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}).

Corollary 3.5. If there exist distinct p and q in ℕ^{∗} such that q = p + p = p + q = q + p = q + q, then there is a set A ⊆ ℕ such that Ψ(A).

Proof. This is an immediate consequence of Corollary 3.3 and [10, Corollary 10.20]. □

One could define a statement Γ(A) to be the statement: “For each k ∈ ℕ, whenever A and ℕ\A are k-colored, there exists a monochrome increasing sequence ⟨x_{n}⟩_{n=1}^{∞} in ℕ\A such that F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) is monochrome.” The existence of a set A satisfying Γ also follows immediately from Corollary 3.3. However, this is not really a stronger conclusion, because Γ(A) follows trivially from Ψ(A) by applying the pigeon hole principle.

We have already noted that a point p ∈ ℕ^{∗} is an idempotent if and only if there is a sequence ⟨x_{n}⟩_{n=1}^{∞} such that F S(⟨x_{n}⟩_{n=1}^{∞}) ∈ p. We doubt that the existence of a set A satisfying Ψ can be shown to imply that there exist p, q ∈ βℕ such that A ∈ q, ℕ\A ∈ p, and p + p = q = q + q = p + q = q + p in any way short of proving that no such set A exists. We do have the following partial converse to Corollary 3.5.

Lemma 3.6. Let A ⊆ ℕ. If Ψ(A), then there exists r ∈ \overline{A} with the property that for every B ∈ r, there exist p ∈ ℕ^{∗}\\overline{A} and q = q + q ∈ \overline{B} such that, whenever k ≥ 2 and u_{1}, u_{2}, …, u_{k} ∈ \{p, q\}, one has u_{1} + u_{2} + … + u_{k} ∈ \overline{B}.

Proof. Let B = {B ⊆ A : there is an increasing sequence ⟨x_{n}⟩_{n=1}^{∞} in ℕ\A such that F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) ⊆ B}. Since Ψ(A), we have that whenever F is a finite partition of A, one must have F ∩ B ≠ ∅. Thus, by [10, Theorem 5.7], there exists r ∈ \overline{A} with B ⊆ r. Let B ∈ r and pick an increasing sequence ⟨x_{n}⟩_{n=1}^{∞} in ℕ\A such that F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) ⊆ B}.

By [10, Theorem 4.20], ⋂_{m=1}^{∞} \overline{F S_{≥2}(⟨x_{n}⟩_{n=m}^{∞})} is a subsemigroup of βℕ so pick by [10, Theorem 2.5] an idempotent q ∈ ⋂_{m=1}^{∞} \overline{F S_{≥2}(⟨x_{n}⟩_{n=m}^{∞})}. Pick p ∈ ℕ^{∗} with {x_{n} : n ∈ ℕ} ∈ p.

To complete the proof it suffices to show (1) F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) ∈ p + p and

(2) if u ∈ βℕ and F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) ∈ u, then F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) ∈ u + p and

F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) ∈ u + q.

To establish (1), we show that

{x_{n} : n ∈ ℕ} ⊆ {y ∈ ℕ : −y + F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) ∈ p}.

Let m ∈ ℕ. Then {x_{n} : n ∈ ℕ and n > m} ⊆ −y + F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}).

To establish (2), assume that F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) ∈ u. We show that

\begin{matrix}F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) ⊆ \{y ∈ ℕ : −y + F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) ∈ p\} and \\ F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) ⊆ \{y ∈ ℕ : −y + F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) ∈ q\} . \end{matrix}

So let y ∈ F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) and pick F ∈ P_{f}(ℕ) with |F | > 1 such that y = ∑_{n∈F} x_{n}. Let m = max F. Then {x_{n} : n ∈ ℕ and n > m} ⊆ −y + F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) and F S_{≥2}(⟨x_{n}⟩_{n=m+1}^{∞}) ⊆ −y + F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}). □

Some of us would conjecture strongly that no set A ⊆ ℕ satisfying Ψ(A) exists. (At least one author disagrees.) In fact, we shall introduce a property Θ weaker than Ψ. We do not even know of a set A ⊆ ℕ for which Θ holds. We shall give several examples of sets A for which Θ fails. These are, of course, examples for which Ψ fails as well.

Definitions 3.7. For each A ⊆ ℕ, Θ(A) is the statement: “For every finite coloring of A, there exists an infinite sequence ⟨x_{n}⟩_{n=1}^{∞} in ℕ\A such that F S_{2}(⟨x_{n}⟩_{n=1}^{∞}) ∪ F S_{3}(⟨x_{n}⟩_{n=1}^{∞}) is monochrome.”

Theorem 3.8. Let ⟨a_{n}⟩_{n=1}^{∞} be an increasing sequence in ℕ such that lim_{n→∞}(a_{n+1} − a_{n}) = ∞ and let A = ℕ\{a_{n} : n ∈ ℕ}. Then ¬Θ(A). (In fact there is a counterexample using two colors.)

Proof. Let B = {a_{m} + a_{n} : m < n and a_{n+1} − a_{n} > a_{m}} and let C = {a_{r} + a_{s} + a_{t} : r < s < t , a_{s+1} − a_{s} > a_{r}, and a_{t+1} − a_{t} > a_{r} + a_{s}}. We claim that B ∩C = ∅. To see this, suppose that a_{m} +a_{n} = a_{r} +a_{s} +a_{t}, where a_{n+1} −a_{n} > a_{m}, a_{s+1} − a_{s} > a_{r} and a_{t+1} − a_{t} > a_{r} + a_{s}. Then a_{n} = a_{t}, because n > t implies that a_{n} − a_{t} ≥ a_{t+1} − a_{t} > a_{r} + a_{s}, and t > n implies that a_{t} − a_{n} ≥ a_{n+1} − a_{n} > a_{m}. So a_{m} = a_{r} +a_{s} and thus m > s. Therefore a_{m} −a_{s} ≥ a_{s+1} −a_{s} > a_{r}, a contradiction.

In a similar fashion, one can show that (B ∪ C) ⊆ A. Suppose that one has an infinite sequence ⟨x_{n}⟩_{n=1}^{∞} in ℕ\A such that either F S_{2}(⟨x_{n}⟩_{n=1}^{∞}) ∪ F S_{3}(⟨x_{n}⟩_{n=1}^{∞}) ⊆ B or F S_{2}(⟨x_{n}⟩_{n=1}^{∞}) ∪ F S_{3}(⟨x_{n}⟩_{n=1}^{∞}) ⊆ A\B. Since F S_{2}(⟨x_{n}⟩_{n=1}^{∞}) ∩ B ≠ ∅ and F S_{3}(⟨x_{n}⟩_{n=1}^{∞}) ∩ C ≠ ∅, we have a contradiction. □

In the following theorem, we give another simple example of a family of sets A for which Θ(A) fails.

Theorem 3.9. Let B ⊆ ℕ be an infinite set with the property that, for some k ∈ ℕ, either kℕ ∩ B is finite or kℕ\B is finite. If A = ℕ\B, then Θ(A) fails.

Proof. For each i ∈ {0, 1, 2, ⋯, k − 1}, let A_{i} = {a ∈ A : a ≡ i(mod k)}. Suppose that there is an infinite sequence ⟨x_{n}⟩_{n=1}^{∞} in B and i ∈ {0, 1, 2, ⋯, k − 1} for which F S_{2}(⟨x_{n}⟩_{n=1}^{∞}) ∪ F S_{3}(⟨x_{n}⟩_{n=1}^{∞}) ⊆ A_{i}. We may suppose that there exists j ∈ {0, 1, 2, ⋯, k −1} such that x_{n} ≡ j(mod k) for every n ∈ ℕ, because this could be achieved by replacing ⟨x_{n}⟩_{n=1}^{∞} by a subsequence. Note that j ≠ 0. (If j = 0, then {x_{n} : n ∈ ℕ} ⊆ kℕ and F S_{2}(⟨x_{n}⟩_{n=1}^{∞}) ⊆ kℕ.) Then F S_{2}(⟨x_{n}⟩_{n=1}^{∞}) ⊆ {a ∈ A : a ≡ 2j(mod k)} and F S_{3}(⟨x_{n}⟩_{n=1}^{∞}) ⊆ {a ∈ A : a ≡ 3j(mod k)}. This is a contradiction, because 2j ≢ 3j(mod k). □

Another natural candidate for a set satisfying Ψ is based on spectra of numbers. These are sets of the form {⌊nα + γ⌋ : n ∈ ℕ}, where α is a positive real number, usually irrational, and 0 ≤ γ ≤ 1. These sets have been much studied. See for example [2, 3, 4, 6, 13, 14].

For large irrational α, the set ℕ\{⌊nα⌋ : n ∈ ℕ} seems as though it might satisfy the statement Ψ. If 0 < γ < 1, it is immediate that ℕ\{⌊nα + γ⌋ : n ∈ ℕ} does not satisfy Ψ. In fact, {⌊nα + γ⌋ : n ∈ ℕ} is an IP* set ([3, Theorem 6.1] or see [10, Theorem 16.42]). That is, for any sequence ⟨x_{n}⟩_{n=1}^{∞}, F S(⟨x_{n}⟩_{n=1}^{∞}) ∩ {⌊nα + γ⌋ : n ∈ ℕ} ≠ ∅. On the other hand [3, Theorem 6.2], for irrational α > 1, the sets {⌊nα⌋ : n ∈ ℕ} and {⌊nα + 1⌋ : n ∈ ℕ} are disjoint and each contain sets of the form F S(⟨x_{n}⟩_{n=1}^{∞}) so neither is an IP* set. (In fact, both of these sets are central. For a description of some of the properties of central sets see [10, Chapter 14].)

Theorem 3.10. Let α be a positive real number and either let A = ℕ\{⌊nα⌋ : n ∈ ℕ} or let A = ℕ\{⌊nα + 1⌋ : n ∈ ℕ}. Then ¬Θ(A).

Proof. We do the proof for the case A = ℕ\{⌊nα⌋ : n ∈ ℕ}. (The other case can be done in a similar way by using the mapping m ↦ m−max{nα : n ∈ ω and nα ≤ m}.) Notice that if α ≤ 1, then A = ∅ so we may assume that α > 1.

For each m ∈ ℕ, let f(m) = min{nα : n ∈ ℕ and nα ≥ m} − m. Notice that m ∈ A if and only if f(m) ≥ 1.

Let ϵ = min \{\frac{1}{8}, \frac{α−1}{3}\}. Since [0, α] is covered by a finite number of intervals of length ϵ, Θ(A) implies that there is an interval I of length ϵ and an infinite sequence ⟨x_{n}⟩_{n=1}^{∞} in ℕ\A such that F S_{2}(⟨x_{n}⟩_{n=1}^{∞}) ∪ F S_{3}(⟨x_{n}⟩_{n=1}^{∞}) ⊆ f^{−1}[I] ∩ A. Choose β ∈ I.

We may suppose that ⟨f(x_{n})⟩_{n=1}^{∞} converges to a limit γ and that |f(x_{n}) − γ| < ϵ for every n ∈ ℕ, because we can achieve this by replacing ⟨x_{n}⟩_{n=1}^{∞} by a subsequence. Note that γ ≤ 1 since each x_{n} ∉ A.

For any m, n, r ∈ ℕ, with m < n < r, each of x_{m} + γ, x_{n} + x_{r} + β and x_{m} +x_{n} +x_{r} +β is within ϵ of a number in ℕα. It follows that |γ −tα| < 3ϵ for some t ∈ ℤ. If t < 0, then γ −tα ≥ α > ϵ. If t > 0, we have |tα−γ| = tα−γ ≥ α−1 ≥ 3ϵ. Thus t = 0 and hence |γ| < 3ϵ.

Thus we have x_{m} ≤ kα < x_{m}+γ+ϵ < x_{m}+4ϵ and x_{n} ≤ lα < x_{n}+γ+ϵ < x_{n}+4ϵ for some k, l ∈ ℕ. So x_{m} + x_{n} ≤ (k + l)α < x_{m} + x_{n} + 8ϵ ≤ x_{m} + x_{n} + 1 and thus x_{m} + x_{n} ∉ A, a contradiction. □

4. A Finitary Ramsey Theoretic Approximation

We have seen that the existence of distinct p and q in ℕ^{∗} satisfying the equations p + p = q = q + q = p + q = q + p (equivalently the existence of a nontrivial continuous homomorphism from βℕ into ℕ^{∗}) implies the existence of a set A ⊆ ℕ such that whenever A is finitely colored, there must exist an increasing sequence ⟨x_{n}⟩_{n=1}^{∞} in ℕ\A such that F S_{≥2}(⟨x_{n}⟩_{n=1}^{∞}) is monochrome. We have not been able to show that no such set exists, and certainly have not been able to produce one.

In this section we produce a set C satisfying the weaker conclusion that whenever it is finitely colored, there exist arbitrarily large finite sequences in ℕ\C with all sums of the form ∑_{t∈F} x_{t} with |F | > 1 monochrome. We remark that the existence of such a set follows from Prömel’s Induced Graham-Rothschild theorem [11]. However, the proof of Prömel’s result is rather long and difficult, so we include here a relatively short proof of our result.

We shall use the Hales-Jewett Theorem. Given a finite alphabet A, a variable word is a word over the alphabet A ∪ {v} in which v occurs, where v is a “variable” which is not a member of A. Given a variable word w and a letter a ∈ A, the word w(a) is the result of replacing each occurrence of v by a.

Theorem 4.1 (Hales-Jewett). Let k, m ∈ ℕ. There exists some d ∈ ℕ such that, whenever A is an alphabet with m letters and the length d words over A are kcolored, there exists a variable word w of length d such that {w(a) : a ∈ A} is monochrome.

Proof. [8]. Or see [7, Section 2.2] or [10, Section 14.2]. □

Corollary 4.2. Let k, m ∈ ℕ\{1}. There is some d ∈ ℕ such that, whenever A is an alphabet with m letters and the length d words over A are k-colored, there exists a variable word w = l_{0}l_{1} … l_{d−1} with each l_{i} ∈ A ∪ {v} so that:

(1) there exist i ≠ j such that l_{i}, l_{j} ∈ A and l_{i} ≠ l_{j} and

(2) {w(a) : a ∈ A} is monochrome.

Proof. Pick d as guaranteed by the Hales-Jewett Theorem for an alphabet of size m and k + m colors. Assume without loss of generality that A = {1, 2, …, m}. Let ϕ : A^{d} → {1, 2, …, k} and define γ : A^{d} → {1, 2, …, k + m} by γ(w) = ϕ(w) unless w is constant and γ(ii … i) = k + i. Pick a variable word w such that γ is constant on {w(i) : i ∈ A}. □

We let k ∈ ℕ be fixed throughout the remainder of this section. We inductively define for each m ∈ ℕ numbers d_{m} and e_{m} and sets A_{m}, B_{m}, and C_{m} as follows.

d_{1} = e_{1} = 1, A_{1} = B_{1} = {1}, C_{1} = ∅ (or anything else – C_{1} is not used). d_{2} = e_{2} = 2, A_{2} = {1, 2, 3}, and B_{2} = C_{2} = {3}. (Or, thinking in binary,

as is appropriate, A_{2} = {01, 10, 11} and B_{2} = C_{2} = {11}.)

Inductively, assume m ≥ 3 and we have defined numbers d_{m−1} and e_{m−1} and sets A_{m−1}, B_{m−1}, and C_{m−1}. Pick by Corollary 4.2, a number d_{m} so that whenever the length d_{m} words over the alphabet A_{m−1} are k-colored there is a variable word w(v) = l_{0}l_{1} … l_{d_{m}−1} (where each l_{i} ∈ A_{m−1} ∪ {v}) such that

(1) there exist i, j ∈ {0, 1, …, d_{m} − 1} with l_{i}, l_{j} ∈ A_{m−1} and l_{i} ≠ l_{j} and

(2) {w(a) : a ∈ A_{m−1}} is monochrome.

Let e_{m} = d_{m} · e_{m−1} and let

A_{m} = {1, 2, …, 2^{e_{m}} − 1} (= {∑_{t∈F} 2^{t} : ∅ ≠ F ⊆ {0, 1, …, e_{m} − 1}}) .

Let

B_{m} = {∑_{i=0}^{d_{m}−1} a_{i} · 2^{i·e_{m−1}} : each a_{i} ∈ A_{m−1}}
= {∑_{t∈F} 2^{t} : F ⊆ {0, 1, …, e_{m} − 1} and for each i ∈ {0, 1, …, d_{m} − 1},
F ∩ {i · e_{m−1}, i · e_{m−1} + 1, …, (i + 1) · e_{m−1} − 1} ≠ ∅}.

Let

C_{m} = B_{m} ∪ {w · ∑_{i∈F} 2^{i·e_{m−1}} : w ∈ C_{m−1} and ∅ ≠ F ⊊ {0, 1, …, d_{m} − 1}}.

For sufficiently large m, the set C_{m} will be our desired set, so let us describe how we can recognize members of C_{m}. We do this by induction, so we assume that when a number is written in binary, you can recognize the members of C_{m−1}. Let a number x be given. Since C_{m} ⊆ A_{m}, if x ∉ A_{m} we know x ∉ C_{m}. Thus assume that x ∈ A_{m} so x = ∑_{t∈F} 2^{t} for some F ⊆ {0, 1, …, e_{m} − 1}. That is the length of the binary expansion of x is at most e_{m} which we view as d_{m} blocks of length e_{m−1}. If there is a 1 in each such block, that is if for each i ∈ {0, 1, …, d_{m} − 1},

F ∩ {i · e_{m−1}, i · e_{m−1} + 1, …, (i + 1) · e_{m−1} − 1} ≠ ∅ ,

then x ∈ B_{m} so x ∈ C_{m}. So assume at least one such block has all 0’s. On the other hand, x ≠ 0 so at least one such block has a 1. If two non-zero blocks look different, then we know x ∉ C_{m}. So assume all non-zero blocks are the same and let G be the set of non-zero blocks. Then there is some w ∈ A_{m−1} such that x = w · ∑_{i∈G} 2^{i·e_{m−1}}. If w ∈ C_{m−1}, then x ∈ C_{m} and if w ∉ C_{m−1}, then x ∉ C_{m}.

Lemma 4.3. Let m ∈ ℕ with m ≥ 2 and let ψ : C_{m} → {1, 2, …, k}. Then there exist x_{1}, x_{2}, …, x_{m} in A_{m}\C_{m} and φ : {2, 3, …, m} → {1, 2, …, k} such that whenever G ⊆ {1, 2, …, m} and |G| > 1, one has ∑_{t∈G} x_{t} ∈ C_{m} and ψ(∑_{t∈G} x_{t}) = φ(max G).

Proof. We proceed by induction, so first assume m = 2. Let x_{1} = 1, x_{2} = 2, and let φ(2) = ψ(3).

Now assume m > 2 and the lemma is valid for m − 1. Let

ψ : C_{m} → {1, 2, …, k} .

Define a k-coloring γ of the length d_{m} words over A_{m−1} as follows. Given u = l_{0}l_{1} … l_{d_{m}−1} with each l_{i} ∈ A_{m−1}, let γ(u) = ψ(∑_{i=0}^{d_{m}−1} l_{i} · 2^{i·e_{m−1}}).

By the choice of d_{m}, pick a variable word w(v) = l_{0}l_{1} … l_{d_{m}−1} and r ∈ {1, 2, …, k} such that there exist i, j ∈ {0, 1, …, d_{m} − 1} with l_{i}, l_{j} ∈ A_{m−1} and l_{i} ≠ l_{j} and for each a ∈ A_{m−1}, γ(w(a)) = r. Define φ(m) = r.

Let F = {i ∈ {0, 1, …, d_{m} − 1} : l_{i} = v}. Let x_{m} be the member of A_{m} corresponding to w(0). That is, x_{m} = ∑_{i∈{0,1,...,d_{m}−1}\F} l_{i} · 2^{i·e_{m−1}}. We claim that x_{m} ∉ C_{m}. Indeed pick i, j ∈ {0, 1, …, d_{m} − 1} with l_{i}, l_{j} ∈ A_{m−1} and l_{i} ≠ l_{j}. Since x_{m} has some blocks of 0’s (corresponding to elements of F) we have x_{m} ∉ B_{m}. Since l_{i} ≠ l_{j}, we have x_{m} ≠ b · ∑_{i∈G} 2^{i·e_{m−1}} for any b ∈ C_{m−1} and any G ⊆ {0, 1, …, d_{m} − 1}.

Now define a k-coloring μ of C_{m−1} by letting μ(y) = ψ(y · ∑_{i∈F} 2^{i·e_{m−1}}). By the induction hypothesis, pick y_{1}, y_{2}, …, y_{m−1} ∈ A_{m−1}\C_{m−1} and

δ : {2, 3, …, m − 1} → {1, 2, …, k}

such that whenever G ⊆ {1, 2, …, m − 1} and |G| > 1, ∑_{t∈G} y_{t} ∈ C_{m−1} and μ(∑_{t∈G} y_{t}) = δ(max G). For t ∈ {2, 3, …, m − 1}, let φ(t) = δ(t). For t ∈ {1, 2, …, m − 1}, let x_{t} = y_{t} · ∑_{i∈F} 2^{i·e_{m−1}}.

We claim that for each t ∈ {2, 3, …, m − 1}, x_{t} ∉ C_{m}. Indeed, since F ≠ {0, 1, …, d_{m} − 1} we have x_{t} ∉ B_{m} and since y_{t} ∉ C_{m−1}, we have x_{t} ≠ b · ∑_{i∈G} 2^{i·e_{m−1}} for any b ∈ C_{m−1} and any G ⊆ {0, 1, …, d_{m} − 1}.

Now let G ⊆ {1, 2, …, m} with |G| > 1 and let p = max G. Assume first that p < m. Then we have that ∑_{t∈G} y_{t} ∈ C_{m−1} and μ(∑_{t∈G} y_{t}) = δ(p) = φ(p). Thus (∑_{t∈G} y_{t})·(∑_{i∈F} 2^{i·e_{m−1}}) ∈ C_{m} and ψ((∑_{t∈G} y_{t})·(∑_{i∈F} 2^{i·e_{m−1}})) = μ(∑_{t∈G} y_{t}) = φ(p). Since

(∑_{t∈G} y_{t}) · (∑_{i∈F} 2^{i·e_{m−1}}) = ∑_{t∈G}(y_{t} · ∑_{i∈F} 2^{i·e_{m−1}})

= ∑_{t∈G} x_{t} ,

we have ψ(∑_{t∈G} x_{t}) = φ(p) as required.

Finally, assume max G = m. Let H = G\{m}. Let z = ∑_{t∈H} y_{t} and note that z ∈ A_{m−1}. (This is immediate if |H| = 1 and if |H| > 1, then z ∈ C_{m−1} ⊆ A_{m−1}.) Now

∑_{t∈G} x_{t} = x_{m} + ∑_{t∈H} x_{t}

= x_{m} + ∑_{t∈H}(y_{t} · ∑_{i∈F} 2^{i·e_{m−1}})

= x_{m} + (∑_{t∈H} y_{t}) · (∑_{i∈F} 2^{i·e_{m−1}})

= x_{m} + z · ∑_{i∈F} 2^{i·e_{m−1}} .

Let w(z) = u_{0}u_{1} … u_{d_{m}−1}, where, recall, w(v) = l_{0}l_{1} … l_{d_{m}−1}. Then

u_{i} = \begin{cases}l_{i} & if i ∉ F \\ z & if i ∈ F . \end{cases}

So

γ(w(z)) = ψ( ∑_{i=0}^{d_{m}−1} u_{i} · 2^{i·e_{m−1}})

= ψ( ∑_{i∈{0,1,...,d_{m}−1}\F} l_{i} · 2^{i·e_{m−1}} + ∑_{i∈F} z · 2^{i·e_{m−1}})

= ψ(x_{m} + z · ∑_{i∈F} 2^{i·e_{m−1}})

= ψ(∑_{t∈G} x_{t}) .

Thus ψ(∑_{t∈G} x_{t}) = γ(w(z)) = φ(m). □

Theorem 4.4. For each n ∈ ℕ there exists m ∈ ℕ such that whenever C_{m} is k-colored, there exist z_{1}, z_{2}, …, z_{n} in ℕ\C_{m} such that

{∑_{t∈F} z_{t} : F ⊆ {1, 2, …, n} and |F | > 1}

is contained in C_{m} and is monochrome.

Proof. Let m = (n−2)·k+2. Given a k-coloring ψ of C_{m} pick x_{1}, x_{2}, …, x_{m} and φ as guaranteed by Lemma 4.3. By the pigeon hole principle, pick G ⊆ {2, 3, …, m} with |G| = n − 1 and φ(i) = φ(j) for all i, j ∈ G. Let z_{1} = x_{1} and let z_{2}, z_{3}, …, z_{n} enumerate {x_{i} : i ∈ G}. □

References

[1] J. Baker, N. Hindman, and J. Pym, Elements of finite order in Stone-Čech compactifications, Proc. Edinburgh Math. Soc. 36 (1993), 49–54, MR 93m:22003, Zbl 811.22002.

[2] T. Bang, On the sequence [nα], n = 1, 2, …, Math. Scand. 5 (1957), 69–76, MR 19,1159h, Zbl 084.04401.

[3] V. Bergelson, N. Hindman, and B. Kra, Iterated spectra of numbers—elementary, dynamical, and algebraic approaches, Trans. Amer. Math. Soc. 348 (1996), 893–912, MR 97b:03058, Zbl 855.05098.

[4] M. Boshernitzan and A. Fraenkel, Nonhomogeneous spectra of numbers, Discrete Math. 34 (1981), 325–327, MR 82d:10077, Zbl 456.10005.

[5] E. van Douwen, The Čech-Stone compactification of a discrete groupoid, Topology and Appl. 39 (1991), 43–60, MR 92g:54026 Zbl 758.54011.

[6] R. Graham, S. Lin, and C. Lin, Spectra of numbers, Math. Mag. 51 (1978), 174–176, MR 58 #10808, Zbl 391.10003.

[7] R. Graham, B. Rothschild, and J. Spencer, Ramsey Theory, Wiley, New York, 1990, MR 90m:05003, Zbl 705.05061.

[8] A. Hales and R. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222–229, MR 26 #1265, Zbl 113.14802.

[9] N. Hindman and D. Strauss, Prime properties of the smallest ideal of βℕ, Semigroup Forum 52 (1996), 357–364, MR 97c:54033, Zbl 867.22002.

[10] N. Hindman and D. Strauss, Algebra in the Stone-Čech Compactification—Theory and Applications, Walter de Gruyter, Berlin, 1998, MR 99j:54001, Zbl 918.22001.

[11] H. Prömel, Induced partition properties of combinatorial cubes, J. Comb. Theory (Series A) 39 (1985), 177–208, MR 87g:05017 Zbl 638.05005.

[12] I. Protasov, J. Pym and D. Strauss, A lemma on extending functions into F-spaces and homomorphisms between Stone-Čech remainders, Topology and its Applications, to appear.

[13] T. Skolem, On certain distributions of integers in pairs with given differences, Math. Scand. 5 (1957), 57–68, MR 19,1159g, Zbl 084.04304.

[14] T. Skolem, Über einige Eigenschaften der Zahlenmengen [αn + β] bei irrationalem α mit einleitenden Bemerkungen über einige kombinatorische probleme, Norske Vid. Selsk. Forh. 30 (1957), 42–49, MR 19,1159i, Zbl 084.04402.

[15] D. Strauss, ℕ^{∗} does not contain an algebraic and topological copy of βℕ, J. London Math. Soc. 46 (1992), 463–470, MR 93k:22002, Zbl 788.54045.

[16] E. Zelenuk, Finite groups in βℕ are trivial (Russian), Ukranian National Academy of Sciences Institute of Mathematics, Preprint 96.3 (1996).

86 Davenport, Hindman, Leader, and Strauss

Department of Mathematics, Miami University, Oxford, OH 45056, USA davenpde@casmail.muohio.edu

Department of Mathematics, Howard University, Washington, DC 20059, USA nhindman@howard.edu, nhindman@aol.com, http://members.aol.com/nhindman/

Department of Mathematics, University College London, London WC1E6BT, UK i.leader@ucl.ac.uk

Department of Pure Mathematics, University of Hull, Hull HU6 7RX, UK d.strauss@maths.hull.ac.uk

This paper is available via http://nyjm.albany.edu:8000/j/2000/6-4.html.