Atomic Latin squares based on cyclotomic orthomorphisms (Q2571262)

A Latin square is an \(n \times n\) array filled with the symbols \(1,\dots,n\) such that each symbol appears in each row and each column. A pair of rows is Hamiltonian if the permutation determined (in two-row notation) by the two rows is transitive; equivalently, if the \(2 \times n\) Latin rectangle contains no \(2 \times k\) Latin subrectangle for \(k < n\). A Latin square is atomic if it and all of its conjugates are row-Hamiltonian. The concept is related to a square not being a composition of two smaller Latin squares. Only one example of an atomic Latin square of composite order (namely 27) was previously known. In this paper the author uses cyclotomic orthomorphisms in finite fields to construct this example, as well as examples for 14 new orders. The same method constructs many new atomic Latin squares of prime order. A variation of the method can be used to construct perfect 1-factorisations of the complete graph \(K_{q+1}\) for many prime powers \(q\). (A 1-factorisation of \(K_n\) is a partition of the edges into perfect matchings; the 1-factorisation is perfect if the union of every pair of these perfect matchings is a Hamiltonian cycle.) The author uses this method to construct perfect 1-factorisations for 33 values of prime powers \(q\) where the existence of such factorisations was previously unknown. The idea involves a computer search for values small enough to be feasible yet large enough to be interesting. An invariant called train is used to distinguish non-isomorphic Latin squares. Note: the author reports that the results on perfect 1-factorisations are similar to those of Dinitz and Dukes (manuscript) and to Leck, who use quotient coset starters, mentioning that it seems to be a case of an idea whose time has come.