Constructing MOLS

Question

I'm looking for a method to construct a pair of two MOLS of even side 4n, n > 2. Is there a method for this, preferably one that is simple to implement? I believe this book to contain a simple construction in ch.4, but I do not have access to this resource.

Answer 1

A recipe for finding a pair of mutually orthogonal latin squares (MOLS) of order $4n$ can be framed in terms that MacNeish presented in 1922.

First factor $4n$ into its prime power factors: $2^{k_1}...p^{k_m}$. By assumption $k_1 > 1$ because the factor $4$ (at least) appears in our order.

Next produce a pair of MOLS for each prime power factor, using the existence of a finite field of that order to produce at least two such. Note that the construction grants us $p^k - 1$ MOLS of order $p^k$, which is the most possible. It is a famous open problem whether $n-1$ MOLS of order $n$ exist for any orders that are not prime powers.

Finally combine the corresponding mutually orthogonal pairs of latin squares of respective prime power orders into two latin squares of order $4n$ by applying the "direct product" construction described by MacNeish (and possibly known earlier to Euler; he was a pretty bright guy). That is, suppose $L$ is a latin square of order $l$ and $M$ a latin square of order $m$. Construct a square $P$ of order $lm$ simply by pairing the symbol $u \in \{1,..,l\}$ in $L_{i,j}$ and the symbol $v \in \{1,..,m\}$ in $M_{r,s}$ and placing this combined symbol (as arithmetically encoded ordered pair) in $P_{i+l(r-1),j+l(s-1)}$:

$$(u,v) \rightarrow u + l(v-1) $$

If this "direct product" construction be performed with MOLS $L_1$ and $L_2$ of order $l$ and respective MOLS $M_1$ and $M_2$ of order $m$, the two results $P_1$ and $P_2$ will be an orthogonal pair of latin squares of order $lm$. The proof of this does not require any condition on coprimality of factor $l,m$. One needs only to verify that the arithmetic encoding preserves distinction of both symbols in the ordered pair.

The importance of having the exponent of $2$ greater than $1$ is that if only a single factor of $2$ is present, the construction is stuck because (trivially) there do not exist a pair of MOLS of order $2$. On the other hand if we apply the recipe above with no factors of $2$ (i.e. to odd orders), it will always work because the family of odd prime power $p^k$ order MOLS provides at least two.

Added: There's a shortcut to produce just a pair of MOLS of odd order, and since that's all we need, it's attractive for producing the required components. For the powers of two we can get by with pre-constructing pairs of MOLS of orders four and eight, and then combining them as above using the "direct product" construction.