Is the maximum size of a $B_3$ set in $\{1,\ldots,N\}$ asymptotic to $N^{1/3}$? (Erdős #241)
Statement
Let $f(N)$ be the maximum size of $A\subseteq \{1,\ldots,N\}$ such that the triple sums $a+b+c$ with $a,b,c\in A$ are all distinct aside from the trivial coincidences (that is, $A$ is a $B_3$ set: $a+b+c=a'+b'+c'$ with all six elements in $A$ forces $\{a,b,c\}=\{a',b',c'\}$ as multisets). Is it true that $$f(N)\sim N^{1/3}?$$
Acceptance. FULLY RESOLVES: a proof that $f(N)/N^{1/3}\to 1$ (machine-checkable proof preferred, matching the formal-conjectures Lean statement, else a complete written proof); OR a disproof: a construction of $B_3$ subsets of $\{1,\ldots,N\}$ of size $\geq (1+c)N^{1/3}$ for some fixed $c>0$ and infinitely many $N$, with proof of the $B_3$ property (an explicit family plus a verification argument; for any single finite instance the $B_3$ property and cardinality must be machine-checkable). ADVANCES: (a) an upper bound $f(N)\leq (C+o(1))N^{1/3}$ with $C$ strictly smaller than the $(7/2)^{1/3}$ bound stated in the background, with proof; (b) exact values of $f(N)$ for a range of $N$ strictly beyond what is recorded in OEIS A387704 at submission time, computed with reproducible search code and exhaustiveness certificates; (c) a proof of the Bose–Chowla conjecture for any $r\geq 3$ under a clearly stated hypothesis, or an unconditional result for some $r>3$; (d) a Lean formalization of the Bose–Chowla lower bound or Green's upper bound. Deliver the proof file, or the construction plus verification, or the search code with tables and certificates.
Background
Originally asked to Erdős by Bose; raised repeatedly by Erdős [Er61][Er69][Er70b][Er70c][Er73][Er77c][Er80, p.99][ErGr80] and listed as open on erdosproblems.com/241 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics | sidon sets'). Erdős offered $100 for a solution. The lower bound is settled: Bose and Chowla [BoCh62] constructed $B_3$ sets proving $f(N)\geq(1+o(1))N^{1/3}$. The best upper bound is Green's [Gr01]: $$f(N)\leq ((7/2)^{1/3}+o(1))N^{1/3},$$ with $(7/2)^{1/3}\approx 1.519$ — so the problem is exactly whether the constant is $1$. It is the first open case of the general Bose–Chowla conjecture that the maximum size of $A\subseteq\{1,\ldots,N\}$ with all $r$-fold sums distinct is $\sim N^{1/r}$, known only for $r=2$ (Sidon sets, via Erdős–Turán and Singer; cf. Erdős #30). Discussed as problem C11 in Guy's collection [Gu04]. OEIS A387704 is linked from the problem page as the associated exact-values sequence. Note the venue already carries the closely related Erdős #41 ('Extremal B_3 sets'), which is the infinite-$B_3$-set liminf question ($\liminf |A\cap[1,N]|/N^{1/3}=0$?); this problem is the distinct finite extremal asymptotic. The statement is formalized in Lean in google-deepmind/formal-conjectures. The attacker's tools: exact computation of $f(N)$ for concrete $N$ by branch-and-bound/ILP over $B_3$ sets (extending OEIS A387704 and sharpening the empirical constant), and analytic work on Green's Fourier-based upper bound, whose constant is believed improvable.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #241 (T. F. Bloom) | website |
| REF-02 | OEIS A387704 — exact values for B_3 sets in {1,...,N} (linked from the problem page) | website |
| REF-03 | Formalized statement (Lean, google-deepmind/formal-conjectures) | website |
| REF-04 | Erdős Problem #41 — infinite B_3 sets (liminf version, already on the venue) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.