Latin Squares in Practice and in Theory II

3. Mutually Orthogonal Latin Squares (MOLS)

After the ``Euler spoiler'' examples of Bose, Parker and Shrikhande, pairs of orthogonal latin squares were known in every size except 2 and 6. For some sizes more was known. For example, if n is a prime, then one can construct n-1 mutually orthogonal latin squares.

Four MOLS of size 5. In the first, each row is shifted one spot to the left with respect to the row above it; in the second, each is shifted two spots to the left, etc. This pattern, using the n-1 possible slopes, gives n-1 MOLS for any prime size n.

What happens with other sizes? Let N(n) be the number of MOLS that exist of size n. It is known that

N(n) is at most n-1;
for primes (see above) and powers of primes, this upper bound can be attained.

Other numbers require special methods. The results are very incomplete, and the problem is currently a hot one in combinatorics. Here is a table from a recent paper by Charles Colbourn and Jeff Dinitz, reproduced with the authors' permission. They tabulate the best known lower bound on N(n), for n from 0 to 199.

      0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19

  0           1   2   3   4   1   6   7   8   2  10   5  12   3   4  15  16   3  18
 20   4   5   3  22   6  24   4  26   5  28   4  30  31   5   4   5   6  36   4   5
 40   7  40   5  42   5   6   4  46   7  48   6   5   5  52   5   6   7   7   5  58
 60   4  60   4   6  63   7   5  66   5   6   6  70   7  72   5   5   6   6   6  78
 80   9  80   8  82   6   6   6   6   7  88   6   7   6   6   6   6   7  96   6   8
100   8 100   6 102   7   7   6 106   6 108   6   6  13 112   6   7   6   8   6   6
120   7 120   6   6   6 124   6 126 127   7   6 130   6   7   6   7   7 136   6 138
140   6   7   6  10  10   7   6   7   6 148   6 150   7   8   8   7   6 156   7   6
160   9   7   6 162   6   7   6 166   7 168   6   8   6 172   6   6  14   9   6 178
180   6 180   6   6   7   9   6  10   6   8   6 190   7 192   6   7   6 196   6 198

The current state of the art in mutually orthogonal latin squares. This table gives, for n from 0 to 199, the best known lower bound for the number N(n) of MOLS of size n. Note that for n prime or a power of a prime, the lower bound is the maximum, n-1. Numbers in red are brand new or only a few years old. For more information, consult the CRC Handbook of Combinatorial Designs.