Algebraic invariants for crystallographic defects in cellular automata

Abstract

Let ${\mathcal{A}}^{{\mathbb{Z}}^D}$ be the Cantor space of ${\mathbb{Z}}^D$-indexed configurations in a finite alphabet ${\mathcal{A}}$, and let $\sigma$ be the ${\mathbb{Z}}^D$-action of shifts on ${\mathcal{A}}^{{\mathbb{Z}}^D}$. A cellular automaton is a continuous, $\sigma$-commuting self-map $\Phi$ of ${\mathcal{A}}^{{\mathbb{Z}}^D}$, and a $\Phi$-invariant subshift is a closed, $(\Phi,\sigma)$-invariant subset ${\mathfrak{A}}\subset{\mathcal{A}}^{{\mathbb{Z}}^D}$. Suppose that ${\mathbf{a}}\in{\mathcal{A}}^{{\mathbb{Z}}^D}$ is ${\mathfrak{A}}$-admissible everywhere except for some small region that we call a defect. It has been empirically observed that such defects persist under iteration of $\Phi$, and often propagate like ‘particles’ which coalesce or annihilate on contact. We construct algebraic invariants for these defects, which explain their persistence under $\Phi$, and partly explain the outcomes of their collisions. Some invariants are based on the cocycles of multidimensional subshifts; others arise from the higher-dimensional (co)homology/homotopy groups for subshifts, obtained by generalizing the Conway–Lagarias tiling groups and the Geller–Propp fundamental group.