STRUCTURE AND CONJUGACY FOR

AUTOMORPHISMS OF FREE GROUPS II

Martin Lustig

Part II: REFINED STRUCTURAL ANALYSIS AND THE ALGORITHM

The goal of this Part II is to present a complete effective algorithm to decide whether two automorphisms of a free group F_{n} are conjugate or not. As in Part I (see [17]), we will use a K(π, 1)-space Y with π_{1}Y = F_{n} and a homotopy equivalence f : Y → Y to represent an outer automorphism α̂ = f_{∗} of F_{n}. If a second automorphism α̂′ is represented by f′ : Y′ → Y′, we see that α̂ is conjugated to α̂′ in Out(F_{n}) if and only if there exists a homotopy equivalence h : Y → Y′ which satisfies f′h = hf up to homotopy in Y′. In this case we say that h commutes with f, f′ up to homotopy, or that h_{∗} conjugates f_{∗} to f′_{∗}. With any such map h, any other map h′ = f′^{t′}hf^{t} with t, t′ ≥ 0 also commutes with f, f′ up to homotopy. This is expressed by saying that h_{∗} and h′_{∗} agree up to powers of the automorphism, or that h and h′ are in the same f′-orbit.

Our strategy for the algorithm is based on the structural results of section 4 of Part I [17]: By Theorem 4.5 there are only finitely many ways to represent α as a relative pseudo-Anosov train track map, up to conjugation with a homotopy equivalence h which preserves the vertex spaces. In section 5 we will show that, once one choses such relative pseudo-Anosov representatives f : G → G, f′ : G′ → G′ for the given automorphisms α̂, α̂′ ∈ Out(F_{n}), then, up to powers of the automorphism, there are only finitely many possibilities how the induced relative maps f_{Γ} and f′_{Γ} on the train track parts can be conjugated, modulo a conjugacy problem for the induced automorphisms on the vertex groups of G and G′. As the rank of the fundamental group decreases strictly when passing from G to a vertex group, this gives an effective recursive procedure, if one takes properly care of the gluing information between the train tack part and the vertex groups of the partial train tack maps. This is explained in detail in section 6.

This leaves us with the case of polynomially growing automorphisms, which are treated in a similar spirit, but with different methods, in section 7. There a similar recursion method is explained which reduces the problem to linearily growing automorphisms. For those the conjugacy problem has been solved, in a joint effort with M.M.Cohen [5] for Dehn twists, and with S.Krstic and K.Vogtmann [11] for

Typeset by AMS-TEX

roots of such. We describe in section 8 how the results of these earlier papers can be inserted into the program persued here to complete the algorithm, which is then summarized in section 9. In that section we also show how our Theorem III (see the Introduction of [17]) about the centralizer of α̂ in Out(F_{n}) follows from the material presented here and in Part I [17], and prove an analogous (more complicated) statement for the centralizer of an arbitrary element in Out(F_{n}).

5. Conjugacy between relative pseudo-Anosov train track maps

In this and the next section we consider relative pseudo-Anosov train track maps f : G → G as defined in section 4 of in Part I [17]. In particular, G is homotopy equivalent to a graph with fundamental group F_{n}, there are no periodic or zero edges in the train track part Γ_{G} of G, and there is (up to scalar multiples) precisely one Perron-Frobenius eigenvector v with eigenvalue λ > 1. As explained in section 4 of Part I [17] such v determines a length function on the edges of G, which will be refered to below as the PF-length of edges or paths in G. By definition all edges of G have PF-length > 0, so that the PF-length and the simplicial length on G are comparable. We denote the (outer) automorphism induced by f on π_{1}G by f_{∗} and say that f represents a given α̂ ∈ Out(F_{n}), if for some identification π_{1}G = F_{n} (called the marking of G) one gets f_{∗} = α̂.

For technical reasons we assume furthermore that all pseudo-Anosov train track maps in this and the following sections satisfy the initial segments condition 3.11 of Part I [17]. It has been shown in section 3 of Part I [17] how this condition can be achieved easily through an effective modification of the given train track map.

The goal of this section is to show how one can decide if any two given relative pseudo-Anosov train track maps f : G → G and f′ : G′ → G′ are conjugated by a map of pairs h : G → G′, up to homotopy and up to an induced analogous problem on the vertex spaces:

Theorem 5.1. There exists an algorithmic procedure which, given two relative pseudo-Anosov train track maps f : G → G and f′ : G′ → G′, either assures that there exist no map of pairs h : G → G′ which conjugates the induced automorphism f_{∗} to f′_{∗}, or else produces two finite families of modified relative pseudo-Anosov train track maps f_{m} : G_{m} → G_{m} and f′_{m} : G′_{m} → G′_{m} representing the same automorphisms as f and f′ respectively, as well as a family of graph isomorphisms h_{Γ}_{m} : Γ_{G_{m}} → Γ_{G′_{m}} on the train track parts, with f′_{m}_{Γ}h_{Γ}_{m} = h_{Γ}_{m}f_{m}_{Γ} (honestly, not just up to homotopy !) such that every possible conjugator between f_{∗} and f′_{∗}, up to powers of the induced automorphism, is represented by a map h : G_{m} → G′_{m} which induces on the train track part a map h_{Γ} which agrees with one of the h_{Γ}_{m}.

Remark 5.2. The graph isomorphisms h_{Γ}_{m} from this last theorem and the equation f′_{m}_{Γ}h_{Γ}_{m} = h_{Γ}_{m}f_{m}_{Γ} extend canonically to the Nielsen faces of G and G′, as their existence and the restriction of f to them is determined by the periodic INP’s in Γ_{G}.

We first consider a special case where the main ideas will become appearent: Let f : Γ → Γ and f′ : Γ′ → Γ′ be two absolute train track representatives of the same automorphism α̂ ∈ Out(F_{n}), and assume that Γ′ does not contain an INP or a periodic INP. Then by the assumption that f and f′ are relative pseudo-Anosov there exist (up to scalar multiples uniquely determined) non-negative eigenvectors v and v′ with eigenvalues strictly bigger than 1, and from Theorem 4.3 it follows that the associated α-invariant limit R I -trees T_{v} and T′_{v} are, up to rescaling, F_{n}-equivariantly isometric, and hence denoted from here on simply by T. Furthermore, there is a homothety H : T → T with stretching factor λ > 1, equal to the eigenvalue of both, v and v′, and there are F_{n}-equivariant maps i : Γ̃ → T and i′ : Γ̃′ → T with if̃ = Hi and i′f̃′ = Hi′ which map legal paths to geodesic segments of same length (see Theorem 4.3). Notice for our algorithmic purposes that it is possible to compute approximations of v, v′ and λ up to any degree of precision.

The main goal of the first part of this section is to show that under these conditions there exists a map h : Γ → Γ′ such that hf = f′h (honestly, not just up to homotopy !), and where the length of h(e) for each edge e of Γ is bounded a priori in terms of data read off from f, Γ, f′ and Γ′. Up to a local homotopy there are only finitely many possible such maps h, and hence a finite search (with details given below) will directly decide whether two given such train track maps f and f′ represent the same outer automorphism of F_{n} or not.

We first recall (see [8]) that the BBT-constant for i is bounded by the v-volume of Γ (and similarly for i′, v′ and Γ′). We introduce (compare [13]) a number p(i), the parallelity of i, which is the maximal distance d ≥ 0 such that any two legal paths γ, γ′ in Γ of v-length d which start at the same vertex and belong to the same gate satisfy i(γ) = i(γ′). Notice that, since Hi = if, for the analogously defined parallelity p(f) one has p(f^{t}) ≤ p(i) for all t ≥ 1. It follows directly from the definition of “gates” and from v > 0 that p(f^{t}) > 0 for suitably large t (and hence p(i) > 0).

We now assume that p(i) > 2BBT (i′), and that all edges of Γ have v-length bigger than 4BBT (i′). If this is not the case, we can simply twist the marking of Γ′ by a suitable power of α, thus obtaining the same train track map but a new map i′ which is related to the old map i′_{old} by i′_{old} = i′f̃′^{t} = H^{t}i′ for some large t > 0, with the effect that the i′-image is scaled down by the factor \frac{1}{λ^{t}}.

For any s > 0 with BBT (i′) < s < min\{\frac{1}{2}p(i), \frac{1}{4}L_{v}(e) | e edge of Γ\} we now define a standard s-neigborhood N(x) for each point x ∈ Γ as follows: If x is within distance s of a vertex v ∈ Γ, then x is called exceptional, and we define N(x) to be the neighborhood of radius 2s of v (not of x !). Otherwise x is regular and N(x) is the s-neighborhood of x. We notice that by our assumption on the minimal length of the edges of Γ every N(x) is the union of initial segments of edges raying out of v in the exceptional case or of inner segments raying out of x in the regular case.

It follows that any connected component N(x̃) of the full lift of N(x) to Γ̃ is homeomorphic to N(x) and hence contains precisely one preimage x̃ of x. From our assumption s < \frac{1}{2}p(i) it follows that in the regular case i(N(x̃)) is a geodesic segment of length 2s centered at i(x̃), while in the exceptional case it is a union of initial segments of length 2s of some of the eigenrays starting at i(ṽ). Notice that from Lemma 4.6 it follows that even in the regular case the geodesic segment i(N(x̃)) belongs to some eigenray. In the exceptional case notice that from Lemma 4.3 it follows furthermore that every point in i(N(x̃)) belongs to some eigenray which also contains two extremal points of i(N(x̃)).

The next observation uses the inequality BBT (i′) < s: We lift i(N(x̃)) via i′ to Γ̃′ but only consider those points of the full preimage which are part of a legal path with endpoints that are mapped by i′ to endpoints of i(N(x̃)). From Lemma 4.3 it follows that every point of i(N(x̃)) has a preimage in this special subset N′(x̃) ⊂ i′^{−1}(i(N(x̃))).

It may well occur that some points of i(N(x̃)) have more than one i′-preimage x̃′ in this special subset N′(x̃). This however can not happen for the point i(x̃) if x is regular, as then some endpoint y of i(N(x̃)) must also have distinct i′-lifts y′, y′′ ∈ Ñ, and the geodesic arc in Γ̃′ connecting y′ to y′′ would pass through the two distinct i′-lifts of i(x̃) and thus not be mapped by i′ into the s-neighborhood of y, contradicting BBT (i′) < s. In the exceptional case, where x is close to a vertex v, this argument fails, as there might be a choice of which of the initial segments of edges raying out of v one choses to form the legal segment of length 2s, and and different choices may indeed lead to different i′-preimages x̃′ ∈ N′(x̃) for i(x̃). There are, however, only finitely many such possibilities, as we get the following description of N′(x̃): Every point z of i(N(x̃)) of distance s to i(ṽ) has precisely one preimage z̃′ in N′(x̃). The eigenray segment of i(N(x̃)) which starts at z and moves away from i(ṽ)) lifts to a union of legal paths, all starting at z̃′. The eigenray segment of i(N(x̃)) which starts at z and moves towards i(ṽ) lifts to the “unique” lift [z̃, ṽ] of the eigenray: By Lemma 4.3 this uniqueness fails precisely in the neighborhood of v if there is an (elementary or generalized) INP in Γ̃′ which covers the initial segment of this eigenray. However, as every generalized INP in Γ̃ is a union of only finitely many elementary INP’s, one has indeed only finitely many possibilities for the lift of i(x̃) to N′(x̃). In the special case considered presently, where Γ′ does not contain an INP, it follows from Lemma 4.3 that there is indeed only one choice for the segment [z̃, ṽ] and hence for the point x̃′ ∈ N′(x̃) with i′(x̃′) = i(x̃).

The obvious equivariance of the above discussion gives us a well defined point x′ in Γ′ which is the image (under the covering map Γ̃ → Γ) of the unique i′- lift x̃′ ∈ N′(x̃) ⊂ Γ̃′ of i(x̃). As i and i′ map legal paths isometrically to T, the correspondence x ↦ x′ is continuous and thus defines a map h : Γ → Γ′ which maps legal paths to legal paths. It follows directly from the definition of h that its F_{n}-equivariant lift h̃ : Γ̃ → Γ̃′ satifies i = i′h̃. This in turn shows that i′f̃′h̃ = Hi′h̃ = Hi = if̃ = i′h̃f̃, i.e. f̃′h̃(x) and h̃f̃(x) are mapped by i′ to the same point in T. Since the same is true for legal segments instead of points x, and sufficiently long such segments have a i′-lift to Γ̃′ which is well defined except possibly for boundary subsegments of length ≤ s, it follows f̃′h̃(x) = h̃f̃(x) for all x ∈ Γ̃. This gives the desired equation hf = f′h : Γ → Γ′ in this special case.

We now pass gradually to the general case: Let us first continue to assume that the vertex groups are trivial, but we now allow INP’s in Γ′ which span corresponding Nielsen faces. Then everything works as before, except that for a vertex v of Γ the lift ṽ′ of i(ṽ) to Γ̃′ may not be any more well defined among some of the vertices of Γ̃′, if these are the endpoints of an INP η̃. In this case we simply take an F_{n}-equivariant choice for ṽ′, arrange all other lifts of points in the s-neighborhood of i(ṽ) to match this choice, and use the auxiliary edges in the boundary of the Nielsen faces to extend the h̃-images of those edges adjacent to ṽ which otherwise had h̃-images ending at another of the possible lifts of i(ṽ). The consequence of these “random” choices is that the equation hf(x) = f′h(x) only holds for the regular points x, while for the exceptional ones it only holds up to a suitably chosen homotopy, which takes place entirely in the the Nielsen face which bounds the INP η. More precisely, the homotopy exchanges precisely one legal branch of η by the other. This situation is described by saying hf = f′h holds up to Nielsen faces.

Now consider the next case, with non-trivial vertex groups, but no INP’s. Here we can literally use the same construction as in the above special case, if we replace Γ̃ by Γ̃_{G} and Γ̃′ by Γ̃′_{G}. The only difference is that N(x̃) is not any more homeomorphic to N(x), but this does not disturb the above given arguments, in particular concerning the possible i′-lifts of i(x̃). Of course, in this case the equation hf(x) = f′h(x) on the train track part is meant (as throughout Part I [17]) only up to homotopy which completely takes place in the relative part, i.e. we get h_{Γ}f_{Γ} = f′_{Γ}h_{Γ}. If we now admit, in addition, the existence of INP’s and Nielsen faces, we have to do precisely the same adjustments as above.

This proves:

Proposition 5.3. For any two relative pseudo-Anosov train track maps f : G → G and f′ : G′ → G′ there is a constant C = C(f, f′) which can be computed from f and f′, such that, if h′ : G → G′ is a map of pairs with h′_{∗}f_{∗} = f′_{∗}h′_{∗} then there exists a map of pairs h : G → G′ with h_{∗} = h′_{∗} up to powers of the automorphism, such that the simplicial length of the edge path h(e) is bounded by C, for any edge e of G, and such that on the train track part of G one has h_{Γ}f_{Γ} = f′_{Γ}h_{Γ} up to Nielsen faces. ⊔ ⊓

Remark 5.4. For future purposes we want to specify that our above proof also shows that the F_{n}-equivariant lift h̃ : G̃ → G̃′ has the property that it commutes with the canonical maps i : G̃ → T and i′ : G̃′ → T: One has i′ = h̃i, and this equation stays valid independently which of the possible choices one has taken at INP’s in G′ which are not matched by INP’s at exceptional points of G.

For our further purposes it is convenient to improve the situation so that h_{Γ}f_{Γ}(x) = f′_{Γ}h_{Γ}(x) holds honestly even for the exceptional points x ∈ Γ_{G}. We use the map h constructed above to modify Γ_{G} (and correspondingly G) locally in the s-neighborhood of those vertices v where the equation h_{Γ}f_{Γ}(x) = f′_{Γ}h_{Γ}(x) only holds up to Nielsen faces, by blowing up these vertices in the following way: We replace the edge e in Γ_{G}, which terminates in a segment e′ of length ≤ s that is mapped to one of the two branches of an INP η, by an “initial” edge e_{0} corresponding to e − e′, and by two branches e′ and e′′ which start at the endpoint of e_{0} and are mapped by h to the two “branches” of η. If v was an f-periodic vertex and ē the initial edge of an eigenray, then the path ē′e′′ is a periodic INP for f, at which we expand a Nielsen face (together with an auxiliary edge), as in Definition 3.7. Thus we introduce for each Nielsen face Δ′ of G′ which is unmatched in G a corresponding “local” Nielsen face to G, at every periodic vertex and every periodic gate of Γ_{G} which has a lift to Γ̃_{G} that is mapped by i to the same branchpoint and the same direction as the corresponding lift of Δ′. This blow up of G gives a new space G_{1} which admits a map f_{1} that agrees with f for all points with regular f-images, and is modeled on f′h otherwise. It is easy to see that f_{1} : G_{1} → G_{1} satisfies all properties of Definition 3.7 of Part I [17], so that it is a partial train track map with Nielsen faces, and that furthermore f_{1} inherits the relative pseudo-Anosov property from f. This shows:

Lemma 5.5. Given relative pseudo-Anosov train track maps f : G → G and f′ : G′ → G′ and a map of pairs h : G → G′ with hf = f′h up to Nielsen faces on the train track part, and with h′_{∗}f_{∗} = f′_{∗}h′_{∗} on π_{1}, then there exists a relative pseudo-Anosov train track map f_{1} : G_{1} → G_{1} and a map of pairs g_{1} : G → G_{1} with g_{1}_{∗}f_{∗} = f_{1}_{∗}g_{1}_{∗}, as well as a map of pairs h_{1} : G_{1} → G′ which satisfies h_{1}_{Γ}f_{1}_{Γ} = f′_{Γ}h_{1}_{Γ} on the train track part and induces h_{1}_{∗}f_{1}_{∗} = f′_{∗}h_{1}_{∗} on π_{1}. Furthermore Γ_{1}, f_{1}, g_{1} and h_{1} can be derived effectively from f, f′, G, G′ and h in finitely many steps. ⊔ ⊓

We are now ready for:

Proof of Theorem 5.1 . Recall that a relative pseudo-Anosov train track map acts strictly length increasing on all edges, with respect to the PF-metric. This implies that for the induced maps f_{Γ} : Γ_{G} → Γ_{G} and f′_{Γ} : Γ_{G′} → Γ_{G′} there are only finitely many periodic or eventually periodic points of any given order in Γ_{G} and Γ_{G′}. Thus we can subdivide the edges of Γ_{G′} so that all points of Γ_{G′} become vertices which have a period that occurs as divisor of one of the periodic vertices of Γ_{G}, as well as all points of Γ_{G′} which are f′^{k}-preimages of vertices, for any k ≤ k′ if some periodic vertex of f has a non-periodic f^{k′}-preimage vertex. This ensures that the map h_{Γ} of Proposition 5.3 must map vertices to vertices, and hence the question of whether there exists a map h (and hence h′) as in Proposition 5.3, and if so, to find all such maps, can be answered by finitely many tries. We apply Lemma 5.5 to improve each such f, G and h to f_{1}, G_{1} and h_{1} as given there.

From the equation i = i′h̃_{1}, see Remark 5.4, and from the definition of T through iteration of f_{1} or of f′, as well as from the above strict length increasing property of f_{1} and f′, it follows that any two edges of G_{1} which are folded by h_{1} must also be folded by a suitable power of f_{1} and hence the two edges are contained in the same gate at their common initial vertex. We use h_{1} to subdivide Γ_{G_{1}} (and accordingly G_{1}) by pulling back all vertices of Γ_{G′}, and, without ever having to subdivide again, we do iteratively folds at the illegal turns of G_{1}, until h_{1}_{Γ} becomes locally injective. Clearly f_{1} induces on these folded train tracks a relative pseudo-Anosov map (also denoted by f_{1}) which preserves the property h_{1}_{Γ}f_{1}_{Γ} = f′_{Γ}h_{1}_{Γ} on the train track part, given by Lemma 5.5. But locally injective equivariant maps between simplicial trees with minimal group action are tree isomorphisms, so that h_{1}_{Γ} has actually become a graph isomorphism. ⊔ ⊓ Remark 5.6. It should be noted that the analogue of Theorem 5.1 does not hold if the partial train track maps are not relative pseudo-Anosov. In fact, even if one has absolute 2-strata train track maps which are (relative) pseudo-Anosov on both strata, this analogue is easily seen to be wrong, by simply iterating the induced map on the lower stratum (as in Remark 3.5 of Part I [17]) and hence creating arbitrary large entries in the off diagonal block sub-transition-matrix corresponding to the two strata.

6. Fix point pattern

Definition 6.1. Given a topological space Y and a map f : Y → Y, a fixed point pattern is a finite, possibly non-connected graph Ω and a map ω : Ω → Y which maps vertices to periodic points or to eventually periodic points of f. If the ωimages of all vertixes are actually periodic, we say that Ω is without non-periodic vertices. The set of maps f^{t}ω : Ω → Y with t ≥ 0, up to homotopy relative to the vertices of Ω, is sometimes called the f-orbit [ω]_{f} of the fixed point pattern ω, and we do not distinguish between any two such f-orbits if one is obtained from the other by deleting finitely many of their maps.

Fixed point pattern occur naturally in the context of maps of graphs of spaces as introduced in section 3 of Part I [17]: If f : G → G is a map of pairs of spaces with union X of vertex spaces X_{v} and edge set Γ̂ which satisfies the initial segments condition 3.11 we obtain canonically an associated Ω-graph Ω_{f} and an associated fixed point pattern ω_{f} : Ω → X, where the vertices of Ω are in 1 − 1 relation with the mixed vertices of G (i.e. the points of Γ̂ ∩ X), and the edges of Ω correspond bijectively to the segments of f^{−1}(X) ∩ Γ̂, attached to the vertices as given by the map f. The map ω is simply the realization of f.

To simplify the subsequent arguments we can easily modify the vertex spaces of a partial train track within their homotopy type, by introducing additional edges at each mixed vertex, in order to satisfy the following:

Improved initial segements condition 6.2. Every edge satisfies the initial segments condition 3.11 of Part I [17], and at every mixed vertex there is precisely one edge of the train track part of G attached.

The following is an easy consequence of the definitions, but is rather basic for the sequel:

Proposition 6.3. Let f : G → G and f′ : G′ → G′ be maps of pairs of spaces which satisfy the improved initial segments condition 6.2. Let h_{Γ} : Γ_{G} → Γ_{G′} be a graph isomorpism which satisfies h_{Γ}f_{Γ} = f′_{Γ}h_{Γ} (directly, not up to homotopy). Let H_{Ω} : Ω_{f} → Ω_{f′} denote the induced isomorphism between the two associated Ω-graphs.

(1) Assume there exists a map of pairs h : G → G′ which induces an isomorphism h_{∗} : π_{1}G → π_{1}G′ with h_{∗}f_{∗} = f′_{∗}h_{∗} up to inner automorphisms. If h induces on Γ_{G} the map h_{Γ}, then (after modifying h by a suitable homotopy to ensures that h satisfies the initial segments condition and in particular maps mixed vertices to mixed vertices) for each vertex space X_{v} of G the map h restricts to a map h_{v} : X_{v} → X_{h_{Γ}(v)} with the following three properties:

(a) The induced map h_{v∗} : π_{1}X_{v} → π_{1}X_{h_{Γ}(v)} is an isomorphism,

(b) h_{v}f_{v} = f′_{h(v)}h_{v} up to a homotopy which fixes the mixed vertices, and (c) h_{v}ω|_{ω^{−1}(X_{v})} = ω′H_{Ω}|_{ω^{−1}(X_{v})} up to homotopy relative V ertices(Ω).

(2) If for each vertex v of Γ_{G} there is a map h_{v} : X_{v} → X_{h(v)} which satisfies the above three properties (a), (b) and (c), then the h_{v} together with h_{Γ} define a map of pairs h : G → G′ which induces an isomorphism h_{∗} : π_{1}G → π_{1}G′ with h_{∗}f_{∗} = f′_{∗}h_{∗} up to inner automorphisms. (In particular the map h induces on Γ_{G} the map h_{Γ} and restricts on each vertex space X_{v} of G to the map h_{v} : X_{v} → X_{h_{Γ}(v)}.) ⊔ ⊓

As we want to consider relative pseudo-Anosov train track maps, which may have Nielsen faces, we need to extend the definition of the associated fixed point pattern to the case where f : G → G is a partial train track map with a collection of Nielsen faces: In this case we add to the above introduced associated fixed point pattern ω_{f} : Ω_{f} → G for every periodic elementary Nielsen face Δ a new edge e_{Δ} to Ω which corresponds to the auxiliary edge of Δ. More precisely, if a periodic INP η in G together with a complementary path γ in X form the boundary of Δ, then e_{Δ} is mapped by ω_{f} to γ. We verify easily:

Remark 6.4. If f : G → G and f′ : G′ → G′ are partial train track maps with a collection of Nielsen faces, with associated fixed point pattern ω_{f} : Ω_{f} → G and ω′_{f} : Ω′_{f} → G′, then the analogue of Proposition 6.3 is valid.

To simplify the induction process over the various pseudo-Anosov strata of a train track representative of a given automorphism α of F_{n} we associate to any pseudo-Anosov train track map f : G → G with relative part X a second, simplified fixed point pattern ω_{f}^{s} : Ω_{f}^{s} → X which is obtained from ω_{f} as follows: For each non-essential component X_{v} which is mapped by f to an essential component we add the mixed vertices of X_{v} as new vertices to Ω, and we define ω on the new vertices to agree with f. Furthermore, for any pair of these new vertices we add a new edge to Ω, which is mapped by ω to the connecting path defined canonically by f(X_{v}). We also apply Remark 3.5 of Part I [17] to the essential components and thus achieve that the ω_{f}^{s}-images of the vertices of Ω_{f}^{s} are actually periodic and not just eventually periodic. We notice that the simplified associated fixed point pattern, together with the finite combinatorics of the restriction of f to the non-essential components X^{ne} of the relative part as well as the finite combinatorics of the restriction of ω_{f} to ω_{f}^{−1}(X^{ne}) allows one to reconstruct the associated fixed point pattern ω_{f}. This explaines why below we only deal with homotopy equivalences f, and only with fixed point pattern without non-periodic vertices.

Note that in the special case where the graph Ω of a fixed point pattern ω : Ω → Y consists only of a single point P which is mapped to fixed point of f : Y → Y, and similarly for ω′ : Ω′ = {P′} → Y′ and f′ : Y′ → Y′ with f′ω′(P′) = ω′(P′), the question, whether a homotopy equivalence h : Y → Y′ exists which maps ω(P) to ω′(P′) such that f′h = hf modulo homotopy relative ω(P), is equivalent to the classical question whether there is a homotopy equivalence from Y to Y′ which conjugates f to f′ and maps ω(P) into the same Nielsen fixed point class as ω′(P′).

Given a map f : Y → Y, every Nielsen class of fixed points of f_{∗} can be represented by attaching an extra edge e to Y at its initial point v to an arbitrary point of Y. The other endpoint v′ of e is called extra vertex. The map f is extended to e by defining it on the first half of e to run over a suitably chosen path γ which joins f(v) to v, and on the second half to cross over e. Similarly, if one wants to represent a fixed point class of any power f^{t} of f by a periodic point of period t, one glues t new edges e_{1}, e_{2}, …, e_{t} to Y at points v, f(v), f^{2}(v), …, f^{t−1}(v), defines f(e_{i}) = e_{i+1} for i = 1, …, t − 1 and f(e_{t}) = γe_{1}. The choice of γ determines the (periodic) Nielsen class, and all Nielsen classes can be realized in this way by fixed or periodic points, without changing the homotopy equivalence class of the space Y or the homotopy class of the map f. An analogous construction can be given for eventually periodic but non-periodic points, but we do not need this here.

Given two selfmaps of spaces g : Z → Z and f : Y → Y and a homotopy equivalence h : Z → Y with hg homotopic to fh via some homotopy H, this method can be used to transfer algorithmically a fixed point pattern ω : Ω → Z from Z to Y: One first adds for any vertex P of Ω an extra edge e (or a new orbit of edges) to Y as above, with initial point h(ω(P)), and with connecting path γ traced out by the homotopy H between h(ω(P)) = hg(ω(P)) and fh(ω(P)) (or between hg^{t}(ω(P)) and f^{t}h(ω(P)), if P has period t. We can then change h by a local homotopy which moves h(ω(P)) along e to its other endpoint, and obtain thus a homotopy equivalence h′ : Z → Y with h′g homotopic to fh′ via some homotopy H′ (an extension of H to the edge e) which fixes h′(ω(P)) for any vertex P of Ω. We now obtain the desired fixed point pattern ω′ : Ω → Y by simply defining ω′ = h′ω. After such a modification we say that Y admits the fixed point pattern hω.

Now we consider the special case Y = G and assume that f : G → G is a relative pseudo-Anosov train track map. Assume that g : Z → Z is conjugate to f via a homotopy equivalence h : Z → G, and that ω : Ω → Z is a fixed point pattern. As described above we introduce extra edges to G and transfer the fixed point pattern to get a fixed point pattern ω′ : Ω → G. We can now apply Proposition 3.12^{1} of Part I [17] to modify the extension of f to the extra edges, and in addition we change ω′ within its f-orbit, in order to achieve that

(i) the extra edges have legal images under f, so that the extension of f still has the partial train track property, and (ii) all edges of Ω are mapped by ω′ to legal paths.

This can be done algorithmically. We then check, as in section 3 of Part I [17], whether the extra edges have lead to new (periodic) INP’s, and, if so, expand correspondingly extra Nielsen faces in which process we introduce as in Definition 3.7 of Part I [17] new auxiliary edges, so that the resulting modification leads again to a relative pseudo-Anosov train track map. In particular the extra edges have non-zero PF-length or else belong by definition to the relative parts. In this latter case, or if the terminal vertex v′ of an extra edge is connected through the new auxiliary edges to a point of G (without extra edges), we say that v′ is X-connected. We notice that, as a consequence of (i), for any non-X-connected extra vertex v′ at an extra edge e the positive iterates f^{t}(ē) of the inverse edge ē are mapped to initial segments of eigenrays R_{f^{t}(v′)} in G which starts at the extra vertices f^{t}(v′). In fact, the edge ē is the first edge of the eigenray R_{v′}. For large t the initial segments f^{t}(ē) of the eigenrays R_{f^{t}(v′)} become long.

1Unfortunately an error has crept into that proof; a corrected version is given at the end of this section.

Now we assume that we are given f : G → G, f′ : G′ → G′ and h_{Γ} : Γ_{G} → Γ_{G′} as in Proposition 6.3. We add as above finitely many extra edges and extra Nielsen faces to both, G and G′, and assume that there are given two fixed point pattern ω : Ω → G and ω′ : Ω′ → G′ without non-periodic vertices as well as a graph isomorphism H_{Ω} : Ω → Ω′. For technical reasons we initially assume that each vertex of Ω or of Ω′ is mapped by ω or ω′ to one of the terminal vertices of the extra edges just introduced. We want to investigate the question whether there exists a map h : G → G′ as in Theorem 5.1 which induces the isometry h_{Γ} on the train track parts (without the extra edges) and commutes with f, f′ up to homotopy fixing the terminal endpoints of the extra edges, as well as integers t, t′ ≥ 0, such that f′^{t′}ω′H_{Ω} = hf^{t}ω up to homotopy relative to the set of vertices of Ω. According to the above discussion we can assume that for ω and ω′ the above conditions (i) and (ii) are satisfied.

For every vertex P of Ω we first want to check whether there is an extension of h to the extra edge e with terminal vertex v′ = ω(P) such that for suitable t, t′ ≥ 0 the two points f′^{t′}ω′H_{Ω}(P) and hf^{t}ω(P) agree, and h_{Γ}f_{Γ} = f′_{Γ}h_{Γ} up to homotopy relative to v′. As h_{Γ} is an isometry and f and f′ are partial train track maps even on the extra edges, we can compose, by property (3) of Definition 3.6 of Part I [17], any such extension h^{∗} of h by a suitable power of f′ to get a new map h^{∗∗} = f′^{t}h^{∗} which has the property that h^{∗∗}(e) reduces to a legal path γ, while h^{∗∗} still commutes with f, f′ up to homotopy relative v′ and honestly on the train track part (without e). We change the definition of h^{∗∗} on e so that h^{∗∗}(e) = γ and observe that this implies, by the same arguments as described in the proof of Lemma 3.9 of Part I [17], that (after a suitable reparametrization of h^{∗∗} along e and possibly after composing h^{∗∗} with further iterates of f) one gets, for G ∪ e, the equation h_{Γ}^{∗∗}f_{Γ} = f′_{Γ}h_{Γ}^{∗∗} up to Nielsen faces. As in the proof of Theorem 5.1 in the last section we can now fold G ∪ e until h^{∗∗} becomes an isometry onto its image and erase the positive length extra edges and the extra Nielsen faces from G′ which are not in the image of h^{∗∗}, so that we obtain indeed the desired equation h_{Γ}^{∗∗}f_{Γ} = f′_{Γ}h_{Γ}^{∗∗}. In particular we see that, if e is X-connected, then h_{Γ}^{∗∗}(e) can be assumed to be contained in Γ_{G′}, while in the non-X-connected case e is mapped to an initial segment of the eigenray R_{h^{∗∗}(v′)}. (The latter may be false for the X-connected extra vertices v′, as there migth be more than one eigenray starting at v′, and the one picked accidentally for h^{∗∗}(e) might be different from the one picked accidentally by the extra edge at G′ with endpoint hf^{t}ω(P).)

This shows that, if we ensure, that in the X-connected case the extra edge has length 0, and in the non-X-connected case, through iterative application of Remark 3.5 in Part I [17] that e is longer than the extra edge e′ with h^{∗∗}(v′) as terminal vertex (both measured in their respective PF-length), we can directly determine the existence of a map h^{∗∗} as desired, modulo further checks in the vertex spaces, by considering the initial segments of the appropriate length of the eigenrays of G′ (with extra edges): As the period of the extra vertices is bounded by the given fixed point pattern, there are only finitely many eigenrays to check, and their initial segments of given finite length in Γ_{G′} are easy to compute from the given map f′ (or more precisely, from f′_{Γ}). There is at most one extension of h_{Γ} to the extra edge e which gives the desired commutative diagram, and if none of the finitely many candidates does, then h cannot be extended such that f′^{t′}ω′H_{Ω}(P) = hf^{t}ω(P) for suitable t, t′ ≥ 0 and hf = f′h up to homotopy relative to v′.

If for every extra vertex P of G an extension of h_{Γ} as above can be found, we proceed as in the proof of Theorem 5.1 in the previous section and fold the extra edges of G over the edges and the vertex spaces of G to get a graph isomorphism h_{Γ} on all of Γ_{G}, including the extra edges. Of course, the extra edges give rise to new of edges in the associated fixed point pattern ω_{f} and ω_{f′}.

It remains to check if for some integers t, t′ ≥ 0 the maps f′^{t′}ω′H_{Ω} and hf^{t}ω are homotopic relative to the images of the vertices of Ω. This can be done again (modulo further checks in the vertex spaces) by iterating and comparing the image paths of the edges of Ω, as legal paths of non-zero PF-length grow strictly longer under itertion of f and f′. If the train track part of the corresponding image paths agree for all edges of Ω, then, for each time these image paths pass through a vertex space, we obtain another new edge which has to be added to both associated fixed point pattern ω_{f} and ω_{f′}. We call the new fixed point pattern obtained by these and the above extensions the associated extended fixed point pattern, and note that, for any given f, f′, ω and ω′ as above the described procedure is algorithmic and shows either that no conjugating map h as desired exists, or else it produces such an associated extended fixed point pattern.

We summarize our arguments:

Proposition 6.5. Let f : G → G and f′ : G′ → G′ be relative pseudo-Anosov train track maps, and let h_{Γ} : Γ_{G} → Γ_{G′} be a graph isomorpism which satisfies h_{Γ}f_{Γ} = f′_{Γ}h_{Γ} (directly, not up to homotopy). Assume that extra vertices, extra edges and extra Nielsen faces have been added to G and G′, to admit fixed point pattern ω : Ω → G and ω′ : Ω′ → G′ without non-periodic vertices, and assume that H_{Ω} : Ω → Ω′ is a graph isomorphism.

Then

(a) there exist a map of pairs h : G → G′ which induces the isometry h_{Γ} on the train track parts (without the extra edges) and induces an isomorphism h_{∗} : π_{1}G → π_{1}G′ with hf = f′h up to homotopy relative the extra vertices, as well as integers t, t′ ≥ 0, such that f′^{t′}ω′H_{Ω} = hf^{t}ω up to homotopy relative to the set of vertices of Ω,

if and only if (b) for each vertex v of Γ_{G} (including the extra vertices) there exists a map h_{v} : X_{v} → X_{h(v)} which satisfies the properties (a), (b) and (c) of Proposition 6.3 for the associated extended fixed point pattern. ⊔ ⊓

Remark 6.6. In the last proposition we have suppressed a particular case which we will consider apart: If all edges of a fixed point pattern ω : Ω → G are mapped by ω into the relative part X of f : G → G, then we gain, in the next step of our recursion procedure, an extra parameter, as the given fixed point pattern ω : Ω → X and the (non-extended !) associated fixed point pattern ω_{f} : Ω_{f} → X can be varied independently within their induced f_{v}-orbits (for each vertex v of Γ_{G}). Hence, in the algorithm in section 9, rather than working with single fixed point pattern as given by Definition 6.1, we have to apply the analogous methods to multiple fixed point pattern ω = {ω_{k}}, which consist of finite families of single fixed point pattern ω_{k} with distinct associated f-orbits. In particular we want to emphasize that, in analogy to the above explained particular case, the associated extended fixed point pattern defined by a multiple fixed point pattern ω = {ω_{k}} is again a multiple fixed point pattern, which consists of one orbit for each ω_{k} with edges mapped to X only, and of the the associated fixed point pattern ω_{f} extended as explained above, but only by all of the remaining ω_{k′}.

Notice in particular that with these definitions Proposition 6.5 stays valid for multiple fixed point pattern ω and ω′ instead of single ones, with the obvious modifications.

We finish this section by stating a corrected version of CASE I in the proof of Proposition 3.12 of Part I [17]:

CASE 1: G−X consists precisely of one f-orbit of periodic edges {e_{1}, e_{2}, …, e_{m}} modulo X.

We distinguish two subcases:

(1) 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_{∗}.

(2) If relative to X′ the given edge e_{i} of G − X does not have a periodic orbit, say f(e_{i}) = γ_{i}e_{i+1}γ′_{i}, we first subdivide e_{i} f-equivariantly at a periodic point, so that, up to inverting the orientation of e_{i}, we only need to consider the case where γ′_{i} is trivial. We then apply Remark 3.5 and property (3) of Definition 3.6 of Part I [17] to ensure that the image γ_{i}e_{i+1} of the edge e_{i} is legal relative to X′, except that there might be an illegal turn between γ_{i} and e_{i+1}. To avoid this we consider the path γ = f^{2}(γ_{i−1})f(γ_{i})γ_{i+1} and iterate f until for some t ≥ 0 guaranteed by property (3) of Definition 3.6 of Part I [17] the path f^{t}(γ) reduces to a legal path. We now have to consider again two subcases:

(a) The image of of the middle segment f(γ_{i}) of γ is completely canceled (up to possibly a subpath in the relative part) when one reduces f^{t}(γ). In this case there is a point x on f^{t+1}(γ_{i}) which is fixed by f (or mapped by f into the same component of the relative part in which it is contained). We then apply again Remark 3.5 but, in addition, use the backtracking path in the above reduction to homotope the point in G′, where after (t + 1)-fold iterating f the edge e_{i} will have its initial vertex glued to G′, onto the point x. The same is done equivariantly on all other initial vertices of the edges e_{i′} in the same f-orbit. It follows that e_{i} becomes periodic relative to X′, so that the above subcase (1) applies.

(b) If in the reduction of f^{t}(γ) the image of of the middle segment f(γ_{i}) of γ is not canceled completely, and if the left-over subpath of f^{t+1}(γ_{i}) after this reduction is not completely contained in the relative part, we proceed similarly: We also apply Remark 3.5 and, in addition, use the backtracking path defined by this reduction to homotope the point in G′, where after (t + 1)-fold iterating f the edge e_{i} will have its initial vertex glued to G′, onto the legal path [f^{t}(γ)] and adjust the path γ_{i} accordingly. The analogue is done f-equivariantly to all other edges e_{i′} in the same orbit. This eliminates to above described illigal turn in f(e_{i}) and thus gives a partial train track map f_{∗} : G_{∗} → G_{∗} relative to X_{∗} = X′ with the desired properties.

7. Polynomial growth automorphisms

Let f : Γ → Γ be a relative train track map as in [3], and assume f is of polynomial growth, i.e. all irreducible diagonal blocks of the transition matrix M(f) are periodic. We first rise f to a sufficiently high power f^{k} so that all diagonal blocks are actually the identity matrix. The resulting map is a finite product of maps of the following type:

The map d : Γ → Γ fixes pointwise all edges but one, say e, and maps e to a path γ′eγ where γ and γ′ are loops which do not meet e. We subdivide e once, so that it suffices to consider the case where γ′ is trivial. We consider the graph of groups decomposition (using the same notation as in [5]) of F_{n} defined by contracting every connected component Γ_{0} of Γ − int(e) to a single vertex with vertex group π_{1}Γ_{0}, while keeping the edge e, with trivial edge group associated to it. We now subdivide e, by introducing a new vertex v, into two subedges, e = e′e′′. We define the vertex group G_{v} of v as well as the edge group G_{e′′} of e′′ to be isomorphic to Z Z , while G_{e′} is trivial. The edge injection f_{}_{ē′′} : G_{e′′} → G_{v} is an isomorphism, and the edge injection f_{e′′} : G_{e′′} → G_{τ(e)} (where τ(e) denotes the terminal vertex of the oriented edge e) maps a generator z = z_{e′′} of G_{e′′} to the element X = X_{e′′} in G_{e′′} which is determined by the loop γ. The element z (or its conjugacy class in F_{n}) is called in [5] the twistor of d. Clearly the new graph of groups has fundamental group canonically isomorphic to the old one, and this remains true if we furthermore contract the edge e′, thus obtaining a new vertex group G_{τ(ē′′)} = G_{τ(ē′)} ∗ G_{τ(e′)} (where ē denotes the edge e with reversed orientation). It is an easy exercise to show that the (single) Dehn twist D given by this graph of groups and by the twistor (compare [5]) is conjugate to the automorphism induced by the original map d : Γ → Γ, where the conjugating group isomorphism is given effectively by the above construction.

For the sequel we need to keep track of some extra data which do only exist if the given automorphismus f_{∗} is not linear growing: We record the splitting of the vertex group G_{τ(ē′′)} = G_{τ(ē′)} ∗ G_{τ(e′)}, or, equivalently, we record the free factor G_{τ(ē′)} which together with the cyclic group G_{τ(e′)} generates G_{τ(ē′′)}. In case where the automorphism is linearily growing this factor G_{τ(ē′)} is not distinguished from any other free factor of G_{τ(ē′′)} complementary to G_{τ(e′)}. We will see below that this is different for the case of higher polynomial growth, where this special complementary factor is indeed well distinguished among all complementary factors of the cyclic factor generated by the twistor (but only at the initial vertex of e′′ in the above construction, not at the terminal vertex !).

This shows that the above power f^{k} of the given relative train track map f : Γ → Γ (of polynomial growth) is a product of automorphisms as just described: f^{k} = d_{q}d_{q−1} … d_{1}. This product has a special property, called semi-commuting in [15]: The conjugacy class in F_{n} of the twistor z_{s} of d_{s}, is left invariant by the action of any of the d_{t} with t ≥ s. Notice here that two Dehn twists do actually commute if and only if they semi-commute in both directions.

It follows from the above definitions that, in general, if t ≥ s then z_{t} will not be kept invariant (up to conjugacy in F_{n}) by d_{s}. However, it follows directly from the relative train track property that the special complementary factor of d_{t} is invariant (up to conjugacy) under the action of d_{s}.

We now permute some of the d_{i} which commute and group them together into subproducts D_{j} to achieve the following normalization: All factors d_{i}, d_{i′} in any one subproduct D_{j} do commute pairwise, while for each factor d_{i} in the (j + 1)-st subproduct D_{j+1} there is a factor d_{k} in D_{j} which only semi-commutes with d_{i} but does not commute. It is easy to see that each of these subproduct D_{j} of pairwise commuting single Dehn twists describes precisely a multiple Dehn twist as introduced in [5].

We use the algorithm described in [5] to transform each such multiple Dehn twist D_{j} into its canonical form, by making it efficient (see [5]). It is not hard to see that in the process of doing this we can carry over the above introduced extra data: This gives is a prefered orientation on every edge e of the graph-of-groups G_{j} with F_{n} = π_{1}G_{j} associated the efficient Dehn twist D_{j} (compare [5]), such that for any vertex v the corresponding vertex group G_{v} has a canonical splitting as free product of cyclic groups, each corresponding to the edge group of an outward oriented edge adjacent to v, and a special complementary factor G_{v}^{c}, obtained as above from the special complementary factors of the initial decomposition of the given map f^{k}. In particular, each G_{v}^{c} is kept invariant (up to conjugacy in F_{n}) by the action of any D_{h} with h < j. We use this observation to define, for j ≥ 2, a new graph-of-groups G′_{j} with fundamental group F_{n} but with trivial edge groups, which is obtained from G_{j} by undoing for each edge of G_{j} the process described at the beginning of this section. In particular, G_{j} and G′_{j} are based on the same graph, and for any vertex v the new vertex group G′_{v} is given by G′_{v} = G_{v}^{c}. We formally define G′_{1} = G_{1}.

It follows directly from our previous arguments that the decomposition F_{n} = π_{1}G′_{j} is invariant under any D_{h} with h ≤ j. In particular, every conjugacy class in a vertex group of G′_{j} grows (measured by the reduced cyclic word length with respect to any fixed basis) polynomially of degree ≤ j − 1, as the semi-commuting composition of k linear growing automorphisms cannot grow faster than a polynomial of degree k: This follows directly by induction over k. On the other hand, every twistor of D_{j}, for j ≥ 2, is mapped by D_{j−1} into a new conjugacy class, different from its preimage: Otherwise the corresponding single Dehn twist would not belong to the factor D_{j} but to D_{j−1} or to one of the preceding factors. Hence the length of every twistor of D_{j} grows linearily under iteration of D_{j−1} (compare [5]); this shows (again by induction over j) that each twistor of D_{j} has polynomial growth which is precisely of degree j − 1, and every conjugacy class which passes over at least one edge in G_{j} (i.e. it is not represented by an element which is contained in a vertex group) must have polynomial growth of degree equal to j. As these data are not influenced by our original passage to powers of f, we obtain the following Structure Theorem for polynomial growth automorphisms, quoted in the Introduction in Part I [17] as Theorem II:

Theorem 7.1. For every polynomially growing, non-periodic automorphism α of F_{n}, given by a relative train track representative, we can algorithmically derive a 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} that have polynomial growth of non-maximal degree, under iteration of α. If the maximal growth is linear, then all edge groups of G are cyclic, while in the case of quadratic or higher growth, they are trivial.

Proof. For linearily growing automorphisms α this is a direct consequence of the results of [5]. It remains to show that, in the case of quadratic or higher growth, the edges in the graph of groups decomposition G are well defined by the vertex groups and by the outer automorphism α̂ = f_{∗} of F_{n}. We first replace f by a power which fixes every edge of G. Now every edge e of G, or more precisely, any lift ẽ to the corresponding Bass-Serre tree T, defines a representative αẽ ∈ Aut(F_{n}) of α̂ which is has the property that its corresponding lift f̃ fixes ẽ. As the stabilizer of ẽ is trivial (since edge groups of G are trivial), the automorphism αẽ is uniquely determined by ẽ. It fixes the subgroups U and V of F_{n} which are the stabilizers of the vertices of T that are endpoints of ẽ. Hence the subgroups U and V of F_{n} belong to the family all of subgroups determined by the vertex groups of G (which are characterized above by the property that they are maximal subgroups of F_{n} which contain only conjugacy classes of non-maximal degree polynomial growth). We observe furthermore that, with respect to the prefered orientation on e, the automorphism αẽ does not fix any element of the terminal vertex stabilizer (say V), except for the elements of the cyclic subgroup generated by the twistor Xẽ of ẽ. If we now consider the selfmap of the subgroup < U, V > given by first conjugating V with X−1 ; ẽ and then applying αẽ, we obtain an automorphism α′ :< U, V > → < U, V > which grows polynomially of degree strictly smaller than d, the degree of α̂. This characterizes the edge ẽ, if both, U and V are non-trivial. If U is trivial (which can happen, as contrary to the case of efficient Dehn twists, see [5], in the above graph of groups G′_{j} some vertex groups can be trivial), then there is at least one other edge e′ with same initial point as e, and if V′ stabilizes the terminal vertex of e′ and X′ is its twistor, then replacing U by V′ and X^{−1} by X′X^{−1} in the above method characterizes the “double edge” ē′e. ⊔ ⊓

This theorem gives us directly a possibility to decide whether two given polynomially growing automorphisms are conjugate, modulo solving the analogous question for automorphisms of polynomial growth of strictly smaller degree, by comparing the two graph of groups decompositions. Hence there is a precise analogy to the pseudo-Anosov case as described in Theorem 5.1, where the train track part is replaced by the graph Γ_{G} of the graph of groups G. The case of linear growth is treated in the next section. In the (easier) case of quadratic or higher polynomial growth, we can realize the graph of groups in the traditional topological manner, to get an honest graph of spaces (for simplicity also called G) on which α is realized as partial train track map f, as studied in section 3 of Part I [17]. In particular, Proposition 6.3 applies again, and we get an associated fix point pattern, this time with a graph Ω_{f} which only consists of vertices and has no edges.

On the other hand, we may have, from the possible previously done recursion steps, an orbit of fixed a point pattern given together with the automorphisms, so that we need in fact a full analogue of Proposition 6.5. The situation here, however, is much simpler, as the map f_{Γ}, induced by f on the train track part of G, is periodic.

The first step, as in section 6, is the attachment of extra edges to G, in order to be able to transfer a fixed point pattern to get ω : Ω → G. As in section 6 we attach for every vertex of Ω a single extra edge e at its initial vertex v to G, and define its image f(e) to be a path γe, where γ connects f(v) to v.

Now, let f′ : G′ → G′ be a second partial train track map which is the realization of the canonical invariant graph-of-groups for a polynomially growing automorphism as in the above Theorem 7.1. Assume that h_{Γ} : Γ_{G} → Γ_{G′} is a graph isomorphism with h_{Γ}f_{Γ} = f′_{Γ}h_{Γ} (directly, not up to homotopy), and let e and e′ be extra edges attached to G and G′ respectively, with f(e) = γe and f′(e′) = γ′e′. Let P be a vertex of Ω which is mapped by ω to the terminal vertex of e, and let P′ be the image of P under the graph isomorphism H_{Ω} : Ω → Ω′ as in Proposition 6.5, which is mapped by ω′ to the terminal vertex of e′. We need to study the question under which conditions there exists a map h as in part (a) of Proposition 6.5.

We first consider the case where f_{Γ} and f′_{Γ} are the identity maps. One verifies easily that then a necessary condition for the existence of h is that the loops γ and γ′ define edge paths γ_{Γ} and γ′_{Γ} in Γ_{G} and Γ_{G′} with h_{Γ}(γ_{Γ}) = γ′_{Γ} up to cyclic permutation and reduction. This necessary condition is also sufficient, modulo properties (a), (b) and (c) of Proposition 6.3 for the associated extended fixed point pattern which in this case are canonically defined by the connecting paths in X or X′ between the edges of G or G′ which are crossed over by the loops γ and γ′. The analogy to section 6 is very close, so that we can leave all further details to the reader. We give, however, the following hint: If γ = γ′γ̂γ′′, with γ′_{Γ} inverse to γ′′_{Γ} in Γ_{G}, then a cyclic reduction of γ_{Γ} which cancels γ′_{Γ} and γ′′_{Γ} is possible if and only if f(γ′′) is inverse to γ′ in G (and not just in Γ_{G} !).

If the maps f_{Γ} and f′_{Γ} are periodic of period p ≥ 1 rather than the identity, then the concatenation of the paths γ, f^{−1}(γ), f^{−2}(γ), …, f^{−p+1}(γ) defines a loop γ̂, and the analogous necessary and sufficient conditions as above for γ and γ′ hold now for γ̂ and the similarly defined γ̂′.

After the extra edges have been attached to G and G′, we can consider the edges E of Ω and their ω-images in G, as well as H_{Ω}(E) and ω′(H_{Ω}(E)) ⊂ G′. As f_{Γ} is periodic, we can check directly, for all t ≥ 0 smaller than the period of f and f′, whether the paths hf^{t}ω(E) and f′^{t′}ω′H_{Ω}(E) are homotopic relative their endpoints, again modulo the connecting subpaths in the vertex spaces, i.e. the edges of the associated extended fixed point pattern. This shows that, indeed, the full analogue of Proposition 6.5 holds in the presently considered non-linear polynomial case.

8. Automorphisms of linear growth

We now assume that α is a multiple Dehn twist or the root of such. Then it has been shown in [5] and [11] that there is a canonical graph of groups decomposition F_{n} = π_{1}G with all edge groups of G infinitely cyclic and a graph-of-groups automorphism f : G → G representing α. As in section 7 we do not distinguish notationally between the graph of groups G and a topological realization of it in the usual way, or between the graph-of-groups automorphism f and a selfmap of this topological realization which induces this automorphism. Any conjugacy between two such automorphisms, f and f′, is induced by a graph-of-groups isomorphism h : G → G′ which in particular induces a graph isomorphism h_{Γ} : Γ_{G} → Γ_{G′}. As there are only finitely many such h_{Γ}, for given graph of groups G and G′, this reduces the conjugacy problem in this case to the question of whether there exists, for every vertex v of G, a groups isomorphism h_{v} : G_{v} → G_{h(v)} between the corresponding vertex groups, such that for the induced maps f_{v} and f′_{h(v)} on the vertex groups one has

(1) f′_{h(v)}h_{v} = h_{f(v)}f_{v} for all vertices v, and

(2) h_{v}f_{e}(z_{e}) is conjugate in G_{h(v)} to f_{h(e)}z_{h(e)}, for all edges e with terminal

endpoint v.

(Attention: For consistency with the notation of [5] we denote the edge injection for an edge e of the graph of groups G by f_{e}. Of course, this has nothing to do with the given graph-of-groups automorphism f.)

This question has been solved algorithmically in [11], extending the work of Whitehead.

The only remaining problem is now to extend the above to the question, whether there exists such an h which in addition to the above properties (a) and (b) carries over the orbit of a fixed point pattern ω : Ω → G for G to a corresponding given orbit of a fixed point pattern ω′ : Ω → G′ for G′. To solve this question algorithmically it is sufficient to show that for each orbit of fixed point pattern there are finitely many conjugacy classes in the vertex groups which characterise the orbit: Then the algorithm in [11] will provide the answer to this remaining problem.

We first consider the special case where the given fixed point pattern consists of a single vertex P only. As in the non-linear polynomial case we attach an extra edge e_{P} with f-fixed terminal vertex ω(P), and the Nielsen fixed point class of ω(P) in G is given (up to the usual extension of the associated fixed point pattern for the vertex groups of G, see below) through f(e_{P}) = γe_{P} by a conjugacy class of based loops [γ]. The latter can be characterized by a reduced word W = w_{0}t_{1}w_{1} … w_{q−1}t_{q}w_{q} as in [5], and this word is uniquely determined by [γ] up to cyclic permutation. Here the w_{j} ∈ G_{τ(e_{j})} = G_{τ(ē_{j+1})} are uniquely determined by the element W ∈ π_{1}G up to multiplying from the left with powers of X_{j}, the image of the twistor z_{e_{j}} of the edge e_{j} in G_{τ(e_{j})}, and from the right with powers of the analogously defined X_{j+1} (called below “intermediate twistor powers”).

The first of the following two lemmas is elementarily proved by combinatorial methods, while the second is a direct consequence of the first:

Lemma 8.1. Given X, Y, w ∈ F_{n} with 1 ≠ X^{p} ≠ wY^{q}w^{−1} ≠ 1 for all p, q ≥ 1, then the 6-tuple of conjugacy classes of

X, Y, XwY w^{−1}, X^{−1}wY w^{−1}, XwY^{−1}w^{−1}, X^{−1}wY^{−1}w^{−1}

determines the element w up to multiplication with powers of X from the left and of Y from the right, and up to “simultaneous conjugation” of type (X, Y, w) ↦ (uXu^{−1}, vY v^{−1}, uwv^{−1}). ⊔ ⊓

Lemma 8.2. Given X, Y, w ∈ F_{n}, then every automorphism α ∈ Aut(F_{n}) which stabilizes each of the six conjugacy classes X, Y, XwY w^{−1}, X^{−1}wY w^{−1}, XwY^{−1}w^{−1}, X^{−1}wY^{−1}w^{−1} maps (X, Y, w) to (uXu^{−1}, vY v^{−1}, uwv^{−1}) for some u, v ∈ F_{n} and s, t ∈ Z Z . ⊔ ⊓

In [11], before Theorem 1.4, it is shown that the stabilizer in Out(F_{n}) of a given finite subgroup of Out(F_{n}), and of a finite family of conjugacy classes in F_{n}, is finitely generated, and how to derive a finite system of generators algorithmically. We apply this, for each vertex v of G′, to the finite subgroup of Out(G_{v}) generated by the smallest power of f′ which fixes v, and to all conjugacy classes of twistors at this vertex, and to the conjugacy classes derived from Lemma 8.2 for each w_{j} as derived above for the fixed point pattern. The resulting set of possible s and t, which determine the possible variations of w_{j} as described above by means of changing h by an element of the this stabilizer, forms a subgroup U(w_{j}) of Z Z ⊕ Z Z = {(s, t) : s, t ∈ Z Z }.

We can then compare the two fixed point pattern ω and ω′, first using Lemma 8.1 and [11] to find a necessary condition (in terms of a large but finite family of conjugacy classes) for h to map ω to ω′. If this necessary condition is satisfied, we iterate the given roots of Dehn twists so that, using the identifications h_{v} just obtaind from Lemma 8.1 and [11], we obtain precisely the same reduced cyclic words for pairs of corresponding conjugacy classes, except that the exponents at the intermediate twistors may be different. But now it is a finite matching game (or more precisely, the solution of a system of linear diophantic equations) to apply the variations of these twistor exponents as derived above from [11] and Lemma 8.2 and to play them against possible further iterations of the Dehn twists, which just add a constant tupel to the set of twist exponents. This gives a sufficient and necessary test for the existence of a conjugator h as desired.

If the fixed point pattern is more complicated, we get, in direct analogy to the situation treated in section 7, for each vertex P of Ω an extra edge e_{P} attached to G with f(e_{P}) = γ_{P} e_{P} that determines a loop γ̂_{P}, and for each edge E of Ω joining P to P′ a path ω(E) from the terminal endpoint of e_{P} to that of e_{P′}. We proceed just as in section 7, except that there the connecting paths between the edges of the paths γ̂_{P} and ω(E) gave rise to edges in the associated extended fixed point pattern, while here we proceed as shown above to encode them into finitely many conjugacy classes in the vertex groups of G (and similarly of G′). Hence the above two lemmas together with the algorithm in [11] gives a solution to the conjugacy problem for automorphisms of linear growth with fixed point pattern.

9. The algorithm

In this section we describe how the methods presented in the previous sections and in Part I [17] can be used to solve the conjugady problem in Aut(F_{n}) and in Out(F_{n}). To do this we solve the following more general problem:

Generalized conjugacy problem 9.1. Given two finite possibly non-connected graphs Γ, Γ′ without contractible components, two homotopy equivalences f : Γ → Γ, f′ : Γ′ → Γ′, a bijection H between the connected components of Γ and Γ′, two (possibly multiple) fixed point pattern ω : Ω → Γ, ω′ : Ω → Γ′ without nonperiodic vertices, and a graph isomorphisms H_{Ω} : Ω → Ω′. Does there exist a map h : Γ → Γ′ which realizes H and satisfies:

(a) h induces a π_{1}-isomorphism h_{∗} on every component of Γ,

(b) hf = f′h up to homotopy relative to the ω-images of the vertices of Ω, and (c) hω = ω′H_{Ω} up to homotopy relative to the vertices of Ω.

If Γ and Γ′ are connected, and if both, Ω and Ω′, are empty, then the above is equivalent to the conjugacy problem for the outer automorphisms induced by f and f′ on the free group F_{n}, where n = 1 − χ(Γ) = 1 − χ(Γ′). If Γ and Γ′ are connected and Ω consists only of a single point P with fixed points as images in Γ and in Γ′, then the above is equivalent to the conjugacy problem for the (non-outer) automorphisms induced by f on π_{1}(Γ, ω(P)) and by f′ on π_{1}(Γ′, ω′H_{Ω}(P)).

To solve the generalized conjugacy problem we proceed inductively over the total rank of the fundamental groups of the components of Γ and Γ′. For any connected component Γ_{0} of Γ we consider the smallest positive power f^{t} of f which fixes this component. We now proceed, see section 4 of Part I [17], to find a relative train track map g : Γ_{1} → Γ_{1} as in [3] which is conjugate to f^{t} : Γ_{0} → Γ_{0}. We replace the other components in the f-orbit of Γ_{0} by identical copies of Γ_{1}, and replace f by a map which realizes the canonical identification map for the first t − 1 iterations of f, and by g for the t-th iteration. The analogous replacement is done with all other f-orbits of connected components of Γ, and similarly with f′.

I. Assume first that there is at least one component where the relative train track map g : Γ → Γ is exponentially growing. For this component we proceed analogously as above, to replace the relative train track map by a partial train track map with Nielsen faces, relative to the polynomially growing part, as in Theorem 4.1 of Part I [17]. We then determine the finite family of relative pseudo-Anosov representatives f_{j} : G_{j} → G_{j} from this partial train track map, as given by Theorem 4.5 of Part I [17]. The same is done with the image f-orbit under the given bijection H to get a finite family of relative pseudo-Anosov train track maps f′_{j′} : G_{j′} → G_{j′}.

We then pick one of the f_{j} and consider one-after-the-other each of the f′_{j′}. For each of the f′_{j′} the algorithm in section 5 provides us with relative conjugating maps h_{Γ} between f_{j} and f′_{j′} as in Proposition 5.1, one for each of the finitely many f′_{j′}-orbits of relative maps h_{Γ} which can possibly be induced by a conjugator h as asked for in the Generalized conjugacy problem 9.1. For each such relative conjugating map h_{Γ} the algorithm in section 5 also determines an induced family of associated fixed point pattern on the vertex spaces. Each of these relative conjugating maps h_{Γ}, together with the induced maps on the vertex spaces and the associated fixed point pattern, will be recorded in a finite list.

For each of the relative conjugating maps h_{Γ} in this finite list we now apply the method described in section 6, to transfer the given fixed point pattern ω from Γ to the G_{j} (and similarly for ω′), and to decide whether the relative conjugating map conjugates the orbits of corresponding fixed point pattern. The algorithm in section 6 either yields a negative answer, in which case the relative conjugating map is deleted from our list, or else it gives for each vertex space (and its image under the relative conjugating map) a new orbit of an associated extended fixed point pattern, which we add as additional information to the above list. We now simplify each associated extended fixed point pattern as explained in section 6 after Remark 6.4, to eliminate the contractible components among the vertex spaces, and also the non-periodic vertices from the fixed point pattern. Hence each member of our finite list gives a new generalized conjugacy problem, where the total rank of the fundamantal groups of the connected components has decreased strictly. This enables us to apply the induction hypothesis and Proposition 6.5 to solve the generalized conjugacy problem in this case.

II. Next we consider the case of a connected component where the relative train track map g : Γ → Γ is of non-linear polynomial growth. We proceed analogously as in case I, but this time using the methods of section 7. Again this gives us a new generalized conjugacy problem with total rank of the fundamental groups decreased strictly, so we can again use the inductive hypothesis.

III. It remains the case where every component has linear growth. In this case section 8 gives a direct solution of the generalized conjugacy problem.

This proves:

Theorem 9.2. The above algorithm constitutes a complete solution of the Generalized conjugacy problem 9.1 and hence of the conjugacy problems in Aut(F_{n}) and in Out(F_{n}). ⊔ ⊓

Remark 9.3. As a corollary to the above algorithm one also obtains algorithms to solve the following problems:

(1) for any α ∈ Aut(F_{n}) determine a finite generating system of

F ix(α) = {w ∈ F_{n} : α(w) = w},

and

(2) for any space X with π_{1}X ˜=F_{n} and any map f : X → X which induces an automorphism f_{∗} = α̂ ∈ Out(F_{n}), and for any two finite families of fixed points x_{i} = f(x_{i}), y_{i} = f(y_{i}) ∈ X, decide whether for all i the points x_{i} and y_{i} lie in the same Nielsen fixed point class of f.

The solution to the first problem follows from the fact that the vertex groups of the last level of the above recursive method, the linear growth subautomorphisms, consist precisely of all conjugacy classes on which α acts periodically, combined with classical methods for finite order automorphisms. Earlier (partial) solutions were given by work of E.Turner [23] and by O.Bogopolski’s graduate student ???? [4].

The second problem is solved by the above solution of the generalized conjugacy problem for an appropriate fixed point pattern representing the given fiexed points. Work on related questions has been done recently by John Guaschi (Toulouse).

We finish this section with the proof of Theorem III as stated in the Introduction in [17]. Let us first specify the notation used there: A relative pseudo-Anosov stratum of an automorphism α̂ ∈ Out(F_{n}) is given by the train track part of any relative pseudo-Anosov train track map which occurs in the recursive procedure described in I. above to determine the conjugacy class of α̂. If α̂ is represented by an expanding partial train track map f : G → G relative to polynomially growing induced automorphisms on the vertex groups as in Theorem 4.1 of Part I [17], then we can define such a relative pseudo-Anosov stratum of α̂ equivalently to be the set of edges of G which are given by the train track part of a relative pseudo-Anosov train track map that is defined on any f-invariant sub-train-track of G through the choices explained before Theorem 4.5 of Part I [17]. In particular, it follows that the relative pseudo-Anosov strata of α̂ are in 1:1 correspondence with the irreducible diagonal blocks of the matrix M(f). The partial order on them is given by the natural inclusion, i.e. the inclusion defined by associating to each diagonal block matrix of M(f) the smallest subspace of G which is f-invariant and contains all edges corresponding to the diagonal block matrix. Of course, this partial order is then precisely reflected by the non-zero off diagonal blocks of M(f).

Proof of Theorem III. One first notices that, if no conjugacy class in F_{n} has finite orbit under the given outer automorphism α̂, then in the last step of our algorithmic decomposition there can be no root of a non-trivial Dehn twist, as in [5] it is shown that an efficient representative of any non-trivial Dehn twist D has all vertex groups (which are fixed up to conjugacy by D) of rank at least 2.

But this implies that there can also be no conjugacy class of higher degree polyomial growth, as by Proposition 7.1 this would imply the existence of linearily growing and hence the existence on non-trivial periodic conjugacy classes.

Hence we deduce that in any partial train track representative f : G → G of α as in Proposition 4.1 of Part I [17] all vertex spaces are contractible, so that one obtains a complete recursive analysis of α̂ by analysing succesively the relative pseudo-Anosov strata of G. But as a direct consequence of Theorem 5.1 one notices that, up to powers of the automorphism, the centralizer of any relative pseudo-Anosov stratum is finite.

This reduced the problem of determining the centralizer of any such automorphism to the question whether different strata allow an independent iteration of the induced automorphism or not. The answer to this question is given directly by the transition matrix M(f), in terms of the non-zero entries outside the diagonal blocks, which defines the partial order on the strata as explained above. It is easy to see that the deduced information translates precisely into the statement given in Theorem III of the Introduction of [17]. ⊔ ⊓

The arguments from the last proof apply just as well to the polynomial growth strata, i.e. the train track part of any f-invariant sub-train-track of a topological realization f : G → G of a graph-of-groups isomorphism as given by Proposition 7.1. This can be used to prove a more general result, concerning the centralizer Cen(α̂) of an arbitrary outer automorphism α̂ in Out(F_{n}): We consider a generalized partial train track representative f : Ĝ → Ĝ of α̂, with relative pseudo-Anosov strata in the top part and polynomial growth strata in the bottom (obtained from a combination of Theorem 4.1 of Part I [17] with Proposition 7.1). The same arguments as in the last proof show that the group Cen(α̂) has a finite index subgroup which decomposes as direct sum of a free abelian subgroup A(α̂), with basis in 1:1 relation to the connected components of the p.o. set of pseudo-Anosov or polynomial growth strata of Ĝ, and of the stabilizers S_{v} of the finite cyclic subgroup induced by f and of the associated finite family of conjugacy classes, for each vertex v of the set V (α̂) of vertex spaces of the lowest stratum of Ĝ, the linear growth one, as exhibited here in section 8:

Theorem 9.4. For all α̂ ∈ Out(F_{n}) the index

[Cen(α̂) : A(α̂) ⊕ ⨁_{v∈V (α̂)} S_{v}]

is finite. ⊔ ⊓

Remark 9.5. This, in turn, explains the structure of any virtually abelian subgroup A of Out(F_{n}), as any element â of a finite index free abelian subgroup A_{0} ⊂ A must lie in the stabilizer of any other such element, and vice versa. We deduce that there must be a generalized partial train track Ĝ as above such that every â ∈ A is represented (with respect to a fixed identification F_{n} = π_{1}G) by a partial train track map fα̂ : G → G. A canonical basis of A_{0} is given by maximal such maps fα̂, i.e. maps which fix the free homotopy classes of all loops in a maximal (among all non-trivial α̂ ∈ A_{0}) union of strata of G. Minimal elements α̂ ∈ A_{0}, on the other hand, satisfy A_{0} ⊂ A(α̂), which leads us to suspect a relationship between this observation and some recently announced results of M.Feighn and M.Handel [7].

We finally note that Theorem 9.4 as well as Remark 9.5 extend directly to give analogous results for Aut(F_{n}) rather than Out(F_{n}), by simply adding a fixed point pattern consisting of a single point to the above representative f : Ĝ → Ĝ of α̂.

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. Bogopolski’s student, ..., Master’s thesis Novosibirsk (2000).

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

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

7. M. Feighn, M. Handel, Abstracts to Haifa Conference, June 2000.

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

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

10. S. Kristic, Actions of finite groups of graphs and related automorphisms of free groups, J. Algebra 124 (1989), 119–138.

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

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

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

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

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

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

17. M. Lustig, Structure and conjugacy for automorphisms of free groups I, MPI-Bonn preprint series 241 (2000), http://www.mpim-bonn.mpg.de/preprints.

18. M. Lustig, private notes.

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

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

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

22. R.Skora, unpublished preprint.

23. E.Turner, ???.

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