ON THE MOMENTS OF THE SUM-OF-DIGITS FUNCTION

P.J. Grabner^{†}, P. Kirschenhofer, H. Prodinger and R.F. Tichy^{†}

Abstract. We are concerned with the asymptotic description of the higher moments of the sum-of-digits function. For the mean value a completely satisfactory result involving a continuous and no-where differentiable oscillation function is due to Trollope (1968) and H. Delange (1975). The asymptotic behaviour of the second moment of the binary sum-of-digits function was investigated by J. Cocquet (1986) and by P. Kirschenhofer (1990). A somewhat weaker result in the decimal number system is due to R. E. Kennedy and C. N. Cooper (1991). In the present paper we prove similar (more or less explicit) formulas in the case of s-th moments by a generalization of Delange‘s approach. Furthermore we discuss a second method for proving such results: the so-called Mellin-Perron summation formula.

1. Introduction

In a recent paper in the Fibonacci Quarterly R. E. Kennedy and C. N. Cooper [K-C91] dealt with the second moment of the sum-of-digits function in the decimal number system, explicitely stating the question for higher moments as an open problem. We consider this question in the sequel.

Let ν(n) represent the total number of 1-digits in the binary representation of the integer n. It is not hard to see that

(1.1)  M_{1}(N) = ∑_{n<N} ν(n) = \frac{1}{2}N log_{2} N + o(N log N),

since asymptotically the binary representations contain roughly as many 0’s as 1’s. The Trollope–Delange formula is more surprising: It expresses S(n) in an exact formula (cf. [Tr68], [De75])

(1.2)  M_{1}(n) = \frac{1}{2}N log_{2} N + Nδ_{1}(log_{2} N),

where δ_{1}(u), a ‘fractal function’, is a continuous, periodic, nowhere differentiable function with an explicit Fourier expansion involving the Riemann zeta function.

The argument given by Delange is based on a combinatorial decomposition of binary representations of integers, followed by a computation of the Fourier coefficients of the fractal function. This exact formula was used to analyze register allocation algorithms, or equivalently the order of random ‘channel networks’ (cf.[F-R-V79]). It was later extended to some non-standard digital representations

Typeset by AMS-TEX

† These authors were supported by the Austrian Science Foundation (Project Nr. P8274PHY)

of integers. Cantor representations were considered in [K-T84], and Gray code [F-R80] was studied for the purpose of analyzing sorting networks. In [Ki83] occurrences of blocks of digits in standard q-ary representations, in [K-P84] subblock occurrences in Gray code representation and in [Co83] the subsequence u(3n) of the classical Thue-Morse sequence u(n) were investigated. In a recent paper [G-T91] this result was extended to digit expansions with respect to linear recurrences. As general surveys we refer to Stolarsky’s article [Sto77] and to [K-P-T85]. As an especially important paper in this area we mention Brillhart, Erdős and Morton’s paper [B-E-M83].

The second moment M_{2}(N) was investigated by J. Cocquet [Co86], and independently in [Ki90]. The following exact formula is proved by Delange’s method: (1.3)

M_{2}(N) = ∑_{n<N} ν(n)^{2} = \frac{N}{4} log_{2}^{2} N + N log_{2} N (\frac{1}{4} + δ_{1}(log_{2} N)) + Nδ_{2}(log_{2} N),

where δ_{1}, δ_{2} are continuous nowhere differentiable functions of period 1 and δ_{1} is the function that occurred in (1.2). By the same approach such exact formulæ can be proved for arbitrary q-ary number systems:

(1.4) ∑_{n<N} ν_{q}(n)^{2} = (\frac{q − 1}{2})^{2} N log_{q}^{2} N + N log_{q} Nη_{1}(log_{q} N) + Nη_{2}(log_{q} N),

where η_{1} and η_{2} are continuous nowhere differentiable functions of period 1 and log_{q} denotes the logarithm to base q, as usual. In [K-C91] R.E. Kennedy and C.N. Cooper rediscovered a weaker result for the decimal system:

∑_{n<N} ν_{10}(n)^{2} = 20.25N log_{10} N + o(N log N).

In [Co86] a similar formula is established for higher moments but without proving the continuity of the fluctuations. In Section 2 we use Delange’s approach to compute the third moment in the binary number system, including the proof of the continuity of the fluctuations. The q-ary case can be settled by similar but more elaborate computations. In Section 3 we sketch this approach in the case of higher moments.^{1} In the final Section 4 we present an exposition of a purely analytic approach using Mellin transform. In [F-G-K-P-T92] this approach was applied to establish exact and asymptotical formulæ in various cases of digital sums. By this method we get automatically the mean and the Fourier-coefficients of the periodic functions. In detail we apply this method to the expectation (first moment) of the q-ary sum-of-digits function. In the case of higher moments some analytic problems remain to be solved.

1While finishing the present paper the authors got to know a manuscript due to J.-M. Dumont and A. Thomas where the corresponding result is proved for digital systems generated by substitution automata. This more general result is proved by different and less elementary methods.

2. Delange’s Approach: The Third Moment

In order to compute the third moment M_{3} of the binary sum-of-digits function we introduce the following notation:

f_{j}(t) = ⌊\frac{t}{2^{j}} ⌋ − 2 ⌊\frac{t}{2^{j+1}} ⌋ , g_{j}(t) = f_{j}(t) − \frac{1}{2}.

Thus we have

M_{3}(N) = ∫_{0}^{N} ∑_{(j_{1},j_{2},j_{3})} f_{j_{1}}(t)f_{j_{2}}(t)f_{j_{3}}(t)dt

= ∑_{k=0}^{3} \binom{3}{k}\frac{1}{2^{3−k}} ∫_{0}^{N} ∑_{(j_{1},...,j_{k})} g_{j_{1}}(t) … g_{j_{k}}(t)dt,

where the summation is extended over all k-tuples (j_{1}, …, j_{k}) of non negative integers ≤ L = ⌊log_{2} N⌋. Denoting the integral for k = 3 by I_{3} we obtain

(2.1)  \begin{aligned}M_{3}(N) & = I_{3} + \frac{3}{2}(L + 1)M_{2}(N) − \frac{3}{4}(L + 1)^{2}M_{1}(N) + \frac{N}{8} (L + 1)^{3} \\ & = I_{3} + N(\frac{1}{8}K^{3} + K^{2}(\frac{3}{8} + \frac{3}{4}δ_{1}) + K(\frac{3}{2}δ_{2} + \frac{3}{8}y) \\ & + (\frac{3}{2}yδ_{2} − \frac{3}{4}y^{2}δ_{1} + \frac{1}{8}y^{3})), \end{aligned}

where δ_{1} = δ_{1}(log_{2} N) and δ_{2} = δ_{2}(log_{2} N) are the periodic fluctuations of the first and second moments occurring in (1.2) and (1.3); K = log_{2} N and y = 1−{log_{2} N}. We note that δ_{1}(0) = δ_{1}(1) = δ_{2}(0) = δ_{2}(1) = 0.

Now we compute the remaining integral

I_{3} = ( ∑_{j_{1}=j_{2}=j_{3}} + 3 ∑_{j_{1}=j_{2}≠j_{3}} + 6 ∑_{j_{1}<j_{2}<j_{3}}) ∫_{0}^{N} g_{j_{1}}(t)g_{j_{2}}(t)g_{j_{3}}(t)dt

= \frac{1}{4} ∑_{j} ∫_{0}^{N} g_{j}(t)dt + \frac{3}{4}L ∑_{j} ∫_{0}^{N} g_{j}(t)dt + 6 ∑_{j_{1}<j_{2}<j_{3}} ∫_{0}^{N} g_{j_{1}}(t)g_{j_{2}}(t)g_{j_{3}}(t)dt.

Notice that the first two parts of this equality follow from the fact that g_{j}(t) is piecewise constant and g_{j}(t)^{2} = \frac{1}{4}. For the last summation we obtain

∑_{j_{1}<j_{2}<j_{3}} = ∑_{0≤j_{1}<j_{2}<j_{3}≤L} 2^{j_{3}+1} ∫_{0}^{N} g(2^{j_{3}−j_{1}}u)g(2^{j_{3}−j_{2}}u)g(u)du,

where g(u) = ⌊2u⌋ − 2⌊u⌋ − \frac{1}{2}. Now transform the index of summation as follows: j := j_{3}, d_{1} := j_{3} − j_{1}, d_{2} := j_{3} − j_{2}. Thus we obtain

∑_{0≤j_{1}<j_{2}<j_{3}≤L} = ∑_{j=0}^{L} 2^{j+1} ∑_{1≤d_{1}<d_{2}≤j} ∫0^{\frac{N}{2^{j+1}}} g(2^{d_{1}}u)g(2^{d_{2}}u)g(u)du.

Notice that the inner summation can be extended to infinity without changing the value and set k = L − j. Hence

∑_{0≤j_{1}<j_{2}<j_{3}≤L} = 2^{L+1} ∑_{k≥0} ∑_{1≤d_{1}<d_{2}} ∫_{0}^{2^{k+{log_{2} N}−1}} g(u)g(2^{d_{1}}u)g(2^{d_{2}}u)du

= 2^{1−{log_{2} N}} ∑_{k≥0} 2^{−k}h_{3}(2^{{log_{2} N}−1}2^{k}),

where h_{3} is the periodic function defined by

(2.2)  h_{3}(x) = ∑_{1≤d_{1}<d_{2}} ∫_{0}^{x} g(u)g(2^{d_{1}}u)g(2^{d_{2}}u)du.

We observe that the integrals occurring in (2.2) are integrals over distinct Rademacher functions; hence h_{3}(1) = h_{3}(\frac{1}{2}) = 0. Thus setting

(2.3)  ψ(x) = 2^{1−{x}} ∑_{k≥0} 2^{−k}h_{3}(2^{k}2^{{x}−1})

we obtain a continuous and 1-periodic function with ψ(0) = ψ(1) = 0. Therefore we have

(2.4) I_{3} = N (K(\frac{3}{4}δ_{1} − \frac{3}{8}y) + ( − \frac{1}{2}δ_{1} + \frac{x}{4} + \frac{3}{4}xδ_{1} − \frac{3}{8}x^{2} + 6ψ(1 − y))) .

By combining (2.1) and (2.4) we derive

(2.5)  M_{3}(N) = N (\frac{1}{8}K^{3} + K^{2}(\frac{3}{8} + \frac{3}{4}δ_{1}) + K(\frac{3}{4}δ_{1} + \frac{3}{2}δ_{2}) + δ_{3}) ,

where

(2.6) δ_{3} = δ_{3}(log_{2} N) = \frac{3}{2}yδ_{2} − \frac{3}{4}y^{2}δ_{1} + \frac{1}{8}y^{3} − \frac{1}{2}δ_{1} + \frac{y}{4} + \frac{3}{4}yδ_{1} − \frac{3}{8}y^{2} + 6ψ(1 − y).

Thus we have proved

Theorem 1. The third moment of the binary sum-of-digits function satisfies

\frac{1}{N} ∑_{n<N} ν_{2}(n)^{3} = \frac{1}{8} (log_{2} N)^{3} + (\frac{3}{8} + \frac{3}{4}δ_{1}(log_{2} N)) (log_{2} N)^{2}

+ (\frac{3}{4}δ_{1}(log_{2} N) + \frac{3}{2}δ_{2}(log_{2} N)) log_{2} N + δ_{3}(log_{2} N),

where δ_{3} is a continuous and periodic function with period 1 defined by (2.6).

Remark. Obviously this result can be extended to q-ary representations. However, the computations are much more involved.

3. Delange’s Approach: The General Case

In the following we sketch the computation of the s-th moments M_{s} of the binary sum-of-digits function:

Adopting analogous notations as in the previous section we start from

M_{s}(N) = ∫_{0}^{N} ∑_{(j_{1},...,j_{s})} f_{j_{1}}(t) … f_{j_{s}}(t)dt

= ∑_{k=0}^{s} \binom{s}{k}\frac{1}{2^{s−k}} ∫_{0}^{N} ∑_{(j_{1},...,j_{k})} g_{j_{1}}(t) … g_{j_{k}}(t)dt.

In the following we evaluate the integral I_{k} appearing in the last expression. To this end we observe that g_{j}^{2}(t) ≡ \frac{1}{4}, so that it is meaningful to group together multiple occurences of g’s with the same index j and to distinguish odd and even frequencies since g_{j}^{2n}(t) ≡ \frac{1}{2^{2n}}, while g_{j}^{2n+1}(t) ≡ \frac{1}{2^{2n}} g_{j}(t).

The above described grouping of g’s with the same index induces a set partition of the subindex set {1, …, k}, where we have to count separately the numbers p resp. r of blocks of odd resp. even cardinality. Let us denote by

S(k; p, r)

the number of the above described set partitions. Then we may compute I_{k} as follows: (We use the abbreviation (x)_{k} = x(x − 1) … (x − k + 1).)

(3.1) I_{k} = ∑_{p,r} \frac{p!}{2^{k−p}} S(k; p, r)(L + 1 − p)_{r} ∫_{0}^{N} ∑_{0≤i_{1}<···<i_{p}≤L} g_{i_{1}}(t) … g_{i_{p}}(t)dt

(Observe that for given index values i_{1}, …, i_{p} belonging to the p blocks of odd cardinality, there are (L+1−p)_{r} possibilities to choose the r index values belonging to the blocks of even cardinality differently from i_{1}, …, i_{p}.)

The sums

Σ_{p}(N) = ∑_{0≤i_{1}<···<i_{p}≤L} ∫_{0}^{N} g_{i_{1}}(t) … g_{i_{p}}(t)dt

can be treated in exactly the same manner as in Section 2 for the instance p = 3 and yield

\frac{1}{N} Σ_{p}(N) = τ_{p}(log_{2} N),

where

τ_{p}(x) = 2^{1−{x}} ∑_{i≥0} 2^{−i}h_{p} (2^{i}2^{−1+{x}})

with

h_{p}(x) = ∑_{1≤i_{1}<i_{2}<···<i_{p−1}} ∫_{0}^{x} g(u)g(u2^{i_{1}}) … g(u2^{i_{p−1}})du.

h_{p}(x) is a continuous function with h_{p}(m) = 0 for all m ∈ ℤ, so that τ_{p}(x) is a periodic function of period 1.

Collecting all contributions and rewriting L = ⌊log_{2} N⌋ as L = log_{2} N −{log_{2} N} we obtain Theorem 2. The s-th moment of the binary sum-of-digits function satisfies

\frac{1}{N} ∑_{n<N} ν_{2}(n)^{s} = \frac{1}{2^{s}} (log_{2} N)^{s} + ∑_{i=0}^{s−1} (log_{2} N)^{i} η_{i}(log_{2} N)

where η_{i}(x) are continuous periodic functions of period 1 that can be expressed explicitely as described before.

Remark 1. The numbers S(k; p, r) do not seem to have been studied in the literature. Of course they are related to the classical Stirling numbers of the second kind [Ri58] via

∑_{p+r=j} S(k; p, r) = S(k, j).

The trivariate generating function of the S(k; p, r) is easily obtained via the operator method for combinatorial constructions as described systematically in [F-V90]:

(3.2)  ∑_{p,r,k} S(k; p, r)x^{p}y^{r} \frac{z^{k}}{k!} = exp (x sinh z + y(cosh z − 1)).

We note that related recurrences already occur in [Co86].

Remark 2. From Theorem 2 it is not difficult to compute expressions for the higher centralized moments.

4. Mellin Perron Approach: An Exposition

As announced in the introduction we present an analytic method to compute digital sums. The method makes use of the so called Mellin Perron summation formula:

(4.1)  ∑_{n<N} a_{n} (1 − \frac{n}{N} ) = \frac{1}{2πi} ∫_{c−i∞}^{c+i∞}∑_{n=1}^{∞} \frac{a_{n}}{n^{s}} N^{s} \frac{ds}{s(s + 1)}.

This formula is well known in analytic number theory and can be proved by an application of Mellin transform (cf. [Do50], [Ap84], [FGKPT92]). We demonstrate the use of this method in the case of the expectation of the q-ary sum-of-digits function.

Theorem 3. [Delange] The sum-of-digits function ν_{q}(n) satisfies

S_{q}(N) = ∑_{n<N} ν_{q}(n) = \frac{q − 1}{2}N log_{q} N + Nδ(log_{q} N),

where δ(u) is representable by the Fourier series δ(u) = ∑_{k∈ℤ} δ_{k}e^{2πikx} and

δ_{0} = \frac{q − 1}{2} (log_{q} 2π − \frac{1}{log q} ) − \frac{q + 1}{4}

δ_{k} = −\frac{q − 1}{log q}ζ(χ_{k}) for k ≠ 0,

where χ_{k} = \frac{2kπi}{log q}.

Proof. Let υ_{q}(k) be the largest exponent such that q^{υ_{q}(k)} divides k and ν_{q}(k) be the sum-of-digits function in the q-ary representation. We have ν_{q}(k) − ν_{q}(k − 1) = 1−(q−1)υ_{q}(k), so that S_{q}(N) resembles a double summation of υ_{q}(k). Furthermore it is well-known and easy to see that

(4.1)  ∑_{k≥1} \frac{υ_{q}(k)}{k^{s}} = \frac{ζ(s)}{q^{s} − 1}.

Thus, from (4.1), with a_{k} = 1−(q−1)υ_{q}(k), we get the basic integral representation

(4.2)  S_{q}(n) = \frac{n}{2πi} ∫_{2−i∞}^{2+i∞}\frac{q^{s} − q}{q^{s} − 1}ζ(s)n^{s} \frac{ds}{s(s + 1)}.

The integrand in (4.2) has a double pole at s = 0 and simple poles at s = χ_{k} (note that the pole s = 1 of ζ(s) is cancelled out). Shifting the line of integration to ℜ(s) = −\frac{1}{4} and taking residues into account we get

(4.3)  S(n) = \frac{1}{2}n log_{q} n + nτ_{0}(log_{q} n) − nR(n),

where the remainder term is

(4.4)  R(n) = \frac{1}{2πi} ∫_{− \frac{1}{4} −i∞}^{− \frac{1}{4} +i∞}\frac{q^{s} − q}{q^{s} − 1}n^{s} \frac{ds}{s(s + 1)},

so that there only remains to prove that R(n) ≡ 0 when n is an integer. The integral converges since |ζ(−\frac{1}{4} + it)| ≪ |t|^{\frac{3}{4}} (cf. [W-W27]).

Using the expansion

\frac{q^{s} − q}{q^{s} − 1} = q + (q − 1) (q^{s} + q^{2s} + q^{3s} ⋯)

in (4.4) which is legitimate since now ℜ(s) < 0, we find that R(n) is a sum of terms of the form

\frac{1}{2πi} ∫_{− \frac{1}{4} −i∞}^{− \frac{1}{4} +i∞}ζ(s)(q^{k}n)^{s} \frac{ds}{s(s + 1)},

and each of these terms is 0 by virtue of

\frac{1}{2πi} ∫_{− \frac{1}{4} −i∞}^{− \frac{1}{4} +i∞}ζ(s)n^{s} \frac{ds}{s(s + 1)} = 0,

which is an immediate consequence of the summation formula for arithmetic progressions and (4.1). □

Remark. It is clear from the discussion above that an exact formula for a sum-of-digits function is obtained each time the analytical behaviour of the corresponding Dirichlet generating function is sufficently known. In the case of higher moments of the sum-of-digits function this procedure can be worked out only formally: serious convergence problems occur. In order to overcome these difficulties one would have to know precise bounds for the rate of growth of the analytic continuation of the Dirichlet series

∑_{n=1}^{∞} \frac{ν(n)^{k}}{n^{s}}

along vertical lines.

References

[Ap84] T.M. Apostol, Introduction to Analytic Number Theory, Springer Verlag, Berlin-Heidelberg-New York, 1984.

[B-E-M83] J. Brillhart, P. Erdős and P. Morton, On Sums of Rudin-Shapiro coefficients II,

Pacific J. Math. 107 (1983), 39–69.

[Co83] J. Coquet, A Summation Formula Related to the Binary Digits, Invent. Math. 73 (1983), 107–115.

[Co86] J. Coquet, Power Sums of Digital Sums, J. Number Th. 22 (1986), 161–176.

[De75] H. Delange, Sur la fonction sommatoire de la fonction “Somme des Chiffres”, Enseignement Math.(2) 21 (1975), 31–47.

[Do50] G. Doetsch, Handbuch der Laplace Transformation, Birkhäuser Verlag, Basel, 1950.

[FGKPT92] P. Flajolet, P. Grabner, P. Kirschenhofer, H. Prodinger and R.F. Tichy, Mellin Transform and Asymptotics: Digital Sums, Theor. Comput. Sci. (to appear).

[F-R80] P. Flajolet and L. Ramshaw, A Note on Gray Code and Odd-Even Merge, SIAM J.

Comput. 9 (1980), 142–158.

[F-R-V79] P. Flajolet, J.C. Raoult and J. Vuillemin, The Number of Registers Required for

Evaluating Arithmetic Expressions, Theor. Comput. Sci. 9 (1979), 99–125.

[G-T91] P.J. Grabner and R.F. Tichy, α-Expansions, Linear Recurrences and the Sum-of-

Digits Function, Manuscripta Math. 70 (1991), 311–324.

[F-V90] P.Flajolet and J.Vitter, Average-Case Analysis of Algorithms and Data Structures, Handbook of Theoretical Computer Science Vol. A “Algorithms and Complexity”, North-Holland, 1990, pp. 431–524.

[K-C91] R.E. Kennedy and C.N. Cooper, An Extension of a Theorem by Cheo and Yien

Concerning Digital Sums, Fibonacci Quarterly 29 (1991), 145–149.

[Ki83] P. Kirschenhofer, Subblock Occurrences in the q-ary Representation of n, SIAM J. Alg. Discr. Math. 4 (1983), 231–236.

[Ki90] P. Kirschenhofer, On the Variance of the Sum of Digits Function, Number-Theoretic Analysis, Lecture Notes in Mathematics 1452 (E. Hlawka and R. Tichy, eds.), 1990, pp. 112–116.

[K-P84] P. Kirschenhofer and H. Prodinger, Subblock Occurrences in Positional Number Sys-

tems and Gray Code Representation, J. Inf. Opt. Sci. 5 (1984), 29–42.

[K-P-T85] P. Kirschenhofer, H. Prodinger and R.F. Tichy, Über die Ziffernsumme natürlicher Zahlen und verwandte Probleme, Zahlentheoretische Analysis, Lecture Notes in Mathematics 1114 (E. Hlawka, ed.), 85, pp. 55–65.

[K-T84] P. Kirschenhofer and R.F. Tichy, On the distribution of digits in Cantor represen-

tations of integers, J. Number Th. 18 (1984), 121–134.

[Pr82] H. Prodinger, Generalizing the sum of digits function, SIAM J. Alg. Discr. Math. 3 (1982), 35–42.

[Ri58] J. Riordan, An Introduction to Combinatorial Theory, J. Wiley, New York, 1958.

[Sto77] K.B. Stolarsky, Power and Exponential Sums of Digital Sums Related to Binomial Coefficient Parity, SIAM J. Appl. Math. 32 (1977), 717–730.

[Tr68] H. Trollope, An explicit expression for binary digital sums, Math. Mag. 41 (1968), 21–25.

[W-W27] E.T. Whittaker and G.N. Watson, A Course in Modern Analysis, Cambridge University Press, 1927.

P. Grabner and R. Tichy Institut für Mathematik TU Graz Steyrergasse 30 8010 Graz, Austria P. Kirschenhofer and H. Prodinger Institut für Algebra und Diskrete Mathematik, TU Wien Wiedner Hauptstraße 8–10 1040 Wien, Austria