Complexity and growth for polygonal billiards  [ Complexité et diagonales généralisées dans les billards polygonaux ]
Annales de l'Institut Fourier, Tome 52 (2002) no. 3, pp. 835-847.

Nous établissons un lien entre la fonction de complexité et le nombre de diagonales généralisées pour un billard polygonal. Dans le cas où le billard est rationnel, la fonction de complexité est comprise entre deux polynômes cubiques; elle a une asymptotique cubique lorsque le polygone pave le plan.

We establish a relationship between the word complexity and the number of generalized diagonals for a polygonal billiard. We conclude that in the rational case the complexity function has cubic upper and lower bounds. In the tiling case the complexity has cubic asymptotic growth.

DOI : https://doi.org/10.5802/aif.1903
Classification : 37C35
Mots clés: complexité, billards polygonaux, diagonales généralisées, mots bispéciaux
@article{AIF_2002__52_3_835_0,
     author = {Cassaigne, J. and Hubert, Pascal and Troubetzkoy, Serge},
     title = {Complexity and growth for polygonal billiards},
     journal = {Annales de l'Institut Fourier},
     pages = {835--847},
     publisher = {Association des Annales de l'institut Fourier},
     volume = {52},
     number = {3},
     year = {2002},
     doi = {10.5802/aif.1903},
     zbl = {01794816},
     mrnumber = {1907389},
     language = {en},
     url = {aif.centre-mersenne.org/item/AIF_2002__52_3_835_0/}
}
Cassaigne, J.; Hubert, Pascal; Troubetzkoy, Serge. Complexity and growth for polygonal billiards. Annales de l'Institut Fourier, Tome 52 (2002) no. 3, pp. 835-847. doi : 10.5802/aif.1903. https://aif.centre-mersenne.org/item/AIF_2002__52_3_835_0/

[BKM] C. Boldrighini; M. Keane ; F. Marchetti Billiards in polygons, Ann. Prob., Volume 6 (1978), pp. 532-540 | Article | MR 644840 | Zbl 0377.28014

[BP] J. Berstel ; M. Pocchiola A geometric proof of the enumeration formula for Sturmian words, J. Alg. Comp., Volume 3 (1993), pp. 349-355 | Article | MR 1240390 | Zbl 0802.68099

[C] J. Cassaigne Complexité et facteurs spéciaux, Bull. Belgian Math. Soc., Volume 4 (1997), pp. 67-88 | | MR 1440670 | Zbl 0921.68065

[CT] N. Chernov; S. Troubetzkoy Ergodicity of billiards in polygons with pockets, Nonlinearity, Volume 11 (1998), pp. 1095-1102 | Article | MR 1632602 | Zbl 0906.58022

[GKT] G. Galperin; T. Krüger; S. Troubetzkoy Local instability of orbits in polygonal and polyhedral billiards, Comm. Math. Phys., Volume 169 (1995), pp. 463-473 | Article | MR 1328732 | Zbl 0924.58043

[Gu1] E. Gutkin Billiards in polygons, Physica D, Volume 19 (1986), pp. 311-333 | Article | MR 844706 | Zbl 0593.58016

[Gu2] E. Gutkin Billiards in polygons: survey of recent results, J. Stat. Phys., Volume 174 (1995), pp. 43-56 | MR 1382759 | Zbl 01554065

[GuH] E. Gutkin ; N. Haydn Topological entropy of generalized interval exchanges, Bull. AMS, Volume 32 (1995), pp. 50-57 | Article | MR 1273398 | Zbl 0879.54023

[GuT] E. Gutkin; S. Troubetzkoy Directional flows and strong recurrence for polygonal billiards, Proceedings of the International Congress of Dynamical Systems, Montevideo, Uruguay (Pitman Research Notes in Math.) Volume 362 (1996) | Zbl 0904.58036

[H] P. Hubert Dynamique symbolique des billards polygonaux rationnels (1995) (Thèse, Université d'Aix-Marseille II)

[H1] P. Hubert Complexité des suites définies par des billards rationnels, Bull. Soc. Math. France, Volume 123 (1995), pp. 257-270 | Numdam | MR 1340290 | Zbl 0836.58013

[H2] P. Hubert Propriétés combinatoires des suites définies par le billard dans les triangles pavants, Theoret. Comput. Sci., Volume 164 (1996), pp. 165-183 | Article | MR 1411203 | Zbl 0871.68146

[HW] G.H. Hardy; E.M. Wright An introduction to the theory of numbers, Oxford Univ. Press, 1964 | MR 67125 | Zbl 0058.03301

[K] A. Katok The growth rate for the number of singular and periodic orbits for a polygonal billiard, Comm. Math. Phys., Volume 111 (1987), pp. 151-160 | Article | MR 896765 | Zbl 0631.58020

[M2] H. Masur Lower bounds for the number of saddle connections and closed trajectories of a quadratic differential, Holomorphic functions and moduli, Volume vol. 1, Springer-Verlag, 1988 | MR 955824 | Zbl 0661.30034

[M1] H. Masur The growth rate of a quadratic differential, Ergod. Th. Dyn. Sys., Volume 10 (1990), pp. 151-176 | MR 1053805 | Zbl 0706.30035

[Mi] F. Mignosi On the number of factors of Sturmian words, Theor. Comp. Sci., Volume 82 (1991), pp. 71-84 | Article | MR 1112109 | Zbl 0728.68093

[MT] H. Masur; S. Tabachnikov Rational billiards and flat structures (1999) (preprint Max Planck Institut) | MR 1928530 | Zbl 1057.37034

[N] A. Nogueira Orbit distribution on 2 under the natural action of SL(2,) (2000) (IML preprint 21) | Zbl 1016.37003

[S] Ya. G. Sinai Introduction to ergodic theory, Princeton Univ. Press, 1976 | MR 584788 | Zbl 0375.28011

[T] S. Tabachnikov Billiards, Panoramas et Synthèses, Soc. Math. France, 1995 | MR 1328336 | Zbl 0833.58001

[Tr] S. Troubetzkoy Complexity lower bounds for polygonal billiards, Chaos, Volume 8 (1998), pp. 242-244 | Article | MR 1609769 | Zbl 0986.37030

[V] W. Veech Teichmüller curves in moduli space, Eisenstein series and an application to triangular billiards, Invent. Math., Volume 97 (1989), pp. 553-583 | Article | MR 1005006 | Zbl 0676.32006

[V1] W. Veech The billiard in a regular polygon, Geom. Func. Anal., Volume 2 (1992), pp. 341-379 | Article | MR 1177316 | Zbl 0760.58036