Mutually orthogonal Latin squares
Mutually orthogonal Latin squares (MOLS) of order n are a collection of r Latin squares, each an n × n array filled with n different symbols such that each symbol appears exactly once in each row and column, where every pair of distinct squares in the set is orthogonal.[1] Two Latin squares are orthogonal if, when superimposed, every possible ordered pair of symbols—one from each square—appears exactly once across the n² positions.[1] The maximum possible value of r is n−1, a bound achieved precisely when n is a prime power, via constructions over finite fields.[2] The concept was introduced by Leonhard Euler in 1776 as a method for constructing magic squares, where pairs of orthogonal Latin squares help ensure constant row, column, and sometimes diagonal sums.[2] Euler conjectured that no pair of orthogonal Latin squares exists for orders n ≡ 2 (mod 4), a claim proven false for n > 6 by R. C. Bose, S. S. Shrikhande, and E. T. Parker in 1959–1960, though it holds for n = 6 as shown by G. Tarry in 1900.[3] In the 20th century, Ronald A. Fisher and Frank Yates advanced their use in statistical experimental design, publishing tables of MOLS for orders up to 9 in 1938 to facilitate randomized block designs that control for multiple sources of variation.[3] MOLS find broad applications in combinatorial design theory, including the construction of orthogonal arrays for statistical experiments, where they enable efficient testing of factors while minimizing confounding effects.[4] They also underpin error-correcting codes based on finite fields, such as Reed-Solomon codes, which detect and correct errors in data transmission and storage.[5] Additional uses include tournament scheduling, cryptography, and finite geometries, where sets of MOLS correspond to affine planes of order n.[4]Fundamentals
Definition and Basic Concepts
A Latin square of order n is an n \times n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column.[6] These symbols are typically taken from a set of size n, such as \{1, 2, \dots, n\} or \{0, 1, \dots, n-1\}.[7] Two Latin squares A = (a_{ij}) and B = (b_{ij}) of order n are said to be orthogonal if, when superimposed, the n^2 ordered pairs (a_{ij}, b_{ij}) for i, j = 1, \dots, n consist of all possible ordered pairs from the symbol sets exactly once.[8] This orthogonality condition ensures that the superposition forms a complete set of distinct pairs, akin to a transversal design of order 4 on n points.[7] A set of r mutually orthogonal Latin squares (MOLS) of order n is a collection of r Latin squares of order n such that every pair among them is orthogonal.[9] The notation N(n) denotes the maximum value of r for which such a set exists.[9] Any single Latin square of order n trivially forms a set of 1 MOLS, as there are no pairs to check for orthogonality.[9] For a concrete example, consider the Latin square L defined by L(i,j) = i + j \pmod{n} for i,j = 0, \dots, n-1, using symbols from \{0, 1, \dots, n-1\}; this is the addition table modulo n and constitutes a valid Latin square, as each row is a cyclic shift of the symbols and each column similarly contains each symbol once.[6]Orthogonality Condition
Two Latin squares A and B of order n, each filled with symbols from a set S of size n, are said to be orthogonal if the mapping (i, j) \mapsto (A_{ij}, B_{ij}) is a bijection from \times to S \times S.[6] This condition ensures that every possible ordered pair of symbols from S appears exactly once when the positions in the two squares are compared.[10] To verify orthogonality, one superimposes the two squares and examines the resulting array of ordered pairs (A_{ij}, B_{ij}) for all i, j \in ; all n^2 possible pairs must appear exactly once, with no repetitions.[6] This pairwise uniqueness distinguishes orthogonal squares from non-orthogonal ones, where some pairs would repeat and others would be absent. For illustration, consider two orthogonal Latin squares of order 3 on the symbol set \{0, 1, 2\}, defined by A_{ij} = i + j \pmod{3} and B_{ij} = i + 2j \pmod{3} (with rows and columns indexed from 0 to 2): | | 0 | 1 | 2 | |---|---|---| | 0 | 0 | 1 | 2 | | 1 | 1 | 2 | 0 | | 2 | 2 | 0 | 1 | | | 0 | 1 | 2 | |---|---|---| | 0 | 0 | 2 | 1 | | 1 | 1 | 0 | 2 | | 2 | 2 | 1 | 0 | Superimposing these yields the pairs (0,0), (1,2), (2,1), (1,1), (2,0), (0,2), (2,2), (0,1), (1,0), confirming all nine distinct pairs appear exactly once.[11] A set \{A_1, \dots, A_r\} of r Latin squares of order n is mutually orthogonal if every pair A_k, A_l with k \neq l satisfies the orthogonality condition.[12] In this context, a Latin square B that is orthogonal to a fixed Latin square A is called an orthogonal mate of A.[12]Historical Development
Early History and Euler's Contributions
The concept of mutually orthogonal Latin squares traces its origins to the work of Leonhard Euler in the late 18th century, particularly through his investigations into magic squares and combinatorial arrangements. In his paper "Recherches sur une nouvelle espèce de quarrés magiques," written in 1779 and published in 1782, Euler explored arrangements where symbols are placed in a square grid such that each row and column contains each symbol exactly once, connecting these to broader designs like knight's tours on chessboards.[13] These structures, which Euler denoted using Latin letters to represent rows and columns in his examples, laid the groundwork for what would later be termed Latin squares, drawing from his earlier studies on chess knight tours where similar row-column labeling appeared.[14] Euler extended this to pairs of such squares that are orthogonal, meaning that superimposing them results in every possible pair of symbols appearing exactly once in the grid. He introduced the term "Graeco-Latin squares" for these orthogonal pairs, using Latin letters for one square and Greek letters for the other to visualize the distinct symbols.[15] Based on his exhaustive examinations of small orders and patterns in magic squares, Euler conjectured that no Graeco-Latin square of order n exists when n \equiv 2 \pmod{4}, a claim rooted in his observations of orthogonal arrays and the absence of such constructions for orders like 2, 6, and 10.[15] This conjecture emerged as part of Euler's broader combinatorial pursuits, including applications to problems like arranging officers in formations, though he believed the condition held generally across even orders not divisible by 4.[13] In the 19th century, mathematicians began scrutinizing Euler's ideas through systematic investigations, building on his foundational notations. Early efforts focused on verifying the conjecture for specific small orders, with limited progress until the turn of the century. Notably, the French mathematician Gaston Tarry conducted an exhaustive enumeration in 1900, confirming that no pair of orthogonal Latin squares of order 6 exists, thereby upholding Euler's conjecture for that case through a laborious case-by-case analysis of over 800 million potential arrangements.[16] Tarry's work, detailed in his publication "Le problème des 36 officiers," represented a pivotal early verification, emphasizing the combinatorial challenges Euler had anticipated without computational aids.[17] These developments highlighted the enduring influence of Euler's contributions on the study of orthogonal designs, setting the stage for later explorations into their existence and properties.The Thirty-Six Officers Problem
In 1782, Leonhard Euler posed a combinatorial puzzle known as the Thirty-Six Officers Problem, challenging mathematicians to arrange 36 officers—representing six ranks and six regiments—into a 6×6 square such that each row and each column contains exactly one officer of every rank and exactly one from every regiment.[18] This arrangement is mathematically equivalent to constructing a pair of mutually orthogonal Latin squares of order 6, where one square encodes the ranks and the other the regiments, with their superposition forming a Graeco-Latin square.[19] Euler conjectured that no such arrangement exists for order 6, as part of his broader belief that Graeco-Latin squares of order n \equiv 2 \pmod{4} are impossible, with n=6 serving as the smallest non-trivial case illustrating this pattern.[18] He demonstrated solutions for other orders but argued against the possibility here based on structural incompatibilities in the orthogonality condition.[19] The problem remained unsolved for over a century until French mathematician Gaston Tarry provided a rigorous proof of non-existence between 1900 and 1901, employing an exhaustive case analysis of potential configurations to verify that no pair of orthogonal Latin squares of order 6 can be formed.[18] Tarry's work confirmed Euler's specific conjecture for this order through meticulous enumeration, ruling out all viable pairings.[20] This historical milestone underscored the inherent difficulties in constructing even pairwise orthogonal Latin squares for certain orders, spurring subsequent research into the existence conditions for mutually orthogonal sets and influencing the development of combinatorial design theory.[18] By highlighting the limitations for n=6, the problem became a foundational example that motivated explorations of general bounds and constructive methods in the field.[19]Existence Theorems
Upper Bounds on the Number of MOLS
The maximum number of mutually orthogonal Latin squares (MOLS) of order n, denoted N(n), is bounded above by N(n) \leq n-1 for all n \geq 2. This absolute upper bound arises from the structural constraints imposed by the orthogonality condition. To see this, consider a fixed Latin square L_0 of order n, where the n rows partition the set of n symbols into n disjoint classes of size n each (one symbol per position in the row). Any additional Latin square L_1 orthogonal to L_0 pairs each symbol from L_0 with symbols from L_1 in such a way that every possible ordered pair appears exactly once across the superimposed array. Extending this to a second square L_2 orthogonal to both L_0 and L_1 requires resolving these pairs into unique triples, and so on for further squares. This process can continue for at most n-1 additional squares before the combinations exhaust the possible unique resolutions, as the total number of distinct tuples needed exceeds what n symbols can provide beyond that point.[21][22] A set achieving this upper bound of n-1 MOLS corresponds precisely to an affine plane of order n, where the squares encode the parallel classes of lines in the plane. This equivalence highlights the deep connection between MOLS and finite geometries, with the bound representing the theoretical maximum for resolving the grid into orthogonal resolutions. At the lower end, a trivial bound holds: N(n) \geq 1 for all n \geq 1, as any single Latin square of order n forms a trivial set of one MOLS (orthogonal to itself in the singleton sense).[22] A special case occurs for n=2, where N(2) = 1; up to isomorphism, no pair of orthogonal Latin squares exists, as exhaustive enumeration shows that the two possible Latin squares of order 2 (the cyclic and its transpose) fail the orthogonality condition.[22]McNeish's Theorem and Prime Power Orders
In 1922, E. H. MacNeish established a foundational result in the theory of mutually orthogonal Latin squares (MOLS), stating that if the order n is a prime power, that is, n = p^k where p is a prime and k \geq 1, then there exist at least n-1 MOLS of order n.[23] This theorem provides a constructive lower bound on N(n), the maximum number of MOLS of order n, by employing a product construction that iteratively builds sets from smaller prime power cases, starting with explicit cyclic constructions for primes.[24] MacNeish's work laid the groundwork for later developments in the 1930s and 1940s, where researchers like R. C. Bose connected MOLS to finite geometries. Bose demonstrated that complete sets of n-1 MOLS for prime power n can be derived from the structure of finite fields of order n, providing an explicit algebraic construction that confirms and refines MacNeish's bound.[25] These advancements highlighted the deep ties between MOLS and affine geometries, where a set of n-1 MOLS corresponds precisely to an affine plane of order n.[26] For orders n that are prime powers, MacNeish's theorem achieves the absolute upper bound N(n) \leq n-1, as established by the orthogonality condition limiting any set of MOLS to at most this size. This equality holds because affine planes of order n exist exactly when n is a prime power, yielding precisely n-1 MOLS; equivalently, projective planes of order n also exist in these cases, reinforcing the geometric interpretation.[26][27] In contrast, for composite orders n that are not prime powers, N(n) < n-1. A classic example is n=6, where N(6)=1, as no pair of orthogonal Latin squares of order 6 exists, resolving Euler's thirty-six officers problem negatively.[26] As of 2025, while no major theoretical advances have altered these existence guarantees for prime powers, computational efforts have verified largest known sets of size 2 for order 10 and 5 for order 12, though the exact values of N(n) remain unknown for these orders.[26]Constructions
Finite Field Constructions
One of the most fundamental algebraic constructions of mutually orthogonal Latin squares (MOLS) utilizes finite fields. When q is a prime power, the finite field \mathrm{GF}(q) admits a complete set of q-1 MOLS of order q. Label the rows, columns, and symbols of these squares by the elements of \mathrm{GF}(q). For each m = 1, 2, \dots, q-1, define the Latin square L_m by L_m(i, j) = i + m \cdot j, where + and \cdot denote the addition and multiplication operations in \mathrm{GF}(q).[28] Each L_m is a Latin square because, for fixed i, as j ranges over \mathrm{GF}(q), the values m \cdot j range over all field elements (since multiplication by nonzero m is bijective), and adding i simply permutes them. Similarly, for fixed j, varying i yields all symbols. To verify orthogonality, consider distinct m, m' \in \{1, \dots, q-1\}. Suppose L_m(i, j) = L_m(i', j') and L_{m'}(i, j) = L_{m'}(i', j') for some i, j, i', j'. This gives i + m j = i' + m j', \quad i + m' j = i' + m' j', which rearranges to i - i' = m (j' - j), \quad i - i' = m' (j' - j). Subtracting these equations yields (m - m')(j' - j) = 0. Since m \neq m' and \mathrm{GF}(q) has no zero divisors, it follows that j' = j, and thus i = i'. Therefore, each ordered pair of symbols appears exactly once in the superposition of L_m and L_{m'}.[28] For a concrete example, consider q=3 and \mathrm{GF}(3) = \{0,1,2\} with arithmetic modulo 3. The square L_1 is \begin{bmatrix} 0 & 1 & 2 \\ 1 & 2 & 0 \\ 2 & 0 & 1 \end{bmatrix}, and L_2 is \begin{bmatrix} 0 & 2 & 1 \\ 1 & 0 & 2 \\ 2 & 1 & 0 \end{bmatrix}. Superimposing these yields all nine ordered pairs (s,t) \in \mathrm{GF}(3) \times \mathrm{GF}(3) exactly once, confirming orthogonality.[28] This construction generalizes the addition and multiplication tables of the finite field, where the affine transformations i \mapsto i + m j encode the field's linear structure over itself. It realizes the upper bound of q-1 MOLS for order q, as guaranteed for prime powers by direct field existence. However, the method applies only to prime power orders and does not extend directly to composite orders without prime power factors.[28]Geometric Constructions from Planes
Affine planes provide a geometric framework for constructing sets of mutually orthogonal Latin squares (MOLS). An affine plane of order n consists of n^2 points and n(n+1) lines, partitioned into n+1 parallel classes, each containing n disjoint lines that cover all points. To derive MOLS, label the points as an n \times n grid using coordinates (i, j) where i, j \in \{1, 2, \dots, n\}, with rows corresponding to one parallel class V (vertical lines) and columns to another H (horizontal lines). For each of the remaining n-1 parallel classes \pi_k ( k = 1, \dots, n-1), construct a Latin square L_k by assigning to position (i, j) the label of the unique line in \pi_k that passes through the intersection of the i-th line in V and the j-th line in H. These n-1 Latin squares are mutually orthogonal because any two lines from different parallel classes intersect at exactly one point, ensuring all symbol pairs appear exactly once when overlaid.[29] Projective planes offer a complementary geometric construction for MOLS. A projective plane of order n has n^2 + n + 1 points and the same number of lines, with every pair of points on exactly one line and every pair of lines intersecting at exactly one point. To obtain MOLS, select two distinct points X_\infty and Y_\infty on a fixed line l_\infty, and choose the remaining n-1 points Q_1, \dots, Q_{n-1} on l_\infty. Label the n lines through X_\infty (excluding l_\infty) as 1 through n, and similarly for lines through Y_\infty. Define points P_{ij} as the intersection of the i-th line through X_\infty and the j-th through Y_\infty. For each Q_k, label the n lines through Q_k (excluding l_\infty) with symbols 1 through n, and in the k-th Latin square, place symbol s at (i, j) if the line from P_{ij} through Q_k is labeled s in this class. The resulting n-1 squares are mutually orthogonal due to the unique intersection properties of lines in the plane.[30] An affine plane of order n can be derived from a projective plane by removing one line l_\infty and its n+1 points, yielding n+1 parallel classes from the lines intersecting l_\infty; conversely, adding a line at infinity restores the projective structure. Thus, the existence of an affine plane of order n is equivalent to that of a projective plane of order n, and both yield a complete set of n-1 MOLS of order n, achieving the upper bound N(n) \leq n-1 on the maximum number of MOLS.[29][30] Such planes, and hence complete MOLS sets, exist precisely when n is a prime power, as constructed using finite fields. For example, the Fano plane, the unique projective plane of order 2 with 7 points and 7 lines, yields 1 MOLS of order 2 via the above method.[30] No projective (or affine) planes are known to exist for non-prime-power orders, consistent with the Bruck-Ryser theorem, which rules out existence for certain such n (e.g., n \equiv 1 or $2 \pmod{4} where n is not a sum of two squares), thereby limiting N(n) < n-1 in those cases.Examples and Specific Cases
Order 2 and 3 MOLS
For order 2, no pair of mutually orthogonal Latin squares exists, as there are only two Latin squares of order 2 on the same symbol set up to isomorphism, and neither is orthogonal to the other.[6][31] For order 3, the maximum number of mutually orthogonal Latin squares is N(3) = 2, which is achieved and thus maximal.[6] A standard construction of such a pair uses the finite field \mathbb{F}_3 = \{0, 1, 2\} with arithmetic modulo 3, where the entries of the k-th square (for k = 1, 2) are given by L_k(i, j) = i + k j \pmod{3} for row index i and column index j ranging over \{0, 1, 2\}.[12][32] This yields the following two Latin squares: L_1: | | 0 | 1 | 2 | |---|---|---| | 0 | 0 | 1 | 2 | | 1 | 1 | 2 | 0 | | 2 | 2 | 0 | 1 | L_2: | | 0 | 1 | 2 | |---|---|---| | 0 | 0 | 2 | 1 | | 1 | 1 | 0 | 2 | | 2 | 2 | 1 | 0 | To verify orthogonality, superimposing L_1 and L_2 produces the following ordered pairs (L_1(i,j), L_2(i,j)) at each position (i,j):- (0,0): (0,0)
- (0,1): (1,2)
- (0,2): (2,1)
- (1,0): (1,1)
- (1,1): (2,0)
- (1,2): (0,2)
- (2,0): (2,2)
- (2,1): (0,1)
- (2,2): (1,0)
Higher-Order Examples
For order 4, the maximum number of mutually orthogonal Latin squares is 3, achieved using the finite field GF(4). A subset of two such squares can be constructed by labeling the symbols as 0, 1, a, b where a^2 = a + 1 and b = a + 1 (with arithmetic in characteristic 2), indexing rows and columns by these elements, and defining the entry in row x and column y of the k-th square as x + k y for k = 1 and k = a. The resulting squares are: First square (k=1):| 0 | 1 | a | b | |
|---|---|---|---|---|
| 0 | 0 | 1 | a | b |
| 1 | 1 | 0 | b | a |
| a | a | b | 0 | 1 |
| b | b | a | 1 | 0 |
| 0 | 1 | a | b | |
|---|---|---|---|---|
| 0 | 0 | a | b | 1 |
| 1 | 1 | b | a | 0 |
| a | a | 0 | 1 | b |
| b | b | 1 | 0 | a |
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| ... | ... | ... | ... | ... | ... |
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | 2 | 4 | 1 | 3 |
| 1 | 1 | 3 | 0 | 2 | 4 |
| 2 | 2 | 4 | 1 | 3 | 0 |
| ... | ... | ... | ... | ... | ... |