💻 computer science

Mahler equations for Zeckendorf numeration

This paper generalizes results by Becker and Dumas by establishing a correspondence between Z-regular sequences and solutions of Z-Mahler equations within the Zeckendorf numeration system, while demonstrating that the isolating condition is necessary for the converse and providing a new construction for weighted automata generating q-regular sequences.

Original authors: Olivier Carton, Reem Yassawi

Published 2026-03-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Olivier Carton, Reem Yassawi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to understand how numbers are built. Usually, we use Base-10 (0-9) or Base-2 (0 and 1, like computers). In these systems, if you add a zero to the end of a number, you simply multiply it by 10 or 2. It's a neat, predictable trick.

But there is a different way to count called Zeckendorf numeration. Instead of powers of 2 or 10, this system uses Fibonacci numbers (1, 2, 3, 5, 8, 13...). The rule is strict: you can't use two consecutive Fibonacci numbers (like 3 and 5) to build a number. It's like a puzzle where every number has one unique, "canonical" way to be built from these blocks.

This paper is about a mathematical detective story involving two main characters: Automata (simple, rule-following machines) and Equations (mathematical recipes).

The Two Characters

The Machine (Weighted Automata):
Think of this as a tiny robot that reads a number written in Zeckendorf code (a string of 0s and 1s). As the robot reads the code, it hops between different rooms (states). Each time it hops, it picks up a "weight" (a number). When it finishes reading the whole code, it adds up all the weights it collected. The final sum is the answer for that number.
- Analogy: Imagine a vending machine. You put in a code (like "101"). The machine follows a specific path, collecting coins along the way. The total money in the tray is the output. If the machine is simple enough, the sequence of outputs is called Z-regular.
The Recipe (Mahler Equations):
This is a special kind of math equation that relates a function to its own "shifted" version. In normal math, shifting might mean replacing $x$ with $x^2$ . In this Zeckendorf world, "shifting" means replacing a number with the next Fibonacci number in the sequence.
- Analogy: Imagine a recipe that says, "To make the soup for today, take the soup from yesterday, add some spices, and mix it with the soup from two days ago." If you can describe the whole sequence of soups using just this one rule, the sequence is a Z-Mahler solution.

The Big Question

The authors wanted to know: Are these two characters the same?

If a robot (Automaton) can generate a sequence of numbers, can we write a recipe (Equation) that describes it?
If we have a recipe, can we build a robot to follow it?

In standard Base-10 or Base-2 math, the answer is "Yes, mostly." But Zeckendorf math is trickier because the "shifting" rule isn't as clean as multiplying by 10.

The Breakthrough

The paper proves two main things:

1. From Recipe to Robot (The Main Result):
If you have a "good" recipe (called an isolating Z-Mahler equation), you can always build a robot to generate the numbers.

The Catch: Because the Zeckendorf system is messy (adding numbers doesn't always work like normal addition), the robot needs a "memory aid." The authors had to invent a special internal mechanism for the robot to track "errors" or "defects" that happen when the math gets weird.
The Metaphor: Imagine trying to walk a straight line, but the ground keeps shifting under your feet. To stay on the path, you need a GPS that constantly recalculates your position. The authors built a "GPS" (a specific type of state in the robot) that tracks these shifts, allowing the robot to follow the recipe perfectly.

2. From Robot to Recipe:
If a robot generates a sequence, that sequence must satisfy a recipe (a Z-Mahler equation). This is the easier direction, similar to how any simple pattern can be described by a rule.

Why Does This Matter?

It Connects Two Worlds: It bridges the gap between computation (machines doing things) and algebra (equations solving things). It shows that if a sequence is "computable" by a simple machine in this Fibonacci world, it is also "algebraic" in a specific sense.
It's a Generalization: This work extends famous theorems from standard math (like Christol's Theorem) to this more complex Fibonacci world.
The "Non-Isolating" Warning: The authors also found a trap. If the recipe isn't "isolating" (a specific technical condition), the robot might fail. They gave an example of a recipe that looks valid but produces numbers that grow so fast and chaotically that no simple robot could ever generate them. It's like a recipe that says "add a pinch of salt," but the pinch gets bigger every time, eventually overflowing the kitchen.

The "Universal" Robot

One of the coolest ideas in the paper is the Universal Weighted Automaton.

Analogy: Think of a "Lego Master Set." You have one giant box of bricks. Depending on how you snap the bricks together (based on the coefficients in your equation), you can build any robot needed to solve any specific problem of this type. You don't need to design a new robot from scratch for every new equation; you just reconfigure the universal one.

Summary

This paper is about proving that in the world of Fibonacci numbers, simple machines and mathematical recipes are two sides of the same coin. The authors had to invent new tools (like the "GPS" for tracking math errors) to make the connection work, showing that even in a messy, non-standard number system, order and predictability still reign supreme.

1. Problem Statement and Context

The paper addresses the generalization of Christol's Theorem and the relationship between regular sequences and Mahler equations from standard base- $k$ numeration systems to Pisot numeration systems, specifically the Zeckendorf numeration (based on Fibonacci numbers).

Background:
- Christol's Theorem: Establishes that a sequence over a finite field $\mathbb{F}_q$ is $q$ -automatic (generated by a finite automaton reading base- $q$ expansions) if and only if its generating function is algebraic over $\mathbb{F}_q(x)$ .
- Regularity: Allouche and Shallit generalized automaticity to regular sequences over commutative rings, generated by weighted automata.
- Mahler Equations: Becker and Dumas established a link between $k$ -regular sequences and $k$ -Mahler equations (functional equations of the form $\sum A_i(x) \Phi^i(y) = 0$ , where $\Phi(f(x)) = f(x^k)$ ). They showed that solutions to isolating $k$ -Mahler equations (where the coefficient of $y$ is 1) are $k$ -regular.
The Gap: While these results hold for base- $k$ systems, they do not directly apply to abstract numeration systems like Zeckendorf (Fibonacci) numeration. In base- $k$ , appending a digit corresponds to a linear operation ( $n \mapsto kn + d$ ). In Zeckendorf numeration, the analogous operation is non-linear, breaking standard proof techniques involving Cartier operators.
Objective: The authors aim to establish a "Christol-type" theorem for Zeckendorf numeration ( $Z$ ). Specifically, they seek to prove that solutions to isolating $Z$ -Mahler equations are $Z$ -regular (generated by weighted automata) and vice versa.

2. Methodology

The authors employ a combination of automata theory, number theory (properties of Pisot numbers), and formal power series analysis.

A. The Zeckendorf Numeration and the Map $\phi$

Zeckendorf System ( $Z$ ): Every integer $n$ has a unique representation as a sum of non-consecutive Fibonacci numbers ( $F_i$ ). The digit set is $\{0, 1\}$ .
The Operator $\Phi$ : In base- $k$ $k$ , the operator is $\Phi(f(x)) = f(x^k)$ $Φ (f (x)) = f (x^{k})$ . For Zeckendorf, the authors define a linear operator $\Phi: R[[x]] \to R[[x]]$ $Φ : R [[x]] \to R [[x]]$ based on a function $\phi: \mathbb{N} \to \mathbb{N}$ $ϕ : N \to N$ .
- If $n = \sum b_i F_i$ , then $\phi(n) = \sum b_i F_{i+1}$ .
- $\Phi(\sum f_n x^n) = \sum f_n x^{\phi(n)}$ .
The Linearity Defect: The critical obstacle is that $\phi$ $ϕ$ is not linear. While $\phi(m+n) = \phi(m) + \phi(n)$ $ϕ (m + n) = ϕ (m) + ϕ (n)$ holds if $m$ $m$ and $n$ $n$ have disjoint support in their Zeckendorf expansions, it fails generally.
- The authors define the linearity defect $\delta(m, n) = \phi(m+n) - \phi(m) - \phi(n)$ .
- They prove (Lemma 18) that $\delta(m, n) \in \{-1, 0, 1\}$ .

B. Automata Construction for the Defect

To handle the non-linearity, the authors construct a deterministic automaton that computes the defect $\delta(m-n, n)$ given the Zeckendorf expansions of $m$ and $n$ .
This relies on the fact that the set of words representing zero in Zeckendorf numeration is regular (Theorem 19).
This automaton tracks the "carry" or "defect" information required to simulate the non-linear map $\phi$ within a weighted automaton framework.

C. Universal Weighted Automata

Base- $k$ Case: The authors first revisit the base- $k$ case (Section 2.4). They construct a universal weighted $k$ -automaton that can generate the solution to any isolating $k$ -Mahler equation by instantiating the coefficients of the equation as transition weights. This avoids the need for Cartier operators.
Zeckendorf Case: They extend this construction to Zeckendorf numeration. The state set of the new automaton includes:
1. Indices related to the degree of the Mahler equation.
2. Indices tracking the "height" (degree of polynomials).
3. Crucially: A state from the defect-computing automaton and a buffer of digits to track the linearity defect $\delta$ .

3. Key Contributions

Definition of $Z$ -Mahler Equations: The paper introduces $Z$ -Mahler equations as functional equations involving the operator $\Phi$ defined by the Zeckendorf map $\phi$ .
Construction of the Defect Automaton: A novel construction of a deterministic automaton that computes the linearity defect $\delta(m, n)$ , proving that the non-linearity of $\phi$ is "regular" and computable.
Universal Automaton for $Z$ -Mahler Equations: The authors define a universal weighted automaton that, given an isolating $Z$ -Mahler equation and an initial condition, generates the unique solution sequence.
State Complexity Bounds: They provide explicit bounds on the number of states required for the automaton generating the solution, showing it depends on the exponent $d$ , height $h$ , and the golden ratio $\phi$ .

4. Main Results

Theorem 1 (Main Result): Solvability implies Regularity

Let $R$ be a commutative ring and $P(x, y) = 0$ be an isolating $Z$ -Mahler equation (where the coefficient of $y$ is 1). If $f(x) = \sum f_n x^n$ is a solution, then the sequence $(f_n)_{n \ge 0}$ is $Z$ -regular.

Proof Strategy: The solution coefficients are computed by a weighted automaton constructed by combining the universal automaton structure with the defect-tracking automaton. The non-linearity of $\phi$ is managed by the defect component of the state.

Theorem 29 (Quantitative Result)

For a $Z$ -Mahler equation of exponent $d$ and height $h$ , there exists a deterministic automaton generating the solution with at most $O(d h^2)$ states (specifically bounded by $45d(3h+1)h$ ). This is compared to the $O(dh)$ bound in the base- $k$ case, highlighting the cost of tracking the linearity defect.

Corollary 34: Regularity implies Solvability

Conversely, any $Z$ -regular series is a solution to a (possibly non-isolating) $Z$ -Mahler equation. This direction is proven by showing that the kernel of a regular sequence is finite and using linear algebra to eliminate higher-order terms.

Counter-Example (Non-Isolating Case)

The authors provide an example (Proposition 38) of a non-isolating $Z$ -Mahler equation: $(1-x)f(x) = \Phi(f(x))$ .

They prove that the solution to this equation has coefficients that grow super-polynomially ( $f_n \ge C n^k$ for all $k$ ).
By Lemma 5, $Z$ -regular sequences must have polynomially bounded coefficients.
Conclusion: The restriction to isolating equations is necessary; non-isolating equations can yield non-regular solutions.

5. Significance and Implications

Generalization of Classical Theory: The paper successfully extends the deep connection between algebraic/functional equations and automata theory from base- $k$ to the Fibonacci (Zeckendorf) base, a fundamental Pisot numeration system.
Overcoming Non-Linearity: The methodology of explicitly constructing an automaton to track the "linearity defect" offers a new technique for handling numeration systems where the shift operation is not a simple linear map. This could be applicable to other Pisot systems.
New Construction for Regular Sequences: The "universal automaton" approach provides a direct, constructive method for generating regular sequences from Mahler equations without relying on Cartier operators, which are difficult to define in non-standard numeration systems.
Open Problems: The authors note that while they have shown isolating equations yield regular sequences, the converse (characterizing exactly which regular sequences satisfy isolating equations) remains open for Zeckendorf numeration, unlike the case for base- $k$ over finite fields. They also raise questions about the transcendence of values of $Z$ -Mahler functions, analogous to Mahler's method.

In summary, this paper establishes a robust theoretical framework linking Mahler-type functional equations and weighted automata in the context of Zeckendorf numeration, overcoming the inherent non-linearity of the Fibonacci base through novel automata constructions.