Singer's finite-field perfect difference set construction (1938)

Statement

Does there exist, for a given integer $n\ge 2$, a perfect (planar) difference set — i.e. a $(v,k,1)$ difference set with $v=n^2+n+1$, $k=n+1$ — in a cyclic group of order $v$? Equivalently (by the standard design-theoretic correspondence): does there exist a cyclic projective plane of order $n$, i.e. a finite projective plane of order $n$ admitting an automorphism group acting as a single cyclic group that is *simply transitive* on its points?

A $(v,k,\lambda)$ difference set is a $k$-subset $D$ of a group $G$ of order $v$ such that every non-identity element of $G$ has exactly $\lambda$ representations as an ordered difference $d_1-d_2$ ($d_1,d_2\in D$); the case $\lambda=1$ is called *planar* or *perfect* (Wikipedia, "Difference set", fetched directly). Before Singer, it was not known whether such configurations exist for any infinite family of orders $n$ at all — projective planes were known combinatorially (e.g. via coordinatization over any field/near-field), but not known to carry the extra cyclic-difference-set structure.

Facts

- Source: J. Singer, "A Theorem in Finite Projective Geometry and Some Applications to Number Theory," *Trans. Amer. Math. Soc.* 43(3):377–385 (1938) — exact citation confirmed both by Mészáros–Rónyai–Szabó (arXiv:1908.05591, reference [25]) and by independent web search. - Answer (existence, resolved): for every prime power $q$, a perfect difference set of size $q+1$ exists in the cyclic group $\mathbb Z_{q^2+q+1}$ — equivalently, $\mathrm{PG}(2,q)$ (the classical Desarguesian projective plane of prime-power order $q$) is a cyclic projective plane. This settles existence affirmatively for the entire prime-power family, which is also exactly the family for which projective planes are known to exist at all by other constructions (coordinatization over $\mathbb F_q$). - Parameters: $(v,k,\lambda) = (q^2+q+1,\ q+1,\ 1)$, matching the point/line count and line size of $\mathrm{PG}(2,q)$. - Converse direction is still open — the Singer conjecture: every difference set in $\mathbb Z_{q^2+q+1}$ is equivalent to Singer's construction (arXiv:1908.05591, §1.2, "very much open"; partial results by Berman [3] and Halberstam–Laxton [15] count reduced Singer-type difference sets exactly). Separately, the closely related prime power conjecture — whether perfect difference sets mod $n^2+n+1$ (equivalently projective planes of order $n$) can exist for $n$ *not* a prime power — remains open, verified computationally false up to very large bounds but with no general proof (WebSearch, emergentmind.com summary); the $n=10$ non-existence case was settled by a massive computer search (Lam–Thiel–Swiercz 1989), but the general conjecture is open and is the structural obstruction behind other still-open Erdős-adjacent problems, e.g. erdos/723 (finite projective planes of non-prime-power order). - General (non-planar) Singer construction: for any prime power $q$ and $n\ge0$, $G=\mathbb F_{q^{n+2}}^\ast/\mathbb F_q^\ast$ is cyclic of order $\frac{q^{n+2}-1}{q-1}$, and $D=\{x\in G : \mathrm{Tr}_{q^{n+2}/q}(x)=0\}$ is a difference set with parameters $\left(\frac{q^{n+2}-1}{q-1},\frac{q^{n+1}-1}{q-1},\frac{q^n-1}{q-1}\right)$ (Wikipedia, "Difference set", trace-kernel formulation); the $n=1$ case is exactly the planar/perfect case above. The trace-zero-coset description is proved equivalent to the original collineation-orbit description by Singer himself (arXiv:1908.05591 §1.2, citing A. Pott, *Finite Geometry and Character Theory*, LNM 1601, 1995). - Downstream reuse already in this wiki: erdos/30.md (Erdős #30, sharp $N^{1/2}$ Sidon-set asymptotics) cites exactly this construction — "Singer [Si38] — via a perfect difference set constructed in the finite field $\mathbb F_q$ ... giving $h(N)\ge(1-o(1))N^{1/2}$" — and notes it was formalized in Lean 4 with zero sorrys in arXiv:2605.03274 ("for every prime power $q=p^k$ there exists a Sidon set modulo $q^2+q+1$ of cardinality $q+1$"). Related pages erdos/241.md ($B_3$-set asymptotics, via Bose–Chowla's generalization of the same idea), erdos/41.md, erdos/39.md, and erdos/1191.md all trace their best-known lower-bound constructions back to this same 1938 result.

Solution

The transferable idea — arithmetize a symmetric combinatorial design by finding a cyclic group acting simply transitively on it, via the multiplicative structure of a finite field.

1. Geometric input. $\mathrm{PG}(2,q)$, the projective plane over $\mathbb F_q$, can be built from the 3-dimensional vector space $\mathbb F_{q^3}$ viewed as a 3-dimensional $\mathbb F_q$-vector space: points of $\mathrm{PG}(2,q)$ are the $\mathbb F_q^\ast$-cosets of nonzero vectors, i.e. exactly the elements of $G=\mathbb F_{q^3}^\ast/\mathbb F_q^\ast$, which has order $\frac{q^3-1}{q-1}=q^2+q+1$ — the correct point count. 2. Key algebraic fact exploited: the multiplicative group of *any* finite field is cyclic. Hence $\mathbb F_{q^3}^\ast$ is cyclic, and its quotient $G=\mathbb F_{q^3}^\ast/\mathbb F_q^\ast$ is again cyclic, of order exactly $q^2+q+1$ = the number of points of $\mathrm{PG}(2,q)$. Multiplication by a fixed generator of $\mathbb F_{q^3}^\ast$ (a "Singer cycle") induces a collineation $c$ of $\mathrm{PG}(2,q)$ — a bijection on points sending lines to lines — that cyclically permutes all $q^2+q+1$ points (Mészáros–Rónyai–Szabó, arXiv:1908.05591 §1.2, attributing this to Singer). 3. Turn geometry into number theory. Fix a base point $P_0$ and label every point $P_i := c^i(P_0)$ for $0\le i\le q^2+q$, giving a bijection between points of $\mathrm{PG}(2,q)$ and $\mathbb Z_{q^2+q+1}$. Since $c$ is a collineation, this labeling turns the incidence structure into an *algebraic* one: fix any single line $L$ (a $(q+1)$-point subset), and let $D=\{i : P_i\in L\}\subset\mathbb Z_{q^2+q+1}$ be the corresponding set of indices, $|D|=q+1$. 4. Why $D$ is automatically a perfect difference set — no separate combinatorial argument needed. In a projective plane of order $q$, any two distinct points lie on a *unique* common line, and any two distinct lines meet in a *unique* common point. Because $c$ acts simply transitively on points (step 2) and is a collineation (so it also permutes the $q^2+q+1$ lines cyclically, transitively, and by the same exponents), the number of pairs $(P_i,P_j)\in L\times L$ with $P_i-P_j\equiv g\pmod{q^2+q+1}$, for a *fixed* nonzero $g$, equals the number of lines in the orbit of $L$ that contain both $P_0$ and $P_{g}$ — which by the axioms of a projective plane is *exactly one*. This is precisely the defining property of a $(q^2+q+1,\,q+1,\,1)$ difference set: the plane's own uniqueness axioms (two points determine a unique line) are transported, via the cyclic labeling, directly into the difference-uniqueness axiom of $D$. No extra counting or estimation is required — the difference-set property is a *restatement* of the projective-plane axioms once the points are cyclically coordinatized. 5. Equivalent, more computational reformulation (also due to Singer, used e.g. for the Lean formalization and for Sidon-set lower bounds): $D$ can be described directly, without reference to a chosen collineation orbit, as the image in $G=\mathbb F_{q^3}^\ast/\mathbb F_q^\ast$ of the trace-zero elements $\{x\in\mathbb F_{q^3}^\ast : \mathrm{Tr}_{q^3/q}(x) := x+x^q+x^{q^2}=0\}$ (arXiv:1908.05591 §1.2; Wikipedia "Difference set"). This trace-kernel form is what generalizes cleanly to the full family $\left(\frac{q^{n+2}-1}{q-1},\frac{q^{n+1}-1}{q-1},\frac{q^n-1}{q-1}\right)$ for all $n\ge0$, and is the version most convenient to formalize or compute with directly (no need to construct/track an explicit collineation). 6. Why this technique transfers. The transferable move is: *whenever a finite incidence structure (design, plane, block system) is known to admit a cyclic group acting regularly (simply transitively) on its points* — which for structures built from $\mathbb F_{q^{n}}$ is essentially automatic, since finite-field multiplicative groups are always cyclic — *the structure's combinatorial uniqueness axioms translate verbatim into a modular-arithmetic difference-uniqueness statement.* This converts a geometry-existence question into a finite-field/number-theory construction, immediately supplying explicit, dense, extremal additive-combinatorics objects: taking $D$ itself (or projecting it via $i \mapsto i \bmod N$ for suitable $N$) gives an explicit Sidon ($B_2$) set of size $q+1\sim\sqrt{v}$ in $\{0,\dots,v-1\}$, since the "every nonzero difference exactly once" property is *strictly stronger* than the Sidon condition ("every nonzero difference at most once"). This is exactly the mechanism reused for: the classical lower bound $h(N)\ge(1-o(1))N^{1/2}$ for Sidon sets (Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets), Bose–Chowla's generalization to $B_h$/$B_3$ sets giving $(1-o(1))N^{1/h}$ (Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets, Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf), infinite Sidon-set constructions built by gluing finite Singer blocks (Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set, Erdős #1191 — how small can an infinite Sidon set's liminf density be?), and — going the other way — recent work extracting/forbidding Sidon subsets *within* Singer's perfect difference sets themselves (Alexeev–Mixon, arXiv:2510.19804, cited in erdos/39.md), plus a full zero-sorry Lean 4 formalization of the construction (arXiv:2605.03274).

Bottom line for downstream use: the "Singer trick" = (i) realize your combinatorial structure's automorphism group contains (or can be embedded to contain) a cyclic group coming from a finite-field multiplicative-group quotient, (ii) label points by group elements via that cyclic action, (iii) the structure's own uniqueness/regularity axioms become, for free, a perfect-difference-set / modular-arithmetic statement, (iv) read off an explicit near-square-root-density additive-combinatorics extremal object. This is the concept page to link as `Singer finite-field perfect difference set construction` (already referenced from erdos/30.md).

Related

- Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — Erdős' sharp $N^{1/2}$ Sidon-set asymptotics; Singer's construction supplies the matching lower bound $h(N)\ge(1-o(1))N^{1/2}$, formalized zero-sorry in Lean 4 (arXiv:2605.03274). - Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets — $B_3$-set asymptotics; Bose–Chowla's generalization of the Singer/finite-field idea gives the $(1-o(1))N^{1/3}$ lower bound. - Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — $B_3$ (distinct-triple-sum) set density; same Bose–Chowla/Singer-family finite-field construction lineage. - Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — infinite Sidon-set density; finite Singer blocks are the building material for the best infinite constructions (Ruzsa, Cilleruelo), and Alexeev–Mixon (arXiv:2510.19804) resolve a sibling problem about Sidon subsets *inside* Singer's perfect difference sets. - Erdős #1191 — how small can an infinite Sidon set's liminf density be? — liminf density of infinite Sidon sets; same construction lineage noted explicitly in that page. - Erdős #552 — Ramsey number R(C4,Sn), dip below n+√n? — $R(C_4,S_n)$ Ramsey numbers; extremal construction is the *polarity graph* of a projective plane, i.e. the same $\mathrm{PG}(2,q)$ object Singer's cyclic labeling arithmetizes, but used via its polarity rather than its cyclic automorphism. - erdos/723 — existence of finite projective planes of non-prime-power order; the still-open converse/structural sibling (prime power conjecture) to Singer's existence result, which only ever produces planes for prime-power orders. - Singer finite-field perfect difference set construction — the technique's own concept page (referenced from erdos/30.md; this page is its fuller writeup). - Finite-field / projective-plane constructions for extremal additive sets — the broader family of explicit finite-field-based extremal constructions (Bose–Chowla etc.) that this construction seeds.