Complexity and growth for polygonal billiards
Annales de l'Institut Fourier, Volume 52 (2002) no. 3, p. 835-847
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.
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.
DOI : https://doi.org/10.5802/aif.1903
Classification:  37C35
Keywords: complexity, polygonal billiards, generalized diagonals, bispecial words
@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},
     publisher = {Association des Annales de l'institut Fourier},
     volume = {52},
     number = {3},
     year = {2002},
     pages = {835-847},
     doi = {10.5802/aif.1903},
     zbl = {01794816},
     mrnumber = {1907389},
     language = {en},
     url = {http://www.numdam.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, Volume 52 (2002) no. 3, pp. 835-847. doi : 10.5802/aif.1903. http://www.numdam.org/item/AIF_2002__52_3_835_0/

[BKM] C. Boldrighini; M. Keane ; F. Marchetti Billiards in polygons, Ann. Prob., Tome 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., Tome 3 (1993), pp. 349-355 | Article | MR 1240390 | Zbl 0802.68099

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

[CT] N. Chernov; S. Troubetzkoy Ergodicity of billiards in polygons with pockets, Nonlinearity, Tome 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., Tome 169 (1995), pp. 463-473 | Article | MR 1328732 | Zbl 0924.58043

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

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

[GuH] E. Gutkin ; N. Haydn Topological entropy of generalized interval exchanges, Bull. AMS, Tome 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, Longman, Essex (Pitman Research Notes in Math.) Tome 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, Tome 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., Tome 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., Tome 111 (1987), pp. 151-160 | Article | MR 896765 | Zbl 0631.58020

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

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

[Mi] F. Mignosi On the number of factors of Sturmian words, Theor. Comp. Sci., Tome 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, Tome 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., Tome 97 (1989), pp. 553-583 | Article | MR 1005006 | Zbl 0676.32006

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