State Complexity of Shifts of the Fibonacci Word

这是一份关于论文《Fibonacci 字移位的状态复杂度》（State Complexity of Shifts of the Fibonacci Word）的详细技术总结。

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

核心问题：
本文研究的是Fibonacci 无限字（Fibonacci infinite word, $f$）的移位序列（shifted sequence）的状态复杂度。
给定一个自动序列（automatic sequence）$(a(i))_{i \ge 0}$，其移位序列定义为 $(a(i+c))_{i \ge 0}$，其中 $c$ 是一个固定的非负整数。研究的核心在于：生成这个移位序列所需的**确定性有限自动机输出机（DFAO）**的最小状态数是多少？

具体对象：
Fibonacci 字 $f = 01001010\dots$ 是组合数学中最著名的对象之一。它可以通过多种方式定义，包括：

• 作为替换系统 $0 \to 01, 1 \to 0$ 的不动点。
• 作为 Zeckendorf 表示（基于斐波那契数的进制系统）中 $i$ 的最后一位数字。
• 作为斜率为 $2-\phi$（$\phi$ 为黄金分割比）的 Sturmian 特征字。

现有挑战：

• 对于一般的 $k$-自动序列，在 $lsd-first$（最低有效位优先）输入下，移位$c$的状态复杂度通常为$O(m \log c)$（$m$ 为原序列状态数）。
• 然而，Zeckendorf 表示系统不支持像普通基数系统那样简单的“逐位加法”转换（没有单遍扫描的确定性转换器能完成 Zeckendorf 加法），这使得直接应用标准技术变得困难。
• 在 $msd-first$（最高有效位优先）模式下，移位操作通常会导致状态复杂度显著增加（例如 Thue-Morse 序列的移位复杂度为 $O(c)$）。
• 本文目标：确定 Fibonacci 字在 $lsd-first$和$msd-first$两种输入模式下，其移位序列$(f(i+c))_{i \ge 0}$ 的状态复杂度，并证明其是否保持在对数级别。

2. 方法论 (Methodology)

本文采用了状态复杂度技术、丢番图逼近（Diophantine approximation）以及逻辑自动定理证明相结合的方法。

A. 数学基础与区间划分

• Zeckendorf 表示与负数扩展：作者不仅使用了标准的 Zeckendorf 表示，还引入了一种处理负整数的特殊表示法（基于 Rockett 和 Szűsz 的推广），这对于分析移位至关重要。
• 分数部分与区间划分：
  • 利用 Fibonacci 字的性质：$f(i)=1 \iff \{i\phi\} \in (-\phi, -2\phi) \pmod 1$。
  • 移位后的性质：$f(i+c)=1 \iff \{i\phi\} \in (-(c+1)\phi, -(c+2)\phi) \pmod 1$。
  • 关键引理（Lemma 3 & 4）：作者构造了基于 Zeckendorf 表示前缀的区间划分（Partition）。
    • 在 $lsd-first$模式下，低阶位决定了${n\phi}$ 落在哪个小区间内。
    • 在 $msd-first$模式下，定义了与斐波那契表示一致的划分$P(r)$，确保读取一位数字后，区间能映射到划分中的另一个区间。

B. 自动机构造

• $lsd-first$ 构造：
  • 利用引理 3，证明读取 $k$ 位 Zeckendorf 数字后，$\{n\phi\}$ 所在的区间可以被确定。
  • 由于移位量 $c$ 决定了目标区间 $J_c = [-(c+2)\phi, -(c+1)\phi)$ 的端点，当读取的位数足以区分这些端点时，自动机即可进入“吸收状态”（Sink States）。
  • 状态数取决于 $c$ 在斐波那契进制下的长度，即 $O(\log c)$。
• $msd-first$ 构造：
  • 直接反转 $lsd-first$ 自动机通常会导致状态数指数级爆炸。
  • 作者通过构造基于划分 $P(-(c+1))$ 和 $P(-(c+2))$ 的合并划分，直接构建 $msd-first$ DFAO。
  • 利用引理 5 证明该划分与 $msd-first$表示一致，从而保证自动机的正确性。状态数同样由划分的端点数量决定，即$O(\log c)$。

C. 自动定理证明 (Automated Theorem Proving)

• 使用了工具 Walnut（基于逻辑的自动序列证明器）。
• 在证明引理 7 和引理 8（关于区间在添加/删除位后的变换性质）时，作者将复杂的区间包含关系转化为第一阶逻辑公式，并由 Walnut 进行验证，确保了证明的严谨性。

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

1. 状态复杂度的对数界

• **定理 1 ($lsd-first$)**：对于任意$c \ge 0$，生成移位序列$(f(i+c))_{i \ge 0}$的$lsd-first$ DFAO 的状态数为 $O(\log c)$。
• **定理 3 ($msd-first$)**：对于任意$c \ge 0$，生成移位序列$(f(i+c))_{i \ge 0}$的$msd-first$ DFAO 的状态数也为 $O(\log c)$。
• 意义：这是非常罕见的结果。通常 $msd-first$ 移位会导致线性甚至更高的复杂度（如 Thue-Morse 序列）。Fibonacci 字在两种输入模式下都表现出极低的复杂度，接近非周期序列的信息论下限。

2. 精确的状态数公式

• 定理 2：给出了 $lsd-first$ 最小 DFAO 的精确状态数公式：
  $$\text{States} = 2(|(c)_F| + 1) + 1 - g(c)$$
  其中 $|(c)_F|$ 是 $c$ 的 Zeckendorf 表示长度，$g(c)$ 是一个取决于 $f(c-1)$ 和 $f(c-2)$ 是否均为 0 的修正项。
• 该结果表明上界 $O(\log c)$ 是最优的，且状态数函数本身是 Fibonacci-regular（斐波那契正则）的。

3. 技术突破

• 克服了 Zeckendorf 系统中无法进行单遍加法转换的困难，通过几何（区间划分）和数论（丢番图逼近）的方法绕过了传统的转换器构造。
• 展示了如何利用 Walnut 工具处理复杂的自动序列性质证明，特别是涉及无理数旋转（irrational rotation）和区间映射的问题。

4. 意义与影响 (Significance)

1. 理论深度：本文揭示了 Fibonacci 字在自动序列理论中的特殊性质。尽管 Fibonacci 字是典型的非周期 Sturmian 字，但其移位操作并未像其他著名序列（如 Thue-Morse）那样导致状态复杂度的剧烈膨胀。这为理解自动序列的“刚性”和“灵活性”提供了新视角。
2. 算法效率：证明了在 Zeckendorf 表示下，Fibonacci 字的移位可以通过极小的自动机高效实现。这对于基于 Fibonacci 进制的计算模型和硬件设计具有潜在的应用价值。
3. 方法论示范：展示了将数论（斐波那契数性质、黄金分割比）、形式语言理论（自动机状态复杂度）和自动定理证明（Walnut）相结合的强大能力。这种混合方法为解决其他自动序列的复杂操作问题提供了范本。
4. 未来方向：作者指出，这些结果可以推广到二次无理数（quadratic irrationals）甚至更一般的无理数，以及 Tribonacci 字等其他序列，为后续研究指明了方向。

总结

这篇论文通过巧妙的数学构造和自动化工具，解决了 Fibonacci 字移位序列状态复杂度的核心问题，证明了其在 $lsd-first$和$msd-first$两种模式下均具有$O(\log c)$ 的极低状态复杂度。这一结果不仅优化了对 Fibonacci 字的理解，也展示了处理非标准进制系统下自动序列操作的强大新范式。