Dyck Words, Pattern Avoidance, and Automatic Sequences

Dieser Artikel untersucht Dyck-Wörter in binären Folgen, indem er die Beziehung zwischen $7/3$-Potenzfreiheit und der Verschachtelungstiefe analysiert, eine explizite Charakterisierung der Dyck-Faktoren im Thue-Morse-Wort liefert und scharfe Schranken für deren Anzahl herleitet.

Das Wesentliche

🎈 Die Welt der Klammern und der unendlichen Muster

Stellen Sie sich vor, Sie haben eine endlose Kette aus zwei Arten von Perlen: schwarze Perlen (0) und weiße Perlen (1).
In dieser Welt gelten schwarze Perlen als öffnende Klammern ( und weiße Perlen als schließende Klammern ).

Ein Dyck-Wort ist einfach eine Kette, die perfekt ausbalanciert ist.

• 01 ist wie (): Eine Öffnung, eine Schließung. Perfekt.
• 0011 ist wie (()): Zwei Öffnungen, zwei Schließungen, tief verschachtelt.
• 0110 ist wie ())(: Das ist ein Chaos. Die zweite Klammer schließt zu früh, und am Ende fehlt eine Öffnung. Das ist kein Dyck-Wort.

Die Autoren dieses Papers (Lucas Mol, Narad Rampersad und Jeffrey Shallit) haben sich gefragt: Was passiert, wenn wir diese perfekten Klammer-Schnüre in riesigen, unendlichen Mustern suchen, die von Computeralgorithmen erzeugt werden?

Hier sind die vier wichtigsten Entdeckungen der Forscher, erklärt mit einfachen Bildern:

---

1. Das Spiel mit den Wiederholungen (Das „7/3"-Regelwerk)

Stellen Sie sich vor, Sie bauen eine Klammer-Schnur. Aber es gibt eine Regel: Sie dürfen keine zu langen, sich wiederholenden Muster haben.

• Ein Wort wie 010101 wiederholt sich oft.
• Die Forscher haben herausgefunden: Wenn Sie eine Regel aufstellen, die besagt „Du darfst keine Muster wiederholen, die länger als das 7/3-fache ihrer Grundlänge sind" (das ist eine sehr strenge Regel!), dann gibt es eine Grenze für die Tiefe.

Die Analogie:
Stellen Sie sich einen Turm aus Klammern vor. Wenn Sie die Wiederholungs-Regel sehr streng machen (wie bei 7/3), dann kann Ihr Klammer-Turm nur 3 Stockwerke hoch werden. Egal wie lang die Schnur ist, sie kann sich nicht unendlich tief verschachteln.

• Überraschung: Wenn man die Regel etwas lockerer macht (z. B. auf 2,4-fache Wiederholung), dann kann der Turm unendlich hoch wachsen! Die Forscher haben sogar gezeigt, wie man Türme baut, die so hoch sind, wie man will, solange man die Wiederholungs-Regel nicht zu streng macht.

2. Der Thue-Morse-Riese (Der berühmte Automat)

Es gibt eine sehr berühmte, unendliche Zahlenfolge, die Thue-Morse-Folge. Sie sieht aus wie ein zufälliges Muster, ist aber streng nach einem Algorithmus gebaut.
Die Forscher haben sich gefragt: „Wie viele perfekte Klammer-Schnüre (Dyck-Wörter) finden wir in diesem riesigen Thue-Morse-Muster?"

Die Entdeckung:

• Sie haben eine Art „Schnürsenkel-Formel" gefunden. Jedes perfekte Klammer-Stück in diesem Muster entspricht genau einem bestimmten Bauplan.
• Sie haben bewiesen, dass die maximale Tiefe (wie viele Klammern ineinander stecken) in diesem speziellen Muster niemals größer als 2 ist. Es ist also wie ein zweistöckiges Haus, das sich unendlich weit in die Länge zieht, aber nie höher wird.
• Sie haben auch eine Formel entwickelt, um genau zu zählen: Wie viele Klammer-Schnüre der Länge 2, 4, 6, 8... gibt es? Die Antwort folgt einem komplexen, aber berechenbaren Muster.

3. Der Computer als Detektiv (Walnut)

Wie können Menschen so komplexe Beweise führen? Die Autoren nutzen ein Werkzeug namens Walnut.
Die Analogie:
Stellen Sie sich Walnut als einen super-intelligenten Roboterdetektiv vor.

• Sie geben dem Roboter die Regeln des Musters (z. B. „Thue-Morse") und die Frage („Gibt es hier eine Klammer-Schnur der Länge 1000?").
• Der Roboter baut sich automatisch ein kleines Labyrinth (einen endlichen Automaten), durch das er läuft. Wenn er am Ende ankommt, ist die Antwort „Ja". Wenn er stecken bleibt, ist die Antwort „Nein".
• Mit diesem Roboter haben die Autoren Beweise geführt, die für einen Menschen zu kompliziert wären, weil sie zu viele Fälle prüfen müssten. Der Roboter hat in Sekunden bewiesen, dass bestimmte Muster niemals auftreten können.

4. Andere Welten (Fibonacci und Rudin-Shapiro)

Die Forscher haben ihre Klammer-Suche auch in anderen berühmten Mustern durchgeführt:

• Die Fibonacci-Welt: Hier ist es sehr langweilig. Es gibt fast keine perfekten Klammer-Schnüre. Nur ganz kurze, einfache wie 01 oder 0101 kommen vor. Es ist, als ob in diesem Universum die Architektur so streng ist, dass keine komplexen Gebäude erlaubt sind.
• Die Rudin-Shapiro-Welt: Hier ist es genau das Gegenteil! In diesem Muster gibt es Klammer-Schnüre, die unendlich tief verschachtelt sind. Man kann Türme bauen, die in den Himmel ragen. Die Forscher haben gezeigt, dass man genau vorhersagen kann, an welchen Stellen diese tiefen Türme stehen.

---

Zusammenfassung: Was bedeutet das alles?

Diese Arbeit ist wie eine Kartenzeichnung für ein Land aus Klammern.

1. Sie zeigt uns, wie tief wir in ein Muster „hineinfallen" können, bevor wir auf eine Barriere stoßen (die 7/3-Regel).
2. Sie erklärt, wie man die Anzahl der perfekten Klammer-Schnüre in riesigen, computergenerierten Welten (wie Thue-Morse) genau berechnet.
3. Sie demonstriert, wie moderne Computer (der Roboter Walnut) helfen können, mathematische Geheimnisse zu lüften, die für das menschliche Gehirn zu groß sind.

Der Kerngedanke: Selbst in scheinbar chaotischen, unendlichen Mustern gibt es strenge Gesetze, die bestimmen, wie tief und komplex unsere „Klammer-Türme" sein dürfen. Und manchmal, wenn man die Regeln ein wenig ändert, öffnen sich Türen zu unendlichen Höhen.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Artikels „Dyck words, pattern avoidance, and automatic sequences" von Lucas Mol, Narad Rampersad und Jeffrey Shallit auf Deutsch.

Titel und Kontext

Titel: Dyck-Wörter, Mustervermeidung und automatische Folgen
Veröffentlicht in: Communications in Mathematics, 33 (2025), Nr. 2.
Thema: Die Untersuchung von Dyck-Wörtern (ausgeglichene Klammerfolgen) innerhalb von binären Folgen, insbesondere im Kontext von Mustervermeidung (Vermeidung von Wiederholungen) und der Theorie der automatischen Folgen.

---

1. Problemstellung und Motivation

Die Autoren untersuchen das Vorkommen von Dyck-Wörtern in unendlichen binären Folgen. Dabei wird die 0 als linke Klammer und die 1 als rechte Klammer interpretiert. Ein Wort ist ein Dyck-Wort, wenn es eine ausgeglichene Klammerfolge darstellt (d.h. die Anzahl der 0s und 1s ist gleich, und in jedem Präfix überwiegen die 0s).

Zentrale Fragen der Arbeit sind:

1. Schachtelungstiefe (Nesting Level): Wie tief können Dyck-Wörter in Folgen sein, die bestimmte Wiederholungsmuster (Powers) vermeiden?
2. Charakterisierung: Welche Faktoren der Thue-Morse-Folge sind Dyck-Wörter?
3. Zählung: Wie viele Dyck-Faktoren einer bestimmten Länge existieren in der Thue-Morse-Folge?
4. Verallgemeinerung: Wie verhält sich dies bei anderen automatischen Folgen (z. B. Rudin-Shapiro, Fibonacci)?

Ein besonderes Interesse gilt der Beziehung zwischen der Vermeidung von $7/3$-Potenzen (Wiederholungen mit Exponent$\ge 7/3$) und der maximalen Schachtelungstiefe.

---

2. Methodik

Die Arbeit kombiniert kombinatorische Beweise mit einer starken computergestützten Methode:

• Theoretische Konstruktion: Entwicklung von Morphismen (Ersetzungssystemen), um Dyck-Wörter mit spezifischen Eigenschaften (z. B. schachtelungstiefenabhängig) zu konstruieren.
• Walnut-Theorembeweiser: Ein Großteil der Beweise wird mit Hilfe von Walnut geführt. Walnut ist ein Theorembeweiser für automatische Folgen, der auf der Theorie der Presburger-Arithmetik und endlichen Automaten basiert.
  • Die Autoren formulieren Eigenschaften (wie das Vorhandensein von Dyck-Faktoren oder deren Schachtelungstiefe) als erste-Ordnung-Logikformeln.
  • Walnut überprüft diese Formeln automatisch und konstruiert zugehörige endliche Automaten (DFAO).
• Lineare Darstellungen: Zur Zählung der Dyck-Faktoren werden lineare Darstellungen (Matrix-Morphismen) verwendet, um zu zeigen, dass die Zählfolge eine $k$-reguläre Folge ist.

---

3. Wichtige Beiträge und Ergebnisse

A. Wiederholungsvermeidung und Schachtelungstiefe

• Theorem 2.1: Jedes binäre Wort, das **$7/3$-power-frei** ist (keine Wiederholungen mit Exponent$\ge 7/3$ enthält) und ein Dyck-Wort ist, hat eine Schachtelungstiefe von höchstens 3.
  • Beweisidee: Durch Analyse der Struktur von Dyck-Wörtern und der Notwendigkeit, bestimmte Muster (wie $000$oder$111$) zu vermeiden, wird gezeigt, dass tiefere Verschachtelungen unweigerlich zu Verletzungen der$7/3$-Bedingung führen.
• Optimalität: Das Ergebnis ist scharf. Es gibt $7/3^+$-power-freie Dyck-Wörter (Vermeidung von Exponenten$> 7/3$) mit beliebig großer Schachtelungstiefe.
  • Konstruktion: Die Autoren definieren zwei Morphismen $g$ (ternär) und $f$ (binär). Die Folge $f(g^\omega(0))$ ist ein $7/3^+$-power-freies Dyck-Wort mit Schachtelungstiefe$2t+2$für den$t$-ten Iterationsschritt. Der Beweis der Power-Freiheit wurde mit Walnut durchgeführt (benötigte 130 GB RAM und über 5 Stunden Rechenzeit).

B. Dyck-Faktoren der Thue-Morse-Folge

Die Thue-Morse-Folge $t$ ist eine der bekanntesten automatischen Folgen.

• Charakterisierung (Theorem 3.1): Die Dyck-Faktoren von $t$ sind exakt die Wörter der Form $h(x)$, wobei $x$ ein Faktor einer bestimmten ternären Folge $s$ ist und $h$ ein definierter Morphismus ist ($h(0)=01, h(1)=0011, h(2)=001011$).
• Schachtelungstiefe: Als Konsequenz daraus haben alle Dyck-Faktoren der Thue-Morse-Folge eine Schachtelungstiefe von höchstens 2.
• Zählung: Sei $d(n)$ die Anzahl der Dyck-Faktoren der Länge $2n$ in der Thue-Morse-Folge.
  • Theorem 4.5 & 4.6: Die Folge $(d(n))_{n \ge 0}$ ist eine 2-reguläre Folge. Dies bedeutet, dass sie durch eine lineare Darstellung (Matrix-Morphismus) beschrieben werden kann.
  • Die Autoren leiten eine lineare Darstellung vom Rang 7 ab, die eine effiziente Berechnung von $d(n)$ ermöglicht.
• Schranken für $d(n)$ (Theorem 5.2 & 5.3):
  • Obere Schranke: $d(n) \le n$ für alle $n \ge 1$. Diese Schranke ist scharf für $n = 3 \cdot 2^i$.
  • Untere Schranke: $d(n) \ge n/2$ für alle $n \ge 0$.
  • Durchschnittswert: Der durchschnittliche Wert von $d(n)$ wächst asymptotisch wie $\frac{19}{24}n$.

C. Andere Automatische Folgen

• Fibonacci-Wort: Enthält nur die trivialen Dyck-Wörter $01$und$0101$ (Proposition 6.1).
• Period-Doubling-Folge: Enthält $01, 0101, 010101$ (Proposition 6.2).
• Rudin-Shapiro-Folge:
  • Im Gegensatz zur Thue-Morse-Folge enthält die Rudin-Shapiro-Folge Dyck-Faktoren mit beliebig großer Schachtelungstiefe (Theorem 6.3).
  • Die Menge der Längen $n$, für die ein Dyck-Faktor existiert, ist eine 4-automatische Menge (Theorem 6.4). Dies erfordert eine Anpassung der Walnut-Methode, da die Rudin-Shapiro-Folge nicht für Basis 2 „running-sum synchronized" ist, wohl aber für Basis 4.

---

4. Signifikanz und Bedeutung

1. Verbindung von Kombinatorik und Logik: Die Arbeit demonstriert eindrucksvoll, wie moderne Theorembeweiser (Walnut) komplexe kombinatorische Probleme lösen können, die für manuelle Beweise zu schwerfällig wären (z. B. der Nachweis der $7/3^+$-Power-Freiheit bei hoher Schachtelungstiefe).
2. Schärfung von Grenzen: Die Ergebnisse zur $7/3$-Power-Freiheit definieren eine klare Grenze: Sobald der Exponent$7/3$überschritten wird (im Sinne von$7/3^+$), bricht die Beschränkung der Schachtelungstiefe zusammen.
3. Reguläre Folgen: Die Erkenntnis, dass die Anzahl der Dyck-Faktoren in der Thue-Morse-Folge eine reguläre Folge ist, erweitert das Verständnis der strukturellen Eigenschaften dieser fundamentalen Folge. Die Bereitstellung der linearen Darstellung ermöglicht effiziente Algorithmen zur Berechnung dieser Werte.
4. Methodische Erweiterung: Die Arbeit zeigt, wie man mit „running-sum synchronized" Folgen umgeht und wie man auch bei Folgen, die diese Eigenschaft nicht direkt erfüllen (wie Rudin-Shapiro), durch Basiswechsel (Basis 4) dennoch automatische Methoden anwenden kann.

Zusammenfassung

Der Artikel liefert eine umfassende Analyse von Dyck-Wörtern in der Welt der automatischen Folgen. Er stellt scharfe Grenzen für die Schachtelungstiefe unter Wiederholungsvermeidungsbedingungen auf, charakterisiert exakt die Dyck-Struktur der Thue-Morse-Folge und liefert präzise asymptotische Schranken für deren Häufigkeit. Die Arbeit ist ein Paradebeispiel für die erfolgreiche Anwendung computergestützter Beweistechniken in der diskreten Mathematik.