Nash (1989) — $B_4$-sequence liminf density collapse: $\\liminf_n A(n)\\log^{1/4}n/n^{1/4}<\\infty$

Statement

The $500 problem this settles one case of (Erdős, via Guy's *Unsolved Problems in Number Theory*, problem C11 [Gu04]; erdosproblems.com/41 — the still-open general statement, Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf). For $h\ge2$, call $A\subset\mathbb N$ a $B_h$-sequence if the equation $$n=a_1+a_2+\cdots+a_h,\qquad a_1\le a_2\le\cdots\le a_h,\ a_i\in A,$$ has at most one solution for every $n$ (repeats among the $a_i$ are allowed; only the *ordered, non-decreasing* representation must be unique). Write $A(n):=|A\cap\{1,\dots,n\}|$. Erdős proved this for $h=2$ (Sidon sets) and asked, offering \$500, whether for every $h\ge2$ and every infinite $B_h$-sequence $A$, $$\liminf_{N\to\infty}\frac{A(N)}{N^{1/h}}=0.$$

The specific case Nash (1989) resolved: $h=4$. For every infinite $B_4$-sequence $A\subset\mathbb N$, $$\liminf_{n\to\infty} A(n)\,\frac{\log^{1/4}n}{n^{1/4}}<\infty. \tag{Nash, eq. 3}$$

This is a *quantitative strengthening* of the $\$500$-problem's $h=4$ instance, not merely a qualitative "=0": because $\log^{1/4}n\to\infty$, boundedness of $A(n)\log^{1/4}n/n^{1/4}$ along an infinite sequence of $n\to\infty$ forces $A(n)/n^{1/4}\to0$ along that same sequence, i.e. $\liminf_N A(N)/N^{1/4}=0$ exactly as the prize problem asks — with an explicit rate.

Facts

- Source. John C. M. Nash, "On $B_4$-Sequences," *Canad. Math. Bull.* 32(4) (1989), 446–449. Received 5 Feb 1988, revised 16 Nov 1988. Author: Dept. of Mathematics, Marshall University, Huntington, WV. AMS(1985) classification 11B83. - **Immediate precursor, $h=2$ (Sidon sets), Erdős (unpublished; reported via Stöhr 1955 and proved in full in Halberstam & Roth, *Sequences* Vol. I, Oxford 1966, pp. 89-90):** $$\liminf_n A(n)\,\log^{1/2}n/n^{1/2}<\infty.$$ Nash's paper states this explicitly as its starting point ("In [Stöhr 1955], Erdős showed that... I will show that the analogous relationship... for $B_4$-sequences") and its Lemma 1 is a direct restatement/reuse of the *same* general block+Cauchy–Schwarz sandwich documented in this wiki as Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant) (same citation, Halberstam & Roth pp. 89-90). - Resolution chronology of the full \$500 problem: $h=2$ Erdős (Stöhr 1955/Halberstam–Roth 1966) → $h=4$ Nash 1989 (this page) → all even $h$ Y.-G. Chen, "A note on $B_{2k}$ sequences," *J. Number Theory* 56 (1996), 1–3 → odd $h\ge3$, including the $h=3$ case, still OPEN as of 2026 (Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf). - Why $h=4$ (not $h=3$) was the natural next target after $h=2$: $4=2\times2$ lets the argument reduce a $B_4$ statement about $A$ to a $B_2$-shaped statement about the sumset $2A:=\{a+a':a,a'\in A\}$ (elements added, not just $A$ itself) — a doubling trick with no direct analogue when $h$ is odd. This is exactly the structural reason Chen's generalization reaches every even $h$ but no odd $h>2$ has ever been settled by this or any known method (see Solution, final paragraph). - A $B_4$-sequence is automatically a $B_2$- and $B_3$-sequence (used without separate proof by Nash, stated as a one-line fact): if $a+b=c+d$ with $\{a,b\}\ne\{c,d\}$, then for *any* $e\in A$ the quadruple sums $a+b+e+e$ and $c+d+e+e$ coincide while $\{a,b,e,e\}\ne\{c,d,e,e\}$ as ordered non-decreasing tuples — violating the $B_4$ uniqueness (repeats are permitted in the definition, so $(e,e)$ is a legal pair to append). Hence $A$ is Sidon, and the classical Erdős–Turán bound gives $A(N)\ll N^{1/4}$ as a *free* starting estimate (not itself the theorem — this is only the trivial upper bound the liminf claim then has to beat infinitely often).

Solution

Answer: liminf collapse holds for $h=4$ — no infinite $B_4$-sequence can stay at density $\gg n^{1/4}$ for all large $n$; it must dip to $o(n^{1/4}/\log^{1/4}n)$ infinitely often.

The proof technique (the transferable idea). Nash's argument is a two-layer construction: reuse an *existing, general-purpose* block+Cauchy–Schwarz sandwich lemma unchanged, and spend the entire new work verifying that lemma's hypothesis for a *derived* sequence, via a self-referential (bootstrapping) energy count. Concretely:

1. Reduce to a lemma already proved for $h=2$. State (and use as a black box) the general fact — Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant), Nash's "Lemma 1," attributed to Halberstam & Roth: for *any* sequence $C\subset\mathbb N$, if $D_\ell:=|C\cap((\ell-1)N,\ell N]|$ satisfies $\sum_{\ell=1}^N D_\ell^2\ll N$, then $\liminf_n C(n)\log^{1/2}n/n^{1/2}<\infty$. (Proved by Cauchy–Schwarz applied to $\sum_\ell D_\ell/\ell^{1/2}$ against $\sum 1/\ell$, converting a bound on the block second moment into a bound on the target liminf ratio.) This lemma is *not* specific to Sidon sets; it applies to any sequence for which the block-energy hypothesis (5) can be checked by whatever means.

2. Transport the $h=4$ question onto the $h=2$-shaped lemma via the sumset $2A$. Since $A(N)\ll N^{1/4}$ (Facts), a sums-of-two counting bound gives, for large $n$, $(2A)(n)\ge\binom{A[n/2]}{2}\ge A([n/2])^2\!\cdot(1+o(1))$. So a bound of the *same shape* as the $h=2$ theorem, but applied to $2A$ instead of $A$ — namely $\liminf_n(2A)(n)\log^{1/2}n/n^{1/2}<\infty$ — algebraically forces $\liminf_n A(n)\log^{1/4}n/n^{1/4}<\infty$, the actual $h=4$ target. This is the "doubling" reduction: $h=4$ for $A$ is reduced to $h=2$-*shaped* for $2A$.

3. The obstacle: $2A$ is not itself Sidon. Every quadruple $a,b,c,d\in A$ produces the identity $(a+c)+(b+d)=(a+d)+(b+c)$ — a *forced*, non-trivial collision in $2A+2A$ that has no counterpart in an honest Sidon set. Applying the Lemma-1 machinery to $2A$ therefore requires directly re-verifying its hypothesis $\sum_\ell D_\ell^2\ll N$ from scratch for $C=2A$ — the original Sidon proof of this hypothesis for $C=A$ does not transfer.

4. Verifying the hypothesis: split into "generic" and "degenerate" quadruples, and close the loop by self-reference — this is the load-bearing new idea. The block second moment for $2A$ reduces (via a standard binomial-coefficient counting identity) to bounding $$|S|,\qquad S:=\{(a_1,a_2,a_3,a_4)\in A^4 : a_i\le N^2,\ 1\le a_1+a_2-a_3-a_4\le N\},$$ the number of $A$-quadruples whose *cross-difference* $a_1+a_2-a_3-a_4$ lands in a window of length $N$. Nash splits $S$ into two classes: - Generic ($a_1\notin\{a_3,a_4\}$ and $a_2\notin\{a_3,a_4\}$, i.e. no index collides across the $+/-$ split): if two generic quadruples give the same cross-difference value, rearranging the equality $a_1+a_2-a_3-a_4=a_1'+a_2'-a_3'-a_4'$ into $a_1+a_2+a_3'+a_4'=a_1'+a_2'+a_3+a_4$ exposes an equality of two genuine $B_4$-sums of $A$ — so the $B_4$-uniqueness hypothesis itself forces the two quadruples to be permutations of one another (at most 4 possibilities, from the genericity conditions). Hence at most $O(1)$ generic quadruples map to any single target value, and the generic class contributes $O(N)$ to $|S|$ — the higher-order hypothesis is used *directly and cheaply* here. - Degenerate (some index collides, e.g. $a_1=a_3$, collapsing the quadruple's cross-difference to a bare pairwise difference $a_2-a_4$): this class's contribution is $A(N^2)\cdot|T|$, where $T:=\{(a_2,a_4): a_i\le N^2,\ 1\le a_2-a_4\le N\}$ is a *lower-order*, pair-difference version of exactly the same counting problem. Using the free bound $A(N^2)\ll N^{1/2}$ from step 0 is not enough by itself — the missing ingredient is a bound on $|T|$, and Nash gets it by noticing $T$ is itself expressible via $S$: $\binom{|T|}{2}\le|S|$ (any two elements of $T$ lift to a quadruple satisfying $S$'s difference condition). Substituting the already-derived bound $|S|\ll N+A(N^2)|T|$ into this self-reference produces a closed quadratic inequality, $|T|^2\ll N+N^{1/2}|T|$, which solves outright to $|T|\ll N^{1/2}$ — with *no* external input beyond what has already been proved about $S$ and $A$. - Feeding $|T|\ll N^{1/2}$ back gives the degenerate class $O(N^{1/2}\cdot N^{1/2})=O(N)$, matching the generic class, so $|S|\ll N$ overall — exactly the hypothesis Lemma 1 needs.

5. Chain the reductions back: hypothesis verified $\Rightarrow$ Lemma 1 applies to $C=2A$ $\Rightarrow$ step 2's algebra converts this into the $h=4$ target for $A$. $\blacksquare$

Why this is the reusable idea (the part later work borrows). The generalizable move is not "block decomposition + Cauchy–Schwarz" per se (that machinery — Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant) — already existed for $h=2$ and is used completely unchanged). The new, transferable idea is: *when lifting a 2-variable uniqueness hypothesis to a 2k-variable derived object (here, sums-of-pairs), split the resulting energy count into a class where the higher-order uniqueness hypothesis gives an immediate $O(1)$ multiplicity bound, and a residual/degenerate class that is not directly controllable — but is exactly a lower-order instance of the same counting problem, so a self-referential (quadratic-in-itself) inequality closes it without needing any new external estimate.* This "recursion that closes on itself" — rather than an explicit construction or a wholly new inequality — is precisely what made $h=4$ tractable from $h=2$, and Chen's 1996 extension to all even $h=2k$ is the same $A\to kA$ doubling/pairing idea run one level further. It structurally requires $h$ to be even (so that $hA$ can be built as a sum of $h/2$ or $2$ copies of a smaller-order object whose own $B_{h/2}$-type uniqueness can be invoked in the "generic" step): for odd $h$ (starting at $h=3$, Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf) there is no analogous way to write the $h$-fold sumset as a doubling of a smaller integer-order object, which is exactly why the odd case has resisted this technique — and, as far as is documented on this wiki, any other technique — for over 30 years since Chen's 1996 paper.

Related

- Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — the $h=3$ (odd) case of the same \$500 problem: still open; the natural next target for this page's technique, and explicitly the case where the doubling/pairing reduction (step 2 here) has no known analogue. - Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant) — the general block-decomposition + weighted Cauchy–Schwarz sandwich (Nash's "Lemma 1," reused unchanged from the $h=2$ Erdős/Stöhr/Halberstam–Roth proof); this page's contribution is entirely in supplying a new way to verify that lemma's hypothesis for a derived (sumset) sequence, not in modifying the lemma itself. - Sidon sets / B_2 sets / Golomb rulers — the $h=2$ base case ($B_2$-sequences) that Nash's introduction takes as its starting theorem, and whose Erdős–Turán upper bound $A(N)\ll N^{1/4}$-for-$B_4$ (via the "$B_4\Rightarrow$Sidon" fact in this page's Facts) supplies Nash's free initial estimate. - Y.-G. Chen, "A note on $B_{2k}$ sequences," *J. Number Theory* 56 (1996), 1–3 — generalizes this page's $h=4$ result to every even $h=2k$ by the same doubling-reduction idea, one level further (not independently verified this session; see provenance). - erdosproblems.com/41 — the live public tracker for the still-open general problem, whose remarks paragraph is the entry point that ties Nash's and Chen's results together as the two known cases of Guy's problem C11.