## Mathematical Analysis of a Simple Cellular Automaton

The cellular automaton rule of Eq. 1 is particularly simple and admits a rather complete mathematical analysis.

The fractal patterns of Figs. 2 and 3 may be characterized in a simple algebraic manner. If no reduction modulo 2 were performed, then the values of sites generated from a single nonzero initial site would simply be the integers appearing in Pascal's triangle of binomial coefficients. The pattern of nonzero sites in Figs. 2 and 3 is therefore the pattern of odd binomial coefficients in Pascal's triangle. (See Stephen Wolfram, ''Geometry of Binomial Coefficients,'' to be published in American Mathematical Monthly.)

This algebraic approach may be extended to determine the structure of the state transition diagram of Fig. 6. (See O. Martin, A. Odlyzko, and S. Wolfram, ''Algebraic Properties of Cellular Automata,'' Bell Laboratories report (January 1983) and to be published in Communications in Mathematical Physics.) The analysis proceeds by writing for each configuration a characteristic polynomial

where is a dummy variable, and the coefficient of is the value of the site at position . In terms of characteristic polynomials, the cellular automaton rule of Eq. 1 takes on the particularly simple form

where

and all arithmetic on the polynomial coefficients is performed modulo 2. The reduction modulo implements periodic boundary conditions. The structure of the state transition diagram may then be deduced from algebraic properties of the polynomial . For even one finds, for example, that the fraction of states on attractors is , where is defined as the largest integral power of 2 that divides (for example, ).

Since a finite cellular automaton evolves deterministically with a finite total number of possible states, it must ultimately enter a cycle in which it visits a sequence of states repeatedly. Such cycles are manifest as closed loops in the state transition graph. The algebraic analysis of Martin et al. shows that for the cellular automaton of Eq. 1 the maximal cycle length (of which all other cycle lengths are divisors) is given for even by

or

For odd , may be shown to divide

and in fact is almost always equal to this value (the first exception occurs for ). Here is a number theoretical function defined to be the minimum positive integer for which modulo . The maximum value of , typically achieved when is prime, is . The maximal cycle length is thus of order , approximately the square root of the total number of possible states .

An unusual feature of this analysis is the appearance of number theoretical concepts. Number theory is inundated with complex results based on very simple premises. It may be part of the mathematical mechanism by which natural systems of simple construction yield complex behavior.