# Strict Asymptotic Nilpotency in Cellular Automata

Ville Salo

► To cite this version:

Ville Salo. Strict Asymptotic Nilpotency in Cellular Automata. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. pp.3-15, 10.1007/978-3-319-58631-1_1 . hal-01656359

HAL Id: hal-01656359

https://inria.hal.science/hal-01656359

Submitted on 5 Dec 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Strict asymptotic nilpotency in cellular automata

Ville Salo
vosalo@utu.fi

University of Turku

**Abstract.** We discuss the problem of which subshifts support strictly asymptotically nilpotent CA, that is, asymptotically nilpotent CA which are not nilpotent. The author talked about this problem in AUTOMATA and JAC 2012, and this paper discusses the (lack of) progress since. While the problem was already solved in 2012 on a large class of multi-dimensional SFTs, the full solutions are not known for one-dimensional sofics, multidimensional SFTs, and full shifts on general groups. We believe all of these questions are interesting in their own way, and discuss them in some detail, along with some context.

## 1 Introduction

A cellular automaton is nilpotent if every configuration is eventually mapped to the all-zero configuration. This notion is best known as an undecidable property of one-dimensional CA, see [1, 6]. Here, we discuss its dynamical aspects. We study the relation of nilpotency and its asymptotic version in the setting of cellular automata on subshifts. Our main point is to state the following questions.

*Question 1.* Which one-dimensional sofic shifts support cellular automata which are asymptotically nilpotent but not nilpotent?

*Question 2.* Which multidimensional SFTs support cellular automata that are asymptotically nilpotent but not nilpotent? Do any?

*Question 3.* Which full shifts on countable groups support cellular automata that are asymptotically nilpotent but not nilpotent? Do any?

Below, these are Question 4, Question 6 and Question 9, respectively. They are discussed in their natural contexts, and we try to include some informal guesses about what the solutions might look like. We also ask other questions, and share some lemmas and examples.

## 2 Nilpotency on multidimensional full shifts

We begin with an introduction of the problem and its full solution in the classical multidimensional full shift setting.
Let $\Sigma \ni 0$ be a finite alphabet.<fnref n="1" /> The $d$-dimensional full shift is the dynamical system $\Sigma^{\mathbb{Z}^d}$ where $\mathbb{Z}^d$ acts by translations $\sigma_v(x)_u = x_{u+v}$. A cellular automaton is a continuous shift-commuting function $f: \Sigma^{\mathbb{Z}^d} \to \Sigma^{\mathbb{Z}^d}$. Cellular automata can be characterized concretely as follows: if $f$ is a cellular automaton, then there is a local rule $f_{\text{loc}}: \Sigma^F \to \Sigma$ where $F \subset \mathbb{Z}^d$ is a finite neighborhood such that $f(x)_v = f_{\text{loc}}(\sigma_v(x)|_F)$ for all $x \in \Sigma^{\mathbb{Z}^d}$ and $v \in \mathbb{Z}^d$.

A cellular automaton is *nilpotent* if it is a root of the trivial (constant-zero) cellular automaton, that is, there exists $n \in \mathbb{N}$ such that $f^n(x) = 0^{\mathbb{Z}}$ for all $x \in \Sigma^{\mathbb{Z}}$.

The second kind of nilpotency we are interested in is *asymptotic nilpotency*. A cellular automaton is asymptotically nilpotent if every configuration converges to the same point in the limit. More precisely,

$$ \forall x \in \Sigma^{\mathbb{Z}^d} : \forall v \in \mathbb{Z}^d : \exists n_0 \in \mathbb{N} : \forall n \ge n_0 : f^n(x)_v = 0. $$

Clearly a nilpotent cellular automaton is asymptotically nilpotent. If a cellular automaton is asymptotically nilpotent but not nilpotent, then it is *strictly asymptotically nilpotent* or *SAN*. This cannot happen on a $d$-dimensional full shift:

**Theorem 1.** A cellular automaton $f: \Sigma^{\mathbb{Z}^d} \to \Sigma^{\mathbb{Z}^d}$ is asymptotically nilpotent if and only if it is *nilpotent*.

This is proved for $d = 1$ in [5], and for general $d$ in [12]. One might think the proof is direct compactness argument, but in fact the first relies on the geometry of $\mathbb{Z}$ and the second on algebraic properties of $\mathbb{Z}^d$. We discuss the ideas behind these proofs in Section 6.

## 3 Nilpotency from a subset of configurations

In this section, we show examples of how taking our initial configurations from a noncompact set can lead to SAN-like phenomena. These will be used as the basis of constructions in compact settings.

Let $f: \Sigma^{\mathbb{Z}^d} \to \Sigma^{\mathbb{Z}^d}$ be a cellular automaton. Let $X \subset \Sigma^{\mathbb{Z}}$ be a subset of $\Sigma^{\mathbb{Z}}$. We say $f$ is *weakly nilpotent on X* if and only if

$$ \forall x \in X : \exists n : f^n(x) = 0, $$

nilpotent on $X$ if and only if $f^n(X) = \{0^{\mathbb{Z}^d}\}$ for some $n \in \mathbb{N}$, and *asymptotically nilpotent on X* if $f^n(x) \to 0^{\mathbb{Z}^d}$ for all $x \in X$.

If $X = \Sigma^{\mathbb{Z}^d}$, then clearly $f$ is nilpotent (in the sense of the previous section) if and only if it is nilpotent on $X$ (in the sense of this section). It is also known that $f$ is weakly nilpotent on $\Sigma^{\mathbb{Z}^d}$ if and only if it is nilpotent on $\Sigma^{\mathbb{Z}^d}$.

We note two trivial examples that are useful to keep in mind:

<footnote n="1">¹ Nilpotency discussions are at their clearest when subshifts are *pointed*, that is, they have a special point $0^{\mathbb{Z}^d}$ as part of their structure, and all nilpotency is toward this special point.</footnote>
In this section, we concentrate on the case when $X$ is a subshift and is also closed under $f$, so that $f: X \to X$ is the restriction of a cellular automaton on $\Sigma^{\mathbb{Z}^d}$; this is the setting of cellular automata on multidimensional subshifts, and such $f$ are precisely the continuous shift-commuting functions on $X$.

## 4.1 SFTs

First, consider the case $d=1$. Let $X \subset \Sigma^{\mathbb{Z}}$ be a subshift of finite type or SFT, that is, a closed shift-invariant subset of $\Sigma^{\mathbb{Z}}$ obtained by forbidding a finite set of words. Such $X$ is conjugate$^2$ to the set of paths in a finite graph [8]. It is shown in [5, 12] that in this setting there are no SAN cellular automata.

**Theorem 3 (Corollary 1 in [12]).** Let $X \subset \Sigma^{\mathbb{Z}}$ be an SFT. Then a cellular automaton $f$ on $X$ is nilpotent if and only if it is asymptotically nilpotent.

One can try to generalize this to SFTs in higher dimensions. SFTs of $\Sigma^{\mathbb{Z}^d}$ are defined like in one dimension, by forbidding finitely many patterns from occurring (and such systems are conjugate to tiling systems induced by finitely many tiles).

**Theorem 4 (Theorem 4 in [12]).** Let $X \subset \Sigma^{\mathbb{Z}^d}$ be an SFT where finite points are dense. Then a cellular automaton $f$ on $X$ is nilpotent if and only if it is asymptotically nilpotent.

The denseness of finite points is not a property that is often assumed from multidimensional SFTs. A more commonly used gluing property is so-called strong irreducibility. Many other gluing properties have been defined, and some are listed for example in [2].

**Definition 1.** Let $X \subset \Sigma^{\mathbb{Z}^d}$ be a subshift. We say $X$ is strongly irreducible if there exists $m \in \mathbb{N}$ such that for any $y, z \in X$ and any finite sets $N, N' \subset \mathbb{Z}^d$ with $\min\{|v-v'| \mid v \in N, v' \in N'\} \ge m$, there exists a point $x \in X$ with $x_N = y_N$ and $x_{N'} = z_{N'}$.

By compactness, the sets $N$ and $N'$ can then be taken infinite as well, and we easily obtain the following lemma.

**Lemma 1.** Let $X \subset \Sigma^{\mathbb{Z}^d}$ be a strongly irreducible SFT and let $x \in X$. Then the points asymptotic to $x$ are dense in $X$.

Since a subshift has to have the point $0^{\mathbb{Z}^d}$ in order to support asymptotically nilpotent cellular automata, we see that in our case of interest, strong irreducibility is a stronger requirement than the density of 0-finite points:

**Corollary 1.** Let $X \subset \Sigma^{\mathbb{Z}^d}$ be a strongly irreducible SFT. Then a cellular automaton $f$ on $X$ is nilpotent if and only if it is asymptotically nilpotent.

<footnote>$^2$ Equal up to shift-commuting homeomorphism.</footnote>
I do not know if any such property is required.

*Question 4.* Is there an SFT $X \subset \Sigma^{\mathbb{Z}^d}$ for some $d \ge 2$ and a CA $f: X \to X$ such that $f$ is asymptotically nilpotent but not nilpotent?

If the answer is yes, then the solution would presumably involve constructing an SFT where every configurations sets up some zones where we eventually have only zeroes, in some controlled way. There are many known constructions that might allow this [3, 15], but since the SFT must be closed under $f$, this seems difficult.

It is known that the shift is not SAN on any $\mathbb{Z}^2$-SFT [10, 13]. In [13], this is shown using topological arguments: by passing to a minimal subsystem (in a technical sense) we can always find certain abstract ‘spaceships’, which prevent nilpotency. The proof is very specific to $d = 2$, and does not seem to extend to $d = 3$.

In fact, a cellular automaton on an SFT can be seen as a shift on a higher-dimensional SFT by looking at its spacetime diagrams, and thus a positive answer to Question 4 would imply a positive answer to the following (where by the previous paragraph we can just as well restrict to $d \ge 3$):

*Question 5.* Is there an SFT $X \subset \Sigma^{\mathbb{Z}^d}$ for some $d \ge 3$ such that $X$ contains at least two points, and $\sigma_v$ is asymptotically nilpotent for some $v \in \mathbb{Z}^d$?

A shift map is nilpotent on an SFT $X$ (as a cellular automaton) if and only if $X = \{0^{\mathbb{Z}^d}\}$, so we may replace the assumption that $\sigma_v$ is not nilpotent by the assumption that $X$ has at least two points. The direction $v$ of the shift does not matter, since SFTs are closed under rotating the lattice by elements of $GL(n, \mathbb{Z})$.

## 4.2 Sofics (and beyond)

The proof of Theorem 4 in [12] in fact does not require that $X$ is an SFT, but only the property that taking the union of the supports of two configurations of $X$ gives a point in $X$ assuming the supports have large enough distance. This is called *zero-gluing* in [13], where nilpotency is studied in the nondeterministic setting.

SFTs are always zero-gluing, but *sofic shifts*, which are images of SFTs under cellular automata (which clearly generalizes SFTs), are not. Let us show how the trivial idea of shifting finite points from the last section leads to an equally trivial example of a sofic shift where we can have SAN maps. We remark that sofic shifts on $\mathbb{Z}$ are precisely the subshifts whose language is regular, and precisely the subshifts that are defined by a regular language of forbidden words.

*Example 3 (One-one).* Let $\Sigma = \{0, 1\}$ and let $X \subset \Sigma^{\mathbb{Z}}$ be defined by the forbidden patterns $10^*1$. This is the *one-one* subshift. Then $X$ is a countable sofic shift. Then $\sigma$ is asymptotically nilpotent but not nilpotent on $X$: on the configuration $x^i$ where $x_j^i = 1 \iff i = j$, the cell at the origin contains 0 after $i$ steps if $i \ge 0$, so $\sigma$ is not nilpotent. However, there can only be one occurrence of 1 in a configuration of $X$, so $\sigma$ is asymptotically nilpotent.
If $X$ is sofic and has points with infinite support, then the shift is not SAN (because it is not even asymptotically nilpotent). Using a different CA, there is an example that is topologically transitive, that is for any words $u, v$ that occur in points of $X$, there exists a word $w$ such that $uwv$ occurs in a point of $X$.

*Example 4.* Let $\Sigma = \{\leftarrow, \rightarrow, 0\}$ and let $X$ be the sofic shift with forbidden patterns the regular language $\leftarrow 0^* \leftarrow + \rightarrow 0^* \rightarrow$. Let $f$ be the cellular automaton that moves every $\leftarrow$ to the left and every $\rightarrow$ to the right, removing both on collision. Then $f$ is asymptotically nilpotent but not nilpotent.

Of course, similar examples are obtained on $Z^d$ – the one-one example directly generalizes to higher dimensions, and any one-dimensional subshift can be turned into a higher-dimensional one by having an independent copy of it in every $Z$-coset.

There are also sofic shifts which are not zero-gluing (and thus are in particular not SFTs), but which do not support SAN maps. The following result can be shown with the proof of [5].

*Example 5 (The even and odd shifts).* Let $\Sigma = \{0, 1\}$ and let $X \subset \Sigma^Z$ be the subshift with forbidden patterns the regular language $1(00)^*1$, and $Y \subset \Sigma^Z$ the one with forbidden patterns $10(00)^*1$. The subshift $X$ is called the *odd shift*, and $Y$ the *even shift*. Both are proper sofic, and neither supports SAN CA.

Intuitively, what is going on is that the even and odd shifts are ‘almost’ zero-gluing, in that two finite configurations can be glued together, up to shifting one of them by one, allowing the same constructions as are used in [5].

Every known one-dimensional sofic shift that does allow SAN maps is based on either the one-one or the idea of colliding particles, and subshifts that are, intuitively, ‘almost’ of finite type do not support SAN CA. Can one find a characterization of sofic shifts allowing such behavior?

*Question 6.* Let $X \subset \Sigma^Z$ be a sofic shift. Under what conditions does there exist a cellular automaton on $X$ which is asymptotically nilpotent but not nilpotent?

*Question 7.* Let $X \subset \Sigma^Z$ be a subshift. Are there natural specification, mixing, or gluing properties that forbid the existence of SAN maps $X$? What properties of $X$ are needed for the proofs of [5, 12] to go through?

Another classification question is which sofic shifts have an undecidable nilpotency problem. In [14] it is shown that nilpotency is decidable on countable sofic shifts, and we know it is undecidable on full shifts, so this class is something in-between.

# 5 Nilpotency as uniform convergence to a point

We now set up a more general framework for nilpotency, so that we do not need to give new definitions every time we generalize our model, and so that we can discuss nilpotency also in positive-dimensional settings.
By definition, a cellular automaton is asymptotically nilpotent if and only if the limit of every point in the action of the CA is the all-zero point. We can characterize nilpotency in terms of this convergence:

**Lemma 2.** Let $X \subset \Sigma^{\mathbb{Z}^d}$ be any subshift with $0^{\mathbb{Z}^d} \in X$ and let $f: X \to X$ be a CA. Then $f$ is nilpotent if and only if $f^n(x) \to 0^{\mathbb{Z}^d}$ uniformly in $x \in X$.

Inspired by this, we give the following definitions: If $(X, f)$ is an $\mathbb{N}$-dynamical system $(X$ is a topological space and $f: X \to X$ is a continuous function), then we say it is *nilpotent*, if there is a point $0 \in X$ such that for some $n \in \mathbb{N}$, $f^n(x) = 0$ for all $x \in X$, *asymptotically nilpotent* or *AN* if there is a point $0 \in X$ such that $f^n(x) \to 0$ for all $x \in X$, and *uniformly asymptotically nilpotent* or *UAN* if this convergence is uniform over $X$.

We have

$$ \text{nilpotent} \implies \text{UAN} \implies \text{AN}, $$

and we will see these implications are strict in general.

A system is *non-uniformly asymptotically nilpotent* or *NUAN* if it is asymptotically nilpotent but not uniformly so, and we define *SAN* as before as being asymptotically nilpotent but not nilpotent:

$$ \text{SAN} = \text{AN} \wedge \neg\text{nilpotent}, \quad \text{NUAN} = \text{AN} \wedge \neg\text{UAN} $$

There are many systems that are uniformly asymptotically nilpotent but not nilpotent, even in the zero-dimensional setting, but the previous lemma shows a CA is nilpotent if and only if it is UAN, so a cellular automaton is SAN if and only if it is NUAN.<fnref n="3" /> In general, for a dynamical system we can only say

$$ \text{NUAN} \implies \text{SAN}. $$

The questions we are interested in are of the following type: Given a class $D$ of dynamical systems, are there NUAN/SAN systems in $D$? In this article, we mostly study the case where we fix a dynamical system (a subshift) and let $D$ be its endomorphisms, but we can consider the NUAN/SAN behavior more generally.

We make some basic remarks (see also [5]) and give some examples: A $\mathbb{Z}$-subshift $X$, seen as an $\mathbb{N}$-system with the action of $\sigma$ is, by definition, AN if and only if the cellular automaton $\sigma$ is asymptotically nilpotent on it, and this happens precisely when all points of $X$ contain only zeros in their eventual right tail. Such a subshift is only UAN if and only it is nilpotent if and only if $X = \{0^\mathbb{Z}\}$. Thus the notions NUAN and SAN agree for $\mathbb{Z}$-subshifts as well.

For an $\mathbb{N}$-subshift $X$, the characterization of AN is the same. Such $X$ is UAN if and only if it is nilpotent if and only if there is a bound $m \in \mathbb{N}$ such that $x \in X \implies \forall n \ge m : x_n = 0$. These are precisely the $\mathbb{N}$-subshifts which are finite and contain only finite points. Thus the notions NUAN and SAN agree for $\mathbb{N}$-subshifts.

<footnote n="3">³ See, however, Example 6.</footnote>
If $X \subset \Sigma^{\mathbb{Z}^d}$ is a subshift, then a cellular automaton $f: X \to X$ is AN if and only if its trace $\{y \in \Sigma^{\mathbb{N}} | \exists x \in X : y_n = f^n(x)_{0^d}\}$ is AN as a one-dimensional subshift, and $f$ is nilpotent if and only if its trace is.

As we have seen, there are subshifts which are SAN (equivalently NUAN), for example the one-one subshift. The one-sided one-one subshift (the set of right tails of the one from the previous section) can also be described as follows: Let $\tilde{N} = \mathbb{N} \cup \{\infty\}$ be the one-point compactification of $\mathbb{N}$, with its usual topology. Then the map $f$ defined by $f(n) \mapsto n-1$ (with $\infty - 1 = \infty$) for $n \ge 1$ and $f(0) = \infty$ is continuous on $\tilde{N}$, and $(\tilde{N}, f)$ is NUAN.

The two-sided one-one subshift can similarly be seen as the subtraction homeomorphism on $\mathbb{Z}$. There is also a more geometric way to implement this idea: Seeing the circle $S^1$ as $[0, 1]$ with 0 and 1 identified, the map $f(x) = x^2$ is well-defined and continuous. In this system $(S^1, f)$, every point converges to 0, but this convergence cannot be uniform, as $f$ is a homeomorphism (so every point has a preimage). This example is also NUAN.

The map $x \mapsto x/2$ also gives us continuous dynamics on $[0, 1]$. This map is not nilpotent, but is UAN. Thus, it is SAN but not NUAN.

# 6 Cellular automata on graphs and groups

Next, we generalize in another direction, and replace $\mathbb{Z}^d$ by a graph.

Let $G$ be any *road-colored graph* whose edges are colored with colors from a finite set $S$ in such a way that for every vertex $v \in G$, for each $s \in S$ there is a unique edge with $v$ as initial vertex and $s$ as label. The terminal vertex of this unique edge is denoted by $vS$. If $u \in S^*$, we write $vu = (\cdots((vu_0)u_1)\cdots u_{|u|-1})$ (with $v\epsilon = v$ where $\epsilon$ is the empty word).

Write $\Sigma^G$ for the set of colorings of the nodes of $G$. A cellular automaton on $\Sigma^G$ is a function $f: \Sigma^G \to \Sigma^G$ such that for some function $f_{\text{loc}}: \Sigma^F \to \Sigma$ where $F \subset S^*$ is finite, we have $f(x)_v = f_{\text{loc}}(a \mapsto x_{va})$ for all $x \in \Sigma^G$ and $a \in F$.

An important example are cellular automata on groups: Let $G$ be a group generated by a finite set $S$, and $\Sigma$ a finite alphabet. Then $G$ acts on $\Sigma^G$ by left translations $g \cdot x_h = x_{g^{-1}h}$, and continuous functions $f: \Sigma^G \to \Sigma^G$ commuting with them are precisely the functions that are cellular automata in the sense of the previous definition on any Cayley graph of $G$, that is, there always exist $f_{\text{loc}}: \Sigma^F \to \Sigma$ such that

$$f(x)_v = f_{\text{loc}}(x_{vS_1}, x_{vS_2}, \dots, x_{vS_k})$$

where $s_1, s_2, \dots, s_k \in G$. Setting $G = \mathbb{Z}^d$, we obtain the classical setting of multidimensional CA. For cellular automata on groups, UAN is equivalent to nilpotency. Thus, in this setting SAN and NUAN are equivalent concepts as well.

One can similarly define cellular automata on monoids: If $M$ is a monoid generated by a set $S$, then $M$ has right Cayley graph with edges $(m, ms)$ where $s \in S$, and we can consider cellular automata on this graph. Setting $M = \mathbb{N}$, this corresponds to the usual one-sided cellular automata.
**Example 6.** Let $f : \Sigma^{\mathbb{Z}} \to \Sigma^{\mathbb{Z}}$ be a cellular automaton which is asymptotically nilpotent on periodic points, but not nilpotent, see Theorem 2. Let $C_n$ be the graph with $n$ nodes in a single cycle, with label 1 on each edge. Let $G = \bigcup_n C_n$ be a disjoint union of these graphs, and let $g : \Sigma^G$ be the cellular automaton with the same local rule as $f$. Then clearly $g$ is asymptotically nilpotent. In fact, $g$ is UAN: for every cycle, there is a bounded time after which it contains only zeroes. Nevertheless, $g$ is not nilpotent, as $f$ is not. It follows that this example is not nilpotent, but is UAN. Thus, it is SAN but not NUAN.

Intuitively, this example comes from the fact that the graph is not homogeneous, in the sense that the neighborhoods of different nodes look different. If we could 'translate the graph' and take limits of this translation process, we would in a natural sense obtain copies of $\mathbb{Z}$ where $f$ is not even asymptotically nilpotent. We do not formalize this idea here.

Example 6 can be seen as a cellular automaton on a group action, as the cellular automaton we define commutes with the action of $\mathbb{Z}$ that rotates the information on each $C_n$. We do not formalize this idea either.

While we can have SAN in the setting of CA on graphs (by the previous example), I do not know whether NUAN behavior is possible.

**Question 8.** Is there a road-colored graph $G$ and an alphabet $\Sigma$ such that some CA $f : \Sigma^G \to \Sigma^G$ is NUAN?

The main question is whether we can obtain SAN maps in the group setting:

**Question 9.** Is there a countable group $G$ and an alphabet $\Sigma$ such that some CA $f : \Sigma^G \to \Sigma^G$ is SAN?

## 6.1 What works on general groups?

Many of the arguments of [5] and [12] work on every group, but have only been stated in the $\mathbb{Z}^d$ case. The first is from [5], and states that there are some patterns that empty a particular cell (or set of cells) forever, in any context.

**Lemma 3.** Suppose $G$ is a countable group and $f : \Sigma^G \to \Sigma^G$ is an asymptotically nilpotent CA. Then for every neighborhood $V$ of $0^G$ there exists a nonempty open set $U$ and $n_0 \in \mathbb{N}$ such that $x \in U \implies \forall n \ge n_0 : f^n(x) \in V$.

The second and third lemmas deal with mortal finite configurations. If $f : X \to X$ is a CA and $x \in X$, then $x$ is mortal if $f$ is nilpotent on $\{x\}$, that is, $f^n(x) = 0^G$ for some $n \in \mathbb{N}$. The proof of both lemmas below are based on the observation that in an asymptotically nilpotent CA, every cell (or set of cells) must regularly visit the all-zero cylinder.

The second lemma states that if a finite configuration does not spread under an asymptotically nilpotent CA, then it is mortal.

**Lemma 4.** Suppose $G$ is a countable group and $f : \Sigma^G \to \Sigma^G$ is an asymptotically nilpotent CA. If $x$ is a finite configuration such that the set $\{v \in G \mid \exists n : f^n(x)_v \ne 0\}$ is finite, then $x$ is mortal.
The following is proved like Lemma 2 of [12].

**Lemma 5.** Suppose $G$ is a countable group, $f: \Sigma^G \to \Sigma^G$ is an asymptotically nilpotent CA and there is a dense set of finite mortal configurations. Then $f$ is nilpotent.

We give an intuitive outline of the proof of the case $G = \mathbb{Z}$ of Theorem 1 in [5], highlighting how the geometry of $\mathbb{Z}$ is used: Suppose we have an asymptotically nilpotent CA. We use Lemma 3 to get a word $w$ which blocks information flow through its central coordinate. One half of such word (after a few iterations) must then block information flow from one side. Sticking such halves around a finite configuration, the configuration becomes stuck in a finite segment, and it must then be mortal by Lemma 4. This means there is a dense set of mortal finite configurations, and we conclude with Lemma 5.<fnref n="4" />

In this proof, we make essential use of the fact $\mathbb{Z}$ has multiple ends: Cutting $w$ in half effectively splits the group in two, and the CA will never see over the gap. However, everything else follows from general arguments.

In the $d \ge 2$ case, the same idea does not work directly, as the blocking words $w$ are replaced by blocking patterns, and they need not block information flow in any essential way. The new idea in [12] is that periodizing a point makes the cellular automaton simulate a one-dimensional CA, and we already know the result for such CA. The periodization must be doable in any direction, so we make essential use of the fact that there are quotient maps $\mathbb{Z}^d \to \mathbb{Z}$ ‘for every dimension $d'$, which is almost the definition of $\mathbb{Z}^d$. In this sense, we make essential use of the algebraic structure of $\mathbb{Z}^d$.

For some specific groups, it is plausible that SAN behavior can be ruled out easily, by a more assiduous application of these ideas. In the case of free groups (which also have multiple ends), one can directly attempt to mimic the proof of [5], while in the case of the Heisenberg group, one can try to mimic the periodization idea of [12].

**Conjecture 1.** If $G$ is a free group or $G$ is the Heisenberg group, then there are no SAN cellular automata on any full shift on $G$.

# 7 CA with very sparse spacetime diagrams

In this section, we list some results of [15]. The construction of [15] gives insight into why it is difficult to show that SAN behavior is impossible: we can ‘almost’ have it on a full shift, in the sense that a non-nilpotent cellular automaton can have both very sparse rows and very sparse columns in the limit.

Consider the full shift $\Sigma^{\mathbb{Z}}$. Then the *Besicovitch pseudometric* is defined by

$$d_B(x, y) = \limsup_{n \to \infty} \frac{1}{2n + 1} \left| \{-n \le i \le n \mid x_i \ne y_i\} \right|.$$

<footnote n="4">⁴ As we only want to emphasize what property of $\mathbb{Z}$ is used, we are of course omitting some technical details. Interested readers will find the details in the references.</footnote>
Then $(\Sigma^Z, d_B)$ is a topological (non-Hausdorff non-compact) space called the Besicovitch space, and if $f: \Sigma^Z \to \Sigma^Z$ is a cellular automaton on $\Sigma^Z$ (in the usual sense), then $f$ is also an endomorphism (continuous shift-commuting self-map) of $(\Sigma^Z, d_B)$. We write $d_C$ for the usual metric inducing the product topology on $\Sigma^Z$.

We cite some results of [15] about nilpotency on the Besicovitch space.

**Proposition 1.** Let $f: \Sigma^Z \to \Sigma^Z$ be a cellular automaton. Then

- $f$ is nilpotent on $(\Sigma^Z, d_B)$ if and only if it is nilpotent on $(\Sigma^Z, d_C)$, and

- if $f$ is AN on $(\Sigma^Z, d_B)$, then it is UAN on $(\Sigma^Z, d_B)$.

These follow from [15, Proposition 41] and [15, Lemma 43], respectively. The second item shows that there are no cellular automata that are NUAN over the Besicovitch space.

The main result of [15] is the construction of a CA with very sparse spacetime diagrams, and the following is one of the corollaries of the construction:

**Theorem 5.** There is a cellular automaton which is UAN on $(\Sigma^Z, d_B)$ but is not nilpotent on $(\Sigma^Z, d_C)$.

Thus, there are cellular automata that are SAN over the Besicovitch space.

Asymptotic nilpotency for the Besicovitch metric is ‘spatial nilpotency’, that is, most cells being zero on every row. Thus, to formulate this notion, we need a notion of ‘space’. For the temporal direction, we can formulate a notion of nilpotency in density directly: If $f: X \to X$ is a dynamical system and $0 \in X$, then $f$ is asymptotically nilpotent in temporal density or ANTD$^5$ if

$$ \forall \epsilon > 0 : \forall x \in X : \liminf_{n \to \infty} \frac{1}{n} |\{0 \le i < n \mid d(f^i(x), 0) < \epsilon\}| = 1. $$

If the convergence is uniform in $X$ for all $\epsilon$, we use the obvious acronym UANTD.

**Proposition 2.** Let $f: \Sigma^Z \to \Sigma^Z$ be a cellular automaton. Then

- $f$ has a unique invariant measure if and only if it is ANTD, and

- if $f$ is ANTD then it is UANTD.

The first observation is well-known, see [15, Proposition 5] for a proof. It is the reason why ANTD cellular automata are usually called *uniquely ergodic*, since this is the term for having a unique invariant measure in ergodic theory. The second condition says that there are no CA that are ‘non-uniformly asymptotically nilpotent in temporal density’, and it is also shown in [15, Proposition 5].

The construction of [15] also gives a CA where the temporal density of zeroes is high:

**Theorem 6.** There exists a cellular automaton $f: \Sigma^Z \to \Sigma^Z$ which is ANTD but not nilpotent.

<footnote n="5">⁵ It would be nice to call this just ‘asymptotic nilpotency in density’, but this is used in [15] in the spatial sense.</footnote>
Thus, there are cellular automata that are 'strictly asymptotically nilpotent in temporal density'.

We can formalize the property of [15] that the density of zeroes becomes high from every starting configuration also using measures: the CA of [15] proving Theorem 5 also has the property that every shift-invariant measure converges to the Dirac measure at zero in the iteration of the CA. In other words, there is a non-nilpotent CA $f : \Sigma^{\mathbb{Z}} \to \Sigma^{\mathbb{Z}}$ which, acting over the space of shift-invariant probability measures on $\Sigma^{\mathbb{Z}}$, is asymptotically nilpotent toward the Dirac measure at $0^{\mathbb{Z}}$.

We mention that for cellular automata, there is also another well-known kind of nilpotency on the space of measures, namely randomization:

*Example 7.* Let $f: \mathbb{Z}_2^2 \to \mathbb{Z}_2^2$ be the two-neighbor XOR $f(x)_i = x_i + x_{i+1}$. Then $f$ acts on the space of shift-invariant measures $M_\sigma$ on $\mathbb{Z}_2^2$. It is known that $f$ is randomizing in density [9, 7, 11] in the sense that $f^n(\mu)$ converges weakly to the uniform Bernoulli measure 'except for a set of times of density zero', whenever $\mu$ is a full-support Bernoulli measure.<fnref n="6" /> Combining the terminology of Section 3 with that of this section means precisely that $f$ is ANTD on the set of full-support Bernoulli measures, with nilpotency towards the uniform measure.

## Acknowledgements

We thank Pierre Guillon and Ilkka Törmä for their comments on the draft.

## References

1. Stål O. Aanderaa and Harry R. Lewis. Linear sampling and the $\forall\exists\forall$ case of the decision problem. *The Journal of Symbolic Logic*, 39:519–548, 9 1974.

2. Mike Boyle, Ronnie Pavlov, and Michael Schraudner. Multidimensional sofic shifts without separation and their factors. *Transactions of the American Mathematical Society*, 362(9):4617–4653, 2010.

3. Bruno Durand, Andrei Romashchenko, and Alexander Shen. Fixed-point tile sets and their applications. *J. Comput. System Sci.*, 78(3):731–764, 2012.

4. Péter Gács, Georgy L. Kurdyumov, and Leonid A. Levin. One-dimensional uniform arrays that wash out finite islands. *Problemy Peredachi Informatsii*, 14(3):92–96, 1978.

5. Pierre Guillon and Gaétan Richard. Asymptotic behavior of dynamical systems and cellular automata. *ArXiv e-prints*, April 2010.

6. Jarkko Kari. The nilpotency problem of one-dimensional cellular automata. *SIAM J. Comput.*, 21(3):571–586, 1992.

7. D.A. Lind. Applications of ergodic theory and sofic systems to cellular automata. *Physica D: Nonlinear Phenomena*, 10(1-2):36–44, 1984.

8. Douglas Lind and Brian Marcus. *An introduction to symbolic dynamics and coding*. Cambridge University Press, Cambridge, 1995.

<footnote n="6">⁶ The initial set of measures can be extended considerably, but we do not know a published reference dealing with a class that is obviously closed under $f$.</footnote>
9. Munemi Miyamoto. An equilibrium state for a one-dimensional life game. *Journal of Mathematics of Kyoto University*, 19(3):525–540, 1979.

10. Ronnie Pavlov and Michael Schraudner. Classification of sofic projective subdynamics of multidimensional shifts of finite type. *Transactions of the American Mathematical Society*, 367(5):3371–3421, 2015.

11. Marcus Pivato. The ergodic theory of cellular automata. *Int. J. General Systems*, 41(6):583–594, 2012.

12. Ville Salo. On Nilpotency and Asymptotic Nilpotency of Cellular Automata. *ArXiv e-prints*, May 2012.

13. Ville Salo. Subshifts with sparse projective subdynamics. *ArXiv e-prints*, May 2016.

14. Ville Salo and Ilkka Törmä. Computational aspects of cellular automata on countable sofic shifts. *Mathematical Foundations of Computer Science 2012*, pages 777–788, 2012.

15. Ilkka Törmä. A uniquely ergodic cellular automaton. *J. Comput. Syst. Sci.*, 81(2):415–442, 2015.