The essential result

Somewhat special arguments finally establish the relationship between zero variance and zero ancestors for automata, namely that the number of ancestors is either uniform for all configurations, or else that there are some configurations with no ancestors at all. As special cases, if the distribution of ancestors for a single cell is not balanced, there must be a Garden of Eden (but not conversely); and a reversible rule will lack a Garden of Eden (but not conversely).

Mathematically, evolution is called surjective if every configuration has an ancestor, injective if it has only one. The essential result states that surjectivity requires uniform numbers of ancestors, at first sight incompatible with injectivity and so with reversibility as well. Reversibility can only be reconciled with uniformity if there is an edge effect; that is if multiple ancestors differ only in a remote boundary layer. The simplest layer would reflect the overhang due to the greater size of neighborhoods relative to cells. Of course another source of injectivity would be to eliminate all but one of the alternatives, by requiring periodicity, or quiescence at infinity, for example.

Zero variance is equivalent to the maximum eigenvalue of N assuming its minimum value, . This in turn implies that the maximum eigenvalue of the matrices is 1, but not conversely. There are consequences in turn for the properties of the subset matrix and the pair matrix, which is the same as the second moment matrix.

---

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx