🔢 mathematics

Superlinear complexity of the $(3/2)^n$ steering word

Diese Arbeit beweist, dass die Subwortkomplexität des durch die $(3/2)^n$ -Abbildung erzeugten Steuerworts superlinear ist, ein Ergebnis, das unter Verwendung des Subspace-Theorems etabliert und in Lean-4 vollständig formalisiert wurde.

Ursprüngliche Autoren: Ralf Stephan

Veröffentlicht 2026-07-14

📖 5 Min. Lesezeit🧠 Tiefgang

CC0 1.0

Ursprüngliche Autoren: Ralf Stephan

Originalarbeit unter CC0 1.0 der Gemeinfreiheit gewidmet (http://creativecommons.org/publicdomain/zero/1.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

Stellen Sie sich eine magische Maschine vor, die eine Zahl nimmt, sie mit 1,5 multipliziert und dann zur nächsten ganzen Zahl rundet. Stellen Sie sich nun vor, Sie lassen diese Maschine immer und immer wieder laufen, beginnend mit der Zahl 1.

1 wird zu 1,5, was zu 2 gerundet wird.
2 wird zu 3, was 3 bleibt.
3 wird zu 4,5, was zu 5 gerundet wird.
5 wird zu 7,5, was zu 8 gerundet wird.

Dies erzeugt eine Folge von ganzen Zahlen: 1, 2, 2, 3, 5, 8 und so weiter. Aber das Papier interessiert sich nicht nur für die Zahlen selbst; es interessiert sich für das „Lenkrad“, das der Maschine sagt, wie sie dorthin gelangt ist. Bei jedem einzelnen Schritt musste die Maschine entscheiden, ob sie auf- oder abrundet, um die nächste ganze Zahl zu treffen. Wenn man all diese kleinen Entscheidungen als einen Code (unter Verwendung von Zahlen wie -2, -1, 0, 1 oder 2) zusammenfügt, erhält man ein langes, unendliches „Steuerwort“.

Die große Frage, die das Papier stellt, lautet: Wie komplex ist dieser Code?

In der Welt der Muster sind manche Codes banal einfach. Denken Sie an ein Lied, das ewig „la-la-la“ wiederholt. Das ist ein einfaches Muster. Andere Codes sind chaotisch und unordentlich, wie das Rauschen im Radio. Mathematiker messen diese „Unordnung“ (Messiness), indem sie zählen, wie viele einzigartige kurze Stücke (oder „Teilwörter“) einer bestimmten Länge der Code besitzt. Wenn ein Code einfach ist, wächst die Anzahl der einzigartigen Stücke langsam (wie eine gerade Linie). Wenn ein Code komplex ist, explodiert die Anzahl der einzigartigen Stücke.

Das Hauptergebnis
Das Papier beweist, dass dieses spezifische Steuerwort wild komplex ist. Es wächst nicht einfach in einer geraden Linie; es wächst „superlinear“. Das bedeutet, dass sich die Anzahl der einzigartigen Muster, die man bei immer längeren Stücken findet, immer schneller erhöht und gegen Unendlich schießt.

Um es spielerisch auszudrücken: Wenn Sie versuchen würden, den nächsten Schritt in dieser Sequenz vorherzusagen, indem Sie in die Vergangenheit schauen, würden Sie irgendwann gegen eine Wand laufen. Egal wie lange ein Muster ist, die Sequenz wird schließlich etwas völlig Neues tun, das Sie noch nie zuvor gesehen haben. Sie weigert sich, sich in einer Schleife einzupendeln.

Was das Papier ausschließt
Das Papier schließt explizit die Idee aus, dass diese Sequenz „eventuell periodisch“ ist. In einfachen Worten ausgedrückt bedeutet dies, dass die Sequenz niemals in einen sich wiederholenden Zyklus verfallen wird, wie eine kaputte Schallplatte. Sie wird niemals anfangen, ewig „1, 2, 3, 1, 2, 3“ zu sagen. Die Autoren beweisen, dass man egal wie weit man in der Sequenz geht, niemals einen Punkt finden wird, an dem sie einfach immer wieder dasselbe Muster wiederholt.

Wie sicher sind sie sich?
Die Autoren raten nicht nur oder simulieren dies an einem Computer. Sie haben es bewiesen.

Sie bauten eine Festung der Logik aus zwei hochkomplexen mathematischen Werkzeugen (denen Sätzen von Corvaja–Zannier und Nair–Kumar–Rout), die wie unknackbare Schlösser wirken. Sie taten zudem etwas Besonderes: Sie übersetzten ihren gesamten Beweis in eine Computersprache namens Lean-4. Dieser Computer überprüfte jeden einzelnen Schritt ihrer Logik, um sicherzustellen, dass es keine menschlichen Fehler gab. Der Computer sagte: „Ja, dieser Beweis ist gültig.“

Der Weg des Beweises
Der Beweis findet in drei Phasen statt, wie das Besteigen eines Berges:

Phase 0 (Das Fundament): Zuerst zeigten sie, dass, falls die Sequenz ein langes Muster wiederholen würde, dies die Gesetze der Mathematik verletzen würde (speziell würde es eine mathematische Unmöglichkeit bezüglich der Art und Weise erzeugen, wie Zahlen sich teilen). Dies bewies, dass die Sequenz keine einfache Schleife ist und zeigte bereits, dass sie komplexer als das einfachste mögliche nicht-repetitive Muster ist.
Phase 1 (Die Reduktion): Sie erkannten, dass sie, um zu beweisen, dass die Sequenz super komplex ist, nur eines Bestimmtes beweisen mussten: dass die Zahlen in der Sequenz nicht „zu oft“ nah beieinander liegen. Wenn sie weit genug voneinander entfernt blieben, wäre der Code gezwungen, chaotisch und komplex zu sein.
Phase 2 (Der Gipfel): Sie nutzten jene schweren mathematischen Werkzeuge, um zu beweisen, dass die Zahlen tatsächlich weit genug voneinander entfernt bleiben. Sie unterteilten das Problem in drei Zonen:
- Die kleine Lücken-Zone: Wenn die Zahlen in der Sequenz nah beieinander liegen.
- Die riesige Lücken-Zone: Wenn die Zahlen in der Sequenz sehr weit voneinander entfernt sind.
- Die mittlere Zone: Der knifflige Bereich dazwischen.

Für die ersten beiden Zonen verwendeten sie einen leistungsstarken Satz. Für die mittlere Zone nutzten sie einen klugen Trick (eine „Dichotomie“), der zeigte, dass wenn das Muster versuchte, einfach zu sein, dies zu einem Widerspruch führen würde (so wie zu beweisen, dass ein Bruch eigentlich eine ganze Zahl ist, was unmöglich ist).

Das Fazit
Das Steuerwort für die (3/2)-Sequenz ist ein chaotisches, nicht-repetitives Meisterwerk. Es ist so komplex, dass die Anzahl der einzigartigen Muster, die es enthält, schneller als jede gerade Linie wächst. Dies ist keine Vermutung oder Simulation; es ist ein mathematisch bewiesener Fakt, der von einem Computer doppelt geprüft wurde und zeigt, dass diese einfach klingende Regel einen unendlich komplizierten Tanz der Zahlen erzeugt.

Technisches Resümee: Superlineare Komplexität des $(3/2)^n$ -Steuerworts

Problemstellung
Die vorliegende Arbeit untersucht die symbolische Dynamik, die durch die Bahn der Zahl 1 unter der Abbildung $x \mapsto \frac{3}{2}x$ erzeugt wird, wobei der Fokus spezifisch auf der Sequenz der Rundungsfehler zur nächsten Ganzzahl liegt. Während die Verteilung der Sequenz $\|(\frac{3}{2})^n\|$ (Abstand zur nächsten Ganzzahl) ein langjähriges offenes Problem der Zahlentheorie darstellt, verlagert diese Arbeit den Fokus auf das „Steuerwort“ $T = (t_n)_{n \geq 0}$ . Dieses Wort zeichnet die bei jedem Schritt ausgewählten ganzzahligen Translationen auf, definiert durch $t_n = 2m_{n+1} - 3m_n$ , wobei $m_n = \text{round}((\frac{3}{2})^n)$ . Die zentrale Fragestellung ist die Subwortkomplexität $p_T(k)$ , welche die Anzahl der distinkten Faktoren der Länge $k$ in $T$ zählt. Das Ziel der Arbeit ist der Nachweis, dass diese Komplexität superlinear ist, d. h. $\lim_{k \to \infty} p_T(k)/k = \infty$ .

Methodik
Die Beweisstrategie ist in drei distinkte Phasen strukturiert, wobei Methoden aus der Untersuchung der algebraischen Zahlkomplexität (speziell die Adamczewski–Bugeaud-Methode) auf diesen dynamischen Kontext übertragen werden. Das Argument stützt sich schwer auf den Satz über die Unterraum-Theorie (Subspace Theorem) und ist als vollständig in Lean-4 formalisiert vermerkt.

Stufe 0: Exakte Identitäten und bedingungslose Schranken (Abschnitt 2)
Der Autor leitet eine exakte „Repetitionsidentität“ her. Wenn ein Faktor der Länge $k$ an den Positionen $a$ und $c$ ( $a < c$ ) wiederkehrt, erzwingt dies die Relation $3^k(\varepsilon_c - \varepsilon_a) = 2^k(\varepsilon_{c+k} - \varepsilon_{a+k})$ , wobei $\varepsilon_n$ der Rundungsfehler ist.
- Diese Identität liefert eine Teilbarkeitsbedingung: $2^k \mid (m_c - m_a)$ .
- In Kombination mit den Wachstums-Eigenschaften der Bahn etabliert dies, dass lange Repetitionen nicht beliebig spät im Wort auftreten können.
- Bedingungsloses Ergebnis: Die Arbeit beweist, dass $T$ nicht schließlich periodisch ist, und stellt eine lineare untere Schranke $p_T(k) \geq \frac{41}{24}k - 3$ fest, die strikt über dem Morse–Hedlund-Niveau ( $k+1$ ) für aperiodische Wörter liegt.
Stufe 1: Reduktion auf einen diophantischen Kern (Abschnitt 3)
Das Problem des Nachweises der superlinearen Komplexität wird auf eine einzige diophantische Aussage reduziert, die als Kern (K) bezeichnet wird.
- Aussage (K): Für jedes rationale $\theta \in (0, 1)$ ist die Menge der Paare $(a, c)$ mit $2 \leq a < c$ , die die Bedingung $\|(\frac{3}{2})^c - (\frac{3}{2})^a\| \leq \theta^c$ erfüllen, endlich.
- Dies repräsentiert eine „exponentielle Paar-Repulsion“, welche die triviale untere Schranke für den Abstand zwischen Bahnpunkten von der Basis $2^{-1}$ auf eine beliebige Basis $\theta < 1$ verbessert.
- Die Reduktion zeigt: Wenn (K) gilt, dann gilt $p_T(k)/k \to \infty$ .
Stufe 2: Etablierung des Kerns (Abschnitte 4 & 5)
Der Beweis von (K) erfolgt durch die Partitionierung der Menge potenzieller Lösungen in drei „Schichten“ (Slices) und die Anwendung tiefer Resultate der diophantischen Approximation:
- Schicht mit beschränktem Abstand (Bounded Gap Slice): Für feste Abstände $c-a$ wird die Endlichkeit mittels des Corvaja–Zannier Hauptsatzes (eine Konsequenz des Schmidtschen Subspace-Theorems) bewiesen.
- Schicht mit großem Abstand (Huge-Gap Slice): Für den Bereich, in dem $a \leq \epsilon' c$ , wird die Endlichkeit ebenfalls über den Corvaja–Zannier-Satz etabliert, indem das Problem als spezieller Fall der Pseudo-Pisot-Exklusion behandelt wird.
- Mittleres Band (Middle Band): Für den verbleibenden Bereich, in dem die Abstände wachsen, aber $a$ im Vergleich zu $c$ nicht vernachlässigbar ist, verwendet der Autor eine Lücken-Dichotomie (gap dichotomy). Sollte die Menge der Lösungen unendlich sein, ließe sich eine Unterfamilie mit distinkten Abständen extrahieren. Dies führt zu einem Widerspruch via des Nair–Kumar–Rout S-Einheiten-Tupel-Theorems, was implizieren würde, dass $(\frac{3}{2})^c$ für einiges $c$ eine ganze Zahl ist – eine Unmöglichkeit.

Wesentliche Beiträge und Ergebnisse

Haupttheorem (Theorem 1.1): Die Subwortkomplexität des Steuerworts $T$ ist superlinear ( $p_T(k)/k \to \infty$ ).
Bedingungslose untere Schranke: Die Arbeit liefert eine explizite, bedingungslose lineare untere Schranke $p_T(k) \geq \frac{41}{24}k - 3$ , die ohne Rückgriff auf unbewiesene Vermutungen abgeleitet wurde.
Formalisierung: Das gesamte Argument ist in Lean-4 formalisiert. Die Formalisierung hängt lediglich vom Evertse–Schlickewei Subspace Theorem in 3 Variablen ab, was die Korrektheit der Abhängigkeiten zu den Ergebnissen von Corvaja–Zannier und Nair–Kumar–Rout bestätigt.
Aperiodizität: Ein rigoroser Beweis, dass das Steuerwort nicht schließlich periodisch ist.

Bedeutung und Behauptungen
Die Arbeit beansprucht, die Komplexitätsfrage für dieses spezifische autonome dynamische System zu lösen, indem sie symbolische Dynamik und diophantische Approximation verknüpft.

Methodischer Transfer: Sie adaptiert erfolgreich die Adamczewski–Bugeaud-Methode, die üblicherweise für algebraische Zahlen verwendet wird, auf ein dynamisches Wort. Der Autor merkt an, dass die autonome Natur der $(3/2)$ -Dynamik das „Bookkeeping“ vereinfacht, da wiederkehrende Faktoren in saubere diophantische Ungleichungen komprimiert werden können, ohne dass eine Präfix-Verankerung nötig ist.
Abhängigkeit von tiefen Theoremen: Der Beweis der Superlinearität ist abhängig vom Corvaja–Zannier-Theorem (begutachtet/refereed) und dem Nair–Kumar–Rout-Theorem (zum Zeitpunkt der Niederschrift ein Preprint). Die Lean-4 Formalisierung dient jedoch als Verifizierung, dass diese Abhängigkeiten logisch fundierte Konsequenzen des Subspace-Theorems sind.
Limitierungen: Die Ergebnisse bezüglich des superlinearen Wachstums sind ineffektiv; das Subspace-Theorem liefert keine expliziten Schranken für die Größe der Ausnahmemengen (die Anzahl der Lösungen der diophantischen Ungleichungen). Die Arbeit beansprucht nicht, das breitere offene Problem bezüglich der Dichte von $\|(\frac{3}{2})^n\| \to 0$ zu lösen, sondern charakterisiert die kombinatorische Komplexität der Rundungssequenz.

Mehr davon