Monochromatic Arithmetic Progressions in Binary Thue–Morse-Like Words

Aedo, Ibai; Grimm, Uwe; Nagai, Yasushi and Staynova, Petra (2022). Monochromatic Arithmetic Progressions in Binary Thue–Morse-Like Words. Theoretical Computer Science, 934 pp. 65–80.

DOI: https://doi.org/10.1016/j.tcs.2022.08.013

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.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 84734
• Item Type
• Journal Item
• ISSN
• 0304-3975
• Project Funding Details

• Funded Project Name	Project ID	Funding Body
  Not Set	EP/S010335/1	Engineering and Physical Sciences Research Council (EPSRC)
  Not Set	Not Set	Early Career Fellowship from the London Mathematical Society

• Keywords
• Combinatorics on words; Binary language; Infinite word; Thue–Morse sequence; Arithmetic progression; Bijective substitution
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © 2022 The Authors
• Depositing User
• ORO Import