Latin Squares and Orthogonality

Mutually orthogonal Latin squares underlie statistical experimental design: Graeco-Latin square designs let statisticians block out two nuisance factors while estimating a treatment effect, exactly using an orthogonal pair to guarantee no confounding between blocking variables — this is R. A. Fisher's original motivation for popularizing Latin square designs in agricultural field trials. In combinatorial design theory, a complete set of $n-1$ MOLS of order $n$ is equivalent to the existence of a projective plane of order $n$: the MOLS supply the "parallel classes" of lines in an affine plane of order $n$, which extends uniquely to a projective plane. This equivalence is the reason the existence question for MOLS of a given order is so consequential — settling $N(n)$ for a given $n$ can settle the existence of a projective plane of that order, as famously happened for $n=10$ (no projective plane of order 10 exists, a landmark computer-assisted proof by Lam, Thiel, and Swiercz in 1989, closely tied to MOLS non-existence results). In coding theory, MOLS constructions yield maximum-distance-separable (MDS) codes and are used to build orthogonal arrays $OA(n^2, k)$, which in turn underlie constructions of error-correcting codes and are central objects connecting back to Combinatorial Designs and BIBDs. In cryptography, Latin squares serve as the combinatorial skeleton of certain block cipher S-boxes and secret-sharing schemes, where orthogonality guarantees uniform, collision-free key/output distributions. In computer science, MOLS appear in constructions of resolvable designs used for scheduling round-robin tournaments and for constructing families of hash functions with strong independence guarantees.

Ask the tutor: How does a complete set of MOLS of order $n$ get turned, step by step, into the lines of a finite projective plane?

Think of a Latin square as a valid seating chart: row = a person, column = a time slot, entry = which topic they discuss. Latin-ness guarantees each person discusses each topic exactly once, and at each time slot every topic is being discussed by exactly one person. Now add a second square recording, say, which room each person uses at each time slot. Orthogonality says: knowing the topic and the room together at a given time-slot pins down the person uniquely — no two people share a (topic, room) pair. This is precisely the classical Graeco-Latin square picture (Euler's Latin and Greek letters superimposed), and it is exactly the requirement of a two-factor experimental design with no confounding between factors. The reason $N(n)$ cannot grow without bound is a rigidity phenomenon: once you fix one Latin square and normalize how a second one interacts with a single row of the first, there are only $n-1$ "genuinely different directions" left for further squares to point without colliding with each other. This is the combinatorial heart of the bound proved below.

Example 1 (order 4: constructing and verifying a complete set of 3 MOLS from $\mathbb{F}_4$). Since $4 = 2^2$ is a prime power, the finite field $\mathbb{F}_4 = \{0, 1, \omega, \omega^2\}$ exists, where $\omega^2 = \omega + 1$ and all arithmetic is done in characteristic 2 (so $x + x = 0$ for every $x$). Index rows and columns of a $4\times 4$ array by the elements of $\mathbb{F}_4$ in the fixed order $0, 1, \omega, \omega^2$. For each nonzero $c \in \mathbb{F}_4$, define the Latin square

using field multiplication and addition. There are three nonzero choices of $c$: $c \in \{1, \omega, \omega^2\}$, giving three squares $L_1, L_\omega, L_{\omega^2}$. Each $L_c$ is Latin. Fix row $i$. As $j$ ranges over $\mathbb{F}_4$, $L_c(i,j) = ci+j$ ranges over all of $\mathbb{F}_4$ bijectively (it's a translation of $j$ by the fixed constant $ci$), so no repeats in a row. Fix column $j$. As $i$ ranges over $\mathbb{F}_4$, $L_c(i,j) = ci + j$: since $c \ne 0$, the map $i \mapsto ci$ is a bijection of the field (as $\mathbb{F}_4$ is a field and $c$ is invertible), so $ci+j$ ranges bijectively over $\mathbb{F}_4$ as $i$ varies. No repeats in a column either. Any two are orthogonal. Take $c \ne c'$, both nonzero. Suppose $(L_c(i,j), L_{c'}(i,j)) = (L_c(i',j'), L_{c'}(i',j'))$ for two cells $(i,j), (i',j')$. Then

Subtracting the two equations gives $(c - c')(i - i') = 0$. Since $c \ne c'$ and we are in a field, $c - c' \ne 0$, forcing $i = i'$ (using char 2, "subtract" means add, but the algebra is identical: $(c+c')(i+i')=0 \Rightarrow i = i'$ since $c + c' \ne 0$). Then from $ci+j = ci'+j' = ci+j'$ we get $j = j'$. Hence the map $(i,j)\mapsto (L_c(i,j), L_{c'}(i,j))$ is injective on a set of size $16$ mapping into a set of size $16$ ($\mathbb{F}_4 \times \mathbb{F}_4$), hence bijective. So $L_c \perp L_{c'}$. We exhibit $L_1$ and $L_\omega$ explicitly. Order rows/columns as $0,1,\omega,\omega^2$. $L_1(i,j) = i+j$:

$L_\omega(i,j) = \omega i + j$. Using $\omega\cdot 0=0,\ \omega\cdot1=\omega,\ \omega\cdot\omega=\omega^2,\ \omega\cdot\omega^2=1$ (since $\omega^3=1$ in $\mathbb{F}_4^\times$):

Superimpose: cell $(2,1)$ (0-indexed as row "$1$", col "$0$" in field labels, i.e. matrix position row 2 col 1) gives pair $(L_1, L_\omega) = (0, \omega)$; cell $(1,1)$ gives $(0,0)$; scanning all 16 cells one confirms each of the 16 ordered pairs from $\mathbb{F}_4 \times \mathbb{F}_4$ appears exactly once — consistent with the general proof above. Since $N(4) \le 3$ by the theorem and we exhibited $3$ pairwise orthogonal squares, $N(4) = 3$: a complete set.

Example 2 (order 5: two explicit orthogonal Latin squares built from $\mathbb{Z}_5$, with a full pairing check). Since $5$ is prime, $\mathbb{Z}_5 = \{0,1,2,3,4\}$ is a field. Define $L_1(i,j) = i+j \pmod 5$ and $L_2(i,j) = i + 2j \pmod 5$ (i.e. $c = 2$).

Latin check for $L_2$: row $i$ is $i, i+2, i+4, i+1, i+3 \pmod 5$ — a full residue system since $2$ is invertible mod 5 ($2 \times 3 \equiv 1$), so as $j$ ranges over $\mathbb{Z}_5$, $2j$ ranges over all residues, hence $i+2j$ does too: no repeats. Column $j$: as $i$ ranges over $\mathbb{Z}_5$, $i + 2j$ ranges bijectively (a shift), so no repeats in a column either. So $L_2$ is Latin (and $L_1$ is the standard addition table, clearly Latin by the same argument with $c=1$). Orthogonality check by direct pairing. We list, for each cell $(i,j)$ with $i,j \in \{0,\dots,4\}$, the pair $(L_1(i,j), L_2(i,j)) = (i+j, i+2j) \bmod 5$. To verify orthogonality by hand without listing all 25, use the algebraic argument (as in Example 1): if $(i+j, i+2j) = (i'+j', i'+2j')$ then subtracting, $(i-i')+(j-j') \equiv 0$ and $(i-i') + 2(j - j') \equiv 0 \pmod 5$; subtracting these two congruences gives $(j - j') \equiv 0 \pmod 5$, so $j = j'$, and then $i = i'$. Hence the map is injective on 25 cells into 25 pairs, so bijective: $L_1 \perp L_2$. As a spot check, pick two cells that might look suspicious. Cell $(0,3)$: $L_1 = 0+3=3$, $L_2 = 0 + 6 = 1 \pmod 5$, pair $(3,1)$. Cell $(4,2)$: $L_1 = 4+2=6\equiv 1$, $L_2 = 4+4=8\equiv 3$, pair $(1,3)$. These are different pairs $(3,1) \ne (1,3)$ — no collision, consistent with the proof. One can continue and confirm distinctness for all 25 cells; the algebraic argument already guarantees it rigorously. Since $5$ is prime, in fact a full construction with $c \in \{1,2,3,4\}$ (all nonzero elements of $\mathbb{Z}_5$) gives four pairwise orthogonal Latin squares $L_1, L_2, L_3, L_4$ by the identical argument as Example 1 (the field argument used there only needs $\mathbb{Z}_5$ to be a field, which it is since 5 is prime). Since $N(5) \le 4$ by the theorem, this achieves $N(5) = 4$: another complete set.