|
|
| Line 1: |
Line 1: |
| − | 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.
| + | The title of the page is found to be unfitting. The contents are moved to a new page. [[Chebyshev and the history of the Prime Number Theorem]] |
| − | | |
| − | ==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]]
| |
