Relative position in binary substitutions (Q7016749)

The authors introduce a new notion for binary sequences that are not ultimately constant, namely \textit{the relative position function}. For a sequence on the alphabet \(\{{\mathbf a}, {\mathbf b}\}\), let \(p_{\mathbf a}(n)\) and \(p_{\mathbf b}(n)\) denote the position of the \(n\)-th occurrence of \({\mathbf a}\), resp.~\({\mathbf b}\), in the sequence; the \textit{relative position function} is defined by: \(r(n) = p_{\mathbf b}(n) - p_{\mathbf a}(n)\). The authors study in detail many properties of this function \(r(n)\) (which is related to the runlengths of the sequence). They prove, among several other nice properties, that there is an algorithmic way of reconstructing a sequence from its relative position function, that any increasing function is the relative position function of some binary sequence, that the mean value of the relative position function is linked to the frequencies of the letters of fixed points of morphisms (if the frequencies exist). They study in particular the Fibonacci sequence and the \textit{extended Pisa family of morphisms} \({\mathbf a} \to {\mathbf a}^k {\mathbf b} {\mathbf a}^{\ell}\), \({\mathbf b} \to {\mathbf a}^m\) with \(k,m \geq 1\), \(\ell \geq 0\). (Note that this family contains the period-doubling morphism.) Finally they study the Thue-Morse sequence on \(\{-1, +1\}\), proving that this is the only sequence on \(\{-1, +1\}\) that is equal to its relative position function.