Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?
share|cite|improve this question
3  
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$ – Coolwater Feb 2 at 18:46
    
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$ – user1952009 Feb 2 at 19:53
    
What is "UFT"?​ – Peter Mortensen Feb 2 at 22:19
1  
@Peter Mortensen : after some investigation, I think it stands for "unique factorization theorem"' – user1952009 Feb 2 at 22:41
up vote 13 down vote accepted

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.

share|cite|improve this answer
2  
In case you are interested, here are two proofs of the fact you state at the beginning of the answer. – wythagoras Feb 2 at 18:57
2  
This would get down to $c = 1/2 + \epsilon$ as well. – Michael Lugo Feb 2 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?

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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