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(10k) 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.

Kommentare (7)

  1. #1 adenosine
    21. Juli 2009

    Was ist eigentlich das bemerkenswerte an diesen Zahlen, dass ein derartiges Theoriegebäude darüber errichtet wird. Warum treibt man den Aufwand nicht für den Zahlentyp, der an der 2. und 3. Nachkommastelle die Werte 2 und 3 enthält?

  2. #2 Thilo Kuessner
    21. Juli 2009

    Die Essenz von Tao’s Vortrag ist ja gerade, daß nichts besonderes an den Primzahlen ist, sondern daß sie sich (von offensichtlichen Einschränkungen abgesehen) wohl genau so verhalten wie jede andere Menge mit derselben Häufigkeitsverteilung.

    Zur Frage nach dem Nutzen: so gut wie alle Verschlüsselungsverfahren im Internet (wenn man z.B. beim Bestellen seine Kreditkartennnummer angibt etc.) benutzen RSA für den Schlüsselaustausch. Für RSA verwendet man zur Zeit 154-stellige Primzahlen, mit besser werdender Technik wird man natürlich immer größere Primzahlen brauchen. Insofern ist es schon von großem praktischem Interesse zu wissen, wie man (automatisiert) große Primzahlen finden kann.

  3. #3 H.M.Voynich
    21. Juli 2009

    @adenosine:
    Vor hundert Jahren konnten die Mathematiker noch sagen: “Mag ja sein, daß die reine Zahlentheorie völlig anwendungsfrei ist, aber dadurch läßt sie sich zumindest nicht für kriegerische Zwecke mißbrauchen.”
    Kaum 40 Jahre später wurden die Künste der Kryptographie und Kryptoanalyse zum Fachgebiet derer, die sich mit Primzahlen auskannten, und sie haben einen Krieg maßgeblich mitentschieden. Die Zahlentheorie hatte ihre Unschuld verloren. Es gab zuvor nicht den geringsten Hinweis darauf, daß dies geschehen könnte. Soviel auch zum Thema “Notwendigkeit der Grundlagenforschung” …

  4. #4 Clint
    15. Februar 2011

    “Ungefähr 1/ln(n) aller Zahlen bis n sind Primzahlen”.

    Ich glaube es sollte n/ln(n) heißen.

  5. #5 Clint
    15. Februar 2011

    Hab mich geirrt, dachte es ist die absolute Anzahl gemeint, hier ist jedoch anscheinend der relative Anteil gemeint.

  6. #6 Thilo
    15. Februar 2011

    Genau. 🙂

  7. #7 shoe heel lift
    https://www.deelsonheels.com/$2099_Dual_Air_Cushioned_Shoe_Lifts/p133745_317500.aspx
    2. April 2013

    Hi I recently love your current amazing article and remember to stick in it