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

12.5　定理 12.17 的证明Proof of Theorem 12.17

本页为译文 + 讲解合一：黑色正文为忠实翻译；彩色框（目标 / 定义 / 引理 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。原文 PDF 在证明 Theorem 12.17 的最后一句处被截断，本页末尾对剩余论证给出清晰标注的补全。

本节目标我们要证明定理 12.17：某类（计数函数大约为 \(n^{1/2}\) 量级的）正整数集合是次完备的（subcomplete），也就是说，它所有有限子集的和构成的集合 \(\mathrm{FS}(A)\) 包含一条无穷等差数列。直接处理"无穷"很难，本节的策略是：先把"次完备"这个无穷条件换成一个有限的、可操作的充分条件（"良好划分"），证明它确实够用（引理 12.21），再把目标集合按下标奇偶拆成两半，验证它满足这个有限条件。

把"次完备"化简成有限条件

为了证明定理 12.17，把（无穷的）次完备性条件归约为一个有限版本会很方便。我们称正整数多重集 \(A\) 的一个划分 \(A=A'\cup A''\) 为良好的（good），如果下面两条性质成立：

定义（良好划分）

于是 \(A'\) 享有次完备性的一个有限版本，而 \(A''\) 的增长比一个缺项（lacunary）序列还要慢。这两个条件合起来便可推出次完备性：

先把两条性质读懂

记号 \(\mathrm{FS}(S)\)（finite subset sums）表示：从 \(S\) 中任取有限个互不相同的元素相加，所能得到的全部数值组成的集合。例如 \(\mathrm{FS}(\{1,2,4\})=\{0,1,2,3,4,5,6,7\}\)（空集和记为 \(0\)）。

第一条说 \(A'\) 这一半"很富裕"：它的子集和里能找到一条想多长就有多长、间距固定为 \(d\) 的等差数列（例如 \(p,\,p+d,\,p+2d,\,\dots\)）。但"任意长"还不是"无穷长"，缺口要靠 \(A''\) 补。

第二条 (12.2) 说 \(A''\) 这一半"很稀疏、很缓慢"：把前 \(i-1\) 项加起来，再减去第 \(i\) 项，差会趋于 \(+\infty\)。直观上这要求前面所有项之和远远超过下一项 \(b_i\)——这样每加入一个新的 \(b_i\)，子集和就能"无缝衔接"地往前延伸，不会留下越来越大的空洞。

引理 12.21（[351, 241, 181]）任何容许一个良好划分的正整数序列 \(A\) 都是次完备的。
例：(12.2) 想表达什么 取 \(b_i=2^{i}\)（恰好是缺项序列的临界情形）。此时 \(\sum_{j=1}^{i-1}b_j=2^{i}-2\)，而 \(b_i=2^{i}\)，于是 \(\sum_{j不趋于 \(+\infty\)，(12.2) 失败。
改取增长更慢的 \(b_i=i^2\)：\(\sum_{j=1}^{i-1}j^2\approx \tfrac{i^3}{3}\) 远大于 \(b_i=i^2\)，于是差 \(\approx \tfrac{i^3}{3}-i^2\to+\infty\)，(12.2) 成立。可见 (12.2) 是在说"\(A''\) 增长得比指数（缺项）慢"。
良好划分 \(A=A'\cup A''\) A'（富裕的一半） FS(A') 含公差 d 的 任意长等差数列 · · · 公差 d · · · A''（稀疏的一半） 增长比缺项序列更慢 满足条件 (12.2) 间距缓慢拉开，但总和始终领先
策略图：A' 负责提供"想多长就多长"的固定公差等差数列；A'' 负责把这些有限段"接成无穷"。两者合作 ⇒ A 次完备。
证明（引理 12.21）. 我们先做一些归约。

首先注意：从 \(A''\) 中去掉有限个元素并不影响条件 (12.2)。特别地，我们可以去掉 \(A'\) 中那些只含有限个元素的剩余类 \(a+d\cdot\mathbb{Z}\pmod d\)（这样去掉的也只是有限个元素）。

设 \(A_d\subset\mathbb{Z}_d\) 为模 \(d\) 后与 \(A'\) 相交的那些剩余类构成的集合（由上面的归约，它们各自都含 \(A'\) 的无穷多个元素）。由 \(A_d\) 张成的群 \(\langle A_d\rangle\) 是 \(\mathbb{Z}_d\) 的子群，从而形如 \(\langle A_d\rangle=d'\cdot\mathbb{Z}_d\)，其中 \(d'\) 是 \(d\) 的某个因子。特别地，\(A'\) 的每个元素都是 \(d'\) 的倍数。注意到 \(\mathrm{FS}(A')\) 必定与 \(A_d\) 中的每个剩余类都相交。于是存在一个有限子集 \(B\subset A'\)，使得 \(\mathrm{FS}(B)\) 与 \(d'\cdot\mathbb{Z}_d\) 中的每个剩余类都相交。

令 \(A''':=A'\setminus B\)，于是 \(A'''\) 仍然服从 (12.2)。一个简单的贪心算法论证表明，子集和集合 \(\mathrm{FS}(A''')\) 是间隙有界的（syndetic，即相邻元素间隔有上界）；更确切地说，存在 \(L\ge 0\)，使得对任意正整数 \(n\)，都能找到 \(m\in\mathrm{FS}(A''')\) 满足 \(0\le n-m\le L\)。

由于 \(\mathrm{FS}(A''')\) 完全由 \(d'\) 的倍数组成，而 \(\mathrm{FS}(B)\) 与 \(d'\cdot\mathbb{Z}_d\) 中的每个剩余类都相交，我们得出：集合 \(\bigl(\mathrm{FS}(A''')+\mathrm{FS}(B)\bigr)\cap(d\cdot\mathbb{Z})\) 也是间隙有界的。又因为 \(\mathrm{FS}(A')\) 包含公差为 \(d\) 的任意长等差数列，故 \[\mathrm{FS}(A')\;+\;\Bigl[\bigl(\mathrm{FS}(A''')+\mathrm{FS}(B)\bigr)\cap(d\cdot\mathbb{Z})\Bigr]\] 包含一条公差为 \(d\) 的无穷等差数列。但这个集合包含于 \(\mathrm{FS}(A)\) 之中，所以 \(A\) 如所断言地是次完备的。♦

把引理证明拆成"动机清晰"的步骤
  1. 清掉无用碎屑。(12.2) 是关于"无穷尾巴"的条件，去掉有限个元素不改变极限，所以可以先把 \(A'\) 中只出现有限次的剩余类丢掉，保证留下的每个剩余类都"无穷多次出现"。
  2. 看清 \(A'\) 落在哪些剩余类里。把 \(A'\) 模 \(d\)，它落入的剩余类张成 \(\mathbb{Z}_d\) 的一个子群，必然长成 \(d'\cdot\mathbb{Z}_d\)（即所有 \(d'\) 的倍数那一类）。于是 \(A'\) 的元素都是 \(d'\) 的倍数——它的子集和只能落在 \(d'\) 的倍数上。
  3. 用有限个元素 \(B\) 覆盖所有需要的剩余类。因为 \(\mathrm{FS}(A')\) 能碰到 \(A_d\) 的每个剩余类，挑出有限个元素 \(B\)，让 \(\mathrm{FS}(B)\) 就足以代表 \(d'\cdot\mathbb{Z}_d\) 的每个剩余类（管"对齐到正确的余数"）。
  4. 剩下的 \(A'''\) 仍稀疏 ⇒ 其子集和"密不透风"。贪心地一个个把 \(A'''\) 的元素加进来：(12.2) 保证每一步迈出的"步长" \(b_i\) 都被"已有的总和"盖过，于是子集和 \(\mathrm{FS}(A''')\) 不留大空洞——间隙有上界 \(L\)（间隙有界 / syndetic）。
  5. 合并 ⇒ 无穷等差数列。"间隙有界的骨架"（\(A'''\) 与 \(B\) 提供，限制在 \(d\) 的倍数上）再加上"公差 \(d\) 的任意长直线段"（\(A'\) 提供），就能拼出一条永不中断、公差为 \(d\) 的无穷等差数列。它整体藏在 \(\mathrm{FS}(A)\) 里，故 \(A\) 次完备。
FS(A''')：间隙 ≤ L，密不透风 ≤L FS(A')：公差 d，任意长（有限段） d 两者相加（A' + 骨架）⇒ 公差 d 的无穷等差数列 ⊂ FS(A)
骨架（上，间隙不超过 \(L\)）保证"处处都有落点"；固定公差 \(d\) 的长线段（下）保证"沿同一公差延伸"。两者的和把有限段接力成无穷数列。

定理 12.17 的证明

我们现在可以证明定理 12.17 了。

定理 12.17 之证明. 把 \(A\) 写成 \(A=\{a_1公差为某个固定 \(d\) 的任意长等差数列。

对每个非负整数 \(j\)，令 \[A_j:=\{a_{2m}:2^{\,j}\le m<2^{\,j+1}\}.\] 于是这些 \(A_j\) 给出 \(A'\) 的一个划分。并且，假设 \(|A\cap[1,n]|\le Cn^{1/2}\) 蕴含：对所有〔原文 PDF 在此处被截断〕……

为什么按奇偶拆分恰好奏效 把递增序列 \(a_1奇偶分成两半：偶下标 \(a_2,a_4,a_6,\dots\) 归入 \(A'\)，奇下标 \(a_1,a_3,a_5,\dots\) 归入 \(A''\)。
  1. \(A''\) 自动满足 (12.2)。稀疏假设 \(|A\cap[1,n]|\le Cn^{1/2}\) 表示元素很"稀"：到 \(n\) 为止至多 \(Cn^{1/2}\) 个，反过来 \(a_i\gtrsim (i/C)^2\) 增长得像 \(i^2\)。于是 \(b_i=a_{2i-1}\) 大约是 \(i^2\) 量级，而前缀和 \(\sum_{j
  2. \(A'\) 仍保有一半元素，足够"富裕"。剩下要做的，是证明这一半的子集和里藏着固定公差的任意长等差数列——这要靠下面的二进分块。
下标 m： a₂1≤m<2 A₀ a₄,a₆2≤m<4 A₁ a₈ … a₁₄4≤m<8 A₂ a₁₆ … a₃₀8≤m<16 A₃ 第 j 块 Aⱼ 恰有 2ʲ 个元素；元素越往后越大，块越宽
二进分块：第 \(j\) 块 \(A_j\) 含 \(2^{j}\) 个偶下标元素。块大小成倍增长，正好配合稀疏假设给出的位置上界。
证明续（PDF 截断处之后的标准论证 · 补全说明）

原文 PDF 仅含本节前两页，在"假设 \(|A\cap[1,n]|\le Cn^{1/2}\) 蕴含：对所有……"处中断。下面按本书标准思路补全剩余论证的骨架（此段为编者补充的讲解，非逐字译文）：

  1. 定位每个块 \(A_j\)。块 \(A_j\) 中最大下标约为 \(2^{j+1}\)。由稀疏假设的逆向估计 \(a_{2^{j+1}}\gtrsim (2^{j+1}/C)^2=4^{\,j+1}/C^2\)，可知 \(A_j\) 整块落在某区间 \([1,\,O(4^{\,j})]\) 内，而它含 \(2^{j}\) 个元素。换言之，\(A_j\) 在长度约 \(N_j=O(4^{j})\) 的区间里有约 \(N_j^{1/2}\) 个元素——这恰是定理 12.2（关于一个集合的和集中出现长等差数列）所要求的"平方根密度"。
  2. 对每块用定理 12.2。于是 \(\mathrm{FS}(A_j)\) 含一条长度约 \(2^{j}\)、公差为某个 \(d_j\) 的等差数列；且公差 \(d_j\) 落在一个有界（或受控）的范围里。
  3. 抽屉原理固定公差。因为可能的公差 \(d_j\) 数量有限（受控），必有无穷多个 \(j\) 给出同一个公差 \(d\)。
  4. 拼接成任意长。把这无穷多块（公差都是 \(d\)）对应的等差数列适当平移、相加，便在 \(\mathrm{FS}(A')\) 中得到公差为 \(d\) 的任意长等差数列——这正是"良好划分"第一条所需。
  5. 收尾。至此 \(A=A'\cup A''\) 是一个良好划分（第一条由本步给出，第二条 (12.2) 由奇偶拆分给出）。由引理 12.21，\(A\) 次完备，即定理 12.17 得证。♦
回顾：整条证明链
  1. 引理 12.21：良好划分（有限条件）⇒ 次完备（无穷结论）。把"无穷"难题压缩成"有限"任务。
  2. 奇偶拆分 \(A=A'\cup A''\)：让 \(A''\) 凭稀疏假设满足 (12.2)。
  3. 二进分块 + 定理 12.2 + 抽屉原理：让 \(A'\) 的子集和含固定公差的任意长等差数列。
  4. 三者拼合 ⇒ 良好划分成立 ⇒ 定理 12.17。

返回 全书目录