Mutually orthogonal Latin squares based on cellular automata

DOI10.1007/S10623-019-00689-8MaRDI QIDQ2291667zbMATH OpenOpenAlexWikidataFDO

Authors Luca Mariot, Maximilien Gadouleau, Enrico Formenti, Alberto Leporati

Publication date 31 January 2020

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.08249

zbMATH Keywords

celluar automata linear Latin square orthogonal Latin squares

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Cellular automata (computational aspects) (68Q80)

Abstract: 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

q^{d - 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

m a t h b b F_{q}

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

m a t h b b F_{q}

. 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.

Review text

For prime powers \(q\), the authors consider Latin squares of order \(q^{d-1}\) associated to linear bipermutive cellular automata (LBCA) with alphabet of size \(q\) and local rule of diameter \(d\). The LBCA Latin squares form a subclass of the linear Latin squares of order \(q^{d-1}\) over a finite field \(F_q\) of order \(q\). The local rule for the LCBA automata is determined by a \(d\)-tuple \((a_0,\dots ,a_{d-1})\in F_q^{d-1}\), which can be identified with a polynomial \(p(x)=a_0+a_1x+\cdots +a_{d-1}x^{d-1}\in F_q[x]\). Because the automata is bipermutive, the coefficients \(a_0\) and \(a_{d-1}\) are forced to be nonzero. Therefore, this special class of linear Latin squares can be identified with the polynomials \(p(x)\) of degree \(d-1\) with nonzero constant term. Two LBCA Latin squares are orthogonal exactly when their corresponding polynomials are co-prime. By counting pairs of co-prime polynomials, the authors are able to count orthogonal LBCA Latin square pairs. They also present a construction for families of pairwise mutually orthogonal LBCA Latin squares.

Recommendations

Cites work

Cited in

(18)

Describes a project that uses

Uses Software

OEIS

This page was built for publication: Mutually orthogonal Latin squares based on cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2291667)