2025-11-10T03:15:48.044021

Balanced Fibonacci word rectangles, and beyond

Shallit, Vukusic
Following a recent paper of Anselmo et al., we consider $m \times n$ rectangular matrices formed from the Fibonacci word, and we show that their balance properties can be solved with a finite automaton. We also generalize the result to every Sturmian characteristic word corresponding to a quadratic irrational. Finally, we also examine the analogous question for the Tribonacci word.
academic

Ausgeglichene Fibonacci-Wort-Rechtecke und darüber hinaus

Grundlegende Informationen

  • Papier-ID: 2509.25994
  • Titel: Balanced Fibonacci word rectangles, and beyond
  • Autoren: Jeffrey Shallit (University of Waterloo), Ingrid Vukusic (University of York)
  • Klassifizierung: math.NT cs.DM cs.FL math.CO
  • Veröffentlichungsdatum: 15. Oktober 2025 (ArXiv-Preprint)
  • Papierlink: https://arxiv.org/abs/2509.25994

Zusammenfassung

Dieses Papier baut auf neuesten Forschungen von Anselmo et al. auf und untersucht m×nm \times n rechteckige Matrizen, die aus Fibonacci-Wörtern gebildet werden. Es wird bewiesen, dass ihre Ausgeglichenheitseigenschaften mittels endlicher Automaten gelöst werden können. Die Forschung verallgemeinert die Ergebnisse weiter auf alle Sturmian-Charakteristikwörter, die quadratischen Irrationalzahlen entsprechen, und untersucht analoge Probleme für Tribonacci-Wörter.

Forschungshintergrund und Motivation

Problemdefinition

Das Kernproblem dieser Forschung ist die Ausgeglichenheit von Wort-Rechtecken: Gegeben eine unendliche Sequenz (ai)i≥0(a_i)_{i≥0}, konstruiert man eine unendliche Matrix A=(ak,ℓ)k,ℓ≥0A = (a_{k,\ell})_{k,\ell≥0}, wobei ak,ℓ=ak+ℓa_{k,\ell} = a_{k+\ell}. Für eine m×nm \times n Untermatrix A(i,m,n)A(i,m,n) ist die Summe aller Elemente: T(i,m,n):=∑k=0m−1∑ℓ=0n−1ai+k+ℓT(i,m,n) := \sum_{k=0}^{m-1}\sum_{\ell=0}^{n-1} a_{i+k+\ell}

Die Ausgeglichenheitsfrage lautet: Für welche (m,n)(m,n)-Paare haben alle T(i,m,n)T(i,m,n)-Werte höchstens zwei verschiedene Werte?

Forschungsmotivation

  1. Theoretische Bedeutung: Fibonacci-Wörter sind klassische Objekte der Kombinatorik, deren Ausgeglichenheitseigenschaften eng mit Zahlentheorie und Automatentheorie verbunden sind
  2. Bestehende Einschränkungen: Anselmo et al. haben bewiesen, dass Rechtecke ausgeglichen sind, wenn max⁡(m,n)\max(m,n) eine Fibonacci-Zahl ist, aber eine vollständige Charakterisierung fehlt noch
  3. Methodische Innovation: Die Verwendung endlicher Automaten zur Lösung solcher Probleme bietet neue Rechenwerkzeuge

Kernbeiträge

  1. Vollständige Charakterisierung: Vollständige automatische Charakterisierung der Ausgeglichenheit von Fibonacci-Wort-Rechtecken (Satz 2 und Folgerung 3)
  2. Verallgemeinerte Ergebnisse: Verallgemeinerung auf alle Sturmian-Wörter, die quadratischen Irrationalzahlen entsprechen (Satz 2)
  3. Algorithmische Implementierung: Konkrete Implementierung und Verifikation basierend auf Walnut-Software
  4. Dichteresultate: Beweis der Dichteigenschaften ausgeglichener Paare (m,n)(m,n) (Proposition 6)
  5. Tribonacci-Erweiterung: Untersuchung analoger Probleme für Tribonacci-Wörter (Satz 10)

Methodische Details

Aufgabendefinition

Gegeben eine unendliche Sequenz (ai)i≥0(a_i)_{i≥0}, konstruiert man eine Hankel-Matrix:

a_i & a_{i+1} & \cdots & a_{i+n-1} \\ a_{i+1} & a_{i+2} & \cdots & a_{i+n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{i+m-1} & a_{i+m} & \cdots & a_{i+m+n-2} \end{pmatrix}$$ Ziel: Bestimmung, welche $(m,n)$-Paare dazu führen, dass alle $T(i,m,n)$-Werte höchstens zwei verschiedene Werte haben. ### Theoretischer Kernrahmen #### Eigenschaften von Sturmian-Wörtern Für Sturmian-Wörter definiert man $\Delta(i,m,n) := T(i+1,m,n) - T(i,m,n)$, wobei: $$\Delta(i,m,n) \in \{-1, 0, 1\}$$ **Schlüssellemma 1**: $(m,n)$ ist ausgeglichen genau dann, wenn die Sequenz $(\Delta(i,m,n))_{i≥0}$ keine Blöcke der Form $1,0,0,\ldots,0,1$ oder $-1,0,0,\ldots,0,-1$ enthält. #### Automaten-Methode Für eine quadratische Irrationalzahl $\alpha$ existiert ein endlicher Automat $M$, der als Eingabe die Ostrowski-$\alpha$-adische Darstellung von $n$ und $x$ nimmt und akzeptiert genau dann, wenn $x = \lfloor n\alpha \rfloor$. **Hauptsatz 2**: Es existiert ein Algorithmus, der für eine gegebene quadratische Irrationalzahl $\alpha \in (0,1)$ einen endlichen Automaten konstruiert. Dieser nimmt als Eingabe die Ostrowski-$\alpha$-adische Darstellung von $(m,n)$-Paaren und akzeptiert genau dann, wenn der $m \times n$-Block ausgeglichen ist. ### Technische Innovationen 1. **Automatische Implementierung des Ausgeglichenheitskriteriums**: Umwandlung der Bedingungen aus Lemma 1 in Formeln der ersten Ordnung und dann in Automaten 2. **Zeckendorf-Darstellungsbehandlung**: Geschickte Behandlung negativer Zahlen mittels $T(i+1,m,n) - T(i,m,n) + 1 \in \{0,1,2\}$ 3. **Walnut-Implementierung**: Vollständige Code-Implementierung, die einen 15-Zustands-Automaten erzeugt ## Experimentelle Einrichtung ### Werkzeuge und Implementierung - **Walnut-Software**: Spezialisiertes Werkzeug zur Automatenkonstruktion und Verifikation - **Zeckendorf-Darstellung**: Standarddarstellungssystem für Fibonacci-Zahlen - **Tribonacci-Darstellung**: Für die Analyse von Tribonacci-Wörtern ### Verifikationsmethoden 1. **Automatenkonstruktion**: Erzeugung des bal-Automaten durch Walnut (15 Zustände) 2. **Theoremverifikation**: Verifikation der Ergebnisse von Anselmo et al. als Spezialfälle 3. **Dichteanalyse**: Berechnung der Verteilungseigenschaften ausgeglichener Paare ## Experimentelle Ergebnisse ### Hauptergebnisse für Fibonacci-Wörter **Folgerung 3**: Der 15-Zustands-Automat in Abbildung 1 löst das Ausgeglichenheitsproblem für Fibonacci-Wort-Rechtecke vollständig. **Folgerung 4**: Verifikation des Satzes von Anselmo et al.: Wenn $\max(m,n)$ eine Fibonacci-Zahl ist, dann ist die $m \times n$-Matrix ausgeglichen. ### Strukturelle Eigenschaften **Proposition 5**: Für $n ≥ 2$: - $(i,j)$ ist ausgeglichen genau dann, wenn $(i',j)$ ausgeglichen ist, wobei $F_{n+1} < i,i' < F_{n+2}$ und $j ≥ F_{n-1}$ - $(F_{n+1}+i,j)$ ist ausgeglichen genau dann, wenn $(F_{n+2}-i,j)$ ausgeglichen ist **Proposition 6** (Dichteresultat): Wenn $F_i < m ≤ F_{i+1}$, dann existiert für alle $n ≥ 1$ ein $j$, $1 ≤ j ≤ F_{i+1}$, so dass $(m,n+j)$ ausgeglichen ist. ### Vielfältigkeitsergebnisse **Satz 8**: Für $m = n = F_{3k}/2$ ist die Anzahl der verschiedenen Werte von $T(i,m,n)$ mindestens $k+1$. **Folgerung 9**: Die Anzahl der verschiedenen Werte von $T(i,F_{3n}/2,F_{3n}/2)$ ist $\Theta(n)$. ### Tribonacci-Wort-Ergebnisse **Satz 10**: Angenommen $m ≤ n$: - Wenn $m = 1$, sind alle $m \times n$-Rechtecke 2-ausgeglichen - Wenn $m = 2$, existiert ein 77-Zustands-Automat, der alle $n$ akzeptiert, für die das $m \times n$-Rechteck 2-ausgeglichen ist - Wenn $m ≥ 3$, existiert kein $n$, das das $m \times n$-Rechteck 2-ausgeglichen macht ## Verwandte Arbeiten 1. **Sturmian-Wort-Theorie**: Aufbauend auf klassischen Arbeiten von Berstel, Brown und anderen 2. **Ausgeglichenheitsforschung**: Erweiterung der Forschung von Vuillon et al. zur Wort-Ausgeglichenheit 3. **Automaten-Methode**: Nutzung der Theorie p-erkennbarer Mengen von Bruyère et al. 4. **Fibonacci-Wort-Eigenschaften**: Basierend auf umfangreicher bestehender Forschung zu Fibonacci-Wörtern ## Schlussfolgerungen und Diskussion ### Hauptschlussfolgerungen 1. Vollständige Lösung des Ausgeglichenheitsproblems für Fibonacci-Wort-Rechtecke mit 15-Zustands-Automat-Charakterisierung 2. Methode ist verallgemeinerbar auf alle Sturmian-Wörter, die quadratischen Irrationalzahlen entsprechen 3. Der Fall von Tribonacci-Wörtern ist komplexer und erfordert 77-Zustands-Automaten für $m=2$ ### Einschränkungen 1. Methode ist nur auf Sturmian-Wörter anwendbar, die quadratischen Irrationalzahlen entsprechen 2. Vollständige Charakterisierung von Tribonacci-Wörtern bleibt komplex 3. Höherwertige Fälle (wie Tribonacci mit $m≥3$) können möglicherweise keine Lösung haben ### Zukünftige Richtungen 1. Verallgemeinerung auf allgemeinere morphische Wörter 2. Untersuchung höherdimensionaler Fälle 3. Optimierung der Automatenzustandszahl ## Tiefgreifende Bewertung ### Stärken 1. **Theoretische Vollständigkeit**: Vollständige Lösung des Ausgeglichenheitsproblems für Fibonacci-Wörter 2. **Methodische Innovation**: Geschickte Kombination von Automatentheorie und Kombinatorik 3. **Praktische Anwendbarkeit**: Konkrete algorithmische Implementierung und Verifikationswerkzeuge 4. **Tiefgreifende Ergebnisse**: Offenlegung der tieferen Verbindung zwischen Ausgeglichenheit und zahlentheoretischen Eigenschaften ### Schwächen 1. **Komplexität**: Die Automaten-Methode ist zwar vollständig, aber möglicherweise nicht intuitiv genug 2. **Verallgemeinerungsgrenzen**: Nur auf spezifische Arten von Irrationalzahlen anwendbar 3. **Rechenkomplexität**: Zeitkomplexität des Automaten wird nicht detailliert analysiert ### Einflussfaktor 1. **Theoretischer Beitrag**: Bietet neue Perspektiven für interdisziplinäre Forschung zwischen Kombinatorik und Automatentheorie 2. **Praktischer Wert**: Walnut-Implementierung macht Ergebnisse verifizierbar und erweiterbar 3. **Methodologische Bedeutung**: Zeigt, wie Automaten zur Lösung komplexer kombinatorischer Probleme eingesetzt werden können ### Anwendungsszenarien 1. Ausgeglichenheitsforschung in der Kombinatorik 2. Anwendungen der Automatentheorie 3. Untersuchung von Irrationalzahlen-Eigenschaften in der Zahlentheorie 4. Entscheidungsprobleme im Algorithmendesign ## Literaturverzeichnis Das Papier zitiert 19 wichtige Referenzen, hauptsächlich: - Klassische Werke von Allouche & Shallit zu automatischen Sequenzen - Grundlegende Arbeiten von Berstel zu Fibonacci-Wörtern und Sturmian-Wörtern - Neueste verwandte Forschung von Anselmo et al. - Relevante Literatur zu Automatentheorie und Zahlentheorie --- Dieses Papier findet ein gutes Gleichgewicht zwischen theoretischer Tiefe und praktischer Anwendbarkeit. Es löst nicht nur ein konkretes kombinatorisches Problem, sondern demonstriert auch die Leistungsfähigkeit der Automaten-Methode bei der Behandlung solcher Probleme. Die vollständige Implementierung und Verifikation verleiht den Ergebnissen hohe Glaubwürdigkeit und praktischen Wert.