Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant)

Statement

The technique, in one sentence: to bound a global additive-extremal quantity for a set with a *bounded local collision* property (Sidon-type: some difference/sum representation function $r_A(\cdot)\le\gamma$ pointwise), partition the ambient range into blocks of a tunable length $N$, form the energy $E:=\sum_\ell F_\ell^2$ of the block-counts $F_\ell:=|A\cap\text{block }\ell|$, bound $E$ from above using only the collision hypothesis (a pigeonhole/double-counting argument, quadratic in $F_\ell$ but linear in the collision budget), bound $E$ from below using weighted Cauchy–Schwarz ($\sum_\ell F_\ell^2 \ge (\sum_\ell w_\ell F_\ell)^2/\sum_\ell w_\ell^2$ for any weights $w_\ell$, chosen to match the density profile being tested), then equate the two bounds and solve for the extremal constant. The block length $N$ (and, in the asymptotic form, the weight profile $w_\ell$) is the free parameter optimized at the end.

**Canonical finite-$N$ instantiation (Erdős–Turán 1941; restated as Theorem 4, Ch. II of Halberstam & Roth's *Sequences*, 1966/1983). For a Sidon set $S\subseteq\{1,\dots,n\}$ of maximum size, set (sliding-window version) $A_u:=|S\cap[u-n^{3/4},\,u)|$ for $u$ ranging over $\mathbb Z$. Bound $\sum_u\binom{A_u}{2}$ two ways: - Upper bound (pure combinatorics from the Sidon hypothesis): a pair $(s_i,s_j)\in S\times S$ contributes to $\binom{A_u}2$ only if both lie in a common window, and is uniquely determined by the difference $s_i-s_j$ (Sidon $\Rightarrow$ distinct differences), so the total contribution across all windows is $O(n)$. - Lower bound** (Cauchy's inequality/convexity): for fixed total $\sum_u A_u\approx|S|\cdot n^{3/4}$, $\sum_u\binom{A_u}2\ge\binom{|S|}2\cdot(\text{window length})/n \gtrsim |S|^2 n^{-1/4}$ by Cauchy–Schwarz applied to the $A_u$ values.

Equating gives $h(n)\le n^{1/2}+O(n^{1/4})$ — the historical origin of the whole family (see Lindström-style shift/collision double-counting (upper-bound method for Sidon sets) for the closely related but logically distinct Lindström/telescoping-differences variant of this same finite-$N$ result, which sharpens the constant further).

Canonical infinite/asymptotic instantiation (O'Bryant, arXiv:2606.28651, 2026, Theorem 1 — the definitive modern write-up of the method). Let $\gamma\ge1$ be an integer and $\mathcal A\subseteq\mathbb Z_{\ge0}$ a $\gamma$-Golomb ruler: every $d>0$ has at most $\gamma$ pairs $(a,b)\in\mathcal A\times\mathcal A$ with $a-b=d$ (Sidon set $=\gamma=1$; see $\gamma$-Golomb rulers (bounded-multiplicity difference sets generalizing Sidon sets)). Write $A(n):=|\mathcal A\cap[0,n)|$, $\psi(n):=\log(en)$. Then $$\liminf_{n\to\infty}\frac{A(n)}{\sqrt{n/\log n}}\ \le\ \frac{2}{\sqrt{\log 2}}\sqrt\gamma\ \approx\ 2.402\sqrt\gamma.$$ The proof (full mechanics reproduced in $\gamma$-Golomb rulers (bounded-multiplicity difference sets generalizing Sidon sets) Technique §, summarized in the Technique section below) is the block-decomposition + weighted-Cauchy–Schwarz energy argument in its most refined, explicitly-optimized-weight form. A companion, weight-free (simpler) instance of the same architecture — "closely follow[ing] that given in Halberstam & Roth" per O'Bryant's own text — gives Theorem 2: $\limsup_n A(n)/\sqrt n\le\sqrt\gamma$, matching (for $\gamma=1$) the classical Erdős ($1/2$) $\to$ Krückeberg ($2^{-1/2}$) constant chain, i.e. Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set?.

Facts

- Attribution chain, verbatim from the primary source. O'Bryant (arXiv:2606.28651, §1 and §3-4) states: "Erdős [1955.Stohr] proved finiteness for Sidon sets, and Cilleruelo [2015.Cilleruelo-a] proved $8\sqrt7\approx21.2$... We bring the constant down to $2/\sqrt{\log2}\approx2.4$." For the companion limsup bound: "a counterpart to Theorem 1 that also originates with Erdős [1955.Stohr], who gave the constant $\tfrac12$. This was improved by Krückeberg to $2^{-1/2}$... This proof closely follows that given in Halberstam & Roth [1966.Halberstam&Roth]." I.e. the exact chain **Erdős (unpublished, reported by Stöhr 1955) → Halberstam & Roth (*Sequences*, 1966, rigorous published proof) → Cilleruelo (2015, explicit constant for the liminf side) → O'Bryant (2026, sharpened constant + $\gamma$-generalization) is the literal historical lineage this technique's name encodes. - The finite-$N$ (Erdős–Turán/Lindström) and infinite/asymptotic (Erdős–Stöhr/Halberstam–Roth/O'Bryant) instantiations are mechanistically siblings, not identical: both use a window/block + second-moment ("energy") + Cauchy–Schwarz-lower / collision-upper** sandwich, but the finite-$N$ form (Erdős–Turán 1941, and its Lindström-1969/BFR21/O'Bryant-2022/CHO25 refinement chain documented in Lindström-style shift/collision double-counting (upper-bound method for Sidon sets)) targets a *single extremal count* $h(N)$ for one fixed $N$, while the infinite/asymptotic form (this page's Theorem 1/2) targets a *liminf/limsup ratio* as $N\to\infty$, requiring the extra ingredient of a weight profile $w_\ell$ tuned to the target growth-rate normalization ($\sqrt{n/\log n}$ vs. plain $\sqrt n$) rather than uniform block-counting. Do not conflate the two pages: Lindström-style shift/collision double-counting (upper-bound method for Sidon sets) is the finite-extremal-count sibling; this page is the asymptotic-oscillation sibling. - Both bounds in O'Bryant's Theorem 1 proof come from exactly one use each of the collision hypothesis and of Cauchy–Schwarz — the upper bound on energy (Line (6), $E\le\gamma N+o(N)$) uses *only* the $\gamma$-Golomb property (via $\sum_\ell\binom{F_\ell}2\le\gamma(N-1)/2$, itself an averaged pigeonhole count over offsets $t\in[0,N)$); the lower bound (Line (9)) uses *only* Cauchy's inequality plus the definition of $\tau_N:=\inf_{n\ge N}A(n)\sqrt{\psi(n)/n}$ (the very quantity being bounded). No other machinery (Fourier analysis, entropy, probabilistic method) is used in this proof — it is a genuinely elementary (if delicately optimized) argument. - The weight choice is the tunable "knob." O'Bryant uses $w_\ell:=(\ell\,\psi(\ell N))^{-1/2}$ for Theorem 1 (targeting the $\sqrt{n/\log n}$ profile) but a simpler, unweighted argument for Theorem 2 (targeting plain $\sqrt n$, following Halberstam–Roth directly). This confirms the general recipe: the block/collision half of the argument is generic; the weight profile is retargeted per the specific asymptotic normalization under test. - The method's author explicitly believes it is exhausted for this specific constant. O'Bryant's §3.1 "Nonrigorous thoughts": "We believe that we have fully optimized this argument," followed by speculation (without proof) that further improvement needs a genuinely different mechanism — a reverse-martingale reformulation (block-truncation "is (up to normalization) that of taking the conditional expectation of the indicator function of $\mathcal A$ relative to the $\sigma$-algebra generated by $\{[T+iN,T+(i+1)N):i\ge0\}$") or an entropy-inequality analogue with entropy replacing energy. This is a rare, dated (2026), primary-source signal of a technique's self-diagnosed ceiling. - Sibling weighted-second-moment arguments exist for finite $B_h[g]$ upper bounds (Cilleruelo, "New upper bounds for finite $B_h$ sequences," building on Cilleruelo–Ruzsa–Trujillo, J. Number Theory 2002): a combinatorial identity (their Lemma 2.1) relates $\sum_h d_A(h)(H-h)$ (a weighted difference-count over a sliding window of length $H$) to $\sum_n(A(n)-A(n-H)-\mu)^2$ (a windowed variance/energy term), and Cauchy's inequality converts a *lower* bound on the $L^1$-type sum $\sum_n|A(n)-A(n-H)-\mu|$ (obtained via Fourier/exponential-sum estimates on the Dirichlet-kernel expansion of $B_h$-representation counts) into a lower bound on this $L^2$/energy term — the same window+energy+Cauchy–Schwarz shape as the finite Erdős–Turán argument, applied one level up ($B_h$, $h\ge2$, rather than pairwise differences). This confirms the block/window-energy-Cauchy–Schwarz pattern is a recurring engine across the whole Sidon/$B_h[g]$ literature, not a one-off trick.

Technique

Recombination-ready recipe — how to apply this method to a new bounded-local-collision extremal problem:

1. Identify the collision/multiplicity hypothesis. You need a representation function $r_A(\cdot)$ (differences, sums, or any bounded-arity linear pattern) with a pointwise bound $r_A(d)\le\gamma$ for all $d$. This is the *only* place the specific combinatorial structure of the problem enters. 2. Partition into blocks of tunable length $N$. Choose an offset $T$ (typically by averaging over all offsets $t\in[0,N)$ and selecting one attaining at most the average) and split the range into consecutive blocks $[T+(\ell-1)N,\,T+\ell N)$; let $F_\ell:=|A\cap\text{block }\ell|$. 3. Upper-bound the energy $E:=\sum_\ell F_\ell^2$ using only the collision hypothesis. Convert $F_\ell^2=2\binom{F_\ell}2+F_\ell$; bound $\sum_\ell\binom{F_\ell}2$ by counting, for each possible difference/pattern value $d<N$, at most $\gamma$ contributing pairs, each counted across at most $N-d$ block-offset choices — this gives a bound linear in $\gamma N$ (a pure double-counting/pigeonhole step, no Cauchy–Schwarz here). Add back the linear term $\sum_\ell F_\ell$ (bounded via a separate, cruder finite-extremal-count lemma, e.g. $\gamma$-Golomb rulers (bounded-multiplicity difference sets generalizing Sidon sets)'s Lemma 3, giving $o(N)$). 4. Lower-bound the same energy via weighted Cauchy–Schwarz, $E\ge(\sum_\ell w_\ell F_\ell)^2/\sum_\ell w_\ell^2$, for a weight sequence $w_\ell$ chosen to match the target asymptotic normalization (e.g. $w_\ell=(\ell\,\psi(\ell N))^{-1/2}$ to target $A(n)\sim\sqrt{n/\log n}$). Bound the denominator $\sum w_\ell^2$ above by an integral-comparison/calculus argument; bound the numerator below by Abel summation (summation by parts, converting a sum over $F_\ell=a_\ell-a_{\ell-1}$ into a sum over $a_\ell$ weighted by $w_\ell-w_{\ell+1}$) combined with the *definition* of the very liminf/limsup quantity under study — this is the step that closes the logical loop and is why the method proves a self-referential bound on $\tau_N:=\inf_{n\ge N}A(n)/(\text{target profile})$. 5. Equate the two energy bounds, let $N\to\infty$ (through a subsequence if needed), and solve the resulting inequality (typically quadratic in the extremal constant) for the sharpest achievable value. 6. WHEN this technique applies: any problem of the shape "how thin/oscillatory can a set with a bounded-multiplicity local additive-collision property be, relative to a fixed target density profile ($\sqrt n$, $\sqrt{n/\log n}$, or similar)" — for *asymptotic* (liminf/limsup, not fixed-$N$) questions specifically. For fixed-$N$ extremal counting (e.g. "what is $h(N)$ exactly"), the sibling finite double-counting technique (Lindström-style shift/collision double-counting (upper-bound method for Sidon sets)) is the right tool and is typically sharper for that purpose. 7. WHEN it does NOT apply / known ceiling: the technique bounds only a *fixed constant* in a liminf/limsup inequality — it structurally cannot, by itself, prove the constant is forced to $0$ or resolve a "does there exist a set with property $X$" existence question requiring more than a single real-parameter (weight-profile) optimization (cf. Erdős #1191 — how small can an infinite Sidon set's liminf density be?'s two open sub-questions, neither touched by this method). Per the method's most recent user (O'Bryant, 2026), reaching further plausibly requires swapping the sandwich's second half from Cauchy–Schwarz to an entropy or reverse-martingale inequality — a genuinely different, not-yet-executed technique. 8. WHY it works (mechanism): it is a two-sided sandwich, structurally analogous to the polynomial-method / slice-rank sandwiches (Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt)) but built from elementary inequalities instead of algebra: the collision hypothesis gives a *cheap, purely combinatorial* upper bound on a quadratic quantity (energy), while Cauchy–Schwarz is the sharp, generic tool for converting a *linear* (weighted-sum) lower bound — itself derived from whatever growth/density hypothesis is under test — into a matching *quadratic* lower bound on the same energy. Because both halves bound the *same* quantity $E$, equating them directly solves for the extremal parameter without needing to separately estimate either side in isolation.

Related

- Erdős #1191 — how small can an infinite Sidon set's liminf density be? — Erdős's \$1000 liminf-oscillation problem for infinite Sidon sets (Stöhr 1955 origin); this technique's exact modern instantiation (O'Bryant Theorem 1) gives the current best explicit constant $2/\sqrt{\log2}\approx2.402$, but resolves neither of the problem's two actual sub-questions — flagged by its own author as needing a different technique to progress further. - Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set? — the limsup companion problem; the simpler, unweighted instance of this same architecture (O'Bryant Theorem 2, following Halberstam–Roth directly) gives the two-sided bound $\sqrt{\gamma/2}\le\limsup A(n)/\sqrt n\le\sqrt\gamma$. - Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — the finite Sidon-set sharp-asymptotics problem $h(N)=N^{1/2}+O_\epsilon(N^\epsilon)$; historically the *first* problem this general block/window+Cauchy–Schwarz family was invented for (Erdős–Turán 1941), though the modern record-holding proofs there use the more refined telescoping/shifted-copies variant, see Lindström-style shift/collision double-counting (upper-bound method for Sidon sets). - Lindström-style shift/collision double-counting (upper-bound method for Sidon sets) — the closely related but logically distinct *finite-$N$* sibling technique (Lindström/Ruzsa/Cilleruelo/Balogh–Füredi–Roy/O'Bryant/Carter–Hunter–O'Bryant chain) for the fixed-$N$ extremal count $h(N)$, as opposed to this page's asymptotic liminf/limsup form. - $\gamma$-Golomb rulers (bounded-multiplicity difference sets generalizing Sidon sets) — the object this page's canonical modern instantiation (O'Bryant 2026, Theorem 1/2) is about; contains the fullest line-by-line reproduction of the proof mechanics for that specific instantiation. - Sidon sets / B_2 sets / Golomb rulers — the $\gamma=1$ special case of the $\gamma$-Golomb-ruler object this technique bounds; general background on Sidon sets as a proof gadget. - Finite-field / projective-plane constructions for extremal additive sets / Singer finite-field perfect difference set construction — the matching *constructive* (lower-bound) counterpart technique family; this page's technique is exclusively an *impossibility*/upper-bound tool and always needs to be paired with a construction to pin down a sharp two-sided answer. - Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt) — a mechanistically different but philosophically parallel two-sided-sandwich technique (algebraic tensor-rank bound vs. this page's combinatorial energy/Cauchy–Schwarz bound) for related no-collision extremal problems. - AlphaEvolve — LLM-guided evolutionary search over verifier-checked numeric parameter spaces — flagged in this wiki (concepts/alphaevolve-constant-optimization.md, concepts/golomb-rulers.md) as a never-yet-attempted transplant target: numerically/evolutionarily searching over alternative weight profiles $w_\ell$ in step 4 above, the one genuinely free real-valued knob in this technique.