Palindromes and two-dimensional Sturmian sequences (Q2731274)

Sturmian sequences can be defined as sequences \((u_n)_{n\geq 0}\) for which there exist an irrational number \(\alpha\) and a real number \(\beta\in (0,1)\) such that NEWLINE\[NEWLINE\begin{alignedat}{3} &\text{either}&\quad &\forall n\geq 0 &\quad u_n&= \bigl\lfloor (n+1)\alpha+\beta \bigr\rfloor- \bigl\lfloor n\alpha+\beta \bigr\rfloor\\ &\text{or}&\quad &\forall n\geq 0 &\quad u_n&= \bigl\lceil (n+1)\alpha+\beta \bigr\rceil- \bigl\lceil n\alpha+\beta \bigr\rceil. \end{alignedat}NEWLINE\]NEWLINE These sequences were introduced by \textit{M. Morse} and \textit{G. A. Hedlund} in 1940 [Am. J. Math. 62, 1-42 (1940; Zbl 0022.34003)] and can be defined in many equivalent ways. One of these consists in counting the palindromic blocks that occur in these sequences: a sequence is Sturmian if and only if it has exactly two blocks each of odd length and exactly one block of even length [this is a result of \textit{X. Droubay} and \textit{G. Pirillo}, Theor. Comput. Sci. 223, 73-85 (1999; Zbl 0930.68116); a particular case was given by \textit{X. Droubay}, Inf. Process. Lett. 55, 217-221 (1995; Zbl 1004.68537)]. NEWLINENEWLINENEWLINEWhat should be the definition of a two-dimensional Sturmian sequence? The equivalent conditions mentioned above have natural 2D generalizations, but these generalizations are no longer equivalent. NEWLINENEWLINENEWLINEIn the paper under review the authors study a 2D generalization of Sturmian sequences by means of a binary coding of a \(\mathbb{Z}^2\)-action on \(\mathbb{R}/\mathbb{Z}\) defined by two irrational rotations. They prove that a 2D uniformly recurrent sequence on \(\{0,1\}\) is Sturmian in this sense if and only if it contains exactly one centro-symmetric rectangular block of size \((m,n)\) if \(m\) is even and \(n\) odd, and exactly two such blocks otherwise. The last part of the paper gives applications to plane partitions. NEWLINENEWLINENEWLINENote that Reference [14] has appeared [Theor. Comput. Sci. 255, 539-553 (2001; Zbl 0981.68126)].