Abelian Groups with Layered Tiles and the Sumset Phenomenon^{∗}^{†}

Renling Jin^{‡} Department of Mathematics College of Charleston Charleston, SC 29424

              jinr@cofc.edu

H. Jerome Keisler^{§} Department of Mathematics University of Wisconsin Madison, WI 53706

                                      keisler@math.wisc.edu

June 21, 2002

Abstract

We prove a generalization of the main theorem in [4] about the sumset phenomenon in the setting of an abelian group with layered tiles of cell measures. Then we give some applications of the theorem for multi–dimensional cases of the sumset phenomenon. Several examples are given in order to show that the applications obtained are not vacuous and cannot be improved in various directions. We also give a new proof of Shnirel’man’s theorem to illustrate a different approach to some combinatorial problems which uses the sumset phenomenon.

0 Introduction

A theorem in nonstandard analysis was proved in [4] in order to answer a question posed by Keisler and Leth in [5]. This theorem implies many results in standard mathematics which reveal a general principle called the sumset phenomenon: if A and B are large in terms of “measure”, then A + B is not small in terms of “order– topology”.

∗2000 Mathematics Subject Classification. Primary 20K99, 60B15, 22A05, 03H05, Secondary 11B05, 26E35, 28E05.

†Key words and phrases. abelian group, layered tiles of cell measures, the sumset phenomenon, upper Banach density.

‡Research is supported in part by NSF grant DMS#0070407.

§Research is supported in part by Vilas Trust Fund.

In §1 of this paper, we generalize [4, Theorem 1] to the setting of abelian groups with layered tiles of cell measures. The new generalization makes the applications in §2 to multi–dimensional cases easier. These applications show that the description of the sumset phenomenon needs to be adjusted with “measure” replaced by “product measure” and “order–topology” replaced by “product of order–topology”. In §3, we construct several examples to show that the results about the sumset phenomenon in §2 and in [4] cannot be improved in various directions. For example, it was proven in [4] that if A and B are two subsets of the natural numbers with positive upper Banach density, then A+B is piecewise syndetic, which means that there exists a fixed positive integer k such that A+B +{0, 1, …, k} is thick. It is natural to ask whether the least such k is related to the upper Banach density of A and the upper Banach density of B. One example constructed in §3 shows that k is not directly related to these upper Banach densities. In §4, a new proof of Shnirel’man’s theorem is given, which uses the idea of the sumset phenomenon rather than a finite combinatorial argument. In §5, two questions are raised.

1 Groups with Layered Tiles of Cell Measures

Let (G, +) be an abelian group. We often write G for (G, +). For any A, B ⊆ G and g ∈ G, we write A ± B = {a ± b : a ∈ A and b ∈ B}, −A = {−a : a ∈ A}, g ± A = {g} ± A, and A ± g = A ± {g}. The lower case Greek letters α, β, γ, δ, ε will always denote standard real numbers.

Definition 1.1 Given a set C ⊆ G such that 0 ∈ C = −C, a C–cell is a set D of the form C + g for some g ∈ G. D is called the translation of C by g, and g is called the center of D.

A cell measure on G is a pair (C, λ) such that 0 ∈ C = −C, λ is a finitely additive measure on a Boolean algebra B of subsets of G (called λ–measurable sets), C ∈ B, λ(C) = 1, and λ is invariant under translations and reflections, that is, for each set A ∈ B and each g ∈ G, A + g ∈ B, −A ∈ B, and λ(A) = λ(A + g) = λ(−A).

A cell measure tiling on G is a triple (C, λ, T ) such that (C, λ) is a cell measure, T is a pairwise disjoint family of C–cells such that the set of centers of cells in T is a subgroup G_{T} of G, and for each λ–measurable set B, the set T (B) = ⋃{E ∈ T : E ⊆ B} is λ–measurable.

Here are some easy consequences of the definition.

Lemma 1.2 Suppose (C, λ, T ) is a cell measure tiling and D is a C–cell. (i) For each g ∈ G, D + g and −D are C–cells. (ii) D − D = C − C. (iii) λ(D) = 1. (iv) If D ∈ T and g ∈ G_{T}, then D + g ∈ T and −D ∈ T .

(v) If A, B are λ-measurable, the set

T (A, B) = ⋃{E ∈ T (B) : E ∩ A ≠ ∅}

is λ–measurable, and

A ∩ T (B) ⊆ T (A, B) ⊆ T (B) ⊆ B.

Proof We have D = C + h for some h ∈ G.

(i) D + g = (C + h) + g = C + (h + g), and −D = −(C + h) = −C − h = C − h. (ii) D − D = (C + h) − (C + h) = (C − C) + (h − h) = C − C. (iii) Because λ is invariant under translations. (iv) Note that h ∈ G_{T} and use the proof of (i).

(v) T (A, B) = T (B) ∖ T (B ∖ A). □

For a simple example of a cell measure tiling, let d be a positive integer, let G be the Euclidean vector space ℝ^{d}, and let C be the open d-cube (−1/2, 1/2)^{d}. Then the set of C–cells is the set of all open d–cubes of side one. Now let λ be the d-th product of Lebesgue measure and let T be the set of C–cells whose center is a d– tuple of integers. Then (C, λ, T ) is a cell measure tiling on G, and G_{T} is the subgroup G_{T} = ℤ^{d}. Further examples will appear later on in this paper.

In this paper (P, ⩽) always denotes a downward directed partial order with no least element. (A partial order is called downward directed if for any two elements p and q, there is an r with r ⩽ p and r ⩽ q.) We say that each sufficiently small s ∈ P has property X if there exists t ∈ P such that each s < t has property X. Since P is downward directed, if all sufficiently small s ∈ P have a property X and all sufficiently small s ∈ P have property Y, then all sufficiently small s ∈ P have property (X and Y).

Here is the key definition in this paper.

Definition 1.3 An abelian group G has layered tiles of cell measures of type P if there is a real number δ ∈ (0, 1) and a family of cell measure tilings {(C_{r}, λ_{r}, T_{r}) : r ∈ P } such that the following hold for all r ∈ P.

1. For each s ∈ P, λ_{s} and λ_{r} have the same measurable sets.

2. If s < r then C_{s} ⊆ C_{r}.

3. There exists s < r such that C_{s} − C_{s} ⊆ C_{r}.

4. For every real ε > 0, and for every sufficiently small s ∈ P:

(a) For each C_{r}–cell C, λ_{r}(C ∖ T_{s}(C)) < ε.

(b) For each C_{r}–cell C and measurable set A, λ_{r}(A ∩ T_{s}(C)) ⩽ αλ_{r}(T_{s}(A, C)) where α = sup{λ_{s}(E ∩ A) : E is a C_{s}–cell }.

(c) For all C_{r}–cells C, D such that the center of D is in C, λ_{r}(T_{s}(C ∩D)) ⩾ δ.

Remarks (1) The reader might want to keep a concrete example in mind in order to better grasp the idea. For example, one can think of G as the group ℝ^{2} with vector addition, P as the set of all pairs of positive real numbers with the partial order

(s, t) ⩾ (s′, t′) iff s ⩾ s′ and t ⩾ t′,

C_{(s,t)} as the open rectangle (−s, s) × (−t, t), λ_{(s,t)} = (4st)^{−1}λ where λ is Lebesgue measure, and T_{(s,t)} as the set of C_{(s,t)}–cells with centers {(2sm, 2tn) : m, n ∈ ℤ}.

(2) The word “layer” is used because one can think of the C_{r}–cells as a layer of cells at level r.

(3) Condition 4 (a) says that each C_{r}–cell is tiled by C_{s}–cells in the set T_{s} with an error less than ε.

(4) Condition 4 (b) says that if A has density at most α within each tile, then A has density at most α within the union of the tiles which meet A.

(5) Condition 4 (c) says that the union of the tiles inside C ∩ D has measure at least δ. The constant δ is independent of r and is a lower bound for the overlap between nearby cells. In the example in (1) above, one can take δ = 1/5.

(6) We define layered tiles of cell measures on an abelian group for convenience only. One can define the concept on a non–abelian group, but we have not yet seen any interesting applications of that case.

Let ℂ = {C_{r} : r ∈ P }, Λ = {λ_{r} : r ∈ P }, and 𝕋 = {T_{r} : r ∈ P }. We write (G, +, ℂ, Λ, 𝕋, δ) for a group with layered tiles of cell measures (C_{r}, λ_{r}, T_{r}) of type P and overlap constant δ. For the rest of this section, we fix such an abelian group (G, +, ℂ, Λ, 𝕋, δ). We also let C_{r} be the set of all C_{r}–cells.

Definition 1.4 A set A ⊆ G is called Λ–measurable if it is λ_{r}–measurable for some r ∈ P. For a Λ–measurable set A ⊆ G, the upper Banach density of A, BD_{Λ}(A), is defined by:

BD_{Λ}(A) = sup{λ_{r}(A ∩ C) : r ∈ P, C ∈ C_{r}}.

Definition 1.5 A set A ⊆ G is called ℂ–nowhere dense if for every r ∈ P and every C ∈ C_{r}, there exists an s < r and a D ∈ C_{s} such that D ⊆ C and D ∩ A = ∅.

Note that the definition of ℂ–nowhere denseness does not mention any measure in Λ. We prove two more easy lemmas.

Lemma 1.6 Let A be Λ–measurable and g ∈ G. Then

BD_{Λ}(A) = BD_{Λ}(A + g) = BD_{Λ}(−A).

If A is ℂ–nowhere dense, then so are A + g and −A.

Proof This follows from the fact that each measure λ_{r} is invariant under translations and reflections. □

Lemma 1.7 Let A be a Λ–measurable set with BD_{Λ}(A) > γ. Then for each sufficiently small s ∈ P there is a C_{s}-cell E such that λ_{s}(A ∩ E) > γ.

Proof By the definition of BD_{Λ} one can find an r ∈ P and a C_{r}–cell C such that λ_{r}(A ∩ C) > γ. Let

ε = λ_{r}(A ∩ C) − γ.

Each sufficiently small s ∈ P satisfies Definition 1.3 part 4 with respect to r and ε. Let

α = sup{λ_{s}(A ∩ E) : E ∈ C_{s}}.

We have T_{s}(A, C) ⊆ C, so λ_{r}(T_{s}(A, C)) ⩽ λ_{r}(C) = 1. Then by 4 (b),

λ_{r}(A ∩ T_{s}(C)) ⩽ αλ_{r}(T_{s}(A, C)) ⩽ α.

Moreover,

A ∩ C ⊆ (A ∩ T_{s}(C)) ∪ (C ∖ T_{s}(C)).

Therefore

γ + ε = λ_{r}(A ∩ C) ⩽ λ_{r}(A ∩ T_{s}(C)) + λ_{r}(C ∖ T_{s}(C)) < α + ε.

Then α > γ, so there is a C_{s}-cell E such that λ_{s}(A ∩ E) > γ. □

Next we state and prove the main theorem of the paper.

Theorem 1.8 Let (G, +, ℂ, Λ, 𝕋, δ) be an abelian group with layered tiles of cell measures of type P. Let A and B be Λ–measurable subsets of G. If BD_{Λ}(A) > 0 and BD_{Λ}(B) > 0, then A + B is not ℂ–nowhere dense.

Proof Assume that the theorem is not true. We will derive a contradiction. First we define two numbers α and β. Let

α = sup{BD_{Λ}(A) : A ⊆ G is Λ–measurable and

there is a Λ–measurable B ⊆ G with BD_{Λ}(B) > 0 such that A + B is ℂ–nowhere dense }.

Note that α is a positive real number by the assumption that the theorem is not true. Fix a positive real number

α_{0} < \frac{αδ}{3}  (1)

and let

β = sup{BD_{Λ}(B) : B ⊆ G is Λ–measurable and

there is a Λ–measurable A ⊆ G with BD_{Λ}(A) > α − α_{0} such that A + B is ℂ–nowhere dense }.

It is easy to see that β is positive and β ⩽ α. Again fix a positive real number

β_{0} < \frac{βδ}{3} .  (2)

We also fix two Λ–measurable sets A, B ⊆ G such that

BD_{Λ}(A) > α − α_{0}, BD_{Λ}(B) > β − β_{0},

and A + B is ℂ–nowhere dense. It follows from the definitions of α and β that BD(A) ⩽ α and BD(B) ⩽ β. By Lemma 1.7, for each sufficiently small r ∈ P there are C_{r}–cells C, D such that

λ_{r}(A ∩ C) > α − α_{0} and λ_{r}(B ∩ D) > β − β_{0}.  (3)

By Lemma 1.6, we may assume that C = C_{r}.

We have D ⊆ C +D because 0 ∈ C. Since A+B is ℂ–nowhere dense, there exists t < r and a C_{t}–cell F ⊆ D such that F ∩ (A + B) = ∅. Let g be the center of D and let f be the center of F, whence D = C + g and F = C_{t} + f.

Let

ε = min (\frac{α_{0}}{2} , \frac{β_{0}}{2} ) .  (4)

Each sufficiently small s ∈ P satisfies Definition 1.3 part 4 for ε, r, and also satisfies s < t and C_{s} − C_{s} ⊆ C_{t}. Then for each E ∈ T_{s} we have E − E + f = C_{s} − C_{s} + f ⊆ C_{t} + f = F, so E − E + f is disjoint from A + B. It follows that

T_{s}(A, C) ∩ T_{s}(f − B, f − D) = ∅,

because if a C_{s}–cell E met both A and f − B, then f − E would meet B, and hence E − E + f would meet A + B.

We have f ∈ F ⊆ C + g, so f = c + g for some c ∈ C, and therefore f − g ∈ C. The C_{r}–cell with center f − g is f − (C + g) = f − D. By 1.3 part 4 (c),

λ_{r}(T_{s}(C ∩ (f − D))) ≥ δ.

It follows that at least one of the sets

T_{s}(C ∩ (f − D)) ∖ T_{s}(A, C), T_{s}(C ∩ (f − D)) ∖ T_{s}(f − B, f − D)

has λ_{r}–measure at least δ/2.

Suppose first that

λ_{r}( T_{s}(C ∩ (f − D)) ∖ T_{s}(A, C) ) ⩾ \frac{δ}{2}.

Then

λ_{r}(T_{s}(A, C)) ⩽ 1 − \frac{δ}{2}.

We have

sup{λ_{s}(A ∩ E) : E ∈ C_{s}} ⩽ BD_{Λ}(A) ⩽ α.

By part 4 (b) of Definition 1.3,

λ_{r}(A ∩ T_{s}(C)) ⩽ αλ_{r}(T_{s}(A, C)).

Since

A ∩ C ⊆ (A ∩ T_{s}(C)) ∪ (C ∖ T_{s}(C)),

we have

λ_{r}(A ∩ C) ⩽ αλ_{r}(A ∩ T_{s}(C)) + λ_{r}(C ∖ T_{s}(C)) < α (1 − \frac{δ}{2}) + ε.

Using (1), (3), and (4), we get the contradiction

α − α_{0} < α (1 − \frac{δ}{2}) + ε < α (1 − \frac{3α_{0}}{2α} ) + \frac{α_{0}}{2} = α − α_{0}.

Now suppose that

λ_{r}( T_{s}(C ∩ (f − D)) ∖ T_{s}(f − B, f − D) ) ⩾ \frac{δ}{2}.

Then

λ_{r}(T_{s}(f − B, f − D)) ⩽ 1 − \frac{δ}{2}.

By repeating the above argument with (f −B, f −D, β) instead of (A, C, α), we again get a contradiction. This completes the proof. □

2 The Sumset Phenomenon

In this section we apply Theorem 1.8 to obtain new examples of the sumset phenomenon for multi–dimensional cases. Let ℕ, ℤ, and ℝ denote the set of all natural numbers including 0, all integers, and all real numbers, respectively. From now on we fix a positive integer d for the dimension of a space. In some applications we work within a countably saturated nonstandard universe ^{∗}V. The reader is assumed to have enough basic knowledge of nonstandard analysis to understand these applications. For more information on nonstandard analysis consult [6],[7], or §4.4 of [2]. For any standard set A, the set ^{∗}A is always the nonstandard version of A in ^{∗}V. For an abelian group (G, +), we also use + for the addition on the product group G^{d}, i.e, (f_{0}, f_{1}, …, f_{d−1}) + (g_{0}, g_{1}, …, g_{d−1}) = (f_{0} + g_{0}, f_{1} + g_{1}, …, f_{d−1} + g_{d−1}). In the first two applications, an interval means an interval of real numbers.

Application 2.1 Let ν be the Lebesgue measure on ℝ and ν^{d} be the d–dimensional product of ν on ℝ^{d}. Let A, B ⊆ ℝ^{d} be such that ν^{d}(A) > 0 and ν^{d}(B) > 0. Then A + B contains a non–empty open ball.

Proof It is sufficient to show that A + B contains a non–empty d–dimensional open cube. Without loss of generality, we can assume that A and B are compact subsets of ℝ^{d}, because every set of positive ν^{d}–measure contains a compact subset of positive ν^{d}–measure. Since A + B is closed, it is enough to prove that A + B is not nowhere dense.

Let G = (ℝ^{d}, +). We now define the layered tiles of cell measures of type P. Let P be the set of all positive real numbers with the natural order. For each r ∈ P let C_{r} = (−r, r)^{d}. Then C_{r} is the set of all d–dimensional open cubes with sides of length 2r. Let λ_{r} = (2r)^{−d}ν^{d}, and let T_{r} be the set of all C_{r}–cells with centers (2rm, 2rn) where m, n ∈ ℤ. Let ℂ = {C_{r} : r ∈ P }, Λ = {λ_{r} : r ∈ P }, and 𝕋 = {T_{r} : r ∈ P }, and let δ = 2^{−d−1}. It is clear that (ℝ^{d}, +, ℂ, Λ, 𝕋, δ) is a group with layered tiles of cell measures of type P, since the each tiling T_{r} is countable. It is easy to see that BD_{Λ}(A) > 0 and BD_{Λ}(B) > 0. Therefore by Theorem 1.8, A + B is not nowhere dense. □

We now use the nonstandard reals to construct another group with layered tiles of cell measures. Let ^{∗}ℝ be the additive group of hyperreal numbers, which is the nonstandard version of the usual additive group of real numbers in ^{∗}V.

A set U of non–negative elements of ^{∗}ℝ is called a cut in ^{∗}ℝ if:

(1) 0 ∈ U,

(2) If y ∈ U and 0 ⩽ x < y, then x ∈ U, and

(3) U + U ⊆ U.

Note that {0} and {r ∈ ^{∗}ℝ : r ⩾ 0} are cuts in ^{∗}ℝ. Let U be a cut in ^{∗}ℝ and r be an element of ^{∗}ℝ. We write r > U if r > s for every s ∈ U. A cut U in ^{∗}ℝ is upper bounded if r > U for some r ∈ ^{∗}ℝ. For convenience we consider only upper bounded cuts in ^{∗}ℝ in the next application. Let ^{∗}(ν^{d}) be the nonstandard version of ν^{d} and let st be the standard part map from ^{∗}ℝ to ℝ ∪ {∞}.

A cut in ^{∗}ℝ^{d} is an d-tuple U = (U_{0}, U_{1}, …, U_{d−1}) of upper bounded cuts in ^{∗}ℝ. Given a cut U and an element r = (r_{0}, …, r_{d−1}) in ^{∗}ℝ^{d}, r > U means that r_{j} > U_{j} for j = 0, …, d − 1. A U–box is a set of the form ∏_{j=0}^{d−1}(a_{j}, b_{j}) where b_{j} − a_{j} > U_{j} for each j. A set A ⊆ ^{∗}ℝ^{d} is called U–nowhere dense if for every U–box C, there is another U–box D such that D ⊆ C and D ∩ A = ∅.

Application 2.2 Let A, B ⊆ ^{∗}ℝ^{d} be internal sets and let U be a cut in ^{∗}ℝ^{d}. If there exist two U–boxes C and D such that

st (\frac{^{∗}(ν^{d})(A ∩ C)}{^{∗}(ν^{d})(C)}) > 0 and st (\frac{^{∗}(ν^{d})(B ∩ D)}{^{∗}(ν^{d})(D)}) > 0,

then A + B is not U–nowhere dense.

Proof Let G = ^{∗}ℝ^{d}. Let

P = {r ∈ ^{∗}ℝ^{d} : r > U}.

For any r, s ∈ P, define r ⩽ s by r_{j} ⩽ s_{j} for j = 0, 1, …, d−1. Then P is a downward directed partial ordering. For each r ∈ P let

C_{r} = ∏_{j=0}^{d−1}(−r_{j}, r_{j}).

Let B be the Boolean algebra of all internal ^{∗}(ν^{d})–measurable sets, and define λ_{r} by

λ_{r}(D) = st (\frac{^{∗}(ν^{d})(D)}{^{∗}(ν^{d})(C_{r})})

for each D ∈ B. Then each λ_{r} is a finitely additive measure on B. Let the tiling T_{r} be the set of all C_{r}–cells with centers (2r_{0}z_{0}, …, 2r_{d−1}z_{d−1}) where z_{0}, …, z_{d−1} ∈ ^{∗}ℤ.

Let ℂ = {C_{r} : r ∈ P }, Λ = {λ_{r} : r ∈ P }, 𝕋 = {T_{r} : r ∈ P }, and δ = 2^{−d−1}. It is easy to see that BD_{Λ}(A) > 0 and BD_{Λ}(B) > 0. By Theorem 1.8, it suffices to verify that (^{∗}ℝ^{d}, +, ℂ, Λ, 𝕋, δ) is an abelian group with layered tiles of cell measures of type P. Parts (1)–(3) of Definition 1.3 are clear. For part 4, let ε > 0 be real and r ∈ P. For each s ∈ P, the set T_{s} is internal and ^{∗}countable, i.e., countable in the sense of the nonstandard universe. Take an integer k such that d/k < ε. Then for any s < r/k in P, part 4 of the definition follows by the transfer principle. In particular, for part 4 (b), consider any real β > α where α = sup{λ_{s}(E ∩ A) : E ∈ C_{s}}. We have

∗(ν^{d})(E ∩ A) < β ·^{∗}(ν^{d})(C_{s})

for each E ∈ C_{s}, and therefore for any C_{r}–cell C

\frac{^{∗}(ν^{d})(A ∩ T_{s}(C))}{^{∗}(ν^{d})(C_{r})} < \frac{β ·^{∗}(ν^{d})(T_{s}(A, C))}{^{∗}(ν^{d})(C_{r})}.

Taking standard parts,

λ_{r}(A ∩ T_{s}(C)) ⩽ β · λ_{r}(T_{s}(A, C)).

Since this holds for all β > α, we get the desired inequality

λ_{r}(A ∩ T_{s}(C)) ⩽ α · λ_{r}(T_{s}(A, C)). □

For the rest of this section we deal with the abelian group ^{∗}ℤ, which is the nonstandard counterpart of the abelian group ℤ of integers under addition. From now on, by an interval we mean an interval in ^{∗}ℤ. An element K ∈ ^{∗}ℕ ∖ ℕ is called a hyperfinite integer. A set S is called hyperfinite if S is internal and the internal cardinality of S is a hyperfinite integer (that is, S is ^{∗}finite but not finite). For a hyperfinite set S let Σ_{S} be the collection of all internal subsets of S. The set Σ_{S} is also a hyperfinite set. Then one can define a normalized counting measure μ^{S} on Σ_{S} (or simply on S) by putting μ^{S}(F) = |F |/|S| for each nonempty F ∈ Σ_{S}. Now st ∘ μ^{S} is a finitely additive standard probability measure defined on Σ_{S}.

A set U ⊆ ^{∗}ℕ is called a cut in ^{∗}ℕ if U is an infinite initial segment of ^{∗}ℕ and U + U ⊆ U. Note that U = ℕ is the smallest cut and ^{∗}ℕ is the largest cut. For convenience we always assume U ≠ ^{∗}ℕ. Given a positive integer d, a cut in ^{∗}ℕ^{d} is a d-tuple U = (U_{0}, U_{1}, …, U_{d−1}) of cuts in ^{∗}ℕ. As before, U < r means that u < r for all u ∈ U, and U < r means that U_{j} < r_{j} for j = 0, …, d − 1. A product of intervals of the form ∏_{j=0}^{d−1}(a_{j}, b_{j}) ⊆ ^{∗}ℤ^{d} is called a U–box if b_{j} − a_{j} > U_{j} for each j. A set A ⊆ ^{∗}ℤ^{d} is called U–nowhere dense if for every U–box C there is a U–box D such that D ⊆ C ∖ A.

In the one dimensional case d = 1, a U–box is just an interval (a, b) such that b − a > U. In this case, it is sometimes convenient to borrow the gap function notation from [5]. Let A ⊆ ^{∗}ℤ be internal and let C be a U–box. Then the length of the largest gap of A in C is

Gap(A, C) = max{|D| : D is a U–box and D ⊆ C ∖ A}.

Thus an internal set A is U–nowhere dense iff for every U-box C, Gap(A, C) > U.

Application 2.3 Let A, B ⊆ ^{∗}ℤ^{d} be internal sets and let U be a cut in ^{∗}ℕ^{d}. If there are U–boxes C and D such that st(μ^{C}(A ∩ C)) > 0 and st(μ^{D}(B ∩ D)) > 0, then A + B is not U–nowhere dense.

In the one dimensional case, the conclusion says that for some U–box E, Gap(A + B, E) ∈ U.

Proof Let P = {r ∈ ^{∗}ℕ^{d} : r > U}. We again define r ⩽ s by r_{j} ⩽ s_{j} for j ∈ [0, d − 1], and P is downward directed. Let G be the abelian group ^{∗}ℤ^{d}. For each r ∈ P let

C_{r} = ∏_{j=0}^{d−1}(−r_{j}, r_{j})

and let ℂ = {C_{r} : r ∈ P }. Let λ_{r} be the finitely additive measure defined on the class of all internal subsets X of ^{∗}ℤ^{d} by the rule

λ_{r}(X) = st (\frac{|X|}{|C_{r}|}) ,

so that λ_{r}(C_{r}) = 1. Let Λ = {λ_{r} : r ∈ P }. Let T_{r} be the set of all C_{r}–cells with centers of the form (2r_{0}z_{0}, …, 2r_{d−1}z_{d−1}) where z_{0}, …, z_{d−1} ∈ ^{∗}ℤ, and let 𝕋 = {T_{r} : r ∈ P }. Let δ = 2^{−d−1}.

It is again easy to see that BD_{Λ}(A) > 0 and BD_{Λ}(B) > 0. Using the same argument as in Application 2.2, one can show that (^{∗}ℤ^{d}, +, ℂ, Λ, 𝕋, δ) is an abelian group with layered tiles of cell measures of type P. The desired result now follows from Theorem 1.8. □

Next we derive a variation of Application 2.3. Let H be a hyperfinite integer, let ^{∗}ℤ_{H} = [0, H − 1], and let ⊕ be the usual addition modulo H. Then (^{∗}ℤ_{H}, ⊕) is an abelian group. We also use ⊕ for the addition on the finite Cartesian product (^{∗}ℤ_{H})^{d} as usual. Let μ^{H} be the normalized counting measure on (^{∗}ℤ_{H})^{d}. For each j ∈ [0, d − 1] let U_{j} ⊆ ^{∗}ℤ_{H} be a cut in ^{∗}ℕ. Note that a cut U ⊆ ^{∗}ℤ_{H} is a relatively small subset of ^{∗}ℤ_{H} because U < H/m for any standard positive integer m. The definition of U–nowhere denseness of a set A ⊆ (^{∗}ℤ_{H})^{d} is exactly the same as before.

Application 2.4 Let A, B ⊆ (^{∗}ℤ_{H})^{d} be two internal sets. If st(μ^{H}(A)) > 0 and st(μ^{H}(B)) > 0, then A ⊕ B is not U–nowhere dense.

Proof By Application 2.3, it suffices to show that A ⊕ B is U–nowhere dense iff A + B is U–nowhere dense. This follows from the fact that

A ⊕ B = ⋃{F_{h} − c_{h} : h ∈ {0, 1}^{[0,d−1]}},

where F_{h} and c_{h} are defined by the following:

Let E_{0} = ^{∗}ℤ_{H} and E_{1} = ^{∗}ℤ_{2H} ∖ ^{∗}ℤ_{H} and let c_{0} = 0 and c_{1} = H. For each function h from [0, d − 1] to {0, 1}, define F_{h} = ∏_{j=0}^{d−1}(E_{h(j)} ∩ (A + B)) and c_{h} = (c_{h(o)}, c_{h(1)}, …, c_{h(d−1)}). □ Remark The main theorem in [4] is a special case of Application 2.4 for dimension d = 1.

The next result is in the standard world. Let A be a subset of ℕ^{d}. The set A ⊆ ℕ^{d} is called thick if for any m, there is an r ∈ ℕ^{d} such that r + [0, m]^{d} ⊆ A. The set A ⊆ ℕ^{d} is called piecewise syndetic if there is a k ∈ ℕ such that A+[0, k]^{d} is thick. The upper Banach density of A, BD(A), is defined by:

BD(A) = lim_{k→∞} sup \{\frac{|A ∩ E|}{|E|} : E = r + [0, k]^{d} for r ∈ ℕ^{d}\} .

Application 2.5 Let A, B ⊆ ℕ^{d}. If BD(A) > 0 and BD(B) > 0, then A + B is piecewise syndetic.

Proof For each j ∈ [0, d − 1], let U_{j} = ℕ and let U = (U_{0}, U_{1}, …, U_{d−1}). By the transfer principle and BD(A) ⩾ α, there is a hyperfinite integer K and an r ∈ ^{∗}ℕ^{d} such that

st (\frac{|^{∗}A ∩ (r + [0, K]^{d})|}{(K + 1)^{d}}) ⩾ α.

Therefore st(μ^{C}(^{∗}A)) ≥ α > 0 where C = [0, K]^{d}. The same holds for ^{∗}B. Thus by Application 2.3, ^{∗}A+^{∗}B is not U–nowhere dense. It follows that there is a hyperfinite integer K and an r ∈ ^{∗}ℕ^{d} such that there is no U–box E ⊆ (r + [0, K]^{d}) ∖ (^{∗}A +^{∗}B). Define

k = max{m ∈ ^{∗}ℕ : (∃ s ∈ ^{∗}ℕ^{d}) s + [0, m − 1]^{d} ⊆ (r + [0, K]^{d}) ∖ (^{∗}A +^{∗}B))}.

Then k must be finite. Therefore r + [0, K − k]^{d} ⊆ ^{∗}A +^{∗}B − [0, k]^{d}, and hence

r + [k, K]^{d} ⊆ ^{∗}A +^{∗}B + [0, k]^{d}.

This implies that A + B is piecewise syndetic. □ Remark Application 2.5 is a multi-dimensional generalization of [4, Corollary 3], which is a complementary result to the following result in [3]: If A ⊆ ℕ has positive upper Banach density, then (A − A) ∩ ℕ is syndetic.

When A = B, the result above can be improved. For simplicity, we consider only the one dimensional case.

Application 2.6 Let A ⊆ ℕ and BD(A) = α > 0. For any sequence of intervals ⟨[a_{i}, b_{i}] : i ∈ ℕ⟩ with lim_{i→∞}(b_{i} − a_{i}) = ∞ such that

lim_{i→∞} \frac{|A ∩ [a_{i}, b_{i}]|}{b_{i} − a_{i} + 1} = α

and for any β ∈ (0, 2), there is a sequence of intervals ⟨[c_{i}, d_{i}] : i ∈ ℕ⟩ and there is a k ∈ ℕ such that [c_{i}, d_{i}] ⊆ [2a_{i}, 2b_{i}],

lim inf_{i→∞} \frac{d_{i} − c_{i}}{b_{i} − a_{i}} ⩾ β,

and

⋃_{i∈ℕ}[c_{i}, d_{i}] ⊆ A + A + [0, k].

Proof By the transfer principle, for every hyperfinite integer K, one has

st (\frac{|^{∗}A ∩ [a_{K}, b_{K}]|}{b_{K} − a_{K} + 1}) = α.  (5)

Therefore, by Application 2.3, ^{∗}A +^{∗}A is not ℕ–nowhere dense. Choose [c′_{K}, d′_{K}] ⊆ [2a_{K}, 2b_{K}] such that

\frac{2 − β}{3} < \frac{c′_{K} − 2a_{K}}{b_{K} − a_{K}} < \frac{2 − β}{2} and \frac{2 − β}{3} < \frac{2b_{K} − d′_{K}}{b_{K} − a_{K}} < \frac{2 − β}{2} .

Then

2 = \frac{2b_{K} − 2a_{K}}{b_{K} − a_{K}} = \frac{d′_{K} − c′_{K}}{b_{K} − a_{K}} + \frac{2b_{K} − d′_{K}}{b_{K} − a_{K}} + \frac{c′_{K} − 2a_{K}}{b_{K} − a_{K}} ⩽ \frac{d′_{K} − c′_{K}}{b_{K} − a_{K}} + 2 − β.

Hence one has

\frac{d′_{K} − c′_{K}}{b_{K} − a_{K}} ⩾ β.

Claim 2.6.1 There exists a k ∈ ℕ such that if [x, y] ⊆ [c′_{K}, d′_{K}] ∖ (^{∗}A + ^{∗}A), then y − x ⩽ k.

Proof of Claim 2.6.1 If the claim is not true, then there is an interval [x, y] ⊆ [2a_{K}, 2b_{K}] ∖ (^{∗}A + ^{∗}A) such that y − x > ℕ. Let H be a hyperfinite integer such that H^{2} < y − x. For simplicity we assume that H evenly divides a_{k}, b_{K}, and x. Let

m = max\{i ∈ ^{∗}ℕ : 2a_{K} + iH ⩽ b_{K}\} = \frac{b_{k} − a_{K}}{H} .

For each i ∈ [0, m − 1] let E_{i} = [a_{K} + iH, a_{K} + (i + 1)H − 1]. Whenever (i + j)H = x − 2a_{K}, we have E_{i} + E_{j} ⊆ [x, y], and therefore either

∗A ∩ E_{i} = ∅ or ^{∗}A ∩ E_{j} = ∅.

Since

x ⩾ c′_{K} > \frac{2 − β}{3} (b_{K} − a_{K}) + 2a_{K} and y ⩽ d′_{K} < 2b_{K} − \frac{2 − β}{3} (b_{K} − a_{K}),

then

st (\frac{x − 2a_{K}}{b_{K} − a_{K}} ) ⩾ \frac{2 − β}{3} and st (\frac{2b_{K} − y}{b_{K} − a_{K}} ) ⩾ \frac{2 − β}{3} .

It follows that [0, m − 1] contains a subinterval I such that st(|I|/m) > 0 and at least half of the points i ∈ I are such that ^{∗}A ∩ E_{i} = ∅. Therefore, in view of equation (5), there exists an i ∈ [0, m − 1] such that

st (\frac{|^{∗}A ∩ [a_{K} + iH, a_{K} + (i + 1)H − 1]|}{H}) > α.

By the transfer principle, one gets BD(A) > α, a contradiction. □(Claim 2.6.1)

By the claim one can find a k ∈ ℕ such that [c′_{K} + k, d′_{K} + k] ⊆ ^{∗}A + ^{∗}A + [0, k]. Let k_{K} be the smallest of these k’s. If the set {k_{K} : K is hyperfinite } is unbounded in ℕ, then by countable saturation, there is a hyperfinite k_{K} for some hyperfinite K. This contradicts that k_{K} is always finite. Hence k_{K} is upper bounded in ℕ. Let k be an upper bound and let c_{K} = c′_{K} + k and d_{K} = d′_{K} + k. Then

[c_{K}, b_{K}] ⊆ (^{∗}A + ^{∗}A + [0, k]) ∩ [2a_{K}, 2b_{K}]

for every hyperfinite integer K. By the underspill principle, there is a sequence ⟨[c_{i}, d_{i}] : i > i_{0}⟩ which satisfies the conclusion of Application 2.6 for i > i_{0}. For i ⩽ i_{0} simply let [c_{i}, d_{i}] = ∅; this completes the proof. □

Next we derive a multi–dimensional generalization of [4, Corollary 2]. Let (ℤ^{d})^{ℕ} denote the set of all functions from ℕ to ℤ^{d}. For any f, g ∈ (ℤ^{d})^{ℕ} let (f + g)(m) = f(m) + g(m). A set of the form S_{k} = ∏_{j=0}^{d−1}[a_{j}^{(k)}, b_{j}^{(k)}] ⊆ ℤ^{d} is called a box. A sequence of boxes ⟨S_{k} : k ∈ ℕ⟩ is called large if for each j ∈ [0, d−1], lim_{k→∞}(b_{j}^{(k)} −a_{j}^{(k)}) = ∞.

Application 2.7 For each k ∈ ℕ, let A_{k}, B_{k} ⊆ ℤ^{d}. If there are two large sequences of boxes ⟨S_{k} : k ∈ ℕ⟩ and ⟨T_{k} : k ∈ ℕ⟩ such that

lim inf_{k→∞} (\frac{|A_{k} ∩ S_{k}|}{|S_{k}|}) > 0, lim inf_{k→∞} (\frac{|B_{k} ∩ T_{k}|}{|T_{k}|}) > 0,

then there is a large sequence of boxes ⟨Q_{k} : k ∈ ℕ⟩ such that

lim inf_{k→∞}(Gap(A_{k} + B_{k}, Q_{k})) < ∞.

Proof Let F be a non–principal ultrafilter on ℕ. Suppose the nonstandard universe ∗V is obtained by taking the ultrapower of the standard universe V modulo F. Then ∗ℤ = ℤ^{ℕ}/F, the ultrapower of ℤ modulo F. Every element in ^{∗}V has the form [⟨a_{k} : k ∈ ℕ⟩], the equivalence class of ⟨a_{k} : k ∈ ℕ⟩ modulo F, where ⟨a_{k} : k ∈ ℕ⟩ is a sequence in a set S in V called a representative of the class. Let

U = {x ∈ ^{∗}ℕ : x < [⟨f(k) : k ∈ ℕ⟩] for every f ∈ ℕ^{ℕ} with lim_{k→∞} f(k) = ∞}.

Then U is a cut. Note that U = ℕ iff F is a so–called p–point. Let U = (U, U, …, U). It is easy to verify that [⟨P_{k} : k ∈ ℕ⟩] is a U–box iff it is represented by a large sequence of boxes. So [⟨S_{k} : k ∈ ℕ⟩] and [⟨T_{k} : k ∈ ℕ⟩] are U–boxes and

st (\frac{|[⟨A_{k} : k ∈ ℕ⟩] ∩ [⟨S_{k} : k ∈ ℕ⟩]|}{|[⟨S_{k} : k ∈ ℕ⟩]|}) > 0

and

st (\frac{|[⟨B_{k} : k ∈ ℕ⟩] ∩ [⟨T_{k} : k ∈ ℕ⟩]|}{|[⟨T_{k} : k ∈ ℕ⟩]|}) > 0.

Hence by Application 2.3, [⟨A_{k} + B_{k} : k ∈ ℕ⟩] is not U–nowhere dense. Now the conclusion follows from the fact that a large sequence of boxes ⟨R_{k} : k ∈ ℕ⟩ with R_{k} ∩ (A_{k} + B_{k}) = ∅ for all but finitely many k ∈ ℕ generates a U–box which is disjoint from [⟨A_{k} + B_{k} : k ∈ ℕ⟩]. □

3 Examples

In this section we give examples which show that the results obtained in §2 are not vacuous and cannot be improved in various directions. For convenience we only give examples in the one dimensional case. The first four examples show that the results obtained in §2 are not vacuous. The first example is well–known.

Example 3.1 For each 0 < α < 1, there is a compact subset A of the unit interval of the real line such that A is nowhere dense and the Lebesgue measure of A is greater than α.

The second example is from [5].

Example 3.2 Let α ∈ (0, 1). For any hyperfinite integer H and any cut U ⊆ [0, H − 1], there is an internal set A ⊆ [0, H − 1] with st(|A|/H) > α such that A is U– nowhere dense.

Example 3.3 For any α ∈ (0, 1), there is a set A ⊆ ℕ such that BD(A) ⩾ α and A is not piecewise syndetic.

Proof Let k_{0} ∈ ℕ be such that

∑_{k=k_{0}}^{∞} \frac{k}{2^{k}} < 1 − α.

For each k ⩾ k_{0} let

B_{k} = ⋃_{m=k_{0}}^{k} ⋃_{l=1}^{2^{k−m}}[l2^{m} − m, l2^{m} − 1].

Then B_{k} ⊆ [0, 2^{k} − 1] and

\frac{|B_{k}|}{2^{k}} ⩽ \frac{1}{2^{k}} ∑_{m=k_{0}}^{k} ∑_{l=1}^{2^{k−m}} m = ∑_{m=k_{0}}^{k} \frac{2^{k−m}m}{2^{k}} = ∑_{m=k_{0}}^{k} \frac{m}{2^{m}} < 1 − α.

Let A_{k} = [0, 2^{k} − 1] ∖ B_{k} and let

A = ⋃_{k=k_{0}}^{∞}(2^{k} − 2^{k_{0}} + A_{k}).

It is easy to check that BD(A) ⩾ α (in fact the Shnirel’man density of A is greater than or equal to α). Since every interval of length 2^{k+1} contains a subinterval of length at least k, which is disjoint from A, A is not piecewise syndetic. □

Example 3.4 For any α ∈ (0, 1) there is a sequence of sets ⟨A_{k} ⊆ [0, 2^{k} −1] : k ∈ ℕ⟩ with

inf \{\frac{|A_{k}|}{2^{k}} : k ∈ ℕ\} ⩾ α

such that for every large sequence of intervals (one–dimensional boxes) ⟨[a_{k}, b_{k}] : k ∈ ℕ⟩, one has

lim_{k→∞} Gap(A_{k}, [a_{k}, b_{k}]) = ∞.

Proof Let A_{k} be the same as in Example 3.3 for k ⩾ k_{0} and let A_{k} = [0, 2^{k} − 1] for k < k_{0}. It is easy to see that the sequence ⟨A_{k} ⊆ [0, 2^{k} − 1] : k ∈ ℕ⟩ has the required properties. □

The last four examples show that the results in §2 cannot be improved in various directions.

Example 3.5 Let H be a hyperfinite integer and let U, V ⊆ [0, H − 1] be two cuts with U ∖ V ≠ ∅. For any α < 1/2 there exist two internal sets A, B ⊆ [0, H − 1] such that st(|A|/H) ⩾ α, st(|B|/H) ⩾ α, and for any interval [a, b] with b − a > U,

Gap(A + B, [a, b]) > V.

Proof Let x ∈ U ∖ V. Define A and B by the following:

A = ⋃ \{[lx, [(l + α)x] − 1] : 0 ⩽ l ⩽ [\frac{H}{x} ] − 1\}

and B = A. It is easy to check that st(|A|/H) = st(|B|/H) = α. Since

A + B ⊆ ⋃ \{[lx, [(l + 2α)x] − 1] : 0 ⩽ l ⩽ 2 [\frac{H}{x} ] − 2\}

and 2α < 1, for any interval [a, b] with b − a > U one has

Gap(A + B, [a, b]) ⩾ [(1 − 2α)x] − 1 > V. □

Remark Using the same idea as in Example 3.2 and Example 3.6, one can modify the sets A and B in Example 3.5 to make them U–nowhere dense.

Look at Application 2.5 for the case of d = 1. Given two sets A, B ⊆ ℕ, if BD(A) > 0 and BD(B) > 0, then there is a m ∈ ℕ such that A + B + [0, m] is thick. It is easy to see that if BD(A) + BD(B) > 1, then A + B is already thick. So m = 0. Hence it is natural to guess that the number m may be related to BD(A) and BD(B). The next example uses an idea similar to Example 3.5 to show that this is not the case.

Example 3.6 For any α and β with α + β < 1 and for any m ∈ ℕ, there exist A, B ⊆ ℕ such that A and B are not piecewise syndetic, BD(A) ⩾ α, BD(B) ⩾ β, and A + B + [0, m] is not thick.

Proof Without loss of generality, we assume m ⩾ 1. Let ε = 1 − α − β and let

δ = min \{\frac{ε}{4α + ε}, \frac{ε}{4β + ε}\} .

Let A_{k} be the same sets constructed in Example 3.3 such that |A_{k}|/2^{k} ⩾ 1 − δ for each k ⩾ k_{0}, where k_{0} can be chosen large enough so that k_{0} > 4m/ε. Let

C = ⋃_{k=k_{0}}^{∞}(2^{k} − 2_{0}^{k} + A_{k}).

Then BD(C) ⩾ 1 − δ and C is not piecewise syndetic. Now we construct A and B by:

A = ⋃_{a∈C}(k_{0}a + [0, [(α + \frac{ε}{4})k_{0}]]) and B = ⋃_{a∈C}(k_{0}a + [0, [(β + \frac{ε}{4})k_{0}]]).

Then

BD(A) ⩾ BD(C) (α + \frac{ε}{4}) ⩾ (1 − δ) (α + \frac{ε}{4}) ⩾ (1 − \frac{ε}{4α + ε}) (\frac{4α + ε}{4}) = α.

By the same reason we have BD(B) ⩾ β. Since C is not piecewise syndetic, then both A and B are not piecewise syndetic. For any l ∈ ℕ, since

[lk_{0}, (l + 1)k_{0} − 1] ∩ (A + B) ⊆ [lk_{0}, lk_{0} + [(α + β + ε/2)k_{0}]],

then

[lk_{0}, (l + 1)k_{0} − 1] ∩ (A + B + [0, m])
⊆ [lk_{0}, lk_{0} + [(α + β + ε/2)k_{0}] + m]
⊆ [lk_{0}, lk_{0} + [(α + β + ε/2)k_{0}] + [εk_{0}/4]]
⊆ [lk_{0}, lk_{0} + [(α + β + 3ε/4)k_{0}]]
⊆ [lk_{0}, lk_{0} + [(1 − ε/4)k_{0}]]
⊆ [lk_{0}, (l + 1)k_{0} − m − 1].

Hence A + B + [0, m] is not thick because any interval of length greater than 3k_{0} contains an interval of the form [lk_{0}, (l + 1)k_{0} − 1], which contains a subinterval [(l + 1)k_{0} − m, (l + 1)k_{0} − 1] disjoint from A + B + [0, m]. □

Assume d = 1 as in Application 2.7. The conclusion there is

lim inf_{k→∞}(Gap(A_{k} + B_{k}, Q_{k})) < ∞.

Is it possible that the conclusion can be strengthened to

lim sup_{k→∞}(Gap(A_{k} + B_{k}, Q_{k})) < ∞?

The next example shows that it cannot.

Example 3.7 For any non–negative real numbers α and β such that α+β < 1, there exist two sequences of sets ⟨A_{k} ⊆ [0, 2^{k} − 1] : k ∈ ℕ⟩ and ⟨B_{k} ⊆ [0, 2^{k} − 1] : k ∈ ℕ⟩ with

inf \{\frac{|A_{k}|}{2^{k}} : k ∈ ℕ\} ⩾ α and inf \{\frac{|B_{k}|}{2^{k}} : k ∈ ℕ\} ⩾ β

such that for any large sequence of intervals ⟨[a_{k}, b_{k}] : k ∈ ℕ⟩ the set

{Gap(A_{k} + B_{k}, [a_{k}, b_{k}]) : k ∈ ℕ}

is unbounded in ℕ.

Proof Choose a non–principal ultrafilter F on ℕ which is not a P–point. Let the nonstandard universe and the cut U be the same as in Application 2.7. Let V = ℕ. Since F is not a P–point, then U ∖ V ≠ ∅. Let H = [⟨2^{k} : k ∈ ℕ⟩] Then U, V ⊆ [0, H − 1]. By Example 3.5 there exist internal sets A = [⟨A_{k} : k ∈ ℕ⟩] and B = [⟨B_{k} : k ∈ ℕ⟩] in [0, H − 1] such that st(|A|/H) ⩾ α, st(|B|/H) ⩾ β, and for any interval [a, b] ⊆ [0, H − 1] of length greater than U,

Gap(A + B, [a, b]) > V.

Let

X = \{k ∈ ℕ : \frac{|A_{k}|}{2^{k}} ⩾ α and \frac{|B_{k}|}{2^{k}} ⩾ β.\}

So X ∈ F. For each k ∈ X let A_{k} and B_{k} be unchanged and for each k ∉ X redefine A_{k} = B_{k} = [0, 2^{k} − 1]. If ⟨[a_{k}, b_{k}] ⊆ [0, 2(2^{k} − 1)] : k ∈ ℕ⟩ is a large sequence of intervals, then the interval [[⟨a_{k} : k ∈ ℕ⟩], [⟨b_{k} : k ∈ ℕ⟩]] ⊆ [0, 2H − 2] has length greater than U. Hence

[⟨Gap(A_{k} + B_{k}, [a_{k}, b_{k}]) : k ∈ ℕ⟩] > V = ℕ.

This implies that {Gap(A_{k} + B_{k}, [a_{k}, b_{k}]) : k ∈ ℕ} is not bounded in ℕ. □

The last example shows that one cannot replace Lebesgue measure by outer Lebesgue measure in Application 2.1. We use [0, 1] for the unit interval of real numbers in the next example.

Example 3.8 There is an A ⊆ [0, 1] such that the outer measure of A is 1 and A+A does not contain a non–empty open interval of real numbers.

Proof In the proof below we use α and β for ordinals. Let 𝔠 = 2^{ℵ_{0}} be the cardinality of the continuum and let {X_{α} : α < 𝔠} be an enumeration of all uncountable closed subsets of [0, 1]. View ℝ as a linear space over ℚ, the rational field. For any Y ⊆ ℝ let ⟨Y ⟩ denote the subspace generated by Y. We now construct two sequences of subsets of [0, 1], A_{0} ⊆ A_{1} ⊆ A_{2} ⊆ ⋯ and B_{0} ⊆ B_{1} ⊆ B_{2} ⊆ ⋯, inductively such that for each α < 𝔠

1. ⟨A_{α}⟩ ∩ [0, 1] = A_{α} and ⟨B_{α}⟩ ∩ [0, 1] = B_{α},

2. ⟨A_{α}⟩ ∩ ⟨B_{α}⟩ = {0},

3. the cardinality of A_{α} ∪ B_{α} < 𝔠,

4. A_{α} ∩ X_{α} ≠ ∅ and B_{α} ∩ X_{α} ≠ ∅.

Suppose A_{β} and B_{β} are obtained so that 1–4 above are true for every β < α. By 3, |X_{α} ∖ ⋃_{β<α}(A_{β} ∪ B_{β})| = 𝔠. By a cardinality argument one can choose x, y ∈ X_{α} ∖ ⋃_{β<α}(A_{β} ∪ B_{β}) such that

⟨ ⋃_{β<α} A_{β} ∪ {x}⟩ ∩ ⟨ ⋃_{β<α} B_{β} ∪ {y}⟩ = {0}.

Now let

A_{α} = ⟨ ⋃_{β<α} A_{β} ∪ {x}⟩ ∩ [0, 1] and B_{α} = ⟨ ⋃_{β<α} B_{β} ∪ {y}⟩ ∩ [0, 1].

It is clear that 1–4 are true for A_{α} and B_{α}. Finally, Let

A = ⋃_{α<𝔠}A_{α} and B = ⋃_{α<𝔠}B_{α}.

We now check that A is the set we want. A has outer measure 1 because of 4. A + A does not contain any non–empty open interval because of 2 and 4. □

4 A New Proof of Shnirel’man’s Theorem

This section offers neither an “easier” nor a “better” proof of Shnirel’man’s theorem. It merely offers a “different” proof. The purpose of this section is to demonstrate the potential of the sumset phenomenon in dealing with combinatorial problems involving asymptotic arguments. A conventional proof can be found in [8].

For a set A ⊆ ℕ the Shnirel’man density of A is defined by the following:

σ(A) = inf_{k⩾1} \frac{|A ∩ [1, k]|}{k}.

Note that if σ(A) ⩾ α, then by the transfer principle

st (\frac{|^{∗}A ∩ [0, H − 1]|}{H}) ⩾ α

for every hyperfinite integer H. Note also that if σ(A) > 0, then 1 ∈ A. For any set A ⊆ ℕ and for any h ∈ ℕ let

hA = \underbrace{A + A + ⋯ + A}_{h}

if h > 0 and let hA = ∅ if h = 0. If U is a cut and x ∈ ^{∗}ℕ ∖ U, then

xU = {y ∈ ^{∗}ℕ : y < xu for some u ∈ U}

and

x/U = {y ∈ ^{∗}ℕ : y < x/u for every u ∈ U}

are cuts. Note that xℕ is the smallest cut containing x and x/ℕ is the largest cut not containing x.

Theorem 4.1 (Shnirel’man) For any set A ⊆ ℕ, if 0 ∈ A and σ(A) > 0, then there is an h ∈ ℕ such that hA = ℕ.

Proof We suppose the theorem is not true and derive a contradiction. Since h^{∗}A ≠ ^{∗}ℕ for every h ∈ ℕ, then ⋃_{h∈ℕ}(h^{∗}A) ≠ ^{∗}ℕ by countable saturation. Let H ∈ ^{∗}ℕ ∖ ⋃_{h∈ℕ}(h^{∗}A).

Claim 4.1.1 Let K be a hyperfinite integer and let [a, b] ⊆ [0, K − 1] be such that b − a > K/n for some n ∈ ℕ. Then [a, b] ∩ (h^{∗}A) ≠ ∅ for some h ∈ ℕ.

Proof of Claim 4.1.1 Since

st (\frac{|^{∗}A ∩ [1, [K/n]]|}{[K/n]}) > 0,

then

∗A ∩ ([0, [K/n]] ∖ K/ℕ) ≠ ∅.

Let x ∈ ^{∗}A be such that K/ℕ < x < K/n. Then x < b − a, and it is easy to see that there is a finite h ∈ ℕ such that hx ∈ [a, b]. So hx ∈ h^{∗}A ∩ [a, b]. □(Claim 4.1.1)

Claim 4.1.2 Suppose that Gap(2^{∗}A, [a, b]) ≤ n(d − c) and [c, d] ⊆ h^{∗}A. Then

[a + nd, b + nc] ⊆ (2 + nh)^{∗}A.

Proof of Claim 4.1.2 Let y = min(2^{∗}A ∩ [a, b]) and z = max(2^{∗}A ∩ [a, b]). Then

[y + nc, z + nd] ⊆ 2^{∗}A + [nc, nd] ⊆ (2 + nh)^{∗}A.

Moreover, y ⩽ a + n(d − c), b − n(d − c) ⩽ z, so [a + nd, b + nc] ⊆ [y + nc, z + nd]. □(Claim 4.1.2)

Let

V = {U : U is a cut, U < H, and H/ℕ ≠ U},

and let

U = {U ∈ V : (∃[a, b] ⊆ H/ℕ)(∃h ∈ ℕ)[a, b] ⊆ h^{∗}A and U < b − a}.

Note that U is downward closed, i.e. U ⊆ V and V ∈ U imply U ∈ U. Claim 4.1.3 ℕ ∈ U. Proof of Claim 4.1.3 For each x ∈ H/ℕ, st(|^{∗}A ∩ [0, x]|/x) ⩾ σ(A) > 0. By

Application 2.3, (2^{∗}A) ∩ [0, 2x]) is not ℕ–nowhere dense. Therefore there exists an interval [a, b] ⊆ [0, 2x] for some x ∈ H/ℕ such that b − a > ℕ and Gap(2^{∗}A, [a, b]) = m ∈ ℕ. Since [0, 1] ⊆ ^{∗}A, it follows from Claim 4.1.2 that

[a + m, b] ⊆ (2 + m)^{∗}A.

□(Claim 4.1.3) Claim 4.1.4 U = V. Proof of Claim 4.1.4 Suppose U ≠ V. Let V̄ = ⋂(V ∖ U). Then V̄ is a cut.

Let x ∈ H/ℕ ∖ V̄. By Application 2.3, there is an interval [a, b] ⊆ [0, 2x] with b − a > V̄ such that Gap(2^{∗}A, [a, b]) = l ∈ V̄.

Case 1. l is finite. Then by Claim 4.1.2,

[a + l, b] ⊆ 2^{∗}A + [0, l] ⊆ (2 + l)^{∗}A.

Therefore in this case we have V̄ ∈ U.

Case 2. l is hyperfinite. Let U = l/ℕ. Then U < l ∈ V̄, so U ∈ U. Hence there exist h′ ∈ ℕ and an interval [c, d] ⊆ H/ℕ such that U < d − c ∈ V̄ and [c, d] ⊆ h′ ^{∗}A. Let n ∈ ℕ be such that d − c > l/n. By Claim 4.1.2 again,

[a + nd, b + nc] ⊆ (2 + nh′)^{∗}A.

Moreover, (b + nc) − (a + nd) = (b − a) − n(d − c) > V̄. Thus in this case we also have V̄ ∈ U.

By the definition of U, there exist h ∈ ℕ and [a, b] ⊆ H/ℕ such that b − a > V̄ and [a, b] ⊆ h^{∗}A. Let V = (b − a)/ℕ, then V ⊇ V̄ because V is the largest cut not containing b−a. Also V ∈ U by the definition of U. So (b−a)ℕ ⊆ V̄ because (b−a)ℕ is the smallest cut containing b − a. This contradicts (b − a)/ℕ ⊇ V̄, and completes the proof that U = V. □(Claim 4.1.4)

Claim 4.1.5 There exist h ∈ ℕ and [a, b] ⊆ [0, H − 1] such that b − a > H/ℕ and [a, b] ⊆ h^{∗}A.

Proof of Claim 4.1.5 By Application 2.3, there is an interval

[c, d] ⊆ [0, [(H − 1)/2]]

such that d − c > H/ℕ and

Gap(2^{∗}A, [c, d]) = l < H/ℕ.

Let U = lℕ. Then U ≠ H/ℕ by countable saturation. So by Claim 4.1.4, there exist h′ ∈ ℕ and [e, f] ⊆ H/ℕ such that f−e > U and [e, f] ⊆ h′ ^{∗}A. Let [a, b] = [c+f, d+e]. Then by Claim 4.1.2,

[a, b] ⊆ (2 + h′)^{∗}A.

It is obvious that 0 ⩽ a and b < [(H − 1)/2] + [(H − 1)/2] ⩽ H − 1. □(Claim 4.1.5)

Let [a, b] ⊆ [0, H − 1] and h ∈ ℕ be obtained according to Claim 4.1.5. By Claim 4.1.1 there is an h′ ∈ ℕ such that [H − b, H − a] ∩ (h′ ^{∗}A) ≠ ∅. Let

r ∈ [H − b, H − a] ∩ (h′ ^{∗}A).

Then

H ∈ [a + r, b + r] = [a, b] + r ⊆ (h^{∗}A) + (h′ ^{∗}A) = (h + h′)^{∗}A.

This contradicts the choice of H and completes the proof. □

5 Questions

In this section we pose two open questions.

Let H be a hyperfinite integer, and let I(H) be the set of all internal subsets of [0, H − 1] ∩^{∗}ℕ. For A ∈ I(H) and m ∈ ^{∗}ℕ let

g(A, m) = min{Gap(A, [a, b]) : b − a + 1 = m}.

It is easy to see that if m > 0 and A ≠ ∅, then g(A, m) < m/2. One can define an internal decreasing sequence

S(H, A) = ⟨m_{i} : 0 ⩽ i ⩽ k⟩

such that m_{0} = H, m_{i+1} = g(A, m_{i}) > 0 for i ∈ [0, k − 1], and m_{k} = 0. The number k is called the length of the sequence S(H, A), and is denoted by len(S(H, A)).

If U ⊆ [0, H − 1] is a cut and A is U–nowhere dense, then the length of the sequence S(H, A) is a hyperfinite integer. On the other hand, if the length of the sequence S(H, A) is hyperfinite, then

U = ⋂_{i∈ℕ}[0, m_{i}]

is a cut and A is U–nowhere dense. Therefore by Application 2.3, if A, B ∈ I(H) and

st (\frac{|A ∩ [0, H − 1]|}{H}) > 0 and st (\frac{|B ∩ [0, H − 1]|}{H}) > 0.

then the length of the sequence S(H, A + B) is finite. Given positive standard real numbers α and β such that α + β < 1, let

L(H, α, β) = \{len(S(H, A + B)) : A, B ∈ I(H), \frac{|A|}{H} ⩾ α, and \frac{|B|}{H} ⩾ β\}.

Then L(H, α, β) is an internal subset of ℕ, and hence is upper bounded in ℕ.

Question 5.1 Given H, α, β, what is the least upper bound of L(H, α, β)?

Let (G, ·) be a countable group not necessarily abelian. For g ∈ G and A ⊆ G let gA = {ga : a ∈ A} and Ag = {ag : a ∈ A}. We would like to define upper Banach density and syndeticity of a subset of G following the ideas in [1]. For convenience we consider only groups rather than semigroups .

A sequence ⟨A_{k} : k ∈ ℕ⟩ of subsets of G is called a left Følner sequence if for every g ∈ G

lim_{k→∞} \frac{|gA_{k}ΔA_{k}|}{|A_{k}|} = 0,

where Δ is the symmetric difference. If G admits left Følner sequences, then for each A ⊆ G one can define the upper Banach density of A by the following:

BD(A) = sup \{lim sup_{k→∞} \frac{|A ∩ A_{k}|}{|A_{k}|} : ⟨A_{k} : k ∈ ℕ⟩ is a left Følner sequence\} .

A set A ⊆ G is called right thick if for every finite F ⊆ G, there is a g ∈ G such that F g ⊆ A. A set A ⊆ G is called right piecewise syndetic if there is a finite subset F of G such that ⋃_{f∈F} fA is right thick.

Question 5.2 Let G be a countable group admitting left Følner sequences. Let A, B ⊆ G. Is A·B = {ab : a ∈ A, b ∈ B} always right piecewise syndetic whenever BD(A) > 0 and BD(B) > 0?

References

[1] Bergelson, V., Hindman, N., and McCutcheon, R., Notions of size and combinatorial properties of quotient sets in semigroups, Topology Proceedings, 23 (1998), pp. 23—60.

[2] Chang, C. C. and Keisler, H. J., Model Theory, North–Holland, third edition 1990.

[3] Furstenberg, H., Recurrence in Ergodic Theory and Combinatorial Number Theory, Princeton University Press, 1981.

[4] Jin, Renling, The Sumset phenomenon, The Proceedings of American Mathematical Society, to appear.

[5] Keisler, H. Jerome and Leth, Steven C., (1991) Meager Sets on the Hyperfinite Time Line, The Journal of Symbolic Logic, 56, pp. 71–102.

[6] Henson, C. W., Foundations of nonstandard analysis–A gentle introduction to nonstandard extension, in Nonstandard Analysis: Theory and Applications, ed. by N. J. Cutland, C. W. Henson, and L. Arkeryd, Kluwer Academic Publishers 1997.

[7] Lindstrom, T., An invitation to nonstandard analysis, in Nonstandard Analysis and Its Application, ed. by N. Cutland, Cambridge University Press 1988.

[8] Nathanson, M. B., Additive Number Theory: The Classical Bases, Spring–Verlag, New York, 1996.