Algorithmic aspects of branched coverings
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.

Reçu le :
Accepté le :
Publié le :
DOI : 10.5802/afst.1566

Laurent Bartholdi 1 ; Dzmitry Dudko 2

1 Ecole Normale Supérieure, 45 rue d’Ulm, 75230 Paris, France and Mathematisches Institut, Georg-August Universität zu Göttingen, Bunsenstraße 3-5, 37073 Göttingen, Germany
2 Mathematisches Institut, Georg-August Universität zu Göttingen, Bunsenstraße 3-5, 37073 Göttingen, Germany
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits
@article{AFST_2017_6_26_5_1219_0,
     author = {Laurent Bartholdi and Dzmitry Dudko},
     title = {Algorithmic aspects of branched coverings},
     journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
     pages = {1219--1296},
     publisher = {Universit\'e Paul Sabatier, Toulouse},
     volume = {Ser. 6, 26},
     number = {5},
     year = {2017},
     doi = {10.5802/afst.1566},
     language = {en},
     url = {https://afst.centre-mersenne.org/articles/10.5802/afst.1566/}
}
TY  - JOUR
AU  - Laurent Bartholdi
AU  - Dzmitry Dudko
TI  - Algorithmic aspects of branched coverings
JO  - Annales de la Faculté des sciences de Toulouse : Mathématiques
PY  - 2017
SP  - 1219
EP  - 1296
VL  - 26
IS  - 5
PB  - Université Paul Sabatier, Toulouse
UR  - https://afst.centre-mersenne.org/articles/10.5802/afst.1566/
DO  - 10.5802/afst.1566
LA  - en
ID  - AFST_2017_6_26_5_1219_0
ER  - 
%0 Journal Article
%A Laurent Bartholdi
%A Dzmitry Dudko
%T Algorithmic aspects of branched coverings
%J Annales de la Faculté des sciences de Toulouse : Mathématiques
%D 2017
%P 1219-1296
%V 26
%N 5
%I Université Paul Sabatier, Toulouse
%U https://afst.centre-mersenne.org/articles/10.5802/afst.1566/
%R 10.5802/afst.1566
%G en
%F AFST_2017_6_26_5_1219_0
Laurent Bartholdi; Dzmitry Dudko. Algorithmic aspects of branched coverings. Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 26 (2017) no. 5, pp. 1219-1296. doi : 10.5802/afst.1566. https://afst.centre-mersenne.org/articles/10.5802/afst.1566/

[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., Volume 24 (2015) no. 1, pp. 76-92 | DOI

[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., Volume 197 (2006) no. 1, pp. 1-51 | DOI

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

[11] Sylvain Bonnot; Mark Braverman; Michael Yampolsky Thurston equivalence to a rational map is decidable, Mosc. Math. J., Volume 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., Volume 21 (2012) no. 5, pp. 1149-1176 | DOI

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

[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., Volume 21 (2012) no. 5, pp. 935-980 | DOI

[15] Adrien Douady; John H. Hubbard Étude dynamique des polynômes complexes. Partie I, Publications Mathématiques d’Orsay, 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, 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., Volume 171 (1993) no. 2, pp. 263-297 | DOI

[18] Benson Farb; Dan Margalit A primer on mapping class groups, Princeton Mathematical Series, 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.), Volume 95, North-Holland, 1980, pp. 101-139

[20] Peter Haïssinsky; Kevin M. Pilgrim An algebraic characterization of expanding Thurston maps, J. Mod. Dyn., Volume 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., Volume 142 (1979) no. 1-2, pp. 123-155 | DOI

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

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

[24] Atsushi Kameyama The Thurston equivalence for postcritically finite branched coverings, Osaka J. Math., Volume 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 | DOI

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

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

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

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

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

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

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

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

[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., Volume 9 (2000) no. 1, pp. 29-53 | DOI

[36] Lei Tan 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] Dylan P. Thurston From rubber bands to rational maps: a research report, Res. Math. Sci., Volume 3 (2016) no. 1, pp. 1-49 | DOI

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

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

Cité par Sources :