Myrvold’s Results on Orthogonal Triples of 10 × 10 10\times 10 Latin Squares: A SAT Investigation
Curtis Bright, Amadou Keita, Brett Stevens · 2025
Read Myrvold’s Results on Orthogonal Triples of 10 × 10 10\times 10 Latin Squares: A SAT Investigation by Curtis Bright, Amadou Keita, Brett Stevens (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-10504.txt.
Introduction
Curtis Bright, Amadou Keita, and Brett Stevens revisit a famous open problem about Latin squares, in a 2025 paper. A Latin square fills a grid so each symbol appears once per row and column. Two squares are orthogonal if, laid on top of each other, every pair of symbols appears exactly once; triples are harder still.
An orthogonal pair of size ten was found in 1959, but no one has found a triple. In 1999 Wendy Myrvold narrowed one special case to twenty-eight possible patterns and ruled out twenty of them by hand. The team fed the problem to a SAT solver, a program that tests logical constraints. It confirmed all her negative results quickly and built example pairs in the eight open cases.
Catalog record
| CREATOR | Curtis Bright, Amadou Keita, Brett Stevens |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-10504
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Myrvold’s Results on Orthogonal Triples of 10 × 10 10\times 10 Latin Squares: A SAT Investigation Curtis Bright, Amadou Keita, Brett Stevens Abstract Ever since E. T. Parker constructed an orthogonal pair of 10 × 10 10\times 10 Latin squares in 1959, an orthogonal triple of 10 × 10 10\times 10 Latin squares has been one of the most sought-after combinatorial designs. Despite extensive work, the existence of such an orthogonal triple remains an open problem, though some negative results are known. In 1999, W. Myrvold derived some highly restrictive constraints in the special case in which one of the Latin squares in the triple contains a 4 × 4 4\times 4 Latin subsquare. In particular, Myrvold showed there were twenty-eight possible cases for an orthogonal pair in such a triple, twenty of which were removed from consideration. We implement a computational approach that quickly verifies all of Myrvold’s nonexistence results and in the remaining eight cases finds explicit examples of orthogonal pairs—thus explaining for the first time why Myrvold’s approach left eight cases unsolved. As a consequence, the eight remaining cases cannot be removed by a strategy of focusing on the existence of an orthogonal pair; the third square in the triple must necessarily be considered as well. Our approach uses a Boolean satisfiability (SAT) solver to derive the nonexistence of twenty of the orthogonal pair types and find explicit examples of orthogonal pairs in the eight remaining cases. To reduce the existence problem into Boolean logic we use a duality between the concepts of transversal representation and orthogonal pair and we provide a formulation of this duality in terms of a composition operation on Latin squares. Using our SAT encoding, we find transversal representations (and equivalently orthogonal pairs) in the remaining eight cases in under a day of computing. 1 Introduction A Latin square of order n is an n\times n array filled with n distinct symbols such that each symbol appears exactly once in each row and exactly once in each column. A transversal of a Latin square of order n consists of n cells of the square chosen so that there is exactly one cell from each row, exactly one cell from each column, and exactly n distinct symbols all together. There are many ways of representing a transversal, but we follow Myrvold [ 28 ] and represent a transversal by listing the symbols in the transversal in each column from left to right. For example, the highlighted transversal in \begin{bmatrix}0&{\color[rgb]{1,0,0}\bf 1}&2\\ {\color[rgb]{1,0,0}\bf 2}&0&1\\ 1&2&{\color[rgb]{1,0,0}\bf 0}\end{bmatrix} is represented by the row vector [2,1,0] . We call this row vector the transversal’s row representation . Two Latin squares of order n are said to be orthogonal when all n^{2} possible symbol pairs occur when the two squares are superimposed over each other. This is equivalent to each Latin square having a decompositon of its cells into transversals. A set of Latin squares that are pairwise orthogonal to each other are known as mutually orthogonal Latin squares (MOLS) and a set of k MOLS of order n are known as a k -MOLS( n ). For each order n , let N(n) denote the largest possible value of k for which a k -MOLS( n ) exists. Determining values of N(n) has a long history [ 1 , Ch. III] and has been of intense interest to mathematicians ever since Euler conjectured in 1782 that N(n)=1 for n\equiv 2\pmod{4} . It is easily seen that N(2)=1 , and Tarry showed in 1900 that N(6)=1 [ 33 ] . However, in 1959, Euler’s conjecture was shown to be false by the discovery of a 2-MOLS(22) [ 6 ] and a 2-MOLS(10) [ 29 ] . In fact, in 1960 it was shown that N(n)\geq 2 for all n>6 [ 7 ] . It is also known that N(n)=n-1 if and only if a projective plane of order n exists. Projective planes exist for all prime powers, so the first order for which the value of N(n) is uncertain is n=10 . It is unknown if N(10)\geq 3 , and determining the value of N(10) is one of the most prominent unsolved problems concerning MOLS. In particular, finding a 3-MOLS(10) or proving its nonexistence is a longstanding open problem in combinatorial design theory. Although it is not known if a 3-MOLS(10) exists or not, there are several special results known about this case. Mann [ 23 ] proved that a 10\times 10 Latin square with a 5\times 5 Latin subsquare cannot belong to an orthogonal pair, let alone an orthogonal triple. Parker [ 30 ] proved that two orthogonal 10\times 10 Latin squares with orthogonal 3\times 3 Latin subsquares cannot be part of an orthogonal triple. Myrvold [ 28 ] considered a 10\times 10 Latin square L with a 4\times 4 Latin subsquare. She showed that it is possible for L to be part of an orthogonal pair, and further considered if L can be part of an orthogonal triple. Myrvold showed there are seven possible ways of decomposing L into transversals and twenty-eight possibilities for decomposing L in two ways (a necessary condition for L to be part of an orthogonal triple). Myrvold ruled out the existence of twenty of the twenty-eight possibilities which required only the consideration of constraints arising from only two of the three putative squares. Her work left open the remaining eight cases: The most obvious next step in extending the current work is to eliminate the remaining eight cases from consideration . [ 28 ] We provide a reason why Myrvold’s method was unable to rule out these eight cases, and show any argument ruling out these cases must necessarily be more involved—because orthogonal pairs in the remaining eight cases exist (though it is unclear if orthogonal triples in the remaining eight cases exist). Thus, any argument ruling out the remaining eight cases must necessarily involve the triple as a whole, not only two of the three squares. We give more background on Latin squares and the formulation of Myrvold’s twenty-eight cases in Section 2 . Our approach uses a satisfiability (SAT) solver to explicitly construct a 2-MOLS(10) in each of the eight cases that Myrvold left open. Additionally, in under a second of compute time the SAT solver shows the nonexistence of a 2-MOLS(10) in the twenty cases solved by Myrvold. To use a SAT solver, it is necessary to reduce the problem of searching for the object in question to the problem of searching for a satisfying assignment to a formula in Boolean logic representing Myrvold’s framework and cases. We reduce the problem of finding a 2-MOLS(10) in each of Myrvold’s twenty-eight cases to SAT—see Section 4 for a description of our encoding. We develop a SAT encoding of orthogonality that relies on an equivalence between the orthogonality of Latin squares and what Myrvold calls a “transversal representation” Latin square [ 28 ] . Myrvold uses this equivalence for “designing computer programs for exploring squares and their mates” . We provide a precise duality relating these two concepts via a “composition” operation on Latin squares and a generalization of Latin squares where only the columns (and not necessarily the rows) contain all