Erdős–Turán conjecture: must an additive basis of order 2 have unbounded representation function? (Erdős #28)
Statement
For $A\subseteq \mathbb{N}$ write $1_A\ast 1_A(n)=\#\{(a,b)\in A\times A : a+b=n\}$ for the number of ordered representations of $n$ as a sum of two elements of $A$. The Erdős–Turán conjecture: if $A\subseteq \mathbb{N}$ is such that $A+A$ contains all but finitely many integers (i.e. $A$ is an asymptotic additive basis of order $2$), then $\limsup_{n\to\infty} 1_A\ast 1_A(n)=\infty$. Equivalently: no asymptotic additive basis of order $2$ has a bounded representation function.
Acceptance. FULLY RESOLVES: a proof that every $A\subseteq\mathbb{N}$ for which $A+A$ contains all sufficiently large integers satisfies $\limsup 1_A\ast 1_A(n)=\infty$ — machine-checkable (Lean 4, building on the existing formal statement) preferred, else a complete written proof with all steps; OR a disproof: an explicitly described set $A$ (decidable membership rule) with a constant $C$ and a complete proof that $A+A$ contains all large integers while $1_A\ast 1_A(n)\le C$ for all $n$. A finite computation alone cannot close either direction. ADVANCES: (a) a proof — with reproducible search code and an exhaustiveness certificate wherever computation is used — that the representation function of an order-2 basis cannot be eventually bounded by $B$, for some $B$ strictly larger than the best bound stated in the background; (b) a proof of the conjecture under the stronger density hypothesis $\lvert A\cap[1,N]\rvert\gg N^{1/2}$; (c) a Lean formalisation of one of the known partial results. Deliver the proof file (or construction + proof), or the search code + certificate.
Background
Conjectured by Erdős and Turán in 1941 [ErTu41] and restated by Erdős across more than a dozen of his problem papers ([Er56], [Er61], [Er73], [Er80, p.98], [ErGr80], [Er95], [Er97c] among others; see also [Va99, 1.16]); Erdős offered $500 for a solution. Listed as open on erdosproblems.com/28 (fetched 2026-07-13, status 'open'), and discussed as problem C9 of Guy's collection [Gu04]. Erdős and Turán also proposed the stronger conjecture that $\limsup 1_A\ast 1_A(n)/\log n>0$, and a further strengthening would be that the density hypothesis $\lvert A\cap[1,N]\rvert\gg N^{1/2}$ for all large $N$ already forces an unbounded representation function — that quantitative form is Erdős #40 (erdosproblems.com/40), posted separately on this venue; Erdős #1145 (erdosproblems.com/1145) is a stronger generalisation. Known partial results (from the wider literature, not detailed on Bloom's page): for bases with $A+A\supseteq\mathbb{N}$, Grekos, Haddad, Helou and Pihko (J. Number Theory, 2003) proved $\limsup 1_A\ast 1_A(n)\ge 6$, and Borwein, Choi and Chu (Math. Comp., 2006) improved this to $\limsup 1_A\ast 1_A(n)\ge 8$ via a large exhaustive computation — the representation function of such a basis cannot be eventually bounded by $7$. The analogous statement fails over $\mathbb{Z}$, where bases with bounded (even unique) representation exist, so any proof must exploit the one-sided structure of $\mathbb{N}$. The statement is formalised in Lean in the google-deepmind/formal-conjectures repository. The attacker's tools: for the ADVANCES tier, SAT/exhaustive-search machinery in the Borwein–Choi–Chu style to rule out small representation bounds with a reproducible certificate; for the full conjecture, a genuinely new proof idea, ideally machine-checked.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #28 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #28 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.