On monochromatic arithmetic progressions in binary words associated with block-counting functions

Bartosz Sobolewski

Published 2022-04-11Version 1

Let $e_v(n)$ denote the number of occurrences of a fixed block $v$ of digits in the binary expansion of $n \in \mathbb{N}$. In this paper we study monochromatic arithmetic progressions in the class of binary words $(e_v(n) \bmod{2})_{n \geq 0}$, which includes the famous Thue--Morse word $\mathbf{t}$ and Rudin--Shapiro word $\mathbf{r}$. We prove that the length of a monochromatic arithmetic progression of difference $d \geq 3$ starting at $0$ in $\mathbf{r}$ is at most $(d+3)/2$, with equality for infinitely many $d$. Moreover, we compute the maximal length of a monochromatic arithmetic progression in $\mathbf{r}$ of difference $2^k-1$ and $2^k+1$. For a general block $v$ we provide an upper bound on the length of a monochromatic arithmetic progression of any difference $d$. We also prove other miscellaneous results and offer a number of related problems and conjectures.