You are currently browsing the tag archive for the ‘elementary numnber theory’ tag.
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.]
Recent Comments