Problem 806

Let $A\subseteq \{1,\ldots,n\}$ with $\lvert A\rvert \leq n^{1/2}$ . Must there exist some $B\subset\mathbb{Z}$ with $\lvert B\rvert=o(n^{1/2})$ such that $A\subseteq B+B$ ?

Source: erdosproblems.com/806

Additive combinatorics

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved; the site labels the problem PROVED. Theorem 1.4 of Alon, Bukh and Sudakov [ABS09] (Israel J. Math. 174 (2009) 285--301, refereed; result page) shows that a group of order $n$ containing a non-doubling set of size between $\sqrt n\log^2n$ and $\sqrt n\log^{10}n$ satisfies the "EN-condition": every $A\subseteq G$ with $|A|\le\sqrt n$ has a basis $B$ with $|B|\le50\sqrt n\log\log n/\log n$ . Cyclic groups qualify (Corollary 1.5(a), solvable groups; or since an interval is non-doubling), and the paper's reduction (p. 3) lifts a basis $B'\subseteq\mathbb Z/n\mathbb Z$ to $B=B'\cup(B'-n)\subset\mathbb Z$ at the cost of a factor $2$ , so every $A\subseteq\{1,\ldots,n\}$ with $|A|\le n^{1/2}$ lies in $B+B$ for some $B\subset\mathbb Z$ with $|B|\le100\,n^{1/2}\log\log n/\log n=o(n^{1/2})$ , for all sufficiently large $n$ . The order is sharp up to constants: Erdős and Newman [ErNe77] (J. Number Theory 9 (1977), refereed) state on p. 423 that most sets of type $(n,n^2)$ have $m_A>c\,n\log\log n/\log n$ , the site's lower bound, a remark they assert without proof and which [ABS09] (pp. 2--3) restates and carries to every finite group. The claim page is Alon, Bukh and Sudakov (accepted on the refereed publication and the site's credit).

ABS09: Alon, N., Bukh, B. and Sudakov, B., Discrete Kakeya-type problems and small bases. Israel J. Math. 174 (2009), no. 1, 285--301, DOI 10.1007/s11856-009-0115-9 (November 2009, as its Crossref record gives it); the edition read is the authors' version from Alon's publication list, https://web.math.princeton.edu/~nalon/PDFS/publications.html (12 pp., its own pagination; the journal text not compared; arXiv:0711.1604 is the preprint). The EN-condition, Theorem 1.4, Corollary 1.5 and the reduction to $\mathbb Z/n\mathbb Z$ , p. 3; Lemma 3.1 and the proof of Theorem 1.4, pp. 8--9. Library home: Alon, Bukh and Sudakov 2009.
ErNe77: Erdős, P. and Newman, D. J., Bases for sets of integers. J. Number Theory 9 (1977), no. 4, 420--425, DOI 10.1016/0022-314x(77)90003-8 (received 13 October 1976, as its Crossref record gives it); the edition read is the Rényi archive copy, https://users.renyi.hu/~p_erdos/1977-05.pdf, by printed page: Theorem 1, p. 420; Theorem 2, p. 422; the remark, p. 423; the question, p. 425. Library home: Erdős and Newman 1977 and its Erdős and Newman 1977, The closing question (p. 425) page.
KoLe92: Kozma, G. and Lev, A., Bases and decomposition numbers of finite groups. Arch. Math. (Basel) 58 (1992), 417--424 ([ABS09]'s [11]; the $2$ -universal sets of Theorem 1.1). Not held; it is cited only as a source of the $2$ -universal sets, the case $k=2$ that [ABS09]'s Theorem 1.2 generalizes.

Problem 806

Status

Proof claims

Discussion