Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf

Statement

Let $A\subset\mathbb{N}$ be an infinite set such that the triple sums $a+b+c$ ($a,b,c\in A$) are all distinct, aside from the trivial coincidences forced by commutativity (i.e. $A$ is an infinite $B_3$ set). Is it true that \[\liminf_{N\to\infty} \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/3}}=0?\] (erdosproblems.com/41, statement verbatim)

Facts

- Prize $500; status open; erdosproblems.com explicitly states "This is open, and cannot be resolved with a finite computation." - Falsifiable: no in the finite-counterexample sense — a "no" answer requires an infinite construction with $|A\cap\{1,\ldots,N\}| \gg N^{1/3}$ for *all* large $N$ (not just infinitely often), which is an asymptotic statement about an infinite object, not decidable by any finite search. A "yes" answer requires a general impossibility proof. - Origin: Erdős, across [Er77c], [Er80,p.99], [ErGr80], [Er81], [Er85c], [Er91], [Er95], [Er97c]; also Vaughan's list [Va99,§1.23]. Additional thanks on the site page to Zachary Chase. - Context — this is the $h=3$ case of a general family. Erdős first proved (own theorem, no single paper pinned by erdosproblems.com — cited across the same survey list) that for pairwise sums ($h=2$, i.e. ordinary infinite Sidon sets): \[\liminf_N \frac{|A\cap\{1,\ldots,N\}|}{N^{1/2}} = 0.\] Guy's *Unsolved Problems in Number Theory*, problem C11 [Gu04], records that Erdős then offered \$500 for the general claim: for all $h\ge 2$, every infinite $B_h$ set (all $h$-fold sums distinct up to trivial coincidence) satisfies $\liminf_N |A\cap\{1,\ldots,N\}|/N^{1/h}=0$. Problem #41 is precisely the $h=3$ instance of this family. - Known results / best bounds (verified via erdosproblems.com/41's remarks, cross-checked bibliographically): - $h=4$: proved by Nash, "On $B_4$-sequences," Canad. Math. Bull. 32 (1989), 446–449 [Na89] (MR 1019410). - All even $h$: proved by Chen, "A note on $B_{2k}$ sequences," J. Number Theory 56 (1996), 1–3 [Ch96b] (MR 1370192) — this paper's title ("$B_{2k}$") signals the proof is specific to *even* order, consistent with erdosproblems.com's claim that the even case is fully settled but says nothing about odd $h$. - Odd $h\ge3$, including $h=3$ (this problem): no proof found anywhere in this search. erdosproblems.com marks #41 open with zero comments and zero claimed partial/full solutions as of 06 April 2026 (last edit date) / 02 July 2026 (fetch date). - I could not obtain the primary text of [Na89] or [Ch96b] (paywalled; zbMATH and MathSciNet both blocked automated access via Cloudflare) — so the *reason* the argument works for even $h$ but not odd $h$ is unverified; erdosproblems.com does not explain it either. This is itself a concrete research lead (see Attack surface). - Related problems: Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — the $h=2$ companion (does there exist an infinite Sidon set with $|A\cap\{1,\ldots,N\}|\gg_\epsilon N^{1/2-\epsilon}$ for all $\epsilon$?), same \$500-era cluster, open; Erdős #158 (ancestor result) — the solved $g=1$ liminf-density theorem for infinite Sidon sets, and its bounded-multiplicity generalization — the multiplicity-relaxed analogue of the *same* liminf statement for $h=2$ but allowing up to 2 representations per sum ($B_2[2]$ sets), open, explicitly reduces to Erdős's own $h=2$ theorem when the multiplicity bound is 1; Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — finite-Sidon-set sharp asymptotics, same Erdős–Turán-era cluster; erdos/14 — unique-sum-representation complement density, same cluster.

Literature state

Not resolved anywhere found. Cross-checked erdosproblems.com/41 itself (open, no comments, no partial solutions), the erdosproblems.com Sidon-sets tag page (34-problem family, #41 not marked solved by any neighboring entry), and the github.com/teorth/erdosproblems wiki "AI contributions to Erdős problems" page (fetched in full — extensive table of GPT-5.x/DeepMind/Aristotle/Lean contributions to *other* numbered problems, e.g. entries tagged [741], [1041], [1141], [441], [541] — but no entry referencing problem 41 as of the fetch).

Broader arXiv/OpenAlex/WebSearch sweep for post-1996 progress on $B_h$-set liminf density for odd $h$ (or specifically $h=3$) turned up no resolving paper. Papers found are all adjacent-but-orthogonal (upper-bound / construction direction, not the liminf-lower-bound-collapse direction this problem asks about): - O'Bryant, "Constructing Thick $B_h$-sets," arXiv:2308.12406 (2023) — explicit finite $B_h$-set diameter constructions generalizing Bose–Chowla/Singer; ends with "a list of open problems" (abstract read directly) but does not address the liminf question. - Fabian, Rué, Spiegel, "On strong infinite Sidon and $B_h$ sets and random sets of integers," arXiv:1911.13275 (2019) — new lower bounds for $\alpha$-strong Sidon/$B_h$ sets inside *random* infinite subsets of $\mathbb{N}$, improving Kohayakawa–Lee–Moreira–Rödl; a genuinely different question (density of the largest $B_h$ set inside a random set), not the liminf-of-all-$B_h$-sets question. - Cilleruelo (with Tesoro), "Dense infinite $B_h$ sequences," arXiv:1206.3087 (2012) — constructs infinite $B_3,B_4$ sequences with counting function $\gg x^{\sqrt{(h-1)^2+1}-(h-1)+o(1)}$, i.e. pushes the *construction* side (how dense can a $B_h$ set be built), the mirror-image question to #41's *obstruction* side (must every $B_h$ set collapse infinitely often). These are complementary, not competing — a good $B_3$ construction from Cilleruelo–Tesoro is exactly the kind of witness a disproof of #41 (a "no", i.e. existence of a $B_3$ set avoiding the liminf collapse) would need, but Cilleruelo–Tesoro's exponent is well below $1/3$, so it does not resolve #41 either way. - Nathanson, "$B_h$-sets of real and complex numbers," arXiv:2502.21272 (2025) — a genericity result (almost all finite subsets of $\mathbb{R}$/$\mathbb{C}$ are $B_h$-sets), different setting (finite subsets of continuum, not infinite subsets of $\mathbb{N}$ with density asymptotics).

Conclusion: the $h=3$ case (problem #41) is genuinely open, exactly as erdosproblems.com states, and appears essentially untouched in the literature since Chen's 1996 even-$h$ paper — I found no serious attempt at the odd-$h$ case in 30 years of subsequent $B_h$-set literature.

Attack surface

- Mode: derivation+formalization (not finite-search — explicitly ruled out by the site; this is an asymptotic statement about all infinite $B_3$ sets). - Concrete first experiment: (1) obtain and carefully read Nash [Na89] and Chen [Ch96b] (via library/interlibrary access, since automated fetch was blocked) to extract exactly *where* the even-$h$ argument uses parity — the title "$B_{2k}$" strongly suggests a pairing/halving trick (e.g. relating an $h=2k$-fold sum condition to a $k$-fold structure via $a_1+\cdots+a_k = b_1+\cdots+b_k \Rightarrow$ contradiction with the $2k$-sum-distinctness, or an induction $2k \to k$) that has no obvious analogue when $h$ is odd and can't be split into two equal halves; this is the single highest-value unresolved question in this write-up. (2) In parallel, numerically construct finite truncations of the Cilleruelo–Tesoro dense $B_3$ sequence (arXiv:1206.3087) and the naive greedy $B_3$ sequence, and empirically track $|A\cap\{1,\ldots,N\}|/N^{1/3}$ across dyadic $N$ to look for the conjectured infinitely-often collapse pattern (or its absence) as a sanity/intuition-building exercise — this cannot prove anything (falsifiability is "not-finite") but can suggest whether the $h=3$ truth more resembles the even-$h$ (collapse) or could plausibly be false (no collapse). - Oracle: for any finite truncation, "is this set $B_3$" and "what is $|A\cap\{1,\ldots,N\}|/N^{1/3}|$ at each $N$" are both fully mechanical ($O(n^3)$ triple-sum collision check, or $O(n^2\log n)$ with sorting/hashing) — so the numerical/exploratory half of the experiment is fully oracle-checkable, even though it cannot settle the actual infinite-$\liminf$ statement. - Feasibility: research-mathematics-hard, but tractable-shaped — unlike many \$500 Erdős problems this one has an *existing, verified-successful proof technique one case up (h=4) and one case-class over (all even h)*; the open gap is specifically "make the Nash/Chen argument (or a genuinely different one) work without a pairing/halving step." That is a much narrower, more concrete target than "prove an arbitrary open conjecture" — a strong candidate for LLM-assisted derivation (search for a parity-independent generalization of Nash/Chen, or a fresh three-way pairing/triple-counting argument analogous to how the $h=2$ case is normally proved) once the primary sources are in hand. No formalization (Lean or otherwise) of either the $h=2$, $h=4$, or even-$h$ results was found in this search.

Related

- Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — the $h=2$ (Sidon set) companion question: does there exist an infinite Sidon set achieving density $N^{1/2-\epsilon}$ for all $\epsilon$? Same \$500-era Erdős cluster, also open, also "not finite computation." - Erdős #158 (ancestor result) — the solved $g=1$ liminf-density theorem for infinite Sidon sets, and its bounded-multiplicity generalization — liminf-density question for $B_2[2]$ sets (at most 2 representations per sum instead of exactly 1); explicitly reduces to Erdős's own $h=2$ theorem when relaxed to genuine Sidon sets; structurally the closest sibling to #41 (a different relaxation axis — multiplicity instead of order — of the same base theorem), open. - Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — finite Sidon set sharp asymptotics ($h(N) = N^{1/2}+O_\epsilon(N^\epsilon)$?), \$1000, same cluster, open. - erdos/14 — unique-sum-representation complement density, same Sidon-set cluster, open. - Sidon sets / B_2 sets / Golomb rulers — the $h=2$ base case; central object of the whole cluster. - B_h sets — generalized Sidon sets of order h (distinct h-fold sums) — the general object of this problem: sets with all $h$-fold sums distinct up to trivial coincidence, of which Sidon sets ($h=2$) are the base case. - Generalized Sidon set constructions — the $B_h[g]$ toolbox (finite-field unions, interleaving, products) — umbrella term (O'Bryant's arXiv:2308.12406 and Martin–O'Bryant's math/0408081) for $B_h$/$B_h[g]$-type constructions, the toolbox likely needed for any $h=3$ counterexample attempt. - Parity/pairing-halving argument for even-order $B_h$ liminf proofs — the (unverified, paywalled) technique that appears to be the load-bearing mechanism in Nash [Na89]/Chen [Ch96b]'s even-$h$ proofs; understanding whether it is essential or circumventable is the core research question here. - Semi-random nibble vs. probabilistic log-prime/discrete-log constructions: two routes to beating the greedy exponent — Ajtai–Komlós–Szemerédi / Ruzsa / Cilleruelo-style probabilistic and discrete-log constructions (documented in detail on Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set) that are the state of the art for building *dense* $B_h$ sets, relevant to the "witness a disproof" direction of #41.