Tao–Vu · 加性组合学 · 第 12 章 和集中的长等差数列
12.2 定理 12.4 的证明Proof of Theorem 12.4
本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 定义 / 定理 / 引理 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。本节是全书较难的一节，讲解会尽量把每一步的动机讲清楚。
本节目标第 12 章研究一个问题：把一个集合 \(A\) 自身相加许多次，得到的和集里会不会出现很长的等差数列？上一节叙述了定理 12.4，它断言：当 \(A\subset[1,n]\) 且 \(l^d|A|\ge C_d n\) 时，\(l\) 重和集 \(lA\) 必包含一条长度约为 \((l^d|A|)^{1/d}\) 的等差数列。本节给出它的证明。核心策略是：先证一个更强的结论（定理 12.5）——和集里不仅有一条直线（等差数列），还有一整块“高维的格点盒子”（广义等差数列），再从盒子里抠出一条长直线。证明的灵魂是一个叫做“树论证”的技巧。
预备：把记号和概念先说清楚
在进入证明之前，先把本节反复出现的几个对象解释透。它们是理解全节的钥匙。
迭代和集 \(lA\) 设 \(A\) 是一个整数集，\(l\ge 1\) 为整数。把 \(A\) 自身相加 \(l\) 次得到的集合记作
\[ lA \;=\; \underbrace{A+A+\dots+A}_{l\ \text{个}}\;=\;\{a_1+a_2+\dots+a_l:\ a_i\in A\}. \]
注意：\(lA\) 与“把每个元素乘以 \(l\)”的数乘 \(l\cdot A=\{la:a\in A\}\) 完全不同。本节 \(lA\) 一律指相加 \(l\) 次的和集。
广义等差数列（GAP）：秩与体积 一个秩为 \(d\) 的广义等差数列（generalized arithmetic progression）形如
\[ P=\Big\{\,a_0+n_1v_1+n_2v_2+\dots+n_dv_d\ :\ 0\le n_i< N_i\,\Big\}, \]
其中 \(a_0\) 是起点，\(v_1,\dots,v_d\) 是 \(d\) 个步长，\(N_1,\dots,N_d\) 是各方向的长度。
- 秩（rank）\(d\)：就是步长（方向）的个数。秩 \(=1\) 时就是普通的等差数列。
- 体积（volume）\(=N_1N_2\cdots N_d\)：把各方向长度相乘，是“格点盒子”里坐标组合 \((n_1,\dots,n_d)\) 的总数。
- 真（proper）：若不同的坐标 \((n_1,\dots,n_d)\) 总给出不同的数值（没有“撞车”），则称 \(P\) 是真的。此时 \(|P|=\) 体积；否则 \(|P|<\) 体积。
渐近记号 \(O_d,\ \Omega_d,\ \Theta_d\) 这是用来“忽略只依赖 \(d\) 的常数倍”的速记。
- \(X=O_d(Y)\)：存在只依赖 \(d\) 的常数 \(C\)，使 \(X\le C\,Y\)（\(X\) 至多是 \(Y\) 的若干倍，上界）。
- \(X=\Omega_d(Y)\)：存在只依赖 \(d\) 的常数 \(c>0\)，使 \(X\ge c\,Y\)（下界）。
- \(X=\Theta_d(Y)\)：同时是 \(O_d\) 与 \(\Omega_d\)（上下界都对，同阶）。
把目标换成更强的命题：定理 12.5
为证明定理 12.4，事实证明证一个更强的结论反而更方便。请注意：在引理 12.3 给出的例子里，和集不仅含有一条等差数列，实际上还含有一个大得多的广义等差数列。这个现象其实相当普遍：
定理 12.5 [350] 对任意固定的正整数 \(d\)，存在常数 \(C_d>0\) 使下述成立：对任意正整数 \(n,l\) 以及任意满足
\[ l^d|A|\ \ge\ C_d\,n \tag{12.5a}\]
的集合 \(A\subset[1,n]\)，和集 \(lA\) 包含一个真广义等差数列，其秩为 \(d'\)、体积至少为 \(\Omega_d\!\big(l^d|A|\big)\)，这里 \(d'\) 是某个满足 \(1\le d'\le d\) 的整数。
容易看出它蕴含定理 12.4，我们把这一步留作习题。引理 12.3 中的例子表明可以取到 \(d'=d\)（满秩）；而简单的例子 \(A=[1,m]\) 又表明可以取到 \(d'=1\)。当然，介于其间的 \(d'\) 取值也都有可能。
例：\(A=[1,m]\) 为什么给出 \(d'=1\) 取 \(A=[1,m]=\{1,2,\dots,m\}\)。把它相加 \(l\) 次：每个 \(a_i\) 在 \(1\) 到 \(m\) 之间，故和 \(a_1+\dots+a_l\) 取遍 \(l\) 到 \(lm\) 的每一个整数，即
\[ lA=[\,l,\ lm\,]=\{l,l+1,\dots,lm\}. \]
这是一条普通等差数列（秩 \(d'=1\)），长度 \(lm-l+1\approx lm\)。所以哪怕定理允许秩高达 \(d\)，这个具体例子里和集本身就只是一条直线，秩只能是 \(1\)。这说明定理 12.5 中的 \(d'\) 确实会随 \(A\) 不同而变化，不能一律取满秩。
为什么“更强”反而更好证直接去找一条长直线（秩 1）很难，因为直线是“一维”的、很挑剔。而允许找一个任意秩 \(1\le d'\le d\) 的高维盒子就宽松多了：盒子有很多形状可选，只要体积够大即可。证完盒子版本（定理 12.5）后，再用一条标准引理（习题 3.2.5）从体积为 \(V\)、秩为 \(d'\) 的盒子里抠出一条长度 \(\gtrsim V^{1/d'}\ge V^{1/d}\) 的直线，就回到了定理 12.4。
引理 12.6：等差数列的“合并”（coalescence）
我们现在来证明定理 12.5。先证明它对广义等差数列（而非一般集合）的一个版本。
引理 12.6（progressions 的合并） 设 \(P\) 是一个秩至多为 \(d\) 的整数真广义等差数列，\(l\ge1\) 为整数。则 \(lP\) 包含一个真广义等差数列，其秩为 \(d'\)、体积至少为 \(\Omega_d\!\big(l^d|P|\big)\)，这里 \(1\le d'\le d\)。
注 12.7（直觉实验） 不妨亲手实验一下：当 \(l\to\infty\) 时和集 \(lP\) 如何变化。例如取秩为 \(d=4\) 的真广义等差数列
\[ P=[1,m]^4\cdot(1,\ N_1,\ N_1N_2,\ N_1N_2N_3),\qquad m秩 \(d=4\) 的真广义等差数列（其大小按多项式增长，约为 \(l^d\)）。但到了某一刻会发生“碰撞”（collision），使和集本质上“合并（coalesce）”成一个秩为 \(d-1\) 或更低的广义等差数列（于是增长得稍慢一些）。经过有限次碰撞后，和集会合并成单独一条等差数列（外加可忽略的零头），此时它只随 \(l\) 线性增长。下面引理 12.6 的证明可以把这幅直观图景形式化，但因所需记号略嫌繁琐，这里不展开。这一结果也与闵可夫斯基第二定理（定理 3.30）以及 3.5 节的其他工具密切相关。
这个“碰撞导致降秩”的现象是全节的物理图像。用一个最小的具体例子把它看清楚：
例：看一次真实的“碰撞” 取秩 2 的真广义等差数列
\[ P=\{0,1,2\}+\{0,10,20\}=\{0,1,2,\ 10,11,12,\ 20,21,22\}, \]
步长为 \(1\)（长度 3）与 \(10\)（长度 3），体积 \(3\times3=9\)，且“真”（9 个数互不相同），故 \(|P|=9\)。现在逐步加大 \(l\)：
- \(lP=[0,2l]+\{0,10,20,\dots,10\cdot 2l\}\)。只要短边 \([0,2l]\) 还够不到步长 \(10\)，即 \(2l<10\)（也就是 \(l\le4\)），两个方向就互不干扰，\(lP\) 保持秩 2、真，体积 \((2l+1)(2l+1)\approx 4l^2\)。例如 \(l=4\)：短边 \([0,8]\)，与 \(10,20,\dots\) 不重叠。
- 当 \(l=5\) 时 \(2l=10\)，短边变成 \([0,10]\)，它的右端 \(10\) 正好撞上步长 \(10\)！于是 \([0,10]+\{0,10,20,\dots\}\) 里相邻两块首尾相接、连成一片：\(5P=[0,110]\) 变成一整条等差数列。秩从 2 掉到了 1——这就是“合并”。
- 此后 \(lP\)（\(l\ge5\)）一直是单条等差数列 \([0,22l]\)，大小随 \(l\) 线性增长，不再是 \(l^2\)。
引理 12.6 的证明. 我们对 \(d\) 作归纳。
- 基础情形 \(d=1\)：此时显然成立——\(lP\) 就是一条长度为 \(l|P|-l+1\) 的等差数列（与上面 \(A=[1,m]\) 的例子同理）。
- 归纳假设：设 \(d>1\)，且命题对 \(d-1\) 已证。又可设 \(l\) 相对 \(d\) 充分大，否则命题平凡（因为 \(lP\) 总包含 \(P\) 的一个平移，秩与体积已够）。
- 选取“倍增层数” \(k\)：取一个待定的大常数 \(C_d>1\)。令 \(k\ge1\) 是满足 \(2^k\le l/C_d\) 的最大整数。我们要考察 \(2^kP\)（把 \(P\) 倍增 \(k\) 次）。
- 情形 A：若 \(2^kP\) 仍是“真”的。那么它的大小就等于体积： \[ |2^kP|=\Theta_d\!\big(2^{kd}|P|\big)=\Theta_d\!\big(l^d|P|/C_d^{\,d}\big). \] 由于 \(lP\) 包含 \(2^kP\) 的一个平移，取 \(d'=d\) 即证完（体积达标）。
- 情形 B：若 \(2^kP\) 不再是“真”的（发生了碰撞）。令 \(1\le k'\le k\) 是使 \(2^{k'}P\) 首次变得“非真”的那一层。如前推理可知（碰撞只会让点数不减） \[ |2^{k'}P|\ \ge\ |2^{k'-1}P|=\Theta_d\!\big(2^{k'd}|P|\big). \]
- 用逆定理把“非真”的 \(P\) 装进低一维的盒子：对 \(2^{k'}P\) 施用定理 3.40，可知 \(O_d(1)\cdot 2^{k'}P\) 包含一个秩为 \(d-1\) 的真广义等差数列 \(Q\)，体积 \(\Theta_d\!\big(|2^{k'}P|\big)=\Theta_d\!\big(2^{k'd}|P|\big)\)。直觉：既然 \(2^{k'}P\) 因碰撞而“变扁”，它就能被一个维数更低的盒子高效罩住。
- 对低一维盒子用归纳假设：对 \(Q\)（秩 \(d-1\)）用归纳假设，得 \(2^{k-k'}Q\) 含一个秩为 \(d'\) 的真广义等差数列，体积至少 \[ \Omega_d\!\Big(2^{(k-k')d}\,|2^{k'}P|\Big)=\Omega_d\!\Big(2^{(k-k')d}\,2^{k'd}|P|\Big)=\Omega_d\!\big(2^{kd}|P|\big)=\Omega_d\!\big(l^d|P|/C_d^{\,d}\big), \] 其中 \(1\le d'\le d-1\)。
- 收尾：若 \(C_d\) 取得足够大，则 \(lP\) 包含 \(2^{k-k'}\cdot O_d(1)\cdot 2^{k'}P\) 的一个平移，从而包含 \(2^{k-k'}Q\) 的一个平移。命题得证。♦
从引理到定理：把长和集“拆成两段”
上面的引理让我们可以把“在 \(lA\) 中寻找一个低秩广义等差数列”这件事拆成两部分。第一，在 \(l'A\)（对某个 \(l'
两段式策略
- 第一段（造盒子）：先用“树论证 + 逆定理”，在前一小段的和集里制造出一个秩可能很高、但体积很大的真广义等差数列 \(Q\)。
- 第二段（合并降秩）：再把 \(Q\) 倍增若干次，用引理 12.6 把它“合并”成一个秩 \(d'\le d\) 的盒子，同时保住体积 \(\gtrsim l^d|A|\)。
定理 12.5 的证明.
- 先确保 \(l\) 足够大。由假设 \(l^d|A|\ge C_d n\) 与 \(A\subset[1,n]\)，只要把 \(C_d\) 取得（依赖 \(d\)）足够大，就能保证 \(l\) 也（依赖 \(d\)）足够大。
- 设定倍增层数 \(k\)。令 \(k\) 为满足 \(2^k\le l\) 的最大整数。于是 \[ 2^{kd}|A|\ \ge\ l^d|A|/2^d\ \ge\ C_d\,n/2^d. \tag{下界}\] 另一方面 \(2^kA\subset[1,2^kn]\)，所以（把上式反解出 \(n\le 2^d2^{kd}|A|/C_d\) 代入） \[ |2^kA|\ \le\ 2^kn\ \le\ \frac{2^{d}}{C_d}\,2^{k(d+1)}|A|. \tag{上界}\] 这一上下界的反差是整个证明的引擎：左边按 \(2^{kd}\) 量级，右边却被压在 \(2^{k(d+1)}/C_d\) 以内。
- 寻找“倍增常数变小”的那一层 \(k'\)。令 \(k'\ge1\) 为使 \[ |2^{k'}A|\ <\ 2^{k'(d+3/2)}|A| \] 成立的最小正整数。当 \(C_d\) 足够大时有 \(k'\le k\)，事实上还有 \[ k'\ \le\ k-\Omega_d(\log C_d). \] 动机：如果在每一层倍增时大小都翻得很猛（\(\ge 2^{(d+3/2)}\) 倍），那么经过 \(k\) 层后 \(|2^kA|\) 会大得超过上界 \((上界)\)，矛盾。所以必有某一层翻得不够猛——那一层就是 \(k'\)，那里“倍增常数”很小。
- 锁定一个倍增常数小的集合 \(A'\)。令 \(A':=2^{k'-1}A\)。由 \(k'\) 的最小性，前一层 \(k'-1\) 还不满足那个不等式，即 \[ |2^{k'-1}A|\ \ge\ 2^{(k'-1)(d+3/2)}|A|, \] 也就是 \(|A'|\ge 2^{(k'-1)(d+3/2)}|A|\)。又因 \(A'+A'=2^{k'}A\) 且 \(|2^{k'}A|<2^{k'(d+3/2)}|A|\le 2^{d+3/2}|A'|\)，得到 \[ |A'+A'|\ \le\ 2^{d+3/2}|A'|, \] 即 \(A'\) 的倍增常数是 \(O_d(1)\)。这正是逆定理可以发力的入口。
- 用逆定理在 \(A'\) 里找出盒子 \(Q\)。由习题 2.3.14，可在 \(A'\) 中找到一个关于某点 \(x/2\) 对称的子集 \(F\subset A'\)，满足 \(|F|=\Omega_d(|A'|)\)，且倍增常数 \(O_d(1)\)。对它施用Ruzsa–Chang 定理（定理 5.30），得知 \(2F-2F\) 包含一个秩为 \(O_d(1)\)、体积为 \(\Omega_d(|A'|)\) 的真广义等差数列。再由 \(F\) 的对称性，\(2F-2F\) 是 \(4F\) 的一个平移，而 \(4F\subset 4A'\)。于是 \[ 4A'=2^{k'+1}A\ \ \text{包含一个真广义等差数列}\ Q,\ \ \text{秩}\ O_d(1),\ \text{体积}\ \Omega_d(|A'|). \] 这就是“第一段”造出的高秩大盒子。
- 第二段：用引理 12.6 把 \(Q\) 合并降秩。注意 \(lA\) 包含 \(2^kA\) 的一个平移，而 \(2^kA\) 又包含 \(2^{\,k-k'-1}Q\)。对它用引理 12.6，得 \(lA\) 包含一个秩为 \(d'\)、体积为 \[ |P|=\Omega_d\!\Big(2^{(k-k')d'}|Q|\Big)=\Omega_d\!\Big(2^{(k-k')d'}|A'|\Big)=\Omega_d\!\Big(2^{(k-k')d'}\,2^{k'(d+3/2)}|A|\Big) \] 的真广义等差数列 \(P\)，其中 \(d'=O_d(1)\)。
- 用体积上界把 \(d'\) 卡到 \(\le d\)。因为 \(lA\subseteq[1,ln]\)，所以
\[ |lA|\ \le\ ln\ \le\ 2^{k+1}n\ \le\ \frac{2^{d+1}}{C_d}\,2^{k(d+1)}|A|. \]
由 \(|P|\le|lA|\)，得
\[ 2^{(k-k')d'}\,2^{k'(d+3/2)}|A|\ \le\ O_d\!\Big(\tfrac{1}{C_d}\,2^{k(d+1)}|A|\Big), \]
两边整理指数（把 \(k(d+1)\) 拆成 \((k-k')(d+1)+k'(d+1)\)）即得
\[ 2^{(k-k')(d'-d-1)}\ \le\ O_d\!\Big(\tfrac{1}{C_d}\,2^{-k'/2}\Big). \tag{关键不等式}\]
若 \(d'\ge d+1\)，左边 \(\ge1\)，而右边在 \(C_d\) 足够大时 \(<1\)，矛盾。故 \(d'
- 核对体积达标。最后 \[ |P|=\Omega_d\!\Big(2^{(k-k')d'}\,2^{k'(d+3/2)}|A|\Big)=\Omega_d\!\big(2^{kd}|A|\big)=\Omega_d\!\big(l^d|A|\big), \] 命题得证。♦
注 12.8（树论证） 这里的关键技巧，是把长和集 \(lA\) 拆开，写成一棵二叉求和树：
\[ 2^{k}A+2^{k}A=2^{k+1}A. \]
我们对 \(|lA|\) 的上界迫使其中某一次二元求和具有小的倍增常数，到了那一步就能动用逆定理——本例中是 Freiman 立方体引理与 Ruzsa–Chang 定理。类似技巧曾用于定理 2.35；亦见 [42]。此方法有时被称为树论证（tree argument）。
注 12.9（能否避开重型工具） 上面的证明用到了一些颇为强力的定理，包括定理 3.40 与 Ruzsa–Chang 定理。然而，证明上述结果其实可以不依赖这些来自加性几何与傅里叶分析的深刻事实，而改用更初等的逆定理，例如 \(3k-3\) 定理（定理 5.11）与 Freiman 立方体引理（定理 5.20）。见 [351] 及下面的习题。后一条路线被证明更为稳健（robust），特别是能处理受限和集 \(l^{*}A\)（restricted sum set）。
习题
习题
- 12.2.1 证明定理 12.5 蕴含定理 12.4。（提示：用习题 3.2.5——从一个秩 \(d'\)、体积 \(V\) 的真广义等差数列中可抠出长度 \(\gtrsim V^{1/d'}\) 的等差数列。）
- 12.2.2 仅用 \(3k-3\) 定理与树论证，证明：若 \(P\) 是一条整数等差数列，且 \(A\subset P\) 满足 \(|A|\ge\delta|P|\)，……（原文此处续接下一页，本节摘录到此。）
一句话回顾整节就做了三件事：(1) 把目标从“找直线”升级为更易证的“找盒子”（定理 12.5）；(2) 用树论证把长和集折成二叉树，迫使某层倍增常数变小，再用逆定理在那里造出大盒子；(3) 用引理 12.6（合并）把盒子降秩到 \(d'\le d\)，同时保住体积 \(\gtrsim l^d|A|\)。最后用习题 3.2.5 从盒子抠出长直线，回到定理 12.4。
返回 全书目录