Invariant sets and nilpotency of endomorphisms of algebraic sofic shifts

Abstract

Let G be a group and let V be an algebraic variety over an algebraically closed field K. Let A denote the set of K-points of V. We introduce algebraic sofic subshifts ${\Sigma \subset A^G}$ and study endomorphisms $\tau \colon \Sigma \to \Sigma $. We generalize several results for dynamical invariant sets and nilpotency of $\tau $ that are well known for finite alphabet cellular automata. Under mild assumptions, we prove that $\tau $ is nilpotent if and only if its limit set, that is, the intersection of the images of its iterates, is a singleton. If moreover G is infinite, finitely generated and $\Sigma $ is topologically mixing, we show that $\tau $ is nilpotent if and only if its limit set consists of periodic configurations and has a finite set of alphabet values.

1 Introduction

The main goal of the present paper is to extend and generalize well-known results about limit sets and nilpotency of classical cellular automata, that is, cellular automata with finite alphabets, to the setting of algebraic cellular automata over algebraic sofic subshifts, where the alphabet is the set of rational points of an algebraic variety.

Since the pioneering work of John von Neumann in the 1940s [58], the mathematical theory of cellular automata has led to very interesting questions, with deep connections to areas such as theoretical computer science, decidability, dynamical systems, ergodic theory, harmonic analysis, and geometric group theory. In his empirical classification of the long-term behavior of classical cellular automata, Wolfram [60] introduced the notion of a limit set. For classical cellular automata, properties of limit sets and their relations with various notions of nilpotency were subsequently investigated by several authors (see [18, 24, 25, 34, 51]). In particular, Aanderaa and Lewis [1] and, independently, Kari [25] proved undecidability of nilpotency for classical cellular automata over $\mathbb {Z}$ : this undecidability result constitutes one of the most influential results in the theory of cellular automata and one of the main motivations for the study of nilpotency in the symbolic dynamics setting. In general, these properties of limit sets become false when the alphabet is allowed to be infinite. A major problem arising when working with infinite alphabets is that images of subshifts of finite type may fail to be closed (e.g. [10, Example 3.3.3]). Nevertheless, infinite alphabet subshifts and their dynamics are not only intrinsically interesting but also fundamental to the study of smooth dynamical systems (cf. e.g. [8], [28, Ch. 7], [29, 52, 53] and the references therein).

After Gromov [20], the study of injectivity and surjectivity of algebraic cellular automata was pursued in [11, 12, 14, 15, 39] to obtain generalizations of the Ax–Grothendieck theorem [3], [23, Proposition 10.4.11] and of the Moore–Myhill Garden of Eden theorem [35, 36]. Nilpotency is in the opposite direction since a nilpotent map is never injective nor surjective when the underlying set has at least two elements.

To state our results, let us first introduce some terminology and notation. Let $f \colon X \to X$ be a map from a set X into itself. Given an integer $n \geq 1$ , the nth iterate of f is the map $f^n \colon X \to X$ defined by (n times). The sets $f^n(X)$ , $n \geq 1$ , form a decreasing sequence of subsets of X. The limit set of f is the set of points that occur after iterating f arbitrarily many times.

Observe that $f(\Omega (f)) \subset \Omega (f)$ . The inclusion may be strict, and equality holds if and only if every $x \in \Omega (f)$ admits a backward orbit, that is, a sequence $(x_i)_{i \geq 0}$ of points of X such that $x_0 = x$ and $f(x_{i + 1}) = x_i$ for all $i \geq 0$ . Clearly, f is surjective if and only if $\Omega (f) = X$ . Note also that and that $\Omega (f^n) = \Omega (f)$ for every $n \geq 1$ . The map f is stable if $f^{n+1}(X)=f^n(X)$ for some $n \geq 1$ . If f is stable, then $\Omega (f) \not = \varnothing $ unless $X = \varnothing $ . Clearly, f is stable whenever X is finite. If X is infinite, there always exist maps $f \colon X \to X$ with $\Omega (f) = \varnothing $ (cf. Lemma A.1).

Assume that X is a topological space and $f \colon X \to X$ is a continuous map. One says that $x \in X$ is a recurrent (respectively non-wandering) point of f if for every neighborhood U of x, there exists $n \geq 1$ such that $f^n(x) \in U$ (respectively $f^n(U)$ meets U). Let $\operatorname {\mathrm {R}}(f)$ (respectively $\operatorname {\mathrm {NW}}(f)$ ) denote the set of recurrent (respectively non-wandering) points of f. It is immediate that $\operatorname {\mathrm {Per}}(f) \subset \operatorname {\mathrm {R}}(f) \subset \operatorname {\mathrm {NW}}(f)$ and that $\operatorname {\mathrm {NW}}(f)$ is a closed subset of X. In general, neither $\operatorname {\mathrm {Per}}(f)$ , nor $\operatorname {\mathrm {R}}(f)$ , nor $\Omega (f)$ are closed in X (see Example 15.1).

Suppose now that X is a uniform space and $f \colon X \to X$ is a uniformly continuous map. One says that a point $x \in X$ is chain-recurrent if for every entourage E of X, there exist an integer $n \geq 1$ and a sequence of points $x_0,x_1,\ldots ,x_n \in X$ such that $x = x_0 =~x_n$ and $(f(x_i),x_{i + 1}) \in E$ for all $0 \leq i \leq n - 1$ . We shall denote by $\operatorname {\mathrm {CR}}(f)$ the set of chain-recurrent points of f. Observe that $\operatorname {\mathrm {CR}}(f)$ is always closed in X.

Let G be a group and let A be a set, called the alphabet. The set , consisting of all maps from G to A, is called the set of configurations over the group G and the alphabet A. We equip $A^G = \prod _{g \in G} A$ with its prodiscrete uniform structure, that is, the product uniform structure obtained by taking the discrete uniform structure on each factor A of $A^G$ . Note that $A^G$ is a totally disconnected Hausdorff space and that $A^G$ is compact if and only if A is finite. The shift action of the group G on $A^G$ is the action defined by $(g,x) \mapsto g x$ , where for all $g,h \in G$ and $x \in A^G$ . This action is uniformly continuous with respect to the prodiscrete uniform structure.

For a subgroup $H \subset G$ , define . Then $\operatorname {\mathrm {Fix}}(G)$ is the set of constant configurations while $\operatorname {\mathrm {Fix}}(\{1_G\}) = A^G$ . A configuration $x \in A^G$ is said to be periodic if its G-orbit is finite, that is, there is a finite index subgroup H of G such that $x \in \operatorname {\mathrm {Fix}}(H)$ .

A G-invariant subset $\Sigma \subset A^G$ is called a subshift of $A^G$ . Note that we do not require closedness in $A^G$ in our definition of a subshift.

Given a finite subset $D \subset G$ and a (finite or infinite) subset $P \subset A^D$ , the set

(1.1)

is a closed subshift of $A^G$ (here $(g^{-1}x)\vert _D \in A^D$ denotes the restriction of the configuration $g^{-1}x$ to D). One says that $ \Sigma (D,P)$ is the subshift of finite type associated with $(D,P)$ and that D is a defining memory set for $\Sigma $ .

Let B be another alphabet set. A map $\tau \colon B^G \to A^G$ is called a cellular automaton if there exist a finite subset $M \subset G$ and a map $\mu \colon B^M \to A$ such that

(1.2) $$ \begin{align} \tau(x)(g) = \mu( (g^{-1}x)\vert_M) \quad \text{for all } x \in B^G \text{ and } g \in G. \end{align} $$

Such a set M is then called a memory set and $\mu $ is called a local defining map for $\tau $ . It is clear from the definition that every cellular automaton $\tau \colon B^G \to A^G$ is uniformly continuous and G-equivariant (see [10]).

More generally, if $\Sigma _1 \subset B^G$ and $\Sigma _2 \subset A^G$ are subshifts, a map $\tau \colon \Sigma _1 \to \Sigma _2$ is a cellular automaton if it can be extended to a cellular automaton $B^G \to A^G$ .

Suppose now that $U, V$ are algebraic varieties (respectively algebraic groups) over a field K, and let , denote the sets of K-points of V and U, that is, the set consisting of all K-scheme morphisms $\operatorname {\mathrm {Spec}}(K) \to V$ and $\operatorname {\mathrm {Spec}}(K) \to U$ , respectively. See [14, Appendix A], [15, §2] for basic definitions and properties of algebraic varieties. The following definition was introduced in the case $U=V$ in [14, Definition 1.1] and [39] after Gromov [20]. A cellular automaton $\tau \colon B^G \to A^G$ is an algebraic (respectively algebraic group) cellular automaton if $\tau $ admits a memory set M with local defining map $\mu \colon B^M \to A$ induced by some algebraic morphism (respectively homomorphism of algebraic groups) $f \colon U^M \to V$ (here $U^M$ denotes the K-fibered product of a family of copies of U indexed by M). More generally, given subshifts $\Sigma _1 \subset B^G$ and $\Sigma _2 \subset A^G$ , a map $\tau \colon \Sigma _1 \to \Sigma _2$ is called an algebraic (respectively algebraic group) cellular automaton if it is the restriction of some algebraic (resp. algebraic group) cellular automaton ${\tilde {\tau } \colon B^G \to A^G}$ (see §16 for an example).

Every cellular automaton with finite alphabet A is an algebraic cellular automaton over any field K (see [14, remarks after Definition 1]). Indeed, it suffices to embed A as a subset of K and then observe that, if M is a finite set, any map $\mu \colon A^M \to A$ is the restriction of some polynomial map $P \colon K^M \to K$ (which can be made explicit by using Lagrange interpolation formula). Similarly, any linear cellular automaton (cf. [10, Ch. 8], [16]) is an algebraic cellular automaton: if A is a finite-dimensional vector space over a field K and M is a finite set, then any linear map $\mu \colon A^M \to A$ is clearly a polynomial.

Definition 1.1. One says that $\Sigma \subset A^G$ is an algebraic (respectively algebraic group) subshift of finite type if there exist a finite subset $D \subset G$ and an algebraic subvariety (respectively algebraic subgroup) $W \subset V^D$ such that, with the notation introduced in (1.1), one has $\Sigma = \Sigma (D,W(K))$ .

By analogy with the definition of sofic subshifts in the classical setting, we define algebraic sofic subshifts and algebraic group sofic subshifts as follows (see Definition 16.4 for more general notions).

Definition 1.2. Let G be a group and let V be an algebraic variety (respectively algebraic group) over a field K. Let . A subset $\Sigma \subset A^G$ is called an algebraic (respectively algebraic group) sofic subshift if it is the image of an algebraic (respectively algebraic group) subshift of finite type $\Sigma ' \subset B^G$ , where $B=U(K)$ and U is a K-algebraic variety (respectively K-algebraic group), under an algebraic (respectively algebraic group) cellular automaton $\tau ' \colon B^G \to A^G$ .

Every algebraic sofic subshift $\Sigma \subset A^G$ is indeed a subshift but it may fail to be closed in $A^G$ (cf. Example 15.1). However, it turns out that, under suitable natural conditions (see hypotheses (H1), (H2), (H3) below), all algebraic sofic subshifts $\Sigma \subset A^G$ are closed in $A^G$ (cf. Corollary 8.2). Moreover, we establish a fundamental characterization of algebraic subshifts of finite type by the descending chain property (cf. Theorem 10.1).

With the notation as in Definition 1.2, we shall investigate in this paper various dynamical aspects of an algebraic cellular automaton $\tau \colon \Sigma \to \Sigma $ over an algebraic sofic subshift $\Sigma \subset A^G$ satisfying one of the following hypotheses (with the same notation throughout the paper):

1. (H1) K is an uncountable algebraically closed field (e.g. $K = \mathbb {C}$ );

2. (H2) K is algebraically closed and $U, V$ are complete (e.g. projective) algebraic varieties over K;

3. (H3) K is algebraically closed, V is an algebraic group over K, $\Sigma \subset A^G$ is an algebraic group sofic subshift, and $\tau \colon \Sigma \to \Sigma $ is an algebraic group cellular automaton.

We shall establish the following result.

Theorem 1.3. Let G be a group and let V be an algebraic variety over a field K. Let and let $\Sigma \subset A^G$ be an algebraic sofic subshift. Let $\tau \colon \Sigma \to \Sigma $ be an algebraic cellular automaton and assume that one of the conditions $(\mathrm {H1})$ , $(\mathrm {H2})$ , $(\mathrm {H3})$ is satisfied. Then the following hold:

1. (i) $\Omega (\tau )$ is a closed subshift of $A^G$ ;

2. (ii) $\tau (\Omega (\tau )) = \Omega (\tau )$ ;

3. (iii) $\operatorname {\mathrm {Per}}(\tau ) \subset \operatorname {\mathrm {R}}(\tau ) \subset \operatorname {\mathrm {NW}}(\tau ) \subset \operatorname {\mathrm {CR}}(\tau ) \subset \Omega (\tau )$ ;

4. (iv) if $(\mathrm {H2})$ or $(\mathrm {H3})$ is satisfied and $\Omega (\tau )$ is a subshift of finite type, then $\tau $ is stable;

5. (v) for every subgroup $H \subset G$ , if $\Sigma \cap \operatorname {\mathrm {Fix}}(H) \neq \varnothing $ , then $\Omega (\tau ) \cap \operatorname {\mathrm {Fix}}(H) \neq \varnothing $ .

See [16, Theorem 1.5] for a linear version of the above theorem.

One says that a map $f \colon X \to X$ from a set X into itself is nilpotent if there exist a constant map $c \colon X \to X$ and an integer $n_0 \geq 1$ such that $f^{n_0} = c$ . This implies $f^n = c$ for all $n \geq n_0$ . Such a constant map c is then unique and we say that the unique point $x_0 \in X$ such that $c(x) = x_0$ for all $x \in X$ is the terminal point of f. The terminal point of a nilpotent map is its unique fixed point.

Observe that if $f \colon X \to X$ is nilpotent with terminal point $x_0$ , then $\Omega (f) = \{x_0\}$ is a singleton. The converse is not true in general. Actually, as soon as the set X is infinite, there exist non-nilpotent maps $f \colon X \to X$ whose limit set is reduced to a single point (cf. Lemma A.1). However, in the algebraic setting, we obtain the following result.

Theorem 1.4. If we keep the same notation and hypotheses as in Theorem 1.3, then the following conditions are equivalent:

1. (a) $\tau $ is nilpotent;

2. (b) the limit set $\Omega (\tau )$ is reduced to a single configuration.

The analog of Theorem 1.4 for classical cellular automata follows from [18, Theorem 3.5]. However, Theorem 1.4 can be seen as a generalization of an interesting and non-trivial property of endomorphisms of algebraic varieties (by taking $G = \{1_G\}$ ).

Both Theorems 1.3 and 1.4 become false if we remove the hypothesis that the ground field K is algebraically closed (see Examples 15.1, 15.8, and 15.9). To illustrate the significance of our results, note that for a group G and a finite set A, the space $A^G$ is compact by Tychonoff’s theorem. Consequently, if $\Sigma \subset A^G$ is a closed subshift and $\tau \colon A^G \to A^G$ is a cellular automaton, then $\tau ^n(\Sigma )$ is closed in $A^G$ for every $n \geq 1$ and it follows that $\Omega (\tau )$ is a closed subshift of $A^G$ . A standard compactness argument shows also that $\Omega (\tau ) \not = \varnothing $ if $\Sigma \neq \varnothing $ (cf. [18]). When A is infinite, $A^G$ is no longer compact and, given a closed subshift $\Sigma \subset A^G$ , the limit set of a cellular automaton $\tau \colon \Sigma \to \Sigma $ is, in general, no longer closed in $A^G$ (cf. Example 15.1). Also, when A is infinite, it may happen that $\Omega (\tau ) = \varnothing $ while $\Sigma \neq \varnothing $ or even $\tau (\Omega (\tau )) \subsetneqq \Omega (\tau )$ (cf. Proposition A.2 and Example 15.8).

A self-map $f \colon X \to X$ on a set X is said to be pointwise nilpotent if there exists a point $x_0 \in X$ such that for every $x \in X$ , there exists an integer $n_0 \geq 1$ such that $f^n(x)=x_0$ for all $n \geq n_0$ .

Consider a group G with the following property: for every finite alphabet A, any cellular automaton $\tau \colon A^G \to A^G$ with $\Omega (\tau )$ finite is nilpotent. Such a group G cannot be finite. Indeed, for G finite and , the identity cellular automaton map $\tau \colon A^G \to A^G$ has a finite limit set $\Omega (\tau ) = A^G$ without being nilpotent. By [24, Corollary 4] or [18], we know that $G=\mathbb {Z}$ satisfies the above property. In Theorem 13.1, we show that actually it is satisfied by all infinite groups.

More generally, we obtain the following various characterizations of nilpotent algebraic cellular automata.

Theorem 1.5. Let G be an infinite group and let V be an algebraic variety over a field K. Let $A=V(K)$ and let $\Sigma \subset A^G$ be a non-empty topologically mixing algebraic sofic subshift (e.g. $A^G$ for $A \not = \varnothing $ ). Let $\tau \colon \Sigma \to \Sigma $ be an algebraic cellular automaton. Assume that one of the conditions $(\mathrm {H1})$ , $(\mathrm {H2})$ , $(\mathrm {H3})$ is satisfied. Then the following are equivalent:

1. (a) $\tau $ is nilpotent;

2. (b) $\tau $ is pointwise nilpotent;

3. (c) the limit set $\Omega (\tau )$ is finite.

If G is finitely generated, then the above conditions are equivalent to

1. (d) each $x \in \Omega (\tau )$ is periodic and the set $\{x(1_G) \colon x \in \Omega (\tau )\}$ of alphabet values of $\Omega (\tau )$ is finite.

Note that for classical cellular automata, the equivalence of items (a) and (b) does not require neither the topological mixing nor the soficity conditions on the subshift ${\Sigma \subset A^G}$ (this is a result going back to Kari, [50]). We do not know whether or not, in our more general setting, the above-mentioned conditions can be dropped. For classical cellular automata, the equivalence of items (b) and (c) is given in Theorem 13.1. Note that, however, if the alphabet A is infinite, for any group G, there exist non-nilpotent cellular automata whose limit set is reduced to a single configuration and therefore is finite (cf. Proposition A.2).

A linear version of the above theorem was given in [16, Theorem 1.9 and Corollary 1.10]. Our general strategy evolves around the analysis of the so-called space-time inverse system associated with a cellular automaton (cf. §4). Such inverse systems and their variants as constructed in the proofs of the main theorems allow us to first conduct a local analysis of the dynamical system as in Theorems 7.1 and 9.1. We can then pass to the inverse limit, by means of the key technical algebro-geometric tools Lemmas 3.1 and 3.3, to obtain global properties such as a closed mapping property in Theorem 8.1 and a characterization of algebraic subshifts of finite type in Theorem 10.1. Variants of space-time inverse systems also allow us to reduce Theorem 1.5 to the finite alphabet case studied in Theorem 13.1.

We remark that by a similar strategy, it is shown in [42] that for a polycyclic-by-finite group G and an algebraic group V over an algebraically closed field K, all algebraic group sofic subshifts of $A^G$ , where $A=V(K)$ , are in fact algebraic group subshifts of finite type. Moreover, our techniques and results, notably the closed mapping property (Theorem 8.1) and the Noetherianity of algebraic subshifts of finite type (Theorem 10.1), admit a wide range of applications including the shadowing property of algebraic group cellular automata [43, 44], the Garden of Eden theorem for algebraic group cellular automata [47], a dynamical characterization of the Noetherianity of group rings in terms of the Markov properties [16], properties of images of algebraic subshifts under embeddings of symbolic varieties [45], and extensions of the direct finiteness conjecture of Kaplansky [17, 40, 41, 46, 48]. Finally, for interested readers, we would like to mention the connections of our results and their applications with some finiteness results in difference algebras and proalgebraic groups obtained in, e.g., [38, 56, 59].

Most of our results for arbitrary groups are inferred from the results for finitely generated groups by the restriction technique applied to cellular automata over subshifts of sub-finite-type (cf. §§2.4, 2.5, 2.6).

A detailed analysis is given in Example 15.1 to provide a non-trivial counter-example to Theorems 1.3 and 8.1. Some generalizations of our results are given in §16. In the Appendix, we study pointwise nilpotency over infinite groups and arbitrary alphabets (cf. Proposition A.5).

2 Preliminaries

2.1 Notation

We use the symbols $\mathbb {Z}$ for the integers, $\mathbb {N}$ for the non-negative integers, $\mathbb {R}$ for the reals, and $\mathbb {C}$ for the complex numbers.

We write $A^B$ for the set consisting of all maps from a set B into a set A. Let $C \subset B$ . If $x \in A^B$ , we denote by $x\vert _C$ the restriction of x to C, that is, the map $x\vert _C \colon C \to A$ given by $x\vert _C(c) = x(c)$ for all $c \in C$ . If $X \subset A^B$ , we denote . Let $E,F$ be subsets of a group G. We write and define inductively $E^n$ for all $n \in \mathbb {N}$ by setting and .

Let A be a set and let E be a subset of a group G. Given $x \in A^E$ , we define $gx \in A^{gE}$ by for all $h \in g E$ .

2.2 Algebraic varieties

Let V be an algebraic variety over a field K, that is, a reduced K-scheme of finite type. We equip V with its Zariski topology. Every subset $Z \subset V$ is equipped with the induced topology and we denote by $Z(K)$ the subset of K-points of V lying in Z. Subvarieties of V mean closed subsets with the reduced induced scheme structure.

Remark 2.1. Every subvariety of a complete (that is, proper) algebraic variety is also complete. Images of morphisms of complete algebraic varieties are complete subvarieties (cf. [31, §3.3.2]). Likewise, kernels and images of homomorphisms of algebraic groups are also algebraic subgroups and are thus Zariski closed (cf. [33, Proposition 1.41, Theorems 5.80, 5.81]).

Suppose now that the base field K is algebraically closed. Then we can identify the set of K-points $A=V(K)$ of a K-algebraic variety V with the set of closed points of V (cf. [21, Proposition 6.4.2]). By a common abuse, we regard A as an algebraic variety. Similarly, induced maps on closed points by morphisms of K-algebraic varieties are also called algebraic morphisms.

2.3 Chain-recurrent points

Proposition 2.2. Let X be a uniform space and let $f \colon X \to X$ be a continuous map. Then $\operatorname {\mathrm {NW}}(f) \subset \operatorname {\mathrm {CR}}(f)$ .

Proof. (Cf. [55, Proposition 1.7] in the metrizable case) Let $x \in \operatorname {\mathrm {NW}}(f)$ and let E be an entourage of X. Choose a symmetric entourage S of X such that $S\circ S\subset E$ . By the continuity of f at x, there exists a symmetric entourage T of X with $T \subset S$ such that $(f(x),f(z)) \in S$ whenever $(x,z) \in T$ . The set $U \subset X$ , consisting of all $z \in X$ such that $(x,z) \in T$ , is a neighborhood of x. Since x is non-wandering, there exist an integer $n \geq 1$ and a point $y \in U$ such that $f^n(y) \in U$ . Let us show that there is a sequence of points $x_0,x_1,\ldots ,x_n \in X$ such that $x= x_0 = x_n$ and $(f(x_i),x_{i + 1}) \in E$ for all $0 \leq i \leq n - 1$ . First observe that since $y \in U$ , we have $(x,y) \in T$ and therefore $(f(x), f(y)) \in S$ . If $n=1$ , we can take $x_0 = x_1 = x$ . Indeed, we then have $f(y) = f^n(y) \in U$ and hence $(f(y),x) {\kern-1pt}\in{\kern-1pt} T \subset S$ . Therefore, $(f(x_0),x_1) = (f(x),x) {\kern-1pt}\in{\kern-1pt} S \circ S \subset E$ . If $n \geq 2$ , we can take the points $x_0,x_1,\ldots ,x_n$ defined by $x = x_0 = x_n$ and $x_i = f^i(y)$ for all $1 \leq i \leq n -1$ . Indeed, we then have $(f(x_0),x_1) = (f(x),f(y)) \in S \subset S \circ S \subset E$ . However, we have $(f(x_i),x_{i+1}) = (f^{i + 1}(y),f^{i + 1}(y)) \in E$ for all $1 \leq i \leq n -2$ . Finally, as $f^n(y) \in U$ , we have $(f(x_{n - 1}),x_n) = (f^n(y),x) \in T \subset S \subset S \circ S \subset E$ . This shows that ${x \in \operatorname {\mathrm {CR}}(f)}$ .

Proposition 2.3. Let X be a Hausdorff uniform space and let $f \colon X \to X$ be a uniformly continuous map. Suppose that $f^n(X)$ is closed in X for all $n \in \mathbb {N}$ . Then $\operatorname {\mathrm {CR}}(f) \subset \Omega (f)$ .

Proof. Denote by $\mathcal {E}$ the set of entourages of X. Let $x \in \operatorname {\mathrm {CR}}(f)$ . Given $E \in \mathcal {E}$ , we define $\nu (E) \in \mathbb {N} \setminus \{0\}$ to be the least $n \in \mathbb {N}$ such that there exists a sequence of points $x_0,x_1,\ldots ,x_n \in X$ satisfying that $x = x_0 = x_n$ and $(f(x_i), x_{i + 1}) \in E$ for all $0 \leq i \leq n - 1$ . Note that the map $\nu \colon \mathcal {E} \to \mathbb {N} \setminus \{0\}$ is decreasing in the sense that if $E,E' \in \mathcal {E}$ and $E \subset E'$ , then $\nu (E') \leq \nu (E)$ . We distinguish two cases according to whether the map $\nu $ is bounded or not.

In the first case, let . Take $E_0 \in \mathcal {E}$ such that $\nu (E_0) = k$ . Let $E \in \mathcal {E}$ . Choose a symmetric entourage $S \in \mathcal {E}$ such that

$$ \begin{align*} \underbrace{S \circ S \circ \cdots \circ S}_{k\ {\tiny \mathrm{times}}} \subset E. \end{align*} $$

Since f is uniformly continuous, so are $f^{2}, \ldots , f^{k}$ . Thus, we can find a symmetric entourage $T \subset E_0$ such that $(f^p(y),f^p(z)) \in S$ whenever $(y,z) \in T$ and ${0 \leq p \leq k}$ . By the maximality of k and the fact that $T \subset E_0$ , we have $\nu (T) = k$ . Therefore, we can find a sequence of points $x_0, x_1, \ldots , x_k \in X$ such that $x =x_0=x_k$ and $(f(x_i), x_{i+1}) \in T$ for all $0 \leq i \leq k - 1$ . Looking at the sequence of points $f^k(x) = f^k(x_0), f^{k - 1}(x_{1}), f^{k - 2}(x_{2}), \ldots , f^{1}(x_{k - 1}), x_k = x$ and using the fact that, for all ${0 \leq i \leq k -1}$ ,

$$ \begin{align*} (f^{k - i}(x_{i}),\quad f^{k - i - 1}(x_{i + 1})) = (f^{k - i - 1}(f(x_{i })),\quad f^{k - i - 1}(x_{i + 1}))) \in S \end{align*} $$

since $(f(x_{i }), x_{i + 1}) \in T$ , we see that

$$ \begin{align*} ( f^k(x),x) \in \underbrace{S \circ S \circ \cdots \circ S}_{k\ {\tiny \mathrm{times}}} \subset E. \end{align*} $$

As the entourage $E \in \mathcal {E}$ was arbitrary and X is Hausdorff, it follows that $x = f^k(x)$ . Hence, the point x is periodic and therefore belongs to $\Omega (f)$ .

Consider now the second case, where $\nu $ is unbounded. Let $m \geq 1$ be an integer. We will show that $x \in f^m(X)$ . Take $E_0 \in \mathcal {E}$ so that $\nu (E_0) \geq m$ . Let $E \in \mathcal {E}$ . Choose a symmetric entourage $S \in \mathcal {E}$ such that

$$ \begin{align*} \underbrace{S \circ S \circ \cdots \circ S}_{m\ {\tiny \mathrm{times}}} \subset E. \end{align*} $$

As in the first case, we can find a symmetric entourage $T \in \mathcal {E}$ such that $T \subset E_0$ and $(f^p(y),f^p(z)) \in S$ whenever $(y,z) \in T$ and $0 \leq p \leq m$ . Observe that since $T \subset E_0$ . By definition of $\nu $ , we can find a sequence of points $x_0, x_1, \ldots , x_{n} \in X$ such that $x =x_0=x_n$ and $(f(x_i), x_{i+1}) \in T$ for all $0 \leq i \leq n -1$ . Looking now at the sequence of points $f^m(x_{n - m}),f^{m - 1}(x_{n - m + 1}), \ldots , f(x_{n - 1}), x_n = x$ , and using the fact that, for all $0 \leq i \leq m -1$ , we have

$$ \begin{align*} & (f^{m - i}(x_{n - m + i}), f^{m - i - 1}(x_{n - m + i + 1})) \\ &\quad = (f^{m - i - 1}(f(x_{n - m + i})), f^{m - i - 1}(x_{n - m + i + 1})) \in S \end{align*} $$

since $(f(x_{n - m + i})),x_{n - m + i + 1}) \in T$ , we see that

$$ \begin{align*} (f^m(x_{n - m}), x) \in \underbrace{S \circ S \circ \cdots \circ S}_{m\ {\tiny \mathrm{times}}} \subset E. \end{align*} $$

As the entourage $E \in \mathcal {E}$ was arbitrary, it follows that x belongs to the closure of $f^m(X)$ . Since $f^m(X)$ is closed in X by our hypothesis, we conclude that $x \in f^m(X)$ for every $m \geq 1$ . This shows that $x \in \Omega (f)$ .

Using the fact that the topology of any compact Hausdorff space is induced by a unique uniform structure, an immediate consequence of Proposition 2.3 is the following well-known result (see e.g. [37, Ch. 6]).

Corollary 2.4. Let X be a compact Hausdorff space and let $f \colon X \to X$ be a continuous map. Then $\operatorname {\mathrm {CR}}(f) \subset \Omega (f)$ .

2.4 Subshifts of sub-finite-type

Let G be a group and let A be a set. A subshift $\Sigma \subset A^G$ is called a subshift of sub-finite-type if it is a factor of a subshift of finite type (cf. (1.1)), namely, there exist a set B, a cellular automaton $\tau ' \colon B^G \to A^G$ , and a subshift of finite type $\Sigma ' \subset B^G$ such that $\Sigma = \tau '(\Sigma ')$ . Note that we do not require $\Sigma $ to be closed in $A^G$ . In the following, every finite subset D of G containing a defining memory set of $\Sigma '$ as well as a memory set of $\tau '$ will be called a memory set of the subshift of sub-finite-type $\Sigma $ . The existence of such a memory set will be necessary for the restriction technique (cf. §§2.5 and 2.6) when the group G is not finitely generated.

Example 2.5. If G is a group, V is an algebraic variety over a field K, and , then it immediately follows from Definition 1.2 in §1 that every algebraic sofic subshift $\Sigma \subset A^G$ is a subshift of sub-finite-type of $A^G$ .

In the rest of the paper, a memory set of an algebraic sofic subshift $\Sigma $ will mean any memory set of $\Sigma $ regarded as a subshift of sub-finite-type.

Example 2.6. Let A be a set and let $\Gamma $ be an A-labeled directed graph. This means that $\Gamma $ is a quintuple $\Gamma = (V,E,\alpha ,\omega ,\unicode{x3bb} )$ , where $V,E$ are sets, and $\alpha ,\omega \colon E \to V$ , $\unicode{x3bb} \colon E \to A$ are maps. The elements of V are called the vertices of $\Gamma $ , those of E are called its edges, and, for every edge $e \in E$ , the vertex $\alpha (e)$ (respectively $\omega (e))$ is called the initial (respectively terminal) vertex of e while $\unicode{x3bb} (e)$ is called its label. The label of a configuration $x \in E^{\mathbb {Z}}$ is the configuration $\Lambda (x) \in A^{\mathbb {Z}}$ defined by $\Lambda (x)(n) = \unicode{x3bb} (x(n))$ for all $n \in \mathbb {Z}$ . Observe that $\Lambda \colon E^{\mathbb {Z}} \to A^{\mathbb {Z}}$ is a cellular automaton admitting as a memory set and $\unicode{x3bb} \colon E^M = E \to A$ as the associated local defining map. An element $x \in E^{\mathbb {Z}}$ is called a path of $\Gamma $ if it satisfies $\omega (x(n)) = \alpha (x(n+1))$ for all $n \in \mathbb {Z}$ . Clearly, the subset $\Sigma ' \subset E^{\mathbb {Z}}$ consisting of all paths of $\Gamma $ is the subshift of finite type $\Sigma (D,P)$ of $E^{\mathbb {Z}}$ , where and . One says that $\Sigma '$ is the Markov shift associated with the unlabeled graph $(V,E,\alpha ,\omega )$ (cf. [28, Ch. 7]). We deduce that is a subshift of sub-finite-type of $A^{\mathbb {Z}}$ . Conversely, it can be shown that every subshift of sub-finite-type of $A^{\mathbb {Z}}$ can be obtained, up to topological conjugacy, as the set of labels of the paths of a suitably chosen A-labeled graph. The proof of this last result is, mutatis mutandis, the one used in the classical setting for showing that every sofic finite alphabet subshift over $\mathbb {Z}$ can be presented by a finite labeled graph (see e.g. [30, Theorem 3.2.1]).

The following result says that the notion of subshifts of sub-finite-type is only interesting when G is not finitely generated.

Proposition 2.7. Let G be a finitely generated group and let A be a set. Then every subshift $\Sigma \subset A^G$ is a subshift of sub-finite-type.

Proof. Let D be a finite generating subset of G such that $1_G \in D$ and $D=D^{-1}$ . Let ${\Sigma \subset A^G}$ be a subshift. Let and define . Consider the subshift of finite type of $B^G$ . Since $D=D^{-1}$ generates G and contains $1_G$ , the map $\mathfrak {X} \mapsto \mathfrak {X}(1_G)$ is a bijection from $\Sigma '$ onto $\Sigma $ . Indeed, for every $g \in G$ and $\mathfrak {X} \in \Sigma '$ , by writing $g= s_1 \cdots s_n$ for some $s_1, \ldots , s_n \in D$ , we find that

$$ \begin{align*} \mathfrak{X}(g) = \mathfrak{X}(s_1 \cdots s_n) = s_1^{-1} \mathfrak{X}(s_2 \cdots s_n) = \cdots = s_n^{-1} \cdots s_1^{-1} (\mathfrak{X}(1_G)) = g^{-1} \mathfrak{X}(1_G). \end{align*} $$

Let $\tau \colon B^G \to A^G$ be the cellular automaton with memory set $\{1_G\}$ and associated local defining map $\mu \colon B \to A$ given by $x \mapsto x(1_G)$ . In other words, $\tau (\mathfrak {X})(g) = (\mathfrak {X}(g))(1_G)$ for every $\mathfrak {X} \in B^G$ and $g \in G$ . Hence, for every $\mathfrak {X} \in \Sigma '$ , we have $\tau (\mathfrak {X}) = \mathfrak {X}(1_G)$ since for all $g \in G$ ,

$$ \begin{align*} \tau(\mathfrak{X}) (g) =(\mathfrak{X}(g))(1_G) = (g^{-1} (\mathfrak{X}(1_G)) )(1_G) = (\mathfrak{X}(1_G))(g). \end{align*} $$

As $\mathfrak {X}(1_G) \in B= \Sigma $ is arbitrary, we conclude that $\Sigma =\tau (\Sigma ')$ is a subshift of sub- finite-type.

2.5 Restriction of cellular automata and of subshifts of sub-finite-type

Let G be a group and let A be a set. Let $\Sigma \subset A^G$ be a subshift of sub-finite-type. Hence, there exist a set B, a cellular automaton $\tau ' \colon B^G \to A^G$ , and a subshift of finite type $\Sigma ' \subset B^G$ such that $\Sigma = \tau '(\Sigma ')$ . Let $D \subset G$ be a finite subset such that D is a defining memory set of $\Sigma '$ as well as a memory set of $\tau '$ . Let $H\subset G$ be a subgroup of G containing D. Denote by the set of all right cosets of H in G. As the right cosets of H in G form a partition of G, we have natural factorizations

$$ \begin{align*} A^G = \prod_{c \in G/H} A^c, \quad B^G = \prod_{c \in G/H} B^c \end{align*} $$

in which each $x \in A^G$ (respectively $x \in B^G$ ) is identified with $ (x\vert _c)_{c \in G/H} \in \prod _{c \in G/H} A^c$ (respectively $(x\vert _c)_{c \in G/H} \in \prod _{c \in G/H} B^c$ ). Since $g D \subset gH$ for every $g \in G$ , the above factorization of $B^G$ induces a factorization

$$ \begin{align*} \Sigma' = \prod_{c \in G/H} \Sigma^{\prime}_c, \end{align*} $$

where $\Sigma ^{\prime }_c = \{x\vert _c \colon x \in \Sigma '\}$ for all $c \in G/H$ . Likewise, for each $c \in G/H$ , let ${\Sigma _c = \{x\vert _c \colon x \in ~\Sigma \}}$ .

Lemma 2.8. The factorization $A^G = \prod _{c \in G/H} A^c$ induces a factorization

$$ \begin{align*} \Sigma = \prod_{c \in G/H} \Sigma_c. \end{align*} $$

Proof. Since H contains a memory set of $\tau '$ , we have $\tau ' = \prod _{c \in G/H} \tau ^{\prime }_c$ , where ${\tau ^{\prime }_c \colon B^c \to A^c}$ is given by for all $y \in B^c$ , where $x \in B^G$ is any configuration extending y. We deduce that $\Sigma _c = (\tau '( \Sigma '))_c = \tau ^{\prime }_c(\Sigma ^{\prime }_c)$ for every $c \in G/H$ . Hence,

$$ \begin{align*} \Sigma = \tau'(\Sigma') = \tau' \bigg( \prod_{c \in G/H} \Sigma^{\prime}_c \bigg) = \prod_{c \in G/H} \tau^{\prime}_c(\Sigma^{\prime}_c) = \prod_{c \in G/H} \Sigma_c.\\[-48pt] \end{align*} $$

Let $T \subset G$ be a complete set of representatives for the right cosets of H in G such that $1_G \in T$ . Then, for each $c \in G/H$ , we have a uniform homeomorphism $\phi _c \colon \Sigma _c \to \Sigma _H$ given by $\phi _c(y)(h) = y(gh)$ for all $y \in \Sigma _c$ , where $g \in T$ represents c. In particular, $\Sigma \neq \varnothing $ if and only if $\Sigma _H \neq \varnothing $ .

Now suppose in addition that $\tau \colon \Sigma \to \Sigma $ is a cellular automaton which admits a memory set contained in H. Then we have $\tau = \prod _{c \in G/H} \tau _c$ , where $\tau _c \colon \Sigma _c \to \Sigma _c$ is defined by setting for all $y \in \Sigma _c$ , where $x \in \Sigma $ is any configuration extending y. Note that for each $c \in G/ H$ , the maps $\tau _c$ and $\tau _H$ are conjugate by $\phi _c$ , that is, we have $\tau _c = \phi _c^{-1} \circ \tau _H \circ \phi _c$ . This allows us to identify the action of $\tau _c$ on $\Sigma _c$ with that of the restriction cellular automaton $\tau _H$ on $\Sigma _H$ . See 9 and [10, Section 1.7].

Lemma 2.9. The following hold:

1. (i) $\Omega (\tau ) = \Omega (\tau _H)^{G/H}$ ;

2. (ii) $\tau $ is nilpotent if and only if $\tau _H$ is nilpotent.

Proof. Observe that the map $x \mapsto (\phi _c(x\vert _c))_{c \in G/H}$ yields a bijection $\Omega (\tau ) \to \prod _{c \in G/H} \Omega (\tau _H) = \Omega (\tau _H)^{G/H}$ , and this proves point (i). Point (ii) is clear by the above discussion.

2.6 Restriction and the closed image property

Let G be a group and let $A, B$ be sets. Let $\Sigma \subset A^G$ be a subshift of sub-finite-type and let now $\tau \colon A^G \to B^G$ be a cellular automaton whose source and domain are the full shifts $A^G$ and $B^G$ , respectively. Let $H\subset G$ be a subgroup of G containing a memory set of $\Sigma $ and a memory set of $\tau $ . As in §2.5, we have the factorizations $\Sigma = \prod _{c \in G/H} \Sigma _c$ (cf. Lemma 2.8) and $\tau = \prod _{c \in G/H} \tau _c$ , with $\tau _c \colon A^c \to B^c$ defined by for all $y \in A^c$ , where $x \in A^G$ is any configuration extending y.

Lemma 2.10. The set $\tau (\Sigma )$ is closed in $B^G$ if and only if $\tau _H(\Sigma _H)$ is closed in $B^H$ .

Proof. We have $\tau (\Sigma )= \prod _{c \in G/H} \tau _c(\Sigma _c)$ . It is immediate that $\tau _H(\Sigma _H)$ is closed in $B^H$ if $\tau (\Sigma )$ is closed in $B^G$ . For the converse implication, we have for every $c \in G/H$ a uniform homeomorphism $\psi _c \colon B^c \to B^H$ by fixing a complete set containing $1_G$ of representatives for the right cosets of H in G (cf. §2.5). Thus, if $\tau _H(\Sigma _H)$ is closed, then so is ${\tau _c(\Sigma _c) = \psi _c^{-1}(\tau _H(\Sigma _H))}$ . Consequently, $\tau (\Sigma )$ is closed in $B^G$ whenever $\tau _H(\Sigma _H)$ is closed in $B^H$ since the product of closed subspaces is closed in the product topology.

3 Inverse limits of countably pro-constructible sets

Let I be a directed set, that is, a partially ordered set in which every pair of elements admits an upper bound. An inverse system of sets indexed by I consists of the following data: (1) a set $Z_i$ for each $i \in I$ ; (2) a transition map $\varphi _{ij} \colon Z_j \to Z_i$ for all $i,j \in I$ such that $i \prec j$ . Furthermore, the transition maps must satisfy the following conditions:

$$ \begin{align*} \varphi_{ii} &= \operatorname{\mathrm{Id}}_{Z_i}\quad \text{(the identity map on}\ Z_i)\ \text{for all } i \in I, \\\varphi_{ij} \circ \varphi_{jk} &= \varphi_{ik}\quad \text{for all}\ i,j,k \in I\ \text{such that } i \prec j \prec k. \end{align*} $$

One then speaks of the inverse system $(Z_i,\varphi _{ij})$ , or simply $(Z_i)$ if the index set and the transition maps are clear from the context.

The inverse limit of an inverse system $(Z_i,\varphi _{i j})$ is the subset

$$ \begin{align*} \varprojlim_{i \in I} (Z_i,\varphi_{i j}) = \varprojlim_{i \in I} Z_i \subset \prod_{i \in I} Z_i \end{align*} $$

consisting of all $(z_i)_{i \in I}$ such that $\varphi _{i j}(z_j)= z_i$ for all $i \prec j$ .

A subset of a topological space X is said to be locally closed if it is the intersection of a closed subset and an open subset of X. It is said to be constructible if it is a finite union of locally closed subsets of X. It is said to be proconstructible if it is the intersection of a family of constructible subsets [22, Définition I.9.4]. We shall say that a subset of X is countably proconstructible if it is the intersection of a countable family of constructible subsets. It is clear that every countably proconstructible subset can be written as the intersection of a decreasing sequence of constructible subsets.

The following lemma is analogous to [39, Lemma 4.1].

Lemma 3.1. Let K be an uncountable algebraically closed field and let $f \colon X \to Y$ be an algebraic morphism of algebraic varieties over K. If $(C_k)_{k \in \mathbb {N}}$ is a decreasing sequence of constructible subsets of X, then

$$ \begin{align*} f \bigg( \bigcap_{k \in \mathbb{N}} C_k(K) \bigg) = \bigcap_{k \in \mathbb{N}} f(C_k(K)) = \bigcap_{k \in \mathbb{N}} f(C_k)(K). \end{align*} $$

Proof. Since for each $k \in \mathbb {N}$ we have $f(C_k(K))= f(C_k)(K)$ (cf. for example [14, Lemma A.22(v)]), the second equality is verified. For the first equality, we have trivially $f ( \bigcap _{k \in \mathbb {N}} C_k(K) ) \subset \bigcap _{k \in \mathbb {N}} f(C_k(K))$ . Conversely, assume that $y \in \bigcap _{k \in \mathbb {N}} f(C_k(K))$ . For each $k \in \mathbb {N}$ , set

Note that $F_k$ is the set of closed points of a constructible subset of X. Remark also that, for every $k \in \mathbb {N}$ , we have $F_{k+1} \subset F_k$ and $F_k \not = \varnothing $ . Hence, by [14, Lemma B.3], there exists $x \in \bigcap _{k \in \mathbb {N}} F_k$ . Clearly, $f(x)=y$ and $x \in \bigcap _{k \in \mathbb {N}} C_k(K)$ . Therefore, $ \bigcap _{k \in \mathbb {N}} f(C_k(K)) \subset f ( \bigcap _{k \in \mathbb {N}} C_k(K) )$ and the proof is completed.

In case (H1), we shall make use of the following generalization of [14, Lemma B.2] to countable inverse systems of countably proconstructible subsets.

Lemma 3.2. Let K be an uncountable algebraically closed field. Let $(X_i, f_{ij})$ be an inverse system indexed by a countable directed set I, where each $X_i$ is a K-algebraic variety and each transition map $f_{i j} \colon X_j \to X_i$ is an algebraic morphism. Suppose given, for each $i \in I$ , a non-empty countably proconstructible subset $C_i \subset X_i$ . Let $Z_i= C_i(K)$ and assume that $f_{ij}(Z_j)\subset Z_i$ for all $i\prec j$ in I. Then the inverse system $(Z_i,\varphi _{i j})_I$ , where $\varphi _{i j} \colon Z_j \to Z_i$ is the restriction of $f_{i j}$ to $Z_j$ , verifies $\varprojlim _{i \in I} Z_i \neq \varnothing $ .

Proof. Since I is a countable directed set, we can find a totally ordered cofinal subset ${\{i_n : n \in \mathbb {N}\} \subset I}$ . As $\varprojlim _{n \in \mathbb {N}} Z_{i_n} = \varprojlim _{i \in I} Z_i$ , we can suppose, without any loss of generality, that $I= \mathbb {N}$ .

For each $i \in \mathbb {N}$ , we can find a decreasing sequence of constructible subsets $(C_{ik})_{k \in \mathbb {N}}$ of $X_i$ such that $C_i= \bigcap _{k \in \mathbb {N}} C_{ik}$ . For $k \in \mathbb {N}$ , let $Z_{ik}= C_{ik}(K)$ . By Lemma 3.1, we have for every $i \leq j$ :

(3.1) $$ \begin{align} Z_i= \bigcap_{k = 0}^{\infty} Z_{ik} \neq \varnothing, \quad f_{ij}(Z_j) = \bigcap_{k=0}^{\infty} f_{ij} (Z_{jk}). \end{align} $$

Consider the universal inverse system $(Z^{\prime }_i, \varphi ^{\prime }_{ij})_{i,j \in \mathbb {N}}$ of the system $(Z_i, \varphi _{ij})_{i,j \in \mathbb {N}}$ , that is, for every $i \in \mathbb {N}$ , let

and let the maps $\varphi ^{\prime }_{ij} \colon Z^{\prime }_{j} \to Z^{\prime }_i$ be the restrictions of $\varphi _{ij} \colon Z_j \to Z_i$ .

Remark that $\varprojlim _{i \in \mathbb {N}} Z^{\prime }_i= \varprojlim _{i \in \mathbb {N}} Z_i$ . Hence, it suffices to check that the sets $Z^{\prime }_i$ are non-empty and the transition maps $\varphi ^{\prime }_{ij}$ are surjective for all $i \leq j$ . By equation (3.1), Chevalley’s theorem (see for example [57, Theorem 7.4.2], [22, Théorème I.8.4]) implies that each $Z^{\prime }_i$ is a countable intersection of constructible sets:

$$ \begin{align*} Z^{\prime}_i = \bigcap_{j=i}^\infty f_{ij}(Z_{j}) = \bigcap_{j = i}^\infty \bigcap_{k=0}^\infty f_{ij} (Z_{jk}). \end{align*} $$

For each $n \geq i$ , consider the diagonal set

By Chevalley’s theorem, $Y_n$ is a constructible subset of $X_i(K)$ . For every $n \geq i$ , we have $Y_{n+1} \subset Y_n$ and since $Z_n \ne \varnothing $ ,

(3.2) $$ \begin{align} Y_n \supset \bigcap_{j=i}^n \bigcap_{k = 0}^\infty f_{ij}(Z_{jk}) = \bigcap_{j=i}^n f_{ij} (Z_j) \supset f_{in}(Z_n) = \varphi_{in}(Z_n) \neq \varnothing. \end{align} $$

As $Z^{\prime }_i = \bigcap _{n=i}^\infty Y_n$ , [14, Lemma B.2] implies that $Z^{\prime }_i \neq \varnothing $ for $i \in \mathbb {N}$ . Now let $k, i \in \mathbb {N}$ with $k \leq i$ and let $z \in Z^{\prime }_k$ . For each $n \geq i$ , by definition of $Z^{\prime }_k$ , there exists $y \in Z_n$ such that $\varphi _{k n}(y)=z$ and thus

(3.3) $$ \begin{align} \varphi_{i n}(y)\in \varphi_{k i}^{-1} (z) \cap \varphi_{i n} (Z_n) \neq \varnothing. \end{align} $$

By equations (3.2), (3.3), and for $n \geq i$ , the constructible subset

(3.4)

is non-empty and $T_{n+1} \subset T_n$ as $Y_{n+1} \subset Y_n$ . Finally, we find that

$$ \begin{align*} (\varphi_{k i}')^{-1} (z) & = \varphi_{k i}^{-1} (z) \cap Z^{\prime}_i = \bigcap_{n=i}^\infty \varphi_{k i}^{-1} (z) \cap Y_n = \bigcap_{n=i}^\infty T_n \end{align*} $$

is non-empty by [14, Lemma B.2]. The proof is thus completed.

We shall apply repeatedly the following result in cases (H2)–(H3).

Lemma 3.3. Let K be an algebraically closed field. Let $(X_i, f_{ij})$ be an inverse system indexed by a countable index set I, where each $X_i$ is a non-empty K-algebraic variety and each transition map $f_{i j} \colon X_j \to X_i$ is an algebraic morphism such that $f_{ij}(X_j) \subset X_i$ is a closed subset for all $i \prec j$ . Then $\varprojlim _{i \in I} X_i(K) \neq \varnothing $ .

Proof. The statement is proved in [39, Proposition 4.2].

4 Space-time inverse systems

Let G be a finitely generated group and let A be a set. Let $\Sigma \subset A^G$ be a closed subshift and assume that $\tau \colon \Sigma \to \Sigma $ is a cellular automaton. Let $\widetilde {\tau } \colon A^G \to A^G$ be a cellular automaton extending $\tau $ .

Let $M\subset G$ be a memory set of $\widetilde {\tau }$ . Since every finite subset of G containing a memory set of $\widetilde {\tau }$ is itself a memory set of $\widetilde {\tau }$ , we can choose M such that $1_G \in M$ , $M = M^{-1}$ , and M generates G. Note that this implies in particular that the sequence $(M^n)_{n \in \mathbb {N}}$ is an exhaustion of G, that is:

1. (Mem1) $M^{n+1} \supset M^n$ for all $n \in \mathbb {N}$ ; and

2. (Mem2) $\bigcup _{n \in \mathbb {N}} M^n = G$ .

Equip $\mathbb {N}^2$ with the product ordering $\prec $ . Thus, given $i,j,k,l \in \mathbb {N}$ , we have $(i,j) \prec (k,l)$ if and only if $i \leq k$ and $j \leq l$ .

We construct an inverse system $(\Sigma _{i j})_{i,j \in \mathbb {N}}$ indexed by the directed set $(\mathbb {N}^2, \prec )$ in the following way.

First, given $i,j \in \mathbb {N}$ , we define $\Sigma _{i j}$ as being the set consisting of the restrictions to $M^{i + j}$ of all the configurations that belong to $\Sigma $ , that is,

To define the transition maps $\Sigma _{k l} \to \Sigma _{i j}$ ( $(i,j) \prec (k,l)$ ) of the inverse system $(\Sigma _{ij})_{i,j \in \mathbb {N}}$ , it is clearly enough to define, for all $i,j \in \mathbb {N}$ , the unit-horizontal transition map $p_{i j} \colon \Sigma _{i+1, j} \to \Sigma _{i j}$ , the unit-vertical transition map $q_{i j} \colon \Sigma _{i,j+1} \to \Sigma _{i j}$ , and verify that the diagram

is commutative, that is,

(4.1) $$ \begin{align} q_{i j} \circ p_{i,j+1} = p_{i j} \circ q_{i+1,j} \quad \text{ for all } i,j \in \mathbb{N}. \end{align} $$

We define $p_{i j}$ as being the map obtained by restriction to $M^{i + j} \subset M^{i + j + 1}$ . Thus for all $\sigma \in \Sigma _{i + 1,j}$ , we have

(4.2) $$ \begin{align} p_{i j}(\sigma) = \sigma\vert_{M^{i + j}}. \end{align} $$

To define $q_{i j}$ , we first observe that, given $x \in \Sigma $ and $g \in G$ , it follows from equation (1.2) applied to $\widetilde {\tau }$ that $\tau (x)(g)$ only depends on the restriction of x to $gM$ . As $gM \subset M^{i + j + 1}$ for all $g \in M^{i + j}$ , we deduce from this observation that, given $\sigma \in \Sigma _{i,j + 1}$ and $x \in \Sigma $ extending $\sigma $ , the formula

(4.3)

yields a well-defined element $q_{i j}(\sigma ) \in \Sigma _{i j}$ and hence a map $q_{i j} \colon \Sigma _{i,j+1} \to \Sigma _{i j}$ .

To check that equation (4.1) is satisfied, let $\sigma \in \Sigma _{i+1,j+1}$ and choose a configuration ${x \in \Sigma }$ extending $\sigma $ . By applying equation (4.2), we see that $p_{i,j+1}(\sigma ) = x\vert _{M^{i + j + 1}}$ . Therefore, using equation (4.3), we get

(4.4) $$ \begin{align} q_{i j} \circ p_{i,j+1} (\sigma) = q_{i j} ( p_{i,j+1}(\sigma)) = q_{i j} (x\vert_{M^{i + j + 1}}) = (\tau(x))\vert_{M^{i + j}}. \end{align} $$

However, by applying again equation (4.3), we see that $q_{i+1,j} (\sigma ) = (\tau (x))\vert _{M^{i + j + 1}}$ . Therefore, using equation (4.2), we get

(4.5) $$ \begin{align} p_{i j} \circ q_{i+1,j} (\sigma) = p_{i j} ( q_{i+1,j} (\sigma)) = p_{i j} ((\tau(x))\vert_{M^{i + j + 1}}) = (\tau(x))\vert_{M^{i + j }}. \end{align} $$

We deduce from equations (4.4) and (4.5) that $q_{i j} \circ p_{i,j+1} (\sigma ) = p_{i j} \circ q_{i+1,j} (\sigma ) $ for all $\sigma \in \Sigma _{i + 1,j + 1}$ . This shows equation (4.1).

Definition 4.1. The inverse system $(\Sigma _{ij})_{i,j \in \mathbb {N}}$ is called the space-time inverse system associated with the triple $(\Sigma ,\tau ,M)$ .

It might be useful to consider the inverse system $(\Sigma _{ij})_{i,j \in \mathbb {N}}$ as a refined diagram of the space-time evolution of the cellular automaton $\tau $ that in addition keeps track of the local dynamics. Comparing to the usual space-time diagram of a classical cellular automaton introduced in [61], in [34], or recently in [19], the main difference of our construction is the following. First, the horizontal direction indexed by $i \in \mathbb {N}$ in our space-time inverse system represents the extension of the ambient spaces of $1_G$ instead of the exact position in the universe G as in the classical diagram. Second, the vertical direction indexed by $j \in \mathbb {N}$ represents the past instead of the future. More precisely, let us fix $i \in \mathbb {N}$ and consider the induced inverse subsystem $(\Sigma _{ij})_{j \in \mathbb {N}}$ lying above $\Sigma _{i0}= \Sigma _{M^i}$ . Then each $(\Sigma _{ij})_{j \in \mathbb {N}}$ should be regarded as an approximation of the past light cone of the events happening in $M^i$ , that is, of configurations $\sigma \in \Sigma _{M^i}$ .

Remark 4.2. Observe that the inverse system $(\Sigma _{i j})_{i,j \in \mathbb {N}}$ is a subsystem of the full inverse system $(A^{M^{i + j}})_{i,j \in \mathbb {N}}$ associated with the triple $(A^G,\widetilde {\tau },M)$ . In the following, we shall denote by $\widetilde {p} _{ij}\colon A^{M^{i+j+1}} \to A^{M^{i+j}}$ (respectively $\widetilde {q}_{ij} \colon A^{M^{i+j+1}} \to A^{M^{i+j}}$ ) the unit horizontal (respectively vertical) transition maps of the full inverse system $(A^{M^{i + j}})_{i,j \in \mathbb {N}}$ .

Remark 4.3. For the hypotheses (H1), (H2), and (H3) in §1, we have the following easy but useful remark. If $A=V(K)$ for some algebraic variety V over an algebraically closed field K and if $\widetilde {\tau } \colon A^G \to A^G$ is an algebraic (respectively algebraic group) cellular automaton, then the transition maps of the full inverse system $(A^{M^{i + j}})_{i,j \in \mathbb {N}}$ are algebraic morphisms (respectively homomorphisms of algebraic groups).

If we fix $j \in \mathbb {N}$ in our space-time inverse system, we get a horizontal inverse system $(\Sigma _{i j})_{i \in \mathbb {N}}$ indexed by $\mathbb {N}$ whose transition maps are the restriction maps $p_{i j} \colon \Sigma _{i + 1,j} \to ~\Sigma _{i j}$ , $i \in \mathbb {N}$ . It immediately follows from the closedness of $\Sigma $ in $A^G$ and properties (Mem1)–(Mem2) that the limit

(4.6)

can be identified with $\Sigma $ in a canonical way. Moreover, the maps $q_{i j} \colon \Sigma _{i, j + 1} \to \Sigma _{i j}$ define an inverse system morphism from the inverse system $(\Sigma _{i, j + 1})_{i \in \mathbb {N}}$ to the inverse system $(\Sigma _{i j})_{i \in \mathbb {N}}$ . This yields a limit map $\tau _j \colon \Sigma _{j + 1} \to \Sigma _j$ . Using the identifications $\Sigma _{j + 1} = \Sigma _j = \Sigma $ , we have $\tau _j = \tau $ for all $j \in \mathbb {N}$ . We deduce that the limit

(4.7) $$ \begin{align} \varprojlim_{i,j \in \mathbb{N}} \Sigma_{ij} = \varprojlim_{j \in \mathbb{N}} \Sigma_{j} \end{align} $$

is the set of backward orbits (or complete histories [34]) of $\tau $ , that is, the set consisting of all sequences $(x_j)_{j \in \mathbb {N}}$ such that $x_j \in \Sigma $ and $x_j = \tau (x_{j+1})$ for all $j \in \mathbb {N}$ . Such a sequence satisfies $x_0 = \tau ^n(x_n)$ for all $n \in \mathbb {N}$ and hence $x_0 \in \Omega (\tau )$ . Thus, we obtain the following result.

Lemma 4.4. We have a canonical map $\Phi \colon \varprojlim _{i,j \in \mathbb {N}} \Sigma _{ij} \to \Omega (\tau )$ . In particular, we have that

$$ \begin{align*} \varprojlim_{i,j \in \mathbb{N}} \Sigma_{ij} \neq \varnothing \implies \Omega(\tau) \neq \varnothing. \end{align*} $$

We will see that the map $\Phi \colon \varprojlim _{i,j \in \mathbb {N}} \Sigma _{ij} \to \Omega (\tau )$ is surjective in the algebraic setting (cf. Theorem 9.1). Therefore, in this case, every limit configuration $x \in \Omega (\tau )$ admits a backward orbit and $\tau (\Omega (\tau )) = \Omega (\tau )$ .

5 Approximation of subshifts of finite type

In this section, keeping all the notation and hypotheses introduced in the previous section, we assume in addition that $\Sigma $ is a subshift of finite type. We fix a finite subset $D \subset G$ and a subset $P \subset A^D$ such that $\Sigma = \Sigma (D, P)$ (cf. equation (1.1)). We begin with a useful observation.

Lemma 5.1. For every finite subset $E \subset G$ such that $D \subset E$ , we have $\Sigma = \Sigma (D, P) = \Sigma (E, \Sigma _E)$ .

Proof. Let $x \in \Sigma $ and $g \in G$ , then clearly $(g^{-1}x) \vert _E \in \Sigma _E$ . Thus, $\Sigma \subset \Sigma (E, \Sigma _E)$ . Conversely, let $x \in \Sigma (E, \Sigma _E)$ and $g \in G$ , then $(g^{-1}x)\vert _D = ((g^{-1}x)\vert _E)\vert _D\in (\Sigma _E)_D \subset P$ since $D \subset E$ . Therefore, $x \in \Sigma (D,P)=\Sigma $ and the conclusion follows.

For all $i, j \in \mathbb {N}$ , we define and

Remark that $\Sigma _{ij} \subset A_{ij}$ . Indeed, we have

$$ \begin{align*} \Sigma_{ij} & = \{ x \in A^{M^{i+j}} \colon \text{ there exists } y \in A^G, x = y \vert_{M^{i+j}}, (g^{-1} y)\vert_{D} \in P \text{ for all } g \in G\} \\ & \subset \{ x \in A^{M^{i+j}} \colon \text{ there exists } y \in A^G, x = y \vert_{M^{i+j}}, (g^{-1} y)\vert_{D} \in P \text{ for all } g \in D_{ij}\} \\ &= \{ x \in A^{M^{i+j}} \colon (g^{-1} x)\vert_D \in P \text{ for all } g\in D_{ij} \} \\ & = A_{ij}. \end{align*} $$

Remark also that for all $(i, j) \prec (k, l)$ in $\mathbb {N}^2$ , we have $D_{ij} \subset D_{kl}$ because $M^{i+j} \subset M^{k+l}$ by property (Mem1).

For $i,j,k \in \mathbb {N}$ such that $i \leq k$ , consider the canonical projection

(5.1) $$ \begin{align} \widetilde{p}_{ijk} \colon A^{M^{k+j}} \to A^{M^{i+j}}, \quad x \mapsto x\vert_{M^{i+j}}. \end{align} $$

Clearly, $\widetilde {p}_{ijk}(A_{k j}) \subset A_{ij}$ since $D_{ij} \subset D_{k+j}$ . We thus obtain well-defined projection maps

(5.2) $$ \begin{align} p_{ijk} \colon A_{k j} \to A_{ij}, \end{align} $$

which extend the horizontal transition maps $\Sigma _{k j} \to \Sigma _{ij}$ of the space-time inverse system $(\Sigma _{ij})_{i,j \in \mathbb {N}}$ associated with $\tau \colon \Sigma \to \Sigma $ and the memory set M.

Remark 5.2. In general, $(A_{ij})_{i,j \in \mathbb {N}}$ is not a subsystem of the space-time inverse system $(A^{M^{i+j}})_{i, j \in \mathbb {N}}$ associated with $(A^G,\widetilde {\tau },M)$ (cf. Remark 4.2). There is no trivial reason for $\widetilde {q}_{ij}(A_{i,j+1}) \subset A_{ij}$ unless $\Sigma $ is the full shift.

The following lemma says that each row of the system $(A_{ij}, p_{ijk})_{i,j,k \in \mathbb {N}}$ gives us an approximation of $\Sigma $ .

Lemma 5.3. For every $j \in \mathbb {N}$ , there is a canonical bijection

$$ \begin{align*} \Psi_j \colon \Sigma \to \varprojlim_{i \in \mathbb{N}} (A_{i j}, p_{i j k}). \end{align*} $$

Proof. Since $\Sigma _{i j} \subset A_{ij}$ for all $i, j\in \mathbb {N}$ , each $x \in \Sigma $ defines naturally an element $\Psi _j(x) = (x\vert _{M^{i+j}})_{i \in \mathbb {N}}\in \varprojlim _{i \in \mathbb {N}} (A_{ij}, p_{ijk})$ . Conversely, let $(x_i)_{i \in \mathbb {N}} \in \varprojlim _{i \in \mathbb {N}} (A_{ij}, p_{ijk})$ . Define $x \in ~A^G$ by setting, for each $g \in G$ , for any $i \in \mathbb {N}$ large enough such that $g \in M^{i + j}$ . The fact that the configuration $x \in A^G$ is well defined follows from properties (Mem1) and (Mem2). Let $g \in G$ . Take i large enough so that $g D \subset M^{i + j}$ . Then $g \in D_{i j}$ and $(g^{-1} x)\vert _D = (g^{-1} x_i)\vert _D \in P$ since $x_i \in A_{i j}$ . This shows that $x \in \Sigma $ .

Lemma 5.4. For all $i, j \in \mathbb {N}$ , we have

$$ \begin{align*} \Sigma_{ij} \subset \bigcap_{k \geq i} p_{i j k}(A_{k j}). \end{align*} $$

Proof. Let $y \in \Sigma $ and let $x= y\vert _{M^{i+j}} \in \Sigma _{ij}$ . Let $k \geq i$ . Since $y\vert _{M^{k+j}} \in \Sigma _{M^{k+j}} \subset A_{k j}$ , it follows that

$$ \begin{align*} x = y\vert_{M^{i+j}} = p_{ijk}(y\vert_{M^{k+j}}) \subset p_{ijk}(A_{k j}). \end{align*} $$

As y is arbitrary, the proof is finished.

6 Algebraic subshifts of finite type

Keeping the notation and hypotheses of §5, we assume in this section that $A=V(K)$ and $P=W(K)$ , where V is an algebraic variety over an algebraically closed field K and $W \subset V^D$ is an algebraic subvariety. Thus, $\Sigma =\Sigma (D, P) \subset A^G$ is an algebraic subshift of finite type.

For all $i, j \in \mathbb {N}$ , it is clear that $A_{ij}$ is a closed algebraic subset of $A^{M^{i+j}}$ since it is a finite intersection of sets of closed points of closed subvarieties of $V^{M^{i+j}}$ :

(6.1) $$ \begin{align} A_{ij} = \bigcap_{g \in D_{ij}} \pi_{ij,g}^{-1} (gW) (K). \end{align} $$

Here, $\pi _{ij,g} \colon V^{M^{i+j}} \to V^{gD}$ is the projection induced by the inclusion $gD \subset M^{i+j}$ for $g \in D_{ij}$ . The subset $gW \subset V^{gD}$ is defined as the image of W under the isomorphism $V^D \simeq V^{gD}$ induced by the bijection $D \simeq gD$ given by $h \mapsto gh$ for every $h \in D$ .

Observe that the maps $\pi _{ij,g}$ above and the transition maps of the inverse system $(\Sigma _{ij})_{i,j \in \mathbb {N}}$ are induced by morphisms of algebraic varieties.

In this section, we consider the following conditions:

1. (C2) V is a complete K-algebraic variety;

2. (C3) V is a K-algebraic group and $W \subset V$ is an algebraic subgroup.

Remark 6.1. In case (C3), note that the projections $p_{ijk} \colon A_{k j} \to A_{ij}$ (cf. equation (5.2)) are homomorphisms of algebraic groups.

Proposition 6.2. With the above notation and hypotheses, suppose in addition that one of the conditions $(\mathrm {H1})$ , $(\mathrm {C2})$ , $(\mathrm {C3})$ is satisfied. Then, for each $i, j \in \mathbb {N}$ , we have

(6.2) $$ \begin{align} \Sigma_{ij} = \bigcap_{k \geq i} p_{ijk}(A_{k j}) \end{align} $$

and $\Sigma _{i j}$ is a countably proconstructible subset of $A^{M^{i+j}}$ . Moreover, in case $(\mathrm {C2})$ (respectively $(\mathrm {C3})$ ), $\Sigma _{ij}$ is a complete subvariety (respectively an algebraic subgroup) of  $A^{M^{i+j}}$ .

Proof. The inclusion $\Sigma _{ij} \subset \bigcap _{k \geq i} p_{ijk}(A_{k j})$ follows from Lemma 5.4.

Let $x \in \bigcap _{k \geq i} p_{ijk}(A_{k j}) \subset A^{M^{i+j}}$ . We must show that x can be extended to an element of $\Sigma $ . Consider the following inverse system lying above x. Let $B_i=\{x\}$ and for each $k \geq i$ , we set

(6.3)

which is a closed algebraic subset of $A^{M^{k+j}}$ . Since $x \in p_{ijk}(A_{k j})$ , each set $B_{k}$ is non-empty. From equation (6.3), it is clear that for every $k \geq i$ , we have

$$ \begin{align*} \widetilde{p}_{kj}(B_{k+1} ) \subset B_k. \end{align*} $$

By restricting the map $\widetilde {p}_{kj}$ to $B_{k+1}$ , we have for each $k \geq i$ a well-defined algebraic map $\pi _k \colon B_{k+1} \to B_k$ . Thus, we obtain an inverse subsystem $(B_k)_{k \geq i}$ with transition maps $\pi _{nm} \colon B_m \to B_n$ , where $m \geq n \geq i$ , as compositions of the maps $\pi _k$ .

We claim that $\varprojlim _{k \geq i} B_k \neq \varnothing $ . Indeed, this follows from Lemma 3.2 if case (H1) is satisfied and from Lemma 3.3 and Remark 2.1 in case (C2). Suppose now that case (C3) is satisfied. Since $x \in \bigcap _{k \geq i} p_{ijk}(A_{k j})$ , there exists for each $k~\geq ~i$ a point $z_k \in B_k$ such that $p_{ijk}(z_k)=x$ . Let $V_k = \ker p_{ijk}$ be an algebraic subgroup of $A^{M^{k+j}}$ , then clearly ${B_k = z_k V_k}$ where the group law is written multiplicatively. For all integers $m \geq n \geq i$ , the map $\pi _{mn}$ is the restriction of a homomorphism of algebraic groups (cf. Remark 4.3). Therefore, $\pi _{nm}(B_m)$ is a translate of an algebraic subgroup of $A^{M^{n+j}}$ and thus is Zariski closed in $B_n$ (cf. Remark 2.1). Hence, the claim follows, also in case (C3), from Lemma 3.3.

Therefore, we can find $(y_k)_{k \geq i} \in \varprojlim _{k \geq i} B_k$ . Let $y \in A^{G}$ be defined as follows. Given $g \in G$ , set $y(g)= y_k(g)$ for any $k \geq i$ such that $g \in M^{k+j}$ . Then y is well defined by property (Mem2). For each $g \in G$ , choose $k \geq i$ so that $gD \subset M^{k+j}$ . Then $(g^{-1}y)\vert _D = y_k\vert _{gD} \in W(K)$ which follows from the definition of $A_{kj}$ and since $y_k \in B_{kj} \subset A_{kj}$ . Hence, $y \in \Sigma $ . By construction, $x= y \vert _{M^{i+j}}$ and we deduce that $\bigcap _{k \geq i} q_{ijk}(A_{k j}) \subset \Sigma _{M^{i+j}}$ . The proof of equation (6.2) is completed. Thus, by Chevalley’s theorem, $\Sigma _{i j}$ is a countably proconstructible subset of $A^{M^{i+j}}$ .

Finally, the last statement follows from equation (6.2) and Remark 2.1 and Noetherianity of the Zariski topology of $A^{M^{i+j}}$ . Note that the sequence $(q_{ijk}(A_{k j}))_{k \geq i}$ is trivially a descending sequence.

Corollary 6.3. With the above notation and hypotheses, suppose that condition $(\mathrm {H1})$ (respectively $(\mathrm {C2})$ , respectively $(\mathrm {C3})$ ) is satisfied for $\Sigma $ . Then, for each finite subset $E \subset G$ , the restriction $\Sigma _E $ is a countably proconstructible subset (respectively a complete subvariety, respectively an algebraic subgroup) of $A^E$ .

Proof. Let $i, j \in \mathbb {N}$ be large enough so that $E \subset M^{i+j}$ . Let $\pi \colon A^{M^{i+j}} \to A^E$ be the induced projection. It follows that $\Sigma _E = \pi (\Sigma _{ij})$ . In cases (C2) and (C3), Proposition 6.2 and Remark 2.1 imply that $\Sigma _E$ is respectively a complete subvariety and an algebraic subgroup of $A^E$ . In case (H1), we find by Lemma 3.1 that

(6.4) $$ \begin{align} \Sigma_E = \pi (\Sigma_{ij}) = \pi \bigg(\bigcap_{k \geq i} p_{ijk} (A_{kj}) \bigg) = \bigcap_{n \in \mathbb{N}} \pi (p_{ijk} (A_{kj}) ). \end{align} $$

Hence, $\Sigma _E$ is countably proconstructible by Chevalley’s theorem. The proof is completed.

7 Algebraic sofic subshifts

Consider the following hypothesis without condition on cellular automata:

$(\mathrm {\widehat {H3}})\quad K$ is algebraically closed, V is a K-algebraic group, and $\Sigma \subset A^G$ is an algebraic group sofic subshift.

We can now state the main local result for algebraic sofic subshifts.

Theorem 7.1. Let V be an algebraic variety over a field K and let $A= V(K)$ . Let G be a finitely generated group and let $\Sigma \subset A^G$ be an algebraic sofic subshift. Let E be a finite subset of G. Suppose that condition $(\mathrm {H1})$ (respectively $(\mathrm {H2})$ , respectively $(\mathrm {\widehat {H3}})$ ) is satisfied. Then the restriction $\Sigma _E \subset A^E$ is a countably proconstructible subset (respectively a complete subvariety, respectively an algebraic subgroup) of $A^E$ .

Proof. By hypothesis, there exist in cases (H1) and (H2) an algebraic variety (respectively in case $(\mathrm {\widehat {H3}})$ an algebraic group) U over K, an algebraic (respectively algebraic group) cellular automaton $\tau ' \colon B^G \to A^G$ where $B= U(K)$ , and an algebraic (respectively algebraic group) subshift of finite type $\Sigma ' \subset B^G$ such that $\Sigma = \tau ' (\Sigma ')$ . Note that $U,V$ are complete varieties in case (H2). Let M be a memory set of $\tau '$ . By Corollary 6.3, the set $\Sigma ^{\prime }_{ME}$ is countably proconstructible. Hence, $\Sigma ^{\prime }_{ME} = \bigcap _{n \in \mathbb {N}} C_n$ where $(C_n)_{n \in \mathbb {N}}$ is some decreasing sequence of constructible subsets of $A^{ME}$ . Let $\varphi \colon B^{ME} \to A^E$ be given by $\varphi (x)(g)= \tau '(y)(g)$ for every $x \in B^{ME}$ , $g \in E$ and every $y \in B^G$ extending x. Then $\varphi $ is algebraic (cf. [14, Lemma 3.2]) and in case $(\mathrm {\widehat {H3}})$ , it is a homomorphism of algebraic groups (cf. [39, Lemma 3.4]). In case (H1), we can conclude by Chevalley’s theorem since

(7.1) $$ \begin{align} \Sigma_E = (\tau'(\Sigma'))_E = \varphi(\Sigma^{\prime}_{ME}) = \varphi \bigg(\bigcap_{n \in \mathbb{N}} C_n \bigg) = \bigcap_{n \in \mathbb{N}} \varphi (C_n), \end{align} $$

where the last equality follows from Lemma 3.1. Finally, in cases (H2) and $(\mathrm {\widehat {H3}})$ , Corollary 6.3 implies that $\Sigma _E = \varphi (\Sigma ^{\prime }_{ME})$ is respectively a complete subvariety and an algebraic subgroup of $A^E$ .

8 A closed mapping property and chain recurrent sets

Using the space-time inverse system, we give a short proof of the following result saying that the image of an algebraic sofic subshift under an algebraic cellular automaton is closed. It extends the linear case in [16, Theorem 4.1].

Let G be a group. Let $V_0, V_1$ be algebraic varieties over an algebraically field K. Let $A_0 = V_0(K)$ and let $A_1=V_1(K)$ . Let $\tau \colon A_0^G \to A_1^G$ be an algebraic cellular automaton and let $\Sigma \subset A_0^G$ be an algebraic sofic subshift.

Then $\Sigma $ is the image of some algebraic subshift of finite type $\Sigma ' \subset B^G$ under an algebraic cellular automaton $\tau ' \colon B^G \to A_0^G$ , where B is the set of K-points of a K-algebraic variety U.

To avoid notational confusion, we introduce in this section the following hypotheses similar to hypotheses (H1), (H2), and (H3), $(\mathrm {\widehat {H3}})$ :

• $(\mathrm {\widetilde {H1}})$ K is uncountable;

• $(\mathrm {\widetilde {H2}})$ $U, V_0$ are complete K-algebraic varieties;

• $(\mathrm {\widetilde {H3}})$ $U, V_0$ , and $V_1$ are K-algebraic groups, $\Sigma ' \subset B^G$ is an algebraic group subshift of finite type, and $\tau ' \colon B^G \to A_0^G$ and $\tau \colon A_0^G \to A_1^G$ are algebraic group cellular automata.

Theorem 8.1. With the above notation, if one of the conditions $(\mathrm {\widetilde {H1}})$ , $(\mathrm {\widetilde {H2}})$ , $(\mathrm {\widetilde {H3}})$ is satisfied, then $\tau (\Sigma )$ is closed in $A_1^G$ .

Proof. It is clear that, up to replacing $\tau $ by the composition $\tau \circ \tau '$ and $\Sigma $ by $\Sigma '$ , we can suppose without loss of generality that $\Sigma $ is an algebraic subshift of finite type. The hypotheses $(\mathrm {\widetilde {H2}})$ , $(\mathrm {\widetilde {H3}})$ now become respectively:

1. (P2) $V_0$ is a complete K-algebraic variety;

2. (P3) $V_0$ and $V_1$ are K-algebraic groups, $\Sigma \subset A_0^G$ is an algebraic group subshift of finite type, and $\tau \colon A_0^G \to A_1^G$ is an algebraic group cellular automaton.

Let $D \subset G$ be a defining memory set of $\Sigma $ . Let $d \in A_1^G$ be in the closure of $\tau (\Sigma )$ . We must show that $d \in \tau (\Sigma )$ .

Suppose first that G is finitely generated. Let $M \subset G$ be a finite memory subset of $\tau $ containing $\{1_G\} \cup D$ which generates G and satisfies $M=M^{-1}$ . Consider the inverse system $(A_0^{M^i})_{i\in \mathbb {N}}$ whose transition maps $p _{ij}\colon A_0^{M^j} \to A_0^{M^i}$ , where $0 \leq i \leq j$ , are defined as the canonical projections induced by the inclusions $M^i \subset M^j$ . For every $i \geq 1$ , the induced map $q_i \colon A_0^{M^i} \to A_1^{M^{i-1}}$ is given as follows. For every $\sigma \in A_0^{M^i}$ , we set , where $x \in A_0^G$ is any configuration that extends $\sigma $ . For every $i \geq 1$ , we define

Since d belongs to the closure of $\tau (\Sigma )$ in $A_1^G$ , it follows that $Z_i \neq \varnothing $ for every $i \geq 1$ . By restricting the projections $p_{ij} \colon A^{M^j} \to A^{M^i}$ to $Z_j$ , we obtain well-defined transition maps $\pi _{ij} \colon Z_j \to Z_i$ , where $j \geq i \geq 1$ , of the inverse system $(Z_i)_{i \geq 1}$ .

It suffices to show that $\varprojlim _{i \geq 1} Z_i \neq \varnothing $ since, by construction of $Z_i$ and $\Sigma _{ij}$ (see also [14, Lemma 2.1]), we have $\tau (c) = d$ for every $c \in \varprojlim _{i \geq 1} Z_i \subset \varprojlim _{i \geq 1} \Sigma _{M^{i+1}} = \Sigma $ (by equation (4.6) since $\Sigma $ is closed as it is a subshift of finite type).

Thanks to Theorem 7.1, the conclusion follows by a direct application of Lemma 3.2, respectively Lemma 3.3, to the inverse system $(Z_i)_{i \in \mathbb {N}}$ if case $(\mathrm {\widetilde {H1}})$ , respectively case (P2), is satisfied. Assume now that case (P3) is satisfied. For each $i \geq 1$ , choose $z_i \in Z_i$ and let be an algebraic subgroup of $\Sigma _{M^i}$ (by Theorem 7.1). We have $Z_i= z_i V_i$ . Hence (by Remark 4.3), for $j \geq i \geq 1$ , $\pi _{ij}(Z_j) $ is a translate of an algebraic subgroup of $\Sigma _{M^i}$ and thus is Zariski closed in $Z_i$ . Therefore, case (P3) follows from Lemma 3.3.

For a general group G, consider a finite memory set M of $\tau $ containing $\{1_G\} \cup D$ and such that $M=M^{-1}$ . Let $H \subset G$ be the subgroup generated by M. As $\Sigma _H$ is clearly an algebraic (respectively in case $(\mathrm {\widetilde {H3}})$ an algebraic group) subshift of finite type, the above discussion shows that $\tau _H(\Sigma _H)$ is closed in $A_1^G$ and so is $\tau (\Sigma )$ by Lemma 2.10.

Corollary 8.2. Let G be a group. Let V be an algebraic variety over a field K and let . Let $\Sigma \subset A^G$ be an algebraic sofic subshift. If one of the conditions $(\mathrm {H1})$ , $(\mathrm {H2})$ , $(\mathrm {\widehat {H3}})$ is satisfied, then $\Sigma $ is closed in $A^G$ .

Proof. It suffices to apply Theorem 8.1 in the case $V_0=V_1$ to the identity map $\tau = \operatorname {\mathrm {Id}}_{A^G}$ , where $A = V_0(K) = V_1(K)$ .

Corollary 8.3. With the notation and hypotheses as in Theorem 1.3, we have ${\operatorname {\mathrm {CR}} (\tau ) \subset \Omega (\tau )}$ .

Proof. By Proposition 2.3, we only need to check that $\tau ^n(\Sigma )$ is closed in $A^G$ for every $n \geq 1$ and that $\tau $ is uniformly continuous. The first property follows from Theorem 8.1. The second is a general property of cellular automata already mentioned in §1.

9 Applications to backward orbits and limit sets

Thanks to the closedness property of algebraic sofic subshifts, we can establish the following key relation among inverse space-time systems, backward orbits, and limit sets.

Theorem 9.1. Let V be an algebraic variety over a field K and let $A= V(K)$ . Let G be a finitely generated group and let $\Sigma \subset A^G$ be an algebraic sofic subshift. Let $\tau \colon \Sigma \to \Sigma $ be an algebraic cellular automaton. Assume that one of the conditions $(\mathrm {H1})$ , $(\mathrm {H2})$ , $(\mathrm {H3})$ is satisfied. Then, with the notation as in §4, we have a surjective map $\Phi \colon \varprojlim _{i,j \in \mathbb {N}} \Sigma _{ij}~\to ~\Omega (\tau )$ .

Proof. By Corollary 8.2, the subshift $\Sigma $ is closed in $A^G$ . Hence, $\varprojlim _{i,j \in \mathbb {N}} \Sigma _{ij}$ is the set of backward orbits of $\tau $ and we have a canonical map $\Phi \colon \varprojlim _{i,j \in \mathbb {N}} \Sigma _{ij} \to \Omega (\tau )$ given in Lemma 4.4. Now let $y_0 \in \Omega (\tau ) \subset \Sigma $ . We must show that there exists $x \in \varprojlim _{i,j \in \mathbb {N}} \Sigma _{ij} $ such that $\Phi (x)=y_0$ . For every $i, j \in \mathbb {N}$ , define a closed subset

By definition of $\Omega (\tau )$ , there exists for every $j \in \mathbb {N}$ an element $y_j \in \Sigma $ such that ${\tau ^j (y_j)=y_0}$ . Hence, it follows from the definition of the transition maps $q_{ik}$ and of $\Sigma _{ij}$ that $y_j\vert _{M^{i+j}} \in B_{ij}$ . In particular, $B_{ij} \neq \varnothing $ for every $i, j \in \mathbb {N}$ . By restricting the transition maps of the space-time inverse system $(\Sigma _{ij})_{i, j \in \mathbb {N}}$ to the sets $B_{ij}$ , we obtain a well-defined inverse subsystem $(B_{ij})_{i, j \in \mathbb {N}}$ .

We claim that $\varprojlim _{i, j \in \mathbb {N}} B_{ij} \neq \varnothing $ . Indeed, by Theorem 7.1, case (H1) is implied by Lemma 3.2. In case (H2), Theorem 7.1 implies that $B_{ij}$ is a complete algebraic subvariety of $\Sigma _{ij}$ and thus of $A^{M^{i+j}}$ . Hence, case (H2) follows from Lemma 3.3 and Remark 2.1. In case (H3), a similar argument as in the proof of Proposition 6.2 shows that the transition maps of the system $(B_{ij})_{i, j \in \mathbb {N}}$ have Zariski closed images. Therefore, case (H3) follows immediately from Lemma 3.3. Thus, we can find

$$ \begin{align*} x \in \varprojlim_{i, j \in \mathbb{N}} B_{ij} \subset \varprojlim_{i, j \in \mathbb{N}} \Sigma_{ij}. \end{align*} $$

It is clear from the constructions of the inverse system $(B_{ij})_{i, j \in \mathbb {N}}$ and of the map $\Phi $ (see the proof of Lemma 4.4) that $\Phi (x)= y_0$ . The proof of the lemma is completed.

Corollary 9.2. With the notation and hypotheses as in Theorem 1.3, we have $\tau (\Omega (\tau ))= \Omega (\tau )$ .

Proof. Let $M\subset G$ be a finite subset containing $1_G$ , a memory set of $\tau $ , and a memory set of $\Sigma $ and such that $M=M^{-1}$ . Let $H \subset G$ be the subgroup generated by M. Since $\tau = \prod _{c \in G/H} \tau _c$ and $\Omega (\tau )= \prod _{c \in G /H} \Omega (\tau _c)$ (cf. Lemma 2.9), we can suppose without loss of generality that $G=H$ . Let $x {\kern-1pt}\in{\kern-1pt} \Omega (\tau )$ , then $x \in \tau ^n(X)$ for every $n {\kern-1pt}\geq{\kern-1pt} 0$ . Thus, $\tau (x) \in \tau ^{n+1}(X)$ for every $n \geq 0$ and it follows that $\tau (x) \in \Omega (\tau )$ . Therefore, $\tau (\Omega (\tau )) \subset \Omega (\tau )$ . For the converse inclusion, let $y \in \Omega (\tau )$ . By Theorem 9.1, there exists ${x = (x_{ij}) \in \varprojlim _{i,j \in \mathbb {N}} \Sigma _{ij}}$ such that $ \Phi (x)=y$ . However, equation (4.7) tells us that $\Phi ^{-1}(y) \subset \varprojlim _{i,j \in \mathbb {N}} \Sigma _{ij}$ is the set of backward orbits of y under $\tau $ . Hence, we can find $z \in \Omega (\tau )$ such that $\tau (z)= y$ . Thus, $\Omega (\tau ) \subset \tau (\Omega (\tau ))$ and the conclusion follows.

10 Noetherianity of algebraic subshifts of finite type

The goal of this section is to establish the following characterization of algebraic subshifts of finite type by the descending chain property. It extends the linear version in [16, Theorem 1.1 and Corollary 1.2]. The proof is an application of Theorem 7.1 combined with the construction of an inverse system analogous to the space-time inverse system. More precisely, we obtain the following theorem.

Theorem 10.1. Let G be a finitely generated group and let V be an algebraic variety (respectively an algebraic group) over an algebraically closed field K. Let $A=V(K)$ and let $\Sigma \subset A^G$ be a subshift. Consider the following properties:

1. (a) $\Sigma $ is a subshift of finite type;

2. (b) $\Sigma $ is an algebraic (respectively algebraic group) subshift of finite type;

3. (c) every descending sequence of algebraic (respectively algebraic group) sofic subshifts of $A^G$

   $$ \begin{align*} \Sigma_0 \supset \Sigma_1 \supset \cdots \supset \Sigma_n \supset \Sigma_{n+1} \supset \cdots \end{align*} $$
   such that $\bigcap _{n \geq 0} \Sigma _n = \Sigma $ eventually stabilizes.

Then we have $(\mathrm{b}) \implies (\mathrm{a}) \implies (\mathrm{c})$ . Moreover, if $\Sigma \subset A^G$ is an algebraic (respectively algebraic group) sofic subshift, then $(\mathrm{a}) \iff (\mathrm{b}) \iff (\mathrm{c})$ .

Proof. It is trivial that (b) $\implies $ (a). Assume that $\Sigma $ is a subshift of finite type. Hence, $\Sigma = \Sigma (D, W)$ , where $D \subset G$ is finite and $W \subset A^D$ is some subset. Let $\Sigma _0 \supset \Sigma _1 \supset \cdots $ be a descending sequence of algebraic (respectively algebraic group) sofic subshifts of $A^G$ whose intersection is $\Sigma $ . Let $M \subset G$ be a finite generating subset containing ${\{1_G\} \cup D}$ and such that $M=M^{-1}$ . Consider the inverse system $(X_{ij})_{i,j \in \mathbb {N}}$ defined by . Remark that $X_{i,j+1} \subset X_{ij}$ since $\Sigma _{j+1} \subset \Sigma _j$ for all $i, j \in \mathbb {N}$ . We define the unit transition maps $p_{ij} \colon X_{i+1, j} \to X_{ij}$ by $p_{ij}(x)= x\vert _{M^{i}}$ for every $x \in X_{i+1, j}$ and $q_{ij} \colon X_{i, j+1} \to X_{ij}$ simply as the inclusion maps.

For all $i, j \in \mathbb {N}$ , Theorem 7.1 implies that every $X_{ij}$ is a complete variety (respectively an algebraic group) over K. By Noetherianity of the Zariski topology, the decreasing sequence $(X_{0j})_{j \in ~\mathbb {N}}$ of algebraic closed subsets of $A^{M}$ eventually stabilizes, say, ${X_{0j}= X_{0m}}$ for all $j \in \mathbb {N}$ for some $m \in \mathbb {N}$ . Let , then is an algebraic (respectively algebraic group) subshift of finite type. It is clear that $\Sigma _m \subset \Sigma '$ and hence $\Sigma \subset \Sigma '$ . We shall prove the converse inclusion.

Let $w \in W'$ . We construct an inverse subsystem $(Z_{ij})_{i \geq m, j \geq 0}$ of $(X_{ij})_{i \geq m, j \geq 0}$ as follows. For $i \geq m$ , let which is clearly an algebraic closed subvariety (respectively a translate of an algebraic subgroup) of $X_{i0}$ . For $i \geq m, j \geq 0$ , we define an algebraic closed subvariety (respectively a translate of an algebraic subgroup (by Theorem 7.1)) of $X_{ij}$ as follows:

The transition maps of $(Z_{ij})_{i \geq m, j \geq 0}$ are well defined as the restrictions of the transition maps of the system $(X_{ij})_{i \geq m, j \geq 0}$ . These transition maps have Zariski closed images (by Remark 2.1).

By our construction, each $Z_{ij}$ is clearly non-empty. Hence, Lemma 3.3 implies that there exists $x = (x_{ij})_{i \geq m,j \geq 0} \in \varprojlim Z_{ij}$ . Let $y \in A^G$ be defined by $y(g)= x_{i0}(g)$ for every $g \in G$ and any large enough $i\geq m$ such that $g \in M^{i}$ . Observe that $x_{ij} = x_{ik}$ for every $i \geq m$ and $0 \leq j \leq k$ since the vertical transition maps $X_{ik} \to X_{ij}$ are simply inclusions. Consequently, for every $n \in \mathbb {N}$ , we have $y \in \Sigma _n$ by equation (4.6) since $\Sigma _n$ is closed in $A^G$ (cf. Corollary 8.2). Hence, $y \in \Sigma $ . By construction, $y\vert _{M^m} = w$ . Since w was arbitrary, this shows that $W' \subset \Sigma _{M^m}$ . Hence, $\Sigma ' = \Sigma (M^m, W') \subset \Sigma (M^m, \Sigma _{M^m}) = \Sigma $ . The last equality follows from Lemma 5.1 as $D \subset M^m$ . Therefore, $\Sigma ' = \Sigma $ and $\Sigma _n= \Sigma $ for all $n \geq m$ . This proves that (a) $\implies $ (c).

Suppose now that $\Sigma \subset A^G$ is an algebraic (respectively algebraic group) sofic subshift which is not a subshift of finite type. Let $M \subset G$ be a finite generating subset containing $\{1_G\}$ such that $M=M^{-1}$ . For every $n \in \mathbb {N}$ , consider (as in §4). Theorem 7.1 tells us that $W_n$ is a complete algebraic subvariety (respectively an algebraic subgroup) of $A^{M^n}$ . Set for every $n \in \mathbb {N}$ , then $\Sigma _n$ is an algebraic (respectively algebraic group) subshift of finite type. As $(\Sigma _{M^{n+1}})_{M^n} = \Sigma _{M^n}$ , it is clear that ${\Sigma \subset \Sigma _{n+1} \subset \Sigma _n}$ for every $n \in \mathbb {N}$ . We claim that $\Sigma = \bigcap _{n \in \mathbb {N}} \Sigma _n$ . Indeed, we only need to prove that $\bigcap _{n \in \mathbb {N}} \Sigma _n \subset \Sigma $ . Let $x \in \bigcap _{n \in \mathbb {N}} \Sigma _n$ . Then by definition of $\Sigma _n$ , we find that $x\vert _{M^n} \in W_n= \Sigma _{M^n}$ for every $n \in \mathbb {N}$ . Thus, since $\Sigma $ is closed (cf. Corollary 8.2), ${x \in \varprojlim _{n \in \mathbb {N}} \Sigma _{M^n} =\Sigma }$ (cf. equation (4.6)) and hence $\bigcap _{n \in \mathbb {N}} \Sigma _n \subset \Sigma $ . However, the descending sequence $(\Sigma _n)_{n \in \mathbb {N}}$ cannot stabilize since otherwise the subshift $\Sigma $ would be of finite type. This shows that (c) $\implies $ (a) if $\Sigma $ is an algebraic (respectively algebraic group) sofic subshift. The proof is complete.

Examples 10.2. (Markov properties)

The examples below provide the original sources and motivations for our main result in this section (Theorem 10.1).

(a) Let G be a group and let A be a finite group. Equip the configuration space $A^G$ with the product group structure (thus, given two configurations $x,y \in A^G$ , their product is defined as the configuration $xy \in A^G$ given by for all $g \in G$ ). A closed subshift $X \subset A^G$ which is also a subgroup of $A^G$ is called a group subshift. Group subshifts $X \subset A^{\mathbb {Z}}$ are called Markov subgroups in [28, §6.3], and were studied and classified up to topological conjugacy by Kitchens in [27] (see also [28, Theorem 6.3.3]).

One says that a group G is of finite Markov type if for any finite group A, every group subshift $\Sigma \subset A^G$ is of finite type. The finite Markov type property is a weakening of the Markov type property introduced by Schmidt in [54, Definition 4.1].

The following hold:

1. (i) every finite group is of finite Markov type;

2. (ii) the additive group $\mathbb {Z}$ is of finite Markov type. This result was established by Kitchens in [27, Proposition 4] (see also [28, Lemma 6.3.5], [30, Exercise 2.1.11], and [13, Exercise 1.114]);

3. (iii) every subgroup of a group of finite Markov type is finitely generated (this is also expressed by saying that groups of finite Markov type are Noetherian). As a consequence, every group of finite Markov type is countable and contains no non-abelian free subgroups;

4. (iv) every quotient of a group of finite Markov type is of finite Markov type;

5. (v) every group containing a finite index subgroup of finite Markov type is itself of finite Markov type;

6. (vi) a group G is of finite Markov type if and only if G is countable and, for any finite group A, every descending sequence of group subshifts of $A^G$

   $$ \begin{align*} X_0 \supset X_1 \supset X_2 \supset \cdots \supset X_n \supset X_{n+1} \supset \cdots \end{align*} $$
   eventually stabilizes, that is, there exists $n_0 \in \mathbb {N}$ such that $X_n = X_{n_0}$ for all ${n \geq n_0}$ (cf. [13, Exercise 1.112]).

In other words, the class of groups of finite Markov type is closed under the operations of taking subgroups, quotients, and extensions by finite or cyclic groups. As a consequence, all finitely generated abelian groups are of finite Markov type (a result observed by Kitchens and Schmidt [26, Remark 3.10(2)]). In fact, more generally, the class of groups of finite Markov type contains all polycyclic-by-finite groups (cf. [13, Exercise 4.37]), a particular case of [54, Theorem I.4.2]. The question whether or not every group of finite Markov type is polycyclic-by-finite remains, at our present knowledge, open.

(b) Let G be a group, let K be a field, and let A be a finite-dimensional vector space over K. Equip the configuration space $A^G$ with the product vector space structure (thus, given a scalar $\unicode{x3bb} \in K$ and two configurations $x,y \in A^G$ , one defines the configuration ${\unicode{x3bb} x \in A^G}$ (respectively $x + y \in A^G$ ) by setting (respectively ) for all $g \in G$ . A closed subshift $\Sigma \subset A^G$ which is also a vector subspace of $A^G$ is called a linear subshift. One says that a group G is of K-linear Markov type if for any finite-dimensional vector space A over K, every linear subshift $\Sigma \subset A^G$ is of finite type. Analogous properties to items (i)–(vi) in point (a), for groups of K-linear Markov type, are shown in [16, §6] (see also [42] for some more general results). In other words, the class of K-linear Markov groups is closed under the operations of taking subgroups, quotients, and extensions by finite or cyclic groups, and contains all polycyclic-by-finite groups (cf. [16, Corollary 1.4]). In addition, one has the following characterization: a group G is of K-linear Markov type if and only if its group ring $K[G]$ is one-sided Noetherian [16, Theorem 1.3].

11 Proof of Theorem 1.3

For item (i), we know that $\Omega (\tau )$ is G-invariant by the G-equivariance of $\tau $ . However, as the set of algebraic cellular automata over $\Sigma $ is closed under the composition of maps (cf. [14, Proposition 3.3] for the case of full shifts, the general case is proved similarly), the map $\tau ^n \colon \Sigma \to \Sigma $ is an algebraic cellular automaton for every $n \geq 1$ . It then follows from Theorem 8.1 that $\tau ^n(\Sigma )$ is closed in $A^G$ for every $n \geq 1$ and thus $\Omega (\tau ) = \bigcap _{n \geq 1} \tau ^n(\Sigma )$ is also closed in $A^G$ . This shows that $\Omega (\tau )$ is a closed subshift of $A^G$ and item (i) is proved.

For item (v), let $z \in \Sigma \cap \operatorname {\mathrm {Fix}}(H)$ for some subgroup $H \subset G$ . Let $F \subset G$ be the subgroup generated by a finite subset M containing $\{1_G\}$ and memory sets of $\tau $ , $\Sigma $ , and such that $M=M^{-1}$ . Note that $z\vert _F$ is fixed by the subgroup of F. Consider the space-time inverse system $(\Sigma _{ij})_{i, j \in \mathbb {N}}$ associated with the restriction $\tau _F$ and M as in Definition 4.1. Keep the notation in §4. For all $i, j \in \mathbb {N}$ , let

be the restriction to $M^{i+j}$ of R-fixed points in $A^H$ . Clearly, $\Delta _{ij}$ is respectively a closed subvariety, a complete algebraic subvariety, and an algebraic subgroup of $A^{M^{i+j}}$ in cases (H1), (H2), and (H3). Define also .

Note that $\tau _F$ sends R-fixed points to R-fixed points. Hence, by restricting the transition maps to the sets $Z_{ij}$ , we obtain a well-defined inverse subsystem of $(\Sigma _{ij})_{i,j \in \mathbb {N}}$ . Theorem 7.1 implies that respectively in each case (H1), (H2), and (H3), the set $Z_{ij} \subset A^{M^{i+j}}$ is a countably proconstructible subset, a complete algebraic subvariety, and an algebraic subgroup. Each $Z_{ij}$ is non-empty since it contains $z\vert _{M^{i+j}}$ . Hence, Lemmas 3.2 and 3.3 imply that there exists $x \in \varprojlim _{i,j \in \mathbb {N}} Z_{ij} \subset \varprojlim _{i,j \in \mathbb {N}} \Sigma _{ij}$ . By Lemma 4.4, we obtain $y= \Phi (x) \in \Omega (\tau _F) \subset A^H$ . By our construction, y is fixed by R. By Lemma 2.9(i), ${\Omega (\tau ) = \Omega (\tau _F)^{G/F}}$ . Thus, y induces a configuration of $\Omega (\tau )$ fixed by H. This proves item (v).

To finish the proof of Theorem 1.3, note that item (ii) follows from Corollary 9.2 and item (iii) follows from the general property $\operatorname {\mathrm {Per}}(\tau ) \subset \operatorname {\mathrm {R}}(\tau ) \subset \operatorname {\mathrm {NW}}(\tau ) \subset \operatorname {\mathrm {CR}}(\tau )$ and from the inclusion $\operatorname {\mathrm {CR}}(\tau ) \subset \Omega (\tau ) $ proved in Corollary 8.3. Finally, in case (H2) (respectively in case (H3)), item (iv) is a direct consequence of the implication (a) $\implies $ (c) in Theorem 10.1 applied to $\Omega (\tau )$ and the decreasing sequence of algebraic (respectively algebraic group) sofic subshifts $\tau (\Sigma ) \supset \tau ^2(\Sigma ) \supset \cdots \supset \tau ^n(\Sigma ) \supset \tau ^{n+1}(\Sigma ) \supset \cdots $ which satisfies by definition.

12 Proof of Theorem 1.4

It is clear that (a) $\implies $ (b). For the converse implication, suppose that $\Omega (\tau )= \{x_0\}$ for some $x_0 \in \Sigma $ . As $\Omega (\tau )$ is G-invariant, there exists an element denoted by $0 \in A$ such that $x_0(g)= 0$ for every $g \in G$ , that is, $x_0=0^G$ . Let $M\subset G$ be a finite subset containing a memory set of $\tau $ and a memory set of $\Sigma $ such that $1_G \in M$ and $M=M^{-1}$ . Let H be the subgroup generated by M and consider the restriction $\tau _H$ . By Lemma 2.9, we deduce that $\Omega (\tau _H)$ must be a singleton as well and $\tau $ is nilpotent if $\tau _H$ is. Thus, up to replacing G by H, we can suppose that G is generated by M.

We construct an inverse subsystem $(\Sigma ^*_{ij})_{i, j \in \mathbb {N}}$ of the space-time inverse system $(\Sigma _{ij})_{i, j \in \mathbb {N}}$ associated with $\tau $ and the memory set M (cf. Definition 4.1) as follows. Let for every $i \geq 0$ . For all $i \geq 0$ and $j \geq 1$ , we define

$$ \begin{align*} \Sigma^*_{ij}= (q_{i 0} \circ \cdots \circ q_{i, j-1})^{-1}(\Sigma_{i0}^*). \end{align*} $$

The unit transition maps $q^*_{ij} \colon \Sigma ^*_{i, j+1} \to \Sigma ^*_{i j}$ and $p^*_{ij} \colon \Sigma ^*_{i+1, j} \to \Sigma ^*_{ij}$ of the inverse subsystem $(\Sigma ^*_{ij})_{i, j \in \mathbb {N}}$ are defined respectively by the restrictions of the transition maps $q_{ij}$ and $p_{ij}$ of $(\Sigma _{ij})_{i, j \in \mathbb {N}}$ .

Assume in contrast that $\tau $ is not nilpotent. We claim that $\Sigma ^*_{ij} \neq \varnothing $ for all $i, j \in \mathbb {N}$ . Otherwise, $\Sigma ^*_{ij}= \varnothing $ for some $i, j \in \mathbb {N}$ . If $j=0$ , then $\Sigma ^*_{i0}= \varnothing $ , that is, $x(1_G) = 0$ for all $x \in \Sigma _{i0}$ , and since $\Sigma $ is G-invariant and $1_G \in M^{i+j}$ , we deduce that $\Sigma = \{0^G\}$ . Hence, $\tau $ is trivially nilpotent and we arrive at a contradiction. Thus, $j \geq 1$ and by definition of $\Sigma _{ij}$ , we have for every $x \in \Sigma _{ij}$ that

$$ \begin{align*} (q_{i 0} \circ \cdots \circ q_{i, j-1})(x)(1_G)=0. \end{align*} $$

Since $\tau ^{i+j}$ is G-equivariant, it follows that $\tau ^{i+j}(x)=0^G$ for every $x \in \Sigma $ , which contradicts the assumption that $\tau $ is not nilpotent. This proves the claim, that is, $\Sigma ^*_{ij} \neq \varnothing $ for all $i, j \in \mathbb {N}$ . We are going to show that

(12.1) $$ \begin{align} \varprojlim_{i,j \in \mathbb{N}} \Sigma^{*}_{ij} \neq \varnothing. \end{align} $$

Indeed, equation (12.1) is a direct application of Theorem 7.1 and Lemma 3.2 to the inverse system $(\Sigma ^*_{ij})_{i, j \in \mathbb {N}}$ in case (H1). For cases (H2) and (H3), observe that for every $(i, j) \prec (k, l)$ in $\mathbb {N}^2$ , we have

(12.2)

where $F_{(i,j), (k,l)} \colon \Sigma _{kl} \to \Sigma _{ij}$ is the transition map of the inverse system $(\Sigma _{ij})_{i, j \in \mathbb {N}}$ . Indeed, by definition of $\Sigma ^*_{kl}$ and $\Sigma ^*_{ij}$ , and using the equality $F_{(i,0),(k,l)} = F_{(i,0),(i,j)} \circ F_{(i,j), (k,l)}$ , we see that

$$ \begin{align*} F_{(i,j), (k,l)} (\Sigma^*_{k,l}) & = F_{(i,j), (k,l)} (\Sigma_{k,l} \setminus F^{-1}_{(i,0),(k,l)}(\Sigma_{i,0} \setminus \Sigma^*_{i,0}) ) \\ & \supset F_{(i,j), (k,l)} (\Sigma_{kl}) \setminus F_{(i,j), (k,l)}(F^{-1}_{(i,0),(k,l)}(\Sigma_{i0} \setminus A^*_{i0}) ) \\ & \supset F_{(i,j), (k,l)} (\Sigma_{kl}) \setminus F^{-1}_{(i,0),(i,j)}(\Sigma_{i0} \setminus \Sigma^*_{i0}) \\ & = F_{(i,j), (k,l)} (\Sigma_{kl}) \setminus (\Sigma_{ij} \setminus \Sigma^*_{ij}) \\ & = F_{(i,j), (k,l)} (\Sigma_{kl}) \cap \Sigma^*_{ij}. \end{align*} $$

However, clearly $F_{(i,j), (k,l)} (\Sigma ^*_{kl}) \subset F_{(i,j), (k,l)} (\Sigma _{kl}) \cap \Sigma ^*_{ij}$ , and equation (12.2) is proved.

In cases (H2) and (H3), the set $F_{(i,j), (k,l)}(\Sigma _{kl})$ is closed in $\Sigma _{ij}$ by Remarks 2.1, 4.3, and Theorem 7.1. We infer from equation (12.2) that $F_{(i,j), (k,l)} (\Sigma ^*_{kl})$ is a Zariski closed subset of $\Sigma ^*_{ij}$ . Therefore, $\varprojlim _{i, j \in \mathbb {N}} \Sigma ^{*}_{ij} \neq \varnothing $ results from Lemma 3.3 and equation (12.1) is proved in all cases.

We can thus choose $x =(x_{ij})_{i, j \in \mathbb {N}} \in \varprojlim _{i,j \in \mathbb {N}} \Sigma ^{*}_{ij}$ . Let $\Phi \colon \varprojlim _{i,j \in \mathbb {N}} \Sigma _{ij} \to \Omega (\tau )$ be the map given in Theorem 9.1. As $\varprojlim _{i,j \in \mathbb {N}} \Sigma ^{*}_{ij} \subset \varprojlim _{i,j \in \mathbb {N}} \Sigma _{ij}$ , we obtain ${y_0= \Phi (x) \in \Omega (\tau )}$ . As $y_0(1_G) = x_{00}(1_G)$ by definition of $\Phi $ and as $x_{00}(1_G) \neq 0$ since $x_{00} \in \Sigma ^*_{00}$ , we deduce that $\Omega (\tau ) \neq \{0^G\}$ . This contradiction shows that (b) $\implies $ (a).

13 Nilpotency over finite alphabets

The following theorem strengthens and extends to any infinite group some results established for full shifts over $G = \mathbb {Z}$ by Culik, Pachl, and Yu [18, Theorem 3.5] and by Guillon and Richard [24, Corollary 4].

Suppose that X is a topological space equipped with a continuous action of a group G. One says that the dynamical system $(X,G)$ is topologically mixing if for each pair of non-empty open subsets U and V of X, there exists a finite subset $F \subset G$ such that $U \cap gV \neq ~\varnothing $ for all $g \in G \setminus F$ . Given a group G and a finite set A, a closed subshift ${\Sigma \subset A^G}$ is said to be topologically mixing provided $(\Sigma ,G)$ is topologically mixing. If $(X,G)$ is a topologically mixing dynamical system and $f \colon X \to X$ is a continuous G-equivariant map, then the factor system $(f(X), G)$ is also topologically mixing.

Theorem 13.1. Let G be an infinite group, let A be a finite set, and let $\Sigma \subset A^G$ be a non-empty topologically mixing subshift of sub-finite-type (e.g. $\Sigma = A^G$ , or, if G is finitely generated, $\Sigma $ is of finite type). Let $\tau \colon \Sigma \to \Sigma $ be a cellular automaton. Then the following conditions are equivalent:

1. (a) $\tau $ is nilpotent;

2. (b) the limit set $\Omega (\tau )$ is reduced to a single configuration;

3. (c) the limit set $\Omega (\tau )$ is finite.

If G is finitely generated, then the above conditions are equivalent to

1. (d) the limit set $\Omega (\tau )$ consists only of periodic configurations.

Before starting the proof of the above theorem, we present a preliminary lemma. The result is probably well known, but since we could not find any reference, we include a proof for the sake of completeness.

Lemma 13.2. Let G be a finitely generated group, let A be a set, and let $\Sigma \subset A^G$ be a finite subshift. Then $\Sigma $ is of finite type.

Roughly, the idea is simple. Every configuration $x \in \Sigma $ has a finite orbit, equivalently, its stabilizer $H_x = \operatorname {\mathrm {Stab}}_G(x)$ is of finite index in G. Since the intersection of finitely many finite-index subgroups is of finite index, the group is of finite index in G. Moreover, by the Poincaré lemma, there exists a finite index normal subgroup $K\!\subset H$ . This way, we can embed $\Sigma $ into $A^{G/K}$ (cf. [10, Proposition 1.3.7]). As $G/K$ is finite, it follows that $\Sigma $ is of finite type. The proof below is a detailed and self-contained version of the above idea. See [16, Proposition 2.4] for a linear version (where ‘finite’ becomes ‘finite-dimensional’).

Proof of Lemma 13.2

Let $S \subset G$ be a finite generating subset of G. After replacing S by $S \cup S^{-1} \cup \{1_G\}$ , we can assume that $S = S^{-1}$ and $1_G \in S$ . Then, given any element $g \in G$ , there exist $n \in \mathbb {N}$ and $s_1, s_2, \ldots , s_n \in S$ such that $g = s_1s_2 \cdots s_n$ . The minimal $n \in \mathbb {N}$ in such an expression of g is the S-length of g, denoted by $\ell _S(g)$ .

For all distinct $x,y \in \Sigma $ , we can find $g = g_{x,y} \in G$ such that $x(g) \neq y(g)$ . Then the finite set satisfies

(13.1) $$ \begin{align} x\vert_{D_0} = y\vert_{D_0}\quad \mbox{implies } x = y \mbox{ for all } x \in \Sigma. \end{align} $$

Let us show that $\Sigma = \Sigma (D,P)$ for $D = SD_0$ and . By definition, we have

(13.2) $$ \begin{align} \Sigma(D,P) &= \{x \in A^G : \mbox{ for all } g \in G \mbox{ there exists } x_g \in \Sigma \mbox{ such that }\notag \\ &\qquad (g^{-1} x)(d) = x_g(d) \text{ for all } d \in D \}. \end{align} $$

Note that the element $x_g \in \Sigma $ in equation (13.2) is uniquely defined by $x \in \Sigma (D,P)$ and $g \in G$ , since $D \supset D_0$ so that $x_g\vert _D = x_g'\vert _D$ infers $x_g = x_g'$ by equation (13.1).

We clearly have $\Sigma \subset \Sigma (D,P)$ , since $\Sigma $ is G-invariant.

For the converse inclusion, suppose that $x \in \Sigma (D,P)$ and let us show that ${x = x_{1_G} \in \Sigma }$ . We prove by induction on the S-length of g that

(13.3) $$ \begin{align} x_g = g^{-1}x_{1_G} \end{align} $$

for all $g \in G$ . If $\ell _S(g) = 0$ , then $g = 1_G$ and equation (13.3) holds trivially. Suppose now that $\ell _S(g) = n$ and let $s \in S$ . Given $d_0 \in D_0$ we have, on the one hand, $x(gsd_0) = (g^{-1}x)(sd_0) = x_g(sd_0) = s^{-1}x_g(d_0)$ , and, on the other hand, $x(gsd_0) = ((gs)^{-1}x)(d_0) = x_{gs}(d_0)$ . This shows that $(s^{-1}x_g)\vert _{D_0} = x_{gs}\vert _{D_0}$ . Since $s^{-1}x_g$ and $x_{gs}$ both belong to $\Sigma $ , we deduce from equation (13.1) that $s^{-1}x_g = x_{gs}$ . By induction, we have $x_g = g^{-1}x_{1_G}$ so that $x_{gs} = (gs)^{-1}x_{1_G}$ . This proves equation (13.3). From equation (13.3) we obtain, for every $g \in G$ ,

$$ \begin{align*} x(g) = (g^{-1}x)(1_G) = x_g(1_G) = g^{-1}x_{1_G}(1_G) = x_{1_G}(g). \end{align*} $$

This shows that $x = x_{1_G} \in \Sigma $ .

Proof of Theorem 13.1

The equivalence (a) $\iff $ (b) follows from Theorem 1.4. The implication (b) $\implies $ (c) is obvious.

Suppose now that $\Omega (\tau )$ is finite. Let $M \subset G$ be a finite subset which serves as a memory set for both $\tau $ and $\Sigma $ , and denote by $H \subset G$ the subgroup it generates. Let $\tau _H \colon \Sigma _H \to \Sigma _H$ denote the corresponding restriction cellular automaton. It follows from Lemma 2.9 that $\Omega (\tau ) = \Omega (\tau _H)^{G/H}$ . If G is not finitely generated, then $G/H$ is infinite and necessarily $\Omega (\tau _H)$ and therefore $\Omega (\tau )$ must consist of a single element, as $\Omega (\tau )$ is non-empty (cf. Theorem 1.3). This proves the implication (c) $\implies $ (b) for G not finitely generated.

If G is finitely generated, it follows from Lemma 13.2 that $\Omega (\tau )$ is a subshift of finite type. Since A is finite, the characterization of subshifts of finite type in Theorem 10.1 can be applied to the sequence

$$ \begin{align*} \Sigma \supset \tau(\Sigma) \supset \tau^2(\Sigma) \supset \cdots \supset \Omega(\tau) = \bigcap_{n \in \mathbb{N}} \tau^n(\Sigma), \end{align*} $$

and implies that there exists $n_0 \in \mathbb {N}$ such that $\Omega (\tau ) = \tau ^{n_0}(\Sigma )$ . Therefore, $\Omega (\tau )$ is a factor of $\Sigma $ . Since $\Sigma $ is topologically mixing, so is $\Omega (\tau )$ . Now let $x, y \in \Omega (\tau )$ . As $\Omega (\tau )$ is finite and Hausdorff, $\{x\}$ and $\{y\}$ are open in $\Omega (\tau )$ . Thus, by topological mixing of $\Omega (\tau )$ , there exists a finite subset $F \subset G$ such that $x = gy$ for all $g \in G \setminus F$ . Since $\Omega (\tau )$ is finite, the stabilizer H of y in G is an infinite subgroup of G. It follows that $H \cap (G \setminus F) \neq \varnothing $ . Taking $g \in H \cap (G \setminus F)$ yields $x = gy = y$ . Hence, $\Omega (\tau )$ is a singleton and this concludes the proof of the implication (c) $\implies $ (b).

Finally, suppose that G is finitely generated. As any finite G-invariant subset of $A^G$ necessarily consists only of periodic configurations, we have (c) $\implies $ (d). The reverse implication follows from the finiteness of closed subshifts containing only periodic configurations proved in [4, Theorem 5.8] and in [32, Theorem 1.4] (see also [5, Theorem 3.8] for the case $G= \mathbb {Z}^2$ ). Note that since $A^G$ is compact and $\tau $ is continuous, $\Omega (\tau )$ is closed in $A^G$ .

14 Proof of Theorem 1.5

By Corollary 8.2, we know that $\Sigma $ is closed in $A^G$ . The equivalence (a) $\iff $ (b) thus results from Proposition A.5. It is trivial that (a) $\implies $ (c) $\implies $ (d). For the implications (d) $\implies $ (a) and (c) $\implies $ (a), let $M \subset G$ be a finite subset containing the memory sets of both $\tau $ and $\Sigma $ such that $1_G \in M$ and $M=M^{-1}$ . Let H be the subgroup of G generated by M. Let $\tau _H \colon \Sigma _H \to \Sigma _H$ denote the restriction cellular automaton. By Lemma 2.9(i), we have $\Omega (\tau ) = \Omega (\tau _H)^{G/H}$ . Thus, if $\Omega (\tau )$ is finite, then so is $\tau (\tau _H)$ . Likewise, if item (d) holds for $\tau $ , then $\{ x(1_G) \colon x \in \Omega (\tau _H) \}$ is finite and $\Omega (\tau _H)$ consists of periodic configurations as well. However, $\tau $ is nilpotent if $\tau _H$ is nilpotent by Lemma 2.9(ii). Therefore, up to replacing G by H, we can assume that G is finitely generated by M. It then suffices to show that (d) $\implies $ (a) as we already know that (c) $\implies $ (d).

Assume that item (d) holds. Then is finite. As $\Omega (\tau )$ is G-invariant, $x(g)\in T$ for every $x \in \Omega (\tau )$ and $g \in G$ .

Let $(\Sigma _{ij})_{i, j \in \mathbb {N}}$ be the space-time inverse system associated with $\tau $ and the memory set M. We set for every $i \geq 0$ , and define for every $i \geq 0$ and $j \geq 1$ :

$$ \begin{align*} \Sigma^*_{ij}= (q_{i 0} \circ \cdots \circ q_{i, j-1})^{-1}(\Sigma_{i0}^*) \subset \Sigma_{ij}. \end{align*} $$

The unit transition maps $p^*_{ij} \colon \Sigma ^*_{i+1, j} \to \Sigma ^*_{ij}$ and $q^*_{ij} \colon \Sigma ^*_{i, j+1} \to \Sigma ^*_{i j}$ are respectively the restrictions of the transition maps $p_{ij}$ and $q_{ij}$ of the system $(\Sigma _{ij})_{i, j \in \mathbb {N}}$ .

Suppose first that $\Sigma ^*_{ij} \neq \varnothing $ for all $i, j \in \mathbb {N}$ . Then exactly as in the proof of Theorem 1.4, there exists $x =(x_{ij})_{i, j \in \mathbb {N}} \in \varprojlim _{i,j \in \mathbb {N}} \Sigma ^{*}_{ij}$ and we obtain $y_0 = \Phi (x) \in \Omega (\tau )$ with $y_0(1_G) = x_{00}(1_G)$ . However, $x_{00}(1_G) \notin T$ because $x_{00} \in \Sigma ^*_{00}$ , we find that $\Omega (\tau ) \not \subset T^G$ , which is a contradiction.

Therefore, we must have $\Sigma ^*_{ij}= \varnothing $ for some $i, j \in \mathbb {N}$ . If $j=0$ , then $\Sigma ^*_{i0}= \varnothing $ and $x(1_G) \in T$ for all $x \in \Sigma _{i0}$ . We deduce that $A^G \subset T^G$ and thus $A \subset T$ is finite. As G is infinite and $\Omega (\tau )$ contains only periodic configurations, Theorem 13.1 implies that $\tau $ is nilpotent. If $j \geq 1$ , then by definition of $\Sigma _{ij}$ , we have for every $x \in \Sigma _{ij}$ that

$$ \begin{align*} (q_{i 0} \circ \cdots \circ q_{i, j-1}) (x)(1_G) \in T. \end{align*} $$

Hence, as $\tau ^{j}$ is G-equivariant, we deduce that $\tau ^{j}(x) \in T^G$ for every $x \in A^G$ . Thus, the restriction is a well-defined cellular automaton. As a subset of $\Omega (\tau )$ , the set $\Omega (\sigma )$ also consists of periodic configurations. We deduce from Theorem 13.1 that $\sigma $ is nilpotent, say, $\sigma ^m(x) = x_0$ for all $x \in T^G$ for some $m \in \mathbb {N}$ and $x_0 \in A^G$ . It follows that $\tau ^{(m+1)j}(x)= \sigma ^m(\tau ^{j} (x) ) =x_0$ for all $x \in A^G$ . We conclude that $\tau $ is nilpotent. The proof of the theorem is completed.

15 Counter-examples

The following example (cf. [11, Example 5.1] and [14, Example 8.1]) shows that Theorem 8.1 and assertions (i) and (iii) of Theorem 1.3 become false if we remove the hypothesis that the ground field K is algebraically closed.

Example 15.1. Let be the additive group of integers and let denote the affine line over $\mathbb {R}$ . Then . Consider the cellular automaton $\tau \colon \mathbb {R}^{\mathbb {Z}} \to \mathbb {R}^{\mathbb {Z}}$ with memory set and associated local defining map $\mu \colon \mathbb {R}^M \to \mathbb {R}$ defined by $\mu (p) = p(1) - p(0)^2$ for all $p \in \mathbb {R}^M$ . Clearly, $\tau $ is an algebraic cellular automaton over $(G,V,\mathbb {R})$ . Indeed, $\mu $ is induced by the algebraic morphism $f\colon V^2 \to V$ associated with the morphism of $\mathbb {R}$ -algebras

$$ \begin{align*} \mathbb{R}[t] & \to \mathbb{R}[t_0,t_1] \\ t & \mapsto t_1-t_0^2. \end{align*} $$

Note that $\tau \colon \mathbb {R}^{\mathbb {Z}}\to \mathbb {R}^{\mathbb {Z}}$ is given by

$$ \begin{align*} \tau(c)(n) = c(n+1) - c(n)^2\quad \text{for all } c\in \mathbb{R}^{\mathbb{Z}} \text{ and } n \in \mathbb{Z}. \end{align*} $$

Claim 15.2. The limit set $\Omega (\tau )$ is a dense non-closed subset of $\mathbb {R}^{\mathbb {Z}}$ . In particular, $\Omega (\tau )$ is not a closed subshift of $\mathbb {R}^{\mathbb {Z}}$ .

Proof. Let $c \in \mathbb {R}^{\mathbb {Z}}$ and let $F \subset \mathbb {Z}$ be a finite subset. Choose an integer $m \in \mathbb {Z}$ such that $F\subset [m,\infty )$ and consider the configuration $d \in \mathbb {R}^{\mathbb {Z}}$ defined by if $n < m$ and if $n \geq m$ . For each $k \in \mathbb {N}$ , define by induction on k a configuration $d_k \in \mathbb {R}^{\mathbb {Z}}$ in the following way. We first take $d_0 = d$ . Then, assuming that the configuration $d_k$ has been defined, we define the configuration $d_{k + 1}$ , using induction on n, by if $n \leq m$ and if $n \geq m$ . Clearly, $\tau (d_{k + 1}) = d_k$ so that $d = d_0 = \tau ^k(d_k)$ for all $k \in \mathbb {N}$ . Therefore, $d \in \Omega (\tau )$ . Since c and d coincide on $[m,\infty )$ and hence on F, this shows that c is in the closure of $\Omega (\tau )$ . Thus, $\Omega (\tau )$ is dense in $\mathbb {R}^{\mathbb {Z}}$ .

In [11, Example 5.1] and [14, Example 8.1], it is shown that $\operatorname {\mathrm {Im}}(\tau )$ is not closed of $R^{\mathbb {Z}}$ and the constant configuration $e\in \mathbb {R}^{\mathbb {Z}}$ , defined by for all $n\in \mathbb {Z}$ , does not belong to $\operatorname {\mathrm {Im}}(\tau )$ . This implies that $e \notin \Omega (\tau )$ . As $\Omega (\tau )$ is dense in $\mathbb {R}^{\mathbb {Z}}$ , we deduce that $\Omega (\tau )$ is not closed in $\mathbb {R}^{\mathbb {Z}}$ .

Remark that $\operatorname {\mathrm {Im}}(\tau )$ is an algebraic sofic subshift of $\mathbb {R}^{\mathbb {Z}}$ since it is the image of the full shift $\mathbb {R}^{\mathbb {Z}}$ under the algebraic cellular automaton $\tau $ . Thus, an algebraic sofic subshift may fail to be closed in the ambient full shift.

For every integer $n \geq 1$ , the set is a memory set for $\tau ^n$ . Let $\mu _n \colon \mathbb {R}^{M_n} \to \mathbb {R}$ denote the associated local defining map. We shall use the fact that for each $n \geq 1$ , there exists a polynomial $\nu _n \in \mathbb {R}[t_0, \ldots , t_{n-1}]$ such that for every $p \in \mathbb {R}^{M_n}$ ,

(15.1) $$ \begin{align} \mu_n(p) = p(n) + \nu_n(p(0), \ldots, p(n-1)). \end{align} $$

This fact can be proved by an easy induction. For $n=1$ , we have $\mu _1(p) = \mu (p) = p(1) - p(0)^2$ for every $p \in \mathbb {R}^{M_1}$ so that we can take $\nu _1(t_0)= - t_0^2$ . Suppose now that the assertion holds for some $n\geq 1$ . Let $c \in \mathbb {R}^{\mathbb {Z}}$ and let $d = \tau ^{n}(c)$ . By the induction hypothesis, we have that $d(0)= \mu _n(c(0), \ldots , c(n))$ and

$$ \begin{align*} d(1) = \mu_n(c(1), \ldots, c(n+1)) = c(n+1) + \nu_n(c(1), \ldots, c(n)). \end{align*} $$

Therefore, we get

$$ \begin{align*} \tau^{n+1}(c)(0) & = \tau(\tau^{n}(c))(0) = \tau(d)(0) = d(1) - d(0)^2 \\ & = c(n+1) + \nu_k(c(1), \ldots, c(n)) - \mu_n(c(0), \ldots, c(k))^2 \\ & = c(n+1) + \nu_{n+1}(c(0), \ldots, c(n)), \end{align*} $$

where $\nu _{n+1} \in \mathbb {R}[t_0, \ldots , t_{n}]$ is given by the formula

Thus, for every $p \in \mathbb {R}^{M_{n+1}}$ ,

$$ \begin{align*} \mu_{n+1}(p) = p(n+1) + \nu_{n+1}(p(0), \ldots, p(n)), \end{align*} $$

and the assertion follows by induction.

Claim 15.3. For every configuration $c \in \mathbb {R}^{\mathbb {Z}}$ and any integer $n \geq 1$ , there exists $d \in \mathbb {R}^{\mathbb {Z}}$ such that $d(k) = c(k)$ for all $k \leq 0$ and $\tau ^{n}(d)(k)=c(k)$ for all $k \geq -n+1$ .

Proof. Let $c \in \mathbb {R}^{\mathbb {Z}}$ . We define $d \in \mathbb {R}^{\mathbb {Z}}$ by

$$ \begin{align*} d(k) = c(k) \quad \mbox{if } k \leq 0 , \end{align*} $$

and inductively for $k \geq 1$ by

(15.2)

By applying equations (15.1) and (15.2), we obtain, for every $k \geq -n+1$ ,

$$ \begin{align*} \tau^{n}(d)(k) & = \mu_{n}(d(k), \ldots, d(n+k)) \\ & = d(n+k) + \nu_{n}(d(k), \ldots, d(k+n-1)) \\ & = c(k), \end{align*} $$

and the claim is proved.

Claim 15.4. The set $\operatorname {\mathrm {R}}(\tau )$ is a dense non-closed subset of $\mathbb {R}^{\mathbb {Z}}$ . In particular, $\operatorname {\mathrm {R}}(\tau )$ is not a closed subshift of $\mathbb {R}^{\mathbb {Z}}$ .

Proof. Let $c \in \mathbb {R}^{\mathbb {Z}}$ . For each $n_0 \geq 1$ , define by induction on $n \geq n_0$ a configuration ${d_n \in \mathbb {R}^{\mathbb {Z}}}$ in the following way. Let $d_{n_0} = c$ . Then, assuming that the configuration $d_n$ has been defined, we can choose by Claim 15.3 and the $\mathbb {Z}$ -equivariance of $\tau $ a configuration $d_{n + 1}$ satisfying $d_{n+1}(k) = d_n(k)$ for $k \leq 2 \cdot 3^{n}$ and $\tau ^{3^{n+1}}(d_{n+1})(k) = d_n(k)$ for $k \geq -3^n+1$ .

Hence, we can define $d \in \mathbb {R}^{\mathbb {Z}}$ by setting $d(k)= d_n(k)$ for any $n \geq n_0$ such that ${k \leq 2 \cdot 3^{n}}$ . Let $n \geq n_0$ . Remark that $M_{3^{n+1}}$ is a memory set of $\tau ^{3^{n+1}}$ and $d(k)= d_{n+1}(k)$ for $k \leq 2 \cdot 3^{n+1}$ . Hence, for $-3^n +1 \leq k \leq 3^n$ so that in particular $3^{n+1} + k \leq 2 \cdot 3^{n+1}$ , we have

(15.3) $$ \begin{align} \tau^{3^{n+1}}(d)(k) = \tau^{3^{n+1}}(d_{n+1})(k) = d_n(k) =d(k). \end{align} $$

Since this holds for all $n \geq n_0$ and as every finite subset is contained in $\{ -3^n+1 , \ldots , 3^n\}$ for any large enough n, we deduce that $d \in \operatorname {\mathrm {R}}(\tau )$ .

It is clear from the construction that $d_n(k)= c(k)$ for every $n \geq n_0$ and $k \leq 2 \cdot 3^{n_0}$ . Thus, $d(k) = c(k)$ for every $k \leq 2 \cdot 3^{n_0}$ . As $n_0 \geq 1$ is arbitrary, it follows that every $c \in \mathbb {R}^{\mathbb {Z}}$ belongs to the closure of $\operatorname {\mathrm {R}}(\tau )$ . In other words, $\operatorname {\mathrm {R}}(\tau )$ is dense in $\mathbb {R}^{\mathbb {Z}}$ .

The set $\operatorname {\mathrm {R}}(\tau )$ is not closed in $\mathbb {R}^{\mathbb {Z}}$ . Indeed, the configuration $e \in \mathbb {R}^{\mathbb {Z}}$ , given by $e(k) = 1$ for all $k \in \mathbb {Z}$ , does not belong to $\operatorname {\mathrm {R}}(\tau )$ since $\tau ^n(e)(0) = 0 \not = c(0)$ for all $n \geq 1$ .

Claim 15.5. One has $\operatorname {\mathrm {NW}}(\tau ) = \operatorname {\mathrm {CR}}(\tau ) = \mathbb {R}^{\mathbb {Z}}$ .

Proof. By Claim 15.4, the set $\operatorname {\mathrm {R}}(\tau )$ is dense in $\mathbb {R}^{\mathbb {Z}}$ . Since $\operatorname {\mathrm {NW}}(\tau )$ and $\operatorname {\mathrm {CR}}(\tau )$ are closed in $\mathbb {R}^{\mathbb {Z}}$ and contain $\operatorname {\mathrm {R}}(\tau )$ , we deduce that $\operatorname {\mathrm {NW}}(\tau ) = \operatorname {\mathrm {CR}}(\tau ) = \mathbb {R}^{\mathbb {Z}}$ .

Claim 15.6. One has $\operatorname {\mathrm {R}}(\tau ) \not \subset \Omega (\tau )$ and $\Omega (\tau ) \not \subset \operatorname {\mathrm {R}}(\tau )$ .

Proof. By the proof of Claim 15.2, we know that the configuration $c \in \mathbb {R}^{\mathbb {Z}}$ , given by $c(k)=0$ if $k \leq - 1$ and $c(k)=1$ if $k \geq 0$ , belongs to $\Omega (\tau )$ . However, as $\tau ^n(c)(0)=0 \neq c(0)$ for every $n \geq 1$ , it follows that $c \notin \operatorname {\mathrm {R}}(\tau )$ .

However, reconsider the configuration $e \in \mathbb {R}^{\mathbb {Z}}$ given by $e(k)=1$ for every $k \in \mathbb {Z}$ . The proof of Claim 15.4 actually shows that there exists $d \in \operatorname {\mathrm {R}}(\tau )$ such that ${d(k)= e(k)=1}$ for all $k \leq 0$ . Suppose that there exists $b \in \mathbb {R}^{\mathbb {Z}}$ such that $\tau (b)= d$ . Then $b(k+1) = 1 + b(k)^2$ for all $k \leq 0$ . Thus, $1 \leq b(k) \leq b(k+1)$ for all $k \leq 0$ , so that the limit exists and is finite. By passing to the limit in the relation $b(k+1) = 1 + b(k)^2$ , we find that $t=1+t^2$ , which is a contradiction as t must be real. This shows that $d \notin \tau (\mathbb {R}^{\mathbb {Z}})$ and thus $d \notin \Omega (\tau )$ . The proof is completed.

Remark 15.7. Consider the complex version of Example 15.1, that is, let $\tau _{\mathbb {C}} \colon \mathbb {C}^{\mathbb {Z}} \to \mathbb {C}^{\mathbb {Z}}$ be the algebraic cellular automaton over $(\mathbb {Z}, {\mathbb {A}}^1_{\mathbb {C}},\mathbb {C})$ with memory set $M = \{0,1\}\subset \mathbb {Z}$ and associated local defining map $\mu _{\mathbb {C}} \colon \mathbb {C}^M \to \mathbb {C}$ defined by $\mu _{\mathbb {C}}(p) = p(1) - p(0)^2$ for all $p \in \mathbb {C}^M$ .

Then the same proofs as in Claims 15.4 and 15.5 show that $\operatorname {\mathrm {R}}(\tau _{\mathbb {C}})$ is a dense non-closed subset of $\mathbb {C}^{\mathbb {Z}}$ and that $\operatorname {\mathrm {NW}}(\tau _{\mathbb {C}}) = \operatorname {\mathrm {CR}}(\tau _{\mathbb {C}}) = \mathbb {C}^{\mathbb {Z}}$ . By applying Theorem 1.3(ii), we deduce that $\Omega (\tau _{\mathbb {C}}) = \mathbb {C}^{\mathbb {Z}}$ , that is, $\tau _{\mathbb {C}}$ is surjective, which can also be easily checked by a direct verification.

The following example shows that assertion (v) of Theorem 1.3 becomes false if we remove the hypothesis that the ground field K is algebraically closed.

Example 15.8. Let G be a group and let denote the affine line over $\mathbb {R}$ . Consider the algebraic morphism $f \colon V \to V$ given by $t \mapsto t^2 + 1$ . Take and let $\tau \colon A^G \to A^G$ denote the cellular automaton with memory set and associated local defining map $\mu \colon A^M = A \to A$ given by $a \mapsto a^2 + 1$ . The cellular automaton $\tau $ is algebraic since $\mu $ is induced by f but its limit set $\Omega (\tau )$ is clearly empty. Remark also that $\tau $ is not stable since otherwise, $\Omega (\tau )$ would be non-empty.

The following example shows that Theorem 1.4 becomes false if we remove the hypothesis that the ground field K is algebraically closed.

Example 15.9. Let G be a group and let denote the projective line over $\mathbb {R}$ . Consider the algebraic morphism $f \colon V \to V$ given by $(x \colon y) \mapsto (x^2 + y^2 \colon y^2)$ . Take and let $\tau \colon A^G \to A^G$ denote the cellular automaton with memory set and associated local defining map $\mu \colon A^M = A \to A$ given by $a \mapsto a^2 + 1$ . The cellular automaton $\tau $ is algebraic since $\mu $ is induced by f. Clearly, the limit set $\Omega (\tau )$ is reduced to the constant configuration $g \mapsto \infty $ but $\tau $ is not nilpotent.

16 Generalizations

Using basic properties of proper morphisms, it is not hard to see that all the results for case (H2) (respectively for case $(\mathrm {\widetilde {H2}})$ in Theorem 8.1) remain valid if V (respectively $V_0$ ) is assumed to be separated (and not necessarily complete). For this, it suffices to remark that images of morphisms from a complete algebraic variety to a separated algebraic variety (cf. [31, §3.3.1]) are Zariski closed complete subvarieties (cf. [31, §3.3.2]). This leads us to the following definition.

Definition 16.1. Let G be a group and let V be a separated algebraic variety over a field K. Let . A subset $\Sigma \subset A^G$ is called a complete algebraic sofic subshift if it is the image of an algebraic subshift of finite type $\Sigma ' \subset B^G$ , where $B=U(K)$ and U is a complete K-algebraic variety, under an algebraic cellular automaton $\tau ' \colon B^G \to A^G$ .

With the above definition, Theorem 10.1 can also be extended as follows without any changes in the proof.

Theorem 16.2. Let G be a finitely generated group. Let V be a separated algebraic variety over an algebraically closed field K. Let $A=V(K)$ and let $\Sigma \subset A^G$ be a complete algebraic sofic subshift. Then following are equivalent:

1. (a) $\Sigma $ is a subshift of finite type;

2. (b) $\Sigma $ is an algebraic subshift of finite type;

3. (c) every descending sequence of algebraic sofic subshifts of $A^G$

   $$ \begin{align*} \Sigma_0 \supset \Sigma_1 \supset \cdots \supset \Sigma_n \supset \Sigma_{n+1} \supset \cdots \end{align*} $$
   such that $\bigcap _{n \geq 0} \Sigma _n = \Sigma $ eventually stabilizes.

Now, let G be a group and let V be an algebraic variety over a field K. Let $A=V(K)$ and let $\Sigma \subset A^G$ be a subset.

Definition 16.3. $\Sigma \subset A^G$ is called a countably proconstructible subshift of finite type (CPSFT) if there exist a finite subset $D \subset G$ and a subset $W \subset V^D$ which is the complement in $V^D$ of a countable number of constructible subsets (cf. §3), such that $\Sigma = \Sigma (D,W(K))$ . Similarly, $\Sigma \subset A^G$ is a countably proconstructible sofic subshift (CPS subshift) if it is the image of a CPSFT under an algebraic cellular automaton with range  $A^G$ .

Our proofs actually show that Theorem 1.3 (except point (iv)), Theorem 1.4 (respectively Theorem 1.5) still hold if we replace hypotheses (H1), (H2), and (H3) and the assumption $\Sigma \subset A^G$ being an algebraic sofic subshift (respectively a topologically mixing algebraic sofic subshift) by a more general hypothesis:

1. (H) K is an uncountable algebraically closed field and $\Sigma \subset A^G$ is a $\operatorname {\mathrm {CPS}}$ subshift (respectively topologically mixing $\operatorname {\mathrm {CPS}}$ subshift) and $\tau \colon \Sigma \to \Sigma $ is an algebraic cellular automaton.

In fact, it can be directly checked from our proofs that results for case (H1) in §6 (respectively §§7 and 8) remain valid if we assume that K is an uncountable algebraically closed field and $\Sigma $ is a $\operatorname {\mathrm {CPSFT}}$ (respectively a $\operatorname {\mathrm {CPS}}$ subshift).

We now introduce a non-trivial class of non-empty $\operatorname {\mathrm {CPSFT}}$ (cf. Theorem 16.6).

Definition 16.4. Let G be a group. Let V be an algebraic variety over a field K and let $A= V(K)$ . A subshift $\Sigma \subset A^G$ is called a full $\operatorname {\mathrm {CPSFT}}$ if there exist a finite subset ${D \subset G}$ and a subset $W = V^D \setminus ( \bigcup _{n \in \mathbb {N}} U_n)$ where each $U_n \subset V^D$ is a constructible subset satisfying $\dim U_n < \dim V^D$ , such that $\Sigma = \Sigma (D, W(K))$ . Here, $\dim Z$ denotes the Krull dimension of a constructible subset Z (see for example [15]).

Remark that if V is finite, that is, $\dim V=0$ , the conditions $\dim U_n < \dim V^D$ imply that $U_n = \varnothing $ for every $n \in \mathbb {N}$ , thus $W=V^D$ . Hence, when the alphabet is finite, the only full $\operatorname {\mathrm {CPSFT}}$ is the full shift.

Example 16.5. If $G= \mathbb {Z}$ , $A = \mathbb {C}$ , $D= \{0, 1\} \subset \mathbb {Z}$ , $W = \mathbb {C}^D \setminus E$ , where $E \subset \mathbb {C}^D \simeq \mathbb {C}^2$ is any countable union of complex algebraic curves and points, then $\Sigma ' = \Sigma (D, W) \subset \mathbb {C}^{\mathbb {Z}}$ is a non-empty full CPSFT (by Theorem 16.6). Let $\tau ' \colon \mathbb {C}^{\mathbb {Z}} \to \mathbb {C}^{\mathbb {Z}}$ be given by $\tau '(x)(n) = x(n)^2 - x(n+1) +1$ for every $x \in \mathbb {C}^{\mathbb {Z}}, n \in \mathbb {Z}$ , then is a non-empty closed CPS subshift of $\mathbb {C}^{\mathbb {Z}}$ (by Theorem 8.1 which is true under the condition (H)). Note that is an algebraic cellular automaton.

Theorem 16.6. Let G be a group. Let V be a non-empty algebraic variety over an uncountable algebraically closed field K and let $A= V(K)$ . Then every full $\operatorname {\mathrm {CPSFT}} \Sigma \subset A^G$ is non-empty.

Proof. We write $\Sigma = \Sigma (D, W(K))$ for some finite subset $D \subset G$ and $W = V^D \setminus ( \bigcup _{n \in \mathbb {N}} U_n)$ , where $U_n \subset V^D$ , $n \in \mathbb {N}$ , is a constructible subset such that $\dim U_n < \dim V^D$ . In particular, W is a countably proconstructible subset of $V^D$ . Suppose first that G is finitely generated and let the notation be as in §5. Then the same proof for case (H1) of Proposition 6.2 actually implies that $\Sigma _{ij} = \bigcap _{k \geq i} p_{ijk}(A_{kj})$ for $i, j \in \mathbb {N}$ , where $ A_{ij} = \bigcap _{g \in D_{ij}} \pi _{ij,g}^{-1} (gW) (K) \subset A^{M^{i+j}} $ (cf. equation (6.1)). Note that $D_{ij}$ is finite and $g W \simeq W$ for all $g \in G$ . It follows immediately that $A_{ij}$ is also a complement of a countable number of constructible subsets $Z_n$ such that $\dim Z_n < \dim A^{M^{i+j}}$ for every $n \in \mathbb {N}$ . Hence, for every finite subset $I \subset \mathbb {N}$ , the constructible set $\bigcap _{n \in I} (A^{M^{i+j}} \setminus Z_n) \neq \varnothing $ by the dimensional reason. By Lemma 3.2, we deduce that $A_{ij} = \bigcap _{n \in \mathbb {N}} (A^{M^{i+j}} \setminus Z_n) \neq \varnothing $ for every $i, j \in \mathbb {N}$ . Always by Lemma 3.2, $\Sigma _{ij} = \bigcap _{k \geq i} p_{ijk}(A_{kj}) \neq \varnothing $ for all $i, j \in \mathbb {N}$ and thus $ \varprojlim _{i \in \mathbb {N}} \Sigma _{ij} \neq \varnothing $ . Finally, the bijection $\Sigma \simeq \varprojlim _{i \in \mathbb {N}} \Sigma _{ij}$ (cf. equation (4.6)) implies that $\Sigma \neq \varnothing $ .

For an arbitrary group G, let H be the subgroup generated by D. Then by Lemma 2.8, we have a factorization $\Sigma = \prod _{c \in G/H} \Sigma _c$ where the sets $\Sigma _c$ are pairwise homeomorphic. By the above paragraph, we know that $\Sigma _H \neq \varnothing $ and therefore $\Sigma \neq \varnothing $ .

Theorem 16.6 serves as a motivation for the notion of full CPSFT as we see in the following comparison with the finite alphabet case. It is well known that for $G= \mathbb {Z}^d$ , $d \geq 2$ , and for a finite set A of cardinality at least 2, it is algorithmically undecidable whether the subshift of finite type $\Sigma (D,P) \subset A^G$ is non-empty for a given finite subset $D \in G$ and a given subset $ P \subset A^D$ . This is known as the domino problem (cf. [2, 7, 49]; see also the recent [6], where a notion of ‘simulation’ for labeled graphs is introduced and applied to the domino problem for the Cayley graph of the lamplighter group and, more generally, to Diestel–Leader graphs).