On a sequence of Kimberling and its relationship to the Tribonacci word

本文利用 Walnut 定理证明器验证了 Clark Kimberling 关于特定二进制序列的猜想，揭示了该序列与无限 Tribonacci 词的关联，并确定了其子词复杂度和临界指数。

要点

这篇论文就像是一场数学侦探小说，侦探们（三位数学家）接手了一个由“数学家克拉克·金伯林”留下的神秘谜题：一个由 0 和 1 组成的无限长字符串。

为了让你轻松理解，我们可以把这个过程想象成**“魔法积木”和“翻译游戏”**。

1. 神秘的“魔法积木”规则

故事的主角是一个叫 B 的无限长字符串（比如 0100101100...）。
金伯林先生发明了一套奇怪的“积木生成规则”：

• 如果你看到两个连在一起的 00，就把它们变成 0101。
• 如果你看到一个单独的 0，保持不变。
• 如果你看到一个 1，把它变成 10。

这就好比你在玩一个游戏：你手里有一堆积木，每次按照规则把特定的积木组合替换成新的组合。金伯林先生发现，无论怎么替换，这个序列的长度增长似乎遵循一个特定的数学公式（斐波那契数列的“表亲”——特里波那契数列）。但他只是猜测，没有证明。

侦探的任务：证明这个长度公式是真的，并且搞清楚这个字符串到底有什么性格（比如它有多复杂，里面有没有重复的长片段）。

2. 核心发现：它是“特里波那契”的变装舞会

论文中最精彩的部分是，作者发现这个神秘的字符串 B，其实是一个著名的数学明星——“特里波那契词”（Tribonacci word） 的“变装”。

• 什么是特里波那契词？ 想象它是一个由 0、1、2 三种颜色积木组成的无限序列，它非常规律，像一首完美的交响乐。
• 变装过程： 作者发现，只要把特里波那契词里的 0、1、2 按照特定的规则“翻译”成 0 和 1（比如把 0 翻译成 10，把 1 翻译成 0 等等），就能完美得到金伯林的那个字符串 B。

比喻： 就像你有一首用三种乐器（0, 1, 2）演奏的曲子。金伯林先生把这首曲子录下来，然后让一个翻译官把每种乐器声都替换成特定的鼓点（0 和 1）。结果发现，虽然听起来全是鼓点，但它的节奏灵魂完全来自那首三乐器曲子。

3. 使用“魔法计算器” (Walnut)

为了证明这些猜想，作者没有只用纸笔，而是使用了一个叫 Walnut 的“自动定理证明器”。

• 比喻： 想象 Walnut 是一个超级聪明的机器人法官。你只需要把数学问题写成它听得懂的“法律条文”（逻辑语言），它就能在几秒钟内检查成千上万种情况，告诉你：“这绝对是真理”或者“这里有个漏洞”。
• 在这个故事里，作者用 Walnut 证明了字符串 B 的平衡性（0 和 1 的数量分布非常均匀，不会一边倒），就像证明一个天平无论怎么放砝码，都不会倾斜超过 3 度。

4. 字符串的“性格测试”

作者还对这个字符串做了两个重要的“体检”：

• 复杂度测试（Factor Complexity）：

  • 问：在这个无限长的字符串里，长度为 $n$ 的不同片段有多少种？
  • 结果：正好是 $2n$ 种。
  • 比喻： 这就像是一个**“罗特词”（Rote word）**。它的复杂程度刚刚好，既不像完全随机的乱码（那样太复杂），也不像 00000... 那样太简单。它处于一种“完美的混沌”状态，就像一首既有规律又充满变化的爵士乐。

• 重复指数（Critical Exponent）：

  • 问：这个字符串里，最长的“重复片段”有多长？比如 010101 是重复了 3 次。
  • 结果：作者算出它的重复极限大约是 3.19。
  • 比喻： 这意味着，无论这个字符串多长，你永远不会看到某个片段连续重复超过 3.19 次。它就像是一个**“洁癖患者”**，绝不允许自己太单调地重复。这个 3.19 的数值，正是由那个“特里波那契常数”（约 1.839）决定的，就像 DNA 决定了生物的特征一样。

总结

这篇论文做了什么？

1. 证实猜想： 证明了金伯林先生关于字符串长度的猜测是对的。
2. 揭示身世： 发现这个字符串其实是著名的“特里波那契词”经过“翻译”后的样子。
3. 性格分析： 算出了它的复杂度和重复极限，发现它属于一种非常特殊的数学家族（罗特词）。
4. 展示工具： 展示了如何用计算机（Walnut）来像侦探一样，严谨地解决这些复杂的数学谜题。

一句话总结： 作者们用“机器人法官”（Walnut）破解了一个由“魔法积木”生成的字符串谜题，发现它其实是另一个著名数学序列的“变装版”，并彻底摸清了它的脾气秉性。

技术摘要

这是一份关于论文《On a sequence of Kimberling and its relationship to the Tribonacci word》（Kimberling 序列及其与 Tribonacci 词的关系）的详细技术总结。

1. 研究问题 (Problem)

本文主要研究由 Clark Kimberling 在 2017 年定义的无限二进制序列 $B$（OEIS 序列 A288462）。该序列通过特定的“膨胀规则”（inflation rules）生成，这些规则比标准的同态（morphism）更为复杂，因为它们在应用前需要对字符串进行特定的分块（factorization）。

Kimberling 提出了关于该序列及其相关序列（A288463, A288464）的几个猜想，包括：

1. 长度增长规律：第 $i$ 次迭代 $B_i$ 的长度 $|B_i|$ 满足特定的线性递推关系。
2. 索引位置：序列中第 $n$ 个 '1' 和第 $n$ 个 '0' 的位置与 Tribonacci 常数 $\psi$ 的线性关系。
3. 组合性质：该序列的因子复杂度（factor complexity）和临界指数（critical exponent）。

此外，该序列与著名的 Tribonacci 词（Tribonacci word）之间的具体数学联系尚不明确，需要进一步揭示。

2. 方法论 (Methodology)

作者采用了一种结合组合数学、自动机理论和形式化证明工具的混合方法：

• 膨胀规则的形式化分析：
  • 将序列 $B$ 的生成过程分解为对最大块（$00, 0, 1$）的替换。
  • 通过引入块计数变量（$N_1, N_{10}, N_{100}$），建立了它们之间的递推关系，证明了这些计数序列满足 Tribonacci 递推式，从而推导出总长度的递推公式。
• 与 Tribonacci 词的关联：
  • 利用**回文词（return words）**的概念，将序列 $B$ 映射到 Tribonacci 词 $TR$。
  • 证明了 $B$ 是 Tribonacci 词在特定同态 $f$ 下的像（即 $B = 0f(TR)$）。
• Walnut 定理证明器（Theorem Prover）：
  • 构建了一个确定性有限自动机输出（DFAO），用于在 Tribonacci 进制表示下计算 $B[n]$。
  • 利用 Walnut 工具将序列的性质（如平衡性、索引位置、因子存在性）转化为一阶逻辑语句，并由计算机自动验证其真伪。
• 组合与渐近分析：
  • 对于因子复杂度和临界指数，由于自动机计算量过大无法直接终止，作者转而使用已知的关于 Tribonacci 词的双特殊因子（bispecial factors）理论，结合同态映射的性质进行推导。

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

A. 证明 Kimberling 的猜想

1. 长度递推公式：
   证明了 $|B_i| = c_i$，其中 $c_0=2, c_1=4, c_2=6, c_3=10$，且对于 $i \ge 4$，满足 $c_i = 2c_{i-1} - c_{i-4}$。
2. 索引位置的渐近行为：
   • 设 $I_0(n)$ 为第 $n$ 个 '0' 的位置，$I_1(n)$ 为第 '1' 的位置。
   • 证明了 $I_0(n) \approx \psi n$ 和 $I_1(n) \approx \gamma n$，其中 $\psi \approx 1.839$ 是 Tribonacci 常数，$\gamma = (\psi^2+1)/2 \approx 2.191$。
   • 给出了精确的不等式界限：$\lfloor \psi n \rfloor - 2 \le I_0(n) \le \lfloor \psi n \rfloor + 2$ 等。

B. 揭示与 Tribonacci 词的关系

• 证明了 $B$ 可以表示为 $0f(TR)$，其中$TR$是 Tribonacci 词，$f$是一个简单的同态映射（$0 \to 10, 1 \to 0, 2 \to 1$）。
• 基于此关系，构建了一个基于 Tribonacci 进制的自动机来计算 $B$ 的任意项。

C. 序列的复杂性质

1. 平衡性（Balance）：
   利用 Walnut 证明序列 $B$ 是 3-平衡 的（即任意两个等长因子中 '1' 的数量差至多为 3），但不是 2-平衡的。
2. 因子复杂度（Factor Complexity）：
   证明了 $B$ 的因子复杂度为 $P(n) = 2n$（对于 $n \ge 1$）。这意味着 $B$ 属于 Rote 词 类。
3. 临界指数（Critical Exponent）：
   计算了 $B$ 的临界指数（即序列中出现的最大幂次）：
   $$ce(B) = 2 + \frac{1}{\psi - 1} \approx 3.19148788$$
   该值与 Tribonacci 词的临界指数相同。

4. 意义与影响 (Significance)

1. 解决开放问题：彻底解决了 Kimberling 提出的关于序列 A288462 及其相关序列的多个猜想，填补了该特定膨胀规则序列理论研究的空白。
2. 方法论示范：本文展示了如何结合自动机理论（构建 DFAO）和形式化验证工具（Walnut）来解决复杂的组合数学问题。即使对于非标准同态生成的序列，这种方法也具有很强的普适性。
3. 理论连接：建立了非标准膨胀序列与经典 Tribonacci 词之间的深刻联系，表明看似复杂的膨胀规则实际上可以通过标准的 Tribonacci 结构和同态映射来理解。
4. 计算复杂性：通过证明该序列具有 $2n$ 的因子复杂度，将其归类为 Rote 词，丰富了我们对二元序列复杂度的分类认知。

总结

这篇论文不仅证实了 Kimberling 的猜想，还通过严谨的数学推导和计算机辅助证明，揭示了该序列本质上是 Tribonacci 词的一个变体。其核心贡献在于展示了如何利用现代自动机工具处理复杂的字符串生成规则，并精确计算了该序列的关键组合参数（复杂度、平衡性、临界指数）。