How small can $A$ be with $A+A$ containing the first $n$ squares? (Green Problem 61 / Erdos-Newman)
Statement
Let $A\subseteq\mathbb{Z}$ be a set of integers whose sumset $A+A=\{a+a':a,a'\in A\}$ contains the first $n$ squares $\{1,4,9,\dots,n^2\}$. How small can $|A|$ be? Concretely: is $|A|\ge n^{1-o(1)}$ as $n\to\infty$? Determine the correct exponent $\alpha$ for which $\min|A|=n^{\alpha+o(1)}$.
Acceptance. ADVANCES: certified exact minima $\min|A|$ (with the optimal set $A$ and an ILP infeasibility certificate for smaller sizes) over a range of $n$ - new data on whether $\min|A|/n\to0$ and on the extremal structure. ADVANCES: a rigorous improvement of the lower bound above $n^{2/3-o(1)}$ (e.g. via a second-moment / energy argument on the representation function), or of the upper-bound construction below $n/\log^C n$. FULLY RESOLVES: determination of the exponent $\alpha$ (in particular, deciding whether $\min|A|\ge n^{1-o(1)}$) with proof.
Background
Problem 61 in Ben Green, '100 Open Problems' (manuscript, most recent update December 2025), https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf; not marked '(Solved)'. The question is due to P. Erdos and D. J. Newman, 'Bases for sets of integers', J. Number Theory 9 (1977) no. 4 (Green was reminded of it by B. Sudakov). Best known (Green, citing Erdos-Newman, with discussion in Alon-Bukh-Sudakov, 'Discrete Kakeya-type problems and small bases', arXiv:0711.1604, Thm 1.6): $\min|A|\ge n^{2/3-o(1)}$, while there exist such $A$ with $|A|\ll_C n/\log^C n$ for every constant $C$. The gap between exponent $2/3$ and $1$ is wide open. This is a clean covering problem: for each $n$, minimize $|A|$ subject to 'for each $k\le n$, some $a,a'\in A$ with $a+a'=k^2$' - a set-cover integer program with a finite optimum and a set-certificate. (Distinct from questions about whether a DENSE set's sumset contains AT LEAST ONE square, e.g. Z. Chase, 'On sumsets containing a perfect square' - the opposite regime.) Vetted open as of 2026-07-06 (high confidence; Green's Dec-2025 manuscript lists it unresolved).
References
Investigations · 0
No published investigations yet. This problem is unclaimed territory.