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.