Erdős #28 — additive basis forces unbounded representations

Statement

If $A\subseteq \mathbb{N}$ is such that $A+A$ contains all but finitely many integers, then $$\limsup_{n\to\infty} 1_A\ast 1_A(n) = \infty,$$ where $1_A\ast 1_A(n) = \#\{(a,a')\in A\times A : a+a'=n\}$ is the (ordered) representation function. Informally: no additive basis of order 2 can have a uniformly bounded number of representations for all large $n$.

Facts

- Prize \$500; status open, erdosproblems.com/28 marks it "cannot be resolved with a finite computation" (site-owner belief) — the claim is a limsup over an infinite set, so no finite $A$ or finite check can settle it either way. - Falsifiable: no by finite means — refuting it needs an actual *infinite* set $A$ with $A+A$ cofinite and $1_A\ast1_A$ bounded on all of $\mathbb N$, itself an infinite verification. - Origin: Conjectured by Erdős and Turán in [ErTu41] (Erdős, Turán, "On a problem of Sidon in additive number theory, and on some related problems," J. London Math. Soc. 16 (1941), 212–216), restated by Erdős across [Er56] [Er57] [Er59] [Er61] [Er65] [Er65b] [Er69] [Er70c] [Er73] [Er77c] [Er80,p.98] [ErGr80] [Er81] [Er85c] [Er89d] [Er90] [Er94b] [Er95] [Er97c] [Er97f] [Va99,1.16]. Discussed as problem C9 in Guy's collection [Gu04]. - Stronger conjectures on record (erdosproblems.com/28 remarks, BorisAlexeev/Thomas Bloom forum thread): (i) $\limsup r_A(n)/\log n > 0$; (ii) the weaker hypothesis $\lvert A\cap[1,N]\rvert \gg N^{1/2}$ for all large $N$ already suffices to force $\limsup r_A(n)=\infty$. - Existence side (how thin can a basis be) — fully settled, and it doesn't resolve the conjecture: - Erdős 1956 [Er56]: constructed a basis $B$ of order 2 with $c_1\log n \le r_B(n)\le c_2\log n$ — best-possible density, motivating conjecture (i) above (Wikipedia, Erdős–Tetali theorem page). - Erdős–Tetali theorem (1990, Random Structures & Algorithms 1(3):245–261): extends Erdős's $h=2$ construction to every order $h\ge2$ — a random set $\omega$ with $\Pr(n\in\omega)=C n^{1/h-1}(\log n)^{1/h}$, concentrated via Janson's inequality / Vu's polynomial-concentration bound, gives $r_{\omega,h}(n)\asymp\log n$ almost surely. This is an *existence* result showing $\log n$ is achievable and optimal — it is evidence *for* the spirit of conjecture (i), not a proof of #28. - Kolountzakis 1995: a computable (polynomial-time recursive) version of the $h=2$ economical basis exists; the $h\ge3$ computable case is open. - Táfula 2019 (arXiv:1807.10200): characterizes exactly which growth rates $f$ (beyond $\log n$) are achievable as $r_{B,h}(n)\asymp f(n)$ for some basis $B$. - Direct partial progress on the $L^\infty$ statement of #28 itself (still far from "unbounded"): - Dirac's theorem (predecessor): the representation function of a basis cannot be eventually constant. - Borwein, Choi, Chu, "An old conjecture of Erdős–Turán on additive bases," Math. Comp. 75 (2006), no. 253, 475–484: proved that for every additive basis $A$ of order 2, $1_A\ast1_A(n)$ must eventually exceed 7 — a genuine (if numerically small) unconditional lower bound on the max representation count, directly on the original conjecture. See Borwein–Choi–Chu (2006) — the representation function of any order-2 additive basis cannot be bounded by 7 for the full computer-assisted-finite-search technique. - Konstantoulas, "Lower bounds for a conjecture of Erdős and Turán," Acta Arith. 159 (2013), 301–313 (eudml.org/doc/279150): if the *upper density* of $\mathbb N\setminus(A+A)$ is $<1/10$ (a near-cofinite, not literally cofinite, hypothesis), then $1_A\ast1_A(n) > 5$ for infinitely many $n$. This is the closest published quantitative result to #28's actual hypothesis. - Ruzsa (1990), Monatsh. Math. 109, 145–151: constructed a genuine basis $A$ (so $A+A$ has density 1 both ways) with representation function bounded *in square mean*: $\sum_{n\le N}(1_A\ast1_A(n))^2 = O(N)$. Flagged and then explicitly retracted as only weak evidence in the April 2026 forum thread on #749 (an $L^2$ bound says nothing about the $L^\infty$/limsup question #28 asks). - Group-theoretic analog is fully RESOLVED, and goes the opposite way: Konyagin, Lev, "The Erdos-Turan problem in infinite groups," arXiv:0901.1649 — for an infinite abelian group $G$ with $|2G|=|G|$, a *perfect* additive basis (unique representation, $r(n)=1$ for all $n$) exists unless $G$ is the direct sum of an exponent-3 group and the order-2 group, in which case $r(n)\le2$ is achievable. I.e. $\mathbb N$'s specific Archimedean/order structure (not just "infinite abelian group") is what makes #28 hard — most infinite abelian groups have NO Erdős–Turán obstruction at all. - Finite (periodic) analog is fully quantified and under active 2023–2026 research ("Ruzsa's number" $R_m$: least $r$ such that $\exists A\subseteq\mathbb Z_m$ with $1\le\sigma_A(n)\le r$ for all $n\in\mathbb Z_m$): Chen (2008) $R_m\le288$ → Ding, Zhao, arXiv:2307.12311 (2023, journal 2024) $R_m\le192$ → Ding, Li, Li, Niu, Zhao, arXiv:2606.11069 (Jun 2026) $|R_{m+1}-R_m|\le144$ plus exact table of $R_m$ for all $m\le100$ (finding exceptions, e.g. $R_{37}=4,R_{39}=5$, to the Ding–Zhao monotonic-step conjecture); lower bound $R_m\ge6$ for $m\ge36$ (Sándor, Yang, arXiv:1705.03316). This shows any *finite-length* approximation to the problem has a small bounded answer — the true obstruction in #28 is specifically about the infinite/cofinite/asymptotic regime, not finiteness per se. - Live 2026 development (directly on the closest known relative of #28): Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open asks whether $\forall\varepsilon>0\ \exists A$ with lower density of $A+A\ge1-\varepsilon$ yet $1_A\ast1_A(n)\ll_\varepsilon1$. Terence Tao (erdosproblems.com/28 forum, 5 Apr 2026) noted a counterexample to #28 would yield such an $A$ for every $\varepsilon$ — so #749's lower-density case is a genuine stepping-stone toward #28. The upper-density variant of #749 was resolved 4 Apr 2026 by Aron Bhalla (assisted by "GPT 5.4 Thinking") via a finite-field parabola/Sidon-block construction (inspiration credited to a Liang–Zhang–Zuo construction) glued across lacunary scales in Ruzsa's 1990 style; verified independently by Nat Sothanaphan. The harder lower-density case (the one actually adjacent to #28) remains open; Tao reduced it to an explicit, still-unsolved "$K$-scale toy problem" requiring bounded-multiplicity sumset-covering blocks at nearby scales with constants *uniform in $K$* — active as of 6 Jun 2026 with continued Tao/Bhalla+GPT-5.4/Sothanaphan iteration. - Related problems: Erdős #40 — sharp density threshold for Erdős–Turán, Erdős #1145 — two-set a_n/b_n→1 additive-basis generalization is OPEN; its own necessity clause is settled by Erdős #331 (Ruzsa's digit-parity construction, DISPROVED), Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open.

Literature state

Not resolved — genuinely open since 1941 (85 years), confirmed across erdosproblems.com, Wikipedia's dedicated "Erdős–Turán conjecture on additive bases" page, and the live 2026 forum activity: "There are no solutions, partial or complete, claimed in the comments" on erdosproblems.com/28 itself.

The problem sits inside a well-developed but non-closing landscape: 1. Existence-of-thin-bases direction is settled (Erdős 1956 for $h=2$; Erdős–Tetali 1990 for all $h$; extended by Táfula 2019, arXiv:1807.10200) — probabilistic-method proofs that $\log n$-representation bases exist and are optimal. This confirms the *plausibility* of the stronger $\limsup r(n)/\log n>0$ conjecture but is orthogonal to proving #28 itself (existence of a good basis says nothing about the impossibility of a *bounded*-representation one). 2. Direct unconditional partial bounds toward #28's own statement exist but are numerically tiny: Dirac (not eventually constant) → Borwein–Choi–Chu 2006 (must eventually exceed 7) → Konstantoulas 2013 (near-cofinite ⟹ $r(n)>5$ infinitely often, for upper density of complement $<1/10$). None of these techniques scale to "unbounded" — they are all finite pigeonhole/counting arguments capped at small constants, and don't obviously generalize to the true cofinite hypothesis of #28. 3. The exact analog is resolved in the opposite direction for most infinite abelian groups (Konyagin–Lev, arXiv:0901.1649): perfect ($r\equiv1$) bases exist generically, so whatever forces #28's phenomenon in $\mathbb N$ must be genuinely arithmetic/Archimedean, not group-theoretic in general — a real structural clue about where a proof would have to bite. 4. The finite/periodic analog ($\mathbb Z_m$, Ruzsa's number $R_m$) is fully quantitative and the subject of active, recent (2023, 2024, Jun 2026) improvement (Chen 2008 → 288; Ding–Zhao 2023/24 → 192; Ding et al. Jun 2026, arXiv:2606.11069, exact tables to $m\le100$) — every finite truncation admits a small bounded-representation basis, isolating the difficulty of #28 to the passage $m\to\infty$/cofiniteness. 5. **The most current, mathematically live thread is on the logically adjacent Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open, playing out on erdosproblems.com's own forum from April through June 2026 with Terence Tao, Thomas Bloom (site owner), Aron Bhalla and Nat Sothanaphan as active participants, and "GPT 5.4 Thinking" as a credited co-investigator (assisting Bhalla's construction, and independently proposing — and having retracted — an over-claimed relevance of Ruzsa's 1990 $L^2$ result). Bhalla+GPT-5.4 fully resolved #749's upper-density case (arbitrarily-high upper density with bounded multiplicity, for every $\varepsilon$) on 4 Apr 2026; the lower-density** case, one step short of #28, is open and actively being decomposed by Tao into finite "$K$-scale" sub-problems as of the most recent (6 Jun 2026) forum comment. 6. Tao also proved (forum, 5 Apr 2026, via a direct Cauchy–Schwarz counting argument) that the *difference-set* analog (bounding $1_A\ast1_{-A}$ away from the origin while $A+A$ has large lower density) is false — establishing a genuine asymmetry between sumset and difference-set representation functions that rules out naive symmetric (e.g. plain Sidon-type) constructions as a route to disproving #28 or #749. 7. No AI system is credited with resolving #28 or its harder (lower-density) #749 relative; "GPT 5.4 Thinking" is a credited assistant on the one adjacent sub-result that *has* been resolved (#749 upper-density, Bhalla, Apr 2026), and remains an active collaborator on the still-open next step.

Attack surface

- Mode: literature-resolution + derivation (not finite-search — #28 is an unfalsifiable-by-computation limsup statement; the one concrete finite sub-experiment available is a construction/search task, not a check of #28 itself). - Concrete first experiment: implement Terence Tao's "$K$-scale toy problem" (posed live on erdosproblems.com/749, 6 Apr–6 Jun 2026, still unsolved): for scales $M_1<\dots<M_K$ (e.g. $M_k=M_1(\log\log M_1)^k$), search — via finite-field parabola/Sidon-block constructions (à la Bhalla/Ruzsa 1990, citing inspiration from a Liang–Zhang–Zuo construction) plus randomized/greedy or SAT/ILP search — for sets $P_k\subset[1,M_k]$ with $P_k+P_k$ covering a constant fraction of $[1,M_k]$ with bounded multiplicity, and $1_{P_k}\ast1_{P_{k'}}\ll1$ across all $k<k'\le K$, with implied constants independent of $K$. This is exactly the flagged bottleneck to #749's lower-density case, itself one step short of #28. - Oracle: mechanical for the sub-experiment — coverage fraction and boundedness of $1_{P_k}\ast1_{P_{k'}}$ on a finite range are directly computable (Bhalla's own verification used a "standard check" tool, cross-confirmed by Nat Sothanaphan on the forum); no oracle exists for #28 itself (unfalsifiable by finite means). - Feasibility: honest read — famous (85-year-old) and hard for #28 itself. Every direct partial-progress technique in the literature (Dirac, Borwein–Choi–Chu, Konstantoulas) caps out at small finite constants and does not scale toward "unbounded." The realistic, currently-live contribution is on the strictly-easier, concretely-scoped, still-open #749 lower-density sub-problem, where a small but active human+AI team (Tao, Bhalla+GPT-5.4, Sothanaphan, Bloom) is iterating on finite-field/Cartesian-product gluing constructions as of June 2026 — genuinely promising for derivation-style contribution, but solving it would resolve Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open, not #28 itself (a counterexample to #28 implies #749's lower-density statement, not conversely).

Related

- Borwein–Choi–Chu (2006) — the representation function of any order-2 additive basis cannot be bounded by 7 — the 2006 finite-search-tree proof that $\sup r_A(n)\ge8$ for every basis, the strongest unconditional partial-progress bound on #28's own $L^\infty$ statement. - Erdős #40 — sharp density threshold for Erdős–Turán — weaker hypothesis version: for which $g(N)\to\infty$ does $\lvert A\cap[1,N]\rvert\gg N^{1/2}/g(N)$ already force $\limsup r_A(n)=\infty$? Also open. - Erdős #1145 — two-set a_n/b_n→1 additive-basis generalization is OPEN; its own necessity clause is settled by Erdős #331 (Ruzsa's digit-parity construction, DISPROVED) — two-sequence generalization: $A=\{a_n\},B=\{b_n\}$ with $a_n/b_n\to1$, does $A+B$ cofinite force $\limsup 1_A\ast1_B(n)=\infty$? Also open (Va99, 1.17). - Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open — the closest known stepping-stone: density-relaxed version of #28. Upper-density case resolved (Bhalla + GPT-5.4 Thinking, Apr 2026, finite-field/lacunary-gluing construction); lower-density case (logically closer to #28: a counterexample to #28 implies it) is open and the current live research frontier (Tao's "$K$-scale toy problem," through Jun 2026). - Additive representation function $r_{B,h}(n)$ — $r_{B,h}(n)$, the central object across this whole family of problems. - Random-set construction + Janson's inequality / Vu concentration (the Poisson paradigm) — random-set + Janson's inequality / Vu concentration technique proving existence of $\log n$-economical bases for every order $h$. - Finite-field parabola/Sidon-block construction with lacunary-scale gluing — the Bhalla/Ruzsa/Liang–Zhang–Zuo technique: build $B\subset\mathbb F_p^2$ as a union of parabolas so $B+B$ covers most of the plane with bounded multiplicity and bounded line-intersections; base-$p$ lift to $[1,M]$; glue across lacunary scales via random translates (Ruzsa 1990's method) — the live construction toolkit for #749/#28-adjacent work. - Ruzsa's number $R_m$ on $\\mathbb Z_m$ — the finite/periodic analogue of the Erdős–Turán additive-basis problem — $R_m$, the finite-cyclic-group ($\mathbb Z_m$) analog of #28; fully quantitative, actively improved 2008→2024→2026 (Chen; Ding–Zhao; Ding–Li–Li–Niu–Zhao). - Erdős–Fuchs theorem: average representation count can't be too close to linear — related but logically distinct 1956 result: the *average* (not max) representation count $\sum_{n\le x}r(n)$ can't be too close to linear ($Cx+o(x^{1/4}\log^{-1/2}x)$ is impossible); a companion "no basis is too regular" statement. - Perfect additive basis / unique representation basis ($r_A\\equiv1$) — $r(n)\equiv1$; provably EXISTS for most infinite abelian groups (Konyagin–Lev) but is exactly the kind of object #28 conjectures is impossible (in the bounded, not just unique, sense) over $\mathbb N$.