{'fraction_non_alphanumeric': 0.06109500933021003, 'fraction_numerical': 0.00943343788462302, 'mean_word_length': 3.5683607211521022, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 53, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The dynamics and geometry of free group endomorphisms

We prove that ascending HNN extensions of free groups are word-hyperbolic if and only if they have no Baumslag-Solitar subgroups. This extends the theorem of Brinkmann that free-by-cyclic groups are word-hyperbolic if and only if they have no free abelian subgroups of rank 2. The paper is split into two independent parts: 1) We study the dynamics of injective nonsurjective endomorphisms of free groups. We prove a canonical structure theorem that initializes the development of improved relative train tracks for endomorphisms; this structure theorem is of independent interest since it makes many open questions about injective endomorphisms tractable. 2) As an application of the structure theorem, we are able to (relatively) combine Brinkmann's theorem with our previous work and obtain the main result stated above. In the final section, we further extend the result to HNN extensions of free groups over free factors.

The HNN extension has the presentation F * A = F, t | t −1 at = φ(a), ∀a ∈ A . If A = F = φ(A), then F * A = F φ Z is a free-by-cyclic group and this case was proven by Peter Brinkmann. Our proof of the main theorem above uses Brinkmann's result. If A = F = φ(A), then F * A = F * φ is a strictly ascending HNN extension and coarse hyperbolization for this class of groups was our original motivation. Finally, when A = F , we more or less reduce this to the case A = F .
The case A = F of the main theorem (Theorem 6.7) proved to be difficult since it required an understanding of the dynamics of injective nonsurjective endomorphisms of free groups and no such complete study had been carried out yet. Patrick Reynolds studied the dynamics of irreducible nonsurjective endomorphisms of free groups [27] and we previously used this work to prove an instance of the main theorem where φ : F → F is irreducible but not surjective [23,24]. In this case, we showed that the strictly ascending HNN extension F * φ is always word-hyperbolic. Unfortunately, it remained unclear how Reynolds' work could be generalized to all injective nonsurjective endomorphisms and no further progress on the problem had been made.
The first part of this paper (Sections 1-4) is a self-contained systematic study of all injective nonsurjective endomorphisms of free groups and is the main novel contribution of the paper. We hereby present a summary of the important results from these sections. Note that the statements given here are not the complete statements of the cited results.
Summary. If φ : F → F is injective but not surjective, then there is: The free factor systems A and A * could be trivial.
This means any injective nonsurjective endomorphism φ : F → F is induced by a graph map f : Γ → Γ such that: 1) some possibly empty or disconnected proper subgraph Γ ⊂ Γ is f -invariant and the restriction of f to Γ is a homotopy equivalence; 2) some f -invariant proper subgraph Γ ⊃ Γ has an f n -image contained in Γ for some n ≥ 1; and 2 3) collapsing the lifts of the subgraph Γ in the universal coverΓ induces an expanding immersionf : T → T on a simplicial F -tree. In particular, if Γ is empty, then f is an expanding graph immersion.
In our previous work [23], we extended a result of Ilya Kapovich [17] and proved the special case of the main theorem with A = F and φ : F → F induced by an expanding graph immersion. The expanding immersion was crucial to the proof and so we developed expanding relative immersions with the intent of, in a sense, relativizing our previous proof and extending it to all injective nonsurjective endomorphisms. This application of the structure theorem is carried out in the second part of the paper (Sections 5-7).
Expanding relative immersions are interesting in their own right as they can potentially be applied to many currently open problems about nonsurjective endomorphisms. To name a few: relative immersions may be needed to extend Hagen-Wise's cubulation of wordhyperbolic free-by-cyclic groups [16,15] to the groups F * A ; we suspect that they could be used to extend the main theorem to a characterization of the possible Dehn/isoperimetric functions of the groups F * A following work by Bridson-Groves [7] (See also Problem 2); they provide a framework for generalizing Bestvina-Feighn-Handel's construction of improved relative train tracks for automorphisms [5], which were used in Brinkmann's, Hagen-Wise's, and Bridson-Groves' results; for a different direction of generalization, the main theorem may be extended to HNN extensions G * A of torsion-free word-hyperbolic groups G over free factors A ≤ G; and finally, the virtual fibering question is a particularly interesting problem that was first posed to us by Dawid Kielak and our structure theorem along with the cubulation problem could be significant steps towards its resolution: Question (Virtual fibering). Suppose φ : F → F is injective but not surjective. If F * φ is word-hyperbolic, then does it have a free-by-cyclic finite index subgroup? What if it has a quadratic Dehn function? Besides Section 7, the results in this paper were the author's doctoral thesis. With future applications of the structure theorem in mind, we have chosen to emphasize in this paper the independence of the "theory" (first part) and "application" (second part). The two parts can be read independently. If you choose to skip the first part, then we encourage you to read the prologue and interlude; these optional sections contain several examples that capture the key points. The main results of the first part are summarized again in the interlude with a bit more detail since we are assuming you will, by then, be familiar with the terms defined in the definitions and conventions section. The summary is all you will need to use expanding relative immersions in your own work. The epilogue is a brief discussion of some questions about endomorphisms in the context of expanding relative immersions.
The main tools used in the first part are Bass-Serre theory, Stallings graphs, bounded cancellation, and train track theory. The second part uses some Bass-Serre theory and the Bestvina-Feighn combination theorem.

Prologue
We will start with a few motivating examples to illustrate the main construction of the first part of this paper. Let F = F (a, b) be the free group on two generators and φ, ϕ, ψ : F → F be injective nonsurjective endomorphisms given by φ : (a, b) → (ab, ba), ϕ : (a, b) → (a, bab −1 ), and ψ : (a, b) → (a, abab).
The standard rose is a rose R with two petals and an identification F = π 1 (R) such that the basis {a, b} corresponds to the petals; it will be graphically represented by a rose with two oriented petals labelled by a and b respectively.
For each integer k ≥ 1, letR k be the cover of R corresponding to the subgroup φ k (F ), i.e., it is the quotient of the universal coverR by the action of the subgroup φ k (F ). The Stallings graph S(φ k (F )) is the core ofR k , i.e., the smallest connected subgraph ofR k with rank 2. Alternatively, we can defineR(φ k (F )) ⊂R to be the smallest subtree invariant a b Figure 1: The standard rose.
under the φ k (F )-action and S(φ k (F )) to be the quotient φ k (F )\R(φ k (F )). Evidently, there is a natural isomorphism φ k (F ) ∼ = π 1 (S(φ k (F ))). A Stallings graph S is graphically represented as an R-digraph, i.e., S will be an oriented graph whose oriented edges are labelled by a or b as shown in Figure 2.
The Stallings graphs S(φ k (F )) are roses for all k ≥ 1 and each petal doubles in size with each iteration. Since φ is injective, it is an isomorphism onto its image. In particular, we may use φ to get an isomorphism F ∼ = φ k (F ) ∼ = π 1 (S(φ k (F ))) for k ≥ 1. Under this isomorphism, the basis {a, b} corresponds to the petals of S(φ k (F )) and we recover the standard rose for all k ≥ 1. This is equivalent to the existence of an immersion (locally injective map) on the rose f : R → R such that π 1 (f ) = φ [24, Lemma 3.2]. Indeed, the obvious map f : R → R that maps the a-petal to the path ab and the b-petal to the path ba is an immersion. The petals of S(φ k (F )) doubling in size with each iteration implies f is in fact an expanding immersion, i.e., all edges expand under f -iteration.
The Stallings graphs S(ϕ k (F )) are barbells for all k ≥ 1, the middle bars roughly double in size with each iteration, and the plates are labelled by a (See Figure 3). Under the isomorphism F ∼ = ϕ k (F ) ∼ = π 1 (S(ϕ k (F ))), the conjugacy classes {[a], [b]} correspond to the two plates of the barbell S(ϕ k (F )) and we recover the so called standard barbell for all k ≥ 1. Just as in the first example, this is equivalent to the existence of an immersion on the barbell g : B → B such that π 1 (g) = ϕ under some identification F = π 1 (B). However, the immersion is not expanding since the plates are not growing in size with each iteration.
What we are now about to do will be the crux of the first part of the paper. Since the (nongrowing) plates of S(ϕ k (F )) are all labelled a, we deduce that a is a free factor fixed by ϕ and b is mapped to a conjugate of a . Thus, { a , b } forms an invariant free factor system that contains a fixed free factor. Now considerg :B →B to be the lift of g S(ϕ(F )) S(ϕ 2 (F )) S(ϕ 3 (F )) Figure 3: Stallings graphs S(ϕ k (F )) for k = 1, 2, 3.
to the universal coverB. Collapsing all translates of axes of a and b inB, i.e., collapsing all edges ofB labelled by the plates of B, will produce a so-called (F, { a , b })-tree T with a nonfree F -action andg induces an expanding immersionḡ : T → T where each edge doubles in size underḡ-iteration. The mapḡ will be referred to as a relative immersion.
For the final example, the Stallings graphs S(ψ k (F )) are roses again where one petal roughly doubles in size with each iteration and another is labelled by a (See Figure 4). Unlike the first example, the roses with the isomorphisms F ∼ = ψ k (F ) ∼ = π 1 (S(ψ k (F ))) are not standard roses since b does not correspond to a petal for k ≥ 1. In fact, applying ψ to the labels of S(ψ k (F )) forces a full fold with one petal to get S(ψ k+1 (F )) which means the Stallings graphs are all distinct marked roses. In particular, ψ cannot be induced by a graph immersion! But the observation that the nongrowing petals of S(ψ k (F )) are all labelled by a implies a is a fixed free factor. Despite ψ not being induced by an immersion, the obvious map on the standard rose h : R → R will induce an expanding immersionh : Y → Y on an (F, { a })-tree Y where every edge doubles in size.
The main result of the first part of this paper is that this construction always produces expanding relative immersions, Theorem 4.5: any injective nonsurjective endomorphism of a free group is induced by a graph map f : Γ → Γ such that collapsing the translates of axes inΓ of some canonical invariant free factor system containing a fixed free factor system will induce an expanding relative immersionf : T → T . This can be summarized into two steps: first establishing the existence of a unique (possibly trivial) maximal fixed free factor system (Section 2); then showing that collapsing this free factor system and its preimages in the universal cover of an appropriately chosen graph Γ will produce a tree T on which we can define an expanding relative immersion (Section 4). The two guiding principles will be bounded cancellation (Lemmas 1.4 & 3.1) and the fact that Stallings graphs for iterated injective nonsurjective endomorphisms have unbounded size (Lemma 1.1 & Proposition 3.9).

Definitions and conventions
F will always be a free group with finite rank at least 2. A nontrivial subgroup system of F is a nonempty finite collection of nontrivial subgroups A = {A 1 , . . . , A l } of F . A nontrivial free factor system of F is a nonempty collection of nontrivial free factors A = {A 1 , . . . , A l } of F such that A i ∩ A j is trivial if i = j and A 1 , . . . , A l is free factor of F . We define the trivial system to be the collection consisting of the trivial subgroup; this will allow us to treat absolute and relative cases simultaneously in our proofs. For any subgroup system A, the subgroups A i ∈ A are called the components of A or Acomponents. A subgroup system A is finitely generated if its components are finitely generated. A free factor system A is proper if some component is proper, i.e., A = {F }. Let A and B be subgroup systems of F . We shall say A carries B if for every component B ∈ B, there is a component A ∈ A and element x ∈ F such that B ≤ xAx −1 and, when A and B are free factor systems, we shall denoted it by B A. For a conjugacy class of elements [g] in F , we shall also say A carries [g] if there is a component A ∈ A and element x ∈ F such that g ∈ xAx −1 . If A = {A} (or B = {B}) is a singleton, then we will write, "A carries [g] / B (or B)." One can easily verify that the -relation on free factor systems is a preorder, i.e., it is reflexive and transitive. So it determines an equivalence relation on the set of free factor systems and a partial order on the set of equivalence classes. Free factor systems will always be considered up to this equivalence relation. In particular, we can replace components in a system with conjugates whenever convenient.
Remark. Suppose F = a, b be the free group of rank 2. With our definition, { a , b } and { bab −1 , (ba)b(ba) −1 } are equivalent free factor systems but { a , (ba)b(ba) −1 } is not a free factor system. Thus, when we replace components in a free factor system with conjugates, we need to ensure the resulting subgroup system is still a free factor system.
Outer endomorphisms of F are the equivalence classes on the set of endomorphisms of F . For instance, properties such as being irreducible are not just properties of an endomorphism φ but also its outer class [φ].
Let φ : F → F be an endomorphism. We say a subgroup system subgroups are permuted up to conjugacy, i.e., σ is a permutation and [φ(A i )] = [A σ(i) ] for all i. When φ is an automorphism, all [φ]-invariant free factor systems are [φ]-fixed. When φ is injective, then, for any k ≥ 1 and free factor system A of F , φ k (A) is a free factor system of φ k (F ); conversely, any free factor system of φ k (F ) gives us a free factor system of F via the isomorphism φ k : F → φ k (F ). Finally, note that when A is a [φ]-fixed free factor system but φ is not surjective, φ k (A) will typically not be a free factor system of F (See the remark above) The endomorphism φ is reducible if it has a nontrivial proper invariant free factor system and irreducible otherwise. One immediate consequence of Stallings folds [29] is the injectivity of irreducible endomorphisms (Observation below). So we can drop the injectivity hypothesis when specializing results to the irreducible case.
For the topological perspective, graphs are 1-dimensional CW-complexes and a graph map f : X → X will be a continuous map of graphs that sends vertices to vertices and any edge to a vertex or immersed path. An edge e of X is pretrivial if f (e) is a vertex. For a graph map f : Γ → Γ of finite graphs, let K be the maximum of the (combinatorial) length of the edge-path f (e) as e varies over all the edges of Γ. Then f is K-Lipschitz, a fact that will be used throughout the paper. Generally, K(f ) will denote some convenient Lipschitz constant for f rather than the infimum. For the moment, X is used for arbitrary graphs but, for most of the paper, Γ will be used for finite connected noncontractible graphs and T for infinite simply-connected graphs (simplicial trees). A core graph is a graph with no proper deformation retract.
A direction at a vertex v ∈ X is a half-edge attached to the vertex. A vertex is bivalent if it has exactly two directions. The set of directions at vertex v is denoted by T v X. branch points are vertices with at least three directions and natural edges are maximal edge-paths whose interior vertices are bivalent. We will say a graph map is natural if it maps branch points to branch points and any natural edge to a branch point or immersed path. If the graph map f : X → X has no pretrivial edges, then the restriction to initial segments induces the derivative map at v, df v : The graph map f is an immersion if it is locally injective, i.e., it has no pretrivial edges and the derivative maps df v are injective for all vertices v; note that immersions are natural. An immersion f is expanding if the length of f n (e) is unbounded as n → ∞ for every edge e of X.
With immersions defined, we preface the observation with a summary of Stallings' folding theorem. Let R be a rose whose edges are indexed by a basis {a 1 , . . . , a n } of F and let f : R → R be the map where f (a i ) is the immersed edge-path in R labelled by φ(a i ). Stallings [29] showed that f factors as ι • f l • · · · • f 1 where each f i is a fold and ι is an immersion. We will use this factorization again to prove bounded cancellation in Lemma 1.4 and Proposition 3.1.
Proof. If φ is not injective, then at least one of the folds in Stallings' factorization of φ collapses a subgraph of the domain. In particular, the kernel of φ contains a proper free factor A ≤ F ; therefore, φ(A) = {1} ≤ A and [φ] is reducible.
Let A = {A 1 , . . . , A l } be a nontrivial subgroup system of F , then an A-marked graph (Γ * , α * ) is a collection of graphs Γ * = {Γ 1 , . . . , Γ l } where the finite connected core graphs Γ i are indexed by markings, i.e., isomorphisms α i : A i → π 1 (Γ i ). When A = {A} is a singleton, we may write A-marked graph in place of A-marked graph. A marked graph (Γ, α) is an F -marked graph. For any marked graph (Γ, α) and any conjugacy class of a nontrivial element g ∈ F , denoted by [g], we define its length with respect to α, g α , to be the (combinatorial) length of the immersed loop in Γ representing [g].
More generally, we want to consider pairs A B of free factor systems of F . For each component B i ∈ B, let A i be either the nonempty maximal subset of A carried by B i or the trivial system if no such subset exists. Typically, we shall replace components of A with conjugates so that A is also a free factor system of B, i.e., each A i is a free factor system of B i (next remark below). A (B, A)-forest T * is a simplicial forest of (B i , A i )-trees T i , i.e., a collection of simplicial trees T * = {T 1 , . . . , T k } where each tree T i is equipped with a minimal simplicial B i -action whose edge stabilizers are trivial and point stabilizers are trivial or conjugates (in B i ) of A i -components. We note that a (B, {B})-tree is a point also known as a degenerate tree.
When A is the trivial system, an (F, A)-tree is a free minimal F -tree T . In that case, the quotient F \T is a marked graph. When A is a nontrivial proper free factor system, the quotient of an (F, A)-tree is a graph of groups decomposition of F with trivial edge groups and A as the nontrivial vertex groups [28]; such decompositions are sometimes known as free splittings of F and they will be our relative analogues for marked graphs. Any given (F, A)-tree endowed with the combinatorial metric has an associated length function l T : F → R. Precisely, any isometry of a simplicial tree is either elliptic (fixes a point) or loxodromic (preserves an axis of least displacement). If g ∈ F is elliptic, then l T (g) = 0; otherwise, l T (g) > 0 is the translation distance of g acting on its axis. When A is trivial and F \T is the marked graph (Γ, α), then l T (·) = · α as functions F → R. The minimal subtree T (H) ⊂ T of a nontrivial subgroup H ≤ F is the smallest subtree with a minimal induced H-action, i.e., the union of all fixed points and axes of nontrivial elements in H.
Remark. Let A B be free factor systems of F , B i ∈ B be a free factor with nontrivial A i , and T be an (F, A)-tree. Choose a connected fundamental domain of B i acting on T (B i ) and the nontrivial stabilizers in B i of vertices in the domain form a free factor system A i of B i . Then A i and A i are equivalent as free factor systems of F since A i {B i }.
Suppose ψ : F → F is an injective homomorphism. Then it determines a contravariant preimage function ψ −1 from the poset of free factor systems of F to the poset of free factor systems of F . One way to define this function is through trees. Let A be a free factor system of F , T be any (F , A )-tree, and T (ψ(F )) ⊂ T be the minimal subtree of ψ(F ) ≤ F . In particular, the quotient ψ(F )\T (ψ(F )) is a free splitting of ψ(F ) whose nontrivial vertex groups form a nontrivial free factor system A of ψ(F ). If T (ψ(F )) has a free ψ(F )-action, then this condition is independent of the choice of (F , A )-tree T and we set ψ −1 · A to be the trivial system. Otherwise, we have a nontrivial free factor system A of ψ(F ) and a corresponding nontrivial free factor system of F via the isomorphism ψ : F → ψ(F ); the equivalence class of the latter free factor system is independent of the (F , A )-tree T and we will denote it by ψ −1 · A .
Let T and T be (F, A)-and (F , A )-trees respectively and ψ : F → F be an injective homomorphism such that A carries ψ(A) or, equivalently, ψ −1 · A A. This carrying condition ensures that elliptic elements in F (with respect to T ) have elliptic ψ-images (with respect to T ). A tree map f : for all g ∈ F and x ∈ T . If we require ψ −1 · A = A, then loxodromic elements in F have loxodromic ψ-images; this is the relative analogue of a π 1 -injective graph map.
Suppose A is a nontrivial [φ]-invariant free factor system of F for some injective endomorphism φ : F → F ; so there is a function σ : {1, . . . , l} → {1, . . . , l} and inner automorphisms i A natural representative is a weak representative that is also natural. A topological representative is a weak representative that has no pretrivial edges and whose underlying graph Γ * has no bivalent vertices.
. An A-relative natural representative is an A-relative weak representative that is also natural. An A-relative representative is an A-relative weak representative with no pretrivial edges and whose underlying forest has no bivalent vertices. A relative representative is minimal if it has no orbit-closed invariant subforests whose components are bounded. An (expanding resp.) A-relative immersion for φ| B is an A-relative representative for φ| B that is also an (expanding resp.) immersion.
In the first part of the paper, we show that any injective endomorphism of F has a canonical invariant free factor system A and an expanding A-relative immersion f such that A is eventually mapped into a canonical fixed free factor system. In the second part of the paper, we use the canonical systems and the expanding relative immersion to prove the main theorem.
Dynamics of free group endomorphisms 1

Stallings graphs and bounded cancellation
Let (Γ, α) be a marked graph with no bivalent vertices. For any nontrivial subgroup system H of F , the Stallings (subgroup) graph for H with respect to a marked graph (Γ, α) with is the smallest H-marked graph (S(H), β * ) along with an immersion ι * : i.e., the smallest deformation retract ofΓ H i , and ι i is the restriction to S(H i ) of the covering mapΓ H i → Γ. We may sometimes refer to the marked graph (Γ, α) as the ambient graph. In the notation, the marking and immersion for Stallings graphs will usually be omitted. H is finitely generated. Suppose φ : F → F is injective, A is a nontrivial free factor system of F . We will be studying the (iterated) Stallings graphs (S[φ k (A)], β * ,k ) for k ≥ 1.
Remark. For any free factor system F of F and nontrivial subgroup system H carried by F, we can similarly define the Stallings graph for H with respect to F-marked graphs (Γ * , α * ). If φ * : F → F is an injective endomorphism, i.e., a collection of injective endomorphism {φ i : F i → F σ(i) } that need not be a restriction of an endomorphism of F , then we can still consider the Stallings graphs S[φ k * (A)] for k ≥ 1 and A F. The point of this remark is that the results of this paper hold when φ : F → F is replaced with φ * : F → F. In other words, the ambient graph Γ need not be connected for our results.
Unlike the ambient graph Γ, we allow Stallings graphs S = S[H] to have bivalent vertices. More precisely, we subdivide S so that the immersion ι * : S → Γ is simplicial, i.e., maps edges to edges. With this subdivision, we get a combinatorial metric on (S, β * ) that is compatible with (Γ, α), i.e., for any nontrivial element g in H i , g α = g β i . This lemma will be invoked on invariant free factor systems containing a component that is not eventually [φ]-periodic. Conversely, the next lemma handles the case when an invariant free factor system consists entirely of eventually periodic free factors. The following fact will be used again in the proof of Proposition 2.4. Proof. By Marshall Hall's theorem, free groups are subgroup separable/locally extended residual finiteness (LERF), i.e., for any finitely generated subgroup H ≤ F and element g ∈ F \ H, there is a finite group G and a surjective homomorphism ϕ : F → G such that ϕ(g) / ∈ ϕ(H). See [29] for a proof due to Stallings. For a contradiction, suppose there is an element y ∈ F such that yHy −1 ≤ H and g ∈ H \ yHy −1 . By subgroup separability, there is a finite group G and homomorphism ϕ : F → G such that ϕ(g) / ∈ ϕ(yHy −1 ). But g ∈ H implies ϕ(g) ∈ ϕ(H) and, by finiteness of G, yHy −1 ≤ H implies ϕ(yHy −1 ) = ϕ(H) -a contradiction.
The next lemma, also known as the Bounded Cancellation Lemma, will be used extensively in this paper. At the risk of overloading notation, for an edge-path p in a graph Γ, [p] denotes the immersed edge-path that is homotopic to p rel. endpoints; for a loop ρ in Γ, [ρ] will be the immersed loop that is freely homotopic to ρ. Lemma 1.4 (Bounded Cancellation). Let g : Γ → Γ be a π 1 -injective graph map. Then there is a constant C(g) such that, for any natural edge-path decomposition p 1 · p 2 of an immersed path in the universal coverΓ, the edge-path [g( The following proof is due to Bestvina-Feighn-Handel [4, Lemma 3.1]. Proof. Any graph map g : Γ → Γ factors as a pretrivial edge collapse and edge subdivision g 0 , a composition of r ≥ 0 folds g r •· · ·•g 1 , and an simplicial immersion g r+1 . The collapse, subdivision, and immersion have cancellation constants 0 while each fold has cancellation constant 1 by π 1 -injectivity. Thus we may choose C(g) = r.
Let f : Γ → Γ be a topological representative for an injective endomorphism φ : F → F , A be a nontrivial [φ]-invariant free factor system of F , andΓ k be the disjoint union of covers of Γ corresponding to φ k (A) for some k ≥ 1. Then f lifts to a mapf k :Γ k →Γ k and the deformation retractionΓ k → S[φ k (A)] induces a mapf k : with K(f k ) = K(f ) and C(f k ) = C(f ). We shall callf k the (k-th) homotopy lift of f .
Stallings graphs S[φ k (A)] are φ k (A)-marked graphs by definition and the mapsf k are weak representatives for [ φ| φ k (A) ] that might map branch points to bivalent vertices. Note that injectivity of φ allows us to also consider the graphs as A-marked graphs andf k as weak representatives for [ φ| A ]. We hope to replace the weak representativesf k with homotopic natural representatives while maintaining uniform control on the Lipschitz and cancellation constants. The next lemma allows us to measure how close the homotopy lift f k is to mapping branch points to branch points. Lemma 1.5. Suppose g : Γ → Γ be a π 1 -injective graph map with cancellation constant C = C(g). Then g maps branch points to the C-neighborhood of branch points.
Proof. Set C = C(g). If Γ is the C-neighborhood of its branch points, then there is nothing to prove. Suppose ν ∈ Γ is a bivalent vertex whose distance to the nearest branch point is greater than C. We need to show that ν is not the g-image of any branch point. Set 1 and 2 to be the distinct oriented directions originating from ν and¯ 1 ,¯ 2 are the same directions with opposite orientation.
Let v ∈ Γ be a branch point and g(v) = ν. As v is a branch point, there are at least three distinct oriented directions originating from v: e 1 , e 2 , and e 3 . Let p 12 be an immersed path that starts and ends with e 1 andē 2 respectively and define p 23 similarly. Set p 13 = [p 12 · p 23 ] and p 13 = p 12 ·p 23 , wherep 23 is the reversal of the path p 23 . See Figure 5 for an illustration. Although the paths are loops, we still treat them as paths, i.e., tightening is done rel. the endpoints. Without loss of generality, assume [g(p 12 )] starts with 1 . If [g(p 12 )] ends with¯ 1 , then [g(p 12 )] = µ 1 · ρ ·μ 1 , where µ 1 is an extension of 1 to an embedded path from ν to a branch point and ρ is an immersed nontrivial loop. By hypothesis, µ 1 is longer than C. Since p 12 starts and ends with e 1 andē 2 respectively, the concatenation p 12 · p 12 is an immersed path such that [g(p 12 )] · [g(p 12 )] hasμ 1 · µ 1 as a subpath, violating bounded cancellation. So we may assume [g(p 12 )] starts and ends with 1 and¯ 2 .
If [g(p 23 )] starts and ends with 2 and¯ 1 , then [g(p 13 )] = [g(p 12 ) · g(p 23 )] starts and ends with 1 and¯ 1 respectively, which violates bounded cancellation for the same reason given in the previous paragraph. Similarly, if [g(p 23 )] starts and ends with 1 and¯ 2 , we rule out this possibility by considering [g(p 13 )]. We have ruled out all cases, and therefore, no branch point v of Γ is mapped to ν. Corollary 1.6. Let g : Γ → Γ be a K-Lipschitz π 1 -injective graph map with cancellation constant C. Then g is homotopic to a (K+C)-Lipschitz natural graph map with cancellation constant 2C.
Proof. By Lemma 1.5, g maps branch points to the C-neighborhood of branch points. So we can find a graph map g homotopic to g that maps branch points to branch points. Since the homotopy is moving images of branch points a distance at most C, we can use K(g ) = K + C and C(g ) = 2C.
The bounded cancellation lemma only considers natural edge-paths, so homotopies that are supported in the interior of natural edges will not affect the cancellation constant. Using a tightening homotopy supported in the interior of natural edges in Γ, we may assume g is a natural graph map. The homotopy will not affect the Lipschitz and cancellation constants.
So we can replace the homotopy liftf k with a homotopic natural representative that has Lipschitz and cancellation constants K(f ) + C(f ) and 2C(f ) respectively. One would usually collapse the pretrivial edges and forget bivalent vertices to get a topological representative but we will not since we want to preserve compatibility: · β * is the restriction of · α to φ k (A). To summarize the properties of homotopy lifts that will be used in the next sections: with Lipschitz and cancellation constants K(f k ) = K(f ) + C(f ) and C(f k ) = 2C(f ) respectively.
The crucial point is that the Lipschitz and cancellation constants are independent of k.

Canonical and elliptic free factor systems
In this section, we will construct a canonical invariant free factor system for any given injective endomorphism of F . This free factor system, called the elliptic free factor system, is crucial for the construction of (expanding) relative immersions later in the paper.
Suppose A is a free factor system and φ : F → F is an injective endomorphism. We shall say that a conjugacy class [g]  Proof. Let φ : F → F be an injective endomorphism. The forward direction is obvious: if [φ] has a nontrivial fixed free factor system A, then any nontrivial conjugacy class [g] carried by A has an infinite [φ]-tail. The main content of the theorem is in the reverse direction. Fix a nontrivial conjugacy class [g] in F with an infinite [φ]-tail. We proceed by descending down the poset of free factor systems. The following claim is the key idea: Since there are no infinite chains in the poset of free factor systems, the descent (proven below) starts with the free factor system {F } and then finds a [φ]-invariant free factor sytem A that carries an infinite [φ]-tail of [g] and whose free factors are eventually [φ]-periodic; such a free factor system contains a nontrivial [φ]-fixed free factor system by Lemma 1.2 and we are done.
Note that the assumption "D contains a free factor that is not eventually [φ]-periodic" in the descent claim is more general than we really need for our conclusion. We could have worked with a more natural assumption "D has no periodic free factors" and reached the same conclusion. However, we give the general argument instead since we will invoke a variation of it in the next proposition.
Proof of descent. Let (Γ, α) be a marked graph, f : Γ → Γ be a topological representative for [φ], and set K = K(f ) + C(f ) and C = 2C(f ). Suppose D is a [φ]-invariant free factor system that carries an infinite [φ]-tail [g n ] n≥1 of [g] and contains a free factor that is not eventually [φ]-periodic. Then, for all k ≥ 1 and n ≥ k, there is an immersed loop ρ k (g n ) in ∆ k = S[φ k (D)] corresponding to [φ k (g n )], where ∆ k = S[φ k (D)] is the Stallings graph with respect to (Γ, α). Set L = max{ g α , C}.
For all k ≥ 1, letf k : ∆ k → ∆ k be the natural representatives for [ φ| φ k (D) ] given by Proposition 1.7. In particular, these representatives have Lipschitz and cancellation constants K and C respectively. As [g n ] n≥1 is an infinite [φ]-tail of [g] carried by D, we get, for any fixed k ≥ 1, an infinite sequence of immersed loops (ρ k (g n )) n≥k in ∆ k such that the free homotopy classes off n−k k (ρ k (g n )) have length g α for all n ≥ k. Form a directed graph G k whose vertices are the natural edges of ∆ k and there is a directed edge E i → E j iff k maps natural edge E i over E j . Note that the number of natural edges of ∆ k is at most N = 3 · rank(F ) − 3 and so G k has at most N vertices.
Since D contains a free factor that is not eventually [φ]-periodic, the length of natural edges in ∆ k is unbounded as k → ∞ by Lemma 1.1. Fix k 0 such that the longest natural edge in ∆ k is longer than L · K N −1 . Let L 0 be the natural edges of ∆ k longer than L · K N −1 and L be the union of L 0 and all natural edges on a directed path to L 0 in G k . Sincef k is K-Lipschitz and the shortest directed path in G k from a natural edge in L to L 0 has at most N natural edges on it, every natural edge in L is longer than L. The natural edges in L will be referred to as the long natural edges and the remaining natural edges as short.
Set ∆ ⊂ ∆ k to be the union of short natural edges, which will be a proper subgraph since long natural edges exist. The subgraph is automaticallyf k -invariant by the construction of L. Since ρ k (g k ) is an immersed loop in ∆ k with length g α ≤ L, its natural edges are short and ∆ is a nonempty, noncontractible proper subgraph of ∆ k . Therefore, ∆ determines a nontrivial [φ]-invariant proper free factor system D ≺ D. Technically, it determines an invariant free factor system of φ k (F ) but, as φ is injective, this corresponds to an invariant free factor system of F . It remains to show that D carries an infinite [φ]-tail of [g].
Let L ⊂ G k be the full subgraph generated by the long natural edges L. If there are no directed cycles in L, thenf N k (∆ k ) ⊂ ∆ ; in this case, the sequence of nontrivial loops carried by D and we are done. Now suppose there are directed cycles in L and let ρ be an immersed loop in ∆ k that contains a long natural edge in such a cycle. Then, by bounded cancellation and the fact long natural edges are longer than L ≥ C, [f m k (ρ)] contains a long natural edge in the same directed cycle in L for all m ≥ 1. Consequently, none of the immersed loops ρ k (g n ) in ∆ k contain a long natural edge that is in a directed cycle of L. Therefore, as far as the sequence of loops (ρ k (g n )) n≥k is concerned, we may assume there are no directed cycles in L and, as before, the sequence (f N k (ρ k (g n ))) n≥k+N determines an infinite [φ]-tail of [g] carried by D .
The following dichotomy is (equivalent to) a result in Reynolds' thesis. Proof. Suppose φ is irreducible and there is a nontrivial conjugacy class with an infinite [φ]-tail. By Theorem 2.1, there is a nontrivial [φ]-fixed free factor system A. Since φ is irreducible, A = {F } and φ is an automorphism.
The fixed free factor system given by Theorem 2.1 may depend on the chosen conjugacy class [g] with an infinite tail or the marked graphs (Γ, α) chosen in the descent. The next proposition constructs a canonical fixed free factor system for [φ]; this system carries all conjugacy classes with an infinite tail as well as all finitely generated fixed subgroup system. The proof will use both descent and ascent (like a losing game of Tetris) in the poset of free factor systems! Proposition 2.3. If φ : F → F is injective, then there is a unique maximal [φ]-fixed free factor system A. Precisely, A carries every conjugacy class with an infinite [φ]-tail and every finitely generated [φ]-fixed subgroup system.
Proof. Let φ : F → F be an injective endomorphism. If the trivial conjugacy class is the only conjugacy class with an infinite [φ]-tail, then the trivial system is the only [φ]-fixed subgroup system. In this case, the trivial system is the unique maximal [φ]-fixed free factor system and we are done as it vacuously carries all conjugacy classes with infinite [φ]-tails and all [φ]-fixed subgroup systems. We can now assume some nontrivial conjugacy class has an infinite [φ]-tail. By Theorem 2.1, φ has a nontrivial fixed free factor system D 0 . We proceed by ascending up the poset of free factor systems: Once again, as there are no infinite chains in the poset of free factor systems, the ascent (proven below) starts with the nontrivial [φ]-fixed proper free factor D 0 and stops at a necessarily unique maximal [φ]-fixed free factor system A that carries all finitely generated [φ]-fixed subgroup systems and all conjugacy classes with infinite [φ]-tails.
Proof of ascent. Let B be a finitely generated nontrivial [φ]-fixed subgroup system of F , [g] be a nontrivial conjugacy class in F with an infinite [φ]-tail, and D be a nontrivial [φ]-fixed free factor system of F that does not carry both B and [g]. We now describe the descent: For all k ≥ 1, let ∆ k = S[φ k (D )] and, by Proposition 1.7, there is a K-Lipschitz natural representative for [ φ| D ],f k : ∆ k → ∆ k , that has cancellation constant C. As some free factor in D is not eventually [φ]-periodic, we can fix k 0 so that the longest natural edge in ∆ k is longer than L · K N −1 by Lemma 1.1. Define the long and short natural edges as before and deduce long natural edges are longer than L. Set ∆ ⊂ ∆ k to be the union of the short natural edges, which is necessarily proper andf k -invariant. Recall that immersed loops of S[φ k (D)] and S[φ k (B)] that cover any edge at most twice have length bounded by L 0 ≤ L and these Stallings graphs have simplicial immersions into ∆ k . Hence the images of these immersions lie in the subgraph of short natural edges ∆ . So ∆ is neither empty nor contractible. The subgraph ∆ determines a [φ]-invariant proper free factor system D ≺ D that carries both D and B since both Although this proposition produces a canonical fixed free factor system for an injective endomorphism, we shall enlarge the system again to get a better [φ]-invariant free factor system that gives us some control of the relative dynamics of [φ]. We do this by taking iterated preimages of the maximal fixed free factor system. We then show that the resulting invariant free factor system is a disjoint union of the maximal fixed free factor system with a free factor system that eventually gets mapped into the fixed system.
After replacing the free factors of A with conjugates if necessary, we can assume A ⊂ A * .
We shall call the free factor system given by this proposition the [φ]-elliptic free factor system. We call it elliptic since it will be carried by the vertex groups in free splittings of F in the subsequent sections.
Proof. Let φ : F → F be an injective endomorphism and A be the maximal [φ]-fixed free factor system of F given by Proposition 2.3. If φ is surjective or has no nontrivial fixed free factor systems, then A * = A is {F } or trivial respectively and we are done. Thus, we assume that A is a nontrivial proper free factor system. For all k ≥ 1, define for all k ≥ 1 and, consequently, all A k are [φ]-invariant. As there are no infinite chains in the poset of free factor systems of F , the chain of [φ]-invariant free factor systems A k (k ≥ 1) stabilizes and we can set A * to be the maximal free factor system in the chain. By construction, A * carries a subgroup system B if and only if φ k (B) is carried by A for some k ≥ 0 and this implies the uniqueness of A * amongst [φ]-invariant free factor system that have φ-iterates carried by A. It remains to show that A ⊂ A * after replacing the free factors of A with conjugates if necessary.
As in the proof of Lemma -fixed free factor system A, it follows that A A J . Replace components of A with conjugates if necessary and assume A is a free factor system of A J ; in particular, Lemma 1.3 says no finitely generated subgroup of F is conjugate to a proper subgroup of itself. Therefore, It is obvious that the maximal [φ]-fixed free factor system is proper exactly when φ is not surjective. The same holds for the [φ]-elliptic free factor system: Observation. Let φ : F → F be an injective endomorphism. The [φ]-elliptic free factor system is 1. proper exactly when φ is not surjective.

Relative representatives
We will now use relative (weak) representatives as the basis for inductively studying dynamical properties of free group endomorphisms. For the whole section, we suppose φ : F → F is an injective endomorphism and φ −1 · A = A, i.e, A is a [φ]-invariant proper free factor system such that there is no free factor system A A such that A carries φ(A ); e.g., consider an injective nonsurjective φ and its elliptic free factor system. The first step is to establish the relative version of the bounded cancellation.
Lemma 3.1 (Bounded Cancellation). Let T and T be (F, A)-and (F , A )-trees respectively and ψ : F → F be an injective homomorphism such that ψ −1 · A = A. If g : T → T is a ψ-equivariant tree map, then there is a constant C(g) such that for every natural edge-path decomposition p 1 · p 2 of an immersed path in T , the edge-path [g( Let A B be a chain of [φ]-invariant free factor systems, T * be a (B, A)-forest, and f * : T * → T * be a A-relative representative for φ| B . For all k ≥ 1, set T * (φ k (B)) ⊂ T * to be the minimal subforest for φ k (B); minimal subforests are the relative analogues of iterated Stallings graphs. We will assume the minimal subforests T * (φ k (B)) inherit their simplicial structure from the ambient forest T * and so they might have bivalent vertices unlike T * . For a graph of groups decomposition with bivalent vertices, branch points are vertices that are images of branch points of the Bass-Serre tree and natural edges are images of natural edges of the tree.
For any k ≥ 1, let f * ,k : T * (φ k (B)) → T * be the restriction of f * to T * ,k and then replace it with an equivariantly homotopic map These homotopy restrictions are the relative analogues of homotopy lifts. The proof of the following lemma is also almost the same as that of Lemma 1.5.
Lemma 3.2. Let T and T be (F, A)-and (F , A )-trees respectively and ψ : F → F be an injective homomorphism such that ψ −1 · A = A. If g : T → T is a ψ-equivariant tree map with cancellation constant C = C(g), then g maps branch points to the C-neighborhood of branch points.
Proof. Set C = C(g) and let ν be a bivalent vertex in T whose distance to the nearest branch point is greater than C. In particular, ν has a trivial stabilizer. We denote by 1 , 2 the 2 distinct directions at ν oriented away from the vertex. Suppose v is a branch point of T such that g(v) = ν. As ψ is injective, v has a trivial stabilizer under the action of F . Choose 3 distinct directions at v: e 1 , e 2 , and e 3 . Let p 12 be an embedded path in T that starts with e 1 and ends with a translate ofē 2 . Since v has a trivial stabilizer, the path determines a unique loxodromic element x 12 in F with axis a 12 such that p 12 is a fundamental domain of the axis under the translation action of x 12 . Without loss of generality, [g(p 12 )] starts with 1 .
If [g(p 12 )] ends with the translate φ(x 12 )¯ 1 , then [g(p 12 )] = µ·ρ·(φ(x 12 )μ), where µ is an extension of 1 to an embedded path from ν to the axis of φ(x 12 ) and ρ is a fundamental domain of the axis of loxodromic element φ(x 12 ). By assumption, µ is longer than C. Decompose the axis a 12 = a − · a + at v, then [g(a − )] · [g(a + )] hasμ · µ as a subpath, violating bounded cancellation. The remaining cases are handled similarly. Upon ruling out all cases, we conclude that no branch point v of T is mapped to ν.
As before, we get a corollary whose proof is essentially the same as that of Corollary 1.6. Corollary 3.3. Let T and T be (F, A)-and (F , A )-trees respectively and ψ : F → F be an injective homomorphism such that ψ −1 · A = A. If g : T → T is a ψ-equivariant K-Lipschitz tree map with cancellation constant C, then g is equivariantly homotopic to a ψ-equivariant (K + C)-Lipschitz natural tree map with cancellation constant 2C.
The corollary allows us to replace f * ,k with an equivariantly homotopic φ k (A)-relative natural representative that has Lipschitz and cancellation constants K(f * ,k ) = K(f * ) + C(f * ) and C(f * ,k ) = 2C(f * ) respectively. If X ⊂ T * (φ k (B)) is an axis and f * ,k | X is an immersion before the homotopy, then f * ,k (X) is an immersed path after the homotopy; however, the restriction f * ,k | X may fail to be an immersion due to pretrivial edges. The following summary is a relative analogue of Proposition 1.7.
such that: 2. If f * restricted to the axes of some conjugacy class is also an immersion modulo pretrivial edges.
Collapsing a maximal (orbit-closed) f * ,k -invariant subforest of T * (φ k (B)) with bounded components and forgetting the bivalent vertices induces a minimal φ k (A)-relative repre- Note that the collapsed maximal subforest contains the pretrivial edges as φ −1 · A = A. Since g * ,k is induced by equivariantly collapsing a forest and forgetting bivalent vertices, we have Proposition 3.5. Let f * : T * → T * be an A-relative representative for φ| B . For any k ≥ 1, there is a (φ k (B), φ k (A))-forest Y * ,k and a minimal φ k (A)-relative representative g * ,k : Y * ,k → Y * ,k for φ| φ k (B) such that: 3. If f * restricted to the axes of some conjugacy class [b] in φ k (B) is an immersion, then g * ,k restricted to the axes of [b] is also an immersion.
For an A-relative weak representative f * for φ| B , we define the transition matrix A(f * ). Let A(f * ) be a nonnegative integer square matrix whose rows and columns are indexed by the orbits of edges in T * ; the entry of A(f * ) in row-i and column-j, A(f * )(i, j), is given by the number of translates of e i that are contained in the immersed edge-path f * (e j ), where e i is a orbit representative for the i-th orbit of edges. An A-relative weak representative f * is irreducible if the matrix A(f * ) is irreducible, i.e., for any pair (i, j), there is a positive integer n ij such that A(f * ) n ij (i, j) > 0. In this case, the stretch factor of We say φ| B is irreducible relative to A if there is no [φ]-invariant free factor system C such that A ≺ C ≺ B. If A is trivial and B = {F }, then we recover the definition of φ's irreducibility. The next lemma is the most useful property of an irreducible restriction for our purposes. Lemma 3.6. If φ| B is irreducible relative to A, then every minimal A-relative representative for φ| B is irreducible.
Proof. Suppose some minimal A-relative representative for φ| B has a reducible transition matrix; in particular, it has an invariant B-equivariant proper subforest (with unbounded components) that determines a [φ]-invariant free factor system C such that A ≺ C ≺ B. So φ| B is not irreducible relative to A.
Remark. Bestvina-Handel give the absolute version of this property as the definition of irreducibility and then prove that it is equivalent to the definition of irreducibility given in this paper [6, Lemma 1.16]. The relative version of this equivalence holds as well but we will not prove it as it is not needed.
The minimal stretch factor will be denoted by λ([φ], B, A).
Proof. Let g * : Y * → Y * be a minimal A-relative representative for φ| B and suppose φ| B is irreducible relative to A. Then g * is an irreducible A-relative representative by Lemma 3.6 with stretch factor λ(g * ). By the lack on bivalent vertices, any irreducible A-relative representative has a transition matrix of size ≤ N = 3 · rank(F ) − 3. Suppose B is an irreducible integer square matrix with Perron-Frobenius eigenvalue λ(B) ≤ λ(g * ). Then B has a positive right eigenvector v associated with λ(B). So for all k ≥ 1, B k has right eigenvector v associated with eigenvalue λ(B) k . Assuming the smallest entry of v is 1 (rescale if necessary), we get that the minimum row-sum of B k is at most λ(B) k for any k ≥ 1. If B has no more than N rows, then the largest entry of B is at most the minimum row-sum of B N ! , which we know is at most λ(B) N ! ≤ λ(g * ) N ! . So there are finitely many irreducible integer square matrices with size ≤ N and Perron-Frobenius eigenvalue ≤ λ(g * ).
Thus, there is a finite set of stretch factors ≤ λ(g * ) for irreducible A-relative representatives for φ| B . In particular, there is an irreducible A-relative representative f * : T * → T * for φ| B with the minimal stretch factor.
Bestvina-Handel's work [6] can be adapted to show that an irreducible A-relative representative for φ| B with the minimal stretch factor is an A-relative train track (Appendix A) and, conversely, bounded cancellation implies all irreducible A-relative train tracks for φ| B have the minimal stretch factor. We do not prove this converse as it is not needed. The next lemma is an application of train track theory that will be invoked once, in the second half of the proof of Proposition 3.9.
Lemma 3.8 (Train Track Theory). If φ| B is irreducible relative to A and f * : T * → T * is an irreducible A-relative representative for φ| B with the minimal stretch factor, then there is an element g in B with an axis a g such that the restriction of f k * to a g is an immersion for all k ≥ 1.
Such an axis will be known as an f * -legal axis.
Proof. If λ(f * ) = 1, then f * is a simplicial embedding and we are done. So we may assume λ(f * ) > 1. By minimality of its stretch factor, f * is an expanding irreducible A-relative train track for φ| B (Theorem A.1), i.e., for any edge e in T * , f k * (e) is an expanding immersed path for all k ≥ 1. A 2-edge path e 1 · e 2 is f * -legal if it is a translate of a subpath of f k * (e) for some edge e and integer k ≥ 1. By irreducibility of f * , every edge e is contained in a 3-edge path e − · e · e + whose 2-edge subpaths are both f * -legal. This means we can form an axis a g whose 2-edge subpaths are all f * -legal. By the train track property, the restriction of f k * to a g is an immersion for all k ≥ 1.
The main tools from Section 1 that were used in the previous section were Lemma 1.1, bounded cancellation, and Proposition 1.7. The relative analogues of the latter two have already been established in this section. We now state the main technical result of this section, an analogue of Lemma 1.1 -analogous in the sense that both give sufficient conditions for iterated subgroup graphs to have arbitrarily long natural edges. Proposition 3.9. Let A ≺ B be a chain of [φ]-invariant free factor systems with φ| B irreducible relative to A and λ([φ], B, A) > 1. If A carries the maximal [φ]-fixed free factor system, then the length of the longest natural edge in T * (φ k (B)) is unbounded as k → ∞.
Before starting the proof, we will first describe the (absolute) vertex blow-up construction. Let A ≺ B be a chain of free factor systems and T * be some (B, A)-forest. Recall that we assume A i ⊂ A is also a free factor system of B i ∈ B. Fix some A-marked roses (R A , α A ) . Define Γ B to be the graph formed by identifying the appropriate vertices of the graph of groups B\T * with the basepoints of roses ( is a B-marked graph. This construction and, in general any pair of graphs Γ A ⊂ Γ B with collections of markings α A , α B such that π 1 (c ) • α A = (α B )| A will be referred to as vertex blow-up.
We note that the Stallings graph The noncontractible components of the subgraph ι −1 B (R A ) will be known as the lower stratum and the rest of the graph as the top stratum.
that agrees with f A on the A-marked roses R A and induces f * on the Bass-Serre forest T * upon collapsing the roses R A .
For any k ≥ 1, we let g * ,k : Y * ,k → Y * ,k be the minimal φ k (A)-relative representative for φ| φ k (B) given by Proposition 3.5 using f * andf k : S[φ k (B)] → S[φ k (B)] be the natural representative for [ φ| φ k (B) ] given by Proposition 1.7 using f B . By Proposition 3.5(3), if an element b in B has an f * -legal axis, then φ k (b) has a g * ,k -legal axis. It can be arranged for and forgetting bivalent vertices.
Here is the idea behind the proof. By irreducibility of the restriction φ| B , we may assume the map g * ,k is an expanding irreducible representative for φ| φ k (B) . For the contrapositive, suppose the forests T * (φ k (B)) had uniformly bounded natural edges. There is a sequence of loxodromic elements b k in φ k (B) with uniformly bounded translation lengths l T * (g k ). Now suppose that the vertex blow-up S[φ k (B)] had natural edges with aribtrarily long top stratum subpaths. Bounded cancellation, the factf k induces g * ,k , and the irreducibility of g * ,k imply g * ,k is an expanding irreducible immersion. However, this contradicts the first assumption since l Y * ,k ≤ l T * (φ k (B)) . So the second supposition is false and the natural edges of S[φ k (B)] have top stratum subpaths with uniformly bounded length. Using the Lipschitz property, expanding irreducibility of g * ,k , and existence of a g * ,k -legal axis (train track theory), we find uniformly bounded lower stratum paths in S[φ k (B)] connecting the origin of any oriented top stratum subpath of a natural edge to another top stratum subpath of a natural edge. Consequently, we are able to build uniformly bounded immersed loops in S[φ k (B)] that contain top stratum subpaths. This implies some loxodromic conjugacy class in B has an infinite [φ]-tail. By Proposition 2.3, any conjugacy class in F with an infinite [φ]-tail is carried by the maximal [φ]-fixed free factor system. Thus the maximal [φ]-fixed free factor system cannot be carried by A as it carries a loxodromic conjugacy class.
Proof of Proposition 3.9. Suppose A ≺ B are [φ]-invariant free factor systems, φ| B is ir-reducible relative to A, f A : R A → R A is a topological representative for φ| A defined on A-marked roses (R A , α A ), and f * : T * → T * is an expanding irreducible A-relative representative for φ| B with the minimal stretch factor λ(f * ) > 1 (Proposition 3.7). By Lemma 3.8, there is an element b in B with an f * -legal axis. Set (Γ B , α B ) to be the vertex blow-up of B\T * with respect to the A-marked roses (R A , α A ). The discussion preceding the proof gives minimal φ k (A)-relative representatives g * ,k : Y * ,k → Y * ,k for φ| φ k (B) and natural representativesf k : ] that have these properties: for all k ≥ 1, The collection φ| φ k (B) is conjugate to φ| B by injectivity of φ. So φ| φ k (B) is irreducible relative to φ k (A) and λ(f * ) is the minimal stretch factor for φ| φ k (B) relative to φ k (A). Furthermore, the minimal φ k (A)-relative representatives g * ,k are irreducible (Lemma 3.6) and λ(g * ,k ) ≥ λ(f * ) > 1 by the minimality of λ(f * ).
Suppose for the contrapositive that there is a bound L ≥ 1 such that all natural edges in T * (φ k (B)) are shorter than L for all k ≥ 1. Then, for all k ≥ 1, there is a loxodromic Suppose, the graph Γ * ,k has an edge E 0 whose corresponding subpathĒ 0 in S[φ k (B)] is longer than C · K N −1 for some k ≥ 1. As we did in the proof of Theorem 2.1, we construct the set of long edges E by looking at all the edges of Γ * ,k that are eventually mapped over E 0 . Here, an edge E 1 in Γ * ,k mapped over E 0 if there are lifts E 1 and E 0 in Y * ,k such that g * ,k maps E 1 over E 0 . Sincef k : S[φ k (B)] → S[φ k (B)] is K-Lipschitz and it induces g * ,k on Y * ,k , each long edge in Γ * ,k corresponds to a top statrum subpath in S[φ k (B)] longer than C. Since g * ,k is an irreducible φ k (A)-relative representative, all edges eventually map over E 0 and hence are long. The long natural edges of S[φ k (B)] will be the natural edges in S[φ k (B)] containing top stratum subpaths.
Suppose an edge E of Γ * ,k had a lift E in Y * ,k that is the initial segment of the g * ,kimage of two edges that share an initial vertex. Then the top stratum subpathĒ is in a long natural edge of S[φ k (B)] that is the initial segment off k -images of natural edges that share an initial vertex; this violates bounded cancellation since long natural edges of S[φ k (B)] longer than C = C(f k ). Hence, there is no folding in g * ,k , i.e., g * ,k is an expanding irreducible φ k (A)-relative immersion. We may now find an m ≥ 1 such that all loxodromic we get that l T * (b ) > (3N − 3)L for all loxodromic elements b in φ k+m (B). This contradicts the assumption that l T * (b k+m ) ≤ (3N − 3)L for some loxodromic b k+m in φ k+m (B). So the top stratum subpathĒ in S[φ k (B)] has length ≤ C · K N −1 for all natural edges E of Γ * ,k and k ≥ 1. This ends the proof of the claim.
Next, we prove the existence of paths in the lower stratum of S[φ k (B)] with uniformly bounded lengths connecting top stratum paths. Suppose E 0 , E 1 , and E 2 are edges of Γ * ,k with lifts E 0 , E 1 , and E 2 in Y * ,k such that E 1 · E 2 is a subpath of the immersed path g * ,k (E 0 ). ThenĒ 1 · P 12 ·Ē 2 is a subpath of immersed pathf k (Ē 0 ) for some lower stratum path P 12 in S[φ k (B)]. SinceĒ 0 has length bounded by C · K N −1 andf k is K-Lipschitz, the path P 12 has length bounded by C · K N . We say the 2-edge path E 1 · E 2 in Γ * ,k has a nondegenerate turn bounded by C · K N .
As g * ,k is an expanding irreducible relative representative that has a legal axis (this is where the argument invokes train track theory), every edge E in Y * ,k can be extended to an immersed 3-edge path E − · E · E + that is a translate of a subpath of g n * ,k (E ) and n ≤ 2·N !. In particular, any edge in Γ * ,k can be extended to a 3-edge path whose 2-edge subpaths both have nondegenerate turns bounded by C ·K N −1 ·K 2·N ! , i.e., every top stratum subpath E can be extended to an immersed pathĒ − ·P − ·Ē·P + ·Ē + with top stratum subpathsĒ − , E + and lower stratum paths P − , P + with length bounded by C · K N −1 · K 2·N ! .
Using this bound on lower stratum paths and the bound on top stratum subpaths given by the claim, we can now form an immersed loop ρ k in Γ * ,k with the properties: In summary, for each k ≥ 1, we construct a loxodromic conjugacy class [b k ] in φ k (B) whose α B -length is bounded by a constant independent of k. As there are finitely many conjugacy classes with α B -length bounded by any given constant, the sequence of conjugacy classes

Canonical expanding relative immersions
The main result of this section is the existence of expanding immersions for nonsurjective endomorphisms relative to their elliptic free factor systems.
Let φ : F → F be an injective endomorphism, A ≺ B be a pair of [φ]-invariant free factor systems such that φ −1 · A = A, and φ| B : B → B be a restriction of φ to B. Recall that a relative representative is minimal if it has no orbit-closed invariant subforests with bounded components and an expanding A-relative immersion for φ| B is an A-relative representative f * : T * → T * for φ| B that is a minimal immersion whose edges expand under f * -iteration.
There will be two possible ways of obtaining a relative immersion from a relatively irreducible restriction with a minimal stretch factor λ. If λ = 1, then an irreducible representative with stretch factor λ is automatically a simplicial immersion. The next proposition shows how to construct an immersion when λ > 1. This construction is unique to nonsurjective endomorphisms because we require that the restriction be irreducible relative to a free factor system that carries the [φ]-elliptic free factor system -when φ is an automorphism, the [φ]-elliptic free factor system is {F } and no such restriction exists. Proof. Suppose φ : F → F is injective, A ≺ B are [φ]-invariant free factor systems that carry the [φ]-elliptic free factor system, φ| B is irreducible relative to A, and f * : T * → T * is an expanding irreducible (B, A)-relative representative for φ| B with minimal stretch factor λ(f * ) > 1. Set K = K(f * ) + C(f * ) and C = 2C(f * ). By Proposition 3.4, there is a natural representative f * ,k : T * (φ k (B)) → T * (φ k (B)) for φ| φ k (B) with Lipschitz and cancellation constants K(f * ,k ) = K and C(f * ,k ) = C respectively for all k ≥ 1.
The first part of the proof proceeds as a relativized version of the proof of Theorem 2.1. By Proposition 3.9, we may fix k 0 such that the set of natural edges L 0 in T * (φ k (B)) longer than C · K N −1 is not empty, where N = 3 · rank(F ) − 3. Choose L to be the set of all natural edges that eventually get mapped over those in L 0 by f * ,k and call L the long natural edges. As f * ,k is K-Lipschitz and there are at most N orbits of natural edges in T * (φ k (B)), the long natural edges are longer that C. Injectivity of φ implies φ| φ k (B) is conjugate to φ| B . So φ| φ k (B) is irreducible relative to φ k (A), λ(f * ) is the minimal stretch factor for φ| φ k (B) relative to φ k (A), and the short natural edges of T * (φ k (B)) form an orbit-closed f * ,k -invariant subforest with bounded components.
Collapse a maximal f * ,k -invariant subforest of T * (φ k (B)) that has bounded components and contains the short natural edges then forget the bivalent vertices; this induces a minimal φ k (A)-relative representative g * ,k : Y * ,k → Y * ,k for φ| φ k (B) . The map g * ,k is an irreducible φ k (A)-relative representative for φ| φ k (B) (Lemma 3.6) and λ(g * ,k ) ≥ λ(f * ) by the minimality of λ(f * ). So g * ,k is an expanding irreducible φ k (A)-relative representative.
Since the lifts in T * (φ k (B)) of all edges in Y * ,k are longer than the cancellation constant C, there is no folding in g * ,k -otherwise, there would be folding in f * ,k identifying paths longer than its cancellation constant, absurd. Thus, g * ,k is an immersion. By injectivity of φ, we can view Y * ,k as a (B, A)-forest and g * ,k as an expanding irreducible A-relative immersion for φ| B .
We are now ready to state and prove our base case for the construction. In light of the previous proposition, the point is that a restriction φ| B that is irreducible relative to the [φ]-elliptic free factor system A will satisfy λ([φ], B, A) > 1. Proof. Let φ : F → F be injective and φ| B be irreducible relative to the [φ]-elliptic free factor system A. Then there is an irreducible A-relative representative f * : T * → T * for φ| B with stretch factor λ(f * ) = λ([φ], B, A) ≥ 1 (Proposition 3.7). We say B i ∈ B is loxodromic if T i ∈ T * is not a point, i.e., B i contains a loxodromic element; similarly, the component B i \T i of the graph of groups B\T * is loxodromic if B i is loxodromic. If λ(f * ) = 1, then the induced map on the loxodromic components of B\T * is a graph isomorphism. So for some k ≥ 1, if A ∈ A is carried by a loxodromic B ∈ B, then A is φ k -invariant. By Proposition 2.4, the subset of all A ∈ A carried by the loxodromic component of B form a [φ]-fixed free factor subsystem. As f * induces a graph isomorphism on the loxodromic components of B\T * and these components' vertex groups form a [φ]-fixed free factor system, we get that f * is surjective when restricted to the unbounded components of the forest T * and the loxodromic components of B form a [φ]-fixed free factor system. This is a contradiction since [φ]-periodic free factors are elliptic (Propositions 2.3 and 2.4). Therefore, λ(f * ) > 1 and the result follows from Proposition 4.1.
Specializing this proposition to the case where φ is irreducible and nonsurjective yields an alternate proof to a result due to Reynolds. Remark. This proof of Reynolds' result is a variation of our previous proof [24,Theorem 4.5] with two crucial differences: 1) it makes no use of limit trees in the compactification of outer space; 2) the specialization of Proposition 4.1 to irreducible nonsurjective endomorphisms need not invoke train track theory since we can use Lemma 1.1 in place of Proposition 3.9.
The next proposition is the induction step for our construction.
Proposition 4.4. Let φ : F → F be injective, A be the [φ]-elliptic free factor system, and A ≺ B ≺ C be a chain of [φ]-invariant free factor systems. If there is an expanding Arelative immersion for φ| B and a B-relative immersion for φ| C , then there is an expanding A-relative immersion for φ| C .
Although the proof gets a bit technical, the idea is rather simple: a B-relative immersion for φ| C (top stratum) and an expanding A-relative immersion for φ| B (lower stratum) can be patched together via a (relative) vertex blow-up to get a minimal A-relative representative g * : Y * → Y * whose only possible folds would have to happen between a top and lower stratum edge of Y * . As the restriction of g * to the lower stratum is an expanding immersion, we may assume the edges in the lower stratum are longer than the cancellation constant. This means no lower stratum edge is identified by a fold and so no folding in g * is possible. Thus, g * is a minimal A-relative immersion for φ| C , which will be expanding if A is the [φ]-elliptic free factor system.
Let T C be a (C, B)-forest and T B be a (B, A)-forest. For any free factor C i ∈ C, let B i the maximal subset of B that is carried by C i . Replace the free factors of B with conjugates if necessary and assume B is also a free factor system of C. In particular, the free factors B ∈ B i are subgroups of the free factors C i ∈ C. Identifying the appropriate vertices of the graph of groups C\T C with basepoints on the graph of groups B\T B results in a graph of groups decomposition for C whose Bass-Serre forest T * is a (C, A)-forest that contains T B . We call T * the vertex blow-up of T C with respect to T B .
Proof of Proposition 4.4. Let φ : F → F be injective, B ≺ C be a chain of [φ]-invariant free factor systems that carry the [φ]-elliptic free factor system A. Suppose f B : T B → T B is an expanding A-relative immersion for φ| B and f C : T C → T C is a B-relative immersion for φ| C then define T * to be the vertex blow-up of T C with respect to T B . The edges of T * are of two types: the lower stratum, which are edges that are contained in the C-orbit of T B , and the top stratum, which are the remaining edges.
Let f * : T * → T * be a minimal A-relative representative for φ| C such that T B is an f * -invariant subforest, the restriction of f * to T B agrees with f B , and f * induces f C upon collapsing the lower stratum. For all k ≥ 1, set T * (φ k (C)) and T * (φ k (B)) to be the minimal subforests of T * for φ k (C) and φ k (B) respectively. Similarly, define the minimal subforest T B (φ k (B)) ⊂ T B . By the inclusion of T B in T * , we get a simplicial identification of T * (φ k (B)) with T B (φ k (B)). However, we want to consider these two forests differently with respect to their branch points and natural edges. In particular, there may be branch points of T * (φ k (C)) that are bivalent when considered as points on the subforest T * (φ k (B)). So by "natural edges of T * (φ k (B))", we mean those inherited from the parent forest T * (φ k (C)); on the other hand, by "natural edges of T B (φ k (B))", we do mean exactly that. Under the identification of the two forests, the natural edges of T * (φ k (B)) partition any natural edge of T B (φ k (B)) into at most 2X segments, where X = rank(F ) − 1.
Since f C : T C → T C is a B-relative immersion for φ| C , the restrictions of f C to T C (φ k (C)) are φ k (B)-relative immersions f C,k : T C (φ k (C)) → T C (φ k (C)) for φ| φ k (C) that are conjugate to f C . As f * induces f C upon collapsing the lower stratum, any edges in f * (T * (φ k (C))) but not T * (φ k (C)) must be in the lower stratum and the restriction of f * to T * (φ k (C)) induces f C,k upon collapsing the lower stratum, i.e., the φ k (C)-orbit of T * (φ k (B)). By Proposition 3.4, there is an φ k (A)-relative natural representative f * ,k : T * (φ k (C)) → T * (φ k (C)) for φ| φ k (C) with Lipschitz and cancellation constants K = K(f * ) + C(f * ) and C = 2C(f * ) respectively. Furthermore, T * (φ k (B)) is an f * ,k -invariant subforest and f * ,k still induces f C,k upon collapsing the lower stratum. As f * agrees with the immersion f B on T B , f * ,k differs from f B on T * (φ k (B)) by a homotopy supported in the natural edges of T B (φ k (B)).
Since f B : T B → T B is an expanding A-relative immersion for φ| B , the minimal subforest T B (φ k (B)) has natural edges whose lengths are all exponential in k. Fix k 0 such that all natural edges of T B (φ k (B)) are longer than 2X · C · K 3X −1 . By the pigeonhole principle, each natural edge of T B (φ k (B)) contains a natural edge of T * (φ k (B)) longer than C · K 3X . Let G k be the directed graph of natural edges of the f * ,k -invariant subforest T * (φ k (B)) where a directed edge E i → E j corresponds to f * ,k mapping E i over E j . Set S 0 to be those natural edges with length at most C and S to be those natural edges with directed path from S 0 in G k and their φ k (C)-translates; these lower stratum natural edges will be the short natural edges of T * (φ k (C)). Since f * ,k is K-Lipschitz and the shortest path between any two natural edges in G k has 3X natural edges, all the short natural edges have length at most C · K 3X −1 . So the short natural edges S form an orbit-closed f * ,k -invariant lower stratum subforest of T * (φ k (C)) with bounded components as S does not cover any natural edge of T B (φ k (B)).
Collapsing the short natural edges of T * (φ k (B)) induces a map g * ,k : Y * ,k → Y * ,k with the same cancellation constant C(g * ,k ) = C. Now iteratively collapse pretrivial edges until the induced map g * ,k : Y * ,k → Y * ,k has none. As the collapses are supported in the lower stratum, the new map g * ,k still induces the immersion f C,k upon collapsing the rest of the lower stratum and, as a result, folding in g * ,k may only occur between initial segments of natural edges of Y * ,k whose g * ,k -images are a lower stratum natural edge. However, all natural edges in the lower stratum of Y * ,k are longer than C by construction and so no folding in g * ,k is possible by bounded cancellation, i.e., g * ,k is an immersion.
Collapsing a maximal invariant subforest with bounded components and forgetting bivalent vertices if necessary, we may assume g * ,k : Y * ,k → Y * ,k is a minimal φ k (A)-relative immersion for φ| φ k (C) . By the injectivity of φ, we can view g * ,k as a minimal A-relative immersion for φ| C . It remains to show that every edge of Y * ,k expands under g * ,k -iteration.
For a contradiction, suppose there is an edge of Y * ,k whose g * ,k -iterates have uniformly bounded length. Since g * ,k is minimal, the non-expanding edges in the graph of groups C\Y * ,k contain a setwise fixed subgraph F that carries a loxodromic element. The subgraph F is a free splitting of a [φ]-invariant free factor system. Recall that the [φ]-elliptic free factor system A decomposes as a union of the maximal [φ]-fixed free factor system and free factors that eventually get mapped into this fixed system (Proposition 2.4). By construction, the point stabilizers of Y * ,k are conjugates of A. So any vertex of the fixed graph F is labelled by either the trivial group or a free factor of the maximal [φ]-fixed free factor system. Thus F is a free splitting of a [φ]-fixed free factor system that carries some loxodromic element. However, Propositions 2.3 and 2.4 imply that all [φ]-fixed free factors systems are elliptic -a contradiction.
We are now ready to inductively construct expanding relative immersions.
Theorem 4.5. If φ : F → F is injective but not surjective, then there is an expanding A-relative immersion for φ, where A is the [φ]-elliptic free factor system.
Proof. Suppose φ : F → F is injective but not surjective. By Proposition 2.4, the [φ]elliptic free factor system A is proper. The naive approach is to assume there exists a chain A = B 0 ≺ · · · ≺ B n = {F } in the poset of [φ]-invariant free factor system such that the restrictions φ| B m+1 are irreducible relative to B m for all m ≥ 1. This assumption is typical when working with automorphisms. For each restriction φ| B m+1 , if the minimal stretch factor λ([φ], B m+1 , B m ) = 1, then there is automatically a B m -relative immersion for φ| B m+1 ; and if λ([φ], B m+1 , B m ) > 1, then there is an expanding B m -relative immersion for φ| B m+1 by Proposition 4.1. In either case, there is a B m -relative immersion for φ| B m+1 . By Proposition 4.2, λ([φ], B 1 , B 0 ) > 1 and there is an expanding B 0 -relative immersion for φ| B 1 . By inductively patching these immersions together using Proposition 4.4, we get an expanding B 0 -relative immersion for φ and we are done. Unfortunately, since φ is not surjective, it could be that no chain A = B 0 ≺ · · · ≺ B n = {F } satisfies the naive assumption we made at the start. Recall that our definition of φ| B m+1 being irreducible relative to B m presupposed φ −1 · B m = B m . Fortunately, this is a minor complication that can be easily addressed. The proof follows the approach described above closely but uses a chain with slightly weaker conditions on it.
We first construct a chain A = B 0 ≺ · · · ≺ B n = {F } in the poset of [φ]-invariant free factor system that we will induct on. Let A ≺ B 1 be a chain of [φ]-invariant free factor systems such that φ| B 1 is irreducible relative to A. Suppose B m has been constructed for some m ≥ 1 and let C B m be the maximal free factor system in the chain B m φ −1 · B m φ −2 · B m · · · of [φ]-invariant free factor systems. If φ −1 · B m = B m = C, then let B m ≺ B m+1 be a chain of [φ]-invariant free factor systems such that φ| B m+1 is irreducible relative to B m . If B m ≺ C, then let B m ≺ · · · ≺ B m+k = C be the chain of [φ]-invariant free factor systems such that B m+i = φ −i · B m for 1 ≤ i ≤ k.
We proceed by inducting on the resulting chain between A and {F }. For the base case, φ| B 1 is irreducible relative to A; therefore, there is an expanding A-relative immersion for φ| B 1 by Proposition 4.2. For our induction hypothesis, suppose that there is an expanding A-relative immersion f Bm : T Bm → T Bm for φ| Bm for some m ≥ 1. By our construction of the chain, either φ| B m+1 is irreducible relative to B or φ(B m+1 ) is carried by B m . We deal with these two cases separately. Case 1. Suppose φ| B m+1 is irreducible relative to B m . By Proposition 3.7, there is an irreducible B m -relative representative f * : T * → T * for φ| B m+1 with minimal stretch factor. If λ(f * ) = 1, then f B m+1 = f * is a B m -relative simplicial immersion for φ| B m+1 . If λ(f * ) > 1, then there is an expanding B-relative immersion f B m+1 for φ| B m+1 by Proposition 4.1. In either case, we get a B m -relative immersion f B m+1 : T B m+1 → T B m+1 for φ| B m+1 defined on a (B m+1 , B m )-forest T B m+1 . Thus, there is an expanding A-relative immersion for φ| B m+1 by the induction hypothesis and Proposition 4.4. Case 2. Now suppose φ(B m+1 ) is carried by B m . Let T Bm (φ(B m+1 )) ⊂ T Bm be the minimal subforest of φ(B m+1 ) and T B m+1 = T Bm (φ(B m+1 )) be the same forest after forgetting bivalent vertices. By injectivity of φ, we may consider T B m+1 as a (B m+1 , A)forest that comes with a natural φ| B m+1 -equivariant immersion g : T B m+1 → T Bm . Since f Bm : T Bm → T Bm is an immersion, we can identify a subdivision of T Bm with the minimal subforest T B m+1 (B m ) ⊂ T B m+1 of B m . Composing g with the subdivision and inclusion which is expanding since its image lies in T B m+1 (B m ) and its restriction to T B m+1 (B m ) is the expanding A-relative immersion f Bm after forgetting bivalent vertices.
It will follow from bounded cancellation that expanding relative immersion from the theorem is in fact canonical. Proposition 4.6. Suppose φ : F → F is injective and there is an expanding A-relative immersion for φ, where A is a [φ]-invariant free factor system. Then there is a unique expanding A-relative immersion for φ.
Proof. Let φ : F → F be injective, A a [φ]-invariant free factor system. Suppose f : T → T and f : T → T are expanding A-relative immersions for φ. The goal is to show that T and T are equivariantly homeomorphic. Let g : T → T be an equivariant tree map, i.e., ψ-equivariant tree map with ψ : F → F being the identity automorphism; such a map always exists between (F, A)-trees. By taking restrictions to the φ k (F )-minimal subtrees T (φ k (F )) and T (φ k (F )) and applying deformation retractions, we get a φ k (F )-equivariant tree map g k : T (φ k (F )) → T (φ k (F )) with cancellation constant C(g). By Corollary 3.3, we assume g k is an equivariant natural tree map with cancellation constant 2C(g).
Recall that f is an expanding A-relative immersion for φ, so all the natural edges of T (φ k (F )) are longer than 2C(g) for large enough k. Fix k 0, then no folding occurs in g k by bounded cancellation. So g k is a forest collapse and T (φ k (F )) has at most the same number of orbits of branch points as T (φ k (F )). By the same argument, T (φ k (F )) is an equivariant forest collapse of T (φ k (F )) and has at most the same number of orbits of branch points as T (φ k (F )). This implies the two minimal subtrees have the same number of orbits of branch points and g k is an equivariant homeomorphism. Since f and f are immersions, T and T are φ k -equivariantly homeomorphic to T (φ k (F )) and T (φ k (F )) respectively. Therefore, T and T are equivariantly homeomorphic by injectivity of φ. So f and f are homotopic immersions and hence agree up to isotopy.  We call the free factor system A * the [φ]-elliptic free factor system. By expanding immersion, we mean every edge of the tree grows under iteration.
As a corollary of this summary, we have the following characterization: [φ] is induced by an expanding graph immersion if and only if the trivial system is the only [φ]-fixed free factor system (Corollary 4.8). We will now contextualize these results and, especially, this corollary. In our previous work [23], we determined exactly when the mapping torus of an expanding graph immersion has a word-hyperbolic fundamental group. By Reynolds' result (Corollary 4.3), we knew this theorem applied to all irreducible nonsurjective endomorphisms but, at the time, there was no known algebraic characterization of the general class of endomorphisms induced by expanding graph immersions. It is clear that nontrivial [φ]-periodic subgroups are an obstruction to φ being induced by an expanding graph immersion. Corollary 4.8 means nontrivial fixed free factor systems are the only (essential) obstruction. So the above theorem can be restated as: Theorem. Let φ : F → F be an injective endomorphism with no nontrivial fixed free factor system. F * φ is word-hyperbolic if and only if it has no BS(1, d) subgroups for d ≥ 2.
The interesting thing about the restatement is that it is purely algebraic, i.e., there is no mention of topological maps. Since fixed free factor systems correspond to free-by-cyclic subgroups F Z of F * φ , the restatement also suggests how to extend our previous work to all injective nonsurjective endomorphisms.
In the next sections, we use expanding relative immersions to relativize our previous work in [23]. For instance, the sequence of lemmas/propositions in the next section is essentially identical to the sequence in [23,Section 3]. In Section 6, we extend our previous theorem to all injective endomorphisms. However, this will not constitute an alternate proof of Brinkmann's theorem [8]: F Z is word-hyperbolic if and only if it has no Z 2 subgroups. We assume Brinkmann's theorem as the base case of our generalization.
Before diving into the details, we give an illustration of the consideration in the second part of this paper. To prove that BS(1, d) subgroups are the only obstruction to wordhyperbolicity, the main tool we use is the Bestvina-Feighn combination theorem [3]: as long as the group in question satisfies the annuli flaring condition, it will be word-hyperbolic. See Section 7 for the exact statement. For non-examples, we now explain why/how BS(1, d) groups fail the annuli flaring condition.
Consider two Baumslag-Solitar groups BS(1, d) with d = 1, 2. Note that BS(1, 1) = Z 2 . Fix the presentation BS(1, d) = a, t | t −1 at = a d and notice that the group is a mapping torus of an endomorphism ψ of the cyclic group a . So BS(1, d) acts on a simplicial tree T with point and edge stabilizers conjugate to a and the quotient graph BS(1, d)\T has one vertex and edge. The edge has a natural orientation inherited from the nontrivial loop corresponding to t and we can lift the orientation to an equivariant orientation of T . Under this orientation, T is like a rooted tree: every vertex has exactly d incoming edges and one outgoing edge. Choose a vertex on the axis of t whose stabilizer by a and define T a to be the family tree of -descendants, i.e., union of directed edge-paths that terminate on .
A class of annuli of length n in BS(1, d) is an ordered pair (g, p g ) where g ∈ BS(1, d) is nontrivial and p g is a geodesic of length n in T fixed by g. Since g is elliptic, then (up to conjugacy) we may assume g ∈ a , ∈ p g , and p g ⊂ T a . The orientation on T implies there are two types of annuli: 1) unidirectional -those whose geodesics are directed paths terminating on ; 2) bidirectional -those whose geodesics are a wedge of two directed paths terminating on . When d = 1, T is a line and all annuli are unidirectional. Loosely speaking, flaring means expanding exponentially towards some end. It should be intuitive that annuli will not flare because the associated endomorphism ψ is the identity map. When d = 2, T is a regular trivalent tree and annuli can be unidirectional or bidirectional. Since the associated endomorphism ψ is represented by a degree 2 map of the circle, the unidirectional annuli will flare. However, due to the branching in T , it is possible to wedge two flaring unidirectional annuli along their expanding ends to get a bidirectional annulus that shrinks exponentially towards both its ends. The objective is to rule out both of these behaviors in the setting of a mapping torus F * φ that has no BS(1, d) subgroups with d ≥ 1 and thus conclude that the mapping torus satisfies the annuli flaring condition. Here is an outline of the second part of the paper: 1. In Section 5, we prove that if F * φ has no BS(1, d) subgroups with d ≥ 2, then there is a uniform bound on one of the two directed pieces of any bidirectional annulus. Thus long bidirectional annuli are unidirectional up to bounded error. However, since annuli are not defined yet in this section, everything is done in terms of pullbacks, which are special classes of bidirectional annuli.
2. In Section 6, we define annuli and give the correspondence with pullbacks. We then use expanding relative immersions and Brinkmann's theorem to prove the section's main result: if F * φ has no Z 2 subgroups, then long unidirectional annuli flare. Thus, together with the previous section, F * φ satisfies the annuli flaring condition if it has no BS(1, d) subgroups with d ≥ 1.
3. Finally, in Section 7, we extend the result to HNN extensions of free groups over free factors F * A by showing that there is a canonical finite collection of mapping tori F * φ ≤ F * A that carry all long annuli of F * A . Intuitively speaking, the action of F * A on its Bass-Serre tree is acylindrical relative to {F i * φ i }. So F * A satisfies the annuli flaring condition if and only if the subgroups {F i * φ i } satisfy the condition.

Geometry of ascending HNN extensions 5 Iterated pullbacks
In our previous work [23,Sections 3], topological pullbacks for a graph immersion f : Γ → Γ were used to give sufficient conditions for π 1 (f ) = φ : F → F to have an invariant nonfixed cyclic subgroup system. The goal of this section is to drop the immersion hypothesis and give sufficient conditions that apply to all injective endomorphisms of F . Suppose immersions f 1 : Γ 1 → Γ and f 2 : Γ 2 → Γ induce inclusions of free groups H 1 , H 2 ≤ F respectively. Then components of the core (topological) pullback of (f 1 , f 2 ), also known as fibered products are in one-to-one correspondence with nontrivial intersection H 1 ∩ gH 2 g −1 as g ranges over (H 1 , H 2 )-double coset representatives of H 1 \F/H 2 . For a graph immersion f : Γ → Γ that induces an endomorphism φ : F → F , we get a oneto-one correspondence between components of the core pullback of (f k , f k ) and nontrivial conjugacy classes [φ k (F )∩gφ k (F )g −1 ] as [[g]] ranges over φ k (F )-double cosets for all k ≥ 1. We will not define pullbacks topological maps since we will be working (semi-)algebraically in this section.
Given subgroups H 1 , H 2 ≤ F , we define the (algebraic) pullback of (H 1 , H 2 ), denoted by H 1 ∧ H 2 , to be the set of all nontrivial components [H 1 ∩ gH 2 g −1 ] as [[g]] ranges over the (H 1 , H 2 )-double cosets in F . Note that pullbacks are not subgroup systems since they are sets of conjugacy classes of subgroups. When H 1 and H 2 are finitely generated, then their pullback is a finite set. For an injective endomorphism φ : F → F and k ≥ 1, define the iterated (algebraic) pullbacks of φ to be Λ k (φ) = φ k (F ) ∧ φ k (F ). Furthermore, the iterated pullback depends only on the outer class [φ] and will be denoted later by Λ k [φ]. In this section, we will simply write Λ k for brevity.
The (algebraic) mapping torus of an injective endomorphism φ is the ascending HNN extension of F with the presentation F * φ = F, t | t −1 xt = φ(x), ∀x ∈ F . We now give a third description of Λ k that will actually be the working description. The mapping torus F * φ is the fundamental group of a circle of groups with one vertex group F and edge group F . The edge monomorphisms for this circle of groups are the identity map id F : F → F and endomorphism φ : F → F and the corresponding Bass-Serre tree T has one orbit of edges and vertices. The tree also comes with a natural orientation where each vertex has exactly one outgoing oriented edge and the stable letter t ∈ F * φ acts on its directed axis with positive translation.
By construction, there is a vertex of T whose stabilizer in F * φ is exactly F . Let T F be the full subtree of T rooted at . Colloquially, T F is the family tree of -descendants. We will use the action of F * φ on T to index the vertices of T F by cosets in F . The root is indexed gF , where gF = F is the coset of F in F . The k th -generation vertices gt −k · are indexed by the cosets gφ k (F ) in F . The intersection corresponds to the simultaneous stabilizer of the ordered pair of vertices indexed by g 1 φ k (F ) and g 2 φ k (F ); the intersection is conjugate in F to the stabilizer of the vertices indexed by φ k (F ) and gφ k (F ), where g = g −1 1 g 2 . The intersection is also conjugate (in F ) to the stabilizers of the vertices indexed by φ k (F ) and hgφ k (F ), where h ∈ φ k (F ). Thus, F -orbits of k th -generation ordered pairs of vertices are indexed by φ k (F )-double cosets in F and conjugacy classes of their nontrivial stabilizers are the components of Λ k .
There is a function φ| Λ k : Λ k → Λ k+1 induced by φ, given algebraically by Graphically, the function maps (the conjugacy class of) the stabilizer of (g 1 t −k , g 2 t −k ) · to (the conjugacy class of) the stabilizer of t −1 · (g 1 t −k , g 2 t −k ) · .
Lemma 5.1. φ| Λ k : Λ k → Λ k+1 as a function on the set of components is injective.
Graphical proof. If t −1 · (g 1 t −k , g 2 t −k ) · and t −1 · (g 1 t −k , g 2 t −k ) · are in the same F -orbit, then they are in fact in the same φ(F )-orbit (descendants of t −1 · ). So (g 1 t −k , g 2 t −k ) · and (g 1 t −k , g 2 t −k ) · are in the same F -orbit by the action of t.
One can give an algebraic proof of the lemma that replaces the action of t with the injectivity of φ. The lemma implies there is a chain of injections Λ 0 → Λ 1 → Λ 2 → · · · . Furthermore, the restriction to each component is an isomorphism since it is a conjugation by t in F * φ . We will be mainly interested in the set complimentΛ k = Λ k \ φ(Λ k−1 ).
Graphically,Λ k is the set of components that stabilizes F -orbits of k th -generation pairs of vertices in T F whose only common ancestor is . We might say iterated pullbacks stabilize ifΛ k = ∅ for some k. The image φ(F ) is malnormal in F if and only ifΛ 1 = ∅. Iterated pullback stability is a sort of generalization of malnormality for φ k (F ) with respect to φ.
Lemma 5.2. Suppose φ : F → F is injective and k ≥ 1. IfΛ k is empty, then so isΛ k+1 ; and ifΛ k has only cyclic components, thenΛ k+1 is empty or has only cyclic components.
Proof. There is an "inclusion" of components,Λ k+1 Λ k , since a stabilizer of a (k+1) thgeneration pair of vertices is contained in a stabilizer of a k th -generation pair of vertices. SoΛ k = ∅ impliesΛ k+1 = ∅. SupposeΛ k has cyclic components, thenΛ k+1 is empty or has cyclic components as the subgroups of a cyclic group are trivial or cyclic.
The reduced rank of a nontrivial finite rank free group H is rr(H) = rank(H) − 1 and the reduced rank of a pullback H 1 ∧ H 2 , where H 1 , H 2 are finitely generated free groups, is the sum of the reduced ranks of components in H 1 ∧ H 2 . The latter is denoted by rr (H 1 ∧ H 2 ). Since the restriction φ| Λ k gives natural isomorphisms of the components, the chain of injections produces a nondecreasing sequence of positive integers Observe that rr(Λ i ) = rr(Λ i+1 ) if and only ifΛ i+1 is empty or has cyclic components only. By Lemma 5.2, the sequence becomes constant once two consecutive entries are equal.
Walter Neumann used topological pullbacks of Stallings graphs to bound the reduced ranks of algebraic pullbacks and improve Hanna Neumann's bound [25]. Remark. Although this bound is weaker than the Strengthened Hanna Neumann Conjecture, now Friedman-Mineyev's Theorem [11,19], it is sufficient for our purposes. W. Neumann's proof is an elementary Euler characteristic computation for the topological pullback.
The uniform bound given by W. Neumann's theorem allows us to conclude that the sequence of reduced ranks given above is eventually constant, and hence, past a certain point we are adding only cyclic components or nothing at all to the iterated pullbacks. Lemma 5.4. If φ : F → F is injective, then eitherΛ k has cyclic components for all k ≥ 2 rr(F ) 2 orΛ k = ∅ for some k.
Proof. Theorem 5.3 gives us a uniform bound on the reduced ranks of the iterated pullbacks rr(Λ k ) ≤ 2 rr(φ k (F )) 2 = 2 rr(F ) 2 for all k ≥ 1. By Lemma 5.2 and the uniform bound on the nondecreasing sequence of reduced ranks, rr(Λ k ) are all equal for k ≥ k 0 = 2 rr(F ) 2 . Therefore,Λ k 0 is empty or has only cyclic components. The lemma follows by inductively applying Lemma 5.2.
We say φ : F → F has an invariant cyclic subgroup system with index d ≥ 1 if there is an integer k ≥ 1, element x ∈ F , and nontrivial cyclic subgroup c ≤ F such that φ k ( c ) ≤ x c x −1 and has index d. Note that this is actually a property of the outer endomorphism [φ]. We can now give the main result of this section: Proposition 5.5. Let φ : F → F be injective. IfΛ k is not empty for all k ≥ 1, then [φ] has an invariant cyclic subgroup system with index d ≥ 2.
Proof. Let k 0 = 2 rr(F ) 2 and φ : F → F be an injective endomorphism such thatΛ k is not empty for all k ≥ 1. By Lemma 5.4,Λ k has cyclic components for k ≥ k 0 .
So far nothing in the section has used relative immersions but our main motivation for constructing them was this proposition. Note thatΛ 1 = ∅ automatically implies φ is not surjective. So φ is injective but not surjective. By Theorem 4.5, there is an expanding A * -relative immersion f : T → T for φ, where A * is the [φ]-elliptic free factor system and T is an (F, A * )-tree. Recall that the equality φ −1 · A * = A * is part of our definition of A * -relative representatives. An element of F is elliptic if it fixes a point on T , i.e., its conjugacy class is carried by A * . By construction of the [φ]-elliptic free factor system (Proposition 2.4), there is an m ≥ 1 such that [φ k (g)] is carried by the maximal [φ]-fixed free factor system A for all k ≥ m and elliptic g ∈ F . As A is a [φ]-fixed free factor system, the components of φ k (A) are free factors of F for all k.
∈Λ k for some k ≥ k 1 = max(k 0 , m + 1). As k ≥ k 0 , this component is cyclic and we may assume it has a representative φ k (F ) ∩ gφ k (F )g −1 generated by a nontrivial element φ k (x) ∈ φ k (F ). In particular, there exists φ k (y) ∈ φ k (F ) and g ∈ F \ φ(F ) such that φ k (x) = gφ k (y)g −1 . We first show that x is loxodromic, i.e., not elliptic. Suppose x ∈ F is elliptic, i.e., A * carries [x]. Then some free factor φ k (A) ∈ φ k (A) carries [φ k (x)] = [φ k (y)] as k ≥ m + 1. So y must be elliptic too since φ −1 · A * = A * and, as noted in the previous paragraph, φ m (A) carries φ m (x) and φ m (y). Thus, up to conjugation in F , we may assume φ m (x), φ m (y) ∈ φ m (A) and, up to conjugation in φ k−m (F ), we may assume φ k (x), φ k (y) ∈ φ k (A). Malnormality of the free factor φ k (A) implies g ∈ φ k−m (F ). But k − m ≥ 1 leads to the contradiction g ∈ φ(F ). Therefore, x is loxodromic. The integer k ≥ k 1 and component [ φ k (x) ] ∈Λ k were arbitrary, so all components ofΛ k are loxodromic for k ≥ k 1 . Recall from the proof of Lemma 5.2 that there is an infinite descending chain: SinceΛ k 1 has finitely many components and the components are all cyclic, there is a cyclic component inΛ k 1 which "carries" some component ofΛ k for all k ≥ k 1 . Suppose this component has a representative generated by c = φ k 1 (x) ∈ φ k 1 (F ). Then for all k ≥ k 1 , there is a cyclic component ofΛ k with a representative generated by φ k (x k ) ∈ φ k (F ) such that c carries φ k (x k ) . If we let α ⊂ T be the axis for element c, then the previous sentence implies there are sequences of element (x k ) k≥k 1 and (t k ) k≥k 1 such that the (unoriented) axes of φ k (x k ) are all translates t k · α of the (unoriented) axis α.
For any k ≥ k 1 , replace x k with its inverse if necessary so that the action of φ k (x k ) on its axis is coherent (respects orientation) with the action of c on α. By passing to a strictly increasing subsequence (k i ) i≥1 , we may assume there is an oriented edge e of T such that the axes α k i of (x k i ) i≥1 all contain a translate of e. We now pass to the graph of groups Γ = F \T in order to avoid mentions of translates and orbits. The axis α will project to an immersed loopᾱ in Γ representing c and axes α k i project to immersed loopsᾱ k i that represent x k i and whosef k i -image is a powerᾱ d i up to rotation/cyclic homotopy, where d i ≥ 1 andf : Γ → Γ is the immersion induced by f : T → T . The edge e projects to an edgeē that is contained in all the loopsᾱ k i for i ≥ 1 The proof now mimics the proof of [23,Proposition 3.11]. Since f is an immersion, it maps axes in T onto axes andf maps immersed loops in Γ to immersed loops. Sof k i (ē) is a subpath of the immersed loopf k i (ᾱ k i ) ᾱ d i for all i, and since f is expanding,f k i (ē) contains arbitrarily long powers ofᾱ as i → ∞. Set N to be the number of subpaths ofᾱ (up to rotation) that are also loops. Choose n 0 such thatf kn (ē) contains the loopᾱ N +1 as a subpath. Thenf k n+1 (ē) is a subpath ofᾱ d n+1 that contains the loopf k n+1 −kn (ᾱ N +1 ) as a subpath. In fact, for all positive integers j ≤ N + 1, the loopf k n+1 −kn (ᾱ j ) is a subpath ofᾱ d n+1 . Thus, there is a sequence of loops ( j ) N +1 j=1 that are subpaths ofᾱ and strictly increasing positive integers (s j ) N +1 j=1 such thatf k n+1 −kn (ᾱ j ) · j isᾱ s j up to rotation. By definition of N and pigeonhole principle, some t = t = for some t < t andf k n+1 −kn (ᾱ t −t ) isᾱ s t −st up to rotation. Lifting back to the (F, A)-tree T , we find that f k n+1 −kn maps the axis α to a translate of itself. So φ k n+1 −kn (c) is conjugate to a nontrivial power c d and d ≥ 2 since f is expanding.

Remark.
A careful examination of the proof reveals that it can be made "more effective" with the pigeonhole principle. For any expanding relative immersion f , we can construct a specific number k = k(f ) for whichΛ k = ∅ implies φ has an invariant cyclic subgroup system with index d ≥ 2. Thus, one would not have to check infinitely many iterated pullbacks of φ to know that an invariant cyclic subgroup system with index d ≥ 2 exists. Of course, for this to be useful, we need to know whether finding the [φ]-elliptic free factor system and expanding relative immersion for φ can be made effective. Finally, we remark that the converse of Proposition 5.5 holds but we omit the proof as it is not needed for the rest of the paper.
In the next section, we will actually be using the contrapositive of the proposition: if φ is injective and has no invariant cyclic subgroup system with index d ≥ 2, then iterated pullbacks of φ stabilize. In this case, we get control on the types of annuli in the mapping torus F * φ , which allows us to prove the main theorem: F * φ is word-hyperbolic if φ additionally has no fixed cyclic subgroup system, i.e., invariant cyclic subgroup system with index d = 1.

Hyperbolic endomorphisms
We are finally ready to put all the major pieces together. The first piece involves understanding the relationship between annuli in the mapping torus F * φ and iterated pullbacks of φ. The second piece involves building on Brinkmann's theorem to show that atoroidal injective endomorphisms are hyperbolic. In our previous work [23], we used these two pieces to give sufficient conditions for the mapping torus to be word-hyperbolic. Theorem 6.4]). If f : Γ → Γ is a based-hyperbolic graph map and all strictly bidirectional annuli in its mapping torus M f are shorter than some integer, then π 1 (M f ) is word-hyperbolic.
We will define the new terms in the theorem as we go. Suppose φ : F → F is an injective endomorphism and f : Γ → Γ is its topological representative. Recall that the (topological) mapping torus of f is the quotient space 0) for all x ∈ Γ and the algebraic mapping torus F * φ is isomorphic to the fundamental group π 1 (M f ). The edge-space of M f will be the crosssection in M f represented by Γ × { 1 2 }. Strictly bidirectional annuli of the mapping torus M f with length 2L can be thought of as the iterated pullbacksΛ L of φ but it does take a bit of work to give the correspondence. This is the definition used in [23]. In light of our last description ofΛ k in the previous section, we give alternative definition. Let T be the Bass-Serre tree for F * φ and be the point whose stabilizer is F . An (algebraic) annulus ([α], p α ) in F * φ of length L ≥ 2 is a choice a nontrivial conjugacy class [α] in F * φ and an orbit of a geodesic path in p α ⊂ T of length L fixed by α. Since elements of [α] act on T with fixed points, we can always choose a representative α ∈ F . Technically, we have defined a conjugacy class of algebraic annuli but the distinction will not be relevant for us.  (1) and (4), the midpoints extend to a geodesic edge-path p α in T of length L + 1 fixed by α.
The other direction works in a similar fashion. For any conjugacy class [α] in F * φ and two consecutive edge-midpoints in T F fixed by α ∈ F , we can construct an annulus of length 1 as follows. Fix a basepoint in the edge-space and assume is the vertex between the midpoints. If the midpoints are increasing/decreasing, then α = φ(x) ∈ φ(F ) without loss of generality. Let σ, ρ be based loop in the edge-space representing x, φ(x) ∈ F and τ a based loop in M f representing t ∈ F * φ . Then the based path σ · τ ·ρ ·τ is null-homotopic and can be extended to an annulus with ends σ, ρ and trace τ . If the midpoints are at the same height, then α = φ(x) ∈ φ(F ) and α = gφ(y)g −1 ∈ gφ(F )g −1 for some g / ∈ φ(F ). Let σ, ρ, γ be based loops in the edge-space representing x, y, g ∈ F respectively and τ a based loop in M f representing t ∈ F * φ . So the based path σ · τ γτ ·ρ · τγτ is null-homotopic and can be extended to an homotopy between σ, ρ satisfying Conditions (1)-(3) and having trace τ γτ . This trace satisfies Condition (4) because tgt −1 / ∈ F and thus the homotopy is a topological annulus with ends σ, ρ. Given a geodesic path in T of length L ≥ 2 fixed by α, we can replace the path with a translate in T F without affecting the class [α] and then construct a topological annulus in M f of length L − 1 by concatenating the length 1 annuli from the preceding discussion. This concludes the correspondence between topological and algebraic annuli.
The natural orientation on T gives a dichotomy for annuli ([α], p α ) in F * φ : 1. all edges of p α have the same orientation-we say α is unidirectional.
2. p α switches from increasing to decreasing exactly once -we say α is bidirectional.
Each vertex of T has exactly one outgoing edge and hence the geodesic p α cannot switch from decreasing to increasing because [F : F ] = 1. For similar reasons, bidirectional annuli do not exist if and only if φ(F ) is malnormal in F . The next proposition generalizes this equivalence of bidirectional annuli (or lack thereof) and malnormality.
An annulus ([α], p α ) in F * φ is strictly bidirectional if the switch from increasing to decreasing occurs at the midpoint of p α . Proof. If there is a strictly bidirectional annulus ([α], p α ) in F * φ of length 2L, then we may assume the midpoint of p α is after replacing p α with a translate. Then the stabilizer of p α contains α and so it is nontrivial. Since the stabilizer of p α is the stabilizer of its (ordered) endpoints, the conjugacy class of the stabilizer is a component ofΛ L [φ].
IfΛ L [φ] is not empty, then some path in T F of length 2L with midpoint at has a nontrivial stabilizer. Choose a nontrivial element α in this stabilizer and ([α], p α ) is a strictly bidirectional annulus in F * φ of length 2L.
Let φ : F → F be injective and f : Γ → Γ be a topological representative for φ. If [φ] has no invariant cyclic subgroup system with index d ≥ 2, then there is an integer L ≥ 1 for whichΛ L [φ] is empty (Proposition 5.5) and all strictly bidirectional annuli in M f are shorter than 2L (Lemma 6.3). This sets up the second hypothesis of Theorem 6.1.
As for the first hypothesis, we begin by defining (based-) hyperbolicity. For a real number λ > 1 and integer n ≥ 1, we say a graph map f : Γ → Γ is (based-) (λ, n)-hyperbolic if all (based) loops σ : S 1 → Γ (with the basepoint mapped to a vertex) satisfy the inequality where | · | is the combinatorial length after tightening; whether tightening respects a basepoint (based homotopy) or not (free homotopy) will be apparent from the context. When a graph map is (based-) (λ , n)-hyperbolic for some λ > 1, n ≥ 1, then it is (based-) (λ k , nk)-hyperbolic for all k ≥ 1 and λ ∈ (1, λ ]. So the constants can be omitted and when we do need them, we can assume λ > 1 is any preferred integer. As defined, hyperbolicity is a property of the homotopy class [f ]. Meanwhile, based-hyperbolicity is a property of the map f . A graph map f : Γ → Γ is atoroidal if it is π 1 -injective and there is no nontrivial loop σ in Γ and integer k ≥ 1 such that f k (σ) σ. This again is a property of the homotopy class [f ]. Bestvina-Feighn-Handel showed, as a step in [4,Theorem 5.1], that hyperbolic atoroidal homotopy equivalences are based-hyperbolic. Their argument is reproduced here, modified to drop the π 1 -surjectivity assumption. This allows us to consider the growth rate of loops without basepoints for the rest of the section Lemma 6.4. If the graph map f : Γ → Γ is atoroidal and (3, n)-hyperbolic, then it is based-(2, n )-hyperbolic.
To avoid context-ambiguity in the proof, we use · for lengths of free homotopy classes of loops and | · | for lengths of loops rel. basepoints. However, the distinction is not needed after the proof as all loops afterwards will be considered up to free homotopy.
Proof. Suppose f : Γ → Γ is atoroidal and (3, n)-hyperbolic for some integer n ≥ 1. Set M to be the maximum length of f k (s) rel. basepoint over all embedded based loops s in Γ for k ∈ {0, n, 2n}.
Since f is atoroidal, there is an integer k 0 such that |f nk (σ )| ≥ 8M for every based loop σ with |σ | ≤ 4M and we conclude that f is based-(2, nk)-hyperbolic .
When p is a subpath of an immersed loop σ and n ≥ 1, then [f n (p)] σ is the subpath of [f n (p)] that survives in [f n (σ)] and |f n (p)| σ is the length of [f n (p)] σ . Bounded cancellation implies |f n (p)| ≤ |f n (p)| σ + 2C(f n ). The next lemma is based on Brinkmann's Lemma 4.2 in [8] with a few changes made to account for graph maps that are not π 1 -surjective. Lemma 6.5. Let f : Γ → Γ be a graph map and R * ⊂ Γ be an f -invariant union of roses such that the restriction f | R * : R * → R * is (4, n)-hyperbolic. For some constant L c , if p ⊂ R * is a subpath (edge-path) of some immersed loop σ in Γ and |f n (p)| σ ≥ L c , then The number L c is the critical length of the triple (f, Γ, R * ).
Proof. Let f : Γ → Γ be a graph map and R * ⊂ Γ be an f -invariant union of roses such that the restriction f | R * is (4, n)-hyperbolic. Set M to be the maximum length of f k (s) rel. basepoint over all petals s in R * and k ∈ {n, 2n}. Choose L c = 2C(f 2n ) + 5M where C(f 2n ) is the cancellation constant for f 2n . Recall the triangle inequality: | |p 1 | − |p 2 | | ≤ |p 1 · p 2 | ≤ |p 1 | + |p 2 | for any path decomposition of a loop p 1 · p 2 . A remark on the context: paths [p i ] are tightened rel. endpoints but the loop [p 1 · p 2 ] is tightened by free homotopy.
Proof. Suppose φ : F → F is an injective and atoroidal endomorphism. If φ is surjective, then the proposition is precisely Brinkmann's result. So we assume φ is not surjective. By Theorem 4.5, there is an expanding A * -relative immersion g : T → T for φ, where A * is the [φ]-elliptic free factor system. Fix some A * -marked roses (R A * , α A * ) and set (Γ, α) to be the (R A * , α A * )-vertex blow-up of the graph of groups F \T , i.e., (Γ, α) is a marked graph with subgraphs R A * corresponding to the free factor system α(A * ). The roses R A * form the lower stratum of Γ and the remaining edges the top stratum.
We outline the proof which follows closely Brinkmann's strategy. Patch together a homotopy equivalence of the lower stratum with the expanding relative immersion to get some topological representative f of [φ]. By Brinkmann's theorem, the restriction of f to the lower stratum is hyperbolic. The expanding relative immersion on the top stratum means loops that are mostly top stratum will have uniform exponential growth under forward iteration. Lemma 6.5 implies loops that are mostly lower stratum will have uniform exponential growth under forward and/or backward iteration. The heart of the proof lies in quantifying what being mostly top or lower stratum means and showing that all loops are one or the other. Of course, there are a few minor technicalities that need addressing; for instance, the restriction to the lower stratum is almost but not exactly a homotopy equivalence. This concludes the outline.
Recall that the maximal [φ]-fixed free factor system A is a subset of A * and there is an integer k 0 ≥ 0 such that φ k 0 (A * ) is carried by A (Proposition 2.4). So we may find a topological representative f A * : R A * → R A * for [ φ| A * ] whose restriction to the periodic roses R A , denoted by f A , is a homotopy equivalence. As φ is atoroidal, the restriction f A is (4, n 0 )-hyperbolic for some n 0 ≥ 1 (Brinkmann's theorem).
If σ is an immersed loop in R A * , then [f k (σ)] is a loop in the periodic roses R A for all k ≥ k 0 . Since the restriction f A is (4, n 0 )-hyperbolic and f n 0 k A * (σ) is a loop in R A for any loop σ in R A * and k ≥ k 0 , we get the inequality Choose an integer k 1 ≥ 1 so that 4 (σ))|, then by induction (σ)|, then by induction and Lipschitz property 4 k 1 · |f and 4 · |f n 0 (k 0 +k 1 ) A * (σ)| ≤ |σ| by choice of k 1 . Therefore, the lower stratum map f A * is (4, n 1 )-hyperbolic with n 1 = n 0 (k 0 + k 1 ).
Let f : Γ → Γ be a topological representative for [φ] that extends f A * to the top stratum and induces the expanding A * -relative immersion g : T → T upon collapsing the lower stratum in the universal coverΓ. For an arbitrary immersed loop σ in Γ, define σ top (σ low resp.) to be the collection of maximal subpaths of σ in the top (lower resp.) stratum. For all n ≥ 1, define [f n (σ top )] σ ([f n (σ low )] σ resp.) to be the collection of paths [f n (p)] σ where p is some path in σ top (σ low resp.). That f induces an immersion g upon collapsing the lower stratum implies that the top stratum is persistent: if σ is an immersed loop in Γ, then f (σ) top survives in [f (σ)].
As the relative immersion g : T → T is expanding, there is an integer k 2 ≥ 1, such that g k 2 (e) has length ≥ 2 for all edges e in T ; and as f induces g, for any immersed loop σ in Γ and path p in σ top , we get 2|p| σ ≤ |f k 2 (p)| σ . We may replace n 1 and k 2 with a common multiple and assume n 1 = k 2 . A similar inequality holds in the lower stratum. By the (4, n 1 )-hyperbolicity of f | R A * and Lemma 6.5, there is a critical length L c = L c (f, Γ, R A * ) such that for any immersed loop σ in Γ and path p in σ low , Set M to be the maximal length amongst all paths in f n 1 (e) low for all top stratum edges e of Γ. For any integer k ≥ 1, we distinguish two cases: Case 1. If |f n 1 k (σ) low | ≤ (L c + 6M ) |f n 1 k (σ) top |, then Additionally, if 2 k ≥ 2(L c + 6M + 1), then 2 |f n 1 k (σ)| ≤ |f 2n 1 k (σ)|. Case 2. Suppose |f n 1 k (σ) low | ≥ (L c +6M ) |f n 1 k (σ) top |. Set m to be the number of paths in f n 1 k (σ) low . Then m is also the number of paths in f n 1 k (σ) top and m ≤ |f n 1 k (σ) top |. By the pigeonhole principle, some path ρ in f n 1 k (σ) low satisfies |ρ| ≥ L c + 6M . As |ρ| ≥ 6M , we have 3(|ρ| − 2M ) ≥ 2|ρ|. Set σ = f n 1 (k−1) (σ). By definition of M and persistence of f n 1 (σ ) top , there must be a path p in σ low such that [f n 1 (p )] σ is a subpath of ρ, |f n 1 (p )| σ ≥ |ρ| − 2M ≥ L c , and 3 |f n 1 (p )| σ ≤ max( |f 2n 1 (p )| σ , |p | ).

HNN extensions over free factors
In the last section, we extend the previous characterization to HNN extensions of free groups defined over free factors. Precisely, let A ≤ F be a (nontrivial) free factor and φ : A → F be an injective homomorphism. The HNN extension of F over A is given by: HNN extensions, just like mapping tori, have associated Bass-Serre trees which we can use to define algebraic annuli as in the previous section. Unlike the Bass-Serre tree of a mapping torus, that of an HNN extension need not behave like a rooted tree: generally, the number of outgoing and incoming edges at a vertex will match the indices of A and φ(A) in F respectively. However, since free factors are malnormal, these HNN extensions share with mapping tori the dichotomy of annuli: annuli are either unidirectional or bidirectional. We will say a conjugacy class of elements [g] in F has one forward iterate if it is contains an element a ∈ A. By malnormality of A, the conjugacy class of [φ(a)] depends only on the class [g]. We set the forward iterate of such a class [g] to be φ · [g] = [φ(a)].
Similar to our use of infinite tails (backward iteration) to construct a canonical fixed free factor system in Section 2, we shall use forward iteration to construct a canonical invariant free factor system of A. The proof will use a simpler variation of descent.
Proposition 7.1. If A ≤ F is a free factor and φ : A → F is injective, then there is a unique maximal [φ]-invariant free factor system of A. Precisely, F carries every conjugacy class with 2 · rank(A) forward iterates and every [φ]-invariant subgroup system.
Proof. Let A ≤ F be a free factor, φ : A → F be injective, and L(A) − 1 = 2 · rank(A) − 1 be the length of the longest chain of free factor systems in A. Any conjugacy class in a [φ]-invariant free factor system of A has infinitely many forward iterates. So if only the trivial conjugacy class has L(A) forward iterates, then the trivial system is the unique [φ]invariant free factor system. Thus, we may assume some fixed nontrivial conjugacy class [g] has L(A) forward iterates. Since A ≤ F is a free factor and φ : A → F is injective, we can iterate φ −1 on the poset of free factor systems of A! Claim (Descent). For some n ≥ 0, let A n ≺ · · · ≺ A 0 be the chain of nontrivial free factor systems of A such that Starting with {A}, the descent will eventually stop at some n < L(A) − 1 with a nontrivial free factor system A n = φ −n · {A} that carries all conjugacy classes with n + 1 forward iterates and all [φ]-invariant subgroup systems of A. Since descent stopped, A n must be [φ]-invariant and hence the unique maximal system amongst all [φ]-invariant free factor systems of A.
Proof of descent. Let n ≥ 0 and A n ≺ · · · ≺ A 0 = {A} be the chain of nontrivial free factor systems such that A i = φ −i · {A} and A n carries all [φ]-invariant subgroup systems of A. Nontriviality of A n implies n < L(A) − 1. Now suppose that A n is not [φ]-invariant.
The existence of a nontrivial conjugacy class [g] with L(A) ≥ n + 2 forward iterates implies A n+1 = φ −1 · A n is a nontrivial free factor system of A. If n = 0, then clearly A n+1 A n . If n > 1, then A n ≺ A n−1 by assumption; hence, φ −1 · A n φ −1 · A n−1 and, equivalently, By assumption, A n carries B and φ(B); therefore, A n+1 = φ −1 · A n carries B.
The unique [φ]-invariant free factor system of A given by Proposition 7.1, denoted by F, is the canonical [φ]-invariant free factor system and it captures the long-term dynamics of [φ]. The system F is proper (in A) if and only if A is not [φ]-invariant; it is trivial exactly when only the trivial conjugacy class has L(A) = 2 · rank(A) forward iterates. The canonical invariant free factor system allows us to naturally extend definitions and results that required iteration of an injective endomorphism. For instance, we can now say φ : A → F has an invariant cyclic subgroup system with index d ≥ 1 if a restriction φ| F : F → F has an invariant cyclic subgroup system with index d ≥ 1. In For k ≥ L(A), we define the iterated pullbacks Λ k [φ] of [φ] to be the iterated pullbacks Λ k [ φ| F ] of the restriction [ φ| F ]. Similarly defineΛ k for k ≥ L(A). Since connectedness did not play any role in the proof of Proposition 5.5, we immediately get the following extension when we replace endomorphisms of F with endomorphisms of F.
is not empty for all k ≥ L(A), then φ has an invariant cyclic subgroup system with index d ≥ 2.
Remark. By the same token, the results in this section do not need A to be "connected." So there is a natural generalization of these results that easily follows if we replace the free factor A ≤ F with a free factor system A of F .
For the rest of the section, we will extend the results of Section 6 to the injective homomorphism φ : A → F . Fix a marked graph (Γ, α) such that the free factor systems F and A correspond to nested core subgraphs Γ F ⊂ Γ A ⊂ Γ respectively, i.e., Γ F and Γ A have markings α F : F → π 1 (Γ F ) and α A : A → π 1 (Γ A ) respectively such that the inclusion maps Assume F is not trivial so that Γ F is not degenerate (finite set of points). A topological representative for [φ] will be a graph map f : Thus, the invariant restriction f | F : Γ F → Γ F is a topological representative for the restriction [ φ| F ].
The following is the analogue of the mapping torus. Let f be a topological representative for φ : A → F . We define the classifying space to be M f = (Γ (Γ A × [0, 1])) / ∼ where we identify (x, 0) ∼ x and (x, 1) ∼ f (x) for all x ∈ Γ A ⊂ Γ. The edge-space of M f will be the cross-section represented by Γ A × { 1 2 }. By construction, π 1 (M f ) ∼ = F * A . Topological annuli in M f and algebraic annuli in F * A are defined exactly as before and the correspondence between them is the same. Similarly, the correspondence between strictly bidirectional annuli and the iterated pullbacks remains. We then get this natural extension of Lemma 6.3. The definition of (based-) hyperbolicity extends naturally using the invariant restriction. For λ > 1 and n ≥ L(A), a topological representative f : (Γ A , Γ F ) → (Γ, Γ F ) for [φ] is (based-) (λ, n)-hyperbolic if f | F : Γ F → Γ F is (based-) (λ, n)-hyperbolic and [f ] is atoroidal if [ f | F ] is atoroidal. When F is trivial, any topological representative of φ is The proof follows the same steps as Theorem 6.7 and the only missing ingredient is an extension of Theorem 6.1 (Theorem 7.7 below) that proves the implication (4) =⇒ (1).
Remark. Every HNN extension of the form F * A where F is a finite rank free group and A ≤ F is a free factor can be written as a mapping torus F * ψ of an injective endomorphism ψ : F → F where F is a free group with possibly infinite rank. Conversely, every finitely generated subgroup of a mapping torus F * ψ where F has possibly infinite rank can be written as an HNN extension F * A where F has finite rank and A ≤ F is a free factor [9]. This argument is Feighn-Handel's result that F * A and F * ψ are coherent. As a corollary, we get the following amusing statement: Corollary 7.6. Let ψ : F → F be an injective endomorphism of an infinite rank free group. F * ψ is locally word-hyperbolic if and only if it contains no BS(1, d) subgroups with d ≥ 1.
By locally word-hyperbolic, we mean every finitely generated subgroup is word-hyperbolic.
The following theorem will complete our proof of Theorem 7.5.
Theorem 7.7. Let A ≤ F be a free factor and φ : A → F be injective. If a topological representative f of [φ] is based-hyperbolic and all strictly bidirectional annuli in its classifying space M f are shorter than some integer, then F * A is word-hyperbolic.
Roughly speaking, the extension follows from the fact that annuli of M f longer than L(A) are annuli of the mapping torus of f | F up to some controlled error. Due to the close similarity with the proof of Theorem 6.1 given in [23], we will only sketch a proof of the extension. Let A n ≺ · · · ≺ A 0 ≺ A −1 be the chain where A −1 = {F }, A 0 = {A}, A n = F, and generally A i = φ −i · {A} for 0 ≤ i ≤ n. By invariance of A n , we can extend the chain by setting A i = A n for i > n. For 0 ≤ i < n, A i−1 carries φ(A i ) by definition. We assume Γ has a filtration of nonempty core subgraphs · · · ⊂ Γ 1 ⊂ Γ 0 ⊂ Γ −1 where Γ −1 = Γ F ∨ R is a wedge between Γ F and a rose R and each Γ i is a A i -marked graph. If n > 0, we will also assume the topological representative f : (Γ 0 , Γ n ) → (Γ −1 , Γ n ) is of the form (Γ 0 , . . . , Γ n−1 , Γ n ) → (Γ −1 , . . . , Γ n−2 , Γ n ). Note that since Γ n = Γ F was f -invariant to begin with, changes can made to the given representative f to allow for these additional assumptions without affecting the invariant restriction f | F . So f is still based-hyperbolic after the changes.
Using this filtration, we introduce a tool needed to iterate based loops not in Γ F : for any integer i ≥ 0 and any immersed based loop s : S 1 → Γ 0 that is freely homotopic into Γ F , there is a "closest point" projection (with respect to Hausdorff distance of lifts to the universal cover) of s to an immersed based loop in Γ 0 denoted by s i : S 1 → Γ 0 freely homotopic to s such that f i ( s i ) is a based loop in Γ 0 . Recall that based loops must send basepoints to vertices. Since we assumed the "complement" of Γ n are roses, the projections s i are immersed based loops in Γ i . So s i = s n for i ≥ n. Implicit in this is the fact that, for all i ≥ 0, any conjugacy class carried by A i but not A i+1 is mapped by φ to a conjugacy class carried by A i−1 but not A i . We are ready to start proving the theorem.
By induction, the f -invariance of Γ n , and the fact M > L(A) > n, we get this inequality: Since f is based-(2, m)-hyperbolic, we know that There are three cases to consider of which we will only prove one.
part of the paper is the idea that F * φ is hyperbolic relative to a canonical finite collection of free-by-cyclic groups when it has no BS(1, d) subgroups for d ≥ 2. Furthermore, when A ≤ F is a free factor and ψ : A → F is injective, then F * A is hyperbolic relative to a canonical finite collection of ascending HNN extensions. This would imply that F * A has a quadratic isoperimetric function when it has no BS(1, d) subgroups for d ≥ 2. We intend to complete this direction in future work by employing a combination theorem for relatively hyperbolic groups [12,22].
When F * φ is word-hyperbolic, Mahan Mj proved there is a continuous extension to the Gromov boundary of the inclusion map F ≤ F * φ [21]; this map is known as the Cannon-Thurston map.
For the first of these questions, it seems that expanding relative immersions reduce the problem to the automorphism case, which has been answered [13,20]. As for the ending laminations, what is missing is the appropriate formulation of the theorem that replaces the usual short exact sequence with a graph of groups decomposition.
Levitt-Lustig covered the surjective case when they proved that most automorphisms of non-elementary word-hyperbolic groups have boundary extensions with north-south dynamics [18]: two fixed points -a repellor and an attractor. Expanding relative immersions should imply that most injective nonsurjective endomorphisms of F have sink dynamics: a single fixed point and it is an attractor.
There are of course more unresolved questions about injective endomorphisms and their expanding relative immersions. These are left for the reader to ask and answer.

A Relative train tracks
The objective in this appendix is to sketch the proof that irreducible relative representatives with minimal stretch factor are train tracks. Bestvina-Handel's construction of train tracks for irreducible automorphisms [6] translates verbatim to the non-free forest setting.
Let φ : F → F be an injective endomorphism, A ≺ B be [φ]-invariant free factor systems, and T * be a (B, A)-forest. We allow forests to have bivalent vertices. Recall, an A-relative weak representative for the restriction φ| B is a φ| B -equivariant graph map f * : T * → T * . An A-relative representative is an A-relative weak representative f * with no pretrivial edges and whose underlying forest T * has no bivalent vertices. Additionally, we say the relative representative is minimal if it has no orbit-closed invariant subforests with bounded components.
Sketch proof of Theorem A.1. Let φ| B be irreducible relative to A and f * : T * → T * be an irreducible A-relative representative. If λ(f * ) = 1, then f * is a simplicial embedding with minimal stretch factor and we are done. So we may assume λ(f * ) > 1.
Suppose for the contrapositive that f * is not an A-relative train track, then the edgepath f n * (e) is not immersed for some edge e in T * and integer n ≥ 1. Let n be the smallest such integer and assume is an interior point of an edge e at which f n * fails to be locally injective. We appropriately subdivide T * so that a neighborhood U of and its iterates f k * (U ) (1 ≤ k ≤ n) satisfy nice properties: 1) U is an interval whose boundary consists of distinct vertices; 2) f k * is locally injective on U for 1 ≤ k < n; 3) f n * folds U at to an edge; and 4) / ∈ f k * (U ) for 1 ≤ k ≤ n. We can then iteratively fold f n−1 * (U ), . . . , f 2 * (U ), and f * (U ). By minimality of n, all the folds except the last one induce an irreducible A-relative weak representative. By the first case of Lemma A.4, this irreducible A-relative weak representative has the same stretch factor as f * . By construction, the last fold induces a map f * that fails to be an A-relative weak representative as it fails to be locally injective at . We can apply a tightening homotopy on f * to make it locally injective at , then collapse a maximal invariant subforest with bounded components to get f * : T * → T * , a minimal A-relative weak representative for φ| B . By Lemma 3.6, the map f * is irreducible. By the second case of Lemma A.4, the stretch factor is strictly smaller: λ(f * ) < λ(f * ). We then sequentially apply bivalent homotopies and collapse maximal invariant subforests with bounded components until we get an irreducible A-relative representative f * . The stretch factor satisfies λ(f * ) ≤ λ(f * ) < λ(f * ) by Lemma A.3. So f * did not have minimal stretch factor.