Dynamics of free group automorphisms

Peter Brinkmann

August 22, 2003

Abstract

We present a coarse convexity result for the dynamics of automorphisms of finitely generated free groups. As an application, we obtain an algorithm that detects whether two elements of the free group are contained in the same orbit of a given automorphism.

Introduction

The following theorem is the main result of this paper.

Theorem 0.1. Let ϕ: F → F be an automorphism of a finitely generated free group. Then there exists a constant K ≥ 1 such that for any pair of exponents N, i satisfying 0 ≤ i ≤ N, the following two statements hold:

1. If w is a cyclic word in G, then

||ϕ_{#}^{i}(w)|| ≤ K (||w|| + ||ϕ_{#}^{N}(w)||) ,

where ||w|| is the length of the cyclic reduction of w with respect to some word metric on F.

2. If w is a word in F, then

|ϕ_{#}^{i}(w)| ≤ K (|w| + |ϕ^{N}(w)|) ,

where |w| is the length of w.

The constant K is effectively computable.

Note that the statement of the theorem does not depend on the choice of generators of F. The intuitive meaning of the theorem is that the map i ↦ |ϕ^{i}(w)| is coarsely convex for all words w ∈ F. Klaus Johannson informed me that a similar result is a folk theorem in the case of surface homeomorphisms. Also, while free-by-cyclic groups are not, in general, CAT(0)- groups [Ger94], Theorem 0.1 suggests that their dynamics mimics that of CAT(0)-groups. Moreover, Theorem 0.1 complements the main result of [Bri00], which provides a strong convexity result for atoroidal automorphisms of free groups.

As an application, Theorem 0.1 yields an algorithm that detects automorphic orbits in free groups.

Theorem 0.2. Given two elements u, v ∈ F and an automorphism ϕ: G → G, there exists an effective algorithm that decides whether the ϕ-orbit of u contains (a conjugate of) v.

The results of this paper grew out of joint work with Ilya Kapovich on generalizations of the famous combination theorem of Bestvina and Feighn[BF92, BF96]. I originally set out to prove Theorem 2.1 because it immediately implies that in a free-by-cyclic group

Γ = F ⋊_{ϕ} ℤ = ⟨ x_{1}, …, x_{n}, t | t^{−1}x_{i}t = ϕ(x_{i}) ⟩,

words of the form t^{−k}wt^{k}ϕ^{k}(w^{−1}) satisfy a quadratic isoperimetric inequality. (Note, however, that Theorem 2.1 is much stronger than the mere existence of a quadratic isoperimetric inequality for such words.) Martin Bridson and Daniel Groves have since announced a proof that free-by-cyclic groups satisfy a quadratic isoperimetric inequality, and they have posted a preprint that deals with the case of positive automorphisms [BG]. Natasa Macura previously proved this for automorphisms of polynomial growth [Mac00].

Theorem 0.1 follows from a technical result (Theorem 2.1) that uses the machinery of improved train track maps of Bestvina, Feighn, and Handel [BFH98]. In Section 1, we review the pertinent definitions and results from [BFH98]. Section 2 presents the statement of Theorem 2.1, and it details how Theorem 0.1 and Theorem 0.2 follow from Theorem 2.1. Section 3 and Section 4 provide some more results on train tracks and automorphisms of free groups. Section 5 introduces some notation and terminology and lists a number of examples that illustrate some of the issues and subtleties that need to be addressed in the proof of Theorem 2.1. Section 6 establishes a technical proposition that may be of independent interest. Finally, Section 7 and Section 8 contain the proof of Theorem 2.1.

I would like to express my gratitude to Ilya Kapovich for many helpful discussions, to Mladen Bestvina for patiently answering my questions, to Steve Gersten for encouraging me to write up this result for its own sake, to the University of Osnabrück for their hospitality, and to Swarup Gadde and the University of Melbourne as well as the Max-Planck-Institute of Mathematics for their hospitality and financial support. Klaus Johannson and Richard Weidmann kindly served as a sounding board while I was working on the exposition of this paper.

1 Improved relative train track maps

In this section, we review the theory of train tracks developed in [BH92, BFH98]. We will restrict our attention to the collection of those results that we will use in this paper.

Given an automorphism ϕ ∈ Aut(F), we can find a based homotopy equivalence f: G → G of a finite connected graph G such that π_{1}(G) = F and f induces ϕ. This observation allows us to apply topological techniques to automorphisms of free groups. In many cases, it is convenient to work with outer automorphisms. Topologically, this means that we work with homotopy equivalences rather that based homotopy equivalences.

Oftentimes, a homotopy equivalence f: G → G will respect a filtration of G, i. e., there exist subgraphs G_{0} = ∅ ⊂ G_{1} ⊂ ⋯ ⊂ G_{k} = G such that for each filtration element G_{r}, the restriction of f to G_{r} is a homotopy equivalence of G_{r}. The subgraph H_{r} = \overline{G_{r} \ G_{r−1}} is called the r-th stratum of the filtration. We say that a path ρ has nontrivial intersection with a stratum H_{r} if ρ crosses at least one edge in H_{r}.

If E_{1}, ⋯, E_{m} is the collection of edges in some stratum H_{r}, the transition matrix of H_{r} is the nonnegative m × m-matrix M_{r} whose ij-th entry is the number of times the f-image of E_{j} crosses E_{i}, regardless of orientation. M_{r} is said to be irreducible if for every tuple 1 ≤ i, j ≤ m, there exists some exponent n > 0 such that the ij-th entry of M_{r}^{n} is nonzero. If M_{r} is irreducible, then it has a maximal real eigenvalue λ_{r} ≥ 1 [Gan59]. We call λ_{r} the growth rate of H_{r}.

Given a homotopy equivalence f: G → G, we can always find a filtration of G such that each transition matrix is either a zero matrix or irreducible.

A stratum H_{r} in such a filtration is called zero stratum if M_{r} = 0. H_{r} is called exponentially growing if M_{r} is irreducible with λ_{r} > 1, and it is called polynomially growing if M_{r} is irreducible with λ_{r} = 1.

An unordered pair of edges in G originating from the same vertex is called a turn. A turn is called degenerate if the two edges are equal. We define a map Df: {turns in G} → {turns in G} by sending each edge in a turn to the first edge in its image under f. A turn is called illegal if its image under some iterate of Df is degenerate, legal otherwise.

An edge path ρ = E_{1}E_{2} ⋯ E_{s} is said to contain the turns (E_{i}^{−1}, E_{i+1}) for 1 ≤ i < s. ρ is said to be legal if all its turns are legal, and a path ρ ⊂ G_{r} is r-legal if no illegal turn in α involves an edge in H_{r}.

Let ρ be a path in G. In general, the composition f^{k} ∘ ρ is not an immersion, but there is exactly one immersion that is homotopic to f^{k} ∘ ρ relative endpoints. We denote this immersion by f_{#}^{k}(ρ), and we say that we obtain f_{#}^{k}(ρ) from f^{k} ∘ ρ by tightening. If σ is a circuit in G, then f_{#}^{k}(σ) is the immersed circuit homotopic to f^{k} ∘ σ.

A path ρ is a (periodic) Nielsen path if f_{#}^{k}(ρ) = ρ for some k > 0. In this case, the smallest such k is the period of ρ. A Nielsen path ρ is called indivisible if it cannot be expressed as the concatenation of shorter Nielsen paths. A path ρ is a pre-Nielsen path if f_{#}^{k}(ρ) is Nielsen for some k ≥ 0.

A decomposition of a path ρ = ρ_{1} · ρ_{2} . . . · ρ_{s} into subpaths is called a ksplitting if f_{#}^{k}(ρ) = f_{#}^{k}(ρ_{1}) ⋯ f_{#}^{k}(ρ_{s}), i.e., if there is no cancellation between f_{#}^{k}(ρ_{i}) and f_{#}^{k}(ρ_{i+1}) for 0 ≤ i < s. Such a decomposition is a splitting if it is a k-splitting for all k > 0. We will also use the notion of k-splittings of circuits σ = ρ_{1} · ρ_{2} . . . · ρ_{s}, which requires, in addition, that there be no cancellation between f_{#}^{k}(ρ_{s}) and f_{#}^{k}(ρ_{1}).

The following theorem was proved in [BH92].

Theorem 1.1 ([BH92, Theorem 5.12]). Every outer automorphism O of F is represented by a homotopy equivalence f: G → G such that each exponentially growing stratum H_{r} has the following properties:

1. If E is an edge in H_{r}, then the first and last edges in f(E) are contained in H_{r}.

2. If β is a nontrivial path in G_{r−1} with endpoints in G_{r−1} ∩ H_{r}, then f_{#}(β) is nontrivial.

3. If ρ is an r-legal path, then f_{#}(ρ) is an r-legal path.

We call f a relative train track map.

An outer automorphism O of F is called reducible if it preserves the conjugacy class of a proper free factor of F. O is called irreducible if it is not reducible. If O is irreducible, then it has a relative train track representative f: G → G whose filtration has only one nonempty element H_{1} = G, with irreducible transition matrix. The properties of relative train tracks show that for every edge E of G, the image f^{n}(E) is an immersion for all n > 0. In this case, we call f a train track map (or absolute train track map), and we denote the growth rate of H_{1} = G by λ.

A path ρ in G is said to be of height r if ρ ⊂ G_{r} and ρ ⊄ G_{r−1}. If H_{r} = {E_{r}} is a polynomially growing stratum, then basic paths of height r are of the form E_{r}γ or E_{r}γE_{r}^{−1}, where γ is a path in G_{r−1}. If τ is a closed indivisible Nielsen path in G_{r−1} and f(E_{r}) = E_{r}τ^{l} for some l ∈ ℤ, then paths of the form E_{r}τ^{k} and E_{r}τ^{k}E_{r}^{−1} are exceptional paths of height r. Moreover, if s < r, τ ⊂ G_{s−1}, and f(E_{s}) = E_{s}τ^{m}, then E_{r}τ^{k}E_{s}^{−1} is also a exceptional path of height r.

For our purposes, the properties of relative train track maps are not strong enough, so we will use the notion of improved train track maps constructed in [BFH98]. We only list the properties used in this paper.

Theorem 1.2 ([BFH98, Theorem 5.1.5 and Proposition 5.4.3]). For every outer automorphism O of F, there exists an exponent k > 0 such that O^{k} is represented by a relative train track map f: G → G with the following additional properties:

1. If H_{r} is a zero stratum, then H_{r+1} is an exponentially growing stratum, and the restriction of f to H_{r} is an immersion. H_{r} is a zero stratum if and only if it is the union of the contractible components of G_{r}.

2. If v is a vertex, then f(v) is a fixed vertex. If H_{r} is a polynomially growing stratum and G′ is the collection of noncontractible components of G_{r−1}, then all vertices in H_{r} ∩ G_{r−1} are fixed.

3. If H_{r} is an exponentially growing stratum and ρ is an indivisible Nielsen path of height r that starts and ends at vertices, then ρ is not closed, and at least one endpoint of ρ is not contained in H_{r} ∩G_{r−1}. Moreover, there is at most one indivisible Nielsen path of height r.

4. If H_{r} is a polynomially growing stratum, then H_{r} consists of a single edge E_{r}, and f(E_{r}) = E_{r} · u_{r} for some closed path u_{r} ⊂ G_{r−1} whose base point is fixed by f.

If σ ⊂ G_{r} is a basic path of height r that does not split as a concatenation of two basic paths of height r or as a concatenation of a basic path of height r with a path contained in G_{r−1}, then either f_{#}^{k}(σ) = E_{r} · σ′ for some k ≥ 0, or u_{r} is a Nielsen path and f_{#}^{k}(σ) is an exceptional path of height r for some k ≥ 0.

We call f an improved relative train track map.

Finally, we state a lemma from [BFH98] that simplifies the study of paths intersecting strata of polynomial growth.

Lemma 1.3 ([BFH98, Lemma 4.1.4]). Let f: G → G be an improved train track map with a polynomially growing stratum H_{r}. If ρ is a path in G_{r}, then it splits as a concatenation of basic paths of height r and paths in G_{r−1}.

Remark 1.4. In fact, part 4 of Theorem 1.2 implies that subdividing σ at the initial endpoints of all occurrences of E_{r} and at the terminal endpoints of all occurrences of E_{r}^{−1} yields a splitting of σ into basic paths of height r and paths in G_{r−1}.

Observe that if H_{r} = {E_{r}} is a polynomially growing stratum, then f_{#}^{k}(E_{r}) = E_{r} · u_{r} · f_{#}(u_{r}) · . . . · f_{#}^{k−1}(u_{r}). Each subpath of the form f_{#}^{i}(u_{r}) is called a block of f_{#}^{k}(E_{r}). Since there is no cancellation between successive blocks, it makes sense to refer to the infinite path

R_{r} = u_{r} · f_{#}(u_{r}) · . . .  (1)

as the eigenray of E_{r}.

2 Statements and corollaries

The following theorem is the main technical result of this paper.

Theorem 2.1. Let ϕ: F → F be an an automorphism. Then there exists an improved relative train track map representing some positive power of ϕ for which there exists a constant K ≥ 1 with the following property: For any pair of exponents N, i satisfying 0 ≤ i ≤ N, the following two statements hold:

1. If σ is a circuit in G, then

L (f_{#}^{i}(σ)) ≤ K (L(σ) + L (f_{#}^{N}(σ))) ,

where L(.) is the length given by the path metric on G.

2. If ρ is a path in G that starts and ends at fixed vertices, then

L (f_{#}^{i}(ρ)) ≤ K (L(ρ) + L (f_{#}^{N}(ρ))) .

The constant K is effectively computable.

We will present the proof of Theorem 2.1 in Section 7 and Section 8. Right now, we show how Theorem 0.1 follows from Theorem 2.1.

Proof of Theorem 0.1. Let ϕ: F → F be an automorphism of a finitely generated free group F = ⟨x_{1}, …, x_{n}⟩. The first part of Theorem 2.1 immediately implies that the first part of Theorem 0.1 holds for some positive power ϕ^{k}, i.e., there exists some K′ ≥ 1 such that for all 0 ≤ i ≤ N and w ∈ F, we have

||ϕ_{#}^{ik}(w)|| ≤ K′ (||w|| + ||ϕ_{#}^{Nk}(w)||) ,

where we compute lengths with respect to the generators x_{1}, …, x_{n}. Let L = max{|ϕ(x_{i})|}. Then, for 0 ≤ j < k, we have

L^{−k}||ϕ^{ik+j}(w)|| ≤ ||ϕ^{ik}(w)|| ≤ L^{k}||ϕ^{ik+j}(w)||

for all w ∈ F. We conclude that for all 0 ≤ i ≤ N and w ∈ F, we have

L^{−k}||ϕ_{#}^{i}(w)|| ≤ K′ (||w|| + L^{k}||ϕ_{#}^{N}(w)||) ,

so that the first part of Theorem 0.1 holds with K = L^{2k}K′.

In order to prove the second assertion, we modify a trick from [BFH97]. Let F′ be the free group generated by x_{1}, …, x_{n} and an additional generator a. We define an automorphism ψ: F′ → F′ by letting ψ(x_{i}) = ϕ(x_{i}) for all 1 ≤ i ≤ n, and ψ(a) = a.

By the previous step, the first part of Theorem 0.1 holds for ψ, with some constant K′ ≥ 1. Let w be some word in F. Then, for all i ≥ 0, ψ^{i}(aw) is a cyclically reduced word in F′, so that we have |ϕ^{i}(w)| + 1 = ||ψ^{i}(aw)||. We conclude that

|ϕ^{i}(w)| + 1 ≤ K′(|w| + |ϕ^{N}(w)| + 2),

for all 0 ≤ i ≤ N. Now the second assertion of Theorem 0.1 holds with K = 2K′.

Finally, we present the proof of Theorem 0.2.

Proof of Theorem 0.2. We will present an algorithm that decides whether a word u ∈ F eventually maps to another word v ≠ u. An entirely analogous algorithm decides whether u eventually maps to a conjugate of v.

Let K be the constant from Theorem 0.1, let L = K(|u|+|v|), and let N be the number of words in F whose length is at most L. We successively compute u, ϕ(u), ϕ^{2}(u), …, until one of the following mutually exclusive events occurs, for some k > 0.

• ϕ^{k}(u) = v, or

• ϕ^{k}(u) = u, or

• |ϕ^{k}(u)| > L.

One of these events occurs after no more than N iterations. In the first case, we have found a positive answer. If the first case does not occur, but the second one does, then we conclude that u is a periodic word, and that u will never map to v. In the third case, Theorem 0.1 implies that u will never map to v.

Repeating this algorithm with the roles of u and v reversed, we complete the proof of Theorem 0.2.

3 Bounded cancellation

Given an improved train track map f: G → G, we construct a metric on G. If H_{r} is an exponentially growing stratum, then its transition matrix M_{r} has a unique positive left eigenvector v_{r} (corresponding to λ_{r}) whose smallest entry equals one [Gan59]. For an edge E_{i} in H_{r}, the eigenvector v_{r} has an entry l_{i} > 0 corresponding to E_{i}. We choose a metric on G such that E_{i} is isometric to an interval of length l_{i}, and such that edges in zero strata or in polynomially growing strata are isometric to an interval of length one. Note that if ρ is a path whose endpoints are vertices, then the number of edges in ρ provides a lower bound for L(ρ). Moreover, if f is an absolute train track map, then f expands the length of legal paths by the factor λ.

Remark 3.1. We merely choose this metric for convenience. All statements here are invariant under bi-Lipschitz maps, but our metric of choice simplifies the presentation of our arguments.

Thurston’s bounded cancellation lemma is one of the fundamental tools in this paper. We state it in terms of homotopy equivalences of graphs.

Lemma 3.2 (Bounded cancellation lemma [Coo87]). Let f : G → G be a homotopy equivalence. There exists a constant C_{f}, depending only on f, with the property that for any tight path ρ in G obtained by concatenating two paths α, β, we have

L(f_{#}(ρ)) ≥ L(f_{#}(α)) + L(f_{#}(β)) − C_{f}.

Let f : G → G be an improved relative train track map with an exponentially growing stratum H_{r} with growth rate λ_{r}. The r-length of a path ρ in G, L_{r}(ρ), is the total length of ρ ∩ H_{r}.

If β is an r-legal path in G whose r-length satisfies λ_{r}L_{r}(β)−2C_{f} > L_{r}(β) and α, γ are paths such that the concatenation αβγ is an immersion, then the r-length of the segment in f_{#}^{k}(αβγ) corresponding to β will tend to infinity as k tends to infinity. The critical length C_{r} of H_{r} is the infimum of the lengths satisfying the above inequality, i. e.,

C_{r} = \frac{2C_{f}}{λ_{r} − 1}.  (2)

4 More on train tracks

We now list some additional technical results about improved train track maps. The following lemma is an immediate consequence of [Bri00, Proposition 6.2]. If H_{r} is an exponentially growing stratum, and ρ is a path of height r, we let n(ρ) denote the number of r-legal segments in ρ.

Lemma 4.1. Let f : G → G be a relative train track map, and let H_{r} be an exponentially growing stratum. For each L > 0, there exists some computable exponent M > 0 such that if ρ is a path or circuit in G_{r} containing at least one full edge in H_{r}, one of the following three statements holds:

1. f_{#}^{M}(ρ) has an r-legal segment of r-length greater than L.

2. n(f_{#}^{M}(ρ)) < n(ρ).

3. ρ can be expressed as a concatenation τ_{1}ρ′τ_{2}, where τ_{1}, τ_{2} each contain at most one r-illegal turn, the r-length of the r-legal segments of τ_{1}, τ_{2} is at most L, and ρ′ splits as a concatenation of pre-Nielsen paths (with one r-illegal turn each) and segments in G_{r−1}. Moreover, f_{#}^{M}(ρ′) is a concatenation of Nielsen paths of height r and segments in G_{r−1}.

Remark 4.2.

• The statement of Lemma 4.1 in [Bri00] does not explicitly mention the computability of M. The proof, however, only uses counting arguments, from which the constant M can be computed.

• The presence of the subpaths τ_{1}, τ_{2} in Part 3 is an artifact of the fact that ρ need not start or end at fixed points if it is a path. If ρ starts at a fixed point, then τ_{1} will be trivial, and if ρ ends at a fixed point, then τ_{2} will be trivial.

• The actual statement of [Bri00, Proposition 6.2] does not mention circuits since they were not a concern in the context of [Bri00]. The proof, however, works for circuits as well as paths. If the first two statements of Lemma 4.1 do not hold, than the third statement will hold with τ_{1} and τ_{2} trivial.

Throughout the rest of this section, let M be the constant from Lemma 4.1 for some fixed L > C_{r} (Equation 2).

From now on, we assume that f: G → G that f is an improved train track map. The following lemmas will be crucial when we analyze cancellation between eigenrays of polynomially growing strata.

Lemma 4.3. Assume that H_{r} is an exponentially growing stratum and that H_{s} = {E_{s}} is a polynomially growing stratum such that f(E_{s}) = E_{s}u_{s} and u_{s} is of height r. Then f_{#}^{(n(ρ)+1)M}(u_{s}) contains an r-legal segment of r-length L.

Proof. Since u_{s} is a closed path starting and ending at a vertex, Theorem 1.2, Part 3, implies that u_{s} cannot be a concatenation of pre-Nielsen paths and paths in G_{r−1}, so that the third statement of Lemma 4.1 cannot hold for the image of u_{s} under any positive power of f.

Now, since n(f_{#}^{(i+1)M}(u_{s})) ≤ n(f_{#}^{iM}(u_{s})) for all i ≥ 0, there exists some 0 ≤ i ≤ n(ρ) such that n(f_{#}^{iM}(u_{s})) = n(f_{#}^{(i+1)M}(u_{s})), so that Lemma 4.1 yields that for all j ≥ i + 1, f_{#}^{jM}(ρ) contains a legal segment of length at least L.

Assume that H_{r} is an exponentially growing stratum, and let ρ be a path of height r. If H_{r} does not support a closed Nielsen path, then we let N(ρ) = n(ρ). If H_{r} supports a closed Nielsen path, then we let N(ρ) equal the number of legal segments in ρ that do not overlap with a Nielsen subpath of ρ.

The following lemma is a generalization of [Bri00, Lemma 6.4].

Lemma 4.4. Assume that H_{r} is an exponentially growing stratum. There exist computable constants λ > 1, N_{0} with the following property: If f_{#}^{M}(ρ) does not contain a legal segment of length at least L, and if N(ρ) > N_{0}, then

N(f_{#}^{M}(ρ)) ≤ λ^{−1}N(ρ).

Regardless of N(ρ), we have

N(f_{#}^{M}(ρ)) ≤ λ^{−1}N(ρ) + 1.

Proof. If H_{r} does not support a closed Nielsen path, then the proof of [Bri00, Lemma 6.4] goes through unchanged. We repeat the argument here because the ideas of the proof show up more clearly in this case.

If H_{r} does not support a closed Nielsen path, then the proof is based on the following observation: If N(ρ) = 6 and f_{#}(ρ) does not contain a long legal segment, then N(f_{#}^{M}(ρ)) < 6. Suppose otherwise, i.e., N(f_{#}^{M}(ρ)) = N(ρ). Then, by Lemma 4.1, f_{#}^{M}(ρ) = τ_{1}γτ_{2}, where γ is a concatenation of three indivisible Nielsen paths of height r and paths in G_{r−1}. This is impossible because by Theorem 1.2, Part 3, we can concatenate no more than two indivisible Nielsen paths of height r with paths in G_{r−1}.

Hence, of every six consecutive legal segments in ρ, at least one cancels completely when f^{M}(ρ) is tightened to f_{#}^{M}(ρ). This implies that if N(ρ) ≥ 6, then N(f_{#}^{M}(ρ)) ≤ \frac{10}{11}N(ρ). In order to see why this choice of λ works, we just observe that if ρ consists of eleven legal segments and the sixth one cancels in f_{#}^{M}(ρ), then there are no six consecutive legal segments that survive in f_{#}^{M}(ρ).

This completes the proof of the first inequality, with λ = \frac{11}{10} and N_{0} = 5, if H_{r} does not support a closed Nielsen path. Regarding the second inequality, we remark that if N(ρ) ≤ N_{0}, then N(f_{#}^{M}(ρ)) ≤ N(ρ) ≤ λ^{−1}N(ρ) + 1.

We now assume that H_{r} supports a closed indivisible Nielsen path σ. The proof in this case is based on the following consequence of Lemma 4.1. If γ a path of height r, n(γ) = n(f_{#}^{M}(γ)) = 4, and f_{#}^{M}(γ) does not contain a long legal segment, then f_{#}^{M}(γ) = τ_{1}σ^{±1}τ_{2}, where τ_{1} and τ_{2} are as in Lemma 4.1. Intuitively, this means that if few legal segments disappear, then many Nielsen paths will appear. Since N(ρ) only counts those legal segments that do not overlap with a Nielsen path, this observation will yield the desired estimate.

First, consider a path γ of height r that does not contain any Nielsen subpaths, i.e., we have N(γ) = n(γ). If N(γ) ≥ 4, then for every four consecutive legal segments whose images do not cancel completely in f_{#}^{M}(γ), f_{#}^{M}(γ) contains at least one Nielsen subpath, so that we have N(f_{#}^{M}(γ)) ≤ \frac{6}{7}N(γ), using the same reasoning as above.

We claim that if γ starts and ends at fixed points, then, by Remark 4.2, we have N(f_{#}^{M}(γ)) ≤ \frac{6}{7}N(γ) regardless of N(γ). To this end, we first argue that if γ starts and ends at fixed points, then n(f_{#}^{M}(γ)) < n(γ). If this were not true, then, by Lemma 4.1 we would have f_{#}^{M}(γ) = σ^{m} for some m ∈ ℤ, which would imply that γ = σ^{m} because γ starts and ends at fixed points. This is a contradiction since we assumed that γ does not contain any Nielsen subpaths. Now, if n(γ) = N(γ) < 4, then we conclude that N(f_{#}^{M}(γ)) ≤ n(f_{#}^{M}(γ)) < n(γ). Now n(γ) < 4 implies that \frac{6}{7}n(γ) ≥ n(γ)−1, which implies that N(f_{#}^{M}(γ)) ≤ \frac{6}{7}n(γ) = \frac{6}{7}N(γ).

After these preparations, we express ρ as a concatenation

ρ = ρ_{1}σ^{n_{1}}ρ_{2}σ^{n_{2}}ρ_{3} ⋯ ρ_{k}σ^{n_{k}}ρ_{k+1},

where n_{1}, …, n_{k} ∈ ℤ, and none of the subpaths ρ_{i} contains a Nielsen subpath.

Note that the subpaths ρ_{2}, …, ρ_{k} start and end at the base point v of the Nielsen path σ, which is fixed by f. Hence, for 2 ≤ i ≤ k, we have N(f_{#}^{M}(ρ_{i})) ≤ \frac{6}{7}N(ρ_{i}), and we have N(f_{#}^{M}(ρ_{1})) ≤ \frac{6}{7}N(ρ_{1}) (resp. N(f_{#}^{M}(ρ_{k+1})) ≤ \frac{6}{7}N(ρ_{k+1})) if N(ρ_{1}) ≥ 4 (resp. N(ρ_{k+1}) ≥ 4).

If N(ρ_{1}) < 4 and N(ρ_{k+1}) < 4, we have

N(f_{#}^{M}(ρ)) ≤ N(ρ_{1}) + N(ρ_{k+1}) + \frac{6}{7}(N(ρ) − N(ρ_{1}) − N(ρ_{k+1}))
≤ 6 + \frac{6}{7}(N(ρ) − 6) ≤ \frac{6}{7}(1 + N(ρ)).

Similar estimates yield that N(f_{#}^{M}(ρ)) ≤ \frac{6}{7}(1 + N(ρ)) regardless of N(ρ_{1}) and N(ρ_{k+1}).

If N(ρ) > 11, then \frac{6}{7}(1+N(ρ)) ≤ \frac{13}{14}N(ρ), which implies that N(f_{#}^{M}(ρ)) ≤ \frac{13}{14}N(ρ) if N(ρ) > 11, so that the first inequality of the lemma holds with λ = PSfrag replacements

E_{i}

E_{j}
α
β
γ
f_{#}^{k}(u_{i})
f_{#}^{l}(u_{j})

Figure 1: The idea of the proof of Lemma 4.5.

\frac{14}{13} and N_{0} = 11. As for the second inequality, we remark that N(f_{#}^{M}(ρ)) ≤ N(ρ) and, if N(ρ) ≤ 11, then N(ρ) ≤ λ^{−1}N(ρ) + 1.

The next lemma is a statement about the (absence of) cancellation between eigenrays of polynomially growing strata. It is a stronger version of [BFH98, Sublemma 1, Page 587].

Lemma 4.5. Let H_{i} = {E_{i}} and H_{j} = {E_{j}} be polynomially growing strata. Let S_{i} (resp. S_{j}) be an initial segment of E_{i}R_{i} (resp. E_{j}R_{j}) such that the concatenation S_{i}S̄_{j} is a path. If S_{i} grows faster than linearly and if an entire block of R_{j} is canceled in f_{#}^{k}(S_{i}S̄_{j}) for some k ≥ 0, then no entire block of S_{i} will be canceled in f_{#}^{l}(S_{i}S̄_{j}) for any l ≥ 0.

Proof. Suppose that at least one block of both S_{i} and S_{j} cancels. Then there are paths α, β, and γ such that f_{#}^{k}(u_{i}) = βγ, f_{#}^{l}(u_{j}) = αβ for some k, l ≥ 0, and f_{#}(α) = γ (see Figure 1).

In particular, we have

R_{i} = R_{i}^{k−1}βf_{#}(α)f_{#}(β)f_{#}^{2}(α) …,

and

R_{j} = R_{j}^{l−1}αβf_{#}(α)f_{#}(β)f_{#}^{2}(α) ….

In particular, the path ρ = E_{i}R_{i}^{k−1}ᾱR̄_{j}^{l−1}Ē_{j} does not split. By Theorem 1.2, ρ is a exceptional path, and both E_{i} and E_{j} grow linearly.

5 Terminology and examples

In this section, we discuss some examples that illustrate some of the main issues that we need to address in the proof of Theorem 2.1. Although we PSfrag replacements

k
w_{0}
w_{i}
w_{k}
u_{1}
u_{k−1}
v_{1}
v_{2}
v_{k−1}

Figure 2: A hallway.

are not primarily concerned with free-by-cyclic groups in this article, the language of free-by-cyclic groups will streamline the exposition.

Given a free group F_{n} = ⟨x_{1}, …, x_{n}⟩ and an automorphism ϕ of F_{n}, the mapping torus of ϕ is the free-by-cyclic group

M_{ϕ} = ⟨x_{1}, …, x_{n}, t | t^{−1}x_{i}tϕ(x_{i}^{−1})⟩.

The letter t is called the stable letter of M_{ϕ}.

A reduced word w in the generators of M_{ϕ} is a hallway if w represents the trivial element of M_{ϕ} and if w can be expressed as w = w_{1}w_{2} such that w_{1} only contains negative powers of t and w_{2} only contains positive powers of t [BF92]. Hallways of the form t^{−k}xt^{k}ϕ^{k}(x^{−1}), for x ∈ F_{n}, are said to be smooth.

Any hallway w can be expressed as

w = t^{−1}u_{k−1}t^{−1}u_{k−2}t^{−1} ⋯ t^{−1}u_{1}t^{−1}w_{0}tv_{1}tv_{2}t ⋯ tv_{k−1}tw_{k}^{−1},

where w_{0}, w_{k}, u_{1}, …, u_{k−1}, v_{1}, …, v_{k−1} are elements of F_{n}. The words u_{i} and v_{i} may be empty. In fact, a hallway is smooth if and only if all the u_{i} and v_{i} are trivial. For 1 ≤ i < k, we define w_{i} to be the word obtained by tightening u_{i}ϕ(w_{i−1})v_{i}. Since w represents the identity, we have w_{k} = ϕ(w_{k−1}). We call w_{i} the i-th slice of w. The number k is the duration D(w) of the hallway. Figure 2 illustrates these notions.

PSfrag replacements

b c a^{2} a^{3} a^{k}

Figure 3: Illustration of Example 5.1.

We say that the instances of letters of F_{n} that occur in the spelling of w are visible. Theorem 0.1 states that if w is a smooth hallway, then the length of each w_{i} is bounded by a constant multiple of the number of visible edges in w.

The following examples illustrate the main issues that arise in the proof. For the remainder of this section, let F_{6} = ⟨a, b, c, d, x, y⟩, and define ϕ by letting

a ↦ a
b ↦ ba
c ↦ caa
d ↦ dc
x ↦ y
y ↦ xcy.

This automorphism admits the stratification H_{1} = {a}, H_{2} = {b}, H_{3} = {c}, H_{4} = {d}, and H_{5} = {x, y}. The restriction of f to the filtration element G_{3} = H_{1} ∪ H_{2} ∪ H_{3} grows linearly, the restriction to G_{4} grows quadratically, and the stratum H_{5} is of exponential growth.

The first example illustrates the behavior of smooth hallways in linearly growing filtration elements.

Example 5.1. Let w_{0} be a word from the list a^{m}, ba^{m}b^{−1}, ca^{m}c^{−1}, for some integer m. Then ϕ(w_{0}) = w_{0}, so that the length of any slice of the hallway PSfrag replacements

b
c
a^{k}

Figure 4: Illustration of Example 5.2.

t^{−k}w_{0}t^{k}w_{0}^{−1} is the same as the length of w_{0}. Now, let w_{0} be a word from the list ba^{m}, ca^{m}, ca^{m}b^{−1}. If m ≥ 0, then |ϕ^{k+1}(w_{0})| = |ϕ^{k}(w_{0})| + 1 for any k ≥ 0. If m < 0, then |ϕ^{k+1}(w_{0})| = |ϕ^{k}(w_{0})| − 1 for 0 ≤ k < −m (Figure 3). Hence, the length of each slice of the hallway t^{−k}w_{0}t^{k}ϕ^{k}(w_{0}^{−1}) is bounded by the number of visible letters.

If w_{0} is an arbitrary word in ⟨a, b, c⟩, then, by Remark 1.4, it splits as a concatenation of words from the above lists and their inverses, which implies that the lengths of slices of smooth hallways is bounded by the number of visible letters, so that Theorem 0.1 holds with K = 1.

The next example shows that hallways that are not smooth may have slices whose length is not bounded in terms of a constant multiple of the number of visible edges.

Example 5.2. Let w = t^{−k}ct^{−k}b^{−1}t^{2k}bc^{−1}. For i < k, we have w_{i} = a^{−i}b^{−1}, and for k ≤ i ≤ 2k, we have w_{i} = ca^{2k−i}b^{−1} (Figure 4). In particular, there is a slice of length k + 2 although there are only four visible edges in w. Informally, one might say that hallways of this form bulge in the middle. A similar bulge occurs for hallways of the form w = t^{−k}b^{−1}t^{−k}bt^{k}b^{−1}t^{k}b.

The next example shows that we need to control the size of such bulges when proving Theorem 2.1.

Example 5.3. First, note that for k ≥ 1, the last letter in the words f^{−k}(xc) is always one of x, y, x^{−1}, y^{−1}, so that words of the form w_{0} = ϕ^{−k}(xc)b^{−1} are reduced, and we have ϕ^{k}(w_{0}) = xca^{k}b^{−1} and ϕ^{2k}(w_{0}) = ϕ^{k}(x)b^{−1}.

Hence, the smooth hallway w = t^{−2k}w_{0}t^{2k}ϕ^{2k}(w_{0}^{−1}) contains a bulge like the first one in the previous example (Figure 5). The presence of this bulge PSfrag replacements

b c x a^{k} ϕ^{−k}(xc) ϕ^{k}(x)

Figure 5: Illustration of Example 5.3.

does not contradict Theorem 0.1 because w contains a large number of visible instances of the letters x and y. This example shows that we cannot consider the strata separately when proving Theorem 2.1.

Example 5.4. If we let w_{0} = ϕ^{−k}(dc)b^{−1}, then the smooth hallway w = t^{−2k}w_{0}t^{2k}ϕ^{2k}(w_{0}^{−1}) contains a bulge like in Example 5.3. This does not contradict Theorem 0.1 as w contains a large number of visible instances of the letter c.

Our final example illustrates a subtlety regarding linearly growing strata.

Example 5.5. Let F_{4} = ⟨a, b, c, d⟩ and define ψ by letting

a ↦ a
b ↦ ba
c ↦ ca
d ↦ dcb^{−1}.

The map ψ is a linearly growing automorphism, so in particular the letter d is of linear growth, although the image of d contains letters of linear growth other than d itself. This phenomenon is unique to letters of linear growth. A letter of quadratic growth, for instance, cannot possibly map over other letters of quadratic growth because of Theorem 1.2, Part 4.

Letters of linear growth may thus behave in two different ways; they may contribute to the growth of images under successive applications of ψ, or they may remain inert as parts of a fixed word. In the proof of Theorem 2.1, we will need to distinguish letters of linear growth according to their role.

The notion of hallways naturally extends to mapping tori of homotopy equivalences of finite graphs. Specifically, a hallway ρ in the mapping torus of f: G → G is an edge path of the form

ρ = t^{−1}μ_{k−1}t^{−1}μ_{k−2}t^{−1} ⋯ t^{−1}μ_{1}t^{−1}ρ_{0}tν_{1}tν_{2}t ⋯ tν_{k−1}tρ_{k}^{−1},

where ρ_{0}, ρ_{k}, μ_{1}, …, μ_{k−1}, ν_{1}, …, ν_{k−1} are edge paths in G. The paths μ_{i} and ν_{i} are called notches. Some or all of the notches may be trivial. For 1 ≤ i < k, we define ρ_{i} to be the path obtained by tightening μ_{i}f(ρ_{i−1})ν_{i}. Since ρ is a closed path, we have ρ_{k} = f_{#}(ρ_{k−1}). As before, we call ρ_{i} the i-th slice of ρ, and the number k is the duration D(ρ).

The number of visible edges in ρ is

V (ρ) = L(ρ_{0}) + L(ρ_{k}) + ∑_{i=1}^{k−1} (L(μ_{i}) + L(ν_{i})) .

Finally, we introduce quasi-smooth hallways: Given some C ≥ 0, we say that w hallway ρ is C-quasi-smooth if the length of all the notches is bounded by C.

6 Strata of superlinear growth

Throughout this section, let f: G → G be an improved relative train track map.

When considering a slice ρ_{i} of a hallway ρ, it makes sense to talk about the origin of each edge of ρ_{i}. Such an edge may be visible, or it may come from the image of an edge in a previous slice. In particular, it makes sense to distinguish between those edges that originate from the image of an edge of linear growth, and those that do not. (This distinction is necessary because of the phenomenon illustrated by Example 5.5.)

The following proposition goes a long way toward proving Theorem 2.1. In fact, if f has no edges of linear growth, then it immediately implies Theorem 2.1.

Proposition 6.1. There exists some constant K ≥ 1 such that for every hallway ρ and every slice ρ_{i} of ρ, the number of edges in ρ_{i} that do not originate from edges of linear growth is bounded by KV (ρ). The constant K is effectively computable.

In order to streamline the exposition, we will not always make the choice of K explicit. However, it will turn out that K can be chosen to be the product of numbers that can easily be read off from the train track map.

The intuition of the proof is that once significant growth occurs, it will be due to the presence of long legal subpaths in exponentially growing strata or long subsegments of eigenrays of polynomially growing strata that grow faster than linearly. Lemma 3.2 and Lemma 4.5 imply that there is hardly any cancellation between such subpaths and their surroundings, so that any significant growth that occurs in a slice will eventually be accounted for by visible edges.

The following definition will help us understand cancellation in hallways. For every stratum H_{r}, we define a number h(H_{r}) in the following way:

• If H_{r} is a constant stratum, then h(H_{r}) = 0.

• If H_{r} is a nonconstant polynomially growing stratum, i.e., H_{r} = {E_{r}} and f(E_{r}) = E_{r}u_{r}, then h(H_{r}) is the height of u_{r}.

• If H_{r} is of exponential growth and H_{r−1} is not a zero stratum, then h(E_{r}) is the height of f(H_{r}) ∩ G_{r−1}, unless this intersection does not contain any edges, in which case we let h(H_{r}) = ∞.

• If H_{r} is of exponential growth and H_{r−1} is a zero stratum, then h(E_{r}) is the height of f(H_{r} ∪ H_{r−1}) ∩ G_{r−2}. We also let h(H_{r−1}) = h(H_{r}).

Essentially, h(H_{r}) is the index of the highest stratum crossed by the image of H_{r}, other than H_{r} itself. We may permute the strata of G (while preserving the improved train track properties) such that h(H_{r}) > h(H_{s}) implies r > s. In particular, all constant and linearly growing strata are at the bottom.

Given a stratum H_{s}, we say that the set S(H_{s}) = {H_{r}|h(H_{r}) = s} is the league of H_{s}, the motivation being that they, in a sense, “play at the same level”. If h(H_{r}) = ∞, then H_{r} does not belong to any league.

Proof of Proposition 6.1. First of all, we note that if a slice ρ_{i} has a subpath in a zero stratum H_{r}, then this subpath is of uniformly bounded length, and it is surrounded by edges in the exponentially growing stratum H_{r+1} (Theorem 1.2, Part 1), so that we have a linear estimate of the number of edges in H_{r} in ρ_{i} in terms of the number of edges in H_{r+1}.

Let p be the largest number for which the league S(p) is nonempty. Fix some stratum H_{r} for r > p. We want to find a linear bound on the number of edges in ρ_{i} ∩ H_{r} in terms of visible edges. By definition of S(p) and choice of r, edges in ρ_{i} ∩ H_{r} never cancel with edges from other strata or their images.

If H_{r} = {E_{r}} is of polynomial growth, then any occurrence of E_{r} in ρ_{i} is the image of a visible copy of E_{r}, and ρ_{i} contains at most one copy of E_{r} for each visible copy of E_{r}. Hence, the number of edges in ρ_{i} ∩ H_{r} is bounded by the number of visible edges.

Now, assume that H_{r} is an exponentially growing stratum. A slice ρ_{i} decomposes into r-legal subpaths with r-illegal turns in between. By Lemma 3.2, a subpath whose r-length is greater than C_{r} (Equation 2) will eventually be accounted for by visible edges since it will not be shortened by cancellation within slices.

Edges in H_{r} whose r-distance from an illegal turn is less than \frac{C_{r}}{2} may cancel eventually, and ρ_{i} contains at most C_{r} of them per r-illegal turn, so that we only need to find a bound of the number of r-illegal turns in terms of the number of visible edges. Since the improved train track map f does not create any illegal turns, any r-illegal turn in ρ_{i} can be traced back to a visible illegal turn in ρ. This implies that the number of r-illegal turns in ρ_{i} is bounded by the number of visible edges in ρ.

Summing up, we have bounded the number of edges in ρ_{i}∩(H_{p+1}∪H_{p+2}∪ …) by a multiple of the number of visible edges.

We now find a bound on the number of edges in ρ_{i} ∩ H_{p}. We first assume that H_{p} is of polynomial growth. By definition of S(p), an edge in ρ_{i} ∩ H_{p} comes from one of four possible origins:

• It may be the image of a visible edge in H_{p}, or

• it may be in the image of an edge in an exponentially growing stratum in S(p), or

• it may be in the eigenray of a superlinear polynomially growing stratum in S(p), or

• it may be in the eigenray of a linearly growing stratum in S(p).

We are not concerned with edges of the fourth kind.

As before, the number of edges of the first kind in ρ_{i} ∩ H_{p} is bounded by the number of visible edges. Let C be the largest number of copies of E_{p} that occur in the image of a single edge in an exponentially growing stratum H_{s}, for s > p. Then the number of edges of the second kind in ρ_{i} ∩H_{p} is bounded by C times the number of exponentially growing edges in ρ_{i−1} ∩ S(p), which in turn is bounded by a multiple of the number of visible edges.

We have no immediate bound on the number of edges of the third kind. As we trace the image of such an edge through subsequent slices, one of three mutually exclusive events will occur:

• Either, it eventually maps to a visible edge, or

• it cancels with an edge of the first or second kind, or

• it cancels with an edge in the eigenray of a polynomially growing (possibly linearly growing) edge in S(p).

The number of edges for which one of the first two events occurs is clearly bounded by a multiple of the number of visible edges. We only need to find a bound on the number of edges in an eigenray that eventually cancel with edges in another eigenray.

Lemma 4.5 implies that there is a uniform bound on the number of edges in H_{p} that cancel when two rays meet, so that we only need to find a bound on the number of meetings between two rays. Clearly, any two rays meet at most once.

If an eigenray cancels with segments from more than one other ray (This is conceivable since a slice may be of the form ρ_{i} = E_{r}S_{1}S_{2}, where E_{r} is a polynomially growing edge in S(p) and the S_{1}, S_{2} are short segments from rays of edges in S(p) such that the ray of E_{r} successively cancels with S_{1} and S_{2}), then all except possibly one of these segments cancel completely, so that they are no longer available for subsequent cancellation. This implies that the number of meetings of rays is bounded by two times the number of pieces of rays available for cancellation, which in turn is bounded by the number of visible edges.

This completes our estimate of the number of edges in ρ_{i} ∩ H_{p} when H_{p} is of polynomial growth. We now assume that H_{p} is of exponential growth.

The number of subpaths of height p of ρ_{i} is bounded by the number of edges of height greater than p in ρ_{i} plus one. The contribution of p-legal subpaths of p-length less than or equal to C_{p} is bounded by C_{p} times the number of subpaths of height p, so that we do not need to worry about them. Any p-legal subpaths of length greater than C_{p} will eventually show up in the visible part of ρ, so that we do not need to worry about them either. The remaining edges in ρ_{i} ∩ H_{p} are at p-distance less than \frac{C_{p}}{2} from a p-illegal turn. Hence, we only need to find a bound on the number of p-illegal turns in ρ_{i}.

As before, we trace illegal turns in ρ_{i} back to their origin:

• An illegal turn may be the image of a visible illegal turn, or

• it may come from a illegal turn in the image of an exponentially growing edge in S(p), or

• it may be contained in the ray of a polynomially growing edge in S(p).

The same arguments that we used for polynomially growing H_{p} yield that the number of illegal turns of the first and second kind is bounded by a multiple of the number of visible edges.

Now, let C be the maximum of the number of illegal turns in the images of polynomially growing edges in S(p). Lemma 4.3 implies that for any polynomially growing edge E_{r} in S(p), f_{#}^{C+1}(u_{r}) contains a long legal segment. This means, in particular, that if ρ contains a block f_{#}^{k}(u_{r}), k ≥ C + 1, then this block contains no more than C illegal turns per long legal segment. Since long legal segments eventually show up as visible edges, the number of illegal turns in such blocks is bounded by CV (ρ).

The remaining illegal turns are contained in initial subpaths of rays that contain no more than the first C + 1 blocks, i.e., there are at most C(C + 1) illegal turns of this kind per ray. Since we already know that the number of rays is bounded in terms of the number of visible edges, we are done in this case.

We have now obtained the desired estimate for edges in ρ_{i} of height p and higher. In particular, this includes all strata in S(p − 1), so that we can repeat the above argument in order to obtain a bound on the number of edges in ρ_{i} ∩ H_{p−1}, etc. Proceeding by induction down through the strata, we complete the proof of the proposition.

7 Polynomially growing automorphisms

In this section, we establish Theorem 2.1 in the case of polynomially growing automorphisms. Specifically, we find estimates for the contribution of linearly growing edges that we ignored in Proposition 6.1. As usual, let f: G → G be an improved relative train track map. Since f is of polynomial growth, every stratum H_{r} contains only one edge E_{r}, and we have f(E_{r}) = E_{r} · u_{r}, where u_{r} is some closed path in G_{r−1}. Note that all vertices of G are fixed.

We first record an obvious lemma.

Lemma 7.1. Let μ_{1}, μ_{2} be Nielsen paths in G, and let ν be some path in G.

• If μ_{1} and μ_{2} can be concatenated, then the path obtained from μ_{1}μ_{2} by tightening relative endpoints is also a Nielsen path.

• If μ_{1} and ν can be concatenated, let γ be the path obtained by tightening μ_{1}ν, and let Δ = L(γ) − L(ν). Then, for all k ≥ 0, we have

L (f_{#}^{k}(γ)) = L (f_{#}^{k}(ν)) + Δ,

and

−L(μ_{1}) ≤ Δ ≤ L(μ_{1}).

We now establish Theorem 2.1 for automorphisms of linear growth. This lemma will provide the base case of our inductive proof of Theorem 2.1.

Lemma 7.2. Assume that f: G → G is of linear growth. If ρ is a smooth hallway, and if ρ_{0} starts and ends at vertices, then the lengths of slices of ρ are bounded by V (ρ), i.e., Theorem 2.1 holds with K = 1.

Proof. The proof proceeds by induction up through the strata of G. The bottom stratum H_{1} is constant, so that the lemma trivially holds for the restriction of f to H_{1}. We now assume that H_{r} is a linearly growing stratum, and that the lemma holds for the restriction of f to G_{p−1}.

Consider the initial slice ρ_{0}. Remark 1.4 yields a splitting of ρ_{0} into basic paths of height p and paths in G_{p−1}. The splitting of ρ_{0} induces a decomposition of ρ into smooth hallways, so that it suffices to prove the claim for hallways whose initial slice is a basic path of height p or a path in G_{p−1}.

By induction, we only need to prove the claim if ρ_{0} is a basic path of height p. If the basic path ρ_{0} is, in fact, an exceptional path, then the reasoning of Example 5.1 proves our claim, so that we may assume that ρ_{0} is not an exceptional path.

PSfrag replacements

α β E_{r} u_{r} t^{k} cut

sawtooth construction

Figure 6: Cutting and the sawtooth construction.

Assume that ρ_{0} is a basic path of the form E_{p}γ. Then, by Theorem 1.2, Part 4, there exists some smallest exponent m ≥ 0 for which f_{#}^{m+1}(E_{p}γ) splits as E_{p} · γ′. Using Remark 1.4 once more, we conclude that E_{p}γ can be expressed as E_{p}u_{p}^{−m}ν.

If D(ρ) ≤ m, then ρ_{0} k-splits as E_{p}u_{p}^{−m} · ν. We can consider the subpaths E_{p}u_{p}^{−m} and ν separately, so that we are done in this case.

Now assume that D(ρ) > m. For 0 ≤ i ≤ m, we have ρ_{i} = E_{p}u_{p}^{i−m}f_{#}^{i}(ν) and L(ρ_{i}) = 1 + (m − i)L(u_{p}) + L (f_{#}^{i}(ν)). For m + 1 ≤ i ≤ D(ρ), we have ρ_{i} = E_{p}u_{p}^{i−(m+1)}f_{#}^{i}(u_{p}ν) and L(ρ_{i}) = 1 + (i − m − 1)L(u_{p}) + L (f_{#}^{i}(ν)) + Δ, where Δ is defined as in Lemma 7.1.

We have V (ρ) = 2 + (D(ρ) − 1) L(u_{p}) + L(ν) + L (f_{#}^{D(ρ)}(ν)) + Δ. By

induction, we have L (f_{#}^{i}(ν)) ≤ L(ν) + L (f_{#}^{D(ρ)}(ν)) for all 0 ≤ i ≤ D(ρ). This immediately implies that L(ρ_{i}) ≤ V (ρ) for all 0 ≤ i ≤ D(ρ).

If ρ_{0} = E_{p}γE_{p}^{−1}, we essentially repeat the same argument. Once more, we can write ρ_{0} = E_{p}u_{p}^{−m}ν, and in order to use the previous argument, we only need to know that the lemma holds for ν. This, however, follows from the previous step, so that we are done.

We now find estimates on the number of edges emitted by linearly growing edges, the quantity we ignored in Proposition 6.1. The idea is to take a hallway and decompose it into smaller and smaller pieces until all remaining pieces only involve linearly growing edges and their rays. Simple counting arguments will give us bounds on the number of the remaining pieces as well as the lengths of their slices.

Let ρ be a hallway, and assume that there is a visible edge E_{r} that does not cancel within ρ, i.e., we can trace its image through the slices of ρ until it reappears as another visible edge. Then ρ can be expressed as ρ = αE_{r}βE_{r}^{−1}, and we define two new hallways ρ′, ρ′′ by tightening t^{−k}E_{r}βE_{r}^{−1} and αt^{k}. We say that ρ′ and ρ′′ are obtained from ρ by cutting along the trajectory of E_{r} (Figure 6). The exponent k is the length of the cut. We say that a hallway ρ is indecomposable if it does not admit any cuts of length D(ρ).

Now we obtain a new hallway σ from ρ′ by repeatedly replacing subwords of the form t^{−1}E_{r} by f(E_{r})t^{−1} and tightening (Figure 6). We refer to this operation as the sawtooth construction along the trajectory of E_{r}.

If M is a collection of hallways, we let

V (M) = ∑_{σ∈M} V (σ).

The following lemma lists some basic properties of our two operations. We say that an edge is of degree d if f_{#}^{k}(E) grows polynomially of degree d.

Lemma 7.3. Fix some C ≥ max{L(u_{r})}. Let ρ be a C-quasi-smooth hallway in G. Choose d > 1 such that the fastest growing edge crossed by ρ grows polynomially of degree d.

Obtain a collection M of hallways by cutting along all trajectories of edges E in ρ of degree d. Let M_{1} be the collection of smooth elements of M, and let M_{2} consist of hallways obtained by performing the sawtooth construction along all trajectories of E of degree d in those elements of M that are not smooth. Then

1. The duration of all elements of M_{1} and M_{2} is at most D(ρ).

2. None of the elements of M_{2} crosses edges of degree d, i.e., they only cross edges of degree at most d − 1.

3. All elements of M_{2} are 2C-quasi-smooth.

4. The number of elements of M_{2} is bounded by 2CD(ρ).

5. We have

V (M_{1}) + V (M_{2}) ≤ V (ρ) + (2CD(ρ))^{2} .

Proof. The first four properties follow immediately from definitions. In order to prove the fifth property, we just remark that each element of M_{2} has at most 2CD(ρ) visible edges that do not appear in ρ itself. Since M_{2} contains at most 2CD(ρ) hallways, the estimate follows.

Lemma 7.4. There exists a (computable) constant C with the following property:

Let γ be a path of height r, starting and ending at vertices, and assume that E_{r} is of degree d > 1. Then, for all k ≥ 0,

L(γ) + L(f_{#}^{k}(γ)) ≥ Ck^{d}.

Proof. It suffices to prove the lemma if either γ = E_{r}γ′, or γ = E_{r}γ′E_{s}^{−1}, where γ′ only involves edges of degree less than d, and E_{s} is of degree d.

In the first case, the claim is obvious. In the second case, we remark that Lemma 4.5 guarantees that there is hardly any cancellation between the rays of E_{r} and E_{s}, so that the lemma follows.

The following proposition implies the second part of Theorem 2.1 in the case of polynomially growing automorphisms. In particular, it provides bounds on the number of edges emitted by linearly growing edges. This is the quantity that we ignored in Proposition 6.1.

Proposition 7.5. Assume that f represents an automorphism that grows polynomially of degree q. Fix some C ≥ max{L(u_{r})}. There exist computable constants K_{1} ≤ K_{2} ≤ … ≤ K_{q} and K′_{1}(C), …, K′_{q}(C) such that

1. If ρ is a smooth hallway whose fastest growing edge is of degree d, and if ρ_{0} starts and ends at vertices, then

L(ρ_{i}) ≤ K_{d}V (ρ)

for all slices ρ_{i} of ρ.

2. If ρ is a C-quasi-smooth hallway whose fastest growing edge is of degree d, then in every slice ρ_{i}, the number of edges emitted by linearly growing edges is bounded by

K_{d}V (ρ) + K′_{d}(C)D^{d+1}(ρ),

so that we have

L(ρ_{i}) ≤ (K + K_{d})V (ρ) + K′_{d}(C)D^{d+1}(ρ),

where K is the constant from Proposition 6.1.

Proof. We prove the proposition by induction on d. For d = 1, the first part holds with K_{1} = 1 because of Lemma 7.2. Now, assume that ρ is a C-quasi-smooth hallway whose fastest growing edge grows of degree d = 1. Obtain a collection M of hallways by cutting ρ along the trajectories of all linearly growing edges that do not cancel within ρ. If σ is a smooth element of M, then the first part implies that the number of edges in each σ_{i} emitted by linearly growing edges is bounded by V (σ).

If σ is not smooth, then in every slice σ_{i}, the number of edges emitted by linearly growing edges is bounded by V (σ) + 2CD(ρ) (It is helpful to keep Example 5.2 in mind). Lemma 7.3 yields that M contains no more than 2CD(ρ) pieces that are not smooth. Summing up, we conclude that every slice of ρ contains at most V (ρ)+(2CD(ρ))^{2} edges emitted by linearly growing edges, so that the second statement follows with K_{1} = 1 and K′_{1}(C) = 4C^{2}.

Now, let K be the constant from Proposition 6.1, and assume inductively that the proposition holds for some d ≥ 1. We want to find some K_{d+1} such that for all hallways ρ whose fastest growing edge is of degree d + 1, we have

L(ρ_{i}) ≤ K_{d+1}V (ρ).

for all slices ρ_{i}. It suffices to prove this with the assumption that ρ is indecomposable. Then we can perform the sawtooth construction along all trajectories of edges of degree d + 1. Since ρ is indecomposable, we obtain one C-quasi-smooth piece σ that only crosses edges of degree d or lower, so that by induction, we conclude that the number of edges in σ_{i} that were emitted by linearly growing edges is bounded by

K_{d}V (σ) + K′_{d}(C)D^{d+1}(ρ).

We conclude that

L(ρ_{i}) ≤ KV (ρ) + K_{d}V (σ) + K′_{d}(C)D^{d+1}(ρ)
≤ (K + K_{d})V (ρ) + (2C + K′_{d}(C)) D^{d+1}(ρ).

Using Lemma 7.4, we can find some constant M such that

MV (ρ) ≥ (2C + K′_{d}(C)) D^{d+1}(ρ)

for all indecomposable hallways ρ involving edges of degree d+1. We conclude that the first statement of the proposition holds with K_{d+1} = K + K_{d} + M.

We now prove the second assertion. Let ρ be a C-quasi-smooth hallway. We obtain two collections M_{1}, M_{2} of hallways by performing cutting and sawtooth operations as in Lemma 7.3.

The elements of M_{1} are smooth hallways, so that for any σ ∈ M_{1}, the previous step yields

L(σ_{i}) ≤ K_{d+1}V (σ).

If σ is an element of M_{2}, then it is a 2C-quasi-smooth hallway, and induction yields that in every slice of σ, the number of edges emitted by linearly growing edges is bounded by

K_{d}V (σ) + K′_{d}(2C)D^{d+1}(σ).

Summing over all elements of M_{1} and M_{2}, we conclude that every slice ρ_{i} of ρ contains at most

K_{d+1}V (M_{1}) + K_{d}V (M_{2}) + 2CD(ρ) · K′_{d}(2C)D^{d+1}(ρ)
≤ K_{d+1}V (ρ) + 4C^{2}K_{d}D^{2}(ρ) + 2CK′_{d}(2C)D^{d+2}(ρ)

edges emitted by linearly growing edges, so that the second statement of the proposition holds with

K′_{d+1}(C) = 4C^{2}K_{d} + 2CK′_{d}(2C).

Remark 7.6. The estimates of Proposition 7.5 are rather crude; lots of edges are counted several times rather than just once. I opted to present the most straightforward estimates rather than tightest ones.

8 Proof of the main result

We now extend the techniques and results of Proposition 7 to arbitrary automorphisms. The presence of exponentially growing strata will turn out to be a mixed blessing. On the one hand, they make for rather simple counting arguments as polynomial contributions as in Proposition 7.5 are easily dwarfed by exponential growth. On the other hand, we will need to consider more complicated decompositions of hallways.

As usual, let f: G → G be an improved relative train track map. After permuting the strata if necessary, we may assume that there exists some s such that the restriction of f to G_{s} is of polynomial growth, and that all higher strata are either exponentially growing strata (with their accompanying zero strata) or polynomially growing strata whose blocks eventually map over exponentially growing edges. Throughout this section, let K be the constant from Proposition 6.1.

If H_{r} is an exponentially growing stratum, then we fix some L > C_{r}, and we replace f by f^{M}, where M is the exponent from Lemma 4.1 for this choice of L. After replacing f by a power yet again if necessary, we may assume that the image of each edge in H_{r} contains at least L edges in H_{r}. If H_{r} supports a closed Nielsen path τ, then the initial and terminal edges of τ are partial edges in H_{r}, and we may assume that the image of each of them also contains at least L edges in H_{r}. We say that a legal path of height r is long if it contains at least L edges in H_{r}.

We first record an exponential version of Lemma 7.4.

Lemma 8.1. Let H_{r} be an exponentially growing stratum or a polynomially growing stratum whose blocks eventually map over an exponentially growing stratum. Then there exists a computable constant λ > 1 such that if σ is a circuit in G_{r} or a path starting and ending at fixed vertices, then either σ is a concatenation of Nielsen paths of height r and subpaths in G_{r−1}, or we have

L(σ) + L(f_{#}^{k}(σ)) ≥ λ^{k}

for all k ≥ 0.

Proof. If H_{r} = {E_{r}} is a polynomially growing stratum, then we argue as in the proof of Lemma 7.4. If H_{r} is an exponentially growing stratum, we need to distinguish two cases: First, assume that for some i ≥ 0, f_{#}^{i}(σ) is a concatenation of Nielsen paths and subpaths in G_{r−1}. Since σ starts and ends a fixed vertices, we conclude that σ itself is a concatenation of Nielsen paths and subpaths in G_{r−1}, so that there is nothing to show in this case.

Let λ_{−}, N_{0} be the constants from Lemma 4.4, and assume that for all i ≥ 0, f_{#}^{i}(σ) is not a concatenation of Nielsen paths and subpaths in G_{r−1}. Let i_{0} be the smallest index for which f_{#}^{i_{0}}(σ) contains a long legal segment. Then, using Lemma 4.4 and Lemma 4.1, we see that L(σ) ≥ λ_{−}^{i_{0}}. Moreover, we have L(f_{#}^{k}(σ)) ≥ λ_{r}^{k−i_{0}}.

If we let λ = \sqrt{max\{λ_{−}, λ_{r}\}}, then we have λ_{−}^{i_{0}} + λ_{r}^{k−i_{0}} ≥ λ^{k}. Hence, we have L(σ) + L(f_{#}^{k}(σ)) ≥ λ_{−}^{i_{0}} + λ_{r}^{k−i_{0}} ≥ λ^{k}.

If H_{r} is an exponentially growing stratum, we let L_{r} equal the length of the longest path in f(H_{r}) ∩ G_{r−1}. We fix another constant L_{C} > 0 with the following property: Let γ be a path in G_{r−1}. If L(γ) ≥ L_{C}, then L(f_{#}(γ)) > 3L_{r} and L(f_{#}^{2}(γ)) > 3L_{r}, and if L(γ) ≤ L_{r}, then L(f_{#}(γ)) < L_{C} and L(f_{#}^{2}(γ)) < L_{C}. We can easily compute a suitable value L_{C} given the train track map f. We say that a path γ in G_{r−1} is long if L(γ) ≥ L_{C}.

If H_{r} is an exponentially growing stratum, and ρ is a hallway of height r, then we need to develop an understanding of the lengths of components of ρ_{i} ∩ G_{r−1}, i.e., we need to study subpaths of slices in G_{r−1}. To this end, we consider a subpath γ ⊂ G_{r−1} of some slice ρ_{i} and analyze how it affects ρ_{i+1}. There are three possibilities:

• ρ_{i+1} contains f_{#}(γ) as a subpath, surrounded by edges in H_{r}.

• f_{#}(γ) cancels completely when f(ρ_{i}) is tightened to ρ_{i+1}.

• f_{#}(γ) partially cancels with a notch or with a path in f(H_{r}) ∩ G_{r−1}. This is what happens in Example 5.3.

Hence, as we trace images of subpaths in G_{r−1} through the slices of ρ, we see that they form (C + L_{r})-quasi-smooth hallways in G_{r−1}. If the initial slice of such a hallway is not contained in ρ_{0} or in a notch, then its length is bounded by L_{r}. If the last slice of such a hallway is not contained in ρ_{D(ρ)} or in a notch, then its length is also bounded by L_{r}.

We let M_{1} be the collection of smooth hallways in G_{r−1} obtained from ρ is this fashion, and we let M′_{2} be the collection of hallways in G_{r−1} that are not smooth. Let σ be an element of M′_{2}, and assume that there exists some 0 < i < D(σ) such that L(σ_{i}) < L_{C}. Then we obtain two new hallways σ′, σ′′ from σ by letting σ′_{j} = σ_{j} for 0 ≤ j ≤ i and σ′′_{j} = σ_{i+j} for 0 ≤ j ≤ D(σ) − i; we may think of this operation as cutting σ along σ_{i}. We obtain a collection of hallways M_{2} by performing all possible cuts of this kind on all elements of M′_{2}.

If σ ∈ M_{1} ∪ M_{2}, we say that σ intersects a slice ρ_{i} if one of the slices of σ is a subpath of ρ_{i}. When looking for bounds on the lengths of a slice ρ_{i}, we mostly need to find bounds on the lengths of slices of hallways σ that intersect ρ_{i}.

For some index r and constant C ≥ 0, we say that the map f satisfies Condition A_{r} if there exist computable constants K_{r}, K′_{r}(C), and an exponent d ≥ 1, such that the following two conditions hold:

• If ρ is a smooth hallway in G_{r} such that the slice ρ_{0} starts and ends at

fixed vertices, then

L(ρ_{i}) ≤ K_{r}V (ρ)

for all slices ρ_{i}.

• If ρ is a C-quasi-smooth hallway in G_{r}, then

L(ρ_{i}) ≤ K_{r}V (ρ) + K′_{r}(C)D^{d}(ρ).

If H_{r} is an exponentially growing stratum, then a hallway of height r is admissible if all its slices start and end at fixed vertices or at points in H_{r}.

Lemma 8.2. Let H_{r} be an exponentially growing stratum, and assume that Condition A_{r−1} holds. Then, given some C ≥ 0, there exists computable constants C_{1}, C_{2} ≥ 1 with the following property: If ρ is an admissible Cquasi-smooth hallway of height r,then

L(ρ_{i}) ≤ C_{1}V (ρ) + C_{2} ∑_{σ∈M_{2} σ intersects ρ_{i} in a long segment} D^{d}(σ)

for every slice ρ_{i} of ρ.

Proof. Since ρ is admissible, all slices of σ ∈ M_{1} start and end at fixed vertices unless σ_{0} is contain in a zero stratum, in which case all slices σ_{i} for i > 0 start and end at fixed vertices. Moreover, if σ_{0} is contained in a zero stratum, then L(σ_{1}) = L(σ_{0}). By Condition A_{r−1}, we have

L(σ_{i}) ≤ K_{r−1}V (σ)

for all slices σ_{i} of σ ∈ M_{1}.

Fix some slice ρ_{i} of ρ. Using Proposition 6.1 and Condition A_{r−1}, we see that

L(ρ_{i}) ≤ KV (ρ) + ∑_{σ∈M_{1} σ intersects ρ_{i}} K_{r−1}V (σ)

+ ∑_{σ∈M_{2} σ intersects ρ_{i}} (K_{r−1}V (σ) + K′_{r−1}(C + L_{r})D^{d}(σ)) .

Consider some σ ∈ M_{1} that intersects ρ_{i}. If the initial slice of σ is not visible in ρ, then, as we noted before, its length is bounded by L_{r}. Similarly, if the terminal slice of σ is not visible in ρ, then its length is also bounded by L_{r}. The number of elements of M_{1} that intersect ρ_{i} is bounded by KV (ρ). Putting it all together, we conclude that

∑_{σ∈M_{1} σ intersects ρ_{i}} V (σ) ≤ (2KL_{r} + 1)V (ρ).

Similarly, using the fact that elements of M_{2} are C + L_{r}-quasi-smooth, and that their initial and terminal slices are either visible in ρ or of length less than L_{C}, we see that

∑_{σ∈M_{2} σ intersects ρ_{i}} V (σ) ≤ (2KL_{C} + 1)V (ρ) + 2(C + L_{r}) ∑_{σ∈M_{2} σ intersects ρ_{i}} D(σ).

Since ρ_{i} contains at most KV (ρ) subpaths in G_{r−1}, the total contribution of subpaths in G_{r−1} that are not long is bounded by KL_{C}V (ρ). Letting C_{1} = K +2K_{r−1}(K(L_{C} +L_{r})+1)+KL_{C} and C_{2} = K′_{r−1}(C +L_{r})+2(C +L_{r}), we conclude that

L(ρ_{i}) ≤ C_{1}V (ρ) + C_{2} ∑_{σ∈M_{2} σ intersects ρ_{i} in a long segment} D^{d}(σ).

Lemma 8.2 shows that from now on, we may focus on the polynomial contribution of nonsmooth hallways in G_{r−1} that intersect a given slice ρ_{i} in a long subpath. In particular, if the initial slice ρ_{0} happens to be an r-legal path, then

L(ρ_{i}) ≤ C_{1}V (ρ)

for all slices ρ_{i} since M_{2} is empty in this case.

Lemma 8.3. Let H_{r} be an exponentially growing stratum, and assume that Condition A_{r−1} holds. Given some C > 0, there exist computable constants C_{1}, C_{2} with the following property: If ρ is an admissible C-quasi-smooth hallway of height r, such that for every slice ρ_{i} except possibly the last one, f_{#}(ρ_{i}) does not contain a legal segment of length at least L, then

L(ρ_{i}) ≤ C_{1}V (ρ) + C_{2}D^{d+1}(ρ)

for all slices ρ_{i}.

Proof. By Lemma 8.2, we may restrict our attention to elements of M_{2} that intersect a given slice ρ_{i} in a long subpath. Let

D = ∑_{σ∈M_{2} σ intersects ρ_{i} in a long segment} D^{d}(σ).

We first claim that the number of long subpaths in G_{r−1} in a slice ρ_{i} is bounded by N(ρ_{i}). By choice of L_{C}, a long legal subpath in G_{r−1} will not cancel completely when f(ρ_{i}) is tightened to f_{#}(ρ_{i}).

If there were two such subpaths in one legal segment of ρ_{i}, then there would be a legal segment in H_{r} in between. Since we assumed that L(f(E)∩ H_{r}) ≥ L for each edge in H_{r}, the r-length of the image of this legal segment is at least L, which means that the slice ρ_{i+1} contains a legal segment of length at least L, contradicting our assumption. This proves the claim if H_{r} does not support a closed Nielsen path, as in this case, the number of legal segments in ρ_{i} equals N(ρ_{i}).

If H_{r} supports a closed Nielsen path, then a legal segment of ρ_{i} that is adjacent to an illegal turn contained in a Nielsen subpath of ρ_{i} cannot contain a long subpath in G_{r−1}. If such a segment contained a long subpath in G_{r−1}, then f_{#}(ρ_{i}) would contain a legal segment of r-length L because both the initial and terminal partial edge of the Nielsen path of H_{r} map to legal segments of r-length at least L. This implies that the number of long subpaths in G_{r−1} is bounded by N(ρ_{i}).

Now, fix some slice ρ_{i}. We make the worst-case assumption that every legal segment of ρ that is not adjacent to an illegal turn contained in a Nielsen subpath contains a long subpath in G_{r−1} that is a slice of a hallway σ ∈ M_{2} of duration j ≥ i. The number of such hallways whose duration is a given number j ≥ i is bounded by N(ρ_{j}) + 1. We conclude that

D ≤ ∑_{j=i}^{D(ρ)} N(ρ_{j})j^{d}.

Choosing λ according to Lemma 4.4, we conclude that N(ρ_{i+1}) ≤ λ^{−1}N(ρ_{i})+ 1 + 2C, as ρ is C-quasi-smooth. This implies, inductively, that

N(ρ_{i}) ≤ λ^{−i}N(ρ_{0}) + 2(1 + C) ∑_{j=0}^{i−1} λ^{−j} ≤ λ^{−i}N(ρ_{0}) + \frac{λ}{λ − 1}(1 + 2C).

We choose some B ≥ ∑_{j=0}^{∞} λ^{−j}j^{d}, and we conclude that

D ≤ ∑_{j=0}^{D(ρ)} N(ρ_{j})j^{d} ≤ BV (ρ) + \frac{λ}{λ − 1}(1 + 2C)D^{d+1}(ρ),

since N(ρ_{0}) ≤ V (ρ).

If C′_{1}, C′_{2} are the constants from Lemma 8.2, then the lemma holds with C_{1} = C′_{1} + C′_{2}B and C_{2} = \frac{λ}{λ−1}(1 + 2C)C′_{2}.

Lemma 8.4. Let H_{r} be an exponentially growing stratum, and assume that Condition A_{r−1} holds. Let N_{0} be the constant from Lemma 4.4. There exist computable constants C_{1}, C_{2} with the following property: If ρ is an admissible smooth hallway for which a slice ρ_{i} does not contain any long legal segments unless N(ρ_{i−1}) < N_{0}, then

L(ρ_{i}) ≤ C_{1}V (ρ) + C_{2}D^{d+1}(ρ)

for all slices ρ_{i}.

Proof. If no slice of ρ contains a long legal segment, then the claim follows from Lemma 8.3. Otherwise, let i_{0} be the smallest index for which ρ_{i_{0}} contains a long legal segment. By choice of i_{0}, ρ_{i_{0}−1} does not contain a long legal segment, and by hypothesis, we have N(ρ_{i_{0}−1}) < N_{0}. If i < i_{0}, then, choosing D as in the proof of Lemma 8.3, we conclude that

D ≤ (∑_{j=0}^{i_{0}−1} N(ρ_{j})j^{d}) + N_{0}D^{d}(ρ)
≤ BV (ρ) + N_{0}D^{d+1}(ρ),

so that the lemma holds for all ρ_{i} with i < i_{0}.

For i ≥ i_{0}, ρ_{i} splits as a concatenation of long r-legal paths and subpaths that contain illegal turns and no long legal subpaths. Each slice may, conceivably, contain slices of N(ρ_{i_{0}−1}) < N_{0} hallways of duration D(ρ). The polynomial contribution of these hallways is bounded by N_{0}D^{d}(ρ).

In addition, the number of short legal segments around illegal turns is at most 2N_{0}. Each of them contains not more than one long subpath in G_{r−1}, belonging to a hallway of duration at most D(ρ) − i_{0}. The polynomial contribution of these paths is bounded by 2N_{0}(D(ρ) − i_{0})^{d}.

Now, since ρ_{i_{0}} contains a long legal segment, the length of ρ_{D(ρ)} = f_{#}^{D(ρ)−i_{0}}(ρ_{i_{0}}) is at least λ_{r}^{D(ρ)−i_{0}}. We can easily find some B′ > 0 such that B′λ_{r}^{k} ≥ 2N_{0}k^{d} for all k ≥ 0. We conclude that for the sum of all polynomial contributions in ρ_{i}, we have

2N_{0}(D(ρ) − i_{0})^{d} + N_{0}D^{d}(ρ) ≤ B′V (ρ) + N_{0}D^{d}(ρ),

which completes the proof of the lemma.

The remaining two lemmas deal with arbitrary smooth hallways of height r as well as quasi-smooth hallways by essentially decomposing them into pieces of the kind that we analyzed in the previous lemmas.

Lemma 8.5. Let H_{r} be an exponentially growing stratum, and assume that Condition A_{r−1} holds. Then there exist computable constants C_{1}, C_{2} with the following property: If ρ is an admissible smooth hallway of height r, then

L(ρ_{i}) ≤ C_{1}V (ρ) + C_{2}D^{d+1}(ρ)

for all slices ρ_{i}.

Proof. Let λ_{−}, N_{0} be the constants from Lemma 4.4. As in the proof of Lemma 8.1, we let λ = \sqrt{min\{λ_{−}, λ_{r}\}}, and we remark that for 0 ≤ j ≤ k, we have λ_{−}^{j} + λ_{r}^{k−j} ≥ λ^{k}. This basic estimate will be crucial in the proof of this lemma. We choose some B > 0 such that Bλ^{k} > k^{d+1} for all k ≥ 0.

Let C′_{1}, C′_{2} be the maximum of the corresponding constants from the previous lemmas. We will see that the lemma holds with C_{1} = C′_{1} + 3BC′_{2} and C_{2} = C′_{2}.

We first observe that if ρ satisfies the hypothesis of Lemma 8.4, then the lemma follows from Lemma 8.4. If ρ_{0} contains long legal segments, we can split ρ_{0} into long r-legal subpaths and neighborhoods of illegal turns (i.e., illegal turns surrounded by legal paths whose length is at most \frac{C_{r}}{2} ). Split ρ_{0} as ρ_{0} = α_{0;1}β_{0;1}α_{0;2} ⋯ α_{0;m}β_{0;m}, where all subpaths α_{0;i} are long legal segments, and all subpaths β_{0;i} are neighborhoods of illegal turns. Such a decomposition of ρ_{0} induces a decomposition of ρ into hallways, and we can choose the decomposition such that all resulting pieces are admissible, and that the legal segments are as long as possible, subject to admissibility. We write α_{j;i} = f_{#}^{j}(α_{0;i}) and β_{j;i} = f_{#}^{j}(β_{0;i}).

Let k = D(ρ). For each long legal subpath α_{0;i}, Lemma 8.2 yields that L(α_{j;i}) ≤ C_{1}(L(α_{0;i}) + L(α_{k;i})), for all 0 ≤ j ≤ k. Since α_{0;i} is a long legal segment, we have L(α_{k;i}) ≥ λ_{r}^{k} ≥ λ^{k}.

If the hallway defined by β_{0;i} satisfies the hypothesis of Lemma 8.4, then we have L(β_{j;i}) ≤ C′_{1}(L(β_{0;i}) + L(β_{k;i})) + C′_{2}k^{d+1}, and we have k^{d+1} ≤ BL(α_{k;i}), hence

L(β_{j;i}) ≤ C′_{1}(L(β_{0;i}) + L(β_{k;i})) + BC′_{2}L(α_{k;i}),

i.e., we can find a legal segment adjacent to β_{0;i} whose contribution to the visible edges of ρ dominates the possible polynomial contribution of β_{0;i}. This takes care of the long legal segments in ρ_{0} as well as the subpaths satisfying the hypothesis of Lemma 8.4. Hence, we only need to deal with those paths that do not satisfy the hypothesis of Lemma 8.4. Assume that for some 0 ≤ i ≤ m, β_{0;i} is one of them.

Then there exists some j_{0} such that β_{j_{0};i} contains a long legal segment, but β_{j_{0}−1;i} does not, and N(β_{j_{0}−1;i}) ≥ N_{0}.

As before, we split β_{j_{0};i} into long legal segments and neighborhoods of illegal turns, obtaining a decomposition β_{j_{0},i} = α_{j_{0};i,0}β_{j_{0};i,0} ⋯ α_{j_{0};i,m}β_{j_{0};i,m}, where α_{j_{0};i,k} are r-legal subpaths, and β_{j_{0};i,k} are neighborhoods of illegal turns. We can find splittings β_{j;i} = α_{j;i,0}β_{j;i,0} ⋯ α_{j;i,m}β_{j;i,m} for all 0 ≤ j ≤ k, such that f_{#}(α_{j;i,k}) = α_{j+1;i,k} and f_{#}(β_{j;i,k}) = β_{j+1;i,k}. We may choose those splitting such that the resulting pieces are admissible, and such that the legal segments α_{j_{0};i,k} are as long as possible, subject to admissibility.

Now, fix on one subpath α_{j_{0};i,k}. If N is the number of long subpaths in G_{r−1} in α_{j_{0};i,k}, then α_{j_{0}−1;i,k} contains at least N legal segments containing long subpaths in G_{r−1}. By Lemma 4.4, we have L(β_{0;i}) ≥ N(β_{j_{0};i}) ≥ λ_{−}^{j_{0}−1}N(β_{j_{0}−1;i}), so that we can find λ_{−}^{j_{0}−1}N illegal turns in β_{0;i}, and we can find λ_{r}^{k−j_{0}} edges in β_{k,i}. Using our earlier estimate, we see that (λ_{−}^{j_{0}−1} + λ_{r}^{k−j_{0}})N ≥ λ_{−}^{−1}λ^{k}N.

The polynomial contribution of the long subpaths in G_{r−1} of α_{j_{0};i,k} is bounded by K′_{r−1}(L_{r})Nk^{d+1} ≤ BK′_{r−1}(L_{r})Nλ^{k}, i.e., it is dominated by corresponding visible edges.

This leaves us to deal with the adjacent subpaths β_{j_{0};i,k} and β_{j_{0};i,k−1}. If β_{0;i,k} satisfies the hypothesis of Lemma 8.4, then its polynomial contribution is bounded by C′_{2}k^{d+1}, which in turn is bounded by BC′_{2}λ^{k}.

This takes care of the legal segments α_{j_{0};i,k} as well as those neighborhoods of illegal turns that satisfy the hypothesis of Lemma 8.4. We apply the previous reasoning to the remaining paths β_{j_{0};i,k}, completing the proof of the lemma.

Lemma 8.6. Let H_{r} be an exponentially growing stratum, and assume that Condition A_{r−1} holds. Given some C > 0, there exist computable constants C_{1}, C_{2} with the following property: If ρ is an admissible C-quasi-smooth hallway of height r, then

L(ρ_{i}) ≤ C_{1}V (ρ) + C_{2}D^{d+3}(ρ)

for all slices ρ_{i}.

Proof. The idea of this proof is to decompose the hallway ρ into pieces that are either smooth or C-quasi-smooth satisfying the hypothesis of Lemma 8.3.

In order to find this decomposition, we introduce trajectories of points in H_{r}. If p is a point in ρ_{i} ∩ H_{r}, we consider its image f(p) in f(ρ_{i}). We say that p survives if f(p) is contained in H_{r} and if f(p) is not contained in an edge that cancels when f(ρ_{i}) is tightened to f_{#}(ρ_{i}). If p survives, then f(p) is contained in ρ_{i+1}, or it is contained in the parts of f_{#}(ρ_{i}) that cancel when μ_{i+1}f_{#}(ρ_{i})ν_{i+1} is tightened to ρ_{i+1}.

Thinking of the hallway ρ as spanning a (possibly singular) disk, we draw a line segment (in this disk) from the surviving points in each slice to their images. If p is a point in a visible edge such that p and all its images survive, then p defines a line starting and ending in visible edges, called the trajectory of p. The trajectories of two points need not be disjoint, but that does not concern us here.

We say that two trajectories are parallel if their initial points are both contained in ρ_{0} or both contained in the same notch, and if their terminal points are both contained in ρ_{D(ρ)} or both contained in the same notch. The crucial observation is that equivalence classes of parallel trajectories are closed subsets of the disk spanned by ρ, so that in every equivalence class, we can find trajectories of two points p_{1}, p_{2} that are extremal in the following sense: If p is a point whose trajectory is parallel to those of p_{1} and p_{2}, then p is located between p_{1} and p_{2}.

We now cut ρ along the extremal trajectories of all equivalence classes of parallel trajectories, obtaining pieces that are either smooth or C-quasi-smooth. Moreover, all the resulting pieces are admissible. Let M_{1} be the collection of smooth pieces and M_{2} the collection of pieces that are not smooth. Note that V (M_{1}) + V (M_{2}) = V (ρ).

We now claim that all elements of M_{2} satisfy the hypothesis of Lemma 8.6. Suppose otherwise, i.e., there exists some σ ∈ M_{2} such that for some slice σ_{i}, f_{#}(σ_{i}) contains a legal segment of length at least L. Within the interior of this legal segment, we can find some point p such that all images of p survive in subsequent slices. Since p is the image of surviving points, we obtain a trajectory along which we can cut σ, contradicting the fact that we obtained σ by cutting ρ along extremal trajectories.

By Lemma 8.5, there are constants C′_{1}, C′_{2} such that for every σ ∈ M_{1} and every slice σ_{i} of σ, we have

L(σ_{i}) ≤ C′_{1}V (σ) + C′_{2}D^{d+1}(σ),

and by Lemma 8.6, there are constants C′′_{1}, C′′_{2} such that

L(σ_{i}) ≤ C′′_{1}V (σ) + C′′_{2}D^{d+1}(σ)

for every slice σ_{i} of every σ ∈ M_{2}.

There are at most 2(D(ρ)−1) notches, so that the number of equivalence classes of parallel trajectories is bounded by (2(D(ρ) − 1) + 1)^{2} (another extremely crude estimate, but it’ll do). Since we cut along no more than two trajectories per equivalence class, we obtain no more than 2(2D(ρ)−1)^{2}+1 ≤ 8D^{2}(ρ) pieces. Letting C_{1} = max{C′_{1}, C′′_{1}} and C_{2} = 8 max{C′_{1}, C′′_{2}}, we conclude that

L(ρ_{i}) ≤ C_{1}V (ρ) + C_{2}D^{d+3}(ρ)

for all slices of ρ.

We now have all the ingredients that we need to prove Theorem 2.1.

Proof of Theorem 2.1. We first show that Condition A_{r} holds for all strata H_{r}. This implies, in particular, that the second statement of Theorem 2.1 holds.

If the restriction of f to G_{r} is of polynomial growth, then Proposition 7.5 establishes Condition A_{r}. Now, assume that Condition A_{r−1} holds for some r. We want to prove Condition A_{r}.

If H_{r} is a polynomially growing stratum, then Condition A_{r−1} is precisely the inductive assumption that we used in the proof of Proposition 7.5, and we use the cutting and sawtooth constructions as before, completing the proof in this case.

Assume that H_{r} is an exponentially growing stratum, and let ρ be a smooth hallway of height r such that ρ_{0} starts and ends at fixed vertices. If ρ_{0} is a concatenation of Nielsen paths of height r and paths in G_{r−1}, then we can split ρ_{0} at the endpoints of its subpaths in G_{r−1}, and Condition A_{r−1} completes the proof. We now assume that ρ_{0} is not a concatenation of Nielsen paths and paths in G_{r−1}.

By Lemma 8.5, we have constants C_{1}, C_{2} such that

L(ρ_{i}) ≤ C_{1}V (ρ) + C_{2}D^{d+1}(ρ)

for all slices ρ_{i}. Moreover, by Lemma 8.1, there exists some C > 0 and λ > 1, independently of ρ, such that

V (ρ) ≥ Cλ^{D(ρ)}.

We can easily find some constant B such that BCλ^{k} ≥ C_{2}k^{d+1} for all k ≥ 0. Now the first part of Condition A_{r} follows, with K_{r} = C_{1} + B. Lemma 8.6 yields the second part of Condition A_{r}, so that Condition A_{r} holds.

Finally, in order to prove the first part of Theorem 2.1, we need to understand the dynamics of circuits. Let σ be a circuit of height r. If H_{r} is an polynomially growing stratum, then Remark 1.4 yields that σ splits, at fixed vertices, into basic paths of height r and paths in G_{r−1}, so that Condition A_{r} proves the claim.

Assume that H_{r} is an exponentially growing stratum. If σ is a concatenation of Nielsen paths of height r and paths in G_{r−1}, then we can split σ at the endpoints of its subpaths in G_{r−1}, so that Condition A_{r−1} completes the proof in this case. We now assume that σ is not a concatenation of Nielsen paths and subpaths in G_{r−1}. Then σ splits at a point p in H_{r}, so that we may interpret σ as a path starting and ending at v. Let ρ be a smooth hallway with ρ_{0} = σ. Then, by Lemma 8.5, we can find constants C_{1}, C_{2} such that

L(ρ_{i}) ≤ C_{1}V (ρ) + C_{2}D^{d}(ρ)

for all slices ρ_{i}. Moreover, by Lemma 8.1, we can find constants C, λ such that

V (ρ) ≥ Cλ^{D(ρ)}.

As before, we find some constant B such that BCλ^{k} ≥ C_{2}k^{d} for all k ≥ 0, so that the first statement of Theorem 2.1 holds with K_{r} = C_{1} + B. This completes the proof.

References

[BF92] M. Bestvina and M. Feighn. A combination theorem for negatively curved groups. J. Differential Geom., 35(1):85–101, 1992.

[BF96] Mladen Bestvina and Mark Feighn. Addendum and correction to: “A combination theorem for negatively curved groups” [J. Differential Geom. 35 (1992), no. 1, 85–101; MR 93d:53053]. J. Differential Geom., 43(4):783–788, 1996.

[BFH97] M. Bestvina, M. Feighn, and M. Handel. Laminations, trees, and irreducible automorphisms of free groups. Geom. Funct. Anal., 7(2):215–244, 1997.

[BFH98] M. Bestvina, M. Feighn, and M. Handel. The Tits alternative for Out(F_{n}) I: Dynamics of exponentially growing automorphisms. preprint, 1998.

[BG] Martin R. Bridson and Daniel P. Groves. The quadratic isoperimetric inequality for mapping tori of free group automorphisms I: Positive automorphisms.

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

[Bri00] P. Brinkmann. Hyperbolic automorphisms of free groups. Geom. Funct. Anal., 10(5):1071–1089, 2000.

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

[Gan59] F. R. Gantmacher. The theory of matrices. Vols. 1, 2. Chelsea Publishing Co., New York, 1959. Translated by K. A. Hirsch.

[Ger94] S. M. Gersten. The automorphism group of a free group is not a CAT(0) group. Proc. Amer. Math. Soc., 121(4):999–1002, 1994.

[Mac00] N. Macura. Quadratic isoperimetric inequality for mapping tori of polynomially growing automorphisms of free groups. Geom. Funct. Anal., 10(4):874–901, 2000.

273 Altgeld Hall 1409 W. Green St. Urbana, IL 61801 U.S.A.

E-mail: brinkman@math.uiuc.edu