The rth Moment of the Divisor Function: An Elementary Approach

Florian Luca School of Mathematics

University of the Witwatersrand

Private Bag 3, Wits 2050 Johannesburg South Africa

and

Max Planck Institute for Mathematics Vivatsgasse 7 53111 Bonn Germany

and

Department of Mathematics Faculty of Sciences University of Ostrava

30 dubna 22 701 03 Ostrava 1 Czech Republic

florian.luca@wits.ac.za

László Tóth Department of Mathematics

University of Pécs Ifjúság útja 6 H-7624 Pécs Hungary

ltoth@gamma.ttk.pte.hu

Abstract

For integer r ≥ 1 we give an elementary proof for the main term of the asymptotic behavior of the rth moment of the number of divisors of n for positive integers n ≤ x.

1 Introduction

Let τ(n) be the number of divisors of n. Ramanujan [2] stated without proof that, given any real number ε > 0, the estimate

∑_{n≤x} τ(n)^{2} = x(A(log x)^{3} + B(log x)^{2} + C log x + D) + O(x^{3/5+ε})

holds with A = π^{−2}. An elementary proof of the asymptotic formula

∑_{n≤x} τ(n)^{2} ∼ Ax(log x)^{3},

as x → ∞, appears in several places (see, for example, [1, Thm. 7.8]). Wilson [3] proved Ramanujan’s claim and generalized it by showing that for any integer r ≥ 2 one has

∑_{n≤x} τ(n)^{r} = x(C_{r,1}(log x)^{2^{r}−1} + C_{r,2}(log x)^{2^{r}−2} + ⋯ + C_{r,2^{r}}) + O(x^{\frac{2^{r}−1}{2^{r}+2} +ε}).

Note that when r = 2, Wilson’s error term is better than the one claimed by Ramanujan. We are not aware even of elementary proofs for the asymptotic formula

∑_{n≤x} τ(n)^{r} ∼ C_{r}x(log x)^{2^{r}−1}

as x → ∞ for any r ≥ 2. In this note, we give an elementary proof of the following more general result.

Theorem 1. Let k be a positive integer and f(n) be a multiplicative function which on prime powers p^{α} satisfies

f(p) = k and f(p^{α}) = α^{O(1)} for all primes p and integers α ≥ 2,

where the constant implied by the above O is uniform in p. Then

∑_{n≤x} f(n) = xC_{f}(log x)^{k−1} + O(x(log x)^{k−2})

where

C_{f} = \frac{1}{(k − 1)!} (∏_{p≥2} (1 − \frac{1}{p})^{k} (∑_{α≥0} \frac{f(p^{α})}{p^{α}})) .

In the case f(n) = τ(n)^{r} for integer r ≥ 1, Theorem 1 applies with k = 2^{r}.

The only facts that we use are Abel’s summation formula, the Möbius inversion formula, the elementary estimate

∑_{n≤t} \frac{1}{n} = log t + γ + O(1/t)  (1)

valid for all real t ≥ 1, and the fact that the counting function of the squarefull numbers s ≤ t is O(t^{1/2}), where s is squarefull if and only if p^{2} | s for all prime factors p of s, all provable by elementary means.

2 A lemma

Lemma 2. Assume that r is a positive integer and f(n) is some arithmetic function such that

∑_{n≤x} f(n) = ∑_{j=0}^{r} c_{j}(log x)^{j} + O(x^{−1/2+o(1)}),  (2)

for some constants c_{j}, j = 0, …, r. Then

∑_{n≤x} f(n)(log(x/n))^{k} = ∑_{ℓ=0}^{k+r} C_{ℓ}(log x)^{ℓ} + O(x^{−1/2+o(1)}),  (3)

holds for all positive integers k with some constants C_{0}, …, C_{k+r}. Here, if ℓ ∈ {k, k + 1, …, k + r}, then

C_{ℓ} := c_{ℓ−k} (1 + (ℓ − k) ∑_{i=1}^{k} \frac{(−1)^{i}}{ℓ − k + i}\binom{k}{i}) .  (4)

Furthermore, if r ≥ t ≥ 1 are positive integers and

∑_{n≤x} f(n) = ∑_{j=t}^{r} c_{j}(log x)^{j} + O((log x)^{t−1}),  (5)

then

∑_{n≤x} f(n)(log(x/n))^{k} = ∑_{j=k+t}^{k+r} C_{j}(log x)^{j} + O((log x)^{t+k−1}).  (6)

Proof. We show how to deduce (3) out of (2) with the leading coefficients given by (4). Let

A(x) = ∑_{n≤x} f(n).

Then

A(x) = ∑_{j=0}^{r} c_{j}(log x)^{j} + R(x),

where |R(x)| = x^{−1/2+o(1)} as x → ∞. Let i ≥ 1. Put

B_{i}(x) := ∑_{n≤x} f(n)(log n)^{i}.

Then, by the Abel summation formula and by interchanging the order between the summation and the integration, we get

B_{i}(x) = A(x)(log x)^{i} − i ∫_{1}^{x} A(t) (\frac{(log t)^{i−1}}{t} ) dt
= ∑_{j=0}^{r} (c_{j}(log x)^{j+i} − i ∫_{1}^{x} (\frac{c_{j}(log t)^{j+i−1}}{t} ) dt)

− i ∫_{1}^{x} \frac{(log t)^{i−1}R(t)}{t}dt + R(x)(log x)^{i}
= ∑_{j=0}^{r} (c_{j}(log x)^{j+i} − \frac{c_{j}i}{j + i}(log t)^{j+i}|_{1}^{x}) +

− i ∫_{1}^{∞} \frac{(log t)^{i−1}R(t)}{t}dt + i ∫_{x}^{∞} \frac{(log t)^{i−1}R(t)}{t}dt + R(x)(log x)^{i}
= ∑_{j=0}^{r} \frac{c_{j}j}{j + i}(log x)^{j+i} + D_{i} + O(x^{−1/2+o(1)}),

where

D_{i} := −i ∫_{1}^{∞} \frac{(log t)^{i−1}R(t)}{t}dt

In the above, we used the fact that |R(t)| ≤ t^{−1/2+o(1)} as t → ∞ to deduce that the above integral converges and that its tail from x to infinity as well as the other errors are O(x^{−1/2+o(1)}) as x → ∞. Using the binomial formula and the above arguments, we have

C_{k}(x) := ∑_{n≤x} f(n)(log(x/n))^{k}

= ∑_{i=0}^{k}(−1)^{i}\binom{k}{i}(log x)^{k−i} ∑_{n≤x} f(n)(log n)^{i}

= ∑_{n≤x} f(n) + ∑_{i=1}^{k}(−1)^{i}\binom{k}{i}(log x)^{k−i}B_{i}(x)

= ∑_{ℓ=0}^{k+r} C_{ℓ}(log x)^{ℓ} + O(x^{−1/2+o(1)}),

where C_{ℓ} are given by formula (4) for ℓ ≥ k. For ℓ = 1, …, k − 1, the coefficient C_{ℓ} involves the expression D_{ℓ}. The deduction of (6) out of (5) is immediate by similar arguments.

3 The proof of Theorem 1

Let f_{0}(n) := f(n). Recursively define f_{j}(n) such that

f_{j−1}(n) = ∑_{d|n} f_{j}(d), j = 1, 2, ….

By Möbius inversion,

f_{j}(n) = ∑_{d|n} μ(d)f_{j−1}(n/d).

On primes

f_{j}(p) = f_{j−1}(p) − 1, j = 1, 2, ….

Since f_{0}(p) = k, we get that f_{j}(p) = k − j. In particular, f_{k}(p) = 0. Further, for α ≥ 2, we have that

f_{j}(p^{α}) = f_{j−1}(p^{α}) − f_{j−1}(p^{α−1}).

Since f_{0}(p^{α}) = α^{O(1)} it follows that f_{j}(p^{α}) = α^{O(1)} for all j ≥ 2. The constant in O(1) might depend on j. Further,

∑_{α≥0} \frac{f_{j}(p^{α})}{p^{α}} = (1 − \frac{1}{p}) ∑_{α≥0} \frac{f_{j−1}(p^{α})}{p^{α}}, j = 1, 2, …,

therefore

∑_{α≥0} \frac{f_{j}(p^{α})}{p^{α}} = (1 − \frac{1}{p})^{j} ∑_{α≥0} \frac{f(p^{α})}{p^{α}}, j = 0, 1, …

Put

E_{j} := ∏_{p≥2} (∑_{α≥0} \frac{f_{j}(p^{α})}{p^{α}}) = ∏_{p≥2} ((1 − \frac{1}{p})^{j} ∑_{α≥0} \frac{f(p^{α})}{p^{α}}) .

Fix j ≥ 1. Then

F_{j−1}(x) := ∑_{n≤x} \frac{f_{j−1}(n)}{n} = ∑_{n≤x} \frac{1}{n} ∑_{d|n} f_{j}(d) = ∑_{d≤x} f_{j}(d) ∑_{\begin{matrix}n≤x \\ d|n \end{matrix}} \frac{1}{n}.

In the inner sum, we write an n ≤ x which is a multiple of d as n = dm for some integer m ≤ x. We get

F_{j−1}(x) = ∑_{d≤x} \frac{f_{j}(d)}{d} ∑_{m≤x/d} \frac{1}{m} = ∑_{d≤x} \frac{f_{j}(d)}{d} (log(x/d) + γ + O(d/x))

= ∑_{d≤x} \frac{f_{j}(d)}{d} log(x/d) + γ ∑_{d≤x} \frac{f_{j}(d)}{d} + O (\frac{1}{x} ∑_{d≤x} |f_{j}(d)|)  (7)

for j = 1, 2, . . .. When j = k, since f_{k}(p) = 0, it follows that f_{k}(d) = 0 if d is not squarefull. Thus, when j = k in the right–hand side of (7), we have

∑_{d≤x} \frac{f_{k}(d)}{d} log(x/d) + γ ∑_{d≤x} \frac{f_{k}(d)}{d} + O (\frac{1}{x} ∑_{d≤x} |f_{k}(d)|) .

Note that

∑_{d≤x} \frac{f_{k}(d)}{d} = ∑_{d≥1} \frac{f_{k}(d)}{d} + O (∑_{d>x} \frac{|f_{k}(d)|}{d}) = E_{k} + O ( ∑_{d≥x ; d squarefull} \frac{1}{d^{1+o(1)}} )

= E_{k} + O(x^{−1/2+o(1)}),  (8)

where for the error term we used the fact that |f_{k}(d)| = |τ(d)|^{O(1)} = d^{o(1)} as d → ∞ and the Abel summation formula to conclude that

∑_{d>x ; d squarefull} \frac{1}{d^{1+o(1)}} ≤ x^{−1/2+o(1)} as x → ∞.

Further, we have

∑_{d≤x} \frac{f_{k}(d)}{d}(− log d + γ) = ∑_{d≥1} \frac{f_{k}(d)(− log d + γ)}{d} + O ( ∑_{d>x ; d squarefull} \frac{|f_{k}(d)| log d}{d})

:= F_{k} + O(x^{−1/2+o(1)})  (9)

as x → ∞, by a similar argument since |f_{k}(d)| log d ≤ d^{o(1)} as d → ∞. Finally

∑_{d≤x} |f_{k}(d)| ≤ x^{1/2+o(1)},  (10)

again since f_{k}(d) = 0 if d is not squarefull. Collecting (8), (9) and (10) and putting them into (7) with j = k, we get

F_{k−1}(x) = ∑_{n≤x} \frac{f_{k−1}(n)}{n} = E_{k} log x + F_{k} + O(x^{−1/2+o(1)}).

In a similar way,

G_{k−1}(x) := ∑_{n≤x} \frac{|f_{k−1}(n)|}{n} = E′_{k} log x + F′_{k} + O(x^{−1/2+o(1)}).

for some (maybe different) constants E′_{k} and F′_{k}. We now apply Lemma 2 in order to find recursively F_{k−2}(x), F_{k−3}(x), …, F_{0}(x). We claim, by induction on j, that

F_{k−j}(x) = A_{j}(log x)^{j} + B_{j}(log x)^{j−1} + O((log x)^{j−2})  (11)

for j = 2, …, k. At j = 1, this is so with A_{1} = E_{k}, B_{1} = F_{k} and the error term is better, namely O(x^{−1/2+o(1)}). In order to realize the induction step from j = 1 to j = 2, we use the first part of Lemma 1 with r = 1, whereas for the induction step from j ≥ 2 to j + 1 we use the second part of Lemma 2 with r = j and t = j − 1. Assuming that (11) holds for j ≥ 1, we have, by (7),

F_{k−j−1}(x) = ∑_{d≤x} \frac{f_{k−j−1}(d)}{d} = ∑_{d≤x} \frac{f_{k−j}(d)}{d} log(x/d) + γ ∑_{d≤x} \frac{f_{k−j}(d)}{d}

+ O (\frac{1}{x} ∑_{d≤x} |f_{k−j}(d)|) .

By Lemma 2, we get that the right hand side is

\frac{A_{j}}{j + 1}(log x)^{j+1} + (\frac{B_{j}}{j} + γA_{j}) (log x)^{j}

+ O ((log x)^{j−1} + \frac{1}{x} ∑_{d≤x} |f_{k−j}(d)|)

:= A_{j+1}(log x)^{j+1} + B_{j+1}(log x)^{j} + O ((log x)^{j−1} + \frac{1}{x} ∑_{d≤x} |f_{k−j}(d)|) ,

where

A_{j+1} = \frac{A_{j}}{j + 1}, and B_{j+1} = γA_{j} + \frac{B_{j}}{j} .

Thus, we note that A_{j} = E_{k}/j!. It remains to deal with the sum in the error term. But the exact same approach applies to |f_{k−j}(n)|. That is g_{0}(n) = |f_{k−j}(n)| satisfies the same conditions as our initial f_{0}(n) with k replaced by k − j. Thus,

∑_{d≤x} \frac{|f_{k−j}(d)|}{d} = C_{j}(log x)^{j} + D_{j}(log x)^{j−1} + O((log x)^{j−2}),

where for j = 1, the error term is O(x^{−1/2+o(1)}) as x → ∞. By Abel summation, we get that

∑_{d≤x} |f_{k−j}(d)| = x(C_{j}(log x)^{j} + D_{j}(log x)^{j−1} + O((log x)^{j−2}))

− ∫_{1}^{x}(C_{j}(log t)^{j} + D_{j}(log t)^{j−1} + O((log t)^{j−2}))dt
= O(x(log x)^{j−1}),

which is sufficient for us. This completes the induction procedure and shows that at j = k we have

∑_{n≤x} \frac{f(n)}{n} = \frac{1}{k!}E_{k}(log x)^{k} + B_{k}(log x)^{k−1} + O((log x)^{k−2}).

Abel summation formula once again gives

∑_{n≤x} f(n) = (\frac{E_{k}}{k!} (log x)^{k} + B_{k}(log x)^{k−1} + O((log x)^{k−2})) x

− ∫_{1}^{x} (\frac{E_{k}}{k!} (log t)^{k} + B_{k}(log t)^{k−1} + O((log t)^{k−2})) dt
= \frac{E_{k}}{(k − 1)!}x(log x)^{k−1} + O(x(log x)^{k−2}),

which is what we wanted.

4 Acknowledgments

We thank the referee for a careful reading of the manuscript. This work was done when both authors visited the Max Planck Institute of Mathematics in Bonn, Germany in February 2017. They thank the Institution for the invitation and support.

References

[1] M. B. Nathanson, Elementary Methods in Number Theory, Graduate Texts in Mathematics, Vol. 195, Springer-Verlag, 2000.

[2] S. Ramanujan, Some formulæ in the analytic theory of numbers, Messenger of Math. 45 (1915), 81–84.

[3] B. M. Wilson, Proofs of some formulae enunciated by Ramanujan, Proc. London Math. Soc. 21 (1922), 235–255.

2010 Mathematics Subject Classification: Primary 11A35; Secondary 11N37. Keywords: number of divisors, Möbius inversion.

(Concerned with sequence \underline{A000005}.)

Received March 20 2017; revised versions received June 27 2017; June 28 2017. Published in Journal of Integer Sequences, July 2 2017.

Return to Journal of Integer Sequences home page.