A first-exit proof of Cusick's sum-of-digits conjecture

Kaimin Cheng

REVIEW

A first-exit proof of Cusick's sum-of-digits conjecture

Kaimin Cheng

Number Theory · Submitted 22 Jun 2026

Pith's verdict: Cheng claims the first proof of Cusick's conjecture with an explicit bound, but the exactness of the stopped-walk deconvolution is the part that needs checking.

T0 · AI review

How this review was made: An AI referee (grok-4.3) read the paper on June 26, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 2 major objections · 2 minor · Ask about this paper · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2606.23398 (version 2)

Pith IDO57RYCX3, Pith's permanent record of this paper and its review

CitationKaimin Cheng. "A first-exit proof of Cusick's sum-of-digits conjecture." arXiv:2606.23398 (2026). https://pith.science/paper/O57RYCX3

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Cheng has produced what looks like the first proof of Cusick's conjecture. For each fixed t the density c_t is shown to exceed 1/2, and the paper supplies the concrete lower bound 1/2 + 2^{-2 s_2(t)-1}. That quantitative statement is new.

The argument works by replacing the distribution of s_2(n+t) - s_2(n) with the law of a finite stopped random walk through an exact deconvolution, then extracting the bias from first-exit medians on principal subsequence ideals. The method is direct and avoids self-referential definitions or fitted constants, which is a clear strength.

The soft spot is whether the deconvolution really is measure-theoretically exact on natural density. Carry sequences and 2-adic periodicity could in principle leave a small discrepancy that prevents the median positivity from transferring straight to the claimed density. The stress-test note flags exactly this point, and it is the spot that would need the most careful verification in the write-up.

The paper is aimed at number theorists who work on sum-of-digits problems, additive combinatorics, or ergodic questions on the integers. A reader who wants to see how stopped-walk techniques apply to digit biases will get concrete value from the explicit bound and the modeling step.

It deserves a serious referee. The claim settles an open conjecture with a checkable new technique and a sharp quantitative result, so the modeling assumption is worth referee time even if revisions are later required on the exactness details.

Referee report

Major objections (2)

[Proof of the main theorem (deconvolution step)] The abstract asserts that the replacement of the distribution of s_2(n+t)-s_2(n) by the law of a finite stopped random walk is exact (via 'exact deconvolution'). For the claimed density lower bound to follow, this replacement must hold measure-theoretically with respect to natural density, with no o(1) discrepancy arising from carry correlations or 2-adic periodicity across residue classes. The manuscript must supply the explicit verification that the stopping time captures every carry sequence for every residue class of n; without this, the transfer of median positivity to c_t remains unconfirmed.
[First-exit median analysis] The first-exit median argument on principal subsequence ideals is invoked to obtain the strict inequality >1/2. The manuscript should state the precise definition of these ideals and verify that the stopped-walk law on each ideal has positive median independently of the residue class; any dependence on the binary length of t or on periodic boundary effects would affect the explicit constant 2^{-2 s_2(t)-1}.

Simulated authors' rebuttal

read the rebuttal and 2 point-by-point responses

We thank the referee for the careful reading and for highlighting the need for greater explicitness in two key steps of the argument. We address each major comment below and indicate the revisions we will make.

Referee: [Proof of the main theorem (deconvolution step)] The abstract asserts that the replacement of the distribution of s_2(n+t)-s_2(n) by the law of a finite stopped random walk is exact (via 'exact deconvolution'). For the claimed density lower bound to follow, this replacement must hold measure-theoretically with respect to natural density, with no o(1) discrepancy arising from carry correlations or 2-adic periodicity across residue classes. The manuscript must supply the explicit verification that the stopping time captures every carry sequence for every residue class of n; without this, the transfer of median positivity to c_t remains unconfirmed.

Authors: The manuscript already contains the required verification: the stopping time τ is defined in Section 3 so that it coincides exactly with the termination of carry propagation in the addition n+t, for every n. Because the binary digits of t fix a finite set of overlapping positions, the carry sequence is completely determined by the initial segment of the 2-adic expansion of n; the map from n to the stopped-walk path is therefore a bijection on each residue class modulo 2^{v_2(t)+s_2(t)}, preserving natural density with no remainder term. We will add a short paragraph after Theorem 3.2 that spells out this bijection and the absence of o(1) error explicitly. revision: yes
Referee: [First-exit median analysis] The first-exit median argument on principal subsequence ideals is invoked to obtain the strict inequality >1/2. The manuscript should state the precise definition of these ideals and verify that the stopped-walk law on each ideal has positive median independently of the residue class; any dependence on the binary length of t or on periodic boundary effects would affect the explicit constant 2^{-2 s_2(t)-1}.

Authors: Definition 2.4 already introduces the principal subsequence ideals as the sets of integers whose binary expansions avoid the forbidden patterns dictated by the support of t. Proposition 4.3 then shows that the stopped random walk on each such ideal has median at least 2^{-2 s_2(t)-1} > 0, with the lower bound obtained from a uniform comparison of the number of paths that exit positively versus negatively; the argument uses only the Markov property and the fixed asymmetry induced by s_2(t), so it is independent of both the residue class of n and the binary length of t. We will move the definition of the ideals to the beginning of Section 4 and restate the uniformity statement in the proof of the main theorem. revision: partial

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

For any fixed positive integer t the proportion of n where the binary digit sum of n+t meets or exceeds that of n exceeds one half.

The reading

The paper establishes Cusick's conjecture by showing that the natural density c_t of integers n satisfying s_2(n+t) ≥ s_2(n) is always strictly larger than 1/2. It supplies the explicit lower bound c_t ≥ 1/2 + 2^{-2 s_2(t)-1} that depends only on the number of 1-bits in t. A sympathetic reader would care because the result demonstrates a persistent directional bias in the popcount function under translation, even though binary digits behave like independent random bits in the limit. The argument proceeds by replacing the distribution of the difference s_2(n+t) - s_2(n) with an exactly equivalent finite stopped random walk and then verifying a positive first-exit median for the associated principal subsequence ideals.

What carries the argument

exact deconvolution of the difference s_2(n+t) - s_2(n) into the position law of a finite stopped random walk, followed by first-exit medians on principal subsequence ideals

Extended reading notes

Core claim

For every integer t ≥ 1 the limit c_t := lim (1/N) #{0 ≤ n < N : s_2(n+t) ≥ s_2(n)} exists and satisfies c_t > 1/2, in fact c_t ≥ 1/2 + 2^{-2 s_2(t)-1}. The proof is obtained by an exact deconvolution that realizes the law of s_2(n+t) - s_2(n) as that of a finite stopped random walk, after which the required bias follows from the positivity of the first-exit median on the corresponding principal subsequence ideals.

Load-bearing premise

The difference s_2(n+t) - s_2(n) has exactly the same distribution as a finite stopped random walk whose first-exit median is strictly positive.

Editorial extensions

If this is right

The natural density c_t exists and is strictly larger than 1/2 for every t ≥ 1.
The explicit lower bound on c_t depends only on the binary Hamming weight of t.
The inequality s_2(n+t) ≥ s_2(n) holds for a positive-density set of n that is strictly larger than half.
The modeling via stopped random walks yields a uniform bias independent of N.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same stopped-walk first-exit technique may apply directly to sum-of-digits functions in other integer bases.
Numerical verification of the bound for small t could reveal whether equality cases exist when t is a power of two.
The deconvolution step isolates carry propagation, suggesting possible extensions to discrepancy estimates for additive functions.

Original abstract

We prove Cusick's conjecture on the binary sum-of-digits function. More precisely, for every integer $t\ge 1$ we show that \[ c_t:=\lim_{N\to\infty}\frac{1}{N} \#\{0\le n<N:\ s_2(n+t)\ge s_2(n)\}>\frac{1}{2}, \] and in fact obtain the explicit bound \[ c_t\ge \frac{1}{2}+2^{-2s_2(t)-1}, \] where $s_2(m)$ denotes the number of ones in the binary expansion of $m$. The proof is based on an exact deconvolution which replaces the distribution of $s_2(n+t)-s_2(n)$ by a finite stopped random-walk law. The required bias is then proved through first-exit medians for principal subsequence ideals.

References

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Sharp extremal asymptotics for Cusick's sum-of-digits bias at fixed Hamming weight
math.NT 2026-08 accept novelty 8.0 of 10

The minimal Cusick bias among numbers with exactly k ones in binary is asymptotically (1/(2*sqrt(pi))) (log_2 k / k)^(3/2).
The equality cases $P_t(\mathbb{N})=\tfrac12$ for the deconvolved sum-of-digits measures
math.NT 2026-08 conditional novelty 8.0 of 10

For odd t=(1w1)_2, P_t(N)=1/2 exactly when w is saturated: with k zeros, every run of ones in w has length at least k, including words with no zeros.
Proof of the TuDeng Conjecture
math.CO 2026-08 accept novelty 8.0 of 10

The paper proves that for every k≥2 and each nonzero t below 2^k−1, the number of binary pairs with weight sum below k and sum congruent to t modulo 2^k−1 is at most 2^{k−1}.
Deficit bounds and equality cases in the Tu--Deng problem
math.CO 2026-08 conditional novelty 7.0 of 10

The Tu-Deng bound is attained exactly when every gap of zeros in the cyclic binary word contains at least Z-1 ones, resolving Conjecture 3.20 of Flori, Randriambololona, Cohen and Mesnager.

How the literature uses it

5 arXiv papers cite this in 20 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 16 sentences without a confident label

Builds on it 1 paper

Corollary [ref] holds true for a random walk on any binary tree - it is an analogue of Proposition 4.2 from [ref] .

The equality cases $P_t(\mathbb{N})=\tfrac12$ for the deconvolved sum-of-digits measures · Random walk on a tree and the running mass of $ℕ$ · 0.93

Uses its method or tool 1 paper

In the proof, as in [ref] , we count the words with an inserted/deleted digit.

The equality cases $P_t(\mathbb{N})=\tfrac12$ for the deconvolved sum-of-digits measures · Properties of $T_w$, and the formula for $P_w()$. · 1.00

Cites it as background 1 paper

Cheng later proved Cusick's conjecture by a cyclic deletion and first-exit argument [ref] .

Proof of the TuDeng Conjecture · The Tu–Deng conjecture and its history · 0.85

What it cites · 5 sentences without a confident label

Compares with 1 paper

Accordingly, formula [ref] is the $0/1$-notation version of equation (4.10) in Tarłowski [ref] , and the limiting identity [ref] is the corresponding case of his Theorem 21.

On the sum-of-digits measures and Cusick's conjecture via stopped random walks · The finite comb identity · 0.86

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.