The Tits Alternative for Ii:
A Kolchin Type Theorem
preliminary version
Contents
1 Introduction and Outline
Recent years have seen a development of the theory for , the outer automorphism group of the free group of rank , that is modelled on NielsenThurston 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 , 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 , 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 whose induced automorphism of is unipotent. We say that such an outer automorphism is unipotent; we also say that is a (or just a ) outer automorphism. A subgroup of is called a subgroup if each element is . We prove (Proposition 3.5) that any polynomially growing outer automorphism that acts trivially in homology is unipotent. Thus every subgroup of polynomially growing outer automorphisms has a finite index 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 . Recall [CV86] that a marked graph is a graph (1dimensional CWcomplex) equipped with a homotopy equivalence from the rose with petals (whose fundamental group is permanently identified with ). A homotopy equivance on a marked graph induces an outer automorphism of the fundamental group of and therefore an element of ; we say that is a representative of .
Suppose that is a marked graph and that is a filtration of where is obtained from by adding a single edge . A homotopy equivalence is upper triangular with respect to the filtration if each where and are loops in . If the choice of filtration is clear then we simply say that is upper triangular. We refer to the ’s and ’s as suffixes and prefixes respectively.
An outer automorphism is if and only if it has a representative that is upper triangular with respect to some filtered marked graph (see Section 3).
For any filtered marked graph let be the set of upper triangular homotopy equivalences of up to homotopy relative to the vertices of . By Lemma 6.2, is a group under the operation induced by composition. There is a natural map from to . We say that a subgroup of is filtered if it lifts to a subgroup of for some filtered marked graph. We can now state our main theorem.
Theorem 1.1.
(Kolchin Theorem for ). Every finitely generated subgroup of is filtered. The number of edges of the filtered marked graph can be taken to be bounded by for .
It is an interesting question whether or not the requirement that be finitely generated is necessary or just an artifact of our proof. Question: Is every group in contained in a finitely generated group?
Remark 1.2.
In contrast to unipotent mapping class subgroups, which are all finitely generated and abelian, subgroups of can be quite large. For example, if is the rose on petals, then a filtration on corresponds to an ordered basis of and elements of correspond to automorphisms of the form with . When , the image of in contains .
This is the second of two papers in which we establish the Tits Alternative for .
Theorem (The Tits Alternative for ) .
Let be any subgroup of . Then either is virtually solvable, or contains .
For a proof of a special (generic) case, see [BFH95]. The relation between Theorem 1 and Theorem 1.1 is captured by the following corollary.
Corollary 1.3.
Every group either contains or is solvable.
Proof.
First assume that is finitely generated. By Theorem 1.1 there is a marked graph , a filtration and a subgroup of that projects isomorphically onto . Let be the largest parameter value for which every element of restricts to the identity on . If , then is the trivial group and we are done. Supppose then that . By construction, each element of satisfies where and are paths (that depend on the element of ) in and are therefore fixed by every element of . The suffix map , which assigns the suffix to the element of , is therefore a homomorphism. If the image of contains , then contains and we are done. If the image of has rank one, then it can be identified with and there is no loss in replacing with the kernel of . If the image of has rank zero, then is the kernel of . A similar argument using prefixes instead of suffixes, allows us to replace with the subgroup of that has no nontrivial prefixes or suffixes for and so restricts to the identity on . Upward induction on now completes the proof when is finitely generated. In fact, this argument shows that is polycyclic and that the length of the derived series is bounded by for .
When is not finitely generated, it can be represented as the increasing union of finitely generated subgroups. If one of these subgroups contains , then so does , and if not then is solvable with the length of the derived series bounded by .∎
Proof of the Tits Alternative for . Theorem 1.3 of [BFH96a] asserts that if does not contain , then there is an exact sequence
with a finitely generated free abelian group and with all elements of of polynomial growth.
By passing to a subgroup of of finite index that acts trivially in homology, we may assume that is a group (see Proposition 3.5). Since does not contain , by Corollary 1.3, is solvable, and thus is also solvable. ∎
In [BFH96b] we strengthen the Tits Alternative for further by proving:
Theorem (Solvable implies abelian) .
A solvable subgroup of has a finitely generated free abelian subgroup of index at most .
The rank of an abelian subgroup of is for [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 subgroup of there is a nontrivial simplicial tree with all edge stabilizers trivial that is fixed by all elements of .
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 . 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 of very small simplicial trees (for a definition see Section 2.1). There is a natural (right) action of on (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 automorphism on . Specifically, we show in Theorem 4.7 that under iteration every tree converges to a tree (necessarily fixed by the automorphism). This fact is a consequence of Theorem 4.2, which asserts that the sequence of iterates of any under a automorphism eventually behaves like a polynomial (for a definition, see Section 4.1; in particular the function coincides with a polynomial for large ). In addition, we show that the asymptotic behavior of the sequence is largely determined by a finite number of eigenrays of that correspond to the eigendirections in the linear case.
Section 5 is the heart of the proof. Let be a nontrivial simplicial tree with trivial edge stabilizers such that the set of elliptic elements (a free factor system) is invariant and maximal among all  invariant free factor systems. For notational simplicity let us assume that is generated by two elements, and . Then consider the sequence of simplicial trees defined inductively by if is even and by if 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 or 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 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 and are elliptic in . The second step is to show that starting from this 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 is independent of (for large ). By the unipotent assumption, the vertex stabilizers of are fixed by (rather than permuted) up to conjugacy (see Proposition 4.15). This however does not imply that is fixed by and (for examples see Section 5). In the third step we examine the edge stabilizers of . If some are trivial and some nontrivial, then by collapsing those with nontrivial stabilizer we obtain a tree that contradicts the choice of . If they are all nontrivial, we examine the term of the sequence that gave rise to such edges and again find a larger proper free factor system invariant under . Therefore all edges of have trivial stabilizer. In the fourth and final step we observe that if is not fixed by and , then in the sequence an equivalence class of edges gets short compared to the average and there is again a larger proper free factor system invariant under . This last step is reminiscent of the development of NielsenThurston 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 ( may well contain ) but on constructing an element in 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 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 CullerVogtmann [CV86], to use spaces of trees to understand in much the same way that Teichmüller space and its compactification were used by Thurston and others to understand mapping class groups.
2 Trees
In this section, we collect the facts about real 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 tree 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 the subset of fixed by is either empty, a point, or an arc. The set of all projective classes of very small trees is denoted by and the subset of consisting of the projective classes of simplicial trees is denoted by . Both are topologized via the embedding into the infinitedimensional projective space, where is the set of all conjugacy classes in and ( is the translation length of in ). See [CM87] for a proof that is injective.
The automorphism group acts naturally on on the right by changing the marking. In terms of the length functions, the action is given by . Inner automorphisms act trivially and we have an action of . There is a natural invariant decomposition of into open simplices. The space can be identified [CL95] [CM87] with CullerMorgan’s compactification [CM87] of CullerVogtmann’s Outer Space [CV86].
2.2 Bounded cancellation constants
We will often need to compare the length of the same element of in different trees. The existence of bounded cancellation constants will usually suffice for this job.
Definition 2.1.
The bounded cancellation constant of an map , denoted , is the least upper bound of numbers with the property that there exist points with on the segment so that the distance between and the segment is .
In [Coo87] Cooper showed that if both and are free simplicial and minimal and is , then is finite. The bound given by Cooper depends on the Lipschitz constants of and of an map .
Below we generalize Cooper’s result to the case that the target tree is very small. For a map between metric spaces we denote by the Lipschitz constant of , i.e.
Lemma 2.2.
Suppose and are maps between minimal trees. Then
Proof.
(1) follows directly from definition.
(2) Choose with , and let be the point in closest to . Then
∎
Definition 2.3.
The covolume of a free simplicial and minimal tree , denoted , is the sum of the lengths of edges in .
Proposition 2.4.
Suppose is an map between free simplicial and minimal trees and . Assume is linear on each edge of . Then
Proof.
Proposition 2.5.
Suppose is a Lipschitz map from a free simplicial tree to a very small simplicial tree . Assume is linear on each edge of . Then .
Proof.
Represent 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 , every very small simplicial tree any map that is linear on edges has finite .
Proof.
By Lemma 2.2 it suffices to prove the proposition in the case that is the universal cover of a rose. Further, it suffices to construct an map with finite (since any two such maps are within bounded distance from each other). There is an embedding of into the space of very small trees. Indeed, let be a basis for and let denote the elements of word length at most 2. If is a nontrivial tree then the lengths of the elements of can’t all be 0 [CV86]. Thus, the set of all very small trees such that the sum of the lengths of the elements of equals 1 is homeomorphic to . Let be the universal cover of a rose in . There is a continuous choice of base point for each [Sko],[Whi91]. Let be the map that takes the vertex of to the base point of and is linear on the edges of . Since the topology on is the same as the based length function topology [AB87], the Lipschitz constant varies continuously. Since the topology on is the same as the equivariant GromovHausdorff topology, is lower semicontinuous [Pau88]. By Proposition 2.4, if 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 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 denote the set of finite nonincreasing sequences in . We allow the empty sequence. Well order lexicographically. For example, . In the cases that we consider, the sum of the elements in the set will be no more than . Thus, the sequence will be the largest element that we will consider and the smallest.
Definition 2.7.
If is a subgroup of then let denote the set of all subgroups of that are conjugate to , i.e. the conjugacy class of . A set of free factors of is a free factor system if there is a free factor of of the form such that . For convenience, we will always require that . Equivalently, a free factor system is the set of point stabilizers of a simplicial tree with trivial edge stabilizers. The complexity of is the element of obtained by arranging the positive numbers among in nonincreasing order. is proper if its complexity is less than .
Lemma 2.8.
If and are two free factor systems then is a free factor system.
Denote this free factor system by .
Proof.
Let denote a simplicial tree with trivial edge stabilizers and vertex stabilizers . Let denote a similar tree with respect to . For , consider the action of on . This gives a simplicial tree with vertex groups and trivial edge groups. Use this tree to blow up [Jia] the orbit of the vertex of stabilized by . We obtain a simplicial tree with trivial edge stabilizers and vertex stabilizers .∎
Notation 2.9.
If and are two sets of subsets of then we write if each is contained in some . If also then we write .
Proposition 2.10.
Let and be two free factor systems. If then
If additionally then and
Proof.
If and are free factors on such that then with equality if and only if . The lemma now follows easily.∎
Corollary 2.11.
Lemma 2.12.
Let be a (possibly infinite) set of subsets of . Then there is a free factor system of minimal complexity such that . Further, this system is unique.
Proof.
Clearly there is such a system, call it . If is another then so is but of smaller complexity. ∎
Corollary 2.13.
Notation 2.14.
Let denote the Hopf boundary [Hop43] of (which agrees with the Gromov boundary in this case). If is represented as the fundamental group of a graph , then may be identified with the space of geodesic rays in the universal cover of where we identify two rays if they eventually coincide. For a finitely generated subgroup , inclusion is a quasiisometric embedding (see Lemma 2.15 below) and so we may identify with a subset of . If is represented as subgraph of then may be identified with the subspace of geodesic rays that are eventually in the preimage of in . Let denote the subset of . For a set of finitely generated subgroups of let denote . If and are two sets of subsets of then we write if each is contained in some . If also then we write .
For a proof of the following lemma, in far greater generality, see [Sho91].
Lemma 2.15.
Let be finitely generated subgroups of .

The inclusion is a quasiisometric embedding.

.∎
Lemma 2.16.
Let be a set of subsets of . Then there is a unique free factor system of minimal complexity such that .
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 , it is important to get a precise picture of these stabilizers. In the case where 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 . For an tree , denotes the collection of its point stabilizers, and 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 . There is a bound depending only on to the number of conjugacy classes of point and arc stabilizers. The rank of a point stabilizer is no more than with equality if and only if is a rose and each edge of has infinite cyclic stabilizer.∎
Proposition 2.19.
There is a bound (depending only on ) to the length of any chain of proper inclusions of vertex groups.
Proof.
Let be a chain of proper containments of vertex groups with corresponding trees , , and . We will show that either or .
Let and be minimal subtrees of and respectively. Since the vertex groups of are precisely the intersection of the vertex groups of with , we see that has a vertex labelled and so . Similarly, . If then we are done, so assume these ranks are equal.
Using Theorem 2.18, the only remaining possibility is that orbit spaces of both and are roses of circles with all edges labeled by infinite cyclic groups. The number of orbits edges of may be computed as . (Indeed, in general if is a tree, its orbit space , and then .) Since there is an epimorphism
we have that . We will show that if then , a contradiction.
Consider the morphism that sends the vertex labelled to the vertex labelled . This map is well defined for if is the edge from to with stabilizer , then . Thus, is obtained from by a finite number of folds (after perhaps first subdividing ) [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 trees with vertex groups of rank that of .
Lemma 2.21.
Let . Then is the union of the maximal groups in each of which is a point stabilizer in .
Proof.
The lemma will follow if we show that every group fixes a point in . If is finitely generated then, by [Ser80, page 65], the restriction of the action of to can have a trivial length function only if there is a global fixed point. Thus we may assume that is not finitely generated. Hence, is an increasing union of noncyclic finitely generated subgroups each contained in some point stabilizer. A noncyclic group fixes at most one point of hence fixes a point.∎
Proposition 2.22.
There is a bound depending only on to the length of a sequence of inclusions
where each .
Proof.
Let be a bound on the length of a chain of proper inclusions of vertex groups of trees in . The existence of is guaranteed by Proposition 2.19. Let denote the set of conjugacy classes of maximal groups in . By Lemma 2.21, consists of conjugacy classes of point stabilizers. For , let denote the set of elements represented by . Let denote the subset of the power set of given by . Let be a bound to (see Theorem 2.18). We will show that .
Sublemma 2.23.
For every pair of integers the following holds with . Let be subsets of the power set of a fixed set . Assume that

if with then ,

for all , and

for all .
Then one of the following two possibilities occurs.

There are , , such that
and at least of these inclusions are proper.

For some , .
Proof.
Induction on . The case is clear. Now suppose that the lemma is true for . Choose arbitrary with . Consider chains of inclusions of length
If each chain contains a proper inclusion, then (1) holds. If not, then one of these chains, say the one with , consists of equalities. Now, remove from , . By the first bullet, the new collection satisfies the inductive hypothesis.∎
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
DefinitionProposition 3.1.
Let or , and let be a free module of finite rank. We say that an module endomorphism is unipotent if the following equivalent conditions are satisfied:

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

for some .
Proof.
It is clear that (1) implies (2). To see that (2) implies (1), assume that . We may assume that . The restriction of to the submodule is 0, and hence each is fixed by . In the case pass to a primitive submultiple if necessary to conclude that always contains an fixed basis element . The proof now concludes by induction on using the observation that the induced homomorphism also satisfies . ∎
Corollary 3.2.
Let or . Let be an module endomorphism, and let be an invariant submodule of which is a directsummand of . Then is unipotent if and only if both the restriction of to and the induced endomorphism on are unipotent.
Proof.
Evident, if we use (2) in and (1) in .∎
Corollary 3.3.
Let be unipotent. If is periodic, i.e. if for some , then is fixed, i.e. .
Proof.
First assume that . We may assume that . Let be the standard basis for . There is a surjective linear map given by , and lifts to the linear map , . For , the generalized eigenspace is defined to be
The linear map must map the generalized eigenspace onto (and all other generalized eigenspaces to 0). Since this space is onedimensional (and equals the eigenspace of ), it follows that and .
If , just tensor with . ∎
Corollary 3.4.
Let be unipotent. If is a direct summand which is periodic (i.e. for some ), then is invariant (i.e. ).
Proof.
The restriction of to is unipotent, so there is a basis element fixed by . By Corollary 3.3, . The proof concludes by induction on .∎
Proposition 3.5.
Let have all eigenvalues on the unit circle (i.e. grows polynomially). If the image of in is trivial, then is unipotent.
Proof.
We first argue that some power of is unipotent, i.e. that all eigenvalues of are roots of unity. Choose so that all eigenvalues of are close to 1. Then is an integer close to , and thus all eigenvalues of are equal to 1.
Let be the minimal polynomial for factored into irreducibles in . Let and . First note that each . For example, but since is minimal. If is not unipotent, then some , say , is not . Thus is the minimal polynomial for a nontrivial root of unity and so it divides for some . The matrix has nontrivial kernel (since its power vanishes on ). It follows that there is a nonzero integral vector such that but . Then is a nontrivial direct summand of , the restriction of to this summand is nontrivial and periodic, and the induced endomorphism of is identity. This contradicts the standard fact that the kernel of is torsionfree. ∎
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 is (or just ) if for each conjugacy class in the sequence of (reduced) word lengths of is bounded above by a polynomial.
We start by recalling the representatives for automorphisms found in [BH92].
Theorem 3.7.
[BH92] Every automorphism has a representative as a homotopy equivalence on a marked graph such that

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

There is a filtration of by invariant subgraphs such that for every edge the edge path crosses exactly one edge in and it crosses that edge exactly once.

If is an invariant free factor system, we can arrange that is represented by some . If is the identity on each conjugacy class in , we can arrange that on .
Definition 3.8.
The representative in Theorem 3.7 is called a relative train track () representative for .
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 automorphisms  the objects of central importance in this paper.
Definition 3.10.
An outer automorphism is a (or just ) automorphism if it is and its action in is unipotent.
We now recall a special case of an improvement of representatives from [BFH96a].
Recall that if is a RTT representative and is an edge path in then we write for the geodesic homotopic rel endpoints to . We also write for edge paths and in if for all and say that “splits”.
Definition 3.11.
Let be an representative. A path in with endpoints in the vertex set is Nielsen if . An exceptional path in is a path of the form
provided is a nontrivial Nielsen path and for some , , or
provided is a Nielsen path, , , and for some .
The following theorem follows easily from Theorem 6.8*** and Lemma 6.24*** of [BFH96a].
Theorem 3.12.
([BFH96a]) Suppose that is a automorphism, that is an invariant free factor system. Then there is an representative of with the following properties.

for some filtration element .

Each is the union of and a single edge satisfying for some closed path that crosses only edges in .

If is any path with endpoints at vertices, then there exists so that for each , splits into subpaths that are either single edges or exceptional subpaths.

is a bounded multiple of the edge length of .

There is a uniform constant so that if is a closed path in that is not a Nielsen path and is an immersed path, then at most copies of are cancelled when is tightened to .
Definition 3.13.
An representative satisfying 15 above is a unipotent representative or a . The based loops are suffixes of .
Note that (2) can be restated as
for all . The immersed infinite ray
is the eigenray associated to . Lifts of to the universal cover of are also called eigenrays. The subpaths of are sometimes referred to as blocks.
For example, the map on the rose with two petals labelled and given by , is a . For we may take in (3), since is a splitting into an edge and an exceptional (Nielsen) path. The map given by , , on the rose with three petals is not a since does not eventually split as in (3). Replacing by yields a of the same outer automorphism.
Definition 3.14.
Let be a . The height of an edgepath in is the smallest such that the path is contained in . A topmost edge in an edgepath of height is an occurrence of or in the edgepath.
Many arguments are inductions on height. The inductive step is based on the observation that a path of height splits at the initial (terminal) endpoints of each occurrence of ().
4 The dynamics of automorphisms
In this section we examine the dynamics of the action of automorphisms on conjugacy classes, free factor systems, and the space of very small trees.
4.1 Polynomial sequences
In this section we show that the sequence of iterates of a path under a automorphism behaves like a polynomial and use this to prove Theorem 4.7 which is fundamental in our approach.
Definition 4.1.
Let be a graph. A sequence of immersed paths in is said to be a polynomial sequence if it can be obtained from constant sequences of paths by finitely many operations described below.

(reindexing and truncation): for a polynomial sequence for some ,

(inversion):