Singer finite-field perfect difference set construction

Statement

Definition ((v,k,λ)-difference set). Let $G$ be a group of order $v$. A subset $D\subseteq G$ with $|D|=k$ is a $(v,k,\lambda)$-difference set if every non-identity element $g\in G$ can be written as $g=d_1d_2^{-1}$ (equivalently $d_1-d_2$, additively) for exactly $\lambda$ ordered pairs $(d_1,d_2)\in D\times D$. Counting pairs forces the parameter identity $k(k-1)=\lambda(v-1)$. A difference set with $\lambda=1$ is called planar or perfect — every nonzero group element arises as a difference in *exactly one* way, so $D$ is simultaneously a Sidon set ($B_2$ set) and "complete" (uses up all $v-1$ nonzero differences), which forces $v=k^2-k+1$.

Singer's theorem (1938). For every prime power $q$ and integer $n\ge1$, let $V=\mathbb F_{q^{n+1}}$ regarded as an $(n+1)$-dimensional vector space over $\mathbb F_q$, and let $PG(n,q)$ be the associated $n$-dimensional projective space over $\mathbb F_q$ (points = 1-dim subspaces of $V$). The multiplicative group $\mathbb F_{q^{n+1}}^\ast$ is cyclic of order $q^{n+1}-1$; let $\sigma$ be multiplication by a generator (primitive root) of $\mathbb F_{q^{n+1}}^\ast$. Then $\sigma$ induces a single cyclic permutation (the Singer cycle) of the $v=(q^{n+1}-1)/(q-1)$ points of $PG(n,q)$ that acts simply transitively on them — i.e. $PG(n,q)$'s point set can be identified with $\mathbb Z/v\mathbb Z$ via one $\sigma$-orbit. Under this identification, the points lying on any *fixed hyperplane* of $PG(n,q)$ form a subset $D\subset\mathbb Z/v\mathbb Z$ that is a $$\left(\frac{q^{n+1}-1}{q-1},\ \frac{q^n-1}{q-1},\ \frac{q^{n-1}-1}{q-1}\right)\text{-difference set.}$$ Equivalently (trace-map construction): with $G=\mathbb F_{q^{n+2}}^\ast/\mathbb F_q^\ast$ (cyclic of order $v=(q^{n+2}-1)/(q-1)$) and $\mathrm{Tr}=\mathrm{Tr}_{\mathbb F_{q^{n+2}}/\mathbb F_q}$, the set $D=\{x\in G:\mathrm{Tr}(x)=0\}$ is such a difference set (en.wikipedia.org/wiki/Difference_set).

**Planar / perfect case ($n=2$, i.e. hyperplanes = lines of the projective *plane* $PG(2,q)$). Taking $n=2$ gives $\lambda=1$: for every prime power $q$, $D\subset\mathbb Z/(q^2+q+1)\mathbb Z$ has size $q+1$ and is a perfect difference set** — every nonzero residue mod $q^2+q+1$ is a difference of two elements of $D$ in *exactly one* way. This is the classical "Singer difference set" most often meant by the name, and it is simultaneously (a) the incidence structure of the finite projective plane of order $q$ (a symmetric $2$-$(q^2+q+1,q+1,1)$ design), and (b) a maximum-size Sidon set mod $q^2+q+1$.

Facts

- Source: J. Singer, "A theorem in finite projective geometry and some applications to number theory," Trans. Amer. Math. Soc. 43 (1938), 377–385 (identified via WebSearch/typeset.io citation record, 752 citations). - Prime-power conjecture: it is conjectured that a perfect difference set of order $n$ (i.e. in $\mathbb Z/(n^2+n+1)\mathbb Z$, size $n+1$) exists *only if* $n$ is a prime power — i.e. Singer's construction is conjectured to produce all perfect difference sets. Verified computationally for all $n$ up to $2\times10^9$ (Baumert–Gordon, per WebSearch synthesis of encyclopediaofmath.org). The conjecture itself remains open, but Peluse (2021, arXiv:2003.04929, Math. Ann. 380) proved an asymptotic version: the number of $n\le N$ for which $\mathbb Z/(n^2+n+1)\mathbb Z$ contains *any* perfect difference set is $\sim N/\log N$ — i.e. asymptotically, almost all perfect-difference-set moduli that occur are (conjecturally, and provably in density) exactly the prime-power ones Singer's theorem produces. - Optimality for Sidon sets mod $m$: a $(v,k,1)$ perfect difference set with $v=q^2+q+1$, $k=q+1$ has $k\approx\sqrt v$ — this is the best possible order of growth for a Sidon set in $\mathbb Z/v\mathbb Z$ (a Sidon set mod $v$ has size $O(\sqrt v)$ by the same double-counting identity $k(k-1)\le v-1$ used above), so Singer's construction is asymptotically optimal, not just a valid example. - Lean 4 formalization: Hulak, Ramos, de Queiroz, "Formalizing Singer Sidon Constructions and Sidon Set Infrastructure in Lean 4" (arXiv:2605.03274, May 2026) gives a zero-sorry machine-checked proof of "for every prime power $q=p^k$ there exists a Sidon set modulo $q^2+q+1$ of cardinality $q+1$," built from a primitive element of $GF(q^3)$ and the trace map $GF(q^3)\to GF(q)$ — this is the modern, fully-verified restatement of Singer's 1938 construction. - **This wiki's own Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets** already cites Singer's construction as the source of the *matching lower-order-term* lower bound in the classical Sidon-set-size problem: $h(N)\ge(1-o(1))N^{1/2}$ (Erdős–Turán [ErTu41] give the matching upper bound $h(N)\le N^{1/2}+N^{1/4}+1$), making Singer's theorem the load-bearing *construction* half of a sandwich whose *impossibility* half is a separate double-counting argument.

Technique

WHY it works (the mechanism). The key structural fact is that the multiplicative group $\mathbb F_{q^{n+1}}^\ast$ is *cyclic*, and Frobenius/scalar multiplication by a primitive root acts on the $\frac{q^{n+1}-1}{q-1}$ one-dimensional subspaces (= points of $PG(n,q)$) as a single cycle of that exact length — this is what makes $PG(n,q)$'s point set identifiable with $\mathbb Z/v\mathbb Z$ at all. Once that identification is fixed, *any* fixed hyperplane's point-set automatically inherits the difference-set property "for free," because the projective plane's own incidence axiom — two distinct points determine a unique line, equivalently two distinct hyperplanes meet in a unique codimension-2 flat, equivalently (dually) any two points lie on exactly $\lambda$ common translates of the hyperplane — is *exactly* the difference-set counting identity, transported along the cyclic group action. In the $n=2$ (planar) case, "two points determine a unique line" *is* $\lambda=1$: perfectness of the difference set is a direct translation of the fundamental axiom of projective planes.

HOW to use it to prove things (recombination steps)

1. Need: a lower bound / existence construction for a dense Sidon-type set ($B_2$ set, or more generally a set with all pairwise differences distinct or a bounded-multiplicity, i.e. $\gamma$-Golomb-ruler) inside $\mathbb Z/v\mathbb Z$ or $\{1,\dots,N\}$. 2. Pick a prime power $q$ with $q^2+q+1\approx v$ (primes are dense enough, by Bertrand-postulate-type gaps, that a suitable $q$ always exists close to any target scale — this is the routine "approximate by nearby prime power" step used to transfer the exact-modulus construction to an arbitrary interval $[1,N]$). 3. Construct $D\subset\mathbb Z/(q^2+q+1)\mathbb Z$, $|D|=q+1$, via the trace-zero coset trace $\mathrm{Tr}_{\mathbb F_{q^3}/\mathbb F_q}(x)=0$ on $\mathbb F_{q^3}^\ast/\mathbb F_q^\ast$ (or the projective-line-of-$PG(2,q)$ orbit description) — this is a fully explicit, polynomial-time-computable set (finite-field arithmetic only). 4. Transport to $\{1,\dots,N\}$: take a set of coset/interval representatives of $D$ in $\{0,\dots,q^2+q\}\subset\{1,\dots,N\}$; because $D$ is perfect (every nonzero residue hit exactly once), the representative set is automatically Sidon *as integers*, not just mod $v$ — giving a Sidon subset of $\{1,\dots,N\}$ of size $(1-o(1))\sqrt N$, matching the Erdős–Turán upper bound's leading term. 5. **When it does *not* directly apply**: Singer's construction gives the *finite*, single-interval extremal Sidon set — it does not by itself give improved *infinite* Sidon sequences (that needs a different, probabilistic/greedy or discrete-log-based technique, e.g. Ruzsa's construction, Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set) nor does it resolve whether every finite Sidon set *extends* to a perfect difference set (false in general — Alexeev–Mixon, arXiv:2510.19804, give explicit finite counterexamples, e.g. $\{1,2,4,8,13\}$, showing the converse direction of "Sidon set $\to$ Singer difference set" fails).

WHEN it applies: whenever the target modulus/interval size can be written (or approximated by) $q^{n+1}-1)/(q-1)$ for a prime power $q$ — most usefully the planar case $v=q^2+q+1$ for Sidon-set / $B_2$-set problems, but the same cyclic-Singer-cycle mechanism generalizes to any $n$, giving $(v,k,\lambda)$-difference sets with $\lambda=\frac{q^{n-1}-1}{q-1}>1$ for higher-dimensional projective spaces (used in coding theory / cyclic-code constructions beyond the pure-Sidon setting, not the main focus of the erdős-problems corpus here but the source of the general parameter family).

Related

- Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — the classical Sidon-set-size problem $h(N)=N^{1/2}+O_\epsilon(N^\epsilon)$; Singer's construction is cited there as the exact source of the matching-leading-term lower bound $h(N)\ge(1-o(1))N^{1/2}$, alongside the Lean formalization arXiv:2605.03274. - Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — infinite Sidon sequences; Singer's construction is explicitly a *finite*-interval technique and does not transfer to give the (still-open, non-finite-computation) infinite-sequence growth-rate problem; the record there (Ruzsa's $x^{\sqrt2-1+o(1)}$) uses a different discrete-log-based construction. - Erdős #1191 — how small can an infinite Sidon set's liminf density be? — references Singer's construction, "shift-incidence counting," and AlphaEvolve-assisted constant optimization in the same Sidon/Golomb-ruler technique lineage. - Sidon sets / B_2 sets / Golomb rulers — the central combinatorial object ($B_2$ sets / Golomb rulers) that Singer's construction produces extremal examples of. - $\gamma$-Golomb rulers (bounded-multiplicity difference sets generalizing Sidon sets) — the $\gamma$-Golomb-ruler generalization (bounded-multiplicity difference sets) that the higher-$\lambda$ Singer parameter family ($\lambda=\frac{q^{n-1}-1}{q-1}$) naturally generalizes to. - Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant) — the *impossibility*-side technique (Erdős–Turán / Erdős–Stöhr–Halberstam–Roth–O'Bryant double-counting) that pairs with Singer's construction to sandwich $h(N)$. - Prime-power conjecture for perfect difference sets — open in general; asymptotic density result by Sarah Peluse, "An asymptotic version of the prime power conjecture for perfect difference sets," arXiv:2003.04929, Math. Ann. 380 (2021), 1387–1425 (shows Singer-type moduli account for a $\sim1/\log N$-density, i.e. essentially-all, fraction of valid $n\le N$). - Bose, R.C. (1939) and Bruck, R.H. (1955) — cited by en.wikipedia.org/wiki/Difference_set as the classical follow-up generalizing Singer's cyclic construction to systematic difference-set families and non-cyclic groups, respectively; not independently fetched this session.