Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets

Statement

Let $f(N)$ be the maximum size of $A\subseteq\{1,\ldots,N\}$ such that the sums $a+b+c$ with $a,b,c\in A$ are all distinct (aside from the trivial coincidences from reordering) — i.e. $A$ is a $B_3[1]$ set. Is it true that \[f(N)\sim N^{1/3}?\] (erdosproblems.com/241)

Facts

- Prize \$100; status open, and erdosproblems.com states explicitly "this is open, and cannot be resolved with a finite computation" (site-owner belief). - Falsifiable: no in the finite-counterexample sense — this is an asymptotic-equivalence claim ($f(N)\sim N^{1/3}$, i.e. the ratio $\to1$); a disproof needs a proof that $\limsup N^{-1/3}f(N) > 1$, not one bad $N$. - Origin: originally asked to Erdős by Bose; restated by Erdős across [Er61][Er69][Er70b][Er70c][Er73][Er77c][Er80,p.99][ErGr80]; discussed as Problem C11 in Guy's *Unsolved Problems in Number Theory* [Gu04]. - Known results / best bounds (verified directly from primary sources): - Lower bound (matches the leading exponent, not the constant $1$ is only asymptotic in a weak sense — see below): Bose & Chowla [BoCh62], *Theorems in the additive theory of numbers*, Comment. Math. Helv. 37 (1962), 141–147, DOI 10.1007/BF02566968 (https://link.springer.com/article/10.1007/BF02566968) — an explicit finite-field construction giving $(1+o(1))N^{1/3}\leq f(N)$. - Upper bound (current record, unchanged since 2001): Green [Gr01], *The number of squares and $B_h[g]$ sets*, Acta Arith. 100(4) (2001), 365–390 (PDF read directly: https://people.maths.ox.ac.uk/greenbj/papers/number-of-squares-and-Bh%5Bg%5D.pdf) — proves $A(3,1,N)\leq(7/2)^{1/3}N^{1/3}(1+o(1))\approx1.5199\,N^{1/3}(1+o(1))$, via a Fourier-analytic lower bound on the additive energy $M(f)=\sum_{a+b=c+d}f(a)f(b)f(c)f(d)$ over normalized weight functions $f:\{1,\ldots,N\}\to\mathbb R$. The same paper gets $A(4,1,N)\leq7^{1/4}N^{1/4}(1+o(1))$ for the 4-fold analogue. - Error-term refinement, not the constant (2021): Johnston, Tait, Timmons, *Upper and lower bounds on the size of $B_k[g]$ sets*, arXiv:2105.03706 — for $g=1$ this matches Green's leading-order upper-bound constant but with an improved error term, and gives a matching lower bound (Lindström's construction, via a result of Caicedo, Gómez, Trujillo) with one hypothesis removed. Does not move the constant $(7/2)^{1/3}$. - Not applicable here: Timmons, *Upper bounds for $B_h[g]$-sets with small $h$*, arXiv:1604.00661 (2016) proves $A(3,g,N)\leq(14.3gN)^{1/3}$ for $g\geq2$, improving Cilleruelo–Ruzsa–Trujillo's $(16gN)^{1/3}$ — but for $g=1$ this constant ($14.3^{1/3}\approx2.43$) is far weaker than Green's $1.5199$, so it does not touch our exact problem. - The more general Bose–Chowla conjecture (any $r$-fold sum, $|A|\sim N^{1/r}$) is resolved only for $r=2$ — the classical Sidon-set problem, Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — and even there only the leading order is settled (Singer 1938 + Erdős–Turán 1941), while the error term is itself a separate open Erdős problem. - OEIS A387704 (Sharvil Kesarwani, https://oeis.org/A387704), "Size of the maximal subset $S$ of $\{1,\ldots,n\}$ such that for all $a,b,c\in S$, $a+b+c$ is unique up to permutation," tabulates $f(N)$ exactly for $N=0..150$ and links directly to this Erdős-problems page. Purely computational data — consistent with the "cannot be resolved with a finite computation" framing, since no finite table of exact values proves the asymptotic ratio $\to1$. - Related problems: Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — the $r=2$ (ordinary Sidon set) sibling problem, same Bose–Chowla/Erdős–Turán-era family, structurally identical "algebraic construction vs. counting/Fourier upper bound" game. erdos/840 — quasi-Sidon sets, a further relaxation in the same family.

Literature state

Not resolved anywhere. Every primary source checked (erdosproblems.com/241 itself, Green's paper read directly, and every citing/related arXiv paper found via search) confirms the gap between the Bose–Chowla lower-bound constant ($1$) and Green's upper-bound constant ($(7/2)^{1/3}\approx1.5199$) has been unchanged since 2001 (24+ years) for the exact $g=1$ case this problem asks about. The only post-2001 movement found is (a) an improved *error term* at the same leading constant [Johnston–Tait–Timmons 2021, arXiv:2105.03706], and (b) improved bounds for the *different* $g\geq2$ variant [Timmons 2016, arXiv:1604.00661], neither of which narrows the actual open gap. No paper found claims either a construction beating $N^{1/3}$'s constant $1$, or an upper-bound argument beating $(7/2)^{1/3}$.

By contrast, the closely related $r=2$ Sidon-set problem (Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets) *did* see an active 2021–2025 AI/computer-assisted episode: Balogh–Füredi–Roy (arXiv:2103.15850), O'Bryant (arXiv:2207.07800), Carter–Hunter–O'Bryant (arXiv:2310.20032), and an informal AlphaEvolve-assisted further improvement documented by Terence Tao (https://terrytao.wordpress.com/2025/11/05/mathematical-exploration-and-discovery-at-scale/) — but all of that machinery operates on the $h=2$ *error term* (the $N^{1/4}$-order correction to an already-settled $N^{1/2}$ leading term), a fundamentally different regime from #241, where even the *leading-order constant* is unresolved. No analogous numerical-optimization pipeline or AI-assisted attempt was found anywhere in the literature for the $h=3$ leading-constant gap. This is a genuine, unaddressed opportunity: Green's proof reduces to an explicit (if more complex, 3-fold) Fourier/large-spectrum optimization, structurally the same *kind* of finite-parameter inequality-chasing that the $h=2$ community has been actively computer/AI-optimizing since 2021 — but nobody has yet run that playbook on Green's 2001 argument.

Attack surface

- Mode: derivation (literature search found no resolution; the live opportunity is either sharpening Green's Fourier argument or improving the Bose–Chowla construction). - Concrete first experiment: reproduce Green's $M(f)$-minimization proof (Section 2–3 of arXiv-unlisted PDF at people.maths.ox.ac.uk/greenbj/papers/number-of-squares-and-Bh%5Bg%5D.pdf) as an explicit finite-parameter inequality (it already reduces to bounding a large-spectrum/Cauchy–Schwarz chain with a handful of free real parameters), then run the same style of computer-assisted / evolutionary numerical optimization over those parameters that Carter–Hunter–O'Bryant and (informally) AlphaEvolve ran on the analogous $h=2$ piecewise-affine landscape (per Tao's blog post on Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets) — a direct transplant of a technique proven to move a sibling problem's constant, never yet attempted here. - Oracle: mechanical for the sub-task — any claimed tighter upper-bound constant $c<(7/2)^{1/3}$ reduces to checking a finite chain of explicit real-parameter inequalities (as in Green's proof structure); any claimed better lower-bound construction is checked by brute-force verifying no repeated triple-sum on finite $A\subset\{1,\ldots,N\}$ and confirming the asymptotic density formula. Not mechanical for the full conjecture — no finite oracle settles $f(N)\sim N^{1/3}$ itself, only a genuine proof does. - Feasibility: the exponent $1/3$ is not in question (both bounds agree on it) — only the constant is open, structurally analogous to #30's error-term gap but arguably more exposed: unlike #30, no one has published a numerically-optimized or AI-assisted attempt at Green's constant since 2001, despite the adjacent $h=2$ problem having exactly that kind of active, citable, ongoing effort. A realistic near-term contribution is reproducing/optimizing Green's inequality chain numerically (the AlphaEvolve-style sub-task, directly transplantable from #30's playbook) to see whether $(7/2)^{1/3}$ can be shaved — this would be a genuine, citable record improvement even though it would not resolve the conjecture (believed answer is the constant $1$, i.e. matching Bose–Chowla exactly). Full resolution is famous-and-hard: a top mathematician's (Green) 2001 argument stands unimproved for 24+ years despite an active surrounding $B_h[g]$ literature.

Related

- Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — the $r=2$ (Sidon set) sibling problem: same Bose–Chowla/Erdős–Turán-era origin, same construction-vs-Fourier/counting bound-tightening game, but there the *leading order* is settled (Singer 1938 + Erdős–Turán 1941) and only the error term is open, whereas here even the leading constant is open. Also carries the AlphaEvolve-assisted numerical-optimization precedent (via Carter–Hunter–O'Bryant, arXiv:2310.20032, and Tao's blog) that has no known analogue yet for #241. - erdos/840 — quasi-Sidon sets ($|A+A|=(1+o(1))\binom{|A|}{2}$), a further relaxation in the same Bose–Chowla/Erdős family where the leading-order constant is likewise open (Erdős–Freud [ErFr91] bounds, improved by Pikhurko [Pi06]). - Sidon sets / B_2 sets / Golomb rulers — the $h=2$ base case of the same $B_h[g]$-set hierarchy. - concept/additive-energy — the quantity $M(f)=\sum_{a+b=c+d}f(a)f(b)f(c)f(d)$ that Green's proof lower-bounds via Fourier analysis; the central object of the technique that gives the current best upper bound here. - Finite-field / projective-plane constructions for extremal additive sets — the Bose–Chowla (1962) finite-field construction giving the $(1+o(1))N^{1/3}$ lower bound, in the same family as Singer's construction for Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets. - concept/bh-g-sets — the general $B_h[g]$-set framework (Green 2001, Johnston–Tait–Timmons 2021, Timmons 2016) unifying #241, #30, and #840 as special/adjacent cases indexed by $(h,g)$. - AlphaEvolve — LLM-guided evolutionary search over verifier-checked numeric parameter spaces — the AI-evolutionary numerical-optimization technique applied to the analogous $h=2$ bound-tightening problem (per Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets's page); a concrete, never-yet-attempted transplant target for Green's $h=3$ argument.