💻 computer science

Mahler equations for Zeckendorf numeration

本文定义了基于 Zeckendorf 进位制的广义 Z-Mahler 方程，证明了 Z-正则序列与特定 Z-Mahler 方程解之间的等价关系，并通过反例和新的加权自动机构造推广了 Becker 和 Dumas 的相关成果。

原作者： Olivier Carton, Reem Yassawi

发布于 2026-03-17

📖 1 分钟阅读☕ 轻松阅读

原作者： Olivier Carton, Reem Yassawi

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文探讨了一个非常有趣的数学领域，我们可以把它想象成是在**“给数字换一种语言”，然后看看这些数字背后隐藏的“自动机器”和“魔法公式”**之间的关系。

为了让你轻松理解，我们把这篇论文的核心内容拆解成几个生动的故事：

1. 背景：数字的两种“方言”

想象一下，我们平时数数用的是十进制（0, 1, 2... 9），这就像是我们说的“普通话”。
但在数学界，还有一种特殊的数数方法叫齐肯多夫（Zeckendorf）系统。

规则：它只用 0 和 1，而且不能有两个 1 挨在一起（比如不能有"11"）。
例子：在十进制里，8 就是 8。但在齐肯多夫系统里，8 被表示为 $5+3$ ，写成二进制串就是 1000（对应斐波那契数列：5, 3, 2, 1...）。
比喻：这就像是用一种特殊的“摩斯密码”来写数字，这种密码有严格的规则（不能连点）。

2. 主角一：自动机器（Weighted Automata）

想象有一台**“智能点钞机”**（自动机）。

你给它一张写有数字“摩斯密码”的纸条（比如 1000 代表 8）。
机器内部有很多小齿轮和开关（状态）。
当它读取纸条上的每一个数字时，齿轮会转动，并给结果加上一些**“权重”**（比如 +1 分，或者 +2 分）。
最后，机器把所有路径的分数加起来，吐出一个数字。
论文发现：如果这台机器能算出某个数列（比如第 8 个数是多少），我们就说这个数列是**“齐肯多夫正则”**的。这就像机器能“读懂”这种特殊语言并算出规律。

3. 主角二：魔法公式（Mahler 方程）

现在，想象有一个**“魔法预言家”**（方程）。

这个预言家不看具体的数字，而是看整个数列的**“整体形状”**（生成函数）。
它有一个特殊的魔法咒语： $\Phi$ $Φ$ 。
- 在普通十进制里，这个咒语是把数字 $n$ 变成 $n \times k$ （比如把 1 变成 10，2 变成 20）。
- 但在齐肯多夫系统里，这个咒语更复杂：它把数字 $n$ 变成 $n$ 的“下一个斐波那契版本”（比如把代表 5 的 100 变成代表 8 的 1000）。
魔法公式：预言家说：“如果你把数列的某些部分按照这个咒语变换后加起来，结果必须等于 0。”
如果有一个数列能满足这个复杂的方程，我们就说它是**“齐肯多夫 - 马勒（Z-Mahler）”**的。

4. 论文的核心发现：它们是一对“双胞胎”

这篇论文的主要成就，就是证明了**“智能点钞机”和“魔法预言家”其实是同一回事**的两种不同表现！

定理 1（从机器到公式）：如果你有一台能算出数列的“智能点钞机”，那么一定存在一个“魔法公式”能描述这个数列。
- 比喻：只要机器能算，就一定能写出它的“操作说明书”（公式）。
定理 2（从公式到机器）：如果你有一个“魔法公式”（而且这个公式是**“隔离的”**，意思是它没有那种会让结果无限爆炸的坏毛病），那么一定存在一台“智能点钞机”能算出这个数列。
- 比喻：只要说明书写得够清楚（隔离的），我们就能造出一台机器来执行它。

5. 最大的挑战：为什么这次很难？

在普通的十进制里，把数字 $n$ 变成 $10n$ 是非常简单的，就像把一串珠子往左移一位。
但在齐肯多夫系统里，把 $n$ 变成它的“斐波那契版本”（ $\phi(n)$ ）并不简单，它不是简单的线性移动。

比喻：在十进制里，加 1 就是进位，很规则。但在齐肯多夫系统里，加 1 可能会引发一连串的连锁反应（比如 100 加 1 变成 101，但 101 加 1 不能变成 102，因为不能有 2，必须变成 1000 这种跳跃）。
作者的突破：作者发现，虽然这个变换不完美（有“线性缺陷”），但这个缺陷很小，而且可以用一台**“小机器”**来专门计算这个缺陷。
解决方案：他们把“计算数列的主机器”和“计算缺陷的小机器”拼在一起，造出了一台超级机器，从而证明了即使在这个复杂的系统里，机器和公式依然是相通的。

6. 一个有趣的反例

论文还展示了一个**“坏孩子”**：

如果魔法公式不是“隔离的”（比如公式里有个 $1-x$ 在分母位置），那么算出来的数列可能会长得太快，导致没有任何一台有限的“智能点钞机”能算出它。
这就像是一个预言家给出的指令太模糊，导致机器根本没法造出来。

总结

这篇论文就像是在说：

“无论我们是用**‘特殊的摩斯密码’（齐肯多夫系统）来数数，还是用‘复杂的魔法公式’来描述规律，只要规则是好的（隔离的），‘机器计算’和‘公式描述’**就是完全等价的。我们不仅证明了这一点，还发明了一种新的方法，把‘计算缺陷’的小零件加进了机器里，解决了以前无法解决的难题。”

这对数学界来说是一个重要的进步，因为它把代数（公式）和计算机科学（自动机）在一种更复杂的数字系统里重新连接了起来。

这是一份关于论文《MAHLER EQUATIONS FOR ZECKENDORF NUMERATION》（Zeckendorf 数制下的 Mahler 方程）的详细技术总结。

1. 研究背景与问题 (Problem)

背景：

Christol 定理建立了有限域上形式幂级数的代数性与 $p$ -自动序列（ $p$ -automatic sequences）之间的联系。
Allouche 和 Shallit 引入了**正则序列（regular sequences）**的概念，将其推广到加权自动机（weighted automata）生成的序列，并允许系数在交换环 $R$ 中取值。
Becker 和 Dumas 证明了对于 $k \ge 2$ ， $k$ -正则序列满足 $k$ -Mahler 方程，反之，隔离（isolating） $k$ -Mahler 方程的解是 $k$ -正则序列。这里的 $k$ -Mahler 方程涉及算子 $\Phi(f(x)) = f(x^k)$ 。
局限性： Christol 定理和 Becker-Dumas 的结果主要基于 $k$ 进制数制（ $n \mapsto kn$ 是线性映射）。然而，对于更一般的 Pisot 数制（如 Zeckendorf 数制，基于斐波那契数）， $n \mapsto kn$ 的类比映射不再是线性的，导致传统的 Cartier 算子方法失效。

核心问题：
论文旨在解决以下问题：

能否将 Becker 和 Dumas 关于 $k$ -Mahler 方程与正则序列之间联系的结果，推广到 Zeckendorf 数制（基于斐波那契数 $F_n$ ）？
在 Zeckendorf 数制下，如何定义合适的"Z-Mahler 方程”？
隔离的 Z-Mahler 方程的解是否由加权自动机生成（即是否为 Z-正则序列）？反之是否成立？

2. 方法论 (Methodology)

作者采用了一种结合自动机理论、数制性质和形式幂级数的方法：

定义 Z-Mahler 算子 $\Phi$ ：
在 $k$ 进制中，算子 $\Phi(f(x)) = f(x^k)$ 对应于 $n \mapsto kn$ 。在 Zeckendorf 数制中，作者定义了一个映射 $\phi: \mathbb{N} \to \mathbb{N}$ ，其中 $\phi(n)$ 对应于将 $n$ 的 Zeckendorf 表示左移一位（即 $F_i \to F_{i+1}$ ）。
定义算子 $\Phi(\sum f_n x^n) = \sum f_n x^{\phi(n)}$ 。
关键难点： $\phi$ 不是线性映射（即 $\phi(m+n) \neq \phi(m) + \phi(n)$ ），这破坏了传统 Mahler 方程证明中使用的代数结构。
处理非线性缺陷（Linearity Defect）：
作者定义了线性缺陷 $\delta(m, n) = \phi(m+n) - \phi(m) - \phi(n)$ 。
利用 Frougny 和 Solomyak 关于加法正规化的工作，证明了 $\delta(m, n)$ 的取值范围很小（在 $\{-1, 0, 1\}$ 中），并且计算 $\delta$ 的函数可以由一个确定性自动机实现。
构造通用加权自动机：
- $k$ -进制情况： 作者首先重新构建了 Becker-Dumas 的证明，定义了一个“通用加权 $k$ -自动机”，通过实例化系数来生成任何隔离 $k$ -Mahler 方程的解，避免了使用 Cartier 算子。
- Zeckendorf 情况： 为了处理 $\phi$ $ϕ$ 的非线性，作者构造了一个更复杂的加权自动机。该自动机的状态不仅包含传统的索引，还包含：
  1. 用于追踪 $\phi$ 迭代次数的索引。
  2. 用于追踪多项式次数的索引。
  3. 关键创新： 一个子自动机的状态，用于实时计算并追踪线性缺陷 $\delta$ 。
    通过这种方式，自动机能够模拟 Z-Mahler 方程的递归关系，即使 $\phi$ 不是线性的。
证明方向：
1. 正向： 证明任何 Z-正则序列都满足某个 Z-Mahler 方程（通过核（kernel）方法和线性代数消元）。
2. 反向（主要贡献）： 证明任何隔离 Z-Mahler 方程的解都可以由一个加权自动机生成。

3. 关键贡献 (Key Contributions)

Z-Mahler 方程的定义：
首次为 Zeckendorf 数制定义了 Z-Mahler 方程：
$P(x, y) = \sum_{i=0}^d A_i(x) \Phi^i(y) = 0$
其中 $\Phi$ 是基于 $\phi(n)$ 的算子，而非 $x^k$ 。
Z-正则性与 Z-Mahler 方程的等价性（在隔离条件下）：
定理 1 (Theorem 1)： 如果 $P(x, y)=0$ 是一个隔离的 Z-Mahler 方程（即 $A_0(x)=1$ ），且 $f$ 是其解，则存在一个加权 Z-自动机生成 $f$ 的系数序列。
这是 Becker-Dumas 结果在 Zeckendorf 数制下的直接推广。
通用加权自动机的构造：
提出了一个通用的加权自动机框架，能够生成任何隔离 Mahler 方程（无论是 $k$ -进制还是 Zeckendorf）的解。这为理解正则序列的自动机结构提供了新的视角。
非隔离方程的反例：
证明了如果 Z-Mahler 方程不是隔离的，其解不一定是 Z-正则序列。
命题 38 (Proposition 38)： 方程 $(1-x)f(x) = \Phi(f(x))$ 的解 $f(x)$ 不是 Z-正则的。作者通过分析系数 $f_n$ 的增长速度（证明其增长快于多项式，违反了正则序列的有界性条件）来证明这一点。
状态复杂度的界限：
给出了生成 Z-Mahler 方程解的自动机状态数量的上界。与 $k$ -进制情况相比，由于需要追踪线性缺陷，状态数量多了一个与黄金分割比 $\phi$ 相关的因子（约为 $O(d \cdot h^2 \cdot \phi^h)$ ）。

4. 主要结果 (Key Results)

定理 14 (Theorem 14)： 对于 $k$ -进制，任何隔离 $k$ -Mahler 方程的解都由加权自动机生成。这是后续 Zeckendorf 结果的基础。
定理 29 (Theorem 29)： 对于 Zeckendorf 数制，任何隔离 Z-Mahler 方程的解都是 Z-正则的。
推论 34 (Corollary 34)： 任何 Z-正则序列都是某个 Z-Mahler 方程的解（可能是非隔离的）。
命题 38 (Proposition 38)： 存在非隔离的 Z-Mahler 方程，其解不是 Z-正则的（例如 $(1-x)f(x) = \Phi(f(x))$ ）。
自动机构造： 成功构造了一个能够计算线性缺陷 $\delta(m, n)$ 的确定性自动机（图 7），这是处理非线性映射 $\phi$ 的核心组件。

5. 意义与影响 (Significance)

理论推广： 将 Christol 定理和 Becker-Dumas 定理从经典的 $k$ -进制数制成功推广到了 Pisot 数制（特别是 Zeckendorf 数制），填补了代数自动机理论在更复杂数制下的空白。
方法创新： 提出了一种不依赖 Cartier 算子（在 Zeckendorf 数制中失效）的新证明方法。通过引入“线性缺陷自动机”来追踪非线性映射的误差，为处理其他非标准数制下的 Mahler 方程提供了新的技术路径。
自动机结构揭示： 揭示了生成正则序列的加权自动机具有统一的“通用”结构，可以通过实例化系数来生成特定的序列。
开放问题： 论文指出了几个未解决的问题，例如：
- 是否存在 Z-正则序列但不是隔离 Z-Mahler 方程的解？（类似于 $k$ -进制中的 Becker 例子）。
- 能否完全刻画 Z-正则序列（类似于 [BCCD19] 在复数域上的工作）？
- 关于 Cobham 型定理在混合数制（如 $k$ -进制和 Zeckendorf 同时成立）下的推广。

总结：
这篇论文通过巧妙的自动机构造，克服了 Zeckendorf 数制中映射非线性的障碍，建立了 Z-Mahler 方程与 Z-正则序列之间的深刻联系。它不仅扩展了经典理论，还展示了如何利用自动机理论来处理数制中的算术缺陷，为代数数论和形式语言理论的交叉研究提供了重要的新工具和新结果。