arXiv:0906.3902v3 [] 9 Jan 2017

Detecting geometric splittings in finitely presented
groups.
Nicholas W.M. Touikan
Department of Mathematical Sciences
Stevens Institute of Technology
email: nicholas.touikan@gmail.com
February 27, 2018
Abstract
We present an algorithm which given a presentation of a group G without
2-torsion, a solution to the word problem with respect to this presentation, and
an acylindricity constant κ, outputs a collection of tracks in an appropriate
presentation complex. We give two applications: the first is an algorithm
which decides if G admits an essential free decomposition, the second is an
algorithm which, if G is relatively hyperbolic, decides if it admits an essential
elementary splitting.

1

Introduction

A important group invariant is whether or not it splits as a certain type of
graph of groups. In this paper we prove an algorithmic analogue of Sela’s κacylindrical super accessibility [Sel97, Theorem 4.3] for the class of one edged
κ-acylindrical geometric splittings. In particular the main result, Theorem
B, gives an algorithm that produces a list that contains a representative of
every one edged κ-acylindrical geometric splitting of π1 (C), up to equivalence
in Aut (π1 (C)). We give some corollaries of this theorem.
Theorem A. There is an algorithm that takes as input a finite presentation
hX | Ri of a group G without 2-torsion and a solution to the word problem with
respect to this presentation and decides whether or not the group G admits an
essential free decomposition, i.e. a free decomposition
G = H1 ∗ H2
with H1 6= {1} =
6 H2 .
This theorem is proved in Section 1.7. As a consequence we have the
following corollary whose proof we leave as an exercise. (Hint: if we can solve
the word problem, then we can decide if a finitely generated group is abelian
and we can decide, given a finite presentation, if an abelian group is cyclic.)

1

Corollary 1.1. Let G = hX | Ri be as in the statement of Theorem A, then
we can find a Grushko decomposition for G.
In a sense, aside from the no 2-torsion assumption, this is the strongest
result of this type possible: the restrictions on the input are as minimal as can
be reasonably expected. This result also extends all previously known results
(at least in the case without 2-torsion), which we now briefly survey.
Diao and Feighn in [DF05] showed how to find a Grushko decomposition
of a fundamental group of a graph of free groups. Their techniques rely on
Whitehead methods refined by Gersten and group actions on square complexes.
Kharlampovich and Miasnikov in [KM05] showed how to find a Grushko decomposition of a fully residually free group by running their Elimination Process: the free decomposition becomes apparent by “separating the variables”
in the defining equations.
Even in the presence of 2-torsion, Dahmani and Groves in [DG08a] are able
to detect free splittings of certain relatively hyperbolic groups, by generalizing
an unpublished algorithm for hyperbolic groups due to Gerasimov. Their
approach is to decide some connectivity criterion of the boundary of toral
relatively hyperbolic groups. Our work implies this result in the 2-torsion-free
case. Another result [GW09] due to Groves and Wilton, which works in the
presence of 2-torsion, is that given a finite presentation of a group G and a
solution to the word problem with respect to that presentation we can decide
if G is free. If G is without 2-torsion, then this is an easy consequence of
Corollary 1.1. At the end of Section 1.7 we will explain later how to obtain
this result in complete generality from the work in this paper.
It is also worth noting that Casals-Ruiz and Kazachkov used methods related to ours to describe solutions to equations over free products [CRK11].
The algorithm given in this paper is also well-suited to relatively hyperbolic
groups we have the following immediate corollary to Theorem C, which is
proved in Section 1.8.
Corollary 1.2. We can decide if a torsion-free relatively hyperbolic group with
polycyclic parabolics has a trivial elementary JSJ decomposition, in the sense
of [Bow98, Bow01]or [GL11, Theorem 4].
This generalizes a result of Dahmani and Groves in [DG08b] for toral relatively hyperbolic groups in two ways. Firstly, the present approach works
for a larger wider class of groups. Secondly, it can detect splittings that are
not in the class Zmax . Both of these earlier limitations arise from fact that
all previous algorithms to detect splittings in relatively hyperbolic groups depend on “equational” methods. In particular they will not work with nilpotent
parabolics since we can’t solve equations over nilpotent groups [Rom79] and
they can’t detect non-Zmax splittings since Dehn twists around such groups
give trivial automorphisms.
In an earlier preprint Effective Grushko decomposition (http://arxiv.org/abs/0906.3902v1)
the author claimed Theorem A without the no 2-torsion hypothesis. There is
a gap in that proof: the argument is incomplete because the author did not
take Möbius strips into consideration. In the second version of this paper we
modified the argument so that it can handle κ-acylindricity and the existence

2

of Möbius strips, at the cost of having to exclude 2-torsion. Otherwise, there
was no gap in the second version of this paper, but it was horribly written.
This third version attempts to rectify the issue and has more pictures.

1.1

Acknowledgements

I wish to thank Olga Kharlampovich for her answers to some very technical
questions, enabling me to adapt the ideas in [KM98] to obtain the results of sections 6 and 7. I am grateful to Alexei Miasnikov for his numerous (ultimately
successful) attempts to explain the elimination process in advanced courses
and for drawing my attention to tracks. I am also grateful to Ilya Kazachkov,
Montserrat Casals-Ruiz, Martin Dunwoody, Gilbert Levitt, François Dahmani,
Vincent Guirardel, Daniel Groves, and Henry Wilton for discussion and encouragement. The second version of this paper was written while the author
was an NSERC postdoctoral fellow at CIRGET in UQAM and at the Oxford
Mathematical Institute. Although much of the third version paper was written on the agonizingly slow Amtrak Adirondack Train that connects New York
and Montreal, I feel no gratitude towards Amtrak. Finally I thank the anonymous referee for actually reading this paper and giving precise and relevant
feedback. The paper is much better now.

1.2

Outline of the paper

First we will give the basic definitions and results needed to make sense of the
statement of Theorem B. After stating it and discussing some of its limitation,
we apply it to detect free decompositions of finitely presented groups and
elementary splittings of relatively hyperbolic groups. These applications also
serve the role of providing a “tutorial” on how to use Theorem B.
Next we will define band complexes which are similar, but not identical,
to the band complexes in [BF95]. Instead of using them to study minimal
foliations, we will treat them as combinatorial objects to study Dunwoody
patterns (see Definition 1.4) . Next we will define transformations done to
band complexes and tracks they carry. This constitutes the Rips machine of
[BF95].
The Rips machine is designed to study a single lamination in a cell complex. The elimination process, inspired from works of Makanin and Razborov
[Mak82, Raz87] as read from [KM98], is a branching search algorithm that
constructs a finite rooted directed tree that decides the existence of certain
types of laminations, in our case, tracks. We will show how to construct this
tree one level at a time and give an analogy with splitting sequences for surface train tracks. We will then define various inadmissibility criteria which will
forbid the elimination tree from growing at certain nodes.
As usual in this business, it will be relatively easy to handle the thin/Levitt/710 case as well as the surface/quadratic/12 case. The real difficulty is in handling the superquadratic/axial/15 case and this is where most of the new ideas
in this paper reside.
Eventually we will have given sufficiently many inadmissibility criteria,
including a periodicity bound, to force the elimination tree to be finite. The

3

leaves of this tree will give us the output of the main algorithm.

1.3

Patterns, tracks, and geometric splittings

We take it for granted that the reader is comfortable with Bass-Serre theory.
The best reference, especially for this paper, would be [SW79]. Another standard reference is [Ser03]. We also assume the reader is well acquainted with
polygonal 2-complexes, their fundamental groups, and the actions of fundamental groups on universal covers by deck transformations.
The graphs of groups X has underlying graph X. We will write G splits
as a graph of groups X or even X is a splitting of G instead writing “G is the
fundamental group of the graph of groups X.” We will also use the action
of a group G on a simplicial tree T and the corresponding splitting X, where
X = G\T , interchangeably. Finally all trees are assumed to be minimal.
Convention 1.3. In order to be sure to avoid any pathologies, we will restrict
ourselves to the piecewise linear category of topological spaces.
Throughout this paper C will be a polygonal 2-complex. If f : X → Y is
a continuous map we denote its functorial image f♯ : π1 (X) → π1 (Y ), which
is well-defined up to conjugacy. Let Y ⊂ X be connected cell complexes.
Consider the natural map:
Y
π1 (Y )

i
i♯

X
π1 (X)

where i denotes the inclusion map. We denote
Gp(Y ) = i♯ (π1 (Y )),
which gives a well defined conjugacy class in π1 (X).
Definition 1.4. Let C be a polygonal 2-complex. A pattern P ⊂ C is an
embedded 1-complex such that:
(i) for every 2-cell D ⊂ C, P ∩ D is a (possibly empty) finite collection of
closed arcs joining distinct sides of D;
(ii) P does not meet C (0) ;
(iii) P has a regular neighbourhood N (P ) ⊂ C homeomorphic to P × [−1, 1].
Definition 1.5. A connected component of a pattern is called a track.
This definition of a pattern is slightly non-standard in that the last condition implies that our pattern is 2-sided. 2-sidedness however should be
standard because it implies that the pattern is locally separating into two
components. The Seifert-van Kampen Theorem immediately implies that the
decomposition (which is essentially a graph of spaces)
C = N (P ) ∪ C \ P

4

(1)

splits π1 (C) as a graph of groups XP where the vertex groups are given by
Gp(Ci ) and the edge groups are given by Gp(tj ), where the Ci denote the
connected components of C \ P and the tj denote the tracks in P respectively.
Proposition 1.6. Let P ⊂ C be a pattern and let Pe be the lift of P in the
e of C. Each connected component of Pe separates C
e into
universal cover C
two components. This gives rise to the π1 (C)-tree T (P, C) whose vertices are
e Pe, whose edges are connected components of Pe and
connected components of C\
fi if e
such that the edge e
t is adjacent to the vertex C
t is contained in the closure
f
of of Ci . Thus T (P, C) can be obtained by a π1 (C)-equivariant identification
map
e ։ T (P, C)
π:C
(2)

e of P is again a pattern in C.
e This gives a decompoProof. The lift Pe ⊂ C
e
e
sition of C as in (1) which expresses π1 (C) as a graph of groups Y. If some
component of Pe is not separating the underlying graph Y of Y contains a cycle
e = 1. It therefore follows that the graph Y is
contradicting the fact that π1 (C)
a tree T (P, C), which is easily seen to be a π1 (C)-tree.
π is obtained collapsing each track neighbourhood N (e
t) = e
t × [−1, 1] ։
e
[−1, 1] and collapsing every connected component of closure C \ N (Pe) to
a point.

This next proposition follows immediately by thinking about the action
of π1 (C) on T (P, C) induced by deck transformations and the meaning of the
Seifert-van Kampen Theorem, or simply by thinking of (1) as a graph of spaces
decomposition à la [SW79].

Proposition 1.7. Let P ⊂ C be a pattern. Then the action of π1 (C) on
T (P, C) gives the splitting of π1 (C) as the graph of groups XP induced by the
decomposition (1).
All that being sorted, we can now make sense of the second and third words
of the title of the paper.
Definition 1.8. For a pattern P ⊂ C the tree T (P, C) obtained in Proposition
1.6 is called the Bass-Serre tree dual to P , or simply the dual Bass-Serre tree.
Definition 1.9. A splitting of π1 (C) is geometric if it is represented by a
pattern P , i.e. the Bass-Serre tree of the splitting is given by the action of
π1 (C) on T (P, C). The pattern P is said to be essential if T (P, C) is infinite.
The following fact is important since it implies that the class of geometric
splittings is significant.
Theorem 1.10 (Restatement of [DS99, Lemma 2.2]). Let π1 (C) act minimally
on a tree T . Then there exists a pattern P ⊂ C such that there is a π1 (C )equivariant surjective simplicial map called a resolution
ρ : T (P, C) → T.
In particular, the edge stabilizers of T (P, C) are conjugate to subgroups of the
edge stabilizers of T . Moreover if the action of π1 (C) on T is non-trivial then
some track in P will be essential.

5

Immediately we get:
Corollary 1.11. If π1 (C) is freely decomposable, then some essential free
decomposition is geometric.
Corollary 1.12. If C is a finite complex, then any Guirardel-Levitt JSJ deformation space [GL09, Definition 4] of π1 (C) contains a geometric splitting.
Proof. We refer the reader to the introduction of [GL09] for the terminology
in this proof. Let T be some JSJ tree for π1 (C) over some class of groups A,
i.e. a domination-maximal universally elliptic A-tree. Theorem 1.10 implies
the existence of a geometric tree T (P, C) → T that dominates T . Since the
edge groups of T (P, C) are contained in edge groups of T and A is assumed to
be closed under taking subgroups, T (P, C) is also an A-tree. Since the edge
groups of T are A-universally elliptic, so must the edge groups of T (P, C). It
follows that T (P, C) is also a domination-maximal universally elliptic A-tree
so the result follows.

1.4

Relative splittings

Suppose we are given a finite collection of finite generating

S = {hi }i∈In | n = 1, . . . , m

of subgroups of π1 (C), and that we want to study the geometric splittings
of π1 (C) in which the subgroups hhi i are elliptic. Then we can make a new
2-complex CS ⊃ C with π1 (C) ≈ π1 (CS ) as follows (see Figure 1.) For each
Sn = {hi }i∈In
(1) Make a bouquet of circles Bn such that for each h ∈ Sn there is a directed
edge eh in Bn .
(2) Attach the vertex vn of Bn to the vertex v of C by an arc αn .
(3) Attach a 2-cell so that the loop αn ∗ eh ∗ α−1
n is now homotopic to h ∈
π1 (C, v).
We call the resulting 2-complex CS . We note that π1 (C) ≈ π1 (Cs ) because
of the obvious deformation retraction CS ։ C. We now employ the following

C

Figure 1: Attaching bouquets of circles to a presentation complex.
We must then attach 2-cells to preserve the fundamental group.
trick to restrict to relative geometric splittings.

6

Proposition 1.13. Let H be the set of subgroups generated by the elements of
S. Then every track t dual to a geometric splitting of π1 (C) relative to H can
be extended to a track t′ ⊂ CS so that t′ is disjoint from the edges eh in item
(1) of the construction of CS .
sketch. Let π1 (C)× T → T be a geometric action with the subgroups H acting
elliptically then we can extend the pattern P ⊂ C ⊂ CS to a pattern P ′ ⊂ CS
such that P ′ has empty intersection with the edges eh and such that we have
a π1 (C)-equivariant isomorphism
T (P ′ , CS ) → T (P, C).

(3)

We do this by taking a resolution
fS → T (P, C)
ρ′ : C

e → T (P, C) such that the lifts of the vertices of vi are
which extends ρ : C
mapped to vertices stabilized by appropriate conjugates of hSi i. We refer the
reader to Section 2 of [DS99] for details on the resolution construction. It
therefore follows geometric splittings of π1 (C) relative to H are given exactly
by patterns in π1 (CS ) that do not intersect the new edges eh .

1.5

Equivalence under automorphisms

Let
ϕ: G×T

→ T

(g, x) 7→ g · x

be an action of a group G on a tree T . Then for any α ∈ Aut(G) we may twist
ϕ by α to get a new action
ϕα : G × T

→ T

(g, x) 7→ α(g) · x
Definition 1.14. Let ϕ : G × T 7→ T and ψ : G × S 7→ S be two actions
of the group G on simplicial trees. Let α ∈ Aut(G) . We say the actions
ϕ and ψ are Aut(G)-equivalent, written ϕ ∼Aut(G) ψ, if there is a simplicial
isomorphism f : T → S and an α ∈ Aut(G) that makes the the following
diagram commutative:
ϕα
G×T
T
1×f
f
ψ
G×S
S
Definition 1.15. Let P, P ′ be patterns in C. We say that the patterns P and
P ′ are Aut(π1 (C))-equivalent, written P ∼Aut(π1 (C)) P ′ if the natural actions
π1 (C)×T (P, C) → T (P, C) and π1 (C)×T (P ′ , C) → T (P ′ , C) are Aut(π1 (C))equivalent.

7

In the case of closed surfaces patterns arise as multicurves and automorphic
equivalence of multicurves coincides with equivalence under homeomorphisms.
For general 2-complexes (which may have trivial mapping class groups) these
equivalences may not coincide.

1.6

The main result

A solution to the word problem in π1 (C) is a procedure that decides if a loop
(given as a sequence of directed edges in C (1) ) is nullhomotopic in C. In the
case where C is a presentation complex such a loop uniquely defines a word in
the prescribed generating set.
Theorem B. There is an algorithm which takes as input a finite 2-complex
C such that π1 (C) has no 2-torsion, a solution to the word problem in π1 (C),
some positive integer κ, a finite collection

S = {hi }i∈In | n = 1, . . . , m

m
of finite generating sets of subgroups H = hhi ii∈In n=1 of π1 (C) and outputs
a finite collection of tracks t1 , . . . , tn(C,κ,S) which lie in a complex CS ⊇ C
(with equality if S = ∅) such that the isomorphism π1 (CS ) ≈ π1 (C) is given
explicitly. These tracks give splittings of π1 (C) relative to H with the following
property: if π1 (C) admits a geometric κ-acylindrical splitting relative to H
represented by a track t then there is some i ∈ {1, . . . , n(C, κ, S)} such that
t ∼Aut(π1 (C)) ti .
This theorem is proved in Section 7.6, where the main algorithm is given.
The 2-complex Cs was defined in Section 1.4.
The result, as stated, is about splittings that are geometric, κ-acylindrical
and with one edge group. This result is not the strongest possible, but it gives
us all the applications we need.
It could be strengthened as follows: by Theorem 1.10 every κ-acylindrical
tree T is resolved by a geometric tree ρ : T (P, C) ։ T . The resolving tree
T (P, C), however, may not itself be κ-acylindrical. The analysis of the relationship between the trees T (P, C) and T in [Del99] combined with the arguments of this paper actually give a finite collection of tracks that resolve
every κ-acylindrical tree. The geometric resolving splittings themselves may
not be κ-acylindrical, but they are “locally” κ-acylindrical in a way that is
good enough for our arguments. Although this would give us a full algorithmic version of Sela’s super accessibility [Sel97, Theorem 4.3] for the class of
κ-acylindrical one edged splittings, we have opted for a simpler formulation;
thus removing a layer of notation. We hope the reader will agree that this is
for the best.
For the sake of simplicity we have also restricted ourselves to one-edged
splitting or tracks, instead of general patterns. This does not weaken the result
because we allow relative splittings which enables us to produce refinements.
Results such as [Wei02, Del99] then give explicit bounds on the number of
components of the pattern.
It should also be noted that Theorem B does not necessarily enable us
to detect whether π1 (C ) actually has a geometric κ-acylindrical splitting. To

8

reach such a conclusion we must be able to further analyze the collection
of tracks produced by the main algorithm. This means we must be able to
solve more delicate algorithmic problems in the ambient group. The next two
applications, especially the proof of Theorem C, will illustrate the necessary
extra requirements.
Finally there is the issue of torsion. The current algorithm cannot handle
actions on trees with arbitrarily long arcs with non-trivial pointwise stabilizers,
even if these stabilizers are finite. Forbidding 2-torsion, for example, controls
a problem that occur with Möbius bands by bounding their width, which
gives terminating conditions. If the algorithm were to run in the presence
of 2-torsion, then it would still produce a (possibly empty) list of tracks and
terminate. However, because the algorithm will have stopped prematurely this
list may be missing some tracks.
There is no reason these torsion issues cannot be overcome. For example,
[DG10] deals with laminations in band complexes with torsion. The author
suspects to solve this problem one would have to generalize band complexes
to some version for 2-orbihedra with finite cell stabilizers.

1.7

Computing Grushko decompositions

This is an application of Theorem B with H = ∅ and κ = 0. In this case we
only need to be able to solve the word problem.
Proof of Theorem A. Let C be a presentation 2-complex form hX | Ri and
consider a maximal splitting of hX | Ri over finite groups. If G admits an
essential free decomposition then by Corollary 1.11 there is a track t ⊂ C that
represents this splitting.
Free decompositions correspond exactly to 0-acylindrical actions on trees.
We now apply the algorithm of Theorem B to get a finite collection of tracks
t1 , . . . , tn .
If there is a track t that represents an essential free splitting of G then t is
Aut(G)-equivalent to some ti in our finite collection. So G admits an essential
free decomposition if and only if some ti represents an essential free decomposition.
With our solution to the word problem we are able to check for each ti if
• Gp(ti ) = {1},
•

– if C \ ti is not connected, then both components of must have non
trivial image in π1 (C) via the inclusion map, or
– if C \ ti is connected, there is nothing to show,

and thus decide if ti represents an essential free decomposition.
We now give another method to decide if a finitely presented group G
with decidable word problem is free (see [GW09].) First note that if we can
solve the word problem, we can decide if a finitely presented group is abelian
(check if the generators commute) and then, by linear algebra, we can compute
its isomorphism type. In particular we can decide if G is isomorphic to Z.

9

We repeatedly apply the algorithm for Theorem A to attempt to compute
the Grushko decomposition of G. If G is 2-torsion-free then this will be the
correct Grushko decomposition. Otherwise we still will obtain some (possibly
trivial) free decomposition of G. We can then decide if each factor of this
decomposition is isomorphic to Z or {1}. This will be the case if and only if
G is free.

1.8

Detecting splittings of relatively hyperbolic groups

For this section we assume that the reader is familiar with relatively hyperbolic
groups. The reader can consult [Far98] or [Hru10] for definitions. Let G be a
finitely presented torsion-free group that is hyperbolic relative to the finitely
generated subgroups H = {H1 , . . . , Hm }. We assume that the groups Hi ∈ H
are pairwise distinct and non-conjugate. Before continuing we need to give
some definitions.
Definition 1.16. An element of g ∈ G (respectively a subgroup K ≤ G)
is parabolic if there exists some h ∈ G such that h−1 gh ∈ Hi (respectively
h−1 Kh ≤ Hi ) for some i ∈ H.
Convention 1.17. We will assume in this section that all algorithms in a
group are with respect to a presentation and that the (tuples of) elements of
the input are given as (tuples of) words in the symmetrized generating set.
Definition 1.18. A splitting of G is elementary if all parabolic subgroups are
elliptic and the edge groups are either trivial, infinite cyclic, or parabolic.

Definition 1.19. A triple hS | Ri, CP, Gen where:
(i) hS | Ri is a finite group presentation,

(ii) CP is an algorithm which solves the the conjugacy problem with respect
to hS | Ri, and
(iii) Gen is an algorithm which decides whether or not a finite tuple generates
hS | Ri
is called an algorithmically tractable triple.
Definition 1.20. A class C of finitely presented groups is called an algorithmically tractable class of parabolics if there is an algorithm which enumerates
algorithmically tractable triples corresponding to the groups in C.
It is worth pointing out that by [BCRS91] the class of polycyclic-by-finite
groups is algorithmically tractable. We now collect some well known facts
about torsion-free relatively hyperbolic groups.

Proposition 1.21 ([Far98, Example 1 p.819]). For all h ∈ G, h−1 Hi h ∩
Hj 6= {1} if and only if i = j and h ∈ Hi .
This next result about elements of G follows from the work in [Bum04] but
is stated explicitly in [Osi06]. The generalization to explicitly given subgroups
of G follows applying Proposition 1.21.

10

Theorem 1.22 (c.f. [Osi06, Theorem 5.6]). Given g ∈ G (respectively K =
hk1 , . . . , kn i ≤ G) if we are given a solution to the conjugacy problem for each
Hi , i = 1, . . . , n then we can decide whether there is some h ∈ G such that
h−1 gh ∈ Hi (respectively h−1 Kh ≤ Hi ) for some i ∈ {1, . . . , n}, and find h if
it exists.
The following two facts are well known, however I couldn’t find any precise
references, they are stated here and proved.
Proposition 1.23. Let g ∈ G be a non-parabolic element. Then its centralizer
C(g) is infinite cyclic and malnormal.
Proof. By Theorems 4.16 and Theorem 4.19, the centralizer C(g) of g is a
word hyperbolic group. By [Aea91, Corollary 3.6], since G is torsion free C(g)
is infinite cyclic. Assume now for simplicity that C(g) = hgi.
Suppose there was some h ∈ G such that h−1 hgih ∩ hgi =
6 {1} then by
[Osi06, Corollary 4.26] there is some l ∈ Z6=0 such that h−1 gl h = g±l . This
means that h2 ∈ C(g l ) and that hgl i is normal in hh, g l i. Now as explained
before hki = C(hg l i) ≥ C(g) = hgi, which implies that k ∈ C(g), so k ∈ hgi;
thus h2 ∈ hgi. From this we get that [hh, g l i : hgl i] ≤ 2l.
Now [Hem76, Lemma 11.4] states that if a group Q contains a an infinite
cyclic subgroup of finite index, then Q contains a finite subgroup K, such that
Q/K is either isomorphic to Z or Z2 ∗ Z2 . If Q ≤ G, then Q is torsion-free;
so K must be trivial and Q must be infinite cyclic. It follows that hh, gl i is
infinite cyclic, say hh, gl i = hzi. Then z ∈ C(g), so in particular h ∈ C(g).
Corollary 1.24. A one edged elementary splitting of a torsion free relatively
hyperbolic group G is 2-acylindrical.
Proof. We first prove the following. Claim: let e be an edge in Bass-Serre T
tree connecting the vertices u, v. Then at least one of the images of Ge ≤ Gu
or Ge ≤ Gv is malnormal.
Indeed, if the splitting in question is free, then the result holds. Suppose
now that the edge group is hgi for some non parabolic g ∈ G. Then hgi must be
maximal cyclic in at least one of its images in the vertex groups, otherwise its
centralizer is not cyclic because in the amalgam hxi ∗xr =ys hyi if r, s 6= 1 then
hxy, y s i ≈ Z ⊕ Z ≤ C(y s ). Also the images of hgi in the associated subgroups
cannot intersect since by [Osi06, Corollary 4.27] any Baumslag-Solitar group
must be parabolic.
Suppose now that the edge group Ge is parabolic, but not maximal parabolic,
and hence malnormal, in either Gu , Gv . Then we have parabolic proper overgroups Ge < Pu ≤ Gu and Ge < Pv ≤ Gv . One one hand since |Pu ∩ Pv | =
|Ge | = ∞ they must lie in a common maximal parabolic subgroup P . On
the other hand P does not act elliptically on T (it has a non-trivial induced
splitting) contradicting the fact that the splitting is elementary. This proves
our claim.
We now prove 2-acylindricity. Let u be a vertex in the Bass-Serre tree
and let e, f be edges such that e ∩ f = {u}. Since e, f are in the same Gorbit we have that Ge , Gf are conjugate. On the other hand if e 6= f then if
Gv ≥ Ge ∩ Gf 6= {1} then Ge is not malnormal in Gv . Suppose towards a

11

contradiction that there is some g ∈ Ge such for some edge h ⊂ T such that
e ∩ h = ∅ we have g · h = h, and suppose moreover that there is some edge
f ⊂ T such that e ∩ f = {u} and f ∩ h = {v}. Then we must have that
g ∈ Ge ∩ Gf ∩ Gh . g ∈ Ge ∩ Gf implies that Gf is not malnormal in Gu which
means by our earlier claim that Gf must be malnormal in Gv so Gf ∩Gh = {1}
contradiction. Therefore no element of G \ {1} fixes an arc of T of length more
than 2.
We finally need the following.
Theorem 1.25 (Theorem 3 of [DG13]). There exists an algorithm as follows.
It takes an input of a finite presentation of a group G, a solution to its word
problem, and a recursive class of finitely presented groups C (given by a Turing
machine enumerating presentations of these groups).
It terminates if and only if G is properly hyperbolic relative to subgroups
that are in the class C.
In this case, the algorithm outputs an [relative linear] isoperimetry constant
K [in the sense of [Osi06, Definition 2.30]], a generating set and a finite
presentation for each of the parabolic subgroups.
Now we have our second application.
Theorem C. Suppose we are given a finite presentation hX | Ri of a torsion
free group G that is relatively hyperbolic with finitely many parabolics that
lie in an algorithmically tractable class of parabolics C. Suppose also that we
are given a solution to the word problem with respect to hX | Ri and a finite
collection S of finite generating sets for a set of subgroups H′ . Then we can
decide if G admits an elementary splittings relative to H′ .
Proof. We first note that by Theorem 1.10 if C is the presentation 2-complex
associated to hX | Ri, then G admits an essential elementary splitting if and
only if π1 (C) admits an essential elementary geometric splitting. Any elementary splitting is, by Corollary 1.24, 2-acylindrical.
We first run the algorithm of Theorem 1.25 to find the finite collection
{H1 , . . . , Hn } (given by generating sets in hX | Ri) of parabolic subgroups we
then apply the algorithm of Theorem B with κ = 2 and
H = H′ ∪ {H1 , . . . , Hn }
with the collection of generating sets S. This gives us a finite collection of
tracks t1 , . . . , tn(C,κ,S) that lie in CS . It is now enough to check for each of
these tracks if they represent an essential elementary splitting. Let t be one of
these tracks. By Theorem 1.22 we can decide if Gp(t) is parabolic.
If Gp(t) is trivial then as in the proof of Theorem A we can decide if it
gives an essential splitting.
Suppose now that Gp(t) isn’t parabolic. Since we can solve the word problem we can check whether Gp(t) is abelian, if it isn’t then it certainly cannot
represent an elementary splitting. Otherwise Gp(t) is abelian. By Proposition
1.23, Gp(t) is contained in the centralizer of some non-parabolic element and
is therefore contained in a non-parabolic maximal cyclic group. If t is a nonseparating track then it gives an essential elementary splitting. Otherwise t

12

separates CS , and G splits as a free product with amalgamation over Gp(t). To
check if the splitting is essential it suffices to check, using the word problem,
whether the generators of the vertex groups commute with Gp(t). Indeed,
since we are assuming that Gp(t) is non-parabolic, we can assume that the
vertex groups are non-parabolic; so by Proposition 1.23 if one of the vertex
groups commutes with Gp(t) then it is at most a finite index cyclic overgroup
of Gp(t). Deciding if the vertex group coincides with Gp(t) can now be solved
using item 3) of Theorem 1.16 of [Osi06].
Suppose finally that Gp(t) is parabolic. Again, if t is non-separating the
splitting is essential. Otherwise the splitting is essential if and only if Gp(t)
doesn’t equal one of the vertex groups. If neither of the vertex groups are
parabolic then the splitting is essential. Otherwise at most one of the vertex
groups is parabolic and we can decide if it is generated by Gp(t) using Theorem 1.22 and our solution to the generation problem given by the algorithmic
tractability assumption (Definition 1.19 (iii)).

2

Band complexes

The algorithm of Theorem B is a procedure that will produce a rooted directed
tree (i.e. a branching sequence) of band complexes. Band complexes first
appeared in [BF95] to classify stable actions of finitely presented groups on
R-trees. Our version of band complexes differ in that they are combinatorial
objects: they do not come with laminations, instead we will allow a band
complex to carry multiple laminations or, in our case, tracks.
As combinatorial objects, our band complexes will contain the same amount
of information as Makanin’s generalized equations (c.f. [KM98].)

2.1

Definitions and terminology

Definition 2.1. A band B is a Cartesian product JB × [−1, 1] where JB homeomorphic to a closed interval. The subsets JB × {±1} are called bases. If
µ = JB × {±1} is the base of a band then we call the base µ = JB × {∓1} the
dual of µ.
A band is therefore a rectangle with well-defined bases and a vertical direction.
Convention 2.2. The letters λ, µ, η, ν shall be used to denote bases and λ will
always denote the dual of λ. We shall denote by B(λ) the band that contains
λ.
Definition 2.3. A band complex C is a 2-complex that is constructed in the
following way:
(1) Start with a simplicial graph Γ.
(2) Attach the bases of the bands B1 , . . . Bm to the interiors of edges of Γ via
embeddings
gµi : µi ֒→ Γ \ Γ(0)
where the {µi } is the set of bases of the bands.

13

(3) Let


U = Γ ∪ B1 ∪ . . . ∪ Bm / ∼

be the resulting identification space. We finally obtain C by attaching
discs D1 , . . . , Dl via immersions fi : ∂Di # U with the following requirement:
(a) For all i, j, fi (∂Di ) ∩ Bj can be expressed as a finite union of embedded arcs αi that travel from one base of Bj to the other. Such arcs
are called connections.
(b) Connections are pairwise disjoint.
(c) If a connection has non-trivial intersection with a side of a band Bj ,
then it coincides with that side.
In the case of measured band complexes [BF95] the complicated requirement 3 above on the 2-cell attaching map is ensured if the 2-cell attaching
maps intersect measured bands in vertical subsets.
Connections (as described in items (3a)-(3c) of the definition above) will occur exactly where boundary connections occur when working with generalized
equations (see for example [KM98].) Controlling their cardinality is a key step
in the repetition argument which deals with the thinning and superquadratic
cases of the elimination process (Section 4.8.)
Convention 2.4. Although a band complex is a 2-complex, whenever we
mention a 2-cell we really mean a 2-cell Di that gets attached in step 3. of
Definition 2.3.
Thus, it is possible that a 2-cell Di in a band complex never intersect any
bands, in which case the image of the attaching map fi (∂Di ) lies entirely in
the underlying graph Γ in item (1) of Definition 2.3.
Convention 2.5. Formally speaking, a base µ isn’t a subset of the band
complex C . That being said we will still write x ∈ µ for some point x ∈ C
such that x ∈ gµ (µ). We will also write λ ⊂ µ if gλ (λ) ⊂ gµ (µ). In the case
where gλ (λ) = gµ (µ) we will use the evocative symbol λ + µ to avoid confusion.
We will also treat the bands Bi as subsets of C when it is convenient.
Definition 2.6. We say that bases µ, µ are matched bases if µ + µ and B(µ)
forms an annulus in C . Otherwise a base is called unmatched.
S
Definition 2.7. A union of unmatched bases U = Sµ∈S µ is called strongly
connected if the union of the interior of the bases U ′ = µ∈S interior (µ) is also
connected (and therefore an interval.) A maximal (with respect to inclusion)
strongly connected union of unmatched bases is called a maximal section.
Maximal sections are almost the blocks in [BF95] and the closed sections
in [KM98].
Definition 2.8 (Carrying a track). Let C be a band complex and let t ⊂ C
be a track. C carries t if t is contained in the union of the bands in C and
furthermore,

14

(i) For each band Bj , t ∩ Bj consists of a union of pairwise disjoint embedded
arcs travelling from one base of Bj to the other, and
(ii) Bj ∩ t is disjoint from the connections in Bj as well as from its sides.
Definition 2.9 (Efficiently carrying). For a base µ, let Sµ ⊂ µ be the finite
set containing the points the form x = µ ∩ c, where c is a connection, and the
points x that are the endpoints of bases. C carries t efficiently if for every
base µ and every distinct x, y ∈ Sµ there is some point in t ∩ µ that separates
them.
Thus, if a C carries a track t, then t is confined to the interior of the
bands. The notion of carrying naturally generalizes to arbitrary measured
laminations, but since we will only be focusing on one leaf laminations we only
need to deal with the hitting measure.
Definition 2.10 (Measure from a track). Let C be a band complex, let t
be a track carried by C , and let S ⊂ C be a union of bases. We define the
hitting measure on S with respect to t, denoted |S|t , to be the cardinality of
the intersection
|S|t = |S ∩ t|.
If µ is a base of C then we will sometimes call |µ|t the length of µ with respect
to t.

2.2 Constructing (measured) band complexes from
tracks
Let C be a standard CW 2-complex and let t ⊂ C be a track. We obtain a
band complex C from C as follows.
For each 2-cell D ⊂ C, t ∩ D is a disjoint union of arcs travelling from one
edge of ∂D to another edge of ∂D. Metrize the 1-skeleton C (1) , giving each
edge ei a length of |ei ∩ t| + 2. Subdivide each 2-cell D into a union of bands
and 2-cells, such that a base µ has length |µ∩t| = |µ|t . Explicitly parameterize
each band
B(µ) = [0, |µ|t ] × [−1, 1],
so that t ∩ B(µ) ∩ t is a union of vertical sets as follows:
|µ|t

t ∩ B(µ) =

[

1
{i − } × [−1, 1];
2

i=1

this is illustrated in Figure 2.
This construction gives a band complex as in Definition 2.3. The underlying
graph is the 1-skeleton C (1) , the bases of the bands are embedded in this
graph and avoid the vertices C (0) . We further see that the remaining 2-cells
have embedded (thus, immersed) boundaries that only intersect bands in their
vertical sides. Furthermore, since no 2-cell attaching maps go through the
interior of any of the bands, t is efficiently carried by the band complex C .

15

2
1
3

Figure 2: On the left, the intersection of a track t with a 2-cell U
in a 2-complex. On the right how to construct the corresponding
measured band complex efficiently carrying t by dividing U into
three bands and four 2-cells.
Definition 2.11. A band complex C is measured if every base µ is metrized
as a real closed interval [0, |µ|t ] (recall Definition 2.10). A subset v of a band
B(µ) = [0, |µ|t ] × [−1, 1] is called vertical if it is of the form
v = {xv } × [−1, 1].
We have proved:
Proposition 2.12. For any track t contained in a 2-complex C, we can subdivide C into a measured band complex C in which t consists of a union of
vertical sets. Moreover C carries t efficiently.
Definition 2.13 (Combinatorial equivalence of band complexes). Two band
complexes C and C ′ are said to be equivalent if there is a homeomorphism
C → C ′ that sends the underlying simplicial graph (Definition 2.3 (1)) to the
underlying simplicial graph, sends bands to bands, sends 2-cells to 2-cells, and
for each of these objects restricts to a homeomorphism.
If we forget the measures on band complexes, we are left with only finitely
many possibilities; thus,
Proposition 2.14. Let C be a finite 2-complex and let S be a finite collection of finite subsets of π1 (C). Then there are only finitely many possible
band complexes (up to the combinatorial equivalence of Definition 2.13) that
arise from the possibly infinite collection of tracks t ⊂ CS (Proposition 1.13.)
Furthermore this list can be effectively constructed.

3

Moves on band complexes carrying tracks

We will present moves that transform a band complex carrying a track into
a new band complex carrying a new track. These moves are essentially the
moves given in [BF95, §6.1]. Our treatment is slightly different since we want
to explicitly realize each move as a continuous map m : C → C ′ sending the
track t to some track t′ ⊂ C ′ , which we denote (C , t) → (C ′ , t′ ). This is
accomplished with the zipping moves. They will be of use in a later section.
We will employ the convention of [KM98] and reuse the names of bases, as
is customary in computer science.

16

3.1 The basic moves on band complexes that carry
a track
Let C be a band complex efficiently carrying a track t. Suppose furthermore
that C is measured (Definition 2.11) so that a base µ is metrized with length
|µ|t and t ⊂ C is a union of vertical sets.
We first define elementary moves (C , t) → (C ′ , t′ ) which transform the
underlying band complex and track, while preserving the fundamental group
and dual Bass-Serre tree T (t, C ). These moves are actually π1 -isomorphic
continuous maps C → C ′ that map t to t′ .
Definition 3.1 (Type I zip). Suppose we have a containment of bases λ ⊂ µ
with λ ∩ µ = ∅ and λ ∩ µ = ∅. The union of U vertical sets of B(µ) that
intersect λ is a rectangle homeomorphic to B(λ). A type I zip of B(λ) into
B(µ) consists of the operation of identifying B(λ) to U so that vertical sets are
sent homeomorphically to vertical sets and λ is identified to the corresponding
subset of µ.
Definition 3.2 (Type II zip, or squish). Suppose we have the containments
of bases λ ⊂ µ and λ ⊂ µ. Suppose furthermore that there are vertical paths
α ⊂ B(λ) and β ⊂ B(µ) such that the concatenation α ∗ β is a nullhomotopic
loop. A type II zip of B(λ) into B(µ) is the operation of continuously identifying
α to β and continuously extending this to an identification of B(λ) to a union
of vertical subsets of B(µ). This identification map must be injective when
restricted to B(µ) and B(λ) and must send vertical sets to vertical sets.

→

←

Figure 3: Type I and Type II zips. The identifications must send
tracks to tracks.
These zipping moves are not used in [BF95], but the type I zip is a step
in the transfer (see Definition 3.10 later) or M4 Slide of [BF95]. The zipping
moves will be necessary later when we will be “wrapping one band around another” (see Figure 19.) Also the fact that they are given by explicit continuous
maps is convenient.
Definition 3.3 (Collapse a band). Let B(µ) be a band such that µ ∩ µ = ∅.
Then the collapse of B(µ) onto µ is the operation of identifying each vertical
subset v that intersects interior (µ) to the point xv = v ∩ µ.
Definition 3.4 (Annulus). An annulus A is a band B(µ) such that µ + µ
whose image in the band complex C is homeomorphic to an annulus.
This next move is similar to the type II zip.

17

Definition 3.5 (Crush an annulus). Let A ⊂ C be an annulus such that
Gp(A) = {1}, then crushing A is the operation of identifying each vertical
subset of A to its intersection with µ.
Definition 3.6 (Vertically subdivide a band). Let B = [a, b]×[−1, 1] be a band
in C and let {p} × [−1, 1] be a vertical subset. The operation of subdividing B
along {p} × [−1, 1]. Consists of the following operations:
(1) Cut B along {p} × [−1, 1] so that we get two bands B1 = [a, p− ] × [−1, 1]
and B2 = [p+ , b] × [−1, 1].
(2) Attach a 2-cell along the loop (p− × [−1, 1]) ∗ (p+ × [−1, 1]), where ∗
denotes concatenation. This 2-cell is called a subdivision digon.
Convention 3.7. We only allow band subdivision of (t, C ) if the resulting
t′ ⊂ C ′ is efficiently carried.
These basic operations may leave some messiness behind:
(i) After performing a zipping move a 2-cell may no longer have an immersed
boundary.
(ii) After a collapse a 2-cell may have a free face and perhaps the resulting
band complex can be given as C = C ′ ∗p α, i.e. the connected sum at a
point p of a band complex C ′ and a closed arc α.
(iii) After crushing an annulus, or performing a type II zip, the boundary of
a 2-cell may map onto a point or an interval resulting in a sphere.
We therefore introduce, as basic moves, the following cleaning operations.
Definition 3.8 (Delete superfluous cells). If a 2-cell in C is a sphere, as may
occur in (iii) above, or if it has a free face, remove it. Do the same for hanging
arcs that occur in (ii) above.
Definition 3.9 (Tighten 2-cells). If a 2-cell D no longer has an immersed
boundary then the attaching map fD : ∂D → C factors as
 f′
∂D ։ S 1 ∗pi τi # C ,

(4)

where the middle term is a circle with some hanging trees τi , which arise from
the “pinching” of the attaching map. This middle term is immersed into C .
We replace D by a 2-cell D ′ whose boundary is identified with S 1 in (4) and
mapped to C \ D (abusing notation) via the immersion f ′ in (4). D ′ is called
the tightening of D.
We leave it to the reader to verify that the result of a 2-cell removal and the
tightening move C → C ′ can be realized by a continuous map. The transfer,
given below and illustrated in Figure 4 is defined in terms of band subdivisions
and zipping, but we will also treat it as an elementary move.
Definition 3.10 (The transfer). Let µ ⊂ λ be bases such that µ 6= λ. The
operation of transferring µ from λ to λ across B(λ) is the following sequence
of operations.

18

(1) Subdivide the band B(µ) horizontally:
B(µ) = B(µ− ) ∪ B(µ+ )
with µ + µ− , µ− + µ+ , and µ+ + µ.
(2) Zip the band B(µ− ) into B(λ). (By hypothesis, this is a type I zip.)
(3) We rename the base µ+ as µ.

µ+

µ
µ

λ

λ

µ

µ−

λ

µ

Figure 4: Transferring µ from λ to λ across B(λ). The dotted
line shows a connection (Definition 2.3(3a)). After a transfer this
connection may give rise to two connections.

3.2

The preservation property

We will now give a preservation result for our moves. This result is stated as a
fact at the beginning of [BF95, §6]. In order to lay out the terminology that is
necessary for our purposes, we will carefully state and prove the preservation
property.
Proposition 3.11 (The preservation property). Let m : (C , t) → (C ′ , t′ ) be
one of the basic moves given in Section 3.1. Then we have an isomorphism of
fundamental groups
∼
m♯ : π1 (C ) → π1 (C ′ )
and a simplicial isomorphism of dual Bass-Serre trees mT : T (t, C ) → T (t′ , C ′ )
induced by m. Furthermore this map is m♯ -equivariant in the following sense,
letting π1 (C ) act naturally on T (t, C ) by deck transformations via the quotient
map π (Proposition 1.6((2)), we have
m♯ (g) · mT (x) = mT (g · x),
for all g ∈ π1 (C ) and all x ∈ T (t, C ).
Proof. We first show prove the proposition for zipping, collapsing and crushing
moves.
We first show that the fundamental groups are isomorphic. Consider first
either a type I Zip (Definition 3.1) of B(λ) into B(µ) (i.e. with λ ⊂ µ) or the
collapse of B(µ) onto µ (Definition 3.3). These moves lift to π1 (C )-equivariant
moves on on Ce. Pick a basepoint x ∈ µ ⊂ C , by the disjointness criteria
we see that no distinct lifts of x in Ce are identified and that the resulting
f′ remains simply connected. Since the lifts of x in Ce are in bijective
complex C
correspondence with π1 (C ), the isomorphism π1 (C ) ≈ π1 (C ′ ) follows.

19

In the case of a type II zip (Definition 3.2) or an annulus crush (Defini] B(λ)
] of
tion 3.5) the π1 -triviality criteria ensure that we can find lifts B(µ),
] ∪ B(λ)
] is as in the right side of Figure
B(λ), B(µ) (respectively) such that B(µ)
e
3, or that the annulus A(µ) lifts to C . Arguing as before (taking a basepoint
in µ) we obtain the isomorphism π1 (C ) ≈ π1 (C ′ ).
In all cases the moves map bands to (interiors) of bands, and vertical sets
to vertical sets. Also points in the complement of the union of bands of C are
sent to the complement of the union of band of C ′ , and the restriction to the
complement is injective. Lifting to Ce we therefore see a bijective correspondence between the connected components of e
t and te′ . Furthermore if connected
components t1 , t2 ⊂ e
t are dual to edges that share a vertex in T (t, C ), then
their images t′1 , t′2 will be dual to edges in T (t′ , C ′ ) that share a vertex. The isomorphism of Bass-Serre trees follows, and m♯ -equivariance of the isomorphism
follows from construction.
The proof for band subdivisions, superfluous 2-cell deletions, and tightenings is obvious.

3.3

Derived moves

Having defined basic moves we shall now define the composite, or derived,
moves that constitute the Rips machine. We first introduce the τ -complexity
(originally Makanin’s ξ-complexity [Mak82]), which is one of the main tools of
our analysis. As we define the derived moves we will show why they do not
increase this τ -complexity.
Definition 3.12. Let σ ⊂ C be a maximal section (Definition 2.7), let b(σ)
be the number of unmatched bases contained in σ. We define the τ -complexity
of a section to be

τ (σ) = max b(σ) − 2, 0

Definition 3.13 ([BF95, Definition 4.3], [KM98, §5] ). Let J ⊂ C be a union
of maximal sections, then we define the J-relative τ -complexity to be
X
τ (C , J) =
τ (σ).
(5)
σ6⊂J

If J = ∅ write τ (C ) instead of τ (C , ∅).
Definition 3.14. For a point x ∈ µ we denote by γ(x) the number of unmatched bases λ such that λ ∋ x.
Definition 3.15. The vertical length of the attaching map ∂D # C of a 2-cell
D is the number of connected components of the preimages of the connections
((3a) of Definition 2.1.) Equivalently, this is the number of times the attaching
map travels through a band.

3.3.1

The Möbius move

Definition 3.16. A dual pair (µ, µ) such that µ + µ and B(µ) forms a Möbius
band is called a Möbius pair.

20

This next move is described in [BF95, Lemma 6.4]. Note that since we
require tracks to be two-sided, a track t ⊂ C can never intersect the core of a
Möbius band. It follows that we can always subdivide a Möbius band along
its core and the resulting band complex will still efficiently carry t.
Definition 3.17 (The Möbius move). Given a Möbius pair (µ, µ), we subdivide the band B(µ) = µ × [−1, 1] along {m} × [−1, 1], the core of the Möbius
band. Call the resulting bands B(µ0 ) and B(µ1 ). We then transfer the base
µ0 across the band B(µ1 ). The dual pair (µ0 , µ0 ) now forms an annulus A(µ0 )
and the pair µ1 , µ1 intersect at a point. If the annulus A(µ0 ) is π1 -trivial, we
crush it. We rename µ1 , µ1 as µ, µ respectively.
Straightforward verification gives the following result:
Lemma 3.18. Let (C , t) be a band complex efficiently carrying a track. Let
(µ, µ) form a Möbius pair. After the corresponding Möbius move m : (C , t) →
(C , t′ ) we have the following:
(i) The hitting measure of µ drops by a half, i.e.
1
|µ|t′ = |µ|t .
2
(ii) The hitting measure of |µ|t′ is the same as the measures of the matched
base |µ0 |t′ .
(iii) The τ -complexity did not increase.

3.3.2

The thinning move

The thinning move is applied whenever there is some point x in a base µ such
that γ(x) = 1 (Definition 3.14). In [BF95] this is the move for Process I, but
modified to keep the number of unmatched bases non-increasing (we prevent
the “long bands” of [BF95] from occurring.) In [KM98] this is the move applied
in cases 7-10.
Definition 3.19. Let x ∈ µ be a point such that γ(x) = 1. Let x ⊂ µ0 ⊂ µ
be the maximal segment that contains only points x′ with γ(x′ ) = 1. We call
µ0 a maximal naked segment.
Suppose that a base µ contains a naked segment we now describe the
thinning move starting at µ:
(1) Subdivide µ. subdivide µ into segments
µ = µ−1 ∪ µ0 ∪ µ1
with µ−1 or µ1 possibly empty, and µ0 a maximal naked segment of µ.
This results in a subdivision of B(µ). Denote by D−1 and D1 be the
added subdivision digons.
(2) Subdivide annuli and clean µ0 . For every matched base pair (λ, λ) such
that λ intersects interior (µ0 ) vertically subdivide
B(λ) = B(λ−1 ) ∪ B(λ0 ) ∪ B(λ1 )

21

so that λ0 ⊂ µ0 and λ±1 doesn’t intersect interior (µ0 ).
Next, take all the resulting base pair (λ0 , λ0 ) with λ0 ⊂ µ0 and transfer
λ0 and λ0 from µ0 to µ0 through B(µ0 ). Now µ0 doesn’t intersect any
other bases.
(3) Collapse the naked segment and the added subdivision digons. Collapse
the band B(µ0 ) onto µ0 . Delete the subdivision digons D−1 , D1 that were
added in Step 1 since they now have free faces.
(4) Remove long bands. A long band is a union of two bands
B(µ) ∪ B(λ)
with µ + λ. If a long band is created, first transfer µ, and all other bases
contained in λ, from λ to λ through B(λ) and then collapse the band
B(λ) onto λ.
(5) Clean up. Crush any remaining π1 -trivial annuli.
A proof of this next fact for generalized equations can be found in [KM98],
instead of adapting it we simply give another proof.
Lemma 3.20. After applying a thinning move starting at a base µ, the τ complexity did not increase. If no annuli were subdivided, the number of 2-cells
did not increase, nor did the vertical lengths of 2-cell attaching maps.
Proof. From (3), the number of 2-cells did not increase, if no annuli were
subdivided. Furthermore, since the only transfer move is immediately followed
by a collapse of the transfer band, the vertical lengths of 2-cell attaching maps
could not increase.
It remains to show that the τ -complexity doesn’t increase. Suppose that
we performed (2), so that µ0 doesn’t intersect any other bases (we could also
do (1), (2) and then recombine the bands created in (1).) Then the number
of maximal sections may have increased, but the number of unmatched bases
did not; thus the τ -complexity did not increase.
Let σ be the maximal section containing µ and σ ′ the maximal segment
containing µ, after the subdivision of matched bases.
Suppose first that µ is completely naked (i.e. µ0 = µ). Then (1) doesn’t
occur and after the collapse of B(µ) in (3), the total number of unmatched
bases goes down by 2. It therefore clearly follows from Definition 3.13(5) that
the τ -complexity decreased.
Suppose now that µ gets subdivided into 2 segments µ0 , µ1 . Take σ to
be co-initial with µ0 . After (1) and (2) σ gets subdivided into σ0 , σ1 with
b(σ0 ) = 1 and b(σ1 ) = b(σ). In σ ′ the base µ gets replaced by µ0 ∪ µ1 this
increases b(σ ′ ) by 1 (Definition 3.13(5)), but in (3) we collapse B(µ0 ) onto µ0 ,
this deletes µ0 from σ ′ so b(σ ′ ) goes back down.
Suppose finally that µ gets subdivided into µ−1 , µ0 , µ1 . After (1) the maximal section σ gets split into σ−1 , σ0 , σ1 . With b(σ0 ) = 1 and b(σ±1 ) ≥ 2.
If we look at the contribution of what is left of σ we have a decrease in the
contribution of τ -complexity of at least

τ (σ) − τ (σ−1 ) + τ (σ0 ) + τ (σ1 ) ≥ 1.

22

On the other hand if we look at σ ′ we see that µ gets subdivided into three
bases and µ0 gets deleted after the collapse in( 3) we therefore have an increase
in the contribution to the τ complexity of resulting sections that constitute
σ ′ , which may have been subdivided, is at most τ (σ ′ ) + 1, thus the total τ complexity did not increase.
Note further that in all the cases above, if we were working with a J-relative
complexity, with µ ⊂ J then the J-relative τ complexity also did not increase.

B(µ)

B(µ−1 )

B(µ1 )

Figure 5: A thinning move (the 2-cells are not shown)

3.3.3

The entire transformation

This is the entire transformation given before [KM98, Case 12], it also constitutes the move used in Process II in [BF95]. One of the disadvantages of the
topological setting is that dealing with closures of maximal sections is awkward, due to the fact that endpoints of bases can lie in the closures of distinct
maximal sections.
Definition 3.21. An ordering < on a band complex C is an ordering < on
the union U of maximal sections (Definition 2.7) that is compatible with some
embedding U ֒→ R. An unmatched base µ whose interior is <-coinitial is
called a leading base. An endpoint of µ is called initial (terminal) if it is the
limit of a <-decreasing (<-increasing) sequence of points in interior (µ).
Convention 3.22. Band complexes will always be assumed to be equipped
with an ordering.
We now describe the entire transformation with carrier µ. Let µ be a
maximal leading base.
(1) Subdivide matched bases. If the base µ intersects any annuli A(λi ), we
vertically subdivide them so that the resulting annuli are either contained
in µ or do not intersect the interior of µ.
(2) Move bases to the right. Transfer every other leading base λ ⊂ µ (except
µ) onto µ through B(µ).
(3) Collapse the naked initial segment. Let µ0 be closure of the <-coinitial
maximal naked subsegment of µ. Subdivide B(µ) into B(µ0 ) ∪ B(µ1 ).
Denote by D1 the added subdivision digon. Collapse B(µ0 ) onto µ0 and
delete D1 because it has a free face.

23

(4) Rename and clean up. We rename µ1 as µ and and crush any π1 -trivial
annuli.
Definition 3.23. The leading base µ given in the definition of the entire
transformation is called the carrier base.
An illustration of the result of an entire transformation is given in Figure
7. This next result follows from a counting argument.
Lemma 3.24 ([BF95, Proposition 7.5]). After applying an entire transformation the τ -complexity did not increase.
Unlike in the thinning case, the vertical lengths of 2-cell attaching maps
may increase.

3.4

The Rips machine

The Rips machine, which was first described in [BF95], is a geometric adaptation of Makanin’s algorithm which takes an measured band complex C and
produces a sequence called the Rips sequence:
C = C0 → C1 → . . .
of measured band complexes, constructed inductively. We assume that C is
equipped with an order <, as given in Definition 3.21.
Lemma 3.25. Let C be equipped with an order < and let m : (C , t) → (C ′ , t′ )
be a Möbius move, a thinning move or an entire transformation. Then there
is a natural induced order <′ on C ′ .
Proof. A Möbius move may split a maximal section σ (i.e. delete a point) into
two maximal sections σ0 , σ1 < therefore restricts to <′ on the new union of
maximal sections.
Denote by U, U ′ the union of maximal sections in C , C ′ , respectively. If a
thinning move is applied, then some maximal base is collapsed onto its dual
so that C → C ′ is actually a retraction. It follows that after splitting some
maximal sections the restriction U → U ′ is also a retraction, so there is a
natural restriction C ′ . For entire transformations, the initial subdivisions and
transfers will at most split U into more open intervals. This is immediately
followed by a collapse, so there is a well defined <′ as before.
We now describe the Rips sequence for C induced by a track t efficiently
carried by C .
(1) Crush any π1 -trivial annuli and delete any superfluous 2-cells.
(2) If there is point Ci with γ(x) = 1, we apply a thinning move collapsing
the <-minimal maximal naked segment (Definition 3.19), to obtain Ci+1 .
(3) Otherwise, if there are any unmatched bases
(a) if possible, apply a Möbius move on a <-minimal Möbius band, or
(b) apply an entire transformation, then

24

tighten all 2-cells attaching maps.
(4) Once all the bases are matched stop.
We note that our choice of ordering < on C is by no means canonical.
However once it is made, the Rips sequence becomes deterministic.
Proposition 3.26. Let t ⊂ C be a track in a 2-complex and let C be the
corresponding measured band complex given in Proposition 2.12. Then after
finitely many steps the Rips machine terminates on a band complex (CT , tT ),
with all bases matched and coinciding. The interior of the union of the bases
is a regular neighbourhood of tT homeomorphic to t × (−1, 1), t is a wedge sum
of circles, and there are no connections in the interior of the bands.
Proof. Since all bases start off with finite integer valued length, the Rips machine eventually stops since every step decreases the length of some base by a
positive integer.
All bases are matched, and they must all coincide, since tT is connected
and it’s efficiently carried by CT . Now, because all the bases are matched, if
µ is any base |µ|tT , the number of connected components of tT , must equal 1.
Efficient carrying also excludes the possibility of connection in the interior of
a band.
Proposition 3.11 implies that the final dual Bass-Serre tree T (tT , CT ) is
π1 (C )-equivariantly isomorphic to the original T (t, C). The following definition is important for the next section
Definition 3.27. A band complex C is in terminal form if it is as described
in conclusion of Proposition 3.26, see Figure 6

Figure 6: A band complex in terminal form, i.e. all bases are
matched. As a graph of spaces, the edge space is clearly visible.
There is a unique track, drawn in black, that efficiently carried by
this band complex. (Recall that tracks are connected by definition.)

4

The elimination process

We will now turn our attention to the set of all tracks that are efficiently
carried by a band complex.
Let C be a band complex equipped with an ordering < on the union of
maximal sections (Definition 3.21). Then, given a track t ⊂ C , the Rips

25

machine (Section 3.4) will perform a specific derived transformation (C , t) →
(C ′ , t′ ). The type of transformation, either an annulus crush, a thinning move,
a Möbius move, or an entire transformation, is determined by C and the
ordering <, but not the track t it carries.
Although the type of transformation doesn’t depend on the track t carried
by C , the combinatorial equivalence class of the resulting C ′ does depend
on the track t. For example consider Figure 7 which shows two different
combinatorial outcomes coming from two different tracks carried by the same
band complex. Seeing as we want to study the set of all tracks carried by C

η

δ
µ
µ

ρ

λ

δ
◮

µ
◮

η
◮
µ
◮
η
◮

µ
◮
λ
◮

µ
◮
ρ
◮

δ
◮
λ
◮

ρ
◮
η
◮
µ
◮

µ
◮

δ
◮
λ
◮

ρ
◮

Figure 7: Two different tracks carried by the same band complex
C give distinct combinatorial outcomes after applying an entire
transformation (see Section 3.3.3.) Here the carrier µ moves base
δ onto its dual. The base diagrams illustrate the ordering < (see
Definition 3.21) on the union of maximal sections.
we must consider all these combinatorial outcomes simultaneously.

4.0.1

The elimination tree T(C)

Given a band complex C with a track t ⊂ C , the Rips machine gives a sequence
(C , t) → . . . → (CT , tT ) with (CT , tT ) in terminal form. If we want to consider

26

all tracks carried by C , then we must have a branching sequence or, in other
words, a rooted directed tree.
Definition 4.1. Let C be a band complex. Denote by tracks(C ) the set of
tracks efficiently carried by C .
Definition 4.2 (Combinatorially equivalent derived transformations). Let t1
and t2 be two tracks efficiently carried by a band complex C . The derived
transformations (C , t1 ) → (C1′ , t′1 ) and (C , t2 ) → (C2′ , t′2 ) are combinatorially
equivalent if there is a commuting homeomorphism e
C
C1′

e

C2′

that is a combinatorial equivalence of band complexes in the sense of Definition
2.13.
Convention 4.3. In section 3.4 it was convenient to consider band complexes
as being measured in order to precisely describe continuous quotient maps.
For the rest of the paper, unless stated otherwise, band complexes C without
tracks will be considered equal if they are combinatorially equivalent in the
sense of Definition 2.13.
The entire transformations shown in Figure 7 are not combinatorially equivalent. We note that, in the notation of the above definition, the tracks
t′1 , t′2 need no longer give combinatorially equivalent derived transformations
of C1′ = C2′ .
Definition 4.4 (Derived transformations of a band complexe). Let C be a
band complex equipped with an ordering < of the union of its maximal sections
(Definition 3.21). For every t ∈ tracks(C ) there is a corresponding derived
transformation (C , t) → (C ′ , t′ ) with resulting band complex C ′ . The type of
this transformation, either an annulus crush, a Möbius move, a thinning move,
or an entire transformation, depends on the underlying band complex C (and
the ordering). Let C1 , . . . , Cn denote the finite set of combinatorial equivalence
classes of the resulting band complexes. A derived transformation of a band
complex C is the operation that produces the finite collection of continuous
maps
C
C1

···

Cn .

(6)

We remark that we can algorithmically construct the set C1 , . . . , Cn .
Lemma 4.5. The if < is an ordering on C then all its children obtained by a
derived transformation have well-defined induced orderings.
Proof. The induced ordering given in Lemma 3.25 does not depend on the
track, only on the continuous map between the underlying band complexes.

27

Convention 4.6. For the rest of the paper, unless stated otherwise, we will
assume that a band complex C comes equipped with such an ordering < of
the union of its maximal sections.
The elimination process for a 2-complex C is the construction of the elimination tree T(C), a directed rooted tree defined inductively as follows:
(0) The root of T(C) is the polygonal complex C.
(1) The set of children of C is the finite collection of band complexes C1 , . . . , CnC
provided by Proposition 2.14 that can efficiently carry all tracks of C. For
each Ci , 1 ≤ i ≤ nC , we equip the union of maximal sections (Definition
2.7) with an ordering < as in Definition 3.21.
(2) If a band complex Cv in T(C) is in terminal form (Definition 3.27), then
it is called a terminal leaf.
(3) If a band complex Cv in T(C) can not be brought to terminal form via
derived moves because the union of the bands is not connected or all
bases are matched, but there are 2-cell attaching maps that intersect the
interior of the bands, then it is a called an inadmissible leaf.
(4) Otherwise we continue to grow T(C) at a band complex Cv by adding its
descendants with a derived transformation (Definition 4.4.) Equip the
union of bases of each descendant Cv′ of Cv with the induced order <
given by Lemma 4.5.
As will be explained in the next section T(C) gives a way to encode the set
of tracks that can lie in the polygonal complex C. It follows that in general it
is infinite.

4.1 The sets of tracks in a band complex organized
by open neighbourhoods.
Lemma 4.7. Let C → C ′ be one of the continuous maps of the derived transformation on C (Definition 4.4 (6)). Suppose that C ′ is equipped with a measure (Definition 2.11.) Then there is a well-defined pullback measure on C .
Furthermore, as long as the union of the interiors of the bands in C ′ is connected, the maximal measure of each base µ of C is no more than the sum of
the measures of the bases in C ′ that are in the image of µ via the map C → C ′ .
Proof. It is now enough to consider the basic moves in Section 3.1, i.e. the
zips, collapses, annulus crushes, vertical and horizontal subdivisions. In all
cases given such a transformation Cˆ → C ′ as a continuous map, there is a
unique pull back measure we can put on Cˆ. The upper bound on the measure
of the bases is of C is obvious from the definitions of the derived moves.
Corollary 4.8 (Going backwards). Let C → C ′ be one of the continuous maps
of the derived transformation on C . Suppose that C ′ efficiently carries a track
t (Definition 2.9.) Then there is a unique track t̂ that is efficiently carried by
C such that (C , t̂) → (C ′ , t) is a derived transformation in the Rips machine.

28

Proof. Since C ′ efficiently carries t, we can put a measure on C ′ (Definition
2.11) that corresponds to t. Lemma 4.7 gives a pullback measure on C , which
induces a track t̂ ⊂ C which induces the derived transformation. Furthermore
it is routine to check for the basic moves in Section 3.1 that t̂ is indeed efficiently
carried by C , provided t is efficiently carried by C ′ .
Any band complex in terminal form (Definition 3.27) efficiently carries a
unique track. We will now show how repeatedly going backwards enables us
to use T(C) to organize the collection of tracks that are efficiently carried by
C.
Proposition 4.9. There is a bijective correspondence between the set of tracks
in C and {Cl } the set of terminal leaves (Section 4.0.1 (2)) of T(C).
Proof. Let C be a band complex at the top level of T(C). As a topological
space it is homeomorphic to C. Any track efficiently carried by C is obviously
a track in C.
If t ⊂ C is a track, by Proposition 3.26 the Rips sequence for (C , t) will
give a path in T(C) from C to some band complex in terminal form Cl . This
map from tracks to leaves is injective since, having fixed <, the outcome of a
particular derived move (C , t) → (C ′ , t′ ) move depends only on the track t.
On the other hand let Cl be a terminal leaf of T(C). We may metrize all
its bases to have length 1, so that each band is explicitly parameterized as
[0, 1] × [−1, 1]. Cl efficiently carries the track tl which intersects each band
as { 21 } × [−1, 1]. Now starting at (Cl , tl ) and repeatedly going backwards
(Corollary 4.8) in T(C), we obtain (C , t), where t ⊂ C is an efficiently carried
track.
If C is some band complex not in terminal form(as in Section 4 (2)) then
any efficiently carried track t ⊂ C gives rise to one of the children in the
elimination tree
C
C1

···

Cn

It follows that there are injective maps
ιj : tracks(Cj ) ֒→ tracks(C )
whose images give a cover
tracks(C ) =

[

(7)

ιj (tracks(Cj )) .

j

Definition 4.10. Let Cv be a band complex in an elimination tree T(C). We
denote the track neighbourhood
NT(C) (Cv ) ⊂ tracks(C )
to be the set of tracks carried by C obtained by composing the maps (7) going
from Cv all the way back to C .
Equivalently if Cv is a band complex in T(C), then there is a natural
inclusion T(Cv ) ⊂ T(C). Proposition 4.9 immediately gives the inclusion
tracks(Cv ) ֒→ tracks(C ) obtained by iterating (7).

29

4.2

Analogies with surface train tracks

If the reader has some familiarity with surface train tracks, the following analogies may be helpful.
If Σ is a surface then a train track τ ⊂ Σ is analogous to a band complex
structure C on a 2-complex C. If we assign positive integer weights to the
branches of a train track τ satisfying the switch equations then we get a multicurve in Σ, which is analogous to a pattern in C. For us a track in a 2-complex
is analogous to a simple closed curve.
The assignment of weights to branches of a train track gives rise to a
splitting sequence
τ = τ0 → · · ·
which will eventually split τ into a multicurve if the weights are positive integers. This is analogous to a Rips process.
On the other hand if we put a measure on a train track then we can consider
all possible train tracks
τ
τ1

···

τn

that can be obtained from τ via a splitting move. Iterating, this gives an
analogue to the elimination tree. In fact we will get an actual tree if we
impose some kind of order < which specifies at which switch to split at each
step. If eventually the train track has split itself into a simple closed curve τT
then we have a train track in terminal form. Assigning weight 1 to the branch
and working backwards (i.e. using folding sequences) gives us a “complicated”
simple closed curve in Σ.
If we were to consider the set of projectivized measured laminations, then
irrational laminations would give infinite splitting sequences. Furthermore the
neighbourhoods of Definition 4.10 are somewhat analogous to open neighbourhoods in the Hausdorff topology on laminations. Indeed, two laminations are
“close” if the corresponding splitting sequences coincide for a long time. This
all carries through to measured laminations on cell complexes, but this technology is not needed, and the ordering < will cause us to stay stuck in a single
minimal component.

4.3

Inadmissibility from κ-acylindricity

Up to now the κ-acylindricity of the dual Bass-Serre tree T (t, C ), has not been
used at all.
Definition 4.11. A track t efficiently carried by a band complex C is called
a κ-track if the dual tree T (t, C ) is κ-acylindrical. We denote by tracksκ (C )
the set of κ-tracks efficiently carried by C .
We give two extra criteria to exclude vertices Cv of T(C) because their
track neighbourhood NC (Cv ) cannot contain any κ-tracks.
Lemma 4.12. If π1 (C ) has no elements of order 2 and t ∈ tracksκ (C ),
then if µ + µ, then either (µ, µ) forms an annulus that can be crushed (which
decreases the number of bands,) or |µ|t ≤ κ where |µ|t is the hitting measure.

30

Proof. By the κ-acylindricity assumption any element that fixes an arc of
length κ + 1 in the dual tree T (t, C ) must be trivial. By assumption B(µ) either forms an annulus A(µ) or a Möbius strip M(µ). In both cases Gp (A(µ))
or Gp (M(µ)) is generated by an element g 6= 1, since clause (1) in the Rips
machine (Section 3.4) crushes π1 -trivial annuli and Gp (M(µ)) must act nontrivially on T (t, C ).
We pass to the universal cover and consider the equivariant map π of Proposition1.6(2), and we see that in the annulus case g fixes an arc of T (t, C ) of
length |µ|t . In the Möbius strip case g2 6= 1 fixes an arc of length |µ|t in
T (t, C ). In the Möbius band case this forces |µ|t to be at most κ. In the
annulus case, if |µ|t > κ then we can crush it since Gp (A(µ)) = {1}.
As an immediate Corollary we have:
Proposition 4.13. Let Cv be a band complex in T(C). If along some path
p : Cu → · · · → Cv
in T(C) either some annulus gets subdivided more than κ+1 times or some base
µ that formed a Möbius pair with its dual gets shortened or vertically subdivided
more than κ+1 times, then NT(C) (Cv ) doesn’t contain any κ-acylindrical tracks.
Definition 4.14. We call a path p in T(C) such as the one given in Proposition
4.13 κ-inadmissible.

4.4

Automorphic minimality and repetitions

Definition 4.15 (Size and minimality). The size of a track t ⊂ C in a band
complex is the finite sum
X
Size(t) =
|µ ∩ t|
µ

where µ ranges over the bases of C . A track t is called automorphically minimal
if among all other tracks t′ such that t ∼Aut(π1 (C )) t′ , Size(t) ≤ Size(t′ ).
This next lemma is easy to prove from the definitions of the basic moves.
Lemma 4.16. Let m : C → C ′ be a basic transformation. If t′1 is a track
efficiently carried by C ′ then there is a corresponding track t1 efficiently carried
by C such that m : (C , t1 ) → (C ′ , t′1 ). Furthermore if t′2 is efficiently carried
by C ′ and Size(t′1 ) < Size(t′2 ) then Size(t1 ) < Size(t2 ) where t2 is the track
efficiently carried by C corresponding to t2 .
This notion of automorphic minimality may seem convoluted, but the proof
of the following proposition may clear things up for the reader.
Proposition 4.17 (Repetitions and minimality). Let Cv be a band complex
in T(C). If along some path
p : Cu → · · · → Cv
in T(C) there are two combinatorially equivalent band complexes (Definition
≈
2.13) Cu → Cv , i.e. a repetition, then NT(C) (Cv ) cannot contain any minimal
tracks.

31

Proof. Suppose towards a contradiction that there was a track t ⊂ C in
NT(C) (Cv ) that was minimal. Let qv : Cv → · · · → Cl be the path to the
terminal leaf in T(C) corresponding to t (recall Proposition 4.9.)
Let pu be the concatenation of paths p and qv , i.e. pu : Cu → · · · →
Cv → · · · → Cl . Since Cu ≈ Cv , we can attach the path qv to Cu to get a
corresponding path qu : Cu → · · · → Cl′ , where Cl′ ≈ Cl . Let t′ ⊂ C be
the track corresponding to Cl′ , and denote by t′i (respectively ti ) the image
of t′ (respectively t) in Ci , should there be such an image. Derived moves
always decrease the lengths of bases; thus, in Cu , Size(t′u ) < Size(tu ). Working
backwards in T(C), i.e. repeatedly applying Corollary 4.8, all the way back to
a direct descendant C of C yields Size(t′ ) < Size(t).
≈
On one hand, by the definitions of qv and qu , we have (Cv , tv ) → (Cu , t′u ).
On the other hand we have a sequence of derived moves
(Cu , tu ) → · · · → (Cv , tv )
this gives a composition of continuous maps
≈

ϕ : Cu → · · · → Cv → Cu
which by Proposition 3.11 induces an isomorphism on π1 , hence ϕ♯ ∈ Aut(π1 (Cu )).
Furthermore, by construction ϕ(tu ) = t′u , so again Proposition 3.11 gives us
that T (tu , Cu ) is ϕ♯ -equivariantly isomorphic to T (t′u , Cu ) where the action on
the second tree is given by (g, x) 7→ ϕ♯ (g) · x. It follows that t′ and t are
automorphically equivalent, contradicting the minimality of t.
Definition 4.18. A path p in T(C) that satisfies the hypotheses of Proposition
4.17 is called repetition-inadmissible.

4.5

Restricted elimination processes

In order to construct T(C) we will sometimes have to construct auxiliary elimination trees that are rooted at band complexes C in T(C).
Let J ⊂ C be a union of maximal sections. We redefine the order < so
that the maximal sections in J are terminal. The restricted elimination tree is
used to study how the bases of C can be moved into J. If C → C ′ is a derived
transformation, which is a continuous map, then J has a well-defined image in
C ′ which we also denote by J. T(C , J) is constructed as follows:
(0) The root of T(C , J) is C .
(1) If every base of a band complex Cl in T(C , J) is contained in J then Cl
is called a J-terminal leaf.
(2) Inadmissible leaves are defined the same way as for T(C).
(3) Otherwise we apply a corresponding derived transformation, either a
Möbius move on (µ, µ), a thinning move starting at µ, or an entire transformation with leading base µ to create the children of Cv . Equip the
union of bases of every child Cv′ of Cv with the induced order <.

32

Restricted elimination processes will be required for some subprocesses of
our main algorithm. It is obvious that the various inadmissibility criteria for
a standard elimination tree T(C) also hold for restricted elimination trees.
Convention 4.19. Many statements about restricted elimination trees will
also follow for the standard elimination tree by replacing T(C) by the elimination trees T(C1 , ∅), . . . T(CnC , ∅) where C1 , . . . , CnC are the children of C (see
step (1) in Section 4.0.1.) These elimination trees are contained in T(C). We
will therefore assume that results about restricted elimination processes will
apply to the standard elimination process, the latter being a special case.

4.6

The infinite branches of T(C).

One of Makanin’s key observations is that every infinite branch of T(C) stabilizes into one of three cases. The main ingredient is the following lemma.
Lemma 4.20. If after applying an entire transformation which didn’t involve
a Möbius move we are in the situation where we must make a thinning move,
then (J-relative) τ -complexity decreased.
In the case of band complexes, this fact is explained between Proposition
7.5 and Proposition 7.6 of [BF95]. The proof consists of a straightforward
complexity counting argument. This next result is ubiquitous whenever the
elimination process/Rips machine is involved.
Theorem 4.21 (Fundamental classification). Every infinite branch b in T(C)
(T(C , J)) has a tail bv = Cv → · · · of one of the following form:
(i) Thinning: Every derived transformation along bv is a thinning move.
(ii) Quadratic: Every derived transformation along bv is an entire transformation. For all but finitely many points in the (J-complement of the)
union of bases of the band complexes Cw along bv we have γ(x) = 2
(Definition 3.14)
(iii) Superquadratic: Every derived transformation along bv is an entire transformation. There is a whole open interval of points in the (J-complement
of the) union of bases of the band complexes Cw along bv such that
γ(x) ≥ 3.
Furthermore if we require NT(C) (Cv ) to contain a κ-track, then we may assume
that no Möbius moves or annulus subdivisions occur along bv .
In (ii) above, we would really like to say that every point in the union of
bases is contained in exactly two unmatched bases. Points on the boundary of
bases, however, may be contained in up to four distinct bases, but there are
only finitely many of them.
Proof. If the (J-restricted) τ -complexity is 0, because we are not allowing long
bands (see Step 4 of the thinning move, Section 3.3.2), all bases are matched
(all bases moved onto J) so we are at a leaf. It therefore follows by Lemma
4.20 that the infinite branch b eventually always consists of thinning moves,
or eventually always consists of entire transformations.

33

Suppose now that bv is not of thinning type. If Cv is of quadratic type,
then after applying an entire transformation Cv′ is still quadratic. The trichotomy now follows. The fact that Möbius moves and annulus subdivisions
stop occurring follows from Lemma 4.12.
König’s Lemma states that every infinite rooted tree with vertices of finite
valency must have an infinite branch. This classification of infinite branches
is the foundation of the construction of a finite subtree of T(C) containing all
the leaves corresponding to minimal κ-acylindrical tracks.

4.7

The admissible subtree A(C , J)

Definition 4.22. The admissible elimination tree A(C , J) ⊂ T(C , J) is the
subtree obtained by forbidding κ-inadmissible and repetition-inadmissible subpaths (Definitions 4.14 and 4.18). We similarly define the admissible elimination tree A(C) ⊂ T(C).
This next proposition enables us to restrict the search for tracks in the
algorithm for Theorem B to admissible elimination trees.
Proposition 4.23. Let t be an automorphically minimal κ-track efficiently
carried by C . Any path C → · · · in T(C , J) induced by t ⊂ C must be
contained in A(C , J).
Proof. Otherwise Proposition 4.14 or 4.18 lead to a contradiction of the hypotheses.
Proposition 4.24. For every n, the subtree of radius n of A(C , J) can be
effectively constructed.
Proof. For any band complex the collection of children (see Definition 4.4(6))
can be constructed effectively and the various inadmissibility conditions can
be verified effectively.

4.8

Reduction to the superquadratic case

We show that infinite thinning or quadratic branch in T(C , J) contains a repetition. From this it will follow that the admissible elimination tree A(C , J)
does not have any infinite thinning or quadratic branches.
Lemma 4.25 (c.f. [KM98, Lemma 15]). Any sufficiently long thinning path
Cv → · · · contains a repetition, i.e. a subpath Cu → · · · → Cw with Cu ≈ Cw .
Proof. By Theorem 4.21 we may assume that no more annulus subdivision
occur. By Lemma 3.20, the number of 2-cells and the vertical lengths of the
2-cell attaching maps are non-increasing, furthermore since the τ -complexity
is bounded and there are no maximal sections σ with τ (σ) = 0 there is a bound
on the number of bases.
A band complex is obtained by gluing bands to a graph Γ and then attaching other 2-cells. Since derived transformations do not change anything in
the exterior of union of the bands, then number of bands and 2-cells remains
bounded, and the combinatorial lengths of the attaching immersions of the 2cells is bounded, any sufficiently long thinning path will have a repetition.

34

This next lemma will also be used later in Section 6.2.
Lemma 4.26 (c.f. [KM98, Case 14]). Any sufficiently long quadratic path
Cv → · · · contains a repetition.
Proof. By Lemma 3.24, the τ complexity doesn’t increase, and we may assume
that no Möbius moves or annulus subdivision occur. It remains to show that
the vertical lengths of 2-cell attaching maps remain bounded; the result will
then follow as in the previous proof.
Consider Figure 8 with leading bases µ, λ, where µ is the carrier. The only

λ
µ

η

η
µ

µ
µ
λ

η

...
...

λ
µ
...

µ

...

η

µ
µ
... λ
...
...

...

Figure 8: Above, the attaching maps of 2-cells under an entire
transformation in the quadratic case. Below, the resulting ordered
base configurations.
way the attaching map of a 2-cell do decrease in vertical length is if it it has
a subpath as in the shaded path on the left of Figure 8 that travels through
B(λ) ∪ B(µ). The only way for a segment in the boundary of a 2-cell to get
“stretched” is if travels through the vertical sides of B(λ) and B(η). In this case
we have a segment σ of length 2 that gets stretched to a segment σ ′ of length
3. After the entire transformation, however, η and µ are now leading bases,
this means that after the next entire transformation there is a subsegment of
length 2 σ ′ that gets shortened again back to length 1.
It therefore follows that the vertical lengths of the boundaries of 2-cells
remain bounded throughout the quadratic path and the result follows.
These two Lemmas immediately imply the following corollary, which pretty
much sets the tone for the rest of the paper.
Corollary 4.27. The admissible elimination subtree A(C , J) ⊂ T(C , J) does
not have any infinite paths of thinning or quadratic type. Equivalently, all
infinite paths in A(C , J) have superquadratic tails.

5

Overlapping pairs and periodic mergers

We start our attack of the superquadratic case by examining overlapping pairs
and by introducing a new move: the periodic merger (precisely defined in

35

Section 5.3). Throughout this section π will denote the map π : Ce → T (t, C )
given in Proposition 1.6(2).

Definition 5.1. A dual pair (µ, µ) is an overlapping pair if interior (µ ∩ µ) 6=
∅ and the pair is orientation preserving, i.e. if the image of B(µ) ⊂ C does not
contain an embedded Möbius band.

Convention 5.2. When (µ, µ) is an overlapping pair we will assume that
µ < µ, where < is the ordering on C (Definition 3.21.)
Definition 5.3. Let B(µ) be a band such that (µ, µ) is an overlapping pair.
Let p ∈ µ the <-initial point (Definition 3.21.) The tubular loop τµ is the loop
α ∗ β where α is the path in the side of B(µ) starting at p and going from µ to
µ and β is the path in µ connecting the endpoint of α to p. See Figure 9.

◭

◭
µ

p ◭
µ
Figure 9: An overlapping pair. The dark loop indicated on the
left is the tubular loop τµ .
We note that our definition of a tubular loop is an oriented based loop.
This gives rise to an element g ∈ π1 (C ) that we will call a µ-tubular element.
For the rest of the paper we will avoid mentioning the basepoint.
Suppose that C carries a track t. Figure 10 illustrates the action of the
µ-tubular element τµ on T (t, C ) given by the quotient map π of Proposition
1.6. p ∈ C is as in Definition 5.3 and pe ∈ µ
e is a lift in the universal cover Ce of
p ∈ µ ⊂ C . It is evident, for any track t efficiently carried by C , that τµ must

τµ · µ
e

τµ · pe
pe

π(e
µ)
e
µ

...

...
τµ · π(e
µ)

µ
e

Figure 10: On the left, the action of a tubular element on the
universal cover by deck transformations; on the right the corresponding action on the tree T (P, C). Tracks are shown as dashed
lines
fix some axis of T (t, C ). Closer examination immediately yields:

36

Lemma 5.4. If C efficiently carries a track t and (µ, µ) is an overlapping pair
then the µ-tubular element τµ acts on T (t, C ) hyperbolically with translation
length denoted
tr(µ) = |µ \ µ|t .

tr(µ)

µ
◮

µ
◮

σ(µ)
Figure 11: The translation length tr(µ) and σ(µ), the section
corresponding to µ given in Definition 5.5.
One of the principal features of a group acting acylindrically on a tree is that
infinite line stabilizers are cyclic. It follows that if there are two overlapping
pairs that themselves overlap sufficiently, the corresponding tubular elements
must fix a common axis, and therefore must lie in a common cyclic subgroup.
In Section 5.3 we will describe the periodic merger, a move from [AHT06],
which will replace these two overlapping pairs by a single overlapping pair.
This is illustrated in Figure 12. There are two subtleties to this operation,

λ
◮
µ
◮

λ
◮
µ
◮

Widen B(λ)

µ
◮

µ
◮
η
◮

µ
◮

µ
◮

λ
◮

λ
◮

λ
◮

λ
◮

At

)
B(η
h
c
ta

Zip onto B(η)
η
◮

η
◮

η
◮

Figure 12: A periodic merger (defined in Section 5.3.) In this
example tr(τµ ) = 2, tr(τλ ) = 3 and tr(τη ) = gcd(2, 3) = 1.
which do not occur when deciding if an equation has a solution, or if we
simply want to count orbits as in [AHT06].
• We must merge these bands into one while preserving the fundamental
group of the band complex as well as the dual Bass-Serre tree.

37

• We must be able to algorithmically produce a finite list containing all
combinatorial outcomes of a periodic mergers for (C , t), where t ranges
over tracksκ (C ). (Definition 4.11.)
There is one outstanding difficulty: given two commuting elements g, h ∈
π1 (C ), decide if they lie in a common cyclic subgroup. Only being able to
solve the word problem in π1 (C ) is insufficient to solve this problem in general.
To overcome this impasse we will use the author’s generalized Bulitko Lemma
[Tou14] in a way that is completely different from its usual purpose.

5.1 Interactions with tubular elements: entanglement
Definition 5.5. If (µ, µ) is an overlapping pair then we denote the section
corresponding to (µ, µ) as
σ(µ) = µ ∪ µ.
Suppose now that here is another band B(λ) whose unmatched bases both
lie in σ(µ), as in Figure 13.

β
◭
pγ
◭

r

◮
α

B(λ)
q

B(µ)

Figure 13: The band B(λ) has both bases lying in the section
σ(µ). The µ-relative loop ρλσ(µ) is the loop α ∗ β ∗ λ.
Convention 5.6. We write (λ, λ) ⊂ σ(µ) to signify λ ∪ λ ⊂ σ(µ). We will
always assume that that base pairs (λ, λ), (µ, µ) are unmatched.
To study how these bands interact we have the following
Definition 5.7. Let (µ, µ) be overlapping and let (λ, λ) ⊂ σ(µ) with λ < λ.
Let p be as in Definition 5.3. The µ-relative loop ρλσ(µ) is the concatenation
α ∗ β ∗ γ shown in Figure 13 where α is the path from p to q in σ(µ), β is the
path from q to r travelling along a side of B(λ), and γ is the path in σ(µ) from
r to p.
Again fixing a lift pe of p and µ
e of µ in the universal cover Ce of C , we can
describe the deck transformation given by ρλσ(µ) (see Figure 14.) From this we
immediately get:
Lemma 5.8. If C efficiently carries a track t, then in T (t, C ) the length of
the arc


axis(τµ ) ∩ ρλσ(µ) · axis(τµ )
is at least |λ|t .

38

γ re
e
ρλσ(µ) · pe ◭

◮

βe

pe

α
e
◮

q

g
σ(µ)

Figure 14: The deck transformation corresponding to ρλσ(µ) . The
lifts of α, β and γ of Figure 13 are shown.
Definition 5.9. We define trσ(µ) (λ) to be the measure of the arc between the
leftmost point of λ and the leftmost point of λ, i.e. the length |α|t − |γ|t as
shown in Figure 13. We say the dual pair (λ, λ) is orientation preserving if
the holonomy λ → λ extends to an orientation preserving homeomorphism of
σ(µ) (relative to its endpoints.)
For the following three lemmas assume that t ∈ tracksκ (C ).
Definition 5.10. If (µ, µ) is an overlapping pair, (λ, λ) ⊂ σ(µ) with (λ, λ)
orientation preserving, and the commutator [τµ , ρλσ(µ) ] = 1, then we say that
dual pairs (µ, µ) and (λ, λ) are entangled.
The following is obvious, but necessary for computational considerations:
Lemma 5.11. Let C be a band complex with (µ, µ) be an overlapping pair,
and (λ, λ) ⊂ σ(µ) and such that (λ, λ) is orientation preserving. If we can
solve the word problem in π1 (C ) then we can decide if (µ, µ) and (λ, λ) are
entangled.
Lemma 5.12. Let (µ, µ) be an overlapping pair, suppose (λ, λ) ⊂ σ(µ) and
that (λ, λ) is orientation preserving and unmatched. If [τµ , ρλσ(µ) ] = 1, i.e.
(µ, µ) and (λ, λ) are entangled, then ρλσ(µ) acts hyperbolically on T (t, C ),
axis(ρλσ(µ) ) = axis(τµ ),
and the translation length of ρλσ(µ) is trσ(µ) (λ).
Proof. Because [τµ , ρλσ(µ) ] = 1,


ρλσ(µ) · axis(τµ ) = axis ρλσ(µ) τµ (ρλσ(µ) )−1 = axis(τµ ).

It therefore follows that hρλσ(µ) i fixes a bi-infinite arc in T (t, C ). From Figure 14, ρλσ(µ) translates this arc by tr(ρλσ(µ) ) (as defined in Definition 5.9), it
therefore follows axis(τµ ) is the minimal invariant subtree for hρλσ(µ) i.
Lemma 5.13. Let (µ, µ) be an overlapping pair, let (λ, λ) ⊂ σ(µ), and let
(λ, λ) be orientation preserving. If |λ|t ≥ tr(µ) + κ + 1 then [τµ , ρλσ(µ) ] = 1, i.e.
(µ, µ) and (λ, λ) are entangled.

39

Proof. Let


I = axis(τµ ) ∩ axis ρλσ(µ) τµ (ρλσ(µ) )−1 .

By Lemma 5.8 we have |I| ≥ tr(µ) + κ + 1 let J be a co-initial (or co-final)
subsegment of I with|J| ≥ κ + 1. Without loss of generality (up to choosing if
J is co-initial or co-final) we may assume that

τµ · J ⊂ I ⊂ axis ρλσ(µ) τµ (ρλσ(µ) )−1

and since λ is orientation preserving and since translation length in invariant
under conjugation we have :

ρλσ(µ) τµ−1 (ρλσ(µ) )−1 · (τµ · J) = J

which by κ-acylindricity implies [τµ , ρλσ(µ) ] = 1.

5.2

The Bulitko trick

If we are given a band complex C with an overlapping pair (µ, µ) that is
entangled with (λ, λ) then, by Lemma 5.12, if tracksκ (C ) 6= ∅, then hτµ , ρλσ(µ) i
must be cyclic. In particular there is hgi = hτµ , ρλσ(µ) i so that gn = τµ and
gm = ρλσ(µ) with n, m minimal in absolute value. The Bulitko trick will either
enable us to find n, m or will certify that tracksκ (C ) = ∅.
Let φ : π1 (C ) → H be a homomorphism to the fundamental group of a
one-edged κ-acylindrical graph of groups. Then as long as some element of hgi
is sent to a hyperbolic element n, m will still be the minimal integers such that
φ(g)n = φ(τµ ) and φ(g)m = φ(ρλσ(µ) ).
Since [ρλσ(µ) , τµ ] = 1 then any φ : π1 (C ) → H will send τµ and ρλσ(µ) to
elements fixing a common axis, provided their images are hyperbolic. In this
case, the acylindrical Bulitko Lemma provides a computable function depending only on τµ and ρλσ(µ) that bounds n, m given above. Before giving the
lemma we must first present the necessary terminology.
Let H act κ-acylindrically on a based tree (T, t0 ), let p be some hyperbolic
element of H (with respect to the given splitting of H) and let L ⊂ T denote
its axis. Consider the set of segments
[
 ′
L ⊂L|L=
p n L′ .
n∈Z

A minimal element of this set with respect to inclusion is called a fundamental
domain of L.
For an element h ∈ H, let [v0 , h · v0 ] denote the geodesic between v0 and
h · v0 . Let g ∈ H. If a segment
σ = [v0 , h · v0 ] ∩ g · L

is non-empty then we call it an L-periodic subsegment of [v0 , h · v0 ]. The
L-periodicity of σ is the integer
⌊

|σ|
⌋
|L0 |

where L0 is a fundamental domain of L. We can now state

40

Theorem 5.14 (Acylindrical Bulitko Lemma, Theorem 1.3 of [Tou14]). There
exists a computable function n : N × N × N → N such that for any nontrivial
homomorphism φ : G → H; where the group G has a finite presentation hY | Si
and the group H has a κ-acylindrical splitting with based Bass-Serre tree (T, t0 );
and for any hyperbolic element in p ∈ H (denote its axis L ⊂ T ), there exists
a homomorphism φ∗ : G → H such that for all y ∈ Y
• if [t0 , φ(y) · to ] has no L-periodic subsegments, then φ(y) = φ∗ (y), and
• if [t0 , φ(y) · to ] has L-periodic subsegments, then there is a bijective correspondence between the L-periodic subsegments of [t0 , φ(y)·to ] and [t0 , φ(y)∗ ·
to ], but the L-periodicity of all the periodic subsegments of [t0 , φ(y)∗ · to ]
is at most n(|Y |, |S|, κ).
Proposition 5.15. Let (µ, µ) be an overlapping pair in a band complex C and
suppose it is entangled with (λ, λ). There is an algorithm which terminates with
one of the two following outputs:
(i) It gives an element g such that hgi = hτµ , ρλσ(µ) i.
(ii) It (correctly) certifies that tracksκ (C ) = ∅.
Proof. Let G = π1 (C ). Since C is an explicitly given cell complex and since we
can solve the word problem in π1 (C ), it is possible to give a finite presentation
hY | Si of G where τµ and ρλσ(µ) are included in the generating set Y .
Let n be the computable function given by Theorem 5.14 and let M =
n(|Y |, |S|, κ). For every pair ni , mj of absolute value less than M let (ui , vj )
be a pair such that ui ni + vi mj = gcd(ni , mi ). Let gij = (τµ )ui (ρλσ(µ) )vj and
check whether (gij )ni = τµ and (gij )mj = ρλσ(µ) . If we find some gij satisfying
item (i) then we stop. Otherwise if all these verifications were negative we
know that that tracksκ (C ) = ∅.
Indeed suppose towards a contradiction that none of the gij were roots
of τµ and ρλσ(µ) but that there is some t ∈ tracksκ (C ). By Lemma 5.12
there is some g ∈ G suchthat hgi is the maximal cyclic group stabilizing
L = axis(τµ ) = axis ρλσ(µ) let n, m be the integers such that gn = τµ and

gm = ρλσ(µ) . By hypothesis |n| or |m| is greater than M . Let H = π1 (C ) let T
be T (t, C ), let φ be the identity, let p = g and let L denote the axis of g. We can
chose the basepoint t0 of T so that t0 ∈ L which implies that that the geodesics
[t0 , φ(ρλσ(µ) ) · t0 ] and [t0 , φ(τµ ) · t0 ] consist of a single L-periodic segment. By
Theorem 5.14 there exists an endomorphism φ∗ such that [t0 , φ∗ (ρλσ(µ) ) · t0 ] and
[t0 , φ∗ (τµ ) · t0 ] contain a single non-trivial L-periodic segment, this implies the
hyperbolicity of φ∗ (τµ ) and φ∗ (ρλσ(µ) ); thus the restriction φ∗ |hgi is injective.
On the other hand the bound on L periodicity implies that φ∗ (τµ ) = gn0 and
φ∗ (ρλσ(µ) ) = g m0 with |n0 |, |m0 | ≤ M . Now we must have φ∗ (g) = g r which
implies that |n0 | = |r||n| and |m0 | = |r||m| which contradicts the assumption
that |n|, |m| > M.

5.3

Merging entangled pairs

Let C be a measured band complex and let t ∈ tracksκ (C ). Suppose we
have an overlapping pair (µ, µ) entangled with (λ, λ) ⊂ σ(µ). Then it will

41

sometimes be possible to merge the bands B(λ) and B(µ) into a new band
B(η).
Simply attaching a new band with overlapping bases to C inside the segment σ(µ) will add a cyclic free factor to π1 (C ). We must therefore also attach
a 2-cell to encode that τη is a root of τµ and ρλσ(µ) . In order to do so we may
first have to widen B(λ).
Consider the operation of widening a band B(λ) illustrated in Figure 15.
We do this so that the resulting base λ is coinitial with σ(µ) and λ is cofinal.

B(λ)

B(λ)

Widen B(λ)

B(µ)

Figure 15: We widen the band B(λ) so that it becomes coinitial
and coterminal with σ(µ).
The inverse of a widening is a deformation retraction, so it preserves π1 (C ).
Furthermore the element ρλσ(µ) of the fundamental group is unchanged. If
[ρλσ(µ) , τµ ] = 1 then for any track t efficiently carried by C both ρλσ(µ) and τµ
have the same axis by Lemma 5.12. Figure 16 depicts what happens when
we pass to the universal cover. Because ρλσ(µ) has the same axis as τµ there

x

g
ρλσ(µ) · σ(µ)

x

]
B(λ)

g
ρλσ(µ) · σ(µ)
]
B(λ)

y

y

g
σ(µ)

g
σ(µ)

Figure 16: The widening move corresponds to equivariantly
] of B(λ) in the universal cover. If x, y
widening every lift B(λ)
f′ we extend the track to
lie in the same track e
t in Ce, then in C
]
pass through the widened B(λ).
f′ so that the
is a natural way to extend the pattern in Ce to a pattern of C
resulting dual trees T (t, C ), T (t′ , C ′ ) are equivariantly isomorphic. No 2-cells
were added so t′ is efficiently carried. We summarize in the following lemma.
Lemma 5.16. Let µ and λ be as above and let t ∈ tracksκ (C ). We can
widen B(λ) so that, in the new band complex C ′ , λ is coinitial with σ(µ)
and λ is cofinal with σ(µ). Furthermore the dual trees T (t, C ) and T (t′ , C ′ )
are equivariantly isomorphic. In particular tr(λ), tr(µ) remain invariant, and
t′ ∈ tracksκ (C ′ ).

42

Lemma 5.17. Let (µ, µ) be an overlapping pair entangled with (λ, λ) and
suppose furthermore that (λ, λ) is itself overlapping. Then after widening B(λ)
as in Lemma 5.16 we have |λ|t ≥ tr(µ).
Proof. If λ is coinitial and cofinal with σ(µ), but |λ|t < tr(µ), then λ can’t
overlap with its dual.
Before continuing we need the following fact, which follows by meditating
on the Euclidean algorithm.
Lemma 5.18. Let n, m be positive integers and let d = gcd(n, m) then without
loss of generality there are integers u, v ∈ Z≥0 such that d = un−vm, moreover
we have non-decreasing sequences of integers 0 = v0 ≤ v1 ≤ . . . ≤ vu+v = v
and 0 = u0 ≤ u1 ≤ . . . ≤ uu+v = u with
ui + vi + 1 = ui+1 + vi+1
such that the following inequalities hold
0 ≤ u i n + vi m ≤ m + n

(8)

This fact motivates the following observation.
Lemma 5.19. Let (µ, µ) be an overlapping pair entangled with (λ, λ). If |λ|t ≥
tr(µ), then
|σ(µ)| ≥ tr(µ) + trσ(µ) (λ)
Proof. By hypothesis |λ|t ≥ tr(µ) and
λ ∪ λ ⊂ σ(µ) ⇒ |λ|t + trσ(µ) (λ)| ≤ |σ(µ)|
which give the required inequality.
Suppose we are in the situation of Lemma 5.19 and that we have widened
B(λ) as in Lemma 5.16. We will illustrate the attachment of B(η) with a
concrete example. Suppose that tr(µ) = 3, trσ(µ) (λ) = 7, |µ|t = 8 and |λ|t = 4,
see Figure 17. gcd(3, 7) = 1, we pick the linear combination 5 ∗ 3 − 2 ∗ 7 = 1

Figure 17: The vertical path αµλ contained in bands B(λ), B(µ),
corresponding to the series 3 + 3 + 3 − 7 + 3 + 3 − 7 = 1 = gcd(3, 7).
which we rewrite the series 3 + 3 + 3 − 7 + 3 + 3 − 7 = 1, we do this because each
initial subsum is positive and at most 10 = 3 + 7 as in Lemma 5.18(8). This
Lemma implies that such a series can be found for any pair of bands satisfying
our hypotheses. Now αµλ in Figure 17 is a simple path that is a concatenation
of vertical sets prescribed by the associated series. Its endpoints in σ(µ) have
distance gcd(tr(µ), trσ(µ) (λ)), which in our example is 1. By Lemmas 5.18 and

43

5.19, we can always find such an αµλ for any pair of bands that satisfy the
hypotheses. This is why we needed to widen B(λ) in the first place; if it were
too narrow we wouldn’t be able to construct αµλ .
In π1 (C ) the elements τµ and ρλσ(µ) commute, so the product implied by
the path αµλ is
(τµ )3 (ρλσ(µ) )−1 (τµ )2 (ρλσ(µ) )−1 = (τµ )5 (ρλσ(µ) )−2 .
(τµ )5 (ρλσ(µ) )−2 is an element that translates axis(τµ ) = axis(ρλσ(µ) ) by a distance of gcd(tr(µ), trσ(µ) (λ)). Noting that (signed) translation length gives an
embedding from the stabilizer of a bi-infinite line in a κ-acylindrical tree to Z,
we conclude that g = (τµ )5 (ρλσ(µ) )−2 is the element such that hgi = hτµ , ρλσ(µ) i
that will (up to sign ±1) be produced by the algorithm given in Proposition
5.15.
We now attach a new band B(η) so that σ(η) = σ(µ) and that tr(η) =
gcd(tr(µ), trσ(µ) (λ)). In our example this forces |η|t = 10. Let βη be the path
shown in Figure 18. Simply attaching B(η) to C gives the fundamental group

βη
◮

Figure 18: Adding B(η) and the arc βη .
π1 (C ) ∗ hτη i. We also attach a 2-cell B along the simple closed path αµλ ∗ βη
to get the resulting fundamental group
(π1 (C ) ∗ hτη i) /hhτη = gii ≈ π1 (C )
by defining τη = g. First note that the new band complex C ′ can be seen
as containing C and that the track t ⊂ C ⊂ C ′ naturally extends to a track
t′ ⊂ C ′ and that the trees T (t, C ) ≈ T (t′ , C ′ ) are equivariantly isomorphic.
Further note that, by the way the attaching map αµλ ∗ βη is defined, C ′ carries
t′ efficiently.
The next step is to zip the bands B(µ) and B(λ) onto B(η). In our example,
since τµ = (τη )3 , B(µ) should “wrap” three times around B(η). To accomplish
this we horizontally subdivide B(µ) into 3 bands and successively perform
three zipping operation (Definitions 3.1 and 3.2). This is best visualized in the
universal cover, see Figure 19. Thus, we have produced a new band complex
C ′ efficiently carrying a track t′ and by Proposition 3.11 we have preserved
the fundamental group and the dual Bass-Serre tree. Although we considered
a specific example, this discussion is sufficiently general to make the following
claim.
Proposition 5.20 (The periodic merger). Let C be a band complex with an
overlapping pair (µ, µ) and an overlapping pair (λ, λ) ⊂ σ(µ), such that (µ, µ)
and (λ, λ) are entangled. Suppose that t ∈ tracksκ (C ). If, after widening
B(λ), as in Lemma 5.16 we have |λ|t ≥ tr(µ) then

44

Figure 19: Zipping B(µ) onto B(η), as seen from the universal
cover. Here τµ = (τη )3 .
• there is a continuous map m : C → C ′ where C ′ with m(t) = t′ ⊂ C ′
where t′ is a track efficiently carried by C ′ .
• The induced map m♯ : π1 (C ) → π1 (C ′ ) is an isomorphism and there is an
m♯ -equivariant isomorphism of dual Bass-Serre trees T (t, C ) → T (t′ , C ′ ).
• The resulting band complex C ′ has two fewer bases.
Proof. C ′ is obtained by first perhaps widening B(λ) so that it is coinitial
and coterminal with σ(µ), then attaching a band B(η) so that σ(η) = σ(µ),
attaching a 2-cell, and finally horizontally subdividing and zipping B(µ) and
B(λ) onto B(η). The resulting composition of operations preserves fundamental
groups and dual trees.

5.4 A modification to T(C): adding periodic mergers to the elimination process
We now turn our attention to band complexes, viewed as combinatorial objects.
Definition 5.21. Let Cv be a band complex in T(C), then we say that Cv is
merging inadmissible if it contains an overlapping pair (µ, µ) that is entangled
with (λ, λ), but the algorithm of Proposition 5.15, certifies that Cv can not
efficiently carry a κ-track.
Merging inadmissibility can be verified algorithmically. Indeed, given (λ, λ) ⊂
σ(µ), Lemma 5.11 states that entanglement can be computed and merging inadmissibility is certified from the output of the algorithm of Proposition 5.15.
By definition, this only depends on the underlying band complex, and not on
the track it carries.
Whether entangled base pairs can actually be merged, and the outcome of
this operation, depend on the track t carried by C . Merging inadmissibility,
however, guarantees that no matter the track being carried by C , such a
merging is impossible.
Now we have proved that if (µ, µ), (λ, λ) are a pair of entangled overlapping
pairs with (λ, λ) ⊂ σ(µ), then for any t ∈ tracksκ (Cv ), after widening B(λ)
as in Lemma 5.16 we will be able to apply a periodic merger by Lemma 5.19.
It therefore follows that we can discard merging inadmissible band complexes
since they cannot carry κ-tracks.

45

This next lemma simply follows from the fact that we can enumerate the
combinatorial outcomes all such periodic mergers since we widened some band
by a controlled amount, added a band, a 2-cell with an attaching map of length
M , and applied N zipping operation, where M, N are bounded by the output
of the algorithm of Proposition 5.15.
Lemma 5.22. Let C be a band complex containing overlapping pairs (µ, µ), (λ, λ)
that are entangled and such that (λ, λ) ⊂ σ(µ). Then we can effectively construct a finite set of band complexes
C
C1

···

CmC

containing all possible outcomes m : C → C ′ of merging B(µ) and B(λ) as
described by Proposition 5.20, with the track t ranging over tracksκ (C ).
We note that although some of the band complexes produced by Lemma
5.22 may not correspond to any periodic mergers, the resulting band complexes
will have the same fundamental group and a lower τ -complexity. In particular
if any of them admit a κ-track, then so must the original C . There is thus no
danger of introducing “false positives”, by giving C illegitimate children. We
now include periodic mergers in our elimination tree.
Definition 5.23. The elimination tree T+ (C , J) is constructed inductively
similarly as T(C , J) in Section 4.5 except with a new clause that takes precedence over item (4) given in Section 4.0.1.
(4m) If Cv is a nonterminal band complex in T+ (C J) that contains overlapping
pairs (µ, µ) and (λ, λ) satisfying the premises of Lemma 5.22 then define
as its children the collection of band complexes given by Lemma 5.22.
Obviously all the κ-inadmissibility and repetition inadmissibility criteria
on paths T(C , J) also apply to T+ (C , J), as does the classification in Theorem
4.21. For the remainder of this paper we will use T+ (C , J) as our elimination
tree.

6 Overlapping pairs must occur and stabilize.
For this section let C be a band complex, and let t ⊂ C be an automorphically
minimal κ-track efficiently carried by C . The corresponding Rips sequence
gives a path in T+ (C , J). Throughout this section we will fix a superquadratic
subpath
p(t1 ) : (C1 , t1 ) → · · · → (CP , tP )
(9)
where, in particular, the track t1 is an automorphically minimal κ-track efficiently carried by C1 . We will further assume that the J-relative τ -complexity
remains constant throughout p. The purpose of this section is to show that if p

46

is sufficiently long, then it must have a tail in which some base µ is repeatedly
the carrier. This is called µ-periodicity (Definition 6.14.)
We prove this by first defining a quantity called the excess that remains
constant throughout p. We then consider the quadratic part of C1 and use this
to show that a union of bases called the participating segments has a length
bounded above by some computable multiple of the excess. This multiple is
computed using a restricted elimination process. It will be clear from the definition that the excess is bounded above by some constant multiple of the length
of the longest base in each Ci occurring in p. Finally we will define something
called a C-T cycle with the property that whenever it occurs, a considerable
portion of the participating segments gets cut out. Our bound on the total
length of the participating segments will prevent these cycles from occurring
too often. The critical detail is that this bound does not depends on the actual track t. It only depends on the sequence of underlying band complexes
that occur along the path p and the assumption that t is an automorphically
minimal κ-track efficiently carried by C .
We will give an example of what is meant by “cut out”. Suppose that
the carrier µ in C1 does not overlap with its dual, that some base λ gets
transferred, and that eventually in Cu λ is again a leading base, see Figure 20.
Let the interval I(u) be the natural image of I(1) in Cu . On one hand we have

Transfer λ

C1

λ
◮
µ
◮

µ
◮
I(1)
...

Cu
λ
◮
µ
◮
I(u)

cut out

Figure 20: In C1 , µ is a carrier and λ gets transferred. In Cu , λ is
again leading. At least |µ|t1 got cut out of I(1).
|I(u)|tu < |I(1)|t1 , on the other hand we have |I(1)|t1 − |I(u)|tu ≥ |µ|t1 , i.e we
cut out at least |µ|t1 from I(1).

47

6.1

The excess invariant

The excess invariant given in Definition 6.2 is originally due to Makanin
[Mak82]. It also occurs in [BF95, KM98].
Definition 6.1. Let p be the path given in (9), by C(p) we denote the set of
bases that are carriers at some point along p and by T (p) we denote the set of
bases that are transferred at some point along p. We denote the participating
segments:
[
σ(p) =
(µ ∪ µ) .
µ∈C(p)∪T (p)

Recall that we are reusing symbols, so that if λ denotes a base in C1 then it
also naturally denotes a base in every Cu that occurs along p. With this in mind
it makes sense to reuse notation to denote the corresponding subset σ(p) of each
Cu in p the same way, if there is a danger of confusion we will explicitly write
σ(p) ⊂ Cu . Noting that entire transformations are compositions of zipping
moves and collapses (c.f. Section 3.1), the continuous map Cu → Cu′ actually
induces a retraction of σ(p) ⊂ Cu onto σ(p) ⊂ Cu′ . It follows that σ(p) ⊂ Cu′
naturally embeds into σ(p) ⊂ Cu . Along the path p(t1 ) given in (9) we will
write |σ(p)|tu to denote the hitting measure of σ(p) ⊂ Cu with respect to tu .
By the embedding above we have a chain of proper inequalities
|σ(p)|t1 > · · · > |σ(p)|tP > 0.

(10)

Definition 6.2. Suppose now a subset σ is a union of bases and a track t is
carried by C . We call the following quantity excess:
!
X
|µ|t − 2|σ|t .
ψt (σ) =
µ⊂σ

Excess measures how far the σ is from being quadratic as quantified by the
hitting measure. From the definition of the entire transformation, a straightforward counting argument gives the following.
Lemma 6.3 (Excess is invariant, c.f. [BF95, (7.6.1)]). Let p(t1 ) be the Rips
process given in (9), i.e. all moves are entire transformations and J-relative
τ -complexity is constant. Then we have equalities
ψt1 (σ(p)) = · · · = ψtw (σ(p)) .

6.2

Bounding the quadratic part

We can decompose σ(p) ⊂ C1 into
σ(p) = Q(p) ∪ SQ(p) ⊂ C1
where Q(p), the quadratic part of σ(p), is the closure of the set of points that
are contained in exactly two bases. We define SQ(p), the superquadratic part
of σ(p), to be the closure of σ(p) \ Q(p) (all points in SQ(p) lie in at most
three bases.) It is worth noting that this decomposition is almost disjoint

48

(intersection consists of finitely many points) and that some bases may lie
partially in Q(p) and partially in SQ(p).
If we forget the tracks ti carried by Ci in p(t1 ) then we have an induced
superquadratic path
p : C1 → · · · → CP
(11)
with constant J-relative τ complexity that lies in T(C , J). Note that we are
not requiring Cp to be terminal.
Lemma 6.4. We can construct a computable function frep , depending only on
the band complex C and a path p as in (11), with positive integer values such
that for any automorphically minimal track t efficiently carried by C1 we have
the inequality:
|Q(p)|t ≤ frep (Cv , p) · |SQ(p)|t .
(12)
Proof. Subdivide each band (Definition 3.6) so that each base either entirely
lies in Q(p) or intersects Q(p) with empty interior. Q(p) is now a union of
maximal sections (Definition 2.7). Let JQ be the complement of Q(p). Consider the JQ -restricted admissible elimination tree A(C1 , JQ ). Since σ(p) is a
union of bases that is closed under taking duals, the leaves of A(C1 , JQ ) will be
band complexes in which every base in Q(p) is eventually moved onto SQ(p).
On the other hand, since A(C1 , JQ ) is JQ -relatively quadratic, by Propositions
4.26 and 4.27 the subtree A(C1 , JQ ) is finite and therefore algorithmically constructible.
Going backwards in A(C1 , JQ ) from every admissible leaf to the root C1
(recall Section 4.1) and repeatedly applying the upper bound of Lemma 4.7
gives us a finite (algorithmically constructible) set of upper bounds for lengths
of the bases in Q(P ) in C1 in terms of |SQ(p)|t . The maximum over this set
can be used to compute an upper bound of |Q(p)|t in terms of |SQ(p)|t for any
automorphically minimal track t efficiently carried by C1 .
Whenever a base λu is the carrier in (Cu , tu ) → (Cu′ , tu′ ) in (9), after
transferring other bases, it gets shortened. The bound given by Lemma 6.4
and the invariance of excess tell us that, although bases get shorter, their
lengths remain bounded below throughout p. This will force them to overlap.
Lemma 6.5. Let p(t1 ) be as in (9) and let λu ∈ C(p) ∪ T (p) be the base in Cu
such that |λu |tu is maximal. The initial length |σ(p)|t1 is always bounded by
|σ(p)|t1 ≤ (frep (C1 , p) + 1) N 2 |λu |tu
where N is the number of bases in Cu .
Proof. In (Cu , tu ), every µ ∈ C(p)∪T (p) has length at most |λu |tu . It therefore
follows that |σ(p)|tu ≤ N · |λu |tu . Now since there are no more than N bases,
each point in σ(p) is contained by at most N bases. The strict upper bound
for the invariant excess
ψt1 (σ(p)) = ψtu (σ(p)) < N 2 · |λu |tu
as well as the bound |SQ(p)|t1 ≤ ψt1 (σ(p)) combine with Lemma 6.4 to give
the desired inequality since |σ(p)|t1 = |Q(p)|t1 + |SQ(p)|t1 .

49

6.3

Orientation reversing overlaps: two lemmas

The proof in the next section requires two additional lemmas.
Lemma 6.6. Suppose π1 (C ) has no elements of order 2, and t ∈ tracksκ (C ).
Then for any dual pair (µ, µ) such that µ ∩ µ 6= ∅ that is orientation reversing
we have
|µ ∩ µ|t < κ + 1.
Proof. Since µ ∩ µ 6= ∅ and (µ, µ) is orientation reversing, the image of B(µ)
in C contains a Möbius band. Let the simple closed curve γ be homotopic to
the core of this band. We may view γ an element of π1 (C ). If C efficiently
carries a track t then γ must invert some segment in T (t, C ); thus γ 6= 1.
By assumption γ 2 6= 1 , but an analysis of the action of γ 2 on Ce and T (t, C )
similar to the one shown in Figure 10 shows that γ 2 fixes an arc of length |µ∩µ|t
in T (t, C ). κ-acylindricity therefore ensures the required bound.
Lemma 6.7. Let (µ, µ) be an overlapping pair and suppose that (λ, λ) is orientation reversing and λ ∪ λ ⊂ σ(µ). If π1 (C ) has no 2-torsion then for any
t ∈ tracksκ (C )
|λ|t < tr(µ) + κ + 1.
Proof. Suppose towards a contradiction that |λ|t ≥ tr(µ) + κ + 1. Assume
that λ is to the left of λ and let q be the leftmost point of λ. By successively
transferring λ through B(µ) we can arrange so that the leftmost point of λ is
moved to a distance of less than tr(µ) to the right of q it therefore follows that
|λ ∩ λ|t ≥ κ + 1, which contradicts Lemma 6.6.

6.4

Cutting off too much

We now introduce C-T cycles which are guaranteed to “shorten” σ(p) ⊂ Cv by
some fixed amount each time they occur. The idea of a C-T cycle is inspired
from Case 3 in the proof of [AHT06, Theorem 12].
Definition 6.8. Let p be as in (9). A C-T cycle is a sub-path Cj → · · · → Ck
such that for each λ ∈ C(p) there is some j ≤ l ≤ k such that λ is the carrier
in some Cl and one of the following occurs:
• If λ either doesn’t overlap with its dual or is orientation reversing, then
for some l < l′ ≤ k, some base δ that was transferred by λ in Cl → Cl+1
is a leading base again in Cl′ .
• If (λ, λ) form an overlapping pair, then there are l < l′ < l′′ ≤ k such
that λ gets carried in Cl′ (i.e. it ceases to be a carrier) and is a leading
base again in Cl′′ . Also there is some some base δ that was transferred
in Cl → Cl+1 is again a leading base in Cl′′′ for some l < l′′′ ≤ k.
Lemma 6.9. Let p(t1 ) be a path as in (9) and let Cj → · · · → Ck be a CT cycle in p(t1 ), then either every base in C(p) ∪ T (p) has length at most
max{2κ, 1}, or
|λ|tj
(13)
|σ(p)|tj − |σ(p)|tk ≥
2(2 + κ)
where λ is the longest base in Cj .

50

Proof. First note that until λ is the carrier in some Cl where j ≤ l ≤ k we
have
|λ|tj = |λ|tj +1 = · · · = |λ|tl .
By definition of a C-T cycle, there is such a j ≤ l ≤ k where λ is the carrier in
Cl . Assume that |λ|tj > max{2κ, 1}. We will now show (13), the proof divides
into cases; decimals denote subcases.
Case 1: λ does not overlap with its dual. In this case let δ be some base
that is carried by λ it is moved by at least |λ|tj to the right. By definition of
a C-T cycle there some l < l′ ≤ k where δ is a leading base in Cl′ again which
means that |σ(p)|tl − |σ(p)|t′l ≥ |λ|tj so the result holds. (See Figure 20.)
Case 2: λ has nontrivial intersection with λ.
Case 2.1: (λ, λ) is orientation reversing. Let δ be some base that carried
by λ. Then δ is moved 2|λ|tl − |λ ∩ λ|tl − |δ|tl to the right. On one hand
|δ|tl ≤ |λ|tl , on the other hand by Lemma 6.6 |λ ∩ λ|tl ≤ κ we therefore conclude that δ is moved at least |λ|tl − κ to the right. When δ is again a leading
base in Cl′ , l < l′ ≤ k then
|σ(p)|tl − |σ(p)|tl′ ≥ |λ|tl − κ − 1 ≥

|λ|tl
2

so (13) holds.
Case 2.2: (λ, λ) form an overlapping pair. There is some maximal l′ such
that in Cl → . . . → Cl′ −1 , λ is always the carrier base. Note moreover that
tr(λ) remains constant.
Case 2.2.1: |λ|tl ≤ (2κ + 2)tr(λ). Let δ be some base that is carried by
λ. Then it is moved to the right by tr(λ) and by hypothesis there is some
l < l′′′ ≤ k such that δ is leading again, hence
|σ(p)|tl − |σ(p)|tl′ ≥

|λ|tl
2κ + 2

and (13) holds.
Case 2.2.2: |λ|tl > (2κ + 2)tr(λ).
|λ|tl
. (13) immediately holds.
2(2κ + 2)
|λ|tl
Case 2.2.2.2: |σ(p)|tl − |σ(p)|tl′ <
. In particular, in Cl′
2(2κ + 2)




4κ + 3
1
= |λ|tl
> (2κ + 3/2)tr(λ)
|λ|tl′ > |λ|tl 1 −
2(2κ + 2)
2(2κ + 2)
Case 2.2.2.1: |σ(p)|tl − |σ(p)|tl′ ≥

by the Case 2.2.2 assumption on |λ|tl .

51

(14)

Case 2.2.2.2.1: The carrier η in Cl′ does not overlap with its dual. In this
case λ is moved to the right by at least |λ|tl′ and we note that for all κ ≥ 0 we
have:
1
1
> 1/2 >
;
1−
2(2κ + 2)
2(2κ + 2)
thus when λ is a leading base again in Cl′′ , by (14) we have
|σ(p)|tl′ − |σ(p)|tl′′ >

|λ|tl
2

so (13) holds.
Case 2.2.2.2.2 The carrier η in Cl′ has nontrivial intersection with η and
is orientation reversing. Note that


1
|η|tl′ > |λ|tl′ ≥ |λ|tl 1 −
.
2(2κ + 2)
As in Case 2.1 we deduce that η carries λ more than |λ|tl′ − κ to the right.
So that in Cl′′ when λ is leading again at least |λ|tl′ − κ was cut from σ(p).
Suppose towards a contradiction that
|λ|tl′ − κ <

|λ|tl
.
2(2κ + 2)

Then since we are in Case 2.2.2.2 we have


1
|λ|tl 1 −
− κ < |λ|tl′ − κ
2(2κ + 2)
Combining these gives

1
−κ
|λ|tl 1 −
2(2κ + 2)


2
⇒
|λ|tl 1 −
2(2κ + 2)


4κ + 2
⇒
|λ|tl
4κ + 4


2
⇒ |λ|tl < 1 +
κ
(4κ + 4)


<

|λ|tl
2(2κ + 2)

<κ
<κ
3
< κ
2

which contradicts our assumption that |λ|tl > 2κ
Case 2.2.2.2.3: (η, η) form an overlapping pair where η in Cl′ is the carrier.
We may assume that, after repeatedly getting shortened in Cl → . . . → Cl′ −1 , λ
is still long enough in Cl′ for (λ, λ) to an overlapping pair. Indeed suppose this
was not the case. By not overlapping we have |λ|tl′ < tr(λ), and substituting
into the the Case 2.2.2 assumption yields
|λ|tl′ <

|λ|tl
.
(2κ + 2)

52

This contradicts (14) since
1−

1
1
>
.
2(2κ + 2)
2κ + 2

Case 2.2.2.2.3.1: (Recall Definition 5.5) In Cl′ , σ(η) ⊂ σ(λ). This means,
since we are in Case 2.2.2.2, that
|η|tl′ > (2κ + 3/2)tr(λ) > tr(λ) + κ + 1
so by Lemma 5.13 τλ and ρησ(λ) commute, so the overlapping pairs (µ, µ) and
(λ, λ) are entangled. By Lemma 5.17 we can apply the periodic merger of
Proposition 5.20 to merge the bands B(η) and B(µ). Since we are working
in the elimination tree T+ (C) by (4m) of Definition 5.23 we must merge the
bands B(η) and B(λ) which decreases the complexity. This contradicts the assumption that the τ -complexity remains constant throughout p.
Case 2.2.2.2.3.2: In Cl′ , σ(η) ⊃ σ(λ). We finally distinguish two sub-cases:
Case 2.2.2.2.3.2.1:(κ + 2)tr(η) ≤ |λ|tl′ . Again as in Case 2.2.2.2.3.1 we can
perform a periodic merger.
Case 2.2.2.2.3.2.2:(κ + 2)tr(η) > |λ|tl′ . In this case λ gets moved by tr(η) to
the right. λ is again a leading base in Cl′′ then we will have cut at least tr(η)
from σ(p) in passing from Cl′ to Cl′′ . On one hand since this is a sub-case of
Case 2.2.2.2 we have


|λ|tl′
|λ|tl
1
>
1−
,
tr(η) >
κ+2
κ+2
2(2κ + 2)
where the last inequality is from (14), and we can estimate

⇒
⇔
⇔

2(2κ + 2) 1
κ+2 2


2(2κ + 2)
1
1−
κ+2
2(2κ + 2)


1
1
1−
κ+2
2(2κ + 2)


1
|λ|tl
1−
κ+2
2(2κ + 2)

⇒

tr(η)

≥1
>1
1
2(2κ + 2)
|λ|tl
>
2(2κ + 2)
|λ|tl
.
>
2(2κ + 2)
>

(13) therefore holds and, furthermore, all possibilities have been exhausted.
We can now combine lemmas 6.5 and 6.9.
Corollary 6.10. Let p be a path as in (9), i.e. a path induced by an automorphically minimal κ-track efficiently carried by C1 . Then at most
N 2 (frep (C1 , p) + 1)(2κ + 2)
disjoint C-T cycles can occur.

53

Proof. By Lemmas 6.9 and 6.5, whenever a C-T cycle Cj → · · · → Ck occurs
we can bound from below the difference
|σ(p)|t1
.
|σ(p)|tj − |σ(p)|tk ≥ 2
N (frep (C1 , p) + 1)(2κ + 2)
Since |σ(p)|t1 > |σ(p)|t2 > · · · > 0 the desired bound on the number of C-T
cycles follows.

6.5

C-T-inadmissibility and a reduction to µ-periodicity

Given a path p in a (restricted) elimination tree T+ (C , J) we can define the
sets C(p) and T (p) (Definition 6.1) and therefore corresponding C-T cycles
(Definition 6.8).
Definition 6.11. If a path p : Cv → · · · → Cu in T+ (C , J) contains more
disjoint C-T cycles than the computable bound given by Corollary 6.10, then
it is called C-T-inadmissible.
Definition 6.12 (Admissible). A subtree of T+ (C , J) is said to be admissible
if it doesn’t contain any leaves that are inadmissible (recall (3) in Section 4), κinadmissible paths (Definition 4.14), repetition inadmissible paths (Definition
4.18), or C-T inadmissible paths. We denote by A+ (C , J) ⊂ T+ (C , J) the
maximal admissible subtree, and call it the admissible elimination tree.
Proposition 6.13. Any path p : C → · · · in T+ (C , J) induced by an automorphically minimal κ-track efficiently carried by C must also lie in A+ (C , J).
Proof. This follows immediately from Proposition 4.23 and Corollary 6.10.
Definition 6.14. Let µ be the carrier base in C . A path
p : Cu → · · ·
in T+ (C , J) is called µ-periodic if, throughout p, µ is the carrier base and
(µ, µ) forms an overlapping pair.
Proposition 6.15. Any infinite path of A+ (C , J) has a tail
Cu → · · ·
that is λ-periodic for some base λ.
Proof. Let p be some infinite path of A+ (C , J). We can form the sets C(p)
and T (p), since every tail p′ of p gives C(p′ ) ⊂ C(p) and T (p′ ) ⊂ T (p), passing
to a tail of p we may assume that each base in C(p) is carrier infinitely often
and every base in T (p) is carried infinitely often.
We may further assume that the (relative) τ -complexity remains constant,
that no annulus subdivisions or Möbius moves occur, and that p is superquadratic.
If C(p) consists of more than one element then infinitely many C-T cycles (Definition 6.8) occur so p is not contained in an admissible subtree.
It therefore follows that some base λ must repeatedly be the carrier throughout p. Now if λ doesn’t overlap with λ after N (the total number of bases)
entire transformations λ can no longer be a maximal leading base. It follows
that (λ, λ) form an overlapping pair.

54

Therefore, if we can find a computable bound on the number of times in a
row the same base λ can be a carrier base in some λ-periodic path Cv → · · ·
induced by a minimal κ-track efficiently carried by Cv , then we will be able
to effectively constructed a finite subtree of A+ (C), whose leaves give a set of
tracks containing all automorphically minimal κ-tracks efficiently carried by
C.

7 Bounding the periodicity of overlapping
pairs
Definition 7.1. We say that a maximal leading base λ is a principal overlapping carrier if (λ, λ) form an overlapping pair and there are no other overlapping pairs (µ, µ) that can be merged with (λ, λ).
By Proposition 6.15, in any sufficiently long admissible branch in T+ (C),
the situation depicted in in Figure 21 will occur. At each such entire trans-

δ
◮
µ
◮

λ
◮
λ
◮

δ
◮
µ
◮

λ
◮
λ
◮

tr(λ)
Figure 21: An entire transformation where the leading base λ
forms a principal overlapping carrier. The transfer base δ is moved
to the right by tr(λ). If δ is eventually a leading base again, then
|λ| will have decreased by tr(λ).
formation although |λ| decreases, tr(λ) is invariant. Taking inspiration from
words, where a large initial segment of a word overlaps with a terminal segment, e.g. abcabcabcab, we have the following:
Definition 7.2. Let C be a band complex efficiently carrying a track t and
suppose that (λ, λ) form an overlapping pair. We define the periodicity of λ
to be the positive integer
periodt (λ) =

55

j |λ| k
t
.
tr(λ)

Lemma 7.3. Let λ be a principal overlapping carrier in an band complex C
efficiently carrying a track t with N bases. Then in the Rips process induced
by t starting at (C , t), λ can be the maximal leading base at most N periodt (λ)
times in a row.
Proof. Each time a base δ is carried by λ it is moved to the right by tr(λ).
The next time that base is carried the base λ will be shortened by tr(λ) so the
advertised bound holds.
It therefore follows that the periodicity of λ bounds the number of consecutive times λ can be a carrier in a Rips process. Equivalently, this is the maximal
length of a λ-periodic path. Given an band complex C that has a principal
overlapping carrier λ, we will compute an upper bound for periodt (λ) that
holds for every automorphically minimal κ-track t. If periodt (λ) exceeds this
bound, we prove the existence of another automorphically equivalent track t′ efficiently carried by C such that Size(t′ ) < Size(t). It is worth noting that, since
we are requiring automorphic equivalence, simply applying Bulitko’s lemma is
not good enough, as the latter only bounds minimal periodicity in possibly
non-injective homomorphic images.
To compute this bound we will construct auxiliary elimination trees. This
will require all the machinery developed up until now as well as a few new
ideas. The auxiliary tree will in fact be a rooted tree of trees. Off the leaves
of this tree we will be able to read an upper bound for the periodicity.
Proposition 6.15 combined with this periodicity bound for every occurring
principal overlapping carrier in A+ (C) will finally enable us to construct a
finite subtree guaranteed to give us all the tracks we need for Theorem B.

7.1

Periodic block form, and the tree TPBF(C , J)

Definition 7.4. Suppose that for some overlapping pair (λ, λ), σ(λ) is a maximal section (recall Definition 2.7). Then we call σ(λ) a periodic block. A
band complex such that every base lies in some periodic block is said to be in
periodic block form.
We now describe another J-restricted elimination process which constructs
the tree TPBF (C , J). This process brings a band complex C into periodic
block form and is a variation of the construction of A+ (C , J); only this time,
whenever we encounter a principal overlapping carrier, we add a new band
B(δ), transfer (λ, λ) all the way to the right using entire transformations,
and enlarge J to J ∪ σ(λ), see Figure 22. By Proposition 6.15, we will have
constructed a finite admissible tree in which every leaf is a band complex whose
bases either lie in J or in some periodic block. We build TPBF (C , J) as follows:
(1) We perform a J-restricted elimination process, adding only admissible
band complexes (recall Definition 6.12).
(2) If at some point as we grow our tree there is a Ci with a principal overlapping carrier λ then instead as doing an entire transformation we do
the following:

56

ρ
◮
µ
◮
λ
◮

ν
◮
λ
◮

(2a)

µ
◮
λ
◮

ν
◮

λ
◮
δ
◮

(2b)

ν
◮

δ
◮

ρ
◮
µ
◮
λ
◮

ρ
◮

δ
◮

ν
◮

λ
◮
δ
◮

δ
◮

µ
◮
λ
◮

ρ
◮

λ
◮
δ
◮

σ(λ)
(2c)
Figure 22: Creating a new periodic block for the principal overlapping carrier λ. Depicted is the sequence (2a) - (2c) in the
construction of TPBF (C , J).
(a) We attach a band B(δ) to Ci by identifying δ + σ(λ), so that δ
doesn’t meet any other bases. We extend the ordering <i so that
the maximal section corresponding to δ is terminal (Definition 3.21.)
(b) We transfer all the bases contained in σ(λ) through B(δ) onto δ.
(c) We collapse the naked initial segment of δ. This gives the Ci′ .
(d) We set J ′ = J ∪ σ(λ) and we continue growing our tree at Ci′ by
returning to step 1 but with J ′ in place of J.
(3) If after step (2d) we have moved all the bases onto J ′ then we stop.
By direct inspection we verify:
Lemma 7.5. If (Ci , J) is quadratic or superquadratic, then after performing
steps (2a) - (2d), the resulting band complex is still quadratic or superquadratic
(respectively).
Lemma 7.6. If we add a band B(δ) to C1 as in (2a), then transfer all the
bases contained in σ(λ) onto δ as in (2b) to produce Ci′ , then τ (Ci ) ≥ τ (Ci′ ).
Moreover if J and J ′ are as in (2d) above then we have a strict inequality
τ (Ci , J) > τ (Ci′ , J ′ ).
Proof. We keep track of the τ -complexity. Adding the band B(δ) adds a base
to a maximal section σ with b(σ) ≥ 2 (recall Definitions 2.7 and 3.13), which
increases the τ -complexity by 1, and creates another maximal section σ(δ)
with only one base, which doesn’t contribute to the τ -complexity. We then

57

move the base λ onto σ(δ) which decreases b(σ) by 1. Now b(σ(δ)) = 2, so it
still contributes 0 to the τ -complexity. So far we have added 1 and removed 1
from the τ -complexity. Since λ was assumed to be a leading base and δ ⊃ λ,
doing the rest of (2b) and (2c) amounts to sequence of transformations, which
do not increase the τ -complexity.
After all this σ(λ) is a maximal section with τ (σ(λ)) > 0 and σ(λ) ∩ J = ∅
which implies that τ (Ci , J) > τ (Ci′ , J ′ ).
Corollary 7.7. TPBF (C , J) is finite. Furthermore, if t ⊂ C is an efficiently
carried automorphically minimal κ-track, then the path C → · · · → Cp to a
band complex in periodic block form induced by t is contained in TPBF (C , J).
Proof. We first prove the first statement. Suppose towards a contradiction that
this was not the case, then TPBF (C , J) has an infinite branch b. Seeing as we
are constructing an admissible elimination tree in the sense of Definition 6.12,
by Proposition 6.15 this infinite branch can be assumed to start with some Cu
with a principal overlapping carrier λ. By the definition of TPBF (C , J), this
means we must construct a new periodic block, item (2), which by Lemma
7.6 strictly decreases the relative τ -complexity, so this event can only happen
finitely many times, contradicting the the fact that b is infinite.
The second claim follows immediately from Proposition 6.13.

7.2

Normalized periodic block form

Once a band complex C is in periodic block form, it will be possible to perform
periodic block mergers, which decreases the number of periodic blocks and the
τ -complexity. Furthermore it will enable us to put a partial order on the
periodic blocks, called a periodic hierarchy. First we give another version of
entanglement.
Definition 7.8. If (µ, µ) is an overlapping pair such that σ(µ) is a maximal
section (Definition 2.7) then (µ, µ) is called a block overlapping pair.
In particular, if C is in periodic block from, then every maximal section is
in fact a block overlapping pair.
Definition 7.9. Let (λ, λ) and (µ, µ) disjoint block overlapping pairs. Suppose
there is a band B(δ) connecting σ(λ) and σ(µ), i.e. δ ⊂ σ(λ) and δ ⊂ σ(µ).
For any p ∈ B(δ) we can define δ-relative tubular elements τλδ , τµδ as in Figure
23. (λ, λ) and (µ, µ) are entangled by B(δ) if
[τλδ , τµδ ] = 1.
Lemma 7.10. Let (µ, µ) and (λ, λ) be entangled by B(δ). If [τµδ , τλδ ] = 1 then
τµδ and τλδ have the same axis in the dual Bass-Serre tree T (t, C ) and lie in a
common cyclic subgroup.
sketch. This is proved the same way as Lemma 5.12.

58

β
◭

◮

◭
α γ
p

Figure 23: δ-relative tubular elements. The relative tubular element τλδ is the loop based at p given by α ∗ β ∗ γ ∗ α−1 .
Lemma 7.11. In the band complex C , let (µ, µ) and (λ, λ) be block overlapping
pairs let B(δ) satisfy δ ⊂ σ(µ) and δ ⊂ σ(λ). If for some t ∈ tracksκ (C )
|δ|t > max {tr(µ) + κ, tr(λ) + κ} ,
then (µ, µ) and (λ, λ) are entangled by B(δ). Furthermore the tubular elements
τλδ and τµδ have the same axis in T (t, C ).
sketch. This is proved the same way as Lemma 5.13.
We can’t simply widen some band B(λ) and still have a well formed band
complex and preserve the dual tree. We could do this in Lemma 5.16, by
studying what happened in the dual tree and by noting that the result was
still a well formed band complex. A similar analysis for block overlapping pairs
gives the following:
Lemma 7.12. Let (µ, µ) be a block overlapping pair in a band complex C and
let t ∈ tracksκ (C ). Then we can obtain a new band complex C ′ ⊃ C , equipped
with an efficiently carried κ-track t′ , by widening B(µ). After widening, µ has a
initial naked segment and we recover C ′ → C by collapsing (Definition 3.3) this
initial segment. The dual Bass-Serre trees T (t′ , C ′ ) and T (t, C ) are therefore
equivariantly isomorphic. Furthermore tr(µ) remains invariant.
Lemma 7.13. Let (µ, µ) and (λ, λ) be block overlapping pairs entangled by
B(δ) in a band complex C . Then for any κ-track t efficiently carried by C we
can obtain a new band complex C ′ ⊃ C by first widening B(λ), B(µ) by at most
|λ|t + |µ|t and then widening B(δ) so that
(i) either σ(λ) ⊂ δ or σ(µ) ⊂ δ, and
(ii) the track t extends to a track t ⊂ t′ efficiently carried by C ′ such that
there is a π1 (C )-equivariant isomorphism of dual Bass-Serre trees
∼

T (t, C ) → T (t′ , C ′ ).
We note that λ, µ only need to be increased to length at most |λ|t + |µ|t
for this to work.

59

7.2.1

The periodic block merger

We now describe the periodic block merger, see Figure 24. Let C have block
overlapping pairs (µ, µ), (λ, λ) entangled by B(δ). We do the following:
(1) Widen bands B(λ), B(µ) and then B(δ) to obtain a band complex C ′ as
given in Lemma 7.13.
(2) Assume that δ ⊃ σ(λ). We treat δ as carrier base and move all the bases
contained in σ(λ) onto δ via entire transformations.
(3) The dual pairs (λ, λ), (µ, µ) are now entangled in the sense of Definition
5.10 and both form overlapping pairs, so by Lemma 5.17 we can apply
the periodic merger given in Proposition 5.20, merging B(λ), B(µ) into
some new B(η).

Figure 24: Steps (1) and (2) of type periodic block merger.
We now record the following observation.
Lemma 7.14. Let C be a band complex containing block overlapping pairs
(λ, λ), (µ, µ) entangled by B(δ). Then we can effectively construct a finite set
of band complexes
C
C1

···

Cn

containing all possible combinatorial outcomes m : (C , t) → (C ′ , t′ ) of applying
a periodic block merger as t ranges over tracksκ (C ).

7.2.2

Normalization: merging away entanglement

It may be that (µ, µ) is a block overlapping pair that is entangled with (λ, λ)
but |λ|t < tr(µ), for example if λ, λ are very short and near the extremities of
(µ, µ). In this situation it is not possible to directly apply a periodic merger.
However since block overlapping pairs can always be widened we have the
following:
Lemma 7.15. Let C have a block overlapping pair (µ, µ) overlapping pair
entangled with (λ, λ). For any t ∈ tracksκ (t) we can widen B(µ) by tr(µ) so
that after widening B(λ) we have |λ|t ≥ tr(µ).
Proof. By Lemma7.12, we can widen (µ, µ) (by at most tr(µ)) so that λ is
at distance more than tr(µ) from the endpoints of σ(µ). It follows that after
widening as in Lemma 5.16, λ is sufficiently long.

60

Corollary 7.16. Let C have a block overlapping pair (µ, µ) overlapping pair
entangled with (λ, λ). For any t ∈ tracksκ (t), after perhaps widening B(µ) by
at most tr(µ) and B(λ) as in Lemma 5.16, we can perform a periodic merger
(Proposition 5.20) of B(µ) and B(λ).
Definition 7.17. Let C be a band complex in periodic block form and let
t ∈ tracksκ (C ), then we can repeatedly apply periodic block mergers and
periodic mergers as described in Corollary 7.16 so no block overlapping pair
is entangled with any other base pair. If such is the case then we call corresponding m : (C , t) → (C ′ , t′ ) the normalization of (C , t) and we say that C ′
is in in normalized periodic block form.
We now give the combinatorial equivalent. Recall that entanglement is
algorithmically decidable and depends only on the band complex C .
Definition 7.18. Let C be a band complex in periodic block form. Then its
normalized children is the collection of band complexes
C
C1

···

Cn

obtained by enumerating all possible combinatorial outcomes of normalizations
m : (C , t) → (C ′ , t′ ) where t ranges over tracksκ (C ).

7.3

Periodic hierarchies and maximal periodic blocks

Throughout this section C will be a band complex in normalized periodic block
form.
Definition 7.19. Let C be in normalized periodic block form, let t ∈ tracksκ (C ),
and let σ(λ) be a periodic block. A base δ ⊂ σ(λ) is t-long in σ(λ) if
|δ|t ≥ tr(λ) + κ + 1. Otherwise it is called t-short.
Lemma 7.20. Let C , t, λ, and δ be as in Definition 7.19. Then if δ also lies
in σ(λ), δ must be t-short in σ(λ).
Proof. If (δ, δ) is orientation reversing, then this follows immediately from
Lemma 6.7. If (δ, δ) is orientation preserving, but t-long in σ(λ), then it is
entangled with (λ, λ), but not merged. By Corollary 7.16 this contradicts the
assumption that C is in normalized periodic block form.
It is possible for a base to be long in one periodic block, but its dual must
lie in another periodic block and it must be short in that periodic block. If a
base and its dual are both long in their respective periodic blocks then we can
perform a periodic block merger.
Definition 7.21 (Periodic hierarchies). Let the band complex C be in normalized periodic block form. A periodic hierarchy H is a partial order <H on
the set of periodic blocks that is generated as follows:

61

(i) If B(δ) has bases lying in in periodic blocks σ(λ1 ) and σ(λ2 ) then we may
either declare σ(λ1 ) <H σ(λ2 ), σ(λ2 ) <H σ(λ1 ), or that σ(λ1 ) and σ(λ2 )
are incomparable.
(ii) We extend (i) to a partial order, if possible.
A periodic block σ(λ) is H-maximal if it is maximal with respect to the partial
order. If t ∈ tracksκ (C ) then we define the induced periodic hierarchy H(t)
to be generated by setting σ(λ1 ) <H(t) σ(λ2 ) if and only if δ is t-long in σ(λ1 )
in (i).
It is obvious that periodic hierarchies, being finite combinatorial objects,
can be effectively listed. What is less obvious is whether the definition of an
induced periodic hierarchy actually gives a periodic hierarchy.
Lemma 7.22. If C , t and H(t) are as in Definition 7.21 then <H(T ) gives a
partial order on the set of periodic blocks; thus H(t) is a periodic hierarchy.
Proof. Suppose that for some B(δ), both δ and δ were long in σ(λ1 ) and σ(λ2 ),
respectively. Then by Lemma 7.11 the block overlapping pairs are entangled
and can be merged, contradicting the assumption that C is normalized, so (i)
of Definition 7.21 is satisfied. Thus (i) gives a directed graph Γ without loops
of length 2 with periodic blocks as vertices. If Γ has a directed cycle, then
this would imply that for some (λ, λ), tr(λ) < tr(λ) which is absurd. We can
therefore extend H to a partial order giving (ii) of Definition 7.21.
Corollary 7.23. If (λ, λ) is an H(t)-maximal block overlapping pair, then
every base δ ⊂ σ(λ) is t-short.

7.4 Bounding the periodicity of maximal periodic
blocks
Definition 7.24. Suppose σ(λ) is a periodic block and suppose that we can
vertically subdivide B(λ) into three bands
B(λ1 ), B(λ2 ), B(λ3 )
such that:
• (λ2 , λ2 ) form an overlapping pair.
• No bases other than λ1 and λ3 intersect σ(λ2 ).
• B(λ2 ) contains no connections (recall Definition 2.3(3a).)
Then we call B(λ2 ) a clean tube.
The significance of clean tubes is illustrated in Figure 25. Although the
next result is obvious from this picture. It is important to state it carefully to
get explicit bounds.
Lemma 7.25. Let t be an automorphically minimal κ-track efficiently carried
by C , and let σ(λ) be a periodic block. Then for any clean tube B(λ2 ) ⊂ B(λ),
|λ2 |t ≤ 2tr(λ).

62

Figure 25: A clean tube in a band complex is literally an embedded
S 1 ×[−1, 1]. The track t spirals around the clean tube. Unwinding
it by a Dehn twist will decrease the size.
Proof. Suppose towards a contradiction that for some clean tube B(λ2 ) we
have:
|λ2 |t > 2tr(λ).
Let I ⊂ λ2 ∩ λ2 be interval of length tr(λ) that is of distance tr(λ) the leftmost
endpoint of of σ(λ2 ). Let p ∈ t ∩ I be the rightmost point of t ∩ I, if we follow
the the connected component of t∩B(λ2 ) that contains p and intersects I again
in p′ we see that the distance between p and p′ in λ2 is exactly tr(λ). Recall
the notation of Definition 2.1 and consider the map
JB(λ2 ) × [−1, 1] → C
with JB(λ2 ) × {1} → λ2 and JB(λ2 ) × {−1} → λ2 . The preimage of I has two
connected components I±1 ⊂ JB(λ2 ) × {±1}. Let α be the straight line in
JB(λ2 ) × [−1, 1] between the rightmost point of I1 and the rightmost point of
I−1 and let β be the line in JB(λ2 ) ×[−1, 1] between the leftmost point of I1 and
the leftmost point of I−1 . α and β are chosen to be transverse to the preimage
of t. Let Q be the quadrilateral in JB(λ2 ) × [−1, 1] enclosed by I±1 , α, β (see
Figure 26.) Then via JB(λ2 ) × [−1, 1] → C , Q is mapped to an annulus A ⊂ C
such that Q ⊂ B(λ2 ) with α, β mapping onto each component of ∂A.

I1

◭

◭

β

α

I−1
Figure 26: The quadrilateral Q inside B(λ2 ). The annulus A is
obtained by identifying I1 and I−1 . The track is drawn as dashed
lines.
We parameterize this annulus A as
{r exp(iθ)|1 ≤ r ≤ 2, 0 ≤ θ ≤ 2π} ⊂ C.

63

(15)

By construction, tA = t ∩ A corresponds to the curve:
tA : [0, 1] → A
s 7→ (2 − s) exp(i(2πs)).

If we make a Dehn τA twist around A then post-composing gives:
τA ◦ tA : [0, 1] → A
s 7→ (2 − s).

β
◭

β
◭

◭
α

◭
α

Figure 27: On the left the image A of Q after identifying I1 and
I2 parameterized as (15) (drawn to scale). On the right the result
of the Dehn twist τA . The the dashed line represents tm ∩ A. Note
that τA restricts to the identity on ∂A
Such a Dehn twist is illustrated in Figure 27. Since the homeomorphism τA
restricts to the identity on ∂A, it extends to a homeomorphism of C which we
will also denote τA . Consider the new track τA (t). On one hand, τA (t) is still
efficiently carried by C . On the other hand, after perturbing by an isotopy we
have, τA (t) ∩ σ(λ) = t ∩ σ(λ) − 1, but otherwise for every subset S ⊂ C \ B(λ2 )
we have S ∩ t = S ∩ τA (t). It follows that
Size(τA (t)) < Size(t)

(16)

e
e
The homeomorphism τA : C → C lifts to a homeomorphism of τf
A : C → C
sending the lift e
t to the lift τ]
A (t). Furthermore τA maps naturally to an
element of Aut(π1 (C )). It follows that the trees T (t, C ) and T (τA (t), C ) are
(τA )♯ -equivariantly-isomorphic so that t ∼Aut(π1 (C )) τA (t). τA (t) is therefore
obviously a κ-track, and with (16) we see that t is not automorphically minimal,
which is a contradiction.
Informally, if clean tubes are longer than twice the translation length, there
would be enough room to make an annulus, as shown in Figures 26, 27. This
would enable us to shorten the track t by a Dehn twist, contradicting automorphic minimality. Clean tubes therefore must be short. We now use this
observation to give a combinatorial bound for periodicity.

64

Corollary 7.26 (Periodicity bound for maximal periodic blocks). Let t ⊂ C be
an efficiently carried automorphically minimal κ-track and let σ(λ) be a H(t)maximal periodic block. Let |C| denote the number of connected components
of connection preimages in B(λ) = JB(λ) × [−1, 1] and let B denote the number
of bases, other than λ, λ contained in σ(λ). Then
periodt (λ) ≤ (6 + 2κ)B + 2|C| + 2.
Proof. Parameterize B(λ) as Jλ × [−1, 1] so that the preimage of t and of every
connection is contained in a union of vertical lines. Every base δ ⊂ B(λ) has
a preimage with connected components δ+ ⊂ Jλ × {1} and δ− ⊂ Jλ × {−1}.
Let C denote the preimage of the connections. Consider the complement
!!
[

Y = JB(λ) × [−1, 1] \ C ∪
δ± × [−1, 1]
,
δ

where δ runs over the bases contained in σ(λ). On one hand Y has at most
|C| + 2B + 1 connected components, on the other hand every maximal clean
tube contained in B(λ) is the preimage of one of these components, thus every
connected component of Y has length at most 2tr(λ) be Lemma 7.25. Furthermore, by Corollary 7.23 and Definition 7.19, every δ± has width at most
tr(λ) + κ. We therefore have the bound:
|λ|t ≤ 2B (tr(λ) + κ) + 2tr(λ) (|C| + 2B + 1)
≤ 2B (tr(λ) + tr(λ)κ) + 2tr(λ) (|C| + 2B + 1)
≤ tr(λ) ((6 + 2κ)B + 2|C| + 2) ;
from which we immediately obtain the advertised bound.
The significance of this bound is that it only depends on the combinatorial
band complex C and the combinatorial periodic hierarchy H(t). We obtain
the following computable function.
Definition 7.27. Let C be in normalized periodic block form, let H be a
periodic hierarchy on C , and let σ(λ) be H-maximal periodic block. We define
periodH (λ) = (6 + 2κ)B + 2|C| + 2
where B, |C| are as in Corollary 7.26.
Unfortunately it may be that the periodic block whose periodicity we are
interested in is not H-maximal. We deal with this in the next section.

7.5 Bounding the periodicity of principal overlapping carriers: auxiliary trees
Throughout this section we will use the following notation. If C is a band
complex, then the term J in the pair (C , J) will always denote a union of
block overlapping pairs. If C happens to be in normalized periodic block

65

form and is equipped with a periodic hierarchy H, then we will denote the
corresponding triple (C , J; H).
We will try to bound the periodicity of the block overlapping pairs that constitute J. It may happen however that two block overlapping pairs get merged
at some point. Because of this we will use the following naming convention.
Convention 7.28 (Renaming merged bases in auxiliary trees). Suppose that
two bands B(λ), B(µ) get merged onto some band B(η) in a periodic merger.
Then, as far as naming bases is concerned, we will consider η = λ = µ, i.e. we
will allow a base to have the multiple names.
This renaming convention is justified since on one hand, we want to bound
the periodicity of an overlapping pair that gets merged, so we must to keep
track of what it got merged with. On the other hand by the following result,
which is an immediate consequence of Position 5.20, we are guaranteed that
any periodicities we compute will be overestimates.
Lemma 7.29. Let (λ, λ) be an overlapping pair such that B(λ) gets zipped
onto B(η) via a periodic merger C → C ′ mapping an efficiently carried κtrack t ⊂ C into the efficiently carried κ-track t′ ⊂ C ′ . Then
periodt (λ) ≤ periodt′ (η).
In particular periodicities of block overlapping pairs are nondecreasing when
passing to normalizations.
Definition 7.30. Let (C , J) be a band complex with a principal overlapping
pair (λ, λ). Then we define the auxiliary children of (C , J) to collection:
(C , J)
(C1 , J ∪ σ(λ); H1 ) · · · (CN , J ∪ σ(λ); HN )
where
{(C1 , J ∪ σ(λ); H1 ), . . . , (CN , J ∪ σ(λ); HN )}
is obtained by first taking the leaves of TPBF (C , J), then taking their normalized children (Definition 7.18), and finally by taking all combinatorial possibilities for periodic hierarchies (Section 7.3).
In Section 7.3 we bounded the periodicity of a maximal block overlapping
pair, but it may be that σ(λ), where λ is a principal overlapping pair in
(C , J), is not a maximal periodic block in some of the auxiliary descendant
(Ci , J ∪ σ(λ), Hi ), due to the choice of periodic hierarchy Hi . It follows that
simply passing to auxiliary children isn’t sufficient to bound periodt (λ) where
t ranges over the automorphically minimal κ-tracks efficiently carried by C .
In Section 7.5.1 we will construct from (C , J) a finite auxiliary tree Taux (C , J ∪ σ(λ)).
If C efficiently carries an automorphically minimal κ-track t, then we will construct an induced tree Taux (C , t, J ∪ σ(λ)) in Section 7.5.2. This induced
tree will be proved to contain a combinatorial witness for an upper bound of

66

periodt (µ) for some base µ such that σ(µ) ⊂ J is a periodic block. We will
also have a containment
Taux (C , t, J ∪ σ(λ)) ⊂ Taux (C , J ∪ σ(λ)) .
From this it will follow that the construction of Taux (C , σ(λ)) will give a way
to bound periodt (λ) in C where t ranges over the automorphically minimal
κ-tracks.

7.5.1

The auxiliary tree Taux (C , J ∪ σ(λ))

We construct Taux (C , J ∪ σ(λ)) with the following recursive algorithm. The
reader may skip ahead to Figure 28 to get an idea of what this tree is supposed
to look like.
(0) If (λ, λ) is a principal overlapping pair in (C , J) then we declare (C , J)
to be the root of Taux (C , J ∪ σ(λ)). Write J ′ = J ′ ∪ σ(λ).
(1) The Taux (C , J ′ )-children of the root (C , J) are the auxiliary children of
C (Definition 7.30). These are connected to the root by auxiliary edges.
Further descendants are added as follows:
(a) If some periodic block σ(µ) ⊂ J ′ in an auxiliary child (C ′ , J ′ ; H′ ) of
(C , J) is H′ -maximal, then (C ′ , J ′ ; H′ ) is called a witnessing terminal. We stop growing Taux (C , J ′ ) at (C ′ , J ′ ).
(b) Otherwise we modify the order <′ on C ′ (Definition 3.21) so that
some H′ -maximal periodic block σ(δ) is initial with δ the carrier
base.
We start building T+ (C , J ′ ) rooted at (C ′ , J ′ ). For every path originating from the root we forbid the base δ from being the carrier
base more than B · periodH′ (δ) times in a row, where B denotes the
number of bases in C ′ . Once δ ceases to be the carrier base we forget
about H′ , and go to (2) below.
(2) We continue growing Taux (C , J ′ ) using the following rules:
(a) If the leading base µ in some (C ′′ , J ′ ) does not form a principal
overlapping pair, then continue growing A+ (C ′ , J ′ ) at (C ′′ , J ′ ) by
adding admissible descendants (Definition 6.12), if there are any.
If (C ′′ , J ′ ) has no admissible children and some of its bases are not
in J, then (C ′′ , J ′ ) is halted by inadmissibility.
Otherwise, if the elimination process stops because all the bases of
C ′′ were moved into J ′ , then we take the auxiliary children
 ′′ ′
(Cr , J ; Hr )

of (C ′′ , J ′ ) (which is already in periodic block from, but may not be
normalized), equipped with periodic hierarchies. All these children
are witnessing terminals as in (1a).
(b) If the carrier base base µ in some (C ′′ , J ′ ) is a principal overlapping
carrier we first construct Taux (C ′′ , J ′′ ) rooted at (C ′′ , J ′ ), where
J ′′ = J ′ ∪ σ(µ). This is the recursion.

67

Next we take
W = W (C ′′ , J ′′ , µ) = {(Ci , Ji ; Hi )}
to be the set of all witnessing terminals of Taux (C ′′ , J ′′ ) in which
σ(µ) is an Hi -maximal block overlapping pair (recall Convention
7.28).
If this set is empty then (C ′′ , J ′ ) is declared to be a halted terminal and no further descendants are added. Otherwise the following
number is defined and computable:
period(C ′′ ,J ′ ) (µ) =

max

(Ci ,Ji ;Hi )∈W

periodHi (µ).

(17)

We continue growing A+ (C ′ , J ′ ) at (C ′′ , J ′ ) but we forbid µ from
being the carrier base more than B · period(C ′′ ,J ′ ) (µ) times in a row
in every path originating at (C ′′ , J ′ ). Once µ ceases to be a carrier
base we go back to (2a) or (2b) as appropriate.
Definition 7.31. Let C ′ be a band complex occurring in Taux (C , J) the depth
of C ′ in Taux (C , J) is the number of auxiliary edges in Taux (C , J) connecting
C and C ′ .
Lemma 7.32. The maximal depth of a descendant of C in Taux (C , J) is at
most the relative τ -complexity τ (C , J).
Proof. By Lemma 7.6 all the leaves of TPBF (C , J,) have strictly smaller τ
complexity relative to J ∪ σ(λ). Furthermore, periodic mergers never increase
τ -complexity. Finally if the relative τ complexity τ (C ′ , J ′ ) = 0, then by (2a)
all its children are witnessing terminals.
We think of auxiliary edges as being vertical; thus
Definition 7.33. A subtree of Taux (C , J) sitting inside some A+ (C ′ , J ′ ) or,
equivalently, without auxiliary edges is called horizontal.
Proposition 7.34. Let λ be a principal overlapping pair in a band complex C
occurring in A+ (C ), then Taux (C , σ(λ)) is finite.
Proof. We first to show that for any C ′′ occurring in some horizontal subtree A+ (C ′ , J ′ ) ⊂ Taux (C , σ(λ)) with a principal overlapping carrier µ, the
auxiliary tree Taux (C ′′ , J ′ ∪ σ(µ)) is finite.
We prove this by induction on τ (C ′′ , J ′ ). If τ (C ′′ , J ′ ) = 0 then if it is not
itself yet a witnessing terminal, then its auxiliary children are halted terminals
and the result follows. Otherwise if τ (C ′′ , J ′ ) = 1, by Lemma 7.6, all auxiliary
children must have (J ′ ∪ σ(λ))-relative τ -complexity equal to 0, so they are
witnessing terminals.
Now we suppose that all auxiliary trees are finite for all relative τ complexities less than n, and that τ (C ′′ , J ′ ) = n. Any auxiliary descendant
(C ′′′ , J ′′ ; H′′′ ) will have τ (C ′′′ , J ′′ ) < n by Lemma 7.6. We construct A+ (C ′′′ , J ′′ )
for each auxiliary descendant of (C ′′ , J ′ ) according to rules (2a) and (2b).
Whenever a principal overlapping carrier η occurs in some C (4) , the corresponding auxiliary tree built in (2b) is finite by the induction hypothesis.

68

Either C (4) is a halted terminal or we can compute the finite period(C (4) ,J ′′ ) (µ)
(as given in (17) of step (2b)). By Proposition 6.15, this prevents horizontal
subtrees from having infinite branches; thus by König’s Lemma they are finite. It follows that Taux (C ′′ , J ′ ∪ σ(λ)) is finite. The result now follows by
induction.
Having established that Taux (C , J) is finite, and therefore effectively constructible, we can now define the following computable function.
Definition 7.35. For a band complex C with a principal overlapping pair
(λ, λ) we define
periodC (λ) =
max periodHi (λ)
(Ci ,Ji ,Hi )∈S

where S is the set of witnessing terminals (Ci , Ji , Hi ) of Taux (C , σ(λ)) where,
following the renaming Convention 7.28, σ(λ) is Hi -maximal.
It remains to show that this periodC (λ) gives an upper bound for periodt (λ)
where t is an automorphically minimal κ-track efficiently carried by C . This
will be done by studying the induced tree.

7.5.2

The induced tree Taux (C , t, J ∪ σ(λ))

A triple (C , t, J) will denote a band complex C , an automorphically minimal
κ-track t efficiently carried by C , and a union J of periodic blocks. If C is
in normalized periodic block form, in the 3+1 tuple (C , t, J; H(t)), H(t) will
denote the periodic hierarchy induced by t (Definition 7.21.)
In any (restricted) elimination tree T rooted at (C , J) a track t ⊂ C efficiently carried by C induces a directed path in T. By Corollary 7.7 and by
Definition 7.17 the following makes sense:
Definition 7.36. Let (C , t, J) be a band complex with a principal overlapping
pair (λ, λ) then its induced auxiliary child is given by the labelled graph
(C , J, t)
(C ′ , t′ , J ∪ σ(λ); H(t′ ))
where (C ′ , t, J ∪ σ(λ); H(t′ )) is the auxiliary descendant of (C , J) (Definition
7.30) induced by t ⊂ C .
The algorithm to construct Taux (C , t, J ∪ σ(λ)) is analogous to the algorithm to construct Taux (C , J ∪ σ(λ)) given in Section 7.5.1. The numbering
of the clauses is intended to coincide.
(0) If (λ, λ) is a principal overlapping pair in (C , t, J) then we declare (C , t, J)
to be the root of Taux (C , t, J ∪ σ(λ)). Write J ′ = J ′ ∪ σ(λ).
(1) The Taux (C , t, J ′ )-child of the root (C , t, J) is the induced auxiliary child
of C . These are connected to the root by an auxiliary edge. Further
descendants are added as follows:

69

(a) If some periodic block σ(µ) ⊂ J ′ in an auxiliary descendant (C ′ , t′ , J ′ ; H(t′ ))
of (C , t, J) is H(t′ )-maximal, then ((C ′ , J ′ ; H(t′ )) is called a witnessing terminal. We stop growing Taux (C , t, J ′ ).
(b) Otherwise we change the order < on (C ′ , t′ , J ′ ; H(t′ )) so that some
H(t′ )-maximal periodic block σ(δ) is initial with δ the carrier base.
We start our Rips process, building the path in A+ (C , J ′ ) rooted at
(C ′ , J ′ ) induced by the track t′ ⊂ C ′ . By Corollary 7.26, δ is not
the carrier base more than B · periodH′ (δ) times in a row, where B
denotes the number of bases in C ′ . Once δ ceases to be the carrier
base we go to (2) below.
(2) We continue growing the path induced by t in A+ (C , J ′ ) using the following rules:
(a) If the carrier base µ in some (C ′′ , t′′ , J ′ ) is not a principal overlapping
carrier, then we add its descendant in A+ (C , J ′ ) as usual.
If all the bases C ′′ are moved into J ′ , then we take the induced
auxiliary child

C ′′′ , t′′′ , J ′ ; H(t′′′ )

of (C ′′ , J ′ ) (which is already in periodic block from, but may not be
normalized). Again we call (C ′′′ , t′′′ , J ′ ; H(t′′′ )) a witnessing terminal
as in (1a).
(b) If the carrier base µ in some (C ′′ , t′′ , J ′ ) forms a principal overlapping pair with its dual we first construct the induced auxiliary tree
Taux (C ′′ , t′′ , J ′′ ) rooted at (C ′′ , J ′ ), where J ′′ = J ′ ∪ σ(µ).
Next we take
R = R(C ′′ , t′′ , J ′′ , µ) = {(Ci , ti , Ji ; H(ti ))}
to be the set of all witnessing terminals of Taux (C ′′ , J ′′ ) in which
σ(µ) is an H(ti )-maximal block overlapping pair (recall Convention
7.28).
If this set is empty then (C ′′ , J ′ ) is declared to be a halted terminal and no further descendants are added. Otherwise the following
number is defined and computable (recall Definition 7.27):
period(C ′′ ,t′′ ,J ′ ) (µ) =

max

(Ci ,ti ,Ji ;H(ti ))∈R

periodH(ti ) (µ).

(18)

We now continue growing the path at (C ′′ , t′′ , J ′′ ) in A+ (C ′ , J ′ ) induced by t′ ⊂ C ′ . By Corollary 7.26 and Lemma 7.29, µ will not be
the carrier base more than B · period(C ′′ ,t′′ ,J ′ ) (µ) times in a row.
Once µ ceases to be a carrier base we go back to (2a) or (2b) as
appropriate.
The induced auxiliary tree can be thought of as being constructed one
vertex at a time, see Figure 28, as opposed to a branching process. Another
important distinction is that induced auxiliary trees do not have terminals
that are halted by inadmissibility.
Lemma 7.37. Taux (C , t, J) is finite.

70

(λ, λ) overlapping.
(C , t)

(C1 , t1 , J)
σ(λ) not H(t1 )maximal.

(µ, µ) overlapping.
(C2 , t2 , J)
···
···
µ is carrier base at
most NperiodH(t5 ) (µ)
times.
(δ, δ) overlapping.
(C4 , t4 , J ′ )
···

(C3 , t3 , J ′ )
σ(µ) and σ(λ) not
H(t3 )-maximal.

···

(η, η) overlapping.
(C6 , t6 , J)

(C7 , t7 , J ∪ σ(η))
σ(λ) is H(ty )-maximal.
In C periodt (λ) is at
most periodH(t5 ) (λ).

(C5 , t5 , J ′′ )
σ(µ) is H(t5 )-maximal.
Continue growing at
C2 .

Figure 28: The tree Taux (C , t, σ(λ)), here J = σ(λ), J ′ = σ(λ) ∪
σ(µ), and J ′′ = J ′ ∪ σ(δ). The band complexes are numbered in
order of appearance. Whenever an overlapping pair occurs, an
auxiliary edge is constructed. C4 and C6 are halted terminals. C5
and C7 are witnessing terminals.
Proof. By Lemma 7.32 there is a bound on the number of auxiliary edges in
any path. The finiteness of horizontal paths follows from the definition of a
Rips process, i.e. Size(t) (Definition 4.15) effectively bounds the length of such
paths.
Lemma 7.38. If (λ, λ) is a principal overlapping pair in C then there is
a witnessing terminal (CT , tT , JT ; H(tT )) in Taux (C , t, σ(λ)) in which σ(λ)
(following renaming convention 7.28) is a H(tT )-maximal periodic block such
that
periodt (λ) ≤ periodH(tT ) (λ).
Proof. We first must show that such a witnessing terminal (CT , tT , Jt ; H(tT ))
exists. Suppose towards a contradiction that this was not the case, then the
top level elimination tree in Taux (C , t, σ(λ)) must end in a halted terminal
(C1 , t1 , σ(λ)), otherwise all the bases are moved onto σ(λ), and this periodic
block will be maximal (since it’s unique.)
Let (λ1 , λ1 ) be the overlapping pair in C1 and let J2 = σ(λ) ∪ σ(λ1 ). Let
(C2 , t2 , J2 ) be the auxiliary descendant, as in (1), of C1 . The horizontal path
in Taux (C , t, σ(λ)) starting at (C2 , t2 , J2 ) must end with a halted terminal,
otherwise it ends in a witnessing terminal (CT , tT , J2 ; H(tT )) with either σ(λ)
or σ(λ)1 H(tT )-maximal. This either contradicts the hypothesis that C1 is
a halted terminal or the hypothesis that Taux (C , t, σ(λ)) has no witnessing
terminals with σ(λ) maximal.
Continuing in this fashion we obtain a sequence of halted terminals of

71

increasing depth
(C1 , t1 , J1 ) , (C2 , t2 , J2 ) , . . . , (CF , tF , JF )
where (λ, λ)i is the principal overlapping pair in Ci and Ji+1 = Ji ∪ λi . Since
τ (Ci , Ji ) > τ (Ci+1 , Ji+1 ) this sequence is finite which forces some principal
overlapping pair λj in CF to be H(tF )-maximal, contradicting the fact Cj is a
halted terminal.
It therefore follows that there is a witnessing terminal (CT , tT , Jt ; H(tT ))
in Taux (C , t, σ(λ)) in which σ(λ) is maximal. The desired upper bound on
periodt (λ) now follows immediately from Definition 7.27, Lemma 7.29, and
Corollary 7.26.
So far we have shown that the induced auxiliary tree contains a witnessing
terminal whose combinatorial periodicity bounds the actual periodicity. We
now bound the periodicity, for all tracks.
Proposition 7.39. Let λ be a principal overlapping pair in a band complex C
in A+ (C ), then for all automorphically minimal κ-tracks t efficiently carried
by C the following holds
periodt (λ) ≤ periodC (λ),
where periodC (λ) is the computable function given by Definition 7.35.
Proof. We first show that for any automorphically minimal κ-track t efficiently
carried by C we have a natural containment:
Taux (C , t, σ(λ)) ⊂ Taux (C , σ(λ)) .

(19)

We will show this by analyzing how Taux (C , t, σ(λ)) is constructed by adding
one band complex at a time.
Going through the construction algorithms point-by-point, by Proposition
6.13, the only problem that could arise is in step (2b) of the construction of the
auxiliary trees. It could be that for some (C ′ , t′ , J ′ ) with principal overlapping
pair (µ, µ), (C ′ , t′ , J ′ ) is not a halted terminal and period(C ′ ,t′ ,J ′ ) (µ) from (18)
is greater than period(C ′ ,J ′ ) (µ) from (17).
Note however that in the recursive construction of Taux (C , t, σ(λ)), we
must first construct Taux (C ′ , t′ , J ′ ∪ λ) before adding a “horizontal” child of
(C ′ , t′ , J ′ ). It follows, by the definition and properties of auxiliary children,
that the next vertex added to Taux (C , t, σ(λ)) is still contained in Taux (C , σ(λ)).
Continuing in this manner it is obvious (the reader is, of course, free to
supply their own argument by induction on relative τ -complexity) that the set
R appearing in (18) of Case (2b) in the construction of the induced auxiliary
tree is a subset of W appearing in (17) of Case (2b) of the construction of the
auxiliary tree. We conclude that
period(C ′ ,t′ ,J ′ ) (µ) ≤ period(C ′ ,J ′ ) (µ).
(19) now follows; thus by Lemma 7.38 a witnessing terminal of Taux (C , σ(λ))
bounds periodt (λ) from above.

72

7.6 The proof of Theorem B: a description of the
main algorithm
Suppose we are given a finite 2-complex C such that π1 (C) has no elements of
order 2, a solution to the word problem for π1 (C), an acylindricity constant κ,
and a finite collection

S = {hi }i∈In | n = 1, . . . , m

m
of finite generating sets of subgroups H = hhi ii∈In n=1 .
We start by replacing C by CS given in Section 1.4. This can be done
algorithmically. Using the construction of Section 2.2, we see that for any
track t ⊂ C there is a corresponding band complex that carries it efficiently.
These band complexes can be effectively enumerated; thus it is possible to
construct the finite set {C1 , . . . , CnC } of band complexes given by Proposition
2.14 (See also Section 4.0.1 (1)). This gives the first level of our elimination
tree. We will now define the ultimate elimination tree TP + (C) in this paper.
Here is final inadmissibility criterion:
Definition 7.40. Let C be a band complex. A path
p : Cu → · · · → Cv
in A+ (C ) (recall section 6.5) is called periodicity-inadmissible if
1. p is a µ-periodic path (Definition 6.14) for some base µ in Cu , and
2. the length of p is greater than N · periodCu (µ) (Definition 7.35), where
N is the number of bases in Cu .
TP + (C) is constructed identically to A+ (C), but we also forbid periodicity
inadmissible paths. By Proposition 7.34 we can compute the periodicity bound
and thus effectively decide whether a path is periodicity-inadmissible, so the
resulting tree is finite.
To help the reader, however, we will give here a more explicit construction of
TP + (C) that will summarize the important results of this paper. We start with
our root, the polygonal 2-complex C. We add the descendants C1 , . . . , CnC .
We then build TP + (C) “one generation at a time” as follows:
(1) For every admissible vertex without descendants we add the descendants
as described in Definition 5.23.
(2) If a freshly added descendant is merging inadmissible (Definition 5.21),
we declare it inadmissible and stop adding its descendants.
(3) We now consider every directed path constructed so far in our elimination
tree. If a path Cu → . . . → Cv is either,
•
•
•
•

κ-inadmissible (Definition 4.14),
repetition inadmissible (Definition 4.18),
C-T-inadmissible (Definition 6.11), or
periodicity inadmissible,

73

C
C1 . . . Ci . . . Cn

Cu

Cv

Figure 29: As we build TP + (C) we have a path (drawn thick)
in which Cu and Cv are equal. This path is therefore repetition
inadmissible and Cv has no further descendants.
then we declare the last vertex Cv to be inadmissible and stop adding its
descendants.
We will now argue that tree TP + (C) is finite and can be algorithmically
constructed. First note that at every step we can algorithmically construct the
set of descendants of a band complex (Definition 4.4), in particular TP + (C)
has finite branching. By König’s lemma it is therefore enough to show that
TP + (C) has no directed infinite paths.
Suppose towards a contradiction that this was the case. By Theorem 4.21
any such infinite branch must be either thinning, quadratic or superquadratic.
In the thinning and quadratic cases, such a branch must either have a κinadmissible subpath or must contain a repetition (see Section 4.8.) In the
superquadratic case any infinite branch must either have a tail with infinitely
many C-T cycles or the tail must be µ-periodic for some base µ (see the proof
of Proposition 6.15.) In both of these cases such a tail will have either a C-Tinadmissible or a periodicity inadmissible initial segment. It therefore follows
that TP + (C) has no infinite branches, furthermore the four inadmissibility
criteria are algorithmically verifiable; thus TP + (C) ⊂ T(C) is algorithmically
constructible.
The leaves of TP + (C) give a subset of all possible tracks of C (recall Section
4.1.) We will now show that this subset contains a representative of every
automorphically minimal κ-track.
Suppose that there was some automorphically minimal κ-track t ⊂ C that
induced a path p : C → C1 → . . . → Cl in T(C) with Cl terminal, which
isn’t contained in TP + (C). Then, by definition of TP + (C), p must either
contain a κ-inadmissible, a repetition inadmissible, a C-T-inadmissible, or a
periodicity inadmissible subpath. Propositions 4.13, 4.17, Corollary 6.10 and
Proposition 7.39 cover each of these cases and contradict the assumption that
t is an automorphically minimal κ-track. It follows that the admissible leaves

74

of TP + (C) give a set of tracks

t1 , . . . , tn(C,κ,S)

in C that satisfy the requirements of Theorem B.

References
[Aea91]

J. M. Alonso and et al. Notes on word hyperbolic groups. In Group
theory from a geometrical viewpoint (Trieste, 1990), pages 3–63.
World Sci. Publ., River Edge, NJ, 1991. Edited by H. Short.

[AHT06]

Ian Agol, Joel Hass, and William Thurston. The computational
complexity of knot genus and spanning area. Trans. Amer. Math.
Soc., 358(9):3821–3850 (electronic), 2006.

[BCRS91] Gilbert Baumslag, Frank B. Cannonito, Derek J. Robinson, and
Dan Segal. The algorithmic theory of polycyclic-by-finite groups.
J. Algebra, 142(1):118–149, 1991.
[BF95]

Mladen Bestvina and Mark Feighn. Stable actions of groups on real
trees. Invent. Math., 121(2):287–321, 1995.

[Bow98]

Brian H Bowditch. Cut points and canonical splittings of hyperbolic
groups. Acta mathematica, 180(2):145–186, 1998.

[Bow01]

B. H. Bowditch. Peripheral splittings of groups. Trans. Amer.
Math. Soc., 353(10):4057–4082 (electronic), 2001.

[Bum04]

Inna Bumagin. The conjugacy problem for relatively hyperbolic
groups. Algebr. Geom. Topol., 4:1013–1040, 2004.

[CRK11]

Montserrat Casals-Ruiz and Ilya V. Kazachkov. On systems of
equations over free products of groups. J. Algebra, 333:368–426,
2011.

[Del99]

Thomas Delzant. Sur l’accessibilité acylindrique des groupes de
présentation finie. Annales de l’institut Fourier, 49(4):1215–1224,
1999.

[DF05]

Guo-An Diao and Mark Feighn. The Grushko decomposition of a
finite graph of finite rank free groups: an algorithm. Geom. Topol.,
9:1835–1880 (electronic), 2005.

[DG08a]

François Dahmani and Daniel Groves.
Detecting free splittings in relatively hyperbolic groups. Trans. Amer. Math. Soc.,
360(12):6303–6318, 2008.

[DG08b]

François Dahmani and Daniel Groves. The isomorphism problem
for toral relatively hyperbolic groups. Publ. Math. Inst. Hautes
Études Sci., (107):211–290, 2008.

[DG10]

François Dahmani and Vincent Guirardel. Foliations for solving
equations in groups: free, virtually free, and hyperbolic groups. J.
Topol., 3(2):343–404, 2010.

75

[DG13]

François Dahmani and Vincent Guirardel. Presenting parabolic
subgroups. Algebr. Geom. Topol., 13(6):3203–3222, 2013.

[DS99]

M. J. Dunwoody and M. E. Sageev. JSJ-splittings for finitely presented groups over slender groups. Invent. Math., 135(1):25–44,
1999.

[Far98]

B. Farb. Relatively hyperbolic groups.
8(5):810–840, 1998.

[GL09]

Vincent Guirardel and Gilbert Levitt. Jsj decompositions: definitions, existence, uniqueness. i: The jsj deformation space. arXiv
preprint arXiv:0911.3173, 2009.

[GL11]

Vincent Guirardel and Gilbert Levitt. Trees of cylinders and canonical splittings. Geom. Topol., 15(2):977–1012, 2011.

[GW09]

Daniel Groves and Henry Wilton. Enumerating limit groups.
Groups Geom. Dyn., 3(3):389–399, 2009.

[Hem76]

John Hempel. 3-Manifolds. Princeton University Press, Princeton,
N. J., 1976. Ann. of Math. Studies, No. 86.

[Hru10]

G. Christopher Hruska. Relative hyperbolicity and relative quasiconvexity for countable groups. Algebr. Geom. Topol., 10(3):1807–
1856, 2010.

[KM98]

O. Kharlampovich and A. Myasnikov. Irreducible affine varieties
over a free group. II. Systems in triangular quasi-quadratic form
and description of residually free groups. J. Algebra, 200(2):517–
570, 1998.

[KM05]

Olga Kharlampovich and Alexei G. Myasnikov. Effective JSJ decompositions. In Groups, languages, algorithms, volume 378 of
Contemp. Math., pages 87–212. Amer. Math. Soc., Providence, RI,
2005.

[Mak82]

G. S. Makanin. Equations in a free group. Izv. Akad. Nauk SSSR
Ser. Mat., 46(6):1199–1273, 1344, 1982.

[Osi06]

Denis V. Osin. Relatively hyperbolic groups: intrinsic geometry,
algebraic properties, and algorithmic problems. Mem. Amer. Math.
Soc., 179(843):vi+100, 2006.

[Raz87]

A Razborov. On systems of equations in a free group. PhD thesis,
Steklov Math. Institute, Moscow, 1987.

[Rom79]

V. A. Roman′ kov. Universal theory of nilpotent groups. Mat. Zametki, 25(4):487–495, 635, 1979.

[Sel97]

Z. Sela. Acylindrical accessibility for groups.
129(3):527–565, 1997.

[Ser03]

Jean-Pierre Serre. Trees. Springer Monographs in Mathematics.
Springer-Verlag, Berlin, 2003. Translated from the French original by John Stillwell, Corrected 2nd printing of the 1980 English
translation.

76

Geom. Funct. Anal.,

Invent. Math.,

[SW79]

Peter Scott and Terry Wall. Topological methods in group theory.
In Homological group theory (Proc. Sympos., Durham, 1977), volume 36 of London Math. Soc. Lecture Note Ser., pages 137–203.
Cambridge Univ. Press, Cambridge, 1979.

[Tou14]

Nicholas W. M. Touikan. Bulitko’s lemma for acylindrical splittings.
J. Algebra, 406:251–271, 2014.

[Wei02]

Richard Weidmann. The Nielsen method for groups acting on trees.
Proc. London Math. Soc. (3), 85(1):93–118, 2002.

77

