Algorithmic aspects of branched coverings

Bartholdi, Laurent; Dudko, Dzmitry

Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 26 (2017) no. 5, pp. 1219-1296.

Ce texte est un survol, et une version condensée, d’une série d’articles étudiant algorithmiquement les applications de Thurston. Nous décrivons les revêtements ramifiés de la sphère en termes d’objets de la théorie des groupes appelés « bi-ensembles », et développons une théorie de leur décomposition.

Nous introduisons une décomposition canonique « de Levy » d’une application de Thurston quelconque en homéomorphismes, applications métriquement dilatantes et applications doublement revêtues par un endomorphisme du tore. Les homéomorphismes se décomposent eux-mêmes en applications d’ordre fini et pseudo-Anosov, et les applications dilatantes se décomposent elles-mêmes en applications rationelles.

Comme conséquence, nous prouvons qu’il est algorithmiquement décidable si deux applications de Thurston sont combinatoirement équivalentes. Nous montrons aussi que les décompositions décrites ci-dessus sont calculables, en théorie et en pratique.

This is a survey, and a condensed version, of a series of articles on the algorithmic study of Thurston maps. We describe branched coverings of the sphere in terms of group-theoretical objects called bisets, and develop a theory of decompositions of bisets.

We introduce a canonical “Levy” decomposition of an arbitrary Thurston map into homeomorphisms, metrically-expanding maps and maps doubly covered by torus endomorphisms. The homeomorphisms decompose themselves into finite-order and pseudo-Anosov maps, and the expanding maps decompose themselves into rational maps.

As an outcome, we prove that it is decidable when two Thurston maps are equivalent. We also show that the decompositions above are computable, both in theory and in practice.

[1] Bartholdi, Laurent IMG — Computations with iterated monodromy groups, Version 0.1.1, 2016 (http://laurentbartholdi.github.com/img/)

[2] Bartholdi, Laurent; Buff, Xavier; Graf von Bothmer, Hans-Christian; Kröker, Jakob Algorithmic construction of Hurwitz maps, Exp. Math., Volume 24 (2015) no. 1, pp. 76-92 | DOI

[3] Bartholdi, Laurent; Dudko, Dzmitry Algorithmic aspects of branched coverings I/V. Van Kampen’s theorem for bisets (2015) (https://arxiv.org/abs/1512.08539)

[4] Bartholdi, Laurent; Dudko, Dzmitry Algorithmic aspects of branched coverings II/V. Sphere bisets and their decompositions (2016) (https://arxiv.org/abs/1603.04059)

[5] Bartholdi, Laurent; Dudko, Dzmitry Algorithmic aspects of branched coverings III/V. Erasing maps and orbispaces (2016) (in preparation)

[6] Bartholdi, Laurent; Dudko, Dzmitry Algorithmic aspects of branched coverings IV/V. Expanding maps (2016) (https://arxiv.org/abs/1610.02434)

[7] Bartholdi, Laurent; Dudko, Dzmitry Algorithmic aspects of branched coverings V/V. Symbolic and floating-point algorithms (2016) (in preparation)

[8] Bartholdi, Laurent; Dudko, Dzmitry; Nekrashevych, Volodymyr V. Iterated Monodromy Groups of Quadratic Polynomials, II (2016) (preprint)

[9] Bartholdi, Laurent; Nekrashevych, Volodymyr V. Thurston equivalence of topological polynomials, Acta Math., Volume 197 (2006) no. 1, pp. 1-51 | DOI

[10] Bestvina, Mladen; Handel, Michael Train-tracks for surface homeomorphisms, Topology, Volume 34 (1995) no. 1, pp. 109-140 | DOI

[11] Bonnot, Sylvain; Braverman, Mark; Yampolsky, Michael Thurston equivalence to a rational map is decidable, Mosc. Math. J., Volume 12 (2012) no. 4, p. 747-763, 884

[12] Buff, Xavier; Epstein, Adam L.; Koch, Sarah; Meyer, Daniel; Pilgrim, Kevin M.; Rees, Mary; Lei, Tan Questions about polynomial matings, Ann. Fac. Sci. Toulouse Math., Volume 21 (2012) no. 5, pp. 1149-1176 | DOI

[13] Cannon, James W.; Floyd, William J.; Parry, Walter R.; Pilgrim, Kevin M. Nearly Euclidean Thurston maps, Conform. Geom. Dyn., Volume 16 (2012), pp. 209-255 | DOI

[14] Chéritat, Arnaud Tan Lei and Shishikura’s example of non-mateable degree 3 polynomials without a Levy cycle, Ann. Fac. Sci. Toulouse Math., Volume 21 (2012) no. 5, pp. 935-980 | DOI

[15] Douady, Adrien; Hubbard, John H. Étude dynamique des polynômes complexes. Partie I, Publications Mathématiques d’Orsay, 84, Université de Paris-Sud, 1984, 75 pages

[16] Douady, Adrien; Hubbard, John H. Étude dynamique des polynômes complexes. Partie II, Publications Mathématiques d’Orsay, 85, Université de Paris-Sud, 1985, v+154 pages (With the collaboration of P. Lavaurs, Tan Lei and P. Sentenac)

[17] Douady, Adrien; Hubbard, John H. A proof of Thurston’s topological characterization of rational functions, Acta Math., Volume 171 (1993) no. 2, pp. 263-297 | DOI

[18] Farb, Benson; Margalit, Dan A primer on mapping class groups, Princeton Mathematical Series, 49, Princeton University Press, 2012, xiv+472 pages

[19] Grunewald, Fritz J. Solution of the conjugacy problem in certain arithmetic groups, Word problems II (Conf. on Decision Problems in Algebra, Oxford, 1976) (Stud. Logic Foundations Math.), Volume 95, North-Holland, 1980, pp. 101-139

[20] Haïssinsky, Peter; Pilgrim, Kevin M. An algebraic characterization of expanding Thurston maps, J. Mod. Dyn., Volume 6 (2012) no. 4, pp. 451-476

[21] Hemion, Geoffrey On the classification of homeomorphisms of $2$-manifolds and the classification of $3$-manifolds, Acta Math., Volume 142 (1979) no. 1-2, pp. 123-155 | DOI

[22] Hurwitz, Adolf Ueber Riemann’sche Flächen mit gegebenen Verzweigungspunkten, Math. Ann., Volume 39 (1891) no. 1, pp. 1-60 | DOI

[23] Ishii, Yutaka; Smillie, John Homotopy shadowing, Amer. J. Math., Volume 132 (2010) no. 4, pp. 987-1029 | DOI

[24] Kameyama, Atsushi The Thurston equivalence for postcritically finite branched coverings, Osaka J. Math., Volume 38 (2001) no. 3, pp. 565-610

[25] Milnor, John W. On Lattès maps, Dynamics on the Riemann sphere, European Mathematical Society, 2006, pp. 9-43 | DOI

[26] Nekrashevych, Volodymyr V. Self-similar groups, Mathematical Surveys and Monographs, 117, American Mathematical Society, 2005, xi+231 pages | DOI

[27] Nielsen, Jakob Surface transformation classes of algebraically finite type, Danske Vid. Selsk. Math.-Fys. Medd., Volume 21 (1944) no. 2, 89 pages

[28] Pilgrim, Kevin M. Combinations of complex dynamical systems, Lecture Notes in Mathematics, 1827, Springer, 2003, x+118 pages

[29] Poirier, Alfredo Critical portraits for postcritically finite polynomials, Fundam. Math., Volume 203 (2009) no. 2, pp. 107-163 | DOI

[30] Richter, Robin Hubbard trees of complex polynomials, Göttingen, Germany (2013) Ph. D. Thesis Bachelor’s thesis (Bachelorarbeit)

[31] Selinger, Nikita Thurston’s pullback map on the augmented Teichmüller space and applications, Invent. Math., Volume 189 (2012) no. 1, pp. 111-142 | DOI

[32] Selinger, Nikita Topological characterization of canonical Thurston obstructions, J. Mod. Dyn., Volume 7 (2013) no. 1, pp. 99-117 | DOI

[33] Selinger, Nikita; Yampolsky, Michael Constructive geometrization of Thurston maps and decidability of Thurston equivalence, Arnold Math. J., Volume 1 (2015) no. 4, pp. 361-402 | DOI

[34] Serre, Jean-Pierre Trees, Springer, 1980 (Translated from the French by John Stillwell)

[35] Shishikura, Mitsuhiro; Lei, Tan A family of cubic rational maps and matings of cubic polynomials, Exp. Math., Volume 9 (2000) no. 1, pp. 29-53 | DOI

[36] Tan, Lei Matings of quadratic polynomials, Ergodic Theory Dyn. Syst., Volume 12 (1992) no. 3, pp. 589-620

[37] The GAP Group GAP — Groups, Algorithms, and Programming, Version 4.5, 2016 (http://www.gap-system.org)

[38] Thurston, Dylan P. From rubber bands to rational maps: a research report, Res. Math. Sci., Volume 3 (2016) no. 1, pp. 1-49 | DOI

[39] Thurston, William P. On the geometry and dynamics of diffeomorphisms of surfaces, Bull. Am. Math. Soc., Volume 19 (1988) no. 2, pp. 417-431 | DOI

[40] Zieschang, Heiner; Vogt, Elmar; Coldewey, Hans-Dieter Surfaces and planar discontinuous groups, Lecture Notes in Mathematics, 835, Springer, 1980, x+334 pages (Translated from the German by John Stillwell)