The Tits Alternative for Out(F_{n}) II: A Kolchin Type Theorem

Mladen Bestvina, Mark Feighn, and Michael Handel

July 4, 1996 preliminary version

Contents

1 Introduction and Outline 2

2 F_{n}-Trees 7 2.1 Very small trees . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Bounded cancellation constants . . . . . . . . . . . . . . . . . 8 2.3 Free factor systems . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4 A chain bound for vertex systems . . . . . . . . . . . . . . . . 12

3 Unipotent polynomially growing outer automorphisms 15 3.1 Unipotent linear maps . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Relative train tracks . . . . . . . . . . . . . . . . . . . . . . . 17 3.3 Unipotent representatives . . . . . . . . . . . . . . . . . . . . 18

4 The dynamics of UP G automorphisms 20 4.1 Polynomial sequences . . . . . . . . . . . . . . . . . . . . . . . 20 4.2 Suffixes and eigenrays . . . . . . . . . . . . . . . . . . . . . . . 24 4.3 Primitive subgroups . . . . . . . . . . . . . . . . . . . . . . . . 26 4.4 UP G automorphisms and trees . . . . . . . . . . . . . . . . . 29

5 A Kolchin Theorem for UP G automorphisms 32 5.1 Bouncing sequences . . . . . . . . . . . . . . . . . . . . . . . . 32 5.2 Bouncing sequences grow at most linearly . . . . . . . . . . . 34 5.3 Bouncing sequences stop growing . . . . . . . . . . . . . . . . 36 5.4 Edge stabilizers are eventually trivial . . . . . . . . . . . . . . 37 5.5 Finding Nielsen pairs . . . . . . . . . . . . . . . . . . . . . . . 38 5.6 Distances between the vertices . . . . . . . . . . . . . . . . . . 44 5.7 Proof of Theorem 5.5 . . . . . . . . . . . . . . . . . . . . . . . 46

6 Proof of the main theorem 46

1 Introduction and Outline

Recent years have seen a development of the theory for Out(F_{n}), the outer automorphism group of the free group F_{n} of rank n, that is modelled on Nielsen-Thurston theory for surface homeomorphisms. As mapping classes have either exponential or linear growth rates, so free group outer automorphisms have either exponential or polynomial growth rates. (The degree of the polynomial can be any integer between 1 and n − 1, see [BH92].) In [BFH96a] we considered individual automorphisms, with primary emphasis on those with exponential growth rates. In this paper we focus on subgroups of Out(F_{n}), all of whose elements have polynomial growth rates.

To remove certain technicalities arising from finite order phenomena, we restrict our attention to those polynomially growing outer automorphisms O whose induced automorphism of H_{1}(F_{n}; ℤ) ≅ ℤ^{n} is unipotent. We say that such an outer automorphism is unipotent; we also say that O is a UP G(F_{n}) (or just a UP G) outer automorphism. A subgroup of Out(F_{n}) is called a UP G subgroup if each element is UP G. We prove (Proposition 3.5) that any polynomially growing outer automorphism that acts trivially in ℤ/3ℤhomology is unipotent. Thus every subgroup of polynomially growing outer automorphisms has a finite index UP G subgroup.

The archetype for the main theorem of this paper comes from linear groups. A linear map is unipotent if and only if it has a basis with respect to which it is upper triangular with 1’s on the diagonal. A celebrated theorem of Kolchin [Ser92] states that for any group of unipotent linear maps there is a basis with respect to which all elements of the group are upper triangular with 1’s on the diagonal.

There is an analagous result for mapping class groups. We say that a mapping class is unipotent if it has linear growth and if the induced linear map on first homology is unipotent. The Thurston classification theorem implies that a mapping class is unipotent if and only if it is represented by a composition of Dehn twists in disjoint simple closed curves. Moreover, if a pair of unipotent mapping classes belong to a unipotent subgroup, then their twisting curves can not have transverse intersections (see for example [BLM83]). Thus every unipotent mapping class subgroup has a characteristic set of disjoint simple closed curves and each element of the subgroup is a composition of Dehn twists along these curves. As in the linear case, in which the basis does not depend on the individual linear maps in a the unipotent subgroup, here the twisting curves do not depend on the individual mapping classes.

Our main theorem is the analogue of Kolchin’s theorem for Out(F_{n}). Recall [CV86] that a marked graph is a graph (1-dimensional CW-complex) equipped with a homotopy equivalence from the rose with n petals (whose fundamental group is permanently identified with F_{n}). A homotopy equivance f : G → G on a marked graph G induces an outer automorphism of the fundamental group of G and therefore an element O of Out(F_{n}); we say that f : G → G is a representative of O.

Suppose that G is a marked graph and that ∅ = G_{0} ⊂ G_{1} ⊂ ⋯ ⊂ G_{K} = G is a filtration of G where G_{i} is obtained from G_{i−1} by adding a single edge E_{i}. A homotopy equivalence f : G → G is upper triangular with respect to the filtration if each f(E_{i}) = v_{i}E_{i}u_{i} where u_{i} and v_{i} are loops in G_{i−1}. If the choice of filtration is clear then we simply say that f : G → G is upper triangular. We refer to the u_{i}’s and v_{i}’s as suffixes and prefixes respectively.

An outer automorphism is UP G if and only if it has a representative that is upper triangular with respect to some filtered marked graph G (see Section 3).

For any filtered marked graph G let Q be the set of upper triangular homotopy equivalences of G up to homotopy relative to the vertices of G. By Lemma 6.2, Q is a group under the operation induced by composition. There is a natural map from Q to UP G(F_{n}). We say that a subgroup of UP G(F_{n}) is filtered if it lifts to a subgroup of Q for some filtered marked graph. We can now state our main theorem.

Theorem 1.1. (Kolchin Theorem for Out(F_{n})). Every finitely generated UP G subgroup H of Out(F_{n}) is filtered. The number of edges of the filtered marked graph can be taken to be bounded by \frac{3n}{2} − 1 for n > 1.

It is an interesting question whether or not the requirement that H be finitely generated is necessary or just an artifact of our proof.

Question: Is every UP G group in Out(F_{n}) contained in a finitely generated UP G group?

Remark 1.2. In contrast to unipotent mapping class subgroups, which are all finitely generated and abelian, UP G subgroups of Out(F_{n}) can be quite large. For example, if G is the rose on n petals, then a filtration on G corresponds to an ordered basis x_{1}, ⋯, x_{n} of F_{n} and elements of Q correspond to automorphisms of the form x_{i} ↦ a_{i}x_{i}b_{i} with a_{i}, b_{i} ∈ ⟨x_{1}, ⋯, x_{i−1}⟩. When n > 2, the image of Q in UP G(F_{n}) contains F_{2} × F_{2}.

This is the second of two papers in which we establish the Tits Alternative for Out(F_{n}).

Theorem (The Tits Alternative for Out(F_{n})) . Let H be any subgroup of Out(F_{n}). Then either H is virtually solvable, or contains F_{2}.

For a proof of a special (generic) case, see [BFH95]. The relation between Theorem and Theorem 1.1 is captured by the following corollary.

Corollary 1.3. Every UP G group H either contains F_{2} or is solvable.

Proof. First assume that H is finitely generated. By Theorem 1.1 there is a marked graph G, a filtration F and a subgroup Z of Q that projects isomorphically onto H. Let i ≥ 0 be the largest parameter value for which every element of Z restricts to the identity on G_{i−1}. If i = K + 1, then Z is the trivial group and we are done. Supppose then that i ≤ K. By construction, each element of Z satisfies E_{i} ↦ v_{i}E_{i}u_{i} where v_{i} and u_{i} are paths (that depend on the element of Z) in G_{i−1} and are therefore fixed by every element of Z. The suffix map S : Z → F_{n}, which assigns the suffix u_{i} to the element of Z, is therefore a homomorphism. If the image of S contains F_{2}, then Z contains F_{2} and we are done. If the image of S has rank one, then it can be identified with ℤ and there is no loss in replacing Z with the kernel of S. If the image of S has rank zero, then Z is the kernel of S. A similar argument using prefixes instead of suffixes, allows us to replace Z with the subgroup of Z that has no non-trivial prefixes or suffixes for E_{i} and so restricts to the identity on G_{i}. Upward induction on i now completes the proof when H is finitely generated. In fact, this argument shows that H is polycyclic and that the length of the derived series is bounded by \frac{3n}{2} − 1 for n > 1.

When H is not finitely generated, it can be represented as the increasing union of finitely generated subgroups. If one of these subgroups contains F_{2}, then so does H, and if not then H is solvable with the length of the derived series bounded by \frac{3n}{2} − 1.

Proof of the Tits Alternative for Out(F_{n}). Theorem 1.3 of [BFH96a] asserts that if H does not contain F_{2}, then there is an exact sequence

1 → H_{0} → H → A → 1

with A a finitely generated free abelian group and with all elements of H_{0} of polynomial growth.

By passing to a subgroup of H of finite index that acts trivially in ℤ/3ℤhomology, we may assume that H_{0} is a UP G group (see Proposition 3.5). Since H_{0} does not contain F_{2}, by Corollary 1.3, H_{0} is solvable, and thus H is also solvable.

In [BFH96b] we strengthen the Tits Alternative for Out(F_{n}) further by proving:

Theorem (Solvable implies abelian) . 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 ≤ 2n − 3 for n > 1 [CV86].

There is a reformulation of our Kolchin theorem in terms of trees. This is the form in which we prove the theorem in this paper.

Theorem 5.1. For every finitely generated UP G subgroup H of Out(F_{n}) there is a nontrivial simplicial F_{n}-tree with all edge stabilizers trivial that is fixed by all elements of H.

Such a tree can be obtained from the marked filtered graph produced by our Kolchin theorem by taking the universal cover and then collapsing all edges except for the lifts of the highest edge E_{K}. For a proof of the reverse implication, namely that Theorem 5.1 implies Theorem 1.1 see Section 6.

We now outline the proof of Theorem 5.1. The idea is to find the common fixed tree using an iteration scheme. This iteration takes place in the space X_{S} of very small simplicial F_{n}-trees (for a definition see Section 2.1). There is a natural (right) action of Out(F_{n}) on X_{S} (see Section 2 for a review of the necessary background). In the first part of the paper we are primarily concerned with a study of the dynamics of the action of a UP G automorphism O on X_{S}. Specifically, we show in Theorem 4.7 that under iteration every tree T ∈ X_{S} converges to a tree T O^{∞} ∈ X_{S} (necessarily fixed by the automorphism). This fact is a consequence of Theorem 4.2, which asserts that the sequence of iterates of any γ ∈ F_{n} under a UP G automorphism O eventually behaves like a polynomial (for a definition, see Section 4.1; in particular the function k ↦ length(O^{k}([γ])) coincides with a polynomial for large k). In addition, we show that the asymptotic behavior of the sequence {O^{k}([γ])} is largely determined by a finite number of eigenrays of O that correspond to the eigendirections in the linear case.

Section 5 is the heart of the proof. Let T_{0} be a nontrivial simplicial F_{n}- tree with trivial edge stabilizers such that the set of elliptic elements (a free factor system) is H-invariant and maximal among all H- invariant free factor systems. For notational simplicity let us assume that H is generated by two elements, O_{1} and O_{2}. Then consider the sequence T_{0}, T_{1}, T_{2}, ⋯ of simplicial trees defined inductively by T_{i+1} = T_{i}O_{1}^{∞} if i is even and by T_{i+1} = T_{i}O_{2}^{∞} if i is odd. We then show that the sequence is eventually constant and the tree thus obtained has the desired properties. The first step consists of showing that a suffix of O_{1} or O_{2} can be hyperbolic in at most one of the trees in the sequence. This claim is established by showing that, assuming the contrary, some element of H grows exponentially. The argument is reminiscent of the argument that the group generated by two Dehn twists in intersecting curves contains an exponentially growing mapping class. It follows from this first step that eventually all suffixes of O_{1} and O_{2} are elliptic in T_{i}. The second step is to show that starting from this T_{i} the set of elliptic elements forms a decreasing sequence. After establishing a chain bound on sets of elliptic elements (see Proposition 2.22), this implies that the set of elliptics in T_{j} is independent of j (for large j). By the unipotent assumption, the vertex stabilizers of T_{j} are fixed by H (rather than permuted) up to conjugacy (see Proposition 4.15). This however does not imply that T_{j} is fixed by O_{1} and O_{2} (for examples see Section 5). In the third step we examine the edge stabilizers of T_{j}. If some are trivial and some nontrivial, then by collapsing those with nontrivial stabilizer we obtain a tree that contradicts the choice of T_{0}. If they are all nontrivial, we examine the term of the sequence {T_{k}} that gave rise to such edges and again find a larger proper free factor system invariant under H. Therefore all edges of T_{j} have trivial stabilizer. In the fourth and final step we observe that if T_{j} is not fixed by O_{1} and O_{2}, then in the sequence {T_{k}} an equivalence class of edges gets short compared to the average and there is again a larger proper free factor system invariant under H. This last step is reminiscent of the development of Nielsen-Thurston theory where one finds invariant curves of a mapping class by an iteration scheme in the moduli space and picks out the curves that get short.

The key arguments in the paper focus not on discovering a ping- pong dynamics (H may well contain F_{2}) but on constructing an element in H of exponential growth. These are Proposition 5.6, Proposition 5.7, and Proposition 5.13.

After the breakthrough of E. Rips and the subsequent successful applications of the theory by Z. Sela and others it became clear that trees were the right tool for proving Theorem 1.1. Surprisingly, under the assumption that H is finitely generated (the case we are concerned with in this paper and that suffices for the Tits Alternative), we only work with simplicial trees and the full scale ℝ-tree theory is never used. However, its existence gave us a firm belief that the project would succeed, and, indeed, the first proof we found of the Tits Alternative used this theory. In a sense, our proof can be viewed as a development of the program, started by Culler-Vogtmann [CV86], to use spaces of trees to understand Out(F_{n}) in much the same way that Teichmüller space and its compactification were used by Thurston and others to understand mapping class groups.

The results of [BFH96a] used here are collected in Section 3.3. The reader interested primarily in the arguments involving trees can read the present paper independently of [BFH96a].

2 F_{n}-Trees

In this section, we collect the facts about real F_{n}-trees that we will need. This paper will only use these facts for simplicial trees, but we record more general results for later use.

2.1 Very small trees

An F_{n}-tree T is very small [CL95] if it is minimal (i.e. it does not have any proper invariant subtrees), nondegenerate (i.e. it is not a point), all edge stabilizers are trivial or primitive cyclic, and for each 1 ≠ γ ∈ F_{n} the subset F ix_{T} (γ) of T fixed by γ is either empty, a point, or an arc. The set of all projective classes of very small F_{n}-trees is denoted by X and the subset of X consisting of the projective classes of simplicial trees is denoted by X_{S}. Both are topologized via the embedding θ : X → ℙ^{C} into the infinitedimensional projective space, where C is the set of all conjugacy classes in F_{n} and θ(T) : [γ] ↦ ℓ_{T} (γ) (ℓ_{T} (γ) is the translation length of γ in T). See [CM87] for a proof that θ is injective.

The automorphism group Aut(F_{n}) acts naturally on X on the right by changing the marking. In terms of the length functions, the action is given by ℓ_{T O}([γ]) = ℓ_{T} (O([γ])). Inner automorphisms act trivially and we have an action of Out(F_{n}) = Aut(F_{n})/Inn(F_{n}). There is a natural invariant decomposition of X_{S} into open simplices. The space X can be identified [CL95]

[CM87] with Culler-Morgan’s compactification [CM87] of Culler-Vogtmann’s Outer Space [CV86].

2.2 Bounded cancellation constants

We will often need to compare the length of the same element of F_{n} in different F_{n}-trees. The existence of bounded cancellation constants will usually suffice for this job.

Definition 2.1. The bounded cancellation constant of an F_{n}-map f : T′ → T, denoted BCC(f), is the least upper bound of numbers B with the property that there exist points a, b, c ∈ T′ with b on the segment [a, c] so that the distance between f(b) and the segment [f(a), f(c)] is B.

In [Coo87] Cooper showed that if both T and T′ are free simplicial and minimal and f is P L, then BCC(f) is finite. The bound given by Cooper depends on the Lipschitz constants of f and of an F_{n}-map T′ → T.

Below we generalize Cooper’s result to the case that the target tree T is very small. For a map f between metric spaces we denote by L(f) the Lipschitz constant of f, i.e.

L(f) := sup{d_{T′}(f(a), f(b))/d_{T} (a, b)|(a, b) ∈ T × T, a ≠ b}.

Lemma 2.2. Suppose f : T′′ → T′ and g : T′ → T are F_{n}-maps between minimal F_{n}-trees. Then

1. BCC(g) ≤ BCC(gf)

2. BCC(gf) ≤ BCC(g) + L(g)BCC(f)

Proof. (1) follows directly from definition.

(2) Choose a, b, c ∈ T′′ with b ∈ [a, c], and let b′ be the point in [f(a), f(c)] closest to f(b). Then

\begin{aligned}d(gf(b), [gf(a), gf(c)]) & ≤ d(gf(b), g(b′)) + d(g(b′), [gf(a), gf(c)]) \\ & ≤ L(g)BCC(f) + BCC(g). \end{aligned}

Definition 2.3. The covolume of a free simplicial and minimal F_{n}-tree T, denoted cov(T), is the sum of the lengths of edges in T/F_{n}.

Proposition 2.4. Suppose f : T_{1} → T is an F_{n}-map between free simplicial and minimal F_{n}-trees T_{1} and T. Assume f is linear on each edge of T_{1}. Then

BCC(f) ≤ L(f)cov(T_{1}) − cov(T)

Proof. Represent f as the composition hgf_{k} ⋯ f_{1} where each f_{i} : T_{i} → T_{i+1} is a fold (see [Sta83]), g collapses some orbits of edges, and h is a homeomorphism, linear on each edge, with L(h) = L(f) (see [BF91, page 452]). Note that L(g) = L(f_{i}) = 1, BCC(h) = BCC(g) = 0, and BCC(f_{i}) = cov(T_{i}) − cov(T_{i+1}). Then we use Lemma 2.2.

BCC(f) = BCC(hgf_{k} ⋯ f_{1})
≤ BCC(h) + L(h)BCC(gf_{k} ⋯ f_{1})
≤ BCC(h) + L(f)(BCC(g) + BCC(f_{k}) + ⋯ + BCC(f_{1}))
= L(f)(BCC(f_{k}) + ⋯ + BCC(f_{1}))
= L(f)(cov(T_{1}) − cov(T_{k+1}))
≤ L(f)cov(T_{1}) − cov(T)

Proposition 2.5. Suppose f : T_{1} → T is a Lipschitz F_{n}-map from a free simplicial F_{n}-tree T_{1} to a very small simplicial F_{n}-tree T. Assume f is linear on each edge of T_{1}. Then BCC(f) < ∞.

Proof. Represent f as a composition of folds and apply Lemma 2.2.

The following generalization is not used in this paper, but will be in [BFH96b].

Proposition 2.6. For every tree T ∈ X, every very small simplicial F_{n}-tree T_{1} any F_{n}-map T_{1} → T that is linear on edges has finite BCC.

Proof. By Lemma 2.2 it suffices to prove the proposition in the case that T_{1} is the universal cover of a rose. Further, it suffices to construct an F_{n}- map T_{1} → T with finite BCC (since any two such maps are within bounded distance from each other). There is an embedding ϕ of X_{S} into the space of very small trees. Indeed, let {x_{1}, ⋯, x_{n}} be a basis for F_{n} and let P denote the elements of word length at most 2. If T is a nontrivial F_{n}-tree then the lengths of the elements of P can’t all be 0 [CV86]. Thus, the set of all very small trees T such that the sum of the lengths of the elements of P equals 1 is homeomorphic to X_{S}. Let T_{1} be the universal cover of a rose in ϕ(X_{S}). There is a continuous choice of base point for each T ∈ ϕ(X_{S}) [Sko],[Whi91]. Let f_{T} : T_{1} → T be the map that takes the vertex of T_{1} to the base point of T and is linear on the edges of T_{1}. Since the topology on ϕ(X_{S}) is the same as the based length function topology [AB87], the Lipschitz constant L(f_{T}) varies continuously. Since the topology on ϕ(X_{S}) is the same as the equivariant Gromov-Hausdorff topology, BCC is lower semicontinuous [Pau88]. By Proposition 2.4, BCC(f_{T}) ≤ L(f_{T})cov(T_{1}) if T is minimal free simplicial. So, the proof now follows from the above observations together with the fact that every very small tree is the limit of free simplicial and minimal trees [BF92, Theorem 2.2].

2.3 Free factor systems

Our next goal is to prove that chains of the sets of elliptic elements in very small F_{n}-trees are bounded. To develop notation we first handle the special case of free factor systems, which corresponds to restricting to simplicial trees with trivial edge stabilizers. There is some overlap between this section and [BFH96a].

Let N denote the set of finite nonincreasing sequences in ℕ. We allow the empty sequence. Well order N lexicographically. For example, 5, 3, 3, 1 > 4, 4, 4, 4, 4, 4 > 4 > ∅. In the cases that we consider, the sum of the elements in the set will be no more than n. Thus, the sequence n will be the largest element that we will consider and ∅ the smallest.

Definition 2.7. If F is a subgroup of F_{n} then let [F] denote the set of all subgroups of F_{n} that are conjugate to F, i.e. the conjugacy class of F. A set F of free factors of F_{n} is a free factor system if there is a free factor of F_{n} of the form F_{1} ∗ ... ∗ F_{k} such that F = [F_{1}] ∪ [F_{2}] ∪ ⋯ ∪ [F_{k}]. For convenience, we will always require that < 1 >∈ F. Equivalently, a free factor system is the set of point stabilizers of a simplicial F_{n}-tree with trivial edge stabilizers. The complexity of F is the element of N obtained by arranging the positive numbers among rank(F_{1}), ..., rank(F_{k}) in nonincreasing order. F is proper if its complexity is less than n ∈ N.

Lemma 2.8. If F and F′ are two free factor systems then {F ∩ F′|F ∈ F, F′ ∈ F′} is a free factor system.

Denote this free factor system by F ∧ F′.

Proof. Let T_{F} denote a simplicial tree with trivial edge stabilizers and vertex stabilizers F. Let T_{F′} denote a similar tree with respect to F′. For F ∈ F, consider the action of F on T_{F′}. This gives a simplicial F -tree with vertex groups {F ∩ F′^{c}|F′ ∈ F′, c ∈ F_{n}} and trivial edge groups. Use this tree to blow up [Jia] the orbit of the vertex of T_{F} stabilized by F. We obtain a simplicial F_{n}-tree with trivial edge stabilizers and vertex stabilizers F ∧ F′.

Notation 2.9. If H and H′ are two sets of subsets of F_{n} then we write H ⪯ H′ if each H ∈ H is contained in some H′ ∈ H′. If also H ≠ H′ then we write H ≺ H′.

Proposition 2.10. Let F and F′ be two free factor systems. If F ⪯ F′ then

Complexity(F) ≤ Complexity(F′).

If additionally ∪F ≠ ∪F′ then F ≺ F′ and

Complexity(F) < Complexity(F′).

Proof. If F and F′ are free factors on F_{n} such that F ⊆ F′ then rank(F) ≤ rank(F′) with equality if and only if F = F′. The lemma now follows easily.

Corollary 2.11.

Complexity(F ∧ F′) ≤ Min{Complexity(F), Complexity(F′)}.

Lemma 2.12. Let H be a (possibly infinite) set of subsets of F_{n}. Then there is a free factor system F(H) of minimal complexity such that H ⪯ F(H). Further, this system is unique.

Proof. Clearly there is such a system, call it F. If F′ ≠ F is another then so is F ∧ F′ but of smaller complexity.

Corollary 2.13.

Complexity(F(H ∪ H′)) ≥ Max{Complexity(F(H)), Complexity(F(H′))}.

Notation 2.14. Let ∂F_{n} denote the Hopf boundary [Hop43] of F_{n} (which agrees with the Gromov boundary in this case). If F_{n} is represented as the fundamental group of a graph G, then ∂F_{n} may be identified with the space of geodesic rays in the universal cover G̃ of G where we identify two rays if they eventually coincide. For a finitely generated subgroup F ⊆ F_{n}, inclusion is a quasiisometric embedding (see Lemma 2.15 below) and so we may identify ∂F with a subset of ∂F_{n}. If F is represented as subgraph Δ of G then ∂F may be identified with the subspace of geodesic rays that are eventually in the preimage of Δ in G̃. Let \overline{F} denote the subset F ∪ ∂F of F_{n} ∪ ∂F_{n}. For a set F of finitely generated subgroups of F_{n} let \overline{F} denote \{\overline{F} |F ∈ F\}. If H and H′ are two sets of subsets of F_{n} ∪ ∂F_{n} then we write H ⪯ H if each H ∈ H is contained in some H′ ∈ H′. If also H ≠ H′ then we write H ≺ H′.

For a proof of the following lemma, in far greater generality, see [Sho91].

Lemma 2.15. Let H, H′ be finitely generated subgroups of F_{n}.

(1) The inclusion H ⊆ F_{n} is a quasiisometric embedding.

(2) ∂F ∩ ∂F′ = ∂(F ∩ F′).

Using Lemma 2.15, a proof similar to that of Lemma 2.12 establishes:

Lemma 2.16. Let H be a set of subsets of F_{n} ∪ ∂F_{n}. Then there is a unique free factor system F(H) of minimal complexity such that H ⪯ \overline{F(H)}.

2.4 A chain bound for vertex systems

Since some of our arguments will proceed by restricting outer automorphisms to point stabilizers of trees in X, it is important to get a precise picture of these stabilizers. In the case where T is simplicial with trivial edge stabilizers, the set of point stabilizers is a free factor system, and we have analyzed these in Section 2.3.

Definition 2.17. A vertex group is a point stabilizer of a tree in X. For an F_{n}-tree T, V(T) denotes the collection of its point stabilizers, and ∪V(T) is the set of elliptic group elements.

In this section, we show the existence of a bound for the length of sequence of inclusions of vertex groups (Proposition 2.19) or more generally vertex systems (Proposition 2.22).

In the case of simplicial trees, the following theorem is established by an easy Euler characteristic argument. The following generalization to ℝ-trees due to Gaboriau and Levitt uses more sophisticated techniques.

Theorem 2.18. [GL95] Let T ∈ X. There is a bound depending only on n to the number of conjugacy classes of point and arc stabilizers. The rank of a point stabilizer is no more than n with equality if and only if T/F_{n} is a rose and each edge of T has infinite cyclic stabilizer.

Proposition 2.19. There is a bound (depending only on n) to the length of any chain of proper inclusions of vertex groups.

Proof. Let V ⊃ V′ ⊃ V′′ be a chain of proper containments of vertex groups with corresponding trees T, T′, and T′′. We will show that either rank(V) > rank(V′′) or n ≥ rank(H_{1}(V/ ≪ V′′ ≫)) > rank(H_{1}(V/ ≪ V′ ≫)).

Let T′_{V} and T′′_{V} be minimal V -subtrees of T′ and T′′ respectively. Since the vertex groups of T′_{V} are precisely the intersection of the vertex groups of T′ with V, we see that T′_{V} has a vertex labelled V′ and so rank(V) ≥ rank(V′). Similarly, rank(V′) ≥ rank(V′′). If rank(V) > rank(V′′) then we are done, so assume these ranks are equal.

Using Theorem 2.18, the only remaining possibility is that orbit spaces of both T′_{V} and T′′_{V} are roses of circles with all edges labeled by infinite cyclic groups. The number k(T′_{V}) of orbits edges of T′_{V} may be computed as rank(H_{1}(V/ ≪ V′ ≫). (Indeed, in general if S is a V -tree, X its orbit space S/V, and K = Kernel(V → π_{1}(X)) then K =< ∪V(S) >.) Since there is an epimorphism

V/ ≪ V′′ ≫⟶ V/ ≪ V′ ≫

we have that n ≥ k(T′′_{V}) ≥ k(T′_{V}). We will show that if k(T′′_{V}) = k(T′_{V}) then V′ = V′′, a contradiction.

Consider the morphism ϕ : T′′_{V} → T′_{V} that sends the vertex v′′ labelled V′′ to the vertex v′ labelled V′. This map is well defined for if e′′ is the edge from v′′ to gv′′ with stabilizer E′′, then E′′ = V′′ ∩ V′′^{g} ⊆ V′ ∩ V′^{g} = Stabilizer(ϕe′′). Thus, T′_{V} is obtained from T′′_{V} by a finite number of folds (after perhaps first subdividing T′′_{V}) [BF91, page 455]. An inspection of the types of folds [BF91, pages 452–3] reveals that, in this situation, a sequence of folds cannot change the vertex groups without decreasing the first Betti number of the quotient graph or increasing the rank of an edge stabilizer.

Remark 2.20. Notice that a vertex group of a vertex group is not necessarily a vertex group. This is apparent from Proposition 2.19 and the fact that there are F_{n}-trees with vertex groups of rank that of F_{n}.

Lemma 2.21. Let T ∈ X. Then ∪V(T) is the union of the maximal groups in V(T) each of which is a point stabilizer in T.

Proof. The lemma will follow if we show that every group V ⊆ ∪V(T) fixes a point in T. If V is finitely generated then, by [Ser80, page 65], the restriction of the action of V to T can have a trivial length function only if there is a global fixed point. Thus we may assume that V is not finitely generated. Hence, V is an increasing union of noncyclic finitely generated subgroups each contained in some point stabilizer. A noncyclic group fixes at most one point of T hence V fixes a point.

Proposition 2.22. There is a bound depending only on n to the length of a sequence of inclusions

∪V(T_{0}) ⊊ ∪V(T_{1}) ⊊ ⋯ ⊊ ∪V(T_{N})

where each T_{i} ∈ X.

Proof. Let l be a bound on the length of a chain of proper inclusions of vertex groups of trees in X. The existence of l is guaranteed by Proposition 2.19. Let M_{i} denote the set of conjugacy classes of maximal groups in ∪V(T_{i}). By Lemma 2.21, M_{i} consists of conjugacy classes of point stabilizers. For M ∈ M_{i}, let ∪M ⊆ F_{n} denote the set of elements represented by M. Let A_{i} denote the subset of the power set P(F_{\}) of F_{n} given by {∪M|M ∈ M_{i}}. Let k be a bound to |A_{i}| (see Theorem 2.18). We will show that N < l^{k}.

Sublemma 2.23. For every pair of integers k, l > 0 the following holds with n = l^{k}. Let A_{0}, A_{1}, …, A_{n} be subsets of the power set P(X) of a fixed set X. Assume that

• if A, A′ ∈ A_{i} with A ⊆ A′ then A = A′, • |A_{i}| ≤ k for all i, and

• A_{i} ⪯ A_{i+1} for all i.

Then one of the following two possibilities occurs.

1. There are A_{i} ∈ A_{i}, i = 1, 2, …, n, such that

A_{0} ⊆ A_{1} ⊆ ⋯ ⊆ A_{n}

and at least l of these inclusions are proper.

2. For some i, A_{i} = A_{i+1}.

Proof. Induction on k. The case k = 1 is clear. Now suppose that the lemma is true for k − 1. Choose arbitrary A_{i} ∈ A_{i} with A_{0} ⊆ A_{1} ⊆ ⋯ ⊆ A_{n}. Consider l chains of inclusions of length l^{k−1}

A_{jl^{k−1}} ⊆ A_{jl^{k−1}+1} ⊆ ⋯ ⊆ A_{(j+1)l^{k−1}}, j = 0, 1, 2, …, l − 1.

If each chain contains a proper inclusion, then (1) holds. If not, then one of these chains, say the one with j = 0, consists of equalities. Now, remove A_{i} from A_{i}, i = 1, 2, …, l^{k−1}. By the first bullet, the new collection satisfies the inductive hypothesis.

We now continue the proof of Proposition 2.22. Assume N = l^{k}. The hypotheses of Sublemma 2.23 are satisfied. According to the Sublemma, there is i so that A_{i} = A_{i+1}, since (1) is impossible by our choice of l. But now we have ∪V(T_{i}) = ∪V(T_{i+1}) since ∪V(T_{i}) = ∪A_{i}.

3 Unipotent polynomially growing outer automorphisms

We now bring outer automorphisms into the picture. We will consider a class of outer automorphisms that is analogous to the class of unipotent matrices. First we review the linear algebra of unipotent matrices.

3.1 Unipotent linear maps

Definition-Proposition 3.1. Let R = ℤ or ℂ, and let V be a free Rmodule of finite rank. We say that an R-module endomorphism F : V → V is unipotent if the following equivalent conditions are satisfied:

1. V has a basis with respect to which F is upper triangular with 1’s on the diagonal.

2. (Id − F)^{n} = 0 for some n > 0.

Proof. It is clear that (1) implies (2). To see that (2) implies (1), assume that (Id − F)^{n} = 0. We may assume that W := Im(Id − F)^{n−1} ≠ 0. The restriction of Id − F to the submodule W is 0, and hence each 0 ≠ w ∈ W is fixed by F. In the case R = ℤ pass to a primitive submultiple if necessary to conclude that V always contains an F -fixed basis element v. The proof now concludes by induction on rank(V) using the observation that the induced homomorphism F′ : V/ < v >→ V/ < v > also satisfies (Id − F′)^{n} = 0.

Corollary 3.2. Let R = ℤ or ℂ. Let F : V → V be an R-module endomorphism, and let W be an F -invariant submodule of V which is a directsummand of V. Then F is unipotent if and only if both the restriction of F to W and the induced endomorphism on V/W are unipotent.

Proof. Evident, if we use (2) in ⟹ and (1) in ⟸.

Corollary 3.3. Let F : V → V be unipotent. If x ∈ V is F -periodic, i.e. if F^{m}(x) = x for some m > 0, then x is F -fixed, i.e. F (x) = x.

Proof. First assume that R = ℂ. We may assume that V = span(x, F (x), ⋯, F^{m−1}(x)). Let e_{1}, e_{2}, …, e_{m} be the standard basis for ℂ^{m}. There is a surjective linear map π : ℂ^{m} → V given by π(e_{i}) = F^{i−1}(x), and F lifts to the linear map \overline{F} : ℂ^{m} → ℂ^{m}, \overline{F} (e_{i}) = e_{i+1 mod m}. For λ ∈ ℂ, the generalized λ-eigenspace is defined to be

\{x ∈ ℂ^{m}|(λI − \overline{F})^{m}(x) = 0\}.

The linear map π must map the generalized 1-eigenspace onto V (and all other generalized eigenspaces to 0). Since this space is one-dimensional (and equals the 1-eigenspace of \overline{F}), it follows that dim(V) ≤ 1 and F (x) = x.

If R = ℤ, just tensor with ℂ.

Corollary 3.4. Let F : V → V be unipotent. If W is a direct summand which is periodic (i.e. F^{m}(W) = W for some m > 0), then W is invariant (i.e. F (W) = W).

Proof. The restriction of F^{m} to W is unipotent, so there is a basis element x ∈ W fixed by F^{m}. By Corollary 3.3, F (x) = x. The proof concludes by induction on rank(W).

Proposition 3.5. Let F ∈ GL_{n}(ℤ) have all eigenvalues on the unit circle (i.e. F grows polynomially). If the image of F in GL_{n}(ℤ/3) is trivial, then F is unipotent.

Proof. We first argue that some power A^{N} of A is unipotent, i.e. that all eigenvalues of A are roots of unity. Choose N so that all eigenvalues of A^{N} are close to 1. Then tr(A^{N}) is an integer close to n, and thus all eigenvalues of A^{N} are equal to 1.

Let f = f_{1}^{n_{1}} ⋯ f_{m}^{n_{m}} be the minimal polynomial for A factored into irreducibles in ℤ[x]. Let A_{i} = f_{i}^{n_{i}}(A) and K_{i} = Ker(A_{i}). First note that each K_{i} ≠ 0. For example, Im(A_{2}A_{3} ⋯ A_{m}) ⊂ K_{1} but A_{2}A_{3} ⋯ A_{m} ≠ 0 since f is minimal. If A is not unipotent, then some f_{i}, say f_{1}, is not x − 1. Thus f_{1} is the minimal polynomial for a nontrivial root of unity and so it divides 1 + x + x^{2} + ⋯ + x^{r−1} for some r > 1. The matrix I + A + A^{2} + ⋯ + A^{r−1} has nontrivial kernel (since its n_{1}^{st} power vanishes on K_{1}). It follows that there is a nonzero integral vector v such that A^{r}(v) = v but A(v) ≠ v. Then F ix(A^{r}) is a nontrivial direct summand of ℤ^{n}, the restriction of A to this summand is nontrivial and periodic, and the induced endomorphism of F ix(A^{r}) ⊗ ℤ/3 is identity. This contradicts the standard fact that the kernel of GL_{k}(ℤ) → GL_{k}(ℤ/3) is torsion-free.

3.2 Relative train tracks

Techniques of this paper strongly depend on finding good representatives for polynomially growing outer automorphisms.

Definition 3.6. An outer automorphism O ∈ Out(F_{n}) is P G(F_{n}) (or just P G) if for each conjugacy class [γ] in F_{n} the sequence of (reduced) word lengths of O^{i}([γ]) is bounded above by a polynomial.

We start by recalling the representatives for P G automorphisms found in [BH92].

Theorem 3.7. [BH92] Every P G automorphism O ∈ Out(F_{n}) has a representative as a homotopy equivalence f : G → G on a marked graph G such that

1. the map f sends vertices to vertices and edges to immersed nontrivial edge paths.

2. There is a filtration ∅ = G_{0} ⊊ G_{1} ⊆ ⋯ ⊊ G_{K} = G of G by f-invariant subgraphs such that for every edge E ∈ \overline{G_{i} \ G_{i−1}} the edge path f(E) crosses exactly one edge in \overline{G_{i} \ G_{i−1}} and it crosses that edge exactly once.

3. If F is an O-invariant free factor system, we can arrange that F is represented by some G_{r}. If O is the identity on each conjugacy class in F, we can arrange that f = Id on G_{r}.

Definition 3.8. The representative in Theorem 3.7 is called a relative train track (RT T) representative for f.

Notation 3.9. All paths in graphs and trees will have endpoints in the vertex set. If γ is a path, [γ] will denote the unique immersed path homotopic to γ rel endpoints. When the endpoints of γ coincide, we say that γ is a based loop. When γ is an (unbased) essential loop, [γ] will denote the unique immersed loop freely homotopic to γ. We make standard identifications between homotopy classes of based loops with elements of the fundamental group and between homotopy classes of loops and conjugacy classes in the fundamental group.

3.3 Unipotent representatives

We now introduce UP G automorphisms - the objects of central importance in this paper.

Definition 3.10. An outer automorphism is a UP G(F_{n}) (or just UP G) automorphism if it is P G(F_{n}) and its action in H_{1}(F_{n}; ℤ) is unipotent.

We now recall a special case of an improvement of RT T representatives from [BFH96a].

Recall that if f : G → G is a RTT representative and z is an edge path in G then we write [z] for the geodesic homotopic rel endpoints to z. We also write z = x · y for edge paths x and y in G if [f^{n}(z)] = [f^{n}(x)][f^{n}(y)] for all n ≥ 0 and say that z “splits”.

Definition 3.11. Let f : G → G be an RT T representative. A path τ in G with endpoints in the vertex set is Nielsen if [f(τ)] = [τ]. An exceptional path in G is a path of the form

• E_{i}τ^{m}E_{i}^{−1} provided τ is a nontrivial Nielsen path and f(E_{i}) = E_{i}τ^{p} for some m, p ∈ ℤ, m ≠ 0, or

• E_{i}τ^{m}E_{j}^{−1} provided τ is a Nielsen path, i ≠ j, f(E_{i}) = E_{i}τ^{p}, and f(E_{j}) = E_{j}τ^{q} for some m, p, q ∈ ℤ.

The following theorem follows easily from Theorem 6.8*** and Lemma 6.24*** of [BFH96a].

Theorem 3.12. ([BFH96a]) Suppose that O ∈ Out(F_{n}) is a UP G-automorphism, that F is an O-invariant free factor system. Then there is an RT T representative f : G → G of O with the following properties.

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

2. Each G_{i} is the union of G_{i−1} and a single edge E_{i} satisfying f(E_{i}) = E_{i} · u_{i} for some closed path u_{i} that crosses only edges in G_{i−1}.

3. 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.

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

5. There is a uniform constant C so that if ω is a closed path in G that is not a Nielsen path and σ = αω^{k}β is an immersed path, then at most C copies of [f^{m}(ω)] are cancelled when [f^{m}(α)][f^{m}(ω^{k})][f^{m}(β)] is tightened to [f^{m}(σ)].

Definition 3.13. An RT T representative f satisfying 1-5 above is a unipotent representative or a UR. The based loops u_{i} are suffixes of f.

Note that (2) can be restated as

[f^{k}(E_{i})] = E_{i}u_{i}[f(u_{i})] ⋯ [f^{k−1}(u_{i})]

for all k > 0. The immersed infinite ray

R_{i} = E_{i}u_{i}[f(u_{i})] ⋯ [f^{k−1}(u_{i})] ⋯

is the eigenray associated to E_{i}. Lifts of R_{i} to the universal cover of G are also called eigenrays. The subpaths [f^{m}(u_{i})] of R_{i} are sometimes referred to as blocks.

For example, the map f : G → G on the rose with two petals labelled a and b given by f(a) = a, f(b) = ba is a UR. For ω = ba^{−10}bab^{−1} we may take M(ω) = 10 in (3), since [f^{10}(ω)] = b · (bab^{−1}) is a splitting into an edge and an exceptional (Nielsen) path. The map given by a ↦ a, b ↦ ba, c ↦ cba^{−1} on the rose with three petals is not a UR since ω = cba^{−1} does not eventually split as in (3). Replacing ba^{−1} by b′ yields a UR of the same outer automorphism.

Definition 3.14. Let f : G → G be a UR. The height of an edge-path in G is the smallest m such that the path is contained in G_{m}. A topmost edge in an edge-path of height m is an occurrence of E_{m} or E_{m}^{−1} in the edge-path.

Many arguments are inductions on height. The inductive step is based on the observation that a path of height m splits at the initial (terminal) endpoints of each occurrence of E_{m} (E_{m}^{−1}).

4 The dynamics of UP G automorphisms

In this section we examine the dynamics of the action of UP G automorphisms on conjugacy classes, free factor systems, and the space X of very small F_{n}- trees.

4.1 Polynomial sequences

In this section we show that the sequence of iterates of a path under a UP G automorphism behaves like a polynomial and use this to prove Theorem 4.7 which is fundamental in our approach.

Definition 4.1. Let G be a graph. A sequence {A_{k}}_{k=k_{0}}^{∞} of immersed paths in G is said to be a polynomial sequence if it can be obtained from constant sequences of paths by finitely many operations described below.

1. (reindexing and truncation): A_{k} = B_{k+k′} for a polynomial sequence {B_{k}}_{k=k_{1}}^{∞} for some k_{1} ≤ k_{0} + k′,

2. (inversion): A_{k} is the inverse of B_{k}, and {B_{k}}_{k=k_{0}}^{∞} is a polynomial sequence, 3. (concatenation): A_{k} = B_{k}C_{k}, where {B_{k}} and {C_{k}} are polynomial

sequences, (and no cancellation occurs in B_{k}C_{k}), and

4. (integration): A_{k} = B_{k_{0}}B_{k_{0}+1} ⋯ B_{k}, where {B_{k}} is a polynomial sequence (and again no cancellation occurs).

For example, in the standard rose, sequences {AB^{k}C} and {ABAB^{2}AB^{3} ⋯ AB^{k}} are polynomial.

Theorem 4.2. Let f : G → G be a UR representative of a UP G automorphism. Let σ be a path in G with endpoints in the vertex set of G. Then there is k_{0} > 0 such that the sequence {[f^{k}(P)]}_{i=i_{0}}^{∞} is polynomial.

Proof. We induct on the height of σ. If the height is 1, the sequence is constant. For the induction step, replace σ by the iterate [f^{M}(σ)] from Theorem 3.12 so that it splits into subpaths which are either single edges or exceptional paths. It suffices to prove the statement for these subpaths. The statement is clear for the exceptional subpaths, and it follows from the inductive assumption for single edges.

More generally, we can consider polynomial sequences in any F_{n}-tree.

Definition 4.3. Let T be an F_{n}-tree. A sequence {A_{k}}_{k=k_{0}}^{∞} of embedded paths in T is said to be polynomial if it can be obtained from constant sequences of paths by finitely many operations described below.

0. (translation): A_{k} = γ_{k}(B_{k}) for a polynomial sequence {B_{k}} and a sequence {γ_{k}} of elements of F_{n},

1. (reindexing and truncation): A_{k} = B_{k+k′} for a polynomial sequence {B_{k}}_{k=k_{1}}^{∞} for some k_{1} ≤ k_{0} + k′,

2. (inversion): A_{k} is the inverse of B_{k}, and {B_{k}}_{k=k_{0}}^{∞} is a polynomial sequence,

3. (concatenation): A_{k} = B_{k}C_{k}, where {B_{k}} and {C_{k}} are polynomial sequences, (and in particular no cancellation occurs in B_{k}C_{k}), and

4. (integration): A_{k} = B_{k_{0}}B_{k_{0}+1} ⋯ B_{k}, where {B_{k}} is a polynomial sequence (and again there is no cancellation).

The following lemma is by induction on the number of above operations and its proof is left to the reader.

Lemma 4.4. Let {A_{k}}_{k=k_{0}}^{∞} be a polynomial sequence of paths in an F_{n}-tree T. Then

1. the function k ↦ ℓ_{T} (A_{k}) is a polynomial function in k,

2. if A_{k} = BC_{k}D for some paths B and D, then the sequence {C_{k}}_{k=k_{0}}^{∞} is polynomial,

3. {A_{k}} is either constant (up to the action of F_{n}), or for any d > 0 there is k_{1} ≥ k_{0} so that for every k ≥ k_{1} A_{k} = BC_{k}D for paths B and D of length ≥ d,

4. the initial endpoints of the A_{k}’s lie in a single F_{n}-orbit, and similarly the terminal endpoints lie in a single F_{n}-orbit.

Proposition 4.5. If O is a UP G(F_{n}) automorphism, then all O-periodic conjugacy classes are fixed.

Proof. Assume x is an O-periodic conjugacy class. Represent x as a loop γ in a UR representative f : G → G. Consider the splitting of γ given by the topmost edge of G that intersects γ. Since x is O-periodic, each of the resulting paths is also f-periodic. Theorem 4.2 and Lemma 4.4 now imply that each path is f-fixed, and thus γ is f-fixed.

Another immediate consequence of Lemma 4.4 is the following.

Proposition 4.6. Let α : G̃ → T be an equivariant map from the universal cover of G to an F_{n}-tree T with a finite BCC (see Section 2.2). Suppose {A_{k}}_{k=k_{0}}^{∞} is a polynomial sequence in G̃, and define B_{k} = [α(A_{k})]. Then there is k_{1} ≥ k_{0} such that the sequence {B_{k}}_{k=k_{1}}^{∞} is polynomial.

Proof. By induction on the number of operations required to construct {A_{k}}. Focus on the last operation. Say A_{k} = X_{k}Y_{k}. Inductively, we know that the sequences {[α(X_{k})]} and {[α(Y_{k})]} are polynomial, after truncation. At most a bounded amount can be canceled. Assuming they are not constant, it follows from Lemma 4.4 (3) that eventually the cancelled portions are independent of k, and the claim follows from Lemma 4.4 (2). If one or both of the sequences are constant, the proof is similar.

The other nonobvious case (integration) is left to the reader.

Theorem 4.7. If T ∈ X and O ∈ UP G_{F_{n}}, then the sequence {T O^{k}} converges to a tree T O^{∞} ∈ X. Further, if T ∈ X_{S} then T O^{∞} ∈ X_{S}.

Proof. Let f : G → G be a UR for O. If w is any conjugacy class, the function k ↦ ℓ_{T} (O^{k}(w)) is eventually polynomial (the transition from paths to loops uses the fact that G̃ → T has a BCC one more time). The degree of the polynomial is uniformly bounded by the number of strata in G. Let d be the largest degree that occurs for this T and variable w. Then for any w the sequence k ↦ ℓ_{T} (f^{k}(w))/k^{d} converges, and not all limits are 0 thus the sequence converges to an F_{n}-tree. To see that the limiting tree is simplicial if T is simplicial, argue by induction on d that if {A_{k}} is a polynomial sequence in T (with endpoints in the vertex set) of degree m, then the leading term of the polynomial k ↦ ℓ_{T} (A_{k}) is uniformly bounded away from 0. It follows that the collection of nonzero numbers lim ℓ_{T} (O^{k}(w))/k^{d} is bounded away from 0, and so T O^{∞} is simplicial.

That this tree is very small follows from the fact, proved in [CL95], that the collection of very small trees is closed under limits (in the projectivized space).

Definition 4.8. Trees T for which d = 0 (i.e. the sequence {ℓ_{T} (O^{k}(w))} is eventually constant for every w) are called non-growers. Others are growers. If d = 1, we say that T grows linearly, etc.

Remark 4.9. There exist non-growers that are not fixed. An example is the tree T with T/ < a, b > a circle with an arc attached at one endpoint, the other endpoint labeled < a >, and all other labels trivial. The loop corresponds to b, and f(a) = a, f(b) = ab. Such examples do not exist in SL_{n}(ℤ) or the mapping class group of a surface. Non-growers are also responsible for the existence of compact sets K ⊂ X in the complement of F ix(f) with the property that for no k is Kf^{k} contained in a certain small neighborhood of F ix(f). A concrete example can be described as follows. Let F_{4} =< a, b_{1}, b_{2}, b_{3} >, and let f be given by f(a) = a and f(b_{i}) = b_{i}a. The compact set K consists of the biinfinite sequence …, T_{−2}, T_{−1}, T_{0}, T_{1}, T_{2}, … together with the limiting tree T_{∞}. The quotient T_{n}/F_{4} is the graph obtained from the triod by attaching loops to the valence 1 points. The center point is labeled < a > and all other labels are 1. The three loops correspond to b_{1}a^{n}, b_{2}a^{−n}, and b_{3} respectively. Passing to the limit as n → ∞ amounts to unfolding the first two loops which in the limit correspond to b_{1} and b_{2} respectively. Now notice that T_{n}f^{n} converges to a non-fixed non-grower (which is a tree just like T_{∞} except for a permutation of {b_{1}, b_{2}, b_{3}}).

It is, however, true that if K is a compact subset of the closure of Outer Space consisting of growers, then the accumulation set of the sequence Kf^{k} is a subset of F ix(f).

4.2 Suffixes and eigenrays

Recall that if f : G → G is a UR, an eigenray associated to an edge E_{i} is the infinite immersed path E_{i}u_{i}[f(u_{i})][f^{2}(u_{i})] ⋯ arising as the limit of iterates [f^{k}(E_{i})]. The following proposition is the analogue of the fact in linear algebra that if A is a unipotent matrix and v a nonzero vector, then projectively the sequence A^{k}(v) converges to an eigenspace of A.

Proposition 4.10. Let f : G → G be a UR. If [f(u_{i})] ≠ u_{i}, R^{∗} is an initial segment of R_{i}, and γ is an immersed edge path in G that contains E_{i} then there is an N such that, for all k > N, [f^{k}(γ)] contains R^{∗} or its inverse as a subpath.

Proof. We argue by induction on height(γ). If height(γ) = i, consider the splitting of f^{M}(γ) into edges and exceptional paths. There is a 1-1 correspondence between occurrences of E_{i} in γ and in f^{M}(γ). Since [f(u_{i})] ≠ u_{i}, E_{i} does not occur in an exceptional path, and hence one of the subpaths in the splitting is E_{i} or E_{i}^{−1}. Eventually, the iterates contain R^{∗} or its inverse.

Now assume height(γ) = j > i. Again consider the splitting of f^{M}(γ) into edges and exceptional paths. First note that an exceptional path E_{s}τ^{k}E_{t}^{−1} in this decomposition cannot cross E_{i} (E_{s} and E_{t} have fixed suffixes and so are distinct from E_{i}, and τ cannot cross E_{i} since height(τ) < j and so otherwise by induction the iterates of τ (which equal τ) would have to contain arbitrarily long segments of R_{i}). If the edge E_{i} or its inverse occur in the splitting, we are done. Also, if there is an edge E_{l} in the splitting whose eigenray R_{l} crosses E_{i}, then large iterates of γ contain large segments of R_{l}, which in turn contain large iterates of u_{l}, and these eventually contain R^{∗} by induction. It remains to exclude the possibility that E_{i} is not crossed by any of the eigenrays R_{l} of the edges E_{l} in the splitting. The set of edges crossed by these eigenrays union all edges with fixed suffixes is an f-invariant subgraph (by induction) that contains [f^{m}(γ)] for large m, and does not contain E_{i}. The restriction of f to this subgraph is a homotopy equivalence, and therefore γ is homotopic into it, contradicting the hypothesis.

We next analyze the edge stabilizers of the tree obtained in the limit under iteration by a UP G automorphism, starting with certain trees with trivial edge stabilizers that are closely related to a UR. We discover that the edge stabilizers of the limiting tree are conjugates of certain suffixes of the UR.

Proposition 4.11. Let f : G → G be a UR of O ∈ Out(F_{n}) and let G_{r} be a subgraph in the associated filtration of G. Assume that for every edge E of G we have f(E) = Eu with u either freely homotopic into G_{r} or [f(u)] = u. Also assume that for at least one such u the first alternative fails.

Let S be the tree obtained from the universal cover G̃ by collapsing all edges that project into G_{r}. Then the stabilizer of any edge in T = Sf^{∞} is infinite cyclic, and it contains a conjugate of a nontrivial suffix that is not freely homotopic into G_{r}.

Example 5.3 illustrates this phenomenon with G_{r} = ∅.

Proof. Notice that S grows linearly under O. Every path ω in G determines a sequence of paths in S by lifting the iterates [f^{i}(ω)] to G̃ with a common initial point and projecting to S. This sequence determines a path f^{∞}(ω) in the limiting tree T (thought of as the Gromov-Hausdorff limit of the trees SO^{i} scaled linearly, see [Pau88]). By construction, paths of the form f^{∞}(ω) cover T. Recall that by Theorem 3.12 if ω is any path or a loop in G, a sufficiently high iterate [f^{M}(ω)] has a splitting into edges and exceptional subpaths. This splitting induces a subdivision of f^{∞}(ω) into subarcs, and shows that T is covered by paths of the form f^{∞}(ω) where ω is an edge or an exceptional path. If γ fixes an arc in T, it must fix a subarc of some such f^{∞}(ω).

We next analyze the stabilizers of the nondegenerate arcs of the form f^{∞}(ω), and show that they each contain a nontrivial suffix not homotopic into G_{r}. Since T is very small, any subarc of f^{∞}(ω) has the same stabilizer and the proposition follows.

Consider first an edge E_{i} and the associated sequence E_{i}u_{i}[f(u_{i})] ⋯ [f^{k}(u_{i})]. If u_{i} is homotopic into G_{r}, then the path f^{∞}(E_{i}) is degenerate, and if it is fixed, then the path is fixed by u_{i}, viewed as an isometry of the limiting tree (a typical element of the sequence is E_{i} followed by a long string of u_{i}’s, all contained in the axis of the isometry induced by u_{i}, where we take the endpoint of E_{i} as the basepoint). An exceptional path E_{i}τ^{k}E_{j}^{−1} similarly determines a degenerate path (if it is Nielsen) or a path fixed by u_{i} (if it is not).

4.3 Primitive subgroups

By looking at homology, it is clear that if free factors in a free factor system are permuted under a UP G automorphism, then they are invariant, and the restriction is UP G. We will show moreover that a periodic free factor (or even a vertex stabilizer of a tree in X) is invariant. Our argument uses only that vertex groups are primitive.

Lemma 4.12. Let H be a finitely generated primitive subgroup of F_{n}, i.e. if γ^{n} ∈ H for some n > 0 then γ ∈ H. Then the normalizer N(H) of H in F_{n} is H.

Proof. Let T be a minimal free simplicial F_{n}-tree and let T_{H} be a minimal H-invariant subtree of T. Let γ ∈ N(H). Then γ(T_{H}) = T_{H} and so the axis of γ is in T_{H} and projects to a loop in T_{H}/H. Thus, a power of γ is in H. Since H is primitive, γ is in H.

We say that a subgroup H of F_{n} is invariant under a subgroup H ⊂ Out(F_{n}) if for every O ∈ H and every lift Ô ∈ Aut(F_{n}) of O, the subgroup Ô(H) is conjugate to H.

Lemma 4.13. Let H be a subgroup of Out(F_{n}) and let H be a finitely generated primitive subgroup of F_{n} that is H-invariant. Then the restriction map ρ_{H} : H → Out(H) is well-defined. Further, if H consists of P G(F_{n}) automorphisms, then H|_{H} := ρ_{H}(H) consists of P G(H) automorphisms.

Proof. The proof is an easy consequence of Lemma 4.12 and Lemma 2.15.

Lemma 4.14. Let G′ → G be an immersion of finite graphs such that Im[π_{1}(G′) → π_{1}(G)] is a primitive finitely generated subgroup of π_{1}(G). Let {A_{n}} be a polynomial sequence of paths in G. Assume that for infinitely many values of n the path A_{n} lifts to G′ starting at a given point x ∈ G′. Then the same is true for all large n and, furthermore, the lifts form (after truncation) a polynomial sequence in G′ (so that in particular – see Lemma 4.4(4) – the terminal endpoint of these lifts is constant).

The lemma fails if the primitivity assumption is dropped; e.g. take G to be the circle and G′ the double cover.

Proof. We proceed by induction on the number of basic operations in the construction of {A_{n}}.

Suppose first that the last step is inversion. For infinitely many n the other endpoint of the lift of A_{n} starting at x is a point y ∈ G′ (there are finitely many preimages of the common terminal endpoint of the A_{n}’s in G). Applying the statement of the lemma to {A_{n}^{−1}} we learn that for all large n there is a lift Ã_{n} of A_{n} that terminates at y, for infinitely many n it starts at x, and {Ã_{n}} forms a polynomial sequence. Therefore, for all large n, Ã_{n} starts at x.

Suppose next that the last step is concatenation: A_{n} = B_{n}C_{n}. Then B_{n} lifts to G′ starting at x for infinitely many n and thus for all large n, and the lifts B̃_{n} form a polynomial sequence. Let y be the common terminal endpoint of the B̃_{n}. Similarly, for all large n the path C_{n} lifts to a path C̃_{n} starting at y, and these paths form a polynomial sequence. Thus Ã_{n} = B̃_{n}C̃_{n} is a polynomial sequence starting at x and projecting to A_{n}.

Finally, suppose that the last step is integration: A_{n} = B_{1}B_{2} ⋯ B_{n}. Since A_{n} is a subpath of A_{n+1} it follows from our assumptions that each A_{n} lifts to a path Ã_{n} starting at x_{0} = x. Infinitely many of these end at the same point y_{1}. Thus for infinitely many n the path B_{n} lifts starting at y_{1}. It follows that eventually all these lifts end at a point y_{2}. Again, for infinitely many n, B_{n} lifts starting at y_{2} etc. Repeating this procedure we produce a sequence y_{1}, y_{2}, · · ·. Suppose that y_{i} = y_{j} for some i < j. For large n there are lifts of B_{n} that connect y_{i} to y_{i+1}, y_{i+1} to y_{i+2},..., y_{j−1} to y_{j}. By the primitivity assumption we must have y_{i} = y_{i+1} = ⋯ = y_{j}. Therefore the sequence y_{1}, y_{2}, ⋯ is eventually constant, i.e. y_{n} = y for all large n. Thus for large n the path B_{n} lifts to B̃_{n} beginning and ending at y. The claim now follows.

Proposition 4.15. Suppose that O is a UP G(F_{n}) automorphism and that H ⊆ F_{n} is a primitive finitely generated subgroup. If O^{k}(H) is conjugate to H for some k > 0, then O(H) is conjugate to H. Furthermore, if Ô ∈ Aut(F_{n}) is a lift of O with Ô^{k}(H) = H then Ô(H) = H.

The statement is false without the primitivity assumption as the following example shows: F_{2} =< a, b >, Ô(a) = a, Ô(b) = ab, H =< a^{2}, b >, k = 2.

Proof. We may assume that rank(H) > 1. Let f : G → G be a UR of O. By p : G̃ → G denote the covering space of G corresponding to H. There is a lift F : G̃ → G̃ of f^{k}. There is a fixed point of F, perhaps after replacing F by a power. (Indeed, by linear algebra, some power F^{m} of F will have negative Lefschetz number. Any fixed point of negative index of F^{m} composed with the retraction to the core is fixed under F^{m}.) Let v be a point fixed by F.

We now use v and p(v) as base points. Let α be a loop in G̃ based at v. The sequence [F^{i}(α)] of based loops forms a sequence of lifts of a subsequence of the sequence [f^{j}(p(α))] of based loops. The latter is eventually a polynomial sequence (Theorem 4.2) and hence by Lemma 4.14 for all large j the based loop [f^{j}(p(α))] lifts to a based loop in G̃. Applying this to loops α generating π_{1}(G̃, v) we conclude that f^{j} lifts to G̃ for all large j. Thus O^{j}(H) is conjugate to H for large j and the claim follows.

For the “furthermore” part of the proposition let v be the base point and choose F so that v is fixed.

Proposition 4.16. Suppose that O is a UP G(F_{n}) automorphism and that H ⊆ F_{n} is a primitive finitely generated subgroup. Then the restriction (see Lemma 4.13) O|_{H} is UP G(H).

Proof. Let f : G → G be a UR of O. By p : G̃ → G denote the covering space of G corresponding to H and let f̃ : G̃ → G̃ be a lift of f. By C denote the core of G̃. Let ρ : G̃ → C be the nearest point retraction. If C does not contain any lifts of the topmost edge E ⊂ G, then we may argue by induction on the number of strata. Therefore we assume that C contains lifts of E. From C form a finite graph G by collapsing all complementary components of C \ ∪{interiors of lifts of E}. The map ρf̃ induces a simplicial homeomorphism ϕ : G → G. The main step of the proof is to argue that ϕ = id.

Assuming ϕ ≠ id, we replace f and ϕ by a power if necessary so that there is a primitive loop γ = E_{1}E_{2} ⋯ E_{m} nontrivially rotated by ϕ. Here each E_{i} is a lift of E or of E^{−1} and ϕ(E_{i}) = E_{i+r} for some 0 < r < m (indices are mod m).

Choose a path in C of the form E_{1}αE_{2} where α does not cross any lifts of E and denote by τ the subpath of E_{1}αE_{2} obtained by splitting at E_{1} and E_{2}. Now consider the sequence {[f̃^{k}(τ)]}_{k=1}^{∞}. This sequence projects to an eventually polynomial sequence. Further, for infinitely many values of k (those in the same congruence class modulo the order of ϕ) these paths have common initial and common terminal endpoints. It follows from Lemma 4.14 that for large k and any i there is a path that joins E_{1+ir} and E_{2+ir} and projects to the same path as [f̃^{k}(τ)]. Repeat this construction for every ϕorbit of consecutive edges in G to obtain a primitive loop in C that projects to a proper power. This contradicts the primitivity assumption and shows that ϕ = id.

If α is any loop in C representing a cycle, then (f̃_{∗} − id)(α) is a cycle supported in the cores of the components of C \ ∪{interiors of lifts of E}. Inductively, it follows that a high power of f̃_{∗} − id kills α. Thus O|_{H} is UP G(H).

4.4 UP G automorphisms and trees

Recall that for T ∈ X we denote by V(T) the set of point stabilizers of T. The set E(T) denotes the set of stabilizers in T of (nondegenerate) arcs. Note that ∪V(T) is the set of elements of F_{n} that are elliptic in T.

Proposition 4.17. Let O be a UP G(F_{n}) automorphism, and let T ∈ X such that V(T) and E(T) are O-invariant. Then

1. each element of E ∈ E(T) is O-fixed (up to conjugacy),

2. each V ∈ V(T) is O-invariant, and

3. the restriction of O to each V ∈ V(T) is UP G(V).

Proof. The collection E(T) consists of finitely many conjugacy classes of cyclic subgroups of F_{n}, by Theorem 2.18. Therefore, generators of elements of E(T) are O-periodic, and hence O-fixed by Proposition 4.5.

Similarly, each of finitely many representatives of conjugacy classes in V(T) is O-periodic, hence O-invariant by Proposition 4.15, and the restriction of O is UP G by Proposition 4.16.

Lemma 4.18. Let g : G → G be a simplicial homeomorphism of a connected finite graph. Suppose that g fixes all valence one vertices, and that either it induces identity map in H_{1}(G, ℤ/3ℤ) or that it induces a unipotent map in H_{1}(G; ℤ). Then either g = Id or G is homeomorphic to S^{1} and g is rotation.

Proof of Sublemma. First assume that G has no valence one vertices. If G is a circle, the claim is clear. So assume χ(G) < 0. By the Lefschetz fixed point theorem, F ix(g) ≠ ∅. Suppose F ix(g) ≠ G. Let P be a shortest nontrivial oriented edge path which intersects F ix(g) only in its endpoints.

If any two g-iterates of P either coincide or intersect only in endpoints, then by considering the induced homomorphism on the homology of the invariant subgraph of G consisting of the union of all iterates of P we conclude that g fixes P.

Suppose that there is an iterate Q := g^{k}(P) ≠ P such that P ∩Q contains a point that is not an endpoint of P. Then, unless P ∩ Q is the common midpoint of P and Q, P is not the shortest nontrivial oriented edge path which intersects F ix(g) only in its endpoints. In particular, P ∩Q is fixed by g^{k}. So, replace g by g^{k}, and P by a proper subarc whose endpoints are fixed by g^{k}. Repeating this will eventually construct a power of g whose action on the homology of a subgraph is not unipotent.

Now suppose that G has a valence one vertex v. Any edge E incident to v must be g-fixed. So, remove E and proceed by induction on the number of edges.

Note that O ∈ Out(F_{n}) fixes a very small tree T, i.e. if ℓ_{T} (O(γ)) = ℓ_{T} (γ) for all γ, if and only if for any lift Ô ∈ Aut(F_{n}) there is an Ô-equivariant isometry fÔ : T → T.

Proposition 4.19. Assume n > 1. Suppose O is a UP G(F_{n}) automorphism that fixes a simplicial tree T ∈ X_{S}. Let Ô ∈ Aut(F_{n}) be a lift of O and let fÔ : T → T be an Ô-equivariant isometry. Then O fixes all orbits of vertices and directions.

Proof. The map fÔ induces a periodic homeomorphism \overline{f} Ô of the quotient graph. It fixes all vertices whose labels are maximal groups in ∪V(T) by Proposition 4.17. In particular, it fixes all valence 1 vertices. Since the induced action in homology of the quotient graph is unipotent, by Lemma 4.18, \overline{f} Ô is identity or rotation of the circle. The latter is impossible since then ∪V(T) ≠ {1}.

Lemma 4.20. Let f : G → G be a UR for O ∈ Out(F_{n}) and let T ∈ X. Assume that whenever a suffix u_{i} of f is not fixed by f, then there is a point in T fixed by each f^{m}(u_{i}), m = 0, 1, 2, ⋯ (these are all loops based at the same point of G and determine elements of F_{n} up to simultaneous conjugacy). Then

1. T is O-growing if and only if ℓ_{T} (u_{i}) > 0 for some suffix u_{i}, and in that case the growth is linear.

2. Moreover, if ℓ_{T O^{∞}}(γ) > 0 for a loop γ in G (see Theorem 4.7), then there is a suffix u_{i} as in (1) such that for every N > 0 there exists m_{0} > 0 with the property that all iterates [f^{m}(γ)], m ≥ m_{0}, contain

[u_{i}^{N}] as a subpath.

Proof. Let γ be any loop in G. For large m, the loop [f^{m}(γ)] has a splitting A_{1}(m) · A_{2}(m) · · · · · A_{k}(m) into subpaths each of which is an edge or an exceptional path. If there is an exceptional path E_{i}τ^{k}E_{j}^{−1} in this splitting which is not Nielsen and with ℓ_{T} (τ) > 0 then u_{i} satisfies (2). Similarly, if u_{i} is the suffix associated to an edge in the splitting with ℓ_{T} (u_{i}) > 0, then we have [f(u_{i})] = u_{i} by our assumption, and again u_{i} satisfies (2). It remains to show that if such u_{i} does not exist, then ℓ_{T} (f^{m}(γ)) remains bounded as m → ∞.

Let ϕ : G̃ → T be an equivariant map from the universal cover of G to T. For l ≥ m we have a splitting of [f^{l}(γ)] as A_{1}(l)·A_{2}(l)·· · ··A_{k}(l) obtained by iterating the splitting above. Consider the lifts of these paths to G̃ starting at a fixed vertex v. Now argue inductively on i that ϕ sends the endpoint of the lift of A_{1}(l) · A_{2}(l) · · · · · A_{i}(l) to a point within bounded distance of ϕ(v). The inductive step is clear when A_{i}(l) is a Nielsen path. Now assume that A_{i}(l) is an initial piece of an eigenray such that the associated suffix u_{i} and all iterates of u_{i} fix a point of T. First, the image of a lift of the associated edge E_{i} has finite length, so the image of its endpoint is within bounded distance from v. The image of the endpoint of A_{i}(l) is obtained from this point by applying the group element corresponding to a subpath of the eigenray R_{i} that is a concatenation of blocks. This element is elliptic by assumption and fixes a point of T independent of l, so the claim follows. Similar argument holds when A_{i}(l) is exceptional or associated to the inverse of an eigenray.

Lemma 4.21. Let O be a UP G(F_{n}) automorphism and S ∈ X. Suppose ℓ_{SO^{∞}}(γ) > 0. Then there is a K such that ℓ_{S}(O^{K′}(γ)) > 0 for all K′ > K.

Proof. This is immediate by the definition of limits.

If f : G → G is a homotopy equivalence that fixes all vertices of G and if u is a path in G with endpoints in the vertex set, then there is a unique immersed path f^{−1}(u) such that [f(f^{−1}(u))] = [u].

Proposition 4.22. Let f : G → G be a UR for O ∈ Out(F_{n}), and T a tree in X. Assume that for each suffix u_{i}, a point in T is fixed by u_{i}, all its iterates f^{m}([u_{i}]) (so that T is O-nongrowing), and all negative iterates f^{−m}([u_{i}^{−1}]) of [u_{i}^{−1}]. If γ is elliptic in T O^{∞}, then γ is elliptic in T.

Proof. Represent γ as a loop in G. Consider the splitting of [f^{M}(γ)] into edges and exceptional paths as in Theorem 3.12. We are assuming that when m is sufficiently large, [f^{m}(γ)] lifts to a loop in the covering space G_{V} of G corresponding to a vertex group V of T.

It follows from Lemma 4.14 that the splitting subpaths of these lifts have endpoints independent of m (for large m) and also that the subpaths corresponding to blocks [f^{k}(u_{i})] are loops for large k. We now claim that this is true for all k and that paths [f^{−k}(u_{i}^{−1})] also lift to loops based at the same points. Indeed, if u_{i} is fixed by f, then there is nothing to prove, and if it is not, then the group generated by u_{i}, its f-iterates and f^{−1}-iterates of u_{i}^{−1} is nonabelian and fixes a unique point in T, and thus is contained in a unique conjugate of V which must be the one represented by taking as basepoint the endpoints of the lift of [f^{k}(u_{i})] for large k. Similarly, the subpaths of the lifts of [f^{m}(γ)] corresponding to the exceptional paths E_{i}τ^{k}E_{j}^{−1} have the property that τ forms a loop in G_{V}.

We now iterate [f^{m}(γ)] backwards m times and conclude that γ lifts to a loop in G_{V} since the lift is obtained from the lift of [f^{m}(γ)] by inserting loops of the form f^{−k}(u_{i}^{−1}).

5 A Kolchin Theorem for UP G automorphisms

The rest of the paper is devoted to the proof of our main theorem.

Theorem 5.1. For every finitely generated UP G(F_{n}) group H there is a tree in X_{S} with all edge stabilizers trivial that is fixed by all elements of H

5.1 Bouncing sequences

We start by setting up our iteration scheme, as outlined in the introduction.

Definition 5.2. Let H be a UP G group with a fixed finite generating set

H = ⟨O_{1}, O_{2}, ⋯, O_{k}⟩

and let T_{0} be any simplicial tree in X_{S}. The bouncing sequence associated with the above data is the sequence of simplicial trees

T_{0}, T_{1}, T_{2}, ⋯

in X_{S} defined by

T_{i} = T_{i−1}O_{i}^{∞}

where subscripts of the O_{i}’s are taken mod k (see Theorem 4.7).

Notice that T_{i} is O_{i}-fixed. We will find a tree fixed by H by producing a bouncing sequence that is eventually constant. In that case the stable value is a tree fixed by all elements of H.

Example 5.3. Let F_{2} = ⟨a, b⟩, H = ⟨O⟩, with O represented by the automorphism h : F_{2} → F_{2} given by h(a) = a, h(b) = ba, and T_{0} is a free simplicial F_{2}-tree. Then T_{1} = T_{0}O^{∞} is the simplicial tree whose quotient graph has one vertex labeled ⟨a, a^{b}⟩ and one edge (loop) labeled ⟨a⟩. The loop is marked by b. This tree T_{1} is fixed by O so the bouncing sequence is eventually constant. However, T_{1} has nontrivial edge stabilizers, and in this case the iteration scheme fails to discover a tree as in the conclusion of Theorem 5.1.

Example 5.4. Let F_{3} = ⟨a, b, c⟩, H = ⟨O_{1}, O_{2}⟩, where O_{i} is represented by h_{i} given by h_{1}(a) = a, h_{1}(b) = ba, h_{1}(c) = c, h_{2}(a) = a, h_{2}(b) = b, h_{2}(c) = b^{−1}abc. Notice that the basis ⟨a, b, bc⟩ is better adapted to h_{2} since h_{2}(bc) = abc. Let T_{0} be a simplicial tree with trivial edge stabilizers whose quotient graph is the rose with two petals marked b and bc respectively, and the single vertex labeled ⟨a⟩. Then T_{1} = T_{0}O_{1}^{∞} has quotient graph a rose with petals marked b and c, and the vertex labeled ⟨a⟩. The tree T_{2} = T_{1}O_{2}^{∞} is a tree combinatorially isomorphic to T_{0}, i.e. T_{0} and T_{2} belong to the same simplex of X_{S}. Notice, however, that T_{0} and T_{2} are not homothetic: the ratio length(b)/length(bc) is smaller in T_{2} than in T_{0}. The bouncing sequence indeed bounces between two simplices in X_{S}, so it does not stabilize. All trees in the sequence are nongrowers under all elements of H. The ratios length_{T_{i}}(b)/length_{T_{i}}(bc) converge to 0.

The above examples indicate the difficulties of trying to find a tree as in the conclusion of Theorem 5.1 using bouncing sequences. We will show, however, that the strategy is successful provided we choose T_{0} carefully.

Theorem 5.5. Let H = ⟨O_{1}, O_{2}, ⋯, O_{k}⟩ be a UP G group. By F denote a maximal H-invariant proper free factor system. Let T_{0} be a simplicial tree with V(T_{0}) = F and trivial edge stabilizers. Then the bouncing sequence that starts with T_{0} is eventually constant, and the stable value is a simplicial tree with trivial edge stabilizers.

In the beginning it is not clear that F is nontrivial (although this is a consequence of Theorem 5.1). The existence of F is guaranteed by Proposition 2.10.

In Example 5.3 we started with F trivial. The bouncing sequence is eventually constant, but the edge stabilizers aren’t trivial. In this case we discover a larger invariant proper free factor system, namely ⟨a⟩ and its conjugates, by looking at the edge stabilizer.

In Example 5.4 we started with F consisting of ⟨a⟩ and its conjugates. The sequence did not even stabilize. However, we find a loop, namely b, that gets shorter and shorter in the bouncing sequence (compared to other elements). This tells us how to enlarge F to a larger invariant free factor system, namely ⟨a, b⟩ and its conjugates.

The proof of Theorem 5.5 occupies the rest of this section.

5.2 Bouncing sequences grow at most linearly

We now show that each tree in the bouncing sequence is either a nongrower, or it grows linearly (assuming the choice of T_{0} was made as in the statement of Theorem 5.5).

Proposition 5.6. Let H be a UP G group and let F be an H-invariant proper free factor system of maximal complexity. For O ∈ H, let f : G → G be a UR such that some subgraph G_{r} in the filtration of G represents F. Let E be an edge of G, u the corresponding suffix, and R the corresponding eigenray, i.e. R = E · u · [f(u)] · [f^{2}(u)] · · ·.

Then at least one of the following holds.

1. The eigenray R is eventually contained in G_{r}, or

2. [f(u)] = u.

Notice that F is contained in the vertex set of all trees in the bouncing sequence. Applying Lemma 4.20 to a UR f_{i} : G_{i} → G_{i} for O_{i} we see that if all suffixes of f_{i} are as in (1), then T_{i−1} is an O_{i}-nongrower, and otherwise it grows at most linearly.

Proof. Suppose the proposition fails for an edge E. We may assume that E is not crossed by any suffix of f, for if f(E′) = E′u′ and u′ crosses E then we may replace E by E′. Indeed, since u ≠ [f(u)], the eigenray R′ = E′u′f(u′) ⋯ contains arbitrarily long subpaths of the eigenray R = Euf(u) ⋯ by Proposition 4.10. Thus R′ crosses edges not in G_{r} infinitely often and it does not have periodic tail.

The edge E determines a splitting of F_{n} as either a free product or an HNN extension. Let F_{E} denote the resulting free factor system. Note that E is not an edge of G_{r} (otherwise u would be in G_{r}), and therefore F ≤ F_{E}. Also, F ≠ F_{E} since R is contained in F_{E} and it is not eventually contained in F.

The rest of the proof breaks into two cases. By Ĥ denote the preimage of H in Aut(F_{n}). Let e be the point in ∂F_{n} determined by a lift of R to the universal cover and let Ĥ{R} denote the set {{Ôe}|Ô ∈ Ĥ} (this set depends on R, but not on e).

Case 1: Ĥ\{R\} ≤ \overline{F_{E}} (equivalently, for all O ∈ H the ray [O(R)] crosses E only finitely many times). In this case the smallest free factor system containing F and whose closure contains Ĥ{R} (see Notation 2.14)) is proper (since it is contained in F_{E}), H-invariant (since both F and Ĥ{R} are), and it strictly contains F (since e is not in \overline{F}). This contradicts the choice of F.

Case 2: Ĥ\{R\} ≰ \overline{F_{E}}. We will show that in this case H contains an element of exponential growth. There is O ∈ H such that, when represented as a homotopy equivalence g : G → G, [g(R)] contains infinitely many E’s. The idea is that the image of a path containing E’s under a high power of f contains long initial subpaths of R and the image under g of a path with long initial subpaths of R contains lots of E’s. This feedback gives rise to exponential growth. We now make this more precise. Let R^{∗} denote an initial subpath of R chosen long enough so that [g(R^{∗})] contains 6 E^{±1}’s with occurrences of distance at least the BCC (see Section 2.2) for g away from its endpoints. Let M be the length of [g(R^{∗})]. Choose N so that for all immersed paths Ew and EwE^{−1} where w is a path in G_{r} of length no more than M we have that each of [f^{N}(Ew)] and [f^{N}(EwE^{−1})] starts with ER^{∗}. We claim that the element of H represented by gf^{N} has exponential growth.

Indeed, since F_{n} and the universal cover of G are quasiisometric, it is enough to find a loop σ in G such that the length of [(gf^{N})^{i}(g(σ))] grows exponentially in i. We show that σ can be taken to be any immersed based loop containing ER^{∗}. In this case, [g(σ)] contains [g(R^{∗})] except that perhaps subpaths containing endpoints of length less than the BCC for g may have been lost. In particular, [g(σ)] contains 6 E^{±1}’s separated by a distance of no more than M. So it contains at least two disjoint immersed subpaths of the form (EwE^{±1})^{±1} where w is a path in G_{r} of length no more than M. Since E is topmost, by Proposition 4.10, [f^{N}g(σ)] contains two disjoint subpaths of the form (ER^{∗})^{±1}. So, [gf^{N}g(σ)] contains 2 disjoint copies of g(R^{∗}) except for a loss of paths of length less than the BCC for g and so contains at least 2 disjoint subpaths each with 6 E^{±1}’s that are separated by a distance of no more than M. This pattern continues and the number of such subpaths containing 6 E^{±1}’s at least doubles with application of gf^{N}.

5.3 Bouncing sequences stop growing

Let O ∈ Out(F_{n}). Recall from Definition 4.8 that a tree T ∈ X_{S} is O-growing if there is γ ∈ F_{n} such that lim_{m→∞}ℓ_{T} (O^{m}([γ])) = ∞.

Proposition 5.7. Let H =< O_{1}, ⋯, O_{k} > be a UP G group, and let T_{0}, T_{1}, ⋯ be a bouncing sequence for H as in Theorem 5.5. Then all but finitely many elements of the sequence are O_{i}-nongrowing for i = 1, 2, ⋯, k.

Proof. For notational simplicity, we assume that H =< O_{1}, O_{2} > and show that in the sequence

T_{0}, S_{0} := T_{0}O_{1}^{∞}, T_{1} := S_{0}O_{2}^{∞}, S_{1} := T_{1}O_{1}^{∞}, T_{2} := S_{1}O_{2}^{∞}, ⋯

only finitely many elements are O_{1}-growing. We will identify homotopy classes of elements of F_{n} with immersed loops in marked graphs. Choose a UR f : G → G for O_{1} so that F is represented by an invariant subgraph G_{r}. Let U be the (finite) set of suffixes of f that are fixed by f. Set K = |U|. In fact, we will show that at most K of the T_{i}’s can be O_{1}-growing. Indeed, suppose that T_{i_{0}}, T_{i_{1}}, ⋯, T_{i_{K}} are O_{1}-growing with i_{0} < i_{1} < ⋯ < i_{K}. By Lemma 4.20, there is a suffix u_{K} of f such that ℓ_{T_{i_{K}}} (u_{K}) > 0. Thus u_{K} (and its f-iterates) are not elliptic in T_{0} and in particular the eigenray

⋯ [f^{s}(u_{K})] · [f^{s+1}(u_{K})] · [f^{s+2}(u_{K})] ⋯

is not eventually contained in G_{r}. Therefore, by Proposition 5.6, u_{K} is fixed by f. Applying Lemma 4.21 2(i_{K}−i_{K−1})−1 times, we see that there is a word w_{K} in O_{1} and O_{2} such that ℓ_{S_{i_{K−1}}}(w_{K}(u_{K})) > 0. Lemma 4.20 then provides a suffix u_{K−1}, such that ℓ_{T_{i_{K−1}}}(u_{K−1}) > 0 and, for large B, [f^{B}(w_{K}(u_{K}))] has a long string of u_{K−1}’s. Continuing in this fashion, we establish

Sublemma 5.8. There are words w_{i} ∈< O_{1}, O_{2} >, 1 ≤ i ≤ K and u_{i} ∈ U, 0 ≤ i ≤ K such that, for large B, [f^{B}(w_{i}(u_{i}))] contains a long string of u_{i−1}’s.

Two of the u_{i}’s are equal, say u_{0} = u_{K}. We next find an element in < O_{1}, O_{2} > of exponential growth, a contradiction that will establish the proposition.

Let C be as in Theorem 3.12(5) for the UR f and choose B so that the immersed based loop [f^{B}w_{i}(u_{i})] contains u_{i−1}^{C+2+A} where A is chosen so that the length of u_{i}^{A} is larger than twice the maximum of the BCC’s of the w_{i}’s (realized as homotopy equivalences on G). Then O_{1}^{B}w_{1} … O_{1}^{B}w_{K} has exponential growth. Indeed, we will show that if γ is any immersed path in G containing L disjoint occurrences of u_{i}^{C+2+A} then [f^{B}w_{i}(γ)] contains 2L disjoint occurrences of u_{i−1}^{C+2+A}. After all, when we apply w_{i} to γ, we obtain for each occurrence of u_{i}^{C+2+A} an occurrence of [w_{i}(u_{i}^{C+2})], the loss due to the cancellation constant for w_{i}. So, by Theorem 3.12(5), each such occurrence gives rise to a splitting and, upon application of f^{B}, we see [f^{B}w_{i}(u_{i}^{2})] which in turn contains two disjoint copies of u_{i−1}^{C+2+A}. This ends the proof of Proposition 5.7.

5.4 Edge stabilizers are eventually trivial

We need the following lemma. Recall that for us an arc in a tree is a subset homeomorphic to [0, 1].

Lemma 5.9. Suppose that T is a tree in X, O is a UP G automorphism, and T is O-nongrowing. Then every arc stabilizer of T′ = T O^{∞} also stabilizes an arc of T and it is O-invariant.

Proof. Let E =< e > be a nontrivial arc stabilizer of T′. Find an arc [v, w] in T′ that has an arc in common with F ix_{T} (E) and two elliptics x and y such that F ix_{T′}(x) ∩ [v, w] = {v} and F ix_{T′}(y) ∩ [v, w] = {w}. Then we have that x, y, e are elliptics in T′ and ℓ_{T′}(xy) > ℓ_{T′}(xe) + ℓ_{T′}(ye). Since T is O-nongrowing, for large m we have ℓ_{T′}(xy) = ℓ_{T} (O^{m}(xy)), etc. Therefore, ℓ_{T} (O^{m}(xy)) > ℓ_{T} (O^{m}(xe)) + ℓ_{T} (O^{m}(ye)), and O^{m}(x), O^{m}(y), O^{m}(e) are elliptics in T. Hence O^{m}(e) is an edge stabilizer of T for all large m. Since there are only finitely many conjugacy classes of edge stabilizers in T, it follows that the sequence O^{m}(e) takes only finitely many values, and is therefore constant (up to conjugacy) by Proposition 4.5, and the lemma follows.

Proposition 5.10. The bouncing sequence T_{0}, T_{1}, ⋯ for H in Theorem 5.5 eventually consists of trees that are O_{i}-nongrowing for all i and have trivial edge stabilizers. Further, for large j, the vertex stabilizers of T_{j} are Hinvariant and independent of j.

Proof. Eventually, the sequence consists of nongrowers by Proposition 5.7. Thus, eventually, the collection ∪V(T_{i}) of elliptics forms a nonincreasing sequence, by Proposition 4.22. It follows from Proposition 2.22 that eventually the sequence ∪V(T_{i}) stabilizes. By Lemma 5.9 eventually the collection of edge stabilizers stabilizes as well. Let T = T_{j} for some large j. Then ∪V(T) is H-invariant and contains ∪F, and all edge stabilizers of T are H-invariant.

It remains to show that all edge stabilizers of T are trivial. Suppose E is a nontrivial edge stabilizer of T. Let p be the smallest integer such that E fixes an edge of T_{p}. By our choice of T_{0}, p > 0. Lemma 5.9 implies that T_{p−1} is an O_{p}-grower (subscripts of O_{i}’s are taken mod k). We now apply Lemma 4.11 to a UR f : G → G for O_{p} and with G_{r} corresponding to F. Since ∪F ⊆ ∪V(T_{p−1}), there is an equivariant map ϕ : S → T_{p−1}, where the tree S is obtained from the universal cover of G by collapsing all edges that project into G_{r} as in Proposition 4.11. In particular, there is a suffix of f that is not elliptic in S, so the hypotheses of Proposition 4.11 are satisfied. Thus both S and T_{p−1} grow linearly under O_{p}. The map ϕ has finite BCC (by Proposition 2.4) Therefore the BCC of the induced equivariant map between SO_{p}^{m} and T_{p−1}O_{p}^{m}, after scaling by 1/m, converges to 0 as m → ∞. In the limit we obtain an equivariant map SO_{p}^{∞} → T_{p−1}O_{p}^{∞} = T_{p} with BCC = 0. We conclude that T_{p} is obtained from SO_{p}^{∞} by collapsing some edges and changing the metric on others. In particular, E fixes an edge of SO_{p}^{∞}. By Proposition 4.11, E contains a conjugate of a suffix of f not homotopic into G_{r}. Now note that the free factor system given by a topmost edge of G contains both F and E. Therefore, the smallest free factor system that contains both F and E is proper, and it is also H-invariant (since F and E are), and it properly contains F (since it contains E, while F doesn’t). This contradicts the choice of F.

5.5 Finding Nielsen pairs

Definition 5.11. Let T be a simplicial F_{n}-tree with all edge stabilizers trivial, and let H be a UP G group. Assume that all vertex stabilizers of T are O-invariant (up to conjugacy) for all O ∈ H. We say that two distinct nontrivial vertex stabilizers V and W of T form a Nielsen pair for H if for all O ∈ H and all lifts Ô of O to Aut(F_{n}) there exists γ ∈ F_{n} such that Ô(V) = V^{γ} and Ô(W) = W^{γ}. (It suffices to check this for one lift.)

For example, if T is fixed by H and V, W are nontrivial stabilizers of neighboring vertices, then V and W form a Nielsen pair.

The proof of the following facts is left to the reader.

Lemma 5.12. Let T and H be as in Definition 5.11.

• If T′ is another simplicial F_{n}-tree that has the same vertex stabilizers as T, then two vertex stabilizers V and W form a Nielsen pair in T if and only if they form a Nielsen pair in T′.

• If H = ⟨O_{1}, O_{2}, ⋯, O_{k}⟩ and two vertex stabilizers V and W of T form a Nielsen pair for ⟨O_{i}⟩ for all i, then they form a Nielsen pair for H.

Proposition 5.13. Let H =< O_{1}, ⋯, O_{k} > be a UP G(F_{n}) group and let T be a simplicial tree such that

• T has trivial edge stabilizers,

• V(T) is H-invariant, and

• T is O_{i}-nongrowing for all i.

Then T contains a Nielsen pair for H.

By h_{i} : G_{i} → G_{i} denote an RT T representative of O_{i} with an invariant subgraph G′_{i} corresponding to V(T), and whenever E is an edge outside G′_{i}, then h_{i}(E) = uEv for closed paths u and v in G′_{i}. Such a representative can be constructed from T O_{i}^{∞} (which is a tree with the same set of elliptics as T by Proposition 4.22, but is O_{i}-fixed) by passing to the quotient and blowing up vertices to UR’s of the restriction maps. As usual, the indices of h_{i}’s and O_{i}’s are taken mod k. Using Lemma 5.12 we shall detect that two vertex stabilizers V and W of T form a Nielsen pair for H by examining for every i whether they form a Nielsen pair for ⟨O_{i}⟩ in the tree T_{i} obtained from the universal cover of G_{i} by collapsing all edges that project to G′_{i}.

Edge paths P in G_{i} are of the form v_{0}P_{1}v_{1}P_{2} … P_{p}v_{p} where each P_{j} is an edge not in G′_{i} and each v_{j} is a path in G′_{i}. We call the elements v_{j} vertex elements (referring to the vertices of T). Some of the v_{j}’s could be trivial paths. When P is such a path, then the iterates h_{i}^{N}(P) have a similar form v_{0}^{(N)}P_{1}v_{1}^{(N)}P_{2} … P_{p}v_{p}^{(N)}. For each j the sequence v_{j}^{(N)} is eventually polynomial. We say that the vertex element v_{j} is inactive if v_{j}^{(N)} is independent of N. Otherwise, v_{j} is active. Of course, h_{i} and the edge path P are implicit in these definitions. Even trivial v_{j}’s could be active.

When i ≠ j there is a homotopy equivalence ϕ_{ij} : G_{i} → G_{j} given by markings. We may assume that this map sends vertices to vertices and restricts to a homotopy equivalence G′_{i} → G′_{j}. Let C be a constant larger than the BCC of any ϕ_{ij}. Let v be a vertex element in a path P in G_{i}. We can transfer P to another G_{j} using ϕ_{ij} and tightening. The path ϕ_{ij}(v) has length bounded above and below by a linear function in the length of v, and then at most 2C is added or subtracted due to the BCC. In particular, if the length of a vertex element in P is larger than some constant C_{0} > 2C, then this vertex element induces a well-defined vertex element in G_{j}. Short vertex elements in P can disappear and new short vertex elements can appear in [ϕ_{ij}(P)].

Choose constants C_{1}, C_{2}, ⋯, C_{7k} such that if a vertex element v has length ≤ C_{i} and is transferred to some other graph, then the induced vertex element has length ≤ C_{i+1}. Also, fix ϵ ∈ (0, 1/14k).

Lemma 5.14. For a sufficiently large integer m > 0 the following statements hold.

• Let N_{i} = 2^{2^{(7k−i+1)m}}, and let I_{i,l} be the interval

[(1 − lϵ)N_{i}, (1 + lϵ)N_{i}^{m}]

for i = 1, 2, ⋯, 7k, l = 1, 2, ⋯, 14k. Then I_{i,1} ⊂ I_{i,2} ⊂ ⋯ ⊂ I_{i,14k} and the intervals I_{i,14k} are pairwise disjoint for i = 1, 2, ⋯, 7k, and further, they are disjoint from [0, C_{7k}].

• If a vertex element v in an edge path P in G_{i} is active and has length ≤ (1 + 14kϵ)N_{i+1}^{m} (which is the right-hand endpoint of I_{i+1,14k}), then the h_{i}-iterated vertex element v^{(N_{i})} has length in I_{i,1}.

• If a vertex element v in an edge path P in G_{i} has length in I_{p,l} (l < 14k), then after transferring to G_{j} v induces a vertex element whose length belongs to I_{p,l+1}.

• If a vertex element v in an edge path P in G_{i} has length in I_{j,l} and if i > j and l < 14k, then the iterated vertex element v^{(N_{i})} in h_{i}^{N_{i}}(P) has length in I_{j,l+1}.

We think of the first index in intervals I_{i,l} as measuring the order of magnitude of lengths of vertex elements. The second index is present only for technical reasons: there is a slight loss when transferring from one graph to another (bullet 3), and when applying “lower magnitude maps” (bullet 4).

Proof of Lemma 5.14. To see that the right-hand endpoint of I_{i+1,14k} is to the left of the left-hand endpoint of I_{i,14k} we have to show that

(1 + 14kϵ)2^{2^{(7k−i)m}+m} < (1 − 14kϵ)2^{2^{(7k−i+1)m}}

i.e. that

2^{[2^{(7k−i+1)m}−2^{(7k−i)m}−m]} > \frac{1 + 14kϵ}{1 − 14kϵ}

That the latter inequality holds for large m follows from the observation that the exponent of the left-hand side

2^{(7k−i)m}(2^{m} − 1) − m

goes to infinity as m → ∞.

It follows from Theorem 3.12(4) that there are polynomials Q_{i} and R_{i} with nonnegative coefficients such that whenever v is an active vertex element in a path P in G_{i}, then the length of v^{(N)} is in the interval [N − R_{i}(|v|), (1 + |v|)Q_{i}(N)]. The proof now reduces to the fact that exponential functions grow faster than polynomial functions. For example, the second bullet amounts to the inequalities

N_{i} − R_{i}((1 + 14kϵ)N_{i+1}^{m}) > (1 − 14kϵ)N_{i}

and

(1 + (1 + 14kϵ))N_{i+1}^{m}Q_{i}(N_{i}) < (1 + 14kϵ)N_{i}^{m}

If we assume without loss of generality that R_{i}(x) = x^{d} then the first inequality simplifies to

\frac{N_{i}}{N_{i+1}^{m+d}} > \frac{(1 + 14kϵ)^{d}}{14kϵ}

Again, the left-hand side amounts to 2^{exp} with

exp = 2^{(7k−i)m}(2^{m} − m − d)

and it goes to infinity as m → ∞. The proof of the second inequality and of the other claims in the lemma are similar. (For the third bullet use the fact that there is a linear function L such that if w is a vertex element of a path P′ induced by a vertex element v of a path P, then the length of w is bounded by L(|v|).)

We will argue that if there are no H-Nielsen pairs in T, then the element O_{7k}^{N_{7k}} ⋯ O_{2}^{N_{2}}O_{1}^{N_{1}} ∈ H has exponential growth.

Start with an immersed loop P_{1} in G_{1} that is not contained in G′_{1} and all of whose vertex elements have length ≤ C_{1}. This loop is the first generation. Then apply h_{1}^{N_{1}} to obtain h_{1}^{N_{1}}(P_{1}) and transfer this new loop via ϕ_{12} to G_{2}. The resulting loop P_{2} is the second generation. Then apply h_{2}^{N_{2}} and transfer to G_{3} to obtain the third generation loop P_{3} etc. The loop P_{7k} whose generation is 7k lives in G_{7k}. Then repeat this process cyclically: apply h_{7k}^{N_{7k}} and transfer to G_{1} to get a loop P_{7k+1} of (7k + 1)^{st} generation etc.

Suppose that v is a vertex element of some P_{i}. If v^{(N_{i})} has length ≥ C_{0}, then v^{(N_{i})} induces a well-defined vertex element v′ in P_{i+1}. We say that v gives rise to v′.

We will now label some of the vertex elements of the P_{i}’s with positive integers. Consider maximal (finite or infinite) chains u_{1}, u_{2}, ⋯ of vertex elements such that u_{i} gives rise to u_{i+1}. In particular, there is an integer s such that u_{i} is a vertex element of P_{i+s} for i ≥ 1. If the length of the chain is ≥ 7k, then label u_{i} by the integer i. If the chain has < 7k vertex elements, we will leave all of them unlabeled. All labels > 1 in P_{i} correspond to unique labels in P_{i−1}. A birth is the introduction of label 1. A death is an occurrence of a labeled vertex element that does not give rise to any vertex elements in the next generation. Any labeled vertex element can be traced backwards to its birth. Traced forward, any labeled vertex element either eventually dies, or lives forever (and the corresponding label goes to infinity).

Lemma 5.15. If a vertex element v in some P_{i} is not labeled, then v is h_{i}-inactive and its length is ≤ C_{7k}.

Proof. The first element v_{1} of a maximal chain v_{1}, v_{2}, ⋯, v_{s}, s < 7k, must have length ≤ C_{1}. Indeed, assume not. Say v_{1} is a vertex element in P_{i+1}. By the choice of P_{1} we must have i ≥ 1. Transferring to G_{i} v_{1} induces a vertex element v′ of length > C_{0}. Now v′ = w^{(N_{i})} and w gives rise to v_{1}, so the chain wasn’t maximal.

If all v_{i}’s are inactive, then the claim about the length follows from the definition of constants C_{i}. If v_{i} is the first active element of the chain, then v_{i+1} has length in I_{i,2} by the second bullet of Lemma 5.14. With each generation the second index of the interval increases by two until 7k generations are complete (by bullets 3 and 4) or its length increases in length to some I_{j,2} with j < i by Property 2 and its life continues at least 7k more generations. This contradicts s < 7k.

Lemma 5.16. If two vertex elements in P_{i} are labeled with no labeled vertex elements between them, then either at least one dies in the next < k generations, or a birth occurs between them in the next < k generations.

Proof. If not, then the path between two such vertex elements is a Nielsen path (i.e. its lift to T connects two vertices whose stabilizers form a Nielsen pair).

Lemma 5.17. Consider the cyclically ordered set of labels in each P_{i}.

• If two labels are adjacent, at least one is < 3k.

• If two labels have one label between them, then at least one is < 4k.

• If two labels have two labels between them, then at least one is < 5k.

• If two labels have three labels between them, then at least one is < 6k.

Proof. Let a and b be two adjacent labels in some P_{i} with a, b ≥ 3k and assume that i is the smallest such i. Consider the ancestors of the two labels. According to Lemma 5.16 a death must occur between the two in some P_{i−s} with s < k. Thus in P_{i−s} we have labels ⋯ (a − s) ⋯ x ⋯ (b − s) ⋯ and x ≥ 7k. The dots between (a − s) and (b − s) are vertex elements that die before reaching P_{i}, and their labels are therefore ≥ 6k. By our choice of i we conclude that x is the only label between (a − s) and (b − s). Now consider further ancestors of (a − s), x, and (b − s). Again by Lemma 5.16 a death must occur between vertex elements labeled (a − s) and x in some P_{i−s−t} with t < k. We thus have two adjacent labels ≥ 5k in P_{i−s−t}, contradicting the choice of i.

Now suppose that in some P_{i} we have labels ⋯ axb ⋯ and a, b ≥ 4k. By the first bullet we must have x < 3k. If a death occurs between a and x, or between b and x, in the previous k generations, then we obtain a contradiction to the first bullet. If not, then by Lemma 5.16 we conclude that x < k and then we have adjacent labels a − x − 1 and b − x − 1 in P_{i−x−1} contradicting the first bullet.

Proofs of the last two bullets are analogous.

Proof of Proposition 5.13. Suppose that there are no H-Nielsen pairs in T. Let C_{0}, C_{1}, ⋯, C_{7k} and ϵ be constants as explained above. Let m be an integer satisfying Lemma 5.14, and consider the labeling of vertex elements in paths P_{i} as above. The fact that O_{7k}^{N_{7k}} ⋯ O_{2}^{N_{2}}O_{1}^{N_{1}} ∈ H grows exponentially now follows from the observation that the number of labels in P_{i+k} is at least equal to the number of labels in P_{i} multiplied by 5/4. Indeed, consider the labels in P_{i} that will die before reaching P_{i+k}. All such labels have to be ≥ 6k (since a vertex element cannot die before reaching the ripe old age of 7k). By Lemma 5.17, any two such labels have at least 3 labels a, b, and c between them. By Lemma 5.16, there will be at least one birth between a and b and at least one birth between b and c between generations i + 1 and i+k. Thus the number of deaths is at most a quarter of the number of labels in P_{i}, and the number of births is at least twice the number of deaths. The above inequality follows.

5.6 Distances between the vertices

Consider the bouncing sequence as in Theorem 5.5. Eventually, for j ≥ j_{0}, T_{j} is O_{i}-nongrowing for i = 1, 2, ⋯, k and the vertex groups of T_{j} are H-invariant. In particular, the collection of vertex stabilizers of T_{j} does not depend on j. For j ≥ j_{0} we define the metric on T_{j+1} = T_{j}O_{j+1}^{∞} by ℓ_{T_{j+1}}(γ) = ℓ_{T_{j}}(O_{j+1}^{N}(γ)) for large N (that is, we are taking the limit in the unprojectivized space of trees). By Proposition 5.13 there is an H-Nielsen pair in T_{j} for j ≥ j_{0}.

Lemma 5.18. Let V and W be two vertex stabilizers of T_{j_{0}} and let d_{j} denote the distance between the vertices in T_{j} fixed by V and W. If V and W form a Nielsen pair for H, then d_{j_{0}} = d_{j_{0}+1} = d_{j_{0}+2} = · · ·.

Proof. Choose nontrivial elements v ∈ V and w ∈ W. The distance between the vertices in T_{j} fixed by V and W equals \frac{1}{2}ℓ_{T_{j}}(vw) and the distance in T_{j+1} is analogously \frac{1}{2}ℓ_{T_{j+1}}(vw). The latter number can be computed as \frac{1}{2}ℓ_{T_{j}}(Ô_{j+1}^{N}(v)Ô_{j+1}^{N}(w)) for large N, where Ô_{j+1} denotes a lift of O_{j+1} to Aut(F_{n}) (since T_{j} is O_{j+1}-nongrowing). This in turn equals the distance in T_{j} between the vertices fixed by Ô_{j+1}^{N}(V) and Ô_{j+1}^{N}(W). But that equals the distance between the vertices fixed by V and W since V and W form a Nielsen pair for ⟨O_{j+1}⟩.

Lemma 5.19. Let D_{j} ⊂ ℝ denote the set of distances between two distinct vertices in T_{j} with nontrivial stabilizer, j ≥ j_{0}. Then

(1) D_{j} is discrete,

(2) D_{j} ⊇ D_{j+1} for all j ≥ j_{0},

(3) there are finitely many F_{n}-equivalence classes of paths P joining two vertices of T_{j} with nontrivial stabilizer and with length(P) = min D_{j},

(4) if V and W are two nontrivial vertex stabilizers of T_{j} such that the distance between the corresponding vertices is min D_{j}, then V and W form a Nielsen pair for ⟨O_{j}⟩.

(5) min D_{j} ≤ min D_{j+1}, and

(6) if min D_{j} = min D_{j+1} then any two nontrivial vertex stabilizers V and W in T_{j+1} realizing the minimal distance also realize minimal distance in T_{j}.

Proof. (1) Every element of D_{j} is a real number that can be represented as a linear combination of (finitely many) edge lengths of T_{j} with nonnegative integer coefficients. Hence D_{j} is discrete.

(2) Every element of D_{j+1} has the form \frac{1}{2}ℓ_{T_{j}}(Ô_{j+1}^{N}(v)Ô_{j+1}^{N}(w)) (see the proof of Lemma 5.18) and hence occurs also as an element of D_{j}.

(3) Let P be such a path. The quotient map T_{j} → T_{j}/F_{n} is either injective on P or identifies only the endpoints of P, hence there are only finitely many possible images of P in the quotient graph. If two such paths have the same image, then they are F_{n}-equivalent.

(4) Since O_{j} fixes T_{j}, for any lift Ô_{j} ∈ Aut(F_{n}) of O_{j} we can choose an Ô_{j}-invariant isometry ϕ : T_{j} → T_{j}. By Proposition 4.19 and Lemma 4.18 ϕ induces identity in the quotient graph. Therefore the immersed path P joining the two vertices is mapped by ϕ to a translate of itself (we are using the fact that all interior vertices of P have trivial stabilizer).

(5) is a consequence of (2).

(6) Choose a lift Ô_{j+1} ∈ Aut(F_{n}) of O_{j+1}. The distance between the vertices corresponding to V and W has the form \frac{1}{2}ℓ_{T_{j}}(Ô_{j+1}^{N}(v)Ô_{j+1}^{N}(w)) for large N. It follows that for large N the immersed path P_{N} joining vertices in T_{j} corresponding to Ô_{j+1}^{N}(V) and Ô_{j+1}^{N}(W) has length min D_{j}. By (4), V and W form a Nielsen pair for h_{j+1} and therefore the paths P_{N} are translates of each other and have length min D_{j}.

5.7 Proof of Theorem 5.5

We are now ready for the proof of Theorem 5.5. For the reader’s convenience we first restate it.

Theorem 5.5. Let H = ⟨O_{1}, O_{2}, ⋯, O_{k}⟩ be a group in UPG. By F denote a maximal H-invariant proper free factor system. Let T_{0} be a simplicial tree with V(T_{0}) = F. Then the bouncing sequence that starts with T_{0} is eventually constant, and the stable value is a simplicial tree with trivial edge stabilizers.

Proof. The sequence eventually consists of nongrowers by Proposition 5.7. Then, eventually, the vertex stabilizers are independent of the tree in the sequence and all edge stabilizers are trivial by Proposition 5.10. By Proposition 5.13 these advanced trees contain Nielsen pairs for H. By Lemma 5.18 it follows that the numbers min D_{j} of Lemma 5.19 are bounded above and hence stabilize. Say min D_{j+1} = min D_{j+2} = ⋯ = min D_{j+k}. Let V and W be two nontrivial vertex stabilizers in T_{j+k} that realize min D_{j+k}. By Lemma 5.19 V and W form a Nielsen pair for every ⟨O_{i}⟩, and hence for H. Let P be the immersed path joining the corresponding vertices. If P projects onto the quotient graph, then this quotient graph has one edge and T_{j+k} is fixed by H. If P does not project onto the quotient graph, we obtain a contradiction by collapsing P and its translates and thus constructing an H-invariant proper free factor system strictly larger than F.

6 Proof of the main theorem

In this section we show that Theorem 5.1 implies Theorem 1.1.

We start with an immediate consequence of Theorem 5.1.

Proposition 6.1. Every finitely generated UP G group H lifts to a group Ĥ ⊂ Aut(F_{n}).

Proof. Let T be a simplicial F_{n}-tree with trivial edge stabilizers fixed by all elements of H. By collapsing orbits of edges we may assume that T has only one orbit of edges (the collapsing is possible by Proposition 4.19). Fix an edge e ⊂ T. Since O ∈ H fixes T, there is a lift Ô ∈ Aut(F_{n}) of O and a Ô-equivariant isomorphism f : T → T. We may choose Ô and f so that f(e) = e, and this choice is unique. The set {Ô|O ∈ H} is a group and gives the desired lift to Aut(F_{n}).

Recall from the introduction that for a filtered marked graph G the set of upper triangular homotopy equivalences of G up to homotopy relative to the vertices is denoted by Q.

Lemma 6.2. Q is a group under the operation induced by composition.

Proof. Since the composition of upper triangular homotopy equivalences is clearly upper triangular, it suffices to show that if f is upper triangular, then there exists an upper triangular g such that fg(E_{i}) and gf(E_{i}) are homotopic rel endpoints to E_{i} for 1 ≤ i ≤ K. We define g(E_{i}) inductively starting with g(E_{1}) = E_{1}. Assume that g is defined on G_{i−1} and that fg(E_{j}) and gf(E_{j}) are homotopic rel endpoints to E_{j} for each j < i. If f(E_{i}) = v_{i}E_{i}u_{i}, define g(E_{i}) = v′_{i}E_{i}u′_{i} where u′_{i} equals r(u_{i}) with its orientation reversed and v′_{i} equals r(v_{i}) with its orientation reversed. Since v_{i} is a path in G_{i−1} with endpoints at vertices, fg(v_{i}) is homotopic rel endpoints to v_{i}. Thus f(v′_{i}) is homotopic rel endpoints to v_{i} with its orientation reversed and v_{i}f(v′_{i}) is homotopic rel endpoints to the trivial path. A similar argument shows that u_{i}f(u′_{i}) is homotopic rel endpoints to the trivial path and hence that fg(E_{i}) = f(v′_{i})v_{i}E_{i}u_{i}f(u′_{i}) is homotopic rel endpoints to E_{i}. A similar argument showing that gf(E_{i}) is homotopic rel endpoints to E_{i} completes the proof.

Proof that Theorem 5.1 implies Theorem 1.1. Let T be an H-fixed tree with trivial edge stabilizers. As in the proof of Proposition 6.1 we may assume that all edges of T are translates of an edge e. There are two cases depending on whether or not the endpoints a and b of e are in the same F_{n}-orbit. We will first consider the case that they are in distinct orbits, i.e. T/F_{n} is an arc. By A and B denote the stabilizers of a and b respectively. By induction on the rank, there exist desired representatives G_{a} and G_{b} for H|_{A} and H|_{B} respectively. We define G to be the disjoint union of G_{a} and G_{b} with an edge E connecting a vertex of G_{a} and a vertex of G_{b}. We choose a filtration of G so that E is the highest edge, and so that this filtration induces the given once on G_{a} and G_{b}. For O ∈ H let Ô ∈ Aut(F_{n}) and f : T → T be as in the proof of Proposition 6.1. Let T_{0} be a free simplicial F_{n}-tree and f_{0} : T_{0} → T_{0} a Ôequivariant map. The triple (T ×_{F_{n}} T_{0}, (orbit of a)×_{F_{n}} T_{0}, (orbit of b)×_{F_{n}} T_{0}) is naturally homotopy equivalent to the triple (G, G_{a}, G_{b}), and under this homotopy equivalence the map f ×_{F_{n}} f_{0} : T ×_{F_{n}} T_{0} → T ×_{F_{n}} T_{0} induces a representative f_{O} of O on G that keeps G_{a} and G_{b} invariant and sends E across itself only once. By induction, there is a homotopy independent of O supported in a small neighborhood of G_{a} ∪ G_{b} such that f_{O} is upper triangular and such that the restrictions to G_{a} and G_{b} satisfy the conclusions of Theorem 1.1.

We now claim that if A and B are nonabelian, then the collection of f_{O}’s provides the desired lift to Q. We first argue that if O ∈ H then f_{O^{−1}}f_{O} is homotopic to the identity rel vertices. This map is freely homotopic to the identity and by the inductive hypothesis it is homotopic rel vertices to a map g : G → G that is identity on G_{a} ∪ G_{b} and maps E to a path of the form vEu where v and u are closed geodesic paths in G_{a} and G_{b} respectively. It remains to show that u and v are trivial paths. Suppose for example that u is nontrivial. We regard the endpoints of E as the basepoints for G_{a} and G_{b}. Then we may choose closed paths α and β in G_{a} and G_{b} so that α does not commute with u and so that β is nontrivial. The closed loop EαE^{−1}β is sent by g to vEuαu^{−1}E^{−1}v^{−1}β. Since the two loops are freely homotopic, we conclude that u and α commute, contradicting the choice of α. One similarly argues that f_{O_{1}}f_{O_{2}} is homotopic to f_{O_{1}O_{2}} thus proving the claim in the case that A and B are nonabelian.

Next suppose that A is abelian and B nonabelian. Then G_{a} is a circle with a single edge α and each f_{O} sends E to a path of the form α^{m(O)}Eu(O). Define a new filtered graph G′ = G_{b} ∪ E′ where E′ is a loop based at the basepoint of G_{b} with the filtration defined so that E′ is topmost and the induced filtration on G_{b} is unchanged. Define the representative f′_{O} : G′ → G′ of O to agree with f_{O} on G_{b} and to send E′ to u(O^{−1})E′u(O). Another way to describe G′ is that it is the result of replacing the “balloon” E ∪ α with the single loop E′ corresponding to E^{−1}αE. The collection {f′_{O}} forms the desired lift.

If both A and B are abelian, then H is trivial (by the preceding argument) and we can take G to be the rose with two petals.

In the case when T/F_{n} is a circle, i.e. each vertex of T is a translate of a, we can construct G from G_{a} by attaching a topmost loop E to a vertex. The details are entirely analogous to the above discussion of the nonabelian case and are left to the reader.

From the above discussion it follows that G contains a (unique) maximal tree such that all edges in the complement are loops, and furthermore (when n > 1) each vertex belongs to at least two edges not in the tree. If V is the number of vertices in G, then G has V − 1 + n edges and n ≥ 2V. Thus V − 1 + n ≤ \frac{3n}{2} − 1 as required.

References

[AB87] R. Alperin and H. Bass, Length functions of group actions on λtrees, (S.M. Gersten and J.R. Stallings, eds.), Annals of Math. Studies, Princeton Univ. Press, vol. 111, 1987.

[BF91] M. Bestvina and M. Feighn, Bounding the complexity of simplicial group actions on trees, Invent. Math. 103 (1991), 449–469.

[BF92] M. Bestvina and M. Feighn, Outer limits, preprint, 1992.

[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}) III: Solvable Subgroups, preprint, 1996.

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

[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.

[CL95] M. Cohen and M. Lustig, Very small group actions on ℝ-trees and Dehn twist automorphisms, Topology 34 (1995), 575–617.

[CM87] M. Culler and J. Morgan, Group actions on ℝ-trees, Proc. London. Math. Soc. 55 (1987), 571–604.

[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.

[GL95] D. Gaboriau and G. Levitt, The rank of actions on real trees, Ann. Sci.École Norm. Sup. 28 (1995), no. 4, 549–570.

[Hop43] H. Hopf, Enden offene Raume und unendliche diskontinuierliche Gruppen, Comment. Math. Helvet. 16 (1943), 81–100.

[Jia] R. Jiang, Collapses of graphs of groups, preprint.

[Pau88] F. Paulin, Topologie de Gromov équivariant, structures hyperboliques et arbres réels, Invent. Math. 94 (1988), 53–80.

[Ser80] J. P. Serre, Trees, Springer-Verlag, 1980.

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

[Sho91] H. Short, Quasiconvexity and a theorem of Howson’s, Group theory from a geometrical viewpoint (Trieste 1990), World Sci. Publishing, 1991, pp. 168–176.

[Sko] R. Skora, Deformations of length functions in groups, preprint.

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

[Whi91] T. White, Fixed points of finite groups of free group automorphisms, Proc. AMS 118 (1991), no. 3, 681–688.