The Tits Alternative for Out(F_{n}) I:

Dynamics of Exponentially Growing Automorphisms

Mladen Bestvina, Mark Feighn, and Michael Handel

June 10, 1996 Preliminary Version

Contents

1 Overview 2

2 Introduction 6

3 Preliminaries 9 3.1 Relative Train Track Maps . . . . . . . . . . . . . . . . . . . . 9 3.2 Bi-Infinite Paths . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 Free Factors and Free Factor Systems . . . . . . . . . . . . . . 13

4 Expanding Laminations 17 4.1 Expansion Factors . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2 Detecting F_{2} via Laminations . . . . . . . . . . . . . . . . . . 29

5 Splittings 32

6 Improved Relative Train Track Maps 37 6.1 Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.2 Nielsen Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.3 Geometric Strata . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.4 Sliding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 6.5 Splitting Basic Paths . . . . . . . . . . . . . . . . . . . . . . . 61 6.6 Proof of Theorem 6.4 . . . . . . . . . . . . . . . . . . . . . . . 66 6.7 Proof of Theorem 6.8 . . . . . . . . . . . . . . . . . . . . . . 68

7 The Weak Attraction Theorem 73

8 Reduction to PG(F_{n}) 88

1 Overview

A group satisfies the Tits Alternative if each of its subgroups either contains a free group of rank two or is virtually solvable. The Tits Alternative derives its name from the seminal result of J. Tits [Tit72] that finitely generated linear groups satisfy this alternative. J. McCarthy [McC85] and N. Ivanov [Iva84] have shown that mapping class groups of (compact) surfaces also satisfy this alternative. J. Birman, A. Lubotzky, and J. McCarthy [BLM83] complement the Tits Alternative for surface mapping class groups by showing that solvable subgroups of such are virtually finitely generated free abelian of predictable index. The analogue fails for linear groups since, for example, GL(3; ℤ) contains the Heisenberg group.

The outer automorphism group Out(F_{n}) of a free group F_{n} of finite rank reflects the nature of both linear and mapping class groups. Indeed, it maps onto GL(n; ℤ) and contains the mapping class group MCG(S) of a compact surface S with fundamental group F_{n}. E. Formanek and C. Procesi [FP92] have shown that Out(F_{n}) is not linear if n > 3. It is unknown if mapping class groups of compact surfaces are all linear.

In a series of three papers we prove the following two main theorems.

Theorem 1.1. (Tits Alternative for Out(F_{n})) [BFH96a]) The group Out(F_{n}) satisfies the Tits Alternative.

Theorem 1.2. (Main Theorem of [BFH96c]) A solvable subgroup of Out(F_{n}) has a finitely generated free abelian subgroup of index at most 3^{5n^{2}}.

The rank of an abelian subgroup of Out(F_{n}) is bounded by vcd(Out(F_{n})) = 2n − 3 for n > 1 [CV86].

Although our work focuses on these results, our approach has always been toward developing a general understanding of subgroups of Out(F_{n}) and their dynamics on certain spaces of trees and bi-infinite paths. The introductions to each of the three papers take up this more general viewpoint. In the rest of this section, we content ourselves with describing how the proof of the main theorems are divided among the three papers, along the way making comparisons to results for GL(n, ℤ) and MCG(S). An introduction to this, the first paper of the series, appears after this overview.

An element O of Out(F_{n}) or MCG(S) (respectively GL(n, ℤ)) has polynomial growth if for each conjugacy class [γ] of an element in F_{n} (respectively ℤ^{n}) the word length with respect to some fixed finite generating set for F_{n} (respectively norm) of O^{i}([γ]) grows at most polynomially. An element O of Out(F_{n}) or MCG(S) (respectively GL(n, ℤ)) has exponential growth if for some conjugacy class this sequence grows at least exponentially. Let GMO denote either GL(n, ℤ), MCG(S), or Out(F_{n}). If an element of GMO does not have polynomial growth then it has exponential growth (see for example [BH92]). A subgroup of GMO is said to be P G if all of its elements have polynomial growth. Nonabelian free groups play an important role in these papers. More generally, we consider subgroups H of GMO that do not contain a nonabelian free subgroup with the property that all of its nontrivial elements have exponential growth. Such a subgroup is said to be W EF (W ithout Exponential F ree subgroups of rank 2). A goal of the first paper in our series is the following theorem which is known for MCG(S) and GL(n, ℤ). As a corollary, the Tits Alternative holds for Out(F_{n}) if it holds for its P G subgroups.

Theorem 1.3. (Theorem 8.1 and Remark 8.2) of [BFH96a]) Let H be a W EF subgroup of Out(F_{n}). There is a finitely generated free abelian group A and a map

Φ : H → A

such that Ker(Φ) consists of the elements of H with polynomial growth.

In the case of GL(n, ℤ) there is a finite set S ⊂ ℂ^{n} of eigenvectors for H such that Φ is the product of the associated eigenvalue maps. More precisely, there is a power m > 0 such that, for O ∈ H and s ∈ S, s is an eigenvector of O^{m}. The mth positive root of the absolute value of the corresponding eigenvalue gives rise to a homomorphism Φ_{s} : H → ℝ^{∗} and Φ is the product of the Φ_{s}’s. In the case of MCG(S), the eigenvectors are replaced by stable laminations. In the case of Out(F_{n}), the eigenvectors are replaced by a generalization of these laminations. It is curious that in the case of MCG(S) and Out(F_{n}) the image of each Φ_{s} is discrete. But, in the case of GL(n, ℤ), even though the image of Φ is discrete, the image of each Φ_{s} need not be. Thus, MCG(S) and Out(F_{n}) behave more like lattices in rank 1 Lie groups in this regard.

The second paper in the series is a study of P G subgroups of Out(F_{n}). A P G subgroup of MCG(S) is virtually abelian. In fact, it has a finite index subgroup generated by Dehn twists in a set of pairwise disjoint simple closed curves [BLM83]. The structure of P G subgroups of GL(n, ℤ) is richer. An element of GL(n, ℤ) is unipotent if it is conjugate to an upper triangular matrix with ones on the diagonal. A subgroup of GL(n, ℤ) is unipotent if all of its elements are unipotent. A P G subgroup H of GL(n, ℤ) has a finite index subgroup that is unipotent. In fact, the kernel of the action of H on Hom(F_{n}; ℤ/3ℤ) is unipotent, see for example Proposition 3.8*** ^{1} of [BFH96b].

The picture is clarified by a special case of the Kolchin theorem [Ser92] which shows that for a unipotent group it is possible to find a basis with respect to which all elements are simultaneously upper triangular. Here and throughout, a superscript can denote conjugation.

Theorem 1.4. (Kolchin) Let H be a unipotent subgroup of GL(n, ℤ). There is M ∈ GL(n, ℤ) such that H^{M} is contained in the subgroup of upper triangular matrices with ones on the diagonal.

In particular, W EF subgroups of GL(n, ℤ) are virtually solvable.

There is a parallel story for Out(F_{n}). We say that O ∈ Out(F_{n}) is UP G if it has polynomial growth and its action on Hom(F_{n}; ℤ) is unipotent. Equivalently (Proposition 3.8*** of [BFH96b]), O is UP G if and only if it may be represented by a relative train track map f : G → G such that G has a filtration

∅ = G_{0} ⊂ G_{1} ⊂ ⋯ ⊂ G_{k} = G

where G_{i} is obtained from G_{i−1} by adding an edge E_{i} and such that there are loops u_{i} in G_{i−1} with f(E_{i}) = E_{i}u_{i}. Such a train track representative is said to be unipotent. A subgroup of Out(F_{n}) is said to be UP G if all of its elements are UP G. A P G subgroup H of Out(F_{n}) has a finite index subgroup that is UP G. In fact, the kernel of the action of H on Hom(F_{n}; ℤ/3ℤ) is UP G (Proposition 3.8*** of [BFH96b]).

A focus of our second paper [BFH96b] is the following analogue of the Kolchin theorem.

Theorem 1.5. (Kolchin Theorem for Out(F_{n}) in [BFH96b]) Let H be a UP G subgroup of Out(F_{n}). There is a filtered marked graph G as above such that each element of H has a unipotent representative on G.

1The numbering is subject to change

The Tits Alternative for Out(F_{n}) follows quickly (see the introduction to [BFH96b]).

The main result of the third paper [BFH96c] is Theorem 1.2 that solvable subgroups of Out(F_{n}) are virtually abelian. In this regard, Out(F_{n}) behaves like MCG(S).

It is striking that nonabelian unipotent subgroups of GL(n, ℤ) are absent in Out(F_{n}). From the Kolchin Theorem 1.4, it follows that every unipotent subgroup H of GL(n; ℤ) is the image of a UP G subgroup Ĥ of Out(F_{n}). Thus, the rich structure of unipotent subgroups of GL(n, ℤ) can be found in UP G subgroups of Out(F_{n}). For example, let H be the Heisenberg group

< a, b, c|[a, c] = 1 = [b, c], [a, b] = c >

which may also be described as the set of upper triangular integral matrices with ones on the diagonal. In this case, we may take Ĥ :=< â, b̂, ĉ > where F_{3} :=< x, y, z >, â(y) = yx and fixes x and z, b̂(z) = zy and fixes x and y, and ĉ(z) = zx and fixes x and y. The subgroup of Ĥ generated by b̂ and ĉ is free of rank 2. More generally, the image of a W EF subgroup of Out(F_{n}) is solvable in GL(n, ℤ). However, there are abelian subgroups H of GL(n, ℤ) that are not the image of any W EF subgroup of Out(F_{n}) under the canonical map. Such a group is

< [ \begin{matrix}1 & −2 & 1 \\ 0 & −2 & 1 \\ 1 & −1 & 0 \end{matrix} ] , [ \begin{matrix}−2 & 1 & 0 \\ −1 & 0 & 1 \\ −2 & 1 & 1 \end{matrix} ] >

(lifts of nontrivial elements would have to be irreducible by [GS91] and then the statement follows from [BFH95]).

A proof of the Tits Alternative for a special class of subgroups of Out(F_{n}) is treated in [BFH95]. Independent of the other three, this paper can serve as an introduction to some of the methods of [BFH96a]. In the first paper [BFH96a] of the series, the train track methods of [BH92] are improved and used to study the dynamics of subgroups of F_{n} on the space of bi-infinite lines is examined. In the second [BFH96b], the focus shifts to actions of UP G subgroups of Out(F_{n}) on spaces of real trees. Finally, in the third paper [BFH96c], a mixture of train track methods and real tree methods are found. The reader is referred to the introductions to the individual papers for more details.

F. Paulin [Pau] has proved that an infinite nilpotent group of outer automorphisms of any word hyperbolic group fixes projectively an action on a real tree. H. Bass and A. Lubotzky [BL] have shown that solvable subgroups of Out(F_{n}) are virtually polycyclic. Our three papers also have connections with recent work [Sela] [Selb] of Z. Sela.

2 Introduction

Throughout this paper F_{n} is the free group of rank n, Out(F_{n}) is the group of outer automorphims of F_{n} and MCG(S) is the mapping class group of the compact surface S. An outer automorphism O is said to have polynomial growth if the word length of the iterates O^{k}([γ]) grow at most polynomially in k for each conjugacy class [γ] in F_{n}. The set of polynomial growth outer automorphisms is denoted by P G(F_{n}). In the analogy with MCG(S), elements of P G(F_{n}) correspond to mapping classes that have no pseudo-Anosov components or equivalently to mapping classes that are compositions of Dehn twists along disjoint simple closed curves. The main result in this paper is the following reduction of the Tits Alternative for Out(F_{n}) to the Tits Alternative for subgroups of P G(F_{n}).

Theorem 8.1 If H ⊂ Out(F_{n}) does not contain a free subgroup of rank two, then there exists k ≥ 0 and a homomorphism Φ : H → ℤ^{k} with Ker(Φ) ⊂ PG(F_{n}).

The proof of Theorem 8.1 is dynamical in nature with primary focus on the expanding lamination pairs associated to an outer automorphism O and on the basin of attraction of these laminations for the action of O on the space of birecurrent paths. This approach is motivated by consideration of Thurston’s work [Thu88] on MCG(S) and it is helpful to keep the surface analogues in mind while reading. To that end, we now outline our proof in the special case that H is a subgroup of MCG(S). There are three main ingredients.

Associated to each pseudo-Anosov mapping class ϕ is a pair of minimal geodesic laminations Λ^{+} and Λ^{−}. (Definitions and details on pseudo-Anosov theory can be found in [Thu88] or [FLP79].) For any simple closed geodesic γ ⊂ S, the iterates ϕ_{#}^{n}(γ) and ϕ_{#}^{−n}(γ) limit on Λ^{+} and Λ^{−} respectively. This limiting is usually thought of as taking place in the space of measured laminations, but it is useful to think of a weaker, more topological type of convergence. Namely, we say that γ is weakly attracted to Λ^{+} under the action of ϕ if for all choices of length L and closeness ϵ > 0, ϕ_{#}^{n}(γ) contains a subpath of length L that is ϵ-parallel to a subpath of some (and hence every) leaf of Λ^{+} for all sufficiently large n. This makes sense for arbitrary bi-infinite geodesics, not just simple ones, and can be easily generalized from MCG(S) to Out(F_{n}). To avoid special cases, we restrict our attention to geodesics that are contained in their own forward and backward limit sets. Every such birecurrent geodesic path γ in S that is not a leaf of Λ^{−} is weakly attracted to Λ^{+} by the action of ϕ. Similarly, every birecurrent geodesic in S that is not a leaf of Λ^{+} is weakly attracted to Λ^{−} by the action of ϕ^{−1}.

If the mapping class ϕ is reducible with pseudo-Anosov components S_{1}, ⋯, S_{k}, then associated to each S_{i} is a pair of minimal geodesic laminations Λ_{i}^{+} and Λ_{i}^{−}. In this setting, the difference between weak attraction and attraction in the measured lamination sense (which we now call strong attraction) is more interesting. If γ ⊂ S_{i} and γ is not a leaf of Λ_{i}^{−}, then γ is attracted to Λ_{i}^{+} in both senses. However if γ intersects the interior of S_{i} but is not entirely contained in S_{i}, then γ is weakly attracted to Λ_{i}^{+} but need not be strongly attracted to Λ_{i}^{+}. The former requires only that iterates of γ develop at least one long path that is close to Λ_{i}^{+}, while that latter requires that ‘almost all’ of ϕ^{n}(γ) be close to Λ_{i}^{+}. Thus Λ_{i}^{+} strongly attracts the geodesics in the subsurface S_{i} but weakly attracts the geodesics that are not entirely contained in the complementary subsurface S \ S_{i}. The weak basin of attraction is larger than the strong basin of attraction. The analogous statements hold for Λ_{i}^{−}.

The second ingredient in the proof is the ‘expansion factor’ homomorphism whose existence is a consequence of the fact that each Λ_{i}^{+} is uniquely ergodic. Any mapping class ψ that topologically fixes Λ_{i}^{+} must also projectively fix the transverse measure on Λ_{i}^{+}. If μ_{i} is the factor by which ψ multiplies the transverse measure, then the assignment ψ ↦ log(μ_{i}(ψ)) is a homomorphism to a discrete subset of ℝ and so can be thought of as a homomorphism from the topological stabilizer of Λ_{i}^{+} to ℤ. Each ψ in the topological stabilizer preserves the subsurface S_{i}. If μ_{i}(ψ) > 1, then Λ^{+} is the expanding lamination for the restriction of ψ to S_{i}; if μ(ψ) < 1, then Λ^{+} is the expanding lamination for the restriction of ψ^{−1} to S_{i}; if μ(ψ) = 1, then ψ restricts to a linear growth automorphism of S_{i}.

The final ingredient in the proof is the observation that there is a uniform bound to the number of essential subsurfaces that can be disjointly embedded in S.

We can now outline the proof of the surface analog of Theorem 8.1. Suppose that H is a subgroup of MCG(S) and that ψ, ϕ ∈ H have pseudo-Anosov components S_{i} and T_{j} respectively. If S_{i} and T_{j} are distinct but have nonempty non-peripheral intersection, then a straightforward ‘Tits pingpong’ argument based on the weak attraction results stated above implies that H contains a free subgroup of rank two. We may therefore assume that there is a finite set of subsurfaces {S_{i}} with disjoint interiors and that each pseudo-Anosov component of each ψ ∈ H is one of these subsurfaces. After passing to a finite index subgroup, we may assume that S_{i} is ψ- invariant for each ψ ∈ H. The pingpong argument also shows that for each S_{i} the lamination pair Λ_{i}^{±} ⊂ S_{i} that ψ ∈ H assigns to S_{i} (if it does not restrict to a linear growth mapping class on S_{i}) is independent of ψ. A standard argument now implies that each Λ_{i}^{+} is topologically stabilized by every ψ ∈ H. The homomorphism Φ is then defined to be the direct sum of the ‘expansion factor’ homomorphisms defined by the Λ_{i}^{+}’s. If ψ is in the kernel of Φ then it has no pseudo-Anosov components and so is an element of P G(F_{n}).

We prove Theorem 8.1 by providing free group analogs of the three main ingredients. The paper is organized as follows. Section 3 contains some preliminary results about bi-infinite paths, relative train track maps [BH92] and free factor systems. In section 4 we define and characterize expanding lamination pairs Λ_{i}^{±}. (See also [Lus92]) We take the least structured point of view and think of laminations simply as closed subsets of bi-infinite paths. Λ_{i}^{±} are defined and studied using relative train track maps. We then show (Lemma 4.4) that the construction is independent of the choice of relative train track map and hence is determined by the outer automorphism O. Expansion factor homomorphisms are defined (Proposition 4.8) and the Tits pingpong argument is applied to give a criterion (Corollary 4.13), in terms of weak attraction, for detecting a free factor of rank two in a subgroup H of Out(F_{n}).

The Weak Attraction Theorem (Theorem 7.1) states if Λ^{+} is a ‘topmost’ expanding lamination for O, then ‘most’ birecurrent paths are attracted to Λ_{i}^{±} under the action of O. This is the key ingredient in the proof of Theorem 8.1.

As in [BH92], we use relative train track maps f : G → G to view an outer automorphism as being built up in stages. The marked graph G is broken up into strata (the difference between nested invariant subgraphs) that are somewhat analogous to the subsurfaces into which a reducible mapping class is divided. To study the iterated images of a bi-infinite path γ, we decompose it into non-interacting pieces that are dominated by a single stratum. This ‘splitting’ is the subject of section 5 and parts of section 6.

Section 6 is the most technical part of the paper. We modify and improve the train track methods of [BH92] to suit our present needs. A very detailed statement is given Theorem 6.4 and we refer the reader to the introduction to that section for an overview of its contents. Section 7 contains the statement and proof of the Weak Attraction Theorem. Section 8 contains the proof of Theorem 8.1, including the Out(F_{n}) analog of the third ingredient mentioned above in the case of the mapping class.

3 Preliminaries

3.1 Relative Train Track Maps

A marked graph is a graph G along with a homotopy equivalence τ : R_{n} → G from the rose R_{n} with n petals and vertex ∗. We assume that F_{n} is identified with π_{1}(R_{n}, ∗) and hence also with π_{1}(G, τ(∗)). A homotopy equivalence f : G → G induces an outer automorphism of π_{1}(G, τ(∗)) and so an outer automorphism O of F_{n}. If f maps vertices to vertices and if the restriction of f to each edge of G is an immersion, then we say that f : G → G is a topological representative of O.

A filtration for a topological representative f : G → G is an increasing sequence of (not necessarily connected) f- invariant subgraphs ϕ = G_{0} ⊂ G_{1} ⊂ ⋯ ⊂ G_{m} = G. The subcomplex cl(G_{r} \ G_{r−1}) is denoted by H_{r} and called the r^{th} stratum. The edges of H_{r} determine a square matrix M_{r} called the transition submatrix for H_{r}; the ij^{th} entry of M_{r} is the number of times that the f-image of the j^{th} edge crosses the i^{th} edge in either direction.

We reserve the word path for an immersed image of an interval and circuit for the immersed image of a circle. If σ is a path or circuit, then we denote by [f(σ)] or f_{#}(σ) the unique path or circuit that is homotopic to f(σ) relative to endpoints, if any.

For any topological representative f : G → G and oriented edge E of G, let T f(E) be the initial oriented edge of the edge path f(E) and inductively define (T f)^{k}(E) = T ((T f)^{k−1}(E)). A turn in G is an unordered pair of oriented edges of G originating at a common vertex. The turn (E_{i}, E_{j}) is legal if (T f)^{k}(E_{i}) and (T f)^{k}(E_{j}) are distinct for all k ≥ 0 and is illegal otherwise. A circuit or path σ ⊂ G_{r} is r-legal if it does not contain any illegal turns in H_{r} (i.e. with both oriented edges in H_{r}).

A non-negative matrix M is irreducible if for each i and j there exists n > 0 so that the ij^{th} entry of M^{n} is positive. By enlarging the filtration if necessary, we may assume that each M_{r} is either the zero matrix or is irreducible. This gives us three kinds of strata. If M_{r} is the zero matrix, then H_{r} is a zero stratum . (These arise in the ‘core subdivision’ operation of [BH92].) If M_{r} is irreducible, then it has an associated Perron-Frobenius eigenvalue λ_{r} ≥ 1 [Sen81]. If λ_{r} ≥ 1, then H_{r} is an exponentially growing stratum; if λ_{r} = 1, then H_{r} is a non-exponentially growing stratum.

A topological representative f : G → G of O is a relative train track map with respect to the filtration ϕ = G_{0} ⊂ G_{1} ⋯ ⊂ G_{m} = G if each non-zero M_{r} is irreducible and if each exponentially growing stratum satisfies the following conditions.

1. If E is an oriented edge of H_{r}, then T f(E) is an oriented edge of H_{r}.

2. If β ⊂ G_{r−1} is a non-trivial path with endpoints in G_{r−1} ∩ H_{r}, then [f(β)] is non-trivial.

3. If σ ⊂ G_{r} is r-legal, then [f(σ)] is r-legal.

Complete details about relative train track maps can be found in [BH92].

The most important consequence of being a relative train track map is Lemma 5.11 of [BH92]. We repeat it here for the reader’s convenience.

Lemma 3.1. Suppose that f : G → G is a relative train track map, that H_{r} is an exponentially growing stratum and that σ = a_{1}b_{1}a_{2} … b_{l} is a decomposition of an r-legal path into subpaths where each a_{i} ⊂ H_{r} and each b_{j} ⊂ G_{r−1}. (Allow the possibility that a_{1} or b_{l} is trivial, but assume that the other subpaths are nontrivial.) Then [f(σ)] = f(a_{1})[f(b_{1})]f(a_{2}) … [f(b_{l})] and [f(σ)]is r-legal.

3.2 Bi-Infinite Paths

The action of an outer automorphism O on conjugacy classes in F_{n} can be realized as an action on circuits in any marked graph G. More precisely, if f : G → G is a topological representative of O and α is the unique circuit in G representing the conjugacy class [a] of a ∈ F_{n}, then f(α) is freely homotopic to the unique circuit [f(α)] that represents O([a]). Let B(G) be the space of unoriented bi-infinite paths (= immersed lines) in G. Following Nielsen, we use an end compactification to define a space B that can be thought of as the space of abstract unoriented bi-infinite paths. We then use the marking on G to identify B with B(G). The main result of this subsection is that the action of O on conjugacy classes extends to a homeomorphism O_{#} : B → B that can be represented on B(G) for any G. The details follow.

Let R_{n} be the rose with n petals and R̃_{n} its universal cover. The space of ends of R̃_{n} is a Cantor set that we denote ∂F_{n}. Define B = (∂F_{n} × ∂F_{n} \ Δ)/(F_{n} × Z_{2}), where Δ is the diagonal and where Z_{2} acts on ∂F_{n} × ∂F_{n} by interchanging the order of the components. For any pair of distinct elements (c_{1}, c_{2}) ∈ ∂F_{n} × ∂F_{n}, there is a unique unoriented properly embedded line σ̃ ⊂ R̃_{n} connecting the ends c_{1} and c_{2}. Since σ̃ is unoriented, it is associated to both (c_{1}, c_{2}) and (c_{2}, c_{1}). Thus the projected image σ ⊂ R_{n} of σ̃ is a biinfinite unoriented path in R_{n} that is determined by s = [c_{1}, c_{2}] ∈ B. The process is reversible, so we can identify B with B(R_{n}).

To simplify notation, we refer to a bi-infinite unoriented path as simply a line. Thus B is the space of abstract lines and B(R_{n}) is the space of lines in R_{n}. We will say that a finite path σ_{0} occurs as an unoriented subpath of a finite, infinite or bi-infinite path σ if σ_{0} occurs as a subpath of σ in either of the possible orientations on σ. If σ is a line, then we sometimes simply write that σ_{0} is a subpath of σ since the lack of orientation is implicit in the fact that σ is unoriented.

We topologize B(R_{n}) to make the identification with B a homeomorphism. For any finite path α ⊂ R_{n}, define N(α) ⊂ B(R_{n}) to be the set of lines in R_{n} that contain α as a subpath. If α̃ is a lift of α to R̃_{n} with endpoints p and q, let U ⊂ ∂F_{n} [respectively V ⊂ ∂F_{n}] be the set of elements whose closest point on α̃ is p [respectively q]. Under the identification of B(R_{n}) with B, N(α) is identified with the projected image of U × V. The N(α)’s form a basis for the topology on B(R_{n}).

If G is a marked graph and Γ is its universal cover, then the marking homotopy equivalence τ : R_{n} → G lifts to an equivariant map τ̃ : R̃_{n} → Γ. Let | · | denotes edge length. Then lim_{|α| →∞} |[τ(α)]| → ∞. This implies that τ̃ is proper and therefore induces a continuous map from ∂F_{n} to the space E(Γ) of ends of Γ. If τ′ : G → R_{n} is a homotopy inverse for τ, then there is a lift τ̃′ such that τ̃′τ̃ moves points by a uniformly bounded amount and therefore induces the identity map on ∂F_{n}. Thus τ̃ induces a homeomorphism from ∂F_{n} to E(Γ) with inverse equal to the map induced by τ̃′. We use this homeomorphism to identify E(Γ) with ∂F_{n} and so also B with (E(Γ) × E(Γ) \ Δ)/(F_{n} × Z_{2}). The latter identification is independent of the choice of τ̃. As in the special case that G = R_{n}, there is a natural bijection between B and B(G). Topologize B(G) so that this bijection is a homeomorphism. For any finite path α ⊂ G, define N(α) ⊂ B(G) to be the set of lines in G that contain α as a subpath. The sets N(α) define a basis for the topology on B(G). Note that a circuit can be thought of as a ‘repeating’ element of B(G). If N(α) ≠ ∅, then α can be extended to a circuit; thus the circuits form a dense set in B(G).

Lemma 3.2. For any homotopy equivalence g : G_{1} → G_{2} of marked graphs, there is an induced homeomorphism g_{#} : B(G_{1}) → B(G_{2}). The associated homeomorphism O_{#} : B → B depends only on the outer automorphism O determined by g and agrees with the induced action of O on conjugacy classes [a].

Proof of Lemma 3.2 Let g̃ : Γ_{1} → Γ_{2} be a lift to the universal covers. As we argued above, g̃ determines an equivariant homeomorphism from E(Γ_{1}) to E(Γ_{2}) and so induces a well defined homeomorphism (g_{1})_{#} : B(G_{1}) → B(G_{2}).

Suppose that α̃_{1} ⊂ Γ_{1} is a lift of a circuit α_{1} ⊂ G_{1}. A homotopy between g(α_{1}) and [g(α_{1})] = α_{2} lifts to a bounded homotopy between g̃(α̃_{1}) and a lift α̃_{2} of α_{2}. This implies that g̃(α̃_{1}) and α̃_{2} have the same endpoints in E(G_{2}). Thus g_{#}(α_{1}) = α_{2} and the homeomorphism g_{#} : B(G_{1}) → B(G_{2}) extends the usual action of g on circuits.

Transferring this to B via the marking homeomorphisms, we see that g induces a homeomorphism O_{#} of B that agrees with the usual action of O on conjugacy classes (under the identification of circuits in R_{n} with conjugacy classes in F_{n}). Since conjugacy classes are dense in B, O_{#} is completely determined by the action of O on conjugacy classes and so is independent of the particular choice of graph representation.

3.3 Free Factors and Free Factor Systems

We denote the conjugacy class of a free factor F^{i} of F_{n} by [[F^{i}]]. We say that β ∈ B is carried by [[F^{i}]] if it is in the closure of the elements of B determined by conjugacy classes in [[F^{i}]]. If G is a marked graph and K is a connected subgraph such that [[π_{1}(K)]] = [[F^{i}]], then γ ∈ B(G) is carried by [[F^{i}]] if and only if every subpath of γ ⊂ G can be extended to a circuit in K; thus, γ ∈ B(G) is carried by [[F^{i}]] if and only if γ ⊂ K.

Recall [SW79] that if F^{1} and F^{2} are free factors, then F^{1} ∩ (F^{2})^{c} is a free factor for all c ∈ F_{n}. (The trivial group < 1 > is considered to be a free factor of rank zero.)

Lemma 3.3. If β ∈ B is carried by both [[F^{1}]] and [[F^{2}]] then β is carried by [[F^{1} ∩ (F^{2})^{c}]] for some c ∈ F_{n}..

Proof of Lemma 3.3 For i = 1, 2, choose a marked graph G_{i} with one vertex v_{i} and a subgraph K_{i} so that the marking identifies π_{1}(K, v_{i}) with F^{i}. Let h : G_{1} → G_{2} be the topological representative determined by the markings. Let β_{1} ⊂ K_{1} and h_{#}(β_{1}) = β_{2} ⊂ G_{2} be the bi-infinite paths that correspond to β. The bounded cancellation lemma [Coo87] [BFH95] implies that for each subpath σ_{k} of β_{1}, [h(σ_{k})] = c_{k}τ_{k}d_{k} where τ_{k} ⊂ β_{2} ⊂ K_{2} and c_{k} and d_{k} have uniformly bounded length. We may choose the σ_{k}’s to be an increasing collection whose union covers β_{1} and so that c_{k} = c and d_{k} = d are independent of k. The union of the τ_{k}’s cover β_{2}. Let w_{k} = σ_{k}σ̄_{1} and note that [h(w_{k})] = [cτ_{k}τ̄_{1}c̄] contains all but a uniformly bounded amount of τ_{k} as a subpath. The lemma now follows from the fact that the element of F_{n} determined by both w_{k} and [h(w_{k})] is contained in F^{1} ∩ (F^{2})^{c}.

Corollary 3.4. For every bi-infinite path β ∈ B, there is a unique free factor F (β) of minimal rank that carries β.

Proof of Corollary 3.4 If F′ ⊂ F are distinct free factors, then rank(F′) < rank(F). Corollary 3.4 therefore follows immediately from Lemma 3.3.

A collection {[[F^{1}]], …, [[F^{l}]]} is a free factor system for [[F^{j}]] if F^{j} and the F^{i}’s can be chosen so that F^{1} ∗ ⋯ ∗ F^{l} is a free factor of F^{j}. If F^{j} = F_{n}, then we simply say that {[[F^{1}]], …, [[F^{l}]]} is a free factor system. We will assume throughout that if F ≠ [[< 1 >]], then each F^{i} is non-trivial and so has positive rank.

If F^{i} is a free factor and F_{2} is a free factor system, then [SW79] the nontrivial elements of {[[F^{i} ∩ (F^{j})^{c}]] : [[F_{j}]] ∈ F_{2}; c ∈ F_{n}} comprise a free factor system for [[F^{i}]]. It follows that if F_{1} and F_{2} are free factor systems, then the non-trivial elements of {[[F^{i} ∩ (F^{j})^{c}]] : [[F_{i}]] ∈ F_{1}; [[F_{j}]] ∈ F_{2}; c ∈ F_{n}} comprise a free factor system that we denote by F_{1} ∧ F_{2}.

In order to generalize Corollary 3.4 to arbitrary subsets of B, we define the complexity of F = {[[F^{1}]], …, [[F^{l}]]} to be the non-increasing sequence of positive integers that is obtained by rearranging the non-zero elements of {rank(F^{1}), …,rank(F^{l})}. For any fixed F_{n}, there are only finitely many such complexities and we order them lexicographically. Thus 5, 3, 3, 1 > 4, 4, 4, 4, 4, 4 > 4 > ∅; [[F_{n}]] has the highest complexity and [[< 1 >]] has the smallest.

If γ ∈ B is carried by some [[F^{i}]] ∈ F, then we say that γ is carried by F.

Corollary 3.5. For any subset B ⊂ B there is a unique free factor system of minimal complexity that carries every element of B.

Proof of Corollary 3.5 Every line is carried by F_{n} so there is at least one smallest free factor system of minimal complexity that carries every element of B. Suppose that there are two such free factor systems F_{1} and F_{2}. Lemma 3.3 implies that if F_{1} and F_{2} both carry B, then so does F_{1} ∧F_{2}. If F_{1} ∧ F_{2} is not equal to F_{1}, then the set of ranks that occur for elements of F_{1} ∧ F_{2} is obtained from the set of ranks that occur for elements of F_{1} by (perhaps more than once) replacing a positive integer with a finite collection of strictly smaller integers. It follows that Complexity(F_{1}) >Complexity(F_{1}∧ F_{2}) in contradiction to the choice of F_{1}.

An outer automorphism O induces an action on the set of conjugacy classes of free factors. If [[F^{i}]] is fixed by O, then we say that [[F^{i}]] is Oinvariant. Sometimes, we will abuse notation and say that F^{i} is O-invariant when we really mean that its conjugacy class is. We say that F is O- invariant if each [[F^{i}]] ∈ F is O-invariant.

We write [[F^{1}]] ⊂ [[F^{2}]] if F^{1} is conjugate to a free factor of F^{2} and F_{1} ⊂ F_{2} if for each [[F^{i}]] ∈ F_{1} there exists [[F^{j}]] ∈ F_{2} such that [[F^{i}]] ⊂ [[F^{j}]]. Note that if F_{1} ⊂ F_{2} and F_{1} ≠ F_{2}, then the complexity of F_{1} is strictly less than the complexity of F_{2}.

If G is a marked graph and K ⊂ G is a subgraph whose non-contractible components are C_{1}, …, C_{l} then F(K) = {[[π_{1}(C_{i})]], …, [[π_{1}(C_{l})]]} is a free factor system. If f : G → G is a topological representative of O that setwise fixes each C_{i}, then F(K) is O-invariant.

Many of our arguments proceed by induction up through a filtration and it is important that the step between one filtration element and the next be as small as possible. More precisely, there should be no O-invariant free factor systems properly contained between F(G_{r−1}) and F(G_{r}). At certain points in the paper, we will replace f : G → G by an iterate. We therefore make our definition stable under iteration. For now, we focus on the exponentially growing strata and say that f : G → G is reduced if, for each exponentially growing stratum H_{r}, there are no free factor systems invariant under the action of an iterate of O and properly contained between F(G_{r−1}) and F(G_{r}).

Lemma 3.6. For any O- invariant free factor system F there exists a relative train track map f : G → G representing O such that F = F(G_{r}) for some filtration element G_{r}. If we replace O by an iterate O^{s} then we may choose f : G → G to be reduced.

Proof of Lemma 3.6 The first step in the proof is to show that for any nested sequence F_{1} ⊂ ⋯ ⊂ F_{l} of O-invariant free factor systems, there is a topological representative f : G → G of O and a filtration ∅ = G_{0} ⊂ G_{1} ⊂ … G_{m} = G so that F_{i} = F(G_{r_{i}}) for some 1 ≤ r_{i} ≤ m and all 1 ≤ i ≤ l. We say that F_{i} is realized by G_{r_{i}}. The construction of f : G → G is very similar to the one in Lemma 1.16 of [BH92].

There is no loss in assuming that F_{l} = [[F_{n}]]. We argue by induction on l, the l = 1 case being trivial. Let F_{l−1} = {[[F^{1}]], …, [[F^{k}]]}. For each 1 ≤ i ≤ k and 1 ≤ j ≤ l − 2, define F_{j}^{i} to be the free factor system of [[F^{i}]] consisting of those elements of F_{j} that are contained in [[F^{i}]] . Note that F_{j} = ∪_{j}F_{j}^{i}. Let C^{i} be the nested sequence F_{1}^{i} ⊂ ⋯ ⊂ F_{l−2}^{i} ⊂ [[F^{i}]]. Choose automorphisms Φ_{i} : F_{n} → F_{n} representing O such that Φ_{i}(F^{i}) = F^{i}. By induction on l, there are topological representatives f_{i} : K_{i} → K_{i} representing O|[[F^{i}]] and filtrations of K_{i} such that each F_{j}^{i} is realized by a filtration element. We may assume inductively that f_{i} fixes a vertex v_{i} of K_{i} and that the marking on K_{i} identifies F^{i} with π_{1}(K_{i}, v_{i}) and identifies Φ_{i} with the automorphism (f_{i})_{#} : π_{1}(K_{i}, v_{i}) → π_{1}(K_{i}, v_{i}).

Let F^{k+1} ≅ F_{n_{k+1}} be a free factor such that F^{1}∗⋯∗F^{k+1} ≅ F_{n}. Define G to be the graph obtained from the disjoint union of the K_{i}’s by adding edges E_{i}, 2 ≤ i ≤ k, connecting v_{1} to v_{i}, and by adding n_{k+1} loops {L_{j}} based at v_{1}. Collapsing the E_{i}’s to v_{1} gives a homotopy equivalence of (G, v_{1}) onto a graph (G′, v′) whose fundamental group is naturally identified with F^{1} ∗ ⋯ ∗ F^{k+1} ≅ F_{n}. This provides a marking on G.

The filtration on ∪K_{i} is built up of strata from the filtration of K_{i}’s added on as follows. First add, one by one and for each i, the strata of K_{i} that realize F_{1}^{i}. This can be done in any order. The union of all these strata is a filtration element that realizes F_{1}. Then add, one by one and for each i, the strata of K_{i} that realize F_{2}^{i}. This can also be done in any order. The union is a filtration element that realizes F_{2}. Continue in this way until all the strata of the K_{i}’s have been added. Finally extend this to a filtration of G.

There exists c_{i} ∈ F_{n}, 2 ≤ i ≤ k, such that Φ_{1}(x) = c_{i}Φ_{i}(x)c̄_{i} for all x ∈ F_{n}. Let γ_{i} ⊂ G be the loops based at v_{1} that are identified, under the marking, with c_{i}. Extend ∪f_{i} : ∪K_{i} → ∪K_{i} to a topological representative f : G → G by defining f(E_{i}) = γ_{i}E_{i} and by defining f(L_{j}) according to Φ_{1}. Then f_{#} : π_{1}(G, v_{1}) → π_{1}(G, v_{1}) induces Φ_{1} : F_{n} → F_{n} and so represents O. This completes the first part of the proof.

The second step in the proof is to promote f : G → G to a relative train track map. This will complete the proof of the first part of the lemma. In section 5 of [BH92], there is an algorithm that begins with an arbitrary topological representative of O and filtration and produces a relative train track map and filtration that represents O. The algorithm uses only the operations of : subdivision; folding; tightening; collapsing pre-trivial forests; valence one homotopy; and (with some restrictions) valence two homotopy. (See [BH92] for definitions.) It suffices to observe that if f̂ : Ĝ → Ĝ is obtained from f : G → G by performing one of these operations and if each F_{i} is realized by a filtration element of G, then each F_{i} is realized by a filtration element of Ĝ.

Let p : G → Ĝ be the natural homotopy equivalence. We will show that if C_{1} and C_{2} are components of a filtration element G_{k} in G, then Ĉ_{1} = p(C_{1}) and Ĉ_{2} = p(C_{2}) are disjoint f̂-invariant subgraphs and [[π_{1}(C_{i})]] = [[π_{1}(Ĉ_{i})]].

Since p(G_{k}) is a filtration element in the induced filtration on Ĝ, this will complete the proof.

We consider first the case that Ĝ is obtained from G by collapsing a pre-trivial forest X. (A forest is pre-trivial if its image under some iterate of f is a finite union of points.) Since a component of X can not intersect both C_{1} and C_{2}, Ĉ_{1} and Ĉ_{2} are disjoint. Let X_{0} be a component of X. If C_{i} ∩ X_{0} has more than one component then there is a circuit that is not contained in C_{i} but whose image under some iterate of f is contained in C_{i}. This contradicts the fact that f and f|C_{i} are homotopy equivalences. Thus C_{i} ∩ X is connected and [[π_{1}(C_{i})]] = [[π_{1}(Ĉ_{i})]].

The operations of subdivision, folding, tightening and valence one homotopy are straightforward to check and we leave this to the reader. Suppose that v is a valence two vertex with incident edges E_{r} and E_{s}. If E_{r} and E_{s} are disjoint from C_{1}∪C_{2} then the valence two homotopy does not effect C_{1} or C_{2}. If E_{r} and E_{s} are both contained in C_{1} ∪C_{2}, then they are both contained in C_{1} or both contained in C_{2}, say C_{1}. In this case, C_{2} is unchanged by the valence two homotopy and it follows immediately from the definitions that Ĉ_{1} ∩ Ĉ_{2} = ∅ and that [[π_{1}(C_{1})]] = [[π_{1}(Ĉ_{1})]]. If one edge, say E_{r}, is contained in C_{1} ∪ C_{2} but E_{s} is not, then E_{s} is not contained in G_{k}. In particular, E_{s} belongs to a higher stratum than does E_{r} so the valence two homotopy is performed by sliding v across E_{r}. From the point of view of G_{k}, a valence one homotopy is being performed on one of its components. The desired properties now follow immediately from the definitions. This completes the second step in the proof.

Extend F to a maximal (with respect to inclusion) nested sequence C of distinct free factor systems F_{i} such that each F_{i} is invariant under the action of some iterate of O Replace O by O^{s} where each F_{i} is O^{s}- invariant and let f : G → G be a relative train track map representing O^{s} such that each F_{i} is realized by a filtration element. If ∅ = G_{0} ⊂ G_{1} ⊂ ⋯ ⊂ G_{m} is the filtration for f : G → G , then the nested sequence [[< 1 >]] ⊂ F(G_{1}) ⊂ ⋯ ⊂ F(G_{m}) = [[F_{n}]] contains the nested sequence C. Since C is maximal, f : G → G is reduced.

4 Expanding Laminations

The exponentially growing dynamics of an outer automorphism O is captured by a finite collection L(O) of expanding laminations. In the analogy between Out(F_{n}) and the mapping class group of a compact surface, L(O) corresponds to the unstable measured foliations associated to the pseudo-Anosov components of the mapping class. In this section, we define and characterize L(O). We begin by working in ‘local coordinates’ and then prove that the construction is independent of all choices.

We view a lamination as a closed set of lines and not as a single point in a space of (measured) laminations. This is messier in some ways, since B is not a nice topological space, but it enlarges the basin of attraction for elements of L(O). Indeed, the iterates of a typical line will limit on all elements of L(O) simultaneously. This not only simplifies the proof of the Tits Alternative but it more faithfully captures the essential dynamics.

A non-negative irreducible matrix is aperiodic if it has an iterate that is strictly positive. We say that a relative train track map f : G → G is egaperiodic if the transition submatrix for each exponentially growing stratum is aperiodic. This is analogous to studying surface homeomorphisms whose pseudo-Anosov components are fixed rather than permuted. We say that O is eg-aperiodic if it is represented by an eg-aperiodic relative train track map . We show in Corollary 4.7 that every O has an iterate that is eg-aperiodic and that every relative train track map representing an eg-aperiodic outer automorphism is eg-aperiodic.

Suppose that f : G → G is a relative train track map, that H_{r} is an exponentially growing stratum with edges {E_{i}} and that the transition submatrix M_{r} is aperiodic. Choose m_{0} > 0 so that, setting h = f^{m_{0}}, each [h(E_{i})] crosses each E_{j} at least three times. Choose an H_{r}-edge and for notational simplicity call it E. There exist non-trivial subpaths α and β such that [h(E)] = αEβ. Lemma 3.1 implies that [h^{2}(E)] = [h(α)][α]E[β][h(β)] and, in general, that [h^{k}(E)] = [h^{k−1}(α)] … [h(α)][α]E[β][h(β)] … [h^{k−1}(β)] = [h^{k−1}(α)][h^{k−1}(E)][h^{k−1}(β)]. Thus … [h^{3}(α)][h^{2}(α)][h(α)][α]E[β][h(β)][h^{2}(β)][h^{3}(β)] … is an f-invariant bi- infinite path and we denote the (unoriented) line that it determines by λ^{+}.

Our next lemma gives a kind of quasi-periodicity for λ^{+}.

Lemma 4.1. For all k there exists N(k) so that [h^{k}(E_{j})] is an unoriented subpath of λ_{0}^{+} for each H_{r}-edge E_{j} and each subpath λ_{0}^{+} ⊂ λ^{+} that contains at least N(k) H_{r}-edges.

Proof of Lemma 4.1 It is clear from the construction that λ^{+} ⊂ G_{r} is hinvariant and r-legal. Lemma 3.1 and induction imply that for any k ≥ 0, λ^{+} can be decomposed into pieces that are either entirely contained in G_{r−1} or are equal, up to a change of orientation, to some [h^{k+1}(E_{i})].

Choose N(k) so that each [h^{k+1}(E_{i})] contains at most N(k)/2 H_{r}-edges. If λ_{0}^{+} contains N(k) H_{r}-edges, then λ_{0}^{+} must contain some [h^{k+1}(E_{i})] and hence [h^{k}(E_{j})].

Define Λ^{+} to be the closure of λ^{+} in B. Each line in Λ^{+} is called a leaf of Λ^{+}. Note that a line λ ⊂ G is a leaf of Λ^{+} if and only if each subpath of λ is a subpath of λ^{+}. A line λ ⊂ G is bi-recurrent if every finite subpath of λ occurs in every infinite subpath of λ. The bounded cancellation lemma implies that if G′ is any other marked graph and if λ′ is the line in G′ that corresponds to λ ⊂ G, then λ is bi-recurrent if and only if λ′ is bi-recurrent. Bi-recurrence is therefore defined on elements of B. If λ is a birecurrent leaf of Λ^{+} and if Λ^{+} is the closure of λ, then we say that λ is a generic leaf of Λ^{+}.

Remark 4.2. A circuit in G_{r} determines a ‘periodic’ line β ∈ B(G). The set {β} is closed in B(G). If β is a generic leaf of Λ^{+}, then β = Λ^{+} = λ^{+} and in particular f_{#}(β) = β. This implies that the difference between the number of H_{r}-edges in a subpath β_{0} ⊂ β and the number of H_{r}- edges in [f(β_{0})] is bounded independently of the choice of β_{0}. This contradicts Lemma 3.1 and the construction of λ^{+}. We conclude that circuits are never generic leaves of Λ^{+}.

We say that U ⊂ B is an attracting neighborhood of γ ∈ B for the action of O if U ⊃ O_{#}(U) and if {O_{#}^{k}(U) : k ≥ 0} is a neighborhood basis for γ in B. We say that α is weakly attracted to γ if O^{k}(α) converges to γ in B. Thus if U is an attracting neighborhood of γ, then α is weakly attracted to γ if and only if some [O^{k}(α)] ∈ U. Working in the marked graph G, we see that if α, γ ⊂ G, then α is weakly attracted to γ if and only if each subpath of γ is contained in [f^{k}(α)] for all sufficiently large k.

Proposition 4.3. Λ^{+} is O-invariant and depends only on f : G → G and H_{r}. A leaf of Λ^{+} is generic if and only if neither of its ends are contained in G_{r−1}. Each generic leaf has an attracting neighborhood. A leaf of Λ^{+} with both ends in G_{r−1} is entirely contained in G_{r−1}.

Proof of Proposition 4.3 The construction of Λ^{+} involved three choices : h = f^{m_{0}}, E and the decomposition [h(E)] = αEβ. Suppose that these choices are changed to h_{1} = f^{m_{1}}, E_{1} and [h_{1}(E_{1})] = α_{1}E_{1}β_{1} and that the resulting bi-infinite path is denoted λ_{1}^{+}. By construction, [h_{1}(E_{1})] crosses E. There exist arbitrarily large k, l ∈ ℕ such that m_{1}(k − 1) = m_{0}l. Lemma 3.1 implies that [h_{1}^{k}(E_{1})] contains [h_{1}^{k−1}(E)] = [h^{l}(E)] as a subpath. Since every finite subpath of λ^{+} is an unoriented subpath of some [h^{l}(E)], λ^{+} is a leaf of Λ_{1}^{+} and Λ^{+} ⊂ Λ_{1}^{+}. By symmetry, Λ^{+} = Λ_{1}^{+} so Λ^{+} is independent of the choices.

Suppose that λ is a leaf of Λ^{+}. If neither end of λ is contained in G_{r−1}, then every infinite subpath of λ contains infinitely many H_{r}-edges. Since every finite subpath of λ is a subpath of λ^{+}, Lemma 4.1 implies that every infinite subpath of λ contains [h^{k}(E)] for all k > 0. Since every finite subpath of λ or λ^{+} occurs in some [h^{k}(E)], λ is birecurrent and λ^{+} is contained in the closure of λ. In other words, λ is generic. The converse, that neither end of a generic leaf is contained in G_{r−1}, is obvious.

If m > m_{0}, then each E_{j} is crossed by [f^{(m−m_{0})}E_{k}] for some E_{k}. Our choice of m_{0} therefore guarantees that each E_{j} is crossed by each [f^{m}(E_{i})]. In particular, [f^{2m_{0}−1}(E)] crosses E and so [f[h^{k−2}(E)]] = [h^{k−2}[f(E)]] is an unoriented subpath of [h^{k−2}[f^{2m_{0}}(E)]] = [h^{k}(E)]. Since f_{#}(λ^{+}) is an increasing union of subpaths of the form [f[h^{k−2}(E)]] and λ^{+} is an increasing union of subpaths of the form [h^{k}(E)], we conclude that f_{#}(λ^{+}) is contained in the closure of λ^{+} and hence is a leaf of Λ^{+}. Since the ends of λ^{+} are not contained in G_{r−1}, neither are the ends of f_{#}(λ^{+}). Thus f_{#}(λ^{+}) is generic and Λ^{+} is O-invariant.

There is a decomposition of λ^{+} at a fixed point of E into infinite paths λ^{+} = σ·τ such that [h(σ)] = σ and [h(τ)] = τ. Let σ_{k} be the terminal segment of σ that initiates at the k^{th} H_{r}-edge of σ̄, let τ_{k} be the initial segment of τ that terminates at the k^{th} H_{r}-edge of τ and let V_{k} be the neighborhood of λ^{+} in B determined by the subpath σ_{k}τ_{k}. The bounded cancellation lemma and the fact that h exponentially increases the number of H_{r}-edges in r-legal paths imply that h_{#}(V_{k}) ⊃ V_{k+1} for all sufficiently large k. It follows that V_{k} is an attracting neighborhood of λ^{+} for the action of O^{m_{0}}. Since Λ_{r}^{+} is Oinvariant, U = V_{k} ∩ O(V_{k}) ∩ ⋯ ∩ O^{m_{0}−1}(V_{k}) is an attracting neighborhood of λ^{+} for the action of O. Generic leaves of Λ^{+} all have the same neighborhoods in B so U is an attracting neighborhood for every generic leaf of Λ^{+}.

Suppose that λ is a leaf of Λ^{+} and that both ends of λ are contained in G_{r−1}. The [h(E_{j})]’s can be written as alternating concatenations of subpaths in H_{r} and subpaths γ_{k} ⊂ G_{r−1}. Thus [h^{m}(E)] is an alternating concatenation of subpaths in H_{r} and subpaths of the form [f^{l}(γ_{k})] for 0 ≤ l ≤ m − 1. Assuming without loss that each [h(E_{j})] contains at least one γ_{k}, an easy induction argument shows that if l_{1}, l_{2} > l, then occurrences of [f^{l_{1}}(γ_{k_{1}})] and [f^{l_{2}}(γ_{k_{2}})] in [h^{m}(E)] are separated by at least 2^{l} edges in H_{r}. Thus any two long subpaths of λ^{+} that are entirely contained in G_{r−1} and are separated by at least one edge in H_{r} must be separated by a lot of edges in H_{r}; the number of edges in H_{r} increases to infinity as the length of the subpaths in G_{r−1} increase to infinity. Since every subpath of λ is contained in λ^{+}, the ends of λ can not be separated by an edge in H_{r}. In other words, λ ⊂ G_{r−1}.

We say that Λ^{+} is the expanding lamination associated to f : G → G and to H_{r}. If O is eg-aperiodic, choose an eg-aperiodic relative train track map f : G → G and let L(O) be the set of expanding laminations associated to the exponentially growing strata of f : G → G .

Lemma 4.4. The set L(O) depends only on O and not on the choice of f : G → G. If [[F]] is O-invariant, then L(O|[[F]]) ⊂ L(O). A line is a generic leaf of an element of L(O) if and only if it is bi-recurrent and has an attracting neighborhood for the action of O.

Proof of Lemma 4.4 The third statement implies the first. Lemma 3.6 implies that if [[F]] is O-invariant, then there is a relative train track map f : G → G such that F(G_{r}) = [[F]] for some filtration element. The first statement therefore implies the second. The only if direction of the third statement is contained in Proposition 4.3.

For the if direction of the third statement, we argue by induction on the rank n of F_{n}. The n = 1 case is vacuous so we may assume that the proposition holds for outer automorphisms of F_{k} with k < n.

Suppose that λ ⊂ G is bi-recurrent and has an attracting neighborhood. Let ∅ = G_{0} ⊂ ⋯ ⊂ G_{m} = G be a filtration for f : G → G . We first consider the case that λ ⊂ G_{m−1}. Since λ has an attracting neighborhood, λ must be contained in an f-invariant component C of G_{m−1}. The inductive hypothesis, applied to the restriction of O to [[π_{1}(C)]], implies that λ is a generic leaf of the expanding lamination associated to H_{i} for some i < m.

We may therefore assume that λ contains infinitely many edges of H_{m}. Let α ≠ λ ⊂ G be a circuit that is weakly attracted to λ. Since f_{#}^{k}(α) converges to λ in B(G), f_{#} can not act periodically on α with period different from one; since α ≠ γ, f_{#} cannot fix α. Thus the number of edges in f_{#}^{k}(α) grows without bound. Since f_{#}^{k}(α) converges to a line with infinitely many H_{m}-edges, the number of H_{m}-edges in f_{#}^{k}(α) grows without bound. We conclude that H_{m} must be an exponentially growing stratum; denote its expanding lamination by Λ_{m}^{+}. Let s be the number of edges in α. Given any subpath λ_{0} ⊂ λ, birecurrence implies that there is a subpath λ_{1} ⊂ λ that contains s + 1 disjoint copies of λ_{0}. Since α is weakly attracted to λ, there exists k so that [f^{k}(α)] contains λ_{1}. At least one of the copies of λ_{0} in λ_{1} must be contained in the f^{k}-image of a single edge e of α. If λ_{0} contains an edge of H_{m}, then e must be one of the edges E_{i} of H_{m}. We conclude that every subpath of λ is contained in some [f^{k}(E_{i})] and hence in every generic leaf of Λ_{m}^{+}. Thus λ is a leaf of Λ_{m}^{+}. Since λ is birecurrent and is not contained in G_{m−1}, it is a generic leaf of Λ_{m}^{+}.

Since all generic leaves of Λ^{+} attract the same lines, we say that γ is weakly attracted to Λ^{+} if it is weakly attracted to some, and hence every, generic leaf of Λ^{+}.

We now recall the folding construction of Stallings [Sta83]. Suppose that f : G → G is a topological representative. If f is not an immersion, then there are a pair of oriented edges E_{1} and E_{2} with the same initial endpoint and there are non-trivial initial segments E_{1}^{∗} ⊂ E_{1} and E_{2}^{∗} ⊂ E_{2} such that f(E_{1}^{∗}) = f(E_{2}^{∗}) is a path with endpoints at vertices. Let p_{1} : G → G^{1} be the quotient or folding map that identifies E_{1}^{∗} with E_{2}^{∗}; we assume that the identification is done so that there is an induced map f_{1} : G^{1} → G satisfying f_{1}p_{1} = f. Repeating this argument with f_{1} : G^{1} → G replacing f : G → G, we conclude that f = θp_{k} … p_{1} where each p_{i} : G^{i−1} → G^{i} is a folding map and where θ : G^{k} → G is an immersion, and hence [Sta83] a homeomorphism.

The following lemma is essentially the statement that a stratum with a single edge can not be exponentially growing.

Lemma 4.5. Suppose that H_{i} is an exponentially growing stratum of a relative train track map f : G → G, that Q_{i−1} is the union of the non- contractible components of G_{i−1} and that X is a component of G_{i} that contains at least one edge of H_{i}. If X ∩ Q_{i−1} = ∅, then −χ(X) ≥ 1. If X ∩ Q_{i−1} ≠ ∅, then −χ(X) > −χ(X ∩ Q_{i−1}) + 2.

Proof of Lemma 4.5 If E is an edge of X ∩ H_{i}, then the edge path [f^{k}(E)] contains at least three copies of E for some k > 0. Thus X is non-contractible and the endpoints of the edges of X ∩ H_{i} have valence at least two in X. Replacing f by an iterate if necessary, we may assume that X = G. Since H_{i} is exponentially growing, π_{1}(X) has rank at least two and so −χ(X) ≥ 1. We may therefore assume that Q_{i−1} ≠ ∅.

It suffices to assume that X \Q_{i−1} is a single, possibly subdivided, interval and argue to a contradiction. There is no loss in erasing all subdivision vertices. We may therefore assume that H_{i} is a single edge E. Since there are paths that cross E three times, each endpoint of E must lie in a noncontractible component of G_{i−1}; thus G_{i−1} = Q_{i−1}.

If f|G_{i−1} is not an immersion, then f = f_{1}p_{1} where p_{1} : G → G^{1} is a folding map determined by initial segments of edges in G_{i−1} and f_{1} : G^{1} → G. Denote the subgraph p_{1}(G_{i−1}) by G_{i−1}^{1}; then G^{1} \ G_{i−1}^{1} is a single edge which we naturally identify with E. If f_{1}|G_{i−1}^{1} is not an immersion, then f = f_{2}p_{2}p_{1} where p_{2} : G^{1} → G^{2} is a folding map determined by initial segments of edges in G_{i−1}^{1}. Denote p_{2}(G_{i−1}^{1}) by G_{i−1}^{2} and identify the remaining edge of G^{2} with E. Continuing in this manner, and denoting p_{k} ⋯ p_{1} by P_{k}, we have f = f_{k}P_{k} where P_{k} : (G, G_{i−1}) → (G^{k}, G_{i−1}^{k}) is a composition of folds, where P_{k} is the identity on E = G \ G_{i−1} = G^{k} \ G_{i−1}^{k} and where f_{k}|G_{i−1}^{k} is an immersion.

The relative train track property for H_{i} implies that [f(E)] begins and end with E or Ē. Since f_{k}(P_{k}(G_{i−1})) = f(G_{i−1}) = G_{i−1}, the only possible fold for f_{k} is between initial subpaths of E and Ē. Denote this fold by p_{k+1} and let P_{k+1} = p_{k+1}P_{k}; assuming that the fold is maximal, f = θP_{k+1} for some homeomorphism θ. Since θ(P_{k}(G_{i−1})) = θ(P_{k+1}(G_{i−1})) = f(G_{i−1}) = G_{i−1}, G^{k} and G have the same number of edges. But G^{k+1} has one more edge than G^{k} and so can not be homeomorphic to G. This contradiction completes the proof.

If [[F^{j}]] carries a generic leaf of Λ^{+}, then it carries every generic leaf of Λ^{+}. In this case we say that [[F^{j}]] carries Λ^{+}. By Corollary 3.4, there is a smallest free factor F(Λ^{+}) that carries Λ^{+}.

Lemma 4.6. Assume that O is eg-aperiodic. Then for each Λ^{+} ∈ L(O) there is a unique Λ^{−} ∈ L(O^{−1}) such that F(Λ^{+}) = F(Λ^{−}). We say that Λ^{+} and Λ^{−} are paired.

Proof of Lemma 4.6 We induct on the rank n of F_{n}. For n = 1, there are no exponentially growing stratum, so the lemma is vacuously true. We may therefore assume that the lemma holds for outer automorphisms of F_{k} where k < n. Define the rank of Λ^{+} to be the rank of F(Λ^{+}).

Proposition 4.3 and the uniqueness of F(Λ_{i}^{+}) imply that F(Λ_{i}^{+}) is O- invariant for each Λ_{i}^{+} ∈ L(O). If the rank of Λ_{i}^{+} is less than n, then Lemma 4.4 and the inductive hypothesis imply that there exists a unique Λ_{i}^{−} ∈ L(O^{−1}) such that F(Λ^{+}) = F(Λ^{−}). Lemma 4.4 also implies that O and O^{−1} have at most one expanding lamination with rank n. It therefore suffices to show that either both O and O^{−1} have an expanding lamination of rank n or that neither of them do.

Suppose that O has an expanding lamination of rank n. Lemma 4.4 implies that L(O) = L(O^{k}) for all k > 0 so there is no loss in replacing O by an iterate. We may therefore assume by Lemma 3.6 that there is a reduced relative train track map representing O. The expanding lamination of rank n is associated to the top stratum H_{r} and each element of L(O) and L(O^{−1}) with rank less than n is carried by F = F(G_{r−1}). Lemma 4.5 implies that F is neither a single free factor of rank n − 1 nor a pair of free factors with rank sum equal to n.

Choose (Lemma 3.6) a relative train track map f′ : G′ → G′ representing an iterate of O^{−1} such that F is realized by a filtration element. Replacing f′ by an iterate if necessary, we may assume that each non-exponentially growing stratum is a single edge. If H′_{m} is the topmost stratum, then since f : G → G is reduced, F = F(G′_{m−1}). H′_{m} cannot be a zero stratum and the concluding observation of the preceding paragraph rules out the possibility that it is a single edge. Thus H′_{m} is exponentially growing. Since the expanding lamination associated to H′_{m} is not carried by F, it must have rank n.

Corollary 4.7. For every O, there exists k ≥ 1 such that O^{k} is eg-aperiodic. L(O^{k}) is independent of k and is setwise invariant under the action of O. A relative train track map f : G → G that represents O is eg-aperiodic if and only if O fixes each element of L(O^{k}). In particular, every representative of an eg-aperiodic outer automorphism is eg-aperiodic and O is eg-aperiodic if and only if O^{−1} is eg-aperiodic.

Proof of Corollary 4.7 Suppose that f : G → G is a relative train track map representing O and that H_{r} is an exponentially growing stratum. If M_{r} is not aperiodic, then there is a partition [Sen81] of the edges of H_{r} into s > 1 sets P_{1}, … P_{s} such that for each edge E ∈ P_{i}, the edge path [f(E)] only crosses edges in P_{i+1( mod s)} and in G_{r−1}. After replacing f by f^{s}, the stratum H_{r} divides into s exponentially growing strata, one for each P_{i}. If s is maximal, then the transition submatrix for each of these strata is aperiodic.

Applying this to each exponentially growing but not aperiodic stratum, we find k ≥ 1 so that f^{k} : G → G is eg-aperiodic. Lemma 4.4 and the construction of Λ^{+} imply that L(f^{k}) = L(f^{mk}) for all m > 0. It follows that L(O^{k}) is independent of the choice of k. Lemma 4.4 also implies that an outer automorphism that commutes with O^{k}, and in particular O, permutes the elements of L(O^{k}).

If the minimal k is greater than one, then at least one stratum H_{r} for f divides into s > 1 strata for f^{k}; the elements of L(O^{k}) associated to H_{r} are transitively permuted by the action of f and hence by the action of O. Thus O does not pointwise fix the elements of L(O^{k}). The converse, that an eg-aperiodic O fixes each element of L(O^{k}), is clear from the definition.

4.1 Expansion Factors

We assume now that Λ is an expanding lamination for some aperiodic outer automorphism O. Choose a relative train track map f : G → G for O and let H_{r} be the exponentially growing stratum associated to Λ. For any path σ ⊂ G define EL_{r}(σ) to be the edge length of σ, counting only the edges of H_{r}. Define Stab(Λ) = {Ψ ∈ Out(F_{n}) : Ψ_{#}(Λ) = Λ}. We say that Ψ ∈ Stab(Λ) asymptotically expands Λ by the factor μ if for some (and hence any) topological representative g : G → G of Ψ on G, and for all ϵ > 0, there exists L so that

μ − ϵ < \frac{EL_{r}([g(σ)])}{EL_{r}(σ)} < μ + ϵ

whenever σ is contained in a leaf of Λ and EL_{r}(σ) > L.

That the above condition holds for any g′ : G → G representing O if it holds for some g : G → G representing O follows from the fact that if g ≃ g′, then [g(σ)] and [g′(σ)] differ by initial and terminal segments of uniformly bounded length.

The following proposition shows that this definition is independent of the choice of f : G → G . The corollary that follows it is essential to our reduction of the Tits Alternative for Out(F_{n}) to the Tits Alternative for PG(F_{n}).

Proposition 4.8. Every Ψ ∈ Stab(Λ) asymptotically expands Λ by some factor μ = μ(Ψ); μ(Ψ^{−1}) = μ(Ψ)^{−1}. If μ > 1 then Λ ∈ L(Ψ). If f′ : G′ → G′ is any relative train track map representing Ψ and H′_{s} is the exponentially growing stratum that corresponds to Λ, then μ = μ′_{s} is the Perron Frobenius eigenvalue for the transition submatrix M′_{s} for H′_{s}.

Corollary 4.9. There is a homomorphism P F_{Λ} : Stab(Λ) → ℤ such that Ψ ∈ Ker(P F_{Λ}) if and only if Λ is not an expanding lamination for either Ψ or Ψ^{−1}.

Proof of Corollary 4.9 Define P F_{Λ}(Ψ) = log(μ(Ψ)). Suppose that g : G → G and g′ : G → G are topological representatives for Ψ and Ψ′ respectively. If σ ⊂ G is contained in a leaf of Λ, then there is a subpath σ′ ⊂ G of [g(σ)] that is contained in a leaf of Λ and that differs from [g(σ)] only in an initial and terminal segment of uniformly bounded length. Similarly, [g′g(σ)] ⊂ G differs from [g′(σ′)] only in an initial and terminal segment of uniformly bounded length. Thus μ(ΨΨ′) = μ(Ψ)μ(Ψ′) and P F_{Λ} is a homomorphism. Proposition 4.8 implies (c.f. page 37 of [BH92]) that the image of P F_{Λ} is a closed discrete subset of ℝ and is hence isomorphic to ℤ. Proposition 4.8 implies that P F_{Λ}(Ψ) > 0 if and only if Λ ∈ L(ψ) and that P F_{Λ}(Ψ) < 0 if and only if Λ ∈ L(ψ^{−1})

Proof of Proposition 4.8 Let {E_{i}} be the edges of H_{r} and let μ_{r} be the Perron-Frobenius eigenvalue for M_{r}. The Perron Frobenius theorem [Sen81] implies that μ_{r}^{−n}M_{r}^{n} converges to a matrix M^{∗} whose columns are projectively equal. Normalize the column vectors of M^{∗} so that the sum of the entries is one and denote this common ‘frequency vector’ by A = (a_{i}).

A generic leaf λ of Λ can be decomposed into a concatenation of edges in H_{r} and paths in G_{r−1}. Applying f^{m} to this decomposition, we see that each f_{#}^{m}(λ), and hence each λ, can be decomposed into a concatenation of paths α_{j} = [f^{m}(E_{j})] and paths β ⊂ G_{r−1}. If m is large, then the fraction of the H_{r}-edges in α_{j} that equal E_{i} is close to a_{i}. It follows that if τ is any subpath of λ and if EL_{r}(τ) is sufficiently large, then the fraction of H_{r}-edges in τ that equal E_{i} is close to a_{i}. The error in this approximation tends to zero as EL_{r}(τ) tends to infinity.

Throughout this proof we use ∼ to denote an approximation where the error is a small fraction of the total. Note that EL_{r}([f^{m}(E_{j})]) equals the column sum for the j^{th} column of M_{r}^{m}. Thus for large m, EL_{r}([f(α_{j})]) ∼ μ_{r}EL_{r}(α_{j}). Lemma 3.1 therefore implies that EL_{r}([f(σ)]) ∼ μ_{r}EL_{r}(σ) whenever EL_{r}(σ) is sufficiently large. In other words, O expands Λ by the factor μ_{r}.

Reapplying the argument from the second paragraph of this proof, we see that λ is a concatenation of α_{j}’s and paths β ⊂ G_{r−1}. Moreover, if σ is a subpath of λ and EL_{r}(σ) is sufficiently large, then the fraction of the α_{j}’s that equal α_{i}, among all α_{j}’s that are entirely contained in σ, is close to a_{i}. (There are at most two α_{j}’s that intersect σ but are not entirely contained in σ.) Let T (σ) the total number of α_{j}’s that are entirely contained in σ and note that a_{i}T (σ) is an approximation for the number of occurrences of α_{i} in σ.

For the remainder of the proof, let g : G → G be a topological representative for Ψ. Suppose that γ is a leaf of Λ that is entirely contained in G_{r−1}. The accumulation set of an end of γ is not equal to Λ. Since ψ ∈ Stab(Λ), the accumulation set of an end of g_{#}(γ) is not equal to Λ. Lemma 4.1 implies that the ends of g_{#}(γ) are contained in G_{r−1} and Proposition 4.3 implies that g_{#}(γ) ⊂ G_{r−1}. The bounded cancellation lemma therefore implies that if β ⊂ G_{r−1} is a subpath of λ, then with the exception of uniformly bounded initial and terminal segments, [g(β)] ⊂ G_{r−1}. In particular, EL_{r}([g(β)]) is bounded by some uniform constant C_{1}.

We can approximate EL_{r}(σ) by ∑_{i} T (σ)a_{i}EL_{r}(α_{i}). The error in this approximation comes in two ways. First from the fact that a_{i}T (σ) is only an approximation to the number of occurrences of α_{i} that are entirely contained in σ. Second from the α_{j}s that intersect σ but are not contained in σ. Thus EL_{r}(σ) ∼ ∑_{i} T (σ)a_{i}EL_{r}(α_{i}). For all ϵ > 0 there exists M = M(ϵ) and T = T (M, ϵ) such that the percentage error in the approximation is less than ϵ so long as m ≥ M and T (σ) ≥ T.

We can approximate EL_{r}([g(σ)]) by ∑_{i} T (σ)a_{i}EL_{r}([g(α_{i})]). The error in this approximation comes in four ways. The first two are as in the previous case. The third comes from the fact that edges may cancel when the concatenation of the [g(β)]’s and the [g(α_{j})]’s is tightened to [g(σ)]. If C is the maximal number of edges cancelled at any juncture, then the loss can be at most 2T (σ)C edges in H_{r}. The fourth error contribution comes from the fact that [g(β)] may contain up to C_{1} edges in H_{r}; the gain can be at most T (σ)C_{1} edges in H_{r}. Thus EL_{r}(σ) ∼ ∑_{i} T (σ)a_{i}EL_{r}([g(α_{i})]. For all ϵ > 0 there exists M = M(ϵ) and T = T (M, ϵ) such that the percentage error in the approximation is less than ϵ so long as m ≥ M and T (σ) ≥ T.

Let

K_{m} = \frac{∑_{i} a_{i}EL_{r}([g(α_{i})])}{∑_{i} a_{i}EL_{r}(α_{i})}.

Then for all ϵ > 0 there exists m = m(ϵ) such that

(1 − ϵ)K_{m} ≤ \frac{EL_{r}([g(σ)])}{EL_{r}(σ)} ≤ (1 + ϵ)K_{m}

for all sufficiently large EL_{r}(σ). It follows that μ = lim K_{m(ϵ)} exists and Ψ expands Λ by the factor μ.

In the proof of Corollary 4.9, we showed that μ(ΨΨ^{−1}) = μ(Ψ)μ(Ψ^{−1}). This implies that μ(Ψ^{−1}) = μ(Ψ)^{−1}.

Suppose now that μ(Ψ) > 1 and that σ is a subpath of a generic leaf λ of Λ^{+}. Let σ_{1} be the subpath of g_{#}(λ) obtained from [g(σ)] by removing the initial and terminal subpaths of length C. The bounded cancellation lemma implies that g_{#}(N(σ)) ⊂ N(σ_{1}). If EL_{r}(σ) is sufficiently large, then EL_{r}(σ_{1}) > EL_{r}(σ) and we may iterate the argument to produce σ_{k} with increasing EL_{r}-length such that g_{#}(N(σ_{k−1})) ⊂ N(σ_{k}) and hence g_{#}^{k}(N(σ)) ⊂ N(σ_{k}). Lemma 4.1 implies that for any finite subpath λ_{0} of λ, and in particular for λ_{0} = σ, N(σ_{k}) ⊂ N(λ_{0}) for all sufficiently large k. It follows that N(σ) is an attracting neighborhood of λ for the action of some Ψ_{#}^{k}. Since Λ is Ψ-invariant, U = N(σ) ∩ Ψ_{#}(N((σ)) ∩ ⋯ ∩ Ψ_{#}^{k−1}(N(σ)) is an attracting neighborhood of λ for the action of Ψ. Lemma 4.4 implies that Λ is an expanding lamination for Ψ.

For the last part of the proposition, suppose that f′ : G′ → G′ is a relative train track map representing Ψ and that Λ is the expanding lamination associated to the stratum H′_{s}. Let μ′_{s} be the Perron Frobenius eigenvalue for M′_{s} and let EL′_{s} be the edge length function that counts edges of H′_{s} in G′. Choose a topological representative h : G → G′ that respects the markings.

We know that if μ′ is computed using G′, H′_{s} and EL′_{s} instead of G, H_{r} and EL_{r}, then μ′ = μ′_{s}. For any path σ ⊂ G_{r}, [hg(σ)] and [f′h(σ)] differ by initial and terminal segments of uniformly bounded size. It therefore suffices to show that the ratio EL′_{s}([h(σ)])/EL_{r}(σ) has a non-zero limit L as EL_{r}(σ) tends to infinity and that this limit is independent of σ.

An argument completely analogous to the second approximation in the first part of this proof (the one with four error terms) shows that EL′_{s}([h(σ)]) ∼ ∑_{i} T (σ)a_{i}EL′_{s}([h(α_{i})]); we leave the details of this modification to the reader.

Let

L_{m} = \frac{∑_{i} a_{i}EL′_{s}([h(α_{i})])}{∑_{i} a_{i}EL_{r}(α_{i})}.

Then for all ϵ > 0 there exists m = m(ϵ) such that

(1 − ϵ)L_{m} ≤ \frac{EL′_{s}([h(σ)])}{EL_{r}(σ)} ≤ (1 + ϵ)L_{m}

for all sufficiently large EL_{r}(σ). As in the previous case L = lim L_{m} exists and is non-zero.

4.2 Detecting F_{2} via Laminations

We now show how expanding laminations can be used to prove that a group of outer automorphisms contains a free subgroup of rank two. Out criterion is based on a technique of Tits [Ti], a version of which appears in the next lemma.

Lemma 4.10. Suppose that a group H acts on a space X, that there are subsets U^{+}, U^{−}, V^{+} and V^{−} of X, a point x ∈ X and elements f, g ∈ H such that

1. x ∉ (U^{+} ∪ U^{−} ∪ V^{+} ∪ V^{−})

2. f({x} ∪ U^{+} ∪ V^{+} ∪ V^{−}) ⊂ U^{+}

3. f^{−1}({x} ∪ U^{−} ∪ V^{+} ∪ V^{−}) ⊂ U^{−}

4. g({x} ∪ U^{+} ∪ U^{−} ∪ V^{+}) ⊂ V^{+}

5. g^{−1}({x} ∪ U^{+} ∪ U^{−} ∪ V^{−}) ⊂ V^{−}

Then the subgroup of H generated by f and g is isomorphic to F_{2}.

Proof of Lemma 4.10 If w = e_{k} ⋯ e_{1}, k ≥ 1, where each e_{i} = f, f^{−1}, g or g^{−1} and where each e_{i+1} ≠ ē_{i}, then an easy induction argument shows that if e_{k} = f [respectively, f^{−1}, g, g^{−1}], then w(x) ∈ U^{+} [respectively U^{−}, V^{+}, V^{−}]. In particular, w(x) ≠ x so that w does not determine the identity element in H.

In our case, H will be a subgroup of Out(F_{n}) and X will be the space B. The ‘ping pong’ method of Tits can be recast as follows.

Lemma 4.11. Suppose that Λ^{+} ∈ L(O), Λ^{−} ∈ L(O^{−1}) and Γ^{+} ∈ L(Ψ), Γ^{−} ∈ L(Ψ^{−1}) are paired laminations such that generic leaves of Λ^{+} and Λ^{−} are weakly attracted to Γ^{+} [respectively Γ^{−}] under the action of Ψ [respectively Ψ^{−1}] and such that generic leaves of Γ^{+} and Γ^{−} are weakly attracted to Λ^{+} [respectively Λ^{−}] under the action of O [respectively O^{−1}]. Then O^{N} and Ψ^{N} generate a free subgroup of rank two for all sufficiently large N.

Proof of Lemma 4.11 Let λ^{±} and γ^{±} be generic leaves for Λ^{±} and Γ^{±}; let U^{±} and V^{±} be attracting neighborhoods of λ^{±} and γ^{±} respectively.

There exists k ≥ 0 such that O_{#}^{k}(γ^{+}) ⊂ U^{+}. Since {Ψ_{#}^{l}(V^{+})} is a neighborhood basis for γ^{+}, there exists l ≥ 0 such that O_{#}^{k}(Ψ_{#}^{l}(V^{+})) ⊂ U^{+}. This inclusion remains valid if k and/or l are increased.

Repeating this argument on various combinations of O^{±1} and Ψ^{±1}, we see that there there exist K, L ≥ 0 such that

• O_{#}^{K}Ψ_{#}^{L}(V^{+}), O_{#}^{K}Ψ_{#}^{−L}(V^{−}) ⊂ U^{+}

• O_{#}^{−K}Ψ_{#}^{L}(V^{+}), O_{#}^{−K}Ψ_{#}^{−L}(V^{−}) ⊂ U^{−}

• Ψ_{#}^{K}O_{#}^{L}(U^{+}), Ψ_{#}^{K}O_{#}^{−L}(U^{−}) ⊂ V^{+}

• Ψ_{#}^{−K}O_{#}^{L}(U^{+}), Ψ_{#}^{−K}O_{#}^{−L}(U^{−}) ⊂ V^{−}

Replacing U^{+} [respectively U^{−}, V^{+}, V^{−}] by O_{#}^{L}(U^{+}) [respectively O_{#}^{−L}(U^{−}), Ψ_{#}^{L}(V^{+}), Ψ_{#}^{−L}(V^{−})] and defining N = K + L, we have

1. O_{#}^{N}(V^{+}), O_{#}^{N}(V^{−}) ⊂ U^{+}

2. O_{#}^{−N}(V^{+}), O_{#}^{−N}(V^{−}) ⊂ U^{−}

3. Ψ_{#}^{N}(U^{+}), Ψ_{#}^{N}(U^{−}) ⊂ V^{+}

4. Ψ_{#}^{−N}(U^{+}), Ψ_{#}^{−N}(U^{−}) ⊂ V^{−}.

Since U^{±} and V^{±} are attracting neighborhoods, we also have

5. O_{#}^{N}(U^{+}) ⊂ U^{+}; O_{#}^{−N}(U^{−}) ⊂ U^{−}; Ψ_{#}^{N}(V^{+}) ⊂ U^{−}; and Ψ_{#}^{−N}(V^{−}) ⊂ V^{−}.

Choose a circuit σ ⊂ G that is weakly attracted to Λ^{+} under the action of O and to Λ^{−} under the action of O^{−1}. By (3) and (4), O_{#}^{m}(σ) is weakly attracted to Γ^{+} [respectively Γ^{−}] under the action of Ψ [respectively Ψ^{−1}] for all sufficiently large m, say m ≥ M. Let x = O_{#}^{M}(σ) ∈ B. Since expanding laminations do not have periodic generic leaves, we can choose L so that x ∉ (U^{+} ∪ U^{−} ∪ V^{+} ∪ V^{−}). For large K and hence large N, O_{#}^{N}(x) ∈ U^{+}; O_{#}^{−N}(x) ∈ U^{−}; Ψ_{#}^{N}(x) ∈ U^{−}; and Ψ_{#}^{−N}(x) ∈ V^{−}.

We have now verified all the hypothesis of Lemma 4.10.

Remark 4.12. If the constant N of Lemma 4.11 is sufficiently large, then every non-trivial element of the subgroup generated by O^{N} and ψ^{N} has exponential growth. Using the notation of the proof of Lemma 4.11 we sketch a proof of this observation.

Choose a marked graph G. There is no loss in assuming that U^{±} = N(γ_{0}^{±}) and V^{±} = N(λ_{0}^{±}) for subpaths γ_{0}^{±} ⊂ γ^{±} and λ_{0}^{±} ⊂ λ^{±}. Since generic leaves are birecurrent, there are subpaths γ_{1}^{±} ⊂ γ^{±} and λ_{1}^{±} ⊂ λ^{±} such that γ_{1}^{±} contains two disjoint copies of γ_{0}^{±} and λ_{1}^{±} contains two disjoint copies of λ_{0}^{±}. Define U_{1}^{±} = N(γ_{1}^{±}) ⊂ U^{±} and V_{1}^{±} = N(λ_{1}^{±}) ⊂ V^{±}. By increasing N if necessary, we can modify (1)-(5) so that the right hand side of the containment statements use U_{1}^{±} and V_{1}^{±} in place of U^{±} and V^{±}. Thus, for example, if σ is any line that contains γ_{0}^{+}, λ_{0}^{+} or λ_{0}^{−}, then O_{#}^{N}(σ) contains two disjoint copies of γ_{0}^{+}. Suppose that w = e_{k} ⋯ e_{1}, k ≥ 1, where each e_{i} is O^{N}, O^{−N}, Ψ^{N} or Ψ^{−N} and where each e_{i+1} ≠ ē_{i}. A straightforward induction argument shows that w_{#}(x) contains 2^{k} disjoint copies of one of the subpaths γ_{1}^{+}, γ_{1}^{−}, λ_{1}^{+} or λ_{1}^{−}. Applying this to iterates of w, we conclude that w has exponentially growth.

We can now state the specific application of Lemma 4.11 that we will use.

Corollary 4.13. Suppose that O is eg- aperiodic, that Λ^{+} ∈ L(O) and Λ^{−} ∈ L(O^{−1}) are paired laminations and that there is an element ψ ∈ H such that generic leaves of the four laminations ψ^{±1}(Λ^{±}) are weakly attracted to Λ^{+} under the action of O and to Λ^{−} under the action of O^{−1}. Then H contains a free subgroup of rank two.

Proof of Corollary 4.13 Define Ψ = ψOψ^{−1} and note that Γ^{+} = ψ_{#}(Λ^{+}) ∈ L(Ψ^{+}) and Γ^{−} = ψ_{#}(Λ^{−}) ∈ L(Ψ^{−1}) are paired laminations. The condition on ψ_{#}^{±1}(Λ^{±}) can be restated as

1. Γ^{±} is weakly attracted to Λ^{+} [respectively Λ^{−}] under the action of O [respectively O^{−1}].

2. ψ_{#}^{−1}Λ^{±} is weakly attracted to ψ_{#}^{−1}(Γ^{+}) [respectively ψ_{#}^{−1}(Γ^{−})] under the action of ψ^{−1}Ψψ [respectively ψ^{−1}Ψ^{−1}ψ].

This last condition is equivalent to

3. Λ^{±} is weakly attracted to Γ^{+} [respectively Γ^{−}] under the action of Ψ [respectively Ψ^{−1}].

The corollary therefore follows from Lemma 4.11.

5 Splittings

The key to understand the iterated images [f^{k}(σ)] of a (possibly infinite) path or a circuit σ under the action of a relative train track map f : G → G is to subdivide σ into non-interacting pieces that are dominated by a single stratum.

A decomposition σ = σ_{1} … σ_{l} is called a k-splitting if [f^{k}(σ)] = [f^{k}(σ_{1})] … [f^{k}(σ_{l})], and is called a splitting if it is a k-splitting for all k ≥ 0. The endpoints of the σ_{i}’s are called the splitting set. As a matter of notation, we will only use · to separate subpaths if the separation is a splitting.

For future references we record the following obvious fact.

Remark 5.1. If σ = σ_{1} · σ_{2} and σ_{1} = σ′_{1} · σ′′_{1}, then σ = σ′_{1} · σ′′_{1} · σ_{2}.

We begin with the basic splitting lemma for non-exponentially growing strata. The restriction on the endpoints of σ in the following lemma reduces the number of special cases that we must consider. If σ intersects the interior of some edge of H_{i} then we say that σ intersects H − i non-trivially.

Lemma 5.2. Suppose that H_{i} = {E_{i}} is a non-exponentially growing stratum of a topological representative f : G → G and that f(E_{i}) = E_{i}u_{i} for some path u_{i} ⊂ G_{i−1}. Suppose also that σ ⊂ G_{i} is a path or circuit that intersects H_{i} non-trivially and that the endpoints of σ, if any, are not contained in the interior of E_{i}. Then σ can be split into subpaths of the following type, where γ is a subpath in G_{i−1} : γ, E_{i}γĒ_{i}, E_{i}γ, or γĒ_{i}.

We refer to these four types of paths as basic paths.

Proof of Lemma 5.2 Divide σ each time it begins to cross E_{i} and each time it finishes crossing Ē_{i}. This gives a decomposition σ = σ_{1} … σ_{m} into subpaths where each σ_{k} is one of the allowable types and where m is as small as possible. We call this the minimal subdivision of σ with respect to H_{i}. We will show, after possibly removing from σ a first or last subpath of type γ whose tightened image is trivial, that [f(σ)] = [f(σ_{1})] … [f(σ_{m})] is the minimal subdivision of [f(σ)] with respect to H_{i}. This shows that σ = σ_{1} … σ_{m} is a 1-splitting and induction shows that it is a k-splitting for all k.

If σ_{k} = γ, then [f(σ_{k})] = γ′ ⊂ G_{i−1}. Moreover, if k ≠ 1 or m, then the endpoints of σ_{k} are initial points of E_{i} and are therefore fixed by f; in particular γ′ is not trivial.

If σ_{k} = E_{i}γĒ_{i}, then [f(σ_{k})] = E_{i}γ′Ē_{i} where γ′ = [u_{i}f(γ)ū_{i}] ⊂ G_{i−1}. Since γ is a loop, γ′ is not trivial.

If σ_{k} = E_{i}γ, then [f(σ_{k})] = E_{i}γ′ where γ′ = [u_{i}f(γ)] ⊂ G_{i−1}.

If σ_{k} = γĒ_{i}, then [f(σ_{k})] = γ′Ē_{i} where γ′ = [f(γ)ū_{i}] ⊂ G_{i−1}.

This completes the proof that [f(σ_{k})] has the same form as σ_{k} and can only be trivial if k = 1 or m and σ_{k} = γ. It is easy to check that [f(σ)] = [f(σ_{1})] … [f(σ_{m})] and that this is the minimal subdivision of [f(σ)]; we leave this to the reader.

We will consider further splittings of basic paths in section 6.5. For the rest of this section we assume that f : G → G is a topological representative and that σ ⊂ G_{r} is a path or circuit that intersects H_{r} non-trivially for some exponentially growing stratum H_{r}. Denote the maximal invariant set {x ∈ H_{r} : f^{k}(x) ∈ H_{r}, ∀k ≥ 0} by I_{r}. The train track property gives the following basic splitting property.

Lemma 5.3. Suppose that f : G → G is a relative train track map, that H_{r} is an exponentially growing stratum and that σ ⊂ G_{r} is r-legal. Divide σ into subpaths σ = σ_{1}σ_{2} along a point x ∈ I_{r} that has arbitrarily small neighborhoods in σ that intersect H_{r} non-trivially. Then σ = σ_{1} · σ_{2}.

Proof of Lemma 5.3. Lemma 3.1 and induction on k imply that σ = σ_{1}σ_{2} is a k-splitting for all k.

The next lemma is a local version of Lemma 5.3. Its proof exploits the fact that exponential growth dominates bounded loss if the initial length is large enough.

Suppose that τ is a path in G and that α ⊂ G_{r} is a subpath of τ. If there are k H_{r}-edges to the left and to the right of α in τ , define W_{k}(α) to be the subpath of τ that begins with the k^{th} H_{r}-edge to the left of α and ends with the k^{th} H_{r}-edge to the right of α. We say that α is k-protected in τ if its first and last edges are in H_{r}, if W_{k}(α) ⊂ G_{r} and if W_{k}(α) is r-legal.

Lemma 5.4. Assume that f : G → G is a relative train track map and that H_{r} is an exponentially growing stratum. There is a constant K such that τ ⊂ G can be split at the endpoints of α ⊂ G_{r} whenever α is K-protected in τ.

Proof of Lemma 5.4. Choose l so that the f^{l}-image of an edge in H_{r} contains at least two edges in H_{r}. Let K = 2lC where C is the bounded cancellation constant for f : G → G .

We will show that if α is K-protected in τ, then τ can be i-split at the endpoints of α for 1 ≤ i ≤ l. Moreover, [f^{l}(α)] is K-protected in [f^{l}(τ)]. Iterating this argument proves that τ can be i-split at the endpoints of α for all i.

Lemma 3.1 and the bounded cancellation lemma imply that if α is kprotected for k > C, then τ can be 1-split at the endpoints of α and that [f(α)] is k − C protected. Thus if α is K protected, then τ can be i-split at the endpoints of α and also at the endpoints of W_{K−lC}(α) = W_{lC}(α) for 1 ≤ i ≤ l. Since [f^{l}(W_{lC}(α))] ⊃ W_{2lC}([f^{l}(α)]) = W_{K}([f^{l}(α)]), [f^{l}(α)] is K-protected in [f^{l}(τ)].

Definition 5.5. Suppose that f : G → G is a relative train track map, that H_{r} is an exponentially growing stratum with expanding lamination Λ^{+} and that σ ⊂ G_{r} is a path or circuit. Then σ is weakly attracted to Λ^{+} if every subpath of some (and hence any) generic leaf of Λ^{+} occurs as an unoriented subpath of [f^{k}(σ)] for all sufficiently large k. Note that this agrees with our previous definition when σ is a circuit or a bi-infinite path.

Corollary 5.6. Assume that f : G → G is a relative train track map, that H_{r} is an exponentially growing stratum with expanding lamination Λ^{+} and that γ is a line, path or circuit. The following are equivalent:

1. γ is weakly attracted to Λ^{+}.

2. γ splits into subpaths, at least one of which is weakly attracted to Λ^{+}.

3. γ splits into subpaths, at least one of which is r-legal and has an iterate that contains an edge of H_{r}.

Proof of Corollary 5.6 If γ is weakly attracted to Λ^{+}, then some [f^{k}(γ)] contains an H_{r}-edge E that is K-protected. Lemma 5.4 implies that [f^{k}(γ)] splits at the endpoints of E. Thus (1) implies (3). It is immediate from the definitions of splitting and weak attraction that (2) implies (1). It is immediate from our construction of Λ^{+} that (3) implies (2).

Lemma 5.4 suggests that if H_{r} is an exponentially growing stratum, then σ ⊂ G_{r} can be split into pieces that are either r-legal or are neighborhoods of an illegal turn in H_{r}. We make that precise in Lemma 5.8 below. First we choose the appropriate neighborhoods of an illegal turn in H_{r}.

Let P_{r} be the set of paths ρ ⊂ G_{r} such that :

(i) Each [f^{k}(ρ)] contains exactly one illegal turn in H_{r}.

(ii) The initial and terminal segments of each [f^{k}(ρ)] are contained in H_{r}.

(iii) There is a uniform bound to the number of H_{r}-edges in [f^{k}(ρ)].

The following lemma is essentially contained in the proof of Lemma 5.11 of [BH92]. We give a proof here for the convenience of the reader. For any path σ ⊂ G_{r}, let σ ∩ H_{r} be the ordered sequence of edges and partial edges of H_{r} in σ.

Lemma 5.7. Assume that f : G → G is a relative train track map and that H_{r} is an exponentially growing stratum. Then P_{r} is a finite f_{#}-invariant set.

Proof of Lemma 5.7 The f_{#}-invariance of P_{r} is immediate from the definition.

Write ρ = αβ where α and β are r-legal. When f^{k}(α) and f^{k}(β) are tightened to [f^{k}(α)] and [f^{k}(β)], no H_{r}-edges are cancelled. When [f^{k}(α)][f^{k}(β)] is tightened to [f^{k}(ρ)], an initial segment of [f^{k}(ᾱ)] is cancelled with an initial segment of [f^{k}(β)]. Since [f^{k}(ρ)] has an illegal turn in H_{r}, the first non-cancelled edges in [f^{k}(ᾱ)] and [f^{k}(β)] are contained in H_{r}. The cancellation between [f^{k}(ᾱ)] and [f^{k}(β)] is therefore determined by [f^{k}(ᾱ)] ∩ H_{r} and [f^{k}(β)] ∩ H_{r}: the two paths cancel until the first distinct elements of [f^{k}(ᾱ)] ∩ H_{r} and [f^{k}(β)] ∩ H_{r} are encountered. Note that [f^{k}(ᾱ)] ∩ H_{r} and [f^{k}(β)] ∩ H_{r} are determined by α ∩ H_{r} and β ∩ H_{r}.

We claim that ρ ∩ H_{r} takes on only finitely many values. Condition (iii) and Lemma 5.4 imply that ρ contains at most 4K H_{r}-edges. Let α_{0} and β̄_{0} be the initial (possibly partial) edge of α ∩ H_{r} and β̄∩ H_{r}. The only possible difficulty is that there exist ρ = αβ and ρ′ = α′β′ such that the only difference between ρ ∩ H_{r} and ρ′ ∩ H_{r} is that the length of α_{0} and α′_{0} and the length of β_{0} and β′_{0} may differ. Suppose for concreteness that α′_{0} is a proper subset of α_{0} and that A is their difference. Property (ii) implies that the cardinality of [f^{k}(A)] ∩ H_{r} grows without bound. Property (iii) therefore implies that edges in [f^{k}(A)] ∩ H_{r} must be cancelled with edges of [f^{k}(β)] ∩ H_{r}. This implies that all of [f^{k}(ᾱ′)] ∩ H_{r} is cancelled with a proper initial segment X of [f^{k}(β)] ∩ H_{r}. But X, like every initial segment of [f^{k}(β)] ∩ H_{r}, either contains or is contained in [f^{k}(β′)] ∩ H_{r}. This contradicts condition (i) for ρ′ and so verifies our claim.

To complete the proof, it suffices to show that there is a uniform bound to the number of edges in ρ. The first and last edge segments of ρ take on only finitely many values and are contained in H_{r}. By property (iii), there is a uniform k such that f^{k} maps these first and last edge segments over all of [f^{k}(ρ)]. This implies that [f^{k}(ρ)], and hence ρ has a uniformly bounded number of edges.

Lemma 5.8. Suppose that f : G → G is a relative train track map, that H_{r} is an exponentially growing stratum, that σ ⊂ G_{r} and that each f^{k}(σ) has the same finite number of illegal turns in H_{r}. Then σ can be split into subpaths that are either r-legal or elements of P_{r}.

We will use the following abstract construction of the canonical splitting set for σ to prove Lemma 5.8. We work in the universal cover Γ of G where paths are imbedded rather than just immersed. Let f̃: Γ → Γ be a lift of f : G → G and let σ̃ be a lift of σ. If σ is a circuit, then σ̃ is the axis of a covering translation T. For this construction, assume that σ and hence σ̃ is oriented.

For each k ≥ 0, let Σ̃_{k} be the minimal subdivision of σ̃ into pieces that map by f̃^{k} to an edge of Γ. In other words, Σ̃_{k} is obtained from σ̃ by subdividing at the full f̃^{k} pre-image of the vertex set of Γ. Define S^{0}(σ̃) = σ̃ and then inductively define S^{k}(σ̃) ⊂ S^{k−1}(σ̃) to be the union of the edges ẽ_{i} of Σ̃_{k} satisfying:

• ẽ_{i} ⊂ S^{k−1}(σ̃)

• f^{k}(e_{i}) ⊂ [f^{k}(σ)]

• If ẽ_{j} is another edge of Σ̃_{k} with the same f̃^{k} image (ignoring orientation) as ẽ_{i}, then ẽ_{i} precedes ẽ_{j} in the order determined by the orientation on σ̃.

Note that each S^{k}(σ̃) is a closed subset of σ̃ with f^{k}(S^{k}(σ)) = [f^{k}(σ)] and that if σ̃ is the axis of a covering translation T then S^{k}(σ̃) is T -invariant. Define S̃(σ̃) = ∩_{k=0}^{∞}S^{k}(σ̃) and S(σ) ⊂ σ to be be the projected image of S̃(σ̃).

Lemma 5.9. Any finite subset X of S(σ) is a splitting set for σ.

Proof of Lemma 5.9 The orientation on σ̃ provides a natural ordering on points of σ̃. The intermediate value theorem implies that if x̃ < ỹ in S^{k}(σ̃), then f̃^{k}(x̃) ≤ f̃^{k}(ỹ) in [f̃^{k}(σ̃)]. This implies that a decomposition along points in X̃ is a k-splitting. Since k is arbitrary, the decomposition is a splitting.

Proof of Lemma 5.8 Points in σ that lie sufficiently close to an illegal turn in H_{r} have images outside of [f(σ)] and so are not contained in the canonical splitting set S(σ). There are nearest points of S(σ) on either side of such an illegal turn of σ. Split σ at these points and let σ_{1} be the resulting subpath of σ that contains the illegal turn in question.

It suffices to show that σ_{1} ∈ P_{r}. Since σ_{1} results from splitting along points in S(σ), the intermediate value theorem implies that S(σ_{1}) ⊂ S(σ). Thus S(σ_{1}) ⊂ ∂σ_{1} and there exist k > 0 and arbitrarily short initial and terminal subintervals α and β of σ_{1} such that [f^{k}(σ_{1})] = [f(^{k}α)][f^{k}(β)]. This implies that [f^{k}(σ_{1})] contains at most one illegal turn in H_{r} for all sufficiently large k. But the number of illegal H_{r}-turns of [f^{k}(σ)], and hence of [f^{k}(σ_{1})], is independent of k, so condition (i) of P_{r} is satisfied. This implies that both [f^{k}(α)] and [f^{k}(β)] intersect H_{r} so condition (ii) of P_{r} is also satisfied. Condition (iii) follows from Lemma 5.4 and that fact that S(σ_{1}) ⊂ ∂σ_{1}.

6 Improved Relative Train Track Maps

Lemma 4.13 connects the Tits Alternative to the action of an eg-aperiodic O on bi-infinite paths and in particular to the basins of attraction for an expanding lamination pair Λ^{±}. In the next section we state and prove our Weak Attraction Theorem which characterizes these basins of attraction for ‘topmost’ laminations. In this section, we lay the groundwork for that analysis.

This is the most technical section in the paper. All future references to results in this section will be made to subsection 6.1. It is therefore possible to skim the proof of Theorem 6.4 and follow the proof of Theorem 8.1.

6.1 Statements

Definition 6.1. A path ρ ⊂ G is a periodic Nielsen path for f : G → G if [f^{k}(σ)] = σ for some k ≥ 1; if k = 1, then σ is a Nielsen path. We say that σ is an indivisible (periodic) Nielsen path if it can not be written as a non-trivial concatenation of (periodic) Nielsen paths.

It is shown in Lemma 5.11 of [BH92] that if f : G → G is a relative train track map, then the indivisible periodic Nielsen paths in G_{r} that intersect H_{r} non-trivially are precisely the elements of P_{r} that have periodic orbit under the action of f_{#}.

Definition 6.2. Suppose that : H_{i} = E_{i} is a non-exponentially growing stratum and that f(E_{i}) = E_{i} · τ^{l} for some Nielsen path τ ⊂ G_{i−1} and some l > 0. Then for all k ≠ 0, the basic path E_{i}τ^{k}Ē_{i} is said to be exceptional. If j ≠ i and H_{j} = E_{j} ⊂ G_{i−1} is a non-exponentially growing stratum with f(E_{j}) = E_{j} · τ^{m} for some m ≠ 0, then for all k the basic path E_{i}τ^{k}Ē_{j} is also said to be exceptional. Note that for any exceptional path σ, the canonical splitting set S(σ) = ∂σ.

Definition 6.3. Suppose that :

• g : Q → Q is a homotopy equivalence of a (not necessarily connected) graph.

• α_{1}, …, α_{m} are circuits in Q that are permuted by g_{#}

• S is a compact surface with m + 1 boundary components, α_{1}^{∗}, …, α_{m}^{∗} and ρ^{∗}

• ϕ : S → S is a pseudo-Anosov homeomorphism that permutes the α_{i}^{∗}’s in the same way that g_{#} permutes the α_{i}’s.

Let A be the union of m annuli A_{i}, …, A_{m}. Define Y to be the space obtained from Q ∪ A ∪ S by attaching one end of A_{i} to α_{i} and the other end to α_{i}^{∗}. Extend g ∪ ϕ to a homotopy equivalence h : Y → Y by interpolating between g(α_{i}) and ϕ(α_{i}^{∗}) on A. We say that h : Y → Y is a geometric extension of g : Q → Q.

Suppose that f : G → G is a topological representation and that H_{i} is an exponentially growing stratum. We say that H_{i} is a geometric stratum if there exists h : Y → Y as above and a homotopy equivalence Φ : (Y, Q) → (G_{i}, G_{i−1}) such that fΦ ≃ Φh. In particular, Φ_{#} identifies the outer automorphism induced by h with the outer automorphism induced by f.

The relative train track maps of [BH92] must be modified to suit our present needs. In [BH92] it was sufficient to control the Nielsen paths; in this paper, we must also control the periodic Nielsen paths. We do this by replacing O by an iterate in which every periodic Nielsen path is a Nielsen path and then applying the techniques of [BH92]. This is carried out in subsection 6.2. [BH92] contains a characterization of the irreducible outer automorphisms that arise as pseudo-Anosov mapping classes. In subsection 6.3, we generalize this by characterizing geometric strata.

There are no restrictions on the non-exponentially growing strata of a relative train track map . By passing to an iterate and subdividing if necessary (or by adding homological restrictions as in [BFH96b]), we may assume that each such stratum is a single edge E_{i} and that f(E_{i}) = E_{i}u_{i} for some path u_{i} ⊂ G_{i−1}. We introduce a move, called sliding, to arrange that u_{i} is a circuit and that f(E_{i}) = E_{i} · u_{i}. This is carried out in subsection 6.4 and analyzed further in subsection 6.5.

Theorem 6.4. For every outer automorphism O and O-invariant free factor system F there is an eg-aperiodic relative train track map f : G → G representing an iterate of O with the following properties.

• F = F(G_{r}) for some filtration element G_{r}.

• f is reduced.

• Every periodic Nielsen path has period one.

• For every vertex v ∈ G, f(v) is a fixed point. If v is an endpoint of an edge in a non-exponentially growing stratum then v is a fixed point. If v is the endpoint of an edge in an exponentially growing stratum H_{i} and if v is also contained in a non-contractible component of G_{i−1}, then v is a fixed point.

• H_{i} is a zero stratum if and only if it is the union of the contractible components of G_{i}.

• If H_{i} is a zero stratum, then

z-(i) H_{i+1} is an exponentially growing stratum.

z-(ii) There are no valence two vertices in G with both edges in H_{i}.

z-(iii) f|H_{i} is an immersion.

z-(iv) G_{i+1} has no valence one vertices.

• If H_{i} is a non-exponentially growing stratum, then

ne-(i) H_{i} is a single edge E_{i}.

ne-(ii) f(E_{i}) = E_{i} · u_{i} for some closed path u_{i} ⊂ G_{i−1} whose endpoints are fixed by f.

ne-(iii) If σ ⊂ G_{i} is a basic path that is not entirely contained in G_{i−1}, then (up to a change of orientation) either : (i) some [f^{k}(σ)] splits into pieces, one of which equals E_{i}; or (ii) u_{i} is a Nielsen path and some [f^{k}(σ)] is exceptional.

• If H_{i} is an exponentially growing stratum then

eg-(i) There is at most one indivisible Nielsen path ρ_{i} ⊂ G_{i} that intersect H_{i} non-trivially. The initial edges of ρ_{i} and ρ̄_{i} are distinct edges in H_{i}.

eg-(ii) If ρ_{i} exists and H_{i} is not geometric then there is an edge E of H_{i} that ρ_{i} crosses exactly once. (See also Lemma 6.7 below.)

eg-(iii) If H_{i} is geometric, then : (i) ρ_{i} is a closed path with common endpoint in the interior of H_{i}; (ii) the circuit determined by ρ_{i} corresponds to the unattached peripheral curve ρ^{∗} of S; and (iii) the surface S is connected.

Definition 6.5. A relative train track map that satisfies the conclusions of Theorem 6.4 is said to be improved.

The following lemma is used to analyze non-geometric strata.

Definition 6.6. For any subgraph X of G and finite path ρ ⊂ G, define < X, ρ > to be the semigroup of paths that can be decomposed into a concatenation of subpaths that are either entirely contained in X or are equal to ρ or ρ̄.

Lemma 6.7. Suppose that f : G → G is reduced, that H_{r} is an exponentially growing stratum, that ρ_{r} ⊂ G_{r} is a Nielsen path that crosses some edge E of H_{r} exactly once and that the first and last edges of ρ_{r} are contained in H_{r}. Then the endpoints of ρ_{r} are distinct and at least one of them is not contained in a non-contractible component of G_{r−1}. If X is a subgraph of G that does not contain any edges of H_{r}, then there is a free factor system that carries the same bi-infinite paths as < X, ρ_{r} >.

Proof of Lemma 6.7 Let Ĝ be the graph obtained from G by removing the edge E and adding a new edge Ê with endpoints equal to the initial and terminal endpoints of ρ. Decompose ρ into the concatenation of subpaths ρ = αEβ where α and β are disjoint from E. There is a homotopy equivalence h : G → Ĝ that is the ‘identity’ on all edges other than E and that satisfies h(E) = ᾱÊβ̄. (The homotopy inverse sends Ê to ρ_{r}.) The map h_{#} induces a bijection between the bi-infinite paths in < X, ρ_{r} > and the bi-infinite paths in the subgraph X ∪ Ê of Ĝ. In particular, < X, ρ_{r} > carries exactly the same bi-infinite paths as the free factor system F(X ∪ Ê).

Suppose now that X = G_{r−1}. If the endpoints of ρ_{r} are equal or are both contained in non-contractible components of G_{r−1}, then F(X ∪ Ê) is strictly larger than F(X) = F(G_{r−1}). An r-legal bi-infinite path in < X, ρ_{r} > must lie entirely in X. Thus F(X ∪Ê) does not carry Λ^{+} and so is strictly smaller than F(G_{r}). Since < X, ρ_{r} > is f_{#}-invariant, this contradicts the assumption that f : G → G is reduced and completes the proof.

An outer automorphism O is said to have polynomial growth if some (and hence every) relative train track map representing O has no exponentially growing strata. The set of all polynomial growth outer automorphisms is denoted P G(F_{n}). An element of GL(n, ℤ) is unipotent if it is conjugate to an upper triangular matrix with ones on the diagonal. We say that an element of P G(F_{n}) is unipotent if its image in GL(n, ℤ) is unipotent. The set of unipotent elements of P G(F_{n}) is denoted UP G(F_{n}) and plays a central role in [BFH96b] and [BFH96c]. We conclude this subsection with a strengthening of Theorem 6.4 for elements of UP G(F_{n}).

Theorem 6.8. Suppose that O is a UP G and that F is an O-invariant free factor system. Then there is a relative train track map f : G → G representing O with the following properties.

1. F = F(G_{∇}) for some filtration element G_{r}.

2. Each H_{i} is a single edge E_{i} satisfying f(E_{i}) = E_{i} · u_{i} for some closed path u_{i} ⊂ G_{i−1}.

3. Every vertex of G is fixed by f.

4. Every periodic Nielsen path has period one.

5. If σ is any path with endpoints at vertices, then there exists M = M(σ) so that for each m ≥ M, [f^{m}(σ)] splits into subpaths that are either single edges or exceptional subpaths.

6. M(σ) is a bounded multiple of the edge length of σ.

The proof of Theorem 6.8 is given in subsection 6.6.

6.2 Nielsen Paths

Suppose that Λ_{1}, …, Λ_{l} are the expanding laminations for an eg-aperiodic O, that μ_{i} are the expansion factors for the action of O on Λ_{i} and that F is an O-invariant free factor system. We say that a topological representative f : G → G of O is F-Nielsen minimized if :

1. f : G → G is reduced.

2. F = F(G_{s}) for some filtration element G_{s}.

3. There are exactly l exponentially growing strata and the Perron Frobenius eigenvalues of their transition submatrices equal μ_{1}, …, μ_{l}.

4. If H_{r} is an exponentially growing stratum, then every indivisible periodic Nielsen path ρ ⊂ G_{r} that intersects H_{r} non-trivially has period one.

5. For each exponentially growing stratum H_{r}, let N_{r}(f) be the number of indivisible Nielsen paths ρ ⊂ G_{r} that intersect H_{r} non-trivially by N_{r}(f). Then N(f) = ∑_{r} N_{r}(f) is as small as possible subject to conditions (1) - (4).

Remark 6.9. We include (1) and (2) in the definition because it is a priori possible that the absolute minimum N(f) does not occur for a relative train track map satisfying (1) and (2). In fact, this does not happen but we do not use that fact in this paper.

Lemma 4.8 implies that condition (3) is satisfied by every relative train track map. In the course of proving Lemma 6.12 below, we must consider topological representations that are not relative train track maps. That is why the definition does not include the hypothesis that f : G → G is a relative train track map and why (4) and (5) do not refer to P_{r}.

If we eliminate conditions (1), (2) and (4) from the definition then we recover the definition of stable topological representative from page 42 of [BH92].

Lemma 6.10. For any O and F, there exists k > 0 and an F-Nielsen minimized relative train track map f : G → G representing O^{k}.

Proof of Lemma 6.10 By Corollary 4.7 and Lemma 3.6 there exists k ≥ 1 and an eg-aperiodic relative train track map that represents O^{k} and satisfies (1) and (2). Every relative train track map satisfies (3). Since every indivisible periodic Nielsen path is an element of the finite set P_{r}, we may assume, by increasing k, that (4) is satisfied. Fix k, and choose, among all topological representatives for O^{k} that satisfy (1) - (4), one, say f′ : G′ → G′, that minimizes N(f) and is hence F-Nielsen minimizing. If f′ : G′ → G′ is a relative train track map, we are done. If not, modify f′ : G′ → G′ by performing ‘core subdivisions’ and ‘collapsing of inessential paths’ to construct a relative train track map f : G → G. This is fully described in the proof of Lemma 5.13, Lemma 5.14 and Theorem 5.12 of [BH92]. Since f : G → G is a relative train track map, (3) is satisfied. The construction involves only subdivision, folding and the collapse of pre-trivial forests. As discussed in the proof of Lemma 3.6, (1) and (2) are satisfied. These operations do not change the period of any indivisible periodic Nielsen path nor any N_{r}(f) so f : G → G is still F-Nielsen minimized.

Suppose that f : G → G is a relative train track map and that H_{r} is an exponentially growing stratum. If ρ ⊂ G_{r} is an indivisible Nielsen path that intersects the interior of H_{r}, then ρ = αβ where α and β are r-legal and the turn (ᾱ, β) is an illegal turn in H_{r}. We say that the fold at (ᾱ, β) is a full fold if either all of the initial edge E_{1} of ᾱ can be folded with all or part of the initial edge E_{2} of β or all of E_{2} can be folded with all or part of E_{1}.

Lemma 6.11. Suppose that f : G → G is an F-Nielsen minimized relative train track map, that H_{r} is an exponentially growing stratum and that ρ ⊂ G_{r} is an indivisible Nielsen path that intersects the interior of H_{r}. Then the fold at the illegal turn of ρ in H_{r} is a full fold.

Proof of Lemma 6.11 This is a slight modification of Lemma 5.17 of [BH92]. There is a decomposition ρ = αβ into r-legal paths in G_{r} and there is a path τ ⊂ G_{r} such that [f(α)] = ατ and [f(β̄)] = β̄τ. It suffices (page 25 of [BH92]) to show that α and β can not be single edges.

Suppose that α and β are single edges. Let G′ be the graph obtained from G by identifying α and β̄ and let q : G → G′ be the quotient map. Since f(α) = ατ and f(β̄) = β̄τ, there is an induced map f′ : G′ → G′ defined by f′(q(E)) = [qf(E)] for each edge E of G. We claim that conditions (1) - (4) in the definition of F-Nielsen minimized are satisfied by f′ : G′ → G′.

Lemma 6.7 implies that the endpoints of ρ_{r} are distinct and that at least one of them is not contained in a non-contractible component of G_{r−1}. Thus q is a homotopy equivalence and F(G_{i}) = F(q(G_{i})) for all G_{i}. This implies conditions (1) and (2).

If E is an edge of G_{r}, then f′(q(E)) = qf(E). (If E belongs to H_{r}, then this uses the fact that an r-legal path in G_{r} does not cross the turn (ᾱ, β).) If E is an edge of G \ G_{r} then f′q(E) is obtained from qf(E) by cancelling edges in H_{r}. Thus H′_{i} = q(H_{i}) is exponentially growing if and only if H_{i} is exponentially growing and the Perron Frobenius eigenvalues for M_{i} and M′_{i} are equal. This implies that condition (3) holds.

For every path σ ⊂ G, [(f′)^{k}(q(σ))] = [qf^{k}(σ)]. In particular, if σ is a periodic Nielsen path for f, then σ′ = [q(σ)] is a periodic Nielsen path for f′ and the period of σ′ is at most the period of σ. If σ ≠ ρ_{r}, then σ′ is not trivial.

Conversely, suppose that σ′ ⊂ G′_{i} is a periodic Nielsen path for f′ : G′ → G′. We choose a path σ ⊂ G_{i} satisfying [q(σ)] = σ′ as follows. If the endpoints of σ′ do not lie in the edge q(α) = q(β̄), then there is a unique path σ ⊂ G satisfying [q(σ)] = σ′. If an endpoint of σ′ lie in q(α) = q(β̄) but is distinct from the initial endpoint of q(α) = q(β̄), then there is a unique path σ ⊂ G that has periodic endpoints and that satisfies [q(σ)] = σ′. Finally, if σ′ begins or ends at the initial endpoint of q(α) = q(β̄), then there is a unique path σ ⊂ G that does not begin or end with ρ_{r} or ρ̄_{r} and that satisfies [q(σ)] = σ′. In all cases, σ is a periodic Nielsen path and the period of σ′ equals the period of σ; moreover, if σ′ is indivisible, then σ is indivisible. Condition (4) for f′ now follows from condition (4) for f.

Since [q(ρ)] is trivial, we have decreased N(f). This contradiction completes the proof.

The following lemma is the main result of this subsection.

Lemma 6.12. If f : G → G is an F- Nielsen minimized relative train track map and H_{r} is an exponentially growing stratum, then there exists at most one indivisible Nielsen path ρ_{r} ⊂ G_{r} that intersects H_{r} non-trivially. If ρ_{r} exists, then its first and last edges are contained in H_{r}, the illegal turn of ρ_{r} in H_{r} is the only illegal turn in H_{r}, ρ_{r} crosses every edge in H_{r} at least once and either ρ_{r} crosses every edge of H_{r} exactly twice or ρ_{r} crosses some edge of H_{r} exactly once.

Proof of Lemma 6.12 This is Theorem 5.15 of [BH92] with the word stable replaced by F-Nielsen minimized. Having proved Lemma 6.11, the proof given in [BH92] carries over to this context without change.

6.3 Geometric Strata

The following proposition is the main result of this subsection. It generalizes Theorem 4.1 of [BH92].

Proposition 6.13. Suppose that f : G → G is an F-Nielsen minimized relative train track map, that H_{r} is an exponentially growing stratum, that ρ_{r} ⊂ G_{r} is an indivisible Nielsen path that crosses every edge of H_{r} exactly twice and that contractible components of G_{r−1} are made up of zero strata. Then : the endpoints of ρ_{r} are equal and are not contained in G_{r−1}, the initial edges of ρ_{r} and ρ̄_{r} are distinct and H_{r} is a geometric stratum.

We assume throughout this section that G = G_{r}. This causes no loss of generality in our proof of Proposition 6.13.

We begin by recalling some notation from [BH92].

Definition 6.14. Suppose that f : G → G , H_{r} and ρ_{r} are as in Proposition 6.13. We define the extended fold F : G → G′ of the illegal turn of ρ_{r} in H_{r} as follows. Decompose ρ_{r} = αβ where α and β are the maximal r-legal subpaths of ρ_{r}. Let E_{1} ⊂ H_{r} and E_{2} ⊂ H_{r} be the initial edges of ᾱ and β respectively. Lemma 6.11 implies that that one of the edge paths [f(E_{i})], i=1 or 2, is an initial subpath of the other. For concreteness, we assume that [f(E_{1})] is an initial subpath of [f(E_{2})]. There are three cases to consider.

In the first two cases, [f(E_{1})] is a proper initial subpath of [f(E_{2})] and we refer to these as proper extended folds. If the second edge of ᾱ is in H_{r}, then the extended fold is the fold of all of E_{1} with a proper initial segment of E_{2}. If the second edge of ᾱ is in G_{r−1}, let b be the maximal subpath of G_{r−1} that follows E_{1} in ᾱ. We claim that [f(E_{1}b)] is a proper initial segment of [f(E_{2})]; the extended fold in this case is then the fold of all of E_{1}b with a proper initial segment of E_{2}.

Suppose that our claim fails. If [f(E)f(b)] = [f(E_{2})], then a terminal segment of [f(E_{2})] would be in G_{r−1} in contradiction to the fact that f : G → G is a relative train track map . The remaining possibility is that the maximal initial segment of [f(E)f(b)] that agrees with an initial segment of [f(E_{2})] is proper in [f(E)f(b)]. Since [f(ρ_{r})] = ρ_{r}, the first edge e in [f(E)f(b)] that is not in this maximal initial segment equals either E_{1} or E_{2}. But both E_{1} and E_{2} are in H_{r} so e can not be in [f(b)]. We have now verified the claim.

In the third case [f(E_{1})] = [f(E_{2})] and the extended fold is the fold of E_{1} with E_{2}; we refer to this as an improper fold.

For proper extended folds, we may think of G\E_{2} as a subcomplex of both G and G′. Thus G is obtained from G\E_{2} by adding E_{2} and G′ is formed from G \ E_{2} by adding an edge E′_{2} with terminal endpoint equal to the terminal endpoint of E_{2} and initial endpoint equal to the terminal endpoint of b. With this notation, F |(G \ E_{2}) is the identity and F (E_{2}) = E_{1}bE′_{2}, where we allow the possibility that b is trivial. There is an induced map g : G′ → G satisfying gF = f. Since f is a relative train track map, [g(E′)] does not cross the turn (Ē_{1}, E_{2}) for any edge E′ of G′. Thus f′ = F g : G′ → G′ is a topological representative. We say that f′ : G′ → G′ is obtained from f : G → G by folding ρ_{r}. A proof that f′ : G′ → G′ is a relative train track map is contained in the proof of Theorem 5.15 of [BH92]. Define ρ′_{r} = α′β′ = [F (ρ_{r})] ⊂ G′ where α′ and β′ are the images in G′ of the subpaths of α and β that are not involved in the extended fold. An argument very similar to the one in Lemma 6.11 shows that f′ : G′ → G′ is F-Nielsen minimizing and that ρ′_{r} is an indivisible Nielsen path. The details are left to the reader. Define H′_{r} = (H_{r} \ E_{2}) ∪ E′_{2}.

In the improper case, F g : G′ → G′ is a topological representative but need not be a relative train track map. If it is not, then we restore the relative train track property by collapsing inessential connecting paths and by performing core subdivisions in G_{r−1} as in the proof of Lemma 6.10. The resulting relative train track map is denoted by f′ : G′ → G′ (even though G′ may have been changed by the collapsing and subdivision) and is said to be obtained from f : G → G by folding ρ_{r}. As in the proof of Lemma 6.10, f′ : G′ → G′ is F-Nielsen minimizing. Define H′_{r} = F (H_{r}) and note that H′_{r} has one fewer edge than H_{r}.

Let v_{1} be the initial vertex of ρ_{r}. If v_{1} ∉ G_{r−1}, then each time ρ_{r} passes through v_{1} it crosses two edges of H_{r}. The total number of times that ρ_{r} crosses the H_{r}-edges in Lk(G, v) is even. Since ρ_{r} starts at v_{1}, it must also end at v_{1}. Thus the conclusions of Proposition 6.13 can be simplified, without loss, by removing the statement that the endpoints of ρ_{r} are equal. It now follows that while proving Proposition 6.13, there is no loss in replacing f : G → G by f′ : G′ → G′. Moreover, this process can be repeated by folding ρ′_{r} and so on. If at some point the fold at the indivisible Nielsen path is not proper, then the number of edges in the r-stratum is reduced by the folding process. Since the number of edges in the r-stratum never increases, improper folds occur only finitely many times. We may therefore assume that each extended fold that we encounter is proper.

We associate a surface S and a graph K to f : G → G and ρ_{r} as follows. We think of ρ_{r} as a map with domain I × {0} ⊂ I × [0, 1] and subdivide I × {0} into subintervals that map either to individual edges of H_{r} or into maximal subpaths {b_{l}} of G_{r−1}. The edges in the subdivision of I × {0} are labelled according to the oriented images in G. For each edge E_{i} of H_{r}, identify the two edges of I ×{0} that are labelled E_{i}. The quotient of I ×{0} by this identification rule is a graph K. The quotient of all of I × [0, 1] by the identification rule is a surface S that deformation retracts to K. The edges of K inherit a labeling that defines a map h : K → G. For each edge E_{i} ⊂ H_{r} there is a unique edge in K labelled E_{i}; for notational simplicity, we refer to this edge as E_{i}. The other edges of K form a subgraph K_{0} consisting of edges that are mapped to G_{r−1}. Note that K_{0} ⊂ ∂S. Let V_{K} be the vertex set of K.

The next lemma states that a proper extended fold can be lifted to a homotopy equivalence between the graphs K and K′ associated to the indivisible Nielsen paths ρ_{r} and ρ′_{r} respectively.

Lemma 6.15. Assume that f : G → G, H_{r} and ρ_{r} are is in Proposition 6.13, that F : G → G′ is the extended fold of ρ_{r} and that f′ : G′ → G′ is obtained from f : G → G by folding ρ_{r}. If the extended fold is proper and if K and K′ are the graphs associated to ρ_{r} and ρ′_{r} respectively, then there is a homotopy equivalence F_{K} : K → K′ such that : (i) h′F_{K} = F h; (ii) F_{K} induces a bijection between the vertices of K and the vertices of K′; and F_{K}|K_{0} : K_{0} → K′_{0} is a homeomorphism.

Proof of Lemma 6.15 The extended fold F : G → G′ can be described as follows. E_{2} is subdivided into two pieces if b is trivial and three pieces if b is non-trivial. The first piece is labeled E_{1} and then identified with E_{1} ⊂ H_{r}; the middle piece, if it exists is labeled b and then identified with b ⊂ G_{r}; and the last piece is labeled E′_{2} and is the new edge of H′_{r}. To define ρ′_{r}, subdivide and relabel both copies of E_{2} in ρ_{r}. Remove E_{1} and b (if it is non-trivial) from α to form α′ and remove the first and middle segment (if it exists) of the subdivided E_{2} that is the first edge of β to form β′; ρ′_{r} = α′β′. The key point is that the second copy of E_{2} in ρ_{r} contributes a copy to ρ′_{r}, of the edges that are removed from α to form α′. The losses and gains exactly balance so that ρ′_{r} crosses every H′_{r} edge exactly twice and there is a one to one correspondence between the edges of K and the edges of K′; the induced correspondence preserves labels with the single exception that E_{2} corresponds to E′_{2}.

We now consider the link structures of K and K′. We think of ρ_{r} = e_{1} · · · · · e_{m} as a concatenation of subpaths where each e_{j} is labelled by either an edge E_{i} ⊂ H_{r} or a maximal subpath b_{l} ⊂ H_{r}. Thus each e_{j} is identified with an edge of K. The link structure is generated by ē_{j} ∼ e_{j+1} for 1 ≤ j ≤ m − 1. Let ∼′ be the analogous equivalence relation on oriented edges in K′.

If b is trivial, let A = E_{1}; if b is not trivial, let A = b_{K}, the edge of K that corresponds to b. Let E_{3} be the edge that follows A in ᾱ. The generating relations for ∼′ are obtained from the generating relations for ∼ as follows. Erase E_{1} ∼ E_{2} and add E_{3} ∼′ E′_{2}. If A = b_{K} or if the second occurrence of E_{1} in ρ_{r} is not followed by the second occurrence of E_{3} in ρ_{r}, then erase Ā ∼ E_{3}. (This accounts for the changes caused by the shortening of α and β to α′ and β′.) If ρ_{r} does not begin with E_{2} or end with Ē_{2}, then ρ_{r} passes through a turn (X, E_{2}) with X ≠ E_{1}. Erase X ∼ E_{2}, add X ∼′ E_{1} and add Ā ∼′ E′_{2}. (This accounts for the subdivision of E_{2} into the edge path AE′_{2} or E_{1}AE′_{2}.) Finally, change ∼ to ∼′ in the remaining generating relations. The combinatorial types of K and K′ differ in at most two links. The initial endpoint of E_{2} is moved from the vertex containing X and E_{1} and is added to the vertex containing E_{3} and Ā. (These vertices need not be distinct.)

We may think of K \ E_{2} as a subgraph of both K and K′; thus K is formed by adding E_{2} and K′ is formed by adding E′_{2}. The maps h and h′ agree on K \ E_{2}; h(E_{2}) = E_{2} and h′(E′_{2}) = E′_{2}. Define F_{K} to be the identity on K \ E_{2} and F_{K}(E_{2}) = E_{1}b_{K}E′_{2} where we allow the possibility that b is trivial. The desired properties of F_{K} follow immediately.

The next step in the proof of Proposition 6.13 is to show that f : G → G can be lifted to K.

Lemma 6.16. There is a homotopy equivalence f_{K} : K → K such that: (i) hf_{K} ≃ fh rel V_{K}; (ii) f_{K} permutes the elements of V_{K}; and (iii) f|K_{0} is a homeomorphism.

Proof of Lemma 6.16 For any extended fold F : G → G′, we may think of G_{r−1} as a subgraph of both G and G′ and with respect to this notation, F |G_{r−1} = identity.

The main step in the proof is to show that there is a factorization f = θf_{r−1}f_{r} where : (i) f_{r} : G → G^{1} is a composition of proper extended folds; (ii) f_{r−1} : G^{1} → G^{2} is a composition of folds involving edges in G_{r−1}; and (iii) θ : G^{2} → G is a homeomorphism. We set notation as follows: ρ_{r} = αβ; E_{1} and E_{2} are the initial edges of ᾱ and β respectively; F : G → G′ is the extended fold of ρ_{r}; g′ : G′ → G is the induced map satisfying g′F = f; f′ : G′ → G′ is the induced relative train track map ; ρ′_{r} = α′β′ ⊂ G′_{r} is the indivisible Nielsen path determined by ρ_{r} ⊂ G_{r}; and E′_{1} and E′_{2} are the initial edges of ᾱ′ and β′ respectively.

Sublemma 6.17. If [g′(E′_{1})] and [g′(E′_{2})] have a common initial segment, then the maximal g′-fold of E′_{1} and E′_{2} is full.

Proof of Sublemma 6.17 Assume the sublemma fails. Let F′ : G′ → G′′ be the maximal g′-fold of E′_{1} and E′_{2} and let g′′ : G′′ → G be the induced map satisfying g′′F′ = g′. Since the fold is not full, H′′_{r} = F′(H′_{r}) has one more edge than do H′_{r} and H_{r}.

Since F′ is maximal, g′′ can not be folded at the newly created vertex. Since (E′_{1}, E′_{2}) is the only illegal turn for g′ that involves an edge in H′_{r}, the illegal turns for g′′ have both edges in G′′_{r−1}. If γ′′ ⊂ G′′_{r−1} is any non-trivial path with endpoints in H′′_{r} ∩ G′′_{r−1} = H′_{r} ∩ G′_{r−1} = H_{r} ∩ G_{r−1}, then there exists a non-trivial path γ ⊂ G_{r} with endpoints equal to those of γ′′ such that [F′F (γ)] = γ′′; in particular, [g′′(γ′′)] = [f(γ)] is non-trivial. It follows that folding edges in G′′_{r−1} according to g′′|G′′_{r−1} will not cause previously distinct vertices in H′′_{r} ∩ G′′_{r−1} to become identified. Thus no new illegal turns involving the edges of H′′_{r} are created during such folds. Consecutively fold edges in G′′_{r−1} according to g′′|G′′_{r−1} until no more folds are possible; call this composition of folds f_{r−1} : G′′ → G^{∗}. There is an induced map θ : G^{∗} → G satisfying f = θf_{r−1}f_{r}. Since θ does not determine any folds in G′′, it is a homeomorphism [Sta83]. Now θ(f_{r−1}(G′′_{r−1})) = f(G_{r−1}) = G_{r−1} so θ(f_{r−1}(H′′_{r})) = H_{r}. But θf_{r−1}|H′′_{r}induces a bijection on edges so this contradicts the fact that H′′_{r} and H_{r} do not have the same number of edges.

If (ᾱ′, β′) is legal for g′, then define f_{r} = F and construct f_{r−1} and θ exactly as in the sublemma. If (ᾱ′, β′) is illegal for g′, then let F′ : G′ → G′′ be the extended fold of ρ′_{r} for g′ and let g′′ : G′′ → G be the induced map satisfying g′′F′ = g′. If the illegal turn of ρ′′_{r} in H′′_{r} is legal for g, then define f_{r} = F′F and construct f_{r−1} and θ exactly as in the sublemma. If the illegal turn of ρ′′_{r} in H′′_{r} is illegal for g′′, then repeat the argument of the sublemma to conclude that that the extended fold of ρ′′_{r} is a factor of g′′. Continue in this manner until we arrive at the desired factorization.

Lemma 6.15 implies that there exists F_{1} : K → K^{1} such that h_{1}F_{1} = f_{r}h. There is a relative train track map f^{1} : G^{1} → G^{1} that is obtained by

iteratively folding indivisible Nielsen paths, starting with ρ_{r} and continuing through the extended folds that make up f_{r}. Let ρ_{r}^{1} = [f_{r}(ρ_{r})] ⊂ G^{1} be the corresponding indivisible Nielsen path and let {b_{l}^{1}} be the maximal subpaths of ρ_{r}^{1} in G_{r−1}^{1}. Since f^{1} is a relative train track map , [θf_{r−1}(b_{l}^{1})] are nontrivial paths in G_{r−1}. By construction θf_{r−1}|H_{r}^{1} is injective and [θf_{r−1}(ρ_{r}^{1})] = [f(ρ_{r})] = ρ_{r}. It follows that ρ_{r} is obtained from ρ_{r}^{1} by replacing each b_{l}^{1} with [θf_{r−1}(b_{l}^{1})] and relabeling an edge E^{1} of H_{r}^{1} by the edge [θf_{r−1}(E^{1})]; thus K is obtained from K^{1} by changing the edge labels b_{l}^{1} to [θf_{r−1}(b_{l}^{1})] and the edge labels E^{1} to [θf_{r−1}(E^{1})]. This induces a homeomorphism F_{2} : K^{1} → K such that hF_{2} ≃ θf_{r−1}h^{1} rel vertices.

Define f_{K} = F_{2}F_{1}. Then hf_{K} = hF_{2}F_{1} ≃ θf_{r−1}h^{1}F_{1} = θf_{r−1}f_{r}h = fh rel V_{K}. Since F_{1} induces a bijection of vertices and F_{2} is a homeomorphism, f_{K} permutes the vertices of K. Finally, since F_{1}|K_{0} and F_{2} are homeomorphisms, f_{K}|K_{0} is a homeomorphism.

The next lemma exploits the fact that f : G → G is reduced. If v̂ is vertex of K, we denote its link, thought of as the oriented edges with initial vertex v̂, by Lk(K, v̂). The link of v in G is denoted Lk(G, v).

Lemma 6.18. 1. If h(Lk(K, v̂)) ⊂ H_{r}, then h(Lk(K, v̂)) = Lk(G, h(v̂)).

2. The endpoints of ρ_{r} are equal and are not contained in G_{r−1}; the initial edge of ρ_{r} is distinct from the initial edge of ρ̄_{r}.

3. For each component C of K_{0}, [h(C)] is a non-trivial circuit in G_{r−1}.

Proof of Lemma 6.18 Since f_{K}|K_{0} is a homeomorphism and f_{K} permutes the vertices of K, we may assume, after replacing f by an iterate if necessary, that f_{K} fixes every vertex of K and restricts to the identity on K_{0}.

Suppose that D = h(Lk(K, v̂)) ⊂ H_{r} is not all of Lk(G, h(v̂)). Define a new graph G′ from G as follows. Replace v = h(v̂) by a pair of vertices v′ and w′; reattach the edges of D to v′ and the remaining edges in Lk(G, v) to w′; add an edge X connecting v′ and w′. Define p : G′ → G_{r} to be the homotopy equivalence that collapses X to v. Let G′_{r} = G′\X and G′_{r−1} = p^{−1}(G_{r−1})\X. Note that p|G′_{r−1} : G′_{r−1} → G_{r−1} is a homeomorphism so we may think of G_{r−1} as a subgraph of both G and G′. With this notation p|G_{r−1} = identity. By construction, there is a map h^{∗} : K → G′_{r} satisfying ph^{∗} = h. If E is an edge of H_{r}, and so also an edge of K, then for all k > 0, [h^{∗}f_{K}^{k}(E)] ⊂ G′_{r} is a lift of [f^{k}(E)]. Thus G′_{r} carries the lamination Λ^{+} ∈ L(O) associated to H_{r} and Lemma 4.4 implies that F(G′_{r}) ≠ F(G_{r−1}).

We next show that F(G′_{r}) is O- invariant by defining a topological representation f′ : G′ → G′ such that pf′ ≃ fp rel vertices and such that f′ restricts to a self map of G′_{r}. On the edges of G′_{r−1} = G_{r−1}, f′ = f. If E′ is an edge of H′_{r} = G′_{r} \ G′_{r−1}, then p(E′) is an edge of H_{r} and so h^{−1}p(E′) is a well-defined edge of K; define f′(E′) = h^{∗}f_{K}h^{−1}p(E′). Finally define f′(X) = X. Lemma 6.16 implies that pf′ ≃ fp rel vertices on the edges of H′_{r} and hence that pf′ ≃ fp rel vertices on all edges. Since f_{K} fixes all vertices, so does f′. It follows that f′ is continuous. By definition, f′ restricts to a self map of G′_{r}.

To complete the proof of (1) we will show that F(G′_{r}) ≠ F(G′) = F(G) in contradiction to the assumption that f : G → G is reduced and our previous observation that F(G′_{r}) ≠ F(G_{r−1}). If F(G′_{r}) = F(G′), then G′_{r} must have two components, one of which Y′ is contractible. Since G′_{r} carries Λ^{+}, Y′ ⊂ G′_{r−1}. But then Y′ is a contractible component of G_{r−1} that contains the vertex v and is hence mapped to itself by f. This contradicts the assumption that contractible components of G_{r−1} are contained in zero strata.

We now turn to the proof of (2). Let v_{1} be the initial vertex of ρ_{r} = αβ. If v_{1} ∉ G_{r−1}, then each time ρ_{r} passes through v_{1} it crosses two edges of H_{r}. The total number of times that ρ_{r} crosses the H_{r}-edges in Lk(G, v) is even. Since ρ_{r} starts at v_{1}, it must also end at v_{1}. Suppose that the initial edge E of ρ_{r} equals the initial edge of ρ̄_{r}. For large k, there are initial subpaths α_{0} and β_{0} of E such that α = [f^{k}(α_{0})] and β̄ = [f^{k}(β_{0})]. We may assume without loss that α_{0} ⊂ β_{0} and hence that α is an initial subpath of β̄. Since the initial edge of β is in H_{r}, the difference between the number of edges in [f^{m}(α)] and [f^{m}(β)] grows without bound, in contradiction to the fact that ρ_{r} = [f^{m}(ρ_{r})] = [f^{m}(α)f^{m}(β)] for all m ≥ 0.

To complete the proof of (2), we assume that v_{1} ∈ G_{r−1} and argue to a contradiction. Let D_{1} be the initial edge of ρ_{r} and suppose that the lift of D_{1} to K has initial endpoint v̂_{1}. Part (1) implies that v̂_{1} is contained in a component C of K_{0}. Since C is completed to a circle in ∂S by ∂I × [0, 1] ∪ I × {1}, C is an arc. For notational concreteness, we give the argument when C has two edges: A with endpoints v̂_{1} and v̂_{2} and label b_{1}; and B with endpoints v̂_{2} and v̂_{3} and label b_{2}. We also assume that v_{1} = v_{3} ≠ v_{2} where v_{i} = h(v̂_{i}). The arguments in other cases require only straightforward modifications.

The subset of Lk(K, v̂_{i}) that projects to H_{r} is denoted D̂_{⟩}; its image in Lk(G, v_{i}) is denoted D_{i}. Note that Lk(K, v̂_{1}) = D̂_{1} ∪ A, Lk(K, v̂_{2}) = D̂_{2} ∪Ā∪B and Lk(K, v̂_{3}) = D̂_{∋} ∪B̄. Define G′ to be the graph obtained from G_{r} as follows. Replace v_{1} = v_{3} by three vertices v′_{1}, v′_{3} and w′_{1}; replace v_{2} by two vertices v′_{2} and w′_{2}. The edges of D_{i} are reattached to v′_{i}. The remaining edges in the link of v_{1} [respectively v_{2}] are reattached to w′_{1} [respectively w′_{2}]. Add edges X connecting v′_{1} to w′_{1}, A′ connecting v′_{1} to v′_{2} and B′ connecting v′_{2} to v′_{3}. Define p : G′ → G to be the homotopy equivalence that collapses X to v_{1}, sends A′ to b_{1} and sends B′ to b_{2}. As in the previous case, there is a map h^{∗} : K → G′ \ X satisfying ph^{∗} = h and there is an induced topological representation f′ : G′ → G′ : that satisfies pf′ = fp; that restricts to the identity on X ∪ A′ ∪ B′; and that maps G′ \ X into itself. Define G′_{r−1} = p^{−1}(G_{r−1}) \ (X ∪ A′ ∪ B′) and G′_{r} = G′ \ X. The proof now concludes as in the previous case.

For part (3), we may assume by parts (1) and (2) that C is a loop. We will give the argument when the boundary component C consists of three edges: A with endpoints v̂_{1} and v̂_{2} and label b_{1}; B with endpoints v̂_{2} and v̂_{3} and label b_{2}; and C with endpoints v̂_{3} and v̂_{1} and label b_{3}. As in part (2) we assume that v_{1} = v_{3} ≠ v_{2}. Define G′ and p : G′ → G exactly as in part (2). If [h(C)] is trivial, then b_{3} ≃ b̄_{2}b̄_{1} rel endpoints and there exists h^{∗} : K → G′ such that ph^{∗} ≃ h rel vertices; one simply defines h^{∗}(A) = A′, h^{∗}(B) = B′ and h^{∗}(C) = B̄′Ā′. The proof now concludes as in the previous cases. Proof of Proposition 6.13 We have already defined S. Parts (1) and (2) of Lemma 6.18 imply that ∂I × {0, 1} ∪ I × {1} projects to a component ρ^{∗} of ∂S. The components of ∂S \ ρ^{∗} = K_{0} are denoted γ_{1}^{∗}, …, γ_{m}^{∗} . Part (3) of Lemma 6.18 implies that each γ_{i} = [h(γ_{i}^{∗})] is a non-trivial circuit. Since hf_{K} ≃ fh and f_{K} permutes the γ_{i}^{∗}’s, f_{#} permutes the γ_{i}’s and the induced permutations of {1, …, m} agree.

Define Ĝ = G_{r−1} ∪_{h|K_{0}} K. The identity map on G_{r−1} and h fit together to give a continuous map ĥ : Ĝ → G. Part (1) of Lemma 6.18 implies that ĥ induces a bijection between the vertices of K\K_{0} and the vertices of G\G_{r−1}. Thus ĥ induces a bijection between the vertices of Ĝ and the vertices of G. Since ĥ also induces a bijection on edges, ĥ is a homeomorphism.

Let A be the union of m annuli A_{i}, …, A_{m}. Define Y to be the space obtained from G_{r−1} ∪ A ∪ S by attaching one end of A_{i} to γ_{i} and the other end to γ_{i}^{∗}. By construction, S = M(ρ_{r}^{K}) is the mapping cylinder of the quotient map ρ_{r}^{K} : I × {0} → K. Since ĥ : Ĝ → G is a homeomorphism, Y is homeomorphic to the mapping cylinder M(ρ_{r}), where ρ_{r} is thought of as a map of the interval into G. The natural deformation retraction of M(ρ_{r}) to G defines Φ : (Y, G_{r−1}) → (G, G_{r−1}). It remains to show that if r : S → K is the deformation retraction given by collapsing mapping cylinder lines, then the homotopy equivalence f_{K}r : S → S is homotopic to a pseudo-Anosov homeomorphism ϕ.

Since r|K_{0} = identity and f_{K}|K_{0} is a homeomorphism, f_{K}r permutes the components of K_{0} ⊂ ∂S. The component ρ^{∗} is freely homotopic in S to the circuit determined by ρ_{r}^{K} and so is also fixed by (f^{K}r)_{#}. It follows [?] that f^{K}r is homotopic to a homeomorphism ϕ. To prove that the mapping class determined by ϕ is pseudo-Anosov, it suffices to show that the only periodic conjugacy classes are the peripheral ones.

A non-trivial circuit σ_{K} ⊂ K determines a non-trivial circuit σ̂ ⊂ Ĝ and hence a non-trivial circuit σ ⊂ G. If σ_{K} is periodic under the action of f_{K} and σ_{K} ⊄ K_{0}, then σ is periodic under the action of f and σ ⊄ G_{r−1}. Lemmas 5.8 and 6.12 imply that σ splits into subpaths that are either entirely contained in G_{r−1} or equal to ρ_{r} or ρ̄_{r}. Part (2) of Lemma 6.18 implies that σ is a multiple of ρ_{r} or ρ̄_{r}.

6.4 Sliding

We assume throughout this subsection that f : G → G is a relative train track map and that each non-exponentially growing stratum H_{i} is a single edge E_{i} satisfying f(E_{i}) = E_{i}u_{i} for some path u_{i} ⊂ G_{i−1}. The goal is to modify f : G → G so that f(E_{i}) = E_{i} · u_{i}.

For any path α ⊂ G_{i−1} with initial endpoint equal to the terminal endpoint of E_{i} and with terminal endpoint at a vertex of G_{i−1}, define a new graph G′ by replacing E_{i} with an edge E′_{i} that has the same initial endpoint as E_{i} and the same terminal endpoint as α. Every edge of G \ E_{i} is naturally identified with an edge of G′ \ E′_{i}; we use the same name for the edge in both graphs. Similarly, a path β ⊂ G that does not cross E_{i} is identified with a path, also called β, in G′.

There are homotopy equivalences p : G → G′ and p′ : G′ → G that equal the ‘identity’ on the common edges of G and G′ and that satisfy p(E_{i}) = E′_{i}ᾱ and p′(E′_{i}) = E_{i}α respectively. Define f′ : G′ → G′ by tightening pfp′ : G′ → G′; i.e. f′ ≃ pfp′ rel vertices and f restricts to an immersion on each edge of G′. We say that f′ : G′ → G′ is obtained from f : G → G by sliding E_{i} along α. For each G_{j} define G′_{j} = p(G_{j}).

The basic properties of sliding are listed in the following lemma.

Lemma 6.19. Suppose that f′ : G′ → G′ is obtained from f : G → G by sliding E_{i} along α. Then f′(E′_{i}) = E′_{i}u′_{i} where u′_{i} = [ᾱuf(α)] ⊂ G′_{i−1}. Moreover, H′_{j} is exponentially growing [respectively non-exponentially growing] if and only if H_{j} is exponentially growing[respectively non-exponentially growing]. If f : G → G is F-Nielsen minimizing, then so is f′ : G′ → G′ .

Proof of Lemma 6.19 We have f′(E′_{i}) = [pfp′(E′_{i})] = [pf(E_{i}α)] = [p(E_{i}uf(α))] = [E′_{i}ᾱuf(α)] = E′_{i}[ᾱuf(α)]. Sliding has no effect on any F(G_{j}) so f′ : G′ → G′ satisfies conditions (1) and (2) in the definition of F-Nielsen minimizing if f : G → G does.

Since f|G_{i−1} agrees with f′|G′_{i−1}, we may restrict our attention to strata H_{j} with j > i. If H_{j} is a zero stratum and E_{0} is an edge in H_{j}, then f(E_{0}) ⊂ G_{j−1}. Thus f′(E_{0}) = [pf(E_{0})] ⊂ G′_{j−1} and H′_{j} is also a zero stratum. If H_{j} is non-exponentially growing, then H_{j} is a single edge E_{j} and there is a path u_{j} ⊂ G_{j−1} such that f(E_{j}) = E_{j}u_{j}. Thus f′(E_{j}) = [pf(E_{j})] = [p(E_{j}u_{j})] = E_{j}[p(u_{j})] where [p(u_{j})] ⊂ G′_{j−1}. Thus H′_{j} is non-exponentially growing.

Suppose now that H_{r} is exponentially growing and that E is an edge of H_{r}. For any non-trivial paths β ⊂ G and γ′ ⊂ G′ with endpoints at vertices, [p′p(β)] = β and [pp′(γ′)] = γ′. In particular, [p(β)] and [p′(γ′)] are non-trivial. The train track property implies that f(E) = a_{1}b_{1}a_{2} … b_{l}a_{l+1} where a_{i} ⊂ H_{r} and b_{i} ⊂ G_{r−1} are non-trivial paths. Thus f′(E) = [pf(E)] = [p(a_{1}b_{1}a_{2} … b_{l}a_{l+1})] = a_{1}[p(b_{1})]a_{2} … [p(b_{l})]a_{l+1}. This implies that H_{r} is exponentially growing and that the transition submatrices, M_{r} and M′_{r}, and hence the Perron Frobenius eigenvalues μ_{r} and μ′_{r}, are equal. If β′ ⊂ G′_{r−1} is a non-trivial path with endpoints in H′_{r} ∩ G′_{r−1}, then [p′(β′)] is a non-trivial path with endpoints in H_{r} ∩ G_{r−1} and hence [fp′(β′)] is non-trivial. Thus [f′(β′)] = [pfp′(β′)] is non-trivial. We have now verified that f′ : G′ → G′ is a relative train track map.

If σ′ ⊂ G′_{r} satisfies [(f′)^{k}(σ′)] = σ′, then [p′(σ′)] = [p′(pfp′)^{k}(σ′)] = [(f)^{k}(p′σ′)]. Similarly, if σ ⊂ G_{r} and [f^{k}(σ)] = σ, then [p(σ)] = [pf^{k}(σ)] = [(f′)^{k}(pσ)]. In other words, p induces a period preserving bijection between indivisible periodic Nielsen paths in G_{r} and indivisible periodic Nielsen paths in G′_{r}. Thus f′ : G′ → G′ is F-Nielsen minimized if f : G → G is.

In order to find good paths along which to slide, we consider a restricted lift of f defined as follows. Choose a lift Ẽ_{i} in the universal cover Γ of G. Let f̃: Γ → Γ be the lift of f : G → G that fixes the initial endpoint of Ẽ_{i}, let ũ_{i} be the lift of u_{i} satisfying f̃(Ẽ_{i}) = Ẽ_{i}ũ_{i} and let Γ_{i−1} ⊂ Γ be the component of the full pre- image of G_{i−1} that contains ũ_{i}. Since f̃(Ẽ_{i}) = Ẽ_{i}ũ_{i}, Γ_{i−1} is f̃-invariant. Denote f̃|Γ_{i−1} by h : Γ_{i−1} → Γ_{i−1} and note that if q̃ is the initial vertex of ũ_{i}, then h(q̃) is its terminal vertex.

The sliding operation can be lifted to Γ by replacing each lift of E_{i} with a lift of E′_{i}. Call the resulting tree Γ′. Let f̃′ : Γ′ → Γ′ be the lift of f′ : G′ → G′ that fixes the initial endpoint of the lift Ẽ′_{i} that corresponds to Ẽ_{i}. (Ẽ_{i} and Ẽ′_{i} have a ‘common’ initial endpoint.) Lemma 6.19 implies that Γ′_{i−1} = Γ_{i−1} and that f̃′|Γ′_{i−1} = f̃|Γ_{i−1}. In this sense, h : Γ_{i−1} → Γ_{i−1} is unchanged by the sliding operation.

For any x̃, ỹ ∈ Γ_{i−1}, denote the path connecting x̃ to ỹ by [x̃, ỹ] and its image in G_{i−1} by pr([x̃, ỹ]). Paths in G_{i−1} that have their initial endpoint at q = pr(q̃) and their terminal endpoint at a vertex v are in one to one correspondence with paths in Γ_{i−1} of the form [q̃, ṽ] where pr(ṽ) = v and hence are in one to one correspondence with the set of vertices ṽ of Γ_{i−1}. Thus we may speak of sliding along the path determined by the vertex ṽ.

Lemma 6.20. If f′ : G′ → G′ is obtained from f : G → G by sliding along the path corresponding to a vertex ṽ, then f′(E′_{i}) = E′_{i}u′_{i} where u′_{i} = pr([ṽ, h(ṽ)]).

Proof of Lemma 6.20 This follows immediately from Lemma 6.19 and the definition of h.

The following proposition is the main result of this subsection. Conditions (1) and (2) record the fact that we have taken u to be as simple as h will allow. Condition (3) is a strengthening of the assertion that f′(E′_{i}) = E′_{i} · u′_{i} and is used in Lemma 6.22.

Proposition 6.21. After subdividing at a periodic orbit of f : G → G if necessary, there is a vertex ṽ of Γ that projects to a periodic point of f so that if f′ : G′ → G′ is obtained from f : G → G by sliding along the path determined by ṽ, then f′(E′_{i}) = E′_{i} · u′_{i} where:

1. u′_{i} is trivial if and only if h has a fixed point.

2. If u′_{i} is non-trivial, then u′_{i} is periodic under the action of f_{#} if and only if h commutes with a covering translation T of Γ_{i−1}; in this case, the infinite ray R̃′ = ũ′_{i}[h(ũ′_{i})][h^{2}(ũ′_{i})] … is contained in the axis of T.

3. If u′_{i} is not trivial, then E′_{i} · w′_{i} is a splitting for every initial segment w′_{i} of u′_{i}.

Proof of Proposition 6.21 If Fix(h) ≠ ∅, then, after subdividing if necessary, we may choose ṽ ∈ Fix(h). Lemma 6.20 implies that u′ is the trivial path. We assume now that h is fixed point free. Lemma 6.20 implies that u′ can not be trivial for any choice of ṽ. This verifies condition (1).

Let X̃ = {x̃ : {x̃, h(x̃), h^{2}(x̃), … } is an ordered subset of an infinite path in Γ_{i−1}}. Note that h(X̃) ⊂ X̃ and that if x̃ ∈ X̃ and [x̃, h(x̃)] = [x̃, ỹ] · [ỹ, h(x̃)], then ỹ ∈ X̃. The first step in the proof is to show that X̃ ≠ ∅.

We say that the initial edge of [ṽ, h(ṽ)] is preferred by the vertex ṽ ∈ Γ_{i−1}. Since h is fixed point free, each edge E is preferred by exactly one of its endpoints. Otherwise h(E) would cross E and create a fixed point in E. For each ṽ ∈ Γ_{i−1}, let L(ṽ) = E^{0} ·E^{1} ·. . . be the infinite path defined by choosing E^{0} to be the preferred edge for ṽ, and by inductively choosing E^{i+1} to be the preferred edge for the terminal endpoint of E^{i}.

Given ṽ, w̃ ∈ Γ_{i−1}, denote [ṽ, w̃] by γ̃. An easy induction argument on edge length shows that either the initial edge of γ̃ is preferred by the initial vertex of γ̃ or the terminal edge of γ̃ is preferred by the terminal vertex of γ̃ or both . In other words, either the initial edge of γ̃ is the initial edge of L(ṽ) or the initial edge of the inverse of γ̃ is the initial edge of L(w̃) or both. It follows that L(ṽ) and L(w̃) have a common infinite end. Define I(ṽ, w̃) to be the initial vertex of L(ṽ) ∩ L(w̃); thus L(I(ṽ, w̃)) = L(ṽ) ∩ L(w̃).

Choose a vertex ṽ_{0} and inductively define ṽ_{i+1} = I(ṽ_{i}, h(ṽ_{i})). Then L(ṽ_{0}) = [ṽ_{0}, ṽ_{1}][ṽ_{1}, ṽ_{2}][ṽ_{2}, ṽ_{3}] … and [h([ṽ_{i}, ṽ_{i+1}])] = [h(ṽ_{i}), h(ṽ_{i+1})] contains [ṽ_{i+1}, ṽ_{i+2}]. Define Ỹ_{m} = {ỹ ∈ [ṽ_{0}, ṽ_{1}] : h^{i}(ỹ) ∈ [ṽ_{i}, ṽ_{i+1}] ∀ 0 ≤ i ≤ m}. A straightforward induction argument shows that h(Ỹ_{m}) = [ṽ_{m}, ṽ_{m+1}] and in particular that Ỹ_{m} ≠ ∅. The Ỹ_{m}’s are a nested sequence of closed sets so ∩Ỹ_{m} ≠ ∅. By construction, ∩Ỹ_{m} ⊂ X̃ so X̃ ≠ ∅.

The next step is to choose a vertex ṽ ∈ X̃. Let s be the smallest parameter value for which there exists x̃ ∈ X̃ satisfying pr[x̃, h(x̃)] ⊂ G_{s}. Choose such an x̃. If H_{s} is non-exponentially growing, then H_{s} is a single edge E_{s} and f(E_{s}) = E_{s}u_{s} for some path u_{s} ⊂ G_{s−1}. After replacing x̃ by some h^{k}(x̃) if necessary, we may assume that [x̃, h(x̃)] contains at least one entire edge ẽ whose projected image e equals either E_{s} or Ē_{s}. If e = E_{s} let ṽ be the initial edge of ẽ; if e = Ē_{s}, let ṽ be the terminal edge of ẽ. Lemma 5.2 implies that [x̃, h(x̃)] can be split at ṽ and hence that ṽ ∈ X̃.

If H_{s} is exponentially growing, then after replacing x̃ by some h^{k}(x̃) if necessary, we may assume that each [h^{i}(x̃), h^{i+1}(x̃)] has the same number of illegal turns in H_{s}. Lemma 5.8 produces a splitting of [x̃, h(x̃)]. If one of the resulting pieces is a lift ρ̃ of some ρ ∈ P_{s}, let ṽ be its initial endpoint. Replacing x̃ by some h^{k}(x̃) if necessary, we may assume (Lemma 5.7) that v is f-periodic. After subdividing at the orbit of v, we may assume that ṽ ∈ X̃ is a vertex. If there are no ρ̃ pieces, then [x̃, h(x̃)] is s-legal. After replacing x̃ by some h^{k}(x̃) if necessary, we may assume that [x̃, h(x̃)] contains an entire edge of H_{s}. Let ṽ be an endpoint of such an edge. Lemma 5.3 implies that [x̃, h(x̃)] splits at ṽ and hence that ṽ ∈ X̃. Replacing ṽ by some h^{i}(ṽ), we may assume that v is a periodic point.

We assume from now on that ũ′_{i} = [ṽ, h(ṽ)], where ṽ is chosen as above, and that u′_{i} ⊂ G_{s} is its projected image. If [(f′)^{k}(u′_{i})] = u′_{i} for some k > 0, then the infinite ray R̃′ = ũ′_{i}[h(ũ′_{i})][h^{2}(ũ′_{i})] … is contained in the axis of the covering translation T : Γ_{i−1} → Γ_{i−1} that satisfies T (ũ′_{i}) = [h^{k}(ũ′_{i})]. Since h_{#} preserves the axis of T, h commutes with T.

Conversely, suppose that there is a covering translation T of Γ_{i−1} that commutes with h. Then T ([x̃, h(x̃)]) = [T x̃, h(T x̃)] for all x̃ and so L(T (ṽ)) = T (L(ṽ)). This implies that L(ṽ) and T (L(ṽ)) have a common infinite end and hence that L(ṽ) and the axis of T have a common infinite end. In particular, h^{l}(ṽ) is contained in the axis of T for all sufficiently large l. This implies that there is a uniform bound to the edge length of [h^{l}(ṽ), h^{l+1}(ṽ)], and hence that [(f′)^{l}(u′_{i})] takes only finitely many values. After replacing ṽ by some h^{l}(ṽ) if necessary, we may assume that u′_{i} is periodic under the action of f′_{#} and that R̃′ is contained in the axis of T. We have now verified (2).

Recall that R̃′ = ũ′_{i} ·[h(ũ′_{i})]·[h^{2}(ũ′_{i})] … is the infinite ray starting at ṽ and containing {h^{i}(ṽ) : i ≥ 0}. Let ũ′_{i} = σ̃_{1} · σ̃_{2} · · · · · σ̃_{n_{0}} be the splitting provided by Lemma 5.8 if H_{s} is non-exponentially growing and by Lemma 5.3 if H_{s} is exponentially growing. Then [h^{i}(ũ′_{i})] = [h^{i}(σ̃_{1})] · [h^{i}(σ̃_{2})] · · · · · [h^{i}(σ_{n_{0}})] and R̃′ has an infinite splitting R̃′ = σ̃_{1} · σ̃_{2} · . . . where σ̃_{in_{0}+j} = [h^{i}(σ̃_{j})].

To verify condition (3), we must show that [ṽ, h^{i}(ṽ)] is contained in [ṽ, h^{i}(ỹ)] for all ỹ ∈ ũ′_{i}. It suffices to show that h^{i}(ũ′_{i}) intersects [h^{i−1}(ũ′_{i})] trivially. We will prove the slightly stronger statement that h^{i}(σ̃_{j}), which tightens to σ̃_{in_{0}+j}, intersects σ̃_{in_{0}+j−1} trivially for 1 ≤ j ≤ n_{0} and all i ≥ 0.

Suppose at first that H_{s} is non-exponentially growing. If the initial edge of σ̃_{j} is a lift of E_{s}, then Lemma 5.2 implies that h^{i}(σ̃_{j}) is a lift of E_{s}, possibly followed by a sequence of edges in Γ_{i−1} and possibly terminating in a lift of Ē_{s}; if h^{i}(σ̃_{j}) does terminate in a lift of Ē_{s} then the sequence of edges in Γ_{i−1} tightens to a non-trivial path. The initial edge is disjoint from the rest of h^{i}(σ̃_{j}) and acts as a barrier to keep h^{i}(σ̃_{j}) from intersecting σ̃_{in_{0}+j−1}. If the initial edge of σ̃_{j} is not a lift of E_{s}, then the terminal end of σ̃_{in_{0}+j−1} is a lift of Ē_{s} and h^{i}(σ̃_{j}) is a sequence of edges in Γ_{i−1}, possibly terminating in a lift of Ē_{s}; if the last edge of h^{i}(σ̃_{j}) is a lift of Ē_{s}, then the sequence of edges in Γ_{i−1} tightens to a non-trivial path. The edges in Γ_{i−1} can not cross the terminal edge of σ̃_{in_{0}+j−1} and the terminating lift of Ē_{s}, if it exists, can not either because the path between it and σ̃_{in_{0}+j−1} is non-trivial.

Assume now that H_{s} is exponentially growing. If σ̃_{j} = ρ̃ for some ρ ∈ P_{s}, let ρ = αβ be the unique decomposition of ρ into s-legal subpaths. Lemma 3.1 implies that h^{i}(α̃) (and also h^{i}(β̃)) decomposes into a path that projects to H_{s}, followed by a sequence of edges that project to G_{s−1} and tighten to a non-trivial path, followed by a path that projects to H_{s} and so on. The terminal end of h^{i}(α̃) and the initial end of h^{i}(β̃) agree up to a point, but there is always an initial subpath of h^{i}(α̃) that is disjoint from the rest of h^{i}(σ̃_{j}). This prevents h^{i}(σ̃_{j}) from crossing back to σ̃_{in_{0}+j−1}.

If σ̃_{j} ≠ ρ̃, then σ̃_{j} is s-legal. If the initial edge of σ̃_{j} projects to H_{s}, then Lemma 3.1 implies that the initial edge of h^{i}(σ̃_{j}) is disjoint from the rest of h^{i}(σ̃_{j}) and prevents h^{i}(σ̃_{j}) from crossing back to σ̃_{in_{0}+j−1}. If the initial edge of σ̃_{j} does not project to H_{s}, then the terminal edge of σ_{in_{0}+j−1} projects to H_{s} and prevents h^{i}(σ̃_{j}) from crossing back to σ̃_{in_{0}+j−1} : edges that project to G_{s−1} can not cross this barrier and edges that project to H_{s} do not because Lemma 3.1 implies that they are part of [h^{i}(σ̃_{j})].

6.5 Splitting Basic Paths

Recall that if f : G → G is a relative train track map and H_{i} is a single edge E_{i}, then a path σ ⊂ G_{i} is basic if it is one of the following four types : γ, E_{i}γ, E_{i}γĒ_{i}, γĒ_{i}, where γ ⊂ G_{i−1}. The path γ can be analyzed by induction. The path γĒ_{i} is the inverse of the path E_{i}γ̄. In this subsection we consider further splittings of the basic paths Eγ and E_{i}γĒ_{i}.

Lemma 6.22. Assume that : f : G → G is a relative train track map; each exponentially growing stratum H_{i} satisfies conditions (eg-(i) - eg-(iii) of Theorem 6.4; each non-exponentially growing stratum H_{i} satisfies the conclusions of Proposition 6.21; and that if H_{i} is an exponentially growing stratum then every indivisible periodic Nielsen path ρ ⊂ G_{i} that intersects H_{i} non-trivially has period one. Then every periodic Nielsen path has period one. If H_{i} is a non-exponentially growing stratum with edge E_{i} and suffix u_{i} and if γ ⊂ G_{i−1} then the following are satisfied :

1. If E_{i}γ [respectively E_{i}γĒ_{i}] can be split at a point in the interior of E_{i}, then [f^{m}(E_{i}γ)] = E_{i} · γ_{1} [respectively [f^{m}(E_{i}γĒ_{i})] = E_{i} · γ_{1}Ē_{i} for some m ≥ 0 and γ_{1} ⊂ G_{i−1}.

2. If E_{i}γ has no non-trivial splittings, then [f^{m}(E_{i}γ)] is exceptional for some m ≥ 0.

3. If E_{i}γĒ_{i} has no non-trivial splittings, then E_{i}γĒ_{i} is exceptional.

Proof of Lemma 6.22 The proof is by induction on f|G_{j}. If G_{1} = H_{1} is exponentially growing, then conditions (1) - (3) for f|G_{1} are vacuous and the condition on periodic Nielsen paths follows directly from our hypotheses. If G_{1} = H_{1} is non-exponentially growing, then u_{1} is the trivial path; condition (1) is trivial, conditions (2) - (3) are vacuous and the the condition on periodic Nielsen paths follows from the fact that f|G_{1} is the identity.

We assume now that the lemma holds for f|G_{i−1} and prove it for f|G_{i}. If H_{i} is exponentially growing, then the the condition on periodic Nielsen paths follows from Lemma 5.8 and the inductive hypothesis; conditions (1) - (3) are vacuous. We may therefore assume that H_{i} is a single non-exponentially growing edge E_{i}. Let s be the smallest parameter value for which u_{i} ⊂ G_{s}.

If E_{i}γ can be split at a point in the interior of E_{i}, then some [f^{m}(E_{i}γ)] = E_{i}w · γ′ where w is an initial segment of u_{i}. Part (3) of Proposition 6.21 implies that E_{i}w = E_{i} · w and hence that [f^{m}(E_{i}γ)] = E_{i} · wγ′. A similar argument works for E_{i}γĒ_{i}. This proves (1).

In order to treat (2) and (3) simultaneously, let σ = E_{i}γ or E_{i}γĒ_{i}. Assume that u_{i} is non- trivial and that σ has only trivial splittings. If σ = E_{i}γ, then, after replacing σ by some [f^{l}(σ)] if necessary, we may assume that the f^{k}-image of the terminal endpoint q of σ is contained in the same stratum for all k ≥ 0. In particular, q is not in the interior of an edge E satisfying f(E) = Eu for some non-trivial u. Since σ has only trivial splittings, q is not contained in the interior of a fixed edge E. Thus either : (i) the terminal endpoint of σ is a vertex and the terminal edge is some non-exponentially growing Ē_{j} with non-trivial u_{j} or (ii) the terminal end is contained in an exponentially growing stratum H_{r}. If σ = E_{i}γĒ_{i}, then (i) holds for E_{i} = E_{j} without replacing σ by [f^{l}(σ)].

Suppose at first that (i) holds. Write σ = E_{i}γ′Ē_{j}, where γ = γ′ if j = i. Define R_{i} to be the infinite path u_{i} · [f(u_{i})] · [f^{2}(u_{i})] · . . . and define R_{i}^{m} to be the initial segment u_{i} · [f(u_{i})] · [f^{2}(u_{i})] · · · · · [f^{m−1}(u_{i})]. We refer to the [f^{k}(u_{i})]’s as the blocks of R_{i}. Define R_{j} and R_{j}^{m} similarly with u_{j} replacing u_{i}. Then [f^{m}(σ)] = [E_{i}R_{i}^{m}f^{m}(γ′)R̄_{j}^{m}Ē_{j}]. We claim that R_{i} and R_{j} have common subpaths that contain at least three blocks in each ray.

Since σ has no non-trivial splittings, the canonical splitting set S(σ) consists of the initial endpoint of σ and perhaps the terminal endpoint of σ. If S(σ) is just the initial endpoint of σ, then there exists m > 0 and an initial segment E_{i}^{∗} of E_{i} such that [f^{k}(E_{i}^{∗})] = [f^{k}(σ)]. But [f^{k}(E_{i}^{∗})] = [f^{l}(E_{i}μ^{∗})] for some l and some initial segment μ^{∗} of u_{i} and is therefore splittable by part (3) of Proposition 6.21. We conclude that S(σ) = ∂σ .

There are subpaths σ_{m} ⊂ σ, whose complement is a small neighborhood of the endpoints of σ, such that f^{m}(σ_{m}) tightens to a point. In particular, there exists M so that f^{M}(γ′) is completely cancelled away when f^{M}(σ) is tightened to [f^{M}(σ)]. Thus [f^{M}(σ)] = E_{i}μ_{M} ν̄_{M} Ē_{j} where μ_{M} and ν̄_{M} are initial subpaths of R_{i}^{M} and R̄_{j}^{M} respectively. For m > M, [f^{m}(σ)] = [f^{m−M}(E_{i}μ_{M} ν̄_{M} Ē_{j})]. Since E_{i}μ_{M} = [f^{l}(E_{i}μ^{∗})] for some initial segment μ^{∗} of μ_{i}, part (3) of Proposition 6.4 implies that E_{i}μ_{M} = E_{i} · μ_{M}; similarly ν̄_{M} Ē_{j} = ν̄_{M} · Ē_{j}. Thus [f^{m}(σ)] is obtained from the concatenation of E_{i}R_{i}^{m−M}[f^{m−M}(μ_{M})] and [f^{m−M}(ν̄_{M})]R̄_{j}^{m−M} Ē_{j} by cancelling at the juncture point. For sufficiently large m, long cancellation must occur in both R_{i}^{m−M} and R̄_{j}^{m−M}. The only way that this could happen is if long segments of R_{i}^{m−M} and R̄_{j}^{m−M} cancel with each other. This verifies our claim.

Choose a lift Ẽ_{i} in the universal cover Γ and choose m as in the previous paragraph. There is a lift of [f^{m}(σ)] that begins with Ẽ_{i} and ends at the inverse of some Ẽ_{j}. Let R̃_{i} and R̃_{j} be the lifts of R_{i} and R_{j} that begin at the terminal endpoints of Ẽ_{i} and Ẽ_{j} respectively. The argument in the previous paragraph shows that R̃_{i} ∩ R̃_{j} contains at least three blocks in each ray. Let h_{i} : Γ → Γ and h_{j} : Γ → Γ be the lifts of f that fix the initial endpoints of Ẽ_{i} and Ẽ_{j} respectively.

We consider first the case that h_{i} = h_{j}. Since the initial endpoint of Ẽ_{j} is fixed by h_{i}, part (1) of Proposition 6.21 implies that the initial endpoint of Ẽ_{j} does not lie in Γ_{i−1} and thus E_{j} = E_{i}. The covering translation S of Γ_{i−1} that carries ũ_{i} =< ṽ, h_{i}(ṽ) > to ũ_{j} =< S(ṽ), h_{j}(S(ṽ)) > commutes with h_{i}. Part (2) of Proposition 6.21 implies that [f^{k}(u_{i})] = u_{i} for some k > 0 and hence by induction that [f(u_{i})] = u_{i}; moreover, both R̃_{i} and R̃_{j} are contained in the axis of S. It follows that u_{i} is a multiple of the circuit τ determined by S and that the segment of the axis of S that separates the terminal endpoints of Ẽ_{i} and Ẽ_{j} projects to some τ^{q}. We have shown that [f^{m}(E_{i}γĒ_{i})] = E_{i}τ^{q}Ē_{i}. Since E_{i}γĒ_{i} and E_{i}τ^{q}Ē_{i} have the same endpoints and the same image under f_{#}^{m}, they must be equal. This completes the proof in the special case and we assume from now on that h_{i} ≠ h_{j}.

Assume for now that H_{s} is a non-exponentially growing stratum. Let X̃ ⊂ R̃_{i} be the set of vertices that are either the initial endpoint of a lift of E_{s} in R̃_{i} or the terminal endpoint of a lift of Ē_{s} in R̃_{i}. Order the elements of X̃ so that x̃_{l} < x̃_{l+1} in the orientation on R̃_{i}. Lemma 5.2 implies that h_{i}(x̃_{l}) = x̃_{l+n_{0}} for all l and some fixed n_{0}. Define Ỹ ⊂ R̃_{j} and m_{0} similarly using R_{j} and h_{j} instead of R_{i} and h_{i}. Then Z̃ = X̃ ∩ Ỹ ⊂ R̃_{i} ∩ R̃_{j} contains at least n_{0} + m_{0} + 1 consecutive elements z̃_{0}, …, z̃_{n_{0}+m_{0}} of X̃ and of Ỹ and h_{i}h_{j}(z̃_{0}) = h_{i}(z̃_{m_{0}}) = z̃_{n_{0}+m_{0}} = h_{j}(z̃_{n_{0}}) = h_{j}h_{i}(z̃_{0}). Since h_{i}h_{j} and h_{j}h_{i} are lifts of f^{2} that agree at a point, they are equal.

There is a non-trivial covering translations S such that Sh_{i} = h_{j} and there is a covering translation T such that T h_{j} = h_{i}S. Then h_{i}h_{j} = h_{i}Sh_{i} = T h_{j}h_{i} so T is the identity and h_{i} commutes with S. A symmetric argument shows that h_{j} also commutes with S. Part (2) of Proposition 6.21 implies that u_{i}, u_{j} ⊂ G_{i−1} are periodic Nielsen paths and that R̃_{i} and R̃_{j} are contained in the axis of S. By the inductive hypothesis, [f(u_{i})] = u_{i} and [f(u_{j})] = u_{j}. The covering translation S_{i} that carries the initial endpoint of ũ_{i} to the terminal endpoint of ũ_{i} and the covering translation S_{j} that carries the initial endpoint of ũ_{j} to the terminal endpoint of ũ_{j} both preserve the axis of S and hence commute with S and with each other. It follows that u_{i} = τ^{k} and u_{j} = τ^{l} where τ is the circuit corresponding to the axis of S; moreover, [f^{m}(σ)] = E_{i}τ^{q}Ē_{j} for some q. Since σ and E_{i}τ^{q−m(k−l)}Ē_{j} have the same endpoints and the same image under f_{#}^{m}, they are equal. We have now proven (2) and (3) in the case that (i) holds and H_{s} is non-exponentially growing.

Suppose now that (i) holds and H_{s} is exponentially growing. If the decomposition of u_{i} given by Lemma 5.8 contains at least one ρ_{s} or ρ̄_{s}, then the previous argument requires only one modification. Namely, X̃ is defined to be the set of lifts of ρ_{s} or ρ̄_{s}. These get ‘translated’ by h_{i} and h_{j} so the argument goes through exactly as before.

If the decomposition of u_{i} given by Lemma 5.8 contains no ρ_{s} of ρ̄_{s}, then u_{i} is s-legal. Since blocks of R̄_{j} cancel with segments of R_{i}, u_{j} is also s-legal. The action of f on R_{i} and R_{j} is more like an affine map than like a translation so we do not use the previous argument. Recall that [f^{m}(σ)] = E_{i}μ_{m}ν̄_{m}Ē_{j} where μ_{m} and ν̄_{m} are initial subpaths of R_{i} and R̄_{j} and in particular are s-legal. Lemma 5.4 implies that μ_{m} and ν_{m} take on only finitely many values and hence that some [f^{m}(σ)] is a periodic Nielsen path, say [f^{m+p}(σ)] = [f^{m}(σ)]. There is a lift f̃ whose restriction to Γ equals h_{i}. Thus f̃ fixes the initial endpoint of Ẽ_{i} and f̃^{p} fixes the initial endpoint q̃ of Ẽ_{j}.

If E_{i} ≠ E_{j}, then q̃ ∈ Γ. Part (1) of Proposition 6.21 implies that p > 1. Let γ̃ ⊂ Γ be the path that connects q̃ to h_{i}(q̃) and let γ be its image in G_{i−1}. Then γ is a periodic Nielsen path and so by the inductive hypothesis is a Nielsen path. But then [γ^{p}] = [γf(γ) … f^{p−1}(γ)] lifts to the trivial path [γ̃h_{i}(γ̃) · · · · · h_{i}^{p−1}(γ̃)] which is impossible. We conclude that E_{i} = E_{j}. The covering translation S that carries the initial endpoint of Ẽ_{i} to the initial endpoint of Ẽ_{j} commutes with f̃^{p}. The restriction S|Γ_{i−1} therefore commutes with h_{i}^{p}. This implies that R̃_{i} and S(R̃_{i}) have an infinite end in common and hence that R̃_{i} and the axis of S have an infinite end in common. It follows that h_{i} preserves the axis of S and so commutes with S. This contradicts part (2) of Proposition 6.21 and the fact that u_{i} is s-legal. We have now completed the proof when (i) holds.

We now consider the possibility that (ii) holds. Arguing as in the previous case, the assumption that σ has only trivial splittings implies that for all sufficiently large m, [f^{m}(E_{i}γ)] = E_{i}μ_{m}ν_{m} where μ_{m} ⊂ R_{i} and where ν_{m} ⊂ G_{r} is r- legal. If r > s, then H_{r}-edges of [f^{(l−m)}(ν_{m})] will not be cancelled when [f^{l−m}(E_{i}μ_{m})][f^{(l−m)}(ν_{m})] is tightened to [f^{l}(σ)]. In this case, [f^{l}(σ)] and hence σ has non-trivial splittings; thus r ≤ s. If r < s, then the H_{s} edges of [f^{l−m}(E_{i}μ_{m})] will not be cancelled in this tightening and we again contradict the assumption that σ has only trivial splittings. We conclude that r = s. The same argument shows that μ_{m} must be s-legal. Lemma 5.4 now implies that μ_{m} takes on only finitely many values. The same is true for ν_{m}: the argument is essentially the same as the one in the proof of Lemma 5.7. There are no subtleties in applying this argument and we leave the details to the reader. We conclude that [f^{m}(σ)] is a periodic Nielsen path. But the argument of the previous paragraph in the E_{i} ≠ E_{j} case proves that this is impossible. We conclude that (ii) does not occur.

It remains to prove that every periodic Nielsen path ρ ⊂ G_{i} has period one. Lemma 5.2 implies that ρ splits into periodic Nielsen paths that are either contained in G_{i−1} or are basic paths. Conditions (1) - (3) of this lemma (which we have already verified), imply that a basic path that is also a periodic Nielsen path splits into exceptional paths and periodic Nielsen paths in G_{i−1}. By induction and by examination of the exceptional paths, we conclude that ρ has period one.

6.6 Proof of Theorem 6.4

Choose (Lemma 6.10) a reduced F-Nielsen minimizing relative train track map f : G → G that represents O^{k} for some k ≥ 1. If there are components of some G_{i} that form an invariant forest, collapse each of these components to points. After tightening the images of edges if necessary, there is an induced topological representative that we continue to call f : G → G. It is easy to check that f : G → G is still a relative train track map and we leave this to the reader. This collapse has no effect on any F(G_{i}) and does not create any new Nielsen paths . Thus f : G → G is still F-Nielsen minimizing. We may therefore assume that contractible components of the G_{i}’s are mapped off of themselves by f and so are unions of zero strata.

Lemma 6.12, Lemma 6.7, Proposition 6.13 and the construction of S in section 6.3 imply (eg-i), (eg-ii), (eg-iii). If H_{r} is an exponentially growing stratum and ρ ⊂ G_{r} is an indivisible periodic Nielsen path that intersects H_{r} non-trivially, then since f : G → G is F-Nielsen minimizing, ρ has period one. These properties are unchanged by taking iterates.

After passing to an iterate if necessary, we may assume : that f(v) is a fixed point for each vertex v; that the non-contractible components of the G_{i}’s are mapped to themselves by f; and that (ne-(i)) is satisfied. After subdividing at a fixed point if necessary, we may assume that each nonexponentially growing stratum E_{i} satisfies f(E_{i}) = E_{i}u_{i} for some path u_{i} ⊂ G_{i−1}.

Suppose that H_{i} is exponentially growing, that C is a non- contractible component of G_{i−1} and that v ∈ H_{i} ∩ C. Choose a path α between v and f(v). Since f|C : C → C is a homotopy equivalence of C, there is a loop β based at f(v) so that [f(β)] = [f(α)]. Then δ = αβ̄ is a path between v and f(v) such that [f(δ)] is trivial. The train track property for H_{s} implies that δ is trivial and hence that v = f(v) is a fixed point.

Apply Proposition 6.21 to the non-exponentially growing strata in the filtration for f : G → G working upwards. At the end of this process we have lost none of our previously acquired properties and arranged that f(E_{i}) = E_{i} · u_{i}. Moreover, the endpoints of the edges in non-exponentially growing stratum are periodic and hence fixed. We have therefore established (ne-ii). Lemma 6.22 implies that condition (ne-iii) holds and that every periodic Nielsen path has period one. The properties that we have verified so far are all stable under passing to an iterate of f.

Suppose that H_{i} is a zero stratum, that C is a non-contractible component of G_{i−1} that intersects H_{i} and that H_{i} is the highest zero stratum with this property. There must be a vertex v of H_{i} that has valence one in C. Since G does not have valence one vertices, v is incident to some edge that is not part of a zero stratum. But we have already shown that such vertices are fixed points. This contradicts the fact that the only edge incident to v in C maps off of itself. We conclude that edges in any zero stratum H_{i} are disjoint from the non-contractible components of G_{i−1}.

We now reorganize the zero strata and push them up the filtration as high as possible. Assume that H_{i} is a zero stratum. If H_{i+1} is a zero stratum, then after replacing f by an iterate if necessary, we can amalgamate H_{i} and H_{i+1} into a single stratum (still called H_{i+1}). We may therefore assume that H_{i+1} is an irreducible stratum. If some components of H_{i} are components of G_{i+1}, then they are not in the image of G_{i+1}, and we can remove these components from H_{i} and consider them as a new stratum H_{i+2}. We may therefore assume that G_{i+1} has no contractible components. Since the endpoints of edges in non-exponentially growing strata are fixed points, H_{i+1} must be an exponentially growing stratum. If an edge E of H_{i} were not in the image of H_{i+1}, then we could remove it from H_{i} and consider it as a new zero stratum H_{i+2}. But then this would violate our observation above that edges of zero strata are never attached to non-contractible components of the previous filtration element. We conclude that every edge in H_{i} must be in the image of H_{i+1}. Since vertices in H_{i} are not in the image of vertices of H_{i+1} (because they are not fixed points), each vertex in H_{i} has valence at least two in G_{i+1}. Since H_{i+1} is exponentially growing, every vertex in G_{i+1} has valence at least two.

If H_{i} is a zero stratum and f|H_{i} is not an immersion, then there are a pair of edges in H_{i} that can be folded. Perform the fold and replace f : G → G by the resulting relative train track map (still called f : G → G ). The total number of edges in the image of H_{i} is reduced by the fold so after finitely many such folds, f|H_{i} is an immersion. (c.f. [BH95]). Perform this folding operation on each zero stratum, working up through the filtration. This ensures that the modifications made in one zero stratum do not undo the modifications made in the previous strata. If v is a valence two vertex of G with both incident edges in H_{i}, then erase v as a vertex. If w is a vertex of G such that f(w) = v, then the only edges incident to w are contained in another zero stratum. Since f restricts to an immersion on zero strata, w has valence two and we erase it as well. After erasing all such vertices, f : G → G satisfies the zero strata conditions. Since folding in a zero stratum, does not undo the conditions on the irreducible strata, f : G → G satisfies the conclusions of Theorem 6.4.

6.7 Proof of Theorem 6.8

Denote the abelianization of F_{n} by H and note that if G is any marked graph then H can be identified with H_{1}(G, ℤ). When O is in UP G(F_{n}), then each O-periodic free factor F satisfies the following two properties. UP G-(i) : the subspace H_{F} of H determined by F is invariant under the induced action of O. UP G-(ii) : if B is a basis for H_{F} with respect to which the induced action has an upper triangular matrix M_{F}, then each diagonal element of M_{F} equals 1.

It will follow from the proof that a P G automorphism O is in UP G if and only if every periodic free factor satisfies UP G-(i) and UP G-(ii).

Lemma 3.6 provides a relative train track map f : G → G representing O and satisfying (1).

Rather than establish (2) directly, we will establish the following weaker property. (2′) Each H_{i} is a single edge E_{i} satisfying f(E_{i}) = v_{i}E_{i}u_{i} for some closed paths v_{i}, u_{i} ⊂ G_{i−1}.

Note that (2′) implies that all periodic points of f are fixed points. We then arrange (2) by induction on i as follows. If both u_{i} and v_{i} are non-trivial, then subdivide E_{i} to create two edges with either u_{i} or v_{i} trivial. If v_{i} is not trivial, replace E_{i} by Ē_{i}. We may therefore assume that v_{i} is trivial. Apply Proposition 6.22 to arrange that f(E_{i}) = E_{i} · u_{i} where the initial endpoint of u_{i} is periodic and hence fixed. This completes the proof that (2′) implies (2).

As a first step toward achieving (2′) we modify f : G → G as follows.

Since O ∈ P G(F_{n}), f : G → G has no exponentially growing strata. If v is a valence one vertex of some G_{i} and if E is the unique edge of G_{i} that is incident to v, then perform a homotopy of f by precomposing f with the homotopy that slides v across E to the other vertex of E and then tightening. This homotopy only effects edges that are incident to v. If E′ ≠ E is an edge of H_{l} that is incident to v, then the homotopy changes the way f(E′) crosses edges in G_{i}, but the relative train track property is maintained since l > i. (Keep in mind that a topological representative of an element of P G(F_{n}) is a relative train track map if and only if it has no exponentially growing strata.) The new image of E is trivial so we can collapse E. This does not effect the relative train track property and does not change any [[π_{1}(G_{r})]] so (1) is still satisfied. After finitely many such moves, no G_{i} has a valence one vertex. In particular, there are no zero strata and all components of G_{i} are non-contractible. Condition UP G-(i) implies that each component of G_{i} is f-invariant.

We now arrange (2′) by induction on i. This may require some additional changes in f : G → G . Since f transitively permutes the edges of G_{1}, every subgraph of G_{1} is O-periodic and condition UP G-(i) implies that π_{1}(G_{1}) has rank one. Since G_{1} does not contain any valence one vertices, G_{1} is homeomorphic to a circle. Condition UP G-(ii) implies that f|G_{1} is orientation preserving. If G_{1} contains more than one edge, then f|G_{1} is a non-trivial rotation. Perform a homotopy of f by precomposing f with a homotopy with support in a small neighborhood of G_{1} that agrees with f^{−1}|G_{1} and then tightening. At this point, the map (which we still call f) fixes each edge in G_{1}; collapse all but one of these edges to arrange that G_{1} is a single edge E_{1} satisfying f(E_{1}) = E_{1}. As in the previous paragraph, (1) is still satisfied.

We assume now that (2′) holds for G_{i−1} and prove it for G_{i}. Suppose that H_{i} = {E^{1}, … E^{p}}. Then f(E^{j}) = v^{j}E^{j+1}u^{j} or f(E^{j}) = v^{j}Ē^{j+1}u^{j} for subpaths v^{j}, u^{j} ⊂ G_{i−1}, where the indices of the E^{j}’s are taken mod p and where some reordering may have been necessary. If the E^{j}’s are disjoint from G_{i−1}, then they determine a component of G_{i} and we may proceed exactly as in the G_{1} case. We may therefore assume that the endpoints of E^{j} are contained in (possibly equal) components C_{1} and C_{2} of G_{i−1}.

Suppose that C_{1} = C_{2}. The subgraph C_{1} ∪ E^{1} is O-periodic and is mapped to the subgraph C_{1} ∪ E^{2}. Condition UP G-(i) implies that p = 1. By induction, H_{1}(C_{1}, ℤ) has a basis B′ with respect to which the induced action of f is upper triangular with all diagonal elements equal to one. By construction, B′ extends to a homology basis B for H_{1}(C_{1} ∪ E^{1}, ℤ) by adding a single element corresponding to E^{2}. Condition (ii) rules out the possibility that f(E^{1}) = v^{1}Ē^{1}u^{1} so f(E^{1}) = v^{1}E^{1}u^{1} as desired.

If C_{1} ≠ C_{2}, then f(E^{j}) = v^{j}E^{j+1}u^{j} and we need only show that p = 1. If p ≥ 3, then the C_{1} ∪ E^{1} ∪ E^{2} is O-periodic and is mapped to C_{1} ∪ E^{2} ∪ E^{3}. This violates UP G-(i) so p ≤ 2. Suppose that p = 2. There a basis B′ for H_{1}(C_{1}∪C_{2}∪E^{1}, ℤ) that has an upper triangular matrix and that extends to a basis B for H_{1}(C_{1} ∪C_{2} ∪E^{1} ∪E^{2}, ℤ) by adding a single element corresponding to E^{1}. But then f(E^{1}) = v^{2}E^{2}u^{2} violates UP G-(ii) and we have the desired contradiction. This completes our verification of condition (2′).

Property (2) implies property (3). Lemma 6.22 implies Property (4). A useful corollary of (3) is that for any path τ with endpoints at vertices, there is a unique path σ with endpoints at vertices such that [f(σ)] = τ. Since every exceptional path is the image of an exceptional path, a non-exceptional path can not have an image that is an exceptional path.

We say that σ has height i if it crosses E_{i} but not does not cross E_{j} for any j > i. A basic path of height i, or its inverse, is of the form σ = E_{i}μ where μ is either a path in G_{i−1} ( we will refer to this as a type 1 basic path) or a path in G_{i−1} followed by Ē_{i} ( we will refer to this as a type 2 basic path). For inductive arguments, it is useful to lexicographically order basic paths according to their height and type; we refer to this as the complexity of the basic path. Thus a type 2 basic path of height i has greater complexity than a type one basic path of height i and lower complexity than a type one basic path of height i + 1. Note that μ always splits into basic subpaths, each of which has lower complexity than σ.

Since f|G_{1} is the identity, M(σ) = 0 for all σ of height 1. We may therefore assume that (5) and (6) hold for all paths with complexity lower than σ. For both (5) and (6) it is sufficient to assume that σ = E_{i}μ is a basic path. Property (5) implies that M(E_{j}) = 0 for all j < i. Replacing u_{i} by [f^{M(u_{i})}(u_{i})] if necessary, (This requires sliding E_{j} as in the proof of Proposition 6.22.) we may assume that M(u_{i}) = 0 and hence that M(E_{i}) = 0. Note also that if σ is exceptional then M(σ) = 0.

If σ = E_{i}μ splits at some point in E_{i}, then part (1) of Lemma 6.22 implies that [f^{k}(σ)] = α · β for some path β and some k ≥ 0. If there is no such splitting, then by using the splitting point closest to E_{i}, we have σ = E_{i}μ_{1}·μ_{2} where E_{i}μ_{1} has no non-trivial splittings. Parts (2) and (3) of Lemma 6.22 imply that some [f^{k}(σ)] = α·β where α is an exceptional path. In either case, β must have lower complexity than σ so M(σ) ≤ k + M(β) and induction completes the proof of (5).

We now turn to the proof of (6). Suppose that the first term in the splitting of [f^{M(σ)}(σ)] is an exceptional path. Let m = M(μ). Then [f^{m}(μ)] = γ_{1} · γ_{2} · · · · · γ_{s} where each γ_{i} is either a single edge or an exceptional path. Let γ_{i_{0}} be the first non-Nielsen path and let A = γ_{1} ⋯ γ_{i_{0}−1}. For k ≥ 0, [f^{m+k}(μ)] has an initial segment I_{k} of the form AE_{j}u_{j}^{l} or Au_{j}^{l}Ē_{j} where |l| → ∞ as k → ∞. Since E_{i} is the first edge of an exceptional path, u_{i} = τ^{a} for some indivisible Nielsen path τ and [f^{m+k}(E_{i})] = E_{i}τ^{a(m+k)}. Since [f^{m+k}(E_{i})][f^{m+k}(μ)] tightens to a path that splits off an initial exceptional path, A = τ^{b}, u_{j} = τ^{c} and I_{k} = [f^{k}(γ_{1} … γ_{i_{0}})] has the form Aū_{j}^{k}Ē_{j}. Thus [f^{m}(E_{i})γ_{1} … γ_{i_{0}}] = E_{i}τ^{am+b}Ē_{j} is exceptional and M(σ) = M(μ).

It remains to prove (6) in the case that [f^{r}(σ)] = E_{i} · β_{r} for some smallest r. For l ≥ 0, let B_{l} = [f^{l}(u_{i})] and let B_{−l} be the unique path with endpoints at vertices such that [f^{l}(B_{−l})] = u_{i}. Then : (i) f_{#}(B_{l}) = B_{l+1} for all l; (ii) B_{k} … B_{l} = B_{k} · · · · · B_{l} for all k and l; and (iii) β_{r} = [B_{0}B_{1} … B_{r−1}f^{r}(μ)] = [f^{r}(B_{−r}B_{−r+1} … B_{−1}μ)]. Thus M(σ) = max{r, M([B_{−r}B_{−r+1} … B_{−1}μ)])}. By induction, it suffices to show that the number of edges in [B_{−r}B_{−r+1} … B_{−1}μ] is a uniformly bounded multiple of the number of edges in μ. Note that [B_{−r−1}B_{−r} … B_{−1}μ] = B_{−r−1} · [B_{−r}B_{−r+1} … B_{−1}μ] but that by the minimality of r, [B_{−r}B_{−r+1} … B_{−1}μ] does not split as B_{−r}·[B_{−r+1} … B_{−1}μ] and hence does not split at the terminal endpoint of any B_{l}. Let [B_{−r−1}B_{−r} … B_{−1}μ] = B_{−r−1}B_{−r} … B_{−s}ν for some smallest r + 1 ≥ s ≥ 1. The following lemma implies that there is a uniform bound to r − s. Since the edge length of μ is at least that of B_{−s+1} … B_{−1}, this completes the proof.

Sublemma 6.23. There is a uniform constant C so that if l − k > C and if a path B_{k} … B_{l}ν splits at the terminal endpoint of B_{k}, then it splits at the terminal endpoint of B_{l−C}.

Proof of Sublemma 6.23 Let X_{n} be the maximal common terminal segment of [f^{n}(ν̄)] and [f^{n}(B_{k} … B_{l})] = B_{k+n} … B_{l+n}. We must show that for all n ≥ 0, X_{n} ⊂ B_{l+n−C} … B_{l+n}. In other words, we must show that there is a uniform bound to the number of ‘B-blocks’ that are cancelled. If height(ν) ≤ height(u_{i}), then X_{n} ⊂ B_{l+n}. We may therefore assume that height(ν) > height(u_{i}) and that we have verified the sublemma for all ν of lower height. We may also assume that B_{k} … B_{l}ν does not split at a vertex of ν, for otherwise we could shorten ν. Lemma 5.2 therefore implies that ν = ν′Ē_{j} where j = height(ν) and height(ν′) < j.

Define C_{m} = [f^{m}(u_{j})]. Then [f^{n}(B_{k} … B_{l}ν)] is obtained from (B_{k+n} ·· · ·· B_{l+n})

[f^{n}(ν′)](C̄_{n} · · · · · C̄_{0} · Ē_{j}) by cancellation at the two indicated junctures.

We first consider the case that a subpath of B_{k+n} · · · · · B_{l+n} that contains at least three B- blocks cancels with a subpath of C̄_{n} · · · · · C̄_{0} that contains at least three C-blocks. During the proof of Lemma 6.22 (see pages 51 and 52) we showed that this implies the existence of an indivisible Nielsen path τ such that u_{i} = τ^{a}, u_{j} = τ^{b} and ν′ = τ^{p}. Since B_{k} … B_{l}ν′ = τ^{a(k−l)}τ^{p} is a path, a and p have the same sign, say a, p > 0. Since B_{k} … B_{l}ν′Ē_{j} splits at the terminal endpoint of B_{k}, b < 0. It follows that B_{k} … B_{l}ν′Ē_{j} splits at the terminal endpoint of each B-block. This completes the proof in this case.

If there is no cancellation between B_{k+n} · · · · · B_{l+n} and C̄_{n} · · · · · C̄_{0}, then X_{n} is the same as if we were considering B_{k} … B_{l}ν′ instead of B_{k} … B_{l}ν. In particular, X_{n} ⊂ B_{l+n−C′} … B_{l+n} for some uniform C′ by induction. We may therefore assume that there is some smallest n_{0} so that [f^{n_{0}}(ν′)] is completely cancelled when f^{n_{0}}(B_{k} … B_{l}ν) is tightened. Induction and the bounded cancellation lemma imply that at this stage only a uniformly bounded number of B-blocks cancel when f^{n_{0}}(B_{k} … B_{l}ν) is tightened to [f^{n_{0}}(B_{k} … B_{l}ν)]. Any further tightening for n > n_{0} will involve C-blocks and B-blocks. If further tightening results in three more C-blocks being cancelled, then by our previous argument, no more than three additional B-blocks can be cancelled. Since all we require is a uniform bound to the number of cancelled B-blocks, we are done. We may therefore assume that fewer than three C-blocks are involved in further cancellation. Thus for n > n_{0} + 3, there is no loss (from the point of view of cancelling B blocks) in replacing [f^{n_{0}}(B_{k} … B_{l}ν)] = [f^{n_{0}}(B_{k} … B_{l}ν′)C̄_{n_{0}} ⋯ C̄_{0}Ē_{j})] by [f^{n_{0}}(B_{k} … B_{l}ν′C̄_{n_{0}} ⋯ C̄_{0}C̄_{−1}C̄_{−2}C̄_{−3}]. Cancellation for n > n_{0} + 3 (and hence for n > n_{0} is uniformly bounded by induction and the fact that ν′C̄_{n_{0}} ⋯ C̄_{0}C̄_{−1}C̄_{−2}C̄_{−3} has height less than j.

We will also need the following technical results in [BFH96b].

Lemma 6.24. Suppose that f : G → G is as in Theorem 6.8. There is a uniform constant C_{1} so that if ω is a closed path that is not a Nielsen path and σ = αω^{k}β is a path, then at most C_{1} copies of [f^{n}(ω)] are cancelled when [f^{n}(α)][f^{n}(ω^{k})][f^{n}(β)] is tightened to [f^{n}(σ)].

Proof of Lemma 6.24 It is sufficient to consider the case that β is empty. The proof is by induction on the height of α. If height(α) ≤ height(ω), then the highest edges in [f^{n}(ω)] are never cancelled. We may therefore assume that height(α) > height(ω) and that we have verified the lemma for all α of lower height. By Lemma 5.2 we may also assume that α = E_{j}α′ where height(α) = j and height(α′) < j. By induction, only a bounded number of copies of [f^{n}(ω)] are cancelled when f^{n}(α′ω^{k}) is tightened. Since f^{n}(E_{j}) = E_{j}u_{j}[f(u_{j})] … [f^{n−1}(u_{j})], Sublemma 6.26 below completes the proof.

Let B_{l} = [f^{l}(u_{j})] and R_{j} = B_{0} · B_{1} · · · · · B_{l} · . . ..

Sublemma 6.25. If γ^{N} ⊂ R_{j} and γ^{N} contains at least three blocks of R_{j} for some N ≥ 3, then γ is a Nielsen path.

Proof of Sublemma 6.25 Lifting to the universal cover, there exists R̃_{j} = B̃_{0}B̃_{1} … where f̃(B̃_{l}) = B̃_{l+1} and there exists a covering translation T corresponding to γ so that the axis of T has an interval I in common with R̃_{j} that contains three B-blocks and three fundamental domains of the axis A(T) of T. Since T and f̃ both ‘translate’ the initial segments of the highest edges in I (c.f. the proof of Lemma 6.22, especially pages 47 and 48) the two lifts T f̃ and f̃T of f agree at a point and so must be equal. We conclude that T commutes with f̃ and hence that γ is Nielsen.

Sublemma 6.26. There is a uniform constant K with the following property. If γ^{K} ⊂ R_{j}, then γ is a Nielsen path.

Proof of Sublemma 6.26 The proof is by induction on j, the j = 1 case being trivial.

If u_{j} has m edges, then B_{l} can be written as a concatenation of at most m edges and at most m subpaths of rays R_{i} with i < j. By induction, there is a constant K_{0} so that if γ^{K_{0}} ⊂ B_{l} then γ is a Nielsen path.

Let K = 6K_{0}. If γ^{K} ⊂ R_{j} then either γ^{K_{0}} is contained in some B_{l} or γ^{K} contains three blocks of R_{j}. In either case γ is a Nielsen path.

7 The Weak Attraction Theorem

We assume throughout this section that O is eg-aperiodic and that Λ^{+} is a topmost element of L(O); i.e. that Λ^{+} is not contained in any other element of L(O). Let Λ^{−} be the expanding lamination for O^{−1} that is paired (Lemma 4.6) with Λ^{+}. The following Weak Attraction Theorem is the main result of this section. It is an explicit description of the basin of attraction of Λ^{+} in the birecurrent elements of B. In the next section we will exploit the fact that ‘most’ birecurrent paths are attracted to Λ^{+}.

Theorem 7.1. Suppose that Λ^{+} is a topmost element of L(O), that f : G → G is an improved relative train track map representing O and that H_{r} is the exponentially growing stratum that determines Λ^{+}.Then there exists a subgraph Z such that Z ∩ G_{r} = G_{r−1} and such that every birecurrent path γ ⊂ G satisfies exactly one of the following.

1. γ is a generic leaf of Λ^{−}.

2. γ ∈< Z, ρ_{r} >

3. γ is weakly attracted to Λ^{+}.

Remark 7.2. Suppose that G = G_{r} and hence that Z = G_{r−1}. If H_{r} is not a geometric stratum, then Lemma 6.7 and (eg-ii) imply that < Z, ρ_{r} > contains the same bi-infinite paths as G_{r−1}. If H_{r} is a geometric stratum, then (eg-iii) implies that the set of bi-infinite paths in < Z, ρ_{r} > is the union of the bi-infinite paths in G_{r−1} with the circuit ρ_{r}.

Remark 7.3. Suppose that ϕ : S → S is a homeomorphism of a compact surface and that S_{0} ⊂ S is a proper subsurface that is a pseudo-Anosov component of ϕ. The geometric analog of Theorem 7.1 implies that the expanding measured foliation F for ϕ|S_{0} weakly attracts every closed curve that is not entirely contained in S \ S_{0}. If we work in the projective foliation space P F rather than in B, then F is only certain to attract every simple closed curve that is entirely contained in S_{0}. Thus the basin of attraction in B can be larger than the basin of attraction in P F.

The following proposition is one of the two main steps in proving Theorem 7.1. Before beginning its proof, we state and prove a lemma that is needed in that proof.

Proposition 7.4. Suppose that f : G → G is an improved relative train track map representing O, that Λ^{+} is a topmost element of L(O) and that H_{r} is the exponentially growing stratum that determines Λ^{+}. Then there is a subgraph Z of G such that:

1. Z ∩ G_{r} = G_{r−1}.

2. Z contains every zero stratum and every exponentially growing stratum other than H_{r}.

3. f(E) ∈< Z, ρ_{r} > for each edge E in Z.

4. Suppose that σ ⊂ G is a finite path whose endpoints are fixed by f. Then σ ∈< Z, ρ_{r} > if and only if σ is not weakly attracted to Λ^{+}.

The following lemma is used in the definition of Z.

Lemma 7.5. Suppose that f : G → G is an improved relative train track map, that H_{r} is an exponentially growing stratum, that ρ_{r} exists and that X is a subgraph of G with non-contractible components such that :

1. X ∩G_{r} = Q_{r−1}, the union of the non- contractible components of G_{r−1}.

2. f(E) ∈< X, ρ_{r} > for each edge E of X.

Define X_{∗} by adding an edge ρ to X and identifying an endpoint of ρ with the corresponding endpoint of ρ_{r} if this endpoint lies in X. Define h : X_{∗} → G by h(ρ) = ρ_{r} and by the inclusion on X. Then the unique (up to homotopy rel vertices) map f_{∗} : X_{∗} → X_{∗} satisfying hf_{∗} ≃ fh rel vertices is a homotopy equivalence.

Proof of Lemma 7.5 Conditions (1) and (2) imply that the subgraph X∪G_{r} of G is f-invariant and has non-contractible components. The restriction of f to X∪G_{r} is therefore a homotopy equivalence and there is no loss in assuming that G = X ∪ G_{r}. The existence and uniqueness of f_{∗} follows easily from (1) and (2). The content of the lemma is that f is a homotopy equivalence.

The main step in the proof is choose a particular factorization f = θp_{k}p_{k−1} … p_{1} where each p_{i} : G^{i−1} → G^{i} is a composition of folding maps, where G^{0} = G and where θ : G^{k} → G is a homeomorphism. We choose additional notation as follows: P_{i} = p_{i}p_{i−1} … p_{1} : G → G^{i}; g_{i} : G^{i} → G is the induced map satisfying f = g_{i}P_{i}; G_{j}^{i} = P_{i}(G_{j}) ⊂ G^{i}; and H_{r}^{i} = P_{r}^{i} \ P_{r−1}^{i}.

If f|G_{r−1} is not a homeomorphism, then there are edges in G_{r−1} that can be folded with each other. Define p_{1} : G → G^{1} to be any such fold. If g_{1}|G_{r−1}^{1} is not a homeomorphism, then define p_{2} : G^{1} → G^{2} by folding a pair of edges in G_{r−1}^{1}. Continue in this way to define, for some 1 ≤ i ≤ m, maps p_{i} : G^{i−1} → G^{i} that fold a pair of edges in G_{r−1}^{i−1}; m is chosen so that g_{m}|G_{r−1}^{m} : G_{r−1}^{m} → G_{r−1} is a homeomorphism.

If g_{m}|G_{r}^{m} is not a homeomorphism, then there are edges in G_{r}^{m} that can be folded with each other. Define p_{m+1} to be any such folding map. At least one edge being folded will necessarily belong to H_{r}^{m}. If the other edge is in G_{r−1}^{m}, then all of it is folded with all or part of the edge in H_{r}^{m}. Thus p_{m+1} only effects edges in H_{r}^{m}. Continue in this way to define, for some m + 1 ≤ i ≤ n, folding maps p_{i} : G^{i−1} → G^{i} as just described; n is chosen so that g_{n}|G_{r}^{n} : G_{r}^{n} → G_{r} is a homeomorphism.

We must be a little more careful about the remaining folds. Suppose that E_{1} is an edge in G^{n} \ G_{r}^{n}, that E_{2} is an edge in G^{n} and that the edge paths [g_{n}(E_{1})] and [g_{n}(E_{2})] have the same initial edge e ⊂ G. If e ⊄ H_{r}, then define p_{n+1} by identifying the initial segments of E_{1} and E_{2} that map to e. Note that in this case E_{2} ⊄ H_{r}^{n}. If e ⊂ H_{r}, then condition (2) implies that [g^{n}(E_{1})] has an initial subpath that equals either ρ_{r} or ρ̄_{r}, say ρ_{r}. If E_{2} ⊄ H_{r}^{n}, then [g^{n}(E_{2})] has an initial subpath that is either ρ_{r} or ρ̄_{r}. Since ρ_{r} and ρ̄_{r} have different initial edges, [g^{n}(E_{2})] has ρ_{r} as an initial segment. In this case, define p_{n+1} by identifying the initial segments of E_{1} and E_{2} that map to ρ_{r}. In the remaining case, E_{2} ⊂ H_{r}^{n}. Define p_{n+1} by identifying the initial segment of E_{1} that maps to ρ_{r} with the unique path in G_{r}^{n} with g_{n}-image equal to ρ_{r}. Repeat this, for some n ≤ i ≤ k, to arrive at a homeomorphism θ = g_{k}. This completes the first part of the proof.

Let G_{∗}^{i}, 0 ≤ i ≤ k, be the graph obtained from G^{i} by removing the edges of H_{r}^{i}, adding an edge ρ and identifying an endpoint of ρ with the corresponding endpoint of ρ_{r}^{i} = P_{i}(ρ_{r}) if this endpoint does not lie in the interior of an edge of H_{r}^{i}. Let h_{i} : G_{∗}^{i} → G^{i} be the map defined by h_{i}(ρ) = ρ_{r}^{i} and by inclusion on the remaining edges of G_{∗}^{i}. Note that G_{∗}^{0} = X_{∗} and that h_{0} = h. We claim that there are maps q_{i} : G_{∗}^{i−1} → G_{∗}^{i} such that h_{i}q_{i} ≃ p_{i}h_{i−1} rel vertices. For 1 ≤ i ≤ m, the edges of G^{i} that are folded by p_{i} do not lie in H_{r}^{i} and so can be thought of as edges in G_{∗}^{i}. Define q_{i} by folding the same edges or edge segments that are used to define p_{i}. For m + 1 ≤ i ≤ n, let q_{i} be the identity. Assume now that n + 1 ≤ i ≤ k. If E_{2} ⊄ H_{r}^{i}, then the edges of G^{i} that are folded by p_{i} can be thought of as edges in G_{∗}^{i}. As before, q_{i} is defined by folding the same initial segments of E_{1} and E_{2} that are used to define p_{i}. In the remaining case, E_{1} is an edge in G_{∗}^{i} and we define q_{i} by identifying an initial segment of E_{1} with ρ. It is immediate from the definitions that h_{i}q_{i} ≃ p_{i}h_{i−1} rel vertices.

The homeomorphism θ : G^{k} → G maps H_{r}^{k} to H_{r} and therefore induces a homeomorphism θ_{∗} : G_{∗}^{k} → X satisfying hθ^{∗} = θh_{k}. Then f_{∗} = θ_{∗}q_{∗}^{k} … q_{∗}^{1} and each map in this factorization is a homotopy equivalence.

Proof of Proposition 7.4 We build Z_{i} = Z ∩ G_{i} in stages, beginning with Z_{r} = G_{r−1}. Condition (3) for Z_{r} follows from the invariance of G_{r−1}.

Before verifying condition (4) for Z_{r}, we make two general observations about proving (4) for Z_{i} once (3) for Z_{i} is known.

If σ ∈< Z_{i}, ρ_{r} >, then [f^{k}(σ)] ∈< Z_{i}, ρ_{r} > for all k ≥ 0. Since < Z_{i}, ρ_{r} > does not contain any r-legal paths with more H_{r}-edges than are contained in ρ_{r}, σ is not weakly attracted to Λ^{+}. Thus we need only prove the if half of (4). For the second observation, assume that each component of Z_{i} is non-contractible. We claim that we can replace σ by [f^{k}(σ)] without loss of generality. This replacement clearly has no effect on being weakly attracted to Λ^{+}, so we need only check that if [f^{k}(σ)] ∈< Z_{i}, ρ_{r} > for some k > 0, then σ ∈< Z_{i}, ρ_{r} >. For any homotopy equivalence f : G → G and path τ ⊂ G with fixed endpoints, there is exactly one path σ that has the same endpoints as τ and that satisfies [f(σ)] = τ. Applying this to the homotopy equivalence f_{∗}^{k} : X_{∗} → X_{∗} of Lemma 7.5 with X = Z_{i}, we see that there is a path σ′ ∈< Z_{i}, ρ_{r} > with fixed endpoints such that [f^{k}(σ′)] = [f^{k}(σ)]. Applying it again to f^{k} : G → G, we conclude that σ = σ′ and hence that σ ∈< Z_{i}, ρ_{r} >.

We now turn to the proof of (4) for Z_{r}. Suppose that σ ⊂ G_{r} has fixed endpoints and is not weakly attracted to Λ^{+}. After replacing σ by some [f^{k}(σ)] if necessary, we may assume that each [f^{i}(σ)] contains the same number of illegal turns in H_{r}. Increasing k if necessary, Lemma 5.8 and the fact that ρ_{r} is the unique periodic element of P_{r} imply that σ splits into pieces that are either r-legal or equal to either ρ_{r} or ρ̄_{r}. Since σ is not weakly attracted to Λ^{+}, each of the r-legal pieces must lie in G_{r−1} = Z_{r−1} and so σ ∈< Z_{r−1}, ρ_{r} >.

Assume now that we have defined Z_{i−1} satisfying (1)-(4) for some i > r. If H_{i} is non-exponentially growing, then H_{i} is a single edge E_{i} and f(E_{i}) =

E_{i} · u_{i} for some path u_{i} whose endpoints are fixed by f. If u_{i} is weakly attracted to Λ^{+}, then define Z_{i} = Z_{i−1}. Condition (3) for Z_{i−1} implies condition (3) for Z_{i}. To verify (4), we must show that if σ ⊂ G_{i} has fixed endpoints and is not weakly attracted to Λ^{+}, then σ ⊂ G_{i−1}. Suppose to the contrary that σ crosses E_{i}. Since the endpoints of σ are fixed, they are not in the interior of E_{i}. Lemma 5.2 implies that σ splits into basic pieces, at least one of which contains E_{i} or Ē_{i}. Since u_{i} is weakly attracted to Λ^{+}, Remark 4.2 implies that u_{i} is not a Nielsen path. After replacing σ by an iterate, ne-(iii) implies that there is a further splitting of σ into pieces, at least one of which is E_{i} or Ē_{i}. This contradicts Corollary 5.6 and so verifies (4).

If u_{i} is not weakly attracted to Λ^{+}, then define Z_{i} = Z_{i−1} ∪ E_{i}. The inductive hypothesis implies that u_{i} ∈< Z_{i−1}, ρ_{r} > so (3) is satisfied. Assume that σ ⊂ G_{i} has fixed endpoints and is not weakly attracted to Λ^{+}. Since σ splits into basic pieces, we may assume that σ is a basic piece. If σ ⊂ G_{i−1}, then the induction hypothesis implies that σ ∈< Z_{i−1}, ρ_{r} >. We may therefore assume that σ = E_{i}γ or E_{i}γĒ_{i} for some γ ⊂ G_{i−1}. If γ is a Nielsen path, then the inductive hypothesis implies that γ ∈< Z_{i−1}, ρ_{r} > and hence that σ ∈< Z_{i−1}, ρ_{r} >. If γ is not a Nielsen path, then ne-(iii) implies, after replacing σ by an iterate if necessary, that σ = E_{i} · γ′ or σ = E_{i} · γ′ · Ē_{i}. Since σ is not weakly attracted to Λ^{+}, neither is γ′. The inductive hypothesis implies that γ′ ∈< Z_{i−1}, ρ_{r} > and hence σ ∈< Z_{i}, ρ_{r} >. This completes the proof when H_{i} is non-exponentially growing.

We suppose next that H_{i} is exponentially growing. Define Z_{i} = Z_{i−1} ∪H_{i}. For each edge E_{j} of H_{i}, f(E_{j}) = a_{1} · b_{1} · a_{2} · · · · · a_{m} where each a_{l} is a subpath in H_{i} ⊂ Z_{i} and each b_{l} ⊂ G_{i−1}. Since Λ^{+} is topmost, each b_{l} is not weakly attracted to Λ^{+}. If the endpoints of b_{l} are fixed, then the inductive hypothesis implies that b_{l} ∈< Z_{i−1}, ρ_{r} >. If the endpoints of b_{l} are not fixed, then b_{l} is contained in a zero stratum and so is contained in Z_{i−1} by the inductive hypothesis. This verifies (3).

Suppose that σ ⊂ G_{i} has fixed endpoints and is not weakly attracted to Λ^{+}. Lemma 5.8 and the assumption that ρ_{i} is the unique periodic element of P_{i} imply, after replacing σ by an iterate if necessary, that σ splits into pieces that are either i-legal or equal to ρ_{i} or ρ̄_{i}. An i-legal path splits into subpaths a_{j} ⊂ H_{i} ⊂ Z_{i} and c_{j} ⊂ G_{i−1}; as in the preceding argument the inductive hypothesis implies that c_{j} ∈< Z_{i−1}, ρ_{r} >. It therefore suffices to show that ρ_{i} ∈< Z_{i}, ρ_{r} >. Decompose ρ_{i} = α_{i}β_{i} where α_{i} and β_{i} are i-legal. If the initial endpoint of ρ_{i} is a vertex, let E be the initial edge of ρ_{i}; otherwise, let E be the edge that contains the initial endpoint of ρ_{i}. For sufficiently large k, α_{i} is a subpath of [f^{k}(E)]. Since [f^{k}(E)] ∈< Z_{i}, ρ_{r} > and the initial and terminal segments of α_{i} are in H_{i}, and so in particular are not in G_{r}, α_{i} ∈< Z_{i}, ρ_{r} >. A similar argument holds for β_{i}. Thus ρ_{i} and ρ̄_{i} are contained in < Z_{i}, ρ_{r} >. This completes the proof in the case that H_{i} is exponentially growing.

If H_{i} is a zero stratum, then define Z_{i} = Z_{i−1}∪H_{i}. By z-(i) of Theorem 6.4, H_{i+1} is an exponentially growing stratum. For each edge E_{j} of H_{i+1}, f(E_{j}) = a_{1} · b_{1} · a_{2} · · · · · a_{m} where each a_{l} is a subpath in H_{i+1} and each b_{l} ⊂ G_{i}. Since Λ^{+} is topmost, each b_{l} is not weakly attracted to Λ^{+}. Let {β_{l}} be the set of paths in H_{i} that occur as a b_{k} in the above decomposition for some f(E_{j}).

Suppose that P, Q ∈ H_{i+1} ∩H_{i}. We write P ∼ Q if P and Q belong to the same component of H_{i} or equivalently if there is a path in H_{i} that connects P and Q. There is also an equivalence relation generated by P ∼′ Q if and only if P and Q are the endpoints of some β_{l}. If we collapse each component of the forest H_{i} to a point then the image of G_{i+1} is a graph Ĝ_{i+1} that is homotopy equivalent to G_{i+1}. We can also view Ĝ_{i+1} as being obtained from G_{i+1}\ int(H_{i}) by identifying ∼ equivalent points in H_{i+1}∩H_{i}. Let Ĝ′_{i+1} be the graph obtained from G_{i+1}\ int(H_{i}) by identifying ∼′ equivalent points in H_{i+1} ∩H_{i}. Then Ĝ_{i+1} is obtained from Ĝ′_{i+1} by identifying the elements in certain finite subsets. Each ∼ equivalence class that contains m ∼′ equivalence classes determines a set of m points in Ĝ′_{i+1} that must be identified to form Ĝ_{i+1}. In particular, Ĝ′_{i+1} corresponds to a free factor system F of F(G_{i+1}) that lies between F(G_{i}) = F(G_{i−1}) and F(G_{i+1}). A bi-infinite path is carried by F if and only if it is contained in < (G_{i+1} \ H_{i}), ∪β_{l} >. This collection of bi-infinite paths is mapped into itself by f_{#}, so F is invariant under the action of an iterate of O. Since f : G → G is reduced and F carries the expanding lamination determined by H_{i+1}, F = F(G_{i+1}). This implies that ∼ and ∼′ must be the same relation.

Condition z-(iii) of Theorem 6.4 and the fact that each f(v) is fixed imply that f(β_{l}) is a path in G_{i−1} with fixed endpoints. The inductive hypothesis implies that f(β_{l}) ∈< Z_{i−1}, ρ_{r} >. Thus β_{l} has a decomposition as an alternating concatenation of subpaths μ_{j} that map into Z_{i−1} and ν_{j} that map to either ρ_{r} or ρ̄_{r}.

Suppose that δ_{1} and δ_{2} are paths in H_{i} with endpoints in H_{i+1} ∩ H_{i} and that δ_{1} and δ_{2} have decompositions into μ_{j}’s and ν_{j}’s as above. We claim that if δ_{1} and δ_{2} have a common initial endpoint, then [δ_{1}^{−1}δ_{2}] has a decomposition into μ_{j}’s and ν_{j}’s as above. It suffices to prove that the maximum common initial segment α of δ_{1} and δ_{2} contains every ν_{j} that it intersects. If this fails, then the image of the initial segment of both δ_{1} \α and δ_{2} \α would complete the partial crossing of ρ_{r} or ρ̄_{r} begun in the image of α. By eg-(i)), ρ_{r} and ρ̄_{r} have different initial edges so the partial image can only be completed in one way. Thus the initial segments of δ_{1} \ α and δ_{2} \ α have the same image, in contradiction to the fact (z- (iii) of Theorem 6.4) that f|H_{i} is an immersion. This verifies our claim.

Since ∼ equals ∼′, every path δ ⊂ H_{i} with endpoints in H_{i+1} ∩ H_{i} can be expressed as [b_{1}b_{2} … b_{m}]. The previous paragraph and induction imply that each δ_{k} = [b_{1} … b_{k}], and in particular δ, has a decomposition into μ_{j}’s and ν_{j}’s and each ν_{j} occurs in the decomposition of some b_{l}.

We next check that each ν_{j} is contained in a single edge of H_{i}. Suppose to the contrary that some ν_{j} crosses a vertex w. Since w is in the interior of ν_{j}, it has at least two incident edges in H_{i}. By z-(ii), w has valence at least three and so by z-(iv) there is a (possibly trivial) path τ that starts at w, ends in H_{i+1} ∩ H_{i} and intersects ν_{j} only in w. Choose β_{l} that contains ν_{j}. The unique path δ ⊂ H_{i} that connects the initial endpoint P of β_{l} to the terminal endpoint Q of τ agrees with β_{l} up to w and then follows τ. But then δ deviates from β_{l} in the middle of ν_{j}, in contradiction to our observation in the previous paragraph that the maximum common initial subinterval of δ and β_{l} contains each ν_{j} that it intersects. We conclude that each ν_{j} is contained in a single edge.

Given an edge e of H_{i}, choose β_{l} = μ_{1}ν_{1}μ_{2}ν_{2} … that contains it. The endpoints of e are not contained in the interior of any ν_{j} so f(e) ∈< Z_{i−1}, ρ_{r} >. This completes the proof of (3).

Property (4) for G_{i} follows from property (4) for G_{i−1} and the observation that a path in G_{i} with fixed endpoints can not be contained in, and hence can not intersect, a component of G_{i} that is mapped off of itself.

The following proposition is the second main piece of the proof of Theorem 7.1.

Proposition 7.6. Suppose that H_{s} is an exponentially growing stratum of an improved relative train track map f : G → G, that γ ⊂ G_{s} is a birecurrent path that is not contained in G_{s−1} and that γ is not weakly attracted to the expanding lamination Λ_{s}^{+} associated to H_{s}. If H_{s} is non-geometric, then γ is a generic leaf of Λ_{s}^{−}. If H_{s} is geometric, then either γ is a generic leaf of Λ_{s}^{−} or γ = ρ_{s}.

Proof of Proposition 7.6 in the geometric case We may assume without loss that G_{s} = G. Assume the notation of Definition 6.3; in particular, ϕ : S → S is a pseudo-Anosov homeomorphism, Q is the union of the noncontractible components of G_{s−1}, Y = Q∪A∪S, Φ : (Y, Q) → (G_{s}, G_{s−1}) and h : Y → Y satisfies Φh ≃ gΦ. Let λ_{ϕ} be a leaf of the expanding lamination Λ_{ϕ}^{+} ⊂ S for ϕ and let λ = Φ_{#}(λ_{ϕ}) be the corresponding bi-infinite path in G.

There is a bi-infinite path γ^{∗} ⊂ Y that intersects ∂S transversely, that intersects each A_{i} in arcs that run from one component of ∂A_{i} to the other and that satisfies Φ_{#}(γ^{∗}) = γ. Moreover, if γ^{∗} is not one of the peripheral curves in S, then intersection with ∂S decomposes γ^{∗} into an alternating concatenation of paths a_{i}^{∗} ⊂ Y \ int(S) and geodesics b_{i}^{∗} ⊂ S; if a_{i}^{∗} or b_{i}^{∗} is finite, then it represents a non-trivial element in π_{1}(Y \ int(S) or π_{1}(S, ∂S) respectively.

For each b_{i}^{∗} and k > 0, the corresponding decomposition of h_{#}^{k}(γ^{∗}) contains a path in S that is homotopic rel ∂S to ϕ^{k}(b_{i}^{∗}). If b_{i}^{∗} is not a generic leaf of the expanding lamination Λ_{ϕ}^{−} ⊂ S for ϕ^{−1}, then the geodesic in S representing ϕ^{k}(b_{i}^{∗}) has subpaths of exponentially growing length that are arbitrarily close to subpaths of λ_{ϕ}. Pushing this forward by Φ_{#}, we see that λ has an attracting neighborhood in B and that if γ^{∗} is non-peripheral and not a leaf of Λ_{ϕ}^{−}, then γ is weakly attracted to λ. Since all leaves in Λ_{ϕ}^{+} are dense in Λ_{ϕ}^{+}, λ is birecurrent. Lemma 4.3 and the fact that λ is not carried by G_{s−1} imply that λ is a generic leaf of Λ_{s}^{+}. A similar argument shows that Φ_{#}(Λ_{ϕ}^{−}) = Λ_{s}^{−}. We conclude that if γ is not a generic leaf of Λ_{s}^{−} and is not ρ_{s}, then it is weakly attracted to Λ_{s}^{+}. .

Proof of Proposition 7.6 in the non-geometric case There is no loss in assuming that G = G_{s}. After passing to an iterate if necessary, we may assume that there is an improved relative train track map representing O^{−1} such that F(G_{s−1}) is realized by a filtration element.

The first step in the proof is to show that γ loses illegal turns in H_{s} at an exponential rate under the action of the outer automorphism O determined by f : G → G . This will be made explicit during the course of the proof.

Suppose that α is a path in G with exactly one illegal turn in H_{s} and that for some k > 0, [f^{k}(α)] also has one illegal turn in H_{s}. Let α′ = α′(k) ⊂ α be the closure of the component of α \ S^{k}(α) that contains the illegal turn in H_{s} (cf. Lemma 5.8). There exists K_{1}, independent of α, so that if k ≥ K_{1}, then α′ ⊂ ρ for some ρ ∈ P_{s} and ρ \ α′ consists of initial and terminal segments of ρ that are contained in single edges of H_{s}. This follows by taking limits and observing (cf. Lemma 5.7) that if [f^{k}(α)] contains an illegal turn in H_{s} for all k, then α′(k) ⊂ α′(k + 1) and ∪α′(k) is an element of P_{s}.

Since P_{s} is finite, ρ_{s} is fixed and no other element of P_{s} is periodic, there exists n_{0} so that [f^{n_{0}}(ρ)] = ρ_{s} for all ρ ∈ P_{s}. We may assume without loss that for all k ≥ K_{1}, [f^{n_{0}}(α′)] differs from ρ_{s} by initial and terminal segments that are contained in single edges of H_{s}. After subdividing if necessary, we may assume that the endpoints of ρ_{s} are vertices. By Lemma 5.4 and Corollary 5.6, there exists K > K_{1} so that for any edge E in H_{s}, every path in G that contains [f^{K−n_{0}}(E)] as a subpath is weakly attracted to Λ^{+}.

Suppose that γ is K-split into subpaths, one of which is a finite subpath γ_{0}. We claim that if γ_{0} contains m illegal turns in H_{s}, then [f^{K}(γ_{0})] contains at most m − [\frac{m}{3}] illegal turns in H_{s}. Let l be the number of H_{s}-illegal turns in [f^{K}(γ_{0})]. Write γ_{0} as a concatenation of subpaths γ_{0} = α_{1}α_{2} ⋯ α_{l} where [f^{K}(γ_{0})] = [f^{K}(α_{1})][f^{K}(α_{2})] … … [f^{K}(α_{l})] and where each [f^{K}(α_{i})] contains one illegal turn in H_{s}. Each α_{i} must contain at least one illegal turn in H_{s} since the image of an s-legal path is s-legal. It therefore suffices to show that α_{i−1}α_{i}α_{i+1} contains at least four illegal turns in H_{s} for each 2 ≤ i ≤ l − 1.

Let β_{i} = [f^{n_{0}}(α_{i})]. If α_{i−1}α_{i}α_{i+1} contains exactly three illegal turns in H_{s}, then β_{i−1}β_{i}β_{i+1} contains exactly three illegal turns in H_{s}. By our choice of n_{0}, these turns are contained in disjoint copies ρ^{1}, ρ^{2} and ρ^{3} of ρ_{s} or ρ̄_{s}. With the possible exception of short initial and terminal segments, β_{i−1}β_{i}β_{i+1} contains a subpath of the form ρ^{1}σ_{1}ρ^{2}σ_{2}ρ^{3}. Moreover, all of the H_{s} edges that are cancelled when f^{K−n_{0}}(β_{i−1}β_{i}β_{i+1}) is tightened to [f^{K}(α_{i−1}α_{i}α_{i+1})] are contained ρ^{1}, ρ^{2} and ρ^{3}. Lemma 6.7 and (eg-(ii)) imply that at least one of σ_{1} or σ_{2} must contain an edge E of H_{s}. Thus [f^{K}(α_{i−1}α_{i}α_{i+1})] and hence [f^{K}(γ)] contains [f^{K−n_{0}}(E)]. This contradicts our choice of K and the fact that γ is not weakly attracted to Λ^{+}. We have verified our claim and completed the first step in the proof.

The second step in the proof is to show for any finite subpath γ_{1} of γ there exists τ ⊂ G with a uniformly bounded number of edges in H_{s} such that γ_{1} is a subpath of O_{#}^{−k}(τ) for some k ≥ 0. If G_{s−1} = ∅, then τ will be a circuit; if G_{s−1} ≠ ∅, then τ will be a bi-infinite path with both ends in G_{s−1}.

If C is the bounded cancellation constant for f^{K}, then γ′ = f_{#}^{K}(γ) contains a subpath γ′_{0} that is obtained from [f^{K}(γ_{1})] by removing at most C initial edges and at most C terminal edges. Let γ′_{2} be the subpath of γ′ that is obtained from γ′_{0} by adding 2C initial edges and 2C terminal edges. We claim that f_{#}^{K}(N(γ_{1})) ⊃ N(γ′_{2}).

To see this, it is convenient to work in the universal cover Γ. Choose lifts f̃^{k} : Γ → Γ, γ̃_{1} ⊂ γ̃ and γ̃′_{0} ⊂ γ̃′_{2} ⊂ γ̃′ = f̃_{#}^{k}(γ̃). Given β′ ∈ N(γ′_{2}), choose a lift β̃′ that contains γ̃′_{2}. There is a unique bi-infinite path β̃ ⊂ Γ such that f̃_{#}^{K}(β̃) = β̃′. Let σ̃ ⊂ Γ be the bi-infinite path connecting the forward end of γ̃ to the forward end of β̃. Then σ̃′ = f̃_{#}^{K}(σ̃) is the bi- infinite path connecting the forward end of γ̃′ to the forward end to β̃′. In particular, σ̃′ is disjoint from γ̃′_{2}. The bounded cancellation lemma therefore implies that f̃^{K}(σ̃) is disjoint from f̃^{K}(γ̃_{1}) and hence that σ̃ is disjoint from γ̃_{1}. A symmetric argument on the backward ends implies that β̃ ⊂ N(γ_{1}) as claimed.

There is a uniform bound to the difference between the number of H_{s}- illegal turns in [f^{K}(γ_{1})] and in γ′_{2}. If γ_{1} contains m illegal turns in H_{s} and m is sufficiently large, say m > M, then by the first step, γ′_{2} contains fewer than m illegal turns in H_{s}. Iterating this, we conclude that for any γ_{1}, there exists k and a finite subpath γ̂_{2} ⊂ γ̂ = f_{#}^{k}(γ) such that f_{#}^{k}(N(γ_{1})) ⊃ N(γ̂_{2}) and such that γ̂_{2} contains at most M illegal turns in H_{s}. Lemma 5.4 and Corollary 5.6 imply that there is a uniform bound to the number of H_{s}-edges in γ̂_{2}. If G_{s−1} = ∅, then extend γ̂_{2} to a circuit τ that crosses each edge at most one more time than γ̂_{2} does. If G_{s−1} ≠ ∅, then extend γ̂_{2} to a biinfinite path τ that crosses an H_{s} edge at most two more times than γ̂_{2} does. Since f_{#}^{k}(N(γ_{1})) = O_{#}^{k}(N(γ_{1})), we have shown that O_{#}^{−k}(τ) ∈ O_{#}^{−k}(N(γ̂_{2})) ⊂ N(γ_{1}). This completes the second step.

Let f′ : G′ → G′ be an improved relative train track map representing O^{−1} such that F(G_{s−1}) is realized by a filtration element. For the final step, we consider first the case that G_{s−1} ≠ ∅. Since F(Λ^{−}) = F(Λ^{+}) is not carried by F(G_{s−1}) and since there are no O^{−1}- invariant free factor systems between F(G_{s−1}) and [[F_{n}]], Λ_{s}^{−} is associated to the highest stratum H′_{s′} and F(G′_{s′−1}) = F(G_{s−1}). Choose a homotopy equivalence h : G → G′ that respects the markings and so induces the natural identification of B(G) with B(G′). Since F(G′_{s′−1}) = F(G_{s−1}), there is a uniform bound to the number of H′_{s′} edges in h_{#}(α) for any path α ⊂ G_{s−1}. Let γ′ = h_{#}(γ) ⊂ G′. Given a finite subpath γ′_{1} ⊂ γ′, choose a finite subpath γ_{1} ⊂ γ such that h_{#}(N(γ_{1})) ⊂ N(γ′_{1}). By the second step, there exists τ and k for γ_{1} as above so that O_{#}^{−k}(τ) ⊂ N(γ_{1}). Let τ′ = h_{#}(τ) and note that there is a uniform bound, say M′, for the number of H′_{s′}-edges in τ′. Then (f′)_{#}^{k}(τ′) = O_{#}^{−k}h_{#}(τ) = h_{#}O_{#}^{−k}(τ) ∈ N(γ′_{1}), or equivalently γ′_{1} is a subpath of (f′)_{#}^{k}(τ′).

Let δ′_{0} ⊂ γ′ be any finite subpath that crosses an edge in H′_{s′}. Choose a finite subpath γ′_{1} ⊂ γ that contains at least 2M′ copies of δ′_{0} and let k and τ′ be as in the preceding paragraph. At least one of the copies of δ′_{0} must be contained in (f′)^{k}(E′) where E′ is a single edge of H′_{s} in τ′. This implies that δ′_{0} is contained in every generic leaf of Λ^{−}. Since δ′_{0} was arbitrary, γ′ is a leaf of Λ^{−}. Since γ′ is birecurrent and is not contained in G′_{s′−1}, Proposition 4.3 implies that γ′ is a generic leaf of Λ_{s}^{−}. Since γ ⊂ G and γ′ ⊂ G′ determine the same line in B, γ is a generic leaf of Λ_{s}^{−}.

It remains to consider the case that G_{s−1} = ∅. As there are only finitely many possibilities for τ, we may assume that τ is independent of γ_{1}. Choose h : G → G′ that respects the markings, let γ′ = h_{#}(γ), let τ′ = h_{#}(τ) and let M′ be the number of edges in τ′. For any finite subpath δ′_{0} ⊂ γ′, there is a finite subpath γ′_{1} ⊂ γ′ that contains at least 2M′ copies of δ′_{0}.

It is useful to distinguish between the circuit O_{#}^{−k}(τ′) ⊂ G′ and the repeating bi-infinite path T′_{k} ⊂ G′ that it determines. If O_{#}^{−k}(τ′) takes on only finitely many values, then γ must be a circuit that is invariant under the action of some iterate of O. In this case, the number of illegal turns of O_{#}^{−m}(γ) is eventually constant in contradiction to the first step in the proof. Thus the number of edges in O_{#}^{−k}(τ′) tends to ∞ as k tends to ∞. It follows that for sufficiently large k, γ′_{1} is a subpath of T′_{k} that intersects at most two fundamental domains. In particular γ′_{1} is contained in a subpath of T′_{k} that is a concatenation of at most 2M′ segments, each of which is a subset of (f′)^{k}(E′) for a single edge E′ of G′. The proof now concludes as in the previous case.

The following corollary will be strengthened at the end of the section after we complete the proof of Theorem 7.1. This partial result is used in the proof of Theorem 7.1.

Corollary 7.7. Suppose that f : G → G is an improved relative train track map representing O, that Λ^{+} ∈ L(O) is associated to the exponentially growing stratum H_{s} and that Λ^{−} ∈ L(O^{−1}) is paired with Λ^{+}. If γ ⊂ G_{s} is a bi-infinite path that is not a generic leaf of either Λ^{+} or Λ^{−}, then γ is weakly attracted to Λ^{+} under the action of O if and only if γ is weakly attracted to Λ^{−} under the action of O^{−1}.

Proof of Corollary 7.7 We may assume that G = G_{s}, and, after passing to an iterate if necessary, that f : G → G represents O and that there is an improved relative train track map f′ : G′ → G′ for O^{−1} such that F(G_{s−1}) is realized by a filtration element. Since F(Λ^{−}) = F(Λ^{+}) is not carried by F(G_{s−1}) and since there are no O^{−1}- invariant free factor systems between F(G_{s−1}) and [[F_{n}]], Λ^{−} is associated to the highest stratum H′_{s′} and F(G′_{s′−1}) = F(G_{s−1}). If γ is carried by F(G_{s−1}) = F(G′_{s′−1}) or if γ is an Oinvariant circuit, then γ is not weakly attracted to either Λ^{+} or Λ^{−}. In all other cases, Proposition 7.6 implies that γ is weakly attracted to both Γ^{+} and Γ^{−}.

Lemma 7.8. Suppose that Z is the subgraph of Proposition 7.4. Then the set of bi-infinite elements in < Z, ρ_{r} > determines a closed subset of B_{G}.

Proof of Lemma 7.8 A (not necessarily finite) path σ ∈< Z, ρ_{r} > has a locally defined canonical decomposition into subpaths in < Z, ρ_{r} >. More precisely, suppose that σ = … a_{i}a_{i+1}a_{i+2} … is the decomposition into single edges of G. The a_{i}’s can be grouped into subpaths b_{j} that are either single edges in Z or ρ_{r} or ρ̄_{r}. The b_{j}’s are uniquely determined by the following rule. If (ā_{i}, a_{i+1}) is an illegal turn in H_{r}, then (ā_{i}, a_{i+1}) is the illegal turn in either ρ_{r} or ρ̄_{r}, and a_{i}, a_{i+1} and some adjacent edges are grouped into a b_{j} that is ρ_{r} or ρ̄_{r} respectively. All edges not so grouped, are in Z and determine b_{j}’s. Let M be the number of edges in ρ_{r}. Then the endpoints of the b_{j}’s are separated by at most M edges and the subpath a_{i−M} ⋯ a_{i+M} determines whether or not the endpoint shared by a_{i} and a_{i+1} is an endpoint of some b_{j}. We say that the endpoints of the b_{j}’s are cutting vertices for σ. Any subpath of σ that is bounded by cutting vertices is contained in < Z, ρ_{r} >.

Suppose that μ_{i} → γ in B_{G} and that μ_{i} ∈< Z, ρ_{r} >. Write γ as an increasing union of finite subpaths γ_{i}. After passing to a subsequence, we may assume that γ_{i} is a subpath of μ_{i}. There is a common subpath of μ_{i} and γ_{i} that is bounded by cutting vertices in μ_{i} and that covers all of γ_{i} with the exception of at most M edges at the beginning and end. Thus γ can be written as an increasing union of subpaths in < Z, ρ_{r} >. The canonical decompositions of these subpaths agree on their overlap so γ ∈< Z, ρ_{r} >.

Corollary 7.9. If Λ^{−} ∈ L(O^{−1}) is paired with a topmost lamination Λ^{+} ∈ L(O), then Λ^{−} is topmost.

Proof of Corollary 7.9 Choose an improved relative train track map f : G → G representing an iterate of O, let H_{r} be the exponentially growing stratum that determines Λ^{+} and let Z be the subgraph of Proposition 7.4. Suppose that Λ_{s}^{+} and Λ_{s}^{−} are paired laminations associated to an exponentially growing stratum H_{s} with s > r. Conditions (2) and (3) of Proposition 7.4 imply that each generic leaf γ of Λ_{s}^{+} is contained in < Z ∩ G_{s}, ρ_{r} >. Choose an H_{s}-edge E that occurs infinitely often (counting orientation) in γ. Choose a subpath γ_{0} ⊂ γ that starts at an occurrence of E and ends just before an occurrence of E. Then γ_{0} is an s-legal circuit that is contained in < Z ∩G_{s}, ρ_{r} > (because the endpoints of γ_{0} are cutting vertices). Lemma 5.3 and Corollary 5.6 imply that γ_{0} is weakly attracted to Λ_{s}^{+} under the action of O. Remark 4.2 and Corollary 7.7 therefore imply that γ_{0} is weakly attracted to Λ_{s}^{−} under the action of O^{−1}. Lemma 7.5 implies that the set of bi-infinite paths in < Z ∩ G_{s}, ρ_{r} > is O^{−1}-invariant. Lemma 7.8 therefore implies that each generic leaf of Λ_{s}^{−} is contained in < Z, ρ_{r} >. On the other hand, the bi-infinite paths of < Z ∩ G_{r}, ρ_{r} > differ from the bi-infinite paths of G_{r−1} in at most a circuit, so < Z, ρ_{r} > does not contain any generic leaves of Λ^{−}. We conclude that a generic leaf of Λ^{−} is not contained in the closure of a generic leaf of Λ_{s}^{−} and hence that Λ^{−} is topmost.

Proof of Theorem 7.1 Let f : G → G, O, H_{r} and Z be as in Proposition 7.4.

If a generic leaf of Λ^{−} is weakly attracted to Λ^{+}, then Λ^{−} (being closed and O-invariant) would contain Λ^{+}. Lemma 4.3 implies that a birecurrent leaf of Λ^{−} is either carried by a strictly smaller free factor system than F(Λ^{−}) or is generic. Since F(Λ^{+}) = F(Λ^{−}), each generic leaf of Λ^{+} would be a generic leaf of Λ^{−} and so Λ^{+} = Λ^{−}. This contradicts Proposition 4.8 and thereby shows that (1) and (3) are mutually exclusive. Since the bi-infinite paths of < G_{r−1}, ρ_{r} > and the bi-infinite paths of G_{r−1} differ by at most a peripheral curve, (1) and (2) are mutually exclusive. If γ ∈< Z, ρ_{r} >, then O_{#}^{k}(γ) ∈< Z, ρ_{r} > for all k > 0. Since there is a uniform bound to the number of H_{r}-edges in an r-legal path in < Z, ρ_{r} >, γ is not weakly attracted to Λ^{+}. We have now shown that (1), (2) and (3) are mutually exclusive.

Let s be the smallest parameter value for which γ ⊂ G_{s}. Since G_{r−1} ⊂ Z we may assume that s ≥ r. The s = r case is proved by Proposition 7.6.

Suppose that s > r. If γ splits into finite paths whose endpoints are fixed by f, then Proposition 7.4 completes the proof. We may therefore assume (Lemma 5.2) that H_{s} is exponentially growing and that γ ∉< G_{s−1}, ρ_{s} >. Let Λ_{s}^{+} and Λ_{s}^{−} be the lamination pair associated to H_{s}. During the proof of Corollary 7.9 we showed that each generic leaf of Λ_{s}^{−} is contained in < Z, ρ_{r} >. We may therefore assume that γ is not a generic leaf of Λ_{s}^{−} and hence, by Proposition 7.6, is weakly attracted to Λ_{s}^{+}. As in the proof of Proposition 7.4, Lemma 7.5 allows us to replace γ by any [f_{#}^{k}(γ)]. We may therefore assume that γ contains subpaths of a generic leaf λ of Λ_{s}^{+} with arbitrarily many H_{s}-edges. Since f maps the set of endpoints of edges in H_{s} into itself, at least one of the vertices is the image of a vertex and is therefore a fixed point. Lemma 5.4 and birecurrence imply that γ has a splitting into finite paths whose endpoints are fixed by f and again Proposition 7.4 completes the proof.

Corollary 7.10. If Λ^{+} ∈ L(O) and Λ^{−} ∈ L(O^{−1}) are paired topmost expanding laminations and γ is a bi-recurrent path that is not a generic leaf of either Λ^{+} or Λ^{−}, then γ is weakly attracted to Λ^{+} under the action of O if and only if γ is weakly attracted to Λ^{−} under the action of O^{−1}.

Proof of Corollary 7.10 Choose an improved relative train track map f : G → G representing an iterate of O, let H_{r} be the exponentially growing stratum that determines Λ^{+} and let Z be as in Proposition 7.1. If γ is not weakly attracted to Λ^{+} under the action of O, then the same is true for all O_{#}^{−k}(γ) and so O_{#}^{−k}(γ) ∈< Z, ρ_{r} > for all k ≥ 0. Lemma 7.8 and the fact that generic leaves of Λ^{−} are not contained in < Z, ρ_{r} > imply that γ is not weakly attracted to Λ^{−} under the action of O^{−1}. The symmetric argument with the roles of Λ^{+} and Λ^{−} reversed completes the proof.

8 Reduction to PG(F_{n})

In this section we reduce the Tits Alternative for Out(F_{n}) to the Tits Alternative for PG(F_{n}). More precisely, we prove the following theorem.

Theorem 8.1. If H ⊂ Out(F_{n}) does not contain a free subgroup of rank two, then there exists k ≥ 0 and a homomorphism Φ : H → ℤ^{k} with Ker(Φ) ⊂ PG(F_{n}).

Remark 8.2. By Remark 4.12, Theorem 8.1 can be strengthened by replacing the assumption that H does not contain a free subgroup of rank two with the assumption that H satisfies the WEF property; i.e. it does not contain a free subgroup of rank two, each of whose non-trivial elements has exponential growth.

We begin by using the Weak Attraction Theorem and Corollary 4.13 to analyze the stabilizers of topmost laminations.

Proposition 8.3. Suppose that H is a subgroup of Out(F_{n}), that O ∈ H is eg-aperiodic and that Λ^{+} ∈ L(O) and Λ^{−} ∈ L(O^{−1}) are paired topmost laminations. Then either H contains a free subgroup of rank two, or at least one of the subgroups, Stab_{H}(Λ^{+}) or Stab_{H}(Λ^{−}), has finite index.

The proof of Proposition 8.3 reduces to the following technical lemma. Before proving the lemma, we use it to prove the proposition.

Lemma 8.4. Suppose that H is a subgroup of Out(F_{n}), that O ∈ H is egaperiodic, that Λ^{+} ∈ L(O) and Λ^{−} ∈ L(O^{−1}) are paired topmost laminations with generic leaves λ^{+} and λ^{−} respectively and that f : G → G is an improved relative train track map representing O such that F(Λ^{+}) = F(Λ^{−}) = F(G_{r}) for some filtration element G_{r}. Let Z and ρ_{r} be as in Theorem 7.1. Then H has a finite index subgroup H_{0} such that ψ(λ^{+}), ψ(λ^{−}) ∉< Z, ρ_{r} > for each ψ ∈ H_{0}.

Proof of Proposition 8.3 By Theorem 6.4 there is an iterate of O such that F(Λ^{+}) = F(Λ^{−}) = F(G_{r}) for some filtration element G_{r}. Let H_{0} be the finite index subgroup of Lemma 8.4 and let ψ ∈ H_{0}. Theorem 7.1 and Corollary 7.10 imply that either ψ(λ^{+}) is a generic leaf of Λ^{±} or ψ(λ^{+}) is weakly attracted to Λ^{+} under the action of O and to Λ^{−} under the action of O^{−1}. The same statement holds for ψ(λ^{−}). Thus, each ψ ∈ H_{0} satisfies one of the following two conditions.

1. The four laminations ψ(Λ^{+}), ψ(Λ^{−}), Λ^{+} and Λ^{−} are not all distinct.

2. ψ(λ^{+}) and ψ(λ^{−}) are weakly attracted to Λ^{+} under the action of O and to Λ^{−} under the action of O^{−1}

Condition (1) either holds for both ψ and ψ^{−1} or fails for both ψ and ψ^{−1}. Moreover, if condition (2) holds for both ψ and ψ^{−1}, then ψ satisfies the hypothesis of Corollary 4.13. Thus either condition (1) holds for all ψ ∈ H_{0}, or the hypothesis of Corollary 4.13 are satisfied for some ψ ∈ H_{0}. In the former case, Lemma 8.5 below implies that either Stab_{H_{′}}(Λ^{+}) or Stab_{H_{0}}(Λ^{−}) has finite index. In the latter case, Corollary 4.13 implies that H contains a free subgroup of rank two.

Lemma 8.5. Suppose that a group H acts on a set Y and that there are points x, y ∈ Y such that

(*) {ψ(x), ψ(y)} ∩ {x, y} ≠ ∅

holds for all ψ ∈ H. Then either Stab_{H}(x) or Stab_{H}(y) has finite index.

Proof of Lemma 8.5 If Stab_{H}(x) does not have finite index, then there exist h_{i} ∈ H, i ≥ 1, such that the h_{i}(x)’s are all distinct; we may assume without loss that h_{i}(x) ∉ {x, y}. Condition (∗) implies that each h_{i}(y) is either x or y. Passing to a subsequence, we may assume that either each h_{i}(y) = x or each h_{i}(y) = y. In the former case, each h_{1}h_{i}(y) ∉ {x, y} and there are at most two values of i for which h_{1}h_{i}(x) ∈ {x, y}. This contradicts (∗) and we conclude that each h_{i}(y) = y.

By a completely symmetric argument, we conclude that if Stab_{H}(y) does not have finite index, then there exist g_{j} ∈ H, j ≥ 1, such that the g_{j}(y)’s are distinct elements of X \ {x, y} and such that each g_{j}(x) = x.

But then each g_{1}h_{i}(y) = g_{1}(y) ∉ {x, y} and there are at most two values of i for which g_{1}h_{i}(x) ∈ {x, y}. This contradicts (∗) and completes the proof.

The proof of Lemma 8.4 divides into the geometric and non-geometric cases. We consider the non- geometric case first.

If G̃ is a cover of G and X is a subgraph of G, then we denote the full pre-image of X by X̃. We denote Euler characteristic by χ.

Lemma 8.6. Suppose that f : G → G is an improved relative train track map and that F(Λ^{+}) = F(G_{r}). Then there exists k > 0 and there is a regular connected k-fold cover G̃ such Rank(H_{1}(G̃_{r})) > Rank(H_{1}(G̃_{r−1})) + k. Moreover, every outer automorphism of F_{n} ≅ π_{1}(G) lifts to an outer automorphism of π_{1}(G̃).

Proof of Lemma 8.6 Let Q_{r−1} be the union of the non-contractible components of H_{r−1}; thus Q_{r−1} = G_{r−2} if H_{r−1} is a zero stratum and Q_{r−1} = G_{r−1} otherwise. In either case, H_{1}(Q_{r−1}) = H_{1}(G_{r−1}). We may assume that Rank(H_{1}(G_{r})) ≤ Rank(H_{1}(G_{r−1})) + 1. Let m = Rank(H_{0}(Q_{r−1})) be the number of components in Q_{r−1}. Since F(G_{r}) = F(Λ^{+}), G_{r} is connected and H_{r} is an exponentially growing stratum. Lemma 4.5 therefore implies that either m ≥ 3 or Rank(H_{1}(G_{r})) = Rank(H_{1}(Q_{r−1})) + 1 and m = 2.

Choose k_{1} > m and connected k_{1}-fold covering spaces for each component of Q_{r−1}. Extend this to a k_{1}-fold covering space Ĝ of G. The key point here is that, independently of k_{1}, the full pre-image Q̂_{r−1} of Q_{r−1} has m components.

F_{n} has only finitely many subgroups of index k_{1}, so the intersection N of all such subgroups is a normal subgroup of finite index. Let k be the index of N, let G̃ be the regular connected k-fold cover of G corresponding to N, and let k_{2} be the integer \frac{k}{k_{1}} . Then G̃ is a k_{2}-fold cover of Ĝ and Q̃_{r−1} has at most k_{2}m components. It is easy to see that for all O ∈ Out(F_{n}), N is invariant under the action induced by O on normal subgroups. In particular, every outer automorphism of π_{1}(G) lifts to an outer automorphism of π_{1}(G̃). We say that N is characteristic.

To verify the conclusions of the lemma, note that Rank(H_{1}(G̃_{i})) = k × Rank(H_{1}(G_{i})) − k × Rank(H_{0}(G_{i})) + Rank(H_{0}(G̃_{i})). (This follows from χ = Rank(H_{0}) − Rank(H_{1}) and χ(G̃_{i}) = k × χ(G_{i})). Thus,

Rank(H_{1}(G̃_{r})) − Rank(H_{1}(G̃_{r−1})) =
Rank(H_{1}(G̃_{r})) − Rank(H_{1}(Q̃_{r−1})) =

k×[Rank(H_{1}(G_{r}))−Rank(H_{1}(Q_{r−1}))]+k×[Rank(H_{0}(Q_{r−1}))−Rank(H_{0}(G_{r}))]

+[Rank(H_{0}(G̃_{r})) − Rank(H_{0}(Q̃_{r−1}))]
≥ k × [Rank(H_{1}(G_{r})) − Rank(H_{1}(Q_{r−1}))] + k(m − 1) + (1 − mk_{2})
= k × [Rank(H_{1}(G_{r})) − Rank(H_{1}(Q_{r−1}))] + k[m − 1 + \frac{1}{k} − \frac{m}{k_{1}}].

Since m ≥ 2 and k_{1} > m, both terms are non-negative. If m ≥ 3, then the second term is strictly larger than k. If m = 2, then the first term equals k and the second term is positive.

Proof of Lemma 8.4 in the non-geometric case Let G̃ be a k-fold cover of G as in Lemma 8.6 and let ρ̃_{r}^{1}, …, ρ̃_{r}^{k} ⊂ G̃ be the lifts of ρ_{r}. Define H_{0} ⊂ H to be the finite index subgroup of elements whose lifts to π_{1}(G̃) act by the identity on H_{1}(G̃; ℤ_{2}). If β is a circuit in < G_{r−1}, ρ_{r} > that lifts to a circuit β̃ in G̃, then β̃ can be decomposed into subpaths that are either single edges in G̃_{r−1}, some ρ̃_{r}^{i} or the inverse of some ρ̃_{r}^{i}. In particular, the ℤ_{2}-homology classes generated by all such β̃ are contained in a subspace of H_{1}(G̃_{r}; ℤ_{2}) of dimension at most Rank(H_{1}(G̃_{r−1})) + k. Lemma 8.6 implies that there is a circuit α̃ ⊂ G̃_{r} whose ℤ_{2}-homology class is not represented by a lift of a circuit in < G_{r−1}, ρ_{r} >. Since Z̃ ∩ G̃_{r} = G̃_{r−1}, the ℤ_{2}-homology class of α̃ is not represented by a lift of a circuit in < Z, ρ_{r} >. Let α ⊂ G_{r} be the projected image of α̃. For each ψ ∈ H_{0}, the ℤ_{2}-homology class determined by ψ̃_{#}(α̃) can not be represented by the lift of a circuit in < Z, ρ_{r} >, so ψ_{#}(α) ∉< Z, ρ_{r} >. Since ψ_{#}(F(G_{r})) = F(ψ_{#}(λ^{+})) = F (ψ_{#}(λ^{−})), every free factor system that contains ψ_{#}(λ^{+}) or ψ_{#}(λ^{−}) must contain ψ_{#}(α) for every circuit α ⊂ G_{r}. Lemma 6.7 therefore implies that ψ_{#}(λ^{+}) ∉< Z, ρ_{r} > and ψ_{#}(λ^{−}) ∉< Z, ρ_{r} >.

We now turn to the proof of Lemma 8.4 in the case that H_{r} is a geometric stratum.

Suppose that μ ⊂ G is a bi-infinite path and that α ⊂ G is a circuit. Choose a lift α̃ of α in the universal cover Γ of G and let T : Γ → Γ be the indivisible covering translation with axis equal to α̃. We say that α is in the span of μ if for all positive integers L, there are lifts μ̃_{i} of μ, 0 ≤ i ≤ m − 1, such that

(Sp) μ̃_{0} ∩ μ̃_{1}, μ̃_{1} ∩ μ̃_{2}, …, μ̃_{m−2} ∩ μ̃_{m−1} and μ̃_{m−1} ∩ T (μ̃_{0}) each contain at least L edges.

Lemma 8.7. Suppose that f : G → G , Z and ρ_{r} are as in Theorem 7.1. If μ ∈< Z, ρ_{r} > and α ⊂ G is in the span of μ, then α ∈< Z, ρ_{r} >.

Proof of Lemma 8.7. Write μ̃ = … b̃_{−1}b̃_{0}b̃_{1} … where each b_{j} is either a single edge of Z or is equal to ρ or ρ̄. We do not assume a priori that this is a decomposition into subpaths, but there is no loss in assuming that b_{j} ≠ b̄_{j}. Since the initial edges of ρ and of ρ̄ lie in H_{r} and are distinct, no cancellation can occur at the juncture of b̃_{j}’s and b̃_{j+1}; we conclude that the b̃_{j}s are subpaths of μ̃.

Let M be the number of edges in ρ_{r}. Choose μ̃_{i} satisfying (Sp) with L = M; denote T (μ̃_{0}) by μ̃_{m}. Since μ̃_{i−1} ∩ μ̃_{i}, 1 ≤ i ≤ m, contains at least M edges, there is a vertex p_{i} ∈ μ̃_{i−1} ∩ μ̃_{i} that is a cutting vertex (see the proof of Lemma 7.8) for both μ̃_{i−1} and μ̃_{i}. For 1 ≤ i ≤ m − 1, let γ̃_{i} be the subpath of μ̃_{i} that is bounded by p̃_{i} and p̃_{i+1}. Let γ̃_{m} be the subpath of μ̃_{m} that is bounded by p̃_{m} and T (p̃_{1}). Then each γ_{i} ⊂< Z, ρ > and α is the circuit obtained by tightening γ_{1} · · · · · γ_{m}.

Let ϕ : S → S and Φ : Y → G_{r} be as in the definition of geometric stratum. For each closed geodesic curve α_{S} ⊂ S, we say that Φ_{#}(α_{S}) ⊂ G_{r} is an H_{r}-geometric circuit.

Lemma 8.8. If H_{r} is a geometric stratum with generic leaves λ^{±}, then every H_{r}-geometric circuit in G_{r} is in the span of λ^{+} and in the span of λ^{−}.

Proof of Lemma 8.8 It suffices to consider λ^{+}. Suppose that an H_{r}- geometric circuit α and length L are given. Let λ_{S}^{+} and α_{S} be the geodesics is S such that Φ_{#}(λ_{S}^{+}) = λ^{+} and Φ_{#}(α_{S}) = α^{+}. We showed during the proof of Proposition 7.6 that λ_{S}^{+} is a generic leaf of the expanding lamination Λ_{S}^{+} for ϕ. There exists ϵ > 0 and a length L_{S} so that if a pair of lifts of λ_{S}^{+} to the universal cover of S contain ϵ-parallel subintervals of length L_{S}, then their Φ_{#}-images in the universal cover Γ of G have a common subinterval that contains at least L edges. There exists δ > 0 so that any two lifts of λ_{S}^{+} that have points within δ of each other, have ϵ-parallel subintervals of length L_{S}. The lemma now follows from the well known fact that α_{S} is freely homotopic to a closed curve of the form u_{0} · s_{0} · u_{1} · s_{1} · · · · · u_{k−1} · s_{k−1} where each u_{i} is an interval in λ_{S}^{+} and where each s_{i} has length at most δ. (To prove this well known fact, note that for sufficiently small δ, the complement S \ N_{δ}(Λ_{S}^{+}) of the δ neighborhood of the expanding lamination Λ_{S}^{+} in S is a finite disjoint union of contractible or peripheral sets. The circuit α_{S} can therefore be homotoped into N_{δ}(Λ_{S}^{+}) and then further homotoped to have the desired decomposition into subpaths.)

Corollary 8.9. Suppose that f : G → G , Z and ρ_{r} are as in Theorem 7.1, that H_{r} is a geometric stratum with generic leaves λ^{±} and that ψ ∈ Out(F_{n}). If ψ_{#}(λ^{+}) ∈< Z, ρ_{r} > or ψ_{#}(λ^{−}) ∈< Z, ρ_{r} >, then ψ_{#}(α) ∈< Z, ρ_{r} > for each H_{r}-geometric circuit α ⊂ G_{r}.

Proof of Corollary 8.9 Let h̃ : Γ → Γ be a lift of a topological representative h : G → G representing ψ. For all L, there exists L_{1} so that if β̃ ⊂ Γ is a path with edge length at least L_{1}, then [h̃(β̃)] is a path with edge length at least L. If C is the constant of the bounded cancellation lemma applied to h̃ : Γ → Γ, and if μ̃_{1} and μ̃_{2} are bi-infinite paths such that μ̃_{1} ∩ μ̃_{2} has edge length at least L_{1}, then h̃_{#}(μ̃_{1}) ∩ h̃_{#}(μ̃_{2}) has edge length at least L − 2C.

By Lemma 8.8, α is in the span of λ^{+} and in the span of λ^{−}. The preceding argument shows that ψ_{#}(α) is in the span of ψ_{#}(λ^{+}) and in the span of ψ_{#}(λ^{−}). Lemma 8.7 now completes the proof.

Assume the notation of Definition 6.3. The following lemma is a modification of Lemma 8.6. Let ∂_{A}S be the union of the components α_{1}^{∗}, …, α_{m}^{∗} of ∂S. Every regular cover G̃ of G determines a regular cover S̃ of S; we denote the full pre-image of ∂_{A}S by ∂_{A}S̃.

Lemma 8.10. If H_{r} is a geometric stratum, then there is a regular connected k-fold cover G̃ such that the induced cover S̃ of S satisfies Rank(H_{1}(S̃))−Rank(H_{1}(∂_{A}S̃)) > k. Moreover, every outer automorphism of F_{n} ≅ π_{1}(G) lifts to an outer automorphism of π_{1}(G̃).

Proof of Lemma 8.10 If S is S^{2} with m+1 disks removed, then Rank(H_{1}(S))− Rank(H_{1}(∂_{A}S)) = 0. If S is a Mobius band with m disks removed, then Rank(H_{1}(S)) −Rank(H_{1}(∂_{A}S)) = 1. In all other cases, Rank(H_{1}(S))−Rank(H_{1}(∂_{A}S)) ≥ 2 and we may choose k = 1 and G̃ = G. Since S supports a pseudo-Anosov homeomorphism, m ≥ 2 and m = 2 only if S is a Mobius band with 2 disks removed. (This last fact is well known; it follows from Lemma 4.5 and the fact that if S is S^{2} with three disks removed or if S is the Mobius band with one disk removed, then S deformation retracts to a one complex made up of ∂_{A}S and one edge.)

Choose elements c_{i} ∈ π_{1}(G), 1 ≤ i ≤ m, whose associated circuit is α_{i}. For j ≥ 1 denote the concatenation of j copies of c_{i} by c_{i}^{j}. Since F_{n} is residually finite, there is a finite index normal subgroup N that does not contain c_{i}^{j} for 1 ≤ i ≤ m and 1 ≤ j ≤ 4, and therefore does not contain any element conjugate to such c_{i}^{j}. If G̃ is the regular connected finite cover of G corresponding to N and if the closed path that goes k times around α_{i} lifts to a closed circuit in G̃, then k ≥ 5. Thus, if q : S̃ → S is the covering space of S induced by G̃, then the restriction of q to any component of ∂_{A}S̃ is at least a five fold cover. It follows that Rank(H_{0}(∂_{A}S̃)) ≤ \frac{k}{5} Rank(H_{0}(∂_{A}S)). As noted in the proof of Lemma 8.6, after passing to a further cover if necessary, we may assume that N is characteristic.

Let m = Rank(H_{0}(∂_{A}S)) be the number of components of ∂_{A}S; since S is connected H_{0}(S) = 1. As in the proof of Lemma 8.6,

Rank(H_{1}(S̃)) − Rank(H_{1}(∂_{A}S̃))

= k×[Rank(H_{1}(S))−Rank(H_{1}(∂_{A}S))]+k×[Rank(H_{0}(∂_{A}S))−Rank(H_{0}(S))]

+[Rank(H_{0}(S̃)) − Rank(H_{0}(˜∂_{A}S))]

≥ k × [Rank(H_{1}(S)) − Rank(H_{1}(∂_{A}S))] + k(m − 1) + (1 − \frac{mk}{5} )

= k × [Rank(H_{1}(S)) − Rank(H_{1}(∂_{A}S))] + k[m − 1 + \frac{1}{k} − \frac{m}{5}].

Both terms are non-negative. If m ≥ 3, then the second term is strictly larger than k. If m = 2, then the first term equals k and the second term is positive.

Proof of Lemma 8.4 in the geometric case The proof is now essentially the same as in the non- geometric case. Let G̃ be a covering space of G as in Lemma 8.10 and let H_{0} be the finite index subgroup of H whose lifts to π_{1}(G̃) act by the identity on H_{1}(G̃; ℤ_{2}). Since ∂S = ∂_{A}S ∪ ρ^{∗}, there are at most k components in ∂S̃ \ ∂_{A}S̃. It is therefore possible to choose a circuit α̃_{S} in S̃ whose ℤ_{2}- homology class is not represented by peripheral curves. The peripheral homology H_{1}(∂_{A}S̃; ℤ_{2}) is a direct summand of the homology H_{1}(S̃; ℤ_{2}); H_{1}(Y; ℤ_{2}) is formed from H_{1}(S̃; ℤ_{2}) ⨁ H_{1}(Q̃; ℤ_{2}) by identifying H_{1}(∂_{A}S̃; ℤ_{2}) with its image in H_{1}(Q̃; ℤ_{2})). It follows that α̃ = Φ̃_{#}(α̃_{S}) determines a non-zero element of H_{1}(G̃_{r}; ℤ_{2}) that is not represented by a lift of a circuit in < G_{r−1}, ρ_{r} > and hence is not represented by a lift of a circuit in < Z, ρ_{r} >. If α is the projection of α̃, then ψ_{#}(α) is not in < Z, ρ_{r} >, and Corollary 8.9 completes the proof.

Lemma 8.11. Assume that H ⊂ Out(F_{n}) does not contain a free subgroup of rank two. Then there is a finite collection L of expanding laminations for elements of H and a finite index subgroup H_{0} of H that stabilizes each element of L with the following feature. If ψ ∈ H_{0} is eg-aperiodic and if Λ^{+} ∈ L(ψ) and Λ^{−} ∈ L(ψ^{−1}) are paired topmost laminations, then at least one of Λ^{+} and Λ^{−} is in L.

Proof of Lemma 8.11 Among all proper free factor systems that are invariant under the action of a finite index subgroup of H, choose one, F_{1}, of maximal complexity. If H_{0} is a finite index subgroup of H that stabilizes F_{1}, then, by induction applied to H_{0}|F_{1}, we may assume that there is a finite collection L_{1} of expanding laminations that are carried by F_{1} and a finite index subgroup (also called) H_{0} that stabilizes each element of L_{1} with the following feature. If ψ ∈ H_{0} is eg-aperiodic and if Λ^{+} ∈ L(ψ) and Λ^{−} ∈ L(ψ^{−1}) are paired topmost laminations that are carried by F_{1}, then either Λ^{+} ∈ L_{1} or Λ^{−} ∈ L_{1}.

If every topmost lamination pair for eg-aperiodic elements of H_{0} is carried by F_{1}, then we are done. Otherwise, choose an eg-aperiodic O ∈ H and a topmost lamination pair Γ^{+} ∈ L(O) and Γ^{−} ∈ L(O) that is not carried by F_{1}. Proposition 8.3 implies, after passing to a smaller finite index subgroup if necessary, that at least one of Γ^{+} or Γ^{−} is stabilized by H_{0}. We assume without loss that Γ^{+} is stabilized by H_{0}; if possible, choose H_{0} to stabilize both Γ^{+} and Γ^{−}. Define L to be the union of L_{1} with Γ^{+} and with Γ^{−} if it is stabilized by H_{0}.

Choose an improved relative train track map f : G → G for some iterate of O such that F_{1} is realized by a filtration element. Since F_{1} and Γ^{+}are both H_{0}-invariant, so is the unique smallest free factor system containing F_{1} and carrying Γ^{+}. Our choice of F_{1} therefore guarantees that this smallest free factor system is F_{n}. It follows that Γ^{+} is associated to the highest stratum G_{r} = G.

Suppose that ψ ∈ H_{0} and that Λ^{+} ∈ L(ψ) and Λ^{−} ∈ L(ψ^{−1}) are paired topmost laminations. If Λ^{±} are carried by F_{1}, then either Λ^{+} ∈ L_{1} ⊂ L or Λ^{−} ∈ L_{1} ⊂ L. Suppose then that Λ^{±} are not carried by F_{1}. Proposition 8.3 implies that either Λ^{+} or Λ^{−}, say Λ^{−}, is stabilized by a finite index subgroup of H_{0}. After replacing f by an iterate if necessary, f_{#} stabilizes Λ^{−}.

Let λ^{−} be a generic leaf of Λ^{−}. Since F_{n} is the only free factor system that contains F_{1} and carries Λ^{−}, λ^{−} ⊄ G_{r−1}. Remark 7.3 therefore implies that either λ^{−} is a leaf of Γ^{−} or λ^{−} is weakly attracted to Γ^{+} under the action of f_{#}. In the former case, Proposition 4.3 implies that λ^{−} is a generic leaf of Γ^{−}, so Λ^{−} = Γ^{−} ∈ L. In the latter case, every subpath of a generic leaf γ^{+} of Γ^{+} is contained in some leaf f_{#}^{m}(λ^{−}) of Λ^{−}, so γ^{+} is a leaf of Λ^{−}. Since F_{n} is the only free factor system that contains F_{1} and carries γ^{+}, Proposition 4.3 implies that γ^{+} is a generic leaf of Λ^{−} and so Γ^{+} = Λ^{−} ∈ L.

Proof of Theorem 8.1 Let L = {Λ_{1}, … Λ_{k}} and H_{0} be as in Lemma 8.11. Define Φ = ⨁ P F_{Λ_{i}^{+}} : H_{0} → Z^{k} where each P F_{Λ_{i}^{+}} is as in Corollary 4.9. If ψ ∈ H_{0} is not in PG(F_{n}), choose (Corollary 4.7) l > 0 so that ψ^{l} is egaperiodic and has paired topmost laminations Γ^{+} ∈ L(ψ^{l}) and Γ^{−} ∈ L(ψ^{−l}). Proposition 4.8 implies that neither P F_{Γ^{+}}(ψ) = \frac{1}{l}P F_{Γ^{+}}(ψ^{l}) nor P F_{Γ^{−}}(ψ) = \frac{1}{l}P F_{Γ^{−}}(ψ^{l}) is zero so Lemma 8.11 implies that ψ ∉ Ker(Φ).

References

[BFH95] M. Bestvina, M. Feighn, and M. Handel, Laminations, trees, and irreducible automorphisms of free groups, preprint, 1995.

[BFH96a] M. Bestvina, M. Feighn, and M. Handel, The Tits Alternative for Out(F_{n}) I: Dynamics of Exponentially Growing Automorphisms, preprint, 1996.

[BFH96b] M. Bestvina, M. Feighn, and M. Handel, The Tits Alternative for Out(F_{n}) II: a Kolchin Theorem, preprint, 1996.

[BFH96c] M. Bestvina, M. Feighn, and M. Handel, The Tits Alternative for Out(F_{n}) III: Solvable Subgroups, preprint, 1996.

[BH92] M. Bestvina and M. Handel, Train tracks and automorphisms of free groups, Ann. Math. 135 (1992), 1–51.

[BH95] M. Bestvina and M. Handel, Train tracks for surface homeomorphisms, Topology 32 (1995), 109–140.

[BL] H. Bass and A. Lubotzky, Linear - central filtrations on groups, preprint.

[BLM83] J.S. Birman, A. Lubotzky, and J. McCarthy, Abelian and solvable subgroups of the mapping class group, Duke Math. J. 50 (1983), 1107–1120.

[Coo87] D. Cooper, Automorphisms of free groups have finitely generated fixed point sets, J. Algebra 111 (1987), 453–456.

[CV86] M. Culler and K. Vogtmann, Moduli of graphs and automorphisms of free groups, Invent. Math. 84 (1986), 91–119.

[FLP79] A. Fathi, F. Laudenbach, and V. Poenaru, Travaux de Thurston sur les surfaces, Asterisque 66 (1979).

[FP92] E. Formanek and C. Procesi, The automorphism group of a free group is not linear, J. Algebra 149 (1992), 494–499.

[GS91] S.M. Gersten and J.R. Stallings, Irreducible outer automorphisms of a free group, Proc. Amer. Math. Soc. 111 (1991), 309–314.

[Iva84] N. Ivanov, Algebraic properties of the Teichmuller modular group, Dokl. Akad. Nauk SSSR 275 (1984), no. 4, 786–789.

[Lus92] M. Lustig, Automorphismen von freien Gruppen, Habilitationsschrift, Bochum, 1992.

[McC85] J. McCarthy, A “Tits Alternative” for subgroups of surface mapping class groups, Trans. AMS 291 (1985), 583–612.

[Pau] F. Paulin, Sur les automorphismes extérieurs des groupes hyperboliques, preprint.

[Sela] Z. Sela, The Nielsen-Thurston classification and automorphisms of the free group I, preprint.

[Selb] Z. Sela, The Nielsen-Thurston classification and automorphisms of the free group II, preprint.

[Sen81] E. Seneta, Non-negative matrices and Markov chains, Springer-Verlag, 1981.

[Ser92] J. P. Serre, Lie Algebras and Lie Groups, Springer-Verlag, 1992.

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

[SW79] G.P. Scott and C.T.C. Wall, Topological methods in group theory, Homological Group Theory (C.T.C. Wall, ed.), Lecture Notes, vol. 36, London Mathematical Society, 1979, pp. 137–203.

[Thu88] W. Thurston, On the geometry and dynamics of diffeomorphisms of surfaces, Bull. AMS 19 (1988), 417–431.

[Tit72] J. Tits, Free subgroups in linear groups, J. Algebra 20 (1972), 250–270.