Mathematik
Refine
Year of publication
- 1999 (2) (remove)
Document Type
- diplomthesis (2) (remove)
Language
- German (2)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Institute
- Mathematik (2)
Über die Anzahlfunktion π(x)
(1999)
Bereits Euklid wusste, dass es unendlich viele Primzahlen gibt. Euler zeigte die qualitative Aussage ¼(x) x ! 0 bei x ! 1. Legendre definierte als erster die Anzahlfunktion ¼(x) als die Anzahl aller Primzahlen · x, (x 2 R) und vermutete irrtümlicherweise, dass ¼(x) = x log(x)¡B; wobei lim x!1 B(x) = 1; 083 66 : : : ist. Gauss vermutete, dass die Funktionen ¼(x) und li(x) := lim "!0 ">0 0@ u=1¡" Z u=0 du log(u) + u=x Z u=1+" du log(u)1A asymptotisch Äquivalent sind. Tschebyschew konnte die Legendresche Vermutung widerlegen; außerdem bewies er: Wenn der Grenzwert lim x!1 ¼(x) x log(x) existiert, so muss dieser gleich 1 sein. Dank wegweisender Vorarbeiten von Riemann, gelang es im Jahr 1896 unabhängig voneinander und nahezu zeitgleich Hadamard und De La Vallee Poussin, den Primzahlsatz analytisch zu beweisen. Beide verwendeten entscheidend die Tatsache, dass die Zetafunktion ³ in der Halbebene Re(s) ¸ 1 nicht verschwindet. Die Beweise waren zuerst so lang und kompliziert, dass sie heutzutage nur noch einen historischen Wert besitzen. Es dauerte weitere 84 Jahre bis der Beweis so vereinfacht werden konnte, dass er nur wenige Seiten in Anspruch nimmt. Ein wichtiger Verdienst kommt hierbei der Arbeit von Newman aus dem Jahre 1980 zu. Lange Zeit wurde es für kaum möglich gehalten, einen Beweis des Primzahlsatzes zu finden, der ohne eine gewisse Kenntnis der komplexen Nullstellen der Zetafunktion auskommt. Und doch glückte 1948 ein solcher Beweis durch Selberg und Erdös mit elementaren Mitteln. Erwähnenswert dabei, dass der Beweis noch lange nicht einfach ist. Uns schienen die analytischen Beweise durchsichtiger zu sein. Daher haben wir in dieser Arbeit auf einen elementaren Beweis verzichtet. Der analytischen Weg zum Primzahlsatz von Newman kommt einerseits mit Integration längs endlicher Wege (und der Tatsache ³(s) 6= 0 in ¾ ¸ 1) aus, umgeht also Abschätzungen bei 1; andererseits ist er frei von Sätzen der Fourier-Analysis. Beim Beweis des Primzahlsatzes von Wolke benutzt man anstelle von ³0(s) ³(s) die Funktion ³ 1 k mit großen k. Wegen des Pols bei s=1 bringt dies bei der Integration leichte Komplikationen, hat aber den Vorteil, dass außer der Nullstellen-Freiheit keine nichttriviale Abschätzung für ³ oder ³0 erforderlich ist. Dank der elementaren Äquivalenz zwischen dem Primzahlsatz und der Konvergenz von 1Pn=1 ¹(n) n brauchte Newman nur die Konvergenz von 1Pn=1 ¹(n) n zu zeigen. Dies erreichte er mit Hilfe seines Konvergenzsatzes. Die Legendresche Formel, die auf dem Sieb des Eratosthenes basiert, erlaubt die exakte Berechnung von ¼(x), wenn alle px nicht übersteigenden Primzahlen bekannt sind. Diese prinzipielle Möglichkeit zur Ermittlung von ¼(x) ist in der Praxis natürlich stark limitiert durch die mit x rasch anwachsende Anzahl der rechts in der Legendresche Formel zu berücksichtigenden Summanden. Mit verfeinerten Siebtechniken haben verschiedene Autoren zur Legendresche Formel analoge Formeln ¼(x) ersonnen, bei denen der genannte Nachteil von Legendresche Formel sukzessive reduziert wurde. Zu erwähnen sind hier vor allem Meissel, Lehmer, sowie Lagarias, Miller und Odlyzko. Aus den Graphen von R(x)¡¼(x); li(x)¡¼(x) und x log(x) ¡¼(x) für den betrachteten Bereich x · 1018 konnten wir feststellen, dass R(x); li(x) sowie x log(x) die Anzahlfunktion Pi (x) annähern, wobei R(x) die beste Approximation für Pi(x) von allen drei ist.
Wir werden uns in dieser Arbeit vorwiegend mit einem Modell befassen, das Y. Peres, C. Kenyon, W. Evans und L.J. Schulman 1998 in ihrem Artikel \Broadcasting on trees and the Ising-Modell" eingeführt haben.
In diesem Modell wird ein Signal, das die Werte +1 oder -1 annehmen kann, von der Wurzel eines Baumes aus entlang der Äste eines unendlichgroßen Baumes übertragen. Die Kanten des Baumes agieren dabei als Übertragungskanäle zwischen den Knoten. Jede Kante kann das Signal korrekt übertragen oder es flippen, das heißt, das Vorzeichen des Signals umkehren.
Das Übertragungsverhalten der Kanten ist zufällig. Mit einer festen Wahrscheinlichkeit ϵ, mit 0 < ϵ <= 1/2 , verfälscht eine Kante das Signal. Dies geschieht an allen Kanten unabhängig mit der gleichen Wahrscheinlichkeit. Es stellt sich nun die Frage, wie groß diese Fehlerwahrscheinlichkeit höchstens sein darf, damit das, was in der Krone des Baumes ankommt, noch etwas zu tun hat mit dem, was in der Wurzel eingespeist wird. Mit anderen Worte: Sind die Signale auf Knoten, die einen Abstand >= n von der Wurzel haben, für n -> ∞ asymptotisch unabhängig vom Signal in der Wurzel? Eine Möglichkeit, den Grad der Abhängigkeit zu messen, ist die sogenannte Information, der Kullback-Leibler-Abstand von gemeinsamer Verteilung zur Produkt-Verteilung, die in Definition 16 eingeführt wird.
Wir werden sehen, daß es eine kritische Schwelle ϵc;I für Informationsübertragung gibt. Ist die Fehlerwahrscheinlichkeit größer als ϵc;I , so ist die Information, die zwischen Wurzel und Krone übertragen wird, 0. Ist die Fehlerwahrscheinlichkeit kleiner als ϵc;I , so wird Information übertragen. Dieser kritische Wert ϵc;I hängt nur von der Branching-Number, einer Art mittleren Verzweigungszahl, des Baumes (vgl. Definition 1) ab.
Wir werden sehen, daß das Broadcasting-Modell eine elegante Formulierung eines wohlbekannten Modells, des Ising-Modells, mit freien Randbedingungen, ist.
Im Ising-Modell hat jeder Knoten des Baumes einen "magnetischen" Spin, der entweder +1 oder -1 sein kann. Spins direkt benachbarter Knoten beeinflussen sich, in dem sie versuchen, den gleichen Wert anzunehmen. Diesem Effekt wirkt ein thermischer Einfluß entgegen, der mittels eines als Temperatur bezeichneten Parameters modelliert wird.
Die klassische Frage im Ising-Modell ist, ob Phasenübergang stattfindet. Wir wollen Phasenübergang als das Phänomen verstehen, daß die Wurzel des Baumes die Vorgabe von Randbedingungen auf der Krone des Baumes spürt. Ist dies der Fall, so sagen wir, daß Phasenübergang stattfindet. Auch dies ist eine
Form der gegenseitigen Beeinflussung zwischen Wurzel und Krone des Baumes. Russel Lyons hat 1989 in seinem Artikel \The Ising-Model on trees and treelike Graphs" das Ising-Modell auf Bäumen untersucht und gezeigt, daß es eine kritische Temperatur tc für Phasenübergang gibt. Ist die Temperatur höher als tc, so spürt die Wurzel nichts von den Randbedingungen der Krone; ist die Temperatur geringer als tc, so haben die Randbedingungen Einfluß auf die Wurzel. Auch hier hängt die kritische Temperatur nur von der Branching-Number des Baumes ab.
In der Broadcasting-Formulierung des Modells ist der Fluß von Information ein naheliegendes Werkzeug, um die Beeinflussung von Wurzel und Krone zu messen, in der Ising-Formulierung ist die Existenz von Phasenübergang ein ebenso naheliegendes Werkzeug, ebendiesen Einfluß zu messen.
Wir werden die beiden Arten der Beeinflussung miteinander vergleichen und können zeigen, daß für die Übertragung von Information stets eine stärkere Interaktion zwischen den Knoten notwendig ist, als für den Einfluß der Randbedingungen aus der Krone.
Als letztes Phänomen werden wir untersuchen, ob es einen Pfad im Baum gibt, der in der Wurzel startend nur Knoten gleichen Spins besucht und die unendlich weit entfernte Krone erreicht. Wir bezeichnen dieses Phänomen als Spinperkolation.
Wir werden die Berechnung der kritischen Interaktion für Spinperkolation in einem Bernoulli-Feld auf den Kanten rekapitulieren und dann zeigen, daß die Existenz eines Perkolationspfades nur von der Interaktionsstärke des Modells und nicht von etwaigen Randbedingungen abhängt. Dabei kombinieren wir Ergebnisse aus zwei Arbeiten von Lyons und die Erkenntnis, daß Broadcasting- Modell und freies Ising-Modell identisch sind. Wir erhalten so einen neuen, einfachen Beweis über die kritische Interaktion für Spinperkolation in der Plus-Phase des Ising-Modells, die Lyons bereits in [7] berechnet hat.