The Tu–Deng Conjecture is concerned with the sum of digits $w(n)$ of $n$ in base $2$ (the Hamming weight of the binary expansion of $n$) and states the following: assume that $k$ is a positive integer and$1\leqslant t<2^k-1$. Then\[\Bigl \lvert\Bigl\{(a,b)\in\bigl\{0,\ldots,2^k-2\bigr\}^2:a+b\equiv t\bmod 2^k-1, w(a)+w(b)<k\Bigr\}\Bigr \rvert\leqslant 2^{k-1}.\]We prove that the Tu–Deng Conjecture holds almost surely in the following sense: the proportion of $t\in[1,2^k-2]$ such that the above inequality holds approaches $1$ as $k\rightarrow\infty$.Moreover, we prove that the Tu–Deng Conjecture implies a conjecture due to T. W. Cusick concerning the sum of digits of $n$ and $n+t$.
@article{10_37236_7178,
author = {Lukas Spiegelhofer and Michael Wallner},
title = {The {Tu-Deng} conjecture holds almost surely},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {1},
doi = {10.37236/7178},
zbl = {1439.11030},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7178/}
}
TY - JOUR
AU - Lukas Spiegelhofer
AU - Michael Wallner
TI - The Tu-Deng conjecture holds almost surely
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/7178/
DO - 10.37236/7178
ID - 10_37236_7178
ER -
%0 Journal Article
%A Lukas Spiegelhofer
%A Michael Wallner
%T The Tu-Deng conjecture holds almost surely
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/7178/
%R 10.37236/7178
%F 10_37236_7178
Lukas Spiegelhofer; Michael Wallner. The Tu-Deng conjecture holds almost surely. The electronic journal of combinatorics, Tome 26 (2019) no. 1. doi: 10.37236/7178
