Mutually orthogonal Latin squares

Imagine a grid of cards.

You want to fill it with patterns. Each row and column must have different items. You can use suits and face values. You can even use colors and words. This is like a puzzle.

Some patterns are special. They are called orthogonal. This means they do not repeat the same pairs. A man named Euler studied these patterns. He found many ways to make them. These grids help us understand how things work together.

Imagine you have a grid of cards.

You want to fill the grid with patterns. Each row and each column must have different items. You can use suits and face values from a deck. You can also use colors and words. This is a type of math puzzle.

Some patterns are very special. We call them orthogonal. This means if you stack two grids together, every pair is unique. No two cells will have the same combination. This makes the two patterns independent. Knowing one part tells you nothing about the other.

Leonhard Euler studied these grids. He called them Graeco-Latin squares. He used Latin letters and Greek letters to make them. Euler tried to solve a hard puzzle called the thirty-six officers problem.

He could not solve it for a size of six. For a long time, people thought these squares did not exist for certain sizes. But in 1959, math experts proved him wrong. They found that these squares do exist for almost all sizes. Today, scientists even study these patterns using quantum physics.

Imagine you have a grid of symbols. You want to fill the cells so that every row and every column has each symbol exactly once. This is called a Latin square. Some of these squares are very special when you put them together. If you stack two squares on top of each other, you create pairs in every cell. If every single pair in that grid is unique, the squares are called orthogonal. This means the two patterns are independent. Knowing one part of the pair tells you nothing about the other part.

To make these special squares, you can use different sets of symbols. A famous way to do this is with a Graeco-Latin square. This name comes from using Latin letters for one square and Greek letters for the second. When you combine them, every cell gets one Latin letter and one Greek letter. This ensures that no two cells have the same pair. You can also use other things like colors and words to make these patterns. For example, you could use different fonts and colors to test how they look together.

People have been playing with these patterns for a very long time. Long before famous mathematicians studied them, people used playing cards for these puzzles. One puzzle asked you to arrange sixteen cards in a grid. Each row and column had to have all four suits and all four face values. A math expert named Kathleen Ollerenshaw later found there were 144 ways to solve this. This was a correction to an earlier mistake made by Rouse Ball. There are actually 1,152 total solutions if you count all the ways to rotate the grid.

Leonhard Euler was a famous mathematician who studied these grids deeply. In the late 1700s, he worked on a puzzle called the thirty-six officers problem. This puzzle was similar to the card game but used ranks and regiments. Euler could build these squares for many sizes, like those that are odd numbers. However, he could not find a solution for a size of six. He guessed that these squares might never exist for certain even numbers. This idea became known as Euler's conjecture.

For many years, people wondered if Euler was right about his guess. In 1901, Gaston Tarry proved that a size of six was impossible. But in 1959, researchers R.C. Bose, S. S. Shrikhande, and E. T. Parker proved him wrong. They found that these squares actually do exist for almost all sizes. Parker even used a very early digital computer to find a solution for size ten. Today, scientists are even studying these patterns in the world of quantum physics.

In the field of combinatorics, mathematicians study the arrangement of sets and patterns. One fascinating concept is the mutually orthogonal Latin square, often abbreviated as MOLS. A Latin square is a grid where every row and every column contains each symbol exactly once. When you take two Latin squares of the same size, or order, and superimpose them, you create a grid of ordered pairs. If every single pair in that grid is unique, the two squares are called orthogonal. This means the two patterns are independent. Knowing the value of one variable gives no information about the value of the other.

To understand how this works, consider a Graeco-Latin square. This is a specific type of orthogonal arrangement where two different sets of symbols are used. For example, Leonhard Euler used the first upper-case letters of the Latin alphabet for one set. He used the first lower-case letters of the Greek alphabet for the second set. When these are combined into a grid, each cell contains one Latin letter and one Greek letter. This ensures that every possible pair from the two sets occurs exactly once. The arrangement can be decomposed back into two separate, orthogonal Latin squares.

There is a specific mathematical requirement for a Latin square to have an orthogonal mate. This requirement involves a concept called a transversal. A transversal is a selection of positions in a square where you pick exactly one cell from every row and every column. For these positions to form a transversal, all the entries in those cells must be distinct. A Latin square of order n possesses an orthogonal mate if and only if it has n disjoint transversals. Interestingly, the Cayley table of any group of odd order forms a Latin square that has an orthogonal mate. These are known as group-based Graeco-Latin squares.

History shows that these patterns were used as puzzles long before they were formally studied. One old puzzle used a standard deck of playing cards. The goal was to arrange sixteen cards, including aces, kings, queens, and jacks, into a 4x4 grid. Every row and column had to contain all four suits and all four face values. While Rouse Ball once claimed there were 72 solutions, Kathleen Ollerenshaw later corrected this. She found there are actually 144 distinct solutions. If you include all possible rotations and reflections, there are 1,152 total solutions.

Leonhard Euler significantly advanced this study in the late 1700s. He was presented with the "thirty-six officers problem," which is similar to the card puzzle but uses ranks and regiments. Euler was able to construct Graeco-Latin squares for orders that were odd or multiples of four. However, he could not find a solution for an order of six. This led him to conjecture that no such squares exist for any order that is an odd multiple of two. This prediction became known as Euler's conjecture.

For over a century, mathematicians worked to prove or disprove Euler's idea. In 1901, Gaston Tarry used a proof by exhaustion to confirm that order six squares do not exist. However, Euler's broader conjecture was eventually proven false. In 1959, R.C. Bose and S. S. Shrikhande found counterexamples known as "Euler spoilers" for order 22. Shortly after, E. T. Parker used a UNIVAC 1206 Military Computer to find a counterexample for order 10. This was one of the earliest instances of a combinatorics problem being solved by a digital computer. Parker, Bose, and Shrikhande eventually proved that Graeco-Latin squares exist for all orders except two and six.

Today, these concepts extend into the realm of quantum physics. Researchers have studied mutually orthogonal quantum Latin squares, where the elements are quantum states. In 2021, a team of physicists found an arrangement of 36 entangled officers. This setup provides a new way to create quantum error detection codes. This allows a six-level system to be encoded into a three 6-level system.

Beyond physics, MOLS are deeply connected to geometry. A complete set of MOLS of order n is equivalent to a finite affine plane of order n. These planes can be extended into finite projective planes. Because complete sets of MOLS exist whenever n is a prime number or a power of a prime, these projective planes exist as well. The study of these structures remains a central part of modern mathematical research.