Substitution invariant Beatty sequences. (English) Zbl 0868.11015

What sequences \((f_\theta)\) defined by \(f_\theta(k)= \lfloor(k+1)\theta\rfloor- \lfloor k\theta\rfloor\), where \(\theta\) is an irrational number, are fixed points of substitutions (morphisms of the free monoid)? This problem has been solved by D. Crisp, W. Moran, A. Pollington and P. Shiue [J. Théor. Nombres Bordx. 5, 123-137 (1993; Zbl 0786.11041)] and a shorter proof was given by J. Berstel and P. Séébold [reference given in the paper under review but also in Bull. Belg. Math. Soc.-Simon Stevin 1, 175-189 (1994; Zbl 0803.68095)].
The authors give here a different, simpler and more efficient argument. Their main result reads as follows: Let \(\theta=[a_0, a_1,a_2,\dots]\), define \(T_0=0\), \(T_1= 0^{a_1-1}1\), \(T_n=T^{a_n}_{n-1} T_{n-2}\) for \(n\geq 2\) (hence \(f_\theta=\lim T_n)\), and let \(W\) be a substitution. Then,
(i) \(W(f_\theta)= f_\theta\iff \exists\;m\geq 0\) \(W(T_i)= T_{i+m}\) \(\forall\;i=1,2,\dots\) and
(ii) such a \(W\) exists if and only if \(a_{i+m}= a_i\) for \(i=3,4,\dots\) and either \(a_{2+m}= a_2\), or \(a_2=1\).
Note that Lemma 2 goes back to R. C. Lyndon and M. P. Schützenberger [Mich. Math. J. 9, 289-298 (1962; Zbl 0106.02204)].


11B85 Automata sequences
68R15 Combinatorics on words