A mate is rare until order ten

The thirty-six officers began with Euler’s question: can thirty-six officers, six ranks from each of six regiments, stand in a square so that every row and column holds every rank once and every regiment once? That is asking for two Latin squares of order six that are orthogonal — laid on top of each other, every pair of a rank and a regiment occurs exactly once — or, put another way, for a Latin square with an orthogonal mate. Gaston Tarry showed in 1900 that no square of order six has one. Euler had guessed the same for every order two more than a multiple of four, and in 1959 Bose, Shrikhande and Parker showed he was wrong: there are orthogonal pairs of every order except two and six.

Those results are about whether some square of a given order has a mate. Orthogonal squares are a code and its predecessors built mates for the squares that have them, the tables of fields and groups, and one cell short of a transversal noted that a square can have transversals and still have no mate. This essay asks the question the other way round. Take a Latin square at random, every square of its order equally likely. Does it have a mate? The answer, order by order, does not do what a sequence of small cases suggests.

What a mate is made of #

A square $A$ has an orthogonal mate exactly when its cells can be split into $n$ transversals that share no cell. A transversal picks one cell in every row and every column, with every symbol of $A$ different. Given a mate $B$, the cells where $B$ shows any one symbol form a transversal of $A$, since $B$ is Latin and since each pair occurs once; and given $n$ disjoint transversals of $A$, writing a different symbol on each of them produces a mate. So the question is about transversals: a square has a mate when $n$ of them fit together without overlapping.

The square in the figure has 848 transversals, and the mate is ten of them chosen to cover every cell once. Finding them is an exact-cover search: every transversal passes through exactly one cell of the first row, so the search takes the first row’s cells in order, tries every transversal through the next one that avoids the cells already used, and backtracks when none does. The search is exhaustive, so when it fails, the square has no mate.

The squares known to have mates are mostly built to have them. For an odd order the addition table modulo $n$, with entry $i + j$ in row $i$ and column $j$, has the mate $i + 2j$: the cells where $i + 2j$ takes one value form a transversal, because doubling is one-to-one when $n$ is odd. For an order that is a prime or a power of a prime, a field’s worth of squares gives a whole family of $n - 1$ squares, every two orthogonal, which assemble into a finite plane. The constructions of Bose, Shrikhande and Parker that settled every other order glue smaller orthogonal pairs together. All of these produce particular squares with mates. None says anything about a square that nobody built — which is what a random square is.

The two kinds of square of order five #

The smallest orders can be settled completely, because every square can be checked. Each Latin square comes from exactly one reduced square — first row and first column in order — by permuting its rows and columns, and the same number of squares comes from each, so the share among reduced squares is the share among all squares.

At order four, one of the four reduced squares has a mate: the table of the group with two generators of order two, which sixteen of five hundred and seventy-six met as one of the two groups of order four. The other three are versions of the cyclic table, which has no transversal at all. At order five, 6 of the 56 reduced squares have a mate, 10.7% of all squares. They are the versions of the addition table modulo five, with 15 transversals that split into five in several ways. The other 50 have exactly 3 transversals each, and all three pass through one common cell — so no two of them are disjoint, and five disjoint ones are out of the question, although every one of the 50 has transversals. At order six none of the 9,408 reduced squares has a mate, as Tarry’s search found by hand and computers have confirmed many times since. The failure there comes in two strengths. 2,100 of the reduced squares have no transversal at all, the parity obstruction that also stops the even cyclic tables; the other 7,308 have transversals, as many as 32, and still cannot fit six together. Order six is the only order at which every square fails, and the only one at which the reason is a theorem about all squares rather than a property of particular ones.

Choosing a square fairly #

From order seven on there are too many squares to check — about $6 \times 10^{13}$ of order seven alone — so the share has to be estimated from squares chosen at random. Choosing a Latin square uniformly at random is harder than it sounds. Filling cells at random and backtracking produces some squares much more often than others. The standard method, found by Mark Jacobson and Peter Matthews in 1996, is a random walk: start from any square, change it by a small move that rearranges a few cells, and repeat until the walk has forgotten where it began. Like any walk designed to sample a distribution, it is built so that in the long run every square is visited equally often.

Jacobson and Matthews proved two things about their walk: that it can reach every Latin square of the order from every other, and that its moves are balanced, each as likely to be undone as to be made, so that in the long run it spends the same time at every state it visits. Those are the two conditions under which a chain runs the same backwards and settles to an even distribution. How long “the long run” is has not been proved for this walk; in practice a few times $n^3$ moves between samples suffices, and the test below checks the whole procedure at order four, where every square can be counted.

The walk has one peculiarity. Some of its moves pass through improper states, which are not Latin squares at all — one cell holds, in effect, minus one copy of a symbol — and the next move always leaves them. How samples are read off the walk then matters, and the obvious way is wrong.

Continuing until the walk next stands on a genuine square — the natural way to deal with the improper states — gives some squares of order four ten times as often as others, a spread eight times larger than chance allows. Looking at fixed times and simply discarding the improper ones gives every square about equally often. The walk spends time evenly over genuine squares, but the square it happens to stand on when an improper detour ends is not a fair draw: some squares are more likely than others to be where detours end. Every random square in the figures below was taken the fair way, and the difference matters: in a first run of these computations, read the natural way, the share of mates at order nine came out several times smaller than the fair figure, and at order seven a third smaller.

One in a hundred, then three in five #

The exact shares are a quarter at order four, 10.7% at order five and nothing at order six. Then the random samples take over. Of 4,000 squares of order seven, 43 have a mate, about 1.1%. Of 2,500 of order eight, 8 do, 0.3%. Of 1,500 of order nine, 23 do, 1.5%. Through order nine the evidence says that a random Latin square almost never has a mate, and a reasonable guess from it is that the share goes to nought as the order grows: the squares with mates look like special cases, the tables of groups and their relatives, in a population that grows far faster than they do.

Then, at order ten, 73 of 120 squares drawn at random have a mate: 61%, with a 95% range from 52% to 69%. The order at which Euler’s conjecture predicted no mates at all — ten is two more than a multiple of four — is the first at which most squares have one. Each of those mates was found by the exhaustive search and checked: in the hero figure, all hundred pairs of digits occur once.

The jump from 1.5% to 61% between nine and ten is too large to be a fluctuation of the samples, and it is not a defect of the sampler, which the order-four test checks. The squares of order ten are simply different in how readily their transversals fit together. A smooth trend in orders seven, eight and nine was not a trend at all — the kind of lesson small cases keep teaching about Latin squares, whose numbers grow so fast that each order is a different population.

How close the others come #

The squares without a mate do not miss by much, and they miss by less as the order grows.

A square cannot hold $n - 1$ disjoint transversals without holding $n$. The $n - 1$ transversals use $n - 1$ cells in every row and column and $n - 1$ copies of every symbol, so the $n$ cells left over contain one cell in every row, one in every column, and one copy of every symbol: they are a transversal themselves. So the most a square without a mate can hold is $n - 2$.

At order seven, 29% of the squares without a mate reach that ceiling of five disjoint transversals; the rest stop at four, three or two. At order eight, 76% reach six. At order nine every one of the 300 squares checked reaches seven: every square of order nine without a mate is two transversals short of a mate and holds as many disjoint ones as a square without a mate possibly can. The failures are failing as narrowly as a failure can. That is consistent with the jump at ten, where most squares no longer fail at all, and it suggests that the obstacle at order nine is a final, very constrained step rather than a shortage of transversals.

More transversals help, but do not decide #

The obvious explanation for the jump would be the number of transversals. A random square of order seven has about 20 of them on average, of order eight about 61, of order nine about 214, and of order ten about 825 — a growth faster than exponential, which the theory of transversals in random squares predicts.

Squares with mates do have more transversals: at order nine the median square with a mate has 225 against 213 without; at order ten, 828 against 808. But the ranges overlap almost completely. Plenty of squares with many transversals have no mate, and squares with fewer have one. At order nine the comparison is lopsided — 23 squares with a mate against 1,477 without — yet their medians differ by barely a twentieth, and at order ten by less than a fortieth. The count alone does not decide, which is why the exact-cover search has to be run on every square, and why the jump at ten is not explained by the transversal count crossing some threshold. Something about how the transversals sit relative to each other changes, and the samples show its effect without showing its cause.

What the samples can and cannot say #

A share estimated from random squares comes with an uncertainty that depends on how many were drawn, and the bars in the share figure are that uncertainty: ranges built so that, over many repetitions of the sampling, 95 in 100 of them would contain the true share. At order seven, 43 mates in 4,000 squares pins the share between 0.8% and 1.4%; at order ten, 73 in 120 pins it between 52% and 69%. The ranges at seven, eight and nine overlap each other but none overlaps order ten’s. That separation is the finding, and it would survive samples many times larger.

The cost is in the larger orders. A square of order ten takes the exact-cover search about a third of a second when it has a mate and longer when it has none, because the search must exhaust every combination before concluding; 120 squares took about forty seconds. That is why order ten has the smallest sample, and why the essay stops there. The orders beyond have squares with thousands of transversals each, and an honest estimate of their share would need thousands of squares.

Squares that can never be mated #

Some squares of every order lack a mate, and the reason is sometimes visible. The cyclic square of even order — the addition table modulo an even number — has no transversal at all, by a parity argument over its symbols, and so no mate. Ian Wanless and Bridget Webb showed in 2006 that Latin squares without orthogonal mates exist at every order except one and three. So no order makes a mate automatic; what changes from order to order is how common the exceptions are.

The question of what happens for large orders is open. Mates exist for some square of every order from seven on, and it is natural to ask whether almost every square has one, as order ten suggests, or almost none, as seven to nine suggested. The samples at order ten are the first evidence for the first answer, and they are a sample of a population of about $10^{37}$ squares; at order eleven the exact-cover search for a square with a few thousand transversals is still quick, but drawing enough random squares to estimate a share is where the cost lies.

Still open: whether almost every square has a mate #

It is not known whether the share of Latin squares of order $n$ with an orthogonal mate tends to one, to nought, or to neither. The theory of random Latin squares has made progress on transversals — almost every large square has many, and, since 2023, every large square comes within one cell of having one — but a mate needs $n$ disjoint transversals covering everything, which is a much stronger requirement, and the methods that find many transversals do not show that they fit together. A proof that almost every square has a mate would also say something about the structure of transversals that no current argument reaches. A proof of the opposite would have to explain order ten as an exception, and the samples give no hint of what kind of exception it could be: the squares of order ten with mates are not marked out by their transversal count, nor by anything else the figures measure, and nothing in orders seven to nine announced them.

The finite cases are open too. Estimates beyond order ten need many more random squares than this essay drew, and how the share behaves at orders eleven and twelve — whether order ten begins a climb or is itself an exception — has not been measured here. And the question that started the subject has a smallest open case of its own: whether three mutually orthogonal Latin squares of order ten exist, which no search has settled, although, as the samples show, a single square of order ten usually has at least one mate.