pith. sign in

arxiv: 2606.23398 · v1 · pith:O57RYCX3new · submitted 2026-06-22 · 🧮 math.NT · math.CO

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

Kaimin Cheng This is my paper

Pith reviewed 2026-06-26 07:17 UTC · model grok-4.3

classification 🧮 math.NT math.CO
keywords binary sum of digitsCusick conjecturepopcountstopped random walkfirst-exit mediannatural densitybinary expansionsubsequence ideals
0
0 comments X

The pith

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.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

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.

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.

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

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.

Where Pith is reading between the lines

These are 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.

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.

What would settle it

For a concrete t, compute the exact count of n < 2^30 satisfying s_2(n+t) ≥ s_2(n) and check whether the count is at most 2^29.

read the 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims to prove Cusick's conjecture: for every integer t ≥ 1, the natural density c_t := lim (1/N) #{0 ≤ n < N : s_2(n+t) ≥ s_2(n)} satisfies c_t > 1/2, with the explicit lower bound c_t ≥ 1/2 + 2^{-2 s_2(t)-1}. The argument proceeds by an exact deconvolution that replaces the distribution of s_2(n+t) - s_2(n) with the law of a finite stopped random walk, after which the strict bias is obtained from first-exit medians on principal subsequence ideals.

Significance. If the central derivation holds, the result resolves a long-standing conjecture in additive number theory with a fully explicit quantitative bound. The stopped-walk and first-exit-median approach supplies a new structural perspective that may extend to related sum-of-digits problems.

major comments (2)
  1. [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.
  2. [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}.
minor comments (2)
  1. Notation for the stopped random walk (step distribution, stopping time) should be introduced with a dedicated display equation before its use in the deconvolution.
  2. The paper should include a short table or remark comparing the new explicit bound with previously known lower bounds for small t (e.g., t=1,3,7).

Simulated Author's Rebuttal

2 responses · 0 unresolved

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.

read point-by-point responses

  1. 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

  2. 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

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper establishes the lower bound on c_t by first proving an exact measure-theoretic replacement of the distribution of s_2(n+t)-s_2(n) by the law of a finite stopped random walk (via deconvolution on the natural density), then deriving the strict positivity of the first-exit median on principal subsequence ideals. No step reduces by construction to a fitted parameter, self-referential definition of c_t, or load-bearing self-citation; the replacement is asserted as an identity justified within the manuscript rather than smuggled via ansatz or prior work by the same author. The argument therefore remains independent of its target inequality.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof rests on the existence of the limiting density c_t and on the exact equivalence between the digit-sum difference and a stopped random walk; these are domain assumptions rather than derived quantities. No free parameters or invented entities are visible in the abstract.

axioms (2)
  • domain assumption The limiting density c_t exists for every fixed t
    Invoked when the limit is written as the definition of c_t
  • domain assumption The difference s_2(n+t)-s_2(n) admits an exact representation as the position of a finite stopped random walk
    Central modeling step stated in the abstract

pith-pipeline@v0.9.1-grok · 5671 in / 1526 out tokens · 20267 ms · 2026-06-26T07:17:52.536055+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

10 extracted references · 1 linked inside Pith

  1. [1]

    somme des chiffres

    J. B´ esineau, Ind´ ependance statistique d’ensembles li´ es ` a la fonction “somme des chiffres”,Acta Arith.20(1972), no. 4, 401–416

    1972

  2. [2]

    T. W. Cusick, Y. Li and P. St˘ anic˘ a, On a combinatorial conjecture,Integers11(2011), no. 2, 185–203

    2011

  3. [3]

    Drmota, M

    M. Drmota, M. Kauers and L. Spiegelhofer, On a conjecture of Cusick concerning the sum of digits ofnandn+t,SIAM J. Discrete Math.30(2016), no. 2, 621–649

    2016

  4. [4]

    J. F. Morgenbesser and L. Spiegelhofer, A reverse order property of correlation measures of the sum-of-digits function,Integers12(2012), Paper No. A47, 5 pp

    2012

  5. [5]

    Sobolewski and L

    B. Sobolewski and L. Spiegelhofer, Decomposing the sum-of-digits correlation measure,J. Number Theory280(2026), 702–736

    2026

  6. [6]

    Spiegelhofer, A lower bound for Cusick’s conjecture on the digits ofn+t,Math

    L. Spiegelhofer, A lower bound for Cusick’s conjecture on the digits ofn+t,Math. Proc. Cambridge Philos. Soc.172(2022), no. 1, 139–161

    2022

  7. [7]

    Spiegelhofer and M

    L. Spiegelhofer and M. Wallner, The Tu–Deng conjecture holds almost surely,Electron. J. Combin. 26(2019), no. 1, Paper No. P1.28, 28 pp

    2019

  8. [8]

    Spiegelhofer and M

    L. Spiegelhofer and M. Wallner, The binary digits ofn+t,Ann. Sc. Norm. Super. Pisa Cl. Sci. (5)24(2023), no. 1, 1–31

    2023

  9. [9]

    Tar lowski, On the sum-of-digits measures and Cusick’s conjecture via stopped random walks, arXiv:2605.08624v3, 2026

    D. Tar lowski, On the sum-of-digits measures and Cusick’s conjecture via stopped random walks, arXiv:2605.08624v3, 2026

    Pith/arXiv arXiv 2026

  10. [10]

    Tu and Y

    Z. Tu and Y. Deng, A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity,Des. Codes Cryptogr.60(2011), no. 1, 1–14. School of Mathematical Sciences, China West Normal University, Nanchong 637002, P. R. China Email address:ckm20@126.com

    2011