Orthogonal squares are a code

Two Latin squares of the same order are orthogonal when, laid one over the other, every ordered pair of symbols appears in exactly one cell. A field of order $q$ builds $q - 1$ of them, every two orthogonal, by the one line $L_a(i, j) = a\cdot i + j$. And a complete set of them is a geometry in disguise: a plane with $q^2$ points in which every two points lie on one line.

This essay reads the same object a third way, and the third reading is the one that matters most outside mathematics. Take each cell of a set of $k$ orthogonal squares and write it down as a word of length $k + 2$: its row, its column, and the symbol it holds in each square. The $q^2$ cells give $q^2$ words. Any two of those words agree in at most one position. So the list is a code — a set of words chosen to be far apart, so that a word damaged in transit can still be recognised — and it is as good a code as any code with that many words and that length can possibly be.

Sixteen words, and the distance between any two #

Start with the three orthogonal squares of order four that the field of four elements builds, and write the sixteen cells as words: row, column, then the entry in each of the three squares. Each word has five symbols, drawn from the four elements $0, 1, \alpha, \alpha + 1$ of the field.

All 120 pairs of words differ in exactly four places. None agrees with another in more than one position, and in fact every pair agrees in exactly one. That is the property to explain, and it follows from the definitions one pair of positions at a time.

Suppose two different words agreed in two positions. If the two positions are the row and the column, the words come from the same cell, so they are the same word. If they are the row and one square’s entry, then that row of that square holds the same symbol in two different cells, which a Latin square forbids; the column and one square’s entry is the same argument turned sideways. And if they are two squares’ entries, then the ordered pair of symbols those two squares show appears in two different cells — which is precisely what orthogonality forbids. Being Latin and being orthogonal are, together, the statement that no two words agree twice. Nothing else is needed and nothing else is true.

That also explains why every pair agrees in exactly one place for a complete set, and the reason is a count. Fix one word. In any single position, each symbol is carried by exactly $q$ of the $q^2$ words, so $q - 1$ other words agree with the fixed word in that position. With all $q - 1$ squares present there are $q + 1$ positions, which gives $(q + 1)(q - 1) = q^2 - 1$ agreements — one for every other word. No word can be counted twice, since no word agrees twice, so every other word agrees exactly once.

As good as a code can be #

Distance is the currency of error correction. If every two words differ in at least $d$ places, a received word with fewer than $d/2$ symbols wrong is still nearer its original than any other word, and a received word with $d - 1$ symbols erased — known to be missing — can still be identified uniquely. The trade-off is that far-apart words are scarce, and the sharpest limit on how scarce is the Singleton bound: a code of length $n$ with $M$ words and distance $d$ has

$$M \le q^{\,n - d + 1}.$$

The proof is one sentence. Delete any $d - 1$ positions from every word; the shortened words are still all different, since two words differing in at least $d$ places still differ somewhere among the rest; and there are only $q^{\,n - d + 1}$ possible shortened words.

For codes made from squares, $M = q^2$, so the bound says $d \le n - 1$ — and the codes from squares achieve $d = n - 1$ exactly. They sit on the bound. A code that meets the Singleton bound is called maximum distance separable, and every set of $k$ orthogonal squares of order $q$ gives one: $q^2$ words of length $k + 2$ over $q$ symbols at distance $k + 1$. The converse holds too. Given any such code, its first two positions name every word exactly once — that is the bound met with equality — so they can be read as a row and a column, and each further position is then a Latin square, every two of them orthogonal. Sets of orthogonal Latin squares and maximum distance separable codes of this size are the same thing.

The erasure reading makes it concrete. Any two surviving symbols of a word pick it out, because any two positions together name every word exactly once — which is orthogonality again, or Latinness, depending on the two positions. So a word can lose any three of its five symbols and be restored. Lose four and the one survivor fits $q = 4$ words, so no code of sixteen words and length five could do better: three erasures is the Singleton bound’s limit, and the code reaches it.

Every pair of positions casts a vote #

Erasures are the easy case, because the damaged positions announce themselves. An error — a symbol silently replaced by a wrong one — is harder, and the squares give a decoder for it that needs no algebra at all.

Take a received word of length five, one symbol of which may be wrong, and let every pair of positions vote. There are ten pairs, and each pair of symbols names exactly one codeword, so each pair votes for a word. The six pairs that avoid the damaged position all read correct symbols, and all six vote for the transmitted word. The four pairs that include the damaged position may vote for wrong words — but no wrong word can collect two of those votes. If it did, it would agree with the received word at the damaged position and at two correct ones, and so agree with the transmitted word at two positions, which no two codewords do. So the transmitted word wins six votes to at most one, and a single error is corrected by counting.

With two errors the count fails, as it must: three pairs avoid both damaged positions and vote correctly, and a wrong word that happens to match both damaged symbols and one correct one collects three votes of its own — as many as the transmitted word. A code whose words differ in four places can correct one error and detect two, and the vote shows both halves of that sentence at work. Practical decoders for Reed–Solomon codes solve equations instead of counting votes, because the number of pairs grows quickly with the length, but the vote is the definition of what they compute: the codeword that agrees with the received word in the most places.

The squares a field builds are a Reed–Solomon code #

The field construction has a second meaning that was hiding in plain sight. The word for cell $(i, j)$ is

$$\big(\,i,\ \ j,\ \ a_1 i + j,\ \ a_2 i + j,\ \ \ldots,\ \ a_{q-1} i + j\,\big).$$

Read $j + i x$ as a polynomial of degree at most one in $x$. Then the last entries are that polynomial’s values at the nonzero field elements $x = a_1, \ldots, a_{q-1}$, the column $j$ is its value at $x = 0$, and the row $i$ is its leading coefficient — its “value at infinity”, which is what the polynomial looks like from very far away. So every word is a list of the values of one linear polynomial, taken at every point of the field and at the point at infinity.

That is the Reed–Solomon code of dimension two, from Irving Reed and Gustave Solomon’s paper of 1960. Its distance has the one-line proof that the essay on polynomials through gaps gave for all Reed–Solomon codes: two different polynomials of degree at most one agree at most at one point, since their difference is a nonzero polynomial of degree at most one and has at most one root. The same fact, stated as geometry, is that two different lines meet at most once. Stated as Latin squares, it is orthogonality.

So the squares Euler could not find at order six, the lines of a finite plane, and the codes that protect the data on a compact disc and in a QR code are three descriptions of one object. The practical codes use polynomials of higher degree, which trade distance for more words, but the principle is the one drawn here: evaluate a low-degree polynomial at many points, and any two words are far apart because two low-degree polynomials cannot agree often.

The distances are forced #

A maximum distance separable code has a property that ordinary codes do not: once its length, size and alphabet are fixed, the number of words at each distance from any given word is determined. No choice of construction can change it.

For two squares of order five the code has 25 words of length four at distance three, and every word has exactly sixteen others at distance three and eight at distance four. The same count explains it. In each of the four positions, $q - 1 = 4$ other words share the fixed word’s symbol, and each of them agrees with it there and nowhere else, so those $4 \times 4 = 16$ words are at distance three. The other $24 - 16 = 8$ words agree with it nowhere, and are at distance four. Nothing about the particular squares entered the count. The general formula, which F. J. MacWilliams and N. J. A. Sloane’s book on coding theory gives for every maximum distance separable code, was checked by the figure at every distance.

For a complete set the formula gives the equidistance already seen: every pair of the sixteen words of length five is at distance exactly four. A complete set of orthogonal squares is a code in which every two words are equally far apart — the same symmetry as an affine plane, where every two lines either meet once or are parallel, and parallel lines agree in the position that names their direction.

At most n − 1 squares, and why that bounds a code #

The oldest fact about orthogonal squares is that there can be at most $n - 1$ of them at order $n$, and the argument is a relabelling and a count. In code language it becomes a bound on length: a code of $n^2$ words over $n$ symbols in which no two words agree twice has length at most $n + 1$.

Translated, the argument runs like this. Relabel the symbols of every square position so that the words of row $0$ read their own column number in every square position. Now look at the word for cell $(1, 0)$. It cannot hold $0$ in any square position, for it would then agree with the word for cell $(0, 0)$ in the column and in that position — twice. And it cannot hold the same symbol $s$ in two square positions, for it would then agree twice with the word for cell $(0, s)$. So its square positions carry different nonzero symbols, of which there are $n - 1$, and the length is at most $2 + (n - 1) = n + 1$.

For codes over a field whose words are closed under addition and scaling — linear codes — the analogous question for every dimension is the MDS conjecture of Beniamino Segre, from 1955: that the longest nontrivial linear maximum distance separable code over a field of $q$ elements has length $q + 1$, with a single family of exceptions in even characteristic. Simeon Ball proved it in 2012 for fields of prime order, and for other orders it is still open. The squares settle dimension two, for linear and non-linear codes alike, with the argument in the figure.

Two codes that do not exist #

The table of the longest codes that squares give, alphabet by alphabet, is the table of how many orthogonal squares exist, and its two famous gaps are two famous non-existence theorems.

At six symbols there is no pair of orthogonal squares — Euler’s officers, proved impossible by Gaston Tarry’s exhaustive search in 1900 — so there is no code of 36 words of length four over six symbols in which any two words differ in at least three places. Stated that way, it sounds like a question about codes that nobody would have guessed was a question about officers.

At ten symbols the table stops knowing. Two orthogonal squares exist, found by Ernest Parker in 1959, so the code reaches length four; whether three exist, for length five, is open. What is known is that nine do not: a complete set would be a projective plane of order ten, and Clement Lam, Larry Thiel and Stanley Swiercz showed in 1989, after thousands of hours of computation, that there is no such plane. The surprising part is how. Their search did not look for the plane directly. It studied the binary code spanned by the plane’s lines — a code that would have had to exist if the plane did — and used the MacWilliams identities, which constrain a code’s distance distribution from its dual’s, to show that the code would need words of certain weights; the computer then showed those words could not be placed. The largest non-existence proof in the theory of orthogonal squares is a theorem about a code, which is fitting, because the squares were a code all along.

What the tables cannot show #

They cannot show codes that are not built from a field. Every complete set checked here comes from the field construction. At order nine there are other complete sets, from planes no field built, and their codes are maximum distance separable but not linear; the figures do not draw them, and the equivalence between squares and codes is argued for them rather than exhibited.

They cannot show the practical codes. The codes that carry real data have many more words than $q^2$ — polynomials of degree up to some $k - 1$ rather than one — and are decoded by algorithms, not by comparing a received word against a table. The squares show why distance comes from low-degree polynomials; they show nothing of how a decoder finds the nearest word quickly, which is a separate and much harder matter.

And the table’s open rows are open. Whether three orthogonal squares of order ten exist, and the true number at twelve, are not settled by anything here. The two gaps are recorded as the literature leaves them.

Still open: three squares of order ten #

The smallest open case is small enough to state on a postcard and has resisted every search: are there three mutually orthogonal Latin squares of order ten? Equivalently, is there a code of one hundred words, of length five, over ten symbols, in which no two words agree in two places? Two such squares exist in abundance; a complete set of nine does not; everything between is unknown. Searches have ruled out large families of candidate constructions, and the space of Latin squares of order ten, about $9.98 \times 10^{36}$ of them, is far beyond exhaustion.

The same object, three times #

A set of $k$ orthogonal Latin squares of order $q$, read cell by cell, is a code of $q^2$ words of length $k + 2$ in which no two words agree in two places — and conversely. Being Latin and being orthogonal are exactly that property, so the code meets the Singleton bound: any two surviving symbols recover a word, and its distance distribution is forced by its size. The squares a field builds, $a\cdot i + j$, are the values of linear polynomials — a Reed–Solomon code — and their distance is the fact that two lines meet at most once.

The bound of $n - 1$ squares is a bound of $n + 1$ on the code’s length. Euler’s thirty-six officers become a code of 36 words that cannot exist, and the non-existence of a plane of order ten was proved by studying a code the plane would have carried. Squares, planes and codes are one object, and each description proves something the others find hard.

When a combinatorial object keeps turning up in other subjects under other names, the names are usually describing one property from three sides.