On the Schnirelmann density of sumsets

Pál Hegedűs, Gábor Piroska and Imre Z. Ruzsa*

Abstract. A classical result of Schnirelmann asserts that σ(A+B) ≥ σ(A)+ σ(B)−σ(A)σ(B) for arbitrary sets of integers, provided at least one of them contains

0. We establish the best possible bound that can be asserted in this case, in particular we describe all cases of equality in Schinrelmann’s theorem.

1. Introduction

Let A and B be sets of nonnegative integers with positive Schnirelmann densities σ(A) = α and σ(B) = β, respectively. Schnirelmann proved that

σ(A + B) ≥ α + β − αβ,  (1.1)

provided at least one of A and B contains 0. Under the stronger assumption that 0 ∈ A ∩ B, Mann strengthened (1.1) to

σ(A + B) ≥ min(α + β, 1).  (1.2)

For a proof and history of (1.1) and (1.2) see, for instance, Halberstam-Roth [2]. Lepson [3] showed that in (1.2) equality can hold for any α and β (see also [1] for a related result). By writing

S(α, β) = inf{σ(A + B) : σ(A) = α, σ(B) = β, 0 ∈ A}

and

M(α, β) = inf{σ(A + B) : σ(A) = α, σ(B) = β, 0 ∈ A ∩ B},

we can restate these results as

α + β − αβ ≤ S(α, β) ≤ M(α, β) = min(α + β, 1).  (1.3)

It was also known that equality can hold in (1.1) for certain values of α and β. However, if α + β > 1, then we have S(α, β) = M(α, β) = 1, as also shown already by Schnirelmann, thus in both inequalities of (1.3) equality can actually occur.

In this paper we give a formula for S(α, β) and describe the cases of equality in inequalities (1.3).

* Supported by Hungarian National Foundation for Scientific Research, Grant No. T 017433 Theorem 1.

For all α, β we have

S(α, β) = inf_{n≥0} \frac{⌈αn⌉ + ⌈β(n + 1)⌉}{n + 1}.  (1.4)

Definition 1.1. Let α, β be positive real numbers satisfying α + β ≤ 1. We call (α, β) a Schnirelmann pair if S(α, β) = α+β −αβ, and a Mann pair if S(α, β) = α+β.

Theorem 2.

The numbers (α, β) form a Schnirelmann pair if and only if they can be expressed as

α = \frac{k}{n}, β = \frac{1}{n + 1}

with certain integers n ≥ 2 and 1 ≤ k ≤ n − 1.

In Section 2 we prove Theorem 1, in Section 3 we give two proofs of Theorem 2, one based on and one independent of Theorem 1. Mann pairs are described in Section 4.

2. The optimal estimate

We introduce the following convention. For any set of integers we use the same letter to denote its counting function, that is, for a set A we write

A(x) = |A ∩ [1, x]|.

We need the following result of van der Corput (see [2]).

Lemma 2.1.

Let A, B be sets of nonnegative integers both containing 0 and put C = A + B. If for a nonnegative number η we have

1 + A(m) + B(m) ≥ η(m + 1) for m = 0, 1, ..., n,  (2.1)

then 1 + C(n) ≥ η(n + 1).

Proof of Theorem 1. Denote the right side of (1.4) by γ. First we show that S(α, β) ≥ γ. Since σ(B) > 0, we have 1 ∈ B. Write B′ = B − 1; thus 0 ∈ B′. We will apply the above lemma to the sets A, B′; the requirement that both contain 0 is hence fulfilled.

Next we show that the sets A, B′ satisfy (2.1) with η = γ. Indeed, by the definition of the Schnirelmann density we have A(m) ≥ αm, and since it must be an integer, we have

A(m) ≥ ⌈αm⌉.

We have

B′(m) = |B′ ∩ [1, m]| = |B ∩ [2, m + 1]| = B(m + 1) − 1 ≥ β(m + 1) − 1,

and again this is an integer, thus

B′(m) ≥ ⌈β(m + 1)⌉ − 1.

On adding these inequalities we find

1 + A(m) + B′(m) ≥ ⌈αm⌉ + ⌈β(m + 1)⌉ ≥ γ(m + 1)

by the definition of γ.

An application of the Lemma to the sets A, B′ yields that their sum C′ = A + B′ satisfies

1 + C′(n) ≥ γ(n + 1)

for all n.

Since C = A + B is connected to C′ via C = C′ + 1, we conclude that

C(n) = |C ∩ [1, n]| = |C′ ∩ [0, n − 1]| = 1 + C′(n − 1) ≥ γn

for all n, which is equivalent to saying σ(C) ≥ γ.

To show that S(α, β) ≤ γ, suppose first that the infimum in the definition (1.4) is a minimum, and let n be any integer satisfying

γ = \frac{⌈αn⌉ + ⌈β(n + 1)⌉}{n + 1}.

Consider the sets

A_{0} = {0, 1, ..., ⌈αn⌉} ∪ {n + 1, n + 2, ...}

and

B_{0} = {1, ..., ⌈β(n + 1)⌉} ∪ {n + 2, n + 3, ...}.

These sets satisfy

σ(A_{0}) = \frac{⌈αn⌉}{n} ≥ α

and

σ(B_{0}) = \frac{⌈β(n + 1)⌉}{n + 1} ≥ β.

We can select subsets A ⊂ A_{0} and B ⊂ B_{0} such that σ(A) = α, σ(B) = β and 0 ∈ A. These sets satisfy

A + B ⊂ A_{0} + B_{0} = {1, 2, ..., ⌈αn⌉ + ⌈β(n + 1)⌉} ∪ {n + 2, ...},

consequently (by evaluating the counting function at n + 1) we find that

σ(A + B) ≤ σ(A_{0} + B_{0}) ≤ \frac{⌈αn⌉ + ⌈β(n + 1)⌉}{n + 1} = γ

as wanted.

Suppose next that the infimum is not attained. In this case we have

s = inf_{n≥0} \frac{⌈αn⌉ + ⌈β(n + 1)⌉}{n + 1} = lim_{n→∞} \frac{⌈αn⌉ + ⌈β(n + 1)⌉}{n + 1} = α + β,

hence the example of [3] for equality in Mann’s theorem serves also as an example for S(α, β) ≤ γ.

3. Schnirelmann pairs

We prove Theorem 2. By Theorem 1, α and β form a Schnirelmann pair if and only if

inf_{n≥0} \frac{⌈αn⌉ + ⌈β(n + 1)⌉}{n + 1} = α + β − αβ.  (3.1)

Since the limit of the left side of (3.1) is α + β, in this case there must be an n such that

\frac{⌈αn⌉ + ⌈β(n + 1)⌉}{n + 1} = α + β − αβ.

Observe that the value of the left side for n = 0 is 1, so we must have n ≥ 1. Write

⌈αn⌉ = k, ⌈β(n + 1)⌉ = l.

We have αn ≤ k and β(n + 1) ≤ l, hence k ≠ 0, l ≠ 0 and

α ≤ k/n, β ≤ l/(n + 1).  (3.2)

By the monotonicity of the function α + β − αβ in both variables (in our domain), we have

α + β − αβ ≤ \frac{k}{n} + \frac{l}{n + 1} − \frac{k}{n} \frac{l}{n + 1} = \frac{k + l}{n + 1} − \frac{k(l − 1)}{n(n + 1)}.

Since l ≥ 1, the last expression is always ≤ (k + l)/(n + 1), and equality can hold only if l = 1 and both inequalities in (3.2) hold with equality. This means that α = k/n and β = l/(n + 1) = 1/(n + 1) as claimed.

Now we give another proof for the following slightly weaker result: if there are sets A, B such that σ(A + B) = α + β − αβ, then α, β are of the form described in Theorem 2. We think that this proof, which does not use Theorem 1 but follows Schnirelmann’s original argument instead with some modifications, is of independent interest. It also yields additional information on the structure of the extremal sets.

Write S = A + B, γ = σ(S) = α + β − αβ. First we show that there exists an x such that S(x)/x = γ. Indeed, if S(x) > γx for all x, then

σ(x) = inf S(x)/x = lim inf S(x)/x = \underline{d}(S).

By Kneser’s theorem (see [2]) we have either

\underline{d}(S) ≥ \underline{d}(A) + \underline{d}(B) ≥ σ(A) + σ(B) ≥ α + β,

or S has the following structure: for a certain m it is the union of some residue classes modulo m, with a finite number of integers omitted. The first case is clearly impossible. In the second case let k be the number of these residue classes. We have

k ≥ S(m) ≥ γm = \underline{d}(S)m = k,

thus again there is equality at x = m.

From now on we fix an integer x with the property S(x) = γx. Since γ < 1, we have x ≥ 2. Observe that x ∉ S, since x ∈ S would imply S(x − 1) = S(x) − 1 < γx. This also implies x ∉ B.

Let

1 = b_{1} < b_{2} < ... < b_{r} < x (< b_{r+1})

be the elements of B up to x, so that

r = B(x) ≥ βx.

Following Schnirelmann’s argument we observe that the numbers b_{i} are all in S, as well as all the numbers b_{i} + a with a ∈ A, 1 ≤ a ≤ b_{i+1} − b_{i} − 1 for 1 ≤ i ≤ r − 1 and the numbers b_{r} + a, a ∈ A, 1 ≤ a ≤ x − b_{r}. This gives

\begin{aligned}S(x) & ≥ r + ∑_{i=1}^{r−1} A(b_{i+1} − b_{i} − 1) + A(x − b_{r}) \\ & ≥ r + α (∑_{i=1}^{r−1}(b_{i+1} − b_{i} − 1) + x − b_{r}) \\ & = r + α(x − r) = αx + (1 − α)r ≥ αx + (1 − α)βx = γx. \end{aligned}  (3.3)

If we have equality here, then equality must hold in all the intermediate inequalities, thus we have r = βx and

A(b_{i+1} − b_{i} − 1) = α(b_{i+1} − b_{i} − 1)  (3.4)

for all i ≤ r − 1. Also

A(x − b_{r}) = α(x − b_{r}).  (3.5)

We have x + 1 ∈ B, since otherwise we would have B(x + 1) = r = βx < β(x + 1). Thus (3.5) becomes the case i = r of (3.4).

If r = 1, then we have β = 1/x and α = A(x − 1)/(x − 1) from (3.5), thus we have the claim of the Theorem with n = x − 1. In the sequel we assume that r ≥ 2.

Write d_{i} = b_{i+1} − b_{i}. We show that this sequence is decreasing for 1 ≤ i ≤ r. Suppose on the contrary that d_{i+1} > d_{i} for some 1 ≤ i ≤ r − 1. Consider the numbers b_{i} + a, a ∈ A lying in [b_{i+1} + 1, b_{i+2} − 1], which correspond to

a ∈ A, d_{i} + 1 ≤ a ≤ d_{i} + d_{i+1} − 1.  (3.6)

These are elements of S up to x, thus must be among those that we counted in (3.3), that is, they must be of the form b_{i+1} + a′, a′ ∈ A. Thus for these numbers we infer that

a′ = a − d_{i} ∈ A.  (3.7)

From (3.4) we know that

A(d_{i} − 1) = α(d_{i} − 1), A(d_{i+1} − 1) = α(d_{i+1} − 1).

By definition of α we have

A(d_{i} + d_{i+1} − 1) ≥ α(d_{i} + d_{i+1} − 1) = A(d_{i} − 1) + A(d_{i+1} − 1) + α.

Since this number must be an integer, we must have

A(d_{i} + d_{i+1} − 1) ≥ A(d_{i} − 1) + A(d_{i+1} − 1) + 1.

This can be rewritten as

|A ∩ [d_{i+1}, d_{i} + d_{i+1} − 1]| ≥ A(d_{i} − 1) + 1.

The elements counted in the left side are all in the range (3.6) (here we use the assumption that d_{i+1} > d_{i}), thus by (3.7) we can substract d_{i} from them and get elements of A again. This yields

|A ∩ [d_{i+1} − d_{i}, d_{i+1} − 1]| ≥ A(d_{i} − 1) + 1

or

A(d_{i+1} − 1) − A(d_{i+1} − d_{i} − 1) ≥ A(d_{i} − 1) + 1.

By rearranging and taking into account (3.4) we obtain

\begin{aligned}A(d_{i+1} − d_{i} − 1) & ≤ A(d_{i+1} − 1) − A(d_{i} − 1) − 1 \\ & = α(d_{i+1} − 1) − α(d_{i} − 1) − 1 < α(d_{i+1} − d_{i} − 1), \end{aligned}

a contradiction.

Thus the numbers b_{2} − b_{1} = b_{2} − 1, b_{3} − b_{2}, ..., b_{r} − b_{r−1}, b_{r+1} − b_{r} = x + 1 − b_{r} are decreasing. With the notation c = b_{2} − 1 this implies

b_{2} = c + 1, b_{3} ≤ 2c + 1, ..., b_{r} ≤ (r − 1)c + 1, x ≤ rc.

Hence β = r/x ≥ 1/c; but also β ≤ B(c)/c = 1/c, thus β = 1/c. Since β < 1, we have c ≥ 2. The case i = 2 of (3.4) yields

α = A(b_{2} − 1)/(b_{2} − 2);

thus we have α, β in the required form with n = b_{2} − 2 = c − 1.

4. Mann pairs

Our main result sounds as follows.

Theorem 3.

If α and β form a Mann pair, then they are either both rational or both irrational. A pair of rational numbers, say α = p/q, β = r/s is a Mann pair if and only if they satisfy

{α(1 − n)} + {−βn} ≥ α  (4.1)

for every integer 1 ≤ n ≤ lcm[q, s]. A pair of irrational numbers is a Mann pair if and only if there are integers k, l, m such that

αk + βl = m, 0 < k < 1/α, 0 ≤ k − l < 1/α.  (4.2)

Lemma 4.1. (α, β) is a Mann pair if and only if they satisfy (4.1) for every integer n ≥ 1. Proof. By Theorem 1, these numbers form a Mann pair if and only if we have

S(α, β) = inf_{n≥1} \frac{⌈α(n − 1)⌉ + ⌈βn⌉}{n} ≥ α + β.

(We replaced n in (1.4) by n − 1.) After multiplying by n and taking into account that

⌈x⌉ = x + {−x},

this formula reduces to (4.1).

Lemma 4.2. (α, β) is a Mann pair if and only if we have

{αn} ≤ {−βn}  (4.3)

for every integer n ≥ 1 such that {αn} ≤ α.

Proof. Observe that

\{α(1 − n)\} = \{ \begin{matrix}α − \{αn\} & if \{αn\} ≤ α , \\ α − \{αn\} + 1 & if \{αn\} > α. \end{matrix}

By substituting this into (4.1) we obtain the inequality (4.3) in the first case, and {αn} ≤ 1 + {−βn} in the second. Since the second inequality is trivially true, (4.1) is equivalent to the assumption that (4.3) holds whenever {αn} ≤ α.

We can reformulate this result as follows. Lemma 4.3. (α, β) is a Mann pair if and only if there is no point of the form ({αn}, {−βn}) in

the domain T defined by

T = {(u, v) : 0 < u ≤ α, 0 ≤ v < u}.

Lemma 4.4.

If α, β, 1 are independent over the rationals, then (α, β) is not a Mann pair.

Proof. In this case the points ({−αn}, {−βn}) are everywhere dense in the unit square, thus we can find a point of this form inside T.

Lemma 4.5.

A rational and an irrational number never form a Mann pair.

Proof. Suppose that β is rational, say β = r/s, and α is irrational. We consider only integers of the form n = sm. For these values we have {−βn} = 0. Furthermore, {αn} = {αsm} can lie in (0, α), since αs is irrational and consequently αsm is everywhere dense modulo 1.

If α is irrational, say α = p/q, we argue similary, using the numbers in the form n = qm − 1. We will have {αn} = α, and we can achieve 0 < {−βn} = {β − βqm} < α, since {βqm} is dense modulo 1.

Thus we can restrict our attention to numbers that are dependent over the rationals.

Lemma 4.6.

Assume that α, β are real numbers, connected by the equation

αk − βl = m,  (4.4)

where k, l, m are integers and gcd(k, l, m) = 1. Define

P = {({αn}, {βn}) : n ≥ 1}

and

Q = {(u, v) : 0 ≤ u, v < 1, uk ≡ vl (mod 1)}.

We have P ⊂ Q, and if α, β are irrational, then P is dense in Q\(0, 0).

Proof. The inclusion P ⊂ Q is obvious.

Suppose now that α, β are irrational, and take an (u, v) ∈ Q, (u, v) ≠ (0, 0). Then uk − vl is an integer, and, since (k, l, m) = 1, it has a representation in the form

uk − vl = ka − lb − mc

with integral a, b, c. By substituting the value of m from (4.4) we obtain

k(u − a − αc) = l(v − b − βc),

or

\frac{(u − a − αc)}{l} = \frac{(v − b − βc)}{k} = γ,

say. (We have kl ≠ 0, since if one of them vanished, then (4.4) could not hold.)

Take an ε > 0. Since αk is irrational, we can find infinitely many integers q such that qkl > 0 and

αqk ≡ βql ≡ γ + δ (mod 1),  (4.5)

where |δ| < ε. (The first congruence in (4.5) holds identically by (4.4).)

Now consider the numbers n = qkl + c. We have

\begin{aligned}αn & = α(qkl + c) = (αqk)l + αc \\ & ≡ (γ + δ)l + αc = δl + γl + αc = δl + (u − a − αc) + αc ≡ u + δl (mod 1). \end{aligned}

An analogous calculation yields

βn ≡ v + δk (mod 1).

Thus (αn, βn) can be arbitrarily near to (u, v) modulo 1. This concludes the proof if both u and v are positive.

If one of u or v is equal to 0, then we approximate (u, v) by (u′, v′) ∈ P, u′, v′ > 0 and apply the previous proof to u′, v′.

We remark that this approximation also works for (0, 0) if kl > 0, but if kl < 0, then it is an isolated point and will not be in the closure of Q.

Lemma 4.7.

Assume that α, β are real numbers, connected by equation

αk + βl = m  (4.6)

with integers k, l, m, gcd(k, l, m) = 1. Define

P = {({αn}, {−βn}) : n ≥ 1}

and

Q = {(u, v) : 0 ≤ u, v < 1, ku ≡ lv (mod 1)}.

We have P ⊂ Q, and if α, β are irrational then P is dense in Q.

Proof. This is the previous lemma applied to the numbers α, −β.

Proof of Theorem 3.

If both numbers are rational, we apply Lemma 4.1. Since the function {α(1−n)}+ {−βn} is periodic with period lcm[q, s], it is sufficient to check integers up to lcm[q, s].

The case when one is rational and the other is irrational is settled by Lemma 4.5. Now assume that both numbers are irrational. If α, β, 1 are independent over the

rationals, we are done by Lemma 4.4. Suppose they are dependent. Then they are connected by an equation (4.6). From the equations we can select one that satisfies (k, l, m) = 1 and k > 0.

Suppose that k, l, m fulfill the conditions in (4.2).

The set T in Lemma 4.3 is a triangle with vertices (0, 0), (α, 0) and (α, α). The value of the function ku − lv at the vertices is 0, αk ∈ (0, 1) and α(k − l) ∈ [0, 1), respectively. Every point of T is a convex combination of the vertices and, since the edge connecting (0, 0) to (α, α) is excluded, the weight of (α, 0) is always positive, thus the image under the above map lies in (0, 1) and cannot contain an integer. Hence P ∩ T = ∅ and (α, β) is a Mann pair by Lemma 4.3.

Suppose that one of the conditions is violated.

If k > 1/α, then the point (1/k + εl, εk) is in T for small ε such that εk > 0 and satisfies ku ≡ lv (mod 1).

If k − l < 0, that is, l > k, then we use the point (εl, εk) for small positive ε. Finally if k < 1/α and k − l > 1/α, then l < k − 1/α < 0. In this case our point is

(\frac{1}{k − l} − εl, \frac{1}{k − l} − εk)

for small positive ε.

In all cases we found a point in the interior of T ∩ Q. By Lemma 4.7 we infer T ∩ P ≠ ∅ and then (α, β) is not a Mann pair by Lemma 4.3.

The description of rational Mann pairs is less satisfactory than that of irrational ones, though it provides a finite algorithm for each pair of rational numbers. The following can be observed.

Statement 4.8.

Let α, β be rational numbers, and write α/β = a/b with (a, b) = 1. If there are integers satisfying (4.2), then (α, β) is a Mann pair. In particular, if α ≤ 1/(a + b), then it is a Mann pair.

Proof. In proving the sufficiency of condition (4.2) we did not use any assumption about the rationality of α and β.

For rational numbers the choice of k, l, m is not unique even under the restrictions k > 0, (k, l, m) = 1. One possible choice is k = b, l = −a. With this choice condition (4.2) becomes 0 < b < 1/α and 0 ≤ a + b < 1/α. Here the positivity conditions are automatically satisfied, and the second upper bound involves the first, thus (4.2) reduces to a + b < 1/α, or α < 1/(a + b). To extend this to the case of α = 1/(a + b), observe that here we have β = \frac{b}{a(a+b)} and (4.2) is applicable with k = l = a.

The difficulty is that the set P will be a lattice in the rational case, and there seems no easy way to decide when a lattice intersects a triangle.

We note that condition (4.2) is not necessary in the rational case. This is seen by the examples α = 4/11, β = 5/11 or α = 8/65, β = 2/13.

References

[1] Cheo, L., A remark on the α+β theorem, Proc. Amer. Math. Soc. 3(1952), 175–177.

[2] Halberstam, H.; Roth, K. F, Sequences, Clarendon, London 1966 (2nd ed. Springer– Verlag, New York–Berlin, 1983) .

[3] Lepson, B., Certain best possible results in the theory of Schnirelmann density, Proc. Amer. Math. Soc. 1(1950), 592–594. Address of authors:

Pál Hegedűs Dept. of Algebra and Number Theory, Eötvös University Budapest, Múzeum krt. 6-8 H-1088 Hungary. e-mail: hegpal@cs.elte.hu

Gábor Piroska TCT-Hungary Amerikai-magyar kft. Budapest, Rákóczi út 25. H-1088 Hungary.

Imre Z. Ruzsa Mathematical Institute of the Hungarian Academy of Sciences, Budapest, Pf. 127, H–1364 Hungary. e-mail: ruzsa@math-inst.hu