On the sum-of-digits measures and Cusick’s conjecture via stopped random walks
Dawid Tarłowski, ORCID 0000-0002-6824-4568; Faculty of Mathematics and Computer Science, Jagiellonian University, Łojasiewicza 6, 30-348 Kraków, Poland · 2026
Read On the sum-of-digits measures and Cusick’s conjecture via stopped random walks by Dawid Tarłowski, ORCID 0000-0002-6824-4568; Faculty of Mathematics and Computer Science, Jagiellonian University, Łojasiewicza 6, 30-348 Kraków, Poland (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-08624.txt.
Introduction
Dawid Tarłowski revisits Cusick's conjecture, a claim about counting ones in binary expansions. Adding a fixed number to n changes its count of ones, and the conjecture says counts more often rise than fall, for every shift. Tarłowski reorders the odd numbers to turn the density question into a growing tree process with an attached stopped random walk.
That view yields a clear structural account of the densities, covering support, symmetry, variance, and when normal or almost sure behavior rules. The conjecture itself reduces to a special case of a broader claim about uneven tree growth, which numeric work supports. Number theory gains fresh machinery for a stubborn digit problem, though the conjecture stays open.
Catalog record
| CREATOR | Dawid Tarłowski, ORCID 0000-0002-6824-4568; Faculty of Mathematics and Computer Science, Jagiellonian University, Łojasiewicza 6, 30-348 Kraków, Poland |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.08624
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the sum-of-digits measures and Cusick’s conjecture via stopped random walks Thanks: E-mail addresses: [email protected] ; [email protected] Dawid Tarłowski, ORCID 0000-0002-6824-4568; Faculty of Mathematics and Computer Science, Jagiellonian University, Łojasiewicza 6, 30-348 Kraków, Poland Abstract . Let s ( n ) s(n) denote the number of ones in the binary expansion of a natural number n ∈ ℕ n\in\mathbb{N} . For any t ∈ ℕ t\in\mathbb{N} and d ∈ ℤ d\in\mathbb{Z} , let μ t ( d ) \mu_{t}(d) denote the asymptotic density of the set of those natural numbers n n for which s ( n + t ) − s ( n ) = d s(n+t)-s(n)=d . The μ t \mu_{t} are properly defined probability measures on ℤ \mathbb{Z} , and the Cusick conjecture states that μ t ( ℕ ) > 1 2 \mu_{t}(\mathbb{N})>\frac{1}{2} for any t ∈ ℕ t\in\mathbb{N} . We investigate the properties of the family { μ t } t ∈ ℕ \{\mu_{t}\}_{t\in\mathbb{N}} by reindexing the odd integers via a suitable partial order. This construction leads to a nonautonomous dynamics on pairs of probability measures on ℤ \mathbb{Z} , which represents the process of growing a tree. The associated stopped random walk allows a transparent structural description of those measures, including their support, symmetries, variance, and an asymptotic dichotomy between the central limit theorem and the almost sure convergence. Next, we focus on the median-preserving property of this process, and show that the Cusick conjecture is a special case of a more general claim about the asymmetric evolution of the associated binary trees, which we support numerically. 1. Introduction Let s(n) denote the number of ones in the binary expansion of an integer n\in\mathbb{N} , namely, \textstyle s(n)=\sum_{k=0}^{m}n_{k}, where: (1.1) \textstyle n=\sum_{k=0}^{m}n_{k}\cdot 2^{k}\mbox{ and }n_{k}\in\{0,1\}\mbox{ for }k=0,1,\dots,m. Throughout the paper we write \mathbb{N}=\{0,1,2,\dots\} and \mathbb{N}^{+}=\{1,2,3,\dots\} . Given any t\in\mathbb{N} and d\in\mathbb{Z} , let \mu_{t}(d) denote the asymptotic density of the set of those natural numbers n for which s(n+t)-s(n)=d , i.e. (1.2) \mu_{t}(d)=\lim_{N\to\infty}\frac{1}{N}|\{n<N\colon s(n+t)-s(n)=d\}|. It is well known that the limit ( 1.2 ) exists, and \mu_{t} is a properly defined probability measure on \mathbb{Z} . Moreover, all the measures \mu_{t} have mean zero, i.e. \sum\limits_{k\in\mathbb{Z}}k\cdot\mu_{t}(k)=0 , and the following recurrence relations are satisfied: (1.3) \mu_{2t}(d)=\mu_{t}(d),\ t\in\mathbb{N},\ d\in\mathbb{Z}, (1.4) \mu_{2t+1}(d)=\frac{1}{2}\mu_{t}(d-1)+\frac{1}{2}\mu_{t+1}(d+1),\ t\in\mathbb{N},\ d\in\mathbb{Z}. For more details, see Lemma 1 in [ 1 ] , Lemma 2.1 in [ 4 ] . This paper is motivated by the Cusick’s conjecture which states that (1.5) {\textstyle{\mu_{t}(\mathbb{N})>\frac{1}{2}\mbox{ for any }t\in\mathbb{N}^{+}.}} The simplicity of the above statement is rather deceptive - the full conjecture is still open, although various results on the subject have been established ( [ 4 , 6 , 7 , 11 , 15 , 16 , 17 ] ). We briefly highlight some of them: paper [ 4 ] has shown that for any \varepsilon>0 we have |\{t<T\colon\frac{1}{2}<\mu_{t}(\mathbb{N})<\frac{1}{2}+\varepsilon\}|=T-O(\frac{T}{\log T}) (the symbol O(\cdot) stands for big O notation) which implies that the asymptotic density of the set of t\in\mathbb{N} which satisfy \mu_{t}(\mathbb{N})>\frac{1}{2} equals to one. In [ 7 ] , a central limit theorem is established for generic sequences (\mu_{t_{k}}) arising by sampling digits of t_{k} from the balanced Bernoulli measure. Papers [ 11 ] and [ 17 ] have generalized this result, and additionally [ 17 ] has shown that \mu_{t}(\mathbb{N})>\frac{1}{2} for any t such that (t)_{2} contains sufficiently many blocks of ones. Recently, [ 19 ] has proposed the decomposition of the characteristic functions associated to \mu_{t} into the sum of the corresponding components. Finally, we mention that Cusick conjecture has several equivalent formulations, see Section 3 in [ 4 ] , and is connected to Tu-Deng conjecture [ 3 ] , [ 20 ] , [ 16 ] . A full proof of Cusick’s conjecture is likely to require a detailed structural understanding of the family \{\mu_{t}\}_{t\in\mathbb{N}} . We will show that, after reindexing the odd integers via an appropriate partial order \preceq , the family \{\mu_{t}\}_{t\in 2\mathbb{N}+1} corresponds to the marginal distributions of a hierarchical martingale defined by a stopped random walk, governed by an explicit recursive dynamics. For convenience we will assume that the random walk starts from zero, that is, we will work with the system of measures P_{t} which is related to \mu_{t} by the convolution: \mu_{t}=\mu_{1}\ast P_{t} . First we will show that the maximal chains of the poset (2\mathbb{N}+1,\preceq) determine the nonautonomous dynamics on pairs of probability measures on \mathbb{Z} which represents the growth of a planar binary tree, and next we will express it in the language of the stopped random walk. The marginal probability distributions of the associated martingale - namely the measures P_{t} - exhibit several rather desirable properties: the monotonicity of the span of the support, the monotonicity of the variance with the explicit bounds (Theorem 19 ), the symmetries, and clear asymptotic behaviour: the unbounded variance case satisfies the central limit theorem (by [ 11 ] , [ 17 ] ) while in the case of bounded variance the trajectories of the martingale are convergent, and the possible asymptotic distributions are exactly the measures \mu_{t} and their reflections (Theorem 21 ). At the end of the paper we focus on the median-preserving property of the martingale, and show that the Cusick conjecture is a special case of a more general statement concerning the asymmetric growth of the trees. In the language of binary digits: if P_{t}(\mathbb{N})>\frac{1}{2} for any odd t=(t_{1}t_{2}\dots t_{n})_{2} with t_{2}=0 , then \mu_{t}(\mathbb{N})>\frac{1}{2} for any t\in\mathbb{N} . We conjecture that the side of the tree that carries mass greater than \frac{1}{2} at the first step of the growth, remains so throughout the whole process (Conjecture 24 ). This last claim is supported numerically, and left open. 2. The evolution of sum of digits measures. 2.1. Order Let us start with the sequence x_{n}=s(n+1)-s(n) , n\in\mathbb{N} , which defines measure \mu_{1} . Let \tau_{k}=\min\{n\in\mathbb{N}\colon x_{n}=k\}\mbox{, where }k\in\mathbb{Z}_{\leq 1}=\{d\in\mathbb{Z}\colon d\leq 1\}. It is not difficult to establish that x_{n} is given by: \tau_{k}=2^{1-k}\mbox{ and }x_{\tau_{k}+i}=x_{i}\mbox{ for }1\leq i<2^{1-k},\mbox{ where }k\in\mathbb{Z}_{\leq 1}. The first elements of \{x_{n}\}_{n\in\mathbb{N}} are: \textbf{1},\ \ \textbf{0},1,\ \ \textbf{-1},1,0,1,\ \ \textbf{-2},1,0,1,-1,1,0,1,\ \ \textbf{-3},1,0,1,-1,1,0,1,-2,1,0,1,-1,1,0,1,\textbf{-4},\dots\\ The above sequence is an elegant representation of a geometric distribution with mean zero, more precisely, the corresponding frequencies lead to the formula: (2.1) \mu_{1}(k)=\left(\frac{1}{2}\right)^{2-k}\mbox{ for }k=1,0,-1,-2,\dots In this chapter we want to gain good insight into how the measures \mu_{t} evolve from \mu_{1} . By ( 1.3 ), only odd t have to be considered. To see that, we will consider an appropriate partial order on the set of odd natural numbers. We start from describing the intuition behind the above idea. Roughly speaking, equations ( 1.3 ) and ( 1.4 ) lead to the following tree-structured decomposition of a natural number t : If t is even, divide it by 2 . If t is odd and greater than one, split t into two numbers: \frac{t-1}{2} and \frac{t+1}{2} . For every number that has appeared, repeat this operation until one is reached . We will reverse time in this decomposition, and omit the even numbers, thereby obtaining a more straightforward evolution of \mu_{t} .The initial measure \mu_{1} is already defined. By ( 1.3 ) and ( 1.4 ),