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

10.4　定量界限Quantitative bounds

本页为译文 + 讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演 / 自测）与配图为面向高中生的详解，尽量把每一步的直觉与动机讲清楚，不用比喻。

本节目标记 \(r_3([1,N])\) 为区间 \([1,N]=\{1,2,\dots,N\}\) 里不含长度为 3 的等差数列（即没有形如 \(x,x+r,x+2r\)、\(r\neq0\) 的三元组）的最大子集的大小。上一节用“密度增量法”证出了 \(r_3([1,N])=O(N/\log\log N)\)。本节要回答一个纯粹的定量问题：这个上界能压到多小？我们将看到三级改进：
  (1) Heath-Brown–Szemerédi 把它压到 \(O(N/\log^c N)\)（某个绝对常数 \(c>0\)）；
  (2) Bourgain 进一步压到 \(O\!\big(\tfrac{\log\log N}{\log N}N\big)\)，这已逼近傅里叶分析方法的极限。
关键的技术升级是：用更省力的方式调用 Kronecker 定理（一次处理一批频率），最终干脆改用 Bohr 集代替等差数列来做迭代。本节较难，我们会把“为什么慢”“怎样变快”的动机讲透。

10.4.1　为什么会出现双重对数：瓶颈在哪里

在上一节中，我们对量 \(r_3([1,N])\) 得到了 \(O(N/\log\log N)\) 的界。这个双重对数（\(\log\log\)）出现的主要原因，在于引理 10.25 中对 Kronecker 定理的使用：它把等差数列 \(P\) 的长度大致缩成原来的平方根，却只把密度增加了很小的一点 \(O(\delta^2)\)。这一步如此低效，以至于值得把论证的其他部分弄得更复杂，从而减少调用 Kronecker 定理的次数。其中一种做法归功于 Heath-Brown 与 Szemerédi：一次性把 Kronecker 定理应用到一大批频率上，而不是一次只处理一个。它给出如下改进1：

直觉：迭代的“两本账”密度增量法是一个循环：每一轮，我们在当前的“容器”（一段等差数列）里找到一段更短的子等差数列，使 \(A\) 在其中的相对密度 \(\delta\) 上升一点。两件事同时发生：
  1. 密度账：每轮密度至少涨 \(\Omega(\delta^2)\)。密度封顶为 \(1\)，所以从 \(\delta\) 涨到 \(2\delta\) 大约要 \(1/\delta\) 轮，全程总轮数有限。
  2. 长度账：每轮容器都会缩短。缩得越狠，能迭代的轮数越少，最终界就越差。
瓶颈正是“长度账”：引理 10.25 每轮把长度 \(L\) 砍到 \(\sqrt{L}\)。若起始长度为 \(N\)，则 \(k\) 轮后长度只剩 \(N^{1/2^k}\)。要让长度还 \(\ge 2\)，必须 \(2^k\lesssim \log N\)，即 \(k\lesssim\log\log N\)。轮数被卡在 \(\log\log N\)，于是密度最多涨到 \(\sim\delta^2\log\log N\lesssim 1\)，得到 \(\delta=O(1/\sqrt{\log\log N})\)——再细致些就是 \(r_3=O(N/\log\log N)\)。要变快，就得让“长度账”不要掉得这么快。
每轮长度被开平方：\(N\to N^{1/2}\to N^{1/4}\to\cdots\) 第 0 轮：长度 N N^(1/2) N^(1/4) N^(1/8) 长度 ≈ N^(1/2^k)，约 loglog N 轮后用尽 → 双重对数瓶颈
平方根收缩极快：每砍一次，指数减半。轮数只能撑到 \(k\approx\log\log N\)，这正是 \(O(N/\log\log N)\) 里那个双重对数的来源。
定理 10.27　[177, 344]对一切充分大的 \(N\)，存在某个绝对常数 \(c>0\)，使得 \[ r_3(\mathbb{Z}_N),\ r_3([1,N]) = O\!\left(\frac{N}{\log^c N}\right). \]

1 作者感谢 Ben Green 向他们讲解了这些论证。

证明. 只需对 \(r_3([1,N])\) 验证该论断即可（对 \(\mathbb{Z}_N\) 的情形可化归到它）。我们将精炼上一节的论证，同样略去一些细节。首先需要下面这个命题 10.24 的变体。♦
为什么“一次一批”更快把上面的“长度账”改一改：与其每轮把长度开平方（\(L\to L^{1/2}\)），不如一次性对 \(|S|\) 个频率同时用一次 Kronecker 定理。代价是长度变成 \(L\to L^{1/(|S|+1)}\)（见下面引理 10.29），但由于这是多项式级的收缩而非反复开平方，迭代轮数可以达到 \(\Omega(\log N)\) 量级，从而把界改进成 \(N/\log^c N\)。关键是要先证明：缺少等差数列会逼出“一整批”大的傅里叶系数（命题 10.28），而不只是一个。

10.4.2　缺少等差数列 ⇒ 强非一致性

命题 10.28（缺少等差数列蕴含非一致性）设 \(A\subset[1,N]\) 满足 \(|A|=\delta N\)（某个 \(0<\delta\le1\)），且 \(A\) 不含真正的长度为 3 的等差数列。又设 \(N\ge100/\delta^2\)。取一个介于 \(N\) 与 \(2N\) 之间的素数 \(p\)，并把 \([1,N]\) 等同于 \(\mathbb{Z}_p\) 的一个子集。令 \(f_U:\mathbb{Z}_p\to\mathbb{R}\) 为函数 \(f_U:=1_A-\delta1_{[1,N]}\)。则存在一个集合 \(S\subset\mathbb{Z}_p\)，满足 \(|S|=O(\delta^{-3})\)，并且 \[ \sum_{\xi\in S}|\widehat{f_U}(\xi)|^2 = \Omega\!\left(\delta^2|S|^{1/5}\right). \]
读懂这些记号
证明. 记 \(f_U^{\perp}:=\delta1_{[1,N]}\)。像命题 10.24 那样论证，我们再次得到 \[ \sum_{\xi\in\mathbb{Z}_p}|\widehat{f_U^{\perp}}(\xi)|^2\,|\widehat{f_U}(-2\xi)| = \Omega(\delta^3), \] 或者与之非常相似的式子。一个直接的计算（留作习题）还表明 \[ \sum_{\xi\in\mathbb{Z}_p}|\widehat{f_U^{\perp}}(\xi)|^3 = O(\delta^3), \tag{10.13} \] 于是由 Hölder 不等式得 \[ \sum_{\xi\in\mathbb{Z}_p}|\widehat{f_U}(\xi)|^3 = \Omega(\delta^3). \tag{10.14} \] 现在为推出矛盾，假设 \[ \sum_{\xi\in S}|\widehat{f_U}(\xi)|^2 \le c\,\delta^2|S|^{1/5} \] 对一切集合 \(S\) 以及某个待定的小常数 \(c>0\) 都成立。特别地，把它应用到集合 \(S=\{\xi:\widehat{f_U}(\xi)\ge\lambda\}\)（\(\lambda\) 为任意参数），我们得到 \[ \lambda^2\,\big|\{\xi:\widehat{f_U}(\xi)\ge\lambda\}\big| \le c\,\delta^2\,\big|\{\xi:\widehat{f_U}(\xi)\ge\lambda\}\big|^{1/5}, \] 从而 \[ \big|\{\xi:|\widehat{f_U}(\xi)|\ge\lambda\}\big| \le c^{5/4}\,\delta^{5/2}\,\lambda^{-5/2}. \] 两边乘以 \(3\lambda^2\) 再积分，得到 \[ \int_0^{\delta}\big|\{\xi:|\widehat{f_U}(\xi)|\ge\lambda\}\big|\,3\lambda^2\,d\lambda = O\!\left(c^{5/4}\delta^3\right). \] 但容易验证（例如用 (4.15)）\(|\widehat{f_U}(\xi)|\le\delta\)，于是左边化简为 \(\sum_{\xi\in\mathbb{Z}_p}|\widehat{f_U}(\xi)|^3\)。然而只要 \(c\) 充分小，这就与 (10.14) 矛盾。论断得证。♦
例：层蛋糕公式为什么能把积分变成立方和 对任意 \(g\ge0\)，有恒等式 \(g(\xi)^3=\int_0^{g(\xi)}3\lambda^2\,d\lambda=\int_0^{\infty}3\lambda^2\,1_{\{g(\xi)\ge\lambda\}}\,d\lambda\)。把它对所有 \(\xi\) 求和并交换求和与积分：
  1. \(\displaystyle\sum_{\xi}|\widehat{f_U}(\xi)|^3=\sum_{\xi}\int_0^{\infty}3\lambda^2\,1_{\{|\widehat{f_U}(\xi)|\ge\lambda\}}\,d\lambda\)。
  2. 交换次序：\(\displaystyle=\int_0^{\infty}3\lambda^2\Big(\sum_{\xi}1_{\{|\widehat{f_U}(\xi)|\ge\lambda\}}\Big)d\lambda=\int_0^{\infty}3\lambda^2\,\big|\{\xi:|\widehat{f_U}(\xi)|\ge\lambda\}\big|\,d\lambda\)。
  3. 因为 \(|\widehat{f_U}(\xi)|\le\delta\)，当 \(\lambda>\delta\) 时计数为 \(0\)，积分上限可截到 \(\delta\)。
  4. 这就是上面“左边化简为 \(\sum|\widehat{f_U}|^3\)”的来历——一边它 \(=O(c^{5/4}\delta^3)\)，另一边 (10.14) 说它 \(=\Omega(\delta^3)\)；小 \(c\) 时 \(O(c^{5/4}\delta^3)<\Omega(\delta^3)\)，矛盾。
直觉：这是“分布函数法”——不去直接控制立方和，而是控制每个高度 \(\lambda\) 上有多少个大系数，再把各层加起来。反设的“批量上界”在每一层都太弱，逐层积累后与 (10.14) 顶撞。
λξ 高度 λ 这一层的宽度 = |{ξ:|f̂(ξ)|≥λ}|
把每个 \(|\widehat{f_U}(\xi)|^3\) 看成一根高度为 \(|\widehat{f_U}(\xi)|\) 的“柱子”的体积 \(\int_0^{高}3\lambda^2d\lambda\)；横着按高度 \(\lambda\) 切片，每片宽度就是“至少这么高的频率个数”。立方和 = 各切片体积之和。

10.4.3　非一致性 ⇒ 密度增量

引理 10.29（非一致性蕴含密度增量）　[287]设 \(N\) 与 \(p\) 如前一引理中所述。设 \(f:\mathbb{Z}_p\to\mathbb{R}\) 是一个支撑在 \([1,N]\) 上的函数，满足对一切 \(n\) 有 \(|f(n)|\le1\)，并且 \[ \sum_{\xi\in S}|\widehat{f}(\xi)|^2 \ge \sigma \tag{10.15} \] 对某个集合 \(S\subset\mathbb{Z}_p\) 与某个 \(\sigma>0\) 成立。则存在一个真正的等差数列 \(P\subset[1,N]\)，其长度 \(|P|=\Omega\!\left(\sigma N^{1/(|S|+1)}\right)\)，并且 \[ \big|\mathbb{E}_{n\in P}f(n)\big| = \Omega(\sigma). \]
这一步在干什么它把“频率世界”里的信息（一整批大傅里叶系数，总能量 \(\ge\sigma\)）翻译回“物理世界”：找到一段等差数列 \(P\)，使 \(f\) 在 \(P\) 上的平均值显著偏离 \(0\)（\(\Omega(\sigma)\)）。当 \(f=1_A-\delta\) 时，这意味着 \(A\) 在 \(P\) 上的密度比基准 \(\delta\) 高出 \(\Omega(\sigma)\)——这正是密度增量。注意长度只缩到 \(N^{1/(|S|+1)}\)（多项式级），这正是相对“开平方”的提速所在。
证明. 由 Kronecker 定理，可以找到 \(1\le r\le N^{1-\frac{1}{|S|+1}}\)，使得对一切 \(\xi\in S\) 有 \(\|r\xi\|_{\mathbb{R}/\mathbb{Z}}\le N^{-\frac{1}{|S|+1}}\)。令 \(Q\) 为等差数列 \(Q=[1,N^{\frac{1}{|S|+1}}/10]\cdot r\)，则一个简单的计算表明 \[ \frac{1}{\mathbb{P}_{\mathbb{Z}_p}(Q)}\,|\widehat{1_Q}(\xi)| = \Omega(1)\quad\text{对一切 }\xi\in S. \] 特别地，由 (4.2)、(4.9)、(10.15) 及上一行，我们有 \[ \left\|\frac{1}{\mathbb{P}_{\mathbb{Z}_p}(Q)}\,f*1_Q\right\|_{L^2(\mathbb{Z})}^2 = \frac{1}{\mathbb{P}_{\mathbb{Z}_p}(Q)^2}\sum_{\xi\in\mathbb{Z}_p}|\widehat{1_Q}(\xi)|^2\,|\widehat{f}(\xi)|^2 = \Omega(\sigma). \] 另一方面，由 \(f\) 的有界性， \[ \left\|\frac{1}{\mathbb{P}_{\mathbb{Z}_p}(Q)}\,f*1_Q\right\|_{L^1(\mathbb{Z})} \le \|f\|_{L^1(\mathbb{Z})}\,\frac{1}{\mathbb{P}_{\mathbb{Z}_p}(Q)}\|1_Q\|_{L^1(\mathbb{Z})} \le 1. \] 于是由 Hölder 不等式， \[ \left\|\frac{1}{\mathbb{P}_{\mathbb{Z}_p}(Q)}\,f*1_Q\right\|_{L^{\infty}(\mathbb{Z})} = \Omega(\sigma). \] 因此存在 \(x\in\mathbb{Z}\) 使得 \[ \big|\mathbb{E}_{y\in x-Q}f(y)\big| = \Omega(\sigma). \] 取 \(P=[1,N]\cap(x-Q)\)，论断得证。♦
例：从 \(L^2\) 大、\(L^1\) 小逼出 \(L^\infty\) 大 设 \(g=\frac{1}{\mathbb{P}_{\mathbb{Z}_p}(Q)}f*1_Q\)。我们手里有两条信息：
  1. \(\|g\|_{L^2}^2=\Omega(\sigma)\)：平均“能量”不小（这来自频率端的 (10.15)）。
  2. \(\|g\|_{L^1}\le1\)：总“质量”被有界性卡住。
  3. Hölder/插值：\(\|g\|_{L^2}^2\le\|g\|_{L^1}\,\|g\|_{L^\infty}\)。代入得 \(\Omega(\sigma)\le 1\cdot\|g\|_{L^\infty}\)，即 \(\|g\|_{L^\infty}=\Omega(\sigma)\)。
  4. \(L^\infty\) 大意味着存在某个点 \(x\) 处 \(g\) 很大；而 \(g(x)\) 就是 \(f\) 在以 \(x\) 为中心、形如 \(x-Q\) 的等差数列上的平均。取交 \(P=[1,N]\cap(x-Q)\) 即得目标等差数列。
直觉：能量铺得很广（\(L^2\) 大）但总量有限（\(L^1\) 小），那它必然在某处堆得很高（\(L^\infty\) 大）。这个“高峰”就是密度增量发生的地方。

证明的其余部分与上一节的论证类似，留作习题。

10.4.4　Bourgain 的改进：彻底改用 Bohr 集

Bourgain [39] 取得了进一步的改进，完全摒弃了对 Kronecker 定理的需求。其想法是避免使用等差数列，而全程使用 Bohr 集，特别是正则 Bohr 集（regular Bohr set）。由此得到下述结果；它看起来非常接近傅里叶分析方法的极限（在某种意义上，它是命题 10.12 的自然推广）：

什么是 Bohr 集，为什么换它对频率集合 \(S\subset Z\)（的对偶）与半径 \(\rho>0\)，Bohr 集定义为 \[ \mathrm{Bohr}(S,\rho)=\{x\in Z:\ \|\xi\cdot x\|_{\mathbb{R}/\mathbb{Z}}\le\rho\ \text{对一切}\ \xi\in S\}. \] 它是“在每个频率 \(\xi\) 方向上都几乎不转动”的那些 \(x\)。\(|S|=d\) 称为它的秩（rank）。
为什么换它？等差数列在迭代里每轮长度被开平方，掉得太快；而 Bohr 集在迭代中只是秩加 1、半径乘以一个 \(\mathrm{poly}(\delta/d)\) 因子（命题 10.32）。这是温和得多的收缩——秩最多涨到 \(O(1/\delta)\)，半径每轮乘 \((\delta/2d)^{31}\)，于是 \(\sim1/\delta\) 轮之后半径仍有 \(\delta^{O(1/\delta)}\)，Bohr 集仍然够大。这把“长度账”从双重对数瓶颈解放出来，换来 \(\frac{\log\log N}{\log N}N\) 的界。
单个频率 ξ：‖ξx‖≤ρ x 允许的 x：相位落在两个小弧内 两个频率 S={ξ₁,ξ₂}：交集 Bohr(S,ρ) 秩 d=|S|；半径 ρ 略变时大小几乎不变 ⇒ 正则
Bohr 集是若干“相位约束”的交。秩 \(d=|S|\) 控制它的“维数”。正则指：把半径从 \(\rho\) 略微改成 \(\rho\pm\rho'\) 时，集合的测度几乎不变——这样边界上的“薄壳”可以忽略，迭代里的误差才控制得住。
定理 10.30（Roth–Bourgain 定理）对一切阶为充分大的有限奇数的加法群 \(Z\)，有 \[ r_3(Z) = O\!\left(\frac{\log\log|Z|}{\log|Z|}\,|Z|\right). \] 特别地，对一切充分大的 \(N\)， \[ r_3(\mathbb{Z}_N),\ r_3([1,N]) = O\!\left(\frac{\log\log N}{\log N}\,N\right). \]

这条定理可由下面这个变体轻松推出；后者可视为定理 10.17 的推广：

定理 10.31对一切阶为充分大有限奇数的加法群 \(Z\)，以及一切满足 \(0\le f(x)\le1\) 的 \(f:Z\to\mathbb{R}^+\)，有 \[ \Lambda_3(f,f,f) = \Omega\!\left(\mathbb{E}_Z(f)^{\,O(\mathbb{E}_Z(f)^{-2})}\right). \]
定理 10.31 在说什么这里 \(\mathbb{E}_Z(f)\) 是 \(f\) 的平均值（即“密度”），\(\Lambda_3(f,f,f)=\mathbb{E}_{x,r\in Z}f(x-r)f(x)f(x+r)\) 是“加权计数的长度-3 等差数列个数”。定理给出一个下界：只要平均密度为 \(\mathbb{E}_Z(f)\)，等差数列就至少有 \(\mathbb{E}_Z(f)^{O(1/\mathbb{E}_Z(f)^2)}\) 这么多（注意底数 \(<1\)、指数为大正数，所以这是个很小但非零的量）。它比上一节的 \(\Omega(\exp(-\exp(O(1/\mathbb{E}_Z(f)))))\)（双重指数小）要大得多——指数从“双指数”降为“单指数 \(\times\log\)”，正对应 \(r_3\) 从 \(N/\log\log N\) 改进到 \(\frac{\log\log N}{\log N}N\)。我们把由定理 10.31 推出定理 10.30 留作习题。

为证明定理 10.31，主要工具将是下面这个结果，它替代了推论 10.26。

命题 10.32（缺少等差数列蕴含密度增量）设 \(Z\) 为阶为大奇数的加法群，设 \(\mathrm{Bohr}(S,\rho)\) 为秩 \(d\) 的正则 Bohr 集，设 \(f:Z\to\mathbb{R}^+\) 满足 \(0\le f(x)\le1\)，且对某个 \(x_0\in Z\) 有 \(\mathbb{E}_{x\in x_0+\mathrm{Bohr}(S,\rho)}f(x)\ge\delta\)。又设 \[ \Lambda_3(f,f,f) \le \left(\frac{\delta}{2d}\right)^{100d}\rho. \] 则存在一个秩至多为 \(d+1\)、半径 \(\rho'\ge\left(\frac{\delta}{2d}\right)^{31}\rho\) 的正则 Bohr 集 \(\mathrm{Bohr}(S',\rho')\)，以及一个元素 \(x_0'\in Z\)，使得 \[ \mathbb{E}_{x\in x_0'+\mathrm{Bohr}(S',\rho')}f(x) \ge \delta + \delta^2/2^{10}. \]
命题 10.32 的循环结构它就是 Bohr 集版的“密度增量一步”： 反复套用：密度每轮涨 \(\sim\delta^2\)，约 \(1/\delta\) 轮密度翻倍直至触顶；秩从 \(d\) 涨到 \(O(1/\delta)\)，半径降到 \(\delta^{O(1/\delta)}\)。把这些代进去就得到定理 10.31。由命题 10.32 推出定理 10.31 同样直接，也留作另一道习题。

10.4.5　命题 10.32 的证明

1 读者不应过分认真地对待本论证中的数值常数（尤其是 \(2\) 的各次幂）；它们当然不是最优的。

证明. 通过平移，可设 \(x_0=0\)。必要时增大 \(\delta\)，可设 \(\mathbb{E}_{x\in\mathrm{Bohr}(S,\rho)}f(x)=\delta\)。把 \(f\) 在 \(\mathrm{Bohr}(S,\rho)\) 外置零，可设 \(f\) 支撑在 \(\mathrm{Bohr}(S,\rho)\) 上。现在为推出矛盾，假设 \[ \mathbb{E}_{x\in x_0'+\mathrm{Bohr}(S',\rho')}f(x) < \delta + \delta^2/2^{10} \tag{10.16} \] 对一切 \(x_0'\in Z\)、一切秩至多 \(d+1\) 且半径至少 \(\left(\frac{\delta}{2d}\right)^{31}\rho\) 的 Bohr 集 \(\mathrm{Bohr}(S',\rho')\) 都成立。

由引理 4.25，可找到 \(0<\rho_3<\rho_2<\rho_1<\rho\)，使得对每个 \(j=1,2,3\)，有 \[ \left(\frac{\delta}{2d}\right)^{10j+1}\rho \le \rho_j \le \left(\frac{\delta}{2d}\right)^{10j}\rho, \] 并且 \(\mathrm{Bohr}(S,\rho_j)\) 是正则的。注意集合 \(\mathrm{Bohr}(S,\rho),\mathrm{Bohr}(S,\rho_1),\mathrm{Bohr}(S,\rho_2),\mathrm{Bohr}(S,\rho_3)\) 的大小会相差 \(\delta^{O(d)}\) 倍，这对我们的应用而言太大。因此我们必须分别仔细追踪每个 Bohr 集的密度。

由假设并作变量替换，我们有 \[ \mathbb{E}_{x,r\in Z}f(x-r)f(x)f(x+r) = \Lambda_3(f,f,f) \le \left(\frac{\delta}{2d}\right)^{100d}\rho; \] 特别地，由 (4.25) 得 \[ \mathbb{E}_{x,r\in Z}f(x-r)f(x)f(x+r) \le \frac{\delta^3}{4}\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho))\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho_1))\quad(\text{譬如}). \] 由于 \(f\) 非负，我们可以把 \(r\) 局部化到 \(\mathrm{Bohr}(S,\rho_1)\)，得到 \[ \mathbb{E}_{x\in Z;\,r\in\mathrm{Bohr}(S,\rho_1)}f(x-r)f(x)f(x+r) \le \frac{\delta^3}{4}\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho)). \tag{10.17} \]

总策略：把“坏的小”拆成“好的大 + 误差”记 \(f_U^{\perp}:=\delta1_{\mathrm{Bohr}(S,\rho)}\)（密度的“均匀骨架”），\(f-f_U^{\perp}\) 是涨落。(10.17) 说“真实的三元乘积很小”。下面把它恒等地拆成两块：(a) 用骨架 \(f_U^{\perp}\) 算出的“主项”——它必然大（\(\sim\delta^3\)）；(b) 含涨落 \(f-f_U^{\perp}\) 的“误差项”。既然“主项大、总和小”，误差项就只能更大。误差项大，就意味着涨落 \(f-f_U^{\perp}\) 有线性偏差——这又逼出一个新频率 \(\xi\)，把它并进 \(S\) 就得到密度增量。这正是整段长证明的脉络。

记 \(f_U^{\perp}:=\delta1_{\mathrm{Bohr}(S,\rho)}\)。由上式关于 \(r\) 的对称性，可以验证如下恒等式 \[ \begin{aligned} &\mathbb{E}_{x\in Z;\,r\in\mathrm{Bohr}(S,\rho_1)}f(x-r)f(x)f(x+r)\\ &= \mathbb{E}_{x\in Z;\,r\in\mathrm{Bohr}(S,\rho_1)}f_U^{\perp}(x-r)f(x)f_U^{\perp}(x+r)\\ &\quad+ \mathbb{E}_{x\in Z;\,r\in\mathrm{Bohr}(S,\rho_1)}(f-f_U^{\perp})(x-r)f(x)(f+f_U^{\perp})(x+r). \end{aligned} \tag{10.18} \]

注意，若 \(x\in\mathrm{Bohr}(S,\rho-\rho_1)\) 且 \(r\in\mathrm{Bohr}(S,\rho_1)\)，则 \(x\pm r\in\mathrm{Bohr}(S,\rho)\)，因此 \[ \mathbb{E}_{r\in\mathrm{Bohr}(S,\rho_1)}f_U^{\perp}(x-r)f(x)f_U^{\perp}(x+r) = \delta^2 f(x). \] 于是由 \(f\) 与 \(f_U^{\perp}\) 的非负性， \[ \mathbb{E}_{x\in Z;\,r\in\mathrm{Bohr}(S,\rho_1)}f_U^{\perp}(x-r)f(x)f_U^{\perp}(x+r) \ge \delta^2\,\mathbb{E}_{x\in Z}f(x)1_{\mathrm{Bohr}(S,\rho-\rho_1)}(x). \] 由假设我们有 \[ \mathbb{E}_{x\in Z}f(x)1_{\mathrm{Bohr}(S,\rho)}(x) = \delta\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho)), \] 而由 \(\mathrm{Bohr}(S,\rho)\) 的正则性， \[ \mathbb{E}_{x\in Z}f(x)1_{\mathrm{Bohr}(S,\rho-\rho_1)}(x) \ge \frac{\delta}{2}\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho))\quad(\text{譬如}). \] 综合以上三个估计，我们得到 \[ \mathbb{E}_{x\in Z;\,r\in\mathrm{Bohr}(S,\rho_1)}f_U^{\perp}(x-r)f(x)f_U^{\perp}(x+r) \ge \frac{\delta^3}{2}\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho)). \] 把它与 (10.17)、(10.18) 结合，便得 \[ \left|\mathbb{E}_{x\in Z;\,r\in\mathrm{Bohr}(S,\rho_1)}(f-f_U^{\perp})(x-r)f(x)(f+f_U^{\perp})(x+r)\right| \ge \frac{\delta^3}{4}\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho)); \] 把它按 \(r\) 平移，得到 \[ \left|\mathbb{E}_{x\in Z;\,r\in\mathrm{Bohr}(S,\rho_1)}(f-f_U^{\perp})(x)f(x+r)(f+f_U^{\perp})(x+2r)\right| \ge \frac{\delta^3}{4}\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho)). \]

尺度难题：r 比 x 还细上式想用来推出 \(f-f_U^{\perp}\) 的“线性偏差”，但约束 \(r\in\mathrm{Bohr}(S,\rho_1)\) 不利——它把 \(r\) 局部化到比 \(x\) 更小的尺度。要做傅里叶分析，得反过来：让位置变量比平移变量更细。解决办法是把 \(x\) 局部化到更小的尺度 \(\rho_2\)（写 \(x=y+z\)，\(z\in\mathrm{Bohr}(S,\rho_2)\)），随后才能安全地去掉 \(r\) 的限制。这就是接下来反复出现 \(\rho_1>\rho_2>\rho_3\) 三个尺度、并不断利用正则性吞掉“薄壳误差”的原因。

我们希望用这个事实推出 \(f-f_U^{\perp}\) 中的某种线性偏差。不幸的是约束 \(r\in\mathrm{Bohr}(S,\rho_1)\) 并不有利（它把 \(r\) 局部化到比 \(x\) 更小的尺度）。为解决此问题，需要把变量 \(x\) 局部化到更小的尺度，即 \(\rho_2\)。为此写 \(x=y+z\)，其中 \(z\) 限制在 \(\mathrm{Bohr}(S,\rho_2)\) 中，于是有 \[ \left|\mathbb{E}_{y\in Z;\,r\in\mathrm{Bohr}(S,\rho_1);\,z\in\mathrm{Bohr}(S,\rho_2)}(f-f_U^{\perp})(y+z)f(y+z+r)(f+f_U^{\perp})(y+z+2r)\right| \ge \frac{\delta^3}{4}\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho)). \]

注意我们可以把 \(y\) 局部化到 \(\mathrm{Bohr}(S,\rho+\rho_2)\)，否则期望内的表达式为零。由于 \(f\) 有界且 \(\mathrm{Bohr}(S,\rho)\) 正则，\(\mathrm{Bohr}(S,\rho+\rho_2)\setminus\mathrm{Bohr}(S,\rho)\) 的贡献可以粗略地界为 \[ \mathbb{P}_Z(\mathrm{Bohr}(S,\rho+\rho_2)) - \mathbb{P}_Z(\mathrm{Bohr}(S,\rho)) \le \frac{\delta^3}{8}\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho-\rho_2))\quad(\text{譬如}). \] 于是我们可以把 \(y\) 限制到 \(\mathrm{Bohr}(S,\rho-\rho_2)\)，并用三角不等式得到 \[ \mathbb{E}_{y\in\mathrm{Bohr}(S,\rho-\rho_2)}F(y) \ge \frac{\delta^3}{8}, \] 其中 \[ F(y) := \left|\mathbb{E}_{r\in\mathrm{Bohr}(S,\rho_1);\,z\in\mathrm{Bohr}(S,\rho_2)}(f-f_U^{\perp})(y+z)f(y+z+r)(f+f_U^{\perp})(y+z+2r)\right|. \]

既然现在位置变量 \(z\) 被局部化到了比平移变量 \(r\) 更小的尺度，我们现在可以如下去掉平移限制 \(r\in\mathrm{Bohr}(S,\rho_1)\)。把 \(F(y)\) 改写为 \[ F(y) = \frac{\mathbb{E}_{z\in\mathrm{Bohr}(S,\rho_2)}\,\mathbb{E}_{r\in Z}\,1_{\mathrm{Bohr}(S,\rho_1)}(r)(f-f_U^{\perp})(y+z)f(y+z+r)(f+f_U^{\perp})(y+z+2r)}{\mathbb{P}_Z(\mathrm{Bohr}(S,\rho_1))}. \] 现在注意，对每个固定的 \(y\) 与每个固定的 \(z\in\mathrm{Bohr}(S,\rho_2)\)，函数 \[ 1_{\mathrm{Bohr}(S,\rho_1)}(r) - 1_{y+\mathrm{Bohr}(S,\rho_1)}(y+z+r)\,1_{2\cdot\mathrm{Bohr}(S,\rho_1)}(y+z+2r) \] 在 \(r\) 变量中的 \(L^1(Z)\) 范数至多为 \(\mathbb{P}_Z\big(\mathrm{Bohr}(S,\rho_1+2\rho_2)\setminus\mathrm{Bohr}(S,\rho_1-2\rho_2)\big)\)，而由 \(\mathrm{Bohr}(S,\rho_1)\) 的正则性，这至多为 \(\frac{\delta^3}{16}\mathbb{P}_Z(\mathrm{Bohr}(S,\rho_1))\)。利用这一点及 \(f\) 的有界性，我们看到，若记 \[ \begin{aligned} \widetilde{F}(y) &:= \Big|\mathbb{E}_{z\in\mathrm{Bohr}(S,\rho_2)}\frac{1}{\mathbb{P}_Z(\mathrm{Bohr}(S,\rho_1))}\mathbb{E}_{r\in Z}\,1_{y+\mathrm{Bohr}(S,\rho_1)}(y+z+r)\,1_{2\cdot\mathrm{Bohr}(S,\rho_1)}(y+z+2r)\\ &\qquad\times(f-f_U^{\perp})(y+z)f(y+z+r)(f+f_U^{\perp})(y+z+2r)\Big|\\ &= \frac{\big|\Lambda_3\big((f-f_U^{\perp})1_{y+\mathrm{Bohr}(S,\rho_2)},\,f1_{y+\mathrm{Bohr}(S,\rho_1)},\,(f+f_U^{\perp})1_{y+2\cdot\mathrm{Bohr}(S,\rho_1)}\big)\big|}{\mathbb{P}_Z(\mathrm{Bohr}(S,\rho_1))\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho_2))}, \end{aligned} \] 则 \(F(y)\) 与 \(\widetilde{F}(y)\) 相差至多 \(\delta^3/16\)。特别地，我们有 \[ \mathbb{E}_{y\in\mathrm{Bohr}(S,\rho-\rho_2)}\widetilde{F}(y) \ge \frac{\delta^3}{16}. \tag{10.19} \]

一阶矩法：先处理“均值不为零”的技术障碍下一步想对涨落 \((f-f_U^{\perp})1_{y+\mathrm{Bohr}(S,\rho_2)}\) 做傅里叶分析（用 \(u^2\) 范数 / Gowers 一致性），但它的均值可能不为零，这会污染估计。\(G(y)\) 正是“在 \(y\) 附近这块小 Bohr 集上，涨落的局部平均”。整体看 \(G\) 均值为 \(0\)、绝对值 \(\le1\)；而由反设 (10.16)，它在内部 \(\le\delta^2/2^{10}\)。一阶矩法说：\(|G|\) 的平均很小，所以绝大多数 \(y\) 处局部均值可忽略——我们就挑这样一个好 \(y\)，使 \(\widetilde F(y)\) 仍大而 \(|G(y)|\) 又小。

此刻我们需要停下来处理一个技术问题：函数 \((f-f_U^{\perp})1_{y+\mathrm{Bohr}(S,\rho_2)}\) 可能具有非零均值。幸运的是这可以用一阶矩法处理。令 \(G(y)\) 表示函数 \[ G(y) := \mathbb{E}_{x\in y+\mathrm{Bohr}(S,\rho_2)}(f-f_U^{\perp}). \] 由于 \(f\) 与 \(f_U^{\perp}\) 都取值于 \(0\) 与 \(1\) 之间且具有相同的均值，我们看到 \(G\) 的绝对值有界于 \(1\) 且均值为零。此外，当 \(y\notin\mathrm{Bohr}(S,\rho+\rho_2)\) 时 \(G(y)\) 为零，而由 (10.16)，当 \(y\in\mathrm{Bohr}(S,\rho-\rho_2)\) 时 \(G(y)\) 上界为 \(\delta^2/2^{10}\)。由于 \(\mathrm{Bohr}(S,\rho)\) 正则，我们因此看到 \[ \begin{aligned} \mathbb{E}_{x\in Z}\max(G(y),0) &\le \frac{\delta^2}{2^{10}}\mathbb{P}_Z(\mathrm{Bohr}(S,\rho-\rho_2)) + \mathbb{P}_Z\big(\mathrm{Bohr}(S,\rho+\rho_2)\setminus\mathrm{Bohr}(S,\rho-\rho_2)\big)\\ &\le \frac{\delta^2}{2^{9}}\mathbb{P}_Z(\mathrm{Bohr}(S,\rho-\rho_2)). \end{aligned} \] 由于 \(|G(y)|=G(y)+2\max(G(y),0)\)，我们于是有 \[ \mathbb{E}_{x\in\mathrm{Bohr}(S,\rho-\rho_2)}|G(y)| \le \frac{1}{\mathbb{P}_Z(\mathrm{Bohr}(S,\rho-\rho_1))}\mathbb{E}_{x\in Z}|G(y)| \le \frac{\delta^2}{2^{8}}; \] 把它与 (10.19) 结合，得到 \[ \mathbb{E}_{y\in\mathrm{Bohr}(S,\rho-\rho_2)}\Big[\widetilde{F}(y) - 8\delta|G(y)|\Big] \ge \frac{\delta^3}{32}, \] 从而存在 \(y\in\mathrm{Bohr}(S,\rho-\rho_2)\) 使得 \[ \widetilde{F}(y) \ge 8\delta|G(y)| + \frac{\delta^3}{32}. \]

我们固定这个 \(y\)，回到对 \(\widetilde{F}(y)\) 的分析。由命题 10.11，我们有 \[ \begin{aligned} \widetilde{F}(y) \le \frac{1}{\mathbb{P}_Z(\mathrm{Bohr}(S,\rho_1))\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho_2))}\,&\big\|(f-f_U^{\perp})1_{y+\mathrm{Bohr}(S,\rho_2)}\big\|_{u^2(Z)}\\ &\times\big\|f1_{y+\mathrm{Bohr}(S,\rho_1)}\big\|_{L^2(Z)}\,\big\|(f+f_U^{\perp})1_{y+2\cdot\mathrm{Bohr}(S,\rho_1)}\big\|_{L^2(Z)}. \end{aligned} \] 由 (10.16) 我们有 \[ \big\|f1_{y+\mathrm{Bohr}(S,\rho_1)}\big\|_{L^2(Z)}^2 \le 2\delta\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho_1)) \] 以及 \[ \big\|(f+f_U^{\perp})1_{y+2\cdot\mathrm{Bohr}(S,\rho_1)}\big\|_{L^2(Z)}^2 \le 8\delta\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho_1)). \] 于是我们有 \[ \widetilde{F}(y) \le \frac{4\delta}{\mathbb{P}_Z(\mathrm{Bohr}(S,\rho_2))}\sup_{\xi\in Z}\big|\big[(f-f_U^{\perp})1_{y+\mathrm{Bohr}(S,\rho_2)}\big]^{\wedge}(\xi)\big|. \] 因此存在 \(\xi\in Z\) 使得 \[ \frac{1}{\mathbb{P}_Z(\mathrm{Bohr}(S,\rho_2))}\big|\big[(f-f_U^{\perp})1_{y+\mathrm{Bohr}(S,\rho_2)}\big]^{\wedge}(\xi)\big| \ge 2|G(y)| + \frac{\delta^2}{128}. \]

出现了新频率 ξ：这就是“增量”的种子上式说：在 \(y+\mathrm{Bohr}(S,\rho_2)\) 上，涨落 \(f-f_U^{\perp}\) 有一个大的傅里叶系数 \(\xi\)（大小超过 \(2|G(y)|+\delta^2/128\)）。这意味着 \(f\) 沿频率 \(\xi\) 有线性偏好。把 \(\xi\) 并入频率集合 \(S'=S\cup\{\xi\}\)，并把 Bohr 集收窄到 \(\mathrm{Bohr}(S',\rho_3)\)，就能在某个平移位置上把密度抬高 \(\delta^2/2^{10}\)——但 (10.16) 又禁止任何这样的抬升。两者顶撞，矛盾。最后几步就是把这个“频率证据”干净地转化为“密度抬升”，途中要消去乘子 \(2+\mathrm{Re}\,e(-\xi\cdot x+\theta)\)。

由于 \(y\in\mathrm{Bohr}(S,\rho-\rho_2)\)，在 \(y+\mathrm{Bohr}(S,\rho_2)\) 上有 \(f_U^{\perp}=\delta\)。因此我们能找到一个相位 \(\theta\in\mathbb{R}/\mathbb{Z}\)，使得 \[ \mathrm{Re}\,\mathbb{E}_{x\in y+\mathrm{Bohr}(S,\rho_2)}(f(x)-\delta)e(-\xi\cdot x+\theta) \ge 2\big|\mathbb{E}_{x\in y+\mathrm{Bohr}(S,\rho_2)}(f-\delta)\big| + \frac{\delta^2}{128}. \] 特别地，由三角不等式， \[ \mathbb{E}_{x\in y+\mathrm{Bohr}(S,\rho_2)}(f(x)-\delta)\big[2 + \mathrm{Re}\,e(-\xi\cdot x+\theta)\big] \ge \frac{\delta^2}{128}. \]

剩下唯一的任务是消去乘子 \(2+\mathrm{Re}\,e(-\xi\cdot x+\theta)\)。这将通过把 Bohr 集 \(\mathrm{Bohr}(S,\rho_2)\) 换成更窄的 \(\mathrm{Bohr}(S',\rho_3)\) 来完成，其中 \(S':=S\cup\{\xi\}\)。写 \(x=w+z\)，其中 \(z\in\mathrm{Bohr}(S',\rho_3)\)，我们看到 \[ \begin{aligned} &\mathbb{E}_{w\in Z;\,z\in\mathrm{Bohr}(S',\rho_3)}1_{\mathrm{Bohr}(S,\rho_2)}(w+z)(f(w+z)-\delta)\big[2 + \mathrm{Re}\,e(-\xi\cdot w+\theta)e(-\xi\cdot z)\big]\\ &\qquad\ge \frac{\delta^2}{128}\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho_2)). \end{aligned} \] 由于 \(z\in\mathrm{Bohr}(S',\rho_3)\)，由 (4.24) 有 \(|e(-\xi\cdot z)-1|\le2\pi\rho_3\)。于是容易把 \(e(-\xi\cdot z)\) 换成 \(1\)，所产生的误差至多 \(\frac{\delta^2}{512}\mathbb{P}_Z(\mathrm{Bohr}(S,\rho_2))\)（譬如），从而得到 \[ \begin{aligned} &\mathbb{E}_{w\in Z;\,z\in\mathrm{Bohr}(S',\rho_3)}1_{\mathrm{Bohr}(S,\rho_2)}(w+z)(f(w+z)-\delta)\big[2 + \mathrm{Re}\,e(-\xi\cdot w+\theta)\big]\\ &\qquad\ge \frac{3\delta^2}{512}\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho_2)). \end{aligned} \] 一个类似的论证（利用 \(\mathrm{Bohr}(S,\rho_2)\) 的正则性）允许我们把截断 \(1_{\mathrm{Bohr}(S,\rho_2)}(w+z)\) 换成 \(1_{\mathrm{Bohr}(S,\rho_2)}(w)\)，得到 \[ \mathbb{E}_{w\in Z;\,z\in\mathrm{Bohr}(S',\rho_3)}1_{\mathrm{Bohr}(S,\rho_2)}(w)(f(w+z)-\delta)\big[2 + \mathrm{Re}\,e(-\xi\cdot w+\theta)\big] \ge \frac{\delta^2}{256}\,\mathbb{P}_Z(\mathrm{Bohr}(S,\rho_2)), \] 我们把它改写为 \[ \mathbb{E}_{w\in\mathrm{Bohr}(S,\rho_2)}\big[2 + \mathrm{Re}\,e(-\xi\cdot w+\theta)\big]\Big(\mathbb{E}_{x\in w+\mathrm{Bohr}(S',\rho_3)}f(x) - \delta\Big) \ge \frac{\delta^2}{256}. \] 另一方面，由 (10.16) 及界 \(2+\mathrm{Re}\,e(-\xi\cdot w+\theta)\le3\)，左边被界为 \(3\cdot\frac{\delta^2}{2^{10}}\)，矛盾。♦

例：收尾的矛盾是怎么“撞”出来的 把最后两行对照着看（取 \(\delta\) 具体些便于感受量级）：
  1. 经过层层化简，我们证出左边 \(\ge\dfrac{\delta^2}{256}=\dfrac{4\delta^2}{2^{10}}\)。
  2. 但 \(\mathrm{Bohr}(S',\rho_3)\) 秩为 \(d+1\)、半径 \(\rho_3\ge(\delta/2d)^{31}\rho\)，正落在反设 (10.16) 的适用范围内，故每个 \(\mathbb{E}_{x\in w+\mathrm{Bohr}(S',\rho_3)}f(x)-\delta<\dfrac{\delta^2}{2^{10}}\)。
  3. 又因 \(0\le 2+\mathrm{Re}\,e(\cdots)\le3\)，左边 \(\le3\cdot\dfrac{\delta^2}{2^{10}}=\dfrac{3\delta^2}{2^{10}}\)。
  4. 于是 \(\dfrac{4\delta^2}{2^{10}}\le\text{左边}\le\dfrac{3\delta^2}{2^{10}}\)，即 \(4\le3\)，矛盾。
矛盾说明反设 (10.16) 不成立——必有某个秩 \(\le d+1\)、半径 \(\ge(\delta/2d)^{31}\rho\) 的 Bohr 集把密度抬到 \(\ge\delta+\delta^2/2^{10}\)，这正是命题 10.32 的结论。

习题

习题
  1. 10.4.1　证明 (10.13)。
  2. 10.4.2　在给定命题 10.28 与引理 10.29 的前提下，补全定理 10.27 的证明。
  3. 10.4.3　由定理 10.31 推出定理 10.30。
  4. 10.4.4　由命题 10.32 推出定理 10.31。（提示：使用一个约 \(O(1/\mathbb{E}_Z(f))\) 步的迭代论证，整个迭代过程中参数大小取 \(\delta=\Omega(\mathbb{E}_Z(f))\)、\(d=O(1/\mathbb{E}_Z(f))\)、\(\rho=\Omega\big(\mathbb{E}_Z(f)^{O(1/\mathbb{E}_Z(f))}\big)\)。）
三级改进（界越小越强） 10.3 节（密度增量+等差数列）：r₃ = O(N / loglog N)　每轮长度开平方，轮数≈loglog N 10.27 Heath-Brown–Szemerédi：r₃ = O(N / log^c N)　一次处理一批频率，长度仅缩 N^(1/(|S|+1)) 10.30 Roth–Bourgain：r₃ = O((loglog N / log N)·N)　全程用正则 Bohr 集，逼近傅里叶法极限
本节的逻辑链：把“长度账”掉得太快的等差数列，先升级为“批量频率”（多项式收缩），再升级为“正则 Bohr 集”（秩 +1、半径乘 \(\mathrm{poly}(\delta/d)\)），从而把上界一路压低。

返回 全书目录