Algebraic Properties of Cellular Automata (1984)

4. Generalizations

A. Enumeration of Additive Cellular Automata

We consider first one-dimensional additive cellular automata, whose configurations may be represented by univariate characteristic polynomials. We assume that the time evolution of each site depends only on its own value and the value of its two nearest neighbours, so that the time evolution dipolynomial is at most of degree two. Cyclic boundary conditions on sites are implemented by reducing the characteristic polynomial at each time step modulo as in Eq. (2.2). There are taken to be possible values for each site. With no further constraints imposed, there are possible , and thus distinct cellular automaton rules. If the coefficients of and in both vanish, then the characteristic polynomial is at most multiplied by an overall factor at each time step, and the behaviour of the cellular automaton is trivial. Requiring nonzero coefficients for and in reduces the number of possible rules to . If the cellular automaton evolution is assumed reflection symmetric, then , and only rules are possible. Further characterisation of possible rules depends on the nature of .

(a) k Prime. In this case, integer values at each site may be combined by addition and multiplication modulo to form a field (in which each nonzero element has a unique multiplicative inverse) . For a symmetrical rule, may always be written in the form

up to an overall multiplicative factor. For , the rule was considered above; the additional rule is also possible (and corresponds to rule 150 of [1]).

(b) k Composite.

Lemma 4.1.

For , with prime, the value of a site obtained by evolution of an additive cellular automaton from some initial configuration is given uniquely in terms of the values attained by that site in the evolution of the set of cellular automata obtained by reducing and all site values modulo .

This result follows from the Chinese remainder theorem for integers (e.g. [8], Chap. 8), which states that if and are relatively prime, then the values and determine a unique value of modulo such that for .

Lemma 4.1 shows that results for any composite may be obtained from those for a prime or a prime power.

When is composite, the ring of integers modulo no longer forms a field, so that not all commutative rings are fields. Nevertheless, for a prime power, there exists a Galois field of order , unique up to isomorphism (e.g. [9], Chap. 4). For example, the field may be taken to act on elements with multiplication taken modulo the irreducible polynomial . Time evolution for a cellular automaton with site values in this Galois field can be reduced to that given by , where is any element of the field. The behaviour of this subset of cellular automata with composite is directly analogous to those over for prime .

It has been assumed above that the value of a site at a particular time step is determined solely by the values of its nearest neighbours on the previous time step. One generalization allows dependence on sites out to a distance , so that the evolution of the cellular automaton corresponds to multiplication by a fixed dipolynomial of degree . Most of the theorems to be derived below hold for any .

B. Cellular Automata over ( Prime)

Lemma 4.2.

The lengths of all cycles in any additive cellular automaton over of size divide the length of the cycle obtained for an initial configuration containing a single site with value 1.

This lemma is a straightforward generalization of Lemma 3.4, and follows directly from the additivity assumed for the cellular automaton rules.

Lemma 4.3.

For a multiple of , for an additive cellular automaton over .

Remark. For a multiple of , but not a power of , it can be shown that for an additive cellular automaton over with . In addition, in this case.

Theorem 4.1.

For any not a multiple of , , and if is symmetric, for any additive cellular automaton over .

The period divides if

Taking

Eq. (A.3) yields

since and , and the first part of the theorem follows. Since , Eq. (4.2) holds for

if is symmetric, so that .

This result generalizes Theorem 3.5 for the particular cellular automaton considered in Sect. 3.

Table 1 gives the values of for all non-trivial additive symmetrical cellular automata over and . Just as in the example of Sect. 3 (given as the first column of Table 1), one finds that for many values of not divisible by

When , all exceptions to (4.3) when are also exceptions for [19]. We outline a proof for the simplest case, when is relatively prime to 6 (as well as 2). Let be the maximal period obtained with , equal to the minimum integer for which

We now show that is a multiple of the maximum period obtained with . Since the mapping is a homomorphism in the field of polynomials with coefficients in , one has

for any such that . Dividing by Eq. (4.4), and using the fact that is odd to take square roots, yields

for any such that . But since , Eq. (4.5) is the analogue of Eq. (4.4) for , and the result follows.

More exceptions to Eq. (4.3) are found with than with .

Lemma 4.4.

A configuration is reachable in the evolution of a size additive cellular automaton over , as described by if and only if is divisible by .

Appendix A.A gives conventions for the greatest common divisor .

If can be reached, then

for some , so that

But and , and hence if is reachable,

We now show by an explicit construction that all satisfying (4.6) in fact have predecessors . Using Eq. (A.10), one may write

for some dipolynomials and , so that

Then taking , the configuration given by the polynomial obtained by reducing the dipolynomial satisfies

and thus provides an explicit predecessor for .

Corollary.

is reachable in steps if and only if divides .

This is a straightforward extension of the above lemma.

Theorem 4.2.

The fraction of possible configurations which may be reached by evolution of an additive cellular automaton over of size is , where .

By Lemma 4.4, only configurations divisible by may be reached. The number of such configurations is , while the total number of possible configurations is .

Let be the maximum which divides and let denote the multiplicity of the irreducible factor of in , where is a polynomial with a nonzero constant term. We further define , so that .

Theorem 4.3.

The state transition diagram for an additive cellular automaton of size over consists of a set of cycles at all nodes of which are rooted identical -ary trees. A fraction of the possible configurations appear on cycles. For , the height of the trees is . The trees are balanced if and only if (a) for all , or (b) for all and , and .

To determine the in-degrees of nodes in the trees, consider a configuration with predecessors represented by the polynomials and , so that

Then since

and , it follows that

Since has a non-zero constant term, is an ordinary polynomial. The number of solutions to this congruence and thus the number of predecessors of is .

The proof of Lemma 3.3 demonstrates the identity of the trees. The properties of the trees are established by considering the tree rooted on the null configuration. A configuration evolves to the null configuration after steps if , so that

Hence all configurations on the tree are divisible by , where . All configurations in the tree evolve to the null configuration after at most steps, which is thus an upper bound on the height of the trees. But since the configuration evolves to the null configuration after exactly steps, this quantity gives the height of the trees. The tree of configurations which evolve to the null configuration (and hence all other trees in the state transition diagram) is balanced if and only if all unreachable (terminal) configurations evolve to the null configuration after the same number of steps. First suppose that neither condition (a) nor (b) is true. One possibility is that some irreducible factor of satisfies with but does not divide . The configuration reaches in steps whereas reaches in one step fewer, yet both are unreachable, so that the tree cannot be balanced. The only other possibility is that there exist two irreducible factors and of multiplicities and , respectively, with and dividing but . Then reaches in steps, whereas reaches in steps. Neither of these configurations is reachable, so again the trees cannot be balanced. This establishes that in all cases either condition (a) or (b) must hold. The sufficiency of condition (a) is evident. If the condition (b) is true, then

and . Equation (4.7) shows that any configuration which evolves to the null configuration after steps is of the form

where is some polynomial. The proof is completed by showing that all such configurations with are indeed reachable. To construct an explicit predecessor for , define the dipolynomial by , so that . Then there exist dipolynomials and such that

The configuration given by the dipolynomial

then provides a predecessor for .

Notice that whenever the balance condition fails, the set and measure entropies of Eqs. (3.11) and (3.12) obtained by evolution from an initial maximal entropy ensemble become unequal.

The results of Theorems 4.2 and 4.3 show that if , then the evolution of an additive cellular automaton is effectively reversible, since every configuration has a unique predecessor.

In general,

so that for the one-dimensional additive cellular automata considered so far, the maximum decrease in entropy starting from an initial equiprobable ensemble is .

Note that for a cellular automaton over () of length with , if and otherwise. Such cellular automata are thus effectively reversible for whenever is not a multiple of 4.

Remark. A configuration lies on a cycle in the state transition diagram of an additive cellular automaton if and only if .

This may be shown by the methods used in the proof of Theorem 4.3.

C. Cellular Automata over ( Composite)

Theorem 4.4.

For an additive cellular automaton over ,

where , and in all coefficients are reduced modulo .

This result follows immediately from Lemma 4.1.

Theorem 4.5.

is equal to either (a) or (b) for an additive cellular automaton.

First, it is clear that

To complete the proof, one must show that in addition

is the smallest positive integer for which a positive integer and dipolynomials and satisfying

exist, where all dipolynomial coefficients (including those in ) are taken as ordinary integers in , and irrelevant powers of on both sides of the equation have been dropped. Raising both sides of Eq. (4.8) to the power , one obtains

Reducing modulo yields the required result.

For and , it can be shown that case (a) of Theorem 4.5 always obtains if , but case (b) can occur when .

Theorem 4.6.

With (all relatively prime), the number of configurations which can be reached by evolution of an additive cellular automaton over is equal to the product of the numbers reached by evolution of cellular automata with the same over each of the . The state transition diagram for the cellular automaton over consists of a set of identical trees rooted on cycles. The in-degrees of non-terminal nodes in the trees are the product of those for each of the cases. The height of the trees is the maximum of the heights of trees for the cases, and the trees are balanced only if all these heights are equal.

These results again follow directly from Lemma 4.1.

Theorem 4.6 gives a characterisation of the state transition diagram for additive cellular automata over when is a product of distinct primes. No general results are available for the case of prime power . However, for example, with , one may obtain the fraction of reachable states by direct combinatorial methods. With one finds in this case that the fraction is for odd, for , and for . With () the systems are reversible (all configurations reachable) unless , in which case a fraction may be reached.

D. Multidimensional Cellular Automata

The cellular automata considered above consist of a sequence of sites on a line. One generalization takes the sites instead to be arranged on a square lattice in two dimensions. The evolution of a site may depend either on the values of its four orthogonal neighbours (type I neighbourhood) or on the values of all eight neighbours including those diagonally adjacent (type II neighbourhood) (e.g. [1]). Configurations of two-dimensional cellular automata may be represented by bivariate characteristic polynomials . Time evolution for additive cellular automaton rules is obtained by multiplication of these characteristic polynomials by a fixed bivariate dipolynomial . For a type I neighbourhood, contains no cross-terms; such terms may be present for a type II neighbourhood. Periodic boundary conditions with periods and may be implemented by reduction modulo and modulo at each time step. Cellular automata may be generalized to an arbitrary -dimensional cubic or hypercubic lattice. A type I neighbourhood in dimensions contains sites, while a type II neighbourhood contains sites. As before, we consider cellular automata with possible values for each site.

Theorem 4.7.

For an additive cellular automaton over on a -dimensional cubic lattice, with a type I or type II neighbourhood, and with periodicities , .

The result may be proved by showing that

for all (such that ). The right member of Eq. (4.9) is given by the smallest integer for which there exists a positive integer such that

for some dipolynomials . Taking with in Eq. (4.10), all terms in the sum vanish except for the one associated with , and the resulting value of corresponds to the left member of Eq. (4.9).

Theorem 4.8.

For an additive cellular automaton over on a -dimensional cubic lattice (type I or type II neighbourhood) with periodicities none of which are multiples of ,

If is symmetrical, so that

for all , then

The and are multidimensional generalizations of the multiplicative order and suborder functions, described in Appendix B.

This theorem is proved by straightforward extension of the one-dimensional Theorem 4.1.

Using the result (B.13), one finds for symmetrical rules

The maximal cycle length is thus bounded by

with the upper limits achieved only if all the are prime. (For example,

saturates the upper bound.)

Algebraic determination of the structure of state transition diagrams is more complicated for multi-dimensional cellular automata than for the one dimensional cellular automata considered above (2). The generalization of Lemma 4.4 states that a configuration is reachable only if vanishes whenever the are simultaneous roots of , . The root sets form an algebraic variety over (cf. [9]).

E. Higher Order Cellular Automata

The rules for cellular automaton evolution considered above took configurations to be determined solely from their immediate predecessors. One may in general consider higher order cellular automaton rules, which allow dependence on say preceding configurations. The time evolution for additive one-dimensional higher-order cellular automata (with sites and periodic boundary conditions) may be represented by the order recurrence relation

This may be solved in analogy with order difference equations to yield

where the are solutions to the equation

and the are analogous to ``constants of integration'' and are determined by the initial configurations . The state of an order cellular automaton depends on the values of its sites over a sequence of time steps; there are thus a total possible states. The transition diagram for these states can in principle be derived by algebraic methods starting from Eq. (4.11). In practice, however, the are usually not polynomials, but elements of a more general function field, leading to a somewhat involved analysis not performed here.

For first-order additive cellular automata, any configuration may be obtained by superposition of the configuration (or its translates ). For higher-order cellular automata, several ``basis'' configurations must be included. For example, when , , , and are all basis configurations, where in , , and represent configurations at successive time steps.

As discussed in Sect. 4B, some first-order cellular automata over () are effectively reversible for particular values of , so that all states are on cycles. The class of second-order cellular automata with is reversible for all and , and for any [10]. In the simple case , one finds , . It then appears that

(The proof is straightforward when .) In the case , the are no longer polynomials. For the case , the results for with between 3 and 30 are: 6, 6, 15, 12, 9, 12, 42, 30, 93, 24, 63, 18, 510, 24, 255, 84, 513, 60, 1170, 186, 6141, 48, 3075, 126, 3066, 36, 9831, 1020.

F. Other Boundary Conditions

The cellular automata discussed above were taken to consist of indistinguishable sites with periodic boundary conditions, as if arranged around a circle. This section considers briefly cellular automata with other boundary conditions. The discussion is restricted to the case of symmetric time evolution rules .

The periodic boundary conditions considered above are not the only possible choice which preserve the translation invariance of cellular automata (or the indistinguishability of their sites) (3). One-dimensional cellular automata may in general be viewed as bundles over . Periodic boundary conditions correspond to trivial bundles. Non-trivial bundles are associated with ``twisted'' boundary conditions. Explicit realizations of such boundary conditions require a twist to be introduced at a particular site. The evolution of particular configurations then depends on the position of the twist, but the structure of the state transition diagram does not.

A twist of value at position causes sites with to appear multiplied by in the time evolution of sites with , and correspondingly, for sites with to appear multiplied by in the evolution of sites with . In the presence of a twist taken at position , the time evolution formula (2.5) becomes

Multiple twists are irrelevant; only the product of their values is significant for the structure of the state transition diagram. If with prime, then (with the zero element removed) forms a multiplicative group, and twists with any value not equal to 0 or 1 yield equivalent results. When with composite, several equivalence classes of values may exist.

Using Eq. (4.12) one may obtain general results for twisted boundary conditions analogous to those derived above for the case of periodic boundary conditions (corresponding to ). When ( prime), one finds for example,

An alternative class of boundary conditions introduces fixed values at particular cellular automaton sites. One may consider cellular automata consisting of sites with values arranged as if along a line, bounded by sites with fixed values and . Maximal periods obtained with such boundary conditions will be denoted . The case is simplest. In this case, configurations

of the length system with fixed boundary conditions may be embedded in configurations

of a length system with periodic boundary conditions. The condition is preserved by time evolution, so that one must have

The periods are equal if the configurations obtained by evolution from a single nonzero initial site have the symmetry of Eq. (4.13). (The simplest cellular automaton defined in Sect. 3A satisfies this condition.)

Fixed boundary conditions , , may be treated by constructing configurations of the form (4.13), with periodic boundary conditions, but now with time evolution

where is taken of the form . Iteration generates a geometric series in , which may be summed to yield a rational function of . For , , one may then show that with , , while with (the case of Sect. 3A), .

previous l next