🔢 mathematics

Balanced Fibonacci word rectangles, and beyond

Dit artikel toont aan dat de balans eigenschappen van rechthoekige matrices gevormd uit het Fibonacci-woord, evenals die van Sturmian-woorden en andere woorden zoals het Tribonacci- en Thue-Morse-woord, kunnen worden bepaald met behulp van een eindige automaat.

Oorspronkelijke auteurs: Jeffrey Shallit, Ingrid Vukusic

Gepubliceerd 2026-03-31

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Jeffrey Shallit, Ingrid Vukusic

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Balans in de Wiskunde: Een Reis door Fibonacci, Tribonacci en de Kunst van de Rechthoek

Stel je voor dat je een oneindig lang lint hebt, bedrukt met alleen nullen en enen. Dit is geen willekeurig lint, maar een heel specifiek patroon dat bekendstaat als het Fibonacci-woord. Het ziet er zo uit: 01001010.... Wiskundigen vinden dit patroon fascinerend omdat het overal in de natuur voorkomt, van de schelpen van slakken tot de rangschikking van bloemblaadjes.

In dit artikel nemen de auteurs, Jeffrey Shallit en Ingrid Vukusic, je mee op een avontuur om te begrijpen hoe we dit oneindige lint in stukjes kunnen knippen en in rechthoekige vormen kunnen leggen, en of die vormen "in balans" zijn.

1. De Oneindige Muur van Getallen

Stel je een enorme muur voor, opgebouwd uit bakstenen. Elke baksteen heeft een nummer. Als je naar de muur kijkt, zie je een rij bakstenen: baksteen 0, baksteen 1, baksteen 2, enzovoort.

Nu gaan we een raam in deze muur maken. Een raam van bijvoorbeeld 3 rijen hoog en 4 bakstenen breed.

De eerste rij van je raam bevat bakstenen 0, 1, 2, 3.
De tweede rij begint één stap verder: bakstenen 1, 2, 3, 4.
De derde rij begint weer één stap verder: bakstenen 2, 3, 4, 5.

Dit noemen ze een rechthoek (of matrix). Als je dit raam over de muur schuift (naar rechts of naar beneden), verandert de inhoud van het raam. De vraag die de auteurs stellen is: Is de "som" van de bakstenen in elk raam ongeveer hetzelfde?

Als je in het ene raam veel "1-en" ziet en in het andere raam (dat net iets verder staat) veel "0-en", dan is er geen balans. Maar als het aantal "1-en" in elk raam altijd binnen een heel klein bereik blijft (bijvoorbeeld altijd tussen 4 en 6), dan noemen we die rechthoek in balans.

2. De Magische Robot (De Automaat)

De grootste uitdaging is dat het lint oneindig lang is. Je kunt niet elk raampje controleren, want dat zou eeuwen duren. Hoe weet je dan of een bepaald formaat (bijvoorbeeld 4x18) altijd in balans is?

De auteurs gebruiken een slimme truc: ze bouwen een digitale robot (in de wiskunde een "eindige automaat" genoemd).

Deze robot is als een zeer specifieke pincode-schakelaar.
Je voert twee getallen in: de hoogte ( $m$ ) en de breedte ( $n$ ) van je raam.
De robot kijkt naar deze getallen (in een speciale code, de "Zeckendorf-notatie", die lijkt op een manier om getallen te schrijven met alleen Fibonacci-getallen).
Als de robot groen licht geeft, betekent het: "Ja, elk raam van dit formaat is in balans."
Als hij rood licht geeft, betekent het: "Nee, hier zit een onevenwichtigheid in."

Het mooie is: deze robot is klein en simpel. Hij hoeft niet het hele oneindige lint te kennen; hij heeft alleen een paar regels nodig om te voorspellen of een bepaald formaat werkt.

3. De Drie Helden van het Verhaal

De auteurs testen hun methode op drie verschillende soorten "linten":

A. De Fibonacci-Held
Dit is de klassieke held. De auteurs hebben bewezen dat je met hun robot precies kunt voorspellen welke afmetingen werken.

Verrassing: Het bleek dat als de langste kant van je raam een Fibonacci-getal is (zoals 5, 8, 13), het raam altijd in balans is. Maar er zijn ook andere afmetingen die werken, zoals 4x3. De robot kan al deze gevallen onderscheiden.

B. De Tribonacci-Held
Dit lint is iets complexer. In plaats van alleen 0 en 1, gebruikt het ook het cijfer 2. Het patroon is: 0102010....

Hier ontdekten ze iets interessants: Als je raam 1 rij hoog is, is het altijd in balans.
Als je raam 2 rijen hoog is, is er een speciale lijst met breedtes die werken (zoals 1, 2, 3, 4, 7, 8...).
Maar als je raam 3 rijen of meer hoog is, is het nooit in balans. Het patroon is simpelweg te chaotisch voor grote, hoge rechthoeken.

C. De Thue-Morse-Held
Dit lint is een heel ander beestje: 01101001.... Het heeft een heel symmetrisch patroon.

Hier kunnen de auteurs een nog krachtigere robot bouwen. Deze robot kan niet alleen zeggen of een raam in balans is, maar ook precies hoe groot de onevenwichtigheid is (bijvoorbeeld: "de som verschilt maximaal met 4").
Ze ontdekten dat voor grote rechthoeken de onevenwichtigheid vaak precies 3 is, mits zowel de hoogte als de breedte oneven getallen zijn.

4. Waarom is dit belangrijk?

Je zou kunnen denken: "Wie zit er nou te rekenen met oneindige rechthoeken van nullen en enen?"

Het antwoord ligt in de voorspelbaarheid van patronen.
Stel je voor dat je een computerchip ontwerpt die data moet verwerken. Je wilt weten of bepaalde patronen van data (zoals geluidsgolven of digitale signalen) stabiel blijven als je ze door een systeem haalt.

Als een patroon "in balans" is, betekent het dat het systeem stabiel is en geen rare pieken of dalen vertoont.
De "robots" die de auteurs hebben gebouwd, zijn als testapparatuur. Ze vertellen je direct of een bepaald formaat van data-stroom veilig is, zonder dat je alles handmatig hoeft na te rekenen.

Conclusie: De Kunst van het Kijken

De kern van dit artikel is een prachtige demonstratie van hoe wiskundigen denken. Ze nemen een abstract, oneindig probleem en veranderen het in een eindig, oplosbaar raadsel.

Ze zeggen eigenlijk: "Je hoeft niet het hele universum te doorzoeken om te weten of een patroon goed is. Als je de juiste sleutel (de automaat) hebt, kun je het antwoord vinden door simpelweg naar de afmetingen van je raam te kijken."

Het is alsof je een magische bril opzet die je laat zien welke vormen in een willekeurig patroon perfect passen, en welke vormen de harmonie verstoren. En met deze bril kunnen we nu zien dat de Fibonacci-wereld verrassend veel harmonie biedt, terwijl de Tribonacci-wereld alleen rust biedt aan kleine, bescheiden vormen.

Probleemstelling

Het artikel onderzoekt het concept van balans in twee dimensies voor woordrechthoeken (word rectangles) afgeleid van oneindige sequenties.

Definitie: Gegeven een oneindige rij $(a_i)_{i \ge 0}$ over $\mathbb{N}$ , wordt een oneindige matrix $A$ gedefinieerd door $a_{k,\ell} = a_{k+\ell}$ . Een $m \times n$ submatrix $A(i, m, n)$ begint bij index $i$ en bevat $m$ rijen en $n$ kolommen.
Balans: Voor een binaire rij (over $\{0, 1\}$ ) wordt de som van alle elementen in een rechthoek $A(i, m, n)$ genoteerd als $T(i, m, n)$ . Een paar $(m, n)$ wordt gebalanceerd genoemd als de verzameling van waarden $\{T(i, m, n) \mid i \ge 0\}$ maximaal twee verschillende waarden bevat.
Doel: Het artikel beantwoordt de vraag: voor welke paren $(m, n)$ zijn de $m \times n$ rechthoeken gebalanceerd voor specifieke oneindige woorden, zoals het Fibonacci-woord, het Tribonacci-woord en het Thue-Morse-woord?

Methodologie

De auteurs hanteren een combinatie van automata-theorie, logica en computerbewijzen met behulp van de softwaretool Walnut.

Sturmian Woorden en Automata:
- Voor Sturmian woorden (geassocieerd met een irrationaal getal $\alpha$ ) wordt een criterium voor balans afgeleid op basis van het verschil $\Delta(i, m, n) = T(i+1, m, n) - T(i, m, n)$ .
- Een paar $(m, n)$ is gebalanceerd dan en slechts dan als de sequentie $\Delta$ geen blokken van de vorm $1, 0, \dots, 0, 1$ of $-1, 0, \dots, 0, -1$ bevat.
- Omdat $\alpha$ een kwadratisch irrationaal getal is (zoals de Gulden Snede voor het Fibonacci-woord), kan de functie $x = \lfloor n\alpha \rfloor$ worden herkend door een eindige automaat in het Ostrowski $\alpha$ -numerasiesysteem.
- De auteurs vertalen de balansvoorwaarde naar een formule in de eerste-orde logica. Via bekende methoden wordt deze formule omgezet in een eindige automaat die de paren $(m, n)$ accepteert als ze gebalanceerd zijn.
Implementatie in Walnut:
- Voor het Fibonacci-woord wordt het Zeckendorf-numerasiesysteem (som van niet-opeenvolgende Fibonacci-getallen) gebruikt.
- De auteurs schrijven Walnut-code om de balansvoorwaarde te modelleren, rekening houdend met de beperking dat Walnut voornamelijk natuurlijke getallen verwerkt (door verschuivingen te gebruiken om negatieve waarden te simuleren).
- Voor het Tribonacci-woord en het Thue-Morse-woord worden aangepaste numeratiesystemen en logische modellen gebruikt.
Lineaire Representaties:
- Om te bewijzen dat het aantal verschillende waarden van $T(i, m, n)$ kan groeien met $n$ (voor specifieke $m, n$ ), gebruiken de auteurs lineaire representaties van functies, berekend via Maple en Walnut.

Belangrijkste Bijdragen en Resultaten

1. Het Fibonacci-woord

Karakterisering: De auteurs bewijzen dat er een algoritme bestaat dat een eindige automaat construeert die precies de gebalanceerde paren $(m, n)$ accepteert voor het Fibonacci-woord.
De Automaat: Ze construeren een automaat met 15 toestanden (in het Zeckendorf-systeem) die de balans bepaalt.
Verificatie van eerdere resultaten: Ze bewijzen dat het resultaat van Anselmo et al. (dat $(m, n)$ gebalanceerd is als $\max(m, n)$ een Fibonacci-getal is) een speciaal geval is van hun algemene karakterisering.
Nieuwe inzichten:
- Ze geven een menselijk leesbaar karakteriseringscriterium (Theorema 7) gebaseerd op de pariteit van de indices in de Zeckendorf-ontwikkeling van $m$ en $n$ .
- Ze bewijzen dat de dichtheid van gebalanceerde $n$ voor een vaste $m$ ondergrens heeft van ongeveer $1/\phi^m$ .
- Ze tonen aan dat het aantal verschillende waarden van $T(i, m, n)$ voor $m=n=F_{3k/2}$ lineair groeit met $k$ (dus $\Theta(k)$ ), wat betekent dat de balans niet triviaal is voor grote vierkanten.

2. Het Tribonacci-woord

Het Tribonacci-woord is 2-gebalanceerd (in 1D). De auteurs onderzoeken wanneer $m \times n$ rechthoeken 2-gebalanceerd zijn.
Resultaten:
- Als $m=1$ , zijn alle rechthoeken 2-gebalanceerd.
- Als $m=2$ , bestaat er een 77-toestanden automaat die de gebalanceerde $n$ accepteert. De auteurs geven een lijst van de eerste waarden.
- Als $m \ge 3$ , zijn er geen $n$ waarvoor de rechthoeken 2-gebalanceerd zijn. Dit wordt bewezen door een tegenvoorbeeld te construeren waarbij het verschil in het aantal '2's in twee rechthoeken 3 is.

3. Het Thue-Morse-woord

Voor het Thue-Morse-woord wordt een volledige beschrijving van de balans gegeven.
Theorema: De balans van $m \times n$ rechthoeken is beperkt tot de waarden 1, 2, 3 of 4.
Specifiek geval: Voor $m, n \ge 3$ is de balans exact 3 dan en slechts dan als zowel $m$ als $n$ oneven zijn.
Complexiteit: De constructie van de automaat die de balans berekent is zeer complex. De tussenstap vereiste een automaat met meer dan 32 miljoen toestanden, 12.834 seconden CPU-tijd en 100 GB RAM. Het resultaat is een automaat met 92 toestanden die de balans bepaalt voor invoer in binaire notatie.

Significantie

Methodologische Doorbraak: Het artikel demonstreert krachtig hoe eindige automata en logische formalisaties kunnen worden gebruikt om complexe combinatorische eigenschappen van oneindige woorden op te lossen, die anders moeilijk analytisch te benaderen zijn.
Generalisatie: De methode is niet beperkt tot het Fibonacci-woord, maar werkt voor alle Sturmian woorden die corresponderen met kwadratische irrationale getallen.
Nieuw Inzicht in Balans: Het toont aan dat de balans in twee dimensies een veel subtieler en complexer gedrag vertoont dan in één dimensie, met name voor grotere rechthoeken en andere woorden dan het Fibonacci-woord.
Reproduceerbaarheid: Alle gebruikte code (Walnut en Maple) is openbaar beschikbaar gemaakt, wat de reproduceerbaarheid van de bewijzen en de mogelijkheid voor verdig onderzoek garandeert.

Samenvattend biedt dit artikel een volledig geautomatiseerd raamwerk om de balans van rechthoekige patronen in diverse klassieke oneindige woorden te karakteriseren, met concrete resultaten voor de drie meest onderzochte woorden in de combinatoriek van woorden.