×

Representing powers of 2 by a sum of four integers. (English) Zbl 0862.11008

Let \(n\) be a positive integer. Let \({\mathcal A} = \{1,2, \dots, n\}\), and let \({\mathcal B}\) be a subset of \({\mathcal A}\) with \(|B |> n/3\). P. Erdös [Ann. N. Y. Acad. Sci. 576, 132-145 (1989; Zbl 0790.11015)] conjectured that there exists a power of 2 which can be represented by a sum of elements of \({\mathcal B}\). This conjecture was proved by P. Erdös and G. Freiman [J. Number Theory 34, No. 1, 1-12 (1990; Zbl 0697.10047)]. Further let \(M({\mathcal B})\) denote the minimal number of elements of \({\mathcal B}\), whose sum equals a power of 2. In this paper the author proves that \(M({\mathcal B}) \leq 4\). This is the best upper bound for \(M({\mathcal B})\), because N. Alon [J. Number Theory 27, 196-205 (1987; Zbl 0622.10042)] showed that if \(n=3 k+1\), \(3k- 2=2^s\), and \({\mathcal B} = \{3,6, \dots, 3k\} \cup \{3k +1\}\), where \(k\) and \(s\) are positive integers with \(k\geq 4\), then \(M({\mathcal B}) >3\).

MSC:

11B13 Additive bases, including sumsets
11B75 Other combinatorial number theory
11B05 Density, gaps, topology
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Alon: Subset sums,J. Number Theory,27 (1987), 196-205. · Zbl 0622.10042 · doi:10.1016/0022-314X(87)90061-8
[2] P. Erd?s: Some problems and results on combinatorial number theory,Ann. New York Acad. Sc.,576 (1989), 132-145. · Zbl 0790.11015 · doi:10.1111/j.1749-6632.1989.tb16392.x
[3] P. Erd?s andG. Freiman: On two additive problems,J. Number Theory,34 (1990), 1-12 · Zbl 0697.10047 · doi:10.1016/0022-314X(90)90047-U
[4] G. A. Freiman: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] G. A. Freiman: Sumsets and powers of 2, in:Colloq. Math. Soc. J?nos Bolyai,60 (1992) (North-Holland, Amsterdam).
[6] M. Nathanson andA. S?rk?zy: Sumsets containing long arithmetic progressions and powers of 2,Acta Arith.,54 (1989), 147-154. · Zbl 0693.10040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.