Billiard complexity in the hypercube

[Complexité du billard cubique multi-dimensionnel]

Bedaride, Nicolas ; Hubert, Pascal

Annales de l'Institut Fourier, Tome 57 (2007), p. 719-738 / Harvested from Numdam

Résumé

On considère l’application du billard dans le cube de $\mathbb{R}^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}$.

Abstract

We consider the billiard map in the hypercube of $\mathbb{R}^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.

Détail

Publié le : 2007-01-01

MR 2336827 | Zbl 1138.37017

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

Bibliographie

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

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

[3] Bedaride, N. Billiard complexity in rational polyhedra, Regul. Chaotic Dyn., Tome 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., Tome 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, Tome 4 (1997) no. 1, pp. 67-88 (Journées Montoises (Mons, 1994)) | MR 1440670 | Zbl 0921.68065

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

[9] Fulton, William Intersection theory, Springer-Verlag, Tome 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., Tome 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, Tome 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., Tome 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, Tome 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., Tome 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., Tome 62 (1940), pp. 1-42 | Article | MR 745 | Zbl 0022.34003