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

11.4　一致性的软障碍Soft obstructions to uniformity

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

本节目标第 11.2–11.3 节里 Gowers 用“硬障碍”（多项式相位之类看得见摸得着的结构）来证明 Szemerédi 定理，代价是要证一个很强、很难的逆定理。本节给出一条替代路线：把“硬障碍”换成“软障碍”——只需知道存在某个有结构的函数与 \(f\) 相关，不必把它写成具体公式。这样逆定理变得几乎免费（见引理 11.14），但代价转移到了最后一步：要把“密度递增”换成“能量递增”，并为软障碍证一条很难的回归性定理（要用到 van der Waerden 定理）。本节就是把这条路线上的工具——对偶函数与一致殆周期范数——一件件搭起来。

在前两节里我们描述了 Gowers 证明 Szemerédi 定理的方法。该论证有三个主要组成部分。第一，是广义 von Neumann 定理 (11.8)，它（除别的之外）表明：只要 \(f-\mathbb{E}_Z(f)\) 在 \(k-2\) 阶意义下足够 Gowers 一致，就可以用 \(\mathbb{E}_Z(f)^k\) 来近似 \(\Lambda_k(f,\dots,f)\)。第二，是逆定理，它蕴含：若 \(f-\mathbb{E}_Z(f)\) 不是 \(k-2\) 阶 Gowers 一致的，则 \(f\) 上就有足够多的结构，足以推出 \(f\) 在 \(Z\) 的某个子空间或子级数上有密度递增。最后，是标准的密度递增论证，它把前两条观察反复迭代，从而完成 Szemerédi 定理的证明。

上述三个组成部分中，第二个是迄今为止最难的。原因在于：这条进路需要一种相当强的逆定理，特别是要求人们给出相当“具体”或“硬”的、阻碍 Gowers 一致性的障碍物，才能得出所要的密度递增。

然而存在一条替代进路，它与 10.5 节给出的有限化遍历论证类似，所需的、阻碍 Gowers 一致性的障碍物要“软”得多——所谓“软”，是指这些障碍物并不像（比方说）多项式相位函数那样以如此显式的形式呈现。这使得论证的第二阶段极大地简化了。不过，现在人们必须把论证的第三阶段弄得更复杂：用能量递增论证替换密度递增论证，再为这些软障碍建立某种回归性结果。这最后一步现在变得相当困难，例如要动用 van der Waerden 定理。其后果之一是：用此方法得到的定量界限极差。尽管如此，这条进路相当稳健，与 Gowers 的进路相比，它对算术结构的要求非常少。

同一个证明框架，两种“障碍 + 迭代”策略 Gowers 进路（前两节） 障碍 = 硬障碍（显式多项式相位） 需要：很强的逆定理（最难） 迭代 = 密度递增 定量界限相对较好 需要较多算术结构 软进路（本节） 障碍 = 软障碍（对偶函数） 逆定理几乎免费（引理 11.14） 迭代 = 能量递增 + 回归性 定量界限极差（用 vdW） 所需算术结构很少，更稳健
“难”在两条路线上守恒：硬障碍把难度压在逆定理上，软障碍把难度推到最后的回归性证明上。

为了描述这条通往 Szemerédi 定理的进路，让我们先回顾 10.5 节中 Roth 定理的有限化遍历证明所用的各种配料。其策略是：用某个低复杂度的近似 \(f_{U^\perp}\) 来逼近原函数 \(f\)，使得误差 \(f_U=f-f_{U^\perp}\) 是适当一致的。人们通过迭代来实现这一点：若已有某个初步近似 \(f_{U^\perp}\)，其误差 \(f_U\) 不够一致，那么就能断定 \(f_U\) 与某个阻碍一致性的障碍物相关——在那种情形下，这障碍物是一个特征标 \(e_\xi\)。然后人们用这个障碍物 \(e_\xi\) 构造出一个 \(\sigma\)-代数，并用该代数把近似 \(f_{U^\perp}\) 精细化（使它更接近 \(f\)），在此过程中增加 \(f_{U^\perp}\) 的能量（\(L^2\) 范数）。人们重复这一手续，直到误差最终变得一致（从而可忽略）为止。剩下唯一的任务，就是为近似 \(f_{U^\perp}\) 建立某种回归性质，即给出 \(\Lambda_k(f_{U^\perp},\dots,f_{U^\perp})\) 的一个下界。这里的关键是：近似 \(f_{U^\perp}\) 是用与特征标相关联的 \(\sigma\)-代数搭建起来的，因而是殆周期的；这就导出了 \(f_{U^\perp}\) 的一条非平凡回归性质。

直觉：迭代是怎么停下来的

把这套迭代想成一个“反复打磨”的过程，注意每一步在数量上发生了什么。

  1. 手里有一个近似 \(f_{U^\perp}\)，误差 \(f_U=f-f_{U^\perp}\)。
  2. 检查误差是否“一致”（Gowers 范数是否很小）。若一致，停止——此时 \(\Lambda_k(f,\dots,f)\approx\Lambda_k(f_{U^\perp},\dots,f_{U^\perp})\)，误差不影响计数。
  3. 若不一致，逆定理给出一个障碍物 \(F\) 与 \(f_U\) 相关。把 \(F\) 加进近似里，得到更好的 \(f_{U^\perp}\)。
  4. 每加一次，\(\|f_{U^\perp}\|_{L^2}^2\)（能量）都严格增大一个固定量。但 \(0\le f_{U^\perp}\le1\) 使能量有上界 \(\le1\)。
  5. “每步涨一个固定量、又有上界”⟹ 只能迭代有限次，必在某步停下。这就是能量递增论证收敛的全部秘密。

以上论证通过引入特征标 \(e_\xi\) 而用到了 Fourier 分析。然而，人们可以把这族函数换成任何其它函数族，只要两条性质成立：第一，这些函数要足够多，足以提供一套完整的、阻碍 \(k-2\) 阶 Gowers 一致性的障碍物；第二，由这些函数（更确切地说，由它们关联的 \(\sigma\)-代数）所生成的任何函数，都要有足够多的“殆周期性”以导出回归性。

利用这一观察，便有可能彻底抛弃 Fourier 分析，转而采用一族略有不同的函数：把特征标换成 \(k-1\) 阶的对偶函数，把殆周期函数换成 \(k-2\) 阶的一致殆周期函数。

现在我们更详细地讨论这些概念。我们从对偶函数的概念开始。

对偶函数

定义 11.13（对偶函数）若 \(f:Z\to\mathbb{C}\) 且 \(d\ge1\)，我们递归地定义对偶函数 \(D_d(f):Z\to\mathbb{C}\) 如下： \[D_1(f)(x)=\mathbb{E}_Z(f);\qquad D_{d+1}(f)(x)=\mathbb{E}_{h\in Z}\,T^h f(x)\,D_d\big(\overline{T^h f}\,f\big)(x).\] 其中 \(T^h f(x)=f(x+h)\) 是平移，\(\overline{T^h f}\,f\) 指逐点乘积 \(y\mapsto \overline{f(y+h)}\,f(y)\)。

当 \(d=2\) 时，可以用 Fourier 变换来计算对偶函数： \[\begin{aligned} D_2(f)(x)&=\mathbb{E}_{h\in Z}\,T^h f(x)\,\mathbb{E}_Z\big(\overline{T^h f}\,f\big)\\ &=\mathbb{E}_{h,k\in Z}\,T^h f(x)\,T^k f(x)\,\overline{T^{h+k}f(x)}\\ &=\sum_{\xi\in Z}|\hat f(\xi)|^2\,\hat f(\xi)\,e(\xi\cdot x). \end{aligned}\tag{11.24}\] 我们把它留作习题。对更高的 \(d\)，公式更复杂，例如 \[D_3(f)(x)=\mathbb{E}_{h,k,l\in Z}\,T^h f(x)\,T^k f(x)\,T^l f(x)\,\overline{T^{h+k}f(x)}\,\overline{T^{h+l}f(x)}\,\overline{T^{k+l}f(x)}\,T^{h+k+l}f(x).\]

例：怎样读懂 \(D_d\) 的“箱子结构”

对偶函数看着吓人，其实有一个干净的组合规则。把 \(d\) 个平移量 \(h_1,\dots,h_d\) 放进一个 \(d\) 维“箱子”，对它的每个非空顶点 \(S\subseteq\{1,\dots,d\}\)，取因子 \(T^{\,h(S)}f\)（其中 \(h(S)=\sum_{i\in S}h_i\)）；若 \(|S|\) 为偶数则取共轭。最后对所有平移量求平均。

  1. \(d=2\)，平移量 \(h,k\)。非空子集：\(\{h\}\)（不共轭）、\(\{k\}\)（不共轭）、\(\{h,k\}\)（偶数，共轭）。共 \(2^2-1=3\) 个因子——正是 (11.24) 里的 \(T^h f\,T^k f\,\overline{T^{h+k}f}\)。
  2. \(d=3\)，平移量 \(h,k,l\)。非空子集 \(2^3-1=7\) 个：单点 3 个（不共轭）、双点 3 个（共轭）、三点 1 个（不共轭）——正是上面 \(D_3\) 的 7 个因子。
  3. 规律一眼可见：因子数 \(=2^d-1\)，共轭与否看子集大小的奇偶。
\(D_2\) 的“正方形箱子”：4 个顶点，去掉原点剩 3 个因子 原点（丢弃） \(T^h f\) \(T^k f\) \(\overline{T^{h+k}f}\) 单点顶点：不共轭　|　双点顶点：共轭
对偶函数 \(D_d(f)\) 是把 \(f\) 的 \(2^d-1\) 个平移副本逐点相乘再平均；它恰好与 Gowers 范数 \(U^d\) 配成一对（见 (11.26)）。

我们注意到下述有用的平移与共轭不变性： \[D_d(T^h f)=T^h D_d(f);\qquad D_d(\bar f)=\overline{D_d(f)},\tag{11.25}\] 它由归纳法容易证得。

对偶函数与 Gowers 一致性范数有着密切联系。一个简单的归纳给出恒等式 \[\|f\|_{U^d(Z)}^{2^d}=\langle f,D_d(f)\rangle_{L^2(Z)}=\mathbb{E}_{x\in Z}\,f(x)\,\overline{D_d(f)(x)},\tag{11.26}\] 而由 Gowers–Cauchy–Schwarz 不等式 (11.6)，我们有不等式 \[\langle g,D_d(f)\rangle_{L^2(Z)}\le\|g\|_{U^d(Z)}\,\|f\|_{U^d(Z)}^{2^d-1}\tag{11.27}\] 对一切 \(f,g:Z\to\mathbb{C}\) 成立。特别地，我们得到 \(U^d(Z)\) 的对偶刻画： \[\|g\|_{U^d(Z)}=\sup\Big\{\langle g,D_d(f)\rangle_{L^2(Z)}:\|f\|_{U^d(Z)}\le1\Big\},\tag{11.28}\] 这正解释了“对偶函数”这一术语的由来。从 (11.26) 我们立刻得到一条简易的逆定理：

引理 11.14（软逆定理）设 \(f:Z\to\mathbb{C}\) 是一个模长不超过 \(1\) 的函数，令 \(F=D_d(f)\) 为其对偶函数。若 \(\|f\|_{U^d(Z)}\ge\eta\)，则 \[|\langle f,F\rangle|\ge\eta^{2^d}.\]
为什么这条逆定理“几乎免费”

对比一下两种逆定理就明白“软”在哪。

  1. 硬逆定理（Gowers 进路要的）：若 \(\|f\|_{U^d}\) 大，则存在一个具体的多项式相位函数 \(e(\phi)\) 与 \(f\) 相关。难点是要把这个 \(\phi\) 找出来并写成显式公式——这极难。
  2. 软逆定理（本节，引理 11.14）：若 \(\|f\|_{U^d}\ge\eta\)，则 \(f\) 与 \(F=D_d(f)\) 相关，\(|\langle f,F\rangle|\ge\eta^{2^d}\)。
  3. 证明只是把 (11.26) 念一遍：\(\langle f,F\rangle=\langle f,D_d(f)\rangle=\|f\|_{U^d}^{2^d}\ge\eta^{2^d}\)。一行而已。
  4. 代价：\(F=D_d(f)\) 是用 \(f\) 自己造出来的，不是一个显式公式，我们对它的内部结构一无所知。这就是“软”——只知道“存在且相关”，不知道“长什么样”。

正因如此，剩下的工作变成：证明这种软障碍 \(D_d(f)\) 仍然“足够有结构”（即殆周期），才能撑起回归性。这正是接下来 一致殆周期范数 要解决的。

于是，对偶函数构成了一套完整的、阻碍 Gowers 一致性的障碍物，它们将扮演 10.5 节中特征标 \(e_\xi\) 所扮演的角色。（要看出这一联系，注意对任何特征标 \(e_\xi\) 有 \(D_2(e_\xi)=e_\xi\)，因此特征标本身就是一种对偶函数。）为了在有限化遍历论证中有效地使用这条逆定理，我们需要表明：那些由对偶函数的 \(\sigma\)-代数所生成的函数，都服从某种“殆周期性”性质。

一致殆周期

实际的定义看起来相当古怪，为给出动机，我们先做一番非正式的讨论。为具体起见，我们在群 \(Z_N\) 中工作。在此情形下，所有函数 \(f:Z_N\to\mathbb{C}\) 当然都是以 \(N\) 为周期的，但我们感兴趣的，是那些对远小于 \(N\) 的平移就出现的殆周期性质——也就是说，平移 \(T^n f\) 以某种方式被压缩进了一个“维数”远小于 \(N\) 的空间里（不管这究竟意味着什么）。结果将表明：对每个阶 \(d-1\)，殆周期性都有一个不同的概念；粗略地说，若一个函数的相位（或诸相位）表现得像一个 \(d-1\) 次多项式，它就应当是 \(d-1\) 阶殆周期的。

让我们用几个例子把这一直觉量化。函数 \(f(x)=e(\xi x/N)\) 是我们期望“1 阶殆周期”的范例函数，因为它的平移 \(T^n f\) 相当回归。事实上我们有公式 \[T^n f=c_n f,\] 其中 \(c_n\) 是常数 \(c_n=e(\xi n/N)\)。若改取函数 \(f(x)=e(\xi_1 x/N)+e(\xi_2 x/N)\)，则该函数仍被视为 1 阶殆周期，因为我们有公式 \[T^n f=c_{n,1}g_1+c_{n,2}g_2,\] 其中 \(c_{n,j}\) 是常数 \(c_{n,j}=e(\xi_j n/N)\)，而 \(g_j\) 是有界函数 \(g_j(x)=e(\xi_j x/N)\)。于是在这种情形下，\(f\) 的诸平移 \(T^n f\) 只在一个二维空间里变动。

接下来，我们考虑函数 \(f(x)=e(ax^2/N)\)。这个函数不会被认为是通常意义下殆周期的，因为它的平移看起来取值于一个维数非常高（高达 \(N\)）的空间。事实上我们有平移公式 \[T^n f=c_n f,\] 其中 \(c_n\) 不再是常数，而它们本身是 \(x\) 的线性无关函数：\(c_n(x)=e((2anx+n^2)/N)\)。然而请注意，虽然 \(c_n\) 不是常数，它们仍比原函数 \(f\) “更简单”，因为它们是 1 阶殆周期的，而我们期望那个二次的对象 \(f\) 是 2 阶殆周期的。

\(f=e(\xi x/N)\) \(T^n f=c_n\,f\) \(c_n\) 是常数 平移住在 1 维空间 ⟹ 1 阶殆周期 相位是 1 次多项式 \(f=e(\xi_1 x/N)+e(\xi_2 x/N)\) \(T^n f=c_{n,1}g_1+c_{n,2}g_2\) \(c_{n,j}\) 是常数 平移住在 2 维空间 ⟹ 仍是 1 阶殆周期 两个 1 次相位之和 \(f=e(ax^2/N)\) \(T^n f=c_n(x)\,f\) \(c_n(x)\) 是1 阶殆周期函数 平移看似住在 N 维 ⟹ 2 阶殆周期 相位是 2 次多项式
核心动机：“高一阶的殆周期 = 把系数从常数放宽成低一阶的殆周期函数”。这就是定义 11.15 递归结构的来源。

当然可以继续举这类例子。它们引向下述递归启发式：一个函数 \(f\) 应当被认为是 \(d-1\) 阶殆周期的，如果它有某种形如 \[T^n f=c_{n,1}g_1+c_{n,2}g_2+\cdots\] 的表示，其中 \(g_1,g_2,\dots\) 是有界函数，而 \(c_{n,1},c_{n,2},\dots\) 是 \(d-2\) 阶殆周期的。当然，人们还应当对这个展开中出现多少项给出某个界限，否则的话一切函数都会是每个阶的殆周期函数了。

把上述直觉形式化的一个方便方式如下。

定义 11.15（一致殆周期范数）若 \(f:Z\to\mathbb{C}\)，当 \(f\) 非常数时我们定义 \(\|f\|_{UAP^0(Z)}\) 为无穷，当 \(f\) 等于某常数 \(c\) 时定义其等于 \(|c|\)。现在归纳地假设 \(UAP^d(Z)\) 范数已对某个 \(d\) 定义好了，我们把 \(f\) 的 \(UAP^{d+1}(Z)\) 范数定义为所有满足下述表示公式的常数 \(M>0\) 的下确界： \[T^n f=M\,\mathbb{E}(c_{n,h}\,g_h)\quad\text{对一切 }n\in Z,\tag{11.29}\] 其中 \(H\) 是一个有限非空集合，\(g=(g_h)_{h\in H}\) 是一族从 \(Z\) 到 \(\mathbb{C}\) 的函数，满足 \(\|g_h\|_{L^\infty(Z)}\le1\)；\(c=(c_{n,h})_{n\in Z,h\in H}\) 是一族从 \(Z\) 到 \(\mathbb{C}\) 的函数，满足 \(\|c_{n,h}\|_{UAP^d(Z)}\le1\)；而 \(h\) 是一个取值于 \(H\) 的随机变量（\(\mathbb{E}\) 即对 \(h\) 求期望）。

我们非正式地称一个函数为 \(d-1\) 阶一致殆周期的，如果它的 \(UAP^{d-1}(Z)\) 范数有界。

逐字读懂 (11.29)

把定义 11.15 与前面三个例子对上号。

  1. 底层 \(d=0\)：只有常数才有有限的 \(UAP^0\) 范数（等于它的模长）。非常数的范数是无穷——这是“最简单”的一档。
  2. 往上一阶 \(UAP^1\)：要求 \(T^n f=M\,\mathbb{E}_h(c_{n,h}g_h)\)，其中系数 \(c_{n,h}\) 的 \(UAP^0\) 范数 \(\le1\)，即 \(c_{n,h}\) 必须是模长 \(\le1\) 的常数。这正对应例子里 \(T^n f=c_{n,1}g_1+c_{n,2}g_2\)（常系数）。
  3. 再往上 \(UAP^2\)：系数 \(c_{n,h}\) 被放宽成 \(UAP^1\) 范数 \(\le1\) 的函数（即 1 阶殆周期）。这正对应 \(f=e(ax^2/N)\) 的 \(T^n f=c_n(x)f\)，其中 \(c_n(x)\) 是 1 阶殆周期。
  4. \(H\) 有限保证了“项数有界”——若允许无穷项，任何函数都能蒙混过关，定义就空洞了。

人们容易归纳地验证：对 \(d\ge1\)，\(UAP^d(Z)\) 范数是有限的，并且确实是范数，特别地服从三角不等式 \[\|f+g\|_{UAP^d(Z)}\le\|f\|_{UAP^d(Z)}+\|g\|_{UAP^d(Z)}.\tag{11.30}\] 此外，我们还有重要的 Banach 代数性质 \[\|fg\|_{UAP^d(Z)}\le\|f\|_{UAP^d(Z)}\,\|g\|_{UAP^d(Z)}.\tag{11.31}\] 我们把这些事实的简易验证留作习题；定义 11.15 中那个相当复杂的构造，其设计的首要目的正是为了得到 (11.30)、(11.31) 这些良好的性质。

为什么 Banach 代数性质 (11.31) 是关键

回忆软进路的设计：要用一致殆周期函数顶替特征标。特征标族有一个好用之处——“殆周期函数的多项式组合仍是殆周期的”。在新框架里，正是 (11.31) 这条“乘积的范数 \(\le\) 范数之积”扮演这个角色。

  1. 能量递增时，我们要把若干障碍物相乘、相加来精细化近似 \(f_{U^\perp}\)。
  2. 三角不等式 (11.30) 保证“相加”后范数不爆。
  3. Banach 代数性质 (11.31) 保证“相乘”后范数不爆：\(\|fg\|\le\|f\|\|g\|\)。
  4. 两条合起来 ⟹ 由有界 \(UAP\) 函数生成的整个代数仍然有界，于是回归性可以传下去。

\(UAP^{d-1}\) 范数是 \(U^d\) 范数的一种对偶；见习题 11.4.8。\(UAP^1\) 范数与 Wiener 代数范数相同，见习题 11.4.10。它们也与对偶函数相联系：

引理 11.16设 \(f:Z\to\mathbb{C}\) 是一个模长不超过 \(1\) 的函数。则对一切 \(d\ge1\)， \[\|D_d(f)\|_{UAP^{d-1}(Z)}\le1.\]
证明. 我们对 \(d\) 归纳。\(d=1\) 的情形是显然的（\(D_1(f)=\mathbb{E}_Z(f)\) 是常数，其 \(UAP^0\) 范数等于其模长 \(\le1\)）。现在设 \(d\ge2\) 且断言已对 \(d-1\) 证得。由 \(D_d(f)\) 的定义与 (11.25)，并作变量替换 \(n+h=h'\)，我们有 \[T^n D_d(f)=\mathbb{E}_{h\in Z}\big(T^{n+h}f\cdot D_{d-1}(\overline{T^{n+h}f}\,T^n f)\big)=\mathbb{E}_{h'\in Z}\big(D_{d-1}(\overline{T^{h'}f}\,T^n f)\cdot T^{h'}f\big).\] 于是只需取 \(M:=1\)，\(H:=Z\)，\(c_{n,h}=D_{d-1}(\overline{T^h f}\,T^n f)\)，以及 \(g_h:=T^h f\)，断言便随之成立。（这里 \(\|g_h\|_{L^\infty}\le1\)；而 \(\overline{T^h f}\,T^n f\) 模长 \(\le1\)，由归纳假设其 \(D_{d-1}\) 的 \(UAP^{d-2}\) 范数 \(\le1\)，即 \(\|c_{n,h}\|_{UAP^{d-1}}\le1\)。）♦

把这一点与引理 11.14 结合，我们看到 \(d-1\) 阶一致殆周期函数构成了一套完整的、阻碍 \(d\) 阶 Gowers 一致性范数的障碍物：

推论 11.17（软逆定理，其二）设 \(f:Z\to\mathbb{C}\) 是一个模长不超过 \(1\) 的函数，且 \(\|f\|_{U^d(Z)}\ge\eta\)。则存在一个函数 \(F:Z\to\mathbb{C}\)，使得 \(\|F\|_{UAP^{d-1}}\le1\) 且 \[|\langle f,F\rangle|\ge\eta^{2^d}.\]
推论 11.17 是怎么拼出来的
  1. 取 \(F=D_d(f)\)。由引理 11.14，\(|\langle f,F\rangle|=\|f\|_{U^d}^{2^d}\ge\eta^{2^d}\)。这就给了“相关性”。
  2. 由引理 11.16，\(\|F\|_{UAP^{d-1}}=\|D_d(f)\|_{UAP^{d-1}}\le1\)。这就给了“结构性（殆周期）”。
  3. 两步合一：障碍物 \(F\) 既与 \(f\) 相关、又是有界殆周期的——这正是软进路所需的全部。

分解与回归

现在人们已有足够的机器来证明下述命题 10.36 的变体。

命题 11.18（Koopman–von Neumann 分解）设 \(k\ge3\)，设 \(f:Z\to\mathbb{R}^+\) 满足 \(0\le f(x)\le1\)，设 \(\sigma>0\)，并设 \(F:\mathbb{R}^+\times\mathbb{R}^+\to\mathbb{R}^+\) 为任意函数。则存在一个量 \(K=O_{\sigma,F,k}(1)\) 以及一个分解 \(f=f_{U^\perp}+f_U\)，具有下述性质：
  • “反一致”分量 \(f_{U^\perp}\) 服从界 \(0\le f_{U^\perp}\le1\) 与 \(\mathbb{E}_Z f_{U^\perp}=\mathbb{E}_Z f\)。此外，存在一个对 \(f_{U^\perp}\) 的近似 \(f_{UAP}\)，满足 \(0\le f_{UAP}\le1\)，\(\|f_{U^\perp}-f_{UAP}\|_{L^2(Z)}\le\sigma\)，以及 \(\|f_{UAP}\|_{UAP^{k-2}(Z)}\le K\)；
  • “一致”分量 \(f_U\) 服从 Gowers 一致性估计 \(\displaystyle\|f_U\|_{U^{k-1}(Z)}\le\frac{1}{F(\sigma,K)}\)。

此命题用与命题 10.36 几乎相同的手段证明，我们把它留作习题。推论 11.17 中的软逆定理使我们能够用一致殆周期函数作为特征标（以及拟周期函数）的替代品；这类函数的 Banach 代数性质则是“殆周期函数的多项式组合仍殆周期”这一事实的替代品。除此之外，证明基本相同。

分解在干什么

把 \(f\) 拆成两块，各管一摊：

  1. \(f_U\)（一致部分）：Gowers 范数极小（可由你随意指定的 \(F\) 把它压到要多小有多小）。由广义 von Neumann 定理 (11.8)，它对 \(\Lambda_k\) 的计数几乎没有贡献，可以忽略。
  2. \(f_{U^\perp}\)（反一致部分）：保持均值不变（\(\mathbb{E}_Z f_{U^\perp}=\mathbb{E}_Z f\ge\delta\)），并且能被一个 \(UAP^{k-2}\) 范数 \(\le K\) 的殆周期函数 \(f_{UAP}\) 很好地逼近。
  3. 于是 \(\Lambda_k(f,\dots,f)\approx\Lambda_k(f_{U^\perp},\dots,f_{U^\perp})\)。只要给后者一个正的下界，定理就到手了——这正是命题 11.19 要做的。

为完成 Szemerédi 定理 \(r_k(Z_N)=o_{N\to\infty;k}(N)\) 的证明，人们还需要一条关于殆周期分量的回归性定理：

命题 11.19（一致殆周期函数是回归的）设 \(k\ge3\)，设 \(N\) 为一个大素数，设 \(f_{U^\perp},f_{UAP}:Z_N\to\mathbb{R}^+\) 满足 \(0\le f_{U^\perp},f_{UAP}\le1\)，\(\mathbb{E}_{Z_N}f_{U^\perp}\ge\delta\)，\(\displaystyle\|f_{U^\perp}-f_{UAP}\|_{L^2(Z_N)}\le\frac{\delta^2}{1024k}\)，以及 \(\|f_{UAP}\|_{UAP^{k-2}(Z_N)}\le K\)。则我们有 \[\Lambda_k(f_{U^\perp},\dots,f_{U^\perp})\;\gg_{k,\delta,K}\;1.\]

由命题 11.19、命题 11.18 与 (11.8)，人们便能用与 10.5 节相同的论证推出 Szemerédi 定理。然而命题 11.19 的证明相当困难，它要援引一个对 \(k\) 的归纳、用一个能量递增论证去正则化将出现的某些 \(\sigma\)-代数、用一些 Hilbert 空间论证把诸如 \(\{T^n f_{UAP}:f_{UAP}\in Z_N\}\) 之类的平移轨道局部紧化，然后用 van der Waerden 定理去寻找单色的算术级数，其中的染色由局部紧化所决定。我们这里不会完整地证明它，把全部细节交给读者参阅 [357]。不过，我们将在下面勾勒稍微简单些的 \(k=3\) 情形的论证。在此情形下，人们其实可以转而依靠习题 11.4.10 与命题 10.35，得到一个更简单、界限高效得多的证明，但我们下面给出的论证不需要 Fourier 变换，并且（在补充论证后）能推广到更高的 \(k\) 情形。

命题 11.19 在 \(k=3\) 情形的证明（梗概）. 我们把诸平移 \(\{T^n f_{UAP}:n\in Z_N\}\) 视作 \(L^2(Z_N)\) 的一个子集。由于 \(\|f_{UAP}\|_{UAP^1}\le K\)，我们看到存在一个取值于有限集合 \(H\) 的随机变量 \(h\) 以及函数 \(g_h:Z\to\mathbb{C}\)（满足 \(\|g_h\|_{L^\infty(Z_N)}\le1\)），使得所有的平移 \(T^n f_{UAP}\) 都含于集合 \[\Omega:=\{K\,\mathbb{E}_h(c_h g_h):c_h\in\mathbb{C},\ |c_h|\le1\text{ 对一切 }h\in H\}\tag{11.32}\] 之中，这个集合可被想成是某种高维立方体。结果表明，这个集合是“紧”的：它能被 \(O_{k,\delta,K}(1)\) 个 \(L^2(Z_N)\) 中半径为 \(\delta^2/1024\) 的球所覆盖（见习题 11.4.13）。这就在 \(Z_N\) 上诱导出一个用 \(O_{\delta,K}(1)\) 种颜色的染色：给每个 \(n\in Z_N\) 指派一个含有 \(T^n f\) 的球（作为它的颜色）。

由 van der Waerden 定理（习题 6.3.9），我们断定：对 \(\gg_{\delta,K}(1)\) 比例的数对 \((a,r)\in Z_N\)，三元组 \(a,a+r,a+2r\) 是单色的，从而函数 \(T^a f_{UAP},\,T^{a+r}f_{UAP},\,T^{a+2r}f_{UAP}\) 落在同一个 \(\delta^2/1024\)-球中。这蕴含函数 \(T^a f_{U^\perp},\,T^{a+r}f_{U^\perp},\,T^{a+2r}f_{U^\perp}\) 两两之间的距离至多为 \(\delta^2/512\)。由于这些函数还介于 \(0\) 与 \(1\) 之间且均值为 \(\delta\)，对它们应用 Markov 不等式便表明：这些函数在一个密度至少为 \(\delta/4\) 的集合上同时大于（比方说）\(\delta/4\)。于是对所有这样的数对 \((a,r)\)， \[\mathbb{E}\big(T^a f_{U^\perp}\cdot T^{a+r}f_{U^\perp}\cdot T^{a+2r}f_{U^\perp}\big)=\gg_\delta(1).\] 对所有 \(a,r\) 取平均，便得到断言。♦

\(k=3\) 回归性证明：从“紧”到单色 AP 再到正的计数 平移轨道 \(\{T^n f_{UAP}\}\) 含于高维立方体 \(\Omega\) (11.32) \(\Omega\) 是“紧”的 可被有限个小球覆盖 习题 11.4.13 球 = 颜色 把 \(Z_N\) 染成有限色 van der Waerden 定理 很多 \((a,a{+}r,a{+}2r)\) 单色 习题 6.3.9 三点函数互相很近 ⟹ 同时较大 Markov 不等式 \(\Rightarrow \Lambda_3(f_{U^\perp},f_{U^\perp},f_{U^\perp})\gg1\) 单色 = 三个平移落在同一小球 ⟹ 三者 \(L^2\) 距离 \(\le\delta^2/512\) 均值 \(\delta\) + 互相很近 ⟹ 在正密度集上同时 \(>\delta/4\) ⟹ 乘积平均为正
软进路最后一步的逻辑链：殆周期 ⟹ 轨道紧 ⟹ 有限染色 ⟹ van der Waerden 给单色 3-AP ⟹ 三点同时大 ⟹ 3-AP 计数有正下界。van der Waerden 的塔型界限正是“定量界限极差”的根源。

习题

习题
  1. 11.4.1　证明 (11.24) 与 (11.25)。
  2. 11.4.2　证明 (11.26)、(11.27) 与 (11.28)。
  3. 11.4.3　验证 \(\|f\|_{UAP^d(Z)}\) 对一切 \(d\ge1\) 是良定义且有限的，并服从 (11.30) 与 (11.31)。特别地，验证 \(UAP^d(Z)\) 范数确实是一个范数。
  4. 11.4.4　建立单调性 \(\|f\|_{UAP^{d+1}(Z)}\le\|f\|_{UAP^d(Z)}\)，对一切 \(f:Z\to\mathbb{C}\) 与 \(d\ge0\)。
  5. 11.4.5　设 \(\phi:Z\to Z\) 是一个 2 阶 Freiman 同构。证明 \(\|f\circ\phi\|_{UAP^{d-1}(Z)}=\|f\|_{UAP^{d-1}(Z)}\)，对一切 \(f:Z\to\mathbb{C}\) 与 \(d\ge1\)。特别地，\(UAP^{d-1}(Z)\) 范数是平移不变的。
  6. 11.4.6　设 \(\phi:Z\to\mathbb{R}/\mathbb{Z}\) 是一个次数小于 \(d\) 的相位多项式。证明 \(\|e(\phi)f\|_{UAP^{d-1}(Z)}=\|f\|_{UAP^{d-1}(Z)}\)，对一切 \(f:Z\to\mathbb{C}\)。
  7. 11.4.7　设 \(\phi:Z\to\mathbb{R}/\mathbb{Z}\) 是一个次数小于 \(d\) 的相位多项式。证明 \(D_d(e(\phi))=e(\phi)\) 且 \(\|e(\phi)\|_{UAP^{d-1}(Z)}=1\)，从而每个多项式相位函数都是一个对偶函数。
  8. 11.4.8　[357] 对任何 \(d\ge1\) 与 \(f,g:Z\to\mathbb{C}\) 得到不等式 \[\langle f,g\rangle_{L^2(Z)}\le\|f\|_{U^d(Z)}\,\|g\|_{UAP^{d-1}(Z)}.\] （提示：对 \(d\) 用归纳。）于是 \(d-1\) 阶一致殆周期的函数几乎正交于 \(d\) 阶 Gowers 一致的函数。这可看作推论 11.17 的一个部分逆命题。特别注意我们有 \[\|f\|_{L^2(Z)}^2\le\|f\|_{U^d(Z)}\,\|f\|_{UAP^{d-1}(Z)},\] 从而一个函数不可能在既一致殆周期又 Gowers 一致的同时还不小。
  9. 11.4.9　设 \(f,g:Z\to\mathbb{C}\) 是模长不超过 \(1\) 的函数。建立不等式 \[\|fg\|_{U^d(Z)}^{2^d}\le\|f\|_{UAP^{d-1}(Z)}\,\|g\|_{U^d(Z)}\] 对一切 \(d\ge1\)。（提示：对 \(\overline f g\) 应用引理 11.16，并结合 \(UAP^{d-1}(Z)\) 的代数性质。）
  10. 11.4.10　（Ben Green，私人通信）证明 \(\|f\|_{UAP^1(Z)}=\|\hat f\|_{\ell^1(Z)}\)，对一切 \(f:Z\to\mathbb{C}\)。（提示：由习题 11.4.7 与三角不等式可得 \(\|f\|_{UAP^1(Z)}\le\|\hat f\|_{\ell^1(Z)}\)。要得另一方向的不等式，先用 Plancherel 定理证明：当 \(c_{n,h}\) 是模长 \(\le1\) 的常数、\(g_h\) 是满足 \(\|g_h\|_{L^\infty(Z)}\le1\) 的函数、\(b\) 是满足 \(\|\hat b\|_{\ell^\infty(Z)}\le1\) 的函数时，\(|\mathbb{E}_{n,x\in Z}c_{n,h}g_h(x)b(x+n)|\le1\)。）
  11. 11.4.11　[357] 证明命题 11.18。
  12. 11.4.12　利用命题 11.19、命题 11.18 与 (11.8)，推出对一切 \(k\ge1\) 与一切大的 \(N\) 有 \(r_k(Z_N)=o_{N\to\infty;k}(N)\)。
  13. 11.4.13　[357] 设 \(\Omega\) 是 (11.32) 中定义的集合。证明：给定任何 \(\varepsilon>0\)，\(\Omega\) 能被 \(O_{\varepsilon,K}(1)\) 个 \(L^2(Z)\) 中半径为 \(\varepsilon\) 的球所覆盖。（提示：找一个极大的标准正交集 \(v_1,\dots,v_J\)，使 \(\mathbb{E}|\langle g_h,v_j\rangle_{L^2(Z)}|^2\ge\varepsilon^2/4\) 对一切 \(1\le j\le J\) 成立，并用 Bessel 不等式与期望的线性性得到 \(J\) 的一个上界。再证明 \(\Omega\) 中的量与 \(v_1,\dots,v_J\) 张成的 \(J\) 维空间相距不超过 \(\varepsilon/2\)。）

返回 全书目录