Tao–Vu · 加性组合学 · 第 10 章 k=3 的 Szemerédi 定理

10.7　Szemerédi 的论证Szemerédi’s argument

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 引理 / 推论 / 证明 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。本节是全书较难的内容之一，讲解会尽量把每一步的直觉与动机说透。

本节目标给出 Roth 定理（“密度为正的整数集合一定含有长度为 3 的等差数列”）的第三种证明，作者是 Szemerédi。它既不用傅里叶分析、也不用正则性引理，而是完全初等、又相当简短。核心招数：用集合 \(A\) 与某个“和集”不相交这件事，来代替傅里叶证明中的“傅里叶偏差”，从而每一轮把 \(A\) 的密度往上推一点，反复迭代直到矛盾。

引子：三种证明的对比

本节我们给出 Roth 定理的又一个证明，归功于 Szemerédi（参见例如 [143]）。这个论证给出的界略好于由正则性引理得到的界，但仍然差于由傅里叶分析论证给出的界。不过，它的优点是完全初等而且相当短。这一论证的一个更复杂的版本也曾在 [343] 中被用来建立长度为 4 的等差数列情形的 Szemerédi 定理；但一般的 \(k\) 情形需要一个相当不同（而且更加复杂）的组合论证，我们这里不作讨论，见 [345]。

先把三种证明放在一起看
  1. 傅里叶分析证明（4.3 节）：界最好，但要用到指数和、傅里叶系数等分析工具。
  2. 正则性引理证明（10.6 节）：界最差，但概念上把图划成“近似随机块”，很直观。
  3. 本节 Szemerédi 的论证：界介于两者之间，但只用加减法、鸽笼原理与计数，不碰任何分析工具。这正是它值得单独讲一节的原因。
三者最终都得到同一个结论——Roth 定理——只是“锋利程度”和“所用工具”不同。

整体思路

直观上，想法如下。如果 \(A\) 是区间 \([1,N]\) 中的一个稠密集合，那么它应当包含一个大的方体 \(a+[0,1]^d\cdot v\)。如果 \(A\) 同时不含任何真正的长度为 3 的等差数列，那么这就意味着 \(A\) 必须与一个“大集合 \(A_0\) 与方体之和”所构成的和集 \[2a+[0,1]^d\cdot 2v-A_0\] 不相交。这种不相交性把 \(A\) “挤压”进一族中等长度的等差数列里，于是 \(A\) 的密度必然在其中至少一条等差数列上变大。这就制造出一个密度增量（density increment），人们随后便可以像在 Roth 定理的傅里叶分析证明中那样去迭代它。因此，这里是用“与某和集不相交”来替代傅里叶偏差（参看练习 4.3.12）。

这段话出现了几个关键词，先把它们解释清楚，再看引理。

关键概念：方体（cube）给定起点 \(a\)、\(d\) 个非零“步长” \(v_1,\dots,v_d\)，记 \(v=(v_1,\dots,v_d)\)，所谓方体 \[a+[0,1]^d\cdot v=\Big\{\,a+\varepsilon_1 v_1+\varepsilon_2 v_2+\cdots+\varepsilon_d v_d\;:\;\varepsilon_i\in\{0,1\}\,\Big\}\] 就是把每个步长“选或不选”得到的全部 \(2^d\) 个和。称它是真（proper）方体，是指这 \(2^d\) 个和两两不同，于是方体恰有 \(2^d\) 个元素。
024 681012 a=11+3=41+5=61+3+5=9 +v₁=3 +v₁=3 +v₂=5
取 \(a=1,\ v=(3,5),\ d=2\)：方体 \(=\{1,\ 1+3,\ 1+5,\ 1+3+5\}=\{1,4,6,9\}\)，共 \(2^2=4\) 个元素，互不相同，所以是“真”方体。\(d\) 越大，方体越大。

第一步：稠密集合一定含有方体

下面我们给出论证的主要步骤，把证明留作练习。首先我们需要证明：稠密集合必含方体。

引理 10.49 设 \(0<\delta<1\)，设 \(P\) 是一个大的真等差数列，又设 \(A\) 是 \(P\) 的子集且 \(|A|\ge\delta|P|\)。那么 \(A\) 含有一个真方体 \(a+[0,1]^d\cdot v\)，其中 \[d=\Omega_\delta(\log\log|P|).\] 特别地，所有步长 \(v_1,\dots,v_d\) 都非零。

这里的要点在于：当 \(|P|\to\infty\) 时，维数 \(d\)（虽然相当缓慢地）会趋于无穷。

怎么理解 \(d=\Omega_\delta(\log\log|P|)\) 直觉：\(A\) 占了 \(P\) 的 \(\delta\) 比例，于是存在很多平移量 \(v\) 使 \(A\) 与 \(A+v\) 大量重叠（练习 10.7.1 的提示）；反复利用这种“自我重叠”，就能把一个个步长 \(v_1,v_2,\dots\) 叠加上去，拼出一个方体。

第二步：无 3-AP 的稠密集合，二选一

作为这条引理的推论，我们有：

推论 10.50 设 \(0<\delta<1\)，设 \(N\) 是依赖于 \(\delta\) 的充分大整数，又设 \(A\subset[1,N]\) 满足 \(|A|\ge\delta N\) 且不含任何长度为 3 的真等差数列。那么下列两个陈述中至少有一个成立：
证明. 不失一般性，我们可以假设对所有 \(i=0,1,2,3\) 都有 \[\big|A\cap (iN/4,\,(i+1)N/4]\big|\le 1.1\,\delta N/4+O(1),\] 否则我们就已经得到一个密度增量（在某个长度约 \(N/4\) 的四等分块上密度已 \(\ge1.1\delta\)，第一种情形成立）。特别地，这蕴含对所有 \(i\) 都有 \(\big|A\cap(iN/4,(i+1)N/4]\big|=\Omega(\delta N)\)。把引理 10.49 应用于集合 \(A\cap(N/4,N/2]\)，可知这个集合含有一个具有所需性质的方体 \(a+[0,1]^d\cdot v\)。于是若令 \(A_0:=A\cap[1,N/4)\)，结论便可由如下观察得出：每当 \(x\in A_0\) 且 \(y\in a+[0,1]^d\cdot v\) 时，序列 \(x,\ y,\ 2y-x\) 是一个真等差数列，因此 \(2y-x\) 不可能落在 \(A\) 中。♦

这个推论是整套论证的“分叉点”，值得逐步拆开看。

  1. 先把 \([1,N]\) 四等分。四块分别是 \((0,N/4],(N/4,N/2],(N/2,3N/4],(3N/4,N]\)。
  2. 看每块里 \(A\) 占多少。如果某一块里 \(A\) 的密度已经 \(\ge1.1\delta\)，太好了：这一块本身就是长度约 \(N/4\) 的等差数列（公差 1），第一种情形“密度增量”当场成立，证明结束。
  3. 否则每块密度都 \(\le1.1\delta\)（再去掉小误差 \(O(1)\)）。由于四块加起来要装下 \(|A|\ge\delta N\) 个元素，每块又装不超过 \(1.1\delta\cdot N/4\)，于是每一块都不能太空——每块至少有 \(\Omega(\delta N)\) 个 \(A\) 的元素。否则其它块就装不下总量了。
  4. 第二块 \((N/4,N/2]\) 里 \(A\) 稠密，用引理 10.49 抽出方体。得到方体 \(a+[0,1]^d\cdot v\)，整个落在 \((N/4,N/2]\)。
  5. 第一块 \([1,N/4)\) 里取 \(A_0:=A\cap[1,N/4)\)，它也有 \(\Omega(\delta N)\) 个元素。
  6. 利用“无 3-AP”逼出不相交性。见下面的关键观察。
关键观察：为什么 \(2y-x\notin A\) 对任意 \(x\in A_0\subset A\) 与 \(y\)（方体里的点，\(y\in A\)），三个数 \[x,\quad y,\quad 2y-x\] 构成等差数列，因为相邻两项之差都等于 \(y-x\)：\(\;(y)-(x)=y-x,\;(2y-x)-(y)=y-x\)。而且因为 \(x真 3-AP。
现在 \(x\in A,\ y\in A\)。如果第三项 \(2y-x\) 也落在 \(A\)，那 \(A\) 里就藏了一条长度 3 的真等差数列——与假设矛盾！所以必有 \(2y-x\notin A\)。
让 \(x\) 跑遍 \(A_0\)、\(y\) 跑遍方体，所有这些 \(2y-x\) 组成的集合正是 \(2a+[0,1]^d\cdot 2v-A_0\)（因为 \(y=a+\sum\varepsilon_i v_i\Rightarrow 2y=2a+\sum\varepsilon_i(2v_i)\)）。它们全都不在 \(A\) 里，即此和集与 \(A\) 不相交。
1N/4N/2N A₀（第一块） 方体（第二块） x y 2y−x 公差 y−x 公差 y−x 必不属于 A
第一项 \(x\) 取自 \(A_0\)、中项 \(y\) 取自方体，二者都在 \(A\)。若末项 \(2y-x\) 也在 \(A\)，就出现一条真 3-AP，违反假设。故所有 \(2y-x\) 组成的和集与 \(A\) 不相交。

第三步：把不相交性变成密度增量

假设我们处在上述推论的情形之中，并且“与和集不相交”这一陈述成立。令 \[E_0\subset E_1\subset\cdots\subset E_d\subset[1,N]\] 为如下定义的集合： \[E_i:=2a+[0,1]^i\cdot(2v_1,\dots,2v_i)-A_0.\] 也就是说，\(E_i\) 只用前 \(i\) 个（加倍后的）步长来造方体、再减去 \(A_0\)。注意 \(E_d\) 正是上一步那个与 \(A\) 不相交的和集，而 \(E_0=2a-A_0\) 只是 \(A_0\) 的一个平移加翻转，规模与 \(A_0\) 相当。

由鸽笼原理，我们可以找到某个 \(1\le i\le d\)，使得 \[|E_i|\le|E_{i-1}|+O\!\left(\frac{N}{d}\right).\tag{1}\]

鸽笼为什么给出 (1) 集合链 \(E_0\subset E_1\subset\cdots\subset E_d\) 一路增大，但全都装在 \([1,N]\) 里，所以 \[|E_d|-|E_0|=\sum_{i=1}^{d}\big(|E_i|-|E_{i-1}|\big)\le N.\] 这是 \(d\) 个非负增量加起来不超过 \(N\)。若每一个增量都大于 \(N/d\)，总和就会超过 \(N\)，矛盾。所以至少有一个 \(i\) 的增量 \(\le N/d\)，即式 (1)。直觉：\(d\) 步把总长 \(N\) 用完，平均每步只能涨 \(N/d\)，必有一步“涨得不多”。

另一方面，我们有 \(E_i=E_{i-1}+\{0,2v_i\}\)。这表明我们可以把集合 \([1,N]\setminus E_i\) 划分成 \(O\!\big(\tfrac{N}{d}\big)\) 条公差为 \(2v_i\) 的真等差数列 \(P_1,\dots,P_k\)（见练习 10.7.2）。

为什么补集能切成少数几条等差数列 关系 \(E_i=E_{i-1}+\{0,2v_i\}\) 表示：把 \(E_{i-1}\) 整体再平移 \(2v_i\)，与原来的 \(E_{i-1}\) 合并，就得到 \(E_i\)。这正是练习 10.7.2 的形式：当 \(|A+\{0,r\}|\le|A|+k\) 时（这里 \(A=E_{i-1},\ r=2v_i\)，由 (1) 知“多出来”的部分只有 \(k=O(N/d)\) 个），补集 \([1,N]\setminus E_i\) 可被切成 \(O(k)=O(N/d)\) 条公差为 \(2v_i\) 的等差数列。
为什么是公差 \(2v_i\)？因为 \(E_i\) 在“沿步长 \(2v_i\) 平移”下几乎封闭（只在两端漏一点），所以它的补集沿同一步长排成一根根“竹竿”，每根就是一条公差 \(2v_i\) 的等差数列。
Eᵢ： 补集 P₁,…,Pₖ： +2vᵢ +2vᵢ 补集里的点沿步长 2vᵢ 串成少数几条等差数列 P₁,…,Pₖ（k=O(N/d)）
红格是 \(E_i\)，几乎在“平移 \(2v_i\)”下封闭；蓝格是补集 \([1,N]\setminus E_i\)，于是沿步长 \(2v_i\) 排成 \(O(N/d)\) 条等差数列。

观察到 \[\sum_{j=1}^{k}|P_j|=N-|E_i|\le N-|A_0|=\big(1-\Omega(\delta)\big)N.\tag{2}\] 另一方面，由于 \(A\) 与 \(E_i\) 不相交（\(A\) 整个落在补集里），我们有 \[\sum_{j=1}^{k}|A\cap P_j|=|A|\ge\delta N.\tag{3}\]

(2)(3) 在说什么：平均密度被抬高了 式 (2)：这些等差数列的总长度少于 \(N\)（因为 \(E_i\) 至少吃掉了 \(|A_0|=\Omega(\delta N)\) 的长度）。
式 (3)：\(A\) 的全部 \(\ge\delta N\) 个元素却原封不动地分布在这些等差数列里（一个都没丢，因为 \(A\) 不碰 \(E_i\)）。
于是把“同样多的 \(A\) 装进更短的总长度”，平均密度自然 \(>\delta\)： \[\frac{\sum|A\cap P_j|}{\sum|P_j|}\ge\frac{\delta N}{(1-\Omega(\delta))N}=\frac{\delta}{1-\Omega(\delta)}>\delta.\] 这就是密度被抬高的来源——挤压效应。

由此我们得到，对某个小的绝对常数 \(c>0\)， \[\sum_{j=1}^{k}\Big(|A\cap P_j|-(\delta+c\delta^2)|P_j|-cd\Big)>0.\tag{4}\] 于是由鸽笼原理，存在一条等差数列 \(P_j\)，使得 \[|P_j|\ge cd=\Omega_\delta(\log\log N)\quad\text{且}\quad|A\cap P_j|\ge(\delta+c\delta^2)|P_j|.\] 这就在一条长度随 \(N\to\infty\) 而趋于无穷的等差数列上建立了 \(A\) 的密度增量。这本质上就是推论 10.26（不过显式常数稍差一些），于是人们现在可以像之前那样迭代这条推论，从而建立 Roth 定理。

不等式 (4) 与那一项 \(-cd\) 的来历 把 (3) 减去 \((\delta+c\delta^2)\) 乘以 (2)： \[\sum_j|A\cap P_j|-(\delta+c\delta^2)\sum_j|P_j|\ge\delta N-(\delta+c\delta^2)\big(1-\Omega(\delta)\big)N=\Omega(\delta^2)\,N,\] （取 \(c\) 足够小，使 \(c\delta^2\) 这一项压不过 \(\Omega(\delta)\) 带来的好处）。这说明“超额密度”的总盈余有 \(\Omega(\delta^2)N\) 之多。
那为什么还要在每条里扣掉 \(cd\)？因为我们不只要“密度高”的等差数列，还要它足够长（长度 \(\ge cd\)），太短的没法继续迭代。把 \(cd\) 从每一项扣掉，扣掉的总量是 \(cd\cdot k=cd\cdot O(N/d)=O(cN)\)，仍小于盈余 \(\Omega(\delta^2)N\)，所以 (4) 的总和仍 \(>0\)。
鸽笼：和为正 \(\Rightarrow\) 至少一项为正，即 \(|A\cap P_j|-(\delta+c\delta^2)|P_j|-cd>0\)。由此 \(|A\cap P_j|>cd\)，故 \(|P_j|\ge|A\cap P_j|>cd\)（长度达标），同时密度 \(\ge\delta+c\delta^2\)（密度达标）。
为什么“密度增量 + 迭代”能逼出整个定理 设想 \(A\) 在 \([1,N]\) 中无 3-AP，密度 \(\delta\)。本节论证保证：
  1. 要么直接在某条长等差数列上密度跳到 \(1.1\delta\)（推论第一种情形）；
  2. 要么经过上面挤压，得到密度 \(\ge\delta+c\delta^2\) 的长等差数列。
无论哪种，把目光限制到那条长等差数列上（它本身可重新标号成一个 \([1,N']\)），密度就严格上升了。再在新区间上重复——密度 \(\delta\to\delta+c\delta^2\to\cdots\) 不断增加。
但密度永远 \(\le1\)！每次至少涨 \(c\delta^2\)，所以最多迭代 \(O(1/\delta)\) 轮密度就会冲破 1，出现矛盾。矛盾说明：当 \(N\) 大到一定程度，密度为 \(\delta\) 的集合不可能无 3-AP。这正是 Roth 定理。

最终的界

对此处各项界做一番仔细的核算，可得 \[r_3([1,N])=O\!\left(\frac{N}{\log^* N}\right),\] 这比由正则性引理得到的界稍微好一点。

\(\log^* N\) 是什么、这个界有多强 \(r_3([1,N])\) 表示 \([1,N]\) 中最大的无 3-AP 子集的元素个数。把它写成 \(O(N/\log^* N)\)，意思是“最大无 3-AP 集合的密度不超过 \(O(1/\log^* N)\)，随 \(N\to\infty\) 趋于 0”。
\(\log^* N\)（迭代对数）= “要对 \(N\) 连取几次对数才能降到 \(\le1\)”。它增长慢得离谱：\(\log^*(2)=1,\ \log^*(2^{2})=3,\ \log^*(2^{65536})=5\)。所以这个界虽然“密度趋于 0”，但趋于 0 极慢——这也是为什么说它只勉强优于正则性引理（后者得到的是 \(1/\log\log\cdots\) 中迭代次数更少、衰减更慢的界）。傅里叶证明则能给出像 \(1/(\log N)^c\) 这样快得多的衰减。

练习

练习 10.7.1 证明引理 10.49。（提示：先证明如下预备结论：若 \(|A|\ge\delta|P|\)，且 \(|P|\) 关于 \(\delta\) 充分大，则存在 \(\Omega(\delta^2|P|)\) 个 \(v\) 的取值，使得 \(|A\cap(A+v)|=\Omega(\delta^2|P|)\)。）
练习 10.7.2 设 \(A\subset[1,N]\)，\(r\neq0\)，满足 \(A+r\subset[1,N]\) 且 \(|A+\{0,r\}|\le|A|+k\)。证明 \([1,N]\setminus(A+\{0,r\})\) 可被划分成 \(O(k)\) 条互不相交、公差为 \(r\) 的等差数列。

返回 全书目录