On the transversals of Latin squares generated by nonlinear bipermutive cellular automata
For researchers in combinatorial design and cellular automata, this provides a theoretical characterization and empirical lower bound for transversals in nonlinear BCA-generated Latin squares, though the results are preliminary.
This paper investigates conditions for Latin squares generated by nonlinear bipermutive cellular automata to have an orthogonal mate, proving that the main diagonal forms a transversal iff the generating function induces an invertible CA. Exhaustive search shows d=6 is the smallest diameter for such nonlinear rules.
In this short paper, we begin to investigate the conditions under which a generic Bipermutive Cellular Automaton (BCA) with no-boundary conditions of diameter $d$ generates a Latin square of order $N=2^{d-1}$ admitting an orthogonal mate, without relying on the linearity of the local rule. Since an orthogonal mate exists if and only if the Latin square can be partitioned into $N$ disjoint \emph{transversals}, we start by characterizing the subclass of BCA whose Latin squares have a transversal on the main diagonal. In particular, we prove that the main diagonal forms a transversal if and only if the generating function of the bipermutive local rule induces an invertible CA with periodic boundary conditions on a configuration of size $d-1$. We then perform exhaustive search experiments, showing that $d=6$ is the smallest diameter for which there exist nonlinear bipermutive CA that generate Latin squares with a transversal on the main diagonal.