Problem 333

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$ ?

Source: erdosproblems.com/333

Number theory
Additive bases

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

The site labels the problem disproved, with a Lean qualifier (page last edited 2025-12-27): the negative answer follows from Theorem 2 of [ErNe77], which Erdős and Graham appear to have overlooked, and a separate direct construction has a Lean 4 proof. Both are accepted claims: Erdős and Newman 1977 on the curator's acceptance and the journal publication, and the Lean-backed construction, Barreto 2025, on formalized evidence.

Problem 333

Status

Proof claims

Discussion