🔢 mathematics

Beatty Sequences for a Quadratic Irrational: Decidability and Applications

该论文证明了二次无理数生成的非齐次贝蒂序列是同步的，从而利用自动机方法（如 Walnut 软件）给出了其加法一阶逻辑理论的可判定性新证明，并解决了关于其作为加法基的判定问题及若干开放猜想。

原作者： Luke Schaeffer, Jeffrey Shallit, Stefan Zorcic

发布于 2026-04-03

📖 1 分钟阅读🧠 深度阅读

原作者： Luke Schaeffer, Jeffrey Shallit, Stefan Zorcic

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

这篇论文听起来充满了高深的数学名词（如“二次无理数”、“贝蒂序列”、“自动机”），但如果我们把它拆解开来，用生活中的比喻来解释，它的核心思想其实非常有趣且直观。

简单来说，这篇论文是在给数学中的“数字规律”找一把“万能钥匙”，并证明这把钥匙不仅能打开锁，还能帮我们解决很多以前很难解开的谜题。

以下是用通俗语言和比喻对这篇论文的解读：

1. 什么是“贝蒂序列”？（数字的“楼梯”）

想象你在爬楼梯。

普通的楼梯：你每走一步，高度增加 1。
贝蒂序列（Beatty Sequence）：想象你有一个特殊的“魔法步长”。比如，你的步长是 $\sqrt{2}$ $2$ （约 1.414）。
- 第 1 步：你站在 1.414 的位置，向下取整，记作 1。
- 第 2 步：你站在 2.828 的位置，向下取整，记作 2。
- 第 3 步：你站在 4.242 的位置，向下取整，记作 4。
- 第 4 步：你站在 5.656 的位置，向下取整，记作 5。
- 以此类推，你得到的数字序列是：1, 2, 4, 5, 7, 8...

这个序列看起来有点乱，没有简单的加减规律。论文研究的正是这种由“魔法步长”（特别是像黄金分割率 $\phi$ 或 $\sqrt{2}$ 这样的二次无理数）生成的数字序列。

2. 核心发现：给数字装上“自动导航”（同步自动机）

以前，数学家发现，如果你用一种特殊的“语言”（叫做Ostrowski 表示法，可以理解为一种基于黄金分割或 $\sqrt{2}$ 的“进制”）来写数字，那么这些看似混乱的贝蒂序列，其实背后藏着极其严格的机械规律。

论文的核心比喻：
想象你有一台自动售货机（这就是论文中的“有限自动机”）。

输入：你投入两个硬币，一个是“步数 $n$ "，一个是“目标数字 $y$ "。
内部逻辑：售货机用一种特殊的“魔法进制”读取这两个数字。
输出：售货机只会在一种情况下吐出货品（接受）：当且仅当 $y$ 正好是你走了 $n$ 步后到达的那个位置（即 $y = \lfloor n\alpha + \beta \rfloor$ ）。

论文的伟大之处在于：
作者证明了，只要你的“魔法步长” $\alpha$ 和“起始偏移” $\beta$ 属于同一个数学家族（同一个二次域，比如都跟 $\sqrt{2}$ 有关），那么这台自动售货机是真实存在的，而且是可以被制造出来的。

这意味着，原本看起来不可预测的数字序列，实际上是可以被一台简单的机器完美预测和验证的。

3. 为什么这很重要？（Walnut 软件与“数学侦探”）

有了这个“自动售货机”（数学上叫同步自动机），作者们利用一个名为 Walnut 的免费软件，把数学问题变成了逻辑判断题。

以前的困境：如果你想问“这个序列里的数字能不能凑成所有的整数？”或者“有没有三个数字能组成等差数列？”，以前可能需要数学家苦思冥想好几年，甚至可能永远找不到答案。
现在的突破：因为序列被“同步”了，你可以直接把这些复杂的问题写成一段“代码”（一阶逻辑公式），扔给 Walnut 软件。
结果：软件会在几秒钟内告诉你：“是” 或 “否”，并且能给出证明。

比喻：以前你要判断一个迷宫有没有出口，得亲自走一遍；现在，因为有了“自动导航图”，你只需要问导航仪：“有没有出口？”，它立刻就能告诉你答案。

4. 具体解决了哪些问题？（应用实例）

论文用这个方法解决了很多困扰数学界很久的问题：

加法基础问题：
- 问题：这个序列里的数字，能不能通过“自己加自己”（比如 3 个、4 个相加），拼出所有的整数？
- 结果：对于这类序列，答案是肯定的，而且我们可以算出最少需要加几个数。
解决“雷布尔猜想”（Reble's Conjectures）：
- 有人猜想某些特定的数字模式在斐波那契数列（一种著名的自然规律序列）中是否会出现。作者用软件直接验证了这些猜想是对的。
格雷厄姆问题（Graham's Question）：
- 这是一个关于“覆盖”的问题：能不能用几组不同的“魔法步长”，把数轴上的所有整数都恰好覆盖一次，不重不漏？
- 结果：作者证明了，如果这些步长属于同一个数学家族，这个问题是可以判定的（即有办法算出答案）。
破解 OEIS 数列之谜：
- 在线整数数列百科全书（OEIS）里有很多数列，只有前几项，没人知道背后的规律。作者利用这个方法，不仅找到了规律，还证明了某些数列其实是同一个东西的不同写法。

5. 总结：这篇论文在说什么？

一句话总结：
这篇论文发现，对于一类特殊的“魔法数字序列”，我们可以制造出一台简单的机器来完美描述它们。有了这台机器，我们就能用计算机瞬间解决过去需要人类数学家花费数年甚至几代人都无法解决的复杂数学难题。

给普通人的启示：
这就像是我们发现，虽然宇宙中的星星排列看起来杂乱无章，但只要找到正确的“坐标系”（Ostrowski 表示法），它们其实遵循着极其简单的机械规则。一旦掌握了这个规则，我们就能预测未来，解开谜题，甚至把复杂的数学问题变成简单的“是”或“否”的判断题。

这篇论文不仅展示了数学的优美（混乱中藏着秩序），也展示了计算机辅助证明的强大力量（让机器帮我们思考）。

这是一份关于论文《Beatty Sequences for a Quadratic Irrational: Decidability and Applications》（二次无理数的 Beatty 序列：可判定性与应用）的详细技术总结。

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

Beatty 序列定义为序列 $(\lfloor n\alpha \rfloor)_{n \ge 1}$ ，其中 $\alpha$ 是无理数。其推广形式为非齐次 Beatty 序列 $(\lfloor n\alpha + \beta \rfloor)_{n \ge 1}$ 。这类序列在数论、组合数学和动力系统（如 Sturmian 序列）中具有重要地位。

核心问题：
对于二次无理数 $\alpha$ 和 $\beta$ （即属于同一个二次域 $\mathbb{Q}(\gamma)$ 的实数），如何判定关于这些序列的一阶逻辑理论（First-order logical theory）是否可判定？具体来说，是否存在一种算法，能够判定涉及这些序列的加法关系、覆盖性质、加法基性质等命题的真伪？

虽然针对特定情况（如黄金分割比 $\phi$ ）已有部分结果，但缺乏一个统一、简单且可自动化的框架来处理所有二次无理数的非齐次 Beatty 序列。

2. 方法论 (Methodology)

作者提出了一种基于自动机理论和Ostrowski 进位制的方法，并利用开源软件 Walnut 进行实现。

2.1 核心概念

Ostrowski 进位制：基于无理数 $\alpha$ 的连分数展开，将自然数唯一表示为 $\sum e_i q_i$ 的形式（其中 $q_i$ 是收敛项）。对于二次无理数，这种进位制具有周期性。
同步序列 (Synchronized Sequences)：如果一个序列 $(s_n)$ 存在一个有限自动机，能够并行读取 $n$ 和 $y$ 的 Ostrowski 表示，并当且仅当 $y = s_n$ 时接受，则称该序列是同步的。
Walnut 定理证明器：一个能够处理自动序列和同步序列的一阶逻辑判定工具。如果序列是同步的，则关于该序列的加法、减法及常数乘法的一阶逻辑理论是可判定的。

2.2 技术路线

建立同步性：证明对于二次无理数 $\gamma$ ，若 $\alpha, \beta \in \mathbb{Q}(\gamma)$ ，则映射 $n \mapsto \lfloor n\alpha + \beta \rfloor$ 是 $\gamma$ -Ostrowski 同步的。
构造自动机：利用连分数的矩阵性质（Hurwitz 方法）和 Ostrowski 表示的移位性质，构造接受 $n$ 和 $\lfloor n\alpha + \beta \rfloor$ 的有限自动机。
逻辑判定：一旦证明了同步性，根据已知理论（Theorem 2），任何涉及这些序列的一阶逻辑公式（包含加法）都可以转化为自动机操作，从而判定其真假。

3. 主要贡献与结果 (Key Contributions & Results)

3.1 理论突破

定理 9 (Theorem 9)：证明了如果 $0 < \gamma < 1$ 是二次无理数且其倒数具有纯周期连分数，且 $\alpha, \beta \in \mathbb{Q}(\gamma)$ ，则非齐次 Beatty 序列 $(\lfloor n\alpha + \beta \rfloor)_{n \ge 1}$ 是 $\gamma$ -Ostrowski 同步的。
定理 28 (Theorem 28)：证明了该命题的逆命题。如果 Beatty 序列是同步的，则 $\alpha$ 和 $\beta$ 必须属于 $\mathbb{Q}(\gamma)$ 。这给出了一个完整的刻画。
可判定性推论 (Corollary 11)：基于上述同步性，证明了自然数集 $\mathbb{N}$ 连同加法运算以及函数 $n \mapsto \lfloor n\alpha + \beta \rfloor$ 的一阶逻辑理论是可判定的。

3.2 具体应用与问题解决

作者利用 Walnut 软件解决了多个长期存在的开放问题和猜想：

加法基 (Additive Basis)：
- 定理 12：证明了对于二次无理数，集合 $\{\lfloor n\alpha + \beta \rfloor\}$ 是否构成 $r$ 阶加法基（或渐近加法基）是可判定的。
- 给出了计算最小阶数 $h$ 的算法。
Reble 的猜想 (Reble's Conjectures)：
- 解决了关于 Fibonacci 词（Sturmian 词）中单色算术级数存在的三个猜想（涉及 OEIS 序列 A189377, A189378, A189379）。通过构造自动机，在不到一秒钟内验证了这些猜想。
Graham 的问题：
- 解决了关于“最终覆盖族”（Eventual Covering Family）的问题：判定一组二次无理数对 $(\alpha_i, \beta_i)$ 是否能覆盖所有足够大的整数且不重叠。
Hildebrand 等人的序列：
- 给出了序列 $\tilde{c}(n)$ （Hildebrand et al. 研究的序列）的显式自动机描述，并证明了 $0 \le c(n) - \tilde{c}(n) \le 2$ 。
Kimberling 的 Swappage 问题：
- 通过自动机验证了 Kimberling 关于 Wythoff 序列变体（如 A141104）的猜想，并给出了显式公式。
$\sqrt{2}$ 相关序列：
- 为 OEIS 中七个与 $\sqrt{2}$ 相关的序列（如 A097508, A001951 等）构建了 Ostrowski 自动机，并验证了多个关于它们之间关系的猜想（如 Dekking 猜想）。
小数部分比较：
- 提出了一种处理 $\{ \alpha x + \beta \} < \{ \alpha' y + \beta' \}$ 这类涉及小数部分比较的方法，将其转化为取整函数的比较，从而在 Walnut 中实现。

4. 意义与影响 (Significance)

统一框架：该论文建立了一个统一的框架，将二次无理数的 Beatty 序列纳入自动机理论的可判定范畴。这比之前的量化消除（Quantifier Elimination）方法更简单、更通用。
自动化证明：展示了如何利用计算机辅助证明工具（Walnut）将复杂的数论问题转化为自动机构造问题。许多原本需要复杂手工证明的定理，现在可以通过几行代码在秒级时间内完成验证。
解决开放问题：直接解决了 Don Reble、Graham、Kimberling 等多位数学家提出的长期未决问题，并澄清了 OEIS 中多个序列的性质。
逆命题刻画：不仅证明了充分性，还证明了必要性（定理 28），明确了同步性与二次无理数域之间的等价关系。
工具推广：进一步推广了 Walnut 软件在数论和组合数学中的应用，特别是处理非标准进位制（Ostrowski 进位制）和二次无理数序列的能力。

总结

这篇论文通过引入Ostrowski 同步序列的概念，成功证明了二次无理数非齐次 Beatty 序列的一阶逻辑理论是可判定的。作者不仅提供了理论证明，还通过 Walnut 软件实现了具体的决策过程，解决了一系列关于加法基、序列覆盖、Sturmian 词性质以及 OEIS 序列猜想的开放问题。这项工作极大地推进了自动序列理论在数论中的应用，并展示了计算数学在解决经典数论问题中的强大能力。