OP-00947 Open

Small sets whose sumset contains the first n squares

Let $A$ be a set of integers such that $A + A$ contains the first $n$ squares $1^2, 2^2, \dots, n^2$. Erdős and Newman showed that necessarily $|A| \ge n^{2/3 - o(1)}$, and that for every $C$ there are such $A$ with $|A| \ll_C n / \log^C n$.

Problem. Is $|A| \ge n^{1 - o(1)}$?

Source: P. Erdős and D. J. Newman, Bases for sets of integers, J. Number Theory 9 (1977). Listed as Problem 61 in B. Green, 100 open problems (version of January 2026).

Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.

Classification

Primary: NT — Number Theory
Secondary: CO
Keywords: additive bases, Erdős problems, squares, sumsets
Literature checked: Oct. 26, 2026 by clemens-admin

References

@article{erdos1977newman,
  author = {Erd{\H o}s, P. and Newman, D. J.},
  title = {Bases for sets of integers},
  journal = {Journal of Number Theory},
  volume = {9},
  number = {4},
  pages = {420--425},
  year = {1977},
  doi = {10.1016/0022-314X(77)90003-8}
}

@article{alon2009kakeya,
  author = {Alon, Noga and Bukh, Boris and Sudakov, Benny},
  title = {Discrete {K}akeya-type problems and small bases},
  journal = {Israel Journal of Mathematics},
  volume = {174},
  pages = {285--301},
  year = {2009},
  doi = {10.1007/s11856-009-0115-9},
  eprint = {0711.1604},
  archivePrefix = {arXiv}
}

@misc{green100open,
  author = {Green, Ben},
  title = {100 open problems},
  howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
  note = {Problem 61; version of January 2026, most recent update December 2025},
  year = {2026}
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00947, "Small sets whose sumset contains the first n squares", clopen.solutions.