Recurrence function of the generalized Thue–Morse word

Mahamadi Nana, Boucaré Kientéga and Idrissa Kaboré
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 32, 2026, Number 3, Pages 590–609
DOI: 10.7546/nntdm.2026.32.3.590-609
Full paper (PDF, 272 Kb)

Details

Authors and affiliations

Mahamadi Nana
Département de Mathématiques, UFR Sciences et Techniques, Université Nazi Boni
01BP 1091 Bobo Dioulasso, Burkina Faso

Boucaré Kientéga
Département de Mathématiques, Informatique et Economie Appliquées, Institut Universitaire Professionnalisant, Université Daniel Ouezzin Coulibaly
BP 176 D\’edougou, Burkina Faso

Idrissa Kaboré
Département de Mathématiques, UFR Sciences et Techniques, Université Nazi Boni
01BP 1091 Bobo Dioulasso, Burkina Faso

Abstract

This paper is devoted to the study of the recurrence function of q-ary Thue–Morse word t_q. After giving the structure of singular factors, we describe the maximal return time of factors of t_q. We conclude by determining the recurrence function of generalized Thue–Morse word.

Keywords

• Infinite words
• Maximal return time
• Singular factor
• Recurrence function

2020 Mathematics Subject Classification

• 68R15
• 11B85

References

1. Allouche, J. P., & Shallit, J. (2000). Sums of digits, overlaps, and palindromes. Discrete Mathematics and Theoretical Computer Science, 4(1), 1–10.
2. Balková, L., Pelantová, E., & Steiner, W. (2007). Return words in fixed points of substitutions. Preprint. Available online at: https://hal.science/hal-00089863v3.
3. Cassaigne, J. (1999). Limit values of the recurrence quotient of Sturmian sequences. Theoretical Computer Science, 218(1), 3–12.
4. Cassaigne, J. (2001). Recurrence in infinite words. In: Ferreira, A., & Reichel, H. (Eds.). Proceedings of STACS 2001. Lecture Notes in Computer Science, Vol. 2010, pp. 1–11. Springer, Berlin, Heidelberg.
5. Cassaigne, J., & Chekhova, N. (2006). Fonctions de récurrence des suites d’Arnoux-Rauzy et réponse à une question de Morse et Hedlund. Annales de l’Institut Fourier, 56(7), 2249–2270.
6. Durand, F. (1998). A characterization of substitutive sequences using return words. Discrete Mathematics, 179(1–3), 89–101.
7. Kaboré, I., Kientéga, B., & Nana, M. (2023). Recurrence function of the ternary
   Thue–Morse word. Advances and Applications in Discrete Mathematics, 39(1), 43–72.
8. Kientéga, B., Nana, M., & Barro, M. (2026). Singular factors of generalized Thue–Morse word. Far East Journal of Mathematical Sciences, 143(2), 375–398.
9. Nana, M., Kientéga, B., & Kaboré, I. (2024). Bispecial and separator factors in the generalized Thue–Morse word. RAMReS Sciences des Structures de la Matière, 8(1), 61–76.
10. Wen, Z.-X., & Wen, Z.-Y. (1994). Some properties of the singular words of the Fibonacci word. European Journal of Combinatorics, 15(6), 587–598.

Manuscript history

• Received: 3 February 2026
• Revised: 19 July 2026
• Accepted: 13 October 2026
• Online First: 31 October 2026

Copyright information

Ⓒ 2026 by the Authors.
This is an Open Access paper distributed under the terms and conditions of the Creative Commons Attribution 4.0 International License (CC BY 4.0).