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.



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 {dn} of differences along which the maximum length A (dn) of a monochromatic arithmetic progression (with fixed difference dn) grows at least polynomially in dn. 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


Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions
No digital document available to download for this item

Item Actions