A finite projective plane of order nn is known to exist for every prime power nn (the Desarguesian plane over the finite field of nn elements, plus many non-Desarguesian families), and every projective plane ever constructed has prime-power order. Whether any finite projective plane exists whose order is not a prime power — equivalently, whether the prime power conjecture (planes exist exactly at prime-power orders) holds — is a central open problem of finite geometry, famously resisting the Bruck–Ryser non-existence theorem and massive computation (order 10 was only settled non-existent in 1989–1991). Stokes and Bras-Amorós (2010) proved that the optimal configurations for peer-to-peer user-private information retrieval are exactly the finite projective planes and noted that their constructions are therefore limited to prime-power orders. The question is posed in full generality; the smallest undecided order is 12, i.e., whether a symmetric 2-(157,13,1)(157,13,1) design exists.

Background

A finite projective plane of order nn, for an integer n≥2n \geq 2, is an incidence structure of points and lines with exactly n2+n+1n^2+n+1 points and equally many lines, in which every line carries n+1n+1 points, every point lies on n+1n+1 lines, and any two distinct points lie on exactly one common line. Equivalently, it is a symmetric 22-(n2+n+1,n+1,1)(n^2+n+1, n+1, 1) design: a collection of n+1n+1-element subsets (the lines, or blocks) of a set of n2+n+1n^2+n+1 points such that every pair of distinct points is contained in exactly one block and the number of blocks equals the number of points.

The standard example is the Desarguesian plane PG(2,q)PG(2, q), built from the one-dimensional and two-dimensional subspaces of a three-dimensional vector space over the finite field Fq\mathbb{F}_q; it has order qq for every prime power qq (a prime power is pkp^k for a prime pp and integer k≥1k \geq 1). Many non-Desarguesian planes, i.e., planes not isomorphic to any PG(2,q)PG(2, q), are also known (translation planes, Hall planes, Hughes planes, and others), but every known example, Desarguesian or not, has prime-power order. Each projective plane can be coordinatized by a planar ternary ring, a set carrying a ternary operation subject to suitable algebraic axioms; when this ring is a field the plane is Desarguesian, and weaker ternary rings yield the known non-Desarguesian planes.

Two classical results constrain the possible orders. The Bruck–Ryser theorem (in its Bruck–Ryser–Chowla form) states that if n≡1n \equiv 1 or 2(mod4)2 \pmod 4, then nn must be a sum of two integer squares; this rules out orders 6,14,21,22,30,…6, 14, 21, 22, 30, \ldots and, in particular, gives a slick modern proof of the non-existence at order 6 first established by Tarry's 1900 hand enumeration (equivalent to Euler's thirty-six officers problem). Order 10 escapes the theorem (since 10=12+3210 = 1^2 + 3^2), and its non-existence was settled only by a massive computer search of Lam, Thiel, and Swiercz, reported in 1991, which was reconfirmed in 2021 by translating the question into Boolean satisfiability and generating independently checkable nonexistence certificates. Beyond these results no general necessary condition is known that excludes any further order, so orders 12,15,18,20,24,26,28,…12, 15, 18, 20, 24, 26, 28, \ldots remain undecided.

A motivating application is peer-to-peer user-private information retrieval (P2P UPIR), a protocol model in which the members of a community submit queries to a database on one another's behalf so that the database cannot profile any individual. The collaboration structure is a combinatorial configuration: nun_u users and ncn_c communication spaces (each a memory sector plus a cryptographic key), each user accessing dud_u spaces and each space shared by dcd_c users, with any two users sharing at most one space. Stokes and Bras-Amorós (2010) proved that the optimal configuration — the one maximizing the anonymity-set size du(dc−1)d_u(d_c-1) against the database (which forces du(dc−1)=nu−1d_u(d_c-1) = n_u-1) while giving the best storage and time efficiency — is achieved exactly by finite projective planes, with du=dc=q+1d_u = d_c = q+1 and nu=nc=q2+q+1n_u = n_c = q^2+q+1 for a plane of order qq. Since planes are guaranteed to exist only when the order qq is a prime power, the optimal protocol configurations are currently available only at those orders, and the paper remarks that existence of planes at other orders is one of the most difficult open problems of finite geometry.

Problem Statement

Does there exist a finite projective plane whose order nn (an integer with n≥2n \geq 2) is not a prime power (a prime power being a number of the form pkp^k for a prime pp and integer k≥1k \geq 1)? Equivalently, is the set of orders of finite projective planes exactly the set of prime powers, as asserted by the prime power conjecture? Here a finite projective plane of order nn, for an integer n≥2n \geq 2, is an incidence structure consisting of a set of n2+n+1n^2+n+1 points and a set of n2+n+1n^2+n+1 lines such that every line is incident with exactly n+1n+1 points, every point lies on exactly n+1n+1 lines, and any two distinct points lie on exactly one common line; equivalently, a symmetric 22-(n2+n+1,n+1,1)(n^2+n+1, n+1, 1) design. (The restriction n≥2n \geq 2 excludes the degenerate three-point triangle, the symmetric 22-(3,2,1)(3,2,1) design of "order 1", which satisfies the incidence axioms literally but is not counted as a projective plane in the prime power conjecture; without it, order 11 — not being of the form pkp^k with k≥1k \geq 1 — would trivially answer the question.) The smallest undecided instance is order 12: does a projective plane of order 12 exist, i.e., a symmetric 22-(157,13,1)(157, 13, 1) design — 157 blocks, each a 13-point subset of a 157-point set, with every pair of distinct points contained in exactly one block? The next undecided orders are 15, 18, 20, 24, 26, 28, and so on, comprising all non-prime-power orders n≥2n \geq 2 not excluded by the Bruck–Ryser theorem and not already settled by computation (the Bruck–Ryser theorem rules out exactly the orders n≡1,2(mod4)n \equiv 1, 2 \pmod 4 that are not sums of two integer squares).

References

  1. Klara Stokes, Maria Bras-Amorós, Optimal configurations for peer-to-peer user-private information retrieval, Computers & Mathematics with Applications 59(4):1568–1577, 2010. DOI: 10.1016/j.camwa.2010.01.003, https://doi.org/10.1016/j.camwa.2010.01.003
  2. Colleen M. Swanson, Douglas R. Stinson, Extended combinatorial constructions for peer-to-peer user-private information retrieval, Advances in Mathematics of Communications 6(4):479–497, 2012. DOI: 10.3934/amc.2012.6.479, https://doi.org/10.3934/amc.2012.6.479; preprint arXiv:1112.2762, https://arxiv.org/abs/1112.2762
  3. R. H. Bruck, H. J. Ryser, The Nonexistence of Certain Finite Projective Planes, Canadian Journal of Mathematics 1(1):88–93, 1949. DOI: 10.4153/CJM-1949-009-2, https://doi.org/10.4153/CJM-1949-009-2
  4. C. W. H. Lam, The Search for a Finite Projective Plane of Order 10, The American Mathematical Monthly 98(4):305–318, 1991. DOI: 10.1080/00029890.1991.12000759, https://doi.org/10.1080/00029890.1991.12000759
  5. Curtis Bright, Kevin K. H. Cheung, Brett Stevens, Ilias Kotsireas, Vijay Ganesh, A SAT-based Resolution of Lam's Problem, Proceedings of the AAAI Conference on Artificial Intelligence 35(5):3669–3676, 2021. DOI: 10.1609/aaai.v35i5.16483, https://doi.org/10.1609/aaai.v35i5.16483; preprint arXiv:2012.04715, https://arxiv.org/abs/2012.04715
  6. Mate Matolcsi, Mihály Weiner, Finite projective planes and the Delsarte LP-bound, Analysis Mathematica 44(1):89–98, 2018. DOI: 10.1007/s10476-018-0108-1, https://doi.org/10.1007/s10476-018-0108-1; preprint arXiv:1801.09480, https://arxiv.org/abs/1801.09480
  7. Daniel M. Gordon, On difference sets with small λ, Journal of Algebraic Combinatorics 55(1):109–115, 2022. DOI: 10.1007/s10801-020-00992-x, https://doi.org/10.1007/s10801-020-00992-x; preprint arXiv:2007.07292 (2020), https://arxiv.org/abs/2007.07292
  8. Sarah Peluse, An asymptotic version of the prime power conjecture for perfect difference sets, Mathematische Annalen 380(3–4):1387–1425, 2021. DOI: 10.1007/s00208-021-02188-5, https://doi.org/10.1007/s00208-021-02188-5; preprint arXiv:2003.04929 (2020, v2 2023), https://arxiv.org/abs/2003.04929
  9. Kenzi Akiyama, Chihiro Suetake, The nonexistence of projective planes of order 12 with a collineation group of order 8, Journal of Combinatorial Designs 16(5):411–430, 2008. DOI: 10.1002/jcd.20175, https://doi.org/10.1002/jcd.20175
  10. Hadi Kharaghani, Sho Suda, Hadamard matrices related to projective planes, The Electronic Journal of Combinatorics 30(2):#P2.49, 2023. DOI: 10.37236/11990, https://doi.org/10.37236/11990; preprint arXiv:2211.02410 (2022), https://arxiv.org/abs/2211.02410
  11. Mingchun Xu, The properties of bordered matrix of symmetric block design, arXiv:1707.02208 (2017, v2), https://arxiv.org/abs/1707.02208