Substitution invariant Beatty sequences. (English) Zbl 0868.11015

Komatsu, Takao; van der Poorten, Alfred J.

Jap. J. Math., New Ser. 22, No. 2, 349-354 (1996).

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

Reviewer: J.-P.Allouche (Orsay)

MSC:

11B85	Automata sequences
68R15	Combinatorics on words

Keywords:

Sturmian sequences; characteristic sequences; Beatty sequences; continued fractions; fixed points of substitutions

Citations:

Zbl 0786.11041; Zbl 0803.68095; Zbl 0106.02204