The complexity of finite smooth words over binary alphabets

Diese Arbeit beweist, dass die Faktoren glatter Wörter f-glatt sind, und liefert Fortschritte zur Vermutung von Sing über das Komplexitätswachstum f-glatter Wörter über binären Alphabeten, indem sie die Vermutung für gerade Alphabeten bestätigt, eine untere Schranke für beliebige binäre Alphabeten etabliert und die bekannte obere Schranke für ungerade Alphabeten verbessert.

Das Wesentliche

Stellen Sie sich vor, Sie haben einen unendlichen, sich selbst wiederholenden Text, der wie ein riesiges, komplexes Muster aus zwei verschiedenen Buchstaben (z. B. A und B) besteht. Dieser Text ist das „Oldenburger-Kolakoski-Wort". Es ist eines der berühmtesten Rätsel in der Welt der Mathematik, weil niemand genau weiß, wie viele verschiedene kleine Abschnitte (Faktoren) darin vorkommen, wenn man sie immer länger macht.

Die Autoren dieses Papers, Julien Cassaigne und Raphaël Henry, haben sich dieses Rätsel vorgenommen. Hier ist die Erklärung ihrer Arbeit, vereinfacht und mit ein paar Bildern:

1. Das große Rätsel: Der unendliche Teppich

Stellen Sie sich den unendlichen Text als einen riesigen, endlosen Teppich vor. Wenn Sie ein kleines Fenster auf den Teppich halten und nach links und rechts schieben, sehen Sie immer wieder neue kleine Muster.

• Die Frage: Wie viele unterschiedliche Muster gibt es, wenn das Fenster eine bestimmte Größe hat?
• Das Problem: Der Teppich ist so komplex, dass man ihn nicht einfach abtasten kann. Man braucht eine Art „Lupe", um die Struktur zu verstehen.

2. Die Lupe: „F-smooth" Wörter

Die Forscher haben eine clevere Methode entwickelt. Anstatt den ganzen unendlichen Teppich zu betrachten, schauen sie sich nur die endlichen Stücke an, die man aus dem Teppich schneiden kann. Sie nennen diese Stücke „f-smooth Wörter".

Stellen Sie sich vor, Sie nehmen ein Stück des Teppichs und drücken es durch eine spezielle Maschine (einen „Derivator").

• Diese Maschine zählt, wie oft ein Buchstabe hintereinander kommt, und schreibt diese Zahl als neuen Buchstaben auf.
• Wenn Sie das Ergebnis wieder durch die Maschine stecken, passiert das Gleiche.
• Ein Wort ist „f-smooth", wenn Sie es immer wieder durch diese Maschine stecken können, ohne dass es „zerbricht" oder sich in etwas Unmögliches verwandelt, bis am Ende nichts mehr übrig ist (wie ein Stück Papier, das man immer kleiner schneidet, bis es zu Staub wird).

Die große Entdeckung der Autoren:
Sie haben bewiesen, dass jedes Stück, das im unendlichen Teppich vorkommt, auch durch diese Maschine „überlebt" hat. Umgekehrt gilt: Jedes Wort, das die Maschine überlebt, kommt auch im unendlichen Teppich vor.

• Metapher: Es ist, als würden sie beweisen, dass alle Teile, die in einer Fabrik überleben, auch auf dem endlosen Fließband zu finden sind, und umgekehrt. Das bedeutet: Um das Rätsel des unendlichen Teppichs zu lösen, reicht es, die endlichen Stücke zu zählen.

3. Die zwei Welten: Gerade und Ungerade Zahlen

Die Forscher haben festgestellt, dass es zwei völlig verschiedene Arten von Teppichen gibt, abhängig davon, welche Zahlen (Buchstaben) verwendet werden:

• Die „Gerade-Welt" (z. B. 2 und 4): Hier verhält sich der Teppich sehr ordentlich. Die Anzahl der verschiedenen Muster wächst vorhersehbar. Die Autoren konnten beweisen, dass die Komplexität genau so schnell wächst, wie die Mathematiker es schon lange vermutet haben.

  • Vergleich: Wie ein gut geplanter Garten, in dem jedes Beet genau die gleiche Anzahl an Blumen hat.

• Die „Ungerade-Welt" (z. B. 1 und 3): Hier wird es chaotischer. Die Muster sind wilder und schwerer zu berechnen. Bisher gab es nur grobe Schätzungen, wie schnell die Komplexität wächst.

  • Vergleich: Wie ein wilder Dschungel, in dem man nicht genau weiß, wie viele verschiedene Pflanzenarten es gibt.

4. Was haben die Autoren geschafft?

Sie haben drei wichtige Dinge getan:

1. Der Beweis der Verbindung: Sie haben endgültig bewiesen, dass die „f-smooth" Wörter (die überlebenden Stücke) exakt die gleichen sind wie die Teile des unendlichen Teppichs. Das schließt eine Lücke, die seit Jahrzehnten offen war.
2. Die untere Grenze (Das Minimum): Sie haben für alle Arten von Teppichen (sowohl gerade als auch ungerade) bewiesen, dass die Komplexität mindestens so schnell wächst wie eine bestimmte Formel sagt. Sie haben also eine „Bodenplatte" gefunden, unter die die Komplexität nicht fallen kann.
3. Die obere Grenze (Das Maximum):
   • Für die geraden Teppiche haben sie bewiesen, dass die Komplexität nicht schneller wächst als die Formel sagt. Damit ist das Rätsel für diese Welt gelöst!
   • Für die ungeraden Teppiche haben sie eine neue, viel bessere Schätzung nach oben hin gefunden. Sie haben den „Dschungel" etwas eingezäunt. Es ist zwar noch nicht perfekt gelöst, aber sie haben gezeigt, dass das Wachstum nicht so wild ist wie man dachte.

Zusammenfassung in einem Satz

Die Autoren haben bewiesen, dass man, um die Geheimnisse eines unendlichen, chaotischen Musters zu verstehen, nur die „überlebenden" endlichen Teile betrachten muss, und sie haben für die ordentlichen Fälle bewiesen, wie schnell die Komplexität wächst, während sie für die chaotischen Fälle eine viel schärfere Obergrenze gefunden haben.

Warum ist das wichtig?
Es hilft uns zu verstehen, wie komplexe Strukturen in der Natur und in der Mathematik entstehen. Es zeigt uns, dass selbst in scheinbar zufälligen Mustern tiefe, verborgene Regeln stecken, die man mit der richtigen „Lupe" (den f-smooth Wörtern) entdecken kann.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papers auf Deutsch:

Titel und Autoren

Titel: The complexity of finite smooth words over binary alphabets (Die Komplexität endlicher glatter Wörter über binären Alphabeten)
Autoren: Julien Cassaigne und Raphaël Henry
Publikationsdatum: März 2026 (Preprint)

---

1. Problemstellung und Hintergrund

Das Paper befasst sich mit der Faktor-Komplexität (Anzahl der verschiedenen Faktoren der Länge $n$) von sogenannten glatten Wörtern (smooth words) über binären Alphabeten $A = \{a, b\}$ mit $1 \le a < b$.

• Glatte Wörter ($C^\infty$): Unendliche Wörter, die unendlich oft "ableitbar" sind. Die Ableitung $D$ basiert auf der Lauf-Länge-Kodierung (Run-Length Encoding). Das bekannteste Beispiel ist das Oldenburger-Kolakoski-Wort $\kappa_{2,1}$ über $\{1, 2\}$.
• Endlich glatte Wörter ($C^\infty_f$ oder $f$-smooth): Eine endliche Version, die durch eine Ableitung $D_f$ definiert ist, die lokal die Lauf-Länge-Kodierung simuliert und auf endliche Wörter angewendet wird, bis sie auf das leere Wort $\varepsilon$ reduziert werden.
• Die zentrale Frage: Wie wächst die Komplexität $p_{C^\infty_f}(n)$ der Sprache der $f$-glatten Wörter?
• Vermutung von Sing (basierend auf Dekking): Die Komplexität wächst asymptotisch wie $\Theta(n^\rho)$ mit $\rho = \frac{\log(a+b)}{\log((a+b)/2)}$.

Bisherige Ergebnisse waren uneinheitlich:

• Für das Alphabet $\{1, 2\}$ wurden polynomiale Schranken gezeigt, aber die exakte Exponentenbestimmung blieb offen.
• Es gab eine Dichotomie zwischen Alphabeten, bei denen $a+b$ gerade ist (even), und solchen, bei denen $a+b$ ungerade ist (odd).
• Ein wichtiger Fehler in einer früheren Arbeit von Huang ([11]) wurde identifiziert, der zu falschen Schranken für ungerade Alphabeten führte.

---

2. Methodik

Die Autoren verwenden eine Kombination aus kombinatorischer Worttheorie, der Analyse von bisspeziellen Faktoren (bispecial words) und linearen Algebra-Methoden (Eigenwerte von Matrizen).

A. Beziehung zwischen glatten und endlich glatten Wörtern

Ein Hauptziel ist es, die Beziehung zwischen der Sprache der unendlichen glatten Wörter $L(C^\infty)$ und der Menge der endlich glatten Wörter $C^\infty_f$ zu klären.

• Die Autoren definieren r-glatte Wörter ($C^\infty_r$), die als Präfixe glatter Wörter fungieren.
• Sie beweisen, dass jedes $f$-glatte Wort ein Faktor eines $r$-glatten Wortes ist und jedes $r$-glatte Wort ein Präfix eines unendlichen glatten Wortes ist.

B. Analyse bisspezieller Faktoren

Die Komplexität wird über die Theorie der bisspeziellen Faktoren berechnet (Theorem 1.5).

• Bisspezielle Wörter: Wörter, die sowohl links als auch rechts um beide Buchstaben des Alphabets erweitert werden können.
• Struktur: Die Autoren klassifizieren die starken und schwachen bisspeziellen $f$-glatten Wörter in Familien, die durch unendliche binäre Bäume strukturiert sind.
• Reduktion: Sie zeigen, dass jede bisspezielle $f$-glatte Wort durch Ableitung auf ein kurzes "Wurzel"-Wort reduziert werden kann, das die gleiche Multiplizität (stark, schwach oder neutral) besitzt.
• Primitiven: Einführung von Abbildungen $P_{f,a}$ und $P_{f,b}$ (finite primitives), die die Struktur dieser Bäume beschreiben.

C. Asymptotische Analyse der Bäume

Um die Komplexität zu schätzen, analysieren die Autoren die Längen der Wörter in den Generationen dieser Bäume:

• Untere Schranke: Berechnung der durchschnittlichen Länge der Wörter in den Bäumen.
• Obere Schranke: Suche nach einer unteren Schranke für die minimale Länge $l_i$ der Wörter in der $i$-ten Generation des Baumes.
• Lineare Algebra: Für ungerade Alphabeten wird die Längenentwicklung durch lineare Rekursionen beschrieben, die durch Matrizen $M$ und $P$ dargestellt werden. Die Wachstumsrate wird durch den dominierenden Eigenwert (spektraler Radius) dieser Matrizen bestimmt.

---

3. Wichtige Beiträge und Ergebnisse

1. Äquivalenz der Sprachen (Theorem 1.31)

• Ergebnis: Über jedem binären Alphabet gilt $L(C^\infty) = C^\infty_f$.
• Bedeutung: Die Menge der $f$-glatten Wörter ist exakt die Menge der Faktoren aller glatten Wörter. Daraus folgt $p_{C^\infty}(n) = p_{C^\infty_f}(n)$. Dies bestätigt die Relevanz der Untersuchung von $C^\infty_f$ für alle Alphabettypen, auch wenn die Struktur der einzelnen glatten Wörter bei geraden Alphabeten komplexer sein kann.

2. Bestätigung der unteren Schranke und der Vermutung für gerade Alphabeten (Theorem 1.32)

• Untere Schranke: Für jedes binäre Alphabet gilt $p_{C^\infty_f}(n) = \Omega(n^\rho)$ mit $\rho = \frac{\log(a+b)}{\log((a+b)/2)}$.
• Gerade Alphabeten ($a, b$ beide gerade): Die Autoren beweisen die Vermutung von Sing vollständig. Es gilt $p_{C^\infty_f}(n) = \Theta(n^\rho)$.
• Methode: Bei geraden Alphabeten sind die minimale und maximale Länge der Wörter in den Baumgenerationen identisch ($l_i = L_i$), was eine exakte Berechnung ermöglicht.

3. Verbesserte obere Schranke für ungerade Alphabeten (Theorem 1.33)

• Problem: Bei ungeraden Alphabeten ($a, b$ beide ungerade) wächst die minimale Länge $l_i$ langsamer als die maximale Länge $L_i$, was die direkte Anwendung der Vermutung erschwert.
• Ergebnis: Die Autoren leiten eine neue obere Schranke $p_{C^\in_f}(n) = O(n^\zeta)$ ab.
• Der Exponent $\zeta$:
  • Falls $a=1$: $\zeta = \frac{\log(2\lambda)}{\log(\lambda)}$ mit $\lambda = \frac{1+\sqrt{2b-1}}{2}$.
  • Sonst: $\zeta = \frac{\log(2\lambda)}{\log(\lambda)}$, wobei $\lambda$ die dominante Nullstelle des Polynoms $X^3 - \frac{a+b}{2}X^2 + \frac{(b-a)^2}{4}$ ist.
• Vergleich: Diese Schranke verbessert die bekannten Ergebnisse von Theorem 1.21 (Dekking/Sing) signifikant, wie in der Tabelle im Paper (Remark 1.34) für verschiedene Alphabeten gezeigt wird.

4. Korrektur früherer Fehler

• Die Autoren identifizieren und korrigieren einen fundamentalen Fehler in Huangs Arbeit [11], der auf einer falschen Definition der endlichen Ableitung beruhte. Huangs Behauptungen über die Komplexität bei ungeraden Alphabeten sind daher falsch.

---

4. Signifikanz und Bedeutung

• Lösung eines offenen Problems: Das Paper liefert den ersten vollständigen Beweis für die asymptotische Komplexität von $f$-glatten Wörtern über geraden Alphabeten und bestätigt damit die Vermutung von Sing in diesem Fall.
• Fortschritt bei ungeraden Alphabeten: Obwohl die Vermutung für ungerade Alphabeten noch nicht als exakte $\Theta$-Schranke bewiesen ist, wird die obere Schranke drastisch verbessert und nähert sich dem vermuteten Wert an.
• Strukturelle Einsichten: Die Entdeckung der Dichotomie zwischen geraden und ungeraden Alphabeten bezüglich des Wachstumsverhaltens der minimalen und maximalen Längen in den bisspeziellen Bäumen ist ein wichtiger theoretischer Durchbruch.
• Methodischer Beitrag: Die Anwendung der Perron-Frobenius-Theorie auf die Matrizen, die die Längenentwicklung in den Bäumen beschreiben, bietet einen neuen Weg zur Analyse der Komplexität solcher Wortklassen.

Zusammenfassend stellt dieses Paper einen Meilenstein in der kombinatorischen Worttheorie dar, indem es die Lücke zwischen den bekannten polynomiellen Schranken und der vermuteten exakten Wachstumsrate schließt und dabei die Struktur der glatten Wörter über beliebigen binären Alphabeten tiefgreifend aufklärt.