Durchbruch enthüllt verborgene Struktur der Primzahlen

 (science.org)
1 Punkte von GN⁺ 2024-08-02 | 1 Kommentare | Auf WhatsApp teilen
  • Ein Preprint von James Maynard und Larry Guth vom 31. Mai schließt bestimmte Ausnahmen von der Riemannschen Vermutung aus und bringt nach Jahrzehnten Fortschritt bei einem 165 Jahre alten Problem, das nach der verborgenen Struktur der Primzahlverteilung sucht
  • Im Mittelpunkt stehen die nichttrivialen Nullstellen der Riemannschen Zetafunktion, die direkt damit zusammenhängen, den Fehler zwischen Gauß’ Schätzung der Anzahl von Primzahlen und der tatsächlichen Primzahlverteilung zu verstehen
  • Computer haben bestätigt, dass mehr als 10 Billionen Nullstellen alle den Realteil 1/2 haben; Mathematiker wollen jedoch keine empirische Überprüfung, sondern einen Beweis, dass andere Positionen unmöglich sind
  • Das Ergebnis senkt die seit Albert Ingham 1940 nicht verbesserte obere Schranke für die Anzahl der Nullstellen auf der 3/4-Linie und durchbricht mit einer Kombination aus analytischer Zahlentheorie und harmonischer Analysis eine alte Barriere
  • Ein vollständiger Beweis der Riemannschen Vermutung ist weiterhin in weiter Ferne, doch die Arbeit könnte zu neuen Werkzeugen führen, um die Anzahl der Primzahlen in kürzeren Intervallen zu schätzen und andere Probleme der Zahlentheorie anzugehen

Die Riemannsche Vermutung als Schlüssel zur Primzahlverteilung

  • Jede natürliche Zahl lässt sich in ein Produkt von Primzahlen zerlegen, die nur durch sich selbst und durch 1 teilbar sind; Mathematiker versuchen seit Langem zu verstehen, wie diese Primzahlen auf der Zahlengeraden verteilt sind
  • Auf den ersten Blick wirken Primzahlen ziemlich zufällig, doch man vermutet darin eine verborgene Struktur
  • Seit 165 Jahren steht die Riemannsche Vermutung im Zentrum der Suche nach dieser Struktur
    • Wenn sie bewiesen wird, könnte sie wie ein Rosetta Stone zur Entschlüsselung der Primzahlen wirken
    • Auf sie ist ein Preisgeld von 1 Million US-Dollar des Clay Mathematics Institute ausgesetzt

Gauß’ Schätzung und die Nullstellen der Zetafunktion

  • Carl Friedrich Gauß erkannte Ende des 18. Jahrhunderts im Alter von 16 Jahren, dass Primzahlen mit wachsender Größe seltener werden, und schätzte, dass die Anzahl der Primzahlen bis X ungefähr wie X / ln X skaliert
  • Diese Schätzung passt sehr gut dazu, dass die tatsächliche Anzahl der Primzahlen in kleinen Schwankungen ober- und unterhalb der Kurve verläuft
  • Bernhard Riemann versuchte 1859, die Differenz zwischen Gauß’ Kurve und der tatsächlichen Primzahlverteilung mithilfe der Riemannschen Zetafunktion zu erfassen
    • Diese Funktion nimmt komplexe Zahlen als Eingabe, die sowohl einen reellen als auch einen imaginären Anteil haben
    • Die Nullstellen der Zetafunktion, an denen die Riemannsche Zetafunktion 0 wird, beschreiben direkt die Fehlerschwankungen um die Gauß-Kurve

Die Einschränkung, die die Riemannsche Vermutung verlangt

  • Die Riemannsche Vermutung sagt voraus, dass — abgesehen von einigen trivialen Lösungen bei negativen Eingaben — alle Nullstellen der Zetafunktion bei Eingaben mit Realteil 1/2 liegen müssen
  • Wenn diese Vermutung wahr ist, sind die Schwankungen in der Anzahl der Primzahlen begrenzt; das bedeutet, dass es auf der Zahlengeraden keine großen Ballungen oder großen Lücken in der Primzahlverteilung gibt
  • Bislang haben Computer mehr als 10 Billionen nichttriviale Nullstellen der Zetafunktion geprüft, und alle lagen exakt auf dem Realteil 1/2
  • Empirische Überprüfung allein reicht jedoch nicht aus
    • Maynard meint, ein Beweis würde nicht nur bestätigen, dass die Aussage wahr ist, sondern verständlich machen, warum sie wahr ist, und dadurch mächtige neue Techniken für den Umgang mit Primzahlen liefern
    • Es gibt noch nicht einmal einen plausiblen Angriffsweg, um die Riemannsche Vermutung zu beweisen

Die schmale Lücke, auf die das neue Ergebnis zielt

  • Da Mathematiker die Riemannsche Vermutung nicht direkt vollständig beweisen können, haben sie das Problem aufgeteilt, indem sie die Bereiche eingrenzen, in denen Nullstellen der Zetafunktion nicht liegen können
  • Nichttriviale Nullstellen der Zetafunktion sind bereits zwischen 0 und 1 eingeschlossen
  • Außerdem gibt es eine Spiegelsymmetrie um 1/2: Schließt man Nullstellen bei 3/4 aus, sind auch Nullstellen bei 1/4 ausgeschlossen
  • Bisherige Techniken funktionierten besser zwischen 1/2 und 3/4 oder zwischen 3/4 und 1; die Möglichkeit blieb jedoch bestehen, dass sich viele Nullstellen bei 3/4 verbergen
  • Die beste obere Schranke für die Anzahl der Nullstellen, die bei 3/4 liegen könnten, stammte aus einem Ergebnis des britischen Mathematikers Albert Ingham aus dem Jahr 1940, und niemand konnte sie seither verbessern

Maynards und Guths Ansatz

  • Maynard ist auf analytische Zahlentheorie spezialisiert und erhielt 2022 die Fields-Medaille; im vergangenen Jahrzehnt dachte er jeden Freitagnachmittag immer wieder über dieses Problem nach, ohne Fortschritte zu erzielen
  • Auf einer Tagung der American Mathematical Society im Jahr 2020 bat Maynard Larry Guth vom MIT, einen Spezialisten für harmonische Analysis, um Hilfe
    • Harmonische Analysis nutzt Ideen aus der Physik und umfasst Techniken, die damit verwandt sind, Klänge in ihre Bestandteile zu zerlegen
    • Auch Guth arbeitete mehrere Jahre an dem Problem und fand kurz davor, aufzugeben, gemeinsam mit Maynard den Durchbruch
  • Die beiden liehen sich Strategien aus ihren jeweiligen mathematischen Sprachen, tauschten bis spät in die Nacht Ideen per E-Mail aus und durchbrachen auf unkonventionelle Weise Inghams obere Schranke

Mögliche Auswirkungen auf die gesamte Zahlentheorie

  • Maksym Radziwill bewertet die Arbeit als die erste neue Idee seit 50 Jahren bei der Suche nach Nullstellen der Zetafunktion und glaubt, dass ein lange vernachlässigter Bereich wieder in Bewegung kommen könnte
  • Die verbesserte obere Schranke hilft kaum beim vollständigen Beweis der Riemannschen Vermutung, könnte aber die Zahlentheorie insgesamt beeinflussen
    • Mathematiker können die Anzahl der Primzahlen in kürzeren Intervallen besser schätzen
    • Radziwill meint, die neue Strategie könne helfen, seine frühere Arbeit zu dynamischen Systemen zu vereinfachen
    • Auch beim Kakeya-Problem könnte sie helfen
    • Guth ist daran interessiert, diese Ideen zu nutzen, um die tiefe Beziehung zwischen der Physik von Wellen und der Verteilung von Zahlenmengen zu erkunden

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-08-02
Hacker-News-Kommentare

  • Das stammt aus dem Mai, und Quanta hat bereits einen besseren Artikel dazu veröffentlicht, der auch hier diskutiert wurde.
    https://www.quantamagazine.org/sensational-proof-delivers-ne...

  • Man stelle sich vor, diese Entdeckung führte zu einem größeren Durchbruch bei Primzahlen, sodass die Primfaktorzerlegung großer ganzer Zahlen leicht würde und Public-Key-Kryptografie wie RSA über Nacht wirkungslos wäre.
    Wenn jeder mit einer Consumer-CPU Schlüssel in realer Einsatzgröße knacken könnte: Hat die Branche einen Disaster-Recovery-Plan für so einen Fall? Könnten große Anbieter schnell auf andere, nicht gebrochene Kryptosysteme umstellen? Für Jailbreak-Entwickler, Konsolen-Modder und die „Gerätefreiheit“-Fraktion wäre das ein himmlischer Tag, aber die Gesamtfolgen wären wohl katastrophal und kaum abschätzbar.
    Ich frage mich, ob die Branche plötzliche Durchbrüche in der Zahlentheorie nicht als mögliches Ereignis betrachtet.

    • Bei RSA ist so etwas schon mehrfach passiert.
      Es gab eine Zeit, in der die US-Regierung den Export langer RSA-Schlüssel beschränkte, und zeitweise nutzten große Teile der Welt 128-Bit-RSA-Schlüssel, bevor man wegen der Dixon-Methode hastig auf 512-Bit-Schlüssel umzog. Später ging es wegen des Special Number Field Sieve hastig auf 1024 Bit und wegen des General Number Field Sieve erneut auf 2048 Bit hoch; das ist relativ gesehen auch noch gar nicht so lange her.
      Wenn man sich RSA-Verschlüsselungshardware aus den 80ern ansieht, gibt es Geräte, die stolz damit werben, 512 Bit zu verarbeiten. Heute sind sie nutzlos.
      https://people.csail.mit.edu/rivest/pubs/pubs/Riv84.pdf
      Die Komplexitätsformeln des Special/General Number Field Sieve unterscheiden sich nur um ein paar Konstanten; bei diesen Konstanten frage ich mich, ob sie wirklich wie fundamentale Grenzen wirken. Es fällt mir schwer zu glauben, dass es keine Methode geben sollte, diese Konstanten weiter zu senken und sogar 2048-Bit-Schlüssel nutzlos zu machen.
      Man muss nicht fragen: „Was passiert, wenn RSA gebrochen wird?“ Nachdem wir so etwas mehrfach erlebt haben, kann ich sofort sagen: Man würde wieder hektisch die Schlüssellängen erhöhen und alle potenziell kompromittierten Daten auditieren.
    • Wenn ein Verfahren entdeckt würde, mit dem sich große ganze Zahlen auf Consumer-Hardware leicht faktorisieren lassen, wäre das sehr schmerzhaft, weil RSA einer der wichtigsten Public-Key-Algorithmen ist.
      Bevor man sich aber Sorgen macht, sollte man bedenken, dass RSA bisher 47 Jahre aktiver Kryptoanalyse überstanden hat. In dieser Zeit wurden viele alternative Algorithmen als überlegen vorgeschlagen, doch viele davon wurden kurz darauf gebrochen.
      Die Bewegung hin zu elliptischen Kurven ist vor allem dadurch motiviert, dass Computer Ver- und Entschlüsselung damit leichter verarbeiten können.
      Wenn ich persönlich Geld darauf setzen müsste, welcher Public-Key-Algorithmus in zehn Jahren noch existiert, würde ich auf RSA setzen.
    • An diesem Punkt scheint die Verschiebung hin zu elliptischen Kurven ins Spiel zu kommen, und sowohl bei Signaturen als auch bei Handshakes (Diffie-Hellman) ist das offenbar schon ziemlich weit fortgeschritten.
      Disaster Recovery wäre sicher keine Sache von einer Minute, aber wenn RSA/DH über Nacht unsicher würden, hieße das wohl nicht, dass plötzlich alles unverändert offen daliegt. Auch meine SSH-Schlüssel sind inzwischen ein Mix aus mehreren Verfahren.
    • Die Branche war nicht einmal auf ein schlechtes CrowdStrike-Update vorbereitet, hat es aber nach ein paar Tagen trotzdem wieder in den Griff bekommen.
      Die Fähigkeit, katastrophale Szenarien vorzubereiten, wird wohl überschätzt, die Fähigkeit zu überleben dagegen unterschätzt.
    • Es gibt die Sichtweise, dass die Entdeckung schneller Faktorisierung extrem unwahrscheinlich ist. So nach dem Motto: Sehr viele kluge Leute haben sich das angesehen, also ist es derzeit vermutlich unmöglich – aber genau diese Erzählung könnte selbst eine Schwäche sein.
      Dieses Risiko ist so real wie das Risiko, dass ein massiver Sonnensturm das Stromnetz lahmlegt und es wegen Verzögerungen bei der Transformatorenherstellung und fehlender Vorräte eine mehrjährige Wiederherstellungsphase wie in der Steinzeit gibt. Aus dieser Perspektive wirkt es aber zu klein und theoretisch, um viel Zeit darauf zu verwenden.
      Was Planung angeht, weiß ich nicht, ob ein einfacher Wechsel zu ECC wirklich so leicht ist. Die tatsächliche asymmetrische Verschlüsselung bei ECC hängt von einem gemeinsamen Geheimnis ab; wenn man annimmt, dass RSA gebrochen ist und der Austauschkanal nicht sicher ist, könnte ECC anfälliger für Man-in-the-Middle-Angriffe sein als RSA. Das scheint kein einfacher Austausch zu sein.
      Unabhängig davon könnte RSA bereits gebrochen sein und die Lösung von Kryptoanalysebehörden geheim gehalten werden. Für sie wäre es sehr verlockend, einen Durchbruch zu verbergen, und sie könnten versuchen, Wege zu finden, einen „plötzlichen Durchbruch in der Zahlentheorie“ zu unterdrücken.

  • Die Leute denken immer, die Struktur der Primzahlen sei komplex, aber tatsächlich ist sie meiner Ansicht nach nur eine rekursive Struktur von Abstandsgrößen, die von Vielfachen der vorherigen Abstände nicht erreicht werden
    Es wird dadurch nicht leicht, sie „vorherzusagen“, ohne alle früheren Abstände zu verfolgen, aber im Kern ist es keine komplexe Struktur. Interessant ist, dass eine so einfache Struktur so schwer zu erfassen ist. Ähnlich wie die 3n+1-Folge Komplexität hervorbringt oder die logistische Abbildung komplex wird, sobald sie einen Schwellenwert überschreitet

    • Ein Generator, der „alle Primzahlen“ erzeugt, ist ziemlich einfach und deterministisch
      Wenn man aber nur die Primzahl n gegeben hat und die nächste Primzahl erhalten will, muss man nichttriviale Reste neu berechnen; die binäre Darstellung der Zahl n enthält daher nicht genug Information, um schnell zu beantworten, was die nächste Primzahl ist. Zuerst muss man einige Referenzpunkte vorab berechnen. Am Ende steckt also doch mehr Komplexität darin, aber es bleibt trotzdem eher einfach und offensichtlich und ist nicht einmal ein Problem, das in NP fallen würde
    • Ach ja, stimmt. Nichts ist so einfach, wie die Grundlagentheorie für Zahlentheorie zu liefern, eines der strengsten und intellektuell einschüchterndsten Gebiete der Mathematik /s
    • Ich frage mich, warum das nicht als gelöstes Problem gilt
      https://en.wikipedia.org/wiki/Information_theory
      https://en.wikipedia.org/wiki/Computational_irreducibility
      https://en.wikipedia.org/wiki/Aperiodic_tiling

  • Die Stelle „In eigens reservierten Denksitzungen am Freitagnachmittag kehrte er im Lauf des vergangenen Jahrzehnts immer wieder zu diesem Problem zurück, aber ohne Ergebnis“ ist ermutigend

    • Ich erinnere mich, dass auch Richard Hamming sich den Freitagnachmittag für tiefes, großes Nachdenken freigehalten hat. Eine großartige Methode

  • Wenn man die Gauss-Kurve und die Riemann-Kurve in einem bestimmten Raum zeichnet, sieht man etwas noch Magischeres
    Um zu sehen, was mit trivialen und nichttrivialen Nullstellen gemeint ist, kann man sich diese Wikipedia-Animation ansehen: [https://en.wikipedia.org/wiki/File:Riemann3d_Re_0.1_to_0.9_I...](https://en.wikipedia.org/wiki/File:Riemann3d_Re_0.1_to_0.9_Im_1_to_51.ogg)
    Im Grunde deutet das meiner Ansicht nach darauf hin, dass es zwischen reellen und imaginären Zahlen noch eine weitere Beziehung gibt, die wir noch nicht entdeckt haben
    Und da Riemannsche Mathematik in der Quantenmechanik eine Rolle spielt, hat das auch Implikationen für die Suche nach einer Gravitationstheorie
    Dass Primzahlen an einer Gravitationstheorie beteiligt sind oder sein könnten, fühlt sich wie seltsame Wissenschaft an

  • Ich frage mich, was mit der Formulierung „Sie machten schließlich einige unorthodoxe Züge, um Inghams Schranke zu durchbrechen“ gemeint ist
    Warum ist es unorthodox, Methoden aus einem anderen Bereich zu übernehmen? Aus Ingenieurssicht ist das eher üblich. Harmonische Analysis ist ein grundlegendes Werkzeug in vielen Bereichen wie Audio, Wellen, elektrischer Analyse und Statistik, und ihre Algorithmen sind intern ebenfalls reine Mathematik
    Wenn man in irgendeinem Basissystem wiederkehrende Strukturen finden will, ist es doch normal, verschiedene Darstellungstechniken auszuprobieren und diejenige zu wählen, die am besten zum Problem passt

    • Das Zitat liest sich nicht so, als bestünde das Unorthodoxe an dem Ansatz lediglich darin, Ideen der harmonischen Analysis zu verwenden. Harmonische Analysis in der Zahlentheorie zu nutzen, ist überhaupt nichts Neues
      In der ersten Vorlesung zur analytischen Zahlentheorie ist die zentrale Idee, und auch die zentrale Idee von Riemanns berühmter Arbeit von 1859, im Grunde „harmonische Analysis“. Dass Riemann ein Pionier dieses Gebiets war, ist also kein Zufall: https://old.reddit.com/r/math/comments/16bh3mi/what_is_the_b...
      Auch die derzeit heißeste große Strömung in der Zahlentheorie ist im Kern „höherdimensionale“ harmonische Analysis über Zahlkörpern: https://en.wikipedia.org/wiki/Automorphic_form, https://en.wikipedia.org/wiki/Langlands_program. Der eindimensionale Fall, den das Langlands-Programm verallgemeinern will, ist https://en.wikipedia.org/wiki/Tate%27s_thesis, auch „Fourier-Analysis über Zahlkörpern“ genannt, und eine der wichtigsten Ideen der Zahlentheorie des 20. Jahrhunderts
      In den Referenzen des Guth-Maynard-Papers findet sich auch das Buch von 1994: H. Montgomery, Ten Lectures On The Interface Between Analytic Number Theory And Harmonic Analysis, No. 84. American Mathematical Soc., 1994. Schon 1994 gab es genug Berührungspunkte für zehn Vorlesungen, und nach der Zahl der Zitationen dieses Buches zu urteilen gab es noch viel mehr. Ich habe dieses Buch ebenfalls in mehr als der Hälfte meiner Arbeiten zitiert
      Überraschend ist nicht die Tatsache an sich, dass harmonische Analysis verwendet wurde, sondern wo und wie sie angewandt wurde. Das ist der Teil, der sich einem breiten Publikum wirklich unmöglich vermitteln lässt, daher möchte ich dem Autor des Artikels keinen Vorwurf machen
      Es klingt ein wenig wie „Warum ist es überraschend, Verbindungen herzustellen?“, aber Durchbrüche entstehen oft aus neuen Verbindungen, und nur weil solche Durchbrüche gelegentlich vorkommen, heißt das nicht, dass neue Verbindungen nicht überraschend wären
    • „Unorthodox“ ist vielleicht etwas stark formuliert, aber gemeint ist wohl, dass bestehende Techniken aus einem anderen Gebiet auf neue Weise angewandt wurden
      In der Mathematik entstehen recht häufig große Durchbrüche dadurch, dass jemand Parallelen zwischen zwei scheinbar nicht zusammenhängenden Bereichen erkennt und Ideen aus einem Bereich als Einsicht für einen anderen nutzt
      Der schwierige Teil ist, dass solche Verbindungen zwischen Gebieten normalerweise nicht offensichtlich sind. Die Ähnlichkeit zu erkennen, kann einen erheblichen gedanklichen Sprung erfordern
    • Eine etwas komische Formulierung. Der Journalist hat eben journalistisch geschrieben
      Man könnte auch sagen, dass in jeder mathematischen Entdeckung bis zu einem gewissen Grad ein „unorthodoxer“ Zug steckt. Orthodox ist schließlich nur alles, was bisher bekannt ist

  • Bei der Aussage „Auf den ersten Blick wirkt es ziemlich zufällig. Aber tatsächlich geht man davon aus, dass es in den Primzahlen eine solche verborgene Struktur gibt“ frage ich mich, wie ein hypothetisches Primzahlmuster aussehen würde.
    Erwartet man so etwas wie eine geschlossene Formel? Wenn die Riemannsche Vermutung bewiesen würde, was wäre dann der nächste Schritt, um die Verteilung zu verstehen? Oder erwartet man, dass der Beweis selbst diese Antwort enthält?

  • Jedes Mal, wenn ich von James Maynard höre, festigt sich bei mir der Eindruck, dass er ein Genie ist, wie es nur einmal pro Generation vorkommt.
    Er hat bereits so viel zur Primzahltheorie beigetragen, dass ich das Gefühl bekomme, ein Beweis der Riemannschen Vermutung könnte noch zu meinen Lebzeiten erscheinen.

  • Ich sehe diese Darstellung zum ersten Mal, und sie ist so fesselnd, dass ich neugierig bin. Sind die Muster, die entstehen, wenn man Primzahlen als Polarkoordinaten-Graph zeichnet, eine neuere Entdeckung, oder sind sie schon lange bekannt und werden hier nur als Illustration verwendet? Mich interessieren Name und Geschichte.

  • Das geht etwas am Thema vorbei, aber dieser Satz erinnert mich an einen Aspekt von automatischen Beweisern, bei dem wir vielleicht noch gar nicht angefangen haben, darüber nachzudenken:
    „Der Mathematiker Alex Kontorovich von der Rutgers University sagt: ‚Das ist ein sensationeller Durchbruch. In diesem Beweis stecken jede Menge neuer Ideen, die die Leute in den kommenden Jahren ausgraben werden.‘“
    Der Beweis von etwas ist oft interessanter als neue Perspektive auf den Gegenstand als nur als Mittel, Strenge herzustellen. Ich frage mich, ob es in der automatisierten Mathematik Arbeiten in diese Richtung gegeben hat.