🔢 mathematics

The equality cases $P_t(\mathbb{N})=\tfrac12$ for the deconvolved sum-of-digits measures

This paper completely resolves the open problem of characterizing when the equality $P_t(\mathbb{N})=\frac{1}{2}$ holds for deconvolved sum-of-digits measures by proving that for odd integers $t \ge 3$ , this equality occurs if and only if the binary representation of $t$ (excluding the leading and trailing ones) is "saturated," meaning every block of consecutive ones contains at least as many ones as there are zeros in the sequence.

Original authors: Dawid Tarłowski

Published 2026-08-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dawid Tarłowski

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of numbers, there is a simple yet profound way to count the ones in a number's binary form. If you write a number using only zeros and ones, like a computer does, you can simply count how many ones appear. Mathematicians call this the "sum of digits." For decades, researchers have been fascinated by what happens when you add a specific number to another and compare the count of ones before and after. Does the count go up, go down, or stay the same? By studying these changes across millions of numbers, mathematicians can calculate the probability, or likelihood, of a certain outcome. One of the most persistent questions in this field asks whether the count of ones tends to increase more often than it decreases. For a long time, this was a guess, a conjecture that seemed true but lacked a complete proof. The mystery centered on a specific threshold: does the probability of the count increasing ever drop to exactly fifty percent, or does it always stay slightly higher?

A recent paper by Dawid Tarlowski settles this question with absolute certainty, moving the field from guessing to knowing. The author has solved a problem that was left open by previous researchers, who had only been able to check the answer for specific numbers using computers. Tarlowski has now provided a complete rule that applies to every single odd number. The paper reveals that the probability of the count increasing is exactly fifty percent only for a very specific, rare group of numbers. For all other numbers, the probability is strictly greater than fifty percent, confirming the long-held belief that the count of ones almost always has a slight upward bias.

To understand how this works, imagine the binary representation of a number as a string of beads, some black and some white. The researchers looked at how this string changes when you add a fixed number to it. They discovered that the behavior of this change can be mapped onto a branching structure, similar to a family tree where each step splits into two paths. In this tree, one side represents the outcome where the count of ones increases, and the other side represents where it decreases. The central question was whether these two sides could ever be perfectly balanced. The paper proves that they can be balanced, but only if the original number's binary string follows a very strict pattern.

The author found that this perfect balance occurs only when the number's binary string is "saturated." In plain terms, this means that if you look at the groups of ones separated by zeros, every single group of ones must be long enough to match or exceed the total number of zeros in the string. If the string has three zeros, every cluster of ones must contain at least three ones. If even one cluster of ones is too short, the balance tips, and the probability of the count increasing rises above the fifty percent mark. The paper provides a precise formula to count how many such "saturated" numbers exist for any given length, showing that while they do exist, they become increasingly rare as the numbers get larger.

This discovery is significant because it closes the door on a decades-old uncertainty. Previous work had shown that the probability is generally high, but it could not explain the rare cases where it might be exactly half. Tarlowski's work identifies those rare cases completely. The paper demonstrates that for any number that does not fit the strict "saturated" pattern, the probability of the count increasing is not just high, but mathematically guaranteed to be higher than fifty percent by a specific, calculable amount. The author also establishes a lower bound for this probability, ensuring that even for the numbers closest to the fifty percent threshold, the bias remains measurable and real.

The method used to reach this conclusion involves a clever combination of probability theory and combinatorics, which is the study of counting and arranging objects. The author treats the process of adding numbers as a random walk, a path that moves step-by-step through a tree of possibilities. By analyzing the points where this path stops, the author can calculate the final probability. The key insight was realizing that the condition for a perfect fifty-fifty split is equivalent to a specific property of the binary string: that no matter how you try to insert an extra one into the string, you cannot create a new pattern that breaks the rules of the original structure. This structural rigidity is what keeps the probability at exactly fifty percent.

The results are definitive. The paper does not suggest or simulate; it proves. It shows that the set of numbers where the probability is exactly fifty percent is not random or chaotic, but follows a clear, logical rule based on the spacing of zeros and ones. For the vast majority of numbers, the rule is broken, and the probability of the count increasing is strictly greater than half. This confirms the intuition of earlier mathematicians and provides the missing piece of the puzzle. The work stands as a complete solution to the "saturation problem," a term used to describe the search for these exact equality cases.

In the end, the paper transforms a vague question about the behavior of numbers into a precise map. It tells us exactly which numbers are the exceptions and why they are exceptions. For any odd number, if you look at its binary form and find that every group of ones is sufficiently long compared to the number of zeros, you know the probability is exactly fifty percent. If you find even one short group, you know the probability is higher. This clarity allows mathematicians to move forward with a solid foundation, knowing that the bias toward an increasing count of ones is a fundamental property of almost all numbers, with only a very specific, well-defined set of exceptions.

Technical Summary: The Equality Cases of the Median Property for the Deconvolved Sum-of-Digits Measures

Problem Statement
This paper addresses the "saturation problem" regarding the measures $P_t$ associated with the binary sum-of-digits function $s(n)$ . Let $s(n)$ denote the number of ones in the binary expansion of an integer $n$ . The asymptotic densities of the level sets of the difference $s(n+t) - s(n)$ define a probability measure $\mu_t$ on $\mathbb{Z}$ . These measures satisfy the recurrence $\mu_t = \mu_1 * P_t$ , where $P_t$ is a family of finitely supported measures.

The central problem is to characterize the set of odd integers $t$ for which the median property holds with equality, specifically where $P_t(\mathbb{N}) = 1/2$ . While Cusick's conjecture posits that $\mu_t(\mathbb{N}) > 1/2$ for all $t \in \mathbb{N}$ , and recent work by Cheng (2026) established that $P_t(\mathbb{N}) \geq 1/2$ with a strict lower bound for words starting with 0, the exact conditions under which equality $P_t(\mathbb{N}) = 1/2$ occurs remained an open problem. Previous analyses were numerical or relied on finite case checks without a general combinatorial characterization.

Methodology
The paper employs a combinatorial framework linking the measures $P_t$ to stopped random walks on recursively grown binary trees $T_t$ .

Tree Representation: The family $P_t$ is identified with the probability distribution of a simple random walk stopped at the first exit time from the internal nodes of a tree $T_w$ (where $w$ is the binary word associated with $t$ ).
Subword Order: Utilizing the combinatorial description of these trees provided by Cheng (2026), the internal nodes of $T_w$ are identified with the set of scattered subwords of the reversed word $\overleftarrow{w}$ . The stopping time $\tau_w$ corresponds to the first time the random walk path ceases to be a subword of $\overleftarrow{w}$ .
Mass Analysis: The probability $P_w(\mathbb{N})$ is expressed as a sum involving the counts of specific subwords. Specifically, the deviation from $1/2$ is governed by the quantity $\Delta^-_m(w) = 2|B^{-1}_{2m-1}(w)| - |B^0_{2m}(w)|$ , where $B^x_n(w)$ denotes the set of subwords of $w$ of length $n$ and balance $x$ .
Insertion Logic: The paper analyzes the condition $\Delta^-_m(w) = 0$ by examining the "deficient" words. It establishes that $P_w(\mathbb{N}) = 1/2$ if and only if for every subword $v \subseteq \overleftarrow{w}$ with $\ell_0(v) = \ell_1(v) + 1$ , inserting a '1' into any slot of $v$ results in a word that is still a subword of $\overleftarrow{w}$ .

Key Contributions and Results
The primary result is a complete characterization of the equality case $P_t(\mathbb{N}) = 1/2$ based on the structure of the binary word $w$ associated with $t = (1w1)_2$ .

Definition of Saturated Words: A word $w$ with $k$ zeros is defined as saturated if, in its block decomposition $w = 1^{a_0}0 1^{a_1}0 \dots 0 1^{a_k}$ , every block of ones satisfies $a_i \geq k$ . Equivalently, every zero is isolated, and every maximal block of ones (including the first and last) has length at least the total number of zeros in the word.
Main Theorem (Theorem 1.2): For an odd integer $t = (1w1)_2$ , the equality $P_t(\mathbb{N}) = 1/2$ holds if and only if $w$ is saturated.
Lower Bound Extension (Corollary 6.3): For non-saturated words $w$ , the paper proves a strict lower bound:
$P_w(\mathbb{N}) \geq \frac{1}{2} + 2^{-2 \min(\ell_0(w), \ell_1(w)+1) - 1}$
This extends a previous bound established by Cheng for words starting with 0 to all non-saturated words.
Enumerative Structure: The paper provides a formula for the number of saturated words of a given length $\ell$ , denoted $E(\ell)$ , and notes that the asymptotic density of the set of integers $t$ satisfying the equality is zero.

Significance
This work resolves the saturation problem left open by Cheng (2026) and provides the exact combinatorial conditions for the equality case of the median property. By linking the equality $P_t(\mathbb{N}) = 1/2$ to the "saturated" property of the underlying binary word, the paper clarifies the structural requirements for the tree asymmetry to vanish. This result is directly relevant to Cusick's conjecture, as it delineates the specific (and sparse) set of parameters where the strict inequality $\mu_t(\mathbb{N}) > 1/2$ might fail to be strict in the deconvolved measure $P_t$ , thereby refining the understanding of the distribution of the sum-of-digits differences. The paper does not propose new applications or future experimental directions but focuses on the complete theoretical solution to the stated open problem.

More like this