💻 computer science

Mahler equations for Zeckendorf numeration

Der Artikel definiert verallgemeinerte Z-Mahler-Gleichungen im Kontext des Zeckendorf-Numerationssystems und zeigt, dass Z-reguläre Folgen genau dann als Lösungen isolierender Z-Mahler-Gleichungen auftreten, wobei ein Gegenbeispiel für nicht-isolierende Gleichungen sowie eine neue Konstruktion gewichteter Automaten für q-reguläre Folgen bereitgestellt werden.

Ursprüngliche Autoren: Olivier Carton, Reem Yassawi

Veröffentlicht 2026-03-17

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Olivier Carton, Reem Yassawi

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Die große Reise: Von Zahlen, Automaten und magischen Gleichungen

Stellen Sie sich vor, Sie haben eine riesige Bibliothek, in der jede Zahl nicht wie gewohnt (1, 2, 3, 4...) geschrieben ist, sondern in einem ganz besonderen Code. Die Autoren dieses Papers beschäftigen sich mit einem solchen Code, der Zeckendorf-System genannt wird.

1. Der Code: Fibonacci statt Zehnerpotenzen

Normalerweise schreiben wir Zahlen im Zehnersystem (10, 100, 1000...). In diesem speziellen Code, dem Zeckendorf-System, benutzen wir die Fibonacci-Zahlen (1, 2, 3, 5, 8, 13...).

Die Regel: Jede Zahl wird als Summe verschiedener Fibonacci-Zahlen geschrieben, aber mit einer wichtigen Einschränkung: Man darf nie zwei benachbarte Fibonacci-Zahlen verwenden (z. B. keine 3 und 5 zusammen, weil 3+5=8 ist, was schon eine eigene Fibonacci-Zahl ist).
Das Bild: Stellen Sie sich vor, Sie bauen Türme aus Steinen. Im normalen System sind die Steine immer 1, 10, 100 groß. Im Zeckendorf-System sind die Steine 1, 2, 3, 5, 8, 13... groß. Und Sie dürfen nie zwei Steine nebeneinander legen, die direkt aufeinanderfolgen.

2. Die beiden Helden: Der Automat und die Gleichung

Die Autoren untersuchen zwei Arten, wie man Zahlenfolgen (Reihen von Zahlen) in diesem System beschreiben kann:

Held A: Der Roboter (Der gewichtete Automat)
Stellen Sie sich einen kleinen Roboter vor, der einen Zettel mit dem Code einer Zahl liest (z. B. "10100" für die Zahl 13). Der Roboter läuft durch ein Labyrinth von Wegen. An jedem Wegabschnitt gibt es einen "Gewicht"-Stempel (eine Zahl). Der Roboter addiert alle Stempel auf seinem Weg und gibt am Ende ein Ergebnis aus.
- Wenn dieser Roboter für jede Zahl $n$ das $n$ -te Glied einer Zahlenfolge berechnet, nennen wir die Folge Z-regulär. Es ist wie ein Computerprogramm, das sehr effizient rechnet.
Held B: Der Zauberer (Die Mahler-Gleichung)
Jetzt stellen Sie sich einen Zauberer vor, der eine magische Gleichung besitzt. Diese Gleichung verknüpft eine Funktion (eine Art unendliche Summe) mit ihrer eigenen "Verjüngung".
- Im normalen Zehnersystem (oder bei Potenzen von 2) macht der Zauberer etwas Einfaches: Er nimmt die Funktion und ersetzt $x$ durch $x^2$ (oder $x^k$ ). Das ist wie ein Zeitraffer.
- Im Zeckendorf-System ist das aber komplizierter. Da die Fibonacci-Zahlen nicht einfach "mal 2" sind, muss der Zauberer einen anderen Trick anwenden. Er benutzt eine Funktion $\phi$ , die den Code einer Zahl in den Code der "nächsten" Fibonacci-Stufe verwandelt.
- Eine Z-Mahler-Gleichung ist eine Gleichung, die diese Funktion $\phi$ benutzt. Wenn eine Zahlenfolge eine Lösung dieser Gleichung ist, nennen wir sie Z-Mahler.

3. Die große Entdeckung: Die Brücke zwischen Roboter und Zauberer

Das Kernstück des Papers ist die Frage: Sind diese beiden Helden eigentlich dasselbe?

Die alte Regel (für das Zehnersystem): Es war schon lange bekannt, dass im normalen Zehnersystem (oder bei Potenzen von Primzahlen) ein Roboter und ein Zauberer fast immer dasselbe tun. Wenn eine Folge von einem Roboter berechnet werden kann, kann sie auch durch eine solche magische Gleichung beschrieben werden – und umgekehrt.
Das Problem: Im Zeckendorf-System (Fibonacci) funktioniert das nicht so einfach. Der Trick des Zauberers (die Funktion $\phi$ ) ist nicht perfekt linear. Wenn Sie zwei Zahlen addieren und dann den Trick anwenden, ist das Ergebnis nicht immer genau das Gleiche wie wenn Sie den Trick auf die einzelnen Zahlen anwenden und dann addieren. Es gibt einen kleinen "Fehler" oder "Defekt".

Die Lösung der Autoren:
Die Autoren haben einen neuen Weg gefunden, um diese Lücke zu schließen.

Vom Roboter zum Zauberer: Sie zeigen, dass jeder Roboter, der im Zeckendorf-System arbeitet, auch eine Lösung einer Z-Mahler-Gleichung ist. Das ist wie zu beweisen, dass jeder gute Koch auch ein Rezept schreiben kann.
Vom Zauberer zum Roboter (Das große Meisterstück): Das ist der schwierigere Teil. Sie beweisen: Wenn eine Zahlenfolge eine Lösung einer isolierten Z-Mahler-Gleichung ist (eine spezielle Art von Gleichung, bei der der "Anfang" der Reihe klar definiert ist), dann gibt es immer einen Roboter, der diese Folge berechnet.

Wie haben sie das gemacht?
Sie haben einen neuen, super-smarten Roboter gebaut. Dieser Roboter hat ein extra Gedächtnis. Er merkt sich nicht nur den aktuellen Weg, sondern auch den kleinen "Fehler" (den Defekt), der entsteht, weil die Fibonacci-Mathematik nicht perfekt linear ist.

Die Analogie: Stellen Sie sich vor, Sie laufen durch ein Labyrinth, aber der Boden ist leicht schief. Ein normaler Roboter würde stolpern. Der neue Roboter der Autoren trägt jedoch einen kleinen "Wasserwaagen-Sensor" (den Defekt-Rechner) bei sich. Er korrigiert seine Schritte ständig, basierend darauf, wie schief der Boden ist. So schafft er es, die magische Gleichung in einen einfachen Roboter-Algorithmus umzuwandeln.

4. Warum ist das wichtig?

Verbindung von Welten: Die Arbeit verbindet zwei Welten: die Welt der Algebra (magische Gleichungen) und die Welt der Informatik (Roboter/Automaten).
Neue Einsichten: Sie zeigen, dass man auch in komplexen Zahlensystemen (wie Fibonacci) Ordnung schaffen kann.
Warnung: Sie zeigen auch, dass man vorsichtig sein muss. Wenn die magische Gleichung nicht die richtige Form hat (nicht "isoliert" ist), dann funktioniert der Roboter-Trick nicht mehr. Es gibt dann Lösungen, die zu kompliziert sind, um von einem endlichen Roboter berechnet zu werden.

Zusammenfassung in einem Satz

Die Autoren haben bewiesen, dass man für Zahlenfolgen im Fibonacci-Code (Zeckendorf-System) immer einen einfachen Computer-Roboter bauen kann, solange die Folge durch eine bestimmte Art von magischer Gleichung beschrieben wird – vorausgesetzt, man gibt dem Roboter ein kleines extra Werkzeug mit, um die kleinen Unregelmäßigkeiten des Fibonacci-Systems auszugleichen.

Es ist wie der Beweis, dass man jedes komplizierte mathematische Rätsel, das mit Fibonacci-Zahlen zu tun hat, in eine einfache, schrittweise Anleitung für einen Roboter übersetzen kann.

1. Problemstellung und Motivation

Das Paper adressiert die Lücke zwischen der Theorie der automatischen Folgen (automata sequences) und der Regulärität (regularity) in allgemeinen Zahlsystemen, speziell im Zeckendorf-System.

Hintergrund: Christols Theorem verbindet die Algebraizität formaler Potenzreihen über endlichen Körpern mit der Berechenbarkeit durch endliche Automaten (basierend auf der $p$ -adischen Darstellung). Allouche und Shallit erweiterten dies auf $k$ -reguläre Folgen, die durch gewichtete Automaten generiert werden, und Becker sowie Dumas zeigten den Zusammenhang zwischen $k$ -regulären Folgen und Lösungen von $k$ -Mahler-Gleichungen (Gleichungen der Form $P(x, y) = \sum A_i(x) \Phi^i(y) = 0$ mit $\Phi(f(x)) = f(x^k)$ ).
Das Problem: Diese Ergebnisse gelten primär für Basis- $k$ -Zahlsysteme, wo die Operation „Anhängen einer Null" der Multiplikation mit $k$ entspricht ( $n \mapsto kn$ ). Im Zeckendorf-System (basierend auf Fibonacci-Zahlen $F_n$ ) ist diese Eigenschaft nicht linear. Die natürliche Verallgemeinerung der Abbildung $n \mapsto kn$ ist hier eine Funktion $\phi$ , die nicht linear ist.
Ziel: Die Autoren wollen einen „Christol-ähnlichen" Satz für das Zeckendorf-System beweisen. Sie definieren $Z$ -Mahler-Gleichungen und untersuchen, ob Lösungen isolierender $Z$ -Mahler-Gleichungen genau den $Z$ -regulären Folgen entsprechen (d.h. durch gewichtete Automaten generiert werden können).

2. Methodik und Kernkonzepte

Die Methode basiert auf der Konstruktion gewichteter Automaten, die die Koeffizienten der Lösungen von Mahler-Gleichungen berechnen.

A. Das Zeckendorf-System und die Funktion $\phi$

Das Zeckendorf-System $Z$ verwendet die Fibonacci-Zahlen als Basis. Jede natürliche Zahl hat eine eindeutige Darstellung als Summe nicht-konsekutiver Fibonacci-Zahlen.
Die Autoren definieren eine Abbildung $\phi: \mathbb{N} \to \mathbb{N}$ , die analog zur Multiplikation mit $k$ in Basis- $k$ wirkt: Wenn $(n)_Z = \sum b_i F_i$ , dann ist $\phi(n) = \sum b_i F_{i+1}$ .
Herausforderung: $\phi$ ist nicht linear. Es gilt $\phi(m+n) \neq \phi(m) + \phi(n)$ im Allgemeinen.
Lösung: Die Autoren nutzen das Konzept des Linearitätsdefekts $\delta(m, n) = \phi(m+n) - \phi(m) - \phi(n$ . Sie zeigen (Lemma 18), dass dieser Defekt nur die Werte $\{-1, 0, 1\}$ annimmt.
Regulärität des Defekts: Ein entscheidender Schritt ist der Beweis (Theorem 19, Proposition 20), dass die Berechnung von $\delta(m-n, n)$ durch einen deterministischen Automaten erfolgen kann, der die Zeckendorf-Darstellungen von $m$ und $n$ liest.

B. Definition von $Z$ -Mahler-Gleichungen

Anstelle des Frobenius-Operators $\Phi(f(x)) = f(x^k)$ definieren die Autoren einen Operator $\Phi: R[[x]] \to R[[x]]$ basierend auf $\phi$ :
$\Phi\left(\sum f_n x^n\right) = \sum f_n x^{\phi(n)}$
Eine $Z$ -Mahler-Gleichung ist eine Gleichung der Form:
$P(x, y) = \sum_{i=0}^d A_i(x) \Phi^i(y) = 0$
Eine Gleichung heißt isoliert (isolating), wenn der Koeffizient $A_0(x)$ der konstante Term 1 ist (d.h. $y$ steht isoliert auf der linken Seite).

C. Konstruktion des gewichteten Automaten

Die Autoren konstruieren einen universellen gewichteten Automaten, der die Koeffizienten der Lösung berechnet.

Im Gegensatz zum Basis- $k$ -Fall, wo der Zustand nur den Index modulo $k$ und den Grad des Polynoms verfolgt, muss der Automat im Zeckendorf-Fall zusätzlich den Linearitätsdefekt verfolgen.
Der Zustandsraum des Automaten $A(P, f_0)$ $A (P, f_{0})$ besteht aus Tupeln $(i, j, q, u)$ $(i, j, q, u)$ , wobei:
- $i, j$ : Indizes bezogen auf den Exponenten der Gleichung und den Grad.
- $q$ : Zustand eines Hilfsautomaten, der den Defekt $\delta$ berechnet.
- $u$ : Ein Wort, das als „Fenster" dient, um den Defekt für die aktuelle Eingabe zu berechnen.
Die Transitionen des Automaten simulieren die Rekursionsformel der Koeffizienten, die durch die $Z$ -Mahler-Gleichung gegeben ist, unter Berücksichtigung des Defekts $\delta$ .

3. Wichtige Ergebnisse

A. Haupttheorem (Theorem 1 & 29)

Hauptsatz: Sei $R$ ein kommutativer Ring und $P(x, y) = 0$ eine isolierte $Z$ -Mahler-Gleichung. Wenn $f(x)$ eine Lösung dieser Gleichung ist, dann ist die Folge der Koeffizienten von $f$ $Z$ -regulär. Das bedeutet, es existiert ein gewichteter $Z$ -Automat, der diese Folge generiert.
Umkehrung (Corollary 34): Jede $Z$ -reguläre Reihe ist eine Lösung einer (möglicherweise nicht-isolierten) $Z$ -Mahler-Gleichung.
Grenzen der Isolation: Die Autoren zeigen in Proposition 38, dass die Bedingung „isoliert" notwendig ist. Sie geben ein Beispiel einer nicht-isolierten $Z$ -Mahler-Gleichung, deren Lösung nicht $Z$ -regulär ist (die Koeffizienten wachsen zu schnell, um von einem endlichen Automaten generiert zu werden).

B. Universeller Automat und Komplexität

Die Autoren definieren einen universellen gewichteten $k$ -Automaten (Theorem 2), der für jede isolierte $k$ -Mahler-Gleichung durch Instantiierung der Gewichte die Lösung generiert.
Für das Zeckendorf-System wird die Anzahl der Zustände des generierten Automaten abgeschätzt (Theorem 29, Lemma 31). Die Anzahl der Zustände wächst polynomial in Bezug auf den Exponenten $d$ und die Höhe $h$ der Gleichung, enthält jedoch einen zusätzlichen Faktor, der vom goldenen Schnitt $\phi$ abhängt und durch die Notwendigkeit des „Defekt-Fensters" (Länge $g$ ) bedingt ist.

C. Verallgemeinerung

Die Ergebnisse lassen sich auf beliebige Pisot-Zahlsysteme verallgemeinern, bei denen die charakteristische Polynom der Rekursion die Minimalpolynom einer Pisot-Zahl ist.

4. Bedeutung und Beitrag

Erweiterung der Theorie: Das Paper schließt eine wichtige Lücke in der Theorie der regulären Folgen, indem es die Äquivalenz zwischen Mahler-Gleichungen und gewichteten Automaten von der klassischen Basis- $k$ -Welt auf das Zeckendorf-System (und damit auf Pisot-Systeme) überträgt.
Neue Konstruktion: Es bietet eine direkte Konstruktion von gewichteten Automaten für Lösungen von Mahler-Gleichungen, die keine Cartier-Operatoren benötigt. Da Cartier-Operatoren im Zeckendorf-Kontext nicht die gewünschten Eigenschaften haben, ist diese direkte Konstruktion ein wesentlicher methodischer Fortschritt.
Verständnis von Nicht-Linearität: Die Arbeit zeigt, wie man mit der Nicht-Linearität der Basis-Operation in Pisot-Systemen umgehen kann, indem man den „Defekt" als berechenbare Größe in den Automaten integriert.
Offene Probleme: Die Autoren diskutieren offene Fragen, wie z.B. eine vollständige Charakterisierung von $Z$ -regulären Folgen (ähnlich wie in [BCCD19] für $\mathbb{C}$ ) und die Existenz von $Z$ -regulären Folgen, die keine Lösungen isolierter $Z$ -Mahler-Gleichungen sind (ein Gegenstück zu Ergebnissen von Adamczewski und Bell für $k$ -Mahler-Gleichungen).

Zusammenfassend etablieren Carton und Yassawi eine robuste algebraisch-automatentheoretische Verbindung für das Zeckendorf-System, die als Fundament für weitere Untersuchungen zu Transzendenz und Substitutionstiling in Pisot-Systemen dienen kann.