The fewest entries that fix a Latin square

Nine thousand four hundred and eight counted the Latin squares of each small order and ended with a theorem about filling in: any partial Latin square of order $n$ with at most $n - 1$ entries can be completed, whatever the positions, while $n$ well-chosen entries can make completion impossible. That is a statement about too few entries — so few that they cannot get in each other’s way. This essay asks about the other end of the same scale. How few entries are enough to fix a square, so that exactly one Latin square agrees with them?

The question has a famous relative. A Sudoku is a Latin square of order nine with an extra rule about boxes, and a Latin square with boxes recounted how a search of every grid established that seventeen clues are the fewest that can pin one down. Without the boxes the question is older and in some ways cleaner. A set of revealed entries that forces the whole square is a defining set; one from which no entry can be removed without losing uniqueness is a critical set; and John Nelder conjectured in the late 1970s that the smallest critical set of any square of order $n$ has exactly $\lfloor n^2/4 \rfloor$ entries — a quarter of the square.

Six entries, twenty-five answers #

The figure takes the cyclic square of order 5, whose entry in row $i$ and column $j$ is $i + j$ reduced modulo 5 (shown as 1 to 5), and reveals six of its entries: the symbols in the cells $(0,0)$, $(0,1)$ and $(1,0)$, and in the three cells at the opposite corner. A completion search — fill an empty cell with fewest candidates, try each candidate, backtrack on contradiction — finds exactly one Latin square agreeing with them. Every set of five cells of this square, all 53,130 of them, leaves at least two squares possible.

The test for uniqueness is itself a small search, and its shape matters for what the figures can afford. Each row and each column is stored as a five-bit mask of the symbols it already holds, so the candidates for a cell are the symbols missing from both masks, found in one operation. The search fills the cell with fewest candidates, tries each, and stops the moment it has found two completions — two is all it needs to know. For a defining set that stop never comes and the search ends after one completion; for most non-defining sets it ends after a handful of steps. That is why testing all 53,130 sets of five cells takes a fraction of a second, and why the same test at order 6, with a hundred million sets to try, does not.

The right-hand square shows that no search is even needed once the six entries are given. In the first round, the cells with only one symbol left — or the symbols with only one cell left in their row — are filled; that creates more such cells; and five rounds of these forced moves fill the whole square. Each forced entry is the square’s own, as the figure checks. So the six entries are not merely enough in principle: they lead a solver to the answer without a guess, the way a well-made puzzle does.

They are also critical. Remove any one of the six and at least two squares fit what remains. The two triangles hold each other up: the top-left triangle fixes the first two rows and columns only in combination with the bottom-right one, and vice versa.

Every square to order five #

The census runs the same exhaustive test on every square of orders 2 to 5. It is enough to test the reduced squares, those whose first row and first column are in order, because renaming symbols and permuting rows and columns carries defining sets to defining sets. There are 1, 1, 4 and 56 reduced squares of these orders, and for each the search tries every set of cells, smallest first, until one forces the square.

The smallest over all squares of each order is 1, 2, 4 and 6 — exactly $\lfloor n^2/4 \rfloor$, as Nelder conjectured. But the squares do not all reach it. At order 4 the three reduced squares built like the cyclic group need 4 entries, while the square of the Klein group — the table of $(a, b) \mapsto a \oplus b$ on two-bit numbers — needs 5. At order 5, the 6 reduced squares of the cyclic kind need 6, and the other 50 need 7. The squares that are easiest to pin down are the most symmetric ones, which looks backwards: symmetry, one would think, means more ways to be confused with something else.

The explanation is in what a defining set must defeat. A partial square fails to be defining when some other Latin square agrees with it, and the other square differs from the true one on a set of cells called a trade — a pattern of entries that can be replaced by a different pattern while keeping every row and column legal. A defining set must reveal at least one cell of every trade. Squares that are the multiplication tables of groups have their trades arranged regularly, so that a few well-placed entries hit many of them at once; squares without that structure have trades scattered irregularly, and catching all of them takes more entries.

Critical sets come in many sizes #

A critical set is a set from which nothing can be removed, and that does not make it small. At order 4 there are few enough subsets — $2^{16} = 65{,}536$ — to test them all, find every defining set, and keep the minimal ones. The cyclic square has 32 critical sets of 4 entries, 576 of 5 and 128 of 6. The Klein square has 96 of 5, 432 of 6 and 48 of 7.

The largest critical sets reveal close to half the square, and still every entry in them is essential: removing any one admits a second square. They are the Latin-square version of a puzzle with many clues and no redundant one, and their existence is why the question is about the smallest critical set — a set that cannot be thinned can be very far from the thinnest. For larger orders the spread widens further, and critical sets covering well over half the square are known alongside the conjectured quarter.

Two triangles at every order #

Exhaustive search over sets of cells stops at order 5: at order 6 there are $\binom{36}{9}$, about 94 million, sets of nine cells, each needing a completion search. But the shape of the order-5 answer suggests a construction, and the figure checks it at orders 6 to 9. Reveal, in the cyclic square of order $n$, the entries with $i + j < m$ — a triangle in the top left corner — and the entries with $i + j > 2(n - 1) - m'$, a triangle in the bottom right, with the two sizes chosen so the total is $\lfloor n^2/4 \rfloor$. For each order the completion search finds exactly one square, and removing any single entry admits a second.

That the two triangles always work was shown by Diane Curran and Jacobus van Rees in 1978, for the back-circulant square at every order. Nelder’s conjecture is the converse claim, that no square of order $n$ — cyclic or not — has a critical set smaller than this. It has been confirmed by computation for the small orders, and lower bounds of a much weaker kind have been proved in general, the best of them growing only slightly faster than $n$ itself, far below $n^2/4$.

How the triangles force everything #

The deduction in the hero figure shows the mechanism, and it is worth following for the triangles in general. In the cyclic square, the symbol in cell $(i, j)$ is $i + j$. The top-left triangle reveals the cells with $i + j < m$, so the revealed symbols are exactly $0, 1, \ldots, m - 1$ arranged on anti-diagonals: symbol $s$ appears in the top-left triangle at the $s + 1$ cells with $i + j = s$. The bottom-right triangle reveals the high symbols on their anti-diagonals in the same way.

Now look at the first row. It contains the revealed symbols $0, 1, \ldots, m - 1$ in its first $m$ cells and, if the bottom-right triangle reaches it, nothing else. The cells of the first row further right must hold the symbols $m, \ldots, n - 1$, and which one goes where is decided by the columns: a column that already shows a high symbol near its bottom cannot take it again. Each forced entry in turn removes a candidate from its row and column, and the deductions spread inwards from both corners until they meet. A triangle that is too small leaves a band in the middle where two symbols can swap — exactly a trade the revealed entries fail to hit — and the size $\lfloor n^2/4 \rfloor$ is where the two triangles together leave no such band.

Random entries take far more #

The six entries of the hero figure are carefully chosen, and a random choice does much worse. With nothing revealed, every one of the 161,280 Latin squares of order 5 is possible. Revealing four random entries of the cyclic square leaves a median of 448 squares; eight leaves 6; ten leaves 2. Not until eleven random entries does more than half the trials leave a single square, and it takes about fourteen before almost every trial does.

The reason is waste. A random set of entries puts some of them in rows and columns that are already constrained and leaves some small trade somewhere untouched — the commonest culprit is a single 2 × 2 swap, discussed next — and one untouched trade is enough to leave two squares. The chosen six place every entry where it removes a possibility nothing else removes. In this sense a minimum critical set is a perfectly efficient piece of information: six symbols, each worth exactly what it costs.

Every small swap must be blocked #

The simplest trade is an intercalate: two rows and two columns whose four cells hold only two symbols, $a$ and $b$ on one diagonal and $b$ and $a$ on the other. Swapping $a$ and $b$ in those four cells leaves every row and column legal and gives a different Latin square. So a set of revealed entries that misses an intercalate entirely cannot be defining.

The Klein square of order 4 is built entirely of intercalates — every pair of rows and pair of columns that share symbols forms one — and it has twelve. Four well-placed cells meet all twelve. Yet the smallest defining set has five entries, because intercalates are not the only trades: there are larger ones, cycles of entries running through three or four rows, that a set meeting every intercalate can still miss. The cyclic square of order 4 has only four intercalates, in a more regular arrangement, and four entries suffice for it. At odd orders the cyclic square has no intercalates at all, which is part of why it is so cheap to fix.

This is the general shape of every lower-bound argument for critical sets. A defining set is a hitting set for the square’s trades — the same kind of object as a set of points meeting every line of a finite plane, with trades in place of lines — and a lower bound needs a large family of trades no small set can hit — trades spread out so that each revealed entry meets only a few of them. Finding such families is hard, and the bounds proved so far come from families that are too thin to reach $n^2/4$.

Fixing a square is not fixing its partner #

Critical sets interact in an unexpected way with the orthogonality where the study of Latin squares began. Euler’s thirty-six officers asked for two Latin squares that, superimposed, show every pair of symbols once, and a field’s worth of squares built such pairs from the arithmetic of a finite field. A pair of orthogonal squares carries twice the information of one, but fixing the pair need not take twice the entries: a revealed cell now shows a pair of symbols, each pair constrains both squares at once, and orthogonality itself forbids many trades that each square alone would allow. How much it saves is a question of its own, studied for the squares of the planes hidden in complete sets of them, where a few revealed cells can determine a whole projective plane. Conversely, a single square with very few transversals — like the order-5 squares of the second kind, which have only three against the cyclic square’s fifteen and so, as a mate is rare until order ten found, no orthogonal mate at all — is among the ones that need more entries to fix. Symmetry, transversals and critical sets all measure the same underlying regularity from different sides.

Where the question came from #

Nelder was a statistician, and critical sets entered mathematics from the design of experiments. A Latin square is a layout for testing $n$ treatments on a field divided into $n$ rows and $n$ columns of plots, so that every treatment appears once in every row and column and differences in soil running across the field cancel out. Communicating such a design, or checking that a partially recorded one can be reconstructed, raises exactly the question of how few entries determine the rest. The same question appears in cryptography, where a Latin square used as a secret key is shared out among participants, and a group of participants who jointly hold a critical set can reconstruct the key while any smaller group cannot — a secret-sharing scheme built from the structure of the square. Critical sets of different sizes in one square correspond to different thresholds of trust.

What the searches show and assume #

Every count here is exact. Completion is tested by backtracking over rows and columns stored as bit masks, and a defining set is one for which the search finds exactly one completion; the order-5 census tests every set of cells of every reduced square in order of size, and the order-4 critical sets are found by testing all 65,536 subsets of both squares. The forced-move deduction is checked against the square at every step.

What the searches cannot reach is the conjecture itself. Order 6 has 9,408 reduced squares and $\binom{36}{8}$ sets of eight cells for each, and the exhaustive test that settles order 5 in seconds is out of reach there; the corner triangles show that $\lfloor n^2/4 \rfloor$ is achievable at orders 6 to 9, and say nothing about whether fewer could work for some other square. The random-entry figure is a sample, and its medians would shift slightly with another seed.

Still open: a quarter of the square #

Is the smallest critical set of every Latin square of order $n$ at least $\lfloor n^2/4 \rfloor$? The conjecture is open. The best general lower bound, due to Nicholas Cavenagh in 2007, grows like $n(\log n)^{1/3}$ — barely more than linear — against the conjectured quadratic. Even the weaker statement that the smallest critical set grows faster than any constant times $n$ took decades. The difficulty is the one the intercalate figure illustrates: a lower bound needs a family of trades so spread out that no small set meets them all, and the trades that are easy to describe are too local. Whether a square can be pinned down by an amount of information much smaller than a quarter of it, by some arrangement nobody has found, is unknown.

A quarter of the square, chosen well #

Six entries fix the cyclic Latin square of order five, and no five do; across every square up to order five the fewest entries that force one are 1, 2, 4 and 6, which is $\lfloor n^2/4 \rfloor$, the value Nelder conjectured for every order. The more symmetric squares are the cheapest — the Klein square of order four needs one more entry than the cyclic one, and fifty of the fifty-six reduced squares of order five need seven — because a defining set must block every trade, and symmetric squares arrange their trades where a few entries can block them all. Two corner triangles achieve the bound for the cyclic square at every order, random entries need nearly twice as many, and whether any square can be fixed by fewer than a quarter of its entries is still open.