2026/05/15 by Alberto Dennunzio, Maximilien Gadouleau, Luca Mariot · 1 voice
Computer Science · Mathematics · #cs.FL #math.CO
paper · pdf · doi:10.48550/arxiv.2605.18875
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=2d-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 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.