Billiard complexity in the hypercube

Bedaride, Nicolas; Hubert, Pascal

doi:10.5802/aif.2274

Billiard complexity in the hypercube [ Complexité du billard cubique multi-dimensionnel ]

Bedaride, Nicolas ; Hubert, Pascal

Annales de l'Institut Fourier, Tome 57 (2007) no. 3, pp. 719-738.

Résumé
Abstract

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^{3 d - 3}$ .

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^{3 d - 3}$ is the order of magnitude of the complexity.

MR 2336827 | Zbl 1138.37017 | 1 citation dans Numdam

DOI : https://doi.org/10.5802/aif.2274
Classification : 37A35, 37C35, 05A16, 11N37, 28D
Mots clés : Dynamique symbolique, billard, mots, complexité

@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'institut Fourier},
     volume = {57},
     number = {3},
     year = {2007},
     doi = {10.5802/aif.2274},
     mrnumber = {2336827},
     zbl = {1138.37017},
     language = {en},
     url = {www.numdam.org/item/AIF_2007__57_3_719_0/}
}

Bedaride, Nicolas; Hubert, Pascal. Billiard complexity in the hypercube. Annales de l'Institut Fourier, Tome 57 (2007) no. 3, pp. 719-738. doi : 10.5802/aif.2274. http://www.numdam.org/item/AIF_2007__57_3_719_0/

Bibliographie

[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 87681 | Numdam | MR 1259106 | Zbl 0791.58034

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

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

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

[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 | Article | MR 1240390 | Zbl 0802.68099

[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 119937 | MR 1440670 | Zbl 0921.68065

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

[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 | Article | MR 1328732 | Zbl 0924.58043

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

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

[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 | Article | MR 896765 | Zbl 0631.58020

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

[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 | Article | MR 1112109 | Zbl 0728.68093

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