Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups (Q1119694): Difference between revisions

The (Prouhet)-Thue-Morse sequence is one of the fixed points of the morphism \(a\to ab\), \(b\to ba\). The authors define \(\phi\) (n) to be the number of factors w of the Thue-Morse sequence such that both wa and wb are factors, (``special factors''). They then prove that \(\phi\) (n) is equal either to 2 or to 4 for \(n\geq 1\). They also characterize those n such that \(\phi (n)=2\) and give an algorithm to construct all special factors of given length. Denoting by F(n) the total number of factors of length n (in the Thue- Morse sequence), they deduce the exact value of F(n) (using the relation \(F(n+1)=F(n)+\phi (n))\), and obtain the inequalities \(3n\leq F(n+1)\leq 10n/3.\) (Note that every automatic sequence satisfies F(n)\(\leq Cn\), see \textit{A. Cobham}, Math. Syst. Theory 6, 164-192 (1972; Zbl 0253.02029). As a consequence they prove that the Thue-Morse monoid is finitely generated, periodic, infinite and weakly permutable. Note, as the authors point out, that an enumeration formula for the factors of the Thue-Morse sequence has been independently obtained by \textit{S. Brlek} [Enumeration of factors in the Thue-Morse word, in Proc. Coll. Montréalais sur la Combinatoire et l'Informatique (to appear)].