zbMATH — the first resource for mathematics

Complexity of trajectories in rectangular billiards. (English) Zbl 0839.11006
The Sturmian sequences are the binary sequences that are a coding of a billiard trajectory in a \((2D)\) square, where the vertical sides are coded by 1 and the horizontal sides by 0. In particular, the (block) complexity of a Sturmian sequence is given by \(\rho (n) = n + 1\), where \(\rho (n)\) is the number of factors (subblocks) of the sequence with length \(n\).
What happens if one plays billiard in a cube or hypercube? A conjecture of Rauzy stated that the complexity of the trajectories for the cubic billiards is given by \(\rho (n) = n^2 + n + 1\). This conjecture has been proved by P. Arnoux, C. Mauduit, I. Shiokawa and J.-I. Tamura who published two papers [Bull. Soc. Math. Fr. 122, No. 1, 1-12 (1994; Zbl 0791.58034) and Tokyo J. Math. 17, No. 1, 211-218 (1994; Zbl 0814.11014)]. These four authors also conjectured a general formula for the hypercube, the formula presenting a mysterious symmetry in \(n\) (the length of blocks) and \(d-1\) (where \(d\) is the dimension).
The author of the paper under review solves the question completely stating in particular that, for reasonable starting angles, one has in dimension \(d\) \[ \rho_d (n) = \sum^{\min (d - 1,n)}_{k = 0} k! {d - 1 \choose k} {n \choose k}. \]

11B83 Special sequences and polynomials
68R15 Combinatorics on words
37E99 Low-dimensional dynamical systems
Full Text: DOI
[1] [AMST] Arnoux, P., Mauduit, C., Shiokawa, I., Tamura, J.-I.: Complexity of sequences defined by billiard in the cube. Bull. Soc. Math. France122, 1–12 (1994) · Zbl 0791.58034
[2] [B] Bruckstein, A. M.: Self-similarity properties of digitized straight lines. In: Vision geometry, Proc. AMS Spec. Sess., 851st Meet., Hoboken/NJ (USA) 1989, Contemp. Math.119, 1–20 (1991) · Zbl 0752.68063
[3] [FF] Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton, NJ: Princeton Univ. Press, 1962. · Zbl 0106.34802
[4] [LP] Lunnon, W.F., Pleasants, P.A.B.: Characterization of two-distance sequences. J. Aust. Math. Soc., Ser. A53, No. 2, 198–218 (1992) · Zbl 0759.11005
[5] [MH] Morse, M., Hedlund, G.A.: Symbolic dynamics II. Sturmian trajectories. Am. J. Math.62, 1–42 (1940) · JFM 66.0188.03
[6] [R] Rauzy, G.: Mots infinis et arithmetique. In: Automata on Infinite Words, Lect. Notes in Comp. Sciences192, Berlin, Heidelberg, New York: Springer (1985) pp. 165–171
[7] [S] Stolarsky, K.B.: Beatty sequences, continuous fractions and certain shift operators. Can. Math. Bull.19, 473–482 (1976) · Zbl 0359.10028
[8] [T] Tabachnikov, S.: Billiards. Preprint (1994)