State Complexity of Shifts of the Fibonacci Word

Titel: State Complexity of Shifts of the Fibonacci Word

Auteurs: Delaram Moradi, Pierre Popoli, Jeffrey Shallit, en Ingrid Vukusic.

1. Probleemstelling

Het artikel onderzoekt de staatcomplexiteit (state complexity) van automaten die verschoven Fibonacci-woorden genereren.

• Het Fibonacci-woord ($f$): Een beroemde aperiodische oneindige woordreeks gedefinieerd als het vaste punt van de morfisme $0 \to 01, 1 \to 0$, of equivalent via de Zeckendorf-representatie (de $i$-de bit is de laatste cijfer van de Zeckendorf-representatie van $i$).
• De operatie: Gegeven een verschuiving $c \geq 0$, wordt de nieuwe reeks $(f(i+c))_{i \geq 0}$ bestudeerd.
• De vraag: Wat is het minimale aantal toestanden dat nodig is voor een Deterministische Finite Automaton met Output (DFAO) om deze verschoven reeks te genereren?
• Context: Er zijn twee invoerformaten:
  1. lsd-first: De minst significante cijfers eerst (in Zeckendorf-representatie).
  2. msd-first: De meest significante cijfers eerst.
  • Voor algemene $k$-automatische reeksen kan een verschuiving $c$ leiden tot een complexiteit van $O(m \log c)$ (lsd-first) of zelfs $O(c)$ (msd-first, zoals bij het Thue-Morse-woord). Het doel is te bepalen of het Fibonacci-woord een uitzondering is en of de complexiteit lager kan blijven.

2. Methodologie

De auteurs combineren technieken uit drie domeinen:

1. Staatcomplexiteit: Constructie van DFAO's en bewijzen van minimaliteit.
2. Diophantische Benadering: Gebruik van eigenschappen van de Gulden Snede ($\phi$) en de verdeling van de punten $\{n\phi\}$ modulo 1.
3. Automatische Theorema-bewijzen: Gebruik van de tool Walnut om logische eigenschappen van automatische reeksen formeel te verifiëren.

Kernconcepten:

• Lemma 1: De $i$-de bit van $f$ is 1 dan en slechts dan als $\{i\phi\} \in (-\phi, -2\phi) \pmod 1$.
• Verschuiving: Een verschuiving met $c$ betekent dat we kijken naar $\{(i+c)\phi\}$. Dit is equivalent met het controleren of $\{i\phi\}$ valt in een specifiek interval $J_c = (-(c+1)\phi, -(c+2)\phi) \pmod 1$.
• Partities: De auteurs definiëren partities van het interval $[0, 1)$ gebaseerd op de Zeckendorf-cijfers. Voor lsd-first worden partities $I_d(m)$ gebruikt die corresponderen met de eerste $d$ cijfers. Voor msd-first worden partities $P(r)$ gedefinieerd op basis van negatieve Fibonacci-getallen.

3. Belangrijkste Resultaten

A. lsd-first geval (Theorema 1)

• Resultaat: Er bestaat een DFAO met $O(\log c)$ toestanden die $(f(i+c))_{i \geq 0}$ genereert voor lsd-first invoer.
• Constructie:
  • De automaat leest de Zeckendorf-cijfers van $i$ van laag naar hoog.
  • De toestanden corresponderen met intervallen in de partitie van $[0, 1)$.
  • Na het lezen van ongeveer $k$ cijfers (waarbij $F_k \approx c$), weet de automaat zeker in welk interval $\{i\phi\}$ ligt ten opzichte van de kritieke punten $\{-(c+1)\phi\}$ en $\{-(c+2)\phi\}$.
  • De automaat gaat dan over naar een "sink state" (een eindtoestand die alleen output 0 of 1 geeft, afhankelijk van de laatste ingevoerde cijfer).
• Optimaliteit (Theorema 2): De auteurs bewijzen dat deze bovengrens optimaal is. De exacte staatcomplexiteit is $2(|(c)_F| + 1) + 1 - g(c)$, waarbij $|(c)_F|$ de lengte van de Zeckendorf-representatie van $c$ is. Dit bevestigt dat de groei logarithmisch is.

B. msd-first geval (Theorema 3)

• Resultaat: Ook voor msd-first invoer is de staatcomplexiteit $O(\log c)$.
• Contrast: Dit is opmerkelijk omdat voor andere reeksen (zoals Thue-Morse) de msd-first complexiteit vaak lineair ($O(c)$) is.
• Constructie:
  • In plaats van de automaat om te draaien (wat exponentiële groei zou veroorzaken), gebruiken de auteurs een directe constructie gebaseerd op partities die consistent zijn met de msd-first representatie.
  • Ze definiëren partities $P(-(c+1))$ en $P(-(c+2))$ gebaseerd op de rijen van negatieve Fibonacci-getallen die ontstaan door bits weg te laten (right-shift).
  • De vereniging van deze partities vormt een nieuwe partitie $P$ met $O(\log c)$ intervallen.
  • De overgangen in de automaat worden bepaald door te kijken in welk sub-interval $\{n(a)\phi\}$ valt als $\{n\phi\}$ in een bepaald interval ligt.
• Validatie: De correctheid van de partities en overgangen wordt formeel bewezen met behulp van Walnut.

4. Significatie en Bijdrage

• Information-theoretische limiet: De complexiteit $O(\log c)$ is zeer dicht bij het theoretische minimum voor aperiodieke reeksen. Een eenvoudige telargument toont aan dat voor niet-periodieke reeksen de complexiteit minstens $c' (\log c) / (\log \log c)$ moet zijn. Het Fibonacci-woord bereikt dus een bijna optimale efficiëntie voor verschuivingen.
• Unieke eigenschap van Fibonacci: Het resultaat toont aan dat het Fibonacci-woord, ondanks zijn complexiteit in andere contexten, een zeer "reguliere" structuur heeft wat betreft verschuivingen, ongeacht of de invoer van links naar rechts of van rechts naar links wordt gelezen.
• Technische innovatie: Het artikel introduceert een nieuwe methode voor het analyseren van msd-first complexiteit door gebruik te maken van partities van negatieve Fibonacci-getallen, in plaats van de gebruikelijke transducer-technieken die hier niet werken.
• Toekomstige richtingen: De auteurs suggereren dat deze resultaten kunnen worden gegeneraliseerd naar andere kwadratische irrationale getallen en naar de Tribonacci-woord, hoewel de analyse daar complexer zal zijn.

Conclusie

Het artikel bewijst dat de staatcomplexiteit van het verschuiven van het Fibonacci-woord met een constante $c$ in beide invoerformaten (lsd-first en msd-first) slechts logarithmisch groeit met $c$. Dit is een aanzienlijke verbetering ten opzichte van de lineaire groei die bij andere bekende automatische reeksen wordt waargenomen, en benadert de theoretische ondergrens voor aperiodieke sequenties. De bewijzen combineren diepe inzichten in getaltheorie (Diophantische benadering) met geautomatiseerd redeneren.