View source for 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 <math>\pi (n)</math> denote the number of primes that is less than or equal to <math>n</math>.

There exist numbers <math>c_1</math> and <math>c_2</math> such that

<cmath>c_1 \frac{x}{\log{x}} \le \pi (x) \le c_2 \frac{x}{\log{x}}</cmath> "

Additionally, he also showed that if the ratio of <math>\pi (x)</math> and <math>\frac{x}{\log{x}}</math> goes toward a limit as <math>x \to \infty</math>, then the limit is <math>1</math>. 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 <math>\pi (n)</math> denote the number of primes that is less than or equal to <math>n</math>.

There exist numbers <math>c_1</math> and <math>c_2</math> such that

<cmath>c_1 \frac{x}{\log{x}} \le \pi (x) \le c_2 \frac{x}{\log{x}}</cmath>

==Proof==
Let <math>p</math> be a prime and <math>n</math> be an integer. Since

<cmath>\dbinom{2n}{n} = \frac{(2n)!}{(n!)(n!)}</cmath>

, <math>p</math> divides <math>\dbinom{2n}{n}</math> exactly

<cmath>\sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} (\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor)</cmath>

times.

Therefore, since

<cmath>\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor \le 1</cmath>

, we have

<cmath>\sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} (\lfloor \frac{2n}{p^i} \rfloor - 2 \cdot \lfloor \frac{n}{p^i} \rfloor)</cmath>

<cmath>\le \sum_{i=1}^{\lfloor \log_{p}{(2n)} \rfloor} 1</cmath>

<cmath>=\lfloor \log_{p}{(2n)} \rfloor</cmath>

so if <math>p^r | \dbinom{2n}{n}</math>, <math>p^r \le 2n</math>

Repeated applications of that gives

<cmath>\dbinom{2n}{n} \le (2n)^{\pi (2n)}</cmath>

Additionally,

<cmath>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}</cmath>

so

<cmath>2^n \le (2n)^{\pi (2n)}</cmath>

<cmath>\implies n \cdot \log {2} \le \pi (2n) \cdot \log {2n}</cmath>

<cmath>\implies \pi (2n) \ge \frac{n \cdot \log {2}}{\log {2n}}</cmath>

<cmath>\implies \pi (n) \ge \frac{\log{2}}{2} \cdot \frac{n}{\log {n}}</cmath>

Now, we note also that

<cmath>\prod_{\text{p is a prime from n to 2n}} {p} | \dbinom{2n}{n}</cmath>

so

<cmath>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}</cmath>

Thus,

<cmath>\pi (2n) - \pi (n) \le \log {4} \cdot \frac{n}{\log {n}}</cmath>

We have

<cmath>\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}</cmath>

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

Repeated addition of that gives

<cmath>\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</cmath>

<cmath>\le \frac{1}{\log {2n}} \cdot (3n \cdot \log {2}+\frac{3n}{2} \cdot \log {2}+\frac{3n}{4} \cdot \log {2}+ \dots)</cmath>

<cmath>= \frac{3n \cdot \log {2}}{\log {2n}} \cdot (1+ \frac{1}{2}+\frac{1}{4} + \dots)</cmath>

<cmath>= \frac{6n \cdot \log {2}}{\log {2n}}</cmath>

<cmath>\le \frac{\log{64} \cdot n}{\log{n}}</cmath>

As we have previously derived,

<cmath>\pi (2n) - \pi (n) \le \log {4} \cdot \frac{n}{\log {n}}</cmath>

so

<cmath>\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}})</cmath>

<cmath>\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}}}}</cmath>

<cmath>\le \frac{\log {x} \cdot \log {4}}{2^{2m+1}} \cdot (\frac{x}{\log {\frac{x}{2^{m+1}}}}+\frac{x}{\log {\frac{x}{2^{m+2}}}})</cmath>

<cmath>\le \frac{\log {x} \cdot \log {4}}{2^{2m}} \cdot \frac{x}{\log {x}- (m+2) \log {2}}</cmath>

<cmath>\le \log {4} \cdot \frac{x}{2^{m}}</cmath>

. (The last step I do not know why. If you can figure out the reason, please add the intermediate steps for it)

If we add that, we get a telescoping sum, so we have

<cmath>\log{x} \cdot \pi (x)  = \sum_{m=0}^{v} (\frac{\log {x}}{2^m} \cdot \pi (\frac{x}{2^m}) - \frac{\log {x}}{2^{m+1}} \cdot \pi (\frac{x}{2^{m+1}}))</cmath>

<cmath>\le \log{4} \cdot x \sum_{m=0}^{v} \frac{1}{2^m}</cmath>

<cmath>\le \log{4} \cdot x</cmath>

<cmath>\implies \pi (x) \le \log {4} \cdot \frac{x}{\log{x}}</cmath>

where <math>v</math> is the greatest integer such a that <math>2^v | x</math>.

Collecting our results, we see that

<cmath>\frac{\log{2}}{2} \cdot \frac{n}{\log {n}} \le \pi (x) \le \log {4} \cdot \frac{x}{\log{x}}</cmath>

We have thus found the desired <math>c_1</math> and <math>c_2</math>. ~Ddk001 <math>\blacksquare</math>

Note: This was actually the same method of proof given by Chebyshev.

==See Also==
*[[Number Theory]]
*[[Prime Number Theorem]]