Kurs:Zahlentheorie (Osnabrück 2016-2017)/Vorlesung 12/kontrolle

Die Abschätzungen von Tschebyschow

Pafnuti Lwowitsch Tschebyschow (1821-1894 Petersburg)

Wir wollen in diesem Abschnitt die Abschätzungen von Tschebyschow beweisen, die die Anzahl der Primzahlen unterhalb einer gewissen Zahl sowohl nach oben als auch nach unten abschätzen. Es geht um Abschätzungen der Form

${}c{\frac {x}{\ln x}}\leq \pi (x)\leq C{\frac {x}{\ln x}}\,.$

mit geeigneten Konstanten ${}c$ und ${}C$. Diese stellen eine Vorstufe zum Primzahlsatz von Hadamard und de la Vallée Pousin dar. Ihr Beweis benötigt einige Vorbereitungen.

Definition Referenznummer erstellen

Die erste Tschebyschow-Funktion ${}\vartheta (x)$ ist durch

${}\vartheta (x)=\sum _{p\leq x,p{\text{ prim}}}\ln(p)\,$

gegeben.

Lemma Lemma 12.2 ändern

Die Tschebyschow-Funktion ${}\vartheta (x)=\sum _{p\in {\mathbb {P} },\,p\leq x}\ln(p)$ genügt der Abschätzung

${}\vartheta (x)<(4\ln(2))x\,.$

Beweis

Der Binomialkoeffizient

${}{\binom {2n}{n}}={\frac {(2n)\cdot (2n-1)\cdots (n+2)\cdot (n+1)}{n\cdot (n-1)\cdots 2\cdot 1}}\,$

wird von allen Primzahlen ${}p$ mit ${}n<p\leq 2n$ geteilt, da diese den Zähler, aber nicht den Nenner teilen. Aus der allgemeinen Binomischen Formel ergibt sich die Abschätzung

${}2^{2n}=(1+1)^{2n}=\sum _{k=0}^{2n}{\binom {2n}{k}}>{\binom {2n}{n}}\,.$

Diese zwei Beobachtungen ergeben zusammen die Abschätzung

${}2^{2n}>\prod _{n<p\leq 2n,\,p\in {\mathbb {P} }}p\,.$

Wir wenden auf diese Abschätzung den natürlichen Logarithmus an und erhalten

${}2n\ln(2)>\sum _{n<p\leq 2n,\,p\in {\mathbb {P} }}\ln(p)=\vartheta (2n)-\vartheta (n)\,.$

Geschicktes Aufsummieren ergibt dann

${}{\begin{aligned}\vartheta (2^{r})-\vartheta (1)&=(\vartheta (2)-\vartheta (1))+(\vartheta (4)-\vartheta (2))+\cdots +(\vartheta (2^{r})-\vartheta (2^{r-1}))\\&<2\ln(2)+4\ln(2)+\cdots +2\cdot 2^{r-1}\ln(2)\\&=\sum _{i=0}^{r-1}2\cdot 2^{i}\cdot \ln(2)\\&=2\ln(2)(1+2+4+\cdots +2^{r-1})\\&=2\ln(2)(2^{r}-1)\\&=\ln(2)(2^{r+1}-2).\end{aligned}}$

Insbesondere erhält man für Zahlen ${}x$ mit ${}2^{r-1}<x\leq 2^{r}$ die Abschätzung

${}\vartheta (x)\leq \vartheta (2^{r})<(2^{r+1}-2)\ln(2)<2^{r+1}\ln(2)=(4\ln(2))\cdot 2^{r-1}<(4\ln(2))\cdot x\,.$

$\Box$

In der folgenden Aussage, die Legendres Identität heißt, bezeichnen wir den ${}p$-Exponenten mit ${}\nu _{p}$.

Lemma Lemma 12.3 ändern

Für eine Primzahl ${}p$ und eine natürliche Zahl ${}n$ ist

${}\nu _{p}(n!)=\left\lfloor {\frac {n}{p}}\right\rfloor +\left\lfloor {\frac {n}{p^{2}}}\right\rfloor +\left\lfloor {\frac {n}{p^{3}}}\right\rfloor +\ldots \,.$

Beweis

Hierzu muss man einfach zählen, wie viele der Zahlen zwischen ${}1$ und ${}n$ Vielfache von ${}p$, wie viele Vielfache von ${}p^{2}$ etc. sind. Das ergibt genau die Summe rechts.

$\Box$

Wir kommen nun zu den Abschätzungen von Tschebyschow.

Satz Satz 12.4 ändern

Es gibt Konstanten ${}C>c>0$ derart, dass die Primzahlfunktion ${}\pi (x)$ für alle ${}x$ den Abschätzungen

${}c{\frac {x}{\ln(x)}}\leq \pi (x)\leq C{\frac {x}{\ln(x)}}\,$

genügt.

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 Lemma 12.2 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.

$\Box$

Korollar Korollar 12.5 ändern

Es ist

${}\lim _{x\rightarrow \infty }{\frac {\pi (x)}{x}}=0\,.$

Beweis

Nach der Abschätzung von Tschebyschow nach oben gilt

${}{\frac {\pi (x)}{x}}\leq C{\frac {1}{\ln(x)}}\,.$

Da der Logarithmus gegen unendlich strebt, geht der Kehrwert gegen ${}0$, was die Behauptung impliziert.

$\Box$

Die Aussage dieses Korollars bedeutet, dass die Wahrscheinlichkeit, dass eine zufällig aus dem Intervall ${}[1,x]$ gewählte natürliche Zahl prim ist, bei ${}x$ hinreichend groß beliebig klein ist.

Satz Referenznummer erstellen

Es gibt eine reelle Zahl ${}D>1$ derart, dass es für jede natürliche Zahl ${}n\geq 1$ zwischen ${}n+1$ und ${}Dn$ stets eine Primzahl gibt.

Beweis

In Lemma 12.2 und im Beweis zur Abschätzung von Tschebyschow nach unten haben wir gesehen, dass es reelle positive Konstanten ${}b$ und ${}B$ gibt mit

${}bx<\vartheta (x)<Bx\,.$

Mit ${}D=B/b$ gilt dann

${}\vartheta (Dx)>bDx=Bx>\vartheta (x)\,.$

Daher liegt zwischen ${}x$ und ${}Dx$ mindestens eine Primzahl.

$\Box$

In diesem Satz kann man sogar ${}D=2$ erreichen. Dies war von Joseph Bertrand vermutet worden und wurde von Tschebyschow bewiesen. Man spricht vom Bertrandschen Postulat.

Joseph Bertrand (1822-1900 Paris)

Satz

Für jede positive natürliche Zahl ${}n$ gibt es eine Primzahl zwischen ${}n+1$ und ${}2n$.

Beweis

Dies werden wir hier nicht beweisen. Die Aussage ist aber prinzipiell mit den in diesem Abschnitt verwendeten Methoden beweisbar.

$\Box$

Ein offenes Problem ist hingegen die Vermutung von Legendre, die besagt, dass es zwischen zwei aufeinanderfolgenden Quadratzahlen, also zwischen ${}n^{2}$ und ${}(n+1)^{2}$ stets eine Primzahl gibt.

<< | Kurs:Zahlentheorie (Osnabrück 2016-2017) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)