During AMC testing, the AoPS Wiki is in read-only mode. Your account is not considered logged in on wiki pages and no edits can be made.

Chebyshev and the history of the Prime Number Theorem

Revision as of 21:53, 10 January 2025 by Ddk001 (talk | contribs) (See Also)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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}}}}\]

\[\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}}}})\]

\[\le \frac{\log {x} \cdot \log {4}}{2^{2m}} \cdot \frac{x}{\log {x}- (m+2) \log {2}}\]

\[\le \log {4} \cdot \frac{x}{2^{m}}\]

. (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

\[\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}}))\]

\[\le \log{4} \cdot x \sum_{m=0}^{v} \frac{1}{2^m}\]

\[\le \log{4} \cdot x\]

\[\implies \pi (x) \le \log {4} \cdot \frac{x}{\log{x}}\]

where $v$ is the greatest integer such a that $2^v | x$.

Collecting our results, we see that

\[\frac{\log{2}}{2} \cdot \frac{n}{\log {n}} \le \pi (x) \le \log {4} \cdot \frac{x}{\log{x}}\]

We have thus found the desired $c_1$ and $c_2$. ~Ddk001 $\blacksquare$

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

See Also