The thirty-six officers

Euler posed the problem in 1782 and stated flatly that he could see no way to do it. He was right about the case he was looking at and wrong about every other case of the kind.

The problem #

Six regiments each send six officers, one of each of six ranks. Arrange the thirty-six in a six-by-six square so that

• every row contains each rank once and each regiment once, and
• every column does too.

Splitting that into two squares makes it a question about a familiar object. A Latin square of order $n$ is an $n \times n$ grid filled with $n$ symbols so that each appears once in every row and once in every column. The officer problem asks for two of them — ranks and regiments — with an extra condition tying them together.

Two Latin squares are orthogonal when superimposing them produces every ordered pair of symbols exactly once. With six ranks and six regiments there are thirty-six pairs and thirty-six cells, so every pair must occur precisely once, which is the officer condition restated.

Where the pairs come from #

For odd orders the construction is one line of arithmetic.

Number the rows and columns $0$ to $n-1$ and set

$$A(i,j) = i + j, \qquad B(i,j) = i + 2j,$$

with everything taken modulo $n$.

Each is Latin: fixing $i$ and varying $j$ runs through all residues, since adding a constant is a bijection, and so does multiplying by $2$ when $2$ is invertible.

They are orthogonal: given a target pair $(a,b)$, solving $i+j = a$ and $i+2j = b$ gives $j = b-a$ and $i = 2a-b$, uniquely — provided the arithmetic allows the subtraction, which it does. One cell per pair, which is the definition.

The step that fails is the invertibility of $2$. Modulo an even number, $2$ is a zero divisor and $B$ is not Latin at all: with $n = 6$, the row $i=0$ reads $0, 2, 4, 0, 2, 4$. So the construction covers every odd order and says nothing about the even ones.

Order $4$ is even and has a pair anyway, built the same way over the field with four elements rather than over the integers mod $4$ — which is precisely the distinction that essay was about. Every prime power works, for the same reason: a field has a $2$ that behaves, unless the field has characteristic two, in which case some other element does.

So orders $3, 4, 5, 7, 8, 9, 11, \ldots$ all have orthogonal pairs, and the doubtful ones are $2, 6, 10, 14, \ldots$ — the numbers that are twice an odd number.

Euler’s conjecture #

Order $2$ obviously fails: there are only two Latin squares of order two and superimposing them repeats every pair.

Order $6$ Euler could not do. From the failure at $2$ and $6$, and the ease at every other order he tried, he conjectured that no pair exists when $n \equiv 2 \pmod 4$ — that is, at $2, 6, 10, 14, 18$ and so on forever.

It was a reasonable guess from the evidence. Two cases had failed, they shared a residue, and the successful construction visibly broke at exactly those orders. It stood for a hundred and seventy-seven years.

What a search can settle here #

The honest position of this page has to be stated plainly, because the famous case is beyond what a page build can decide.

Deciding whether two orthogonal squares of order six exist means searching the pairs of Latin squares of that order. There are $812{,}851{,}200$ Latin squares of order six, and even after reducing by symmetry the search is substantial. Gaston Tarry did it in 1900, by hand, by classifying the squares into families and eliminating each — a year’s work, and the first exhaustive computer-style search predating computers.

Nothing here reproduces that. What the figures can decide is a necessary condition, and the necessary condition is decisive for the square they draw.

A transversal of a Latin square is a choice of one cell in each row and each column such that the symbols chosen are all different. Transversals matter because of a one-line argument:

If $A$ has an orthogonal mate $B$, then for each symbol $s$ of $B$, the cells where $B$ shows $s$ form a transversal of $A$.

Those cells number one per row and one per column, since $B$ is Latin; and the symbols $A$ shows on them are all different, since otherwise the pair $(\text{that symbol}, s)$ would occur twice. So a square with no transversal has no mate at all, and the question is settled without any search over mates.

The figures walk every permutation. At order five that is $120$ placements and fifteen of them work; at order six it is $720$ and none does; at order seven it is $5{,}040$ and $133$ work. The pattern is exactly parity: the cyclic square of even order has no transversal, and of odd order has plenty.

The reason is a two-line count. A transversal picks one cell per row and column, so its cells are $(i, \sigma(i))$ for a permutation $\sigma$, and the symbols are $i + \sigma(i)$. If those are all different, they are all $n$ residues, so summing them gives

$$\sum_i i + \sum_i \sigma(i) = \sum_i (\text{all residues}),$$

which reads $2 \cdot \frac{n(n-1)}{2} \equiv \frac{n(n-1)}{2} \pmod n$. For even $n$ the left side is $0$ and the right side is $n/2$, which is not zero. Contradiction.

That last figure is the essential qualification and the reason the argument here proves less than the famous result. The cyclic square of order four has no transversal, and order four nevertheless has an orthogonal pair. The obstruction is a property of one square, not of the order, and ruling out one square rules out nothing about the rest.

So what the figures on this page establish is precise and limited: the most natural square of order six is disqualified, by a search over all seven hundred and twenty candidates, and the reason is a parity argument that applies at every even order. Euler’s problem is not settled by that, and the page does not claim otherwise.

How many Latin squares there are #

A number is worth putting on the search Tarry did, because the difficulty of the problem is entirely in the size of the space.

Latin squares of order $n$ number $1, 2, 12, 576, 161{,}280, 812{,}851{,}200$ for $n$ up to six, and $61{,}479{,}419{,}904{,}000$ at $n=7$. The counts have no formula; each was obtained by a computation harder than the last, and the largest known is at $n=11$.

Most of that multiplicity is relabelling. Fixing the first row and the first column in increasing order — a reduced square — leaves $1, 1, 1, 4, 56, 9{,}408$ squares for $n$ up to six, and it is the $9{,}408$ that Tarry classified. Even that is a great deal of hand work, and he organised it by sorting the squares into seventeen families and disposing of each.

The gap between $9{,}408$ and $812$ million is the symmetry group of the problem, and exploiting it is the whole technique of an exhaustive search. It is the same manoeuvre the Fano plane’s $168$ symmetries allow, and the same one every modern search program uses: never examine two objects that a relabelling carries onto each other.

The conjecture was wrong #

In 1959 and 1960, Raj Chandra Bose, Sharadchandra Shrikhande and Ernest Parker constructed orthogonal pairs at order $22$, then $10$, then at every order $n \equiv 2 \pmod 4$ with $n \ge 10$.

So the complete answer is: orthogonal Latin squares of order $n$ exist for every $n$ except $2$ and $6$.

Euler’s conjecture was wrong at every case it named beyond the two he could check. Six is not the first member of an infinite family of failures; it is the last member of a finite family of two, and it fails for reasons that stop there.

The three authors were called Euler’s spoilers in the press, and the order-ten construction made the front page of a national newspaper — one of very few combinatorial results to manage that. The proof is constructive: pairs are exhibited, so nothing rests on an existence argument.

What went wrong with the guess #

The failure is worth diagnosing, because it is the standard shape of a wrong conjecture in this subject.

Euler had two data points and a construction that broke at exactly the orders those points occupied. That is a strong pattern by the ordinary standards of pattern-finding: the failures and the construction’s breaking point coincided perfectly.

What the coincidence actually reflected was that his construction was the only one he had. Its breaking at $n \equiv 2 \pmod 4$ was a fact about the formula $i + 2j$ and not about the orders, and the later constructions do not resemble it at all — they glue smaller designs together rather than computing entries from a formula.

Two cases is also a very small sample, and the two available are the smallest, which is where structure is scarcest. There simply are not many Latin squares of order two; the object had no room to be anything. That small cases mislead is a standing theme in this collection, and the officer problem is the sharpest instance in it: a conjecture supported by every case anybody could check, false in every case they could not.

There is a second, subtler warning in the episode, and it is about what an exhaustion proves. Tarry’s search is correct and settles order six completely. What it cannot do is say anything about order ten, because an exhaustive search is a statement about the instance searched and nothing else. Reading it as evidence for the general pattern — which is what Euler’s conjecture did in advance and what a century of acceptance did afterwards — is reading a finite verdict as an infinite one, and that is the mistake this whole field is arranged to avoid. A hundred and seventy-seven years is a long time for such a reading to stand, and it stood because the two verdicts available were both negative and nobody had a construction to try.

The general lesson is not that patterns are untrustworthy. It is that an existence claim and a non-existence claim need different evidence: the first is settled by exhibiting the object, and the second by an argument covering every case, which no finite search over a subset of the cases can supply.

Where the squares turn up #

Latin squares are older than the theory and they arrive from several directions at once, which is worth recording because it explains why the officer problem was considered interesting rather than recreational.

A Cayley table. The multiplication table of any group is a Latin square, because multiplying by a fixed element is a bijection. The converse is false — most Latin squares are not group tables — but every group supplies one, and the cyclic square of order $n$ drawn throughout this essay is the table of addition modulo $n$. The multiplication table of a finite field, with its zero row and column removed, is another.

An experimental design. To test $n$ treatments against two nuisance factors — position in a field and time of day, say — a Latin square arrangement gives each treatment once in every row and column, so neither nuisance can be confounded with the effect. Two orthogonal squares handle three nuisance factors at once, which is what a Graeco-Latin design is for and is the main reason the objects are studied in statistics.

A puzzle. Sudoku is a Latin square of order nine with an extra condition on the boxes, and the counting problems it raises are of exactly the kind above.

A code. A pair of orthogonal squares of order $n$ is a code of length four over $n$ symbols with minimum distance three: the codewords are $(i, j, A(i,j), B(i,j))$, and any two entries determine the other two. That connection runs both ways, and the non-existence at order six is equivalent to the non-existence of a particular small code.

The last of these is the tightest link back to the earlier anchors of this field, and it is not a loose analogy: the equivalence is an exact translation, and the maximum number of mutually orthogonal squares of order $n$ is the maximum size of a certain family of codes.

The complete sets, and the plane #

There is a stronger question behind the officer problem, and it closes the circle with the previous essay.

Squares can be mutually orthogonal in larger families: $A$, $B$ and $C$ pairwise orthogonal, and so on. The maximum possible number of mutually orthogonal squares of order $n$ is $n-1$, by a short counting argument, and:

A complete set of $n-1$ mutually orthogonal Latin squares of order $n$ exists exactly when a projective plane of order $n$ exists.

The translation is direct. Given the plane, delete a line and its points to get an affine plane; its lines fall into $n+1$ parallel classes; two of the classes are the rows and columns of a grid and each remaining class is a Latin square. Given the squares, the construction runs backwards.

So the open problem about which orders admit a plane is the same open problem as which orders admit a complete set of squares, and Tarry’s hand search of 1900 is, in that language, the first proof that there is no projective plane of order six — twelve years before Veblen and Bussey named the objects.

What this field has been about #

This is the last essay of the phase that opened the field, and it is a fair place to say what the field claims.

Every essay in it fixed a set of operations or a set of conditions and asked what could be built. The compass and straightedge reach the numbers expressible with square roots and nothing more. A parity check over the two-element field reaches a code whose distance is decided by a matrix’s columns. A polynomial over a finite field reaches a code meeting the best bound there is. A projective plane exists at every prime power and possibly nowhere else, and a schedule of triples exists exactly when two divisions come out whole.

The answers came in two shapes. Where the question was finite, it was decided by exhaustion and the exhaustion is the figure — every candidate root, every relabelling, every permutation, every word in the space. Where the question was infinite, the figure drew the step and the prose carried the rest, and each essay said which of the two it was doing.

Euler’s officers are the case where the honest answer is that the exhaustion is too large for a page. The necessary condition is checked in full; the famous verdict is Tarry’s and is quoted; and the conjecture built on it turned out to be false, which is the best possible reminder that a pattern holding in every case anyone can check is a pattern and not a theorem.