22 1. Arithmetic Functions
Proposition 1.15. log(d(n)) has maximal order log(2) log(n)/ log log(n).
Proof. Write the prime factorization of an arbitrary positive integer n in
logarithmic form
log(n) = α1 log(p1) + · · · + αr log(pr).
The inequality αk log(2) ≤ αk log(pk) ≤ log(n) is an immediate consequence,
so αk ≤ log(n)/ log(2). Furthermore
log(d(n)) = log(α1 + 1) + · · · + log(αr + 1),
and the inequality log(αk + 1) ≤ αk log(2) also holds. Apply the first in-
equality when log(pk) is comparatively small, and the second inequality
otherwise. Suppose log(pk) ≤ c precisely when 1 ≤ k ≤ m, where c is a
parameter. Then
log(d(n)) =
m
k=1
log(αk + 1) +
r
k=m+1
log(αk + 1)
≤
ec
log
log(n)
log(2)
+ 1 +
r
k=m+1
αk log(2)
≤
ec
log
log(n)
log(2)
+ 1 +
log(2)
c
r
k=m+1
αk log(pk)
≤
ec
log
log(n)
log(2)
+ 1 +
log(2) log(n)
c
since m ≤ exp(c). Now choose c = (1 − δ) log log(n) with 0 δ 1. Now
log(d(n)) ≤
log1−δ(n)
log
log(n)
log(2)
+ 1 + (1 −
δ)−1
log(2) log(n)
log log(n)
.
Since δ may be chosen arbitrarily close to 0, for every ε 0 there is some
n(ε) so that log(d(n)) (1 + ε) log(2) log(n)/ log log(n) for n ≥ n(ε).
Let p be any prime so large that ϑ(p) ≥ p/e and let n = 2·3···p be the
product of all the primes up to and including p. Then
log(d(n))
log(2) log(n)
log log(n)
=
π(p) log(2)
log(2)ϑ(p)
log(ϑ(p))
≥
π(p) log(2)
log(2)π(p) log(p)
log(ϑ(p))
=
log(ϑ(p))
log(p)
≥
log(p/e)
log(p)
= 1 −
1
log(p)
.
But p can be taken arbitrarily large.
The above result immediately yields the weaker bound d(n)
ε
nε,
valid
for any ε 0. This bound is usually more convenient in applications.
