On the abelian complexity of the Rudin-Shapiro sequence

Abstract

In this paper, we study the abelian complexity of the Rudin-Shapiro sequence and a related sequence. We show that these two sequences share the same complexity function $\rho (n)$ which satisfies certain recurrence relations. As a consequence, the abelian complexity function is $2$-regular. Further, we prove that the box dimension of the graph of the asymptotic function $\lambda (x)$ is $3/2$ where $\lambda (x)={\lim }_{k\to \infty }\rho (4^{k}x)/\sqrt{4^{k}x}$ and $\rho (x)=\rho (\lfloor x\rfloor )$ for any $x>0$.

18 pages, 1 figure