On monochromatic arithmetic progressions in binary words associated with pattern sequences

Let e v ( n ) denote the number of occurrences of a fixed pattern v in the binary expansion of n ∈ N . In this paper we study monochromatic arithmetic progressions in the class of binary words ( e v ( n ) mod 2 ) n ≥ 0 , which includes the famous Thue–Morse word t and Rudin–Shapiro word r . We prove that the length of a monochromatic arithmetic progression of difference d ≥ 3 starting at 0 in r is at most ( d + 3 ) / 2 , with equality for infinitely many d . We also compute the maximal length of a monochromatic arithmetic progression in r of difference 2 k − 1 and 2 k + 1 . For a general pattern v we show that the maximal length of a monochromatic arithmetic progression of difference d is at most linear in d . Moreover, we prove that a linear lower bound holds for suitable subsequences ( d k ) k ≥ 0 of differences. We also offer a number of related problems and conjectures.