The Tribonacci constant and finite automata

基本信息

• 论文ID: 2510.10834
• 标题: The Tribonacci constant and finite automata
• 作者: Jeffrey Shallit (University of Waterloo)
• 分类: cs.FL cs.DM math.NT
• 发表时间: October 21, 2025 (arXiv预印本)
• 论文链接: https://arxiv.org/abs/2510.10834

摘要

本文证明了不存在能够并行接受n和x的Tribonacci表示的自动机，其中ψ = 1.839···是Tribonacci常数，x = ⌊nψ⌋。类似地，不存在能够生成斜率为ψ-1的Sturmian特征字的Tribonacci自动机。

研究背景与动机

问题背景

1. Fibonacci情形的成功案例：对于黄金比例φ = (1+√5)/2，序列(⌊φn⌋)_{n≥0}是Fibonacci同步的，即存在有限自动机能够并行接受n和x的Zeckendorf表示，当且仅当x = ⌊φn⌋。
2. 自然的推广问题：是否对于Fibonacci数的推广（如Tribonacci数）也存在类似的性质？
3. 数论与自动机理论的交叉：这个问题涉及数论中的无理数性质与理论计算机科学中的有限自动机理论的深层联系。

研究动机

• 探索从二阶递推（Fibonacci）到三阶递推（Tribonacci）的推广是否保持自动机的可识别性
• 理解高阶递推序列与有限自动机之间的根本差异
• 为相关的逻辑理论和可判定性问题提供理论基础

核心贡献

1. 主要否定性结果：证明了序列(⌊ψn⌋)_{n≥0}不是Tribonacci同步的，其中ψ是Tribonacci常数
2. Sturmian序列的不可自动性：证明了相应的Sturmian特征序列不是Tribonacci自动的
3. 逻辑理论的影响：证明了映射n → ⌊ψn⌋不能在一阶理论⟨N,+,V'(n)⟩中表达
4. 深层数学洞察：揭示了二阶与三阶情形的根本差异在于周期性的缺失

方法详解

任务定义

研究两类自动机问题：

1. 同步自动机：接受函数f: N → N，并行输入n和x（Tribonacci表示），当且仅当x = f(n)时接受
2. 输出自动机（DFAO）：计算序列(a_n)_{n≥0}，输入n的Tribonacci表示，输出a_n

核心数学构造

Tribonacci数的性质

• 递推关系：T_i = T_ + T_ + T_，初值T_0 = 0, T_1 = 1, T_2 = 1
• 闭式表达：T_n = c_1ψ^n + c_2α^n + c_3β^n
• 其中ψ ≈ 1.839是X³ - X² - X - 1的实根，α,β是复共轭根

关键技术构造

定义：

• a(n) = ⌊ψn⌋
• b(n) = ⌊(ψ-1)(n+2)⌋ - ⌊(ψ-1)(n+1)⌋
• c(n) = ⌊ψ(n+1)⌋ - ⌊ψn⌋

证明策略

主要证明思路

1. 归约论证：证明如果a(n)是同步的，则b(n)是自动的
2. 状态区分：构造无穷多个可区分的自动机状态
3. Myhill-Nerode定理应用：利用状态区分证明不存在有限自动机

关键数学分析

利用分数部分的性质：

{ψT_n} = {2Re c_2(ψ-α)α^n}

其中：

• γ = arg c_2(ψ-α) = 2.536155···
• ζ = arg α = 4.10695···
• c(T_n)的值依赖于v(n) := γ + nζ mod 2π

实验设置

理论验证方法

本文主要是理论证明，使用的验证方法包括：

1. 数值计算：验证复数系数和参数的精确值
2. Kronecker定理应用：证明稠密性质
3. 线性无关性验证：确认ζ和2π在有理数上线性无关

关键参数计算

• |c_2(ψ-α)| = 0.608085···
• |α| = 0.73735···
• 验证了|2Re c_2(ψ-α)α^n| < 2-ψ对n ≥ 5成立

实验结果

主要理论结果

定理1的证明完成

证明了：

1. 序列(a(n))_{n≥0}不是Tribonacci同步的
2. 序列(b(n))_{n≥0}不是Tribonacci自动的

状态区分的构造性证明

• 对所有i < j，存在k使得c(T_{i+k}) ≠ c(T_{j+k})
• 利用Kronecker定理保证了无穷多个这样的k存在
• 成功构造了无穷多个可区分状态

逻辑理论结果

定理2

证明了映射n → ⌊ψn⌋不能在一阶理论⟨N,+,V'(n)⟩中表达，其中V'(n)是n的Tribonacci表示中最小的Tribonacci数。

相关工作

Fibonacci情形的已知结果

• Mousavi等人和Hieronymi独立证明了n → ⌊φn⌋在相应结构中可表达
• Khani和Zarei用不同方法也得到了类似结果
• 对于任意二次无理数都有类似性质

数值系统理论

• Zeckendorf表示理论
• 广义Fibonacci数列的表示理论
• Pisano数相关的数值系统

结论与讨论

主要结论

1. 根本差异：Fibonacci和Tribonacci情形存在本质区别
2. 周期性缺失：F_{n+1} - φF_n的符号是周期的，但T_{n+1} - ψT_n的符号不是周期的
3. 近似结果存在：虽然精确结果不可达，但存在误差在±1内的自动机近似

局限性

1. 否定性结果：主要是否定性的，没有提供替代的构造方法
2. 特定于Tribonacci：结果特定于三阶递推，更高阶情形需要单独分析
3. 近似方法的精度：近似自动机的误差界限可能不够精确

未来方向

1. 其他Pisano数：研究基于其他三次Pisano数的数值系统
2. 更高阶推广：考虑k阶递推序列的情形
3. 近似算法：改进近似自动机的精度和效率

深度评价

优点

1. 理论深度：揭示了递推阶数对自动机可识别性的根本影响
2. 证明技巧：巧妙地利用了复分析、数论和自动机理论的结合
3. 完整性：不仅证明了主要结果，还分析了逻辑理论的影响
4. 数学严谨性：证明过程严密，计算精确

不足

1. 构造性不足：主要是存在性的否定结果，缺乏正面的构造
2. 应用有限：结果主要是理论性的，实际应用价值有限
3. 推广性：方法对其他类似问题的推广性需要进一步验证

影响力

1. 理论贡献：为自动机理论和数论的交叉研究提供了重要洞察
2. 方法论价值：证明技巧对相关问题具有参考价值
3. 边界确定：明确了自动机方法的适用边界

适用场景

1. 理论研究：数论、自动机理论、形式语言理论
2. 算法设计：需要考虑自动机限制的数值算法设计
3. 复杂性理论：相关可判定性问题的研究

参考文献

论文引用了17篇重要文献，涵盖：

• 自动机理论经典教材（Hopcroft & Ullman）
• Fibonacci自动机的开创性工作（Bruyère等）
• 数论基础（Hardy & Wright）
• 相关的最新研究（Mousavi等，Hieronymi等）

总体评价：这是一篇高质量的理论论文，通过严密的数学证明揭示了Fibonacci和Tribonacci情形在自动机可识别性方面的根本差异。虽然主要是否定性结果，但为相关领域的理论发展提供了重要贡献，特别是在理解递推序列与有限自动机关系方面具有深远意义。