On the behavior of binary block-counting functions under addition
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913621437579264 |
|---|---|
| author | Sobolewski, Bartosz |
| author_facet | Sobolewski, Bartosz |
| contents | Let $\mathsf{s}(n)$ denote the sum of binary digits of an integer $n \geq 0$. In the recent years there has been interest in the behavior of the differences $\mathsf{s}(n+t)-\mathsf{s}(n)$, where $t \geq 0$ is an integer. In particular, Spiegelhofer and Wallner showed that for $t$ whose binary expansion contains sufficiently many blocks of $\mathtt{1}$s the inequality $\mathsf{s}(n+t) -\mathsf{s}(n) \geq 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 $\mathtt{1}$s in its binary expansion. This extends an earlier result by the author and Spiegelhofer for $w=\mathtt{11}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_15851 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the behavior of binary block-counting functions under addition Sobolewski, Bartosz Number Theory Combinatorics 11A63, 11BO5, 05A16 Let $\mathsf{s}(n)$ denote the sum of binary digits of an integer $n \geq 0$. In the recent years there has been interest in the behavior of the differences $\mathsf{s}(n+t)-\mathsf{s}(n)$, where $t \geq 0$ is an integer. In particular, Spiegelhofer and Wallner showed that for $t$ whose binary expansion contains sufficiently many blocks of $\mathtt{1}$s the inequality $\mathsf{s}(n+t) -\mathsf{s}(n) \geq 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 $\mathtt{1}$s in its binary expansion. This extends an earlier result by the author and Spiegelhofer for $w=\mathtt{11}$. |
| title | On the behavior of binary block-counting functions under addition |
| topic | Number Theory Combinatorics 11A63, 11BO5, 05A16 |
| url | https://arxiv.org/abs/2412.15851 |