3. A Simple Example

A. Introduction

This section introduces algebraic techniques for the analysis of additive cellular automata in the context of a specific simple example. Section 4 applies the techniques to more general cases. The mathematical background is outlined in the appendices. The cellular automaton considered in this section consists of sites arranged around a circle, where each site has value or . The sites evolve so that at each time step the value of a site is the sum modulo two of the values of its two nearest neighbours at the previous time step:

This rule yields in many respects the simplest non-trivial cellular automaton. It corresponds to rule 90 of [1], and has been considered in several contexts elsewhere (e.g. [4]).

The time evolution (3.1) is represented by multiplication of the characteristic polynomial for a configuration by the dipolynomial

according to Eq. (2.5). At each time step, characteristic polynomials are reduced modulo (which is equal to since all coefficients are here, and throughout this section, taken modulo two). This procedure implements periodic boundary conditions as in Eq. (2.2) and removes any inverse powers of .

Equation (3.2) implies that an initial configuration containing a single nonzero site evolves after time steps to a configuration with characteristic dipolynomial

For (before ``wraparound'' occurs), the region of nonzero sites grows linearly with time, and the values of sites are given simply by binomial coefficients modulo two, as discussed in [1] and illustrated in Fig. 1. (The positions of nonzero sites are equivalently given by where the give the positions of nonzero digits in the binary decomposition of the integer .) The additive superposition property implies that patterns generated from initial configurations containing more than one nonzero site may be obtained by addition modulo two (exclusive disjunction) of the patterns (3.3) generated from single nonzero sites.

B. Irreversibility

Every configuration in a cellular automaton has a unique successor in time. A configuration may however have several distinct predecessors, as illustrated in the state transition diagram of Fig. 2. The presence of multiple predecessors implies that the time evolution mapping is not invertible but is instead ``contractive''. The cellular automaton thus exhibits irreversible behaviour in which information on initial states is lost through time evolution. The existence of configurations with multiple predecessors implies that some configurations have no predecessors (1). These configurations occur only as initial states, and may never be generated in the time evolution of the cellular automaton. They appear on the periphery of the state transition diagram of Fig. 2. Their presence is an inevitable consequence of irreversibility and of the finite number of states.

Lemma 3.1.

Configurations containing an odd number of sites with value 1 can never be generated in the evolution of the cellular automaton defined in Sect. 3A, and can occur only as initial states.

Consider any configuration specified by characteristic polynomial . The successor of this configuration is , taken, as always, modulo . Thus

for some dipolynomials and . Since for , . Hence contains an even number of terms, and corresponds to a configuration with an even number of nonzero sites. Only such configurations can therefore be reached from some initial configuration .

An extension of this lemma yields the basic theorem on the number of unreachable configurations:

Theorem 3.1.

The fraction of the possible configurations of a size cellular automaton defined in Sect. 3A which can occur only as initial states, and cannot be reached by evolution, is for odd and for even.

A configuration is reachable after one time step of cellular automaton evolution if and only if for some dipolynomial ,

so that

for some dipolynomials and . To proceed, we use the factorization of given in Eq. (A.7), and consider the cases even and odd separately.

(a) even. Since by Eq. (A.4), (taken, as always, modulo 2), and by Eq. (A.7),

for even , Eq. (3.5) shows that

in this case. But since contains a constant term, is thus an ordinary polynomial if is chosen as such. Hence all reachable configurations represented by a polynomial are of the form

for some polynomial . The predecessor of any such configuration is , so any configuration of this form may in fact be reached. Since deg , deg . There are thus exactly reachable configurations, or of all the possible configurations.

(b) odd. Using Lemma 3.1 the proof for this case is reduced to showing that all configurations containing an even number of nonzero sites have predecessors. A configuration with an even number of nonzero sites can always be written in the form . But

giving an explicit predecessor for .

The additive superposition principle for the cellular automaton considered in this section yields immediately the result:

Lemma 3.2.

Two configurations and yield the same configuration after one time step in the evolution of the cellular automaton defined in Sect. 3A if and only if , where .

Theorem 3.2.

Configurations in the cellular automaton defined in Sect. 3A which have at least one predecessor have exactly two predecessors for odd and exactly four for even.

This theorem is proved using Lemma 3.2 by enumeration of configurations which evolve to the null configuration after one time step. For odd, only the configurations and (corresponding to site values ) have this property. For even, has the form

where the are the four polynomials of degree less than two. Explicitly, the possible forms for are , , , and .

C. Topology of the State Transition Diagram

This subsection derives topological properties of the state transition diagrams illustrated in Fig. 2. The results determine the amount and rate of ``information loss'' or ``self organization'' associated with the irreversible cellular automaton evolution.

The state transition network for a cellular automaton is a graph, each of whose nodes represents one of the possible cellular automaton configurations. Directed arcs join the nodes to represent the transitions between cellular automaton configurations at each time step. Since each cellular automaton configuration has a unique successor, exactly one arc must leave each node, so that all nodes have out-degree one. As discussed in the previous subsection, cellular automaton configurations may have several or no predecessors, so that the in-degrees of nodes in the state transition graph may differ. Theorems 3.1 and 3.2 show that for odd, of all nodes have zero in-degree and the rest have in-degree two, while for even, have zero in-degree and in-degree four.

As mentioned in Sect. 1, after a possible ``transient'', a cellular automaton evolving from any initial configuration must ultimately enter a loop, in which a sequence of configurations are visited repeatedly. Such a loop is represented by a cycle in the state transition graph. At every node in this cycle a tree is rooted; the transients consist of transitions leading towards the cycle at the root of the tree.

Lemma 3.3.

The trees rooted at all nodes on all cycles of the state transition graph for the cellular automaton defined in Sect. 3A are identical.

This result is proved by showing that trees rooted on all cycles are identical to the tree rooted on the null configuration. Let be a configuration which evolves to the null configuration after exactly time steps, so that . Let be a configuration on a cycle, and let be another configuration on the same cycle, such that . Then define

We first show that as ranges over all configurations in the tree rooted on the null configuration, ranges over all configurations in the tree rooted at . Since

it is clear that all configurations evolve after time steps [where the value of depends on ] to . To show that these configurations lie in the tree rooted at , one must show that their evolution reaches no other cycle configurations for any . Assume this supposition to be false, so that there exists some for which

Since , this would imply , or . But , and by construction for any , yielding a contradiction. Thus maps configurations at height in the tree rooted on the null configuration to configurations at height in the tree rooted at , and the mapping is one-to-one. An analogous argument shows that is onto. Finally one may show that preserves the time evolution structure of the trees, so that if , then

which follows immediately from the definition of . Hence is an isomorphism, so that trees rooted at all cycle configurations are isomorphic to that rooted at the null configuration.

Notice that this proof makes no reference to the specific form (3.2) chosen for in this section; Lemma 3.3 thus holds for any additive cellular automaton.

Theorem 3.3.

For odd, a tree consisting of a single arc is rooted at each node on each cycle in the state transition graph for the cellular automaton defined in Sect. 3A.

By virtue of Lemma 3.3, it suffices to show that the tree rooted on the null configuration consists of a single node corresponding to the configuration . This configuration has no predecessors by virtue of Lemma 3.1.

Corollary.

For odd, the fraction of the possible configurations which may occur in the evolution of the cellular automaton defined in Sect. 3A is after one or more time steps.

The ``distance'' between two nodes in a tree is defined as the number of arcs which are visited in traversing the tree from one node to the other (e.g. [6]). The ``height'' of a (rooted) tree is defined as the maximum number of arcs traversed in a descent from any leaf or terminal (node with zero in-degree) to the root of the tree (formally node with zero out-degree). A tree is ``balanced'' if all its leaves are at the same distance from its root. A tree is termed ``quaternary'' (``binary'') if each of its non-terminal nodes has in-degree four (two).

Let be the maximum which divides (so that for example ).

Theorem 3.4.

For even, a balanced tree with height is rooted at each node on each cycle in the state transition graph for the cellular automaton defined in Sect. 3A; the trees are quaternary, except that their roots have in-degree three.

Theorem 3.2 shows immediately that the tree is quaternary. In the proof of Theorem 3.1, we showed that a configuration can be reached from some configuration if and only if ; Theorem 3.2 then shows that if is reachable, it is reachable from exactly four distinct configurations . We now extend this result to show that a configuration can be reached from some configuration by evolution for time steps, with , if and only if . To see this, note that if

then

and so, since by Eq. (A.7), for , it follows that

for . On the other hand, if , say , then , which shows that is reachable in steps.

The balance of the trees is demonstrated by showing that for , if , then can be reached from exactly initial configurations . This may be proved by induction on . If

then all of the four states from which may be reached in one step satisfy . Consider now the configurations which satisfy

If we write , then as in Theorem 3.2, the four predecessors of are exactly

where . ranges over the four polynomials of degree less than two, as in Theorem 3.2. Exactly one of these polynomials satisfies Eq. (3.9), whereas the other three satisfy only

Any state satisfying Eq. (3.9) thus belongs to a cycle, since it can be reached after an arbitrary number of steps. Conversely, since any cycle configuration must be reachable after time steps, any and all configurations satisfying Eq. (3.9) are indeed on cycles. But, as shown above, the three which do not satisfy Eq. (3.9) are roots of balanced quaternary trees of height . The proof of the theorem is thus completed.

Corollary.

For even, a fraction of the possible configurations appear after steps in the evolution of the cellular automaton defined in Sect. 3A for . A fraction of the configurations occur in cycles, and are therefore generated at arbitrarily large times.

Corollary.

All configurations on cycles in the cellular automaton of Sect. 3A are divisible by .

This result follows immediately from the proof of Theorems 3.3 and 3.4.

Entropy may be used to characterize the irreversibility of cellular automaton evolution (cf. [1]). One may define a set (or topological) entropy for an ensemble of configurations occurring with probabilities according to

where for , and 0 otherwise. One may also define a measure entropy

For a maximal entropy ensemble in which all possible cellular automaton configurations occur with equal probabilities,

These entropies decrease in irreversible cellular automaton evolution, as the probabilities for different configurations become unequal. However, the balance property of the state transition trees implies that configurations either do not appear, or occur with equal nonzero probabilities. Thus the set and measure entropies remain equal in the evolution of the cellular automaton of Sect. 3A. Starting from a maximal entropy ensemble, both nevertheless decrease with time according to

D. Maximal Cycle Lengths

Lemma 3.4.

The lengths of all cycles in a cellular automaton of size as defined in Sect. 3A divide the length of the cycle obtained with an initial configuration containing a single site with value one.

This follows from additivity, since any configuration can be considered as a superposition of configurations with single nonzero initial sites.

Lemma 3.5.

For the cellular automaton defined in Sect. 3A, with of the form , .

In this case, any initial configuration evolves ultimately to a fixed point consisting of the null configuration, since

Lemma 3.6.

For the cellular automaton defined in Sect. 3A, with even but not of the form , .

A configuration appears in a cycle of length if and only if

and therefore

After time steps, the configuration obtained by evolution from an initial state containing a single nonzero site is ; by Theorems 3.3 and 3.4 and the additive superposition principle, the configuration

is therefore on the maximal length cycle. Thus the maximal period is given by the minimum for which

and so

with , odd. Similarly,

Squaring this yields

from which it follows that

Since divides , so does its square root, , and therefore

Combining Eqs. (3.15) and (3.16) implies that either or . To exclude the latter possibility, we use derivatives. Using Eq. (A.6), and the fact that the derivative of vanishes over , one obtains from (3.13),

If were odd, the right member would be non-trivial, and the divisibility condition could not hold. Thus must be even. But then the right member of (3.13) is a perfect square, so that

Thus , and the proof is complete.

Theorem 3.5.

For the cellular automaton defined in Sect. 3A, with odd, where is the multiplicative ``suborder'' function of 2 modulo , defined as the least integer such that . (Properties of the suborder functions are discussed in Appendix B.)

By Lemma 3.1, an initial configuration containing a single nonzero site cannot be reached in cellular automaton evolution. The configuration obtained from this after one time step can be reached, and in fact appears again after time steps, since

The maximal cycle lengths for the cellular automaton considered in this section are given in the first column of Table 1. The values are plotted as a function of in Fig. 4. Table 1 together with Table 4 show that for almost all odd . The first exception appears for , where ; subsequent exceptions are , , , , , and so on.

[ Figure 4 ] The maximal length of cycles generated in the evolution of a cellular automaton with size and , as a function of . Only values for integer are plotted. The irregular behaviour of as a function of is a consequence of the dependence of on number theoretical properties of .

As discussed in Appendix B, . This bound can be attained only when is prime. It implies that the maximal period is . Notice that this period is the maximum that could be attained with any reflection symmetric initial configuration (such as the single nonzero site configuration to be considered by virtue of Lemma 3.4).

E. Cycle Length Distribution

Lemma 3.4 established that all cycle lengths must divide and Theorems 3.3 and 3.4 gave the total number of states in cycles. This section considers the number of distinct cycles and their lengths.

[ Table 1 ] Maximal cycle lengths for one-dimensional nearest-neighbour additive cellular automata with size and possible values at each site. Results for all possible nontrivial symmetrical rules with are given. For , the fixed time evolution polynomials are and (corresponding to rules 90 and 150 of [1], respectively). For , the polynomials are , , and , while for , they are , , , and .

Lemma 3.7.

For the cellular automaton defined in Sect. 3A, with a multiple of 3, there are four distinct fixed points (cycles of length one); otherwise, only the null configuration is a fixed point.

For , the only stationary configurations are (null configuration), and

Table 2 gives the lengths and multiplicities of cycles in the cellular automaton defined in Sect. 3A, for various values of . One result suggested by the table is that the multiplicity of cycles for a particular increases with the length of the cycle, so that for large , an overwhelming fraction of all configurations in cycles are on cycles with the maximal length.

[ Table 2 ] Multiplicities and lengths of cycles in the cellular automaton of Sect. 3A with size . The notation indicates the occurrence of distinct cycles each of length . The last column of the table gives the total number of distinct cycles or ``attractors'' in the system.

When is prime, the only possible cycle lengths are and 1. Then, using Lemma 3.7, the number of cycles of length is for , and is otherwise.

When is not prime, cycles may exist with lengths corresponding to various divisors of . It has not been possible to express the lengths and multiplicities of cycles in this case in terms of simple functions. We nevertheless give a computationally efficient algorithm for determining them.

Theorems 3.3 and 3.4 show that any configuration on a cycle may be written in the form

where is some polynomial. The cycle on which occurs then has a length given by the minimum for which

where with odd, and . Using the factorization [given in Eq. (A.8)]

where the are the irreducible cyclotomic polynomials over of degree , Eq. (3.17) can be rewritten as

for all , , and for all such that . Let denote the smallest for which (3.19) holds with given , . Then the length of the cycle on which occurs is exactly the least common multiple of all the . If , then clearly Eq. (3.19) holds for , and . If (and ), then Eq. (3.19) is equivalent to

The values of for configurations with are therefore equal, and will be denoted (). Since (), the value of divides the minimum for which . This equation is the same as the one for the maximal cycle length of a size cellular automaton: the derivation of Theorem 3.5 then shows that

It can also be shown that or .

As an example of the procedure described above, consider the case . Here,

where

Then

Thus the cycles which occur in the case have lengths 1, 2, 3, 6, 15, and 30.

To determine the number of distinct cycles of a given length, one must find the number of polynomials with each possible set of values . This number is given by

where and

for . The cycle lengths of these polynomials are determined as above by the least common multiple of the .

In the example discussed above, one finds that configurations on cycles of length 3 have or , implying that 60 such configurations exist, in 20 distinct cycles.

previous  l  next