Analysis of Prime Number Theorem

103 Views Asked by At

Assume that we do not know Prime Number Theorem yet. Then

What is the limit of $\frac{\pi(x)}{x}$ as $x \to \infty$. I feel that is should go to $0$, but I am not sure about that. How should I find that out. May be we should bound it above by some function. How should I proceed with that?

$\pi$ is the prime counting function.

2

There are 2 best solutions below

0
On

Hint: By the elementary Chebyshev estimate we have $$ \frac{c_1}{\log(x)}<\frac{\pi(x)}{x}<\frac{c_2}{\log(x)} $$ for all $x\ge x_0$ and constants $0<c_1<1$, $c_2=\frac{6}{5}c_1$. See here for references.

At this site, the question has been answered here: show that $\lim(\pi(x)/x) = 0$

0
On

Applying the sieve of Eratosthenes to $[1,x]$ sieves out roughly $\frac1p$ of the numbers for each prime $p$. More specifically, as $x\to\infty$, the proportion of numbers sieved out in the step for prime $p$ converges to $\frac1p$. (If this is not obvious, you can prove it by applying the Chinese remainder theorem to the product of all primes up to and including $p$.) Thus, the proportion of numbers remaining can be made arbitrarily close to $\prod_{i=1}^n\left(1-\frac1{p_i}\right)$ for arbitrary $n$ (where $p_i$ is the $i$-th prime). But

\begin{eqnarray} \prod_{i=1}^n\left(1-\frac1{p_i}\right) &=& \exp\left(\sum_{i=1}^n\log\left(1-\frac1{p_i}\right)\right) \\ &\le& \exp\left(-\sum_{i=1}^n\frac1{p_i}\right) \\ &\to& 0 \end{eqnarray}

for $n\to\infty$, since the sum of the reciprocals of the primes diverges. Since the primes are a subset of the numbers that remain after $n$ sieving steps, it follows that

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