PUB - Publikationen an der Universität Bielefeld

We determine asymptotic growth rates for lengths of mono-chromatic arithmetic progressions in certain automatic se-quences. In particular, we look at (one-sided) fixed points of aperiodic, primitive, bijective substitutions and spin sub-stitutions, 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 differ-ences along which the maximum length A(dn) of a monochro-matic 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. (c) 2023 Elsevier Inc. All rights reserved.