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.
Previous Page Next Page