Enumeration of factors in the Thue-Morse word. (English) Zbl 0683.20045

The infinite word of Thue-Morse M is the limit \(\lim_{n\to \infty}\phi^ n(a)\), where \(\phi\) is the endomorphism of the free monoid \(\{a,b\}^*\) defined by \(\phi (a)=ab\), \(\phi (b)=ba\). The author proves that if M is written \(w_ 1w_ 2\), then either \(w_ 1\) has a square suffix, or \(w_ 2\) has a square prefix. A byproduct of his methods allows him to deduce a result of Pansiot, which characterizes the square factors of M. Finally, he gives some results on the function \(P(m)=number\) of factors of length m of M, in particular \[ \liminf_{m\to \infty}P(m)/(m-1)=3\quad and\quad \limsup P(m)/(m- 1)=10/3. \]
Reviewer: Ch.Reutenauer


20M05 Free semigroups, generators and relations, word problems
05A15 Exact enumeration problems, generating functions
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: DOI


[1] Adian, S. I., The Burnside Problem and Identities in Groups (1979), Springer: Springer Berlin · Zbl 1343.20040
[2] Adler, A.; Li, S. Y.R., Magic cubes and Prouhet sequences, Amer. Math. Monthly, 84, 618-627 (1977) · Zbl 0389.05018
[3] Arshon, S., Démonstration de l’existence des suites asymétriques finies, Mat. Sb., 44, 769-777 (1937), (Russian) · Zbl 0018.11503
[4] A. de Luca and S. Varricchio, Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups (to appear).; A. de Luca and S. Varricchio, Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups (to appear). · Zbl 0671.10050
[5] Hall, M., Generators and relations in groups-The Burnside problem, (Saaty, T. L., Lectures on Modern Mathematics, Vol. 2 (1964), Wiley: Wiley New York), 42-92 · Zbl 0123.02002
[6] Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[7] Morse, M., A one to one representation of geodesics on a surface of negative curvature, Amer. J. Math., 43, 33-51 (1921) · JFM 48.0786.05
[8] Morse, M., Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc., 22, 84-100 (1921) · JFM 48.0786.06
[9] Morse, M.; Hedlund, G. A., Symbolic dynamics, Amer. J. Math., 60, 815-866 (1938) · JFM 64.0798.04
[10] Morse, M.; Hedlund, G. A., Unending chess, symbolic dynamics and a problem in semigroups, Duke Math. J., 11, 1-7 (1944) · Zbl 0063.04115
[11] Novikov, P. S.; Adian, S. I., On infinite periodic groups, Math. USSR Izv., 2, 665-685 (1968), English translation in · Zbl 0194.03301
[12] Pansiot, J. J., The Morse sequence and iterated morphisms, Inform. Process. Lett., 12, 68-70 (1981) · Zbl 0464.68075
[13] Prouhet, M. E., Mémoire sur quelques relations entre les puissances des nombres, C.R. Acad. Sci., 31 (1851), Paris
[14] Restivo, A.; Reutenauer, C., Rational languages and the Burnside problem, Theoret. Comput. Sci., 40, 13-30 (1985) · Zbl 0597.68057
[15] Thue, A., Über unendliche Zeichenreihen, Videnskabsselskabets Skrifter I Mat. Nat. Kl. Christiana, 7, 1-22 (1906) · JFM 39.0283.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.