ON ADDITION OF TWO DIFFERENT SETS OF INTEGERS

VSEVOLOD F. LEV AND PAVEL Y. SMELIANSKY

What is the structure of a pair of finite integers sets A, B ⊂ ℤ with the small value of |A + B|? We answer this question for addition coefficient 3. The obtained theorem sharpens corresponding results of G.Freiman.

1. Introduction and historical comments

Let A = {a_{1}, …, a_{k}}, B = {b_{1}, …, b_{l}} be two sets of integers, so that k = |A|, l = |B|, and suppose 0 = a_{1} < ⋯ < a_{k}, 0 = b_{1} < ⋯ < b_{l}. As usual, we write A + B for the set {a_{i} + b_{j} | 1 ≤ i ≤ k, 1 ≤ j ≤ l}, and put 2A = A + A. By (a_{1}, …, a_{k}) we denote the greatest common divisor of a_{1}, …, a_{k}, and by (a_{1}, …, b_{l}) — the greatest common divisor of a_{1}, …, a_{k}, b_{1}, …, b_{l}.

In [1] G.Freiman proved the following:

Theorem 1. We have:

(i) Let a_{k} ≤ 2k − 3. Then |2A| ≥ a_{k} + k.

(ii) Let a_{k} ≥ 2k − 2 and (a_{1}, …, a_{k}) = 1. Then |2A| ≥ 3k − 3.

The present paper is devoted to the generalization of this theorem onto the case of summation of two different sets A and B. Without loss of generality, we may assume a_{k} ≥ b_{l}, and put

δ = \begin{cases}1, if b_{l} = a_{k} \\ 0, if b_{l} < a_{k}. \end{cases}

Our main result is:

Theorem 2. We have:

(i) Let a_{k} ≤ k + l − 2 − δ. Then |A + B| ≥ a_{k} + l.

(ii) Let a_{k} ≥ k + l − 1 − δ and (a_{1}, …, a_{k}) = 1. Then |A + B| ≥ k + 2l − 2 − δ.

We would like to note at this point, that Theorem 2 will be deduced in the next section from the following lemma, which in turn will be proved in Section 3:

Lemma 1. Let (a_{1}, …, a_{k}) = 1. Then |A + B| ≥ min{a_{k}, k + l − 2 − δ} + l.

2 VSEVOLOD F. LEV AND PAVEL Y. SMELIANSKY

The question which so far remains unanswered is: how one can estimate |A + B| in the case of a_{k} ≥ k + l − 1 − δ and (a_{1}, …, a_{k}) = d > 1? We may, of course, assume that (a_{1}, …, b_{l}) = 1 (else both A and B should be reduced by the greatest common divisor) and then the following technique may be used.

Break B into the union of pairwise disjoint sets B = B_{1} ∪ ⋯ ∪ B_{s}, where s is the number of residue classes modulo d, having non-empty intersection with B, and B_{i} (i = 1, …, s) are those intersections. Then obviously A + B_{i} also are pairwise disjoint, hence

|A + B| = ∑_{i=1}^{s} |A + B_{i}|.

Using the well-known estimation |A + B_{i}| ≥ |A| + |B_{i}| − 1 and observing that s ≥ 2 (in view of (a_{1}, …, b_{l}) = 1) we immediately obtain:

Lemma 2. Let (a_{1}, …, a_{k}) > 1 and (a_{1}, …, b_{l}) = 1. Then |A + B| ≥ 2k + l − 2.

The more accurate approach is to estimate |A + B_{i}| using Lemma 1 (which firstly requires the application of a suitable linear transformation to both A and B_{i}). This readily gives:

|A + B| ≥ l + ∑_{i=1}^{s} min \{\frac{a_{k}}{d} , k + l_{i} − 2 − δ_{i}\} ,  (1)

where we set l_{i} = |B_{i}| (so that l_{1} + ⋯ + l_{s} = l) and

δ_{i} = \begin{cases}1, if 0 ∈ B_{i} and δ = 1 \\ 0, if 0 ∉ B_{i} or δ = 0. \end{cases}

The sum in the right-hand side of (1) should now be estimated on the basis of specific features of particular problem. Actually, we will use this approach later on in this paper to deduce Theorem 2 from Lemma 1.

And now a brief historical reference. The first generalization of Theorem 1 onto the case of two different summands was done by G.Freiman in [2]. The results obtained may be formulated as follows:

Theorem 3. We have:

(i) Let a_{k} ≤ k + l − 3. Then |A + B| ≥ a_{k} + l.

(ii) Let a_{k} ≥ k + l − 2 and (a_{1}, …, b_{l}) = 1. Then |A + B| ≥ k + l + min{k, l} − 3.

Later, J. Steinig gave in [5] somewhat simplified proof of Theorem 3.

Note, that this theorem follows easily from Theorem 2 and Lemma 2 according to the scheme below:

ON ADDITION OF TWO DIFFERENT SETS OF INTEGERS 3

1) If a_{k} ≤ k + l − 3, we apply Theorem 2, part (i);

2) If a_{k} ≥ k + l − 2 and (a_{1}, …, b_{l}) = 1:

2.1) If (a_{1}, …, a_{k}) > 1, we apply Lemma 2; 2.2) If (a_{1}, …, a_{k}) = 1:

2.2.1) If a_{k} ≥ k + l − 1 − δ, we apply Theorem 2, part (ii);

2.2.2) If a_{k} ≤ k + l − 2 − δ, then δ = 0, a_{k} = k + l − 2 and we apply Theorem 2, part (i).

2. Deduction of the main theorem from Lemma 1

We assume (a_{1}, …, a_{k}) = d > 1 and

a_{k} ≤ k + l − 2 − δ  (2)

(else Theorem 2 follows from Lemma 1 automatically) and make use of (1). First observe, that B is situated in s of d available residue classes modulo d. Therefore

l ≤ s\frac{a_{k}}{d} + δ,

which together with (2) gives:

a_{k} ≤ k + s\frac{a_{k}}{d} − 2,
a_{k}(d − s) ≤ (k − 2)d

and then, in view of a_{k} ≥ (k − 1)d, we obtain s = d. Hence, the result will follow from (1) as soon as we show that for each i = 1, …, d holds

\frac{a_{k}}{d} ≤ k + l_{i} − 2 − δ_{i}.  (3)

Using once again (2) we obtain:

#{0 ≤ c < a_{k} | c ∉ B} = a_{k} − l + δ ≤ k − 2,
l_{i} = #{0 ≤ c < a_{k} | c ∈ B_{i}} + δ_{i}
≥ \frac{a_{k}}{d} − #\{0 ≤ c < a_{k} | c ∉ B\} + δ_{i}
≥ \frac{a_{k}}{d} − (k − 2) + δ_{i},

which proves (3) and therefore the whole theorem.

4 VSEVOLOD F. LEV AND PAVEL Y. SMELIANSKY

3. Proof of Lemma 1

Let G be an abelian group, and let \overline{C} ⊆ G be a finite subset of G. By H(\overline{C}) we will denote the period of \overline{C}, that is the subgroup of all those elements h ∈ G, which satisfy \overline{C} + h = \overline{C}. Obviously, H(\overline{C}) is always finite. If |H(\overline{C})| > 1, the set \overline{C} is called periodic.

We will need the following result, due to M. Kneser ([3, 4]):

Theorem 4. Let \overline{A}, \overline{B} ⊆ G be finite non-empty subsets of G, satisfying

|\overline{A} + \overline{B}| ≤ |\overline{A}| + |\overline{B}| − 1.

Then H = H(\overline{A} + \overline{B}) satisfies

|\overline{A} + \overline{B}| + |H| = |\overline{A} + H| + |\overline{B} + H|.

Hence, \overline{A} + \overline{B} is periodic if

|\overline{A} + \overline{B}| ≤ |\overline{A}| + |\overline{B}| − 2.

Proof of Lemma 1: Suppose

|A + B| ≤ k + 2l − 3 − δ  (4)

and prove, that

|A + B| ≥ a_{k} + l.

Set q = a_{k}, \overline{A} = φA, \overline{B} = φB, where φ : ℤ → ℤ_{q} is the canonical homomorphism of ℤ onto ℤ_{q}. Then |\overline{A}| = k − 1, |\overline{B}| = l − δ, and obviously, \overline{A} + \overline{B} = φA + φB = φ(A + B). As the first step, we show that

|\overline{A} + \overline{B}| ≤ |A + B| − l.  (5)

To this purpose, in the case of b_{l} < a_{k} it is sufficient to observe that

φ(a_{1} + b_{i}) = φ(a_{k} + b_{i}) (i = 1, …, l)

while all the sums a_{1} + b_{i}, a_{k} + b_{i} (i = 1, …, l) are pairwise distinct:

a_{1} + b_{1} < ⋯ < a_{1} + b_{l} < a_{k} + b_{1} < ⋯ < a_{k} + b_{l}.

And in the case of b_{l} = a_{k}, here we have

φ(a_{1} + b_{i}) = φ(a_{k} + b_{i}) (i = 2, …, l − 1),
φ(a_{1} + b_{1}) = φ(a_{1} + b_{l}) = φ(a_{k} + b_{l})

while all the sums above are pairwise distinct:

a_{1} + b_{1} < a_{1} + b_{2} < ⋯ < a_{1} + b_{l−1}
< a_{1} + b_{l}
< a_{k} + b_{2} < ⋯ < a_{k} + b_{l−1}
< a_{k} + b_{l}.

In either case, (5) holds, and thus (4) implies

|\overline{A} + \overline{B}| ≤ (k + 2l − 3 − δ) − l = |\overline{A}| + |\overline{B}| − 2

which in view of Kneser’s theorem shows, that \overline{A}+\overline{B} is periodic. Put H = H(\overline{A}+\overline{B}) ⊆ ℤ_{q} so that H = dℤ_{q} for some d|q, d > 0 (the requirement d > 0 effectively means |H| > 1). Moreover, if d = 1, then H = ℤ_{q}, that is \overline{A} + \overline{B} = ℤ_{q}, and hence

|A + B| ≥ |\overline{A} + \overline{B}| + l = q + l = a_{k} + l

which was to be proved. We assume therefore d > 1 and show that d|(a_{1}, …, a_{k}),— in contradiction with assumptions of the lemma.

Denote by σ the canonical homomorphism σ : ℤ_{q} → ℤ_{q}/H, and let Ã = σ\overline{A}, B̃ = σ\overline{B}. Since

|\overline{A} + H| = |Ã||H|, |\overline{B} + H| = |B̃||H|, |\overline{A} + \overline{B}| = |Ã + B̃||H|,

Kneser’s theorem gives:

|Ã + B̃| = |Ã| + |B̃| − 1,  (6)
|(\overline{A} + H) \ \overline{A}| + |(\overline{B} + H) \ \overline{B}| = |H| − (|\overline{A}| + |\overline{B}| − |\overline{A} + \overline{B}|).  (7)

Each element c ∈ A + B satisfies either σφc ∈ B̃, or σφc ∈ (Ã + B̃) \ B̃. We will now separately count the number of elements c of both types:

1. Since \overline{B} + H ⊆ \overline{A} + \overline{B}, we have:

#\{c ∈ A + B | σφc ∈ B̃\} = #\{c ∈ A + B | φc ∈ \overline{B} + H\}
≥ l + #\{\overline{c} ∈ \overline{A} + \overline{B} | \overline{c} ∈ \overline{B} + H\}
= l + |\overline{B} + H| = l + |B̃||H|.  (8)

2. We have:

#{c ∈ A + B | σφc ∈ (Ã + B̃) \ B̃} = ∑_{c̃∈(Ã+B̃)\B̃} #{c ∈ A + B | σφc = c̃}.

For each c̃ ∈ (Ã + B̃) \ B̃ fix ã ∈ Ã, b̃ ∈ B̃ in such a way, that c̃ = ã + b̃. Then

#{c ∈ A + B | σφc = c̃} ≥ |φ^{−1}σ^{−1}ã ∩ A + φ^{−1}σ^{−1}b̃ ∩ B|
≥ |φ^{−1}σ^{−1}ã ∩ A| + |φ^{−1}σ^{−1}b̃ ∩ B| − 1
≥ |σ^{−1}ã ∩ \overline{A}| + |σ^{−1}b̃ ∩ \overline{B}| − 1
≥ 2|H| − 1 − |(\overline{A} + H) \ \overline{A}| − |(\overline{B} + H) \ \overline{B}|
= |H| − 1 + |\overline{A}| + |\overline{B}| − |\overline{A} + \overline{B}|

(we used here (7)). Therefore, in view of (6),

#{c ∈ A + B | σφc ∈ (Ã + B̃) \ B̃}
≥ |(Ã + B̃) \ B̃|(|H| − 1 + |\overline{A}| + |\overline{B}| − |\overline{A} + \overline{B}|)
= (|Ã| − 1)(|H| − 1 + |\overline{A}| + |\overline{B}| − |\overline{A} + \overline{B}|).  (9)

Summing up (8) and (9) and taking into account (6), we obtain:

|A + B| ≥ l + |B̃||H| + (|Ã| − 1)(|H| − 1 + |\overline{A}| + |\overline{B}| − |\overline{A} + \overline{B}|)
= l + (|Ã| + |B̃| − 1)|H| + (|Ã| − 1)(|\overline{A}| + |\overline{B}| − |\overline{A} + \overline{B}| − 1)
= l + |\overline{A} + \overline{B}| + (|Ã| − 1)(|\overline{A}| + |\overline{B}| − |\overline{A} + \overline{B}| − 1).

Now (4) gives |A + B| ≤ (k − 1) + (l − δ) + l − 2 = |\overline{A}| + |\overline{B}| + l − 2, hence

|\overline{A}| + |\overline{B}| + l − 2 ≥ l + |\overline{A} + \overline{B}| + (|Ã| − 1)(|\overline{A}| + |\overline{B}| − |\overline{A} + \overline{B}| − 1),

that is

1 + (|Ã| − 2)(|\overline{A}| + |\overline{B}| − |\overline{A} + \overline{B}| − 1) ≤ 0,

and the obtained inequality shows, that |Ã| = 1. But in view of 0 ∈ Ã this means d|(a_{1}, …, a_{k}),— contradiction.

4. Consequences

Two situations permanently arise in applications and are worth mentioning here. The first is when B is a subset of A. This is an additional information, and we

use it to reject in Theorem 2 the restriction concerning the greatest common divisor of elements of A. This also allows to put the conclusion of the theorem in a more compact form, like that of Lemma 1.

The second situation is when we can not decide in advance which one of the two sets A and B is longer. We have to pay for this uncertainty by relaxing the estimations in Theorem 2.

In this section, we do not assume that the minimal elements of A and B are equal to 0, so the definition of δ should be changed, to say, as follows:

δ = \begin{cases}1, if A and B are of the same length \\ 0, if A and B are of different length. \end{cases}

Here by length of a set we mean the difference between its maximal and minimal elements.

We need also the notion of reduced length. For A = {a_{1}, …, a_{k}} put a′_{i} = a_{i} −a_{1} (i = 1, …, k), and denote by d the greatest common divisor of the elements of the set A′ = {a′_{1}, …, a′_{k}}. Then the reduced length of A is defined by a = a′_{k}/d.

Theorem 5. Let A be a finite set of integers of reduced length a, and B ⊆ A. Then

|A + B| ≥ min{a, k + l − 2 − δ} + l.

Proof. We define A′, d as above and put

a′′_{i} = a′_{i}/d (i = 1, …, k), A′′ = {a′′_{1}, …, a′′_{k}}
b′′_{i} = (b_{i} − b_{1})/d (i = 1, …, l), B′′ = {b′′_{1}, …, b′′_{l}},

so that a′′_{k} = a is the reduced length of A. Then our theorem follows immediately from Lemma 1 as applied to the sets A′′ and B′′. □

The second situation of the two discussed above is covered by

Theorem 6. Define d = (a′_{1}, …, a′_{k}, b′_{1}, …, b′_{l}), a = a′_{k}/d, b = b′_{l}/d (where a′_{i} = a_{i} − a_{1}, b′_{i} = b_{i} − b_{1}) and put c = max{a, b}. Then

|A + B| ≥ min{c, k + l − 2 − δ} + min{k, l}.

Proof. We may assume d = 1, a_{1} = b_{1} = 0 and also (due to the symmetry between A and B) c = a_{k} ≥ b_{l}. Then in the case of (a_{1}, …, a_{k}) = 1 we apply Lemma 1, and otherwise,— Lemma 2. □

It should be pointed out that theorems of this type are usually utilized to estimate length for a given value of |A + B|, like the following:

Corollary 1. Let A, B, a be as in Theorem 5, and assume that T = |A + B| < k + 2l − 2 − δ. Then a ≤ T − l.

Corollary 2. Let A, B, c be as in Theorem 6, and assume that T = |A + B| < k + l + min{k, l} − 2 − δ. Then c ≤ T − min{k, l}.

5. Conclusion

(This section is not present in the printed version of the paper, it is included in the “Web version” only.)

Let A = {a_{1}, …, a_{k}} and B = {b_{1}, …, b_{l}} be non-empty integer sets with 0 = a_{1} < ⋯ < a_{k}, 0 = b_{1} < ⋯ < b_{l}, and a_{k} ≥ b_{l}. Put

δ = \begin{cases}1 & if a_{k} = b_{l}, \\ 0 & if a_{k} > b_{l}. \end{cases}

The main result of the present paper (Theorem 2) is as follows.

Theorem.

(i) If a_{k} ≤ k + l − 2 − δ, then |A + B| ≥ a_{k} + l; (ii) if a_{k} ≥ k + l − 1 − δ and (a_{1}, …, a_{k}) = 1, then |A + B| ≥ k + 2l − 2 − δ.

We have also shown (Lemma 2) that if (a_{1}, …, a_{k}) > 1, while (a_{1}, …, b_{l}) = 1, then |A + B| ≥ 2k + l − 2.

Stanchescu (“On addition of two distinct sets of integers”) has improved the estimate in case (i) of the above theorem to |A + B| ≥ max{a_{k} + l, b_{l} + k}. Putting everything together, one can deduce the following

Theorem. Let A and B be finite non-empty integer sets. If

|A + B| < |A| + |B| + min{|A|, |B|} − 3

holds, then there is an integer d ≥ 1 such that A is contained in an arithmetic progression with difference d of length |A + B| − |B|, and B is contained in an arithmetic progression with difference d of length |A + B| − |A|.

References

[1] G. Freiman, On addition of finite sets, I, Izv. Vyssh. Uchebn. Zaved. Mat., 6(13)(1959), 202–213.

[2] G. Freiman, Inverse problems of additive number theory, VI. On addition of finite sets, III, Izv. Vyssh. Uchebn. Zaved. Mat., 3(28)(1962), 151–157.

[3] M. Kneser, Abschätzung der asymptotischen Dichte von Summenmengen, Math. Z., 58(1953), 459–484.

[4] M. Kneser, Ein Satz über abelschen Gruppen mit Anwendungen auf die Geometrie der Zahlen, Math. Z., 61(1955), 429–434.

[5] J. Steinig, On Freiman’s theorems concerning the sum of two finite sets of integers, in: Preprints of the conference on the Structure Theory of Set Addition, CIRM, Marseille, 1993, 173–186.

School of Mathematical Sciences, Sackler Faculty of Exact Sciences, Tel-Aviv University 69978 Tel-Aviv, Israel

  E-mail address: seva@math.tau.ac.il

2/56 Smith str., Wollongong, NSW 2000, Australia

  E-mail address: pavel@sbdev.oz.au