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