Automorphisms of Transition Graphs for Linear Cellular Automata
Edward Powley and Susan Stepney
The transition graph of a cellular automaton (CA) represents the CA’s global dynamics. The automorphisms of the transition graph are its selfisomorphisms or “symmetries”, and in a sense these are precisely the symmetries of the CA’s dynamics.
Previously we have argued that studying how the total number of automorphisms varies with the number of cells on which the CA operates yields a partial classification of CArules. One of the classes thus identified consists mainly of linear CAs; that is, CAs whose local rules are linear functions.
In this paper, we use the algebraic properties of linear CAs in general, and of one linear CA (elementary rule 90) in particular, to derive an expression for the number of automorphisms admitted by that CA. We use this expression to produce numerical results, and observe that the number of automorphisms as a function of the number of cells exhibits a correlation with a number-theoretic function, the suborder function.
Keywords: Linear cellular automata, rule 90, transition graphs, automorphisms, symmetry, suborder function.