On a sequence of Kimberling and its relationship to the Tribonacci word

In dit artikel worden de conjectures van Clark Kimberling over zijn door inflatieregels gedefinieerde binaire rij bewezen met behulp van de Walnut-theorema-prover, waarbij de relatie met het oneindige Tribonacci-woord wordt aangetoond en zowel de subwoordcomplexiteit als de kritische exponent van de rij worden bepaald.

De kern

Stel je voor dat je een mysterieuze, oneindige ketting van blokken hebt, gemaakt van alleen maar twee soorten steentjes: zwart (0) en wit (1). Deze ketting heet de "Kimberling-reeks". In 2017 bedacht de wiskundige Clark Kimberling een vreemde manier om deze ketting te bouwen, en hij had een paar sterke vermoedens over hoe deze ketting precies in elkaar zat. Maar hij kon het niet bewijzen.

De auteurs van dit artikel (Lubomíra, Edita en Jeffrey) zijn als detectives opgestaan om die vermoedens te controleren. Ze hebben twee krachtige wapens gebruikt:

1. Een slimme computer (Walnut): Een soort "rekenmachine voor logica" die kan bewijzen of een wiskundige stelling waar is of niet, zonder dat een mens de hele berekening handmatig hoeft te doen.
2. Een oude, bekende vriend (de Tribonacci-reeks): Een beroemde, al bestudeerde ketting die als een soort "moeder" fungeert voor Kimberling's ketting.

Hier is wat ze hebben ontdekt, vertaald naar alledaags taalgebruik:

1. De Bouwregels: Een Vreemde Instructie

Kimberling's ketting begint met twee zwarte steentjes: 00.
Om de volgende versie te maken, kijkt hij naar de ketting en doet hij het volgende:

• Als hij een enkele witte steen ziet (1), verandert die in 10.
• Als hij een enkele zwarte steen ziet (0), blijft die 0.
• Maar! Als hij twee zwarte stenen naast elkaar ziet (00), verandert dat blok in 0101.

Het is alsof je een recept hebt waarbij je soms één ingrediënt vervangt, maar soms een hele groep ingrediënten in één keer omzet. Kimberling dacht dat de lengte van de ketting op een heel specifieke manier groeide (volgens een getallenreeks die hij had bedacht). De auteurs hebben met hun computer bewezen: Ja, hij had gelijk. De ketting groeit precies zoals hij voorspelde.

2. De Geheimen: Een Spiegelbeeld van de Tribonacci

Het meest fascinerende deel is de connectie met de Tribonacci-reeks.
Stel je voor dat de Tribonacci-reeks een groot, complex labyrint is. Kimberling's ketting is eigenlijk gewoon een vertaling van dat labyrint.

De auteurs hebben ontdekt dat je Kimberling's ketting kunt krijgen door de Tribonacci-reeks door een speciaal "vertaalapparaat" te sturen.

• In het labyrint (Tribonacci) zijn er drie soorten paden: 0, 1 en 2.
• In Kimberling's wereld zijn er maar twee: 0 en 1.
• Het "vertaalapparaat" (een wiskundige formule) neemt elk stukje van het labyrint en zet het om in de juiste volgorde van zwarte en witte steentjes.

Dit betekent dat we Kimberling's mysterieuze ketting niet als een nieuw, raadselachtig ding hoeven te zien, maar als een bekende vriend in een nieuw jasje.

3. De Balans: Hoeveel Witte Steentjes?

Kimberling vroeg zich ook af: "Als ik naar een stukje van de ketting kijk, hoeveel witte steentjes zitten er dan?"
Hij dacht dat het aantal witte steentjes in elk stukje van dezelfde lengte bijna hetzelfde zou zijn, met een klein verschil.

• De auteurs hebben bewezen dat het verschil nooit meer dan 3 is.
• Het is niet mogelijk dat het verschil slechts 2 is.

Dit is als het verdelen van snoepjes onder kinderen. Als je 100 kinderen hebt en je verdeelt de snoepjes, kan het zijn dat het ene kind 3 snoepjes meer krijgt dan het andere, maar nooit 4 of 5. De ketting is "in balans", maar niet perfect.

4. De Complexiteit: Hoeveel Verschillende Patronen?

Een andere vraag was: "Hoeveel verschillende patronen van een bepaalde lengte komen er in deze ketting voor?"

• Als je een ketting hebt die heel saai is (bijvoorbeeld 01010101...), zijn er maar heel weinig verschillende patronen.
• Als je een ketting hebt die willekeurig is, zijn er enorm veel.

Kimberling's ketting zit precies in het midden. Het is een Rote-woord. Dit is een wiskundige term voor een ketting die precies twee keer zo veel verschillende patronen heeft als de lengte van het patroon.

• Voor een lengte van 10 zijn er precies 20 verschillende patronen.
• Voor een lengte van 100 zijn er precies 200.
  Het is een heel specifieke, elegante structuur die niet te saai en niet te chaotisch is.

5. De Herhaling: Hoe vaak kan iets terugkomen?

Tot slot keken ze naar de "kritische exponent". Dit is een maat voor hoe vaak een patroon zich direct achter elkaar kan herhalen.

• 0101 is een herhaling van 01 (2 keer).
• 010101 is een herhaling van 01 (3 keer).

De auteurs hebben berekend dat in Kimberling's ketting een patroon zich maximaal ongeveer 3,19 keer kan herhalen. Het kan dus niet oneindig vaak hetzelfde patroon herhalen (zoals 000000...), maar het kan wel een paar keer "op zijn kop" staan. Dit getal (3,19...) is een heel specifiek getal dat ook voorkomt in de Tribonacci-reeks, wat de band tussen de twee kettingen weer bevestigt.

Samenvatting

Kortom: Dit artikel is een bewijs dat een raadselachtige, door een mens bedachte rij van nullen en enen (Kimberling's reeks) eigenlijk een heel bekende, wiskundige vriend is (de Tribonacci-reeks) die een nieuwe vermomming draagt. Met de hulp van een slimme computer hebben de auteurs bewezen dat de groei, de balans en de patronen in deze ketting precies zo werken als de oorspronkelijke bedenker dacht. Het is een mooi voorbeeld van hoe moderne computers ons kunnen helpen oude wiskundige mysteries op te lossen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "On a sequence of Kimberling and its relationship to the Tribonacci word" in het Nederlands.

Titel en Context

Het artikel, geschreven door Lubomíra Dvořáková, Edita Pelantová en Jeffrey Shallit, onderzoekt een specifieke binaire rij (reeks van 0's en 1's) die in 2017 door Clark Kimberling werd gedefinieerd (OEIS-reeks A288462). De auteurs bewijzen een aantal conjectures (vermoedens) van Kimberling en onthullen de diepe wiskundige relatie tussen deze rij en het beroemde oneindige Tribonacci-woord.

1. Het Probleem

Clark Kimberling definieerde de rij $B$ via een complexere "inflatieregels" dan een standaard morfisme. De constructie verloopt als volgt:

• Start met $B_0 = 00$.
• Om $B_{i+1}$ te krijgen, wordt $B_i$ gefactoriseerd in maximale blokken van de vorm 00, 0 en 1.
• Vervolgens worden de regels toegepast: 0 $\to$ 0, 1 $\to$ 10, en 00 $\to$ 0101.
• De rij $B$ is de unieke oneindige limiet van deze iteraties.

Kimberling deed een aantal conjectures over deze rij, waaronder:

1. Een specifieke formule voor de lengte van de iteraties $|B_i|$.
2. De relatie tussen de posities van de 0's en 1's in $B$ en de Tribonacci-constante.
3. Eigenschappen zoals de factorcomplexiteit en de kritieke exponent.

De uitdaging lag in het analyseren van een rij die niet direct via een lineair morfisme wordt gegenereerd, wat traditionele methoden bemoeilijkt.

2. Methodologie

De auteurs combineren drie krachtige technieken:

1. Combinatoriek op Woorden: Gebruik van concepten zoals return words (terugkeerwoorden), bispeciale factoren en afgeleide sequenties.
2. Automata-theorie: Constructie van een Deterministisch Eindige Automaton met Output (DFAO) die de rij $B$ berekent op basis van de Tribonacci-representatie van een index.
3. Automatisch Bewijzen (Walnut): Het gebruik van de theorem-prover "Walnut" om eigenschappen van de rij formeel te verifiëren. Walnut kan beslissen over uitspraken in de eerste-orde logica over automatische sequenties.

3. Belangrijkste Bijdragen en Resultaten

A. Bewijs van Kimberling's Conjectures over Lengte

De auteurs bewijzen dat de lengte van de $i$-de iteratie $|B_i|$ voldoet aan de recurrente relatie:
$|B_i| = 2|B_{i-1}| - |B_{i-4}|$ voor $i \ge 4$, met specifieke startwaarden.
Dit bevestigt Kimberling's conjecture dat $|B_i|$ overeenkomt met de rij A288465.

B. Relatie met het Tribonacci-woord

Een centrale ontdekking is dat $B$ direct gerelateerd is aan het Tribonacci-woord $TR$ (de vaste punt van $0 \to 01, 1 \to 02, 2 \to 0$).

• Stelling: $B = 0f(TR)$, waarbij $f$ een morfisme is: $0 \to 10, 1 \to 0, 2 \to 1$.
• De auteurs tonen aan dat de afgeleide sequentie van $B$ (gebaseerd op terugkeerwoorden naar 10) exact het Tribonacci-woord is.
• Hierdoor kunnen ze een automaat construeren die $B[n]$ berekent door de Tribonacci-representatie van $n$ te gebruiken.

C. Balans en Indexen

• Balans: De rij $B$ is 3-balanced (het aantal 1's in twee factoren van dezelfde lengte verschilt maximaal met 3), maar niet 2-balanced. Dit wordt bewezen met Walnut.
• Indexconjectures: Kimberling vermoedde dat de indexen van de $n$-de 0 en 1 respectievelijk asymptotisch benaderd worden door $\psi n$ en $\gamma n$, waarbij $\psi$ de Tribonacci-constante is ($\approx 1.839$) en $\gamma = (\psi^2+1)/2$.
  • De auteurs bewijzen scherpere ongelijkheden:
    • $\lfloor \psi n \rfloor - 2 \le I_0(n) \le \lfloor \psi n \rfloor + 2$
    • $\lfloor \gamma n \rfloor - 1 \le I_1(n) \le \lfloor \gamma n \rfloor + 3$

D. Factorcomplexiteit en Kritieke Exponent

• Factorcomplexiteit: De auteurs bewijzen dat $B$ een Rote-woord is. De factorcomplexiteit (het aantal unieke blokken van lengte $n$) is exact $2n$voor alle$n \ge 1$. Dit wordt afgeleid uit de analyse van de bispeciale factoren van$B$.
• Kritieke Exponent: De kritieke exponent (de maximale macht van een herhalend patroon in de rij) wordt bepaald als:
  $$ce(B) = 2 + \frac{1}{\psi - 1} \approx 3.19148788$$
  Dit is exact dezelfde kritieke exponent als die van het Tribonacci-woord.

4. Significatie

• Methodologische Voorbeeld: Het artikel dient als een "primer" (inleiding) voor het analyseren van complexe rijen die niet direct morfisch zijn, maar wel gerelateerd aan bekende structuren zoals het Tribonacci-woord. Het demonstreert hoe men combinatorische inzichten kan combineren met computationele bewijzen (Walnut).
• Oplossing van Open Problemen: Het lost een reeks open vragen van Kimberling op die sinds 2017 onbeantwoord waren.
• Verbinding tussen Gebieden: Het versterkt het verband tussen de theorie van Sturmiaanse en episturmiaanse woorden (zoals het Tribonacci-woord) en rijen die via complexere inflatieregels worden gegenereerd.
• Praktische Toepassing: De gepubliceerde Walnut-code en de geconstrueerde automaten bieden directe tools voor verdere onderzoekers om eigenschappen van deze en vergelijkbare rijen te testen.

Kortom, het paper transformeert een ogenschijnlijk willekeurige binaire rij in een goed begrepen wiskundig object met elegante eigenschappen, gekoppeld aan de fundamentele structuur van het Tribonacci-woord.