Cardinality of Rauzy classes

Delecroix, Vincent

Annales de l'Institut Fourier, Tome 63 (2013) no. 5, pp. 1651-1715.

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.

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.

Classification : 05A15, 37A05, 37B10
Keywords: Rauzy classes, Rauzy induction, interval exchange transformations, irreducible permutations, indecomposable permutations
Mot clés : classes de Rauzy, induction de Rauzy, échanges d’intervalles, permutation irréductible, permutation indécomposable

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

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

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

[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, Volume 19 (2006) no. 3, pp. 579-623 | DOI | MR | Zbl

[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 $\sum n!t^n$, C. R. Acad. Sci. Paris, Volume 275 (1972) no. A, pp. 569-572 | MR | Zbl

[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., Volume 97 (2003) no. 1, pp. 61-179 | DOI | Numdam | MR | Zbl

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

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

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

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

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

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

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

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

[19] Keane, M. Interval exchange transformations, Math. Z., Volume 141 (1975), pp. 77-102 | DOI | MR | Zbl

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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., Volume 28 (1979) no. 3, pp. 315-319 | DOI | MR | Zbl

[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 | Zbl

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

[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 | Zbl

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