Monochromatic arithmetic progressions in binary Thue–Morse-like words

Journal article


Aedo, I., Grimm, U., Nagai, Y. and Staynova, P. 2022. Monochromatic arithmetic progressions in binary Thue–Morse-like words. Theoretical Computer Science. 943, pp. 65-80. https://doi.org/10.1016/j.tcs.2022.08.013
AuthorsAedo, I., Grimm, U., Nagai, Y. and Staynova, P.
Abstract

We study the length of monochromatic arithmetic progressions in the Thue–Morse word and in a class of generalised Thue–Morse words. In particular, we give exact values or upper bounds for the lengths of monochromatic arithmetic progressions of given fixed differences inside these words. Some arguments for these are inspired by van der Waerden's proof for the existence of arbitrary long monochromatic arithmetic progressions in any finite colouring of the (positive) integers. We also establish upper bounds for the length of monochromatic arithmetic progressions of certain differences in any fixed point of a primitive binary bijective substitution.

KeywordsCombinatorics on words; Binary language; Infinite word; Thue–Morse sequence; Arithmetic progression; Bijective substitution; Bijective automata
Year2022
JournalTheoretical Computer Science
Journal citation943, pp. 65-80
PublisherElseiver
ISSN0304-3975
Digital Object Identifier (DOI)https://doi.org/10.1016/j.tcs.2022.08.013
Web address (URL)https://www.sciencedirect.com/science/article/pii/S0304397522004868
Accepted author manuscript
File Access Level
Open
Publisher's version
License
File Access Level
Open
Output statusPublished
Publication dates
Online19 Aug 2022
Publication process dates
Accepted12 Aug 2022
Deposited07 Jul 2023
Permalink -

https://repository.derby.ac.uk/item/9y455/monochromatic-arithmetic-progressions-in-binary-thue-morse-like-words

Download files


Publisher's version
1-s2.0-S0304397522004868-main.pdf
License: CC BY 4.0
File access level: Open

  • 31
    total views
  • 26
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as