Nine thousand four hundred and eight

Two rungs of this ladder have asked which Latin squares can be put beside which others — which orders carry an orthogonal pair, and what a complete family of them is. This one asks the flatter question underneath: how many Latin squares of order $n$ are there at all?

The answer is known exactly for $n$ up to eleven and is not known for twelve, and the reason for that boundary is not that anybody lost interest. It is that the count grows faster than the searches do.

The two factorials that come straight back out #

Most of any such count is uninteresting, and the standard move is to divide it out first.

Given any Latin square, its symbols can be renamed so that the first row reads $0, 1, \dots, n-1$ — that is a choice of one of $n!$ renamings — and then its rows below the first can be permuted so that the first column reads in order too, which is $(n-1)!$ choices. Every square arises from exactly one reduced square by exactly one such pair of choices. So

$$L(n) = n! \cdot (n-1)! \cdot R(n),$$

with $R(n)$ the number of reduced squares. All the content is in $R$, and the factorials are bookkeeping.

The reduced counts start $1, 1, 1, 4, 56$, and then $9{,}408$ at order six. Multiplying back gives $576$ squares of order four, $161{,}280$ of order five, and $812{,}851{,}200$ of order six. The first of those is small enough to list outright, and the figure above does exactly that as a check on the arithmetic: the enumeration and the formula agree at $576$, which is the sort of agreement worth arranging, because the formula is the kind of thing that is off by a factorial for years.

The division is also where the first surprise sits. Order five has fifty-six reduced squares and order six has nine thousand four hundred and eight — a jump by a factor of a hundred and sixty-eight for one extra row and column, against a jump of fourteen from order four to order five. The factorials in front grow smoothly and predictably; the interesting factor does not, and the ratio between consecutive reduced counts keeps climbing at every order anybody has reached. Whatever the count of Latin squares is doing, it is not doing it at a rate that the small cases display.

What a search can reach #

Enumerating reduced squares is a backtracking search: fill the cells in order, never repeating a symbol in a row or a column, count the completions. At order six that search finishes in a moment. At order seven the answer is $16{,}942{,}080$ reduced squares, which is still within reach but no longer within a page build; at order eight it is over five hundred billion.

The record is order eleven, computed by McKay and Wanless in 2005, and the reduced count there has thirty-four digits. Getting it needed far more than a faster computer: the search is over equivalence classes rather than over squares, with the symmetries of the problem divided out before the enumeration rather than after, and even then the total is reached by counting classes and multiplying by their sizes.

That is the standing pattern for this kind of question. A brute-force search buys two or three orders and then stops; the structure of the object has to be used to buy any more; and the boundary between the last order that is known and the first that is not moves about once a decade. It is the same boundary an exhaustive proof runs into from the other side, and the same one that makes enumerating every order of arrival hopeless past a dozen players.

How fast it actually grows #

The exact numbers stop at eleven, but the growth rate does not have to.

Counting the ways to add one row to a partly-filled square is counting the perfect matchings in a bipartite graph, and that number is the permanent of a matrix of ones and zeroes — the determinant with all its minus signs removed. Removing the signs removes everything that makes a determinant computable: there is no elimination for a permanent, because there is no cancellation to exploit. So the number of Latin squares is a product of permanents, and the two classical bounds on permanents become bounds here.

The upper bound is Brégman’s, proved in 1973: a matrix of ones and zeroes with $r_i$ ones in row $i$ has permanent at most $\prod_i (r_i!)^{1/r_i}$. The lower bound is the van der Waerden conjecture, proved by Egorychev and Falikman in 1981: a doubly stochastic matrix has permanent at least $n!/n^n$. Together they pin the count between

$$\frac{(n!)^{2n}}{n^{n^2}} \ \leq\ L(n) \ \leq\ \prod_{k=1}^{n} (k!)^{n/k}.$$

At order six the lower bound is about $1.9$ million, the upper about $7.6$ billion, and the truth — $812{,}851{,}200$ — sits between them, some four hundred times the lower bound and about a ninth of the upper. Both bounds are correct and neither is close, which is what a factor of $n^{n^2}$ does to a comparison.

What the two together do establish is the shape: the $n^2$-th root of $L(n)$ behaves like $n/e^2$, so the count is roughly $(n/e^{2})^{n^{2}}$ for large $n$. The convergence is slow enough that this is useless as a numerical estimate at any order anybody has enumerated — at eleven it is out by many orders of magnitude — and it is nevertheless the right statement, because it is the statement that holds for every $n$ rather than the one that fits the eleven that are known. Counting partitions has the same two-part shape — exact values by recursion, an asymptotic that is only eventually accurate — and in that subject the two halves were found sixty years apart.

A rectangle never gets stuck #

Set the counting aside for the opposite question. Suppose $k$ rows of an $n$-column grid have been filled legally — no symbol twice in a row, none twice in a column. Such a thing is a Latin rectangle. Can it always be completed to a full Latin square?

It can, always, and the proof is a matching.

Build a bipartite graph: the columns on one side, the symbols on the other, and an edge from a column to each symbol that column has not yet used. A new row is exactly a perfect matching in that graph — one symbol per column, no symbol twice. So the question is whether the graph has one, and Hall’s theorem answers it, in the form a bottleneck makes visible: a matching exists exactly when no set of columns has fewer available symbols between them than there are columns in the set.

Why the graph cannot fail #

Hall’s condition holds here for a reason that needs no search at all, and it is a double count.

Each column has $k$ symbols used and $n - k$ available, so every column vertex has degree $n - k$. Each symbol appears once in each of the $k$ filled rows, so it has been used in exactly $k$ columns and is available in exactly $n - k$ — so every symbol vertex has degree $n - k$ as well. The graph is regular.

In a regular bipartite graph, a set $S$ of columns has $|S| \cdot (n-k)$ edge-ends leaving it, and every symbol it reaches can absorb at most $n - k$ of them, so at least $|S|$ symbols are reached. That is Hall’s condition, established by counting edges twice rather than by examining any particular graph — and it is the same argument that says a regular bipartite graph splits into perfect matchings, which is a way of saying that the whole remaining square can be filled row by row without ever backtracking.

The counting-argument nature of that proof is worth pausing on. It says nothing about which square gets built and offers no way to build a particular one, and it cannot fail on any input, which means it can offer no insight into why some orders are harder than others. It is the flattest possible good news.

The last row, and the ones before it #

The extension argument gives more than existence. When $k = n - 1$ every column has one symbol left, so the matching is forced and the final row is unique — a Latin square is determined by all but its last row.

Below that the choices proliferate. Marshall Hall’s 1945 argument shows that a $k \times n$ rectangle has at least $\prod_{j=1}^{n-k} j!$ completions, so the number of ways to finish grows factorially as the rows are removed, and at $k = n-1$ the product is $1!$, which is the uniqueness above. That bound is where the lower bound on $L(n)$ in the previous section ultimately comes from.

Counting classes instead of squares #

The order-eleven computation was not a bigger version of the order-six one, and the difference is where the interest in the counting actually lies.

Three operations turn a Latin square into another Latin square without changing anything essential: permuting the rows, permuting the columns, and renaming the symbols. Two squares related by those are isotopic, and the reduction from $L(n)$ to $R(n)$ at the top of this essay is a crude version of dividing by them. There is a fourth operation that is stranger and just as harmless: a Latin square is a set of $n^2$ triples — row, column, symbol — with the property that any two coordinates determine the third, and that description is symmetric in the three coordinates. So the roles can be permuted, giving six conjugates of each square, and squares related by an isotopy followed by a conjugation are in the same main class.

At order four there are two isotopy classes among the $576$ squares; at order five, two again; at order six, twenty-two, and twelve main classes. Those are small numbers hiding behind enormous ones, and they are the counts an enumeration should actually chase: build one representative of each class, count how large its class is, and multiply. That is why order eleven is known at all.

The three-coordinate description also settles something that the grid makes look asymmetric. The rows, the columns and the symbols of a Latin square are interchangeable, so every theorem about rows is automatically a theorem about columns and about symbols. The extension theorem above says a set of complete rows extends; by conjugation it also says that a set of complete symbols — a partial square in which some symbols have been placed everywhere they go and the others nowhere — extends as well. Neither statement is harder than the other, and only one of them has to be proved.

Where the easy part stops #

Everything above is about rows. Fill in cells anywhere, and the picture changes completely.

A partial Latin square with cells filled in arbitrary positions can be impossible to complete, and it does not take many cells. Put the symbols $1$ through $n-1$ along the first row’s first $n-1$ cells, and put the symbol $n$ in the second row’s last cell. That is $n$ filled cells, all legal. The first row’s last cell must now be $n$, since every other symbol is spent in that row — and the last column already holds an $n$. Nothing can be written there.

The remarkable thing is how sharp that is. Any partial Latin square of order $n$ with at most $n - 1$ cells filled can be completed, whatever the positions. That was conjectured by Trevor Evans in 1960 and proved by Smetaniuk in 1981, and independently by Andersen and Hilton; and the example above shows that $n - 1$ cannot be improved to $n$. One cell is the difference between a theorem and a counterexample.

Deciding whether a given partial square can be completed, in general, is a genuinely hard computational problem — that is a result of Colbourn’s from 1984, and the cost of procedures belongs to a different collection than this one. What matters here is the shape: filling by rows is trivially always possible, filling by arbitrary cells is not, and the boundary between them falls at $n-1$ cells.

What the counting cannot show #

The figures on this page enumerate where enumeration is possible, and the honest boundary is drawn in the drawing itself: the bars for orders seven and eight are a different colour, because those numbers were quoted from the literature rather than counted here. That distinction is worth keeping visible. A figure that mixes measured and quoted values without saying which is which invites the reader to trust both equally, and only one of them was checked.

Nothing here draws the growth rate. Asymptotics are statements about all large $n$, and the largest order any picture on this page reaches is eleven, at which the asymptotic estimate is wrong by a factor bigger than the count of atoms in anything. The bar chart shows a straight line on a logarithmic scale over eight orders, which is a shape that could be produced by half a dozen different growth rates; it is evidence that the count grows fast and is no evidence at all about the exponent.

And the extension figures show one rectangle each. The theorem is about every rectangle of every order, and what makes it true — the regularity of the availability graph — is a counting argument that no drawing can exhibit in general. The figures do check Hall’s condition exhaustively over all $2^n - 1$ sets of columns at the order drawn, which is the strongest thing a picture can do here: it verifies the hypothesis rather than illustrating the conclusion.

Where the ladder goes next #

The last rung leaves orthogonality and geometry behind entirely and asks what a Latin square is when nothing is placed beside it. It is a multiplication table — the table of a system where every equation $a \cdot x = b$ has exactly one solution — and among the $576$ tables of order four, the ones that also happen to be associative can be counted. There are sixteen, and the groups they represent are two.