Monochromatic arithmetic progressions in automatic sequences with group structure

Aedo, Ibai; Grimm, Uwe; Mañibo, Neil; Nagai, Yasushi and Staynova, Petra (2024). Monochromatic arithmetic progressions in automatic sequences with group structure. Journal of Combinatorial Theory, Series A, 203, article no. 105831.

DOI: https://doi.org/10.1016/j.jcta.2023.105831

Abstract

We determine asymptotic growth rates for lengths of monochromatic arithmetic progressions in certain automatic sequences. In particular, we look at (one-sided) fixed points of aperiodic, primitive, bijective substitutions and spin substitutions, which are generalisations of the Thue-Morse and Rudin-Shapiro substitutions, respectively. For such infinite words, we show that there exists a subsequence {d_n} of differences along which the maximum length A (d_n) of a monochromatic arithmetic progression (with fixed difference d_n) grows at least polynomially in d_n. Explicit upper and lower bounds for the growth exponent can be derived from a finite group associated to the substitution. As an application, we obtain bounds for a van der Waerden-type number for a class of colourings parametrised by the size of the alphabet and the length of the substitution.

Viewing alternatives

Metrics

Item Actions

Export

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