Subsquare-free Latin squares of odd order (Q854835)

A Latin square of order \(n\) is a square matrix of order \(n\) in which each of \(n\) symbols appears once in each row and once in each column. Long standing problems include proving the existence or non-existence of Latin squares with various properties, and one of the more difficult and significant problems is to determine if there exists a Latin square of order \(n\) with no proper subsquare which is also a Latin square. \textit{Proper} means the order is greater than two but less than \(n\). A Latin square with no proper subsquares is said to be \(N_\infty\). It was previously known that if \(n\) is divisible by a prime greater than or equal to five, then there exists an \(N_\infty\) Latin square. The authors are to be congratulated as they are able to improve significantly on this result. They prove: If \(n\) is odd and divisible by three, then there is an \(N_\infty\) Latin square of order \(n\). From this and the earlier result, if \(n\) is odd, there exists an \(N_\infty\) Latin square of order \(n\). The existence of \(N_\infty\) Latin squares of large orders of the form \(2^a3^b\) for \(a>1\) remains open. One of the present authors, \textit{I. M. Wanless} [Eur. J. Comb. 25, 393--413 (2004; Zbl 1047.05007)] gave a candidate for \(N_\infty\) for each odd \(n\) which had been verified by computer for \(n\leq 10,000\). The authors prove this earlier conjecture for the case that \(n\) is divisible by 3, which completes the odd \(n\) case. The authors' method involves an algorithm for checking certain cases which uses a computer in an interesting way.