Using your Head is Permitted

January 2016 solution

The largest set of such mutually orthogonal Latin squares has 2k-1 elements for order 2k 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, {S1,...,St}. 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 Si2,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 Si1,1). We conclude that tn-1.

In the case of prime orders, p=n, this bound is tight, because we can set Sai,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 Sa two values along a row equalled each other: Sai,j=Sai,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 Sa two values along a column equalled each other: Sai,j=Sai',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, Sa and Sa' have two positions (i,j) and (i',j'), such that the pairs (Sai,j, Sa'i,j) and (Sai',j', Sa'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 pk for any prime p and any natural k. (And, in particular, for n=2k.) 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=pk, we can use the same construction, choosing Sai,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