Welcome to our community

Be a part of something great, join today!

Number Theory Prove: lim nu(n)/n = 0

Alexmahone

Active member
Jan 26, 2012
268
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$.
 
Jan 31, 2012
54
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
Jan 26, 2012
268
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$.