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