Amateur löst mit ChatGPT ein Erdős-Problem

• Es gilt nun als akzeptiert, dass ein altes Problem gelöst wurde: Der Minimalwert der Erdős-Summe einer primitive set ist 1, und der Wert nähert sich diesem Grenzwert an, wenn die Elemente gegen unendlich gehen — mit einer von GPT-5.4 Pro erzeugten Lösung
• Die Lösung wurde von Liam Price mit einem einzigen Prompt erhalten und auf erdosproblems.com veröffentlicht; danach erhielt sie durch die Prüfung von Kevin Barreto und Fachleuten schnell große Aufmerksamkeit
• Der Beweis folgte einem anderen Weg als dem üblichen ersten Ansatz und fällt besonders dadurch auf, dass er bekannte Formeln aus einem verwandten Fachgebiet auf unerwartete Weise mit diesem Problem verbindet
• ChatGPTs ursprünglicher Beweis war in der vorliegenden Form sehr roh; erst nachdem Fachleute den Kern herausgearbeitet und verstanden hatten, wurde er in eine kürzere und besser geordnete Fassung gebracht
• Dass ein neuer Ansatz von LLMs bei einem Problem funktionierte, das selbst namhafte Mathematiker nicht lösen konnten, könnte den Blick auf die Struktur großer Zahlen und auf die Zusammenhänge zwischen ähnlichen Problemen verändern

---

Das Problem und der Lösungsansatz

• Eine primitive set ist eine Menge ganzer Zahlen, in der keine Zahl eine andere teilt
  • Erdős definierte dafür die Erdős sum, und er nahm an, dass dieser Wert sinkt, je größer die Zahlen der Menge werden
  • Die Vermutung, dass ihr Minimalwert genau 1 ist und dass sich der Wert diesem Grenzwert nähert, wenn die Elemente der Menge gegen unendlich gehen, blieb lange offen
• Diese Lösung ist das Ergebnis, das Liam Price nach einem einzigen Prompt an GPT-5.4 Pro erhielt und anschließend auf erdosproblems.com veröffentlichte
  • Price kannte die Hintergrundgeschichte des Problems nicht und erhielt, als er probeweise ein Erdős-Problem an die KI gab, eine Lösung, die auf den ersten Blick korrekt wirkte
  • Danach prüfte er sie gemeinsam mit Kevin Barreto, woraufhin kontaktierte Fachleute rasch aufmerksam wurden
• Schon zuvor gab es Berichte darüber, dass KI mehrere Erdős problems gelöst habe, doch Bedeutung und Schwierigkeit dieser Probleme unterscheiden sich stark; als Maßstab für mathematische Leistungsfähigkeit war das unvollständig, und manche Lösungen waren weniger neu, als es zunächst schien
  • Dieses Ergebnis wird anders bewertet, weil es ein Problem betrifft, das selbst renommierte Mathematiker nicht lösen konnten, und weil dafür eine Methode verwendet wurde, die bei Problemen dieses Typs bislang nicht eingesetzt wurde

Warum es anders bewertet wird

• Menschen wählten bei diesem Problem meist einen ähnlichen ersten Ansatz, doch diese LLM-Lösung schlug einen völlig anderen Weg ein
  • Sie griff auf in einem verwandten mathematischen Gebiet gut bekannte Formeln zurück, doch niemand hatte daran gedacht, diese Kombination auf ein solches Problem anzuwenden
• Terence Tao merkte an, das Problem selbst sei möglicherweise einfacher gewesen als gedacht, und beim frühen Zugang habe es eine Art mental block gegeben
• Jared Lichtman erklärte, dass ChatGPTs ursprünglicher Beweis in seiner Rohfassung sehr grob gewesen sei und Fachleute erst herausarbeiten und verstehen mussten, worauf er hinauswollte
  • Inzwischen haben Lichtman und Tao den Beweis zu einer kürzeren Fassung überarbeitet, in der die zentrale Einsicht des LLM klarer hervortritt
• Dieser Sprung könnte zu einer neuen Denkweise über große Zahlen und ihre Struktur führen
  • Für eine endgültige Einschätzung der langfristigen Bedeutung ist es noch zu früh, doch die Methode wird bereits als Unterstützung für die Intuition gesehen, dass ähnliche Probleme als zusammengehörig betrachtet werden können

[GN⁺]

Hacker-News-Kommentare

• https://archive.ph/2w4fi

• Paul Erdős war ein sehr berühmter und ziemlich exzentrischer Mathematiker, der den Großteil des 20. Jahrhunderts erlebte.
  Er hatte die Angewohnheit, an Problemen festzuhalten und sie zu katalogisieren, mit denen Mathematiker sich beschäftigten, und die Schwierigkeitsgrade reichten von heutigem Undergraduate-Hausaufgabenniveau bis hin zu Problemen auf Fields-Medal-Niveau, falls man sie lösen konnte.
  Der gemeinsame Kern dieser Probleme ist, dass einer der klügsten Menschen der letzten 100 Jahre keine sofortige Antwort darauf hatte.
  Heutzutage versucht man, mit LLMs Beweise für solche Probleme zu erzeugen und nutzt sie dabei wie Benchmarks; mit jedem neuen Modell werden ein paar mehr gelöst.

  • Den Reaktionen der Mathematiker nach zu urteilen, wirkt dieser Erdős-Beweis wie ein ziemlich besonderer Meilenstein.
    Mehrere Fachmathematiker hatten sich das Problem schon zuvor angesehen, und es heißt, der entstandene Beweis sei überraschend und elegant gewesen und habe sogar neue Verbindungen aufgezeigt.
    Frühere Erdős-Problemlösungen von ChatGPT waren im Allgemeinen weniger beeindruckend und wirkten eher wie Literatursuche oder wie das Lösen vergleichsweise leichter, aber vernachlässigter Probleme.
    Wenn man den Prompt liest, fragt man sich auch, ob die Formulierung in Richtung unkonventionell ist in Ordnung zum Erfolg beigetragen hat.
    [1] https://chatgpt.com/share/69dd1c83-b164-8385-bf2e-8533e9baba9c
  • Der Artikel behandelt einen Fall, in dem ein bereits bekanntes ungelöstes Problem gelöst wurde, und das gehört natürlich eher zur schwierigeren Kategorie.

• Der tatsächliche Dialog begann mit diesem Prompt.
  Es wurde gesagt, keine Internetrecherche zu machen, sondern für ein Problem aus number theory and primitive sets einen nichttrivialen, neuen und kreativen Beweis oder Gegenbeweis zu entwickeln.
  Verlangt wurde ein vollständiger unconditional proof oder disproof, und es wurde nochmals betont, dass eine solche Behauptung ungewöhnliche und kreative Elemente erfordern könne.
  Dazu stand Thought for 80m 17s.
  https://chatgpt.com/share/69dd1c83-b164-8385-bf2e-8533e9baba9c

  • Mit 5.5 Pro, Extended Thinking ausprobiert, kam nach 17 Minuten heraus,
    dass die vorgeschlagene bound korrekt sei und die Konstante 1 sharp sei,
    und es wurde angeboten, w(a)= 1/alog(a) und uniformly for every primitive A⊂[x,∞), ∑w(a)≤1+O(1/log(x)) zu beweisen.
    Es wurde behauptet, das sei ein stärkeres Ergebnis als das geforderte 1+o(1).
    https://chatgpt.com/share/69ed8e24-15e8-83ea-96ac-784801e4a6ec
  • Bei mir dauerte es mit Pro 20 Minuten.
    https://chatgpt.com/share/69ed83b1-3704-8322-bcf2-322aa85d7a99
    Allerdings verstehe ich nicht genug von Mathematik, um beurteilen zu können, ob das wirklich ein korrekter Beweis ist.
  • Ich habe denselben Prompt auch mit dem free plan ausprobiert, und das Ergebnis war deutlich schlechter.

• Wissenschaftlicher Fortschritt entsteht oft dadurch, dass man eine Technik X aus einem Bereich auf ein Problem Y in einem anderen Bereich anwendet, und LLMs scheinen bei solchen Verbindungen zwischen Fachgebieten stärker zu sein als Menschen.
  Sie kennen viel mehr Theorien und Ansätze, als ein einzelner Mensch wissen kann, und müssen sich keine Sorgen machen, vor Kollegen dumm dazustehen.

  • Genau das ist für mich auch reasoning.
    Die Fähigkeit, Wissen zu verallgemeinern und auf andere Domänen anzuwenden.
  • Ein großer Teil intellektueller Arbeit liegt in Wahrheit näher an intellectual labor und besteht darin, viele Informationen an einem Ort zusammenzuführen.
    Darin sind LLMs viel besser als Menschen, und es wirkt, als hätten Menschen das traditionell oft fälschlich als Kreativität eingeordnet.
  • Ich nutze sie tatsächlich auch auf diese Weise.
    Ich würde nicht behaupten, dass ich damit riesige Durchbrüche erzielt hätte, aber ich hatte schon ein paarmal das Gefühl, Einsichten gewonnen zu haben, die sich zu einem Whitepaper ausarbeiten ließen.
    Schon der Prozess, Korrelationen über mehrere Fachgebiete hinweg zusammenzubringen, ist als LLM-Experiment ziemlich spannend.
  • Die Zivilisation wurde stark durch eine left-brained/sequential/language based Herangehensweise vorangetrieben, und Computer und AI wirken wie deren Höhepunkt.
    Auch ich habe als Kind eher ganze Seiten auf einmal gelesen und bin irgendwann zu einem wortweisen und zeilenweisen Lesen übergegangen, und dieser Modus hat sich verfestigt.
    Während des Studiums gab es eine Zeit, in der sich in meinem mathematischen Fachgebiet eine tiefere, breitere und nichtlineare Wahrnehmung geöffnet hatte, aber ich weiß nicht, ob das linkshirnige Übung war oder ob das rechte Gehirn stärker beteiligt war.
    Bei dieser sequenziellen Denkweise werden uns LLMs klar überholen, und dann frage ich mich, ob Menschen stärker in die verbleibende right-brainness ausweichen müssen oder ob AI auch dort noch schneller ankommen wird.
  • Wer ein typisches Beispiel dafür sehen will, wie Methoden eines Fachgebiets auf ein anderes angewendet werden, sollte nach dem Langlands project schauen.

• AI ist mein liebster seltsamer Kollaborateur.

• Manche Erdős-Probleme werden mit raffinierten Methoden, die erst später entwickelt wurden, im Nachhinein fast trivial.
  Einer meiner Professoren hatte mit Erdős zusammen veröffentlicht und war sehr stolz darauf, dass er ein Erdős-Problem, das eine Zeit lang ungelöst gewesen war, als Quizfrage für Undergraduates stellen konnte.

  • Dazu noch ein Punkt: Diese Probleme wurden bereits fast alle durch LLMs gejagt.
    Deshalb wirkt dieser Fall wie ein Beleg dafür, dass das Modell tatsächlich stärker geworden ist.
    Frühere LLM-Generationen konnten dieses Problem nämlich nicht lösen.
  • Laut Tao wirkt der bisherige Standardansatz für dieses Problem wie eine Sackgasse, ist aber gleichzeitig so naheliegend, dass ihn jeder als ersten Schritt ausprobiert.
    Deshalb wirkt dieses Ergebnis umso hoffnungsvoller.
    Denn dadurch gibt es nun eine neue Angriffsrichtung, die sich auch bei ähnlichen Problemen bewerten lässt.

• An diesem Punkt wäre ein GitHub repo schön, in das man massenhaft ungelöste dry-lab-Probleme legt und dann eine Harness baut, die sie bei jedem neuen Modell alle erneut durchläuft.

  • Tatsächlich betreiben Terence Tao und andere Mathematiker so ein Repository und nutzen es aktiv, um mit LLMs nach Lösungen zu suchen.
    [1] https://github.com/teorth/erdosproblems
  • Das sind buchstäblich die Erdős problems selbst.
    In diesem Beitrag geht es darum, dass eines davon gelöst wurde.

• Als ich die Formulierung las, dass ChatGPTs ursprünglicher Beweis eigentlich ziemlich schlecht war und erst von einem Experten gefiltert werden musste, um zu verstehen, was er sagen wollte, fühlte sich das exakt so an wie das Gefühl, das ich immer beim Lesen mathematischer Arbeiten habe.

• Wenn das ein 60 Jahre altes Problem ist, dachte ich eigentlich, dass es vielleicht indirekt schon gelöst worden war und das Modell nur verschiedene Informationen zusammengeführt hat, um das zu finden.
  Auf der Seite sah es aber so aus, als gäbe es kaum Spuren früherer Diskussionen durch Menschen und nur neuere Kommentare darüber, dass GPT es entdeckt habe, was dieses Gefühl noch verstärkte.
  Bei einem 60 Jahre alten Problem hätte ich erwartet, ältere Diskussionen dazu zu finden, daher frage ich mich, ob ich etwas übersehe.
  Trotzdem ist es eine großartige Entdeckung, und es gibt vermutlich noch weitere Probleme, die sich auf ähnliche Weise mit GPT erneut überprüfen ließen.

• Sowohl Menschen als auch von Menschen gebaute Maschinen lösen Probleme meist auf kumulative Weise.
  Weil man immer weiter auf bestehende Grundlagen aufbaut und das Rad nicht neu erfinden will, gerät man leicht in festgefahrene Denkmuster.
  Deshalb wäre ich nicht besonders überrascht, wenn ein naives LLM einen Ansatz hervorgebracht hat, den Experten nicht ausprobiert hatten.
  In solchen begrenzten Fällen kann ein LLM sehr nützlich sein, um einen anderen Ansatz vorzuschlagen, und es muss dafür nicht einmal richtigliegen; es reicht schon, eine Alternative auf den Tisch zu legen und das Feld aufzurütteln.
  Allerdings weiß ich nicht, welchen praktischen Wert dieses Erdős-Problem eigentlich hat.
  Wenn man fragt, ob das ein Beweis dafür sei, dass LLMs keine nutzlosen Spielzeuge sind, klingt das für mich ein bisschen so, als hätte man 1928 gefragt, ob man Hunderttausende Dollar in Zahlentheorie investieren sollte.
  Die Antwort damals wäre wohl gewesen: Nein, und jetzt raus aus meinem Büro.