Posted by: Silvio Capobianco | 2019/08/30

## Positive Expansivity is Impossible for Reversible Cellular Automata

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 $(X,d)$ be a metric space and let $(S,\cdot)$ be a semigroup. A continuous action $\tau$ of $S$ on $X$ is expansive (with respect to $d$) if an expansivity constant $\varepsilon_0>0$ exists such that the following happens: For every $x, y \in X$ such that $x \neq y$ there exists $s \in S$ such that $d(\tau_s(x), \tau_s(y)) > \varepsilon_0$.

If $(S,\cdot)$ is either $(\mathbb{Z},+)$ or $(\mathbb{N},+)$, then the action $\tau$ is entirely determined by the function $F = \tau_1$. In the second case, we say that $F$ 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 $(X,d)$ be a compact metric space. Suppose there exists a function $F : X \to X$ which is continuous, injective, and positively expansive. Then $X$ 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 $\varepsilon_0$ be an expansivity constant for $F$. There exists a positive integer $n$ such that, if $d(F^t(x), F^t(y)) \leq \varepsilon_0$ for every $t$ from 1 to $n$, then $d(x,y) \leq \varepsilon_0$.

Proof. By contradiction, assume that for every $n \geq 1$ there exist two points $x_n, y_n \in X$ such that $d(F^t(x_n), F^t(x_n)) \leq \varepsilon_0$ for every $t$ from 1 to $n$, but $d(x_n, y_n) > \varepsilon_0$. As $X$ is compact, there exists a sequence $(n_k)$ such that $\lim_{k \to \infty} x_{n_k} = x$ and $\lim_{k \to \infty} y_{n_k} = y$ both exist. Then on the one hand, as $d(x_{n_k}, y_{n_k}) > \varepsilon_0$ for every $k \geq 1$, by continuity it must also be $d(x, y) \geq \varepsilon_0 > 0$, so $x \neq y$. But on the other hand, for all positive integers $t$ and $k$ such that $1 \leq t \leq n_k$ it is $d(F^t(x_{n_k}), F^t(y_{n_k})) \leq \varepsilon_0$, so again by continuity it must be $d(F^t(x), F^t(y)) \leq \varepsilon_0$ for every $t \geq 1$: by positive expansivity, $F(x) = F(y)$, against injectivity of $F$. $\Box$

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

Lemma 3. In the hypotheses of Lemma 1, with $n$ given by Lemma 2, if for infinitely many $k \geq 0$ it is $d(F^t(x), F^t(y)) \leq \varepsilon_0$ for every $t$ from $k+1$ to $k+n$, then $d(F^t(x), F^t(y) \leq \varepsilon_0$ for every $t \geq 0$.

Proof. By repeatedly applying Lemma 2 starting from $F^t(x)$ instead of $x$, we get that, in the hypotheses of Lemma 1, however given an integer $k \geq 0$, if $d(F^t(x), F^t(y)) \leq \varepsilon_0$ for $t$ from $k+1$ to $k+n$, then $d(F^t(x), F^t(y)) \leq \varepsilon_0$ for every $t \leq k+n$. But the only way that it can be $d(F^t(x), F^t(y)) \leq \varepsilon_0$ for every $1 \leq t \leq k$ for infinitely many $k$ is that $d(F^t(x), F^t(y) \leq \varepsilon_0$ for every $t \geq 0$. $\Box$

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

$U(z) = \left\{ x \in X \mid d(F^t(x), F^t(z)) \leq \varepsilon_0 \,, \; 1 \leq t \leq n \right\}$

are open and $\bigcup_{z \in X} U(z) = X$, so by compactness of $X$ there exist $z_1, \ldots, z_m \in X$ such that $\bigcup_{i=1}^m U(z_i) = X$. We will show that $X$ cannot have more than $m$ elements. Otherwise, fix a subset $Y$ of $X$ with $m+1$ elements. As $F$ is injective, for every $t \geq 0$ the set $F^t(Y)$ also has $m+1$ elements. Therefore, for every $k \geq 0$ there exist $1 \leq i \leq n$ and $y_i, y'_i \in Y$ such that $y_k \neq y'_k$ and $F^k(y_k), F^k(y'_k) \in U(z_i)$. By construction:

$d(F^{k+t}(y_k), F^{k+t}(y'_k)) \leq \varepsilon_0$ for every $1 \leq t \leq n$.

As there are only finitely many pairs $(y_k, y'_k)$, there must exist $y, y' \in Y$ such that $(y_k, y'_k) = (y, y')$ for infinitely many values of $k$: for those $k$,

$d(F^{k+t}(y), F^{k+t}(y')) \leq \varepsilon_0$ for every $1 \leq t \leq n$

By Lemma 3, $d(F^t(y), F^t(y')) \leq \varepsilon_0$ for every $t \geq 0$: by expansivity, $y = y'$. But this is impossible, because by construction $y = y_k \neq y'_k = y'$ for suitable $k$. $\Box$

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 $X = \mathbb{R}$ and $F(x) = 2x$ for every $x \in \mathbb{R}$. Then any $\varepsilon_0 > 0$ is an expansivity constant for $F$. $\Diamond$

Example 2. Let $X$ be the interval $[0,1]$ with its endpoints identified, with the distance $d(x,y) = \min(x-y \pmod{1}, y-x \pmod{1})$, and $F(x) = 2x \pmod{1}$ for every $x \in X$. Then $\varepsilon_0 = 1/8$ is an expansivity constant for $F$.

To prove this, observe first that the distance $d$ on $X$ is precisely the distance induced by the Euclidean distance on $\mathbb{R}$. Given two different points $x$ and $y$, if $\delta = d(x, y) \leq 1/8$, then the representation of $\delta$ as a binary number starts with $.0^{m}1$ for some $m \geq 2$, and in addition $d(F^t(x), F^t(y)) = 2^t \delta$ for every $t \leq m-1$. But the binary representation of $2^t \delta$ starts with $.0^{m-t}1$, so $d(F^{m-1}(x), F^{m-1}(y) \geq 1/4 > 1/8$. $\Diamond$

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

## Responses

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