Logo
All Random Solved Random Open
SOLVED
What is the size of the largest $A\subseteq \{1,\ldots,N\}$ such that, for all $\emptyset\neq S\subseteq A$, $\sum_{n\in S}n$ is not a square?
Erdős observed that $\lvert A\rvert \gg N^{1/3}$ is possible, taking the first $\approx N^{1/3}$ multiples of some prime $p\approx N^{2/3}$.

Essentially solved by Nguyen and Vu [NgVu10], who proved that $\lvert A\rvert\ll N^{1/3}(\log N)^{O(1)}$.

See also [438].

This question was asked by Erdős to a young Terence Tao in 1985. We thank Tao for sharing this memory and a letter of Erdős describing the problem.

Additional thanks to: Terence Tao