Hunting for MOLS: a bootstrap project
Chip Eastham
participate in a coarsely grained parallel computing project to
resolve the (non-)existence of a set of 3 mutually orthogonal Latin
squares of order 10.
There are many open questions about sets of mutually orthogonal Latin
squares (MOLS), but a good bit is known. E.g. there are at least two
orthogonal Latin squares of every order except 2 and 6. (Bose,
Shrikhande, and Parker, 1960; Wilson, 1974)
I thought I'd set forth the mathematical background here, although I'm
not sure about cross-posting between a Google Group and Usenet.
A Latin square of order N is an NxN array in which each of N symbols
appears exactly once in every row and in every column. Two Latin
squares are said to be orthogonal iff matching the symbols that appear
in corresponding entries (same row, same column) of the two squares
produces exactly N^2 distinct ordered pairs of symbols. A set of
Latin squares is _mutually orthogonal_ iff every distinct pair of
Latin squares in the set are orthogonal.
Let M(N) be the maximum size of a set of MOLS of order N. It is known
that M(N) <= N-1, and that this upper bound is attained when N is a
prime or a prime power (using a design from projective geometry). It
is not known if the upper bound can be attained in other cases.
Latin squares remain so under various "symmetry" operations:
- permutation of rows
- permutation of columns
- permutation of symbols
- interchanging the roles of rows and columns
- interchanging the roles of rows and symbols
- interchanging the roles of columns and symbols
A word of explanation is needed about the last two operations. To
make sense these require that the symbols used be the same as the
indexes for rows and columns, e.g. {1,...,N}.
These symmetries apply with some restrictions to preserving MOLS,
which allows us to cut down on the search space by assuming WLOG
something about the form taken of solutions. I'll drill down into the
details in my next post.
regards, chip
Chip Eastham
On Dec 31 2009, 10:47 am, Chip Eastham <hardm...@gmail.com>
wrote (in part):
> Latin squares remain so under various "symmetry" operations:
>
> - permutation of rows
> - permutation of columns
> - permutation of symbols
> - interchanging the roles of rows and columns
> - interchanging the roles of rows and symbols
> - interchanging the roles of columns and symbols
>
> A word of explanation is needed about the last two operations. To
> make sense these require that the symbols used be the same as the
> indexes for rows and columns, e.g. {1,...,N}.
>
> These symmetries apply with some restrictions to preserving MOLS,
> which allows us to cut down on the search space by assuming WLOG
> something about the form taken of solutions. I'll drill down into the
> details in my next post.
The different symmetries of Latin squares above
may appear strange, but if one looks at them
in terms of orthogonal arrays, it can be seen
that those symmetries emerge from a small set
of operations. Also orthogonal arrays define
a set of mutually orthogonal Latin squares as
easily as they define a single Latin square:
[Latin square -- Wikipedia]
http://en.wikipedia.org/wiki/Latin_square
(see section on orthogonal array representations)
Because of the equivalence of many Latin
squares with respect to symmetry operations,
it helps to pursue an exhaustive search
strategy if we can use equivalences to cut
down the search space. One can place a
single Latin square in "reduced" or "standard
form" by permuting the rows and columns so
that the symbols appears in ascending order
in both the first row and first column.
The Wikipedia article shows counts for the
Latin squares of certain small orders as
well as for the reduced Latin squares, a
factor of n!(n-1)! being accounted for by
sorting the rows and columns. It also links
to the OEIS entries for the same.
Combining all the symmetries into a single
equivalence relation gives what are termed
the "main classes" of Latin squares:
[Number of main classes of Latin squares of order n]
http://www.research.att.com/~njas/sequences/A003090
For n = 6 there are only 12 main classes,
while for n = 10 there are 34817397894749939.
When we search for MOLS (sets of mutually
orthogonal Latin squares), we cannot apply
the symmetry reductions indiscriminately.
We can put the "first" Latin square into
reduced form; applying the corresponding
row and column permutations to the other
squares in the set preserves orthogonality.
We can apply independent symbol permutations
to each square without loss of orthogonality.
Therefore the first row of all squares can
be assumed in ascending order.
Because of our control over first rows and
to a lesser extent first columns, it will
be convenient to use symbols {0,..,n-1} for
MOLS of order n, and consider rows/columns
to be zero-indexed.
One further element of symmetry reduction
in the search space can now be described.
In the "first" (reduced) Latin square we
have located two of each symbol 1,..,n-1
and only one of symbol zero. The remaining
(n-1) zeros must appear in distinct rows
and columns of the lower right (n-1)x(n-1)
subsquare of the "first" Latin square. We
note the locations of these zeros define a
permutation pi of order n-1, (k,pi(k)), if
we think of the columns as a function of
the rows.
But we need not consider all possible pi
here. Instead we can arrange that the
"disjoint cycle" representation of pi is
of special form, mentioning the symbols
1,..,n-1 in order and having cycles of
ascending lengths. Instead of (n-1)!
possibilities for pi, we have only as
many as the unordered partitions of n-1.
For n=6 this improves 5! = 120 to 7, and
for n=10 from 9! = 362880 to 30. [Sketch
of proof: After the "first" Latin square
is in reduced form, apply a permutation
equally to the final n-1 rows and columns
so that locations of zeros in that portion
gives a permutation pi of the above form,
and apply the same row/column permutation
to other squares (preserves orthogonality).
Relabel the nonzero symbols to put the
"first" Latin square back in reduced form,
and relabel the other squares to get their
first rows in ascending order.]
One final element of search space reduction
has nothing to do with the symmetries of
Latin squares, but does concern the order
of squares after the first. We'd like to
impose a canonical ordering so that the
same set of MOLS is sought only once, and
for this we impose a lexicographic order
on the first columns of the squares. The
"first" Latin square is reduced and thus
already has the least first column. Each
of the remaining first columns has (after
an initial zero) a derangement of symbols
1,..,n-1. That is, a permutation such
that no symbol 1,..,n-1 remains in its
"natural" place (since the other squares
are orthogonal to the first and each other).
Since the first columns are necessarily
distinct, the ordering is well-defined and
in fact determined by the second entry of
the first column.
regards, chip