🔢 mathematics

Balanced Fibonacci word rectangles, and beyond

本文在 Anselmo 等人研究的基础上，证明了由斐波那契词构成的矩形矩阵的平衡性可通过有限自动机判定，并将该结果推广至对应于二次无理数的所有 Sturmian 特征词，同时探讨了 Tribonacci 词和 Thue-Morse 词中的类似问题。

原作者： Jeffrey Shallit, Ingrid Vukusic

发布于 2026-03-31

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Jeffrey Shallit, Ingrid Vukusic

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

这篇论文就像是在探索一个由数字组成的**“无限乐高积木世界”，研究者们试图找出在这个世界里，什么样的“长方形积木块”是完美平衡**的。

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

1. 背景：什么是“斐波那契单词”和“矩形”？

想象一下，你有一串无限长的数字项链，比如：0, 1, 0, 0, 1, 0, 1, 0...。这串数字不是乱排的，而是遵循著名的斐波那契规则（就像兔子生兔子的规律）生成的，我们叫它“斐波那契单词”。

现在，想象你拿一把剪刀，从这串项链上剪下一块长方形的区域。

比如，你剪一个 3 行 4 列 的长方形。
这个长方形里填满了 0 和 1。
如果你把长方形里所有的 0 和 1 加起来，得到一个“总分”。

核心问题来了：
如果你把剪刀在项链上稍微移动一点点（比如从第 1 个数字开始剪，还是从第 2 个数字开始剪），剪出来的同样大小的长方形，它们的“总分”会变化吗？

如果无论怎么剪，总分几乎一样（最多只有两种不同的分值），我们就说这个长方形是**“平衡”的**。
如果剪出来的长方形有的全是 0，有的全是 1，那它们就是**“不平衡”**的。

2. 研究者的发现：用“机器”来寻找平衡

以前，数学家们发现，如果长方形的边长是斐波那契数（比如 2, 3, 5, 8...），那它们通常是平衡的。但还有很多其他情况（比如 4 行 3 列）也是平衡的，大家搞不清楚到底哪些是，哪些不是。

Jeffrey 和 Ingrid 这两位研究者想出了一个绝妙的主意：
他们不靠死算，而是设计了一个**“智能安检机”（有限自动机）**。

这个机器怎么工作？
你把它想象成一个复杂的迷宫。你输入两个数字（长方形的长和宽），机器就会沿着迷宫走。
- 如果它能走到终点，说明这个长方形是平衡的（完美！）。
- 如果它走不通，说明这个长方形不平衡（不完美）。
为什么这很厉害？
以前人们觉得这个问题太复杂，像大海捞针。但这篇论文证明，对于斐波那契数列生成的这种数字世界，这个“安检机”是存在的，而且只有 15 个状态（很小巧）。这意味着，只要有了这个机器，我们就能瞬间判断任何尺寸的长方形是否平衡。

3. 扩展：不仅仅是斐波那契

这篇论文不仅解决了斐波那契的问题，还把这个方法推广到了其他更复杂的“数字世界”：

特里波那契（Tribonacci）世界： 这里的规则稍微复杂一点（像三个兔子生兔子）。研究者发现，对于 1 行或 2 行的长方形，很容易找到平衡的；但一旦长方形变成 3 行或更多，就永远找不到完美的平衡了。这就像试图在一个倾斜的桌面上放稳一个 3 层高的积木塔，怎么放都会倒。
Thue-Morse 世界： 这是一个由 0 和 1 交替生成的特殊序列。在这里，研究者发现了一个有趣的规律：只要长方形的长和宽都是奇数，它的平衡程度就正好是"3"。这就像是一个只有奇数步长的舞步，总是能走出一种特定的节奏。

4. 核心工具：Walnut（一个数学计算器）

论文中大量使用了一个叫 Walnut 的软件。你可以把它想象成一个**“数学翻译官”**。

研究者把复杂的数学逻辑（比如“如果 A 发生，那么 B 就不发生”）写成代码。
Walnut 把这些代码自动翻译成那个“智能安检机”（自动机）。
最后，机器自己跑一遍，告诉人类答案。

这就像是你告诉机器人：“帮我找所有能装下 10 个苹果且重量不超过 5 公斤的篮子。”机器人不仅找到了，还画出了一张地图，告诉你哪些篮子是合格的。

5. 总结与启示

这篇论文就像是在说：

“在这个由数字构成的无限迷宫里，虽然看起来杂乱无章，但其实隐藏着严格的秩序。我们不需要一个个去试，只要造出一台小小的‘平衡检测机’，就能一眼看穿所有长方形积木的秘密。”

简单来说：

问题： 在特定的数字序列里，什么样的长方形切块是“公平”的（0 和 1 的数量差不多）？
方法： 用计算机自动机（一种简单的逻辑机器）来自动判断。
结果： 我们找到了判断斐波那契、特里波那契和 Thue-Morse 序列中长方形是否平衡的“万能公式”（机器）。
意义： 这展示了数学和计算机科学的完美结合——用简单的机器逻辑去解决看似极其复杂的无限序列问题。

这就好比，虽然宇宙中的星星排列看似随机，但如果你有一把特殊的尺子（自动机），你就能发现其中隐藏的几何规律。

这是一份关于论文《Balanced Fibonacci word rectangles, and beyond》（平衡的斐波那契词矩形及推广）的详细技术总结。

1. 研究背景与问题定义

核心概念：
论文研究的是由无限序列生成的 $m \times n$ 矩形矩阵的**平衡性（Balance）**问题。

矩阵定义：给定无限序列 $(a_i)_{i \ge 0}$ ，定义矩阵 $A(i, m, n)$ ，其元素 $a_{k, \ell} = a_{i+k+\ell}$ 。这实际上是一个汉克尔矩阵（Hankel matrix）的变体，其中每一行都是序列的滑动窗口。
和函数：定义 $T(i, m, n)$ 为矩阵 $A(i, m, n)$ 中所有元素之和。
平衡性定义：对于给定的维度 $(m, n)$ ，如果所有可能的起始位置 $i$ 对应的和 $T(i, m, n)$ 的取值集合中，不同值的个数不超过 2，则称该 $(m, n)$ 对是平衡的。

研究动机：

对于二元序列（0 和 1），一维平衡性（即任意两个长度相同的子串中 1 的个数之差不超过 1）是 Sturmian 词的经典性质。
二维平衡性（矩形平衡）是一个更精细的问题。Anselmo 等人之前的研究表明，对于斐波那契词，如果 $\max(m, n)$ 是斐波那契数，则矩形是平衡的。但存在其他平衡对（如 $(4, 3)$ ）。
核心问题：对于斐波那契词、Tribonacci 词和 Thue-Morse 词，究竟哪些 $(m, n)$ 对是平衡的？能否给出一个通用的判定算法？

2. 方法论：有限自动机与 Walnut 系统

论文的核心方法论是利用有限自动机（Finite Automata）和自动定理证明工具 Walnut来解决组合数学中的判定问题。

理论基础：
- 对于二次无理数 $\alpha$ （如黄金分割比 $\phi$ 的倒数），存在算法可以构建有限自动机来识别 $\lfloor n\alpha \rfloor$ 的性质。
- 使用 Ostrowski $\alpha$ -数制（对于斐波那契词即 Zeckendorf 表示法）作为自动机的输入编码。
- 利用 Presburger 算术的扩展，将关于序列平衡性的逻辑公式转化为自动机。
技术实现：
- 作者使用 Walnut 软件（基于自动机理论的定理证明工具）来构建和验证自动机。
- 关键策略：不直接计算 $T(i, m, n)$ 的不同值个数（因为这可能随 $m, n$ 线性增长，无法被有限自动机直接处理），而是利用 Lemma 1 中的判据：
  
  矩形是平衡的，当且仅当差分序列 $\Delta(i, m, n) = T(i+1, m, n) - T(i, m, n)$ 中不包含形如 $1, 0, \dots, 0, 1$ 或 $-1, 0, \dots, 0, -1$ 的块。
- 由于 $\Delta$ 的取值范围很小（ $\{-1, 0, 1\}$ ），这一条件可以用一阶逻辑公式表达，进而转化为接受 $(m, n)$ 的有限自动机。

3. 主要贡献与结果

A. 斐波那契词 (Fibonacci Word)

定理 2 (Theorem 2)：对于任何对应于二次无理数 $\alpha$ 的 Sturmian 特征词，存在一个算法构建有限自动机，输入为 $(m, n)$ （使用 Ostrowski $\alpha$ -数制），当且仅当 $m \times n$ 矩形平衡时接受。
Corollary 3：针对斐波那契词（ $\alpha = \gamma = (3-\sqrt{5})/2$ ），作者构建了一个 15 状态的自动机（图 1），精确判定哪些 $(m, n)$ 对是平衡的。
Corollary 4：通过自动机验证，重新证明了 Anselmo 等人的定理：若 $\max(m, n)$ 是斐波那契数，则矩形平衡。
Proposition 5 & 6：利用自动机证明了关于平衡对的密度和对称性的新性质。例如，平衡对的密度下界约为 $1/(\phi m)$ 。
Theorem 7：给出了一个“人类可读”的充要条件，基于 $m$ 和 $n$ 的 Zeckendorf 展开（斐波那契进制表示）中的最大项及其奇偶性。
Theorem 8 & Corollary 9：研究了“多样性”（Diversity）。证明了对于 $m=n=F_{3k/2}$ ， $T(i, m, n)$ 的不同取值个数至少为 $k+1$ （即 $\Theta(n)$ ），表明平衡性并非总是成立，且不同值的数量随维度增长。

B. Tribonacci 词 (Tribonacci Word)

背景：Tribonacci 词是三元序列，已知是 2-平衡的（一维）。
Theorem 10：研究了 Tribonacci 词矩形的 2-平衡性（即任意两个同尺寸矩形中各字符出现次数之差不超过 2）。
- 若 $m=1$ ，所有 $n$ 均平衡。
- 若 $m=2$ ，存在一个 77 状态的 Tribonacci 自动机判定平衡的 $n$ 。前几个平衡 $n$ 为 1, 2, 3, 4, 7, 8... 结构复杂，无明显简单描述。
- 若 $m \ge 3$ ，不存在任何 $n$ 使得矩形是 2-平衡的。作者通过构造反例（利用特定的 $3 \times 3$ 子矩阵差异）证明了这一点。

C. Thue-Morse 词 (Thue-Morse Word)

Theorem 11：对于 Thue-Morse 词，证明了 $m \times n$ 矩形的和 $T(i, m, n)$ 满足 $|2T(i, m, n) - mn| \le 4$ 。即平衡性在 1 到 4 之间。
Theorem 12：构建了一个 92 状态的自动机，输入为 $m, n$ $m, n$ （二进制），输出该矩形的精确平衡值。
- 技术难点：Thue-Morse 序列的对称性允许将问题转化为负数运算。作者使用了 Base-(-2) 数制在 Walnut 中处理，最后转换回 Base-2。
- 计算规模：这是一个巨大的计算任务，中间自动机状态数高达 3200 万，耗时约 3.5 小时，需 100GB 内存。
Theorem 14：证明了当 $m, n \ge 3$ 时，矩形的平衡值恰好为 3 当且仅当 $m$ 和 $n$ 均为奇数。

4. 意义与影响

算法化组合数学：本文展示了如何利用自动机理论和 Walnut 工具，将复杂的组合平衡性问题转化为可计算的判定问题。这种方法不仅解决了斐波那契词的问题，还推广到了更广泛的 Sturmian 词（二次无理数）和其他著名序列（Tribonacci, Thue-Morse）。
精确刻画：对于斐波那契词，给出了平衡对的完整自动机刻画和基于数制的显式条件，超越了之前仅知道“斐波那契数”这一充分条件的认知。
揭示复杂性：
- 对于 Tribonacci 词，揭示了当维度增加（ $m \ge 3$ ）时，平衡性会完全消失，且 $m=2$ 时的平衡集具有高度复杂性（77 状态自动机）。
- 对于 Thue-Morse 词，通过大规模计算得出了精确的平衡值分布规律。
工具验证：论文中提供的所有 Walnut 代码和 Maple 文件均可公开获取，为后续研究提供了可复现的基准和工具。

总结

该论文通过引入有限自动机方法，系统性地解决了由斐波那契词、Tribonacci 词和 Thue-Morse 词生成的矩形矩阵的平衡性问题。它不仅给出了判定平衡对的算法（自动机），还发现了新的数学性质（如平衡值的分布、不同值数量的增长阶），并展示了自动机技术在解决高维组合序列问题中的强大能力。