Ein OpenAI-Modell hat eine zentrale Vermutung der diskreten Geometrie widerlegt

Seit fast 80 Jahren untersuchen Mathematiker:innen eine täuschend einfache Frage: Wenn man $n$ Punkte in der Ebene platziert, wie viele Punktpaare können dann genau den Abstand $1$ voneinander haben?

Dies ist das Problem der Einheitsabstände in der Ebene, das erstmals 1946 von Paul Erdős gestellt wurde. Es ist eine der bekanntesten Fragen der kombinatorischen Geometrie, leicht zu formulieren und bemerkenswert schwer zu lösen. Das Buch Research Problems in Discrete Geometry von Brass, Moser und Pach aus dem Jahr 2005 nennt es „möglicherweise das bekannteste (und am einfachsten zu erklärende) Problem der kombinatorischen Geometrie“. Noga Alon, ein führender Kombinatoriker an der Princeton University, bezeichnet es als „eines von Erdős’ Lieblingsproblemen“. Erdős setzte sogar einen Geldpreis für die Lösung dieses Problems aus.

Heute teilen wir einen Durchbruch beim Problem der Einheitsabstände. Seit Erdős’ ursprünglicher Arbeit war die vorherrschende Auffassung, dass die weiter unten dargestellten „quadratischen Gitter“-Konstruktionen im Wesentlichen optimal seien, um die Zahl der Einheitsabstandspaare zu maximieren. Ein internes OpenAI-Modell hat diese langjährige Vermutung widerlegt und eine unendliche Familie von Beispielen geliefert, die eine polynomielle Verbesserung ergeben. Der Beweis wurde von einer Gruppe externer Mathematiker:innen geprüft. Sie haben außerdem eine Begleitpublikation verfasst, die das Argument erläutert und weiteren Hintergrund sowie Kontext zur Bedeutung des Ergebnisses liefert.

Bemerkenswert ist das Ergebnis auch wegen der Art, wie es gefunden wurde. Der Beweis stammt von einem neuen allgemeinen Reasoning-Modell und nicht von einem System, das speziell für Mathematik trainiert, zum Durchsuchen von Beweisstrategien angeleitet oder eigens auf das Problem der Einheitsabstände ausgerichtet wurde. Im Rahmen eines breiteren Vorhabens, zu testen, ob fortgeschrittene Modelle zur Spitzenforschung beitragen können, evaluierten wir es anhand einer Sammlung von Erdős-Problemen. In diesem Fall erzeugte es einen Beweis, der das offene Problem löst.

Dieser Beweis ist ein wichtiger Meilenstein für die Mathematik- und KI-Community. Er markiert das erste Mal, dass ein bedeutendes offenes Problem, das für ein Teilgebiet der Mathematik zentral ist, autonom von KI gelöst wurde. Er zeigt außerdem, wie tief das Reasoning ist, das diese Systeme inzwischen unterstützen. Die Mathematik bietet ein besonders klares Testfeld für Reasoning: Die Probleme sind präzise, mögliche Beweise können überprüft werden, und ein langes Argument funktioniert nur, wenn das Schlussfolgern von Anfang bis Ende kohärent ist. Auch die Methode, mit der das Problem gelöst wurde, ist bemerkenswert. Der Beweis bringt unerwartete, anspruchsvolle Ideen aus der algebraischen Zahlentheorie bei einer elementaren geometrischen Frage zur Anwendung.

Der Fields-Medaillengewinner Tim Gowers nennt das Ergebnis in der Begleitpublikation „einen Meilenstein der KI-Mathematik“. Laut dem führenden Zahlentheoretiker Arul Shankar „zeigt diese Arbeit meiner Meinung nach, dass aktuelle KI-Modelle über die Rolle bloßer Hilfen für menschliche Mathematiker:innen hinausgehen – sie sind fähig, eigene geniale Ideen zu haben und sie dann erfolgreich umzusetzen“.

Der Beweis ist hier⁠(wird in einem neuen Fenster geöffnet) verfügbar. Die Begleitpublikation führender externer Mathematiker:innen ist hier⁠(wird in einem neuen Fenster geöffnet) verfügbar. Eine gekürzte Version der Gedankenkette des Modells findest du hier⁠(wird in einem neuen Fenster geöffnet).

$u(n)$ soll die größtmögliche Anzahl von Einheitsabstandspaaren unter $n$ Punkten in der Ebene sein. Beispiele mit linearer Wachstumsrate lassen sich leicht konstruieren: Werden $n$ Punkte auf einer Linie platziert, ergibt das $n-1$ Paare, während ein quadratisches Gitter etwa $2n$ Paare ergibt. Die zuvor beste bekannte Konstruktion, die aus einem neu skalierten quadratischen Gitter stammt, liefert noch mehr: $n^{1 + C / \log \log(n)}$ für eine Konstante $C$. Da $\log \log(n)$ mit $n$ gegen unendlich geht, geht der zusätzliche Term im Exponenten gegen $0$, was bedeutet, dass diese Konstruktionen nur geringfügig schneller als linear wachsen. Jahrzehntelang war weithin die Auffassung verbreitet, dass diese Rate im Wesentlichen die bestmögliche sei und keine Konstruktion das quadratische Gitter wesentlich verbessern könne. Technisch formuliert vermutete Erdős eine obere Schranke von $n^{1+o(1)}$, wobei das zusätzliche $o(1)$ einen Term bezeichnet, der mit $n$ gegen $0$ geht.Unser neues Ergebnis widerlegt diese Vermutung. Genauer gesagt konstruiert der Beweis für unendlich viele Werte von $n$ Konfigurationen aus $n$ Punkten mit mindestens $n^{1+\delta}$ Einheitsabstandspaaren für einen festen Exponenten $\delta > 0$. (Der ursprüngliche KI-Beweis gibt kein explizites $\delta$ an, aber eine bevorstehende Verfeinerung von Will Sawin, Mathematikprofessor in Princeton, hat gezeigt, dass $\delta = 0,014$ gewählt werden kann.)

Die Geschichte des Problems hilft zu verstehen, warum das Ergebnis überraschend ist. Die beste bekannte untere Schranke war seit Erdős’ ursprünglicher Konstruktion von 1946 im Wesentlichen unverändert geblieben. Die beste obere Schranke, $O(n^{4/3})$, geht auf Arbeiten von Spencer, Szemerédi und Trotter aus dem Jahr 1984 zurück, und trotz späterer Verfeinerungen und verwandter struktureller Arbeiten von Székely, Katz und Silier, Pach, Raz und Solymosi sowie anderen ist die obere Schranke im Wesentlichen unverändert geblieben. Als Hinweis zugunsten der Vermutung untersuchten Matoušek und Alon-Bucić-Sauermann das Problem mit nicht-euklidischen Abständen in der Ebene und bewiesen, dass „die meisten“ dieser nicht-euklidischen Abstände der Vermutung in gewissem Sinne genügen.Überraschenderweise stammen die Schlüsselbestandteile der Konstruktion aus einem ganz anderen Teilgebiet der Mathematik, der algebraischen Zahlentheorie, die Konzepte wie Faktorisierung in Erweiterungen der ganzen Zahlen untersucht, die als algebraische Zahlkörper bekannt sind.

Auf hoher Ebene beginnt der Beweis mit einer vertrauten geometrischen Idee und treibt sie in eine unerwartete Richtung.

Erdős’ ursprüngliche untere Schranke lässt sich über die gaußschen ganzen Zahlen verstehen: Zahlen der Form $a+bi$, wobei $a$ und $b$ ganze Zahlen sind und $i$ die Quadratwurzel aus $-1$ ist. Die gaußschen ganzen Zahlen erweitern die gewöhnlichen ganzen Zahlen und besitzen wie diese Eigenschaften wie die eindeutige Primfaktorzerlegung. Solche Erweiterungen der gewöhnlichen ganzen Zahlen oder rationalen Zahlen werden algebraische Zahlkörper genannt. Das neue Argument ersetzt die gaußschen ganzen Zahlen durch kompliziertere Verallgemeinerungen aus der algebraischen Zahlentheorie mit reicheren Symmetrien, die viel mehr Differenzen der Länge eins erzeugen können.

Das genaue Argument verwendet Werkzeuge wie unendliche Klassenkörpertürme und die Golod-Shafarevich-Theorie, um zu zeigen, dass die für das Argument benötigten Zahlkörper tatsächlich existieren. Diese Ideen waren algebraischen Zahlentheoretiker:innen gut bekannt, doch es war eine große Überraschung, dass diese Konzepte Auswirkungen auf geometrische Fragen in der euklidischen Ebene haben.

Dieses Ergebnis markiert einen wichtigen Moment in der Wechselwirkung zwischen KI und Mathematik: Ein KI-System hat autonom ein langjähriges offenes Problem gelöst, das im Zentrum eines aktiven Forschungsfelds steht. Es bietet außerdem einen frühen Einblick in eine neue Art der Zusammenarbeit zwischen KI und menschlichen Mathematiker:innen. In diesem Fall zeichnet die Begleitarbeit externer Mathematiker:innen ein deutlich reichhaltigeres Bild als die ursprüngliche Lösung allein.

Wie Thomas Bloom in der Begleitnotiz schreibt:

„Wenn ich die Bedeutung und den Einfluss eines KI-generierten Beweises bewerte, stelle ich mir die Frage: Hat uns das etwas Neues über das Problem gelehrt? Verstehen wir die diskrete Geometrie jetzt besser? Ich denke, die Antwort ist ein vorsichtiges Ja: Das zeigt, dass zahlentheoretische Konstruktionen zu solchen Fragen viel mehr beitragen können, als wir vermutet hatten; außerdem kann die dafür nötige Zahlentheorie sehr tiefgehend sein. Zweifellos werden sich in den kommenden Monaten viele algebraische Zahlentheoretiker:innen andere offene Probleme der diskreten Geometrie genau ansehen.“

Die unerwartete Verbindung zwischen algebraischer Zahlentheorie und diskreter Geometrie, die durch die Lösung sichtbar wird, ist ein Teil dessen, was das Ergebnis bemerkenswert macht. Es widerlegt nicht nur eine bestimmte Vermutung, sondern kann Mathematiker:innen eine Brücke bieten, um weitere verwandte Probleme zu erkunden.

Bloom weist auch auf eine breitere Möglichkeit hin:

„Die Grenzen des Wissens sind sehr zerklüftet, und zweifellos werden die kommenden Monate und Jahre ähnliche Erfolge in vielen anderen Bereichen der Mathematik bringen, in denen langjährige offene Probleme dadurch gelöst werden, dass eine KI unerwartete Verbindungen aufzeigt und den bestehenden technischen Apparat an seine Grenzen bringt. KI hilft uns, das Werk der Mathematik, das wir über Jahrhunderte aufgebaut haben, vollständiger zu erkunden; welche anderen ungesehenen Wunder warten noch im Verborgenen?“

Dieses Ergebnis liefert ein vielversprechendes Beispiel: KI trägt nicht nur eine Lösung bei, sondern eine mathematische Entdeckung, deren Bedeutung durch das anschließende menschliche Verständnis klarer und reichhaltiger wird.

Die zentrale Erkenntnis geht über dieses konkrete Ergebnis hinaus. Besseres mathematisches Reasoning kann KI zu einem stärkeren Forschungspartner machen: zu etwas, das schwierige Gedankengänge verfolgen, Ideen über weit entfernte Wissensgebiete hinweg verbinden, vielversprechende Wege, die Fachleute vielleicht nicht priorisiert hätten, sichtbar machen und Forschenden helfen kann, bei Problemen voranzukommen, die sonst zu komplex oder zu zeitaufwendig wären.

Diese Fähigkeiten sind auch jenseits der Mathematik wichtig. Wenn ein Modell ein kompliziertes Argument kohärent verfolgen, Ideen über weit entfernte Wissensgebiete hinweg verbinden und Arbeit hervorbringen kann, die der Prüfung durch Fachleute standhält, dann sind das auch in Biologie, Physik, Materialwissenschaft, Ingenieurwesen und Medizin nützliche Fähigkeiten, und sie sind Teil unseres längerfristigen Wegs hin zu stärker automatisierter Forschung: Systeme, die Wissenschaftler:innen und Ingenieur:innen helfen können, mehr Ideen zu erkunden und schwierigere technische Fragen zu verfolgen.

KI steht kurz davor, eine sehr ernsthafte Rolle in den kreativen Teilen der Forschung zu übernehmen, und vor allem in der KI-Forschung selbst. Auch wenn dieser Fortschritt nicht unerwartet ist, unterstreicht er die Dringlichkeit, die wir dabei empfinden, diese nächste Phase der KI-Entwicklung, die Herausforderungen bei der Ausrichtung sehr intelligenter Systeme und die Zukunft der Zusammenarbeit zwischen Mensch und KI zu verstehen.

Diese Zukunft hängt weiterhin vom menschlichen Urteilsvermögen ab. Expertise wird wertvoller, nicht weniger wertvoll. KI kann beim Suchen, Vorschlagen und Verifizieren helfen. Menschen wählen die wichtigen Probleme aus, interpretieren die Ergebnisse und entscheiden, welche Fragen als Nächstes verfolgt werden.