subsecref subsecname = thmref thmname = theorem lemref lemname = lemma
claimrefcmd = Claim LABEL:#1 defrefcmd = Definition LABEL:#1 proprefcmd =
Proposition LABEL:#1 thmrefcmd = Theorem LABEL:#1 subsecrefcmd = Subsection
LABEL:#1 remrefcmd = Remark LABEL:#1 correfcmd = Corollary LABEL:#1 exarefcmd
= Example LABEL:#1 lemrefcmd = Lemma LABEL:#1 figrefcmd = Figure LABEL:#1

# the geometric subgroup membership problem

Nicanor Carrasco-Vargas

###### Abstract.

We show that every infinite graph which is locally finite and connected admits
a translation-like action by $\mathbb{Z}$ such that the distance between a
vertex $v$ and $v\ast 1$ is uniformly bounded by 3. This action can be taken
to be transitive if and only if the graph has one or two ends. This strenghens
a theorem by Brandon Seward.

Our proof is constructive, and thus it can be made computable. More precisely,
we show that a finitely generated group with decidable word problem admits a
translation-like action by $\mathbb{Z}$ which is computable, and satisfies an
extra condition which we call decidable orbit membership problem.

As an application we show that on any finitely generated infinite group with
decidable word problem, effective subshifts attain all effectively closed
Medvedev degrees. This extends a classification proved by Joseph Miller for
$\mathbb{Z}^{d},$ $d\geq 1$.

###### 2020 Mathematics Subject Classification:

05C63, 20F65, 37B10, 03D99

##  1\. Introduction

###  1.1. Translation-like actions by $\mathbb{Z}$ on locally finite graphs

A right action $\ast$ of a group $H$ on a metric space $(X,d)$ is called a
translation-like action if it is free111Which means that $x\ast h=x$ implies
$h=1_{H}$, for $x\in X$, $h\in H$., and for each $h\in H$, the set
$\\{d(x,x\ast h)|\ x\in X\\}$ is bounded. If $G$ is a finitely generated group
endowed with the word metric associated to some finite set of generators, then
the action of any subgroup $H$ on $G$ by right translations $(g,h)\mapsto gh$
is a translation-like action. Thus, translation-like actions can be regarded a
generalization of subgroup containment.

Following this idea, Kevin Whyte proposed in [29] to replace subgroups by
translation-like actions in different questions or conjectures about groups
and subgroups, and called these geometric reformulations. For example, the von
Neumann Conjecture asserted that a group is nonamenable if and only if it
contains a nonabelian free subgroup. Its geometric reformulation asserts then
that a group is nonamenable if and only if it admits a translation-like action
by a nonabelian free group. While the conjecture was proven to be false [23],
Kevin Whyte proved that its geometric reformulation holds.

One problem left open in [29] was the geometric reformulation of Burnside’s
problem. This problem asked if every finitely generated infinite group
contains $\mathbb{Z}$ as a subgroup, and was answered negatively in [12].
Brandon Seward proved that the geometric reformulation of this problem also
holds.

######  Theorem 1.1 (Geometric Burnside’s problem, [27]).

Every finitely generated infinite group admits a translation-like action by
$\mathbb{Z}$.

A finitely generated infinite group with two or more ends has a subgroup
isomorphic to $\mathbb{Z}$ by Stalling’s structure theorem. Thus, it is the
one ended case that makes necessary the use of translation-like actions. In
order to prove 1.1, Brandon Seward proved a more general graph theoretic
result.

######  Theorem 1.2 ([27, Theorem 1.6]).

Let $\Gamma$ be an infinite graph whose vertices have uniformly bounded
degree. Then $\Gamma$ admits a transitive translation-like action by
$\mathbb{Z}$ if and only if it is connected and has one or two ends.

This result proves 1.1 for one ended groups, and indeed it says more, as the
translation-like action obtained is transitive. The proof of this result
relies strongly on the hypothesis of having uniformly bounded degree. Indeed,
the uniform bound on $d_{\Gamma}(v,v\ast 1)$ depends linearly on a uniform
bound for the degree of the vertices of the graph.

We will strengthen this result by weakening the hypothesis to the locally
finite case, and improving the uniform bound on $d_{\Gamma}(v,v\ast 1)$ to 3.

######  Theorem 1.3.

Let $\Gamma$ be an infinite graph which whose vertices have finite degree.
Then $\Gamma$ admits a transitive translation-like action by $\mathbb{Z}$ if
and only if it is connected and has one or two ends.

Moreover, the action can be taken such that the distance between a vertex $v$
and $v\ast 1$ is uniformly bounded by 3.

A problem left in [27, Problem 3.5] was to characterize which graphs admit a
transitive translation-like action by $\mathbb{Z}$. Thus we have solved the
case of locally finite graphs, and it only remains the case of graphs with
vertices of infinite degree.

We now mention an application of translation-like actions to Cayley graphs. It
follows from Seward’s theorem that every finitely generated group with one or
two ends has at least one set of generators $S$ for which $\text{Cay}(G,S)$
admits a bi-infinite Hamiltonian path [27, Theorem 1.8]. It is not known
whether this holds for every Cayley graph [27, Problem 4.8], but our result
yields an improvement in this direction.

######  Corollary 1.4.

Let $G$ be a finitely generated group with one or two ends, and let $S$ be a
finite set of generators. Then the Cayley graph of $G$ with respect to the
generating set $\\{g\in G|\ d_{S}(g,1_{G})\leq 3\\}$ admits a bi-infinite
Hamiltonian path.

This was known to hold for generating sets of the form $\\{g\in G|\
d_{S}(g,1_{G})\leq J\\}$, where $S\subset G$ is a finite generating set for
$G$ and $J$ depends linearly on the vertex degree of $\text{Cay}(G,S)$.

In the more general case where we impose no restrictions on ends, we obtain
the following result for non transitive translation-like actions. This
readiliy implies 1.1.

######  Theorem 1.5.

Every infinite graph which is locally finite and connected admits a
translation-like action by $\mathbb{Z}$ such that the distance between a
vertex $v$ and $v\ast 1$ is uniformly bounded by 3.

These statements about translation-like actions can also be stated in terms of
powers of graphs. Given a graph $\Gamma$, its $n$-th power $\Gamma^{n}$ is
defined as the graph with the same set of vertices, and where two vertices
$u,v$ are joined if their distance in $\Gamma$ is at most $n$. It was shown by
Jerome Karaganis [19] that the cube of a finite and connected graph is
Hamiltonian. Our 1.3 generalizes this to infinite graphs, that is, the cube of
a locally finite connected graph with one or two ends admits a bi-infinite
Hamiltonian path. In our proofs we make use of Karaganis result: we will
define bi-infinite Hamiltonian paths locally.

We mention that 1.5 has been proved in [7, Section 4], using the same fact
about cubes of finite graphs.

###  1.2. Computability of translation-like actions

Let us now turn our attention to the problem of the computability of
translation-like actions on groups or graphs. In order to discuss this
precisely, we need the following notions. A graph $\Gamma$ is computable if
there exists an algorithm which given two vertices $u$ and $v$, determines
whether they are neighbors or not. A stronger notion is that of a highly
computable graph, namely, a computable graph which is locally finite and for
which the function which maps a vertex to its degree is computable. This extra
condition is necessary to compute the neighborhood of a vertex.

An important example comes from group theory: if $G$ is a finitely generated
group with decidable word problem and $S$ is a finite set of generators, then
its Cayley graph with respect to $S$ is highly computable.

A classical example of a problem in graph theory which admits no computable
solution is that of finding infinite paths. Kőnig’s infinity lemma asserts
that every infinite, connected, and locally finite graph admits an infinite
path. However, there are highly computable graphs which admit paths, all of
which are uncomputable. Another example comes from Hall’s matching theorem.
There are highly computable graphs satisfying the hypothesis in the theorem,
but which admit no computable right perfect matching [21]. These two results
are used in the proof of Seward’s theorem, so the translation-like actions
from this proof are not clearly computable.

By a computable translation-like action on a computable graph $\Gamma$, we
mean that the function $\ast:V(\Gamma)\times\mathbb{Z}\to V(\Gamma)$ is
computable, i.e. there exists an algorithm which given a vertex $v\in
V(\Gamma)$ and $n\in\mathbb{Z}$, computes the vertex $v\ast n$.

In 4 we will provide a computable version of 1.3, from which follows that a
highly computable graph admits a transitive translation-like action by
$\mathbb{Z}$ if and only if it admits a computable one. The restriction on
ends is essential to make the proof computable, and indeed we can not show a
computable version of 1.5.

Our interest in the computability of translation-like actions comes from
symbolic dynamics, and the shift spaces associated to a group. We will need a
computable translation-like action such that it is possible to distinguish in
a computable manner between different orbits. Let us introduce a general
definition, though we will only treat the case where the acting group is
$\mathbb{Z}$.

######  Definition 1.6.

Let $G$ be a group, and $S\subset G$ a finite set of generators. A group
action of $H$ on $G$ is said to have decidable orbit membership problem if
there exists an algorithm which given two words $u$ and $v$ in $(S\cup
S^{-1})^{*}$, decides whether the corresponding group elements $u_{G},v_{G}$
lie in the same orbit under the action.

This property arises when one requires a standard construction in the shift
space $A^{G}$ to preserve a complexity measure called Medvedev degree. This is
the motivation behind the following result, whose application is discussed
below (1.8).

######  Theorem 1.7.

Let $G$ be a finitely generated infinite group with decidable word problem.
Then $G$ admits a computable translation-like action by $\mathbb{Z}$ with
decidable orbit membership problem.

It is interesting to note that the introduced property corresponds to the
geometric reformulation of a subgroup property: the decidable subgroup
membership problem. If $G$ is a finitely generated group with decidable word
problem, then the action of a subgroup $H$ by right translations has decidable
orbit membership problem if and only if $H$ has decidable subgroup membership
problem (4.10).

The proof of 1.7 is as follows. For groups with one or two ends, we will show
the existence of a computable and transitive translation-like action by
$\mathbb{Z}$, i.e. a computable version of 1.3. This has decidable orbit
membership problem for the trivial reason that has only one orbit. For groups
with two or more ends, we will obtain the desired translation-like action from
a subgroup isomorphic to $\mathbb{Z}$ with decidable membership problem. The
existence of this subgroup is a consequence of the computability of the normal
form from Stalling’s structure theorem on groups with decidable word problem
(4.8).

###  1.3. Medvedev degrees of effective subshifts

Let us now turn our attention to Medvedev degrees, a complexity measure which
is defined using computable functions. Precise definitions of this and the
following concepts are given in 5. Intuitively, the Medvedev degree of a set
$P\subset A^{\mathbb{N}}$ measures how hard is to compute a point in $P$. For
example, a set has zero Medvedev degree if and only if it has a computable
point. Note that this becomes meaningful if we regard $P$ as the set of
solutions to some problem.

This notion can be applied to a variety of objects, such as graph colorings
[25], paths on graphs, matchings from Hall’s matching theorem, and others [10,
Chapter 13]. In this article we consider Medvedev degrees of subshifts.

Let $G$ be a finitely generated group, and let $A$ be a finite alphabet. A
subshift is a subset of $A^{G}$ which is closed in the prodiscrete topology,
and is invariant under translations. Dynamical properties of subshifts have
been related to their computational properties in different ways. A remarkable
example of this is the characterization of the entropies of two dimensional
subshifts of finite type as the class of nonnegative $\Pi_{1}^{0}$ real
numbers [15].

In the same manner that it is done with the entropy, one may ask which is the
class of Medvedev degrees that a certain class of subshifts can attain. The
classification is known for subshifts of finite type in $\mathbb{Z}^{d},d\geq
1$. In the case $d=1$, all subshifts of finite type have Medvedev degree zero,
because all of them contain a periodic point, and then a computable point. In
the case $d\geq 2$, subshifts of finite type can attain the class of
$\Pi_{1}^{0}$ Medvedev degrees [28].

A larger class of subshifts is that of effective subshifts. A subshift
$X\subset A^{\mathbb{Z}}$ is effective if the set of words which do not appear
in its configurations is computably enumerable. This notion can be extended to
a finitely generated group, despite some intricacies that arise in relation to
the word problem of the group. In this article we deal with groups with
decidable word problem, and the notion of effective subshift is a
straightforward generalization.

Answering a question left open in [28], Joseph Miller proved that effective
subshifts over $\mathbb{Z}$ can attain all $\Pi_{1}^{0}$ Medvedev degrees
[22]. We generalize this result to the class of infinite, finitely generated
groups with decidable word problem.

######  Theorem 1.8.

Let $G$ be a finitely generated and infinite group with decidable word
problem. The class of Medvedev degrees of effective subshifts on $G$ is the
class of all $\Pi_{1}^{0}$ Medvedev degrees.

The idea for the proof is the following. Given any subshift $Y\subset
A^{\mathbb{Z}}$, we can produce a new subshift $X\subset B^{G}$ that
simultaneously describes translation-like actions by $\mathbb{Z}$, and
elements in $Y$. Then 1.7 ensures that this construction preserves the
Medvedev degree of $Y$, and the result follows from the known classification
for $\mathbb{Z}$.

Despite the simplicity of the proof we need to translate some computability
notions from $A^{\mathbb{N}}$ to $A^{G}$, this is done by taking a computable
numbering of $G$. The notions obtained do not depend of the numbering, and are
consistent with notions present in the literature defined by other means.

The mentioned construction using translation-like actions has been used in
different results in the context of symbolic dynamics. For example, to
transfer results on the emptiness problem for subshifts of finite type from
one group to another [18], to produce aperiodic subshifts of finite type on
new groups [18, 7], and to study the entropy of subshifts of finite type on
some amenable groups [3].

### Paper structure

In 2 we fix some notation, and recall some basic facts on graph and group
theory. We also fix our computability setting for countable sets. In 3 we show
1.3 and 1.5. In 4 we show 1.7, and apply this in 5 to prove 1.8.

### Acknowledgements

This paper would not have been possible without the help, guidance, and
careful reading of my two advisors. I am grateful to Sebastián Barbieri for
suggesting that translation-like actions would work to prove 1.8, and for
helping me with many details. I am also grateful to Cristóbal Rojas for
providing the computability background which took me to Medvedev degrees of
complexity, and finally to ask 1.8.

This research was supported by ANID 21201185 doctorado nacional, and the
project CID computing with infinite Data.

##  2\. Preliminaries

###  2.1. Graph theory

In this article all graphs are assumed to be undirected, without self loops,
and simple (not multigraphs). We now fix some terminology and recall some
basic facts.

Given a graph $\Gamma$ we denote its vertex set by $V(\Gamma)$, and its edge
set by $E(\Gamma)$. Each edge $e$ is an unordered pair of vertices
$\\{x,y\\}$, we say that $e$ joins $x$ and $y$, its endpoints. We also say
that $x,y$ are adjacent or neighbors. The degree of a vertex $x$ is the number
of its neighbors, and is denoted $\deg_{\Gamma}(x)$.

A subgraph of $\Gamma$ is a graph whose edge and vertex set are contained in
the edge and vertex set of $\Gamma$. A set of vertices $V\subset V(\Gamma)$
determines a subgraph of $\Gamma$, denoted $\Gamma[V]$, as follows. The vertex
set of $\Gamma[V]$ is $V$, and its edge set is the set of all edges in
$E(\Gamma)$ whose endpoints are both in $V$. We say that $\Gamma[V]$ is the
subgraph of $\Gamma$ induced by $V$.

Another way to obtain a subgraph of $\Gamma$ is by deleting a set of vertices.
For $V\subset V(\Gamma)$, $\Gamma-V$ denotes the graph $\Gamma[V(\Gamma)-V]$,
that is, we erase from $\Gamma$ all vertices in $V$, and all edges incident to
them. If $\Gamma^{\prime}$ is a subgraph of $\Gamma$, then
$\Gamma-\Gamma^{\prime}$ stands for $\Gamma-V(\Gamma^{\prime})$.

A path on $\Gamma$ is an injective function $f:[n,m]\subset\mathbb{Z}\to
V(\Gamma)$ which sends consecutive integers to adjacent vertices. We say that
$f$ joins $f(n)$ to $f(m)$, and define its length to be $n-m$.

We say that $\Gamma$ is connected when any pair of vertices are joined by a
path. A connected component of $\Gamma$ is a connected subgraph of $\Gamma$
which is maximal for the subgraph relation.

If $\Gamma$ is connected, we define the path length metric $d_{\Gamma}$ on
$V(\Gamma)$ as follows. Given two vertices $u$ and $v$, $d_{\Gamma}(u,v)$ is
the length of the shortest path which joins $u$ to $v$.

The number of ends of $\Gamma$ is the supremum of the number of infinite
connected components of $\Gamma-V$, where $V$ ranges over all finite sets of
vertices in $V(\Gamma)$. Thus the number of ends of $\Gamma$ is an element of
$\mathbb{N}\cup\\{\infty\\}$.

###  2.2. Elementary computability notions

The following definitions of computable functions and sets are fairly
standard, and can be found, for example, in [5].

Given any set $A$, we denote by $A^{*}$ the set of all finite words of
elements of $A$. In this context we call $A$ an alphabet. The empty word is
denoted by $\mathbb{\varepsilon}$. A word $u$ of length $n$ is a prefix of $v$
if they coincide in the first $n$ symbols.

Now let $A,B$ be finite alphabets. Recall that a partial function from
$A^{\ast}$ to $B^{\ast}$ is a function whose domain is a subset of $A^{\ast}$,
and that it is called total if its domain is all of $A^{\ast}$.

A partial function $f\colon\text{Dom}(f)\subset A^{*}\to B^{*}$ is computable
when there exists an algorithm which on input a word $w\in A^{*}$ in the
domain of $f$ halts and outputs $f(w)$, and which does not halt when given as
input a word outside the domain of $f$.

A subset $X\subset A^{*}$ is computable or decidable if there is an algorithm
that decides which elements belong to $X$ and which elements do not, that is,
its characteristic function is a total computable function.

A subset $X\subset A^{*}$ is computably enumerable or semi decidable if it is
the domain of a partial computable function. Equivalently, there is an
algorithm that halts with input $x$ if and only if $x\in X$. Equivalently, $X$
is the range of a partial computable function.

We say that a function or a set is uncomputable when it is not computable. It
is easily seen that a set $X$ is computable if and only if $X$ and its
complement are computably enumerable.

We can obtain computability notions on $\mathbb{N}^{p},p\geq 1$ by identifying
$\mathbb{N}^{p}$ with a computable subset of $A^{*}$, for some finite alphabet
$A$. Indeed, we commonly write elements of $\mathbb{N}^{p}$ as words on the
finite alphabet of digits from 0 to 9, the parenthesis symbols, and the comma
symbol.

###  2.3. Words and finitely generated groups

It will be convenient for us to keep the distinction between words and group
elements. Let $G$ be a group, and $S$ a subset of $G$. We denote by $S^{-1}$
the set $\\{s^{-1}|\ s\in S\\}$. Now given a word $w\in(S\cup S^{-1})^{*}$
which is the concatenation of $s_{1},\dots,s_{n}\in S$, we denote by $w^{-1}$
the word obtained by concatenating $s_{n}^{-1}\dots s_{1}^{-1}$.

Given a word $w\in(S\cup S^{-1})^{*}$, we denote by $w_{G}$ the group element
that it represents, that is, the group element obtained replacing
concatenation by the group operation. We also write $u=_{G}v$ if the words
$u,v$ correspond to the same group element.

A set $S\subset G$ is said to generate $G$ if every group element can be
written as a word in $(S\cup S^{-1})^{*}$, and $G$ is finitely generated if it
admits a finite generating set.

Let us assume now that $S$ is a finite set of generators for $G$. The
(undirected, and right) Cayley graph of $G$ relative to $S$ is denoted by
$\text{Cay}(G,S)$. Its vertex set is $G$, and two vertices $g,h$ are joined by
an edge when $gs=h$ for some $s\in(S\cup S^{-1})$. The path length metric that
this graph produces on $G$ is the same as the word metric associated to $S$,
denoted $d_{S}$. Given a pair of elements $g,h\in G$, their distance
$d_{S}(g,h)$ is the length of the shortest word $w\in(S\cup S^{-1})^{*}$ such
that $gw_{G}=h$. We denote by $B(g,r)$ the ball $\\{h\in G\mid d_{S}(g,h)\leq
r\\}$.

The number of ends of a finitely generated group is defined as the number of
ends of its Cayley graph, for some generating set. This definition does not
depend on the chosen generating set, and can only be among the numbers
$\\{0,1,2,\infty\\}$, as proved in [11, 17].

Now let $H$ be a subgroup of $G$. We say that $H$ has decidable subgroup
membership problem if the set $\\{w\in(S\cup S^{-1})^{*}\mid w_{G}\in H\\}$ is
decidable. This property depends only on $G$ and $H$, and not on $S$. In other
words, this set is decidable for some fixed and finite generating set $S$ if
and only if this holds for every generating set.

In the particular case where $H=\\{1_{G}\\}$, the set defined above is called
the word problem of $G$, and denoted by $\text{WP}(G,S)$. This notion is
related to that of computable group, which we discuss in the following
subsection.

###  2.4. Computability on countable sets via numberings

In this article we need to discuss the computability of graphs, group actions,
and infinite paths. For a group $G$, this will be related with computability
notions on the symbolic space $A^{G}$ in 5. We consider a unified approach
using numberings, a generalization of Gödel numberings introduced by Yuri
Ershov. A survey on the subject can be found in [13, Chapter 14].

######  Definition 2.1.

A (bijective) numbering of a set $X$ is a bijective map $\nu:N\to X$, where
$N$ is a decidable subset of $\mathbb{N}$. We call $(X,\nu)$ a numbered set.
When $\nu(n)=x$, we say that $n$ is a name for $x$, or that $n$ represents
$x$.

As long as the set $X$ is infinite, we can always assume that the set $N$
equals $\mathbb{N}$, because a decidable and infinite subset of $\mathbb{N}$
admits a computable bijection onto $\mathbb{N}$.

Computability notions are transferred from $\mathbb{N}$ to numbered sets as
follows. A subset $Y$ of $(X,\nu)$ is decidable or computable when
$\nu^{-1}(Y)\subset\mathbb{N}$ is a decidable set. Given two numbered sets
$\nu:N\to X$, $\nu:N^{\prime}\to X^{\prime}$, we can endow their product
$X\times X^{\prime}$ with a numbering as follows. The product of $\nu$ and
$\nu^{\prime}$ is a bijection $N\times N^{\prime}\subset\mathbb{N}^{2}\to
X\times X^{\prime}$, where $N\times N^{\prime}$ is a decidable subset of
$\mathbb{N}^{2}$. It remains to compose with a computable bijection between
$N\times N^{\prime}$ and a decidable subset
$N^{\prime\prime}\subset\mathbb{N}$, and we obtain a numbering of $X\times
X^{\prime}$.

This gives a definition of a decidable or computable relation $R\subset
X\times X^{\prime}$ between numbered sets $(X,\nu)$ and
$(X^{\prime},\nu^{\prime})$. In the particular case where the relation is a
function $f:X\to X^{\prime}$, this is equivalent to ask
$\nu^{\prime}{}^{-1}\circ f\circ\nu:\mathbb{N}\to\mathbb{N}$ to be computable.

Different numberings on a set $X$ may produce different computability
notions222Indeed, non equivalent numberings do admit a semilattice structure.
See [2] and references therein.. However after we impose some structure on the
set -such as functions or relations- and require the numbering to make them
computable, the possibilities can be dramatically reduced. A notable example
is that of finitely generated groups, as we will see later. The following two
definitions will be relevant to us.

######  Definition 2.2.

A computable group is a group $(G,\star)$ and a numbering $\nu$ of $G$ such
that the function $\star:G^{2}\to G$ is computable. A numbering of a group is
computable if it satisfies the previous condition.

For example, $\mathbb{Z}$ admits a computable numbering, and thus is a
computable group.

######  Definition 2.3.

A computable graph is an undirected graph $\Gamma$ and a numbering of
$V(\Gamma)$ such that the adjacency relation is decidable, i.e.
$\\{(x,y)\mid\\{x,y\\}\in$$E(\Gamma)\\}$ is a decidable subset of
$V(\Gamma)^{2}$. A computable graph is highly computable if it is locally
finite and the function $V\to\mathbb{N}$, $v\mapsto\deg(v)$ is computable.

Now a computable graph or group defines a class of computable objects. For
example, a bi-infinite path $f:\mathbb{Z}\to V(\Gamma)$ is computable if the
function $f$ is computable between numbered sets $\mathbb{Z}$ and $V(\Gamma)$,
and so on.

Let us now discuss some properties of computable groups and their numberings.
The following proposition will be used to define numberings easily.

######  Proposition 2.4.

Let $R\subset\mathbb{N}^{2}$ be a decidable equivalence relation. Then the set
of equivalence classes $\mathbb{N}^{2}/R$ admits a unique numbering, up to
equivalence, such that the relation $\in$ is decidable.

To prove the existence we can just represent each equivalence class by the
least natural number in that equivalence class, the full proof is given at the
end of this subsection.

Thus to define a numbering on any set $X$, it is enough to take a surjection
$s:\mathbb{N}\to X$ such that we can decide if two numbers $n,m$ name the same
element (so the relation $s(n)=s(m)$ is decidable), and this numbering enjoys
a uniqueness property. This can be applied in a variety of situations.

Now let $G$ be a group with decidable word problem, $S\subset G$ a finite set
of group generators, and $\pi:(S\cup S^{-1})^{\ast}\to G$ the map $w\mapsto
w_{G}$. The equivalence relation $\pi(u)=\pi(v)$ is decidable, as two words
$u$ and $v$ have the same image under $\pi$ if and only if $uv^{-1}$ lie in
the decidable set $\text{WP}(G,S)$. We obtain a numbering of $G$ by 2.4.
Indeed, this is a computable numbering, and it is the only one up to
equivalence:

######  Proposition 2.5 ([24]).

A finitely generated group admits a computable numbering if and only if it has
decidable word problem. If this is the case, then all its computable
numberings are equivalent.

Moreover, computability notions are preserved by group isomorphisms.

######  Proposition 2.6.

Let $G$ and $G^{\prime}$ be finitely generated groups with decidable word
problem, and $f:G\to G^{\prime}$ a group isomorphism. Then $f$ is computable
(for any computable numbering of $G$ and $G^{\prime}$).

The proofs are also given below. Let us now review some properties of highly
computable graphs, let $\Gamma$ be a highly computable graph. The crucial
consequence of this hypothesis is that given some vertex $v$, and
$r\in\mathbb{N}$, we can compute (uniformly on $v$ and $r$) all vertices in
the ball $\\{v\in V(\Gamma)\mid d_{\Gamma}(v,v_{0})\leq r\\}$. This is true
for $r=1$: as the adjacency relation is decidable, we can computably enumerate
the set $\\{v\in V(\Gamma)\mid d_{\Gamma}(v,v_{0})\leq 1\\}$, and
$\deg_{\Gamma}(v_{0})$ tells us at which point we have found them all. For
$r=2$, we just have to iterate the previous step over each vertex
$v_{1}\in\\{v\in V(\Gamma)\mid d_{\Gamma}(v,v_{0})\leq 1\\}$, and so on.

This also shows that on a highly computable graph, the path-length metric
$d_{\Gamma}:V(\Gamma)^{2}\to\mathbb{N}$ is a computable function.

Finally, let us observe that a computable numbering of a computable group is
automatically a computable numbering of $\text{Cay}(G,S)$: two vertices
$g,h\in G$ are joined if and only if $hg^{-1}\in S\cup S^{-1}$, and this is a
decidable relation (for example, because the numbering makes the group
operation computable and $S\cup S^{-1}$ is a finite set).

###### Proof of 2.4.

We first prove the existence. Taking the usual order on $\mathbb{N}$, we
define the decidable set $N\subset\mathbb{N}$ as follows. A natural number $n$
lies in $N$ if it is the minimal element of its equivalence class. Then
$\nu:N\to\mathbb{N}/R$ is a numbering. The $\in$ relation in
$\mathbb{N}\times\mathbb{N}^{2}/R$ is decidable. Given $n,m\in\mathbb{N}$,
where $m$ is a name for the equivalence class $\nu(m)$, we can decide if $n$
lies in the equivalence class $\nu(m)$ by checking if $(n,m)\in R$.

We now prove the uniqueness, let $\nu$ and $\mu$ be numberings of
$\mathbb{N}^{2}/R$ as in the statement. We see that the identity function from
$(\mathbb{N}^{2}/R,\nu)$ to $(\mathbb{N}^{2}/R,\mu)$ is computable, the
remaining direction holds for symmetry. Let $n$ be a name for the equivalence
class $\nu(n)$, we need to compute $m$ such that $\mu(m)=\nu(n)$. As $\in$ is
a decidable relation for $\nu$, we can compute $r\in\mathbb{N}$ so that
$r\in\nu(n)$. As $\in$ is also decidable for $\mu,$ we can compute the $\mu$
name $m$ of the equivalence class where $r$ lies. Thus $\mu(m)=\nu(n)$. ∎

###### Proof of 2.5.

Let $(G,\star)$ be a finitely generated group. If $G$ is finite, then the
statement holds. Indeed, it admits a computable numbering because a finite set
$N\subset\mathbb{N}$ is always decidable and a function $f:N^{2}\to N$ is
always computable. Any two numberings are equivalent because any bijection
between finite subsets of $\mathbb{N}$ is computable.

Let us now assume that $G$ is infinite, that it has decidable word problem,
and that $S$ is a finite set of group generators. We already defined a
numbering $\nu:\mathbb{N}\to G$ by means of the function $\pi:(S\cup
S^{-1})^{\ast}\to G$, $w\mapsto w_{G}$. We now show that this is a computable
numbering of $G$.

Indeed, let $n,m$ be names for $g,h\in G$. We need to compute a name for $gh$.
As the relation $\in$ is decidable for this numbering, we can compute two
words $u,v\in(S\cup S^{-1})^{*}$ such that $u_{G}=g$ and $v_{G}=h$. Again, as
$\in$ is decidable, we can compute a $\nu$ name for the equivalence class of
$(uv)_{G}$. Thus $\nu$ is a computable numbering of $G$.

Now keep the numbering $\nu$ just defined, and assume that $G$ has another
computable numbering $\mu$. Let us denote by $\bullet$ and $\diamond$ the
computable group operations on $\mathbb{N}$ defined by
$(\nu\times\nu)^{-1}(\star)$ and $(\mu\times\mu)^{-1}(\star)$, respectively.
Let us write $S\cup S^{-1}=\\{s_{1},\dots,s_{k}\\}\subset G$, and define
$\\{r_{1},\dots,r_{k}\\}\subset\mathbb{N}$ and
$\\{t_{1},\dots,t_{k}\\}\subset\mathbb{N}$ by
$\mu(t_{i})=\nu(r_{i})=s_{i},$where $i=1,\dots,k$.

We show that the identity function is computable from $(G,\nu)$ to
$(G,\nu^{\prime})$. On input $m\in\mathbb{N}$ (a $\nu$ name for a group
element), compute natural numbers $i_{1}\dots i_{n}$ such that
$m=r_{i_{1}}\bullet\dots\bullet r_{i_{n}}$. This can be done by searching
exhaustively, and using that $\bullet$ is computable. Then output
$t_{i_{1}}\diamond t_{i_{2}}\diamond\dots\diamond t_{i_{n}}^{\prime}$. Thus is
a $\mu$ name for the same group element. ∎

The proof of 2.6 is left to the reader, as it is identical to the previous
one.

##  3\. Translation-like actions by $\mathbb{Z}$ on locally finite graphs

In this section we prove 1.3 and 1.5. For this we will work with finite and
bi-infinite 3-paths.

######  Definition 3.1.

A 3-path (resp. bi-infinite 3-path) on a graph $\Gamma$ is an injective
function $f:[a,b]\to V(\Gamma)$, $[a,b]\subset\mathbb{Z}$, (resp.
$f:\mathbb{Z}\to V(\Gamma)$) such that consecutive integers in the domain are
mapped to vertices whose distance $d_{\Gamma}$ is at most 3. It is called
Hamiltonian if it visits all vertices.

It is known that a finite and connected graph admits a Hamiltonian 3-path, and
we can pick the first and last of its vertices [19]. We start by showing that
we can impose additional conditions on this 3-path.

######  Lemma 3.2.

Let $\Gamma$ be a connected finite graph, and $u\neq v$ two of its vertices.
Then $\Gamma$ admits a Hamiltonian $3$-path $f:[a,b]\to V(\Gamma)$ which
starts at $u$, ends at $v$, and moreover satisfies the following two
conditions.

  1. (1)

If $b-a\geq 2$, then $d_{\Gamma}(f(a),f(a+1))\leq 2$ and
$d_{\Gamma}(f(b-1),f(b))\leq 2$ (the first and last “jump” have length at most
2).

  2. (2)

There is no $c\in[a,b]$ with $c+1,c-1\in[a,b]$ and such that
$d_{\Gamma}(f(c-1),f(c))=3$ and $d_{\Gamma}(f(c),f(c+1))=3$ (there are no
consecutive length 3 “jumps”).

Using this we will construct bi-infinite 3-paths in an appropiate manner, and
this will provide a proof of 1.5 and 1.3. Before proving the lemma, let us
introduce some useful terminology.

Let $\Gamma$ be a finite graph, and let $f:[a,b]\to V(\Gamma)$ be a 3-path on
$\Gamma$. We say that $f$ starts at $f(a)$ and ends at $f(b)$, that it goes
from $f(a)$ to $f(b)$, and that $f(a),f(b)$ are the endpoints of $f$. We say
that vertices in $f([a,b])$ are visited by $f$, and abreviate this set by
$V(f)$.

Now let $f:[a,b]\to V(\Gamma)$ and $g:[c,d]\to V(\Gamma)$ be two 3-paths. We
say that $g$ extends $f$ if it does it as a function, that is, its restriction
to the domain of $f$ is equal to $f$. We define the concatenation of $f$ and
$g$ as the function $h$ which visits the vertices visited by $f$ and then the
vertices visited by $h$, in the same order. More precisely, $h$ has domain
$[a,b+1+d-c]$, and is defined by

$h(x)=\begin{cases}f(x)&x\in[a,b]\\\ g(x+b-1+c)&x\in[a+1,b+1+d-c].\end{cases}$

If $V(f)\cap V(g)=0$ and $d_{\Gamma}(f(b),g(c))\leq 3$, then $h$ is a 3-path
and extends $f$. Finally, the inverse of a 3-path $f:[a,b]\to V(\Gamma)$,
denoted $-f$, is the 3-path with domain $[-b,-a]$ and which sends $x$ to
$f(-x)$.

###### Proof of 3.2.

The proof is by induction on $|V(\Gamma)|$. The claim holds for
$|V(\Gamma)|\leq 3$, as in that case any pair of vertices are at distance at
most two.

Now let $\Gamma$ be a connected finite graph with $|V(\Gamma)|\geq 3$, let
$u\neq v\in V(\Gamma)$, and assume that the result holds for graphs with a
strictly lower amount of vertices. We will show that there is a Hamiltonian
3-path on $\Gamma$ from $u$ to $v$ as in the statement.

Let $\Gamma_{1},\dots,\Gamma_{n}$, $n\geq 1$ be the connected components of
$\Gamma-v$, and assume that $u$ lies in $\Gamma_{1}$. Moreover, let
$\Gamma_{n+1}$ be the graph whose only vertex is $v$.

For each $i\in[1,n+1]$ we pick a pair of vertices $u_{i}$ and $v_{i}$ in
$\Gamma_{i}$ as follows. For $i=1$ we pick $u_{1}=u$. If $\Gamma_{1}$ has only
one vertex then $v_{1}$ is also equal to $u$, otherwise $v_{1}$ is a vertex in
$\Gamma_{1}$ adjacent to $v$. For $i\in[2,n]$ we pick $u_{i}$ as a vertex in
$\Gamma_{i}$ adjacent to $v$. If $\Gamma_{i}$ has only one vertex then we pick
$v_{i}$ equal to $u_{i}$, otherwise we take $v_{i}$ as a vertex in
$\Gamma_{i}$ adjacent to $u_{i}$. Finally, we let $u_{n+1}$ and $v_{n+1}$ be
equal to $v$. Thus for $i\in[1,n]$, $v_{i}$ is at distance at most 3 from
$u_{i+1}$.

We now invoke the inductive hypothesis on each $\Gamma_{i}$, $i\in[1,n+1]$
(this is also correct when $|V(\Gamma_{i})|=1$), and obtain a 3-path $f_{i}$
from $u_{i}$ to $v_{i}$ as in the statement. We define $f$ as the
concatenation of $f_{1},\dots,f_{n+1}$, and claim that $f$ satisfies the
required conditions.

First observe that $f$ is a 3-path on $\Gamma$, as $V(f_{i})$ and $V(f_{j})$
are disjoint for $i\neq j\in[1,n+1]$, and the last vertex visited by $f_{i}$
is at distance at most 3 from the first vertex visited by $f_{i+1}$. It is
clear that it visits all vertices exactly once, so it is Hamiltonian.

We now verify that $f$ satisfies the first numbered condition in the
statement. We need the following observation, which follows from the fact that
$u_{i+1}$ is at distance at most one from $v$.

######  Remark.

If $\Gamma_{i}$ is a singleton, $i\in[1,n]$, then $d(v_{i},u_{i+1})\leq 2$.

We claim that after $u=u_{1}$, $f$ visits a vertex at distance at most 2 from
$u$. Indeed, if $|V(\Gamma_{1})|\geq 2$, then the claim holds by inductive
hypothesis on $f_{1}$. Otherwise it follows from the fact that $u_{1}=v_{1}$
and previous remark. Moreover, the last vertex visited by $f_{n}$, which is
$v_{n}$, is at distance at most 2 from $v$ ($n\geq 1$).

We now verify that $f$ satisfies the second numbered condition in the
statement. Take $c\in[a,b]$ such that $c+1$ and $c-1$ are both in $[a,b]$, we
claim that some of $f(c-1)$, $f(c+1)$ is at distance at most 2 from $f(c)$. To
prove this let $\Gamma_{i}$ be the component containing $f(c)$, and note that
$i\in[1,n]$. If $\Gamma_{i}$ has one vertex, then $d_{\Gamma}(f(c),f(c+1))\leq
2$ by the remark above. Now assume that $\Gamma_{i}$ has more than one vertex,
and recall that $f_{i}$ is a Hamiltonian 3-path on $\Gamma_{i}$ from $u_{i}$
to $v_{i}$ as in the statement. If $f(c)$ is some of $u_{i}$ or $v_{i}$, then
the fact that $f_{i}$ satisfies the first item in the statement shows the
claim. If $f(c)$ is not one of $u_{i}$ or $v_{i}$, then the fact that $f_{i}$
satisfies the second item in the statement shows the claim. This finishes the
proof.

∎

We now introduce the following condition. It will be used to extend 3-paths
iteratively.

######  Definition 3.3.

We say that a 3-path $f:[a,b]\to V(\Gamma)$ on a graph $\Gamma$ is bi-
extensible if the following conditions are satisfied.

  1. (1)

$\Gamma-f$ has no finite connected component.

  2. (2)

There is a vertex $u$ in $\Gamma-f$ at distance at most 3 from $f(b)$.

  3. (3)

There is a vertex $v\neq u$ in $\Gamma-f$ at distance at most 3 from $f(a)$.

If only the two first conditions are satisfied, we say that $f$ is right-
extensible.

We first need to show that bi-extensible and right-extensible 3-paths exist.
The proofs are easy, and are given by completeness.

######  Lemma 3.4.

Let $\Gamma$ be an infinite, connected, and locally finite graph. Then for any
pair of vertices $u$ and $v$, there is a right-extensible 3-path which starts
at $u$ and visits $v$.

###### Proof.

Let $f$ be a path joining $u$ and $v$, which exists by connectedness. Now
define $\Lambda$ as the graph induced in $\Gamma$ by the vertices in $f$ and
the ones in the finite connected components of $\Gamma-f$. Notice that as
$\Gamma$ is locally finite, there are finitely many such connected components,
and thus $\Lambda$ is a finite graph.

As $\Gamma$ is connected there is some vertex $w$ in $\Lambda$ which is
adjacent to some vertex outside $\Lambda$. By 3.2 there is a 3-path
$f^{\prime}$ which is Hamiltonian on $\Lambda$, starts at $u$ and ends in $w$.
We claim that this $f^{\prime}$ is right-extensible. Indeed, our choice of
$\Lambda$ ensures that $\Gamma-f^{\prime}$ has no finite connected component,
and our choice of the endpoint $w$ of $f^{\prime}$ ensures that the second
condition in the definition of right extensible 3-path is satisfied. This
finishes the proof. ∎

######  Lemma 3.5.

Let $\Gamma$ be an infinite, locally finite, connected graph, and let $w$ be a
vertex in $\Gamma$. Then there is a bi-extensible 3-path which visits $w$.

###### Proof.

Let $w^{\prime}\neq w$ be adjacent to $w$, and define $\Lambda$ to be the
subgraph of $\Gamma$ induced by the vertices $w$, $w^{\prime}$ and the ones in
the finite connected components of $\Gamma-\\{w,w^{\prime}\\}$. Thus $\Lambda$
is a finite connected subgraph of $\Gamma$, has at least two vertices, and
$\Gamma-\Lambda$ has no finite connected component.

As $\Gamma$ is connected, there is a vertex $u$ in $\Lambda$ which is adjacent
to some vertex $u^{\prime}$ in $\Gamma-\Lambda$. As $\Gamma-\Lambda$ has no
finite connected component, there is another vertex $v^{\prime}$ in
$\Gamma-\Lambda$ adjacent to $u^{\prime}$. Finally as $\Lambda$ is connected
and has at least two vertices, there is a vertex $v$ in $\Lambda$ adjacent to
$u$. Now we invoke 3.2 on $\Lambda$ to obtain a 3-path $f$ which is
Hamiltonian and goes from $u$ to $v$. We claim that $f$ is bi-extensible.
Indeed, our choice of $\Lambda$ ensures that $\Gamma-f$ has no finite
connected component. Moreover, $u$ is at distance one from the vertex
$u^{\prime}$ in $\Gamma-f$, and $v$ is at distance at most 3 from the vertex
$v\neq u$ in $\Gamma-f$. This finishes the proof. ∎

We now show that under suitable conditions, a bi-extensible 3-path can indeed
be extended to a larger bi-extensible 3-path, and we can choose the new 3-path
to visit some vertex $w$. The second condition in 3.2 will be important in the
following proof.

######  Lemma 3.6.

Let $\Gamma$ be an infinite, locally finite, and connected graph. Let $f$ be a
bi-extensible 3-path on $\Gamma$, and let $u\neq v\in\Gamma-f$ be two vertices
at distance at most 3 from the first and last vertex of $f$, respectively. If
$w$ is a vertex in the same connected component of $\Gamma-f$ that some of $u$
or $v$, then there is a 3-path $f^{\prime}$ which extends $f$, is bi-
extensible on $\Gamma$, and visits $w$. Moreover, we can assume that the
domain of $f^{\prime}$ extends that of $f$ in both directions.

###### Proof.

If $u$ and $v$ lie in different connected components of $\Gamma-f$, then then
the claim is easily obtained by applying 3.4 on each of these components.
Indeed, by 3.4 there are two right extensible 3-paths $g$ and $h$ in the
corresponding connected components of $\Gamma-f$, such that $g$ starts at $u$,
$h$ starts at $v$, and some of them visits $w$. Then the concatenation of
$-g$, $f$ and $h$ satisfies the desired conditions.

We now consider the case where $u$ and $v$ lie in the same connected component
of $\Gamma-f$, this graph will be denoted $\Lambda$. Thus $\Lambda$ is
infinite, locally finite, connected, contains $u$, $v$, and $w$.

We claim that there are two right-extensible 3-paths on $\Lambda$, $g$ and
$h$, satisfying the following list of conditions: $g$ starts at $u$, $h$
starts at $v$, some of them visits $w$, and $V(g)\cap V(h)=\emptyset$. In
addition, $(\Lambda-g)-h$ has no finite connected component, and has two
different vertices $u^{\prime}$ and $v^{\prime}$ such that $u^{\prime}$ is at
distance at most 3 from the last vertex of $g$, and $v^{\prime}$ is at
distance at most 3 from the last vertex of $h$.

Suppose that we have $g,h$ as before. Then we can define a 3-path $f^{\prime}$
by concatenating $-g$, $f$ and then $h$. It is easily seen from the properties
above that then $f^{\prime}$ satisfies the conditions in the statement.

We now construct $g$ and $h$. For this purpose, we take $\Lambda^{\prime}$ to
be a connected finite subgraph of $\Lambda$ which contains $u,v,w$ and such
that $\Lambda-\Lambda^{\prime}$ has no finite connected component.

The graph $\Lambda^{\prime}$ can be obtained, for example, as follows. As
$\Lambda$ is connected, we can take a path $f_{u}$ from $u$ to $w$, and a path
$f_{v}$ from $v$ to $w$. Then define $\Lambda^{\prime}$ as the graph induced
by the vertices in $V(f_{v})$, $V(f_{u})$, and all vertices in the finite
connected components of $(\Lambda-f_{v})-f_{u}$. This graph has the desired
properties by construction.

Let $p$ be a Hamiltonian 3-path on $\Lambda^{\prime}$ from $u$ to $v$ as in
3.2, we will split $p$ aproppiately to obtain $g$ and $h$. Let $w_{1}$ be a
vertex in $\Lambda^{\prime}$ which is adjacent to some vertex $v^{\prime}$ in
$\Lambda-\Lambda^{\prime}$, which exists as $\Lambda$ is connected. Now we
need the second condition in 3.2, which says that there is a vertex $w_{2}$ in
$\Lambda^{\prime}$ whose distance from $w_{1}$ is at most 2, and such that $p$
visits consecutively $\\{w_{1},w_{2}\\}$. We will assume that $p$ visits
$w_{2}$ after visiting $w_{1}$, the other case being symmetric. As
$\Lambda-\Lambda^{\prime}$ has no finite connected component, there is a
vertex $u^{\prime}$ in $\Lambda$ which is outside $\Lambda^{\prime}$ and is
adjacent to $v^{\prime}$. Thus, $w_{1}$ is at distance at most 2 from
$u^{\prime}$, and $w_{2}$ is at distance at most 3 from $v^{\prime}$.

We define $g$ and $h$ by splitting $p$ at the vertex $w_{1}$. More precisely,
let $[a,c]$ be the domain of $p$, and let $b$ be such that $p(b)=w_{1}$. Then
$h$ is defined as the restriction of $p$ to $[a,b]$, and $-g$ is defined as
the restriction of $p$ to $[b+1,c].$ Thus $h$ is a 3-path from $v$ to $w_{1}$,
and $g$ is a 3-path from $u$ to $w_{2}$. By our choice of $\Lambda^{\prime}$
and $p$, it is easily seen that the 3-paths $h$ and $g$ satisfy the mentioned
list of conditions, and this finishes the proof. ∎

Observe that when $\Gamma$ has one or two ends, the hypothesis of 3.6 on $u,v$
and $w$ are always satisfied. We obtain a very simple and convenient
statement: we can extend a bi-extensible 3-path so that it visits a vertex of
our choice.

######  Corollary 3.7.

Let $\Gamma$ be a locally finite, and connected graph with one or two ends.
Let $f$ be a bi-extensible 3-path, and let $w$ be a vertex. Then $f$ can be
extended to a bi-extensible 3-path which visits $w$. Moreover we can assume
that the domain of the new 3-path extends that of $f$ in both directions.

We are now in position to prove some results about bi-infinite 3-paths. We
start with the Hamiltonian case, which is obtained by iteration of 3.7. When
we deal with bi-infinite 3-paths, we use the same notation and abreviations
introduced before for 3-paths, as long as they are well defined.

######  Proposition 3.8.

Let $\Gamma$ be a one or two ended, connected, locally finite graph. Then it
admits a bi-infinite Hamiltonian 3-path.

###### Proof.

Let $(v_{i})_{i\in\mathbb{N}}$ be a numbering of the vertex set of $\Gamma$.
We define a sequence of bi-extensible 3-paths $(f_{i})_{i\in\mathbb{N}}$ on
$\Gamma$ in the following recursive manner. We define $f_{0}$ as a bi-
extensible 3-path which visits $v_{0}$, this is possible by 3.6. Now assume
that we have defined the bi-extensible 3-path $f_{i}$, and that it visits
$v_{i}$. We define $f_{i+1}$ as a bi-extensible 3-path on $\Gamma$ which
extends $f_{i}$, its domain extends the domain of $f_{i}$ in both directions,
and it visits $v_{i}$. This is possible by applying 3.7 to the graph $\Gamma$
and the 3-path $f_{i}$.

Finally, we define a bi-infinite 3-path $f:\mathbb{Z}\to\Gamma$ by setting
$f(n)=f_{i}(n)$, for $i$ big enough. Then $f$ is well defined because
$f_{i+1}$ extends $f_{i}$ as a function, and the domains of $f_{i}$ exhaust
$\mathbb{Z}$. By construction $f$ visits every vertex exactly once, so it is
Hamiltonian. This finishes the proof. ∎

We now proceed with the non Hamiltonian case, where there are no restrictions
on ends. We first prove that we can take a bi-infinite 3-path whose deletion
leaves no finite connected component.

######  Lemma 3.9.

Let $\Gamma$ be an infinite, connected, and locally finite graph. Then it
admits a bi-infinite 3-path $f$ such that $\Gamma-f$ has no finite connected
component.

###### Proof.

By first applying 3.5 and then iterating 3.6, we obtain a sequence of bi-
extensible 3-paths $(f_{i})_{i\in\mathbb{N}}$ on $\Gamma$, such that $f_{i+1}$
extends $f_{i}$ for all $i\geq 0$, and such that their domains exhaust
$\mathbb{Z}$. We define a bi-infinite 3-path $f:\mathbb{Z}\to\Gamma$ by
setting $f(n)=f_{i}(n)$, for $i$ big enough.

We claim that $\Gamma-f$ has no finite connected component. We argue by
contradiction, let us assume that $\Gamma_{0}$ is a nonempty and finite
connected component of $\Gamma-f$. Define $V_{1}$ as the set of vertices in
$\Gamma$ which are adjacent to some vertex in $\Gamma_{0}$, but which are not
in $\Gamma_{0}$. Then $V_{1}$ is nonempty for otherwise $\Gamma$ would not be
connected, and is finite because $\Gamma$ is locally finite. Thus there is a
natural number $k$ such that $f_{k}$ has visited all vertices in $V_{1}$. By
our choice of $V_{1}$, $\Gamma_{0}$ is a nonempty and finite connected
component of $\Gamma-f_{k}$, and this contradicts that $f_{k}$ is bi-
extensible. ∎

Now the proof of the following result is by iteration of 3.9.

######  Proposition 3.10.

Let $\Gamma$ an infinite, connected, and locally finite graph. Then there is a
set of bi-infinite 3-paths $f_{i}:\mathbb{Z}\to\Gamma$, $i\in I$, such that
$V(\Gamma)=\bigsqcup_{i\in I}V(f_{i})$.

###### Proof.

As $\Gamma$ is infinite, connected, and locally finite, we can apply 3.9 to
obtain a bi-infinite 3-path $f_{0}$ such that $\Gamma-f_{0}$ has no finite
connected component. Each connected component of $\Gamma-f_{0}$ is an
infinite, connected, and locally finite graph, so we can apply 3.9 on each of
them. Iterating this process in a tree-like manner, we obtain a family of
3-paths $f_{i}:\mathbb{Z}\to\Gamma$, $i\in I$. Observe that the countability
of the vertex set ensures that $V(\Gamma)=\bigsqcup_{i\in I}V(f_{i})$

∎

We now derive 1.5 and 1.3 from this statements in terms of bi-infinite
3-paths.

###### Proof of 1.5.

Let $\Gamma$ be a graph as in the statement, and let $f_{i},i\in I$ as in
3.10. We define $\ast:V(\Gamma)\times\mathbb{Z}\to V(\Gamma)$ by the
expression

$\displaystyle v\ast n$ $\displaystyle=f(f^{-1}(v)+n),\ n\in\mathbb{N},$

where $f$ is the only $f_{i}$ such that $v$ is visited by $f_{i}$. Observe
that $v\ast 1$ is well defined because $V(\Gamma)=\bigsqcup_{i\in I}V(f_{i})$.
This defines a translation-like action by $\mathbb{Z}$, where the distance
from $v$ to $v\ast 1$, $v\in V(\Gamma)$ is uniformly bounded by 3. ∎

###### Proof of 1.3.

Let $\Gamma$ be a graph as in the statement. By 3.8, $\Gamma$ admits a
Hamiltonian bi-infinite 3-path $f$. This defines a translation-like action by
$\mathbb{Z}$ as in the proof of 1.5, and it is transitive because $f$ is
Hamiltonian.

We now prove that a locally finite graph which admits a transitive
translation-like action by $\mathbb{Z}$ is connected and has one or two ends.
This is stated in [27, Theorem 3.3] for graphs with uniformly bounded vertex
degree, but the proof can be applied to locally finite graphs. We describe
here another argument.

Let $\Gamma$ be a locally finite graph which admits a transitive translation-
like action by $\mathbb{Z}$. Connectedness is clear. It is also clear that
$\Gamma$ must be infinite, so it does not have zero ends. Assume now that it
has at least 3 ends to obtain a contradiction. Denote this translation-like
action by $\ast$, and let $J=\max\\{d_{\Gamma}(v,v\ast 1)\mid v\in
V(\Gamma)\\}$. Now take any vertex $v\in V(\Gamma)$, and define the function
$f:\mathbb{Z}\to V(\Gamma)$ by $f(n)=v\ast n,n\in\mathbb{Z}$. This function is
bijective and sends consecutive integers to vertices in $\Gamma$ at distance
$d_{\Gamma}$ at most $J$.

As $\Gamma$ has at least $3$ ends, there is a finite set of vertices $V_{0}$
such that $\Gamma-V_{0}$ has at least three infinite connected components,
which we denote $\Gamma_{1},$ $\Gamma_{2}$ and $\Gamma_{3}$. By enlarging
$V_{0}$ if necessary, we can assume that any pair of vertices $u,v$ which lie
in different connected components in $\\{\Gamma_{1},\Gamma_{2},\Gamma_{3}\\}$
are at distance $d_{\Gamma}$ at least $J+1$. As $V_{0}$ is finite, there is a
finite set $[n,m]\subset\mathbb{Z}$ such that $f([n,m])$ contains $V_{0}$. By
our choice of $V_{0},$ $n$ and $m$, the set of vertices $f[m+1,\infty)$ is
completely contained in one of $\Gamma_{1}$, $\Gamma_{2}$, or $\Gamma_{3}$.
The same holds for $f(-\infty,n-1]$, and thus the remaining infinite component
is empty. This is a contradiction, and finishes the proof. ∎

We end this section by repeating a problem left in [27, Problem 3.5].

######  Problem 3.11.

Find necessary and sufficient conditions for a graph to admit a transitive
translation-like action by $\mathbb{Z}$.

1.3 shows that the number of ends and connectedness completely classify
locally finite graphs which admit a transitive translation-like action by
$\mathbb{Z}$. The case of graphs with vertices of infinite degree may be
different, as there is not a uniquely defined notion of ends there. This is
discussed in detail in [8].

##  4\. Computable translation-like actions by $\mathbb{Z}$

In this section we prove that every finitely generated group with decidable
word problem admits a computable translation-like by $\mathbb{Z}$ with
decidable orbit membership problem (1.7). Let us recall here the proof scheme.
For groups with at most two ends this is obtained from a computable version of
1.3. For the remaining case, we show that the group contains a subgroup
isomorphic to $\mathbb{Z}$ with decidable subgroup membership problem.

The reader may observe that in the case where the group has two ends we
provide two different proofs for 1.7. Indeed a group with two ends is
virtually $\mathbb{Z}$, and it would be easy to give a more direct proof, but
the intermediate statements have independent interest (4.1 and 4.8).

###  4.1. Computable and transitive translation-like actions

In this subsection we prove the following result, and derive from it 1.7 for
groups with one or two ends.

######  Theorem 4.1 (Computable 1.3).

A highly computable graph which is connected and has one or two ends admits a
computable and transitive translation-like action by $\mathbb{Z}$, where the
distance between a vertex $v$ and $v\ast 1$ is uniformly bounded by 3.

Joining this with 1.3 we obtain the following corollary.

######  Corollary 4.2.

A highly computable graph (resp. a finitely generated infinite group with
decidable word problem) admits a transitive translation-like action by
$\mathbb{Z}$ if and only if it admits a computable one.

As discussed in the introduction, this shows great contrast between transitive
translation-like actions and other infinite objects that arise in graph
theory, at least from the perspective of computability theory.

We now proceed with the proof, which is divided in different lemmas. Recall
that 1.3 was obtained by constructing a bi-infinite Hamiltonian 3-path (3.8).
In its proof we constructed a sequence of 3-paths $(f_{i})_{i\in\mathbb{N}}$
satisfying certain conditions. We will show that these conditions are
decidable, and this will suffice to compute the sequence by doing an
exhaustive search. For this we will need to separate the one and two ended
case. We start with the following result, which is used in both cases.

######  Lemma 4.3.

Let $\Gamma$ be a highly computable graph which is connected. There is an
algorithm which on input a finite set of vertices $V\subset V(\Gamma)$, halts
if and only if $\Gamma-V$ has some finite conected component.

###### Proof.

The intuitive idea is that we can discover a finite connected component of
$\Gamma-V$ by computing a finite but big enough subgraph. Let
$v_{0}\in\Gamma-V$, and for each $n\in\mathbb{N}$ let $\Gamma_{n+1}$ denote
the finite graph induced by all vertices $v$ in $\Gamma-V$ with
$d_{\Gamma}(v,v_{0})\leq n+1$. Observe that if some vertex $v$ lies in
$\Gamma_{n+1}$ and its distance to $v_{0}$ is at most $n$, then we see all its
$\Gamma-V$ edges or neighbors in the finite graph $\Gamma_{n+1}$. This if for
some $n_{0}$ there is a finite connected subgraph of $\Gamma_{n_{0}}$ which
remains the same on $\Gamma_{n_{0}+1}$, then it will remain the same for all
$n\geq n_{0}$, and thus it is a finite connected component of $\Gamma-V$. Thus
the following algorithm proves the claim:

For each $n\in\mathbb{N}$, compute $\Gamma_{n}$ and $\Gamma_{n+1}$, which is
possible as $\Gamma$ is highly computable, and do the following. Check if
there is a finite connected component of $\Gamma_{n}$ with no vertices in
$\Gamma_{n+1}$, and halt if this is the case. ∎

We now can show that in the one ended case, the property of being a bi-
extensible 3-path is decidable.

######  Lemma 4.4.

Let $\Gamma$ be a highly computable multigraph with one end. There is an
algorithm which on input a finite set of vertices $V\subset V(\Gamma)$,
decides if $\Gamma-V$ has no finite connected component.

In particular, it is decidable whether a 3-path is bi-extensible.

###### Proof.

We prove the first claim. By 4.3, it remains to prove the existence of an
algorithm which halts on input a finite set of vertices $V$ if and only if
$\Gamma-V$ is has no finite connected component. As $\Gamma$ has one end, this
is equivlent to ask if $\Gamma-V$ is connected. The following algorithm halts
on input $V$, a finite set of vertices, if and only if $\Gamma-V$ is
connected:

Compute the set $V_{0}$ of vertices in $\Gamma-V$ which are adjacent to some
vertex in $V$. For each pair of vertices of $V_{0}$, search exhaustively for a
path in $\Gamma-V$ which joins them. If at some point we have found such a
path for every pair of vertices in $V_{0}$, halt.

We now observe that the second claim in the statement is obtained from the
first. Note that the second and third condition in the definition of bi-
extensible 3-path are clearly decidable. ∎

We now proceed with the two ended case, where we make use of the finite
information contained in a finite set of vertices which disconnects the graph.

######  Lemma 4.5.

Let $\Gamma$ be a highly computable multigraph with two ends, and let
$V^{\prime}$ be a finite set of vertices such that $\Gamma-V^{\prime}$ has two
infinite connected components. There is an algorithm which on input a finite
set of vertices $V\subset V(\Gamma)$ which contains $V^{\prime}$, decides if
$\Gamma-V$ is has some finite connected component.

Now let $f_{0}$ be a bi-extensible 3-path on $\Gamma$ such that $\Gamma-f_{0}$
has two infinite connected components. It is decidable whether a 3-path $f$
which extends $f_{0}$ is bi-extensible.

###### Proof.

We now prove the first claim. By 4.3, it remains to show that there is an
algorithm which halts on input $V$ if and only if $\Gamma-V$ has no finite
connected component. As $V$ contains $V^{\prime}$, we know that $\Gamma-V$ has
exactly two infinite connected components. Now the following algorithm proves
the claim.

On input $V$, compute the set $V_{0}$ of vertices in $\Gamma-V$ which are
adjacent to some vertex in $V$. For each pair of vertices of $V_{0}$, search
exhaustively for a path in $\Gamma-V$ which joins them. Now halt if at some
point we find enough paths so that $V_{0}$ can be written as $V_{1}\sqcup
V_{2}$, where every pair of vertices in $V_{i}$ can be joined by a path in
$\Gamma-V$, $i=1,2$

We now observe that the second claim in the statement is obtained from the
first. Note that the second and third condition in the definition of bi-
extensible 3-path are clearly decidable. ∎

We can now show tht the bi-infinite Hamiltonian path in 3.8 can be computed.

######  Proposition 4.6 (Computable 3.8).

Let $\Gamma$ be a highly computable graph satisfying the hypothesis in 1.3.
Then it admits a Hamiltonian bi-infinite 3-path which is computable.

###### Proof.

Let $(v_{i})_{i\in\mathbb{N}}$ the numbering associated to the highly
computable graph $\Gamma$, so $V(\Gamma)=\\{v_{i}|\ i\in\mathbb{N}\\}$.

Now let $f_{0}$ be a 3-path which is bi-extensible and visits $v_{0}$. If
$\Gamma$ has two ends, then we also require that $\Gamma-f_{0}$ has two
infinite connected components (in this case we do not claim that the path
$f_{0}$ can be computed from a description of the graph, but it exists and can
be specified with finite information).

Now define the sequence of 3-path $(f_{i})_{i\in\mathbb{N}}$ in a recursive
and computable manner. Assume that $f_{i}$ has been defined, $i\geq 0$, and
define $f_{i+1}$ as any bi-extensible 3-path on $\Gamma$ such that $f_{i+1}$
extends $f_{i}$, its domain extends the domain of $f_{i}$ in both directions,
and it visits $v_{i}$. Its existence is guaranteed by applying 3.7 to the
graph $\Gamma$ and the 3-path $f_{i}$. Moreover, it can be computed by
searching exhaustively, the conditions imposed on $f_{i+1}$ are decidable
thanks to 4.4 and 4.5.

The remaining of the proof is the same as before. We define
$f:\mathbb{Z}\to\Gamma$ by $f(n)=f_{i}(n)$, for $i$ big enough, and this is a
and Hamiltonian 3-path on $\Gamma$. Moreover, it is computable becuse the
sequence $(f_{i})_{i\in\mathbb{N}}$ is computable. ∎

We can now prove 4.1.

###### Proof of 4.1.

Let $f:\mathbb{Z}\to V(\Gamma)$ be a bi-infinite 3-path on $\Gamma$ which is
Hamiltonian and computable, which exists thanks to 4.6. It is enough to
observe that the translation-like action $\ast:V(\Gamma)\times\mathbb{Z}\to
V(\Gamma)$ defined by

$\displaystyle v\ast n$ $\displaystyle=f(f^{-1}(v)+n),\ n\in\mathbb{N}$

is computable. ∎

As mentioned before, 4.1 implies inmediately that 1.7 holds for groups with
one or two ends.

###### Proof of 1.7 for groups with one or two ends.

Let $G$ be a finitely generated infinite group with one or two ends and
decidable word problem, let $\Gamma=\text{Cay}(G,S)$ where $S$ is a finite set
of generators for $G$, and endow $G$ with a computable numbering $\nu$. This
numbering makes $\Gamma$ a highly computable graph. Now 4.1 yields a
computable and transitive translation-like action on $(V(\Gamma),d_{\Gamma})$,
which is also a transitive and computable translation-like action on
$(G,d_{S})$. ∎

###  4.2. Computable normal forms from Stalling’s theorem

In this subsection we prove 1.7 for groups with two or more ends. For this we
will show that a finitely generated group with two or more ends has a subgroup
isomorphic to $\mathbb{Z}$ with decidable subgroup membership problem. This
will be obtained from the computability of the normal form associated to
Stalling’s structure theorem (see 4.8 below).

For the reader’s convenience, we recall some facts about HNN extensions,
amalgamated products, and normal forms. We refer the interester reader to [20,
Chapter IV]. Let $H=\langle S_{H}|R_{H}\rangle$, $t$ a symbol not in $S_{H}$,
and an isomorphism $\phi:A\to B$ between subgroups of $H$. The HNN extension
relative to $H$ and $\phi$ is the group with presentation

$H\ast_{\phi}:=\langle S_{H},t|\ R_{H},tat^{-1}=\phi(a),\forall a\in
A\rangle.$

Now let $T_{A}\subset H$ (respectively $T_{B}$) be a fixed set of
representatives for equivalence classes of $H$ modulo $A$ (respectively $B$).
A sequence of group elements
$h_{0},t^{\epsilon_{1}},h_{1},\dots,t^{\epsilon_{n}},h_{n}$ is in normal form
if $\epsilon_{i}\in\\{1,-1\\}$ and the following conditions are satisfied:

  1. (1)

$h_{0}\in H$

  2. (2)

if $\epsilon_{i}=-1$, then $h_{i}\in T_{A}$

  3. (3)

if $\epsilon_{i}=1$, then $h_{i}\in T_{B}$

  4. (4)

There is no subsequence of the form $t^{\epsilon},1_{H},t^{-\epsilon}$.

For every $g\in H\ast_{\phi}$ there exists a unique sequence in normal form
whose product equals $g$ in $H\ast_{\phi}$. The situation is analogous for
amalgamated products, which we define now. Consider two groups $H=\langle
S_{H}|\ R_{H}\rangle$ and $K=\langle S_{K}|R_{K}\rangle$, and an isomorphism
$\phi:A\to B$ between the subgroups $A\mathbb{\leqslant}H$ and
$B\mathbb{\leqslant}K$. The amalgamated product of $H$ and $K$ relative to
$\phi$ is the group with presentation

$H\ast_{\phi}K=\langle S_{H},S_{K}|\ a=\phi(a),\forall a\in A\rangle.$

Let $T_{A}\subset H$ (respectively $T_{B}\subset K$) be a fixed set of
representatives for $H$ modulo $A$ (respectively $K$ modulo $B$). Then a
sequence of group elements $c_{0},c_{1},\dots,c_{n}$ is in normal form if

  1. (1)

$c_{0}$ lies in $A$ or $B$

  2. (2)

For $i\geq 1$, each $c_{i}$ is in $T_{A}$ or $T_{B}$

  3. (3)

For $i\geq 1$ $c_{i}\neq 1$

  4. (4)

Succesive $c_{i}$ alternate between $T_{A}$ and $T_{B}$

For each element $g\in H\ast_{\phi}K$, there exist a unique sequence in normal
form whose product equals $g$ in $H\ast_{\phi}K$.

In the terms previously defined, we have:

######  Theorem 4.7 (Stalling’s structure theorem, [9]).

Let $G$ be a finitely generated group with two or more ends. Then one of the
following occurs:

  1. (1)

$G$ is an HNN extension $H\ast_{\phi}$.

  2. (2)

$G$ is an amalgamated product $H\ast_{\phi}K$.

In both cases the corresponding isomorphism $\phi\colon A\to B$ is between
finite and proper subgroups $A$ and $B$.

A classical application of normal forms is the following: if a group $H$ has
decidable word problem, and we take an HNN extension $H\ast_{\phi}$ satisfying
some particular hypothesis, then the extension $H\ast_{\phi}$ has computable
normal form, and as consequence, decidable word problem [20, pp 185]. For our
application, we need a sort of converse of this result. The proof is direct,
but we were unable to find this statement in the literature.

######  Theorem 4.8.

Let $G$ be a finitely generated group with two or more ends and decidable word
problem. Then the normal forms associated to the decomposition of $G$ as HNN
extension or amalgamated product is computable.

###### Proof.

Let us assume that we are in the first case, so $G$ is (isomorphic to) an HNN
extension of a group $H$:

$H\ast_{\phi}:=\langle S_{H},t|\ R_{H},tat^{-1}=\phi(a),a\in A\rangle.$

Let us show that the normal forms of $H\ast_{\phi}$ described above is
computable. For this purpose we will show that we can computably enumerate
sequences of words $w_{1},\dots,w_{n}$ whose corresponding group elements
$(w_{1})_{G},\dots,(w_{n})_{G}$ are in normal form (for fixed sets $T_{A}$ and
$T_{B}$), and be sure to enumerate normal forms for all group elements. To
compute the normal form of a group element $w_{G}$ given by a word $w$, we
just enumerate such sequences $w_{1},\dots,w_{n}$ until we find one satisfying
$w=_{G}w_{1}\dots w_{n}$. This is possible as $G$ has decidable word problem.

First note that the fact that $G$ is finitely generated and $A$ is finite
forces $H$ to be finitely generated (see [6, page 35]), so we can assume that
$S_{H}$ is a finite set. Moreover $H$ has decidable word problem because this
property is inherited by subgroups.

Now we claim that $A=\\{a_{1},\dots,a_{n}\\}$ has decidable membership problem
in $H$. Indeed, to decide if $w_{H}\in A$, we just have to check $w=_{H}a_{i}$
for $i=1,\dots,m$; this is possible as $A$ is finite and the word problem of
$H$ is decidable. As a consequence of this, we can also decide if $u\in Av$
for any $u,v\in(S_{H}\cup S_{H}^{-1})^{*}$, as this is equivalent to decide if
$uv_{H}^{-1}\in A$. The same is true for $B$.

Let us show how to enumerate a set of words $W_{A}\subset(S_{H}\cup
S_{H}^{-1})^{*}$ whose corresponding group elements are a colection of
representatives for $H$ modulo $A$, namely $T_{A}$. First define $u_{0}$ be
the empty word. Now assume that words $u_{0},\dots,u_{n}$ have been selected
and search for a word $u_{n+1}\in(S_{H}\cup S_{H}^{-1})^{*}$ which is not in
$Au_{0},\dots,Au_{n}$. It is clear then that $W_{A}$ is a computably
enumerable set of words, and that the set $T_{A}$ of the group elements of $H$
corresponding to these words is a set of representatives for $H$ modulo $A$.

A set $W_{B}$ corresponding to $T_{B}$ can be enumerated analogously. Thus we
can enumerate normal forms $w_{1},\dots,w_{n}$ as follows: $w_{1}$ is an
arbitrary element of $(S_{H}\cup S_{H}^{-1})^{*}$, and the rest are words of
$W_{A},$ $W_{B}$, or $\\{t,t^{-1}\\}$ so as to alternate as in the definition.
This finishes the proof for the case of an HNN extension.

If $G$ is an amalgamated product, the fact that $G$ and $C$ are finitely
generated forces $H$ and $K$ to be finitely generated (see [6, page 43]), and
thus we can assume that $S_{H}$ and $S_{K}$ are finite sets. The sets $W_{A}$
and $W_{B}$ corresponding to $T_{A}$ and $T_{B}$ can be computably enumerated
in the same manner as above, and the rest of the argument is identical to the
HNN case. ∎

Now the proof of the following result is inmediate.

######  Corollary 4.9.

Let $G$ be a finitely generated group with two or more ends and decidable word
problem. Then it has a subgroup isomorphic to $\mathbb{Z}$ with decidable
subgroup membership problem.

###### Proof.

If $G$ is an HNN extension, then the group $\langle
t\rangle\mathbb{\leqslant}G$ has decidable membership problem. Indeed a group
element $g$ is in this subgroup if and only if the normal form of $g$ or
$g^{-1}$ is $1,t,1\dots,t,1$.

If $G$ is an amalgamated product, let $u\in T_{H}$, $v\in T_{K}$ be any pair
of non trivial elements. Then the subgroup $\langle
uv\rangle\mathbb{\leqslant}G$ is infinite cyclic and has decidable membership
problem, as a group element $g$ is in this subgroup if and only if the normal
form of $g$ or $g^{-1}$ is $u,v,\dots,u,v$. ∎

As mentioned in the introduction, for translation-like actions coming from
subgroups, the two properties (decidable orbit membership problem, and
decidable subgroup membership problem) become equivalent.

######  Proposition 4.10.

Let $G$ be a finitely generated group. Then a subgroup $H\mathbb{\leqslant}G$
has decidable membership problem if and only if the action of $H$ on $G$ by
right translations has decidable orbit membership problem.

###### Proof.

Let us denote by $\ast$ the right action $G\times H\to G$, $(g,h)\mapsto gh$.
Now we just have to note that two elements $g_{1},g_{2}\in G$ lie in the same
$\ast$ orbit if and only if $g_{1}g_{2}{}^{-1}\in H$, and an element $g\in G$
lies in $H$ if and only if it lies in the same $\ast$ orbit as $1_{G}$.

It is clear how to rewrite this in terms of words, but we fill the details for
completeness. The set $\\{w\in(S\cup S^{-1})^{*}|\ w_{G}\in H\\}$ equals the
set of words $w\in(S\cup S^{-1})^{*}$ such that $w$ and $1_{G}$ lie in the
same orbit, which is a decidable set assuming that $\ast$ has decidable orbit
membership problem. We now assume that $\\{w\in(S\cup S^{-1})^{*}|\ w_{G}\in
H\\}$ is decidable. Given two words $u,v\in(S\cup S^{-1})^{*}$, they lie in
the same $\ast$ orbit if and only if the word $uv^{-1}$ lie in $\\{w\in(S\cup
S^{-1})^{*}|\ w_{G}\in H\\}$. ∎

We can now finish the proof of 1.7, where the only remaining step is to verify
the computability of the action.

###### Proof of 1.7 for groups with two or more ends.

Let $G$ be a finitely generated infinite group with decidable word problem. By
4.9 there is an element $c\in G$ such that $\langle c\rangle$ is isomorphic to
$\mathbb{Z}$, and has decidable subgroup membership problem in $G$. Thus the
right action $\ast:G\times\mathbb{Z}\to G,$ $(g,n)\mapsto(gc^{n})$ has
decidable orbit membership problem by 4.10.

It only remains to verify that this action is computable. This is obvious in
terms of words, but we write the details for completeness. Let $S$ be a finite
set of generators for $G$, and let $u$ be a word in $(S\cup S^{-1})^{*}$ such
that $u_{G}=c$. Now, the function which given a word $w\in(S\cup S^{-1})^{*}$
and an integer $n\in\mathbb{Z}$ outputs the concatenation $wu^{n}$, is a
computable function. Without loss of generality (2.5) we can endow $G$ with
the numbering obtained from the surjection $(S\cup S^{-1})^{*}\to G,w\mapsto
w_{G}$, and the previous paragraph makes it clear that the fuction $\ast$ is
computable. ∎

##  5\. Medvedev degrees of effective subshifts

In this section we prove 1.8. For this we need some definitions. Let $G$ be a
finitely generated group, and $A$ a finite set. A subshift is a subset
$X\subset A^{G}$ which is closed in the prodiscrete topology, and invariant
under the group action $G\mathbb{\curvearrowright}A^{G}$ by left translations
$(g\ast x)(h)\mapsto x(g^{-1}h).$ A pattern is a function $p:K\subset G\to A$
with finite domain, and it determines the cylinder

$[p]=\\{x\in A^{G}|\ x(k)=p(k)\hskip 10.00002pt\forall k\in K\\}.$

Cylinders are closed and open, and they form a basis for this topology. If
$g\ast x\in[p]$ for some $g\in G$, we say that $p$ appears on $x$.

A set of patterns $\mathcal{F}$ defines the subshift
$X_{\mathcal{\mathcal{F}}}$ of all elements $x\in A^{G}$ such that no pattern
of $\mathcal{F}$ appears in $x$. We say that $X_{\mathcal{F}}$ is obtained by
forbidding patterns of $\mathcal{F}$. Conversely, any subshift can be obtained
by forbidding patterns.

A subshift $X$ is called a subshift of finite type if it can be obtained by
forbidding finitely many patterns. We now discuss a notion of effectiveness of
subshifts, for which we need the following definition.

A pattern coding $c$ is a finite set of tuples
$\\{(w_{1},a_{1}),\dots,(w_{k},a_{k})\\}$, where $w_{i}\in S^{*}$ and
$a_{i}\in A$, and it is called consistent if for each $i,j$, $w_{i}=_{G}w_{j}$
implies $a_{i}=a_{j}$. A consistent pattern coding as above can be associated
to the pattern $p(c):K\subset G\to A$, where $K$ is the set of group elements
associated to $\\{w_{1},\dots,w_{k}\\}$, and $p((w_{i})_{G})=a_{i}$.

A set of pattern codings $\mathcal{C}$ defines the subshift $X_{\mathcal{C}}$
of all elements $x\in A^{G}$ such that no pattern of the form $p(c)$ appears
in $x$, where $c$ ranges over $\mathcal{C}$. Thus inconsistent pattern codings
are ignored by definition. A subshift $X$ is called effective if
$X=X_{\mathcal{C}}$ for a computably enumerable set of pattern codings
$\mathcal{C}$.

The previous definition was introduced in [1] to define effective subshifts
without assumptions on the word problem of the group. If we assume that $G$
has decidable word problem, we can decide which pattern codings are
consistent, and decide which ones corresponds to the same pattern. This gives
a bijective numbering of the set of all patterns as in 2.4, and we can say
that a set of patterns $\mathcal{F}$ is computably enumerable. It is then
clear that a subshift $X$ is effective if and only $X=X_{\mathcal{F}}$ for
some computably enumerable set of patterns $\mathcal{F}$.

A third equivalent notion is that an effective subshift is a subshift which is
also an effectively closed subset of $A^{G}$. For this to make sense, we need
to define effectively closed subsets of $A^{G}$. In what follows we will
transfer all computability notions from $A^{\mathbb{N}}$ to $A^{G}$ using
representations, in the sense of computability theory. This is used to define
the Medvedev degree of a subset of $A^{G}$, and to show that this notion
enjoys some stability properties.

###  5.1. Computability on $A^{\mathbb{N}}$, and Medvedev degrees

Despite $\mathbb{N}$ not being a group, we will use the same definitions of
patterns and cylinders in $A^{\mathbb{N}}$. A word $w_{0}\dots w_{n}\in A^{*}$
can be identified with a pattern $\\{0,\dots,n\\}\to A$, and thus $[w]=\\{x\in
A^{\mathbb{N}}|\ x_{0}\dots x_{n}=w\\}$.

We review now some facts on computability on the Cantor space that will be
needed, the reader is refered to [26]. The intuitive meaning in the following
definition is the following. A function $\Phi$ on $A^{\mathbb{N}}$ is
computable if there is a computable function on words which computes it via
finite prefixes, that is, it takes as input a finite prefix of $x\in
A^{\mathbb{N}}$ and outputs a finite prefix of $\Phi(x)$.

######  Definition 5.1 (Computable function).

A partial function $\Phi:D\subset A^{\mathbb{N}}\to B^{\mathbb{N}}$ is
computable if there exists a partial computable function $\phi:A^{*}\to B^{*}$
which is compatible with the prefix order on words333That is, if $u$ is a
prefix of $v$, then $\phi(u)$ is a prefix of $\phi(v)$., and such that $D$ is
the set of sequences $x\in B^{\mathbb{N}}$ where the following holds. As $n$
tends to infinity, $\phi(x_{0}\dots x_{n})$ is always defined, its length
tends to infinity, and $\bigcap_{n}[\phi(x_{0}\dots x_{n})]$ is the singleton
which only contains $\Phi(x)$.

An alternative definition uses the concept of oracle, which we have avoided to
make this article more accesible444A reader familiar with the concept of
oracle may prefer this definition: $\Phi$ is computable if there is a partial
computable function with oracle $\phi:\mathbb{N}\to B$, such that with oracle
$x$ and input $n\in\mathbb{N}$ returns the $n$-th coordinate of $\Phi(x)$,
that is $\phi^{x}(n)=\Phi(x)_{n}$ for $n\in\mathbb{N}$ and all $x$ in the
domain of $\Phi$..

######  Example 5.2.

The shift function $\sigma:2^{\mathbb{N}}\to 2^{\mathbb{N}},\sigma
x(n):=x(n+1)$ is computable. It is given by the function $s:2^{*}\to 2^{*}$,
$s(w_{0}w_{1}\dots w_{n})=w_{1}\dots w_{n}$.

The following is a fairly standard fact, but we give a proof as it will be
used later.

######  Proposition 5.3.

Let $f:\mathbb{N}\to\mathbb{N}$ be any computable bijection. Then the
homeomorphism

$\displaystyle F:A^{\mathbb{N}}$ $\displaystyle\to A^{\mathbb{N}}$
$\displaystyle x$ $\displaystyle\mapsto x\circ f$

is computable and with computable inverse $x\mapsto x\circ f^{-1}$.

###### Proof.

Note that a computable bijection of $\mathbb{N}$ has computable inverse. Now
we define the computable function $\phi$ as follows. On input $a_{1}\dots
a_{n}\in A^{\ast}$ compute $k=k(n)$ to be the biggest natural number such that
$\\{0,\dots,k\\}$ is contained in $\\{f(0),\dots,f(n)\\}$, and then output
$\phi(a_{0}\dots a_{n})=a_{f^{-1}(0)}\dots a_{f^{-1}(k)}$. Note that
$\lim_{n\to\text{$\infty$}}k(n)=\text{$\infty$}$, and thus
$\lim_{n\to\text{$\infty$}}|\phi(a_{0}\dots a_{n})|=\text{$\infty$}$, this
shows that $F$ is defined on all inputs. By construction we have that
$F(x)=\cap_{n\in\mathbb{N}}[\phi(x_{0}\dots x_{n})]$. Thus we proved that $F$
is computable.

Replacing $f$ by $f^{-1}$ in the argument, we see that the inverse of $F$,
$x\to x\circ f^{-1}$ is also computable. ∎

######  Definition 5.4.

Let $X\subset A^{\mathbb{N}}$ and $Y\subset B^{\mathbb{N}}$. The sets $X,Y$
are computably homeomorphic if there exists partial computable functions
$\Phi:A^{\mathbb{N}}\to B^{\mathbb{N}}$, $\Psi:B^{\mathbb{N}}\to
A^{\mathbb{N}}$, such that $X$ (resp $Y$) is contained in the domain of $\Phi$
(resp $\Psi$), and such that $\Psi(\Phi(x))=x\hskip 10.00002pt\forall x\in X$.

######  Example 5.5.

The sets $A^{\mathbb{N}}$ and $B^{\mathbb{N}}$ are computably homeomorphic for
any $A$ and $B$ finite. Indeed, the usual homeomorphism between these sets is
a computable function (for example, the one described in [16, Theorem 2-97]).
A particularly simple case is when $A=\\{0,1,2,3\\}$ and $B=\\{0,1\\}$. A
computable homeomorphism between $A^{\mathbb{N}}$ and $B^{\mathbb{N}}$ is
given by the letter-to-word substitutions

$0\mapsto 00\hskip 10.00002pt1\mapsto 01\hskip 10.00002pt2\mapsto 10\hskip
10.00002pt3\mapsto 11.$

######  Definition 5.6.

A subset $X\subset A^{\mathbb{N}}$ is effectively closed, denoted
$\Pi_{1}^{0}$, if some of the following equivalent conditions holds.

  1. (1)

The complement of $X$ can be written as $\bigcup_{w\in L}[w]$ for a computably
enumerable set $L\subset A^{*}$.

  2. (2)

We can semi decide if a word $w\in A^{*}$ satisfies $[w]\cap X=\emptyset$.

  3. (3)

We can semi decide if a pattern $p:K\subset\mathbb{N}\to A$ satisfies $[p]\cap
X=\emptyset$.

######  Example 5.7.

Let $T\subset A^{*}$ be a tree, which means a set of words closed under
prefix, and denote by $[T]$ the set of infinite paths of $T$, $\\{x\in
A^{\mathbb{N}}|\ \forall n\in\mathbb{N},x_{0}\dots x_{n}\in T\\}.$ If the tree
$T$ is computable (as subset of $A^{*}$), then its set of infinite paths
$[T]=A^{\mathbb{N}}-\cup_{w\not\in T}[w]$ is an effectively closed set.
Conversely, it can be shown that every effectively closed set is the set of
paths of a computable tree.

######  Definition 5.8 (Medvedev degrees).

Let $X\subset A^{\mathbb{N}},$ $Y\subset B^{\mathbb{N}}$. We say that $Y$ is
Medvedev reducible to $X$, written

$Y\leq_{\mathfrak{M}}X,$

if there is a partial computable function $\Phi$ defined on all elements of
$X$, and such that $\Phi(X)\subset Y$. This is a preorder, and induces the
equivalence relation $\equiv_{\mathfrak{M}}$ given by

$X\equiv_{\mathfrak{M}}Y\iff X\leq_{\mathfrak{M}}Y\text{ and
}Y\leq_{\mathfrak{M}}X.$

Equivalence classes of $\equiv_{\mathfrak{M}}$ are called Medvedev degrees.
Medvedev degrees form a lattice with interesting properties, a survey on the
subject is [14]. If we regard a set $X\subset A^{\mathbb{N}}$ as the set of
solutions to a problem, then the Medvedev degree of $X$,
$\deg_{\mathfrak{M}}(X)$, measures how hard is it to construct a solution,
where hard means hard to compute. From the definition, one can see that:

  1. (1)

If $X$ has a computable point $x_{c}$, then it is minimal for
$\leq_{\mathfrak{M}}$. This is proved by noting that the constant function
$\Phi:A^{\mathbb{N}}\to X$, $x\mapsto x_{c}$ is computable. The Medvedev
degree of this set is denoted $0_{\mathfrak{M}}$.

  2. (2)

The empty set $\emptyset$ is maximal for $\leq_{\mathfrak{M}}$. This reflects
that for $\leq_{\mathfrak{M}}$, the hardest problem is one with no solutions.

  3. (3)

If $X$ and $Y$ are computably homeomorphic, then $X\equiv_{\mathfrak{M}}Y$.

As $2^{\mathbb{N}}$ and $A^{\mathbb{N}}$ are computably homeomorphic for any
finite set $A$, it is enough to consider Medvedev degrees of subsets of
$2^{\mathbb{N}}$.

An important sublattice of the lattice of Medvedev degrees is that of Medvedev
degrees of effectively closed subsets. This is a countable class, its elements
admit a finite description, and it exhibits many interesting properties.
Natural and geometrical examples of effectively closed sets are subshifts of
finite type, and more generally effective subshifts. As mentioned in the
introduction, it is known that all $\Pi_{1}^{0}$ Medvedev degrees can be
attained by two dimensional subshifts of finite type [28], and one dimensional
effective subshifts [22].

###  5.2. Computability on $A^{G}$

In this subsection we define the Medvedev degree of a subset of $A^{G}$ using
representations. For the definition and its stability properties it will be
essential to assume that $G$ is a finitely generated infinite group with
decidable word problem.

Representations are the uncountable version of numberings, as defined in 2.4.
We recall the following definitions from [4, Chapter 9]. A represented space
is a pair $(X,\delta)$ where $X$ is a set and $\delta$ is a representation of
$X$, that is, a partial surjection $\delta:\text{dom}(\delta)\subset
A^{\mathbb{N}}\to X$. A representation allows us to transfer the computability
notions from $A^{\mathbb{N}}$ to $X$. For example, in a represented space
$(X,\delta)$, a subset $Y\subset X$ is effectively closed when
$\delta^{-1}(Y)\subset A^{\mathbb{N}}$ is an effectively closed set. Moreover,
if $(X^{\prime},\delta^{\prime}:A^{\prime}{}^{\mathbb{N}}\to X^{\prime})$ is
another represented space, a function $F:X\to X^{\prime}$ is computable when
$\delta^{\prime}{}^{-1}\circ F\circ\delta:A^{\mathbb{N}}\to
A^{\prime}{}^{\mathbb{N}}$ is a computable function. Finally, two
representations of $X$, $\delta:A^{\mathbb{N}}\to X$ and
$\delta^{\prime}:B^{\mathbb{N}}\to X$, are called equivalent if the identity
function $X\to X$ is computable between $(X,\delta)$ and
$(X,\delta^{\prime})$. In this case, both representations induce the same
computability notions on $X$.

We will consider the following representation, which is also a total function
and a homeomorphism.

######  Definition 5.9.

Let $G$ be a finitely generated infinite group with decidable word problem,
and $\nu$ a computable numbering of $G$. We define the representation $\delta$
by

$\displaystyle\delta:A^{\mathbb{N}}$ $\displaystyle\to A^{G}$ $\displaystyle
x$ $\displaystyle\mapsto x\circ\nu^{-1}.$

Recall from 2 that a group as in the statement admits a computable numbering.
The next proposition shows that the computability notions that we obtain on
$A^{G}$ do not depend on the choice of $\nu$.

######  Proposition 5.10.

In the previous definition, any two computable numberings induce equivalent
representations.

###### Proof.

Let $F:A^{G}\to A^{G}$ be the identity function. Then
$\delta^{\prime}{}^{-1}\circ F\circ\delta:A^{\mathbb{N}}\to A^{\mathbb{N}}$ is
given by $x\mapsto x\circ\nu^{-1}\circ\nu^{\prime}$. This is a computable
function by 5.3 and the fact that
$\nu^{-1}\circ\nu^{\prime}:\mathbb{N}\to\mathbb{N}$ is a computable bijection
of $\mathbb{N}$. ∎

Indeed, computability notions on $A^{G}$ are also preserved by group
isomorphisms.

######  Proposition 5.11.

Consider a group $G^{\prime}$ and a representation for $A^{G^{\prime}}$ as in
5.9. If $f:G\to G^{\prime}$ is a group isomorphism, then the associated
function $F:A^{G^{\prime}}\to A^{G}$, $x\mapsto x\circ f$ is computable.

The proof is omited, as it is identical to the previous one by applying 2.6.
This means that the computability notions being considered on $A^{G}$ are
preserved if we rename group elements (for example, by taking different
presentations of the same group).

We can now define the Medvedev degree of a subset of $A^{G}$.

######  Definition 5.12.

For a subset $X\subset A^{G}$, we define
$\deg_{\mathfrak{M}}X=\deg_{\mathfrak{M}}(\delta^{-1}X)$.

This definition does not depend on $\delta$, as long as $\delta$ comes from a
computable numbering of $G$. Let us now review some basic facts about
effectively closed sets on $A^{G}$. With this representation we recover the
familiar description of effectively closed subsets in terms of cylinders.

######  Proposition 5.13.

A subset $X\subset A^{G}$ is effectively closed if and only if we can semi
decide if a pattern $p:K\subset G\to A$ satisfies $[p]\cap X=\emptyset$.

###### Proof.

Given a pattern $p:K\subset G\to A$, we just have to compute a pattern
$p^{\prime}:K\subset\mathbb{N}\to A$ such that $p=p^{\prime}\circ\nu$. Then
$[p]\cap X=\emptyset$ if and only if
$[p^{\prime}]\cap\delta^{-1}(X)=\emptyset$, which can be semi decided as
$\delta^{-1}(X)$ is effectively closed. ∎

In [1, Lemma 2.3] it is shown that for recursively presented group and in
particular one with decidable word problem, an effective subshift has a
maximal -for inclusion- computably enumerable set of pattern codings
associated to forbidden patterns. In other words, the set of all patterns $p$
with $[p]\cap X=\emptyset$ is computably enumerable. Joining this with 5.13,
we obtain:

######  Proposition 5.14.

A subshift $X\subset A^{G}$ is effective if and only if it is an effectively
closed subset of $A^{G}$.

###  5.3. The subshift of translation-like actions, and the main construction

In this subsection we describe how to code translation-like actions as a
subshift, and then we use this to prove 1.8. Let $G$ be an infinite group, $S$
a finite set of generators, and $J\in\mathbb{N}$ (we will not assume yet that
$G$ has decidable word problem).

######  Definition 5.15.

Let $T_{J}(\mathbb{Z},G)$ be the set of all translation-like actions
$\ast:\mathbb{Z}\times G\to G$ such that $\\{d_{S}(g,g\ast 1)|\ g\in G\\}$ is
bounded by $J$.

Figure 1. Representation of some orbits of a translation-like action in
$T_{2}(\mathbb{Z},\mathbb{Z}^{2})$, or alternatively, a finite piece of
configuration in $X_{2}(\mathbb{Z},\mathbb{Z}^{2})$. In this case,
$\mathbb{Z}^{2}$ is endowed with the set of four generators $S=\\{(\pm
1,0),(0,\pm 1)\\}$.

Recall that $B(1_{G},J)$ is the ball $\\{g\in G\mid d_{S}(g,1_{G})\leq J\\}$.
We will consider the finite alphabet $B=B(1_{G},J)\times B(1_{G},J)$.
Informally, a configuration $x\in B^{G}$ can be thought of as having an
incoming and outogoing arrow at each $g\in G$. If $x(g)=(l,r)$, we can think
that $g$ has an outgoing arrow to $gr$, and an incoming arrow from $gl$, see
1.

Any translation-like action $\ast\in T_{J}(\mathbb{Z},G)$ defines the
configuration $x_{\ast}\in B^{G}$ by the condition

$\forall g\in G\hskip 10.00002ptx_{\ast}(g)=(l,r)\iff g\ast-1=gl\text{ and
}g\ast 1=gr.$

######  Definition 5.16.

Let $X_{J}(\mathbb{Z},G)$ be the set of all $x_{*}$, where $*$ ranges over
$T_{J}(\mathbb{Z},G)$.

We will prove that $X_{J}(\mathbb{Z},G)$ is a subshift, but we first introduce
some notation. $L$ and $R$ stand for the projections $B\to B(1_{G},J)$ to the
left and right coordinate, respectively. Now an arbitrary element $x\in B^{G}$
defines two semigroup actions as follows. For $m\in\mathbb{Z}_{\geq 0}$ and
$g\in G$, define the element $g\ast_{x}m$, by declaring $g\ast_{x}0=g$,
$g\ast_{x}1=g\cdot R(x(g))$, and $g\ast_{x}(m+1)=(g\ast_{x}m)\ast_{x}1.$ For
$m\in\mathbb{Z}_{\leq 0}$, we define $g\ast_{x}m$ by $g\ast_{x}-1=g\cdot
L(x(g))$ and $g\ast_{x}(m-1)=(g\ast_{x}m)\ast_{x}-1.$ If $p:K\subset G\to B$
is a pattern, we give $g\ast_{p}m$ the same meaning as before, as long as it
is defined.

It is easily seen that for arbitrary $x\in B^{G}$, we have

$(g\ast_{x}n)\ast_{x}m=g\ast_{x}(n+m)$

for both $n,m$ positive or both negative integers. It may fail for
$n,m\in\mathbb{Z}$, but this is easily fixed with local rules.

######  Proposition 5.17.

The set $X_{J}(\mathbb{Z},G)$ is a subshift. If we assume that $G$ has
decidable word problem, it is an effective subshift.

###### Proof.

We claim that $X_{J}(\mathbb{Z},G)=X_{\mathcal{J}}$, where $\mathcal{J}$ is
the set of all patterns $p:B(1_{G},n)\to B$, $n\in\mathbb{N}$, such that some
of the following fails

  1. (1)

$(1_{G}\ast_{p}1)\ast_{p}-1=1_{G}$, $(1_{G}\ast_{p}-1)\ast_{p}1=1_{G}$

  2. (2)

For any nonzero $m\in\mathbb{Z}$, $1_{G}\ast_{p}m\neq 1_{G}$.

If $\ast\in T_{J}(\mathbb{Z},G)$, it is clear that no pattern of $\mathcal{J}$
may appear on $x_{\ast}$, by the definition of action and translation-like
action. Thus $X_{J}(\mathbb{Z},G)\subset X_{\mathcal{J}}$. Now let $x\in
X_{\mathcal{J}}$. We claim that $\ast_{x}$ is a translation-like action. To
see that it is a group action, first note that for $g\in G$, $g\ast_{x}0=g$ by
definition. An easy induction on $\max\\{|n|,|m|\\}$ shows that
$(g\ast_{x}n)\ast_{x}m=g\ast_{x}(n+m)$ for any $n,m\in\mathbb{Z}$ and $g\in
G$. The group action $\ast_{x}$ is free because of the second condition, and
the boundedness condition comes from the alphabet chosen. Thus $\ast_{x}$ is a
translation-like action.

To show that $x$ lies in $X_{J}(\mathbb{Z},G)$, we have to check that it is of
the form $x_{\ast}$ for some translation-like action $\ast$, and it is clear
that $x=x_{(\ast_{x})}$. Thus $X_{J}(\mathbb{Z},G)$ is a subshift.

Now let us assume that $G$ has decidable word problem. Note that the
definition of $\ast_{p}$ above is recursive. Given an arbitrary pattern $p$,
and $m\in\mathbb{Z}$, we can decide if the group element $1_{G}\ast_{p}m$ is
defined, and compute it. This shows that the conditions (1) and (2) are
decidable over patterns, and thus $\mathcal{J}$ is a decidable set. This shows
that $X_{\mathcal{J}}$ is an effective subshift. ∎

We now describe a subshift on $G$ whose elements describe, simultaneously,
translation-like actions, and configurations from a subshift over
$\mathbb{Z}$. Let $A$ be an arbitrary finite alphabet, and let $B$ be the
alphabet already defined and which depends on the natural number $J$. Note
that elements of $(A\times B)^{G}$ can be conveniently written as $(y,x)$ for
$y\in A^{G}$ and $x\in B^{G}$; we will write $\pi_{A}:A\times B\to A$ and
$\pi_{B}:A\times B\to B$ for the projections to the first and second
coordinate, respectively.

######  Definition 5.18.

For a one dimensional subshift $Y\subset A^{\mathbb{Z}}$, let
$Y[X_{J}(\mathbb{Z},G)]$ be the set of all configurations $(y,x)\in(A\times
B)^{G}$ such that

  1. (1)

$x\in X_{J}(\mathbb{Z},G)$, and

  2. (2)

for any $g\in G$, the $A^{\mathbb{Z}}$ element defined by
$y(m)=\pi_{A}(y(g\ast_{x}m)$ lies in $Y$.

######  Proposition 5.19.

The set $Y[X_{J}(\mathbb{Z},G)]$ is a subshift. If we assume that $G$ has
decidable word problem and $Y$ is an effective subshift, then
$Y[X_{J}(\mathbb{Z},G)]$ is an effective subshift.

###### Proof.

Let $\mathcal{F}$ be the set of all patterns in $\mathbb{Z}$ that do not occur
in $X$, so that $X=X_{\mathcal{F}}$, and let $\mathcal{J}$ as before, so that
$X_{\mathcal{J}}=X_{J}(\mathbb{Z},G)$. Define $\mathcal{H}$ to be the set of
all patterns $p:B(1_{G},n)\to A\times B$, $n\in\mathbb{N}$, such that one of
the following occurs. Denote $q=\pi_{B}\circ p:B(1_{G},n)\to B$.

  1. (1)

The pattern $q$ lies in $\mathcal{J}$.

  2. (2)

For some $m\in\mathbb{N}$ the elements $g\ast_{q}1,\dots,g\ast_{q}m$ are all
defined, lie in $\text{$B(1_{G},n)$},$ and the pattern
$r:\\{1,\dots,m\\}\subset\mathbb{Z}\to A,r(k)=\pi_{A}(g\underset{q}{\ast}k)$
lies in $\mathcal{F}$.

As before, it is a rutinary verification that $x\in Y[X_{J}(\mathbb{Z},G)]$ if
and only if $x\in X_{\mathcal{H}}$ .

Now assume that $G$ has decidable word problem. Let us argue that
$\mathcal{H}$ is a computably enumerable set, provided that the same holds for
$\mathcal{F}$. Given a pattern $p$, we can compute the pattern $q$. The first
condition is decidable, as we already proved that $\mathcal{J}$ is a decidable
set. For the second, note that given $p$ and $m\in\mathbb{N}$, we can also
compute the pattern $r$. As $\mathcal{F}$ is a computable enumerable set, we
can semi decide that $r$ is in $\mathcal{F}$. This shows that $\mathcal{H}$ is
a computably enumerable set, and finishes the proof. ∎

Figure 2. A finite piece of configuration in
$Y[X_{2}(\mathbb{Z},\mathbb{Z}^{2})]$, where $A$ is the alphabet containing
the symbols of a circle, square, and rhombus, and $Y\subset A^{\mathbb{Z}}$ is
the orbit closure of the periodic sequence that repeats circle, square, and a
rhombus in that order.

The previous construction still makes sense if we replace $\mathbb{Z}$ by
another finitely generated group $H$. In this case, the alphabet $B$ depends
on the generators of $H$. This is described in detail in [3, 18]. We will
write $X_{J}(H,G)$ and $Y[X_{J}(\mathbb{Z},G)]$ with the same meaning as
before, but only for reference reasons. It is natural to ask what properties
are preserved by the map

$Y\subset A^{H}\mapsto Y[X_{J}(H,G)]\subset(A\times B)^{G}.$

The following is known.

  1. (1)

In [18], E. Jeandel proved that when $H$ is a finitely presented group, the
map above preserves the property of being a weakly aperiodic subshift, and of
being empty or nonempty. This shows the undecidability of the emptiness
problem for subshifts of finite type, and the existence of weakly aperiodic
subshifts on new groups.

  2. (2)

In [3], S. Barbieri proved that when $H$ and $G$ are amenable groups, the
topological entropy satisfies

$h(Y[X])=h(Y)+h(X).$

This construction is used to classify the entropy of subshifts of finite type
on some amenable groups.

In the present paper we use the previous construction because it preserves the
constructive complexity of a subshift. We already proved that it preserves the
property of being an effective subshift, which is folklore. In the following
result we use 1.7 to show that this construction also preserves the Medvedev
degree of a subshift $Y$ for $H=\mathbb{Z}$, and $J$ big enough. This shows
1.8, as the same classification for $H=\mathbb{Z}$ was proved by J. Miller in
[22].

######  Theorem 5.20.

Let $G$ be a finitely generated infinite group with decidable word problem,
and let $J\in\mathbb{N}$ such that $G$ admits a translation-like action by
$\mathbb{Z}$ with decidable orbit membership problem. Then for any $Y\in
A^{\mathbb{Z}}$,

$Y\equiv_{\mathfrak{M}}Y[X_{J}(\mathbb{Z},G)].$

###### Proof.

Recall that the inequality $Y\geq_{\mathfrak{M}}X$ holds if there exists a
computable function $\Phi$ with $\Phi(Y)\subset X$, and this means that we can
compute elements of $X$ using elements of $Y$ using a single algorithm. In
this case, $\Phi$ is a computable function between the represented spaces
$A^{\mathbb{Z}}$ and $(A\times B)^{G}$.

The obvious inequality is $Y[X_{J}(\mathbb{Z},G)]\geq_{\mathfrak{M}}Y$, that
is, we can compute an $Y$ element using a $Y[X_{J}(\mathbb{Z},G)]$ element.
Informally, on input $(y,x)$ we can just follow the arrows from $1_{G}$ and
read the $A$ component of the alphabet. This outputs an element of $Y$ by
definition.

Formally, we define the function $\Phi:Y[X_{J}(\mathbb{Z},G)]\to
Y,(y,x)\mapsto z$ by

$z(n)=y(\pi_{A}(1_{G}\ast n)),n\in\mathbb{Z}.$

It is clear from the expression above how to compute $z$ on input $(y,x)$, and
thus, $\Phi$ is computable.

For the remaining inequality, we need to compute a $Y[X_{J}(\mathbb{Z},G)]$
element using an element $z\in Y$. For this, let $\ast$ be a translation-like
action as in 1.7.

The intuitive idea is to define $(y,x)\in Y[X_{J}(\mathbb{Z},G)]$ by leting
$x=x_{\ast}$, which is a computabe point of $B^{G}$ as $\ast$ is a computable
function. Then we define $y$ by coloring each orbit of $\ast$ with the
sequence $z$. For this purpose, we use that $\ast$ has decidable orbit
membership problem to compute a sequence of representatives for each orbit,
and then we overlay $z$ on each one of these orbits starting from the chosen
representative.

Let $(g_{n})_{n\in\mathbb{N}}$ be a computable numbering of $G$. We compute a
sequence of representatives for orbits of $\ast$ as follows. Define the
computable sequence $(k_{i})_{i\in\mathbb{N}}$ by setting $k_{0}=0$, and
defining $k_{i+1}$ as the minimal natural number such that $g_{k_{i+1}}$ lies
in a different orbit by $\ast$ than any of $g_{k_{0}},\dots,g_{k_{i}}$. Note
that this can be decided because $\\{g_{k_{0}},\dots,g_{k_{i}}\\}$ is a finite
set and $\ast$ has decidable orbit membership problem. Thus the sequence
$(g_{k_{i}})_{i\in\mathbb{N}}$ is computable and contains exactly one element
in each orbit of $\ast$.

We now define a computable function $\Psi_{A}:A^{\mathbb{Z}}\to A^{G}$ as
follows. On input $z$ it outputs the element $y$ defined by

$y(g_{k_{i}}\ast n)=z(n),\hskip 10.00002pti\in\mathbb{N},\ n\in\mathbb{Z}.$

This defines $y(g)$ for all $g\in G$, as $(g_{k_{i}})_{i\in\mathbb{N}}$
contains exactly one element in each orbit of $\ast$.

To see that $\Psi_{A}$ is a computable function, note that given any $g\in G$
we can first compute $k_{i}$ such that $g$ lies in the same orbit as
$g_{k_{j}}$ (as the sequence $(k_{i})_{i\in\mathbb{N}}$ is computable), and
then use that the fact that the action $\ast$ is computable to find
$n\in\mathbb{N}$ satisfying $g=g_{k_{i}}\ast n$.

Now define $\Psi_{B}:A^{\mathbb{Z}}\to B^{G}$ as the constant function
$x_{\ast}$, which is computable as $x_{\ast}$ is a computable point.

The previous two steps show that the function $\Psi:A^{\mathbb{Z}}\to(A\times
B)^{G}$ defined by $z\mapsto\Psi(z)=(\Psi_{A}(z),\Psi_{B}(z))$ is computable.
It satisfies $\Psi(Y)\subset Y[X_{J}(\mathbb{Z},G)]$ by construction, and this
finishes the proof. ∎

## References

  * [1] Nathalie Aubrun, Sebastián Barbieri, and Mathieu Sablik.  A notion of effectiveness for subshifts on finitely generated groups.  Theoretical Computer Science, 661:35–55, 2017.
  * [2] Serikzhan Badaev and Sergey Goncharov.  The theory of numberings: Open problems.  In Computability theory and its applications. Current trends and open problems. Proceedings of a 1999 AMS-IMS-SIAM joint summer research conference, Boulder, CO, USA, June 13–17, 1999, pages 23–38. Providence, RI: American Mathematical Society (AMS), 2000.
  * [3] Sebastián Barbieri.  On the entropies of subshifts of finite type on countable amenable groups.  Groups, Geometry, and Dynamics, 15(2):607–638, 2021.
  * [4] Vasco Brattka and Peter Hertling, editors.  Handbook of computability and complexity in analysis.  Theory Appl. Comput. Cham: Springer, 2021.  ISSN: 2190-619X.
  * [5] Ian Chiswell.  A course in formal languages, automata and groups.  Universitext. Berlin: Springer, 2009.  ISSN: 0172-5939.
  * [6] Daniel E. Cohen.  Combinatorial group theory: a topological approach.  Number 14 in London Mathematical Society student texts. Cambridge University Press, Cambridge ; New York, 1989.
  * [7] David B. Cohen, Chaim Goodman-Strauss, and Yo’av Rieck.  Strongly aperiodic subshifts of finite type on hyperbolic groups.  Ergodic Theory and Dynamical Systems, pages 1–44, September 2021\.  Publisher: Cambridge University Press.
  * [8] Reinhard Diestel and Daniela Kühn.  Graph-theoretical versus topological ends of graphs.  Journal of Combinatorial Theory. Series B, 87(1):197–206, 2003\.
  * [9] M. J. Dunwoody.  Cutting up graphs.  Combinatorica, 2:15–23, 1982.
  * [10] Yu. L. Ershov, S. S. Goncharov, A. Nerode, J. B. Remmel, and V. W. Marek, editors.  Handbook of recursive mathematics. Vol. 1: Recursive model theory, volume 138 of Stud. Logic Found. Math. Amsterdam: Elsevier, 1998.
  * [11] Hans Freudenthal.  Über die Enden diskreter Räume und Gruppen.  Commentarii Mathematici Helvetici, 17:1–38, 1945.
  * [12] E. S. Golod and I. R. Shafarevich.  On the class field tower.  Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya, 28:261–272, 1964.
  * [13] Edward R. Griffor, editor.  Handbook of computability theory.  Number v. 140 in Studies in logic and the foundations of mathematics. Elsevier, Amsterdam ; New York, 1st ed edition, 1999.
  * [14] Peter G. Hinman.  A survey of Mučnik and Medvedev degrees.  The Bulletin of Symbolic Logic, 18(2):161–229, 2012.
  * [15] Michael Hochman and Tom Meyerovitch.  A characterization of the entropies of multidimensional shifts of finite type.  Annals of Mathematics, 171(3):2011–2038, May 2010.
  * [16] John G. Hocking and Gail S. Young.  Topology.  Addison-Wesley series in mathematics. Addison-Wesley, Reading, Mass., 1961.
  * [17] Heinz Hopf.  Enden offener Räume und unendliche diskontinuierliche Gruppen.  Commentarii Mathematici Helvetici, 16:81–100, 1944.
  * [18] Emmanuel Jeandel.  Translation-like Actions and Aperiodic Subshifts on Groups.  arXiv:1508.06419 [cs, math], August 2015.  arXiv: 1508.06419.
  * [19] Jerome J. Karaganis.  On the Cube of a Graph.  Canadian Mathematical Bulletin, 11(2):295–296, June 1968.  Publisher: Cambridge University Press.
  * [20] Roger C Lyndon and Paul E Schupp.  Combinatorial group theory.  2001\.  OCLC: 1164606566.
  * [21] Alfred B. Manaster and Joseph G. Rosenstein.  Effective matchmaking (recursion theoretic aspects of a theorem of Philip Hall).  Proceedings of the London Mathematical Society. Third Series, 25:615–654, 1972.
  * [22] Joseph S. Miller.  Two notes on subshifts.  Proceedings of the American Mathematical Society, 140(5):1617–1622, 2012.
  * [23] A. Yu. Ol’shanskij.  On the question of the existence of an invariant measure on a group.  Uspekhi Matematicheskikh Nauk [N. S.], 35(4(214)):199–200, 1980\.
  * [24] M. O. Rabin.  Computable algebra, general theory and theory of computable fields.  Transactions of the American Mathematical Society, 95:341–360, 1960\.
  * [25] J. B. Remmel.  Graph colorings and recursively bounded \\(\Pi ^ 0_ 1\\)-classes.  Annals of Pure and Applied Logic, 32:185–194, 1986.
  * [26] Hartley Rogers.  Theory of recursive functions and effective computability.  MIT Press, Cambridge, Mass, 1st mit press pbk. ed edition, 1987.
  * [27] Brandon Seward.  Burnside’s problem, spanning trees and tilings.  Geometry & Topology, 18(1):179–210, 2014.
  * [28] Stephen G. Simpson.  Medvedev degrees of two-dimensional subshifts of finite type.  Ergodic Theory and Dynamical Systems, 34(2):679–688, 2014.
  * [29] Kevin Whyte.  Amenability, bilipschitz equivalence, and the von Neumann conjecture.  Duke Mathematical Journal, 99(1), July 1999.