## Notes of Richard Webb’s Cambridge lecture 9-01-2017

Polynomial time Thurston type recognition algorithm

Joint with Mark Bell.

1. Introduction

Theorem 1 (Thurston) A mapping class is either

1. periodic,
2. reducible,
3. pseudo-Anosov.

Reducible means that map ${f}$ 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 ${M_f}$ admits

1. ${H^2\times{\mathbb R}}$ geometry,
2. a non trivial JSJ decomposition,
3. ${H^3}$ geometry.

Question (Pseudo-Anosov decision problem). Let ${X}$ be a finite generating set for MCG. Given a word in ${X}$, decide wether it is pseudo-Anosov.

Theorem 3 (Bell-Webb)

1. The PADP is in P.
2. There existe a polynomial time algorithm that accepts a word and returns a conical curve system for ${f}$.

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 ${C(S)}$ 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.

${C(S)}$ 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 ${f\in MCG}$ is

$\displaystyle \begin{array}{rcl} \|f\| :=\lim_{n\rightarrow\infty}\frac{1}{n}d(\gamma,f^n\gamma) \end{array}$

for arbitrary vertex ${\gamma}$.

If ${f}$ is periodic or reducible, then ${\|f\|=0}$. On the other hand,

Theorem 5 (Mazur-Minsky) There is a uniform positive lower bound for ${\|f\|}$ for ${f}$ pseudo-Anosov.

In fact (Bowditch) ${\|f\|}$ are rational numbers with bounded denominators.

2.2. Procedure

Fix a curve ${\gamma}$ on surface. Fix a large constant ${N}$. Compute geodesic from ${\gamma}$ to ${f^N \gamma}$. Take a mid-point ${\gamma'}$ of that geodesic. Compute ${d=d(\gamma',f^N \gamma'}$. If ${d}$ is large, then ${f}$ is pseudo-Anosov. If ${d}$ is small, then ${f}$ is reducible.

Why does this work ?

If ${f}$ is pseudo-Anosov, it has a quasi-axis which is translated by at least ${c>0}$, ${\|f^N\|=N\|f\|\geq Nc}$ is large. Furthermore, the geodesic from ${\gamma}$ to ${f^N\gamma}$ travels a long way along the axis, ${\gamma'}$ belongs to the axis, thus it is translated a lot.

If ${f}$ is reducible, it has a canonical curve system, ${f}$ rotates around it, the geodesic from ${\gamma}$ to ${f^N\gamma}$ comes close to it (Bounded geodesic image theorem), ${\gamma'}$ is within distance 2 of it, thus ${\gamma'}$ 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 ${e_i}$. 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 ${\alpha}$ and ${\beta}$.

1. Compute a ${K}$-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.
2. Compute “tight paths” of length ${\leq L}$ beween pairs of vertices in this set. By definition, a tight path is a sequence of multicurves ${\gamma_i}$ on the surface such that whenever ${|i-j|\geq 3}$, ${\gamma_i}$ and ${\gamma_j}$ fill the surface, and ${\gamma_i}$ bounds a neighborhood of ${\gamma_{i-1}\cup\gamma_{i+1}}$.

Theorem 6 All tight geodesics are contained in the quasi-geodesic.

3. Finally, use Dijkstra’s algorithm to find a geodesic in this set.