no. 14 · Friday 13 November 2026
Idempotence criteria for lazy cellular automata
Abstract
A lazy cellular automaton $τ:A^G\to A^G$ is determined by a finite neighborhood $S\subseteq G$ containing the group identity $e$, a pattern $p\in A^S$, and a writing symbol $a\in A\setminus\{p(e)\}$: its local rule is equal to the projection to $e$ except when it reads the pattern $p$, in which case it writes $a$. For a nonempty subset $T$ of the fiber $S_a:= p^{-1}(a)$, we introduce compatibility conditions on $p$ along the right translates $St$, $t\in T$. We show that, over every group, the existence of a compatible set is necessary for $τ$ to be non-idempotent, and that it is also sufficient whenever each element of $S_a$ normalizes the fiber $S_{p(e)}$. In particular, compatibility characterizes non-idempotence over abelian groups, which yields a test using $O(|S|^3)$ elementary operations, instead of an exhaustive search that is exponential in $|S|$. Finally, for every dihedral group $D_n$ with $n\geq 4$, we construct an idempotent lazy cellular automaton that admits a compatible set, showing that the normalization hypothesis cannot simply be dropped.
- comments
- 12 pages
- fields
- Group Theory