The power conjugacy problem in Higman-Thompson groups

∗†

arXiv:1503.01032v2 [] 28 Dec 2015

Nathan Barker1 , Andrew J. Duncan2 , and David M. Robertson2
1

CMEP, Department for Pure Mathematics and Mathematical Statistics,
Cambridge University, CB3 OWB, UK
2
School of Mathematics and Statistics, Newcastle University, Newcastle upon Tyne,
NE1 7RU, UK
March 12, 2018

Abstract
An introduction to the universal algebra approach to Higman-Thompson groups (including
Thompson’s group V ) is given, following a series of lectures by Graham Higman in 1973. In
these talks, Higman outlined an algorithm for the conjugacy problem; which although essentially correct fails in certain cases, as we show here. A revised and complete version of the
algorithm is written out explicitly. From this, we construct an algorithm for the power conjugacy problem in these groups. Python implementations of these algorithms can be found
at [26].

1

Introduction

In 1965, Thompson introduced the group now called “Thompson’s group V ” and its subgroups
F < T . In doing so he gave the first examples (namely V and T ) of finitely presented, infinite simple
groups (see [11, 28]). McKenzie and Thompson [23] later used V to construct finitely presented
groups with unsolvable word problem. Subsequently, Galvin and Thompson (unpublished) identified
V with the automorphism group of an algebra V2,1 , studied by Jónsson and Tarski [18]. Higman
[17] generalised this construction, defining Gn,r as the automorphism group of a generalisation Vn,r
of V2,1 , for n ≥ 2 and r ≥ 1. Moreover, Higman showed that the commutator subgroup of Gn,r is
a finitely generated, infinite, simple group, for all n ≥ 2. (Gn,r is perfect when n is even, and its
commutator subgroup has index 2 when n is odd.)
The groups Gn,r are the “Higman-Thompson” groups of the title. There are many isomorphic
groups in this set: in fact the algebras Vn,r and Vn0 ,r0 are isomorphic if and only if n = n0 and
r ≡ r0 mod n − 1; so Gn,r ∼
= Gn0 ,r0 if n = n0 and r ≡ r0 mod n − 1. Higman [17] showed
that there are infinitely many non-isomorphic groups Gn,r and gave necessary conditions for such
groups to be isomorphic. Recently Pardo [24] completed the isomorphism classification, showing
∗ This

research was partially supported by the EPSRC Grant EP/K016687/1.
first and third authors were supported by EPSRC doctoral training grants. Parts of this paper appear in
the first author’s thesis.
† The

1

that Higman’s necessary conditions are also sufficient: that is Gn,r ∼
= Gn0 ,r0 if and only if n = n0
0
0
and gcd(n − 1, r) = gcd(n − 1, r ). Higman-Thompson groups have been much studied and further
generalised: we refer to [11, 8, 6, 22, 15, 10] for example.
In this paper we consider the conjugacy and power conjugacy problems in Higman-Thompson
groups. We use Higman’s method, describing the groups Gn,r in terms of universal algebra. This
allows us to give a detailed description of the algorithm for the conjugacy problem; and to uncover
a gap in the original algorithm proposed by Higman. To be precise, Lemma 9.6 of [17] is false,
and consequently the “orbit sharing” algorithm in [17] does not always detect elements in the same
orbit of an automorphism. The orbit sharing algorithm is crucial to the algorithm for conjugacy
given in [17], which may fail to recognise that a pair of elements of Gn,r are conjugate. Fortunately
it is not difficult to complete the algorithm. We then extend these results to construct an algorithm
for the power conjugacy problem: that is, given elements g, h in a group G decide whether or not
there exist non-zero integers a and b such that g a is conjugate to hb .
The power conjugacy problem though less well known than the conjugacy problem, already
occurs as one of the problems in the hierarchy of decision problems studied by Lipschutz and Miller
[20]. The problem has been shown to be decidable in, for example, certain HNN-extensions and
free products with cyclic amalgamation [1, 14], in certain one-relator groups [25], in Artin groups of
extra large type [5], in groups with small cancellation conditions C(3) and T(6) [4] and in free-bycyclic groups [7]. Cryptographic protocols based on the power conjugacy search problem have been
proposed, see for example [19], although these may be susceptible to attack by quantum computer
[16].
The third author has implemented the algorithms described in this paper in Python [26]. In
fact it was the process of testing this implementation which uncovered the existence of an orbit
unrecognised in [17]; and it became evident that the algorithms of [17] were incomplete.
Note that other approaches to algorithmic problems in Gn,r have been developed. For example
[27] proposes an algorithm for the conjugacy problem in G2,1 based on the the revealing tree pairs
of Brin [8]. In [6] the same methods are used to study the centralisers of elements of Gn,1 for
n ≥ 2. Again Belk and Matucci [3] gave a solution to the conjugacy problem in G2,1 based on
strand diagrams. In another direction, Higman’s methods were used by Brown [9] to show that all
the Higman-Thompson groups are of type F P∞ . This discussion of finiteness properties has been
extended to generalisations of Higman-Thompson groups, by Martinez-Perez and Nucinkis [22].
In detail the contents of the paper are as follows. In order to make this account self-contained, we
begin with an introduction to universal algebra. Section 2 outlines the universal algebra required,
following Cohn’s account [13]. In Section 2.1 we introduce Ω-algebras; that is universal algebras
with signature Ω. Sections 2.2 and 2.3 cover quotients of Ω-algebras, varieties of Ω-algebras and
free Ω-algebras. We use this machinery in Section 3 to define the algebras Vn,r and establish their
basic properties, following the exposition of [17].
The groups Gn,r are defined in Section 4 as the automorphism groups of Vn,r . We represent
elements of Gn,r as bijections between carefully chosen generating sets of the algebras Vn,r . This is
done in two stages, beginning with the semi-normal forms of Section 4.1. There are many ways of
representing a given automorphism in semi-normal form, but in Section 4.2 it is shown that this
representation may be refined to a unique quasi-normal form. Furthermore, an algorithm is given
which takes an automorphism and produces a quasi-normal form representation.
The solution to the conjugacy problem is based on an analysis of certain orbits of automorphisms
in quasi-normal form, and we give a full account of this analysis in Sections 4.1 and 4.2. Here we
follow [17] except that, as pointed out above, there exist orbits of types not recognised there, which

2

give automorphisms in quasi-normal form a richer structure, as described here.
Section 5 contains the algorithm for the conjugacy problem. This involves breaking an automorphism down into well-behaved parts. It is shown that every element of Gn,r decomposes into factors
which are called periodic and regular infinite parts. The conjugacy problem for periodic and regular
infinite components are solved separately and then the results recombined. The decomposition into
these parts is the subject of Section 5.1 and here we give the main algorithm for the conjugacy
problem, Algorithm 5.6. This algorithm depends on algorithms for periodic and regular infinite
automorphisms: namely Algorithm 5.13 in Section 5.3 and Algorithm 5.27 in Section 5.4.
In Section 6 we turn to the power conjugacy problem. In the version considered here the problem
is, given g, h ∈ Gn,r to find all pairs of non-zero integers (a, b) such that g a is conjugate to hb . Again
the problem splits into the periodic and regular infinite parts. The periodic part is straightforward,
and reduces to the conjugacy problem; see Section 6.1. The algorithm for power conjugacy of
regular infinite elements is Algorithm 6.13, in Section 6.3 and gives the main result of the paper
Theorem 6.14: that the power conjugacy problem is solvable. On input g, h ∈ Gn,r the algorithm
returns a (possibly empty) set S consisting of all pairs of integers (a, b) such that g a and hb are
conjugate; as well as a conjugator, for each pair.
In outline, the main steps of the algorithm for the (power-)conjugacy problem are:
• Lemma 4.28 which computes the quasi-normal basis of a given automorphism;
• Lemma 4.30, the ‘component-sharing test’, as in Higman’s original algorithm;
• Lemma 4.34, the ‘orbit-sharing test’, which recognises and combines components which belong
to a single orbit;
• Algorithm 5.6 which is Higman’s solution to the conjugacy problem; and
• Algorithm 6.13 which determines if two automorphisms are power conjugate.
The examples given throughout the text are used as examples in [26], from where these and
other examples may be run through the third author’s implementations of the algorithms. To find
Example x.y in [26], follow the instructions in the documentation to install the program; then run
>>> from thompson import *
>>> f = load example(’example x y’)
in a Python session. The automorphism will then be available as the Python object f.

Acknowledgements
The authors thank Collin Bleak, for suggesting work on conjugacy problems in Thompson’s group,
and Claas Röver, who suggested the use of Higman’s approach, and made many improvements to
earlier versions of this work. We thank Sarah Rees for overall guidance and constructive suggestions.
We thank Steve Pride for pointing us in the direction of the power conjugacy problem and Francesco
Matucci, José Burillo and Matt Brin for helpful conversations.

3

2
2.1

Universal Algebra
Ω-algebras

In this section we review enough universal algebra to underpin the construction of the HigmanThompson groups in later sections. We follow [13].
Definition 2.1. An operator domain consists of a set Ω and a mapping a : Ω → N0 . The
elements of Ω are called operators. If ω ∈ Ω, then a(ω) is called the arity of ω. We shall write
Ω(n) = {ω ∈ Ω | a(ω) = n}, and refer to the members of Ω(n) as n-ary operations.
An algebra with operator domain (or signature) Ω consists of a set S, called the carrier of the
algebra, and a family of maps {ϕω }ω∈Ω indexed by Ω, such that for ω ∈ Ω(n), ϕω is a map from
S n to S.
Following [13] we suppress all mention of the maps ϕω , identifying ϕω with ω, and referring to
any algebra with carrier S and operator domain Ω as an Ω-algebra, which we denote by (S, Ω). For
example, a group (G, ·,−1 , 1) is a Ω-algebra with operator domain {·,−1 , 1} and carrier G, where ·
is binary, −1 is unary and 1 is a constant. For this to describe a group, certain laws must hold
between these operations, i.e. the group axioms.
Given an Ω-algebra (S, Ω) and f ∈ Ω(n), we write s1 · · · sn f for the image of the n-tuple
(s1 , . . . , sn ) ∈ S n under f . We say that a subset T ⊆ S is closed under the operations of Ω (or that
T is Ω-closed ) if, for all n ≥ 0, for all f in Ω(n) and for all s1 , . . . , sn ∈ T the element s1 · · · sn f
is also an element of T . Indeed, if T is a subset of S then T is Ω-closed if and only if (T, Ω) is an
Ω-algebra: which brings us to the next definition.
Definition 2.2. Given an Ω-algebra (S, Ω), an Ω-subalgebra is an Ω-algebra (T, Ω) whose carrier
T is a subset of S.
The intersection of any family of subalgebras is again a subalgebra. Hence, for any subset X of
the set S we may define the subalgebra hXi generated by X to be the intersection of all subalgebras
containing X. The subalgebra hXi may also be defined recursively: that is hXi is the subset of S
such that (i) X ⊆ hXi, (ii) if y1 , . . . , yn ∈ hXi then y1 · · · yn f ∈ hXi, for all f ∈ Ω(n) and (iii) if s
does not satisfy (i) or (ii) then s does not belong to hXi. Loosely speaking we might say that hXi
is obtained from X by applying a finite sequence of operations of Ω. If the subalgebra generated
by X is the whole of S, then X is called a generating set for (S, Ω).
A mapping g : A → B between two Ω-algebras A = (S, Ω), B = (S 0 , Ω) is said to be compatible
with f ∈ Ω(n) if, for all s1 , . . . , sn ∈ S,
(s1 g) · · · (sn g)f = (s1 · · · sn f )g.
If g is compatible with each f ∈ Ω, it is called a homomorphism from A = (S, Ω) to B = (S 0 , Ω).
If a homomorphism g from A to B has an inverse g −1 which is again a homomorphism, g is called
an isomorphism and then the Ω-algebras A = (S, Ω), B = (S 0 , Ω) are said to be isomorphic. An
isomorphism of an algebra A = (S, Ω) with itself is called an automorphism and a homomorphism of
an algebra into itself is called an endomorphism. A homomorphism is determined once the images
of a generating set are fixed.
Proposition 2.3 ([13, Proposition 1.1]). Let g, h : A → B be two homomorphisms between Ωalgebras A = (S, Ω), B = (S 0 , Ω). If g and h agree on a generating set for A, then they are equal.
4

Qm
From a family {Ai }m
i=1 (Ai = (Si , Ω)) of Ω-algebras we can form the direct product P =
i=1 Ai
of Ω-algebras. Its set is the Cartesian product S of the Si , and the operations are carried out
component wise. Thus, if πi : S → Si are the projections from the product to the factors then any
f ∈ Ω of arity n is defined on S n by the equation
(p1 · · · pn f )πi = (p1 πi ) · · · (pn πi )f,
where pi ∈ S.
Let C be a class of Ω-algebras, whose elements we will call C-algebras. By a free C-algebra on a
set X we mean a C-algebra F with the following universal property.
There is a mapping µ : X → F such that every mapping f : X → A into a C-algebra A
can be factored uniquely by µ to give a homomorphism from F to A, i.e. there exists
a unique homomorphism f 0 : F → A such that µf 0 = f .
In this case we say that X is a free generating set or a basis for F . If X is a subset of F then
we shall always assume that µ is the inclusion map. Not every class has free algebras, but they do
exist in the class under consideration here (see Proposition 2.16).
A free product is defined similarly, replacing the set X by a collection of C algebras. Given an
indexing set I and for each i ∈ I an Ω algebra Ai from C the free product A of {Ai }i∈I , written
A = ∗i∈I Ai , is an Ω-algebra in C satisfying the following property.
There exist homomorphisms µi : Ai → A, for all i ∈ I, such that for any Ω-algebra B
and homomorphisms fi : Ai → B, for all i ∈ I, there exists a unique homomorphism
f 0 : A → B such that µi f 0 = fi , for all i.
Given collections {Ai }i∈I and {Bi }i∈I of Ω-algebras such that there exist free products A = ∗i∈I Ai
and B = ∗i∈I Bi , then, by definition, there exist homomorphisms µi : Ai → A and µ0i : Bi → B,
for all i ∈ I. In this case, given homomorphisms fi : Ai → Bi , for all i ∈ I, the composition
fi µ0i is a homomorphism from Ai to B, so there exists a unique homomorphism f 0 : A → B, with
µi f 0 = fi µ0i , for all i ∈ I. We denote f 0 by ∗i∈I fi .

2.2

Congruence on an Ω-algebra

A relation between two sets S and R is defined to be a subset of the Cartesian product S × R.
A mapping f : S → R is a relation Γf ⊂ S × R with the properties that for each s ∈ S there
exists r ∈ R such that (s, r) ∈ Γf (everywhere defined) and if (s, r), (s, r0 ) ∈ Γf then r = r0 (single
valued). A relation Γ ⊂ S × R has an inverse Γ−1 , defined by
Γ−1 = {(r, s) ∈ R × S | (s, r) ∈ Γ};
and if ∆ ⊂ R × T is a relation then the composition Γ ◦ ∆ of Γ and ∆ is defined by
Γ ◦ ∆ = {(s, t) ∈ S × T | (s, x) ∈ Γ and (x, t) ∈ ∆ for some x ∈ R}.
If Γ ⊂ S × R and S 0 ⊂ S we define
S 0 Γ = {r ∈ R | (s, r) ∈ Γ for some s ∈ S 0 }.

5

Given a set S the identity relation 1S = {(s, s) | s ∈ S} and the universal relation S 2 = {(s, s0 ) |
s, s0 ∈ S} always exist.
An equivalence on a set S is a subset Γ of S 2 with the properties Γ◦Γ ⊂ Γ (transitivity): Γ−1 = Γ
(symmetry) and 1S ⊆ Γ (reflexivity). The equivalence class of s ∈ S is {s0 ∈ S | (s, s0 ) ∈ Γ} = {s}Γ.
Given any subset U of S × S, the equivalence generated by U is
\
E = {V ⊆ S × S | V is an equivalence and U ⊆ V };
that is, the smallest equivalence E on S containing U . It follows that E is
{(a, b) ∈ S × S | there exists a0 , . . . , an such that a0 = a, an = b and (ai , ai+1 ) ∈ U }.
Of particular interest in the study of Ω-algebras are relations which are also subalgebras. Firstly,
if A = (S, Ω) and B = (R, Ω) are Ω-algebras and Γ ⊂ S × R is a relation which is closed under the
operations of Ω, as defined in A × B, then (Γ, Ω) is a subalgebra of A × B. In this case we abuse
notation and say Γ is a subalgebra of A × B.
Lemma 2.4 ([13, Lemma 2.1, Chapter 1]). Let A, B, C be Ω-algebras and let Γ, ∆ be subalgebras
of A × B, B × C respectively. Then Γ−1 is a subalgebra of B × A, Γ ◦ ∆ is a subalgebra of A × C and
if A0 is a subalgebra of A, with carrier S 0 ⊆ S, then (S 0 Γ, Ω) is a subalgebra of B.
Let S and T be sets and f : S → T a mapping between them. The image of f is defined as
SΓf , and the kernel of f is defined as
ker f = {(x, y) ∈ S 2 | xf = yf }.
The latter is an equivalence on S; the equivalence classes are the inverse images of elements in the
image (sometimes called the fibres of f ).
Example 2.5 (Groups). Given a group homomorphism f : G → H, the (group-theoretic) kernel of
f is a normal subgroup N ; and the different cosets of N in G are the fibres of f . So, the equivalence
classes of kerf , in the definition above, are the cosets of N in G.
A congruence on an Ω-algebra A = (S, Ω) is an equivalence on S which is also a subalgebra of
A2 i.e. an equivalence Γ ⊂ S × S which is Ω-closed. From the above, 1A and A2 are congruences
on A. Given any subset U ⊆ S × S the congruence generated by U is
\
C = {V ⊆ S × S | V is a congruence and U ⊆ V }.
It follows that C is the smallest congruence on A containing U .
Let A be an Ω-algebra. By definition a congruence is an equivalence which admits the operations
ω (ω ∈ Ω). Now each n-ary operator ω defines an n-ary operation on A:
(a1 , . . . , an ) 7→ a1 · · · an ω for a1 , . . . , an ∈ A.

(1)

By giving fixed values in A to some of the arguments, we obtain r-ary operations for r ≤ n. In
particular, if we fix all the aj except one, say the ith, we obtain, for any n − 1 fixed elements
a1 , . . . , an−1 ∈ A, a unary operation
x 7→ a1 · · · ai−1 xai · · · an−1 ω;
6

(2)

and this applies for all i ∈ {1, . . . , n}. We say that the operation (2) is an elementary translation
(derived from Ω by specialisation in A). Given a finite sequence τ1 , . . . , τn of elementary transformations the composition τ = τ1 ◦ · · · ◦ τn is also a unary operation on A, which we call a translation.
(In particular we allow n = 0 in this definition, so the identity map on A is a translation.)
Proposition 2.6 ([12, Proposition 6.1, Chapter6]). An equivalence q on an Ω-algebra A is a
congruence if and only if it is closed under all translations. More precisely, a congruence is closed
under all translations, while any equivalence which is closed under all elementary translations is a
congruence.
Remark 2.7. If U ⊆ S × S, then the congruence generated by U can be seen to consist of pairs
(a, b) ∈ S × S such that there exist m ≥ 0, a0 , . . . , am ∈ S, and a translation τ with
• a0 = a, am = b and
• (ai , ai+1 ) = (ui τ, ui+1 τ )
where either (ui , ui+1 ) ∈ U , (ui+1 , ui ) ∈ U or ui = ui+1 . That is, there exist s1 , . . . , sn−1 ∈ S,
u0 , . . . , um ∈ S, and ω ∈ Ω(n) such that (ui , ui+1 ) ∈ U ∪ U −1 ∪ 1S and setting
ai = (s1 , . . . , sj−1 , ui , sj , . . . , sn−1 )ω,
for 0 ≤ i ≤ m, we have a = a0 and b = am .
The next two theorems explain the significance of congruences for Ω-algebras and will be used
in the following section on free algebras and varieties.
Theorem 2.8 ([13, Theorem 2.2, Chapter 1]). Let g : A → B be a homomorphism of Ω-algebras.
Then the image of g is a subalgebra of B and the kernel of g is a congruence on A.
Theorem 2.9 ([13, Theorem 2.3, Chapter 1]). Let A be an Ω-algebra and q a congruence on A.
Then, there exists a unique Ω-algebra, denoted A/q, with carrier the set of all q-classes such that
the natural mapping ν : A → A/q is a homomorphism.
The homomorphism ν in the previous theorem, which maps an element s of the carrier of A
to its q-equivalence class, is called the natural homomorphism from A to A/q. The algebra A/q is
called the quotient algebra of A by q.
Example 2.10. Given a group G and a normal subgroup N of G, the natural mapping G → G/N
is a homomorphism.

2.3

Free algebras and varieties

Let X = {x1 , x2 , . . .} be a non-empty, finite or countably enumerable set, called an alphabet, and
Ω an operator domain, with Ω ∩ X = ∅. We define an Ω-algebra as follows. An Ω-row in X is a
finite sequence of elements of Ω ∪ X. The set of all Ω-rows in X is denoted W (Ω; X). The length
of the Ω-row w = w1 · · · wm (where wi ∈ Ω ∪ X) is defined to be m and is written |w|. The carrier
of our Ω-algebra is W (Ω; X), the set of Ω-rows.
We define the action of elements Ω on W (Ω; X) by concatenation. First observe that if u and v
are Ω-rows then the concatenation uv of u with v is also an Ω-row, and this may be extended to
the concatenation of arbitrarily many Ω-rows in the obvious way. For f ∈ Ω(n) and u1 , . . . , un ∈
7

W (Ω; X), we define the the image of the n-tuple (u1 , . . . , un ) ∈ W (Ω, X)n under the operation f
to be the Ω-row u1 · · · un f . By abuse of notation we will refer to W (Ω; X) as an Ω-algebra.
The alphabet X ⊂ W (Ω; X) and we call the subalgebra generated by X the Ω-word algebra on
X, denoted WΩ (X). Its elements are called Ω-words in the alphabet X. There is a clear distinction
between Ω-rows that are Ω-words and those that are not. For example, if f is a binary operation
then
x1 x2 x3 f x4 f f = (x1 , ((x2 , x3 )f, x4 )f )f
is a Ω-row which is also an Ω-word, whereas x1 f f x2 f x3 is an Ω-row which is not an Ω-word.
DefinitionP2.11 ([13, Chapter 1]). We define the valency of an Ω-row w = w1 · · · wm (wi ∈ Ω ∪ X)
m
as v(w) = i=1 v(wi ) where
(
1,
if wi ∈ X,
v(wi ) =
1 − arity(wi ), if wi ∈ Ω.
Proposition 2.12 ([13, Proposition 3.1, Chapter 1]). An Ω-row w = w1 · · · wm in W (Ω; X) is an
Ω-word if and only if every left-hand factor ui = w1 · · · wi of w satisfies
v(ui ) > 0 for i = 1, . . . , m

and

v(w) = 1.

Moreover, each Ω-word can be obtained in precisely one way by applying a finite sequence of operations of Ω to elements of X.
Let A be an Ω-algebra. If in an element w of WΩ (X) we replace each element of X by an
element of A we obtain a unique element of A. For |w| = 1, this is clear, so assume |w| > 1 and we
will use induction on the length of w. We have w = u1 · · · un f (f ∈ Ω(n), ui ∈ WΩ (X)), where, by
Proposition 2.12, the ui are uniquely determined once w is given. By induction each ui becomes
a unique element ai ∈ A, when we replace the elements of X by elements of A. Hence w becomes
a1 · · · an f ; a uniquely determined element of A.
This establishes the next theorem.
Theorem 2.13 ([13, Theorem 3.2, Chapter 1]). Let A be an Ω-algebra and let X be a set. Then
any injective mapping θ : X → A extends, in just one way, to a homomorphism θ̄ : WΩ (X) → A.
That is, WΩ (X) is a free Ω-algebra, freely generated by X.
Corollary 2.14 ([13, Corollary 3.3, Chapter 1]). Any Ω-algebra A can be expressed as a homomorphic image of an Ω-word algebra WΩ (X) for a suitable set X. Here X can be taken to be any
set mapping onto a generating set of A.
By an identity or law over Ω in X we mean a pair (u, v) ∈ WΩ (X) × WΩ (X) or an equation
u = v formed from such a pair. We say that the law (u, v) holds in the Ω-algebra A or that A
satisfies the equation u = v if every homomorphism WΩ (X) → A maps u and v to the same element
of A. This correspondence between sets of laws and classes of algebras establishes a pair of maps,
with the following definitions.
• Given a set Σ of laws over Ω in X, form VΩ (Σ), the class of all Ω-algebras satisfying all the
laws in Σ. This class VΩ (Σ) is called the variety generated by Σ.
• Given a class C of Ω-algebras we can form the set q = q(C) of all laws over Ω in X which hold
in all algebras of C.
8

Thus we have a pair of maps VΩ and q; relating each variety of Ω-algebras to a relation q on WΩ (X)
and vice-versa. We shall see below that q(C) is a congruence, but first we make a further definition.
A subalgebra of an Ω-algebra A is called fully invariant if it is mapped into itself by all endomorphisms of A. A congruence Γ on A is said to be fully invariant if (u, v) ∈ Γ implies (uθ, vθ) ∈ Γ,
for all endomorphisms θ of A. The fully invariant congruence generated by Γ is
\
I = {V | V is a fully invariant congruence and Γ ⊆ V }.
It follows that I is the smallest invariant congruence on A generated by Γ.
We claim that if C is a class of Ω-algebras then q(C) is a fully invariant congruence on WΩ (X).
To see that q(C) is a congruence, note that in in every class C of Ω-algebras we have the following:
u = u for all u ∈ WΩ (X); if u = v holds then so does v = u; and if u = v and v = w then
also u = w. Further, if ui = vi for i = 1, . . . , n are laws holding in A and if ω ∈ Ω(n), then
u1 · · · un ω = v1 · · · vn ω holds in A. Hence q(C) is indeed a congruence.
To see that q(C) is a fully invariant congruence, let (u, v) ∈ q(C) and let θ be any endomorphism
of WΩ (X). If A ∈ C and α : WΩ (X) → A is any homomorphism, then so is θα, hence uθα = vθα.
Thus the law uθ = vθ holds in A, so (uθ, vθ) ∈ q(C) and thus q(C) is a fully invariant congruence.
Cohn shows in addition that the map VΩ is a bijection with inverse q, and deduces the following
theorem.
Given sets S and T and a relation Γ from S to T , we may use Γ to define a system of subsets
of S, T , as follows. For any subset X of S we define a subset X ∗ of T by
X ∗ = {y ∈ T | (x, y) ∈ Γ for all x ∈ X} = ∩x∈X {x}Γ,
and similarly, for any subset Y of T we define a subset Y ∗ of S by
Y ∗ = {x ∈ S | (x, y) ∈ Γ for all y ∈ Y } = ∩y∈Y {y}Γ−1 .
We thus have mappings X 7→ X ∗ and Y 7→ Y ∗ of the power sets of S and T with the following
properties:
X1 ⊆ X2 ⇒ X1∗ ⊇ X2∗
X⊆X
X

∗∗∗

∗∗

=X

∗

Y1 ⊆ Y2 ⇒ Y1∗ ⊇ Y2∗

(3)

Y ⊆ Y ∗∗ ,

(4)

Y

∗∗∗

∗

=Y .

(5)

A pair of maps X 7→ X ∗ , from the power set 2S of S to the power set 2T of T , and Y 7→ Y ∗ , from
2T to 2S , satisfying (3–5) is called a Galois connection.
Theorem 2.15 ([13, Theorem 3.5, Chapter 1]). Let W = WΩ (X) be the Ω-word algebra on the
alphabet X. The pair of maps Σ 7→ VΩ (Σ) and C 7→ q(C) forms a Galois connection giving a
bijection between varieties of Ω-algebras and fully invariant congruences q on WΩ (X).
Proposition 2.16 ([13, Proposition 3.6, Chapter 1]). Let V be a variety of Ω-algebras and q the
congruence on WΩ (X) (the Ω-word algebra generated by X) consisting of all the laws on V i.e. the
fully invariant congruence q(V). Then WΩ (X)/q is the free V-algebra on X.
Suppose Σ is a set of laws over Ω in X and let V = VΩ (Σ) and q = q(V). Then Σ ⊆ q and, from
Proposition 2.16, q is a fully invariant congruence and WΩ (X)/q is the free V-algebra.
9

Now let p be the fully invariant congruence generated by Σ. Then, as Σ ⊆ q and q is a fully
invariant congruence, we have p ⊆ q. Let A = WΩ (X)/p. Then A is an Ω-algebra, in which every
law of Σ holds (as Σ ⊆ p). Thus A is a V-algebra. Then, from Proposition 2.16, the natural map
X → A extends to a homomorphism WΩ (X)/q → A. It follows that q ⊆ p. Therefore p = q = q(V).
We record this as a corollary which we shall use in Section 3 to construct Higman’s algebras Vn,r .
Corollary 2.17. Let Σ be a set of laws over Ω in X, let V = VΩ (Σ) and q = q(V). Then q is the
fully invariant congruence generated by Σ.

3

The Higman Algebras Vn,r

In this section we define the algebras which Higman called Vn,r . Let n ≥ 2 be an integer and let
A be an Ω-algebra, with carrier S and operator domain Ω = {λ, α1 , . . . , αn }, such that a(αi ) = 1,
for i = 1, . . . , n and a(λ) = n. We call the n-ary operation λ : S n → S a contraction and the unary
operations αi : S → S descending operations. We define a map α : S → S n , which we shall call an
expansion, by
vα = (vα1 , . . . , vαn ),
for all v ∈ S. For any subset Y of S, a simple expansion of Y consists of substituting some element
y of Y by the n elements of the tuple yα. A sequence of d simple expansions of Y is called a d-fold
expansion of Y . A set obtained from Y by a d-fold expansion, d ≥ 0, is called an expansion of Y .
For example, if x ∈ S then {xα1 , . . . , xαn } is the unique simple expansion of {x} and the 2-fold
expansions of {x} are the sets {xα1 , . . . , xαi−1 , xαi α1 , . . . , xαi αn , xαi+1 , . . . , xαn }, for 1 ≤ i ≤ n.
Every d-fold expansion of Y has |Y | + (n − 1)d elements. Similarly, a simple contraction of Y
consists of substituting n distinct elements {y1 , . . . , yn } ∈ Y by the single element (y1 , . . . , yn )λ. A
set obtained from Y by applying a finite number of simple contractions is called a contraction of
Y.
From now on in this paper, Ω is fixed as above. Let x be a non-empty set and recall that the
Ω-word algebra WΩ (x) is the free Ω-algebra on x.
Definition 3.1. Let Σn be the set of laws over Ω in x:
1. for all w ∈ WΩ (x),
wαλ = w,
(or explicitly wα1 · · · wαn λ = w).
2. for all (w1 , . . . , wn ) ∈ WΩ (x)n and i ∈ {1, . . . , n},
w1 · · · wn λαi = wi .
That is,
Σn = {(wα1 · · · wαn λ, w) | w ∈ WΩ (x)}
n
[
∪
{(w1 · · · wn λαi , wi ) | wi ∈ WΩ (x)}.
i=1

Let Vn = VΩ (Σn ) the variety of Ω-algebras which satisfy Σn and let q = q(Vn ).
10

From Proposition 2.16 and Corollary 2.17, it follows that q is the fully invariant congruence on
WΩ (x) generated by Σn and WΩ (x)/q is the free Vn -algebra on x.
Definition 3.2. Let x be a non-empty, finite or countably enumerable set of cardinality r and
n ≥ 2 an integer. Then Vn,r (x) is the free Vn -algebra WΩ (x)/q, where q = q(Vn ) and Vn = VΩ (Σn ).
When no ambiguity arises we refer to Vn,r (x) as Vn,r .
Remark 3.3. In [17, Section 2] Higman defines a standard form over x to be one of the finite
sequences of elements of x ∪ {α1 , . . . , αn , λ} specified by the following rules.
(i) xαi1 · · · αik is a standard form whenever k ≥ 0, x ∈ x and 1 ≤ ij ≤ n for j = 1, . . . , k.
(ii) If w1 , . . . , wn are standard forms then so is w1 · · · wn λ, unless there is a standard form u such
that wi = uαi for i = 1, . . . , n.
(iii) No sequence is a standard form unless this follows from (i) and (ii).
We define the descending operations α1 , . . . , αn by the rules
(xαi1 · · · αik )αi = xαi1 · · · αik αi ,
(w1 · · · wn λ)αi = wi
for i ∈ {1, . . . , n}. The contraction operation λ is defined by
(w1 , . . . , wn )λ = w1 · · · wn λ,
unless there is a standard form u such that wi = uαi for i = 1, . . . , n in which case
(w1 , . . . , wn )λ = (uα1 , . . . , uαn )λ = u.
These operations turn the set of standard forms into an Ω-algebra. Higman then goes on to prove
that this is a free Vn -algebra, freely generated by x ([17, Lemma 2.1]). This follows in our case
from the definition above, and the remarks following it, together with Lemma 3.4 below.
Lemma 3.4. Let U be an equivalence class of the congruence q on WΩ (x). Then there exists a
unique minimal length element u in U . The unique minimal length elements of equivalence classes
are precisely the standard forms of Higman.
To prove Lemma 3.4, one can use a standard argument which proves a statement of this form
in an algebra of an appropriate type. Details may be found in [2, Lemma 2.4.5].
Let y be the minimal length representative of its equivalence class in Vn,r i.e. let y be a standard
form. Then the length of the equivalence class of y is the length of y, denoted |y|, and the λ-length
of the equivalence class of y is the number of times the symbol λ occurs in y.
Now that we have a concrete description of the free algebra Vn,r in the variety Vn , we recall
those results of [17, Section 2], required in the sequel.
Lemma 3.5 (cf. [17, Lemma 2.3]). Let B be a basis of Vn,r (x).
1. Every expansion of B is a basis of Vn,r (x).
2. Every contraction of B is a basis of Vn,r (x).
11

Proof.
1. Let Y be a d-fold expansion of B, where d ≥ 0. Arguing by induction, we assume that
every d-fold expansion of B is a basis of Vn,r and show that any simple expansion of Y is also
a basis. Let y ∈ Y and let Y 0 be the simple expansion
Y 0 = (Y \ {y}) ∪ {yα1 , . . . , yαn }.
Since y = yα1 · · · yαn λ, the set Y 0 generates Vn,r . It remains to show that Y 0 is a basis for
Vn,r .
Given A ∈ Vn and a map θ : Y 0 → A, we shall show that there is a unique homomorphism
θ̄ : Vn,r → A extending θ. Firstly, define θ∗ from Y to A by y 0 θ∗ = y 0 θ, for y 0 ∈ Y \ {y}, and
yθ∗ = yα1 θ · · · yαn θλ. As Y is a basis, there is a unique homomorphism θ̄∗ from Vn,r to A
extending θ∗ . Now
(yαi )θ̄∗ = (y θ̄∗ )αi = (yθ∗ )αi = (yα1 θ · · · yαn θλ)αi = yαi θ.
Hence θ̄∗ also extends θ. Furthermore, any other homomorphism which extends θ must equal
θ̄∗ , since any such map must be defined on Y in the same way as θ∗ .
2. This is proved in the same way as 1.
The final statement of Corollary 3.13 forms a partial converse to this lemma, for finite bases.
Mostly we work with bases for Vn,r (x) which are expansions of x, so we make the following definition.
Definition 3.6. Let A = {α1 , . . . , αn } ⊂ Ω. An A-basis of Vn,r (x) is an expansion of x.
If A = (S, Ω) is an Ω-algebra with carrier S then we may form the A-algebra (S, A) and the
{λ}-algebra (S, {λ}), where the elements of A and {λ} have actions inherited from A. We call
these, respectively, the A-algebra and {λ}-algebra of A. A subset U of Vn,r is said to be A-closed
if uαi ∈ U , for all αi ∈ A, and an A-closed subset is called an A-subalgebra of (the A-algebra of)
Vn,r . Similarly W ⊆ Vn,r is called a {λ}-subalgebra (of the {λ}-algebra of Vn,r ) if it is {λ}-closed :
that is if wλ ∈ W , for all w ∈ W .
Definition 3.7. Let Y be a subset of Vn,r . The A-subalgebra generated by Y is denoted Y hAi.
The {λ}-subalgebra generated by Y is denoted Y hλi.
The free monoid on a set L is denoted L∗ . If Y is a subset of Vn,r (x) then Y A∗ = {yΓ | y ∈
Y, Γ ∈ A∗ } is A-closed, and it follows that Y hAi = Y A∗ . If in addition Y ⊆ xhAi, then yΓ is a
standard form for all y ∈ Y and Γ ∈ A∗ . In the sequel we write Y hAihλi for (Y hAi)hλi.
Lemma 3.8. Let B be an A-basis and Y a finite basis for Vn,r (X). If B ⊆ Y hAi then B is an
expansion of Y .
Proof. Since Y is finite, there exists an expansion of Y contained in BhAi. Let d be minimal such
that there is a d-fold expansion of Y contained in BhAi, and let W be such a d-fold expansion.
Each w ∈ W is of the form w = bΓ, for some b ∈ B and Γ ∈ A∗ . As B ⊆ Y hAi we have b = y∆, for
some y ∈ Y and ∆ ∈ A∗ ; so w = y∆Γ. Also, as w ∈ W , there exists y 0 ∈ Y such that w = y 0 Γ0 , as
part of an expansion of Y . As Y is a basis it follows that y = y 0 and ∆Γ = Γ0 .
Suppose that Γ 6= 1, so that Γ = Γ0 αj , for some αj ∈ A and Γ0 ∈ A∗ . As W is an expansion of
Y it follows that y∆Γ0 αi ∈ W , for all i ∈ {1, . . . , n}. Furthermore y∆Γ0 ∈ BhAi, so the union
W 0 = (W \ {y∆Γ0 αi | 1 ≤ i ≤ n}) ∪ {y∆Γ0 }
12

is contained in BhAi. Now W 0 is a simple contraction of W , so W 0 is a basis by Lemma 3.5. But W 0
is a (d − 1)-fold expansion of Y , which contradicts the minimality of d. So Γ = 1 and w ∈ B, and
hence W ⊆ B.
Conversely, if b ∈ B then b = yΓ, for some y ∈ Y and Γ ∈ A∗ . So either b∆ = yΓ∆ ∈ W for
some ∆ ∈ A∗ , or yΓ0 = w ∈ W , where Γ = Γ0 Γ1 . In the first case, b∆ = w ∈ B implies w = b and
∆ = 1. In the second case, b = yΓ = yΓ1 Γ0 = wΓ0 , with w ∈ B, so again w = b and Γ0 = 1. Thus
B ⊆ W.
A word Γ ∈ A∗ is called primitive if it is not a proper power of another word. Explicitly, this
means that if Γ is non-trivial and Γ ∈ {∆}∗ , for some ∆ ∈ A∗ , then Γ = ∆.
Proposition 3.9 ([21], Proposition 1.3.1, Chapter 1). If Γn = ∆m with Γ, ∆ ∈ A∗ and n, m ≥ 0,
there exists a word Λ such that Γ, ∆ ∈ {Λ}∗ . In particular, for each word Γ ∈ A∗ , there exists a
unique primitive word Λ such that Γ ∈ {Λ}∗ .
Proposition 3.10 ([21], Proposition 1.3.2, Chapter 1). Two words Γ, ∆ ∈ A∗ commute if and
only if they are powers of the same word. More precisely, the set of words commuting with a word
Γ ∈ A∗ is a monoid generated by a single primitive word.
Lemma 3.11 ([17, Section 2, Lemma 2.2]). Let Y be a subset of Vn,r and let W be the Ω-subalgebra
of Vn,r generated by Y . Then
1. W = Y hAihλi and
2. for all w ∈ W , the set whAi \ Y hAi is finite.
Proof.
1. Let w ∈ W . Then there exists a finite subset Y0 of Y such that w belongs to the
Ω-subalgebra W0 of Vn,r generated by Y0 . Let Z be an expansion of x such that |Z| ≥ |Y0 |.
Choose a surjection β of Z onto Y0 . As Vn,r is freely generated by Z we may extend β to a
homomorphism from Vn,r to W0 . Let w0 be the preimage of w under this homomorphism and
let l be the λ-length of the standard form of w0 over Z. By a straightforward induction on l it is
apparent that w0 ∈ ZhAihλi. Hence the image w of w0 in W0 belongs to Y0 hAihλi ⊆ Y hAihλi,
as required.
2. As in the previous part of the proof, we may assume that W is freely generated by Y . Let
w ∈ W and let l be the λ-length of the standard form of w over Y . Then wαi1 · · · αir ∈ Y hAi,
whenever r ≥ l. Hence, the only elements of the set difference whAi \ Y hAi are those of the
form wαi1 · · · αir with r < l, and there are only finitely many of these since we only have n
choices for each αij .
Lemma 3.12 ([17, Section 2, Lemma 2.4]). Let x be a set of size r ≥ 1 and let X ⊆ Vn,r (x) be an
expansion of x. If U is a subset of Vn,r (x) contained in XhAi, then the following are equivalent:
1. U = XhAi ∩ Y hAi, for some generating set Y of Vn,r ,
2. U is A-closed and XhAi \ U is finite,
3. U = ZhAi for some expansion Z of X.
Moreover, if Y in statement 1 is a finite basis for Vn,r (x) then Z in statement 3 is an expansion of
Y.
13

Proof. Firstly, let U = XhAi ∩ Y hAi. Since U is the intersection of A-closed sets, it is also A-closed.
By Lemma 3.11, XhAi \ Y hAi is finite and therefore XhAi \ U is finite. So 1 implies 2.
Secondly, assume that U is A-closed and XhAi \ U is finite. We will prove statement 3 by
induction on the size of |XhAi \ U |. If |XhAi \ U | = 0, then statement 3 holds with Z = X.
Otherwise, |XhAi \ U | > 0 and we choose an element w ∈ XhAi \ U whose length |w| is maximal.
Then the set U ∗ = U ∪ {w} is A-closed and |XhAi \ U ∗ | = |XhAi \ U | − 1.
By induction, there is an expansion Z ∗ of X such that U ∗ = Z ∗ hAi. The element w belongs
to Z ∗ , otherwise w would have the form w = zαi1 · · · αit , where z ∈ Z ∗ and t > 0, and hence
z ∈ U ∗ \ {w} = U . However, U is A-closed and so this would imply that w ∈ U , a contradiction.
If we take
Z = (Z ∗ \ {w}) ∪ {wαi | 1 ≤ i ≤ n},
then this is again an expansion of X and by the choice of w we have wαi ∈ U , for all i. Therefore
U = ZhAi and 2 implies 3.
For the last implication: if U = ZhAi for some expansion Z of X, then U = XhAi ∩ Y hAi, with
Y = Z, and so 3 implies 1.
Finally, let U = XhAi ∩ Y hAi as in statement 1, so that U = ZhAi by statement 3. In particular
this means that Z ⊆ Y hAi. As Z is an expansion of X, it is also an expansion of x; then Lemma 3.8
tells us that Z is a basis of Vn,r (x). Now suppose that Y is a basis. Since Y is finite, we can apply
Lemma 3.8 to see that Z is an expansion of Y .
Corollary 3.13 (cf. [17, Corollary 1, page 12]). Let B and C be finite bases of Vn,r (x). Then
B and C have a common expansion Z, which may be chosen such that ZhAi = BhAi ∩ ChAi.
In particular, every finite basis of Vn,r (x) may be obtained from x by an expansion followed by a
contraction.
Proof. Let f be the homomorphism from Vn,r (x) to Vn,|B| (B) defined by mapping b ∈ B ⊆ Vn,r (x)
to b ∈ Vn,|B| (B), for all b ∈ B. As this is a bijection between bases, f is an isomorphism. Let
C 0 = Cf , so C 0 is a basis for Vn,|B| (B). From Lemma 3.12, B and C 0 have a common expansion
Z 0 such that BhAi ∩ C 0 hAi = Z 0 hAi. Then B and C have common expansion Z = Z 0 f −1 , and the
remainder of the first statement of the lemma follows. The final statement follows on taking B to
be an arbitrary finite free generating set and C = x.
Corollary 3.14 ([17, Corollary 2, page 12]). Vn,r ∼
= Vn,s if and only if r ≡ s mod n − 1.
Proof. If r ≡ s mod n − 1 then it follows from Lemma 3.5 that Vn,r ∼
= Vn,s . Conversely, let θ be an
isomorphism from Vn,r (X) to Vn,s (Y ), where X and Y are sets of size r and s, respectively. Then
Xθ is a basis of Vn,s (Y ) of size r. From Corollary 3.13, there is a common expansion Z of Xθ and Y .
If Z is a d-fold expansion of Xθ and an e-fold expansion of Y then r + (n − 1)d = |Z| = s + (n − 1)e,
so r ≡ s mod (n − 1), as claimed.
We could henceforth restrict to Vn,r , where 1 ≤ r ≤ n − 1. However, we do not need to do
this for what follows here, and it is convenient to allow arbitrary positive values of r, and multiple
instances of the same algebra.
Definition 3.15. Let u, v be elements of Vn,r . Then, u is said to be a proper initial segment of v
if v = uΓ for some non-trivial Γ ∈ A∗ . If u = v or u is a proper initial segment of v then u is called
an initial segment of v .

14

Lemma 3.16 ([17, Section 2, Lemma 2.5(i)-(iii)]). Let B be an A-basis of Vn,r and V a subset of
BhAi.
1. If B and V are finite, then V is contained in an expansion of B if and only if the following
condition is satisfied:
no element of V is a proper initial segment of another.

(†)

2. If B and V are finite, then V is an expansion of B if and only if (†) is satisfied and for each
u ∈ BhAi there exists v ∈ V such that one of u, v is an initial segment of the other.
3. V is a set of free generators for the Ω-subalgebra it generates if and only if (†) is satisfied.
Proof.

1. If V is contained in an expansion of B then, using Lemma 3.5.1, (†) is satisfied.

Suppose V satisfies (†) and write
U = BhAi \ {proper initial segments of elements of V }.
Then (†) implies that V ⊆ U . Also, U is A-closed and BhAi \ U consists of initial segments of
the elements of the finite set V , so it is finite. Thus, by Lemma 3.12, there is an expansion Z
of B such that U = ZhAi. Therefore, U ⊆ ZhAi, and this implies that V ⊆ Z (for an element
of ZhAi \ Z has a proper initial segment in Z ⊆ U so it can not be in V by the definition of
U ). Hence, V is contained in an expansion of B.
2. If V is an expansion of B then (†) is satisfied and for each u ∈ BhAi there exists v ∈ V such
that one of u, v is an initial segment of the other.
Suppose V satisfies (†) and for each u ∈ BhAi there exists v ∈ V such that one of u, v is an
initial segment of the other. By Part 1, V is contained in an expansion Z of B. If V 6= Z
then there is an element z ∈ Z \ V and hence by the hypothesis there exists v ∈ V such that
one of v or z is an initial segment of the other. But no element of Z can be an initial segment
of another, so this is a contradiction and hence V = Z.
3. If V is a set of free generators for the Ω-subalgebra it generates then (†) is satisfied.
Suppose (†) is satisfied. If V is not a free generating set then the same is true of some finite
subset V0 and clearly (†) is also satisfied with V replaced by V0 . Then V0 ⊆ B0 hAi for some
finite subset B0 of B. As (†) holds, it follows from Part 1 that V0 is a subset of an expansion
Z0 of B0 . However, this means that V0 is a subset of a basis of Vn,r , a contradiction.
Corollary 3.17. Let Yi be a finite basis for Vn,r , for i = 1, . . . , m. Then there is a unique minimal
common expansion Z of all the Yi , and Z satisfies ZhAi = ∩m
i=1 (Yi hAi).
Proof. For m = 2, from Corollary 3.13 we have a common expansion Z of Y1 and Y2 such that
ZhAi = Y1 hAi ∩ Y2 hAi. Furthermore, if W is a common expansion of Y1 and Y2 then, from Lemma
3.16, W ⊆ ZhAi, which implies that W is an expansion of Z.
For m > 2, let ZhAi = ∩m−1
i=1 (Yi hAi) and V = ZhAi ∩ Ym hAi, where we assume inductively that
Z is the unique minimal expansion of Y1 , . . . , Ym−1 . From the previous paragraph there exists a
unique minimal expansion W of Z and Ym such that W hAi = V . It follows that the result holds
for Y1 , . . . , Ym and hence by induction for all m.
15

Corollary 3.18. Let Y be a finite basis and let B be an A-basis of Vn,r (x). If Y ⊆ BhAi then Y
is an expansion of B: i.e. Y is an A-basis.
Proof. As Y ⊆ BhAi and Y is a basis, Y satisfies (†) from Lemma 3.16.3. If u ∈ BhAi then
u ∈ Y hAihλi, so for some Γ, ∆ ∈ A∗ and y ∈ Y we have uΓ = y∆. As u ∈ BhAi and y ∈ Y ⊆ BhAi
there exist b, b0 ∈ B and Λ, Λ0 ∈ A∗ such that u = bΛ and y = b0 Λ0 , so bΛΓ = b0 Λ0 ∆, and therefore
b = b0 . Thus bΛΓ = bΛ0 ∆, so either u = bΛ is an initial segment of y = bΛ0 , or vice-versa. Hence,
from Lemma 3.16.2, Y is an expansion of B.
Lemma 3.19 ([17, Section 2, Lemma 2.5(iv)]). Let B be an A-basis of Vn,r . Let Y and Z be d-fold
expansions of B, for d ≥ 1. If Y 6= Z then some element of Y is a proper initial segment of an
element of Z.
Proof. If no element of Y is a proper initial segment of an element of Z then, from Corollary 3.13,
Y ⊆ ZhAi. Then Lemma 3.16 implies that Y is an expansion of Z. However, Y and Z are both
d-fold expansions of B and thus Y = Z. This competes the proof.
Lemma 3.20. Let u ∈ Vn,r and let d be a non-negative integer.
1. If v ∈ Vn,r then u = v if and only if uΓ = vΓ, for all Γ ∈ A∗ of length d.
2. If S is an Ω-subalgebra of Vn,r then u ∈ S if and only if uΓ ∈ S, for all Γ ∈ A∗ of length d.
Proof.

1. If u = v then uΓ = vΓ for all Γ ∈ A∗ of length d.

We shall show that given d ≥ 0 we have
u, v ∈ Vn,r satisfy uΓ = vΓ for all Γ ∈ A∗ of length d

=⇒

u = v.

(∗)

If d = 0 this holds trivially; to proceed we use induction on d. Our hypothesis is that for
all d0 such that 0 ≤ d0 < d, the implication (∗) holds with d0 instead of d. Suppose then
that u, v ∈ Vn,r and uΓ = vΓ for all Γ of length d. We may uniquely write Γ = ∆αi , where
1 ≤ i ≤ n and ∆ ∈ A∗ has length d − 1. Write u∆ as a contraction u∆ = u∆α1 . . . u∆αn λ.
Each string ∆αj has length d, so u∆αj = v∆αj for each j. Then the contraction above is
equal to v∆α1 . . . v∆αn λ = v∆, and so u∆ = v∆.
Now apply this argument to all strings Γ of length d. In doing so we will use every length d−1
string ∆ (n times), and so u∆ = v∆ for every ∆ of length d − 1. By the inductive hypothesis
we conclude u = v.
2. The proof is similar to that of part 1.

4

The Higman-Thompson groups Gn,r

In this section we define the groups which form the object of study in this paper. Throughout
the remainder of the paper, we assume that n ≥ 2, and that Vn,r = Vn,r (x) = WΩ (x)/q, where
x = {x1 , . . . , xr }. When r = 1 we let x = {x}.
When we discuss automorphisms of Vn,r we assume that they are given by listing the images of
a (finite) basis of Vn,r . For instance, let ψ ∈ Vn,r be defined by the bijection ψ : Y → Z, where Y
and Z are bases of Vn,r . If we expand y ∈ Y to form Y 0 = Y \ {y} ∪ {yα1 , . . . , yαn }, the result Y 0 is
16

also a basis by Lemma 3.8. As yαi ψ = yψαi = zαi for i = 1, . . . , n, we see that the automorphism
ψ induces an expansion Z 0 of Z such that Y 0 ψ = Z 0 . Thus, if Y and Z are not expansions of x, we
can find Y 0 and Z 0 = Y 0 ψ contained in xhAi and redefine ψ in terms of Y 0 and Z 0 . In other words,
we may always describe an automorphism by a bijection between A-bases.
As bijections between bases are not particularly easy to read, we represent automorphisms using
pairs of rooted forests. An n-ary rooted tree is a tree with a single distinguished root vertex of degree
n, such that all other vertices have degree n + 1 or 1. If a vertex v is at distance d ≥ 1 from the
root then the n vertices incident to v and not on the path to the root are its children. Vertices of
degree 1 are called leaves. An n-ary rooted tree is said to be A-labelled if the edges joining a vertex
v to its n children are labelled with the elements αi ∈ A, so that two edges joining v to different
children are labelled differently. An A-labelled, r-rooted, n-ary forest is a disjoint union of r rooted,
A-labelled, n-ary trees.
Let T be such a forest consisting of trees T1 , . . . , Tr . For each 1 ≤ i ≤ r, we identify the root
of Ti with the generator xi ∈ x of Vn,r (x). We proceed by recursively identifying vertices of Ti
with elements of {xi }hAi ⊆ Vn,r . Suppose that v ∈ Ti is not a leaf, and that v has been identified
with xi Γ for some Γ ∈ A∗ . Then v has n children c1 , . . . , cn , where cj is the child connected to v
by an edge labelled aj . For each 1 ≤ j ≤ n we identify cj with xi Γαj ; this identifies each vertex
of T with a uniquely determined element of xhAi. Furthermore, by construction, the leaves of T
correspond to an expansion of x. We use such trees to represent automorphisms, as in the following
example.
Example 4.1. Let n = 2, r = 1, x = {x} and let ψ be the element of G2,1 corresponding to the
bijective map between A-bases Y = {xα12 , xα1 α2 , xα2 } and Z = Y ψ = {xα1 , xα2 α1 , xα22 } given by
xα12 ψ = xα1 , xα1 α2 ψ = xα2 α1 , xα2 ψ = xα22 .
The A-labelled binary trees corresponding to these bases are shown below. The labelling of edges
is not shown, but edges from a vertex to its children are always ordered from left to right in the
order α1 , . . . , αn . Thus the leaves of the left hand tree correspond to Y and the leaves of the right
hand tree to Z. The numbering below the leaves determines the mapping ψ; by taking leaf labelled
j on the left to leaf labelled j on the right.
ψ:
1

2

3

−→

1

2

3

Definition 4.2 ([17]). The Higman-Thompson group Gn,r is the group of Ω-algebra automorphisms
of Vn,r .
Note that the largest Thompson group V is isomorphic to G2,1 , because the A-labelled trees we
have described are exactly the tree-pair diagrams used to represent elements of V .
Lemma 4.3 ([17, Lemma 4.1]). If {ψ1 , . . . , ψk } is a finite subset of Gn,r and X is an A-basis of
Vn,r , then there is a unique minimal expansion Y of X such that Y ψi ⊆ XhAi, for i = 1, . . . , k.
That is, any other expansion of X with this property is an expansion of Y .
Proof. For each i, Xψi−1 is a generating set for Vn,r , but may not be a subset of XhAi. Let
Ui = XhAi ∩ Xψi−1 hAi. Then, by Lemma 3.12, Ui is A-closed and there exists an expansion Yi of
X such that Ui = Yi hAi. Now, Corollary 3.17 gives a unique minimal common expansion Y , of the
Yi ’s, and Y hAi = ∩ki=1 (Yi hAi). Then, for all i, Y ⊆ Yi hAi = Ui ⊆ Xψi−1 hAi, so Y ψi ⊆ XhAi.
Let Z be an expansion of X. If Zψi ⊆ XhAi, for all i, then (by the definition of Ui ) Z ⊆ Ui =
Yi hAi, so Z ⊆ ∩ki=1 (Yi hAi) = Y hAi. Hence, from Lemma 3.12, Z is an expansion of Y .
17

Definition 4.4. Let {ψ1 , . . . , ψk } be a finite subset of Gn,r and let X be an A-basis of Vn,r .
The expansion Y of X given by Lemma 4.3 is called the minimal expansion of X associated to
{ψ1 , . . . , ψk }.

4.1

Semi-normal forms

Let ψ ∈ Gn,r , let X be an A-basis of Vn,r , and y ∈ Vn,r . The ψ-orbit of y is the set Oy = {yψ n |
n ∈ Z}. We consider how ψ-orbits intersect the A-subalgebra XhAi. To this end an X-component
of the ψ-orbit of y is a maximal subsequence C of the sequence (yψ i )i=∞
i=−∞ such that all elements
of C are in XhAi. More precisely, C must satisfy
1. if yψ p and yψ q belong to C, where p < q then yψ k belongs to XhAi, for all k such that
p ≤ k ≤ q; and
2. C is a maximal subset of the ψ-orbit of y for which statement 1 holds.
Note: Higman [17, Section 9] refers to X-components as “orbits in XhAi”.
First we distinguish the five possible types of X-component of ψ by giving them names.
1. Complete infinite X-components. For any y in such an X-component, yψ i belongs to XhAi
for all i ∈ Z, and the elements yψ i are all different.
2. Complete finite X-components. For any y in such an X-component, yψ i = y for some positive
integer i, and y, yψ, . . . , yψ i−1 all belong to XhAi.
3. Right semi-infinite X-components. For some y in the X-component, yψ i belongs to XhAi for
all i ≥ 0, but yψ −1 does not. The elements yψ i , i ≥ 0, are then necessarily all different.
4. Left semi-infinite X-components. For some y in the X-component, yψ −i belongs to XhAi for
all i ≥ 0, but yψ does not. The elements yψ −i , i ≥ 0, are then necessarily all different.
5. Incomplete finite X-components. For some y in the X-component and some non-negative
integer i we have y, yψ, . . . , yψ i belonging to XhAi but yψ −1 and yψ i+1 do not.
Example 4.5. Let n = 2, r = 1, x = {x}. Let our bases be
Y = {xα13 , xα12 α2 , xα1 α2 , xα2 α1 , xα22 }

and Z = {xα12 , xα1 α2 α1 , xα1 α22 , xα22 , xα2 α1 }.

Define the automorphism ψ by Y ψ = Z, with the ordering given above.
−→

ψ:
1

2

3

4

5

1

2

3

5

4

Then Y is the minimal expansion of x associated to ψ. Take the basis X to be just X = x. The
X-component of xα13 is left semi-infinite
· · · 7→ xα14 7→ xα13 7→ xα12 ,
and the X-component of xα1 α2 is right semi-infinite:
xα1 α2 7→ xα1 α22 7→ xα1 α23 7→ · · · .
18

The X-component of xα12 α2 is complete infinite
· · · 7→ xα14 α2 7→ xα13 α2 7→ xα12 α2 7→ xα1 α2 α1 7→ xα1 α22 α1 7→ · · · ,
and (xα2 α1 , xα22 ) is a complete finite X-component. We have xα2 = xα2 α1 xa22 λ, so xα2 ψ =
xa22 xα2 α1 λ and xα2 ψ 2 = xα2 ; therefore (xα2 ) is an incomplete finite X-component.
Let ψ ∈ Gn,r , let X be an A-basis of Vn,r , let Y be the minimal expansion of XhAi associated
to ψ and let Z = Y ψ. Then, as discussed above, Y and Z are both expansions of X. From Lemma
3.12, both XhAi \ ZhAi and XhAi \ Y hAi are finite. Furthermore, as |Y | = |Z|, both X and Y are
d-fold expansions, for some d, so |XhAi \ ZhAi| = |XhAi \ Y hAi|.
By definition Y hAi = XhAi ∩ XhAiψ −1 , and moreover ψ maps no proper contraction of Y into
XhAi. Hence
ZhAi = Y hAiψ = XhAiψ ∩ XhAi.
Thus, if u ∈ XhAi \ ZhAi then u 6∈ XhAiψ, so uψ −1 6∈ XhAi and hence u is an initial element
either of an incomplete finite X-component or of a right semi-infinite X-component i.e. in an Xcomponent of type (3) or (5). Similarly, if v ∈ XhAi \ Y hAi then v 6∈ XhAiψ −1 , so vψ 6∈ XhAi and
hence v is a terminal element either of an incomplete finite X-component or of a left semi-infinite
X-component i.e. in an X-component of type (4) or (5).
If C is an X-component of type (3) or (5), then by definition C has an initial element u: that is
uψ −1 6∈ XhAi. Then u 6∈ XhAiψ, and so u ∈ XhAi \ ZhAi. Similarly, if C is an X-component of
type (4) or (5), then C has a terminal element v: that is vψ 6∈ XhAi. Again, v 6∈ XhAiψ −1 and so
v ∈ XhAi \ Y hAi.
Let u be an initial element of an incomplete finite X-component C. By the above, u ∈ XhAi \
ZhAi and by definition of an incomplete finite X-component, there is some non-negative integer k
such that u, uψ, . . . , uψ k all belong to XhAi but uψ k+1 does not. Since uψ k is the terminal element
of the incomplete finite X-component C, we have uψ k ∈ XhAi \ Y hAi. Therefore, the initial
elements of incomplete finite X-components in XhAi \ ZhAi and terminal elements of incomplete
finite X-components in XhAi \ Y hAi pair up.
Given that the initial and terminal elements of the incomplete finite X-components must be
in one-to-one correspondence, all other elements of |XhAi \ ZhAi| (respectively |XhAi \ Y hAi|)
are initial (respectively terminal) elements in right (respectively left) semi-infinite X-components.
Hence there are as many right semi-infinite X-components as left semi-infinite X-components.
The above is summarised in a lemma.
Lemma 4.6 ([17, Lemma 9.1]). Let ψ be an element of Gn,r and let X be an A-basis of Vn,r . There
are only finitely many X-components of ψ of types (3–5) and there are as many of type (3) as of
type (4). If Y is the minimal expansion of XhAi associated to ψ and Z = Y ψ then
• Y hAi = XhAi ∩ XhAiψ −1 and ZhAi = XhAiψ ∩ XhAi;
• XhAi\ZhAi is exactly the set of initial elements of X-components of types (3) or (5); and
• XhAi\Y hAi is exactly the set of terminal elements of X-components of types (4) or (5).
Example 4.7. In Example 4.5, we have XhAi \ ZhAi = {x, xα1 , xα1 α2 , xα2 } and XhAi \ Y hAi =
{x, xα1 , xα12 , xα2 }. The incomplete finite X-components are (x), (xα1 ) and (xα2 ), while xα1 α2
is an initial element of a right semi-infinite X-component and xα12 is a terminal element of a left
semi-infinite X-component. All other X-components of elements of XhAi are complete.
19

Definition 4.8 ([17, Section 9]). An element ψ of Gn,r is in semi-normal form with respect to the
A-basis X if no element of XhAi is in an incomplete finite X-component of ψ.
Lemma 4.9 ([17, Lemma 9.2]). Let ψ ∈ Gn,r and let X be an A-basis of Vn,r . There exists an
expansion of X with respect to which ψ is in semi-normal form.
Proof. Let ψ ∈ Gn,r . We prove the lemma by induction on the number of elements in XhAi which
belong to an incomplete finite X-component. Note that Lemma 4.6 shows us that this number is
finite. If there are no such elements then we are done.
Suppose then that there exists an element u in XhAi which belongs to an incomplete finite
X-component. Thus, there exist y ∈ X and Γ ∈ A∗ such that u = yΓ and some minimal m, k ∈ N0
such that uψ −(m+1) , uψ k+1 6∈ XhAi. It follows that yψ −(m+1) , yψ k+1 6∈ XhAi, so that y is also in
an incomplete finite X-component. Let X 0 be the simple expansion X 0 = X\{y} ∪ {yα1 , . . . , yαn }.
Then X 0 is a A-basis for Vn,r and XhAi\X 0 hAi = {y}. Thus the number of elements of X 00 hAi in an
incomplete finite X 00 -component is one less than the number of elements of XhAi in an incomplete
finite X-component. Hence, by induction, there exists an expansion of X with respect to which ψ
is in semi-normal form.
Remark 4.10. Continuing the discussion above Lemma 4.6, observe that if u ∈ XhAi and u ∈
/
Y hAi ∪ ZhAi then u is both the initial and terminal element of an X-component of ψ; so (u)
constitutes an incomplete finite X-component. Therefore, when implementing the argument of
Lemma 4.9 to find a semi-normal form for ψ, we may pass immediately to a minimal expansion
containing no elements of XhAi \ (Y hAi ∪ ZhAi): that is an expansion minimal amongst those
contained in Y hAi ∪ ZhAi.
Example 4.11. Let n = 2, r = 1, x = {x} and let ψ be the automorphism of Example 4.1.
Here Y = {xα12 , xα1 α2 , xα2 } is the minimal expansion of x associated to ψ and Z = Y ψ =
{xα1 , xα2 α1 , xα22 }. In this example, xhAi \ (Y hAi ∪ ZhAi) = {x} and the minimal expansion of x
not containing x is X = {xα1 , xα2 }. Then Y remains the minimal expansion of X associated to
ψ, XhAi \ ZhAi = {xα2 } and XhAi \ Y hAi = {x, xα1 }. As xα1 is the terminal element of a left
semi-infinite X-component, while xα2 is the initial element of a right semi-infinite X-component it
follows that ψ is in semi-normal form with respect to X.
Example 4.12. Let n = 2, r = 1, x = {x} and let ψ be the element of G2,1 corresponding to the
bijective map:
xα12 ψ = xα22 , xα1 α2 ψ = xα2 α1 , xα2 ψ = xα1 .
ψ:
1

2

3

−→

3

2

1

Again, Y = {xα12 , xα1 α2 , xα2 } is the minimal
{xα1 , xα2 α1 , xα22 }, the minimal expansion of

expansion of x associated to ψ and setting Z = Y ψ =
x contained in Y hAi ∪ ZhAi is X1 = {xα1 , xα2 }; and
Y is still the minimal expansion of X1 associated to ψ. However (xα2 , xα1 ) is an incomplete finite
X1 -component, so ψ is not in semi-normal form with respect to X1 . As xα1 is in an incomplete
finite X1 -component, we first take the simple expansion of X1 at xα1 , giving X2 = Y . As xα2 ψ =
xα1 ∈
/ X2 hAi, (xα2 ) is now an incomplete finite X2 -component, so ψ is not in semi-normal form
with respect to X2 . We take a further simple expansion of X2 at xα2 , to obtain a new A-basis
X3 = {xα12 , xα1 α2 , xα2 α1 , xα22 }. Then ψ maps X3 to itself:
xα12 ψ = xα22 , xα1 α2 ψ = xα2 α1 , xα2 α1 ψ = xα12 , xα22 = xα1 α2 .
20

−→

ψ:
1

2

3

4

3

4

2

1

As all elements of X3 are in the same complete finite X3 -component, ψ is in semi-normal form with
respect to X3 . The minimal expansion of X3 associated to ψ is just X3 .
Example 4.13. The automorphism ψ of Example 4.7 is not in semi-normal form with respect to
X or X1 = {xα1 , xα2 }, as both xα1 and xα2 are in incomplete finite X-components. However, ψ
is in semi-normal form with respect to X2 = {xα12 , xα1 α2 , xα2 α1 , xα22 }. The minimal expansion of
X2 associated to ψ is the A-basis Y of Example 4.5.
The following, which follows directly from the definitions, summarises the possibilities for the
intersection with XhAi of the orbit of an element under an automorphism in semi-normal form.
Corollary 4.14. Let ψ be an element of Gn,r in semi-normal form with respect to the A-basis X,
let v ∈ Vn,r and let Ov be the ψ-orbit of v. Then Ov has one of the following six types.
1. Ov ∩ XhAi = ∅.
2. Ov is finite and Ov ⊆ XhAi, so Ov is a complete finite X-component.
3. Ov is infinite and Ov ⊆ XhAi, so Ov is a complete infinite X-component.
4. Ov ∩ XhAi consists of a unique left semi-infinite X-component.
5. Ov ∩ XhAi consists of a unique right semi-infinite X-component.
6. Ov ∩ XhAi is the disjoint union of a left semi-infinite X-component and a right semi-infinite
X-component.
Remark 4.15. As can be seen from Example 4.17 below, there are automorphisms for which orbits of
the final type in this list exist. In fact we shall show in Example 4.31 that there exist automorphisms
which have such orbits with respect to every semi-normal form. This means that [17, Lemma 9.6] is
false. Consequently, the algorithms [17, Lemma 9.7] for determining if two elements of Vn,r belong
to a single orbit, and [17, Theorem 9.3] for conjugacy of automorphisms are incomplete.
Definition 4.16. Let ψ be an element of Gn,r in semi-normal form with respect to the A-basis X,
and let O be a ψ-orbit of type 6, as given in Corollary 4.14. Then O is called a pond orbit with
respect to X. The subsequence P ⊂ O of elements not in XhAi is called a pond. The width of P
is one more than number of elements in P ; this is the number of times we need to apply ψ to get
from the endpoint of one semi-infinite X-component to the other.
Example 4.17. Let n = 2, r = 1 and V2,1 be free on x = {x}. Let
Y = {xα14 , xα13 α2 , xα12 α2 α1 , xα12 α22 , xα1 α2 , xα2 α1 , xα22 },
Z = {xα12 , xα1 α2 α12 , xα1 α2 α1 α2 , xα1 α22 α1 , xα1 α23 , xα2 α1 , xα22 }
and let ψ ∈ G2,1 be determined by the bijection Y → Z illustrated below.
−→

ψ:
5
1

2

3

6

7

4

1

4

2
21

5

7

6

3

Figure 4.1.1: The binary trees above represent a finite subset of xhAi, as described in the introduction to Section 4. On the left we have annotated this tree, highlighting the semi-infinite
X-components (6) and (7). Below these components sit the pond orbit (10), which is shown on the
right tree. Note that the element w = xα22 xα2 α1 λ ∈
/ xhAi does not correspond to a vertex of this
tree; we have represented it as a ‘phantom’ vertex below xα2 whose left child is xα22 and whose
right child is xα2 α1 —a ‘twisted’ version of xα2 .
As usual, Y is the minimal expansion of x associated to ψ and Z = Y ψ. The minimal expansion of
x contained in Y hAi ∪ ZhAi is X = {xα12 , xα1 α2 , xα2 α1 , xα22 }. Two of these elements are endpoints
of semi-infinite X-components, whereas the other two belong to complete infinite X-components.
· · · 7→ xα14 7→ xα12

(6)

2

xα1 α2 7→ x(α1 α2 ) 7→ · · ·

(7)

· · · 7→
7→ xα12 α22 7→ xα2 α1 7→ xα1 α23 7→ x(α1 α2 )2 α22 7→ · · ·
7→ xα14 α2 α1 7→ xα12 α2 α1 7→ xα22 7→ xα1 α22 α1 7→ x(α1 α2 )2 α2 α1 7→

(8)

xα14 α22

···

···

(9)

Thus ψ is in semi-normal form with respect to X. Now let us compute the ψ-orbit of the element
xα12 α2 .
· · · xα16 α2 7→ xα14 α2 7→ xα12 a2 7→ xα22 xα2 α1 λ 7→ xα1 α22 7→ x(α1 α2 )2 α2 7→ · · ·

(10)

Figure 4.1.1 illustrates the orbit (10), which consists of two semi-infinite X-components and a single
element xα22 xα2 α1 λ (the pond) outside of XhAi. In this case, the pond has width 1 + 1 = 2.
Lemma 4.18 ([17, Lemma 9.3]). Let ψ be an element of Gn,r in semi-normal form with respect to
the A-basis X. Suppose that x is an element of X. Exactly one of the following holds.
(A) There exists Γ ∈ A∗ such that xΓ is in a complete finite X-component. In this case x itself
belongs to a complete finite X-component, which consists of elements of X, and we say x is of
type (A).
(B) There exist Γ, ∆ ∈ A∗ , with Γ 6= ∆, such that xΓ and x∆ belong to the same X-component. In
this case there exists Λ ∈ A∗ and m ∈ Z \ {0} with |m| minimal, such that xψ m = xΛ; we say
x is of type (B). If m > 0 then the X-component containing x is right semi-infinite; if m < 0
then the X-component containing x is left semi-infinite.
22

(C) x is not of type (A) or (B) above and there exists some z ∈ X of type (B) and non-trivial
∆ ∈ hAi such that xψ i = z∆. In this case the X-component containing x is infinite; and we
say x is of type (C).
Proof. (A) If x belongs to an infinite X-component of ψ (of types (1), (3) or (4) that is), then so
does xΓ, a contradiction. As ψ is in semi-normal form with respect to X it follows that x is in
a complete finite X-component. Let d be the smallest positive integer such that xψ d = x. For
each 1 ≤ i ≤ d − 1 write xψ i = z∆ for some z ∈ X and ∆ ∈ A∗ . Then z must also belong to a
complete finite X-component, so we can write zψ d−i = yΓ for some y ∈ X and Γ ∈ A∗ . Then
x = xψ d = z∆ψ d−i = zψ d−i ∆ = yΓ∆. From Lemma 3.16, we have y = x and Γ = ∆ = ε, so
xψ i = z ∈ X, as claimed.
(B) If x belongs to a finite X-component then, from (A), the X-component of xΓ consists of
elements zΓ, where z ∈ X, contrary to the hypotheses of (B). Therefore x belongs to an
infinite X-component of ψ. Without loss of generality we may assume that there is i > 0 such
that xΓψ i = x∆. Suppose first that xψ k ∈ XhAi, for all k ≥ 0. Then xψ i = vΛ, for some
v ∈ X and Λ ∈ A∗ , and thus x∆ = xΓψ i = vΛΓ; so v = x and ∆ = ΛΓ, and we obtain
xψ i = xΛ.
Similarly, if xψ −k ∈ XhAi, for all k ≥ 0, then xψ −i = xΛ0 , for some Λ0 ∈ A∗ , with Γ = Λ0 ∆.
Note that if xψ k ∈ XhAi for all k, then x = xΛΛ0 , which forces Λ = Λ0 = ε, so Γ = ∆, a
contradiction. Hence the final statement of (B) holds.
(C) In this case x must belong to an infinite X-component, as (A) does not hold. As X is finite
there is z ∈ X such that zΓ and z∆ belong to the X-component of x, for distinct Γ and ∆ in
A∗ ; and then z is of type (B), as required.
Definition 4.19. Let u ∈ Vn,r and ψ ∈ Gn,r . If uψ d = uΓ for some d ∈ Z \ {0} and some
Γ ∈ A∗ \ {1}, then u is a characteristic element for ψ. If u is a characteristic element for ψ then
the characteristic of u is the pair (m, Γ) such that m ∈ Z \ {0}, Γ ∈ A∗ with
• uψ m = uΓ and
• for all i such that 0 < |i| < |m|, uψ i 6∈ uhAi.
In this case Γ is called the characteristic multiplier and m is the characteristic power for u, with
respect to ψ.
From the definition, if ψ is in semi-normal form with respect to X then an element x ∈ X is
of type (B) if and only if x is a characteristic element: in which case it follows from Lemma 4.24
below that the ψ-orbit of x is of type 4 or 5 in Corollary 4.14. On the other hand, if x ∈ X has
type (C) then the ψ-orbit of x may be of types 3, 4, 5 or 6 in Corollary 4.14.
Example 4.20. In Example 4.13, the automorphism ψ is in semi-normal form with respect to an
A-basis X. The elements xα2 α1 and xα22 of X are of type (A). The element xα12 ∈ X is of type (B)
with characteristic (−1, α1 ), while xα1 α2 ∈ X is of type (B) with characteristic (1, α2 ); and both
of these elements are endpoints of their semi-infinite X-components.
In Example 4.17 the elements xα2 α1 and xα22 of X are of type (C), are not characteristic and
belong to complete infinite X-components. The elements xα12 α2 and xα1 α22 in the pond orbit (10)
are also type (C) and non-characteristic, but belong to semi-infinite X-components.
23

Lemma 4.21. If u ∈ Vn,r is a characteristic element for ψ ∈ Gn,r then
1. the characteristic (m, Γ) is uniquely determined, and
2. if v is in the same ψ-orbit as u then v is a characteristic element with the same characteristic
as u.
0

Proof. To see part 1, suppose that u has characteristic (m, Γ). If uψ m = u∆ and for all 0 < |k| <
|m0 | we have uψ k 6∈ uhAi, then |m0 | ≥ |m| by Definition 4.19, so m = ±m0 . If uψ −m = u∆ then
u = uψ m ∆ = uΓ∆, which cannot happen as Γ 6= 1.
For part 2, let uψ r = v. For all k such that uψ k = u∆ with ∆ ∈ A∗ , we have
vψ k = uψ r ψ k = uψ k ψ r = u∆ψ r = uψ r ∆ = v∆.
Interchanging u and v we see also that whenever vψ k = v∆ then uψ k = u∆.
From Lemma 4.21, if a ψ-orbit has a characteristic element, then every X-component of this ψorbit contains a characteristic element, and all these elements have the same characteristic. Bearing
this in mind we make the following definition.
Definition 4.22. Let ψ ∈ Gn,r have an X-component C containing a characteristic element u.
Then we define the characteristic of C to be equal to the characteristic of u.
Theorem 4.23 ([17, Theorem 9.4]). Let ψ ∈ Gn,r be in semi-normal form with respect to X. Then
ψ is of infinite order if and only if it has a characteristic element u. Moreover, if ψ is of infinite
order then we may assume that u ∈ X.
Proof. If u is a characteristic element for ψ with characteristic (m, Γ) then uψ m = uΓ, so uψ mq =
uΓq . So for sufficiently large q, uψ mq ∈ XhAi. Then uψ mq also has characteristic (m, Γ) by
Lemma 4.21. Write uψ mq = x∆, for some x ∈ X and ∆ ∈ A∗ . Now x∆Γ = uψ mq Γ = uψ m(q+1) =
x∆ψ m , so from Lemma 4.18, x has type (B). Thus we may assume u ∈ X. Now
uψ mj = uψ m ψ m(j−1) = uΓψ m(j−1) = uΓψ m ψ m(j−2)
= uψ m Γψ m(j−2) = uΓ2 ψ m(j−2) = · · · = uΓj ,
for j ∈ N. Since Γ is a characteristic multiplier, the elements uΓj are all different for j ∈ N, so ψ
has infinite order.
Conversely, if ψ has no characteristic element, then certainly there are none in X, so X has no
elements of type (B) nor type (C). Thus all elements of X are of type (A), as ψ is in semi-normal
form; whence ψ is a permutation of X and has finite order.
Lemma 4.24. Let ψ be in semi-normal form with respect to an A-basis X and let u ∈ Vn,r . If u has
characteristic (m, Γ) then the ψ-orbit of u has precisely one X-component, which is semi-infinite
(right semi-infinite if m > 0 and left semi-infinite if m < 0) and consists of elements of the form
xΛ, where x ∈ X is of type (B) and Λ ∈ A∗ .
Furthermore, if xΛ belongs to the X-component of the ψ-orbit of u, where x ∈ X and Λ ∈ A∗ ,
then x has characteristic (m, Γ1 Γ0 ), where Γ = Γ0 Γ1 , Λ = (Γ1 Γ0 )p Γ1 = Γ1 Γp , p ≥ 0, and Γ0 is
non-trivial.

24

Proof. As uψ m = uΓ we have uψ mq = uΓq , for all integers q ≥ 0, and choosing q sufficiently large
uΓq ∈ XhAi. Thus we may assume that u ∈ XhAi. Let C denote the X-component containing u
and write u = xΛ, where x ∈ X and Λ ∈ A∗ .
Assume first that m > 0. As u has characteristic (m, Γ), both xΛ and xΛΓ belong to C, so x
is of type (B) by Lemma 4.18. Suppose there is an integer K ≥ 0 such that uψ −k ∈ XhAi, for all
k ≥ K. (That is, suppose that the ψ-orbit of u contains a left semi-infinite X-component.) Let
Λ = Λ0 Γt , where Λ0 has no terminal segment equal to Γ. Then, for j such that m(j + 1) ≥ K and
j ≥ t, uψ −m(j+1) ∈ XhAi, so uψ −m(j+1) = zΞ for some z ∈ X and Ξ ∈ A∗ . From Lemma 4.21 we
see that zΞ has characteristic (m, Γ). Hence
zΞΓj+1 = zΞψ m(j+1) = u = xΛ0 Γt ,
which implies z = x and ΞΓj−t+1 = Λ0 , a contradiction. As ψ is in semi-normal form with respect
to X and C is not a complete X-component, the C must be right semi-infinite. We have just shown
the ψ-orbit of u contains no left semi-infinite X-component, so C is the unique X-component of
this ψ-orbit.
For the second part of the lemma, suppose x has characteristic (k, Ω). The X-component of
x cannot be left semi-infinite, or else xΛψ −i ∈ XhAi for all i ≥ 0; this would mean that C is
not right semi-infinite. Hence x is in a right semi-infinite X-component and k > 0. If Λ = Ωj Λ1
then xΛ1 ψ kj = xΩj Λ1 = u and so C contains xΛ1 ; and it suffices to prove the Lemma under the
assumption that that Λ has no initial segment equal to Ω.
Suppose that m = kp + r, where 0 ≤ r < k. Then xΛψ kp = xΩp Λ and xΩp Λψ r = xΛψ kp+r =
xΛψ m = xΛΓ. However, as x is in a right semi-infinite X-component, xψ r = zΞ, for some z ∈ X
and Ξ ∈ A∗ . Thus xΛΓ = xΩp Λψ r = xψ r Ωp Λ = zΞΩp Λ, which implies that z = x and ΛΓ = ΞΩp Λ.
Now, as xψ r = xΞ, 0 ≤ r < k and x has characteristic (k, Ω), it must be that r = 0, m = kp and
Ξ = ε. We have now ΛΓ = Ωp Λ, and as Λ has no initial segment equal to Ω it follows that Ω = ΛΩ1 .
Now uψ k = xΛψ k = xψ k Λ = xΩΛ = xΛΩ1 Λ = uΩ1 Λ, so k ≥ m, by definition of characteristic.
Therefore k = m and Γ = Ω1 Λ, completing the proof in the case m > 0.
In the case when m < 0 the result follows from the above on replacing ψ by ψ −1 .
An element w of the free monoid A∗ is said to be periodic with period i if w = a1 · · · an , where
aj ∈ A, and ak = ak+i , for 1 ≤ k ≤ n − k. In this sense, in Lemma 4.24 above, Λ = (Γ1 Γ0 )p Γ1 is
periodic of period m.
Lemma 4.25. Let ψ ∈ Gn,r and u ∈ Vn,r such that uψ k = u∆, where ∆ 6= ε. Then u has
characteristic (m, Γ) with respect to ψ, where k = mq and ∆ = Γq , for some positive integer q.
Proof. Let ψ be in semi-normal form with respect to X, and let (m, Γ) be the characteristic of u.
Suppose first that k > 0. As in the proof of Lemma 4.24, we may assume that u ∈ XhAi, the
X-component of u is right semi-infinite and that there exist x ∈ X and Γ1 ∈ A∗ such that u = xΓ1
and x has characteristic power m. Then k ≥ m, say k = mq + s, where 0 ≤ s < m and q ≥ 1. Let
xψ s = yΛ0 , where y ∈ X and Λ0 ∈ A∗ . Now xΓ1 ∆ = u∆ = uψ k = uψ mq+s = uΓq ψ s = xψ s Γ1 Γq =
yΛ0 Γ1 Γq . Hence x = y and so s = 0 and k = mq. Moreover xΛ∆ = u∆ = uψ k = uψ mq = uΓq =
xΛΓq , so Λ∆ = ΛΓq , from which ∆ = Γq , as required.
If k < 0, replace ψ with ψ −1 in the argument above. We have uψ −k = u∆, so from the previous
part of the proof, u has characteristic (m, Γ), with respect to ψ, where −k = mq, q > 0, and
∆ = Γq . If follows that u has characteristic (−m, Γ), with respect to ψ, and −m = kq, completing
the proof.
25

Corollary 4.26. Let ψ be in semi-normal form with respect to an A-basis X and let u ∈ Vn,r .
Then there exists an element Λ ∈ A∗ such that uΛ belongs to a complete X-component of ψ.
Proof. Multiplying by a sufficiently long element of A∗ we may, as usual, assume that u ∈ XhAi,
so u belongs to either a complete or a semi-infinite X-component of ψ. There are finitely many
semi-infinite X-components (Lemma 4.6). If S is a characteristic semi-infinite X-component with
characteristic (m, Γ) then, from Lemma 4.24, elements of S have the form xΛ where x ∈ X, Λ ∈ A∗
and, for all but finitely many elements of S, Λ is periodic of period m.
Let FS be the finite subset of elements of A∗ such that Λ ∈ FS only if xΛ ∈ S and Λ is
not periodic of period m. Let F0 be the union of the FS over all characteristic semi-infinite Xcomponents. If S is non-characteristic then, from Lemma 4.18, S contains an element z∆, where
z ∈ X of type (B), with characteristic (m0 , Γ0 ), say. It follows, from Lemma 4.24 again, that all but
finitely many elements of S have the form xΛ∆ where x ∈ X, Λ ∈ A∗ and Λ is periodic of period m0 .
This time, let FS be the finite subset of elements of A∗ such that Λ∆ ∈ FS only if xΛ∆ ∈ S and Λ
is not periodic of period m0 . Let F1 be the union of the FS over all non-characteristic semi-infinite
X-components.
Let M be the maximum of lengths of elements of F0 ∪ F1 and assume u = xΓ, where x ∈ X,
Γ ∈ A∗ . Choose element Ξ of A∗ such that ΓΞ has length greater than M , is not periodic and does
not factor as Λ∆, where Λ is periodic and ∆ ∈ F1 . Then uΞ = xΓΞ cannot belong to a semi-infinite
X-component, so must belong to a complete X-component.

4.2

Quasi-normal forms

Quasi-normal forms are particular semi-normal forms which give representations of automorphisms
minimising the number of elements in pond orbits. In [17, Section 9] it is claimed that if an
automorphism is given with respect to a quasi-normal form, then it has no pond orbits. In this
section we shall see that this is not the case.
Definition 4.27 ([17, Section 9]). An element ψ of Gn,r is in quasi-normal form with respect to
the A-basis X if it is in semi-normal form with respect to X, but not with respect to any proper
contraction of X.
It follows from Lemma 4.3 that for ψ ∈ Gn,r there exists an A-basis X with respect to which ψ
is in quasi-normal form. For instance, the automorphisms ψ in Examples 4.11, 4.13 and 4.17 are in
quasi-normal form with respect to the bases X in those examples. Additionally, the automorphism
ψ of Example 4.12 is in quasi-normal form with respect to the basis X3 .
Lemma 4.28 (cf. [17, Lemma 9.7]). Given an element ψ ∈ Gn,r there exists a unique A-basis,
denoted Xψ , with respect to which ψ is in quasi-normal form. Furthermore Xψ may be effectively
constructed.
Proof. Assume ψ is given by listing the images of elements of X, where X is an A-basis of Vn,r . We
modify X to find an A-basis X 0 with respect to which ψ is in semi-normal form. For each y ∈ X
we can list elements of the ψ-orbit of y.
. . . , yψ −3 , yψ −2 , yψ −1 , y, yψ, yψ 2 , yψ 3 , . . .
We enumerate the forward sequence (yψ m )m≥0 , until we reach m ≥ 0 such that

26

(1F) either yψ m ∈ XhAi with yψ m+1 6∈ XhAi, or
(2F) for some 0 ≤ l < m, ŷ ∈ X and Γ, ∆ ∈ A∗ we have yϕl = ŷΓ and yϕm = ŷ∆.
Similarly, we enumerate the backwards sequence (yψ −k )k≥0 until we reach k ≥ 0 such that
(1B) either yψ −k ∈ XhAi with yψ −(k+1) 6∈ XhAi or,
(2B) for some 0 ≤ l < k, ŷ ∈ X and Γ, ∆ ∈ A∗ we have yϕ−l = ŷΓ and yϕ−k = ŷ∆.
Given y ∈ X, the forward part of the process above produces a sequence of elements of XhAi, until
it halts. As X is finite, if it does not halt at step (1F) then it halts at step (2F); so always halts.
Similarly, the backward part of the process always halts.
If some y satisfies (1F) and (1B), then y is in an incomplete X-component, so ψ is not in
semi-normal form with respect to X. In this case we take a simple expansion X 0 of X at the
element y. Next, use the proof of Lemma 4.9 to find an expansion X 00 of X 0 with respect to
which ψ is in semi-normal form. We now replace X with X 00 and return to the start of this proof.
Repeating as necessary, eventually we shall find X such that no y ∈ X satisfies both (1F) and
(1B). The repetition terminates because the number of elements x00 ∈ X 00 belonging to incomplete
X 00 components is strictly smaller than the corresponding number for X.
At this stage, every y ∈ X satisfies one of (2F) and (2B), so ψ is in semi-normal form with
respect to X by Lemma 4.18. We can now test all the contractions of the A-basis X to find an
expansion of x with respect to which ψ is in a quasi-normal form.
For uniqueness, we will argue by contradiction. Let ψ be in quasi-normal form with respect to X1
and X2 , with X1 6= X2 . Since X1 , X2 are expansions of x, (without loss of generality) there exists a
simple contraction X10 of X1 which contains an element y of X2 \X1 . Then X10 hAi = X1 hAi∪{y}hAi
and, as ψ is in semi-normal form with respect to X2 , it is also in semi-normal form with respect to
X10 , contrary to the definition of quasi-normal form.
Remark 4.29. Let ψ ∈ Gn,r be in quasi-normal form with respect to X. The proof of this lemma
illustrates that if ψ is in semi-normal form with respect to X 0 , then X 0 is an expansion of X.
The converse is false: it is not true in general that ψ is in semi-normal form with respect to all
expansions of X.
Lemma 4.30. Let ψ ∈ Gn,r be in semi-normal form with respect to an A-basis X and let u, v ∈
XhAi. Then we can effectively decide whether or not u, v are in the same X-component, and if so,
find the integers m for which uψ m = v.
Proof. As u ∈ XhAi, we have u = yΛ where y ∈ X and Λ ∈ A∗ . We now run the process of
Lemma 4.28 on y. If the process halts with yψ m = y, for some m then we may list the elements
uψ i = yψ i Λ, i = 0, . . . , m − 1, of the (complete finite) ψ-orbit of u. In this case v is in the same
ψ-orbit as u if and only if it appears in the list, so we are done.
Otherwise the process halts at least one of the states (2F) and (2B). We obtain ye ∈ X and
integers k 6= l such that yϕk = yeΛ1 and yϕl = yeΛ2 , where Λ1 and Λ2 are distinct elements of A∗ .
It follows from Lemma 4.18 that ye is of type (B). As u and uϕk = yΛϕk = yeΛ1 Λ are k steps apart
in the same X-component, we may replace u = yΛ with u
e = yeΛ1 Λ. Therefore we now assume that
u = yΛ, where y is of type (B).
Now, when we run the process of Lemma 4.28 on y it halts either at (2F) and (1B) or else
at (1F) and (2B). Suppose first the forward part halts at (2F). Then y is in a right semi-infinite
27

X-component and there is a minimal positive integer m such that yψ m = yΓ, with Γ 6= 1. That
is y has characteristic (m, Γ), with m > 0. Set u0 = yΛ0 . If Λ = Γi Λ0 where Λ0 has no initial
segment Γ, then
u0 ψ mi = yΛ0 ψ mi = yψ mi Λ0 = yΓi Λ0 = yΛ = u,
so u0 is mi steps away from u in the ψ-orbit of u. We may replace u = yΛ by u0 = yΛ0 . This
allows us to assume from now on that Λ has no initial segment equal to the characteristic multiplier
Γ of y.
Next we run the process of Lemma 4.28 on u instead of y. As y is in a right semi-infinite
X-component the forward part of the process halts at (2F). We obtain a list of elements of the
X-component of u of the form
zr Φr , · · · , z1 Φ1 , u = yΛ, y1 Γ01 Λ, . . . , ym−1 Γ0m−1 Λ, yΓΛ,

(11)

where yj , zj ∈ X, Γ0j , Φj ∈ A∗ , zj Φj = uψ −j , for 1 ≤ j ≤ r and for some r ≥ 0, and yψ s = ys Γ0s ,
for 0 < s < m. (The yi ’s must be distinct otherwise u would have characteristic power less than
m.) We proceed differently based on which state the backwards enumeration finishes in.
Case (1B). If the backward part of the process halts at (1B) then zr Φr ψ −1 = uψ −r−1 ∈
/ XhAi.
In this case, the entire X-component of u consists of the elements on this list together with elements
yi Γ0i Γq Λ,

with q > 0 and 0 < i ≤ m,

where we set y0 = y, Γ00 = Γ.
As v ∈ XhAi we also have z ∈ X and ∆ in A∗ such that v = z∆. If z is in a finite X-component
then v cannot belong to the same X-component as u, so we assume z is in an infinite X-component.
As in the case of u, we may adjust v so that z is of type (B). As before we find a characteristic
multiplier Φ for z and, replacing ∆ with a shorter element if necessary, we may assume that ∆ has
no initial segment equal to Φ.
If v = uψ d , where d ≥ 0, then v = yi Γ0i Γq Λ, for some q ≥ 0 and i with 0 ≤ i < m. In this case,
z = yi and by Lemma 4.24 and our assumption on v we have q = 0, so v = yi Γ0i Λ, which appears
on list (11). Assume then that v = uψ d , where d < 0. As the backward part of the enumeration of
the ψ-orbit of u halts at (1B), the X-component of u has initial element zr Φr , and v must appear
on list (11).
Case (2B). On the other hand, if the backward part of the process stops at (2B) then u is in a
complete infinite X-component and, for some s with 0 ≤ s ≤ r, we have zr = zs (and r is minimal
with this property). It follows that zs is of type (B) and in a left semi-infinite X-component. Again,
we may assume that v = z∆, where ∆ ∈ A∗ , z ∈ X is of type (B) and has characteristic multiplier
Φ, such that ∆ has no initial segment equal to Φ. As before, if v = uψ d with d ≥ 0, then v appears
on list (11). Assume then that v = uψ d , where d < 0. Repeating the argument above, using the
left semi-infinite X-component of zs instead of the right semi-infinite X-component of y, it follows
again that v appears on list (11).
Therefore, in the case where y is in a right semi-infinite X-component we have v in the Xcomponent of u if and only if v lies on the list (11); and we may compute m such that uψ m = v,
if this is the case. Finally, if the enumeration of the X-component of y halts at steps (1F) and
(2B) then the process is essentially the same, except that we deal with a left, rather than a right,
semi-infinite X-component of y.
This procedure allows us to decide if two given words in XhAi belong to the same X-component
so, if there are no pond orbits, we may decide if two such words belong to the same ψ-orbit. On
28

the other hand, as the enumeration of components always stops once we fall outside XhAi, we
cannot detect when a pair of elements lie in the same ψ-orbit but on opposite sides of a pond. We
demonstrate below that there exist automorphisms for which every semi-normal form has a pond;
thus we require a strategy to deal with ponds.
Lemma 4.31. Let ψ ∈ Gn,r be in semi-normal form with respect to X, and suppose that some ψorbit O contains a pond with respect to X. If ψ is in semi-normal form with respect to an expansion
X 0 of X, then O is also a pond-orbit with respect to X 0 .
Proof. Let us write O as
. . . lψ −t , . . . lψ −1 , l, p1 , . . . pk , r, rψ, . . . rψ s , . . .

O:

where l, r ∈ XhAi are endpoints of semi-infinite X-components and the pi ∈
/ XhAi form a pond of
length k. To begin with we claim that, for sufficiently large s ≥ 0, we have rψ s ∈ X 0 hAi. Indeed,
because r belongs to a semi-infinite X-component, Lemma 4.18 implies that there is some s0 ≥ 0
0
for which rψ s = r0 ∆, where ∆ ∈ A∗ and r0 ∈ X has characteristic (m, Γ). Therefore, for all q ≥ 0,
0

0

rψ s +mq = rψ s ψ mq = r0 ∆ψ mq = r0 ψ mq ∆ = r0 Γq ∆.
0

By taking q sufficiently large, we can ensure that rψ s +mq ∈ X 0 hAi. This works because the
difference XhAi \ X 0 hAi is finite. So we can find s ≥ 0 such that rψ s ∈ X 0 hAi. Similarly, there is
some t ≥ 0 for which lψ −t ∈ X 0 hAi.
Since X 0 hAi ⊂ XhAi, it follows that each pi ∈
/ X 0 hAi. Appealing to Corollary 4.14, the only
possibility is that O is a pond-orbit with respect to X 0 .
Notice that the pond width with respect to X 0 is at least the previous width (k + 1) with respect
to X. Additionally, if ψ was in quasi -normal form with respect to X, this (with Remark 4.29) shows
that every semi-normal form X 0 for ψ contains the pond given above. Example 4.17 shows that
this possibility does occur.
Lemma 4.32. Given an element ψ ∈ Gn,r in semi-normal form with respect to an A-basis X we
may effectively construct the set P (ψ) of the triples (l, k, r) such that r (resp. l) is the initial (resp.
terminal) word in a right (resp. left) semi-infinite X-component, and k is the width of the pond
between them.
Proof. Let Y be the minimal expansion of X associated to ψ and let Z = Y ψ. Since there are no
incomplete X-components, Lemma 4.6 tells us that the set of initial elements of right semi-infinite
X-components is R = XhAi\ZhAi. This is finite, so we may enumerate this effectively. The same
is true for the set L = XhAi\ZhAi of terminal elements of left semi-infinite X-components. To
enumerate P (ψ), for each (l, r) ∈ L × R we need to solve the equation r = lψ k for some k, or to
determine that there is no solution. A solution exists if and only if rΓ = lΓψ k , for all Γ ∈ A∗ .
With this in mind, first find Γ ∈ A∗ such that lΓ is in a complete infinite X-component. We
do this by enumerating the words Γ of length 1, 2, . . . and applying the process of Lemma 4.28 to
each element lΓ in turn. We stop when we find Γ such that the process halts at (2F) and (2B).
Now use Lemma 4.30 to determine whether rΓ and lΓ are in the same X-component. If not, then
there cannot exist an element of the form (l, k, r) ∈ P (ψ); that is l and r are not joined by a pond.
Assume then that rΓ = lΓψ k , for some k. We can test to see if r = lψ k directly, which holds
if and only if (l, k, r) ∈ P (ψ). If the equality were false, is it possible that (l, k 0 , r) ∈ P (ψ) for a
29

0

0

0

different k 0 6= k? This would mean that r = lψ k , so lψ k Γ = rΓ = lΓψ k and thus lΓψ k−k = lΓ. As
lΓ belongs to a complete infinite X-component, this means k = k 0 ; so the answer to our previous
question is ‘no’. In this situation there are no elements of the form (l, k 0 , r) in P (ψ).
In practice, when enumerating the sets L and R in the proof above, we need consider only noncharacteristic elements, as Lemma 4.24 implies that no characteristic element belongs to a pond
orbit.
Example 4.33. Let ψ and X be the automorphism and basis described in Example 4.17; we noted
above that ψ is in quasi-normal form with respect to X. We claim that this ψ-orbit is the only
pond orbit with respect to X.
The endpoints of semi-infinite X-components are precisely
L = XhAi \ Y hAi = {xα12 , xα13 , xα12 α2 }

and R = XhAi \ ZhAi = {xα1 α2 , xα1 α2 α1 , xα1 α22 }.

The four endpoints xα12 , xα13 , xα1 α2 and xα1 α2 α1 have characteristics (−1, α12 ), (−1, α12 ), (1, α1 α2 )
and (1, α2 α1 ) respectively. Are the two remaining endpoints l = xα12 α2 and r = xα1 α22 separated
by a pond? (We saw before in computation (10) that they are, but to illustrate Lemma 4.32 we’ll
remain ignorant of this.)
Multiplying by Γ = α1 we obtain lΓ = xα12 α2 α1 , which is in a complete infinite X-component.
We also see that rΓ = lψ 2 Γ = xα1 α22 α1 is in this component, so we have a candidate pond width
of k = 2. Fortunately we directly computed that r = lψ 2 in (10), so P (ψ) = {(xα12 a2 , 2, xα1 α22 )}.
Lemma 4.34 (cf. [17, Lemma 9.7]). Let ψ ∈ Gn,r and u, v ∈ Vn,r . Then we can effectively decide
whether or not u, v are in the same ψ-orbit, and if so, find the integers m for which uψ m = v.
Proof. For a fixed integer s ≥ 0 we have uψ m = v if and only if (uΓ)ψ m = uψ m Γ = vΓ for all
Γ ∈ A∗ of length s (using Lemma 3.20). Now, suppose that we have an algorithm A to decide
whether v 0 = u0 ψ m for some m, given elements u0 , v 0 of XhAi (and to return m, if so). Then if u, v
are arbitrary elements of Vn,r we may choose s such that uΓ and vΓ belong to XhAi, for all Γ ∈ A∗
of length s, and input all these elements to the algorithm A in turn. In the light of the previous
remark, this allows us to determine whether or not u and v belong to the same ψ-orbit (and to
return appropriate m, if so). Hence we may assume u, v ∈ XhAi.
By Corollary 4.14, u and v belong to the same ψ-orbit if and only if either they belong to the
same X-component of a ψ-orbit, or they belong to different X-components of a single pond orbit.
We may use Lemma 4.30 to decide whether or not u and v both belong to the same X-component.
If so we are finished. If not, and both belong to semi-infinite X-components, then for each triple
(l, k, r) in P (ψ) we check whether u belongs to the same component as l or r.
If u belongs to neither component then u is not in a pond orbit, and thus u and v do not share
a ψ-orbit. Otherwise if u and l (resp. r) share an X-component, we run the same check on v and r
(resp. l). If the check determines that v is not in the X-component in question, then u and v do
not share a ψ-orbit. Else we have l = uψ a and v = rψ b for some a and b, so v = uψ a+k+b .
Example 4.35. Let ψ be the automorphism of Examples 4.17 and 4.33, which is in quasi-normal
form with respect to X = {q1 = xα12 , q2 = xα1 α2 , q3 = xα2 α1 , q4 = xα22 }. The elements q1 and
q2 have characteristics (−1, α12 ) and (1, α1 α2 ) respectively, whereas q3 and q4 belong to complete
infinite X-components such that q3 ψ = q2 α22 and q4 ψ −1 = q1 α2 α1 .

30

1. We wish to test if u = xα1 α22 α12 α2 = q2 α2 α12 α2 and v = xα2 α12 = q3 α1 belong to the same
ψ-orbit. Because q3 is not characteristic, Lemma 4.30 first replaces v = q3 α1 with v 0 = vψ =
q3 ψα1 = q2 α22 α1 , which begins with the characteristic element q2 of X. Enumerating the
X-component containing u gives us a specific instance of list (11)
xα14 α2 α12 α2 7→ xα12 α2 α12 α2 7→ xα22 α1 α2 7→ xα1 α22 α12 α2 7→ x(α1 α2 )2 α2 α12 α2
{z
}
|

(11’)

u

once the enumeration has halted at stages (2F) and (2B). Since v 0 does not lie on this list, we
conclude that v 0 does not belong to the X-component of u, so neither does v.
We now need to check if u and v are separated by a pond. In Example 4.33 we showed that
ψ has only one pond-orbit, and referring to the computation (10) we see that neither u nor v
belong to this orbit. Hence u and v 0 do not share a ψ-orbit.
2. Now let us test if u and w = xα14 α2 α12 α2 = q1 α12 α2 α12 α2 share a ψ-orbit. We remove the
characteristic multiplier α12 of q1 from w, obtaining w0 = q1 α2 α12 α2 where w0 ψ −1 = w. From
list (11’) we notice that uψ −2 = w0 , so uψ −3 = w.
3. Let u = xα18 α2 , v = xα14 α2 α1 and w = x(α1 α2 )3 α2 . In terms of X, these are u = q1 α16 α2 ,
v = q1 α12 α2 α1 , and w = q2 (α1 α2 )2 α2 . Since q1 and q2 are characteristic, we remove copies
of the characteristic multipliers. We obtain u0 = q1 α2 = uψ 3 , v 0 = q1 α2 α1 = v 0 ψ and
w0 = q2 α2 = wψ −2 . Enumerating the X-component of u0 gives us
. . . 7→ xα14 α2 7→ xα12 α2 = u0 ,
(halting at stages (1F) and (2B)) and we see that neither v 0 nor w0 are in this list. However,
u0 is adjacent to a pond. Referring once more to Example 4.17, we see that the corresponding
endpoint is ū = u0 ψ 2 = xα1 α22 . Its X-component begins
ū = xα1 α22 7→ x(α1 α2 )2 α2 7→ . . .
Since this list does not contain v 0 , we conclude that u and v do not share a ψ-orbit. On the
other hand, we note that w0 = ū belongs to the list. Hence u and w belong to the same
ψ-orbit, and having kept track of the various powers, we calculate that
wψ −2 = w0 = ū = u0 ψ 2 = uψ 3 ψ 2 =⇒ w = uψ 7 .

5

The Conjugacy problem

For a group with presentation G = hX | Ri, the conjugacy problem is to determine, given words
g, h ∈ F(X) whether or not g is conjugate to h in G; denoted g ∼ h. The strong form, which
we consider here, requires us to produce a conjugator c ∈ F(X) when g is conjugate to h, i.e. an
element c such that c−1 gc =G h. We say the conjugacy problem is decidable if there is an algorithm
which for inputs g and h outputs “yes” if they’re conjugate and “no” otherwise. The stronger form
is decidable if there is an algorithm which produces a conjugator c in the “yes” case. Note that the
word problem is the special case of the conjugacy problem where h = 1.
As pointed out at the beginning of Section 4, an element ψ of Gn,r may be uniquely represented
by the triple (Y, Z, ψ0 ), where Y is the minimal expansion of ψ, Z = Y ψ and ψ0 is a bijection
31

between Y and Z, namely ψ0 = ψ|Y . This triple is called a symbol for ψ. In [17, Section 4] a
finite presentation of Gn,r is given, with generators the symbols (Y, Z, ψ0 ) such that Y is a d-fold
expansion of x, for d ≤ 3. As we may effectively enumerate symbols and effectively construct
the symbol for ψ1 ψ2 , from the symbols for ψ1 and ψ2 , words in Higman’s generators effectively
determine symbols and vice-versa. Therefore when we consider algorithmic problems in Gn,r we
may work with symbols for automorphisms, and leave the presentation in the background. That
is, we always assume that automorphisms are given as maps between bases of Vn,r (from which a
symbol may be computed). As minimal expansions are unique it follows immediately that the word
problem is solvable in Gn,r . In this section we give an algorithm for the conjugacy problem in Gn,r ,
based on (a complete version of) Higman’s solution.

5.1

Higman’s ψ-invariant subalgebras

Let ψ be an element of Gn,r . Higman defined two Ω-subalgebras of Vn,r determined by ψ, namely
• the Ω-subalgebra VP,ψ generated by the set of elements of Vn,r which belong to finite ψ-orbits.
• the Ω-subalgebra VRI,ψ generated by the set of characteristic elements for ψ.
Where there is no ambiguity, we will write VP for VP,ψ and VRI for VRI,ψ .
If u ∈ Vn,r then the ψ-orbit of u is identical to the ψ-orbit of uψ; so u is in a finite ψ-orbit if
and only if uψ is in a finite ψ-orbit. From Lemma 4.21, an element u is a characteristic element
for ψ if and only if uψ is a characteristic element for ψ. Therefore VP,ψ and VRI,ψ are ψ-invariant
subalgebras of Vn,r . (A subalgebra S is ψ-invariant if Sψ = S.) Hence ψP = ψ|VP,ψ is an
automorphism of VP,ψ and ψRI = ψ|VRI,ψ is an automorphism of VRI,ψ .
If ψ and ϕ are conjugate elements of Gn,r and ρ−1 ψρ = ϕ for some conjugator ρ ∈ Gn,r , then
for all Γ ∈ A∗ we have uϕm = uΓ if and only if uρ−1 ψ m ρ = uΓ if and only if (uρ−1 )ψ m = (uρ−1 )Γ.
Thus u is in a finite ϕ-orbit if and only if uρ−1 is in a finite ψ-orbit (taking Γ = ε) and u is a
characteristic element for ϕ if and only if uρ−1 is a characteristic element for ψ (Γ 6= ε). It follows
that the restriction ρ|VP,ψ of ρ to VP,ψ maps VP,ψ isomorphically to VP,ϕ , and similarly ρ|VRI,ψ is
an isomorphism from VRI,ψ to VRI,ϕ .
Now suppose that ψ is in semi-normal form with respect to an A-basis X. Partition X into
XP = XP,ψ = {y ∈ X | y is of type (A)}
and
XRI = XRI,ψ = {y ∈ X | y is of type (B) or (C)}.
Theorem 5.1 ([17, Theorem 9.5]). Let ψ be an element of Gn,r , in semi-normal form with respect
to A-basis X. Then, with the notation above, the following statements hold.
1. Vn,r = VP ∗ VRI , the free product of the ψ-invariant subalgebras VP and VRI .
2. VP = XP hAihλi and VRI = XRI hAihλi; that is, VP (VRI ) is generated by XP (XRI ).
3. Given ψ, ϕ, ρ ∈ Gn,r define six restrictions as follows.
ψP = ψ|VP,ψ

ϕP = ϕ|VP,ϕ

ρP = ρ|VP,ψ

ψRI = ψ|VRI,ψ

ϕRI = ϕ|VRI,ϕ

ρRI = ρ|VRI,ψ

−1
We have ρ−1 ψρ = ϕ if and only if ρ−1
P ψP ρP = ϕP and ρRI ψRI ρRI = ϕRI .

32

Proof. Write WP = XP hAihλi and WRI = XRI hAihλi. As X is the disjoint union of XP and XRI ,
we have Vn,r = WP ∗ WRI , using Lemma 3.11. We shall show that VP = WP and VRI = WRI . By
definition, WP ⊆ VP . If x ∈ XRI is of type (B) then x ∈ VRI , by definition. If x ∈ XRI is of type
(C) then there exists z ∈ XRI , of type (B), and ∆ ∈ A∗ , such that xψ i = z∆. As z ∈ VRI , so is
z∆, and as VRI is ψ-invariant we have x = z∆ψ −i ∈ VRI . Hence WRI ⊆ VRI .
To see that VP ⊆ WP , let u ∈ Vn,r have a finite ψ-orbit. Choose d ∈ N such that, uΓ ∈ XhAi,
for all Γ ∈ A∗ of length d. For each such Γ write uΓ = x∆, where x ∈ X and ∆ ∈ A∗ . As u is in
a finite ψ-orbit so is uΓ, so x ∈ XP and thence uΓ = x∆ ∈ WP . As this holds for all Γ in A∗ of
length d, we have u ∈ WP , by Lemma 3.11. Hence VP ⊆ WP .
To see that VRI ⊆ WRI , we first show that WRI is ψ-invariant. Let Y be the minimal expansion
of X associated to ψ and let x ∈ XRI . Then choose d such that xΓ ∈ Y hAi, for all Γ ∈ A∗ of
length d. Given such a Γ, write xΓ = y∆ for y ∈ Y and ∆ ∈ A∗ . Then xΓψ = yψ∆ ∈ XhAi,
so xΓψ = zΛ, for some z ∈ X and Λ ∈ A∗ . Moreover, z must have type (B) or (C), as x does,
so xΓψ ∈ XRI hAi ⊆ WRI . This holds for all Γ of length d, so again xψ ∈ WRI . It follows that
WRI ψ ⊆ WRI .
Repeating the same argument, using Z = Y ψ instead of Y and ψ −1 instead of ψ gives WRI ψ −1 ⊆
WRI ; so WRI is ψ-invariant as claimed. Now let u ∈ Vn,r be a characteristic element for ψ.
Then, from Lemma 4.24, we have uψ i = xΛ, for some integer i, x ∈ XRI and Λ ∈ A∗ . Thus
u = xΛψ −i ∈ WRI , as WRI is ψ-invariant; and we have VRI ⊆ WRI . This proves 1 and 2 of the
Theorem, and 3 then follows from the discussion preceding the statement of the Theorem.
Note that in the case that ρ−1 ψρ = ϕ in the theorem above we have ρ = ρP ∗ρRI an isomorphism
from VP,ψ ∗ VRI,ψ to VP,ϕ ∗ VRI,ϕ , both of which are isomorphic to Vn,r .
Example 5.2. Let ψ be as in Example 4.5. Then XP = {xα2 α1 , xα22 } and XRI = {xα12 , xα1 α2 }.
Thus ψP is the automorphism of VP = XP hAihλi defined by
xα2 α1 7→ xα22 ,

xα22 7→ xα2 α1 .

Let YRI = {xα13 , xα12 α2 , xα1 α2 } and ZRI = {xα12 , xα1 α2 α1 , xα1 α22 }, both of which are expansions
of XRI . Then ψRI is the automorphism of VRI = XRI hAihλi defined by
xα13 7→ xα12 ,

xα12 α2 7→ xα1 α2 α1 ,

xα1 α2 7→ xα1 α22 .

Theorem 5.1 allows us to decompose the conjugacy problem for (ψ, ϕ) into conjugacy problems
for (ψP , ϕP ) and (ψRI , ϕRI ). Indeed, VP ∼
= Vn,|XRI | , and we regard ψP and
= Vn,|XP | and VRI ∼
ψRI as automorphisms of Vn,|XP | and Vn,|XRI | , respectively. It turns out that ψP and ψRI are each
of particularly simple types; so if we can solve the conjugacy problem for these simple types of
automorphism, then we can solve it in general. In the remainder of this subsection we describe in
detail how this decomposition works.
First consider a single automorphism ψ ∈ Gn,r , where ψ is in semi-normal form with respect
to an A-basis X. As before, we take Vn,r to be the free Vn algebra on a set x of size r, so that X
is an expansion of x. Let XP and XRI be defined as above, let Y be the minimal expansion of X
associated to ψ and let Z = Y ψ. As Y is an expansion of X, for all x ∈ X the set Yx = Y ∩ {x}hAi
is an expansion of {x}, by Lemma 3.16. Therefore YP = Y ∩ XP hAi is an expansion of XP , and
YRI = Y ∩ XRI hAi is an expansion of XRI . Similarly, ZP = Z ∩ XP hAi and ZRI = Z ∩ XRI hAi are
expansions of XP and XRI , respectively. In fact, as ψ permutes the elements of X with type (A),

33

ψP permutes the elements of XP , so XP = YP = ZP . Therefore ψP is an automorphism of
VP = XP hAihλi, which permutes the elements of XP .
For all y ∈ YRI we have yψ = z ∈ Z; moreover z ∈ XRI hAi because VRI is ψ-invariant, so
YRI ψ = ZRI . Now ψRI is an automorphism of VRI , where VRI is freely generated by XRI , and YRI
is the minimal expansion of XRI associated to ψRI (as Y is the minimal expansion of X associated
to ψ). Furthermore YRI ψRI = ZRI and if u is an element of XRI hAi such that uψ ∈ XhAi then
uψ ∈ XhAi ∩ VRI = XRI hAi; so no element of XRI hAi is in an incomplete finite XRI -component
of ψRI .
To summarise, let |XP | = a, |XRI | = b and let XP = {x1 , . . . , xa } and XRI = {xa+1 , . . . , xa+b },
where xi ∈ xhAi. Then, regarding the xi as new generators, we may view VP as Vn,a , the free Vn
algebra on {x1 , . . . , xa }, and VRI as Vn,b , the free Vn algebra on {xa+1 , . . . , xa+b }. We regard ψP
and ψRI as elements of Gn,a and Gn,b , respectively. In this case, ψP (resp. ψRI ) is in quasi-normal
form with respect to the A-basis XP (resp. ψRI ) We write all elements of Y and Z in terms of the
xi , rather than as expansions of elements of x.)
Example 5.3. Let n = 2, r = 1 and V2,1 be free on x = {x}. Let
Y = {xα14 , xα13 α2 , xα12 α2 , xα1 α2 α1 , xα1 α22 , xα2 α1 , xα22 α1 , xα23 }
and
Z = {xα13 , xα12 α2 α1 , xα12 α22 , xα1 α2 α1 , xα1 α22 , xα2 α12 , xα2 α1 α2 , xα22 }
and let ψ be the element of Gn,r determined by the bijection illustrated below.
−→

ψ:

1

2

3

4

5

6

7

8
1

2

3

5

4

6

7

8

Then Y is the minimal expansion of x associated to ψ. The minimal expansion of x contained in
Y hAi ∪ ZhAi is
X = {xα13 , xα12 α2 , xα1 α2 α1 , xα1 α22 , xα2 α1 , xα22 }.
Then XhAi \ (Y hAi ∩ ZhAi) = {xα13 , xα12 α2 , xα2 α1 , xα22 }. The X-components of these elements are
· · · 7→ xα14 7→ xα13

xα12 α2 7→ xα12 α22 7→ · · ·

· · · 7→ xα23 7→ xα22

xα2 α1 7→ xα2 α12 7→ · · · ,

so ψ is in quasi-normal form with respect to X. Introduce new generators x1 = xα13 , x2 = xα12 α2 ,
x3 = xα1 α2 α1 , x4 = xα1 α22 , x5 = xα2 α1 and x6 = xα22 . Then XP = {x3 , x4 } and XRI =
{x1 , x2 , x5 , x6 }.
Let V2,2 be free on {x3 , x4 }. Then, as an element of G2,2 the map ψP is the map sending x3 to
x4 and x4 to x3 . Let V2,4 be free on {x1 , x2 , x5 , x6 }. We have
YRI = {xα14 , xα13 α2 , xα12 α2 , xα2 α1 , xα22 α1 , xα23 } = {x1 α1 , x1 α2 , x2 , x5 , x6 α1 , x6 α2 }
and
ZRI = {xα13 , xα12 α2 α1 , xα12 α22 , xα2 α12 , xα2 α1 α2 , xα22 } = {x1 , x2 α1 , x2 α2 , x5 α1 , x5 α2 , x6 },
so as an element of G2,4 the map ψRI is given by the following forest diagram.
34

ψRI :

x1
1 2

x2

x5

3

4

x6

x1

x2

x5

1
5 6

x6
6

2 3 4 5

Definition 5.4. Let ψ be an element of Gn,r . Then ψ is called periodic if VRI = ∅ and ψ is called
regular infinite if VP = ∅.
Lemma 5.5. Let ψ be an element of Gn,r in semi-normal form with respect to an A-basis X.
1. ψ is periodic if and only if ψ permutes the elements of X.
2. ψ is regular infinite if and only if no element of X is of type (A).
Proof.
1. If ψ permutes the elements of X then X contains no element of type (B) or (C); so
X = XP and Vn,r = VP , by Theorem 5.1. As Vn,r is the free product of VP and VRI it follows
that VRI = ∅, so ψ is periodic.
If ψ is periodic then XRI ⊆ VRI = ∅, so X = XP . Thus X consists of elements of type (A),
which are permuted by ψ, by Lemma 4.18.
2. If ψ is regular infinite then VP = ∅, so Xp = ∅; i.e. no element of X is of type (A). If X
contains no element of type (A) then XP = ∅, and therefore VP = ∅ by Theorem 5.1, so ψ is
regular infinite.
It follows that, in the notation established above Example 5.3, the automorphism ψP ∈ Gn,a is
periodic and ψRI ∈ Gn,b is regular infinite. Thus, the decomposition of Theorem 5.1 may be viewed
as factoring ψ into a product of a periodic and a regular infinite automorphism. It remains to see
how to regard a pair of automorphisms in this way, simultaneously in the same algebra.
To this end suppose that ψi ∈ Gn,ai is in semi-normal form with respect to an A-basis Xi , where
|Xi | = ai , for i = 1, 2. If there exists an isomorphism ρ : Vn,a1 → Vn,a2 with the property that
ρ−1 ψ1 ρ = ψ2 then, from Corollary 3.14, a1 ≡ a2 mod n − 1. Also, if a1 ≡ a2 mod n − 1 then Vn,ai
is isomorphic to Vn,s where 1 ≤ s ≤ n−1 and s ≡ ai . If this is the case then we may take an A-basis
xs of s elements of Vn,s and choose expansions X10 and X20 of xs of a1 and a2 elements respectively.
Now let fi be the map taking Xi to Xi0 . Then there exists an isomorphism ρ : Vn,a1 → Vn,a2 such
that ρ−1 ψ1 ρ = ψ2 if and only if a1 ≡ a2 mod n − 1 and, setting ψbi = fi−1 ψi fi ∈ Gn,s , we have
ρ−1 f1 ψb1 f1−1 ρ = f2 ψb2 f2−1 : that is θ−1 ψb1 θ = ψb2 , where θ = f1−1 ρf2 ∈ Gn,s . (See Figure 5.1.1.)
Combining this with Theorem 5.1.1 gives a decomposition of the conjugacy problem into the
conjugacy problem for periodic and for regular infinite elements, separately. Let ψ and ϕ be elements
of Gn,r , write Vn,a1 = VRI,ψ , ψ1 = ψRI , Vn,a2 = VRI,ϕ and ψ2 = ϕRI . Using the procedure above,
if ρRI exists (in the notation of Theorem 5.1) then we may regard ψi , i = 1, 2, as a regular infinite
element of Gn,s , namely ψbi , for appropriate s. Similarly, we may regard ψP and ϕP as periodic
automorphisms of a single algebra.
We can now outline the algorithm for the conjugacy problem.

5.2

The conjugacy algorithm

Algorithm 5.6. Let ψ and ϕ be an elements of Gn,r .

35

ψ1

Vn,a1

Vn,a1

f1
f1

Vn,s
ρ

b1
ψ

θ

Vn,s

Vn,s
ρ

θ
b2
ψ

Vn,s

f2
f2

Vn,a2

ψ2

Vn,a2

Figure 5.1.1: Isomorphisms of Vn,ai and Vn,s
Step 1: Find A-bases Xψ and Xϕ such that ψ and ϕ are in quasi-normal form with respect to
Xψ and Xϕ , respectively, as in Lemma 4.28. The sets XP,ψ , XRI,ψ , XP,ϕ and XRI,ϕ are
obtained as part of this process.
If |XP,ψ | ≡ |XP,ϕ | mod n − 1 and |XRI,ψ | ≡ |XRI,ϕ | mod n − 1; continue. Otherwise
output “No” and stop.
Step 2: Find the minimal expansion Yψ of Xψ associated to ψ and the minimal expansion Yϕ of
Xϕ associated to ϕ. (See Lemma 4.3.) Construct YRI,ψ and YRI,ϕ ; the sets elements of
Yψ and Yϕ which are not in finite orbits (as in the the discussion following Theorem 5.1).
Construct ZRI,ψ = YRI,ψ ψ and ZRI,ϕ = YRI,ϕ ϕ.
Step 3: For T = P and for T = RI carry out the following. Find the integer sT such that
1 ≤ sT ≤ n−1 and sT ≡ |XT,ψ |. Let xT be a set of sT elements, let Vn,sT be free on xT and
find expansions WT,ψ and WT ϕ of xT of sizes |XT,ψ | and |XT,ϕ |, respectively. Construct a
map fT,ψ mapping XT,ψ bijectively to WT,ψ and fT,ϕ mapping XT,ϕ bijectively to WT,ϕ .
Write ψT and ϕT as elements of Gn,sT , using these maps.
Step 4: Input ψP and ϕP into Algorithm 5.13 below for conjugacy of periodic elements of Gn,r .
If ψP and ϕP are not conjugate, return “No” and stop. Otherwise obtain a conjugating
element ρP .
Step 5: Input ψRI and ϕRI into Algorithm 5.27 below for conjugacy of regular infinite elements
of Gn,sRI . If ψRI and ϕRI are not conjugate, return “No” and stop. Otherwise obtain a
conjugating element ρRI .
Step 6: Return the conjugating element ρP ∗ ρRI .
Given this algorithm we have the following theorem.
Theorem 5.7 ([17, Theorem 9.3]). The conjugacy problem is soluble in Gn,r .
Proof. Apply Algorithm 5.6.

36

5.3

Conjugacy of periodic elements

Let ψ ∈ Gn,r be a periodic element. For u ∈ Vn,r the size of the ψ-orbit of u is the least positive
integer d such that uψ d = u.
Definition 5.8. Let ψ be a periodic element of Gn,r in semi-normal form with respect to the
A-basis X. The cycle type of ψ is the set
Tψ (X) = {d ∈ N | some x ∈ has a ψ-orbit of size d}.
For d ∈ N, define the ψ-multiplicity of d to be mψ (d, X) = D/d, where D is the number of elements
of X which belong to a ψ-orbit of size d.
Note that, as ψ is periodic and in semi-normal form with respect to X, all X-components of
ψ are (ordered) ψ-orbits and all ψ-orbits of elements of XhAi are X-components (once ordered
appropriately). Also, d ∈ Tψ (X) if and only if mψ (d, X) 6= 0; the size of the set X is |X| =
P
d∈Tψ (X) dmψ (d, X); if d ∈ Tψ (X) then X contains mψ (d, X) disjoint ψ-orbits of size d; and ψ is
a torsion element of order equal to the least common multiple of elements of Tψ (X).
Example 5.9. Let n = 2, r = 1 and V2,1 be free on x = {x}. Let
X = {xα13 , xα12 α2 , xα1 α2 , xα2 α12 , xα2 α1 α2 , xα22 α1 , xα23 }
and let ψ be the periodic element of G2,1 defined by the tree pair diagram below.
−→

ψ:
1

2

3

4

5

6

3

7

1

2

5

4

7

6

Then the cycle type of ψ is {2, 3} with multiplicites mψ (2, X) = 2 and mψ (3, X) = 1.
Lemma 5.10. Let ψ be a periodic element of Gn,r in semi-normal form with respect to the Abasis X and the A-basis Z, where Z is a q-fold expansion of X. Then Tψ (X) = Tψ (Z) and
mψ (d, X) ≡ mψ (d, Z) mod n − 1, for all d ∈ Tψ (X).
Proof. It suffices to prove the lemma in the case where Z is a simple expansion of X, because any
expansion is obtained by a finite sequence of simple expansions. Suppose the expansion happens
at w ∈ X, so that Z = (X \ {w}) ∪ {wα1 , . . . , wαn }. To compute Tψ (Z) we need to break Z into a
union of ψ-orbits.
Let d be the size of the ψ-orbit of w, so that Ow = {w, wψ, . . . , wψ d−1 }. For each 1 ≤ i ≤ n
the orbit of wαi is Owαi = {wαi , wψαi , . . . , wψ d−1 αi }, which is of size at most d. In fact its size is
exactly d: if there are integers 0 ≤ j < k < d for which wψ j αi = wψ k αi , we would have wψ j = wψ k ,
which cannot occur.
Thus, in moving from X to Z we have lost 1 and gained n ψ-orbits of size d; all other ψ-orbits
inside Z are ψ-orbits inside X. Therefore Tψ (X) = Tψ (Z). In terms of multiplicities this means
mψ (d, Z) = mψ (d, X) + n − 1 and mψ (e, Z) = mψ (e, X), for every positive integer e 6= d; whence
the result.
Note that it follows from this lemma that if ψ is in semi-normal form with respect to both X
and X 0 then Tψ (X) = Tψ (X 0 ), since we may take a common expansion of both X and X 0 and then
expand this to an A-basis Z with respect to which ψ is in semi-normal form. So from now on, we
refer to the cycle type Tψ without reference to an A-basis X.
37

Proposition 5.11. Let ψ and ϕ be periodic elements of Gn,r in semi-normal form with respect to
the A-bases Xψ and Xϕ , respectively. Then ψ is conjugate to ϕ if and only if
1. Tψ = Tϕ and
2. mψ (d, Xψ ) ≡ mϕ (d, Xϕ ) mod n − 1, for all d ∈ N.
Proof. Assume that ψ and ϕ are conjugate and let ρ ∈ Gn,r be such that ρ−1 ψρ = ϕ. Let ρ be
in semi-normal form with respect to Xρ , let Y be the minimal expansion of Xρ associated to ρ
and let Z = Y ρ. Let W be a common expansion of Xψ and Y and let ψ be in semi-normal form
with respect to an expansion Xψ0 of W . (Such an expansion of W exists, by Lemma 4.9.) As ψ
is periodic and in semi-normal form it permutes the elements of Xψ0 , so for all x ∈ Xψ0 we have
x0 ∈ Xψ0 such that xρϕ = xψρ = x0 ρ ∈ Xρ. Therefore ϕ permutes the elements of Xψ0 ρ, so ϕ is in
semi-normal form with respect to Xϕ0 = Xψ0 ρ. As Xψ0 is an expansion of Y and Z = Y ρ it follows
that Xϕ0 is an expansion of Z.
Now if x ∈ Xψ0 and i ∈ Z then xρϕi = xψ i ρ, so we have xψ d = x if and only if xρϕd = xρ; in
other words, x and xρ have orbits of equal size. This applies to any x, so Tψ = Tϕ and both Xψ0 and
Xϕ0 have the same number of elements with an orbit of size d. Therefore mψ (d, Xψ0 ) = mϕ (d, Xϕ0 ),
for all d ∈ Tψ = Tϕ . Statement 2 follows, from Lemma 5.10 and the fact that Xψ0 and Xϕ0 are
expansions of Xψ and Xϕ , respectively.
Conversely, suppose that statements 1 and 2 hold. Let Tψ = Tϕ = {d1 , . . . , dk } and write
mj = mψ (dj , Xψ ) and m0j = mϕ (dj , Xϕ ). Fix j ∈ {1, . . . , k}. Assume first that mj > m0j . Then,
by hypothesis, mj = m0j + qj (n − 1) for some positive integer qj . Select an element x ∈ Xϕ whose
ϕ-orbit Ox has size dj . Let Yx be a qj -fold expansion of {x} and set E = {Γ ∈ A∗ | xΓ ∈ Yx }, so
that Yx = xE. Then for each 0 ≤ i < dj , xϕi E is a qj -fold expansion of {xϕi }.
For every string Γ ∈ E, the set {xΓ, xϕΓ, . . . , xϕd−1 Γ} is a ϕ-orbit of size d. (We saw this in
Lemma 5.10 for Γ = αi .) Hence the set Ox E = {xϕi Γ | Γ ∈ E, 0 ≤ i < dj } is a qj dj -fold expansion
of Ox ; more precisely it is a disjoint union of |E| = qj (n − 1) ϕ-orbits of size dj . After Ox is
expanded to Ox E, the resulting expansion Xϕ has exactly m0j + qj (n − 1) = m0j size dj ϕ-orbits.
For each j such that mj > m0j apply this process to a single element of Xϕ with ϕ-orbit size dj .
Dually, for each j such that m0j > mj apply the process to an element of Xψ with ψ-orbit size dj ,
interchanging the roles of ϕ and ψ. The result is an expansion Xψ0 of Xψ and an expansion Xϕ0 of
Xϕ such that mϕ (d, Xϕ0 ) = mψ (d, Xψ0 ) for every positive integer d.
Now define ρ : Xψ0 → Xϕ0 by mapping orbits of size d to each other, preserving the order within
each orbit. In detail, for each d set m = mψ (d, Xψ ) = mϕ (d, Xϕ ). Let O1 , . . . , Om be the size d
0
be the size d ϕ-orbits in Xϕ0 (also in any order).
ψ-orbits (in any order) in Xψ0 and let O10 , . . . , Om
0
0
Select a representative oi ∈ Oi and oi ∈ Oi for each of these 2m orbits. We define ρ by the rule
oi ψ j ρ = o0i ϕj . By construction we have xψρ = xρϕ, for all x ∈ Xψ0 . Hence ρ−1 ψρ = ϕ.
Example 5.12. Let n = 2, r = 1 and V2,1 be free on x = {x}. Let
X = {xα14 , xα13 α2 , xα12 α2 , xα1 α2 , xα2 α1 , xα22 }
and let ψ be the periodic element of G2,1 given by the tree pair diagram below.
−→

ψ:
1

2

3

4

5

6
2
38

1

4

3

6

5

Then ψ has cycle type Tψ = {2} and multiplicity mψ (2, X) = 3. The ψ-orbits of elements of X are
O1 = {xα14 , xα13 α2 }, O2 = {xα12 α2 , xα1 α2 } and O3 = {xα2 α1 , xα22 }.
Let Y = {xα1 , xα2 } and let ϕ be the periodic element of G2,1 which swaps the elements of Y .
ϕ:

1

2 −→ 2

1

Then ϕ has cycle type Tϕ = {2} and mϕ (2, Y ) = 1. From Proposition 5.11, ψ is conjugate to ϕ. We
can construct a conjugator by applying the process of the proof. We take the same 2-fold expansion
of both xα1 and xα2 to give a 4-fold expansion
Y 0 = {xα13 , xα12 α2 , xα1 α2 , xα2 α12 , xα2 α1 α2 , xα22 }
of Y such that ϕ is in semi-normal form with respect to Y 0 . The ϕ-orbits of elements of Y 0 are
O10 = {xα13 , xα2 α12 }, O20 = {xα12 α2 , xα2 α1 α2 } and O30 = {xα1 α2 , xα22 }, so mϕ (2, Y 0 ) = 3. Take
the representative of each orbit to be the first element listed in its description. The corresponding
conjugator ρ is the element of G2,1 which sends Oi to Oi0 via xα14 ρ = xα13 , xα13 α2 ρ = xα2 α12 ,
xα12 α2 ρ = xα12 α2 , xα1 α2 ρ = xα2 α1 α2 , xα2 α1 ρ = xα1 α2 and xα22 ρ = xα22 .
−→

ρ:
1

2

3

4

5

6
1

3

5

2

4

6

Then ρ−1 ψρ = ϕ.
From the proof of Theorem 5.11 we extract the following algorithm for the conjugacy of periodic
elements of Gn,r .
Algorithm 5.13. Let ψ and ϕ be periodic elements of Gn,r .
Step 1: Construct A-bases Xψ and Xϕ with respect to which ψ and ϕ are in semi-normal form
(Lemma 4.9).
Step 2: Compute the cycle types Tψ and Tϕ . If Tψ 6= Tϕ , output “No” and stop.
Step 3: Compute mψ (d, Xψ ) and mϕ (d, Xϕ ), for all d ∈ Tψ . If mψ (d, Xψ ) 6≡ mϕ (d, Xϕ ) mod n−1,
output “No” and stop.
Step 4: Construct A-bases Xψ0 and Xϕ0 as described in the proof of Theorem 5.11.
Step 5: Choose a map ρ sending ψ-orbits of elements of Xψ0 to ϕ-orbits of elements of Xϕ0 , as in
the proof of the theorem, and output ρ.

5.4

Conjugacy of regular infinite elements

We begin with a necessary condition for two regular infinite elements to be conjugate. Let ψ
be a regular infinite element of Gn,r in semi-normal form with respect to X. By Lemma 4.6, ψ
has finitely many semi-infinite X-components, each of which has a characteristic element u with
some characteristic (m, Γ) (see Definition 4.22). If ψ is also in semi-normal form with respect
to Y , the ψ-orbit of u has precisely one Y -component, which is again semi-infinite of characteristic
(m, Γ). Therefore, the set of pairs (m, Γ) which are characteristics of semi-infinite X-components
is independent of the choice of a basis for a semi-normal form. With this in mind, we make the
following definition.
39

Definition 5.14. Let ψ be a regular infinite element of Gn,r in semi-normal form with respect to
X. Define
Mψ = {(m, Γ) | (m, Γ) is the characteristic of a semi-infinite X-component of ψ}.
Example 5.15. We refer to the following example through the remainder of this section. Let
n = 2, r = 1, x = {x} and ϕ ∈ G2,1 be determined by the bijection from A-basis
Y = {xα1 , xα2 α1 , xα22 α12 , xα22 α1 α2 , xα23 }
to the A-basis
Z = {xα13 , xα12 α2 , xα1 α2 , xα2 α1 , xα22 }
as illustrated below.
−→

ϕ:
1
2
3

4

1

5

2

4

5

3

Then Y is the minimal expansion of x associated to ϕ and Z = Y ϕ. The elements of xhAi \ (Y hAi ∪
ZhAi) are x and xα2 , so we start the search for a quasi-normal form by taking the unique minimal
expansion X = {xα1 , xα2 α1 , xα22 } of x not containing either of these elements.
The X-component of xα1 is
xα1 7→ xα13 7→ xα15 7→ · · · ,
which is right semi-infinite of characteristic (1, α12 ). Next, xα2 α1 belongs to a complete infinite
X-component:
· · · xα25 7→ xα24 7→ xα23 7→ xα2 α1 7→ xα12 α2 7→ xα14 α2 7→ xα16 α2 7→ · · ·
Finally, the X-component of xα22 is
· · · 7→ xα22 α14 7→ xα22 α12 7→ xα22 ,
which is left semi-infinite of characteristic (−1, α12 ). Thus ϕ is in quasi-normal form with respect
to X.
To determine Mϕ , we compute the sets XhAi \ Y hAi = {xα22 , xα22 α1 } and XhAi \ ZhAi =
{xα1 , xα12 }. The X-components we have yet to calculate are those of xα22 α1 and xα12 ; these are the
sets {xα22 α12i−1 | i ≥ 1} and {xα12i | i ≥ 1} with characteristics (1, α12 ) and (−1, α12 ) respectively.
Hence
Mϕ = {(1, α12 ), (−1, α12 )}.
Lemma 5.16. Let ψ and ϕ be regular infinite elements of Gn,r in semi-normal form with respect
to A-bases X and Y respectively. Suppose that the elements are conjugate via ρ ∈ Gn,r with
ρ−1 ψρ = ϕ. Then the sets Mψ and Mϕ coincide. Moreover, ρ maps a semi-infinite X-component of
ψ into a ϕ-orbit which contains a (unique) semi-infinite Y -component with the same characteristic.
Proof. If u is an element of XhAi such that uψ m = uΓ, for some m and Γ, then
uρϕm = uψ m ρ = uΓρ = uρΓ.
40

The same argument can be applied starting with an element v ∈ Y hAi and interchanging ψ and
ϕ. Hence if u belongs to a ψ-orbit of characteristic (m, Γ) then uρ belongs to an ϕ-orbit of characteristic (m, Γ). Thus, from Lemma 4.24, a ψ-orbit that contains a semi-infinite X-component
of characteristic (m, Γ) is mapped by ρ to a ϕ-orbit which has a semi-infinite Y -component of the
same characteristic.
Definition 5.17. Let ψ be in semi-normal form with respect to X. The equivalence relation ≡
on X, is that generated by the relation x ≡ x0 , whenever xΓ and x0 ∆ are in the same ψ-orbit, for
some Γ, ∆ ∈ A∗ .
Example 5.18. Let ϕ be as in Example 5.15. Then xα2 α1 ϕ = (xα1 )α1 α2 , so xα2 α1 ≡ xα1 . Also,
xα2 α1 ϕ−1 = (xα22 )α2 , so xα2 α1 ≡ xα22 . Therefore all elements of X are related by ≡.
Proposition
`m 5.19. Let ψ be a regular infinite element in semi-normal form with respect to X.
Let X = i=1 Xi , where the Xi are the equivalence classes of ≡ defined on X under the action
of ψ. Then Vn,r is the free product of the ψ-invariant Ω-subalegbras V1 , . . . , Vm , where Vi is the
Ω-subalgebra generated by Xi .
Proof. As ψ is regular infinite, the sets Xi partition X, so Vn,r is the free product of the Vi ’s. To
show that Vi is ψ-invariant it suffices to show that if x ∈ Xi then xψ and xψ −1 are in Vi . To this
end, choose d ≥ 0 such that xψΓ and xψ −1 Γ belong to XhAi, for all Γ ∈ A∗ of length d. Then for
all such Γ we have xψΓ = y∆ and xψ −1 Γ = zΛ, for some y, z ∈ X and ∆, Λ ∈ A∗ . By definition
then y ≡ x ≡ z, so x, y, z ∈ Xi . This implies that xψΓ = y∆ ∈ Vi and xψ −1 Γ = zΛ ∈ Vi . This
holds for all Γ of length d, so from Lemma 3.20, xψ and xψ −1 belong to Vi , as required. Hence Vi
is ψ-invariant.
Lemma 5.20. Let ψ be a regular infinite element in semi-normal form with respect to X and let
Xi , i = 1, . . . , m, be the equivalence classes of ≡ defined on X under the action of ψ. We may
effectively construct the Xi .
Proof. From Lemmas 4.28 and 4.3, we may effectively construct X, the minimal expansion Y of
ψ with respect to X, and the basis Z = Y ψ. For each v ∈ X ∪ Y ∪ Z we may enumerate a
finite subsequence Cv of the X-component of v using the procedure of Lemma 4.28. Let ≡0 be the
equivalence relation on X generated by y ≡0 z if yΓ and z∆ belong to Cv , for some v ∈ X ∪ Y ∪ Z
and Γ, ∆ ∈ A∗ . We claim that ≡0 = ≡.
By definition, ≡0 ⊆≡. To prove the opposite inclusion, we suppose that there exist p ∈ Z,
x, y ∈ X and ∆, Φ ∈ A∗ such that xΦ = y∆ψ p and x and y are not related under the relation
≡0 . In this case we may assume, interchanging x and y if necessary, that p > 0. Let p be a
0
minimal positive integer for which such x, y exist. As y∆ψ p = xΦ it follows that y∆ψ p ∈ XhAi,
0
0 0
0 0 p−1
0
for p = 1, . . . , p − 1. Let y∆ψ = y ∆ , so y ∆ ψ
= xΦ. By minimality of p we have y ≡0 x.
Let ∆0 be an initial subword of ∆ of maximal length such that y∆0 ψ ∈ XhAi, say ∆ = ∆0 ∆1 .
Then y∆0 ∈ Y and y∆0 ψ = y 00 ∆000 , for some y 00 ∈ X and ∆000 ∈ A∗ . Now y 0 ∆0 = y∆0 ∆1 ψ =
y 00 ∆000 ∆1 , so y 00 = y 0 and ∆0 = ∆000 ∆1 . Thus y∆0 ψ = y 0 ∆000 and, as y∆0 ∈ Y , y 0 ∆000 ∈ Z we have
y ≡0 y 0 . Therefore y ≡0 x, a contradiction. We conclude that no such p, x and y exist and so
≡⊆≡0 , as required. Thus ≡0 =≡, and as we may effectively compute the sets Cv , it follows that we
may compute the equivalence classes Xi .

41

Lemma 5.21. Let ψ be a regular infinite element in semi-normal form with respect to X and let
Xi , i = 1, . . . , m be the equivalence classes of ≡ defined on X under the action of ψ. Define

xψ if x ∈ Xi ,
xθi =
x if x ∈ Xj for i 6= j,
for i = 1, . . . , m. Then θi extends to an element of Gn,r which commutes with ψ and with θj , for
all j = 1, . . . , m.
Proof. Let Vi be the Ω-subalgebra generated by Xi , i = 1, . . . , m. Since Vn,r = V1 ∗ · · · ∗ Vm and the
Vi are ψ invariant, we have ψ = ψ1 ∗ · · · ∗ ψm , where ψi = ψ|Vi . Moreover ψi is an automorphism of
Vi . By definition, ψi |Xi = ψ|Xi = θi |Xi , so θi |Xi extends to the automorphism ψi of Vi . Thus (the
extension to Vn,r of) θi = 1V1 ∗ · · · ∗ ψi ∗ · · · ∗ 1Vm is an automorphism of Vn,r . For i < j we have
θi θj = 1V1 ∗ · · · ∗ ψi ∗ · · · ∗ ψj · · · ∗ 1Vm = θj θi , and it follows that θi commutes with ψ.
Lemma 5.22. Let ψ and ϕ be regular infinite elements of Gn,r , in semi-normal form with respect
to the A-bases X and Y respectively. Let X1 , . . . , Xm be the equivalence classes of ≡ defined on
X under the action of ψ. Choose a representative xi ∈ Xi of type (B) for each i. If ψ and ϕ are
conjugate, there exists a conjugator ρ such that xi ρ is a terminal or initial element in a semi-infinite
Y -component of ϕ.
Proof. Let ρ0 ∈ Gn,r be a conjugator with ρ0−1 ψρ0 = ϕ. We will explain how to modify ρ0 to
form another conjugator ρ satisfying the requirements of the lemma. Lemma 5.16 asserts that xi ρ0
belongs to a ϕ-orbit containing a semi-infinite Y -component, which has the same characteristic as
xi . Let yi ∈ Y hAi be the initial or terminal element of this Y -component. Then there exists ji such
that xi ρ0 = yi ϕji , meaning that
yi = yi ϕji ϕ−ji = xi ρ0 ϕ−ji = xi ψ −ji ρ0 .
For each equivalence class Xi , define θi as in Lemma 5.21 and ρ ∈ Gn,r by
!
n
Y
−ji
ρ=
θi
ρ0 .
i=1

Then θ = i=1 θi−ji commutes with ψ, so ρ−1 ψρ = ρ0−1 θ−1 ψθρ0 = ρ0−1 ψρ0 = ϕ; furthermore for
each chosen xi ∈ Xi we have
!
n
Y
−ji
xi ρ = xi
θi
ρ0 = xi θi−ji ρ0 = xi ψ −ji ρ0 = yi .
Qn

i=1

Thus ρ is the required conjugator.
Definition 5.23. Let ψ and ϕ be regular infinite elements in semi-normal form with respect to X
and Y and let X1 , . . . , Xm , be the equivalence classes of ≡ defined on X under the action of ψ.
We define Ri (ψ, ϕ) to be the set of pairs (x, y), where x ∈ Xi is of type (B) and y is an initial or
terminal element of a semi-infinite Y -component of ϕ with the same characteristic as x.
Given a choice of elements (xi , yi ) ∈ Ri (ψ, ϕ) for each 1 ≤ i ≤ m, let ρ0 be the map from
{x1 , . . . , xm } to {y1 , . . . , ym } given by xi ρ0 = yi for each i. We define R(ψ, ϕ) to be the set of all
such maps ρ0 constructed in this way.
42

The set Ri (ψ, ϕ) is finite since the number of elements of type (B) in X and the number of
semi-infinite Y -components of ϕ is finite, so R(ψ, ϕ) is also finite.
Lemma 5.24. Given ρ0 ∈ R(ψ, ϕ), there are finitely many ways of extending ρ0 to an element
ρ of Gn,r such that ϕ = ρ−1 ψρ. Moreover the existence of such an extension ρ can be effectively
determined, and if such ρ exists then the images yρ can be effectively determined, for all y ∈ X.
Proof. Throughout the proof, when we say ρ exists we mean that an extension ρ of ρ0 to an
element of Gn,r exists and satisfies ϕ = ρ−1 ψρ. From Lemma 5.20, we may effectively construct the
equivalence classes Xi , and so also the sets Ri (ψ, ϕ). First consider a single equivalence class Xi . We
are given a representative element xi ∈ Xi of type (B) and an element yi such that xi ρ0 = yi , where
yi is an initial or terminal element of a semi-infinite Y -component of ϕ with the same characteristic
as xi .
Let x ∈ X of type (B). Then, by definition of ≡, we have x ∈ Xi if and only if there exist
elements xi = u0 , . . . , ut = x of X, elements Γj , ∆j ∈ A∗ and kj ∈ Z with uj+1 ∆j+1 = uj Γj ψ kj ,
for j = 0, . . . , t − 1. Before going any further, we show that we may assume that uj is of type (B),
for all j. Suppose not, say uj is of type (C). Then, by Lemma 4.18, there exist kj0 ∈ Z, Γ0j ∈ A∗
0
and u0j ∈ X of type (B) such that uj ψ kj = u0j Γ0j . Now
0

0

uj−1 Γj−1 ψ kj−1 +kj = uj ∆j ψ kj = u0j Γ0j ∆j
and

0

0

u0j Γ0j Γj ψ kj −kj = u0j Γ0j ψ −kj Γj ψ kj = uj Γj ψ kj = uj+1 ∆j+1 ,
so we may replace uj by u0j . Continuing this way, eventually all uj will be of type (B).
We show, by induction on t, that there are finitely many possible values of xρ, for a conjugator
ρ ∈ Gn,r such that xϕ = xρ−1 ψρ which extends ρ0 . (That is, where xi ρ = xi ρ0 = yi .) We also
describe an effective procedure to enumerate the set of all such elements. Suppose first that t = 1,
so x = u1 and we have Γ = Γ0 , ∆ = ∆1 and k = k0 such that xi Γψ k = x∆. Given that ρ exists,
from Lemma 5.16, xρ belongs to a semi-infinite Y -component C of ϕ with the same characteristic
as x. Therefore (if ρ exists) there exists an element (x, w) ∈ Ri (ψ, ϕ) such that w is the initial or
terminal element of C, as well as an integer l such that wϕl = xρ. This implies that
w∆ϕl = (x∆)ρ = xi Γψ k ρ = xi Γρϕk = xi ρ0 ϕk Γ,
so
w∆ϕl−k = xi ρ0 Γ = yi Γ.

(12)

Lemma 4.34 gives an effective procedure to determine whether an integer l satisfying (12) exists,
and if so find it. Given ρ0 and x, the integer k and the elements Γ and ∆ are uniquely determined
so, to decide whether an appropriate value xρ exists, we may check each pair (x, w) in the set
Ri (ψ, ϕ) to see if (12) holds for some l or not. For each such w there is at most one l such that
(12) has a solution and, as Ri (ψ, ϕ) is finite, we may effectively enumerate the values w∆ϕl−k that
could be assigned to xρ. Hence the result holds if t = 1.
Now assume that t > 1 and the result holds for all x related to xi by a chain of length at most
t − 1. Then ut−1 is of type (B) and by assumption ut−1 ρ may be given one of finitely many values,
and we have a procedure to enumerate these values. Suppose then that ut−1 ρ = v. Now x = um
and we have Γt−1 , ∆t ∈ A∗ and kt−1 ∈ Z such that ut−1 Γt−1 ψ kt−1 = x∆t . Applying the argument
43

of the case m = 1 with ut−1 , Γt−1 , ∆t and v in place of xi , Γ, ∆ and y, we see that a finite set of
possible values for xρ may be effectively determined. Therefore, by induction, the result holds for
all x ∈ Xi of type (B).
Finally, if x ∈ Xi is of type (C), then by Lemma 4.18 there is a zΣ in the X-component of x, for
some z of type (B) and Σ ∈ A∗ , i.e. xψ p = zΣ for some integer p. Since we have already determined
the possible images of all the type (B) elements in Xi , if ρ exists we have, for each choice of zρ,
xρ = zΣψ −p ρ = zρΣϕ−p
and this determines the image of the type (C) element under ρ (uniquely once we have made our
initial choice for the image of zρ).
We carry out this process on each equivalence class in turn. If the process results in at least one
possible value for each element of X, we obtain a potential extension ρ of ρ0 . For such a ρ to be a
genuine extension, we need to check if ρ defines an automorphism of Vn,r . This is the case if and
only if the image Xρ of the A-basis X is itself a basis for Vn,r , which we can effectively determine
using Lemma 3.16. (Note that Xρ need not be an A-basis—see Example 5.26 below.)
We are now able to state the main result of this section.
Proposition 5.25. Let ψ and ϕ be regular infinite elements of Gn,r in quasi-normal form with
respect to X and Y respectively. Then ψ is conjugate to ϕ if and only if there exists a map
ρ0 ∈ R(ψ, ϕ) which extends to an element ρ of Gn,r with ρ−1 ψρ = ϕ.
Proof. If ρ0 extends to an element ρ ∈ Gn,r with ρ−1 ψρ = ϕ, then ψ is certainly conjugate to ϕ.
Assume that ψ is conjugate to ϕ. Lemma 5.22 tells us that there exists a conjugator ρ such
that, for each equivalence class Xi , there exists an element xi of type (B) in Xi with yi = xi ρ
an initial or terminal element of a semi-infinite Y -component of ϕ. We define ρ0 to be the map
x1 7→ y1 , . . . , xm 7→ ym , where yi = xi ρ for each i = 1, . . . , m. Thus, ρ0 is an element of the finite set
R(ψ; ϕ). Now ρ0 is the restriction of ρ to {x1 , . . . , xm }, so it certainly extends to ρ, as required.
Example 5.26. Let n = 2, r = 1 and V2,1 be free on x = {x}. Let
Y = {xα1 , xα2 α12 , xα2 α1 α2 , xα22 }

and Z = {xα13 , xα12 α2 , xα1 α2 , xα2 }

determine the automorphism ψ as illustrated below.
−→

ψ:
1
2

3

4

1

3

4

2

Then Y is the minimal expansion of x associated to ψ and Z = Y ψ. The only element of xhAi
not in Y hAi ∪ ZhAi is x, so we take X = {xα1 , xα2 } to be our candidate basis for a quasi-normal
form. Then XhAi \ Y hAi = {xα2 , xα2 α1 } and XhAi \ ZhAi = {xα1 , xα12 }. The X-components of
the first two elements are
xα2 α1 ∈ {xα2 α12k+1 }k≥0 ,

xα2 ∈ {xα2 α12k }k≥0

both left semi-infinite with characteristic (−1, α12 ). The latter two elements’ X-components are
xα1 ∈ {xα12k+1 }k≥0

xα12 ∈ {xα12k+2 }k≥0 ,
44

both right semi-infinite with characteristic (1, α12 ). Hence ψ is in quasi-normal form with respect
to X, both elements of X are of type (B) and Mψ = {(1, α12 ), (−1, α12 )}. As (xα2 )α2 ψ = (xα1 )α2
there is one equivalence class of ≡, that is X1 = X.
Let ϕ be automorphism of Examples 5.15 and 5.18. Then ϕ is in quasi-normal form with respect
to the A-basis Xϕ = {xα1 , xα2 α1 , xα22 } and Mϕ = Mψ . The initial elements of right semi-infinite
Xϕ -components are xα1 and xα12 and the terminal elements of left semi-infinite Xϕ -components
are xα22 and xα22 α1 .
The set R1 (ψ, ϕ) consists of the pairs (xα1 , xα1 ), (xα1 , xα12 ), (xα2 , xα22 ) and (xα2 , xα22 α1 ). Let
us choose xα1 as our type (B) representative in X1 . We have two choices for the image of xα1 under
ρ0 , corresponding to the two pairs (xα1 , xα1 ), (xα1 , xα12 ) ∈ R1 . Denote these by ρ1 and ρ2 , where
xα1 ρ1 = xα1 and xα1 ρ2 = xα12 .
Next we determine the images of the other type (B) element xα2 of X under the action of ρ1 and
ρ2 , following the proof of Lemma 5.24.
As noted above, xα1 ≡ xα2 because (xα1 )α2 ψ −1 = (xα2 )α2 , so in the notation of the proof of
Lemma 5.24 we have Γ = α2 , ∆ = α2 and k = −1. Substituting these values into equation (12),
we wish to find l such that
wα2 ϕl+1 = (xα1 )ρi α2 ,
where i = 1 or 2, and w = xα22 or xα22 α1 . Whenever we find such an l then we set xα2 ρi = wϕl
and check to see if ρi determines an automorphism. If so, we check if ρi is a conjugator i.e. if
ρ−1
i ψρ = ϕ.
Case i = 1: xα1 ρ1 = xα1 .
(i) When w = xα22 we have
xα23 ϕl+1 = xα1 α2

⇐⇒

xα2 α1 ϕl = xα1 α2 ,

which has no solutions, as may be verified using the process of Lemma 4.34.
(ii) When w = xα22 α1 we have
xα22 α1 α2 ϕl+1 = xα1 α2

xα1 α2 ϕl = xα1 α2 ,

⇐⇒

which has solution l = 0. Therefore we set xα2 ρ1 = xα22 α1 . Now ρ1 now maps X to
{xα1 , xα22 α1 }, which is not a basis of V2,1 (see Lemma 3.16). So the set map ρ1 extends
to an endomorphism which is not an automorphism of V2,1 .
Neither value of w results in a potential conjugator ρ1 .
Case i = 2: xα1 ρ2 = xα12 .
(i) When w = xα22 we have
xα23 ϕl+1 = xα12 α2

⇐⇒

xα2 α1 ϕl = xα12 α2

which has solution l = 1. Therefore we set
xα2 ρ2 = xα22 ϕ
= (xα22 α12 )(xα22 α1 α2 )λ(xα23 )λϕ
= (xα22 α12 ϕ)(xα22 α1 α2 ϕ)λ(xα23 ϕ)λ
= (xα22 )(xα1 α2 )λ(xα2 α1 )λ
45

(13)

In this case xα22 is in Xϕ hAi \ W hAi, where W is the minimal expansion associated to
ϕ; this is why the standard form of xα2 ρ2 is written using contraction operations λ.
To define ρ2 in terms of XhAi, we must take an expansion of X at xα2 . We
take the minimal expansion which allows us to define the map into xhAi; namely
{xα2 α12 , xα2 α1 α2 , xα22 }. From (13) we obtain
xα2 α12 ρ2 = (xα22 )α12 ϕ = xα22
xα2 α1 α2 ρ2 = (xα22 )α1 α2 ϕ = xα1 α2
xα22 ρ2 = (xα22 )a2 ϕ = xα2 α1 .
We see that ρ2 maps the expansion {xα1 , xα2 α12 , xα2 α1 α2 , xα22 } of X to
{xα12 , xα22 , xα1 α2 , xα2 α1 } which is a basis for V2,1 ; so ρ2 determines an element of G2,1 .
It can be verified ρ−1
2 ψρ2 = ϕ, so ρ2 is a conjugator. At this point we could stop but we
give the final case for completeness.
(ii) When w = xα22 α1 we have
xα22 α13 α2 ψ l+1 = xα12 α2

⇐⇒

xα1 α2 = xα12 α2 ,

which has no solutions.
We find one conjugating element ρ2 and we see that ψ and ϕ are conjugate via ρ2 .
The algorithm for the conjugacy of regular infinite elements of Gn,r is as follows.
Algorithm 5.27. Let ψ and ϕ be regular infinite elements of Gn,r .
Step 1: Construct A-bases Xψ and Xϕ with respect to which ψ and ϕ are in quasi-normal form
(Lemma 4.28).
Step 2: Construct the equivalence classes Xi , i = 1, . . . , m, of ≡ on Xψ (Lemma 5.20).
Step 3: Find the initial and terminal elements of semi-infinite Xϕ -components of ϕ, by finding the
minimal expansion of Xϕ associated to ϕ (Lemma 4.9).
Step 4: Construct the sets Ri (ψ, ϕ).
Step 5: For each equivalence class Xi of ≡ on Xψ choose an element xi ∈ Xi , of type (B).
Step 6: For each i and each pair (xi , y) of Ri (ψ, ϕ), construct a map ρi : Xi 7→ Xϕ , using equation (12), as in the proof of Lemma 5.24, if possible. In each case check that ρi is an
automorphism.
Step 7: For each m tuple ρ1 , . . . , ρm of automorphisms, from the previous step, check whether the
map ρ = ρ1 ∗ · · · ∗ ρm conjugates ψ to ϕ.

46

6

The power conjugacy problem

For a group with presentation hX | Ri, the power conjugacy problem is to determine, given words
g, h ∈ F(X) whether or not there exist non-zero integers a and b such that g a is conjugate to hb in
G. We may in addition require that, if the answer to this question is “yes”, then integers a and b,
and an element c ∈ F(X), are found, such that c−1 g a c =G hb . We say the power conjugacy problem
is decidable if there is an algorithm which, given g and h outputs “yes” if they’re conjugate and
“no” otherwise. Again, the stronger form entails the obvious extra requirements. As before, in Gn,r
we work entirely with symbols for automorphisms, ignoring the presentation.
As in the case of the conjugacy problem, we break the power conjugacy problem down into
two cases; one for periodic elements and one for regular infinite elements. Then, we construct an
algorithm that combines the two parts.

6.1

The power conjugacy for periodic elements

Let ψ and ϕ be periodic elements of Gn,r , of order k and m respectively, in quasi-normal form with
respect to the A-bases X and Y . To test whether there exist a, b ∈ Z such that ψ a is conjugate to
ϕb , we apply Proposition 5.11 to the pair ψ c , ϕd , for all c ∈ {1, . . . , k} and all d ∈ {1, . . . , m}.

6.2

Regular infinite elements

The first step is to compare the sets Mψ and Mψa , a ∈ Z, |a| > 1, for a regular infinite automorphism ψ.
Lemma 6.1. Let ψ be a regular infinite element of Gn,r and let a be a non-negative integer. Then
Mψa = {(m/d, Γq ) | (m, Γ) ∈ Mψ , gcd(m, a) = d and |a| = qd}.

(14)

Proof. Let ψ be in semi-normal form with respect to X. The X-components of ψ a are sub-sequences
of the X-components of ψ, so ψ a is also in semi-normal form with respect to X. Suppose to begin
with that a > 0. First we show that the right hand side of (14) is contained in the left hand side.
If (m, Γ) ∈ Mψ then there exists an element u of Vn,r in a semi-infinite X-component for ψ of
characteristic (m, Γ); and we may assume u ∈ XhAi. If d = gcd(m, a), p = m/d, q = a/d and
k = ma/d, then u(ψ a )p = uψ mq = uΓq , (as mq has the same sign as m). If a < 0 then, from the
above, with d = gcd(m, −a), p = m/d, q = −a/d and k = −ma/d, we have uψ −ap = uΓq . In all
cases therefore u is a characteristic element of ψ a . Furthermore, if u(ψ a )r = u∆, with ∆ 6= 1 then,
from Lemma 4.25, m|ar, which we can rewrite as pd|qdr, so p|qr. As gcd(p, q) = 1, this implies p|r,
so that |m/d| = |p| ≤ |r|. Hence u has characteristic (m/d, Γq ), with respect to ψ a . As u belongs
to a semi-infinite X-component for ψ a , it follows that (m/d, Γq ) is in Mψa and so we have
Mψa ⊇ {(m, Γq ) | (md, Γ) ∈ Mψ , d > 0, gcd(m, q) = 1 and |a| = qd}.
On the other hand, suppose that (r, ∆) ∈ Mψa . Then again, there exists u ∈ XhAi such that
u is a characteristic element of ψ a , so uψ ar = u∆. Thus, from Lemma 4.25, u is a characteristic
element for ψ, with characteristic (m, Γ) ∈ Mψ , such that m|ar and ∆ = Γt , where ar = mt, t > 0.
Let d = gcd(a, m), m = pd and a = qd. Then dqr = pdt, so qr = pt and gcd(p, q) = 1, so r = pr0
and t = qt0 , for some r0 , t0 . However, we have u(ψ a )p = uψ dpq = uψ mq = uΓq , and so, by definition
of (r, ∆) ∈ Mψa , we see that |p| ≥ |r|, so r0 = ±1. Since a > 0, both m and r have the same sign,
47

so r0 = 1. It now follows that r = p = m/d and ∆ = Γq , so (r, ∆) belongs to the set on the right
hand side of (14). That is
Mψa ⊆ {(m, Γq ) | (md, Γ) ∈ Mψ , d > 0, gcd(m, q) = 1 and |a| = qd}.
If a < 0 then the lemma follows by applying the result above to Mψ−1(−a) , as for all θ ∈ Gn,r
we have (m, Γ) ∈ Mθ if and only if (−m, Γ) ∈ Mθ−1 .
Example 6.2. Let n = 2 and r = 1 and let V2,1 be free on x = {x}. Let ϕ be the regular infinite
element of G2,1 defined by the bijection from
Y = {xα13 , xα12 α2 , xα1 α2 , xα2 },
to
Z = {xα12 , xα1 α2 , xα2 α1 , xα22 },
given by the following tree pair diagram.
ϕ:
1

2

3

−→

4

3

1

2

4

Then Y is the minimal expansion of {x} associated to ϕ. The minimal expansion of {x} contained
in Y hAi ∪ ZhAi is X = {xα12 , xα1 α2 , xα2 }. XhAi \ Y hAi = {xα12 } and XhAi \ ZhAi = {xα2 }. The
X-components of these elements are
· · · 7→ xα1 α2 α1 7→ xα13 7→ xα1 α2 7→ xα12
with characteristic (−2, α1 ) and
xα2 7→ xα22 7→ xα23 7→ xα24 7→ · · ·
with characteristic (1, α2 ). Hence ϕ is in quasi-normal form with respect to X and Mϕ =
{(-2, α1 ), (1, α2 )}.
The map ϕ2 may be defined by the bijection from
U = {xα13 , xα12 α2 , xα1 α2 α1 , xα1 α22 , xα2 }
to
V = {xα12 , xα1 α2 , xα2 α1 , xα22 α1 , xα23 }
given by a different tree pair diagram.
ϕ2 :

−→
5
1

2

3

4

1

3

4

2

5

Then U is the minimal expansion of {x} associated to ϕ2 and the minimal expansion of {x}
contained in U hAi∪V hAi is X again. XhAi\U hAi = {xα12 , xα1 α2 } and XhAi\V hAi = {xα2 , xα22 };
the corresponding X-components are
· · · 7→ xα13 7→ xα12

· · · 7→ xα1 α2 α1 7→ xα1 α2
48

with characteristic (−1, α1 ) and
xα2 7→ xα23 7→ · · ·

xα22 7→ xα24 7→ · · ·

with characteristic (1, α22 ). Hence ϕ2 is in quasi-normal form with respect to X and Mϕ2 =
{(-1, α1 ), (1, α22 )}, as asserted by Lemma 6.1.
Lemma 6.3 and Proposition 6.6 will allow us to find “minimal” pairs (a, b) such that ψ a and ϕb
are conjugate.
Lemma 6.3. Let ψ and ϕ be regular infinite elements of Gn,r and let c be an integer, such that c
is coprime to m, for all m ∈ Z such that (m, Γ) ∈ Mψ ∪ Mϕ . Then ψ c ∼ ϕc if and only if ψ ∼ ϕ.
Proof. If ψ ∼ ϕ then it is immediate that ψ c ∼ ϕc . For the converse, let ρ ∈ Gn,r be such that
ϕc = ρ−1 ψ c ρ and observe that we may assume, without loss of generality, that c > 0. Suppose that
ψ and ϕ are in quasi-normal form with respect to A-bases X and Y , respectively. From Lemma
6.1, Mψc = {(m, Γc )|(m, Γ) ∈ Mψ } and Mϕc = {(m, ∆c )|(m, ∆) ∈ Mϕ }.
Let u be an element of Vn,r which is characteristic for ψ, with ψ-characteristic (m, Γ). Then,
from Lemma 6.1 (and its proof), u has ψ c -characteristic (m, Γc ) and, as ϕc = ρ−1 ψ c ρ, its image
uρ has ϕc -characteristic (m, Γc ). Hence, from Lemma 6.1 again, uρ has ϕ-characteristic (m, Γ). As
gcd(c, m) = 1, there exist integers s and t such that ms + ct = 1. Since ψ c ρ = ρϕc we have, in the
case where s > 0,
uψρ = uψ ms+ct ρ = (u(ψ m )s )ψ ct ρ = uΓs ψ ct ρ = uΓs ρϕct
= (uρ)Γs ϕct = (uρ)ϕms ϕct = (uρ)ϕms+ct
= uρϕ.
If s < 0 then we have m(−s) + c(−t) = −1, with −s > 0 and the argument above implies instead
that uψ −1 ρ = uρϕ−1 . In this case, let v = uψ, so v also has ψ-characteristic (m, Γ) and, applying
the argument above to v instead of u, consequently vψ −1 ρ = vρϕ−1 , from which it follows that
uψρ = uρϕ. This applies in particular to all elements of X of type (B), with respect to ψ.
Let y 0 be an element of type (C), with respect to ψ; so there exists an integer k and an element
y ∈ X of type (B) such that y 0 ψ k = yΩ. Then y 0 = yΩψ −k , and yψ j has the same ψ-characteristic
as y, for all j: and so is a characteristic element for ψ. From the above then yψ j ρ = (yρ)ϕj , for all
j. Now
y 0 ψρ = yΩψ 1−k ρ = yψ 1−k ρΩ = yρϕ1−k Ω = yρϕ−k ϕΩ
= yψ −k ρϕΩ = yψ −k Ωρϕ = y 0 ρϕ.
Therefore, yψρ = yρϕ, for all y ∈ X, so ψ ∼ ϕ.
Definition 6.4. Let ψ be a regular infinite element of Gn,r and let a be a positive integer. Define
a map ψba : Mψ → Mψa by ψba (m, Γ) = (p, Γα ), where d = gcd(m, a), p = m/d and α = a/d.
Example 6.5. For ϕ in Example 6.2, with a = 2, the map ϕ
b2 : Mϕ → Mϕ2 is given by
ϕ
b2 (-2, α1 ) = (-1, α1 )

and ϕ
b2 (1, α2 ) = (1, α22 ).

49

From Lemma 6.1 this is a well defined map, and is surjective. In general it is not injective. For
instance if p, s and t are pairwise coprime positive integers and we have m1 = ps, m2 = pt and
a = st, then d1 = gcd(m1 , a) = s and d2 = gcd(m2 , a) = t. If, for some non-trivial Λ ∈ A∗ , we have
(m1 , Λs ) and (m2 , Λt ) in Mψ then both these elements are mapped by ψba to (p, Λst ).
Proposition 6.6. Let ψ and ϕ be regular infinite elements of Gn,r , let a and b be positive integers
and let the images of ψba and ϕ
bb be
βi
i
Mψa = {(pi , Γα
i ) | i = 1, . . . , M } and Mϕb = {(qi , ∆i ) | i = 1, . . . , N }.

For i = 1, . . . , M , let
i
(ψba )−1 (pi , Γα
i ) = {(mi,j , Γi,j ) | 1 ≤ j ≤ Mi }

and, for i = 1, . . . , N , let
(ϕ
bb )−1 (qi , ∆βi i ) = {(ni,j , ∆i,j ) | 1 ≤ j ≤ Ni }.
i
If ψ a ∼ ϕb then M = N and, after reordering if necessary, we have pi = qi and Γα
= ∆βi i .
i
∗
Moreover, there exist positive integers α, β, g, di,j , ei,k , si,j,k , ti,j,k , fi,j,k , and Λi,j,k ∈ A , for 1 ≤
i ≤ M , 1 ≤ j ≤ Mi and 1 ≤ k ≤ Ni , such that

α=

a
b
= di,j fi,j,k ti,j,k and β = = ei,k fi,j,k si,j,k , for all i, j, k,
g
g

and
ψ α ∼ ϕβ ,
s

i,j,k
and ∆i,j =
where di,j is a positive divisor of mi,j , ei,k is a positive divisor of ni,k , Γi,j = Λi,j,k

ti,j,k
Λi,j,k
,

and

fi0 ,j 0 ,k0 


Y

(ti,j,k di,j ) /ti0 ,j 0 ,k0 di0 ,j 0 ,

i,j,k

for all i0 , j 0 , k 0 .
Proof. Assume ψ a ∼ ϕb , with a, b > 0, and that ρ−1 ψ a ρ = ϕb . From Lemma 5.16, Mψa and
βi
i
Mϕb are equal, so M = N , and we may order Mψa so that (pi , Γα
i ) = (qi , ∆i ), so pi = qi and
βi
αi
α
α
Γi = ∆i . With the notation for (ψba )−1 (pi , Γi i ) and (ϕ
bb )−1 (qi , ∆i i ) given in the statement of
the proposition, let di,j = gcd(a, mi,j ) and ei,k = gcd(b, ni,k ), so
mi,j /di,j = pi = qi = ni,k /ei,k
and let
αi,j = a/di,j , βi,k = b/ei,k ,
and

β

α

βi
i,k
i
Γi,ji,j = Γα
i = ∆i = ∆i,k ,

by Definition 6.4, for 1 ≤ i ≤ M , 1 ≤ j ≤ Mi and 1 ≤ k ≤ Ni .

50

(15)

α

β

As Γi,ji,j = ∆i,ki,k , by Proposition 3.9, there exist Λi,j,k ∈ A∗ and positive integers si,j,k , ti,j,k
s

t

i,j,k
i,j,k
such that Γi,j = Λi,j,k
and ∆i,j = Λi,j,k
. Taking a power of Λi,j,k if necessary, we may assume
that gcd(si,j,k , ti,j,k ) = 1. Then

s

i,j,k
Λi,j,k

αi,j

β

α

t

i,j,k
= Γi,ji,j = ∆i,ki,k = Λi,j,k

βi,k

,

(16)

so si,j,k αi,j = ti,j,k βi,k . As si,j,k and ti,j,k are coprime this implies that αi,j /ti,j,k = βi,k /si,j,k =
ci,j,k ∈ Z, and αi,j = ci,j,k ti,j,k and βi,k = ci,j,k si,j,k .
Let
g = gcd({ci,j,k |1 ≤ i ≤ M, 1 ≤ j ≤ Mi , 1 ≤ k ≤ Ni }).
Then there exist integers fi,j,k such that ci,j,k = gfi,j,k , for all i, j, k. From Lemma 6.1, Mψa/g
consists of elements (m/p, Γα ), where (m, Γ) ∈ Mψ , p = gcd(m, a/g) and α = a/gp. Similarly,
elements of Mϕb/g are of the form (n/q, ∆β ), where (n, ∆) ∈ Mϕ , q = gcd(n, b/g) and β =
b/gq. Now g|ci,j,k and ci,j,k |αi,j and ci,j,k |βi,k . Therefore gcd(mi,j , a/g) = gcd(mi,j , a) = di,j and
similarly gcd(ni,k , b/g) = ei,k . Thus g is coprime to
pi =

ni,k
mi,j
=
,
gcd(mi,j , a/g)
gcd(ni,k , b/g)

for all i, j, k. From Lemma 6.3, it follows that ψ a/g ∼ ϕb/g .
Now
a/g = αi,j di,j /g = ci,j,k ti,j,k di,j /g = fi,j,k ti,j,k di,j
and similarly
b/g = fi,j,k si,j,k ei,k ,
for all i, j, k. Also
gcd({fi,j,k |1 ≤ i ≤ M, 1 ≤ j ≤ Mi , 1 ≤ k ≤ Ni }) = 1
so, for fixed i0 , j 0 , k 0 ,

fi0 ,j 0 ,k0 


Y

(ti,j,k di,j ) /ti0 ,j 0 ,k0 di0 ,j 0 .

i,j,k

Corollary 6.7. The power conjugacy problem for regular infinite elements of Gn,r is solvable.
Proof. Let ψ and ϕ be regular infinite elements of Gn,r . Suppose that ψ a is conjugate to ϕb , for
some non-zero a, b. Replacing either ψ or ϕ or both by their inverse, we may assume that a, b > 0.
Then, in the notation of the proposition above, we have ψ α ∼ ϕβ , where α = fi,j,k ti,j,k di,j and
β = fi,j,k si,j,k ei,k . From the conclusion of the theorem it is clear that there are finitely many
choices for fi,j,k , si,j,k , ti,j,k , di,j and ei,k . Hence there are finitely many possible α and β, and
we may effectively construct a list of all possible pairs (α, β). Having constructed this list we may
check whether or not ψ α ∼ ϕβ , using Algorithm 5.27. Hence we may decide whether or not there
exist a, b such that ψ a ∼ ϕb .

51

The proof of Proposition 6.6 forms the basis for the algorithm for the power conjugacy problem.
Given regular infinite elements ψ, ϕ ∈ Gn,r we construct bounds â and b̂ such that if some (positive)
power of ψ is conjugate to a (positive) power of ϕ then ψ c ∼ ϕd , for 0 < c ≤ â and 0 < d ≤ b̂.
Following the proof of the proposition, if ψ a ∼ ϕb , for some a, b > 0, then the inverse images ψ̂a
and ϕ̂b partition Mψ and Mϕ , so we have integers L, Mi , Ni such that
Mψ = ∪L
i=1 {(mi,j , Γi,j ) | 1 ≤ j ≤ Mi }
and
Mϕ = ∪L
i=1 {(ni,k , ∆i,k ) | 1 ≤ k ≤ Ni }.
∗
r
0s
Given any Γ ∈ A∗ there
√ exists unique Λ ∈ A and r ∈ N such that Γ = Λ and if Γ = Λ then
s ≤ r. We denote Λ by Γ and r by m(Γ). From equations (15) and (16), it follows that
p
p
p
p
p
Λi,j,k = Γi,j = Γi = ∆i = ∆i,k

and
si,j,k ≤ m(Γi,j ) and ti,j,k ≤ m(∆i,k ),
for 1 ≤ i ≤ L, 1 ≤ j ≤ Mi and 1 ≤ k ≤ Ni .
Q
From Proposition 6.6 we have α = d1,1 f1,1,1 t1,1,1 and f1,1,1 ≤ (i,j,k)6=(1,1,1) di,j ti,j,k . As di,j ≤
|mi,j | and ti,j,k ≤ m(∆i,k ), this means that
α≤

Mi Y
Ni
L Y
Y

di,j ti,j,k

i=1 j=1 k=1

≤

Mi Y
Ni
L Y
Y

|mi,j | m(∆i,k )

i=1 j=1 k=1

≤

Mi
L Y
Y

Ni

|mi,j |

i=1 j=1

≤

L
Y



Mi
Y


i=1

Ni
Y

!
m(∆i,k )

k=1

Ni
|mi,j |

j=1

Ni
Y

!Mi
m(∆i,k )

.

(17)

k=1

Similarly

Ni 
!Mi  M
Ni
L
i
Y
Y
Y



|ni,k |
m(Γi,j )  .
β≤

i=1
0

(18)

j=1

k=1
0

Now suppose that a solution ψ a ∼ ϕb gives rise to sub-partitions of the partitions of Mψ and Mϕ
above. Straightforward calculation shows that in this case, the bounds on α and β obtained are again
less than or equal to the right hand sides of (17) and (18) (calculated using the original partitions).
Thus, in computing (upper) bounds â and b̂ we may take partitions of Mψ = P1 ∪ · · · ∪ PL and
Mϕ = Q1 ∪ · · · ∪ QL√with √
L as small as possible, subject to the constraint that, for each i such that
1 ≤ i ≤ L we have Γ = ∆, for all (m, Γ) ∈ Pi and (n, ∆) ∈ Qi . If these partitions satisfy these
properties, and this does not hold for any partition of fewer than L subsets, (in other words the
52

partitions are formed by gathering together characteristics with the same root) then the bounds â
and b̂ are given by

|Qi | 
|Pi | 
L
Y
Y
Y



(19)
â =
|m|
m(∆) 

and

i=1

(m,Γ)∈Pi


L
Y

b̂ =


Y

i=1

(n,∆)∈Qi

|Qi | 

m(Γ)  .

|Pi | 
Y

|n|



(n,∆)∈Qi

(20)

(m,Γ)∈Pi

Example 6.8. Let n = 2 and r = 1 and V2,1 be free on {x}. Let ψ be the regular infinite element
of G2,1 of Examples 4.1 and 4.11. Then ψ is in quasi-normal form with respect to the A-basis
X = {xα1 , xα2 } and Mψ = {(1, α2 ), (-1, α1 )}.
Let ϕ be the regular infinite element of G2,1 defined by a bijective map from
Yϕ = {xα1 , xα2 α13 , xα2 α12 α2 , xα2 α1 α2 , xα22 }
to
Zϕ = {xα12 , xα1 α2 α1 , xα1 α22 α1 , xα1 α23 , xα2 }
given as illustrated below.
−→

ϕ:
1
2

3

4

5

3

2
4

5

1

Then Yϕ is the minimal expansion of {x} associated to ϕ and the minimal expansion of {x}
contained in Yϕ hAi∪Zϕ hAi is X. We have XhAi\Yϕ hAi = {xα2 , xα2 α1 , xα2 α12 } and XhAi\Zϕ hAi =
{xα1 , xα1 α2 , xα1 α22 } The X-components of these elements are:
xα1 7→ xα1 α23 7→ xα1 α26 7→ · · ·
xα1 α2 7→ xα1 α24 7→ xα1 α27 7→ · · ·
xα1 α22 7→ xα1 α25 7→ xα1 α28 7→ · · ·
· · · 7→ xα2 α16 7→ xα2 α13 7→ xα2
· · · 7→ xα2 α17 7→ xα2 α14 7→ xα2 α1
· · · 7→ xα2 α18 7→ xα2 α15 7→ xα2 α12
so ϕ is in quasi-normal form with respect to X and Mϕ = {(1, α23 ), (-1, α13 )}. In the notation
above, we have partitions Mψ = P1 ∪ P2 and Mϕ = Q1 ∪ Q2 with P1 = {(1, α2 )}, P2 = {, (-1, α1 )},
Q1 = {(1, α23 )} and Q2 = {(-1, α13 )}, so we obtain bounds â = 9 and b̂ = 1.
Assume there exists positive integers a, b such that ψ a ∼ ϕb . We may now assume that a ≤ 9
and b = 1. The map ψba : Mψ → Mψa is given by
a/d
a/d
ψba (1, α2 ) = (1/d1 , α2 1 ), ψba (−1, α1 ) = (−1/d2 , α1 2 ),

53

where d1 = gcd(1, a) = 1 and d2 = gcd(-1, a) = 1. Thus
Mψa = {(1, α2a ), (-1, α1a )}.
The only possible choice for a making Mψa = Mϕb = Mϕ is a = 3. Applying Algorithm 5.27 to
ψ 3 and ϕ we find a conjugating element ρ, given by xα1 ρ = xα2 and xα2 ρ = xα1 .
Remark 6.9. In Corollary 6.7 the powers a and b were positive, giving us upper bounds a ≤ â and
b ≤ b̂ for the minimal powers which solve the power conjugacy problem. Now suppose that a < 0
and b > 0. We may write ψ a = (ψ −1 )−a and then −a > 0. If we apply Corollary 6.7 to (ψ −1 , ϕ),
we obtain a second pair of bounds −a ≤ ā and b ≤ b̄. Observing that (m, Γ) ∈ Mψ if and only if
(−m, Γ) ∈ Mψ−1 , we note that this replacement ψ 7→ ψ −1 preserves the absolute value |m| of all
characteristic multipliers. Thus each of the terms |mi,j |, |ni,k |, |m| and |n| in equations (17–20) is
unchanged. We conclude that ā = â and b̄ = b̂.
The same argument applies equally well to the remaining two cases a > 0, b < 0 and a < 0,
b < 0. Thus, once we have obtained â and b̂, we need only to check the ranges 1 ≤ |a| ≤ â and
1 ≤ |b| ≤ b̂ to find minimal conjugating powers.
Example 6.10. Let ψ be as in Example 6.8 and let ϕ be as in Example 6.2. Then Mψ =
{(1, α2 ), (-1, α1 )} and Mϕ = {(-2, α1 ), (1, α2 )}. In the notation above, we have partitions Mψ =
P1 ∪P2 and Mϕ = Q1 ∪Q2 with P1 = {(1, α2 )}, P2 = {(-1, α1 )}, Q1 = {(1, α2 )} and Q2 = {(-2, α1 )},
so we obtain bounds â = 1 and b̂ = 2.
Assume there exist positive integers a, b such that ψ a ∼ ϕb ; with a = 1 and b ≤ 2. The map
b
ϕ
b : Mϕ → Mϕb is given by
b/d1

ϕ
bb (1, α2 ) = (1/d1 , α2

b/d2

), ϕ
bb (-2, α1 ) = (-2/d2 , α1

),

where d1 = gcd(1, b) = 1 and d2 = gcd(-2, b) = b. Thus,
Mϕb = {(1, α2 ), (-2, α1 )}

or {(1, α22 ), (-1, α1 )}.

As Mψ 6= Mϕb , for b = 1 and b = 2, there is no pair of positive integers a, b such that ψ a ∼ ϕb .
The same argument applies on replacing ϕ or ψ by ϕ−1 or ψ −1 , respectively, so no nontrivial power
of ϕ is conjugate to a power of ψ.
In order to solve the power conjugacy problem for general regular infinite elements of Gn,r we
require an algorithm which finds all pairs (a, b), within the bounds calculated, rather than merely
deciding whether or not such a pair exists. This is the algorithm we describe here. It constructs a
set PC RI consisting of triples (a, b, ρ), such that ρ−1 ψ a ρ = ϕb .
Algorithm 6.11. Let ψ and ϕ be regular infinite elements of Gn,r .
Step 1: Construct A-bases Xψ and Xϕ with respect to which ψ and ϕ are in quasi-normal form
(Lemma 4.28).
Step 2: Construct the sets Mψ and Mϕ (see Definition 5.14).
Step 3: Calculate the bounds on â and b̂, using equations (19) and (20).
Step 4: For all pairs a, b such that 1 ≤ |a| ≤ â and 1 ≤ |b| ≤ b̂, input ψ a and ϕb to Algorithm
5.27. If a conjugating automorphism ρ is returned, add (a, b, ρ) to the set PC RI .
54

Step 5: If PC RI = ∅, output “No” and halt. Otherwise output PC RI .
Corollary 6.7 may be strengthened.
Corollary 6.12. Given regular infinite elements ψ, ϕ ∈ Gn,r there is a finite subset PC RI of
Z × Z × Gn,r , which may be effectively constructed, such that ψ a ∼ ϕb if and only if a = cg and
b = dg, for some (c, d, ρ) ∈ PC RI and g ∈ Z. Moreover, for all (c, d, ρ) ∈ PC RI and g ∈ Z, we have
ρ−1 ψ cg ρ = ϕdg .
Proof. From Lemma 6.6 and the description of Algorithm 6.11, PC RI is a finite set and it follows
that if ψ a ∼ ψ b , for some positive a, b ∈ Z, then (a/g, b/g, ρ) ∈ PC RI and in this case ρ−1 ψ a ρ = ϕb .
Replacing one or other, or both, of ψ and ϕ by their inverses the same holds, without the constraint
that a, b be positive. On the other hand if (c, d, ρ) is in PC RI then ρ−1 ψ c ρ = ϕd , so ρ−1 ψ cg ρ = ϕdg ,
for all g ∈ Z.

6.3

The power conjugacy algorithm

We combine the algorithms of Sections 6.1 and 6.2 to give an algorithm for the power conjugacy
problem in Gn,r . In fact in Sections 6.1 and 6.2 we find a description of all solutions of the power
conjugacy problem for periodic and regular infinite automorphisms, respectively: and the algorithm
in this section does the same for arbitrary elements of Gn,r .
If we are only interested in the existence of a solution to the power conjugacy problem then
we may essentially ignore the periodic part of automorphisms, as long as the regular infinite part
is non-trivial. To see this, suppose ψ and ϕ are elements of Gn,r and we have decompositions
a
ψ = ψP ∗ ψRI , ϕ = ϕP ∗ ϕRI . Assume that we have found that VRI,ψ is non-trivial and ψRI
is
b
conjugate to ϕRI , a, b 6= 0. In this case, ψP and ϕP have finite orders, m and k say, and so we
immediately have a solution ψ amk ∼ ϕbmk , amk, bmk 6= 0, of the power conjugacy problem. The
algorithm described below allows this type of solution but also tries to find a solution to the power
conjugacy problem corresponding to each pair (c, d) such that ψPc ∼ ϕdP . Thus, in Theorem 6.14,
we obtain a description of all solutions to the power conjugacy problem, for ψ and ϕ. (That is, all
pairs (a, b) such that ψ a ∼ ϕb . We do not find all possible conjugators ρ.)
Algorithm 6.13. Let ψ and ϕ be elements of Gn,r .
Step 1: Run Steps 1, 2 and 3 of Algorithm 5.6.
Step 2: Input ψRI and ϕRI to Algorithm 6.11.
Step 3: If XRI,ψ is non-empty (that is, VRI,ψ is non-empty) and PC RI is empty, output “No” and
stop.
Step 4: Compute the orders k and m of ψP and ϕP . Input ψPa and ϕbP to Algorithm 5.13, for all
c, d such that 1 ≤ c ≤ k and 1 ≤ d ≤ m. Construct the set PC P of all triples (c, d, ρ) found
such that ρ−1 ψ c ρ is conjugate to ϕd . If XRI,ψ is non-empty, adjoin the triple (0, 0, θ0 ) to
PC P , where θ0 is the identity map of the algebra Vn,sP , of Step 3 of Algorithm 5.6.
Step 5: If PC P is empty, output “No” and stop. If PC P is non-empty and XRI,ψ is empty output
PC P and stop.

55

Step 6: If this step is reached then both PC P and PC RI are non-empty. For all (α, β, ρRI ) in
PC RI and all pairs (c, d, ρP ) in PC P consider the simultaneous congruences
αx ≡ c mod k and βx ≡ d mod m,
where k and m are the orders of ψP and ϕP found in Step 4. For each positive solution
x = g (less than lcm(k, m)) add (αg, βg, g, ρP ∗ ρRI ) to the set PC (which is empty at the
start).
We verify that this algorithm solves the power conjugacy problem in the proof of the following
theorem.
Theorem 6.14. The power conjugacy problem for the Higman-Thompson group Gn,r is solvable.
Furthermore, given elements ψ, ϕ ∈ Gn,r , let ψP have order k, let ϕP have order m and let l =
lcm(k, m). There is a finite subset PC ⊆ Z3 × Gn,r , which may be effectively constructed, such that
ψ a ∼ ϕb if and only if (ag/h, bg/h, g, ρ) ∈ PC, where ρ ∈ Gn,r and g, h ∈ Z such that h ≡ g mod l,
h|a and h|b. In this case ρ−1 ψ a ρ = ϕb .
Proof. Apply Algorithm 6.13 to ψ and ϕ. If there exist a, b ∈ Z such that ψ a ∼ ϕb then ψPa ∼ ϕbP
a
∼ ϕbRI . In this case let ψP and ϕP have orders k and m, respectively and let a1 , b1 ∈ Z
and ψRI
be such that 1 ≤ a1 < k and 1 ≤ b1 < m and a1 ≡ a mod k, b1 ≡ b mod m. Then there exists ρP
such that (a1 , b1 , ρP ) ∈ PC I . Furthermore, from Corollary 6.12, there exists (a2 , b2 , ρRI ) ∈ PC RI
and h ∈ Z such that a = a2 h and b = b2 h. Let g be such that 1 ≤ g < lcm(k, m), and g ≡ h
mod lcm(k, m) so g ≡ h mod k and g ≡ h mod m. As h is a solution to the congruences a2 x ≡ a1
mod k and b2 x ≡ b1 mod m, it follows that g is also a solution to these congruences. Therefore
(a2 g, b2 g, g, ρP ∗ ρRI ) ∈ PC. As a2 = a/h and b2 = b/h, this is an element of Z3 × Gn,r of the
required form.
Conversely, assume (u, v, g, ρP ∗ ρRI ) ∈ PC, where u = ag/h and v = bg/h, for some a, h ∈ Z
satisfying the hypotheses of the theorem. Then there exist (α, β, ρRI ) in PC RI and (c, d, ρP ) in
PC P such that u = αg ≡ c mod k and v = βg ≡ d mod m. As g ≡ h mod l this implies that
a = (u/g)h = αh ≡ c mod k and b = (v/g)h = βh ≡ d mod m. Therefore ψPa = ψPc ∼ ϕdP = ϕbP ,
−1 a
b
a
by definition of PC P , and indeed ρ−1
P ψP ρP = ϕP . Also, a = αh and b = βh implies ρRI ψRI ρRI =
b
ϕRI , by Corollary 6.12, so
a
ψ a = (ψP ∗ ψRI )a = ψPa ∗ ψRI
∼ ϕbP ∗ ϕbRI = (ϕP ∗ ϕRI )b = ϕb

and ρP ∗ ρRI is a conjugating element.
Examples which illustrate how the algorithm works on automorphisms which are not necessarily
periodic or regular infinite can be found at [26]: follow the link to “Examples” and refer to the
examples named “mixed pconj phi” and “mixed pconj psi”.

References
[1] M. Anshel and P. Stebe, “The solvability of the conjugacy problem for certain HNN groups”,
Bull. Amer. Math. Soc., 80 (2) (1974) 266–270.
[2] N. Barker, “Topics in Algebra: The Higman-Thompson Group G2,1 and Beauville p-groups”,
Thesis, Newcastle University (2014)
56

[3] J. M. Belk and F. Matucci, “Conjugacy and dynamics in Thompson’s groups”, Geom. Dedicata
169 (1) (2014) 239–261.
[4] N.V. Bezverkhnii, “Ring Diagrams with Periodic Labels and Power Conjugacy Problem in
Groups with Small Cancellation Conditions C (3) -T (6)”, Science and Education of the Bauman MSTU, 14 (11) (2014).
[5] V.N. Bezverkhniı̌, A.N. Kuznetsova, “Solvability of the power conjugacy problem for words in
Artin groups of extra large type”, Chebyshevskii Sb. 9 (1) (2008) 50–68.
[6] C. Bleak, H. Bowman, A. Gordon, G. Graham, J. Hughes, F. Matucci and J. Sapir, “Centralizers in R.Thompson’s group Vn ”, Groups, Geometry and Dynamics 7, No. 4 (2013), 821–865.
[7] O. Bogopolski, A. Martino, O. Maslakova and E. Ventura, “The conjugacy problem is solvable
in free-by-cyclic groups”, Bulletin of the London Mathematical Society, 38, (10) (2006) 787–
794.
[8] M. G. Brin, “Higher dimensional Thompson groups”, Geom. Dedicata, 108 (2004) 163–192.
[9] K. S. Brown, “Finiteness properties of groups”, Journal of Pure and Applied Algebra, 44
(1987) 45-75.
[10] J. Burillo, S. Cleary and C. E. Röver, “Obstructions for subgroups of Thompson’s group V ”,
arxiv.org/abs/1402.3860
[11] J. W. Cannon, W.J. Floyd and W. R. Parry, “Introductory notes on Richard Thompson’s
groups”, Enseign. Math., (2) 42(3–4) (1996) 215–256.
[12] P. M. Cohn, “Universal Algebra”. Mathematics and its Applications, 6, D. Reidel Pub. Company, (1981).
[13] P. M. Cohn, “Algebra, Volume 3”. J. Wiley, (1991).
[14] L. P. J. Comerford, A note on power-conjugacy, Houston J. Math. 3 (1977), no. 3, 337—341.
[15] W. Dicks, C. Martinez-Pérez, “Isomorphisms of Brin-Higman-Thompson groups”, Israel Journal of Mathematics, 199 (2014), 189–218.
[16] A.V. Fesenko, “Vulnerability of Cryptographic Primitives Based on the Power Conjugacy
Search Problem in Quantum Computing”, Cybernetics and Systems Analysis, 50 (5) (2014)
815–816.
[17] G. Higman, “Finitely presented infinite simple groups”, Notes on Pure Mathematics, Vol. 8
(1974).
[18] B. Jónsson and A. Tarski, “On two properties of free algebras”, Math. Scand., 9 (1961) 95–101.
[19] D. Kahrobaei and M. Anshel, “Decision and Search in Non-Abelian Cramer-Shoup Public Key
Cryptosystem”, Groups-Complexity-Cryptology, 1 (2) (2009) 217-225.
[20] S. Lipschutz and C.F. Miller, “Groups with certain solvable and unsolvable decision problems”,
Comm. Pure Appl. Math., 24 (1971) 7–15.
57

[21] M. Lothaire, “Combinatorics on Words”, Addison-Wesley, Advanced Book Program, World
Science Division, (1983).
[22] C. Martinez-Perez, B. Nucinkis, “Bredon cohomological finiteness conditions for generalisations
of Thompson’s groups”, Groups Geom. Dyn. 7 (4) (2013) 931–959.
[23] R. McKenzie and R. J. Thompson, “An elementary construction of unsolvable word problems in
group theory”, Word problems: decision problems and the Burnside problem in group theory,
Studies in Logic and the Foundations of Math., 71, pp. 457–478. North-Holland, Amsterdam,
(1973).
[24] E. Pardo, “The isomorphism problem for Higman-Thompson groups”, Journal of Algebra, 344
(2011), 172–183.
[25] S.J. Pride, “On the residual finiteness and other properties of (relative) one-relator groups”,
Proc. Amer. Math. Soc. 136 (2) (2008) 377–386.
[26] D. M. Robertson, “thompson: a package for Python 3.3+ to work with elements of the HigmanThompson groups Gn,r ”. Source code available from https://github.com/DMRobertson/
thompsons_v and documentation available from http://thompsons-v.readthedocs.org/.
[27] O. P. Salazar-Diaz, “Thompson’s group V from a dynamical viewpoint”, Internat. J. Algebra
Comput., 1, 39–70, 20, (2010).
[28] R. J. Thompson, unpublished notes.
http://www.math.binghamton.edu/matt/thompson/index.html

58

