Glider automorphisms and a finitary Ryan’s theorem for transitive subshifts of finite type

Let \(X\subseteq A^{\mathbb {Z}}\) be a one-dimensional subshift over a symbol set A. If w is a finite word over A, we may say that an element \(x\in X\) is w-finite if it begins and ends with infinite repetitions of w. In this paper we consider the problem of constructing reversible shift-commuting continuous maps (automorphisms) on X which decompose all w-finite configurations into collections of gliders traveling into opposing directions. As a concrete example, consider the binary full shift \(X=\{0,1\}^{\mathbb {Z}}\) and the map \(g=g_3\circ g_2\circ g_1:X\rightarrow X\) defined as follows. In any \(x\in X\), \(g_1\) replaces every occurrence of 0010 by 0110 and vice versa, \(g_2\) replaces every occurrence of 0100 by 0110 and vice versa, and \(g_3\) replaces every occurrence of 00101 by 00111 and vice versa. In Fig. 1 we have plotted the sequences \(x,g(x),g^2(x),\dots\) on consecutive rows for some 0-finite \(x\in X\). It can be seen that the sequence x eventually diffuses into two different “fleets”, the one consisting of 1 s going to the left and the one consisting of 11 s going to the right. It can be proved, along similar lines as in the proofs of Lemmas 6 and 7, that this diffusion happens eventually no matter which finite initial point \(x\in X\) is chosen. In Sect. 4 we construct, on all nontrivial mixing SFTs, a function that we call a diffusive glider automorphism and that has the same diffusion property as the binary automorphism g above.

The existence of such a diffusive glider automorphism g on a subshift X is interesting, because g can be used to convert an arbitrary finite \(x\in X\) into another sequence \(g^t(x)\) (for some \(t\in {{\mathbb {N}}_+}\)) with a simpler structure, which nevertheless contains all the information concerning the original point x because g is invertible. Such maps have been successfully applied to other problems. We give some examples. The paper (Salo 2017) contains a construction of a finitely generated group G of automorphisms of \(A^{\mathbb {Z}}\) (when \(\vert A \vert =4\)) whose elements can implement any permutation on any finite collection of 0-finite non-constant configurations that belong to different shift orbits. An essential part of the construction is that one of the generators of G is a diffusive glider automorphism on \(A^{\mathbb {Z}}\). Another example is the construction of a physically universal cellular automaton g on \(A^{\mathbb {Z}}\) (when \(\vert A \vert =16\)) in Salo and Törmä (2017). Also here it is essential that g is a diffusive glider automorphism (but g also implements certain additional collision rules for gliders).

We also consider a finitary version of Ryan’s theorem. Let X be a mixing SFT and denote the set of its automorphisms by \({{\,\mathrm{Aut}\,}}(X)\), which we may consider as an abstract group. According to Ryan’s theorem (Boyle et al. 1988; Patrick Ryan 1972) the center of the group \({{\,\mathrm{Aut}\,}}(X)\) is generated by the shift map \(\sigma\). There may also be subsets \(S\subseteq {{\,\mathrm{Aut}\,}}(X)\) whose centralizers C(S) are generated by \(\sigma\). Denote the minimal cardinality of such a finite set S by k(X). In Salo (2017) it was proved that \(k(X)\le 10\) when X is the full shift over the four-letter alphabet. In the same paper it is noted that k(X) is an isomorphism invariant of \({{\,\mathrm{Aut}\,}}(X)\) and therefore computing it could theoretically separate \({{\,\mathrm{Aut}\,}}(X)\) and \({{\,\mathrm{Aut}\,}}(Y)\) for some mixing SFTs X and Y. Finding good isomorphism invariants of \({{\,\mathrm{Aut}\,}}(X)\) is of great interest, and it is an open problem whether for example \({{\,\mathrm{Aut}\,}}(\{0,1\}^{\mathbb {Z}})\cong {{\,\mathrm{Aut}\,}}(\{0,1,2\}^{\mathbb {Z}})\) [Problem 22.1 in Boyle (2008)]. We show that \(k(X)=2\) for all nontrivial mixing SFTs, the proof of which uses our diffusive glider automorphism construction and Lemma 1 (Main lemma). It is then a simple corollary that \(k(X)=2\) for every transitive SFT X that does not consist of the orbit of a single periodic point. The diffusive glider automorphism construction and the proof of \(k(X)=2\) was done for mixing SFTs containing a fixed point in the paper (Kopra 2018) published in the proceedings of AUTOMATA 2018.

Lemma 1 is a criterion saying essentially that if S is a collection of automorphisms that acts together with the diffusive glider automorphism g in a special way, then \(C(S\cup \{g\})\) is not very complicated. We have formulated a reasonably general version of the lemma to allow its application in other contexts. To further showcase our Main lemma, we consider an alternative finitary variant of Ryan’s theorem. In Sect. 7.3 of Salo (2017) the question was raised whether for a mixing SFT X and for every \(G\subseteq {{\,\mathrm{Aut}\,}}(X)\) such that \(C(G)=\left\langle \sigma \right\rangle\) there is a finite subset \(S\subseteq G\) such that also \(C(S)=\left\langle \sigma \right\rangle\). In the same section it was noted that to construct a counterexample it would be sufficient to find a locally finite group \(G\subseteq {{\,\mathrm{Aut}\,}}(X)\) whose centralizer is generated by \(\sigma\). We use a different strategy based on Lemma 1 to construct a counterexample in the case when X is the binary full shift.

A finite set A containing at least two elements (letters) is called an alphabet and the set \(A^{\mathbb {Z}}\) of bi-infinite sequences (configurations) over A is called a full shift. Formally any \(x\in A^{\mathbb {Z}}\) is a function \({\mathbb {Z}}\rightarrow A\) and the value of x at \(i\in {\mathbb {Z}}\) is denoted by x[i]. It contains finite and one-directionally infinite subsequences denoted by \(x[i,j]=x[i]x[i+1]\cdots x[j]\), \(x[i,\infty ]=x[i]x[i+1]\cdots\) and \(x[-\infty ,i]=\cdots x[i-1]x[i]\). Occasionally we signify the symbol at position zero in a configuration x by a dot as follows:A factor of \(x\in A^{\mathbb {Z}}\) is any finite sequence x[i, j] where \(i,j\in {\mathbb {Z}}\), and we interpret the sequence to be empty if \(j<i\). Any finite sequence \(w=w[1] w[2]\cdots w[n]\) (also the empty sequence, which is denoted by \(\lambda\)) where \(w[i]\in A\) is a word over A. The concatenation of a word or a left-infinite sequence u with a word or a right-infinite sequence v is denoted by uv. A word u is a prefix of a word or a right-infinite sequence x if there is a word or a right-infinite sequence v such that \(x=uv\). Similarly, u is a suffix of a word or a left-infinite sequence x if there is a word or a left-infinite sequence v such that \(x=vu\). The set of all words over A is denoted by \(A^*\), and the set of non-empty words is \(A^+=A^*{\setminus }\{\lambda \}\). More generally, for any \(L\subseteq A^*\), leti.e. \(L^*\) is the set of all finite concatenations of elements of L. The set of words of length n is denoted by \(A^n\). For a word \(w\in A^*\), \(\vert w \vert\) denotes its length, i.e. \(\vert w \vert =n\iff w\in A^n\). Given \(x\in A^{\mathbb {Z}}\) and \(w\in A^+\) we define the sets of left (resp. right) occurrences of w in x byNote that both of these sets contain the same information up to a shift in the sense that \(\text {occ}_{\hbox {r}}(x,w)=\text {occ}_\ell (x,w)+\vert w \vert -1\). Typically we refer to the left occurrences and we say that \(w\in A^n\) occurs in \(x\in A^{\mathbb {Z}}\) at position i if \(i\in \text {occ}_\ell (x,w)\). We define the shift map \(\sigma _A:A^{\mathbb {Z}}\rightarrow A^{\mathbb {Z}}\) by \(\sigma _A(x)[i]=x[i+1]\) for \(x\in A^{\mathbb {Z}}\), \(i\in {\mathbb {Z}}\). The subscript A in \(\sigma _A\) is typically omitted. The set \(A^{\mathbb {Z}}\) is endowed with the product topology (with respect to the discrete topology on A), under which \(\sigma\) is a homeomorphism on \(A^{\mathbb {Z}}\). For any \(S\subseteq A^{\mathbb {Z}}\) the collection of words appearing as factors of elements of S is the language of S, denoted by L(S). Any closed set \(X\subseteq A^{\mathbb {Z}}\) such that \(\sigma (X)=X\) is called a subshift. The restriction of \(\sigma\) to X may be denoted by \(\sigma _X\), but typically the subscript X is omitted. The orbit of a point \(x\in X\) is \({\mathcal {O}}(x)=\{\sigma ^i(x)\mid i\in {\mathbb {Z}}\}\).

For any word \(w\in A^+\) we denote by \({}^\infty w\) and \(w^\infty\) the left- and right-infinite sequences obtained by infinite repetitions of the word w. We denote by \(w^{\mathbb {Z}}\in A^{\mathbb {Z}}\) the configuration defined by \(w^{\mathbb {Z}}[in,(i+1)n-1]=w\) (where \(n=\vert w \vert\)) for every \(i\in {\mathbb {Z}}\). We say that \(x\in A^{\mathbb {Z}}\) is w-finite if \(x[-\infty ,i]={}^\infty w\) and \(x[j,\infty ]=w^\infty\) for some \(i,j\in {\mathbb {Z}}\).

We say that subshifts \(X\subseteq A^{\mathbb {Z}}\) and \(Y\subseteq B^{\mathbb {Z}}\) are conjugate if there is a continuous bijection (a conjugacy) \(\psi :X\rightarrow Y\) such that \(\psi \circ \sigma _X=\sigma _Y\circ \psi\).

Although the notation for the set \(E^s\) of incoming edges of s is similar to the notation for the set \(E^n\) of words of length n over E, in practice the distinction should be clear from the context.

A sequence of edges \(e[1]\cdots e[n]\) in a graph \({\mathcal {G}}=(V,E)\) is a path (of length n) if \(\tau (e[i])=\iota (e[i+1])\) for \(1\le i<n\), it is a cycle if in addition \(\tau (e[n])=\iota (e[1])\) and it is a simple cycle if in addition \(\iota (e[i])\) for \(1\le i\le n\) are all distinct. We say that the path starts at \(\iota (e[1])\) and ends at \(\tau (e[n])\). A graph \({\mathcal {G}}\) is irreducible if for every \(v_1,v_2\in V\) there is a path starting at \(v_1\) and ending at \(v_2\) and it is primitive if there is \(n\in {{\mathbb {N}}_+}\) such that for every \(v_1,v_2\in V\) there is a path of length n starting at \(v_1\) and ending at \(v_2\). For any graph \({\mathcal {G}}=(V,E)\) we call the set(i.e. the set of bi-infinite paths on \({\mathcal {G}}\)) the edge subshift of \({\mathcal {G}}\).

The centralizer of a set \(S\subseteq {{\,\mathrm{Aut}\,}}(X)\) isand the subgroup generated by \(S\subseteq {{\,\mathrm{Aut}\,}}(X)\) is denoted by \(\left\langle S\right\rangle\). The following definition is from Salo (2017):

It is proven in Patrick Ryan (1972) and as Theorem 7.7 in Boyle et al. (1988) that \(k(X)\ne \perp\) whenever X is a mixing SFT. The following observation is from Sect. 7.6 of Salo (2017).

For conjugate subshifts X and Y it necessarily holds that \(k(X)=k(Y)\).

In this section we prove as our main lemma a useful criterion which can be used to significantly restrict the kinds of automorphisms that can occur in C(G) when \(G\subseteq {{\,\mathrm{Aut}\,}}(X)\) is chosen carefully. We state a reasonably general version of the lemma to make it applicable in many different contexts. A special case occurs as part of the proof of Theorem 14 in Kopra (2018).

The idea of an abstract diffusive glider automorphism group is the following. For any \({\bf 0}\)-finite \(x\in X\) there is a \(g\in G\) that can be used to “diffuse” x into a point g(x) such that elements of \({\mathcal {O}}(g(x))\) locally look like elements of some \(\mathrm {GF}_i\), and in practice \(\overline{\mathrm {GF}_i}\) will be in some sense simpler subshifts than X. The local shift maps \({\varsigma }_i\) are used to dynamically distinguish the points in \(\mathrm {GF}_i{\setminus }{\mathcal {O}}({\bf 0}^{\mathbb {Z}})\). In the proof of our main lemma we will also require that the points of \(\mathrm {GF}_i\) consist of gliders in a more concrete sense. We encode this in the following definition.

For X and \({\bf 0}\) as above we let \({{\,\mathrm{Aut}\,}}(X,{\bf 0})=\{f\in {{\,\mathrm{Aut}\,}}(X)\mid f({\mathcal {O}}({\bf 0}^{\mathbb {Z}}))={\mathcal {O}}({\bf 0}^{\mathbb {Z}})\}\). For \(x,y\in A^{\mathbb {Z}}\) and \(i\in {\mathbb {Z}}\) we denote by \(x\otimes _i y\in A^{\mathbb {Z}}\) the “gluing” of x and y at i, i.e. \((x\otimes _i y)[-\infty ,i-1]=x[-\infty ,i-1]\) and \((x\otimes _i y)[i,\infty ]=y[i,\infty ]\). Typically we perform gluings at the origin and we denote \(x\otimes y=x\otimes _0y\).

In the next lemma we need the notion of a bipartite non-directed graph. By this we mean a pair \({\mathcal {B}}=(V,E)\) where V is the set of vertices with a nontrivial partition \(V=V_1\cup V_2\) and \(E\subseteq V_1\times V_2\) is the set of edges, i.e. an edge cannot connect two vertices belonging in the same element of the partition. V and E are not necessarily finite. We say that \({\mathcal {B}}\) is connected if the equivalence relation on V generated by E is equal to \(V\times V\), which is equivalent to saying that it is possible to traverse between any two vertices by a finite path in which edges can be crossed in both directions.

Before the proof we continue our previous example and show how this lemma can be applied to it.

In our example the construction of a nontrivial diffusive glider automorphism g was simple because of the existence of a decomposition \(A^{\mathbb {Z}}=B^{\mathbb {Z}}\times B^{\mathbb {Z}}\). On more general subshifts we cannot rely on such decompositions. In the example we also augmented G by an automorphism f and got a group \(G'\) satisfying the assuptions of Lemma 1. The construction of such a map f will be essentially the same in all our later applications of the lemma. To gain a better understanding of Main Lemma, it may be helpful to consider how the following proof would go in the case of the previous example.

In this section we construct for an arbitrary nontrivial mixing SFT X (with a distinguished periodic point \({\bf 0}^{\mathbb {Z}}\)) an automorphism g which breaks every \({\bf 0}\)-finite point of X into a collection of gliders traveling in opposite directions. More precisely, we will construct a diffusive glider automorphism \(g:X'\rightarrow X'\) for a subshift \(X'\) which is conjugate to X (via some conjugacy \(\phi :X\rightarrow X'\)) but has a graph presentation that makes our constructions simpler. Then the map \(\phi ^{-1}\circ g\circ \phi\) is an abstract diffusive glider automorphism on X.

To begin, consider a nontrivial mixing SFT X defined by a graph \({\mathcal {G}}=(V,E)\) and let \({\bf 0}=0_1\cdots 0_p\in E^p\) be some fixed simple cycle in \({\mathcal {G}}\). We will want, among other things, that occurrences of the letters \(0_i\) can only occur within occurrences of the word \({\bf 0}\) in points of X. We start with some auxiliary definitions.

We emphasize that if w is a deterministic path, we do not require that w[1] has a unique predecessor or that w[n] has a unique successor.

Now let X be a nontrivial mixing SFT. By applying the three previous lemmas consecutively, we may assume up to conjugacy that X is defined by a graph \({\mathcal {G}}=(V,E)\) such that \({\mathcal {G'}}\), \({\bf 0}\), \({\bf{1}}\), etc. are as in the conclusion of the previous lemma. In the rest of this section we will construct a diffusive glider automorphism \(g:X\rightarrow X\) with the associated diffusive glider automorphism group \((\left\langle g\right\rangle ,{\bf 0},{\mathcal {I}},\boxed {\leftrightarrow },{\mathrm {spd}},{\varsigma },\mathrm {GF})\). Let \({\mathcal {I}}=\{\ell ,{\hbox {r}}\}\), \({\mathrm {spd}}(\ell )=pq\) and \({\mathrm {spd}}({\hbox {r}})=-pq\), which reflect the fact that we will have left- and rightbound gliders. The gliders will benote that these are of equal length \((p+1)q\). We define the glider fleet setsand languagesSince \({\mathcal {G'}}\) is primitive, it has a mixing constant \(n\ge \vert {\bf{1}} \vert ^{p+2}\), i.e. a number such that for every \(n'\ge n\) and \(s,s'\in V'\) there is a path of length \(n'\) in \({\mathcal {G'}}\) from s to \(s'\). Denote \(N=2n\) and for each \(a\in E'\cup \{0_1\}\) let \(W_a'=\{w_{a,1},\dots , w_{a,k_a}\}\subseteq E'^{N}\) be the set of all those words over \(E'\) of length N such that \(w_{a,i}\) does not have prefix \({\bf{1}}^{p+2}\) and \(0_p w_{a,i} a\in L(X)\) for \(1\le i\le k_a\), let \(w_a\in E'^{N}\) be some single word with prefix \({\bf{1}}^{p+2}\) such that \(0_p w_a a\in L(X)\) (such a word \(w_a\) exists by the choice of the mixing constant n), and denote \(W_a=W_a'\cup \{w_a\}\). For each \(j\in \{1,\dots , p\}\) let \(u_j'={\bf{1}}^{p+1+j}\) and let \(U_j'=\{u_{j,1}',\dots ,u_{j,n_j}'\}\subseteq E'^+\) be all the cycles from \(s_1\) to \(s_1\) (which may visit \(s_1\) several times) of length at most \(N-1\) such that \(\vert u_{j,i}' \vert \equiv \vert u_j' \vert \pmod p\) and \(u_{j,i}'\) does not have prefix \({\bf{1}}^{p+2}\), with the additional restriction that \({\bf{1}},{\bf{1}}^{p+1}\notin U_p'\). Finally, these words are padded to constant length; let \(u_j={\bf 0}^{c_j}u_j'\) and \(u_{j,i}={\bf 0}^{c_{j,i}}u_{j,i}'\), where \(c_j, c_{j,i}\ge 100N\) are chosen in such a way that all \(u_j\), \(u_{j,i}\) are of the same length for any fixed j. The words in \(W_a\) and \(U_j'\) have been chosen so as to allow the following structural definition.

We outline a deterministic method to narrow down the word w of the previous definition in a way that clarifies its existence and uniqueness. First, by the maximality of i it follows that \(x[i]\in E'\). If \(x[i,i+N-1]\in E'^N\), then \(w\in W_{x[i+N]}'x[i+N]\) directly by the definition of the sets \(W_a'\) unless \(x[i,\infty ]\) has prefix \({\bf{1}}^{p+2}\), in which case \(w={\bf{1}}^{p+2}\) is the only option. Otherwise \(x[i,i+N-1]\notin E'^N\) and there is a minimal \(m<N\) such that \(x[i,i+m-1]\in E'^m\) and \(x[i+m,i+m+p-1]={\bf 0}\). Then \(x[i,i+m-1]\) is a cycle of length \(m<N\) from \(s_1\) to \(s_1\) and \(w\in U_j'{\bf 0}\) for some \(j\in \{1,\dots ,p\}\) unless we have specifically excluded \(x[i,i+m-1]\) from all the sets \(U_j'\). But this happens precisely if \(x[i,i+m-1]\in \{{\bf{1}},{\bf{1}}^{p+1}\}\) or \(x[i,i+m-1]\) has prefix \({\bf{1}}^{p+2}\). In these cases \(w\in \{{\bf{10}},{\bf{1}}^{p+1}{\bf 0},{\bf{1}}^{p+2}\}\).

The point of this definition is that if x is of left bound type (w, k), then the diffusive glider automorphism g defined later will eventually create a new leftbound glider at position k and break it off from the rest of the configuration. (A possible exception to this is if \(w={\bf{1}}^{p+1}{\bf 0}=\boxed {\rightarrow }{\bf 0}\), in which case it might happen that the rightbound glider just travels to the right.)

We define four automorphisms \(g_1,g_2,g_3,g_4:X\rightarrow X\) as follows. In any \(x\in X\),It is easy to see that these maps are well-defined automorphisms of X. The automorphism \(g:X\rightarrow X\) is defined as the composition \(g_4\circ g_3\circ g_2\circ g_1\). We commence arguing that g is a diffusive glider automorphism with respect to \((\left\langle g\right\rangle ,{\bf 0},{\mathcal {I}},\boxed {\leftrightarrow },{\mathrm {spd}},{\varsigma },\mathrm {GF})\), where we choose \({\varsigma }_\ell ={\varsigma }_{\hbox {r}}=g\).

We first give a heuristic argument showing that g could be a diffusive glider automorphism. It is easier to convince oneself that with the choices \(g'=g_2\circ g_1\), \(G=\left\langle g',g_3,g_4\right\rangle\) and \({\varsigma }_\ell '={\varsigma }_{\hbox {r}}'=g'\) the tuple \((G,{\bf 0},{\mathcal {I}},\boxed {\leftrightarrow },{\mathrm {spd}},{\varsigma }',\mathrm {GF})\) is a diffusive glider automorphism group. Namely, the previous lemma would hold even if g were replaced by \(g'\), and it also seems reasonable that \(\mathrm {GF}_\ell\), \(\mathrm {GF}_{\hbox {r}}\) are glider fleet sets with respect to \({\varsigma }_\ell '\), \({\varsigma }_{\hbox {r}}'\) in the sense of Definitions 5 and 6, so \(g'\) is a glider automorphism. It remains to show diffusiveness. If \(x\in X\) is \({\bf 0}\)-finite, then \(x_1=g'^i(x)\) for large \(i\in {\mathbb {N}}\) contains gliders very far from the origin going to opposing directions and possibly there is an occurrence of a word \({\bf 0}^M w\) (with large \(M\in {\mathbb {N}}\)) that does not look like a glider near the origin. Then for some j, the occurrence of this word is replaced in \(x_2=g_4^j(x_1)\) by \({\bf 0}^{M'}{\bf{1}}^{p+2}\), and then \(g_3\) separates an occurrence of a glider from this pattern; \(x_3=g_3(x_2)\) contains \(\boxed {\leftarrow }\) near the origin which can be shifted away by sufficiently many applications of \(g'\). By repeating this argument we find an element \({\overline{g}}\in G\) such that \({\overline{g}}(x)\) contains only leftbound gliders far to the left and rightbound gliders far to the right, so in particular the last item in Definition 5 is satisfied.

The reason why \(g=g_4\circ g_3\circ g'\) could also have the diffusion property is that the words in points \(x\in X\) on which \(g'\), \(g_3\) and \(g_4\) can act nontrivially are for the most part distinct, e.g. \(g_3\) can change occurrences of the word \({\bf 0}^{q+1}({\bf{1}}^{p+2})\) but in the definition of \(g_4\) this occurs as a subword only in \({\bf 0}^{q+1} w_a a\) and \({\bf 0}u_j {\bf 0}\). Therefore, whenever one component in the map g does something conductive to the diffusion of x, it is unlikely that this effect is immediately reversed by some other component. We proceed with the actual proof that g is a diffusive glider automorphism.

In this section we prove our finitary version of Ryan’s theorem. This is done by applying Lemma 1. As in Example 3, we need a suitable automorphism f to augment the diffusive glider automorphism group of Theorem 2.

As earlier, let X be a mixing SFT from the conclusion of Lemma 4 and consider the notation of the previous section. First we define maps \(f_1,f_2:X\rightarrow X\) as follows. In any \(x\in X\),It is easy to see that these maps are well-defined automorphisms of X. The automorphism \(f:X\rightarrow X\) is then defined as the composition \(f_2\circ f_1\). Similarly to Example 3, f has the following properties. First, it replaces any occurrence of \({\bf 0}\boxed {\rightarrow }{\bf{000}}\boxed {\leftarrow }{\bf 0}\) by \({\bf{00}}\boxed {\rightarrow }{\bf 0}\boxed {\leftarrow }{\bf{00}}\). Second, if \(x\in X\) is a configuration containing only gliders \(\boxed {\leftarrow }\) and \(\boxed {\rightarrow }\) and every occurrence of \(\boxed {\leftarrow }\) is sufficiently far from every occurrence of \(\boxed {\rightarrow }\), then \(f(x)=x\).

Finitary Ryan’s theorem can be interpreted as a compactness result saying that, for nontrivial mixing SFT X, the group \({{\,\mathrm{Aut}\,}}(X)\) has a finite subset S such that \(C(S)=\left\langle \sigma \right\rangle\). One may wonder whether this compactness phenomenon is more general: if \(G\subseteq {{\,\mathrm{Aut}\,}}(X)\) is an arbitrary infinite set such that \(C(G)=\left\langle \sigma \right\rangle\), does there exist a finite \(F\subseteq G\) such that \(C(F)=\left\langle \sigma \right\rangle\)? We will show by an example that this is not true for general G even if X is the binary full shift.

In this section let \(X=\{0,1\}^{\mathbb {Z}}\). For every \(n\in {{\mathbb {N}}_+}\) we define two automorphisms \(g_{n,1},g_{n,2}:X\rightarrow X\) as follows. In any \(x\in X\),It is easy to see that these maps are well-defined automorphisms of X. The maps \(g_n:X\rightarrow X\) are defined as the compositions \(g_{n,2}\circ g_{n,1}\). We will define a tuple \((G',0,{\mathcal {I}},\boxed {\leftrightarrow },{\mathrm {spd}},{\varsigma },\mathrm {GF})\), which will turn out to be a diffusive glider automorphism group for the binary full shift X. Let \(G'=\left\langle \{g_n\mid i\in {{\mathbb {N}}_+}\}\right\rangle\) and let \({\mathcal {I}}=\{(n,{\hbox {r}})\mid n\in {{\mathbb {N}}_+}\}\cup \{(n,\ell )\mid n\in {{\mathbb {N}}_+}\}\) be the index set. We define gliders \(\boxed {\leftrightarrow }_{n,\ell }=\boxed {\leftarrow }_n=01^{2n-1}\) and \(\boxed {\leftrightarrow }_{n,{\hbox {r}}}=\boxed {\rightarrow }_n=1^{2n}\) and glider fleet setsWe define languagesFor \(n\in {{\mathbb {N}}_+}\) we let \({\mathrm {spd}}(n,\ell )=1\), \({\mathrm {spd}}(n,{\hbox {r}})=-1\) and \({\varsigma }_{(n,{\hbox {r}})}={\varsigma }_{(n,\ell )}=g_n\).

We construct the group G generated by \(G'\) and all automorphisms \(f_{n,m}=f_{n,m,2}\circ f_{n,m,1}\) for \(n,m\in {{\mathbb {N}}_+}\) defined as follows. In any \(x\in X\),It is easy to see that these maps are well-defined automorphisms of X. Similarly to Example 3, the map \(f_{n,m}\) has two important properties. First, it replaces any occurrence of \(0\boxed {\rightarrow }_n 000\boxed {\leftarrow }_m0\) by \(00\boxed {\rightarrow }_n0\boxed {\leftarrow }_m00\). Second, if \(x\in X\) is a configuration containing only gliders \(\boxed {\leftarrow }_{m}\) and \(\boxed {\rightarrow }_{n}\) and every occurrence of \(\boxed {\leftarrow }_{m}\) is sufficiently far from every occurrence of \(\boxed {\rightarrow }_n\), then \(f_{n,m}(x)=x\).

The following two propositions conclude our current example.

We have constructed diffusive glider automorphisms g for nontrivial mixing SFTs X (with some fixed periodic point \({\bf 0}^{\mathbb {Z}}\)) that decompose all \({\bf 0}\)-finite configurations into two fleets of gliders traveling into opposing directions. This construction was somewhat complicated and finding a simpler construction (and/or a simpler proof) would be desirable. One might also want to construct diffusive glider automorphisms on general mixing SFTs with several different types of gliders that travel at different speeds and that would satisfy some carefully specified collision rules (this is simpler on full shifts when the cardinality of the alphabet is not a prime, see e.g. Salo and Törmä (2017) for the case of the full shift \(A^{\mathbb {Z}}\) with \(\vert A \vert =16\)).

We have applied these glider maps to prove for any nontrivial mixing SFT X that \(k(X)=2\). As a simple corollary we have also shown that \(k(X)=2\) for any transitive SFT X that consists of more than a single orbit. It would be interesting to find more sensitive isomorphism invariants of \({{\,\mathrm{Aut}\,}}(X)\). As one possible invariant related to k(X) we suggestIt is previously known by Theorem 7.17 of Salo (2017) that \(k_2(A^{\mathbb {Z}})\in {\mathbb {N}}\) when \(\vert A \vert =4\). Some upper bounds for this quantity for general transitive SFTs can be given by noting that the automorphisms in Proposition 1 can be represented as compositions of involutions. However, it might be difficult to recognize an optimal upper bound when it has been found. For example, we do not know the answer to the following.

We have also given an example of a finitary variant of Ryan’s theorem which is not true, i.e. there exists \(G\subseteq {{\,\mathrm{Aut}\,}}(\{0,1\}^{\mathbb {Z}})\) such that \(C(G)=\left\langle \sigma \right\rangle\) but \(C(F)\supsetneq \left\langle \sigma \right\rangle\) for every finite \(F\subseteq G\).