Billiard complexity in the hypercube
Annales de l'Institut Fourier, Volume 57 (2007) no. 3, pp. 719-738.

We consider the billiard map in the hypercube of d . We obtain a language by coding the billiard map by the faces of the hypercube. We investigate the complexity function of this language. We prove that n 3d-3 is the order of magnitude of the complexity.

On considère l’application du billard dans le cube de d . On code cette application par les faces du cube. On obtient un langage, dont on cherche à évaluer la complexité. On montre que l’ordre de grandeur de cette fonction est n 3d-3 .

DOI: 10.5802/aif.2274
Classification: 37A35, 37C35, 05A16, 11N37, 28D
Keywords: Symbolic dynamic, billiard, words, complexity function
Mot clés : Dynamique symbolique, billard, mots, complexité
Bedaride, Nicolas 1; Hubert, Pascal 2

1 Fédération de recherches des unités de mathématiques de Marseille UMR 6632 Laboratoire d’Analyse Topologie et Probabilités Av. Escadrille Normandie-Niemen 13397 Marseille Cedex 20 (France)
2 Fédération de recherches des unités de mathématiques de Marseille UMR 6632 Laboratoire d’Analyse Topologie et Probabilités av. Escadrille Normandie-Niemen 13397 Marseille Cedex 20 (France)
@article{AIF_2007__57_3_719_0,
     author = {Bedaride, Nicolas and Hubert, Pascal},
     title = {Billiard complexity in the hypercube},
     journal = {Annales de l'Institut Fourier},
     pages = {719--738},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {57},
     number = {3},
     year = {2007},
     doi = {10.5802/aif.2274},
     zbl = {1138.37017},
     mrnumber = {2336827},
     language = {en},
     url = {http://archive.numdam.org/articles/10.5802/aif.2274/}
}
TY  - JOUR
AU  - Bedaride, Nicolas
AU  - Hubert, Pascal
TI  - Billiard complexity in the hypercube
JO  - Annales de l'Institut Fourier
PY  - 2007
SP  - 719
EP  - 738
VL  - 57
IS  - 3
PB  - Association des Annales de l’institut Fourier
UR  - http://archive.numdam.org/articles/10.5802/aif.2274/
DO  - 10.5802/aif.2274
LA  - en
ID  - AIF_2007__57_3_719_0
ER  - 
%0 Journal Article
%A Bedaride, Nicolas
%A Hubert, Pascal
%T Billiard complexity in the hypercube
%J Annales de l'Institut Fourier
%D 2007
%P 719-738
%V 57
%N 3
%I Association des Annales de l’institut Fourier
%U http://archive.numdam.org/articles/10.5802/aif.2274/
%R 10.5802/aif.2274
%G en
%F AIF_2007__57_3_719_0
Bedaride, Nicolas; Hubert, Pascal. Billiard complexity in the hypercube. Annales de l'Institut Fourier, Volume 57 (2007) no. 3, pp. 719-738. doi : 10.5802/aif.2274. http://archive.numdam.org/articles/10.5802/aif.2274/

[1] Arnoux, P.; Mauduit, C.; Shiokawa, I.; Tamura, J. Complexity of sequences defined by billiard in the cube, Bull. Soc. Math. France, Volume 122 (1994) no. 1, pp. 1-12 | EuDML | Numdam | MR | Zbl

[2] Baryshnikov, Yu. Complexity of trajectories in rectangular billiards, Comm. Math. Phys., Volume 174 (1995) no. 1, pp. 43-56 | DOI | MR | Zbl

[3] Bedaride, N. Billiard complexity in rational polyhedra, Regul. Chaotic Dyn., Volume 8 (2003) no. 1, pp. 97-104 | DOI | MR | Zbl

[4] Bedaride, N. Entropy of polyhedral billiard (2005) (submitted) | Zbl

[5] Bedaride, N. A generalization of Baryshnikov’s formula. (2006) (Preprint)

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

[7] Cassaigne, J. Complexité et facteurs spéciaux, Bull. Belg. Math. Soc. Simon Stevin, Volume 4 (1997) no. 1, pp. 67-88 Journées Montoises (Mons, 1994) | EuDML | MR | Zbl

[8] Cassaigne, J.; Hubert, P.; Troubetzkoy, S. Complexity and growth for polygonal billiards, Ann. Inst. Fourier, Volume 52 (2002) no. 3, pp. 835-847 | DOI | EuDML | Numdam | MR | Zbl

[9] Fulton, William Intersection theory, Springer-Verlag, Volume 2 (1998), pp. xiv+470 | MR | Zbl

[10] Galʼperin, G.; Krüger, T.; Troubetzkoy, S. Local instability of orbits in polygonal and polyhedral billiards, Comm. Math. Phys., Volume 169 (1995) no. 3, pp. 463-473 | DOI | MR | Zbl

[11] Hardy, G. H.; Wright, E. M. An introduction to the theory of numbers, The Clarendon Press Oxford University Press, New York, 1979 | MR | Zbl

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

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

[14] Masur, H. The growth rate of trajectories of a quadratic differential, Ergodic Theory Dynam. Systems, Volume 10 (1990) no. 1, pp. 151-176 | DOI | MR | Zbl

[15] Mignosi, F. On the number of factors of Sturmian words, Theoret. Comput. Sci., Volume 82 (1991) no. 1, Algorithms Automat. Complexity Games, pp. 71-84 | DOI | MR | Zbl

[16] Morse, M.; Hedlund, G. A. Symbolic dynamics II. Sturmian trajectories, Amer. J. Math., Volume 62 (1940), pp. 1-42 | DOI | MR | Zbl

Cited by Sources: