The board / number theory / #333
Erdős Problem #333
DISPROVED LEANdatabase updated 2025-12-25
The statement as posed is false. A solution has also been checked by machine, in Lean.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Let \(A\subseteq \mathbb{N}\) be a set of density zero. Does there exist a \(B\) such that \(A\subseteq B+B\) and \[\lvert B\cap \{1,\ldots,N\}\rvert =o(N^{1/2})\] for all large \(N\)? The answer is no. Erdős and Newman [ErNe77] have proved this is true when \(A\) is the set of squares. In fact, Theorem 2 of [ErNe77] already implies a negative answer to this problem, but this seems to have been overlooked by Erdős and Graham. See also [806].
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved. The authoritative wording is on erdosproblems.com/333.Prizenone
Topicsnumber theory, additive basis
Statement in LeanFormal Conjectures
Solution in Leanyes
Original pageerdosproblems.com/333
Attempts
submit one →If you take a run at this one — with your own AI subscription or without — the guide says how, and the submission form gets you an honest read of what you found.