💻 computer science

Mahler equations for Zeckendorf numeration

Dit artikel introduceert veralgemeende Z-Mahler-vergelijkingen gebaseerd op het Zeckendorf-telsysteem en bewijst dat Z-regulariteit equivalent is aan het oplossen van isolerende vergelijkingen, terwijl een tegenvoorbeeld aantoont dat dit niet geldt voor niet-isolerende gevallen, wat bovendien leidt tot een nieuwe constructie van gewogen automaten voor klassieke q-regulariteit.

Oorspronkelijke auteurs: Olivier Carton, Reem Yassawi

Gepubliceerd 2026-03-17

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Olivier Carton, Reem Yassawi

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

De Zeckendorf-Mahler-verbinding: Een reis door getallen, automaten en magie

Stel je voor dat je een heel groot boek hebt vol met getallen. In de wiskunde proberen we vaak te begrijpen hoe deze getallen zich gedragen. Soms volgen ze een heel strak patroon, soms lijken ze willekeurig. Dit artikel van Olivier Carton en Reem Yassawi is als een detectiveverhaal waarin ze een nieuw soort "magische formule" ontdekken die een brug slaat tussen twee heel verschillende werelden: automaten (simpelere versies van computers) en wiskundige vergelijkingen.

Hier is het verhaal, vertaald in alledaags taal met een paar leuke vergelijkingen.

1. De twee werelden: De Computer en de Vergelijking

Stel je twee manieren voor om een rij getallen te maken:

De Computer (Automaten): Stel je een kleine robot voor die een rijtje getallen moet maken. De robot kijkt naar een getal (bijvoorbeeld 100) en leest het als een code (bijvoorbeeld in binair: 1100100). De robot heeft een paar "vermoedens" (toestanden) en springt van het ene naar het andere als hij een cijfer ziet. Aan het einde geeft hij een antwoord. Als deze robot maar een eindig aantal "vermoedens" heeft, noemen we de rij automatisch.
De Vergelijking (Mahler-vergelijkingen): Stel je nu een magisch recept voor. Je hebt een onbekende rij getallen (laten we die $f$ noemen). Het recept zegt: "Deze rij is gelijk aan zichzelf, maar dan een stukje opgeschoven en vermenigvuldigd met een paar getallen." Als je dit recept kunt oplossen, heb je een Mahler-rij.

In de gewone wereld (waar we tellen met 10, of 2, of 100) weten we al lang dat deze twee werelden aan elkaar verbonden zijn. Als een rij door een simpele robot gemaakt kan worden, dan voldoet hij ook aan zo'n magisch recept, en andersom. Dit heet het stelling van Christol (of Becker en Dumas).

2. Het nieuwe puzzelstukje: De Zeckendorf-telwijze

Nu komt het spannende deel. De auteurs kijken niet naar de gewone manier van tellen (1, 2, 3, 4, 5...), maar naar de Zeckendorf-telwijze.

De gewone manier: Je gebruikt machten van 2 (1, 2, 4, 8...) of 10 (1, 10, 100...).
De Zeckendorf-methode: Je gebruikt de Fibonacci-getallen (1, 2, 3, 5, 8, 13...).
- Het leuke aan deze methode is dat je elk getal op één unieke manier kunt schrijven als een som van Fibonacci-getallen, maar dan met één regel: je mag geen twee opeenvolgende Fibonacci-getallen gebruiken.
- Bijvoorbeeld: 10 is niet $8 + 2$ (want 8 en 2 zijn niet opeenvolgend, maar wacht... 8 is $F_6$ en 2 is $F_3$ , dat mag wel). Laten we het simpel houden: 4 is $3 + 1$ (Fibonacci 3 en 1). 5 is gewoon 5. Maar 6 is $5 + 1$ . Je mag 6 niet schrijven als $3 + 2 + 1$ (want 3 en 2 zijn opeenvolgend in de Fibonacci-reeks).

Het probleem is: in de gewone wereld is "een nul toevoegen" hetzelfde als "vermenigvuldigen met 10". In de Fibonacci-wereld werkt dat niet zo simpel. Als je een nul toevoegt aan een Fibonacci-code, gebeurt er iets heel anders. De "magische formule" (de Mahler-vergelijking) werkt hier niet meer vanzelfsprekend.

3. De uitdaging: De "Kromme Lijn"

De auteurs zeggen: "Oké, we hebben een robot die getallen in Fibonacci-stijl leest. Kunnen we ook een magische formule vinden die precies diezelfde getallen produceert?"

Het grote obstakel is dat de Fibonacci-wereld niet lineair is.

Vergelijking: Stel je voor dat je een ladder hebt. In de gewone wereld (basis 10) is elke sport precies even hoog. Als je 1 sport omhoog gaat, ga je 10 stappen vooruit.
In de Fibonacci-wereld zijn de sporten van de ladder ongelijk. Soms is de stap groot, soms klein. Als je probeert een simpele formule te maken die zegt "ga 1 sport omhoog", werkt dat niet omdat de afstand tussen de sporten varieert.

De auteurs noemen dit de "lineaire tekortkoming". Het is alsof je probeert een rechte lijn te tekenen op een oppervlak dat hobbelig is.

4. De oplossing: Een slimme robot met een geheugen

Hoe lossen ze dit op? Ze bouwen een nieuwe, super-slimme robot (een "gewogen automaat").

De oude robot: Kijkt alleen naar het huidige cijfer en springt naar de volgende toestand.
De nieuwe robot: Kijkt niet alleen naar het cijfer, maar onthoudt ook hoeveel de "hobbels" in de ladder hebben afgeleid.
- De robot heeft een klein "notitieboekje" (een extra toestand) waarin hij bijhoudt of hij net een grote sprong heeft gemaakt of een kleine.
- Door dit extra geheugen te gebruiken, kan de robot de "kromme lijn" van de Fibonacci-getallen precies volgen.

Ze bewijzen dat:

Als je een rij hebt die door zo'n slimme robot gegenereerd wordt, dan voldoet die rij aan een Zeckendorf-Mahler-vergelijking (een aangepaste versie van de magische formule).
Als je een oplossing hebt van zo'n vergelijking (die "isolé" is, wat betekent dat het recept goed gestructureerd is), dan kun je die oplossing altijd laten maken door zo'n slimme robot.

5. Waarom is dit belangrijk?

Dit klinkt misschien als pure wiskundige theorie, maar het heeft diepere betekenissen:

Het is een brug: Het verbindt de wereld van simpele computers (automaten) met de wereld van complexe vergelijkingen, maar dan in een heel andere "taal" (Fibonacci in plaats van decimaal).
Het is een waarschuwing: Ze tonen aan dat als je de vergelijking niet goed opstelt (niet "isolé" is), de robot het niet meer kan doen. Het is alsof je een recept hebt dat zegt "voeg een beetje suiker toe", maar als je te veel suiker toevoegt, wordt het een rommel en werkt de machine niet meer.
Toekomst: Het opent de deur voor meer onderzoek. Misschien kunnen we nu ook andere "vreemde" telwijzen (zoals die gebaseerd op andere getallen dan Fibonacci) begrijpen met dezelfde techniek.

Samenvatting in één zin

De auteurs hebben bewezen dat je voor de speciale Fibonacci-telwijze een soort "magische formule" kunt schrijven die precies hetzelfde doet als een slimme computer die deze getallen berekent, mits je die formule slim genoeg ontwerpt om rekening te houden met de onregelmatige sprongen in de Fibonacci-reeks.

Het is alsof ze een nieuwe sleutel hebben gevonden die een deur opent naar een kamer die we dachten dat gesloten was, en die sleutel werkt alleen als je hem precies in de juiste hoek draait!

Titel: Mahler-vergelijkingen voor Zeckendorf-nummeringssystemen

Auteurs: Olivier Carton en Reem Yassawi

1. Probleemstelling en Context

Het artikel onderzoekt de relatie tussen automatische sequenties (gegenereerd door eindige toestandsautomaten) en algebraïsche eigenschappen van machtreeksen, specifiek binnen het kader van Pisot-nummeringssystemen.

Achtergrond: Christols theorema verbindt algebraïsche machtreeksen over eindige velden met $p$ -automatische sequenties (waarbij $p$ een priemgetal is). De theorie is later uitgebreid naar $k$ -reguliere sequenties (gegenereerd door gewogen automaten) en $k$ -Mahler-vergelijkingen.
De beperking: Bestaande resultaten (van Becker en Dumas) tonen aan dat voor een standaard basis- $k$ $k$ -systeem:
1. Elke $k$ -reguliere sequentie voldoet aan een $k$ -Mahler-vergelijking.
2. Elke oplossing van een isolerende $k$ -Mahler-vergelijking is $k$ -regulier.
Het probleem: Deze resultaten zijn gebaseerd op de eigenschap dat in basis $k$ het toevoegen van een nul aan het einde van een getal gelijkstaat aan vermenigvuldiging met $k$ ( $n \mapsto kn$ ). Dit lineaire verband geldt niet voor het Zeckendorf-nummeringssysteem (gebaseerd op Fibonacci-getallen), waar de "vermenigvuldigingsoperator" niet-lineair is.
Doel: De auteurs willen een analoog theorema bewijzen voor het Zeckendorf-systeem ( $Z$ ), waarbij ze definiëren wat een $Z$ -Mahler-vergelijking is en het verband leggen met $Z$ -reguliere sequenties.

2. Methodologie

De auteurs ontwikkelen een nieuwe constructie die de lineaire eigenschappen van basis- $k$ vervangt door een mechanisme dat de niet-lineariteit van het Zeckendorf-systeem compenseert.

A. De Operator $\Phi$ en de functie $\phi$

In plaats van de operator $f(x) \mapsto f(x^k)$ , definiëren de auteurs een operator $\Phi$ gebaseerd op een functie $\phi: \mathbb{N} \to \mathbb{N}$ .

Voor een getal $n$ met Zeckendorf-expansie $(n)_Z = b_k \dots b_0$ , is $\phi(n) = [b_k \dots b_0 0]_Z$ (effectief een verschuiving van de Fibonacci-coëfficiënten).
Cruciaal punt: De functie $\phi$ is niet lineair. Voorbeeld: $\phi(1+1) = \phi(2) = 3$ , maar $\phi(1) + \phi(1) = 2 + 2 = 4$ .
De auteurs definiëren een lineariteitsdefect $\delta(m, n) = \phi(m+n) - \phi(m) - \phi(n)$ . Ze bewijzen dat dit defect beperkt blijft tot $\{-1, 0, 1\}$ .

B. Automatische Tracking van het Defect

Om de niet-lineariteit te hanteren in een automaat, gebruiken de auteurs een deterministische automaat die het defect $\delta(m-n, n)$ berekent op basis van de Zeckendorf-expansies van $m$ en $n$ .

Dit vereist het combineren van de standaard constructie voor Mahler-vergelijkingen met een extra "toestand" die het defect bijhoudt.
Ze tonen aan dat de verzameling woorden waarvoor het defect een bepaalde waarde heeft, regulier is (herkenbaar door een automaat).

C. Constructie van de Gewogen Automaat

De kern van de bewijsvoering is de constructie van een universele gewogen automaat voor isolerende $Z$ -Mahler-vergelijkingen.

Een $Z$ -Mahler-vergelijking heeft de vorm: $P(x, y) = \sum_{i=0}^d A_i(x) \Phi^i(y) = 0$ .
De auteurs construeren een automaat $A(P, f_0)$ $A (P, f_{0})$ waarvan de toestanden niet alleen de index $i$ $i$ (van de operator $\Phi$ $Φ$ ) en de graad $j$ $j$ van de polynoomcoëfficiënten bijhouden, maar ook:
1. De toestand van de automaat die het defect berekent.
2. Een "buffer" van de recent ingelezen cijfers om het defect correct te kunnen berekenen.
De overgangen in de automaat gebruiken de coëfficiënten van de vergelijking en het berekende defect om de juiste volgende coëfficiënt van de oplossing te genereren.

3. Belangrijkste Resultaten

Hoofdstelling (Theorema 1)

Laat $R$ een commutatieve ring zijn en $P(x, y) = 0$ een isolerende $Z$ -Mahler-vergelijking (waarbij de coëfficiënt van $y$ gelijk is aan 1). Als $f(x)$ een oplossing is van deze vergelijking, dan is de rij van coëfficiënten van $f$ $Z$ -regulier.

Dit betekent dat er een gewogen automaat bestaat die de coëfficiënten van $f$ genereert door de Zeckendorf-expansie van $n$ in te voeren.
De auteurs geven bovendien een bovengrens voor het aantal toestanden van deze automaat, afhankelijk van de exponent en de hoogte van de vergelijking en de gulden snede $\phi$ .

Omgekeerde Richting (Corollary 34)

Elke $Z$ -reguliere reeks is de oplossing van een $Z$ -Mahler-vergelijking.

Dit wordt bewezen door een lineaire afhankelijkheid aan te tonen tussen de iteraties van de operator $\Phi$ toegepast op de reeksen gegenereerd door de toestanden van de automaat.

Noodzaak van Isolatie

De auteurs tonen aan dat de voorwaarde dat de vergelijking isolering (isolating) moet zijn, essentieel is.

Ze presenteren een tegenvoorbeeld (Propositie 38) van een niet-isoalerende $Z$ -Mahler-vergelijking: $(1-x)f(x) = \Phi(f(x))$ .
De oplossing hiervan heeft coëfficiënten die sneller groeien dan polynomen (exponentiële groei), wat in strijd is met de eigenschappen van $Z$ -reguliere sequenties (die polynomiale groei hebben, zie Lemma 5).

Universele Automaat (Theorema 2)

Voor het standaard basis- $k$ geval construeren de auteurs een universele gewogen automaat. Door de gewichten in deze automaat in te stellen op basis van de coëfficiënten van een isolerende $k$ -Mahler-vergelijking, wordt de oplossing van die vergelijking gegenereerd. Dit biedt een nieuwe, directe constructie voor de stelling van Becker en Dumas, zonder gebruik te maken van Cartier-operatoren.

4. Bijdragen en Significatie

Generalisatie van Christols Theorema: Het artikel breidt de fundamentele link tussen algebraïsche structuren (Mahler-vergelijkingen) en computationele structuren (automaten) uit van het standaard basis- $k$ -systeem naar het complexere Zeckendorf-systeem.
Oplossing van het Lineariteitsprobleem: De grootste technische uitdaging was het ontbreken van de lineaire eigenschap $n \mapsto kn$ . De auteurs lossen dit op door een automaat te ontwerpen die het "lineariteitsdefect" dynamisch berekent en opslaat. Dit is een innovatieve methode die waarschijnlijk toepasbaar is op andere Pisot-systemen.
Nieuwe Constructie voor Basis- $k$ : Zelfs voor het klassieke geval van basis $k$ bieden ze een nieuwe, meer directe constructie van de automaat die de oplossing van Mahler-vergelijkingen genereert, wat de afhankelijkheid van Cartier-operatoren elimineert.
Open Vragen: Het artikel identificeert open problemen, zoals of er een volledige karakterisering bestaat voor $Z$ -reguliere reeksen (vergelijkbaar met het werk van Allouche, Shallit en anderen voor complexe getallen) en welke reeksen zowel $k$ - als $Z$ -Mahler zijn.

Conclusie

Dit werk is een significante stap in de theoretische informatica en getaltheorie. Het bewijst dat de elegante correspondentie tussen Mahler-vergelijkingen en reguliere sequenties standhoudt in niet-lineaire numereringssystemen, mits men de juiste technische hulpmiddelen (zoals defect-tracking automaten) inzet. Het legt de basis voor verdere onderzoek naar de algebraïsche eigenschappen van substitutie-vaste punten en Pisot-systemen.