STRUCTURE THEOREM FOR MULTIPLE ADDITION AND THE FROBENIUS PROBLEM

VSEVOLOD F. LEV

To the memory of my father, Felix Lev

Abstract. Let A ⊆ [0; l] be a set of n integers, and let h ≥ 2. By how much does |hA| exceed |(h − 1)A|? How can one estimate |hA| in terms of n, l? We give sharp lower bounds extending and generalizing the well-known theorem of G. Freiman for |2A|.

A number of applications are provided as well. In particular, we give a solution for the old extremal problem of Frobenius-Erdős-Graham concerning estimating of the largest integer, non-representable by a linear form. In a sense, our solution can not be improved.

1. Introduction

In this section, we present a brief overview and a summary of results of the present paper. The proofs will be made in consequent sections.

Throughout the paper, A is assumed to be a set of n = |A| ≥ 2 integers, contained in the segment [0; l] and satisfying

0, l ∈ A, gcd(A) = 1.

By k we denote the positive integer satisfying

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

(if n = 2 or if n − 2 divides l − 1, there may be more than one choice for k). For h ≥ 1, by hA denote the set of all the integers representable by a sum of h elements from A.

Our main result is given by

Theorem 1. Let h ≥ 2. Then

|hA| ≥ |(h − 1)A| + min{l, h(n − 2) + 1}.

For h = 2 this turns into

|2A| ≥ n + min{l, 2n − 3}

2 VSEVOLOD F. LEV

which is a well-known and widely used theorem of Freiman (see [2]).

The method of the proof of Theorem 1 originates from that used by P. Smeliansky and the author in [7].

Define

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

The iterative application of Theorem 1 leads to

Corollary 1. We have:

|hA| ≥ \{ \begin{matrix}B_{h}(n), & if h ≤ k, \\ B_{k}(n) + (h − k)l, & if h ≥ k. \end{matrix}

In [6], we defined dense sets as those for which l ≤ 2n − 3; in other words, the number of “gaps” of A in the segment [1; l − 1] (that is l + 1 − n) should not exceed the number of elements of A in the same segment (that is n − 2). The important property of dense set is that its multiples contain long intervals of succesive integers: in [6], we showed that [l; (h − 1)l] ∩ ℤ ⊂ hA for h ≥ 2; and in [3], it was shown that [2l − 2n + 2; 2n − 2] ∩ ℤ ⊆ 2A. In Section 4 we deduce from Theorem 1 the following result:

Theorem 2. The set kA is dense and

|kA| ≥ B_{k}(n) = \frac{k(k + 1)}{2}n − (k^{2} − 1).

As to the structure of those h for which hA is dense, we prove that they form a ray [h_{0}; ∞[ (where h_{0} ≤ k, as it follows from the last theorem). We obtain this as a corollary of the next theorem showing that the sequence of densities of hA is increasing:

Theorem 3. Let h ≥ 2. Then

\frac{1}{h}(|hA| − 1|) ≥ \frac{1}{h − 1}(|(h − 1)A| − 1).

This theorem allows us to estimate |hA| by means of |(h − 1)A|, and under certain circumstances this estimation is better than that of Theorem 1.

Consider the linear form

a_{1}x_{1} + ⋯ + a_{n}x_{n}

where the variables x_{1}, …, x_{n} assume non-negative integer values, and the coefficients a_{1}, …, a_{n} are positive integers, coprime and pairwise distinct:

0 < a_{1} < ⋯ < a_{n} = l, gcd(a_{1}, …, a_{n}) = 1.

STRUCTURE THEOREM FOR MULTIPLE ADDITION 3

It is well-known that the above form represents all sufficiently large integers and it is customary to denote by G = G(a_{1}, …, a_{n}) the largest integer which has no such representation. Futuremore, define

g(n, l) = max_{a_{n}=l} G,

the maximum being taken over all sets of n coefficients with the maximal coefficient equals to l.

For l ≤ 2n, the value of g(n, l) may be easily calculated. For l < 2n + c\sqrt{n} with sufficiently small positive c, the value of g(n, l) was found by P. Erdős and R.L. Graham in [1]. For l ≤ 3n−2 this was done by the author in [6]. In Section 5 below, we use Theorem 1 to obtain the following result:

Theorem 4. Let κ satisfy κ(n − 1) + 1 ≤ l ≤ (κ + 1)(n − 1) + 1 (we always may choose κ = ⌊\frac{l−1}{n−1}⌋). Then

g(n, l) ≤ (2κl − κ(κ + 1)n) + κ^{2} − κ − 1.

We also show that the estimation of this theorem is best possible in a sense: namely, it is attained if l is divisible by κ + 1 (in other cases, it may exceed the real value of g(n, l) by at most O(κ^{2}) = O(l^{2}/n^{2}), while one can easily see that the main term is of the order l^{2}/n).

Observe, that

(2κl − κ(κ + 1)n) + κ^{2} − κ = κ(l − ρ),

where ρ = (κ + 1)(n − 1) + 2 − l.

2. Proof of Corollary 1. The extremal set

Below, we deduce Corollary 1 from Theorem 1 and also expose the “worst” set for which the estimation of the corollary is reached.

Proof of Corollary 1. We use induction on h. The case of h = 1 is trivial, and let h ≥ 2. If h ≤ k, then l ≥ k(n − 2) + 1 ≥ h(n − 2) + 1, and by Theorem 1

|hA| ≥ |(h − 1)A| + h(n − 2) + 1 ≥
≥ (\frac{1}{2}h(h − 1) + h) (n − 2) + h + 1 = B_{h}(n).

If h ≥ k + 1, then l ≤ (k + 1)(n − 2) + 1 ≤ h(n − 2) + 1, and by Theorem 1

|hA| ≥ |(h − 1)A| + l ≥
≥ B_{k}(n) + (h − 1 − k)l + l = B_{k}(n) + (h − k)l.

□

Here is the construction of the “worst” set. Let

A = {0, …, n − 2} ∪ {l}.

Then obviously

hA = ⋃_{j=0}^{h} L_{j}, L_{j} = {jl, jl + 1, …, jl + (h − j)(n − 2)},

where the number of elements in L_{j} is |L_{j}| = (h − j)(n − 2) + 1. Clearly, each of the segments L_{j} (1 ≤ j ≤ h) begins to the right from the beginning of the previous segment L_{j−1}, but generally speaking may intersect it.

If h ≤ k then all L_{j} are pairwise disjoint in view of

l ≥ k(n − 2) + 1 > h(n − 2) ≥ (h − j)(n − 2),
(j + 1)l > jl + (h − j)(n − 2).

Hence

|hA| = ∑_{j=0}^{h} |L_{j}| = (n − 2) ∑_{j=0}^{h}(h − j) + h + 1 = B_{h}(n).

Now, if h < k, then one easily verifyes that all L_{j} with h − k ≤ j ≤ h are pairwise disjoint, while all L_{j} with 0 ≤ j ≤ k − h “sticks” into the single segment [0; (h − k)l + k(n − 2)]. Hence hA is the disjoint union

hA = [0; (h − k)l + k(n − 2)] ∪ L_{h−k+1} ∪ ⋯ ∪ L_{h},

and so

|hA| = (h − k)l + k(n − 2) + 1 + (n − 2) ∑_{j=h−k+1}^{h}(h − j) + k =

= (h − k)l + k(n − 2) + (n − 2) ∑_{j=0}^{k−1} j + k + 1 =
= B_{k}(n) + (h − k)l.

3. Proof of Theorem 1

The case of n = 2 is trivial, and we assume below n ≥ 3.

Notation. Let \overline{A} be the image of A under the canonical homomorphism ℤ → ℤ_{l} onto the group of residue classes modulo l; thus, |\overline{A}| = n − 1, 0 ∈ \overline{A} and \overline{A} is contained in no proper subgroup of ℤ_{l} (this is because gcd(A) = 1). Also, the image of an integer c will be denoted by \overline{c}.

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

|hA| ≥ |(h − 1)A| + l.

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

Below, we assume H ≠ ℤ_{l}. Observe, that this implies

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

since otherwise we would have

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

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

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

This subgroup must therefore be the whole ℤ_{l}, thus also h\overline{A} = (h−1)\overline{A}+H = ℤ_{l}, and so H = ℤ_{l}, a contradiction. Estimating #\{c ∈ hA | \overline{c} ∈ (h − 1)\overline{A}\}. As above, in each class \overline{c} ∈ (h − 1)\overline{A} there exists an integer c ∈ hA \ (h − 1)A, and therefore

#\{c ∈ hA | \overline{c} ∈ (h − 1)\overline{A}\} ≥
≥ #\{c ∈ (h − 1)A | \overline{c} ∈ (h − 1)\overline{A}\} + |(h − 1)\overline{A}| =
= |(h − 1)A| + |(h − 1)\overline{A}|.  (2)

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

#\{c ∈ hA | \overline{c} ∈ ((h − 1)\overline{A} + H) \ (h − 1)\overline{A}\} ≥
≥ |((h − 1)\overline{A} + H) \ (h − 1)\overline{A}| =
= |(h − 1)\overline{A} + H| − |(h − 1)\overline{A}|.  (3)

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

#\{c ∈ hA | \overline{c} ∈ h\overline{A} \ ((h − 1)\overline{A} + H)\} ≥
≥ |h\overline{A} \ ((h − 1)\overline{A} + H)| =
= |h\overline{A}| − |(h − 1)\overline{A} + H|,

which in the case of |h\overline{A}| ≥ h|\overline{A}| − (h − 1) immediately gives

#\{c ∈ hA | \overline{c} ∈ h\overline{A} \ ((h − 1)\overline{A} + H)\} ≥
≥ h|\overline{A}| − (h − 1) − |(h − 1)\overline{A} + H|.  (4)

We prove that this estimation holds true also in the case of

|h\overline{A}| ≤ h|\overline{A}| − (h − 1).  (5)

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

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

Let \overline{A}_{i} = (\overline{a}_{i} + H) ∩ \overline{A} and A_{i} = \{a ∈ A | \overline{a} ∈ \overline{A}_{i}\} (i = 1, …, h) (that is \overline{A}_{i} is the image of A_{i} in ℤ_{l}). Then

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

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

|A_{1} + ⋯ + A_{h}| ≥ |A_{1}| + ⋯ + |A_{h}| − (h − 1) ≥
≥ h|\overline{A}| + h|H| − h|\overline{A} + H| − (h − 1).  (6)

For brevity, denote the right-hand side of (6) by K. By a theorem of Kneser on addition in abelian groups (see [4, 5])

|h\overline{A}| ≥ h|\overline{A} + H| − (h − 1)|H|,

STRUCTURE THEOREM FOR MULTIPLE ADDITION 7

which together with (5) gives

h|\overline{A}| − (h − 1) ≥ h|\overline{A} + H| − (h − 1)|H|,
h|\overline{A}| + h|H| − h|\overline{A} + H| − (h − 1) ≥ |H|,

that is K ≥ |H|.

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

#\{c ∈ hA | \overline{c} ∈ h\overline{A} \ ((h − 1)\overline{A} + H)\} ≥ KN/|H| =

= (K − |H|)(N − |H|)/|H| + K + N − |H| ≥ K + N − |H| =
= h|\overline{A}| + (h − 1)|H| − h|\overline{A} + H| − (h − 1) + |h\overline{A}| − |(h − 1)\overline{A} + H| =
= h|\overline{A}| − (h − 1) − |(h − 1)\overline{A} + H| + (|h\overline{A}| − h|\overline{A} + H| + (h − 1)|H|) ≥
≥ h|\overline{A}| − (h − 1) − |(h − 1)\overline{A} + H|

(we used here Kneser’s theorem once again). Thus (4) is proved. Completion of the proof. Summing up (2), (3) and (4), we obtain:

|hA| ≥ |(h − 1)A| + |(h − 1)\overline{A}| +
+ |(h − 1)\overline{A} + H| − |(h − 1)\overline{A}| +
+ h|\overline{A}| − (h − 1) − |(h − 1)\overline{A} + H| =
= |(h − 1)A| + h|\overline{A}| − (h − 1) =
= |(h − 1)A| + h(n − 2) + 1.
□

4. Dense sets: Proofs of Theorems 2 and 3

Proof of Theorem 2. By Corollary 1

|kA| ≥ B_{k}(n) =
= \frac{k(k + 1)}{2}(n − 2) + k + 1 =
= \frac{k}{2}((k + 1)(n − 2) + 1) + \frac{k}{2} + 1 ≥
≥ \frac{lk + k + 2}{2} ≥
≥ \frac{lk + 3}{2},

hence lk ≤ 2|kA| − 3 and kA is dense. □

Proof of Theorem 3. For i = 0, …, h − 1 we have:

(h − 1)A ∩ [0; il[⊆ hA ∩ [0; il[,
(h − 1)A ∩ [il; (h − 1)l] + l ⊆ hA ∩ [(i + 1)l; hl].

The first follows from (h − 1)A ⊆ hA, the second, — from (h − 1)A + l ⊆ hA. Therefore,

|(h − 1)A| ≤ |hA \ [il; (i + 1)l[|.

Summing up over all i, we obtain

h|(h − 1)A| ≤ h|hA| − |hA ∩ [0; hl[| = (h − 1)|hA| + 1

which was to be proved. □

Corollary 2. If h ≥ 2 and (h − 1)A is dense, so is hA.

Proof. If (h − 1)A is dense, then (h − 1)l ≤ 2|(h − 1)A| − 3, and by Theorem 3

|hA| ≥ 1 + \frac{h}{h − 1}(|(h − 1)A| − 1) ≥
≥ 1 + \frac{h}{h − 1} \frac{(h − 1)l + 1}{2} >
> 1 + \frac{h}{h − 1} \frac{(h − 1)l}{2} + \frac{1}{2} =
= \frac{hl + 3}{2},

hence hl < 2|hA| − 3 and hA is dense. □

5. The extremal problem of Frobenius-Erdős-Graham: Proof of Theorem 4

The case of κ = 0 is trivial (here l = n), assume therefore κ ≥ 1.

Let A′ = {0, a_{1}, …, a_{n}} (so that |A′| = n + 1) and let G(A′) abbreviates G(a_{1}, …, a_{n}). It was shown in [6] that G(A′) = G(hA′) for every h, and also that if hA′ is dense, then

G(hA′) ≤ 2(hl − |hA′|) + 1.

Choose h = κ. Then hA′ is dense for our choice of κ by Theorem 2, and applying this theorem also to estimate |κA′|, we obtain:

G(A′) = G(κA′) ≤ 2(κl − |κA′|) + 1 ≤
≤ 2(κl − B_{κ}(n + 1)) + 1 =
= 2κl − κ(κ + 1)(n − 1) − 2κ − 1 =
= (2κl − κ(κ + 1)n) + κ^{2} − κ − 1.
□

Here is an example showing that the obtained estimation is exact for (κ + 1)|l. Define t = l/(κ + 1) (hence t ≤ n − 1) and let

A′ = {0, κ + 1, …, t(κ + 1)} ∪
{l − 1 − (n − 1 − t)(κ + 1), l − 1 − (n − 2 − t)(κ + 1), …, l − 1}.

Then it is easily seen that

G(A′) = G(κ + 1, l − 1 − (n − 1 − t)(κ + 1)) =
= κ(l − 2 − (n − 1 − t)(κ + 1)) − 1 =
= κl − κ(κ + 1)n + tκ(κ + 1) + κ(κ + 1) − 2κ − 1 =
= (2κl − κ(κ + 1)n) + κ^{2} − κ − 1.

References

[1] P. Erdős and R.L. Graham, On a linear diophantine problem of Frobenius, Acta Arith. XXI (1972), 399–408.

[2] G.A. Freiman, “Foundations of a structural theory of set addition”, Kazan. Gos. Ped. Inst., Kazan, 1966 [Russian]. English translation in: Translations of Math. Monographs, 37 (1973), American Math. Soc., Providence.

[3] G.A. Freiman, Sumsets and powers of 2, Colloq. Math. Soc. János Bolyai, 60 (1992), North-Holland, Amsterdam.

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

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

[6] V.F. Lev, On the extremal aspect of the Frobenius’ problem, Journal of Combinatorial Theory, Series A, to appear.

[7] V.F. Lev and P.Y. Smeliansky, On addition of different sets of integers, Acta Arithmetica, to appear.

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

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