A field's worth of squares

Euler’s officers leave a question behind that the failure at order six rather hides. Two Latin squares are orthogonal when laying one on the other produces every ordered pair of symbols exactly once. At order six there is no such pair at all. At order five there are pairs, and the obvious next question is how many squares can be put together so that every pair among them is orthogonal — three squares, four, as many as the order will bear.

Stumbling on one pair is luck. A family of four, checked in all six of its pairings, is not something to stumble on, and the construction that produces it is a single line of arithmetic.

One line of arithmetic #

Number the rows and the columns by the elements of a field with $q$ elements, and fill the cell in row $i$ and column $j$ of the square belonging to the multiplier $a$ with

$$L_a(i, j) = a \cdot i + j.$$

That is the whole construction. There is one square for each non-zero $a$, so there are $q - 1$ of them, and the claim is that every pair among them is orthogonal.

Each square is Latin before anything else is asked of it. Fix a row — fix $i$ — and the map $j \mapsto a i + j$ adds a constant to every symbol, which shuffles the field without repeating anything. Fix a column instead and the map $i \mapsto a i + j$ multiplies by $a$ and then adds a constant; multiplying by a non-zero element of a field is invertible, so again nothing repeats. The multiplier has to be non-zero or the row index does nothing at all and every row of the square comes out the same.

Why the pairs come out right #

Take two of the squares, belonging to multipliers $a$ and $b$ with $a \neq b$, and pick any ordered pair of symbols $(u, v)$. The question is whether some cell carries $u$ in the first square and $v$ in the second, and whether it is the only one. That is two equations in two unknowns:

$$a i + j = u, \qquad b i + j = v.$$

Subtract the second from the first. The $j$ cancels, and what is left is $(a - b) \, i = u - v$. Because $a \neq b$, the coefficient $a - b$ is not zero; because the arithmetic is a field’s, a non-zero element can be divided by; so $i$ is determined, and then $j = u - a i$ is determined too. One solution, always, and never two.

That is the entire proof, and it is worth noticing what it used. It used that a non-zero difference can be inverted. Everything else — commutativity, distributivity, the existence of a zero — is scaffolding around that one step, and the step is exactly the property that separates a field from an arithmetic that merely wraps.

Where wrapping is not enough #

The clock arithmetics — the integers modulo $n$ — look like fields and mostly are not. Modulo six, the multiplier $2$ has no reciprocal, because two threes make six, which is zero on a dial of six, and a number that multiplies something non-zero down to zero can have no inverse. Those are the zero divisors, and they are what a composite modulus has and a field does not.

Follow the construction anyway, modulo six, and watch it fail twice over. The square $L_a$ is Latin only when $a$ has an inverse, so only $a = 1$ and $a = 5$ are available at all. Those two squares are then orthogonal only if $5 - 1 = 4$ can be inverted modulo six, and $4$ shares the factor $2$ with $6$. The construction supplies no pair at order six, which is the right answer, arrived at by the wrong reasoning — the true statement, that no pair of orthogonal squares of order six exists by any construction, needed Tarry’s year of exhaustion and not this paragraph.

At order four the point is sharper still, because there the arithmetic that works is not the clock. In the integers modulo four, two multiplied by itself is zero; the field with four elements is a different object built on the same four symbols, and the three squares in the opening figure come from it. A reader who tries the construction on the clock at order four gets one Latin square and two that are not.

The ceiling nobody can raise #

How many mutually orthogonal squares can an order $n$ carry, whatever the construction? The answer is at most $n - 1$, and the argument is a relabelling and a pigeonhole.

Relabelling the symbols of one square — swapping every $2$ for a $5$ and so on — cannot make an orthogonal pair stop being orthogonal, since it merely renames the pairs that already occur once each. So assume each square in the family has been relabelled so that its first row reads $0, 1, 2, \dots, n-1$ in order. Every square now agrees along its top row, which means that every pair of equal symbols has already been used up there: the cell in row $0$ and column $s$ carries $s$ in every square.

Now look at the cell directly under the top left corner. In any one square its entry cannot be $0$, because $0$ already stands above it in that column. And two different squares cannot both carry the same symbol $t$ there, because the pair $(t, t)$ was already spent in the top row. So the entries in that one cell are distinct, non-zero, and drawn from $n$ symbols — leaving at most $n - 1$ squares.

The construction over a field produces exactly $q - 1$ squares, so at every prime power it hits this ceiling. That is a satisfying coincidence and it is not a coincidence at all; the next rung of this ladder is about what a family of $n-1$ squares actually is, and the answer explains both halves at once.

The orders where the ceiling is reached #

Write $N(n)$ for the largest number of mutually orthogonal squares of order $n$. The construction settles every prime power: $N(q) = q - 1$ whenever $q$ is a prime or a power of one, since the field exists and the ceiling forbids more.

Off the prime powers the picture is thin and stays thin. $N(6) = 1$, which is Tarry’s exhaustion. $N(10)$ is known to be at least $2$ and at most $8$, and the true value has been unknown since the question was asked. $N(12)$ is at least $5$. There is no order $n > 6$ for which $N(n) = 1$ — every such order carries at least one orthogonal pair — and that fact is the corpse of Euler’s conjecture, established by Bose, Shrikhande and Parker in 1959 and 1960.

The construction here is old. It appears in work of E. H. Moore in the 1890s and was put in this form by Bose in 1938, a hundred and fifty years after Euler asked about his officers, which is a fair measure of how much easier the positive half of this subject is than the negative half.

Two families multiplied together #

There is a second construction, and it is the reason the composite orders are not simply blank. Given a family of squares of order $m$ and a family of order $n$, the cells of an $m \times m$ square can each be replaced by a whole $n \times n$ square, with symbols taken from the pairs. What comes out is a family of order $mn$, and its size is the smaller of the two sizes it was built from:

$$N(mn) \ \geq\ \min(N(m), N(n)).$$

Applied to $12 = 4 \times 3$ this gives $N(12) \geq 2$, since $N(4) = 3$ and $N(3) = 2$. Applied to $10 = 2 \times 5$ it gives $\min(1, 4) = 1$, which says nothing at all, because the factor two contributes nothing and the bound is only as good as its worst factor.

MacNeish conjectured in 1922 that this bound is the whole truth — that $N(n)$ is exactly the minimum of $p^e - 1$ over the prime powers in the factorisation of $n$. It is a natural guess, it holds at every order small enough to check by hand, and it is false. Order ten is the counterexample: the bound gives $1$ and the answer is at least $2$. The same pair of squares that killed Euler’s conjecture killed MacNeish’s, which is unusually good value for one counterexample.

What the counting costs #

The figures here decide the orthogonality rather than asserting it, and the arithmetic of that is worth stating, because it is the reason the check is possible at all and the reason it stops.

Checking one pair of squares of order $n$ means forming $n^2$ ordered pairs and asking whether they are all different — cheap. Checking a whole family means doing that for every pairing, and a family of $n - 1$ squares has $(n-1)(n-2)/2$ of them. At order four that is three pairings and forty-eight symbol pairs; at order seven it is fifteen pairings; at order thirty-two it would be four hundred and sixty-five pairings of a thousand cells each, which is still nothing.

What is not nothing is searching for such a family rather than constructing one. The number of Latin squares of order $n$ grows faster than any exponential, which is the subject of a later rung on this ladder, and the failure at order six was settled by exhaustion only because six is small. Constructions scale; searches do not. The whole reason the field is interesting here is that it replaces a search with an arithmetic.

The same family, wearing three other hats #

A complete family of squares turns up in three places that have nothing obvious to do with one another, and the arithmetic above is the whole of what they share.

The oldest is experimental design. To test $n$ treatments in a field divided into $n$ rows and $n$ columns, where the soil varies along both, a Latin square arranges the treatments so that each appears once in every row and once in every column — so any systematic difference between rows, or between columns, is spread evenly over the treatments rather than confounded with one of them. Fisher made this standard in the 1920s. Add a second, orthogonal square and a second factor can be tested at the same time, with every combination of the two occurring exactly once, and the analysis stays as simple as it was for one.

The second is scheduling, and it is the design of triples seen from a different angle: a family of orthogonal squares of order $n$ is a way of arranging $n^2$ competitors into rounds so that no two ever meet twice. Rows are one round, columns are another, and each square supplies one more. The ceiling of $n - 1$ squares is then the statement that there are at most $n + 1$ such rounds, which is a fact about tournaments derived from a fact about relabelling.

The third is coding. Read each cell of the plane as a message of two symbols — its row and its column — and each square as one check symbol computed from them. Every square is one more redundant symbol, and orthogonality says exactly that two messages agreeing in any two of their coordinates are the same message. That is a code in which any two coordinates determine the rest, which is the extreme case of the trade between redundancy and distance, and it is the same object a polynomial through the gaps arrives at from the other side — polynomials of low degree over the same field, evaluated at every point of it. The two constructions are one construction: $a i + j$ is a polynomial of degree one in $i$, and the squares are its evaluations.

That last coincidence is the honest reason to care about the ceiling. A bound on how many squares an order can carry is simultaneously a bound on how many check symbols a code of that shape can have, and on how many rounds a tournament can run — and it was proved by looking at one cell.

What the pictures cannot show #

Every figure on this page is one order. The claim is about all prime powers, and no drawing settles a claim about infinitely many orders — what the drawings do is check the construction where it can be checked, which is what a figure in this field is for.

The second limit is subtler and matters more. The pictures show families that exist; they can say nothing about the orders where none does, because a drawing of an object that does not exist is a drawing of nothing. The ceiling argument is the exception, and it is the exception precisely because it is a counting argument: it is about the symbols a cell may take, and it applies to families nobody has ever seen as easily as to the three squares at the top of the page. The pigeonhole is the only tool in this essay that says anything about the orders where the answer is unknown.

Where the ladder goes next #

A complete set of $n - 1$ squares turns out not to be a lucky collection of squares. It is a geometry — a plane with $n^2$ points, in which every two points lie on exactly one line — and the rows, the columns and each square’s symbol classes are its lines. That correspondence is exact in both directions, and it is what turns a question about arrangements into a question about geometry: seven points and seven lines is the smallest case, a schedule where every pair meets once is the same object doing a different job, and the orders at which no plane exists are the orders at which the ceiling cannot be reached.

That is where order ten’s answer eventually came from, and it is the next rung. Further up, the counting: how many Latin squares of order $n$ there are, why the exact answer stops at eleven, and why a partial square can always be extended one row at a time even though the total is beyond enumeration. And beyond that, what a Latin square is when nobody is looking for orthogonality — the multiplication table of an algebra with division and, almost never, with associativity.