Question about a certain coding of rotations

Question

Notation: A word $w$ on the alphabet $A=\{a,b\}$ having $2p$ letters can be viewed as a word $w'$ having $p$ letters on the alphabet $A'=A^2$. I denote by $\beta(w)$ the number of occurences of the letter "$bb$" in the word $w'$. For example $\beta(aaab)=0$, $\beta(abbb)=1$, $\beta(abba)=0$.

Let $T$ be the rotation on $\mathbb{R}/\mathbb{Z}$ with irrational angle $\theta=\sqrt{2}-1$. I denote by $w_n$ a word of length $2^n$ obtained by coding by "$a$" and "$b$" a $2^n$-piece of a trajectory $x, Tx, \ldots, T^{2^n-1}x$ according to whether it's in $(0,\theta)$ or not.

The word $w_1$ takes three possible values, namely $ab$, $ba$ or $bb$. Thus $\beta(w_1) \in \{0,1\}$.

With the help of simulations I observed the following facts :

• $\beta(w_2) \in \{0,1\}$. That is, $w_2=w_1w'_1$ and the case $\beta(w_1)=\beta(w'_1)=1$ never occurs.

• $\beta(w_3) \in \{0,1\}$. That is, $w_3=w_2w'_2$ and the case $\beta(w_2)=\beta(w'_2)=1$ never occurs.

• $\beta(w_4) \in \{1,2\}$. That is, $w_4=w_3w'_3$ and the case $\beta(w_3)=\beta(w'_3)=0$ never occurs.

• $\beta(w_5) \in \{2,3\}$: that is $\beta(w_4)=\beta(w'_4)=2$ never occurs.

• $\beta(w_6) \in \{5,6\}$: $2+2$ never occurs.

• $\beta(w_7) \in \{10,11\}$: $6+6$ never occurs.

• $\beta(w_8) \in \{21,22\}$: $10+10$ never occurs.

So a conjecture is that $\beta(w_n)$ takes two consecutive possible values for every $n$. How could we prove it? This also seems to work for every value of $\theta < 1/2$. Is there a proof which works for every $\theta<1/2$?

Answer 1

This is true for every irrational $\theta$; the question can be rephrased in terms of Sturmian sequences. Given a sequence $z \in \{a,b\}^\mathbb{Z}$ and indices $i<j$, let $z_{[i,j]} \in \{a,b\}^{j-i+1}$ be the subword of $z$ given by $z_i \cdots z_j$. Let $c(z_{[i,j]})$ be the number of times the symbol $b$ appears in $z_i\cdots z_j$. The sequence $z$ is Sturmian if it is not eventually periodic and if it is balanced, meaning that for every $n$, the quantity $c_{[i,i+n]}(z)$ takes exactly two values as $i$ varies. The usual definition of Sturmian is that $z$ contains exactly $n+1$ distinct subwords of length $n$ (for every $n$), but the two can be shown to be equivalent.

A sequence arises as a coding for an irrational rotation (using the convention you describe) if and only if it is Sturmian; this was shown by Morse and Hedlund in 1940; in fact they considered codings of geodesic flow on a torus, but it is equivalent. The condition $\theta < \frac 12$ is equivalent to the condition that $bb$ appears and $aa$ does not, so let's assume this from now on.

A Sturmian word is a subword of a Sturmian sequence. Let $w$ be a Sturmian word of length $2n$, and partition it into $n$ blocks of length $2$. Each of these is either $ab$, $ba$, or $bb$ (since $aa$ and $bb$ cannot both appear in a Sturmian word). Let $\beta(w)$ be the number of these that are equal to $bb$; then it is easy to see that the number of $b$s in $w$ is $c(w) = n + \beta(w)$. Since $w$ came from a Sturmian sequence $z$, every other subword $v$ of $z$ with length $2n$ also has $c(v) = n + \beta(v)$, and moreover $|c(v) - c(w)| \leq 1$. We conclude that $|\beta(v) - \beta(w)|\leq 1$.

Answer 2

To Vaughn's excellent answer I can only add that a must-read book on Sturmian words is

M. Lothaire, Algebraic Combinatorics on Words