Abstract
We consider the generalized Thue-Morse word on the alphabet \(\varSigma = \{0, 1, 2\}\). The object of the research is arithmetic progressions in this word, which are sequences consisting of identical symbols. Let A(d) be a function equal to the maximum length of an arithmetic progression with the difference d in the generalized Thue-Morse word. If n, d are positive integers and d is less than \(3^n\), then the upper bound for A(d) is \(3^n+6\) and is attained with the difference \(d=3^n-1\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Van der Waerden, B.L.: Beweis einer Baudetschen Vermutung. Nieuw Arch. Wisk. 15, 212–216 (1927)
Szemerédi, E.: On sets of integers containing no \(k\) elements in arithmetic progression. Collection of articles in memory of Juriǐ Vladimirović Linnik. Acta Arith. 27, 199–245 (1975)
Allouche, J.-P., Shallit, J.: The ubiquitous Prouhet-Thue-Morse sequence. In: Ding, C., Helleseth, T., Niederreiter, H. (eds.) Proceedings of SETA 1998, pp. 1–16. Springer, New York (1999)
Avgustinovich, S. V., Fon-der-Flaass, D. G., Frid, A. E.: Arithmetical complexity of infinite words. In: Proceedings of Words, Languages and Combinatorics III (2000), pp. 51–62 . World Scientific, Singapore (2003)
Frid, A.E.: Arithmetical complexity of symmetric D0L words. Theoret. Comput. Sci. 306(1–3), 535–542 (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Parshina, O.G. (2015). On Arithmetic Progressions in the Generalized Thue-Morse Word. In: Manea, F., Nowotka, D. (eds) Combinatorics on Words. WORDS 2015. Lecture Notes in Computer Science(), vol 9304. Springer, Cham. https://doi.org/10.1007/978-3-319-23660-5_16
Download citation
DOI: https://doi.org/10.1007/978-3-319-23660-5_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23659-9
Online ISBN: 978-3-319-23660-5
eBook Packages: Computer ScienceComputer Science (R0)