logo AFST
Algorithmic aspects of branched coverings
Laurent Bartholdi; Dzmitry Dudko
Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 26 (2017) no. 5, p. 1219-1296

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.

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.

Received : 2016-02-14
Accepted : 2016-10-20
Published online : 2017-12-15
DOI : https://doi.org/10.5802/afst.1566
     author = {Laurent Bartholdi and Dzmitry Dudko},
     title = {Algorithmic aspects of branched coverings},
     journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
     publisher = {Universit\'e Paul Sabatier, Toulouse},
     volume = {Ser. 6, 26},
     number = {5},
     year = {2017},
     pages = {1219-1296},
     doi = {10.5802/afst.1566},
     language = {en},
     url = {https://afst.centre-mersenne.org/item/AFST_2017_6_26_5_1219_0}
Bartholdi, Laurent; Dudko, Dzmitry. Algorithmic aspects of branched coverings. Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 26 (2017) no. 5, pp. 1219-1296. doi : 10.5802/afst.1566. afst.centre-mersenne.org/item/AFST_2017_6_26_5_1219_0/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[30] Robin Richter Hubbard trees of complex polynomials (2013) (Ph. D. Thesis)

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

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

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

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

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

[36] Lei Tan Matings of quadratic polynomials, Ergodic Theory Dyn. Syst., Tome 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] Dylan P. Thurston From rubber bands to rational maps: a research report, Res. Math. Sci., Tome 3 (2016) no. 1, pp. 1-49 | Article

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

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