I was given the following thing to prove:

$$\lim_{n \to \infty} {d(n) \over n} = 0$$ where $d(n)$ is the number of divisors of n.

I'm so sure how to approach this question. One way I thought of is to use the UFT to turn the expression to:

$$\lim_{n \to \infty} {\prod (x_i + 1) \over \prod p_i^{x_i}}$$

And then to use L'Hôpital's rule for each $x_i$, so I get something like this:

$$\lim_{n \to \infty} {1 \over \ln (\sum p_i) \prod p_i^{x_i}}$$

That equals zero.

  1. Is this a good approach?
  2. Is there a different way to solve this?
  • 3
    $\begingroup$ For some $n$, the divisors can be at most: 1, 2, 3, 4 up to the smallest integer greater than $\sqrt(n)$, along with their correspondants n/1, n/2, etc.., i.e. there is at most $2\sqrt(n)$, and so the limit is bounded by $1/2/\sqrt(n)$ which converge to $0$ $\endgroup$ – Coolwater Feb 2 '16 at 18:46
  • $\begingroup$ following your argument, it seems possible to say that $2^k / \prod_{i=1}^k p_i \to 0$ and $(k+1) / p_i^k \to 0$ when $k \to \infty$ so together with $d(n) \le n$ it should prove that $\prod (x_i+1)/\prod p_i^{x_i} \to 0$ when $\prod p_i^{x_i} \to \infty$ $\endgroup$ – reuns Feb 2 '16 at 19:53
  • $\begingroup$ What is "UFT"?​ $\endgroup$ – Peter Mortensen Feb 2 '16 at 22:19
  • 1
    $\begingroup$ @Peter Mortensen : after some investigation, I think it stands for "unique factorization theorem"' $\endgroup$ – reuns Feb 2 '16 at 22:41

It is actually true that $\lim_{n\to\infty} \frac{d(n)}{n^c}=0$ for any $c>0$, but if you only want it for $c=1$, the simplest proof would be the following. The divisors $\delta\mid n$ can be organized into pairs $(\delta,n/\delta)$, and in every pair the smallest divisor is $\min\{\delta,n/\delta\}\le\sqrt n$. It follows that the number of pairs is at most $\sqrt n$. Thus $d(n)\le 2\sqrt n$ and the assertion follows.

  • 2
    $\begingroup$ In case you are interested, here are two proofs of the fact you state at the beginning of the answer. $\endgroup$ – wythagoras Feb 2 '16 at 18:57
  • 2
    $\begingroup$ This would get down to $c = 1/2 + \epsilon$ as well. $\endgroup$ – Michael Lugo Feb 2 '16 at 19:22

Hint: For every divisior $p$ greater than $\sqrt{n}$ of $n$, there is a divisor $q$ smaller than $\sqrt{n}$ such that $n=pq$. It follows that we can divide the divisiors in pairs where one of the elements is smaller than $\sqrt{n}$, and hence $d(n) \leq 2\sqrt{n}$. Can you use this to evaluate the limit?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.