arXiv:1411.6302v4 [math.GR] 6 Jun 2017

Algorithmic constructions of relative train track
maps and CTs
Mark Feighn∗

Michael Handel†

June 7, 2017

Abstract
Building on [BH92, BFH00], we proved in [FH11] that every element ψ of
the outer automorphism group of a finite rank free group is represented by a
particularly useful relative train track map. In the case that ψ is rotationless
(every outer automorphism has a rotationless power), we showed that there is
a type of relative train track map, called a CT, satisfying additional properties.
The main result of this paper is that the constructions of these relative train
tracks can be made algorithmic. A key step in our argument is proving that it
is algorithmic to check if an inclusion F @ F 0 of φ-invariant free factor systems
is reduced. We also give applications of the main result.

Contents
1 Introduction

2

2 Relative train track maps in the general case
2.1 Some standard notation and definitions . . . . . . . . . . . . . . . . .
2.2 Algorithmic proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5
6
9

3 Rotationless iterates
3.1 More on markings . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Principal automorphisms and principal points . . . . . . . .
3.3 A sufficient condition to be rotationless and a uniform bound
3.4 Algorithmic Proof of Theorem 2.12 . . . . . . . . . . . . . .
∗

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

13
13
14
16
20

This material is based upon work supported by the National Science Foundation under Grant
No. DMS-1406167 and also under Grant No. DMS-14401040 while the author was in residence at
the Mathematical Sciences Research Institute in Berkeley, California, during the Fall 2016 semester.
†
This material is based upon work supported by the National Science Foundation under Grant
No. DMS-1308710 and by PSC-CUNY grants in Program Years 46 and 47.

1

4 Reducibility
4.1 The EG case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 The NEG case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20
21
30

5 Definition of a CT

31

6 Sliding NEG edges
6.1 Completely Split Rays . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Finding a Fixed Point . . . . . . . . . . . . . . . . . . . . . . . . . .

34
34
37

7 Upward induction and extension

40

8 Proof of Theorem 7.5
8.1 The one-edge extension case . . . . . . . . . . . . . . . . . . . . . . .
8.2 The multi-edge extension case . . . . . . . . . . . . . . . . . . . . . .

42
42
44

9 Finding Fix(Φ)
9.1 The periodic case . . . . . .
9.2 A G-graph of Nielsen paths
9.3 Fix(Φ) for rotationless φ . .
9.4 The general case . . . . . .

52
52
53
56
57

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

10 S(f ) and Fix(φ)

57

11 Possibilites for [Fix(Φ)]

58

12 A Stallings graph for FixN (∂Φ)
12.1 Definition of SN (f ) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12.2 Properties of SN (f ) . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60
60
62

13 Moving up through the filtration

63

14 Primitively atoroidal outer automorphisms

64

15 The index of an outer automorphism

66

16 Appendix: Hyperbolic and atoroidal automorphisms

74

1

Introduction

An automorphism Φ of the rank n free group Fn is typically represented by giving its
effect on a basis of Fn . Equivalently, if we identify the edges of the rose Rn (the graph
with one vertex ∗ and n edges) with basis elements of Fn , then Φ may be represented

2

as a self homotopy equivalence of Rn preserving ∗. In this paper, we are interested in
outer automorphisms, that is we are interested in elements of the quotient
Out(Fn ) := Aut(Fn )/Inn(Fn )
of the automorphism group Aut(Fn ) of Fn by its subgroup Inn(Fn ) of inner automorphisms. Since outer automorphisms are defined only up to conjugation, the base
point loses its special role and φ ∈ Out(Fn ) is typically represented as a self homotopy
equivalence of Rn that is not required to fix ∗. More generally it is also typical to
take advantage of the flexibility gained by representing φ as a self homotopy equivalence f : G → G of a marked graph G, i.e. a graph G equipped with a homotopy
equivalence µ : Rn → G. The marking identifies the fundamental group of G with
Fn , but only up to conjugation. In an analogy with linear maps, representing φ as
f : G → G corresponds to writing a linear map in terms of a particular basis.
In [BH92], Bestvina-Handel showed that every element of Out(Fn ) has a representation as a relative train track map, that is a representation f : G → G as above but
with strong properties. In the analogy with linear maps, a relative train track map
corresponds to a normal form. [BH92] goes on to use relative train track maps to
solve the Scott conjecture: the rank of the fixed subgroup of an element of Aut(Fn )
is at most n. Further applications spurred the further development of the theory of
relative train tracks. See for example, [BFH00] where improved relative train tracks
(IRTs) were used to show that Out(Fn ) satisfies the Tits alternative or [FH09] where
completely split relative train tracks (CTs) [FH11] were used to classify abelian subgroups of Out(Fn ).
CTs are relative train tracks that were designed to satisfy the properties that
have proven most useful (to us) for investigating elements of Out(Fn ). By convention,
the identity map on the rose with one petal is a CT representing the trivial element
of Out(F1 ). For the definition when n ≥ 2, see Section 5. Not every φ ∈ Out(Fn )
is represented by a CT, but all rotationless (see Definition 3.3) elements are. This
is not a big restriction since there is a specific M > 0 depending only on n (see
Corollary 3.14) such that φM is rotationless. We believe that CTs will be of general use
in approaching algorithmic questions about Out(Fn ). As a first step in that process,
our main theorem (Theorem 1.1) verifes that CTs can be constructed algorithmically.
Many arguments involving CTs go by induction up through the strata. It is
therefore useful if a CT f : G → G satisfies:
(Inheritance) The restriction of f to each component of each core filtration element
is a CT.
As Example 5.6 shows, not every CT satisfies (Inheritance). By using an upward
induction argument (see Section 7) instead of the downward induction arguments
used in previous relative train track constructions, we prove that CTs satisfying (Inheritance) can be constructed algorithmically.
3

Theorem 1.1. There is an algorithm whose input is a rotationless φ ∈ Out(Fn )
and whose output is a CT f : G → G that represents φ and satisfies (Inheritance).
Moreover, for any nested sequence C of φ-invariant free factor systems, one can choose
f : G → G so that each non-empty element of C is realized by a core filtration element.
A CT f : G → G representing rotationless φ ∈ Out(Fn ) is a graphical representation of φ, and may be used to find graphical representations of some important
invariants of φ. For example, there is an algorithm to compute a finite core graph
S(f ) immersing to G such that a closed path in G represents a fixed φ-conjugacy class
iff and only if it lifts to a closed path in S(f ). There is also a graph SN (f ) immersing
to G, obtained from S(f ) by attaching finitely many rays, that additionally records
fixed points at infinity (see Sections 10 and 12). Arbitrarily large neighborhoods of
S(f ) in SN (f ) may be computed algorithmically.
The proof of Theorem 1.1 is in Sections 7 and 8. It relies heavily on our paper
[FH11] and, more specifically, on the proof of Theorem 4.28 of [FH11] which states
that every rotationless outer automorphism of Fn is represented by a CT. We strongly
recommend that the reader have a copy of [FH11] handy while reading the current
one. We will also rely on [FH11] for complete references. Much of the proof of
[FH11, Theorem 4.28] is already algorithmic and the main work in the current paper
is to make algorithmic the parts of that proof that are not explicitly algorithmic. In
fact, there are only three places in the proof of Theorem 4.28 where non-algorithmic
arguments are given. The first has to do with relative train track maps for general
elements of Out(Fn ) [BH92]. In this case there is an underlying algorithm to the
arguments and we make it explicit in Sections 2 and 3.
The second part of the proof to be made algorithmic involves checking whether the
filtration by invariant free factor systems induced by the given filtration by invariant
subgraphs is reduced. (See Section 2.1 for a review of the relevant definitions.) This
requires new arguments and is carried out in Section 4. The main result of Section 4
is captured in Corollary 1.2 below, which we believe to be of independent interest.
Although we present this result as a corollary of Theorem 1.1, a stand-alone proof
could be given using the methods in Section 4; see in particular Proposition 4.9.
These methods are in turn key ingredients in the proof of the Theorem 1.1.
Recall that if ψ ∈ Out(Fn ) and F1 @ F2 are ψ-invariant free factor systems then
ψ is said to be fully irreducible relative to F1 @ F2 if for all k ≥ 1 there are no ψ k invariant free factor systems properly contained between F1 and F2 . Equivalently,
if φ is a rotationless iterate of ψ then there are no φ-invariant free factor systems
properly contained between F1 and F2 ; see [FH11, Lemma 3.30].
Corollary 1.2. There is an algorithm with input ψ ∈ Out(Fn ) and ψ-invariant free
factor systems F1 @ F2 and output YES or NO depending on whether or not ψ is
fully irreducible relative to F1 @ F2 . In the case that ψ is not fully irreducible, k ≥ 1
and a ψ k -invariant free factor system that is properly contained between F1 and F2
are found.
4

Proof. Construct a CT f : G → G with filtration ∅ = G0 ⊂ G1 ⊂ . . . ⊂ GN = G for
a rotationless φ = ψ M with M as in Corollary 3.14 in which F1 @ F2 are realized by
core subgraphs Gr ⊂ Gt . Then, by defining property (Filtration) of a CT, ψ is fully
irreducible relative to F1 @ F2 if there are no core subgraphs Gs properly contained
between Gr and Gt . If there is such a subgraph then its associated free factor system
is properly contained between F1 and F2 .
Remark 1.3. In the special case that F1 = ∅, Corollary 1.2 is an algorithm for
checking if ψ is fully irreducible. Our algorithm in this special case is different from
the ones given in [Kap14] and [CMP15]. More recently, Kapovich [Kap] has produced
a polynomial time algorithm to detect full irreducibility.
The third and final non-algorithmic part of the proof of [FH11, Theorem 4.28]
requires a new fixed point result (Lemma 6.4) allowing us to properly attach the
terminal endpoints of NEG edges; this takes place in Section 6.
We include some sample applications of Theorem 1.1 – most already known.
• In Proposition 9.10, we give another proof of the result of Bogopolski and
Maslakova [BM16] that it is algorithmic to compute Fix(Φ) for Φ ∈ Aut(Fn ).
• An outer automorphism φ is primitively atoroidal if it does not act periodically
on the conjugacy class of a primitive element of Fn , i.e. an element of some basis.
In Corollary 14.4 we give an algorithm to decide if φ is primitively atoroidal.
• In Section 15 we prove that the well-known index invariant i(φ) of [GJLL98]
can be computed algorithmically and introduce a similar invariant j(φ) ≥ i(φ)
that can also be computed algorithmically. In Proposition 15.14 we show that
j(φ) ≤ n − 1 and so the key inequality satisfied by i(φ) is still satisfied by j(φ).
• In Corollary 16.4 we reprove a result of Ilya Kapovich [Kap00] that it is algorithmic to tell if a given φ ∈ Out(Fn ) is hyperbolic. The Kapovich result is
stronger in that φ is only assumed to be an injective endomorphism.
We thank the referee for suggesting applications to be added to this paper, specifically: algorithmically computing the index (Proposition 15.2); algorithmically deciding if an automorphism is primitively atoroidal (Corollary 14.4); and algorithmically
finding the possibilities for [Fix(Φ)] for a Φ representing a rotationless outer automorphism (Corollary 11.1).

2

Relative train track maps in the general case

In this section we revisit three existence theorems for relative train track maps representing arbitrary φ ∈ Out(Fn ), rotationless or not. The original statements of these
results did not mention algorithms and the original proofs did not emphasize their
5

algorithmic natures. In this section we give the algorithmic versions of two of these
results; see Theorem 2.2 and Lemma 2.10. The third existence result that we revisit
is [FH11, Theorem 2.19] which in the current paper is reproduced as Theorem 2.12.
We will need the algorithmic version of Theorem 2.12 and its proof is postponed until
Section 3.4 because the proof depends on consequences of Theorem 2.12 established
in Section 3.
Rather than cut and paste arguments from [BH92], [BFH00] and [FH11] into this
paper, we will point the reader to specific sections in those papers and explain how
they fit together to give the desired results. In some cases, we refer to arguments that
occur in lemmas whose hypotheses are not satisfied in our current context. Nonetheless the arguments that we refer to will apply.

2.1

Some standard notation and definitions

In this section we recall the basic definitions of relative train track theory, assuming
that the reader has some familiarity with this material. Complete details can be
found in any of [BH92, Sections 1 and 5], [BFH00, Sections 2 and 3], [FH11, Section
2] and Part I of [HM].
Identify Fn with π1 (Rn , ∗) where the rose Rn is the graph with one vertex ∗
and n edges. A (not necessarily connected) graph is core if it is the union of its
immersed circuits. A marked graph is a finite core graph G equipped with a homotopy
equivalence µ : Rn → G called the marking by which we identify Out(π1 (G)) with
Out(π1 (Rn )) and hence with Out(Fn ). In this way, a homotopy equivalence f : G → G
determines an element φ ∈ Out(Fn ); we say that f : G → G represents φ or that
f : G → G is a topological representative of φ. Conversely, each φ ∈ Out(Fn ) is
represented (non-uniquely) by a homotopy equivalence of any marked graph G, cf.
Lemma 7.2.
Convention 2.1. Unless otherwise stated, we assume that f is an immersion when
restricted to edges and that if J is an interval in the interior of an edge then some
f -iterate of J either contains a vertex or is contained in a periodic edge. This can be
arranged for example by assigning each edge length one and making the restriction of
f to each edge linear.
A (finite, infinite or bi-infinite) path in G is an immersion σ : J → G defined
on an interval J such that the image of each end of J crosses infinitely many edges
of G; equivalently, σ lifts to a proper map into the universal cover G̃. We allow
the possibility that J is a single point in which case we say that the path is trivial.
Subdividing at the full pre-image of the set V of vertices of G, we view J as a simplicial
complex and σ as a map whose restriction to an edge is one-to-one with image an
edge or partial edge. In this way we view σ as an edge path; i.e. a concatenation of
edges of G, where we allow the first and last to be partial edges if the endpoints are
not at vertices. We do not distinguish between paths that have the same associated
6

edge path and we often identify a path with its associated edge path and write σ ⊂ G.
A path has height r if it is contained in Gr but not Gr−1 .
A bi-infinite path σ is called a line. Each lift σ̃ ⊂ G̃ of a line σ ⊂ G has well
defined endpoints in the set ∂G of ends of G. A singly infinite path is called a ray.
Each lift of a ray has one endpoint in G̃ and one ideal endpoint in ∂ G̃. Conversely,
each ordered pair of distinct points in ∂ G̃ is the endpoint set of a unique line in G̃.
For any marked graph G, one can identify ∂G with ∂Fn ; see Section 3. In this way
lines in G are identified with Fn -orbits of ordered pairs (P, Q) of distinct points in
∂Fn . We sometimes refer to (P, Q) as an abstract line or even just a line. Thus each
line in G determines an Fn -orbit of abstract lines. Each lift f˜ : G̃ → G̃ extends to a
homeomorphism (also called f˜) of the set ∂G of the ends of G̃.
We denote the conjugacy class of a subgroup A of Fn by [A]. If A1 ∗ . . . ∗ Am is a
free factor of Fn and each Ai is non-trivial then {[A1 ], . . . , [Am ]} is a free factor system
and each [Ai ] is a component of that free factor system. We also allow the trivial free
factor system ∅. For any marked graph G and subgraph C with non-contractible
components C1 , . . . , Cm , the fundamental group of each Ci determines a well defined
conjugacy class that we denote [Ci ] and [C] := {[C1 ], . . . , [Cm ]} is a free factor system.
We say that C ⊂ G realizes [C]. Every free factor system is realized by some subgraph
of some marked graph. There is a partial order @ on free factor systems defined by
{[A1 ], . . . , [Ak ]} @ {[B1 ], . . . , [Bl ]} if each Ai is conjugate to a subgroup of some Bj .
There is a natural action of φ ∈ Out(Fn ) on conjugacy classes of free factors. If each
element of a free factor system F is φ-invariant then we say that F is φ-invariant.
More generally, a subgroup system is a finite collection {[A1 ], . . . , [Ak ]} of distinct
conjugacy classes of finitely generated non-trivial subgroups of Fn . The conjugacy
class [c] of c ∈ Fn is carried by the subgroup system {[A1 ], . . . , [Ak ]} if c is conjugate to
an element of some Ai . Equivalently, the fixed points for the action of a conjugate of c
on ∂Fn are contained in some ∂Ai . More generally if P, Q ∈ ∂Ai then the Fn -orbit of
the abstract line with endpoints P and Q is carried by {[A1 ], . . . , [Ak ]}. If a subgraph
C of a marked graph G realizes a free factor system F then a conjugacy class is carried
by F if and only if the circuit representing it in G is contained in C; similarly, the
Fn -orbit of an abstract line is carried by F if and only if the corresponding line in G is
contained in C. By [BFH00, Lemma 2.6.5] (see also Lemma 4.2), for each collection of
conjugacy classes of elements and Fn -orbits of abstract lines there is a unique minimal
(with respect to the above partial order @) free factor system that carries them all.
If that minimal free factor system is {[Fn ]} then we say that the collection fills. In
this context, we will treat a subgroup as the collection of conjugacy classes that it
carries. In particular, it makes sense to talk about a subgroup system filling.
A filtration of a marked graph G is an increasing sequence of subgraphs ∅ =
G0 ⊂ G1 ⊂ . . . ⊂ GN = G. The rth stratum Hr is the subgraph whose edges are
contained in Gr but not Gr−1 . A homotopy equivalence f : G → G preserves the
filtration if f (Gr ) ⊂ Gr for each Gr . Assuming this to be the case and that the edges
in Hr have been ordered, the transition matrix Mr associated to Hr is the square
7

matrix with one row and column for each edge of Hr and whose ij th coordinate is the
number of times that the f -image of the ith edge of Hr crosses (in either direction)
the j th edge of Hr . After enlarging the filtration if necessary, we may assume that
each Mr is either the zero matrix or irreducible; we say that Hr is a zero stratum or
an irreducible stratum respectively. In the irreducible case, each Mi has a PerronFrobenius eigenvalue λr ≥ 1. The stratum Hr is EG if λr > 1 and is NEG if λr = 1. If
f : G → G is a topological representative of φ then we sometimes say that f : G → G
and ∅ = G0 ⊂ G1 ⊂ . . . ⊂ GN = G represent φ.
If σ ⊂ G is a path and f : G → G is a homotopy equivalence then f (σ) := f ◦ σ :
J → G need not be immersed and so need not be a path. If σ is a finite path, we
define f# (σ) to be the unique path that is homotopic to f (σ) rel endpoints. For rays
and lines, one defines f# (σ) by choosing a lift σ̃, defining f˜# (σ̃) to be the unique
path that is homotopic to f˜(σ̃) rel endpoints (including ideal endpoints) and then
projecting f˜# (σ̃) to a path f# (σ) ⊂ G.
If paths σ1 and σ2 can be concatenated then we denote the concatenation by
σ1 σ2 . A decomposition σ = . . . σ1 σ2 . . . σm . . . of a path into subpaths is a splitting
if f#k (σ) = . . . f#k (σ1 )f#k (σ2 ) . . . f#k (σm ) . . . for all k ≥ 1; in this case we usually write
σ = . . . · σ1 · σ2 · . . . · σm · . . ..
If f#k (σ) = σ for some k ≥ 1 and finite path σ then σ is a periodic Nielsen path.
If k = 1 then σ is a Nielsen path. If a (periodic) Nielsen path σ can not be written
as the concatenation of non-trivial (periodic) Nielsen subpaths then it is indivisible.
Two points in Fix(f ) are in the same Nielsen class if they bound a Nielsen path.
An edge E in a (necessarily NEG) stratum Hi is linear if f (E) = Eu where
u ⊂ Gi−1 is a non-trivial Nielsen path. If u = wd for some root-free w and some d 6= 0
then the unoriented conjugacy class of w is called the axis for E. All other edges in
NEG strata are non-linear.
A direction at a point x ∈ G is a germ of non-trivial finite paths with initial
vertex x. If x is not a vertex then there are two directions at x. Otherwise there is
one direction for each oriented edge based at x and we identify the direction with the
oriented edge. A homotopy equivalence f : G → G induces a map Df from directions
at x to directions at f (x). A turn at x is an unordered pair (d1 , d2 ) of directions based
at x; it is degenerate if d1 = d2 and non-degenerate otherwise. Df induces a map on
turns that we also denote by Df . A turn is illegal if its image under some iterate
of Df is degenerate and is legal otherwise. If σ = . . . Ei Ei+1 . . . and if each turn
(Ēi , Ei+1 ) is legal then σ is legal. Here Ēi denotes Ei with the opposite orientation.
We sometimes also use the exponent -1 to indicate the inverse of a path. If σ has
height r then σ is r-legal if each turn (Ēi , Ei+1 ) for which both Ei and Ei+1 are edges
in Hr is legal.
The homotopy equivalence f : G → G is a relative train track map [BH92, page
38] if it maps vertices to vertices and if the following conditions hold for every EG
stratum Hr .
(RTT-i) Df maps directions in Hr to directions in Hr .
8

(RTT-ii) If σ ⊂ Gr−1 is a non-trivial path with endpoints in Hr ∩ Gr−1 then f# (σ)
is a non-trivial path with endpoints in Hr ∩ Gr−1 .
(RTT-iii) If σ ⊂ Hr is legal then f (σ) is an r-legal path.

2.2

Algorithmic proofs

The following theorem is modeled on [BH92, Theorem 5.12] which proves the existence
of relative train track maps that satisfy an additional condition called stability. This
condition is algorithmically built into CTs at a later stage of the argument (see [FH11,
Step 1( EG Nielsen Paths) in Section 4.5]) so we do not need it here. See also [DV96].
The proof of [BH92, Theorem 5.12] is mostly algorithmic. We have added Lemmas 2.4
and 2.7 to make the entire argument algorithmic.
Theorem 2.2. There is an algorithm that produces for each φ ∈ Out(Fn ) a relative
train track map f : G → G representing φ.
The proof of Theorem 2.2 appears at the end of this section after we recall some
definitions and results from [BH92].
Definition 2.3. Suppose that f : G → G and ∅ = G0 ⊂ G1 ⊂ . . . ⊂ GN = G are a
topological representative and filtration representing φ. For each EG stratum Hr , let
λr ≥ 1 be the Perron-Frobenious eigenvalue of the transition matrix Mr associated
to Hr . Let Λ(f ) be the set of (not necessarily distinct) λr ’s associated to EG strata
Hr of f : G → G, listed in non-increasing order. Say that f : G → G is bounded
if there are at most 3n − 3 exponentially growing strata Hr and if each λr is the
Perron-Frobenious eigenvalue of some irreducible matrix with at most 3n − 3 rows
and columns. Note that if each vertex of G has valence at least 3 then f : G → G is
bounded because G has at most 3n − 3 edges. Note also that if the set of all possible
Λ(f )’s is ordered lexicographically, then any strictly decreasing sequence of Λ(f )’s
associated to bounded f ’s is finite; see [BH92, page 37].
Lemma 2.4. There is an algorithm that checks if a given bounded topological representative f : G → G of φ is a relative train track map.
Proof. Property (RTT-i) is obviously a finite property. We may therefore assume that
each EG stratum satisfies (RTT-i). Suppose that Hj is an EG stratum and that C is
a component of Gj−1 . If C is contractible then it contains only finitely many paths
with endpoints at vertices so checking (RTT-ii) for paths in C is a finite process. If
C is not contractible then there is a smallest p ≥ 1 such that f p (C) ⊂ C. Since Hj
satisfies (RTT-i), f p (Hj ∩ C) ⊂ Hj ∩ C. If f p induces a bijection of Hj ∩ C then
(RTT-ii) is satisfied for all σ ⊂ C. Otherwise, there exist distinct v, w ∈ Hj ∩ C and
a smallest 1 ≤ q ≤ p such that f q (v) = f q (w). After replacing v and w by f q−1 (v)
and f q−1 (w), we may assume that q = 1. In this case v and w are connected by a
unique path σ ⊂ C whose f# -image is trivial and (RTT-ii) fails. We have now proved
9

that (RTT-ii) is a finite property. Finally, (RTT-iii) is equivalent to the statement
that f (E) is j-legal for each edge E ⊂ Hj and so is a finite property.
Definition 2.5. [BH92, paragraph before Lemma 5.13] Suppose that f : G → G is
a topological representative and that E is an edge in an EG stratum Hr . The core
of E is defined to be the smallest closed subinterval of E such that each point in the
complement of the core is eventually mapped into Gr−1 . The set of endpoints of the
cores of all the edges in Hj is mapped into itself by f . Subdivision at this finite set
(and enlarging the original filtration to accommodate the new edges formed by the
complements of the core) is called the core subdivision of Hr .
Lemma 2.6. [BH92, Lemma 5.13] Suppose that f : G → G is a bounded topological
representative of φ and that f 0 : G0 → G0 is obtained from f : G → G by a core
subdivision of the EG stratum Hr . Then:
(1) Λ(f ) = Λ(f 0 )
(2) There is a bijection Hj ↔ Hj0 0 between the EG strata of f and the EG strata of
f 0 such that:
(a) Hj0 0 satisfies (RTT-i).
(b) relative height is preserved; i.e. j < k if and only if j 0 < k 0
(c) If j 6= r and Hj satisfies (RTT-i) or (RTT-ii) then Hj0 0 satisfies (RTT-i)
or (RTT-ii), respectively.
Lemma 2.7. Core subdivision is algorithmic.
Proof. Suppose that f : G → G is a topological representative and that E is an edge
in an EG stratum Hr . If the Df orbit of E (thought of as the initial direction of E)
is contained in Hr then the core of E contains an initial segment of E and E does not
contribute to the set of core subdivision points. Suppose then that some iterate of
Df maps E into Gr−1 . Define Dr f (E) to be the first Hr -edge in the edge path f (E).
If E is Dr f -periodic of minimal period p, let Ei = Dr f i (E) for i = 0, . . . , p − 1. Thus
f (Ei ) = ui Ei+1 vi where ui is a possibly trivial path in Gr−1 and indices are taken
mod p. Consider the subintervals of Ei whose images under f p are single edges. The
first such subinterval ei that is mapped into Hr satisfies f p (ei ) = Ei and we choose
the core subdivision point corresponding to Ei to be the unique point in ei that is
fixed by f p . If E is not Dr f -periodic then choose the minimal q such that Dr f q (E)
is Dr f -periodic and take the core subdivision point for E to be the first point in E
that is mapped to the core subdivision point of Dr f q (E).
Lemma 2.8. Given a bounded topological representative f : G → G of φ with an EG
stratum that satisfies (RTT-i) but not (RTT-iii) there is an algorithm to construct a
bounded topological representative f 00 : G00 → G00 of φ such that Λ(f 00 ) < Λ(f ).

10

Proof. The proof of [BH92, Lemma 5.9] contains an algorithm that modifies f : G →
G to produce a not necessarily bounded, topological representative f 0 : G0 → G0 such
that Λ(f 0 ) < Λ(f ). The proof of [BH92, Lemma 5.5] contains an algorithm that
modifies f 0 : G0 → G0 to produce a bounded topological representative f 00 : G00 → G00
of φ such that Λ(f 00 ) ≤ Λ(f 0 ) < Λ(f ).
We next recall [BH92, Lemma 5.14], making the algorithm used in its proof part
of the statement of the lemma.
Lemma 2.9. [BH92, Lemma 5.14] Suppose that f : G → G is a bounded topological
representative of φ and that Hs is an EG stratum that does not satisfy (RTT-ii). Then
there is an algorithm to construct a bounded topological representative f 0 : G0 → G0
of φ such that
(1) Λ(f ) = Λ(f 0 )
(2) There is a bijection Hj ↔ Hj0 0 between the EG strata of f and the EG strata of
f 0 such that:
(a) relative height is preserved; i.e. j < k if and only if j 0 < k 0 .
(b) |Hs0 0 ∩ G0s0 −1 | < |Hs ∩ Gs−1 |
(c) if k > s and Hk satisfies (RTT-i) and (RTT-ii) then Hk0 0 satisfies (RTT-i)
and (RTT-ii).
(d) if k ≥ s and Hk satisfies (RTT-i) then Hk0 0 (RTT-i).
Proof of Theorem 2.2: Start with any bounded topological representative f : G →
G of φ. For example, one can choose any homotopy equivalence of the rose that
represents φ. If there are no EG strata then f : G → G is a relative train track map
and we are done. Otherwise, apply Lemma 2.6 to produce a bounded topological
representative (still called f : G → G) of φ whose top EG stratum satisfies (RTT-i).
If the top EG stratum does not also satisfy (RTT-ii), apply Lemma 2.9 to produce a
new bounded topological representative (still called f : G → G) of φ whose top EG
stratum still satisfies (RTT-i). If the top EG stratum of the current f : G → G does
not satisfy (RTT-ii) apply Lemma 2.9 again. Item (b) of that lemma guarantees that
after finitely many applications of Lemma 2.9, we arrive at f : G → G whose top EG
stratum satisfies (RTT-i) and (RTT-ii).
Repeat this procedure on the second highest EG stratum to produce a bounded
topological representative of φ whose top two EG stratum satisfies (RTT-i) and (RTTii). After finitely many iterations, we have a bounded topological representative (still
called f : G → G) of φ, all of whose EG strata satisfy (RTT-i) and (RTT-ii).
Apply Lemma 2.4 to check if f : G → G is a relative train track map. If yes, we are
done. Otherwise apply Lemma 2.8 to produce a bounded topological representative
f 0 : G0 → G0 of φ with Λ(f 0 ) < Λ(f ). Then start over again with f 0 : G0 → G0
11

replacing the original f : G → G. Since every decreasing sequence Λ(f ) > Λ(f 0 ) > . . .
is finite, this process produces a relative train track map in finite time.
Corollary 2.10. There is an algorithm that takes φ ∈ Out(Fn ) and a nested sequence
C = F1 @ F2 @ · · · @ Fm of φ-invariant free factor systems as input and produces
a relative train track map f : G → G and filtration ∅ = G0 ⊂ G1 ⊂ . . . ⊂ GN = G
representing φ and such that for each Fi there exists Gj satisfying Fi = [Gj ].
Proof. The proof of this corollary is explicitly contained in the proof of [BFH00,
Lemma 2.6.7] (even though the statement of that lemma is weaker in that it assumes
that C is a single free factor system). The first step of the proof of the lemma is to
inductively construct a bounded topological representative f : G → G and filtration
∅ = G0 ⊂ G1 ⊂ . . . ⊂ GN = G representing φ such that for each Fi there exists
Gj satisfying Fi = [Gj ]. Then one applies the relative train track algorithm of
Theorem 2.2, checking that C is preserved, to promote f : G → G to a relative train
track map.
The third existence theorem that needs discussion is [FH11, Theorem 2.19]. We
first recall some notation that is used in its statement.
Notation 2.11. If u < r and
(1) Hu is irreducible;
(2) Hr is EG and each component of Gr is non-contractible; and
(3) for each u < i < r, Hi is a zero stratum that is a component of Gr−1 and each
vertex of Hi has valence at least two in Gr
then we say that each Hi is enveloped by Hr and write Hrz = ∪rk=u+1 Hk .
Theorem 2.12 ([FH11, Theorem 2.19]). For each φ ∈ Out(Fn ) there is a relative
train track map f : G → G and a filtration ∅ = G0 ⊂ G1 ⊂ . . . ⊂ GN = G
representing φ and satisfying the following properties.
(V) The endpoints of all indivisible periodic Nielsen paths are vertices.
(P) If a stratum Hm ⊂ Per(f ) is a forest then there exists a filtration element Gj
such [Gj ] 6= [Gl ∪ Hm ] for any Gl .
(Z) Each zero stratum Hi is enveloped by an EG stratum Hr . Each vertex in Hi is
contained in Hr and has link contained in Hi ∪ Hr .
(NEG) The terminal endpoint of an edge in a non-periodic NEG stratum Hi is
periodic and is contained in a filtration element of height less than i that is its
own core.
(F) The core of each filtration element is a filtration element.
12

Moreover, if C is a nested sequence of φ-invariant free factor systems then we may
choose f : G → G so that for each Fi ∈ C there exists Gj satisfying F = [Gj ].
The proof that f : G → G as in Theorem 2.12 can be constructed algorithmically
is contained in Section 3.4

3

Rotationless iterates

Every element of Out(Fn ) has an iterate that is rotationless (Definition 3.3). Corollary 3.14 below gives an explicit bound on the size of the iterate; see also [FH11,
Lemma 4.42] for a proof that such a bound exists.

3.1

More on markings

In this subsection we discuss markings in more detail and recall definitions and results
from [FH11, Section 3]. We assume throughout this subsection that f : G → G is a
relative train track map representing φ ∈ Out(Fn ).
Markings are used to translate the geometric properties of f : G → G into algebraic properties of φ. In this paper, we will focus on the geometric properties of the
homotopy equivalences and only bring in markings at the last minute when necessary. Further details on the material presented in this section can be found in [FH11,
Section 2.3].
Recall that the rose Rn denotes the rose with vertex ∗ and that we have once
and for all identified π1 (Rn , ∗) with Fn . A lift ∗˜ ∈ R̃n of ∗ to the universal cover R̃n
determines an isomorphism J˜∗ from Fn = π1 (Rn , ∗) to the group T (R̃n ) of covering
translations of R̃n given by [γ] maps to the covering translation T of R̃n that takes ∗˜
to the terminal endpoint of the lift of γ with initial endpoint ∗˜.
Let G be a finite graph equipped with a marking µ : Rn → G. Denoting µ(∗) by ?,
µ : (Rn , ∗) → (G, ?) induces an isomorphism µ# : π1 (Rn , ∗) → π1 (G, ?) that identifies
Fn with π1 (G, ?). Fix a lift ˜? of ? to G̃. The lift µ̃ : (R̃n , ∗˜) → (G̃, ˜?) determines a
homeomorphism ∂ µ̃ : ∂ R̃n → ∂ G̃ of Gromov boundaries. In this way ∂Fn , ∂ R̃n , and
∂ G̃ are all identified. Since covering translations are determined by their action on
Gromov boundaries, there is an induced identification of T (R̃n ) with T (G̃). For any
v ∈ G and lift ṽ ∈ G̃, there is an induced isomorphism Jṽ : π1 (G, v) → T (G̃) defined
exactly as J˜∗ . It is straightforward to check that µ# = J˜?−1 J˜∗ : π1 (Rn , ∗) → π1 (G, ?).
We also have an identification of automorphisms representing φ ∈ Out(Fn ) with
lifts f˜ : G̃ → G̃ of f : G → G given by Φ ↔ f˜ if the actions of Φ and f˜ on ∂Fn agree,
i.e. if ∂Φ = ∂ f˜. We usually specify f˜ by specifying f˜(˜?) or equivalently by specifying
the path ρ̃ = [˜?, f˜(˜?)] or its image ρ in G. We say that Φ or f˜ is determined by f˜(˜?), ρ̃,
or ρ. The action of Φ on π1 (G, ?) is given by γ 7→ f (γ)ρ := ρf (γ)ρ. If f˜ is determined
by ρ and f˜0 is determined by ρ0 then Φ0 = iγ Φ where Φ ↔ f˜, Φ0 ↔ f˜0 , and γ ∈ Fn is
represented by the loop ρ0 ρ. Working in the universal cover G̃ is algorithmic in the
13

sense that we can always compute the action of f˜ on arbitrarily large balls (in the
graph metric) around ˜?. In particular, given Φ we may algorithmically find f˜ with
Φ ↔ f˜ and vice versa. If f˜ fixes ṽ ∈ G̃ then f˜ ↔ Φ for Φ determined by ρ where
ρ̃ = η̃ f˜(η̃ −1 ) and η̃ = [˜?, ṽ].
Definition 3.1. For f˜ : G̃ → G̃ a lift of f : G → G, we denote the subgroup of T (G̃)
consisting of covering translations that commute with f˜ by ZT (f˜).
We state the following well known fact (see for example [FH11, Lemma 2.1]) as a
lemma for easy reference.
Lemma 3.2. If f˜ corresponds to Φ as above then ZT (f˜) and Fix(Φ) are equal when
viewed as subgroups of T (G̃).
Automorphisms Φ1 , Φ2 ∈ Aut(Fn ) are isogredient if Φ1 = ia Φ2 i−1
a for some inner
automorphism ia . Lifts f˜1 and f˜2 of f are isogredient if the corresponding automorphisms are isogredient. That is, f˜1 and f˜2 are isogredient if there exists a covering
translation T of G̃ such that f˜2 = T f˜1 T −1 . The set of attracting laminations for
φ ∈ Out(Fn ) is denoted L(φ); see [BFH00, Section 3].

3.2

Principal automorphisms and principal points

Recall from [GJLL98] that for each Θ ∈ Aut(Fn ),
Fix(∂Θ) = Fix− (∂Θ) ∪ Fix+ (∂Θ) ∪ ∂ Fix(Θ)
where Fix(Θ) is the fixed subgroup for Φ, Fix− (∂Θ) ⊂ ∂Fn is a finite union of Fix(Θ)orbits of isolated repellers and Fix+ (∂Θ) ⊂ ∂Fn is a finite union of Fix(Θ)-orbits of
isolated attractors.
Associated to each φ ∈ Out(Fn ) is a finite set L(φ) of attracting laminations, each
a closed subset of abstract lines which we refer to as leaves of the lamination. A leaf
γ of Λ ∈ L(φ) is generic in Λ if both of its ends are dense in Λ. See [BFH00, Section
3.1].
Definition 3.3. [FH11, Definition 3.1] For Φ ∈ Aut(Fn ) representing φ, denote the
set of non-repelling fixed points of ∂Φ by FixN (∂Φ). We say that Φ is a principal
automorphism and write Φ ∈ P(φ) if either of the following hold.
• FixN (∂Φ) contains at least three points.
• FixN (∂Φ) is a two point set that is neither the set of fixed points for the action
of some non-trivial a ∈ Fn on ∂Fn nor the set of endpoints of a lift of a generic
leaf of an element of L(φ).
If f : G → G is a topological representative of φ and f˜ : G̃ → G̃ is the lift corresponding to principal Φ then f˜ is a principal lift.

14

If Φ ∈ P(φ) and k > 1 then FixN (∂Φ) ⊂ FixN (∂Φk ) and Φk ∈ P(φk ). It may
be that the injection Φ 7→ Φk of P(φ) into P(φk ) is not surjective. It may also be
that FixN (∂Φk ) properly contains FixN (∂Φ) for some principal Φ and some k > 1.
If neither of these happen then we say that φ is forward rotationless. For a formal
definition, see [FH11, Definition 3.13].
Remark 3.4. It is becoming common usage to suppress the word “forward” in “forward rotationless” and we will follow that convention in this paper. So, when we
say that φ ∈ Out(Fn ) is rotationless, we mean that φ is forward rotationless. This
convention was followed in the recent work of Handel-Mosher [HM]. Be aware though
that the term “rotationless” has a slightly different meaning in [FH09].
Suppose that f : G → G is a topological representative of φ. By [FH11, Corollary 3.17], Fix(f˜) 6= ∅ for each principal lift f˜. The projected image of Fix(f˜) is
exactly a Nielsen class in Fix(f ) and a pair of principal lifts are isogredient if and
only if they determine the same Nielsen class of Fix(f ) [FH11, Lemma 3.8].
Definition 3.5. We say that x ∈ Per(f ) is principal if neither of the following
conditions are satisfied.
• x is not an endpoint of a non-trivial periodic Nielsen path and there are exactly two periodic directions at x, both of which are contained in the same EG
stratum.
• x is contained in a component C of Per(f ) that is topologically a circle and
each point in C has exactly two periodic directions.
If each principal periodic vertex is fixed and if each periodic direction based at a
principal periodic vertex is fixed then we say that f is rotationless.
Remark 3.6. By definition, a point is principal with respect to f if and only if it is
principal with respect to f k for all k ≥ 1.
Remark 3.7. Definition 3.5 is a corrected version of Definition 3.18 of [FH11] in which
‘x is not an endpoint of a non-trivial Nielsen path’ in the first item of Definition 3.5
is replaced with the inequivalent condition ‘x is the only point in its Nielsen class’.
Our thanks to Lee Mosher who pointed this out to us. Fortunately, the definition we
give here and not the one given in [FH11] is the one that is actually used in [FH11]
so no further corrections to [FH11] are necessary.
We are mostly interested in the case of a CT, where characterizations of principal
points are simpler. The next lemma gives two.
Lemma 3.8. Suppose f : G → G is a CT.
(1) A point x ∈ Per(f ) is principal iff x ∈ Fix(f ) and the following condition is not
satisfied.

15

• x is not an endpoint of a non-trivial Nielsen path and there are exactly
two periodic directions at x, both of which are contained in the same EGstratum.
(2) The following are equivalent for a point x ∈ Fix(f ). Let f˜ : G̃ → G̃ be a lift of
f fixing a lift x̃ of x.
(a) x is principal.
(b) f˜ is principal.
(c) FixN (∂ f˜2 ) is not the set of endpoints of a generic leaf of an element of
L(φ).
Proof. (1): Periodic Nielsen paths in a CT are fixed [FH11, Lemma 4.13] and so the
bulleted item in the lemma is equivalent to the first bulleted item of the Definition 3.5.
By definition, periodic edges of a CT are fixed and the endpoints of fixed edges are
principal. Therefore the second item in Definition 3.5 never holds. To complete the
proof it remains to show that all principal points of f are fixed. This holds for vertices
because CTs are rotationless. If x is a periodic but not fixed point in the interior of
an edge then (by definition of a CT) that edge must be in an EG stratum and so x
is not principal.
(2): By [FH11, Corollaries 3.22 and 3.27], (2a) and (2b) are equivalent. If f˜ is
principal, then by definition of rotationless and principal, FixN (∂ f˜) = FixN (∂ f˜2 ) is
not contained in the set of endpoints of a generic leaf. We see (2b) implies (2c). If
x is not principal for f then the bulleted item in (1) holds. In particular there are
exactly two periodic directions at x, both of which are in the same EG-stratum. By
[FH11, Lemma 2.13], FixN (∂ f˜2 ) contains the set of endpoints of a generic leaf of an
element of L(φ). By Remark 3.6, x is not principal for f 2 , and so f˜2 is not a principal
lift. Hence | FixN (∂ f˜2 )| < 3. We conclude (2c) implies (2a).

3.3

A sufficient condition to be rotationless and a uniform
bound

Before turning to Lemma 3.12, which gives a sufficient condition for an outer automorphism to be rotationless, we recall the connection between edges in a CT and
elements of Fix+ (Φ).
Definition 3.9. Given a CT f : G → G representing φ, let E (or Ef ) be the set of
oriented, non-fixed, and non-linear edges in G whose initial vertex is principal and
whose initial direction is fixed by Df . For each E ∈ E, there is a path u such that
f#k (E) = E · u · f# (u) · . . . · f#k−1 (u) for all k ≥ 1 and such that |f#k (u)| → ∞ with k.
The union of the increasing sequence
E ⊂ f (E) ⊂ f#2 (E) ⊂ . . .
16

of paths in G is a ray RE . Each lift R̃E of RE to the universal cover of G has a
well-defined terminal endpoint ∂ R̃E ∈ ∂Fn and so RE determines an Fn -orbit ∂RE in
∂Fn .
Lemma 3.10. Suppose that f : G → G is a CT and that E ∈ E. If Ẽ is a lift of
E and f˜ is the lift of f that fixes the initial endpoint of Ẽ then the lift R̃Ẽ of RE
that begins with Ẽ converges to a point
in Fix+ (∂ f˜). Moreover, E 7→ ∂RE defines a

surjection E → ∪Φ∈P(φ) Fix+ (∂Φ) /Fn .
Proof. Suppose that x is the initial endpoint of E ∈ E, that x̃ is a lift of x, that RẼ
is the lift of RE that begins at x̃ and that f˜ : G̃ → G̃ is the lift of f that fixes x̃.
Lemma 3.8(2) implies that f˜ is a principal lift and [FH11, Lemma 4.36(1)] implies that
R̃Ẽ converges to a point ∂ R̃E ∈ FixN (∂Φ) where Φ is the principal automorphism
corresponding to f˜. Since |f#k (u)| → ∞, it follows [GJLL98, Proposition I.1] that
∂ R̃Ẽ ∈ Fix+ (∂Φ). [FH11, Lemma 4.36(2)] implies that E 7→ ∂RE is surjective.
Remark 3.11. By [GJLL98, Proposition I.1], P ∈ Fix+ (∂Φ) is not fixed by any ia
and so is not fixed by ∂Φ0 for any Φ0 6= Φ representing φ. Thus ∪Φ∈P(φ) Fix+ (∂Φ) is
a disjoint union.
Lemma 3.12. Suppose that θ ∈ Out(Fn ) acts trivially on H1 (Fn ; Z/3Z) and induces
the trivial permutation on ∪Φ∈P(φ) Fix+ (∂Φ) /Fn for some (any) rotationless iterate
φ = θL of θ. Then θ is rotationless.
Proof. We show below that
(∗) For any Φ ∈ P(φ), there is Θ ∈ P(θ) with the property that FixN (∂Φ) ⊂
FixN (∂Θ).
To see why this is sufficient to prove the lemma, let Θk ∈ P(θk ) for some k ≥ 1.
Since θkL = φk , ΘLk ∈ P(φk ). Since φ is rotationless, there exists Φ ∈ P(φ) such that
ΘLk = Φk and FixN (∂Φ) = FixN (∂Φk ) = FixN (∂ΘLk ). By (∗), there is Θ ∈ P(θ) such
that
FixN (∂Θk ) ⊂ FixN (∂ΘLk ) = FixN (∂Φ) ⊂ FixN (∂Θ) ⊂ FixN (∂Θk )
It follows that Θk = Θk . We have now seen that P(θ) → P(θk ) given by Θ 7→ Θk is
surjective. By [FH11, Definition 3.13 and Remark 3.14], to show that θ is rotationless
it remains to show that FixN (∂Θk ) = FixN (∂Θ) for all Θ ∈ P(θ) and k ≥ 1. This
follows from the above displayed sequence of inclusions by taking Θk := Θk .
We now turn to the proof of (∗). Set F := Fix(Φ). We claim that there exists Θ
representing θ such that F ⊂ Fix(Θ). If the rank of F is < 2 then this follows from
[HM, Part II Theorem 4.1], which implies that θ fixes each conjugacy class that is
fixed by φ and in particular fixes each conjugacy class represented by an element of
Fix(Φ).
Suppose then that F has rank ≥ 2. We recall two facts.

17

• Each element of Fn is fixed by only finitely many elements of P(φ) and the
root-free ones that are fixed by at least two such automorphisms determine
only finitely many conjugacy classes; see [FH11, Lemma 4.40].
• F is its own normalizer in Fn . Proof: Since F is finitely generated and has rank
> 1, we can choose x ∈ ∂F ⊂ ∂Fn that is not fixed by any ∂ia , a ∈ Fn \ {1},
and so is not fixed by ∂Φ0 for any automorphism Φ0 6= Φ representing φ. If
y normalizes F then ∂iy (x) ∈ ∂F and x is fixed by ∂Φ0 where Φ0 = iy−1 Φiy =
iy−1 Φ(y) Φ. It follows that Φ(y) = y and hence y ∈ F.
By the first bullet, we may choose a basis {bj } for F consisting of elements that
are not fixed by any other element of P(φ). Applying [HM, Part II Theorem 4.1]
again, choose an automorphism Θj representing θ and fixing bj . The automorphism
Θj ΦΘ−1
fixes bj by construction and belongs to P(φ) by [FH09, Lemma 2.6] and
j
the fact that θ and φ commute. By uniqueness, Θj ΦΘ−1
= Φ and so Θj commutes
j
with Φ. In particular, Θj preserves F. Since F is its own normalizer, the outer
automorphism θ|F of F determined by Θj is independent of j. It follows that θ|F acts
trivially on H1 (F; Z/3Z). Since θL |F is the identity and since the kernel of natural
map Out(Fn ) → H1 (Fn ; Z/3Z) is torsion-free1 , θ|F is the identity and the claim is
proved.

Since θ acts trivially on ∪Φ∈P(φ) Fix+ (∂Φ) /Fn , each Q ∈ Fix+ (∂Φ) is fixed
by some ΘQ representing θ. Since ΘLQ and Φ both fix Q and represent φ we have
ΘLQ = Φ. As above, ΘQ commutes with Φ and so preserves F and Fix+ (∂Φ). For any
other Q0 ∈ Fix+ (∂Φ) we have ΘQ = ia ΘQ0 for some a ∈ Fn . Since both ΘQ and ΘQ0
preserve F, ia does as well and so a ∈ F.
It suffices to show that ΘQ is independent of Q and F ⊂ Fix(ΘQ ). This is obvious
if F is trivial. If F has rank one then F = Fix(ΘQ ) and
Q0 = Φ(Q0 ) = ΘLQ (Q0 ) = (ia ΘQ0 )L (Q0 ) = iLa ΘLQ0 (Q0 ) = iLa (Q0 )
which implies that a must be trivial and we are done. If F has rank ≥ 2 then there
is a unique Θ such that F ⊂ Fix(Θ) and Φ is the only automorphism representing φ
such that F ⊂ Fix(Φ). Thus ΘL = Φ. There exists b ∈ F such that ΘQ = ib Θ. We
have Φ = ΘLQ = iLb ΘL = iLb Φ so b is trivial and the proof is complete.
To apply Lemma 3.12 we will need a bound on the cardinality of

∪Φ∈P(φ) Fix+ (∂Φ) /Fn
Lemma 3.13. If φ ∈ Out(Fn ) is rotationless then

∪Φ∈P(φ) Fix+ (∂Φ) /Fn ≤ 15(n − 1)
1

This follows from the standard fact that the kernel of the natural map GLn (Z) → GLn (Z/3Z) is
torsion-free and the result of Baumslag-Taylor [BT68] that the kernel of the natural map Out(Fn ) →
GLn (Z) is torsion-free.

18

Proof. Choose a CT f : G → G representing φ and assume the notation of Definition 3.9. By Lemma 3.10 it suffices to show that the cardinality of the image
of E 7→ [RE ] is bounded by 15(n − 1). By construction, the initial vertex of E is
principal. If it has valence at least three then we say that it is natural.
There are at most 6(n − 1) oriented edges based at natural vertices. Some of
these are not fixed and so do not contribute to E. For example, if E is NEG then
(Lemma 4.21 of [FH11]) the terminal vertex of E is natural and the direction determined by Ē is not fixed. Similarly, if (E1 , E2 ) is an illegal turn of EG height then
the basepoint for this turn is natural and either E1 or E2 determines a non-fixed
direction. It follows that 6(n − 1) is an upper bound for the sum of the number of
edges in E that are based at natural vertices, the number of non-fixed NEG edges
and the number of EG stratum Hr with an illegal turn of height r.
It remains to account for those EG edges E ∈ E that are based at valence two
vertices v. By our previous estimate there are at most 6(n − 1) such v with the other
edge incident to v being non-fixed NEG. The only other possibility is that both edges
incident to v are EG. If the edges were in different strata, say Hr and Hr0 with r < r0
then v would have valence ≥ 2 in Gr (because Gr is a core subgraph), a contradiction.
Thus both edges belong to the same stratum Hr . Since v is a principal vertex, it must
be an endpoint of a Nielsen path ρ of height r. There are at most four edges incident
to valence two verticesat the endpoints of ρ and these determine at most three points
in ∪Φ∈P(φ) Fix+ (∂Φ) /Fn because the two directions pointing into ρ determine the
same point. There is at most one such ρ for each EG stratum Hr and ρ has an illegal
turn of height r so our initial bound of 6(n − 1) counted each ρ once; we now have
to count it two more times. In passing from the highest core Gs with s < r to Gr ,
at least two natural edges are added. It follows that the number of EG strata is
≤ 23 (n − 1). The total count then is 6(n − 1) + 6(n − 1) + 3(n − 1) = 15(n − 1).
2

Corollary 3.14. Let h(n) = |GL(Z/3/Z, n)| = 3(n −1) , let g(m) be Landau’s function, the maximum order of an element in the symmetric group Sm , and let Kn =
g(15(n − 1))! · h(n). If θ ∈ Out(Fn ) then θKn is rotationless.
Proof. Lemma 3.13 implies that θg(15(n−1))! induces the trivial permutation on

∪Φ∈P(φ) Fix+ (∂Φ) /Fn
for any rotationless iterate φ of θ. Hence θKn = (θg(15(n−1))! )h(n) satisfies the hypotheses of Lemma 3.12.
Remark 3.15. In Corollary 15.18, we will see that

| ∪Φ∈P(φ) Fix+ (∂Φ) /Fn | ≤ 6(n − 1)
and so we could take Kn = g(6(n − 1))! · h(n) in Corollary 3.14.

19

3.4

Algorithmic Proof of Theorem 2.12

We review the proof of the existence of f : G → G for θ as given in [FH11, Theorem 2.19], altering it slightly to make it algorithmic.
If C is not specified, take it to be the single free factor system [Fn ]. Apply Corollary 2.10 to construct a relative train track map f : G → G and ∅ = G0 ⊂ G1 ⊂
. . . ⊂ GN = G such that for each Fi ∈ C there exists Gj satisfying F = [Gj ]. The
modifications necessary to arrange all the properties but (V) are explicitly described
in the original proof. These steps come after (V) has been established in that proof
but make no use of (V) so there is no harm in our switching the order in which
properties are arranged. For notational simplicity we continue to refer to the relative
train track map as f : G → G even though it has been modified to satisfy all the
properties except possibly (V).
For Kn as in Corollary 3.14, θKn is rotationless. Subdivide f : G → G at the
(finite) set S of isolated points in Fix(f Kn ) that are not already vertices; these occur
only in EG edges E and are in one to one correspondence with the occurrences of E
or Ē in the edge path f#Kn (E). We claim that property (V) is satisfied. If not, then
perform a further finite ([FH11, Lemma 2.12]) subdivision so that (V) is satisfied.
[FH11, Proposition 3.29] and [FH11, Lemma 3.28] imply that every periodic Nielsen
path of f : G → G (after the further subdivision) has period at most Kn . But then S
contains the endpoints of all indivisible periodic Nielsen paths after all and no further
subdivision was necessary. Since subdivision at S is algorithmic, we are done.

4

Reducibility

Given a relative train track map f : G → G and filtration ∅ = G0 ⊂ G1 ⊂ . . . ⊂ GN =
G representing φ ∈ Out(Fn ), let ∅ = F0 @ F1 @ . . . @ FK be the increasing sequence
of distinct φ-invariant free factor systems that are realized by the Gi ’s. Assuming
that f : G → G satisfies property (F) of Theorem 2.12, Fi is realized by a unique core
filtration element for each i ≥ 1 and F0 is realized by G0 . If F is a free factor system
that is invariant by some iterate φk of φ and that is properly contained between Fi
and Fi+1 then we say that F is a reduction for Fi @ Fi+1 with respect to φ; if there is
no such F then Fi @ Fi+1 is reduced with respect to φ. If each Fi @ Fi+1 is reduced
with respect to φ then we say that f : G → G is reduced.
We assume for the rest of the section that φ is rotationless. In particular, a free
factor system that is invariant by some iterate of φ is φ-invariant [FH11, Lemma 3.30].
The main results of this section are Proposition 4.9 and Lemma 4.12. The former,
which assumes that f : G → G satisfies the conclusions of Theorem 2.12, provides
an algorithm in the EG case for deciding if Fi @ Fi+1 is reduced and for finding a
reduction if there is one. The latter has stronger requirements and easily leads to an
algorithm that handles the NEG case. We save the final details of that algorithm for
Section 8.
20

4.1

The EG case

Recall ([BFH00, Section 2] or [HM, Part I Fact 1.3]) that a pair of free factor systems
F 1 and F 2 has a well-defined meet F 1 ∧ F 2 characterized by [A] ∈ F 1 ∧ F 2 if and
only if there there exist subgroups A1 , A2 such that [Ai ] ∈ F i and A1 ∩ A2 = A.
Let B be the basis of Fn corresponding to the edges of Rn (see Section 2.1). If A is
a finitely generated subgroup of Fn then the Stallings graph RA of the conjugacy class
[A] of A is the core of the cover of Rn corresponding to A. There is an immersion
RA → Rn and if we subdivide RA at the pre-image of the vertex of Rn then we view
the edges of RA as labeled by their image edges in Rn and hence by elements of B.
The complexity of A is the number of edges in (subdivided) RA . Stallings graphs are
generalized in Section 9.2 and more discussion can be found there.
Lemma 4.1. Given free factor systems F 1 and F 2 one can algorithmically construct
F 1 ∧ F 2.
Proof. We may assume without loss that F 1 = {[A]} and F 2 = {[B]} for given
subgroups A, B. According to Stallings [Sta83, Theorem 5.5 and Section 5.7(b)], the
conjugacy classes of the intersections of A with conjugates of B are all represented
by components of the pullback of the diagram RA → R ← RB .
Lemma 4.2. Given a finite set {ai } of elements of Fn and a finite set {Aj } of
finitely generated subgroups of Fn there is an algorithm that finds the unique minimal
free factor system that carries each [ai ] and each conjugacy class carried by some [Aj ].
Proof. By replacing [ai ] by [hai i], we may assume that finite set {ai } is empty. The
complexity of A = {[Aj ]} is the sum of the complexities of the [Aj ]. By Gersten
[Ger84], there is an algorithm to find Θ ∈ Aut(Fn ) so that Θ(A) = {[Θ(Aj )]} has
minimal complexity in the orbit of A under the action of Aut(Fn ). Let P be the finest
partition of B such that the labels of each Stallings graph RΘ(Aj ) are contained in
some element of P. The free factor system F(P) determined by P is the minimal
free factor system carrying Θ(A); see [DF05, Lemma 9.19]. Hence Θ−1 (F(P)) is the
minimal free factor system carrying A.
Corollary 4.3. Suppose that φ ∈ Out(Fn ), that F 1 is a proper free factor system
and that F 0 @ F 1 is a (possibly trivial) φ-invariant free factor system. Then there
is an algorithm that decides if there is a φ-invariant free factor system F @ F 1 that
properly contains F 0 and that finds such an F if one exists.
Proof. First check if F 1 is φ-invariant or if F 1 = F 0 . If the latter is true the output of
the algorithm is NO. If the latter is false and the former is true the output is YES. If
neither is true apply Lemma 4.1 to compute F 1 ∧ φ(F 1 ) which is properly contained
in F 1 , contains F 0 and contains every φ-invariant free factor system that is contained
in F 1 . Repeat these steps with F 1 ∧ φ(F 1 ) replacing F 1 . Since there is a uniform
bound to the length of a strictly decreasing sequence of free factor systems [HM, Part
I Fact 1.3] the process stops after finitely many steps.
21

The following lemma is used in Step 1 of the proof of Proposition 4.9. Recall
from [FH11, Remark 3.20] that if f : G → G represents a rotationless φ and satisfies
the conclusions of Theorem 2.12, then for each Λ ∈ L(φ) there is an EG stratum Hr
such that Λ has height r and this defines a bijection between L(φ) and the set of EG
strata. The definition of a path being weakly attracted to Λ+ appears as [BFH00,
Definition 4.2.3].
Lemma 4.4. Suppose that f : G → G and ∅ = G0 ⊂ G1 ⊂ . . . ⊂ GN = G are a
relative train track map and filtration representing a rotationless φ and satisfying the
conclusions of Theorem 2.12 and that Hr is an EG stratum with associated attracting
lamination Λ+ . Then there is a computable constant C such that if σ0 ⊂ Gr is an
r-legal path that crosses at least C edges in Hr then every path σ ⊂ Gr that contains
σ0 as a subpath is weakly attracted to Λ+ .
Proof. Choose l so that the f l image of each edge in Hr crosses at least two edges in
Hr . It is shown in the proof of [BFH00, Lemma 4.2.2] (see also [BFH00, Corollary
4.2.4]) that C = 4lC0 + 1 satisfies the conclusions of our lemma for any constant C0
that is greater than or equal to the bounded cancellation constant for f . Since the
latter can be computed [BFH97, Lemma 3.1] using only the transition matrix for f ,
we are done.
Lemma 4.5. Suppose that f : G → G and ∅ = G0 ⊂ G1 ⊂ . . . ⊂ GN = G are
a relative train track map and filtration representing a rotationless φ and satisfying
the conclusions of Theorem 2.12. Suppose further that Hr is an EG stratum. Then
every indivisible periodic Nielsen path with height r has period one and there is an
algorithm that finds them all.
Remark 4.6. For a more efficient method than the one described in the proof see
[HM11, Section 3.4].
Proof. Suppose that ρ is an indivisible periodic Nielsen path of height r. Proposition 3.29 and Lemma 3.28 of [FH11] imply that ρ has period 1 and property (V) of
Theorem 2.12 implies that the endpoints of σ are vertices. By [BH92, Lemma 5.11],
ρ decomposes as a concatenation ρ = αβ −1 of r-legal edge paths whose initial and
terminal edges are in Hr . Let α0 and β0 be the initial edges of α and β respectively.
By Lemma 4.4 we can bound the number of Hr edges crossed by α and β by some
positive constant C. Since Hr is an EG stratum we can choose k so that f#k (E)
crosses more than C edges in Hr for each edge E in Hr . Since ρ = f#k (ρ) is obtained
from f#k (α)f#k (β −1 ) by canceling edges at the juncture point and since no edges in Hr
are cancelled when f k (α) and f k (β) are tightened to f#k (α) and f#k (β), α ⊂ f#k (α0 )
and β ⊂ f#k (β0 ). In particular, we can compute an upper bound for the number of
edges crossed by ρ, reducing us to testing a finite set of paths to decide which are
indivisible Nielsen paths.

22

A subgroup system A is a vertex group system if there exists a real Fn -tree with
trivial arc stabilizers such that A is the set of non-trivial vertex stabilizers.
Lemma 4.7. Suppose that f : G → G and ∅ = G0 ⊂ G1 ⊂ . . . ⊂ GN = G are a
relative train track map and filtration representing a rotationless φ and satisfying the
conclusions of Theorem 2.12. Suppose also that HN is an EG stratum with attracting
lamination Λ+ , and that [Gu ] ∪ Λ+ fills where Gu = G \ HNz . Then the following are
satisfied.
(1) There is a unique vertex group system A such that a conjugacy class [a] is not
weakly attracted to Λ+ if and only if [a] is carried by an element of A.
(2) A circuit σ ⊂ G represents an element of A if and only if σ splits as a concatenation of subpaths each of which is either contained in Gu or is an indivisible
Nielsen path of height N .
(3) There is a proper free factor system F 0 A [Gu ] such that one of the following
holds.
(a) A = F 0
(b) A fills and A = F 0 ∪ {[A]} where [A] has rank one.
Moreover, [Gu ] @ [GN ] is reduced with respect to φ if and only if F 0 = [Gu ].
Remark 4.8. Gu is not necessarily a core subgraph. It deformation retracts to a core
subgraph Gs and is obtained from Gs by adding NEG edges with terminal endpoints
in Gs . We use Gu in this lemma rather than Gs because indivisible Nielsen paths of
height N can have endpoints at the valence one vertices of Gu .
Proof. The existence of a vertex group system A as in (1) follows from [BFH00,
Theorem 6.1] and [HM, Part III Proposition 1.4(1)]. Uniqueness of A follows from
the fact [HM, Part I Lemma 3.1] that a vertex group system is determined by the
conjugacy classes that it carries. For the rest of this proof we take (1) to be the
defining property of A. Note that A depends only on Λ+ and φ and not on the choice
of f : G → G. In particular, A is φ-invariant.
If a circuit σ ⊂ G splits into subpaths that are either contained in Gu or are
Nielsen paths of height N then the number of HN edges in f#k (σ) is independent of k
and σ is not weakly attracted to Λ+ . This proves the if direction of (2).
The only if direction of (2) is more work. [BFH00, Lemmas 4.2.6 and 2.5.1] and
Lemma 4.5 imply that there exists k ≥ 1 such that f#k (σ) splits into subpaths that
are either contained in GN −1 , are indivisible Nielsen paths of height N or are edges
of height N . Assuming that σ, and hence f#k (σ), is not weakly attracted to Λ+ ,
[BFH00, Corollary 4.2.4] implies that no term in this splitting is an edge of height
N . If f#k (σ) ⊂ Gu then σ ⊂ Gu and we are done. If f#k (σ) is a closed Nielsen path of

23

height N then σ and f#k (σ) have the same f#k -image and so are equal. In particular,
σ is a Nielsen path of height N . In the remaining case, there is a splitting
f#k (σ) = µ1 · ν1 · µ2 · ν2 · . . . · µm · νm
into subpaths µi ⊂ Gu and Nielsen paths νi of height N . Since the endpoints of each
µi are fixed by f and since the restriction of f to each f -invariant component of Gu
is a homotopy equivalence, there exist paths µ0i ⊂ Gu with the same endpoints as µi
such that f#k (µ0i ) = µi . Letting
σ 0 = µ01 · ν1 · µ02 · ν2 · . . . · µ0m · νm
we have f#k (σ 0 ) = f#k (σ) and hence σ 0 = σ. In particular, σ splits into subpaths of Gu
and indivisible Nielsen paths of height N . This completes the proof of (2).
The main statement of (3) follows from [BFH00, Proposition 6.0.1 and Remark
6.0.2] (which applies because there is a CT representing φ in which Λ+ corresponds to
the highest stratum and [Gu ] is realized by a core filtration element). Since φ preserves
A, it acts periodically on the components of A. [FH11, Lemma 3.30] therefore implies
that φ preserves each rank one component of A and so also preserves F 0 . If F 0 6= [Gu ]
then F 0 is a reduction for [Gu ] @ [GN ]. This proves the only if direction of the
moreover statement.
Suppose then that F 0 = [Gu ]. If either (a) or (b) holds then any free factor system
F that properly contains [Gu ] carries a conjugacy class not carried by A. Item (1)
implies that F carries a conjugacy classs that is weakly attracted to Λ+ . If F is
φ-invariant then F carries Λ+ in addition to containing Gu and so is improper. This
completes the proof of the if direction of the moreover statement.
The next proposition shows how to reduce a relative train track map satisfying the
conclusions of Theorem 2.12. One way to create an unreduced example is to identify
a pair of distinct fixed points in a stratum Hr of a CT where Hr is both highest and
EG.
Proposition 4.9. Suppose that f : G → G and ∅ = G0 ⊂ G1 ⊂ . . . ⊂ GN = G are a
relative train track map and filtration representing a rotationless φ and satisfying the
conclusions of Theorem 2.12. Suppose also that Hr is an EG stratum and that Gs is
the highest core filtration element below Gr . Then there is an algorithm to decide if
[Gs ] @ [Gr ] is reduced and if it is not to find a reduction.
Proof. By [FH11, Lemma 3.30], the non-contractible components of Gr are f -invariant;
in particular Hr is contained in a single component of Gr . By restricting to this component we may assume that Hr is the top stratum and hence that r = N .
Let Λ+ ∈ L(φ) be the lamination associated to HN . By [BFH00, Lemma 3.2.4]
there exists Λ− ∈ L(φ−1 ) such that the smallest free factor system that carries Λ+
is the same as the smallest free factor system that carries Λ− and we denote this by
FΛ . It follows that the realizations of Λ+ and Λ− in any marked graph cross the same
24

set of edges in that graph. It also follows that the smallest free factor system that
carries [Gs ] and Λ+ is the same as the smallest free factor system that carries [Gs ]
and Λ− and we denote this by Fs,Λ . Since both [Gs ] and Λ± are φ-invariant, [BFH00,
Corollary 2.6.5] implies that Fs,Λ is φ-invariant.
Choose constants as follows.
• CE = 6(n − 1) is the maximal number of oriented natural edges in a marked
core graph of rank n.
• M = 2n; if F0 @ F1 @ . . . @ FP is an increasing nested sequence of free factor
systems of Fn then P ≤ M − 1. (This follows by induction on the rank n and
the observation that if FP = {Fn } with n > 1 then there exists F such that
FP −1 @ F @ FP and F consists of a pair of conjugacy classes whose ranks add
to n.)
• C0 = C + 2 where C satisfies the conclusion of Lemma 4.4.
Step 1: An existence result when Fs,Λ is proper : Consider the set K of
marked graphs K containing a (possibly empty) core subgraph K0 and equipped with
a marking preserving homotopy equivalence p : K → G taking vertices to vertices
such that
(a) p K0 : K0 → Gs is a homeomorphism (If s = 0 then Gs = K0 = ∅).
(b) the restriction of p to each natural edge is either an immersion or constant.
(c) there is at most one natural edge on which p is constant.
Each natural edge E of K ∈ K is labeled by p(E), thought of as a (possibly trivial)
edge path in G. We do not distinguish between two elements of K if there is a label
preserving homeomorphism between them. The length |E| of a natural edge E is the
number of edges in p(E) and the total length |K| of K is the sum of the length of its
−
natural edges. The number of HN edges in p(E) is denoted |E|N . Let Λ+
K and ΛK
be the realizations of Λ+ and Λ− in K. As observed above, the set of edges crossed
by Λ+ is the same as the set of edges crossed by Λ− . We denote this common core
subgraph by KΛ .
We claim that if Fs,Λ is proper then there exists an element K ∈ K with the
following properties.
(1) |E|N ≤ C0 for all natural edges E of K.
(2) The restriction of p to a leaf of Λ+
K is an immersion.
(3) K0 ∪ KΛ is a proper core subgraph.

25

Note that K0 ∪ KΛ is a core subgraph because it is a union of core subgraphs so the
content of (3) is that K0 ∪ KΛ is proper. Our proof of the claim makes use of an idea
from the proof of Proposition 3.4 in Part IV of [HM].
Assuming that Fs,Λ is proper, there exists a marked graph K with proper core
subgraphs K0 ⊂ K1 ⊂ K and a marking preserving homotopy equivalence p : K → G
satisfying (a) and (b) and [K1 ] = Fs,Λ . The last property implies that K1 = K0 ∪ KΛ
so (3) is satisfied. If there is at least one natural edge in K \ K1 on which p is an
immersion then collapse each natural edge in K on which p is constant to a point.
Otherwise, collapse each natural edge in K1 on which p is constant and all but one
natural edge in K \K1 on which p is constant to a point. The resulting marked graph,
which we continue to denote K, still satisfies (a) and (b) because p|K0 is injective and
so K0 is unaffected by the collapsing and (c) is now satisfied so K ∈ K. Replacing
K1 by its image under the collapse, it is still true that K1 = K0 ∪ KΛ is a proper core
subgraph and now the restriction of p to each natural edge of K1 is an immersion.
(It may now be that [K1 ] properly contains Fs,Λ .)
If p K1 is not an immersion then there is a pair of natural edges E1 , E2 in K1 with
the same initial vertex and such that the edge paths p(E1 ) and p(E2 ) have the same
first edge, say e. Folding the initial segments of E1 and E2 that map to e produces
an element K 0 ∈ K with subgraph K00 satisfying (a) and such that |K 0 | < |K|. Note
that (3) is still satisfied because K00 ∪ KΛ0 is contained in the image K10 ⊂ K 0 and
[K1 ] = [K10 ]. Replacing K with K 0 and repeating this finitely many times, we may
assume that p K1 is an immersion and hence that p restricts to an immersion on
−
leaves of Λ+
K and ΛK . In particular, (2) is satisfied. If (1) is satisfied then the proof
of the claim is complete.
Suppose then that there is a natural edge E of K such that |E|r > C0 = C + 2.
By [BFH00, Theorem 6.0.1], a leaf of Λ− is not weakly attracted to a generic leaf of
−
Λ+ . Lemma 4.4 therefore implies that at least one of the two laminations Λ+
K and ΛK
does not cross E. It follows that FΛ @ [K \ E] and hence that E is contained in the
complement of KΛ . Since E is obviously in the complement of K0 , we have that E
is contained in the complement of K0 ∪ KΛ . If there is a natural edge on which p is
constant, it must be in the complement of K0 ∪ KΛ ∪ E and we collapse it to a point.
As above, the resulting marked graph is still in K and (2) and (3) are still satisfied.
We may now assume that p is an immersion on each natural edge of K. The map
p : K → G is not a homeomorphism so there is at least one pair of edges that can be
folded. Perform the fold and carry the K0 ⊂ K notation to the new marked graph.
It is still true that K ∈ K and that (2) holds. Folding reduces |E|r by at most 2 so
there is still an edge with |E|r > C. Arguing as above we see that E is contained in
the complement of K0 ∪ KΛ so (3) is still satisfied. If (1) is satisfied then the proof
of the claim is complete. Otherwise perform another fold. Conditions (2) and (3)
are satisfied so check condition (1) again. Folding reduces |K| so after finitely many
folds, (1) is satisfied and the claim is proved.
Step 2: Part 1 of the algorithm : In this step we present an algorithm that either
26

finds a reduction for [Gs ] @ [Gr ] or concludes that Fs,Λ is improper, i.e. Fs,Λ = {[Fn ]}.
In the former case we are done. In the latter case we move on to the second part of
the algorithm in which we either find a reduction for [Gs ] @ [Gr ] or we conclude that
[Gs ] @ [Gr ] is irreducible.
(A1) Choose a generic leaf γ ⊂ G of Λ+ . One way to do this is to choose an edge e
of Hr and k > 0 so that at least one occurrence of e in the edge path f#k (e) is
neither the first nor last Hr edge. Then e ⊂ f#k (e) ⊂ f#2k (e) ⊂ . . . and the union
of these paths is a generic leaf of Λ+ by [BFH00, Corollary 3.1.11 and Lemma
3.1.15].
(A2) Let C1 = 1. Choose a subpath γ1 of γ that crosses at least
(CE + 1)C0 + CE (C1 + C0 ) + 2C0
edges in Hr and let L1 be the number of edges in γ1 . (The choice of these
constants will be clarified in Step 3.)
(A3) Enumerate all core graphs J of rank < n satisfying: there is a core subgraph
J0 ⊂ J and a map p : J → G taking vertices to vertices such that the restriction
of p to each natural edge is an immersion onto a path of length at most L1 and
such that p J0 : J0 → Gs is a homeomorphism. Label the natural edges of
J by their p images. We do not distinguish between labeled graphs that differ
by a label preserving homeomorphism so there are only finitely many J and
we consider them one at a time. If σ ⊂ J is a path with endpoints at natural
vertices and if p restricts to an immersion on σ then we let |σ| be the number
of edges crossed by p(σ) and |σ|r the number of Hr edges crossed by p(σ).
Let p# be the homomorphism induced by p : J → G on fundamental groups.
By Lemma 4.2 we can decide if p# is an isomorphism to a free factor system [J]
of Fn . If not, then move on to the next candidate. If yes, then apply Lemma 4.3
with F0 = [J0 ] = [Gs ] and F1 = [J]. If this produces a φ-invariant F @ [J]
that properly contains [Gs ] then we have found a reduction and the algorithm
stops. Otherwise we know that [J] does not contain such an F. In particular
[J] does not contain Fs,Λ and so does not carry Λ+ . Choose a finite subpath
γ1,J ⊂ γ ⊂ G that does not lift to J.
By [BFH00, Lemma 3.1.10(4)] there exists an edge E in Hr and k ≥ 1 such that
γ1,J is a subpath of f˜#k (E). By [BFH00, Lemma 3.1.8(3)] there is a computable
k0 so that for any edge E 0 in Hr and any l ≥ k + k0 , f˜#k (E), and hence γ1,J ,
is a subpath of f#l (E 0 ). Finally, by [BFH00, Lemma 3.1.10(3)] there exists
computable C2,J > 0 so that if σ is a subpath of γ that crosses ≥ C2,J edges of
Hr then σ contains some f#l (E 0 ), and hence contains γ1,J , as a subpath and so
does not lift into J. Now move on to the next candidate.

27

At the end of the process we have either found a reduction and the algorithm
stops or we have found a constant C2 = max{C2,J } so that if σ is a subpath of
γ that crosses at least C2 edges of Hr then σ does not lift into any J. Choose
a subpath γ2 of γ that crosses at least
(CE + 1)C0 + CE (C2 + C0 ) + 2C0
edges of Hr and let L2 be the number of edges crossed by γ2 .
(A4) Repeat (A3) replacing L1 with L2 . At the end of the process we have either
found a reduction and the algorithm stops or we have found a constant C3 so
that if σ is a subpath of γ that crosses at least C3 edges of Hr then σ does not
lift into any J. Choose a subpath γ3 of γ that crosses at least
(CE + 1)C0 + CE (C3 + C0 ) + 2C0
edges of Hr and let L3 be the number of edges crossed by γ3 .
(A5) Iterate this process up to M times. If after M iterations the algorithm has not
found a reduction and stopped, then stop and conclude that Fs,Λ = {[Fn ]}.
Step 3: Justifying part 1 of the algorithm: In this step we verify that if Fs,Λ is
proper then the above algorithm finds a reduction in at most M steps.
Suppose K ∈ K satisfies (1) - (3) and let K(L1 ) be the subgraph of K consisting
of natural edges E with |E| ≤ L1 . Lift the path γ1 into KΛ . After removing initial
and terminal subpaths contained in single natural edges of KΛ , we have a natural (in
K) edge path γ1,K ⊂ Λ+
K ⊂ KΛ that projects onto all of γ1 except perhaps initial and
terminal segments that cross at most C0 edges of Hr . Thus γ1,K ⊂ K(L1 ) and
|γ1,K |r ≥ (CE + 1)C0 + CE (C1 + C0 )
Combining this inequality with (1), we see that γ1,K has a subpath that decomposes
as
α1 β1 α2 . . . βCE αCE +1
where each αi is a single natural edge and each βi is a natural subpath whose image
under p crosses at least C1 edges in Hr . Since there are at most CE oriented natural
edges in K, it follows that γ1,K contains a natural subpath that begins and ends with
the same oriented natural edge and whose p-image crosses at least C1 = 1 edges in
Hr . This proves that that there is a circuit in K(L1 ) that is not in K0 and hence that
[K(L1 )] properly contains [K0 ]. By (3), K0 ∪ KΛ is proper and so if K0 ∪ KΛ ⊂ K(L1 )
then K0 ∪ KΛ occurs as a J in the first iteration of the process and Lemma 4.3 finds
a reduction in the first iteration of (A3) because Fs,Λ @ [K0 ∪ KΛ ].

28

If no reduction is found in the first iteration then proceed to the second iteration as
described in (A4). By the same reasoning, there is a natural edge path γ2,K ⊂ K(L2 )
such that
|γ2,K |r ≥ (CE + 1)C0 + CE (C2 + C0 )
and there is a subpath of γ1,K that decomposes as
α1 β1 α2 . . . βCE αCE +1
where each αi is a single natural edge and each βi is a natural subpath whose image
under p crosses at least C2 edges in Hr . It follows that there is a circuit in K(L2 ) that
is not in K(L1 ) and hence that [K(L2 )] properly contains [K(L1 )]. If K0 ∪KΛ ⊂ K(L2 )
then K0 ∪ KΛ occurs as a J in the second iteration of the process and our algorithm
finds a reduction.
Continuing on, the iteration either produces a reduction within M steps or produces a properly nested sequence
[K0 ] @ [K(L1 )] @ [K(L2 )] @ . . . @ [K(LM )]
of free factors. Since the latter contradicts the definition of M , a reduction must have
been found.
Step 4: Part 2 of the algorithm: In this part of the algorithm we assume that
Fs,Λ is improper. The filtration element Gu = GN \ HNz deformation retracts to Gs ,
see Remark 4.8. In particular, [Gu ] = [Gs ].
Given a circuit σ ⊂ G [resp. a subgroup A] let Fu,σ [resp. Fu,A ] be the smallest free
factor system that carries [σ] [resp. every conjugacy class in [A]] and every conjugacy
class in [Gu ]. By Lemma 4.2, Fu,σ and Fu,A can be algorithmically determined.
By Lemma 4.5, the set P of indivisible periodic Nielsen paths with height r is
finite, can be determined algorithmically and each element of P has period one. For
notational convenience we assume that P is closed under orientation reversal. Let Σ
be the set of circuits in G that split into a concatenation of paths in Gu and elements
of P . Lemma 4.7 implies that Σ is the set of circuits that are not weakly attracted
to Λ+ and that the conjugacy classes determined by Σ are exactly those carried by
the subgroup system A of that lemma.
We consider several cases, each of which can be checked by inspection of Gu and
the elements of P . If every circuit in Σ is contained in Gu then A = [Gu ] and HN is
reduced by Lemma 4.7(3).
As a second case, suppose that there is a non-trivial path µ ⊂ G with endpoints
x, y ∈ Gu such that µ is homotopic rel endpoints to a concatenation of elements of P
and so is a Nielsen path of height N . Let [B] be the conjugacy class of the subgroup
of Fn represented by closed paths based at x that decompose as a concatenation of
subpaths, each of which is either µ, µ−1 or a path in Gu with endpoints in {x, y}. Then
[B] is φ-invariant, has rank ≥ 2, and each conjugacy class in [B] is represented by a
29

circuit σ ∈ Σ. By Lemma 4.7(3) there is a proper free factor system that carries [Gu ]
and the conjugacy class of each element of B. It follows that Fu,B is proper. Since
both [Gu ] and [B] are φ-invariant, Fu,B is φ-invariant by [BFH00, Corollary 2.6.5]
and we have found a reduction of HN .
The final case is that there are no paths µ ⊂ G as in the second case and there
is at least one element σ ∈ Σ that is not contained in Gu . Each such σ is homotopic
to a concatenation of elements of P . In particular, the conjugacy class determined
by σ is φ-invariant and so Fu,σ is φ-invariant. Choose one such σ and check if Fu,σ
is proper. If it is then we have found a reduction of HN and we are done so suppose
that it is not. Lemma 4.7(3) implies that [σ] is carried by a rank one component
[A] of A and that A = F 0 ∪ [A] for some φ-invariant free factor system F 0 . If there
exists an element σ 0 ∈ Σ that is not carried by [Gu ] and such that σ and σ 0 are not
multiples of the same root-free circuit then [σ 0 ] is not carried by [A] so Fu,σ0 is a
reduction. Otherwise, F 0 = [Gu ] and Hr is reduced. This completes the second step
in the algorithm and so also the proof of the proposition.

4.2

The NEG case

We now consider reducibility for NEG strata, beginning with a pair of examples.
Example 4.10. Suppose that f : G → G is a homotopy equivalence with filtration
∅ = G0 ⊂ G1 ⊂ . . . ⊂ GN = G representing φ ∈ Out(Fn ) and that Gr+2 = Gr ∪Er+1 ∪
Er+2 where Gr is a connected core subgraph and where Hr+1 = Er+1 and Hr+2 = Er+2
are oriented edges with a common initial vertex not in Gr and a common terminal
endpoint in Gr . Suppose also that f (Er+1 ) = Er+1 u and f (Er+2 ) = Er+2 u for some
closed non-trivial path u ⊂ Gr and that f Gr is a CT. Then the (NEG Nielsen
Paths) property of f Gr+2 fails. The CT algorithm corrects this (see Section 8.1) by
discovering that Er+2 Ēr+1 is a Nielsen path and then sliding the terminal endpoint
0
of Er+2 along Ēr+1 . In other words, Er+2 is replaced by a fixed loop Er+2
based at
the initial endpoint of Er+1 . Note that while establishing (NEG Nielsen Paths) for
f Gr , we have discovered a reduction of [Gr ] @ [Gr+2 ]. Namely, the φ-invariant free
0
factor system {[Gr ], [Er+2
]} is properly contained between [Gr+1 ] = [Gr ] and [Gr+2 ].
Example 4.11. Suppose that f : G → G is a homotopy equivalence with filtration
∅ = G0 ⊂ G1 ⊂ . . . ⊂ GN = G representing φ ∈ Out(Fn ), that Gr+1 = Gr ∪ Er+1
where Gr is a connected core subgraph such that f Gr is a CT and where Hr+1 =
Er+1 is a fixed edge whose initial and terminal endpoints, x and y, belong to the
same Nielsen class of f Gr . Then f Gr+1 satisfies all the properties of a CT except
that [Gr ] @ [Gr+1 ] is not reduced. The CT algorithm corrects this in stages. First,
a Nielsen path σ ⊂ Gr connecting y to x is found. Then the terminal end of Er+1 is
slid along σ so that its new terminal endpoint is x. Thus Er+1 is replaced by a fixed
0
0
edge Er+1
with both endpoints at x. Finally, x is blown up to a fixed edge Er+2
with

30

0
0
Er+1
attached at the ‘new’ endpoint of Er+2
and the remaining edges in the link of x
still attached at x. Both [Gr ] @ [Gr+1 ] and [Gr+1 ] @ [Gr+2 ] are reduced.

Lemma 4.12. Suppose that f : G → G and ∅ = G0 ⊂ G1 ⊂ . . . ⊂ GN = G are
a relative train track map and filtration satisfying the conclusions of Theorem 2.12
and representing a rotationless φ ∈ Out(Fn ). Suppose further that Gs is core, that
Hs = {Es } is an NEG stratum, that C is the component of Gs that contains Hs and
that f C satisfies (NEG Nielsen Paths). If [C \ Es ] @ [C] is reducible then Es is
fixed and its terminal endpoint is connected to its initial endpoint by a Nielsen path
β ⊂ C \ Es . In particular, Es β is a basis element and {[Gs−1 ], [Es β]} is a φ-invariant
free factor system that is properly contained between [Gs−1 ] and [Gs ].
Proof. By restricting to C, we may assume that G = C = Gs and hence that Gs−1
has either a single component of rank n − 1 or two components whose ranks add to
n. If [C \ Es ] @ [C] is reducible, there is a marked graph K with distinct proper core
subgraphs K1 ⊂ K2 ⊂ K such that [K1 ] = [Gs−1 ] and such that [K2 ] is φ-invariant.
From
−χ(K1 ) ≤ −χ(K2 ) < −χ(K) = −χ(K1 ) + 1
it follows that K2 is obtained from K1 by adding a disjoint loop α and that K \ K2
is an edge E. In particular, K1 is connected.
We claim that the circuit σ ⊂ G representing [α] crosses Es exactly once. The
marked graph K 0 obtained from K by collapsing the components of a maximal forest
is a rose with α as one of its edges. The marked graph G0 obtained from G by
collapsing the components of a maximal forest in Gs−1 is a rose with Es as one of its
edges. Moreover [K 0 \ α] = [K1 ] = [Gs−1 ] = [G0 \ Es ]. Let h : K 0 → G0 be a homotopy
equivalence that respects markings and that restricts to an immersion on each edge.
Then h(K 0 \ α) = G0 \ Es and it suffices to show that h(α) crosses Es exactly once.
This follows from [BFH00, Corollary 3.2.2].
Having verified the claim, we can now complete the proof of the lemma. Since
[K2 ] is φ-invariant and α is a component of K2 , α determines a φ-invariant conjugacy
class. It follows that σ decomposes as a concatenation of indivisible Nielsen paths
and fixed edges. Since σ crosses Es exactly once, the (NEG Nielsen Paths) property
of f : G → G implies that Es is a fixed edge. Thus σ decomposes as a circuit into
Es β where β is a Nielsen path in Gs−1 .

5

Definition of a CT

The definition of a CT evolved over many years, growing out of improved relative
trains [BFH00] which grew out of relative train tracks [BH92]. In addition to the nine
items that make up the formal definition, there are numerous auxiliary consequences
of these definitions that are used repeatedly. We have included the complete definition

31

here for the reader’s convenience but recommend consulting [FH11] (see also [HM,
Part I Section 1.5]) for discussion and elaboration.
We have already discussed some of the technical terms in the definition of CT.
• For basics of relative train track theory, including the definitions of relative train
track maps, filtrations, EG and NEG strata, linear edges and Nielsen paths see
Section 2.1.
• For zero strata enveloped by EG strata see Notation 2.11.
• For principal vertices and rotationless f : G → G see Definition 3.3.
• For the definition of a filtration being reduced see the beginning of Section 4.
There are a few more terms that need defining.
Definition 5.1. [FH11, Definition 4.1] If w is a closed root-free Nielsen path and
Ei , Ej are linear edges satisfying f (Ei ) = Ei wdi and f (Ej ) = Ei wdj for distinct
di , dj > 0 then a path of the form Ei w∗ Ēj is called an exceptional path.
Definition 5.2. [FH11, Definition 4.3] If Hr is EG and α ⊂ Gr−1 is a non-trivial path
with endpoints in Hr ∩ Gr−1 then we say that α is a connecting path for Hr . If E is
an edge in an irreducible stratum Hr and k > 0 then a maximal subpath σ of f#k (E)
in a zero stratum Hi is said to be r-taken or just taken if r is irrelevant. A non-trivial
path or circuit σ is completely split if it has a splitting, called a complete splitting, into
subpaths, each of which is either a single edge in an irreducible stratum, an indivisible
Nielsen path, an exceptional path or a connecting path in a zero stratum Hi that is
both maximal (meaning that it is not contained in a larger subpath of σ in Hi ) and
taken. Note that the endpoints, if any, of a completely split path are at vertices.
Definition 5.3 (Definition 4.4 [FH11]). A relative train track map is completely split
if
(1) f (E) is completely split for each edge E in each irreducible stratum.
(2) If σ is a taken connecting path in a zero stratum then f# (σ) is completely split.
Proper extended folds, which are referred to in the (EG Nielsen Paths) property
of a CT are defined in [BFH00, Definition 5.3.2]. We will not review that here, in
part because the actual definition is never used in this paper and in part because in
applications one almost always refers to a consequence of this property (for example
[FH11, Corollary 4.19]) rather than to the property itself.
Definition 5.4. A relative train track map f : G → G and filtration F given by
∅ = G0 ⊂ G1 ⊂ . . . ⊂ GN = G is said to be a CT (for completely split improved
relative train track map) if it satisfies the following properties.
(1) (Rotationless) f : G → G is rotationless.(Definition 3.3)
32

(2) (Completely Split) f : G → G is completely split.
(3) (Filtration) F is reduced. (Section 4) The core of each filtration element is a
filtration element.
(4) (Vertices) The endpoints of all indivisible periodic (necessarily fixed) Nielsen
paths are (necessarily principal) vertices. The terminal endpoint of each nonfixed NEG edge is principal (and hence fixed).
(5) (Periodic Edges) Each periodic edge is fixed and each endpoint of a fixed
edge is principal. If the unique edge Er in a fixed stratum Hr is not a loop then
Gr−1 is a core graph and both ends of Er are contained in Gr−1 .
(6) (Zero Strata) If Hi is a zero stratum, then Hi is enveloped by an EG stratum
Hr , each edge in Hi is r-taken and each vertex in Hi is contained in Hr and has
link contained in Hi ∪ Hr .
(7) (Linear Edges) For each linear Ei there is a closed root-free Nielsen path wi
such that f (Ei ) = Ei widi for some di 6= 0. If Ei and Ej are distinct linear edges
with the same axes then wi = wj and di 6= dj .
(8) (NEG Nielsen Paths) If the highest edges in an indivisible Nielsen path σ
belong to an NEG stratum then there is a linear edge Ei with wi as in (Linear
Edges) and there exists k 6= 0 such that σ = Ei wik Ēi .
(9) (EG Nielsen Paths) If Hr is EG and ρ is an indivisible Nielsen path of height
r, then f |Gr = θ ◦ fr−1 ◦ fr where :
(a) fr : Gr → G1 is a composition of proper extended folds defined by iteratively folding ρ.
(b) fr−1 : G1 → G2 is a composition of folds involving edges in Gr−1 .
(c) θ : G2 → Gr is a homeomorphism.
We include the following for future reference.
Lemma 5.5. If f : G → G is a CT then f k : G → G is a CT for all k ≥ 1.
Proof. By [FH11, Lemma 4.13], every periodic Nielsen path for f has period one.
With this in hand, the first eight CT properties for f k are easy to check. The remaining property (EG Nielsen Paths) for f k follows from [FH11, Corollary 4.33].
The following example shows that the restriction of a CT f to a component of a
core filtration element need not be a CT.

33

Example 5.6. We refer to Figure 1 for notation. The map f : G → G given by
e 7→ e, b 7→ be, c 7→ c, and d 7→ de2 is a CT with the filtration
∅ ⊂ {e} ⊂ {e, b} ⊂ {e, b, c} ⊂ G
and the restriction of f to each filtration element is a CT. If we however consider the
new filtration
∅ ⊂ {e} ⊂ {e, c} ⊂ {e, c, d} ⊂ G
then f is still a CT with the new filtration but f |{e, c, d} is not a CT because it does
not satisfy (Vertices).
c

G

e

d

b

Figure 1: Example 5.6

6

Sliding NEG edges

The key step for arranging that an NEG edge has good properties under iteration is to
slide the terminal endpoint of the edge into an optimal position in the lower filtration
element that contains it. This is carried out in [BFH00, Proposition 5.4.3]. In this
section we make the algorithmic arguments needed to replace the non-algorithmic
parts of the original proof.

6.1

Completely Split Rays

Recall from [FH11, Definition 4.4] that a splitting σ = σ1 ·σ2 . . . is a complete splitting
if each σi is either a single edge in an irreducible stratum, an indivisible Nielsen path,
an exceptional path or a maximal subpath in a zero stratum (with some additional
features that we will not recall here.) A finite path or circuit has at most one complete
splitting by [FH11, Lemma 4.11]. The first item of our next lemma states that the
same is true for rays.
Recall from Section 2.1 that a ray σ with initial point a vertex is thought of as
an edge path σ = E0 E1 . . .. The initial and terminal endpoints, wi and wi+1 of Ei
34

are the vertices of σ. We view the set W of vertices of a path as being ordered by
their subscripts. A decomposition of σ into subpaths is specified by a subset of W;
if wi and wj are consecutive elements of the subset then Ei . . . Ej−1 is a term in the
decomposition. If the decomposition is a splitting then we refer to these vertices as
splitting vertices. A similar definition holds for circuits.
Lemma 6.1. Suppose that f : G → G is a CT, that R ⊂ G is a completely split ray
and that R0 is a subray of R that has a complete splitting. Then
(1) The complete splitting of R is unique.
(2) Let v be the first splitting vertex for R that is contained in R0 (when the edge
path R0 is viewed as a subpath of the edge path R). Then each splitting vertex
w for R0 that comes after v (in the ordering of splitting vertices of R0 ) is a
splitting vertex for R.
Proof. The second item implies the first by taking R0 = R so we need only prove the
second. Let µ0 be the term in the complete splitting of R0 whose initial vertex is w. If
µ0 is either an indivisible Nielsen path or an exceptional path then the interior of µ0
is an increasing union of pre-trivial paths by [FH11, Remark 4.2 and Lemma 2.11(2)]
and so by [FH11, Lemma 4.11(2)] is contained in a single term µ of the complete
splitting of R. Obviously µ is not a single edge and is not contained in a zero stratum
so it must be either an indivisible Nielsen path or an exceptional path. Since v is the
initial endpoint of some term in the complete splitting of R and w comes after v, it
follows that v is not contained in the interior of µ and so µ ⊂ R0 . The symmetric
argument therefore applies to show that µ is contained in a term of the complete
splitting of R0 and hence that µ = µ0 as desired. If µ0 is either a single edge or is
a maximal subpath in a zero stratum and µ0 is not a term in the complete splitting
of R then µ0 is properly contained in a term µ of R that is an indivisible Nielsen
path or an exceptional path. But this violates the hard splitting property [FH11,
Lemma 4.11(2)] for the complete splitting of R0 (applied to its finite completely split
subpaths) and the fact that the interior of µ is the increasing union of pre-trivial
paths. Thus µ0 is a term in the complete splitting of R and we are done.
Definitions 6.2. Suppose that f : G → G is a CT, that x ∈ G, that σ ⊂ G is
a non-trivial completely split path connecting x to f (x) and that the turn at f (x)
determined by σ̄ and f# (σ) is legal. The ray R = σ · f# (σ) · f#2 (σ) · . . . satisfies
f# (R) ⊂ R and the given splitting of R has a refinement that is a complete splitting
by [FH11, Lemma 4.11]; we say that R is generated by σ.
If E is a non-fixed edge of G whose initial direction is fixed then f (E) = E · σ for
some σ as above. The ray RE = E · σ · f# (σ) · f#2 (σ) · . . . is the eigenray determined by
E. Note that we are not requiring that the initial vertex of E be principal (as we did
in Section 3.3) or that E is non-linear and NEG so we are using the term eigenray
a little more generally than is sometimes the case. We will need this inclusiveness
35

in the proof of Lemma 6.4. For the same reason we assume that each isolated fixed
point for f is a vertex.
Lemma 6.3. Suppose that f : G → G is a CT and that σ and σ 0 are completely split
non-Nielsen paths generating rays R and R0 respectively. Then there is an algorithm
to decide if the rays R and R0 have a common terminal subray and if so to find
initial subpaths τ ⊂ R and τ 0 ⊂ R0 that terminate at splitting vertices of R and R0
respectively and whose complementary terminal subrays are equal. Equivalently we
find splitting vertices v ∈ R and v 0 ∈ R0 such that terminal subrays of R and R0
initiating at v and v 0 are equal (as edge paths).
Proof. Let V = {v0 , v1 , . . .} be the set of splitting vertices for R ordered so that vi−1
and vi are the endpoints of the ith term in the complete splitting. By construction,
f (V) ⊂ V. For each i ≥ 0, let σi ⊂ R be the path connecting vi to f (vi ) and let
`i = |σi | be the number of edges in σi ; in particular, σ = σ0 . Note that σi generates
the terminal subray of R that begins with vi . Define V 0 , σj0 and `0j similarly using σ 0
and R0 in place of σ and R. It is obvious that R and R0 have a common terminal
subray if σi = σj0 for some i and j. (Namely, the subrays of R and R0 initiating at
vi ∈ V 0 and vj0 ∈ V 0 respectively.) The converse follows from Lemma 6.1. Our goal
then is to either find i and j such that σi = σj0 or to conclude that no such i and j
exist.
Let r [resp r0 ] be the maximal height of a term in the complete splitting of σ [resp.
σ 0 ] that is not a Nielsen path. Since f (σ) and σ have a common endpoint, σ is not
entirely contained in a zero stratum. Thus any term τ in the complete splitting of
σ that is contained in a zero stratum is adjacent to a term that intersects the EG
stratum that envelops τ (Notation 2.11). Since this adjacent edge has at least one
non-fixed endpoint, it is neither an exceptional path nor a Nielsen path so must be
a single edge in that EG stratum. We conclude that Hr is not a zero stratum. It
follows that if µ is any height r term in the complete splitting of σ and if µ is not a
Nielsen path then the length of f#i (µ) goes to infinity with i; we say that µ is growing.
Note that r is the maximal height of a growing term in the complete splitting of any
σi and similarly for r0 and σj0 . Note also that for any given L > 0 one can find, by
inspection, M > 0 such that `i , `0j > L for all i, j ≥ M .
The first step in the algorithm is to check if r = r0 . If yes, then move on to step
two. If not then there do not exist i and j such that σi = σj0 so the algorithm stops
and outputs NO.
We may now assume that r = r0 . If Hr is NEG define K = 1. Otherwise Hr
is EG and we choose K so that for each edge E of Hr , f#K (E) contains at least C
edges of Hr where C is the constant of Lemma 4.4. Now define I to be the number of
terms in the complete splitting of σ · f# (σ) · . . . · f#K (σ) or equivalently so that i ≤ I
if and only if ṽi ∈ σ̃ · f˜# (σ̃) · . . . · f˜#K (σ̃). Define J to be the number of terms in the
complete splitting of σ 0 · f# (σ 0 ) · . . . · f#K (σ 0 ) or equivalently so that j ≤ J if and only
if ṽj0 ∈ σ̃ 0 · f˜# (σ̃ 0 ) · . . . · f˜#K (σ̃ 0 ).
36

Fix j. To check if σj0 = σi for some i we need only consider i < M where `i > `0j
for all i ≥ M . The symmetric argument implies that for any fixed i we can check if
σi = σj0 for some j. The second and final step of the algorithm is to decide if there
exists i ≤ I such that σi = σj0 for some j or if there exists j ≤ J such that σi = σj0
for some i. If not then the algorithm outputs NO. If yes then the algorithm outputs
YES and vi , vj0 .
It remains to prove that if R and R0 have a common subray then the algorithm
outputs YES in the second step. Suppose that R = ρR00 and R0 = ρ0 R00 where ρ ⊂ R
and ρ0 ⊂ R0 are finite and R00 is a maximal common subray. Lift R = ρR00 ⊂ G
to R̃ = ρ̃R̃00 ⊂ G̃ and the initial segment σ ⊂ R to an initial segment σ̃ ⊂ R̃. Let
f˜ : G̃ → G̃ be the lift of f that takes the initial endpoint of σ̃ to the terminal
endpoint of σ̃ and note that R̃ = σ̃ · f˜# (σ̃) · f˜#2 (σ̃) · . . .. Since σ is not a Nielsen
path, |f#k (σ)| → ∞. It follows that the terminal endpoint P ∈ ∂Fn of R̃ is an
attractor for the action of ∂ f˜ and so is not fixed by any covering translation [GJLL98,
Proposition I.1]. In particular, f˜ is the only lift of f that fixes P . Lift R0 = ρ0 R00 to
R̃0 = ρ̃0 R̃00 and σ 0 to an initial segment σ̃ 0 of R̃0 . The uniqueness of f˜ implies that
R̃0 = σ̃ 0 · f˜# (σ̃ 0 ) · f˜#2 (σ̃ 0 ) · . . .. Let Ẽ 00 be the first height r edge crossed by R̃00 . There
0
exist unique k, k 0 ≥ 0 such that Ẽ 00 is crossed by f˜#k (σ̃) and by f˜#k (σ̃ 0 ). We may
assume without loss that k 0 ≥ k. By Lemma 6.1, it suffices to show that k ≤ K or
equivalently that ρ ⊂ σ̃ · f˜# (σ̃) · . . . · f˜K (σ̃).
If Hr is NEG then by the basic splitting property of NEG edges [BFH00, Lemma
4.1.4] there is a unique height r edge whose image under f˜k crosses Ẽ 00 . Since both
0
σ̃ and f˜#k −k (σ̃ 0 ) cross such an edge, their intersection is non-empty. It follows that
ρ̃ ⊂ σ̃1 so we are done.
0
If Hr is EG then there exist x̃ ∈ σ̃ and x̃0 ∈ f˜#k −k (σ̃ 0 ) such that f˜k (x̃) = f˜k (x̃0 ).
The path τ̃ from x̃ to x̃0 decomposes as a concatenation of subpaths α̃β̃ −1 where α̃ ⊂ ρ̃
and β̃ ⊂ ρ̃0 . By construction f˜#k (τ̃ ) is trivial so in particular τ is not weakly attracted
to Λ+ . Lemma 4.4 implies that α̃ does not cross C edges that project to Hr and so
does not contain f˜#K (Ẽ) for any edge Ẽ that projects to Hr . Since σ̃ crosses such an
Ẽ it follows that α̃ and hence ρ̃ is contained in σ̃ · f˜# (σ̃) · . . . · f˜K (σ̃) as desired.

6.2

Finding a Fixed Point

The proof of Theorem 1.1 begins with an arbitrary relative train track map f : G → G
and filtration and modifies f : G → G and the filtration so that it satisfies more and
more of the CT properties. Certain steps in this process are inductive and involve
consideration of a, not necessarily core, component of a filtration element. Lemma 6.4
below is applied in that context. The reader will note that essentially all of the
arguments take place in a core filtration element.
We state our next result in terms of a lift f˜ : G̃ → G̃ of f : G → G and fixed
points for f˜. We could just as easily have stated it in terms of finite paths ρ ⊂ G as

37

described in Section 3.1 but it seems more natural to work with lifts.
Following Definition 6.2 we say that a completely split path σ̃ ⊂ G̃ generates a
completely split ray R̃ if R̃ = σ̃ · f˜# (σ̃) · f˜#2 (σ̃) · . . .. As we have seen, f˜# (R̃) ⊂ R̃ and
f˜ maps the set of splitting vertices for R̃ into itself.
Lemma 6.4. Suppose that f : G → G is a homotopy equivalence of a connected finite
graph, that ∅ = G0 ⊂ G1 ⊂ . . . ⊂ GK = G is an f -invariant filtration and that there
is a connected core filtration element Gr such that f Gr is a CT and such that for
each r < s ≤ K, Hs is a single non-fixed edge Es satisfying the following properties.
(1) The terminal endpoint of Es is contained in Gr and the initial vertex of Es has
valence one in G.
(2) f (Es ) = Es · us where us is a completely split closed path whose endpoint is
principal for f Gr .
(3) f : G → G satisfies (Linear Edges) and (NEG Nielsen Paths).
Then there is an algorithm that takes a lift f˜ : G̃ → G̃ of f : G → G as input
and determines if Fix(f˜) is non-empty. If it is non-empty then the output of the
algorithm is an element of Fix(f˜). If it is empty then the output of the algorithm
is a completely split path σ̃ ⊂ G̃r that generates a completely split ray R̃ ⊂ G̃r .
Moreover, if Fix(f˜) = ∅ and if the projection σ ⊂ Gr of σ̃ is not a Nielsen path then
FixN (∂ f˜) = FixN (∂(f˜ G̃r )) = {P } where P is the endpoint of R̃ and P is not the
endpoint of an axis of a covering translation.
Proof. We dispense with the moreover statement first. Suppose that Fix(f˜) = ∅ and
that σ is not a Nielsen path. Then |f#k (σ)| → ∞ and [GJLL98, Proposition I.1]
implies that the terminal endpoint of R̃ = σ̃ · f˜# (σ̃) · f˜#2 (σ̃) · . . ., which is evidently
fixed by ∂ f˜, is an attractor for the action of ∂ f˜, is contained in FixN (∂ f˜) and is not
the endpoint of an axis of a covering translation. Since Fix(f˜) = ∅, [FH11, Corollary
3.16] implies that P is the only attractor in FixN (∂ f˜). If there were another point
in FixN (∂ f˜) then it would be the endpoint of the axis of a covering translation that
commuted with f˜ and the translates of P would be additional attractors in FixN (∂ f˜).
Thus FixN (∂ f˜) = {P }.
We now turn to the algorithm. Following the proof of [BFH00, Proposition 5.4.3],
we say that for each non-fixed vertex ṽ ∈ G̃r , the initial edge of the path from ṽ to
f˜(ṽ) is preferred by ṽ. If both Ẽ and Ẽ −1 are preferred by their initial vertices then
some sub-interval of Ẽ is mapped over itself by f˜ and so contains a fixed point.
Consider the following (possibly infinite) method for finding either a fixed point
in G̃ or a ray whose terminal endpoint is an element of FixN (∂ f˜). Choose any vertex
ṽ0 ∈ G̃r . If ṽ0 is not fixed, let Ẽ0 be the edge preferred by ṽ. If Ẽ0−1 is preferred
by the terminal vertex of Ẽ0 then Ẽ0 contains a fixed point that we can find by
inspection (Section 3.4). Otherwise, let Ẽ1 be the edge preferred by the terminal
38

vertex of Ẽ0 . Repeat this to either find a fixed point in Ẽ1 or define Ẽ2 and so on. If
this process does not terminate by finding a fixed point then the ray R̃ṽ0 = Ẽ1 Ẽ2 . . .
that it produces converges to a point in ∂ F̃n that is evidently fixed and not repelling
so is contained in FixN (∂ f˜). For each m ≥ 0, let σ̃m be the path connecting the
initial endpoint of Ẽm to its f˜-image.
Step 1 of the algorithm: Modify the above process by stopping not only if Ẽm
contains a fixed point but also if σ̃m is completely split and the turn between σ̃m and
f˜# (σ̃m ) is legal.
To see that this modified process stops in finite time, it suffices to show that
if the original process produces a ray R̃ṽ0 then at least one of the σ̃m ’s has the
desired properties. We verify this by following (and tweaking) the proof of [BFH00,
Proposition 5.4.3].
Consider the subsequence {ṽi } of the set of vertices of R̃ṽ0 starting with ṽ0 and
inductively defined by letting p ≥ i be the largest integer such that the closest point
to f˜(ṽi ) in Ẽ0 Ẽ1 . . . Ẽp is the terminal endpoint of Ẽp and then taking ṽi+1 to be the
terminal endpoint of Ẽp . Equivalently, ṽi+1 is the nearest point in R̃ṽ0 to f˜(ṽi ).
Letting [ṽi , ṽi+1 ] be the path connecting ṽi to ṽi+1 , the key property of the ṽi ’s is
f˜# ([ṽi , ṽi+1 ]) ⊃ [ṽi+1 , ṽi+2 ]
For m ≥ 1, define
Ỹm = {ỹ ∈ [ṽ0 , ṽ1 ] : f˜i (ỹ) ∈ [ṽi , ṽi+1 ] ∀ 1 ≤ i ≤ m}
The obvious induction argument shows that f˜(Ỹm ) = [ṽm , ṽm+1 ] and in particular
that Ỹm is non-empty. The Ym ’s are a nested sequence of closed non-empty subsets
∞
of [ṽ0 , ṽ1 ] and so their intersection ∩∞
m=0 Ỹm is non-empty. Each element of ∩m=0 Ỹm is
contained in
X̃ = {x̃ : {x̃, f˜(x̃), f˜2 (x̃), . . .} is an ordered sequence of R̃ṽ0 }
In the first two paragraphs on page 68 of [BFH00] it is shown that X̃ ⊂ R̃ṽ0
contains a vertex ṽ that is the initial vertex of an irreducible edge. For sufficiently
large k, the paths µ̃ := [f˜k (ṽ), f˜k+1 (ṽ)] and ν̃ := [f˜k+1 (ṽ), f˜k+2 (ṽ)] are completely
split by [FH11, Lemma 4.25]. It follows, after increasing k if necessary, that the
initial directions of µ−1 and ν are periodic by Df . Since ṽ ∈ X̃, these directions are
distinct and so the turn they define is legal. Letting Em be the edge in R̃ṽ0 that begins
with f˜k (ṽ), we have found the desired σ̃m . (The proof of [BFH00, Proposition 5.4.3]
allows the possibility of subdividing at an endpoint of a periodic Nielsen path; in our
context, these points are already fixed vertices so no subdivision is required.) This
completes the proof that the first part of our algorithm stops in finite time.
If the first step of the algorithm produces a fixed point we are done and the
algorithm stops. Suppose then that the first step produces a path σ̃ = σ̃m as above.
39

Let P ∈ FixN (∂ f˜) be the terminal endpoint of the ray R̃ = σ̃ · f˜# (σ̃) · . . . generated
by σ̃. The hard splitting property [FH11, Lemma 4.11(2)] implies that R̃ is fixed
point free. If Fix(f˜) 6= ∅ then there exists a ray R̃0 with initial endpoint z̃ ∈ Fix(f˜),
terminal endpoint P and with interior disjoint from Fix(f˜). The initial edge Ẽ of R̃0
determines a fixed direction; this follows from [FH11, Lemma 3.16] if E ⊂ Gr and by
hypothesis if E ⊂ G \ Gr . Let RE be the eigenray determined by E (Definition 6.2),
let R̃Ẽ be the lift of RE with initial edge Ẽ and let P 0 ∈ FixN (∂ f˜) be the terminal
endpoint of R̃Ẽ . If P 6= P 0 then the line connecting P to P 0 would be a fixed point
free line in G̃r with endpoints in FixN (f˜) in contradiction to [FH11, Lemma 3.16].
Thus P 0 = P and the rays R̃ and R̃Ẽ = R̃0 have a common terminal subray.
If σ is a Nielsen path then E is a linear edge, f (E) = Ewd for some root-free
Nielsen path w that forms a circuit, RE = Ew∞ and R̃ is a ray in a line L̃ that
projects to w. It follows that that the terminal endpoint of Ẽ is contained in L̃. The
root-free covering translation that preserves L commutes with f˜. After translating by
some iterate of this covering translation we may assume that the terminal endpoint
of Ẽ is contained in any chosen lift w̃ of w in R̃. This analysis justifies the next two
steps of the algorithm.
Step 2 of the algorithm: Check if σ is a Nielsen path. If it is not, go to Step 3.
If it is, then the algorithm ends as follows. Consider the finite set of points that are
the initial vertex of a linear edge Ẽ with terminal endpoint in σ̃. If an element of this
set is contained in Fix(f˜) then that point is the output of the algorithm. Otherwise
conclude that Fix(f˜) = ∅.
We may now assume that σ is not a Nielsen path and hence that P is not fixed
by any covering translation. It follows that f˜ is the only lift of f that fixes P and
hence that f˜ fixes the initial endpoint of any eigenray that converges to P .
Step 3 of the algorithm : Apply Lemma 6.3 to the set of eigenrays (Definition 6.2)
for f , one by one, to decide if there is an eigenray RE that shares a terminal end with
R. If there is no such eigenray, then Fix(f˜) = ∅. Otherwise, we have an edge E, its
eigenray RE and decompositions R = τ R00 and RE = τ 0 R00 for some ray R00 . Let τ
be the lift of τ that begins with σ̃ and let τ̃ 0 be the lift of τ 0 that shares a terminal
endpoint with τ̃ . Equivalently, R̃ = τ̃ R̃00 and R̃Ẽ = τ̃ 0 R̃00 . Then the initial endpoint
of τ̃ 0 is fixed by f˜.

7

Upward induction and extension

The original construction of relative train track maps is by downward induction
through the strata, making it difficult to prove extension statements. In this paper, we construct CTs using upward induction.
Notation 7.1. Let F = {[F i ]} be a free factor system in Fn . A core graph K = ti Ki
is F-marked if each Ki is marked by F i , i.e. there is a rose R(F i ) whose fundamental
40

group is identified with F i and a homotopy equivalence R(F i ) → Ki .
Suppose φ ∈ Out(Fn ), K is F-marked, F is φ-invariant and h : K → K is a
homotopy equivalence that preserves components. We say that h is a topological
representative of φ|F if each induced map h Ki : Ki → Ki is a topological representative of φ F i . If each h Ki is a CT [and satisfying (Inheritance)] then we say that
h : K → K is a CT representing φ F [and satisfying (Inheritance)]. See Section 1
for the definition of (Inheritance).
A topological representative f : G → G of φ is an extension of h : K → K if
there is an embedding K → G respecting markings such that the following diagram
commutes.
h
K ............................................ K
...
...
...
...
...
...
..
..........
.

G

f

............................................

...
...
...
...
...
...
..
..........
.

G

In this situation we also say that f extends h and that h extends to Fn .
Interpreted in this language, the proof of Lemma 2.6.7 of [BFH00] shows that
every restriction extends.
Lemma 7.2. Every topological representative for φ F extends to Fn .
Remark 7.3. The proof of Lemma 2.6.7 assumes the property that each h Ki fixes
a point. This assumption is not necessary. However, we will only use Lemma 7.2
when h|K is a CT and so this property holds.
As mentioned, we want a construction of CTs that proceeds by upward induction.
Our main tool will be a relative version of Theorem 1.1.
Theorem 7.4 ( Extension). Suppose that φ ∈ Out(Fn ) is rotationless, that C is a
nested sequence (F = F0 ) @ F1 @ F2 @ . . . @ (Fm = {[Fn ]}) of φ-invariant free
factor systems and that h : K → K is a CT representing φ F. Then there is an
algorithm that produces a CT f : G → G and filtration that represents φ, extends
h : K → K and such that each element of C is realized by a core filtration element; if
h : K → K satisfies (Inheritance) then f : G → G satisfies (Inheritance).
Theorem 1.1 is the special case of Theorem 7.4 in which F = ∅.
The filtration we start with might not be reduced so our algorithm will have to
discover reductions, if they exist, as it proceeds.
Theorem 7.5 (Extend or Reduce). Suppose that φ ∈ Out(Fn ) is rotationless, that
F is a φ-invariant free factor system and that h : K → K is a CT that represents
φ F [and satisfies (Inheritance)]. Then there is an algorithm that either produces a
CT f : G → G that represents φ [satisfies (Inheritance)] and extends h : K → K or
finds a φ-invariant proper free factor system F 0 that properly contains F.

41

Proof of Theorem 7.4 given Theorem 7.5: The proper length of C is the number of
inclusions that are proper. If C 0 is a sequence of inclusions of φ-invariant free factor
systems and if each element of C is an element of C 0 then we say that C 0 is an extension
of C. Define L(C) ≥ 0 to be the maximal proper length of some C 0 extending C. The
proof is an induction on L(C). If L(C) = 0 then F = {[Fn ]} and the statement is
vacuous. If L(C) = 1 the statement follows from Theorem 7.5. Assume then that
L(C) ≥ 2. We may assume that the inclusions F @ Fm−1 @ {[Fn ]} are proper.
Step 1 (Extend h to Fm−1 ): Each component [F ] of Fm−1 induces the φ F invariant nested sequence C|F of free factor systems in F given by
(F|F = F0 |F ) @ F1 |F @ F2 |F @ . . . @ (Fm−1 |F = {[F ]})
where Fi |F is the union of the components of Fi that conjugate into F . Clearly
L(C|F ) < L(C). Let K(F ) be the union of the components C of K such that [C] is
conjugate into F and so [K(F )] = F|F . By induction we can algorithmically produce
a CT and filtration that represents φ F , extends the restriction of h to K(F ) and
such that each element of C|F is realized by a core filtration element; if h : K → K
satisfies (Inheritance) then so does this CT. The disjoint union of these CTs is a CT
[satisfying (Inheritance) if h does] representing φ Fm−1 such that each element of
F @ F1 @ · · · @ Fm−1 is represented by a core filtration element.
Step 2 (Further extend to Fn ): The sequence Fm−1 @ {[Fn ]} also has proper
length less than L(C). Hence by induction we can algorithmically produce a CT that
represents φ and extends the restriction of φ to Fm−1 found in Step 1; if h : K → K
satisfies (Inheritance) then so does this CT.
To prove Theorem 1.1, it remains to prove Theorem 7.5. The proof of Theorem 7.5
is given in Section 8.

8

Proof of Theorem 7.5

The proof of Theorem 7.5 is carried out in Sections 8.1 and 8.2. In both cases, φ, F
and h : K → K are as in the statement of the theorem.

8.1

The one-edge extension case

In this section we assume that F @ {[Fn ]} is a one-edge extension, meaning that
either F = {[F1 ]} where F1 has rank n − 1 or F = {[F1 ], [F2 ]} where the ranks of F1
and F2 add to n. In this case, there is a marked graph G obtained from K by adding a
single topological edge E and there is a topological representative g : G → G of φ that
agrees with h on K and satisfies g(E) = ūEv or g(E) = ūĒv for some possibly trivial
paths u, v ⊂ K by [BFH00, Corollary 3.2.2]. We first complete the proof assuming
that g(E) = ūEv and then apply CT theory to show that the g(E) = ūĒv case does
not happen.
42

If u and v are both trivial then g(E) = E and g satisfies all the properties of a
CT except that K ⊂ G might not be reduced. Check (using Lemma 4.5 and (NEG
Nielsen Paths)) if there is a Nielsen path β ⊂ K connecting the terminal endpoint of
E to the initial endpoint of E. If not, then K ⊂ G is reduced by Lemma 4.12 and g is
a CT. If yes, then Eβ is a closed Nielsen path and the free factor system {[K], [Eβ]}
is properly contained between [K] and [G].
Suppose next one of u and v is trivial and that the other is not. The cases are
symmetric so we assume that u is trivial and v is non-trivial. Let C be the component
of K that contains v. If C has rank one then C has a single fixed edge e and single
vertex w and g(E) = Eed for some d 6= 0. There are two subcases. If w is also the
initial vertex of E then n = 2 and G has only two edges, E and e. (NEG Nielsen
Paths) follows from the basic splitting property for NEG edges [BFH00, Lemma 4.1.4].
Lemma 4.12 implies that [K] @ Fn is reduced and so (Filtration) is satisfied. The
remaining CT properties are clear so g is a CT. If w is not the initial vertex of e then
g is not a CT because w is not principal. In this case we redefine g so that it fixes E
and is unchanged on K. The resulting homotopy equivalence f : G → G is homotopic
to g and so is still a topological representative of φ. We are now back in the case that
u and v are trivial. Lemma 4.12 implies that K ⊂ G is reduced so f : G → G is a
CT.
We assume now that C has rank at least two and we apply [FH11, Step 5 pages
91–93]. Choose a lift Ẽ of E, let g̃ : G̃ → G̃ be the lift of g that fixes the initial
endpoint of Ẽ, let Γ ⊂ G̃ be the component of the full pre-image of C that contains
the terminal endpoint of Ẽ and let h̃ = g̃ Γ : Γ → Γ. To make this step algorithmic,
we apply Lemma 6.4 to either find a fixed point for h̃ or to conclude that h̃ is fixed
point free and find a completely split path σ̃ that generates a completely split ray R̃.
No algorithm for this was given in the original proof.
The remainder of [FH11, Step 5 pages 91–93] can be applied as written in [FH11].
This is a sliding operation that changes the way that E is attached to C. It may be
that E becomes a fixed edge for the new modified g : G → G. In this case, we go back
to the fixed edge case described above and proceed from there. If E is not fixed after
the sliding operation then all of the CT properties are satisfied except that K ⊂ G
might not be reduced. The proof now concludes by applying Lemma 4.12 and [FH11,
Step 5 page 91] to conclude that K ⊂ G is reduced.
The final case is that both u and v are non-trivial. Subdivide E = Ē1 E2 where
g(E1 ) = E1 u and g(E2 ) = E2 v. Let Ci be the component of K that contains the
terminal endpoint of Ei . If C1 = C2 has rank one, then C1 = C2 has a single fixed
edge e and single vertex w and g(Ei ) = Ei edi for some d1 , d2 6= 0. Define f by f (e) = e
and f (E) = Eed2 −d1 and note that f is homotopic to g and so is still a topological
representative of φ. If d1 6= d2 then f is a CT. If d1 = d2 then {[e], [E]} is a φ-invariant
free factor system that is properly contained between [K] and [Fn = F2 ].
If C1 6= C2 both have rank one then the identity map of G is homotopic to g and
is a CT. We may now assume, after interchanging E1 and E2 if necessary that C2 has
43

rank at least two. If C1 has rank one then g is homotopic to g 0 that agrees with h on
K and that satisfies g 0 (E) = Ev so we are reduced to a previous case.
The remaining case is that both C1 and C2 have rank at least two. The edges E1
and E2 are modified in the same way that E was modified in the case that C had
rank at least two. Namely, follow [FH11, Step 5 pages 91–93] and apply Lemma 6.4
to make the construction algorithmic. The edges E1 and E2 are considered one at a
time so when E2 is considered the subgraph it is being attached to is K ∪ E1 and not
K (This accounts for the hypotheses of Lemma 6.4 being what they are.) It may be
that after sliding E2 , both of its endpoints are attached to the initial vertex of E1 ;
see Example 4.10.
This completes the proof in the case that g(E) = ūEv. Suppose now that g(E) =
ūĒv. Applying the previous case to h = g 2 representing θ = φ2 , we see that there is a
CT representing θ and extending h2 : K → K. As shown in the first two paragraphs
of [FH11, Section 5.1], there is a line γ ⊂ G whose edge path contains one copy of
E and zero copies of Ē and such that some (and hence every) lift γ̃ has endpoints in
FixN (Θ) for some Θ ∈ P(θ). Since φ is rotationless, there exists Φ ∈ P(φ) such that
FixN (Φ) = FixN (Θ). Thus γ is φ-invariant which contradicts the fact that the edge
path for h(γ) crosses Ē once and E zero times. We conclude that this case does not
happen.

8.2

The multi-edge extension case

We assume in this section that F @ {Fn } is not a one-edge extension. If f : G → G
represents φ and extends h : K → K then the core filtration element that is identified
with K will be denoted Gr . In particular, [Gr ] = F.
Step 1:
There is an algorithm that either produces a relative train track map
extending h : K → K or finds a proper φ-invariant free factor system F 0 that properly
contains F. Moreover, in the former case, either there are no EG strata above the
core filtration element Gr that is identified with K or the top stratum HN of G is the
only EG stratum above Gr .
We can not simply apply the relative train track map algorithm of Theorem 2.2.
That algorithm was by downward induction through the filtration and so made no
effort to leave lower filtration elements untouched. We say that an algorithm is K-safe
if it preserves the property of extending h : K → K.
Lemma 8.1. The algorithms of Lemma 2.6 and Lemma 2.8 are K-safe.
Proof. The algorithms use only subdivision, folding, valence one homotopies and
valence two homotopies applied to edges above K and so are K-safe.
The algorithm of Lemma 2.9 (which is really [BH92, Lemma 5.14]) is not entirely
K-safe. In order to isolate the part that is K-safe we introduce some notation and
recall the steps in the algorithm.
44

If Hs is an EG stratum of a topological representative then a non-trivial path
σ ⊂ Gs−1 with endpoints in Hs ∩ Gs−1 is called an inessential connecting path for Hs
if f# (σ) is trivial. If the EG stratum Hs satisfies (RTT-i) then it satisfies (RTT-ii) if
and only if there are no inessential connecting paths for Hs .
An inessential connecting path σ for Hs is ‘collapsed’ as follows. Choose a turn in
σ whose two directions have the same image under Df . This exists because f# (σ) is
trivial. Then fold initial segments of these edges and tighten the new map if necessary
to ‘shorten’ σ. After finitely many such moves σ is completely folded away and the
endpoints of σ are identified to a single vertex thereby reducing the cardinality of
Hs ∩ Gs−1 .
If σ ⊂ Gs−1 is disjoint from Gr , for example if σ is contained in a contractible
component of Gs−1 , then collapsing σ is K-safe. We record this fragment of Lemma 2.9
as Lemma 8.3 after adding one more piece of notation.
Notation 8.2. An EG stratum Hs satisfies (partial RTT-ii) if the contractible components of Gs−1 do not contain any inessential connecting paths.
Lemma 8.3. Suppose that f : G → G is a bounded topological representative of φ that
extends h : K → K and that Hs is an EG stratum that does not satisfy (partial RTTii). Then there is a K-safe algorithm to construct a bounded topological representative
f 0 : G0 → G0 of φ such that
(1) Λ(f ) = Λ(f 0 )
(2) There is a bijection Hj ↔ Hj0 0 between the EG strata of f and the EG strata of
f 0 such that:
(a) relative height is preserved; i.e. j < k if and only if j 0 < k 0 .
(b) |Hs0 0 ∩ G0s0 −1 | < |Hs ∩ Gs−1 |
(c) if Hs satisfies (RTT-i) then Hs0 0 satisfies (RTT-i).
Remark 8.4. Note that Lemma 8.3 is not exactly parallel to Lemma 2.9. We will
only apply Lemma 8.3 with Hs being the first EG stratum above K and we will not
be concerned with preserving properties of higher EG strata.
The following corollary takes us as far as we can go using just the techniques of
Theorem 2.2.
Corollary 8.5. Given a bounded topological representative f : G → G of φ that
extends h : K → K, there is an algorithm that constructs a bounded topological
representative f 0 : G0 → G0 of φ that extends h : K → K such that Λ(f 0 ) ≤ Λ(f )
and such that either there are no EG strata above K or the first EG stratum above
K satisfies (RTT-i), (RTT-iii) and (partial RTT-ii).

45

Proof. If there are no EG strata above K then we are done. Otherwise, apply
Lemma 2.6 and Lemma 8.1 to produce a bounded topological representative (still
called f : G → G) of φ that extends h : K → K whose first EG stratum above K satisfies (RTT-i). If that stratum does not also satisfy (partial RTT-ii), apply Lemma 8.3
to produce a new bounded topological representative (still called f : G → G) of φ
whose first EG stratum above K still satisfies (RTT-i). Item (b) of Lemma 8.3 guarantees that after finitely many applications of Lemma 8.3, we arrive at f : G → G whose
first EG stratum above K satisfies (RTT-i) and (partial RTT-ii). Apply Lemma 2.4
to check if the first EG stratum above K satisfies (RTT-iii). If yes, we are done.
Otherwise apply Lemma 2.8 and Lemma 8.1 to produce a bounded topological representative f 0 : G0 → G0 of φ that extends h : K → K with Λ(f 0 ) < Λ(f ). Then start
over again with f 0 : G0 → G0 replacing the original f : G → G. Since every decreasing sequence Λ(f ) > Λ(f 0 ) > . . . is finite (Definition 2.3), this process produces the
desired f : G → G in finite time.
Before introducing the new move necessary to achieve (RTT-ii) in a K-safe manner, we prove a lemma that will simplify the situation in which the new move is
needed.
Lemma 8.6. Suppose that f : G → G is a bounded topological representative of φ
that extends K and that Hs , s > r, is an EG stratum that satisfies (RTT-i), (RTT-iii)
and (partial RTT-ii). Then [Gr ] = F is properly contained in [Gs ]. In particular, if
Gs 6= G then [Gs ] is a proper φ-invariant free factor system that properly contains F.
Proof. It suffices to show that there is a line in Gs that crosses an edge in Hs and
for this it suffices to show that if a vertex v ∈ Hs is either disjoint from Gs−1 or is
contained in a contractible component of Gs−1 then there is path µ = Ē1 τ E2 ⊂ Gs
where E1 , E2 are edges in Hs and τ is a possibly trivial path that contains v and
does not contain an edge in Hs . Since Hs is an EG stratum, the cardinality of
f −p (v) ∩ Hs goes to infinity with p. Choose p ≥ 1 and a point x in the interior
of an edge E ⊂ Hs such that f p (x) = v. We may assume without loss that either
f (x) ∈ Gs−1 or that f (x) is a vertex in Hs . Subdivide E into ‘edgelets’ that are
mapped by f to single edges in G. There is an edgelet subpath e1 . . . et such that
f (ej ) is an edge in Hs if and only if j = 1 or j = t and such that either t > 2 and
x ∈ e2 . . . et−1 or t = 2 and x is the common endpoint of e1 and e2 . If t = 2 then
(f (ē1 ), f (e2 )) is a legal turn in Hs by (RTT-iii) and so Df p−1 (f (ē1 )) and Df p−1 (f (e2 ))
are distinct edges in Hs based at v and we are done (with τ being trivial). If t > 2 then
τ 0 = f (e2 ) . . . f (et−1 ) is a non-trivial path in Gs−1 with endpoints in Hs ∩ Gs−1 . In
particular, f (x) ∈ Gs−1 . It follows that v = f p (x) ∈ Gs−1 and hence (by hypothesis)
v is contained in a contractible component of Gs−1 . This in turn implies that each
of τ 0 , f# (τ 0 ), . . . , f#p−1 (τ 0 ) is contained in a contractible component of Gs−1 . Since
τ 0 is a non-trivial path in Gs−1 with endpoints in Hs ∩ Gs−1 , the same is true for
f# (τ 0 ), . . . , f#p−1 (τ 0 ) by (RTT-i) and the (partial RTT-ii) property. Property (RTT-i)
46

implies that Df p−1 (f (ē1 )) and Df p−1 (f (et )) are directions in Hs and again we are
done. This completes the proof of the lemma.
Notation 8.7. Let R be the set of bounded topological representatives f : G → G
of φ that extend h : K → K and such that the top stratum HN :
• is the only EG stratum above K
• satisfies (RTT-i), (RTT-iii) and (partial RTT-ii).
The failure of f : G → G in R to be a relative train track map is measured by
the number δ(f ) of directions in HN that are based at non-periodic vertices in noncontractible components of GN −1 .
We will only define the new move in this context.
Lemma 8.8. Suppose that f : G → G is an element of R and that δ(f ) > 0. Then
there is an algorithm to construct an element fˆ : Ĝ → Ĝ of R such that either:
(1) Λ(fˆ) < Λ(f ) or
(2) Λ(fˆ) = Λ(f ) and δ(fˆ) < δ(f )
Proof. Let Ap [resp. Anp ] be the set of periodic [resp. non-periodic] vertices of HN
that are contained in non-contractible components of GN −1 . Thus f permutes the
elements of Ap and each element of Anp is mapped by an iterate of f into Ap . By
hypothesis, Anp 6= ∅. Choose an element x ∈ Anp such that f (x) ∈ Ap . There is a
unique y ∈ Ap such that f (x) = f (y) and there is a unique inessential connecting
path ν connecting x to y. Choose an edge E ⊂ HN with initial endpoint x and
slide its initial endpoint along ν to y to produce a new topological representative
f 0 : G0 → G0 . The marked graph G0 is obtained from G by replacing E with an edge
E 0 with terminal endpoint equal to that of E and with initial endpoint y. Thus G \ E
can be viewed as a subgraph of both G and G0 . For each edge e ⊂ G \ E, the edge
path f 0 (e) is obtained from the edge path f (e) by replacing each copy of E with νE 0
and each copy of Ē with Ē 0 ν̄ and then tightening. The edge path f 0 (E 0 ) is obtained
from the edge path f# (ν̄E) = f# (ν̄)f (E) = f (E) by making the same replacements
as in the previous case and then tightening. It is clear that f GN −1 = f 0 GN −1
and that no edges in HN are cancelled during the tightening operation. It follows
that f 0 extends h : K → K, that the top stratum HN0 of G0 is the only EG stratum
above K, that Λ(f ) = Λ(f 0 ) and that f 0 satisfies (partial RTT-ii). By construction,
δ(f 0 ) = δ(f ) − 1. If the initial direction determined by E is not in the image of Df
then HN0 satisfies (RTT-i). If HN0 also satisfies (RTT-iii) then fˆ = f 0 satisfies (2).
Otherwise, we apply Lemma 2.8 and Lemma 8.1 to produce fˆ satisfying (1).
If the initial direction determined by E is in the image of Df then HN0 does not
satisfy (RTT-i). (For example, if Df (e) = E then f 0 (e) begins with νE 0 .) In this
case, we perform a core subdivision producing a new map f 00 : G00 → G00 . (Continuing
47

with the example, e = e1 e2 where f 00 (e1 ) = ν and f 00 (e2 ) begins with E 0 .) There is
one subdivision point for each direction in HN that is mapped by some iterate of Df
to E. If an edge e is subdivided into e1 e2 then e1 is a zero stratum for f 00 and e2
replaces e as an edge in the top EG stratum. (It may be that the initial and terminal
directions of e are both eventually mapped to E and so e is ultimately subdivided
into two zero strata and one edge in the top EG stratum.) The contribution of e2 to
δ(f 00 ) balances the contribution of e to δ(f 0 ) so δ(f 00 ) = δ(f 0 ) < δ(f ). If (RTT-iii) is
satisfied then fˆ = f 00 satisfies (2). Otherwise, we apply Lemma 2.8 and Lemma 8.1
to produce fˆ satisfying (1).
Step 1 can now be completed as follows. Start with any bounded topological
representation of φ that extends h : K → K (Lemma 7.2). Apply Corollary 8.5
to produce a bounded topological representative f 0 : G0 → G0 of φ that extends
h : K → K such that Λ(f 0 ) ≤ Λ(f ) and such that either there are no EG strata above
K or the first EG stratum Hs0 0 above K satisfies (RTT-i), (RTT-iii) and (partial RTTii). In the former case, f 0 is a relative train track map and we are done so assume the
latter holds. If Hs0 0 is not the top stratum then (Lemma 8.6) we have found a proper
φ-invariant free factor system that properly contains F and we are done. We may
therefore assume that f 0 : G0 → G0 is an element of R. If δ(f 0 ) = 0 then f 0 : G0 → G0
is a relative train track map and we are done. Otherwise, apply Lemma 8.8 to produce
f 00 : G00 → G0 with either Λ(f 00 ) < Λ(f 0 ) ≤ Λ(f ) or δ(f 00 ) < δ(f 0 ). In the former case,
we start all over. This can only happen a finite number of times so we may assume
that we are in the case that δ(f 00 ) < δ(f 0 ). After applying Lemma 8.8 finitely many
times, we arrive a relative train track map and are done.
Step 2: Modify f : G → G from Step 1 so that the conclusions of Theorem 2.12
are satisfied.
The algorithm for Step 2 is explicitly described in Subsection 3.4 and in [FH11,
pages 18–23]. Each move effects only strata above Gr and so is K-safe. For future
reference we note that the number of edges in each EG stratum and the number of
indivisible Nielsen paths of EG height are not increased in Step 2. This ends Step 2.
Going forward, we may now also assume (with justification below) that:
(i) f : G → G is rotationless.
(ii) F ⊂ {[Fn ]} is irreducible.
(iii) there are no periodic strata above Gr .
(iv) every indivisible periodic Nielsen path ρ of EG height has period one.
(v) HN is EG and aperiodic, meaning that some iterate of its transition matrix is
positive.

48

Let f : G → G be as in Step 2. Item (i) follows from [FH11, Proposition 3.29].
Applying the algorithm of Proposition 4.9, we can either find a reduction of F ⊂
{[Fn ]}, in which case we are done, or conclude that F ⊂ {[Fn ]} is irreducible. We
may therefore assume that (ii) is satisfied. Item (iii) follows from (ii) and property
(P) of Theorem 2.12.
If there are no EG strata above Gr then each stratum Hj above Gr is non-periodic
NEG by (iii) and property (Z) of Theorem 2.12. Item (i) and property (NEG) of
Theorem 2.12 then imply that each Hj is a single edge Ej with terminal endpoint
in a core filtration element of height less than j. By property (F) of Theorem 2.12,
the core of each filtration element is a filtration element. Letting Gt be the first
core filtration element above Gr , it follows that [Gr ] @ [Gt ] is a one-edge extension.
By hypothesis, [Gr ] @ [GN ] is not a one-edge extension. We have therefore found
a reduction in contradiction to (ii). We conclude that HN is EG and is the only
irreducible stratum above Gr (recall the output of Step 1).
We need only check (iv) for an indivisible periodic Nielsen path ρ of height N . Any
such ρ begins and ends with edges in HN by [BH92, Lemma 5.11]. It follows that the
endpoints of ρ are incident to at least one periodic direction in HN and so are principal
by Definition 3.5. Item (iv) therefore follows from (i) and [FH11, Proposition 3.29].
Item (i) and [FH11, Lemma 3.19] imply that there are fixed directions in HN which
in turn implies that HN is aperiodic so (v) is satisfied.
Step 3: Modify f : G → G from Step 2 to produce a relative train track map that
satisfies (EG Nielsen Paths).
An algorithm for Step 3 is given in [FH11, pages 87–89] but it is not entirely
K-safe because it makes use of the ‘collapsing inessential connecting paths’ move in
the relative train track map algorithm. If we carry out this collapse as described in
Step 1 above rather than as described in [BH92] then the algorithm becomes K-safe
and we can use it to complete Step 3. For the readers convenience, we summarize
this algorithm and point out the one place where the K-safe modification occurs.
Remark 8.9. The algorithm of [FH11] applies results from [BH92, Sections 3 and 5]
and [BFH00, Sections 5.2 and 5.3]. Section 5.3 of [BFH00] has the global hypothesis
that HN is a geometric stratum. That hypothesis is not used in any of the results
cited so our conclusions also hold in the non-geometric case. Most of the results cited
ultimately derive from Section 5 of [BH92] where there is no assumption that HN is
geometric.
By [BH92, Lemma 5.11], every indivisible Nielsen path of height N has the form
ρ = ᾱβ where (α, β) is the only illegal turn of height N in ρ. Let E1 and E2 be the
first edges of α and β respectively. Depending on the edge paths f (E1 ) and f (E2 ),
there are three ways in which f : G → G and ρ can be modified to produce a new
relative train track map f 0 : G0 → G0 and indivisible Nielsen path ρ0 ⊂ G0 . In all three
cases, the number of edges in EG strata and the number of indivisible Nielsen paths

49

of EG height do not increase. The first and third are K-safe as described in [BH92]
and [BFH00]. To make the second K-safe we use Lemma 8.8 instead of Lemma 2.9.
If one of f (E1 ) and f (E2 ), say f (E2 ), is properly contained in the other then the
fold is said to be proper. There is a maximal path δ ⊂ GN −1 such that E2 δ is an initial
segment of β. In this case, f 0 : G0 → G0 is defined by folding an initial segment of
E1 with E2 δ; see [BFH00, Definition 5.3.2 and Lemma 5.3.3]. The indivisible Nielsen
path ρ0 is the tightened image of ρ in G0 under the folding map.
In the improper case, f (E1 ) = f (E2 ) and one begins the process [BFH00, Definition 5.3.4] by folding E1 and E2 to form a single new edge. If the edge following E1
in α or the edge following E2 in β belongs to HN then both of those edges belong
to HN and nothing more is required. Otherwise, the resulting map is not a relative
train track map and one must perform core subdivisions and collapses of inessential
connecting paths to restore the relative train track map properties. These should be
done as in Step 1 so as to be K-safe. In this case, the the number of edges in the EG
stratum decreases. See [BFH00, Lemma 5.3.5].
The third possibility, a partial fold, is that the maximal common subpath of f (E1 )
and f (E2 ) is proper in both edge paths. It follows [BH92, page 25] that α = E1 and
β = E2 . Items (ii) and (v) and [BFH00, Lemma 5.1.7] imply that the endpoints of
ρ are distinct and that if both endpoints are contained in GN −1 then at least one of
them is contained in a contractible component of GN −1 [BFH00, Lemma 5.1.7]. Item
(iii) above implies that there are no invariant contractible components of GN −1 and
we conclude that at least one of the endpoints of ρ is disjoint from GN −1 . In this
case, do not perform a standard fold but rather entirely identify E1 and E2 to form
a new graph G0 with an induced map f 0 : G0 → G0 . Since the turn (α, β) is not taken
by f (E) for any edge E, the image in G0 of f (E) is already tight and f 0 : G0 → G0
is a topological representative. It is immediate from the construction that (RTT-i) is
preserved. Since at least one of the endpoints of ρ is disjoint from GN −1 , (RTT-ii) is
also preserved. As argued in the proof of [BFH00, Lemma 5.2.4], Λ0 = Λ so Lemma 2.8
and Lemma 8.1 imply that (RTT-iii) is satisfied and f 0 : G0 → G0 is a relative train
track map. By construction (see also the proof of [BFH00, Lemma 5.2.4]) the number
of indivisible Nielsen paths with EG height has been decreased.
Since each of these operations begins and ends with a relative train track map and
an indivisible Nielsen path, we can iteratively fold to produce a sequence of relative
train track maps and indivisible Nielsen paths. Let C(f ) be the sum of the entries in
the transition matrix for f . This gives an upper bound for the number of elementary
folds in a Stallings factorization of f : G → G. If the first C(f ) folds encountered are
proper then f satisfies (EG Nielsen Paths); see [FH11, Lemma 4.33 and Remark 4.34]
and the proof of [BFH00, Lemma 5.3.6]. Otherwise, one encounters either a partial
or an improper fold in which case either the number of edges in EG strata or the
number of indivisible Nielsen paths of EG height decreases and we start over. Since
these numbers never increase, this algorithm terminates in finite time.
At the end of Step 3, f : G → G satisfies (EG Nielsen Paths). If the relative train
50

track map that was the input to Step 3 did not satisfy (EG Nielsen Paths) then either
the number of edges in an EG stratum decreased or the number of indivisible Nielsen
paths of EG height decreased during Step 3. Throughout the remaining steps, the
number of edges in each EG stratum and the number of indivisible Nielsen paths of
EG height are never increased. As a result, we need not verify the (EG Nielsen Paths)
after each step. If it fails at some point, go back to Step 3 and start again. This can
only happen finitely many times so does not prevent the process from terminating.
Step 4: If the relative train track map produced by Step 3 does not satisfy the
conclusions of Theorem 2.12 return to Step 2. As just noted, changes are required in
Step 3 only a finite number of times so Step 4 is a finite process.
Step 5: (Rotationless), (Filtration), (Zero Strata) and (Periodic Edges).
The first two properties follow from [FH11, Proposition 3.29] and Theorem 2.12
respectively. (Zero Strata) is arranged by the K-safe tree replacement moves described
in [FH11, Step 3]. (Periodic Edges) follows from the assumption that f Gr is a CT
and item (c) above.
Step 6: Modify f : G → G from Step 5 so that it satisfies (Vertices), (Linear
Edges) and (NEG Nielsen Paths). Additionally, the modified f : G → G satisfies
(Completely Split) on all NEG edges.
By property (Z) of Theorem 2.12 there is an irreducible stratum Hp such that
each stratum between Hp and HN is a zero stratum that is a component of GN −1 .
The edges E1 , . . . , Ep of Gp \ Gr are non-fixed NEG edges with terminal endpoints in
Gr and initial endpoints that have valence one in GN −1 . The proof of this assertion is
essentially the same as the proof of (v) and is left to the reader. The three conditions
to be achieved depend only on the NEG edges Ei . Since f : G → G is rotationless
and satisfies Theorem 2.12, f (Ei ) = Ei ui for some ui ⊂ Gr . By item (c) above, ui is
non-trivial.
Suppose that C is a rank one component of Gr and that the unique vertex w of
C is the terminal endpoint of E 1 , . . . , E q ⊂ {E1 , . . . , Ep }. Then C has a single edge
e and f (E j ) = E j edj for some dj 6= 0. If w is not the endpoint of an edge in HN
then redefine f on the E j ’s by f (E j ) = E j edj −d1 . The new map still represents φ and
none of our established properties are lost. The edge E 1 is now fixed and so can be
collapsed. After these moves, w is the endpoint of at least one edge in HN and so is
principal for f . We assume now that the unique vertex of each rank one component
of Gr is the endpoint of an edge in HN .
With that special case out of the way, one just applies [FH11, Step 5 pages 91–93],
applying Lemma 6.4 as described in Section 8.1.
Step 7: Modify f : G → G from Step 6 so that it satisfies (Completely Split).
We can apply [FH11, Step 6] without change.
This completes the proof of Theorem 7.5.

51

9

Finding Fix(Φ)

The goal of this section is to give another proof of the result of Bogopolski-Maslakova
[BM16] that there is an algorithm that, given Φ ∈ Aut(Fn ), computes Fix(Φ).

9.1

The periodic case

In this section, we examine the special case that Φ is periodic. The analysis in this
section will parallel that of the general case.
Recall from Section 3.1 that if G is a marked graph and ṽ ∈ G̃ is a lift to the
universal cover of v ∈ G then there is an isomorphism Jṽ : π1 (G, v) → T (G̃) given by
mapping [γ] to the covering translation T of G̃ that takes ṽ to the terminal endpoint
of the lift γ̃ of γ with initial endpoint ṽ.
Lemma 9.1. Suppose that h : G → G is a periodic homeomorphism of a marked
graph G and that h̃ : G̃ → G̃ is a periodic lift of h to the universal cover G̃. Then
(1) Fix(h̃) 6= ∅ and a point ṽ ∈ Fix(f˜) can be found algorithmically.
(2) If ṽ ∈ Fix(h̃) projects to v ∈ G then Jṽ (π1 (Fix(h), v)) = ZT (h̃). (See Definition 3.1.)
Proof. After subdividing if necessary we may assume that h, and hence h̃, pointwise
fixes each edge that it preserves. We are now in the setting of Bass-Serre theory and
we use its language. Note that h̃ is not hyperbolic, for otherwise h̃ has infinite order.
Hence h̃ is elliptic; equivalently Fix(h̃) 6= ∅. It is algorithmic to find a fixed point ṽ.
Indeed, if x̃ ∈ G̃ then the midpoint of [x̃, h̃(x̃)] is fixed. This completes the proof of
(1).
For (2), let Fix(h̃) denote the subtree of G̃ consisting of h̃-fixed edges. Given [γ] ∈
π1 (Fix(h), v), let γ̃ be the lift of γ that begins at ṽ and let w̃ be the terminal endpoint
of γ̃. Then T = Jṽ (γ) is the covering translation that carries ṽ to w̃. Since h̃ fixes ṽ
and γ ⊂ Fix(h), h̃ fixes w̃. In particular, T ◦ h̃(ṽ) = T (ṽ) = w̃ = h̃(w̃) = h̃ ◦ T (ṽ)
and so T and h̃ commute. We see that Jṽ (π1 (Fix(h), v)) is contained in ZT (h̃). To
see surjectivity, let T ∈ ZT (h̃). Then T (ṽ) ∈ Fix(h̃). Since Fix(h̃) is a tree, [ṽ, T (ṽ)]
descends to a closed path in Fix(h) based at v.
We could not find a reference for the following result so we have included a proof.
Lemma 9.2. There is an algorithm that, given periodic Φ ∈ Aut(Fn ), computes
Fix(Φ).
Proof. Let φ ∈ Out(Fn ) be represented by Φ. Since the only periodic automorphisms
of Z are the identity and x 7→ −x, we may assume that n ≥ 2. The relative train track
algorithm of [BH92] (see Theorem 2.2) finds a periodic homeomorphism h : G → G
of a marked graph representing φ.
52

We recall some notation from Section 3.1. The marking homotopy equivalence is
µ : (Rn , ∗) → (G, ?). Via a lift of ? to ˜? ∈ G̃ we have an identification of T (G̃) with
Fn , an isomorphism J˜? : π1 (G, ?) → T (G̃) and a lift h̃ : G̃ → G̃ that can be found
algorithmically and that corresponds to Φ in a sense made precise in Section 3.1.
The key points for us are that h̃ is periodic and (Lemma 3.2) that ZT (h̃) and Fix(Φ)
are equal when viewed as subgroups of T (G̃). Since Fn has been identified via µ#
with π1 (G, ?), our goal is to find J˜?−1 ZT (h̃) < π1 (G, ?). By Lemma 9.1 we can
algorithmically find an element ṽ ∈ Fix(h̃). Moreover, letting v ∈ G be the projection
of ṽ and H := π1 (Fix(h), v) < π1 (G, v), we have Jṽ (H) = ZT (h̃). Let η̃ be the path in
G̃ from ˜? to ṽ and let η ⊂ G be its projection. A quick chase through the definitions
shows that J˜?−1 Jṽ : π1 (G, v) → π1 (G, ?) is defined by [γ] → [ηγη −1 ]. Thus Fix(Φ) is
identified with H η < π1 (G, ?).
To recap, the algorithm is
Φ

9.2

h̃

ṽ ∈ Fix(h̃)

H = π1 (Fix(h), v) < π1 (G, v)

H η < π1 (G, ?)

A G-graph of Nielsen paths

For the remainder of Section 9 we assume that f : G → G is a CT representing (a
necessarily rotationless) φ ∈ Out(Fn ).
Let Σ be a (not necessarily connected) graph. It is often useful to work in the
Stallings category of graphs labeled by Σ or Σ-graphs, i.e. an object is a graph H
with a cellular immersion H → Σ and a morphism from H → Σ to H 0 → Σ is a
cellular immersion H → H 0 making the following diagram commute:
H

...............................

...
...
...
...
...
.........

H0

.
...
...
..
.
..........
..

Σ
The map to Σ is often suppressed. In this section we assume that H is finite but in
Section 12 we allow H to be infinite. If we give H the CW -structure whose vertex
set is the preimage of the vertex set of Σ, then the resulting edges of H (often called
edgelets) are labeled by their image edges in Σ and we refer to the oriented edges of
Σ as the set of labels. An edge-path is labeled by its sequence of oriented edges. The
core of H is the Σ-graph that is the union of all immersed circles in H. H is core if
it is its own core.
Σ-graphs are useful because, on each component of H, the immersion H → Σ
induces an injection on the level of π1 and so H is a geometric realization of a collection
of conjugacy classes π1 (Σ) of subgroups of Fn indexed by the components of H. Our
goal in this section is to construct a G-graph that is the geometric realization of the
collection of conjugacy classes [Fix(Φ)] as [Φ] varies over isogredience classes P(φ)/ ∼
of principal automorphisms representing φ.
53

Review 9.3. We precede the construction with a quick review of Nielsen paths in
a CT. Since Nielsen paths with endpoints at vertices split as products of fixed edges
and indivisible Nielsen paths, we focus on indivisible Nielsen paths. There are only
two sources of indivisible Nielsen paths µ. By the (Vertices) property of a CT, the
endpoints of indivisible Nielsen paths are always vertices. If E ∈ Lin(f ), the set
of linear edges in G, then f (E) = EwEd for some twist path wE and some d 6= 0
and EwEk Ē is an indivisible Nielsen path for k 6= 0. By the (NEG Nielsen Paths)
property of a CT, all indivisible Nielsen paths of NEG-height have this form. To E
we associate a G-graph YµE which is a lollipop. Specifically, YµE is the union of an
edge labeled E and a circle labeled wE attached to the terminal end of E. Note that
each EwEk Ē ⊂ G lifts to a path in YµE with both endpoints at the initial vertex of the
edge labeled E. The other possibility is an indivisible Nielsen path µ of EG-height,
say r. In this case, µ and µ̄ are the only indivisible Nielsen paths of height r and
the initial edges of µ and µ̄ are distinct edges of Hr [FH11, Lemma 4.19]. Further,
µ = αβ̄ where α and β are r-legal and the turn (ᾱ, β̄) is illegal of height r [FH11,
Lemma 2.11]. See [FH11, Section 4] for details on Nielsen paths in CTs.
Definition 9.4. We construct a G-graph Ŝ(f ) as follows. If n = 1, then G = R1 (a
rank 1 rose) and Ŝ(f ) := G. Otherwise, start with the subgraph Ŝ1 (f ) of G consisting
of all vertices in Fix(f ) and all fixed edges. For each E ∈ Lin(f ), attach the lollipop
YµE to Ŝ1 (f ) at the initial vertex of E thought of as a vertex in Ŝ1 (f ). For each
EG stratum with an indivisible Nielsen path of that height, choose one µ of that
height (there are only two and they differ by orientation) and attach an edge, say Eµ ,
labeled by µ to Ŝ1 (f ) with initial and terminal endpoints equal to those of µ. This
completes the construction of the graph Ŝ(f ). There is a natural map h : Ŝ(f ) → G
given by inclusion on Ŝ1 (f ) and by the G-graph structures on each YµE and Eµ . By
construction, h is an immersion away from the attaching points in Ŝ1 (f ) and is a local
homeomorphism at each vertex in Ŝ1 (f ). Thus Ŝ(f ) is a G-graph.
Let v ∈ Fix(f ). We abuse notation slightly by also denoting the unique lift of v in
Ŝ1 (f ) by v. Define Ŝ(f, v) to be the component of Ŝ(f ) that contains v. It is possible
that Ŝ(f, v) is not core.

a

b

Figure 2: A CT f : G → G given by a 7→ ab, b 7→ bab and the graph Ŝ(f ). Ŝ1 (f ) is
the unique vertex of G. Ŝ(f ) is the closed Nielsen path µ = abāb̄.

54

a
c

b

d
b
a

a

c

a

Figure 3: A CT h : H → H given by a 7→ a, b 7→ ba2 , c 7→ ca, d 7→ db and the graph
Ŝ(h). Ŝ1 (h) is the loop a and the common initial vertex of c and d. Add the lollipop
associated to b to the former component and the lollipop associated to c to the latter
to make Ŝ(h).
Remark 9.5. Since the construction of f : G → G is algorithmic, finding the set
of indivisible Nielsen paths of EG height, and finding Fix(f ) are all algorithmic, it
follows that the constructions of Ŝ(f ) and Ŝ(f, v) are algorithmic.
Lemma 9.6. (1) A path σ ⊂ G with endpoints at vertices lifts to a (necessarily
unique) path σ̂ ⊂ Ŝ(f ) with endpoints in Ŝ1 (f ) if and only if σ is a Nielsen
path. Moreover, σ is closed if and only if σ̂ is closed.
(2) If f represents φ ∈ Out(Fn ) then non-trivial φ-periodic (equivalently φ-fixed)
conjugacy classes in Fn are characterized as those classes represented by circuits
in Ŝ(f ).
Proof. (1): The main statement is an immediate consequence of the construction of
Ŝ1 (f ) and the fact that a Nielsen path in a CT is the concatenation of fixed edges
and indivisible Nielsen paths with endpoints at vertices. The moreover part follows
from the fact that each vertex in G has a unique lift into Ŝ1 (f ).
(2): Suppose that the circuit σ ⊂ G represents a φ-fixed conjugacy class. [FH11,
Lemmas 4.11 and 4.25] imply that f#k (σ) has a unique complete splitting for all
sufficiently large k and hence σ has a unique complete splitting. It follows that each
term in the splitting is a periodic, and hence fixed, Nielsen path. Viewing σ as a closed
path with endpoint at one of the splitting vertices, we can lift σ to a path σ̂ ⊂ Ŝ(f )
with endpoints in Ŝ1 (f ). Since each vertex in G has a unique lift into Ŝ1 (f ), σ̂ is a
closed path and hence a circuit (because it projects to a circuit). Conversely, every
circuit in Ŝ(f ) projects in G to a concatenation of fixed edges and indivisible Nielsen
paths.
Definition 9.7. We will also have need of the subgraph S(f ) := ∪v S(f, v) of Ŝ(f )
where the union is over principal vertices v of G. Equivalently (see Lemma 3.8), S(f )
is obtained from Ŝ(f ) by removing components consisting of a single non-principal
vertex. The construction of S(f ) goes exactly as in Definition 9.4 except we start
with the subgraph S1 (f ) consisting of all principal vertices and fixed edges in Fix(f ).

55

9.3

Fix(Φ) for rotationless φ

In this section we compute Fix(Φ) for (not necessarily principal) Φ ∈ Aut(Fn ) representing rotationless φ ∈ Out(Fn ). We begin with the analog of Lemma 9.1(2). Recall
that the unique lift of v ∈ Fix(f ) in Ŝ1 (f, v) is denoted v.
Lemma 9.8. For each vertex v ∈ Fix(f ) and lift ṽ ∈ G̃ let Jˆṽ = Jṽ h# : π1 (Ŝ(f, v), v) →
T (G̃) where h# : π1 (Ŝ(f, v), v) → π1 (G, v) is induced by the immersion h : Ŝ(f, v) →
G. Let f˜ : G̃ → G̃ be the lift of f that fixes ṽ. Then Jˆṽ is injective and has image
equal to ZT (f˜).
Proof. Jˆṽ is injective because h# is injective and Jṽ is an isomorphism.
If γ̂ ⊂ Ŝ(f, v) is a closed path based at v then γ := h(γ̂) ⊂ G is a closed Nielsen
path based at v by Lemma 9.6. Lift γ to a Nielsen path γ̃ ⊂ G̃ for f˜ with initial
endpoint ṽ. By definition, T := Jˆṽ ([γ]) is the covering translation that maps ṽ to the
terminal endpoint w̃ of γ̃. Since w̃ ∈ Fix(f˜), we have f˜ ◦ T (ṽ) = f˜(w̃) = w̃ = T (ṽ) =
T ◦ f˜(ṽ) and so f˜ ◦ T = T ◦ f˜, i.e. T ∈ ZT (f˜).
To see that Jˆṽ is surjective, let T ∈ ZT (f˜). Then T (ṽ) is fixed by f˜ and the path
γ̃ from ṽ to w̃ is a Nielsen path for f˜ and so projects to a closed Nielsen path γ ⊂ G
based at v that lifts to a closed Nielsen path γ̂ ⊂ Ŝ(f ) based at v̂. By construction,
Jˆṽ [γ̂] = T .
Lemma 9.9. There is an algorithm that, given rotationless φ ∈ Out(Fn ), computes
Fix(Φ) for Φ ∈ φ.
Proof. Let f : G → G be a CT representing the element φ ∈ Out(Fn ) determined
by Φ. Subdivide if necessary so that every isolated fixed point of f is a vertex.
The setup is similar to that of Lemma 9.2. The marking homotopy equivalence is
µ : (Rn , ∗) → (G, ?). Via a lift of ? to ˜? ∈ G̃ we have an identification of T (G̃) with
Fn , an isomorphism J˜? : π1 (G, ?) → T (G̃) and a lift f˜ : G̃ → G̃ that can be found
algorithmically and that corresponds to Φ in a sense made precise in Section 3.1. The
key point for us is Lemma 3.2 which states that ZT (f˜) and Fix(Φ) are equal when
viewed as subgroups of T (G̃).
Apply Lemma 6.4 to decide if Fix(f˜) = ∅.
If Fix(f˜) 6= ∅ then Lemma 6.4 finds ṽ ∈ Fix(f˜). Since isolated fixed points of f are
vertices, we may assume that ṽ is a vertex. Indeed, by Convention 2.1 non-isolated
fixed points only occur in fixed edges.
Let v ∈ G be the projection of ṽ, let η ⊂ G be the projection of the path η̃ ⊂ G̃
from ˜? to ṽ, and let h : Ŝ(f, v) → G be the immersion given by the G-structure. Define
H = h# (π1 (Ŝ(f, v), v)) < π1 (G, v). Arguing as in Lemma 9.2, with Lemma 9.1(2)
replaced by Lemma 9.8 we conclude that Fix(Φ) is identified with H η < π1 (G, ?).
Since Fn has been identified via µ# with π1 (G, ?), we are done. In summary,
Φ

f˜

ṽ ∈ Fix(f˜)

H = h# (π1 (Ŝ(f, v), v)) < π1 (G, v)
56

H η < π1 (G, ?)

If Fix(f˜) = ∅ then f˜ is not principal [FH11, Corollary 3.17] and so rank(Fix(Φ)) ≤
1 [FH11, Remark 3.3] and FixN (∂ f˜) = FixN (∂Φ) has at most two points. Lemma 6.4
finds a completely split path σ̃ that generates a ray R̃. There are two subcases. If
the projected image σ ⊂ G is not a Nielsen path then |f#k (σ)| → ∞ and [GJLL98,
Proposition I.1] implies that the terminal endpoint P of R̃ = σ̃ · f˜# (σ̃) · f˜#2 (σ̃) · . . .,
which is evidently fixed by ∂ f˜, is an attractor for the action of ∂ f˜, is contained
in FixN (∂ f˜) and is not the endpoint of an axis of a covering translation. If ZT (f˜)
contains a non-trivial element T then the T -orbit of P would be an infinite set in
FixN (∂ f˜). This contradiction shows that ZT (f˜), and hence Fix(Φ), is trivial. The
remaining subcase is that σ is a Nielsen path. Let ṽ and w̃ be the initial and terminal
endpoints of σ̃ respectively and let T be the covering translation that carries ṽ to
w̃. Since f˜# (σ̃) is the unique lift of σ with initial endpoint at w̃, we have f˜(ṽ) =
T (ṽ) = w̃ and f˜(w̃) = T (w̃). Thus f˜T (ṽ) = T f˜(ṽ) and T ∈ ZT (f˜). Equivalently
Jṽ ([σ]) ∈ ZT (f˜). Letting H < π1 (G, v) be the maximal cyclic subgroup that contains
[σ], we have Jṽ (H) = ZT (f˜) and the usual argument shows that Fix(Φ) is identified
with H η < π1 (G, ?). In summary,
Φ

9.4

f˜

σ̃

h[σ]i < H < π1 (G, v)

H η < π1 (G, ?)

The general case

Proposition 9.10 (Bolgopolski-Maslakova [BM16]). There is an algorithm that,
given Φ ∈ Aut(Fn ), computes Fix(Φ).
Proof. The case of Φ ∈ φ with φ rotationless was handled in Lemma 9.9.
Suppose then that φ is not rotationless. In Corollary 3.14 we computed M so
that φM is rotationless. So quoting Lemma 9.9 again, Fix(ΦM ) can be computed
algorithmically. We are reduced to finding the fixed subgroup of the periodic action
of Φ on Fix(ΦM ). More generally, we are reduced to finding Fix(Φ) for a finite order
Φ ∈ Aut(Fn ), and this is the content of Lemma 9.2.

10

S(f ) and Fix(φ)

Let f : G → G be a CT representing φ ∈ Out(Fn ). In this section we characterize
the components of S(f ) and show that S(f ) is the geometric realization of Fix(φ)
defined as follows.
Definition 10.1. For φ ∈ Out(Fn ), Fix(φ) is defined to be the collection of [Fix(Φ)]
indexed by isogredience classes [Φ] ∈ P(φ)/ ∼.
Recall two facts from the review in Section 3.2:
57

• If f˜ is a principal lift of f then Fix(f˜) is non-empty.
• If f˜1 , f˜2 are principal lifts of f then f˜1 and f˜2 are isogredient iff Fix(f˜1 ) and
Fix(f˜2 ) have equal projections in G.
By the definition of a CT, endpoints of indivisible Nielsen paths are vertices and
so Lemma 3.8(1) implies that, for principal f˜, Fix(f˜) consists of vertices and edges.
It follows that there are only finitely many equivalence classes of principal lifts of f
and that there is a 1-1 correspondence between isogredience classes [f˜] of principal
lifts f˜ of f and Nielsen classes [v] of principal vertices v in G given by [f˜] ↔ [v] iff f˜
fixes some lift of v. It is algorithmic to tell if a vertex of G is principal and to find
its Nielsen class (Lemmas 3.8(1) and 9.6).
By construction, for principal vertices v and v 0 , S(f, v) = S(f, v 0 ) iff [v] = [v 0 ]. We
write S(f, v) = S(f, [v]) = S([f˜]) where [v] ↔ [f˜] and see that S(f ) = t[v] S(f, [v]) =
t[f˜] S([f˜]) where [v] runs over Nielsen classes of principal vertices in G and [f˜] runs
over isogredience classes of principal lifts of f .
If f˜ ↔ Φ and f˜0 ↔ Φ0 are isogredient then Fix(Φ) and Fix(Φ0 ) are conjugate and
ZT (f˜) and ZT (f˜0 ) are conjugate. Hence, the isogredience classes of Φ and f˜ determine a conjugacy class Fix([Φ]) of subgroup of Fn and a conjugacy class ZT ([f˜]) of
subgroup of T (G̃). The sets Fix([Φ]) and ZT ([f˜]) correspond under the identifications
of Section 3.1; we denote this by Fix([Φ]) ↔ ZT ([f˜]). If [f˜] ↔ [v] and f˜ ↔ Φ then
S(f, [v]) is the geometric realization of Fix([Φ]) and S(f ) is the geometric realization
of Fix(φ).

11

Possibilites for [Fix(Φ)]

In this section we algorithmically find the possibilities for [Fix(Φ)] = Fix([Φ]) for
Φ ∈ φ with φ rotationless (Corollary 11.1).
Corollary 11.1. Let φ ∈ Out(Fn ) be rotationless.
(1) There are finitely many Fn -conjugacy classes in
{Fix(Φ) | Φ ∈ Aut(Fn ) is principal and represents φ}
These conjugacy classes are represented by the components of S(f ) where f :
G → G is a CT for φ. In particular, they can be computed algorithmically.
(2) For all Φ ∈ φ, Fix(Φ) is root-free. Conversely, if w 6= 1 ∈ Fn is root-free and
[w] is φ-invariant then
(a) there is Φ ∈ P(φ) such that w ∈ Fix(Φ) and
(b) there is non-principal Φ0 ∈ φ such that Fix(Φ0 ) = hwi.

58

Proof. (1): This is the content of Section 10.
(2): Fix(Φ) is always root-free. The existence of Φ as in (a) follows from [FH11,
Lemma 3.30 (1)]. The automorphism Φm := im
w ◦ Φ fixes w for all m and is principal
for only finitely many m ∈ Z; see [FH11, Lemma 4.40]. Take Φ0 to be a non-principal
Φm . Since Φ0 is non-principal, rank(Fix(Φ0 )) < 2 and we see that Fix(Φ0 ) = hwi.
Lemma 11.3 below seems obvious but we could not find a reference for it in the
literature so we are including it here with a proof for completeness. The following
lemma is used in its proof.
Lemma 11.2. For all non-trivial φ there exists a filling conjugacy class that is not
fixed by φ.
Proof. After replacing φ by an iterate, we may assume that φ is rotationless. Let
f : G → G be a topological representative of φ and let β ⊂ G be a circuit representing
a conjugacy class [c] that is not φ-invariant. Since φ is rotationless, [c] is not fixed by
any iterate of φ. We may therefore choose k so that the edge length of f#k (β) is greater
than the edge length of β. Choose a path α ⊂ G such that any circuit containing
α is filling (any path α whose Whitehead graph does not have a cut-point will do
[Mar95]; see also [BF14, Proof of Lemma 3.2]). Choose a circuit τ that contains both
α and β as disjoint subpaths. Decompose τ as a concatenation of subpaths τ = µβ
and let τN = µβ N . The bounded cancellation lemma implies that the edge length of
f#k (τN ) is greater than the edge length of τN for all sufficiently large N . Each such
τN satisfies the conclusions of the lemma.
Lemma 11.3. Each infinite order φ ∈ Out(Fn ) is represented by Φ ∈ Aut(Fn ) with
trivial fixed subgroup.
Proof. Choose (Lemma 11.2) a filling conjugacy class [a] that is not fixed by ψ = φl
where l is chosen so that both ψ and ψ −1 are rotationless. Let {a± } ⊂ ∂Fn denote the
endpoints of the axis of a. Choose Φ representing φ such that ∂Φ({a± }) ∩ {a± } = ∅
and let Φm = im
a ◦ Φ. We will prove that Fix(Φm ) is trivial for all sufficiently large m.
Assuming that Φm fixes some non-trivial bm for arbitrarily large m, we will argue
to a contradiction. For notational convenience we pass to a subsequence and assume
that for all m ≥ 1, bm is fixed by Φm . After passing to a further subsequence we may
−
+
+
assume that b+
m → P and bm → Q for some P, Q ∈ ∂Fn . From ∂Φm (bm ) = bm we see
−m +
+
−1 −
that ∂Φ(b+
m ) = ∂ia (bm ) and hence that P is either a or ∂Φ (a ). Similarly, Q is
either a+ or ∂Φ−1 (a− ).
Let f : G → G be a CT representing ψ and let f˜m be the lift of f : G → G
corresponding to Ψm := Φlm . Let T and Sm be the covering translations corresponding
±
to a and bm respectively. Thus T ± = a± and Sm
= b±
m . If P 6= Q then the line
connecting a+ to ∂Φ−1 (a− ) is a weak limit of the axes for Sm . It follows that the axis
of T is a weak limit of a sequence of Nielsen axes for f˜m and hence that the axis of

59

T is an increasing union of arcs each lifting to S(f ). The axis of T therefore lifts to
S(f ) and so represents a ψ-fixed conjugacy class by Lemma 9.6, contradiction.
Suppose then that P = Q = Φ−1 (T − ). (The case that P = Q = T + is argued
+
symmetrically.) For all sufficiently large m, there is a neighborhood Um
of T + in
+
+
+
∂Fn such that ∂Φm (Um
) ⊂ Um
. By [LL08, Theorem I], Um
contains a non-repelling
+
periodic point for the action of ∂Φm . Thus Ψm is a principal lift of ψ and Um
contains
+
an element Bm of FixN (Ψm ). As m → ∞ we may assume that Bm → T .
By Lemma 3.10, there exists a lift Ẽm of some Em ∈ E such that the lift R̃Em of
the eigenray generated by Em terminates at Bm . We may assume without loss that
E = Em is independent of m. The ray from the initial endpoint x̃m of Ẽm to b+
m
factors as a concatenation of Nielsen paths and so lifts into S(f ). After passing to
yet another subsequence we may assume that x̃m converges to a point X. If X = T +
then the axis of T is a weak limit of paths that lift into S(f ) and so lifts to S(f ). As
above, this gives the desired contradiction. We may therefore assume that X 6= T + .
In this case the axis of T is a weak limit of lifts of RE and so the periodic line that it
projects to is a weak limit of RE . We will complete the proof by showing that each
such periodic line L is carried by Gr−1 where Hr is the top stratum of G. There is no
loss in assuming that E is an edge in Hr . If E is NEG then [FH11, Lemma 3.26(3)]
completes the proof. If E ⊂ Hr is EG then L is leaf in the attracting lamination
Λr associated to Hr by [FH11, Lemma 3.26(2)]. But every leaf is either contained in
Gr−1 or is dense in Λr by [BFH00, Lemma 3.1.15] and the latter is impossible for a
periodic line.

12

A Stallings graph for FixN (∂Φ)

As usual, throughout Section 12 f : G → G will denote a CT for φ. The goal of
this section is to generalize Section 10 by describing a (not necessarily finite) G-graph
SN (f ) with core S(f ) that in a sense described below represents the collection of
FixN (∂Φ) (Definition 3.3) indexed by Φ ∈ P(φ). This collection plays an important
role in the main theorem of [FH11]. We will first define the graph SN (f ) and then
relate it to the collection of FixN (∂Φ). FixN (∂Φ) has been of considerable interest;
see for example [Nie86, Nie29, IKT90, Coo87, GJLL98, BFH97].

12.1

Definition of SN (f )

The idea of the construction of SN (f ) is to start with S(f ) and add a copy of RE
for each E ∈ Ef . This does not quite work since it is possible that ∂RE = ∂RE 0 for
E 6= E 0 . In the next paragraph we describe the ways that this can happen.
Suppose that E 6= E 0 ∈ Ef and that ∂RE = ∂RE 0 . Choose a lift Ẽ of E to G̃,
let R̃E be the lift of RE that begins at the initial endpoint ṽ of Ẽ and let P be the
terminal endpoint of R̃E . By hypothesis, there is a lift R̃E 0 of RE 0 that terminates
at P . Let Ẽ 0 be the initial edge of R̃E 0 and let w̃ be the initial vertex of Ẽ 0 . If
60

f˜ is the lift that fixes ṽ then ∂ f˜ fixes P . Since f˜ is the only lift of f that fixes
P (Remark 3.11), it follows that f˜ also fixes w̃. The path ρ̃ connecting ṽ to w̃ is
therefore a Nielsen path for f˜ and its image ρ ⊂ G is a Nielsen path for f . The edges
E and E 0 are of the same EG height, say r, since the height of E (resp. E 0 ) is the
height of RE (resp. RE 0 ) and edges of this height occur infinitely often in RE (resp.
0
RE 0 ) and RE and RE
have a common tail. It follows from the facts in Review 9.3
that ρ is a concatenation of subpaths that are fixed edges or indivisible Nielsen paths,
that E (resp. E 0 ) must be contained in an indivisible Nielsen subpath of height r,
and that each of these indivisible Nielsen subpaths of height r contributes an illegal
turn of height r. By construction, ρ has at most one illegal turn of height r and so
we conclude that ρ is indivisible. Note that R̃E and R̃E 0 have a common terminal ray
R̃E,E 0 and that ρ̃ = α̃β̃ −1 where R̃E = α̃R̃E,E 0 and R̃E 0 = β̃ R̃E,E 0 giving ρ the form
αβ −1 as in Review 9.3.
Definition 12.1. We use the notation from the Definitions 9.4 and 9.7. Let SN (f )
be the graph obtained from S(f ) as follows. For each NEG E ∈ Ef and for each EG
E ∈ Ef that is not the initial edge of an indivisible Nielsen path, attach RE to S(f )
by identifying the initial endpoint of RE with the initial endpoint of E thought of as
a vertex in S1 (f ). If E ∈ Ef belongs to an EG stratum Hr and E is the initial edge
of an indivisible Nielsen path ρ of height r then the initial edge E 0 of ρ−1 is also an
edge of Ef ∩ Hr . Subdivide the edge labeled ρ that was added to S(f ) during stage
two so that it is now two edges, one labeled α and the other β −1 . Attach RE,E 0 to
S(f ) at the newly created vertex.
Remark 12.2. Given that the construction of S(f ) is algorithmic and that any initial
segment of a ray RE of prescribed length can be explicitly computed, it follows that
there is an algorithm that, given d > 0, constructs the d-neighborhood (in the graph
metric) of S(f ) in SN (f ).

...
Figure 4: SN (f ) for f as in Figure 2. SN (f ) is obtained from S(f ) by adding the
rays Ra,b = babbab . . . and RB = BABBABAB . . . .
By construction of SN (f ), its components are in a 1-1 correspondence with the
components of S(f ). That is, components of SN (f ) are in a bijective correspondence

61

a
b

a

c dbbabaabaaa...

a

Figure 5: SN (h) for h as in Figure 3. SN (h) is obtained from S(h) by adding the
eigenray dbb . . ..
with Nielsen classes [v] of principal vertices v in G. Let SN (f, [v]) denote the component of SN (f ) containing v. We have SN (f ) = t[v] SN (f, [v]) where [v] runs over
Nielsen classes of principal vertices in G. We continue to identify the principal vertices of G with the vertices of S1 (f ). We call these vertices the principal vertices of
SN (f ).

12.2

Properties of SN (f )

In this section we record some properties of SN (f ). We defined the term core of a
Σ-graph H in Section 9.2. The weak core of H is the union of all properly immersed
lines in H. H is weakly core if it is its own weak core. We say that H has finite type
if it is the union of a finite graph and finitely many rays.
Lemma 12.3. SN (f ) is a G-graph of finite type and all vertices have valence ≥ 2.
In particular, SN (f ) is weakly core.
Proof. By construction, the labeling map SN (f ) → G is an immersion and SN (f )
has finite type and its non-principal vertices have valence either two or three. By
[FH11, Lemma 4.14], a principal vertex v has at least two fixed directions in G, each
corresponding to a fixed edge, an edge in Lin(f ), or an edge in Ef . By construction,
each of these edges contributes a direction at v in SN (f ). Thus all principal vertices,
and hence all vertices, have valence at least two.
Lemma 12.4. Let f˜ : G̃ → G̃ be principal and fix the vertex ṽ ∈ G̃. The labelling
map SN (f, v) → G induces an embedding S̃ → G̃ of universal covers. The induced
map ∂ S̃ → ∂ G̃ has image FixN (∂ f˜).
Proof. The first conclusion follows since the labelling map is an immersion. To prove
the second, note that every ray R with initial vertex v is either contained in S(f, v)
in which case the corresponding lift R̃ has endpoint in ∂(Fix(f˜)) or else is the concatenation of a Nielsen path and a ray RE in which case R̃ has endpoint in Fix+ (∂ f˜).
Conversely, if P ∈ FixN (∂ f˜) then the ray [ṽ, P ) is a concatenation of a Nielsen path
and the lift of some RE by [FH11, Lemma 4.36(2)].

62

Corollary 12.5. In the notation of Lemma 12.4, S̃ is the convex hull of FixN (∂ f˜),
i.e. the union of all lines connected distinct points in FixN (∂ f˜). In particular, if
n > 1 then no component of SN (f ) is a circle, an axis in G̃, or a generic leaf of an
attracting lamination of f .
Remark 12.6. In the main theorem of [FH11], a rotationless outer automorphism φ
is characterized in terms of two invariants: one qualitative and the other quantitative.
The collection of FixN (∂Φ) indexed by Φ ∈ P(φ) is the qualitative invariant. From
the results of this section, we see that SN (f ) represents this qualitative invariant in
the following sense. If X is a component of SN (f ) and X̃ → G̃ is a lift of the natural
immersion X → G, then the image of the induced map ∂ X̃ → ∂Fn is FixN (∂Φ) for
some Φ ∈ P(φ). Conversely, if Φ ∈ P(φ) then FixN (∂Φ) is the image of ∂ X̃ → ∂Fn
for some component X of SN (f ) and some lift X̃ → G̃.

13

Moving up through the filtration

Several of our applications are verified by working up through the filtration of a
CT f : G → G. In this section we establish notation by recalling some notation
and a lemma from [FH09, Notation 8.2 and Lemma 8.3]. The negative of the Euler
characteristic will be important to us; we write χ− for −χ.
Notation 13.1. Recall from (Filtration) that the core of each filtration element is a
filtration element. The core filtration
∅ = G0 = Gl0 ⊂ Gl1 ⊂ Gl2 ⊂ · · · ⊂ GlK = GN = G
is defined to be the coarsening of the full filtration obtained by restricting to those
elements that are their own cores or equivalently have no valence one vertices. Note
that l1 = 1 by (Periodic edges). For each Gli , let Hlci be the ith stratum of the core
filtration. Namely
li
[
c
Hli =
Hj
j=li−1 +1

The change in negative Euler characteristic is denoted ∆i χ− := χ− (Gli ) − χ− (Gli−1 ).
Referring to Notation 2.11, if Hli is EG then Hui denotes the highest irreducible
stratum in Gli −1 .
Lemma 13.2 ([FH09, Lemma 8.3]).
one of the following holds.

(1) If Hlci does not contain any EG strata then

(a) li = li−1 + 1 and the unique edge in Hlci is a fixed loop that is disjoint from
Gli−1 .
(b) li = li−1 + 1 and both endpoints of the unique edge in Hlci are contained in
Gli−1 .
63

(c) li = li1 +2 and the two edges in Hlci are nonfixed and have a common initial
endpoint that is not in Hli−1 and terminal endpoints in Gli−1 .
In case (a), ∆i χ− = 0; in cases (b) and (c), ∆i χ− = 1.
(2) If Hlci contains an EG stratum then Hli is the unique EG stratum in Hlci and
there exists li−1 ≤ ui < li such that both of the following hold.
(a) For li1 < j ≤ ui , Hj is a single nonfixed edge Ej whose terminal vertex
is in Gli−1 and whose initial vertex has valence one in Gui . In particular,
Gui deformation retracts to Gli−1 and χ(Gui ) = χ(Gli−1 ).
(b) For ui < j < li , Hj is a zero stratum. In other words, the closure of
Gli \ Gui is the extended EG stratum Hlzi .
If some component of Hlci is disjoint from Gui then Hlci = Hli is a component of
Gli and ∆i χ− ≥ 1; otherwise ∆i χ− ≥ 2.

14

Primitively atoroidal outer automorphisms

In this section we exhibit an algorithm to determine whether or not a φ ∈ Out(Fn ) is
primitively atoroidal (Corollary 14.4).
Definition 14.1. A conjugacy class in Fn is primitive if it is represented by an
element in some basis of Fn . An outer automorphism φ is primitively atoroidal if
there does not exist a periodic conjugacy class for φ which is primitive.
Lemma 14.2. Let f : G → G be a CT. Either some stratum is a fixed loop or all
closed Nielsen paths are trivial in H1 (G; Z/2Z).
Proof. We use the notation of Section 13. Suppose the statement holds for Glli −1 .
To get a contradiction, suppose the statement fails for Gli , that is suppose that Hlci
is not a fixed loop and that some closed Nielsen path µ of height li is non-trivial in
H1 (Gli ; Z/2Z). We go through the cases of Lemma 13.2.
Recall that Nielsen paths are completely split and their complete splitting consists
of fixed edges and indivisible Nielsen paths.
In (1a), Hli is a fixed loop and we are assuming this is not the case.
In (1b), by the (NEG Nielsen Paths) property of a CT Eli := Hli is either fixed or
linear and if Eli is linear then µ or µ−1 has a term of the form Eli wlki Ēli with notation
as in (NEG Nielsen Paths).
Suppose first that Eli is fixed.
• If µ has only one occurrence of Eli and no occurrences of its inverse (or the
symmetric case) then µ is primitive. In this case, the union F of the free factor
system [Gli−1 ] with the conjugacy class of the cyclic subgroup generated by µ is a
64

φ-invariant free factor system properly containing [Gli−1 ] and contained in [Gli ];
see Example 4.11. The (Filtration) property of a CT implies that F = [Gli ]
contradicting our assumption that Hlci is not a fixed loop.
• Consider the (cyclic) sequence of El±1
’s that occurs in µ and suppose there
i
are consecutive occurrences with the same orientation, say µ = . . . Eli xEli . . . .
Then µ0 = Eli x is a closed Nielsen path as in the preceding bullet, contradiction.
• The remaining case is that µ or µ−1 has the form Eli x1 El−1
x2 El1 . . . El−1
xN ,
i
i
i.e. the orientations of the Eli ’s alternate. Each xi is a closed Nielsen path
and by induction is trivial in H1 (G; Z/2Z). If follows that µ is also trivial in
H1 (G; Z/2Z)
dl

Next suppose that Eli is linear and f (Eli ) = Eli · wli i (with notation as in (Linear
Edges)). In particular, wli is a closed Nielsen path of height < li and so is trivial in
H1 (G; Z/2Z). By (NEG Nielsen Paths), µ a product of paths of the form Eli uk El−1
k
and closed Nielsen paths of height < li . In particular, µ is trivial in H1 (G; Z/2Z),
contradiction. This completes the proof of (1b).
In (1c), by (NEG Nielsen Paths) Hlci consists of two linear edges. This case is
similar to the case that Hlci consists of one linear edge. We conclude µ is trivial in
H1 (G; Z/2Z), again a contradiction.
In (2), by [FH11, Corollary 4.19 and Remark 4.20] either there are no closed
Nielsen paths of height li or there is a Nielsen loop µli of height li such that every
Nielsen loop of this height is a power of µli and further µli is trivial in H1 (G; Z/2Z).
This is a contradiction.
Corollary 14.3. Let φ be rotationless. Either
• for some Φ ∈ P(φ), there is an element of Fix(Φ) that is primitive in Fn ; or
• for all Φ ∈ P(φ), every element of Fix(Φ) is trivial in H1 (Fn ; Z/2Z).
There are more general purpose algorithms that check whether a finitely generated
subgroup of Fn contains a primitive element; see [CG10, Dic14]. We thank the referee
for pointing out these references to us.
Corollary 14.4. There is an algorithm to tell whether or not a given φ ∈ Out(Fn )
is primitively atoroidal.
Proof. Compute a CT f : G → G for a rotationless power of φ. According to
Lemma 14.2, φ is primitively atoroidal iff some stratum of G is a fixed circle.

65

15

The index of an outer automorphism

Definition 15.1 ([GJLL98]). For Φ ∈ Aut(Fn ),
1
i(Φ) := max{0, rank(Fix(Φ)) + a(Φ) − 1}
2
where a(Φ) is the P
number of Fix(Φ)-orbits of attracting fixed points of ∂Φ. For φ ∈
Out(Fn ), i(φ) :=
i(Φ) where the sum ranges over representatives of isogredience
classes of φ.
It is clear that i(Φ) > 0 implies Φ is principal. In particular
i(φ) :=
where the sum

P

X


1
rank(Fix(Φ)) + a(Φ) − 1
2

i(Φ) is over principal representatives Φ of φ only.

Proposition 15.2. There is an algorithm to compute the index of rotationless φ ∈
Out(Fn ).
See also [GJLL98, Section 6.1].
Proof. Using Theorem 1.1, construct a CT f : G → G for φ. Let SN (f ) = t[v] SN (f, [v])
be the graphs constructed from f in Section 12. If Φ is in the isogredience class of
the principal representative of φ determined by the principal vertex v ∈ G then
i(Φ) = i(SN (f, [v])) where the the index i of a finite type connected graph Γ is
1
i(Γ) := max{0, rank(Γ) + a(Γ) − 1}
2
where a(Γ) is the number of ends of Γ.
The index satisfies a well-known inequality:
Theorem 15.3 ([GJLL98]). For φ ∈ Out(Fn ), i(φ) ≤ n − 1.
We take this opportunity to use CTs to somewhat strengthen this inequality; see
Proposition 15.14. See Section 3.3 to recall notation. Also see Lemma 3.10.
From the CT point of view, the set of attracting fixed points of ∂Φ can be partitioned into those coming from EG strata and those coming from NEG strata. The
following lemma states that this is independent of the choice of CT representing φ.
Lemma 15.4. [HM, Part I Definitions 2.9 and 2.10 and Lemma 2.11] Suppose that
φ is rotationless, that Φ ∈ P(φ) and that P ∈ Fix+ (∂Φ). Then the following are
equivalent.
(1) For some CT f : G → G representing φ there is a non-linear N EG edge E
with a lift Ẽ to G̃ so that R̃Ẽ converges to P .
66

(2) For every CT f : G → G representing φ there is a non-linear N EG edge E
with a lift Ẽ to G̃ so that R̃Ẽ converges to P .
Following Lemma 15.4 we make the following definition, with justification given
in Remark 15.6.
Definition 15.5. Let Φ ∈ P(φ) with φ ∈ Out(Fn ) and P ∈ Fix+ (∂Φ). If φ is
rotationless then P is an NEG-ray for Φ if the equivalent conditions of Lemma 15.4
are satisfied. If φ is not necessarily rotationless then P is an NEG-ray for Φ if P
is an NEG-ray for ΦK where φK is a rotationless iterate of φ. Let RN EG (Φ) denote
{R | R is an NEG-ray for Φ}, let RN EG (φ) denote ∪Φ∈P(φ) RN EG (Φ) and let R(φ)
denote ∪Φ∈P(φ) Fix+ (Φ).
Remark 15.6. To see that Definiton 15.5 is well defined (i.e. independent of the
choice of K), note that if φ is rotationless and f is a CT representing φ then f k is a
CT representing φk for all k ≥ 1 (Lemma 5.5). It follows that P is an NEG-ray for Φ
if and only if it is a NEG-ray for each Φk . If φ is not rotationless but has rotationless
iterates φK and φL then P is an NEG-ray for φK if and only if it is an NEG-ray for
φKL if and only if it is an NEG-ray for φL .
Definition 15.7. Suppose φ ∈ Out(Fn ) and Φ ∈ P(φ). Define j(Φ) := i(Φ) + 21 b(Φ)
where
b(Φ) is the number of Fix(Φ)-orbits of N EG-rays of Φ and define j(φ) :=
P
j(Φ) where the sum is over representatives of isogredience classes of principal
representatives of φ.
Lemma 15.8. Let Φ, Ψ ∈ P(φ).
(1) If Fix+ (Φ) ∩ Fix+ (Ψ) 6= ∅ then Φ = Ψ. In particular,
R(φ) = tΦ∈P(φ) Fix+ (Φ)
and
RN EG (φ) = tΦ∈P(φ) RN EG (Φ)
(2) The stabilizer of Fix+ (Φ) [resp. RN EG (Φ)] under the action of Fn on R(φ)
[resp. RN EG (φ)] is Fix(Φ).
(3) The natural maps
tN
i=1 Fix+ (Φi )/ Fix(Φi ) → R(φ)/Fn
and
tN
i=1 RN EG (Φi )/ Fix(Φi ) → RN EG (φ)/Fn
are bijective where {Φi | i = 1, . . . , N } is a set of representatives of isogredience
classes in P(φ).

67

Proof. (1): Since Φ and Ψ both represent φ, ΦΨ−1 = ia for some a ∈ Fn . If R ∈
Fix+ (Φ) ∩ Fix+ (Ψ) then aR = R. Since R is not an endpoint of the axis of a, a = 1.
(Here we are using the shorthand notation aR for ∂ia (R).)
(2): Suppose a ∈ Fix(Φ) and R ∈ RN EG (Φ). Then ∂Φ(aR) = Φ(a)∂Φ(R) = aR
and so aR ∈ RN EG (Φ). Conversely, if a ∈ Fn , R ∈ RN EG (Φ), and ∂Φ(aR) = aR
then aR = ∂Φ(aR) = Φ(a)∂Φ(R) = Φ(a)R. We conclude a = Φ(a) as in the proof of
(1). The same argument applies with RN EG (Φ) replaced by Fix+ (Φ).
(3): This is a consequence of (1), (2), and the observation that Fn acts on Fix+ (Φ)
[resp. RN EG (φ)] by permuting the Fix+ (Φ)’s [resp. RN EG (Φ)’s].
Lemma 15.9.

(1) For k > 0 and φ ∈ Out(Fn ), b(φk ) ≥ b(φ).

(2) For k > 0 and φ ∈ Out(Fn ), a(φk ) ≥ a(φ).
Proof. (1): By definition of b(φ) and Lemma 15.8(3),
b(φ) = | tN
i=1 RN EG (Φi )/ Fix(Φi )| = |RN EG (φ)/Fn |
Also by definition, if R is an NEG-ray for Ψ ∈ P(φ) then R is an NEG-ray for
Ψk ∈ P(φk ) and so RN EG (φk ) ⊇ RN EG (φ). Hence
b(φk ) = |RN EG (φk )/Fn | ≥ |RN EG (φ)/Fn | = b(φ)
(2): The proof is the same as that of (1), replacing RN EG (Φ) with Fix+ (Φ) and
RN EG (φ) with R(φ).
Notation 15.10. For H < Fn , r̂(H) := max(0,
P rank(H) − 1). For Φ ∈ Aut(Fn ),
r̂(Φ) := r̂(Fix(Φ)). For φ ∈ Out(Fn ), r̂(φ) := r̂(Φ) where the sum is over representatives of P(φ)/ ∼.
Lemma 15.11. Let φ ∈ Out(Fn ) and k > 0 such that ψ := φk is rotationless. Then
r̂(ψ) ≥ r̂(φ).
Proof. Assuming without loss that r̂(φ) > 0, let Φ1 , . . . , Φs , . . . Φm be representatives
of P(φ)/ ∼ where Fix(Φi ) ≥ 2 if and only if i ≤ s. Let {Ψj } be representatives of
P(ψ)/ ∼. For each 1 ≤ i ≤ s there exists j = p(i) such that Φki ∼ Ψj . If j = p(i)
then there exists a ∈ Fn such that Ψj = ia Φki ia−1 . Replacing Φi by ia Φia−1 , we have
Φki = Ψj . Thus
Φki = Ψp(i)
for 1 ≤ i ≤ s. We may assume the Ψj ’s are ordered so that the function p, whose
domain is {1, . . . , s}, has image {1, . . . , t}.
It suffices to show that
t
s
X
X
r̂(Ψj ) ≥
r̂(Φi )
j=1

i=1

68

and so it also suffices to show that
r̂(Ψj ) ≥

X

r̂(Φi )

i∈p−1 (j)

for each 1 ≤ j ≤ t.
Fix j and let F = Fix(Ψj ). For each i ∈ p−1 (j), Φki = Ψj and so F = Fix(Φki ).
Thus, Φi preserves F, Fix(Φi ) ⊂ F and the restriction Φi |F is a finite order automorphism of F. Since F is its own normalizer (see the second bullet in the proof of
Lemma 3.12) the restriction φ|F ∈ Out(F) is well-defined and has finite order.
We claim that if i0 ∈ p−1 (j) and i0 6= i then the subgroups Fix(Φi ) and Fix(Φi0 ) are
not conjugate in Fn and hence not conjugate in F. Indeed, if Fix(Φi ) = h Fix(Φi0 )h−1
for some h ∈ Fn then Fix(Φi ) = Fix(ih Φi0 ih−1 ). Since these groups have rank at least
two and both Φi and ih Φi0 ih−1 represent φ, Φi = ih Φi0 ih−1 , in contradiction to the
assumption that Φi and Φi0 represent distinct isogredience classes.
By Culler’s Theorem 3.1 of [Cul84], applied to φ|F, the conjugacy classes in F
determined by the subgroups {Fix(Φi ) : i ∈ p−1 (j)} form a free factor system of
F. Since r̂(Ψj ) = rank(F) − 1 and r̂(Φi ) = rank(Fix(Φi )) − 1, the desired displayed
inequality holds.
Lemma 15.12. Suppose φ ∈ Out(Fn ) and k > 0 such that φk is rotationless. Then
j(φk ) ≥ j(φ).
Proof. By definition of j(φ), the lemma is a direct consequence of Lemmas 15.9 and
15.11.
Proposition 15.13. There is an algorithm to compute j(φ) for rotationless φ ∈
Out(Fn ).
Proof. This follows from Proposition 15.2 and the fact that j(φ) is the sum of i(φ)
and one half the number of non-linear NEG edges in any CT representing φ.
Proposition 15.14. For φ ∈ Out(Fn ), j(φ) ≤ n − 1.
Example 15.15. Start with the usual linear 2-rose a1 7→ a1 and a2 7→ a2 a1 . Further
2i+1
attach edges ai , 2 < i ≤ n, with ai 7→ a2i
. If we subdivide each ai , 2 < i ≤ n
2 ai a2
then the result f : G → G is a CT for a φ ∈ Out(Fn ). Here SN (f ) is the disjoint union
of a pair of eyeglasses and n − 2 lines each with two N EG-rays. Hence j(φ) = n − 1
and i(φ) = 1.
Proof of Proposition 15.14. By Lemma 15.12, we may assume that φ is rotationless.
Let f : G → G be a CT for φ. We use the terminology of Section 13. In particular,
∅ = G0 = Gl0 ⊂ Gl1 ⊂ Gl2 ⊂ · · · ⊂ GlK = GN = G
is the core filtration and ∆i χ− := χ− (Gli ) − χ− (Gli−1 ).
69

Recall that SN (f ) is built up in three stages: starting with principal vertices and
fixed edges, lollipops corresponding to linear edges, edges corresponding to EG Nielsen
paths, and then rays corresponding (perhaps not bijectively) to oriented edges in E are
added. For each 1 ≤ 1 ≤ K, define SN (k) to be the subgraph of SN (f ) corresponding
to Glk . More precisely, start with principal vertices in Glk and fixed edges in Glk ,
then add lollipops corresponding to linear edges in Glk and edges corresponding to
EG Nielsen paths in Glk and then add rays corresponding to oriented edges in E ∩Glk .
For each component Γ of SN (k) define
1
1
j(Γ) := rank(Γ) + a(Γ) + b(Γ) − 1
2
2
where a(Γ) is the number of ends of Γ and b(Γ) is the number of N EG-rays of Γ.
Then define
X
j(Γ)
j(k) =
Γ

where the sum is taken over all components Γ of SN (k). Using Remark 12.6, j(SN (f )) =
j(φ) = j(K). Proposition 15.14 therefore follows from the more general inequality
j(k) ≤ χ− (Glk )

(∗k )

for 0 ≤ k ≤ K, which we will prove by induction on k.
The k = 0 case holds because j(∅) = χ− (∅) = 0.
Suppose that (∗k−1 ) holds for some k ∈ {1, . . . , K}. Define ∆k j := j(k) − j(k − 1).
We check that, in each of the cases of Lemma 13.2, ∆k j ≤ ∆k χ− . Once this has been
done, (∗k ) holds and the proposition is proven.
We use the following formula to compute χ− of a finite graph:
χ− = Σv (

val(v)
− 1)
2

where the sum is over the vertices v and val(v) is the number of directions at v.
Thus, ∆k χ− is the half number of “new” directions (two for each new edge) minus
the number of “new” vertices. As we proceed through the process of verifying ∆k j ≤
∆k χ− , we refer to vertices, directions, or rays of Glk or SN (k) previously considered
as old; others are new.
Lemma 3.8 implies that in cases (1a), (1b) and (1c) the endpoints of all new edges
are principal.
Case 1a. SN (k) is obtained from SN (k − 1) by attaching a circle component and
hence ∆k j = ∆k χ− = 0.
Case 1b. If the edge H := Hlk is fixed then SN (k) [resp. Glk ] is obtained from
SN (k − 1) [resp. Glk−1 ] by adding a new edge to old vertices. Hence ∆k j = ∆k χ− = 1.
We may therefore assume that the edge H is not fixed and so f (H) = H · u with u
non-trivial. In this case, SN (k) is obtained from SN (k − 1) by attaching to an old
70

vertex either a lollipop (if u is a Nielsen path) or the N EG-ray H · u · f (u) · f 2 (u) . . .
(otherwise). In each case, ∆k j = ∆k χ− = 1.
Case 1c. There are three subcases depending on whether or not the added edges
are linear. Their shared initial vertex is a new principal vertex in Glk and so SN (k) is
obtained from SN (k − 1) by adding a new component. The new component is a pair
of eyeglasses if both edges are linear. It is a one point union of an N EG-ray and a
lollipop if only one edge is linear, and it is a line with two N EG-rays if neither edge
is linear. In all cases, ∆k j = ∆χ− = 1.
Case 2. In Case 2, we will break the verification that ∆k j ≤ ∆k χ− into two
steps: first passing from Glk−1 to Guk and then passing from Guk to Glk .
Step 1: For the edge Hj with j as in Case (2a), the contribution to SN (k) is a
new NEG-ray [or lollipop] with new initial vertex. (The terminal direction in Hj is
not fixed and so does not contribute.) Thus, the contribution to ∆k j is 0 ( 21 to the
a-count since the ray is new, another 21 to the b-count since it is NEG [or 1 to rank]
and -1 for the new component). This is balanced with the contribution of Hj to
∆k χ− , namely 12 for each of its directions and -1 for the new vertex.
Step 2: For each vertex v ∈ Hlk , let ∆k j(v) and ∆k χ− (v) be the contributions to
∆k j and ∆k χ− coming from v and the Hlk -directions that are incident to v. For each
principal vertex v ∈ Hlk let κ(v) be the number of Hlk -directions that are incident to
v and not fixed. If v ∈ Hlk is not principal let κ(v) = val(v) − 2. Since each direction
we encounter in this step is contained in Hlk , and is hence EG, the b-count does not
change.
As a first case assume that there are no indivisible Nielsen paths of height lk . If v
is not principal then ∆k j(v) = 0. By Lemma 3.8, v is new so the directions incident
to v are all in Hlk and ∆k χ− (v) = 21 (val(v) − 2) = 12 κ(v). Thus ∆k χ− (v) − ∆k j(v) =
1
κ(v) ≥ 0.
2
We next consider principal v, letting L(v) be the number of fixed Hlk -directions
that are based at v. Thus L(v) + κ(v) is the number of Hlk -directions that are based
at v. If v is old then ∆k j(v) = 21 L(v) and ∆k χ− (v) = 12 (L(v) + κ(v)). If v is new
then ∆k j(v) = 12 L(v) − 1 and ∆k χ− (v) = 12 (L(v) + κ(v)) − 1. As in the previous case,
∆k χ− (v) − ∆k j(v) = 21 κ(v) ≥ 0.
The second and final case is that there is an indivisible Nielsen path ρ of height
lk . By [FH11, Lemma 4.24], lk = uk + 1. From [BFH00, Lemma 5.1.7] and [FH11,
Corollary 4.19] it follows that if the endpoints w, w0 of ρ are distinct then at least one
of w, w0 is new and if w = w0 then w is new. Let d and d0 be the directions determined
by ρ at w and w0 respectively.
Let V be the set of vertices of Hlk that are not endpoints of ρ. Each v ∈ V is
handled as in the no Nielsen path case. The conclusion is that
X

∆k χ− (v) −

v∈V

X

∆k j(v) =

v∈V

X1
v∈V

−

2

κ(v) ≥ 0

Let ∆k j(ρ) and ∆k χ (ρ) be the contributions to ∆k j and ∆k χ− coming from the
71

endpoints of ρ and the Hlk -directions that are incident to the endpoints of ρ. The
remaining analysis breaks up into subcases as follows.
• Suppose that ρ is a closed path based at a new vertex w. The change in CSN (k)
corresponding to w is the addition of a new vertex w, an edge representing ρ
with both endpoints at w, one ray for each fixed Hlk -direction based at w other
than d and d0 and then one ray corresponding to d and d0 . (See Section 12.) We
therefore have
1
1
1
∆k j(ρ) = 1 + (L(w) − 1) − 1 = L(w) −
2
2
2
1
∆k χ− (ρ) = (L(w) + κ(w)) − 1
2
Thus
1
∆k χ− (ρ) − ∆k j(ρ) = (κ(w) − 1)
2
Since there is always at least one illegal turn between Hlk -directions (for example, the one in ρ) there must be at least one vertex v ∈ V ∪ {w} with
−
κ(v)
P 6= 0. We conclude that ∆k j ≤ ∆k χ as desired with equality if and only
if
κ(v) = 1 where the sum is taken over all vertices in Hik .
• Suppose that w is new and w0 is old. The change in CS(k) corresponding to w
and w0 is the addition of a new vertex w, an edge representing ρ connecting w
to w0 , one ray for each fixed Hlk -direction based at w or w0 other than d and d0
and then one ray corresponding to d and d0 . This yields
1
1
∆k j(ρ) = (L(w) + L(w0 )) −
2
2
1
∆k χ− (ρ) = (L(w) + L(w0 ) + κ(w) + κ(w0 )) − 1
2
and the proof concludes as in the previous case.
• Suppose that w and w0 are distinct and both new. The change in CS(k) corresponding to w and w0 is the addition of two new vertices, an edge representing
ρ connecting them, one ray for each fixed Hlk -direction based at w or w0 other
than d and d0 and then one ray corresponding to d and d0 . The calculation is
the same as in the previous case.

We have the following two corollaries to the proof of Proposition 15.14.
72

Corollary 15.16. If G has no EG-strata then j(φ) = n − 1. If G has an EG-stratum
without Nielsen paths, then j(φ) < n − 1.
For the next corollary, recall (Sections 3.2 and 12.1) that there are bijections
between Nielsen classes of principal vertices of G and isogredience classes in P(φ) and
the set of components of SN (f ).
Corollary 15.17.
N EG.

(1) Suppose that SN (f, [v]) is a line L. Then one of its rays is

(2) Each SN (f, [v]) contributes at least 1/2 to j(φ).
(3) |[P(φ)]| ≤ 2j(φ), i.e. SN (f ) has at most 2j(φ) components.
Proof. (3) follows from (2) We will prove (1) and (2) simultaneously.
Since SN (f, [v]) is a weakly core graph we may assume that each vertex of SN (f, [v])
has valence two. In particularly, if [w] = [v] then w is not the endpoint of an indivisible Nielsen path (see Section 12) and w has only two gates in G. We view SN (f ) as
being built up as in the proof of Proposition 15.14. Let w be the lowest principal vertex satisfying [w] = [v] and let Glk be the lowest core filtration element that contains
w. We consider the cases enumerated in the proof of Proposition 15.14. Case (1a) is
ruled out because w is principal and so would have at least three gates. Since w is
new in Hlk we are not in case (1b). If we are in case (1c) then both edges must be
non-linear and j(Γ) ≥ 1. It remains to rule out case (2). Since w is a new vertex in
the EG strata Hlk there are at least two gates in Hlk based at w. Since w is principal
but is is not the endpoint of an indivisible Nielsen path, there must be at least three
gates at w. This completes the proof of (1) and (2).

Corollary 15.18. | ∪Φ∈P(φ) Fix+ (∂Φ) /Fn | ≤ 6(n − 1).
Proof.
j(φ) =

X

j(SN (f, [v])) ≥

[v]

X a(SN (f, [v])
− 1)
(
2
[v]

|ends of SN (f )|
− |components of SN (f )|
2

1
≥ · | ∪Φ∈P(φ) Fix+ (∂Φ) /Fn }| − 2j(φ)
2

Thus | ∪Φ∈P(φ) Fix+ (∂Φ) /Fn | ≤ 6j(φ) ≤ 6(n − 1) by Proposition 15.14.
=

Remark 15.19. We commented in Remark 3.15 how Proposition 15.14 could be used
to improve the bound in Lemma 3.13 and hence also Corollary 3.14. With more care,
Proposition 15.14 could be used to further improve this bound.

73

16

Appendix: Hyperbolic and atoroidal automorphisms

In this appendix we reprove a result of Brinkmann (Lemma 16.2) and a result of
Kapovich (Corollary 16.4).
Definition 16.1. An outer automorphism φ ∈ Out(Fn ) is hyperbolic if for some
N > 0 and λ > 1,
λkαk ≤ max{kφN (α)k, kφ−N (α)k}
for all non-trivial conjugacy classes α in Fn . We say φ is atoroidal if φ has no nontrivial periodic conjugacy classes. Φ ∈ Aut(Fn ) is hyperbolic if for some N > 0 and
λ > 1,
λ|a| ≤ max{|ΦN (a)|, |Φ−N (a)|}
for all non-trivial a in Fn . Here k · k and | · | denote respectively reduced word length
and word length with respect to a fixed basis for Fn . The mapping torus MΦ of
Φ ∈ Aut(Fn ) is the group with presentation hFn , t | tat−1 = Φ(a) for each a ∈ Fn i.
Lemma 16.2 ([Bri00]). Suppose that no conjugacy class in Fn is fixed by an iterate
of φ. Then φ is hyperbolic.
±
Proof. Suppose that Λ±
1 , . . . , Λm are the lamination pairs for φ. After replacing φ by
an iterate, we may assume that φ and φ−1 are rotationless. Since φ does not fix any
conjugacy classes, each Λ±
i is non-geometric, and so ([HM, Part III Theorem F]; see
also [BFH00, Definition 5.1.4 and Theorem 6.0.1]) there is a φ-invariant free factor
system Ai for which the following are equivalent for each conjugacy class [a] in Fn .

• [a] is not weakly attracted to Λ+
i under iteration by φ.
−1
• [a] is not weakly attracted to Λ−
i under iteration by φ .

• [a] is carried by Ai .
In particular, Ai does not carry Λ±
i .
We claim that no line is carried by every Ai . If this failed, then one could choose
free factors Ai such that [Ai ] is a component of Ai and such that A := A1 ∩ . . . ∩ Am
is non-trivial. Thus A is a non-trivial free factor that does not carry any Λ±
i . There
is a CT representing φ in which [A] is represented by a filtration element. The
lowest stratum cannot be EG and so must be a fixed loop. But that contradicts the
assumption that there are no φ-invariant conjugacy classes and so completes the proof
of the claim.
Choose CTs f : G → G representing φ and f 0 : G0 → G0 representing φ−1 . Let
λi the expansion factor ([BFH00, Definition 3.3.2]) for φ with respect to Λ+
i , µi the
−
−1
expansion factor for φ with respect to Λi and λ = min{λi , µi } > 1.

74

Let Hi ⊂ G be the stratum corresponding to Λ+
i . By [BFH00, Lemma 4.2.2] there
+
exists a subpath δi ⊂ G of Λ+
(any
subpath
of
Λ
that
crosses sufficiently many edges
i
i
of Hi will do) with the following property: if σ ⊂ G is a circuit or path and σ0 ⊂ σ is
a copy of δi or its inverse δ̄i , then there is a splitting of σ in which one of the terms
is an edge of Hi contained in σ0 . Let B + (σ) be the maximum number of disjoint
subpaths of σ that are copies of some δi or δ̄i . Then σ has a splitting in which B + (σ)
terms are single edges in EG strata. It follows that
|f#k (σ)| > CB + (σ)λk
for all k ≥ 1 where C is a positive constant and | · | denotes length.
−
Define δi0 ⊂ G0 and B − (σ 0 ) symmetrically replacing Λ+
i and f : G → G with Λi
with f 0 : G0 → G0 . Each path or circuit σ 0 ⊂ G0 has a splitting in which B − (σ 0 ) terms
are single edges in EG strata of f 0 : G0 → G0 . After decreasing C if necessary, we
have
|(f 0 )k# (σ 0 )| > CB − (σ 0 )λk
for all k ≥ 1.
Let h : G → G0 be a homotopy equivalence that preserves markings. After
replacing φ (and hence f and f 0 ) by an iterate, we may assume that for each i the
neighborhood V (δi ) of Λ+
i consisting of lines that contain either δi or δ̄i as a subpath
0
is mapped into itself by φ and that the neighborhood V (δi0 ) of Λ−
i determined by δi is
mapped into itself by φ−1 . By [HM, Part III Theorem H] there is a positive integer
Ni so that if β ⊂ G is a line that is not carried by Ai then either h# (β) contains a
copy of δi0 or δ̄i0 or f#Ni (β) contains a copy of δi or δ̄i . Let N := max{Ni }. Since f#
maps each V (δi ) into itself and since no line is carried by Ai for all i, we have
B + (f#N (β)) + B − (h# (β)) ≥ 1
for all lines β.
Recall (see [HM, Part I Section 1.1.6]) that for all paths α ⊂ G there is a path
h## (α) ⊂ G0 obtained from h# (σ) by removing initial and terminal segments of
length at most the bounded cancellation constant of h and satisfying h## (V (α)) ⊂
V (h# (α)). We claim that there exists a positive integer L so that if σ ⊂ G has length
at least L then
B + (f#N (σ)) + B − (h## (σ)) ≥ 1
Indeed, if this fails then there exists Lj → ∞ and paths σj ⊂ G with length ≥ Lj
such that for all 1 ≤ i ≤ m
• h## (σj ) does not contain δi0 or δ̄i0 as a subpath.
• f#N (σj ) does not contain δi or δ̄i as a subpath.

75

By focusing on the ‘middle’ of each σj and passing to a subsequence we may assume
that there are subpaths βj ⊂ σj such that β1 ⊂ β2 ⊂ . . . is an increasing sequence of
paths whose union is a line β ⊂ G. As verified above, there exists 1 ≤ i ≤ m such that
Ai does not carry β. By [HM, Part I Lemma 1.6(3)] h## (βj ) ⊂ h## (βj+1 ) ∩ h## (σj )
and h# (β) is the union of the h## (βj )’s. It follows that h# (β) does not contain δi0
N
or δ̄i0 as a subpath and so f#N (β) must contain a copy of δi or δ̄i . But then f##
(βj )
N
contains a copy of δi or δ̄i for all sufficiently large j and hence f# (σj ) contains a copy
of δi or δ̄i for all sufficiently large j. This contradiction completes the proof of the
claim.
We are now ready to complete the proof. After replacing φ with φN , we may
] subpaths
assume that N = 1. Given a circuit σ ⊂ G with |σ| ≥ 2L divide it into [ |σ|
L
σl of length at least L where [·] is the greatest integer function. Applying the preceding
claim and the fact that the f## (σl )’s are disjoint subpaths of f# (σ) we have
max{B + (f# (σ)), B − (σ 0 )} ≥ [

|σ|
]
2L

In conjunction with the above displayed inequalities this completes the proof of the
lemma if |σ̂| ≥ 2L. As there are only finitely many remaining σ̂ and none of these is
fixed by an iterate of φ we are done.
Proposition 16.3. Let Φ ∈ Aut(Fn ) represent φ ∈ Out(Fn ). The following are
equivalent.
(1) φ is atoroidal.
(2) φ is hyperbolic.
(3) Φ is hyperbolic.
(4) MΦ is hyperbolic.
Proof. (1) =⇒ (2) is Lemma 16.2. (2) =⇒ (3) follows from the proof of Theorem 5.1 of [BFH97]. (3) =⇒ (4) is a consequence of the first corollary of Section 5
of [BF92]. (4) =⇒ (1) since otherwise MΦ contains Z2 .
Corollary 16.4 ([Kap00]; see also [Dah16, page 2]). There is an algorithm with input
φ ∈ Out(Fn ) that outputs YES or NO depending on whether or not φ is hyperbolic.
Proof. Construct a CT f : G → G for a φM with M as in Corollary 3.14. By Proposition 16.3, φ is hyperbolic iff φ is atoroidal. By Lemma 9.6(2), φ is atoroidal if and only
if S(f ) has no circuits and this can be checked algorithmically; see Remark 9.5.

76

References
[BF92]

M. Bestvina and M. Feighn, A combination theorem for negatively curved
groups, J. Differential Geom. 35 (1992), no. 1, 85–101. MR 93d:53053

[BF14]

Mladen Bestvina and Mark Feighn, Hyperbolicity of the complex of free
factors, Adv. Math. 256 (2014), 104–155. MR 3177291

[BFH97] M. Bestvina, M. Feighn, and M. Handel, Laminations, trees, and irreducible automorphisms of free groups, Geom. Funct. Anal. 7 (1997), no. 2,
215–244. MR 98c:20045
[BFH00] Mladen Bestvina, Mark Feighn, and Michael Handel, The Tits alternative
for Out(Fn ). I. Dynamics of exponentially-growing automorphisms, Ann.
of Math. (2) 151 (2000), no. 2, 517–623. MR 1 765 705
[BH92]

Mladen Bestvina and Michael Handel, Train tracks and automorphisms of
free groups, Ann. of Math. (2) 135 (1992), no. 1, 1–51.

[BM16]

Oleg Bogopolski and Olga Maslakova, An algorithm for finding a basis of
the fixed point subgroup of an automorphism of a free group, Internat. J.
Algebra Comput. 26 (2016), no. 1, 29–67. MR 3463201

[Bri00]

P. Brinkmann, Hyperbolic automorphisms of free groups, Geom. Funct.
Anal. 10 (2000), no. 5, 1071–1089. MR 1800064 (2001m:20061)

[BT68]

Gilbert Baumslag and Tekla Taylor, The centre of groups with one defining
relator, Math. Ann. 175 (1968), 315–319. MR 0222144 (36 #5196)

[CG10]

A. Clifford and R. Z. Goldstein, Subgroups of free groups and primitive elements, J. Group Theory 13 (2010), no. 4, 601–611. MR 2661660
(2011g:20028)

[CMP15] Matt Clay, Johanna Mangahas, and Alexandra Pettet, An algorithm to
detect full irreducibility by bounding the volume of periodic free factors,
Michigan Math. J. 64 (2015), no. 2, 279–292. MR 3359026
[Coo87]

Daryl Cooper, Automorphisms of free groups have finitely generated fixed
point sets, J. Algebra 111 (1987), no. 2, 453–456. MR 89a:20024

[Cul84]

Marc Culler, Finite groups of outer automorphisms of a free group, Contributions to group theory, Contemp. Math., vol. 33, Amer. Math. Soc.,
Providence, RI, 1984, pp. 197–207. MR 767107

[Dah16]

François Dahmani, On suspensions and conjugacy of hyperbolic automorphisms, Trans. Amer. Math. Soc. 368 (2016), no. 8, 5565–5577. MR
3458391
77

[DF05]

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

[Dic14]

Warren Dicks, On free-group algorithms that sandwich a subgroup between
free-product factors, J. Group Theory 17 (2014), no. 1, 13–28. MR 3176649

[DV96]

Warren Dicks and Enric Ventura, The group fixed by a family of injective endomorphisms of a free group, Contemporary Mathematics, vol.
195, American Mathematical Society, Providence, RI, 1996. MR 1385923
(97h:20030)

[FH09]

Mark Feighn and Michael Handel, Abelian subgroups of Out(Fn ), Geom.
Topol. 13 (2009), no. 3, 1657–1727. MR MR2496054

[FH11]

, The recognition theorem for Out(Fn ), Groups Geom. Dyn. 5
(2011), no. 1, 39–106. MR 2763779 (2012b:20061)

[Ger84]

S. M. Gersten, On Whitehead’s algorithm, Bull. Amer. Math. Soc. (N.S.)
10 (1984), no. 2, 281–284. MR 85g:20051

[GJLL98] Damien Gaboriau, Andre Jaeger, Gilbert Levitt, and Martin Lustig, An
index for counting fixed points of automorphisms of free groups, Duke Math.
J. 93 (1998), no. 3, 425–452.
[HM]

M. Handel and L. Mosher, Subgroup decomposition in Out(Fn ), to appear
in Mem. Amer. Math. Soc.

[HM11]

Michael Handel and Lee Mosher, Axes in outer space, Mem. Amer. Math.
Soc. 213 (2011), no. 1004, vi+104. MR 2858636

[IKT90]

W. Imrich, S. Krstić, and E. C. Turner, On the rank of fixed point sets
of automorphisms of free groups, Cycles and rays (Montreal, PQ, 1987),
NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 301, Kluwer Acad.
Publ., Dordrecht, 1990, pp. 113–122. MR 1096989

[Kap]

Ilya Kapovich, Detecting fully irreducible automorphisms: a polynomial
time algorithm. With an appendix by Mark C. Bell, arXiv:1609.03820.

[Kap00]

Ilya Kapovich, Mapping tori of endomorphisms of free groups, Comm. Algebra 28 (2000), no. 6, 2895–2917. MR 1757436 (2001c:20098)

[Kap14]

, Algorithmic detectability of iwip automorphisms, Bull. Lond.
Math. Soc. 46 (2014), no. 2, 279–290. MR 3194747

78

[LL08]

Gilbert Levitt and Martin Lustig, Automorphisms of free groups have
asymptotically periodic dynamics, J. Reine Angew. Math. 619 (2008), 1–36.
MR 2414945

[Mar95]

Reiner Martin, Non-uniquely ergodic foliations of thin type, measured currents, and automorphisms of free groups, University of Utah, PhD thesis,
1995.

[Nie29]

Jakob Nielsen, Untersuchungen zur Topologie der geschlossenen zweiseitigen Flächen. II, Acta Math. 53 (1929), no. 1, 1–76. MR 1555290

[Nie86]

, Jakob Nielsen: collected mathematical papers. Vol. 2, Contemporary Mathematicians, Birkhäuser Boston, Inc., Boston, MA, 1986, Edited
and with a preface by Vagn Lundsgaard Hansen. MR 865336

[Sta83]

J. Stallings, Topology of finite graphs, Inv. Math. 71 (1983), 551–565.

79

