Chebyshev's estimate for the number of primes

This page is a detailed description of Chebyshev's attempt to prove the prime number theorem, and a bit of the history of the prime number theorem in general.

History

In 1850, Russian mathematician Pafnuty Lvovich Chebyshev made a major breakthrough by showing a statement that supports the prime number theorem. It states:

"Let $\pi (n)$ denote the number of primes that is less than or equal to $n$ .

There exist numbers $c_1$ and $c_2$ such that

$c_1 \frac{x}{\log{x}} \le \pi (x) \le c_2 \frac{x}{\log{x}}$ "

Additionally, he also showed that if the ratio of $\pi (x)$ and $\frac{x}{\log{x}}$ goes toward a limit as $x \to \infty$ , then the limit is $1$ . Finally, in 1896, French mathematician Jacques Hadamard and Belgian mathematician Charles-Jean-Gustave-Nicholas de la Vallee-Poussin both (independently) produced a proof of the prime number theorem.

Chebyshev's statement

Let $\pi (n)$ denote the number of primes that is less than or equal to $n$ .

There exist numbers $c_1$ and $c_2$ such that

$c_1 \frac{x}{\log{x}} \le \pi (x) \le c_2 \frac{x}{\log{x}}$

Proof

Let $p$ be a prime and $n$ be an integer. Since

$\dbinom{2n}{n} = \frac{(2n)!}{(n!)(n!)}$

, $p$ divides $\dbinom{2n}{n}$ exactly

$\sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} (\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor)$

times.

Therefore, since

$\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor \le 1$

, we have

$\sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} (\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor)$

$\le \sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} 1$

$=\lfloor \log_{p}{(2n)} \rfloor$

so if $p^r | \dbinom{2n}{n}$ , $p^r \le 2n$

Repeated applications of that gives

$\dbinom{2n}{n} \le (2n)^{\pi (2n)}$

Additionally,

$2^n=\prod_{a=1}^n {2} \le \prod_{a=1}^n {\frac{n+a}{a}} = \frac{(n+1) \cdot (n+2) \cdot \dots \cdot 2n}{n!} = \dbinom{2n}{n} \le \sum_{a=0}^{2n} {\dbinom{2n}{a}} = 2^{2n}$

so

$2^n \le (2n)^{\pi (2n)}$

$\implies n \cdot \log {2} \le \pi (2n) \cdot \log {2n}$

$\implies \pi (2n) \ge \frac{n \cdot \log {2}}{\log {2n}}$

$\implies \pi (n) \ge \frac{\log{2}}{2} \cdot \frac{n}{\log {n}}$

Now, we note also that

$\prod_{\text{p is a prime from n to 2n}} {p} | \dbinom{2n}{n}$

so

$n^{\pi (2n) - \pi (n)}=\prod_{\text{p is a prime from n to 2n}} n < \prod_{\text{p is a prime from n to 2n}} p \le \dbinom{2n}{n} \le 2^{2n}$

Thus,

$\pi (2n) - \pi (n) \le \log {4} \cdot \frac{n}{\log {n}}$

We have

$\log {2n} \cdot \pi (2n)+\log {n} \cdot \pi (n)= \log {2} \cdot \pi (2n) + \log {n} \cdot (\pi (2n) - \pi (n)) \le \log {2} \cdot \pi (2n) + n \cdot \log {4} \le 3n \cdot \log {2}$

since $\pi (2n) \le n$ for $n>3$ (because there is at least a half of even numbers).

Repeated addition of that gives

$\pi (2n) = \frac{1}{\log{2n}} \cdot (\log {2n} \cdot \pi (2n)- \log {n} \cdot \pi (n))+(\log {n} \cdot \pi (n)- \log {\frac{n}{2}} \cdot \pi (\frac{n}{2}))+ (\log {\frac{n}{2}} \cdot \pi (\frac{n}{2})- \log {\frac{n}{4}} \cdot \pi (\frac{n}{4}))+ \dots$

$\le \frac{1}{\log {2n}} \cdot (3n \cdot \log {2}+\frac{3n}{2} \cdot \log {2}+\frac{3n}{4} \cdot \log {2}+ \dots)$

$= \frac{3n \cdot \log {2}}{\log {2n}} \cdot (1+ \frac{1}{2}+\frac{1}{4} + \dots)$

$= \frac{6n \cdot \log {2}}{\log {2n}}$

$\le \frac{\log{64} \cdot n}{\log{n}}$

As we have previously derived,

$\pi (2n) - \pi (n) \le \log {4} \cdot \frac{n}{\log {n}}$

so

$\frac{\log {x}}{2^m} \cdot \pi (\frac{x}{2^m}) - \frac{\log {x}}{2^{m+1}} \cdot \pi (\frac{x}{2^{m+1}}) = \frac{\log {x}}{2^{m}} (\pi (\frac{x}{2^m})-\pi (\frac{x}{2^{m+1}})) + \frac{\log {x}}{2^{m+1}} \cdot \pi (\frac{x}{2^{m+1}})$

$\le \frac{\log {x}}{2^{m}} \cdot \log {4} \cdot \frac{\frac{x}{2^{m+1}}}{\log {\frac{x}{2^{m+1}}}} + \frac{\log {x}}{2^{m+1}} \cdot \frac{\log{64} \cdot \frac{x}{2^{m+2}}}{\log{\frac{x}{2^{m+2}}}}$