The prime power conjecture: determining all orders of finite projective planes

The existence problem for finite projective planes asks for the exact set of positive integers $n$ for which a projective plane of order $n$ exists. Planes are known for every prime-power order (starting from the planes over finite fields), and no plane of non-prime-power order has ever been found; nonexistence is proved only through the Bruck–Ryser congruence obstruction, the classical order-6 reduction to orthogonal Latin squares, and the 1989 computer-assisted exclusion of order 10, leaving order 12 the smallest unresolved case. The conjecture that the admissible orders are exactly the prime powers — the prime power conjecture — remains one of the oldest open problems in combinatorics. The open question cited in Yibo Gao's 2016 paper on pure partial planes of order 6 remains unresolved: no counterexample has been constructed, no nonexistence proof is known for order 12 or for any order $\equiv 0, 3 \pmod 4$, and only an asymptotic result (Peluse 2021) exists for the strictly smaller cyclic subcase.

Background

A finite projective plane is an incidence structure of points and lines satisfying three axioms: any two distinct points lie on exactly one common line, any two distinct lines meet in exactly one common point, and there exist four points no three of which are collinear. From these axioms it follows that there is an integer $n \geq 2$, the order of the plane, such that every line contains exactly $n+1$ points, every point lies on exactly $n+1$ lines, and the plane has exactly $n^2+n+1$ points and equally many lines. For every prime power $q$ (a number of the form $p^k$ with $p$ prime), the plane $PG(2,q)$, whose points and lines are the 1- and 2-dimensional subspaces of a 3-dimensional vector space over the finite field of $q$ elements, is a projective plane of order $q$; many further non-Desarguesian planes (planes not arising from a field in this way) are also known, but every known construction, classical or exotic, still yields a prime-power order.

For non-prime-power orders the picture is fragmentary. The order-6 case is the setting of Euler's thirty-six officers problem: Bose (1938) reduced the existence of a plane of order 6 to the existence of a pair of orthogonal Latin squares of order 6 — two $n \times n$ arrays of symbols such that each ordered pair of symbols occurs exactly once when the arrays are superimposed — and Tarry's 1900–1901 enumeration showed no such pair exists, so there is no plane of order 6. The Bruck–Ryser theorem (1949) gives a general number-theoretic obstruction: if $n \equiv 1$ or $2 \pmod 4$ and $n$ is not a sum of two integer squares, then no plane of order $n$ exists. This excludes $6, 14, 21, 22, \dots$ but gives no information when $n \equiv 0$ or $3 \pmod 4$ (orders such as $12, 15, 20, 24$) and leaves sums of two squares such as $10, 18, 26$ untouched. Order 10 survived every algebraic obstruction and was finally excluded only in 1989 by Lam, Thiel, and Swiercz through an exhaustive computer search organized around the binary linear code spanned by the line-incidence vectors of a hypothetical plane; the computation was a multi-year search on the fastest hardware of its day and has since been independently re-verified. Since 1989 the smallest order of unknown status is $n = 12$.

A related but strictly smaller subproblem concerns cyclic planes. A perfect difference set is a subset $D$ of the cyclic group $\mathbb{Z}/(n^2+n+1)\mathbb{Z}$ of size $n+1$ whose pairwise differences $d-d'$ realize every nonzero group element exactly once; such a set is equivalent to a projective plane of order $n$ admitting a sharply transitive cyclic automorphism group (an automorphism whose powers cycle through all $n^2+n+1$ points in a single orbit), and perfect difference sets exist for every prime power by a classical construction from finite fields. Even for this restricted class the prime power conjecture is open: Baumert and Gordon verified computationally that no non-prime-power $n \leq 2 \times 10^9$ admits such a difference set, and Peluse proved in 2021 only the asymptotic statement that the number of integers $n \leq N$ for which $\mathbb{Z}/(n^2+n+1)\mathbb{Z}$ contains a perfect difference set is asymptotically $N/\log N$ — the count predicted if exactly the prime powers occurred. The general existence problem for arbitrary planes is at least as hard as the cyclic subcase, since every perfect difference set yields a plane but planes need not admit any cyclic symmetry.

Problem Statement

Determine exactly for which positive integers $n$ there exists a finite projective plane of order $n$; equivalently, prove or refute the prime power conjecture: a finite projective plane of order $n$ exists if and only if $n$ is a prime power. Here a projective plane of order $n$ is an incidence structure of points and lines in which any two distinct points lie on exactly one line, any two distinct lines meet in exactly one point, there exist four points with no three collinear, and some (hence every) line contains exactly $n+1$ points; such a structure then has exactly $n^2+n+1$ points and lines. The existence direction for prime powers is classical (planes over every finite field, plus many non-Desarguesian families). The open content is the converse: whether any order $n$ that is not a prime power — the smallest being $n=12$ — admits a projective plane. The conjecture is resolved by a proof that settles existence for all non-prime-power orders simultaneously, which together with the classical constructions closes the characterization, or by exhibiting at least one plane of non-prime-power order, refuting the conjecture and identifying a new admissible class; the complete classification of admissible orders is the objective.

References

1. Yibo Gao, "The Largest Pure Partial Planes of Order 6 Have Size 25", arXiv:1611.00084 (2016), DOI 10.48550/arXiv.1611.00084, https://arxiv.org/abs/1611.00084 (source paper)
2. R. H. Bruck and H. J. Ryser, "The Nonexistence of Certain Finite Projective Planes", Canadian Journal of Mathematics 1 (1949), 88–93, DOI 10.4153/cjm-1949-009-2, https://doi.org/10.4153/cjm-1949-009-2
3. C. W. H. Lam, L. Thiel, and S. Swiercz, "The Non-Existence of Finite Projective Planes of Order 10", Canadian Journal of Mathematics 41 (1989), 1117–1123, DOI 10.4153/cjm-1989-049-4, https://doi.org/10.4153/cjm-1989-049-4
4. Dominique J. Roy, "Confirmation of the non-existence of a projective plane of order 10", M.Sc. thesis, Carleton University (2011), DOI 10.22215/etd/2011-09202, https://doi.org/10.22215/etd/2011-09202
5. Sarah Peluse, "An asymptotic version of the prime power conjecture for perfect difference sets", Mathematische Annalen 380 (2021), no. 3-4, 1387–1425, arXiv:2003.04929, DOI 10.1007/s00208-021-02188-5, https://doi.org/10.1007/s00208-021-02188-5
6. Leonard D. Baumert and Daniel Gordon, "On the existence of cyclic difference sets with small parameters", in High Primes and Misdemeanours: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams, Fields Institute Communications 41, American Mathematical Society (2004), 61–68, DOI 10.1090/fic/041/05, https://doi.org/10.1090/fic/041/05