6
$\begingroup$

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$?

$\endgroup$

2 Answers 2

6
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

M. Lothaire, Algebraic Combinatorics on Words

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.