1.1 The main technical result

In order to state our main technical result, Theorem 1.1, we require some notation and setup. As above, the surfaces in this paper are all of the form $S = S_{g,p}$ . Before we start in earnest, we give an abstract topological definition that will be used in the discussion of the space of measured foliations.

Integral cone complexes. In this paper, an integral cone complex is a sort of cell complex where a cell is a positive cone in some $\mathbb {R}^d$ defined as the set of solutions to a finite set of integer linear equations and integer inequalities; we will refer to such a cone as an integral linear cone. Such a cell has a finite set of faces, each being a cell in the same sense. Cells are glued along their faces, the gluing maps being linear.

We now present a basic example of an integral cone complex $Y_\Delta $ that we will treat as a running example. Let $V_1$ , $V_2$ , and $V_3$ each be the first quadrant in $\mathbb {R}^2$ . We glue the face of $V_i$ on the x-axis to the face of $V_{i+1}$ on the y-axis (subscripts considered modulo 3) by the map $(t,0) \mapsto (0,t)$ . The complex $Y_\Delta $ is homeomorphic to $\mathbb {R}^2$ .

The integral cone complex $Y_\Delta $ can be geometrically realized in $\mathbb {R}^3$ as the boundary of the first octant (by a geometric realization, we mean an embedding into $\mathbb {R}^N$ mapping cells to cells). The complex $Y_\Delta $ is also geometrically realized as the set of points in the first octant of $\mathbb {R}^3$ whose coordinates satisfy a degenerate triangle inequality, meaning that one coordinate is the sum of the other two. See Figure 1 for an illustration.

Figure 1

A geometric realization of the integral cone complex $Y_\Delta $ .

With the definition of an integral cone complex in hand, we have several further definitions to make:

1. (a) integral linear maps, integral cone complex maps, and linear regions,

2. (b) the projectivized complex, vertex rays, and induced maps,

3. (c) the radius,

4. (d) subdivisions for generating sets,

5. (e) PL-eigenvectors,

6. (f) PL-eigenregions,

7. (g) projectively source-sink integral cone complex maps, and

8. (h) extended dynamical maps and sink packages.

After making these definitions, we explain how to compute PL-eigenvectors explicitly.

(a) In the category of integral cone complexes, the natural maps $f : Y \to Y$ are integral cone complex maps, which we now define. First, suppose U is a subset of some cell V of Y; we say that a map $U \to Y$ is integral linear if the image is contained in a cell W and – using the V- and W-coordinates – the map is given by the restriction of an integral matrix.

With this definition in hand, a map $f : Y \to Y$ is an integral cone complex map if there is an integral cone complex subdivision $Y_f$ of Y so that the restriction of f to each cell of $Y_f$ is an integral linear map. If $V_i$ is a cell of Y we denote the cells of such a subdivision of $V_i$ by $V_{i,k}^f$ . We will refer to the cells of any such subdivision as linear pieces for f. These pieces are not canonical; the important feature for us is that each $V_{i,k}^f$ is determined by finitely many integer linear inequalities in the $V_i$ -coordinates.

If U is any integral linear cone contained in a cell V and U is also f-linear, then U can be extended to a subdivision $Y_f$ as above. Therefore, it makes sense to refer to any such U as a linear piece for f.

We may describe the action of f on an f-linear piece U by a 4-tuple $(A,V_i,V_j,U)$ , where $V_i$ and $V_j$ are cells of Y, the domain U is an integral linear cone contained in $V_i$ , the image $f(U)$ is contained in $V_j$ , and A is the matrix describing the action of f on the linear piece U in the given coordinates of $V_i$ and $V_j$ .

In our algorithms, it will suffice to record only the triple $(A,V_i,V_j)$ , omitting the domain. Indeed, by multiplying the matrices from these triples, we can obtain a matrix for the product of mapping classes without knowing the domain. In the case where $V_i$ is equal to $V_j$ , we may write $(A,V_i)$ instead of $(A,V_i,V_j)$ .

To illustrate, we return to our running example $Y_\Delta $ . Let

$$ \begin{align*} V_{1,1} &= \{ (x,y) \in V_1 \mid y \leq x \}, \text{and} \\ V_{1,2} &= \{ (x,y) \in V_1 \mid x \leq y \}. \end{align*} $$

There is an integral cone complex map $f_1$ given by the four 4-tuples

$$\begin{align*}\left( A_{1,1},V_1,V_1,V_{1,1}\right), \left(A_{1,2},V_1,V_2,V_{1,2}\right), \left(A_2,V_2,V_3,V_2\right), \text{ and } \left(A_3,V_3,V_3,V_3\right), \end{align*}$$

where

$$\begin{align*}A_{1,1} = \left(\begin{smallmatrix} 1 & -1 \\ 0 & 1 \end{smallmatrix}\right), \ \ A_{1,2} = \left(\begin{smallmatrix} 1 & 0 \\ -1 & 1 \end{smallmatrix}\right), \ \ A_2 = \left(\begin{smallmatrix} 1 & 1 \\ 0 & 1 \end{smallmatrix}\right), \ \ A_3 = \left(\begin{smallmatrix} 1 & 0 \\ 1 & 1 \end{smallmatrix}\right), \ \ \end{align*}$$

There is another cone complex map r given by permuting the $V_1$ cyclically, mapping each to the next by the identity matrix.

(b) If Y is an integral cone complex, there is a projectivized version of Y, denoted $\mathcal {P}(Y)$ , which is a cell complex in the usual sense. For instance, the projectivized complex for $\operatorname {\mathrm {MF}}(S)$ is $\mathcal {P}(\operatorname {\mathrm {MF}}(S)) = \operatorname {\mathrm {PMF}}(S)$ (Thurston described the $\operatorname {\mathrm {Mod}}(S)$ -action on $\operatorname {\mathrm {PMF}}(S)$ as opposed to $\operatorname {\mathrm {MF}}(S)$ ). If $f : Y \to Y$ is an integral cone complex map, then there is an induced cellular map $\mathcal {P}(Y_1) \to \mathcal {P}(Y_1)$ , where $Y_1$ is an integral cone complex subdivision of Y. We also define a vertex ray of an integral cone complex Y to be the ray corresponding to a vertex of $\mathcal {P}(Y)$ .

For our running example $Y_\Delta $ , the cell complex $\mathcal {P}(Y_\Delta )$ is a triangle. Under the geometric realization given by Figure 1, $\mathcal {P}(Y_\Delta )$ is identified with the triangle shown in the picture. There are three vertex rays in $Y_\Delta $ . The subdivision associated to the map $f_1$ is given by adding a vertex to $\mathcal {P}(Y_\Delta )$ corresponding to the ray spanned by $(1,1)$ in $V_1$ ; this is the midpoint of the $V_1$ -edge of $\mathcal {P}(Y_\Delta )$ .

(c) We now set out to define the radius of an integral cone complex Y – which we also refer to as the radius of $\mathcal {P}(Y)$ . First, we define a graph $\mathcal {G}_Y$ whose vertices are the top-dimensional cells of $\mathcal {P}(Y)$ and whose edges connect cells of $\mathcal {P}(Y)$ with nonempty intersection. For a set of vertices W of $\mathcal {G}_Y$ , we define the radius of Y at W to be the supremal distance in $\mathcal {G}_Y$ from a vertex of $\mathcal {G}_Y$ to W. For a vertex c of $\mathcal {P}(Y)$ , we define the radius of Y at c to be the radius of Y at $W_c$ , the set of top-dimensional cells of $\mathcal {P}(Y)$ containing c.

For the running example $Y_\Delta $ , the graph $\mathcal {G}_Y$ is a triangle (dual to $\mathcal {P}(Y_\Delta )$ ), and so the radius with respect to any W is at most 1. As another example, if Y is any triangulation of $S^2$ given by the equator and any number of longitudes, then the radius of Y with respect to the vertex at the north pole is 1. As we will see, this example mirrors the situation for $\operatorname {\mathrm {MF}}(S)$ .

(d) Suppose that G is a group that acts on the integral cone complex Y by integral cone complex maps, and say that G is generated by $\Gamma = \{h_\ell \}$ . We denote by $Y_\Gamma $ the collection of integral cone complex subdivisions $\{ Y_{h_\ell } \}$ (so there is one subdivision for each generator). As above, we denote the cells of the $h_\ell $ -subdivision of $V_i$ by $V_{i,k}^{h_\ell }$ .

If $\Gamma $ is finite, then there is a single subdivision (namely, the common refinement of the $Y_{h_\ell }$ ) with the property that each cell of the subdivision is a linear piece for each $h_\ell $ and $h_\ell ^{-1}$ . In practice, it is convenient to use a different subdivision for each generator since this reduces the number of calculations required.

(e) Let Y be an integral cone complex and let $f : Y \to Y$ be an integral cone complex map. For a point v in Y and a $\lambda \geq 0$ , the point $\lambda v$ is a well-defined point of Y. With this in mind, a PL-eigenvector for f is a point $v \in Y$ so that $f(v) = \lambda v$ for some $\lambda \geq 0$ . We emphasize that if A represents f on a cone V of Y, a real eigenvector v for A is not necessarily a PL-eigenvector for f. This is because v might not lie in the cone of $\mathbb {R}^d$ corresponding to V.

In our running example, the point $(1,0) \in V_1$ is a PL-eigenvector of the integral cone complex map $f_1$ described above, since it is an eigenvector of the matrix $A_{1,1}$ and since the domain of this linear piece is contained in the codomain. By the same token, $(0,1) \in V_1$ is not a PL-eigenvector of $f_1$ : it is an eigenvector of $A_{1,2}$ but its image is $(0,1) \in V_2$ , which is not identified with (any multiple of) $(0,1) \in V_1$ .

(f) Next, a PL-eigenregion for the integral cone complex map f is a linear piece U for f that contains a PL-eigenvector v. The linear transformation associated to $f|U$ will recognize v as an eigenvector. More specifically, if $f|U$ has the triple $(A,V_i,V_j)$ with $i=j$ then v will be a (classical) eigenvector for A. When $i \neq j$ , we can choose coordinates on $V_i$ and $V_j$ that agree on the cell $V_{ij} = V_i \cap V_j$ . In these coordinates, we again have that v is an eigenvector for A.

As part of our algorithm, we will find a point w with the property that it is contained in the interior of a union of PL-eigenregions for v. In such a case, there may be several different triples associated to the action of f at w, and hence several different matrices. However, all of these matrices will have v as an eigenvector.

In the running example, the map $f_1$ has two PL-eigenregions for the PL-eigenvector $(1,0) \in V_1$ , namely, $V_{1,1}$ and $V_3$ . We already discussed the former region. Similarly, $V_3$ is a PL-eigenregion for $f_1$ since $(0,1)$ is an eigenvector for $A_3$ and the third piece of $f_1$ has the same domain and codomain, which contains $(0,1)$ .

(g) Next, an integral cone complex map $f : Y \to Y$ is projectively source-sink if the induced cellular map $\mathcal {P}(Y) \to \mathcal {P}(Y)$ has source-sink dynamics. This means that the induced map has exactly two fixed points, the source and the sink, and that the f-iterates of all points outside of the source converge to the sink. In particular, the only two PL-eigenvectors for f (up to scale) are representatives of the source and the sink.

In the running example, if we take $f_2 = r \circ f_1 \circ r^{-1}$ , then the integral cone complex map

$$\begin{align*}f_2^{-1} \circ f_1 \end{align*}$$

is projectively source-sink. The sink and source correspond to the vectors $(\varphi ,1) \in V_3$ and $(1,\varphi ) \in V_1$ , where $\varphi $ is the golden mean. The corresponding triples are

$$\begin{align*}(D,V_3,V_3) \text{ and } (E,V_1,V_1) \end{align*}$$

where

$$\begin{align*}D = \left(\begin{smallmatrix} 2 & 1 \\ 1 & 1 \end{smallmatrix}\right) \text{ and } E = \left(\begin{smallmatrix} 2 & -1 \\ -1 & 1 \end{smallmatrix}\right). \end{align*}$$

(h) Let Y be an integral cone complex and $f : Y \to Y$ a projectively source-sink integral cone complex map. Let U be a PL-eigenregion for the sink of f with triple $(A,V_i,V_j)$ . There exists a maximal subcone W of $V_i \cap V_j$ invariant under f, and the map $f|W$ is a dynamical map in the sense that f maps W to itself. The cone W is nontrivial since it contains the ray corresponding to the sink. In Section 1.2 we give an algorithmic procedure to find W and to compute the linear map associated to $f|W$ . We also show that, in any $\mathbb {R}^d$ -coordinates on $V_i$ , the cone W is the intersection of $V_i$ with a subspace of $\mathbb {R}^d$ . Hence it makes sense to project $V_i$ onto W.

We prove in Lemma 7.4 that (under a certain condition about the location of the sink) the largest real eigenvalue of $f|W$ is the eigenvalue for the sink, and any corresponding positive eigenvector is the sink. If we precompose $f|W$ with a projection map $V_i \to W$ (really a projection of the corresponding subspaces of $\mathbb {R}^d$ ), we obtain a linear map $V_i \to W$ , which we call an extended dynamical map for the sink; say that D is a matrix for this map. The nonzero real eigenvalues of D are the same as those of $f|W$ . As such, the pair $(V_i,D)$ contains the data of the sink; we refer to any such pair as a sink package.

In the running example, we have $i=j$ (this is the generic scenario); specifically $W = V_i = V_j = V_3$ . As such, the sink package for the map $f_2^{-1} \circ f_1$ is $(V_3,D)$ , where D is the matrix given above.

The space of measured foliations…. Turning back now to the mapping class group, we denote by $\operatorname {\mathrm {MF}}(S)$ the space of measured foliations on S, again up to Whitehead moves and isotopy. See the book by Fathi–Laudenbach–Poénaru [Reference Fathi, Laudenbach and Poénaru12] for background on $\operatorname {\mathrm {MF}}(S)$ .

Let $S=S_{g,p}$ and let $\xi (S)=3g-3+p$ . Thurston proved that $\operatorname {\mathrm {MF}}(S)$ is homeomorphic to $\mathbb {R}^{2\xi (S)}$ . He further proved that $\operatorname {\mathrm {MF}}(S)$ has the structure of an integral cone complex [Reference Thurston30]. Thurston actually described the projectivized complex for $\operatorname {\mathrm {PMF}}(S)$ , which can be described in terms of train track coordinates as follows.

A train track in S is a certain type of embedded finite graph in S with a well-defined tangent line at each point; see the book of Penner–Harer [Reference Penner and Harer25] for details. Thurston’s cells in the cell structure for $\operatorname {\mathrm {PMF}}(S)$ – equivalently, the projectivized integral cone complex structure for $\operatorname {\mathrm {MF}}(S)$ – correspond naturally to train tracks in S. Conversely, every train track gives a cone in $\operatorname {\mathrm {MF}}(S)$ by considering the measured foliations that are carried by $\tau $ . Given a train track $\tau $ , the associated cone will be denoted $V(\tau )$ . For any given S, we may choose once and for all a cell decomposition Y of $\operatorname {\mathrm {MF}}(S)$ with cells $V(\tau _1),\dots ,V(\tau _N)$ .

There are infinitely many choices for the set of $V(\tau _i)$ , that is, infinitely many choices of structures as an integral cone complex where the cells correspond to train tracks. But they all give the same PL structure. While there are integral cone complex structures on $\operatorname {\mathrm {MF}}(S)$ that do not arise from train tracks, we will only make use of the ones that do; in what follows we refer to these as train track cell structures.

As an example, let S be $S_{0,4}$ , or equivalently the thrice-punctured plane. The train tracks $\tau _1$ , $\tau _2$ , and $\tau _3$ shown in Figure 2 give a cell structure on $\operatorname {\mathrm {MF}}(S_{0,4})$ . The weights $x_i$ and $y_i$ on $\tau _i$ give an identification of each cell $V(\tau _i)$ with the first quadrant in $\mathbb {R}^2$ . The resulting integral cone complex structure on $\operatorname {\mathrm {MF}}(S_{0,4})$ is isomorphic to our running example $Y_\Delta $ . The geometric realization given in Figure 1 has a geometric description, namely, it is given by the geometric intersection numbers of a weighted train track with three rays to infinity that emanate from the three marked points.

Figure 2

Train tracks giving a cell structure on $\operatorname {\mathrm {MF}}(S_{0,4})$ .

Figure 2 Long description

A central three-way branching arrow points toward three distinct regions.

1. Top Region: A three-lobed cell structure labeled tau sub 1 contains points x sub 1 and y sub 1. To its left, an oval labeled ‘a’ encloses two points. To its right, an oval encloses two points.

2. Bottom-Right Region: A three-lobed cell structure labeled tau sub 3 contains points x sub 3 and y sub 3. Below it is an oval labeled ‘b’ enclosing two points.

3. Bottom-Left Region: A three-lobed cell structure labeled tau sub 2 contains points x sub 2 and y sub 2.

Each tau structure consists of three teardrop-shaped lobes connected at a central junction, each containing a single black dot.

There is a convenient class of train track cell structures on $\operatorname {\mathrm {MF}}(S)$ that applies to an arbitrary S, namely, the ones arising from Dehn–Thurston train tracks. These are defined as follows. First, we choose a pants decomposition of S; we will refer to the curves of the pants decomposition as base curves. From there, we decompose S into a collection of annuli and pairs of pants. The core curves of the annuli are the base curves and the pairs of pants are the closures of the complementary regions. Each pair of pants has between one and three boundary components, with the other holes accounted for by punctures. As in the book by Penner–Harer [Reference Penner and Harer25, §2.6], there are four model (sub)-train tracks on each annulus and at most four on each pair of pants. By gluing together all possible models, we obtain the collection of Dehn–Thurston train tracks. We prove in Lemma 7.3 that if Y is a Dehn–Thurston cell structure on $\operatorname {\mathrm {MF}}(S)$ and c is one of the base curves, then the radius of Y at c is 1.

…and the mapping class group action. There is a natural action of $\operatorname {\mathrm {Mod}}(S)$ on $\operatorname {\mathrm {MF}}(S)$ ; again see [Reference Fathi, Laudenbach and Poénaru12]. As explained by Thurston, the action of $\operatorname {\mathrm {Mod}}(S)$ on $\operatorname {\mathrm {MF}}(S)$ is by integral cone complex maps (in his setup, piecewise integral projective maps).

Given an integral cone complex structure Y for $\operatorname {\mathrm {MF}}(S)$ and a finite generating set $\Gamma $ for $\operatorname {\mathrm {Mod}}(S)$ , there is (as above) an associated collection of subdivisions $Y_\Gamma $ (as in our general discussion, there are canonical choices for these subdivisions, but in practice we compute subdivisions which may be finer than those). Moreover, each subdivision is a train track cell structure. If $V(\tau _i)$ is a top-dimensional cell of Y and $h_\ell $ is an element of $\Gamma $ , we denote by $V(\tau _{i,1}^{h_\ell }), \dots , V(\tau _{i,N}^{h_\ell })$ the cells of the corresponding subdivision of $V(\tau _i)$ . Each $\tau _{i,j}^{h_\ell }$ is obtained from the corresponding $\tau _i$ by a sequence of splittings; again see [Reference Penner and Harer25] for details.

An additional property of the $\operatorname {\mathrm {Mod}}(S)$ -action is that each pseudo-Anosov element acts on $\operatorname {\mathrm {MF}}(S)$ with projective source-sink dynamics. In particular, such an element has exactly two PL-eigenvectors. The eigenvalues are $\lambda $ and $1/\lambda $ , for the source and sink, respectively. We will refer to a PL-eigenregion for either of these PL-eigenvectors as a Nielsen–Thurston eigenregion.

From a Nielsen–Thurston eigenregion, we obtain an extended dynamical map, and a corresponding sink package $(V(\tau _i),D)$ , or simply $(\tau _i,D)$ . Any such sink package $(\tau _i,D)$ will be called a Nielsen–Thurston package. This is the desired output of our algorithm.

In our running example, the left-handed half-twist $H_a$ about the curve a in Figure 2 (obtained by a clockwise $\pi $ -rotation of the two leftmost marked points) is given by the map $f_1$ described above (using the above identification of $\operatorname {\mathrm {MF}}(S_{0,4})$ with $Y_\Delta $ ), and similarly the half-twist $H_b$ is given by $f_2$ . The mapping class $H_b^{-1} H_a$ is pseudo-Anosov with stretch factor $\varphi ^2$ . By the above calculation, the sink package for $H_b^{-1} H_a$ is $(D,V(\tau _3))$ .

Statement of the main technical theorem. Let $S=S_{g,p}$ . For the statement of Theorem 1.1, we must define a constant $Q=Q(S)$ . We build up the definition of Q by defining a sequence of preliminary constants. We do this in order to give a sense of how Q arises, and to make it feasible to improve our Q by improving the intermediate constants (and hence improve the implementation). In the end, we give a definition of Q using the intermediary constants, and also a formula given directly in terms of g and p; the impatient reader is encouraged to skip to the latter definition of Q.

We begin with a basic constant related to the topology of S:

$$\begin{align*}K(S) = 4\xi(S) = 4(3g-3+p). \end{align*}$$

The number $K=K(S)$ is the maximum number of separatrices for a measured foliation on S; we refer to K as the separatrix complexity of S. In other words, this is the maximum possible sum of the degrees of the singularities of a foliation on S.

Next we have the constants

$$\begin{align*}D(S) = 1\quad \text{and} \quad E(S) = 14. \end{align*}$$

The number $D=D(S)$ is the radius (as defined above) of any Dehn–Thurston integral cone complex structure on $\operatorname {\mathrm {MF}}(S)$ , specifically the radius about one of the curves of the underlying pants decomposition; see Lemma 7.3. The number $E(S)$ is an upper bound on the diameter in $\mathcal {C}(S)$ of the set of vertex cycles for a train track in S. Aougab [Reference Aougab2, Section 5] proved that for all but finitely many S there is an upper bound of 3 for all train tracks in S. As observed by Tang–Webb [Reference Tang and Webb29, Section 2.3], it follows from the work of Bowditch [Reference Bowditch8] that there is an upper bound of 14 for all train tracks in all surfaces. Masur–Minsky [Reference Masur and Minsky20] had previously conjectured that the diameter is bounded above by 3 for all train tracks in all surfaces, but this is still an open problem.

From the above constants, we now define several constants that appear in the statements of the main propositions in the paper or in the proof of Theorem 1.1: Next, we have

$$ \begin{align*} Q_{\text{curve}}(S) &= 2K^2 \\ Q_{\text{track}}(S) &= E \cdot Q_{\text{curve}} \\ Q_{\text{force}}(S) &= Q_{\text{track}} + (2K+6) \cdot 2K\\ Q_{\text{fit}}(S) &= Q_{\text{force}}(S) + (E+3) \cdot Q_{\text{curve}}\\ Q_{\text{DT}}(S) &= (D+1) Q_{\text{track}} \end{align*} $$

The first three of these constants appear in the statements of Propositions 3.1, 5.1, and 6.1, which we call the bounded slope lemma, the forcing lemma, and the fitting lemma. The number $2K+6$ appears in the statement of Lemma 4.1.

Finally, we define

$$\begin{align*}Q(S) = Q_{\mathrm{force}}(S) + Q_{\mathrm{fit}}(S) + Q_{\mathrm{DT}}(S) + 1. \end{align*}$$

This gives

$$ \begin{align*} Q(S_{g,p}) &= 2,464\, \xi^2 + 96\,\xi + 1 \\ &= 2,464(3g-3+p)^2 + 96(3g-3+p) + 1 \end{align*} $$

and in particular

$$\begin{align*}Q(S_2) = 22,465 \quad \text{and} \quad Q(S_3) = 89,281. \end{align*}$$

The coefficient 2,464 arises as $32(5E+7)$ . If one proves the Masur–Minsky conjecture that $E(S)$ can be replaced with 3, then we obtain

$$\begin{align*}Q(S_{g,p}) = 704\, \xi^2 + 96\,\xi + 1, \quad Q(S_2) = 6,625, \quad \text{and} \quad Q(S_3) = 25,921. \end{align*}$$

We may now state our main technical result in terms of Dehn–Thurston cell structures, Nielsen–Thurston eigenregions, and the number $Q=Q(S)$ just defined.

We may think of the first statement of Theorem 1.1 as saying that the Nielsen–Thurston eigenregion is large in some sense (Proposition 6.1 even more directly has this interpretation). For a general PL-action of a group on a manifold, we would expect the eigenregion for a sink to become arbitrarily small as the word length of f becomes increasingly large. As such, Theorem 1.1 is not a general fact about PL-actions; our arguments rely heavily on technology specific to the setting of the mapping class group.

The point of the first statement of Theorem 1.1 is that $f^Q(c)$ finds a Nielsen–Thurston eigenregion for f (or perhaps several). From the action of f on any such eigenregion we may compute a Nielsen–Thurston package $(\tau ,D)$ . Then the second statement of the theorem allows us to extract the stretch factor and unstable measured foliation for f.

We emphasize that the cell structure on $\operatorname {\mathrm {MF}}(S)$ is fixed once and for all. If the cell structure – and hence the notion of linearity – were allowed to depend on f, then the corresponding statement would hold for $Q=1$ , because there exists an invariant train track for f that carries the curve c. We also emphasize that our exponent Q does not depend on the generating set for $\operatorname {\mathrm {Mod}}(S)$ . We will return to this point in Section 1.2.

1.2 The algorithm

We now explain in detail the algorithm that comes from Theorem 1.1. As above, the algorithm runs in quadratic time with respect to the length of the spelling of f as a word in any fixed generating set for $\operatorname {\mathrm {Mod}}(S)$ , and it runs in polynomial time with respect to $\xi (S)$ . And the output is a train track and a matrix. We state this result as Corollary 1.2 below.

There are three subroutines in the main algorithm: the linear piece algorithm, the basic computation algorithm, and the sink package algorithm. We explain these in turn. The first of these is used in the second; the second and third are both utilized in the main algorithm.

Ledgers and the linear piece algorithm. Let M be a space that admits an integral cone complex structure Y, and let G be a finitely generated group acting on M by integral cone complex maps. Suppose we have chosen

1. 1. a generating set $\Gamma = \{h_1,\dots ,h_m\}$ for G and

2. 2. a cell structure for Y on M with cells $\{V_1,\dots ,V_N\}$ .

A linear piece algorithm for the pair $(Y,\Gamma )$ is an algorithm that takes as input an $h_\ell \in \Gamma $ and a cell $V_i$ of Y, and produces as output two pieces of data:

1. 3. a subdivision $\{V_{i,k}^{h_\ell }\}$ of $V_i$ corresponding to $h_\ell $ and

2. 4. the integer matrices $\mathcal {A} = \{A_{i,k}^{h_\ell }\}$ so each $h_\ell | V_{i,k}^{h_\ell }$ is described by $A_{i,k}^{h_\ell }$ .

Here the $V_{i,k}^{h_\ell }$ are described in terms of linear inequalities in the $V_i$ -coordinates.

In some applications it may be expedient to write down once and for all the set of subdivisions $Y_\Gamma = \{Y_{h_\ell }\}$ for all cells $V_i$ and all generators $h_\ell \in \Gamma $ , as well as the set of all matrices $\mathcal {A} = \{A_{i,k}^{h_\ell }\}$ . We would refer to any such quadruple $(\Gamma ,Y,Y_\Gamma ,\mathcal {A})$ as a ledger for the action of G on M. As above, once $\Gamma $ and Y are chosen, the $Y_\Gamma $ and the $\mathcal {A}$ are derived from those choices. In Section 2 we demonstrate our algorithm through a particular example, and in that case we start by giving the entire ledger.

Linear piece algorithms for mapping class groups. For mapping class groups, there are many examples of linear piece algorithms (and ledgers) already in the literature. In his thesis [Reference Penner27], Penner gave formulas – which give a constant-time linear piece algorithm – in terms of Dehn–Thurston train track coordinates (explicit matrices are not given, but they can be derived from the computations there). Penner’s formulas contain minor mistakes, corrected in his subsequent paper [Reference Penner24]. There is still one other mistake, pointed out by Yandi Wu: in the second elementary move (Theorem A.2), the $\lambda $ ’s and $\kappa $ ’s should be switched [Reference Wu32]. For punctured surfaces, a constant-time linear piece algorithm is given by Hamidi-Tehrani–Chen [Reference Hamidi-Tehrani and Chen18].

Again, for the case of the $\operatorname {\mathrm {Mod}}(S)$ -action on $\operatorname {\mathrm {MF}}(S)$ , the cells of $Y_\Gamma $ correspond to train tracks. Further, we can choose the ledger so that each subdivision $V_{i,k}^{h_\ell }$ is equal to some $V(\tau _{i,k}^{h_\ell })$ , where $\tau _{i,k}^{h_\ell }$ is obtained from train track $\tau _i$ by a sequence of splittings; see the book by Penner–Harer for the definition of a splitting [Reference Penner and Harer25].

In the case of $\operatorname {\mathrm {Mod}}(S)$ , the number of cells $V_i$ is exponential in $\xi (S)$ . Therefore, in order to obtain an algorithm that runs in polynomial time with respect to $\xi (S)$ , we cannot compute the entire ledger. Fortunately, this is not necessary. Penner’s ledger (or formulas) gives us a linear piece algorithm that runs in constant time with the Lickorish generators for $\operatorname {\mathrm {Mod}}(S)$ . This is because (a) each generator only interacts with a bounded number of coordinates, (b) there is a finite set of closed formulas describing the action of a generator on the corresponding coordinates, and (c) the corresponding linear inequalities have bounded bit size.

Basic computation algorithm. Say that G is a group with finite generating set $\Gamma =\{h_i\}$ and that G acts on a space M that admits the structure of an m-dimensional integral cone complex Y. Suppose we are given some word

$$\begin{align*}w = f_n \cdots f_1 \end{align*}$$

in the generating set $\Gamma $ , and let $c \in M$ be a point, written as an integer point in some cell $V_i$ of Y. Say that w represents $f \in G$ . We would like to compute:

• ○ $f(c) \in M$ and

• ○ a triple $(A,V_i,V_j)$ describing f in a partial neighborhood of c.

By the latter, we mean (as above), a triple $(A,V_i,V_j)$ where $V_i$ and $V_j$ are cells of Y and A is a matrix describing f on a linear piece $U \subseteq V_i$ containing c (the matrix A uses the $V_i$ and $V_j$ coordinates). We now give the algorithm for performing these computations.

Setup. A space M and group G as above, with a choice of linear piece algorithm for the choices of Y and $\Gamma $ .

Input. A word $w = f_n \cdots f_1$ in the generating set $\Gamma $ (so each $f_\ell $ is some $h_{i_\ell }^{\pm 1}$ )

Initialization. Let $c_0=c$ , with $c_0 \in V_{i_0}$ , let $A_0 = I_m$ (the identity matrix), and let $\ell =1$ .

For $\ell = 1,\dots ,n$ :

1. 1. Apply the linear piece algorithm to $V_{i_{\ell -1}}$ and $f_\ell $ , and determine a top-dimensional subdivision cell $V_{i_{\ell -1},k}^{f_\ell }$ that contains $c_{\ell -1}$ and on which $f_\ell $ is linear, has codomain in some $V_{i_\ell }$ , and is represented by a matrix $A_{i,k}^{f_\ell }$ .

2. 2. Compute $c_{\ell } = A_{i,k}^{f_\ell } c_{\ell -1}$ and $A_{\ell } = A_{i,k}^{f_\ell } A_{\ell -1}$ .

Output. $f(c) = c_n$ and $(A_n,V_{i_0},V_{i_n})$

We emphasize that there can be different outputs for the triple $(A_n,V_{i_0},V_{i_n})$ , since at each stage there may be more than one linear piece of $f_\ell $ containing c. We also point out that step (1) is where the generating set for G is most relevant to the complexity of the algorithm; if we choose a generating set that is not well-suited to the cell structure on Y, then the linear piece algorithm can be more complicated.

The sink package algorithm. We now give an algorithm to find the sink package for a projectively source-sink integral cone complex map $f : Y \to Y$ . We suppose that we have in hand a triple $(A,V_i,V_j)$ for the action of f on a PL-eigenregion for the sink $v \in Y$ . Both $V_i$ and $V_j$ are cones in $\mathbb {R}^d$ , and we may assume without loss of generality that whatever faces are shared in Y are also shared in $\mathbb {R}^d$ . In this case we say that the coordinates on $V_i$ and $V_j$ are compatible.

Input. A triple $(A,V_i,V_j)$ for a PL-eigenregion for the sink of a projectively source-sink integral cone complex map. We assume that the matrix A is written in terms of compatible $\mathbb {R}^d$ -coordinates on $V_i$ and $V_j$ .

Initialization. Let $W_0$ be the subspace of $\mathbb {R}^d$ spanned by $V_i \cap V_j$ (in the compatible coordinates).

1. 1. For $k = 1,\dots , m$ :

   let $W_k = A(W_{k-1}) \cap W_{k-1}$

2. 2. Choose a $d \times d$ matrix B that projects $\mathbb {R}^d$ to $W_m$ ; set $D=AB$ .

Output. $(V_i,D)$

In general, projection onto an integral linear subspace gives a matrix with rational entries. So, generically, we expect the output matrix D to have rational entries.

We will of course apply the sink package algorithm in the case of the mapping class group, in which case $V_i$ can be replaced by the train track defining the cell of $\operatorname {\mathrm {MF}}(S)$ corresponding to $V_i$ . Again, we prove in Lemma 7.4 that the largest real eigenvalue of D is the eigenvalue for the sink, and any corresponding positive eigenvector is the sink.

Property Q. We will state the main algorithm for any group action on an integral cone complex that satisfies the same property as the one guaranteed for the mapping class group by the first statement of Theorem 1.1. Specifically, we say that the action of a finitely generated group G on an integral cone complex Y satisfies property Q if there is a natural number $Q=Q(Y)$ so that, for any $f \in G$ acting with projectively source-sink dynamics and any $c \in Y$ lying on a vertex ray, the point $f^Q(c)$ lies in the interior of a union of PL-eigenregions for f containing the sink.

The main algorithm. Say that G is a group with finite generating set $\Gamma =\{h_i\}$ and that G acts on a space M that admits the structure of an m-dimensional integral cone complex Y. Fix a constant-time linear piece algorithm for the choices of Y and $\Gamma $ , and fix some nonzero $c \in M$ lying on a vertex ray of Y. Suppose that the G-action on M satisfies property Q for some specific $Q=Q(Y)$ .

Input. A word $w = f_n \cdots f_1$ in the generating set $\Gamma $ that represents a projectively source-sink element f of G.

Step 1. Applying the basic computation algorithm to w, compute $f^Q(c)$ .

Step 2. Applying the basic computation algorithm to w, compute a triple $(A,\tau _i,\tau _j)$ associated to an f-linear piece U of Y containing $f^Q(c)$ .

Step 3. Compute a sink package $(\tau _i,D)$ for f using $V(\tau _i)$ -coordinates.

Output. $(\tau _i,D)$

We are finally ready to state our corollary of Theorem 1.1, which gives the algorithm from the Main Theorem.

Corollary 1.2 follows immediately from Theorem 1.1, the standard running times for matrix multiplication and the Zassenhaus algorithm, and the existence of a constant-time linear piece algorithm for the mapping class group. (The Zassenhaus algorithm here boils down to row reduction of matrices of size $O\big (\xi \big )$ and bit size $O\big (n\big )$ , and this row reduction problem has the complexity stated in the introduction; see [Reference Yap33, Lecture X, Theorem 5]).

The Nielsen–Thurston problem. The more general problem that our work fits into is the Nielsen–Thurston problem. This is the algorithmic problem of determining, from a product of generators of $\operatorname {\mathrm {Mod}}(S)$ , the Nielsen–Thurston type of the resulting $f \in \operatorname {\mathrm {Mod}}(S)$ and the associated data: the period if f is periodic, the canonical reduction system if f is reducible, and the stretch factor and foliations when f is pseudo-Anosov.

Bell–Webb gave a polynomial-time algorithm for the reducibility problem, that is, the problem of determining whether an infinite order mapping class (given as a word in the generators) is reducible [Reference Bell and Webb5]. In this case, their algorithm gives the canonical reduction system. Otherwise, their algorithm computes the asymptotic translation length in the curve graph. (It is known classically that if f is periodic, then this – plus the period – can be determined in quadratic time. Indeed, this follows from the upper bound on the period (depending only on S) and the quadratic-time solution to the word problem for $\operatorname {\mathrm {Mod}}(S)$ ). Thus, combining our work with theirs, we obtain a polynomial-time algorithm to solve the Nielsen–Thurston problem.

Baroni [Reference Baroni3] recently gave an alternate version of the Bell–Webb algorithm. Instead of just being polynomial in the word length, his algorithm is polynomial in the word length and the complexity of the surface. On the other hand, Baroni’s algorithm does not explicitly determine any reducing curves.

As pointed out to us by Agol, there is an approach to the Nielsen–Thurston problem using the classical theory of 3-manifolds. Given a mapping class, the algorithm proceeds by producing a triangulation of the corresponding mapping torus, and then using the Jaco–Tollefson algorithm to find the JSJ-decomposition [Reference Jaco and Tollefson19, Section 8]. (The key point is that a pseudo-Anosov mapping class has a trivial JSJ-decomposition.)

1.3 New tools and an outline of the proof

We now give an outline of the paper and the proofs of the main results, as well as descriptions of the new tools introduced in the paper. We begin in Section 2 by illustrating our algorithm through a concrete example.

The rest of the paper is devoted to the proof of Theorem 1.1. The keys to our proof are Propositions 5.1 and 6.1, called the forcing lemma and the fitting lemma. Both propositions are stated in terms of the notion of slope for a curve in a surface, which is also new. We now turn to developing this idea, beginning with the required background.

Horizontal and vertical foliations. Let $f \in \operatorname {\mathrm {Mod}}(S)$ be a pseudo-Anosov mapping class. In order to orient ourselves (and the reader), we will refer to the stable and unstable measured foliations, $(\mathcal {F}^s,\mu ^s)$ and $(\mathcal {F}^u,\mu ^u)$ , as $(\mathcal {F}_v,\mu _v)$ and $(\mathcal {F}_h,\mu _h)$ . The ‘v’ and ‘h’ stand for “vertical” and “horizontal” and in our pictures we will (away from singularities) draw the foliations so that $\mathcal {F}_v$ is vertical, $\mathcal {F}_h$ is horizontal, and the transverse measures are $|dx|$ and $|dy|$ . In such a picture, the pseudo-Anosov representative of f stretches horizontally and compresses vertically.

Singular Euclidean structures. The two measured foliations $\mathcal {F}_v$ and $\mathcal {F}_h$ induce a singular Euclidean structure X on S, the singular points being the singularities of the foliations. Let $\bar X$ be the closed singular Euclidean surface defined by taking the completion of X with the induced metric. There is a set of marked points $\Sigma \subseteq \bar X$ so that $\bar X \setminus \Sigma $ is equal to the surface obtained from X by deleting the singularities of $\mathcal {F}_v$ and $\mathcal {F}_h$ . In other words, $\Sigma $ is the set of points that either correspond to punctures of X or singularities of the foliations (or both).

We remark that $\mathcal {F}_h$ and $\mathcal {F}_v$ are also the horizontal and vertical measured foliations associated to an integrable meromorphic quadratic differential q on $\bar X$ , regarded as a closed Riemann surface.

Section 3: Saddle connections and slope. Let X be a singular Euclidean surface. A saddle connection in the surface $\bar X$ is a closed geodesic arc that meets $\Sigma $ in exactly two points, its endpoints. The corresponding arc in X is also called a saddle connection.

Let $\sigma $ be such a saddle connection in X. We define the slope of $\sigma $ as its height over width:

$$\begin{align*}\operatorname{\mathrm{slope}}_X(\sigma) = \frac{\mu_h(\sigma)}{\mu_v(\sigma)}. \end{align*}$$

For any collection of saddle connections Z, we define $\operatorname {\mathrm {slope}}_X(Z)$ to be the set of slopes of elements of Z.

Let c be a simple closed curve in X. By pulling c tight in X, the curve c degenerates to an immersed path in $\bar X$ contained in a set of pairwise noncrossing saddle connections. Here and throughout when we say that saddle connections are noncrossing, we mean that their interiors are disjoint. Similarly, if c is a measured foliation on S, we can pull tight each nonsingular leaf. Each leaf gives an immersed path contained in a set of pairwise noncrossing saddle connections. Further, since the leaves are pairwise disjoint, there is a single collection of pairwise noncrossing saddle connections so that each leaf gives an immersed path contained in the union. For c either a simple closed curve or a foliation, let $Z=\{\sigma _1, \ldots , \sigma _k\}$ be the resulting collection of pairwise noncrossing saddle connections. We define the slope of c as the finite set

$$\begin{align*}\operatorname{\mathrm{slope}}_X(c) = \operatorname{\mathrm{slope}}_X(Z) = \{\operatorname{\mathrm{slope}}_X(\sigma_1), \ldots, \operatorname{\mathrm{slope}}_X(\sigma_k)\}. \end{align*}$$

Finally, for a train track $\tau $ , we define $\operatorname {\mathrm {slope}}_X(\tau )$ to be the union of the slopes of the vertex cycles.

Section 3 (cont.): Horizontality. It is sometimes convenient for us to use an alternate formulation of the slope. Let $f : S \to S$ be a pseudo-Anosov mapping class with stretch factor $\lambda $ and singular Euclidean surface X, and let c (or $\tau $ ) be as above. We define

$$\begin{align*}\mathcal{H}_f(c) = -\frac{1}{2} \log_\lambda \operatorname{\mathrm{slope}}_X(c). \end{align*}$$

We refer to $\mathcal {H}_f(c)$ as the horizontality of c. We are using an abuse of notation here, as $\mathcal {H}_f$ is not completely determined by f. Indeed, different choices of X lead to horizontality functions that differ by a constant. For any such choice, horizontality satisfies the equation

$$\begin{align*}\mathcal{H}_f(f^k(c)) = \mathcal{H}_f(c) + k \end{align*}$$

for any k. We also prove in Proposition 3.1 that for any set of disjoint curves, arcs, or leaves of a foliation c, the set $\mathcal {H}_f(c)$ has diameter bounded above by $Q_{\mathrm {curve}} = 2K^2$ , the key point being that this bound depends only on S (and not on f).

For two sets of real numbers A and B we say that $A < B$ if $\max A < \min B$ . We will use this notion to compare the slopes and horizontalities of the various objects discussed above.

As an application of our upper bound on $\operatorname {\mathrm {diam}} \mathcal {H}_f(c)$ , we give a new approach to, and – in the case of a closed surface – a slight improvement of the result of Gadre–Tsai on stable translation distances in the curve graph; see Section 3.4.

Section 4: Approximating rectangles. In Section 4 we prove Lemma 4.1, a technical lemma that will be used to prove the forcing lemma in Section 5. The basic idea of the lemma is to approximate a configuration $(\gamma _1,\gamma _2,\ell )$ , where the $\gamma _i$ are crossing saddle connections and $\ell $ is a horizontal leaf, by a configuration $(\gamma _1,\gamma _2,R)$ , where R is a maximal rectangle. For the latter to be an approximation, we mean that the $\gamma _i$ cross the horizontal sides of R and that the slope of R – defined to be the slope of either diagonal – is not too small.

Section 5: The forcing lemma. Let f, $\mathcal {F}_h$ , and X be as above, and let $\tau $ be a filling, transversely recurrent train track in S. We write $c \prec \tau $ and $\mathcal {F} \prec \tau $ to mean that a curve c or a foliation $\mathcal {F}$ is carried by $\tau $ , and in this case we write $\tau [c]$ and $\tau [\mathcal {F}]$ for the sub-train track of $\tau $ consisting of all branches traversed by c or $\mathcal {F}$ , respectively.

Suppose that c is a simple closed curve or a leaf of a measured foliation in S. In the forcing lemma (Proposition 5.1) we assume that

$$\begin{align*}\mathcal{H}_f(c) \geq \mathcal{H}_f(\tau) + Q_{\mathrm{force}}. \end{align*}$$

Under this assumption, the forcing lemma gives the following implications:

1. 1. If $c \prec \tau $ , then $\mathcal {F}_h \prec \tau [c]$ .

2. 2. If $\mathcal {F}_h \prec \tau $ , then c is carried by a diagonal extension of $\tau [\mathcal {F}_h]$ .

Again, for the relevant train track-related definitions, including carrying and diagonal extensions, see the book by Penner–Harer [Reference Penner and Harer25].

Section 6: The fitting lemma. Suppose f is a pseudo-Anosov mapping class and that $\tau _1$ and $\tau _2$ are two train tracks carrying the horizontal foliation $\mathcal {F}_h$ . The fitting lemma (Proposition 6.1) gives an f-invariant train track $\nu $ – meaning that $f(\nu ) \prec \nu $ – with two properties:

1. 1. $\nu \prec \tau _i$ for $i \in \{1,2\}$ and

2. 2. $\mathcal {H}_f(\nu ) \leq \mathcal {H}_f(\tau _i) + Q_{\mathrm {fit}}$ for $i \in \{1,2\}$ .

The train tracks $\tau _1$ and $\tau _2$ will be Dehn–Thurston train tracks coming from the cell structure on $\operatorname {\mathrm {MF}}(S)$ . On an intuitive level, if a train track $\nu $ is carried by $\tau _i$ and has much larger horizontality, then $V(\nu )$ is a very small subregion of $V(\tau _i)$ . So the $\nu $ in the conclusion of Proposition 6.1 is fitted in the sense that $V(\nu )$ is both contained in $V(\tau _i)$ and is large (intuitively, we think of $V(\nu )$ as being almost the size of $V(\tau _i)$ , although it may be of smaller dimension).

Figure 3

In the proof of Theorem 1.1, we choose Q so $\mathcal {H}_f(f^Q(c))$ is very large, we find a coordinate train track $\tau _i$ carrying $\mathcal {F}_h$ , and we choose an f-invariant $\nu $ carried by $\tau _i$ with $\mathcal {H}_f(\nu )$ small.

Section 7: Proof of the main technical theorem. We sketch the idea of the proof of Theorem 1.1. Choose any curve c lying on a vertex ray of $\operatorname {\mathrm {MF}}(S)$ . Our Q and $Q_{\mathrm {DT}}$ are defined exactly so that

$$\begin{align*}\mathcal{H}_f(f^Q(c)) \geq \mathcal{H}_f(\tau_i) + Q_{\mathrm{force}} + Q_{\mathrm{fit}} + 1 \end{align*}$$

for all train tracks $\tau _i$ arising in the chosen cell decomposition of $\operatorname {\mathrm {MF}}(S)$ . Suppose that $f^Q(c)$ is carried by the coordinate train track $\tau _i$ . By the forcing lemma, $\mathcal {F}_h$ is carried by $\tau _i$ . By the fitting lemma, there is an f-invariant train track $\nu $ so that

$$\begin{align*}\mathcal{H}_f(f^Q(c)) \geq \mathcal{H}_f(\nu) + Q_{\mathrm{force}} + 1 \end{align*}$$

Then for every curve d near $f^Q(c)$ , the forcing lemma (plus the continuity of horizontality) gives a diagonal extension $\nu _d$ of $\nu $ that carries d. Each such $V(\nu _d)$ is a Nielsen–Thurston eigenregion. Since the $V(\nu _d)$ form an open neighborhood of $f^Q(c)$ in $\operatorname {\mathrm {MF}}(S)$ , every linear piece for f that contains $f^Q(c)$ must overlap one of the Nielsen–Thurston eigenregions $V(\nu _d)$ , and hence is contained in a Nielsen–Thurston eigenregion, as desired.