Balanced Fibonacci word rectangles, and beyond

基本信息

• 论文ID: 2509.25994
• 标题: Balanced Fibonacci word rectangles, and beyond
• 作者: Jeffrey Shallit (University of Waterloo), Ingrid Vukusic (University of York)
• 分类: math.NT cs.DM cs.FL math.CO
• 发表时间: October 15, 2025 (ArXiv预印本)
• 论文链接: https://arxiv.org/abs/2509.25994

摘要

本文基于Anselmo等人的最新研究，考虑由Fibonacci词形成的$m \times n$矩形矩阵，证明了它们的平衡性质可以用有限自动机来解决。研究进一步将结果推广到对应于二次无理数的每个Sturmian特征词，并考查了Tribonacci词的类似问题。

研究背景与动机

问题定义

本文研究的核心问题是词矩形的平衡性：给定一个无穷序列$(a_i)_{i≥0}$，构造无穷矩阵$A = (a_{k,\ell})_{k,\ell≥0}$，其中$a_{k,\ell} = a_{k+\ell}$。对于$m \times n$子矩阵$A(i,m,n)$，其所有元素的和为： $T(i,m,n) := \sum_{k=0}^{m-1}\sum_{\ell=0}^{n-1} a_{i+k+\ell}$

平衡性问题是：对于哪些$(m,n)$对，所有的$T(i,m,n)$值最多只有两个不同的值？

研究动机

1. 理论重要性：Fibonacci词是组合数学中的经典对象，其平衡性质与数论、自动机理论密切相关
2. 现有局限：Anselmo等人证明了当$\max(m,n)$是Fibonacci数时矩形是平衡的，但完整的刻画仍然缺失
3. 方法创新：使用有限自动机来解决这类问题提供了新的计算工具

核心贡献

1. 完全刻画：给出了Fibonacci词矩形平衡性的完整自动机刻画（定理2和推论3）
2. 一般化结果：将结果推广到所有对应二次无理数的Sturmian词（定理2）
3. 算法实现：提供了基于Walnut软件的具体实现和验证
4. 密度结果：证明了平衡对$(m,n)$的密度性质（命题6）
5. Tribonacci扩展：研究了Tribonacci词的类似问题（定理10）

方法详解

任务定义

给定无穷序列$(a_i)_{i≥0}$，构造Hankel矩阵： $A(i,m,n) := \begin{pmatrix} a_i & a_{i+1} & \cdots & a_{i+n-1} \\ a_{i+1} & a_{i+2} & \cdots & a_{i+n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{i+m-1} & a_{i+m} & \cdots & a_{i+m+n-2} \end{pmatrix}$

目标：确定哪些$(m,n)$对使得所有$T(i,m,n)$值最多有两个不同值。

核心理论框架

Sturmian词的性质

对于Sturmian词，定义$\Delta(i,m,n) := T(i+1,m,n) - T(i,m,n)$，有： $\Delta(i,m,n) \in \{-1, 0, 1\}$

关键引理1：$(m,n)$平衡当且仅当序列$(\Delta(i,m,n))_{i≥0}$不包含形如$1,0,0,\ldots,0,1$或$-1,0,0,\ldots,0,-1$的块。

自动机方法

对于二次无理数$\alpha$，存在有限自动机$M$，输入为Ostrowski $\alpha$-进制表示的$n$和$x$，接受当且仅当$x = \lfloor n\alpha \rfloor$。

主要定理2：存在算法，给定二次无理数$\alpha \in (0,1)$，构造有限自动机，输入为Ostrowski $\alpha$-进制表示的$(m,n)$对，接受当且仅当$m \times n$块是平衡的。

技术创新点

1. 平衡判据的自动机实现：将引理1的条件转化为一阶逻辑公式，再转化为自动机
2. Zeckendorf表示处理：巧妙处理负数问题，使用$T(i+1,m,n) - T(i,m,n) + 1 \in \{0,1,2\}$
3. Walnut实现：提供完整的代码实现，生成15状态自动机

实验设置

工具和实现

• Walnut软件：用于自动机构造和验证的专用工具
• Zeckendorf表示：Fibonacci数的标准表示系统
• Tribonacci表示：用于Tribonacci词分析

验证方法

1. 自动机构造：通过Walnut生成bal自动机（15个状态）
2. 定理验证：验证Anselmo等人的结果作为特例
3. 密度分析：计算平衡对的分布性质

实验结果

Fibonacci词的主要结果

推论3：图1中的15状态自动机完全解决了Fibonacci词矩形的平衡性问题。

推论4：验证了Anselmo等人的定理：如果$\max(m,n)$是Fibonacci数，则$m \times n$矩阵是平衡的。

结构性质

命题5：对于$n ≥ 2$：

• $(i,j)$平衡当且仅当$(i',j)$平衡，其中$F_{n+1} < i,i' < F_{n+2}$且$j ≥ F_{n-1}$
• $(F_{n+1}+i,j)$平衡当且仅当$(F_{n+2}-i,j)$平衡

命题6（密度结果）：若$F_i < m ≤ F_{i+1}$，则对所有$n ≥ 1$存在$j$，$1 ≤ j ≤ F_{i+1}$使得$(m,n+j)$平衡。

多样性结果

定理8：对于$m = n = F_{3k}/2$，$T(i,m,n)$的不同值个数至少为$k+1$。

推论9：$T(i,F_{3n}/2,F_{3n}/2)$的不同值个数为$\Theta(n)$。

Tribonacci词结果

定理10：假设$m ≤ n$：

• 若$m = 1$，所有$m \times n$矩形都是2-平衡的
• 若$m = 2$，存在77状态自动机接受所有使$m \times n$矩形2-平衡的$n$
• 若$m ≥ 3$，不存在使$m \times n$矩形2-平衡的$n$

相关工作

1. Sturmian词理论：建立在Berstel、Brown等人的经典工作基础上
2. 平衡性研究：扩展了Vuillon等人关于词平衡性的研究
3. 自动机方法：利用Bruyère等人关于p-可识别集合的理论
4. Fibonacci词性质：基于大量关于Fibonacci词的已有研究

结论与讨论

主要结论

1. 完全解决了Fibonacci词矩形的平衡性问题，提供了15状态自动机刻画
2. 方法可推广到所有二次无理数对应的Sturmian词
3. Tribonacci词的情况更复杂，需要77状态自动机处理$m=2$的情况

局限性

1. 方法仅适用于二次无理数对应的Sturmian词
2. Tribonacci词的完整刻画仍然复杂
3. 高阶情况（如Tribonacci的$m≥3$）可能无解

未来方向

1. 推广到更一般的morphic词
2. 研究高维情况
3. 优化自动机状态数

深度评价

优点

1. 理论完备性：提供了Fibonacci词平衡性的完整解决方案
2. 方法创新性：巧妙结合自动机理论和组合数学
3. 实用性强：提供了具体的算法实现和验证工具
4. 结果深刻：揭示了平衡性与数论性质的深层联系

不足

1. 复杂性：自动机方法虽然完整但可能不够直观
2. 推广限制：仅适用于特定类型的无理数
3. 计算复杂度：未详细分析自动机的时间复杂度

影响力

1. 理论贡献：为组合数学和自动机理论的交叉研究提供新思路
2. 实用价值：Walnut实现使得结果可验证和可扩展
3. 方法论意义：展示了如何用自动机解决复杂的组合问题

适用场景

1. 组合数学中的平衡性研究
2. 自动机理论的应用
3. 数论中的无理数性质研究
4. 算法设计中的决策问题

参考文献

论文引用了19篇重要文献，主要包括：

• Allouche & Shallit关于自动序列的经典著作
• Berstel关于Fibonacci词和Sturmian词的基础工作
• Anselmo等人的最新相关研究
• 自动机理论和数论的相关文献

这篇论文在理论深度和实用性之间找到了很好的平衡，不仅解决了一个具体的组合问题，还展示了自动机方法在处理此类问题中的强大威力。其完整的实现和验证使得结果具有很高的可信度和实用价值。