REPRESENTATION OF ELEMENTS OF A SEQUENCE BY SUMSETS

VSEVOLOD F. LEV

Abstract. In this note the method of [5] and a result from [3] are combined to treat the following classical problem: given a finite set A and an infinite sequence S (both in ℤ), what is the minimal number of elements of A whose sum lies in S? We obtain an upper bound depending only on the densities of A and S (but not on their arithmetic nature).

1. Introduction

Let A be a set of co-prime positive integers, and let S be an increasing sequence of positive integers. For some special sequences S, like the sequence of powers of 2, the sequence of square-frees or the sequence of r-th powers, the following problem was studied by a number of authors (see, for instance, [1, 2, 5] and the references given there): Prove, that there is an element of S which can be represented by a sum of elements of A, and estimate the number of summands from A required for such a representation.

As to the case of general S of unknown arithmetic structure, [4, Theorem 1] immediately yields a result of the type discussed. Actually, in [4] we effectively calculate M_{A} and ν_{A}(s) > 0 such that each integer s > M_{A} can be represented by a sum of at most ν_{A}(s) elements of A.

Below, we obtain a sharper result assuming that S has bounded growth rate. More precisely, we need S to satisfy the following condition:

S has an element in each interval [N; 2N] for every positive integer N, (∗)

or at least the following weaker condition:

S has an element in each interval [N; 2N] for every positive integer N ≥ N_{0}, where N_{0} is a fixed positive integer.

(∗∗)

1991 Mathematics Subject Classification. 11B13, 11B75.

2 VSEVOLOD F. LEV

Condition (∗) covers such sequences as powers of 2 or prime numbers. Condition (∗∗) is introduced to include also the sequences which are asymptotically dense, but sparse at the beginning, like the sequence of r-th powers.

Let n = |A| ≥ 2 be the cardinality of A, and let l denote the maximal element of A. To characterize the density of A, define

κ = \begin{cases}1, & if l = n, \\ ⌈\frac{l−1}{n−1}⌉ − 1, & if l > n. \end{cases}

Our main result is the following.

Theorem 1.

i) Let S satisfy (∗). Then some element of S can be represented by a sum of at most 2κ elements of A.

ii) Let S satisfy (∗∗), and assume l ≥ N_{0}. Then some element of S can be represented by a sum of at most 2κ + 2 elements of A.

2. Auxiliary results and proof of Theorem 1

The following lemma is a generalization of [5, Lemma 1].

Lemma 1. Let S satisfy (∗∗) with some N_{0} ≥ 1, and let B ⊆ [0; L] be a set of integers (where L ∈ ℤ, L ≥ 0). Assume that |B| ≥ \frac{1}{2}L + \frac{1}{2}N_{0} + 1. Then some element of S can be represented by a sum of precisely two elements of B.

Proof. We use induction on L. The case L < N_{0} is actually impossible, since

\frac{1}{2}L + \frac{1}{2}N_{0} + 1 ≤ |B| ≤ L + 1.

If L = N_{0}, then B = {0, …, N_{0}}, and the result follows since S has an element in [N_{0}; 2N_{0}]. Now, suppose L ≥ N_{0} + 1 and find s ∈ S subject to L ≤ s ≤ 2L. Write

B′ = B ∩ [0; s − L − 1], B′′ = B ∩ [s − L; L].

If 2B is disjoint to S, then by the pigeonhole principle

2|B′′| ≤ 2L − s + 1,

and also by the induction hypothesis

2|B′| ≤ (s − L − 1) + N_{0} + 1

(this holds trivially if s = L). Summing up, we obtain

2|B| ≤ L + N_{0} + 1,

a contradiction. □

REPRESENTATION OF ELEMENTS OF A SEQUENCE BY SUMSETS 3

Define A′ = {0} ∪ A, and let hA′ stand for the set of all h-fold sums of elements of A′:

hA′ = {a_{1} + ⋯ + a_{h} | a_{1}, …, a_{h} ∈ A′} (h ≥ 1).

The following estimates are special cases of [3, Corollary 1]:

|κA′| ≥ \frac{1}{2}κ(κ + 1)(n − 1) + κ + 1,  (1)
|(κ + 1)A′| ≥ \frac{1}{2}κ(κ + 1)(n − 1) + l + κ + 1.  (2)

(generally, the corollary we are referring to asserts that if A′ ⊆ [0; l] is a set of n + 1 coprime integers satisfying 0, l ∈ A′, gcd(A) = 1, then for h ≥ 1

|hA′| ≥ \begin{cases}B_{h}(n), & if h ≤ κ, \\ B_{κ}(n) + (h − κ)l, & if h ≥ κ, \end{cases}

where κ is defined as above and B_{h}(n) = \frac{1}{2}h(h + 1)(n − 1) + h + 1 ).

We can now prove Theorem 1.

Proof of Theorem 1.

i) Let B = κA′ ⊆ [0; L], where L = κl. Then by (1)

|B| ≥ \frac{1}{2}κ((κ + 1)(n − 1) + 1) + \frac{1}{2}κ + 1 ≥ \frac{1}{2}κl + \frac{3}{2} = \frac{1}{2}L + \frac{3}{2},

hence Lemma 1 (with N_{0} = 1) shows that some element of S is a sum of two elements of B and therefore a sum of 2κ elements of A′.

ii) Let B = (κ + 1)A′ ⊆ [0; L], where L = (κ + 1)l. Then by (2)

|B| >\frac{1}{2}κ((κ + 1)(n − 1) + 1) + l + 1 ≥
\frac{1}{2}κl + \frac{1}{2}l + \frac{1}{2}N_{0} + 1 = \frac{1}{2}L + \frac{1}{2}N_{0} + 1,

thus we can apply Lemma 1 and the proof can be completed as above. □

Remark 1. As it is easily seen from the proof, Theorem 1 ii) may be slightly strengthened for very sparse A. Namely, if S satisfies (∗∗) and κ ≥ N_{0}, then already 2κ elements of A suffices to represent an element of S by their sum.

Remark 2. Condition (∗) may be written in another and more customary form. Let S = {s_{i}}_{i=1}^{∞}. Then (∗) means that s_{1} ≤ 2 and s_{i+1} ≤ 2s_{i} + 2 for i = 1, 2, . . .. Condition (∗∗) also may be rewritten in a similar way.

References

[1] N. Alon, Subset Sums, J. Number Theory 27 (1987), 196–205.

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

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

[4] , Optimal representations by sumsets and subset sums, J. Number Theory, to appear.

[5] , Representing powers of 2 by a sum of four integers, Combinatorica 16 (2) (1996), 1–4.

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

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