🔢 mathematics

Resolution of Erdős Problem #728: a writeup of Aristotle's Lean proof

Dieses Papier präsentiert die erste vollautonome KI-Lösung des Erdős-Problems #728 unter Verwendung einer Kombination aus GPT-5.2 Pro und dem Aristotle-System, um einen formalen Lean-Beweis zu generieren, der ein logarithmisches Lückenphänomen in der Fakultätsteilbarkeit durch eine neuartige primzahlbasierte Analyse von Binomialkoeffizienten nachweist.

Ursprüngliche Autoren: Nat Sothanaphan

Veröffentlicht 2026-01-27

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Nat Sothanaphan

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das Große Ganze: Ein Team von KI-Mathematikern

Stellen Sie sich den berühmten, im Ruhestand befindlichen Mathematik-Genies Paul Erdős vor, der sein Leben damit verbrachte, eine riesige „To-Do-Liste“ mit ungelösten Rätseln zu hinterlassen. Eines dieser Rätsel, #728, blieb jahrzehntelang unberührt.

Kürzlich hat ein Team, bestehend aus einer superintelligenten KI (GPT-5.2 Pro) und einem spezialisierten Mathematik-Prüfroboter (Aristoteles), es endlich gelöst. Sie haben die Antwort nicht einfach nur erraten; sie haben einen strengen, schrittweisen Beweis erstellt, den ein Computer als zu 100 % korrekt verifizieren kann. Die Autoren dieses Papers übersetzen diesen Computercode lediglich in eine Geschichte, die Menschen lesen können.

Das Rätsel: Der Fakultäts-Balanceakt

Das Problem stellt eine Frage zu Fakultäten (Zahlen wie $5! = 5 \times 4 \times 3 \times 2 \times 1$ ).

Stellen Sie sich vor, Sie haben einen riesigen Haufen Blöcke, die $n!$ repräsentieren. Sie möchten sehen, ob Sie zwei kleinere Türme, $a!$ und $b!$ , und einen dritten kleinen Turm $k!$ bauen können, sodass die beiden kleinen Türme perfekt in den großen passen, ohne dass Blöcke übrig bleiben.

Mathematisch bedeutet das: Teilt $a! \times b!$ die Zahl $n! \times k!$ ohne Rest?

Das Rätsel fragt: Wie groß kann die „Lücke“ ( $k$ ) sein?

Wenn $k$ winzig ist, ist es einfach, die Blöcke einzupassen.
Wenn $k$ riesig ist, ist es meistens unmöglich.
Der Trick besteht darin, eine „Goldlöckchen-Zone“ zu finden, in der $k$ groß genug ist, um interessant zu sein, aber nicht so groß, dass die Blöcke nicht mehr passen.

Das KI-Team hat bewiesen, dass man unendlich viele Situationen finden kann, in denen diese Lücke ( $k$ ) etwa in der Größenordnung des Logarithmus der Gesamtzahl liegt. In einfachen Worten: Wenn Ihre Gesamtzahl an Blöcken eine Million ist, kann die Lücke etwa 14 betragen. Wenn Ihre Zahl eine Milliarde ist, kann die Lücke etwa 20 betragen. Sie wächst sehr langsam, aber sie wächst tatsächlich.

Die Strategie: Das „Übertrag“-Spiel

Um dies zu lösen, mussten die Mathematiker das Problem durch die Linse der Primzahlen (2, 3, 5, 7 usw.) betrachten. Sie verwendeten eine Regel namens Kummerscher Theorem, was wie ein Spiel des „Übertragens“ beim Addieren ist.

Die Analogie: Der überlaufende Eimer
Stellen Sie sich vor, Sie addieren Zahlen in einer bestimmten Sprache (Basis $p$ ).

Wenn Sie zwei Ziffern addieren und das Ergebnis zu groß für einen Platz ist, „tragen“ Sie den Rest an die nächste Stelle über.
Das Ziel: Die KI musste eine Zahl ( $m$ ) finden, die, wenn man sie verdoppelt, viele Überträge verursacht (wie ein Eimer, der wiederholt überläuft).
Das Hindernnis: Gleichzeitig musste die KI sicherstellen, dass die unmittelbar folgenden Zahlen (wie $m+1, m+2...$ ) keine „Spitzen“ aufweisen – also plötzliche, massive Teilbarkeit durch eine Primzahl, die das Gleichgewicht zerstören würde.

Denken Sie an das Gehen auf einem Seil:

Das Seil (die „Übertrag“-Bedingung): Sie müssen eine Zahl wählen, die „übertrag-reich“ ist. Wenn Sie sie verdoppeln, sollte sie ihre Eimer so oft wie möglich überlaufen lassen. Dies erzeugt ein „Sicherheitsnetz“ der Teilbarkeit, das hilft, die Gleichung zu erfüllen.
Die Spitzen (die „schlechte“ Bedingung): Sie müssen Zahlen vermeiden, bei denen die nächsten aufeinanderfolgenden ganzen Zahlen durch riesige Potenzen einer Primzahl teilbar sind. Dies sind „Spitzen“, die Sie vom Seil werfen könnten.

Wie sie die Lösung fanden

Die KI hat nicht einfach eine Zufallszahl gewählt. Sie verwendete ein Zählargument (eine statistische Strategie):

Der Suchbereich: Sie betrachteten einen riesigen Bereich von Zahlen (von $M$ bis $2M$ ).
Der Filter: Sie berechneten, wie viele Zahlen in diesem Bereich „schlecht“ waren (entweder trugen sie nicht genug über oder sie hatten eine Spitze).
Das Ergebnis: Sie bewiesen, dass die Anzahl der „schlechten“ Kandidaten tatsächlich kleiner ist als die Gesamtzahl der Kandidaten in diesem Bereich.
Die Schlussfolgerung: Da es mehr Zahlen als „schlechte“ Zahlen gibt, muss es in dem Haufen mindestens eine „gute“ Zahl geben.

Es ist wie zu sagen: „Wenn Sie ein Glas mit 1.000 Murmeln haben und nur 900 davon rot (schlecht) sind, müssen mindestens 100 blaue (gut) übrig sein.“ Die KI bewies, dass für jedes ausreichend große Glas immer eine „gute“ Murmel existiert.

Warum das wichtig ist (laut dem Paper)

Erster KI-alleiniger Beweis: Dies ist das erste Mal, dass ein KI-System autonom eines der berühmten Probleme von Erdős gelöst und einen formalen Beweis produziert hat, den Menschen verifizieren können.
Die „logarithmische Lücke“: Sie bestätigten, dass die Lücke zwischen den Zahlen logarithmisch sein kann. Während das Paper anmerkt, dass die Lücke potenziell etwas größer sein könnte (wie vom Mathematiker Terence Tao vorgeschlagen), etabliert dieser Beweis eine solide, garantierte Basislinie.
Methodik: Die verwendete Methode (Zählen von Überträgen und Vermeiden von Spitzen) ähnelt Techniken, die Erdős selbst in der Vergangenheit verwendet hat, wird hier jedoch auf ein komplexeres, sich bewegendes Ziel angewendet.

Zusammenfassung

Das Paper ist ein Bericht darüber, wie ein KI-Team ein 40 Jahre altes mathematisches Rätsel gelöst hat. Sie zeigten, dass man immer eine spezifische Menge von Zahlen finden kann, bei denen eine komplexe Fakultätsgleichung perfekt ausbalanciert ist. Dies gelang ihnen, indem sie Zahlen wie Eimer behandelten, die überlaufen (Überträge), und bewiesen, dass man immer einen Eimer finden kann, der gerade genug überläuft, um nützlich zu sein, ohne an den falschen Stellen zu viel zu verschütten.

Technisches Resümee: Lösung des Erdős-Problems #728

Problemstellung
Die Arbeit befasst sich mit dem Erdős-Problem #728, welches die maximale mögliche Größe der Lücke $k := a + b - n$ unter der Bedingung der Fakultäts-Teilbarkeit untersucht:
$a! b! \mid n! (a + b - n)!$
Ohne zusätzliche Einschränkungen existieren triviale Lösungen, bei denen $k$ beliebig groß werden kann (z. B. durch das extrem große Wählen von $a$ und $b$ ). Um das Problem nicht-trivial zu gestalten, legen die Autoren die Bedingung fest, dass $a$ und $b$ von den Extremen ferngehalten werden, spezifisch $\varepsilon n \le a, b \le (1-\varepsilon)n$ für ein $0 < \varepsilon < 1/2$ . Das Ziel ist es zu bestimmen, wie groß $k$ im Verhältnis zu $n$ unter diesen Bedingungen sein kann.

Methodik und Beweisstrategie
Der Beweis erfolgt durch die Transformation der Fakultäts-Teilbarkeitsbedingung in ein Problem über Binomialkoeffizienten und $p$ -adische Valuationswerte.

Reduktion auf Binomial-Teilbarkeit:
Durch Setzen von $n = 2m$ , $b = m$ und $a = m + k$ ist die ursprüngliche Bedingung äquivalent zu:
$\binom{m+k}{k} \mid \binom{2m}{m}$
Dies erfordert den Nachweis, dass für jede Primzahl $p$ die $p$ -adische Valuation der linken Seite kleiner oder gleich der der rechten Seite ist:
$\nu_p\left(\binom{m+k}{k}\right) \le \nu_p\left(\binom{2m}{m}\right)$
Valuationsanalyse mittels Kummer-Theorem:
Unter Verwendung des Kummer-Theorems wird $\nu_p\left(\binom{2m}{m}\right)$ als die Anzahl der Überträge identifiziert, die beim Addieren von $m + m$ in der Basis $p$ auftreten. Der Term $\nu_p\left(\binom{m+k}{k}\right)$ wird durch die maximale Valuation eines beliebigen Terms im aufeinanderfolgenden Block $m+1, \dots, m+k$ , bezeichnet als $V_p(m, k)$ , nach oben begrenzt.
Die zentrale zu erfüllende Ungleichung lautet:
$V_p(m, k) \le \kappa_p(m)$
wobei $\kappa_p(m)$ die Anzahl der Überträge für $m+m$ in der Basis $p$ ist.
Primzahlweise Analyse:
Die Autoren unterteilen die Analyse in zwei Regime basierend auf der Größe der Primzahl $p$ relativ zu $k$ :
- Große Primzahlen ( $p > 2k$ ): In diesem Bereich ist die Ungleichung automatisch erfüllt. Da die Intervalllänge $k$ kleiner als $p/2$ ist, kann höchstens eine Zahl im Block $m+1, \dots, m+k$ durch $p$ teilbar sein. Wenn eine hohe Potenz $p^J$ eine Zahl teilt, erzwingen die Basis- $p$ -Ziffern von $m$ mindestens $J$ Überträge beim Verdoppeln, was die Bedingung erfüllt.
- Kleine Primzahlen ( $p \le 2k$ ): Dies stellt die Hauptschwierigkeit dar. Die Autoren verwenden ein probabilistisches Zählargument, um eine ganze Zahl $m$ $m$ in einem großen Intervall $[M, 2M]$ $[M, 2 M]$ zu finden, die gleichzeitig zwei Bedingungen für alle $p \le 2k$ $p \leq 2 k$ erfüllt:
  - Übertrag-reich (Carry-Rich): Die Basis- $p$ -Entwicklung von $m$ besitzt viele Ziffern $\ge \lceil p/2 \rceil$ in den ersten $L_p$ Positionen. Dies erzwingt eine hohe Anzahl an Überträgen ( $\kappa_p(m)$ ), wenn $m$ verdoppelt wird.
  - Spitzen-frei (Spike-Free): Keine Ganzzahl im Block $m+1, \dots, m+k$ ist durch eine ungewöhnlich hohe Potenz von $p$ teilbar (spezifisch wird $V_p(m, k)$ unter einem Schwellenwert $J_p + t(M)$ gehalten).
Existenz mittels Union-Bound:
Die Autoren definieren "schlechte" Mengen von ganzen Zahlen $m$ , die entweder die Übertrag-Bedingung oder die Spitzen-Bedingung nicht erfüllen. Unter Verwendung von Chernoff-Schranken für die Verteilung großer Ziffern und einfachem Zählen für die Spitzen-Bedingung zeigen sie, dass das Gesamtmaß dieser schlechten Mengen strikt kleiner als die Größe des Intervalls $[M, 2M]$ ist. Folglich existiert ein "gutes" $m$ , das die Teilbarkeitsbedingung für alle relevanten Primzahlen gleichzeitig erfüllt.

Kernergebnisse
Das Paper etabliert Theorem 1 (Logarithmisches Lückenfenster):
Für beliebige Konstanten $0 < C_1 < C_2$ und $0 < \varepsilon < 1/2$ existieren unendlich viele Tripel $(a, b, n) \in \mathbb{N}^3$ mit:

$\varepsilon n \le a, b \le (1-\varepsilon)n$
$a! b! \mid n! (a + b - n)!$
$C_1 \log n < a + b - n < C_2 \log n$

Die Konstruktion liefert eine Lücke $k$ , die logarithmisch mit $n$ wächst. Die Autoren merken an, dass der aktuelle Beweis $k \asymp \log n$ liefert, die Methode jedoch potenziell auf $k = \exp(c\sqrt{\log n})$ erweitert werden könnte, falls weitere Verfeinerungen vorgenommen werden, wobei sich der vorliegende Text auf das logarithmische Regime konzentriert.

Bedeutung und Ansprüche

Erstes KI-gelöstes Erdős-Problem: Die Autoren behaupten, dies sei das erste Erdős-Problem, das "vollständig autonom durch ein KI-System gelöst wurde". Das genutzte System war eine Kombination aus GPT-5.2 Pro und dem Theorembeweiser "Aristotle" von Harmonic.
Formale Verifikation: Der Beweis wurde als formaler Beweis in dem Theorembeweiser Lean generiert und anschließend in die hier präsentierte informelle Mathematik übersetzt.
Methodischer Beitrag: Die Arbeit erweitert frühere Techniken von Erdős und Pomerance bezüglich der Teiler zentraler Binomialkoeffizienten. Im Gegensatz zu früheren Arbeiten, die sich auf "übertrag-arme" ganze Zahlen (wenige Überträge) oder feste Längengrößen konzentrierten, konstruiert dieser Beweis "übertrag-reiche" ganze Zahlen, um ein wachsendes Fenster der Größe $k \asymp \log n$ zu handhaben.
Unabhängigkeit: Die Autoren merken an, dass Carl Pomerance nach ihrer ersten Arbeit unabhängig ähnliche Ergebnisse hergeleitet hat, und dass Modifikationen dieses Arguments zur Lösung der Erdős-Probleme #729 und #401 verwendet wurden.

Das Paper beansprucht nicht, das Problem in seiner absolut stärksten möglichen Form gelöst zu haben (da auf das Potenzial für größere Lücken hingewiesen wird), behauptet aber die erfolgreiche Lösung der spezifischen Frage nach der logarithmischen Lücke, die Erdős gestellt hat.