## 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)].

### MSC:

 11B85 Automata sequences 68R15 Combinatorics on words

### Citations:

Zbl 0786.11041; Zbl 0803.68095; Zbl 0106.02204