Singer perfect difference sets / finite-field constructions for Sidon-type lower bounds

Statement

The technique in one sentence: to prove a *lower bound* $f(N)\gtrsim N^{1/h}$ (or similar) for the maximum size of a set in $\{1,\dots,N\}$ avoiding a fixed additive coincidence (repeated difference, repeated $h$-fold sum, etc.), exhibit an explicit subset of a finite field or finite projective space, near the target scale, whose required collision-freeness is an exact algebraic/incidence identity rather than a probabilistic estimate — then transport it from $\mathbb Z_v$ (or $\mathrm{GF}(q^h)$) into $\{1,\dots,N\}$.

Core object — Singer's perfect difference set. For every prime power $q$: let $G=\mathbb F_{q^3}^\ast/\mathbb F_q^\ast$, cyclic of order $v=q^2+q+1$ (the point count of the projective plane $PG(2,q)$). Then $$D=\{x\in G:\mathrm{Tr}_{\mathbb F_{q^3}/\mathbb F_q}(x)=0\}\subset G\cong\mathbb Z_v,\qquad |D|=q+1,$$ is a $(q^2+q+1,\,q+1,\,1)$ perfect difference set: every nonzero residue mod $v$ is realized as $d_1-d_2$ ($d_1,d_2\in D$) in exactly one ordered way. $\lambda=1$ ("perfect"/"planar") is the strongest possible collision-freeness — $D$ is simultaneously a Sidon set *and* uses up all $v-1$ nonzero differences, which forces $v=k^2-k+1$ exactly (no slack). Full statement, projective-plane picture, and trace-kernel proof: Singer finite-field perfect difference set construction.

Generalization used for higher-order lower bounds — Bose–Chowla. For prime power $q$, integer $h\ge2$, primitive element $\alpha$ of $\mathrm{GF}(q^h)$: the set $$A=\{a\in\mathbb Z_{q^h-1}: \alpha^a-\alpha\in\mathrm{GF}(q)\}$$ is a $B_h$ set (all $h$-fold sums distinct) of size $q$ in $\mathbb Z_{q^h-1}$ (Bose–Chowla 1962, restated in arxiv.org/pdf/2104.12711). $h=2$ recovers a variant of the Singer/perfect-difference-set Sidon lower bound; general $h$ gives a lower bound of order $q\approx N^{1/h}$ for the $B_h$-set extremal function.

Facts

- **Why it gives a matching lower bound, not just *a* lower bound: $k=q+1\approx\sqrt v$, and the elementary pigeonhole bound (every Sidon set in $\mathbb Z_v$ has $k(k-1)\le v-1$) shows $O(\sqrt v)$ is already the ceiling — so Singer's construction is not a probabilistic near-optimum, it is an exact algebraic optimum up to lower-order terms**. This is the single most important fact for reuse: whenever a problem's *upper* bound comes from a one-line double-counting/pigeonhole argument on differences (or $h$-fold sums), a perfect-difference-set-type construction is the natural candidate to *match* it in leading order. - The mechanism is incidence, not counting. In $PG(2,q)$, "two points determine a unique line" (dually: any two points lie on exactly one common translate of a fixed line) *is literally* the $\lambda=1$ difference-set identity once points are labeled by a cyclic ("Singer cycle") group action coming from $\mathbb F_{q^3}^\ast$ being cyclic. No union bound, no second moment — the extremal property is baked into projective-plane axioms. See Finite-field / projective-plane constructions for extremal additive sets "Flavor A" for the general pattern (incidence transport vs. Weil-bound/root-count transport). - Existence is restricted to prime powers, but that's not a practical obstruction. The construction needs $q$ a prime power. Because prime powers (in fact primes) are dense at every scale, one always picks $q\approx\sqrt N$ (or $q^{h-1}\approx N^{1/h}$ for Bose–Chowla) and loses only a lower-order term transporting $\mathbb Z_v\to\{1,\dots,N\}$. - The "perfect" (λ=1) property is strictly stronger than Sidon, and that gap is real, not cosmetic. Erdős conjectured (1976, in a dozen+ papers over two decades) that every finite Sidon set *extends* to a perfect difference set — this converse direction is false: Alexeev–Mixon, "Forbidden Sidon subsets of perfect difference sets, featuring a human-assisted proof," arXiv:2510.19804 (PNAS, 2026) give explicit finite counterexamples (e.g. $\{1,2,4,8,13\}$, rediscovering an earlier Hall counterexample) — Sidon-ness does not imply embeddability in a Singer-type perfect difference set. Useful caution when trying to *use* a known Sidon set as a stepping stone toward a perfect difference set: the implication only runs one way (perfect $\Rightarrow$ Sidon), not the reverse. - Prime-power conjecture (converse existence question, open): conjectured that perfect difference sets mod $n^2+n+1$ exist *only* for $n$ a prime power, i.e. Singer's family is conjectured to be *all* of them; verified computationally to $2\times10^9$ (Baumert–Gordon) and $n=10$ ruled out by exhaustive search (Lam–Thiel–Swiercz 1989), but open in general. Peluse (arXiv:2003.04929, Math. Ann. 380 (2021)) proved the asymptotic-density version: $\#\{n\le N:$ a perfect difference set mod $n^2+n+1$ exists$\}\sim N/\log N$. - Machine-verified: the Sidon-set special case is formalized end-to-end with zero sorrys in Lean 4 — "for every prime power $q=p^k$ there exists a Sidon set modulo $q^2+q+1$ of cardinality $q+1$" (Hulak, Ramos, de Queiroz, arXiv:2605.03274, "Formalizing Singer Sidon Constructions and Sidon Set Infrastructure in Lean 4").

HOW to use this as derivation fuel (recombination recipe for a lower bound)

1. Recognize the shape: the target problem asks "how large can a subset of $\{1,\dots,N\}$ (or $\mathbb Z_N$) be while avoiding a repeated additive coincidence of bounded type $h$" — repeated difference ($h=2$, Sidon/$B_2$), repeated $h$-fold sum ($B_h$, $h\ge3$), or a related bounded-multiplicity variant ($\gamma$-Golomb ruler). The matching upper bound is typically a one-line counting/pigeonhole identity: $\binom{k}{2}\lesssim N \Rightarrow k=O(N^{1/h})$-type. 2. Pick a prime power $q$ near the target scale: $q\approx N^{1/2}$ for Sidon/$B_2$; $q^{h-1}\approx N$, i.e. $q\approx N^{1/(h-1)}$, for Bose–Chowla $B_h$ (giving output size $\approx q\approx N^{1/h}$ after the correct normalization — check the exact exponent against the specific $h$). 3. Build the explicit set either as (a) the trace-zero coset $\{x\in\mathbb F_{q^3}^\ast/\mathbb F_q^\ast:\mathrm{Tr}(x)=0\}$ (Singer, $h=2$) or (b) the discrete-log coset $\{a: \alpha^a-\alpha\in\mathrm{GF}(q)\}$ in $\mathbb F_{q^h}$ (Bose–Chowla, general $h$) — both are fully explicit, poly-time-computable, finite-field-arithmetic-only constructions. 4. Certify collision-freeness algebraically, not probabilistically: for Singer, invoke the projective-plane incidence axiom (two points/one line); for Bose–Chowla, invoke that a nonzero low-degree polynomial over $\mathbb F_{q^h}$ has few roots, so a coincidence between two $h$-tuples forces a polynomial identity that fails generically. 5. Transport to $\{1,\dots,N\}$: take coset/interval representatives of $D\subset\mathbb Z_v$ in $\{0,\dots,v-1\}\subset\{1,\dots,N\}$; because the difference/sum property is exact (not approximate) mod $v$, it survives unchanged as an integer property, giving a lower bound of $(1-o(1))N^{1/h}$ — usually *matching* the counting upper bound in leading order (a rarity among explicit, non-probabilistic constructions; see Finite-field / projective-plane constructions for extremal additive sets for why this "explicit beats probabilistic" outcome is unusual in extremal combinatorics generally). 6. Check whether you need "perfect" ($\lambda=1$) or merely "Sidon" ($\lambda\le1$). If the target problem only needs a large collision-free set, the weaker Sidon property already suffices and Singer's construction over-delivers; if the target problem specifically needs *every* difference realized (a genuinely "complete" design, e.g. for a combinatorial-design or coding-theory application), you need the full perfect-difference-set property, and should not substitute a merely-Sidon set (per the Alexeev–Mixon non-equivalence above). 7. **When it does *not* directly apply: - Infinite sequences**: Singer/Bose–Chowla are single-interval, finite constructions; they do not by themselves give improved *infinite* Sidon-type sequence densities. That regime needs gluing finite Singer blocks (Cilleruelo's discrete-log analogue, arXiv:1209.0326) or a genuinely different multiplicative-to-additive log trick (Ruzsa 1998) — see Sidon sets / B_2 sets / Golomb rulers Technique §3, Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set. - Unbounded-order patterns (arbitrarily long APs, general Szemerédi-type statements): not amenable — that's Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt) territory, a mechanistically different (tensor-rank/density-increment) toolkit. - Non-prime-power target scale exactly: the construction only exists at prime-power $v$; for a scale that must be hit *exactly* (not just approximated), you need either a "round to nearest prime power" transport (costing a lower-order term) or a different technique entirely. - Wanting the converse (does a given Sidon set extend to / embed in a perfect difference set?): false in general (Alexeev–Mixon).

WHEN it applies: any lower-bound half of a Sidon/$B_h$/Golomb-ruler-type extremal problem, or more generally any "avoid a fixed bounded-order additive coincidence, at an explicit computable scale" problem where the matching upper bound comes from a counting/incidence identity that a finite-field incidence structure can mirror exactly.

Related

- Singer finite-field perfect difference set construction — the full historical/existence-focused writeup of Singer's 1938 theorem (statement, proof idea, prime-power conjecture, Lean formalization); this page is the technique-extraction companion. - Finite-field / projective-plane constructions for extremal additive sets — the umbrella family (Singer, Bose–Chowla, polarity graphs, Weil-bound constructions) this page's recipe is one instance of; explains the general "Flavor A (incidence) vs Flavor B (root-count/Weil)" mechanism split. - Sidon sets / B_2 sets / Golomb rulers — the central combinatorial object (Sidon/$B_h$/Golomb ruler) this technique produces extremal lower-bound examples for. - Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — sharp Sidon-set-size asymptotics $h(N)=N^{1/2}+O_\epsilon(N^\epsilon)$; Singer's construction supplies the matching-leading-term lower bound $h(N)\ge(1-o(1))N^{1/2}$. - Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets — $B_3$-set asymptotics; Bose–Chowla's generalization gives the $(1-o(1))N^{1/3}$ lower bound, matched by Green's 2001 Fourier upper bound. - Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — $B_3$/triple-sum density, same finite-field construction lineage. - Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — infinite Sidon sequence density; finite Singer/Bose–Chowla blocks are the raw material for the best known infinite constructions (Ruzsa, Cilleruelo), but need an extra gluing technique. - Erdős #1191 — how small can an infinite Sidon set's liminf density be? — liminf-oscillation for infinite Sidon sets; O'Bryant's 2026 $\gamma$-Golomb-ruler generalization of the same block-energy/construction lineage. - Erdős #552 — Ramsey number R(C4,Sn), dip below n+√n? — polarity-graph (dual/orthogonal-form) use of the same $PG(2,q)$ object for $C_4$-free extremal graphs rather than Sidon sets. - erdos/723 — existence of finite projective planes of non-prime-power order; the open structural sibling to the prime-power conjecture. - Alexeev, Mixon, "Forbidden Sidon subsets of perfect difference sets, featuring a human-assisted proof," arXiv:2510.19804 (PNAS, 2026) — disproves Erdős's 1976 conjecture that every Sidon set extends to a perfect difference set. - Bose, Chowla, "Theorems in the additive theory of numbers," Comment. Math. Helv. 37 (1962), 141–147; recap in arxiv.org/pdf/2104.12711 ("The Bose-Chowla argument for Sidon sets"). - Singer, J., "A theorem in finite projective geometry and some applications to number theory," Trans. Amer. Math. Soc. 43 (1938), 377–385. - Hulak, Ramos, de Queiroz, "Formalizing Singer Sidon Constructions and Sidon Set Infrastructure in Lean 4," arXiv:2605.03274 (May 2026) — zero-sorry machine-checked version of the $h=2$ construction.