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.
Constructing MOLS
-
0As Euler's conjecture illustrates, the case of "oddly even" pairs of MOLS (order 4n+2) is the hard case. For MOLS pairs of order 4n the problem can be reduced to finding a pair of order n. My choice of reference on this material would likely be van Lint and Wilson's *A Course in Combinatorics* (Cambridge University Press, 2nd ed. 2001). – 2012-10-16
-
0Thanks. Seems like I'm lucky then; upon further inspection I could narrow down my requirement to only MOLS of size 4n. Does this change things? – 2012-10-16
-
0Have you read [the Wikipedia article](http://en.wikipedia.org/wiki/Graeco-Latin_square)? It gives an indication of why Euler was wrong, and of the difficulty of the construction in the oddly even case. The case when an order is a prime power is fully solved by finite fields of that order. Also there is a tensor product-like construction, so that a pair of MOLS of order $n$ and of order $m$ combine to give a pair of order $nm$. Let me check if these simple constructions have not already been detailed in previous answers. – 2012-10-16
-
0Check out @GerryMyerson's answer to [Mutually orthogonal latin squares of order $mn$ from order $m$ and order $n$](http://math.stackexchange.com/q/170149/3111). The finite fields used to construct complete families of MOLS of order $p^k$ for prime $p$ is at least referenced in Douglas Stone's answer to [Directory of MOLS that are prime powers?](http://math.stackexchange.com/q/170569/3111), with a pointer to a fine book by P.J. Cameron. – 2012-10-17
-
0Bottom line: a construction is straightforward for a pair of MOLS of order $4n$ once you have a pair of order $n$. If you push the finite field and tensor product constructions, then you can indeed construct pairs of order $4n$ for arbitrary $n$ (by working with the prime factorization of $4n$). – 2012-10-17
1 Answers
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.