On arithmetic progressions in the generalized Thue-Morse word. (English) Zbl 1330.68239
Manea, Florin (ed.) et al., Combinatorics on words. 10th international conference, WORDS 2015, Kiel, Germany, September 14–17, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-23659-9/pbk; 978-3-319-23660-5/ebook). Lecture Notes in Computer Science 9304, 191-196 (2015).
Summary: 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\).
For the entire collection see [Zbl 1320.68023].
For the entire collection see [Zbl 1320.68023].
References:
| [1] | Van der Waerden, BL, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wisk., 15, 212-216 (1927) · JFM 53.0073.12 |
| [2] | 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) · Zbl 0303.10056 |
| [3] | Allouche, J-P; Shallit, J.; Ding, C.; Helleseth, T.; Niederreiter, H., The ubiquitous Prouhet-Thue-Morse sequence, Sequences and Their applications, 1-16 (1999), New York: Springer, New York · Zbl 1005.11005 · doi:10.1007/978-1-4471-0551-0_1 |
| [4] | 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) |
| [5] | Frid, AE, Arithmetical complexity of symmetric D0L words, Theoret. Comput. Sci., 306, 1-3, 535-542 (2003) · Zbl 1263.68121 · doi:10.1016/S0304-3975(03)00345-1 |
| [6] | \(####\) |
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.
