Polynomial time Thurston type recognition algorithm
Joint with Mark Bell.
Theorem 1 (Thurston) A mapping class is either
Reducible means that map Pseudo-Anosov means looks locally like an Anosov map, stable and unstable directions are given by a (singular) measured foliation.
Theorem 2 (Thurston) Accordingly, the mapping torus admits
- a non trivial JSJ decomposition,
Question (Pseudo-Anosov decision problem). Let be a finite generating set for MCG. Given a word in , decide wether it is pseudo-Anosov.
Theorem 3 (Bell-Webb)
- The PADP is in P.
- There existe a polynomial time algorithm that accepts a word and returns a conical curve system for .
This follows from
Theorem 4 (Bell-Webb) There exists a polynomial time algorithm that accepts vertices of the curve complex and returns a (tight) geodesic between them.
Note that Margalit-Strenner-Yurttas obtains thms 1 and 2 by different methods.
History. Mosher, Hamdi-Tehrani-Chen gave an exponential time solution. Bestvina-Handel’s solution seems to be exponential again. The case of braid groups, using Garside structures, was completed by Calvez (after earlier works).
Koberda-Margalit showed that PADP is in co-NP. Bell showed that it is in NP.
The issue of computing distance in the curve complex was studied by Leasure, Shackleton, Watanabe, Birman-Margalit-Menasco, but none gave explicit running times. Unclear at all that there could be a polynomial algorithm.
2. The curve graph
This is the 1-skeleton of Harvey’s curve complex: vertices are isotopy classes of essential simple closed curves. Essential means not null homotopic, not homotopic to a puncture. An edge between two curves if they have disjoint realizations.
is connected but locally infinite. MCG acts on it, the action is acylindrical. It has infinite diameter. Pseudo-Anosov classes act loxodromically. It is hyperbolic.
2.1. How thm 4 implies thm 3
The asymptotic translation length of is
for arbitrary vertex .
If is periodic or reducible, then . On the other hand,
Theorem 5 (Mazur-Minsky) There is a uniform positive lower bound for for pseudo-Anosov.
In fact (Bowditch) are rational numbers with bounded denominators.
Fix a curve on surface. Fix a large constant . Compute geodesic from to . Take a mid-point of that geodesic. Compute . If is large, then is pseudo-Anosov. If is small, then is reducible.
Why does this work ?
If is pseudo-Anosov, it has a quasi-axis which is translated by at least , is large. Furthermore, the geodesic from to travels a long way along the axis, belongs to the axis, thus it is translated a lot.
If is reducible, it has a canonical curve system, rotates around it, the geodesic from to comes close to it (Bounded geodesic image theorem), is within distance 2 of it, thus is translated by at most 4.
2.3. Proof of Key Theorem
Assume surface is punctured (otherwise, introduce fake puncture). Fix an ideal triangulation. A curve is uniquely determined by the intersections numbers with the edges . The algorithm is polynomial time in the bitsize of intersection numbers (polynomial in the intersection numbers themselves would not be sufficient).
Overview of algorithm. Data: two simple closed curves and .
- Compute a -unparametrized quasi-geodesic. For this, use Agol-Hass-Thurston to compute fast train track splitting sequences. Mazur-Minsky already observed that these provide quasi-geodesics.
- Compute “tight paths” of length beween pairs of vertices in this set. By definition, a tight path is a sequence of multicurves on the surface such that whenever , and fill the surface, and bounds a neighborhood of .
Theorem 6 All tight geodesics are contained in the quasi-geodesic.
- Finally, use Dijkstra’s algorithm to find a geodesic in this set.