On the behavior of binary block-counting functions under addition

Abstract

Let $\mathsf{s}(n)$ denote the sum of binary digits of an integer $n\ge 0$. In the recent years there has been interest in the behavior of the differences $\mathsf{s}(n+t)-\mathsf{s}(n)$, where $t\ge 0$ is an integer. In particular, Spiegelhofer and Wallner showed that for $t$ whose binary expansion contains sufficiently many blocks of $1$s the inequality $\mathsf{s}(n+t)-\mathsf{s}(n)\ge 0$ holds for $n$ belonging to a set of asymptotic density $>1/2$, partially answering a question by Cusick. Furthermore, for such $t$ the values $\mathsf{s}(n+t)-\mathsf{s}(n)$ are approximately normally distributed. In this paper we consider a natural generalization to the family of block-counting functions $N^w$, giving the number of occurrences of a block of binary digits $w$ in the binary expansion. Our main result show that for any $w$ of length at least $2$ the distribution of the differences $N^w(n+t)-N^w(n)$ is close to a Gaussian when $t$ contains many blocks of $1$s in its binary expansion. This extends an earlier result by the author and Spiegelhofer for $w=11$.

36 pages