The greedy 3-sumfree sequence $S_{1,g,g+1}$

技术摘要：贪婪 3-sumfree 序列 $S_{1,g,g+1}$

问题陈述
本文旨在对贪婪 3-sumfree 序列 $S_{x,y,z}$ 进行特征化描述。该序列定义为一个由正整数组成的递增序列，起始项为 $x, y, z$，其中每一个后续项都是大于前一项的最小整数，且该整数不能表示为三个不同早期项之和。具体而言，作者研究了对于每个整数 $g \ge 2$ 的序列 $S_{1,g,g+1}$。虽然 Bosma 等人 [1] 此前利用自动定理证明器 Walnut 建立了针对特定较小情况（$g=2, 3, 4$）的显式描述，并猜想了一个适用于所有 $g \ge 2$ 的统一公式，但一个通用的证明仍然悬而未决。

方法论
作者采用了直接的区间和集（interval-sumset）论证方法，而非依赖自动定理证明。其方法论流程如下：

1. 候选集合的定义 ($A_g$)： 本文基于模运算定义了一个特定的集合 $A_g$。令 $m = 10g + 3$，$e = 2g + 1$，$f = 6g + 1$。集合 $A_g$ 由初始项 $\{1, e, f\}$ 以及一系列周期性区间 $I_k$ 和 $J_k$（其中 $k \ge 0$）的并集组成，定义为：

   • $I_k = km + [g, 2g]$
   • $J_k = km + [6g + 2, 7g + 1]$
     集合 $A_g$ 被构建为这些不相交组件的并集。

2. 简化为两个命题： 证明 $S_{1,g,g+1} = A_g$ 的过程被简化为验证关于整数“强制性”（若一个整数可以表示为集合中三个不同元素的和，则称该整数是强制的）的两个性质：

   • 命题 2： 每个不在 $A_g$ 中的整数 $n > g + 1$ 都是强制的（即可以写成 $A_g$ 中三个不同元素的和）。
   • 命题 3： $A_g$ 中的任何元素都不是强制的（即 $A_g$ 中的任何元素都不能写成 $A_g$ 中三个不同元素的和）。

3. 区间算术： 证明的核心在于计算定义的区间的和集。通过使用区间和集的初等恒等式（例如 $b_3[u, v] = [3u+3, 3v-3]$），作者证明了 $A_g$ 中的间隙恰好被 $A_g$ 中三个不同元素的和所覆盖，而来自 $A_g$ 的三个元素的和总是落在 $A_g$ 的补集内（具体为一个周期性的补集模式 $C$）。

4. 归纳验证： 作者使用对 $n$ 的数学归纳法来证明贪婪规则恰好采纳了 $A_g$ 中的元素。如果 $n \notin A_g$，则它被小于 $n$ 的元素强制（根据归纳假设，这些元素都在序列中），因此被排除；如果 $n \in A_g$，则它不被小于 $n$ 的元素强制，因此被采纳。

关键结果
本文确立了 定理 1，它为所有 $g \ge 2$ 的序列 $S_{1,g,g+1}$ 提供了精确的特征描述：
整数 $z$ 属于 $S_{1,g,g+1}$ 当且仅当：
$$z \in \{1, 2g + 1, 6g + 1\} \quad \text{或} \quad z \pmod{10g + 3} \in [g, 2g] \cup [6g + 2, 7g + 1].$$

论文进一步详细阐述了该序列的结构：

• 初始项： 序列开始于 $1, g, g+1, \dots, 2g, 2g+1, 6g+1$。
• 最终周期性： 在前 $g+4$ 项之后，序列在模 $m = 10g + 3$ 下具有周期性。
• 周期结构： 重复块的长度为 $2g + 1$，由以下剩余类组成：
  $$6g + 2, 6g + 3, \dots, 7g + 1, g, g + 1, \dots, 2g.$$

意义与主张
本文声称提供了一个对 Bosma, Bruin, Fokkink, Grube, Reuijl, 和 Tromp [1] 所提出的猜想的直接证明。虽然该猜想此前已通过机械方式在 $2 \le g \le 10$ 范围内得到验证，但本研究通过解析手段将结果扩展到了所有整数 $g \ge 2$。作者明确指出，其方法是通过区间和集论证实现的“直接证明”，这与先前工作中使用的计算方法形成了对比。此外，本文还提供了最终周期性的完整显式描述，包括前周期（preperiod）和重复块，从而完全解析了该序列的结构。