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.
Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2014 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.
