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}.$

MSC:
 11B83 Special sequences and polynomials 68R15 Combinatorics on words 37E99 Low-dimensional dynamical systems
Full Text:
References:
 [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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.