ON CONSECUTIVE SUBSET SUMS

VSEVOLOD F. LEV

Abstract. We consider the subset sums analog of the linear Diophantine problem of Frobenius. It is shown that if A ⊆ [1; l] is a sufficiently dense set of n positive integers, then

[2l − 2n + 1; σ − (2l − 2n + 1)] ⊆ A^{∗},

where σ is the sum of all elements of A, and A^{∗} is the set of all subset sums of A. The interval above is best possible and can not be extended.

1. Introduction

For l ∈ ℤ, l ≥ 1 let A ⊆ [1; l] be a non-empty set of n = |A| co-prime integers. Denote the elements of A by a_{1}, …, a_{n} and consider the linear form

L = a_{1}x_{1} + ⋯ + a_{n}x_{n},

where the variables x_{i} assume non-negative integer values. It is well-known that the set of integers representable by L contains all sufficiently large numbers. The linear Diophantine problem of Frobenius consists in determining the smallest G(A) such that all the integers g ≥ G(A) can be represented. The extremal version of this problem, proposed by P. Erdős and R. Graham in [3], deals with the smallest G(n, l) such that all the integers g ≥ G(n, l) can be represented for each n-element set A ⊆ [0; l] (see [2, 7, 8] for more details).

If we restrict x_{i} to the values 0 and 1 then the set of integers representable by L will be

A^{∗} = ⋃_{h=0}^{n} h·A,

where h·A stands for the set of all h-subset sums of A:

h·A = {_{∑b∈B} b: B ⊆ A, |B| = h}

(this set is often denoted hˆ A, but we prefer the notation above). Let σ = Σ(A) be the sum of all elements of A. Clearly, A^{∗} ⊆ [0; σ] (here and below all intervals are considered to be subsets of ℤ). It is also clear that m belongs to A^{∗} if and only if σ − m does; thus, A^{∗} is symmetrical around \frac{1}{2}σ.

One can show that for dense A the sets h·A and A^{∗} contain long chains of consecutive integers. This phenomenon has been studied in numerous papers; see [1, 4, 5, 6, 9].

2 VSEVOLOD F. LEV

In virtually all cases the analytical circle method was used, and thus the results available hold only for very large n and often depend on some large or even non-effective constants. Perhaps, the only exception is [6] where the problem is treated with elementary means.

Suppose m ∈ [0; σ]. Heuristic arguments show that the closer m is to \frac{1}{2}σ, the more likely we have m ∈ A^{∗}. Along with the above considerations this suggests that A^{∗} should contain a long interval of integers, centered at \frac{1}{2}σ. Indeed, a result of this type was obtained in [1], where it is proved that for A sufficiently dense (and n large enough) A^{∗} contains an interval I, centered around \frac{1}{2}σ, provided that there is no residue class modulo an integer d > 1 which contains “almost all” elements of A. (Examples of the type A = {3, 6, 9, 10} show that the last condition is essential.) The length of the interval I was estimated from below as (∑ a_{i}^{2})^{1/2}.

However, the following problem remained open: determine the minimal integer F = F (n, l) ≤ \frac{1}{2}σ such that [F; σ − F] ⊆ A^{∗} for all A. This problem may be considered as the subset sums counterpart of the extremal version of the Frobenius problem. Note that, as the example above shows, F (n, l) may not be defined for all n and l if we do not impose additional restrictions on A.

This paper is intended as an attempt to do a first step in the investigation of this subject. Our main result is the following.

Theorem 1. Let A ⊆ [1; l] be a set of n ≥ 1 integers, and assume that l ≤ \frac{3}{2}n − 2. Then

[2l − 2n + 1; σ − (2l − 2n + 1)] ⊆ A^{∗}.

If A = {l − n, l − n + 1, …, 2l − 2n − 1} ∪ {2l − 2n + 1, 2l − 2n + 2, …, l}, then evidently 2l − 2n ∉ A^{∗}, and thus the interval in the formulation of the theorem can not be enlarged. However, the condition l ≤ \frac{3}{2}n − 2 is far from being tight, and even a slight refinement of our method (not presented here) allows one to replace the coefficient \frac{3}{2} by \frac{1}{6}(7 + \sqrt{7}) ≈ 1.6. We conjecture that actually the sharp bound here would be l ≤ 2n − 3.

Note that the length of the interval of Theorem 1 is of the order of magnitude σ ≍ n^{2}, while the length of the interval of [1] is only (∑ a_{i}^{2})^{1/2} ≍ n^{3/2} (for l ≪ n).

This paper is organized as follows. In Section 2 we study the structure of the sets h·A and show that these sets contain long intervals of integers. In Section 3 we “glue together” the intervals in individual h·A to get a longer interval in A^{∗}.

2. Long intervals in h·A

The following simple lemma will be used repeatedly.

Lemma 1. Let A be a set of integers, and let α, β be two integers, such that α ≤ β. Assume that

2|A ∩ [α; β]| > β − α + 2.

Then α + β ∈ 2·A.

Proof. Suppose α + β ∉ 2 · A. Define J = ⌊(β − α)/2⌋ and let j ∈ [0; J]. Then each integer from [α; β] falls into one of the pairs (α + j, β − j), and in each pair there is at most one element of A. Hence we obtain

|A ∩ [α; β]| ≤ J + 1 ≤ \frac{1}{2}(β − α) + 1.
□

For l ≤ 2n − 2 consider

A = {1, 2, …, l − n + 1} ∪ {2l − 2n + 2, 2l − 2n + 3, …, l}.

It is easily seen that 2l −2n+2 ∉ 2·A, and replacing A by l +1−A we obtain the set A′ with 2n ∉ 2 · A′. On the other hand, we prove now that all the integers between these two must lie in 2·A, provided A is sufficiently dense.

Proposition 1. Let A ⊆ [1; l] be a set of n ≥ 1 integers, and assume that l ≤ 2n − 2. Then

[l + 1 − (2n − 2 − l); l + 1 + (2n − 2 − l)] ⊆ 2·A.

Proof. Assume first m ∈ [l + 1 − (2n − 2 − l); l + 1] and show that m ∈ 2·A. We have:

2|A ∩ [1; m − 1]| ≥ 2(m − 1 − (l − n)) = m + (m − 2l − 2 + 2n) > m,

hence m ∈ 2·A by Lemma 1.

Now, if m ∈ [l + 2; l + 1 + (2n − 2 − l)] we apply the already proved assertion to the set l + 1 − A and the integer 2l + 2 − m ∈ [l + 1 − (2n − 2 − l); l] to see that 2l + 2 − m ∈ 2·(l + 1 − A), which is equivalent to m ∈ 2·A. □

For further references, we denote

I_{2} = [l + 1 − (2n − 2 − l); l + 1 + (2n − 2 − l)],

and for h = 3, …, n let

I_{h} = [(h − 1)l − (h − 1)n + \frac{1}{2}h(h + 1); l + (h − 1)n − \frac{1}{2}h(h + 1) + h].

It is a simple matter to verify that I_{h} is surely non-empty if l ≤ 2n − h: indeed, in this case

(l + (h − 1)n − \frac{1}{2}h(h + 1) + h) − ((h − 1)l − (h − 1)n + \frac{1}{2}h(h + 1))
= 2(h − 1)n − h^{2} − (h − 2)l
≥ 2(h − 1)n − h^{2} − (h − 2)(2n − h)
= 2(n − h)
≥ 0.

Obviously, the restriction l ≤ 2n−2 in Proposition 1 is best possible for if l ≥ 2n−1, then interval I_{2} degenerates. At the same time, if we require somewhat more, we can derive a much stronger conclusion:

Proposition 1′. Let A ⊆ [1; l] be a set of n ≥ 1 integers, and assume that l ≤ \frac{1}{2}(3n − 3). Then 2·A contains an interval of at least 2n − 3 successive integers (and thus necessarily contains I_{2}).

This proposition will not be used in the sequel. However, it is of some independent interest, and since the proof is rather short, we present it below.

Proof. If [3; l] ⊆ 2 · A or [l + 2; 2l − 1] ⊆ 2 · A then the assertion follows immediately by Proposition 1. Else, let g′, g′′ ∉ 2·A satisfy

3 ≤ g′ < l + 1 < g′′ ≤ 2l − 1.

We prove that g′′ − g′ ≥ 2n − 2.

By Lemma 1 we have:

2|A ∩ [1; g′ − 1]| ≤ g′,  (1)
2|A ∩ [g′′ − l; l]| ≤ 2l − g′′ + 2,  (2)

and we distinguish two cases. I. If g′ − 1 < g′′ − l then we sum up (1), (2) and the obvious inequality

2|A ∩ [g′; g′′ − l − 1]| ≤ 2(g′′ − g′ − l)

to obtain

2n ≤ g′′ − g′ + 2

which yields g′′ − g′ ≥ 2n − 2 as claimed.

ON CONSECUTIVE SUBSET SUMS 5

II. If g′ − 1 ≥ g′′ − l then summing up (1) and (2) and using Proposition 1 we obtain

2n ≤ 2l + 2 − (g′′ − g′) ≤ 2l − 2(2n − 2 − l) = 4l − 4n + 4,
2l ≥ 3n − 2,

a contradiction, showing that this case is actually impossible. □

Turning to the sets h·A with h ≥ 3, we assume 1, l ∈ A (the general result will be derived from this particular case). Let

A = {1} ∪ {l − n + 2, l − n + 3, …, l}.

Then obviously

(l − n + 2) + ⋯ + (l − n + h) = (h − 1)l − (h − 1)n + \frac{1}{2}h(h + 1) − 1 ∉ h·A,

and replacing A by l + 1 − A we obtain the set A′ with

l + (h − 1)n − \frac{1}{2}h(h + 1) + h + 1 ∉ h·A′.

We prove that all the integers between these two must lie in h · A, provided A is sufficiently dense.

Proposition 2. Let A ⊆ [1; l] be a set of n ≥ 1 integers, such that 1, l ∈ A, and let h ≥ 3. Assume that l ≤ 2n − h − 1. Then I_{h} ⊆ h·A.

Proof. We use induction by h. For h = 3 we have I_{3} = [2l − 2n + 6; l + 2n − 3] and it suffices to show that m ∈ 3 · A for every integer m ∈ [2l − 2n + 6; 2l] (then for m ∈ [2l + 1; l + 2n − 3] one can apply this result to l + 1 − A and 3l + 3 − m ∈ [2l − 2n + 6; l + 2] to obtain 3l + 3 − m ∈ 3 · (l + 1 − A), which is equivalent to m ∈ 3·A). Consider two cases.

If m ≤ l + 2, then

2|A ∩ [2; m − 3]| ≥ 2(m − 4 − (l − n)) = m − 2 + (m − 2l + 2n − 6) > m − 3,

hence (by Lemma 1) m − 1 is the sum of 2 distinct elements of A, greater than 1, and then m is the sum of 3 distinct elements of A, one of which equals 1.

Now let l + 3 ≤ m ≤ 2l. If m − l − 1 ∈ A, then we have the representation m = 1 + (m − l − 1) + l, therefore we assume m − l − 1 ∉ A. Define

A′ = A ∩ [2; m − l − 2], A′′ = A ∩ [m − l; l − 1].

If 2|A′| > m − l − 2 or 2|A′′| > 2l − m + 1 then we can apply Lemma 1 as above. But otherwise

2|A| ≤ (m − l − 2) + (2l − m + 1) + 4 = l + 3,

a contradiction.

We now turn to the induction step. Let h ≥ 4. It is sufficient to prove that m ∈ h·A for each integer m satisfying

\frac{1}{2}h(l + 1) ≤ m ≤ l + (h − 1)n − \frac{1}{2}h(h + 1) + h.

Let A = A′ ∪{l}, where A′ is a set of n−1 integers, and denote the maximum element of A′ by l′. Then l′ ≤ l −1 ≤ 2(n−1)−(h−1)−1, hence by the induction hypothesis

[(h−2)l′−(h−2)(n−1)+ \frac{1}{2}h(h−1); l′+(h−2)(n−1)− \frac{1}{2}h(h−1)+(h−1)] ⊆ (h−1)·A′,

and if we prove that m − l falls into this interval, the assertion follows. Thus, what is left to verify is that

\begin{cases}(h − 2)l′ − (h − 2)(n − 1) + \frac{1}{2}h(h − 1) ≤ \frac{1}{2}h(l + 1) − l, \\ (h − 1)n − \frac{1}{2}h(h + 1) + h ≤ l′ + (h − 2)(n − 1) − \frac{1}{2}h(h − 1) + (h − 1). \end{cases}

But one can rewrite this as

\begin{cases}l′ − (n − 1) + \frac{1}{2}h ≤ \frac{1}{2}l, \\ n ≤ l′ + 1, \end{cases}

and here the second inequality is obvious, while the first follows from

l′ ≤ l − 1 ≤ \frac{1}{2}l + \frac{1}{2}(2n − h − 1) − 1 = \frac{1}{2}l + (n − 1) − \frac{1}{2}h − \frac{1}{2}.
□

Remark 1. A careful examination of the proof shows that actually we obtained somewhat more than was claimed. Namely, we proved that every integer m ∈ I_{h} has a representation as a sum of h distinct elements of A, where all but at most two elements are picked out “from the ends” of the set A.

Remark 2. The restriction l ≤ 2n − h − 1 of the last proposition can be easily verified to be best possible for h = 3. For h = 4 we guess that the sharp upper bound would be l ≤ 2n − 2 (provided n ≥ 8). At the same time, we conjecture that for h ≥ 5 this bound is of the form l ≤ κn − C, where κ = κ(h) > 2. Once proved, such a result would make it possible to improve substantially the factor \frac{3}{2} of Theorem 1.

3. Proof of Theorem 1

The aim of the following auxiliary result is to show, that the complete intervals in h·A “glue” into a single long interval.

ON CONSECUTIVE SUBSET SUMS 7

Proposition 3. Let A ⊆ [z+1; z+l′] be a set of n ≥ 1 integers, where z+1, z+l′ ∈ A and [z + 1; z + l′] ⊆ [1; l]. Assume that l ≤ 2n − 4. Then

[2z + 2l′ − 2n + 1; \frac{1}{2}(z + l′ + 1)(2n − z − l′) + \frac{1}{2}z(z + 2n − 1) − 1] ⊆ A^{∗}.

Proof. Define H = 2n − l′ − 1. Observe, that H ≥ 2n − l − 1 ≥ 3, and if 3 ≤ h ≤ H, then l′ ≤ 2n − h − 1. By Propositions 1 and 2 (as applied to the set A − z) we have [u_{h}; v_{h}] ⊆ A^{∗} for h = 2, …, H, where

u_{2} = 2z + 2l′ − 2n + 3,
v_{2} = 2z + 2n − 1,
u_{h} = hz + (h − 1)(l′ − n) + \frac{1}{2}h(h + 1) (h ≥ 3),
v_{h} = hz + l′ + (h − 1)n − \frac{1}{2}h(h + 1) + h (h ≥ 3).

Note, that u_{2}, u_{3}, … is an increasing sequence, and that

v_{H} = (2n − l′ − 1)z + l′ + (2n − l′ − 2)n − \frac{1}{2}(2n − l′ − 1)(2n − l′) + (2n − l′ − 1)
= (2n − l′ − 1)z + (2n − l′)n − \frac{1}{2}(2n − l′ − 1)(2n − l′) − 1
= (2n − l′ − 1)z + \frac{1}{2}(l′ + 1)(2n − l′) − 1
= \frac{1}{2}(z + l′ + 1)(2n − z − l′) + \frac{1}{2}z(z + 2n − 1) − 1.

Thus we shall have established the assertion if we prove that:

i) Each interval [u_{h}; v_{h}] (for h = 3, …, H) “glues” to the previous one, that is

u_{h} ≤ v_{h−1} + 1;  (3)

ii) 2z + 2l′ − 2n + 1, 2z + 2l′ − 2n + 2 ∈ A^{∗}. Here are the proofs. I. We have:

u_{3} = 3z + 2l′ − 2n + 6 = (2z + 2n) + (z + 2l′ − 4n + 6) ≤ (2z + 2n) + 2(l − 2n + 3) < 2z + 2n = v_{2} + 1,

therefore proving (3) we may assume 4 ≤ h ≤ H. In this case (3) can be rewritten as

hz + (h − 1)(l′ − n) + \frac{1}{2}h(h + 1) ≤ (h − 1)z + l′ + (h − 2)n − \frac{1}{2}h(h − 1) + h,
z + (h − 2)l′ − (2h − 3)n + h^{2} − h ≤ 0,

and since z + l′ ≤ l, this will follow from

l + (h − 3)l′ − (2h − 3)n + h^{2} − h ≤ 0.

8 VSEVOLOD F. LEV

Denote the left-hand side by F (h) and consider it as a function of real h. This function is convex, thus if we prove that F (3), F (H) ≤ 0, the assertion follows. But F (3) = l − 3n + 6 ≤ 0, and

F (H) = l + (H − 3)(2n − H − 1) − (2H − 3)n + H^{2} − H
= l + H − 3n + 3
= l − l′ − n + 2
≤ l − 2n + 2
≤ 0.

II. Assume 2z + 2l′ − 2n + 1 ∉ A. We show that 2z + 2l′ − 2n + 1 ∈ 2·A. Clearly,

|A ∩ [z + 2l′ − 2n + 1; z + l′]| ≤ 2n − l′ − 1,

hence

2|A ∩ [z + 1; z + 2l′ − 2n]| ≥ 2(l′ + 1 − n) = (2l′ − 2n − 1) + 3,

therefore 2z + 2l′ − 2n + 1 ∈ 2·A by Lemma 1.

Similarly, one easily verifies that either 2z+2l′−2n+2 ∈ A, or 2z+2l′−2n+2 ∈ 2·A, which completes the proof. □

Corollary 1. Let A ⊆ [1; l] be a set of n ≥ 1 integers, and assume that l ≤ 2n − 4. Then

[2l − 2n + 1; \frac{1}{2}(l + 1)(2n − l) − 1] ⊆ A^{∗}.

Proof. Define z, l′ as in the last proposition. Then

(z + l′ + 1)(2n − z − l′) ≥ (l + 1)(2n − l),

as the function f(x) = (x + 1)(2n − x) decreases for x ≥ n − \frac{1}{2}, and l ≥ z + l′ ≥ n > n − \frac{1}{2}. □

We are now in a position to prove our main theorem.

Proof of Theorem 1. It can be easily shown that for l ≤ \frac{1+\sqrt{3}}{2}n ≈ 1.37n the interval of Corollary 1 covers the interval [2l − 2n + 1; \frac{1}{2}σ], and this evidently establishes the assertion for those l. To relax somewhat the density requirement we apply an additional trick.

Define k = l − n + 4, and let

A′ = {a_{1}, …, a_{k}}, A′′ = {a_{k+1}, …, a_{n}},

(where we assume a_{i} < a_{j} for 1 ≤ i < j ≤ n), so that A = A′ ∪ A′′. Denote

σ′ = Σ(A′), σ′′ = Σ(A′′)

ON CONSECUTIVE SUBSET SUMS 9

(that is, σ′ is the sum of all elements of A′, and σ′′ is the sum of all elements of A′′). Observe, that the definitions of A′ and A′′ are correct since k ≤ \frac{1}{2}n + 2 ≤ n.

Obviously, a_{k} ≤ l − n + k = 2k − 4, whence by Corollary 1

[2a_{k} − 2k + 1; \frac{1}{2}(a_{k} + 1)(2k − a_{k}) − 1] ⊆ (A′)^{∗}.  (4)

Note, that the interval in the left-hand side consists of

\begin{aligned}\frac{1}{2}(a_{k} + 1)(2k − a_{k}) − 1 − (2a_{k} − 2k) & ≥ 2(a_{k} + 1) − 1 − (2a_{k} − 2k) \\ & = 2k + 1 \\ & = (l − n + k + 1) + 4 \\ & > a_{k+1}, \end{aligned}  (5)

successive integers. On the other hand, if A′′ is not empty, then the difference between any two consecutive elements of A′′ does not exceed

l − a_{k+1} − n + k + 2 ≤ l − n + 1 = k − 3 < a_{k+1},

and thus the difference between any two consecutive elements of (A′′)^{∗} does not exceed a_{k+1} either. Therefore, in view of A^{∗} = (A′)^{∗} + (A′′)^{∗} and using (4) and (5) we obtain

[2a_{k} − 2k + 1; σ′′ + \frac{1}{2}(a_{k} + 1)(2k − a_{k}) − 1] ⊆ A^{∗}.

However, by Corollary 1 also

[2l − 2n + 1; \frac{1}{2}(l + 1)(2n − l) − 1] ⊆ A^{∗},

and

\frac{1}{2}(l + 1)(2n − l) − 1 ≥ 2(l + 1) − 1 > 2a_{k} − 2k + 1,
σ′′ + \frac{1}{2}(a_{k} + 1)(2k − a_{k}) − 1 ≥ 2a_{k} + 1 ≥ 2k + 1 > 2l − 2n + 1,

which yields

[2l − 2n + 1; σ′′ + \frac{1}{2}(a_{k} + 1)(2k − a_{k}) − 1] ⊆ A^{∗}.

Thus, it suffices to prove that

σ′′ + \frac{1}{2}(a_{k} + 1)(2k − a_{k}) − 1 ≥ \frac{1}{2}σ.

But this is equivalent to

σ′′ + (a_{k} + 1)(2k − a_{k}) − 2 ≥ σ′,

and it remains to observe that

σ′′ + (a_{k} + 1)(2k − a_{k}) − 2 ≥ σ′′ + 4a_{k} + 2
≥ (n − k + 4)a_{k} + 2
> (k + (3n − 2l − 4))a_{k}
≥ ka_{k}
≥ σ′.
□

References

[1] N. Alon and G. Freiman, On sums of subsets of a set of integers, Combinatorica 8 (4) (1988), 297–306.

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

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

[4] P. Erdős and G. Freiman, On two additive problems, J. Number Theory 34 (1) (1990), 1–12.

[5] G. Freiman, Subset-sum problem with different summands, Congressus Numerantium 70 (1990), 207–215.

[6] Y.O. Hamidoune, The representation of some integers as a subset sum, Bull. London Math. Soc. 26 (1994), 557–563.

[7] V. Lev, On the extremal aspect of the Frobenius Problem, J. Combinatorial Theory, Series A 73 (1) (1996), 111–119.

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

[9] E. Lipkin, On representation of r-th powers by subset sums, Acta Arith. LII (1989), 353–365.

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

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