Kurs:Zahlentheorie (Osnabrück 2008)/Vorlesung 12/latex
\setcounter{section}{12}
\zwischenueberschrift{Die Abschätzungen von Tschebyschow}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Chebyshev.jpg} }
\end{center}
\bildtext {Pafnuti Lwowitsch Tschebyschow (1821-1894 Petersburg)} }
\bildlizenz { Chebyshev.jpg } {} {VindicatoR} {pl.wikipedia.org} {PD} {}
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.
\inputdefinition
{}
{
Die \definitionswort {erste Tschebyschow-Funktion}{}
\mathl{\vartheta (x)}{} ist durch
\mavergleichskettedisp
{\vergleichskette
{ \vartheta(x)
}
{ =} { \sum_{p\le x, p \text{ prim} } \ln (p)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gegeben.
}
\inputfaktbeweis
{Zahlentheorie/Primzahlverteilung/Ungleichungen von Tschebyschow/Lemma 1/Fakt}
{Lemma}
{}
{
Die Tschebyschow-Funktion
\mavergleichskette
{\vergleichskette
{ \vartheta(x)
}
{ = }{\sum_{p \in {\mathbb P},\, p \leq x} \ln (p)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
genügt der Abschätzung
\mavergleichskettedisp
{\vergleichskette
{ \vartheta(x)
}
{ <} { (4 \ln (2)) x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
{
Der Binomialkoeffizient
\mavergleichskettedisp
{\vergleichskette
{ \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
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskettedisp
{\vergleichskette
{ 2^{2n}
}
{ =} { (1+1)^{2n}
}
{ =} { \sum_{k = 0}^{2n} \binom{2n}{k}
}
{ >} { \binom{2n}{n}
}
{ } {
}
}
{}{}{.}
Diese zwei Beobachtungen ergeben zusammen die Abschätzung
\mavergleichskettedisp
{\vergleichskette
{ 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
\mavergleichskettedisp
{\vergleichskette
{ 2n \ln (2)
}
{ >} { \sum_{n <p \leq 2n, \, p \in {\mathbb P} } \ln (p)
}
{ =} { \vartheta(2n) - \vartheta (n)
}
{ } {
}
{ } {
}
}
{}{}{.}
Geschicktes Aufsummieren ergibt dann
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ \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})
}
}
{
\vergleichskettefortsetzungalign
{ =} { 2 \ln (2) (2^r-1)
}
{ =} { \ln (2)(2^{r+1} -2)
}
{ } {}
{ } {}
}
{}{.}
Insbesondere erhält man für Zahlen $x$ mit
\mavergleichskette
{\vergleichskette
{ 2^{r-1}
}
{ < }{x
}
{ \leq }{ 2^r
}
{ }{
}
{ }{
}
}
{}{}{}
die Abschätzung
\mavergleichskettedisp
{\vergleichskette
{ \vartheta(x)
}
{ \leq} { \vartheta(2^r)
}
{ <} { (2^{r+1} -2)\ln (2)
}
{ <} { 2^{r+1}\ln (2)
}
{ =} {(4 \ln(2)) \cdot 2^{r-1}
}
}
{
\vergleichskettefortsetzung
{ <} { (4 \ln(2)) \cdot x
}
{ } {}
{ } {}
{ } {}
}{}{.}
\inputfaktbeweis
{Zahlentheorie/Primzahlverteilung/Ungleichungen von Tschebyschow/Legendres Identität/Fakt}
{Lemma}
{}
{
Für eine Primzahl $p$ und eine natürliche Zahl $n$ ist
\mavergleichskettedisp
{\vergleichskette
{ \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
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
{
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.
\inputfaktbeweis
{Zahlentheorie/Primzahlverteilung/Ungleichungen von Tschebyschow/Fakt}
{Satz}
{}
{
Es gibt Konstanten
\mavergleichskette
{\vergleichskette
{C
}
{ > }{c
}
{ > }{0
}
{ }{
}
{ }{
}
}
{}{}{}
derart, dass die
\definitionsverweis {Primzahlfunktion}{}{}
\mathl{\pi(x)}{} für alle $x$ den Abschätzungen
\mavergleichskettedisp
{\vergleichskette
{ c \frac{x}{\ln(x)}
}
{ \leq} {\pi(x)
}
{ \leq} {C \frac{x}{\ln(x)}
}
{ } {
}
{ } {
}
}
{}{}{}
genügt.
}
{
Wir betrachten zuerst die Abschätzung nach oben. Für
\mavergleichskette
{\vergleichskette
{ \sqrt{x}
}
{ < }{ p
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt
\mavergleichskette
{\vergleichskette
{ \ln (x)/2
}
{ < }{ \ln (p)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und somit
\mavergleichskette
{\vergleichskette
{ 2 \ln (p)/\ln (x)
}
{ > }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Ferner gilt die Abschätzung
\mavergleichskette
{\vergleichskette
{ 2\sqrt{x}
}
{ > }{ \ln(x)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und somit
\mavergleichskettedisp
{\vergleichskette
{ \sqrt{x}
}
{ =} { x/\sqrt{x}
}
{ <} { 2x/\ln (x)
}
{ } {}
{ } {}
}
{}{}{.}
Aus diesen zwei Vorüberlegungen und aus
Lemma 12.2
folgt dann die Abschätzung
\mavergleichskettealign
{\vergleichskettealign
{\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)
}
}
{
\vergleichskettefortsetzungalign
{ <} { \sqrt{x} + \frac{2}{\ln (x)} (4 \ln(2))x
}
{ \leq} { ( 2 + 8 \ln (2))\frac{x}{\ln (x)}
}
{ } {}
{ } {}
}
{}{.}
Die Abschätzung ist also mit
\mavergleichskette
{\vergleichskette
{C
}
{ = }{ 2 + 8 \ln (2)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
erfüllt.
Wir betrachten nun die Abschätzung nach unten. Nach
Legendres Identität
ist
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{\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) }
}
}
{}
{}{.}
Die Summe läuft hierbei bis zum maximalen $k$ mit
\mavergleichskette
{\vergleichskette
{ p^{k}
}
{ \leq }{ 2n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
also bis
\mavergleichskette
{\vergleichskette
{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,
\mavergleichskettedisp
{\vergleichskette
{ \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
\mavergleichskettedisp
{\vergleichskette
{ \binom { 2n } { n }
}
{ \leq} { \prod_{p < 2n, p \text{ prim} } p^{\left\lfloor \frac{\ln (2n)}{\ln (p)} \right\rfloor}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Andererseits ist
\mavergleichskettedisp
{\vergleichskette
{ 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
\mavergleichskettedisp
{\vergleichskette
{ n \ln(2)
}
{ \leq} { \sum_{p < 2n} \left\lfloor \frac{\ln (2n)}{\ln (p)} \right\rfloor \ln(p)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Für
\mavergleichskette
{\vergleichskette
{ p
}
{ > }{ \sqrt{2n}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{ \ln(p)
}
{ > }{ \frac{\ln (2n)}{2}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und damit
\mavergleichskette
{\vergleichskette
{ \left \lfloor { \frac{ \ln(2n) }{ \ln(p) } } \right \rfloor
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir verwenden dies in der folgenden Aufspaltung und erhalten
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{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)
}
{ } {}
}
{}
{}{.}
Dies ergibt die Abschätzung
\mavergleichskettedisp
{\vergleichskette
{ \vartheta(2n)
}
{ \geq} { n { \left( \ln(2) - \frac{ \sqrt{2n}\ln (2n)}{n} \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Der Bruch rechts ist beschränkt
\zusatzklammer {und konvergiert gegen $0$} {} {.}
Man erhält also eine positive Konstante $M$ mit
\mavergleichskette
{\vergleichskette
{ \vartheta(2n)
}
{ \geq }{ Mn
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für $n$ hinreichend groß. Für $x$ zwischen $2n$ und
\mathl{2n+2}{} hat man
\mavergleichskettedisp
{\vergleichskette
{ \vartheta(x)
}
{ \geq} { \vartheta (2n)
}
{ \geq} { Mn
}
{ \geq} { M \frac{x-2}{2}
}
{ } {}
}
{}{}{,}
und dies ist wiederum
\mathl{\geq Nx}{} für eine geeignete positive Schranke $N$
\zusatzklammer {und für $x$ hinreichend groß} {} {.}
Dann gibt es aber auch eine positive Schranke $c$ mit
\mavergleichskette
{\vergleichskette
{ \vartheta (x)
}
{ \geq }{ cx
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{ x
}
{ \geq }{ 2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Aus
\mavergleichskettedisp
{\vergleichskette
{cx
}
{ \leq} { \vartheta(x)
}
{ =} {\sum_{p \leq x} \ln (p)
}
{ \leq} { \pi(x) \ln(x)
}
{ } {}
}
{}{}{}
folgt nun
\mavergleichskette
{\vergleichskette
{ c \frac{x}{\ln(x)}
}
{ \leq }{ \pi(x)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
wie behauptet.
\inputfaktbeweis
{Primzahlverteilung/Häufigkeit gegen null/Fakt}
{Korollar}
{}
{
Es ist
\mavergleichskettedisp
{\vergleichskette
{ \lim_{x \rightarrow \infty} \frac{\pi(x)}{x}
}
{ =} { 0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
{
Nach
der Abschätzung von Tschebyschow
nach oben gilt
\mavergleichskettedisp
{\vergleichskette
{ \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.
Die Aussage dieses Korollars bedeutet, dass die Wahrscheinlichkeit, dass eine zufällig aus dem Intervall
\mathl{[1,x]}{} gewählte natürliche Zahl prim ist, bei $x$ hinreichend groß beliebig klein ist.
\inputfaktbeweis
{Primzahlverteilung/Primzahl zwischen n+1 und Bn/Fakt}
{Satz}
{}
{
Es gibt eine reelle Zahl
\mathl{D >1}{} derart, dass es für jede natürliche Zahl
\mathl{n \geq 1}{} zwischen
\mathkor {} {n+1} {und} {Dn} {}
stets eine
\definitionsverweis {Primzahl}{}{}
gibt.
}
{
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
\mavergleichskettedisp
{\vergleichskette
{bx
}
{ <} {\vartheta(x)
}
{ <} { Bx
}
{ } {
}
{ } {
}
}
{}{}{.}
Mit
\mavergleichskette
{\vergleichskette
{D
}
{ = }{ B/b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt dann
\mavergleichskettedisp
{\vergleichskette
{ \vartheta (Dx)
}
{ >} { bDx
}
{ =} { Bx
}
{ >} { \vartheta(x)
}
{ } {
}
}
{}{}{.}
Daher liegt zwischen $x$ und $Dx$ mindestens eine Primzahl.
In diesem Satz kann man sogar
\mathl{D=2}{} erreichen. Dies war von Joseph Bertrand vermutet worden und wurde von Tschebyschow bewiesen.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Bertrand.jpg} }
\end{center}
\bildtext {Joseph Bertrand (1822-1900 Paris)} }
\bildlizenz { Bertrand.jpg } {} {Wladyslaw Sojka} {Commons} {PD} {http://scienceworld.wolfram.com/biography/Bertrand.html}
{Primzahlverteilung/Primzahl zwischen n+1 und 2n/Bertrandsches Postulat/Fakt}
{Satz}
{}
{
Für jede positive natürliche Zahl $n$ gibt es eine \definitionsverweis {Primzahl}{}{} zwischen \mathkor {} {n+1} {und} {2n} {.}
}
{
Dies werden wir hier nicht beweisen. Die Aussage ist aber prinzipiell mit den in diesem Abschnitt verwendeten Methoden beweisbar.
Ein offenes Problem ist hingegen die Vermutung von Legendre, die besagt, dass es zwischen zwei aufeinanderfolgenden Quadratzahlen, also zwischen $n^2$ und
\mathl{(n+1)^2}{} stets eine Primzahl gibt.