🔢 mathematics

Dead ends in square-free digit walks

Diese Arbeit beweist, dass die asymptotische Dichte von „Sackgassen“ in quadratfrei-zifferbasierten Gängen etwa $1,317 \times 10^{-9}$ beträgt, was etwa 40.000 Mal kleiner ist als von stochastischen Modellen vorhergesagt, und etabliert einen geschlossenen Ausdruck für diese Dichten über alle Basen hinweg unter Verwendung eines Ergebnisses, das durch das AxiomProver-System vollständig in Lean/Mathlib formalisiert wurde.

Ursprüngliche Autoren: Evan Chen, Chris Cummins, Ben Eltschig, Dejan Grubisic, Leopold Haller, Letong Hong, Andranik Kurghinyan, Kenny Lau, Hugh Leather, Seewoo Lee, Aram Markosyan, Ken Ono, Manooshree Patel, Gaurang Pendha

Veröffentlicht 2026-02-09

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Evan Chen, Chris Cummins, Ben Eltschig, Dejan Grubisic, Leopold Haller, Letong Hong, Andranik Kurghinyan, Kenny Lau, Hugh Leather, Seewoo Lee, Aram Markosyan, Ken Ono, Manooshree Patel, Gaurang Pendharkar, Vedant Rathi, Alex Schneidman, Volker Seeker, Shubho Sengupta, Ishan Sinha, Jimmy Xin, Jujian Zhang

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 Spiel: „Quadratfreie Digitenzuwendung“

Stellen Sie sich vor, Sie spielen ein Spiel mit Zahlen. Sie beginnen mit einer Zahl, die „quadratfrei“ ist.

Was ist quadratfrei? Es ist eine Zahl, die keine perfekte Quadratzahl als Teiler in sich verbirgt (außer der 1). Zum Beispiel ist 10 quadratfrei (es ist $2 \times 5$ ), aber 12 ist es nicht (es ist $4 \times 3$ , und 4 ist ein Quadrat).
Der Zug: Sie versuchen, „bis zur Unendlichkeit zu wandern“, indem Sie am Ende Ihrer Zahl immer eine weitere Ziffer anhängen. Wenn Sie die Zahl 5 haben, können Sie versuchen, 50, 51, 52, ..., bis 59 zu bilden.
Die Regel: Jede neue Zahl, die Sie erstellen, muss ebenfalls quadratfrei sein. Wenn Sie eine Zahl erstellen, die nicht quadratfrei ist, ist dieser spezifische Pfad eine „Sackgasse“.

Die große Frage: Können Sie ewig weiterwandern? Gibt es eine Startzahl und eine Folge von Ziffern, die Sie wählen können, sodass Sie niemals auf eine Sackgasse stoßen und so bis zur Unendlichkeit wandern können?

Die alte Vermutung: „Die Münzwurf-Theorie“

Vor dieser Arbeit betrachteten Mathematiker (speziell Miller et al.) dieses Problem mithilfe eines „stochastischen“ oder zufälligen Modells. Sie behandelten die Quadratfreiheit wie einen Münzwurf.

Etwa 60 % aller Zahlen sind quadratfrei.
Sie stellten sich vor, dass Sie bei jedem Schritt eine Wahrscheinlichkeit von 60 % haben, eine „sichere“ Ziffer anzuhängen.
Da Sie 10 Ziffern zur Auswahl haben, berechneten sie, dass die Chancen, steckenzubleiben (eine Sackgasse zu finden), sehr gering sind.
Ihre Vorhersage: Sie glaubten, dass Sackgassen selten sind und etwa 52 Mal pro Million Zahlen vorkommen. Sie glaubten, dass unendliche Wanderungen fast garantiert seien.

Die Neuentdeckung: „Die arithmetische Falle“

Diese Arbeit beweist, dass die „Münzwurf-Theorie“ falsch ist. Die reale Welt der Zahlen ist viel hartnäckiger als ein zufälliger Münzwurf.

Die Autoren (eine Mischung aus menschlichen Mathematikern und einem KI-Tool namens AxiomProver) entdeckten, dass Sackgassen tatsächlich extrem selten sind – etwa 1 zu einer Milliarde.

Warum der Unterschied?
Das „Münzwurf“-Modell ging davon aus, dass die Gründe für das Scheitern unabhängig voneinander sind. Es dachte, dass das Scheitern aufgrund der Ziffer „0“ nichts damit zu tun hat, dass man aufgrund der Ziffer „1“ scheitert.

In der Realität erzeugen die Regeln der Arithmetik eine enge Falle.

Die Analogie: Stellen Sie sich vor, Sie versuchen, eine Tür mit 10 verschiedenen Schlüsseln zu verschließen. Die alte Theorie dachte, jeder Schlüssel hätte eine 6er-Chance von 60 %, unabhängig zu funktionieren.
Die Realität: Die „Schlösser“ (Primusquadrate wie $4, 9, 25, 49$) sind sehr wählerisch. Damit eine Zahl für alle 10 Ziffern gleichzeitig scheitert, muss sie eine sehr spezifische, komplexe Menge von Bedingungen erfüllen, die viele verschiedene Primzahlen gleichzeitig involviert.
Da diese Bedingungen so spezifisch und voneinander abhängig sind, ist es unglaublich schwierig, eine Zahl zu finden, die für jede mögliche nächste Ziffer scheitert. Die „Sackgassen“ sind so selten, dass das Zufallsmodell die Häufigkeit massiv überschätzt hat.

Das Ergebnis: Eine neue Formel

Die Arbeit liefert eine präzise mathematische Formel (einen „geschlossenen Ausdruck“), um genau zu berechnen, wie selten diese Sackgassen für jede Basis (nicht nur für Basis 10) sind.

Für die Basis 10 ist die wahre Dichte der Sackgassen etwa $1,3 \times 10^{-9}$ .
Das ist etwa 40.000 Mal kleiner als die alte Vorhersage.

Der „KI“-Twist: AxiomProver

Ein einzigartiger Teil dieser Arbeit ist die Art und Weise, wie die Mathematik gemacht wurde.

Die Autoren haben den Beweis nicht einfach von Hand geschrieben. Sie nutzten ein KI-Tool namens AxiomProver.
Sie fütterten die KI mit einer Beschreibung des Problems in natürlicher Sprache: „Finde die Dichte der Sackgassen in quadratfreien Digitenzuwendungen.“
Die KI hat nicht nur geraten; sie leitete die Formel ab und schrieb einen formalen Beweis in einer Computersprache namens Lean.
Der Computer hat den Beweis dann Schritt für Schritt verifiziert, um sicherzustellen, dass er zu 100 % logisch korrekt ist.
Die menschlichen Autoren nahmen dann diesen computergenerierten Beweis und schrieben diese Arbeit, um sie anderen Menschen zu erklären.

Eine Anmerkung zur Geschichte (Das „Update“)

Die Arbeit enthält ein wichtiges Update: Nachdem sie ihre Arbeit veröffentlicht hatten, erfuhren sie, dass ein Mathematiker namens Mirsky genau dieses Problem bereits im Jahr 1947 gelöst hatte.

Die Arbeit von Miller et al. aus dem Jahr 2024 (die die „Münzwurf“-Debatte startete) hatte vergessen, Mirskys Arbeit von 1947 zu zitieren.
Obwohl die Mathematik in dieser Arbeit korrekt ist und der KI-Beweis eine coole neue Errungenschaft darstellt, ist das Ergebnis selbst nicht neu in der Geschichte der Mathematik. Die Autoren entschieden sich gegen eine Veröffentlichung in einem Fachjournal, da die Antwort bereits bekannt war, aber sie teilen es, um zu zeigen, wie gut ihr KI-Tool alte Mathematik wiederentdecken kann.

Zusammenfassung

Das Spiel: Kann man unendlich viele Ziffern anhängen, ohne auf eine nicht-quadratfreie Zahl zu stoßen?
Die alte Sicht: Ja, fast sicher. Sackgassen sind selten (1 zu 20.000).
Die neue Sicht: Sackgassen sind super selten (1 zu einer Milliarde), weil die Regeln der Mathematik strenger sind als der Zufall.
Die Methode: Ein KI-Tool namens AxiomProver konnte erfolgreich die korrekte Formel ableiten und sie beweisen, wodurch ein Ergebnis aus dem Jahr 1947 wiederentdeckt wurde.

Technische Zusammenfassung: Sackgassen in quadratfreien Ziffer-Wegen

Problemstellung
Die Arbeit untersucht das Vorhandensein und die Dichte von „Sackgassen“ (Dead Ends) in quadratfreien Ziffer-Wegen. Ein quadratfreier Weg in der Basis $b$ beginnt mit einer quadratfreien Ganzzahl $N_0$ und versucht, eine unendliche Sequenz $N_0, N_1, N_2, \dots$ zu konstruieren, wobei jeder nachfolgende Term durch Anhängen einer Ziffer $d \in \{0, \dots, b-1\}$ gebildet wird, sodass $N_{k+1} = bN_k + d$ quadratfrei bleibt.

Eine positive Ganzzahl $N$ wird als Sackgasse definiert, wenn:

$N$ quadratfrei ist.
Für jede Ziffer $d$ in der Basis die Erweiterung $bN + d$ nicht quadratfrei ist.

Die zentrale Frage, die von Miller et al. [5] aufgeworfen wurde, ist, ob unendliche quadratfreie Wege existieren. Während ein stochastisches Modell (das „Blind Unlimited Model“) nahelegt, dass unendliche Wege mit einer Wahrscheinlichkeit nahe 1 existieren (was impliziert, dass Sackgassen selten sind, mit einer asymptotischen Dichte von $\approx 5,218 \times 10^{-5}$ in Basis 10), analysiert diese Arbeit rigoros die tatsächliche arithmetische Dichte von Sackgassen, um zu bestimmen, ob die stochastische Vorhersage hält.

Methodik
Die Autoren verwenden eine Kombination aus elementärer multiplikativer Zahlentheorie und dem Prinzip des Inklusions-Exklusions-Verfahrens, wobei sie die probabilistischen Annahmen des stochastischen Modells vermeiden.

Indikatorfunktionen: Das Problem wird unter Verwendung der Möbius-Funktion $\mu(n)$ umformuliert. Da $\mu(n)^2$ die Indikatorfunktion für quadratfreie Ganzzahlen ist, lässt sich der Indikator für eine Sackgasse $N$ wie folgt ausdrücken:
$\mathbb{1}_{N \text{ ist Sackgasse}} = \mu(N)^2 \prod_{d \in D} (1 - \mu(bN + d)^2)$
wobei $D$ die Menge der Ziffern ist.
Inklusion-Exklusion: Das Produktglied wird zu einer Summe über alle Teilmengen $S$ der Ziffernmenge expandiert. Dies transformiert die Zählfunktion $D_b(X)$ (die Anzahl der Sackgassen $\le X$ ) in eine alternierende Summe von Zählfunktionen $Q_S(X)$ , wobei $Q_S(X)$ die Anzahl der Ganzzahlen $n \le X$ zählt, für die sowohl $n$ als auch alle Erweiterungen $bn+d $(für$ d \in S$) quadratfrei sind.
Siebanalyse: Für eine feste Teilmenge $S$ wird die Bedingung, dass $n$ und $bn+d$ quadratfrei sind, primweise analysiert. Die Autoren definieren „schlechte“ Restklassen modulo $p^2$ , die vermieden werden müssen. Unter Verwendung des Chinesischen Restsatzes bestimmen sie die Dichte von Ganzzahlen, die diese Klassen vermeiden.
- Für große Primzahlen $p$ (wobei $p \nmid b$ ) erzwingt die Bedingung $p^2 \mid (bn+d)$ die Einordnung von $n$ in eine einzige Restklasse modulo $p^2$ . Entscheidend ist, dass eine einzelne Primzahlquadrat höchstens eine Ziffererweiterung gleichzeitig blockieren kann.
- Die Dichte wird als unendliches Produkt (Euler-Produkt) lokaler Faktoren $(1 - \nu_{p,b}(S)/p^2)$ ausgedrückt, wobei $\nu_{p,b}(S)$ die Anzahl der verbotenen Restklassen modulo $p^2$ zählt.
Fehlertermkontrolle: Der Beweis kontrolliert sorgfältig die Fehlerterme, die durch das Abschneiden des Siebs bei einem Parameter $z$ und durch den Beitrag großer Primzahlen entstehen, und etabliert einen Fehlerterm von $O(X/\sqrt{\log X})$ .

Hauptergebnisse

Theorem 1.1 (Basis 10): Die asymptotische Dichte der Sackgassen in Basis 10 existiert und ist gegeben durch:
$c_{\text{dead}} = \sum_{S \subseteq \{0,\dots,9\}} (-1)^{|S|} \prod_{p \text{ prim}} \left( 1 - \frac{\nu_p(S)}{p^2} \right)$
wobei $\nu_p(S)$ die Anzahl der Restklassen $n \pmod{p^2}$ ist, sodass $p^2 \mid n$ oder $p^2 \mid (10n+d)$ für ein $d \in S$ .
Der berechnete Wert ist $c_{\text{dead}} \approx 1,317 \times 10^{-9}$ .
Theorem 1.2 (Allgemeine Basis $b$ ): Das Ergebnis lässt sich auf jede Basis $b \ge 2$ generalisieren. Die Dichte $c_{\text{dead}}(b)$ wird durch eine ähnliche geschlossene Form unter Verwendung von alternierenden Euler-Produkten angegeben. Die Arbeit liefert berechnete Näherungen für Primbasen $b \in \{2, 3, 5, 7\}$ .
Diskrepanz zu stochastischen Modellen: Die wahre Dichte ( $\approx 1,3 \times 10^{-9}$ ) ist etwa 40.000 Mal kleiner als die stochastische Vorhersage ( $\approx 5,2 \times 10^{-5}$ ). Die Arbeit schreibt dies arithmetischen Abhängigkeiten zu: Das naive stochastische Modell nimmt die Unabhängigkeit zwischen Ziffererweiterungen an, aber in der Realität erfordert die Bedingung, dass alle zehn Erweiterungen gleichzeitig fehlschlagen, die gleichzeitige Blockade durch viele verschiedene Primzahlquadrate – eine Bedingung, die wesentlich strenger ist als das unabhängige Wahrscheinlichkeitsmodell suggeriert.

Bedeutung und Ansprüche

Auflösung der Vermutung: Die Arbeit zeigt, dass während die stochastische Heuristik die Existenz unendlicher Wege als fast sicher vorhersagt, die tatsächliche arithmetische Struktur Sackgassen wesentlich seltener macht als vorhergesagt. Die Existenz eines unendlichen Weges bleibt jedoch ein offenes Problem; die Arbeit quantifiziert die Seltenheit der „Hindernisse“ (Sackgassen), beweist aber nicht die Existenz eines unendlichen Pfades.
Formalisierung: Ein primärer Anspruch der Arbeit ist, dass das Haupttheorem (Theorem 1.2) vollständig in Lean/Mathlib formalisiert wurde und der Beweis automatisch durch ein KI-Tool namens AxiomProver erzeugt wurde. Dem System wurde lediglich eine natürliche Sprachformulierung des Problems zur Verfügung gestellt, und es leitete autonom die geschlossene Formel und den Beweis ab.
Historischer Kontext (Update): Die Autoren merken an, dass sie nach der ursprünglichen Veröffentlichung auf arXiv erfuhren, dass das Hauptergebnis bereits von Mirsky im Jahr 1947 [6] erzielt wurde. Die Arbeit räumt ein, dass die Arbeit von Miller et al. (2024) [5] versäumte, auf diese Vorarbeit zu verweisen. Folglich stellt die Arbeit fest, dass, obwohl die Lean-Formalisierung ein gültiger automatisierter Beweis ist, das Manuskript nicht als primärer Forschungsbeitrag zur Fachzeitschrift eingereicht wird, sondern vielmehr als Fallstudie für automatisiertes Theorembeweisen dient.

Fazit
Die Arbeit liefert eine rigorose arithmetische Herleitung der Dichte von Sackgassen in quadratfreien Ziffer-Wegen und zeigt, dass die wahre Dichte aufgrund zahlentheoretischer Abhängigkeiten massiv von stochastischen Vorhersagen abweicht. Ihr innovativster Beitrag, wie von den Autoren formuliert, ist die erfolgreiche End-to-End-Automatisierung dieser Formalisierung mittels AxiomProver, was die Fähigkeit aktueller KI-Systeme demonstriert, nicht-triviale Probleme der analytischen Zahlentheorie zu bearbeiten.