[Algebraic computation of] additive cellular automata As discussed on page 951 a step in the evolution of an additive cellular automaton can be thought of as multiplication by a polynomial modulo k . After t steps, therefore, the configuration of such a system is given by PolynomialMod[poly t , k] .

The same is true for higher-dimensional generalizations such as so-called Anosov maps {x, y}  Mod[m . … The continued fraction map x  Mod[1/x, 1] discussed on page 914 becomes repetitive whenever its initial condition is a solution to a quadratic equation. For a map x  f[x] where f[x] is a polynomial such as a x (1 - x) the real initial conditions that yield period p are given by Select[x /.

The positions of the black cells are given by (and this establishes the connection with the picture on page 117 ) Fold[Flatten[{#1 - #2, #1 + #2}] &, {0}, 2^DigitPositions[t]] DigitPositions[n_] := Flatten[Position[Reverse[IntegerDigits[n, 2]], 1]] - 1 The actual pattern generated by rule 90 corresponds to the coefficients in PolynomialMod[Expand[(1/x + x) t ], 2] (see page 1091 ); the color of a particular cell is thus given by Mod[Binomial[t, (n + t)/2], 2] /; EvenQ[n + t] . Mod[Binomial[t, n], 2] yields a distorted pattern that is the one produced by rule 60 (see page 58 ).

This can be determined either from Mod[a, 2] or equivalently from (1 - (-1) a )/2 or Sin[ π /2 a] 2 . The succession of polynomials above can be obtained by expanding the generating functions 1/(1 - (1 + x) y) and 1/(1 - (1 + x + x 2 ) y) . … GegenbauerC is a so-called orthogonal polynomial—a higher mathematical function.

One starts by converting the list of cell colors at each step to a polynomial FromDigits[list, x] . Then for the case of rule 60 with n cells and cyclic boundary conditions, the state obtained after t steps is given by PolynomialMod[(1 + x) t z, {x n - 1, 2}] where z is the polynomial representing the initial state, and z = 1 for a single black cell in the first position.

One can reduce such an exponential equation to a pure polynomial equation by encoding powers using integer equations. The simplest known way of doing this (see note below ) involves a degree 8 equation with 60 variables: a  b c ↔ α [d, 4 + b e, 1 + z] ∧ α [f, e, 1 + z] ∧ a  Quotient[d, f] ∧ α [g, 4 + b, 1 + z] ∧ e  16 g(1 + z) λ [a_, b_, c_] := Module[{x}, 2 a + x 1  c ∧ (Mod[b - a, c]  0 ∨ Mod[b + a, c]  0)] α [a_, b_, c_] := Module[{x}, x 1 2 - b x 1 x 2 + x 2 2  1 ∧ x 3 2 - b x 3 x 4 + x 4 2  1 ∧ 1 + x 4 + x 5  x 3 ∧ Mod[x 3 , x 1 2 ]  0 ∧ 2x 4 + x 7  b x 3 ∧ Mod[-b + x 8 , x 7 ]  0 ∧ Mod[-2 + x 8 , x 1 ]  0 ∧ x 8 - x 11  3 ∧ x 12 2 - x 8 x 12 x 13 + x 13 2  1 ∧ 1 + 2 a + x 14  x 1 ∧ λ [a, x 12 , x 7 ] ∧ λ [c, x 12 , x 1 ]] (This roughly uses the idea that solutions to Pell equations grow exponentially, so that for example x 2  2y 2 + 1 has solutions With[{u = 3 + 2 √ 2 }, (u n + u -n )/2] .) … It also means that given any specific enumeration of polynomials, there must be some universal polynomial u which if fed the enumeration number of a polynomial p , together with an encoding of the values of its variables, will yield the corresponding value of p as a solution to u  0 .

[Intractability in] systems of limited size In the system x  Mod[x + m, n] from page 255 the repetition period n/GCD[m, n] can be computed using Euclid's algorithm in at most about Log[GoldenRatio, n] steps. In the system x  Mod[2x, n] from page 257 , the repetition period MultiplicativeOrder[2, n] probably cannot always be computed in any polynomial of Log[n] steps, since otherwise FactorInteger[n] could also be computed in about this number of steps.

The reason for this is that n[i + 2]  Mod[65539 2 n[i], 2 31 ]  Mod[6 n[i + 1] - 9 n[i], 2 31 ] so that in computing n[i + 2] from n[i + 1] and n[i] only small coefficients are involved. … Starting from a single 1, the state after t steps is then given by PolynomialMod[x t , {1 + x + x n , 2}] This result illustrates the analogy with linear congruential generators. … For a register of size n the maximal period of 2 n -1 is obtained whenever x n + Apply[Plus, x taps - 1 ] is one of the EulerPhi[2 n - 1]/n primitive polynomials that appear in Factor[Cyclotomic[2 n - 1, x], Modulus  2] .

With odd n the same turns out to be true for sequences Exp[2 π  Mod[Range[n] 2 , n]/n] —a fact used in the design of acoustic diffusers (see page 1183 ). For sequences involving only two distinct integers flat spectra are rare; with ± 1 those equivalent to {1, 1, 1, -1} seem to be the only examples. ( {r 2 , r s, s 2 , -r s} works for any r and s , as do all lists obtained working modulo x n - 1 from p[x]/p[1/x] where p[x] is any invertible polynomial.) … If Mod[p, 4]  1 JacobiSymbol sequences also satisfy Fourier[list]  list .

For additive cellular automata, states and rules can be represented as polynomials (see page 951 ), with h[a_, b_] := PolynomialMod[a b, k] and for example r = (1 + x) for elementary rule 60. … In both cases it then turns out that h can be obtained from (see note above ) h[a_, b_] := FromDigits[g[ListConvolve[ IntegerDigits[a, k], IntegerDigits[b, k], {1, -1}, 0]], k] where for multiplication rules g = Identity and for additive cellular automata g = Mod[#, k] & . For multiplication rules, there are normally carries (handled by FromDigits ), but for power cellular automata, these have only limited range, so that g = Mod[#, k α ] & can be used.