Distribution of the sum-of-digits function of random integers: a survey (Q462807)

In the present survey, the authors investigate probabilistic properties of the sum-of-digits function. They present four methods attacking the problem as well as an extension to general numeration systems.NEWLINENEWLINEThe authors start with a historical background on the sum-of-digits function and its investigations. They provide several ``formulas'' which were used over time to consider the arithmetic mean of the sum-of-digits function. Then, they consider the variance, higher moments and limit distribution of the sum-of-digits function. Throughout their considerations, they provide several methods attacking these problems. At the end of the first part, they consider the asymptotic distribution of the sum-of-digits function, again describing the different approaches used over time.NEWLINENEWLINEIn the second part, the authors provide new results. Let \(X_n\) denote the number of ones in the binary representation of a random integer, where each of the integers \(\{0,1,\dots,n-1\}\) is chosen with equal probability \(\frac1n\). Then, among other results, they show that NEWLINE\[NEWLINE\sum_{0\leq k \leq\lambda}\left| \mathbb{P}\left(X_n=k\right)-\sum_{0\leq r<m} (-1)^ra_r(n)2^{-\lambda}\Delta^r\binom{\lambda}{k}\right|NEWLINE\]NEWLINE NEWLINE\[NEWLINE=\frac{h_m\left|a_m(n)\right|}{(\log_2n)^{m/2}}+\mathcal{O}\left((\log n)^{-(m+1)/2}\right),NEWLINE\]NEWLINE for \(m=1,2,\dots\), where \(a_r(n)\) are constants, which can be explicitly calculated, and \(\Delta\) is the difference operator.NEWLINENEWLINEThe final part deals with general numeration systems and applications. In particular, the authors apply the methods from the first and second part to Gray codes and general codings satisfying a relation on the numbers of ones in the representation of \(n\) and \(2n\).