Zahlentheorie (Osnabrück 2008)/Vorlesung 12

Aus Wikiversity

Wechseln zu: Navigation, Suche

Inhaltsverzeichnis




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. Sie stellen eine Vorstufe zum Primzahlsatz von Hadamard und de la Vallée Pousin dar. Ihr Beweis benötigt einige Vorbereitungen.


Definition (Erste Tschebyschow-Funktion)  

Die erste Tschebyschow-Funktion \vartheta (x) ist gegeben durch

\vartheta(x)=\sum_{p\le x, p \mbox{ prim} } \ln (p) \, .



Lemma  

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 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 zusammen ergeben 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{align} \vartheta(2^r) & = \vartheta(2^r) - \vartheta(1) \\ & = (\vartheta(2) - \vartheta(1)) + (\vartheta(4) - \vartheta(2)) + \ldots +(\vartheta(2^r) - \vartheta(2^{r-1})) \\ & < 2 \ln(2) + \ldots +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+ \ldots + 2^{r-1}) \\ & = 2 \ln (2) (2^r-1) \\ & = \ln (2)(2^{r+1} -2) \, .\end{align}

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



Lemma (Identität von Legendre)  

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 p2 etc. sind. Das ergibt genau die Summe rechts.

\Box



Satz (Abschätzungen von Tschebyschow)  

Es gibt Konstanten C > c > 0 derart, dass die Primzahlfunktion π(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 2ln(p) / ln(x) > 1. Ferner gilt für x \geq 2 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{align} \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{align}

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

Wir betrachten nun die Abschätzung nach unten. Nach Legendres Identität (Lemma 12.3) ist

\begin{align} \nu_p\left( \binom{2n}{n}\right) & = \nu_p\left( \frac{ (2n)!}{n! n!}\right) \\ & = \left\lfloor \frac{2n}{p} \right\rfloor + \ldots + \left\lfloor \frac{2n}{p^k} \right\rfloor -2 \left( \left\lfloor \frac{n}{p} \right\rfloor + \ldots + \left\lfloor \frac{n}{p^k} \right\rfloor \right) . \, \end{align}

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 Summe links 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 \mbox{ 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{align} n \ln(2) & \leq \sum_{p < \sqrt{2n} } \left\lfloor \frac{\ln (2n)}{\ln (p)} \right\rfloor \ln(p) + \sum_{ \sqrt{2n} \leq p <2n} \left\lfloor \frac{\ln (2n)}{\ln (p)} \right\rfloor \ln(p) \\ & \leq \sum_{p < \sqrt{2n} } \ln (2n)+\sum_{ \sqrt{2n} \leq p <2n} \ln(p) \\ & \leq \sqrt{2n} \ln(2n) + \vartheta (2n) . \, \end{align}

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 null). 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  

Es ist

\lim_{x \rightarrow \infty} \frac{\pi(x)}{x} =0 \, .

Beweis  

Nach der Abschätzung von Tschebyschow (Satz 12.4) 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  

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.

Joseph Bertrand (1822-1900 Paris)



Satz (Bertrandsches Postulat)

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

Beweis

Dies werden wir hier nicht beweisen. Die Ausage 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 n2 und (n + 1)2 stets eine Primzahl gibt.


<< | Kurs:Zahlentheorie (Osnabrück 2008) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)
Von „http://de.wikiversity.org/wiki/Zahlentheorie_(Osnabr%C3%BCck_2008)/Vorlesung_12“
Persönliche Werkzeuge