Representing powers of 2 by a sum of four integers

Vsevolod F. Lev

Abstract We solve an arithmetic problem due to Erdős and Freud (1986) investigated also by Freiman, Nathanson and Sárközy: How many elements from a given set of integers one must take to represent a power of 2 by their sum?

1 Introduction

For natural n, let B ⊆ [1; n] be a set of integers. If B = {3, 6, …, 3⌊n/3⌋} then obviously neither power of 2 is represented by a sum of elements of B. In [2] P. Erdős and R. Freud conjectured, that for |B| > ⌊n/3⌋ such a power of 2 must exist. This was proved by P. Erdős and G. Freiman in [3] (and even for a sum of distinct elements of B). However, their proof is valid only for sufficiently large n and requires as much as c log n summands (c > 0 is an absolute constant). In [6], M.B. Nathanson and A. Sárközy proved this for a fixed number of summands (3504 ones to be exact) and also for sufficiently large n. Next, in [5] G. Freiman proved the result for 6 summands. However, the question about the minimal number of elements of B whoes sum equals to a power of 2, remained opened.

As shows the example (due to N. Alon) of

B = {3, 6, …, 3k} ∪ {3k + 1},

where k ≥ 4 is chosen under 3k − 2 = 2^{s}, three elements of B are insufficient: here powers of 2 up to 2^{s} obviously are not represented by any sum of three or less elements of B, and the same applies to the powers of 2 starting from 2^{s+2} since 2^{s+2} = 4(3k − 2) > 3(3k + 1). Also 2^{s+1} is not represented by such a sum in view of

2^{s+1} ≡ 2 ≢ ν(3k + 1) (mod 3), ν = 0, 1, 3

and 2^{s+1} = 2(3k − 2) < 2(3k + 1). In the same way, one can easily construct B with up to \frac{5}{12}(n − 1) elements, sum of each three (or less) of which is not a power of 2.

On the other hand, we prove below that one can always guarantee the existence of at most four elements of B with the required property:

Theorem 1 Let B ⊆ [1; n], and assume |B| > n/3. Then there exist at most four elements of B whose sum is a power of 2. □

This theorem will be proved in the next section. Its proof is based on the following lemma, which seems to be of independent interest:

Lemma 1 Let A ⊆ [0; n], and assume |A| ≥ \frac{1}{2}n + 1. Then either A contains a power of 2, or there exist two distinct elements of A whose sum is a power of 2. □

The lemma also will be proved in the next section. Note its similarity (only an external one, however) with the well-known fact, stated below:

Proposition 1 (Erdős) Let A ⊆ [1; n], and assume |A| ≥ \frac{1}{2}n + 1. Then there exist two distinct elements of A whoes quotient is a power of 2. □

The two analogical problems concerning representation of powers of 2 by products and differences appear to be trivial.

As to representations of powers of 2 by a sum of distinct elements of A, the example like above shows that one must require at least 5 summands. On the other hand, as observed N. Alon, using the theorem of Szemerédy (as in [1]) and the method of this paper one can show that 6 or less distinct elments of A whose sum is a power of 2 always exist, provided n is sufficiently large.

2 The proofs

Proof of Lemma 1. Use induction on n. For n = 1, 2, 3 the lemma is easily verified. Suppose n ≥ 4, and let

n = 2^{s} + r, 0 ≤ r ≤ 2^{s} − 1.

We assume, that 2^{s} ∉ A, and of the two numbers 2^{s} − t, 2^{s} + t (1 ≤ t ≤ r) at least one does not belong to A (else we would have 2^{s+1} ∈ 2A). Thus, writing

A′ = A ∩ [0; 2^{s} − r − 1], A′′ = A ∩ [2^{s} − r; 2^{s} + r]

we obtain

|A′′| ≤ r, |A′| ≥ |A| − r.

On the other hand, by the induction hypothesis

|A′| < \frac{1}{2}(2^{s} − r − 1) + 1

(if A′ is empty, this holds trivially). Therefore,

|A| − r ≤ |A′| < \frac{1}{2}(2^{s} − r − 1) + 1,

and

|A| < \frac{1}{2}(2^{s} + r − 1) + 1 = \frac{1}{2}n + \frac{1}{2}, −

a contradiction. □ Proof of Theorem 1. Clearly, we may assume gcd(B) = 1: we have gcd(B) ≤ 2 by |B| > n/3, and in the case of gcd(B) = 2 just divide all the elements of B by 2. Also, without loss of generality we assume n ∈ B. Put A = {0} ∪ B. Then |A| > n/3 + 1, gcd(A) = 1, the largest element of A is n, and thus by a well-known theorem of Freiman (see [4])

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

Hence, |2A| ≥ n + 1 since |A| + n > n, 3|A| − 3 > n.

Therefore, 2A ∈ [0; 2n] and |2A| ≥ n + 1. By Lemma 1, there exists a power of 2 represented by a sum of at most two elements of 2A, and that sum is obviously equal to a sum of at most four elements of B. □

References

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

[2] Erdős P.: Some problems and results on combinatorial number theory, Ann. New York Acad. Sc., 576(1989), 132–145.

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

[4] Freiman G.A.: Foundation of a structural theory of set addition (Kazan, 1966) [Russian], or: Translation of Math. Monographs, 37 (American Math. Soc., Providence, R.I., 1973).

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

[6] Nathanson M. and Sárközy A.: Sumsets containing long arithmetic progressions and powers of 2, Acta Arith., 54(1989), 147–154.

Vsevolod F. Lev

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

seva@math.tau.ac.il