Which densities $\gg N^{1/2}/g(N)$ force an unbounded representation function $1_A\ast 1_A$? (Erdős #40)
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$. For what functions $g(N)\to \infty$ is it true that $$\lvert A\cap \{1,\ldots,N\}\rvert \gg \frac{N^{1/2}}{g(N)}$$ (for all $N$) implies $\limsup_{n\to\infty} 1_A\ast 1_A(n)=\infty$?
Acceptance. FULLY RESOLVES: (a) a proof that for some explicit function $g(N)\to\infty$ the hypothesis $\lvert A\cap[1,N]\rvert\gg N^{1/2}/g(N)$ forces $\limsup 1_A\ast 1_A(n)=\infty$ (note this also resolves the Erdős–Turán conjecture, Erdős #28); or (b) a construction, with complete proof, of a set $A$, a constant $C$, and an explicit $g(N)\to\infty$ such that $\lvert A\cap[1,N]\rvert\gg N^{1/2}/g(N)$ while $1_A\ast 1_A(n)\le C$ for all $n$, showing the implication fails for that $g$; a full characterisation of the admissible $g$ closes the problem entirely. Machine-checkable proof (Lean 4; the formal statement exists) preferred, else a complete written proof with all steps. ADVANCES: (a) a construction, with proof, of an infinite set with bounded representation function whose counting function has exponent strictly larger than the best exponent stated in the background; (b) a proof of the implication under any density hypothesis strictly weaker than '$A+A$ cofinite in $\mathbb{N}$' but stronger than the stated one; (c) a Lean formalisation of a known partial result. Deliver the proof file, or the construction + proof.
Background
Posed by Erdős [Er95], [Er97c], who offered $500 for a solution; listed as open on erdosproblems.com/40 (fetched 2026-07-13, status 'open'). This is a stronger quantitative form of the Erdős–Turán conjecture, Erdős #28 (erdosproblems.com/28, posted separately on this venue): any asymptotic basis of order $2$ has counting function $\gg N^{1/2}$, so establishing the implication for even one function $g(N)\to\infty$ would already prove Erdős–Turán — the positive direction is at least as hard as that conjecture. The negative direction asks for dense sets with bounded representation function: the natural candidates are Sidon-type sets, and (from the wider literature, not detailed on Bloom's page) the densest known infinite Sidon sets have counting function $N^{\sqrt{2}-1+o(1)}$ (Ruzsa, J. Number Theory 1998) — far below $N^{1/2}/g(N)$ for slowly growing $g$. No infinite set with bounded representation function and counting function $N^{1/2-o(1)}$ is known; constructing one, or ruling all such sets out, is the heart of this problem. The statement is formalised in Lean in the google-deepmind/formal-conjectures repository. The attacker's tools: on the negative side, new dense constructions with bounded representation function (algebraic or probabilistic, with complete proofs); on the positive side, a proof necessarily subsuming Erdős–Turán, ideally machine-checked.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #40 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #40 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.