Latin Hypercubes based on Linear Cellular Automata


Latin squares and hypercubes have a wide range of applications in statistics, cryptography and coding theory. In this talk, we review a construction of Latin squares based on cellular automata (CA) that was introduced by Mariot, Formenti and Leporati at AUTOMATA 2016, and we generalize it to the case of Latin hypercubes of dimension $k > 2$. We first show a characterization of Latin cubes generated by bipermutive CA with linear rules, where the central coefficients define an invertible Toeplitz matrix. Next, for dimension $k > 3$ we prove that linear bipermutive CA generating Latin hypercubes are defined by sets of invertible Toeplitz matrices with partially overlapping coefficients. In particular, we remark that the overlap relation can be described by a specific kind of regular de Bruijn graph, which allows to count and enumerate all linear CA rules generating Latin Hypercubes.

MDSC Seminar
Salle des RĂ©unions, Laboratoire I3S, Sophia Antipolis, France

Note: This talk is based on a collaboration with Max Gadouleau.