Sturmian words and the Stern sequence (Q2345447)

There is a natural one-to-one correspondence between words on a binary alphabet \(\left\{ 0,1\right\} \) and nodes of a complete infinite binary tree. The empty word \(\varepsilon\) corresponds to the root, \(0\) means moving to the left son, \(1\) means moving to the right son. The authors consider two special closely related labelings by irreducible fractions of the infinite binary tree called the Raney (or Calkin-Wilf) tree and the Stern-Brockot tree. This allows arithmetization of the terms of central, standard, and Christoffel words which, as written in the abstract of the paper, ``are three strongly interrelated classes of binary finite words which represent a finite counterpart to characteristic Sturmian words''. The labels in the two kinds of trees provide a characterization of the well-known Stern's diatomic sequence, which, in another approach, can be defined as follows: \(s\left( 0\right) =s\left( 1\right) =1\), \(s\left( 2n)=s(n\right)\), \(s(2n+1)=s(n)+s(n+1)\). One description of standard Sturmian words was previously given by the first author using the palindromization map \(\psi\), where \(\psi\left( \varepsilon\right) =\varepsilon\) and, for a word \(w\) and a symbol \(a\), \(\psi\left( wa\right) \) is the shortest palindrome having the prefix \(\psi\left( w\right) a\). The authors prove the relationship of this map to Stern's sequence thus allowing to apply the properties of Stern's sequence in the combinatorics of standard Sturmian words and related word classes. The main result is the following theorem. For \(w\in\left\{ 0,1\right\} ^{\ast}\), consider all position sequences describing occurrences of scattered subwords from \(1\left( 01\right) ^{\ast}\) in \(1w1\). If each initial position (the scattered subword starting with the first symbol of \(1w1\)) is denoted by \(0\) and all other positions by \(1\), then the lexicographically sorted sequence of reversals of the positions yields the word \(\psi\left( w\right) 10\). This is an analogue of the ``alternating bit sets theorem'' of Calkin and Wilf which states that \(s\left( n\right) \) is equal to the number of occurrences of the subwords \(1\left( 01\right) ^{\ast}\) in the binary expansion of \(n\). Some properties of the length of Christoffel words and their distributions are shown as well.