Complexity of trajectories in rectangular billiards. (English) Zbl 0839.11006

Baryshnikov, Yu.

Commun. Math. Phys. 174, No. 1, 43-56 (1995).

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}. \]

Reviewer: J.-P.Allouche (Orsay)

MSC:

11B83	Special sequences and polynomials
68R15	Combinatorics on words
37E99	Low-dimensional dynamical systems

Keywords:

billiard in higher dimensions; generalized Sturmian sequences; trajectories cubic billiard; cubic billiard; hypercube

Citations:

Zbl 0791.58034; Zbl 0814.11014

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 · doi:10.1017/S1446788700035795
[5]	[MH] Morse, M., Hedlund, G.A.: Symbolic dynamics II. Sturmian trajectories. Am. J. Math.62, 1–42 (1940) · JFM 66.0188.03 · doi:10.2307/2371431
[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 · doi:10.4153/CMB-1976-071-6
[8]	[T] Tabachnikov, S.: Billiards. Preprint (1994)