1 Introduction
Starting with the work of Hadamard [Reference Hadamard18] and the highly influential article of Hedlund and Morse [Reference Hedlund and Morse21], symbolic dynamical systems have quite often played a pivotal role in the understanding of more general dynamics. A celebrated instance of this is the prominent role of subshifts of finite type (SFT) in the study of Anosov, and more generally of Axiom A diffeomorphisms, through Markov partitions of their non-wandering sets [Reference Bowen9]. Another well-known example of this tight relationship is the fact that the natural action of a word-hyperbolic group on its boundary is a very well behaved topological factor of an SFT on the same group [Reference Coornaert and Papadopoulos16].
These and similar results raise the question of understanding precisely which dynamical systems are topological factors of SFTs. An observation made by Hochman [Reference Hochman22] is that subactions of multidimensional SFTs satisfy strong computability constraints. More precisely, they must be computable maps on effectively closed sets in the sense that the complement of the space of orbits must consist on a union of cylinders whose defining words can be enumerated by a Turing machine. However, the truly remarkable discovery of Hochman is that, up to a difference in the dimension of the acting group and a topological factor, this is the only constraint: every computable homeomorphism on an effectively closed zero-dimensional set is the topological factor of a subaction of a
$\mathbb {Z}^3$
-SFT.
Results linking computable maps on effectively closed zero-dimensional sets to SFTs are called ‘simulation results’, as they express that very explicit and simple models such as SFTs are capable of universally encoding this considerably larger class of dynamical systems. These simulation results along with further developments [Reference Aubrun and Sablik2, Reference Durand, Romashchenko, Shen, Blass, Dershowitz and Reisig17] led to a new understanding of classical results in the theory of symbolic dynamics of group actions, such as the undecidability of the domino problem [Reference Berger7, Reference Wang35], the existence of aperiodic tilesets [Reference Berger7, Reference Robinson30], and, more generally, the existence of two-dimensional tilings without computable orbits [Reference Hanf19, Reference Myers28]. Moreover, they also provided the tools to obtain new and long sought-after results, such as the classification of topological entropies of multidimensional SFTs [Reference Hochman and Meyerovitch23].
Further work has extended the initial result of Hochman to the context of actions of discrete groups on zero-dimensional spaces [Reference Barbieri3, Reference Barbieri and Sablik4, Reference Barbieri, Sablik and Salo6]. Notably, it was shown that for a large class of non-amenable groups called self-simulable, the class of zero-dimensional topological factors of SFTs contains every possible computable action on an effectively closed zero-dimensional set [Reference Barbieri, Sablik and Salo5]. These works have led to new results about the dynamics of such groups. For instance, they have provided new examples of groups that can act freely, expansively, and with shadowing on a zero-dimensional space.
A common theme among all of the previous simulation results is that they apply to actions on zero-dimensional spaces. The reason behind this is rooted in the fact that the Cantor space
$\{0,1\}^{\mathbb {N}}$
admits a natural computable structure, where the cylinders are described by finite words, and that allows the application of algorithmic techniques. The main objective of this paper is to explore a generalization to groups acting on non-symbolic spaces, such as compact subsets of
$\mathbb {R}^n$
,
$\operatorname {GL}_n(\mathbb {C})$
or compact abelian groups such as
$(\mathbb {R}/\mathbb {Z})^n$
. Thus, the goal of this article is to explore the following question.
Question 1.1. Can the simulation results be extended to group actions on spaces that are not zero-dimensional?
The theory of computable analysis offers the means to endow separable metric spaces with computable structures that allow the notion of a computable map to make sense and the application of algorithmic techniques possible. In this paper, we explore this approach and study its connections with the existing simulation results. In particular, we introduce a very general notion of an effective dynamical system (EDS) and show that all of the known simulation results can be extended to this class. By an effective dynamical system, we mean one that is topologically conjugate to a computable action over a recursively compact subset of a computable metric space. We do not require the topological conjugacy to be computable, so an EDS does not need to be computable itself. The class of EDS is therefore quite large and encompasses virtually all natural examples (although artificial non-examples can be constructed, see §8). Our main tool will be the following result.
Theorem A. Let
$\Gamma $
be a finitely generated and recursively presented group. For any effective dynamical system
$\Gamma \curvearrowright X$
, there exists an effectively closed zero-dimensional space
$\widetilde {X}\subset \{0,1\}^{\mathbb {N}}$
and a computable action
$\Gamma \curvearrowright \widetilde {X}$
such that
$\Gamma \curvearrowright X$
is a topological factor of
$\Gamma \curvearrowright \widetilde {X}$
.
We remark that is it a well-known fact that every group action by homeomorphisms on a compact metrizable space admits a zero-dimensional extension. This extension, however, carries a priori no computable structure. Our contribution is that, for recursively presented groups, the computable structure stemming from the effective nature of the system is preserved by a well-chosen zero-dimensional extension.
Given a finitely generated group
$\Gamma $
and an epimorphism
$\psi \colon \Gamma \to H$
, we say that
$\Gamma $
simulates H if given any computable action of H on an effectively closed subset of the Cantor space, the corresponding action of
$\Gamma $
induced through
$\psi $
is a factor of a
$\Gamma $
-SFT. If
$\psi $
is an isomorphism, then
$\Gamma $
is called self-simulable. The class of self-simulable groups includes several interesting examples, see Theorem 5.2.
The main application of Theorem A is that for recursively presented groups, the simulation results in the literature also apply to EDS.
Theorem B. Let
$\Gamma ,H$
be finitely generated groups and
$\psi \colon \Gamma \to H$
be an epimorphism. Suppose that H is recursively presented, then
$\Gamma $
simulates H if and only if for every effective dynamical system
$H \curvearrowright X$
, the induced action of
$\Gamma $
is a topological factor of a
$\Gamma $
-SFT.
Combining this result with the simulations result in the literature, we obtain that many dynamical systems on non-zero-dimensional spaces can be realized as factors of subshifts of finite type. This includes the natural action of
$\operatorname {GL}_n(\mathbb {Z}) \curvearrowright \mathbb {R}^n/\mathbb {Z}^n$
by left matrix multiplication for
$n \geq 5$
, actions of
$F_2\times F_2$
on the circle by computable rotations on each generator, actions of the braid groups
$B_n$
for
$n \geq 7$
on compact computable groups, and more.
To better illustrate the power of Theorem B, we develop in detail a particular application which we believe could be of special interest. An action of a countable group on a compact abelian topological group by automorphisms is called algebraic. This is a rich class of group actions which has been the object of much study in the literature, for instance, in [Reference Chung and Li15, Reference Lind and Schmidt25, Reference Lind, Schmidt and Ward26, Reference Schmidt32]. Using our results, we obtain that a large class of algebraic actions of non-amenable groups can be presented as topological factors of SFTs.
Theorem C. Let
$\Gamma $
be a finitely generated and recursively presented self-simulable group. Every finitely presented algebraic action of
$\Gamma $
is the topological factor of a
$\Gamma $
-subshift of finite type.
In fact, this result applies to an even larger class of algebraic actions which admit ‘recursive presentations’, see Definition 6.5.
We complete our discussion with several observations. There exist at least two notions of computability for shift spaces present in the literature (Corollary 7.7). We discuss their connection to the notion of EDS and show that for recursively presented groups, they all coincide. We also completely characterize the relations between these notions for groups which are not recursively presented. We then focus on the class of topological factors of EDS. While it is true that computable factors of EDS are EDS (Proposition 3.30), the class of EDS is, in general, not closed under topological factor maps. We provide two examples of this fact, one as a non-EDS factor of an EDS on a compact subset of
$\mathbb {C}$
, and the other as a non-EDS zero-dimensional factor of a zero-dimensional EDS. In the case of zero-dimensional spaces, we propose a new notion (Definition 8.4) of weak effective dynamical system (WEDS). We show that for recursively presented groups, every zero-dimensional factor of an EDS is a WEDS (Proposition 8.9), and that the class of WEDS is closed under topological factor maps. This class of systems can be thought of as those that can be written as an inverse limit of effective subshifts, but with the caveat that the effectiveness of the sequence of subshifts is not required to be uniform. Using this notion, we naturally recover the fact that the class of subshifts which are EDS is closed under topological factor maps.
1.1 Paper organization
After some preliminaries, we give an introduction to computable analysis and the precise definition of an EDS in §3. The proof of Theorem A along with a few interesting side remarks are provided in §4. In particular, we show that for zero-dimensional EDS, we may always consider the canonical computable structure induced by the cylinder sets and that, in this case, we do not need the hypothesis that the acting group is recursively presented. We also show that in the case where the action admits a generating cover, the extension can be taken to be an effective subshift. In §5, we summarize the simulation results in the literature, prove Theorem B, and discuss several examples. In §6, we present the relevant background for Theorem C along with its proof. In §7, we turn our attention back to shift spaces and study the relationship between the different notions of computability for subshifts. Finally, in §8, we construct the examples showing that the class of EDS is not closed by topological factor maps, introduce the class of WEDS, show that this class is closed by factor maps, and discuss their relationship with EDS.
2 Preliminaries
2.1 Computability on countable sets
A formal introduction to the theory of computation can be found in [Reference Rogers31] or [Reference Sipser33]. Here, we will provide a brief functional description. We will make use of the word algorithm to refer to a Turing machine [Reference Turing34]. The reader may think about a Turing machine as a computer program written in any standard programming language which receives some finite information called input, then proceeds to sequentially execute a finite set of instructions. Depending on these instructions and the input, the execution may at some halt and return some finite information, called output, or it may not halt, in which case, the execution will continue forever without ever providing an output. The notion of algorithm characterizes mathematical objects according to the extent to which they can be computed. Depending on what exactly the algorithm is required to compute, we will use different names for them in our definitions (computable, effective, decidable, etc).
Let us start by functions over words. For a set A, denote by
$A^* = \bigcup _{n \in \mathbb {N}}A^n$
the set of all words on A. Let
$A,B$
be finite sets (called alphabets in this setting). A partial function
$f\colon A^* \to B^*$
is a function which is not necessarily defined in all of
$A^*$
. A computable function is a partial function
$f\colon A^* \to B^*$
for which there exists an algorithm which on input
$w \in A^*$
, halts if and only if f is defined on w, in which case it outputs
$f(w)$
. We say that a partial function is total if it is defined on every element of
$A^*$
.
We may also define computable functions on other countable sets by representing them through words in a canonical way. For instance, we will represent non-negative integers using the alphabet
$A = \{\mathtt {0},\mathtt {1}\}$
through their binary representation. Note that this is a ‘good’ representation in the sense that comparing or adding integers boils down to computable functions on their representations. Similarly, we can represent rational numbers, tuples in
$\mathbb {N}^d$
, or sequences in
$\mathbb {N}^*$
by words using some bijection with binary words. A named set is then a pair
$(X,\nu )$
where
$\nu \colon \{\mathtt {0},\mathtt {1}\}^* \to X$
is a bijection that we will call representation. Again, we will choose representations which are ‘good in the sense that they make the relevant structure of the named set computable through their representations’. In what follows, we will therefore speak freely of algorithms working on named sets without explicitly referring to their representations.
Let X be a named set and
$A \subset X$
. We say that A is recursively enumerable (r.e.) or semi-decidable if there is an algorithm which, on input w, halts if and only if
$w\in A$
. Equivalently, A is r.e. if it is either empty or it equals
$\{f(n) : n\in {\mathbb {N}}\}$
for some total computable function
$f\colon \mathbb {N} \to X$
. We say that A is decidable if both A and
$X\setminus A$
are semi-decidable.
Example 2.1. Let
$(\varphi _e)_{e\in \mathbb {N}}$
be an effective enumeration of all partial computable functions (for example, in lexicographic order according to their ‘code’). The famous halting set
$\texttt {Halt}=\{ e \in \mathbb {N} : \varphi _e(e) \mbox { halts}\}$
is an example of a semi-decidable set that is not decidable.
Every time we have a sequence
$(x_n)_{n\in {\mathbb {N}}}$
of objects that are computable in some way, for instance, a sequence
$(f_n)_{n\in {\mathbb {N}}}$
of computable functions or a sequence
$(A_n)_{n\in {\mathbb {N}}}$
of decidable sets, we will say that the computability of the sequence is uniform when all the objects in the sequence can be computed by the same algorithm. For example, a sequence
$(f_n)_{n\in {\mathbb {N}}}$
of total functions is uniformly computable if there is an algorithm which on input
$(n,w)$
, halts and outputs
$f_n(w)$
. Similarly, a sequence
$(A_n)_{n\in {\mathbb {N}}}$
of sets is uniformly r.e. if there is an algorithm which on input
$(n,w)$
, halts if and only if
$w\in A_n$
.
Example 2.2. Let
$(\varphi _e)_{e\in \mathbb {N}}$
be the lexicographic enumeration of all partial computable functions and let
$A_e = \{n\in \mathbb {N} : \varphi _e(n) \text { halts}\}$
. Then, the sequence of all recursively enumerable sets
$(A_e)_{e\in \mathbb {N}}$
is uniform. However, the sequence
$(A_{e_n})_{n\in \mathbb {N}}$
of all decidable sets is not uniform.
2.2 Finitely generated groups
Let
$\Gamma $
be a group. Given
$S\subset \Gamma $
and a word
${w = w_1\cdots w_n \in S^*}$
, we denote by
w
the element of
$\Gamma $
obtained by multiplying the
$w_i$
. Recall that
$\Gamma $
is finitely generated if
$\Gamma = \{\underline {w} : w \in S^*\}$
for some finite
$S\subset \Gamma $
. We call such a set S a generator for
$\Gamma $
. In this paper, we will always assume generators to be symmetric, that is, closed by inverses. The word problem of
$\Gamma $
with respect to S is the set of words
$$ \begin{align*}\texttt{WP}_S(\Gamma)= \{w \in S^* : \underline{w} = 1_{\Gamma}\}.\end{align*} $$
We say that a finitely generated group
$\Gamma $
is recursively presented if
$\texttt {WP}_S(\Gamma )$
is recursively enumerable, and that
$\Gamma $
has decidable word problem if
$\texttt {WP}_S(\Gamma )$
is decidable. These two properties do not depend upon the choice of S, as long as S is a finite generating set for
$\Gamma $
. A surjective group homomorphism is called an epimorphism.
Remark 2.3. Let
$\Gamma $
be a group which is finitely generated by S. Consider the canonical map
$\pi \colon S^* \to \Gamma $
which assigns to a word w its corresponding element
$\pi (w)=\underline {w}$
. If the word problem of
$\Gamma $
is decidable, then one can compute a set of words that uniquely represent the elements of
$\Gamma $
. By identifying this set with
$\{\mathtt {0},\mathtt {1}\}^*$
through a computable bijection, one obtains a representation that makes the group operation computable. Conversely, it is not hard to see that if a finitely generated group admits a representation that makes the group operation computable, then it necessarily has decidable word problem.
2.3 Group actions and their dynamics
Given a group
$\Gamma $
and actions by homeomorphisms on compact metrizable spaces
$\Gamma \curvearrowright X$
and
$\Gamma \curvearrowright Y$
, a continuous surjective map
$f\colon X \to Y$
is a topological factor map if for every
$g\in \Gamma $
and
$x \in X$
, we have
$g(f(x)) = f(gx)$
. Furthermore, we say that a topological factor map is a topological conjugacy if it is an homeomorphism. A major challenge in dynamical systems theory is to classify this kind of group actions up to topological conjugacy or topological factor maps.
Given a group homeomorphism
$\psi \colon G\to \Gamma $
and a group action
$\Gamma \curvearrowright X$
, we define the induced action
$G\curvearrowright X$
by
$g x=\psi (g) x$
for every
$g\in G$
.
2.4 Shift spaces
Let A be an alphabet set and
$\Gamma $
be a group. The full
$\Gamma $
-shift is the set
$A^{\Gamma } = \{ x\colon \Gamma \to A\}$
equipped with the left shift action
$\Gamma \curvearrowright A^{\Gamma }$
by left multiplication given by
The elements
$x \in A^\Gamma $
are called configurations. Given a finite set
$F\subset \Gamma $
, a pattern with support F is an element
$p \in A^F$
. We denote the cylinder generated by p by
$[p] = \{ x \in A^{\Gamma } : x|_F = p \}$
and note that the cylinders are a clopen base for the prodiscrete topology on
$A^{\Gamma }$
.
Definition 2.4. A subset
$X \subset A^\Gamma $
is a
$\Gamma $
-subshift if and only if it is
$\Gamma $
-invariant and closed in the prodiscrete topology.
If the context is clear, we drop the
$\Gamma $
from the notation and speak plainly of a subshift. Equivalently, X is a subshift if and only if there exists a set of forbidden patterns
${\mathcal {F}}$
such that
$$ \begin{align*}X=X_{\mathcal{F}} = \{ x \in A^{\Gamma} : gx\notin [p] \mbox{ for every } g \in \Gamma, p \in {\mathcal{F}} \}.\end{align*} $$
A subshift X is of finite type (SFT) if there exists a finite set of forbidden patterns
$\mathcal {F}$
for which
$X = X_{\mathcal {F}}$
.
We say that an action
$\Gamma \curvearrowright X$
on a compact metrizable space is expansive if for some metric d, which is compatible with the topology, there exists
$C>0$
such that whenever
$x,y \in X$
are distinct, then
$\sup _{g \in \Gamma }\,d(gx,gy) \geq C$
. It is a well known elementary fact (for instance, see [Reference Hedlund20, Theorem 2.1]) that an action
$\Gamma \curvearrowright X$
on a zero-dimensional compact metrizable space is expansive if and only if it is topologically conjugate to a subshift.
2.5 Computability on Cantor spaces
Let A be a finite set with
$|A|\geq 2$
. The space
$A^{\mathbb {N}}$
endowed with the product of the discrete topology will be called a Cantor space. It is compact, metrizable, and has topological dimension zero. The Cantor space is universal in the sense that every compact, metrizable space with topological dimension zero is homeomorphic to a closed subset of
$A^{\mathbb {N}}$
(further on in Theorem 3.18, we will prove an effective version of this result). As we will only deal with compact metrizable spaces, in what follows, we will just say that a space is zero-dimensional to say that it has these three properties.
A natural metric in the Cantor space is given by
$$ \begin{align*} d(x,y) = 2^{-\inf \{n \in \mathbb{N}\ :\ x_n \neq y_n \} }\quad \mbox{for } x,y \in A^{\mathbb{N}}.\end{align*} $$
Given a word
$w=w_0\cdots w_n \in A^*$
, the cylinder determined by w is the clopen set
$$ \begin{align*} [w] = \{x \in A^{\mathbb{N}} : x_0 \cdots x_n = w_0 \cdots w_n\}. \end{align*} $$
The collection of all cylinders forms a basis for the topology on
$A^{\mathbb {N}}$
.
Next, we will introduce computability notions for
$A^{\mathbb {N}}$
. We say that a set
$U \subset A^{\mathbb {N}}$
is effectively open if there exists a recursively enumerable set
$L\subset A^{*}$
such that
${U = \bigcup _{w \in L}[w]}$
. Intuitively, this means that this set can be approximated by an algorithm from the inside. Similarly, we say that a set
$C \subset A^{\mathbb {N}}$
is effectively closed if it is the complement of an effectively open set. For a subspace
$X\subset A^{\mathbb {N}}$
, we say that a set is effectively open (respectively closed) in X if it is the intersection of X with an effectively open (respectively closed) set.
Remark 2.5. Let
$(U_i)_{i \in \mathbb {N}}$
be an uniform sequence of effectively open sets and write
$U_i = \bigcup _{w \in L_i}[w]$
. As the union of a uniform sequence (in particular, a finite sequence) of recursively enumerable languages is recursively enumerable, it follows that the union
$\bigcup _{i\in \mathbb {N}} U_i$
is also effectively open. An analogous argument shows that the intersection of any uniform sequence (in particular, a finite sequence) of effectively closed sets is effectively closed.
Remark 2.6. Given a finite list of words
$w_1,\ldots ,w_n \in A^*$
, it is easy to write an algorithm which decides if
$\bigcup _{i =1}^n [w_i] = A^{\mathbb {N}}$
. In particular, as
$A^{\mathbb {N}}$
is compact, it follows that if
$U = \bigcup _{w \in L}[w]$
is an effectively open set, we may semi-decide from L whether
$U = A^{\mathbb {N}}$
by repeatedly checking whether finite unions of its associated cylinder sets cover
$A^{\mathbb {N}}$
. Moreover, taking complements, we deduce that we can semi-decide if an effectively closed set is empty.
Definition 2.7. Let
$A,B$
be alphabets. We say that a function
$f\colon X\subset A^{\mathbb {N}} \to B^{\mathbb {N}}$
is computable if uniformly for every
$w\in B^*$
, there exists an effectively open set
$U_w\subset A^{\mathbb {N}}$
such that
$f^{-1}([w]) = U_w \cap X$
.
Notice that computable functions are always continuous in their domain and that the composition of computable functions is computable. An equivalent and perhaps more intuitive way to think about computable functions on
$X\subset A^{\mathbb {N}}$
is as those for which there is an algorithm that, given a prefix of
$x \in X$
, yields a prefix of
$f(x)$
, and the sequence of these prefixes monotonously converges to
$f(x)$
.
Proposition 2.8. Let
$A,B$
be alphabets. A function
$f\colon X\subset A^{\mathbb {N}} \to B^{\mathbb {N}}$
is computable if and only if there exists a partial computable function
$g\colon A^* \to B^*$
such that for any
$x \in X$
,
$g(x|_{\{0,\ldots ,n\}})$
is defined for every n, the cylinders
$[g(x|_{\{0,\ldots ,n\}})]$
form a nested sequence, and
$$ \begin{align*} \{f(x)\} = \bigcap_{n \in \mathbb{N}} [g(x|_{\{0,\ldots,n\}})]. \end{align*} $$
Proof. Suppose that f is computable. We shall construct a partial computable function
$g\colon A^*\to B^*$
with the required properties. As f is computable, there is an algorithm which can list, in some order, all
$(v,w)\in A^*\times B^*$
such that
$[v]\cap X \subset f^{-1}([w])$
. Set
$g(\epsilon ) = \epsilon $
and start the listing algorithm. Iteratively, for every pair
$(v,w)$
which is listed, compute the largest prefix
$v'\in A^*$
for which
$g(v')$
is already defined. If
$g(v')$
is strictly a prefix of w, set
$g(v) = w$
and
$g(v")=g(v')$
for every intermediate word
$v"$
which has
$v'$
as a prefix and is a prefix of v. Otherwise, do nothing. The function
$g\colon A^*\to B^*$
resulting from this procedure is a partial computable map which satisfies the required properties.
Conversely, given a partial computable function
$g\colon A^* \to B^*$
with the properties of the statement and
$w \in B^*$
, the collection
$$ \begin{align*}L_w = \{v \in A^* : g(v) \mbox{ is defined and } w \mbox{ is a prefix of } g(v)\},\end{align*} $$
is recursively enumerable uniformly on w. Therefore, the collection
$U_w = \bigcup _{v \in L_w}[v]$
is uniformly effectively open and because of the assumptions on g, it satisfies
$f^{-1}([w]) = X \cap U_w$
.
We shall now provide a few examples.
Example 2.9. The shift map
$\sigma \colon A^{\mathbb {N}} \to A^{\mathbb {N}}$
given by
$\sigma (x)_n = x_{n+1}$
is computable. Indeed, the map
$g\colon A^* \to A^*$
which deletes the first symbol, that is,
$g(x_1\cdots x_m) = x_2\cdots x_m$
, is computable and satisfies the required monotonicity condition.
Example 2.10. Consider the map
$f\colon \{\mathtt {0},\mathtt {1}\}^{\mathbb {N}} \to \{\mathtt {0}, \mathtt {1},\mathtt {2}\}^{\mathbb {N}}$
given by
$$ \begin{align*} f(x)_0 = \begin{cases} \mathtt{0} & \mbox{if } x_0 = \mathtt{0},\\ \mathtt{1} & \mbox{if } x_0x_1 = \mathtt{10},\\ \mathtt{2} & \mbox{if } x_0x_1 = \mathtt{11}\\ \end{cases} \quad\mbox{and}\quad f(x)_k = \begin{cases} f(\sigma(x))_{k-1} & \mbox{if } x_0 = \mathtt{0},\\ f(\sigma^2(x))_{k-1} & \mbox{if } x_0 = \mathtt{1},\\ \end{cases} \quad\mbox{for } k\geq 1,\end{align*} $$
where
$\sigma $
is the shift map from Example 2.9. It is clear by its recursive definition that f is a computable map. Moreover, this map provides an example of a computable homeomorphism (computable bijection with computable inverse) between
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
and
$\{\mathtt {0}, \mathtt {1},\mathtt {2}\}^{\mathbb {N}}$
. This construction can be easily generalized to provide a computable homeomorphism between
$A^{\mathbb {N}}$
and
$B^{\mathbb {N}}$
for any finite
$A,B$
with at least two elements each, in fact, we shall show that a much more general statement holds in Theorem 3.18.
Definition 2.11. Let
$\Gamma $
be a finitely generated group and
$X\subset A^{\mathbb {N}}$
. We say that an action
$\Gamma \curvearrowright X$
is computable if for some finite set of generators S and each
$s\in S$
, we have that the group action map
$f_s \colon X \to X$
given by
$f_s(x) = sx$
is computable.
Notice that as the composition of computable maps is computable, we have that for any
$g \in \Gamma $
, the map
$f_g\colon X \to X$
given by
$f_g(x)=gx$
is computable. Therefore, if this condition is satisfied by some generating set, then it is uniformly satisfied by all of them.
Although there are only countably many computable maps, almost every action that one may come up with naturally (without introducing explicitly an uncomputable parameter) is likely going to be computable. Let us provide a few examples of computable actions on Cantor spaces.
Example 2.12. Let
$A = \{\mathtt {0},\mathtt {1}\}$
and consider the binary odometer action
$\mathbb {Z} \curvearrowright \{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
induced by the homeomorphism
$T\colon \{\mathtt {0},\mathtt {1}\}^{\mathbb {N}} \to \{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
defined by
$$ \begin{align*} T(x)_n = \begin{cases} \mathtt{0} & \mbox{if } n < c,\\ \mathtt{1} & \mbox{if } n = c,\\ x_n & \mbox{if } n> c, \end{cases}\quad \mbox{where } c = \inf\{k \in \mathbb{N}: x_k = \mathtt{0}\}.\end{align*} $$
Clearly,
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
is effectively closed. We claim that the map T is computable: let
$x_0\cdots x_{n-1}$
be the first n digits of
$x\in A^{\mathbb {N}}$
. We can read the sequence from left to right swapping
$\mathtt {1}$
for
$\mathtt {0}$
until we either read a
$\mathtt {0}$
, in which case we swap it for a
$\mathtt {1}$
and leave the rest of the sequence untouched, or we reach the end of the sequence. The resulting sequence corresponds to the first n-digits of the image of
$T(x)$
. A similar argument shows that
$T^{-1}$
is computable as well, and as
$\{-1,1\}$
generates
$\mathbb {Z}$
, we conclude that the binary odometer action is computable.
Example 2.13. Let
$\mathcal {U} = \{u_1,\ldots ,u_n\}$
and
$\mathcal {V} = \{v_1,\ldots ,v_n\}$
be two sets of binary words which induce partitions of
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
, that is, such that
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}} = \bigcup _{i=1}^{n}[u_i] = \bigcup _{i=1}^{n}[v_i]$
and the unions are disjoint. Consider the homeomorphism f of
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
such that
$f(u_ix) = v_ix$
, that is, if an infinite word begins by
$u_i$
, it replaces that prefix by
$v_i$
and leaves the rest of the word unchanged. Notice that for any choice of
$\mathcal {U},\mathcal {V}$
, the associated homeomorphism is computable.
Three celebrated groups can be defined using these homeomorphisms, namely:
-
(1) Thompson’s group F of all such homeomorphisms where the elements of both
$\mathcal {U}$
and
$\mathcal {V}$
are indexed in lexicographical order; -
(2) Thompson’s group T of all such homeomorphisms where the elements of both
$\mathcal {U}$
and
$\mathcal {V}$
are indexed in lexicographical order up to a cyclical permutation; -
(3) Thompson’s group V of all such homeomorphisms.
The three groups above satisfy
$F \leqslant T \leqslant V$
and are finitely generated [Reference Cannon, Floyd and Parry11]. Their natural actions on
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
are examples of computable actions on an effectively closed set.
Naturally, for any named set
$\mathcal {N}$
, we can consider computability of maps from
$A^{\mathcal {N}}$
to
$B^{\mathcal {N}}$
through the identification of
$\mathcal {N}$
with
$\mathbb {N}$
. For instance, if we let
$\varphi \colon \mathbb {N} \to \mathbb {Z}$
be the bijection
$\varphi (n) = (-1)^n \lceil {n}/{2}\rceil $
, a set
$X\subset A^{\mathbb {Z}}$
would be effectively closed if and only if
$X' = \{x' \in A^{\mathbb {N}}: x' = x \circ \varphi \mbox { for some } x \in X\}$
is effectively closed in
$A^{\mathbb {N}}$
.
Example 2.14. Consider the homeomorphisms t and a on
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {Z}}$
given by
$$ \begin{align*} t(x)_{n} = x_{n+1} \quad \mbox{and } \quad a(x)_n = \begin{cases} \mathtt{1}-x_n & \mbox{if } n = 0,\\ x_n & \mbox{if } n \neq 0, \end{cases} \quad \mbox{for every } x \in \{\mathtt{0},\mathtt{1}\}^{\mathbb{Z}} \mbox{ and } n \in \mathbb{Z}. \end{align*} $$
In words, the map t shifts a bi-infinite binary sequence to the left, while the involution a swaps the symbol at the origin. The maps
$t,t^{-1}$
and a generate the lamplighter group. If we identify
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {Z}}$
with
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
through a computable bijection between
$\mathbb {N}$
and
$\mathbb {Z}$
, we get that the maps corresponding to
$t,t^{-1}$
and a are computable. It follows that the induced natural action
$(\mathbb {Z} \wr \mathbb {Z}/2\mathbb {Z})\curvearrowright \{\mathtt {0},\mathtt {1}\}^{\mathbb {Z}}$
is computable.
3 Computability and dynamical systems
In this section, we introduce and discuss the main notion of this work: effective dynamical systems. This notion generalizes the idea of a computable action over an effectively closed subset of
$A^{\mathbb {N}}$
to metric spaces with positive topological dimension. Our definition will be expressed in the formalism of computable analysis, to which we will provide a short introduction.
3.1 Computable analysis
Computable analysis is about making algorithms able to process infinite objects, such as real numbers or infinite sequences. A convenient unifying way to formalize this idea is to see these objects as points of a metric space with an extra computable structure. Most of the results presented here are well known and can be found in the literature (we refer to [Reference Brattka and Hertling10] for a modern exposition). We also present some new results related to zero-dimensional spaces.
Definition 3.1. A computable metric space is a triple
$(X,d,\mathcal {S})$
, where
$(X,d)$
is a separable metric space and
$\mathcal {S} = \{s_i : i \ge 0\}$
a countable dense subset of X, such that there exists an algorithm which, upon input
$(i,j,n) \in \mathbb {N}^{3}$
, outputs
$r\in \mathbb {Q}$
such that
$$ \begin{align*}|d(s_i,s_j)-r| \le 2^{-n}.\end{align*} $$
We say that the distances
$d(s_i,s_j)$
are uniformly computable from
$i,j$
.
For a rational number
$r>0$
and x an element of X, we denote by
$B(x,r) = \{ z \in X \ : \ d(z,x)<r\}$
the open ball with center x and radius r. The balls centered on elements of
$\mathcal {S}$
with rational radii are called basic balls. A computable enumeration of the basic balls
$B_{n}=B(s^{(n)},r^{(n)})$
can be obtained by taking, for instance, a bi-computable bijection
$\varphi \colon \mathbb {N} \rightarrow \mathbb {N} \times \mathbb {Q}$
and letting
$s^{(n)} = s_{\varphi _1 (n)}$
and
$r^{(n)} = \varphi _2 (n)$
, where
$\varphi (n) = (\varphi _1 (n),\varphi _2 (n))$
. We fix such a computable enumeration from now on. For any subset I (finite or infinite) of
$\mathbb {N}$
, we define
$$ \begin{align*}U_{I} = \bigcup_{n \in I} B_n.\end{align*} $$
An open set
$V\subset X$
is effectively open if
$V=U_I$
for some recursively enumerable set
$I\subset \mathbb {N}$
. We note that finite intersections and unions of countably many uniformly effectively open sets are again effectively open. A set
$K\subset X$
is effectively closed if it is the complement of an effectively open set.
A point
$x\in X$
is computable if the set
$\{n\in \mathbb {N}:x\in B_n\}$
is recursively enumerable. Note that a point
$x\in X$
is computable if and only if one can uniformly compute a sequence
$(s_{\varphi (n)})_{n\in {\mathbb {N}}}$
of elements of
$\mathcal {S}$
which satisfy
$|s_{\varphi (n)}-x|\leq 2^{-n}$
for every
$n \in \mathbb {N}$
.
Example 3.2. The set
$\mathbb {R}$
of real numbers, with the Euclidean metric
$d(x,y)=|x-y|$
and
$\mathcal {S}=\mathbb {Q}$
is a computable metric space. The basic balls here are the open intervals with rational endpoints. In this case, the notion of computable point can be split into two: a real x is lower semi-computable if the set
$\{q\in \mathbb {Q}:q<x\}$
is recursively enumerable and upper semi-computable if
$-x$
is lower semi-computable. It is an easy exercise to verify that x is computable if and only if it is both lower and upper semi-computable. An example of a lower semi-computable real number which is not computable is given by
$$ \begin{align*}h=\sum_{e\in \texttt{Halt}}2^{-e},\end{align*} $$
where
$\texttt {Halt}$
is the halting set (or any other r.e. set that is not decidable).
Example 3.3. For a computable point
$x\in X$
, a closed ball of the form
$\overline {B}(x,r)=\{y\in X : d(x,y)\leq r\}$
is effectively closed if and only if r is upper semi-computable. In particular, the closure of every basic ball is effectively closed. However, if we let r be a lower semi-computable but not computable number, then the open ball
$B(x,r)$
is an example of an effectively open set whose closure is not effectively closed.
Example 3.4. Let A be a countable set with at least two elements. The space
$A^{\mathbb {N}}$
with the metric introduced in §2.4 has a natural computable metric space structure using a standard enumeration of the dense countable set of eventually constant configurations
$$ \begin{align*}\mathcal{S} = \{w\mathtt{a}^{\infty}: w \in A^{*}, \mathtt{a}\in A\}.\end{align*} $$
In this case, the basic balls are the cylinders and thus for the case when A is finite, we recover the computable structure introduced in §2.4. We will call this the canonical computable structure of Cantor spaces. In the case where
$A = \mathbb {N}$
, we obtain an analogous canonical computable structure for the Baire Space
$\mathbb {N}^{\mathbb {N}}$
.
Example 3.5. Let
$(X_i,d_i,\mathcal {S}_i)_{i \in \mathbb {N}}$
be a sequence of uniformly computable metric spaces such that the distances
$d_i$
are uniformly bounded. Write
$\mathcal {S}_i = \{s_{i,k}\}_{k \in \mathbb {N}}$
. The product space
$(\prod _{i \in \mathbb {N}} X_i,d,\mathcal {S})$
is a computable metric space where
$d((x_i)_i,(y_i)_i)=\sum _{i \in \mathbb {N}}2^{-i}d_i(x_i,y_i)$
and
$$ \begin{align*}\mathcal{S}=\bigg\{ (x_i)_{i \in \mathbb{N}}\in \prod_{i \in \mathbb{N}} \mathcal{S}_i : \mbox{there is } m,L \in \mathbb{N} \mbox{ such that for } \ell \geq L, x_{\ell} = s_{\ell,m} \bigg\}.\end{align*} $$
Let
$(X,d)$
and
$(X',d')$
be computable metric spaces. Let
$(B^{\prime }_m)_{m\in \mathbb {N}}$
denote the canonical enumeration of the basic balls of
$X'$
. A function
$f\colon X \to X'$
is computable if there exists an algorithm which, given as input some integer m, enumerates a set
$I_m\subset \mathbb {N}$
such that
$$ \begin{align*}f^{-1} (B^{\prime}_m) = U_{I_m},\end{align*} $$
that is, if the preimages
$f^{-1}(B^{\prime }_m)$
of basic balls are effectively open sets uniformly in m. More generally, for any
$Y\subset X$
, we say
$f\colon Y\to X'$
is computable if there exists an algorithm which, given as input some integer m, enumerates a set
$I_m$
such that
$$ \begin{align*}f^{-1} (B^{\prime}_m) = U_{I_m}\cap Y.\end{align*} $$
Remark 3.6. For Cantor spaces
$A^{\mathbb {N}},B^{\mathbb {N}}$
endowed with the canonical computable structure given in Example 3.4, the notion of computable function boils down to Definition 2.7.
It follows immediately from the definition that computable functions are continuous and closed under composition. It is perhaps more intuitively familiar, and in fact equivalent, to think of a computable function as one for which there is an algorithm which, provided with arbitrarily good approximations, outputs arbitrarily good approximations of
$f(x)$
. The formal statement and the proof are analogous to Proposition 2.8.
3.1.1 Computability of compact sets
Definition 3.7. A compact set
$K\subset X$
is said to be recursively compact if the inclusion
$$ \begin{align*}K \subset U_I,\end{align*} $$
where I is some finite subset of
$\mathbb {N}$
, is semi-decidable. That is, if there is an algorithm which, given I as input, halts if and only if the inclusion above is verified.
We remark that for a recursively compact set K, the inclusion
$K\subset U_{I}$
can be semi-decided for any effectively open set
$U_{I}$
, as it suffices to run in parallel the above algorithm on all finite subsets
$I' \subset I$
and halt if one of them halts.
Example 3.8. The Cantor space is recursively compact. Indeed, recursive compactness for Cantor spaces boils down to check whether a finite list of cylinders covers the whole space, which is clearly semi-decidable (actually, even decidable, see Remark 2.6). A similar reasoning applies to the unit interval, which is also recursively compact.
We will next prove that the product of a collection of uniformly recursively compact metric spaces is again recursively compact. We refer to [Reference Rettinger and Weihrauch29] for a treatment of the computability of Tychonoff’s theorem in the general case.
Proposition 3.9. Let
$(X_i,d_i,\mathcal {S}_i)_{i \in \mathbb {N}}$
be a uniform sequence of computable metric spaces with uniformly bounded distances. If
$K_i \subset X_i$
is uniformly recursively compact, then their product
$\prod _{i \in \mathbb {N}} K_i $
is recursively compact in
$\prod _{i \in \mathbb {N}} X_i$
.
Proof. To see that
$\prod _{i \in \mathbb {N}} K_i$
is recursively compact, notice that the projection of a rational ball in the product space to coordinate i contains the whole
$X_i$
for all
$i>N$
for some sufficiently large N, and we can compute N from the radius of the ball. Thus, checking whether a finite list of balls covers
$\prod _{i \in \mathbb {N}} K_i$
boils down to check, for finitely many i terms, whether a finite list of balls in
$X_i$
covers
$K_i$
, and this can be done by the uniform recursive compactness of the
$K_i$
.
Remark 3.10. Note that the product topology on a uniform sequence of computable metric spaces has the property that the projection onto a uniform (in particular, a finite) collection of coordinates is a computable function.
We will make use of the following result, which is a computable version of the fact that in a Hausdorff space, a subset of a compact set is compact if and only if it is closed.
Proposition 3.11. Let
$(X,d,\mathcal {S})$
be a recursively compact computable metric space. A subset
$K \subset X$
is recursively compact if and only if it is effectively closed.
Proof. Assume K is effectively closed. Then,
$X\setminus K$
is effectively open. Let U be a finite union of open basic balls. To see that we can semi-decide whether
$K\subset U$
, simply note that U covers K exactly when
$U \cup (X\setminus K)$
covers X, which can be semi-decided since X is recursively compact. Conversely, if K is recursively compact, then we can enumerate its complement by enumerating the complement of the closure of all the finite unions of basic balls that cover K.
Remark 3.12. An important consequence of the previous proposition is that in any recursively compact space X, there is an algorithm which, given as input a description of an effectively closed set K and an effectively open set
$U_I$
, halts if and only if
$K\subset U_I$
. In particular, we can uniformly semi-decide if
$K = \varnothing $
.
We also note that if
$f\colon X\to X'$
is a computable function between computable metric spaces, then the image of a recursively compact set is recursively compact uniformly in the description of the set. We end this section with the following two important propositions.
Proposition 3.13. Let
$f\colon X \to Y$
be a function between computable metric spaces that is computable on a recursively compact set
$K\subset X$
. Then, uniformly for any basic ball
$B\subset X$
, there exists an effectively open set
$U_{B} \subset Y$
such that
$f(B\cap K) = f(K) \cap U_B$
. In particular, if f is injective, it has a computable inverse
$f^{-1}\colon f(K)\to K$
.
Proof. Let B be a basic ball. We show how to uniformly compute an effectively open
$U_B\subset Y$
such that
$f(B\cap K) = U_B \cap f(K)$
. As K is recursively compact, we have that
$K\setminus B$
is recursively compact and, thus,
$f(K\setminus B)$
is recursively compact in Y uniformly on B. The set
$U_B=Y\setminus f(K\setminus B)$
is effectively open and satisfies the required property.
Proposition 3.14. Let
$f\colon K\to K$
be a computable function on an effectively closed subset of a computable metric space X. Then, the set
$$ \begin{align*}\{x\in K : f(x)=x\}\end{align*} $$
is effectively closed.
Proof. Simply note that the function
$F(x) = d(x,f(x))$
is computable on K, and therefore
$$ \begin{align*} X\setminus \{x\in K : f(x)=x\} = (X\setminus K) \cup F^{-1}(\{r\in \mathbb{R}: r>0\}) \end{align*} $$
is an effectively open set.
3.2 Computability for zero-dimensional spaces
Another interesting application of Proposition 3.11 is the construction of a basis of clopen sets for any given recursively compact zero-dimensional subset of a computable metric space.
Proposition 3.15. Let K be a zero-dimensional recursively compact subset of a computable metric space X. Then, one can uniformly compute a collection
$(C_n)_{n \in \mathbb {N}}$
of finite unions of basic balls in X such that
$(C_n\cap K)_{n \in \mathbb {N}}$
forms a basis of clopen sets for K.
Proof. Since K is zero-dimensional, it has a basis of clopen sets. Let C be clopen in K. Since C is open in K, there exists a set U open in X such that
$C = U\cap K$
. Since C is also closed and K is compact, C is compact as well, and thus the set U can be taken to be a finite union of basic balls. Now consider the collection
$V_1, V_2, \ldots $
of all finite unions of basic balls. By what we have just shown, we know that
$(V_i\cap K)_{i \in \mathbb {N}}$
contains a basis of clopen sets for K. We claim that we can uniformly semi-decide, given a finite union V, whether
$C = V \cap K$
is clopen in K. Indeed, note that if C is a clopen set in K, then one has
$$ \begin{align*} C = \overline{C} = \overline{V}\cap K,\end{align*} $$
where
$\overline {V}$
is the union of the closures of the finitely many balls defining V. This is equivalent to having
$$ \begin{align*}(K\setminus C) \subset X\setminus \overline{V}.\end{align*} $$
However,
$K\setminus C = K\setminus V$
is effectively closed, and therefore recursively compact by Proposition 3.11. Since
$X\setminus \overline {V}$
is an effectively open set, it follows that this last relation is semi-decidable.
It is a well-known result of Brouwer that every zero-dimensional compact space without isolated points is homeomorphic to the Cantor space
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
. Here, we will prove an effective version of this result. To state it, we need the following notion of computability for closed sets.
Definition 3.16. A closed set X is recursively enumerable (r.e.) if one can uniformly compute a sequence
$(x_i)_{i \in \mathbb {N}} \subset X$
of points that is dense in X. If X is both effectively closed and r.e., then we say it is computably closed.
Remark 3.17. We note that since computable functions send uniformly computable sequences of points to uniform computable sequences of points, it follows that the image of a closed r.e. set by a computable function is also closed r.e.
Theorem 3.18. Let X be a non-empty recursively compact zero-dimensional subset of a computable metric space. Then, X is computably homeomorphic to an effectively closed subset E of
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
. Moreover:
-
• if X is computably closed, then E can be taken to be computably closed;
-
• if X is computably closed and has no isolated points, then E can be taken to be
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
.
Proof. If X is a singleton, then there is nothing to prove. We assume therefore that X contains at least two points. We claim that one can uniformly compute a sequence
$(\mathcal P^n)_{n\in {\mathbb {N}}}$
of partitions of X made by effectively closed clopen sets, where each
$\mathcal P^n$
is indexed as
$\{P^n_0,\ldots ,P^n_{k_n}\}$
, such that each set in
$\mathcal P^n$
has diameter at most
$2^{-n}$
and such that the elements of
$\mathcal P^n$
are unions of elements in
$\mathcal P^{n+1}$
. Indeed, it suffices to observe that, given any
$n\in \mathbb {N}$
, by using Proposition 3.15, one can uniformly compute a basis of clopen sets whose diameter is less than
$2^{-n}$
(recall that from the index of a basic ball, one can compute its radius). Now, given any clopen and effectively closed set, call it C, we can use recursive compactness of C (see Proposition 3.11) to find a finite collection of basic clopen sets of small diameter that covers C. By iteratively applying this observation, we can compute the sequence of partitions
$(\mathcal P^n)_{n\in {\mathbb {N}}}$
as needed. Moreover, by our assumption on X, we can assume that
$\mathcal {P}^0$
has more than one element. Now, for each
$n\in {\mathbb {N}}$
, we let
$B_n=\{0,\ldots ,k_n\}$
. It follows that
$B_n$
has at least two elements. As
$(k_n)_{n\in {\mathbb {N}}}$
is a computable sequence of natural numbers, it follows that
$\prod _{n \in \mathbb {N}} B_n$
is an effectively closed and recursively compact subset of
${\mathbb {N}}^{\mathbb {N}}$
by Theorem 3.9. We now consider the following subset of
$\prod _{n \in \mathbb {N}} B_n$
:
$$ \begin{align*}Y=\bigg\{y\in\prod_{n \in \mathbb{N}} B_n : \text{for all } n\in{\mathbb{N}}, P^n_{y(n)}\cap X\neq\varnothing \text{ and } P^n_{y(n)}\supset P^{n+1}_{y(n+1)}\bigg\}. \end{align*} $$
Observe that Y is effectively closed. Indeed, we can semi-decide whether
${P^n_{y(n)}\cap X=\varnothing }$
by the recursive compactness of X. The condition
$P^k_{y(k)}\supset P^{k+1}_{y(k+1)}$
is decidable by construction. As
$\prod _{n \in \mathbb {N}} B_n$
is a recursively compact subset of
${\mathbb {N}}^{\mathbb {N}}$
, it follows that Y is recursively compact as well by Proposition 3.11.
We now observe that Y and X are computably homeomorphic. We define the function
$\psi \colon Y\to X$
by the following equality:
$$ \begin{align*}\{\psi (y)\}=\bigcap_{n\in{\mathbb{N}}} P^n_{y(n)}.\end{align*} $$
This function is well defined, as the intersection of a nested sequence of compact sets with diameters tending to zero must be a singleton. It is clear from the expression above that
$\psi $
is continuous, computable, and bijective. It follows from Proposition 3.13 that the inverse of
$\psi $
is computable, and thus it is a computable homeomorphism.
We shall now prove that
$\prod _{n \in \mathbb {N}} B_n$
is recursively homeomorphic to
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
. For this, we take
$T\subset {\mathbb {N}}^*$
as the set of words
$\{\varepsilon \} \cup \bigcup _{n\in {\mathbb {N}}}B_0\times \cdots \times B_n$
. Then, T is an infinite tree (a set of words closed by prefix) with the property that each word can be extended by at least two different words on the right. Furthermore, T is a decidable subset of
${\mathbb {N}}^*$
and
$\prod _{n \in \mathbb {N}} B_n$
can be identified with the set of infinite rooted paths in this tree.
We define a function
$h\colon T\to \{\mathtt {0},\mathtt {1}\}^\ast $
in the following recursive manner. First,
${h(\epsilon )=\epsilon }$
. Now let us assume that
$h(w)$
has been defined for some
$w\in T$
. Then we compute the set of words
$\{w_0,\ldots ,w_m\}$
which have w as prefix, and whose length is equal to the length of w plus one, labeled in lexicographical order. As each word in T can be extended in two ways on the right, this set is non-empty and
$m \geq 1$
. Let
$$ \begin{align*}v_0=\mathtt{0},v_1=\mathtt{10},v_2=\mathtt{110},\ldots,v_{m-1} = \mathtt{1}^{m-1}\mathtt{0}, v_m=\mathtt{1}^{m},\end{align*} $$
and define
$h(w_i)=h(w)v_i$
for
$0\leq i\leq m$
. These conditions define
$h(w)$
for every
$w\in T$
. From our construction, it is clear that h is a computable function, it is monotone for the prefix order, and the length of
$h(w)$
tends to infinity with the length of w. Thus, h induces a function
$$ \begin{align*}H\colon \prod_{n \in \mathbb{N}} B_n\to \{\mathtt{0},\mathtt{1}\}^{\mathbb{N}}\end{align*} $$
given by
$H(y)(n)=h(y_0\cdots y_k)(n)$
, the nth element in the word
$h(y_0\cdots y_k)$
, for some k big enough and computable from n. A routine verification shows that H is a computable homeomorphism between
$\prod _{n \in \mathbb {N}} B_n$
and
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
.
The fact that X is computably homeomorphic to an effectively closed subset E of
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
follows by composing the computable homeomorphism between X and
${Y\subset \prod _{n \in \mathbb {N}} B_n}$
, and the computable homeomorphism between
$\prod _{n \in \mathbb {N}} B_n$
and
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
. Computable homeomorphisms preserve the property of being effectively closed, so E will be effectively closed when X is effectively closed. The same holds for the property of being r.e. closed by Remark 3.17.
We now prove that if X is computably closed, non-empty, and has no isolated points, then it is computably homeomorphic to
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
. For this purpose, we make some modifications to the proof given above. We must add some conditions to the sequence
$(\mathcal P^n)_{n\in {\mathbb {N}}}$
. The first extra condition is that for every
$n\in {\mathbb {N}}$
, every element in
$\mathcal P^n$
intersects X. As X is computably closed, we can decide which elements from
$\mathcal P^n$
have empty intersection with X, and discard those elements. The second extra condition is that for every
$n\in {\mathbb {N}}$
, every element in
$\mathcal P^n$
contains at least two elements in
$\mathcal {P}^{n+1}$
. This can be obtained by computably taking a sub-sequence of the original sequence of partitions. The existence being assured by the fact that X has no isolated points.
After these considerations, the set Y is defined in the same manner. Observe that being a computable homeomorphic image of a computably closed set X, Y is computably closed. Now let T be the set of words (including the empty word)
$w\in {\mathbb {N}}^\ast $
such that the cylinder
$[w]\subset {\mathbb {N}}^{\mathbb {N}}$
has non-empty intersection with Y. As Y is computably closed, it follows that T is a computable tree. Observe that from our choice of
$\mathcal {P}^n$
, every element in the tree has at least two children. Then, we just repeat the construction of h given above on the tree T. The function H constructed before induces now a computable homeomorphism between Y and
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
.
3.3 Effective subshifts
Let us recall that a subshift
$X\subset A^\Gamma $
is a closed subset which is invariant by the shift action. A subshift
$X\subset A^{\mathbb {Z}}$
is said to be effective when it is an effectively closed subset of
$A^{\mathbb {Z}}$
, that is, when the set of all words not appearing in the subshift is recursively enumerable. This notion has been extensively used in the literature [Reference Aubrun and Sablik2, Reference Cenzer, Dashti and King14, Reference Durand, Romashchenko, Shen, Blass, Dershowitz and Reisig17, Reference Hochman22]. Our goal in this section is to generalize this notion from
${\mathbb {Z}}$
to an arbitrary finitely generated group
$\Gamma $
. When
$\Gamma $
has decidable word problem, there is a canonical way to endow the full
$\Gamma $
-shift
$A^\Gamma $
with a computable metric structure such that one can speak about effectively closed sets (and therefore effective subshifts). However, as we will see, for more general groups, the task is less straightforward.
3.3.1 Computable structure on
$A^\Gamma $
for a group with decidable word problem
Let
$\Gamma $
be a finitely generated group with decidable word problem. Then, there is a bijection (see Remark 2.3)
$\nu \colon {\mathbb {N}}\to \Gamma $
for which the pullback of the group operation to
${\mathbb {N}}^2\to {\mathbb {N}}$
becomes a computable function. We now introduce a computable metric space structure on
$A^\Gamma $
. For this purpose, we consider the function
$$ \begin{align*}\psi\colon A^{\mathbb{N}}\to A^\Gamma\end{align*} $$
$$ \begin{align*}(x_i)_{i\in{\mathbb{N}}}\mapsto (x_{\nu^{-1}(g)})_{g\in\Gamma},\end{align*} $$
which is in fact an homeomorphism, and let
$\mathcal S=\{\psi (w\mathtt {a}^\infty ) : w\in A^\ast , \mathtt {a}\in A \}$
be the collection of basic points in
$A^\Gamma $
. The distance d on
$A^\Gamma $
obtained by declaring
$\psi $
to be an isometry generates the prodiscrete topology. In this way,
$\mathcal {S}$
becomes a dense subset of
$A^\Gamma $
on which the distance d is clearly computable.
Remark 3.19. We note that this computable metric structure for
$A^\Gamma $
makes the shift action
$\Gamma \curvearrowright A^\Gamma $
computable. To see this, let
$g\in \Gamma $
and let
$f_g\colon A^\Gamma \to A^\Gamma $
be defined by
${f_g(x)=gx}$
. To show that
$f_g$
is computable, it is enough to note that
$\psi ^{-1} f_g\circ \psi \colon A^{\mathbb {N}} \to A^{\mathbb {N}}$
is computable. Indeed, this function can be written as
$(x_i)_{i\in {\mathbb {N}}}\to (x_{h(i)})_{i\in {\mathbb {N}}}$
, where h is a computable bijection of
${\mathbb {N}}$
which comes from the computability of the group operation.
Remark 3.20. The computable metric space structure produced in this way for
$A^\Gamma $
is inherent to
$\Gamma $
and does not depend on the choice of
$\nu $
. Indeed, let
$\nu '$
be another bijection
${\mathbb {N}}\to \Gamma $
as before, and let us denote by
$(A^\Gamma ,d,\mathcal S)$
,
$(A^\Gamma ,d',\mathcal S')$
the computable metric space structures associated to
$\nu $
and
$\nu '$
. Then,
$\operatorname {id}\colon (A^\Gamma ,d,\mathcal S)\to (A^\Gamma ,d',\mathcal S')$
is a computable homeomorphism. This can be proved by noting that
$\nu ^{-1} \circ \nu ' $
is a computable bijection of
${\mathbb {N}}$
. For details, the reader is referred to [Reference Carrasco-Vargas12, §§2.4 and 5]).
Once
$A^\Gamma $
has been endowed with its canonical computable structure, one can naturally extend the definition of an effective subshift for
$A^{\mathbb {Z}}$
to make sense in
$A^\Gamma $
by simply requiring the subshift to be effectively closed. Note that, by definition, a set
$X\subset A^\Gamma $
is effectively closed if and only if the set of patterns p such that
$[p]\cap X=\varnothing $
is recursively enumerable.
We now present a construction that allows us to have a useful notion of effective subshift when
$\Gamma $
is an arbitrary finitely generated group.
3.3.2 Computable structure on
$A^\Gamma $
for arbitrary finitely generated groups
We shall prove later that for some groups, the space
$A^\Gamma $
cannot be endowed with a computable metric space structure for which the action by translations
$\Gamma \curvearrowright A^\Gamma $
is computable. However, the set
$A^\Gamma $
can always be identified with a closed subset of
$A^{F}$
for a suitable free group F. The idea is to use the fact that finitely generated free groups have decidable word problem which, as we have just seen, allows us to endow
$A^F$
with a canonical computable structure. Now to the details.
Let
$\Gamma $
be a finitely generated group, which is not assumed to have decidable word problem. Let S be a finite set of generators of the group
$\Gamma $
. Consider the free group
$F(S)$
generated by S and consider the canonical epimorphism
$\phi \colon F(S)\to \Gamma $
, where every reduced word on S is mapped to its corresponding element in
$\Gamma $
. Let
$\widehat {\phi } \colon A^\Gamma \to A^{F(S)}$
be the map given by
$\widehat {\phi }(x)(w) = x(\phi (w))$
for every
$w \in F(S)$
.
Every subshift
$X\subset A^{\Gamma }$
induces a pullback subshift
$\widehat {X}\subset A^{F(S)}$
given by
$$ \begin{align*}\widehat{X} = \{ \widehat{\phi}(x) \in A^{F(S)} : x \in A^{\Gamma}\}.\end{align*} $$
Definition 3.21. We say that a subshift
$X\subset A^{\Gamma }$
is effective if for some finite set S of generators of
$\Gamma $
, the pullback subshift
$\widehat {X}\subset A^{F(S)}$
is an effectively closed subset of
$A^{F(S)}$
.
It can be seen that this definition does not depend on the set of generators S. Indeed, let
$S'$
be another set of generators and denote by
$\widehat {X}'$
its pullback in
$A^{F(S')}$
. For each
$s \in S$
, let
$\psi (s)$
be a word in
$S'$
such that s is equal to
$\psi (s)$
in
$\Gamma $
. Then,
$\psi $
extends to a computable injective homeomorphism from
$F(S)$
to
$F(S')$
. It follows that the map
$\Psi \colon \widehat {X}\to \widehat {X}'$
given by
$\Psi (x)(w) = x(\psi (w))$
is a computable homeomorphism. In particular,
$\widehat {X}'$
is also effectively closed. A similar argument shows that for a group with decidable word problem,
$\widehat {X}\subset A^{F(S)}$
is effectively closed exactly when
$X\subset A^\Gamma $
is effectively closed, as
$\widehat {A^{\Gamma }}$
is then effectively closed in
$A^{F(S)}$
.
Remark 3.22. In the literature [Reference Aubrun, Barbieri and Sablik1], there is a different computability notion for shift spaces (Definition 7.2). While both notions coincide for recursively presented groups (Corollary 7.7), it turns out that for general finitely generated groups, the two definitions are not equivalent. In §7, we shall provide a characterization of this other notion and clarify the relation with ours.
Example 3.23. If
$\Gamma $
is recursively presented, then the full shift
$A^{\Gamma }$
is effective. Indeed, as the word problem of
$\Gamma $
is recursively enumerable, the set of patterns of the form
${p:\{1_{F(S)},w\}\to A} $
satisfying
$\underline {w}=1_{\Gamma }$
and
$p(1_{F(S)})\ne p(w)$
is recursively enumerable. The union of cylinders associated to these patterns in
$A^{F(S)}$
is equal to the complement of
$\widehat {A^\Gamma }$
.
Remark 3.24. Observe that the map
$\widehat {\phi }$
is a homeomorphism between X and
$\widehat X$
. Moreover, we can define an action
$\Gamma \curvearrowright \widehat {X}$
by setting
$gx=wx$
, where
$w\in F(S)$
is any element satisfying
$\phi (w)=g$
. In this manner, the actions
$\Gamma \curvearrowright \widehat {X}$
and
$\Gamma \curvearrowright X$
are topologically conjugate. In particular, we have that if X is an effective subshift, then
$\Gamma \curvearrowright X$
is topologically conjugate to a computable action
$\Gamma \curvearrowright \widehat {X}$
, where
$\widehat {X}$
is an recursively compact subset of a computable metric space. This is the property that will allow us to generalize the notion of effective subshift to general dynamical systems.
3.4 Effective dynamical systems
Let X be a recursively compact subset of a computable metric space. Similarly to the zero-dimensional case, we say that
$\Gamma \curvearrowright X$
is a computable action if for some finite set of generators S, we have that for each
$s\in S$
, the group action map
$f_s \colon X \to X$
given by
$f_s(x) = sx$
is a computable function. Notice that in this case,
$f_g\colon X \to X$
is in fact uniformly computable for all
$g\in \Gamma .$
In particular, if an action is computable, it will satisfy the definition with respect to every finite set of generators.
We are interested in the behavior of actions as topological dynamical systems, and thus will consider them up to topological conjugacy. Our focus will be on those conjugacy classes that contain some computable representative.
Definition 3.25. Let X be a compact metrizable space and
$\Gamma $
a finitely generated group. We say that an action
$\Gamma \curvearrowright X$
is an effective dynamical system (EDS) if it is topologically conjugate to a computable action
$\Gamma \curvearrowright \widehat {X}$
for some recursively compact subset
$\widehat {X}$
of a computable metric space.
We insist in that our definition of effective dynamical system does not require the space X to have any computable structure or the topological conjugacy to be computable. Given an EDS
$\Gamma \curvearrowright X$
, we will refer to a topologically conjugate instance of a computable action
$\Gamma \curvearrowright \widehat {X}$
over a recursively compact subset
$\widehat {X}$
of a computable metric space as a computable representative.
Example 3.26. An effective subshift
$X\subset A^{\Gamma }$
is an EDS. Indeed, if
$A^{\Gamma }$
is an effective subshift, then
$\Gamma \curvearrowright X$
is topologically conjugate to the action
$\Gamma \curvearrowright \widehat {X}$
, where
$\widehat {X}$
is the subshift from Definition 3.21 (see also Remark 3.24). We will see later that, conversely, the only subshifts which are EDS are the effective ones, thus justifying the name (Proposition 7.1). We remark that the above holds for any finitely generated group
$\Gamma $
, even if it is not recursively presented.
The following example shows that the conjugacy class of an effective dynamical system can contain uncountably many systems. In particular, it contains representatives that are not computably homeomorphic.
Example 3.27. Fix some computable angle
$\alpha \in [0,2\pi ]$
and consider
$C_r=\{x\in \mathbb {R}^2: \|x\|=r\}$
to be the circle of radius
$r>0$
. Note that the space
$C_r$
is a recursively compact subset of
$\mathbb {R}^2$
only for computable r. Despite this, the conjugacy class of the action
$\mathbb {Z} \curvearrowright C_r$
induced by the rotation by
$\alpha $
has a computable representative, namely
$\mathbb {Z} \curvearrowright C_1$
, and is therefore an EDS regardless of the value of r.
Example 3.28. The action
$\operatorname {GL}_n(\mathbb {Z}) \curvearrowright \mathbb {R}^n/\mathbb {Z}^n$
of the general linear group on the n-dimensional torus by left matrix multiplication is an EDS.
Example 3.29. Recall the Thompson’s groups F and T from Example 2.13. These groups are more often defined in the literature as the space of piecewise linear homeomorphisms of
$[0,1]$
(in the case of T, of
$\mathbb {R}/\mathbb {Z}$
) that preserve orientation and whose non-differentiable points are dyadic rationals and whose slopes are all powers of 2. These maps are clearly computable and thus it follows that the natural actions
$F\curvearrowright [0,1]$
and
$T \curvearrowright \mathbb {R}/\mathbb {Z}$
are EDS.
Next, we are going to show that the class of EDS is closed under computable topological factor maps. We stress the fact that in this result, we need both actions to be represented as computable actions in computable metric spaces and the factor to be computable as well. In §8, we will later show that without strong assumptions that enforce computability, the class of EDS is, in general, not closed under topological factor maps.
Proposition 3.30. Let
$\Gamma $
be a finitely generated group and X, Y be computable metric spaces. Let
$X'\subset X$
be a recursively compact set and
$\Gamma \curvearrowright X'$
be a computable action. Let
$\Gamma \curvearrowright Y' \subset Y$
be a topological factor of
$\Gamma \curvearrowright X'$
by a computable function
$f\colon X'\to Y'$
. Then,
$Y'$
is a recursively compact set and
$\Gamma \curvearrowright Y'$
is a computable group action.
Proof. As
$X'$
is recursively compact and f is computable, it follows that
$Y'$
is recursively compact. Let
$(B^X_i)_{i \in \mathbb {N}}$
and
$(B^Y_i)_{i \in \mathbb {N}}$
be recursive enumerations of the basic balls in X and Y, respectively. Let
$s \in \Gamma $
and let
$i \in \mathbb {N}$
. As f is computable, it follows that, uniformly in i, there is a recursively enumerable set
$I_i \subset \mathbb {N}$
such that
$f^{-1}(B^Y_i) = X' \cap \bigcup _{j \in I_i} B^{X}_j$
. As the action is computable, uniformly for each
$j \in \mathbb {N}$
, there is a recursively enumerable set
$I^{\prime }_j\subset \mathbb {N}$
such that
$$ \begin{align*}s^{-1}f^{-1}(B^Y_i) = X' \cap \bigcup_{j \in I_i}\bigcup_{k \in I^{\prime}_j} B_k^X.\end{align*} $$
Finally, as f is computable and
$X'$
recursively compact, it follows by Proposition 3.13 that uniformly for
$k \in \mathbb {N}$
, there is a recursively enumerable set
$I^{\prime \prime }_k\subset \mathbb {N}$
such that
$$ \begin{align*} s^{-1}(B_i^Y\cap Y') = f(s^{-1}f^{-1}(B_i^Y)) = \bigcup_{j \in I_i}\bigcup_{k \in I^{\prime}_j}\bigcup_{m \in I^{\prime\prime}_k} B_m^Y, \end{align*} $$
where the first equality holds because f is
$\Gamma $
-equivariant. It follows the map
$y \mapsto sy$
is computable and as s is arbitrary, we obtain that
$\Gamma \curvearrowright Y'$
is computable.
4 EDS as factors of computable actions on zero-dimensional effectively closed sets
In this section, we prove Theorem A. Let us briefly recall the standard procedure to build a zero-dimensional topological extension of a dynamical system
$\Gamma \curvearrowright X$
.
-
(1) First, we extract a sequence
$(\mathcal P_n)_{n\in {\mathbb {N}}}$
of open covers of X with diameters tending to zero, and associate to each one of them a subshift
$Y_n$
. -
(2) Define the sequence of subshifts
$(Z_n)_{n\in {\mathbb {N}}}$
, where
$Z_n = \prod _{k \leq n} Y_k$
with the coordinate-wise shift, and consider the projection factor maps
$\pi _{n+1}\colon Z_{n+1}\to Z_n$
. -
(3) Define the inverse limit
$Z= \varprojlim Z_n$
, this is a topological extension of
$\Gamma \curvearrowright X$
.
In our proof, we effectivize this construction. For this purpose, we first need to prove effective versions of some of the steps. This includes infinite products, inverse limits, and subshifts associated to covers.
4.1 Effective versions of some classical constructions
In this section, we prove effective versions of a few classical constructions commonly used in dynamical systems, and which may therefore be of independent interest.
4.1.1 Products of computable actions and inverse limit constructions
Now we show that the operations of countable product and inverse limits are computable under mild computability assumptions. For the next two results,
$(Y_n)_{n \in \mathbb {N}}$
will be a sequence of uniformly computable metric spaces, as in Example 3.5, and we will consider
$\prod _{n\in {\mathbb {N}}} Y_n$
with its product computable metric space structure.
Proposition 4.1. Let
$X_n \subset Y_n$
be a sequence of subsets and
$\Gamma \curvearrowright X_n$
be a uniform sequence of computable actions of the finitely generated group
$\Gamma $
. Then, the component-wise action
$$ \begin{align*} \Gamma\curvearrowright \prod_{n\in{\mathbb{N}}} X_n \subset \prod_{n\in{\mathbb{N}}} Y_n \end{align*} $$
is computable.
Proof. Let us fix
$g\in \Gamma $
. Let
$n\in {\mathbb {N}}$
and let
$U_i$
be an effectively open subset of
$X_i$
for
$i\in \{0,\ldots ,n\}$
. We verify that the preimage by g of
$$ \begin{align*}U=U_0\times\cdots \times U_n\times Y_{n+1}\times Y_{n+2}\times\cdots\end{align*} $$
is effectively open in
$\prod _{n\in {\mathbb {N}}}X_n$
, and that this process is uniform in n and the
$U_i$
. Indeed,
$$ \begin{align*}g^{-1}(U) = g^{-1}(U_0)\times\cdots \times g^{-1}(U_n)\times X_{n+1}\times X_{n+2}\times\cdots\end{align*} $$
This set is effectively open in
$\prod _{n\in {\mathbb {N}}}X_n$
, and it can be uniformly computed from
$n \in \mathbb {N}$
and a description of
$U_0,\ldots ,U_n$
because each of the
$g^{-1}(U_i)$
is effectively open in
$X_i$
and can be uniformly computed from a description of
$U_i\subset Y_i$
.
Proposition 4.2. Let
$\Gamma \curvearrowright X_n$
be as in the previous statement, where each
$X_n$
is now assumed to be an effectively closed subset of
$Y_n$
. Let
$(\pi _n)_{n\geq 1}$
be a sequence of uniformly computable functions, where each
$\pi _{n+1}\colon X_{n+1}\to X_n$
is a topological factor map from
$\Gamma \curvearrowright X_{n+1}$
to
$\Gamma \curvearrowright X_{n}$
. Then, the inverse limit
$$ \begin{align*}\varprojlim X_n=\bigg\{(x_n)\in\prod_{n \in \mathbb{N}} X_n\mid\pi_{n+1}(x_{n+1})=x_n, n\geq 1\bigg\}\end{align*} $$
is an effectively closed subset of
$\prod _{n \in \mathbb {N}} Y_n$
.
Proof. Let
$f\colon \prod _{n \in \mathbb {N}} X_n\to \prod _{n \in \mathbb {N}} X_n$
be the function defined by
$(x_n)_{n\in {\mathbb {N}}}\mapsto (\pi _{n+1} (x_{n+1}))_{n\in {\mathbb {N}}}$
. We claim that f is computable. We verify that the preimage by f of a set of the form
$$ \begin{align*}U=U_0\times\cdots \times U_n\times X_{n+1}\times X_{n+2}\times\cdots\end{align*} $$
is effectively open in
$\prod _{n \in \mathbb {N}} Y_n$
, uniformly on n and the
$U_i$
. Indeed, the preimage
$f^{-1}$
can be written as
$$ \begin{align*} f^{-1}(U)=\pi_1^{-1}(U_0)\times\cdots \times \pi_{n+1}^{-1}(U_n)\times X_{n+1}\times X_{n+2}\times\cdots\end{align*} $$
This set is effectively open uniformly on the
$U_i$
because
$(\pi _n)_{n\geq 1}$
is a sequence of uniformly computable functions. However, it is clear that
$\varprojlim X_n$
equals the set of fixed points of f in
$\prod _{n \in \mathbb {N}} X_n$
. Then, it follows from Proposition 3.14 that
$\varprojlim X_n$
is effectively closed.
4.1.2 Effective covers and partitions, and their associated subshifts
In this subsection, we fix a recursively compact set X which lies in a computable metric space
$\mathcal {X}$
. We start by reviewing some standard terminology regarding covers and the construction of a subshift from a cover. A cover
$\mathcal P$
of X is a finite collection of sets whose union equals X. A cover
$\mathcal P$
is said to be open (respectively closed) if it consists on sets which are open in X (respectively closed in X). We say that the cover
$\mathcal P'$
refines
$\mathcal P$
if every element in
$\mathcal P'$
is contained in some element of
$\mathcal P$
. The join of two covers
$\mathcal P \lor \mathcal P'$
is the cover
$\{P\cap P'\mid P\in \mathcal P, P'\in \mathcal P'\}$
. Given a group action
$\Gamma \curvearrowright X$
and a finite subset
$F\subset \Gamma $
, we write
$\bigvee _{g\in F} g^{-1}\mathcal P$
for the join of all
$g^{-1}\mathcal {P}$
for
$g\in F$
. The diameter of the cover
$\mathcal P$
is the maximum of the diameters of its elements. A cover
$\mathcal P$
of X is said to be generating for the group action
$\Gamma \curvearrowright X$
if for each
$\varepsilon>0$
, there is a finite subset
$F\subset \Gamma $
such that
$\bigvee _{g\in F} g^{-1}\mathcal P$
has diameter at most
$\varepsilon $
.
Given a cover of X labeled as
$\mathcal {P}=\{P_0,\ldots ,P_n\}$
, we define the subshift cover
${Y(\Gamma \curvearrowright X, \mathcal {P})}$
by
$$ \begin{align*} &Y(\Gamma\curvearrowright X, \mathcal{P})\\ &\quad= \{ y \in \{0,\ldots,n\}^{\Gamma} : \mbox{there exists } x \in X \mbox{ such that for every } g \in \Gamma, g^{-1}x \in \overline{P_{y(g)}}\}. \end{align*} $$
The idea behind this definition is that every configuration in the subshift labels the orbit of some element
$x\in X$
under the action
$\Gamma \curvearrowright X$
by indicating the elements of
$\mathcal {P}$
it hits. A compactness argument shows that a configuration y lies in
$Y(\Gamma \curvearrowright X, \mathcal P)$
if and only if for every finite
$F\subset \Gamma $
and pattern
$p\colon F\to \{0,\ldots ,n\}$
which occurs in y, the set
$$ \begin{align*} D(p):=\bigcap_{g\in F} g^{-1}(\overline{P_{p(g)}}). \end{align*} $$
is non-empty. In particular,
$Y(\Gamma \curvearrowright X, \mathcal {P})$
is indeed a subshift. Now we prove that this well-known construction is computable when the cover is made by effectively closed sets.
Definition 4.3. A cover
$\mathcal P$
of X is called effective if its elements are effectively closed sets.
Proposition 4.4. Let
$\Gamma \curvearrowright X$
be a computable action of a finitely generated group, S be a finite generating set of
$\Gamma $
, and let
$F(S)\curvearrowright X$
be the induced action. Then, the associated subshift
$Y(F(S) \curvearrowright X, \mathcal {P})$
is effective uniformly for all effective covers
$\mathcal {P}$
.
Proof. It suffices to show that we can semi-decide, given an effective cover
$\mathcal {P}$
and a pattern
$p \colon W \to F(S)$
with
$W\subset F(S)$
finite, whether
$D(p)=\varnothing $
. Observe that
$D(p)$
is an effectively closed subset of X, uniformly in p and
$\mathcal {P}$
. Indeed, each
$P_i$
is an effectively closed subset of X, the preimage of an effectively closed set by a computable function is effectively closed, and the finite intersection of effectively closed sets is effectively closed. Thus, we can uniformly semi-decide whether
${D(p)}$
is empty using the recursive compactness of X (see Definition 3.7 and Remark 3.12).
Remark 4.5. In what follows, we focus on the construction of effective covers. These will be obtained intersecting X with unions of closures of basic balls in
$\mathcal {X}$
. Note that X is not assumed to be a computable metric space, and this is the reason why we appeal to the space
$\mathcal X$
.
Proposition 4.6. A cover of X whose elements are finite unions of elements of the form
$\overline {B}\cap X$
, where B are basic balls in
$\mathcal {X}$
, is effective.
Proof. This follows from the fact that X is effectively closed, and that the topological closure of a basic ball in
$\mathcal {X}$
is effectively closed (see Example 3.3).
The following construction provides a uniform sequence of refined effective covers at any desired resolution.
Lemma 4.7. There is an algorithm which on input
$n\in {\mathbb {N}}$
, computes an effective cover
$\mathcal {P}_n$
of X with diameter at most
$2^{-n}$
, and such that for every
$n\in {\mathbb {N}}$
,
$\mathcal P_ {n+1}$
refines
$\mathcal {P}_n$
, and the inclusion of elements in
$\mathcal P_ {n+1}$
to elements in
$\mathcal P _n$
is decidable uniformly on n. Moreover, if X is a zero-dimensional set, we can add the extra condition that
$\mathcal P$
is a partition of X.
Proof. Using the recursive compactness of X, one can compute a cover
$\mathcal {P}_0$
of X made by the intersection of X with (the closure of) basic balls of radius one. The algorithm now proceeds inductively on
$n \in \mathbb {N}$
. After it has computed
$\mathcal P_0,\ldots ,\mathcal P_n$
with the desired properties, it computes
$\mathcal P_{n+1}$
as follows. Let
$\{V_i\}_{i \in \mathbb {N}}$
be a computable enumeration of all finite unions of basic balls. First observe that there is a finite subset I of
${\mathbb {N}}$
such that the set
$\{V_i : i\in I\}$
satisfies the following conditions:
-
(1)
$V_i$
has diameter at most
$2^{-(n+1)}$
; -
(2)
$\overline {V}_i$
is contained in the interior of some of the elements of
$\mathcal P_n$
; -
(3) the union of
$V_i$
for
$i\in I$
contains X; -
(4) if X is zero-dimensional, then the sets
$\overline {V_i}\cap X$
are disjoint.
The existence of such a finite set of basic balls satisfying the first three conditions follows from the fact that X is compact and that the set
$\{V_i : i\in {\mathbb {N}}\}$
is a basis for the topology. If X is zero-dimensional, then the last condition can be added because by Proposition 3.15, we can take the basic sets to be clopen. We now observe that it is semi-decidable whether a finite subset I of
${\mathbb {N}}$
satisfies the conditions above:
-
(1) finite unions of (the closure of) basic balls are computable sets, so the first condition is routine;
-
(2) the semi-decidability of the second follows from the fact that
$\overline {V}_i\cap X$
is recursively compact and the interior of the elements in the partition are effectively open; -
(3) the semi-decidability of the third condition follows directly from the recursive compactness of X;
-
(4) finally, for the fourth condition, it suffices to note that in a recursively compact space, it is semi-decidable whether two effectively closed sets have empty intersection (recall that in a recursively compact space, we can semi-decide whether an effectively closed subset is empty, the intersection of two effectively closed sets is effectively closed, and this is a computable operation on the descriptions of the sets).
Thus, we can compute a set I as desired by an exhaustive search, and finally set
$\mathcal {P}_{n+1}=\{V_i\cap X : i\in I\}$
.
Proposition 4.8. If
$\Gamma \curvearrowright X$
admits a generating open cover, then it admits a generating effective cover.
Proof. Let
$\mathcal P$
be a generating open cover of
$\Gamma \curvearrowright X$
. We construct a new cover
$\mathcal P'$
as follows. Let
$\mathcal J$
be the collection of all sets of the form
$B_i\cap X$
which are contained in some element of
$\mathcal P$
, where
$B_i$
is a basic ball in
$\mathcal X$
. The fact that basic balls constitute a basis for a topology of
$\mathcal X$
, together with the compactness of X, imply that there is a finite subset
$\mathcal J'\subset \mathcal J$
which is an open cover of X. As
$\mathcal J'$
refines
$\mathcal P$
, it follows that it is also a generating cover of
$\Gamma \curvearrowright X$
. Finally, we define
$\mathcal P'$
as the closed cover obtained by taking the topological closure of all elements in
$\mathcal J'$
. By construction,
$\mathcal P'$
is a closed cover of X which is generating for the action
$\Gamma \curvearrowright X$
, and it follows from Proposition 4.6 that
$\mathcal P'$
is an effective cover.
We remark that in the previous proposition, we do not claim the cover
$\mathcal P'$
to be computable uniformly from a description of
$\Gamma \curvearrowright X$
, just its existence.
Proposition 4.9. If
$\Gamma \curvearrowright X$
admits a generating open cover and X is zero dimensional, then
$\Gamma \curvearrowright X$
admits an effective generating cover which is also a partition.
Proof. It follows from the hypotheses that X admits a generating open cover
$\mathcal P$
which is a partition of X. Indeed, let
$\mathcal P_0$
be an open cover for X which is generating for
$\Gamma \curvearrowright X$
. As X is zero-dimensional, there is an open cover
$\mathcal P$
of X which refines
$\mathcal P_0$
and constitutes a partition of X. Observe that the cover
$\mathcal P$
is also generating for
$\Gamma \curvearrowright X$
because it refines
$\mathcal P_0$
.
Repeating the construction in the proof of Proposition 4.8 with the cover
${\mathcal P=\{P_0,\ldots ,P_n\}}$
, we obtain a finite open cover
$\mathcal J'$
of X which refines
$\mathcal P$
, and such that every element in
$\mathcal J'$
has the form
$B\cap X$
, where B is a basic ball in
$\mathcal X$
. We define a new cover
$\mathcal P'=\{P^{\prime }_0,\ldots ,P^{\prime }_n\}$
by the following condition. For every
$i \in \{0,\ldots ,n\}$
,
$P^{\prime }_i$
is the union of all elements in
$\mathcal J'$
which are contained in
$P_i$
. The fact that
$\mathcal P$
is a partition of X implies that the same holds for
$\mathcal P'$
. It is also clear that
$\mathcal P'$
is a generating cover. We now verify that
$\mathcal P'$
is an effective cover. Indeed, the fact that
$\mathcal P'$
is a partition implies that the elements of
$\mathcal P'$
are closed in X. In particular, we can write
$$ \begin{align*}P^{\prime}_i=\overline{P^{\prime}_i}=\bigcup_{m\in M} \overline{B_m}\cap X,\end{align*} $$
where M is a finite subset of
${\mathbb {N}}$
and
$B_m$
are rational balls. Here, topological closures can be taken in X and in
$\mathcal X$
. Both topological closures coincide because X is a closed subset of
$\mathcal X$
and we consider X with the subspace topology. It follows from the previous set equality and Proposition 4.6 that
$\mathcal P'$
is also an effective cover.
4.2 Proof of main results
We start with the following observation for computable actions on zero-dimensional spaces.
Proposition 4.10. Let
$\Gamma \curvearrowright X$
be a computable action, where X is zero-dimensional subset of a computable metric space. Then,
$\Gamma \curvearrowright X$
is topologically conjugate to a computable action
$\Gamma \curvearrowright Y$
, where Y is an effectively closed subset of
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
.
Proof. This follows by conjugating the action
$\Gamma \curvearrowright X$
with a computable homeomorphism between X and an effectively closed subset of
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
, whose existence is guaranteed by Theorem 3.18.
We are now ready to present the proof of our main result.
Theorem 4.11. (Theorem A)
Let
$\Gamma \curvearrowright X$
be an EDS, where
$\Gamma $
is a finitely generated and recursively presented group. Then,
$\Gamma \curvearrowright X$
is the topological factor of a computable action of an effectively closed subset of
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
.
Proof. We start by replacing
$\Gamma \curvearrowright X$
by a computable representative, as defined in §3.4. As explained at the beginning of this section, we will construct a topological extension of
$\Gamma \curvearrowright X$
as the inverse limit of a sequence of subshifts.
Let S be a finite set of generators of
$\Gamma $
and
$F(S)$
be the free group generated by S. Let
$F(S)\curvearrowright X$
be the action induced from
$\Gamma \curvearrowright X$
and notice it is computable. We apply the tools from §4.1.2 to the action
$F(S)\curvearrowright X$
. Let
$(\mathcal P ^n)_{n\in {\mathbb {N}}}$
be a uniform sequence of effective covers as in Lemma 4.7. For each
$\mathcal P^n=\{P^n_0,\ldots ,P^n _{m_n}\}$
, we set
$A_n$
to be the alphabet
$\{0,\ldots ,m_n\}$
, and we let
$Y(F(S)\curvearrowright X, \mathcal P ^n)$
be the subshift cover associated to the action
$F(S)\curvearrowright X$
and the cover
$\mathcal P ^n$
. By Proposition 4.4, each
$Y(F(S)\curvearrowright X, \mathcal P ^n)$
is an effective subshift, and the sequence
$(Y(F(S)\curvearrowright X, \mathcal P ^n))_{n\in {\mathbb {N}}}$
is uniformly effective.
It is possible that some elements in
$F(S)$
which are mapped to the identity element in
$\Gamma $
(and thus act trivially on X), act non-trivially on
$Y(F(S)\curvearrowright X, \mathcal P ^n)$
. Indeed, if
$w\in F(S)$
is mapped to the identity element in
$\Gamma $
, and there are distinct
$i,j$
such that
${P^n_{i} \cap P^n_{j} \neq \varnothing }$
, we could associate distinct elements to
$1_{F(S)}$
and w, and thus w acts non-trivially on
$Y(F(S)\curvearrowright X, \mathcal P ^n)$
. This is solved as follows. For each n, we define
$Y_n$
by
$$ \begin{align*}Y_n = Y(F(S)\curvearrowright X, \mathcal P ^n)\cap \widehat{A_n^\Gamma}\subset A_n^{F(S)},\end{align*} $$
where
$\widehat {A_n^\Gamma }$
is the pullback of
$A_n^\Gamma $
to
$F(S)$
. As
$\Gamma $
is recursively presented, the set
$\widehat {A_n^\Gamma }$
is effectively closed (Example 3.23). As
$Y_n$
is the intersection of two effectively closed sets, then
$Y_n$
is effectively closed. Furthermore, as
$Y(F(S)\curvearrowright X, \mathcal P ^n)$
is uniform and the second set in the intersection (
$\widehat {A_n^\Gamma }$
) is the same for each n, it follows that
$(Y_n)_{n \in \mathbb {N}}$
is uniformly effectively closed.
We now build a zero-dimensional topological extension of
$\Gamma \curvearrowright X$
, and then we verify the computability of the construction. We define an
$F(S)$
-subshift
$Z_n$
on alphabet
${B_n=A_0\times \cdots \times A_n}$
by the following two conditions:
-
(1)
$Z_n \subset Y_0 \times \cdots \times Y_n$
; -
(2) for each
$z\in Z_n$
and for each
$w\in F(S)$
with
$z(w)=(e_0,\ldots ,e_n)$
, we have
$$ \begin{align*}P^n_{e_n}\subset\cdots\subset P^0_{e_0}.\end{align*} $$
For each n, let
$\pi _{n+1}\colon Z_{n+1}\to Z_n$
be the map which removes the last component of the tuple. Then, let Z be the inverse limit of dynamical systems
$$ \begin{align*}Z=\varprojlim Z_n=\bigg\{(z_n)\in\prod_{n \in \mathbb{N}} Z_n\mid\pi_{n+1}(x_{n+1})=x_n, n\geq 1\bigg\}\subset\prod_{n \in \mathbb{N}} B_n^{F(S)}.\end{align*} $$
We now go into some computability considerations. First, observe that for each
$n\in \mathbb {N}$
,
$Z_n$
is an effectively closed subset of
$B_n^{F(S)}$
. As
$(Y_n)$
is a uniform sequence of effectively closed sets, we can semi-decide whether the first condition fails. Moreover, the second defining condition of
$Z_n$
is decidable, uniformly on n, by construction of the sequence
$(\mathcal P^n)_{n\in {\mathbb {N}}}$
(Lemma 4.7). Thus,
$(Z_n)_{n \in \mathbb {N}}$
is a uniform sequence of effective
$F(S)$
-subshifts. It is also clear that
$(\pi _n)_{n\geq 1}$
is a uniform sequence of computable functions, which are also factor maps. Now we claim that Z is a recursively compact subset of
$\prod _{n \in \mathbb {N}} B_n^{F(S)}$
. This follows from three facts:
-
(1) Z is an effectively closed subset of
$\prod _{n \in \mathbb {N}} B_n^{F(S)}$
by Proposition 4.2; -
(2) the product
$\prod _{n \in \mathbb {N}} B_n^{F(S)}$
is recursively compact by Theorem 3.9; -
(3) an effectively closed subset of a recursively compact computable metric space is recursively compact (Proposition 3.11).
The action
$F(S)\curvearrowright \prod _{n \in \mathbb {N}} B_n^{F(S)}$
is computable by Proposition 4.1, and then the same holds for
$F(S)\curvearrowright Z$
. By construction, every element
$w\in F(S)$
which corresponds to the identity element in
$\Gamma $
acts trivially on Z, and thus we can define an action
$\Gamma \curvearrowright Z$
by the expression
$gz=wz$
, where
$w\in F(S)$
is any element with
$\underline w = g$
. It remains to verify that
$\Gamma \curvearrowright Z$
is a topological extension of
$\Gamma \curvearrowright X$
. This is well known, but we sketch the argument for completeness.
We define a topological factor
$\phi \colon Z\to X$
as follows. First, for each
$n\in {\mathbb {N}}$
, we define
$\nu _n\colon Z\to Y_n$
as the function which sends
$z=(z_n)_{n\in {\mathbb {N}}}$
to the configuration
$\nu _n(z)$
given by
$\nu _n(z)(w) = (z_n)(w)(n)$
, the nth component of
$(z_n)(w)\in B_n$
. We now define
$\phi (z)$
by the expression
$$ \begin{align*}\{\phi(z)\}=\bigcap_{n\in{\mathbb{N}}} P^n_{\nu_n(z)(1_{F(S)})}.\end{align*} $$
The function
$\phi $
is well defined, as a nested intersection of non-empty compact sets with diameter tending to zero must be a singleton. It is straightforward to verify that
$\phi $
is continuous, surjective, and it commutes with the actions
$\Gamma \curvearrowright X$
and
$\Gamma \curvearrowright Z$
.
We have proved that
$\Gamma \curvearrowright Z$
is a computable action on a recursively compact and zero-dimensional subset of a computable metric space, and that it is a topological extension of
$\Gamma \curvearrowright X$
. Now by Corollary 4.10, the action
$\Gamma \curvearrowright Z$
is topologically conjugate to a computable action on an effectively closed subset of
$\{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
. This finishes the proof.
We end this section by proving that when the action admits a generating partition, the extension can be taken as an effective subshift. In the zero-dimensional regime, this is the computable version of the fact that subshifts are precisely the expansive actions on zero-dimensional sets.
Theorem 4.12. Let
$\Gamma \curvearrowright X$
be an EDS, where
$\Gamma $
is a finitely generated and recursively presented group and the action admits a generating open cover. Then,
$\Gamma \curvearrowright X$
is a topological factor of an effective
$\Gamma $
-subshift.
Moreover, if X is zero-dimensional, then
$\Gamma \curvearrowright X$
is topologically conjugate to an effective
$\Gamma $
-subshift and the recursively presented hypothesis on
$\Gamma $
can be removed.
Proof. We first prove the result assuming that
$\Gamma $
is recursively presented. By Proposition 4.8,
$\Gamma \curvearrowright X$
admits an effective generating cover
$\mathcal P$
. Now let S be a finite set of generators of
$\Gamma $
and let
$F(S)$
be the free group generated by S. Let
$F(S)\curvearrowright X$
be the action induced by
$\Gamma \curvearrowright X$
, and consider the subshift
$Y(F(S) \curvearrowright X, \mathcal P)$
defined in §4.1.2. By Proposition 4.4, we have that
$Y(F(S) \curvearrowright X, \mathcal P)$
is effective.
Observe that some elements in
$F(S)$
which are mapped to the identity element in
$\Gamma $
and thus act trivially on X, have a non-trivial action on
$Y(F(S) \curvearrowright X, \mathcal P)$
. To solve this, we define Y by
$$ \begin{align*}Y = Y(F(S) \curvearrowright X, \mathcal P)\cap \widehat{A^\Gamma},\end{align*} $$
where
$\widehat {A^\Gamma }$
is the pullback of
$A^\Gamma $
in
$F(S)$
. As
$\Gamma $
is recursively presented, the set
$\widehat {A^\Gamma }$
is effectively closed (Example 3.23), and thus Y is an effective subshift.
It is a standard fact that X is a topological factor of Y thanks to the fact that
$\mathcal P$
is a generating cover. We sketch the argument for completeness. Let
$(F_n)_{n\in \mathbb {N}}$
be an increasing sequence of finite subsets of
$F(S)$
whose union is
$F(S)$
. For each
$y\in Y(F(S) \curvearrowright X, \mathcal P)$
, we define
$D(y)$
as the following subset of X:
$$ \begin{align*} D(y) = \bigcap_{n\in{\mathbb{N}} } D(y|_{F_n}). \end{align*} $$
Recall that
$D(p)$
, for a pattern p, was defined in §4.1.2. For each
$y\in Y$
, the set
$D(y)$
is a singleton, being a nested intersection of non-empty compact sets with diameter tending to zero. Indeed, for each n, the set
$D(y|_{F_n})$
is contained in the cover
$\bigvee _{g\in F_n} g^{-1}\mathcal P$
, and the diameters of these elements tend to zero by definition of generating cover.
We can now define a topological factor map
$\phi \colon Y\to X$
by the expression
$$ \begin{align*}\{\phi(y)\}=D(y).\end{align*} $$
It is straightforward to verify that
$\phi $
is continuous, surjective, and it commutes with the actions
$\Gamma \curvearrowright X$
and
$\Gamma \curvearrowright Y$
.
We have proved the claim for recursively presented groups. We now prove that if X is zero-dimensional, the hypothesis that
$\Gamma $
is recursively presented can be removed. Note that if X is zero-dimensional, then by Proposition 4.9, we can assume that
$\mathcal P$
is also a partition, which makes
$\phi $
injective and, therefore, a topological conjugacy. In particular, it preserves the set of group elements which act trivially. More precisely, recall that
${F(S)\curvearrowright X}$
is the action induced by
$\Gamma \curvearrowright X$
. As
$F(S)$
has decidable word problem, the previous construction shows that the action
$F(S)\curvearrowright X$
is topologically conjugate to an effectively closed
$F(S)$
-subshift Y. Being a topological conjugacy, every element in
$F(S)$
which maps to the trivial element of
$\Gamma $
must act trivially on Y. Thus, we can define a
$\Gamma $
-subshift Z given by
$$ \begin{align*}Z= \{z\in A^\Gamma: \mbox{there exists } y \in Y \mbox{ where } y(w) = z(\underline{w}) \mbox{ for every } w \in F(S) \}.\end{align*} $$
It is straightforward that the pullback
$\widehat {Z}$
to
$F(S)$
is precisely Y, and thus Z is an effective
$\Gamma $
-subshift as required.
5 Simulation by subshifts of finite type
The main motivation behind Theorem A is that it can be used to enhance several results in the literature that characterize zero-dimensional effective dynamical systems as topological factors of subshifts of finite type. We shall provide a general definition that will help us to summarize most of these results.
Consider two groups
$\Gamma ,H$
and suppose there exists an epimorphism
$\psi \colon \Gamma \to H$
, that is, that H is a quotient of
$\Gamma $
. Given an action
$H \curvearrowright X$
, recall that the induced action of
$H \curvearrowright X$
to
$\Gamma $
is the action
$\Gamma \curvearrowright X$
which satisfies that
$g\cdot x = \psi (g)\cdot x$
for every
$g \in \Gamma $
.
Definition 5.1. Let
$\Gamma $
and H be finitely generated groups and
$\psi \colon \Gamma \to H$
be an epimorphism. We say
$\Gamma $
simulates H (through
$\psi $
) if for every effectively closed set
$X\subset \{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
and every computable action
$H \curvearrowright X$
, there exists a
$\Gamma $
-SFT Y such that the induced action
$\Gamma \curvearrowright X$
is a topological factor of
$\Gamma \curvearrowright Y$
.
If the map
$\psi $
in the definition above is clear, then we do not mention it (for instance, if
$\Gamma $
is a direct product of H with another group, we assume that
$\psi $
is the projection to H). Furthermore, if
$\psi $
is an isomorphism, we say that
$\Gamma $
is a self-simulable group. Let us briefly summarize a few of the simulation results available in the literature
Theorem 5.2. The following simulation results hold.
-
(1) [Reference Hochman22]
$\Gamma = \mathbb {Z}^3$
simulates
$\mathbb {Z}$
. -
(2) [Reference Barbieri and Sablik4] Let H be a finitely generated group,
$d \geq 2$
and
$\varphi \colon H \to \operatorname {GL}_d(\mathbb {Z})$
. Then, the semidirect product
$\Gamma = \mathbb {Z}^d \rtimes _{\varphi } H$
simulates H (through the projection epimorphism). -
(3) [Reference Barbieri3] Let
$H,G_1,G_2$
be finitely generated groups. Then,
$\Gamma = H \times G_1 \times G_2$
simulates H. -
(4) [Reference Barbieri, Sablik and Salo6] Let
$H,K$
be finitely generated groups, suppose H is non-amenable and that K has decidable word problem, then
$\Gamma = H \times K$
simulates H. -
(5) [Reference Barbieri, Sablik and Salo5] The following groups are self-simulable:
-
• the direct product of any two finitely generated nonamenable groups;
-
• the general linear group
$\operatorname {GL}_n(\mathbb {Z})$
and the special linear group
$\operatorname {SL}_n(\mathbb {Z})$
for
$n \geq 5$
; -
• Thompson’s group V and the Brin–Thompson’s groups
$nV$
for
$n \geq 1$
; -
• finitely generated non-amenable Branch groups;
-
• the automorphism group
$\operatorname {Aut}(F_n)$
and the outer automorphism group
$\operatorname {Out}(F_n)$
of the free group
$F_n$
on n generators for
$n \geq 5$
; -
• the braid groups
$B_n$
for
$n \geq 7$
strands.
-
(In references [Reference Barbieri3, Reference Barbieri and Sablik4, Reference Hochman22], the simulation results are stated differently, using subactions rather than an induced action. However, they also hold in our terminology (the result in [Reference Barbieri3] is stated only for expansive actions, but it can be generalized with a slight modification in the proof which will be covered in an upcoming article).)
We can enhance all of the above results using Theorem A.
Theorem 5.3. (Theorem B)
Let
$\Gamma ,H$
be finitely generated groups and
$\psi \colon \Gamma \to H$
be an epimorphism. Suppose that H is recursively presented, then
$\Gamma $
simulates H if and only if for every effective dynamical system
$H \curvearrowright X$
, the induced action of
$\Gamma $
is a topological factor of a
$\Gamma $
-SFT.
Proof. Suppose first that for every EDS
$H \curvearrowright X$
, the induced action of
$\Gamma $
is a topological factor of a
$\Gamma $
-SFT. As a computable action on an effectively closed zero-dimensional set is, in particular, an EDS, it follows that
$\Gamma $
simulates H.
Conversely, let
$H \curvearrowright X$
be an EDS. As H is recursively presented, Theorem A implies that there exists an effectively closed set
$\widetilde {X}\subset \{\mathtt {0},\mathtt {1}\}^{\mathbb {N}}$
and a computable action
$H \curvearrowright \widetilde {X}$
such that
$H \curvearrowright X$
is a topological factor of
$H \curvearrowright \widetilde {X}$
. Taking the induced action of
$\Gamma $
of these two actions, it follows that
$\Gamma \curvearrowright X$
is a topological factor of
$\Gamma \curvearrowright \widetilde {X}$
. As
$\Gamma $
simulates H, there exists a
$\Gamma $
-SFT Y which factors onto
$\Gamma \curvearrowright \widetilde {X}$
and thus onto
$\Gamma \curvearrowright X$
.
Let us illustrate how Theorem B can be applied with a few examples.
Example 5.4. As mentioned in Example 3.28, the action
$\operatorname {GL}_n(\mathbb {Z}) \curvearrowright \mathbb {R}^n/\mathbb {Z}^n$
by left matrix multiplication is an EDS. For
$n \geq 5$
, the group
$\operatorname {GL}_n(\mathbb {Z})$
is both recursively presented and self-simulable, thus it follows by Theorem B that there exists a
$\operatorname {GL}_n(\mathbb {Z})$
-SFT which topologically factors onto
$\operatorname {GL}_n(\mathbb {Z}) \curvearrowright \mathbb {R}^n/\mathbb {Z}^n$
.
Example 5.5. Let
$\{\beta _i\}_{i=1}^4$
be four computable points in
$\mathbb {R}/\mathbb {Z}$
. Consider
$F_2 \times F_2 = \langle a_1,a_2 \rangle \times \langle a_3,a_4 \rangle $
and the action
$F_2 \times F_2 \curvearrowright \mathbb {R}/\mathbb {Z}$
given by
$a_i\cdot x = x+\beta _i \bmod {\mathbb {Z}}$
for
$i \in \{1,\ldots ,4\}$
, and remark that this action is in fact the pullback of an action
$\mathbb {Z}^4 \curvearrowright \mathbb {R}/\mathbb {Z}$
. As
$F_2\times F_2$
is recursively presented and self-simulable, it follows by Theorem B that there exists an
$(F_2\times F_2)$
-SFT which topologically factors onto
$F_2 \times F_2 \curvearrowright \mathbb {R}/\mathbb {Z}$
.
Example 5.6. Let G be a group,
$n \geq 2$
, and consider
$\Delta _n(G) \subset G^n$
the space of all n-tuples of elements of G whose product is trivial, that is,
$$ \begin{align*} \Delta_n(G) = \{ (x_1,\ldots,x_n)\in G^n : x_1\cdots x_n = 1_{G}\}.\end{align*} $$
The braid group
$B_n$
on n strands acts on
$\Delta _n(G)$
by
$$ \begin{align*}\sigma_i (x_1,\ldots,x_{i-1},x_{i},x_{i+1},\ldots,x_n) = (x_1,\ldots,x_{i-1},x_{i+1}, x_{i+1}^{-1}x_ix_{i+1},x_{i+2},\ldots,x_n), \end{align*} $$
where
$1 \leq i \leq n-1$
and
$\sigma _i$
is the element of
$B_n$
which crosses strands i and
$i+1$
(for the definition of braid group, refer to [Reference Birman, Brendle, Menasco and Thistlethwaite8]). If we let G be any compact topological group which admits a computable structure such that group multiplication is a computable map, for instance, the group of unitary complex matrices
$G = U(k) \leqslant \operatorname {GL}_k(\mathbb {C})$
for some
$k \geq 1$
, then
$\Delta _n(G)$
is an effectively closed set of
$G^n$
and the action
$B_n \curvearrowright \Delta _n(G)$
is computable. It follows that if
$n \geq 7$
, then there exists a
$B_n$
-SFT which topologically factors onto
${B_n \curvearrowright \Delta _n(G)}$
.
In [Reference Barbieri, Sablik and Salo5], it was proven that Thompson’s group F (see Example 2.13) is self-simulable if and only if F is non-amenable, which is a longstanding open question. We can therefore strengthen the characterization of the potential amenability of F in the following way.
Corollary 5.7. Thompson’s group F is amenable if and only if there exists an EDS
$F \curvearrowright X$
which is not the topological factor of an F-SFT.
In the literature, there are a few simulation results which apply exclusively to expansive maps. More precisely, let
$\Gamma $
and H be finitely generated groups and
$\psi \colon \Gamma \to H$
be an epimorphism. We say
$\Gamma $
simulates expansive actions of H (through
$\psi $
) if for every effective subshift
$X\subset A^{H}$
, there exists a
$\Gamma $
-SFT Y such that the pullback subshift
$\Gamma \curvearrowright X$
is a topological factor of
$\Gamma \curvearrowright Y$
. The most famous results are due to Aubrun and Sablik [Reference Aubrun and Sablik2] and Durand, Romaschenko, and Shen [Reference Durand, Romashchenko, Shen, Blass, Dershowitz and Reisig17] which state that
$\mathbb {Z}^2$
simulates expansive actions of
$\mathbb {Z}$
(through the projection epimorphism).
In light of Proposition 4.12, we can improve the expansive simulation theorems in the following way.
Theorem 5.8. Let
$\Gamma ,H$
be finitely generated groups and
$\psi \colon \Gamma \to H$
be an epimorphism. Suppose that H is recursively presented, then
$\Gamma $
simulates expansive actions of H if and only if for every effective dynamical system
$H \curvearrowright X$
which admits a generating cover (in particular, every expansive EDS), the induced action of
$\Gamma $
is a topological factor of a
$\Gamma $
-SFT.
6 Algebraic actions as effective dynamical systems
In this section, we will show that, under mild conditions, algebraic actions are effective dynamical systems and thus we can apply the results of the previous sections on them.
Definition 6.1. Let
$\Gamma $
be a countable group and X be a compact metrizable abelian group. We say that
$\Gamma \curvearrowright X$
is an algebraic action if
$\Gamma $
acts by continuous automorphisms of X.
Next we provide a few examples to give an idea of what algebraic actions look like. The reader can find a plethora of interesting examples in [Reference Schmidt32].
Example 6.2. Let
$X = (\mathbb {R}/\mathbb {Z})^2$
be the torus (with pointwise addition). For every
${A \in \operatorname {GL}_2(\mathbb {Z})}$
, the action
$\mathbb {Z} \curvearrowright X$
given by
$n\cdot x = A^{n}x$
is algebraic.
Example 6.3. Let
$\Gamma $
be a countable group and consider
$X = (\mathbb {R}/\mathbb {Z})^{\Gamma }$
with pointwise addition as the group operation. Then, X is a compact metrizable abelian group and the shift action
$\Gamma \curvearrowright X$
given by
$(g\cdot x)(h) = x(g^{-1}h)$
for every
$x \in X$
and
$g,h \in \Gamma $
is algebraic.
Example 6.4. Let
$e_1 = (1,0), e_2 = (0,1)$
in
$\mathbb {Z}^2$
and consider
$$ \begin{align*}X = \{ x \in (\mathbb{R}/\mathbb{Z})^{\mathbb{Z}^2} : \mbox{for every } u \in \mathbb{Z}^2, x(u)+x(u+e_1)+x(u+e_2) = 0 \bmod{\mathbb{Z}}\}.\end{align*} $$
Then, X is a compact metrizable abelian group (with pointwise addition) and the shift action
$\mathbb {Z}^2 \curvearrowright X$
is algebraic.
An interesting property of algebraic dynamical systems is that they can all be represented in a canonical way through the use of Pontryagin duality. This identification is well established in the literature (it can be found for
$\mathbb {Z}^d$
in [Reference Schmidt32] and for a general countable group in [Reference Kerr and Li24, Ch. 13]), so we shall provide a relatively short account of the main facts. A reader who is already familiar with the basics of algebraic actions of countable groups can skip directly to the paragraph above the definition of recursively presented algebraic action (Definition 6.5).
Let
$\Gamma $
be a countable group. The integral group ring
$\mathbb {Z}[\Gamma ]$
(usually denoted in the literature as
$\mathbb {Z}\Gamma $
to simplify the notation) is the set of all finitely supported maps
$p \colon \Gamma \to \mathbb {Z}$
endowed with pointwise addition and with polynomial multiplication. That is, for
${p,q \in \mathbb {Z}[\Gamma ]}$
and
$g\in \Gamma $
, then
$(p+q)(g) = p(g)+q(g)$
and
$p\cdot q (g) = \sum _{h \in \Gamma } p(gh^{-1})q(h)$
. For this reason, we usually denote elements
$p \in \mathbb {Z}[\Gamma ]$
as finite formal sums
${p = \sum _{i \in I} c_ig_i}$
with
$c_i \in \mathbb {Z}, g_i \in \Gamma $
. We also endow
$\mathbb {Z}[\Gamma ]$
with the
$*$
-operation given by
$p^* = \sum _{i \in I}c_ig_i^{-1}$
. We remark that for
$x \in (\mathbb {R}/\mathbb {Z})^{\Gamma }$
and
$p = \sum _{i \in I} c_ig_i \in \mathbb {Z}[\Gamma ]$
, the product
$x p^*\in (\mathbb {R}/\mathbb {Z})^{\Gamma }$
is well defined and given for every
$h \in \Gamma $
by
$$ \begin{align*} (x p^*)(h) = \sum_{i \in I} c_ix(hg_i) \bmod{\mathbb{Z}}. \end{align*} $$
Let us recall that for a locally compact abelian group X, its Pontryagin dual is the space
$\widehat {X}$
of all continuous homeomorphisms from X to
$\mathbb {R}/\mathbb {Z}$
. Notice that if we endow
$\widehat {X}$
with the topology of uniform converge on compact sets and with pointwise addition, then
$\widehat {X}$
is also a locally compact abelian group whose elements are called characters. We recall two well-known properties, their proofs can be found, for instance, in [Reference Morris27]. First, that X is a compact metrizable abelian group if and only if
$\widehat {X}$
is countable and discrete. Second, that there exists an isomorphism (as topological groups and through the canonical evaluation map) between X and its double dual 
.
Now, there is a natural correspondence between algebraic actions
$\Gamma \curvearrowright X$
and actions
$\Gamma \curvearrowright \widehat {X}$
by automorphisms by letting
$(g\cdot \chi )(x) = \chi (g^{-1}x)$
for every
$g \in \Gamma $
,
$x\in X$
, and
$\chi \in \widehat {X}$
. Moreover,
$\widehat {X}$
, endowed with its corresponding action, has a natural structure of countable left
$\mathbb {Z}[\Gamma ]$
-module, where for
$p = \sum _{i \in I} c_ig_i \in \mathbb {Z}[\Gamma ]$
and
$\chi \in \widehat {X}$
, the operation is given by
$$ \begin{align*} p \cdot \chi = \sum_{i \in I} c_i (g_i\cdot \chi). \end{align*} $$
Conversely, given a countable left
$\mathbb {Z}[\Gamma ]$
-module M endowed with the discrete topology, there is a natural action by (continuous) automorphisms
$\Gamma \curvearrowright M$
given by left multiplication by the monomials
$p_g = 1\cdot g$
using the module product operation, and as before, this induces an action by continuous automorphisms in
$\widehat {M}$
. In particular, this means that there is a one-to-one correspondence (up to isomorphism) between algebraic actions of
$\Gamma $
and countable left
$\mathbb {Z}[\Gamma ]$
-modules.
An algebraic action
$\Gamma \curvearrowright X$
is called finitely generated if its associated
$\mathbb {Z}[\Gamma ]$
-module is finitely generated. In this case, we can identify the module up to isomorphism with
$\mathbb {Z}[\Gamma ]^n/J$
for some integer
$n \geq 1$
and J a left-submodule of the free module
$\mathbb {Z}[\Gamma ]^n$
. Passing through the Pontryagin dual, this means that, in this case, without loss of generality, we can identify
$$ \begin{align*} X = \bigg\{ (x_1,\ldots,x_n) \in ((\mathbb{R}/\mathbb{Z})^{\Gamma})^n : \sum_{i=1}^n x_i p_i^* = 0 \mbox{ for every } (p_1,\ldots,p_n) \in J\bigg\}, \end{align*} $$
with the action 
being the left shift as in Example 6.3. An algebraic action
${\Gamma \curvearrowright X}$
is called finitely presented if the associated
$\mathbb {Z}[\Gamma ]$
-module is finitely presented. In this case, the module is isomorphic to
$\mathbb {Z}[\Gamma ]^n / \mathbb {Z}[\Gamma ]^k P$
for some
$n \in \mathbb {N}$
and a
$k \times n$
matrix
$P \in \mathcal {M}_{k \times n}(\mathbb {Z}[\Gamma ])$
. Therefore, in this case, we can identify
$$ \begin{align*} X = \bigg\{ (x_1,\ldots,x_n) \in ((\mathbb{R}/\mathbb{Z})^{\Gamma})^n : \sum_{i=1}^n x_i P_{i,j}^* = 0 \mbox{ for every } j \in \{1,\ldots,k\}\bigg\}. \end{align*} $$
We remark that the three examples given at the start of this section are finitely presented algebraic actions.
To state our results in their full generality, we will introduce an intermediate notion for algebraic actions which we call being ‘recursively presented’. Let S be a finite set of generators for a group
$\Gamma $
and for
$w \in S^*$
, denote by
$\underline {w}$
its corresponding element of
$\Gamma $
. Let
$\mathbb {Z}[S^*]$
be the space of finitely supported maps
$p \colon S^* \to \mathbb {Z}$
. To each map p, we can associate
$\underline {p}\in \mathbb {Z}[\Gamma ]$
by letting
$\underline {p}= \sum _{w \in \operatorname {\mathrm {supp}}(p)} p(w)\underline {w}$
.
Definition 6.5. Let
$\Gamma $
be a finitely generated group and S a finite set of generators. A finitely generated algebraic action
$\Gamma \curvearrowright X$
is called recursively presented if there exists
$n \in \mathbb {N}$
and a computable total map
$g \colon \mathbb {N} \to \mathbb {Z}[S^*]^n$
such that up to isomorphism, the action is the shift map on
$$ \begin{align*} X = \bigg\{ (x_1,\ldots,x_n) \in ((\mathbb{R}/\mathbb{Z})^{\Gamma})^n : \sum_{i=1}^n x_i\underline{g(k)_i}^* = 0 \mbox{ for every } k \in \mathbb{N}\bigg\}. \end{align*} $$
Notice that finitely presented algebraic actions are recursively presented, as they can be represented by the maps
$g\colon \mathbb {N} \to \mathbb {Z}[S^*]^n$
which are eventually the zero of
$\mathbb {Z}[S^*]^n$
and thus computable.
Theorem 6.6. Let
$\Gamma $
be a finitely generated and recursively presented group. Every recursively presented algebraic action
$\Gamma \curvearrowright X$
is an EDS.
Proof. Fix S a finite set of generators of
$\Gamma $
. Consider
$n \in \mathbb {N}$
and a computable total map
$g\colon \mathbb {N} \to \mathbb {Z}[S^*]^n$
which define the recursively presented algebraic action
$\Gamma \curvearrowright X$
. As the space
$(\mathbb {R}/\mathbb {Z})$
is recursively compact (with the structure given by the rationals and the euclidean metric), it follows by Theorem 3.9 that the product space
$((\mathbb {R}/\mathbb {Z})^{S^*})^n$
is also recursively compact. For
$x \in (\mathbb {R}/\mathbb {Z})^{S^*}$
and
$p \in \mathbb {Z}[S^*]$
, we formally define
$xp^* \in (\mathbb {R}/\mathbb {Z})^{S^*}$
by
$(xp^*)(w) = \sum _{u \in \operatorname {\mathrm {supp}}(p)} x(wu)p(u)$
. Notice that for
$w \in S^*$
, we have
$(x\underline {p}^{*})(\underline {w}) = (xp^*)(w)$
.
Consider the space Y of all
$(x_1,\ldots ,x_n)\in ((\mathbb {R}/\mathbb {Z})^{S^*})^n$
which satisfy the following two conditions:
-
(1) for every
$u,v \in S^*$
such that
$\underline {u}=\underline {v}$
and for every
$i \in \{1,\ldots ,n\}$
, we have
$x_i(u) = x_i(v)$
; -
(2) for every
$k \in \mathbb {N}$
, we have that
$\sum _{i=1}^n x_i g(k)_i^* = 0$
.
We claim that Y is an effectively closed subset of
$((\mathbb {R}/\mathbb {Z})^{S^*})^n$
. Indeed, as
$\Gamma $
is recursively presented, the set
$\texttt {EQ}(\Gamma ) = \{ (u,v)\in S^* \times S^* : \underline {u}=\underline {v}\}$
is recursively enumerable. For words
$u,v$
, consider the map
$f_{u,v} \colon ((\mathbb {R}/\mathbb {Z})^{S^*})^n \to (\mathbb {R}/\mathbb {Z})^n$
given by
$$ \begin{align*}f_{u,v}(x_1,\ldots,x_n) = (x_1(u)-x_1(v), \ldots, x_n(u)-x_n(v)).\end{align*} $$
It is clear that each
$f_{u,v}$
is computable (as projections are computable in the product space) and that the collection
$\{f_{u,v}\}_{(u,v) \in \texttt {EQ}(\Gamma )}$
is uniformly computable. As
$\{0\}$
is an effectively closed subset of
$(\mathbb {R}/\mathbb {Z})^n$
, it follows that
$Y_{(1)} = \bigcap _{(u,v) \in \texttt {EQ}(\Gamma )} f_{u,v}^{-1}(\{0\})$
is an effectively closed set. Remark that this is precisely the set of elements of
$((\mathbb {R}/\mathbb {Z})^{S^*})^n$
which satisfy condition (1).
Given
$k \in \mathbb {N}$
and
$v \in S^*$
, consider the map
$h_{k,v} \colon ((\mathbb {R}/\mathbb {Z})^{S^*})^n \to \mathbb {R}/\mathbb {Z}$
given by
$$ \begin{align*} h_{k,v}(x_1,\ldots,x_n) = \bigg(\sum_{i=1}^n x_i g(k)_i^*\bigg)(v) = \sum_{i =1 }^n \sum_{u \in \operatorname{\mathrm{supp}}(g(k)_i)} x_i(vu) g(k)_i(u). \end{align*} $$
It is clear from the fact that g is a total computable function that the collection
$(h_{k,v})_{k \in \mathbb {N}, v \in S^*}$
is uniformly computable. It follows that
$Y_{(2)} = \bigcap _{k \in \mathbb {N}}\bigcap _{v \in S^*} h_{k,v}^{-1}(\{0\})$
is an effectively closed set as well. Remark that this is precisely the set of elements of
$((\mathbb {R}/\mathbb {Z})^{S^*})^n$
which satisfy condition (2).
As
$Y = Y_{(1)}\cap Y_{(2)}$
, it follows that Y is an effectively closed subset of
$((\mathbb {R}/\mathbb {Z})^{S^*})^n$
.
Let us define for each
$s \in S$
the computable map
$t_s \colon Y \to Y$
given by
$(t_s(x_1,\ldots ,x_n)) (u) = (x_1,\ldots ,x_n)(s^{-1}u)$
. It is clear by condition (1) that these maps induce an action of
$\Gamma $
, and thus
$\Gamma \curvearrowright Y$
is a computable action on an effectively closed set. Finally, it follows from condition (2) that the map
$\phi \colon X \to Y$
given by
$(\phi (x_1,\ldots ,x_n))(w) = (x_1,\ldots ,x_n)(\underline {w})$
is a topological conjugacy, and thus
$\Gamma \curvearrowright X$
is an EDS.
Putting together Theorems 6.6 and B, we obtain the following corollary which, in turn, implies Theorem C (as finitely presented algebraic actions are recursively presented).
Corollary 6.7. (Theorem C)
Let
$\Gamma $
be a recursively presented self-simulable group. Then, every recursively presented algebraic action of
$\Gamma $
is the topological factor of some
$\Gamma $
-subshift of finite type.
7 Other computability notions for shift spaces
The goal of this section is to compare the computability notions for subshifts we have introduced in this article with other notions of computability for shift spaces that can be found in the literature. We start by showing that a subshift is an EDS if and only if it is effective as per Definition 3.21.
Proposition 7.1. Let
$\Gamma $
be a finitely generated group. A subshift
$X\subset A^{\Gamma }$
is an EDS if and only if it is effective.
Proof. Let us recall that for a finitely generated group
$\Gamma $
, a subshift
$X\subset A^{\Gamma }$
is effective if its pullback into the full shift
$A^{F(S)}$
is an effectively closed set. We already argued in Example 3.26 that every effective subshift is an EDS. Let us fix a finite set of generators S of
$\Gamma $
and denote by
$\widehat {X}\subset A^{F(S)}$
the pullback subshift of X on the free group
$F(S)$
. Suppose that
$\Gamma \curvearrowright X$
is topologically conjugate to a computable action on an effectively closed subset Y of a recursively compact metric space. By Corollary 4.10, we may assume without loss of generality that Y is an effectively closed subset of
$\{0,1\}^{\mathbb {N}}$
with the canonical computable structure. As
$\Gamma \curvearrowright X$
is topologically conjugate to
$\Gamma \curvearrowright \widehat {X}$
, there is a topological conjugacy
$\phi \colon Y \to \widehat {X}$
. For
$a \in A$
, let
$[a] = \{ \widehat {x} \in \widehat {X} : \widehat {x}(1_{F(S)}) = a\}$
; for a finite
$W\subset F(S)$
and
$p \in A^{W}$
, we let
$$ \begin{align*} [p] = \bigcap_{w \in W} w[p(w)] = \{ \widehat{x} \in \widehat{X} : \widehat{x}(w) = p(w) \mbox{ for every } w \in W\}. \end{align*} $$
As
$\phi $
is a homeomorphism, we have that
$C_a = \phi ^{-1}([a])$
is a finite union of cylinder sets in Y and thus an effectively closed subset of Y.
We claim that there exists an algorithm that given a finite
$W\subset F(S)$
and a pattern
$p \colon W \to A$
, accepts if and only if
$[p]\cap \widehat {X}=\varnothing $
. Indeed, given such a p, we may compute a description of
$C_p = \bigcap _{ w \in W} w \cdot C_{p(w)}$
. As the action
$\Gamma \curvearrowright Y$
is computable, it follows that each
$w\cdot C_{p(w)}$
is an effectively closed set and thus, as the intersection of finitely many effectively closed sets is effectively closed, one may semi-decide whether
$C_p = \varnothing $
, which occurs precisely when
$[p] \cap \widehat {X} =\varnothing $
. It follows that the collection
$\mathcal {F}_{\mathrm \max } = \{ p \mbox { is a pattern } : [p] \cap \widehat {X} = \varnothing \}$
is recursively enumerable. As
$\mathcal {F}_{\mathrm \max }$
is the maximal set of patterns which defines
$\widehat {X}$
, it follows that
$\widehat {X}$
is an effectively closed set.
In the literature, there is also an intrinsic notion of computability for subshifts based on codings of forbidden patterns. This notion was originally defined in [Reference Aubrun, Barbieri and Sablik1].
Let S be a finite set of generators of a group
$\Gamma $
and A be an alphabet. A partial function
$c\colon S^* \to A$
with finite support is called a pattern coding and its domain is denoted
$\operatorname {supp}(c)$
. Recall that for
$w \in S^*$
, we denote by
$\underline {w}$
the corresponding element of
$\Gamma $
. The cylinder set induced by a pattern coding c is given by
$$ \begin{align*} [c] = \{ x \in A^{\Gamma} : x(\underline{w}) = c(w) \mbox{ for every } w \in \operatorname{supp}(c) \}. \end{align*} $$
A pattern coding is inconsistent if there are
$u,v \in \operatorname {supp}(c)$
such that
$\underline {u}=\underline {v}$
, but
${c(u)\neq c(v)}$
. Notice that for inconsistent pattern codings, we have
$[c] = \varnothing $
. The set of all pattern codings is a named set, and thus we can speak about computability of sets of pattern codings. Given a set
$\mathcal {C}$
of pattern codings, we can define a subshift
$X_{\mathcal {C}}\subset A^{\Gamma }$
by
$$ \begin{align*} X_{\mathcal{C}} = A^{\Gamma} \setminus \bigcup_{g \in \Gamma, c \in \mathcal{C}} g[c]. \end{align*} $$
Definition 7.2. We say that a subshift
$X \subset A^{\Gamma }$
is effectively closed by patterns (ECP) if there exists a recursively enumerable set of pattern codings
$\mathcal {C}$
such that
$X = X_{\mathcal {C}}$
.
Example 7.3. For any finitely generated group
$\Gamma $
, every subshift of finite type
$X\subset A^{\Gamma }$
is ECP, as it is given by a finite set of forbidden pattern codings.
In what follows, we will show that for general finitely generated groups, being an ECP subshift is strictly weaker than being an EDS (or equivalently, an effective subshift), but that all notions coincide for recursively presented groups. For a subshift
$X\subset A^{\Gamma }$
, denote by
$\mathcal {C}_{\max }(X)$
the set of all pattern codings c such that
$[c]\cap X = \varnothing $
.
Proposition 7.4. Let
$\Gamma $
be a finitely generated group. A subshift
$X\subset A^{\Gamma }$
is effective if and only if the set
$\mathcal {C}_{\max }(X)$
is recursively enumerable.
Proof. Let
$\mathcal C_{\max }'$
be the set of all pattern codings c such that
$[c]\cap X = \varnothing $
and c is consistent on the free group
$F(S)$
. As the word problem in
$F(S)$
is decidable, it follows that
$\mathcal C_{\max }(X)$
is recursively enumerable if and only if
$\mathcal C_{\max }'$
is recursively enumerable.
Let us recall that X is an effective subshift when
$\widehat {X}\subset A^{F(S)}$
is effectively closed. We claim that
$\mathcal C_{\max }'$
is recursively enumerable if and only if
$\widehat {X}\subset A^{F(S)}$
is effectively closed. This is just by definition of an effectively closed set, as
$\mathcal C_{\max }'$
is exactly the set of pattern codings of patterns in the free group whose associated cylinders in
$A^{F(S)}$
do not intersect
$\widehat X$
.
In particular, as the set
$\mathcal {C}_{\max }(X)$
defines the subshift X, we obtain that every effective subshift is ECP.
Corollary 7.5. Let
$\Gamma $
be a finitely generated group and
$X\subset A^\Gamma $
be an effective subshift. Then, X is effectively closed by patterns.
We shall see that the converse only holds in recursively presented groups. For this, we shall need the following lemma.
Lemma 7.6. [Reference Aubrun, Barbieri and Sablik1, Lemma 2.3]
Let
$\Gamma $
be a finitely generated and recursively presented group. For every ECP subshift
$X\subset A^{\Gamma }$
, the set
$\mathcal {C}_{\max }(X)$
is recursively enumerable.
Corollary 7.7. On recursively presented groups, every ECP subshift is effective. Thus, on recursively presented groups, the three computability notions are equivalent.
We remark that for an effective cover
$\mathcal {P}$
of a recursively compact metric space X, the subshift
$Y(\Gamma \curvearrowright X, \mathcal {P})$
from Proposition 4.4 is ECP but not necessarily effective. This is fundamentally the reason why we need to ask that
$\Gamma $
is recursively presented in Theorem A.
A useful consequence of Corollary 7.7 is that on recursively presented groups, SFTs are effective subshifts. This follows from the fact that SFTs are ECP.
Corollary 7.8. Let
$\Gamma $
be a recursively presented group. Then, every
$\Gamma $
-SFT is effective.
Let us show that for non-recursively presented groups, there are always ECP subshifts which are not effective. Let A be a finite alphabet with
$|A|\geq 2$
and
$\Gamma $
a finitely generated group. Notice that the full
$\Gamma $
-shift
$A^{\Gamma }$
is ECP as it is defined through the empty set of pattern codings.
Proposition 7.9. The full
$\Gamma $
-shift is effective if and only if
$\Gamma $
is recursively presented.
Proof. If
$\Gamma $
is recursively presented, then the full
$\Gamma $
-shift is effective by Corollary 7.8. Conversely, if the full
$\Gamma $
-shift is effective, then
$\widehat {A^{\Gamma }}$
is an effectively closed set and thus by Proposition 7.4, the maximal set of forbidden pattern codings is recursively enumerable.
Let S be a finite generating set of
$\Gamma $
and consider the pullback
$\widehat {A^{\Gamma }}\subset A^{F(S)}$
. Fix two distinct symbols
$a,b \in A$
. Given
$w \in S^*$
, there is an algorithm that constructs its corresponding element
$\underline {w}\in F(S)$
and the pattern
$p_w \in A^{\{1_{F(S)},\underline {w}\}}$
with
$p_w(1_{F(S)}) = a$
and
$p_w(\underline {w})=b$
. Clearly,
$[p_w]\cap \widehat {A^{\Gamma }}=\varnothing $
if and only if w represents the identity in
$\Gamma $
and furthermore,
$\widehat {A^{\Gamma }} = A^{F(S)}\setminus \bigcup _{g \in \Gamma , w \in \operatorname {\texttt {WP}}(\Gamma )} g[p_w]$
.
It follows that given
$w \in S^*$
, we can recursively enumerate the w for which
${[p_w]\cap \widehat {A^{\Gamma }}=\varnothing }$
, which are precisely the elements of
$\texttt {WP}(\Gamma )$
. Therefore,
$\Gamma $
is recursively presented.
8 Topological factors of effective dynamical systems
We begin by showing that the class of EDS is not closed by topological factors. In particular, it shows that subshifts of finite type on certain groups may have factors that are not EDS. However, we shall show that under certain conditions such as having topological zero dimension, we can still provide computational restrictions that said factors must satisfy.
Given an action
$\Gamma \curvearrowright X$
, we define its set of periods as
$$ \begin{align*} \mathtt{Per}(\Gamma \curvearrowright X) = \{ g \in \Gamma : \mbox{there is } x \in X \mbox{ such that } gx = x\}.\end{align*} $$
The following lemma holds in general for any finitely generated group with decidable word problem. However, we shall only need it for the special case of
$\mathbb {Z}$
-actions.
Lemma 8.1. Let
$\mathbb {Z} \curvearrowright X$
be an EDS. Then,
$\mathtt {Per}(\mathbb {Z}\curvearrowright X)$
is a co-recursively enumerable set.
Proof. We will prove that the complement of
$\mathtt {Per}(\mathbb {Z} \curvearrowright X)$
is a recursively enumerable subset of
$\mathbb {Z}$
. Without loss of generality, replace
$\mathbb {Z} \curvearrowright X$
by a computable representative. Then, the product space
$X^2$
is recursively compact and thus the diagonal
$\Delta ^2 = \{ (x,x) \in X^2 : x \in X\}$
is an effectively closed subset and thus also recursively compact. As
$\mathbb {Z}\curvearrowright X$
is computable, it follows that the collection of diagonal maps
$f_n\colon X^2 \to X^2$
given by
$(x,y) \mapsto (T^n(x),y)$
for
$n \in \mathbb {Z}$
is uniformly computable, and thus the collection of sets
$Y_n = f_n^{-1}(\Delta ^2)$
is uniformly recursively compact. It follows that we can recursively enumerate the integers n such that
$Y_n \cap \Delta ^2 = \varnothing $
. In other words, the set
$$ \begin{align*} \mathbb{Z} \setminus \mathtt{Per}(\mathbb{Z} \curvearrowright X) = \{ n \in \mathbb{Z} : Y_n \cap \Delta^2 = \varnothing\} \end{align*} $$
is recursively enumerable.
The set of periods is an invariant of topological conjugacy; therefore, any action
$\mathbb {Z}\curvearrowright X$
for which the set of periods is not co-recursively enumerable cannot be topologically conjugate to an EDS (see Figure 1).
Proposition 8.2. The class of EDS is not closed under topological factor maps.
Figure 1 A representation of the actions
$\mathbb {Z}\curvearrowright X$
and
$\mathbb {Z} \curvearrowright Y$
.
Proof. Let us consider
$$ \begin{align*}X = \{0\} \cup \bigg\{ z \in \mathbb{C} : |z| = \frac{1}{n} \mbox{ for some integer }n \geq 1 \bigg\}. \end{align*} $$
Additionally, let
$T \colon X \to X$
be given by
$T(z) = z\exp (2\pi i |z|)$
. It is clear that X is a recursively compact subset of
$\mathbb {C}$
with the standard topology and that T is a computable homeomorphism which thus induces a computable action
$\mathbb {Z} \curvearrowright X$
. The map T consists of rational rotations on each circle, where the period is given by the inverse of the radius, and thus it is easy to see that
$\mathtt {Per}(\mathbb {Z}\curvearrowright X) = \mathbb {Z}$
.
Now let
$A \subset \mathbb {N}\setminus \{0\}$
be some infinite set and let
$Y\subset \mathbb {C}$
be given by
$$ \begin{align*}Y = \{0\} \cup \bigg\{ z \in \mathbb{C} : |z| = \frac{1}{n} \mbox{ for some } n \in A \bigg\}.\end{align*} $$
Similarly, the map
$S\colon Y\to Y$
given by
$S(z) = z\exp (2\pi i |z|)$
is a homeomorphism which induces an action
$\mathbb {Z} \curvearrowright Y$
.
Let
$f \colon X \to Y$
be the map given by
$$ \begin{align*} f(z) = \begin{cases} z & \mbox{if } |z| = \dfrac{1}{n} \mbox{ for some } n \in A, \\0 & \mbox{otherwise. } \end{cases}\end{align*} $$
It is clear from the definition that f is a continuous, surjective map such that
$f\circ T = S \circ T$
and thus a topological factor map from
$\mathbb {Z} \curvearrowright X$
to
$\mathbb {Z} \curvearrowright Y$
. However, notice that
$\mathtt {Per}(\mathbb {Z}\curvearrowright Y) = \mathbb {Z} A$
, that is, the set of integers which are integer multiples of some element of A.
Notice that as the set of prime numbers is decidable, then a subset A of prime numbers is co-recursively enumerable if and only if
$\mathbb {Z} A$
is co-recursively enumerable. In particular, if we take A which is not co-recursively enumerable, we would have that
$\mathtt {Per}(\mathbb {Z}\curvearrowright Y)$
is not co-recursively enumerable either and thus
$\mathbb {Z} \curvearrowright Y$
cannot be an EDS.
Proposition 8.3. The class of EDS is not closed under topological factor maps, even if we restrict to zero-dimensional spaces.
Proof. For each
$n\in {\mathbb {N}}$
, let
$X_n=\{0,\ldots ,n\}$
, and let
$t_n = (1\ 2\ \cdots \ n)$
be the permutation on
$X_n$
which fixes
$0$
and cyclically permutes
$1\mapsto 2\mapsto 3 \mapsto \cdots \mapsto n\mapsto 1$
. Now define
$Y_n$
as the product
$X_0\times \cdots \times X_n$
, and
$s_n$
as the map on
$Y_n$
which applies
$t_0,\ldots , t_n$
component-wise. We define
$\pi _{n+1}$
as the map
$Y_{n+1}\to Y_n$
which removes the last component of the tuple, this is a factor map from
$Y_{n+1}$
to
$Y_n$
with their respective actions. We now define Y as the inverse limit of sequence
$$ \begin{align*} \cdots\xrightarrow {\pi_{n+2}}\ Y_{n+1}\xrightarrow {\pi_{n+1}} Y_n \xrightarrow{\pi_{n} \ \ } \cdots \xrightarrow{\pi_1 \ \ } Y_0. \end{align*} $$
It is straightforward to verify that the set Y endowed with the component-wise action is a zero-dimensional EDS. Let
$A \subset \mathbb {N}$
. We now define a topological factor of Y called
$Y_A$
.
For each n, define
$g_n \colon X_n\to X_n$
, as follows. For
$n\not \in A$
,
$g_n$
sends everything to
$0$
. For
$n\in A$
,
$g_n$
is the identity function on
$X_n$
. Now define
$f_n\colon Y_n\to Y_n$
as the function which on component n applies
$g_n$
. Then,
$f_n$
is an endomorphism of
$Y_n$
with the action induced by
$s_n$
. Finally, define F as the endomorphism of Y which, in component n, applies
$f_n$
and let
$Y_A$
be the image of F, which is a compact subset of
$\prod _{n \in \mathbb {N}} Y_n$
by the continuity of F. We endow
$Y_A$
with the component-wise action inherited as a subsystem of Y.
As in the previous construction, it suffices to take A as a set of primes which is not co-recursively enumerable. In this case,
$Y_A$
is a zero-dimensional topological factor of the zero-dimensional EDS Y, but it cannot be an EDS because its set of periods is exactly
$\mathbb {Z} A$
which is not co-recursively enumerable.
Even if the class of EDS is not closed under topological factor maps, it is reasonable to assume that a factor of an EDS should still satisfy some sort of computability constraint. With the aim of understanding this class in the case of zero-dimensional spaces, we introduce a notion of weak EDS which will turn out to be stable under topological factor maps.
Definition 8.4. An action
$\Gamma \curvearrowright X$
with
$X \subset A^{\mathbb {N}}$
is a weak effective dynamical system (WEDS) if for every clopen partition
$\mathcal {P}= (P_i)_{i=1}^n$
of X, the subshift
$$ \begin{align*} &Y(\Gamma \curvearrowright X, \mathcal{P})\\ &\quad= \{ y \in \{1,\ldots,n\}^{\Gamma} : \mbox{there is } x \in X \mbox{ such that for every } g \in \Gamma,\ g^{-1}x \in P_{y(g)}\} \end{align*} $$
is effective.
Notice that for an action
$\Gamma \curvearrowright X$
with
$X\subset A^{\mathbb {N}}$
to be a WEDS, it suffices to check the condition on the clopen partitions
$\mathcal {P}_n = \{[w] : w \in A^n \mbox { and } [w]\cap X \neq \varnothing \}$
as this family of clopen partitions refines any other clopen partition. As
$\Gamma \curvearrowright X$
can be obtained as the inverse limit of the shift action on the
$Y(\Gamma \curvearrowright X, \mathcal {P}_n)$
, we may also define a WEDS as an action that can be obtained as the inverse limit of a sequence of effective subshifts. Notice that we do not require the sequence to be uniform in this definition.
Remark 8.5. Notice that any expansive WEDS
$\Gamma \curvearrowright X$
is automatically an EDS, as in this case,
$\Gamma \curvearrowright X$
is topologically conjugate to
$Y(\Gamma \curvearrowright X,\mathcal P)$
for any partition with small enough diameter, and thus we have that
$\Gamma \curvearrowright X$
is an EDS.
Proposition 8.6. If
$\Gamma \curvearrowright X$
is a zero-dimensional EDS, then it is a WEDS.
Proof. Let
$\mathcal P$
be a cover of X which consists of disjoint clopen sets and let S be a finite set of generators for
$\Gamma $
. Let us consider the action of the free group
$F(S)\curvearrowright X$
induced by the action
$\Gamma \curvearrowright X$
. We proved in Proposition 4.4 that the subshift
$Y(F(S)\curvearrowright X,\mathcal P)$
is effective and thus an EDS. We now prove that
$Y(\Gamma \curvearrowright X,\mathcal P)$
is an EDS. For this, it suffices to prove that every
$w\in F(S)$
with
$\underline {w}=1_\Gamma $
acts trivially on
$Y(\Gamma \curvearrowright X,\mathcal P)$
, as then we have a topological conjugacy between
$\Gamma \curvearrowright Y(\Gamma \curvearrowright X,\mathcal P)$
and
$\Gamma \curvearrowright Y(F(S) \curvearrowright X,\mathcal P)$
.
Assume that
$wy\neq y$
for some y in
$Y(F(S) \curvearrowright X,\mathcal P)$
to obtain a contradiction. We can assume that
$wy$
and y differ in
$1_{F(S)}$
by shifting y. By definition, this means that there is some element
$x\in X$
such that
$x\in P_{y(1_{F(S)})}$
and
$x\in P_{wy(1_{F(S)})}$
. This is a contradiction, as the computable map associated to w is the identity and thus the sets
$P_{y(1_{F(S)})}$
,
$P_{wy(1_{F(S)})}$
are disjoint.
Next, we show that the class of WEDS is closed under topological factors.
Proposition 8.7. Let
$\Gamma \curvearrowright X$
be a WEDS and
$\Gamma \curvearrowright Y$
be a zero-dimensional topological factor. Then,
$\Gamma \curvearrowright Y$
is a WEDS.
Proof. Denote by
$f \colon X \to Y$
the topological factor map and let
$\mathcal {P} = (P_i)_{i=1}^n$
be a clopen partition of Y. Then,
$\mathcal {Q} = (f^{-1}(P_i))_{i=1}^n$
is a clopen partition of X. As X is WEDS, we obtain that
$Y(\Gamma \curvearrowright X, \mathcal {Q})$
is an effective subshift. As
$Y(\Gamma \curvearrowright X, \mathcal {Q}) = Y(\Gamma \curvearrowright Y, \mathcal {P})$
, we obtain that Y is a WEDS.
As an immediate corollary of Propositions 8.6 and 8.7, we obtain the following corollary.
Corollary 8.8. Every zero-dimensional topological factor of a zero-dimensional EDS is a WEDS.
Finally, putting this result together with Theorem A, we obtain the following general result.
Proposition 8.9. Let
$\Gamma $
be a finitely generated and recursively presented group,
$\Gamma \curvearrowright X$
be an EDS, and
$\Gamma \curvearrowright Y$
be a zero-dimensional topological factor. Then,
$\Gamma \curvearrowright Y$
is a WEDS.
Proof. As
$\Gamma $
is recursively presented, by Theorem A, there is a zero-dimensional EDS extension of
$\Gamma \curvearrowright X$
. Then,
$\Gamma \curvearrowright Y$
is a topological factor of this zero-dimensional extension and thus, by Proposition 8.6, we obtain that it is a WEDS.
We have proved that for zero-dimensional systems, the class of EDS is different to the class of WEDS. Indeed, the example constructed in Proposition 8.3 is not an EDS, but it follows from Proposition 8.9 that is a WEDS.
Corollary 8.10. Let
$\Gamma \curvearrowright X$
be an EDS and
$\Gamma \curvearrowright Y$
be an expansive and zero-dimensional topological factor. If X is zero-dimensional or
$\Gamma $
is recursively presented, then
$\Gamma \curvearrowright Y$
is an EDS.
Corollary 8.11. The class of effective subshifts is closed under topological factor maps.
We remark that Corollary 8.11 can also be obtained through the Curtis–Hedlund–Lyndon theorem [Reference Ceccherini-Silberstein and Coornaert13, Theorem 1.8.1]. We finish this section with the following question which we were unable to answer.
Question 8.12. Is it true that any WEDS is the topological factor of some EDS?
Acknowledgments
The authors are grateful to Mathieu Hoyrup for stimulating conversations on the construction of explicit examples of non-effective dynamical systems in higher dimensions. We also thank an anonymous reviewer for suggesting several substantial improvements. S.B. was supported by the FONDECYT grants 11200037 and 1240085. N.C.-V. was partially supported by ANID CONICYT-PFCHA/Doctorado Nacional/2020-21201185, ANID/Basal National Center for Artificial Intelligence CENIA FB210017, and the European Union’s Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement No 731143. C.R. was supported by ANID/FONDECYT Regular 1230469 and ANID/Basal National Center for Artificial Intelligence CENIA FB210017.
