Pre-expansivity in cellular automata

Abstract

We introduce the notion of pre expansivity for cellular automata (CA): it is the property of being positively expansive on asymptotic pairs of configurations (i.e. configurations that differ in only finitely many positions). Pre-expansivity therefore lies between positive expansivity and pre-injectivity, two important notions of CA theory. We show that there exist one-dimensional pre-expansive CAs which are not positively expansive and they can be chosen reversible (while positive expansivity is impossible for reversible CAs). We provide both linear and non-linear examples. In the one-dimensional setting, we also show that pre-expansivity implies sensitivity to initial conditions in any direction. We show however that no two-dimensional Abelian CA can be pre-expansive. We also consider the finer notion of k-expansivity (positive expansivity over pairs of configurations with exactly k differences) and show examples of linear CA in dimension 2 and on the free group that are k-expansive depending on the value of k, whereas no (positively) expansive CA exists in this setting.