« vorheriger Beitrag  · nächster Beitrag »

21.07.09 · 10:40 Uhr

Terence Tao über Primzahlen

Kategorie: Naturwissenschaften  ·  Kommentare: 6

Terence Tao hat auf der IMO in Bremen einen Vortrag "Structure and randomness in the primes" gehalten - hier als pdf.

We believe that the primes do not observe any significant pattern beyond the obvious ones (e.g. mostly being odd), but we are still a long way from making this belief completely rigorous.

Die Essenz seines Vortrages ist, daß sich Primzahlen (vermutlich) "pseudo-zufällig" verhalten, also daß es in den Primzahlen keine Muster (außer den offensichtlichen - z.B. dem Fehlen gerader Zahlen > 2) geben soll.

Während es schwierig ist, explizit große Primzahlen zu konstruieren, ist es realistischer, Aussagen über die Verteilung der Primzahlen beweisen zu wollen.

It is difficult to locate and count all the grains of sand in a box, but one can get an estimate on this count by weighing the box.

Das klassische Beispiel dafür ist natürlich die Riemannsche Zeta-Funktion, deren Nullstellen Information über die Verteilung der Primzahlen liefern. Insbesondere erhielt man aus der Nichtexistenz von Nullstellen s der Zeta-Funktion mit Realteil Re(s) mindestens 1 den Primzahlsatz:

Ungefähr 1/ln(n) aller Zahlen bis n sind Primzahlen.
(Genauer: Ungefähr 2/ln(n) aller ungeraden Zahlen und genau 2/n aller geraden Zahlen.)

Suche nach Primzahlen - zufällig und deterministisch

Man muß also ca. ln(10^k) Zahlen testen, wenn man eine Primzahl mit k Stellen finden will. Obwohl man keine Formeln hat, um deterministisch Primzahlen zu konstruieren, kann man mit solchen Tests zufällig gewählter Zahlen viele große Primzahlen finden (was ja bei der Verschlüsselung mit RSA benötigt wird). Das bekannteste Beispiel für einen solchen "Monte Carlo"-Primzahltest ist der Miller-Rabin-Test.
Die P=BPP-Vermutung besagt, daß man jeden Zufalls-Algorithmus zu einem deterministischen Algorithmus machen kann. (Genauer: wenn es einen Monte-Carlo-Algorithmus in polynomieller Zeit gibt, dann kann man daraus einen deterministischen Algorithmus in polynomieller Zeit machen.) Für die Suche nach Primzahlen haben Agrawal-Kayal-Saxena 2002 jedenfalls einen deterministischen Algorithmus gefunden, der in polynomieller Zeit entscheidet, ob eine Zahl Primzahl ist.

Primzahlen als 'Pseudozufallsmenge'

Neuere Arbeiten von Green-Tao benutzen nicht die arithmetischen Eigenschaften von Primzahlen, sondern einfach ihre Pseudozufälligkeit. Man betrachtet Mengen, die dieselbe Dichte haben wie die Primzahlen und beweist Sätze über solche Mengen. So haben Green und Tao ihren Satz bewiesen, daß es beliebig lange arithmetische Folgen von Primzahlen gibt. (Bemerkenswert auch deshalb, weil es als Konsequenz aus dem Primzahlsatz keine unendlich langen Folgen von Primzahlen geben kann.)
Es war schon seit 1975 bekannt (Satz von Szemeredi), daß es für jede 'Dichte' d und jedes k eine Zahl N gibt, so daß jede dN-elementige Teilmenge von {1,...,N} eine arithmetische Folge der Länge k enthält. Dieser Satz läßt sich auf die Primzahlen natürlich nicht anwenden, aber Green-Tao haben einen analogen Satz für Mengen mit der durch den Primzahlsatz gegebenen Dichte bewiesen.

We have many ways of establishing that a pattern exists...
but how does one demonstrate the absence of a pattern?

Cramers Zufalls-Modell betrachtet Primzahlen einfach als Zufalls-Menge, wo jede Zahl mit Wahrscheinlichkeit 1/ln(n) genommen wird. Mit diesem Modell kann man zum Beispiel plausibel machen (aber nicht beweisen), daß es unendlich viele Primzahlzwillinge geben sollte. Es gibt Verfeinerungen dieses Modells, mit denen man dann auch gute Vorhersagen für die Anzahl der Primzahlzwillinge bis n erhält. (Seite 11/12 im pdf.)

Zu der Frage, ob man solche Plausibilitäts-Argumente zu Beweisen machen kann, schreibt Tao: "There has been some progress in doing this. One approach is to try to classify all the possible ways in which a set could fail to be pseudorandom (i.e. it does something noticeably different from what a random set would do), and then show that the primes do not behave in any of these ways."

Konkret wurde das von Vinogradov benutzt, um zu zeigen, daß jede ungerade Zahl Summe von 3 Primzahlen ist ("Ungerade Goldbach-Vermutung"). Dies wäre nämlich richtig für eine zufällig gewählte Menge der Dichte 1/ln(n) und man kann zeigen, daß die Primzahlen sich (in Hinblick auf die "Ungerade Goldbach-Vermutung") dann von einer pseudozufälligen Menge unterscheiden würden, wenn es einen Bias bei der letzten Ziffer von Primzahlen gäbe, d.h. wenn eine ungerade Zahl als letzte Ziffer häufiger vorkäme als die anderen, und daß die "Ungerade Goldbach-Vermutung" nur dann falsch sein kann, wenn es für die Primzahlen einen solchen Bias (nicht notwendig modulo 10) gibt..
Mit dem Satz von Green-Tao kann man zum Beispiel zeigen, daß es unendlich viele Primzahlen mit letzter Ziffer 1 geben muß. Allgemein hat Vinogradov bewiesen, daß es für Reste von Primzahlen keinen Bias nicht gibt. (Seite 15/16 im pdf.)

Also: man kann Sätze über Primzahlen beweisen, indem man zusätzliche "Muster" in der "Pseudozufalls-Menge" der Primzahlen ausschließt.

 

Autor: Thilo· 6 Kommentare· Permalink· Trackback-URL

Tags: deterministisch· Dichte· Green· Primzahl· pseudozufällig· Szemeredi· Tao· Test· Vinogradov· Wahrscheinlichkeit· Zufall