The Golden Sieve

本文重审了作者于 2002 年提出的“黄金筛”自指删除过程，建立了其与 Wythoff 对、Fokkink 和 Joshi 研究的“打嗝序列”及 Fraenkel 互补划分的联系，并引入了一种能生成打嗝序列且对算术级数作用由仿射变换控制的“提取筛”。

要点

这篇论文讲述了一个关于数字游戏的有趣故事，作者 Benoit Cloitre 发明并深入研究了两种特殊的“筛子”（Sieve），用来从一串数字中筛选出特定的规律。

想象一下，你面前有一排排整齐的数字，像是一列等待检票的火车。这篇论文就是关于如何设计一套自动检票规则，让某些数字留下（幸存者），某些数字被踢走（删除者），并发现这些留下的数字竟然隐藏着像黄金比例、斐波那契数列这样深奥的数学秘密。

为了让你轻松理解，我们把这篇论文拆解成几个生动的场景：

1. 核心概念：什么是“黄金筛子”？

想象你有一列无限长的火车，车厢编号是 1, 2, 3, 4, 5...（这就是自然数）。

“黄金筛子”的规则是这样的：

• 第 1 步： 你站在第 1 节车厢前，看它的编号是"1"。这个数字"1"告诉你：“去把第 1 节车厢里的乘客踢出去！”于是，1 号被踢走了。
• 第 2 步： 现在火车剩下了 2, 3, 4, 5...。你站在第 2 节车厢前（现在的第 2 节其实是原来的 3），看到它的编号是"3"。这个数字"3"告诉你：“去把第 3 节车厢里的乘客踢出去！”于是，3 号被踢走了。
• 第 3 步： 火车剩下了 2, 4, 5, 6...。你站在第 3 节车厢前（现在的第 3 节是原来的 5），看到编号是"5"。于是，5 号被踢走。

神奇之处：
这个过程会一直持续下去。虽然规则很简单（“看第 N 个数字是多少，就踢掉那个位置的数字”），但最后留下的数字（幸存者）和被踢掉的数字（删除者）竟然形成了完美的互补关系：它们把自然数分成了两半，互不重叠，合起来正好是所有整数。

更惊人的是，当起始数字是 1, 2, 3...时，留下的数字序列竟然和黄金分割率（$\phi \approx 1.618$）有关，就像著名的威索夫（Wythoff）游戏中的必胜策略一样。

2. 扩展玩法：从“自然数”到“等差数列”

作者不仅研究了从 1 开始的数列，还研究了从其他数字开始的数列，比如“所有偶数”（2, 4, 6...）或者“所有 3 的倍数加 1"（4, 7, 10...）。

这就好比把火车的座位间距拉大了。

• 发现： 无论你怎么调整起始数字和间距，这个“筛子”依然能工作，并且留下的数字依然遵循某种**“打嗝”（Hiccup）**规律。
• 什么是“打嗝”规律？
  想象留下的数字在排队，它们之间的间隔（步长）只有两种可能：要么走 1 步，要么走 2 步（或者在更复杂的规则下走 $a$ 步或 $2a$ 步）。
  走哪一步，取决于**“你自己是否曾经出现过”**。
  • 如果当前的步数编号是你以前出现过的数字，你就走大步（打个大嗝）。
  • 如果没出现过，你就走小步。
    这种“自己决定自己下一步怎么走”的机制，就是论文中提到的**自指（Self-referential）**特性。

3. 新角色登场：“提取筛子” (Extraction Sieve)

除了“黄金筛子”，作者还介绍了一种更粗暴的筛子，叫**“提取筛子”**（或者叫“银筛子”）。

• 黄金筛子是：看第 N 个位置，把那个位置的人踢走。
• 提取筛子是：直接把队伍最前面的人抓出来作为幸存者，然后按照规则把后面几个人踢走。

比喻：

• 黄金筛子像是在玩“点名游戏”：老师点名说“第 3 号同学出列”，然后那个同学被带走。
• 提取筛子像是玩“抓阄”：老师直接说“把第 1 个同学抓走，然后如果刚才抓的是奇数号，再抓走后面 2 个；如果是偶数号，再抓走后面 1 个”。

有趣的结果：
这种“提取筛子”能直接生成各种复杂的“打嗝”数列。比如，著名的Bosma-Dekking-Steiner 数列（OEIS A086377），以前人们不知道它是怎么来的，现在发现它其实就是用“提取筛子”从自然数里筛出来的。

4. 数学背后的“魔法”

这篇论文虽然用了很多数学公式，但核心思想可以用几个简单的比喻概括：

• 互补方程（Complementary Equation）： 就像拼图，留下的数字和踢走的数字正好拼成完整的自然数世界，没有缝隙也没有重叠。
• 斜率（Slope）： 留下的数字增长有多快？作者发现，这个增长速度由一个二次方程决定。就像黄金比例是 $x^2 - x - 1 = 0$ 的根一样，这些新数列的增长速度也是某个特定方程的根。
• 平方数的陷阱： 作者还尝试把筛子用在“平方数”（1, 4, 9, 16...）上。结果发现，这里的规律变得更加复杂，像是一个**“嵌套的俄罗斯套娃”**。留下的数字的规律，取决于它们自己的平方数是否出现过。这产生了一种非常奇特的增长模式：$n + \sqrt{n} - \sqrt[4]{n} + \dots$。

5. 总结：这有什么用？

这篇论文不仅仅是为了玩数字游戏，它揭示了：

1. 简单的规则能产生复杂的秩序： 一个看似随意的删除规则，最终会形成极其严谨的数学结构（如威索夫对、Beatty 序列）。
2. 统一性： 无论是从 1 开始，还是从 100 开始，无论是自然数还是平方数，这些“筛子”都在用同一种逻辑（自指、互补、打嗝）在运作。
3. 连接游戏与数论： 这些数列实际上对应着某些双人博弈游戏（如 Nim 游戏）的必胜策略。如果你知道这些数字规律，你就知道在游戏中如何必胜。

一句话总结：
作者 Benoit Cloitre 发明了一套“数字筛子”，通过“看位置踢人”或“抓头踢人”的简单规则，从混乱的数字流中提炼出了像黄金比例一样完美的数学秩序，并发现这些秩序背后隐藏着深刻的博弈论秘密和自指逻辑。这就像是在数字的海洋里，用一把简单的勺子，舀出了形状完美的珍珠。

技术摘要

这是一份关于 Benoit Cloitre 论文《The Golden Sieve》（黄金筛）的详细技术总结。该论文发表于 2026 年 3 月，旨在纪念 Samuel Beatty 提出其相关问题的百年诞辰。

1. 研究问题与背景

核心问题：
论文研究了一种名为“黄金筛”（Golden Sieve）的确定性删除过程。该过程作用于一个严格递增的正整数序列 $W_0$。在每一步 $n$，算法读取当前工作序列 $W_{n-1}$ 中第 $n$ 个元素的值 $h_n$，并将该值作为位置索引，删除 $W_{n-1}$ 中位于 $h_n$ 位置的元素。
这一过程将初始序列 $W_0$ 划分为两个互补的递增子序列：

• 幸存者序列 $(s_n)$：从未被删除的元素。
• 删除序列 $(d_n)$：被删除的元素。

研究动机：
当 $W_0$ 为自然数集 $\mathbb{N}$ 时，该过程已知会产生与 Wythoff 对（Wythoff pair）和 Beatty 划分相关的结果，且受黄金分割比 $\phi$ 控制。然而，对于更一般的算术级数 $W_0 = a\mathbb{N} + b$（其中 $a \ge 1, 0 \le b < a$），其结构性质、递归规律以及与组合数学中其他概念（如 Hiccup 序列、Fraenkel 互补方程）的联系尚不完全清楚。此外，作者还探讨了该过程在完全平方数序列上的变体，以及一种对偶的“提取筛”（Extraction Sieve）。

2. 方法论

论文采用了以下主要数学工具和方法：

• 归纳构造与指针 - 幸存者恒等式： 通过严格的归纳法证明，对于 $a \ge 2$ 的情况，删除过程具有“前缀稳定”特性，即第 $n$ 步的指针 $h_n$ 总是等于当前的第 $n$ 个幸存者 $s_n$。
• 归一化（Normalization）： 将算术级数 $a\mathbb{N} + b$ 映射回自然数 $\mathbb{N}$，定义归一化幸存者 $\sigma_n = (s_n - b)/a$ 和归一化删除值 $\delta_n = (d_n - b)/a$，从而简化分析。
• 互补方程与仿射变换： 利用 Fraenkel 和 Kimberling 的互补方程理论，建立幸存者与删除值之间的仿射关系 $\delta_n = a\sigma_n + n + (b-1)$。
• 自指涉递归（Self-referential Recurrences）： 分析序列的“间隙”（gaps），发现其仅取两个值，并受序列自身值集的成员资格测试控制，这符合 Fokkink 和 Joshi 定义的"Hiccup 序列”范式。
• 连分数与渐近分析： 通过求解特征二次方程，推导序列的渐近斜率（asymptotic slope）及其连分数表示。
• Kimberling 秩变换（Rank Transform）： 将筛法结果与 Kimberling 的秩变换理论联系起来，证明两者在特定条件下产生相同的互补对。

3. 主要贡献与结果

3.1 黄金筛在算术级数 $a\mathbb{N} + b$ 上的性质

• 指针 - 幸存者恒等式： 对于 $a \ge 2$，证明了 $h_n = s_n$。这意味着删除目标总是位于当前前缀之后，消除了 $a=1$ 时的退化情况。
• 秩恒等式（Rank Identity）： 建立了归一化删除值与幸存者之间的精确仿射关系：
  $$\delta_n = a\sigma_n + n + (b - 1)$$
  这一关系将筛法与 Fraenkel 的 $NIM(a, 1)$ 博弈的 P-位置（先手必败态）联系起来。
• 双间隙性质（Two-Gap Property）： 证明了归一化幸存者的间隙 $\sigma_n - \sigma_{n-1}$ 仅取 $\{1, 2\}$ 两个值。删除值的间隙则取 $\{a+1, 2a+1\}$。
• Hiccup 规则： 幸存者序列 $(s_n)$ 是一个 $(0, s_1, 2a, a)$-Hiccup 序列。即间隙大小取决于索引 $n$ 是否属于幸存者集合本身：
  $$s_n - s_{n-1} = \begin{cases} 2a & \text{if } n \in \{s_1, s_2, \dots\} \\ a & \text{otherwise} \end{cases}$$
  删除序列的间隙也由相同的二进制控制词 $H(n)$ 决定，但测试条件经过 $W_0$ 的过滤。
• 渐近斜率： 证明了归一化幸存者序列的渐近斜率 $\alpha(a) = \lim_{n\to\infty} \sigma_n/n$ 是二次方程 $a\alpha^2 - a\alpha - 1 = 0$ 的正根：
  $$\alpha(a) = \frac{a + \sqrt{a^2 + 4a}}{2a}$$
  当 $a=1$ 时，$\alpha(1) = \phi$（黄金分割比）；当 $a \ge 2$ 时，序列不再是 Beatty 序列。

3.2 与 Beatty 划分及博弈论的联系

• Wythoff 对的恢复： 当 $W_0 = \mathbb{N}$ ($a=1, b=0$) 时，该过程产生的序列（经平移后）即为经典的 Wythoff 对 $(\lfloor n\phi \rfloor, \lfloor n\phi^2 \rfloor)$。
• Fraenkel 博弈： 对于 $b=1$ 的情况，黄金筛产生的归一化序列恰好是 Fraenkel 推广的 $NIM(a, 1)$ 博弈的 P-位置。这为这些博弈位置提供了一个动态的构造解释。
• Kimberling 秩变换： 证明了对于 $b \ge 1$，黄金筛产生的互补对与 Kimberling 对块序列 $u_{a,b}$ 的秩变换结果完全一致。

3.3 变体：平方数筛（Square Sieve）

• 当 $W_0 = \{n^2\}$ 时，作者发现了一种新的自指涉现象。
• 幸存者的根索引 $\mu_n = \sqrt{s_n}$ 满足一个嵌套的 Hiccup 规则，其间隙取决于 $n$ 是否属于“平方阴影集” $M = \{\mu_m^2 : m \ge 2\}$。
• 推导出了 $\mu_n$ 的渐近展开式，涉及交替的根塔（alternating root tower）：
  $$\mu_n = n + n^{1/2} - n^{1/4} + n^{1/8} - \dots + O(\log \log n)$$

3.4 提取筛（Extraction Sieve）与 Hiccup 序列

• 作者引入了一种对偶的“提取筛”机制：每一步提取最小值作为幸存者，并根据成员资格测试删除固定数量的后续最小值。
• 参数变换定理： 证明了提取筛作用于算术级数 $a\mathbb{N} + b$ 时，产生的幸存者序列是一个 Hiccup 序列，其参数 $(j, x, y, z)$ 通过仿射变换映射为 $(j, a+b, ay, az)$。
• Beatty 表示： 对于 $|y-z|=1$ 的情况，给出了提取筛产生的 Hiccup 序列的显式 Beatty 公式（斜率和偏移量），涵盖了 Wythoff 序列、Bosma-Dekking-Steiner 序列（银筛）等著名序列。

4. 意义与影响

1. 统一框架： 该论文将黄金筛、Wythoff 博弈、Fraenkel 博弈、Hiccup 序列以及 Kimberling 秩变换统一在一个动态删除过程的框架下，揭示了它们之间深刻的内在联系。
2. 新序列的发现与分类： 为算术级数上的自指涉序列提供了系统的分类（基于参数 $a, b$），并确定了其间隙词的 combinatorial 性质（如是否为 Sturmian 词、k-automatic 等）。
3. 动态构造： 为 Fraenkel 博弈的 P-位置提供了直观的动态构造方法，而不仅仅是代数定义。
4. 开放问题： 论文指出了若干未解之谜，特别是对于 $a \ge 2$ 时间隙词 $H$ 的自动性（automaticity）和因子复杂度（factor complexity），建议使用 Walnut 等工具进行进一步研究。

5. 结论

Benoit Cloitre 的《The Golden Sieve》不仅推广了经典的黄金分割筛法，还通过引入归一化、秩恒等式和提取筛等工具，建立了一个连接数论、组合博弈论和形式语言理论的丰富理论体系。该工作不仅解释了已知序列（如 Wythoff 对）的生成机制，还揭示了算术级数和平方数序列上新的自指涉规律，为未来的研究提供了明确的方向和工具。