On monochromatic arithmetic progressions in binary words associated with pattern sequences

Abstract

Let $e_v(n)$ denote the number of occurrences of a fixed pattern $v$ 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)\mathrm{mod}2{)}_{n\ge 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\ge 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 pattern $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.

arXiv comment31 pages, 3 figures. Slightly changed the title and abstract, added references and additional comments in Section 1, merged Sections 3 and 4 into one and rewrote the proofs in there