Lindström-style shift/collision double-counting (upper-bound method for Sidon sets)

Statement

The technique (as crystallized by Lindström 1969 [Li69], building on Erdős–Turán 1941 [ErTu41]) is a family of *elementary double-counting arguments* for upper-bounding the size of a Sidon set (a.k.a. $B_2$ set: a set $A$ all of whose pairwise sums $a+b$, $a\le b\in A$, are distinct — equivalently, all pairwise differences $a-b$, $a\ne b \in A$, are distinct; see Sidon sets / B_2 sets / Golomb rulers). Every instance of the method has the same two-step shape: (1) partition or re-index the $\binom{|A|}{2}$ pairs of elements of $A$ (by *difference order* or by *shift amount*) so that a *collision-freeness* consequence of the Sidon property forces the pieces to inject into a bounded ambient range; (2) sum/count the pieces two different ways — once as an exact combinatorial count (growing like $|A|^2$), once as a bound coming from the ambient range's size (growing like $N$) — and equate the two to solve for $|A|$.

Variant A — "difference-order" collision counting (Lindström's original argument, [Li69]). Let $A=\{a_1<\cdots<a_k\}\subseteq\{1,\dots,n\}$ be a Sidon set. For $i<j$, call $j-i$ the *order* of the difference $a_j-a_i$. Fix $\ell\approx n^{1/4}$ and sum all differences of order $\le\ell$: $$\sum_{1\le i<j\le k,\ j\le i+\ell} (a_j-a_i).$$ There are $(k-1)+(k-2)+\cdots+(k-\ell) = \ell k - \binom{\ell+1}{2}$ such differences, and — crucially, this is where the Sidon hypothesis is used — they are all *distinct* positive integers $\le n-1$ (distinctness follows because a Sidon set has distinct differences at all; boundedness by order plays no logical role here beyond bookkeeping the *count* of terms). This gives the exact lower bound $\sum \ge 1+2+\cdots+(\ell k - \binom{\ell+1}{2}) \ge \binom{\ell k -\binom{\ell+1}{2}+1}{2}$ (source: BFR21 §2, exact inequality (2.1)). On the other side, the sum of *all* differences of a fixed order $r\le\ell$ telescopes to at most $r\cdot n$ (each order-$r$ difference is at most $n$, and cancellation across the telescoping sum $a_{i+r}-a_i$ bounds the total), so summing over $r=1,\dots,\ell$ gives the upper bound $\binom{\ell+1}{2}n$ (inequality (2.2)). Equating the two bounds and solving the resulting quadratic in $k$, then optimizing $\ell\approx n^{1/4}$, yields $$k < n^{1/2}+n^{1/4}+1.$$ (BFR21 §2, Theorem 2.1, exact proof reproduced with all constants; this is precisely Lindström's 1969 theorem, matching Erdős–Turán's original $n^{1/2}+O(n^{1/4})$ up to the explicit constant.)

Variant B — "shifted-copies" incidence/overlap counting (Ruzsa [Ru98] / Cilleruelo [Ci10], reframed by BFR21 §3 via Johnson's set-system inequality). Let $A\subseteq\{1,\dots,n\}$ be Sidon, $k=|A|$, and for an integer $m$ define $m$ shifted translates $A_i := A+(i-1)$ for $i=1,\dots,m$, each a $k$-subset of $\{1,\dots,n+m-1\}$. Key lemma: any two distinct shifted copies overlap in at most one point, $|A_i\cap A_j|\le1$ for $i\ne j$ — because $x=y$ for $x\in A_i\cap A_j$, $y\in A_i\cap A_j$ with $x\ne y$ would force $a+i=b+j$ and $c+i=d+j$ for $a,b,c,d\in A$, giving $a+d=b+c$ with $\{a,d\}\ne\{b,c\}$, contradicting Sidon. This is exactly a *bounded pairwise-intersection set system* (in the sense of coding theory / hypergraph theory), so Johnson's inequality ($v(\bigcup A_i) \ge k^2m/(tm+k-t)$ for $t$-bounded pairwise intersections, itself proved by a double-counting-of-incidences argument on the "degree" $d_x=|\{i: x\in A_i\}|$: $\sum_i\sum_j|A_i\cap A_j| = \sum_x d_x^2 \ge (\sum_x d_x)^2/v = k^2m^2/v$) applies with $t=1$, and since $\bigcup A_i\subseteq\{1,\dots,n+m-1\}$, one gets $(n+m-1)(m+k-1)\ge k^2m$. Optimizing $m\approx n^{3/4}$ gives $k<n^{1/2}+n^{1/4}+1$ (Cilleruelo's calculation sharpens the additive constant to $+\tfrac12$; BFR21 §3, Theorem 3.2, exact proof reproduced).

Both variants are instances of the same meta-pattern: exploit the Sidon (no-repeated-difference / no-repeated-overlap) hypothesis to get an *injection* from a large, exactly-countable combinatorial family (order-bounded differences in Variant A; pairwise shift-overlaps in Variant B) into a bounded ambient interval of size $O(n)$, then solve the resulting size inequality for $k=|A|$.

Facts

- Origin and chain of results (all sharpening only the $O(n^{1/4})$-order *additive constant*, never the $n^{1/2}$ leading term or the $n^{1/4}$ *exponent*): - Erdős–Turán 1941 [ErTu41], *J. London Math. Soc.* 16(4):212–215 — first proof, $h(N)\le N^{1/2}+O(N^{1/4})$, via an early shift-counting argument (Ben Green notes some later Fourier-analytic re-derivations "have the same spirit," per BFR21 §1). - Lindström 1969 [Li69], *J. Combin. Theory* 6:211–212 — the explicit-constant version $h(N)<N^{1/2}+N^{1/4}+1$ (Variant A above), the canonical textbook form of the argument. - Cilleruelo 2010 [Ci10] — recalculates Ruzsa's shifted-copies argument (Variant B) more carefully, $h(N)<N^{1/2}+N^{1/4}+\tfrac12$. - Balogh–Füredi–Roy 2021, arXiv:2103.15850 (publ. *Amer. Math. Monthly* 130(5), 2023) — combines *both* variants (a "slack term" $C$ in Variant A's telescoping-cancellation bound, provably nonzero, is bounded below and fed back in), obtaining $h(N)<N^{1/2}+0.998N^{1/4}$, the first *genuine* $\Theta(N^{1/4})$-order improvement since 1969/2010. - O'Bryant 2022, arXiv:2207.07800 — a "logically simpler but computationally heavier" variant of the same architecture, $h(N)\le N^{1/2}+0.99703N^{1/4}$. - Carter–Hunter–O'Bryant 2023/2025, arXiv:2310.20032 (publ. *Acta Math. Hungarica* 175:108–126) — "conceptually simple but very computationally intensive" extension (their own abstract's words), current published record $b\le1.96365$, i.e. $h(N)\le N^{1/2}+0.98183N^{1/4}+O(1)$; a hand-verifiable weaker version gives $b\le1.99058$. - Nov 2025 (informal): Terence Tao + Daniel Carter run Google DeepMind's AlphaEvolve directly on the CHO25 admissible-parameter optimization landscape, improving $b$ to $1.9526463099204112$ (terrytao.wordpress.com/2025/11/05, per this wiki's Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets and concept/alphaevolve-cho25-constant-optimization). - Structural ceiling of the whole method. Every result in the chain above is of the shape $N^{1/2}+c\,N^{1/4}+O(1)$ for a shrinking constant $c$; none touches the *exponent* $1/4$. Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets (Erdős's own \$1000 problem) asks whether the error term is $O_\epsilon(N^\epsilon)$ for every $\epsilon>0$ — a qualitatively stronger claim that this entire counting/optimization architecture is, by its own internal logic, structurally incapable of reaching (per this wiki's Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets "Literature state" analysis: the method bounds a telescoping/overlap sum by a *single* real-parameter optimization, which caps out at $\Theta(N^{1/4})$-order savings, not sub-polynomial savings). - Matches Singer's lower-bound leading term exactly. Singer's 1938 finite-field perfect-difference-set construction (Singer finite-field perfect difference set construction) gives $h(N)\ge(1-o(1))N^{1/2}$; the double-counting upper bound $N^{1/2}+O(N^{1/4})$ pins the leading-order asymptotic exactly, leaving only the $N^{1/4}$-scale gap as the 85-year-old open question.

Technique

**Recombination-ready recipe — how to apply this method to a *new* no-repeated-additive-relation problem:**

1. Identify the collision-freeness hypothesis. You need a set $A$ (or family) such that some fixed bounded-arity linear relation among its elements has *at most one* solution up to the trivial symmetries (for Sidon: $a-b=c-d \Rightarrow \{a,b\}=\{c,d\}$). This is the raw material both variants consume. 2. Choose an indexing that turns "at most one solution" into "an injection into a bounded range." Two standard choices, matching Variants A/B above: - Order/telescoping indexing (Variant A): index pairs by a secondary bounded parameter $\ell$ (here, index-gap $j-i$) and sum a *telescoping* quantity (here, the differences themselves) two ways — once by exact term-count (quadratic in $|A|$, using that all values are distinct nonnegative integers so their sum is $\ge\binom{\text{count}+1}{2}$), once by a *cancellation* bound on each telescoping "shell" (linear in the ambient size $n$ per shell, so $O(\ell n)$ total). Optimize the free parameter $\ell$ at the end (here $\ell\approx n^{1/4}$) by calculus on the resulting quadratic-in-$k$ inequality. - Shifted-copy / incidence indexing (Variant B): build $m$ translates $A_i=A+i$ of the same set inside a slightly larger ambient range, show pairwise overlaps are $\le1$ (directly from the collision-freeness hypothesis), then invoke a generic bounded-pairwise-intersection inequality (Johnson's inequality — itself proved by a *second*, nested double-count: $\sum_x d_x^2 \ge(\sum_x d_x)^2/v$ via Cauchy–Schwarz on the "how many copies contain point $x$" degree sequence) to lower-bound the union's size, which is capped by the ambient range. Optimize the free parameter $m$ at the end (here $m\approx n^{3/4}$). 3. Look for slack. Both bounding steps above are typically *not* tight (BFR21's explicit "slack term" $C$ in Variant A, §2.1: the cancellation bound "sum of order-$r$ differences $\le rn$" is loose whenever the difference set has values clustered away from the extremes of $\{1,\dots,n\}$). Any provable *lower bound* on the slack (even $\Omega(n^{5/4})$ suffices, per BFR21 (2.4)) feeds back linearly into an improved constant — this is exactly the mechanism every post-1969 improvement (Cilleruelo, BFR21, O'Bryant, CHO25, AlphaEvolve) exploits, each finding a sharper/computer-searched lower bound on essentially the same slack quantity or a structurally analogous one, without changing the $N^{1/2}+cN^{1/4}$ architecture. 4. WHEN this applies: any extremal problem of the shape "how large can a set/sequence be subject to a fixed bounded-arity linear (or near-linear) non-collision condition, embedded in a bounded ambient range of size $n$" — the two-sided count (exact combinatorial lower bound vs. ambient-range upper bound) is available whenever the non-collision hypothesis lets you exhibit an injection from a quadratic-in-$|A|$-sized family into an $O(n)$-sized target. It transfers directly to $B_h$ ($h\ge3$, distinct $h$-fold sums, Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf) and to $B_h[g]$ sets with bounded multiplicity, with the same two-variant machinery (order-telescoping or shifted-copy-overlap), though the optimal exponents/constants change. 5. WHY it works (the mechanism, for recombination): it is a *sandwich* argument structurally identical in spirit to the slice-rank / polynomial-method sandwich (Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt)) — a single combinatorial quantity is bounded from *below* by exact enumeration (using the non-collision hypothesis to guarantee no double-counting) and from *above* by a coarser, ambient-size-dependent bound (using boundedness/cancellation), and equating the two solves for the extremal parameter. The reason it caps out at $N^{1/2}+\Theta(N^{1/4})$ rather than reaching a sub-polynomial error term is that both the lower bound (a discrete-sum-of-distinct-integers estimate) and the upper bound (a linear-in-range cancellation estimate) are themselves only quadratic-order-tight — closing the gap further would need a genuinely different, non-counting mechanism (per Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets's "Literature state," no such technique is known as of 2026).

Related

- Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — Erdős's \$1000 problem asking for $h(N)=N^{1/2}+O_\epsilon(N^\epsilon)$; this concept page is the technique substrate behind every published upper bound cited there ([ErTu41]→[Li69]→Cilleruelo→BFR21→O'Bryant→CHO25→AlphaEvolve-assisted), and the page where this method's structural ceiling is analyzed in most detail. - Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — the $B_3$ (triple-sum) analogue; the same double-counting architecture generalizes to $h$-fold sums, with different optimal exponents. - Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets — the $B_3$-set density problem more broadly; Green's 2001 Fourier/additive-energy upper bound is a related but mechanistically distinct sibling to this counting technique. - Sidon sets / B_2 sets / Golomb rulers — the central combinatorial object this technique bounds; contains the broader "how Sidon sets are used" recombination toolkit (constructions, applications), of which this page is the dedicated deep-dive on the *upper-bound* half. - Singer finite-field perfect difference set construction — the matching *lower*-bound construction (Singer 1938), pinning the same $N^{1/2}$ leading order that this double-counting method proves as an upper bound. - concept/alphaevolve-cho25-constant-optimization — the live (Nov 2025) AI-assisted numerical-optimization application of this exact technique's free-parameter landscape (Carter–Hunter–O'Bryant's $\tau,\alpha,c_s$ parameters), the most recent link in the 85-year improvement chain. - 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 counting bound) for related no-collision extremal problems.