Morphic words, Beatty sequences and integer images of the Fibonacci language (Q2290645)

A \textit{morphic word} \(x\) is the image of the fixed point of a prolongable morphism \(g\) under a morphism \(f\), called a \textit{decoration}. A classical result of Cobham states that one can obtain \(x\) by choosing \(f\) to be a letter-to-letter coding and \(g\) to be a non-erasing morphism. In this paper, the author advocates that there are situations where it is more natural to take a decoration instead of a letter-to-letter coding to produce morphic words. In particular, he reconsiders a natural algorithm (discussed by several authors such as Honkala) to get letter-to-letter codings. In the first part of the paper, he studies the first differences of the sequence \(A(A(n))\) where \(A(n)=\lfloor \alpha n\rfloor\) with \(\alpha\) being a quadratic irrational. If the conjugate of \(\alpha\) has modulus less than one, then it is known that \(A(A(n))\) is a generalized Beatty sequence of the form \(p \lfloor \alpha n\rfloor + q n + r\), \(p\), \(q\), \(r\) being integers, and it follows that the first differences sequence is pure morphic. The author therefore considers the case where the conjugate has modulus larger than one. In that case he provides a morphism and a decoration proving that the first differences sequence is morphic. For the special case of \(\sqrt{2}\), an alternative proof is given in an appendix. The second example is defined as follows. Take the language \(L\) made of the factors occurring in the Fibonacci word and a homomorphism of the monoids \(S\) from this language (equipped with concatenation) to \((\mathbb{N},+)\). The question is to determine when the complement of \(S(L)\) is finite and in that case find its largest element. This is a version of the so-called Frobenius problem. The author therefore studies the sequence of first differences of \(\mathbb{N}\setminus S(L)\) as the decoration of the fixed point of a morphism.