Tao–Vu · 加性组合学 · 第 12 章 和集中的长等差数列

12.4　完全序列与亚完全序列Complete and subcomplete sequences

本页为译文 + 讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为帮助理解的详解，逐步推演、举例、画图，不用比喻。

本节目标本节研究一个无穷正整数集合 \(A\) 的「不同元素子集和」能覆盖多大范围。如果它最终能盖住所有足够大的正整数，就叫 \(A\) 完全（complete）；如果只要求盖住某一条无穷等差数列，就叫 \(A\) 亚完全（subcomplete）。核心问题是：一个序列要多「稠密」，才能保证它是（亚）完全的？本节给出定义、关键引理与几条主要定理（证明放在下一节）。

一个无穷的正整数集合 \(A\subset\mathbb{Z}^{+}\) 称为完全的（complete），如果它的子集和 \(FS(A)\) 包含每一个足够大的正整数。这个概念与第 1 章所研究的基（base）的概念相似，但又有所不同：这里我们允许任意长度的求和，但要求被加的项两两不同。完全序列的概念由 Erdős 在六十年代初引入，此后被众多研究者广泛研究（综述见 [89, 第 6 节] 或 [274, 第 4.3 节]）。这一研究的核心，是寻找一个序列为完全的充分必要条件。

关键定义：子集和 \(FS(A)\)对集合（或后面提到的多重集）\(A=\{a_1,a_2,\dots\}\)，其有限子集和定义为 \[FS(A):=\Big\{\sum_{i\in I}a_i:\ I\subset\mathbb{Z}^{+}\ \text{有限}\Big\}.\] 也就是：从 \(A\) 里任取有限多个、互不相同的元素加起来，所有能得到的和构成的集合。
例：用 \(A=\{1,2,4,8,\dots\}\)（所有 2 的幂）说明「完全」 取每个元素至多一次，二进制告诉我们：每个正整数都能唯一写成若干不同 2 的幂之和。例如 \(13=8+4+1\)，\(22=16+4+2\)。
  1. \(1=1\)，\(2=2\)，\(3=1+2\)，\(4=4\)，\(5=1+4\)，\(6=2+4\)，\(7=1+2+4\)……
  2. 于是 \(FS(A)=\{1,2,3,4,5,\dots\}=\mathbb{Z}^{+}\)，盖住了所有正整数。
  3. 所以 \(A\) 是完全的（甚至从 1 开始就盖全，不只是「足够大」）。
注意「项两两不同」这一要求：在「基」的概念里允许 \(a+a\) 这样重复使用同一个数，而这里不允许。

直观上，一个集合越稠密，它就越可能是完全的。然而，仅有稠密性是不够的：全体偶数的密度为 \(1/2\)，但它们并不完全。更一般地，任何被包含在一条过零点的无穷等差数列中的集合都不会是完全的。为了处理这些情形，我们称一个集合 \(A\) 是亚完全的（subcomplete），如果它的子集和 \(FS(A)\) 包含一条无穷等差数列 \[a+\mathbb{N}\cdot r=\{a,\,a+r,\,a+2r,\,\dots\}.\]

为什么偶数虽稠密却不完全 设 \(A=\{2,4,6,8,\dots\}\)，密度高达 \(1/2\)。
  1. 把任意多个偶数加起来，结果仍然是偶数（偶 + 偶 = 偶）。
  2. 所以 \(FS(A)\subseteq\{2,4,6,\dots\}\)，它永远碰不到任何奇数。
  3. 奇数有无穷多个且任意大，所以「盖住所有足够大正整数」做不到——\(A\) 不完全。
  4. 但 \(FS(A)\) 显然包含整条无穷等差数列 \(\{2,4,6,\dots\}\)（取单个元素即可），所以 \(A\) 仍然是亚完全的。
这正说明了「完全」与「亚完全」的差别：亚完全只要盖住一条等差数列；完全则要在此之外，还能填补所有剩下的余数类。
完全：盖住所有足够大的整数 亚完全：只盖住一条等差数列（如偶数 a+r·N）
上排：完全序列的子集和最终占满整条数轴（每个大整数都被命中）。下排：亚完全序列只需命中一条等距排列的点（实心点），中间的空心点可以一直空着。

容易看出，这两个概念之间有如下联系：

引理 12.16 设 \(A\subset\mathbb{Z}^{+}\) 为无穷集。则 \(A\) 是完全的，当且仅当 \(A\) 是亚完全的，并且 \(FS(A)\) 与 \(\mathbb{Z}^{+}\) 中的每一条无穷等差数列都相交。

我们把该引理留作练习。「\(FS(A)\) 与 \(\mathbb{Z}^{+}\) 中每条无穷等差数列都相交」这一条件是一个局部条件，它只依赖于 \(A\) 所占据的剩余类（即模某数的余数）以及它们的重数；见练习。特别地，对于诸如 Waring 基 \(\mathbb{N}^{\wedge}k\)（即 \(k\) 次幂之集）或素数集 \(P\) 这类标准的基，这个条件通常很容易验证。因此我们将把注意力集中在亚完全这一性质上。

怎样读懂引理 12.16 的「两半」分工 要让 \(A\) 完全 = 盖住每个大整数，可以拆成两件互补的事：
  1. 「量」的保证（亚完全）：\(FS(A)\) 至少要包含一整条等差数列 \(a+r\mathbb{N}\)，这说明子集和能「走得很远很密」，不会稀稀拉拉。
  2. 「相位」的保证（局部相交条件）：还要保证对每个模 \(m\)、每个余数类，\(FS(A)\) 都能落进去——否则就会像偶数那样，永远漏掉某些余数（如奇数）。
  3. 两者合起来，才能既「走得远」又「不漏任何余数」，从而盖住所有大整数。第 2 条只看 \(A\) 元素模 \(m\) 的分布（局部、易查），所以真正困难的是第 1 条。

Cassels [46] 给出的一个简单例子表明：存在密度 \(|A\cap[1,n]|=\Theta(n^{1/2})\) 的集合 \(A\) 却不是亚完全的；见练习。引人注目的是，这个例子在常数倍意义下是最优的（sharp）：

定理 12.17 [350] 存在一个绝对常数 \(C>0\)，使得每一个满足 \[|A\cap[1,n]|\ \ge\ C\,n^{1/2}\] 的无穷集 \(A\subset\mathbb{Z}^{+}\) 都是亚完全的。特别地，若 \(FS(A)\) 还与 \(\mathbb{Z}^{+}\) 中每条无穷等差数列都相交，则 \(A\) 是完全的。

我们将在下一节证明这一结果；主要工具是推论 12.14。该结果的后半部分由 Erdős [85] 于 1962 年猜测，前半部分由 Folkman [103] 于 1966 年猜测。在 [85] 中，后半部分是在更强的假设 \(|A\cap[1,n]|\ge C\,n^{(\sqrt5-1)/2}\) 下证明的；而在 [103] 中，前半部分是在假设 \(|A\cap[1,n]|\ge n^{1/2+\varepsilon}\)（对任意 \(\varepsilon>0\) 及充分大的 \(n\)）下证明的。后来 Hegyvári [181] 以及 Łuczak 与 Schoen [241] 利用 Sárközy 定理（见练习），把这一界降到了 \(C\,n^{1/2}\log^{1/2}n\)。

解读「\(n^{1/2}\) 门槛是最优的」 门槛 \(Cn^{1/2}\) 的两面要一起看：
  1. 下界（不能更小）：Cassels 造出密度只有 \(\Theta(n^{1/2})\) 却不亚完全的反例。所以指数 \(1/2\) 不能再降——比这更稀疏的集合可能失败。
  2. 上界（已经够用）：定理 12.17 说只要密度达到 \(Cn^{1/2}\)（同样的量级，只是常数 \(C\) 取得足够大），就一定亚完全。
  3. 两边的「指数」都是 \(1/2\)，仅差一个常数因子，所以称这个阈值在「常数倍意义下最优」。直觉：\([1,n]\) 里有约 \(\sqrt n\) 个元素时，它们的子集和数量级可达 \(2^{\sqrt n}\)，足以稠密地覆盖一条等差数列。
n |A∩[1,n]| 阈值 ~ C·n^{1/2} 这上方：保证亚完全（定理 12.17） 这下方：可能不亚完全（Cassels 反例）
横轴 \(n\)，纵轴是 \(A\) 在 \([1,n]\) 中的元素个数。曲线 \(C\,n^{1/2}\) 是分界：长在它上方的集合必亚完全，长在它下方的集合可能失败。

对于 \(\mathbb{Z}^{+}\) 中的无穷多重集（multiset）\(A=\{a_1,a_2,\dots\}\)，上述结果有一个类比版本——这里 \(a_1\le a_2\le\cdots\) 允许出现重复。我们仿照之前的方式定义有限和集 \[FS(A):=\Big\{\sum_{i\in I}a_i:\ I\subset\mathbb{Z}^{+}\ \text{有限}\Big\},\] 并如上定义完全性与亚完全性的概念。在这种情形下，密度可以大到 \(|A\cap[1,n]|=\Theta_{\varepsilon}(n^{1-\varepsilon})\)（对任意给定的 \(\varepsilon>0\)，当然这里要计入重数）却仍然不亚完全（见练习）。同样地，这个例子本质上也是最优的。

集合 vs 多重集：门槛为什么从 \(n^{1/2}\) 跳到 \(n\)
  1. 普通集合：元素两两不同，\([1,n]\) 中最多 \(n\) 个元素，所以 \(n^{1/2}\) 已经是「相当稀疏」的一档。
  2. 多重集：同一个数可以反复出现。例如把 \(1\) 放进 \(A\) 一万次，子集和只能在 \(\{1,2,\dots,10000\}\) 里打转，重数虽高却帮助甚微——重复元素不会带来新的「步长」。
  3. 所以即便密度（计入重数）高达 \(n^{1-\varepsilon}\)，多重集也可能不亚完全。要想保证亚完全，需要把门槛提高到线性的 \(Cn\)（见下面定理 12.18）。
定理 12.18 [350] 存在一个绝对常数 \(C>0\)，使得每一个满足 \[|A\cap[1,n]|\ \ge\ C\,n\] 的无穷多重集 \(A\subset\mathbb{Z}^{+}\) 都是亚完全的。特别地，若 \(FS(A)\) 还与 \(\mathbb{Z}^{+}\) 中每条无穷等差数列都相交，则 \(A\) 是完全的。

这一结果由 Folkman [103] 猜测，其证明与定理 12.17 非常相似，我们把它留作下一节（证明定理 12.17 之处）的练习。

作为本节的结尾，让我们讨论完全性的有限版本。我们称 \(\mathbb{Z}_p\)（\(p\) 为一个大素数）的一个子集 \(A\) 是完全的，如果 \(FS(A)=\mathbb{Z}_p\)。Olson [265] 回答了 Erdős 与 Heilbronn 的一个问题，证明了：若 \(|A|>2\sqrt p\)，则 \(A\) 是完全的。界 \(2\sqrt p\) 本质上是最优的。要看出这一点，取 \[A=\{-k,-(k-1),\dots,-1,0,1,\dots,(k-1),k\},\] 其中 \(k\) 是使得 \(\sum_{i=1}^{k} i

唯一的（反）例。

定义：小集合（small set）我们称一个由 \(0\) 与 \(p-1\) 之间的整数构成的集合 \(A\) 是小的（small），如果 \[\sum_{a\in A}\ \big\|a/p\big\|\ <\ 1,\] 其中 \(\|z\|\)（一如既往）表示 \(z\) 到与它最近的整数之间的距离。容易验证：一个小集合不是完全的。
读懂 \(\|a/p\|\) 与「小集合不完全」
  1. \(\|z\|\) 是 \(z\) 到最近整数的距离，取值在 \([0,1/2]\)。例如 \(\|0.2\|=0.2\)，\(\|0.9\|=0.1\)，\(\|3.5\|=0.5\)。
  2. 把 \(\mathbb{Z}_p\) 的元素 \(a\) 想成圆周上的角度 \(a/p\)（一圈对应 \(1\)）。\(\|a/p\|\) 衡量 \(a\)（或 \(-a=p-a\)）离 \(0\) 有多近。
  3. 「小集合」就是所有元素都挤在 \(0\) 附近（正、负方向都算），它们的「离 0 距离」加起来还不到 \(1\)。
  4. 这样的集合每个元素绝对值都很小（或接近 \(p\)，即很小的负数），任取子集求和也跑不远，无法绕满整个 \(\mathbb{Z}_p\)，故不完全。
0 (= p) 圆心 元素全挤在 0 附近 → 小集合
把 \(\mathbb{Z}_p\) 画成圆周（顶端为 \(0\)）。小集合的元素都聚集在 \(0\) 的左右两侧（红点），它们的角距之和不足一整圈的一小段，于是子集和走不远、盖不满整圈。
定理 12.19 设 \(A\) 是 \(\mathbb{Z}_p\) 的一个含有多于 \(2\sqrt p\) 个元素的子集。若 \(A\) 不完全，则存在 \(\mathbb{Z}_p\) 中一个非零元素 \(x\)，使得集合 \(x\cdot A\) 是小的。
定理 12.19 在说什么 它给出了「大却不完全」的集合的结构刻画：
  1. \(x\cdot A=\{x\cdot a\bmod p:\ a\in A\}\) 是把 \(A\) 在 \(\mathbb{Z}_p\) 上做一次「乘法旋转/拉伸」。乘以非零 \(x\) 是一个双射，不改变集合大小，也不改变完全与否（因为 \(FS(x\cdot A)=x\cdot FS(A)\)）。
  2. 定理说：如果 \(A\) 足够大（超过 \(2\sqrt p\)）却偏偏不完全，那它一定是被「伪装」过的小集合——只要乘上某个合适的 \(x\)，就能把它「转正」成一个挤在 \(0\) 附近的小集合。
  3. 换句话说，「大而不完全」的唯一原因就是「本质上是个小集合」。这与前面 \(2\sqrt p\) 几乎最优、且反例唯一的论断相呼应。

Szemerédi 与 Vu [349, 352] 证明了：通过从 \(A\) 中去掉一个小的子集，可以大幅削弱条件 \(|A|>2\sqrt p\)。

定理 12.20 设 \(A\) 是 \(\mathbb{Z}_p\) 的一个不完全的子集。则存在 \(A\) 的一个子集 \(A'\)，其元素个数至多为 \(p^{.49}\)，以及 \(\mathbb{Z}_p\) 中一个非零元素 \(x\)，使得 \(x\cdot(A\backslash A')\) 是小的。

定理 12.19 与 12.20 的递进关系
  1. 定理 12.19 要求 \(A\) 整个就能被「转正」成小集合，前提是 \(|A|>2\sqrt p\) 这样的较强条件。
  2. 定理 12.20 更宽松：不要求 \(A\) 大到 \(2\sqrt p\)，也不要求整个 \(A\) 都小。它说，只要 \(A\) 不完全，就能剔除掉极少数（至多 \(p^{0.49}\) 个）「捣乱」的元素，剩下的 \(A\backslash A'\) 在某个旋转 \(x\) 下是小集合。
  3. 由于 \(0.49<1/2\)，被剔除的部分 \(p^{0.49}\) 比 \(\sqrt p=p^{0.5}\) 还少，所以这是对 12.19 的实质性加强：结构刻画对几乎所有不完全集合都成立，而不只是很大的那些。

返回 全书目录