Cardinality of Rauzy classes
Annales de l'Institut Fourier, Volume 63 (2013) no. 5, p. 1651-1715

Rauzy classes form a partition of the set of irreducible permutations. They were introduced as part of a renormalization algorithm for interval exchange transformations. We prove an explicit formula for the cardinality of each Rauzy class. Our proof uses a geometric interpretation of permutations and Rauzy classes in terms of translation surfaces and moduli spaces.

Les classes de Rauzy forment des partitions de l’ensemble des permutations irréductibles. Elles ont été introduites par G. Rauzy dans l’étude d’un algorithme de renormalisation des échanges d’intervalles. Nous démontrons une formule explicite pour la cardinalité de chaque classe de Rauzy. La preuve que nous développons utilise une interprétation géométrique des permutations et des classes de Rauzy en termes de surfaces de translation et d’espace de modules.

DOI : https://doi.org/10.5802/aif.2811
Classification:  05A15,  37A05,  37B10
Keywords: Rauzy classes, Rauzy induction, interval exchange transformations, irreducible permutations, indecomposable permutations
@article{AIF_2013__63_5_1651_0,
     author = {Delecroix, Vincent},
     title = {Cardinality of Rauzy classes},
     journal = {Annales de l'Institut Fourier},
     publisher = {Association des Annales de l'institut Fourier},
     volume = {63},
     number = {5},
     year = {2013},
     pages = {1651-1715},
     doi = {10.5802/aif.2811},
     mrnumber = {3186505},
     zbl = {1285.05007},
     language = {en},
     url = {http://www.numdam.org/item/AIF_2013__63_5_1651_0}
}
Delecroix, Vincent. Cardinality of Rauzy classes. Annales de l'Institut Fourier, Volume 63 (2013) no. 5, pp. 1651-1715. doi : 10.5802/aif.2811. http://www.numdam.org/item/AIF_2013__63_5_1651_0/

[1] Ahlfors, L. Lectures on quasiconformal mappings, Van Nostrand (1966) (Reprint Wadsworth Inc., 1987; New edition by the AMS, 2006) | MR 200442 | Zbl 0138.06002

[2] Avila, A.; Forni, G. Weak mixing for interval exchange transformations and translation flows, Ann. of Math., Tome 165 (2007) no. 2, pp. 637-664 | Article | MR 2299743 | Zbl 1136.37003

[3] Boccara, G. Nombre de representations d’une permutation comme produit de deux cycles de longueurs donnees, Discrete Math., Tome 29 (1980), p. 105-13 | Article | MR 558612 | Zbl 0444.20003

[4] Boissy, C. Classification of Rauzy classes in the moduli space of quadratic differentials (2009) (arxiv:0904.3826v1)

[5] Boissy, C. Labeled Rauzy classes and framed translation surfaces (2010) (arXiv:1010.5719v1)

[6] Bufetov, A. I. Decay of correlations for the Rauzy-Veech-Zorich induction map on the space of interval exchange transformations and the central limit theorem for the Teichmüller flow on the moduli space of Abelian differential, J. Amer. Math. Soc, Tome 19 (2006) no. 3, pp. 579-623 | Article | MR 2220100 | Zbl 1100.37002

[7] Chapuy, G. Combinatoire bijective des cartes de genre supérieur, École Polytechnique (2009) (Ph. D. Thesis)

[8] Community, The Sage-Combinat Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics (2008) (http://combinat.sagemath.org)

[9] Comtet, L. Sur les coefficients de l’inverse de la sèrie formelle n!t n , C. R. Acad. Sci. Paris, Tome 275 (1972) no. A, pp. 569-572 | MR 302457 | Zbl 0246.05003

[10] Eskin, A.; Masur, H.; Zorich, A. Moduli spaces of Abelian differentials: the principal boundary, counting problems and the Siegel-Veech constants, Publ. Math. Inst. Hautes Études Sci., Tome 97 (2003) no. 1, pp. 61-179 | Article | Numdam | MR 2010740 | Zbl 1037.32013

[11] Eskin, A.; Okounkov, A. Asymptotics of numbers of branched coverings of a torus and volumes of moduli spaces of holomorphic differentials, Invent. Math., Tome 145 (2001) no. 1, pp. 59-103 | Article | MR 1839286 | Zbl 1019.32014

[12] Eskin, A.; Okounkov, A.; Pandharipande, R. The theta characteristic of a branched covering, Adv. Math., Tome 217 (2008) no. 3, pp. 873-888 | Article | MR 2383889 | Zbl 1157.14014

[13] Flajolet, P.; Sedgewick, R. Analytic Combinatorics, Cambridge University Press (2009) | MR 2483235 | Zbl 1165.05001

[14] Goupil, A.; Schaeffer, G. Factoring n-cycles and counting maps of given genus, European J. Combin., Tome 19 (1998), pp. 819-834 | Article | MR 1649966 | Zbl 0915.05007

[15] Hatcher, A. Algebraic topology, Cambridge University Press (2002) | MR 1867354 | Zbl 1044.55001

[16] Hubbard, J. H. Teichmüller theory and Applications to geometry, topology and dynamics. Volume 1, Matrix Editions (2006) | MR 2245223 | Zbl 1102.30001

[17] Imayoshi, Y.; Taniguchi, M. An introduction to Teichmüller spaces, Springer (1992) | MR 1215481 | Zbl 0754.30001

[18] Johnson, D. Spin structures and quadratic forms on surfaces, J. London. Math. Soc., Tome 22 (1980) no. 2, pp. 365-373 | Article | MR 588283 | Zbl 0454.57011

[19] Keane, M. Interval exchange transformations, Math. Z., Tome 141 (1975), pp. 77-102 | Article | MR 357739 | Zbl 0278.28010

[20] Kerckhoff, S. P. Simplicial systems for interval exchange maps and measured foliations, Ergodic Theory and Dynamical Systems, Tome 5 (1985) no. 2, pp. 257-271 | Article | MR 796753 | Zbl 0597.58024

[21] King, A. Generating indecomposable permutations, Discrete Math., Tome 306 (2006) no. 5, pp. 508-518 | Article | MR 2212519 | Zbl 1086.05004

[22] Kontsevich, M.; Zorich, A. Connected components of the moduli spaces of Abelian differentials wit prescribed singularities, Invent. math., Tome 153 (2003) no. 3, pp. 631-678 | Article | MR 2000471 | Zbl 1087.32010

[23] Lando, S.; Zvonkin, A. Graphs on Surfaces and their Applications, Springer Tome 141 (2004) | MR 2036721 | Zbl 1040.05001

[24] Lanneau, E. Connected components of the strata of the moduli spaces of quadratic differentials, Ann. Sci. Éc. Norm. Supér., Tome 41 (2008) no. 1, pp. 1-56 | Numdam | MR 2423309 | Zbl 1161.30033

[25] Marmi, S.; Moussa, P.; Yoccoz, J.-C. The cohomological equation for Roth type interval exchange transformations, Journal of the Amer. Math. Soc., Tome 18 (2005), pp. 823-872 | Article | MR 2163864 | Zbl 1112.37002

[26] Masur, H. Interval exchange transformations and measured foliations, Ann. of Math., Tome 115 (1982) no. 1, pp. 169-200 | Article | MR 644018 | Zbl 0497.28012

[27] Nag, S. The complex analytic theory of Teichmüller spaces, Wiley-Intersciences (1988) | MR 927291 | Zbl 0667.30040

[28] Nogueira, A.; Rudolph, D. Topological weak-mixing of interval exchange maps, Ergodic theory Dynam. Systems, Tome 17 (1997) no. 5, pp. 1183-1209 | Article | MR 1477038 | Zbl 0958.37010

[29] Rauzy, G. Echanges d’intervalles et transformations induites, Acta Arith., Tome 34 (1979), pp. 315-328 | MR 543205 | Zbl 0414.28018

[30] Serre, J.-P. Topics in Galois Theory, Jones and Bartlette Publishers (1992) | MR 1162313 | Zbl 0746.12001

[31] Stanley, R. Factorization of permutations into n-cycles, Discrete Math., Tome 37 (1981), pp. 255-262 | Article | MR 676430 | Zbl 0467.20005

[32] Stein, W. Sage Mathematics Software (Version 4.5.2), The Sage Development Team (2009) (http://www.sagemath.org)

[33] Veech, W. A. Gauss measures for transformations on the space of interval exchange maps, Ann. of Math., Tome 115 (1982) no. 1, p. 201-24 | Article | MR 644019 | Zbl 0486.28014

[34] Veech, W. A. Moduli space of quadratic differentials, J. d’Analyse Math., Tome 55 (1990), pp. 117-171 | Article | MR 1094714 | Zbl 0722.30032

[35] Veech, W. A. Flat surfaces, Amer. J. of Math., Tome 115 (1993) no. 3, pp. 589-689 | Article | MR 1221838 | Zbl 0803.30037

[36] Viana, M. Dynamics of interval exchange maps and Teichmüller flows (2008) (http://w3.impa.br/~viana)

[37] Walkup, D. How many ways can a permutation be factored into two n-cycles?, Discrete Math., Tome 28 (1979) no. 3, pp. 315-319 | Article | MR 548630 | Zbl 0429.05006

[38] Yoccoz, J.-C. Echanges d’intervalles (2005) (Cours au collège de France, http://college-de-france)

[39] Yoccoz, J.-C. Continued fraction algorithms for interval exchange maps: an introduction, Frontiers in number theory, physics and geometry. I, Springer (2006), pp. 401-435 | MR 2261103 | Zbl 1127.28011

[40] Zagier, D. B.; Harer, J. L. The Euler characteristic of the moduli space of curves, Invent. Math., Tome 85 (1986) no. 3, pp. 457-486 | Article | MR 848681 | Zbl 0616.14017

[41] Zorich, A. Flat surfaces, Frontiers in Number Theory, Physics and Geometry. Volume 1: On random matrices , zeta functions and dynamical systems, Springer (2006), pp. 437-583 | MR 2261104 | Zbl 1129.32012

[42] Zorich, A. Explicit Jenkins-Strebel representatives of all strata of Abelian and quadratic differentials, J. Mod. Dyn., Tome 2 (2008) no. 1, pp. 139-185 | Article | MR 2366233 | Zbl 1149.30033