Tag Archive

You are currently browsing the tag archive for the ‘elementary numnber theory’ tag.

The divisor bound

23 September, 2008 in expository, math.NT | Tags: , , | by | 39 comments

Given a positive integer n, let d(n) 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

n = p_1^{a_1} \ldots p_k^{a_k} (1)

then (by the fundamental theorem of arithmetic)

d(n) = (a_1+1) \ldots (a_k+1). (2)

Clearly, d(n) \leq n.  The divisor bound asserts that, as n gets large, one can improve this trivial bound to

d(n) \leq C_\varepsilon n^\varepsilon (3)

for any \varepsilon > 0, where C_\varepsilon depends only on \varepsilon; equivalently, in asymptotic notation one has d(n) = n^{o(1)}.  In fact one has a more precise bound

\displaystyle d(n) \leq n^{O( 1/ \log \log n)} = \exp( O( \frac{\log n}{\log \log n} ) ). (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 \log n on the average, as can be seen easily from the double counting identity

\sum_{n \leq N} d(n) = \# \{ (m,l) \in {\Bbb N} \times {\Bbb N}: ml \leq N \} = \sum_{m=1}^N \lfloor \frac{N}{m}\rfloor \sim N \log N,

or from the heuristic that a randomly chosen number m less than n has a probability about 1/m of dividing n, and \sum_{m<n} \frac{1}{m} \sim \log n.  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.]

Read the rest of this entry »

Archives