Zahlentheorie/Primzahlverteilung/Ungleichungen von Tschebyschow/Fakt/Beweis

Beweis

Wir betrachten zuerst die Abschätzung nach oben. Für ${}{\sqrt {x}}<p$ gilt ${}\ln(x)/2<\ln(p)$ und somit ${}2\ln(p)/\ln(x)>1$. Ferner gilt die Abschätzung ${}2{\sqrt {x}}>\ln(x)$ und somit

${}{\sqrt {x}}=x/{\sqrt {x}}<2x/\ln(x)\,.$

Aus diesen zwei Vorüberlegungen und aus Fakt folgt dann die Abschätzung

${}{\begin{aligned}\pi (x)&=\pi ({\sqrt {x}})+(\pi (x)-\pi ({\sqrt {x}}))\\&\leq {\sqrt {x}}+\sum _{{\sqrt {x}}<p\leq x,\,p\in {\mathbb {P} }}1\\&<{\sqrt {x}}+{\frac {2}{\ln(x)}}\left(\sum _{{\sqrt {x}}<p\leq x,\,p\in {\mathbb {P} }}\ln(p)\right)\\&<{\sqrt {x}}+{\frac {2}{\ln(x)}}\vartheta (x)\\&<{\sqrt {x}}+{\frac {2}{\ln(x)}}(4\ln(2))x\\&\leq (2+8\ln(2)){\frac {x}{\ln(x)}}.\end{aligned}}$

Die Abschätzung ist also mit ${}C=2+8\ln(2)$ erfüllt.

Wir betrachten nun die Abschätzung nach unten. Nach Legendres Identität ist

${}{\begin{aligned}\nu _{p}{\left({\binom {2n}{n}}\right)}&=\nu _{p}{\left({\frac {(2n)!}{n!n!}}\right)}\\&=\nu _{p}{\left((2n)!\right)}-2\nu _{p}(n!)\\&=\left\lfloor {\frac {2n}{p}}\right\rfloor +\cdots +\left\lfloor {\frac {2n}{p^{k}}}\right\rfloor -2\left(\left\lfloor {\frac {n}{p}}\right\rfloor +\cdots +\left\lfloor {\frac {n}{p^{k}}}\right\rfloor \right)\\&=\sum _{j=1}^{k}{\left(\left\lfloor {\frac {2n}{p^{j}}}\right\rfloor -2\left\lfloor {\frac {n}{p^{j}}}\right\rfloor \right)}.\end{aligned}}$

Die Summe läuft hierbei bis zum maximalen ${}k$ mit ${}p^{k}\leq 2n$, also bis ${}k=\lfloor \log _{p}(2n)\rfloor =\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor$. Da die einzelnen Summanden der letzten Summe nur ${}0$ oder ${}1$ sein können, folgt,

${}\nu _{p}{\left({\binom {2n}{n}}\right)}\leq \left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor \,.$

Durch betrachten aller Primzahlen ergibt sich daraus die Abschätzung

${}{\binom {2n}{n}}\leq \prod _{p<2n,p{\text{ prim}}}p^{\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor }\,.$

Andererseits ist

${}2^{n}\leq {\frac {2n}{n}}{\frac {2n-1}{n-1}}\cdots {\frac {n+1}{1}}={\binom {2n}{n}}\,.$

Wir wenden den Logarithmus auf die zusammengesetzte Abschätzung an und erhalten

${}n\ln(2)\leq \sum _{p<2n}\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor \ln(p)\,.$

Für ${}p>{\sqrt {2n}}$ ist ${}\ln(p)>{\frac {\ln(2n)}{2}}$ und damit ${}\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor =1$. Wir verwenden dies in der folgenden Aufspaltung und erhalten

${}{\begin{aligned}n\ln(2)&\leq \sum _{p\leq {\sqrt {2n}}}\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor \ln(p)+\sum _{{\sqrt {2n}}<p<2n}\left\lfloor {\frac {\ln(2n)}{\ln(p)}}\right\rfloor \ln(p)\\&\leq \sum _{p\leq {\sqrt {2n}}}\ln(2n)+\sum _{{\sqrt {2n}}<p<2n}\ln(p)\\&\leq {\sqrt {2n}}\ln(2n)+\vartheta (2n).\end{aligned}}$

Dies ergibt die Abschätzung

${}\vartheta (2n)\geq n{\left(\ln(2)-{\frac {{\sqrt {2n}}\ln(2n)}{n}}\right)}\,.$

Der Bruch rechts ist beschränkt (und konvergiert gegen ${}0$). Man erhält also eine positive Konstante ${}M$ mit ${}\vartheta (2n)\geq Mn$ für ${}n$ hinreichend groß. Für ${}x$ zwischen ${}2n$ und ${}2n+2$ hat man

${}\vartheta (x)\geq \vartheta (2n)\geq Mn\geq M{\frac {x-2}{2}}\,,$

und dies ist wiederum ${}\geq Nx$ für eine geeignete positive Schranke ${}N$ (und für ${}x$ hinreichend groß). Dann gibt es aber auch eine positive Schranke ${}c$ mit ${}\vartheta (x)\geq cx$ für alle ${}x\geq 2$. Aus

${}cx\leq \vartheta (x)=\sum _{p\leq x}\ln(p)\leq \pi (x)\ln(x)\,$

folgt nun ${}c{\frac {x}{\ln(x)}}\leq \pi (x)$ wie behauptet.

Zur bewiesenen Aussage