2019/06/30 by Luca Mariot, Maximilien Gadouleau, Enrico Formenti +1 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #cs.DM #math.CO #nlin.CG
paper · pdf · doi:10.1007/s10623-019-00689-8
25 pages, 3 figures
arxiv created 2019/10/31 · arxiv updated 2019/11/01
We investigate sets of Mutually Orthogonal Latin Squares (MOLS) generated by Cellular Automata (CA) over finite fields. After introducing how a CA defined by a bipermutive local rule of diameter d over an alphabet of q elements generates a Latin square of order qd-1, we study the conditions under which two CA generate a pair of orthogonal Latin squares. In particular, we prove that the Latin squares induced by two Linear Bipermutive CA (LBCA) over the finite field \mathbbFq are orthogonal if and only if the polynomials associated to their local rules are relatively prime. Next, we enumerate all such pairs of orthogonal Latin squares by counting the pairs of coprime monic polynomials with nonzero constant term and degree n over \mathbbFq. Finally, we present a construction of MOLS generated by LBCA with irreducible polynomials and prove the maximality of the resulting sets, as well as a lower bound which is asymptotically close to their actual number.