General associative [cellular automaton] rules

With a cellular automaton rule in which the new color of a cell is given by f[a₁, a₂] (compare page 886) it turns out that the pattern generated by evolution from a single non-white cell is always nested if the function f has the property of being associative or Flat. In fact, for a system involving k colors the pattern produced will always be essentially just one of the patterns obtained from an additive rule with k or less colors. In general, the pattern produced by evolution for t steps is given by

NestList[Inner[f, Prepend[#, 0], Append[#, 0], List] &, {a}, t]

so that the first few steps yield

{a},
{f[0, a], f[a, 0]},
{f[0, f[0, a]], f[f[0, a], f[a, 0]], f[f[a, 0], 0]},
{f[0, f[0, f[0, a]]], f[f[0, f[0, a]], f[f[0, a], f[a, 0]]], f[f[f[0, a], f[a, 0]], f[f[a, 0], 0]], f[f[f[a, 0], 0], 0]}

If f is Flat, however, then the last two lines here become

{f[0, 0, a], f[0, a, a, 0], f[a, 0, 0]},
{f[0, 0, 0, a], f[0, 0, a, 0, a, a, 0], f[0, a, a, 0, a, 0, 0], f[a, 0, 0, 0]}

and in general the number of a's that appear in a particular element is given as in Pascal's triangle by a binomial coefficient. If f is commutative (Orderless) then all that can ever matter to the value of an element is its number of a's. Yet since there are a finite set of possible values for each element it immediately follows that the resulting pattern must be essentially Pascal's triangle modulo some integer. And even if f is not commutative, the same result will hold so long as f[0, a]  a and f[a, 0]  a—since then any element can be reduced to f[a, a, a, …]. The result can also be generalized to cellular automata with basic rules involving more than two elements—since if f is Flat, f[a₁, a₂, a₃] is always just f[f[a₁, a₂], a₃].

If one starts from more than a single non-0 element, then it is still true that a nested pattern will be produced if f is both associative and commutative. And from the discussion on page 952 this means that any rule that shows generalized additivity must always yield a nested pattern. But if f is not commutative, then even if it is associative, non-nested patterns can be produced. And indeed page 887 shows an example of this based on the non-commutative group S₃. (In general f can correspond to an almost arbitrary semigroup, but with a single initial element only a cyclic subgroup of it is ever explored.)