Einheitsabstand

Behauptung: KI kann wissenschaftliche Durchbrüche erzielen.

Beweis: Ein internes OpenAI-Modell hat die berühmteste Vermutung der diskreten Geometrie gelöst, nämlich die Optimalität (oder deren Fehlen) des Gitters für das Einheitsabstandsproblem. Diese Vermutung hatte trotz großen Interesses seit ihrer Aufstellung vor 80 Jahren keinerlei Fortschritte gesehen. (Es gab allerdings viel Aktivität und Fortschritt RUNDHERUM!)

Lass mich diesen Thread nutzen, um konkret zu erklären, was passiert ist. Du kannst auch Erklärungen mit unterschiedlichem Komplexitätsgrad in unserem Blogbeitrag, in dem Begleitpapier, das von weltweit führenden Mathematikern verfasst wurde (erscheint später heute auf arxiv), in dem Bericht mit dem ursprünglichen KI-Beweis und in dem (umgeschriebenen) Gedankengang des Modells, das das Problem löst, finden.

Okay, worüber reden wir hier eigentlich: Die Frage ist lächerlich einfach; wenn ich n Punkte in die Ebene setze, wie viele Abstände zwischen diesen Punkten können gleich sein? (Durch Um skalieren kannst du auch einfach fragen, wie viele dieser Abstände gleich 1 sein können, daher der Name „Einheits“-Abstandsproblem.) Nun, du könntest einen Punkt in den Mittelpunkt eines Kreises setzen und alle anderen auf einen Kreis um diesen Punkt, was dazu führen würde, dass n−1 Abstände gleich sind. Und offensichtlich gibt es höchstens n²/2 Abstände. Was ist also die Wahrheit: Ist das Beste, was man erreichen kann, von der Größenordnung n oder von der Größenordnung n²?

Als Erdős das Problem 1946 einführte, analysierte er die natürlichste Konstruktion dafür: Punkte auf ein einfaches Gitter zu setzen. Okay, ein Punkt hat nun 4 Nachbarn auf diesem Gitter, also gibt es sicher mindestens von der Größenordnung 2·n gleiche Abstände (2n und nicht 4n wegen doppelter Zählung). Aber seien wir ein klitzeklein wenig cleverer: Anstatt Knoten im Abstand 1 zu betrachten (sagen wir, das Gitter hat Kanten der Länge 1), könnten wir Knoten betrachten, die den Abstand √5 = √(1+2²) haben. Mach eine kleine Skizze und du wirst sehen, dass es 8 Punkte in diesem Abstand gibt! Tatsächlich bewegst du dich im Grunde entlang einer L-Form, die du beliebig drehen kannst (und es gibt 8 Möglichkeiten, das zu tun). Was Erdős bewies (und ich werde den Beweis unten geben), ist, dass du so in Zweierpotenzen weiter machen kannst, bis etwa u(n) = 2^{log(n)/loglog(n)}. Das bedeutet, das Gitter hat mindestens etwa u(n)·n gleiche Abstände, und tatsächlich ist diese Berechnung optimal für das Gitter. Beachte, dass u(n)·n = n^{1+o(1)} ist (genauer: n^{1+cst/loglog(n)}).

Was Erdős vermutete, ist, dass das Gitter im Wesentlichen optimal ist: Jede Konfiguration von Punkten sollte höchstens n^{1+o(1)} gleiche Abstände haben. Dies ist das Problem, das in den letzten 80 Jahren keinerlei Fortschritte sah, wiederum trotz großen Interesses, angesichts wie grundlegend und natürlich diese Frage ist. Mein Verständnis ist, dass Erdős fest daran glaubte, dass das Gitter optimal ist, und tatsächlich wurde er in dem eng verwandten Problem (im selben Aufsatz von 1946 eingeführt!) der verschiedenen Abstände bestätigt. Das Problem der verschiedenen Abstände ist einfach die gegenteilige Version der Frage, bei der man fragt, was die minimale Anzahl verschiedener Abstände ist, die n Punkte bilden können. Das Gitter liefert n/√(log(n)) verschiedene Abstände, und eine bahnbrechende Arbeit von Guth und Katz vor 10 Jahren zeigte, dass dies tatsächlich im Wesentlichen optimal ist, mit einer unteren Schranke von n/log(n). Mit anderen Worten: Alles deutete darauf hin, dass das Gitter auch ein optimaler Kandidat für das Einheitsabstandsproblem ist.

Hier kommt das interne OpenAI-Modell ins Spiel. Es hat diese lange gehegte Überzeugung tatsächlich STARK widerlegt und eine neue (umwerfende) Konstruktion gefunden, mit einer Anzahl gleicher Abstände von der Größenordnung n^{1+δ} für ein δ>0. Um ein paar Worte darüber zu verlieren, wie dieser Durchbruch vom Modell erzielt wurde, muss ich dir zunächst etwas mehr über Erdős’ Beweis erzählen und woher die 2^{log(n)/loglog(n)} kommt. Es stellt sich heraus, dass die Primzahlen im Hintergrund lauern!

Wir werden zwei Dinge über Primzahlen annehmen: Erstens den Primzahlsatz, der besagt, dass es etwa n/log(n) Primzahlen unterhalb von n gibt (naja, eigentlich brauchen wir eine etwas verfeinerte Version, aber das spielt für das Niveau dieser Darstellung keine Rolle). Zweitens, dass eine Primzahl, die gleich 1 modulo 4 ist, über den gaußschen ganzen Zahlen zerfällt (das sind ganze Zahlen der Form a+ib mit a und b ganze Zahlen), nämlich in diesem Fall p = z \bar{z}. Zum Beispiel 5=(1+2i)(1−2i), und das sollte dich an oben erinnern, als wir 8 Knoten im Abstand √5 = √(1+2²) gezählt haben. Okay, nimm nun die ersten k Primzahlen, die gleich 1 modulo 4 sind, p₁, …, p_k, und betrachte die Zahl R = p₁…p_k = z₁ \bar{z₁} … z_k \bar{z_k}. Der entscheidende Punkt ist, dass wir daraus 2^k gaußsche ganze Zahlen mit dem Betrag √R erhalten, indem wir für jede Primzahl p_i entweder z_i oder \bar{z_i} wählen und dann ihr Produkt bilden (entscheidend ist, dass der Betrag multiplikativ ist und die Konjugation den Betrag erhält). Mit anderen Worten: Wir haben 2^k Punkte im Abstand √R vom Ursprung auf dem Gitter gefunden! (Um genau zu sein, müssen wir auch beweisen, dass diese Punkte verschieden sind, wo die eindeutige Faktorisierung in ℤ[i] wichtig wird, und etwas, das im neuen Beweis entscheidend sein wird, aber das ignorieren wir hier.) Jetzt müssen wir nur noch sehen, wie groß wir k wählen können, während √R < √n bleibt (letzteres ist die Seitenlänge eines Gitters mit n Punkten). Wir haben log(R) = ∑_{i=1}^k log(p_i), was nach dem Primzahlsatz ungefähr ∑_{i=1}^k log(i log(i)) ist, was im Wesentlichen k log(k) ist. Also benötigen wir k log(k) kleiner als log(n), also sollte k etwa log(n)/loglog(n) sein, und wir erhalten das behauptete 2^k = 2^{log(n)/loglog(n)}.

Das obige ein Absatz lange Argument (zugegeben, ein cleveres) ist 80 Jahre lang der Stand der Technik geblieben. Was die KI nun getan hat, ist meiner Meinung nach ziemlich verrückt. Zunächst einmal, wie im Gedankengang zu sehen ist, entschied es fast sofort, die Gitterkonstruktion zu verbessern, was das Gegenteil dessen ist, was die meisten Mathematiker bisher versucht hatten. Nach meinem begrenzten Verständnis ist die Strategie, zu der es kam (und die es perfekt umsetzte), ungefähr so: Wäre es nicht großartig, wenn es mehr Möglichkeiten gäbe, die Primzahlen aufzuteilen? Vielleicht, wenn wir einen anderen Körper als ℚ betrachten würden, einen mit höherem Grad, dann könnte dies funktionieren, wenn die ganzen Zahlen ℤ durch den Ganzheitsring dieses Körpers ersetzt werden? Vielleicht könnten wir statt 2^k ein 2^{f k} erhalten, wobei f der Grad des Körpers ist? Der erste Gedanke wäre, sich Kreisteilungskörper anzusehen, aber das Modell macht das zuerst in seinem Gedankengang und erkennt schnell, dass das nicht funktioniert. Es arbeitet hart weiter und bringt schließlich die Sprache der Ideale ein, wo es nicht‑eindeutige Faktorisierung geben kann, die von einer Klassengruppe behandelt wird. Jetzt musst du anfangen darüber nachzudenken, wie du Körper hohen Grades konstruierst, wobei alle Parameter kontrolliert sind (zuerst die Klassenzahl, aber auch dies wird ein höherdimensionales Gitter sein, also muss es zurück in die komplexe Ebene projiziert werden, und diese Projektion wird ein Kollabieren verursachen, das kontrolliert werden muss, und so weiter). Hier verwendet das Modell einen Hammer aus der Klassenkörpertheorie – die unendlichen Türme von Golod‑Shafarevich. An diesem Punkt ist es wahrscheinlich besser für dich, zum Begleitpapier von tatsächlichen Experten auf diesem Gebiet zu gehen, um weitere Details zu erfahren!

Okay, lass mich einen Schritt zurücktreten: Im Grunde hat die KI ihr umfangreiches Wissen der gesamten Mathematik genutzt, um eine Verbindung zwischen diskreter Geometrie und algebraischer Zahlentheorie zu sehen, und dann konnte sie entscheidend die Argumentation meisterhaft verketten, mit Berechnungen auf Expertenniveau bei jedem Schritt. Es ist wirklich ein bahnbrechendes Ergebnis, aber gleichzeitig ist es auch wahr, dass das Modell keine „neue Mathematik“ „erfunden“ hat (sagen wir, es hat keine alternative Klassenkörpertheorie erfunden, was auch immer das bedeuten würde). Aber das ist der entscheidende Punkt: Allein die Fähigkeit, alle Ergebnisse eines wissenschaftlichen Fachgebiets tief zu kennen und alle bekannten Argumente fachkundig mit der genau richtigen Wahl der Parameter anzuwenden, kann zu einer Unmenge von Durchbrüchen führen, und das ist nicht nur auf Mathematik beschränkt – diese Art von (äußerst) solider Expertenausführung ist das tägliche Brot vieler, vieler wissenschaftlicher Fortschritte.

Abschließend ein Wort dazu, was dies für die Mathematik in Zukunft bedeutet. Das Begleitpapier enthält viele Überlegungen dazu von führenden Mathematikern, also lies besser, was SIE zu sagen haben. Aber eine interessante Sache ist, dass wir den Beweis des Modells NICHT auf arxiv einreichen. Tatsächlich kann kein menschlicher Autor behaupten, im traditionellen Sinne beigetragen zu haben (obwohl es natürlich wirklich die Frucht all der menschlichen Forscher bei OpenAI ist, die dieses erstaunliche Modell geschaffen haben, sowie der Menschheit im Allgemeinen, die Mathematik seit Jahrtausenden entwickelt …). Andererseits geht das Begleitpapier von Menschen über bloße Überlegungen zur Bedeutung des Moments hinaus, es verdaut den Beweis, stellt ihn in einen breiteren Kontext und vereinfacht ihn sogar ein wenig. Während die Gemeinschaft noch viel Arbeit zu tun hat, um sich vollständig an diese neuen Entwicklungen anzupassen, glauben wir, dass dieses Prinzip der Trennung des KI‑Beweises vom menschlichen Verständnis davon ein wichtiges Puzzleteil sein wird.