The orders a plane cannot have

A projective plane of order $n$ has $n^2 + n + 1$ points and as many lines, $n + 1$ points on every line and $n + 1$ lines through every point, and any two points on exactly one line. Seven points and seven lines drew the smallest, of order two; every finite field builds one, so every prime power is the order of a plane. What nobody has ever built is a plane whose order is not a prime power.

The first such order is six. A plane of order six would have $43$ points and $43$ lines with seven points on each, and nothing in the counting objects: $43 = 6^2 + 6 + 1$, every count that must be a whole number is one, and the determinant argument that forces at least as many lines as points is satisfied with equality. And yet there is no such plane. The proof, found by Richard Bruck and Herbert Ryser in 1949, is the subject of this essay, because it is a strange proof: it never draws a line, it uses one matrix identity, and it reduces the question to whether six is a sum of two squares.

The one equation a plane satisfies #

Write the plane as a table $N$ with a row for each point and a column for each line, and a $1$ where the point lies on the line. The product $N N^{\mathsf T}$ has, in row $a$ and column $b$, the number of lines containing both point $a$ and point $b$. For $a = b$ that is the number of lines through a point, $n + 1$; for $a \neq b$ it is exactly one. So

$$N N^{\mathsf T} = nI + J,$$

where $I$ is the identity and $J$ the matrix of all ones. The figure checks it entry by entry for the plane of order three: $4$ down the diagonal, $1$ everywhere else.

That identity is all the proof uses. It does not know what a line is, or that lines meet, or anything about the geometry beyond this one fact about pairs of points. And it is enough to rule out infinitely many orders, because it can be read as a statement about sums of squares.

Take one variable $x_p$ for each point, and for each line $\ell$ let $y_\ell$ be the sum of the variables of the points on it. The sum of the squares of the $y$’s is $x^{\mathsf T} N N^{\mathsf T} x$, and the identity turns that into

$$y_1^2 + y_2^2 + \dots + y_v^2 \;=\; n\left(x_1^2 + \dots + x_v^2\right) + w^2, \qquad w = x_1 + \dots + x_v.$$

A plane of order $n$ therefore produces an identity between two ways of writing a quadratic form as a combination of squares, valid for every choice of the $x$’s. The argument asks what that identity forces on $n$.

Which orders it can speak about #

The theorem. If a projective plane of order $n$ exists and $n$ leaves a remainder of $1$ or $2$ when divided by $4$, then $n$ is a sum of two squares.

Six leaves $2$ and is not a sum of two squares, so there is no plane of order six. Fourteen, twenty-one, twenty-two and thirty fall the same way, and so, as the figure shows, do twenty orders below a hundred. Orders leaving $0$ or $3$ are untouched, and so are the orders leaving $1$ or $2$ that are sums of two squares — ten is $1^2 + 3^2$, and the theorem says nothing about it.

The two remainders matter because of how the proof groups variables. There are $v = n^2 + n + 1$ variables, and when $n$ leaves $1$ or $2$ the number $v$ leaves $3$ when divided by four. Adding one more variable makes the count a multiple of four, and it is in blocks of four that the next step works.

Four squares at a time #

The obstacle in the identity is the factor $n$. The left side is a sum of plain squares; the right side is $n$ times a sum of squares, and $n$ is not a square. Lagrange proved in 1770 that every whole number is a sum of four squares, and an identity Euler found twenty years earlier turns that into a way of absorbing the $n$.

Write $n = a^2 + b^2 + c^2 + d^2$ and form the $4 \times 4$ array whose first row is $(a, b, c, d)$ and whose other rows are the same numbers rearranged with signs — the multiplication table of the quaternion $a + bi + cj + dk$. Its rows are perpendicular and each has squared length $n$. Applied to four variables $x_1, \dots, x_4$, it produces four new ones $z_1, \dots, z_4$ with

$$z_1^2 + z_2^2 + z_3^2 + z_4^2 = n\left(x_1^2 + x_2^2 + x_3^2 + x_4^2\right),$$

which is the identity that multiplies sums of squares, read as a change of variables. Because the array is invertible — its product with its transpose is $n$ times the identity — the $x$’s can be recovered from the $z$’s as rational combinations.

So add one variable $x_{v+1}$, and $n x_{v+1}^2$ to both sides, to bring the count to a multiple of four. Every block of four $x$’s multiplied by $n$ becomes four $z$’s squared, and the identity becomes

$$y_1^2 + \dots + y_v^2 + n\,x_{v+1}^2 \;=\; z_1^2 + \dots + z_{v+1}^2 + w^2,$$

with every $y$, every $x$ and $w$ now a rational combination of the $z$’s. The factor $n$ has been absorbed everywhere except one place, the extra variable on the left.

Why the blocks are fours #

The number four is not a convenience, and the reasons it has to be four say something about the whole method.

The step needs two things of a block size $m$: every order $n$ must be a sum of $m$ squares, so that the array exists; and there must be an $m \times m$ array with perpendicular rows of squared length $n$, so that $n$ times a sum of $m$ squares is again a sum of $m$ squares by a linear change of variables. Blocks of two satisfy the second requirement — complex multiplication gives the $2 \times 2$ array — but fail the first, since only the sums of two squares have such a representation, and those are exactly the orders the theorem is trying to test. Blocks of three fail the first requirement too: numbers of the form $4^a(8b + 7)$, starting with seven, are not sums of three squares.

Four is the smallest size at which every number qualifies, by Lagrange’s theorem, and at which the array exists, by the quaternions. Adolf Hurwitz proved in 1898 that the second requirement — an identity multiplying sums of $m$ squares — holds only for $m = 1, 2, 4$ and $8$, the sizes of the real numbers, the complex numbers, the quaternions and the octonions, and what is lost at eight is why the list stops there. So the proof sits on the one block size that is both universal and multiplicative. A theorem about finite planes is carried by the four-dimensional number system; the only other block size that would serve is eight, with the octonions, and it would need the variable count to be adjusted to a multiple of eight instead.

Cancelling one line at a time #

Now the $z$’s are free to be chosen, and they are chosen so that squares cancel.

The first line-form $y_1$ is some combination of the $z$’s. Choose $z_1$ so that $z_1 = y_1$ — a linear equation for $z_1$ in terms of the other $z$’s, solvable unless $z_1$’s coefficient in $y_1$ happens to be exactly $1$, in which case choose $z_1 = -y_1$ instead. Either way $y_1^2 = z_1^2$, and those two squares cancel from the two sides. Substitute the choice everywhere, and $z_1$ is gone. Do the same with $y_2$ and $z_2$, and so on through all $v$ lines.

After $v$ steps only $z_{v+1}$ remains free, every other quantity is a rational multiple of it, and the identity has become

$$n\,x_{v+1}^2 = z_{v+1}^2 + w^2.$$

Set $z_{v+1} = 1$. Then $x_{v+1}$ and $w$ are rational numbers with $n\,x_{v+1}^2 = 1 + w^2$, and $x_{v+1}$ cannot be nought, since the right side is at least one. Dividing,

$$n = \left(\frac{1}{x_{v+1}}\right)^2 + \left(\frac{w}{x_{v+1}}\right)^2,$$

so $n$ is a sum of two squares of rational numbers. And a whole number that is a sum of two rational squares is a sum of two whole squares — the theorem a fraction on the circle forces a whole point is exactly that statement. The plane would make $n$ a sum of two squares.

The argument run on planes that exist #

A proof by contradiction usually cannot be watched working, because what it assumes does not exist. This one can, because the orders that are sums of two squares have planes, and the argument’s steps can be carried out on them.

For the plane of order two, the seven points and one extra variable make two blocks of four, seven eliminations follow, and what comes out is $x_8$ and $w$ with $2 x_8^2 = 1 + w^2$. The figure reports it as $2 = (7/5)^2 + (1/5)^2$, and $49/25 + 1/25$ is $2$. For the planes of order five and nine the eliminations are thirty-one and ninety-one steps long and the fractions they produce have ten and eighteen digits, and each pair of squares, checked exactly, adds to the order.

Two things are worth noticing. The argument does not find the obvious representation — nine is $0^2 + 3^2$, and the elimination produces a pair of eighteen-digit fractions instead — because it is not looking for one: it is carrying out a sequence of substitutions dictated by the plane’s incidences, and the squares it lands on are whatever the plane’s structure makes them. And for order six there is nothing to run it on. The substitutions need the $43 \times 43$ table, and the theorem’s content is precisely that no such table exists, because if it did the same elimination, eleven blocks of four long, would end at $6 = r^2 + s^2$ in rationals.

Why six cannot be two squares #

That last equation has no solution, and the reason is a small calculation modulo three.

Suppose $x^2 + y^2 = 6z^2$ in whole numbers, not all nought — clearing denominators from a rational solution gives one. The squares modulo three are $0$ and $1$, so $x^2 + y^2$ is divisible by three only when both $x$ and $y$ are. Then $9$ divides $x^2 + y^2 = 6z^2$, so $3$ divides $2z^2$ and hence $z$. Dividing all three by $3$ gives a smaller solution, and the division can be repeated forever, which no whole numbers allow. So there is none.

The same descent works for any prime of the form $4k + 3$ that divides a number an odd number of times, and those are exactly the numbers that are not sums of two squares — the lattice of two squares is where that theorem is drawn. Six has the prime three once, fourteen has seven once, twenty-one has three and seven once each, twenty-two has eleven once. Twelve has three once too, and it is not a sum of two squares, but twelve leaves $0$ when divided by four and the theorem does not apply to it: the obstruction exists for twelve and the proof cannot reach it.

What the argument cannot say #

When $n$ leaves $0$ or $3$ modulo four, $v = n^2 + n + 1$ leaves $1$, and the variables fit into blocks of four with one left over rather than one short. The same elimination then ends at $y^2 = n x^2 + w^2$, which has the solution $x = 0$, $y = w$ for any $n$. The identity is satisfied, nothing is forced, and the argument falls silent on twelve, fifteen, twenty, twenty-four and every other order in that half.

It is also silent on the orders it does apply to that are not prime powers but pass the test: ten, twenty-six, thirty-four, forty-five, fifty. For those the equation $n = r^2 + s^2$ has solutions, so the substitutions have somewhere to end, and the argument cannot tell whether a plane exists.

Ten is where that silence was finally broken, and not by any argument like this one. Clement Lam, Larry Thiel and Stanley Swiercz showed in 1989 that no plane of order ten exists, by a computer search of several thousand hours organised around the error-correcting code a plane of order ten would carry. It is the only order excluded that way, and nobody has proposed repeating the method at twelve.

Two older proofs for six #

Six was known to be impossible before 1949, by a completely different route.

A plane of order $n$ is equivalent to a set of $n - 1$ mutually orthogonal Latin squares of order $n$ — the plane hiding in the squares is that equivalence. For order six that would need five mutually orthogonal squares, and there is not even a pair: Gaston Tarry showed in 1900, by listing the cases, that Euler’s puzzle of the thirty-six officers has no solution. That settles the plane of order six by exhaustion.

Bruck and Ryser’s argument settles it by arithmetic, and it settles fourteen, twenty-one, twenty-two and infinitely many others at the same time, none of which an exhaustive search could reach. Those two proofs say the same thing about six and share no step. One lists squares until none is left; the other shows that a table satisfying one identity would make six a sum of two squares. The arithmetic proof is the only one of the two that says why — and the reason is not about officers or planes at all but about which numbers the quaternions can split.

A generalisation, and the pattern it follows #

The argument used only $N N^{\mathsf T} = nI + J$, and that identity belongs to a larger family: the symmetric designs, where $v$ points and $v$ blocks have $k$ points in each block and every two points share $\lambda$ blocks, so that $N N^{\mathsf T} = (k - \lambda) I + \lambda J$. Sarvadaman Chowla and Ryser extended the theorem to them in 1950: when $v$ is odd, the equation

$$x^2 = (k - \lambda)\,y^2 + (-1)^{(v-1)/2}\,\lambda\,z^2$$

must have a solution in whole numbers not all nought. Projective planes are the case $\lambda = 1$, $k = n + 1$, where it becomes the two-squares condition. When $v$ is even the condition is simpler still: $k - \lambda$ must be a perfect square, which is the determinant argument reading off the determinant of $N N^{\mathsf T}$ and asking it to be the square of an integer.

The Chowla–Ryser equation is a statement about a quadratic form in three variables having a rational zero, and that question was settled completely by Hasse and Minkowski: such a form has a rational zero exactly when it has one over the real numbers and over every field of $p$-adic numbers. So the design question becomes finitely many checks, one per prime dividing the coefficients — exactly the descent modulo three above, done for every relevant prime at once. An existence question about a finite geometry has been turned into local arithmetic, which is as far as the method can go.

The tables and the arithmetic that are shown #

One plane’s table is drawn, of order three. The identity $N N^{\mathsf T} = nI + J$ is checked entry by entry for the planes of orders two, three, five and nine, and those are the only planes the figures build. A plane of order sixteen or twenty-five is used nowhere.

The elimination is run where it can be run, which is where it proves nothing. For orders two, five and nine it ends at a genuine pair of squares, checked exactly; for six it cannot start. The figure shows the mechanism of the proof on inputs for which its conclusion was never in doubt, and the logical force of the argument is entirely in the case the figure cannot draw.

The map of orders is a record of knowledge rather than a computation of it. Which orders are prime powers and which fail the two-squares test is computed; that ten is excluded is Lam’s result, and that the blank orders are open is the state of the subject, not something any figure established.

Still open: whether twelve has a plane #

Twelve is the smallest order about which nothing is known. It leaves $0$ modulo four, so Bruck and Ryser’s argument cannot reach it; it is not a prime power, so no field builds a plane of order twelve; and a search on the scale of the one that settled ten is far out of reach, since the number of configurations grows so steeply that the experience at ten is not a guide.

Is there a projective plane of order twelve? More generally, is the order of every finite projective plane a prime power? Every plane anyone has found has prime-power order, and the only two tools that exclude orders are the one in this essay and exhaustive computation. Between them they have ruled out six, ten, and the Bruck–Ryser orders; they are silent on twelve, fifteen, eighteen, twenty and every other blank on the map.

A geometry decided by arithmetic #

The habit worth keeping is the one the proof uses.

A projective plane is a configuration of points and lines, and the natural instinct is to argue about configurations — to try to build one, and to find where the building fails. Bruck and Ryser threw the configuration away almost immediately. They kept one consequence of it, a matrix identity; read the identity as a statement about sums of squares; used the quaternions to move a troublesome factor out of the way; and ended with a question about which numbers are sums of two squares, which Fermat had already answered.

The geometry never came back. That is what makes the argument powerful — it rules out infinitely many orders at once, where a search rules out one — and it is also what limits it: whatever the identity cannot see, the proof cannot see either, and the identity is the same for orders twelve and nine, one of which has four planes.