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

10.2　小挠率情形The small torsion case

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

本节目标上一节我们用傅里叶分析得到了“没有三项等差数列的集合一定有线性偏差”这个结论，但它本身还不能直接推出矛盾。本节要做的，是把“有线性偏差”这条分析性质转化为一条更好用的结构性质——“在某个低一维的子空间陪集上密度变大”。靠这一步反复迭代（密度增量法），就能在结构最简单的群（\(p\)-挠群，即域 \(\mathbf F_p\) 上的向量空间）里证明 Roth 定理。本节还会把同样的思路推广到 Varnavides 型定理、以及随机子集中的 Roth 定理（转移原理）。

我们现在运用上述傅里叶分析方法与密度增量论证，来证明 Roth 定理的下述简单特例。

命题 10.12（\(p\)-挠群上的 Roth 定理）[248] 设 \(Z\) 是某个奇素数 \(p\) 的 \(p\)-挠群（即对一切 \(x\in Z\) 都有 \(px=0\)）。则 \[ r_3(Z) < \frac{3}{\log_p|Z|}\,|Z|. \tag{10.12*}\]
先把符号读懂
在 \(\mathbf F_3^2\)（9 个点）中，一条“线”就是一个三项等差数列 \(x\) \(x+d\) \(x+2d\)
红色三点共线：\(x,\,x+d,\,x+2d\) 恰好是一个三项等差数列。一个不含任何这种“线”的集合（capset），其大小就被 \(r_3\) 度量。
注记 10.13 定义无线集（capset）为向量空间 \(\mathbf Z_3^n\) 中不含任何线的子集。那么上述命题表明：无线集的密度小于 \(3/n\)。令人惊讶的是，这个简单的上界（除去改进常数 \(3\) 之外）本质上仍是已知最好的结果；在相反方向上，\(\mathbf Z_3^n\) 中无线集密度的已知最好下界是 \((0.724581\ldots+o(1))^n\)，见 [75]。把上界改进到 \(o(1/n)\)，或把下界改进到 \((1-o(1))^n\)，都将是我们对 Erdős–Turán 猜想理解上的重大进展。
注记 10.14 一个有用的启发式是：循环群 \(Z_N\)（或区间 \([1,N]\)）在 \(N\sim p^n\) 时，其行为大致应当像 \(p\)-挠群 \(\mathbf Z_p^n\)。利用这一启发式与上述命题，人们会期待 \(r_3([1,N])\) 与 \(r_3(Z_N)\) 应为 \(O(N/\log N)\)。这样的界在 \(k=3\) 的情形本质上等价于 Erdős–Turán 猜想（猜想 10.6）。遗憾的是，上述论证的直接类比只给出 \(r_3([1,N]),\,r_3(Z_N)=O\!\left(N\frac{\log\log N}{\log N}\right)\)，见定理 10.30。一般而言，\(p\)-挠群由于其在域 \(\mathbf F_p\) 上的向量空间结构，比一般群稍易分析。要把 \(p\)-挠的论证推广到更一般的情形，需要一些额外工具，特别是 Bohr 集理论。

我们现在开始证明命题 10.12。可以把 \(Z\) 视为域 \(\mathbf F_p\) 上的向量空间。反设我们能找到密度 \(\mathbf P_Z(A)\ge\dfrac{3}{\log_p|Z|}\) 的集合 \(A\subset Z\)，使其不含长度为 \(3\) 的真等差数列。由推论 10.10 我们已经知道 \(A\) 必定表现出线性偏差，即 \(\|A\|_u\) 较大。为了利用这一事实，我们需要把线性偏差转化为更有用的结构性质。这一转化由下述引理完成。

引理 10.15（非一致性蕴含密度增量） 设 \(Z\) 是有限素数阶域 \(\mathbf F_p\) 上的向量空间，又设 \(f:Z\to\mathbf R\) 是均值为零的函数，\(\mathbf E_Z(f)=0\)。则存在 \(Z\) 在 \(\mathbf F_p\) 上余维数为 \(1\) 的子空间 \(Z'\)，以及一点 \(x_0\in Z\)，使得 \[ \mathbf E_{x\in x_0+Z'}\,f(x)\ \ge\ \tfrac12\,\|f\|_{u^2(Z)}. \]
这条引理在说什么
\(Z=\mathbf F_p^n\) 被余维 1 子空间 \(Z'\) 切成 \(p\) 张平行薄片（陪集） \(0+Z'\) \(\cdots\) \(x_0+Z'\) \(\cdots\) 这一张薄片上 \(f\) 的平均 \(\ge\tfrac12\|f\|_{u^2}\)
引理 10.15：偏差大 \(\Rightarrow\) 至少有一张超平面薄片（陪集）上 \(f\) 的平均值偏高。这正是“密度增量”要落脚的地方。
证明. 不失一般性，取 \(Z=\mathbf F_p^n\)，并采用例 4.2 中的双线性型 \(\xi\cdot y\)。 由 \(\|f\|_{u^2(Z)}\) 的定义以及均值为零的假设，我们可以找到非零的 \(\xi\in Z\) 与相位 \(\theta\in\mathbf R/\mathbf Z\)，使得 \[ \operatorname{Re}\,\mathbf E_{y\in Z}\,f(y)\,e(\xi\cdot y+\theta)=\|f\|_{u^2(Z)}, \] 其中 \(e\) 是由式 (4.1) 定义的指数映射。再次利用均值为零的假设，我们得到 \[ \operatorname{Re}\,\mathbf E_{y\in Z}\,f(y)\bigl(e(\xi\cdot y+\theta)+1\bigr)=\|f\|_{u^2(Z)}. \] 令 \(Z':=\{\xi\}^{\perp}=\{x\in Z:\ \xi\cdot x=0\}\) 为 \(\xi\) 的正交补；则 \(Z'\) 是 \(Z\) 的余维数为 \(1\) 的子空间，而函数 \(y\mapsto e(\xi\cdot y+\theta)+1\) 在 \(Z'\) 的每个陪集上取常值。对每个 \(x\in Z'\) 作变量替换 \(y=x_0+x\)，再对 \(x_0\) 取平均，我们得到 \[ \operatorname{Re}\,\mathbf E_{y\in Z}\,f(y)\bigl(e(\xi\cdot y+\theta)+1\bigr)=\mathbf E_{x_0\in Z}\Bigl(\mathbf E_{x\in x_0+Z'}\,f(x)\Bigr)\operatorname{Re}\bigl(e(\xi\cdot x_0+\theta)+1\bigr). \] 由抽屉原理，必定存在某个陪集 \(x_0+Z'\)，使得 \[ \Bigl(\mathbf E_{x\in x_0+Z'}\,f(x)\Bigr)\operatorname{Re}\bigl(e(\xi\cdot x_0+\theta)+1\bigr)\ \ge\ \|f\|_{u^2(Z)}. \] 由于 \(\operatorname{Re}\bigl(e(\xi\cdot x_0+\theta)+1\bigr)\le 2\)，结论得证。♦
  1. 抓住偏差方向。 偏差量 \(\|f\|_{u^2}\) 的定义保证：有一个非零频率 \(\xi\) 与相位 \(\theta\)，让加权平均 \(\operatorname{Re}\,\mathbf E_y f(y)e(\xi\cdot y+\theta)\) 恰好等于这个偏差量。这是“偏差”最原始的含义——\(f\) 与某个线性波 \(e(\xi\cdot y+\theta)\) 有非零的相关。
  2. 加上常数 1。 因为 \(\mathbf E_Z(f)=0\)，给括号里添一个常数 \(1\) 不改变平均值（\(\mathbf E_y f(y)\cdot 1=0\)），于是把 \(e(\cdots)\) 换成 \(e(\cdots)+1\)，等式照样成立。这一步的目的见注记 10.16：让权重非负。
  3. 权重在薄片上是常数。 当 \(x\) 在 \(Z'=\{\xi\}^\perp\) 内变动时 \(\xi\cdot x=0\)，所以 \(e(\xi\cdot y+\theta)\) 只依赖于 \(y\) 落在哪张薄片 \(x_0+Z'\) 上。于是整张薄片共用同一个权重 \(\operatorname{Re}(e(\xi\cdot x_0+\theta)+1)\)。
  4. 把平均拆成“先片内、后片间”。 先在每张薄片内对 \(f\) 求平均，得到片平均 \(\mathbf E_{x\in x_0+Z'}f(x)\)；再带着非负权重对各薄片求平均，总和仍等于 \(\|f\|_{u^2}\)。
  5. 抽屉原理。 一堆非负权重乘以片平均，加起来 \(\ge\|f\|_{u^2}\)，那必有一项 \(\ge\|f\|_{u^2}\)。由于权重 \(\le 2\)，对应的片平均就 \(\ge\tfrac12\|f\|_{u^2}\)。♦
注记 10.16 给 \(e(\xi\cdot y+\theta)\) 加上 \(1\) 的原因，是为了确保 \(\operatorname{Re}\bigl(e(\xi\cdot y+\theta)+1\bigr)\) 非负。我们在本章中将反复使用这一技巧。

我们现在可以运用 Roth 的密度增量论证来证明命题 10.12。

定理 10.12 之证明. 由推论 3.8，我们可以取 \(Z=\mathbf F_p^n\)，配以例 4.2 中的标准双线性型。我们对 \(n\) 作归纳。当 \(n\le 3\) 时结论平凡，故设 \(n>3\)。反设 \(r_3(\mathbf F_p^n)\ge 3/n\)（按密度），则可找到密度 \(\mathbf P_Z(A)\ge 3/n\) 的集合 \(A\subset Z\)，它不含长度为 \(3\) 的真等差数列。 于是由引理 10.15（对 \(f:=1_A-\mathbf P_Z(A)\) 应用），存在 \(Z\) 的余维数为一的陪集 \(x_0+Z'\)，使得 \[ \mathbf P_{x_0+Z'}(A)\ \ge\ \mathbf P_Z(A)+\tfrac12\,\|A\|_u. \] 应用推论 10.10，我们得到 \[ \mathbf P_{x_0+Z'}(A)\ \ge\ \frac{3}{n}+\frac12\!\left(\frac{9}{n^2}-\frac{1}{|Z|}\right)\ \ge\ \frac{3}{n}+\frac{4}{n^2}\ \ge\ \frac{3}{n-1}, \] 这里用到了 \(|Z|=p^n\ge n^2\) 与 \(n\ge 3\)。由归纳假设，集合 \((A-x_0)\cap Z'\) 因而含有一个长度为 \(3\) 的真等差数列，从而 \(A\) 也含有，这就给出了所需的矛盾。♦
密度增量为什么能赢核心是一场“维数换密度”的拔河：每迭代一次，维数 \(n\) 减少 \(1\)（落到余维 1 的子空间 \(Z'\cong\mathbf F_p^{n-1}\)），而密度从 \(\tfrac{3}{n}\) 升到 \(\ge\tfrac{3}{n-1}\)。关键不等式拆开看：
  1. 推论 10.10 说“无三项等差数列 \(\Rightarrow\) 偏差大”，给出 \(\|A\|_u\ge \mathbf P_Z(A)^2-\tfrac{1}{|Z|}\ge \tfrac{9}{n^2}-\tfrac{1}{|Z|}\)。
  2. 引理 10.15 把这份偏差兑换成片上密度增量 \(\tfrac12\|A\|_u\)，于是 \(\mathbf P_{x_0+Z'}(A)\ge \tfrac3n+\tfrac12\bigl(\tfrac{9}{n^2}-\tfrac{1}{|Z|}\bigr)\)。
  3. 因 \(|Z|=p^n\ge n^2\)，那个 \(-\tfrac{1}{2|Z|}\) 至多吃掉 \(\tfrac{1}{2n^2}\)，剩下 \(\ge\tfrac3n+\tfrac{4}{n^2}\)。
  4. 再核对 \(\tfrac3n+\tfrac{4}{n^2}\ge\tfrac{3}{n-1}\)：两边通分等价于 \(n^2-4n\ge0\)，即 \(n\ge4\)（正是 \(n>3\)）。于是“升一级密度、降一维”的循环可以一直进行，直到维数掉到 \(n\le3\) 的平凡情形，矛盾出现。
密度增量迭代：每步维数 −1，密度 \(\tfrac3n\to\tfrac{3}{n-1}\) 维数 n（向左减小） \(\tfrac{3}{n}\) \(\tfrac{3}{n-1}\) \(\tfrac{3}{n-2}\) \(\cdots\) \(n\le3\) 矛盾
密度单调上升而维数有限，迭代必在有限步内把维数压到 \(n\le3\)，那里“高密度无三项等差数列集合”不存在，矛盾产生。

一个非常类似的论证也能在此情形下确立 Varnavides 定理：

命题 10.17（\(p\)-挠群上的 Varnavides 定理） 设 \(Z\) 是某个奇素数 \(p\) 的 \(p\)-挠群，又设 \(f:Z\to\mathbf R^+\) 满足对一切 \(x\in Z\) 有 \(0\le f(x)\le 1\)。则 \[ \Lambda_3(f,f,f)\ \ge\ p^{-6/\mathbf E_Z(f)}. \]
Varnavides 型结论的意思命题 10.12 只说“密度够高就至少有一个三项等差数列”。Varnavides 型结论更强：它给出三项等差数列的数量下界。这里 \(\Lambda_3(f,f,f):=\mathbf E_{x,d\in Z}\,f(x)f(x+d)f(x+2d)\) 是计数三项等差数列的三线性平均；取 \(f=1_A\) 时，它就正比于 \(A\) 中三项等差数列（含退化的）的个数。结论说：只要平均密度 \(\mathbf E_Z(f)\) 为正，这个计数就被一个仅依赖密度的正数 \(p^{-6/\mathbf E_Z(f)}\) 从下方挡住，不可能太小。
证明. 我们对 \(n:=3/\mathbf E_Z(f)\) 作归纳。当 \(n\le 3\) 时结论平凡，故设 \(n>3\) 且对 \(n-1\) 已证。再次把 \(Z\) 视为 \(\mathbf F_p\) 上配有标准双线性型的向量空间。把 \(f\) 写成 \[ f=f_{U^\perp}+f_U,\qquad f_{U^\perp}:=\mathbf E_Z(f),\quad f_U:=f-f_{U^\perp}. \] 注意 \[ \Lambda_3(f_{U^\perp},f_{U^\perp},f_{U^\perp})=\mathbf E_Z(f)^3. \] 若已有 \[ \Lambda_3(f,f,f)\ \ge\ \mathbf E_Z(f)^3/9 \] （比方说），则证毕（因为 \(\mathbf E_Z(f)^3/9\ge p^{-6/\mathbf E_Z(f)}\)），故我们不妨改设 \[ \bigl|\Lambda_3(f,f,f)-\Lambda_3(f_{U^\perp},f_{U^\perp},f_{U^\perp})\bigr|\ \ge\ 8\,\mathbf E_Z(f)^3/9. \] 我们可以把左端改写为三项的伸缩和（telescoping sum）： \[ \bigl|\Lambda_3(f_U,f,f)+\Lambda_3(f_{U^\perp},f_U,f)+\Lambda_3(f_{U^\perp},f_{U^\perp},f_U)\bigr|. \] 由定义可见，\(f_U\) 均值为零，而 \(f_{U^\perp}\) 为常数。于是容易验证后两项消失。从而 \[ |\Lambda_3(f_U,f,f)|\ \ge\ 8\,\mathbf E_Z(f)^3/9. \] 由于 \(f\) 以 \(1\) 为界，我们有 \[ \|f\|_{L^2(Z)}^2=\mathbf E_Z(f^2)\le \mathbf E_Z(f), \] 因而由命题 10.11 得到 \[ \|f_U\|_{u^2(Z)}\ \ge\ 4\,\mathbf E_Z(f)^2/9. \] 应用引理 10.15，我们可以找到 \(Z\) 的余维数为 \(1\) 的子空间 \(Z'\)，使得 \[ \mathbf E_{x\in x_0+Z'}\,f(x)\ \ge\ \mathbf E_Z(f)+4\,\mathbf E_Z(f)^2/9. \] 若令 \(g:Z'\to\mathbf R\) 为函数 \(g(x):=f(x+x_0)\)，则 \(g\) 取值于 \(0\) 与 \(1\) 之间，且 \[ \mathbf E_{Z'}(g)\ \ge\ \mathbf E_Z(f)+4\,\mathbf E_Z(f)^2/9; \] 这尤其迫使 \(\mathbf E_Z(f)\le 3/4\)，进而由初等代数得到 \[ \frac{6}{\mathbf E_{Z'}(g)}\ \le\ \frac{6}{\mathbf E_Z(f)}-2. \] 于是由归纳假设有 \[ \Lambda_3(g,g,g)\ \ge\ p^{2}\,p^{-6/\mathbf E_Z(f)}, \] 而由 \(g\) 的定义与 \(f\) 的非负性，我们有 \(\Lambda_3(f,f,f)\ge p^{-2}\,\Lambda_3(g,g,g)\)。这就完成了归纳。♦
  1. 分解 \(f\)。 把 \(f\) 拆成常数部分 \(f_{U^\perp}=\mathbf E_Z(f)\)（“反一致”主项，即平均密度）与零均值的涨落 \(f_U=f-\mathbf E_Z(f)\)（“一致”部分）。常数部分自身贡献的三项等差数列计数恰为 \(\mathbf E_Z(f)^3\)。
  2. 两种可能。 要么 \(\Lambda_3(f,f,f)\) 已经够大（\(\ge\mathbf E_Z(f)^3/9\)），直接收工；要么它与主项相差很大，说明涨落 \(f_U\) 起了大作用。
  3. 消项。 把差 \(\Lambda_3(f,f,f)-\Lambda_3(f_{U^\perp},f_{U^\perp},f_{U^\perp})\) 用伸缩和拆成三项。凡是“常数 + 常数 + 零均值涨落”的项都为零（常数在三项等差数列平均下与零均值函数解耦），只剩 \(\Lambda_3(f_U,f,f)\) 一项较大。
  4. 大计数 \(\Rightarrow\) 大偏差。 因为 \(\Lambda_3(f_U,f,f)\) 大、且 \(f\le1\)，命题 10.11 把它兑换为 \(f_U\) 的偏差下界 \(\|f_U\|_{u^2}\ge 4\mathbf E_Z(f)^2/9\)。
  5. 密度增量 + 降维归纳。 引理 10.15 把偏差变成某张薄片上的密度抬升：限制到 \(Z'\) 上的 \(g\) 密度涨到 \(\ge\mathbf E_Z(f)+\tfrac49\mathbf E_Z(f)^2\)。代数核对 \(\tfrac{6}{\mathbf E_{Z'}(g)}\le\tfrac{6}{\mathbf E_Z(f)}-2\)，于是归纳给出 \(g\) 的计数 \(\ge p^2 p^{-6/\mathbf E_Z(f)}\)；最后用 \(Z'\) 是 \(Z\) 的 \(p\) 倍指数子空间这一事实，把 \(g\) 的计数折回 \(f\) 的计数（系数 \(p^{-2}\)），刚好抵消那个 \(p^2\)。♦

一个引人注目的现象是：上述类型的下界，即使把有界性条件 \(f\le 1\) 换成更一般的条件 \(f\le\nu\)，只要包络权 \(\nu\) 足够伪随机，下界依然成立。这一现象（本质上最早见于 [212]、[147]）在 [158] 中被表述得更为明确，那里提出了一条转移原理。该原理本是为研究任意长度 \(k\) 的等差数列、并以遍历论语言表述的；但在 \(k=3\) 时存在一条平行的傅里叶分析版本，并在 [159] 中得到发展。我们下面在 \(p\)-挠群的随机子集这一特殊语境中，给出该结果的一个简化表述。具体地，我们将证明：

定理 10.18（挠群随机子集中的 Roth 定理） 设 \(Z\) 是某个奇素数 \(p\) 的有限 \(p\)-挠群，设 \(|Z|^{-0.01}\le\tau\le1\)，又设 \(B\) 是 \(Z\) 的随机子集，事件 \(\{x\in B\}\) 相互独立、概率 \(\mathbf P(x\in B)=\tau\)。则以概率 \(1-o_{|Z|\to\infty;\,p}(1)\) 有 \(r_3(B)=o_{|Z|\to\infty;\,p}(|B|)\)。
注记 10.19 本定理的要点在于：它允许我们在密度低至 \(|Z|^{-0.01}\) 的 \(Z\) 的子集中探测等差数列——这远超命题 10.12 的能力范围——前提是这些集合相对于一个随机集合具有较大的相对密度。下面给出的证明经过修改，可用来确立：素数集中任意正相对密度的子集都含有无穷多个长度为 \(3\) 的等差数列；见 [147]、[159]。其要点在于：素数被包含在一个“殆素数”集合中，后者非常一致（或“伪随机”），从而在某种傅里叶分析意义下表现得极像一个随机集合。把傅里叶分析方法换成遍历论方法（并把线性一致性换成 Gowers 一致性的概念——后者可由 Goldston 与 Yıldırım 的某些数论论证对殆素数得到），这一结果随后被推广到覆盖任意长度的等差数列；见 [158]。注意 [212] 中的原始证明依赖的是 Szemerédi 正则性引理（下面的引理 10.42），而非傅里叶分析方法（其代价是较弱的界）；另一方面，它适用于任意奇阶的有限加性群 \(Z\)，并允许密度 \(\tau\) 逼近最优值 \(|Z|^{-1/2}\)（习题 10.2.3）。

我们现在开始证明定理 10.18。我们需要命题 10.17 的如下推广，其中 \(f\) 不再以 \(1\) 为界，而是以一个“伪随机测度”为界，并且还满足某些傅里叶界。

定理 10.20 [159] 设 \(Z\) 是某个奇素数 \(p\) 的有限 \(p\)-挠群，又设 \(f:Z\to\mathbf R_{\ge0}\) 是非负函数，满足 \[ \|\hat f\|_{l^q(Z)}\le M \tag{10.7}\] 对某个 \(2
把“界 \(f\le1\)”换成“界 \(f\le\nu\)”意味着什么命题 10.17 要求函数被常数 \(1\) 卡住。但研究素数这类稀疏集合时，做不到这一点——它们密度趋于 \(0\)。补救办法是先把 \(f\) 嵌进一个“包络测度” \(\nu\)（满足 \(f\le\nu\)），只要 \(\nu\) 足够伪随机（它的非零频率傅里叶系数都很小，即 (10.8)），就能把命题 10.17 的下界几乎原样搬过来。代价是右端多出一个误差项 \(-7M^3\log_p^{1-3/q}(1/\eta)\)，当 \(\eta\) 极小时这个误差可忽略。\(\eta=0\)（即 \(\nu\equiv1\)）时误差为零，正好退化回命题 10.17。
证明. 我们可设 \(Z\) 是 \(\mathbf F_p\) 上配有例 4.2 双线性型的向量空间。令 \(\alpha:=M/\log_p^{1/q}\dfrac1\eta\)。回忆 \(f\) 的谱 \(\operatorname{Spec}_\alpha(f)\subseteq Z\)，定义为 \[ \operatorname{Spec}_\alpha(f):=\{\xi\in Z:\ |\hat f(\xi)|\ge\alpha\}. \] 由假设 (10.7) 与 Chebyshev 不等式，我们有 \[ |\operatorname{Spec}_\alpha(f)|\le M^q/\alpha^q=\log_p\frac1\eta. \tag{10.9}\] 于是若令 \(V=\operatorname{Spec}_\alpha(f)^\perp\) 为 \(\operatorname{Spec}_\alpha(f)\) 的正交补，则 \(V\) 是 \(Z\) 的子空间，且 \[ |V^\perp|\le p^{|\operatorname{Spec}_\alpha(f)|}\le\frac1\eta. \tag{10.10}\] 我们把 \(f\) 分裂为 \(f=f_U+f_{U^\perp}\)，其中 \(f_U:=f-f*\dfrac{1_V}{\mathbf P_Z(V)}\) 是 \(f\) 的“一致”分量，而 \(f_{U^\perp}:=f*\dfrac{1_V}{\mathbf P_Z(V)}\) 是“反一致”分量。这使我们能把 \(\Lambda_3(f,f,f)\) 分裂为八项： \[ \Lambda_3(f,f,f)=\Lambda_3(f_U,f_U,f_U)+\cdots+\Lambda_3(f_{U^\perp},f_{U^\perp},f_U)+\Lambda_3(f_{U^\perp},f_{U^\perp},f_{U^\perp}). \] 思路是用命题 10.17 对最后一项取下界，用 (10.6) 对其余七项取量级界。 我们先控制 \(f_{U^\perp}\)。由于 \(f\) 逐点被 \(\nu\) 所界，运用 Poisson 求和公式（习题 4.1.7）以及 (10.10)、(10.8)，我们得到 \[ f_{U^\perp}(x)=f*\frac{1_V}{\mathbf P_Z(V)}(x)\le \nu*\frac{1_V}{\mathbf P_Z(V)}(x)=\sum_{\xi\in V^\perp}\hat\nu(\xi)e(\xi\cdot x)\le 1+|V^\perp|\sup_{\xi\in V^\perp\setminus0}|\hat\nu(\xi)|\le 1+\frac1\eta\cdot\eta=2. \] 我们因而看到 \(f_{U^\perp}\) 上方以 \(2\) 为界。它也是非负的，且由 (4.10) 有 \(\mathbf E_Z(f_{U^\perp})=\mathbf E_Z(f)\)。于是由命题 10.17（对 \(f_{U^\perp}/2\) 应用）得 \[ \Lambda_3(f_{U^\perp},f_{U^\perp},f_{U^\perp})\ \ge\ 8\,p^{-12/\mathbf E_Z(f)}. \] 现在考虑其余各项。再次由 Poisson 求和公式，我们有 \[ \hat f_{U^\perp}=\hat f\,1_{V^\perp}\qquad\text{与}\qquad \hat f_U=\hat f\,(1-1_{V^\perp}). \] 特别地有 \[ \|\hat f_U\|_{l^q(Z)},\ \|\hat f_{U^\perp}\|_{l^q(Z)}\le M. \] 此外，由于 \(V^\perp\) 包含 \(\operatorname{Spec}_\alpha(f)\)，我们看到 \[ \sup_{\xi\in Z}|\hat f_U(\xi)|\le\alpha. \] 应用 (10.6) 与 Hölder 不等式，我们得到 \[ |\Lambda_3(f_U,f_{U^\perp},f_{U^\perp})|\le M^q\alpha^{3-q}=M^3\log_p^{\,1-3/q}\frac1\eta, \] 对其余六个待估的 \(\Lambda_3(\cdot)\) 表达式也类似。结论得证。♦
把 \(f\) 沿“谱”分成两块 频率 \(\xi\) \(|\hat f(\xi)|\) 阈值 \(\alpha\) 谱 \(\operatorname{Spec}_\alpha(f)\)：归入反一致主项 \(f_{U^\perp}\) 阈值以下的小频率：归入一致小项 \(f_U\)（可忽略）
定理 10.20 的几何：大于阈值 \(\alpha\) 的少数大频率（谱）拼成可控的反一致主项 \(f_{U^\perp}\)；其余小频率拼成傅里叶意义下很小的一致项 \(f_U\)，对三项等差数列计数的贡献可忽略。
注记 10.21 上述转移论证的策略是：找出 \(Z\) 的一个相当粗的划分（此处即 \(V\) 的诸陪集）来对其取平均，从而造出 \(f\) 的一个性质良好的逼近 \(f_{U^\perp}\)，而 \(f\) 与 \(f_{U^\perp}\) 之间的误差 \(f_U\)（在傅里叶意义下）一致到可以忽略不计。这一理念在 [150] 中被定量地展开，那里得到了 Szemerédi 正则性引理的一个算术版本。

本推论中的假设 (10.7) 看似限制性很强，但在许多情形下，人们可以通过利用 \(\nu\) 的伪随机性质来控制 \(\hat f\) 的 \(l^q\) 范数，或至少控制 \(f\) 的谱 \(\operatorname{Spec}_\alpha(f)\)。例如，有：

引理 10.22（Tomas–Stein 论证） 设 \(Z\) 是有限加性群，又设 \(\nu:Z\to\mathbf R^+\) 与 \(f:Z\to\mathbf C\) 满足 (10.8) 对某个 \(\eta\) 成立，且对一切 \(x\in Z\) 有 \(|f(x)|\le\nu(x)\)。对任意 \(\alpha>0\)，令 \(\operatorname{Spec}_\alpha(f):=\{\xi\in Z:\ |\hat f(\xi)|\ge\alpha\}\)。则 \[ |\operatorname{Spec}_\alpha(f)|\le 4/\alpha^2 \] 对一切 \(\alpha\ge2\eta^{1/2}\) 成立。
注记 10.23 此估计应与 (4.37) 相比较；要点在于这里并未假设 \(f\) 有任何 \(L^2\) 界，否则此类估计将由 Plancherel 定理直接得出。这里所用的正交性论证，在傅里叶变换的限制理论中起着根本作用，综述见例如 [356]。它也与解析数论中的大筛法不等式密切相关。
证明. 对每个 \(\xi\in\operatorname{Spec}_\alpha(f)\)，令 \(c(\xi):=\operatorname{sgn}(\hat f(\xi))\)。则有 \[ \sum_{\xi\in\operatorname{Spec}_\alpha(f)}\hat f(\xi)\overline{c(\xi)}=\sum_{\xi\in\operatorname{Spec}_\alpha(f)}|\hat f(\xi)|\ \ge\ \alpha|\operatorname{Spec}_\alpha(f)|. \] 但左端可改写为 \[ \mathbf E_Z\Bigl(f\,\overline{\textstyle\sum_{\xi\in\operatorname{Spec}_\alpha(f)}c(\xi)e_\xi}\Bigr). \] 由于 \(|f|\le\nu\)，我们可用 Cauchy–Schwarz 不等式而得 \[ \alpha|\operatorname{Spec}_\alpha(f)|\le \mathbf E_Z(\nu)^{1/2}\,\mathbf E_Z\Bigl(\nu\,\bigl|\textstyle\sum_{\xi\in\operatorname{Spec}_\alpha(f)}c(\xi)e_\xi\bigr|^2\Bigr)^{1/2}. \] 由于 \(\mathbf E_Z(\nu)=\hat\nu(0)\le1+\eta\le2\)，我们因而推出 \[ \mathbf E_Z\Bigl(\nu\,\bigl|\textstyle\sum_{\xi\in\operatorname{Spec}_\alpha(f)}c(\xi)e_\xi\bigr|^2\Bigr)\ \ge\ \tfrac12\,\alpha^2|\operatorname{Spec}_\alpha(f)|^2. \] 我们可以把左端展开为 \[ \sum_{\xi,\xi'\in\operatorname{Spec}_\alpha(f)}c(\xi)\overline{c(\xi')}\,\mathbf E_Z(\nu\,e_\xi\overline{e_{\xi'}})=\sum_{\xi,\xi'\in\operatorname{Spec}_\alpha(f)}c(\xi)\overline{c(\xi')}\,\hat\nu(\xi-\xi'). \] 但由于 \(|c(\xi)|=1\) 且 \(|\hat\nu(\xi-\xi')|\le\eta+\mathbf I(\xi-\xi'=0)\)，我们推出 \[ \tfrac12\,\alpha^2|\operatorname{Spec}_\alpha(f)|^2\le \sum_{\xi,\xi'\in\operatorname{Spec}_\alpha(f)}\bigl(\eta+\mathbf I(\xi-\xi'=0)\bigr)\le \eta|\operatorname{Spec}_\alpha(f)|^2+|\operatorname{Spec}_\alpha(f)|. \] 由于 \(\alpha\ge2\eta^{1/2}\)，我们有 \(\eta|\operatorname{Spec}_\alpha(f)|^2\le\tfrac14\alpha^2|\operatorname{Spec}_\alpha(f)|^2\)，结论随之得证。♦
  1. 把谱里的频率“对齐相位”。 给每个大频率 \(\xi\) 配一个单位复数 \(c(\xi)=\operatorname{sgn}(\hat f(\xi))\)，让 \(\hat f(\xi)\overline{c(\xi)}=|\hat f(\xi)|\) 变成正实数。对谱求和得到下界 \(\ge\alpha\cdot|\operatorname{Spec}_\alpha(f)|\)。
  2. 翻译成物理空间的内积。 这个和等于 \(f\) 与“纯频率叠加” \(\sum c(\xi)e_\xi\) 的内积。
  3. 用 \(|f|\le\nu\) 加 Cauchy–Schwarz。 既然没有 \(f\) 的 \(L^2\) 界，就借助 \(\nu\) 当权重，把内积上界化成 \(\mathbf E_Z(\nu)^{1/2}\) 乘以一个加权 \(L^2\) 量。
  4. 展开加权 \(L^2\) 量。 平方展开后出现 \(\hat\nu(\xi-\xi')\)。伪随机性 (10.8) 说：非对角项 \((\xi\neq\xi')\) 都 \(\le\eta\)，对角项 \((\xi=\xi')\) 贡献 \(1\)。于是该量 \(\le\eta|\operatorname{Spec}|^2+|\operatorname{Spec}|\)。
  5. 门槛 \(\alpha\ge2\eta^{1/2}\) 吃掉非对角项。 此时 \(\eta|\operatorname{Spec}|^2\) 至多是 \(\tfrac14\alpha^2|\operatorname{Spec}|^2\)，与左端 \(\tfrac12\alpha^2|\operatorname{Spec}|^2\) 对消后只剩 \(|\operatorname{Spec}|\) 一项主导，整理即得 \(|\operatorname{Spec}_\alpha(f)|\le4/\alpha^2\)。♦
伪随机 \(\nu\)：对角项 (1) 主导，非对角项 (\(\le\eta\)) 可忽略 对角 \(\xi=\xi'\)：贡献 1 非对角 \(\xi\neq\xi'\)：每格 \(\le\eta\)（浅色，被门槛压住）
把 \(\sum_{\xi,\xi'}\hat\nu(\xi-\xi')\) 看作一张表：对角线是结实的 1，其余格子在伪随机性下都 \(\le\eta\)。门槛 \(\alpha\ge2\eta^{1/2}\) 保证非对角总和翻不起浪，于是谱不可能太大。

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

定理 10.18 之证明. 我们可以假设 \(|Z|\) 充分大（依赖于 \(\delta,p\)），因为否则结论是空洞的。我们将把 \(o_{|Z|\to\infty;\,p}(1)\) 简记为 \(o(1)\)。由推论 1.9，我们有 \(\mathbf P_Z(B)=\tau+O(|Z|^{-1/5})\)（比方说）以概率 \(1-o(1)\) 成立；特别地 \(B\) 非空。又若令 \(\nu:=1_B/\tau\)，则由引理 4.16（把其中的 \(A\) 换成 \(Z\)）我们有 \[ \sup_{\xi\in Z\setminus0}|\hat\nu(\xi)|=O\!\left(|Z|^{-1/5}\right) \] 同样以概率 \(1-o(1)\) 成立。将此与我们对 \(\mathbf P_Z(B)\) 的密度界结合，我们因而有 \[ \sup_{\xi\in Z}|\hat\nu(\xi)-\mathbf I(\xi=0)|=O\!\left(|Z|^{-1/5}\right) \tag{10.11}\] 以概率 \(1-o(1)\) 成立。今后我们将在这些事件上取条件。 设 \(\delta=\delta(|Z|,p)<1\) 是一个随 \(|Z|\to\infty\) 非常缓慢地衰减到零的小量（即 \(\delta=o(1)\)）；只需证明：当 \(\delta\) 衰减得足够缓慢、且在前述事件上取条件时，\(B\) 的每个相对密度 \(|A|/|B|\ge\delta\) 的子集 \(A\) 都含有一个长度为 \(3\) 的真等差数列。

证明思路收束（本节到此为止）本节的 PDF 在此处中止（论证在后续小节继续）。但脉络已经清楚：
  1. 造伪随机包络。 取 \(\nu=1_B/\tau\)。随机集合 \(B\) 的傅里叶系数（除零频外）以高概率极小，故 \(\nu\) 满足伪随机性 (10.11)，其中 \(\eta=O(|Z|^{-1/5})\) 微乎其微。
  2. 套用转移定理。 对 \(B\) 的高相对密度子集 \(A\)，令 \(f=1_A\)，它满足 \(f\le\nu\)。再用引理 10.22（Tomas–Stein）控制谱、从而验证 (10.7)。
  3. 得三项等差数列计数下界。 定理 10.20 给出 \(\Lambda_3(f,f,f)\ge 8p^{-12/\mathbf E_Z(f)}-\)（极小误差）。由于误差项含 \(\eta\) 极小，下界为正，于是 \(A\) 中三项等差数列的数量正比于一个正常数——多到足以保证存在真等差数列（退化项数量可忽略）。这就把命题 10.17 那种“稠密集合里必有许多三项等差数列”的结论，转移到了稀疏但伪随机背景下的相对稠密集合上。

返回 全书目录