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

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.  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.]