LINEAR EQUATIONS IN THE STONE-ČECH COMPACTIFICATION OF ℕ

Neil Hindman

Department of Mathematics, Howard University, Washington, D.C. 20059, U.S.A.

                              nhindman@howard.edu

Amir Maleki

Department of Mathematics, Howard University, Washington, D.C. 20059, U.S.A.

                               amaleki@howard.edu

Dona Strauss

Department of Pure Mathematics, University of Hull, Hull HU6 7RX, U.K.

                           d.strauss@maths.hull.ac.uk

Received: 5/7/99, Revised: 12/7/99, Accepted: 12/14/99, Published: 5/19/00

Abstract

Let a and b be distinct positive integers. We show that the equation u + a · p = v + b · p has no solutions with u, v ∈ βℕ and p ∈ βℕ\ℕ. More generally, we show that if (S, +) is any commutative cancellative semigroup and S has no nontrivial solutions to n · s = n · t for n ∈ ℕ and s, t ∈ S, then the equation u + a · p = v + b · p has no solutions with u, v ∈ βS and p ∈ βS\S. We characterize completely the Abelian groups for which such an equation can be satisfied. We also show that if S can be embedded in the circle group 𝕋, then the equation a · p + u = b · p + v has no solutions with u, v ∈ βS and p ∈ βS\S. Finally, we investigate solutions to the equation a_{1} · p + a_{2} · p + … + a_{n} · p = b_{1} · p + b_{2} · p + … + b_{m} · p where p ∈ βℕ\ℕ and a_{1}, a_{2}, …, a_{n}, b_{1}, b_{2}, …, b_{m} ∈ ℕ.

1. Introduction

Given any discrete semigroup (S, +) there is a unique extension of the operation in S to its Stone-Čech compactification βS making βS a right topological semigroup with S contained in its topological center. (That is, for each p ∈ βS, the function ρ_{p} : βS → βS defined by ρ_{p}(q) = q + p is continuous. And for each s ∈ S, the function λ_{s} : βS → βS defined by λ_{s}(p) = s + p is continuous.) We are denoting the operation by + because we shall be concerned in this paper almost exclusively with commutative semigroups S. In fact, we are primarily concerned with the semigroup (ℕ, +). However, the reader should be cautioned that βS is hardly ever commutative. (See [5, Theorem 4.27].) (We are writing ℕ for the set of positive integers and write ω = ℕ ∪ {0}.)

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 0 (2000), #A02 2

For almost 25 years, the algebra of βℕ has been a powerful tool in Ramsey Theory, beginning with the Galvin-Glazer proof of the Finite Sums Theorem. (See the notes to Chapter 5 of [5] for a discussion of the history of this proof.) Conversely, the fact that there is a finite partition of ℕ with the property that no cell contains a sequence with all of its pairwise (distinct) sums and all of its pairwise (distinct) products shows that the equation p + p = p · p has no solutions in βℕ. The fact that there is an idempotent p of (βℕ, ·) in the topological closure of {q ∈ βℕ : q+q = q} provided the first [4], and for fifteen years the only, proof of the following fact: Let r ∈ ℕ and let ℕ = ⋃_{i=1}^{r} A_{i}. Then there exist i ∈ {1, 2, …, r} and sequences ⟨x_{n}⟩_{n−1}^{∞} and ⟨y_{n}⟩_{n−1}^{∞} in ℕ such that F S(⟨x_{n}⟩_{n−1}^{∞}) ∪ F P (⟨y_{n}⟩_{n−1}^{∞}) ⊆ A_{i} where F S(⟨x_{n}⟩_{n−1}^{∞}) = {∑_{n∈F} x_{n} : F is a finite nonempty subset of ℕ} and F P (⟨y_{n}⟩_{n−1}^{∞}) = {∏_{n∈F} y_{n} : F is a finite nonempty subset of ℕ}. An elementary proof of this fact was eventually provided in [1].

Other results, equally easy when done in terms of βℕ, seem unlikely to be provided with elementary proofs any time soon. For example, {p ∈ βℕ : every A ∈ p has positive upper density} is a compact subsemigroup of (βℕ, +), and consequently has an idempotent. Therefore, whenever ℕ is finitely colored, one may inductively choose a sequence ⟨x_{t}⟩_{t=1}^{∞}, with F S(⟨x_{t}⟩_{t=1}^{∞}) monochrome, in such a way that, having chosen ⟨x_{t}⟩_{t=1}^{n}, the set of choices for x_{n+1} has positive upper density.

An alternative description of this result in the terminology of game theory was suggested to us recently by Tomasz Łuczak. At the start of the game, ℕ is finitely colored. At the n^{th} turn, player one chooses a subset A_{n} of ℕ with positive upper density and player two chooses any element x_{n} ∈ A_{n}. Player one wins provided F S(⟨x_{n}⟩_{n−1}^{∞}) is monochrome. The theorem says that player one has a winning strategy.

See Part III of [5] for numerous other examples of the applications of the algebra of βℕ to combinatorics, specifically Ramsey Theory.

In this paper, much of the interaction between algebra and Ramsey Theory occurs in the reverse direction. That is, we use combinatorial results involving partitions of ℕ, ℝ, or 𝕋 to conclude that certain equations in βℕ cannot be solved.

We take the points of βS to be the ultrafilters on S and identify the principal ultrafilters with the points of S. The topology of βS is defined by choosing the sets of the form \overline{A} = \{p ∈ βS : A ∈ p\}, where A ⊆ S, as a base for the open sets. The set \overline{A} is clopen in this topology and is equal to cl_{βS}(A). Given p, q ∈ βS and A ⊆ S, one has that A ∈ p + q if and only if {x ∈ S : −x + A ∈ q} ∈ p, where −x + A = {s ∈ S : x + s ∈ A}. Alternatively, p + q can be defined topologically as lim_{\begin{matrix}s→p \\ s∈S \end{matrix}} lim_{\begin{matrix}t→q \\ t∈S \end{matrix}}(s + t).

The following fact is easy to verify. Suppose that p, q ∈ βS, that P ∈ p and that Q_{s} ∈ q for each s ∈ P. Then ⋃_{s∈P} (s + Q_{s}) ∈ p + q. We shall use this fact several times.

See [5] for an elementary introduction to the properties of the semigroup βS, as well as for any unfamiliar algebraic assertions encountered here.

If X is a completely regular space, any function f from S to X, has a continuous extension mapping βS to βX, which we shall denote by f̃.

In this paper, we investigate solutions to certain “linear” equations. Before we talk about these, we need to clarify what we mean, for example, by 2·p where p ∈ βS\S. (We do not mean p + p.) We take our motivation from the situation in βℕ. Here 2 · p is naturally interpreted as multiplication in the semigroup (βℕ, ·). It is defined to be l̃_{2}(p) where l̃_{2} : βℕ → βℕ is the continuous extension of l_{2} : ℕ → ℕ defined by l_{2}(x) = 2 · x. It is characterized by the fact that for any A ⊆ ℕ, A ∈ 2 · p if and only if 2^{−1}A ∈ p where 2^{−1}A = {x ∈ ℕ : 2 · x ∈ A}. We take a similar approach in an arbitrary semigroup.

Definition 1.1. Let (S, +) be a semigroup and let a ∈ ℕ. Define l_{a} : S → S by l_{a}(s) = s + s + … + s (a times) and let l̃_{a} : βS → βS be the continuous extension of l_{a}. For p ∈ βS define a · p = l̃_{a}(p).

Note that if p ∈ S then, as usual, a · p is the sum of p with itself a times.

It is immediate from the definition that a · p = lim_{\begin{matrix}s→p \\ s∈S \end{matrix}} a · s.

Lemma 1.2. Let (S, +) be a semigroup, let a ∈ ℕ, let p ∈ βS, and let A ⊆ S. Then A ∈ a · p if and only if a^{−1}A ∈ p, where a^{−1}A = {x ∈ S : a · x ∈ A}. In particular, if B ∈ p, then a · B ∈ a · p.

Proof. Necessity. We have that \overline{A} is a neighborhood of l̃_{a}(p) so pick B ∈ p such that l̃_{a}[\overline{B}] ⊆ \overline{A}. Then B ⊆ a^{−1}A.

Sufficiency. Suppose that A ∉ a · p. Then S\A ∈ a · p and so, by the sufficiency applied to S\A, a^{−1}(S\A) ∈ p. Since a^{−1}A ∩ a^{−1}(S\A) = ∅, this is a contradiction.

Lemma 1.3. Let (S, +) be a commutative semigroup, let a ∈ ℕ, and let p, q ∈ βS. Then a · (p + q) = a · p + a · q.

Proof. Since S is commutative, l_{a} : S → S is a homomorphism and thus, by [5, Corollary 4.22], so is l̃_{a} : βS → βS.

In Sections 2 and 3 we investigate the equations a · p + u = b · p + v and u + a · p = v + b · p, where u, v ∈ βS, p ∈ S^{∗} = βS\S, and a, b ∈ ℕ with a ≠ b.

In Section 2, we show that the equation a·p+u = b·p+v has no solution for any semigroup S which is embeddable in the unit circle 𝕋.

In Section 3, we show that the equation u+a·p = v +b·p has no solution (again for p ∈ S^{∗}) for a wide class of commutative cancellative semigroups. We in fact characterize those Abelian groups S for which this equation can hold as exactly those for which {s ∈ S : ab|b − a| · s = 0} is finite.

In Section 4 we turn our attention to a particular class of linear equations in βℕ. (These equations were in fact our original motivation for the equations studied in Sections 2 and 3.) Consider the following result.

Theorem 1.4. Let a_{1}, a_{2}, …, a_{n}, b_{1}, b_{2}, …, b_{m} ∈ ℕ so that for any i ∈ {1, 2, …, n − 1} and any j ∈ {1, 2, …, m − 1}, a_{i} ≠ a_{i+1} and b_{j} ≠ b_{j+1}. Let p be an idempotent in (βℕ, +). Suppose that

a_{1} · p + a_{2} · p + … + a_{n} · p = b_{1} · p + b_{2} · p + … + b_{m} · p .

Then m = n and for all i ∈ {1, 2, …, n}, a_{i} = b_{i}.

Proof. This is [6, Theorem 2.19], where it was derived as an easy consequence of [2, Theorems 2.10 and 3.3].

Notice that, if a ∈ ℕ and p = p + p, then by [5, Lemma 13.1] a · p = a · (p + p) = a · p + a · p. Consequently, the restriction on repeating coefficients in Theorem 1.4 is necessary.

We were led then to ask the following question, asking essentially whether the idempotent requirement can be omitted from Theorem 1.4. (Originally, it was a conjecture, but we have lost faith because of the difficulties that we have encountered.)

Question 1.5. Let a_{1}, a_{2}, …, a_{n}, b_{1}, b_{2}, …, b_{m} ∈ ℕ so that for any i ∈ {1, 2, …, n−1} and any j ∈ {1, 2, …, m − 1}, a_{i} ≠ a_{i+1} and b_{j} ≠ b_{j+1}. Suppose that there exists some p ∈ ℕ^{∗} such that

a_{1} · p + a_{2} · p + … + a_{n} · p = b_{1} · p + b_{2} · p + … + b_{m} · p .

Must it then be true that m = n and for all i ∈ {1, 2, …, n}, a_{i} = b_{i}?

We investigate this question in Section 4, obtaining some partial results.

2. The Equation a · p + u = b · p + v

Let 𝕋_{d} be the circle group with the discrete topology (while 𝕋 denotes the circle group with its usual topology). We show here that if a, b ∈ ℕ with a ≠ b, then the equation a · p + u = b · p + v has no solution with u, v ∈ β𝕋_{d} and p ∈ 𝕋_{d}^{∗}. As a consequence, if S is a semigroup which can be algebraically embedded in 𝕋, such as the semigroup (ℕ, +) and the group (ℤ, +), then the equation a · p + u = b · p + v has no solution with u, v ∈ βS and p ∈ S^{∗}.

We take 𝕋 = ℝ/ℤ and let π : ℝ → 𝕋 be the usual projection. Notice that, since π is a homomorphism, if a ∈ ℕ and r ∈ ℝ, then a · π(r) = π(a · r). We observe that π is an open mapping and so are the maps l_{a} and l_{b}, considered as maps from 𝕋 to itself.

We define γ : β𝕋_{d} → 𝕋 to be the continuous extension of the identity map from 𝕋_{d} to 𝕋, and note that this is a homomorphism by [5, Theorem 4.8]. For any p ∈ β𝕋_{d}, γ(p) is the point of 𝕋 to which p converges. To see this, suppose that U is a neighborhood of γ(p) in 𝕋. Then U ∈ p, because otherwise we should have p ∈ \overline{𝕋 \ U} and hence γ(p) ∈ cℓ_{𝕋}(γ(𝕋 \ U)) = cℓ_{𝕋}(𝕋 \ U).

Lemma 2.1. Let a ∈ ℕ and q ∈ β𝕋_{d}. Then a · γ(q) = γ(a · q).

Proof. Since l_{a} : 𝕋 → 𝕋, γ : β𝕋_{d} → 𝕋, and l̃_{a} : β𝕋_{d} → β𝕋_{d} are continuous functions, and l_{a} ∘ γ agrees with γ ∘ l̃_{a} on 𝕋, it follows that l_{a} ∘ γ(q) = γ ∘ l̃_{a}(q).

Lemma 2.2. Let U be an open subset of 𝕋. If q, r ∈ β𝕋_{d} and U ∈ q, then U + γ(r) ∈ q + r.

Proof. For every x ∈ U, −x + U + γ(r) is a neighborhood of γ(r) and so −x + U + γ(r) ∈ r. Thus {x ∈ 𝕋 : −x + U + γ(r) ∈ r} ∈ q.

Lemma 2.3. Let p ∈ β𝕋_{d}, let a, b ∈ ℕ with a ≠ b, and let V be an open subset of 𝕋 such that a · V ∩ b · V = ∅. If there exist u, v ∈ β𝕋_{d} such that a · p + u = b · p + v, then γ(p) + V ∉ p.

Proof. Put p′ = −γ(p) + p, u′ = −γ(u) + u and v′ = −γ(v) + v. Since γ is a homomorphism, γ(a · p) + γ(u) = γ(b · p) + γ(v). By Lemma 2.1, a · γ(p) + γ(u) = b · γ(p) + γ(v), and so

a · p′ + u′ = a · ( − γ(p)) + a · p + (−γ(u) + u) (by Lemma 1.3)
= −a · γ(p) + ( − γ(u)) + a · p + u by [5, Theorem 6.54]
= −b · γ(p) + ( − γ(v)) + b · p + v
= b · p′ + v′ .

Notice that γ(u′) = γ(v′) = 0. If V ∈ p′, then a · V ∈ a · p′ + u′ and b · V ∈ b · p′ + v′ (by Lemma 2.2) – a contradiction.

Lemma 2.4. Let a, b ∈ ℕ with a < b and pick n ∈ ℕ such that (\frac{a}{b})^{2n} < \frac{1}{2b}. For j ∈ \{0, 1, 2, 3\}, let

D_{j} = ⋃_{k=n}^{∞} ((\frac{a}{b})^{2k+1+j/2} , (\frac{a}{b})^{2k+j/2})

and let X_{j} = −D_{j} ∪ D_{j}. Then each X_{j} is open,

(− (\frac{a}{b})^{2n} , (\frac{a}{b})^{2n}) = ⋃_{j=0}^{3} X_{j} ∪ \{0\} ,

and for each j ∈ {0, 1, 2, 3}, π[a · X_{j}] ∩ π[b · X_{j}] = ∅.

Proof. The first two assertions are immediate. Suppose that we have j ∈ {0, 1, 2, 3} and r, s ∈ X_{j} such that π(a · r) = π(b · s). Since the same equation holds with r replaced by −r and s replaced by −s, we may assume that r > 0. Pick m ∈ ℤ such that a · r = b · s + m. Now

0 < r < (\frac{a}{b})^{2n} < \frac{1}{2b} < \frac{1}{2a}

so that 0 < a · r = b · s + m < \frac{1}{2}. Also, −\frac{1}{2b} < s < \frac{1}{2b} so −\frac{1}{2} < b · s < \frac{1}{2}. Therefore −1 < m < 1

and thus m = 0. That is, a · r = b · s. Pick k ∈ ℕ with k ≥ n such that

(\frac{a}{b})^{2k+1+j/2} < r < (\frac{a}{b})^{2k+j/2} .

Then (\frac{a}{b})^{2k+2+j/2} < \frac{a}{b}r = s < (\frac{a}{b})^{2k+1+j/2} so that s ∉ X_{j}.

Theorem 2.5. Let p ∈ 𝕋_{d}^{∗}, let u, v ∈ β𝕋_{d}, and let a, b ∈ ℕ with a ≠ b. Then a · p + u ≠ b · p + v.

Proof. Suppose that a · p + u = b · p + v and assume without loss of generality that a < b. Pick

n ∈ ℕ such that (\frac{a}{b})^{2n} < \frac{1}{2b} and let U = (− (\frac{a}{b})^{2n} , (\frac{a}{b})^{2n}). Let X_{0}, X_{1}, X_{2}, X_{3} be as in

Lemma 2.4.

We claim that γ(p) + π[U] ∈ p. Indeed, γ(p) + π[U] is a neighborhood of γ(p) so pick B ∈ p such that γ[\overline{B}] ⊆ γ(p) + π[U]. Then B = γ[B] ⊆ γ(p) + π[U]. Since p ∈ 𝕋_{d}^{∗}, \{γ(p)\} ∉ p. By Lemma 2.4, γ(p) + π[U] = {γ(p)} ∪ ⋃_{j=0}^{3}(γ(p) + π[X_{j}]) so pick j ∈ {0, 1, 2, 3} such that γ(p) + π[X_{j}] ∈ p. By Lemma 2.4, π[a · X_{j}] ∩ π[b · X_{j}] = ∅, so by Lemma 2.3, γ(p) + π[X_{j}] ∉ p, a contradiction.

Corollary 2.6. Let S be a discrete semigroup which is algebraically embeddable in 𝕋, let p ∈ S^{∗}, let u, v ∈ βS, and let a, b ∈ ℕ with a ≠ b. Then a · p + u ≠ b · p + v.

Proof. Let φ : S → 𝕋 be an injective homomorphism and let φ̃ : βS → β𝕋_{d} be its continuous extension. By [HS, Corollary 4.22], φ̃ is a homomorphism. Since φ is injective, φ̃(p) ∈ 𝕋_{d}^{∗}. By Theorem 2.5, a · φ̃(p) + φ̃(u) ≠ b · φ̃(p) + φ̃(v) and thus a · p + u ≠ b · p + v.

Corollary 2.7. Let p ∈ ℤ^{∗}, let u, v ∈ βℤ, and let a, b ∈ ℕ with a ≠ b. Then a · p + u ≠ b · p + v.

Proof. Pick an irrational number α. Then the function n ↦ π(n · α) algebraically embeds ℤ in 𝕋 so Corollary 2.6 applies.

3. The Equation u + a · p = v + b · p

We show here that for a large class of semigroups S, including the semigroup (ℕ, +), if a, b ∈ ℕ with a ≠ b, then the equation u + a · p = v + b · p has no solution with u, v ∈ βS and p ∈ S^{∗}. We in fact characterize precisely those Abelian groups S for which solutions exist.

Theorem 3.1. Let (S, +) be a commutative semigroup with identity 0 and let a, b ∈ ℕ with a < b. If {s ∈ S : ab(b − a) · s = 0} is infinite, then there exist u, v ∈ βS and p ∈ S^{∗} such that u + a · p = b + v · p.

Proof. Pick p ∈ S^{∗} such that {s ∈ S : ab(b − a) · s = 0} ∈ p. Notice that {s ∈ S : ab(b − a) · s = 0} ⊆ {s ∈ S : (bab) · s = (aab) · s}. Assume first that (ab) · p ∈ S^{∗}. In this case, let q = (ab) · p. Since l̃_{a} ∘ l̃_{ab} agrees with l̃_{b} ∘ l̃_{ab} on a member of p we have that a · ((ab) · p) = b · ((ab) · p), i.e., a · q = b · q.

Consequently we may assume that (ab) · p = t ∈ S. Notice that a · (b · p) = b · (a · p) because l̃_{a} ∘ l̃_{b} and l̃_{b} ∘ l̃_{a} both agree with l̃_{ab} on S. Now suppose that b · p ∈ S^{∗} and let q = b · p. Then a · q = a · (b · p) = t and thus b · q + a · q = b · q + t. By [5, Theorem 6.54], b · q + t = t + b · q so that b · q + a · q = t + b · q. (Here is the only place we use the commutativity of S.)

Similarly if a · p ∈ S^{∗}, we let q = a · p and conclude that a · q + b · q = t + a · q. Thus we may assume that b · p = u ∈ S and a · p = v ∈ S. Let B = {s ∈ S : a · s = v and b · s = u}. Then B ∈ p. If s ∈ B, then v + (b − a) · s = b · s = u and so v + b · s = v + (b − a) · s + a · s = u + a · s. Consequently λ_{v} ∘ l̃_{b} and λ_{u} ∘ l̃_{a} agree on a member of p and thus u + a · p = v + b · p.

We shall show in Theorem 3.18 that the condition of Theorem 3.1 characterizes those Abelian groups S for which the equation u + a · p = b + v · p has solutions with u, v ∈ βS and p ∈ S^{∗}. The next theorem provides a way for building all Abelian groups in which such an equation does not hold.

Lemma 3.2. Let h : S → T be a homomorphism, where S is a discrete commutative semigroup and T is a compact right topological semigroup. For any a ∈ ℕ and any p ∈ βS, a·h̃(p) = h̃(a·p).

Proof. The mappings p ↦ a · h̃(p) and p ↦ h̃(a · p) are continuous and agree on the dense subspace S of βS.

The following lemma is well known. We give a proof because we do not have a reference.

Lemma 3.3. Let S and T be discrete spaces, let f and g be mappings from S to T, and let f̃, g̃ : βS → βT be their continuous extensions. Let p ∈ βS and suppose that f̃(p) = g̃(p) and that there exists P ∈ p such that f_{|P} is injective. Then {s ∈ S : f(s) = g(s)} ∈ p.

Proof. Since f_{|P} is injective, we can choose a mapping h : T → S such that h(f(s)) = s for all s ∈ P. Then h̃(g̃(p)) = h̃(f̃(p)) = p since h̃ ∘ f agrees with the identity on P. Therefore, by [5, Theorem 3.35] \{s ∈ S : h(g(s)) = s\} ∈ p. Now \{s ∈ S : g(s) ∈ f[P]\} ∈ p, because \overline{f[P]} is a neighborhood of f̃(p) = g̃(p) in βT. Since

{s ∈ S : h(g(s)) = s} ∩ {s ∈ S : g(s) ∈ f[P]} ⊆ {s ∈ S : f(s) = g(s)} ,

we have {s ∈ S : f(s) = g(s)} ∈ p as required.

Recall that any cardinal is an ordinal, and as such is the set of all smaller ordinals. The statements ι < κ and ι ∈ κ are synonymous.

Theorem 3.4. Let a, b ∈ ℕ with a < b and let Ψ(T) be the statement “T is a discrete semigroup with identity 0 and for all u, v ∈ βT and all p ∈ T^{∗}, u+a·p ≠ v +b·p”. Let κ > 0 be a cardinal and let {T_{ι} : ι < κ} be a set of semigroups such that for each ι < κ, Ψ(T_{ι}) and let S = ⨁_{ι<κ} T_{ι}. If each of the sets

{ι < κ : there exist s ≠ t in T_{ι} such that either a · s = a · t or b · s = b · t}

and

{ι < κ : there exists t ∈ T_{ι}\{0} such that a · t = b · t}

is finite, then Ψ(S).

Proof. Suppose the theorem is false, and choose the smallest cardinal κ for which a counterexample exists.

We consider first the possibility that κ < ω. For each ι < κ, π̃_{ι} is a homomorphism by [5, Corollary 4.22]. So π̃_{ι}(u) + a · π̃_{ι}(p) = π̃_{ι}(v) + b · π̃_{ι}(p) (by Lemma 3.2). Since Ψ(T_{ι}) holds, this is impossible if π̃_{ι}(p) ∈ T_{ι}^{∗} and so one has some y_{ι} ∈ T_{ι} such that {s ∈ S : π_{ι}(s) = y_{ι}} ∈ p. Let y ∈ S such that for each ι < κ, π_{ι}(y) = y_{ι}. But then, {y} = ⋂_{ι<κ}{s ∈ S : π_{ι}(s) = y_{ι}} ∈ p, a contradiction.

We thus assume that κ ≥ ω. Define ψ : S → κ by ψ(0) = 0 and for s ∈ S\{0}, ψ(s) = max{ι < κ : π_{ι}(s) ≠ 0}. We claim that for each γ < κ, {s ∈ S : ψ(s) ≥ γ} ∈ p. So suppose instead that we have some γ < κ such that {s ∈ S : ψ(s) < γ} ∈ p. Let f : S → ⨁_{ι<γ} T_{ι} be the projection onto the first γ coordinates and let f̃: βS → β(⨁_{ι<γ} T_{ι}) be its continuous extension. Then f̃(u) + a · f̃(p) = f̃(u + a · p) = f̃(v + b · p) = f̃(v) + b · f̃(p), so by the induction hypothesis, f̃(p) is principal. So pick x ∈ ⨁_{ι<γ} T_{ι} such that {x} ∈ f̃(p). Define y ∈ S by

y_{ι} = \{ \begin{matrix}x_{ι} & if ι < γ \\ 0 & if ι ≥ γ . \end{matrix}

Pick V ∈ p such that f̃[V] = {x}. Then {y} = V ∩ {s ∈ S : ψ(s) < γ} ∈ p, a contradiction. Thus {s ∈ S : ψ(s) ≥ γ} ∈ p for each γ < κ as claimed.

Pick γ < κ such that, whenever γ ≤ ι < κ, we have a · s ≠ a · t and b · s ≠ b · t whenever s and t are distinct members of T_{ι} and a · t ≠ b · t whenever t ∈ T_{ι}\{0}. (We can do this because the set of ι’s violating these conditions is finite.)

Define g : S → S by

g(s)_{ι} = \{ \begin{matrix}0 & if ι ≠ ψ(s) \\ s_{ι} & if ι = ψ(s) . \end{matrix}

Let P ∈ p. We note that {s + a · t : s ∈ S, t ∈ P, and ψ(t) > max{ψ(s), γ}} ∈ u + a · p and {s′ +b·t′ : s′ ∈ S, t′ ∈ P, and ψ(t′) > max{ψ(s′), γ}} ∈ v+b·p. Thus we have s+a·t = s′ +b·t′ for some s, s′ ∈ S and t, t′ ∈ P, with ψ(t) > max{ψ(s), γ} and ψ(t′) > max{ψ(s′), γ}. Now g(s + a · t) = a · g(t) and g(s′ + b · t′) = b · g(t′). So a · g̃(p) = b · g̃(p). Now l_{a} is injective on g[{s ∈ S : ψ(s) > γ}] ∈ g̃(p).

It follows from Lemma 3.3 that {s ∈ S : a·s = b·s} ∈ g̃(p) and hence that {s ∈ S : a·g(s) = b · g(s)} ∈ p. This is a contradiction, because a · g(s) ≠ b · g(s) if ψ(s) > γ.

We now need to establish that the statement Ψ(T) of Theorem 3.4 holds for some specific groups. We shall use a real number x to denote the element π(x) of 𝕋 in order to avoid equations in 𝕋 that are too cumbersome. Of course, with this notation, the equation x = y in 𝕋 is equivalent to the relation x ∈ y + ℤ in ℝ.

Definition 3.5. Let r be a prime number. Then ℤ_{r}^{∞} = \{\frac{m}{r^{n}} ∈ 𝕋 : m ∈ ℕ and n ∈ ω\}.

The subgroups of 𝕋 of this form are called quasicyclic. When using the notation βℤ_{r}^{∞}, we shall assume that ℤ_{r}^{∞} has the discrete topology.

Definition 3.6. Let r be a prime number. For each s ∈ ℤ_{r}^{∞}, we define o(s) to be the order of s, that is the least k ∈ ℕ such that k · s = 0, and we put τ(s) = log_{r} (o(s)). Let τ̃: βℤ_{r}^{∞} → βℤ be the continuous extension of τ.

Lemma 3.7. Let r be a prime, let S = ℤ_{r}^{∞}, let p ∈ S^{∗}, let u ∈ βS and let a ∈ ℕ. If r^{d} is the highest power of r which divides a, then τ̃(u + a · p) = −d + τ̃(p).

Proof. We note that every s ∈ S \ \{0\} can be expressed as s = \frac{m}{r^{n}}, where m, n ∈ ℕ and (m, r) = 1. Then o(s) = r^{n} and τ(s) = n. It is not hard to show that, for any s, t ∈ S, o(t) > o(s) implies that o(s + t) = o(t), and that o(t) > r^{d} implies that o(a · t) = r^{−d}o(t) and thus τ(a·t) = −d+τ(t). Now, for any s ∈ S, {t ∈ S : o(t) > max{o(s), r^{d}}} ∈ p, because this set has a finite complement in S. Thus τ̃(u+a·p) = lim_{s→u} lim_{t→p} τ(s+a·t) = lim_{t→p}(−d+τ(t)) = −d+τ̃(p).

Lemma 3.8. Let r be a prime, let S = ℤ_{r}^{∞}, let p ∈ S^{∗}, let u, v ∈ βS, and let a, b ∈ ℕ. If u + a · p = v + b · p, then the highest power of r which divides a is equal to the highest power of r which divides b.

Proof. Let r^{d} and r^{e} denote the highest powers of r which divide a and b respectively. By Lemma 3.7, −d + τ̃(p) = −e + τ̃(p). This implies that d = e by [5, Lemma 6.28].

Theorem 3.9. Let r be a prime, let S = ℤ_{r}^{∞}, let a, b ∈ ℕ, let u, v ∈ βS, and let p ∈ S^{∗}. If a ≠ b, then u + a · p ≠ v + b · p.

Proof. Suppose that u + a · p = v + b · p. Then, by Lemma 3.8, we can write a = a_{1}r^{d} and b = b_{1}r^{d}, where a_{1}, b_{1} ∈ ℕ, d ∈ ω and (a_{1}, r) = (b_{1}, r) = 1.

We choose k ∈ ℕ satisfying r^{k} > |a_{1} − b_{1}|.

Each s ∈ S\\{0\} can be expressed as \frac{m(s)}{r^{n(s)}}, where m(s), n(s) ∈ ℕ and (m(s), r) = 1. Thus we

have s = \frac{x(s)r^{k} + y(s)}{r^{n(s)}}, for some x(s) ∈ ω and some y(s) ∈ \{1, 2, …, r^{k} − 1\} with (y(s), r) = 1.

We can choose y ∈ {1, 2, …, r^{k} − 1}, with (y, r) = 1, and a set P ∈ p such that y(t) = y for every t ∈ P. Let s ∈ S. Then {t ∈ P : τ(t) > k + d + τ(s)} ∈ p. It follows that the set of elements of ℤ_{r}^{∞} of the form \frac{z}{r^{l}} + a · \frac{xr^{k} + y}{r^{n}}, with x, z, k, l, n ∈ ω and n > k + d + l, is a member of u + a · p. The corresponding statement also holds for v + b · p. Thus we have an equation in ℤ_{r}^{∞} of the form:

\frac{z}{r^{l}} + a · \frac{xr^{k} + y}{r^{n}} = \frac{z′}{r^{l′}} + b · \frac{x′r^{k} + y}{r^{n′}} ,

in which all the symbols denote non-negative integers and n > k + d + l and n′ > k + d + l′. We observe that the left hand side of this equation has order r^{n−d} and the right hand side has order r^{n′−d}, and so n = n′. Thus we have the following relation in ℝ:

\frac{z}{r^{l}} + a_{1} · \frac{xr^{k} + y}{r^{n−d}} ∈ \frac{z′}{r^{l′}} + b_{1} · \frac{x′r^{k} + y}{r^{n−d}} + ℤ.

Multiplying by r^{n−d} shows that a_{1}y ≡ b_{1}y (mod r^{k}) and hence that a_{1} ≡ b_{1} (mod r^{k}). Since |a_{1} − b_{1}| < r^{k}, it follows that a_{1} = b_{1} and hence that a = b.

We now turn our attention to the direct sum of copies of ℤ_{r}^{∞}, one for each prime r. We omit the easy proof of the following lemma, which enables us to invoke Theorem 3.4.

Lemma 3.10. Let r be a prime and let a, b ∈ ℕ with a < b.

(1) If there exists t ∈ ℤ_{r}^{∞}\{0} such that a · t = b · t, then r|(b − a).

(2) If there exist t ≠ s in ℤ_{r}^{∞} such that a · t = a · s, then r|a.

Theorem 3.11. Let ⟨r_{n}⟩_{n=1}^{∞} be the sequence of primes, let S = ⨁_{n=1}^{∞} ℤ_{r_{n}}^{∞}, let p ∈ S^{∗}, let u, v ∈ βS, and let a, b ∈ ℕ with a < b. Then u + a · p ≠ v + b · p.

Proof. Let Ψ(T) be the statement of Theorem 3.4. By Theorem 3.9, we have for each n ∈ ℕ that Ψ(ℤ_{r_{n}}^{∞}) holds. By Lemma 3.10, we have that {n < ω : there exist s ≠ t in ℤ_{r_{n}}^{∞} such that either a · s = a · t or b · s = b · t} is finite and {n < ω : there exists t ∈ ℤ_{r_{n}}^{∞}\{0} such that a · t = b · t} is finite. Thus Theorem 3.4 applies.

Now we consider the group (ℚ, +). We shall need the following well known fact.

Lemma 3.12. π[ℚ] ≈ ⨁_{n=1}^{∞} ℤ_{r_{n}}^{∞}.

Proof. This is proved in [3, Chapter 1, Section 5].

In the following theorem, ℚ_{d} denotes ℚ with the discrete topology.

Theorem 3.13. Let S = ℚ_{d}, let u, v ∈ βS, let p ∈ S^{∗} and let a, b ∈ ℕ with a ≠ b. Then u + a · p ≠ v + b · p.

Proof. Suppose that u+a·p = v+b·p. We may assume that [0, ∞)∩ℚ ∈ p. (For if (−∞, 0)∩ℚ ∈ p we have by [5, Lemma 13.1] that −u + a · (−p) = −1 · (u + a · p) = −1 · (v + b · p) = −v + a · (−p) and then (0, ∞) ∩ ℚ ∈ −p. )

Assume first that there is some n ∈ ℕ such that [0, n) ∩ ℚ ∈ p. Since π is a homomorphism, we have that its continuous extension π̃ : βℚ_{d} → β(π[ℚ]_{d}) is a homomorphism by [5, Corollary 4.22]. Therefore, π̃(u + a · p) = π̃(u) + π̃(a · p).

Further, for s ∈ ℚ, π(a · s) = a · π(s) so that π̃ ∘ l_{a} and l_{a} ∘ π̃ agree on S and hence on βS, so that π̃(a · p) = a · π̃(p).

Thus π̃(u) + a · π̃(p) = π̃(v) + b · π̃(p). By Theorem 3.11 and Lemma 3.12, this is impossible if π̃(p) ∈ (π[ℚ]_{d})^{∗}. Thus there is some x ∈ ℚ such that π̃(p) = π(x) and thus, {y ∈ ℚ : π(y) = π(x)} ∈ p. But {y ∈ ℚ : π(y) = π(x)} ∩ [0, n) is finite and so p ∉ S^{∗}, a contradiction.

Now assume that for all n ∈ ℕ, (n, ∞) ∩ ℚ ∈ p. We assume without loss of generality that

a < b and let α = ^{4} \sqrt{\frac{b}{a}}. Define f : ℚ → ω by

f(x) = \{ \begin{matrix}⌊log_{α} x⌋ & if x ≥ 1 \\ 1 & if x < 1 . \end{matrix}

Let f̃: βℚ_{d} → βω be the continuous extension of f.

Note that f(b) = f(a)+4. Note also that for all x, y ∈ ℚ∩[1, ∞) either f(x·y) = f(x)+f(y) or f(x · y) = f(x) + f(y) + 1. Pick i ∈ {0, 1} such that {y ∈ ℚ : f(a · y) = f(a) + i + f(y)} ∈ p. Then f̃ ∘ l_{a} and λ_{f(a)} ∘ λ_{i} ∘ f̃ agree on a member of p and thus f̃(a · p) = f(a) + i + f̃(p). Likewise, pick j ∈ {0, 1} such that f̃(b · p) = f(b) + j + f̃(p).

Observe next that for all n ∈ ℕ, (n, ∞) ∩ ℚ ∈ a · p and (n, ∞) ∩ ℚ ∈ b · p. We now claim that for all x, y ∈ ℚ, if y > max \{\frac{−x · α}{α − 1}, \frac{x}{α − 1}\} + 1, then there is some k ∈ \{−1, 0, 1\} such

that f(x + y) = f(y) + k. To see this, assume first that x ≥ 0. Then y > \frac{x}{α − 1} so αy > x + y

and thus α^{f(y)} ≤ y ≤ y + x < αy < α^{f(y)+2}. Next assume that x < 0. Then y > \frac{−x · α}{α − 1} and

thus y + x > \frac{y}{α}. Then α^{f(y)−1} ≤ \frac{y}{α} < y + x < y < α^{f(y)+1}.

For each x ∈ ℚ, pick k(x) ∈ {−1, 0, 1} such that {y ∈ ℚ : f(x+y) = f(y)+k(x)} ∈ a·p and pick k ∈ {−1, 0, 1} such that {x ∈ ℚ : k(x) = k} ∈ u. We claim that f̃(u + a · p) = k + f̃(a · p).

For this it suffices to show that f̃∘ ρ_{a·p} is constantly equal to f̃(a · p) + k on a member of u. So let x ∈ ℚ such that k(x) = k. Then f̃∘ λ_{x} and λ_{k} ∘ f̃ agree on a member of a · p so the claim is established.

Similarly, pick m ∈ {−1, 0, 1} such that f̃(v +b·p) = m+f̃(b·p). Then m+f(b)+j +f̃(p) = f̃(v+b·p) = f̃(u+a·p) = k+f(a)+i+f̃(p). Then by [5, Lemma 6.28], m+f(b)+j = k+f(a)+i and thus f(b) − f(a) = k + i − j − m ≤ 1 + 1 + 0 + 1 < 4, a contradiction.

Theorem 3.14. Let S be a discrete Abelian group and let a, b ∈ ℕ with a < b. If for every s ∈ S\{0}, ab(b − a) · s ≠ 0, then there do not exist u, v ∈ βS and p ∈ S^{∗} such that u + a · p = v + b · p.

Proof. We note that, by an obvious induction, for every s ∈ S\{0} and every n ∈ ℕ, (ab(b − a))^{n}s ≠ 0. By [3, Theorems 19.1 and 20.1], S can be embedded in a group of the form ⨁_{ι<κ} T_{ι} where each T_{ι} is either ℚ or ℤ_{r}^{∞} for some prime r. Let I = {ι < κ : T_{ι} = ℤ_{r}^{∞} for some prime r such that r|ab(b − a)} and let J = κ\I. Let G_{1} = ⨁_{ι∈J} T_{ι} and let G_{2} = ⨁_{ι∈I} T_{ι}. Let φ : S → G_{1} × G_{2} be an embedding. Given s ∈ S, let φ(s) = (s_{1}, s_{2}) Now (ab(b − a))^{n}s_{2} = 0 for some n ∈ ℕ. Thus s ≠ 0 implies that s_{1} ≠ 0. So the mapping s ↦ π_{1} ∘ φ is injective and defines an embedding of S in G_{1}.

By Theorems 3.9 and 3.13, we have that for each ι ∈ I, Ψ(T_{ι}) holds. We have by Lemma 3.10 that {ι ∈ J : there exist s ≠ t in T_{ι} such that either a · s = a · t or b · s = b · t} = ∅ and {ι ∈ J : there exists t ∈ T_{ι}\{0} such that a · t = b · t} = ∅. Thus Theorem 3.4 applies to yield the conclusion for G_{1} and thus for S.

Definition 3.15. If S is an Abelian group and r a prime number, we put S_{r} = {s ∈ S : r^{n}s = 0 for some n ∈ ℕ}.

Lemma 3.16. Let S be an Abelian group. Assume that u + a · p = v + b · p, where u, v ∈ βS, p ∈ S^{∗} and a, b are distinct positive integers. Let R denote the set of prime factors of ab(b − a). Then there exists s ∈ S such that s + ⨁_{r∈R} S_{r} ∈ p, where ⨁_{r∈R} S_{r} denotes the internal direct sum.

Proof. By [3, Theorems 19.1 and 20.1] we may assume that S ⊆ G where G is the (internal) direct sum of discrete groups G_{1} and G_{2}, where G_{1} is a direct sum of groups which are copies of ℚ or of quasicyclic groups corresponding to primes which are not in R, and G_{2} is a direct sum of quasicyclic groups corresponding to primes which are in R. Let π_{1} denote the natural map from S to G_{1} and let π̃_{1} : βS → βG_{1} be its continuous extension. By [5, Corollary 4.22] and Lemma 3.2, π̃_{1}(u) + a · π̃_{1}(p) = π̃_{1}(v) + b · π̃_{1}(p). So by Theorem 3.14, π̃_{1}(p) ∉ G_{1}^{∗}. Thus there exist P ∈ p and s_{1} ∈ G_{1} for which π_{1}[P] = {s_{1}}. Choose any s ∈ P. Then −s + P ⊆ G_{2}. Now G_{2} is a torsion group and G_{2} ∩ S_{r} = {0} for every r ∉ R. It follows that G_{2} ⊆ ⨁_{r∈R} S_{r}, since, by [3, Theorem 2.1], every Abelian torsion group is the direct sum of its r-subgroups.

Lemma 3.17. Let r be a prime number and let G be an Abelian r-group. Let H = {x ∈ G : rx = 0}. Then H is isomorphic to a direct sum ⨁_{ι∈I} ℤ_{r}, and G can be embedded in ⨁_{ι∈I} ℤ_{r}^{∞}. In particular, if H is finite, G can be embedded in the direct sum of a finite number of copies of ℤ_{r}^{∞}.

Proof. We observe that H has the form ⨁_{ι∈I} ℤ_{r}, because H is a vector space over ℤ_{r}. Let f : H → D = ⨁_{ι∈I} ℤ_{r}^{∞} denote the natural embedding. Consider the set of all pairs (N, h), where N is a subgroup of G which contains H and h : N → D is an injective homomorphism which extends f. We order this set by saying that (N, h) ≤ (N′, h′) if N ⊆ N′ and h′_{|N} = h. By Zorn’s Lemma choose a pair (M, g) which is maximal with respect to this ordering. We shall show that M = G.

Suppose, on the contrary, that there exists x ∈ G \ M. We may suppose that r · x ∈ M. (Letting k be the largest element of ω such that r^{k}x ∉ M one has r(r^{k}x) ∈ M.) Since D is divisible, we can extend g to a homomorphism \overline{g} : M + ℤx → D by [3, Theorem 16.1].

We claim that \overline{g} is injective. To see this, suppose that \overline{g}(t + nx) = 0, where t ∈ M and n ∈ ℤ. Then \overline{g}(rt+nrx) = 0 and so rt+nrx = 0, because rt+nrx ∈ M. Thus t+nx ∈ H ⊆ M and therefore t + nx = 0.

Theorem 3.18. Let S be a discrete Abelian group and let a, b ∈ ℕ with a < b. There exist u, v ∈ βS and p ∈ S^{∗} such that u + a · p = v + b · p if and only if {s ∈ S : ab(b − a) · s = 0} is infinite.

Proof. The sufficiency is a consequence of Theorem 3.1.

For the necessity, assume that {s ∈ S : ab(b − a) · s = 0} is finite. Let R denote the set of prime factors of ab(b − a). For each r ∈ R, {s ∈ S : rs = 0} is finite. By Lemma 3.17, there is an injective homomorphism h from ⨁_{r∈R} S_{r} to a group G which is the direct sum of a finite number of quasicyclic groups. Since G is divisible, h extends to a homomorphism h′ : S → G by [3, Theorem 16.1]. We then have h̃′(u) + a · h̃′(p) = h̃′(v) + b · h̃′(p). By Lemma 3.16, s + ⨁_{r∈R} S_{r} ∈ p for some s ∈ S. Since h′ is injective on this set, h̃′(p) ∈ G^{∗}. By Theorems 3.4 and 3.9, this is a contradiction.

Corollary 3.19. Let S be a commutative cancellative semigroup and let a, b ∈ ℕ with a < b. Assume that {(s, t) ∈ S × S : s ≠ t and ab(b − a) · s = ab(b − a) · t} is finite. Let u, v ∈ βS, let p ∈ S^{∗} and let a, b ∈ ℕ with a ≠ b. Then u + a · p ≠ v + b · p.

Proof. Let G be the group of quotients of S. (Notice that “quotients” is multiplicative terminology. The members of G all have the form s − t for some s, t ∈ S.) Since {(s, t) ∈ S × S : s ≠ t and ab(b − a) · s = ab(b − a) · t} is finite, {x ∈ G : ab(b − a) · x = 0} is finite, so Theorem 3.18 applies.

Lemma 3.20. Let r be a prime number. Suppose that S = ⨁_{ι<κ} ℤ_{r}^{∞}. Let o(s) denote the order of the element s ∈ S and let õ : βS → βℕ denote the continuous extension of o. If u + a · p = v + b · p for some u, v ∈ βS, p ∈ S^{∗} and a ≠ b in ℕ, then õ(p) ∈ ℕ.

Proof. Suppose we have u, v ∈ βS, p ∈ S^{∗}, and a ≠ b ∈ ℕ with u+a·p = v +b·p and õ(p) ∈ ℕ^{∗}. We make the inductive assumption that κ is the smallest cardinal for which this is possible. We note that Theorems 3.4 and 3.9 imply that κ ≥ ω.

We may suppose that (a, b) = 1 because, if (a, b) = d, we can replace a and b by \frac{a}{d} and

\frac{b}{d} respectively, replacing p by d · p. (Observe that õ(d · p) ∈ ℕ^{∗}, and consequently d · p ∈ ℕ^{∗}. Indeed, if õ(d · p) = n ∈ ℕ, then {t ∈ S : o(d · t) = n} ∈ p and thus {t ∈ S : o(t) ≤ d · n} ∈ p, contradicting the assumption that õ(p) ∈ ℕ^{∗}.)

We know by Theorem 3.14 that r|ab(b − a). We first consider the case in which r|a. Let r^{k} be the largest power of r which divides a. Define τ : S → ω by τ(s) = log_{r} o(s). If s, t ∈ S and o(t) > r^{k}o(s), then τ(s + a · t) = τ(a · t) = −k + τ(t). Thus τ̃(u + a · p) = lim_{s→u} lim_{t→p} τ(s + a · t) = −k + τ̃(p). Similarly, since r |̸ b, τ̃(v + bp) = τ̃(p). By [5, Lemma 6.28], this is a contradiction.

We may thus suppose that r |̸ a and r |̸ b. This implies that, for every s ∈ S, o(a · s) = o(b · s) = o(s). If s ∈ S\{0}, let l(s) = max{ι < κ : π_{ι}(s) ≠ 0} and let μ(s) = max{ι < κ : o(π_{ι}(s)) = o(s)}. Define g : S → S by g(0) = 0 and for s ∈ S\{0} and ι < κ,

g(s)(ι) = \{ \begin{matrix}0 & if ι ≠ μ(s) \\ π_{μ(s)}(s) & if ι = μ(s) . \end{matrix}

We claim that a · g̃(p) = b · g̃(p), so suppose instead that a · g̃(p) ≠ b · g̃(p) and pick P ∈ p such that for all t, t′ ∈ P, a · g(t) ≠ b · g(t′). Notice that for each λ < κ, {t ∈ S : μ(t) > λ} ∈ p. To see this, suppose instead that {t ∈ S : μ(t) ≤ λ} ∈ p. Let σ denote the projection of S onto ⨁_{ι≤λ} ℤ_{r}^{∞}. Since {t ∈ S : μ(t) ≤ λ} ∈ p, we have that {t ∈ S : o(σ(t)) = o(t)} ∈ p and thus õ(σ̃(p)) = õ(p) ∈ ℕ^{∗}, contradicting our inductive assumption.

Consequently,

{s + a · t : s ∈ S, t ∈ P, μ(t) > l(s), and o(t) > o(s)} ∈ u + a · p and
{s′ + b · t′ : s′ ∈ S, t′ ∈ P, μ(t′) > l(s′), and o(t′ > o(s′)} ∈ v + b · p .

Thus we may choose s, s′ ∈ S and t, t′ ∈ P with μ(t) > l(s), o(t) > o(s), μ(t′) > l(s′), and o(t′) > o(s′) such that s + a · t = s′ + b · t′. Since μ(a · t) = μ(t) > l(s) and o(t) > o(s), we have μ(s + a · t) = μ(a · t) and π_{μ(a·t)}(s + a · t) = a · π_{μ(t)}(t) and so g(s + a · t) = a · g(t) and similarly g(s′ + b · t′) = b · g(t′). Since t, t′ ∈ P, this is a contradiction and thus a · g̃(p) = b · g̃(p) as claimed.

Since l_{a} is injective on S, it follows from Lemma 3.3 that {t ∈ S : a · t = b · t} ∈ g̃(p). Let r^{m} be the largest power of r which divides b − a. Now {t ∈ S : o(t) > r^{m}} ∈ p and o(g(t)) = o(t) for all t ∈ S. So {t ∈ S : o(t) > r^{m}} ∈ g̃(p). This is a contradiction, because if o(t) > r^{m}, then a · t ≠ b · t.

Theorem 3.21. Let S be an Abelian group. Suppose that u + ap = v + bp for some u, v ∈ βS, some p ∈ S^{∗}, and some a ≠ b in ℕ. Then there exist s ∈ S and k ∈ ℕ such that (ab(b − a))^{k}p ∈ S.

Proof. By Lemmas 3.16 and 3.17, there exist s ∈ S such that s+⨁_{r∈R} S_{r} ∈ p and an embedding h : ⨁_{r∈R} S_{r} → D = ⨁_{r∈R} D_{r}, where each D_{r} is a direct sum of copies of ℤ_{r}^{∞}. By [3, Theorem 16.1], h extends to a homomorphism h′ from S to D. Since π_{r} ∘ h′ is a homomorphism, so is π̃_{r} ∘ h̃′ by [5, Corollary 4.22]. Thus π̃_{r} ∘ h̃′(u) + a · π̃_{r} ∘ h̃′(p) = π̃_{r} ∘ h̃′(v) + b · π̃_{r} ∘ h̃′(p). So, by Lemma 3.20, for each r ∈ R, õ ∘ π̃_{r} ∘ h̃′(p) ∈ ℕ and hence õ ∘ π̃_{r} ∘ h̃′(−s + p) ∈ ℕ.

So r^{n_{r}} · (π̃_{r} ∘ h̃′(−s + p)) = 0 for some n_{r} ∈ ℕ. Let n = ∏_{r∈R} r^{n_{r}}. Then h̃′(n · (−s + p)) = n·h̃′(−s+p) = 0. Now h′ is injective on ⨁_{r∈R} S_{r}, so that (see [5, Exercise 3.4.1]) h̃′ is injective on cℓ(⨁_{r∈R} S_{r}). Since n · (−s + p) ∈ cℓ(⨁_{r∈R} S_{r}) it follows that n · (−s + p) = 0. Our claim follows from the fact that we can choose k ∈ ℕ such that (ab(b − a))^{k} is a multiple of n.

Our results depended in an essential way on the assumption that S is Abelian. However, our next corollary shows that we can obtain analogous results for some non-Abelian semigroups. If S is an arbitrary semigroup and a ∈ ℕ, we shall use π_{a} : S → S for the mapping s ↦ s^{a} and π̃_{a} : βS → βS for its continuous extension.

Corollary 3.22. Let S denote the free semigroup on a finite set of generators. If u, v ∈ βS, p ∈ S^{∗}, and a, b ∈ ℕ with a ≠ b, then uπ̃_{a}(p) ≠ vπ̃_{b}(p).

Proof. For s ∈ S, let ℓ(s) be the length of s. We note that ℓ is a homomorphism and that ℓ(π_{n}(s)) = n·ℓ(s) for every n ∈ ℕ and every s ∈ S. Thus ℓ̃: βS → βℕ is a homomorphism by [5, Corollary 4.22], and it follows from the continuity of the maps involved that ℓ̃(π_{n}(x)) = n · ℓ̃(x) for every x ∈ βS. So ℓ̃(u) + a · ℓ̃(p) = ℓ̃(v) + b · ℓ̃(p). By Corollary 3.19, ℓ̃(p) ∈ ℕ. However, if ℓ̃(p) = n, the fact that ℓ^{−1}[{n}] is finite implies that p ∈ S, a contradiction.

4. The Equation a_{1}·p + a_{2}·p + … + a_{n}·p = b_{1}·p + b_{2}·p + … + b_{m}·p

Recall from Theorem 1.4 that if p+p = p, a_{1}, a_{2}, …, a_{n} ∈ ℕ with a_{i} ≠ a_{i+1} for all i ∈ {1, 2, …, n−1}, b_{1}, b_{2}, …, b_{m} ∈ ℕ with b_{i} ≠ b_{i+1} for all i ∈ {1, 2, …, m−1}, and a_{1}·p+a_{2}·p+…+a_{n}·p = b_{1} · p + b_{2} · p + … + b_{m} · p, then m = n and a_{i} = b_{i} for all i ∈ {1, 2, …, n}. Recall also that the restriction on repeated coefficients is necessary. For example, for any idempotent p ∈ βℕ, one has p + p + 2 · p + 3 · p = p + 2 · p + 3 · p + 3 · p.

In this section we investigate solutions to the equation a_{1} · p + a_{2} · p + … + a_{n} · p = b_{1} · p + b_{2} · p + … + b_{m} · p for p ∈ ℕ^{∗}. As an immediate consequence of Corollary 2.7 and Theorem 3.14 we have that necessarily a_{1} = b_{1} and a_{n} = b_{m}. Beyond that, the information we are able to obtain is quite limited. In particular, our main results are restricted to the case when there exists some d ∈ ℕ\{1} such that a_{1}, a_{2}, …, a_{n}, b_{1}, b_{2}, …, b_{m} ∈ {1, d}. (By [5, Lemma 13.1] the restriction that a_{1}, a_{2}, …, a_{n}, b_{1}, b_{2}, …, b_{m} ∈ {1, d} is the same as requiring that a_{1}, a_{2}, …, a_{n}, b_{1}, b_{2}, …, b_{m} ∈ {k, l} where k divides l.)

Some special cases of our results include the facts that the equations p + 3 · p + p = p and 3 · p + p + 3 · p + p = 3 · p + p have no solutions. The nature of the arguments is such that we cannot even determine whether the equation 2 · p + 3 · p + 2 · p = 2 · p can be solved. (We conjecture very strongly that it cannot be solved.)

The key to the amount of success that we have had is the following lemma, which allows us to work in base d arithmetic and add numbers with no carrying.

Lemma 4.1. Let p ∈ ℕ^{∗} and let a_{1}, a_{2}, …, a_{n}, b_{1}, b_{2}, …, b_{m} ∈ ℕ. If a_{1} · p + a_{2} · p + … + a_{n} · p = b_{1} · p + b_{2} · p + … + b_{m} · p and a_{1} + a_{2} + … + a_{n} ≠ b_{1} + b_{2} + … + b_{m}, then for all d, l ∈ ℕ, ℕd^{l} ∈ p.

Proof. It suffices to show that for every prime q and every l ∈ ℕ, ℕq^{l} ∈ p. So let a prime q be given. Without loss of generality assume that c = a_{1} + a_{2} + … + a_{n} − (b_{1} + b_{2} + … + b_{m}) > 0. Let l ∈ ℕ be given and pick k ∈ ℕ such that q^{k} ≥ c. Pick i ∈ {0, 1, …, q^{k+l} − 1} such that A = ℕq^{k+l} + i ∈ p. Then a_{1}A + a_{2}A + … + a_{n}A ∈ a_{1} · p + a_{2} · p + … + a_{n} · p (as can be established by an easy induction) and b_{1}A + b_{2}A + … + b_{m}A ∈ b_{1} · p + b_{2} · p + … + b_{m} · p. Consequently a_{1}A + a_{2}A + … + a_{n}A ∩ b_{1}A + b_{2}A + … + b_{m}A ≠ ∅. Thus a_{1}i + a_{2}i + … + a_{n}i ≡ b_{1}i + b_{2}i + … + b_{m}i (mod q^{k+l}). That is, c · i ≡ 0 (mod q^{k+l}). Since q^{k+1} |̸ c, we have q^{l}|i. Then ℕq^{k+l} + i ⊆ ℕq^{l} so that ℕq^{l} ∈ p as required.

We now adopt some special notation to be used in our proof of the main theorem of this section, Theorem 4.5.

Definition 4.2. Let d ∈ ℕ\{1}, let x ∈ ℕ, and write x in its base d expansion as ∑_{i=1}^{l} d^{t_{i}} · g_{i} where 0 ≤ t_{1} < t_{2} < … < t_{l} and each g_{i} ∈ {1, 2, …, d−1}. Then start(x) = t_{l}, and end(x) = t_{1}. For i ∈ ℤ, f_{i}(x) = |{j ∈ {1, 2, …, l − 1} : t_{j+1} − t_{j} ≡ i (mod 3)}|.

The notation does not reflect its dependence on the choice of d. The terminology “start” and “end” comes from [2] and refers to the number as ordinarily written in base d (with high order digits to the left). For example, if d = 5 and x = 4003201410300, then start(x) = 12, end(x) = 2, f_{0}(x) = 1, f_{1}(x) = 3, and f_{2}(x) = 2.

Lemma 4.3. Let d ∈ ℕ\\{1\}, let u ∈ βℕ, let p ∈ ⋂_{l=1}^{∞} \overline{ℕd^{l}}, and let i ∈ \{0, 1, 2\}. If \{x ∈ ℕ : start(x) ≡ i (mod 3)} ∈ p, then

{x ∈ ℕ : start(x) ≡ i + 1 (mod 3)} ∈ d · p ,

{x ∈ ℕ : start(x) ≡ i (mod 3)} ∈ u + p , and
{x ∈ ℕ : start(x) ≡ i + 1 (mod 3)} ∈ u + d · p .

Proof. Let A = {x ∈ ℕ : start(x) ≡ i (mod 3)}. To see that {x ∈ ℕ : start(x) ≡ i+1 (mod 3)} ∈ d · p, note that A ⊆ d^{−1}{x ∈ ℕ : start(x) ≡ i + 1 (mod 3)}.

To see that A ∈ u + p, we show that for all x ∈ ℕ, −x + A ∈ p. So let x ∈ ℕ and let B = A ∩ ℕd^{start(x)+1}. Then B ∈ p. If y ∈ B, then start(y + x) = start(y) ≡ i (mod 3) so B ⊆ −x + A.

The proof that {x ∈ ℕ : start(x) ≡ i + 1 (mod 3)} ∈ u + d · p is similar.

Lemma 4.4. Let d ∈ ℕ\\{1\}, let p ∈ ⋂_{l=1}^{∞} \overline{ℕd^{l}}, let a_{1}, a_{2}, …, a_{n} ∈ \{1, d\}, and fix i, j ∈ \{0, 1, 2\} such that {x ∈ ℕ : start(x) ≡ i (mod 3) and end(x) ≡ j (mod 3)} ∈ p. Let c_{1} = |{i ∈ {1, 2, …, n − 1} : a_{i} = 1 and a_{i+1} = d}|. Let r ∈ ℕ and fix α ∈ {0, 1, …, r − 1} such that {x ∈ ℕ : f_{j+1−i}(x) ≡ α (mod r)} ∈ p. Then

{x ∈ ℕ : f_{j+1−i}(x) ≡ n · α + c_{1} (mod r)} ∈ a_{1} · p + a_{2} · p + … + a_{n} · p .

Proof. Let A = {x ∈ ℕ : start(x) ≡ i (mod 3) and end(x) ≡ j (mod 3)} and let B = {x ∈ ℕ : f_{j+1−i}(x) ≡ α (mod r)}. We proceed by induction on n.

Assume first that n = 1. Then c_{1} = 0 and n · α + c_{1} = α. If a_{1} = 1, then B ∈ a_{1} · p directly, so assume that a_{1} = d. Given x ∈ ℕ, f_{j+1−i}(dx) = f_{j+1−i}(x) and so B ⊆ d^{−1}B and hence B ∈ a_{1} · p.

Now let n > 1 and assume that the statement is true for n−1. Let F = {x ∈ ℕ : f_{j+1−i}(x) ≡ n · α + c_{1} (mod r)}. We consider four cases.

\underline{Case 1}: a_{n−1} = 1 and a_{n} = 1. Then by the induction hypothesis,

E = {x ∈ ℕ : f_{j+1−i}(x) ≡ (n − 1) · α + c_{1} (mod r)} ∈ a_{1} · p + a_{2} · p + … + a_{n−1} · p .

Also, by Lemma 4.3, {x ∈ ℕ : start(x) ≡ i (mod 3)} ∈ a_{1} · p + a_{2} · p + … + a_{n−1} · p. We claim that E ∩ {x ∈ ℕ : start(x) ≡ i (mod 3)} ⊆ {x ∈ ℕ : −x + F ∈ p} so let x ∈ E such that start(x) ≡ i (mod 3) and let l = start(x) + 1. Then B ∩ ℕd^{l} ∩ A ⊆ −x + F.

\underline{Case 2}: a_{n−1} = 1 and a_{n} = d. Then by the induction hypothesis,

E = {x ∈ ℕ :: f_{j+1−i}(x) ≡ (n − 1) · α + c_{1} − 1 (mod r)} ∈ a_{1} · p + a_{2} · p + … + a_{n−1} · p .

Also, by Lemma 4.3, {x ∈ ℕ : start(x) ≡ i (mod 3)} ∈ a_{1} · p + a_{2} · p + … + a_{n−1} · p. We claim that E ∩ {x ∈ ℕ : start(x) ≡ i (mod 3)} ⊆ {x ∈ ℕ : −x + F ∈ d · p} so let x ∈ E such that start(x) ≡ i (mod 3) and let l = start(x) + 1. Then B ∩ ℕd^{l} ∩ A ⊆ d^{−1}(−x + F).

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 0 (2000), #A02 18

Cases 3 (a_{n−1} = d and a_{n} = 1) and 4 (a_{n−1} = d and a_{n} = d) are handled similarly. Theorem 4.5. Let d ∈ ℕ\\{1\}, let p ∈ ⋂_{l=1}^{∞} \overline{ℕd^{l}}, let a_{1}, a_{2}, …, a_{n}, b_{1}, b_{2}, …, b_{m} ∈ \{1, d\} and assume that a_{1} · p + a_{2} · p + … + a_{n} · p = b_{1} · p + b_{2} · p + … + b_{m} · p. Let c = |{t ∈ {1, 2, …, n − 1} : a_{t} ≠ a_{t+1}} and let e = |{t ∈ {1, 2, …, m − 1} : b_{t} ≠ b_{t+1}}. Then a_{1} = b_{1}, a_{n} = b_{m},

and (n − m)|\frac{e − c}{2}.

Proof. That a_{1} = b_{1} and a_{n} = b_{m} follows from Corollary 2.7 and Theorem 3.18. Let

c_{1} = |{t ∈ {1, 2, …, n − 1} : a_{t} = 1 and a_{t+1} = d} ,
c_{2} = |{t ∈ {1, 2, …, n − 1} : a_{t} = d and a_{t+1} = 1} ,
e_{1} = |{t ∈ {1, 2, …, m − 1} : b_{t} = 1 and b_{t+1} = d} , and
e_{2} = |{t ∈ {1, 2, …, m − 1} : b_{t} = d and b_{t+1} = 1} .

Notice that (1) If a_{1} = a_{n}, then c_{1} = c_{2}.

(2) If a_{1} = 1 and a_{n} = d, then c_{1} = c_{2} + 1.

(3) If a_{1} = d and a_{n} = 1, then c_{2} = c_{1} + 1. Since similar statements hold for e_{1} and e_{2}, we have in any event that c_{2} − c_{1} = e_{2} − e_{1}.

Fix i, j ∈ {0, 1, 2} such that {x ∈ ℕ : start(x) ≡ i (mod 3) and end(x) ≡ j (mod 3)} ∈ p .

If m = n, pick r ∈ ℕ such that r > |e_{1} − c_{1}|. If m ≠ n, let r = |m − m|. Pick α ∈ {0, 1, …, r − 1} such that {x ∈ ℕ : f_{j+1−i}(x) ≡ α (mod r)} ∈ p. By Lemma 4.4, we have that {x ∈ ℕ : f_{j+1−i}(x) ≡ n · α + c_{1} (mod r)} ∈ a_{1} · p + a_{2} · p + … + a_{n} · p and {x ∈ ℕ : f_{j+1−i}(x) ≡ m · α + e_{1} (mod r)} ∈ b_{1} · p + b_{2} · p + … + b_{m} · p. Consequently n · α + c_{1} ≡ m · α + e_{1} (mod r).

If m = n, we have c_{1} ≡ e_{1} (mod r) so, since r > |c_{1} − e_{1}|, c_{1} = e_{1}.

If m ≠ n, then r = |m − n| so that c_{1} ≡ e_{1} (mod r) and thus (n − m)|(e_{1} − c_{1}).

Therefore in any case (n − m)|(e_{1} − c_{1}). We have observed that c_{2} − c_{1} = e_{2} − e_{1} and thus e − c = (e_{2} − c_{2}) + (e_{1} − c_{1}) = 2(e_{1} − c_{1}) so that (n − m)|\frac{e − c}{2} as required. Corollary 4.6. Let d ∈ ℕ\{1}, let p ∈ ℕ^{∗}, let a_{1}, a_{2}, …, a_{n}, b_{1}, b_{2}, …, b_{m} ∈ {1, d}, and assume that a_{1} · p + a_{2} · p + … + a_{n} · p = b_{1} · p + b_{2} · p + … + b_{m} · p. Let c = |{t ∈ {1, 2, …, n − 1} : a_{t} ≠ a_{t+1}} and let e = |{t ∈ {1, 2, …, m − 1} : b_{t} ≠ b_{t+1}}. Then a_{1} = b_{1}, a_{n} = b_{m},

and either a_{1} + a_{2} + … + a_{n} = b_{1} + b_{2} + … + b_{m} or (n − m)|\frac{e − c}{2}.

Proof. By Lemma 4.1, if a_{1} + a_{2} + … + a_{n} ≠ b_{1} + b_{2} + … + b_{m}, then p ∈ ⋂_{l=1}^{∞} \overline{ℕd^{l}} so that Theorem 4.5 applies.

We see in particular that if the coefficients alternate, they must match exactly.

Corollary 4.7. Let d ∈ ℕ\{1}, let p ∈ ℕ^{∗}, let a_{1}, a_{2}, …, a_{n}, b_{1}, b_{2}, …, b_{m} ∈ {1, d}, such that for all i ∈ {1, 2, …, n − 1} and all j ∈ {1, 2, …, m − 1}, a_{i} ≠ a_{i+1} and b_{j} ≠ b_{j+1}. If a_{1} · p + a_{2} · p + … + a_{n} · p = b_{1} · p + b_{2} · p + … + b_{m} · p, then n = m and for all i ∈ {1, 2, …, n}, a_{i} = b_{i}.

Proof. Let c = |{t ∈ {1, 2, …, n−1} : a_{t} ≠ a_{t+1}} and let e = |{t ∈ {1, 2, …, m−1} : b_{t} ≠ b_{t+1}}. Then c = n−1 and e = m−1 and so e−c = m−n. By Corollary 4.6, either a_{1} +a_{2} +…+a_{n} = b_{1} + b_{2} + … + b_{m} or (n − m)|\frac{n − m}{2}. In either case we conclude that n = m. Since also a_{1} = b_{1} we have that for all i ∈ {1, 2, …, n}, a_{i} = b_{i}.

Notice also that Corollary 4.6 tells us that many equations whose coefficients do not alternate have no solutions. For example, there is no p ∈ ℕ^{∗} such that p + p = p + 2 · p + p + 2 · p + p. On the other hand we no not know whether there exist solutions to p+p+p = p+2·p+p+2·p+p. Nor do we know whether p + p + 2 · p + 2 · p = p + 2 · p + p + 2 · p has any solutions (although Theorem 4.5 tells us there are no solutions with p ∈ ⋂_{l=1}^{∞} \overline{ℕd^{l}}).

There are other equations which we know can be solved by idempotents such as p+p+2·p = p + 2 · p for example, and we would conjecture that these are the only solutions. We know, of course, that there are equations in βℕ only solvable by idempotents. Trivially p + p = p is one such. Much less trivial is the fact that p + p + p = p implies that p is an idempotent. (Indeed, if p + p + p = p, then {p, p + p} forms a subgroup of ℕ^{∗} and the very difficult Zelenuk’s Theorem [5, Theorem 7.17] asserts that the only finite subgroups of ℕ^{∗} are singletons.) It is unknown whether there exists any p ≠ p + p such that p + p + p = p + p. The existence of such p is equivalent to the existence of a nontrivial continuous homomorphism from βℕ to ℕ^{∗} [5, Corollary 10.20].

Similarly, we do not know whether the equation p + p + 2 · p = p + 2 · p has any solutions in ℕ^{∗} besides idempotents. It is a consequence of Theorem 4.8 that there are no such solutions with p ∈ K(βℕ), the smallest ideal of βℕ.

Theorem 4.8. Let p ∈ K(βℕ) and let q ∈ βℕ. If p + p + q = p + q, then p + p = p.

Proof. Pick by [5, Theorem 2.8] a minimal left ideal L and a minimal right ideal R of βℕ with p ∈ R ∩ L. By [5, Theorem 2.7], R ∩ L is a group. Let e be the identity of R ∩ L and let r be the inverse of p in R ∩ L. By [5, Theorem 1.46], L + q is a minimal left ideal of βℕ and e + q ∈ L + q so by [5, Theorem 2.11(c)], ρ_{e+q|L} is a homeomorphism from L onto L + q. Since ρ_{e+q}(p) = p + e + q = e + p + q = r + p + p + q = r + p + q = e + q = e + e + q = ρ_{e+q}(p), we have that p = e.

References

[1] V. Bergelson and N. Hindman, Additive and multiplicative Ramsey Theorems in ℕ – some elementary results, Comb. Prob. and Comp. 2 (1993), 221-241.

[2] W. Deuber, N. Hindman, I. Leader, and H. Lefmann, Infinite partition regular matrices, Combinatorica 15 (1995), 333-355.

[3] L. Fuchs, Abelian groups, Pergamon Press, Oxford, 1960.

[4] N. Hindman, Partitions and sums and products of integers, Trans. Amer. Math. Soc. 247 (1979), 227-245.

[5] N. Hindman and D. Strauss, Algebra in the Stone-Čech compactification – theory and applications, Walter de Gruyter, Berlin, 1998.

[6] A. Maleki, Solving equations in βℕ, Semigroup Forum, to appear.