Chen (1993/1996) — $B_{2k}$-sequence liminf density collapse for every even $h=2k$

Statement

The $500 problem this settles the entire even case of (Erdős, via Guy's *Unsolved Problems in Number Theory*, problem C11; erdosproblems.com/41, 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$. Write $A(n):=|A\cap\{1,\dots,n\}|$. Erdős proved this for $h=2$ (Sidon sets) and offered \$500 for the general claim: for every $h\ge2$ and every infinite $B_h$-sequence $A$, $$\liminf_{N\to\infty}\frac{A(N)}{N^{1/h}}=0.$$

The case Chen resolved: every even $h=2k$ ($k\ge1$). For every infinite $B_{2k}$-sequence $A\subset\mathbb N$ ($k\ge2$; $k=1$ is Erdős's own base case), $$\liminf_{n\to\infty} A(n)\,\frac{(\log n)^{1/(4k-4)}}{n^{1/(2k)}}<\infty,\qquad \limsup_{n\to\infty}\frac{a_n}{n^{2k}\sqrt{\log n}}=\infty,$$ (Chen, J. Number Theory 56 (1996), 1–3), building on the qualitatively identical but cruder $$\liminf_{n\to\infty} A(n)\left(\frac{\log n}{n}\right)^{1/(2k)}<\infty$$ from Chen's own earlier paper (Acta Arith. 64 (1993), 325–330). Both are *quantitative strengthenings* of the \$500 problem's even-$h$ instances, not merely "$=0$": since the log factor multiplying $A(n)$ grows without bound, boundedness along a subsequence forces $A(n)/n^{1/2k}\to0$ along that same subsequence — i.e. $\liminf_N A(N)/N^{1/(2k)}=0$ exactly as the prize problem asks, with an explicit rate of collapse.

Facts

- Sources. Sheng Chen, "On Sidon sequences of even orders," *Acta Arith.* 64 (1993), 325–330 (MR 94h:11015); Sheng Chen, "A note on $B_{2k}$ sequences," *J. Number Theory* 56 (1996), 1–3 (MR 97a:11035 / MR1370192, per this wiki's already-verified Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf citation). - Resolution chronology of the full \$500 problem: $h=2$ Erdős (unpublished; reported by Stöhr 1955, proved in full in Halberstam & Roth, *Sequences* Vol. I, Oxford 1966, pp. 89–90) → $h=4$ Nash 1989, *Canad. Math. Bull.* 32, 446–449 (Nash (1989) — $B_4$-sequence liminf density collapse: $\\liminf_n A(n)\\log^{1/4}n/n^{1/4}<\\infty$) → all even $h=2k$, Chen 1993/1996 (this page) → odd $h\ge3$, including $h=3$, still OPEN as of 2026 (Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf). - Chen's own conjecture, stated in the 1993 paper, generalizes the pattern to every $h$ (not just even): $\liminf_n A(n)(\log n/n)^{1/h}<\infty$ for any $B_h$-sequence. This general conjecture is *itself still open* for odd $h\ge3$ — Chen proved his own conjecture only for the even case, which is the content of this page. - The even-order regime was independently attacked and confirmed by at least three separate groups within a two-year window, a strong signal that "even $h$" is a genuinely tractable structural case rather than one lucky proof: Chen (1993, 1996, the sharpest quantitative form); Martin Helm, "On $B_{2k}$-sequences," Acta Arith. 63 (1993), 367–371, and "A remark on $B_{2k}$-sequences," J. Number Theory 49 (1994), 246–249 — the latter explicitly stated as *improving* Chen's log-exponent, from $1/(2k)$ to $1/(3k-1)$, in the analogous liminf inequality; and Xing De Jia, "On $B_{2k}$-sequences," J. Number Theory 48 (1994), 183–196, giving a *different*, purely elementary combinatorial route to a closely related bound (if $A(n^2)\ll A(n)^2$ then $\liminf_n A(n)/\sqrt[2k]{n/\log n}<\infty$), and — per Mihail Kolountzakis's own 1996 paper abstract (J. Number Theory 56 (1996), 4–11) — Jia's elementary method *also* independently reproved the companion finite-set density bound $\sigma_{2k}\le\big((k)(k!)^2\big)^{1/2k}$ for every even order, matching what Lindström (1969) had done by hand only for $k=2$. - A $B_{2k}$-sequence is automatically a $B_2, B_3,\dots, B_{2k-1}$-sequence (the same "pad with repeated elements" trivial fact used at $k=2$ by Nash, Nash (1989) — $B_4$-sequence liminf density collapse: $\\liminf_n A(n)\\log^{1/4}n/n^{1/4}<\\infty$ Facts): appending enough copies of any fixed $e\in A$ to two colliding shorter sums produces a collision in the $2k$-fold sum, so $A$ inherits the classical finite-set upper bound $A(N)\ll_k N^{1/2k}$ (Bose–Chowla / Erdős–Turán-type bounds, sharpened over decades, see Sidon sets / B_2 sets / Golomb rulers) as a *free* starting estimate — this is only the trivial ceiling the liminf claim then has to beat infinitely often, not itself the theorem. - Odd $h\ge3$ remains completely open, including the very next case $h=3$, per this wiki's own Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf page: no proof or disproof for any odd $h$ has been found anywhere in the 30 years since Chen's 1996 paper, and erdosproblems.com marks the $h=3$ instance open with zero comments as of its most recent (2026) edit.

Solution

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

The proof technique (the transferable idea) — reconstructed here as a direct generalization of Nash's $h=4$ argument (Nash (1989) — $B_4$-sequence liminf density collapse: $\\liminf_n A(n)\\log^{1/4}n/n^{1/4}<\\infty$; this generalization is inferred, not read from Chen's own paper — see provenance). The structural shape that makes even $h$ tractable is a doubling/pairing reduction that has no analogue for odd $h$:

1. Fix a general-purpose block+Cauchy–Schwarz lemma, unchanged for every $k$. The same lemma Erdős used for $h=2$ and Nash reused unchanged for $h=4$ — Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant): for *any* sequence $C\subset\mathbb N$, if the dyadic block second moment $\sum_{\ell\le N} D_\ell^2\ll N$ (where $D_\ell:=|C\cap((\ell-1)N,\ell N]|$), then $\liminf_n C(n)\log^{1/2}n/n^{1/2}<\infty$. This lemma is $h$-independent; it only needs a second-moment (energy) bound on whatever derived object $C$ is fed into it. 2. Transport the $B_{2k}$ question about $A$ onto a $B_2$-shaped question about the $k$-fold sumset $kA:=\{a_1+\cdots+a_k : a_i\in A\}$. At $k=2$ this is exactly Nash's reduction to $2A$. For general $k$, the free bound $A(N)\ll N^{1/2k}$ (Facts) gives $(kA)(n)\gtrsim A(n/k)^k$, so a bound of the *same shape* as the $h=2$ lemma applied to $kA$ — namely $\liminf_n(kA)(n)\log^{1/2}n/n^{1/2}<\infty$ — algebraically forces $\liminf_n A(n)\,(\log n)^{c_k}/n^{1/2k}<\infty$, the actual $B_{2k}$ target, for an explicit $c_k$ coming out of the algebra. This is the "$k$-fold doubling" reduction: $h=2k$ for $A$ reduces to $h=2$-*shaped* for the $k$-fold sumset $kA$. 3. The obstacle: $kA$ is never itself Sidon for $k\ge2$. Every $2k$-tuple $a_1,\dots,a_k,b_1,\dots,b_k\in A$ that can be re-paired into two different $k$-subsets summing to the same total produces a *forced*, non-trivial collision in $kA+kA$ with no counterpart in an honest Sidon set — the original $h=2$ proof of the energy hypothesis for $C=A$ does not transfer to $C=kA$ and has to be re-derived from scratch. 4. Re-derive the energy hypothesis for $kA$ by splitting into "generic" and "degenerate" $2k$-tuples, closing the loop with a self-referential (bootstrapping) inequality — the load-bearing new idea, generalized from Nash's 4-tuple split. The block second moment for $kA$ reduces to bounding the number of $A^{2k}$-tuples whose *cross-difference* $(a_1+\cdots+a_k)-(b_1+\cdots+b_k)$ lands in a fixed-length window: - Generic tuples (no index shared between the two $k$-blocks): rearranging a coincidence between two generic tuples into an equality of two genuine $2k$-fold sums of $A$ invokes the $B_{2k}$-uniqueness hypothesis itself, forcing the two tuples to be permutations of one another — at most $O_k(1)$ generic tuples per target value, contributing $O_k(N)$ overall. The higher-order hypothesis does the work directly here, exactly as at $k=2$. - Degenerate tuples (some index shared, collapsing the cross-difference to a *lower-order* version of the identical counting problem, on $(k-1)$-fold or smaller sumsets): this class's contribution is again expressible via the *same* target quantity one order down, so — as at $k=2$, where the degenerate class collapsed onto a bare pairwise-difference count $T$ satisfying $\binom{|T|}{2}\le|S|$ — a self-referential (quadratic-in-itself, or in general polynomial-in-itself) inequality closes the degenerate class without any external input, purely from what has already been established about the generic class and about $A$ itself. - This inductive-in-$k$ closure is exactly why the technique caps out at $k$ finite but arbitrary: each step down from $k$ to $k-1$ re-uses the *same* generic/degenerate machinery on a strictly smaller sumset, bottoming out at the original $h=2$ (Erdős/Stöhr) base case. 5. Chain the reductions back: hypothesis verified for $C=kA$ $\Rightarrow$ the block+Cauchy–Schwarz lemma applies $\Rightarrow$ step 2's algebra converts this into the $B_{2k}$ target for $A$, for every $k\ge1$. $\blacksquare$

Why this is the reusable idea. The generalizable move is not "block decomposition + Cauchy–Schwarz" (that machinery is $h$-independent and pre-existing). The transferable idea, run one level further at every step from $k=1\to2\to\cdots$, is: *when lifting a $2$-variable uniqueness hypothesis to a $2k$-variable derived object (here, $k$-fold sumsets), split the resulting energy count into a class where the higher-order uniqueness hypothesis gives an immediate $O_k(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 an induction on $k$, closed at each step by a self-referential inequality, finishes the argument without any new external estimate.* It structurally requires $h$ to be even, because it is built entirely out of writing the $h$-fold sumset as $k$ copies of $A$ glued pairwise into a $k$-fold sumset $kA$, then comparing $kA$ against itself (a $B_2$-shaped, i.e. pairwise, comparison) — there is no known way to split an *odd* number of summands into two equal, comparable halves, which is exactly why Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf (the $h=3$ case) and every other odd $h\ge3$ remain open more than three decades after Chen's 1996 paper. Any attack on the odd case would need either a genuinely different (non-pairing) energy argument, or a way to compare unequal-sized sumset halves (e.g. $\lfloor h/2\rfloor A$ vs. $\lceil h/2\rceil A$) whose cross terms the generic/degenerate split cannot currently absorb.

Related

- Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — the $h=3$ (odd) case of the same \$500 problem, and the general tracker for the whole family: still open, explicitly the case where the pairing reduction used here has no known analogue. - Nash (1989) — $B_4$-sequence liminf density collapse: $\\liminf_n A(n)\\log^{1/4}n/n^{1/4}<\\infty$ — the $k=2$ ($h=4$) instance of this exact family, solved first (1989) and independently, directly verified against Nash's full proof; this page's Solution section is a reconstructed generalization of that page's argument to general $k$. - Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant) — the $h$-independent block-decomposition + weighted Cauchy–Schwarz sandwich (Erdős/Stöhr/Halberstam–Roth, reused unchanged by Nash and, by inference, by Chen) that both the $k=2$ and general-$k$ arguments reduce to as their final step. - Sidon sets / B_2 sets / Golomb rulers — the $h=2$ base case and the finite-set density bounds ($A(N)\ll_k N^{1/2k}$) that supply the free starting estimate for every even-$h$ argument in this family. - Parity/pairing-halving argument for even-order $B_h$ liminf proofs — the general "even order lets you pair/halve; odd order doesn't" obstruction this whole cluster (Nash, Chen, and the still-unbroken odd wall at Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf) is the canonical worked example of. - Martin Helm, "On $B_{2k}$-sequences," *Acta Arith.* 63 (1993), 367–371, and "A remark on $B_{2k}$-sequences," *J. Number Theory* 49 (1994), 246–249 — independent, log-exponent-sharpening refinements of Chen's same-shaped even-$h$ result. - Xing De Jia, "On $B_{2k}$-sequences," *J. Number Theory* 48 (1994), 183–196 — an independent, purely elementary-combinatorial route to a closely related even-$h$ liminf/density bound, corroborating that even-$h$ is robustly tractable by more than one method. - erdosproblems.com/41 — the live public tracker whose remarks paragraph is the entry point tying Nash's, Chen's, and the still-open odd-$h$ cases together as the known state of Guy's problem C11.