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.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s