Combinatorial and Automata Applications

Orthogonal Latin Squares and the Refutation of Euler's Conjecture

Euler conjectured in 1782 that no pair of orthogonal Latin squares of order 4k+2 exists beyond order 2. He was right about order 6 and wrong about every other case.

Engineering · Mathematics6 min readKV-MATH-0229

Learning objectives

Define orthogonality for a pair of Latin squares.
State Euler's conjecture and the officer problem that motivated it.
Describe Tarry's verification of the order-6 case.
State the Bose–Shrikhande–Parker refutation and its final form.
Express orthogonality algebraically as a condition on two quasigroup operations.
Explain how the algebraic reading supports product constructions.

01Orthogonality

Two Latin squares of the same order n are orthogonal when superimposing them produces each of the n² ordered pairs of symbols exactly once.

A ⊥ B ⟺ the map (i, j) ↦ ⟨A(i,j), B(i,j)⟩ is a bijection onto the n² symbol pairs

Equivalently: for any prescribed pair of symbols there is exactly one cell where the first square shows the first symbol and the second shows the second.

A set of squares pairwise orthogonal is called a set of mutually orthogonal Latin squares, abbreviated MOLS. The maximum size of such a set for a given order is a central quantity in design theory, bounded above by n − 1, with equality exactly when a projective plane of order n exists.

02Euler's officer problem

Euler posed the question in 1782 in concrete form: can thirty-six officers, one from each combination of six ranks and six regiments, be arranged in a six-by-six square so that each rank and each regiment appears once in every row and column?

1782
Euler poses the problem
The thirty-six officers problem is a request for two orthogonal Latin squares of order 6. Euler could not construct them.
1782
Euler's conjecture
He conjectured that no pair of orthogonal Latin squares exists for any order congruent to 2 modulo 4 — that is, orders 2, 6, 10, 14, 18, and so on.
1900
Tarry settles order 6
By systematic case analysis, Tarry verified that no orthogonal pair of order 6 exists. Euler's conjecture held in the one case anyone could check.
1959–1960
Bose, Shrikhande and Parker
Constructed orthogonal pairs of order 22, then order 10, then established that pairs exist for every order congruent to 2 modulo 4 except 2 and 6.

Key resultThe final answer

A pair of orthogonal Latin squares of order n exists for every n except n = 2 and n = 6. Euler's conjecture is false in every case beyond the two he could verify, and the two exceptions are genuinely exceptional rather than the start of a pattern.

03Why the conjecture was plausible and wrong

Euler had two data points — orders 2 and 6 both fail — and a natural residue class containing both. Tarry's verification of order 6 in 1900 strengthened the case without adding evidence about any larger order, since it confirmed the one instance already known to fail.

CautionTwo confirming instances are not a pattern

The conjecture survived 177 years on a sample of size two, and the first genuinely new case — order 10 — turned out to falsify it. This is a standard cautionary example in combinatorics: residue-class conjectures based on small cases are unusually prone to failure, because small orders are precisely where constructions are most constrained.

The refutation was not a single counterexample but a construction method. Bose, Shrikhande and Parker built machinery — pairwise balanced designs and recursive constructions — that produced orthogonal pairs in all the remaining orders at once. That is why the result is definitive rather than partial.

04The algebraic reading

Since a Latin square is a quasigroup multiplication table, orthogonality is a condition relating two quasigroup operations on the same set.

Operations ∘ and ∗ on Q are orthogonal ⟺
the map (x, y) ↦ ⟨x ∘ y, x ∗ y⟩ is a bijection Q² → Q²

A single condition on the pair, expressible in the first-order language of the two operations.

ProcedureVerifying orthogonality algebraically

in: two quasigroup operations → out: orthogonality decision

input: quasigroup operations ∘ and ∗ on a finite set Q
form the map φ : Q² → Q², φ(x, y) := ⟨x ∘ y, x ∗ y⟩
since |Q²| is finite, φ is a bijection iff φ is injective
so check: x ∘ y = u ∘ v and x ∗ y = u ∗ v jointly imply ⟨x,y⟩ = ⟨u,v⟩
if injective: the two Latin squares are orthogonal
for MOLS: check every pair in the family

Correctness: on a finite set injectivity and surjectivity coincide, so one check suffices. Caveat: this is quadratic in |Q|² and is a verification procedure, not a construction — finding orthogonal mates is the hard direction.

The algebraic form is what makes product constructions transparent. If ∘₁ ⊥ ∗₁ on Q₁ and ∘₂ ⊥ ∗₂ on Q₂, then the coordinatewise operations on Q₁ × Q₂ are orthogonal. So orthogonal pairs of orders m and n give an orthogonal pair of order mn, immediately.

05The product construction and its limits

The product construction generates a great deal from a little, and explains why Euler's residue class was the only plausible obstruction.

Prime powers are easy
For q a prime power, the field of order q yields q − 1 mutually orthogonal Latin squares via x ∘_a y = a·x + y for each non-zero a. This is the maximum possible.
Products multiply orders
Orthogonal pairs of orders m and n give one of order mn, so any order factoring into prime powers all admitting pairs is covered.
The gap
Orders congruent to 2 modulo 4 have a factor of 2 to exactly the first power, and order 2 admits no pair — so the product construction never reaches them. This is the structural reason Euler's class resisted.
The resolution
Bose, Shrikhande and Parker supplied constructions that bypass the product method entirely, using pairwise balanced designs to reach the residual orders directly.

06MOLS numbers and where to get them

The maximum number of mutually orthogonal Latin squares of order n, written N(n), is known exactly only for prime powers and a handful of small orders. For most n only bounds are known, and those bounds have been improved repeatedly.

CautionN(n) values are live research data, not textbook constants

Lower bounds on N(n) for non-prime-power orders are the output of ongoing construction work, and tables of them are revised as new designs are found. A table transcribed from a 1981 text would be out of date and would look authoritative while being wrong. The durable facts are the ones stated above: N(n) ≤ n − 1 always, N(q) = q − 1 for prime powers, N(n) ≥ 2 except for n = 2 and n = 6.

For current values and bounds, use the Handbook of Combinatorial Designs and the maintained design-theory tables routed from the sourcing policy page. The projective plane connection — N(n) = n − 1 exactly when a projective plane of order n exists — remains open for most orders and is one of the oldest unsettled questions in the subject.

Frequently asked

Does an orthogonal pair of order 10 exist?

Yes. Parker constructed one in 1959, and it was the first case genuinely contradicting Euler's conjecture, since order 6 had been confirmed to fail. Whether a full set of nine mutually orthogonal squares of order 10 exists — equivalently, whether a projective plane of order 10 exists — is a separate and much harder question, resolved negatively by a substantial computer search well after the source was written.

Why is order 6 exceptional?

There is no illuminating reason. Tarry's 1900 result was obtained by exhaustive case analysis, and modern proofs are shorter but still essentially computational. Orders 2 and 6 are genuinely sporadic exceptions rather than instances of a general obstruction, which is precisely why the conjecture based on them failed.

What does universal algebra actually contribute here?

It supplies the translation and the product construction. Recognising a Latin square as a quasigroup makes orthogonality a first-order condition on a pair of algebras, and then the direct product of algebras gives the multiplicative construction for free. The hard refutation itself is combinatorial, but the framing in which it sits is algebraic.

Sources and further reading

S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Millennium Edition (a corrected re-typesetting of Springer GTM 78, 1981).
G. Grätzer, Universal Algebra, 2nd edition, Springer.
R. McKenzie, G. McNulty and W. Taylor, Algebras, Lattices, Varieties, Volume I.

Original KEVOS® explanatory article. Written from the topic map of the cited works; no text is reproduced from them.