Erdős #40 — sharp density threshold for Erdős–Turán

Statement

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)}\] implies $\limsup_{n\to\infty} 1_A\ast 1_A(n)=\infty$, where $1_A\ast 1_A(n) = \#\{(a,b)\in A^2 : a+b=n\}$? (erdosproblems.com/40)

Facts

- Prize $500; status open, explicitly "cannot be resolved with a finite computation" (erdosproblems.com/40) — it is a statement about an asymptotic threshold function, not a finite object. - Falsifiable: no. Answering "for which $g$" requires both (i) a proof that the implication holds for some explicit slowly-growing $g$, and (ii) either a proof it holds for *all* $g\to\infty$, or an explicit construction showing it fails for some $g$ — none of which is a finite check. - Origin: Erdős [Er95, "Some of my favourite problems..."], [Er97c, "Some of my favorite problems and results"]. - **This is a strictly stronger form of the Erdős–Turán conjecture Erdős #28 — additive basis forces unbounded representations**: taking $g(N)\to\infty$ arbitrarily slowly and noting $A+A\supseteq[N,\infty)$ (cofinite sumset) forces $|A\cap[1,N]|\gg\sqrt N$ (else $A+A$ misses an interval by pigeonhole — this exact reduction is formalized in Erdos40.erdos_40.variants.implies_erdos_28 in the DeepMind Lean file), a positive answer to #40 for *any* single $g\to\infty$ would immediately imply #28. So #40 is Erdős's own attempt to sharpen Erdős #28 — additive basis forces unbounded representations to a quantitative density statement. - Known results / best bounds on the *negative* (counterexample) side, i.e. ruling out $g$'s for which the implication is FALSE: - Erdős–Rényi 1960 ("Additive properties of random sequences of positive integers," Acta Arith. 6, 83–110, users.renyi.hu/~p_erdos/1960-02.pdf; cited verbatim on erdosproblems.com/39): for every $\epsilon>0$ there is a set $A$ with $|A\cap[1,N]|\gg_\epsilon N^{1/2-\epsilon}$ for all large $N$ and $1_A\ast1_A(n)\ll_\epsilon 1$ (bounded, hence $\limsup$ finite) for all $n$. Since $N^{1/2-\epsilon}=N^{1/2}/N^\epsilon$, this rules out every $g(N)=N^\epsilon$, $\epsilon>0$ fixed — the implication in #40 is false for any polynomially-growing $g$. - Pliego 2024 (arXiv:2405.04154, "On the Erdős-Turán Conjecture and the growth of $B_2[g]$ sequences"): for any $0<\epsilon<1$ and integer $g>1/\epsilon$, constructs a $B_2[g]$ sequence (representation function $\le g$ everywhere, so certainly $\limsup<\infty$) with $|A\cap[1,x]|\gg x^{g/(2g+1)}$ — a quantitative refinement (density exponent $\to 1/2$ as the allowed rep-count $g\to\infty$) that "improves upon earlier results of Cilleruelo and of Erdős and Rényi" per its own abstract. This sharpens the trade-off but is still a *fixed-power* result ($x^{1/2-\delta}$ for fixed small $\delta$ depending on the chosen $g$), not a sub-polynomial one. - Erdős (stated on erdosproblems.com/39): for every infinite Sidon set $A$, $\liminf_N |A\cap[1,N]|/N^{1/2}=0$ — so a *true* Sidon set (rep. function $\le 2$ pointwise, the $g\to 1$ extreme) can never stay at density $\gg N^{1/2}$ for all $N$; density must dip. This bounds how far the Erdős–Rényi-type construction can be pushed toward $g(N)\to1$ (constant). - Best known infinite Sidon set density: Ruzsa [Ru98], $\gg N^{\sqrt2-1+o(1)}$ ($\approx N^{0.4142}$), matched by Cilleruelo's explicit discrete-log construction — see Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set for the full derivation chain. This is the extreme "$g\equiv$const=1" end of the same trade-off spectrum as #40. - No source found (erdosproblems.com/40 remarks, the DeepMind Lean file, or the arXiv/OpenAlex searches performed) that resolves or narrows the case of sub-polynomial $g(N)\to\infty$ (e.g. $g(N)=\log N$, $\log\log N$, or any $g(N)=N^{o(1)}$) — this is exactly the gap left open, consistent with the site's "open" status and the Lean file's sorry. - Related problems: Erdős #28 — additive basis forces unbounded representations — the conjecture #40 sharpens; Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set? — "how large can $\limsup |A\cap[1,N]|/N^{1/2}$ be for a Sidon set" (same critical exponent $N^{1/2}$, complementary question: exact Sidon-density ceiling rather than the Erdős–Turán representation threshold); Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — best known infinite Sidon set growth rate ($N^{\sqrt2-1+o(1)}$, Ruzsa), the extremal "no-representation-growth-allowed" endpoint of #40's trade-off; 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) — generalization to two sequences $A,B$ with $a_n/b_n\to1$.

Literature state

Not resolved anywhere, and not merely "open" in the weak sense — the *shape* of the eventual answer is not even conjectured on erdosproblems.com, in the cited Erdős sources, or in any paper found. What the literature *does* establish, read directly: - The polynomial regime is fully settled in the negative: Erdős–Rényi (1960) already killed every $g(N)=N^\epsilon$, $\epsilon>0$ fixed, via an explicit bounded-representation-function construction of density $N^{1/2-\epsilon}$ (source: erdosproblems.com/39's remarks, cross-checked against the original 1960 Acta Arithmetica paper, PDF confirmed accessible at users.renyi.hu/~p_erdos/1960-02.pdf). - Pliego's 2024 paper (arXiv:2405.04154) is the most recent progress in this exact cluster; it sharpens the density-vs-boundedness trade-off ($x^{g/(2g+1)}$ for $B_2[g]$ sequences) and explicitly frames itself as improving "earlier results of Cilleruelo and of Erdős and Rényi" — i.e. the community is actively working the *quantitative* boundary right next to #40, but every published construction found is still a fixed power below $1/2$, never a slowly-diverging correction factor $g(N)\to\infty$. No paper claims a construction with density $\gg N^{1/2}/g(N)$ for $g(N)=o(N^\epsilon)$ (any $\epsilon$), which is the open sub-polynomial regime #40 is really asking about. - The DeepMind formal-conjectures Lean file (FormalConjectures/ErdosProblems/40.lean, fetched raw 2026-07-02) formalizes both the general statement Erdos40For (g) and the reduction to #28 (erdos_40.variants.implies_erdos_28, i.e. Erdős–Turán is a corollary via $g(N)=\sqrt N$... no — via any $g\to\infty$, tested with $g(N)=\sqrt N$ giving the density bound $\gg 1$, i.e. one needs only that $A+A$ cofinite $\Rightarrow |A\cap[1,N]|\gg1$, which the Lean proof derives from the sumset-covering pigeonhole argument). The main theorem erdos_40 itself is answer(sorry) with proof sorry — confirms no closed-form conjectured answer even exists in the formalization effort as of this fetch. - One AI attempt log exists (gpt-5.2, via the community "Erdosproblems-llm-hunter" tracker, mehmetmars7.github.io, fetched via its data/erdos_data.js): it independently re-derives (a) the trivial averaging/pigeonhole fact that density $\gg N^{1/2}h(N)$ for diverging $h$ trivially forces $\limsup=\infty$ (the *easy*, non-open direction, dense side of the threshold — not what #40 is asking), and (b) a weaker, self-constructed Sidon set of density $N^{1/3}$ ruling out only $g(N)\ge CN^{1/6}$ — strictly weaker than the site's own cited Erdős–Rényi fact ($g(N)=N^\epsilon$ for *any* $\epsilon>0$, i.e. rules out $g(N)\ge N^\epsilon$ for arbitrarily small fixed $\epsilon$). Logged as "unresolved" by the tracker itself; not used as a claim source above, only noted for completeness/precedent. - No forum comments on erdosproblems.com/40 (0 comments as of fetch) and no "problem-status" widget activity (status: "None" — no partial/claimed solutions logged by the community).

Attack surface

- Mode: derivation+formalization (explicitly not finite-search, per the site and the Lean sorry). - Concrete first experiment: (1) formalize/verify in Lean the Erdős–Rényi $N^{1/2-\epsilon}$ construction and Pliego's $B_2[g]$ trade-off (arXiv:2405.04154) as machine-checked floor facts — currently neither is formalized in the DeepMind repo for #40, only the trivial #28-implication direction is. (2) Numerically probe the sub-polynomial regime: take Pliego's or Cilleruelo's constructions and empirically measure, for slowly-growing rep-count caps $g = g(N)$ (e.g. $g(N)=\lceil\log N\rceil$, applied adaptively across dyadic blocks the way Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set's block-union constructions work), whether an explicit finite-truncation density near $N^{1/2}/\log N$ is achievable with representation function staying bounded on each truncation — this cannot prove the infinite statement but would be informative derivation fuel (does the trade-off degrade gracefully or hit a wall well before $g(N)\to\infty$ slowly?). - Oracle: for any finite truncation and explicit candidate set, "does $A\cap[1,N]$ have density $\ge cN^{1/2}/g(N)$ and representation function $\le r$ for all $n\le 2N$" is fully mechanical ($O(N\log N)$ sort-and-count), so empirical exponent/trade-off exploration is oracle-checkable end-to-end even though — like Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — it cannot settle the actual $\limsup_{N\to\infty}$ statement. - Feasibility: famous and hard as literally stated — it directly implies the 80+-year-old Erdős–Turán conjecture Erdős #28 — additive basis forces unbounded representations for the easiest case, so any full resolution (even just "true for all $g$") would be a major result. The realistic near-term contribution is not resolving #40 itself but (1) Lean-formalizing the known negative-direction (Erdős–Rényi, Pliego) results as reusable floor facts, mirroring what already exists for the adjacent Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set/Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets cluster, or (2) a targeted literature/derivation push specifically on the *sub-polynomial* $g(N)$ regime (log, iterated-log), which appears to be genuinely untouched — no paper found addresses it, polynomial-regime results (Erdős–Rényi, Pliego) don't degrade continuously into it, and this is the precise gap between "known false" (any $N^\epsilon$) and "known true only trivially" (density $\gg N^{1/2}h(N)$, $h\to\infty$, the wrong/easy side).

Related

- Erdős #28 — additive basis forces unbounded representations — the Erdős–Turán conjecture itself; #40 is its sharp quantitative/stronger form, and a positive answer to #40 for any single $g\to\infty$ implies #28 (proved in the DeepMind Lean file). - Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set? — "how large can $\limsup|A\cap[1,N]|/N^{1/2}$ be for a Sidon set?" — same critical exponent $N^{1/2}$; Erdős–Turán proved $\le1$, Krückeberg proved $\ge1/\sqrt2$ achievable, and Kolountzakis/Cilleruelo–Trujillo extended the achievability to $B_2[g]$ sequences for $g\ge2$ — directly informs which densities near $N^{1/2}$ are achievable with bounded (not just eventually-bounded) representation counts. - Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — best known infinite Sidon set density $N^{\sqrt2-1+o(1)}$ (Ruzsa); the $g\to$const=1 extreme endpoint of #40's density-vs-boundedness trade-off, and the source of the block-union / discrete-log construction techniques most likely to be adaptable to #40's sub-polynomial-$g$ regime. - 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$ cofinite $\Rightarrow\limsup 1_A*1_B(n)=\infty$?), same cluster, also open. - Additive representation function $r_{B,h}(n)$ — $1_A\ast1_A(n)$, the central object; the whole problem is about how its $\limsup$ behaves as a function of $A$'s density. - Sidon sets / B_2 sets / Golomb rulers — $B_2[1]$ sets, the extremal bounded-representation objects whose density ceiling ($\approx N^{1/2}$) is the exact threshold #40 asks about; shared with Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set, Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set?. - B_2[g] sequences — bounded (but not unique) representation, the Sidon relaxation — the bounded-but-not-1 generalization (Kolountzakis, Cilleruelo–Trujillo, Pliego arXiv:2405.04154) that provides the current-best negative-direction constructions for #40. - Erdős–Rényi random-subset-plus-deletion construction (power-law random sets for additive bases) — the 1960 probabilistic-deletion method (Acta Arith. 6, 83–110) that rules out every polynomial $g(N)=N^\epsilon$. - concept/additive-energy / Additive-energy / pigeonhole averaging identity — $\sum_n r_A(n)=|A|^2$ forces large representation values on the dense side — the trivial dense-side argument ($\sum_n r_{A_N}(n)=|A_N|^2$, forcing $\limsup=\infty$ once density $\gg N^{1/2}h(N)$, $h\to\infty$) that bounds the *easy* direction and clarifies exactly where #40's difficulty starts (density strictly below $N^{1/2}$, by any diverging factor). - Lean 4 formalization of constructions and conditional reductions (Erdős-problem context) — DeepMind formal-conjectures repo, FormalConjectures/ErdosProblems/40.lean, statement formalized (including the #28-implication direction, fully proved), main question answer(sorry).