Parity/pairing-halving argument for even-order $B_h$ liminf proofs

Statement

The technique, in one sentence. To prove a liminf-density-collapse statement for infinite $B_h$-sequences ($h$-fold sums $a_1+\cdots+a_h$, $a_1\le\cdots\le a_h\in A$, all distinct — see Sidon sets / B_2 sets / Golomb rulers for $h=2$) when $h=2k$ is even, write $h$ as two equal halves ($k+k$) and transport the question onto the derived $k$-fold sumset $kA:=\{a_1+\cdots+a_k : a_i\in A\}$, to which an already-proved order-2-shaped liminf lemma (e.g. Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant)) can be applied — *provided* one can independently verify that lemma's hypothesis (a bounded block second moment / energy bound) for $kA$, which is not automatic because $kA$ is never itself literally Sidon. That verification is done by splitting the relevant collision-count set into a "generic" class, where the $B_h$-uniqueness hypothesis on $A$ *itself* (not on $kA$) forces an $O(1)$ multiplicity bound almost for free via a direct algebraic rearrangement, and a "degenerate" class (indices shared between the two halves), which turns out to be a *lower-order instance of the identical counting problem* and is closed by a self-referential (bootstrapping) inequality rather than any new external input.

**Precise instantiation, $h=4$ (Nash 1989, fully verified primary-source proof — see Nash (1989) — $B_4$-sequence liminf density collapse: $\\liminf_n A(n)\\log^{1/4}n/n^{1/4}<\\infty$).** For every infinite $B_4$-sequence $A\subset\mathbb N$ with $A(n):=|A\cap\{1,\dots,n\}|$, $$\liminf_{n\to\infty} A(n)\,\frac{\log^{1/4}n}{n^{1/4}}<\infty,$$ proved by transporting the question onto $2A$ and the $h=2$ (Sidon) block+Cauchy–Schwarz sandwich lemma of Erdős/Stöhr/Halberstam–Roth (which gives $\liminf_n C(n)\log^{1/2}n/n^{1/2}<\infty$ for any $C$ whose block second moment is $\ll N$).

**General even case (Chen 1996, "A note on $B_{2k}$ sequences," *J. Number Theory* 56, 1–3 — attributed secondhand, not independently read; see provenance). The same $\$500$ Erdős/Guy-C11 liminf-collapse statement $\liminf_N A(N)/N^{1/h}=0$ holds for every even** $h$, by (per erdosproblems.com/41 and this wiki's own problems/41.md inference) the same doubling/pairing-halving reduction carried one level further.

The obstruction this technique cannot cross. Odd $h$ (starting at $h=3$, Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf, still open as of 2026) has no way to split $h$ into two equal positive-integer halves, so there is no analogous derived sumset $kA$ ($h=2k$) onto which to transport the argument — this is precisely why the technique is named for its *parity* dependence, and why (per this wiki's own investigation) no odd-$h$ proof of any kind is known 30+ years after Chen's 1996 paper.

Facts

- Historical/logical chain: $h=2$ (Sidon sets), Erdős, unpublished, reported by Stöhr 1955 and proved in full in Halberstam & Roth, *Sequences* Vol. I (Oxford, 1966), pp. 89–90, giving $\liminf_n A(n)\log^{1/2}n/n^{1/2}<\infty$ — the base-case lemma this whole technique reuses unchanged as a black box (documented in full in Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant)) $\to$ $h=4$, Nash 1989 (*Canad. Math. Bull.* 32(4), 446–449), the first application of the pairing-halving idea, fully primary-source-verified on this wiki $\to$ all even $h=2k$, Chen 1996 (*J. Number Theory* 56, 1–3), generalizing one level further $\to$ odd $h\ge3$ including $h=3$, still open (Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf, the \$500 Erdős/Guy problem C11). - The "$B_4\Rightarrow$ Sidon" free starting estimate. Any $B_4$-sequence is automatically also a $B_2$- (Sidon) and $B_3$-sequence: if $a+b=c+d$ with $\{a,b\}\ne\{c,d\}$ then for any $e\in A$, appending the repeated pair $(e,e)$ gives two distinct $B_4$-representations of the same sum, contradicting $B_4$-uniqueness (Nash's argument implicitly relies on repeats being permitted in the $B_h$ definition). Hence the classical Erdős–Turán bound $A(N)\ll N^{1/4}$ is available *for free* before the real argument starts (used as step 0 of Nash's proof). - **Why the reduction needs the *original* order-$h$ hypothesis, not just an order-2 hypothesis on the derived object.** The derived sumset $kA$ is *never* itself Sidon: for $h=4$, every quadruple $a,b,c,d\in A$ produces the forced identity $(a+c)+(b+d)=(a+d)+(b+c)$, a genuine non-trivial collision in $(2A)+(2A)$ with no counterpart in an honest Sidon set. This is exactly why the base-case lemma's hypothesis cannot be verified "automatically" and needs the generic/degenerate split — the pairing-halving argument's entire technical content lives in this verification step, not in the (unchanged) base lemma. - The generic/degenerate split, in general shape. Bounding the block second moment of $kA$ reduces to bounding $|S|$, the number of $A$-tuples of size $h$ whose *cross-difference* between the two halves lands in a fixed-length window. Splitting on whether any index is shared across the two halves: generic tuples (no shared index) convert, by rearranging the cross-difference equality, directly into an equality of two genuine $h$-fold sums of $A$ — so the $B_h$-uniqueness hypothesis *on $A$ itself* forces at most $O(1)$ generic tuples per target value, contributing $O(N)$ total, with no further work. Degenerate tuples (a shared index collapses the cross-difference to a lower-arity pattern, e.g. a bare pairwise difference for $h=4$) form a strictly *smaller*, lower-order instance of the identical counting problem, which is then shown to be *itself* boundable in terms of $|S|$ (e.g. $\binom{|T|}2\le|S|$ for the $h=4$ degenerate count $T$), producing a closed, self-referential quadratic inequality in the unknown bound that solves outright without any new external estimate. - Structurally requires $h$ even. The generic/degenerate split's generic half needs to write the $h$-fold sum as an equality of two genuine $h$-fold sums of $A$ recovered from a *balanced* two-half rearrangement — this rearrangement is available exactly when $h$ splits into two equal integer halves $k+k$. For odd $h$ there is no integer $k$ with $h=2k$, so there is no derived sumset $kA$ to transport the question onto, and (per this wiki's own Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf investigation) no substitute mechanism has been found in the 30 years since Chen's 1996 paper.

Technique

WHEN to reach for this. Use the parity/pairing-halving argument whenever a problem asks for a liminf-density-collapse (or structurally similar "cannot stay dense at every scale") statement about an even-order generalized Sidon set ($B_{2k}$-sequence, $k\ge1$), and an analogous liminf lemma is *already proved* for a lower order (canonically order $2$, via Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant)). It is specifically the right tool when the naive obstacle to reusing the lower-order lemma is that the natural derived object (the $k$-fold sumset $kA$) does not itself satisfy the lower-order uniqueness hypothesis outright — i.e. when a direct reduction fails and the collision structure of the derived object needs its own bespoke verification.

WHY it works (the mechanism). Two independent ideas combine: 1. Reuse, don't reprove, the base lemma. The order-2 (or order-$k$) liminf sandwich lemma — block decomposition + weighted Cauchy–Schwarz, Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant) — is generic: it only needs a bound on the block second moment ("energy") of *whatever* sequence is fed into it. Nothing about it is Sidon-specific, so it applies unchanged to $kA$ once its hypothesis is separately verified. 2. Bootstrap the hypothesis verification via a self-closing recursion. The hard part — bounding the energy of $kA$ — splits into a class controllable *for free* by the *original* $B_h$ hypothesis on $A$ (the generic class, via a direct algebraic rearrangement that exposes a forbidden $h$-fold collision), and a residual class that is not directly controllable but is recognized as a strictly lower-order instance of the same counting problem being solved, closing a quadratic-in-itself inequality with no new external input. This "recursion that closes on itself," rather than an explicit construction or a fresh inequality, is the load-bearing new idea in both Nash's and (by inference) Chen's proofs — it is what makes an $h$-fold uniqueness hypothesis usable as leverage on a $k$-fold ($k=h/2$) derived object.

HOW it is used to prove things (recombination steps, generalized from Nash's $h=4$ proof): 1. Check parity first. Confirm the target order $h$ is even; write $h=2k$. If $h$ is odd, this technique has no known instantiation — do not attempt it (this is exactly the wall Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf sits behind). 2. Establish (or cite) a free starting estimate. An order-$h$ ($h=2k$) uniqueness hypothesis typically implies lower-order uniqueness too (e.g. $B_4\Rightarrow$ Sidon, via the repeated-pair trick above) — extract whatever coarse density bound ($A(N)\ll N^{1/h}$-type) is available for free before the real argument starts; it is used later as an auxiliary factor, not as the theorem itself. 3. Identify the target derived object. Form $kA$ (or, for iterated applications at $h=2^j$, iterate pairwise doubling) and state the reduction algebra explicitly: a liminf bound of the lower-order shape for $kA$ must be shown to *imply*, via a counting inequality relating $(kA)(n)$ to $A(n/k)^k$ (roughly $(kA)(n)\gtrsim A(n/k)^k$), the actual target liminf bound for $A$. 4. Cite the lower-order lemma as a black box. State the generic liminf sandwich lemma (Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant)) exactly as proved for order 2 (or order $k$), with its precise hypothesis (block second moment $\ll N$) — do not modify it. 5. Verify the lemma's hypothesis for the derived object by the generic/degenerate split. Reduce the block-energy bound for $kA$ to bounding a cross-difference count $|S|$ over $h$-tuples of $A$. Partition $S$ by whether any index is shared between the two halves: - Generic (no shared index): rearrange the cross-difference equality into an equality of two genuine $h$-fold $A$-sums; invoke the order-$h$ uniqueness hypothesis directly to get an $O(1)$-per-target-value multiplicity bound, contributing $O(N)$ total — cheap, no further work. - Degenerate (a shared index collapses arity): recognize the resulting count as a lower-order instance $T$ of the identical problem; relate $T$ back to $S$ itself (e.g. $\binom{|T|}2\le|S|$); substitute to get a closed self-referential (typically quadratic) inequality in $|T|$ and/or $|S|$; solve it outright. 6. Chain the reductions back. Hypothesis verified $\Rightarrow$ base lemma applies to $kA$ $\Rightarrow$ step 3's counting algebra converts the $kA$-liminf bound into the target $A$-liminf bound. $\blacksquare$ 7. WHEN this does NOT suffice. The technique gives no purchase on odd $h$ (no balanced two-half split exists) and, even for even $h$, only reaches whatever asymptotic exponent the base lemma reaches (it inherits, does not improve, the base lemma's constant/log-power). It also does not by itself suggest *why* the even/odd asymmmetry should be a genuine mathematical obstruction rather than a limitation of this specific proof strategy — recognizing that gap (a technique-specific ceiling, not necessarily a theorem-level one) is itself useful derivation fuel for attacking Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf: either find a genuinely different (non-pairing) mechanism for odd $h$, or find a reason no such mechanism can exist.

Related

- Nash (1989) — $B_4$-sequence liminf density collapse: $\\liminf_n A(n)\\log^{1/4}n/n^{1/4}<\\infty$ — the fully primary-source-verified $h=4$ instantiation of this technique in complete mechanical detail (every step of the generic/degenerate split and the closing quadratic inequality); the canonical worked example to study before attempting any new application. - Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — the open $h=3$ (odd) case of the same \$500 Erdős/Guy-C11 problem; the exact wall this technique cannot cross, and the page that first flagged this concept slug as the (at the time unverified) load-bearing mechanism in the even-$h$ literature. - Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant) — the order-2 (and order-$k$-shaped) block-decomposition + weighted Cauchy–Schwarz liminf/limsup sandwich lemma that this technique reuses unchanged as a black box; this page's entire contribution is a way to verify that lemma's hypothesis for a derived (sumset) object, not a modification of the lemma itself. - Sidon sets / B_2 sets / Golomb rulers — the $h=2$ base case ($B_2$-sequences); the object whose classical liminf theorem (Erdős/Stöhr/Halberstam–Roth) is the literal base case this whole family of pairing arguments builds on top of. - Additive representation function $r_{B,h}(n)$ — general framework for $r_{B,h}(n)$, the object whose boundedness/uniqueness is being exploited in both the original ($A$, order $h$) and derived ($kA$, order-2-shaped) settings. - B_2[g] sequences — bounded (but not unique) representation, the Sidon relaxation — a different (multiplicity, not order) relaxation axis of the same Sidon/$B_h$ family; contrast with this page's order-halving axis — both are ways of moving between related liminf/density questions in the same cluster, but via structurally different reductions.