On Thursday 29 August 2019 I gave a Theory Lunch talk about expansivity. I focused on positive expansivity and discussed a general statement which has a most remarkable consequence for cellular automata theory.

**Definition.** Let be a metric space and let be a semigroup. A continuous action of on is* expansive* (with respect to ) if an *expansivity constant* exists such that the following happens: For every such that there exists such that .

If is either or , then the action is entirely determined by the function . In the second case, we say that is *positively expansive*, where “positively” means “in the positive direction of time”.

**Theorem.** *No reversible cellular automaton on an infinite group is positively expansive.*

Note that we are not making any assumptions on the alphabet of the CA, except the standard one that it is finite and has two or more elements. Theorem 1 follows from a surprising result due to W.R. Utz.

**Lemma 1.** *Let be a *compact* metric space. Suppose there exists a function which is continuous, *injective*, and positively expansive. Then is finite.*

Both compactness and injectivity play a crucial role in the proof, which we split into three parts following the argument from Coven and Keane, 2006. We first prove a statement which is of interest by itself.

**Lemma 2.** *In the hypotheses of Lemma 1, let be an expansivity constant for . There exists a positive integer such that, if for every from 1 to , then .*

*Proof.* By contradiction, assume that for every there exist two points such that for every from 1 to , but . As is compact, there exists a sequence such that and both exist. Then on the one hand, as for every , by continuity it must also be , so . But on the other hand, for all positive integers and such that it is , so again by continuity it must be for every : by positive expansivity, , against injectivity of .

Note the role of compactness and injectivity in the proof of Lemma 2.

**Lemma 3.** *In the hypotheses of Lemma 1, with given by Lemma 2, if for *infinitely many* it is for every from to , then for *every* .*

*Proof.* By repeatedly applying Lemma 2 starting from instead of , we get that, in the hypotheses of Lemma 1, however given an integer , if for from to , then for every . But the only way that it can be for every for infinitely many is that for every .

*Proof of Lemma 1.* Let be continuous and injective with expansivity constant $\varepsilon_0$ and let be as by Lemma 1. As is continuous, the sets:

are open and , so by compactness of $X$ there exist such that . We will show that cannot have more than elements. Otherwise, fix a subset of with elements. As is injective, for every the set also has elements. Therefore, for every there exist and such that and . By construction:

for every .

As there are only finitely many pairs , there must exist such that for infinitely many values of : for those ,

for every

By Lemma 3, for every : by expansivity, . But this is impossible, because by construction for suitable .

Note the role of compactness and injectivity in the proof of Lemma 3. Injective functions on non-compact spaces, or non-injective functions on compact spaces, can be positively expansive.

**Example 1.** Let and for every . Then any is an expansivity constant for .

**Example 2.** Let be the interval with its endpoints identified, with the distance , and for every . Then is an expansivity constant for .

To prove this, observe first that the distance on is precisely the distance induced by the Euclidean distance on . Given two different points and , if , then the representation of as a binary number starts with for some , and in addition for every . But the binary representation of starts with , so .

Bibliography:

- Ethan M. Coven and Michael Keane. Every compact metric space that supports a positively expansive homeomorphism is finite.
*Institute of Mathematical Statistics Lecture Notes – Monograph Series*, 48:304–305, 2006. - Expansive system. Scholarpedia entry. http://www.scholarpedia.org/article/Expansive_system

[…] Find the talk on my personal blog HERE […]

By:

Positive expansivity is impossible for reversible cellular automata | Theory Lunchon 2019/08/30at 5:12 pm