# Number TheoryProve: lim nu(n)/n = 0

#### Alexmahone

##### Active member
Let $\nu(n)$ be the number of prime factors of the integer $n$. For example, $\nu(8)=3$, $\nu(5)=1$. Prove: $\lim\ \nu(n)/n=0$.

#### Also sprach Zarathustra

##### Member
Let $\nu(n)$ be the number of prime factors of the integer $n$. For example, $\nu(8)=3$, $\nu(5)=1$. Prove: $\lim\ \nu(n)/n=0$.

In math literature we use the symbol $\pi(x)$ for number of prime factors of the integer that less or equal to $x$.

You need to prove that:

$$\lim_{x\to\infty}\frac{\pi{(x)}}{x}=0$$

Proof:

Recall calculus limit definition:

We will show that for all $\varepsilon >0$, there is exist $N$ such that $\frac{\pi(x)}{x}<\varepsilon$ for all $x\geq N$.

Let $n>1$ be a natural number. Bertrand postulate guarantees us existence of prime number $p$ so that $2^{n-1}<p<2^n$. $p$ such that maintains $p\mid (2^n)!$ but $p\nmid (2^{n-1})!$ , hence the binomial coefficient $\binom{2^n}{2^{n-1}}$ divisible by $p$.

From the above we get the following inequalities:

$$2^{2^n}\geq \binom{2^n}{2^{n-1}} \geq \prod _{2^{n-1}<p<2^n}p\geq (2^{n-1})^{\pi(2^n)-\pi(2^{n-1})}$$

We can say conclude that,

$$\pi(2^n)-\pi(2^{n-1})\leq \frac{2^n}{n-1}$$

Now we substitute $n=2k,2k-1,2k-2,...,3$, and summing all the inequalities, we'll get:

$$\pi({2^{2k}})-\pi({2^2})\leq \sum ^{2k}_{r=3}\frac{2^r}{r-1}$$

It's clear that, $\pi{2^2}<2^2$, hence:

$$\pi({2^{2k}})<\sum ^{2k}_{r=2}\frac{2^r}{r-1}=\sum ^{k}_{r=2}\frac{2^r}{r-1}+\sum ^{2k}_{r=k+1}\frac{2^r}{r-1}<\sum ^{k}_{r=2}{2^r}+\sum ^{2k}_{r=k+1}\frac{2^r}{k}<2^{k+1}+\frac{2^{2k+1}}{k}$$

$k<2^k$ for all $k\geq 2$ and, $2^{k+1}<\frac{2^{2k+1}}{k}$, so:

$$\pi({2^{2k}})<2(\frac{2^{2k+1}}{k})=4(\frac{2^{2k}}{k})$$

or:

$$\frac{2^{2k}}{2^{2k}}<\frac{4}{k}$$

For all real number $x>4$ , there is exist unique natural number $k$ such that:

$$2^{2k-2}<x\leq 2^{2k}$$

From last inequality we can deduce:

$$\frac{\pi(x)}{x}\leq \frac{\pi(2^{2k})}{x}<\frac{\pi(2^{2k})}{2^{2k-2}}=4(\frac{\pi({2^{2k}})}{2^{2k}})<\frac{16}{k}$$

Now, let $\varepsilon >0$, and we choose $N=2^{2[\frac{16}{\varepsilon }]+1}$. If $x\geq N$ then $k\geq [\frac{16}{\varepsilon }]+1$, and:

$$\frac{\pi(x)}{x}<\frac{16}{[\frac{16}{\varepsilon }]+1}<\varepsilon$$

Q.E.D

The proof is from David M. Burton, Elementary Number Theory, page 419, Hebrew edition.

Last edited:

#### Alexmahone

##### Active member
There's actually a neat way of doing this:

Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}$

Then $\nu(n)=\alpha_1+\alpha_2+\ldots+\alpha_k$

$n\ge 2^{\alpha_1}2^{\alpha_2}\ldots 2^{\alpha_k}=2^{\alpha_1+\alpha_2+\ldots+\alpha_k}=2^{\nu(n)}$

$\log_2 n\ge\nu(n)$

$0\le\frac{\nu(n)}{n}\le\frac{\log_2 n}{n}$

Using the squeeze theorem, we see that $\lim \frac{\nu(n)}{n}=0$.