Problem 29

Is there an explicit construction of a set $A\subseteq \mathbb{N}$ such that $A+A=\mathbb{N}$ but $1_A\ast 1_A(n)=o(n^\epsilon)$ for every $\epsilon>0$ ?

Source: erdosproblems.com/29

Number theory
Additive bases

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

PROVED (LEAN), the site's label (page last edited 28 December 2025): Jain, Pham, Sawhney and Zakharov [JPSZ24] give an explicit set with $A+A=\mathbb{N}$ and $1_A\ast1_A(n)\le Cn^{c/\log\log n}$ , so the answer is yes; the site's Lean marker corresponds to the proof the formal-conjectures catalog links, a third party's Lean proof of a weaker existence statement (see Formalization). The claim page An explicit economical additive basis records the acceptance evidence: the refereed publication and the curator of erdosproblems.com, Thomas Bloom; the corpus has not built or audited the Lean proof.

Problem 29

Status

Proof claims

Discussion