ADDENDUM TO

“STRUCTURE THEOREM FOR MULTIPLE ADDITION”

VSEVOLOD F. LEV

Abstract. In our earlier paper we gave a sharp lower-bound estimate for the cardinality of hA = A+⋯+A (A being a finite set of integers). It appears that certain applications require this estimate to be generalized for the case of distinct summands. Below we obtain such a generalization by estimating the cardinality of A_{1} + ⋯ + A_{h} (A_{i} being distinct finite sets of integers).

In the present paper, we prove the following theorem, generalizing both [4, Theorem 1] and [5, Theorem 2]:

Theorem. Let A_{1}, …, A_{h} ⊆ [0; l] be non-empty sets of integers, and assume that 0, l ∈ A_{h} and gcd(A_{h}) = 1. For i = 1, …, h set

n_{i} = \begin{cases}|A_{i}|, & if either 0 ∉ A_{i}, or l ∉ A_{i}, \\ |A_{i}| − 1, & if 0, l ∈ A_{i}. \end{cases} .

Then

|A_{1} + ⋯ + A_{h}| − |A_{1} + ⋯ + A_{h−1}| ≥ min{l, n_{1} + ⋯ + n_{h} − h + 1}.

Let A ⊆ [0; l] be a set of integers of the cardinality n ≥ 2 and satisfying 0, l ∈ A, gcd(A) = 1. For h_{1}, h_{2} ≥ 1 define h = h_{1} + h_{2} and write

A_{i} = \begin{cases}A, & if 1 ≤ i ≤ h_{1}, \\ l − A, & if h_{1} < i ≤ h. \end{cases}

Then evidently |h_{1}A − h_{2}A| = |A_{1} + ⋯ + A_{h}|, and using induction exactly in the same way as in [4], one can derive the following corollary:

Corollary. Let A, h_{1}, h_{2} satisfy the assumptions above, and let k ≥ 1 be the integer satisfying

k(n − 2) + 1 ≤ l ≤ (k + 1)(n − 2) + 1

(thus, k characterizes the density of A). Then

|h_{1}A − h_{2}A| ≥ \begin{cases}B_{h}(n), & if h ≤ k, \\ B_{k}(n) + (h − k)l, & if h ≥ k, \end{cases}

where

B_{h}(n) = \frac{h(h + 1)}{2}(n − 2) + h + 1.

Proof of the theorem. The proof follows that of [4, Theorem 1] with certain modifications.

If |A_{h}| = 2 then clearly l = 1, n_{1} = ⋯ = n_{h} = 1 and the assertion holds trivially; therefore, we assume below |A_{h}| ≥ 3, which means n_{h} ≥ 2. Notation. For C ⊂ ℤ, let \overline{C} be the image of C under the canonical homomorphism ℤ → ℤ_{l} onto the group of residue classes modulo l; thus, |\overline{A}_{i}| = n_{i} (i = 1, …, h) and 0 ∈ \overline{A}_{h}. Also, the image of an integer c will be denoted by \overline{c}.

For brevity, we write S_{h−1} = A_{1} + ⋯ + A_{h−1} and S_{h} = A_{1} + ⋯ + A_{h}. By H we denote the period of the set \overline{S}_{h}, that is the set of all those residue classes \overline{c} which satisfy \overline{S}_{h} +\overline{c} = \overline{S}_{h}. Evidently, H ⊆ ℤ_{l} is a subgroup, \overline{S}_{h} is a union of certain H-cosets, and the relation H = ℤ_{l} is equivalent to \overline{S}_{h} = ℤ_{l}. The case H = ℤ_{l}. We show that in this case in each class \overline{c} ∈ ℤ_{l} there exists an integer c ∈ S_{h} \ S_{h−1}, and therefore

|S_{h}| ≥ |S_{h−1}| + l.

Indeed, such an integer obviously exits if \overline{c} ∉ \overline{S}_{h−1} (since \overline{c} ∈ ℤ_{l} = \overline{S}_{h}, thus \overline{c} has an origin in S_{h}). And if \overline{c} ∈ \overline{S}_{h−1}, then choose c = c_{0} + l, where c_{0} is the maximal element of S_{h−1} from the class \overline{c}. Since c_{0} ∈ S_{h−1}, l ∈ A_{h} one has c ∈ S_{h}.

In what follows we assume H ≠ ℤ_{l}. Observe, that this implies

\overline{S}_{h−1} + H ≠ \overline{S}_{h}  (1)

since otherwise we would have

\overline{S}_{h−1} + H = (\overline{S}_{h−1} + H) + \overline{A}_{h},

and hence \overline{A}_{h} should lie in the subgroup of all those \overline{c} satisfying

\overline{S}_{h−1} + H = (\overline{S}_{h−1} + H) + \overline{c}.

ADDENDUM 3

This subgroup must therefore be the whole ℤ_{l} (as in view of gcd(A_{h}) = 1 the only subgroup of ℤ_{l} containing A_{h} is ℤ_{l} itself), thus \overline{S}_{h} = \overline{S}_{h−1} + H = ℤ_{l}, and so H = ℤ_{l}, a contradiction. Estimating #\{c ∈ S_{h} | \overline{c} ∈ \overline{S}_{h−1}\}. Since 0 ∈ A_{h}, we have S_{h−1} ⊆ S_{h}; besides, as above, in each residue class \overline{c} ∈ \overline{S}_{h−1} there exists an integer c ∈ S_{h} \ S_{h−1}. Therefore

#\{c ∈ S_{h} | \overline{c} ∈ \overline{S}_{h−1}\} ≥ |S_{h−1}| + |\overline{S}_{h−1}|.  (2)

Estimating #\{c ∈ S_{h} | \overline{c} ∈ (\overline{S}_{h−1} + H) \ \overline{S}_{h−1}\}. Since \overline{S}_{h−1} + H ⊆ \overline{S}_{h}, in each class \overline{c} ∈ \overline{S}_{h−1} + H there exists an integer c ∈ S_{h}, and thus

\begin{matrix}#\{c ∈ & S_{h} | \overline{c} ∈ (\overline{S}_{h−1} + H) \ \overline{S}_{h−1}\} \\ ≥ |(\overline{S}_{h−1} + H) \ \overline{S}_{h−1}| \\ = |\overline{S}_{h−1} + H| − |\overline{S}_{h−1}|. \end{matrix}  (3)

Estimating #\{c ∈ S_{h} | \overline{c} ∈ \overline{S}_{h} \ (\overline{S}_{h−1} + H)\}. Since in each residue class \overline{c} ∈ \overline{S}_{h} \ (\overline{S}_{h−1} + H) there exists an integer c ∈ S_{h}, we have:

#\{c ∈S_{h} | \overline{c} ∈ \overline{S}_{h} \ (\overline{S}_{h−1} + H)\}
≥ |\overline{S}_{h} \ (\overline{S}_{h−1} + H)|
= |\overline{S}_{h}| − |\overline{S}_{h−1} + H|.

In case |\overline{S}_{h}| ≥ n_{1} + ⋯ + n_{h} − (h − 1) this immediately yields

\begin{matrix}#\{c ∈ S_{h} | \overline{c} ∈ \overline{S}_{h} \ (\overline{S}_{h−1} + H)\} \\ ≥ n_{1} + ⋯ + n_{h} − (h − 1) − |\overline{S}_{h−1} + H|. \end{matrix}  (4)

We prove that this latter estimate holds true also in the case

|\overline{S}_{h}| ≤ n_{1} + ⋯ + n_{h} − (h − 1).  (5)

The set \overline{S}_{h} \ (\overline{S}_{h−1} + H) is a union of certain H-cosets of the form

\overline{c} + H, \overline{c} = \overline{a}_{1} + ⋯ + \overline{a}_{h}; a_{i} ∈ A_{i} \ \{0, l\}.

Let A_{i} = \{a ∈ A_{i} | \overline{a} ∈ \overline{a}_{i} + H\} (i = 1, …, h), so that \overline{A}_{i} = (\overline{a}_{i} + H) ∩ \overline{A}_{i}. Then

|A_{i}| = |\overline{A}_{i}| = |H| − |(\overline{a}_{i} + H) \ \overline{A}_{i}|
≥ |H| − |(\overline{A}_{i} + H) \ \overline{A}_{i}|
= |\overline{A}_{i}| + |H| − |\overline{A}_{i} + H|.

Evidently A_{1} + ⋯ + A_{h} is mapped into \overline{c} + H, and thus the total number of preimages of \overline{c} + H in S_{h} is at least

|A_{1} + ⋯ + A_{h}| ≥ |A_{1}| + ⋯ + |A_{h}| − (h − 1)

≥ ∑_{i=1}^{h} n_{i} + h|H| − ∑_{i=1}^{h} |\overline{A}_{i} + H| − (h − 1). (6)

Denote the right-hand side of (6) by K. By the theorem of Kneser on set addition in abelian groups (see [2, 3])

|\overline{S}_{h}| ≥ ∑_{i=1}^{h} |\overline{A}_{i} + H| − (h − 1)|H|,

which together with (5) gives

∑_{i=1}^{h} n_{i} − (h − 1) ≥ ∑_{i=1}^{h} |\overline{A}_{i} + H| − (h − 1)|H|,

∑_{i=1}^{h} n_{i} + h|H| − ∑_{i=1}^{h} |\overline{A}_{i} + H| − (h − 1) ≥ |H|,

that is K ≥ |H|.

The number of H-cosets in \overline{S}_{h} \ (\overline{S}_{h−1} + H) is N/|H| where N = |\overline{S}_{h}| − |\overline{S}_{h−1} + H| ≥ |H| (by (1)) and therefore

#\{c ∈S_{h} | \overline{c} ∈ \overline{S}_{h} \ (\overline{S}_{h−1} + H)\} ≥ KN/|H|

= (K − |H|)(N − |H|)/|H| + K + N − |H| ≥ K + N − |H|

= ∑_{i=1}^{h} n_{i} + (h − 1)|H| − ∑_{i=1}^{h} |\overline{A}_{i} + H| − (h − 1) + |\overline{S}_{h}| − |\overline{S}_{h−1} + H|

= ∑_{i=1}^{h} n_{i} − (h − 1) − |\overline{S}_{h−1} + H|

+ (|\overline{S}_{h}| − ∑_{i=1}^{h} |\overline{A}_{i} + H| + (h − 1)|H|)

≥ ∑_{i=1}^{h} n_{i} − (h − 1) − |\overline{S}_{h−1} + H|

(we use here Kneser’s theorem once again). Thus (4) is proved.

Completion of the proof. Summing up (2), (3) and (4), we obtain:

|S_{h}| ≥ (|S_{h−1}| + |\overline{S}_{h−1}|) + (|\overline{S}_{h−1} + H| − |\overline{S}_{h−1}|)

+ ( ∑_{i=1}^{h} n_{i} − (h − 1) − |\overline{S}_{h−1} + H|)

= |S_{h−1}| + n_{1} + ⋯ + n_{h} − h + 1.

□

Priority remark In [4], as an application of [4, Corollary 1], we proved a result concerning the linear Diophantine problem of Frobenius. When the paper was already in press, the author was informed that this result was obtained a few years earlier by J. Dixmier (see [1]), whom we completely credit for it.

References

[1] J. Dixmier, Proof of a conjecture by Erdős and Graham concerning the problem of Frobenius, J. Number Theory 34 (1990), 198–209.

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

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

[4] V. Lev, Structure theorem for multiple addition and the Frobenius problem, J. Number Theory 58(1) (1996), 79–88.

[5] V. Lev and P. Smeliansky, On addition of two distinct sets of integers, Acta Arithmetica LXX.1 (1995), 85–91.

School of Math. Sciences, Tel-Aviv University, 69978 Tel-Aviv, Israel

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