🔢 mathematics

Balanced Fibonacci word rectangles, and beyond

Dieser Artikel zeigt, dass die Balance-Eigenschaften rechteckiger Matrizen aus dem Fibonacci-Wort durch einen endlichen Automaten entschieden werden können, verallgemeinert dieses Ergebnis auf Sturmische charakteristische Wörter quadratischer Irrationalzahlen und untersucht analoge Fragen für das Tribonacci- und das Thue-Morse-Wort.

Ursprüngliche Autoren: Jeffrey Shallit, Ingrid Vukusic

Veröffentlicht 2026-03-31

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Jeffrey Shallit, Ingrid Vukusic

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

Stellen Sie sich vor, Sie haben eine unendliche Kette aus Perlen, die nur aus zwei Farben bestehen: Schwarz (0) und Weiß (1). Diese Kette folgt einer ganz bestimmten, mathematischen Regel, die man die Fibonacci-Wort-Kette nennt. Sie sieht ungefähr so aus: Schwarz-Weiß-Schwarz-Schwarz-Weiß-Schwarz-Weiß-Schwarz...

Nun nehmen wir diese Kette und legen sie nicht nur in einer Reihe aus, sondern stapeln sie zu einem riesigen, unendlichen Gitter (einer Matrix). Stellen Sie sich vor, Sie schneiden aus diesem Gitter immer wieder kleine Rechtecke heraus. Ein Rechteck könnte 4 Zeilen und 6 Spalten haben, ein anderes 10 Zeilen und 100 Spalten.

Die Frage, die sich die Autoren dieses Papiers stellen, ist ganz einfach: Sind diese Rechtecke „ausgewogen"?

Das Problem: Der Gleichgewichtszustand

Ein Rechteck ist „ausgewogen" (oder balanced), wenn die Anzahl der schwarzen und weißen Perlen in jedem solchen Rechteck fast immer gleich ist, egal wo Sie es auf dem Gitter ausschneiden.

Wenn Sie ein Rechteck an einer Stelle ausschneiden und es hat 10 schwarze und 10 weiße Perlen.
Und Sie ein gleich großes Rechteck an einer ganz anderen Stelle ausschneiden, sollte es auch etwa 10 schwarze und 10 weiße Perlen haben.
Wenn es aber vorkommt, dass das eine Rechteck 15 schwarze und das andere nur 5 hat, dann ist das Rechteck nicht ausgewogen.

Die Autoren wollen herausfinden: Für welche Größen (Breite und Höhe) sind diese Rechtecke immer fair verteilt?

Die Lösung: Ein digitaler Detektiv (Automat)

Früher war es sehr schwer, das für alle möglichen Rechteckgrößen zu berechnen. Die Autoren haben jedoch einen genialen Trick angewendet. Sie haben einen digitalen Detektiv (einen sogenannten endlichen Automaten) gebaut.

Stellen Sie sich diesen Automaten wie einen sehr strengen, aber klugen Kassenautomaten vor:

Sie geben ihm zwei Zahlen ein: die gewünschte Breite ( $m$ ) und die gewünschte Höhe ( $n$ ) des Rechtecks.
Der Automat rechnet im Kopf nach (basierend auf den speziellen Regeln der Fibonacci-Kette).
Er drückt einen grünen Knopf, wenn das Rechteck ausgewogen ist.
Er drückt einen roten Knopf, wenn es nicht ausgewogen ist.

Das Tolle an diesem Papier ist, dass sie nicht nur für die Fibonacci-Kette einen solchen Detektiv gebaut haben, sondern gezeigt haben, wie man ihn für viele andere ähnliche mathematische Ketten (wie die Tribonacci- oder Thue-Morse-Ketten) bauen kann.

Die Entdeckungen im Detail

Hier sind die wichtigsten Ergebnisse, übersetzt in Alltagssprache:

1. Für die Fibonacci-Kette (Die klassische Perlenkette):
Die Autoren haben herausgefunden, dass es keine einfache Regel wie „alle geraden Zahlen funktionieren" gibt. Stattdessen hängt es von der speziellen Art und Weise ab, wie man die Zahlen in Fibonacci-Zahlen zerlegt (ähnlich wie man Geld in Münzen zerlegt).

Beispiel: Ein Rechteck mit 4 Zeilen und 18 Spalten ist fair. Ein Rechteck mit 2 Zeilen und 4 Spalten ist es nicht.
Der von ihnen gebaute Automat (ein Diagramm mit 15 Zuständen) kann jede beliebige Kombination sofort prüfen.

2. Für die Tribonacci-Kette (Die dreifarbige Kette):
Hier gibt es drei Farben (0, 1, 2). Die Frage ist: Sind die Rechtecke fair verteilt, wenn man alle drei Farben zählt?

Ergebnis: Wenn das Rechteck nur 1 Zeile hoch ist, ist es immer fair.
Wenn es 2 Zeilen hoch ist, gibt es eine Liste von erlaubten Breiten (die der Automat prüft).
Aber: Sobald das Rechteck 3 Zeilen oder mehr hat, ist es niemals fair verteilt. Es gibt immer eine Stelle im Gitter, wo die Farben ganz anders verteilt sind als anderswo. Das ist wie ein Würfel, der ab einer bestimmten Größe immer schief fällt.

3. Für die Thue-Morse-Kette (Die symmetrische Kette):
Diese Kette hat eine besondere Eigenschaft: Sie ist fast perfekt symmetrisch.

Hier konnten die Autoren beweisen, dass die Rechtecke immer sehr fair sind. Die Abweichung ist winzig (höchstens 4 Perlen Unterschied).
Sie haben sogar einen riesigen, komplexen Detektiv (mit 92 Zuständen) gebaut, der genau sagt, wie „unfair" ein Rechteck maximal sein kann, basierend auf seiner Größe.

Warum ist das wichtig?

Auf den ersten Blick klingt das nach reinem Mathematik-Spaß. Aber diese Art von Mustern taucht überall auf:

In der Kryptographie (Verschlüsselung), wo man zufällig wirkende, aber berechenbare Folgen braucht.
In der Physik, bei der Anordnung von Atomen in speziellen Kristallen (Quasikristalle).
In der Informatik, um Algorithmen zu optimieren, die mit Datenströmen arbeiten.

Zusammenfassung in einer Metapher

Stellen Sie sich vor, Sie sind ein Architekt, der unendliche Teppiche webt.

Die Fibonacci-Teppiche haben ein komplexes Muster. Die Autoren haben einen Scanner gebaut, der sofort sagt: „Wenn du diesen Teppich in Rechtecke von Größe 4x18 schneidest, sieht das Muster überall gleich aus. Wenn du ihn in 2x4 schneidest, sieht es an manchen Stellen ganz anders aus."
Bei den Tribonacci-Teppichen haben sie entdeckt: „Solange du nur dünne Streifen (1 Zeile) schneidest, ist alles okay. Aber sobald du einen dicken Block (3 Zeilen) nimmst, wird das Muster an den Rändern immer chaotisch."
Bei den Thue-Morse-Teppichen sagten sie: „Diese Teppiche sind so perfekt gewebt, dass egal wie groß das Rechteck ist, das Muster nie wirklich schief wird."

Die Autoren haben also nicht nur die Teppiche untersucht, sondern die Werkzeuge (die Automaten) entwickelt, mit denen man diese Muster für fast jede denkbare mathematische Kette analysieren kann. Sie haben gezeigt, dass man mit Computern und Logik tief in die Geheimnisse dieser unendlichen Zahlenfolgen eindringen kann.

1. Problemstellung

Das Paper untersucht die Balance-Eigenschaft von rechteckigen Matrizen, die aus unendlichen Folgen (Wörtern) über dem Alphabet $\{0, 1\}$ (und erweitert auf größere Alphabete) konstruiert werden.

Konstruktion: Gegeben eine unendliche Folge $(a_i)_{i \ge 0}$ wird eine unendliche Matrix $A$ definiert durch $a_{k,\ell} = a_{k+\ell}$ . Ein $m \times n$ -Rechteck $A(i, m, n)$ ist eine Submatrix, die bei Index $i$ beginnt.
Definition der Balance: Die $m \times n$ -Rechtecke heißen balanciert, wenn die Summe aller Einträge in diesen Rechtecken (bezeichnet als $T(i, m, n)$ ) über alle Startindizes $i$ hinweg höchstens zwei verschiedene Werte annimmt.
Ziel: Zu bestimmen, für welche Paare natürlicher Zahlen $(m, n)$ die Rechtecke einer gegebenen Folge balanciert sind.
Kontext: Während für binäre Wörter die Balance (Unterschied der Anzahl von 1en in Blöcken gleicher Länge) gut untersucht ist, ist die zweidimensionale Balance eine neuere Verfeinerung. Für die Fibonacci-Folge war bekannt, dass bestimmte Paare (z. B. wenn $\max(m, n)$ eine Fibonacci-Zahl ist) balanciert sind, aber eine vollständige Charakterisierung fehlte.

2. Methodik

Die Autoren verwenden einen automatenbasierten Ansatz, der auf der Theorie der Sturmischen Wörter und der Ostrowski-Numerierung basiert.

Sturmische Wörter: Diese werden durch $a_i = \lfloor (i+1)\alpha \rfloor - \lfloor i\alpha \rfloor$ für ein irrationales $\alpha \in (0, 1)$ definiert. Die Fibonacci-Folge entspricht $\alpha = \gamma = (3-\sqrt{5})/2$ .
Reduktion auf Differenzen: Ein zentrales Lemma zeigt, dass die Rechtecke balanciert sind genau dann, wenn die Differenzfolge $\Delta(i, m, n) = T(i+1, m, n) - T(i, m, n)$ keine Blöcke der Form $1, 0, \dots, 0, 1$ oder $-1, 0, \dots, 0, -1$ enthält.
Endliche Automaten & Walnut:
- Da $\alpha$ eine quadratische Irrationalzahl ist, existiert ein Algorithmus, um einen endlichen Automaten zu konstruieren, der die Beziehung $x = \lfloor n\alpha \rfloor$ erkennt (unter Verwendung des Ostrowski- $\alpha$ -Systems).
- Die Autoren nutzen die Software Walnut, ein Werkzeug zur automatischen Beweissührung in der Theorie der endlichen Automaten und der ersten Ordnung Logik.
- Die Balance-Bedingung wird als logische Formel formuliert, die in einen endlichen Automaten übersetzt wird. Dieser Automat akzeptiert genau die Paare $(m, n)$ (dargestellt im jeweiligen Numerierungssystem), für die die Balance gilt.
Erweiterung auf andere Folgen: Für die Tribonacci-Folge und die Thue-Morse-Folge werden angepasste Methoden verwendet, da diese nicht direkt Sturmisch sind, aber ähnliche strukturelle Eigenschaften aufweisen.

3. Wichtige Beiträge und Ergebnisse

A. Fibonacci-Wort (Sturmische Wörter)

Hauptsatz (Theorem 2): Es existiert ein Algorithmus, der für jedes quadratische Irrational $\alpha$ einen endlichen Automaten konstruiert, der die Menge der balancierten Paare $(m, n)$ entscheidet.
Konkrete Lösung für Fibonacci: Für die Fibonacci-Folge wurde ein 15-Zustände-Automat (siehe Abbildung 1 im Paper) konstruiert, der alle balancierten Paare $(m, n)$ im Zeckendorf-System (Fibonacci-Darstellung) erkennt.
Korollar 4: Der Satz von Anselmo et al. (dass $\max(m, n)$ eine Fibonacci-Zahl impliziert Balance) wird als Spezialfall dieses Automaten bewiesen.
Strukturelle Eigenschaften: Es werden neue Eigenschaften abgeleitet, z. B. dass die Dichte der balancierten $n$ -Werte für ein festes $m$ durch $\approx 1/(\phi m)$ nach unten beschränkt ist.
Vielfalt der Werte (Theorem 8): Für quadratische Rechtecke mit Seitenlänge $F_{3k/2}$ wächst die Anzahl der verschiedenen Summenwerte $T(i, m, n)$ linear mit $k$ (genauer $\Theta(k)$ ), was zeigt, dass die Balance nicht trivial ist und die Anzahl der Werte für große Rechtecke unbeschränkt wachsen kann.

B. Tribonacci-Wort

Die Autoren untersuchen die 2-Balance (Unterschied der Häufigkeit von Symbolen in Blöcken ist $\le 2$ ) für Rechtecke der Tribonacci-Folge.
Theorem 10:
- Für $m=1$ : Alle Rechtecke sind 2-balanciert.
- Für $m=2$ : Es existiert ein 77-Zustände-Automat, der die balancierten $n$ bestimmt. Die Liste der $n$ ist komplex und scheint keine einfache Beschreibung zu haben.
- Für $m \ge 3$ : Es gibt keine $n$ , für die die Rechtecke 2-balanciert sind. Dies wird durch die Konstruktion spezifischer unbalancierter $3 \times 3$ -Teilmatrizen bewiesen.

C. Thue-Morse-Wort

Hier wird die Balance für das Alphabet $\{0, 1\}$ untersucht.
Theorem 11: Es wird gezeigt, dass die Differenz $|2 \cdot |A(i, m, n)|_1 - mn|$ durch 4 beschränkt ist. Die Balance kann 1, 2, 3 oder 4 sein (0 ist unmöglich, da die Folge nicht periodisch ist).
Theorem 12: Ein 92-Zustände-Automat wurde konstruiert, der für gegebene $m, n$ (in Basis 2) die exakte Balance bestimmt.
Theorem 14: Für $m, n \ge 3$ ist die Balance genau dann 3, wenn sowohl $m$ als auch $n$ ungerade sind.
Rechenleistung: Die Berechnung erforderte erhebliche Ressourcen (ca. 12.834 Sekunden CPU-Zeit, 100 GB RAM), wobei der größte Zwischenschritt einen Automaten mit über 32 Millionen Zuständen hatte.

4. Signifikanz und Bedeutung

Algorithmische Charakterisierung: Das Paper liefert einen allgemeinen, algorithmischen Rahmen, um Balance-Eigenschaften in zweidimensionalen Strukturen über unendlichen Wörtern zu entscheiden. Dies geht über manuelle Beweise hinaus.
Verbindung von Logik und Automaten: Es demonstriert die Kraft der Kombination aus mathematischer Logik (Erststufige Logik), Zahlentheorie (Ostrowski-Systeme) und Automatentheorie (Walnut) zur Lösung komplexer kombinatorischer Probleme.
Erweiterung des Wissens: Es löst ein offenes Problem bezüglich der Fibonacci-Folge vollständig und erweitert die Analyse auf andere wichtige Folgen (Tribonacci, Thue-Morse), wobei es überraschende Ergebnisse liefert (z. B. das Fehlen von Balance für $m \ge 3$ bei Tribonacci).
Reproduzierbarkeit: Alle verwendeten Walnut-Code-Skripte und Maple-Dateien sind öffentlich zugänglich, was die Überprüfbarkeit und Weiterentwicklung der Ergebnisse fördert.

Zusammenfassend stellt das Paper einen Meilenstein in der Untersuchung der zweidimensionalen Balance von Folgen dar und zeigt, wie komplexe kombinatorische Eigenschaften durch endliche Automaten vollständig charakterisiert und algorithmisch gelöst werden können.