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 […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Categories

%d bloggers like this: