Analysis of Additive Binary Valued Cellular Automata Using Roots of Unity

Abstract

This paper considers binary valued additive cellular automata rules acting on cylinders of size n in terms of circulant matrices and roots of unity. The purpose is to illustrate some of the possibilities of such an approach. Means of determining maximum tree heights and cycle periods are given, together with a method of computing conditions for states to be fixed points or to lie on cycles of given periods. The anomalous shifts that lead to maximum cycle periods being smaller than predicted for certain cylinder sizes are explained and it is shown that the set of all rules on cylinders of odd size n will have specific spectra of cycle periods determined by the prime decomposition of n. Finally, numeric properties of the n-th roots of unity when coupled with mod(2) arithmetic are exploited to group additive rules acting on a cylinder of size n into classes having the same eigenvalues for their circulant matrix representations.