no. 3
Complexity and growth for polygonal billiards
[Complexité et diagonales généralisées dans les billards polygonaux]
Cassaigne, J.1 ; Hubert, Pascal1 ; Troubetzkoy, Serge2
1 Institut de Mathématiques de Luminy, Case 907, 13288 Marseille Cedex 9 (France)
2 Centre de Physique Théorique, Institut de Mathématiques de Luminy, Case 907, 13288 Marseille Cedex 9 (France)
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 : 10.5802/aif.1903
Classification : 37C35
Keywords: complexity, polygonal billiards, generalized diagonals, bispecial words
Mot clés : complexité, billards polygonaux, diagonales généralisées, mots bispéciaux
Cassaigne, J. 1 ; Hubert, Pascal 1 ; Troubetzkoy, Serge 2

1 Institut de Mathématiques de Luminy, Case 907, 13288 Marseille Cedex 9 (France)
2 Centre de Physique Théorique, Institut de Mathématiques de Luminy, Case 907, 13288 Marseille Cedex 9 (France) 
@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{\textquoteright}institut Fourier},
     volume = {52},
     number = {3},
     year = {2002},
     doi = {10.5802/aif.1903},
     mrnumber = {1907389},
     zbl = {01794816},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/aif.1903/}
}
TY  - JOUR
AU  - Cassaigne, J.
AU  - Hubert, Pascal
AU  - Troubetzkoy, Serge
TI  - Complexity and growth for polygonal billiards
JO  - Annales de l'Institut Fourier
PY  - 2002
SP  - 835
EP  - 847
VL  - 52
IS  - 3
PB  - Association des Annales de l’institut Fourier
UR  - http://www.numdam.org/articles/10.5802/aif.1903/
DO  - 10.5802/aif.1903
LA  - en
ID  - AIF_2002__52_3_835_0
ER  - 
%0 Journal Article
%A Cassaigne, J.
%A Hubert, Pascal
%A Troubetzkoy, Serge
%T Complexity and growth for polygonal billiards
%J Annales de l'Institut Fourier
%D 2002
%P 835-847
%V 52
%N 3
%I Association des Annales de l’institut Fourier
%U http://www.numdam.org/articles/10.5802/aif.1903/
%R 10.5802/aif.1903
%G en
%F 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. http://www.numdam.org/articles/10.5802/aif.1903/

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

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

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

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

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

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

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

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

[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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cité par Sources :