The divisor bound

Given a positive integer , let denote the number of divisors of n (including 1 and n), thus for instance d(6)=4, and more generally, if n has a prime factorisation

(1)

then (by the fundamental theorem of arithmetic)

. (2)

Clearly, .  The divisor bound asserts that, as gets large, one can improve this trivial bound to

(3)

for any , where depends only on ; equivalently, in asymptotic notation one has .  In fact one has a more precise bound

. (4)

The divisor bound is useful in many applications in number theory, harmonic analysis, and even PDE (on periodic domains); it asserts that for any large number n, only a “logarithmically small” set of numbers less than n will actually divide n exactly, even in the worst-case scenario when n is smooth.  (The average value of d(n) is much smaller, being about on the average, as can be seen easily from the double counting identity

,

or from the heuristic that a randomly chosen number m less than n has a probability about 1/m of dividing n, and .  However, (4) is the correct “worst case” bound, as I discuss below.)

The divisor bound is elementary to prove (and not particularly difficult), and I was asked about it recently, so I thought I would provide the proof here, as it serves as a case study in how to establish worst-case estimates in elementary multiplicative number theory.

[Update, Sep 24: some applications added.]