Subgroups of

Finitely Presented Simple Groups

Claas H. E. W. Röver Pembroke College University of Oxford Trinity Term 1999

A thesis submitted in partial fulfilment of the requirements for the degree of Doctor of Philosophy at the University of Oxford.

Subgroups of

Finitely Presented Simple Groups

Claas H. E. W. Röver

Pembroke College University of Oxford Trinity Term 1999

A thesis submitted in partial fulfilment of the requirements for the degree of Doctor of Philosophy at the University of Oxford.

Abstract

This thesis is concerned with the possible structure of subgroups of finitely presented infinite simple groups. We survey the finitely presented simple groups that were known prior to this thesis and prove that they are all torsion locally finite except possibly those for which the conjugacy problem is unsolvable. A group is called torsion locally finite if every finitely generated torsion subgroup is finite.

Then we generalise the old methods for constructing finitely presented simple groups. This, in turn, enables us to describe constructive embeddings of certain recursively presented groups into finitely presented groups which in theory exist by Higman’s Embedding Theorem.

What is more, we can construct a class of finitely presented simple groups H_{f,p}′ that are not torsion locally finite. More precisely, they have subgroups isomorphic to Grigorchuk-Gupta-Sidki groups which are finitely generated infinite torsion groups under suitable assumptions. We also prove that each group H_{f,p}′ is generated by two elements.

In the last two chapters we investigate algorithmic decision problems for the groups H_{f,p}, thereby obtaining a positive answer to the order problem. We also prove that the conjugacy problem is solvable for all elements with ‘flat symbols’ if p is a prime. This includes all periodic elements, so in particular the conjugacy problem for periodic elements is shown to be solvable. In addition, we describe an effective procedure to decide whether an element has a flat symbol.

We also show that the family H_{f,p}′ of finitely presented simple groups contains a countable infinity of isomorphism classes.

Acknowledgements

First of all I would like to thank my supervisor Prof. Martin R. Bridson for his guidance and the many helpful and inspiring conversations during the past two years.

Equally important were my parents who only made this project possible with their financial support for which I’m very grateful, indeed, and forever.

I thank Dr. Peter M. Neumann and Prof. Dan Segal for conversations, coffee, problems to think about, and making me feel welcome in Oxford. And all my fellow Algebra students for sharing their and my questions as well as spare time.

I also thank Dr. Vlad Sergiescu for inviting me to Grenoble where I learned a great deal about the different aspects of Thompson’s group and its relatives. And Dr. Jens Harlander who invited me to give a talk in Frankfurt and discussed the Houghton groups with me.

Thank you, also to the Mathematical Institute, EPSRC, and the EU for supporting my participation at numerous conferences and short courses which meant lots of exciting mathematic(ian)s.

All my friends who helped me to survive socially, though not much with the mathematics, are too many to be named individually, but are each and everyone worth a cheers.

Final acknowledgements go to TEX for typesetting and the computer administrators who kept the system bug-free at all times and saved me some valuable time by recovering material I accidentally deleted.

Contents

Introduction 1

1 Preliminaries 6 1.1 Conventions and Notation . . . . . . . . . . . . . . . . . . . . 6 1.2 Inescapable Bases and Subspaces . . . . . . . . . . . . . . . . 7 1.3 Groups of Maximal Inescapable Isomorphisms . . . . . . . . . 9 1.4 Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5 Tree Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2 Subgroups: Part I 18 2.1 Some ‘Classical’ Subgroups and Simplicity . . . . . . . . . . . 18 2.2 Thompson’s Lemma . . . . . . . . . . . . . . . . . . . . . . . 20 2.3 Obvious Subgroups of G_{n,r} . . . . . . . . . . . . . . . . . . . 22 2.4 Restrictions on Subgroups . . . . . . . . . . . . . . . . . . . . 25 2.5 Ping-Pong and some Free Products . . . . . . . . . . . . . . . 26 2.6 Generators for G_{n,r} . . . . . . . . . . . . . . . . . . . . . . . . 29

3 Expansibility and Fake Expansibility 30 3.1 Expansibility . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2 A Presentation for Expansible Groups . . . . . . . . . . . . . 33 3.3 The θ-Construction . . . . . . . . . . . . . . . . . . . . . . . . 35 3.4 Fake Symbols and Fake Expansibility . . . . . . . . . . . . . . 36 3.5 Presentations for Fake Expansible Groups . . . . . . . . . . . 39 4 Subgroups: Part II 46

4.1 Some Expansible Groups . . . . . . . . . . . . . . . . . . . . . 46 4.2 Torsion Local Finiteness . . . . . . . . . . . . . . . . . . . . . 47 4.3 Grigorchuk-Gupta-Sidki . . . . . . . . . . . . . . . . . . . . . 51 4.4 The Groups E_{f,p} and H_{f,p} . . . . . . . . . . . . . . . . . . . . 53 4.5 The Commutator Subgroup of H_{f,p} . . . . . . . . . . . . . . . 55 4.6 More Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5 The Order Problem 62 5.1 The Group M . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.2 Step Columns and Flat Symbols . . . . . . . . . . . . . . . . 65 5.3 Solving the Order Problem . . . . . . . . . . . . . . . . . . . 68

6 The Conjugacy Problem 72 6.1 Pseudo-Orbits and their Characteristics . . . . . . . . . . . . 72 6.2 Conjugate Flat Symbols . . . . . . . . . . . . . . . . . . . . . 74 6.3 Pseudo-Orbit Expansions . . . . . . . . . . . . . . . . . . . . 75 6.4 Normal Symbols . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.5 The Conjugacy Problem: I . . . . . . . . . . . . . . . . . . . 78 6.6 Legal Symbols and their Index . . . . . . . . . . . . . . . . . 81 6.7 The Conjugacy Problem: II . . . . . . . . . . . . . . . . . . . 83

Appendices 88

A Some Calculations 88

B Tree Diagrams of Generators 91

C Tree Diagrams to Look at 92

Bibliography 93

Index 96

Introduction

This work grew out of a desire to get a more detailed picture of the possible structure of subgroups of finitely presented simple groups. The first such groups that come to mind are probably finite simple groups, which obviously have only finite subgroups. Conversely, every finite group can be embedded in some alternating group of sufficiently large degree, for instance, and hence in a finite simple group. This is all we want to say about finite simple groups, and from now on, ‘finitely presented simple group’ always means ‘infinite finitely presented simple group’.

The motivations for our study are numerous. Firstly, simple groups have played an important role in group theory since its inception. Secondly, the class of finitely presented groups is in many ways the most important and natural class of infinite groups (these are fundamental groups of compact manifolds, for example) and has many interesting subclasses, e.g., hyperbolic groups, automatic groups, linear groups over the integers, and Fuchsian groups, to mention just a few. Also very interesting is their connection with algorithmic properties highlighted in the famous embedding theorem of G. Higman [23]: a finitely generated group is embeddable in a finitely presented group if and only if it is recursively presented. To say that a finitely generated group is recursively presented means precisely that there is a recursively enumerable set of defining relations. The set of all relations (words representing the identity) is recursive if and only if the group has a solvable word problem, i.e., there is an algorithm which, given an arbitrary word on the generators, decides whether this word represents the trivial element. This leads to one of the few general results about finitely presented simple groups. Kuznetsov [29] proved that every finitely presented simple group has a solvable word problem. In fact, this is true for every recursively presented simple group. Inspired by Higman’s embedding theorem one might seek an algebraic characterisation of groups with solvable word problem. Taking Kuznetsov’s result into account, it seems reasonable to pose the following conjecture (see [4]).

Boone-Higman-Conjecture: A finitely generated group has a solvable word problem if and only if it can be embedded in a finitely presented simple group.

We would have loved to prove this conjecture but it appears to be very difficult. However, we do prove several new and related results. Some of them can be summarised as follows.

Theorem A. There are countably many non-isomorphic 2-generated finitely presented simple groups with finitely generated infinite torsion subgroups.

As we believe that our results can be more appreciated by seeing them within the present state of knowledge, a quick survey precedes a more detailed discussion of our theorems.

The study of finitely presented simple groups began in 1965 when R. J. Thompson discovered the first two examples (see [40] for a description). These are the groups we call G_{2,1} and T_{2,1}. Viewing G_{2,1} as a subgroup of an uncountable group, Thompson [40] proved that a finitely generated group has a solvable word problem if and only if it is a subgroup of a finitely generated simple group which, in turn is a subgroup of a finitely presented group. Moreover, the finitely presented group can be chosen to have a solvable word problem. This is still the most comprehensive result towards the Boone-Higman-Conjecture. Note that there are finitely presented groups with unsolvable word problem, e.g. [32],[3],[31].

In 1974 Higman, upon hearing about Thompson’s group, constructed in [24] a countably infinite family of finitely presented simple groups generalising Thompson’s G_{2,1}. These are the commutator subgroups of the groups called G_{n,r} later in this work. (That name is the same as in [24] and the subscripts are integers n ≥ 2, r ≥ 1.) He also showed that this family contains infinitely many isomorphism types. Some time later, in 1987, K. S. Brown discovered a family of finitely presented simple subgroups of the groups G_{n,r} which are generalisations of Thompson’s T_{2,1}. We will meet these briefly in Chapter 2.

There are several ways to describe these groups. They are automorphism groups of r-generated free algebras in the variety of algebras of sets that are in bijection with their own n-th direct power, cf. [24]. They are also groups of piecewise linear homeomorphisms of the unit interval with prescribed slopes and limited sets of non-differentiable points (see for example [39] and [5]). Furthermore, they are groups of tree diagrams of finite n-ary rforests. This is the approach in [10]. Yet another point of view, taken in [35] for instance, is their interpretation as groups of maximal inescapable isomorphisms. In this work we use the latter two descriptions, and they are explained in detail in Chapter 1.

The groups G_{n,r} are still not fully understood. For example, the isomorphism problem is not yet known to be solvable in this class of groups. However, Higman’s work [24] gives quite some insight. And, amongst many other results, he shows that the group GL_{3}(ZZ) of invertible three-by-three matrices over the integers is not isomorphic to a subgroup of any of the groups G_{n,r}. Note that GL_{n}(ZZ) has a solvable word problem, since multiplication of matrices is effective and only the identity matrix is the trivial element.

His results also imply that the additive group of the rational numbers cannot be embedded in any G_{n,r}, and neither can the Baumslag-Solitar groups BS(l, m) which are generated by two elements a and b subject to the single defining relation b^{−1}a^{l}b = a^{m} if m divides l.

After studying the obvious generalisations (the groups G_{n,r} in this work) of Thompson’s uncountable supergroup, E. A. Scott [36] showed in 1984 that for any positive integer n there exists a finitely presented simple group with subgroups isomorphic to GL_{n}(ZZ). She did this using her method developed in [35] that can be used to embed certain finitely presented groups in finitely presented simple groups: the θ-construction. This is explained in Section 3.3.

The key to these constructions is Thomson’s Lemma which says that every subgroup of G_{n,r} that contains G_{n,r}′ has a simple commutator subgroup (Lemma 2.3). So, for example, one strategy to obtain finitely presented simple groups is as follows: construct finitely presented supergroups of G_{n,r}′ inside G_{n,r} and make sure that their commutator subgroups are of finite index. This is exactly what can be done with the θ-construction, and our constructions also follow these lines.

One of our results (Theorem 4.7) says that every finitely presented simple group obtained with the θ-construction from a torsion locally finite group is also torsion locally finite. We call a group torsion locally finite if every finitely generated torsion subgroup is finite. Putting this together with the observation that each countable locally finite group is a subgroup of any group G_{n,r} (see [24] or Theorem 2.4) we get a complete characterisation of torsion subgroups of G_{n,r}: they are precisely the countable locally finite groups. This appears to be new.

A weakness of the θ-construction is that it applies (a priori) to finitely presented groups only. Therefore we develop a generalisation of Scott’s method in Chapter 3, which enables us to construct embeddings of certain recursively presented groups into finitely presented simple groups. More precisely, we prove that every Grigorchuk group defined by an almost periodic sequence is isomorphic to a subgroup of some finitely presented simple group (Theorem 4.10). These simple groups are the derived groups of the groups called H_{f,p} in Chapter 4 where one also finds the necessary definitions concerning Grigorchuk groups.

The finitely presented simple groups H_{f,p}′ are interesting for at least two reasons. On the one hand, their constructions are rather rare examples of constructive embeddings of recursively presented groups in finitely presented groups. (It is shown for example in [17] that a non-trivial Grigorchuk group is not finitely presented.) For one specific Grigorchuk group such an embedding was recently obtained by R. I. Grigorchuk [19] using an HNN-extension. In addition, he needs an explicit presentation, whereas our methods do not require a presentation at all. On the other hand, the groups H_{f,p}′ are probably the first finitely presented simple, but not torsion locally finite, groups. This is simply because Grigorchuk groups are finitely generated infinite torsion groups for suitably chosen (periodic) defining sequences. Our methods can also be applied to embed other finitely generated infinite torsion groups in finitely presented simple groups, for example, those studied by N. Gupta and S. Sidki in [22] and suitable special groups in the sense of [17]. We also prove that the direct product of any finite family of Grigorchuk-Gupta-Sidki groups whose defining sequences are periodic can be embedded in a finitely presented simple group (Theorem 4.16).

There is one class of previously known finitely presented simple groups that we have not been able to show are torsion locally finite, namely the finitely presented simple groups with unsolvable conjugacy problem described by Scott in [37]. Their construction still relies on Thompson’s Lemma, but does not use the θ-construction. Hence our criterion for torsion locally finiteness does not apply, and therefore we cannot assure that the groups H_{f,p}′ are new finitely presented simple groups. However, we conjecture that these groups are also torsion locally finite.

One way out of this dilemma would be a solution of the conjugacy problem for H_{f,p}′. In such an attempt we have only succeeded in describing a procedure that solves the conjugacy problem for elements with ‘flat’ symbols (Theorem 6.13) if p is prime. Every periodic element has a flat symbol, so in particular, the conjugacy problem for periodic elements of H_{p,f} is shown to be solvable. This would be worthless without being able to decide whether a given element has finite order. So we show in Theorem 5.9 that the order problem is solvable for elements of H_{f,p}′. In fact we describe a procedure which decides whether an element has a flat symbol. As a by-product we prove that there is a countable infinity of isomorphism types among the groups H_{f,p}′ (Theorem 6.14).

Besides all these new results, from a broader point of view, our finitely presented simple groups H_{f,p}′ are after all groups of maximal inescapable isomorphisms, and as such not so far away from the groups G_{n,r}′ and the groups constructed by Scott. Hence, we should mention that recently M. Burger and S. Mozes constructed very different finitely presented simple groups in [9]. These are lattices in direct products of two automorphism groups of regular (non-rooted) trees, and can also be seen as free products with amalgamation of two finitely generated free groups with the amalgamated subgroup having finite index in each factor. In particular, they are torsion-free, and hence not isomorphic to any of the groups G_{n,r}′ or H_{f,p}′.

Let us now give an outline of the individual chapters of this work. We fix our notation and embark on some conventions in the first section of Chapter 1. The remainder of that chapter is a complete introduction to groups of maximal inescapable isomorphism including the language of symbols and tree diagrams. The basic properties of maximal inescapable isomorphisms are gathered there as well.

Chapter 2 presents a selection of known results about the groups G_{n,r} with an emphasis on simplicity (Section 2.1) and the possible structure of subgroups. It contains a proof that G_{n,r} is generated by two elements and some unpublished, though maybe known, results about subgroups. In particular, we show that the Houghton groups are subgroups of every G_{n,r}.

Mathematics’ technical side shows itself in Chapter 3. First we recall the main features of Scott’s paper [35] and describe the θ-construction. Then we introduce fake expansibility as a generalisation of Scott’s expansibility, and prove a criterion for finite presentability of certain groups of maximal inescapable isomorphisms, namely fake-E-expansible groups, where E is a finitely presented group.

The applications of this result, in particular the construction of the groups H_{f,p} and H_{f,p}′ and the proof that they are generated by two elements occupy most of Chapter 4. First, however, we record the results of Scott and prove that the θ-construction preserves torsion locally finiteness.

Chapter 5 is a not-so-short but painless description of the algorithm that solves the order problem for H_{f,p}. And finally, Chapter 6 concerns the solvability of the conjugacy problem for elements with flat symbols, in particular periodic elements, of H_{f,p}. An affirmative answer is obtained by a rather long and detailed analysis of different kinds of specialised symbols if p is a prime.

At the end of this work we have included an index of all the major definitions. The reason for this is that we prefer to give definitions in the main text. Since the defined terms are emphasised, readers should have no difficulty in finding them using the index.

Equations are numbered inside each chapter, e.g., the equation labelled (3.4) is the fourth equation in Chapter 3. Theorems, propositions, lemmas, and corollaries are all treated as ‘proclaimed statements’ and also numbered within chapters, e.g., Lemma 1.7 is the seventh statement in Chapter 1 but not necessarily the seventh lemma of that chapter. References always give both numbers, either in round brackets if they point to an equation, or as in ‘Proposition 3.4’, if a statement is the target.

Chapter 1

Preliminaries

In this chapter we introduce the main objects of study and fix some notation that is used throughout this thesis. Section 1.1 deals with basic group and set theoretic notions and notational conventions. The remaining sections form an elementary introduction to groups of maximal inescapable isomorphisms which are the main objects of study in this work. Apart from Section 1.5 which is more or less borrowed from [10], most of that material can be found in [35] with minor changes in the notation. We delay definitions of more specialised terms to the places where they are needed.

1.1 Conventions and Notation

We write ZZ, IN, and IN_{0} for the integers, the non-negative integers, and the the positive integers, respectively. In particular, 0 ∉ IN and IN_{0} = IN ∪ {0}. By |X| we denote the cardinality of a set X and X \ Y is defined as {x ∈ X | x ∉ Y }.

For group elements g and h we write g^{h} for h^{−1}gh, the conjugate of g by h, and let [g, h] denote the commutator g^{−1}h^{−1}gh of g and h. The derived or commutator subgroup of the group G is denoted G′ and defined as the subgroup generated by { [g, h] | g, h ∈ G }, which is to be read as ‘the set of all [g, h] such that g and h are elements of G’. Consequently, we write G′′ for the commutator subgroup of the derived subgroup of G. For a subset Y of G the subgroup of G generated by Y is denoted ⟨Y ⟩ and we also use the standard shorthand notations, e.g., G′ = ⟨[g, h] | g, h ∈ G⟩. The identity element of a group and the trivial group, as well as the integer ‘one’, are all denoted by 1, confusion being prevented by the context. If g is a group element, we denote by |g| its order, and we call elements of finite order also periodic or torsion elements. A torsion or periodic group is one with torsion elements only.

If the group G acts on a set X then x^{g} denotes the image of x ∈ X under g ∈ G. That is, all our actions are right actions and we use exponential notation; thus, interpreted as an operator, gh means ‘g followed by h’ and conjugation is one example. Frequently we will be dealing with permutations π of {a_{1}, a_{2}, …, a_{n}}, a set with n elements, and it is convenient to interpret π also as a permutation of the subscripts; thus a_{i}^{π} and a_{i^{π}} are equal. As it is slightly odd to have superscripts inside subscripts, we will, in such circumstances, depart from the convention above and write a_{iπ} in place of a_{i^{π}}.

To be on the safe side and to avoid superfluous explanations later, we agree to distinguish the direct product X_{i∈T} U_{i} and the restricted direct product ⨁_{i∈I} U_{i} of a family {U_{i}}_{i∈I} of groups, indexed by a set I, where the former is the set of all functions f : I ⟶ ⋃_{i∈I} U_{i} with i^{f} ∈ U_{i} under pointwise composition, and the latter is the subgroup of those functions with i^{f} = 1 for all but finitely many i ∈ I.

Let us finally recall the definition of some variants of wreath products. Suppose G and H are groups acting on sets X respectively Y. Then the permutational wreath product, denoted G≀H, of G with H is the semidirect product of X_{y∈Y} G_{y} with H, where each G_{y} is isomorphic to G and H permutes the components according to its action on Y. If no actions are specified we assume that G and H act on themselves via right multiplication (this is called the standard wreath product in the literature). We will only need the case where Y (or H in standard wreath products) is finite, and it is then convenient to denote elements of G ≀ H as (g_{y_{1}}, …, g_{y_{r}})h, where g_{y_{i}} ∈ G(= G_{y_{i}}) and h ∈ H. The important rule to remember is

(g_{y_{1}}, …, g_{y_{r}})^{h} = (g_{y_{1}h^{−1}}, …, g_{y_{r}h^{−1}}),

where as before, y_{i}h means y_{i}^{h}.

1.2 Inescapable Bases and Subspaces

Let n, r ∈ IN, n ≥ 2, let W_{n} be the set of all finite words over the alphabet A_{n} = {a_{1}, a_{2}, …, a_{n}} including the empty word which we denote by ∅, and let X_{r} be a set of r distinct symbols x_{1}, …, x_{r} disjoint from A_{n}. If U and V are sets of words we define UV = {uv | u ∈ U, v ∈ V } where uv denotes the concatenation of u and v. We also use the inductive definition U^{n+1} = U^{n}U, n ≥ 1, with U^{1} = U and, if U = {u}, then we write u^{n} for U^{n}.

The binary relation “u is a prefix of v” (written u ≤ v or v ≥ u) equips X_{r}W_{n} with a partial order. As usual we write u < v if u ≤ v and u ≠ v. A subset B of X_{r}W_{n} is called independent if its elements are pairwise ≤- incomparable and is said to be an inescapable basis if it is maximal among independent subsets. Let B be an inescapable basis, b ∈ B and define C as (B \ {b}) ∪ {ba_{i} | 1 ≤ i ≤ n}. Then C is easily seen to be an inescapable basis, too, and we call C the simple expansion of B at b or simply a simple expansion of B. Furthermore, we call the inescapable basis D an expansion of B if there is a finite family of inescapable bases B_{0}, … B_{m} with B = B_{0}, D = B_{m}, and B_{i} is a simple expansion of B_{i−1} for 1 ≤ i ≤ m. Let us agree to write B ⪯ D or D ⪰ B if D is an expansion of B. Note that every finite inescapable basis is an expansion of the inescapable basis X_{r}.

An inescapable subspace of X_{r}W_{n} is a subset of the form U = BW_{n}, where B is an inescapable basis. The term shall reflect the facts that UW_{n} ⊂ U and for every v ∈ X_{r}W_{n} there exists w ∈ W_{n} such that vw ∈ U. In fact, these two conditions can also be used to define an inescapable subspace. If B is finite then one says that U is a finitely based inescapable subspace. Furthermore, if U is an inescapable subspace we denote by B_{U} its inescapable basis; this is the set of minimal elements in the partially ordered set U with the induced order from X_{r}W_{n}. It should be clear that U ⟶ B_{U} is a bijection between inescapable subspaces and inescapable bases and that U′ ⊂ U if and only if B_{U′} ⪰ B_{U}.

Using the second characterisation of inescapable subspaces it is straightforward that every intersection of finitely many (finitely based) inescapable subspaces is again a (finitely based) inescapable subspace. If B_{1}, …, B_{m} are inescapable bases then we denote by ⨆_{i=1}^{m} B_{i} the inescapable basis of the inescapable subspace ⋂_{i=1}^{m} B_{i}W_{n} and, if m = 2 we also write B_{1} ⊔ B_{2}. This is first of all more legible than B_{⋂_{i=1}^{m} B_{i}W_{n}} and secondly more convenient, since it only involves inescapable bases. The following lemma records the basic properties of inescapable bases we will need later.

Lemma 1.1 Let B_{i}, 1 ≤ i ≤ m, be a finite family of inescapable bases and put B = ⨆_{i=1}^{m} B_{i}. Then the following hold.

a) B ⪰ B_{i} for 1 ≤ i ≤ m.

b) B ⊂ ⋃_{i=1}^{m} B_{i}.

c) If w ∈ B_{j} ∩ BW_{n} for some j, 1 ≤ j ≤ m, then w ∈ B.

Proof. Part a) is obvious. We prove b). Without loss of generality we may assume m = 2. To obtain a contradiction, let d ∈ B and assume d ∉ B_{1} ∪ B_{2}. By definition B ⊂ B_{1}W_{n} ∩ B_{2}W_{n}, so there are b ∈ B_{1}, c ∈ B_{2} and w, v ∈ W_{n} \ {∅} such that d = bw = cv. It follows that w = xa_{i} and v = ya_{i} for some i, 1 ≤ i ≤ n, and hence z = bx = cy ∈ B_{1}W_{n} ∩ B_{2}W_{n}. But z < d which contradicts the assumption that B is the inescapable basis of B_{1}W_{n} ∩ B_{2}W_{n}. To prove c) we may again assume m = 2, and we lose nothing by setting j = 1. Supposing w ∉ B, we find b ∈ B and ∅ ≠ x ∈ W_{n} with w = bx. In particular b < w. But b < w ∈ B_{1} implies b ∉ B_{1}W_{n}, which in turn contradicts b ∈ B ⊂ B_{1}W_{n} ∩ B_{2}W_{n}. The proof of the lemma is now complete.

Sometimes it is useful to think of X_{r}W_{n} as the graph with vertex set V = X_{r}W_{n} and edge set E = { (u, ua_{i}) | u ∈ V, 1 ≤ i ≤ n } (see Section 1.5 for definitions concerning graphs). Figure 1 below indicates this graph which in fact is a forest.

Figure 1: The graph associated with X_{r}W_{n}

Observe that each vertex v is in a unique connected component which in turn corresponds to a unique element x_{i} of X_{r} and that there is a unique reduced path, i.e. a path without backtracking, joining x_{i} to v. Therefore we may as well identify v with this path. Taking this point of view, an inescapable basis B is identified with the subgraph consisting of all those paths corresponding to the vertices of B. It is now clear that there is a bijection between inescapable bases and those subgraphs which have precisely r connected components each of which contains a unique x_{i} ∈ X_{r} of valency n and all other vertices have valency n + 1 or 1. In Section 1.5 we will further explore this point of view.

1.3 Groups of Maximal Inescapable Isomorphisms

Recall the convention that maps will be written on the right of their argument and mostly as exponents. Let U and V be inescapable subspaces of X_{r}W_{n}. A bijection ϕ : U ⟶ V is an inescapable isomorphism (of X_{r}W_{n}) if

(uw)^{ϕ} = u^{ϕ}w holds for all u ∈ U, w ∈ W_{n}.  (1.1)

In particular, u ≤ u′ implies u^{ϕ} ≤ u^{′ϕ}, where u, u′ ∈ U. This shows immediately that the restriction of ϕ to the inescapable basis of U is a bijection B_{U} ⟶ B_{V}. Conversely, for a given bijection φ : B ⟶ C between inescapable bases B and C there is a unique inescapable isomorphism ϕ : BW_{n} ⟶ CW_{n} whose restriction to B is φ; simply (bw)^{ϕ} = b^{φ}w, b ∈ B, w ∈ W_{n}.

Let ϕ_{i} : U_{i} ⟶ V_{i}, i = 1, 2, be inescapable isomorphisms and assume U_{2} ⊂ U_{1}. Then ϕ_{1} is called an extension of ϕ_{2} if the restriction of ϕ_{1} to U_{2} equals ϕ_{2}. Note that for every inescapable subspace U which is contained in U_{1}, U^{ϕ_{1}} is an inescapable subspace and contained in V_{1}. An inescapable isomorphism is called maximal if it has no proper extension. The following result is Lemma 1 in [35] of which we reproduce a proof for the sake of completeness.

Lemma 1.2 Every inescapable isomorphism has a unique maximalisation.

Proof. Let ϕ : U ⟶ V be an inescapable isomorphism of X_{r}W_{n}. Define U^{∗} to be the set of all z ∈ X_{r}W_{n} for which there exists y ∈ X_{r}W_{n} so that (zw)^{ϕ} = yw for all those w ∈ W_{n} with zw ∈ U. Then U^{∗} is an inescapable subspace because z ∈ U^{∗} clearly implies zv ∈ U^{∗} for all v ∈ W_{n}, whence U^{∗}W_{n} ⊂ U^{∗}, and for all v ∈ X_{r}W_{n} there is w ∈ W_{n} with vw ∈ U ⊂ U^{∗}. For z ∈ U^{∗} define ϕ^{∗} by z^{ϕ^{∗}} = y, where y is such that (zw)^{ϕ} = yw for all w ∈ W_{n} with zw ∈ U. It is clear from the definition that ϕ^{∗} extends ϕ. We proceed to show that ϕ^{∗} is an inescapable isomorphism. To this end let z ∈ U^{∗}, v ∈ W_{n} and suppose z^{ϕ^{∗}} = y. Then, for all w ∈ W_{n} with zvw ∈ U, (zvw)^{ϕ} = yvw, whence, by definition of ϕ^{∗}, (zv)^{ϕ^{∗}} = yv = z^{ϕ^{∗}}v. Furthermore, z^{ϕ^{∗}} = z^{′ϕ^{∗}} = y with z, z′ ∈ U^{∗} implies (zw)^{ϕ} = (z′w)^{ϕ} = yw for all w ∈ W_{n} with zw, z′w ∈ U, and hence zw = z′w, as ϕ is a bijection. Thus z = z′ and ϕ^{∗} is a bijection U^{∗} ⟶ U^{∗}^{ϕ^{∗}}. Since U^{∗}^{ϕ^{∗}} ⊃ V, U^{∗}^{ϕ^{∗}} is an inescapable subspace. So ϕ^{∗} is an inescapable isomorphism. Suppose now that ψ : U′ ⟶ V′ is an inescapable isomorphism extending ϕ. Then (uw)^{ψ} = (uw)^{ϕ} = u^{ψ}w for all u ∈ U′, w ∈ W_{n} with uw ∈ U, so u ∈ U^{∗}. Moreover, u^{ϕ^{∗}} = u^{ψ}, by definition of ϕ^{∗}, and hence ϕ^{∗} extends ψ. Thus ϕ^{∗} is the unique maximalisation of ϕ and the lemma is proved.

This enables us to define a group structure on the set of maximal inescapable isomorphisms of X_{r}W_{n} as follows. Let ϕ_{i}, i = 1, 2, be as above and put S = V_{1} ∩ U_{2}, R = S^{ϕ_{1}^{−1}} and T = S^{ϕ_{2}}. Then it is readily checked that the composition of the restriction of ϕ_{1} to R with the restriction of ϕ_{2} to S is an inescapable isomorphism χ : R ⟶ T, and we define ϕ_{1}ϕ_{2} to be the (unique) maximalisation of χ.

From now on G_{n,r} denotes the group of maximal inescapable isomorphisms of X_{r}W_{n}. It follows from Section 1.2 that the set of maximal inescapable isomorphisms between finitely based inescapable subspaces forms a subgroup of G_{n,r} which hitherto will be denote by G_{n,r}.

Convention. We agree now to call inescapable bases for short bases but warn readers that these bases do not share the properties usually expected of bases such as having uniquely determined cardinality etc. However, they are bases in the universal algebra setting of Higman’s point of view, cf. [24]. We shall also always identify X_{1}W_{n} with W_{n} via x_{1}w ↦ w.

1.4 Symbols

In this section we describe one way of representing inescapable isomorphisms. Another way is described in Section 1.5. The following approach is already contained implicitly in the work of Thompson [40] and takes the form it is presented here via the works of Higman [24] and Scott [35].

Let us define a symbol to be a scheme of the form

( \begin{matrix}b_{1} & b_{2} & ⋯ & b_{s} \\ g_{1} & g_{2} & ⋯ & g_{s} \\ c_{1} & c_{2} & ⋯ & c_{s} \end{matrix} )  (1.2)

where the g_{i} are elements of G_{n,1} and {b_{1}, b_{2}, …, b_{s}} and {c_{1}, c_{2}, …, c_{s}} are finite bases of X_{r}W_{n}, say B and C, respectively.

Let Γ be the symbol (1.2). Then B and C are called the top row and bottom row of Γ, respectively, which are denoted by top(Γ) respectively bot(Γ); thus top(Γ) = {b_{1}, b_{2}, …, b_{s}} and bot(Γ) = {c_{1}, c_{2}, …, c_{s}}. Sometimes we call the g_{i} middle row entries of Γ. Note, that although the rows of the symbol Γ appear to be ordered, top(Γ) and bot(Γ) are only defined to be sets. What follows will make clear that the order does not play any role apart from appearing in print. The symbol Γ defines the inescapable isomorphism

BW_{n} ⟶ CW_{n}
b_{i}w ⟼ c_{i}(w)^{g_{i}}, whenever w^{g_{i}} is defined, w ∈ W_{n},

the maximalisation of which we define to be the element ϕ ∈ G_{n,r} with symbol Γ.

We also say that ϕ ∈ G_{n,r} has the symbol Δ if Δ is a symbol defining ϕ. Furthermore, for i ∈ {1, 2, …, n},

( \begin{matrix}b_{i} \\ g_{i} \\ c_{i} \end{matrix} )

is called a column of the symbol (1.2), and we say that ϕ ∈ G_{n,r} has the column C or C is a column of ϕ, if ϕ has a symbol Δ so that C is a column of Δ. It follows directly from the definition, that the order in which the columns of a symbol Δ appear in print does not alter the inescapable isomorphism defined by Δ, so it is perfectly sensible to treat symbols as finite sets of columns and we will do this from time to time. This is why we write C ∈ Δ to denote that C is a column of Δ and top(C) and bot(C) for the top respectively bottom row entry of the column C. The column C is called trivial if it has a trivial middle row entry and top(C) = bot(C). Observe that a symbol defines the trivial element of G_{n,r} if and only if all its columns are trivial.

A more precise notion is that of an E-symbol where E is a subgroup of G_{n,1}, i.e., all the middle row entries are elements of E. This notion will play an important role from Chapter 3 onwards. Note that G_{n,r} consists precisely of those elements which have a 1-symbol (1 denotes the trivial group). This follows from Section 1.2. We also remark that G_{n,r} embeds in G_{n,1} for all n, r ∈ IN, showing that g_{i} ∈ G_{n,1} in the definition of a symbol is no serious restriction. For, let B be a finite basis of W_{n} of cardinality at least r, say {b_{1}, …, b_{r}} ⊂ B, and let C be a basis of X_{r}W_{n}. Then by replacing x_{i} by b_{i} for 1 ≤ i ≤ r in every element of C we obtain C′ ⊂ W_{n} and moreover Ĉ = C′ ∪ (B \ {b_{1}, …, b_{r}}) is a basis of W_{n}. Finally, if ϕ : CW_{n} ⟶ DW_{n} is an inescapable isomorphism of X_{r}W_{n} define ϕ̂ : ĈW_{n} ⟶ D̂W_{n} as the identity on B \{b_{1}, …, b_{r}} and as the obvious map C′W_{n} ⟶ D′W_{n} induced by ϕ. It is now straightforward to check that ϕ ⟼ ϕ̂ is an embedding of G_{n,r} into G_{n,1}. Note, that the image of G_{n,r} under this embedding lies in G_{n,1}.

Suppose now Γ is given by (1.2) and g_{i} has the symbol

( \begin{matrix}u_{1} & u_{2} & ⋯ & u_{t} \\ h_{1} & h_{2} & ⋯ & h_{t} \\ v_{1} & v_{2} & ⋯ & v_{t} \end{matrix} ) .

Then it is straightforward to verify that Γ and the symbol

Δ = ( \begin{matrix}b_{1} & ⋯ & b_{i−1} & b_{i}u_{1} & ⋯ & b_{i}u_{t} & b_{i+1} & ⋯ & b_{s} \\ g_{1} & ⋯ & g_{i−1} & h_{1} & ⋯ & h_{t} & g_{i+1} & ⋯ & g_{s} \\ c_{1} & ⋯ & c_{i−1} & c_{i}v_{1} & ⋯ & c_{i}v_{t} & c_{i+1} & ⋯ & c_{s} \end{matrix} )

define the same maximal inescapable isomorphism. Recall that, by the convention at the end of Section 1.3, X_{1}W_{n} is identified with W_{n} which is crucial for Δ to be a symbol according to the definition above. We call Δ an expansion of Γ at the column

( \begin{matrix}b_{i} \\ g_{i} \\ c_{i} \end{matrix} );

if t = n then Δ is called a simple expansion of Γ

(at ( \begin{matrix}b_{i} \\ g_{i} \\ c_{i} \end{matrix} )).

More generally, we say that the symbol Δ is an expansion of the symbol Σ if there are symbols Δ_{0} = Σ, Δ_{1}, …, Δ_{r} = Δ and columns C_{i} ∈ Δ_{i} such that Δ_{i+1} is an expansion of Δ_{i} at C_{i} for 0 ≤ i ≤ r − 1. If the symbol Δ is an expansion of the symbol Σ we write Δ ⪰ Σ or Σ ⪯ Δ. As it will be clear from the context whether we talk about symbols or bases, there should be no confusion caused by the multiple use of ⪯. For even more clarity, bases will usually be denoted by upper case roman letters and symbols by upper case greek letters. The following easy lemma is Lemma 5 in [35] and it relates symbols to the group structure of G_{n,r}.

Lemma 1.3 If

Γ = ( \begin{matrix}u_{1} & ⋯ & u_{s} \\ g_{1} & ⋯ & g_{s} \\ v_{1} & ⋯ & v_{s} \end{matrix} ) and Δ = ( \begin{matrix}v_{1} & ⋯ & v_{s} \\ h_{1} & ⋯ & h_{s} \\ w_{1} & ⋯ & w_{s} \end{matrix} )

are symbols for the inescapable isomorphisms ϕ and ψ, respectively, then

( \begin{matrix}u_{1} & ⋯ & u_{s} \\ g_{1}h_{1} & ⋯ & g_{s}h_{s} \\ w_{1} & ⋯ & w_{s} \end{matrix} )

is a symbol for ϕψ.

Let us also record the next result (see [35] Lemma 4) which says that a column for ϕ ∈ G_{n,r} is already determined by its top row entry. Note that a similar statement holds with bottom row entry instead of top row entry; simply replace ϕ by ϕ^{−1}.

Lemma 1.4 If

( \begin{matrix}b \\ x \\ c \end{matrix} ) and ( \begin{matrix}b \\ y \\ d \end{matrix} )

are both columns of g ∈ G_{n,r} then x = y and c = d.

Let Γ be the symbol (1.2). Then Γ^{−1} denotes the symbol

( \begin{matrix}c_{1} & c_{2} & ⋯ & c_{s} \\ g_{1}^{−1} & g_{2}^{−1} & ⋯ & g_{s}^{−1} \\ b_{1} & b_{2} & ⋯ & b_{s} \end{matrix} ) ,

and moreover, if ϕ is the element defined by Γ, then ϕ^{−1} is the element defined by Γ^{−1}, by Lemma 1.3.

For symbols Γ and Δ for ϕ respectively ψ we say that the combination ΓΔ exists if bot(Γ) = top(Δ). In this case ΓΔ is the symbol for ϕψ given by Lemma 1.3. Similarly, we say that the combination Γ_{1} ⋯ Γ_{m} of the symbols Γ_{1}, …, Γ_{m} exists if bot(Γ_{k}) = top(Γ_{k+1}) for 1 ≤ k ≤ m − 1 and we identify this combination with the symbol given by repeated application of Lemma 1.3.

Let us focus for a moment on the groups G_{n,r}. We have already noted that ϕ ∈ G_{n,r} has a 1-symbol, Δ say. Since the identity element of G_{n,1} has the 1-symbol

( \begin{matrix}a_{1} & ⋯ & a_{n} \\ 1 & ⋯ & 1 \\ a_{1} & ⋯ & a_{n} \end{matrix} ) ,

it follows that for each column C ∈ Δ, the simple expansion of Δ at C exists. These observations suffice to obtain the following lemma which we will use freely throughout this work.

Lemma 1.5 Let ϕ, ψ ∈ G_{n,r} and suppose ϕ has the 1-symbol Δ, then the following hold.

a) Every expansion Γ of Δ is again a 1-symbol for ϕ and top(Γ) ⪰ top(Δ) as well as bot(Γ) ⪰ bot(Δ).

b) For the finite basis B the following hold

(i) If B ⪰ top(Δ) then ϕ has a 1-symbol Γ with top(Γ) = B.

(ii) If B ⪰ bot(Δ) then ϕ has a 1-symbol Γ with bot(Γ) = B

c) If ψ has the 1-symbol Γ, then there are expansions Δ̂ and Γ̂ of Δ respectively Γ so that the combination Δ̂Γ̂ exists. Moreover, Δ̂ and Γ̂ can be constructed effectively.

As an immediate consequence of Lemma 1.3 and 1.5 c) we see that 1-symbols can be used to compute effectively with elements of the groups G_{n,r} in the sense that for any two elements ϕ and ψ of G_{n,r} there are 1-symbols Γ respectively Δ such that the combination ΓΔ exists, i.e., ΓΔ is a 1-symbol for ϕψ. Since a 1-symbol defines the identity element if and only if it has only trivial columns, we see that the groups G_{n,r} have solvable word problem, i.e., it is effectively decidable whether a given element is trivial.

1.5 Tree Diagrams

Here we describe an alternative way of representing elements of the group G_{n,r}, namely tree diagrams. This approach can also be found in [10]. Since the tree diagrams get quite complex for general n and r, we restrict ourselves to the group G_{2,1} and leave it to the reader to draw examples for the other groups. The main purpose of this section is to encourage the reader to draw tree diagrams whenever he fears to get lost in the symbol notation. Unfortunately, the symbol notation does not give such a good intuitive picture of inescapable isomorphisms as tree diagrams but it is mathematically more rigorous which is why we decided to use it for preference in the following chapters.

For our purpose a graph is a set V, whose elements are called vertices, together with a set E of two-element subsets of V. The elements of E are called edges. We say that v ∈ V and e ∈ E are incident if v ∈ e. A path p in a graph is a sequence v_{0}, v_{1}, …, v_{r} of vertices such that {v_{i}, v_{i+1}} is an edge for 0 ≤ i ≤ r − 1; this path is said to join v_{0} and v_{r}. The path p is called trivial if r = 0 and closed if v_{0} = v_{r}. Furthermore, the path p is said to have a backtracking, if v_{i} = v_{i+2} for some i. A graph is called connected if any two vertices can be joined by a path. Let us mention that there are more complex definitions of a graph, for instance to include multiple edges incident with the same two vertices or loops. Since we are only concerned with forests, we can stick to the simple definition above.

As usual, a graph is called a tree if it is connected and has no non-trivial closed path without backtracking. And a graph is a forest if each connected component is a tree. Let us define a finite rooted binary tree to be a finite tree with precisely one vertex of valency 2, the root, and all other vertices having valency 3 or 1. The vertices of valency 1 are called leaves. (For the general case one would define finite n-ary r-forests, i.e., graphs with r connected components which in turn are finite n-ary rooted trees.) As indicated at the end of Section 1.2, the set of finite bases of W_{2} is in bijection with the set of finite rooted binary trees. Let us agree to draw the root of the tree at the top of the picture of (the geometric realisation of) a rooted binary tree and that for every vertex v the vertices va_{1} and va_{2} are ‘southwest’ respectively ‘southeast’ of v, where ‘north’ is at the top of the page, as usual. This convention allows us to suppress the labels of the vertices in the diagrams. Figure 2, for example, shows the tree corresponding to the basis {a_{1}a_{1}a_{1}, a_{1}a_{1}a_{2}, a_{1}a_{2}, a_{2}a_{1}, a_{2}a_{2}}.

Remark. In the general case, we first order the elements of the alphabet A_{n} and of X_{r} according to their subscripts and then order each basis of X_{r}W_{n} lexicographically. We then draw tree diagrams so that this order corresponds to the order of the leaves read from left to right.

Figure 2

Recall that a finitely based inescapable isomorphism ϕ : S ⟶ T is uniquely determined by its restriction to B_{S} and, what is more, B_{S}^{ϕ} = B_{T}, cf. Section 1.3. Thus we can describe ϕ by drawing the two trees corresponding to B_{S} and B_{T} with the leaves labelled in such a way that b ∈ B_{S} and c ∈ B_{T} have the same label if and only if b^{ϕ} = c and an arrow indicating the range and the domain. We call such an arrangement a tree diagram. For example, the element defined by the symbol

Δ = ( \begin{matrix}a_{1} & a_{2}a_{1} & a_{2}a_{2} \\ 1 & 1 & 1 \\ a_{1}a_{2} & a_{1}a_{1} & a_{2} \end{matrix} )

is the same as the element defined by the tree diagram in Fig. 3.

Figure 3

If B_{S} = B_{T} then ϕ induces a permutation of B_{S}. In this case we sometimes use a tree diagram with only one tree and arrows indicating the action of ϕ. Such an example is given in Fig. 4 for the element defined by the symbol

Δ = ( \begin{matrix}a_{1}a_{1} & a_{1}a_{2} & a_{2} \\ 1 & 1 & 1 \\ a_{1}a_{2} & a_{1}a_{1} & a_{2} \end{matrix} ) .

Figure 4

Expansions of symbols have an obvious analogue in terms of tree diagrams. Let us omit the details and refer to Fig. 5 instead, which illustrates the computation of the product of the element defined by the tree diagram in Fig. 4 with the element defined by the tree diagram in Fig. 3.

Figure 5: Multiplying tree diagrams

We conclude this section with an example indicating how we use labelled tree diagrams to represent elements that are given by symbols with non-trivial middle row entries. Let g_{1}, g_{2}, g_{3} be elements of G_{2,1}. Then Fig. 6 shows the labelled tree-diagram which defines the same element as the symbol

( \begin{matrix}a_{1} & a_{2}a_{1} & a_{2}^{2}a_{1} & a_{2}^{3} \\ g_{1} & g_{2} & g_{3} & 1 \\ a_{1}a_{2}a_{1} & a_{1}^{2} & a_{2} & a_{1}a_{2} \end{matrix} ) .

Figure 6

Subgroups: Part I

In this chapter we present a selection of known results about groups of finitely based maximal inescapable isomorphisms. The main focus is on simple groups and what kind of subgroups they may have. In Sections 2.3 and 2.5, however, we obtain at least some unpublished, although maybe well known, results. The final section consists of a proof that each G_{n,r} is generated by two elements. This appears to be new as well.

2.1 Some ‘Classical’ Subgroups and Simplicity

In this section we define the groups F_{n,r} and T_{n,r} which, for n = 2, r = 1, were also studied by Thompson [40]. Their generalisations were introduced by Brown [7]. Since we only work inside the groups G_{n,r} in this section, ‘symbol’ always means ‘1-symbol’.

Recall that we can equip each finite basis with the lexicographic order as in the remark in Section 1.5, and we write u < v if u comes before v in a lexicon. This convention rules only in this section where the ‘prefix order’ of Section 1.2 is not used. The first subgroup that comes to mind with this definition is the group F_{n,r} of order preserving elements of G_{n,r}. More precisely, g ∈ F_{n,r} if and only if for all u, u′ in the domain of g, u < u′ implies u^{g} < u^{′g}. Equivalently, if Δ is a symbol for g, then the orders of the columns induced by the orders of the top respectively bottom row are the same. It is straightforward to check that this definition is independent of the chosen symbol, so F_{n,r} is really a subgroup. Moreover, F_{n,r} is torsion-free, as can be verified directly. But it also follows from Proposition 4.5, by noting that an element g of F_{n,r} with a symbol Δ satisfying top(Δ) = bot(Δ) must be trivial.

Let us advance a little and define the group T_{n,r} as the set of all elements of G_{n,r} that preserve the order cyclically. By this we mean that, whenever

( \begin{matrix}u_{1} & ⋯ & u_{s} \\ 1 & ⋯ & 1 \\ v_{1} & ⋯ & v_{s} \end{matrix} )

is a symbol for g ∈ T_{n,r} with u_{1} < u_{2} < ⋯ < u_{s}, then there is j ∈ {1, …, s} such that v_{j} < v_{j+1} < ⋯ < v_{s} < v_{1} < ⋯ < v_{j−1}. One can check that this holds for all symbols for g if it holds for one symbol for g, so T_{n,r} is indeed a subgroup. It is clear that F_{n,r} ⊂ T_{n,r} ⊂ G_{n,r}

Remark. The group F_{2,1} is especially interesting because it appears naturally in various branches of mathematics, e.g. [13],[21]. It has particularly attracted attention in connection with the Day problem concerning amenable groups (for amenable groups see, for example, [11],[12],[41]). We do not want to go into details here, but like to mention that it is not known if F_{2,1} is amenable. Both, an affirmative and a negative answer, would be interesting. If it was amenable, then it would be a finitely presented not elementary amenable group, otherwise it would be a finitely presented non amenable group without non-abelian free subgroups, cf. [10]. However, it seems to be very difficult to decide if F_{2,1} is amenable. All the known criteria do not apply. At this point we should mention that a finitely presented amenable but not elementary amenable group was constructed recently by Grigorchuk in [19], as an HNN-extension of the group G_{ω}, where ω = 012012 ⋯ and p = 2 (see Section 4.3 for the definition). Apart from the groups H_{f,p} and H_{f,p}′ of Section 4.4 this is the only finitely presented group having a Grigorchuk group as a subgroup known (to us), and we would like to point out that it is not clear if similar methods work for groups G_{ω′}, where ω′ is an arbitrary recursively enumerable sequence. The reason is that the proof uses an explicit presentation of the group G_{ω}, whereas no explicit presentations are known in the general case. Let us also remark that the group T_{2,1} appears surprisingly in Teichmüller Theory as the universal Ptolémée group, cf. [26].

We proceed with the description of another important subgroup of G_{n,r}; its commutator subgroup. It is plain that every element of G_{n,r} can be written as a product of an order preserving element and a permutational element, i.e., an element having a symbol Δ with top(Δ) = bot(Δ). Such a symbol is called flat. An element is said to be even if its associated permutational element has a flat symbol inducing an even permutation in its top row, i.e., the permutation can be written as product of an even number of 2-cycles. We note that for even n every element is even which follows basically from Fig. 7. This figure also indicates that the definition of an even element is independent of the choice of symbol if n is odd.

Figure 7 It is not difficult to check that the set of even elements is actually a subgroup of G_{n,r}, and the following was shown in [24].

Lemma 2.1 The commutator subgroup of G_{n,r} coincides with the set of even elements, in particular, its index is the highest common divisor of 2 and n − 1.

The commutator subgroups of F_{n,r} and T_{n,r}, as well as the second derived subgroup of the latter, are described in detail in [7] and we do not give these results here. We conclude this section with a result proved by Thompson for G_{2,1}, by Higman for G_{n,r}, and for T_{n,r} by Brown ([40],[24],[7]). Before we state that result, let us mention that F′_{n,r} is also a simple group, but not finitely generated. In contrast, F_{n,r} is finitely presented.

Theorem 2.2 For all integers n ≥ 2 and r ≥ 1, the commutator subgroup of G_{n,r} and the second derived subgroup of T_{n,r} are finitely presented (infinite) simple groups.

2.2 Thompson’s Lemma

The result of this section could be considered the key to the constructions of more finitely presented simple groups in Chapter 4. It was proved by Thompson [40] for n = 2, r = 1. Scott adapted the proof for general n and r = 1 in [35]. We give a somewhat sketchy proof which we hope is more transparent than the proof in [35], although it follows the same lines. From now on ‘<’ denotes again the ‘prefix order’ defined in Section 1.2.

Lemma 2.3 Every subgroup H of G_{n,r} which contains the commutator subgroup of G_{n,r} has a simple commutator subgroup, for all n, r ∈ IN, n ≥ 2.

Proof. To begin with let ν be a non-trivial element of G_{n,1}. Then there are w, v ∈ X_{r}W_{n} such that w^{ν} = v ≠ w and {w, v} is an independent set. To see this assume that w^{ν} = v ≠ w but v < w, then the basis of the domain of ν contains w′ > v with w′ ≠ w, and hence w^{′ν} cannot be ≤-comparable with v, by the definition of inescapable isomorphisms. So w′ and w^{′ν} satisfy the assumptions. If on the other hand w < v, then apply the above argument to ν^{−1} with the roles of v and w interchanged.

Only in this proof we use infinite symbols and columns of infinite symbols for elements of G_{n,r}. They can be defined in the same manner as symbols with ‘bases’ replacing ‘finite bases’. Having only finitely many pages we certainly need to treat them as collections of columns. So suppose ν has an infinite symbol consisting of the columns

( \begin{matrix}w \\ 1 \\ v \end{matrix} ) and ( \begin{matrix}w_{i} \\ 1 \\ v_{i} \end{matrix} ) , i ∈ I,

where w and v satisfy the conditions above and I is some index set. Let β be the element defined by the tree-diagram in Fig. 8 and define α to be the element with an infinite symbol having the columns

( \begin{matrix}w \\ β \\ w \end{matrix} ) and ( \begin{matrix}w_{i} \\ 1 \\ w_{i} \end{matrix} ) , i ∈ I.

Then ν^{−1}αν has the columns

( \begin{matrix}v \\ β \\ v \end{matrix} ) and ( \begin{matrix}v_{i} \\ 1 \\ v_{i} \end{matrix} ) , i ∈ I.

Note that α and ν^{−1}αν are actually different elements of G_{n,r}′ because they induce even permutations. Thus, α^{−1}ν^{−1}αν is a non-trivial element in N ∩ G_{n,r}′, where N is the normal closure of ν. Using the fact that G_{n,r}′ is a simple group, we have shown that every non-trivial normal subgroup N of H contains G_{n,r}′.

Figure 8

Suppose now that H satisfies the hypothesis of the lemma and let N be a non-trivial normal subgroup of H. In the next paragraph we show that H/N is abelian, i.e., H′ ⊂ N. This completes the proof by the following argument. Since H′ is a group satisfying the hypotheses of the lemma (G_{n,r}′ is non-abelian and simple), each of its non-trivial normal subgroups contains H′′. But H′′ is normal in H, and therefore equal to H′. Take two elements, ϕ and χ say, in H. To prove that they commute modulo N, we may, by the above arguments, multiply them with elements of G_{n,r}′ and show that these altered elements commute. Let us go back to the situation of the first paragraph of the proof. There is certainly an element γ in G_{n,r}′ with v^{γ} = w, so w^{νγ} = w. Hence we can assume that ϕ and χ both have a fixed point. Suppose y^{χ} = y. Finally, one can now find an element δ ∈ G_{n,r}′ such that δ^{−1}ϕδ acts non-trivial on elements in yW_{n} only. It follows that δ^{−1}ϕδ and χ commute, and the proof is complete.

2.3 Obvious Subgroups of G_{n,r}

For a start, let us state explicitly that every finite group is a subgroup of any G_{n,r}; simply let it act as a permutation group on a sufficiently large finite basis. Recall that a group is called locally finite if every finitely generated subgroup is finite. The following lemma was already established by Higman in [24]. It is proved roughly like this: if the finite group K acts regularly on the independent set S_{1}, and if S_{k} is the independent set obtained from S_{k−1} by simply expanding each element of S_{k−1}, then K acts on S_{k} in the same manner as in its diagonal action on S_{1}^{k}, the direct product of k copies of S_{1} (S_{1}^{k} is not inside X_{r}W_{n}, but S_{k} is). So if K is a subgroup of index k in the group H, then we can let H act regularly on S_{k} so that the induced action of K viewed as a subgroup of H is precisely that coming from the original action of K on S_{1}. Iterating this process, each direct limit of countably many finite groups can be embedded in G_{n,r}. But a countable locally finite group is exactly such a direct limit.

Lemma 2.4 Every countable locally finite group can be embedded in G_{n,r} for all n ≥ 2, r ≥ 1.

The proof of the next lemma could safely be left as an exercise but the result also follows from the more general Corollary 3.2, by noting that G_{n,r} is 1-expansible.

Lemma 2.5 The class of subgroups of G_{n,r} is closed under countable restricted direct products (see Section 1.1 for the definition) and finite extensions.

There are also numerous embeddings between the groups G_{n,r} for different choices of n and r, and we only mention a few. For example, the stabiliser of x_{1} in G_{n,r} is clearly isomorphic to G_{n,r−1} for r ≥ 2. We have already shown that G_{n,r} is embeddable in G_{n,1} (Section 1.4). Let us now show that G_{n,1} can be embedded in G_{2,1} for all n ≥ 3. Define b_{i+1} = a_{2}^{i}a_{1}, 0 ≤ i ≤ n − 2, and b_{n} = a_{2}^{n−1}. Then {b_{i} | 1 ≤ i ≤ n} is a basis of W_{2}; denote it by B. For w ∈ W_{n} define w^{∗} ∈ W_{2} as the element obtained from w by replacing each letter a_{i} by b_{i} for 1 ≤ i ≤ n. It follows that every basis C of W_{n} corresponds to a basis C^{∗} in W_{2} under this identification, as an easy induction on the number of simple expansions needed to get from {a_{1}, …, a_{n}} to C shows. So given an element g of G_{n,r}, with symbol Δ say, we can replace all its top and bottom row entries by their *-images to obtain a symbol Δ^{∗} defining an element g^{∗} of G_{2,1}. It is straightforward to check that this defines an embedding. So G_{2,1}, although it might look like the ‘smallest’ group among the G_{n,r} in some sense, contains all the others as subgroups.

There are also some isomorphisms between the groups G_{n,r}. For instance, it is not so difficult to see that G_{n,r} is isomorphic to G_{n,r′} whenever r and r′ are congruent modulo n − 1 (see [24]). In [24] Higman proved that G_{n,r} is not isomorphic to G_{n′,r′} if n ≠ n′. However, the isomorphism problem for the groups G_{n,r} is still open; e.g., it is not known if G_{40,1} and G_{40,7} are isomorphic. The remainder of this section is concerned with the Houghton groups H_{m} which were introduced by Houghton in [25]. See also [27], [42]. We learned about this group in conversations with J. Harlander and from the paper [7] by Brown which caught our attention with the simplicity results quoted in the first section of this chapter. The main purpose of that paper, however, was to show in a unified way that the groups F_{n,r}, T_{n,r}, T′′_{n,r}, G_{n,r}, and G_{n,r}′ are all of type F P_{∞} and finitely presented. In fact, that paper also shows this for some other subgroups of G_{n,r}, which we do not want to define here. That F_{n,r} is of type F P_{∞} was first shown by Brown and Geoghegan in [8]. A group G is said to be of type F P_{n} (resp. F P_{∞}) if the ZZG-module ZZ has a projective resolution which is finitely generated in dimensions ≤ n (resp. in all dimensions), cf. [6]. Brown shows in [7] that the Houghton group H_{m} is of type F P_{m−1} but not F P_{m} and finitely presented if m ≥ 3. Before giving some additional remarks, we define the Houghton groups and show that they are embeddable in G_{n,r}. This seems to be new. Let m ≥ 1 be an integer, and define S = IN × {1, …, m}. Think of S as the disjoint union of m copies of IN, each arranged along a ray emanating from the origin in the plane (see Fig. 9). The Houghton group H_{m} is the group of all permutations of S which are eventually translations on each ray. More precisely, if h ∈ H_{m}, then there are integers l_{i}, 1 ≤ i ≤ m, such that

(k, i)^{h} = (k + l_{i}, i)  (2.1)

for all sufficiently large k ∈ IN and all admissible i. Note that ∑_{i=1}^{m} l_{i} must be zero, and that H_{m} contains the finitary symmetric group on the set S for every m ≥ 1; that is all permutations fixing all but finitely many s ∈ S. For m ≥ 3, H_{m} is generated by

h_{i} = \{ \begin{matrix}(k, i) ⟼ (k − 1, i), & if k ≥ 2 \\ (k, i + 1) ⟼ (k + 1, i + 1), & if k ≥ 2 \\ (1, i) ⟼ (1, i + 1) \\ (k, j) ⟼ (k, j), & if j ∉ \{i, i + 1\} \end{matrix}

for 1 ≤ i ≤ m−1 (see Fig. 9). For [h_{2}^{−1}, h_{1}] is the transposition ((1, 2), (2, 2)) which together with all its conjugates under the h_{i} generates the finitary symmetric group F on S, and it is not difficult to see that F and the h_{i} generate every permutation of S satisfying (2.1).

Proposition 2.6 For all integers m ≥ 1, the Houghton group H_{m} is a subgroup of any G_{n,r}.

Figure 9

Proof. For simplicity we prove this for G_{2,1}, only. The general case is similar. It is clear that H_{1} is isomorphic to the finitary symmetric group on a countable set. Let B be a countable basis of W_{2} and observe that the finitary symmetric group on B is in fact a subgroup of G_{2,1}. This proves the case m = 1. It is also not difficult to see that H_{2} is isomorphic to the semidirect product of the finitary symmetric group on ZZ with the infinite cyclic group generated by the ‘shift’ s : z ⟼ z +1, z ∈ ZZ. Now let B be the basis {a_{1}^{i}a_{2}, a_{2}^{i}a_{1} | i ∈ IN} whose lexicographic order is order-isomorphic to that of ZZ in its natural order, and let α be the element defined by the tree diagram in Fig. 10. Then α induces the shift s. Let K ⊂ G_{2,1} be the finitary symmetric group on B, and put H = ⟨K, α⟩. Then K is normal in H, and it is clear that restricting the action of H to B induces a homomorphism from H onto H_{2}. Suppose kα^{t} ∈ H lies in the kernel of this homomorphism, where k ∈ K. Since k affects only finitely many elements of B, we must have t = 0, which in turn implies k = 1. The case m = 2 is now complete.

Figure 10

Now let m ≥ 3, and define

\begin{aligned}ϕ : & S ⟶ W_{2} \\ & (i, j) ⟼ a_{2}^{j−1}a_{1}^{i}a_{2} . \end{aligned}

Observe that ϕ is injective and, moreover, S^{ϕ} ∪ {a_{2}^{m}} is a basis (see Fig. 11). Let g_{1} ∈ G_{2,1} be the element with tree diagram

,

and, for 2 ≤ i ≤ m − 1, define g_{i} ∈ G_{2,1} to be the element whose only non-trivial column is

( \begin{matrix}a_{2}^{i−1} \\ g_{1} \\ a_{2}^{i−1} \end{matrix} ) .

It is straightforward to check that ϕg_{i}ϕ^{−1} = h_{i} for 1 ≤ i ≤ m−1. Since all g_{i} fix a_{2}^{m} and ϕ is a bijection between S and S^{ϕ}, we get that G = ⟨g_{1}, …, g_{m−1}⟩ is a subgroup of G_{2,1} isomorphic to H_{m} (observe that an element element of G is trivial if and only if it fixes S^{ϕ} pointwise). The proof is complete.

Figure 11

2.4 Restrictions on Subgroups

This section is about groups that cannot be embedded in any group G_{n,r}, and it therefore motivates and justifies the search for more finitely presented simple groups. The first serious restriction on subgroups of the groups G_{n,r} was encountered by Higman [24]. Let us recall that the rank of an abelian group is the minimal integer r such that every finitely generated subgroup is generated by r elements.

Theorem 2.7 Let n ≥ 2 and r ≥ 1 be integers. Let A ⊂ G_{n,r} be torsion-free abelian group of finite rank. Then A is free and its centraliser in G_{n,r} has finite index in its normaliser in G_{n,r}. Consequently, G_{n,r} has no subgroup isomorphic to SL_{3}(ZZ).

Another, rather strong, restriction on torsion-free subgroups is implicit in the next theorem which was also proved by Higman [24]. Recall that a root of an element g of a group G is an element h ∈ G such that h^{t} = g for some t ∈ IN.

Theorem 2.8 An element g of G_{n,r} of infinite order does not have arbitrarily large roots, i.e., there is a bound on the t for which there may exist h ∈ G_{n,r} with h^{t} = g.

As a consequence of this the additive group of the rationals is not embeddable in any G_{n,r}. Also certain Baumslag-Solitar groups BS(m, l) with l ≠ m are excluded as subgroups by this theorem. The group BS(l, m) is generated by two elements a and b subject to the single defining relation b^{−1}a^{l}b = a^{m}. Suppose that l = mk for some integer k. Then, if we write a_{i} = a^{b^{i}}, i ∈ ZZ we have a_{i}^{l} = a_{i−1}^{m} and thus

a_{0}^{m} = a_{1}^{mk} = a_{2}^{mk^{2}} = (a_{i}^{m})^{k^{i}},

which implies that a^{m} has arbitrarily large roots.

The last result can be contrasted with the following observation.

Lemma 2.9 In G_{n,r}, every element of finite order has n^{i}-th roots for all i ≥ 0.

Proof. It certainly suffices to show that every element g of finite order has an n-th root. It is shown in Proposition 4.5 that g has a symbol Δ with top(Δ) = bot(Δ), so that g induces a permutation of top(Δ). Each cycle of this permutation corresponds to n cycles in top(Γ) when Γ is the symbol obtained from Δ by simply expanding all columns. So there is an element h in the symmetric group on top(Γ) whose n-th power induces exactly the same cycles in top(Γ) as g, i.e., h^{n} = g, as required.

In Section 4.2 we establish another restrictive result (Theorem 4.8). It is about torsion subgroups and gives as a special case the following.

Theorem 2.10 Every torsion subgroup of G_{n,r} is locally finite.

Together with Theorem 2.4 this gives a complete characterisation of torsion subgroups of G_{n,r}; they are precisely the countable locally finite groups.

2.5 Ping-Pong and some Free Products

In [37] Scott gives an example of a non-abelian free subgroup of G_{2,1} due to Higman. In this section we prove a probably well known Ping-Pong Lemma and give some examples of subgroups of G_{n,r} to which it applies.

Lemma 2.11 (Ping-Pong Lemma) Let G be a group acting faithfully on a set X by permutations. Let H and K be subgroups of order at least three of G, and assume X_{H} and X_{K} are disjoint non-empty subsets of X satisfying the following condition.

(PP) If h and k are non-trivial elements of H respectively K, then X_{K}^{h} ⊂ X_{H} and X_{H}^{k} ⊂ X_{K}.

Then the subgroup of G generated by H and K is isomorphic to the free product of H with K.

Proof. By the normal form theorem for free products (see for example [28]) we only have to show that no word of the form h_{1}k_{1} ⋯ h_{n}k_{n}, defines the trivial element, where 1 ≠ h_{i} ∈ H, 1 ≠ k_{i} ∈ K, with the only possible exceptions being h_{1} and k_{n} but not both if n = 1. First suppose that h_{1} ≠ 1 and k_{n} = 1. Then condition (PP) implies that x^{h_{1}k_{1}···h_{n}} ∈ X_{H} for all x ∈ X_{K}, whence h_{1}k_{1} ⋯ h_{n} cannot be trivial. A similar argument (this time with x ∈ X_{H}) applies if h_{1} = 1 and k_{n} ≠ 1. If, on the other hand, h_{1} and k_{n} are both non-trivial, then we can conjugate by some h ∈ H with h ≠ h_{1} (|H| > 2) to get to the first case. The case h_{1} = k_{n} = 1 is reduced to the first case again by conjugation, and the lemma is proved.

Corollary 2.12 The group G_{n,r} has non-abelian free subgroups of every countable rank for every n ≥ 2 and r ≥ 1.

Proof. We restrict ourselves to G_{2,1}, the general case being similar. Since the free group of rank two contains free groups of every countable rank, it suffices to find two elements a, b ∈ G_{2,1} which freely generate a free subgroup. Define a and b by the tree diagrams in Fig. 12. To have a permutation action of G_{2,1} we consider its induced action on the set of ends X of the infinite rooted binary tree, i.e., all infinite sequences with values in {a_{1}, a_{2}}. Then we apply the Ping-Pong Lemma with G = G_{2,1}, H = ⟨a⟩, K = ⟨b⟩, X_{H} = a_{2}X, and X_{K} = a_{1}X.

Figure 12

Remark. Observe that a and b are both cyclically order preserving so that, in fact, T_{2,1} has free subgroups. This should be compared with Corollary 4.9 of [10] saying that F_{n,r} has no non-abelian free subgroups. Note also that these generators are a little easier than those in [37].

Corollary 2.13 Every free product of finitely many finite groups is embeddable in G_{n,r} for any choice of n ≥ 2 and r ≥ 1.

Proof. We show that for every finite group F, the free product of F with the infinite cyclic group generated by the element a defined in Fig. 12 is embeddable in G_{2,1}. This suffices, for we can take F to be the direct product of the given finite groups, F_{1}, …, F_{t} say, and it then follows from the normal form theorem for free products that the subgroup ⟨F_{i}^{a^{i}} | 1 ≤ i ≤ t⟩ of F ∗ ⟨a⟩ is isomorphic to F_{1} ∗ ⋯ ∗ F_{t}. Let s be the order of F and let B be the basis {a_{1}^{i}a_{2} | 0 ≤ i ≤ s − 2} ∪ {a_{1}^{s−1}}. Choose a bijection between B and F so that a_{2} corresponds to the identity and consider the group K of permutations of B which is induced by the right regular representation of F on itself and this bijection. Now the Ping-Pong Lemma applies with G = G_{2,1}, H = ⟨a⟩, K, and X, X_{H} and X_{K} as in the proof of Corollary 2.12.

Remark. This result follows in a more indirect way from the fact that every free product of finitely many finite groups has a free subgroup of finite index (see for example [14]) together with Corollary 2.12 and Lemma 2.5

Corollary 2.14 The free product of an infinite cyclic group with the direct product of finitely many finite and finitely generated free abelian groups is embeddable in G_{n,r} for any choice of n ≥ 2 and r ≥ 1.

Proof. Let H_{1}, …, H_{r} be a finite family of finitely generated free abelian groups and finite groups of order at least three. Let K_{i} = ⟨x_{i}⟩ be infinite cyclic groups for 1 ≤ i ≤ r. Suppose that all these groups act on the same set X and that for 1 ≤ i ≤ r there are subsets X_{H_{i}}, X_{K_{i}} of X such that condition (PP) holds for every pair (H_{i}, K_{i}). Assume in addition that for every i, 1 ≤ i ≤ r, H_{i} and K_{i} both fix ⋃_{j≠i}(X_{H_{j}} ∪ X_{K_{j}}) pointwise. Then we claim that the group M ⊂ Sym(X) generated by the H_{i} and x_{1}x_{2} ⋯ x_{r} is isomorphic to (H_{1} × ⋯ × H_{r}) ∗ ZZ. It is clear from the assumptions that [h_{j}, h_{i}] = [h_{j}, k_{i}] = [k_{j}, k_{i}] = 1 for all h_{l} ∈ H_{l}, k_{l} ∈ K_{l} and 1 ≤ i ≠ j ≤ r. So the group H generated by the H_{i} is isomorphic to X_{i=1}^{r}H_{i}. Put k = x_{1}x_{2} ⋯ x_{r} and K = ⟨k⟩ and let w = h_{1}k_{1} ⋯ h_{t}k_{t} be a non-trivial word with h_{i} ∈ H, k_{i} ∈ K. We have to show that w is not the identity. If t = 1 and either h_{1} or k_{1} are trivial this is obvious. Otherwise w contains some nontrivial h_{i} which we may assume is h_{1} after possibly conjugating w. Now h_{1} can be assumed to be a word l_{1} ⋯ l_{s} with l_{j} ∈ H_{j} and clearly l_{q} ≠ 1 for some q. Conjuagating w again we may now assume that k_{t} = 1 and h_{n} contains some l′_{q} ∈ H_{q}. Now consider X_{K_{q}}^{w}. By the hypothesis, only elements of H_{q} and k must be taken into account to see that X_{K_{q}}^{w} ⊂ X_{H_{q}}. Finally, to see that such a construction can be done inside G_{n,r} use Corollary 2.12 and 2.13 and put such constructions further down in the tree to create space in order to meet our conditions above on fixed points. Note that the assumption on the orders of the finite groups is no problem, since we can consider the group we are looking for as a subgroup of a group satisfying these conditions. This completes the proof.

2.6 Generators for G_{n,r}

For future reference we include here some remarks on generating sets for the groups G_{n,r} and G_{n,r}′. It was shown by Mason [30] that G_{n,r}′ can be generated by two elements. He assumed that 1 < r ≤ n which is no restriction, as G_{n,r} is isomorphic to G_{n,r+n−1} (see Section 2.3). The elements needed are all defined in Appendix B which can be folded out to be visible while reading here. This Appendix is also used in Section 4.5, and the dashed lines in the tree diagrams play a role then, but should be ignored for the time being. Mason proved that ab and c generate G_{n,r}′. We show that G_{n,r} can also be generated by two elements. By Lemma 2.1, only for odd n is there something to prove. Observe, that cbc^{−1} is a single cycle, y say, in the symmetric group S on {x_{j}a_{i} | 1 ≤ j ≤ r, 1 ≤ i ≤ n} fixing at most x_{1}a_{1}. So y and â generate S which includes a, and hence ⟨a, b, c⟩ ⊂ ⟨â, b, c⟩. Since â and b commute and have coprime finite orders, ⟨â, b⟩ = ⟨âb⟩. (This is also true for a in place of â.) Hence, ⟨âb, c⟩ = G_{n,r}, because â is not even, if n is odd.

Expansibility and Fake Expansibility

This chapter lays the ground for the constructions in Chapter 4. In the first half we record without proofs the main results of [35]. Those are the definition of E-expansible groups, a presentation for E-expansible groups and the θ-construction. In the second part we introduce fake-E-expansibility as a generalisation of E-expansibility and then we prove that certain fake-E-expansible groups are finitely presented if E is finitely presented.

3.1 Expansibility

In [35] Scott introduced the notion of E-expansibility in order to show that certain subgroups of G_{n,1} are finitely presented. Let us state an equivalent definition of E-expansibility.

Let E and H be subgroups of G_{n,1} with E ⊂ H. Then H is called Eexpansible if there exists a generating system Y for H such that, if h is in H and h = y_{1} ⋯ y_{m} with y_{i} ∈ Y^{±1} for 1 ≤ i ≤ m, then there are Esymbols Γ_{1}, …, Γ_{m} for y_{1}, …, y_{m}, respectively, such that the combination Γ_{1} ⋯ Γ_{m} exists. Thanks to Lemma 1.3, this combination is an E-symbol for h, in particular, every element of H has an H-symbol. The idea behind this definition is that all relations which hold in H can be expressed in terms of E-symbols, and hence H can be investigated by studying E-symbols.

The main result of Scott [35] gives an explicit description of a set of defining relations for an E-expansible group H, when H contains G_{n,1}. As we are going to use it in the following chapter, we recall now the main features of that result whose actual statement comes only in the following section.

As in [35] we denote subgroups of G_{n,1} which contain G_{n,1} by capital script letters. We consider the following situation: H is a subgroup of G_{n,1}, H = ⟨G_{n,1}, H⟩ is the subgroup of G_{n,1} generated by G_{n,1} and H.

For g ∈ G_{n,1} define σ_{g} to be the element with symbol

( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{n} \\ g & 1 & ⋯ & 1 \\ a_{1} & a_{2} & ⋯ & a_{n} \end{matrix} ) .

It is easy to see that H^{∗} = {σ_{h} | h ∈ H} is a subgroup of G_{n,1} isomorphic to H (Lemma 7 in [35]). Let us also recall the following lemma which is Lemma 8 in [35] for which we indicate a tree-diagram proof. We hope that this is more enlightening than the original proof.

Lemma 3.1 If H is H-expansible, then ⟨G_{n,1}, H^{∗}⟩ and H are equal.

Sketch of proof. Let h ∈ H. Thanks to the H-expansibility of H, h has arbitrarily large H-symbols, for αh can be expressed as a combination of H-symbols for all α ∈ G_{n,1}. The example in Fig. 13 shows how to prove h ∈ ⟨G_{n,1}, H^{∗}⟩. Note that a ∈ G_{n,1} and that the element in the second row of that figure is an element of ⟨G_{n,1}, H^{∗}⟩.

Figure 13

Since h_{3} is an inescapable isomorphism, using the argument above, it has an H-symbol with at least one trivial middle row entry. Assume, for example, h_{3} has the tree-diagram in Fig. 14.

Figure 14

Then h has the tree-diagram in Fig. 15.

Figure 15 Now, let g and k be the elements defined in Fig. 16 and check that ghk = σ_{h}. So H^{∗} ⊂ ⟨G_{n,1}, H⟩ and our sketch of the proof is complete.

Figure 16

Corollary 3.2 If H is H-expansible, then the following hold.

(i) Every H-symbol defines an element of H.

(ii) The class of subgroups of H is closed under restricted direct products of countable families and finite extensions.

Proof. As can be seen from the proof of the lemma, every H-symbol is the combination of finitely many conjugates of H-symbols for elements of H^{∗} with a symbol for an element of G_{n,r}. This proves (i). Furthermore, from the proof of the lemma together with (i), we get that for every subgroup U of H, U^{∗} is a subgroup of H. So given a countable family U_{1}, U_{2}, … of subgroups of H, we can “place them below the vertices of an infinite basis” as indicated in Fig. 17 below. It is clear that this gives a subgroup of G_{n,1} isomorphic to the direct product of the U_{i}. Since the elements of the restricted direct product have finite supports, they have H-symbols, and the first part of (ii) is proved.

Figure 17

The second part of (ii) follows from the well known embedding theorem of Krasner and Kalužnin (see for example [33]), stating that every extension of a group G by a group H is isomorphic to a subgroup of the standard wreath product of G with H, cf. Section 1.1. Since the direct and restricted direct product of a finite family are indistinguishable, the corollary follows from the first part of (ii) and the fact that the symmetric group of any finite basis is a subgroup of G_{n,1}.

3.2 A Presentation for Expansible Groups

In this section we complete the description of the main result of [35], stated here as Theorem 3.3. A set {η_{2}, …, η_{s}} of elements of G_{n,1} is said to be of type s if there is a basis B = {a_{1}, w_{2}, …, w_{s}} such that η_{i} naturally corresponds to the involution (a_{1}, w_{i}) in SymB, the symmetric group on the set B.

We now define four sets A, B, C, and D of relations. The relations in B, C, and D are written in terms of general elements of G_{n,1} and H^{∗}, not just on elements of a chosen generating set. The elements are considered as ‘shorthand’ notation for the words on the chosen generating set to which they correspond. Since we have relations A, it does not matter which of the words a particular element of G_{n,1} or H^{∗} is taken to represent. Usually a generating set X ∪ Y will be used, where X and Y are finite generating sets for G_{n,1}, respectively H^{∗}.

Relation-set A. This consists of a fixed set of defining relations of G_{n,1} and a fixed set of defining relations of H^{∗} with respect to the chosen generating sets.

Relation-set B. Let F denote the subgroup of G_{n,1} that fixes all words of the form a_{1}w, w ∈ W_{n}. Then B = {ασ_{h} = σ_{h}α | h ∈ H, α ∈ F }.

Relation-set C. Let δ be the element with symbol

( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{n−1} & a_{n}a_{1} & a_{n}a_{2} & ⋯ & a_{n}a_{n} \\ 1 & 1 & ⋯ & 1 & 1 & 1 & ⋯ & 1 \\ a_{n}a_{1} & a_{2} & ⋯ & a_{n−1} & a_{1} & a_{n}a_{2} & ⋯ & a_{n}a_{n} \end{matrix} ) .

Then C = {δσ_{h}δσ_{h′} = σ_{h′}δσ_{h}δ | h, h′ ∈ H}.

Relation-set D. Let h ∈ H and let

Γ = ( \begin{matrix}u_{1} & ⋯ & u_{s} \\ h_{1} & ⋯ & h_{s} \\ v_{1} & ⋯ & v_{s} \end{matrix} )

be an H-symbol for σ_{h}. Let S = {η_{2}, …, η_{s}} be a set of type s with corresponding basis {a_{1}, w_{2}, …, w_{s}} and define τ and ϵ by the symbols

( \begin{matrix}u_{1} & u_{2} & ⋯ & u_{s} \\ 1 & 1 & ⋯ & 1 \\ a_{1} & w_{2} & ⋯ & w_{s} \end{matrix} ) and ( \begin{matrix}a_{1} & w_{2} & ⋯ & w_{s} \\ 1 & 1 & ⋯ & 1 \\ v_{1} & v_{2} & ⋯ & v_{s} \end{matrix} ) ,

respectively. Furthermore, let R_{h,Γ,S} denote the relation

σ_{h} = τσ_{h_{1}}η_{2}σ_{h_{2}} ⋯ η_{s}σ_{h_{s}}η_{s} ⋯ η_{2}ϵ.  (3.1)

Then D is the set of relations R_{h,Γ,S} for all possible choices of subscripts.

Define the set χ of relations to be A ∪ B ∪ C ∪ D.

Theorem 3.3 (Scott) Let H be a subgroup of G_{n,1}. If H = ⟨G_{n,1}, H⟩ is H-expansible, then the set χ of relations is a set of defining relations for H. Moreover, if H is finitely presented, then A ∪ B ∪ C is finitely based, i.e., there is a finite subset of A ∪ B ∪ C which implies all the relations in A ∪ B ∪ C.

Before we recall a construction due to Scott for obtaining H-expansible groups in the next section, we give an example showing how restrictive expansibility is. Observe that H must be H-expansible if H is H-expansible.

Example. Define H to be the group of order two generated by the element h defined by the H-symbol

( \begin{matrix}a_{1}^{2} & a_{1}a_{2} & a_{2} \\ h & 1 & 1 \\ a_{1}^{2} & a_{2} & a_{1}a_{2} \end{matrix} ) .

Then H is clearly H-expansible, but H is not, for hσ_{h} has no H-symbol. This is because every H-symbol for h has a column

( \begin{matrix}a_{1}^{2k} \\ h \\ a_{1}^{2k} \end{matrix} ) ,

whereas every H-symbol for σ_{h} has a column

( \begin{matrix}a_{1}^{2k+1} \\ h \\ a_{1}^{2k+1} \end{matrix} ) ,

for k ≥ 0. So hσ_{h} cannot have an H-symbol which is the combination of H-symbols for h respectively σ_{h}. Observe that σ_{h} is indeed an element of H even though Lemma 3.1 does not apply. What is even worse, we cannot define an element h_{1} such that h has the column

( \begin{matrix}a_{1}^{2k+1} \\ h_{1} \\ a_{1}^{2k+1} \end{matrix} )

for some k ≥ 0.

3.3 The θ-Construction

Here we describe a method due to Scott to obtain expansible groups, cf. [35]. In Section 4.2 we prove a general theorem about groups obtained in this fashion. Recall from Section 1.1 the definition of the permutational wreath product. It is clear that for groups A, B, and a permutation group C, each homomorphism φ : A ⟶ B induces an obvious homomorphism A ≀ C ⟶ B ≀ C.

Now consider the following situation. Let F be a finitely generated free group and denote by S_{n} the symmetric group of degree n with its natural action on {1, 2, …, n}. Let F ≀ S_{n} be the permutational wreath product, where F acts on itself via the right regular representation. Suppose we are given a homomorphism θ : F ⟶ F ≀ S_{n}. Then θ induces a homomorphism θ_{1} : F ≀ S_{n} ⟶ F ≀ S_{n} ≀ S_{n}, and iterating this process gives the following commutative diagram of homomorphisms

F ⟶^{θ} F ≀ S_{n} ⟶^{θ_{1}} F ≀ S_{n} ≀ S_{n} ⟶^{θ_{2}} F ≀ S_{n} ≀ S_{n} ≀ S_{n} ⟶^{θ_{3}}
↓ ρ_{1}  ↓ ρ_{2}  ↓ ρ_{1}  ⋯
S_{n}  ⟵^{η_{1}} S_{n} ≀ S_{n}  ⟵^{η_{2}} S_{n} ≀ S_{n} ≀ S_{n}  ⟵^{η_{3}}

where ρ_{i} and η_{i} denote the natural projections. Define ψ_{1} = θρ_{1}, ψ_{i} = θθ_{1} ⋯ θ_{i−1}ρ_{i} for i ≥ 2 and let K_{i} be the kernel of ψ_{i}. Finally put K = ⋂_{i=1}^{∞} K_{i} and H_{θ} = F/K. The following proposition summarises Lemmas 14, 15, and 17, and Theorem 2 of [35].

Proposition 3.4 Let H_{θ} be defined as above. Then there is an embedding of H_{θ} in G_{n+1,1} whose image is denoted by H_{θ} again such that, the group H_{θ} = ⟨G_{n+1,1}, H_{θ}⟩ is H_{θ}-expansible and every element of H_{θ} has a H_{θ}- symbol of the form

( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{n} & a_{n+1} \\ h_{1} & h_{2} & ⋯ & h_{n} & 1 \\ a_{1π} & a_{2π} & ⋯ & a_{nπ} & a_{n+1} \end{matrix} ) ,  (3.2)

where π ∈ S_{n}. Moreover, H_{θ} is finitely presented whenever H_{θ} is finitely presented.

Observe that the special form (3.2) of the H_{θ}-symbols for elements of H_{θ} implies that every (simple) expansion of any H_{θ}-symbol exists, and is again an H_{θ}-symbol. This immediately gives the following result which we state for future reference.

Lemma 3.5 Let Δ and Γ be H_{θ}-symbols for some k ∈ H_{θ}. Suppose that Δ is an expansion of Γ and let B and C be finite bases in W_{n} so that B ⪰ top(Δ) and C ⪰ bot(Δ). Then the following hold.

(i) top(Δ) ⪰ top(Γ) and bot(Δ) ⪰ bot(Γ).

(ii) There are unique H_{θ}-symbols Δ_{1} and Δ_{2} for k such that top(Δ_{1}) = B and bot(Δ_{2}) = C. Furthermore, Δ_{1} and Δ_{2} can be constructed effectively and Δ ⪯ Δ_{1} as well as Δ ⪯ Δ_{2}.

3.4 Fake Symbols and Fake Expansibility

The following definitions are inspired by the results of the last section which roughly say that an expansible group in which the elements have sufficiently well expansible symbols is a good candidate for being finitely presented.

Let S_{n} be the subgroup of G_{n,1} consisting of the elements which have a symbol of the form

( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{n} \\ 1 & 1 & ⋯ & 1 \\ a_{1π} & a_{2π} & ⋯ & a_{nπ} \end{matrix} )  (3.3)

where π is some permutation of the set {1, …, n}. Obviously, S_{n} is isomorphic to the symmetric group of degree n. Let E and H be subgroups of G_{n,1} with E ⊂ H. Then a fake-E-symbol for h ∈ H is a symbol for h of the form

( \begin{matrix}u_{1} & u_{2} & ⋯ & u_{s} \\ x_{1} & x_{2} & ⋯ & x_{s} \\ v_{1} & v_{2} & ⋯ & v_{s} \end{matrix} )

where x_{i} ∈ E ∪ S_{n} for 1 ≤ i ≤ s. Furthermore we call H fake-E-expansible if there exists a set of generators Y for H such that, if h is in H and h = y_{1} ⋯ y_{m} with y_{i} ∈ Y^{±1} for 1 ≤ i ≤ m, then h has a symbol which is the combination Γ_{1} ⋯ Γ_{m} of fake-E-symbols Γ_{1}, …, Γ_{m} for y_{1}, …, y_{m}, respectively. Note that this combination is rather a ⟨E, S_{n}⟩-symbol than a fake-E-symbol. The next two results relate fake expansibility and expansibility.

Proposition 3.6 Let E and H be subgroups of G_{n,1} and E ⊂ H. If H is fake-E-expansible and every e ∈ E has a fake-E-symbol of the form

( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{n} \\ x_{1} & x_{2} & ⋯ & x_{n} \\ a_{1π} & a_{2π} & ⋯ & a_{nπ} \end{matrix} )  (3.4)

for some permutation π (possibly depending on e) of the set {1, …, n}, then H is E-expansible.

Proof. We must show that there is a generating system Y for H such that, if y_{1} ⋯ y_{m} is any word in Y^{±1}, then there are E-symbols Γ_{1}, …, Γ_{m} for y_{1}, …, y_{m}, respectively, such that their combination Γ_{1} ⋯ Γ_{m} exists. To this end let Y be a generating system for H such that H is fake-E-expansible with respect to Y. Let y_{1} ⋯ y_{m} be any word in Y^{±1} and choose fake-E-symbols Γ_{1}, …, Γ_{m} for y_{1}, …, y_{m}, respectively, such that the combination Γ_{1} ⋯ Γ_{m} exists. Observe that all of the Γ_{k} have the same number of columns, C say, and that we can assume (by reordering if necessary) that the bottom row of Γ_{k} is the same as the top row of Γ_{k+1} as ordered sets, for 1 ≤ k ≤ m − 1. Now enumerate the columns of each Γ_{j}, 1 ≤ j ≤ m, from left to right by 1, …, C and apply the following procedure.

Start with Step 1 and stop when you reach Step m + 1 where for 1 ≤ i ∈ IN Step i is defined as follows.

Step i: Let X be the set of all numbers of columns whose middle row entry in Γ_{i} is a non-trivial element of S_{n}.

(a) If X is empty then go to Step i + 1.

(b) If X is not empty do the following. For 1 ≤ j ≤ m simply-expand all the columns of Γ_{j} numbered by some x ∈ X and denote the resulting symbol by Γ_{j} again. Now reorder the columns in Γ_{1}, …, Γ_{m} so that the bottom row of Γ_{k} is equal to the top row of Γ_{k+1} as ordered sets, for 1 ≤ k ≤ m−1. Replace C by C + |X|(n − 1) and go to Step 1.

Note that (3.3) and (3.4) ensure we can execute part (b) and that C will again be the number of columns of each of the Γ_{i}. To prove that the algorithm gives the required result we will show, by induction on i ≤ m + 1, that

(α) Step i will be reached and

(β) at the time of reaching Step i all of the symbols Γ_{1}, …, Γ_{i−1} are Esymbols.

Part (β) holds because the only way to reach Step i is via Step i − 1 part (a), i ≥ 2.

As Step 1 is reached by definition, to prove (α) it suffices to show that Step i will finally lead to Step i + 1, 1 ≤ i ≤ m. First let i = 1. As part (a) of Step 1 leads immediately to Step 2, we only need to check part (b). By the definition of X and (3.3) it is clear that at the end of Step 1 part (b) Γ_{1} is an E-symbol, and the procedure continues with Step 1 part (a) which leads to Step 2.

Now consider i with m ≥ i > 1. Again Step i part (a) leads to Step i + 1. If, on the other hand, we have to execute Step i part (b), then the definition of X and (3.3) show that, at the end of this, Γ_{i} is an E-symbol. Furthermore, using (β), if 1 ≤ c ≤ C and for some j with 1 ≤ j ≤ i − 1 the c^{th} column of Γ_{j} has now a non-trivial middle row entry in S_{n}, then the c^{th} column of Γ_{i} has trivial middle row entry. Thus, while going from Step 1 up to Step i again, only columns with trivial middle row entry in Γ_{i} are affected. Hence, using the induction hypothesis, we will come to Step i part (a) which leads to Step i + 1. This completes the proof of the proposition.

Next we show that with a little more care we can even deduce the Eexpansibility of H = ⟨H, G_{n,1}⟩.

Proposition 3.7 Let E and H be subgroups of G_{n,1} with E ⊂ H and let H be fake-E-expansible. Assume that there is a generating system Y for H such that E ⊂ Y and every y ∈ Y has a fake-E-symbol of the form

( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{n} \\ x_{1} & x_{2} & ⋯ & x_{n} \\ a_{1π} & a_{2π} & ⋯ & a_{nπ} \end{matrix} )

for some permutation π of the set {1, …, n}. Then H = ⟨H, G_{n,1}⟩, the group generated by H and G_{n,1}, is E-expansible.

Proof. In the light of Proposition 3.6, it suffices to prove that H is fake-E-expansible with respect to the generating system Z = Y ∪ G_{n,1}. Let h = z_{1} ⋯ z_{m}, z_{i} ∈ Z^{±1}, 1 ≤ i ≤ m. The proof is by induction on m. If m = 1 it follows from the assumptions that h = z_{1} has a fake-E-symbol. So we assume that there are fake-E-symbols Γ_{1}, …, Γ_{m−1} for z_{1}, …, z_{m−1}, respectively, such that the combination Γ_{1} ⋯ Γ_{m−1} exists.

First let z_{m} ∈ Y. Then z_{m} has a fake-E-symbol Γ of the form (3.4), and as E ⊂ Y, every middle row entry of Γ has such a fake-E-symbol too. An induction on the number of simple expansions needed to go from {a_{1}, …, a_{n}} to bot(Γ_{m−1}) now shows that we can expand Γ to a fake-E-symbol Γ_{m} for z_{m} such that the combination Γ_{1} ⋯ Γ_{m} exists.

In the case z_{m} ∈ G_{n,1}, let Γ be a 1-symbol for z_{m}. Then there is a common expansion U of the two finite bases top(Γ) and bot(Γ_{m−1}). The argument in the proof of Proposition 3.6 also shows that we can expand all the Γ_{k}, 1 ≤ k ≤ m−1, to obtain fake-E-symbols Δ_{k} for z_{k} such that the combination Δ_{1} ⋯ Δ_{m−1} exists and bot(Δ_{m−1}) = U. But there is also an expansion Δ_{m} of Γ with top(Δ_{m}) = U. Hence, the combination Δ_{1} ⋯ Δ_{m} exists and therefore H is fake-E-expansible, as required.

3.5 Presentations for Fake Expansible Groups

This section is entirely devoted to the proof of the following theorem.

Theorem 3.8 Let E, Y, H, and H satisfy the hypotheses of Proposition 3.7. Then H is finitely presented, if E is finitely presented.

To begin with, we show that under the hypotheses of the theorem, H is in fact generated by G_{n,1} and E. Write E = ⟨G_{n,1}, E⟩ and note that E is Eexpansible as a subgroup of the E-expansible group H, cf. Proposition 3.7. So E is the group of all those elements of G_{n,1} that have an E-symbol, by Corollary 3.2. Since all elements of Y (or H if you like) have an E-symbol, H = E.

Now let Z be a finite generating set for E. All what follows will be with respect to the generating set Z^{∗} ∪ G_{n,1} for H. This is a generating set by Lemma 3.1. By Theorem 3.3, χ = A∪B ∪C ∪D is a set of defining relations for H, where A, B, C, and D are the sets of relations defined in Section 3.2. We define three more sets of relations as follows.

Relation-set D′′. Let e ∈ E and let

Γ = ( \begin{matrix}u_{1} & ⋯ & u_{s} \\ x_{1} & ⋯ & x_{s} \\ v_{1} & ⋯ & v_{s} \end{matrix} )

be a fake-E-symbol for σ_{e}. Let S = {η_{2}, …, η_{s}} be a set of type s with corresponding basis {a_{1}, w_{2}, …, w_{s}} and define τ and ϵ by the symbols

( \begin{matrix}u_{1} & u_{2} & ⋯ & u_{s} \\ 1 & 1 & ⋯ & 1 \\ a_{1} & w_{2} & ⋯ & w_{s} \end{matrix} ) and ( \begin{matrix}a_{1} & w_{2} & ⋯ & w_{s} \\ 1 & 1 & ⋯ & 1 \\ v_{1} & v_{2} & ⋯ & v_{s} \end{matrix} ) ,

respectively. Furthermore, let R′′_{e,Γ,S} denote the relation

σ_{e} = τσ_{x_{1}}η_{2}σ_{x_{2}} ⋯ η_{s}σ_{x_{s}}η_{s} ⋯ η_{2}ϵ.

Then D′′ is the set of relations R′′_{e,Γ,S} for all possible choices of subscripts.

Note that this differs from the definition of the set D only in the use of ‘fake-E-symbol’ in place of ‘E-symbol’. But clearly each E-symbol for σ_{e} is also a fake-E-symbol for σ_{e}, so that D ⊂ D′′.

Relation-sets D′ and D̂. Let e ∈ E and let

Γ = ( \begin{matrix}a_{1} & ⋯ & a_{n} \\ x_{1} & ⋯ & x_{n} \\ a_{1π} & ⋯ & a_{nπ} \end{matrix} )

be the fake-E-symbol (3.4) which exists by hypothesis. Let δ be the same element as in the definition of the relation set C and let δ_{i}, 1 ≤ i ≤ n act on the basis

{a_{1}, a_{2}, …, a_{n−1}, a_{n}a_{1}a_{1}, …, a_{n}a_{1}a_{n}, a_{n}a_{2}, …, a_{n}a_{n}}

as the involution that interchanges a_{1} with a_{n}a_{1}a_{i} and fixes all the other elements. We let R′_{e} denote the relation

σ_{e} = δδ_{1}σ_{x_{1}}δ_{2}σ_{x_{2}} ⋯ δ_{n}σ_{x_{n}}δ_{n} ⋯ δ_{1}δσ_{π}.  (3.5)

Then D′ = {R′_{e} | e ∈ E} and D̂ = {R′_{e} | e ∈ Z}.

Remark. As the elements σ_{e}, δ, δ_{i} (1 ≤ i ≤ n) play a significant role throughout the remainder of this section, we have provided reminding tree diagrams in Appendix C which can be folded out.

Observe that D̂ is finite, and our first aim is to show that together with A ∪ B ∪ C it implies D′ (Lemma 3.11). Define χ′ = A ∪ B ∪ C ∪ D′ and χ′′ = A ∪ B ∪ C ∪ D′′. As A ∪ B ∪ C is finitely based, by Theorem 3.3, the theorem will then follow immediately from the next lemma using χ ⊂ χ′′.

Lemma 3.9 Every relation in χ′ is a consequence of relations in χ and each relation in χ′′ is a consequence of relations in χ′.

Before we prove Lemma 3.9 we need a few more facts. The next result is Lemma 12 in [35].

Lemma 3.10 If {η_{2}, …, η_{s}} is of type s and μ is a permutation of the set {m, …, r}, 1 ≤ m ≤ r ≤ s, then the relation

σ_{g_{m}}η_{m+1}σ_{g_{m+1}} ⋯ η_{r}σ_{g_{r}} = α_{μ}σ_{g_{mμ}}η_{m+1}σ_{g_{(m+1)μ}} ⋯ η_{r}σ_{g_{rμ}}β_{μ}

is a consequence of A ∪ B ∪ C, where α_{μ} and β_{μ} have symbols

( \begin{matrix}w_{2} & ⋯ & w_{m} & x_{m} & x_{m+1} & ⋯ & x_{r} & w_{r+1} & ⋯ & w_{s} \\ 1 & ⋯ & 1 & 1 & 1 & ⋯ & 1 & 1 & ⋯ & 1 \\ w_{2} & ⋯ & w_{m} & a_{1} & w_{m+1} & ⋯ & w_{r} & w_{r+1} & ⋯ & w_{s} \end{matrix} ) and

( \begin{matrix}w_{2} & ⋯ & w_{m} & w_{m+1} & ⋯ & w_{r} & a_{1} & w_{r+1} & ⋯ & w_{s} \\ 1 & ⋯ & 1 & 1 & ⋯ & 1 & 1 & 1 & ⋯ & 1 \\ w_{2} & ⋯ & w_{m} & y_{m+1} & ⋯ & y_{r} & y_{r+1} & w_{r+1} & ⋯ & w_{s} \end{matrix} )

(x_{mμ^{−1}} = a_{1}, x_{j} = w_{jμ} (jμ ≠ m), y_{i+1} = w_{iμ+1} (iμ ≠ r)).

Let us record a few relations implied by A ∪ B ∪ C which will be used soon. But first observe that {δ_{1}, …, δ_{n}} is a subset of a set of type 3n − 2. Let S = {η_{2}, …, η_{s}} be any set of type s and e, e′ ∈ E, then the following hold.

η_{i}^{2} = 1  for 2 ≤ i ≤ s  (3.6)
η_{i}η_{j}σ_{e}η_{j} = η_{j}σ_{e}η_{j}η_{i}  for 2 ≤ i ≠ j ≤ s  (3.7)
σ_{e}η_{i}σ_{e′}η_{i} = η_{i}σ_{e′}η_{i}σ_{e}  for 2 ≤ i ≤ s  (3.8)

The definition of a set of type s gives immediately (3.6). Equations (3.7) follow from B and the fact that η_{j}η_{i}η_{j} fixes a_{1} if i ≠ j. Finally, if we assume that {a_{1}, w_{2}, …, w_{s}} is the basis corresponding to S and define τ_{i}, 2 ≤ i ≤ s, to be the element of G_{n,1} given by a symbol whose only non-trivial columns are

( \begin{matrix}a_{n}a_{1} \\ 1 \\ w_{i} \end{matrix} ) and ( \begin{matrix}w_{i} \\ 1 \\ a_{n}a_{1} \end{matrix} ) ,

then τ_{i} fixes a_{1} and τ_{i}η_{i}τ_{i} = δ. Hence (3.8) is a conjugate of a relation in C under τ_{i}.

Lemma 3.11 Let e ∈ E have the fake-E-symbol

( \begin{matrix}a_{1} & ⋯ & a_{n} \\ y_{1} & ⋯ & y_{n} \\ a_{1ρ} & ⋯ & a_{nρ} \end{matrix} ) ,

then the relation R′_{e} ∈ D′ is a consequence of χ̂ = A ∪ B ∪ C ∪ D̂.

Proof. We use induction on the length of e with respect to the generating set Z. If e has length one, then R′_{e} is already in D̂, so we assume that e = fz with z ∈ Z, f ∈ E and f is of strictly shorter length than e. Suppose f and z have the fake-E-symbols

( \begin{matrix}a_{1} & ⋯ & a_{n} \\ f_{1} & ⋯ & f_{n} \\ a_{1α} & ⋯ & a_{nα} \end{matrix} ) and ( \begin{matrix}a_{1} & ⋯ & a_{n} \\ z_{1} & ⋯ & z_{n} \\ a_{1β} & ⋯ & a_{nβ} \end{matrix} ) ,

respectively. Since σ_{e} = σ_{f}σ_{z} is a consequence of A,

σ_{e} = δδ_{1}σ_{f_{1}}δ_{2}σ_{f_{2}} ⋯ δ_{n}σ_{f_{n}}δ_{n} ⋯ δ_{1}δσ_{α}δδ_{1}σ_{z_{1}}δ_{2}σ_{z_{2}} ⋯ δ_{n}σ_{z_{n}}δ_{n} ⋯ δ_{1}δσ_{β}

is a consequence of χ̂. It is easy to see that δσ_{α}δ fixes a_{1} and hence commutes with every σ_{z_{i}} for 1 ≤ i ≤ n, by B. That δσ_{α}δδ_{j} = δ_{jα^{−1}}δσ_{α}δ holds in G_{n,1} is also easy to check, whence

σ_{e} = δδ_{1}σ_{f_{1}} ⋯ δ_{n}σ_{f_{n}}δ_{n} ⋯ δ_{1}δ_{1α^{−1}}σ_{z_{1}} ⋯ δ_{nα^{−1}}σ_{z_{n}}δ_{nα^{−1}} ⋯ δ_{1α^{−1}}δσ_{α}σ_{β} is a consequence of χ̂. Clearly, σ_{α}σ_{β} = σ_{αβ}, and using (3.7) and (3.8) we get

σ_{e} = δδ_{1}σ_{f_{1}}σ_{z_{1α}}δ_{2}σ_{f_{2}}σ_{z_{2α}} ⋯ δ_{n}σ_{f_{n}}σ_{z_{nα}}δ_{n} ⋯ δ_{1}δσ_{αβ}

as a consequence of χ̂. But

( \begin{matrix}a_{1} & ⋯ & a_{n} \\ f_{1}z_{1α} & ⋯ & f_{n}z_{nα} \\ a_{1αβ} & ⋯ & a_{nαβ} \end{matrix} )

is the combination of the two given symbols for f and z and, by Lemma 1.4, ρ = αβ and y_{i} = f_{i}z_{iα}. Furthermore, σ_{ρ} = σ_{α}σ_{β} is a consequence of A and σ_{y_{i}} = σ_{f_{i}}σ_{z_{iα}} is a consequence of A whenever both, f_{i} and z_{iα}, are either in E or S_{n}. But this always holds, for we know that y_{i} is in E ∪ S_{n}. Thus R′_{e} is a consequence of D̂, as required.

Lemma 3.12 Every fake-E-symbol for σ_{e} is an expansion of

Γ = ( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{n} \\ e & 1 & ⋯ & 1 \\ a_{1} & a_{2} & ⋯ & a_{n} \end{matrix} ) .

Proof. Let Σ be the fake-E-symbol

( \begin{matrix}u_{1} & ⋯ & u_{s} \\ x_{1} & ⋯ & x_{s} \\ v_{1} & ⋯ & v_{s} \end{matrix} )

for σ_{e}. Then {u_{1}, …, u_{2}} is a finite basis and therefore an expansion of {a_{1}, …, a_{n}}. As any expansion of {a_{1}, …, a_{n}} leads to an expansion Δ of Γ such that Δ is a fake-E-symbol for σ_{e}, there is a fake-E-symbol Δ for σ_{e} of the form

( \begin{matrix}u_{1} & ⋯ & u_{s} \\ y_{1} & ⋯ & y_{s} \\ z_{1} & ⋯ & z_{s} \end{matrix} )

which is an expansion of Γ. It follows, by Lemma 1.4, that x_{i} = y_{i} and z_{i} = v_{i} for 1 ≤ i ≤ s, which implies Δ = Σ. Thus the lemma is proved.

Proof of Lemma 3.9. Let us first show that every relation in χ′ follows from the relations in χ. To this end let e ∈ E have the fake-E-symbol (3.4) and let J be the subset of {1, 2, …, n} satisfying x_{j} ∈ S_{n} if and only if j ∈ J. Let K = {1, 2, …, n}\L and suppose J = {j_{1}, …, j_{r}} and K = {k_{1}, …, k_{t}}. Then

Γ = ( \begin{matrix}a_{n}a_{1} & ⋯ & a_{n}a_{n} & a_{2} & ⋯ & a_{n−1} & a_{1}a_{k_{1}} & ⋯ & a_{1}a_{k_{t}} \\ 1 & ⋯ & 1 & 1 & ⋯ & 1 & x_{k_{1}} & ⋯ & x_{k_{t}} \\ a_{n}a_{1} & ⋯ & a_{n}a_{n} & a_{2} & ⋯ & a_{n−1} & a_{1}a_{k_{1}π} & ⋯ & a_{1}a_{k_{t}π} \end{matrix}

\begin{matrix}a_{1}a_{j_{1}}a_{1} & ⋯ & a_{1}a_{j_{1}}a_{n} & ⋯ & a_{1}a_{j_{r}}a_{1} & ⋯ & a_{1}a_{j_{r}}a_{n} \\ 1 & ⋯ & 1 & ⋯ & 1 & ⋯ & 1 \\ a_{1}a_{j_{1}π}a_{1x_{j_{1}}} & ⋯ & a_{1}a_{j_{1}π}a_{nx_{j_{1}}} & ⋯ & a_{1}a_{j_{r}π}a_{1x_{jr}} & ⋯ & a_{1}a_{j_{r}π}a_{nx_{jr}} \end{matrix} )

is an E-symbol for σ_{e}. Note that Γ has s = rn + t + 2n − 2 columns, and let S = {η_{2}, …, η_{s}} be the set of type s corresponding to the ordered basis

{a_{1}, a_{n}a_{2}, …, a_{n}a_{n}, a_{2}, …, a_{n−1}, a_{n}a_{1}a_{k_{1}}, …, a_{n}a_{1}a_{k_{t}},
a_{n}a_{1}a_{j_{1}}a_{1}, …, a_{n}a_{1}a_{j_{1}}a_{n}, …, a_{n}a_{1}a_{j_{s}}a_{1}, …, a_{n}a_{1}a_{j_{s}}a_{n}}.

As all this might be a little confusing, Appendix C shows schematic pictures of the top row of Γ and this basis with the appropriate labelling used in the definition of the relation set D. We consider the relation R_{e,Γ,S} in χ (see (3.1)); namely

σ_{e} = τη_{2} ⋯ η_{2n−2}η_{2n−1}σ_{x_{k_{1}}} ⋯ η_{2n−2+t}σ_{x_{k_{t}}} η_{2n−2+t} ⋯ η_{2}ϵ

after the obvious cancellations using (3.6). Note that τ = δ and η_{2n−2+i} = δ_{k_{i}}. So, by using (3.6), (3.7), and (3.8), we obtain

σ_{e} = δσ_{x_{k_{1}}}^{δ_{k_{1}}} ⋯ σ_{x_{k_{t}}}^{δ_{k_{t}}} ϵ

as a consequence of χ. The relation ϵ = σ_{x_{j_{1}}}^{δ_{j_{1}}} ⋯ σ_{x_{jr}}^{δ_{jr}} δσ_{π} is a consequence of A (see Appendix A). Thus

σ_{e} = δσ_{x_{k_{1}}}^{δ_{k_{1}}} ⋯ σ_{x_{k_{t}}}^{δ_{k_{t}}} σ_{x_{j_{1}}}^{δ_{j_{1}}} ⋯ σ_{x_{jr}}^{δ_{jr}} δσ_{π}

is a consequence of χ, and, using (3.7) and (3.8) again, we get R′_{e} (see (3.5)) as a consequence of χ, as required.

We now turn to the the second part of the lemma, whose proof is similar to that of Lemma 19 in [35]: we show that every relation in D′′ is a consequence of χ′. Let

Δ = ( \begin{matrix}u_{1} & ⋯ & u_{s} \\ x_{1} & ⋯ & x_{s} \\ v_{1} & ⋯ & v_{s} \end{matrix} )

be a fake-E-symbol for σ_{e}, e ∈ E. Then, by Lemma 3.12, Δ is an expansion of the symbol in Lemma 3.12, and by Lemma 3.10 we can, and will, assume that the columns of Δ are in any order which suits us. The proof is by induction on the number m of columns of the form

( \begin{matrix}a_{1}u \\ l \\ a_{1}v \end{matrix} )

in Δ. The pattern of the induction is as follows. We first prove the cases m = 1 and m = n and then turn to the induction step.

If m = 1, then

Δ = ( \begin{matrix}a_{1} & u_{2} & ⋯ & u_{s} \\ e & 1 & ⋯ & 1 \\ a_{1} & u_{2} & ⋯ & u_{s} \end{matrix} )

and the corresponding relation in χ′′ is σ_{e} = τσ_{e}ϵ. But τϵ = 1 is a consequence of A, in this case, and τ fixes a_{1}, so the result is a consequence of A ∪ B.

If m = n, then

Δ = ( \begin{matrix}a_{1}a_{1} & ⋯ & a_{1}a_{n} & u_{n+1} & ⋯ & u_{s} \\ x_{1} & ⋯ & x_{n} & 1 & ⋯ & 1 \\ a_{1}a_{1π} & ⋯ & a_{1}a_{nπ} & u_{n+1} & ⋯ & u_{s} \end{matrix} ) ,

by (3.4), and the corresponding relation in D′′ ⊂ χ′′ is

σ_{e} = τσ_{x_{1}}η_{2}σ_{x_{2}} ⋯ η_{n}σ_{x_{n}}η_{n} ⋯ η_{2}ϵ.  (3.9)

Let α be the element with symbol

( \begin{matrix}a_{1} & w_{2} & ⋯ & w_{n} & w_{n+1} & ⋯ & w_{s−1} & w_{s} \\ 1 & 1 & ⋯ & 1 & 1 & ⋯ & 1 & 1 \\ a_{1} & a_{n}a_{1}a_{2} & ⋯ & a_{n}a_{1}a_{n} & z_{n+1} & ⋯ & z_{s−1} & a_{n}a_{1}a_{1} \end{matrix} ) ,

for some z_{n+1}, …, z_{s−1}. The relations α^{−1}η_{i}α = δ_{i}, 2 ≤ i ≤ n are consequences of A and α fixes a_{1}, so

σ_{e} = δδ_{1}α^{−1}σ_{x_{1}}η_{2}σ_{x_{2}} ⋯ η_{n}σ_{x_{n}}η_{n} ⋯ η_{2}αδ_{1}δσ_{π}

is obtained from R′_{e} (see (3.5)) as a consequence of χ′. The element ταδ_{1}δ fixes a_{1}, because

\begin{matrix}a_{1}a_{i} & ↦^{τ} & w_{i} & ↦^{α} & a_{n}a_{1}a_{i} & ↦^{δ_{1}} & a_{n}a_{1}a_{i} & ↦^{δ} & a_{1}a_{i}, & if 2 ≤ i ≤ n \\ a_{1}a_{1} & ↦ & a_{1} & ↦ & a_{1} & ↦ & a_{n}a_{1}a_{1} & ↦ & a_{1}a_{1} \end{matrix} .

Hence, using B and (3.6),

σ_{e} = ταδ_{1}δδδ_{1}α^{−1}σ_{x_{1}}η_{2} ⋯ η_{n}σ_{x_{n}}η_{n} ⋯ η_{2}αδ_{1}δσ_{π}δδ_{1}α^{−1}τ^{−1}

is a consequence of χ′. Furthermore, the relation αδ_{1}δσ_{π}δδ_{1}α^{−1}τ^{−1} = ϵ follows from A (see Appendix A), whence (3.9) is a consequence of χ′.

We now turn to the inductive step. Consider the simple expansion

( \begin{matrix}u_{1} & ⋯ & u_{s−1} & u_{s}a_{1} & ⋯ & u_{s}a_{n} \\ x_{1} & ⋯ & x_{s−1} & y_{1} & ⋯ & y_{n} \\ v_{1} & ⋯ & v_{s−1} & v_{s}(a_{1}π) & ⋯ & v_{s}(a_{n}π) \end{matrix} )

of Δ. For a given set of type r = s + n − 1 we have to show that the relation

σ_{e} = τσ_{x_{1}}η_{2}σ_{x_{2}} ⋯ η_{s−1}σ_{x_{s−1}}η_{s}σ_{y_{1}} ⋯ η_{r}σ_{y_{n}}η_{r} ⋯ η_{2}ϵ

follows from χ′. By the inductive hypothesis we can assume that, for any set {ν_{2}, …, ν_{s}} of type s,

σ_{e} = τ′σ_{x_{1}}ν_{2}σ_{x_{2}} ⋯ ν_{s}σ_{x_{s}}ν_{s} ⋯ ν_{2}ϵ′  (3.10)

is a consequence of χ′. Let β be the element with symbol

( \begin{matrix}a_{1} & w_{2} & ⋯ & w_{s−1} & w_{s} & w_{s+1} & ⋯ & w_{r} \\ 1 & 1 & ⋯ & 1 & 1 & 1 & ⋯ & 1 \\ a_{1} & z_{2} & ⋯ & z_{s−1} & z_{s}a_{1} & z_{s}a_{2} & ⋯ & z_{s}a_{n} \end{matrix} )

for some z_{2}, …, z_{s} and define ν_{i} = β^{−1}η_{i}β, 2 ≤ i ≤ s−1. Then there exists ν_{s} such that {ν_{2}, …, ν_{s}} is of type s with corresponding basis {a_{1}, z_{2}, …, z_{s}}. With the symbol

( \begin{matrix}z_{2} & ⋯ & z_{s} & a_{1}a_{1} & ⋯ & a_{1}a_{n} \\ 1 & ⋯ & 1 & y_{1} & ⋯ & y_{n} \\ z_{2} & ⋯ & z_{s} & a_{1}a_{1π} & ⋯ & a_{1}a_{nπ} \end{matrix} )

for σ_{x_{s}}, the case m = n implies that

σ_{x_{s}} = τ′′η_{2} ⋯ η_{s}σ_{y_{1}}η_{s+1} ⋯ σ_{y_{n}}η_{r} ⋯ η_{2}ϵ′′  (3.11)

is a consequence of χ′. The relations τ′′η_{2} ⋯ η_{s−1} = ν_{s}β^{−1}, ϵ′′ν_{s} ⋯ ν_{2}ϵ′ = ϵ and τ′β^{−1} = τ are consequences of A (see Appendix A), and hence

σ_{e} = τ′σ_{x_{1}}ν_{2}σ_{x_{2}} ⋯ ν_{s}σ_{x_{s}}ν_{s} ⋯ ν_{2}ϵ′
= τ′β^{−1}σ_{x_{1}}η_{2}σ_{x_{2}} ⋯ η_{s−1}σ_{x_{s−1}}βν_{s}σ_{x_{s}}ν_{s} ⋯ ν_{2}ϵ′
= τ′β^{−1}σ_{x_{1}}η_{2} ⋯ σ_{x_{s−1}}βν_{s}τ′′η_{2} ⋯ η_{s}σ_{y_{1}}η_{s+1} ⋯ σ_{y_{n}}η_{r} ⋯ η_{2}ϵ′′ν_{s} ⋯ ν_{2}ϵ′
= τσ_{x_{1}}η_{2} ⋯ σ_{x_{s−1}}η_{s}σ_{y_{1}}η_{s+1} ⋯ σ_{y_{n}}η_{r} ⋯ η_{2}ϵ

is a consequence of χ′. Here the equalities follow from (3.10), the definition of the ν_{i} and B as β fixes a_{1}, (3.11), and the argument of the preceding paragraph respectively. This completes the proof of Lemma 3.9 and Theorem 3.8.

Subgroups: Part II

In this chapter we will describe finitely presented simple groups which have more complicated subgroups than the groups G_{n,r}. In the first section we state without proofs the results of Scott showing that GL_{n}(ZZ) can be embedding in finitely presented simple groups for all n ≥ 1. Recall Theorem 2.7; GL_{3}(ZZ) is not a subgroup of any of the groups G_{n,r}. In Section 4.2 we prove that finitely generated infinite torsion groups cannot be contained in any of the finitely presented simple groups with solvable conjugacy problem constructed so far. The following section introduces a well known class of finitely generated infinite torsion groups. These are the Grigorchuk-Gupta-Sidki groups. In the remaining two sections of the chapter we construct finitely presented simple groups that have subgroups isomorphic to Grigorchuk-Gupta-Sidki groups.

4.1 Some Expansible Groups

Using the θ-construction (see Section 3.3) Scott was able to prove the following two theorems [36].

Theorem 4.1 For every n ≥ 1 there is a finitely presented simple group containing ZZ^{n}>◁ GL_{n}(ZZ) as a subgroup.

In fact it is shown that ZZ^{n}>◁ GL_{n}(ZZ) is isomorphic to H_{θ} for a suitable homomorphism θ : F ⟶ F ≀ Sym_{2^{n}−1}, where F is a free group of rank 2n + 1

To understand the next result, let us recall some facts about abelian groups. Let A be a countable abelian group and let T be the set of all periodic elements. Then T is a characteristic subgroup of A, and A/T is called the torsion factor group of A.

Theorem 4.2 Let m be an integer. Every countable abelian group whose torsion factor group is a finitely generated ZZ[\frac{1}{m}]-module is embeddable in a finitely presented simple group.

This theorem is proved by showing that for m ∈ IN the group with presentation ⟨a, b | b^{−1}ab = a^{m}⟩ is isomorphic to H_{θ} for a homomorphism θ : F ⟶ F ≀ Sym_{n}, where F is free group of rank 2 and suitable n ∈ IN. This result should be compared to Theorem 2.8.

For completeness, let us also record the following theorem, which was obtained by Scott [37] with quite a different kind of expansible groups. It uses a construction of C. F. Miller III [31] for finitely presented groups with an unsolvable conjugacy problem which are extensions of one finitely generated free group by another free group of finite rank. A group G is said to have an unsolvable conjugacy problem if there is no algorithm which decides whether two arbitrary given elements of G are conjugate in G.

Theorem 4.3 There exist finitely presented simple groups with unsolvable conjugacy problem.

4.2 Torsion Local Finiteness

The main result of this section shows that all the groups G_{n,r} and the groups constructed by Scott in [36], i.e., those groups of Theorems 4.1 and 4.2, are torsion locally finite (Theorem 4.8). A group is called torsion locally finite (t.l.f.) if every torsion subgroup is locally finite, or equivalently, if every finitely generated torsion subgroup is finite. We believe this result to be of independent interest. Our main interest, though, comes from the fact that it shows that the groups considered in Sections 4.5 and 4.6 are genuinely new finitely presented simple groups. Let us start with an observation.

Lemma 4.4 The class of torsion locally finite groups is closed under extensions and subgroups.

Proof. Only the statement about extensions requires proving. To this end, let N be a normal subgroup of the group G, let π : G ⟶ G/N be the natural projection and assume N and G/N are both t.l.f. Let S be a finitely generated torsion subgroup of G. We have to show that S is finite. Clearly, S^{π} is a finitely generated torsion subgroup of G/N and therefore finite. Let K be the kernel of the restriction of π to S, i.e., K = N ∩ S. Then |S : K| is finite, whence K is a finitely generated torsion subgroup of N and hence finite. So S is finite, as an extension of the finite group K by the finite group S^{π}. The lemma is proved.

Recall the θ-construction from Section 3.3, in particular, Proposition 3.4, which implies that H_{θ} acts length preserving on W_{n}. Recall also Lemma 3.5. We move on to examine the structure of finite subgroups of H_{θ}. Suppose K is a subgroup of H_{θ}. A basis B is said to be a K-basis if it is finite and every element of K has an H_{θ}-symbol whose top and bottom row are equal to B.

Proposition 4.5 If K is a finite subgroup of H_{θ}, then there is a K-basis.

Proof. It suffices to find a finite basis B such that, for every b ∈ B, each k ∈ K has a column

( \begin{matrix}b \\ h \\ c \end{matrix} )

with c ∈ B and h ∈ H_{θ}. To this end let K = {k_{1}, …, k_{t}} (t = |K|) and for 1 ≤ i ≤ t let Γ_{i} be an H_{θ}-symbol for k_{i}. Let C be a finite basis of W_{n} contained in ⋂_{i=1}^{t} top(Γ_{i})W_{n}. In particular C ⪰ top(Γ_{i}) for 1 ≤ i ≤ t, and hence there are (unique) H_{θ}-symbols Δ_{i} for k_{i} with top(Δ_{i}) = C, by Lemma 3.5(ii). Let U = ⋂_{i=1}^{t} bot(Δ_{i})W_{n} and B = B_{U}, i.e. B = ⨆_{i=1}^{t} bot(Δ_{i}). We claim that B has the required properties.

First let u ∈ U. Then u ∈ bot(Δ_{i})W_{n} for 1 ≤ i ≤ t and, by Lemma 3.5 (i), there are v_{i} ∈ CW_{n} and h_{i} ∈ H_{θ} such that k_{i} has the column

( \begin{matrix}v_{i} \\ h_{i} \\ u \end{matrix} ) .

Choose k ∈ K and note that B ⪰ C, since 1 ∈ K. By Lemma 3.5, k has a column

( \begin{matrix}u \\ h \\ w \end{matrix} )

with (unique) w ∈ W_{n} and h ∈ H_{θ}. Hence

( \begin{matrix}v_{i} \\ h_{i}h \\ w \end{matrix} )

is a column of k_{j_{i}} = k_{i}k, and v_{i} ∈ CW_{n} implies w ∈ bot(Δ_{j_{i}})W_{n} for 1 ≤ j_{i} ≤ t. Thus w ∈ U.

Now let b ∈ B, in particular, b ∈ U. Then, by Lemma 1.1 b), b ∈ bot(Δ_{j}) for some j, 1 ≤ j ≤ t. Hence

( \begin{matrix}c \\ h \\ b \end{matrix} )

is a column of k_{j}, where c ∈ C, h ∈ H_{θ}. For k ∈ K with column

( \begin{matrix}b \\ h′ \\ w \end{matrix} )

we see that

( \begin{matrix}c \\ hh′ \\ w \end{matrix} )

is a column of Δ_{l} where k_{l} = k_{j}k. Together with the previous paragraph it follows that w ∈ U ∩ bot(Δ_{l}). So, by Lemma 1.1 c), w ∈ B, as required.

Addendum. The above proof actually establishes a more general result. Namely, if D is a finite basis contained in ⋂_{i=1}^{t} top(Γ_{i})W_{n}, then

\overline{D}^{K} = ⨆_{i=1}^{t} bot(Σ_{i})  (4.1)

is a K-basis, where Σ_{i} is an H_{θ}-symbol for k_{i} with top(Σ_{i}) = D. We call \overline{D}^{K} the K-closure of D.

Let us now describe subgroups K of H_{θ} that admit a K-basis.

Lemma 4.6 Let K ⊂ H_{θ} have a K-basis B. Then K embeds in the permutational wreath product H_{θ} ≀ Sym(B) of H_{θ} with the symmetric group on the set B, where H_{θ} acts on itself via right multiplication.

Proof. Let B = {b_{1}, …, b_{s}}. Then each k ∈ K has an H_{θ}-symbol of the form

( \begin{matrix}b_{1} & b_{2} & … & b_{s} \\ h_{1}(k) & h_{2}(k) & … & h_{s}(k) \\ b_{1}π_{k} & b_{2}π_{k} & … & b_{s}π_{k} \end{matrix} )

with h_{i}(k) ∈ H_{θ} and π_{k} ∈ Sym(B). We leave it to the reader to check that the map ϕ defined by

\begin{aligned}ϕ : & K & ⟶ & H_{θ} ≀ Sym(B) \\ & k & ⟼ & (h_{1}(k), h_{2}(k), …, h_{s}(k))π_{k} \end{aligned}

is an embedding.

Theorem 4.7 Let H_{θ} be a group defined by a homomorphism θ : F ⟶ F ≀ Sym_{n−1} as in Section 3.3. If H_{θ} is torsion locally finite, then H_{θ} = ⟨G_{n,1}, H_{θ}⟩ is also torsion locally finite.

Proof. By Lemma 4.4, H_{θ} ≀ Sym(B) is t.l.f. for any finite set B. Thanks to the previous lemma, it therefore suffices to show that every finitely generated torsion subgroup K of H_{θ} admits a K-basis. The proof is by induction on the minimal number, d, of generators for K, the case d = 1 follows from Proposition 4.5. So we assume that d > 1, and K = ⟨k_{1}, …, k_{d}⟩. Define G = ⟨k_{1}, …, k_{d−1}⟩ and X = ⟨k_{d}⟩. By the induction hypothesis, G and X are finite and have G- and X-bases A_{0} and A_{1}, respectively. Let A = A_{0} ⊔ A_{1} and define inductively, for i ≥ 0,

B_{0} = \overline{A}^{X}, C_{i} = \overline{B_{i}}^{G} and B_{i+1} = \overline{C_{i}}^{X}.

Note that the B_{i} and C_{i} are (finite) X- respectively G-bases. Furthermore, the proof of (4.1) shows that for each b_{i} ∈ B_{i}, i ≥ 1, there are c_{i} ∈ C_{i−1}, h_{i} ∈ H_{θ}, and x_{i} ∈ X such that

( \begin{matrix}c_{i} \\ h_{i} \\ b_{i} \end{matrix} )

is a column of x_{i}. Similarly, for each c_{i} ∈ C_{i−1}, i ≥ 1, there are d_{i} ∈ B_{i−1}, l_{i} ∈ H_{θ}, and g_{i} ∈ G such that

( \begin{matrix}d_{i} \\ l_{i} \\ c_{i} \end{matrix} )

is a column of g_{i}. Repetition of these arguments shows that for all i ≥ 0 and b ∈ B_{i} there are \overline{b} ∈ B_{0}, h_{b} ∈ H_{θ}, and an element k_{b} ∈ K = ⟨G, X⟩ such that

( \overline{b} ; h_{b} ; b )

is a column of k_{b}.

Assume now, in order to obtain a contradiction, that the chain

A ⪯ B_{0} ⪯ C_{0} ⪯ B_{1} ⪯ C_{1} ⪯ ⋯  (4.2)

does not terminate. Then we can find a not eventually constant sequence b_{0}, b_{1}, b_{2}, … of elements of W_{n} with b_{i} ∈ B_{i} and b_{i} ≤ b_{i+1} for all i ≥ 0. Since B_{0} is finite there exist i > j such that b_{i} ≠ b_{j} but \overline{b_{i}} = \overline{b_{j}}, showing that k = k_{b_{j}}^{−1}k_{b_{i}} has the column

( \begin{matrix}b_{j} \\ h_{b_{j}}^{−1}h_{b_{i}} \\ b_{i} \end{matrix} ) .

Using b_{i} > b_{j} and the fact that H_{θ} acts in a length preserving manner, it is easy to prove that k has infinite order, which is a contradiction. Thus the chain (4.2) terminates and it is obvious that its last element is a K-basis. This completes the proof of the theorem.

Note that all the groups H_{θ} used in [36] are either torsion-free or isomorphic to ZZ^{n}>◁ GL_{n}(ZZ) and therefore t.l.f. (see for example [33]). Using also the fact that G_{n,r} embeds in G_{n,1} (see Section 1.4), we have the following.

Theorem 4.8 All the groups G_{n,r}, G′_{n,r} and all the finitely presented simple groups constructed by Scott in [36], i.e., the groups of Theorems 4.1 and 4.2, are torsion locally finite.

At this point we should also mention that the finitely presented simple groups recently constructed by Burger and Mozes [9] are t.l.f., indeed torsion free. This follows immediately from their presentation as a free product with amalgamation F ∗_{A} F, where F and A are finitely generated free groups. Therefore, Theorem 4.8 tells us that none of the previously known finitely presented simple groups can be isomorphic to any of the groups H_{f,p}′ which will be constructed in the following sections, with one possible exception; the finitely presented simple groups with unsolvable conjugacy problem of [37] (Theorem 4.3).

4.3 Grigorchuk-Gupta-Sidki

In the following we give a short introduction to Grigorchuk-Gupta-Sidki groups (GGS groups hereafter). This terminology was introduced in [2] by Baumslag. We first describe the ‘original’ Grigorchuk groups as defined in [18]. Then we turn to closely related groups including those investigated in [22] by N. Gupta and Sidki. Originally, Grigorchuk defined his groups by their action on the unit interval, whereas Gupta and Sidki considered automorphisms of rooted regular trees. Later it became popular to describe all these groups as subgroup of the automorphism group of a rooted regular tree (see for example [2, 34]). This approach appears more intuitive.

We begin with the description of Grigorchuk groups. Our description here will be in the language of inescapable isomorphisms. But it is straightforward to extend these inescapable isomorphisms to graph automorphisms of the tree W_{p} described in Section 1.2 (see Section 5.3). Instead of n we now use p, since it makes the comparison of the original definition with ours a little easier. (In [18] p was always a prime, but for our purpose this is irrelevant.) Given an infinite sequence ω = ω(0)ω(1) … with values in {0, 1, …, p − 1}, define the inescapable isomorphism b_{ω} of W_{p} by its action on the basis

{a_{p}^{r}a_{1}a_{1}, …, a_{p}^{r}a_{1}a_{p}, a_{p}^{r}a_{2}, …, a_{p}^{r}a_{p−1} | r ≥ 0},

the action is

\begin{matrix}a_{p}^{r}a_{1}a_{i} & ↦ & a_{p}^{r}a_{1}(a_{i}π^{ω(r)}), & 1 ≤ i ≤ p \\ a_{p}^{r}a_{j} & ↦ & a_{p}^{r}a_{j}, & 2 ≤ j ≤ p − 1 \end{matrix}

where π denotes the cyclic permutation (a_{1} a_{2} … a_{p}). See Fig. 18 for an example.

Figure 18: The element b_{ω} with ω = 120120120 ⋯ and p = 3

Given a sequence ω with values in {0, 1, …, p} define the two maps ¯ and ˜ from {0, …, p} to {0, …, p − 1} as in [18], i.e.,

x̄ = \{ \begin{matrix}0, & if x = p \\ 1, & if x ≠ p \end{matrix} and x̃ = \{ \begin{matrix}1, & if x = p \\ x, & if x ≠ p \end{matrix} .

The Grigorchuk group G_{ω} is isomorphic to the subgroup of G_{p,1} generated by bω̄, bω̃ and the inescapable isomorphism γ with symbol

( \begin{matrix}a_{1} & a_{2} & … & a_{p−1} & a_{p} \\ 1 & 1 & … & 1 & 1 \\ a_{2} & a_{3} & … & a_{p} & a_{1} \end{matrix} ) .  (4.3)

As mentioned above, in [18] the groups G_{ω} are described by their action on the set C of all open intervals of the real line of the form (\frac{t}{p^{k}} , \frac{t+1}{p^{k}}) with 0 ≤ t ≤ p^{k} − 1 and 1 ≤ k ∈ IN. The isomorphism between G_{ω} as described above and G_{ω} as described in [18] is induced by the bijection between W_{p} and the set C that lets a_{i_{1}}a_{i_{2}} ⋯ a_{i_{k}} ∈ W_{p} correspond to (\frac{t}{p^{k}} , \frac{t+1}{p^{k}}), where

t = ∑_{j=1}^{k} \frac{i_{j}−1}{p^{j}}.

Remark. It is worth noting that the nature of the maps ¯ and ˜ is irrelevant for our arguments. However, they played a crucial role in [18] for deducing that G_{ω} is a finitely generated infinite torsion group of intermediate growth in case each of the letters 0, 1, …, p occurs infinitely many times in ω.

Let us quickly recall the definition of some other groups which were considered during the search for groups of intermediate growth in the early eighties. N. Gupta and S. Sidki investigated in [22] the group G_{GS} which is defined for p = 3 and generated by the element γ with symbol (4.3) and b which has the fake-⟨b⟩-symbol

( \begin{matrix}a_{1} & a_{2} & a_{3} \\ γ & γ^{−1} & b \\ a_{1} & a_{2} & a_{3} \end{matrix} ) .

J. Fabrykowski and Gupta studied in [15] and [16] the group G_{ω} for p = 3 and ω = 111 ⋯ with the task to show that it has intermediate growth. Their proofs, however are not complete. Recently L. Bartholdi [1] has given a unified method to show that several two generated GGS-groups are of intermediate growth.

The most general sort of groups similar to those above are called special groups by Grigorchuk [20]. They are defined as follows. Let R be a subgroup of the symmetric group on {a_{1}, … a_{p}}. Now let ω = ω(0)ω(1)ω(2) ⋯ be an infinite sequence where each ω(i) is a (p−1)-tupel of elements of R. Assume ω(i) = (ω(i)_{1}, …, ω(i)_{p−1}) and define b_{ω} to be the element with symbol

( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{p−1} & a_{p} \\ ω(i)_{1} & ω(i)_{2} & ⋯ & ω(i)_{p−1} & b_{ω^{κ}} \\ a_{1} & a_{2} & ⋯ & a_{p−1} & a_{p} \end{matrix} ) ,

where κ is the forget map (4.4). A special group is a group generated by R and a finite set D of elements b_{ω}.

4.4 The Groups E_{f,p} and H_{f,p}

Here we describe some fake expansible groups which are used to prove that every Grigorchuk group G_{ω} which is defined by an almost periodic sequence ω can be embedded in a finitely presented simple group (Theorem 4.10). More general examples are given in Section 4.6. The reason for singling out the groups in this section is that our investigation of decision problems in Chapters 5 and 6 deals with these groups only.

Fix p, f ∈ IN and define Ω = {0, …, p − 1}^{IN_{0}}; thus, if ω ∈ Ω then ω = ω(0)ω(1)ω(2) · · ·. For n ∈ IN define the sequence [n] by

[n](i) = \{ \begin{matrix}1 & if i ≡ 0 (mod n) \\ 0 & otherwise \end{matrix}

The “forget” map κ is defined by

\begin{aligned}κ & : & Ω & ⟶ & Ω \\ & & ω = ω(0)ω(1) … & ⟼ & ω^{κ} = ω(1)ω(2) … \end{aligned}  (4.4)

Define Ω_{0} = {[pf]^{κ^{i}} | 0 ≤ i ≤ pf − 1} and let E_{f,p} be the subgroup of G_{p,1} generated by the set {b_{ω} | ω ∈ Ω_{0}}, where b_{ω} is defined as in Section 4.3. Observe that for 0 ≤ i ≤ pf − 1

[pf]^{κ^{i}}(j) = \{ \begin{matrix}1 & if j ≡ −i(mod pf) \\ 0 & otherwise \end{matrix}

Note that if we define the sum of the two sequences ω, ω′ by (ω + ω′)(i) = (ω(i) + ω′(i))(mod p) then we have b_{ω}b_{ω′} = b_{ω+ω′}. And a glance at Fig. 18 tells us that b_{ω}^{p} = 1 for all ω ∈ Ω_{0}. Furthermore, b_{ω} has the symbol

( \begin{matrix}a_{1} & a_{2} & … & a_{p−1} & a_{p} \\ γ^{ω(0)} & 1 & … & 1 & b_{ω^{κ}} \\ a_{1} & a_{2} & … & a_{p−1} & a_{p} \end{matrix} ) ,  (4.5)

where γ is the “top spin” with symbol (4.3)). Since γ ∈ S_{p} and [pf]^{κ^{i}} = [pf]^{κ^{pf+i}} for i ∈ IN, we have that E_{f,p} is fake-E_{f,p}-expansible (with respect to the generating system E_{f,p}) and each element e of E_{f,p} has a fake-E_{f,p}- symbol of the form

( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{p−1} & a_{p} \\ γ^{k} & 1 & ⋯ & 1 & e′ \\ a_{1} & a_{2} & ⋯ & a_{p−1} & a_{p} \end{matrix} ) ,  (4.6)

where 0 ≤ k ≤ p − 1, e′ ∈ E_{f,p}.

Define H_{f,p} to be the subgroup of G_{p,1} generated by G_{p,1} and E_{f,p}. Applying Proposition 3.7 with H = Y = E = E_{f,p} we get the following lemma.

Lemma 4.9 The group E_{f,p} is isomorphic to the direct product of pf cyclic groups of order p, and the group H_{f,p} = ⟨E_{f,p}, G_{p,1}⟩ is E_{f,p}-expansible.

In the following section we show that the group H_{f,p} defined above has a finitely presented simple commutator subgroup which contains an isomorphic copy of each Grigorckuk group G_{ω} if ω is periodic of period f.

4.5 The Commutator Subgroup of H_{f,p}

Let us call the infinite sequence ω almost periodic if there exist k, f ∈ IN, such that ω(i) = ω(i + f) for k ≤ i ∈ IN. In this case the least such f is called the period of ω. We also say that the sequence ω is almost f-periodic.

Theorem 4.10 Let H_{f,p} be the group defined in the previous section. The derived subgroup of H_{f,p} is a finitely presented simple group and contains every Grigorchuk group G_{ω} which is defined by an almost f-periodic sequence ω.

Proof. The simplicity of H_{f,p}′ follows from Lemma 2.3. Since E_{f,p} is finite, we can apply Theorem 3.8, to get that H_{f,p} is finitely presented. So H_{f,p}′ will be finitely presented if it has finite index in H_{f,p} (Coroll 2.8 in [28]). Thanks to Lemmas 2.1 and 4.9, x^{2p} ∈ H_{f,p}′ for all x ∈ G_{p,1} ∪ E_{f,p}. As G_{p,1} ∪ E_{f,p} contains a finite generating system for H_{f,p}, we get that H_{f,p}/H_{f,p}′ is a finitely generated abelian group of exponent at most 2p and hence finite, as required.

Now it only remains to show that H_{f,p}′ contains the required Grigorchuk groups. First note that if ω is any fp-periodic sequence then b_{ω} ∈ E_{f,p}. Thus H_{f,p} contains σ_{bω̂} where ω̂ is fp-periodic and begins with

\underbrace{\underbrace{10 … 0}_{f} \underbrace{20 … 0}_{f} … \underbrace{(p − 1)0 … 0}_{f} \underbrace{0 … 0}_{f}}_{pf} .

Let α be the element with symbol

( \begin{matrix}a_{2}a_{1} & ⋯ & a_{2}a_{p−1} & a_{1} & a_{2}a_{p} & a_{3} & ⋯ & a_{p} \\ 1 & ⋯ & 1 & 1 & 1 & 1 & ⋯ & 1 \\ a_{1}a_{1} & ⋯ & a_{1}a_{p−1} & a_{1}a_{p} & a_{2} & a_{3} & ⋯ & a_{p} \end{matrix} )  (4.7)

and observe that α^{−1}σ_{b_{ω}}α = σ_{b_{0ω}} and hence α^{−f}σ_{bω̂}^{−1}α^{f}σ_{bω̂} = σ_{b_{[f]}} ∈ H_{f,p}′. Furthermore, for every f-periodic sequence ω, σ_{b_{ω}} ∈ H_{f,p}′.

As E^{∗} ≅ E for every subgroup E ⊂ G_{p,1} (see Section 3.2 for the definition of E^{∗}), in order to complete the proof it suffices to exhibit σ_{γ} and σ_{b_{v\overline{0}}} as elements of H_{f,p}′ for every finite sequence v with entries in {0, 1, … p − 1}, where \overline{0} = 000 … and γ has the symbol (4.3). By Lemma 2.1, G′_{p,1} = G_{p,1} if p is even and σ_{γ} ∈ Alt({a_{1}a_{1}, …, a_{1}a_{p}, a_{2}, …, a_{p}}) ⊂ G′_{p,1} if p is odd, where Alt(Y) denotes the alternating group on the set Y. Therefore, σ_{γ} ∈ H_{f,p}′ and σ_{σ_{γ}} ∈ H_{f,p}′. From σ_{b_{1\overline{0}}} = σ_{σ_{γ}} and the last paragraph it follows that σ_{b_{v\overline{0}}} ∈ H_{f,p}′ for every finite sequence v with entries in \{0, 1, … p − 1\}. The proof of Theorem 4.10 is complete.

Remark. It can be shown that H_{f,p}′ contains in fact subgroups isomorphic to any Grigorchuk group defined by an almost fp-periodic sequence. For such a group is clearly a subgroup of ⟨γ, E_{f,p}⟩ which, in turn, is a finite extension of ⟨γ, E_{f,p}⟩ ∩ H_{f,p}′, and therefore embeddable in H_{f,p}′, by Corollary 3.2. This approach, however, does not establish the natural embedding that is obtained in the proof of the theorem.

Corollary 4.11 The group H_{f,p} is generated by three elements.

This follows from Section 2.6 and the fact that E^{∗} is generated by b_{ω}^{α^{i}}, 0 ≤ i ≤ pf − 1, where ω = [pf] and α is the element with symbol (4.7). To be more precise, H_{f,p} is generated by b_{[pf]} and the elements âb and c, with â, b, and c as defined in Appendix B. By noting that c is always an element of G_{n,r}′, we see that the index of H_{f,p}′ in H_{f,p} is at most εp because (âb)^{ε}, (b_{[pf]})^{p} ∈ H_{f,p}′, where ε is the largest common divisor of 2 and p − 1. In fact, we have the following.

Corollary 4.12 The group H_{f,p}/H_{f,p}′ is cyclic of order εp, where ε is the largest common divisor of 2 and p − 1. In particular, G_{p,1} ∩ H_{f,p}′ = G_{p,1}′.

Proof. For an fp-periodic sequence ω define

M(ω) = ω(0) + ω(1) + ⋯ + ω(pf − 1) (mod p),

and note that M(ω + ω′) = M(ω) + M(ω′) (mod p) and M(ω) = M(ω^{κ}) (for κ see (4.4). This implies that the map A : H_{f,p} ⟶ ZZ/pZZ which maps the E_{f,p}-symbol

( \begin{matrix}u_{1} & ⋯ & u_{s} \\ b_{ω_{1}} & ⋯ & b_{ω_{s}} \\ v_{1} & ⋯ & v_{s} \end{matrix} )

to M(ω_{1} + ⋯ + ω_{s}) is a homomorphism, which is onto, as A(σ_{b_{[pf]}}) = 1. If p is even this proves the statement, since σ_{b_{[pf]}} is the only generator not lying in H_{f,p}′. If, on the other hand, p is odd, then it follows from the fact that γ is an even element of G_{n,r}, that we can define even elements precisely as in Section 2.1. In detail: write an element h of H_{f,p} as a product of an order preserving element and an element with a flat E_{f,p}-symbol Δ, i.e., top(Δ) = bot(Δ) (see Section 5.2). Hence, there is also a homomorphism from H_{f,p} onto the the cyclic group of order two, mapping an element onto the generator if the induced permutation in the top row of the flat symbol is odd. Since p was odd, we have now a homomorphism onto the cyclic group of order 2p. The last assertion follows from this, and the proof is complete.

In the remainder of this section we prove that H_{f,p} and H_{f,p}′ are generated by two elements. This should be compared with Section 2.6. To simplify notation, we write ω for b_{ω} and switch to additive notation for the group E_{f,p}, i.e., b_{ω}b_{ω′} becomes ω + ω′ and b_{ω}^{−1} will be −ω. We need the following a lemma.

Lemma 4.13 Let z be defined by the tree diagram

,

where ω = [pf]. Then H_{f,p}′ is generated by G_{p,1}′ and z.

Proof. It is clear that the following relation of E_{f,p}-symbols holds.

( \begin{matrix}u_{1} & ⋯ & u_{s} \\ ω_{1} & ⋯ & ω_{s} \\ v_{1} & ⋯ & v_{s} \end{matrix} ) = ( \begin{matrix}u_{1} & ⋯ & u_{s} \\ ω_{1} & ⋯ & ω_{s} \\ u_{1} & ⋯ & u_{s} \end{matrix} ) ( \begin{matrix}u_{1} & ⋯ & u_{s} \\ 1 & ⋯ & 1 \\ v_{1} & ⋯ & v_{s} \end{matrix} )  (4.8)

Assume that the symbol on the left hand side of (4.8) defines an element of H_{f,p}′. Then M(ω_{1} + ⋯ + ω_{s}) = 0 and the element defined by the 1-symbol on the right hand side of (4.8) lies in G_{p,1}′ (see proof of Corollary 4.12). So it suffices to show that we can generate every element with an E_{f,p}-symbol of the form

Δ = ( \begin{matrix}u_{1} & ⋯ & u_{s} \\ ω_{1} & ⋯ & ω_{s} \\ u_{1} & ⋯ & u_{s} \end{matrix} ) ,

with M(ω_{1} + ⋯ + ω_{s}) = 0. As in the proof of Theorem 4.10, by conjugating z with positive powers of the element α with symbol (4.7), we can generate all elements with tree diagrams of the form

where ρ = ω^{κ^{i}} for some i ≥ 0. Observe that α ∈ G_{p,1}′. We can now multiply some of these conjugates of z together to get every element with a tree diagram of the form for arbitrary fp-periodic ρ. Furthermore, we can assume, by possibly conjugating, that u_{s} = a_{1}a_{1} in the symbol Δ. It follows that we can generate the element with symbol

Γ = ( \begin{matrix}u_{1} & ⋯ & u_{s−1} & a_{1}a_{1} \\ ω_{1} & ⋯ & ω_{s−1} & −M(ω_{1} + ⋯ + ω_{s−1})ω \\ u_{1} & ⋯ & u_{s−1} & a_{1}a_{1} \end{matrix} )

with our given generators. After multiplying Δ with Γ^{−1}, we are left to show that we can generate the element with symbol

Σ = ( \begin{matrix}u_{1} & ⋯ & u_{s−1} & a_{1}a_{1} \\ 1 & ⋯ & 1 & ω′ \\ u_{1} & ⋯ & u_{s−1} & a_{1}a_{1} \end{matrix} ) ,

where ω′ = ω_{s} + M(ω_{1} + ⋯ + ω_{s−1})ω. Note first that M(ω′) = 0, and then that z is conjugate under an element of G_{p,1}′ to the element with tree diagram

which multiplied with z gives an element conjugate to σω̃, where ω̃ is fpperiodic with period 1 − 100 ⋯ 0. Finally, for every fp-periodic sequence ω̂ with M(ω̂) = 0, σω̂ is a product of conjugates of σω̃ under positive powers of α. In particular, we get σ_{ω′} which is a conjugate of the element with symbol Σ, and the lemma is proved.

Theorem 4.14 The groups H_{f,p} and H_{f,p}′ are generated by two elements for all f ≥ 1, p ≥ 2.

Proof. First you should fold out Appendix B again. Read those tree diagrams with the dashed lines and assume r = p = n. They define elements of G_{p,1}. Note that the results of Section 2.6 are still valid, since G_{p,p} is isomorphic to G_{p,1} by interpreting x_{i} as a_{i} for 1 ≤ i ≤ p. For the rest of this proof ω = [fp].

We begin with H_{f,p}. Assume p ≥ 3, and put

e =  and ã =  .

Check that [ã, e] = [ã, b] = [b, e] = 1. Let x = ãbe, then x^{p} = âb^{p} and ⟨x^{2p}⟩ = ⟨b⟩. So, by Section 2.6, G_{p,1} = ⟨â, b, c⟩ ⊂ ⟨x, c⟩. Since â, b ∈ G_{p,1}, e ∈ ⟨x, c⟩. But e is conjugate to σ_{ω}, and we are done, by Corollary 4.11. Suppose now p = 2, and define

e = .

Now [e, d] = 1 and with x = de, one checks that cx^{4}c^{−1} = b and x^{6} = â(= a). Hence G_{2,1} ⊂ ⟨x, c⟩. As d ∈ G_{2,1}, e ∈ ⟨x, c⟩, and e is again conjugate to σ_{ω}, so ⟨x, c⟩ = H_{f,2}, by Corollary 4.11.

Let us now turn to H_{f,p}′. Assume first that p is odd; thus, we are in the first case of the definition of b. This time define

e = ,

and put x = ābe. Then x^{p} = ab^{p} and ⟨x^{p^{2}}⟩ = ⟨b⟩, whence, by Section 2.6, G_{p,1}′ = ⟨a, b, c⟩ ⊂ ⟨x, c⟩. As before, ā, b ∈ G_{p,1}′ implies e ∈ ⟨x, c⟩, and Lemma 4.13 completes this case, using that e is conjugate to z defined in that very lemma. Next we assume that p is even but not two. Then define

e =

and let a′ be a p-th root of â such that a′ fixes a_{2}, …, a_{p}, a_{1}a_{p−1}, and a_{1}a_{p}, cf. Lemma 2.9. Similar as before, with x = a′be, we find ⟨x, c⟩ = H_{f,p}′. And finally, if p = 2, we let

e = ,

and check that a, b, c, e ∈ ⟨de, c⟩, so that H_{f,2}′ is generated by de and c, by Lemma 4.13. The proof of the theorem is now complete.

4.6 More Examples

Here we give some more examples of fake expansible groups. Interested readers would probably not have any difficulties in finding these very quickly on their own, as they are more or less straightforward generalisations of the groups H_{f,p}.

First let us note that the group G_{GS} described at the end of Section 4.4 is not contained in H_{f,p} in any obvious way. But it is easily seen to be a special group. Let us show that a special group defined by an almost periodic sequence is also embeddable in a finitely presented simple group using groups similar to E_{f,p} as follows.

Let p ∈ IN and let S_{p} denote the symmetric group on {a_{1}, …, a_{p}}. Given an infinite sequence ω with values in S_{p} and i ∈ {1, …, p}, define the inescapable isomorphism b_{i,ω} by its action on the basis

{a_{p}^{r}a_{i}a_{1}, …, a_{p}^{r}a_{i}a_{p}, a_{p}^{r}a_{j} | r ≥ 0, 1 ≤ j ≤ p, j ≠ i},

the action is

\begin{matrix}a_{p}^{r}a_{i}a_{l} & ↦ & a_{p}^{r}a_{i}(a_{lω(r)}), & 1 ≤ i ≤ p \\ a_{p}^{r}a_{j} & ↦ & a_{p}^{r}a_{j}, & 1 ≤ j ≤ p − 1, j ≠ i. \end{matrix}

Choose a period f and define

E = {b_{i,ω_{i}} | 1 ≤ i ≤ p − 1, ω_{i} an f-periodic sequence}.

Noting that E is isomorphic to a subgroup of the direct product of f(p − 1) copies of S_{p} and hence finite, arguments similar to those in Sections 4.4 and 4.5 give the following theorem.

Theorem 4.15 Let G = ⟨R, D⟩ be a special group as defined in Section 4.3. If all defining sequences for elements of D are periodic, then G can be embedded in a finitely presented simple group.

The following result is slightly more interesting.

Theorem 4.16 For 1 ≤ i ≤ r let G_{ω_{i}} be a Grigorchuk group defined by an f_{i}-periodic sequence ω_{i} with values in {0, 1, …, p_{i}}. The direct product G_{ω_{1}} × ⋯ × G_{ω_{r}} is embeddable in a finitely presented simple group.

Proof. Let n = ∑_{i=1}^{r} p_{i} and let

A_{n} = {a_{1,1}, a_{1,2}, ⋯, a_{1,p_{1}}, ⋯, a_{r,1}, a_{r,2}, ⋯, a_{r,p_{r}}}.

For 1 ≤ i ≤ r let γ_{i} to be the permutation of A_{n} with cycle (a_{i,1} a_{i,2} … a_{i,p_{i}}) and let σ_{i} = [f_{i}] (see Section 4.3 for the definition of [f_{i}]). Define e_{σ_{i}} to be the element whose only non-trivial columns are

( \begin{matrix}a_{i,1} \\ γ_{i} \\ a_{i,1} \end{matrix} )  and  ( \begin{matrix}a_{i,p_{i}} \\ e_{σ_{i}^{κ}} \\ a_{i,p_{i}} \end{matrix} ) ,

where κ is once more the forget map (4.4). It follows as before that H = ⟨G_{n,1}, e_{σ_{i}} | 1 ≤ i ≤ r⟩ is finitely presented, and that H′ is a finitely presented simple group of finite index in H. It is clear from the definitions that the

group generated by the γ_{i} together with all e_{σ_{i}}^{α_{i}^{j}} for 0 ≤ j ≤ f_{i} − 1 contains an isomorphic copy of G_{ω_{1}} × ⋯ × G_{ω_{r}}, where the α_{i} are elements chosen in a similar way to α before and satisfy e_{σ_{i}}^{α_{i}} = e_{σ_{i}^{κ}}. Observe that we have ‘enough room’ if r ≥ 2 to do this for e_{σ_{i}} as opposed to σ_{e_{σ_{i}}}. The theorem is proved.

The Order Problem

The goal of this chapter is to show that the groups H_{f,p} have a solvable order problem. Let us recall that a group has solvable order problem if given any element one can effectively decide whether it has finite or infinite order. Note that together with the solvability of the word problem this implies that we can actually find the exact order of a given element, for once we know that an element has finite order, we simply check for all its powers if they are trivial. Clearly, having a solvable order problem is passed on to subgroups, and hence H_{f,p}′ has a solvable order problem.

In the first section we establish some preliminary results. Then we introduce flat symbols and step columns in Section 5.2, and combine the results to solve the order problem in Section 5.3.

5.1 The Group M

Recall from Section 4.4 the definition of the groups E_{f,p} and H_{p,f} for f, p ∈ IN, and that γ is the element of G_{p,1} defined by the symbol

( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{p−1} & a_{p} \\ 1 & 1 & ⋯ & 1 & 1 \\ a_{2} & a_{3} & ⋯ & a_{p} & a_{1} \end{matrix} ) .  (5.1)

Put C = ⟨γ⟩ and note that it is a cyclic group of order p acting naturally on {a_{1}, …, a_{p}} and hence on {1, …, p}. Also, recall that every element e of E_{f,p} has a symbol of the form

( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{p−1} & a_{p} \\ δ & 1 & … & 1 & e′ \\ a_{1} & a_{2} & ⋯ & a_{p−1} & a_{p} \end{matrix} ) ,  (5.2)

with δ ∈ C and e′ ∈ E_{f,p}. Let M be the subgroup of G_{p,1} generated by C ∪ E_{f,p}, then it follows directly from (5.1) and (5.2) that every element m of M has an M-symbol of the form

( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{p} \\ m_{1} & m_{2} & ⋯ & m_{p} \\ a_{1π} & a_{2π} & ⋯ & a_{pπ} \end{matrix} )  (5.3)

for some π ∈ C. So we can define the following homomorphism

\begin{aligned}Φ : & M & ⟶ & M ≀ C \\ & m & ⟼ & (m_{1}, …, m_{p})π, \end{aligned}  (5.4)

where m has the symbol (5.3). Since an element m of M lies in the kernel of Φ if and only if m^{Φ} = (1, …, 1)1, i.e., its symbol defines the trivial element of G_{p,1}, we see that Φ is an embedding. Let ρ be the natural projection from M ≀ C onto C and define Ψ = Φρ.

Theorem 5.1 The group M as defined above has solvable word problem.

Proof. Since M is a subgroup of the E_{f,p}-expansible group H_{f,p}, M is also E_{f,p}-expansible. So given m ∈ M, find an E_{f,p}-symbol Δ for m. This can be done effectively using Proposition 3.7. Now m is trivial if and only if Δ defines the trivial element of G_{p,1} which happens precisely when all columns of Δ are trivial. As this can clearly be checked in finite time, the proof is complete.

Theorem 5.2 The group M as defined above has solvable order problem.

Proof. The proof is by induction on the length l(m) of the element m ∈ M as a word in the free product of the groups E_{f,p} and C. Every non-trivial element of length one has order dividing p, by Lemma 4.9. Since conjugation does not change the order of an element, we can assume m to have the following form

δ_{1}e_{1}δ_{2}e_{2} ⋯ δ_{n}e_{n}, where δ_{i} ∈ C \ {1}, e_{i} ∈ E_{f,p} \ {1}, 1 ≤ i ≤ n.

We now consider two cases.

Case 1: m ∈ ker(Ψ) or equivalently δ_{1}δ_{2} ⋯ δ_{n} = 1. Then

m = e_{1}^{δ_{1}^{−1}}e_{2}^{(δ_{1}δ_{2})^{−1}} ⋯ e_{n−1}^{(δ_{1}···δ_{n−1})^{−1}}e_{n}

and m^{Φ} is an element of M^{p}, the base group of M ≀ C. Suppose m^{Φ} = (m_{1}, …, m_{p}). It follows from (5.2) that each factor e_{i}^{(δ_{1}···δ_{i})^{−1}} contributes at most one letter each to m_{i} and hence l(m_{i}) < l(m) for 1 ≤ i ≤ p. By the induction hypothesis, we can decide the order problem for each m_{i}, and therefore, the order problem for m. For it is clearly that m has finite order if and only if each m_{i} has finite order.

Case 2: m ∉ ker(Ψ) or equivalently δ_{1}δ_{2} ⋯ δ_{n} = δ ≠ 1. Let q be the order of δ. Then m^{q} ∈ ker(Ψ) and

m^{q} = ∏_{i=0}^{q−1}(e_{1}^{δ_{1}^{−1}}e_{2}^{(δ_{1}δ_{2})^{−1}} ⋯ e_{n−1}^{(δ_{1}···δ_{n−1})^{−1}}e_{n}^{δ^{−1}})^{δ^{−i}}.

Suppose m^{q} = (m_{1}, …, m_{p}). If q ≠ p, then the two non-trivial components of e_{i}^{(δ_{1}···δ_{i})^{−1}} lie in different δ-orbits. This in turn implies that each factor e_{i}^{(δ_{1}···δ_{i})^{−1}} together with all its conjugates under δ^{j}, 0 ≤ j ≤ q−1, contributes at most one letter to each m_{j}, 1 ≤ j ≤ p. Hence l(m_{j}) < l(m) for 1 ≤ j ≤ p and we can refer to the induction hypothesis.

Assume now that q = p and m^{p} = (m_{1}, …, m_{p}). From (5.2) we get that each e_{i}^{(δ_{1}···δ_{i})^{−1}} together with all its conjugates under δ^{j}, 1 ≤ j ≤ p − 1, can contribute at most two letters to m_{k} for 1 ≤ k ≤ p. Hence l(m_{k}) ≤ 2n = l(m). Note that all the m_{k} are pairwise conjugate so that it suffices to decide the order problem for any of the m_{k} in order to solve the order problem for m. If for some k, 1 ≤ k ≤ p, l(m_{k}) < 2n we plainly refer to the induction hypothesis.

So let us speak of the worst case if actually l(m_{k}) = l(m) for 1 ≤ k ≤ p. In this case we apply the whole procedure to m_{1} instead of m. If we find ourselves again in the worst case, we obtain an m_{2}, a component of m_{1}^{p} of the same length and so forth.

Suppose we always stay in the worst case and consider the resulting sequence of elements m_{i}, i ≥ 0, arising as described above. Observe that each m_{i} is conjugate (via an element of E_{f,p} ∪ C) to an element of the form

ϵ_{1}f_{1} ⋯ ϵ_{n}f_{n},  (5.5)

where ϵ_{i} ∈ C \ {1} and f_{i} ∈ E_{f,p} \ {1}. But there are only finitely many elements of the form (5.5). This means m_{s}^{x} = m_{r} for some s < r ∈ IN and some x ∈ M, and we will find this after at most K = (p − 1)^{n}(p^{fp} − 1)^{n} steps. It follows from the procedure that m_{s}^{p^{r−s}} and m_{s} have the same order. Hence, if m_{s} is not trivial, m_{s} and m have infinite order, and m has finite order, if m_{s} is trivial. As we can decide whether m_{s} is trivial or not, by Theorem 5.1, this solves the order problem for m, and the proof is complete.

5.2 Step Columns and Flat Symbols

Here begins our investigation of particularly nice symbols. Flat symbols play also a major role in Chapter 6.

Let Δ be a symbol and let C be a column of Δ. We call C a step column if it is of the form

( \begin{matrix}b \\ g \\ bv \end{matrix} ) or ( \begin{matrix}bv \\ g \\ b \end{matrix} )

for some v ∈ W_{n} \ {∅}. Let M be defined as in the previous section. The next lemma shows that for an element g of H_{f,p} either all its M-symbols have a step column or none of its M-symbols has a step column.

Lemma 5.3 Suppose the M-symbol Δ has a step column. Then every expansion of Δ has a step column, and every contraction of Δ which itself is an M-symbol has a step column.

Proof. By possibly replacing Δ by Δ^{−1}, we may assume that

C = ( \begin{matrix}b \\ m \\ bv \end{matrix} )

is the step column of Δ.

We deal with expansions first. It certainly suffices to prove the statement for simple expansions, and we only have to consider the case that C gets expanded. Assuming that (m_{1}, …, m_{p})π is the image of m under the embedding Φ (see (5.4)), C gets replaced by

( \begin{matrix}ba_{1} & ⋯ & ba_{p} \\ m_{1} & ⋯ & m_{p} \\ bva_{1π} & ⋯ & bva_{pπ} \end{matrix} ) .

Hence, if v = a_{i}w, then

( \begin{matrix}ba_{i} \\ m_{i} \\ ba_{i}(wa_{iπ}) \end{matrix} )

is the step column of the expansion.

To prove the statement for contractions we may restrict ourselves to simple contractions which involve the column C. Assume

C = ( \begin{matrix}b \\ m \\ bv \end{matrix} ) = ( \begin{matrix}b′a_{i} \\ m \\ bv′a_{i′} \end{matrix} ) .

Then Δ must also contain columns

( \begin{matrix}b′a_{j} \\ m_{j} \\ bv′a_{jπ} \end{matrix} )

for 1 ≤ j ≤ p, j ≠ i, and some permutation π of {a_{1}, …, a_{n}} with iπ = i′. Moreover, there must be m′ ∈ M such that its image under the embedding Φ is (m_{1}, …, m_{i−1}, m, m_{i+1}, …, m_{p})π for the resulting contraction, Δ′ say, to be an M-symbol. But then

( \begin{matrix}b′ \\ m′ \\ b′a_{i}v′ \end{matrix} ) ∈ Δ′

which is a step column as a_{i}v′ ≠ ∅ and the lemma is proved.

A symbol Δ is called flat if top(Δ) = bot(Δ). Observe, that if g is the element defined by the flat symbol Δ, the combination Δ^{t} exists for all t ∈ ZZ \ {0} and top(Δ) is a ⟨g⟩-basis in the sense of Section 4.2. This motivates the following definition(s) in which T is to be replaced by E_{f,p}, fake-E_{f,p}, or M. Let g ∈ H_{f,p}. We call Δ a ⟨g⟩-T -symbol if Δ is a flat T -symbol for g. We also say g has a flat T -symbol if there exists a ⟨g⟩-T - symbol. Let us emphasise that being a ⟨g⟩-T -symbol means in particular being a T -symbol for g, rather than just any element of ⟨g⟩.

Lemma 5.4 Let g ∈ H_{f,p}, then g has a flat fake-E_{f,p}-symbol if and only if it has a flat M-symbol.

Proof. The only if part is trivial. Let us proceed with the if part. For k ∈ IN let L_{k} denote the set of all words of length k in W_{n}. The lemma is now an immediate consequence of

Lemma 5.5 For every m ∈ M there exists K ∈ IN so that for all k ≥ K, m has a flat fake-E_{f,p}-symbol Δ with top(Δ) = L_{k}.

Proof. It suffices to prove that there exists K ∈ IN such that m has a flat fake-E_{f,p}-symbol Δ with top(Δ) = L_{K}. For then, the result of simply expanding every column of Δ is a ⟨m⟩-fake-E_{f,p}-symbol whose top row is equal to L_{K+1}, by (5.1) and (5.2).

The proof is now by induction on the length l(m) of m with respect to the generating set C ∪E_{f,p}. By (5.1) and (5.2) again, the statement surely holds if l(m) ≤ 2 with K = 1. So assume l(m) > 2 and write m = m′x, where x ∈ C ∪ E_{f,p} and l(m′) < l(m). Let Γ be the ⟨m′⟩-fake-E_{f,p}-symbol with top(Γ) = L_{K} for suitable K whose existence is guaranteed by the induction hypothesis, and let Σ be a ⟨x⟩-fake-E_{f,p}-symbol with top(Σ) = L_{K}. Then ΓΣ exists and its middle row entries are elements of M of length at most two. According to what was said above, the result of simply expanding each column of ΓΣ is a ⟨m⟩-fake-E_{f,p}-symbol Δ with top(Δ) = L_{K+1}. This establishes Lemmas 5.5 and 5.4.

Let us also record the following useful criterion for finding a flat symbol. Recall that for a finite family (B_{i})_{i∈I} of bases of W_{n}, ⨆_{i∈I} B_{i} denotes the basis of the inescapable subspace ⋂_{i∈I} B_{i}W_{n} of W_{n}.

Lemma 5.6 In the following T may be replaced by E_{f,p}, fake-E_{f,p} or M. Let g ∈ H_{f,p}, 0t ∈ IN, and assume that Δ_{1}, …, Δ_{t} are T -symbols for g such that the combination Δ_{1} ⋯ Δ_{t} exists. If Γ is the symbol for g with top(Γ) = ⨆_{i=1}^{t} top(Δ_{i}), then Γ is a T -symbol and Γ is flat if and only if top(Δ_{1}) = bot(Δ_{t}).

Proof. Put B = ⨆_{i=1}^{t} top(Δ_{i}), let Γ be the symbol for g with top(Γ) = B and let

( \begin{matrix}b \\ x \\ c \end{matrix} )

be a column of Γ. By Lemma 1.1 b) and Lemma 1.4, this is also a column of one of the given symbols, say of Δ_{j}, so in particular Γ is a T -symbol and c ∈ bot(Δ_{j}). Since b ∈ B, we have b ∈ top(Δ_{i})W_{p} for each i, so that g has the columns

( \begin{matrix}b_{i}v_{i} = b \\ x_{i} \\ w_{i} \end{matrix} ) ,

where b_{i} ∈ top(Δ_{i}), and consequently w_{i} ∈ bot(Δ_{i})W_{p}. By Lemma 1.4 again, all w_{i} are equal to c, whence c ∈ ⋂_{i=1}^{t} bot(Δ_{i})W_{p}. It follows from Lemma 1.1 c) that c ∈ ⨆_{i=1}^{t} bot(Δ_{i}). Assuming top(Δ_{1}) = bot(Δ_{t}), it follows that B = ⨆_{i=1}^{t} bot(Δ_{i}), and hence c ∈ B, so Γ is flat. On the other hand, if Γ is flat, we have B = bot(Γ) ⊂ ⨆_{i=1}^{t} bot(Δ_{i}), which implies B = ⨆_{i=1}^{t} bot(Δ_{i}), as both, B and ⨆_{i=1}^{t} bot(Δ_{i}), are bases. This proves the lemma.

An easy consequence of this is a characterisation of elements of finite order in H_{f,p}.

Proposition 5.7 The element g of H_{f,p} has finite order if and only if it has a flat E_{f,p}-symbol.

Proof. If Δ is a flat E_{f,p}-symbol for g then it is clear that g^{s!p} = 1, where s is the number of columns of Δ. This is because E_{f,p} is an abelian group of exponent p (Lemma 4.9). For the converse assume that g^{t} = 1 and we are given E_{f,p}-symbols Δ_{1}, …, Δ_{t} for g such that the combination Δ_{1} ⋯ Δ_{t} exists (H_{f,p} is E_{f,p}-expansible, by Lemma 4.9). This combination is a symbol for the trivial element and thus top(Δ_{1}) = bot(Δ_{t}). By Lemma 5.6, the symbol Γ for g with top(Γ) = ⨆_{i=1}^{t} bot(Δ_{i}) is a ⟨g⟩-E_{f,p}-symbol, and the proposition is proved.

5.3 Solving the Order Problem

Our aim in this section is to establish the following dichotomy.

Proposition 5.8 For g ∈ H_{f,p} one of the following holds.

(i) There is a flat fake-E_{f,p}-symbol for g, or

(ii) for some t ∈ IN, g^{t} has a step column.

First we show that it implies

Theorem 5.9 The order problem for H_{f,p} is solvable.

Proof. First we show that we can decide in finite time which of the two cases of the proposition holds. So let g ∈ H_{f,p} be given. If it is given to us as a word in the generators, we can effectively compute an M-symbol for g, since we can execute simple expansions effectively by (4.6). So we might as well assume that we are given an M-symbol Δ. In case g satisfies (i), g also has a flat M-symbol Γ such that Γ is an expansion of Δ, by Lemmas 5.4 and 6.1. Hence, checking all expansions of Δ, say simple expansions first, then simple expansions of the simple expansions an so forth, will eventually reveal a flat M-symbol. If, on the other hand, g satisfies (ii), then the following test works: compute symbols Δ_{2}, Δ_{3}, … for g^{2}, g^{3}, … and check them for step columns. By Lemma 5.3, it does not matter which particular M-symbol Δ_{i} for g^{i} we have computed, so the procedure stops. Thus, running both tests simultaneously, one of them will stop, by the proposition, as required.

To complete the proof we note first that an element g with a step column has infinite order, for otherwise there would be a flat E_{f,p}-symbol for g, by Lemma 5.7, which contradicts Lemma 5.3, by which every symbol for g has a step column. Now suppose g has a flat fake-E_{f,p}-symbol Δ. Then for every column of Δ^{t} the top and bottom row entries are equal, where t = |top(Δ)|!. So g has finite order if and only if all the middle row entries of Δ^{t} are periodic which we can decide by Theorem 5.2. This completes the proof of the Theorem.

The proof of the proposition that follows is close to Higman’s proof for the solvability of the order problem for G_{n,r}. But to make those arguments work we need to extend the domain of the elements of E_{f,p}. As mentioned before, the group E_{f,p} can be described as a group of tree automorphisms of the tree W_{p}, and we adopt this point of view here. More precisely, for e ∈ E_{f,p} and w ∈ W_{p} define

wē = \{ \begin{matrix}w^{e}, & if w^{e} is defined \\ w, & otherwise \end{matrix}

A glance at the definition of e(= b_{ω}) in Section 4.3 shows that e ⟼ ē is a well define injection from the group E_{f,p} of maximal inescapable isomorphisms into the automorphism group of the tree W_{p} (see Section 1.5). Moreover, this definition is compatible with expansions in the sense that for every fake-E_{f,p}-symbol Δ for e the restriction of ē to the subspace top(Δ)W_{p} is the same map as the one defined by the symbol obtained from Δ by ‘baring’ all middle row entries. Here we are assuming that we have also extended the action of γ by setting ∅γ̄ = ∅.

For the remainder of this section we omit the bars and assume that elements of M act as tree automorphisms.

Remark. The point is that, contrary to the situation for inescapable isomorphisms, (bw)^{g} is now defined for all w ∈ W_{p} and b ∈ top(Δ), where Δ is any M-symbol for g. But it is no longer true that for v = wz, (bv)^{g} = (bw)^{g}z. However, we still have (bv)^{g} = (bw)^{g}z′ for some z′ ∈ W_{p} of the same length as z, because middle row entries preserve this length (automorphisms of a rooted tree have to fix the root).

From now on g is an arbitrary but fixed element of H_{f,p}. We call a basis B benign (for g) if it is finite and w^{g^{−1}} and w^{g} are defined for all w ∈ BW_{p}. Note that every expansion of a benign is also benign.

Lemma 5.10 There exists a benign basis B such that, for every w ∈ BW_{p} there is ε ∈ {±1} with w^{g^{εt}} ∈ BW_{p} for all t ∈ IN.

Proof. Let B be a benign basis and put U = BW_{p}. For u ∈ U define the quasi-orbit O(u) of u as follows. Let s ≤ 0 be minimal subject to u^{g^{k}} ∈ U for all k with s ≤ k ≤ 0 or s = −∞ if u^{g^{k}} ∈ U for all k ≤ 0, and let t ≥ 0 be maximal subject to u^{g^{k}} ∈ U for all k with 0 ≤ k ≤ t or t = ∞ if u^{g^{k}} ∈ U for all k ≥ 0. Then O(u) = {u^{g^{k}} | s ≤ k ≤ t}. We say u is of finite type if both s and t are finite, and in that case u^{g^{s}} and u^{g^{t}} are called ends of O(u). Observe that B satisfies the lemma if there are no elements in U of finite type and that O(v) = O(u) for all v ∈ O(u).

Let us show that there are only finitely many elements of finite type in U. Let v be an end of O(u), then v^{g^{ε}} ∈ W_{p} \ U for some ε ∈ {±1} and we say v^{g^{ε}} is an exit of O(u). It is straightforward that each element of W_{p} \ U is the exit of at most two different quasi-orbits. Since W_{p} \ U is finite and every quasi-orbit of finite type is finite and has an exit, there are only finitely many elements of finite type in U.

Now assume that u is of finite type and write u = bv with b ∈ B and v ∈ W_{p}. Then b is also of finite type, since b^{g^{k}} ≤ u^{g^{k}} for all k such that b^{g^{k}} is defined. Let C be the simple expansion of B at b and note that CW_{p} has the same elements of finite type as U but b. Hence, by induction on the number of elements of finite type, there is a benign basis D such that D has no elements of finite type, and the lemma is proved.

A benign basis satisfying Lemma 5.10 is called a normal basis (for g). Observe that the proof of the lemma gives an effective procedure for finding a normal basis and, moreover, that every benign basis has a normal expansion.

Proof of Proposition 5.8. Let B be a normal basis for g such that g has an M-symbol with top row B. Suppose b ∈ B such that O(b) finite. Then we claim that b^{g^{i}} ∈ B for all i ∈ ZZ. For otherwise there is b′ ∈ O(b) such that b^{′g} = b′′v with b′′ ∈ B and ∅ ≠ v ∈ W_{p}, and hence b′ = (b′′v)^{g^{−1}} = b^{′′g^{−1}}v′ for some ∅ ≠ v′ ∈ W_{p}, since B is benign. This implies b^{′′g^{−1}} ∉ BW_{p} which force O(b′′) to be infinite, as B is normal. It follows that O(b) must also be infinite, a contradiction. Thus, the M-symbol for g with top row B is flat if all elements of B have finite quasi-orbits. So (i) holds , by Lemma 5.4.

Now assume that O(b) is infinite for b ∈ B. By possibly replacing g by g^{−1} we can assume that b^{g^{i}} ∈ BW_{p} for all i ≥ 0. Define t(b) to be the maximal integer subject to b^{g^{i}} ∉ B for 0 ≤ i < t(b) and let b̂ = b^{g^{t(b)}} (t(b) exists since B is finite). Then b̂ = b_{1}v_{1} for some b_{1} ∈ B and ∅ ≠ v_{1} ∈ W_{p}. As before, b_{1}^{g^{−1}} ∉ BW_{p}, and O(b_{1}) is infinite, since it is not of finite type (B is normal). In particular, b_{1}^{g^{i}} ∈ BW_{p} for i ≥ 0. Iterating this argument we get b_{i} ∈ B with b_{i}v_{i} = b̂_{i−1}, v_{i} ∈ W_{p}, and, as B is finite, we find j ≥ 0 with j < k and b_{j} = b_{k}, where b_{0} = b. For 1 ≤ i ≤ k − 1 put t_{i} = t(b_{i}) and check that

b_{j}^{g^{t_{j} +t_{j+1}+···+t_{k−1}}} = (b_{j+1}∗)^{g^{t_{j+1}+···+t_{k−1}}}
= (b_{j+2}∗)^{g^{t_{j+2}+···+t_{k−1}}}
⋮
= (b_{k−1}∗)^{g^{t_{k−1}}}
= b_{j}∗

where the ∗ is to be replaced by some non-empty element of W_{p}, possibly varying from line to line. It is now clear that g^{t_{j}+t_{j+1}+···+t_{k−1}} has a step column, and the proof of the proposition is complete.

As all the steps of this proof can be carried out effectively, we get immediately

Chapter 5

Corollary 5.11 For g ∈ H_{f,p} it is effectively decidable whether g has a flat fake-E_{f,p}-symbol.

The Conjugacy Problem

This chapter is the outcome of an attempt to solve the conjugacy problem for the groups H_{p,f}. A group has a solvable conjugacy problem if given two arbitrary elements one can effectively decide whether they are conjugate in the group. Since an element is conjugate to the identity if and only if it is the identity, the solvability of the conjugacy problem implies the solvability of the word problem. However, we cannot give a complete solution but we prove an affirmative answer for elements that have flat symbols. This includes all elements of finite order (Proposition 5.7) and in addition some elements of infinite order. Since this involves already quite a lot of notation even in the case where p is a prime and gets considerably more complicated if p is not prime, we assume from now on that p is a prime. This restriction is most important in Section 6.6.

6.1 Pseudo-Orbits and their Characteristics

Here we investigate flat fake-E_{f,p}-symbols in greater detail. Although this notion came up earlier, it was mainly developed to treat the conjugacy problem, and hence it appears in this chapter.

Let Δ be a ⟨g⟩-fake-E_{f,p}-symbol (this includes being a ⟨g⟩-E_{f,p}-symbol). Then there is a well defined permutation π_{g}(Δ) of top(Δ), given by b^{π_{g}(Δ)} = c, where

( \begin{matrix}b \\ x \\ c \end{matrix} )

is a column of Δ. We call the orbits of π_{g}(Δ) in top(Δ) pseudo-orbits of g. We also let π_{g}(Δ) permute (the set of columns of) Δ according to their top-entries. For convenience, we think hereafter of a symbol as a set of columns, so that we may speak of the pseudo-orbits of g in Δ. Since such a pseudo-orbit O is again nothing but a set of columns, we will usually denote it by

( \begin{matrix}o_{1} & o_{2} & ⋯ & o_{t−1} & o_{t} \\ x_{1} & x_{2} & ⋯ & x_{t−1} & x_{t} \\ o_{2} & o_{3} & ⋯ & o_{t} & o_{1} \end{matrix} ) .  (6.1)

Let P S(Δ) denote the set of pseudo-orbits of Δ, having in mind that this requires Δ to be at least a flat symbol. But we will only deal with flat M-symbols in the sequel.

Convention. It is now convenient to distinguish a word over the alphabet C ∪ E_{f,p} from the element of M it represents. We have to be even more rigorous, and take elements of the free product C ∗E_{f,p} into account as well. If w ≡ x_{1} ⋯ x_{r} is a word over C ∪ E_{f,p}, i.e., x_{i} ∈ C ∪ E_{f,p}, we write \overline{w} for the element of M it represents. By l(w) we denote the length of w as an element of C ∗ E_{f,p}, i.e., we lump together consecutive occurrences of letters of the same factor and.

Suppose now O ∈ P S(Δ) is given by (6.1). We define the characteristic of O, denoted χ(O), to (be the word) x_{1}x_{2} ⋯ x_{t}. And define the trace of the pseudo-orbit Oby

tr(O) = \{ \begin{matrix}0, & if \overline{x_{1}x_{2} ⋯ x_{t}} = 1 \\ 1, & otherwise. \end{matrix}

Note that the definition of χ(O) depends on the choice of o_{1} and that, for a different choice of o_{1} the characteristic is a cyclic conjugate x_{i} ⋯ x_{t}x_{1} ⋯ x_{i−1} of χ(O). In contrast, the characteristic is independent of that choice. It also makes sense to say that O has finite (infinite) characteristic if \overline{χ(O)} has finite (infinite) order. Similarly, we say that χ(O) lies in the kernel of Ψ if \overline{χ(O)} does, where Ψ is the homomorphism defined just before Theorem 5.1. It is clear that all these latter definitions are independent of the choice of o_{1}. But they depend heavily on the intrinsic order that is determined by the cycle structure of π_{g}(Δ).

Let O be a pseudo-orbit of Δ. By a simple pseudo-orbit expansion of Δ at O we mean the resulting symbol after simply expanding Δ at all columns of O (a subset of Δ). And as before, we say that Γ is a pseudo-orbit expansion of Δ if there are finitely many symbols Δ_{0}, …, Δ_{k} such that Δ = Δ_{0}, Γ = Δ_{k} and Δ_{i} is a simple pseudo-orbit expansion of Δ_{i−1} at some O ∈ P S(Δ_{i−1}) for 1 ≤ i ≤ k.

Lemma 6.1 Suppose g ∈ H_{f,p} has a flat fake-E_{f,p}-symbol. Then g has a unique minimal flat fake-E_{f,p}-symbol Δ, in the sense that every other ⟨g⟩- E_{f,p}-symbol Γ is an expansion of Δ. Moreover, every such Γ is in fact a pseudo-orbit expansion of Δ, and conversely, every pseudo-orbit expansion of Δ gives such a Γ. Consequently, g has arbitrary large flat fake-E_{f,p}- symbols.

Proof. Suppose Γ_{1} and Γ_{2} are two ⟨g⟩-fake-E_{f,p}-symbols and top(Γ_{1}) ≠ top(Γ_{2}). We may now assume that there is o_{1} ∈ top(Γ_{1}) with o_{1} ∉ top(Γ_{2})W_{p}. Let O be the pseudo-orbit in Γ_{1} containing o_{1}. Then it is clear that for every o ∈ top(O), o ∉ top(Γ_{2})W_{p}. Let

U = {C ∈ Γ_{2} | top(C) ∈ top(Γ_{2}) ∩ top(O)W_{p}}

and observe that Γ_{3} = (Γ_{2}\U)∪O is a ⟨g⟩-fake-E_{f,p}-symbol and a proper contraction of Γ_{2}. Therefore, the assumption that both Γ_{1} and Γ_{2} are minimal gives a contradiction, and hence there is a unique minimal flat fake-E_{f,p}- symbol for g. The second part of the lemma follows from the obvious fact that for every proper non-empty subset J of {1, …, t} the result of simply expanding all columns with top entry o_{j}, j ∈ J, of the pseudo-orbit (6.1) does not lead to a flat fake-E_{f,p}-symbol. This proves the lemma.

6.2 Conjugate Flat Symbols

Here we gather some obviously necessary conditions for elements with flat fake-E_{f,p}-symbols to be conjugate. Assume that g and h are elements of a single conjugacy class of H_{f,p}, say x^{−1}gx = h for some x ∈ H_{f,p}, and that g has a flat fake-E_{f,p}-symbol. Since H_{f,p} is E_{f,p}-expansible (Lemma 4.9) we find E_{f,p}-symbols Σ, Δ, Λ, and Γ for x^{−1}, g, x, and h, respectively, such that

ΣΔΛ = Γ.  (6.2)

Recall that each (simple) expansion of a fake-E_{f,p}-symbol is again a fake-E_{f,p}-symbol and, that for every combination Δ_{1} ⋯ Δ_{r} of fake-E_{f,p}-symbols and given expansion Γ_{i} of Δ_{i}, there are expansions Γ_{j} ⪰ Δ_{j}, 1 ≤ j ≠ i ≤ r, so that Γ_{1} ⋯ Δ_{r} exists, by (5.1) and (5.3). By our assumptions, it is now possible to do the following: expand (6.2) so that the symbol for g becomes a flat fake-E_{f,p}-symbol. The obtained combination is of the form

Σ^{−1}ΔΣ = Γ,  (6.3)

where Γ is a fake-E_{f,p}-symbol for h, Δ is a ⟨g⟩-fake-E_{f,p}-symbol, and Σ is a fake-E_{f,p}-symbol for x. It follows that Γ is in fact a flat fake-E_{f,p}-symbol. Let (6.1) be a pseudo-orbit, O say, of g in Δ and let

( \begin{matrix}w_{1} & w_{2} & ⋯ & w_{t−1} & w_{t} \\ y_{1}^{−1} & y_{2}^{−1} & ⋯ & y_{t−1}^{−1} & y_{t}^{−1} \\ o_{1} & o_{2} & ⋯ & o_{t−1} & o_{t} \\ x_{1} & x_{2} & ⋯ & x_{t−1} & x_{t} \\ o_{2} & o_{3} & ⋯ & o_{t} & o_{1} \\ y_{2} & y_{3} & ⋯ & y_{t} & y_{1} \\ w_{2} & w_{3} & ⋯ & w_{t} & w_{1} \end{matrix} )

be the corresponding part of the left hand side of (6.3). Then

( \begin{matrix}w_{1} & w_{2} & ⋯ & w_{t−1} & w_{t} \\ y_{1}^{−1}x_{1}y_{2} & y_{2}^{−1}x_{2}y_{3} & ⋯ & y_{t−1}^{−1}x_{t−1}y_{t} & y_{t}^{−1}x_{t}y_{1} \\ w_{2} & w_{3} & ⋯ & w_{t} & w_{1} \end{matrix} )  (6.4)

is a pseudo-orbit, U say, of h in Γ. Moreover, the characteristic of U is y_{1}^{−1}χ(O)y_{1}. In particular, U has finite characteristic or lies in the kernel of Ψ if and only if O has finite characteristic or respectively lies in the kernel of Ψ. Also note that the y_{i} are elements of the finite set E_{f,p} ∪ C. Thus, given a flat fake-E_{f,p}-symbol Ω for g, we can list in finite time all possible characteristics of pseudo-orbits of elements conjugate to g such that Ω occurs in the corresponding combination of fake-E_{f,p}-symbols. This should make clear that we have to investigate the behaviour of pseudoorbits under pseudo-orbit expansions if we seek a solution to the conjugacy problem. This is precisely what follows.

6.3 Pseudo-Orbit Expansions

Let Δ be a flat fake-E_{f,p}-symbol and let O ∈ P S(Δ). We say that O is of class I if χ(O) lies in the kernel of the homomorphism Ψ : M ⟶ C defined just before Theorem 5.2, and of class II otherwise.

Lemma 6.2 Let Δ be a ⟨g⟩-fake-E_{f,p}-symbol and O ∈ P S(Δ). Suppose Γ is the simple pseudo-orbit expansion of Δ at O and χ(O)^{Φ} = (m_{1}, …, m_{p})π. Then we can order the columns of Γ so that Γ has the same pseudo-orbits as Δ except for O which gets replaced by pseudo-orbits O_{i} according to the following two cases.

1. If O is of class I, then 1 ≤ i ≤ p, χ(O_{i}) = m_{i}, and |O_{i}| = |O|.

2. If O is of class II, then i = 1, χ(O_{1}) = m_{1}m_{1π} ⋯ m_{1π^{p−1}}, and |O_{1}| = p|O|.

Moreover, l(χ(O_{i})) ≤ l(χ(O)) for all i in question and with strict inequality in the first case.

Proof. Suppose O is given by (6.1) and x_{i}^{Φ} = (x_{i,1}, …, x_{i,p})σ_{i} for 1 ≤ i ≤ p. Put π_{i} = σ_{1} ⋯ σ_{i}, 1 ≤ i ≤ t and observe that π = π_{t}, so π_{t} = 1 if and only if O is of class I.

Suppose first that O is of class I. Then it follows from the correspondence between Φ and symbols for elements of M (see (5.3) and (5.4)) that the result of simply expanding all columns of O contains

( \begin{matrix}o_{1}a_{i} & o_{2}a_{iπ_{1}} & ⋯ & o_{t}a_{iπ_{t−1}} \\ x_{1,i} & x_{2,iπ_{1}} & ⋯ & x_{t,iπ_{t−1}} \\ o_{2}a_{iπ_{1}} & o_{3}a_{iπ_{2}} & ⋯ & o_{1}a_{i} \end{matrix} )

for 1 ≤ i ≤ p. This is clearly a pseudo-orbit, O_{i} say, and its characteristic is x_{1,i}x_{2,iπ_{1}} ⋯ x_{t,iπ_{t−1}} which is soon shown to be the i-th component of (x_{1}x_{2} ⋯ x_{t})^{Φ}. Clearly, |O_{i}| = |O|.

Assume now that O is of class II, i.e., π_{t} ≠ 1. Then the result of simply expanding all columns of O is

( \begin{matrix}o_{1}a_{1} & o_{2}a_{1π_{1}} & ⋯ & o_{t}a_{1π_{t−1}} & ⋯ & o_{1}a_{iπ_{t}^{p−1}} & ⋯ & o_{t}a_{1π_{t}^{p−1}π_{t−1}} \\ x_{1,1} & x_{2,1π_{1}} & ⋯ & x_{t,1π_{t−1}} & ⋯ & x_{1,1π_{t}^{p−1}} & ⋯ & x_{t,1π_{t}^{p−1}π_{t−1}} \\ o_{2}a_{1π_{1}} & o_{3}a_{1π_{2}} & ⋯ & o_{1}a_{1π_{t}} & ⋯ & o_{2}a_{1π_{t}^{p−1}π_{1}} & ⋯ & o_{1}a_{1} \end{matrix} ) ,

which is a pseudo-orbit of cardinality p|O| and with characteristic

x_{1,1}x_{2,1π_{1}} ⋯ x_{t,1π_{t−1}} ⋯ x_{1,1π_{t}^{p−1}} ⋯ x_{t,1π_{t}^{p−1}π_{t−1}}.

The claims about the relations between the characteristics of O and its expansion follow immediately from our assumption on x_{i}^{Φ} and the following computation.

(x_{1}x_{2} ⋯ x_{t})^{Φ} = (x_{1,1}, …, x_{1,p})(x_{2,1}, …, x_{2,p})^{π_{1}^{−1}} ⋯ (x_{t,1}, …, x_{t,p})^{π_{t−1}^{−1}}π_{t} = (x_{1,1}, …, x_{1,p})(x_{2,1π_{1}}, …, x_{2,pπ_{1}}) ⋯ (x_{t,1π_{t−1}}, …, x_{t,pπ_{t−1}})π_{t}

= (x_{1,1}x_{2,1π_{1}} ⋯ x_{t,1π_{t−1}} , …, x_{1,p}x_{2,pπ_{1}} ⋯ x_{t,pπ_{t−1}})π_{t}

Finally, the statement about the length of the characteristics follows from the corresponding statements in the proof of Theorem 5.2, by noting that m_{1}m_{1π} ⋯ m_{1π^{p−1}} is the first component of ((m_{1}, m_{2}, …, m_{p})π)^{p}. This proof of the lemma is complete.

6.4 Normal Symbols

For the flat fake-E_{f,p}-symbol Δ, define

F P S(Δ) = \{O ∈ P S(Δ) | |\overline{χ(O)}| < ∞\} and

IP S(Δ) = \{O ∈ P S(Δ) | |\overline{χ(O)}| = ∞\} .

These two sets are effectively computable from Δ, by Theorem 5.2. We call Δ a normal symbol for g, if it is a ⟨g⟩-fake-E_{f,p}-symbol and, in addition, satisfies the following condition (N) For every expansion Γ of Δ which is also a flat fake-E_{f,p}-symbol and

for all O ∈ IP S(Γ), O is of class II.

Note that (N) is also a condition for Δ itself since Δ is trivially an expansion of Δ.

The reason for this definition is that we would like to write a flat fake-E_{f,p}- symbol Δ for g as the combination of two flat fake-E_{f,p}-symbols Δ_{F}, Δ_{I}; the former containing only pseudo-orbits with finite characteristic, and the latter having only pseudo-orbits with infinite characteristics and trivial columns. This decomposition will define two elements g_{F} and g_{I} in a natural way, the only trouble is that this definition is not independent of the choice of the flat fake-E_{f,p}-symbol. As a pseudo-orbit with infinite characteristic can lead to a pseudo-orbit with finite characteristic under pseudo-orbit expansions (see the example below). We show in Lemma 6.3 that for a normal symbol for g this will be well defined. Let us first give an example of a flat fake-E_{f,p}- symbol which is not normal.

Example. Consider the group H_{2,2} and let ω, σ, and τ be the 2-periodic sequences with periods 11, 10, and 01, respectively. Then it is an easy exercise application of Theorem 5.2 that γb_{ω} and b_{τ} γ have infinite respectively finite order. Suppose

O = ( \begin{matrix}o_{1} & o_{2} & o_{3} & o_{4} \\ b_{σ} & γ & b_{ω} & γ \\ o_{2} & o_{3} & o_{4} & o_{1} \end{matrix} )

is a pseudo orbit of a flat fake-E_{f,p}-symbol Δ for some element of H_{2,2}. Since (b_{σ}γb_{ω}γ)^{Φ} = (γb_{ω}, b_{τ} γ), we have that O of class I and hence Δ is not normal. Note that O has infinite characteristic. By Lemma 6.2 and the usual expansion rules, in the simple pseudo-orbit expansion of Δ at O, O leads to

O_{1} = ( \begin{matrix}o_{1}a_{1} & o_{2}a_{1} & o_{3}a_{2} & o_{4}a_{2} \\ γ & 1 & b_{ω} & 1 \\ o_{2}a_{1} & o_{3}a_{2} & o_{4}a_{2} & o_{1}a_{1} \end{matrix} ) and O_{2} = ( \begin{matrix}o_{1}a_{2} & o_{2}a_{2} & o_{3}a_{1} & o_{4}a_{1} \\ b_{τ} & 1 & γ & 1 \\ o_{2}a_{2} & o_{3}a_{1} & o_{4}a_{1} & o_{1}a_{2} \end{matrix} ) .

Observe that O_{1} has infinite characteristic, whereas O_{2} has finite characteristic.

The following lemma says that for a normal symbol the pathology of the above example cannot occur.

Lemma 6.3 Let Δ be a normal symbol for g ∈ H_{f,p}, and let Γ be a pseudoorbit expansion of Δ. Then the following hold.

a) Γ is a normal symbol for g

b) If U ∈ F P S(Γ), then top(U) ⊂ top(O)W_{p} for some O ∈ F SP (Δ).

Proof. To see a) it suffices to note that Γ is a ⟨g⟩-fake-E_{f,p}-symbol satisfying (N), since all its pseudo-orbit expansions are also pseudo-orbit expansions of Δ. To prove b) it suffices to consider simple pseudo-orbit expansions of Δ. By case 2 of Lemma 6.2, a pseudo-orbit of class II with infinite characteristic leads to precisely one pseudo-orbit with infinite characteristic under a simple pseudo-orbit expansion, and condition (N) forces this pseudo-orbit to be of class II again. so U cannot be the expansion of a pseudo-orbit of class II with infinite characteristic, and the lemma is proved. The existence of normal symbols is our next task.

Proposition 6.4 Suppose g ∈ H_{f,p} has a flat fake-E_{f,p}-symbol. Then g has a normal symbol.

Proof. Let us start with a verbal version of Lemma 6.3 b): for every pseudoorbit expansion of a normal symbol, pseudo-orbits with finite characteristic can only come from pseudo-orbits with finite characteristic. From the proof of that statement it is clear that only pseudo-orbits of class I with infinite characteristic may lead to ‘new’ pseudo-orbits with finite characteristic. In this case, the length of the characteristic of the new pseudo-orbits is strictly smaller than the length of the original characteristic, by Lemma 6.2. Therefore, new pseudo-orbits with finite characteristic, in the sense that they come from a pseudo-orbits with infinite characteristic, cannot occur infinitely many times in the process of performing simple pseudo-orbit expansions at pseudo-orbits with infinite characteristic over and over again. We will know when to stop, when we find that two expansions of the same pseudo-orbit with infinite characteristic have equal characteristics, which must happen by the arguments in the proof of Theorem 5.2. The proof is complete.

6.5 The Conjugacy Problem: I

Having normal symbols at hand, we show here that we can divide the conjugacy problem for elements with flat symbols into two parts: those with pseudo-orbits of finite characteristics on the one hand, and those with either trivial columns or pseudo-orbits of infinite characteristics on the other hand. The latter part is easier and proven to be solvable also in this section. First we need to introduce more notation.

Let Δ be a normal symbol for g. Define

top(Δ)_{I} = {top(C) | C ∈ O ∈ IP S(Δ)},

top(Δ)_{F} = {top(C) | C ∈ O ∈ F P S(Δ)},

Δ_{I} = ( ⋃_{O∈IP S(Δ)} O) ∪ \{( \begin{matrix}b \\ 1 \\ b \end{matrix} ) | b ∈ top(Δ)_{F} \}

and

Δ_{F} = ( ⋃_{O∈F P S(Δ)} O) ∪ \{( \begin{matrix}b \\ 1 \\ b \end{matrix} ) | b ∈ top(Δ)_{I} \} .

Remark. Note that top(Δ)_{I} and top(Δ)_{F} are disjoint with union top(Δ), and that bot({C | top(C) ∈ top(Δ_{X})}) = top(Δ_{X}) for X = F, I. Hence Δ_{I} and Δ_{F} are well defined. It should be clear that Δ_{F} defines a periodic element, whereas Δ_{I} defines an element of infinite order.

Lemma 6.5 Let Δ be a normal symbol for g ∈ H_{f,p} and let g_{F} and g_{I} be the elements defined by Δ_{F} and Δ_{I}, respectively. Then g_{F} and g_{I} are independent of the choice of the normal symbol Δ and g = g_{I}g_{F} = g_{F} g_{I}.

Proof. A similar proof to that for Lemma 6.1 shows that there is a unique minimal normal symbol Δ for g such that every other normal symbol for g is a pseudo-orbit expansion of Δ. In fact every pseudo-orbit expansion Γ of Δ is a normal symbol for g, by Lemma 6.3, which also shows that top(Γ)_{F} ⊂ top(Δ)_{F} W_{p}. Together with top(Γ)_{I} ⊂ top(Δ)_{I}W_{p} which obviously holds, we get Γ_{F} ⪰ Δ_{F} and Γ_{I} ⪰ Δ_{I}. Hence Γ_{F} is a symbol for g_{F} and Γ_{I} is a symbol for g_{I}, whence the definition of g_{F} and g_{I} are independent of the choice of normal symbol Δ for g. It is plain from the definitions that g = g_{I}g_{F} = g_{F} g_{I}, and the lemma is proved.

Proposition 6.6 Assume g, h ∈ H_{f,p} have flat fake-E_{f,p}-symbols. Then g and h are conjugate in H_{f,p} if and only if g_{F} is conjugate to h_{F} and g_{I} is conjugate to h_{I}.

Proof. First suppose that, for some x ∈ H_{f,p}, x^{−1}gx = h is a relation in H_{f,p}. Now g and h have normal symbols, by Lemma 6.4, and, by Lemma 6.3 a), we can expand (6.2) so that Σ^{−1}ΔΣ = Γ holds, where Δ and Γ are normal symbols and Σ is a fake-E_{f,p}-symbol. It follows by what was said about the characteristics after (6.3) that Σ^{−1}Δ_{F} Σ = Γ_{F} and Σ^{−1}Δ_{I}Σ = Γ_{I}. Thus g_{F} is conjugate to h_{F} and g_{I} is conjugate to h_{I}, by Lemma 6.5.

For the converse assume that x^{−1}g_{F} x = h_{F} and y^{−1}g_{I}y = h_{I} hold in H_{f,p} for some x, y ∈ H_{f,p}. Then there are fake-E_{f,p}-symbols Σ, Λ, Δ, and Γ for x, y, g, and h, respectively, such that

Σ^{−1}Δ_{F} Σ = Γ_{F}  and  Λ^{−1}Δ_{I}Λ = Γ_{I}.

Define the essential parts of Σ and Λ to be the following collections of columns

Σ_{e} = {C ∈ Σ | top(C) ∈ top(Δ)_{F} }

and

Λ_{e} = {C ∈ Λ | top(C) ∈ top(Γ)_{F} }.

By the remark preceding Lemma 6.5, top(Σ_{e}) and top(Λ_{e}) are disjoint, top(Σ_{e}) ∪ top(Λ_{e}) = top(Δ), top(Σ_{e}) = bot(Σ_{e}), and top(Λ_{e}) = bot(Λ_{e}). Hence Ω = Σ_{e} ∪ Λ_{e} is a fake-E_{f,p}-symbol and it is easy to check that the combination Ω^{−1}ΔΩ exists and is equal to Γ. This proves the Proposition.

We end this section by showing that we can decide whether g_{I} and h_{I} are conjugate. In the following sections we tackle the considerably more difficult task to decide whether g_{F} and h_{F} are conjugate. One further definition is required. For a, b, r ∈ IN, we write a ≡^{∗} b (mod r), if a ≡ b (mod r) and a = 0 if and only if b = 0.

Proposition 6.7 Let g and h be elements of H_{f,p} which have flat fake-E_{f,p}- symbols. Then it is decidable whether g_{I} and h_{I} are conjugate.

Proof. First recall the definition of the trace of a pseudo-orbit (p. 73). For a flat fake-E_{f,p}-symbol Σ, let tt(Σ) be the number of pseudo-orbits of Σ with trace zero (trivial trace) and nt(Σ) the number of pseudo-orbits of Σ with trace one. Suppose g_{I} and h_{I} are defined by Δ_{I} respectively Γ_{I}, where Δ and Γ are normal symbols for g and h. Assume for a moment that Σ is a pseudo-orbit expansion of Δ_{I}. Then nt(Σ) = nt(Δ_{I}) and tt(Σ) ≡^{∗} tt(Δ_{I}) (mod p − 1), by Lemma 6.2 and condition (N). Hence we see from the discussion in Section 6.2 that the following three conditions are necessary for g_{I} and h_{I} to be conjugate.

1) nt(Δ_{I}) = nt(Γ_{I})

2) tt(Δ_{I}) ≡^{∗} tt(Γ_{I}) (mod p − 1)

3) There are suitably ordered pseudo-orbit expansions Δ′_{I} and Γ′_{I} of Δ_{i} respectively Γ_{I} and elements y_{1}, …, y_{r} ∈ E_{f,p} ∪ C such that, for suitable listings of their pseudo-orbits O_{1}, …, O_{r} respectively U_{1}, …, U_{r}, χ(O_{i})^{y_{i}} = χ(U) for 1 ≤ i ≤ r, where r = nt(Δ).

That these conditions are also sufficient is a consequence of the first part of Lemma 6.2, which together with condition 2) implies that we can choose Δ′_{I} and Γ′_{I} with the same number of trivial columns, and the fact that every fake-E_{f,p}-symbol defines an element of H_{f,p}. Let us show how to check in finite time whether these three conditions are satisfied by the given Δ_{I} and Γ_{I}. Clearly, we only need to check condition 3) in case 1) and 2) hold already.

We claim that there is a finite subset S of M so that for every pseudo-orbit U of any pseudo-orbit expansion Σ of Δ_{I}, χ(U) ⊂ S. This follows from the last statement of Lemma 6.2 by which the length of all possible characteristic of such U are bounded. Now we are left to check finitely many things to find whether condition 3) can be satisfied, since there are only finitely many pseudo-orbit each with only finitely many possible characteristics for its expansions, which can be cyclically reordered in finitely many ways, and only finitely many elements to choose the y_{i} from. The proof is complete.

Remark. It is worth noting that until now we have not used our assumption that p is a prime.

6.6 Legal Symbols and their Index

Now we deal with the question whether g_{F} and h_{F} are conjugate for given elements g and h of H_{f,p} which admit flat fake-E_{f,p}-symbols. In other words we attack the conjugacy problem for elements of finite order which, by Proposition 5.7, are precisely those elements with a flat E_{f,p}-symbol.

Call Δ is a legal symbol for g if it is a ⟨g⟩-fake-E_{f,p}-symbol and an expansion of a flat E_{f,p}-symbol for g. In particular, an element of H_{f,p} has a legal symbol if and only if it has finite order. The following result divides the pseudo-orbits of legal symbols into two genuinely different classes. Recall that C = ⟨γ⟩, where γ has the symbol (5.1).

Lemma 6.8 Suppose Γ is a legal symbol for g ∈ H_{f,p}. Then for each pseudo-orbit O of g in Γ one (and only one) of the following holds.

I) All middle row entries of O belong to C.

II) One of the middle row entries of O belongs to E_{f,p} \{1}. Furthermore, in this case all middle row entries of O are in E_{f,p}. Consequently, the characteristic of O is independent of the order of the columns of Γ.

We will speak of pseudo-orbits of type I or II depending on which statement of the lemma they satisfy and we denote the type of O by t(O).

Proof. First of all, note that every flat E_{f,p}-symbols satisfies the dichotomy of the lemma. As Γ is a pseudo-orbit expansion of some E_{f,p}-symbol, it suffices to check that a simple pseudo-orbit expansion of a flat fake-E_{f,p}- symbol that satisfies the lemma also satisfies the lemma. This can be seen from Lemma 6.2 as follows. If a pseudo-orbit is of type I, then all the x_{i,j} in the proof of that lemma are trivial, so all the resulting pseudo-orbits are of type I again. If, on the other hand, a pseudo-orbit is of type II, then it is of class I, and all the π_{i} are trivial. It follows from (4.6) that only middle row entries from either E_{f,p} or C contribute to the characteristic of resulting pseudo-orbit. The final statement follows because E_{f,p} is abelian, by Lemma 4.9, and the lemma is proved.

It is convenient to introduce the following terminology for the legal symbol Δ. The rank of Δ, denoted r(Δ), is given by

r(Δ) = |P S(Δ)|.

For O ∈ P S(Δ), we define the index i(O) of O by

i(O) = (χ(O), |O|),

and we call the unordered tuple

{i(O)}_{O∈P S(Δ)}

the index of Δ which we denote by i(Δ). A closer inspection of the proof of Lemma 6.8 easily gives the following result.

Proposition 6.9 Let Δ be a legal symbol for g. If Γ is the result of the simple pseudo-orbit expansion of Δ at O ∈ P S(Δ), then the following hold.

a) r(Γ) = \{ \begin{matrix}r(Δ), & if 1 ≠ \overline{χ(O)} ∈ C \\ r(Δ) + p − 1, & otherwise \end{matrix}

b) i(Γ) is obtained from i(Δ) by deleting i(O) and adding

(i) (1, cp), if i(O) = (δ, c) with 1 ≠ δ ∈ C, or

(ii) p times (1, c), if i(O_{i}) = (1, c), or

(iii) p − 2 times (1, c), (δ, c) and (e′, c), in case i(O) = (e, c), 1 ≠ e, and e has the symbol (5.2).

In particular, the number of pseudo-orbits of g of type II with non-trivial characteristic is independent of the chosen legal symbol for g.

The index of a legal symbol allows a first necessary and sufficient criterion for period elements to be conjugate.

Proposition 6.10 Let g, h ∈ H_{f,p} be elements of finite order. Then g and h are conjugate in H_{f,p} if and only if there are legal symbols Δ and Γ for g respectively h, such that i(Δ) = i(Γ), i.e. there is a bijection α : P S(Δ) ⟶ P S(Γ) with i(O^{α}) = i(O).

Proof. First assume x^{−1}gx = h is a relation in H_{f,p}. Doing a few expansions we may assume that we are in the situation of Section 6.2 with Δ and Γ of (6.3) being a flat E_{f,p}-symbol and a legal symbol, respectively. Obviously |U| = |O|, so once we establish χ(O) = χ(U), Δ and Γ clearly have the same index. By Lemma 6.8 and the form of Δ and Γ, we know χ(O) ∈ E_{f,p}, χ(U) ∈ C ∪ E_{f,p} and that χ(U) is independent of the order of multiplication. But from (6.4), χ(U) = χ(O)^{y_{i}} for 0 ≤ i ≤ t − 1. Surely, we may now assume χ(O) ≠ 1. From the definition of C and E_{f,p} we see that y_{i} ∈ E_{f,p} for 0 ≤ i ≤ t − 1. Since E_{f,p} is abelian we get χ(O) = χ(U), as required.

For the converse, let Δ and Γ be legal symbols for g and h, respectively, with i(Δ) = i(Γ). For 1 ≤ j ≤ r(Δ), let O_{j} and O_{j}^{α} be given by

( \begin{matrix}o_{1,j} & ⋯ & o_{t_{j}−1,j} & o_{t_{j},j} \\ x_{1,j} & ⋯ & x_{t_{j}−1,j} & x_{t_{j},j} \\ o_{2,j} & ⋯ & o_{t_{j},j} & o_{1,j} \end{matrix} ) and ( \begin{matrix}w_{1,j} & ⋯ & w_{t_{j}−1,j} & w_{t_{j},j} \\ z_{1,j} & ⋯ & z_{t_{j}−1,j} & z_{t_{j},j} \\ w_{2,j} & ⋯ & w_{t_{j},j} & w_{1,j} \end{matrix} )

respectively. Now define for 1 ≤ j ≤ r(Δ) the following elements of M inductively, y_{1,j} = 1 and y_{i+1,j} = x_{i,j}^{−1}y_{i,j}z_{i,j} for 1 ≤ i ≤ t_{j} − 1. Finally, let k ∈ H_{f,p} be the element with M-symbol

Φ = ⋃_{j=1}^{r(Δ)} \{( \begin{matrix}o_{i,j} \\ y_{i,j} \\ w_{i,j} \end{matrix} ) | 1 ≤ i ≤ t_{j}\} .

(Observe that every M-symbol defines an element of H_{f,p}.) Having in mind that x_{1,j} ⋯ x_{t_{j},j} = χ(O_{|}) = χ(O_{|}^{α}) = z_{1,j} ⋯ z_{t_{j},j}, it is now straightforward to check that Φ^{−1}ΔΦ exists and is equal to Γ. This completes the proof of the Proposition.

6.7 The Conjugacy Problem: II

Before we turn to the main result of this section we need yet more notation and describe some reductions. Let Δ be a legal ⟨g⟩-fake-E_{f,p}-symbol, then

|g| = \{ \begin{matrix}p|π_{g}(Δ)|, & if Δ^{π_{g}(Δ)} has pseudo-orbits with trace one \\ |π_{g}(Δ)|, & otherwise. \end{matrix}  (6.5)

Remark. This is the first time we use that p is a prime.

For each divisor d of the order of g we define

N_{d}(Δ) = {O ∈ P S(Δ) | i(O) = (1, d)},

F_{d}(Δ) = {O ∈ P S(Δ) | i(O = (δ, d), 1 ≠ δ ∈ C},

M_{d}(Δ) = {O ∈ P S(Δ) | i(O) = (e, d), 1 ≠ e ∈ E_{f,p}},

n_{d}(Δ) = \{ \begin{matrix}|N_{d}(Δ)| + |F_{d/p}(Δ)|, & if p divides d \\ |N_{d}(Δ)|, & otherwise, \end{matrix}

m_{d}(Δ) = |M_{d}(Δ)|, and finally

d − type(Δ) = {χ(O)}_{O∈M_{d}(Δ)},

by which we mean an unordered m_{d}(Δ)-tuple. We chose this notation because we distinguish normalised and fake pseudo-orbits of type I and pseudoorbits with non-trivial characteristic in the group E_{f,p} ⊂ M. Let us call Δ̂ a legal expansion of Δ, if Δ̂ is a legal symbol and also an expansion of Δ.

Assume now that we are given g, h ∈ H_{f,p} of finite order. First we find ⟨g⟩- and ⟨h⟩-E_{f,p}-symbols Δ and Γ, respectively. Note that this can be done effectively (see proof of Proposition 5.7). By Proposition 6.10, it suffices to give an effective procedure which decides whether there are Δ′ and Γ′, legal ⟨g⟩- and ⟨h⟩-fake-E_{f,p}-symbols, respectively, such that i(Δ′) = i(Γ′). In addition, we may assume that Δ′ and Γ′ expand Δ and Γ, so that all possible indices of such Δ′ and Γ′ can be effectively computed from those of Δ and Γ, by Proposition 6.9.

The following conditions are clearly necessary because they are invariant under simple pseudo-orbit expansion, by Proposition 6.9.

1) |g| = |h|

2) r(Δ) ≡ r(Γ) (mod p − 1)

3) m_{d}(Δ) = m_{d}(Γ) for all divisors d of |g|

These conditions can obviously be checked. Furthermore, since E_{f,p} is finite, there are only finitely many possibilities for the d−type of a legal expansion of Δ, and similarly for Γ. Therefore, by Proposition 6.9 b) (iii), we can also check if the following condition can be met.

4) There exist legal expansions of Δ and Γ with the same d − type for all divisors d of |g|.

Recall that a ≡^{∗} b (mod r) if a ≡ b (mod r) and a = 0 if and only if b = 0. We proceed with the following weakening of Proposition 6.10.

Lemma 6.11 Suppose Δ and Γ satisfy the requirements 1) − 4). Then g and h are conjugate in H_{f,p} if and only if

5) n_{d}(Δ) ≡^{∗} n_{d}(Γ) (mod p − 1) for all divisors d of |g|.

Proof. Only if follows directly from Proposition 6.10. We prove the if direction. By Proposition 6.9 b) (ii), it is clear that Δ and Γ have legal expansions Δ′ and Γ′ with n_{d}(Δ′) = n_{d}(Γ′) for all divisors d of |g|. From Proposition 6.9 b) (i) and the definition of n_{d} we see that we can expand Δ′ and Γ′ further to obtain Δ̂ and Γ̂ with n_{d}(Δ̂) = n_{d}(Γ̂) and F_{d}(Δ̂) = F_{d}(Γ̂) = ∅ for all divisors d of |g|. Since all these expansions leave the d−type fixed, it follows that i(Δ̂) = i(Γ̂). Now, by Proposition 6.10, g and h are conjugate, which completes the proof of the lemma.

The difficulty we have to overcome now is that pseudo-orbit expansions of orbits of type II can and will produce new fake pseudo-orbits and therefore may change the residue class of some n_{d}. So that we cannot be sure that g and h are not conjugate if the condition in the lemma is not satisfied for some choice of legal symbols satisfying 1) − 4). Hence we need a closer investigation of this phenomenon.

From now on will denote elements of E_{f,p} by their defining sequence, i.e., e = b_{ω} ∈ E_{f,p} is denoted by ω. And for ω, let P (ω) denote the period of ω; thus, P (ω) is the least non-zero positive integer with ω^{κ^{P (ω)}} = ω, where κ is the ‘forget’ (4.4). Furthermore, we define the multiplicator M(ω) of ω by

M(ω) = |{ω(i) | ω(i) ≠ 0, 0 ≤ i < P (ω)}|.

Theorem 6.12 Suppose g, h ∈ H_{f,p} have finite order. Then it is effectively decidable if g and h are conjugate in H_{f,p}.

Proof. Let Δ and Γ be legal symbols for g respectively h such that 1) − 4) hold. We are going to describe an effective procedure which decides whether Δ and Γ have legal expansions satisfying 5).

Suppose for a moment that d − type(Δ) = (ω_{1}, …, ω_{m_{d}(Δ)}) and let M_{i} = M(ω_{i}). Then it is an easy consequence of Proposition 6.9 b) (iii) that there is a legal expansion Δ′ of Δ such that d − type(Δ) = d − type(Δ′) and

n_{l}(Δ′) = \{ \begin{matrix}n_{d}(Δ) + (p − 2) ∑_{i=1}^{m_{d}(Δ)} λ_{i}M_{i}, & if l = d \\ n_{pd}(Δ) + ∑_{i=1}^{m_{d}(Δ)} λ_{i}M_{i}, & if l = pd \\ n_{l}(Δ), & if l ≠ d, pd \end{matrix} ,

for any choice of λ_{i} ∈ IN.

Let D(g) denote the set of all divisors of |g| that are not divisible by p and let η ∈ IN be such that p^{η} is the highest power of p dividing |g|. Hence, if d′ ∈ D(g) then every legal expansion Δ̂ of Δ with d′−type(Δ̂) = d′−type(Δ) satisfies

n_{d′}(Δ̂) = n_{d′}(Δ) + (p − 2) ∑_{i=1}^{m_{d′}(Δ)} λ_{i}M_{i}

for suitable λ_{i} ∈ IN. Furthermore, since Δ and Γ have the same d′ − type, there are legal expansions Δ′ and Γ′ with the same d′ − type and n_{d′}(Δ′) ≡^{∗} n_{d′}(Γ′) (mod p − 1) if and only if

n_{d′}(Δ) − n_{d′}(Γ) ≡ ∑_{i=1}^{m_{d′}(Δ)} ξ_{i}M_{i} (mod p − 1)  (6.6)

has a solution with ξ_{i} ∈ ZZ. This is because we can alter Δ and Γ and the fact that for Γ exactly the same M_{i} are to be used.

We may now assume that (6.6) has a solution for all d′ ∈ D(g). It is clear that for legal expansions Δ′ and Γ′ with d′ − type(Δ′) = d′ − type(Γ′) and n′_{d}(Δ′) ≡^{∗} n′_{d}(Γ′) (mod p − 1), d′ ∈ D(g), we have new values for n_{d′p}(Δ′) and n_{d′p}(Γ′) in comparison to Δ and Γ. But, by repeating the argument above for divisors of the form d′p^{i}, d′ ∈ D(g), 1 ≤ i ≤ η − 1 in increasing order, and noting that expansions of pseudo-orbits of index (e, d′p^{i}) (1 ≠ e ∈ E_{f,p}) leave n_{d′p^{j}} unchanged for 0 ≤ j < i, it is decidable whether g and h have legal symbols Δ′ and Γ′ satisfying n_{d}(Δ′) ≡^{∗} n_{d}(Γ′) (mod p−1) for all divisors d of \frac{|g|}{p} or |g| according to whether |g| is divisible by p or not. Thus, if for such Δ′ and Γ′ also n_{d}(Δ′) ≡^{∗} n_{d}(Γ′) (mod p − 1) holds for all other divisors d of |g|, then g and h are conjugate in H_{f,p}, by Lemma 6.11. On the other hand it is clear from the procedure that, if this is not the case then g and h do not have legal symbols which satisfy 5), whnece g and h cannot be conjugate in H_{f,p}, by Proposition 6.10. The proof of Theorem 6.12 is now complete.

Combining this result with Lemma 5.4, Proposition 6.6 and Proposition 6.7 we have

Theorem 6.13 The conjugacy problem for elements of G_{f,p} with flat Msymbols is solvable if p is a prime.

We would like to point out that this is the obvious adoption of the method used in [24] to classify conjugacy classes of finite subgroups of G_{n,r}. Only, here it gets a little more complex, as we have to take the group M into account. Let us conclude this thesis by showing that there are as many isomorphism classes among the H_{f,p}′ as possible and a proof of Theorem A stated in the introduction.

Theorem 6.14 If p and q are primes and p ≠ q, then H_{f,p} is not isomorphic to H_{f,q} and H_{f,p}′ is not isomorphic to H_{f,q}′ Proof. First of all, the group H_{f,p} has infinitely many conjugacy classes of elements of order p because there are symbols Δ whose columns have equal top and bottom row entries with m_{d}(Δ) = k for every k ∈ IN. On the other hand, it has only finitely many conjugacy classes of elements of order q, since such a conjugacy class is characterised by the numbers of fixed points and q-cycles both modulo p − 1. The same arguments goes through for the derived subgroups. This completes the proof.

Proof of Theorem A. Put Theorems 4.10, 4.14 and 6.14 together. The proof and thesis are complete.

Appendix A

Some Calculations

Here we present detailed calculations of relations used in the proof of Lemma 3.9. Since we are dealing with elements of G_{p,1} which all have 1-symbols we do not print the ones in the middle rows.

First we show how to obtain the relation ϵ = σ_{x_{j_{1}}}^{δ_{j_{1}}} ⋯ σ_{x_{jr}}^{δ_{jr}} δσ_{π} used in the first part of the proof of Lemma 3.9. We omit the columns

( \begin{matrix}a_{n}a_{j} \\ 1 \\ a_{n}a_{j} \end{matrix} ) and ( \begin{matrix}a_{i} \\ 1 \\ a_{i} \end{matrix} )

for 2 ≤ j ≤ n and 2 ≤ i ≤ n − 1 as they are not altered by the elements under consideration. In the following 1 ≤ i ≤ n.

\begin{matrix}a_{n}a_{1} & a_{1}a_{k_{1}π} & ⋯ & a_{1}a_{k_{t}π} & a_{1}a_{j_{1}π}a_{ix_{i_{j_{1}}}} & ⋯ & a_{1}a_{j_{r}π}a_{ix_{i_{jr}}} \\ & & & & & & & ↓ ϵ^{−1} \\ a_{1} & a_{n}a_{1}a_{k_{1}} & ⋯ & a_{n}a_{1}a_{k_{t}} & a_{n}a_{1}a_{j_{1}}a_{i} & ⋯ & a_{n}a_{1}a_{j_{r}}a_{i} \\ & & & & & & & ↓ σ_{x_{j_{1}}}^{δ_{j_{1}}} \\ a_{1} & a_{n}a_{1}a_{k_{1}} & ⋯ & a_{n}a_{1}a_{k_{t}} & a_{n}a_{1}a_{j_{1}}a_{x_{j_{1}}} & ⋯ & a_{n}a_{1}a_{j_{r}}a_{i} \\ ⋮ & ⋮ & & ⋮ & ⋮ & & ⋮ \\ & & & & & & & ↓ σ_{x_{jr}}^{δ_{jr}} \\ a_{1} & a_{n}a_{1}a_{k_{1}} & ⋯ & a_{n}a_{1}a_{k_{t}} & a_{n}a_{1}a_{j_{1}}a_{x_{j_{1}}} & ⋯ & a_{n}a_{1}a_{j_{r}}a_{ix_{jr}} \\ & & & & & & & ↓ δ \\ a_{n}a_{1} & a_{1}a_{k_{1}} & ⋯ & a_{1}a_{k_{t}} & a_{1}a_{j_{1}}a_{ix_{i_{j_{1}}}} & ⋯ & a_{1}a_{j_{r}}a_{ix_{i_{jr}}} \\ & & & & & & & ↓ σ_{π} \\ a_{n}a_{1} & a_{1}a_{k_{1}π} & ⋯ & a_{1}a_{k_{t}π} & a_{1}a_{j_{1}π}a_{ix_{i_{j_{1}}}} & ⋯ & a_{1}a_{j_{r}π}a_{ix_{i_{jr}}} \end{matrix} ) 1

Computing the relation αδ_{1}δσ_{π}δδ_{1}α^{−1}τ^{−1} = ϵ in the case m = p. Assume that a_{i}π = a_{1}, that is iπ = 1.

\begin{matrix}a_{1} & w_{2} & ⋯ & w_{i} & ⋯ & w_{p} & w_{p+1} & ⋯ & w_{s−1} & w_{s} \\ & & & & & & & & & & ↓ α \\ a_{1} & a_{p}a_{1}a_{2} & ⋯ & a_{p}a_{1}a_{i} & ⋯ & a_{p}a_{1}a_{p} & z_{p+1} & ⋯ & z_{s−1} & a_{p}a_{1}a_{1} \\ & & & & & & & & & & ↓ δ_{1} \\ a_{p}a_{1}a_{1} & a_{p}a_{1}a_{2} & ⋯ & a_{p}a_{1}a_{i} & ⋯ & a_{p}a_{1}a_{p} & z_{p+1} & ⋯ & z_{s−1} & a_{1} \\ & & & & & & & & & & ↓ δ \\ a_{1}a_{1} & a_{1}a_{2} & ⋯ & a_{1}a_{i} & ⋯ & a_{1}a_{p} & z_{p+1} & ⋯ & z_{s−1} & a_{p}a_{1} \\ & & & & & & & & & & ↓ σ_{π} \\ a_{1}(a_{1}π) & a_{1}(a_{2}π) & ⋯ & a_{1}a_{1} & ⋯ & a_{1}(a_{p}π) & z_{p+1} & ⋯ & z_{s−1} & a_{p}a_{1} \\ & & & & & & & & & & ↓ δ \\ a_{p}a_{1}(a_{1}π) & a_{p}a_{1}(a_{2}π) & ⋯ & a_{p}a_{1}a_{1} & ⋯ & a_{p}a_{1}(a_{p}π) & z_{p+1} & ⋯ & z_{s−1} & a_{1} \\ & & & & & & & & & & ↓ δ_{1} \\ a_{p}a_{1}(a_{1}π) & a_{p}a_{1}(a_{2}π) & ⋯ & a_{1} & ⋯ & a_{p}a_{1}(a_{p}π) & z_{p+1} & ⋯ & z_{s−1} & a_{p}a_{1}a_{1} \\ & & & & & & & & & & ↓ α^{−1} \\ w_{1π} & w_{2π} & ⋯ & a_{1} & ⋯ & w_{pπ} & w_{p+1} & ⋯ & w_{s−1} & w_{s} \\ & & & & & & & & & & ↓ τ^{−1} \\ a_{1}(a_{1}π) & a_{1}(a_{2}π) & ⋯ & a_{1}a_{1} & ⋯ & a_{1}(a_{p}π) & x_{p+1} & ⋯ & x_{s−1} & x_{s} \end{matrix} ) ϵ

Computing the relation τ′′η_{2} ⋯ η_{s−1} = ν_{s}β^{−1}.

z_{2} z_{3} ⋯ z_{s−1} z_{s} a_{1}a_{1} ⋯ a_{1}a_{p}

↓ τ′′

a_{1} w_{2} ⋯ w_{s−2} w_{s−1} w_{s} ⋯ w_{r}

↓ η_{2} ⋯ η_{s−1}

w_{2} w_{3} ⋯ w_{s−1} a_{1} w_{s} ⋯ w_{r}

↓ β

z_{2} z_{3} ⋯ z_{s−1} a_{1} z_{s}a_{1} ⋯ z_{s}a_{p}

↓ ν_{s}^{−1}

z_{2} z_{3} ⋯ z_{s−1} z_{s} a_{1}a_{1} ⋯ a_{1}a_{p}

Computing the relation ϵ′′ν_{s} ⋯ ν_{2}ϵ_{2} = ϵ.

\begin{matrix}a_{1} & w_{2} & ⋯ & w_{s−2} & w_{s−1} & w_{s} & ⋯ & w_{r} \\ & & & & & & & & ↓ ϵ′′ \\ z_{2} & z_{3} & ⋯ & z_{s−1} & z_{s} & a_{1}(a_{1}π) & ⋯ & a_{1}(a_{p}π) \\ & & & & & & & & ↓ ν_{s} \\ z_{2} & z_{3} & ⋯ & z_{s−1} & a_{1} & z_{s}(a_{1}π) & ⋯ & z_{s}(a_{p}π) \\ & & & & & & & & ↓ ν_{s−1} ⋯ ν_{2} \\ a_{1} & z_{2} & ⋯ & z_{s−2} & z_{s−1} & z_{s}(a_{1}π) & ⋯ & z_{s}(a_{p}π) \\ & & & & & & & & ↓ ϵ′ \\ v_{1} & v_{2} & ⋯ & v_{s−2} & v_{s−1} & v_{s}(a_{1}π) & ⋯ & v_{s}(a_{p}π) \end{matrix} ) ϵ

Computing the relation τ′β^{−1} = τ.

\begin{matrix}u_{1} & u_{2} & ⋯ & u_{s−1} & u_{s}a_{1} & ⋯ & u_{s}a_{p} \\ & & & & & & & ↓ τ′ \\ a_{1} & z_{2} & ⋯ & z_{s−1} & z_{s}a_{1} & ⋯ & z_{s}a_{p} \\ & & & & & & & ↓ β^{−1} \\ a_{1} & w_{2} & ⋯ & w_{s−1} & w_{s} & ⋯ & w_{r} \end{matrix} ) τ

Appendix B

Tree Diagrams of Generators

\begin{matrix}a = & ā = \\ â = & d = \end{matrix}

c =

b = \{ \begin{matrix}, r and n odd \\ , otherwise \end{matrix}

Appendix C

Tree Diagrams to Look at

σg =

δ =  δ_{i} =

m = 2n − 2 and k = m + t The top row of Γ and the basis corresponding to S.

Bibliography

[1] L. Bartholdi, A class of groups acting on rooted trees, preprint, 1999 [2] G. Baumslag, Combinatorial Group Theory, Lectures in Mathematics

ETH Zürich, Birkhäuser Verlag, 1993

[3] W. W. Boone, Certain simple unsolvable problems in group theory, I, II, III, IV, V, VI, Nederl. Akad. Wetensch Proc. Ser. A 57 (1954), 231–237, 492–497, 58 (1955), 252-256, 571-577, 60 (1957), 22-27, 227-232

[4] W. W. Boone and G. Higman, An algebraic characterization of groups with solvable word problem, J. Aust. Math. Soc. 18 (1974), 41–53

[5] M. G. Brin and C. C. Squier, Groups of piecewise linear homeomorphisms of the real line, Invent. Math. 79 (1985), 485–498

[6] K. S. Brown, Cohomology of Groups, Springer-Verlag, Berlin, 1982 [7] K. S. Brown, Finiteness properties of groups, J. Pure Appl. Algebra

44 (1987), 45–75

[8] K. S. Brown and R. Geoghegan, An infinite-dimensional torsionfree F P_{∞} group, Invent. Math. 77 (1984), 367–381

[9] M. Burger and S. Mozes, Finitely presented simple groups and products of trees, C. R. A. S. Paris 324.I (1997), 747–752

[10] J. W. Cannon, W. J. Floyd, and W. R. Perry, Introductory Notes on Richard Thompson’s group, Ens. Math. 42 (1996), 215–256

[11] C. Chou, Elementary amenable groups, Illinois J. Math. 24 (1980), 396–407

[12] M. Day, Amenable semigroups, Illinois J. Math. 1 (1957), 509–544 [13] P. Dehornoy, The Structure Group for the Associativity Identity, J.

Pure Appl. Alg. 111 (1996), 59–82

[14] W. Dicks and M. Dunwoody, Groups acting on graphs, Cambridge studies in advanced mathematics, Camb. Univ. Press, 1989 [15] J. Fabrykowski and N. Gupta, On groups with subexponential

growth functions, J. Indian Math Soc. 49 (1985), 249–256

[16] J. Fabrykowski and N. Gupta, On groups with subexponential growth functions ii, J. Indian Math Soc. 56 (1991), 217–228

[17] R. I. Grigorchuk, Degrees of growth of finitely generated groups and the theory of invariant means, Math. USSR Izv. 25 (1985)

[18] R. I. Grigorchuk, On the growth degrees of p-groups and torsion-free groups, Math. USSR Sb. 54 (1986), 185–205

[19] R. I. Grigorchuk, A finitely presented amenable group not in the class EG, Sbornik Math. 189 (1998), 75–95

[20] R. I. Grigorchuk, Just infinite branch groups, in New horizons in pro-p groups, M. du Sautoy, D. Segal, and A. Shalev, eds., Birkhäuser Verlag, Boston, 2000

[21] V. Guba and M. Sapir, Diagram Groups, Memoirs of the AMS 620 (1997)

[22] N. Gupta and S. Sidki, Some infinite p-groups, Algebra i Logika 22 (1983), 584–589

[23] G. Higman, Subgroups of finitely presented groups, Proc. Royal Soc. London Ser. A 262 (1961), 455–475

[24] G. Higman, Finitely Presented Infinite Simple Groups, Notes on Pure Mathematics 8, The Australian National University, 1974

[25] C. H. Houghton, The first cohomology of a group with permutation module coefficients, Arch. Math. (Basel) 31 (1978/79), 254–258

[26] M. Imbert, Sur l’isomorphisme du groupe de Richard Thompson avec le group de Ptolémée, in Geometric Galois Actions 2, L. Schneps and P. Lochak, eds., Camb. Univ. Press, 1997

[27] D. L. Johnson, Embedding some recursively presented groups, in Groups St. Andrews 1997 in Bath, Vol. II, Lectures Notes Series 261, London Math. Soc., 1998

[28] A. Karrass, W. Magnus, and D. Solitar, Combinatorial Group Theory, Dover Publications, Inc., New York, 1976

[29] A. V. Kuznetsov, Algorithms as operations in algebraic systems, Izv. Akad. Nauk SSSR Ser. Mat. (1958)

[30] D. R. Mason, On the 2-generation of certain finitely presented simple groups, J. London Math. Soc. (2) 16 (1977), 224–231 [31] C. F. Miller III, Decision Problems in Algebraic Classes of Groups

(A Survey), in Word Problems, W. W. Boone, F. B. Cannonito, and R. C. Lyndon, eds., North-Holland, Amsterdam, 1973

[32] P. S. Novikov, On the algorithmic unsolvability of the word problem in group theory, Trudy Mat. Inst. Steklov 44 (1955), 1–143

[33] D. J. S. Robinson, A Course in the Theory of Groups, Springer-Verlag, New York, Heidelberg, Berlin, 1993

[34] C. E. Röver, Wachstum von endlich erzeugten Gruppen, Diplomarbeit, Freiburg i. Br., 1997

[35] E. A. Scott, A construction which can be used to produce finitely presented simple groups, J. Algebra 90 (1984), 294–322

[36] E. A. Scott, The embedding of certain linear and abelian groups in finitely presented simple groups, J. Algebra 90 (1984), 323–332

[37] E. A. Scott, A finitely presented simple group with an unsolvable conjugacy problem, J. Algebra 90 (1984), 333–353

[38] E. A. Scott, A tour around finitely presented infinite simple groups, in Algorithms and Classification in Combinatorial Group Theory, G. Baumslag and C. F. Miller III, eds., Springer-Verlag, 1992

[39] M. Stein, Groups of piecewise linear homeomorphisms, Trans. Amer. Math. Soc. 332 (1992), 477–514

[40] R. J. Thompson, Embeddings into finitely generated simple groups which preserve the word problem, in Word Problems II, S. I. Adian, W. W. Boone, and G. Higman, eds., North-Holland, Amsterdam, 1980

[41] J. von Neumann, Zur allgemeinen Theorie des Maßes, Fund. Math. 13 (1929), 73–116

[42] J. Wiegold, Transitive groups with fixed-point free permutations II, Arch. Math. (Basel) 29 (1977), 571–573

Index

E-expansible, 30 F P S(Δ), 76 F_{n,r}, 18 IP S(Δ), 76 K-basis, 47 K-closure, 49 P S(Δ), 73 T_{n,r}, 18 Δ_{F}, 79 Δ_{I}, 79 G_{n,r}, 10 top(Δ)_{F}, 79 top(Δ)_{I}, 79 π_{g}(Δ), 72 G_{n,r}, 10 i(Δ), 82 i(O), 82 r(Δ), 82 E_{f,p}, 54 H_{f,p}, 54

basis, 10 normal, 70

column, 11

trivial, 11 conjugacy problem, 72

even element, 19 expansion of

inescapable basis, 7 pseudo-orbit, 73 symbol, 12

fake-E-expansible, 36

Grigorchuk group, 52

inescapable basis, 7 isomorphism, 9 subspace, 8

legal expansion, 84 locally finite, 22

middle row entries, 11

order problem, 62

pseudo-orbit, 72 characteristic of, 73 class of, 75 index of, 82 trace of, 73 type of, 81

row, bottom, 11 top, 11

set of type s, 33 simple expansion of

inescapable basis, 7 pseudo-orbit, 73 symbol, 12 step column, 65 symbol, 11 E-, 12 ⟨g⟩-E_{f,p}-, 66 ⟨g⟩-fake-E_{f,p}-, 66 fake-E, 36 flat, 66 index of, 82 legal, 81 normal, 76 rank of, 82

torsion locally finite, 47 tree, 15

finite rooted binary, 15 tree diagram, 16