The binary digits of n+t

DOI10.2422/2036-2145.202105_069MaRDI QIDQ6098863zbMATH OpenOpenAlexFDO

Authors Lukas Spiegelhofer, Michael Wallner

Publication date 19 June 2023

Published in ANNALI SCUOLA NORMALE SUPERIORE - CLASSE DI SCIENZE (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.07167

zbMATH Keywords

Cusick conjectureHamming weightsum of binary digitsTu and Deng conjecture

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Combinatorial inequalities (05A20) Radix representation; digital problems (11A63) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71)

Abstract: The binary sum-of-digits function $s$ counts the number of ones in the binary expansion of a nonnegative integer. For any nonnegative integer $t$, T.~W.~Cusick defined the asymptotic density $c_t$ of integers $ngeq0$ such that [s(n+t)geq s(n).] In 2011, he conjectured that $c_t>1/2$ for all $t$ -- the binary sum of digits should, more often than not, weakly increase when a constant is added. In this paper, we prove that there exists an explicit constant $M_0$ such that indeed $c_t>1/2$ if the binary expansion of $t$ contains at least $M_0$ maximal blocks of contiguous ones, leaving open only the "initial cases" -- few maximal blocks of ones -- of this conjecture. Moreover, we sharpen a result by Emme and Hubert (2019), proving that the difference $s(n+t)-s(n)$ behaves according to a Gaussian distribution, up to an error tending to $0$ as the number of maximal blocks of ones in the binary expansion of $t$ grows.

Recommendations

• A lower bound for Cusick’s conjecture on the digits of n + t
• Approaching Cusick's conjecture on the sum-of-digits function
• On the distribution of the sum of digits of sums \(a+b\)
• On a conjecture of Cusick concerning the sum of digits of n and n+t
• The sum-of-digits function on arithmetic progressions

Cites work

• A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity
• A lower bound for Cusick’s conjecture on the digits of n + t
• Approaching Cusick's conjecture on the sum-of-digits function
• Automatic Sequences
• Boolean functions optimizing most of the cryptographic criteria
• Central limit theorem for probability measures defined by sum-of-digits function in base 2
• Discrepancy results for the van der Corput sequence
• scientific article; zbMATH DE number 5988004 (Why is no real title available?)
• Indépendance statistique d'ensembles liés à la fonction "somme des chiffres"
• On a combinatorial conjecture
• On a combinatorial conjecture of Tu and Deng
• On a Conjecture about Binary Strings Distribution
• On a conjecture of Cusick concerning the sum of digits of n and n+t
• On the asymptotic behavior of density of sets defined by sum-of-digits function in base 2
• Precise distribution properties of the van der Corput sequence and related sequences
• Sendov's conjecture for sufficiently-high-degree polynomials
• The ring of k-regular sequences
• The ring of \(k\)-regular sequences. II.
• The Tu-Deng conjecture holds almost surely

Cited in

(9)

• The sum-of-digits function on arithmetic progressions
• On a conjecture of Cusick concerning the sum of digits of n and n+t
• Approaching Cusick's conjecture on the sum-of-digits function
• On the asymptotic behavior of density of sets defined by sum-of-digits function in base 2
• On the variation of the sum of digits in the Zeckendorf representation: an algorithm to compute the distribution and mixing properties
• Collisions of digit sums in bases 2 and 3
• Decomposing the sum-of-digits correlation measure
• Block occurrences in the binary expansion
• Primes as sums of Fibonacci numbers

This page was built for publication: The binary digits of n+t

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6098863)