A divide and conquer algorithm for deciding group cellular automata dynamics

We prove that many dynamical properties of group cellular automata (GCA) can be decided by decomposing them into a set of much simpler GCA, provided those properties are decidable for such simpler GCA. Specifically, we provide a novel algorithmic technique that decomposes the GCA under investigation into a finite number of GCA, some defined on abelian groups, while others, if any, on products of simple non-abelian isomorphic groups. Importantly, the groups resulting from the decomposition depend only on the original group and are therefore completely independent of both the automaton and the considered property. Consequently, they do not inherit any aspect of the complexity of the automaton under investigation. We study the inheritance of the dynamical properties in the original GCA versus the same properties in the GCA obtained through decomposition. The latter turn out to be significantly easier to analyze than in the original GCA. Then, we show that injectivity, surjectivity, and equicontinuity/sensitivity to initial conditions can be decided by testing them in the smaller GCA produced by the decomposition. Moreover, we prove that the topological entropy of a GCA can be computed, provided one knows how to compute it for GCA defined on products of simple non-abelian isomorphic groups – for which we explicitly prove how to compute it in the surjective case – and on abelian groups. Finally, we prove that no strongly transitive, and therefore no positively expansive, GCA defined on non-abelian groups exist.