The plane hiding in the squares

The squares of order $n$ that a field builds come in families of $n - 1$, which is the largest number any order can carry. What has not been said is what such a family is, and the answer is not a fact about squares at all.

Take the $n^2$ cells of the grid and call them points. Each row is a set of $n$ cells; call it a line. Each column is another. And for each square in the family, each of its $n$ symbols marks out $n$ cells — one in every row and one in every column — so call each of those a line too. That is $n$ lines from the rows, $n$ from the columns, and $n$ from each of the $n-1$ squares: $n(n+1)$ lines in $n+1$ families of parallel ones.

The axiom, and where it comes from #

A plane is not a collection of lines; it is a collection of lines satisfying a condition, and the condition is that any two distinct points lie on exactly one line. That is what the drawing above checks by brute force, and it is worth seeing where each half of it comes from, because the two halves come from different places.

Two points in the same row lie on that row. Two points in the same column lie on that column. Two points sharing neither — different row, different column — lie on a symbol line exactly when the square in question gives them the same symbol. So the condition says: for every pair of cells in different rows and different columns, exactly one square of the family gives them a matching symbol.

At most one is orthogonality, restated. If two squares both matched that pair, the ordered pair of symbols they carry would appear at both cells, and orthogonality forbids a repeat. At least one is the counting. Each cell has $(n-1)^2$ others off its row and column; each square matches it at $n - 1$ of them; and $(n-1)$ squares therefore account for $(n-1)^2$ cells — exactly the number available, with none left over and no room for a collision. The whole equivalence turns on that arithmetic being tight, which is the same tightness that made $n - 1$ a ceiling in the first place.

Both directions #

The correspondence is not merely that squares produce lines. It runs the other way with nothing lost.

Given a plane of this kind — $n^2$ points, lines in $n+1$ parallel classes — pick two of the classes and call them rows and columns. Every point is then on one line of each, so a point is a pair of coordinates, and the grid is back. Take any third class: it has $n$ lines, each meeting every row once and every column once, so labelling its lines $0$ to $n-1$ and writing each line’s label into its own cells fills the grid with a Latin square. Two different classes give two squares that agree nowhere, because two points determine a line and cannot lie on lines from both classes twice.

So a complete family of $n - 1$ mutually orthogonal squares and an affine plane of order $n$ are two descriptions of one object. Everything provable about one is a fact about the other, and the questions that were hard to think about as arrangements become questions about geometries.

Two points, or none at all #

The smallest case is small enough to be suspicious of, and it is worth drawing precisely because it looks like nothing.

At order two the family is a single square, the plane has four points, and every pair of points is a line. Nothing is ruled out by anything. That is the shape of the smallest case in this subject generally: it satisfies the axioms without exercising them, which is why the interesting orders start at three and the interesting failures start at six.

Completing the plane #

An affine plane has parallel lines — lines in the same class never meet — and the classical repair is to add the meeting points rather than to live with the exception. For each of the $n + 1$ parallel classes, add one new point and declare every line of that class to pass through it. Then add one more line consisting of exactly those new points.

The count comes out to $n^2 + n + 1$ points and $n^2 + n + 1$ lines, with $n + 1$ points on every line and $n + 1$ lines through every point, and now any two lines meet in exactly one point — parallelism has gone. That is a projective plane of order $n$, and the perfect symmetry between the counts of points and lines is the duality that makes these objects worth having.

Order two completed is the Fano plane, which turns up in this collection already as the smallest projective plane and as a schedule where every pair meets once. Order three completed has thirteen points and thirteen lines, four points to a line, and is small enough to print in full.

Which orders exist #

Restated as geometry, the question that Euler’s officers opened becomes: for which $n$ is there a projective plane of order $n$?

Every prime power has one, built from the field of that size exactly as the squares were. No other order has ever been found, and the conjecture that no other order has one is a century old and open.

Two orders are settled in the negative, and they were settled in completely different ways.

Order six falls to the Bruck–Ryser theorem of 1949, which says that if $n$ leaves a remainder of $1$ or $2$ on division by four, then a projective plane of order $n$ can exist only if $n$ is a sum of two squares. Six leaves remainder $2$, and six is not a sum of two squares — $1 + 5$, $4 + 2$, and nothing else to try. So there is no plane of order six, and no complete family of five orthogonal squares of order six, which is consistent with Tarry’s exhaustion finding no orthogonal pair there either.

The same theorem disposes of $14$, $21$, $22$, $30$ and infinitely many more, all by an arithmetic condition that can be checked in a second and that says nothing whatever about arrangements.

Order ten is not touched by it. Ten leaves remainder $2$, but $10 = 1 + 9$ is a sum of two squares, so the theorem is silent — and silence is not permission. The question stayed open for forty years and was closed in 1989 by Lam, Thiel and Swiercz with a computer search: thousands of hours on a Cray, an exhaustive case analysis, and the answer that no plane of order ten exists.

That result belongs beside the four-colour theorem rather than beside Bruck–Ryser. It is a proof in the sense that every case was eliminated, and no human has read the elimination; its author said as much at the time, and the result was checked later by re-running parts of it rather than by understanding it. What it settles about the squares is that the largest orthogonal family of order ten has at most eight members — while the largest anybody has ever built has two.

Where the ceiling and the plane meet #

Putting the two rungs together gives a sentence worth stating on its own:

An order $n$ carries $n - 1$ mutually orthogonal Latin squares exactly when there is a projective plane of order $n$.

The ceiling argument of the previous rung is one half of it, and the dictionary above is the other. It explains the strange shape of what is known. The prime powers are easy because a field is a machine for building both objects at once. The composite orders are hard because nothing else is known to build either, and the impossibility results are hard because they have to rule out every arrangement rather than fail to find one.

The smallest order whose answer nobody knows is twelve. It is not ruled out by Bruck–Ryser, since twelve is divisible by four and the theorem says nothing there, and it is far beyond what a search of Lam’s kind can reach: the case analysis grows viciously with the order, and ten was already at the edge of what a decade of computing could do. Five orthogonal squares of order twelve are known; six are not; whether eleven exist is the open question, and it is the same open question as whether a plane of order twelve exists.

What an incomplete family is #

Most orders carry some orthogonal squares and not the full complement, and the dictionary handles that case too rather than merely failing at it.

A family of $k$ squares of order $n$ gives $k + 2$ parallel classes on the $n^2$ cells — the rows, the columns, and one class per square — with two points now lying on at most one line rather than exactly one. That object has a name, a net, and the missing classes are exactly the missing squares. The two known orthogonal squares of order ten are a net with four classes on a hundred points, and the question of whether ten carries more squares is the question of whether that net can be extended.

Reading it this way makes one thing plain that the squares hide. Extending a net is a local question with a global obstruction: adding one class is adding one more way to cut the points into lines that disagrees with every earlier cut, and there is no reason for the difficulty to grow smoothly as the classes accumulate. It does not. Bruck proved in the 1960s that a net which is close enough to complete — within roughly $\sqrt[4]{n}$ classes of the full $n + 1$ — can always be finished, so the hard cases are all in the middle. An order either fills up almost immediately or gets stuck a long way short, and order ten, stuck at four classes out of eleven, is stuck as far short as an order can be.

That is also the honest reason the small tables of $N(n)$ have the shape they do. The counting that produced Euler’s conjecture was over pairs, and pairs are the first class past the trivial ones; nothing about the difficulty of finding a second square predicts the difficulty of finding a ninth. The geometry says why: the second square is one line-cutting, and the ninth is a line-cutting that has to disagree with eight others at once.

More than one plane at an order #

One more fact, because it is the sort of thing the correspondence makes visible and the squares hide.

The plane an order carries need not be unique. For orders two, three, four, five, seven and eight there is exactly one projective plane, and it is the one the field builds. At order nine there are four — the field’s plane and three others, which satisfy every axiom above and cannot be coordinatised by any field. They are distinguished by a geometric condition, Desargues’ theorem, that the field-built planes satisfy and the others do not.

Translated back, that says there are complete families of eight orthogonal squares of order nine that are genuinely not the family the field builds, and no relabelling turns one into the other. The construction of the previous rung produces a plane; it does not produce all of them.

What the pictures cannot show #

The figures here check the axiom by taking every pair of points and counting the lines through it. At order four that is a hundred and twenty pairs, and the count is exact and complete. That is a check of a plane that exists.

Nothing here draws the non-existence of one. Bruck–Ryser is an arithmetic argument about sums of two squares and has no picture in it; Lam’s search is a picture nobody could look at. The best a figure can do for those is what the previous rung’s figure did for the ceiling — draw the object where it exists, and let the counting argument carry the orders where it does not. This collection is fairly consistent about that boundary: a proof by exhaustion is shown as the exhaustion when it is small enough to fit and is quoted when it is not, and which of the two is happening is always said.

The other thing the pictures cannot show is the size of the search. The panels above cut sixteen points into lines five different ways. The search at order ten was over structures with a hundred and eleven points, and the number of ways to begin is what made the problem forty years old rather than an afternoon.

Where the ladder goes next #

The counting, which has been kept out of both rungs so far and cannot be kept out much longer. There are $576$ Latin squares of order four and $161{,}280$ of order five, and the exact number is known only up to order eleven. Against that, a partial square — a few rows, filled in legally — can always be finished, and the reason is a matching argument that has nothing to do with fields or planes.

The contrast is the point of putting the two next to each other. This rung’s objects are rigid: a complete family exists at an order or it does not, and deciding which took a Cray. A single Latin square is the opposite of rigid — there are more of them than anybody can count, they can be built greedily, and no partial one ever paints itself into a corner. Both statements are about the same grid of $n^2$ cells, and the difference between them is entirely the number of conditions imposed on it, which is a pattern worth watching for: the orders whose value nobody knows in this subject are always the ones where a condition is nearly, but not quite, tight enough to force the answer.