A set with bounded representation function whose sumset has lower density 1−ε: does it exist? (Erdős #749)
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$. Let $\epsilon>0$. Does there exist $A\subseteq\mathbb{N}$ such that the lower density of $A+A$ is at least $1-\epsilon$ and yet $1_A\ast 1_A(n)\ll_\epsilon 1$ for all $n$ (i.e. the representation function is bounded by a constant depending only on $\epsilon$)?
Acceptance. FULLY RESOLVES: (i) for every $\epsilon>0$ an explicitly described set $A_\epsilon\subseteq\mathbb{N}$ (decidable membership rule) together with a complete proof that $\liminf_{N\to\infty}\lvert(A_\epsilon+A_\epsilon)\cap[1,N]\rvert/N\geq 1-\epsilon$ and $\sup_n 1_{A_\epsilon}\ast 1_{A_\epsilon}(n)\leq C(\epsilon)<\infty$; OR (ii) a proof that for some $\epsilon>0$ no such set exists — i.e. every $A$ with a bounded representation function has lower density of $A+A$ below $1-\epsilon$. Machine-checkable proof (Lean 4, building on the formalised statement) preferred, else a complete written proof; no finite computation can close either direction. ADVANCES: (a) a construction with proof achieving lower density of $A+A$ at least $1-\epsilon$ with representation function bounded by a stated slowly growing function (e.g. $O(\log\log n)$) — a quantitative interpolation toward the full question; (b) a proof of the negative direction under an additional, clearly stated structural hypothesis on $A$; (c) a machine-checked formalisation of Bhalla's upper-density construction; (d) a proven quantitative trade-off between the bound $\sup_n 1_A\ast 1_A(n)\leq C$ and the achievable lower density of $A+A$. Deliver the construction plus proof file, or the proof file.
Background
Asked by Erdős [Er94b, p.263]; listed as open on erdosproblems.com/749 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics'). Bloom notes it is unclear from [Er94b] whether Erdős expected a yes or a no. Erdős recorded that he and Sárközy believed bounded representation functions should force the sumset away from full density — that if $1_A\ast 1_A(n)\leq C$ for all $n$ then the UPPER density of $A+A$ is at most $1-\epsilon_C$ for some $\epsilon_C>0$ depending on $C$. That belief has now been refuted for upper density: Bhalla's construction (2026, manuscript linked from the problem page, written with the assistance of GPT 5.4) produces, for each $\epsilon>0$, a set $A$ whose sumset $A+A$ has upper density at least $1-\epsilon$ even though the representation function stays $\ll\epsilon^{-1}$ at every $n$. The stated problem — the same question for LOWER density — remains open and is strictly harder: the construction must keep the sumset dense at every scale, not just along a subsequence of scales. The question is a near neighbour of the Erdős–Turán conjecture, Erdős #28 (erdosproblems.com/28), that an order-2 additive basis must have unbounded representation function; a yes here would exhibit a strong 'near-basis with bounded multiplicity' phenomenon just short of contradicting it. The statement is formalised in Lean in google-deepmind/formal-conjectures. The attacker's tool: adapt Bhalla's blockwise construction to control all scales simultaneously — proof-shaped work; computational experiments with blockwise/random constructions can guide parameter choices but cannot close the problem.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #749 (T. F. Bloom) | website |
| REF-02 | Bhalla — resolution of the upper-density variant of Erdős #749 (manuscript, with GPT 5.4 assistance) | paper |
| REF-03 | Lean formalisation of Erdős #749 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.