Erdős #66 — additive basis with $r_A(n)/\\log n \\to c\\neq 0$

Statement

Is there $A\subseteq \mathbb{N}$ such that \[\lim_{n\to \infty}\frac{1_A\ast 1_A(n)}{\log n}\] exists and is $\neq 0$?

Here $1_A\ast 1_A(n) = r_A(n) := \#\{(a,a')\in A\times A : a+a'=n\}$ is the (additive) representation function of $A$ with itself. The question asks whether a set can be found whose representation function grows *exactly* like $c\log n$ for a genuine nonzero constant $c$, with a limit that actually exists (not just bounded liminf/limsup).

Facts

- Prize \$500; status open, falsifiability not-finite — erdosproblems.com explicitly states "This is open, and cannot be resolved with a finite computation" (erdosproblems.com/66, directly fetched, reflects site-owner T.F. Bloom's belief). - Origin: Erdős raised this repeatedly across [Er56], [Er59], [Er80,p.98], [ErGr80], [Er85c], [Er89d], [Er90], [Er95], [Er97c], [Er97f], [Va99,1.16] (bib details fetched from erdosproblems.com/bibs/*). Erdős believed the answer should be no; in [Er80] he explicitly asked the sub-question of whether such a set exists with limit exactly $1$, and did not believe one exists. - A random construction achieves this up to a density-zero exceptional set: "a suitably constructed random set has this property if we are allowed to ignore an exceptional set of density zero. The challenge is obtaining this with no exceptional set" (erdosproblems.com/66, remarks). This is the standard random-greedy $B_2$-type construction giving $r_A(n)\asymp \log n$ almost everywhere; the open difficulty is uniformity for *all* large $n$. - Erdős suggested the possibly-true stronger statement that $\liminf$ and $\limsup$ of $r_A(n)/\log n$ are always separated by an absolute constant (i.e. the limit essentially can never exist and be nonzero) — erdosproblems.com/66 remarks. - Best known partial result (impossibility direction): Erdős and Sárközy proved \[\frac{\lvert r_A(n)-\log n\rvert}{\sqrt{\log n}}\to 0\] is impossible for any $A$ (erdosproblems.com/66, citing the Erdős–Sárközy line of work; likely A. Sárközy, "On a theorem of Erdős and Fuchs," Acta Arith. 37 (1980), 333–338, an explicit Erdős–Fuchs-type refinement — paper itself not independently read, flagged as inferred attribution). - Sharpened by Horváth (2007): G. Horváth, "An improvement of a theorem of Erdős and Sárközy," Pollack Periodica (2007), 155–161 (erdosproblems.com/bibs/Ho07), proves \[\lvert r_A(n)-\log n\rvert \leq (1-\epsilon)\sqrt{\log n}\] cannot hold for all large $n$, for any fixed $\epsilon>0$ — a quantitative strengthening of Erdős–Sárközy's vanishing-error statement to a fixed-fraction-of-$\sqrt{\log n}$ error. - Neither result rules out the log n problem's actual question (a genuine limit $c\log n + o(\log n)$, i.e. error $o(\log n)$, which is a much weaker regularity demand than $o(\sqrt{\log n})$) — there remains a real gap between what's proved impossible ($O(\sqrt{\log n})$-close) and what the problem asks about ($O(\log n)$-close, i.e. a true limit of the ratio). This gap is the crux of why the problem is still open. - Related problems: Erdős #28 — additive basis forces unbounded representations, 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) (see Related).

Literature state

Not resolved anywhere found. Direct fetch of erdosproblems.com/66 confirms status OPEN with "There are no solutions, partial or complete, claimed in the comments," last edited 06 April 2026.

This is the natural sharpening (a literal-limit form) of the much more famous Erdős–Turán conjecture on additive bases Erdős #28 — additive basis forces unbounded representations (erdosproblems.com/28, directly fetched): if $A+A$ covers all but finitely many integers then $\limsup r_A(n)=\infty$. That page's own remarks state Erdős and Turán "also suggest the stronger conjecture that $\limsup r_A(n)/\log n > 0$" — problem #66 asks for something adjacent-but-different (existence of an actual finite nonzero *limit*, not just a $\limsup$ bound away from 0), and per the erdosproblems.com/66 remarks Erdős actually believed this specific literal-limit version should have a negative answer, i.e. is the opposite direction from #28. Problems #28, #40 (erdosproblems.com/40, quantitative Erdős–Turán via density threshold $N^{1/2}/g(N)$) and #1145 (erdosproblems.com/1145, two-sequence $A,B$ with $a_n/b_n\to1$ generalization) share almost the identical Erdős-reference list as #66 ([Er56],[Er59],[Er80],[ErGr80],[Er85c],[Er89d],[Er90],[Er95],[Er97c],[Er97f],[Va99]), confirming they come from the same cluster of Erdős survey passages on additive-basis representation-function regularity.

The technical ancestor machinery for all impossibility results in this cluster is the Erdős–Fuchs theorem (Erdős, P.; Fuchs, W.H.J., J. London Math. Soc. 1956; en.wikipedia.org/wiki/Erdős–Fuchs_theorem, fetched directly): for the *accumulated* representation function $s_{A,2}(x)=\sum_{n\le x} r_A(n)$, no $A\subseteq\mathbb N$ satisfies $s_{A,2}(x) = cx + o(x^{1/4}(\log x)^{-1/2})$ for any $c>0$ — the sharp exponent/log-power form is due to Montgomery & Vaughan, "On the Erdős–Fuchs theorem," in *A Tribute to Paul Erdős* (1990) (cited on the same Wikipedia page). The proof is a generating-function/Parseval (complex-analytic $L^2$-on-the-unit-circle) argument: writing $f(z)=\sum_{a\in A}z^a$, the assumption forces $|f(z)|^2$ too close to a fixed singular kernel near $z=1$, and Parseval on $|z|=r\to1^-$ produces a contradiction. This exact technique family is still active and extendable: arXiv:1911.12313 (Cambie/Cilleruelo-type authors, "An Erdős–Fuchs Theorem for Ordered Representation Functions," 2019, published *Ramanujan J.* 2020) extends it to ordered/weighted representation counts $r_k^{\le},r_k^{<}$; arXiv:1608.08433 ("On the Erdős-Fuchs theorem," 2016) gives several further extensions; arXiv:2009.03392 ("Additive representation functions and discrete convolutions," 2020) proves Erdős–Fuchs-type theorems for general principal terms $\sum b_k b_{n-k}$ (not just linear $cx$), which is structurally the closest published machine to what a direct attack on #66 would need (replacing the linear kernel with a $c\log n$-type kernel).

A parallel, distinct technique line is the Sárközy–Sós block/difference-regularity approach: Erdős, Sárközy and Sós showed that if the number of maximal blocks of consecutive integers in $A$ up to $N$, $B(A,N)$, satisfies $B(A,N)/\sqrt N \to \infty$, then the $\ell$-th finite difference $\Delta_\ell(r_A(n))$ cannot be bounded, for any fixed $\ell\ge1$ (per arXiv:1804.07560 abstract, fetched, which extends this further); a related "question of Sárközy and Sós on representation functions" is treated in arXiv:1108.5832. This is a combinatorial (block-counting) rather than complex-analytic technique, orthogonal to Erdős–Fuchs.

AI literature-search attempt

the teorth/erdosproblems GitHub wiki's "AI contributions to Erdős problems" page (raw.githubusercontent.com/wiki/teorth/erdosproblems/AI-contributions-to-Erdős-problems.md, fetched directly) logs GPT-5 running a literature search on problem #66 on 13 Oct 2025, outcome "🟡 Partial results found" — in the "Secondary contributions / Literature search" table, not the "Full/partial solution" table, i.e. it did not claim any new mathematical progress, only found what's already documented above (almost certainly the Horváth 2007 paper). No AI system is logged as having produced a proof, partial proof, or formalization attempt for #66 specifically.

A targeted search for very recent (2023–2026) work specifically on "$r_A(n)/\log n$ limit" or "$1_A*1_A(n)$ vs $\log n$" additive-basis papers turned up nothing beyond the above — the problem appears genuinely dormant in the primary literature since Horváth (2007), aside from the adjacent-but-different Sárközy–Sós block-regularity line continuing to be extended (1804.07560, 2020; 1108.5832).

Attack surface

- Mode: derivation+formalization (primary — the problem is explicitly not finite-checkable) + literature-resolution (secondary — the Erdős–Fuchs-type machine is still actively being generalized, e.g. 2020's "general principal term" version, and might already almost reach the $c\log n$ kernel with direct adaptation). - Concrete first experiment: (1) Read arXiv:2009.03392 in full (its abstract already targets general principal terms $\sum_{k=0}^n b_k b_{n-k}$ rather than only linear $cn$) and check whether setting $b_k$ so that $\sum_{k\le n} b_k b_{n-k} \sim c\log n$ (e.g. $b_k \sim c'/\sqrt{k}\,$ or a similarly tuned density) falls inside its hypothesis class ($\limsup b_n <1$) — if so, its theorem may directly imply an Erdős–Fuchs-type obstruction for the *accumulated* sum analogue of #66, which would need translating from accumulated-sum form back to the pointwise-ratio form asked in #66 (nontrivial but mechanical Abel-summation-style step). (2) In parallel, numerically construct candidate sets $A$ (random greedy $B_2$-style, or the "ignore density-zero exceptional set" construction erdosproblems.com/66 already describes) up to $N\sim 10^7$–$10^8$ and empirically plot $r_A(n)/\log n$ to see how close to a constant limit one can numerically get and where/how it must break down — not a proof, but useful to sharpen intuition about whether Erdős's "liminf/limsup separated by an absolute constant" belief (erdosproblems.com/66 remarks) is numerically visible already at moderate $N$. - Oracle: none mechanical for a full proof (not finite-checkable, per erdosproblems.com). For the numerical-exploration sub-task, an oracle exists only for a *counterexample to Erdős's belief* (a construction where $r_A(n)/\log n$ visibly stabilizes to a constant over a huge, expanding range with shrinking wobble) — this would be suggestive but never dispositive, since the problem is about an actual $n\to\infty$ limit. - Feasibility: honest read — this is a genuinely hard, 40–70-year-old open problem in classical additive number theory (Erdős posed variants of it from 1956 through the 1990s) with almost no independent chipping since Horváth (2007), i.e. essentially dormant for ~19 years prior to this review. Full resolution is out of reach for us. The one concretely promising, bounded-scope sub-target is reading arXiv:2009.03392's "general principal term" Erdős–Fuchs theorem closely to see if it (or a straightforward adaptation of its proof) already closes some of the gap between the proved $O(\sqrt{\log n})$-regularity obstruction and the $O(\log n)$-regularity the problem actually asks about — this is a real, scoped, citable derivation attempt rather than blue-sky work, since the machinery and the target kernel ($c\log n$) are both already in the literature, just not yet connected.

Related

- Erdős #28 — additive basis forces unbounded representations — Erdős–Turán conjecture on additive bases ($A+A\supseteq\mathbb N$ eventually $\Rightarrow \limsup r_A(n)=\infty$); its own remarks state Erdős–Turán "also suggest the stronger conjecture that $\limsup r_A(n)/\log n>0$," the direct qualitative ancestor of #66's literal-limit question; shares nearly the identical Erdős bibliography with #66. - Erdős #40 — sharp density threshold for Erdős–Turán — quantitative form of Erdős–Turán via density threshold $\lvert A\cap[1,N]\rvert \gg N^{1/2}/g(N)$; same \$500 prize, same "additive basis" tag cluster. - 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,B$ with $a_n/b_n\to1$, $A+B\supseteq\mathbb N$ eventually $\Rightarrow \limsup r_{A,B}(n)=\infty$), the Erdős–Sárközy conjectured strengthening found via the same reference network. - Erdős–Fuchs theorem: average representation count can't be too close to linear — the founding generating-function/Parseval technique for proving representation functions can't be too regular; direct ancestor of the Erdős–Sárközy and Horváth partial results on #66, and still actively generalized (2016, 2019, 2020 extensions). - concept/erdos-turan-conjecture-additive-bases — the parent open conjecture; #66 is a strictly stronger, "literal limit exists" refinement in the same direction Erdős–Turán themselves flagged as a natural sharpening. - concept/sarkozy-sos-block-difference-regularity — the orthogonal, combinatorial (block-counting / finite-difference $\Delta_\ell$) technique line for representation-function regularity, still being extended (2018, 2020 papers). - concept/random-greedy-additive-basis-construction — the construction achieving $r_A(n)\asymp\log n$ off a density-zero exceptional set, per erdosproblems.com/66's own remarks; the "easy direction" whose obstruction (removing the exceptional set) is the actual open problem.

PRIOR-ART SCAN (2026-07-03)

Verdict: ACTIVELY-WORKED (still genuinely OPEN — not resolved anywhere — but this corrects/supersedes the "dormant since Horváth 2007" characterization in the Literature-state section above; there is real, recent, directly-relevant work).

Sources actually fetched/read this pass

- curl -sS -L erdosproblems.com/66 (HTTP 200, re-verified): status still OPEN, remarks unchanged, "last edited 06 April 2026." - curl -sS -L erdosproblems.com/forum/discuss/66 (HTTP 200, full comment thread read) — this was not checked in the prior pass and contains the key new finding (below). - raw.githubusercontent.com/google-deepmind/formal-conjectures/main/FormalConjectures/ErdosProblems/66.lean (fetched directly, full 43-line file read) — per the #64 lesson, checked the linked GitHub repo end-to-end: it contains only a theorem erdos_66 : answer(sorry) ↔ ... := by sorry stub (statement formalized, zero proof content, TODO(firsching) comment). No branches/other files for #66 in that repo beyond this stub. - arxiv.org/abs/2405.01530 — Christian Táfula, "Representation functions with prescribed rates of growth" (submitted 2 May 2024, v2 9 Aug 2025, v3 4 May 2026 — i.e. revised 2 months before today). Full 28-page PDF read in full (not just abstract). - api.semanticscholar.org graph API for arXiv:2405.01530 — 3 citing papers, all 2024–2026, all in the same "prescribed representation function" subfield (arXiv:2605.04411 "Thin subbases of Piatetski-Shapiro sequences" 2026; arXiv:2501.08371 "Waring and Waring-Goldbach subbases with prescribed representation function" 2025; arXiv:2410.11832 "On Vu's theorem in Waring's problem for thinner sequences" 2024). - raw.githubusercontent.com/wiki/teorth/erdosproblems/AI-contributions-to-Erdős-problems.md (re-fetched) — confirms the table entry for #66 is unchanged since the prior pass: only "GPT-5 | 13 Oct 2025 | 🟡 Partial results found," no new AI attempt logged since. - export.arxiv.org API, two searches over math.NT for "representation function" + additive (2023–2026 window) — no other directly relevant hits beyond the Táfula cluster above.

Key new finding — a live forum comment not yet folded into the official remarks

On erdosproblems.com/forum/discuss/66, user FlaredRain posted (15:51, 28 May 2026, i.e. ~5 weeks before today) flagging Táfula's arXiv:2405.01530 as directly relevant to #66. Unlike the earlier Horváth comment on the same thread (which carries a "(The site has been updated to address this comment.)" annotation and is reflected in the page's official Facts/remarks), the Táfula comment carries no such annotation — it has not yet been incorporated into erdosproblems.com's own remarks, which is why the prior wiki-page pass (reading only the rendered remarks, not the raw forum thread) missed it.

What Táfula's paper actually proves, and why it does NOT resolve #66

- Thm 1.1 (asymptotic existence): for any regularly-varying $F$ with $F(n)/\log n\to\infty$, a set $A$ exists with $r_{A,h}(n)\sim F(n)$. This covers growth *strictly faster* than $\log n$ — it does not touch the $c\log n$ boundary #66 asks about. - Thms 1.3/1.4 (order-of-magnitude, $\asymp$ not $\sim$): extend existence down to $F(n)\asymp\log n$, but only up to order of magnitude, not a genuine limit — again not #66's question. - Thm 1.5 / Section 6 (the directly relevant part): for the specific near-critical random-greedy construction with $\Pr(n\in A)=\min\{c(n\log n)^{1/h}/n,1\}$ tuned so $\mathbb E(r_{A,h}(n))\sim(1-\varepsilon)\log n$ (i.e. targeting a constant $c=1-\varepsilon<1$), Táfula *rigorously proves* $r_{A,h}(n)=0$ infinitely often, almost surely. This is a genuine theorem, but only about one specific probabilistic ensemble, not a universal statement over all $A\subseteq\mathbb N$. - This motivates a new, explicitly stated open Conjecture 1.6 in the paper: "If $r_{A,h}(n)>0$ for all large $n$, then $\limsup_n r_{A,h}(n)/\log n \geq 1$" — a strengthening of Erdős's own 1956 conjecture [Er56, p.132] (the qualitative ancestor also cited on erdosproblems.com/66's own remarks page). Even if Conjecture 1.6 were proved, it would only rule out constants $0<c<1$ for a genuine limit — it says nothing about $c\geq 1$, and Erdős's own explicit sub-question in [Er80] was specifically about the limit equaling exactly $1$. So a full proof of Conjecture 1.6 would *narrow* #66 but not resolve it. - Táfula's paper explicitly frames this as continuing Erdős–Tetali (1990) and Vu (2000)'s existence-construction line, not the Erdős–Sárközy/Horváth impossibility line already documented in this file's Facts section — it is a genuinely separate, still-active branch of attack.

Why the verdict is ACTIVELY-WORKED, not FRESH-AND-TRACTABLE or dormant HARD-OPEN

a professional number theorist (Táfula, USP, acknowledging Andrew Granville) has an actively-revised paper (2024→2025→2026, latest revision 5 weeks before today) whose explicit stated target is exactly the $\log n$ boundary #66 lives on, has generated a new open conjecture in the process, and has 3 independent 2024–2026 follow-on citations in the same narrow subfield. On erdosproblems.com itself, two users (Mahmudsudo, quintessen) self-tag as "Currently working on this problem" and a third (Dogmachine) flags it "looks difficult." This is a small but real, live, technically sophisticated research cluster — not a good target for us to claim fresh/tractable ground on; any attack surface here competes directly with an active specialist and requires the same heavy Kim–Vu/Vu-concentration probabilistic machinery Táfula's paper is built on. The problem itself remains fully open and is not close to resolution.

No claim of resolution, partial or complete, was found anywhere (erdosproblems.com comments, the Lean formalization repo, or the citing-paper cluster).