STRUCTURE AND CONJUGACY FOR

AUTOMORPHISMS OF FREE GROUPS I

Martin Lustig

0. Introduction and statement of results

The purpose of this paper and the subsequent Part II (= sections 5 - 9)^{1} is to present a complete algorithmic solution of the following two problems, where F_{n} denotes a (non-abelian) free group F_{n} of finite rank n ≥ 2:

Conjugacy problem for automorphisms of F_{n}.

(a) Given automorphisms α, α′ ∈ Aut(F_{n}), does there exist an automorphism β ∈ Aut(F_{n}) such that α′ = βαβ^{−1} ?

(b) Given α, α′ ∈ Aut(F_{n}), does there exist β ∈ Aut(F_{n}) such that α′ = βαβ^{−1} up to inner automorphisms of F_{n} ?

A solution of these problems has been announced in [13], and solutions for special cases have been given in [4], [8], [9], [10] and [17]. Related structural informaton about automorphisms of free groups has been derived in [2] and in [18]. The solution presented here is a combinatorial one, and can (not just in principle) be programmed on a computer of standard nowadays capacities. For small cases it can well be performed by hand: It is efficient in the human sense, i.e. in most cases it requires few time, while we also can concoct some rare cases where all of the more sophisticated invariants presented here have to be computed in order to show that the difficulty in finding a conjugator is not just due to bad luck or insufficient persistence.

As automorphisms of free groups are enumerable, a “positive” machine, i.e. an algorithm which stops if a conjugator β as above is found, and keeps running otherwise, is given directly. All the difficulty stays in finding an analogous “negative” machine: This amounts to the exhibition of sufficiently many structural data which are both,

(1) invariant under conjugacy, and

(2) algorithmically computable.

Typeset by AMS-TEX

1also to appear in the Max-Planck preprint series. It is presently being brought into final form, compare [14] (M.L., December 15, 2000)

The main such structural data are minimal actions of F_{n} on a R I -tree T by isometries which are (projectively) α-invariant in the following sense: There exists a homothety H : T → T with stretching factor λ ≥ 1 such that α(w)H = Hw : T → T for all w ∈ F_{n}. The existence of such actions has been shown in [1], [12] and [19]. A general and geometric construction of such T has been presented in [6] and is rewiewed here in section 1. It is crucially based on the existence of a train track map f : Γ → Γ which represents the given α ∈ Aut(F_{n}), and T is completely described by means of a Perron-Frobenius eigenvector of the nonnegative geometric transitions matrix associated to f. We call such actions Perron-Frobenius actions of F_{n}.

The first goal of this paper is to show that there are no other α-invariant R I -tree actions with stretching factor λ > 1. In the case where α admits an absolute train track representative, this is done in sections 1 and 2. In order to treat the general case we introduce and study in section 3 train tracks with 2-cells (called Nielsen faces), which can be derived algorithmically from Bestvina-Handel’s relative train track representatives [3]. In section 4 we show the following result, which also contributes to a better understanding of the action of α on Culler-Vogtmann’s outer space CV_{n} and its boundary.

Theorem I. Every α-invariant action of F_{n} on an R I -tree T with stretching factor λ > 1 is Perron-Frobenius, for any α ∈ Aut(F_{n}).

In particular, any such R I -tree is given by a non-negative eigenvector with eigenvalue λ on any partial train track representative f : G → G with Nielsen faces of α, relative to a subspace of polynomial α-growth. The converse is also true.

We then define a special type of such actions, and we show that they are given by special graphical representatives of α which we call relative pseudo-Anosov maps. For every exponentially growing automorphism α there exists a non-empty finite family, derived algorithmically, of relativ pseudo-Anosov train track maps which represent all of the special invariant α-invariant actions. In section 5 we show that, if two such relative pseudo-Anosov maps f : G → G and f′ : G′ → G′ define the same R I -tree action of F_{n}, then there exists a conjugating map h : G → G′, i.e. hf = f′h up to differences in the vertex spaces and up to certain controlled homotopies involving the 2-cells. The crucial algorithmic insight here is that we can bound the length of the images of the edges a priory, depending only on data derived from f and f′.

In the polynomially growing case the situation is similar, but easier, as there is a unique canonical α-invarinat action on an R I -tree, this time with stretching factor λ = 1. It comes from a graph of groups decomposition of F_{n} as follows (see section 7 and 8):

Theorem II. Let α ∈ Aut(F_{n}) be polynomially growing, say of degree d ≥ 1, given by a relative train track representative. We can algorithmically derive a canonical graph-of-groups decomposition F_{n} = π_{1}G which is α-invariant. It is uniquely determined by the property that the vertex groups of G consist precisely of those elements which determine conjugacy classes in F_{n} which have polynomial growth of degree strictly smaller than d, under iteration of α. If d = 1, then all edge groups of G are cyclic, while in the case of quadratic or higher growth, d ≥ 2, they are trivial.

A major technical effort in our approach is needed to keep track of all data when passing from one stratum of G to the next lower one (given by the restriction of α to the stabilizers of the branch points of T), where each time the rank of the free group in question decreases strictly. For this purpose we introduce fix point pattern in section 6 and show in section 6 for exponentially growing α and in sections 7 and 8 for polynomially growing α how conjugacy of (orbits) of fixed point pattern can be decided algorithmically, modulo introducing new (orbits) of fixed point pattern for the next level of our recursion procedure. The details of this algorithm are presented in section 9.

It turns out that, after the right tools are developped, the exponentially growing case is easier to decide than the polynomial one, and the hardest among the polynomially growing is the periodic-linear case, treated in [9]. The stronger growth forces more rigidity, which makes it easier to read off computible invariants of the automorphism. For example, it follows from the methods presented here that the centralizer of an outer automorphism is virtually cyclic (i.e. essentially the subgroup generated by the automorphism itself), except for additional factors which are derived on the lowest, the linear level of our recursion procedure. In particular, a direct consequence of the work presented here is:

Corollary III. If for an outer automorphism α̂ ∈ Out(F_{n}) no conjugacy class [w] ⊂ F_{n} is fixed by α̂^{t}, (t ≥ 1), then the centralizer Cen(α̂) ⊂ Out(F_{n}) is virtually abelian.

Here the rank of the finite index abelian subgroup is given by the number of connected components of the canonical graph representing the p.o. set of the relative pseudo-Anosov strata of α with respect to the inclusion.

More generally, the methods and results developped in this paper have some direct applications to other questions on automrphisms: For example, one can derive rather easily a structural result about all virtually abelian subgroups of Out(F_{n}) much in the spirit of Corollary III above. Other applications concern the complete determination of the dynamics on ∂F_{n} induced by an automorphism α (joint work with G. Levitt) and a fast proof of P. Brinckmann’s result that α is hyperbolic (as defined by Gromov) if no conjugacy class in F_{n} has a periodic α-orbit.

Acknowledgments. I would like to thank Gilbert Levitt for many useful conversations which have directly and indirectly helped shaping this work. My thanks go also to Mladen Bestvina, Marshall Cohen and Karen Vogtmann for their interest and encouragement, and to University of Utah, Salt Lake City, Université P.Sabatier, Toulouse, Université S.Antipolis, Nice, and the Max-Planck Institut, Bonn, for their support and hospitality during several extended research stays, where most of this paper has been written. Finally I’d like to thank Yoav Moriah and Karen Vogtmann for motivating me properly to take on the final writing effort.

Part I: PERRON-FROBENIUS ACTIONS OF FREE GROUPS AND A STRUCTURE THEOREM FOR FREE GROUP AUTOMORPHISMS

The purpose of this Part I is a structural analysis for outer automorphisms of free groups which is in close analogy to (but more complicated than) the Nielsen Thurston classification of surface homeomorphisms. Algorithmic aspects play only a minor role in this Part I; we have tried to put the emphasis in our presentation primarily on the structural results and on the tools needed to understand them.

1. Invariant R I -trees through iteration of absolute train track maps

1.1. Let F_{n} be a free group of rank n ∈ N I , and let α ∈ Aut(F_{n}) be an automorphism of F_{n}. Let T be an R I -tree with a non-trivial minimal action of F_{n} by isometries, and let H : T → T be a homothety with stretching factor λ > 0. If for every w ∈ F_{n} one has

α(w)H = Hw : T → T

F_{n}-action on T α-invariant.

In [12] it has been shown that for every α ∈ Aut(F_{n}) there is an α-invariant minimal F_{n}-action on some non-trivial R I -tree, with trivial arc stabilizers and with λ ≥ 1.

The main goal of this and the following two sections is to determine all such α-invariant actions on R I -trees with small arc stabilizers and with λ > 1. We first recall a particular construction which leads to such actions, built on Perron-Frobenius eigenvectors of the transition matrix of a train track representative of α, and which are hence called here Perron-Frobenius actions. We prove in section 2:

Theorem 1.2. For any automorphism α ≠ 1 of F_{n} with an absolute train track representative every α-invariant small minimal action of F_{n} on an R I -tree with stretching factor λ > 1 is Perron-Frobenius.

In particular this shows that automorphisms which are represented by a train track map with irreducible transition matrix and eigenvalue λ > 1 have, up to rescaling, precisely one α-invariant R I -tree action with stretching factor strictly bigger than 1. This includes all irreducible automorphisms with irreducible powers.

The iteration tree

Throughout sections 1 and 2 of the paper we use the following notation:

Notation 1.3. Let α be an automorphism of F_{n}. Let Γ be a graph with π_{1}Γ = F_{n}, a free group of finite rank n ≥ 2, and let f : Γ → Γ be a p.l. homotopy equivalence which induces the outer automorphism of F_{n} defined by α. Let Γ̃ denote the universal covering of Γ (a tree !), equipped with the usual action of F_{n} by covering translations, and let f̃: Γ̃ → Γ̃ denote the lift of f which represents the automorphisms α ∈ Aut(F_{n}): For every w ∈ F_{n} one has

α(w)f̃ = f̃w : Γ̃ → Γ̃ .  (1)

1.4. For a graph Γ we define an edge length function L to be a map L : Edges(Γ) → R I _{≥0}. Every such function defines an F_{n}-equvariant pseudo-metric d on Γ̃, i.e. a function d : Γ̃ × Γ̃ → R I _{≥0} which differs from a metric only in that distinct points may have distance 0. Other pseudo-metrics considered later in this paper are given by pulling back the distance from a metric space X under a continuous map f : Γ̃ → X.

In [6] the following construction has been introduced (with slightly more generality):

1.5. Assume that the tree Γ̃ is given an F_{n}-equivariant pseudo-metric d which is δ-hyperbolic. Let λ > 1 be a number which satisfies

d(f̃(x), f̃(y)) ≤ λd(x, y)  (2)

for all x, y ∈ Γ̃. We define a new distance function d_{∞} on Γ̃ through

d_{∞}(x, y) = lim_{k→∞} d(f̃^{k}(x), f̃^{k}(y))/λ^{k}  (3)

and observe that d_{∞} also defines a pseudo-metric on Γ̃, which satisfies

d_{∞}(x, y) ≤ d(x, y)  (4)

and

d_{∞}(f̃(x), f̃(y)) = λd_{∞}(x, y)  (5)

for all x, y ∈ Γ̃. It is not hard to see that, as λ > 1, the pseudo-metric d_{∞} is uniquely determined by the value of d on the vertices of Γ̃. In particular it suffices that (2) is satisfied for all vertices x, y ∈ Γ̃.

It follows that there is an R I -tree T with an action of F_{n} by isometries, and a surjective d_{∞}-distance preserving F_{n}-equivariant map i : Γ̃ → T. This iteration tree T = T (Γ, f, L(^{.}), λ) is uniquely determined, up to F_{n}-equivariant isometry, by the graph Γ, the map f, the edge length function L(^{.}) and by λ. In particular there is a homothety H : T → T with stretching factor λ which satisfies

α(w)H = Hw : T → T  (6)

for all w ∈ F_{n}, and

if̃ = Hi : Γ̃ → T .  (7)

We want to state the uniqueness of the iteration tree T = T (Γ, f, L(^{.}), λ) precisely, in the following form:

Lemma 1.6. Let T′ be any R I -tree with F_{n}-action, and let i′ : Γ̃ → T′ be an F_{n}- equivariant map which preserves the d_{∞}-metric on Γ̃. Then there is a (uniquely determined) F_{n}-equivariant isometric embedding j : T (Γ, f, L(^{.}), λ) → T′ with i′ = ji. ⊔ ⊓

With the above generality, of course, the tree T may well consist of a single point only. We also want to point out that in general the map i may well ”crumble” the edges of Γ̃: For any edge e the image i(e) does not need to be a geodesic segment.

Perron-Frobenius metrics and train track maps

Let f : Γ → Γ be as in 1.3. We use the following terminology:

Notation 1.7. Let M(f) = (m_{e,e′})_{e,e′∈Edges(Γ)} denote the geometric transition matrix for f, i.e. the entry m_{e,e′} denotes the number of times the path f(e′) crosses or partially crosses over the edge e, disregarding the orientations. As f is assumed to be p.l., each m_{e,e′} is finite. Let v = (v_{e})_{e∈Edges(Γ)} be a Perron-Frobenius row eigenvector of M(f), i.e. v has all entries v_{e} ≥ 0 and eigenvalue λ ≥ 1. Such an eigenvector exists always, by the Perron-Frobenius theorem for non-negative matrices, since M(f) is integer and f is not homotopic to the trivial map. We use v = (v_{e}) to define the Perron-Frobenius length function L_{v}(e) = v_{e} for any edge e of Γ, and notice that the induced pseudo-metric d : Γ̃ × Γ̃ → R I _{≥0} and λ satisfy inequality (2) of 1.5 for all vertices x, y of Γ̃.

Let Γ be a graph, X any topological space and f : Γ → X a continuous map. As in [6] we call a path β : [0, 1] → Γ an f-backtracking path if β is locally injective and if fβ is a contractible loop in X.

Definition 1.8. A homotopy equivalence f : Γ → Γ of a finite graph Γ is called train track map if f preserves the set V (Γ) of vertices of Γ and if there is no f^{k}-backtracking path in the interior of any edge of Γ, for all k ≥ 1.

Train track maps f : Γ → Γ have the remarkable property that for any edge ẽ of the universal covering Γ̃ the image f̃^{k}(e), for any k ≥ 1, is again a geodesic (with respect to any metric on the tree Γ̃ !). If we provide Γ̃ with a Perron-Frobenius length function L_{v}(^{.}) with eigenvalue λ > 1, it follows directly that L_{v}(f̃^{k}(ẽ)) = λ^{k}L_{v}(ẽ). Hence the length of ẽ in the associated d_{∞}-pseudo-metric on Γ̃ is equal to L_{v}(e), and thus every edge ẽ ⊂ Γ̃ is mapped by the map i : Γ̃ → T, defined as in 1.5, to a geodesic segment of length L_{v}(ẽ). With respect to the pseudo-metric d_{∞} this restriction iẽ : ẽ → i(ẽ) is an isometry, and we will think from now on of the metric d defined by means of the length function L_{v}(^{.}) as being “reparametrized” along the edges (without changing the total edge length) so that it agrees with d_{∞} on every edge of Γ̃.

We will call a map from a simplicial tree Γ̃ to an R I -tree edge geodesic if it maps every edge to a geodesic segment. Notice in particular that if Γ̃ carries a pseudometric which is non-zero, and if every edge is mapped to a geodesic segment of same length, as is the case above, then it follows in particular that the tree T is not just a single point.

Definition 1.9. If f : Γ → Γ is a train track map, with edge lengths L_{v}(e) defined by a non-trivial Perron-Frobenius eigenvector v of M(f) with eigenvalue λ > 1, then we call the associated iteration tree T_{v} = T (Γ, f, L_{v}(^{.}), λ) a Perron-Frobenius tree and the F_{n}-action on T_{v} a Perron-Frobenius action, with respect to the train track map f : Γ → Γ.

Proposition 1.10. For any R I -tree T_{v} with Perron-Frobenius F_{n}-action it follows that

(a) the tree T_{v} is non-trivial,

(b) the F_{n}-action on T_{v} is minimal, and

(c) the stabilizer of any non-degenerate arc in T_{v} is trivial (and hence in particular the action is small and even very small).

Proof. A complete proof has been given in [6]. It is assumed there that the transition matrix M(f) is irreducible, but this assumption is not really used in the proof other than to guarantee the existence of some v and λ as assumed here. ⊔ ⊓

Bounded backtracking

In [6] a the following notion for a free group action on an R I -tree has been introduced and used intensively.

Definition 1.11. The action of F_{n} on the R I -tree T has bounded backtracking (BBT) if for every Q ∈ T and every basis A of F_{n} there exists a constant C ≥ 0 such that for any reduced words v, w ∈ F_{n} with reduced product vw one has dist(vQ, [Q, vQ]) ≤ C, where [U, V] denotes the geodesic segment from U to V.

In the next sections we will use the property BBT explicitly in the following equivalent form:

Lemma 1.12. The F_{n}-action on T satisfies BBT if and only if for any graph Γ with π_{1}Γ = F_{n} and any F_{n}-equivariant map i : Γ̃ → T there is a constant c ≥ 0 such that the i-image of any geodesic arc [x, y] ⊂ Γ̃ is contained in the c-neighborhood of the geodesic segment [i(x), i(y)] ⊂ T. ⊔ ⊓

Remark 1.13. If the F_{n}-action on the R I -tree T satisfies BBT, then so does the induced action of F_{n} on the metric completion T̂ of T. This follows directly from Definition 1.11.

It has been observed in [6] that from a bounded cancellation lemma due to Bestvina-Feighn-Handel (see [2] or [5, Lemma 2.2.4]), the following can be derived:

Propositon 1.14. Every F_{n}-action on an R I -tree T which is a limit of free simplicial actions (i.e. T represents a point in Culler-Vogtmann’s outer space CV_{n} or its Thurston boundary ∂CV_{n}) satisfies BBT. ⊔ ⊓ 2. Proof of Theorem 1.2

We first want to give a criterion for α-invariant trees to be Perron-Frobenius:

Propositon 2.1. Let f : Γ → Γ be a train track map representing α ∈ Aut(F_{n}), and let T be an α-invariant R I -tree, with respect to a homothety H with stretching factor λ > 1, as in 1.1. Assume furthermore that T satisfies BBT. If there exists an F_{n}-equivariant edge geodesic map i : Γ̃ → T which satisfies

if̃ = Hi ,  (8)

then the minimal F_{n}-invariant subtree T_{0} ⊂ T is F_{n}-equivariantly isometric to a Perron-Frobenius tree, with respect to f.

Proof. We define a length L(ẽ) for every edge ẽ in Γ̃ with initial vertex P and terminal vertex Q through

L(ẽ) = dist(i(P), i(Q)) .

As i is assumed to be F_{n}-equivariant, this induces a well defined length function L : Edges(Γ) → R I _{≥0} on Γ. Notice that the assumption that i be edge geodesic together with equation (8) implies that for any edge ẽ ∈ E(Γ̃) and any t ≥ 1 the path f̃^{t}(ẽ) is mapped by i to a geodesic in T (namely to H^{t}i(ẽ)). This shows λL(e) = length(f(e)) = ∑_{e′∈Edges(Γ)} m_{e′,e}L(e), for every edge e of Γ. Thus the length function L on the edges of Γ and of Γ̃ is given by a Perron-Frobenius eigenvector of the transition matrix M(f) = (m_{e′,e}), with eigenvalue equal to the stretching factor λ of H.

We claim now that i preserves the d_{∞}-metric on Γ̃ which is defined as explained in 1.5 through the length function L. In fact, by definition of L and by the above observation that f̃^{t}(ẽ) is mapped by i to a geodesic in T, it follows that our claim is true for any two points on f̃^{t}(ẽ), for any edge ẽ of Γ̃. As every finite edge path in Γ̃ is a finite concatenation of such T -isometric subpaths (i.e. subpaths contained in some f̃^{t}(ẽ)), it follows that d_{∞}(x, y) ≥ dist(i(x), i(y)) for any x, y ∈ Γ̃. Observe that the reduced arc [x, y] in Γ̃ which joins x to y is a finite union of subarcs with endpoints of distance 0 with respect to the d_{∞}-metric, and of (possibly degenerate) T -isometric subpaths, such that the d_{∞}-lengths of the latter add up to d_{∞}(x, y).

Thus, in order to complete the argument for d_{∞}(x, y) = dist(i(x), i(y)) by means of a proof by contradiction, we can now assume that there are points x, y ∈ Γ̃ with dist(i(x), i(y)) = 0 and d_{∞}(x, y) ≠ 0. From the above observation it follows then that there are points x′ ≠ y′ on one of those T -isometric subpaths of [x, y] such that f̃^{t}(x′) and f̃^{t}(y′) are contained in the geodesic arc connecting f̃^{t}(x) to f̃^{t}(y), for all t ≥ 1. But as dist(if̃^{t}(x′), if̃^{t}(y′)) → ∞ for t → ∞, this contradicts the assumption that T satisfies BBT, as dist(if̃^{t}(x), if̃^{t}(y)) = dist(H^{t}i(x), H^{t}i(y)) = λ^{t}dist(i(x), i(y)) = 0 for all t ≥ 1.

With these data we consider now the iteration tree T (Γ, f, L(^{.}), λ) as defined in 1.3, and let î : Γ̃ → T (Γ, f, L(^{.}), λ) be the canonical d_{∞}-preserving map defined there. From the above claim and Lemma 1.6 it follows that there is an F_{n}- equivariant isometric embedding j : T (Γ, f, L(^{.}), λ) → T, and as T (Γ, f, L(^{.}), λ) is minimal by Proposition 1.10 (b), it follows that j(T (Γ, f, L(^{.}), λ)) agrees with the minimal subtree T_{0} ⊂ T. Thus T_{0} is Perron-Frobenius with respect to f. ⊔ ⊓

We now want to construct a map i as in the previous Proposition 2.1, first for the vertices, and then extend it to the edges. We crucially use the dynamics of H to define the right such map. Notice that until the next proposition (inclusively) we do not need the train track property of f nor the fact that T satisfies BBT.

2.2. Let H : T → T be as in 1.1. Let T̄ be the metric completion of T, and let H̄ : T̄ → T̄ be the (well defined) continuous extension of H. It follows that H̄ as well as every wH̄^{m} : T̄ → T̄ (w ∈ F_{n}, m ≥ 1) has a fixed point Q(w, m) which is uniquely determined, as the stretching factor of the homotheties H^{m}, H̄^{m} and wH̄^{m} is equal to λ^{m} > 1.

2.3. As H̄ is a continuous extension of H, it follows that H̄ is also α-invariant: For every w ∈ F_{n} one has H̄w = α(w)H̄ and hence (replacing w by α^{−1}(w^{−1})) also H̄^{−1}w = α^{−1}(w)H̄^{−1}. Iterated applications of these formulae gives H̄^{m}w = H̄^{m−1}α(w)H̄ = H̄^{m−2}α^{2}(w)H̄^{2} = … and hence

H̄^{m}w = α^{m}(w)H̄^{m} : T̄ → T̄  (9)

for any m ∈ Z Z .

Similarily, let f : Γ → Γ be as in 1.3 and let f̃ : Γ̃ → Γ̃ be the lift of f to the universal covering Γ̃ of Γ which represents the same α ∈ Aut(F_{n}). Then the equation (1) in 1.3 can be applied iteratively to give

f̃^{m}w = α(w)^{m}f̃^{m} : Γ̃ → Γ̃ ,  (10)

but here we have to assume m ≥ 0 as f^{−1} is not well defined.

2.4. Let f : Γ → Γ be as in W.1, and assume that f maps the set of vertices V (Γ) to itself. Let V_{0} ⊂ V (Γ) be the set of vertices which are fixed by some positive power of f. If we define m = |V (Γ)|! then we obtain f^{m}(P) = P for every P ∈ V_{0} and f^{m}(P) ∈ V_{0} for every P ∈ V (Γ) − V_{0}.

Let f̃, H̄ and α be as in 2.3 As the action of F_{n} on Γ̃ by covering translations is free, it follows that for every vertex P in the full preimage Ṽ_{0} of V_{0} there is precisely one element wP ∈ F_{n} which satisfies

w_{P} f̃^{m}(P) = P .  (11)

We use 2.2 to define a map i : V (Γ̃) → T̄, given for all P ∈ Ṽ_{0} through

i(P) = Q(w_{P} , m)

and for all other vertices P ∈ V (Γ̃) − Ṽ_{0} with P_{0} = f̃^{m}(P) through

i(P) = H̄^{−m}if̃^{m}(P) = H̄^{−m}(Q(w_{P_{0}}, m) .

Proposition 2.5. The above defined map i : V (Γ̃) → T̄ satisfies (a) vi = iv for all v ∈ F_{n}, and

(b) if̃ = H̄i.

Proof. (I) We first consider the case P ∈ Ṽ_{0}, and let P′ = vP. In order to prove (a) we have to show that Q(w′_{P} , m) = vQ(w_{P} , m), for m ≥ 1 as in 2.4:

From the above equations (10) and (11) one derives f̃^{m}(vP) = α^{m}(v)f̃^{m}(P) = α^{m}(v)w_{P}^{−1}P = α^{m}(v)w_{P}^{−1}v^{−1}(vP). This shows w_{P′} = vw_{P} α^{m}(v^{−1}). On the other hand, for Q = Q(w_{P} , m) the definition of Q(w_{P} , m) gives w_{P} H̄^{m}(Q) = Q, and thus we derive from (9) just as above H̄^{m}(vQ) = α^{m}(v)H̄^{m}(Q) = α^{m}(v)w_{P}^{−1}Q = α^{m}(v)w_{P}^{−1}v^{−1}(vQ). This proves Q(vw_{P} α^{m}(v^{−1}), m) = vQ and hence Q(w_{P′}, m) = vQ(w_{P} , m).

In order to prove (b) (for the case P ∈ Ṽ_{0}) we have to show that Q(w_{P} , m) = Q(w_{f̃(P)}, m):

From (11) and (10) it follows f̃(P) = f̃(w_{P} f̃^{m}(P)) = α(w_{P})f̃^{m+1}(P) = α(w_{P}) f̃^{m}(f̃(P)) and hence w_{f̃(P)} = α(w_{P}). But then the definition of Q(w_{P} , m) together with (9) gives w_{f̃(P)}H̄^{m}(H̄(Q(w_{P} , m))) = α(w_{P})H̄(H̄^{m}(Q(w_{P} , m))) = α(w_{P})H̄(w_{P}^{−1}Q(w_{P} , m)) = α(w_{P}) α(w_{P}^{−1})H̄(Q(w_{P} , m)) = H̄(Q(w_{P} , m)). This implies H̄Q(w_{P} , m) = Q(w_{f̃(P)}, m).

(II) Assume now P ∈ V (Γ̃) − Ṽ_{0}, and let P_{0} = f̃^{m}(P) ∈ Ṽ_{0}. In order to show (a) we use (in this order) (10), the above derived equation (a) for P_{0}, (9) and the definition of i(P) to compute i(vP) = H̄^{−m}if̃^{m}(vP) = H̄^{−m}iα^{m}(v)f̃^{m}(P) = H̄^{−m}i(α^{m}(v)P_{0}) = H̄^{−m}α^{m}(v)i(P_{0}) = vH̄^{−m}if̃^{m}(P) = vi(P).

In order to show (b) for P we use (b) for P_{0} to compute H̄i(P) = H̄H̄^{−m}if̃^{m}(P) = H̄^{−m}H̄i(P_{0}) = H̄^{−m}if̃(P_{0}) = H̄^{−m}if̃^{m+1}(P) = if̃(P). The last equation, in case f̃(P) ∈ V (Γ̃) − Ṽ_{0}, follows from the definition of the map i in 2.4, and in case f̃(P) ∈ Ṽ_{0} it follows from equation (b) as proved above for vertices in Ṽ_{0}. ⊔ ⊓

We can now extend the map i geodesically to the edges:

Lemma 2.6. Let f : Γ → Γ be a train track representative of α ∈ Aut(F_{n}), and let T̄ be a (not necessarily minimal) α-invariant R I -tree which satisfies BBT. Let H̄ : T̄ → T̄ be a homothety with stretching factor λ > 1, and let i : Γ̃ → T̄ be a geodesic F_{n}-equivariant map which satisfies if̃(P) = H̄i(P) for all vertices P ∈ V (Γ̃). Then one obtains (after properly reparametrizing f and i along the edges of Γ)

if̃ = H̄i .

Proof. We observe:

(i) As i maps by assumption any edge ẽ ⊂ Γ̃ to a geodesic segment, it follows that H̄i(ẽ) ⊂ if̃(ẽ). (ii) As f is a train track map, then no edge e in Γ contains an f^{k}-backtracking path for any k ≥ 1. Hence any lift f̃^{k}(ẽ) of f^{k}(e) is a geodesic arc in Γ̃. As T̄ satisfies BBT, it follows from Lemma 1.12 that there is a constant c ≥ 0 such that if̃^{k}(ẽ) is contained in the c-neighborhood of a geodesic arc in T̄.

(iii) No edge ẽ ⊂ Γ̃ can possibly contain a non-degenerated if̃-backtracking path ẽ_{0}, as we can show that if̃(e_{0}) must be a single point in T̄: Otherwise the diamater of if̃^{k}(ẽ_{0}) grows arbitrary large for increasing k, as H̄ stretches T̄ by λ > 1 and H̄^{k−1}if̃(ẽ) ⊂ if̃^{k}(ẽ), by (i) above. But this would contradict (ii) above. This shows c = 0, and actually a little more: The map if̃^{k} maps the points of ẽ in a ”non-strictly monotonious” fashion to if̃^{k}(e), i.e. small segments of ẽ may be collapsed to single points, but there is no backtracking along if̃^{k}(ẽ).

(iv) Let ẽ be an edge in Γ̃ with initial vertex P and terminal vertex Q. From observation (iii) it follows that i maps the path f̃(ẽ) to a geodesic segment which connects if̃(P) to if̃(Q). By assumption one has if̃(P) = H̄i(P) and if̃(Q) = H̄i(Q); hence it follows that if̃(ẽ) and H̄i(ẽ) are both equal to the (unique) geodesic segment connecting these two points. Thus it follows that a reparametrization of f and i along edges gives if̃(x) = H̄i(x) for all points x ∈ ẽ. ⊔ ⊓

We can now prove Theorem 1.2, stated in the following slightly more explicite form:

Theorem 1.2’. If α admits an absolute train track representative f : Γ → Γ then every α-invariant F_{n}-action on some small R I -tree T with stretching factor λ > 1 is Perron-Frobenius, i.e. T = T_{v} for some Perron-Frobenius eigenvector v of the transition matrix M(f). In particular, if M(f) is irreducible, it follows that T is unique up to uniform rescaling of the metric.

Proof. Let f : Γ → Γ be a train track representative of α ∈ Aut(F_{n}), and let H : T → T commute with α as in 1.1. We also assume that the action on T is minimal and small. As T is α-invariant with stretching factor λ > 1, this implies by 1.10 that T has trivial arc stabilizers, and hence is the limit of free actions (see [1] ). It follows in particular that T satisfies BBT.

We replace T by its metric completion T̄ and H by the canonical extension to H̄, as in 2.2. We then apply Lemma 2.5 and Proposition 2.6 to obtain a edge geodesic F_{n}-equivariant map i : Γ̃ → T̄. Thus Lemma 2.1 shows that there is an F_{n}-equivariant isometric embedding j : T_{v} → T̄ for some Perron-Frobenius tree T_{v}, with respect to f : Γ → Γ. But as T is the minimal subtree of T̄, it follows that j(T_{v}) = T, which shows that T is Perron-Frobenius. ⊔ ⊓ 3. Partial train tracks with 2-cells

The following notions will be basic for the rest of this paper. Earlier versions of some of them have been used in [6] and [16]. In this section we present the new concepts with a slightly higher degree of generality than needed just for free group automorphisms, to include other naturally occuring cases e.g. from Nielsen-Thurston surface theory.

Partial train track maps

A graph of spaces G is a finite family of path-connected vertex spaces X_{v}, which we sometimes assume for simplicity to be K(π, 1)-spaces, with a collection Γ̂ of finitely many edges attached to them (“the edges of G”). We do not require that G is path-connected, but in order to simplify notation we only treat the pathconnected case; the extension to the general case is canonical. One obtains from Γ̂ a graph Γ = Γ_{G} by quotienting every vertex space X_{v} to a single vertex v. The analoguous operation on the universal covering G̃ of G gives a tree Γ̃_{G} (which should not be confused with the universal covering of the graph Γ_{G}) with a canonical action of π_{1}G by “deck transformations”. Let f : G → G be a map of pairs, i.e. the union X of all vertex spaces satisfies f(X) ⊂ X, so that f induces maps f_{Γ} : Γ → Γ and f_{v} : X_{v} → X_{f_{Γ}(v)} for any vertex v ∈ Γ. We assume that f induces an automorphism f_{∗} of π_{1}G, which is the free product of the π_{1}X_{v} with π_{1}Γ. In particular it follows for every essential vertex v, i.e. with non-trivial π_{1}X_{v}, that f_{Γ} acts periodically on v and that a suitable power of f induces an automorphism of π_{1}X_{v}. Furthermore every homotopy class of non-trivial closed loops in X has precisely one preimage in X, and every homotopy class rel. boundary of edge paths which cross over precisely 2 edges of G has only finitely many f-preimages with endpoints on edges of G.

Another consequence of the hypothesis that f_{∗} be an automorphism is that f has bounded backtracking: There is an upper bound to the diameter of the image of any f-backtracking path, i.e. any reduced path in G which is mapped by f to a contractible loop. Here length means the simplicial length of the path, i.e. the number of edges of G crossed by the path (edges in X, if there are any, do not count !). A path in G is reduced if any “lift” to Γ̃_{G} is reduced. For any path γ in G or in G̃ we denote by [γ] the reduced path obtained from γ by contracting all backtracking subpaths to a point or into the subspace X. We will not distinguish between homotopic paths if the homotopy only takes place in the relative part.

A map of pairs f : G → G as above has the partial train track property (relative to X ⊂ G) if any positive power f^{t} of f maps every f^{t}-backtracking path contained in an edge of G into the invariant subspace X. More generally, any path γ in G is called legal if any f^{t}-backtracking subpath of γ, for any t ≥ 1, is mapped by f^{t} into X. Generalizing a notion of Bestvina-Handel [3] we say that two edges e, e′ of G, which initiate at the same vertex space X_{v}, together with a connecting path β in X_{v}, form an illegal turn if some positive iterate f^{t} of f maps β to a connecting path which is a contractible loop in f^{t}(X_{v}), and if f^{t} identifies initial segments of both edges by mapping them to a path of non-zero simplicial length (i.e. e^{−1}βe′ is reduced, but f^{t}(e^{−1}βe′) is not !). The path β is called the tip of the illegal turn. The illegal turns group the edges raying out of a vertex in Γ̃_{G} into equivalence classes called the gates of f or of G. If, as assumed above, Γ_{G} is finite and f acts as π_{1}-isomorphism on the essential vertex spaces, it follows that all gates are finite. Notice that a path γ in G is legal if and only if it runs over legal turns only, and furthermore that the f-image of any legal path is again legal. We sometimes refer to X as the relative part and to Γ̂ as the train track part of f or of G.

Definition 3.1. A map f : G → G is called a partial train track map (relative to X ⊂ G) if G is a finite (possibly non-connected) graph of spaces, f maps the union X of the vertex spaces to itself, f induces an automorphism of π_{1}G, and f has the partial train track property relative to X. In this case G (together with the gate structure induced by f on G̃) is sometimes called a partial train track.

A reduced path η in G is called an INP (“indivisible Nielsen path”) for f if it consists of precisely two legal subpaths, and if f(η) is homotopic relative endpoints to η (compare [3]). INP’s for positive powers of f are called periodic INP’s. Notice that a periodic INP may well have its endpoints in the interior of an edge of G; in this case it is sometimes useful to subdivide the edge, by which we add the subdivision vertex as a new inessential component to the relative part X.

We say that f has no periodic edges if no edge of Γ has a periodic orbit with respect to the induced map f_{Γ}. Similarly, if there are no edges which are contracted by an iterate of f_{Γ} to a single point, we say that f no zero edges.

Lemma 3.2. If f : G → G is a partial train track map relative to an f-invariant subspace X, and if f has no periodic or zero edges, then for every finite path γ in G there exits an integer t ≥ 0 such that [f^{t}(γ)] is “pseudo-legal”: It is a legal concatenation of legal paths and of periodic INP’s.

Proof. As the number of illegal turns in [f^{t}(γ)] cannot increase with t, we can assume that for sufficiently large t the number of illegal turns becomes stationary. We can then define for each of these illegal turns an image turn as follows: It is the illegal turn in [f^{t+1}(γ)] which has its tip at the “inner endpoint” of the backtracking subpath in the non-reduced image f^{t+1}(γ) which has at its “outer endpoint” the f-image of the tip of the illegal turn we started out with.

For any two adjacent illegal turns of [f^{t}(γ)] let γ′ denote the legal subpath of [f^{t}(γ)] connecting their tips. We consider the points P, P′ on γ′ which cut off the eventually cancelled boundary segments, i.e. the boundary segments of γ′ that contain precisely those points which are under iteration of f eventually mapped into the backtracking subpaths at the illegal turns at the two endpoints of γ′. It can occur that P = P′, but the two eventually cancelled segments can not overlap, as otherwise the number of illegal turns would strictly decrease, contrary to our assumption.

Let us rename γ′ = γ′(t), P = P (t), P′ = P′(t) and, for t′ ≥ t let γ′(t′), P (t′), P′(t′) denote the corresponding legal subpaths and points of [f^{t′}(γ)] which lie between the image illegal turns. Then it follows directly from our definitions that f(P (t)) = P (t + 1) and f(P′(t)) = P′(t + 1).

Claim 1: The simplicial length (i.e. the number of edges or edge segments from Γ̂) of an eventually cancelled segment is bounded.

This follows directly from the above observed fact that f has bounded backtracking (i.e. the backtracking subpath at the tip of the image of an illegal turn has bounded length), together with the observation that by the finiteness of Γ_{G} there is a t_{0} ≥ 0 with length(f^{t_{0}}(e)) ≥ 2 for any edge of Γ_{G}, since by assumption f has no periodic or zero edges.

Let now γ′′(t) be the maximal legal subpath of [f^{t}(γ)] adjacent to γ′(t), so that the terminal eventually cancelled boundary segment γ′_{term}(t) of γ′(t) cancels eventually against the analogously defined initial eventually cancelled boundary segment γ′′_{init}(t) of γ′′(t).

Claim 2: In γ′_{term}(t) and in γ′′_{init}(t) any connecting path β (in X) between two adjacent edges (in G) has to belong, up to homotopy relative endpoints, to a given finite family of paths.

Let us first assume that f maps β into the backtracking subpath at the image of the illegal turn between γ′_{term}(t) and γ′′_{init}(t). Then either f(β) cancels against the image of some subpath in the interior of an edge which is mapped to the relative part, or else there is a connecting path β′ in γ′′_{init}(t) such that f(β′) cancels against f(β). As G has only finitely many edges, in the first case there are only finitely many choices for β, as follows from the observation at the beginning of this section, that every edge path of length 2 in G has only finitely many preimages with endpoints on edges. But the same is true in the second case, as at least one of β or β′ must belong to a non-periodic (and hence inessential) component of X, because f induces an automorphism on π_{1}G, so that β and β′ cannot belong to the same component X_{0} of X: otherwise the subpath of γ′_{term}(t̂) γ′′_{init}(t̂) bounded by β and β′ could be closed up in X_{0} to give a non-trivial loop with contractible image.

Next let us consider any connecting path β which is not the first connecting path in γ′_{term}(t) or the last in γ′′_{init}(t)): For those β the statement of the Claim 1 together with the fact that edges are eventually expanded by f imply that there is an upper bound t̂≥ 1, such that β is mapped by f t̂ into the backtracking subpath at the illegal turn. Hence Claim 2 follows for any such β from the above considered first case and from the above quoted observation at the beginning of this section.

It remains to prove Claim 2 for the first connecting path of γ′_{term}(t) and the last of γ′′_{init}(t). If those two will eventually cancel against each other (or against another connecting path), then again one of them must belong to a non-periodic vertex space, and Claim 2 follows as above. If they do not cancel against each other or against any other connecting path, they must eventually cancel against the image of a subpath of an edge. But then for one of them this edge is neither the first on γ′_{term}(t) nor the last of γ′′_{init}(t), and hence we deduce (in two steps) from the finiteness of the choices for the other connecting paths considered above, that there is again a bound as the above t̂, for the remaining two connecting paths considered now. This proves Claim 2.

The finiteness of the edges of G together with Claims 1 and 2 shows that there are only finitely many choices for the paths γ′_{term}(t) and γ′′_{init}(t), and hence it follows that some choice will eventually repeat for some iterate f t̂. In this case it follows that even the precise position of the initial point P′(t) of γ′_{term}(t) (and similarly of the terminal point of γ′′_{init}(t)), if that is contained in the interior of an edge, has to repeat, as P′(t) only depends on the finite repeating edge paths which contain all of the eventually cancelled boundary segments. But this show precisely that γ′_{term}(t̂) γ′′_{init}(t̂) is a periodic INP. ⊔ ⊓

Remark 3.3. A careful analysis of the last proof shows that there exists a critical exponent t^{∗} such that for any path γ with at most one illegal turn the path f^{t^{∗}}(γ) is pseudo-legal.

It is not difficult to see that, in the absence of periodic and zero edges, there can be only finitely many periodic INP’s (as their length is bounded in terms of the cancellation bound of f and of the minimal exponent t such that f^{t} honestly expands every edge of G, and as there are only finitely many choices for the connecting paths in any f-backtracking path, see the above proof), and that they can be detected by a relatively easy algorithm.

Let f : G → G be a partial train track map. An infinite reduced path R in G is called an eigenray of f if f^{t}(R) = R for some t ≥ 1 (as usually, up to homotopy which only takes place in the relative part). One verifies easily the following:

Facts 3.4. If f : G → G has no periodic or zero edges, then:

(1) An eigenray is always legal.

(2) Every eigenray starts either at a periodic point in the interior of an edge, or at a periodic gate, i.e. a gate which consists of edges e for which some f^{t}(e) starts (up to an initial path in the relative part) at this gate.

(3) Every periodic gate defines precisely one eigenray which starts at that gate. Similarly, every periodic point in the interior of an edge defines in each direction an eigenray.

(4) Every pair of eigenrays which agrees up to a finite initial path of non-zero length defines a periodic INP which is built from these initial paths.

(5) Every periodic INP is obtained as in (4) from two eigenrays.

⊔ ⊓

From Facts 3.4 (4) and (5) it follows that there is a natural equivalence among periodic INP’s: η and η′ are equivalent if and only if maximal legal subpaths γ of η and γ′ of η′, together with a suitable finite segment of the canonical prolongation of γ and γ′ by the corresponding eigenray, form again a periodic INP (which would then be equivalent to both η and to η′). The union of all such suitable prolonged maximal legal subpaths of equivalent periodic INP’s will sometimes be called a generalized periodic INP.

The most important example of partial train tracks are given by Bestvina-Handel’s relative train track representatives for automorphisms of free groups (see [3]). Here the relative part is given by the union of all non-maximal strata.

A partial train track does not change essentially if one replaces the relative part by a homotopy equivalent space and adapts the train track map in the canonical way given by the homotopy equivalence. A particular such case, which plays an important role in the sequel, is described now:

Remark 3.5. Let f : G → G be a partial train track map relative X. If X′ is an f-invariant union of some of the connected components of X and if the restriction of f to a selfmap of X′ is a homotopy equivalence, then we can construct a new partial train track map in the following way: We fix an integer t ≥ 1. Then we unglue every endpoint of an edge e in G which is attached to a point v of X′ and reglue it to f^{t}(v). We redefine the image f(e) for any edge e of G by replacing any subpath γ′ of f(e) contained in X′ by f^{t}(γ′). Similarly, if f maps a connected component X_{v} of X − X′ into X′, we redefine f on X_{v} to be replaced by the map f^{t}. It follows directly from these definitions that this gives a well defined map f_{1} : G_{1} → G_{1}, and it is easy to verify that this is again a partial train track map relative the subspace X_{1} which is a copy of X. The maps f and f_{1} commute via the map h : G → G_{1} which “fixes” every edge of G as well as every point of X −X′, and maps every point x ∈ X′ to the point f^{t}(x) in the subspace X′_{1} of the relative part X_{1} of G_{1} which is the copy of X′. It is easy to show that h is a homotopy equivalence.

Notice that the assumption that f restricts to a homotopy equivalence of X′ is necessary in order to get a homotopy equivalence h as above, with hf = f′h. If one is content with a more general map h which satisfies this equation, but is only an isomorphism on π_{1}, then the weaker assumption suffices that f induces a π_{1}- isomorphism on each connected component of X′. It is, however, unavoidable that X′ contains no inessential components of X: otherwise π_{1}G_{1} would be different from π_{1}G.

Nielsen faces

We now consider maps f : G^{2} → G^{2}, where G^{2} differs from the previously considered spaces G in that, other than a relative part X and a train track part Γ̂ as before, it also contains finitely many 2-cells, called Nielsen faces, which are attached to G^{1} = X ∪ Γ̂ along their boundary. The restriction of f to G^{1} is a partial train track map as before. The Nielsen faces, however, must satisfy certain additional conditions:

In case of an elementary Nielsen face Δ the boundary of the 2-cell Δ forms a closed loop in G^{1} which must contain precisely one periodic INP η, while the complementary boundary subpath ∂Δ − ^{∘} η must be contained in X. To describe the general case we subdivide the above elementary Nielsen face Δ into two fins by introducing a spine which cuts Δ from the tip of η through the interior of Δ down to some point on the interior of the complementary boundary subpath ∂Δ − ^{∘} η. A general Nielsen face Δ̂ now consists similarly of a spine with fins attached to it, but in general there may be more than two fins. In this case any two together of this finite collection Δ̂ of fins must form an elementary Nielsen face Δ as described before. In particular, the union of all boundary INP’s of a general Nielsen face constitute precisely of a generalized INP as defined above. Below we will often treat only the case of an elementary Nielsen face, if the extension to general Nielsen faces is canonical.

We formally define a path γ in G^{1} to be illegal if some positive iterate f^{t}(γ) contains an formally illegal turn, i.e. a subpath γ_{0} which is homotopic relative endpoints in X to the complementary boundary subpath γ′_{0} of a Nielsen face Δ, such that γ proceeds on both sides of γ_{0} by edges of G^{1} which lie in the same gate as the initial segments of the periodic INP η = ∂Δ − ^{∘} γ′. Thus the two gates in G^{1} defined by the initial edges of the boundary INP of any Nielsen face Δ will be assembled together into a new, formally enlarged gate in G^{2}; similarly one proceeds with their f-preimage gates. We say that any path which contains all of the boundary INP of a Nielsen face is non-reduced and we reduce it by homotopying the path over the Nielsen face, thus replacing the INP by the complementary boundary subpath in X. Similarly, any path with a subpath γ_{0} that runs once around the whole boundary of a Nielsen face Δ, starting at an arbitrary point x ∈ ∂Δ, is unreduced and can be reduced by homotopying the subpath γ_{0} over the Nielsen face Δ to replace it by the single point x. It follows, just as for partial train tracks without Nielsen faces, that a path is legal in G^{2} if and only if all of its positive iterates are reduced. We’d like to point out that in particular the two maximal legal subpaths of the boundary INP of any Nielsen face must be legal in G^{2}, not just in G^{1}: they cannot cross over any formally illegal turn as defined above.

We also require that f permutes the Nielsen faces, i.e. the image of a Nielsen face is a Nielsen face, up to homotopy in X and up to the fact that the image of a (periodic) INP is not reduced but contains a backtracking subpath at its tip. In particular it follows that f permutes the boundary INP’s in precisely the same way as the homotopy classes rel. endpoints of the complementary boundary subpaths. The purpose of Nielsen faces, obviously, is to improve pseudo-legal paths by a reduction in G^{2} to paths which are honestly legal.

However, since above we formally enlarged the definiton of an illegal turn, a priori one has to admit the possibility that the backtracking subpath at the tip of the image of a periodic INP η is not backtracking in G^{1}, for example if the illegal turn at the tip of η belongs to one of the formally enlarged gates as described above. In order to avoid an undesired iteration phenomenon which could lead to infinitely many INP’s, we work in this paper with the following definition:

Definition 3.6. A selfmap f : G^{2} → G^{2} of a graph of spaces with finitely many attached 2-cells is a partial train track map with Nielsen faces relative to the subspace X ∈ G, if the following conditions are satisfied:

(1) The restriction f^{1} : G^{1} → G^{1} of f to the 1-skeleton G^{1} of G^{2} is a partial train track map rel. X as in Definition 3.1. The train track property of f^{1}, however, must be satisfied also with respect to the formally illegal turns defined by the Nielsen faces.

(2) every 2-cell Δ is an elementary Nielsen face (i.e. ∂Δ is the union of a periodic INP and a path in X, and f permutes the Nielsen faces) or part of a general Nielsen face (i.e. the union of elementary Nielsen faces),

(3) every finite path has an f-iterate which can be reduced in G^{2} to a legal path,

(4) there is no non-trivial legal loop outside X which is contractible, and (5) for every vertex space X_{v} of X the inclusion into G^{2} is π_{1}-injective.

The map f is called partial train track map with a collection of some Nielsen faces if properties (1), (2), (4) and (5) hold.

The most important example (implicitely) in the literature are Thurston’s invariant train tracks on surfaces for pseudo-Anosov homeomorphisms: After a slight isotopy one achieves that vertices of such train tracks are mapped to vertices, and then we can subdivide each complementary region, by cutting along arcs which joins the fixed points on adjacent boundary leaves, into triangular shaped Nielsen faces, and into a left-over disk which represents the vertex space for this case. More interesting examples are obtained similarly if the homeomorphism is pseudo-Anosov only on some invariant subsurfaces.

Some of the notions introduced above become more natural if one passes to the 2-complex Γ̃_{G^{2}}^{2} which is the analogue of the tree Γ̃_{G} in the case of train tracks without Nielsen faces. One obtains Γ̃_{G^{2}}^{2} from the universal covering G̃^{2} by contracting every connected component of the full preimage X̃ of the relative part X to a point. This transforms every Nielsen face into a bigon with legal sides. One may feel tempted to identify equivariantly the two sides of this bigon (properly), but for many examples the resulting quotient is not any more simplicial: In fact, if the corners of the bigons are the only illegal turns in G^{2}, then the quotient resulting from identifying isometrically with respect to a length function coming from an eigenvector is precisely the corresponding Perron-Frobenius limit tree, see section 4.

In this paper all partial train track maps with Nielsen faces occur from the following special construction:

Definition 3.7. Let f : G → G be a partial train track map, possibly without Nielsen faces or with a collection of some Nielsen faces, and let η = γ_{1}γ_{2}^{−1} be an INP with legal subpaths γ_{1}, γ_{2}, which is not contained as boundary INP in any of the given Nieslen faces. Then the following operation is called expansion of an (elementary) Nielsen face at the INP η: First we check if a boundary point of η is contained in the interior of an edge of G, and in this case we subdivide this edge. Then we add a triangular shaped 2-cell Δ to G by glueing two of its sides to γ_{1} and to γ_{2}, and define the third side to be a new auxiliary edge e of G which connects the initial point of γ_{1} to that of γ_{2}. We define f(e) = e and f(Δ) = Δ ∪ f(η), and add e to the relative part of G. Similarly, in case of a periodic INP we introduce a periodic orbit of 2-cells and a periodic orbit of corresponding auxiliary edges.

In case of a collection of m eigenrays which agree all up to finite initial subpaths, i.e. the case of a generalized periodic INP, we can expand a general Nielsen face by an analogous but more complex expansion process which adds a new auxiliary vertex and m new auxiliary half edges to the relative part as well as m fins to G such that any two of the latter form a 2-cell which could be obtained alternatively by the expansion of an elementary Nielsen face as described above.

It is important, however, that before doing such an expansion of a general Nielsen face, we check that none of the elementary periodic INP’s belonging to this generalized INP is already the boundary INP if a given (elementary or generalized) Nielsen face. If this is the case, then we check which of the eigenrays are already contained in a fin, and only the other ones are expanded by attaching a new fin to G (along the same spine as the given fins) and a new auxiliary half edge to X (using the given auxiliary vertex as boundary vertex).

We would like to point out that, if f : G → G has no periodic or zero edges, then the expansion of all (periodic or general) Nielsen faces is an algorithmic procedure, based on the above described algorithm which determined all periodic INP’s.

Lemma 3.8. (a) Let f : G → G be a partial train track map without Nielsen faces and with no periodic or zero edges, and let G^{2} be obtained from G by expanding Nielsen faces at every periodic or generalized INP. Then the resulting map f : G^{2} → G^{2} is a partial train track map with Nielsen faces. In particular, every finite edge path γ in G^{2} has an iterate f^{t}(γ) which reduces in G^{2} to a legal path [f^{t}(γ)].

(b) Let f : G → G be a partial train track map with no periodic or zero edges, but possibly with a collection of some Nielsen faces which all belong to an f-invariant subspace G′, where we assume that the restriction f′ : G′ → G′ of f satisfies the properties (1) - (5) of Definition 3.6. Let G^{2} be obtained from G by expanding Nielsen faces at every periodic or generalized INP which is not contained in G′. Then again the resulting map f : G^{2} → G^{2} is a partial train track map with Nielsen faces.

Proof. (a) The properties (1), (2) and (5) of Definition 3.6 follow directly from the construction of G^{2} or from the analogous properties of the train track map f : G → G, since the image of any edge of G does not cross over any of the newly introduced auxiliary edges (or half edges) in the enlarged relative part X. To show property (3) we consider a maximal subpath γ_{i} of γ which does not cross over any auxiliary edge. By Lemma 3.2 there is an iterate f^{t_{i}}(γ_{i}) which can be reduced in G to a pseudo-legal path: in particular it also does not cross over any of the auxiliary edges. For t′ = max{t_{i}} this gives a path f^{t′}(γ) which reduces to a path γ′ that runs over no illegal turns, except at the tip of some periodic INP which is contained in a pseudo-legal subpath, and except perhaps for the in G^{2} formally declared illegal turns at the auxiliary edges. But in the latter case a further iterate allows a reduction in G^{2} which replaces the auxiliary edge by an illegal turn in G. Thus one can start again the original iteration procedure, but on a path with strictly less auxiliary edges. This leads eventually to an iterate f^{t}(γ) of γ which reduces in G to a path γ′ with no formally illegal turns, and where every maximal subpath in G is pseudo-legal. Hence we can reduce γ′ in G^{2} to a legal path [f^{t}(γ)].

Finally, to show property (4) of Definition 3.6, we use a similar argument to produce an iterate of the given legal path γ where all auxiliary edges can be isotoped over the corresponding Nielsen faces to give a loop which reduces in G to a pseudo-legal loop γ′. As f eventually expands every edge of G, the length of the legal path γ, if not contained in X, grows unboundedly if one iterates f, while the number of auxiliary edges in f^{t}(γ) stays constant. As the possible cancellation between a periodic INP η and two adjacent long legal paths is bounded, unless the auxiliary edge which was replaced by η would have given rise to a formally illegal turn, it follows that γ′ cannot be trivial.

(b) The proof of this part is similar to the above and is left as an exercise to the reader. For the final argument of the proof of (4) one observes that, as π_{1}G is a free product of the π_{1} of the connected components of G′ ∪ X and of a free group, the reduced path γ′ in G can be contractible unless it is contained in G′ ∪ X, since (4) holds by hypothesis on G′. ⊔ ⊓

We would like to point out here that a reduced path in a train track with Nielsen faces G^{2} has much weaker properties than reduced paths in train tracks G without Nielsen faces: In general their lifts to G̃ are far from being geodesic or quasigeodesic, and the train track map f : G^{2} → G^{2} will not have bounded backtracking with respect to arbitrary reduced paths. In fact, even for train tracks with Nielsen faces which arise as in Lemma 3.8 it easy to think up examples of reduced paths which can be homotoped over Nielsen faces to give unreduced paths in the 1-skeleton which contain backtracking subpaths in the 1-skeleton of arbitrary length.

On the other hand, geodesics in a partial train track map with Nielsen faces are difficult to control; we restrict ourselves here to the following special case:

Let v = (v_{e})_{e∈Edges(Γ_{G})} ∈ R I _{≥0}^{Edges(G)} be a non-negative eigenvector of the transition matrix M(f). This defines as in section 1 a length function L_{v} : Edges(G) → R I _{≥0}, e ↦ v_{e} on Γ_{G} and hence an F_{n}-equivariant pseudo-metric d_{v} on the universal covering G̃ (or on Γ̃_{G}).

Lemma 3.9. Let f : G → G be a partial train track map with Nielsen faces and no periodic edges. For any non-negative eigenvector v of M(f) with eigenvalue λ > 1 all legal paths in G̃ are geodesics with respect to the pseudo-metric d_{v}.

Proof. We first observe that every periodic INP has the property that its two maximal legal subpaths have the same v-length, as v is an eigenvector and the two subpaths have f^{t}-images which agree eventually everywhere, for increasing t. Next we notice that, if γ and γ′ are two legal paths which are homotopic relative endpoints, then by property (3) of Definition 3.6 the path [f^{t}(γ^{−1}γ′)] is legal for sufficiently large t and thus, by property (2) of Definition 3.6, it must be contained in X, so that we can think of the unreduced path f^{t}(γ^{−1}γ′) as one long backtracking path. Hence the difference between f^{t}(γ) and f^{t}(γ′) can only stay in the fact that they run over different maximal legal subpaths of some periodic INP’s, so that their length is equal, by the above observation. But f multiplies the length of legal paths by λ, so that γ and γ′ must have the same length.

Now consider a possibly non-legal path γ_{∗} in G. If we apply f sufficiently often, we obtain by property (3) of Definition 3.6 a legal path [f^{t}(γ_{∗})]. Now assume that γ is a legal path homotopic relative endpoints to γ_{∗}. Then f^{t}(γ) is again legal, and by the above argument we have f^{t}(γ) and [f^{t}(γ_{∗})] have the same length. But f^{t} stretches both γ and γ^{∗} by the factor λ, and by definition of a reduction the length of [f^{t}(γ_{∗})] is less or equal to that of f^{t}(γ_{∗}). Hence the length of γ^{∗} cannot have been shorter than that of γ, which proves the statement of the lemma. ⊔ ⊓

For later purposes we need the following sharpening of property (3) of Definition 3.6. The proof is not difficult and hence left to the reader:

Lemma 3.10. Let f : G → G be a partial train track map with Nielsen faces and no periodic edges, and let τ be a finite tree. Then for any map j : τ → G there exists a t ≥ 0 and a quotient tree τ′ = q(τ) such that f^{t}j is homotopic relative endpoints to a composed map j′q : τ → τ′ → G with the property that for any two endpoints of τ the reduced path which connects their q-images in τ′ is mapped by j′ to a legal path. ⊔ ⊓

It turns out that often it is convenient if all endpoints of edges in a partial train track map f : G → G are mapped by positive powers of f eventually to a periodic orbit. This is the case if f satisfies the following:

Initial segments condition 3.11. The image of any edge of G is a path which starts and ends in an edge of G.

Any given partial train track map can be easily modified to a partial train track map which satisfies this condition: One just needs to subdivide all edges which violate that condition and to add to the relative part X of G the maximal initial and terminal segments which are eventually mapped under iteration of f to X.

We now want to use these notions to show the reader how to transform a given “2-strata train track” into an honest partial train track map with Nielsen faces. Here we explicitely include the (notationally so far suppressed) case that partial train tracks have more than one connected component.

Proposition 3.12. Let f : G → G be a partial train track (without Nielsen faces), possibly with periodic or zero edges, such that the restriction to the relative part X = G′ is a partial train track map f′ : G′ → G′ with Nielsen faces but without periodic or zero edges, relative to a subspace X′. Then one can modify G in an algorithmic way to obtain a partial train track map f_{∗} : G_{∗} → G_{∗} relative to X_{∗} with Nielsen faces and without periodic or zero edges. Here X_{∗} is obtained from X′ by iteratively adding periodic or zero edges, π_{1}G_{∗} and π_{1}G are canonically isomorphic, and f_{∗} as well as f induce automorphisms on π_{1} which commute via this canonical isomorphism.

In fact, it follows from the proof given below that, if all connected components of X′, of X and of G are K(π, 1)-spaces, as will be the case in our applications in the next sections, then G_{∗} and G are canonically homotopy equivalent and f and f_{1} are homotopic via this homotopy equivalence. Furthermore G_{∗} is again a K(π, 1)-space.

Proof. We can assume without loss of generality that the geometric transition matrix M(f) is irreducible; the reducible case follows by iterative application of this special case to f-invariant sub-train-tracks with irreducible transition matrix.

CASE 1: G − X consists precisely of one f-orbit of periodic edges modulo X.

We distinguish two subcases: If f acts on the given edge orbit periodically not just up to homotopy in X, but also up to homotopy only in X′, then we can simply add all edges of that orbit to X′, to get an invariant subspace X_{∗}. Now f_{∗} = f and G_{∗} = G is the desired partial train track map relative to X_{∗}.

If relative to X′ the given edge orbit of G − X is not periodic, then we apply Remark 3.5 and property (3) of Definition 3.6 to ensure that the image of any edge of G − X is legal relative to X′. This makes G into a partial train track relative X′ and we can apply Lemma 3.8 (b). This gives a partial train track map f_{∗} : G_{∗} → G_{∗} relative to X_{∗} = X′ with the desired properties.

CASE 2: G − X consists precisely of one zero edge modulo X.

We proceed precisely as in case 1, following the two subcases described there.

CASE 3: G has no periodic or zero edges relative X.

We first check if f satisfies the initial segments condition (for the train track part of G, i.e. for the edges of G − G′). If not, we subdivide the edges of G as explained after 3.11 above to achieve the initial segments condition. This gives rise to new periodic or zero edges (the initial and terminal segments of the original edges of G − X). Hence the transition matrix M(f) may not be any more irreducible, and we may have to use iteratively finitely many times the above two cases before proceeding with this case 3, but now with the hypothesis that the initial segments condition is satisfied:

Let G′_{0} be the union of all essential components of G′, so that the restriction f′_{0} : G′_{0} → G′_{0} of f′ induces a π_{1}-isomorphism on each connected component (or is actually a homotopy equivalence, as in our applications in the next sections).

Consider now any edge e of G and any maximal subpath γ of f(e) which is contained in G′. From property (3) of Definition 3.6 we know that there is some t(γ)-th iterate of γ which reduces to a legal path. Similarly, we know from Lemma 3.10 that for any inessential component X′_{v′} of G′ which is mapped by f to an essential component of G′ there is a quotient X′′_{v′} of X′_{v′} as well as a t(v′)-th iterate which is homotopic to a map where the image of any reduced path in X′ is legal. Every inessential component of G′ will be replaced by homeomorphic copies of the corresponding quotient X′′_{v′}.

Let t be the maximum of all such t(γ) and t(v′). We now apply Remark 3.5 and obtain a new map f_{∗} : G_{∗} → G_{∗} which commutes with f via a homotopy equivalence (or at least a map which induces an isomorphism on π_{1}).

We claim that this map is a partial train track map relative to X′ rather than just relative to X = G′: We show that all iterates of any edge are legal paths. For the edges of the essential components of G′ this is clear, as (in applying Remark 3.5) we haven’t changed the original train track map. For the inessential components of X′ it follows directly from the above described modification. Finally, for an edge e of G we use the initial segments condition to guarantee that in any iterate of e the composition of the above constructed maximal legal subpaths in G′ or their (legal !) iterates with adjacent edges from G form indeed a legal path.

Thus all hypotheses of Lemma 3.8 (b) are satisfied, and hence this lemma gives us the desired result.

The reader verifies easily that, indeed, the above procedure is algorithmic, and, second, that indeed the expansion of INP’s and the corresponding addition of auxiliary edges to the relative part keeps the iterative property of X_{∗} as claimed.

⊔ ⊓

4. The structure theorem for outer automorphisms of F_{n}

We now want to show that every automorphism α ∈ Aut(F_{n}) is represented by a particular partial train track map with Nielsen faces f : G → G. By this we mean that there is an isomorphism π_{1}G ˜=F_{n}, such that f induces on π_{1}G an outer automorphism which, via this isomorphism π_{1}G ˜=F_{n}, is equal to the outer automorphism α̂ induced by α.

For any 2-complex Γ^{2} and any map g : Γ^{2} → Γ^{2} which represents α we say that the map g or the automorphism a is of polynomial growth if all irreducible diagonal block submatrices of the geometric transition matrix M(g) are periodic or 0. The existence of such a map g is equivalent (compare [3] or [6]) to the fact that the growth (with respect to any fixed basis of F_{n}) of any conjugacy class [α^{t}(w)] in F_{n} is bounded above by a polynomial in t. In this case, any relative train track representative g : Γ → Γ of α (as introduced in [3] and derived there algorithmically from α) is of polynomial growth.

Proposition 4.1. Every automorphism α of a free group can be represented by a partial train track map f : G → G with Nielsen faces and no periodic or zero edges, such the restriction to the vertex groups is of polynomial growth. Moreover, G and f can be derived algorithmically from a relative train track representative of α.

Proof. We prove this by induction over the rank n of the free group F_{n}: Let g : Γ → Γ be a relative train track representative of α. As discussed before Remark 3.5, we can reinterprete this as a partial train track map without Nielsen faces where the top stratum of Γ is the train track part and the union of all lower strata is the relative part. (Alternatively, one can use directly Corollary 5.3 of [16] to get a partial train track representative of α). Without loss of generality the top stratum is not a 0-stratum (otherwise we may erase it and start all over with the remainder), so that all essential components of the relative part have free groups of strictly smaller rank than n as fundamental groups. By inductive hypothesis the restricted automorphisms can be represented by a partial train track map f′ : G′ → G′ which satisfies the claim in question. We can replace the union of the lower strata by these partial train tracks and contract the inessential components to single points. This defines a 2-strata partial train track f : G → G relative X = G′ as in Proposition 3.12 which represents the same automorphism α, and our claim is given directly by that proposition. ⊔ ⊓

As a consequence we can extend the facts proved in [6] and in the previous sections from absolute or relative train tracks to partial train tracks with Nielsen faces. In fact, the construction of a projectively α-invariant R I -tree T from a train track representative of α is done in [6, section 2] for δ-hyperbolic spaces. One only has to prove that the d_{∞}-pseudo-metric defined on G̃ is indeed given by the Perron-Frobenius eigenvector v used there. This follows directly from the fact that legal paths are geodesics with respect to the metric defined by the length function L_{v}(^{.}), as shown in the above Lemma 3.9.

For the converse direction (Theorem 1.2’) we first need to show:

Proposition 4.2. Let T be an R I -tree with very small minimal isometric action of F_{n}, and let G be a pseudo-metric 2-complex with π_{1}G = F_{n}. Let i : G̃ → T be an equivariant map which maps every subset of G̃ that has diameter 0 (with respect to the lift of the pseudo-metric) to a single point of T. Then this map i satisfies BBT: There is a constant BBT (i) > 0 such for that every geodesic segment [x, y] ⊂ G̃ the image i([x, y]) is contained in the BBT (i)-neighborhood of the geodesic segment [i(x), i(y)] ⊂ T.

Proof. Let d be the pseudo-metric on G̃, and let d′ be any metric obtained from d by equivariantly “blowing up” the maximal subspaces of diameter 0. Notice that d(x, y) ≤ d′(x, y) for all x, y ∈ G̃.

Notice also that by assumption there exists a constant K > 0 such that dist(i(x), i(y)) ≤ Kd(x, y) for all x, y ∈ G̃.

We use the fact that the fundamental group of G is free, and hence there is a homotopy equivalence h : G → Γ onto some connected finite metric graph Γ. Notice that its F_{n}-equivariant lift h̃ : G̃ → Γ̃ is a quasi-isometry, say with quasiisometry constants λ > 0 and ϵ ≥ 0, with respect to d′ and to the metric on Γ̃ lifted from Γ. We choose an F_{n}-equivariant map j : Γ̃ → T and observe that there is a constant C > 0 such that i(x) and jh̃(x) are at distance at most C for all x ∈ G̃.

Now let γ : [0, 1] → G̃ be a d-geodesic i-backtracking path with endpoints x, y ∈ G̃, and consider the image path h̃γ in Γ̃ as well as its reduction relative endpoints [h̃γ] which is a geodesic as Γ̃ is a tree. As T satisfies BBT, there is a bounded backtracking constant BBT (j) > 0, such that j([h̃γ]) is contained in the BBT (j)-neighborhood of the geodesic segment [jh̃(x), jh̃(y)] and hence in the BBT (j) + C-neighborhood of the point i(x) = i(y). Thus any point of γ which is mapped by i outside the BBT (j) + 2C-neighborhood N of i(x) = i(y) must be contained in a maximal h̃-backtracking subpath γ_{0} of γ. The latter has its endpoints mapped by h̃ to [h̃γ] and hence by i into N ⊂ T. But the d′- length of γ_{0} is bounded by ϵ, and so is its d-length, which implies that i(γ_{0}) is contained in the \frac{1}{2}Kϵ-neighborhood of its common endpoint in T. This shows that BBT (j) + 2C + \frac{1}{2}Kϵ is a backtracking bound for i. ⊔ ⊓

We can now extend the proof given in section 2 from absolute train tracks to train track maps with Nielsen faces f : G → G as considered in Proposition 4.1:

We first define a map i on every connected component X̃_{v} of the full preimage X̃ in G̃ of the relative part X ⊂ G in precisely the same way as explained before Proposition 2.5, which proof extends directly. As the automorphism grows polynomially on X, while the given homothety H : T → T with stretching factor λ > 1 reflects exponential growth, any map i which satisfies if̃ = Hi must map all of any component X̃_{0} to a single point.

We then proceed, as in Lemma 2.6, by extending i geodesically to the edges of the train track part of G. However, as G̃ is not necessarily a tree and reduced paths may not be geodesic, we have to use a little care in extending the proof of Lemma 2.6:

We proceed iteratively by using the strata structure of G from the proof of Proposition 4.1 by first considering the lowest stratum, which has already the train track property before adding any 2-cells. Hence the proof of Lemma 2.6 applies to this stratum.

We then define a length on the edges of this stratum by pulling back the idistance of their endpoints as in the beginning of the proof of Proposition 2.1 and argue as there to show that this length function determines an eigenvector of the corresponding submatrix of the transition matrix M(f). This enables us to use Lemma 3.9 to argue that, after expanding all Nielsen faces of this stratum, legal paths are geodesics.

We can now pass to the next stratum, again first without 2-cells. As we know that the f^{t}-images of any edge of this stratum are legal, for all t ≥ 1, the previous argument ensures that they are also geodesic, so that again the proof of Lemma 2.6 applies: The latter is based in the property BBT (for geodesics !), which is shown in Proposition 4.2 above, in the form needed here.

The same arguments apply iteratively to all higher strata, which completes the proof of the analogue of Lemma 2.6. The final step, the proof of Proposition 2.1, extends canonically.

This shows Theorem I of the Introduction, restated here in the following more explicit form:

Theorem 4.3. Let α ∈ Aut(F_{n}), and let f : G → G be a partial train track representative of α as in Proposition 4.1 (i.e. with Nielsen faces and no periodic or zero edges, relative to a subspace on which f has polynomial growth).

(a) Every non-negative eigenvector v with eigenvalue λ > 1 of the geometric transition matrix M(f) defines a non-trivial minimal R I -tree T_{v} with small isometric F_{n}-action and a homothety H_{α} : T_{v} → T_{v} with stretching factor λ which satisfies α(w)H_{α} = H_{α}w : T_{v} → T_{v} for all w ∈ F_{n}. Furthermore, the F_{n}-action on T_{v} has trivial arc stabilizers.

(b) Conversely, given a non-trivial minimal R I -tree T with small isometric F_{n}- action and a homothety H : T → T with stretching factor λ > 1 which satisfies α(w)H = Hw : T → T for all w ∈ F_{n}, there exists a non-negative eigenvector v of M(g) with eigenvalue λ and an F_{n}-equivariant isometry j : T_{v} → T which satisfies Hj = jH_{α}.

(c) For every eigenvector v there is an F_{n}-equivariant map i : G̃ → T_{v} such that H_{α}i = if̃, where f̃ is the lift of f to G̃ which satisfies α(w)f̃ = f̃w : G̃ → G̃ for all w ∈ F_{n}. Here i maps every edge e and more generally any legal path in G̃ isometrically (with respect to the d_{v}-metric, given by the length function L_{v} defined on Edges(G)) to a geodesic segment in T_{v}. ⊔ ⊓

The set of non-negative eigenvectors v with eigenvalues strictly bigger than 1, for the non-negative matrix M(f), is a subset of the non-negative cone of R I ^{Edges(G)}. Hence it carries a linear structure and has (finitely many) extremal points. It is possible to show that these properties are intrinsic properties of the set of α-invariant R I -trees and thus independent of the particular train track map used. Notice the fact (see [7]) that the stabilizer of a branchpoint in T is always of smaller rank than n. Such a branchpoint is given as the i-image of a connected component of full preimage of the 0-part of v, i.e. the union of the relative part of G together with all edges e with v_{e} = 0. This gives the possibility for an effective structural analysis of α by decomposing F_{n} into a family of iteratively defined canonical (up to finitely many choices) α-invariant subgroups of strictly smaller rank, where the α-action on each “stratum” is reflected by an α-invariant R I -tree action with λ > 1, except for the “bottom stratum”, where α has polynomial growth. For example, if α is geometric, i.e. induced by a homeomorphism h of a surface with boundary, then the Nielsen-Thurston classification of h is a special case of this structural analysis.

However, for the purpose of this paper we do not need all of this structural analysis, and hence we will here not persue this further. In Part II we only need the following:

Corollary 4.4. Let f : G → G and f′ : G′ → G′ be two partial train track maps with Nielsen faces and no periodic edges, both relative to subspaces on which f and f′ are polynomially growing. Assume that both, f and f′ represent the same automorphism α ∈ Aut(F_{n}): there is a homotopy equivalence h : G → G′ which commutes up to homotopy with f, f′. Then to every non-negative eigenvector v of M(f) there is canonically associated a non-negative eigenvector v′ of M(f′), and the homotopy equivalence h restricts to a homotopy equivalence between the essential components of the 0-parts on G and G′ defined by v and v′. This restriction of h commutes up to homotopy with the corresponding restrictions of f and of f′.

⊔ ⊓

In the 1:1 correspondence between eigenvectors from this corollary clearly the partial order of R I -tree actions is preserved, which is defined by the inclusion on the associated set of conjugacy classes of elements w ∈ F_{n} that have translation length 0. It is easy to see that the maximal R I -trees T_{v} with respect to this partial order are precisely the ones which have exactly one non-periodic irreducible diagonal block in the transition matrix, modulo the 0-part of v. In particular, up to scalar multiples such an eigenvector v is uniquely determined by its 0-part among all non-negative eigenvectors of M(f) with eigenvalue strictly bigger than 1. In analogy to the situation of a surface homeomorphism which is on a subsurface a pseudo-Anosov self-map, we will call such an action on T_{v} a relative pseudo-Anosov action and T_{v} a relative pseudo-Anosov R I -tree. For any such eigenvector v of the transition matrix M(f), for f as in Corollary 4.4, we define a new partial train track map, called a relative pseudo-Anosov train track map, by adding all edges e of G in the 0-part of v to the relative part X. Hence, if f : G → G is relative pseudo-Anosov, then there is (up to rescaling) precisely one eigenvector with eigenvalue λ > 1, and this Perron-Frobenius eigenvector is strictly positive on all edges of G.

As by Theorem 4.3 there are only finitely many relative pseudo-Anosov R I -tree actions (up to rescaling), for any α ∈ Aut(F_{n}), we have proved:

Theorem 4.5. Every automorphism α of F_{n} either is polynomially growing, or else there exists a non-empty finite family of relative pseudo-Anosov R I -trees T_{i}, and one can algorithmically derive from α for each of the T_{i} a relative pseudo-Anosov train track map f_{i} : G_{i} → G_{i} which represents α and satisfies T_{i} = T_{v_{i}} for the (up to scalar multiplication uniquely determined) eigenvector v_{i} of M(f_{i}) with λ > 1. If f′ : G′ → G′ is another relative pseudo-Anosov representative of α with relative pseudo-Anosov R I -tree T′, and if there is an equivariant isometry T_{i} → T′, then there is a homotopy equivalence h : G_{i} → G′ which is a map of pairs and commutes with f, f′ up to homotopy of pairs. ⊔ ⊓

This theorem is the essential tool which we use in Part II to define an inductive procedure which determines the conjugacy class of α. It is noteworthy that without a further normalization process (see [15]) the properties of the transition matrix of such a pseudo-Anosov R I -tree action are not very well determined by the R I -tree: For example, it may well occur that two relative pseudo-Anosov train track maps f and f′ determine the same R I -tree, but the matrix M(f) is irreducible, while M(f′) is reducible.

We finish this section with a lemma on relative pseudo-Anosov train track maps which is needed in the next section. First we need to recall some notation from [6]:

Consider a point Q in an R I -tree T with wH^{t}(Q) = Q for some t ≥ 1, w ∈ F_{n}, for some homothety H with stretching factor λ > 1. In [6] it was pointed out that every direction at Q contains precisely one eigenray: This is an infinite geodesic path ρ in T which starts at Q and is wH^{t}-invariant. It is easy to see that F_{n}- translates and the H-images of eigenrays are again eigenrays in T. The proof of the following is a direct consequence of our discussion of eigenrays in G in the last section, and of the fact that M(f) has only one diagonal block which is nonperiodic, and none which is 0.

Lemma 4.6. For any eigenray ρ in a pseudo-Anosov R I -tree T there is a legal path R̃ in G̃, the lift of an eigenray R in G, which is mapped by i isometrically onto ρ. Any two such paths R̃ and R̃′ agree up to finite initial segments R̃_{0} ⊂ R̃ and R̃′_{0} ⊂ R̃′, and if these have v-length > 0 then their images in G form an INP. All INP’s in G come from an eigenray ρ in T in such a way. Every edge of G is contained in the image R of any such R̃ ⊂ G̃. ⊔ ⊓

References

1. M.Bestvina, M.Feighn, Outer limits, preprint.

2. M.Bestvina, M.Feighn, M.Handel, The Tits Alternative for Out(F_{n}) I, II, preprints.

3. M. Bestvina, M. Handel, Train tracks for automorphisms of the free group, Annals of Math. 135 (1992), 1–51.

4. M.M.Cohen, M.Lustig, The conjugacy problem for Dehn twist automorphisms of free groups, Comment. Math. Helv., to appear.

5. W. Dicks, E. Ventura, The group fixed by a family of injective endomorphisms of a free group, Contemporary Mathematics 195, Providence, RI: AMS, (1996).

6. D. Gaboriau, A. Jaeger, G. Levitt, M. Lustig, An index for counting fixed points of automorphisms of free groups, Duke Math. Jour. 93 (1998), 425–452.

7. D. Gaboriau, G. Levitt, The rank of actions on R-trees, Ann. Sci. Ec. Norm. Super., IV. Ser. 28 (5) (1995), 549–570.

8. S. Kristic, A uniqueness decomposition theorem for actions of finite groups on free groups, J. Pure Appl. Algebra 61 (1989), 29–48.

9. S.Krstic, M.Lustig, Vogtmann, An equivariant Whitehead algorithm and conjugacy for roots of Dehn twists, Proc. Edinburgh Math. Soc., to appear.

10. J.Los, On the conjugacy problem for automorphisms of free groups. With an addendum., Toplogy 53 (1996), 779–808.

11. M. Lustig, Automorphismen von freien Gruppen, Habilitation thesis (1992).

12. M. Lustig, Automorphisms, train tracks and non-simplicial R I -tree actions, unpublished preprint 1993.

13. M. Lustig, Prime decomposition and conjugacy problem for Out(F_{n}), unpublished survey preprint 1994.

14. M. Lustig, Structure and conjugacy for automorphisms of free groups, http://homepage.ruhruni-bochum.de/Martin.Lustig, April 1999.

15. M. Lustig, private notes.

16. M. Lustig, U. Oertel, Invariant Laminations for Diffeomorphisms of Handlebodies, Quart. J. Math. Oxford, to appear.

17. Z.Sela, The isomorphism problem for hyperbolic groups. I., Ann. Math., II. Ser. 141 (2) (1995), 217–283.

18. Z.Sela, The Nielsen-Thurston classification and automorphisms of a free group. I.,II., preprints.

19. R.Skora, unpublished preprint.

Laboratoire de Mathématiques, Faculte des Sciences (St. Jérome), Avenue Escadrille Normandie-Niemen, Université d’Aix-Marseille III, 13397 Marseille Cedex 20, France

E-mail address: Martin.Lustig@math.u-3mrs.fr, lustig@mpim-bonn.mpg.de