# Using your Head is Permitted

## January 2016 solution

The largest set of such mutually orthogonal Latin squares has
2^{k}-1 elements for order 2^{k} and
*p*-1 elements for prime order *p*.
Mutually orthogonal Latin squares (or MOLS) is a hot topic of study in
combinatorics. For more information, see
here and
here,
and for a glimpse into the state-of-the-art of MOLS searching, see
here.

The maximal size of any set of MOLS of order *n*, for any *n*, is
bounded by *n*-1. To see this, consider any set of such MOLS,
{*S*^{1},...,*S*^{t}}. We can always
assume that the top row of all Latin squares in the set is
"1 2 ... *n*". This is because renaming the symbols in a Latin square
retains both its Latin square properties and its orthogonality properties.

Now, consider element *S*^{i}_{2,1} for
*i*=1,...,*t*.

Clearly, no two such elements can equal each other (for all such pairs have
already appeared in the top row). Furthermore, none of them can equal "1",
because each of them already had a "1" in the same column (in
*S*^{i}_{1,1}). We conclude that *t*≤*n*-1.

In the case of prime orders, *p*=*n*, this bound is tight, because
we can set *S*^{a}_{i,j}=(*ai*+*j*) mod *p*.
(For convenience, we have renamed the symbols here 0,...,*p*-1 rather than
1,...,*p*. Clearly, this change makes no difference.)

To prove that each of these is a Latin square:

Suppose that for some *S*^{a} two values along a row equalled
each other: *S*^{a}_{i,j}=*S*^{a}_{i,j'} implies
(*ai*+*j*) mod *p* = (*ai*+*j*') mod *p*,
which implies
*ai*+*j* = *ai*+*j*' (mod *p*),
which implies
*j* = *j*' (mod *p*),
which implies
*j* = *j*'.

Suppose now that for some *S*^{a} two values along a column equalled
each other: *S*^{a}_{i,j}=*S*^{a}_{i',j} implies
(*ai*+*j*) mod *p* = (*ai*'+*j*) mod *p*,
which implies
*ai*+*j* = *ai*'+*j* (mod *p*),
which implies
*ai* = *ai*' (mod *p*),
which implies
*i* = *i*' (mod *p*),
which implies
*i* = *i*'.

Each element is therefore a Latin square. To show orthogonality, suppose that
some pair of Latin squares, *S*^{a} and
*S*^{a'} have two positions (*i*,*j*) and
(*i*',*j*'), such that the pairs
(*S*^{a}_{i,j},
*S*^{a'}_{i,j}) and
(*S*^{a}_{i',j'},
*S*^{a'}_{i',j'}) are equal.
Then, with all calculations done modulo *p*, we have
*ai*+*j* = *ai*'+*j*' and *a*'*i*+*j* = *a*'*i*'+*j*'.
Subtracting these two equations we get
(*a*-*a*')*i* = (*a*-*a*')*i*',
so either *a* = *a*' or *i*=*i*'. The latter condition
cannot hold because the elements are Latin squares: no element can repeat
twice on the same row. We conclude that this is a set of MOLS.

In fact, all of the above works not just for MOLS of order *p* but also
for MOLS of order *p*^{k} for any prime *p* and any
natural *k*. (And, in particular, for *n*=2^{k}.)
The reason this is so is that all calculations performed were field operations.
Nowhere did we use any property of "mod *p*" other than the fact that it
is a field. When *n*=*p*^{k}, we can use the same
construction, choosing
*S*^{a}_{i,j}=*ai*+*j*, except
for the fact that instead of this equality being true "mod *p*", it should
now be true over an arbitrarily chosen field of size *n* (i.e., the
product and the addition are the product and addition operations of the field,
the row number, *i*, and the column number, *j*, are mapped into the
elements of the field, and the Latin square number, *a*, is mapped into
the non-zero elements of the field.).
The same proof will show that this is an MOLS (and, of course, there is no
change to the proof of maximality).

Q.E.D.

Back to riddle

Back to main page