Almost Golomb Sequences

这是一份关于 Benoit Cloitre 论文《Almost Golomb Sequences》（近 Golomb 序列）的详细技术总结。

1. 问题背景与定义

背景：
Golomb 序列（$G(n)$）是整数序列中最著名的自指序列之一（OEIS A001462）。它是唯一的非递减正整数序列，满足整数 $n$ 在序列中恰好出现 $a(n)$ 次。其全局自指规则为：
$$a\left(\sum_{k=1}^n a(k)\right) = n$$
Golomb 序列具有平滑的幂律增长特性（$a(n) \sim C n^{\phi-1}$，其中 $\phi$ 为黄金分割比），且对于任何 $k \ge 2$ 都不是 $k$-正则的（$k$-regular）。

新问题：
本文引入了近 Golomb 序列（Almost Golomb Sequences），记为 $a_r(n)$。其核心思想是将 Golomb 序列定义中的“无限累积和”截断为固定大小 $r$ 的滑动窗口。
定义如下：对于 $r \ge 2$，$a_r(n)$ 是满足以下条件的最小非递减正整数序列（$a(k)=0$ 当 $k \le 0$）：
$$a_r\left( \sum_{j=0}^{r-1} a_r(n-j) \right) = n$$
即 $a_r(S_n) = n$，其中 $S_n = a_r(n) + a_r(n-1) + \dots + a_r(n-r+1)$。

核心差异：
这种从无限记忆到有限记忆窗口的截断，彻底改变了序列的性质：

• 增长模式： 从平滑的幂律增长转变为线性增长伴随离散振荡（$a(n) \asymp n$）。
• 正则性： 序列从非正则转变为$r$-正则（$r$-regular），甚至具有自动序列（automatic）结构。

---

2. 方法论

本文采用了一种混合研究方法，结合了构造性证明、自动机理论（Automata Theory）和计算机辅助证明（Computer-Assisted Proof）。

1. 通用正则性证明 (Universal $r$-regularity)：

   • 首先建立了序列的全局“运行结构”（Run Structure）：证明了序列值的增量 $d(n) = a(n+1) - a(n)$ 仅取 $\{0, 1\}$，且每个整数 $m$ 的首次出现位置由滑动和 $S_m$ 决定。
   • 利用 Allouche-Shallit 准则，证明了差值序列 $d(n)$ 是 $r$-自动的（$r$-automatic），从而推导出原序列 $a(n)$ 是 $r$-正则的。

2. 显式去嵌套（Explicit Denesting）：

   • 对于小参数 $r \in \{2, 3, 4, 5\}$，作者推导出了基于 $r$ 进制表示的“去嵌套公式”（Denesting Formulas）。
   • 形式通常为：$a(rn + i) = \sum c_k a(n+k) + \text{常数} + \varepsilon_i(n)$。
   • 其中 $\varepsilon_i(n)$ 是修正序列（Correction Sequences），它们是 $r$-自动的（由有限状态自动机生成），用于处理边界情况和非通用项。

3. 计算机辅助验证 (Walnut)：

   • 对于 $r=4$ 和 $r=5$ 的情况，由于手动推导极其复杂，作者使用了 Walnut 定理证明器。
   • 首先通过数学推导识别出递归模式，然后利用 Walnut 验证这些递归关系对所有 $n$ 成立，并验证修正序列的自动性。

4. 渐近分析与组合解释：

   • 利用自动机在几何级数上的周期性（Lemma 2.8），计算了 $a(n)/n$ 的极限点，证明了其不收敛。
   • 对于 $r=2$ 和 $r=3$，提供了组合解释（如布尔细胞自动机、回文替换规则）。

---

3. 主要贡献与结果

3.1 通用理论结果

• $r$-正则性定理 (Theorem 2.9)： 证明了对于任意 $r \ge 2$，近 Golomb 序列 $a_r(n)$ 都是 $r$-正则的。这是通过将差值序列的自动性归约到有限局部窗口数据来实现的。

3.2 具体案例的显式公式

• $r=2$ (Dyadic)：
  • 导出了闭式公式和 Mallows 类型的嵌套递归：$a(n+1) = 1 + a(n + 1 - a(a(n)+1) + a(a(n)-1))$。
  • 给出了去嵌套公式：$a(2n) = a(n) + a(n+1) - 1$ 等。
  • 组合解释： 序列的差值 $d(n)$ 由一个简单的布尔细胞自动机生成（偶数位为 1，奇数位为父节点值的逻辑与）。
• $r=3$ (Triadic)：
  • 引入了一个关键的修正序列 $\varepsilon(n)$（指示集合 $I$ 的特征函数），该序列是 3-自动的。
  • 给出了包含 $\varepsilon(n)$ 的去嵌套公式。
  • 组合解释： 差值序列的三元块具有回文性质，且序列表现出一种“延迟反馈”机制，导致振荡。
• $r=4, 5$：
  • 识别了多个修正序列（$r=4$ 有 4 个，$r=5$ 有 2 个 $\varepsilon, \eta$）。
  • 利用 Walnut 完成了这些序列的自动性认证和递归关系的证明。

3.3 非收敛性 (Non-convergence)

• 主要发现： 与 Golomb 序列不同，近 Golomb 序列的比值 $a(n)/n$ 不收敛。
• 振荡行为： 对于每个 $r$，比值在两个（或多个）明确的有理数极限点之间振荡。
  • $r=2$: 极限为 $3/4$ 和 $2/3$。
  • $r=3$: 极限为 $8/15$ 和 $5/8$。
  • $r=4, 5$: 也有类似的 distinct 极限点。
• 这证明了序列的增长虽然是线性的，但具有分形般的波动特性。

3.4 Golomb 元结构猜想 (Golomb Meta-structure Conjecture)

• 现象： 作者发现，近 Golomb 序列族中最大重数 $M(r) = \sup_n N_r(n)$（即某个整数在序列中出现的最大次数）的增长规律竟然由 Golomb 序列本身 控制。
• 猜想 (Conjecture 9.1)： 设 $j_k$ 为使 $M(r) \ge k$ 的最小 $r$ 值。则对于 $k \ge 4$：
  $$j_{k+1} - j_k = G(k)$$
  $$j_k = S(k-1) + 2$$
  其中 $G(k)$ 是 Golomb 序列，$S(k)$ 是其前缀和。
• 意义： 这意味着截断 Golomb 规则生成的序列族，其内部结构（最大重数）反过来“编码”了原始的 Golomb 序列。这是一个深刻的自指现象。
• 状态： 该猜想已通过数值计算验证至 $r=700$，并被简化为两个边界猜想（前缀猜想和支配引理）。

---

4. 意义与影响

1. 连接不同数学领域： 本文成功地将自指序列（Self-referential sequences）、自动序列理论（Automatic sequences）、正则序列（Regular sequences）以及组合数学（Cellular automata, Substitutions）联系起来。
2. 揭示有限记忆的影响： 展示了从无限记忆（Golomb）到有限记忆（近 Golomb）的相变。这种截断将序列从解析的幂律领域推向了离散的自动序列领域，产生了振荡而非平滑增长。
3. 方法论创新： 展示了如何使用“数学推导识别模式 + Walnut 自动验证”的混合方法来解决复杂的递归序列问题，为处理高阶 $r$ 的情况提供了范式。
4. 未解之谜： 提出了关于 $r \to \infty$ 时的相变行为、Cesàro 平均的收敛性以及 $r \ge 4$ 的组合解释等开放问题，特别是关于 Golomb 元结构的严格证明仍是未来的工作方向。

总结

Benoît Cloitre 的这篇论文不仅定义并深入分析了一类新的整数序列（近 Golomb 序列），还通过严谨的数学证明和计算实验，揭示了有限记忆自指系统丰富的结构特性。最引人注目的是发现了这些新序列与原始 Golomb 序列之间深刻的“元结构”联系，即被截断的规则重新出现在其生成的序列族的统计规律中。