Embeddings into left-orderable simple groups

Arman Darbinyan Texas A&M, USA [email protected] and Markus Steenbock IRMAR
Univ Rennes et CNRS
35000 Rennes
France [email protected]

Abstract.

We prove that every countable left-ordered group embeds into a finitely generated left-ordered simple group. Moreover, if the first group has a computable left-order, then the simple group also has a computable left-order. We also obtain a Boone-Higman-Thompson type theorem for left-orderable groups with recursively enumerable positive cones. These embeddings are Frattini embeddings, and isometric whenever the initial group is finitely generated.

Finally, we reprove Thompson’s theorem on word problem preserving embeddings into finitely generated simple groups and observe that the embedding is isometric.

Key words and phrases:

embedding theorems, left-ordered groups, simple groups, word problem, computability on groups

2010 Mathematics Subject Classification:

20F60, 20E32, 20F10

1. Introduction

A group is simple if it has no proper non-trivial normal subgroups. Infinite finitely generated simple groups were discovered in [Hig51]. In fact, every countable group embeds into a finitely generated simple group [Hal74, Gor74], see also [Sch76, Tho80].

1.1. Left-order preserving embeddings into simple groups

A group is left-ordered if it has a linear order that is invariant under multiplications from the left.

By [KKL19, Theorem 4.5], every finitely generated left-ordered groups embeds into a finitely generated left-ordered group whose derived subgroup is simple.

Infinite finitely generated simple and left-ordered groups were discovered by Hyde and Lodha in [HL19], see also [MBT18, HLNR19]. We extend the construction of such groups [HL19, MBT18] as follows.

Theorem 1.

Every countable left-ordered group $G$ embeds into a finitely generated left-ordered simple group $H$ . Moreover, the order on $H$ continues the order on $G$ .

We also study additional geometric and computability properties of such embeddings, see Remark 1.1 and Theorem 2.

A subgroup $G$ of $H$ is called Frattini embedded if any two elements of $G$ that are conjugate in $H$ are also conjugate in $G$ . Also, if there exist finite generating sets $X$ and $Y$ of $G$ and $H$ , respectively, such that the word metric of $G$ with with respect to $X$ coincides with the word metric of $G$ with respect to $Y$ , then it is said that $G$ is isometrically embedded in $H$ .

Remark 1.1.

The embedding of Theorem 1 can be chosen to be a Frattini embedding. If $G$ is finitely generated, the embedding is also isometric.

A systematic study of computability aspects of orders on groups was initiated in [DK86], see also [Dow98]. A left-order is computable if it is decidable whether a given element is positive, negative or equal to the identity. In particular, a finitely generated computably left-ordered group has a decidable word problem.

The following theorem is the computable version of Theorem 1.

Theorem 2.

Every countable computably left-ordered group $G$ embeds into a finitely generated computably left-ordered simple group $H$ . Moreover, the order on $H$ continues the order on $G$ .

In addition, the embedding is a Frattini embedding, and if $G$ is finitely generated, then it is isometric.

1.2. Boone-Higman and Thompson’s theorem revisited

A landmark result on computability in groups is the Boone-Higman theorem. It states that a finitely generated group has decidable word problem if and only if it embeds into a simple subgroup of a finitely presented group. Thompson strengthened Boone-Higman’s theorem by showing that the simple group can be chosen to be finitely generated [Tho80]. The next theorem is a version of Thompson’s theorem that, in addition, preserves the geometry of the group.

Theorem 3 (cf. Theorem A.1).

Every countable group $G$ embeds into a finitely generated simple group $H$ such that if $G$ has decidable word problem, then so does $H$ .

In addition, the embedding is a Frattini embedding. If $G$ is finitely generated, then the embedding is isometric.

Remark 1.2.

Belk and Zaremsky [BZ20, Theorem C] recently proved that every finitely generated group isometrically embeds into a finitely generated simple group, but they did not study the Frattini property or computability properties of their embedding. Their result and Theorem 3 strengthen a theorem of Bridson, who proved that every finitely generated group quasi-isometrically embeds into a finitely generated group without any non-trivial finite quotient [Bri98].

Remark 1.3.

If the group $G$ in Theorem 3 is not finitely generated, instead of saying $G$ has decidable word problem, it is more common to say that $G$ is a computable group (see Definition 2.2 below).

Bludov and Glass obtained a left-orderable version of the Boone-Higman theorem by showing that a left-orderable group has decidable word problem if and only if it embeds into a simple subgroup of a finitely presented left-orderable group [BG09, Theorem E]. In this context, it is natural to ask whether the simple group can be made finitely generated, cf. [Gla81, p. 251, Problem 4].

The next theorem answers this question in the positive given that the set of positive elements is recursively enumerable. Namely, the following theorem holds.

Theorem 4.

Let $G$ be a left-orderable finitely generated group that has a recursively enumerable positive cone with respect to some left-order. Then $G$ has decidable word problem if and only if $G$ embeds into a finitely generated simple subgroup of a finitely presented left-orderable group.

Remark 1.4.

The existence of left-orderable groups with decidable word problem that do not embed in a group with computable left order was shown in [Dar19].

Also, the existence of finitely generated left-orderable groups with decidable word problem but without recursively enumerable positive cone is first shown in [Dar19]. Earlier, the analogous result for countable but not finitely generated groups was shown in [HT18].

The question whether Theorem 4 holds without the assumption that $G$ has a left-order with recursively enumerable positive cone remains open. Also it is open whether a finitely generated left-orderable simple group with decidable word problem but without recursively enumerable positive cone exists.

1.3. Sketch of the embedding constructions

We sketch the proof of Theorems 1 and 2. We start with a countable computably left-ordered group $G$ .

Step 1 (Embedding into a finitely generated group).

By a classical wreath product construction [Neu60] every countable left-ordered group embeds into a $2$ –generated left-ordered group. A version of this embedding construction with additional computability properties was established in [Dar15]. We use the construction from [Dar15] (see Theorem 5.15) to embed the initial left-orderable countable group $G$ into a two-generated left-orderable group that also preserves the computability properties of the left-order on $G$ .

Step 2 (Embedding into a perfect group).

A group is perfect if it coincides with its first derived subgroup. By Step 1 we assume that $G$ is finitely generated. We let $T(\varphi)$ be a finitely generated left-ordered simple group of [MBT18]. We note that $T(\varphi)$ is computably left-ordered and $G$ embeds into a finitely-generated left-orderable perfect subgroup $G_{1}$ of $G\wr_{\mathbb{R}}T(\varphi)$ that preserves the computability property of the left-order on $G$ , see Theorem 5.1. Our construction might be considered as a modification of a similar embedding result from [Tho80].

Step 3 (Embedding into a simple group of piecewise homeomorphisms of flows).

Finally, let $G_{1}$ be a finitely generated (computably) left-ordered perfect group in which $G$ embeds. We embed $G_{1}$ into a finitely generated (computably) left-ordered simple group. To this end, we extend the construction of [MBT18]. In [MBT18], Matte-Bon and Triestino construct a finitely generated left-orderable simple group $T(\varphi)$ of piecewise linear homeomorphisms of flows of the suspension of a minimal subshift $\varphi$ , see Subsection 3.2.

The main observation is that every group $H$ of piecewise homeomorphisms of an interval with countably many breakpoints (see Definition 3.8) embeds into a subgroup $T(H,\varphi)$ of piecewise homeomorphisms of flows of the suspension, see Definition 3.13. We then study the subgroup $T(H,\varphi)$ . In particular, it is finitely generated if $H$ is so. Just as in [MBT18], a standard commutator argument implies that it is simple given that $H$ is perfect, and if $H$ preserves the orientation of the interval, then it is also left-orderable.

Finally, we use the dynamical realisation of left-orderability: every left-ordered group embeds into the group of orientation preserving homeomorphisms of an interval. We use this embedding to conclude that $G_{1}$ , and hence also $G$ , embeds into the finitely generated left-ordered simple group $T(G_{1},\varphi)$ . To analyze the required computability aspects as well as to show that the embeddings are isometric and Frattini, we use a modified version of the dynamical realization of left-orderability, see Proposition 6.7.

If $G$ has decidable word problem, it embeds into a group of computable piecewise homeomorphisms of an interval [Tho80, §3]. If we use this embedding in Step 3 of the above construction, then we obtain the aforementioned result of [Tho80], Theorem 3.

1.4. Plan of the paper

In Section 2, we review computable groups and computably left-ordered groups. In particular, we explain the computability of the standard dynamical realization of left-orderabitity.

After that, we come to the main parts of our paper. In Section 3, we discuss Step 3, that is, we extend Matte-Bon and Triestino’s construction of left-orderable finitely generated simple groups in order to embed perfect groups into finitely generated simple groups. Step 2, our version of Thompson’s splinter group construction, is discussed in Section 5. Step 1 is reviewed in Section 5.4.

Finally, we prove Theorems 1, 2 and 4. To analyze the computability aspects required by Theorem 2 as well as to obtain the isometry and Frattini properties of the embeddings, we introduce a stronger version of the standard dynamical realization of left-orderability that we call modified dynamical realization(see Section 6). In Section 7, we prove Theorem 3 using the groups of piecewise homeomorphisms of flows discussed in Section 3.

Acknowledgements. We thank Y. Lodha, M. Triestino and M. Zaremsky for their interest and useful comments on a previous version of this work. The first named author thanks Université Rennes-I for hospitality and financial support and was supported by ERC-grant GroIsRan no.725773 of A. Erschler. The second named author was supported by ERC-grant GroIsRan no.725773 of A. Erschler and by Austrian Science Fund (FWF) project J 4270-N35.

2. Computability on groups

We collect some facts from computability theory on groups, cf. [FS56, Rab60, Mal61, DK86].

A function $f:\mathbb{N}\to\mathbb{N}$ is computable if there is a Turing machine such that it outputs the value of $f$ on the input. A subset of $\mathbb{N}$ is recursively enumerable if there is a computable map (i.e. enumeration) from $\mathbb{N}$ onto that set. Moreover, it is recursive if, in addition, its complement is recursively enumerable as well.

Similarly, a function $f:\mathbb{Q}\to\mathbb{Q}$ is computable if there is a Turing machine that, for every input $(m,n)\in\mathbb{N}\times\mathbb{N}$ , outputs $(p,q)\in\mathbb{N}\times\mathbb{N}$ such that $f\left(\frac{m}{n}\right)=\frac{p}{q}$ .

Moreover, if $J$ is an interval in $\mathbb{R}$ , then we call a function $f:J\to\mathbb{R}$ computable if its restriction to the rational numbers in $J$ maps to $\mathbb{Q}$ and this restriction is computable.

2.1. Group presentations and the word problem

Let $S$ be a finite set. We denote by $(S\cup S^{-1})^{*}$ the set of all finite words over the alphabet $S\cup S^{-1}$ .

Definition 2.1 (word problem).

Let $G=\langle S\rangle$ be a finitely generated group. The word problem is decidable if the set $\operatorname{WP}(S):=\{w\in(S\cup S^{-1})^{*}\mid w=_{G}1\}$ is recursive.

The decidability of the word problem does not depend on the choice of the finite generating set.

2.2. Computable groups

For a countable group $G=\{g_{1},g_{2},\ldots\}$ , let $\mathfrak{m}:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ be the function such that

\mathfrak{m}(i,j)=k

g_{i}g_{j}=g_{k}

Definition 2.2.

A countable group $G$ is computable if there exists an enumeration of its elements $G=\{g_{1},g_{2},\ldots\}$ such that the corresponding $\mathfrak{m}:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ is computable.

Remark 2.3.

A finitely generated group is computable if and only if it has decidable word problem.

2.3. Computably left-ordered groups

An order $\preceq$ on $\mathbb{N}\times\mathbb{N}$ is computable if there is a Turing machine that takes a pair $(i,j)\in\mathbb{N}\times\mathbb{N}$ as input and decides whether or not $i\preceq j$ .

For a countable linearly ordered enumerated set $S=\{s_{1},s_{2},\ldots\}$ , let $\preceq$ on $\mathbb{N}\times\mathbb{N}$ be the relation such that

i\prec j

s_{i}

is smaller than

s_{j}

and

i=j

s_{i}

is equal to

s_{j}

A countable set $S$ is computably orderable with respect to the enumeration $S=\{s_{1},s_{2},\ldots\}$ if there is a linear order on $S$ such that the corresponding to it order relation $\preceq$ on $\mathbb{N}\times\mathbb{N}$ is computable.

Definition 2.4.

A countable group $G$ is computably left-orderable with respect to the enumeration $G=\{g_{1},g_{2},\ldots\}$ if there is a left-order $\preceq$ on $G$ such that the corresponding order relation $\preceq$ on $\mathbb{N}\times\mathbb{N}$ is computable. In this case $\preceq$ is called computable left-order on $G$ with respect to the enumeration $G=\{g_{1},g_{2},\ldots\}$ .

Remark 2.5.

In case $G=\langle S\rangle$ , $|S|<\infty$ , $G$ is computably left-orderable with respect to some enumeration if and only if there is a left-order $\preceq$ on $G$ such that the set $\{w\in(S\cup S^{-1})^{*}\mid 1\preceq w\}\subseteq(S\cup S^{-1})^{*}$ is a recursive set. In this case $\preceq$ is called computable left-order on $G$ , and its computability property does not depend on the choice of the finite generating set, see [Dar19] for details.

Remark 2.6.

Every computably left-orderable group is computable. In particular, every finitely generated computably left-ordered group has decidable word problem.

By [HT18] there is a left-orderable computable group without any computable left-order. In fact, there is a finitely generated orderable computable group without any computable order [Dar19].

Example 2.7.

The natural order on the group of rational numbers is computable.

Example 2.8 (Thompson’s group $F$ ).

A dyadic point in $\mathbb{R}$ is one of the form $\frac{n}{2^{m}}$ , for some $n\,,m\in\mathbb{Z}$ . An interval is dyadic if its endpoints are dyadic.

Let $J$ be a closed dyadic interval in $\mathbb{R}$ . We denote by $\mathbb{Q}_{J}$ the set of the rational points on $J$ . We denote by $F_{J}$ the group of piecewise linear homeomorphisms of $J$ that are differentiable except at finitely many dyadic points and such that the respective derivatives, where they exist, are powers of $2$ .

The group $F_{J}$ is isomorphic to Thompson’s group $F$ , see e.g. [CFP96, §1]. Therefore, it is $2$ –generated and left-orderable, see e.g. [CFP96, Corollary 2.6, Theorem 4.11]. Moreover, the word problem in $F$ is decidable, cf. [Tho80].

We define the left-order on $F_{J}$ in the following way, cf. [CFP96, Theorem 4.11]: let $\mathbb{Q}_{J}=\{q_{1},q_{2},\ldots\}$ be a fixed recursive enumeration. Let $f,g\in F_{J}$ be distinct and let $i_{0}$ be the minimal index such that $f(q_{i_{0}})\not=g(q_{i_{0}})$ . Then $f<g$ if $f(q_{i_{0}})<g(q_{i_{0}})$ .

In fact, this order is computable: indeed, let $f,g\in F_{J}$ be given as words in a finite generating set. As the word problem in $F_{J}$ is decidable, the case of $f=g$ can be computably verified. We note that the elements of $F_{J}$ are computable functions. In addition, an element of $F_{J}$ is uniquely determined by its restriction to the rationals. Thus, if $f\not=g$ , the minimal index $i_{0}$ such that $f(i_{0})\not=g(i_{0})$ exists and can be computably determined. Therefore, the order is computable.

2.4. Positive cones

If $G$ is left-ordered, then the positive cone is the set of all positive elements of $G$ . We note that the positive cone is a semigroup. In fact, if $G$ admits a linear order such that the positive elements generate a semigroup in $G$ , then the linear order is a left-order on $G$ , see [DNR14, CR16].

Lemma 2.9.

Let $G=\{g_{1},g_{2},\ldots\}$ be a finitely generated group with a fixed enumeration, and ‘ $\prec$ ’ be a left-order on $G$ . Then ‘ $\prec$ ’ is computable if and only if its positive cone is recursively enumerable and the word problem in $G$ is decidable.

Proof.

If the order is computable, then the word problem is decidable, see Remark 2.6. In addition, there is a partial algorithm to confirm that a positive element, given as a word in the generators of $G$ , is positive. This implies that the positive cone is recursively enumerable.

On the other hand, if the positive cone is recursively enumerable and the word problem decidable, let $w$ be a word in the generators of $G$ . We first computably determine whether or not $w=1$ . If $w=1$ , we stop. Otherwise either $w$ or $w^{-1}$ is in the positive cone of $G$ . As the positive cone is recursively enumerable, there is a partial algorithm to confirm that a positive element is in the positive cone. We simultaneously run this algorithm for $w$ and $w^{-1}$ . As one of these elements is positive, it stops for $w$ or $w^{-1}$ . We thus know whether $w$ is positive or negative. This completes the proof. ∎

2.5. Dense orders

A linear order $\preceq$ on a set $S$ is dense if for any $g\prec h\in S$ , there exists $g^{\prime}\in S$ such that $g\prec g^{\prime}\prec h$ .

Recall that by $\mathbb{Q}_{J}$ the set of the rational points on an interval $J\subset\mathbb{R}$ . We fix a recursive enumeration $\mathbb{Q}_{J}=\{q_{0},q_{1},\ldots\}$ such that the natural order on $\mathbb{Q}_{J}$ is computable with respect to this enumeration.

Lemma 2.10 (cf. Theorem 2.22 of [CR16]).

Let $J\subset\mathbb{R}$ be an interval. Let $S=\{s_{0},s_{1},\ldots\}$ be a countable ordered set. If the order on $S$ is dense and does not have maximal and minimal elements, then there is an order preserving bijection $\Phi:S\to\mathbb{Q}_{J}$ .

If, in addition, the order on $S$ is computable, then the map $i\mapsto\Phi(s_{i})$ is computable.

We recall the proof of this lemma, that we will later modify to prove Lemma 6.8.

Proof.

We define $\Phi:S\to\mathbb{Q}_{J}$ iteratively as $\Phi:s_{j_{i}}\mapsto q_{j_{i}}$ for $i\in\mathbb{N}$ . First, define $s_{j_{0}}=s_{0}$ and $q_{j_{0}}=q_{0}$ . Now assuming that $S_{k}:=\{s_{j_{0}},\ldots,s_{j_{k}}\}$ and $Q_{k}:=\{q_{j_{0}},\ldots,q_{j_{k}}\}$ are already defined, let us define its extension according to the following procedure:

(1)

Choose the smallest $i$ such that $s_{i}\notin S_{k}$ and set $S_{k+1}=S_{k}\cup\{s_{i}\}$ . Choose the smallest $j$ such that $q_{j}\notin Q_{k}$ and $\Phi:S_{k}\cup\{s_{i}\}\to Q_{k}\cup\{q_{j}\}$ is an order preserving bijection. Set $s_{j_{k+1}}=s_{i}$ and $q_{j_{k+1}}=q_{j}$ .
(2)

Choose the smallest $j$ such that $r_{j}\notin Q_{k+1}$ , and choose the smallest $i$ such that $s_{i}\notin S_{k+1}$ and $\Phi^{-1}:Q_{k+1}\cup\{q_{j}\}\to S_{k+1}\cup\{s_{i}\}$ is an order preserving bijection. Set $s_{j_{k+2}}=s_{i}$ and $q_{j_{k+2}}=q_{j}$ .
(3)

Repeat the process starting from Step 1.

Since the orderings of $S$ and $\mathbb{Q}_{J}$ are computable with respect to the fixed enumerations, the above described iterative procedure of defining $\Phi$ is also computable. Therefore, the map $i\mapsto\Phi(s_{i})\in\mathbb{Q}_{J}$ is computable. ∎

Remark 2.11.

If $G$ is left-ordered, then the lexicographical left-order on the group $G\times\mathbb{Q}$ is dense (and has no minimal or maximal elements). In addition, if $G=\{g_{1},g_{2},\ldots\}$ has a computable left-order, the lexicographical left-order on $G\times\mathbb{Q}$ is computable with respect to the induced enumeration. Moreover, the standard embedding $G\hookrightarrow G\times\mathbb{Q}$ that sends $g\mapsto(g,0)$ is computable and a Frattini embedding.

2.6. Dynamical realization of computably left-ordered groups

Let $J$ be an interval in $\mathbb{R}$ . We denote the group of homeomorphisms of $J$ by $\operatorname{Homeo}(J)$ , and the subgroup of orientation preserving homeomorphisms of $J$ by $\operatorname{Homeo}^{+}(J)$ .

We note that for every interval $J\subset\mathbb{R}$ , every countable left-ordered group $G$ admits an embedding of $G$ into $\operatorname{Homeo}^{+}(J)$ , see e.g. [CR16, §2.4] [DNR14, Proposition 1.1.8]. We also note the following fact.

Proposition 2.12.

Let $G$ be a countable group.

If $G$ is left-orderable, then there is an embedding $\rho_{G}:G\hookrightarrow\operatorname{Homeo}^{+}(J)$ such that, for all $g\in G\setminus\{1\}$ , the map $\rho_{G}(g):J\rightarrow J$ does not fix any rational interior point of $J$ .

If $G$ is computably left-orderable, then, in addition, all the maps $\rho_{G}(g)$ can be granted to be computable.

We actually need a strong variant of Proposition 2.12, see Proposition 6.7, but to the best of our knowledge, the computability aspect of Proposition 2.12 does not exist in the literature neither. For this reason we decided to include a proof of Proposition 2.12. We analyze computability aspects based on the proof given in [CR16, §2.4].

By Remark 2.11, we may assume that the order on $G$ is dense. Then, by Lemma 2.10, there is an order preserving bijection $\Psi:G\to\mathbb{Q}_{J}$ .

Definition 2.13.

Let $\Psi:G\to\mathbb{Q}_{J}$ be an order preserving bijection. We define $\rho_{G}^{\Psi}:G\to\operatorname{Homeo}^{+}(J)$ by prescribing $\rho_{G}^{\Psi}(g_{i})(\Psi(h))=\Psi(g_{i}h)$ on the dense subset $\Psi(G)=\mathbb{Q}_{J}\subset J$ .

We note the following.

Lemma 2.14.

Let $\Psi:G\to\mathbb{Q}_{J}$ be an order preserving bijection. The map $\rho_{G}^{\Psi}:G\to\operatorname{Homeo}^{+}(J)$ is an embedding. Moreover, if the map $i\mapsto\Psi(s_{i})$ is computable, then for all $i\in\mathbb{N}$ , $\rho_{G}^{\Psi}(g_{i})$ is computable. ∎

Lemma 2.15.

Let $\Psi:G\to\mathbb{Q}_{J}$ be an order preserving bijection. If $x\in\mathbb{Q}_{J}$ such that $\rho_{G}^{\Psi}(g)(x)=x$ , then $g=1$ .

Proof.

Indeed, suppose that $\rho_{G}^{\Psi}(g)(x)=x$ . Let $h=\Psi^{-1}(x)$ . Then by definition of $\rho_{G}^{\Psi}$ , we have $\rho_{G}^{\Psi}(x)=\Psi(gh)$ , i.e. $\Psi(h)=\Psi(gh)$ . But since $\Psi:G\rightarrow\mathbb{Q}_{J}$ is a bijection, $h=gh$ and $g=1$ . ∎

Proof of Proposition 2.12.

Suppose $G=\{g_{1},g_{2},\ldots\}$ has a computable left-order with respect to the given enumeration. By Lemma 2.10, we may assume that the map $i\mapsto\Psi(g_{i})$ is computable. By Lemmas 2.14 and 2.15, $\rho_{G}^{\Psi}:G\to\operatorname{Homeo}^{+}(J)$ satisfies the properties required by Proposition 2.12. ∎

3. Groups of piecewise homeomorphisms of flows

We first collect definitions and facts on groups of piecewise linear homeomorphisms of flows from [MBT18]. As every countable group embeds as a subgroup in a group of piecewise homeomorphisms of flows, we then start to study such groups in more generality.

We recall from Example 2.8 that a dyadic point in $\mathbb{R}$ is one of the form $\frac{n}{2^{m}}$ for some $n\,,m\in\mathbb{Z}$ . Moreover, for a dyadic interval $J$ , $F_{J}$ is Thompson’s group acting on $J$ .

3.1. Minimal subshifts

Let $A$ be a finite alphabet and $\varphi$ a shift on $A^{\mathbb{Z}}$ . If $X$ is a closed and shift-invariant subset of $A^{\mathbb{Z}}$ , then $(X,\varphi)$ is a dynamical system that is called subshift. A subshift is minimal if the set of $\varphi$ –orbits is dense in $X$ .

Let $(X,\varphi)$ be a minimal subshift of $A^{\mathbb{Z}}$ . Then $X$ is totally disconnected and Hausdorff, and every $\varphi$ –orbit is dense in $X$ .

The suspension (or mapping torus) $\Sigma$ of $(X,\varphi)$ is the quotient of $X\times\mathbb{R}$ by the equivalence relation defined by $(x,t)\sim(\varphi^{n}(x),t-n),\,n\in\mathbb{Z}.$ We denote the corresponding equivalence class of $(x,t)\in X\times\mathbb{R}$ by $[x,t]$ .

The map $\Phi_{t}$ that sends $[x,s]$ to $[x,s+t]$ is a homeomorphism and defines a flow $\Phi$ on $\Sigma$ , the suspension flow, so that $(\Sigma,\Phi)$ is a dynamical system as well. The orbits of the suspension flow are homeomorphic to the real line.

We denote by $\operatorname{H}(\varphi)$ the group of homeomorphisms of $\Sigma$ that preserves the orbits of the suspension flow, and by $\operatorname{H}_{0}(\varphi)$ the subgroup of $\operatorname{H}(\varphi)$ that, in addition, preserves the orientation on each orbit.

3.2. The group $\operatorname{T}(\varphi)$

Let $C$ be a clopen subset of $X$ and let $J\subset\mathbb{R}$ be of diameter $<1$ . The embedding of $C\times J$ into $X\times\mathbb{R}$ descends to an embedding into $\Sigma$ that we denote by $\pi_{C,J}$ .

For every clopen $C\subset X$ and subset $J$ of diameter $<1$ in $\mathbb{R}$ , the map $\pi_{C,J}$ is a chart for the suspension, whose image is denoted by $U_{C,J}$ . If $z$ is in the interior of $U_{C,J}$ , then $\pi_{C,J}$ is a chart at $z$ .

Definition 3.1 (Dyadic chart).

Let $C$ be a clopen subset of $X$ , and let $J$ be a dyadic interval of length $<1$ in $\mathbb{R}$ . Then $\pi_{C,J}:C\times J\hookrightarrow\Sigma$ is called dyadic chart.

Definition 3.2 (Dyadic map).

A dyadic map is a map $f$ of real numbers such that $f(x)=\lambda x+c$ , where $\lambda$ is a power of $2$ and $c$ is a dyadic rational.

Definition 3.3 (Definition 3.1 of [MBT18]).

The group $\operatorname{T}(\varphi)$ is the subgroup of $\operatorname{H}_{0}(\varphi)$ consisting of all elements $h\in\operatorname{H}_{0}(\varphi)$ such that for all $z\in\Sigma$ there is a dyadic chart $\pi_{C,J}$ at $z$ and a piecewise dyadic map $f:J\to f(J)$ with finitely many breakpoints such that the restriction of $h$ to $U_{C,J}$ is given by $[x,t]\mapsto[x,f(t)]$ .

We recall that $F_{J}$ denotes the group of piecewise dyadic homeomorphisms of $J$ with finitely many breakpoints.

Definition 3.4.

Let $\pi_{C,J}$ be a dyadic chart and let $f\in F_{J}$ . Then $f_{C,J}$ is the map in $\operatorname{T}(\varphi)$ whose restriction to $U_{C,J}$ is given by

\displaystyle[x,t]\mapsto[x,f(t)]

and that is the identity map elsewhere. We let $F_{C,J}$ be the subgroup of $\operatorname{T}(\varphi)$ generated by the elements $f_{C,J}$ for all $f\in F_{J}$ .

The group $\operatorname{T}(\varphi)$ is infinite, simple, left-ordered and finitely generated [MBT18, Corollary C]. As noted in [MBT18], the first examples of such groups [HL19] are subgroups of $\operatorname{T}(\varphi)$ .

In Section 3.5, we revisit the proof of simplicity given in [MBT18]. In Section 3.6, we revisit the proof of left-orderability given in [MBT18]. To this end we note the following.

Lemma 3.5 (Lemma 3.4 of [MBT18]).

For every $z\in\Sigma$ , the $T(\varphi)$ –orbit of $z$ is dense in the $\Phi$ –orbit of $z$ . In particular, the $\operatorname{T}(\varphi)$ –action on $\Sigma$ is minimal. ∎

For any group $H$ , we denote by $H^{\prime}$ the first derived subgroup of $H$ .

Lemma 3.6 (Lemma 4.8 of [MBT18]).

Let $C\subset X$ be clopen and $J\subset\mathbb{R}$ be dyadic. If $C\times J$ is covered by a family $\{C_{i}\times J_{i}\}_{i\in\mathcal{I}}$ for clopen $C_{i}\subset C$ and dyadic intervals $J_{i}\subset J$ , then $F^{\prime}_{C,J}$ is contained in the group generated by $\bigcup_{i\in\mathcal{I}}F^{\prime}_{C_{i},J_{i}}$ ∎

We assume without restriction that $(X,\varphi)$ is a minimal subshift over the two letter alphabet $A=\{0,1\}$ . For $k,\,n\in\mathbb{Z}$ and a word $w=a_{0}a_{1}\ldots a_{k}$ over $A$ , we denote by $C_{n,w}$ the cylinder subset of $X$ consisting of sequences $(x_{i})_{i\in\mathbb{Z}}$ such that $x_{n}x_{n+1}\ldots x_{n+k}=w$ .

As a matter of fact, the cylinder subsets are clopen and form a basis for the topology of $X$ . We note that

\displaystyle\varphi\left(C_{n,w}\right)=C_{{n-1},w}.

Let $I_{0}:=[-1/4,1/2]$ and $I_{1}:=[1/4,9/8]$ .

Lemma 3.7 (Proposition 6.2 of [MBT18]).

The group $\operatorname{T}(\varphi)$ is generated by $F_{X,I_{0}}$ , $F_{C_{0,0},I_{1}}$ and $F_{C_{0,1},I_{1}}$ . In particular, $\operatorname{T}(\varphi)$ can be generated by six elements.∎

3.3. Piecewise homeomorphisms and group embeddings

Definition 3.8.

A bijection $h:I\to J$ of subsets $I,J\subseteq\mathbb{R}$ is a piecewise homeomorphism if

•

there are half-open pairwise disjoint intervals $I_{i}=[x_{i},y_{i})$ , $i=1,2,\ldots,$ whose union is $I$ ,
•

for all of these $I_{i}$ the restriction of $h$ to $I_{i}$ is a homeomorphism onto its image,

If, in addition, the intervals $I_{i}$ and $h(I_{i})$ are dyadic, we say that $h$ has dyadic breakpoints. If, the restrictions of $h$ to the intervals $I_{i}$ are dyadic maps, we say that $h$ has dyadic pieces.

If $S$ is a set, $\operatorname{bij}(S)$ denotes the group of permutations of $S$ .

Let us fix a half-open interval $\mathfrak{J}=[x,y)$ that is strictly contained in $[0,1]$ . Let $\mathcal{C}(\mathfrak{J})\subset\operatorname{bij}(\mathfrak{J})$ denote the subgroup of all piecewise homeomorphisms with dyadic breakpoints on $\mathfrak{J}$ . The subgroup of $\mathcal{C}(\mathfrak{J})$ of orientation preserving bijections is denoted by $\mathcal{C}^{+}(\mathfrak{J})$ .

Example 3.9.

Every countable group embeds into $\mathcal{C}(\mathfrak{J})$ .

Example 3.10.

Every countable left-orderable group embeds into the group of orientation preserving homeomorphisms of $\mathfrak{J}$ , and therefore into $\mathcal{C}^{+}(\mathfrak{J})$ .

Since the set of non-dyadic rational points of $\mathfrak{J}$ is dense in $\mathfrak{J}$ , the next lemma is a basic property of the (piecewise) continuity.

Lemma 3.11.

Every function in $\mathcal{C}(\mathfrak{J})$ is uniquely determined by its values on non-dyadic rational points on $\mathfrak{J}$ . Moreover, every function from $\mathcal{C}(\mathfrak{J})$ is continuous at non-dyadic rational points.∎

To construct respective embeddings into finitely generated simple groups we propose the following extension of the construction in [MBT18].

3.4. Groups of flows of piecewise homeomorphisms

Let us fix a subgroup $G$ of $\mathcal{C}(\mathfrak{J})$ .

Definition 3.12.

Define $\tau_{\Sigma,\mathfrak{J}}:G\rightarrow\operatorname{bij}(\Sigma)$ as follows: for each $g\in G$ , let $\tau_{\Sigma,\mathfrak{J}}(g):=g_{\Sigma,\mathfrak{J}}$ , where $g_{\Sigma,\mathfrak{J}}$ is defined by

\displaystyle g_{\Sigma,\mathfrak{J}}:[x,t]\mapsto[x,g(t)],\mbox{ for all }t\in\mathfrak{J},

and $g_{\Sigma,\mathfrak{J}}$ is the identity map elsewhere.

We extend Definition 3.3 as follows.

Definition 3.13 (The group $T(G,\varphi)$ ).

Let $G$ be a subgroup of $\mathcal{C}(\mathfrak{J})$ . We define $T(G,\varphi)$ as the subgroup of $\operatorname{bij}(\Sigma)$ generated by $\tau_{\Sigma,\mathfrak{J}}(G)$ and $T(\varphi)$ .

Lemma 3.14.

The group $G$ embeds into $T(G,\varphi)$ by $g\mapsto g_{\Sigma,\mathfrak{J}}$ . Moreover, if $G$ is finitely generated, then $T(G,\varphi)$ is finitely generated as well.

Proof.

The second statement follows from the definition of $T(G,\varphi)$ and the fact that $T(\varphi)$ is finitely generated. For the first statement, it is enough to notice that, by definition, $g_{\Sigma,\mathfrak{J}}$ is an identity map if and only if $g=1$ . ∎

Definition 3.15 ((Non-dyadic) rational points).

A point $[x,t]\in\Sigma$ is called a rational point on $\Sigma$ if $t\in\mathbb{Q}$ . If, in addition, $t$ is not dyadic, we say that $[x,t]$ is a non-dyadic rational point.

Lemma 3.16.

There exists a dense and recursive set of non-dyadic rational points in $\Sigma$ .

Proof.

Let us choose a recursive countable subset $\mathcal{X}:=\{x_{1},x_{2},\ldots\}\subset X$ that is dense in $X$ , for example, the set of proper ternary fractions. Moreover, for all $i\in\mathbb{N}$ , let $R_{i}\subset\Sigma$ be defined as

R_{i}:=\{[x_{i},t]\mid\hbox{$t$ is rational and non-dyadic}\}.

We denote $R=\cup_{i=1}^{\infty}R_{i}.$ Note that each of $R_{i}$ is a recursive set. Therefore, since $\mathcal{X}$ is also recursive by our choice, the we get that $R$ is recursive as well. ∎

Lemma 3.17.

If $G$ is a subgroup of $\mathcal{C}(\mathfrak{J})$ , then the elements of $T(G,\varphi)$ are uniquely defined by their values on any (countable) dense set of non-dyadic rational points of $\Sigma$ . Moreover, the elements of $T(G,\varphi)$ are continuous at non-dyadic rational points of $\Sigma$ .

Proof.

By Lemma 3.16 there a fixed countable dense set of non-dyadic rational points in $\Sigma$ . Let $R\subset\Sigma$ be such a set. Let us define $\mathcal{X}\subset X$ such that for each $x\in\mathcal{X}$ there exists $t\in\mathbb{Q}$ such that $[x,t]\in R$ . Since $R$ is dense, $\mathcal{X}$ is dense as well.

Note that since $\mathcal{X}\subset X$ is dense in $X$ , by Lemma 3.5, the set $\{[x,t]\mid x\in\mathcal{X},t\in\mathbb{R}\}$ is dense in $\Sigma$ . Therefore, the elements of $T(G,\varphi)$ are uniquely defined by their restrictions to the $\Phi$ -orbits of the elements $[x,0]$ for $x\in\mathcal{X}$ . Now, the lemma follows from the combination of this observation with Lemma 3.11. ∎

3.5. Simplicity and rigid stabilizers

To prove simplicity results, we use the following standard tool.

Let $Y$ be a set, and $H$ a group acting faithfully on $Y$ . Then the rigid stabilizer of a subset $U\subset Y$ is the subgroup of $H$ whose elements move only points from $U$ . We denote the rigid stabilizer of $U$ by $\operatorname{RiSt}(U)$ .

The following lemma is used to prove simplicity of $\operatorname{T}(\varphi)$ in [MBT18], cf. [MBT18, Lemma 2.1].

Lemma 3.18.

Let $N$ be a normal subgroup of $H$ . If there is a non-trivial element $g\in N$ and a non-empty subset $U\subset Y$ such that $g(U)\cap U=\emptyset$ , then the first derived subgroup ${\operatorname{RiSt}(U)}^{\prime}$ is in $N$ . ∎

A group $G$ is called perfect if it coincides with its first derived subgroup, that is $G=G^{\prime}(=[G,G])$ .

Lemma 3.19.

If $G\leq\mathcal{C}(\mathfrak{J})$ is a perfect group, then $T(G,\varphi)$ is simple.

Proof.

Assume that $N$ is a normal subgroup of $T(H,\varphi)$ and $N\neq\{1\}$ . The proof of Lemma 3.19 follows from the following two claims.

Claim 1: The group $\operatorname{T}(\varphi)$ is in $N$ .

The proof of Claim 1 follows the arguments of simplicity in [MBT18].

Proof of Claim 1.

Let us fix a non-trivial element $g\in N$ . Then, by Lemma 3.17, there exists a non-dyadic rational point $y\in\Sigma$ such that $g(y)\neq y$ . By Lemma 3.17, the elements of $T(G,\varphi)=\langle\tau_{\Sigma,\mathfrak{J}}(G),T(\varphi)\rangle$ are continuous at the non-dyadic rational points of $\Sigma$ . Therefore, since $\Sigma$ is a Hausdorff space and $g(y)\neq y$ , there exists an open neighborhood $U$ of $y$ such that $gU\cap U=\emptyset$ . By Lemma 3.18, ${\operatorname{RiSt}(U)}^{\prime}$ is in $N$ .

Let $z\in\Sigma$ , and choose $h\in\operatorname{T}(\varphi)$ such that $h(z)\in U$ . Such a map $h$ exists as, by Lemma 3.5, the action of $\operatorname{T}(\varphi)$ on $\Sigma$ is minimal. Then, as $z\in h^{-1}U$ and $\operatorname{RiSt}(h^{-1}U)=h^{-1}\operatorname{RiSt}(U)h$ , the rigid stabilizer $\operatorname{RiSt}(h^{-1}U)$ is in $N$ .

As $h^{-1}U$ is open, there is a chart $\pi_{C,K}$ at $z$ which is in $h^{-1}U$ . Since ${F_{C,K}}$ is in the rigid stabilizer of $h^{-1}U$ , we conclude that ${F_{C,K}}^{\prime}\subseteq N$ .

Therefore, for every chart $\pi_{C,K}$ there is a covering $\{C_{i}\times K_{i}\}$ of $C\times K$ such that ${F_{C_{i},K_{i}}}^{\prime}$ is in $N$ . By Lemma 3.6, we conclude that for every chart $\pi_{C,K}$ the group ${F_{C,K}}^{\prime}$ is in $N$ . Now we use that $\bigcup_{I\subsetneq K}F_{I}\subset{F_{K}}^{\prime}$ (cf. [CFP96, Theorem 4.1]) to conclude that the generators of $\operatorname{T}(\varphi)$ are in $N$ . ∎

Claim 2: For every normal subgroup $N$ of $\operatorname{T}(G,\varphi)$ , $\tau_{\Sigma,\mathfrak{J}}(G)$ is in $N$ .

Proof of Claim 2.

Let $f\in F_{[0,1]}$ be an element of Thompson’s group such that $J\cap f(J)=\emptyset$ . Then $f_{X\times[0,1]}$ is in $\operatorname{T}(\varphi)$ and separates $U_{X\times J}$ from $U_{X,f(J)}$ . By the previous claim, $f_{X,J}\in N$ . Therefore, the first derived subgroup of the rigid stabilizer of the interior of $U_{X\times J}$ is in $N$ by Lemma 3.18. Finally, we note that $\tau_{\Sigma,\mathfrak{J}}(G)$ is in the rigid stabilizer of the interior of $U_{X,J}$ . Thus $\tau_{\Sigma,\mathfrak{J}}(G)^{\prime}$ is in $N$ . As $G$ is assumed to be perfect, this yields the claim. ∎

Now, to conclude the proof of Lemma 3.19, we only need to combine the above claims with the fact that, by definition, $T(G,\varphi)=\langle\tau_{\Sigma,\mathfrak{J}}(G),T(\varphi)\rangle$ . ∎

3.6. Left-orders on $T(G,\varphi)$

Lemma 3.20.

If $G\leq\mathcal{C}^{+}(\mathfrak{J})$ , then the group $T(G,\varphi)$ is left-orderable. Moreover, if $G$ is finitely generated and consists of computable functions, then there exists a left-order on $T(G,\varphi)$ with recursively enumerable positive cone.

Proof.

First of all, note that since $G\leq\mathcal{C}^{+}(\mathfrak{J})$ , the action of $T(G,\varphi)$ on $\Phi$ -orbits of elements of $X\subset\Sigma$ is orientation preserving.

Let $R=\{[a_{1},s_{1}],[a_{2},s_{2}],\ldots\}$ be a fixed, recursively enumerated and dense subset of non-dyadic rationals in $\Sigma$ . The existence of such sets is by Lemma 3.16.

Now for $f\in T(G,\varphi)$ , define $f>1$ if for the smallest index $k\in\mathbb{N}$ such that $f([a_{k},s_{k}])\neq[a_{k},s_{k}]$ we have $f([a_{k},s_{k}])=[a_{k},q_{k}]$ such that $q_{k}>s_{k}$ . Therefore, by Lemma 3.11, for all $f\neq 1$ either $f>1$ or $f^{-1}>1$ and for $f_{1},f_{2}>1$ , $f_{1}f_{2}>1$ . By Lemma 3.17, the defined order is a left-order on $T(G,\varphi)$ .

Recall that the set $R$ is recursive. Therefore, to check whether $f>1$ , we can consecutively compute the values $f([a_{1},s_{1}]),f([a_{2},s_{2}]),\ldots$ . We stop at the first $k$ such that $f([a_{k},s_{k}])\neq[a_{k},s_{k}]$ . By Lemma 3.17, this procedure stops if and only if $f\neq 1$ , and since $G$ consists of computable maps, this procedure recursively enumerates the positive cone of the above defined left-order. ∎

Corollary 3.21.

The group $T(\varphi)$ has a left-order with recursively enumerable positive cone.

4. Chart representations and the word problem in $T(G,\varphi)$

Recall that $\mathfrak{J}$ is a fixed interval that is strictly contained in $[0,1)$ . Let us fix a subgroup $G$ in $\mathcal{C}({\mathfrak{J}})$ , and assume that $G$ is finitely generated and consists of computable functions.

4.1. Chart representations

Definition 4.1 (Chart representations).

Let $h\in T(G,\varphi)$ . A chart representation of $h$ is a finite collection of triples $(C_{i}\times I_{i},C_{i}\times J_{i},h_{i})$ , where $h_{i}$ is a piecewise homeomorphism with countably many breakpoints on $I_{i}$ and $h_{i}(I_{i})=J_{i}$ , such that $\{U_{C_{i}\times I_{i}}\}$ and $\{U_{C_{i}\times J_{i}}\}$ cover $\Sigma$ , and such that the restriction of $h$ to ${U_{C_{i}\times I_{i}}}$ is the function $[x,t]\mapsto[x,h_{i}(t)]$ .

Each of the triples $(C_{i}\times I_{i},C_{i}\times J_{i},h_{i})$ is called a chart. The maps $h_{i}$ are local representations of $h$ .

Remark 4.2.

Chart representations play the role of the (partial) tables of Thompson in [Tho80].

Remark 4.3.

By definition (compactness of $X$ and $\Sigma$ ) every $h\in T(G,\varphi)$ has a chart representation.

Remark 4.4.

Chart representations are not unique.

Example 4.5.

$f\in F_{X\times[-1/4,1/2]}$ . We give two chart representations for $f$ :

(1)

$\big{\{}(X\times[-1/4,1/2],X\times[-1/4,1/2],f),$
$(X\times[1/2,3/4],X\times[1/2,3/4],id)\big{\}}.$
(2)

$\big{\{}(X\times[0,1/2],X\times f([0,1/2]),f|_{[0,1/2]})$
$(X\times[3/4,1],X\times f([-1/4,0])+1,t\mapsto f|_{[-1/4,0]}(t-1)+1)$ ,
$(X\times[1/2,3/4],X\times[1/2,3/4],id)\big{\}}$ .

Definition 4.6 ( $G$ -dyadic maps).

A piecewise homeomorphism $\Lambda:I_{n}\to I_{0}$ is a $G$ -dyadic map if $\Lambda=g_{1}f_{1}\ldots g_{n}f_{n}$ is a composition of piecewise homeomorphisms $f_{i}:I_{i}\to J_{i}\subseteq\mathfrak{J}$ and $g_{i}:J_{i}\to I_{i-1}$ , where all $f_{i}$ are dyadic maps, $f_{i}\not=id$ whenever $i\not=n$ , and the $g_{i}$ are restrictions of non-trivial elements of $G$ .

Remark 4.7.

A $G$ -dyadic map could a priori be equal to the identity map.

Definition 4.8 (Canonical chart representations).

Let $h\in T(G,\varphi)$ , and let $\{(C_{i}\times I_{i},C_{i}\times J_{i},h_{i})\}_{1\leqslant i\leqslant n}$ be a chart representation of $h$ such that for every $h_{i}$ , $1\leq i\leq n$ , one of the following takes place:

(I)

$h_{i}$ is a dyadic map on $I_{i}$ ;
(II)

$h_{i}=f\Lambda$ is the composition a dyadic map $f$ and a $G$ -dyadic map $\Lambda$ .

Then, the representation $\{(C_{i}\times I_{i},C_{i}\times J_{i},h_{i})\}_{1\leqslant i\leqslant n}$ is called canonical. Also, charts for which $h_{i}$ corresponds to (I) or (II) are called charts of type (I) or (II), respectively.

4.2. Operations on charts

The following operations can be applied to go from one chart representation to another.

Definition 4.9 (Inverse).

Let $\{(C_{i}\times I_{i},C_{i}\times J_{i},h_{i})\}_{1\leqslant i\leqslant n}$ be a chart representation of $h\in T(G,\varphi)$ . Then $\{(C_{i}\times J_{i},C_{i}\times I_{i},h^{-1}_{i})\}_{1\leqslant i\leqslant n}$ is a chart representation of $h^{-1}$ and is called the inverse of the initial one.

Definition 4.10 (Refinements).

The following operations on charts are called refinement.

(1)

If $I=I_{0}\cup I_{1}$ , then $(C\times I,C\times J,f)$ can be replaced by $(C\times I_{0},C\times f(I_{0}),f|_{I_{0}})$ and $(C\times I_{1},C\times f(I_{1}),f|_{I_{1}})$ .
(2)

If $J=J_{0}\cup J_{1}$ , then $(C\times I,C\times J,f)$ can be replaced by $(C\times f^{-1}(J_{0}),C\times J_{0},f|_{f^{-1}(J_{0})})$ and $(C\times f^{-1}(J_{1}),C\times J_{1},f|_{f^{-1}(J_{1})})$ .
(3)

If $C=C_{0}\cup C_{1}$ , then $(C\times I,C\times J,f)$ can be replaced by $(C_{0}\times I,C_{0}\times J,f)$ and $(C_{1}\times I,C_{1}\times J,f)$ .

Definition 4.11 (Reunions).

A reunion is the inverse operation of a refinement.

Definition 4.12 (Shifts).

A shift (of order $m\in\mathbb{Z}$ ) is replacing a triple $(C\times I,C\times J,f)$ by $(\varphi^{m}(C)\times(I-m),\varphi^{m}(C)\times(J-m),t\mapsto f(t+m)-m)$ .

Remark 4.13.

A chart representation obtained by a refinements, reunion, or a shift on its charts corresponds to the same element from $T(G,\varphi)$ . In particular, chart representations of elements from $T(G,\varphi)$ are not unique.

Remark 4.14.

Since the functions in $G$ are computable, the operations 4.9, 4.10, 4.11 and 4.12 are computable.

Lemma 4.15.

$T(G,\varphi)$ is finitely generated and each of the generators can be represented by a canonical chart representation, which can be algorithmically determined.

Proof.

Indeed, the generators of $T(\varphi)$ given by Lemma 3.7 can be represented as in Example 4.5. One then applies a finite number of chart refinements at the breakpoints of the generating piecewise dyadic maps to obtain a canonical chart representation. The generators of $G$ can be represented by a canonical chart representation by definition. ∎

Lemma 4.16.

The inverse, refinements and shifts preserve the canonicity of chart representations.

Proof.

We will prove only that shift operations on charts of type (II) preserve the canonicity of chart representations, as the rest of statements of the lemma are straightforward.

Suppose that the initial chart of type (II), on which a shift operation of order $m$ is applied, is $(C_{i}\times I_{i},C_{i}\times J_{i},\Lambda)$ . Then a shift of order $m$ would transform it into the chart $(\varphi^{m}(C_{i})\times(I_{i}-m),\varphi^{m}(C_{i})\times(J_{i}-m),\tilde{\Lambda})$ , where $\tilde{\Lambda}:I_{i}-m\rightarrow J_{i}-m$ is defined as $\tilde{\Lambda}(x)=\Lambda(x+m)-m$ .

Suppose that $\Lambda=fg_{1}f_{1}\ldots g_{n}f_{n}$ is decomposed as in Definition 4.6. Then, $\tilde{\Lambda}=\tilde{f}g_{1}f_{1}\ldots g_{n}\tilde{f}_{n}$ , where $\tilde{f}_{n}(x)=f_{n}(x+m)$ and $\tilde{f}(x)=f(x)-m$ . The chart $\tilde{\Lambda}$ is also a $G$ -dyadic map. Therefore, $(\varphi^{m}(C_{i})\times(I_{i}-m),\varphi^{m}(C_{i})\times(J_{i}-m),\tilde{\Lambda})$ satisfies the definition of charts of type (II) from Definition 4.8. Thus shift operations applied on charts of type (II) of canonical chart representations preserve the canonicity. ∎

Definition 4.17 (Composition).

Let $\{(C_{i}\times I_{i},C_{i}\times J_{i},f_{i})\}_{1\leqslant i\leqslant n}$ and $\{(C^{\prime}_{i}\times I^{\prime}_{i},C^{\prime}_{i}\times J^{\prime}_{i},f^{\prime}_{i})\}_{1\leqslant i\leqslant m}$ be chart representations such that $\bigcup I_{i}=\bigcup J_{i}^{\prime}=[0,1]$ . Then we say that the chart representation

\{(C_{i,j}\times I_{i,j},C_{i,j}\times J_{i,j},f_{i,j})\}_{1\leqslant i\leqslant mn},

where

I_{i,j}=f_{i}^{\prime-1}(J_{i}^{\prime}\cap I_{j})\subseteq I^{\prime}_{i},~{}J_{i,j}=f_{j}(f_{i}^{\prime-1}(J_{i}^{\prime}\cap I_{j}))\subseteq J_{j},

C_{i,j}=C_{i}\cap C_{j},\text{~{}and~{}}f_{ij}=f_{j}\mid_{J_{i}^{\prime}\cap I_{j}}\circ f_{i}^{\prime}\mid_{f_{i}^{\prime-1}(J_{i}^{\prime}\cap I_{j})},

is their composition.

Remark 4.18.

Note that if, in Definition 4.17, the chart representations correspond to $f,f^{\prime}\in T(G,\varphi)$ , respectively, then the composition chart representation corresponds to $ff^{\prime}$ .

Remark 4.19.

Note that if the two chart representations in Definition 4.17 are canonical, then their composition is canonical as well. In addition, finding the composition is a computable procedure.

Lemma 4.20.

Let $h\in T(G,\varphi)$ be given by a canonical chart representation $\{(C_{i}\times I_{i},C_{i},\times J_{i},h_{i})\}_{1\leqslant i\leqslant n}.$ Then there is an algorithm to determine a canonical chart representation $\{(C_{j}^{\prime}\times I_{j}^{\prime},C_{j}^{\prime}\times J_{j}^{\prime},h_{i}^{\prime})\}_{1\leqslant j\leqslant n^{\prime}}$ of $h$ such that $\bigcup J_{j}^{\prime}=[0,1]$ .

Proof.

We describe the algorithm. For $1\leqslant i\leqslant n$ ,

if $J_{i}\subset[0,1]$ do nothing, go to $i+1$ .

if $J_{i}\cap[0,1]$ and $J_{i}\setminus(0,1)$ is non-empty, let $J_{i_{1}}=J_{i}\cap[0,1]$ , $J_{i_{2}}=J_{i}\setminus(0,1)$ and apply a refinement (Definition 4.10 (2)). Repeat from the beginning.

if $J_{i}\cap[0,1]$ is empty, determine $m$ such that $J_{i}-m\cap[0,1]$ is non-empty and apply a shift of order $m$ (Definition 4.12). Repeat from the beginning.

Since this procedure does not affect charts of type (2) from Definition 4.8, by Lemma 4.16, the canonicity of the initial chart representation is preserved. ∎

Lemma 4.21.

Proof.

The proof is analogous to the proof of Lemma 4.20.∎

Lemma 4.22.

There is an algorithm that for any two elements $f,f^{\prime}\in T(G,\varphi)$ , given by their canonical chart representations, computes a canonical representation of $ff^{\prime}$ .

Proof.

By Lemmas 4.20 and 4.21, there exists an algorithmic procedure that computes canonical chart representations $\{(C_{i}\times I_{i},C_{i}\times J_{i},f_{i})\}_{1\leqslant i\leqslant n}$ and $\{(C^{\prime}_{i}\times I^{\prime}_{i},C^{\prime}_{i}\times J^{\prime}_{i},f^{\prime}_{i})\}_{1\leqslant i\leqslant m}$ of respectively $f$ and $f^{\prime}$ such that $\bigcup I_{i}=\bigcup J_{i}^{\prime}=[0,1]$ . Then their composition will be a canonical chart representation of $ff^{\prime}$ (see Remarks 4.18 and 4.19.) ∎

From the previous two lemmas we get:

Lemma 4.23.

There exists an algorithm that for any input $f\in T(G,\varphi)$ , given as a word in finite set of generators, outputs a canonical chart representation of $f$ . In particular, every element from $T(G,\varphi)$ has a canonical chart representation.

Proof.

It follows from Remark 4.18, Lemma 4.22, and the fact that the standard generators of $T(G,\varphi)$ have canonical chart representations, see Lemma 4.15. ∎

4.3. The word problem

The following observations are useful for studying the groups $T(G,\varphi)$ .

Lemma 4.24.

Let $h\in T(G,\varphi)$ and let $\{(C_{i}\times I_{i},C_{i}\times J_{i},h_{i})\}_{1\leqslant i\leqslant n}$ be a chart representation of $h$ . Then $h=1$ in $T(G,\varphi)$ if and only if, for all $1\leqslant i\leqslant n$ , we have $h_{i}=id$ (and $J_{i}=I_{i}$ ).

Proof.

Let $1\leqslant i\leqslant n$ . Recall that $h$ maps $[x,t]$ to $[x,h_{i}(t)]$ for $(x,t)\in C_{i}\times I_{i}$ . As $h=1$ , $[x,h_{i}(t)]=[x,t].$ Thus, for any $x\in C_{i}$ and $t\in I_{i}$ , there is $m\in\mathbb{Z}$ such that $(\varphi^{m}(x),t-m)=(x,h_{i}(t))$ . We conclude that $h_{i}(t)=t-m$ and $\varphi^{m}(x)=x$ . But $\varphi$ is a minimal subshift, that is, every orbit of $\varphi$ is dense. In particular, $m=0$ . Therefore $h_{i}=id$ . This yields one side of the assertion. The inverse assertion is trivial. ∎

Lemma 4.25.

If there is an algorithm to decide whether a $G$ –dyadic map is equal to the identity, then the word problem in $T(G,\varphi)$ is decidable.

Proof.

By Lemma 4.23, for every $h\in T(G,\varphi)$ one can algorithmically find a canonical chart representation for $h$ . By Lemma 4.24, $h=1$ if and only if for any canonical chart representation of $h$ the corresponding charts of types (I), and (II) are identity charts. If $h_{i}$ a local representation in a chart of type (I), $h_{i}$ is a piecewise dyadic map with finitely many breakpoints, so that we can algorithmically check whether $h_{i}=id$ .

Now suppose that $h=f\Lambda:I\to I$ is a local representation in a chart of type (II), where $f:I_{0}\to I$ is dyadic and $\Lambda:I_{n}\to I_{0}$ a $G$ -dyadic map. We note that $h=id$ on $I$ if, and only if, $\Lambda f=id$ on $I_{0}$ . In fact, $\Lambda f$ is a $G$ –dyadic map, so that, by assumption, we can algorithmically check whether $h=id$ . ∎

Corollary 4.26.

$T(\varphi)$ is computably left-orderable. In particular, the word problem in $T(\varphi)$ is decidable.

Proof.

By Lemma 4.25, the word problem is decidable. By Corollary 3.21, $T(\varphi)$ has a recursively enumerable positive cone. Thus, by Lemma 2.9, $T(\varphi)$ is computably left-orderable. ∎

5. Embeddings into perfect groups

Our next goal is to prove the following.

Theorem 5.1.

Every countable group $G$ embeds into a finitely generated perfect group $H$ . In addition,

(1)

if $G$ is computable, then $H$ has decidable word problem;
(2)

if $G$ is left-ordered, then $H$ is left-ordered;
(3)

if $G$ is computably left-ordered, then the left order on $H$ is computable;
(4)

the embedding is a Frattini embedding.

Moreover, in case (2) and (3), the order on $H$ continues the order on $G$ .

This strengthens [Neu60], [Gla81, Theorem 10A] and [Tho80, Theorem 2.3]. If $G$ is assumed to be finitely generated, assertion $(1)$ is proved in [Tho80, Theorem 2.3]. Examples of (finitely generated) left-ordered and perfect groups are well-known, see [Ber91].

We first prove Theorem 5.1 for finitely generated groups. In Section 5.4, we reduce the general case to the finitely generated case.

5.1. Splinter Groups

Let us assume that $G$ is a finitely generated group. We now construct a finitely generated perfect group in which $G$ embeds. Our construction resembles the splinter group construction of [Tho80, §2]. We comment on the construction of [Tho80] in Section 5.5.

Let us fix an action of $T(\varphi)$ on the real line as follows: let us fix $z_{0}:=[x_{0},0]\in\Sigma$ . As the action of $\operatorname{T}(\varphi)$ on $\Sigma$ preserves the $\Phi$ –orbits, $T(\varphi)$ acts on the $\Phi$ –orbit of $z_{0}$ , the action is orientation-preserving, and its orbits are dense. Finally, recall that the $\Phi$ –orbit of $z_{0}$ is homoemorphic to $\mathbb{R}$ . We fix such a homeomorphism. This induces an action of $T(\varphi)$ on $\mathbb{R}$ . We fix this action of $\operatorname{T}(\varphi)$ .

Let $\mathcal{C}_{0}(\mathbb{R},G)$ denote the group of functions from $\mathbb{R}$ to $G$ of bounded support. The action of $T(\varphi)$ on $\mathbb{R}$ induces an action $\sigma$ of $T(\varphi)$ on $\mathcal{C}_{0}(\mathbb{R},G)$ such that for every $h\in\mathcal{C}_{0}(\mathbb{R},G)$ and $f\in T(\varphi)$ ,

\sigma(f)(h)(s):=h(f^{-1}(s)).

The permutational wreath product $G\wr_{\mathbb{R}}\operatorname{T}(\varphi)$ is defined as the semi-direct product $\mathcal{C}_{0}(\mathbb{R},G)\rtimes_{\sigma}\operatorname{T}(\varphi)$ , where, for $(h_{1},f_{1})$ and $(h_{2},f_{2})\in\mathcal{C}_{0}(\mathbb{R},G)\rtimes_{\sigma}\operatorname{T}(\varphi)$ , $(h_{1},f_{1})(h_{2},f_{2}):=(h_{1}\sigma(f_{1})(h_{2}),f_{1}f_{2})$ .

For every $g\in G$ , we define the following function $\overline{g}$ in $\mathcal{C}_{0}(\mathbb{R},G)$ :

\displaystyle\overline{g}(s):=\begin{cases}g&\hbox{for }s\in[1/2,1),\\ 1&\hbox{otherwise;}\end{cases}

and $\overline{G}:=\{\overline{g}\mid g\in G\}$ .

Definition 5.2 (Splinter groups).

The splinter group is the subgroup of the permutational wreath product $G\wr_{\mathbb{R}}\operatorname{T}(\varphi)$ generated by $\overline{G}$ and $\operatorname{T}(\varphi)$ . We denote it by $\operatorname{Sp}(G,\varphi)$ .

Recall that $\operatorname{T}(\varphi)$ and $G$ are finitely generated. We note the following.

Lemma 5.3.

The group $G$ embeds into $\operatorname{Sp}(G,\varphi)$ with image $\overline{G}$ . Moreover, $\operatorname{Sp}(G,\varphi)$ is finitely generated.∎

Lemma 5.4.

The splinter group $\operatorname{Sp}(G,\varphi)$ is perfect.

To prove Lemma 5.4, we adapt the arguments of the proof of [Tho80, Theorem 2.3]. We first prove

Lemma 5.5.

The group $\overline{G}$ is in the first derived subgroup $\operatorname{Sp}(G,\varphi)^{\prime}$ of $\operatorname{Sp}(G,\varphi)$ .

Proof.

Let $f_{1}$ and $f_{2}\in T(\varphi)$ be such that $f_{1}$ maps $[1/2,1)$ onto $[1/4,1)$ and $f_{2}$ maps $[1/2,1)$ onto $[1/4,1/2)$ , respectively. The existence of such elements follows from the definition of $T(\varphi)$ . We note that for any $\bar{g}\in\bar{G}$

	$\displaystyle f_{1}\overline{g}f_{1}^{-1}(s)=\sigma(f_{1})(\bar{g})(s)=$	$\displaystyle\begin{cases}g&\hbox{for }s\in[1/4,1),\\ 1&\hbox{otherwise;}\\ \end{cases}$
	$\displaystyle f_{2}\overline{g}f_{2}^{-1}(s)=\sigma(f_{2})(\bar{g})(s)=$	$\displaystyle\begin{cases}g&\hbox{for }s\in[1/4,1/2),\\ 1&\hbox{otherwise.}\end{cases}$

Therefore, $\overline{g}=f_{1}\overline{g}f_{1}^{-1}(f_{2}\overline{g}f_{2}^{-1})^{-1}$ , hence $\overline{g}$ is a commutator element. This completes the proof. ∎

Proof of Lemma 5.4.

Since $\operatorname{T}(\varphi)$ is simple, it is in $\operatorname{Sp}(G,\varphi)^{\prime}$ . By Lemma 5.5, $\overline{G}$ is in $\operatorname{Sp}(G,\varphi)^{\prime}$ as well. Therefore, $\operatorname{Sp}(G,\varphi)^{\prime}=\operatorname{Sp}(G,\varphi)$ . ∎

Lemma 5.6.

The group $G$ isometrically embeds into $\operatorname{Sp}(G,\varphi)$ .

Proof.

Let $X$ and $Y$ be finite generating sets of $G$ and $T(\varphi)$ , respectively. We prove that the embedding of $G=\langle X\rangle$ into $\operatorname{Sp}(G,\varphi)=\langle\bar{X}\cup{Y}\rangle$ by $g\mapsto\bar{g}$ is an isometric embedding, where $\bar{X}$ is the image of $X$ in $\operatorname{Sp}(G,\varphi)$ .

Let $g\in G$ . Also, let $f_{i}\in T(\varphi)$ and $g_{i}\in G$ , $1\leq i\leq n$ , be such that

\bar{g}=f_{1}\bar{g}_{1}\ldots f_{n}\bar{g}_{n}

and $|\bar{g}|_{\bar{X}\cup{Y}}=\sum_{i=1}^{n}|f_{i}|_{\bar{X}\cup{Y}}+\sum_{i=1}^{n}|\bar{g}_{i}|_{\bar{X}\cup{Y}}$ , where $|\cdot|$ is the length of the group element with respect to the corresponding generating set. We have

\bar{g}=\bar{g_{1}}^{h_{1}}\bar{g_{2}}^{h_{2}}\ldots\bar{g_{n}}^{h_{n}}h_{n},

where $h_{i}=f_{1}\ldots f_{i}$ , $1\leq i\leq n$ . Therefore, it must be that $h_{n}=1$ and

\bar{g}(1/2)=g=\prod_{i\in I}g_{i},

where $I\subseteq\{1,\ldots,n\}$ is the set of indexes $i$ such that $h_{i}(1/2)\in[1/2,1)$ . Thus we get

\bar{g}=\prod_{i\in I}\bar{g}_{i}.

Therefore, since we have $|\bar{g}|_{\bar{X}\cup{Y}}=\sum_{i=1}^{n}|f_{i}|_{\bar{X}\cup{Y}}+\sum_{i=1}^{n}|\bar{g}_{i}|_{\bar{X}\cup{Y}}$ , we get $f_{1}=\ldots=f_{n}=1$ and $I=\{1,\ldots,n\}$ , which implies that $|g|_{X}=|\bar{g}|_{\bar{X}\cup{Y}}$ . Since $g$ is an arbitrary element of $G$ , the last conclusion finishes the proof.

∎

Lemma 5.7.

The embedding of $G$ into $\operatorname{Sp}(G,\varphi)$ by $g\mapsto\bar{g}$ is a Frattini embedding.

Proof.

Let $g,h\in G$ , and suppose that $\bar{g}$ and $\bar{h}$ are conjugate in $\operatorname{Sp}(G,\varphi)$ . We want to show that $g$ is conjugate to $h$ in $G$ .

There exist $e\in C_{0}(\mathbb{R},G)$ and $f\in T(\varphi)$ such that $(e,f)\bar{g}(e,f)^{-1}=\bar{h}$ or, equivalently, $e\sigma(f)(\bar{g})e^{-1}=\bar{h}$ . Therefore, we have

\displaystyle\operatorname{supp}(e\sigma(f)(\bar{g})e^{-1})=\operatorname{supp}(\bar{h})=[1/2,1).

On the other hand,

\operatorname{supp}(e\sigma(f)(\bar{g})e^{-1})=\operatorname{supp}(\sigma(f)(\bar{g}))=f(\operatorname{supp}(\bar{g}))=f([1/2,1)).

Thus $f([1/2,1))=[1/2,1)$ , which implies that $\sigma(f)(\bar{g})=\bar{g}$ (recall that $\bar{g}$ is constant on $[1/2,1)$ ) and, hence, $e\bar{g}e^{-1}=\bar{h}.$ The last equality immediately implies that $g$ is conjugate to $h$ in $G$ . ∎

5.2. The word problem for $\operatorname{Sp}(G,\varphi)$ .

We recall that $\operatorname{T}(\varphi)$ is computably left-ordered, acts order-preservingly on $\mathbb{R}$ , and that this action is computable.

We adapt a notion of splinter table introduced in [Tho80, p. 413].

Definition 5.8 (Splinter table).

A splinter table corresponding to the element $(t,f)\in\operatorname{Sp}(G,\varphi)$ is a finite tuple of the form $(J_{1},\ldots,J_{n};g_{1},\ldots,g_{n};f)$ , where $J_{1},\ldots,J_{n}$ is a disjoint finite collection of bounded intervals from $\mathbb{R}$ whose union contains the support of $t:\mathbb{R}\rightarrow G$ such that $t(J_{i})=g_{i}\in G$ .

Example 5.9.

The group $\overline{G}$ coincides with the set of all splinter tables $([1/2,1);g;1_{T(\varphi)})$ , $g\in G$ , and $\operatorname{T}(\varphi)$ coincides, for example, with the set of all splinter tables $([1/2,1);1_{G};f)$ , $f\in\operatorname{T}(\varphi)$ .

Lemma 5.10.

If $(t,f),(s,e)\in\operatorname{Sp}(G,\varphi)$ are given by their splinter tables, then their product $(t,f)(s,e)$ can be represented by a splinter table. The product splinter table can be computably determined.

Proof.

Suppose that the splinter tables of $(t,f)$ and $(s,e)$ correspondingly are

(J_{1},\ldots,J_{n};g_{1},\ldots,g_{n};f)\mbox{~{}and~{}}(I_{1},\ldots,I_{m};h_{1},\ldots,h_{m};e).

Let $J:=\bigsqcup_{1\leqslant i\leqslant n}J_{i}$ and $I:=\bigsqcup_{1\leqslant j\leqslant m}I_{j}$ .

Let $(r,q):=(t,f)(s,e)$ . Then $q=fe$ , and $r=t\,\sigma(f)s$ is a step function such that for all $1\leqslant i\leqslant n$ and for all $1\leqslant j\leqslant m$

r\left(J_{i}\cap f(I_{j})\right)=g_{i}h_{j},\;r\left(J_{i}\setminus f(I)\right)=g_{i},\;r\left(f(I_{j})\setminus J\right)=h_{j}

and the identity elsewhere.

By the properties of $\operatorname{T}(\varphi)$ , the inverse of $f$ as well as $J_{i}\cap f(I_{j})$ , $J_{i}\setminus f(I)$ and $f(I_{j})\setminus J$ can be computably determined. ∎

Corollary 5.11.

Every element of $\operatorname{Sp}(G,\varphi)$ can be represented by a splinter table. ∎

Note that $(J_{1},\ldots,J_{n};g_{1},\ldots,g_{n};f)$ is a splinter table corresponding to the trivial element of $\operatorname{Sp}(G,\varphi)$ if and only if $g_{1}=\ldots=g_{n}=1$ and $f=1$ . Therefore, combining this observation and Lemma 5.10 with the fact that the word problem of $T(\varphi)$ is decidable (Corollary 4.26), we immediately get the following.

Lemma 5.12.

If the word problem for $G$ is decidable, then so is the word problem for $\operatorname{Sp}(G,\varphi)$ . ∎

5.3. Left-orders

Now let $G$ be left-ordered. We then define a left-order on $\operatorname{Sp}(G,\varphi)$ as follows, cf. [Neu60, Gla81]: let $(t,f)\in\operatorname{Sp}(G,\varphi)$ be given as a splinter table $(J_{1},\ldots,J_{n};g_{1},\ldots,g_{n};f)$ , see Corollary 5.11. If $t\not=1$ , then, without loss of generality, we let $J_{1}$ be the leftmost interval such that $t(J_{1})\not=1$ (i.e. $g_{1}\neq 1$ ). We set $(t,f)>1$ if either $f>1$ in $\operatorname{T}(\varphi)$ or if $f=1$ and $g_{1}>1$ in $G$ . As the action of $T(\varphi)$ on $\mathbb{R}$ is orientation-preserving, this defines a left-order on $\operatorname{Sp}(G,\varphi)$ .

We conclude:

Lemma 5.13.

If $G$ is left-ordered, then so is $\operatorname{Sp}(G,\varphi)$ . The order on $\operatorname{Sp}(G,\varphi)$ continues the order on $G$ . ∎

Lemma 5.14.

If $G$ is computably left-ordered, then so is $\operatorname{Sp}(G,\varphi)$ . The order on $\operatorname{Sp}(G,\varphi)$ continues the order on $G$ .

Proof.

We fix a computable left-order on $T(\varphi)$ , see Corollary 4.26. Let $(t,f)\in\operatorname{Sp}(G,\varphi)$ . First run the algorithm for the word problem, see Lemma 5.12. If $(t,f)$ represents the identity stop. Otherwise, check whether or not $f$ is positive, negative or the identity. In the first two cases, we are done. Otherwise, we can computably determine the leftmost (maximal) interval $J$ of the splinter representation of $(t,f)$ such that $t(J)\not=1$ . Then we use that the left-order on $G$ is computable to determine whether or not $t(J)$ is positive or negative. ∎

5.4. Embeddings into finitely generated groups

To conclude the proof of Theorem 5.1, we need the following result of [Dar15], see also [Dar19, Theorem 3] for more details on assertions (1)-(3).

Theorem 5.15.

Every countable group $G$ embeds into a $2$ –generated group $H$ . In addition,

(1)

if $G$ is computable, then $H$ has decidable word problem;
(2)

if $G$ is left-ordered, then $H$ is left-ordered;
(3)

if $G$ is computably left-ordered, then the left order on $H$ is computable;
(4)

the embedding of $G$ into $H$ is a Frattini embedding.

Moreover, the left-order on $H$ continues the left-order on $G$ . ∎

Here we briefly explain why the embedding from [Dar15] is a Frattini embedding.

Proof of assertion (4) of Theorem 5.15.

As it is shown in Section 2 of [Dar15], for $G=\{g_{1},g_{2},\ldots\}$ , the embedding satisfying Theorem 5.15 has the following properties: it embeds $G$ into a two generated subgroup $\langle c,s\rangle$ of the group $G\wr\langle z\rangle\wr\langle s\rangle$ , where $\langle z\rangle$ and $\langle s\rangle$ are infinite cyclic groups, such that $g_{i}$ goes to $[c,c^{s^{2^{i}-1}}]\in(G\wr\langle z\rangle)^{\langle s\rangle}$ . Moreover, the element $[c,c^{s^{2^{i}-1}}]$ , regarded as a map ${\langle s\rangle}\rightarrow G\wr\langle z\rangle$ , has support $\subseteq\{1\}$ . In addition, $[c,c^{s^{2^{i}-1}}](1)$ is a map $\langle z\rangle\rightarrow G$ such that $([c,c^{s^{2^{i}-1}}](1))(1)=g_{i}$ .

Now assume that for two elements $g,h\in G$ , their images in $\langle c,s\rangle$ are conjugate. Let $\bar{g}$ and $\bar{h}$ be the images of $g$ and $h$ in $\langle c,s\rangle$ , respectively. In particular, $\bar{g}$ and $\bar{h}$ are elements of the form $[c,c^{s^{2^{i}-1}}]$ . Let $(f,s^{n})\in\langle c,s\rangle\leq(G\wr\langle z\rangle)\wr{\langle s\rangle}$ be such that $(f,s^{n})\bar{g}(f,s^{n})^{-1}=\bar{h}$ . Then we get

f\bar{g}^{s^{n}}f^{-1}=\bar{h},

which implies that $\operatorname{supp}(f\bar{g}^{s^{n}}f^{-1})=\operatorname{supp}(\bar{g})=\{1\}$ . On the other hand,

\operatorname{supp}(f\bar{g}^{s^{n}}f^{-1})=\operatorname{supp}(\bar{g}^{s^{n}})=\{s^{-n}\}.

Therefore, $n=0$ , hence $\bar{g}(1)$ is conjugate to $\bar{h}(1)$ in $G\wr\langle z\rangle$ . Repeating this argument one more time with respect to the pair $\bar{g}(1),\bar{h}(1)\in G\wr\langle z\rangle$ and using the fact that $(\bar{g}(1))(1)=g$ and $(\bar{h}(1))(1)=h$ , we get that $g$ is conjugate to $h$ in $G$ . Since $g,h\in G$ are arbitrarily chosen elements from $G$ , we get that the embedding from [Dar15] that satisfies Theorem 5.15 is Frattini. ∎

Proof of Theorem 5.1.

By Theorem 5.15, we assume without loss of generality that $G$ is $2$ –generated.

Let $H$ be the splinter group $\operatorname{Sp}(G,\varphi)$ . Then $G$ embeds into $H$ and $H$ is finitely generated by Lemma 5.3. Moreover, $H$ is perfect by Lemma 5.4. Assertion (1) follows from Lemma 5.12. Assertion (2) follows from Lemma 5.13. Assertion (3) follows from Lemma 5.14. Assertion (4) follows from Lemma 5.7. ∎

5.5. Thompson’s Splinter group revisited

We compare Definition 5.2 with Thompson’s definition of a splinter group [Tho80, Definition 2.1].

Let $X$ be a Cantor set, whose elements are represented as infinite sequences in letters $0$ and $1$ . We note that the so called Thompson’s group $V$ is exactly the group $\operatorname{Ft}(X)$ defined in [Tho80, p. 405]. In fact, $V$ is an infinite finitely generated simple group that acts on $X$ [Tho80, Proposition 1.5, Corollary 1.9].

We note that the splinter group of [Tho80] is the subgroup of $G\wr_{X}V$ generated by $V$ and the functions $\overline{g}$ from $X$ to $G$ that take the value $g$ on all sequences starting with $01$ , and the identity elsewhere. Lemma 5.4 corresponds to [Tho80, Theorem 2.3], and Lemma 5.12 to [Tho80, Proposition 2.7].

Unfortunately, the group $V$ and, hence, the splinter group of [Tho80] are not left-orderable.

6. Embeddings of left-ordered groups

Let $J$ be a dyadic interval in $[0,1]$ . Since every left-ordered group embeds as a subgroup into $\operatorname{Homeo}^{+}(J)$ , we have the following.

Proposition 6.1.

Every countable left-ordered group $G$ embeds into a finitely generated left-ordered group $H$ . In addition, the order on $H$ continues the order on $G$ .

Proof.

Let $G$ be countable left-orderable group. Then, by Theorem 5.1, $G$ embeds into a finitely generated perfect left-orderable group $G_{1}$ . On its own turn, since $G_{1}$ is left-orderable, it embeds into $\operatorname{Homeo}^{+}\left(J\right)$ . Let $G_{2}\leq\operatorname{Homeo}^{+}\left(J\right)$ such that $G_{2}$ is isomorphic to $G_{1}$ . Let $H=T(G_{2},\varphi)$ , see Definition 3.13. By Lemmas 3.14, 3.19 and 3.20, $H$ has the required properties. ∎

We now construct an embedding as in the previous proposition, that, in addition, is Frattini and isometric (provided that $G$ is finitely generated), as required by Remark 1.1, and that has the computability properties required by Theorem 2. To achieve this, we modify the construction of Proposition 2.12 of embeddings of left-ordered groups into $\operatorname{Homeo}^{+}(J)$ .

6.1. Dyadic parts

Definition 6.2.

For any $r=2^{k}\frac{p}{q}\in\mathbb{Q}\setminus\{0\}$ , where $p$ and $q$ are odd integers, we call $\{r\}_{d}:=k$ the dyadic part of $r$ .

We observe:

Lemma 6.3.

Let $c\neq 0,\lambda,x\in\mathbb{Q}$ and $\{\lambda\}_{d}+\{x\}_{d}\neq\{c\}_{d}$ . Then $\{\lambda x+c\}_{d}=\min\{\{\lambda\}_{d}+\{x\}_{d},\{c\}_{d}\}$ . Also, $\{\lambda x\}_{d}=\{\lambda\}_{d}+\{x\}_{d}$ . ∎

Definition 6.4.

Let $I$ and $J$ be fixed intervals and $g:\mathbb{Q}_{I}\rightarrow\mathbb{Q}_{J}$ be a bijection. Then we say that $g$ is strongly permuting the dyadic parts if the following two conditions take place.

(1)

For each $m\in\mathbb{Z}$ , there exists at most one $x\in\mathbb{Q}_{I}$ such that $\{x\}_{d}=m$ and $\{g(x)\}_{d}\leq 0$ ;
(2)

If $x_{1}\neq x_{2}\in\mathbb{Q}_{I}$ and $\{x_{1}\}_{d}=\{x_{2}\}_{d}$ , then $\{g(x_{1})\}_{d}\neq\{g(x_{2})\}_{d}$ .

If $g$ is a bijection from $I$ to $J$ , when we say that $g$ is strongly permuting the dyadic parts if it maps rational points to rational points and its restriction $g\mid_{\mathbb{Q}_{I}}:\mathbb{Q}_{I}\rightarrow\mathbb{Q}_{J}$ satisfies Definition 6.4.

Remark 6.5.

If $g:\mathbb{Q}_{I}\rightarrow\mathbb{Q}_{J}$ is strongly permuting the dyadic parts, then, for each $m\in\mathbb{Z}$ , the set $\left\{\{g(x)\}_{d}\mid x\in\mathbb{Q}_{I},~{}\{x\}_{d}=m\right\}$ is unbounded from above.

Let us consider, for $0<i\leqslant n$ ,

•

bijective dyadic maps $f_{i}:I_{i}\to J_{i}$ such that $f_{i}(x)=\lambda_{i}x+c_{i}$ , where $\lambda_{i}$ is a power of $2$ and, for all $i\notin\{0,n\}$ , $c_{i}\not=0$ ; and
•

bijective maps $g_{i}:J_{i}\to I_{i-1}$ , whose restriction to $\mathbb{Q}_{J_{i}}$ strongly permutes the dyadic parts.

Lemma 6.6.

If $\Lambda=g_{1}f_{1}g_{2}f_{2}\ldots g_{n}f_{n}$ , then, for large enough $N\in\mathbb{N}$ , the set

\left\{\{\Lambda(x)\}_{d}\mid x\in\mathbb{Q}_{I_{n}},~{}\{x\}_{d}=N\right\}

is unbounded from above. In particular, $\Lambda\not=id$ .

Proof.

We will prove the lemma by induction on $n$ .

Let $n=1$ . Then $\Lambda(x)=g_{1}(\lambda_{1}x+c_{1})$ . If $c_{1}=0$ or $N>\{c_{1}\}_{d}$ and $\{x_{1}\}_{d}=\{x_{2}\}_{d}=N$ , then, by Lemma 6.3, $\{\lambda_{1}x_{1}+c_{1}\}_{d}=\{\lambda_{1}x_{2}+c_{1}\}_{d}$ . The statement now follows as $g_{1}$ strongly permutes the dyadic parts (see Remark 6.5).

Next let $n>1$ . Then $\Lambda(x)=g_{1}(\lambda_{1}\Lambda_{2}(x)+c_{1})$ , where $\Lambda_{2}=g_{2}f_{2}\ldots g_{n}f_{n}$ and $c_{1}\neq 0$ . By inductive assumption, for any large enough $N$ , there exists a sequence $\{x_{i}\}_{i=1}^{\infty}$ such that $\{x_{i}\}_{d}=N$ and $\lim_{i\rightarrow\infty}\{\Lambda_{2}(x_{i})\}_{d}=\infty$ . By Lemma 6.3, for any large enough index $i$ , $\{\lambda_{1}\Lambda_{2}(x_{i})+c_{1}\}_{d}=\{c_{1}\}_{d}$ , hence, the lemma follows as $g_{1}$ strongly permutes the dyadic parts. ∎

6.2. The modified dynamical realization

Let $J$ be a fixed closed interval in $\mathbb{R}$ with non-empty interior. We prove:

Proposition 6.7.

Let $G$ be a countable group.

If $G$ is left-orderable, then there is an embedding $\Psi:G\hookrightarrow\operatorname{Homeo}^{+}(J)$ such that, for all $g\in G\setminus\{1\}$ , the map $\Psi(g):J\rightarrow J$ is strongly permuting the dyadic parts and does not fix any rational interior point of $J$ .

If $G$ is computably left-orderable, then, in addition, all the maps $\Psi(g)$ can be taken to be computable.

As in the proof of Proposition 2.12, we fix a recursive enumeration $\mathbb{Q}_{J}=\{q_{0},q_{1},\ldots\}$ such that the natural order on $\mathbb{Q}_{J}$ is computable with respect to this enumeration.

We first strengthen Lemma 2.10 that states that there is an order preserving bijection $\Phi:G\to\mathbb{Q}_{J}$ .

Lemma 6.8.

If $G$ is enumerated and densly left-ordered, then there is an enumeration $G=\{g_{i_{1}},g_{i_{2}},\ldots\}$ and an order preserving bijection $\Theta:G\to\mathbb{Q}_{J}$ such that

(1)

For odd $j$ , $\{\Theta(g_{i_{j}})\}_{d}\in\mathbb{N}$ and $\{\Theta(g_{i_{j}})\}_{d}\not\in\left\{\,\{\Theta(g_{i_{k}})\}_{d}\mid 1\leqslant k<j\right\}$ ;
(2)

For even $j$ , $g_{i_{j}}\not\in\left\{g_{i_{k}}g_{i_{l}}^{-1}g_{i_{m}}\mid 1\leqslant k,l,m<j\right\}$ ;
(3)

If $G$ is computably left-ordered, then the enumeration $G=\{g_{i_{1}},g_{i_{2}},\ldots\}$ and the map $j\mapsto\Theta(g_{i_{j}})$ are computable.

Proof.

Let $G=\{1=g_{0},g_{1},g_{2},\ldots\}$ and $\mathbb{Q}_{J}=\{0=r_{0},r_{1},r_{2},\ldots\}$ be fixed (recursive) enumerations. We define $\Theta:g_{0}\mapsto r_{0}$ and $\Theta:g_{i_{j}}\mapsto r_{i_{j}}$ , where $(g_{i_{1}},g_{i_{2}},\ldots)$ and $(r_{i_{1}},r_{i_{2}},\ldots)$ are permutations of $(g_{1},g_{2},\ldots)$ and $(r_{1},r_{2},\ldots)$ , respectively, defined recursively as follows.

Step $2n+1$ . Let $G_{2n}=\{g_{i_{1}},\ldots,g_{i_{2n}}\}$ and $Q_{2n}=\{r_{i_{1}},\ldots,r_{i_{2n}}\}$ be already defined. Let us define $g_{i_{2n+1}}$ as the element of the smallest index that is not in $G_{2n}$ . Suppose that $g_{i_{s}}<g_{i_{2n+1}}<g_{i_{t}}$ and that no element from $G_{2n}$ is in between $g_{i_{s}}$ and $g_{i_{t}}$ . Then define $r_{i_{2n+1}}\in\mathbb{Q}_{J}$ to be of the smallest index such that

(O1)

$r_{i_{2n+1}}\notin Q_{2n}$ and $r_{i_{s}}<r_{i_{2n+1}}<r_{i_{t}}$ ,
(O2)

$\{r_{i_{2n+1}}\}_{d}\in\mathbb{N}$ and $\{r_{i_{2n+1}}\}_{d}\notin\{\{r_{i_{j}}\}_{d}\mid 1\leq j\leq 2n\}$ .

Step $2n+2$ . Let $G_{2n+1}:=\{g_{i_{1}},\ldots,g_{i_{2n+1}}\}$ and $Q_{2n+1}=\{r_{i_{1}},\ldots,r_{i_{2n+1}}\}$ be already defined. Let us define $r_{i_{2n+2}}$ as the rational of the smallest index that is not in $Q_{2n+1}$ . Suppose that $r_{i_{s}}<r_{i_{2n+2}}<r_{i_{t}}$ and that no element from $Q_{2n+1}$ is in between $r_{i_{s}}$ and $r_{i_{t}}$ . Then let us define $g_{i_{2n+2}}\in G$ as the element of the smallest index such that

(E1)

$g_{i_{2n+2}}\notin G_{2n+1}$ and $g_{i_{s}}<g_{i_{2n+2}}<g_{i_{t}}$ , and
(E2)

$g_{i_{2n+2}}\notin\{g_{i_{k}}g_{i_{l}}^{-1}g_{i_{m}}\mid 1\leq k,l,m\leq 2n+1\}$ .

The bijection $\Theta$ defined this way is order preserving by (O1) and (E1). Condition (O2) yields assertion (1), and (E2) yields assertion (2). Finally, as the procedure is algorithmic, we also obtain assertion (3). ∎

Proof of Proposition 6.7.

By Remark 2.11, we may assume that the order on $G$ is dense. Let the enumeration $G=\{g_{0},g_{1},\ldots\}$ and $\Theta:G\to\mathbb{Q}_{J}$ satisfy the assertions of Lemma 6.8. Then $\Theta:G\to\mathbb{Q}_{J}$ induces the embedding $\rho_{G}^{\Theta}:G\hookrightarrow\operatorname{Homeo}^{+}(J)$ according to $\rho_{G}^{\Theta}(g)(\Theta(h))=\Theta(gh)$ for $g,h\in G$ . Denote $\Psi=\rho_{G}^{\Theta}$ . Let $h\in G\setminus\{1\}$ . By Lemmas 2.14 and 2.15, we only need to show that $\Psi(h)$ is strongly permuting the dyadic parts.

To this end, we enumerate $\mathbb{Q}_{J}$ such that $\Theta(g_{i})=r_{i}$ and let $r_{i}\neq r_{j}\in\mathbb{Q}_{J}$ . We define $r_{k}=\Psi(h)(r_{i})=\Theta(hg_{i})$ and $r_{l}=\Psi(h)(r_{j})=\Theta(hg_{j})$ , so that $g_{k}=hg_{i}$ and $g_{l}=hg_{j}$ .

We first show property (1) of Definition 6.4. By contradiction, assume that there exist $i\neq j$ such that $\{r_{i}\}_{d}=\{r_{j}\}_{d}$ and $\{r_{k}\}_{d},\{r_{l}\}_{d}\notin\mathbb{N}$ . Since $\{r_{k}\}_{d},\{r_{l}\}_{d}\notin\mathbb{N}$ , the indices $k$ and $l$ are even. Then, since $g_{k}=hg_{i}=(hg_{j})(g_{j}^{-1})(g_{i})$ and $g_{l}=hg_{j}=(hg_{i})(g_{i}^{-1})(g_{j})$ , by (2) of Lemma 6.8, the largest index is among $i$ or $j$ . Let $j>i$ . Then, since $\{r_{i}\}_{d}=\{r_{j}\}_{d}$ , we get the index $j$ is even. Since $g_{j}=g_{i}(hg_{i})^{-1}(hg_{j})$ , again by (2) of Lemma 6.8, we get a contradiction, which yields the claim.

Next, we prove property (2) of Definition 6.4. By contradiction, assume that there exist $r_{i}\neq r_{j}\in\mathbb{Q}_{J}$ such that $\{r_{i}\}_{d}=\{r_{j}\}_{d}$ and suppose that $\{r_{l}\}_{d}=\{r_{k}\}_{d}$ . Without loss of generality, $l>i,j,k$ (if, say, $j>i,k,l$ , then instead of $h$ we could consider $h^{-1}$ ). Then, since $\{r_{k}\}_{d}=\{r_{l}\}_{d}$ , by (1) of Lemma 6.8, $l$ has to be even. Therefore, since $\Theta(hg_{j})=r_{l}$ and $l$ is even, by (2) of Lemma 6.8, $hg_{j}\not\in\left\{g_{m}g_{n}^{-1}g_{p}\mid 1\leqslant m,n,p<j\right\}$ . On the other hand, since $l>i,j,k$ , we get $hg_{j}=(hg_{i})(g_{i}^{-1})(g_{j})$ , a contradiction.

This completes the proof of Proposition 6.7. ∎

6.3. The embedding theorems

Let $G$ be countable left-orderable group. Then, by Theorem 5.1, $G$ embeds into a finitely generated perfect left-orderable group $G_{1}$ . Moreover, this embedding is a Frattini embedding.

Let $J:=[1/4,1/2]$ . Since $G_{1}$ is left-orderable, there is an embedding $\Psi:G_{1}\hookrightarrow\operatorname{Homeo}^{+}\left(J\right)$ . Let $G_{2}=\Psi(G_{1})$ . By Proposition 6.7, we can assume that the non-trivial elements of $G_{2}\subseteq\operatorname{Homeo}^{+}\left(J\right)$ strongly permute the dyadic parts and do not fix any rational interior point of $J$ .

For the definition of $G_{2}$ –dyadic maps, see Definition 4.6.

Lemma 6.9.

Let $\Lambda$ be a $G_{2}$ –dyadic map. If $G_{2}$ has decidable word problem, then there is an algorithm to decide whether or not $\Lambda=id.$

Proof.

Let $n>0$ and, for all $0\leqslant i\leqslant n$ , let ${J}_{i}\subset J$ and let $g_{i}:{J_{i}}\rightarrow{I_{i-1}}$ be the restriction of an element of $G_{2}$ such that $g_{i}\not=id$ . Moreover, let $f_{i}:{{I}_{i}}\rightarrow{{J}_{i}}$ , given by $f_{i}(x)=\lambda_{i}x+c_{i}$ , be dyadic maps such that $f_{i}\not=id$ .

Since, for all $0<i<n$ , $J_{i}\subset[1/4,1/2]$ and, by definition, $\lambda_{i}$ is a power of $2$ , we get that $c_{i}\not=0$ for $0<i<n$ . Then, by Lemma 4.25, $\Lambda:=g_{1}f_{1}g_{2}f_{2}\ldots g_{n}f_{n}\not=id$ .

If $n=1$ and $f_{1}=id$ , then $\Lambda=g_{1}\in G$ . Then we decide using the algorithm for the word problem in $G$ . ∎

Combining Lemmas 5.6 and 6.9, we also conclude the following.

Lemma 6.10.

The embedding $G_{1}\hookrightarrow T(G_{2},\varphi)$ is isometric.∎

Lemma 6.11.

The embedding $G_{1}\hookrightarrow T(G_{2},\varphi)$ is a Frattini embedding.

Proof.

Let $h,g\in G_{2}$ and $t\in T(G_{2},\varphi)$ . We assume that $ht^{-1}gt=1$ .

We represent $t$ by a canonical chart representation $(C_{i}\times I_{i},C_{j}\times J_{i},t_{i})$ such that $\bigcup_{i}J_{i}=[0,1]$ ; and represent $t^{-1}$ by $(C_{i}\times J_{i},C_{i}\times I_{i},t_{i})$ . We recall that $t_{i}(I_{i})=J_{i}$ .

Let $k$ be a index such that $1/2$ is in the closure of $J_{k}$ and such that (after applying a chart refinement if necessary) $J_{k}\subseteq J$ . As $g$ is fixing $1/2$ , there is $J_{k}^{\prime}\subseteq J_{k}$ such that $g(J_{k}^{\prime})\subseteq J_{k}$ and such that $1/2$ is in the closure of $J_{k}^{\prime}$ . We let $I_{k}^{\prime}=t_{k}^{-1}(J_{k}^{\prime})$ and $I_{k}^{\prime\prime}=t_{k}^{-1}gt_{k}(I_{k}^{\prime})$ .

Then the triple $(C\times I_{k}^{\prime},C\times I_{k}^{\prime\prime},t_{k}^{-1}gt_{k})$ is in a chart representation of $t^{-1}gt$ . Up to applying the algorithm of Lemma 4.20 to this chart representation, we may assume that $I_{k}^{\prime\prime}$ is in $[0,1]$ . Moreover, up to applying a chart refinement if necessary, we may assume that either $I_{k}^{\prime\prime}\cap\mathfrak{J}$ is empty or consists of one point ( $1/4$ or $1/2$ ), or $I_{k}^{\prime\prime}\subseteq\mathfrak{J}$ .

If $I_{k}^{\prime\prime}\cap J$ is empty or consists of one point, then $(C\times I_{k}^{\prime},C\times I_{k}^{\prime\prime},t_{k}^{-1}gt_{k})$ is in a chart representation of $ht^{-1}gt$ . Thus $t_{k}^{-1}gt_{k}=id$ on $I_{k}^{\prime}$ by Lemma 4.24. This implies that $g$ acts as the identity on $J_{k}^{\prime}$ . Since non-trivial elements of $G_{2}$ do not fix any rational interior points of $J$ , the element $g=1$ .

Otherwise, the triple $(C\times I_{k}^{\prime},C\times h(I_{k}^{\prime\prime}),ht_{k}^{-1}gt_{k})$ is in a chart representation of $ht^{-1}gt$ . Thus $ht_{k}^{-1}gt_{k}=id$ on $I_{k}^{\prime}$ by Lemma 4.24. Then $h(I_{k}^{\prime\prime})=I_{k}^{\prime}$ . This is only possible if $I_{k}^{\prime}\subseteq J$ . But then Lemma 6.9, implies that $t_{k}$ acts as an element of $G_{2}$ . Since non-trivial elements of $G_{2}$ do not fix any rational interior points of $J$ , this implies that $g$ and $h$ are conjugate in $G_{1}$ . ∎

We can now conclude Theorems 1, 2 and 4.

Proof of Theorems 1, 2 and Remark 1.1.

We let $H=T(G_{2},\varphi)$ .

The group $H$ is finitely generated left-orderable and simple by Lemmas 3.14, 3.20 and 3.19. By construction, $G$ embeds into $H$ , and the order on $H$ extends the order on $G$ . Moreover, by Lemma 6.11, the embedding of $G$ is a Frattini embedding.

If $G$ is computably left-ordered, we may in addition assume that $G_{1}$ is computably left-ordered, see Theorem 5.1. By Proposition 6.7, for all $g\in G_{1}$ , $\Psi(g)$ is computable. Therefore, by Lemma 2.9, the positive cone of $H$ is recursively enumerable. Moreover, by Lemma 6.9 and Lemma 4.25, the group $H$ has decidable word problem. By Lemma 2.9, the left-order on $H$ is computable. ∎

Proof of Theorem 4.

Let $G$ be finitely generated left-orderable group with a recursively enumerated positive cone. If $G$ has decidable word problem, then the left-order on $G$ is computable by Lemma 2.9. Then Theorem 2 implies that $G$ embeds into a finitely generated computably left-ordered simple group $H$ . In particular, the word problem in $H$ is decidable. Thus $H$ can be defined by a recursively enumerable set of relations. By [BG09, Theorem D], $H$ embeds into a left-orderable finitely presented group.

On the other hand, if $H$ is a finitely generated simple subgroup of a finitely presented group, then it has decidable word problem (see [LS77, Theorem 3.6]). Therefore, $G$ has decidable word problem as well. ∎

7. Embeddings of computable groups

In this section we prove Theorem 3, the isometric version of Thompson’s theorem [Tho80]. In Appendix we present yet another proof of Theorem 3 that, using the setting of our paper, mimics the original idea of [Tho80].

Theorem 7.1.

Every computable group $G$ Frattini embeds into a finitely generated simple group $H$ with decidable word problem. If $G$ is finitely generated, then the embedding is isometric.

Remark 7.2.

The original statement [Tho80] is for finitely generated groups, but finite generation can be replaced by computability of $G$ due to Theorem 5.15.

7.1. The embedding construction

Let $G$ be a computable group. By Theorem 5.1, $G$ embeds into a finitely generated perfect group $G_{1}$ with decidable word problem (if $G$ is finitely generated, this claim also follows from [Tho80, §2]).

Let $G_{1}=\{g^{(1)},g^{(2)},\ldots\}$ be enumerated so that $\mathfrak{m}:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$ , defined as $\mathfrak{m}((i,j))=k$ if $g^{(i)}g^{(j)}=g^{(k)}$ , is computable. By Remark 2.3 the existence of such $\mathfrak{m}$ is equivalent to decidability of the word problem.

Let us fix two recursively enumerated recursive sets of dyadic numbers $\{x_{1},x_{2},\ldots\}$ and $\{y_{1},y_{2},\ldots\}$ such that the following takes place

(1)

$0<x_{1}<y_{1}<x_{2}<y_{2}<\ldots<\frac{1}{3}$ ,
(2)

$x_{i}$ and $y_{i}$ are of the form $\frac{m}{2^{n}}$ and $\frac{m+1}{2^{n}}$ , respectively,
(3)

$\lim_{i\rightarrow\infty}x_{i}=\frac{1}{3}$ .

Let us denote $D_{i}=[x_{i},y_{i}]$ and $\mathfrak{J}=(0,\frac{1}{3}]\supset\sqcup_{i=1}^{\infty}D_{i}$ .

For every $l\in\mathbb{N}$ , let $\xi_{l}:\mathfrak{J}\rightarrow\mathfrak{J}$ be such that, for every $k\in\mathbb{N}$ , it is an affine map from $D_{k}$ onto $D_{\mathfrak{m}(l,k)}$ and that is identity outside of $\cup_{i=1}^{\infty}D_{i}$ . In particular, the map $\xi_{l}:D_{k}\rightarrow D_{\mathfrak{m}(l,k)}$ is dyadic.

Remark 7.3.

The maps $\xi_{l}:\mathfrak{J}\rightarrow\mathfrak{J}$ , $l\in\mathbb{N}$ , are computable and continuous at non-dyadic points. Also, they have finitely many (dyadic) breakpoints outside of any open neighborhood of $1/3$ .

Let us define $\lambda:G_{1}\rightarrow\mathcal{C}(\mathfrak{J})$ by $\lambda(g^{(l)})=\xi_{l}$ , for all $l\in\mathbb{N}$ .

Remark 7.4.

The map $\lambda$ is an embedding of $G_{1}$ into computable maps in $\mathcal{C}(\mathfrak{J})$ .

Let $\Lambda=g_{1}f_{1}g_{2}f_{2}\ldots g_{n}f_{n}:\mathcal{I}_{n}\rightarrow\mathcal{I}_{0}$ , where $f_{i}:{\mathcal{I}_{i}}\rightarrow{\mathcal{J}_{i}}$ and $g_{i}:\mathcal{J}_{i}\rightarrow\mathcal{I}_{i-1}$ , be a $G_{2}$ -dyadic map as in Definition 4.6. Recall that in particular we have $\mathcal{J}_{i}\subseteq\mathfrak{J}=(0,\frac{1}{3}]$ for $1\leq i\leq n$ . We say that $\Lambda$ is a special $G_{2}$ -dyadic map if for each $1\leq i\leq n$ we have $1/3\in\overline{\mathcal{J}}_{i}$ (closure of $\mathcal{J}_{i}$ ). Correspondingly, we say that a chart of type (II), see Definition 4.8, is special if the local representation in this chart is of the form $f_{0}\Lambda$ , where $\Lambda$ is a special $G_{2}$ –dyadic map.

The following lemma is a direct consequence of Remark 7.3 and of the fact that the maps $f_{i}$ , $g_{i}$ , $1\leq i\leq n$ , are computable.

Lemma 7.5.

There exist a finite collection of intervals $K_{1},K_{2},\ldots,K_{s}\subseteq(0,\frac{1}{3}]$ such that $\Lambda|_{K_{i}\cap\mathcal{I}_{0}}$ is a special $G_{2}$ -dyadic map. Moreover, such intervals $K_{1},K_{2},\ldots,K_{s}$ can be found algorithmically. ∎

Lemma 7.6.

If $h:I\rightarrow J$ is a surjective dyadic map such that $1/3$ is in the closures of $I$ and ${J}$ , and ${I},{J}\subseteq(0,\frac{1}{3}]$ , then $h$ is the identity map.

Proof.

The lemma follows from the fact that $\frac{1}{3}$ is non-dyadic. ∎

By Lemma 7.6, we have:

Corollary 7.7.

Special local representations are of the form $f_{0}g_{1}f_{1}$ . In particular, if a special $G_{2}$ -dyadic map or a special chart of type (II) fixes $1/3$ , then it acts as an element of $G_{2}$ . ∎

Since the word problem for $G_{2}$ is decidable, this implies that there exists an algorithm that decides whether or not a special $G_{2}$ -dyadic map represents the identity map. This, combined with Lemmas 7.5 and 4.25, leads to the following corollary.

Corollary 7.8.

The word problem in $T(G_{2},\varphi)$ is decidable. ∎

7.2. Frattini property

The embedding $G\hookrightarrow T(G_{2},\varphi)$ is Frattini.

Lemma 7.9.

The embedding $G_{1}\hookrightarrow T(G_{2},\varphi)$ is a Frattini embedding.

We adapt the proof of Lemma 6.11.

Proof.

Let $h,g\in G_{2}$ and $t\in T(G_{2},\varphi)$ . We assume that $ht^{-1}gt=1$ .

We represent $t$ by a canonical chart representation $\{(C_{i}\times I_{i},C_{j}\times J_{i},t_{i})\}$ such that $\bigcup_{i}J_{i}=[0,1]$ ; and represent $t^{-1}$ by $\{(C_{i}\times J_{i},C_{i}\times I_{i},t_{i}^{-1})\}$ . We recall that $t_{i}(I_{i})=J_{i}$ .

Let $k$ be a index such that $1/3$ is in the closure of $J_{k}$ and such that (after applying a chart refinement if necessary) $J_{k}\subseteq\mathfrak{J}$ . As $g$ is fixing $1/3$ , there is $J_{k}^{\prime}\subseteq J_{k}$ such that $g(J_{k}^{\prime})\subseteq J_{k}$ and such that $1/3$ is in the closure of $J_{k}^{\prime}$ . We let $I_{k}^{\prime}=t_{k}^{-1}(J_{k}^{\prime})$ and $I_{k}^{\prime\prime}=t_{k}^{-1}gt_{k}(I_{k}^{\prime})$ .

Then the triple $(C\times I_{k}^{\prime},C\times I_{k}^{\prime\prime},t_{k}^{-1}gt_{k})$ is in a chart representation of $t^{-1}gt$ . Up to applying the algorithm of Lemma 4.20 to this chart representation, we may assume that $I_{k}^{\prime\prime}$ is in $[0,1]$ . Moreover, up to applying a chart refinement if necessary, we may assume that either $I_{k}^{\prime\prime}\cap\mathfrak{J}$ is empty or consists of one point $1/3$ , or $I_{k}^{\prime\prime}\subseteq\mathfrak{J}$ .

If $I_{k}^{\prime\prime}\cap\mathfrak{J}$ is empty or consists of one point $1/3$ , then $(C\times I_{k}^{\prime},C\times I_{k}^{\prime\prime},t_{k}^{-1}gt_{k})$ is in a chart representation of $ht^{-1}gt$ . Thus $t_{k}^{-1}gt_{k}=id$ on $I_{k}^{\prime}$ by Lemma 4.24. This implies that $g$ acts as the identity on $J_{k}^{\prime}$ . As $1/3$ is in the closure of $J_{k}^{\prime}$ , this implies that $g=1$ .

Otherwise, the triple $(C\times I_{k}^{\prime},C\times h(I_{k}^{\prime\prime}),ht_{k}^{-1}gt_{k})$ is in a chart representation of $ht^{-1}gt$ . Thus $ht_{k}^{-1}gt_{k}=id$ on $I_{k}^{\prime}$ by Lemma 4.24. But then $t_{k}ht_{k}^{-1}g:J_{k}^{\prime}\to J_{k}^{\prime}$ has to be the identity as well. As $g$ is fixing $1/3$ , $t_{k}ht_{k}^{-1}$ has to fix $1/3$ .

If $t_{k}$ was dyadic (i.e. of type (I)), it would have to fix $1/3$ , so that $t_{k}=id$ by Lemma 7.6. If $t_{k}$ is of type (II), we may assume that $t_{k}$ is special, see Lemma 7.5. Then, by Corollary 7.7, $t_{k}$ acts as an element of $G_{2}$ .

Thus $g$ and $h$ are conjugated by elements of $G_{2}$ . This implies that $g$ and $h$ are conjugated in $G_{1}$ . ∎

Combining Lemma 7.9 with Lemma 5.7, we obtain:

Corollary 7.10.

The embedding $G\hookrightarrow T(G_{2},\varphi)$ is Frattini. ∎

Lemma 7.11.

The embedding $G_{1}\hookrightarrow T(G_{2},\varphi)$ is an isometric embedding.

Proof.

We fix a finite generating set $X$ for $G_{1}$ , and denote the generating set of $T(\varphi)$ given by Lemma 3.7 by $Y$ . We denote the union of the bijective images of $X$ and $Y$ in $T(G_{2},\varphi)$ by $Z$ and recall that $Z$ generates $T(G_{2},\varphi)$ . We assume that all generating sets are symmetric. We denote by $|.|_{A}$ the word metric with respect to the generating set $A$ .

Let $g\in G_{2}$ and let $t=z_{1}\cdots z_{m}$ be a reduced word in the alphabet $Z$ that represents $g^{-1}\in T(G_{2},\Phi)$ , so that $tg=1$ . In addition, we assume that $m=|g|_{Z}$ . We represent every generator $z_{i}$ by a canonical chart representation, see Lemma 4.15. Lemma 4.23 then gives a canonical chart representation $(C_{i}\times I_{i},C_{i}\times J_{i},t_{i})$ for $t$ . Recall that the maps $t_{i}$ are compositions $t_{i}=h_{1}\cdots h_{m_{i}}$ , where each map $h_{j}$ is a local representation in the canonical chart representation of a generator in $Z$ and $m_{i}\leqslant m$ . In addition, up to applying the algorithm of Lemma 4.20 to this chart representation of $t$ , we may assume that $\bigcup I_{i}=[0,1]$ .

Let $I_{k}$ be an interval such that $1/3$ is in the closure of $I_{k}$ and such that (after applying a chart refinement if necessary) $I_{k}\subseteq\mathfrak{J}$ .

Then $(C_{i}\times g^{-1}(I_{k}),C_{i}\times J_{i},t_{i}g)$ is in a canonical chart representation of the identity. By Lemma 4.24, $t_{i}g$ is the identity mapping. In particular, $g^{-1}(I_{k})=J_{i}$ , so that $J_{i}\subseteq\mathfrak{J}$ and $1/3$ is in the closure of $J_{i}$ .

We note that $t_{i}$ is not dyadic (i.e. of type (I)) by Lemma 7.6. If $t_{i}=fg_{1}f_{1}\cdots g_{n}f_{n}$ is a chart of type (II), then, by Lemma 7.5, we may assume that $t_{i}$ is special. Thus $t_{i}=g_{1}\cdots g_{n}\in G_{2}$ (Lemma 7.6), where $n\leqslant m_{i}\leqslant m$ .

Thus we may assume that $t_{i}=x_{j_{1}}\cdots x_{j_{m_{i}}}\in G_{2}$ . Then $|g|_{X}\leqslant m_{i}\leqslant m=|g|_{Z}$ . We conclude that the embedding is isometric. ∎

Combining Lemma 7.11 with Lemma 5.6, we obtain:

Corollary 7.12.

If $G$ is finitely generated, then the embedding $G\hookrightarrow T(G_{2},\varphi)$ is isometric. ∎

Proof of Theorem 7.1.

The simplicity of $T(G_{2},\varphi)$ follows from Lemma 3.19. From Corollary 7.8, the word problem in $T(G_{2},\varphi)$ is decidable provided that it is decidable in $G_{2}$ . By Corollary 7.10, the embedding $G\hookrightarrow T(G_{2},\varphi)$ is Frattini. By Corollary 7.12, it is an isometric embedding provided that $G$ is finitely generated. Therefore, the embedding $G\hookrightarrow T(G_{2},\varphi)$ satisfies Theorem 7.1. ∎

Appendix A Thompson’s embedding revisited

Here we adapt the original embedding construction of [Tho80] to the setting of our paper and note that, in addition, it is an isometric embedding.

Theorem A.1.

Every computable group $G$ Frattini embeds into a finitely generated simple group $H$ with decidable word problem. Moreover, if $G$ is finitely generated, the embedding is isometric.

Remark A.2.

The original statement [Tho80] is for finitely generated groups, but finite generation can be replaced by computability of $G$ due to Theorem 5.15.

A.1. The embedding construction

Let $G_{1}=\{g_{1},g_{2},\ldots\}$ be enumerated so that $\mathfrak{m}:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$ , defined as $\mathfrak{m}((i,j))=k$ if $g_{i}g_{j}=g_{k}$ , is computable. By Remark 2.3 the existence of $\mathfrak{m}$ is equivalent to decidability of the word problem.

Let $J=[\frac{1}{2},1)$ . For strictly positive $k\in\mathbb{N}$ , let

I_{k}:=\left[\frac{2^{k}-1}{2^{k}},\frac{2^{k}-1}{2^{k}}+\frac{1}{2^{2k}}\right).

We observe that any two such intervals are disjoint.

We denote by $I^{l}_{k}$ the left half of the interval, and by $I^{r}_{k}$ the right half, so that

I^{l}_{k}=\left[\frac{2^{k}-1}{2^{k}},\frac{2^{k}-1}{2^{k}}+\frac{1}{2^{2k+1}}\right)\hbox{ and }I^{r}_{k}=\left[\frac{2^{k}-1}{2^{k}}+\frac{1}{2^{2k+1}},\frac{2^{k}-1}{2^{k}}+\frac{1}{2^{2k}}\right).

For every $l\in\mathbb{N}$ , let $\xi_{l}:J\rightarrow J$ be the piecewise homeomorphism, whose pieces are dyadic, and that, for every $k\in\mathbb{N}$ , maps $I_{k}^{r}$ onto $I_{\mathfrak{m}(l,k)}^{r}$ and that is the identity map elsewhere on $J$ .

Let us define $\lambda:G_{1}\rightarrow\mathcal{C}(J)$ by $\lambda(g_{l})=\xi_{l}$ , for all $l\in\mathbb{N}$ .

Remark A.3.

The map $\lambda$ is an embedding of $G_{1}$ into computable maps in $\mathcal{C}(J)$ .

Remark A.4.

If $\lambda(g_{l})$ is fixing a right half $I^{r}_{k}$ , then $g_{l}=1$ . Indeed, then $\mathfrak{m}(l,k)=k$ , so that $g_{l}g_{k}=g_{k}$ .

A.2. $G_{2}$ –dyadic maps

Let $G_{2}=\lambda(G_{1})$ . We study $G_{2}$ –dyadic maps, see Definition 4.6.

Let $J^{\prime}\subset J$ be an interval such that the closure of $J^{\prime}$ contains 1. We want to prove:

Lemma A.5.

There is an algorithm to decide that a $G_{2}$ –dyadic map $\Lambda:J^{\prime}\to J^{\prime}$ is equal to the identity.

Remark A.6.

Our definition of $\lambda$ follows the construction in [Tho80, §3]. The main arguments to prove Lemma A.5, cf. Lemma A.9, A.10, A.11 and A.13 below, are essentially those of [Tho80, §3].

Remark A.7.

We assume that the closure of $I_{n},\ldots,I_{0}$ , and $J_{n},\ldots,J_{0}$ of Definition 4.6 contains $1$ . This is no restriction in generality.

Indeed, if $\Lambda:g_{1}f_{1}\cdots g_{n}f_{n}$ and $I_{i+1}$ (equivalently, $J_{i}$ ) does not contain $1$ , then $g_{i}:J_{i}\to I_{i+1}$ has only finitely many dyadic pieces on $I_{i}$ . Therefore, a finite sequence of chart subdivisions at the breakpoints of $g_{i}$ on $I_{i}$ transforms $f_{i+1}g_{i}f_{i}$ into a finite number of dyadic maps. Thus, we can algorithmically split $\Lambda$ into a finite number of $G$ -dyadic maps of $<n$ factors.1

Lemma A.8.

Let $\Lambda=g_{n}f_{n}\cdots g_{1}f_{1}:J^{\prime}\to J^{\prime}$ be a $G_{2}$ –dyadic map. Then all dyadic factors $f_{i}$ of $\Lambda$ fix $1$ .

Proof.

By contradiction, let $f=f_{i}$ be a dyadic map such that $f(1)\not=1$ . Up to inverting $\Lambda$ , $f(1)>1$ . This contradicts the definition of $G_{2}$ –dyadic maps, Definition 4.6. ∎

For $n\in\mathbb{Z}$ , we write $s_{n}(x):=2^{-n}x+(1-2^{-n}).$ All dyadic maps that fix $1$ are of this form. Note that $s_{n+m}=s_{n}\circ s_{m}$ . We call $|n|$ the degree of $s_{n}$ .

Lemma A.9.

Let $n\not=0$ , and let $g\in G_{2}$ . Then, for all $k>|n|$ , $gs_{n}$ and $s_{n}$ are equal on $I^{r}_{k}$ . Moreover, $s_{n}g$ acts as the identity on at most finitely many $I_{k}^{r}$ .

Proof.

Let $n>0$ and $k>n$ . Direct computations show that

s_{-n}(I^{r}_{k})=\left[\frac{2^{k-n}-1}{2^{k-n}}+\frac{1}{2^{2k-n+1}},\frac{2^{k-n}-1}{2^{k-n}}+\frac{1}{2^{2k-n}}\right)\subset I^{l}_{k-n}.

Since, by definition, $g$ acts trivially on $I^{l}_{k-n}$ , we get $gs_{-n}$ coincides with $s_{-n}$ on $I^{r}_{k}$ .

Similarly, $I^{r}_{k}\subset s_{n}(I^{l}_{k-n})$ , so that $s_{n}(I_{k-n}^{r})$ does not intersect with $I_{l}^{r}$ , for any $l>0$ . Thus, by definition, $g$ acts trivially on $s_{n}(I_{k-n}^{r})$ , and $gs_{n}$ coincides with $s_{n}$ on $I^{r}_{k-n}$ .

In addition, as $g$ permutes the intervals $I_{k}^{r}$ , $s_{n}g$ acts as the identity on at most finitely many $I_{k}^{r}$ .

∎

Let $m>0$ and for all $1\leqslant i\leqslant m$ , let $g_{i}\not=1$ in $G_{2}$ , and $n_{i}\not=0$ in $\mathbb{N}$ . Let us fix

\Lambda=g_{m}s_{n_{m}}\cdots g_{1}s_{n_{1}}

to be a $G_{2}$ –dyadic map as in Lemma A.5. Let $S_{0}=id$ , $S_{1}=s_{n_{1}}$ , and, recursively, $S_{i}=s_{n_{i}}S_{i-1}$ .

Lemma A.10.

If, for all $i<m$ , $S_{i}\not=id$ and $k$ is strictly larger than the degree of $S_{i}$ , then $\Lambda$ acts as $g_{m}S_{m}$ on $I_{k}^{r}$ . In particular, $\Lambda\not=id$ .

Proof.

Let $k$ be strictly larger than the degree of $S_{i}$ , for all $i<m$ . By Lemma A.9, as $k>|n_{1}|$ , $g_{1}s_{n_{1}}$ equals to $s_{n_{1}}$ on $I^{r}_{k}$ . Thus, restricted to these intervals, $g_{m}s_{n_{m}}\cdots g_{1}s_{n_{2}+n_{1}}$ equals to $\Lambda$ . By induction this yields the first assertion.

We show that $g_{m}s_{n_{m}+\ldots+n_{1}}\not=id$ on all but finitely many of the intervals $I_{k}^{r}$ . If $s_{n_{m}+\ldots+n_{1}}\not=id$ , this is by Lemma A.9. Otherwise $g_{m}s_{n_{m}+\ldots+n_{1}}=g_{m}\not=id$ , which yields the claim by Remark A.4. ∎

If $m>0$ , let $i_{0}$ be the smallest index such that $n_{i_{0}}+\ldots+n_{1}=0$ , and recursively define $i_{j}$ to be the smallest index such that $n_{i_{j}}+\ldots+n_{i_{j-1}+1}=0$ . Let $i_{M}$ be the largest such index $<m$ .

Lemma A.11.

If $n_{m}+\ldots+n_{2}+n_{1}=0$ , then $\Lambda$ equals to $g_{m}g_{i_{M}}g_{i_{M-1}}\cdots g_{i_{1}}g_{i_{0}}$ on all but a finite number of intervals $I_{k}^{r}$ , which can be algorithmically determined. Otherwise, $\Lambda\not=id$ .

Proof.

If $m=0$ the claim follows by Lemma A.10. Let $m>0$ .

By Lemma A.9, $g_{m}s_{n_{m}}g_{m-1}\ldots g_{i_{1}}$ and $\Lambda$ are equal on $I^{r}_{k}$ unless $k$ is smaller than the degree of $S_{i}$ , for some $i\leqslant i_{0}$ . Inductively, $g_{m}s_{n_{m}}g_{m-1}\ldots g_{i_{j}}$ and $g_{m}s_{n_{m}}g_{m-1}\ldots g_{{i_{j-1}+1}}s_{i_{j-1}+1}$ equal on $I_{l_{j}}^{r}:=g_{i_{j-1}}\cdots g_{i_{0}}(I^{r}_{k})$ unless $l_{j}$ is smaller than the degree of $S_{i}$ , for some $i_{j-1}<i\leqslant i_{j}$ . Finally, $g_{m}s_{n_{m}+\ldots+i_{M}+1}$ and $g_{m}s_{n_{m}}g_{m-1}\ldots g_{i_{M}+1}s_{M+1}$ are equal on $I_{l_{M}}=g_{i_{M}}\cdots g_{i_{0}}(I^{r}_{k})$ , unless $l_{M}$ is smaller than the degree of $S_{i}$ , for some $i_{M-1}<i\leqslant i_{M}$ .

Let $g:=g_{i_{M}}g_{i_{M-1}}\cdots g_{i_{1}}g_{i_{0}}$ . We conclude that $\Lambda$ is equal to $g_{m}s_{m+\ldots+i_{M}+1}g$ on all but a finite number of intervals $I_{k}^{r}$ . As the degree of the $S_{i}$ is computable, we can algorithmically determine these intervals. If $s_{m+\ldots+i_{M}+1}=id$ , this concludes the proof. Otherwise, by Lemma A.9, $\Lambda$ acts as $s_{n_{m}+\ldots i_{M}+1}g$ on all but finitely many intervals $I_{k}^{r}$ . Thus, $\Lambda\not=id$ by Lemma A.9. ∎

Corollary A.12.

There is an algorithm to decide whether $\Lambda$ is the identity on the intervals $I_{k}^{r}$ in $J^{\prime}$ . ∎

Proof.

By Lemma A.11, there is a computable number $k_{0}>0$ such that, for all $k\geqslant k_{0}$ , $\Lambda=id$ on $I_{k}^{r}$ , if, and only if, $g_{m}g_{i_{M}}\cdots g_{i_{1}}g_{i_{0}}=1$ . As the word problem in $G$ is decidable, this can be algorithmically determined. On the other hand, for each $k$ , there is an (obvious) algorithm to decide whether or not $\Lambda$ acts as the identity on $I_{k}^{r}$ . We apply this algorithm for each $k<k_{0}$ . This completes the proof. ∎

Lemma A.13.

Let $x\in J^{\prime}\setminus\bigcup_{k=1}^{\infty}\bigcup_{i=0}^{m}S_{i}^{-1}(I_{k}^{r})$ . Then $\Lambda(x)=S_{m}(x)$ .

Proof.

Since, for all $k$ , $x\not\in S_{1}^{-1}(I_{k}^{r})$ , we have that $\Lambda(x)=g_{m}s_{m_{n}}\cdots g_{n_{2}}s_{n_{2}}s_{n_{1}}(x)$ . By induction, $\Lambda(x)=S_{m}(x)$ , which is the claim. ∎

Proof of Lemma A.5.

By Lemma A.8, all dyadic factors in a $G_{2}$ –dyadic map fix $1$ . We first compute the degree of $S_{m}$ . If the degree of $S_{m}$ is not $0$ , then Lemma A.11 implies that $\Lambda\not=id$ .

Otherwise, Lemma A.13 implies that $\Lambda$ is the identity on $J^{\prime}\setminus\bigcup_{k=1}^{\infty}\bigcup_{i=0}^{m}S_{i}^{-1}(I_{k}^{r})$ . Let $0\leqslant i\leqslant m$ . We argue that there is an algorithm to decide whether or not $\Lambda$ is the identity on the intervals $S_{i}^{-1}(I_{k}^{r})$ in $J^{\prime}$ . This will complete the proof.

Let $x\in S_{i}^{-1}(I_{k}^{r})$ , and let $y\in I_{k}^{r}$ be the point such that $x=S_{i}(y)$ . We note that $\Lambda(x)=x$ if, and only if, $\Lambda(S_{i}y)=S_{i}y$ , if, and only if, $S_{i}^{-1}\Lambda S_{i}(y)=y$ . Therefore, we need to decide whether or not the $G_{2}$ –dyadic map $S_{i}^{-1}\Lambda S_{i}$ is the identity on the intervals $I_{k}^{r}$ such that $S_{i}^{-1}(I_{k}^{r})\subset J^{\prime}$ .

Let $k_{0}>0$ be the smallest index such that for all $k\geqslant k_{0}$ , $I_{k}^{r}\subset S_{i}(J^{\prime})$ . As $S_{i}(J^{\prime})$ can be algorithmically determined, $k_{0}$ can be computed as well. Thus, we need to decide whether or not $S_{i}^{-1}\Lambda S_{i}$ is the identity on the intervals $I_{k}^{r}$ in $\left[\frac{2^{k_{0}}-1}{2^{k_{0}}},1\right)$ . By Corollary A.12 such an algorithm exists. ∎

A.3. Frattini property

To conclude Thompson’s theorem, Theorem A.1, we also need:

Lemma A.14.

The embedding $\lambda:G_{1}\to T(G_{2},\varphi)$ is a Frattini embedding.

The proof of this lemma is analogous to the proof of Lemma 6.11.

Proof.

Let $h,g\in G_{2}$ and $t\in T(G_{2},\varphi)$ . We assume that $ht^{-1}gt=1$ .

Let $k$ be an index such that $1$ is in the closure of $J_{k}$ and such that (after applying a chart refinement if necessary) $J_{k}\subseteq J$ . As $g$ is fixing $1$ , there is $J_{k}^{\prime}\subseteq J_{k}$ such that $g(J_{k}^{\prime})\subseteq J_{k}$ and such that $1/3$ is in the closure of $J_{k}^{\prime}$ . We let $I_{k}^{\prime}=t_{k}^{-1}(J_{k}^{\prime})$ and $I_{k}^{\prime\prime}=t_{k}^{-1}gt_{k}(I_{k}^{\prime})$ .

Then the triple $(C\times I_{k}^{\prime},C\times I_{k}^{\prime\prime},t_{k}^{-1}gt_{k})$ is in a canoncial chart representation of $t^{-1}gt$ . Up to applying the algorithm of Lemma 4.20 to this chart representation, we may assume that $I_{k}^{\prime\prime}$ is in $[0,1]$ . Moreover, up to applying a chart refinement if necessary, we may assume that either $I_{k}^{\prime\prime}\cap\mathfrak{J}$ is empty or consists of one point $1$ , or $I_{k}^{\prime\prime}\subseteq\mathfrak{J}$ .

If $I_{k}^{\prime\prime}\cap J$ is empty or consists of one point, then $(C\times I_{k}^{\prime},C\times I_{k}^{\prime\prime},t_{k}^{-1}gt_{k})$ is in a chart representation of $ht^{-1}gt$ . Thus $t_{k}^{-1}gt_{k}=id$ on $I_{k}^{\prime}$ by Lemma 4.24. This implies that $g$ acts as the identity on $J_{k}^{\prime}$ . As $1$ is in the closure of $J_{k}^{\prime}$ , this implies that $g=1$ .

Otherwise, $(C\times I_{k}^{\prime},C\times h(I_{k}^{\prime\prime}),ht_{k}^{-1}gt_{k})$ is in a chart representation of $ht^{-1}gt$ . Thus $ht_{k}^{-1}gt_{k}=id$ on $I_{k}^{\prime}$ by Lemma 4.24. But then $t_{k}ht_{k}^{-1}g:J_{k}^{\prime}\to J_{k}^{\prime}$ has to be the identity as well. As $g$ is fixing $1$ , $t_{k}ht_{k}^{-1}$ has to fix $1$ .

If $t_{k}$ does not fix $1$ , $h$ acts (up to applying finitely many chart refinements if necessary) as a dyadic map on $I_{k}^{\prime}$ . But it has to fix $t_{k}^{-1}(1)$ . Thus $h$ acts as the identity on $I_{k}^{\prime}$ . This implies that $g=1$ by Remark A.3.

Otherwise, by Lemma A.11, there are $g_{i_{M}},\ldots,g_{i_{0}}\in G_{2}$ such that, on all but finitely many of the intervals $I_{j}^{r}$ , the maps $h^{-1}t_{k}^{-1}gt_{k}$ equals to $h^{-1}g_{i_{0}}^{-1}\cdots g_{i_{M}}^{-1}gg_{i_{M}}\cdots g_{i_{0}}$ . By Remark A.4, this implies that $h$ and $g$ are conjugated in $G_{1}$ . ∎

Moreover, the embedding of Thompson is also an isometric embedding.

Lemma A.15.

The embedding $G_{1}\hookrightarrow T(G_{2},\varphi)$ is an isometric embedding.

Proof.

We fix a finite generating set for $G_{1}$ . This gives a finite generating set for $(G_{2},\Phi)$ . We denote by $|h|$ the word metric of $h$ .

Let $g\in G_{2}$ and $t\in T(G,\Phi)$ such that $tg=1$ . We represent $t$ by finitely many (canonical) charts $(C_{i}\times I_{i},C_{i}\times J_{i},t_{i})$ such that $\bigcup I_{i}=[0,1]$ . We note that $|t_{i}|\leqslant|t|$ .

Let $I_{k}$ be the interval such that $1$ is in the closure of $I_{k}$ and such that (after applying a chart refinement if necessary) $I_{k}\subseteq J$ .

Then $(C_{i}\times g^{-1}(I_{k}),C_{i}\times J_{i},t_{i}g)$ is in a canonical chart representation of $tg$ . By Lemma 4.24, $t_{i}g$ is the identity mapping. In particular, $g^{-1}(I_{k})=J_{i}$ , so that $J_{i}\subseteq J$ and $1$ is in the closure of $J_{i}$ .

If $t_{i}$ is a dyadic map, then $t_{i}=id$ (Lemma A.9) and thus $g=1$ .

If $t_{i}\in G_{2}$ , then $g=t_{i}^{-1}$ and $|g|=|t_{i}|\leqslant|t|$ .

Otherwise, $t_{i}=g_{1}f_{1}\cdots g_{n}f_{n}$ is a $G_{2}$ –dyadic map. Moreover, by Remark A.4, we may assume that all dyadic maps $f_{i}$ fix $1$ . Thus, by Lemma A.11, $g=g_{i_{1}}\cdots g_{m}$ . Thus $|g|\leqslant m\leqslant|f|$ .

We conclude that the embedding is isometric. ∎

Combining Lemma A.15 with Lemma 5.6, we obtain

Corollary A.16.

If $G$ is finitely generated, then the embedding $G\hookrightarrow T(G_{2},\varphi)$ is isometric. ∎

Proof of Theorem A.1.

By Lemmas A.5 and 4.25, the group $T(G_{2},\varphi)$ has decidable word problem. This group is also finitely generated and simple, see Lemmas 3.14 and 3.19. By construction, $G$ embeds into $T(G_{2},\varphi)$ . ∎

Remark A.17.

If $G$ is non-computably left-orderable with decidable word problem, it is open whether $T(G_{2},\varphi)$ is left-orderable as well.

References

[Ber91] George M. Bergman. Right orderable groups that are not locally indicable. Pac. J. Math., 147(2):243–248, 1991.
[BG09] V. V. Bludov and A. M. W. Glass. Word problems, embeddings, and free products of right-ordered groups with amalgamated subgroup. Proc. Lond. Math. Soc. (3), 99(3):585–608, 2009.
[Bri98] Martin R. Bridson. Controlled embeddings into groups that have no non-trivial finite quotients. In The Epstein birthday schrift, volume 1 of Geom. Topol. Monogr., pages 99–116. Geom. Topol. Publ., Coventry, 1998.
[BZ20] James Belk and Matthew C. B. Zaremsky. Twisted Brin-Thompson groups. arXiv preprint arXiv:2001.04579, 2020.
[CFP96] J. W. Cannon, W. J. Floyd, and W. R. Parry. Introductory notes on Richard Thompson’s groups. Enseign. Math. (2), 42(3-4):215–256, 1996.
[CR16] Adam Clay and Dale Rolfsen. Ordered groups and topology, volume 176 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2016.
[Dar15] A. Darbinyan. Group embeddings with algorithmic properties. Comm. Algebra, 43(11):4923–4935, 2015.
[Dar19] A. Darbinyan. Computability, orders, and solvable groups. arXiv preprint arXiv:1909.05720, 2019. accepted for publication in the Journal of Symbolic Logic.
[DK86] R. G. Downey and Stuart A. Kurtz. Recursion theory and ordered groups. Ann. Pure Appl. Logic, 32(2):137–151, 1986.
[DNR14] Bertrand Deroin, Andrés Navas, and Cristóbal Rivas. Groups, orders, and dynamics. arXiv preprint arXiv:1408.5805, 2014.
[Dow98] R. G. Downey. Computability theory and linear orderings. In Handbook of recursive mathematics, Vol. 2, volume 139 of Stud. Logic Found. Math., pages 823–976. North-Holland, Amsterdam, 1998.
[FS56] A. Fröhlich and J. C. Shepherdson. Effective procedures in field theory. Philos. Trans. R. Soc. Lond., Ser. A, 248:407–432, 1956.
[Gla81] A. M. W. Glass. Ordered permutation groups, volume 55 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge-New York, 1981.
[Gor74] A. P. Gorjuškin. Imbedding of countable groups in $2$ -generator simple groups. Mat. Zametki, 16:231–235, 1974. English translation: Math. Notes 16 (1974), no. 2, 725â727 (1975).
[Hal74] P. Hall. On the embedding of a group in a join of given groups. J. Austral. Math. Soc., 17:434–495, 1974. Collection of articles dedicated to the memory of Hanna Neumann, VIII.
[Hig51] Graham Higman. A finitely generated infinite simple group. J. London Math. Soc., 26:61–64, 1951.
[HL19] James Hyde and Yash Lodha. Finitely generated infinite simple groups of homeomorphisms of the real line. Inventiones mathematicae, Mar 2019. online first, doi:10.1007/s00222-019-00880-7.
[HLNR19] James Hyde, Yash Lodha, Andrés Navas, and Christóbal Rivas. Uniformly perfect finitely generated simple left orderable groups. arXiv preprint arXiv:1901.03314, 2019.
[HT18] Matthew Harrison-Trainor. Left-orderable computable groups. J. Symb. Log., 83(1):237–255, 2018.
[KKL19] Sang-hyun Kim, Thomas Koberda, and Yash Lodha. Chain groups of homeomorphisms of the interval. Ann. Sci. Éc. Norm. Supér. (4), 52(4):797–820, 2019.
[LS77] Roger C. Lyndon and Paul E. Schupp. Combinatorial group theory. Springer-Verlag, Berlin-New York, 1977. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89.
[Mal61] A. I. Mal’tsev. Constructive algebras. I. Russ. Math. Surv., 16(3):77–129, 1961.
[MBT18] Nicolás Matte Bon and Michele Triestino. Groups of piecewise linear homeomorphisms of flows. arXiv preprint arXiv:1811.12256, 2018. accepted for publication in Compositio Mathematica.
[Neu60] B. H. Neumann. Embedding theorems for ordered groups. J. London Math. Soc., 35:503–512, 1960.
[Rab60] M. O. Rabin. Computable algebra, general theory and theory of computable fields. Trans. Am. Math. Soc., 95:341–360, 1960.
[Sch76] Paul E. Schupp. Embeddings into simple groups. J. London Math. Soc. (2), 13(1):90–94, 1976.
[Tho80] Richard J. Thompson. Embeddings into finitely generated simple groups which preserve the word problem. In Word problems, II (Conf. on Decision Problems in Algebra, Oxford, 1976), volume 95 of Stud. Logic Foundations Math., pages 401–441. North-Holland, Amsterdam-New York, 1980.

Embeddings into left-orderable simple groups

Abstract.

Key words and phrases:

2010 Mathematics Subject Classification:

1. Introduction

1.1. Left-order preserving embeddings into simple groups

Theorem 1.

Remark 1.1.

Theorem 2.

1.2. Boone-Higman and Thompson’s theorem revisited

Theorem 3 (cf. Theorem A.1).

Remark 1.2.

Remark 1.3.

Theorem 4.

Remark 1.4.

1.3. Sketch of the embedding constructions

Step 1 (Embedding into a finitely generated group).

Step 2 (Embedding into a perfect group).

Step 3 (Embedding into a simple group of piecewise homeomorphisms of flows).

1.4. Plan of the paper

2. Computability on groups

2.1. Group presentations and the word problem

Definition 2.1 (word problem).

2.2. Computable groups

Definition 2.2.

Remark 2.3.

2.3. Computably left-ordered groups

Definition 2.4.

Remark 2.5.

Remark 2.6.

Example 2.7.

Example 2.8 (Thompson’s group FF).

2.4. Positive cones

Lemma 2.9.

Proof.

2.5. Dense orders

Lemma 2.10 (cf. Theorem 2.22 of [CR16]).

Proof.

Remark 2.11.

2.6. Dynamical realization of computably left-ordered groups

Proposition 2.12.

Definition 2.13.

Lemma 2.14.

Lemma 2.15.

Proof.

Proof of Proposition 2.12.

3. Groups of piecewise homeomorphisms of flows

3.1. Minimal subshifts

3.2. The group T⁡(φ)\operatorname{T}(\varphi)

Definition 3.1 (Dyadic chart).

Definition 3.2 (Dyadic map).

Definition 3.3 (Definition 3.1 of [MBT18]).

Definition 3.4.

Lemma 3.5 (Lemma 3.4 of [MBT18]).

Lemma 3.6 (Lemma 4.8 of [MBT18]).

Lemma 3.7 (Proposition 6.2 of [MBT18]).

3.3. Piecewise homeomorphisms and group embeddings

Definition 3.8.

Example 3.9.

Example 3.10.

Lemma 3.11.

3.4. Groups of flows of piecewise homeomorphisms

Definition 3.12.

Definition 3.13 (The group T​(G,φ)T(G,\varphi)).

Lemma 3.14.

Proof.

Definition 3.15 ((Non-dyadic) rational points).

Lemma 3.16.

Proof.

Lemma 3.17.

Proof.

3.5. Simplicity and rigid stabilizers

Lemma 3.18.

Lemma 3.19.

Proof.

Proof of Claim 1.

Proof of Claim 2.

3.6. Left-orders on T​(G,φ)T(G,\varphi)

Lemma 3.20.

Proof.

Example 2.8 (Thompson’s group $F$ ).

3.2. The group $\operatorname{T}(\varphi)$

Definition 3.13 (The group $T(G,\varphi)$ ).

3.6. Left-orders on $T(G,\varphi)$

4. Chart representations and the word problem in $T(G,\varphi)$

Definition 4.6 ( $G$ -dyadic maps).

5.2. The word problem for $\operatorname{Sp}(G,\varphi)$ .