Infinite Words with very Low Factor Complexity: an introduction to Combinatorics on Words

Diese Vorlesungsnotizen führen in die Kombinatorik auf Wörtern ein, indem sie das zentrale Thema der geringen Faktor-Komplexität unendlicher Wörter untersuchen, klassische Konzepte wie Sturmische Wörter und Rauzy-Graphen vorstellen sowie einen neuen algebraischen Beweis für einen Satz von Tijdeman liefern.

Das Wesentliche

Hier ist eine einfache, bildhafte Erklärung der wissenschaftlichen Arbeit von Mélodie Andrieu, die sich mit unendlichen Wörtern und ihrer „Komplexität" beschäftigt.

Die Geschichte der unendlichen Wörter: Ein Spaziergang durch ein Labyrinth

Stellen Sie sich vor, Sie schreiben einen unendlich langen Text, der nur aus Buchstaben besteht. Vielleicht ist es ein Lied, das nie aufhört, oder ein Code, der die Struktur des Universums beschreibt. Die Frage, die sich die Mathematiker in diesem Vortrag stellen, lautet: Wie kompliziert kann so ein Text sein, ohne dass er einfach nur langweilig wird?

Um das zu verstehen, brauchen wir ein paar Werkzeuge aus der Welt der „Kombinatorik auf Wörtern" (eine Art Mathematik für Buchstabenfolgen).

1. Der Komplexitäts-Messer: Wie viele Bausteine gibt es?

Stellen Sie sich vor, Sie schneiden Ihren unendlichen Text in kleine Stücke von gleicher Länge.

• Wenn Sie alle 3-Buchstaben-Stücke (Dreier-Blöcke) herausschneiden, wie viele verschiedene Varianten finden Sie?
• Bei einem Text wie AAAAA... gibt es nur eine einzige Variante: AAA. Das ist extrem einfach.
• Bei einem Text wie ABABAB... gibt es zwei Varianten: ABA und BAB.
• Bei einem wilden, zufälligen Text (wie der Dezimalzahl von Pi) gibt es für jede Länge fast alle möglichen Kombinationen. Das ist maximal komplex.

Die Komplexität eines Wortes ist also eine Zahl, die uns sagt: „Wie viele verschiedene Bausteine benötige ich, um diesen Text zu bauen?"

2. Das große Geheimnis: Was ist „nicht-trivial"?

Die Forscher fragen sich: Was ist das Minimum an Komplexität für einen Text, der nicht einfach nur ein stumpfes Muster wiederholt (wie ABABAB...)?

• Für 2 Buchstaben (A und B):
  Hier haben die Mathematiker Morse und Hedlund bereits 1938 eine Antwort gefunden. Sie sagten: Wenn ein Text nicht periodisch ist (also nicht einfach immer wieder dasselbe Muster wiederholt), dann muss er mindestens n + 1 verschiedene Bausteine der Länge n haben.
  • Beispiel: Bei Länge 1 braucht er 2 Varianten (A und B). Bei Länge 2 braucht er 3 Varianten. Bei Länge 100 braucht er 101 Varianten.
    Diese speziellen, „minimal komplexen" Wörter heißen Sturmian-Wörter. Sie sind wie ein perfekter Tanz zwischen Ordnung und Chaos. Sie hängen eng mit der Goldenen Zahl (dem Goldenen Schnitt) zusammen. Man kann sie sich wie die Spur eines Billiardballs auf einem quadratischen Tisch vorstellen, der nie in eine Ecke läuft, sondern für immer weiterrollt.

3. Das Problem mit mehr Buchstaben (3, 4, 5...)

Jetzt wird es spannend. Was passiert, wenn wir nicht nur A und B, sondern A, B und C (oder noch mehr) haben?
Hier gab es lange Zeit Unsicherheit.

• Man könnte denken: „Na ja, wenn ich 3 Buchstaben habe, brauche ich einfach mehr Bausteine."
• Aber es gibt einen Haken: Man könnte einen Text bauen, der nur A, B und C benutzt, aber eigentlich nur ein Sturmian-Wort (mit A und B) ist, bei dem man einfach C an den Anfang klebt. Das wäre technisch gesehen ein 3-Buchstaben-Wort, aber geistig immer noch nur ein 2-Buchstaben-Wort. Das ist „trivial" und langweilig.

Die Forscher wollen also nur die echten 3-Buchstaben-Wörter betrachten, bei denen alle Buchstaben in einem perfekten, ausgewogenen Verhältnis vorkommen. Das nennt man rationale Unabhängigkeit. Stellen Sie sich vor, die Häufigkeit von A, B und C ist so verknüpft, dass man sie nicht durch einfache Brüche (wie 1/2 oder 1/3) beschreiben kann. Sie sind wie ein Orchester, bei dem kein Instrument im Takt der anderen schlägt.

4. Die Entdeckung von Tijdeman (und das neue Rätsel)

Ein Mathematiker namens Tijdeman hat 1999 eine Formel gefunden. Er sagte:

„Wenn Sie ein Wort mit 3 Buchstaben haben, bei dem alle Buchstaben in diesem perfekten, irrationalen Verhältnis vorkommen, dann ist die minimale Komplexität 2n + 1."
(Bei 4 Buchstaben wäre es 3n + 1, bei d Buchstaben (d-1)n + 1).

Das ist die untere Grenze. Alles, was darunter liegt, ist entweder zu einfach (periodisch) oder nicht „echt" genug.

5. Die neue Lösung: Ein algebraischer Beweis (2022)

Bis vor kurzem war der Beweis von Tijdeman sehr schwer zu verstehen. Er basierte auf komplexen kombinatorischen Tricks.
In diesen Vorlesungsnotizen präsentiert die Autorin (zusammen mit J. Cassaigne) einen neuen, algebraischen Beweis aus dem Jahr 2022.

Die Metapher des Beweises:
Stellen Sie sich das Wort nicht als Text vor, sondern als ein Flussnetzwerk (wie Wasserrohre oder Stromkreise).

• Die Buchstaben sind die Wasserströme.
• Die verschiedenen Bausteine (Faktoren) sind die Knotenpunkte im Netzwerk.
• Die Autorin benutzt eine spezielle Matrix (eine Art Tabelle), die sie „Flow-Matrix" (Fluss-Matrix) nennt. Diese Matrix beschreibt, wie das Wasser durch das Netzwerk fließt.

Ihr genialer Trick: Sie nutzen Gesetze aus der linearen Algebra (die Mathematik der Vektoren und Matrizen), um zu zeigen, dass das Netzwerk nur dann stabil sein kann, wenn die Komplexität genau dieser Formel folgt. Wenn die Komplexität zu niedrig wäre, würde das Netzwerk „kollabieren" – das Wasser würde nicht mehr fließen können, ohne dass sich die Buchstaben-Häufigkeiten ändern.

Warum ist das wichtig?
Dieser neue Beweis ist nicht nur eleganter, sondern er enthüllt auch eine verborgene Struktur dieser Wörter. Er zeigt, dass alle diese minimal komplexen Wörter eine besondere Eigenschaft haben: Sie sind „dendrisch".

• Dendrisch kommt von „Dendron" (Baum).
• Das bedeutet, dass die Struktur dieser Wörter wie ein Baum aufgebaut ist: Es gibt keine geschlossenen Kreise, keine Schleifen, die sich verheddern. Alles ist klar verzweigt.

Zusammenfassung für den Alltag

Stellen Sie sich vor, Sie bauen eine Stadt mit Straßen (die Buchstaben).

1. Sturmian-Wörter (2 Buchstaben): Eine Stadt, die so effizient gebaut ist, dass sie genau eine Spur mehr hat als nötig, um nicht in einem Kreis zu enden. Sie ist perfekt ausbalanciert.
2. Tijdeman-Wörter (3+ Buchstaben): Eine Stadt mit mehr Straßen. Die Frage war: Wie viele Straßen braucht man mindestens, damit die Stadt lebendig ist und nicht in einem einfachen Kreis endet?
3. Die Antwort: Man braucht genau so viele Straßen, wie die Formel sagt.
4. Der neue Beweis: Die Autorin hat gezeigt, dass man diese Frage nicht durch Zählen der Straßen lösen muss, sondern indem man die „Flussdynamik" des Verkehrs analysiert. Und dabei hat sie entdeckt, dass diese perfekten Städte immer wie Bäume aufgebaut sind – verzweigt, aber ohne Sackgassen oder Kreise.

Fazit:
Diese Arbeit zeigt uns, dass hinter scheinbar zufälligen Buchstabenfolgen tiefe, mathematische Gesetze stecken. Sie verbindet die Welt der Zahlen (Irrationalität), die Welt der Dynamik (wie sich Dinge bewegen) und die Welt der Struktur (Bäume und Graphen). Und das Beste: Sie hat einen neuen, klaren Weg gefunden, um diese Gesetze zu beweisen, der wie ein gut geöltes Maschinenteil funktioniert.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Vortragsmanuskripts auf Deutsch.

Titel und Kontext

Titel: Infinite Words with very Low Factor Complexity: an introduction to Combinatorics on Words (Unendliche Wörter mit sehr niedriger Faktorkomplexität: Eine Einführung in die Kombinatorik auf Wörtern).
Autor: Mélodie Andrieu (in Zusammenarbeit mit J. Cassaigne).
Kontext: Vorlesungsnotizen, basierend auf einem Vortrag auf der Dyadisc-Konferenz (2024) und neuen Ergebnissen aus Seminaren seit 2023. Der Text richtet sich an Doktoranden und Forscher im Bereich der Kombinatorik auf Wörtern, dynamischen Systemen und algebraischen Strukturen.

---

1. Problemstellung und Motivation

Das zentrale Thema der Arbeit ist die Untersuchung der Faktorkomplexität unendlicher Wörter über endlichen Alphabeten.

• Definition: Die Komplexität $p_w(n)$ eines unendlichen Wortes $w$ zählt die Anzahl der verschiedenen Faktoren (Teilwörter) der Länge $n$, die in $w$ vorkommen.
• Hintergrund: Der klassische Satz von Morse und Hedlund (1938) besagt, dass ein unendliches Wort genau dann schließlich periodisch ist, wenn seine Komplexität beschränkt ist (bzw. wenn $p_w(n) \le n$ für ein $n$ gilt). Für nicht-periodische binäre Wörter ($d=2$) ist die minimale Komplexität $p_w(n) = n + 1$. Diese Wörter werden als Sturmische Wörter bezeichnet und sind tief mit irrationalen Rotationen, Kettenbrüchen und geometrischen Billardbahnen verknüpft.
• Die offene Frage: Wie lässt sich dieses Ergebnis auf Wörter über größeren Alphabeten ($d \ge 3$) verallgemeinern?
  • Was ist die minimale Komplexität für "interessante" (nicht-triviale) $d$-adische Wörter?
  • Wie definiert man "nicht-trivial" für $d \ge 3$? (Nicht-periodisch reicht nicht aus, da man trivial konstruierte Wörter mit minimaler Komplexität $n+d-1$ finden kann, die im Wesentlichen nur Sturmische Wörter mit zusätzlichen Buchstaben sind).
  • Welche Wörter erreichen diese minimale Komplexität und welche strukturellen Eigenschaften haben sie?

---

2. Methodik und theoretischer Rahmen

Die Arbeit verbindet drei Hauptbereiche:

1. Kombinatorik auf Wörtern: Analyse von Faktoren, speziellen Faktoren (rechts/links-spezial) und Substitutionen.
2. Dynamische Systeme: Kodierung von Rotationen, Billardbahnen und Fluss auf Tori.
3. Algebraische Methoden: Einsatz von Linearer Algebra (Rang-Nullität-Satz, Eigenräume) auf neu eingeführten Matrizen, die aus der Struktur der Wörter abgeleitet werden.

Schlüsselkonzepte:

• Rational unabhängige Häufigkeiten: Als Verallgemeinerung der "Nicht-Periodizität" für $d \ge 3$ wird die Bedingung eingeführt, dass die Häufigkeiten der Buchstaben $f_1, \dots, f_d$ über $\mathbb{Q}$ linear unabhängig sein müssen (d.h. $\dim_{\mathbb{Q}} \text{Span}(f_1, \dots, f_d) = d$).
• Rauzy-Graphen: Gerichtete Graphen, deren Knoten die Faktoren der Länge $n$ und deren Kanten die Faktoren der Länge $n+1$ sind.
• Flow-Matrizen (Strömungsmatrizen): Eine neuartige, rechteckige Matrix $M$ (Größe $p_w(n) \times p_w(n+1)$), die die Differenz zwischen links- und rechtsseitigen Erweiterungen von Faktoren kodiert. Sie basiert auf Kirchhoffs Knotenregel.
• Dendrische Wörter: Eine Klasse von Wörtern, bei denen die Erweiterungsgraphen aller Faktoren Bäume sind.

---

3. Hauptergebnisse und Beiträge

Die Arbeit ist in drei Kapitel unterteilt, die folgende Ergebnisse liefern:

Kapitel 1: Grundlagen und Sturmische Wörter

• Einführung in den Satz von Morse und Hedlund.
• Detaillierte Analyse der Sturmischen Wörter ($d=2$):
  • Sie sind genau die nicht-periodischen binären Wörter mit Komplexität $p_w(n) = n+1$.
  • Es wird die Verbindung zu Kettenbrüchen hergestellt: Das "Run-Length"-Verfahren (Renormierung) eines Sturmischen Wortes entspricht dem Algorithmus zur Berechnung der Kettenbruchentwicklung des Verhältnisses der Buchstabenhäufigkeiten.
  • Es wird gezeigt, dass Sturmische Wörter unendlich viele sind (eine für jede positive irrationale Zahl) und äquivalent als Kodierungen irrationaler Rotationen oder Billardbahnen auf einem Quadrat definiert werden können.

Kapitel 2: Verallgemeinerung auf $d$-adische Wörter (Satz von Tijdeman)

• Problem der Definition von "Minimal": Es wird gezeigt, dass die Bedingung "nicht schließlich periodisch" für $d \ge 3$ zu schwach ist, da man Wörter mit Komplexität $n+d-1$ konstruieren kann, die jedoch keine echten Verallgemeinerungen der Sturmischen Wörter sind (sie haben rational abhängige Häufigkeiten).
• Die Lösung: Die Bedingung wird auf rationale Unabhängigkeit der Buchstabenhäufigkeiten verschärft.
• Satz von Tijdeman (1999):
  • Für ein unendliches $d$-adisches Wort mit rational unabhängigen Häufigkeiten gilt die untere Schranke:
    $$p_w(n) \ge (d-1)n + 1$$
  • Diese Schranke ist scharf; es existieren Wörter, die diese Komplexität erreichen.
• Charakterisierung: Es wird diskutiert, welche bekannten Klassen (Arnoux-Rauzy-Wörter, Cassaigne-Selmer-Wörter, strikte episturmische Wörter) diese minimale Komplexität erreichen.
• Erweiterter Satz (Andrieu/Cassaigne 2022): Eine Verschärfung des Tijdeman-Satzes, die nicht nur die minimale Irrationalitätsstufe $\delta_w$, sondern die maximale Irrationalitätsstufe $\Delta_w$ der Häufigkeiten (basierend auf Häufungspunkten der Häufigkeitsvektoren) verwendet:
  $$p_w(n) \ge (\Delta_w - 1)(n - 1) + d$$

Kapitel 3: Neuer algebraischer Beweis und Konsequenzen

Dies ist der Kern der neuen Forschungsergebnisse des Autors.

• Neuer Beweis des Tijdeman-Satzes:
  • Statt kombinatorischer Argumente (wie im Original von Tijdeman) wird ein rein algebraischer Beweis mittels Linearer Algebra vorgestellt.
  • Methode: Analyse des Kerns der Flow-Matrix $M$.
  • Schlussfolgerung: Der Vektor der pseudo-Häufigkeiten der Faktoren liegt im Kern von $M$. Durch Untersuchung der Dimension des Kerns (unter Verwendung des Rang-Nullität-Satzes und der Eigenschaften der Rauzy-Graphen) wird gezeigt, dass die Dimension des von den Buchstabenhäufigkeiten aufgespannten rationalen Raums durch die Komplexität beschränkt ist. Ein Widerspruch zur Annahme der rationalen Unabhängigkeit führt zum Beweis der unteren Schranke.
• Neues Ergebnis: Dendrische Struktur:
  • Als Nebenprodukt dieses Beweises wird gezeigt, dass alle unendlichen $d$-adischen Wörter mit rational unabhängigen Häufigkeiten und minimaler Komplexität $(d-1)n+1$ dendrisch sind.
  • Dies bedeutet, dass die Erweiterungsgraphen aller ihrer Faktoren Bäume sind. Dies ist ein starkes strukturelles Ergebnis, das die Klasse dieser Wörter eng eingrenzt.

---

4. Signifikanz und Bedeutung

1. Lösung eines offenen Problems: Die Arbeit liefert eine präzise Antwort auf die Frage nach der minimalen Komplexität für nicht-triviale Wörter über großen Alphabeten, indem sie die Bedingung der rationalen Unabhängigkeit der Häufigkeiten als das richtige Kriterium für "Nicht-Trivialität" etabliert.
2. Methodischer Fortschritt: Der neue algebraische Beweis des Tijdeman-Satzes ist konzeptionell neu. Er verbindet die Kombinatorik auf Wörtern direkt mit der Theorie der linearen Abbildungen und Matrizen (Flow-Matrizen), was neue Werkzeuge für zukünftige Forschung eröffnet.
3. Strukturelle Charakterisierung: Die Erkenntnis, dass Wörter mit minimaler Komplexität und rational unabhängigen Häufigkeiten notwendigerweise dendrisch sind, stellt einen wichtigen Schritt zur vollständigen kombinatorischen Charakterisierung dieser Klasse dar. Dies verknüpft die Komplexitätstheorie mit der Theorie der Erweiterungsgraphen.
4. Verbindung der Disziplinen: Das Manuskript verbindet erfolgreich arithmetische Eigenschaften (Kettenbrüche, Irrationalität), dynamische Systeme (Rotationen, Billards) und kombinatorische Strukturen (Substitutionen, Graphen) in einem einheitlichen Rahmen.

Zusammenfassend stellt dieses Dokument eine fundierte Einführung in die Theorie der Sturmischen Wörter dar und liefert gleichzeitig signifikante neue Forschungsergebnisse zur Verallgemeinerung auf höhere Alphabetgrößen, wobei ein neuer algebraischer Zugang zu einem klassischen Problem gefunden wurde.