Sturmian words and the Stern sequence

Abstract: Central, standard, and Christoffel words are three strongly interrelated classes of binary finite words which represent a finite counterpart of characteristic Sturmian words. A natural arithmetization of the theory is obtained by representing central and Christoffel words by irreducible fractions labeling respectively two binary trees, the Raney (or Calkin-Wilf) tree and the Stern-Brocot tree. The sequence of denominators of the fractions in Raney's tree is the famous Stern diatomic numerical sequence. An interpretation of the terms

s (n)

of Stern's sequence as lengths of Christoffel words when

n

is odd, and as minimal periods of central words when

n

is even, allows one to interpret several results on Christoffel and central words in terms of Stern's sequence and, conversely, to obtain a new insight in the combinatorics of Christoffel and central words by using properties of Stern's sequence. One of our main results is a non-commutative version of the "alternating bit sets theorem" by Calkin and Wilf. We also study the length distribution of Christoffel words corresponding to nodes of equal height in the tree, obtaining some interesting bounds and inequalities.

Review text

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.

Recommendations

Cites work

Cited in

(14)

Describes a project that uses

Uses Software

OEIS

This page was built for publication: Sturmian words and the Stern sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2345447)