Tao–Vu · 加性组合学 · 第 4 章 傅里叶分析方法

4.2　\(L^p\) 理论L theory

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演 / 自测）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。本节是全书较难的一节，凡是抽象记号都会先用具体的小例子把它“算给你看”。

本节目标上一节我们把傅里叶变换“定义”出来了；本节要给它装上度量工具——一整套测量“函数有多大”的范数 \(L^p\) 与 \(l^p\)，并证明两条核心不等式（豪斯多夫–杨不等式、杨不等式）。然后把这套工具用到一个具体的组合问题上：在有限域里，只要集合 \(A\) 足够大，它的“积集再相加” \(A\!\cdot\!A+A\!\cdot\!A+A\!\cdot\!A\) 就会铺满整个域。一句话：用“函数大小”的语言重新刻画“集合大小”，再用傅里叶把它们联系起来。

我们现在转向傅里叶变换与卷积的解析理论，先从 \(L^p\) 理论讲起，然后把它应用到“在和集（sum set）内部定位算术级数”这一问题上。

4.2.1　范数：测量一个函数有多大

设 \(f\in\mathbb{C}^Z\)（即 \(f\) 是从有限加法群 \(Z\) 到复数的函数），并设 \(0\(L^p(Z)\) 范数定义为 \[\|f\|_{L^p(Z)}:=\big(\mathbb{E}_Z|f|^p\big)^{1/p}=\Big(\mathbb{E}_{x\in Z}|f(x)|^p\Big)^{1/p}.\] 这里 \(\mathbb{E}_{x\in Z}\) 表示对 \(x\) 在 \(Z\) 上取平均，即 \(\mathbb{E}_{x\in Z}h(x)=\frac{1}{|Z|}\sum_{x\in Z}h(x)\)。例如 \(\|f\|_{L^2(Z)}\) 恰好就是把 \(f\) 看作希尔伯特空间中的向量时的“长度”（模长）。我们还定义 \[\|f\|_{L^\infty(Z)}=\sup_{x\in Z}|f(x)|.\] 类似地，对 \(0求和而非平均） \[\|f\|_{l^p(Z)}:=\Big(\sum_{\xi\in Z}|f(\xi)|^p\Big)^{1/p},\qquad \|f\|_{l^\infty(Z)}:=\sup_{\xi\in Z}|f(\xi)|.\]

例：先把这两套范数算给你看 取 \(Z=\{0,1,2,3\}\)（四个元素，\(|Z|=4\)），函数取值 \(f(0)=2,\ f(1)=0,\ f(2)=0,\ f(3)=2\)。
  1. \(L^2\)（带平均）：\(\|f\|_{L^2}=\big(\tfrac14(2^2+0+0+2^2)\big)^{1/2}=\big(\tfrac14\cdot 8\big)^{1/2}=\sqrt2\)。
  2. \(l^2\)（不带平均，直接求和）：\(\|f\|_{l^2}=\big(2^2+0+0+2^2\big)^{1/2}=\sqrt8=2\sqrt2\)。
  3. \(L^\infty\) 与 \(l^\infty\)：两者都取最大绝对值 \(=2\)（\(\sup\) 不区分平均还是求和）。
关键区别只有一个：\(L^p\) 在“物理空间” \(Z\) 上取平均，\(l^p\) 在“频率空间” \(Z\) 上直接求和。本书的习惯是：对原函数 \(f\) 用 \(L^p\)，对它的傅里叶变换 \(\hat f\) 用 \(l^p\)。
物理空间：\(L^p\)（取平均 \(\mathbb E_{x}\)） 频率空间：\(l^p\)（直接求和 \(\sum_\xi\)） 除以 \(|Z|\) 后开方 不除以 \(|Z|\) 直接开方
同一组数据，用 \(L^p\) 与用 \(l^p\) 量出来的“大小”差一个 \(|Z|^{1/p}\) 的因子。记住口诀：左边平均（\(L\)），右边求和（\(l\)）。

4.2.2　两条核心不等式

关于傅里叶变换与卷积，我们有以下两个基本的 \(L^p\) 估计。

定理 4.8 设 \(f,g:Z\to\mathbb{C}\) 是加法群 \(Z\) 上的函数。则对任意 \(1\le p\le 2\)，有豪斯多夫–杨不等式（Hausdorff–Young inequality） \[\|\hat f\|_{l^{p'}(Z)}\le\|f\|_{L^p(Z)},\tag{4.12}\] 其中 \(p\) 的对偶指数 \(p'\) 由 \(\dfrac1p+\dfrac1{p'}=1\) 定义。此外，只要 \(1\le p,q,r\le\infty\) 满足 \(\dfrac1p+\dfrac1q=\dfrac1r+1\)，就有杨不等式（Young inequality） \[\|f*g\|_{L^r(Z)}\le\|f\|_{L^p(Z)}\,\|g\|_{L^q(Z)}.\tag{4.13}\]

这两个不等式都容易由里斯–索林复插值定理（Riesz–Thorin complex interpolation theorem）推出。有了这条定理，人们只需验证两个极端（且容易）的情形即可。然而里斯–索林定理超出了本书的范围。另一方面，也可以用组合论证给出一个初等证明（见习题 4.2.3）。

直觉：“插值”是什么意思，为什么只需验两端 对偶指数的关系 \(\frac1p+\frac1{p'}=1\) 把 \([1,2]\) 上的每个 \(p\) 都配上一个 \(p'\in[2,\infty]\)。
  1. 左端 \(p=1\)：此时 \(p'=\infty\)。(4.12) 变成 \(\|\hat f\|_{l^\infty}\le\|f\|_{L^1}\)，意思是“每个傅里叶系数的大小都不超过 \(f\) 的平均绝对值”——因为 \(\hat f(\xi)\) 本身就是某种带相位的平均，三角不等式立刻给出，这是容易的一端。
  2. 右端 \(p=2\)：此时 \(p'=2\)。(4.12) 变成 \(\|\hat f\|_{l^2}\le\|f\|_{L^2}\)，这其实是普朗歇尔（Parseval）等式，也容易。
  3. 插值定理说：一个线性映射若在两端 \(p=1\) 与 \(p=2\) 都成立这样的估计，那么对中间的每个 \(p\) 也自动成立。于是只验两端就够了。这正是“插值”一词的含义：在两个已知点之间“连线补全”。
习题 4.2.3 给出一条不依赖插值定理的纯组合路线，思路是“二进分解 + 张量幂去掉对数因子”，下文习题部分会逐字翻译。

4.2.3　与加法能量的联系

回忆 \(Z\) 中两个加法集合 \(A,B\) 之间的加法能量（additive energy） \(E(A,B)\)，它在定义 2.8 中给出。由那条定义可以容易验证 \[E(A,B)=|Z|^3\,\|1_A*1_B\|_{L^2(Z)}^2.\] 利用 (4.2) 与 (4.9)（即傅里叶反演与“卷积的傅里叶变换等于傅里叶变换之积”），我们得到如下基本恒等式 \[E(A,B)=|Z|^3\,E(\hat 1_A,\hat 1_B)=|Z|^3\sum_{\xi\in Z}|\hat 1_A(\xi)|^2\,|\hat 1_B(\xi)|^2.\tag{4.14}\] 这条公式或许能照亮第 2.3 节中得到的加法能量的若干性质，例如对称性 \(E(A,B)=E(B,A)=E(A,-B)\) 以及柯西–施瓦茨不等式 (2.9)；见习题 4.2.7。

加法能量到底数的是什么 加法能量 \(E(A,B)\) 数的是四元组 \((a,b,a',b')\in A\times B\times A\times B\) 中满足 \[a+b=a'+b'\] 的个数。等价地：有多少种方式让“一个来自 \(A\)、一个来自 \(B\) 的和”发生碰撞。下图把一次碰撞画出来。
数轴（和的取值） a b a' b' 两条弦落在同一点：\(a+b=a'+b'\) 同一个和值
加法能量 = “和发生碰撞”的四元组数。公式 (4.14) 说：这个纯组合的计数，等于在频率空间里把 \(|\hat 1_A|^2|\hat 1_B|^2\) 全部加起来——这就是傅里叶方法的威力：把计数翻译成求和。

就加性组合学的目的而言，傅里叶变换在作用于特征函数（characteristic function） \(f=1_A\) 时最为有用；此时关于傅里叶变换及其与加法能量 \(E(A,A)\) 的关系，能说出相当多的东西。

引理 4.9 设 \(A\) 是有限加法群 \(Z\) 的子集，\(\hat 1_A:Z\to\mathbb{C}\) 为 \(A\) 的特征函数的傅里叶变换。则有如下恒等式： \[\|\hat 1_A\|_{l^\infty(Z)}=\sup_{\xi\in Z}|\hat 1_A(\xi)|=\hat 1_A(0)=\mathbb{P}_Z(A);\tag{4.15}\] \[\|\hat 1_A\|_{l^2(Z)}^2=\sum_{\xi\in Z}|\hat 1_A(\xi)|^2=\mathbb{P}_Z(A);\tag{4.16}\] \[\hat 1_A(\xi)=\overline{\hat 1_A(-\xi)};\tag{4.17}\] \[\|\hat 1_A\|_{l^4(Z)}^4=\sum_{\xi\in Z}|\hat 1_A(\xi)|^4=\frac{E(A,A)}{|Z|^3};\tag{4.18}\] \[\hat 1_A(\xi)=\sum_{\eta\in Z}\hat 1_A(\eta)\,\hat 1_A(\xi-\eta).\tag{4.19}\] 其中 \(\mathbb{P}_Z(A)=|A|/|Z|\) 是 \(A\) 在 \(Z\) 中的密度。

本引理容易从已经建立的那些估计推出；见习题 4.2.4。

逐条读懂引理 4.9
  1. (4.15)：\(\hat 1_A(0)\) 是“零频率”，即不带相位的平均 \(\mathbb{E}_x 1_A(x)=|A|/|Z|=\mathbb{P}_Z(A)\)。又因为任何 \(\hat 1_A(\xi)\) 都是若干个模长为 \(1\) 的项的平均、再乘上权重，其绝对值不会超过零频率处的值。所以最大的傅里叶系数恰好出现在 \(\xi=0\)，等于密度。
  2. (4.16)：这是普朗歇尔等式。注意 \(1_A\) 取值非 \(0\) 即 \(1\)，故 \(\mathbb{E}_x|1_A(x)|^2=\mathbb{E}_x 1_A(x)=\mathbb{P}_Z(A)\)；普朗歇尔把它搬到频率边，得到所有 \(|\hat 1_A(\xi)|^2\) 之和也等于密度。
  3. (4.17)：因为 \(1_A\) 取实值，把 \(\xi\) 换成 \(-\xi\) 相当于把所有相位取共轭，于是 \(\hat 1_A(-\xi)\) 与 \(\hat 1_A(\xi)\) 互为共轭。
  4. (4.18)：把 (4.14) 取 \(B=A\) 即得——\(l^4\) 范数的四次方正是加法能量（除以 \(|Z|^3\)）。这是后文反复使用的一座桥：“能量大”等价于“某些傅里叶系数大”。
  5. (4.19)：因为特征函数满足 \(1_A\cdot 1_A=1_A\)（要么 \(0\cdot0\)，要么 \(1\cdot1\)），两边取傅里叶变换；右边“逐点相乘”对应频率边的“卷积”，于是得到 \(\hat 1_A\) 与自身的卷积仍等于 \(\hat 1_A\)。

4.2.4　一个应用：有限域上的和–积估计

我们现在在有限域 \(\mathbb{F}\) 的背景下，给出傅里叶变换的一个简单应用。

引理 4.10 设 \(\mathbb{F}\) 是一个有限域，\(A\subset\mathbb{F}\setminus\{0\}\) 满足 \(|A|>|\mathbb{F}|^{3/4}\)。则 \[3(A\cdot A)=A\cdot A+A\cdot A+A\cdot A=\mathbb{F}.\]
先把结论说清楚 这里 \(A\cdot A=\{a_1a_2:a_1,a_2\in A\}\) 是积集，而 \(A\cdot A+A\cdot A+A\cdot A\) 是把三个这样的积集逐元素相加得到的和集。结论是：只要 \(A\) 的元素个数超过 \(|\mathbb{F}|^{3/4}\)（在整个域里占的比例不算太小），那么“三段积集之和”就足以覆盖整个域 \(\mathbb{F}\) 的每一个元素，一个都不漏。这说明：在域里同时做乘法和加法，会让一个集合迅速“膨胀”到撑满全域。
整个有限域 \(\mathbb{F}\)（每个点都要被覆盖） 三块 \(A\!\cdot\!A\) 相加后互相叠加，缝隙全部填满 → \(=\mathbb F\)
当 \(|A|>|\mathbb F|^{3/4}\) 时，三段积集之和没有任何空隙。证明的策略是：证明卷积 \(f*f*f\) 在每一点都严格大于零，而“取值非零的点集”正是 \(3(A\cdot A)\)。
证明. 我们在 \(\mathbb{F}\) 上取一个例 4.2 中那种类型的对称非退化双线性型（用来定义傅里叶变换所需的“频率配对”）。令 \(f:\mathbb{F}\to\mathbb{R}\) 为如下非负函数 \[f:=\mathbb{E}_{a\in A}\,1_{a\cdot A}.\] 注意到 \(\operatorname{supp}(f)=A\cdot A\)（\(f(x)\neq0\) 当且仅当 \(x\) 能写成 \(a\cdot a'\) 的形式），且 \(\hat f(0)=\mathbb{E}_{\mathbb F}f=\mathbb{P}_{\mathbb F}(A)\)。取傅里叶变换，我们得到 \[\hat f(\xi)=\mathbb{E}_{a\in A}\,\hat 1_A(\xi/a)\qquad\text{对任意 }\xi\in\mathbb{F}.\] 若 \(\xi\neq0\)，则当 \(a\) 在 \(A\) 中变动时，频率 \(\xi/a\) 两两不同。利用柯西–施瓦茨不等式，再用 (4.16)，我们得到 \[|\hat f(\xi)|\le\frac1{|A|}\,|A|^{1/2}\,\mathbb{P}_{\mathbb F}(A)^{1/2}=1/|\mathbb{F}|^{1/2}\qquad\text{对 }\xi\neq0.\] 现在设 \(x\in\mathbb{F}\) 任意。我们用 (4.4) 与 (4.9) 来计算 \[ \begin{aligned} f*f*f(x)&=\operatorname{Re}\,f*f*f(x)\\ &=\operatorname{Re}\sum_{\xi\in\mathbb F}\hat f(\xi)^3\,e(\xi\cdot x)\\ &\ge\operatorname{Re}\hat f(0)^3-\sum_{\xi\in\mathbb F\setminus\{0\}}|\hat f(\xi)|^3\\ &\ge\mathbb{P}_{\mathbb F}(A)^3-\sum_{\xi\in\mathbb F}|\mathbb{F}|^{-1/2}\,|\hat f(\xi)|^2\\ &=\mathbb{P}_{\mathbb F}(A)^3-|\mathbb{F}|^{-1/2}\,\mathbb{P}_{\mathbb F}(A)\\ &>0, \end{aligned} \] 这是因为由假设 \(\mathbb{P}_{\mathbb F}(A)>|\mathbb{F}|^{-1/4}\)。由于 \(\operatorname{supp}(f*f*f)=3(A\cdot A)\) 而 \(x\) 是任意的，证毕。♦
把证明拆成最小的步子
  1. 造一个函数 \(f\)。 \(f=\mathbb{E}_{a\in A}1_{a\cdot A}\) 是把 \(A\) 的所有“放大版” \(a\cdot A\) 平均起来。它的支撑集（取值非零处）恰好是积集 \(A\cdot A\)。
  2. 看零频率。 \(\hat f(0)\) 就是 \(f\) 的平均 \(=\mathbb{P}_{\mathbb F}(A)=|A|/|\mathbb F|\)，这是“主项”。
  3. 控制非零频率（关键）。 对 \(\xi\neq0\)，\(\hat f(\xi)=\mathbb{E}_{a\in A}\hat 1_A(\xi/a)\) 是 \(|A|\) 个频率处的平均。因为这些频率 \(\xi/a\) 互不相同，柯西–施瓦茨给 \[\Big|\sum_{a\in A}\hat 1_A(\xi/a)\Big|\le|A|^{1/2}\Big(\sum_{a\in A}|\hat 1_A(\xi/a)|^2\Big)^{1/2}\le|A|^{1/2}\,\mathbb P_{\mathbb F}(A)^{1/2},\] 最后一步用 (4.16)：所有 \(|\hat 1_A|^2\) 之和都不超过 \(\mathbb P_{\mathbb F}(A)\)。除以 \(|A|\) 得 \(|\hat f(\xi)|\le|\mathbb F|^{-1/2}\)。
  4. 卷积写成频率求和。 三重卷积 \(f*f*f(x)=\sum_\xi\hat f(\xi)^3 e(\xi\cdot x)\)。把 \(\xi=0\) 的主项 \(\hat f(0)^3=\mathbb P_{\mathbb F}(A)^3\) 单独拿出，其余项当作误差。
  5. 主项压住误差。 误差 \(\le\) \(\big(\max_{\xi\neq0}|\hat f(\xi)|\big)\sum_\xi|\hat f(\xi)|^2\le|\mathbb F|^{-1/2}\mathbb P_{\mathbb F}(A)\)。于是 \[f*f*f(x)\ge\mathbb P_{\mathbb F}(A)\big(\mathbb P_{\mathbb F}(A)^2-|\mathbb F|^{-1/2}\big).\]
  6. 用假设收尾。 \(|A|>|\mathbb F|^{3/4}\) 即 \(\mathbb P_{\mathbb F}(A)>|\mathbb F|^{-1/4}\)，平方得 \(\mathbb P_{\mathbb F}(A)^2>|\mathbb F|^{-1/2}\)，括号为正，故 \(f*f*f(x)>0\)。每一点 \(x\) 都被覆盖，即 \(3(A\cdot A)=\mathbb F\)。♦
这正是傅里叶方法的标准套路：主项（零频率）+ 误差（非零频率），证明主项始终压住误差。
注记 4.11 引理 4.10 是一个和–积估计（sum-product estimate）的简单例子——所谓和–积估计，是断言一个集合 \(A\) 的“和与积的某种组合”必然比 \(A\) 本身大得多。它可以看作如下事实的定量反映：一个基数大于 \(|\mathbb{F}|^{3/4}\) 的集合 \(A\)，很难表现得像 \(\mathbb{F}\) 的一个子域。应将它与第 2.8 节的结果相比较。
为什么“像子域就矛盾” 若 \(A\) 真是一个子域，则对加法和乘法都封闭，于是 \(A\cdot A=A\)、\(A\cdot A+A\cdot A+A\cdot A=A\)，集合不会变大。引理 4.10 却说和集铺满了全域 \(\mathbb F\)——除非 \(A\) 本身就接近全域，否则这与“封闭、不增长”直接冲突。所以一个足够大但又不等于全域的 \(A\) 不可能对乘法与加法同时保持封闭，这就是“难以像子域”的精确含义。

习题

习题 4.2.1（\(L^p\) 与 \(l^p\) 的三角不等式） 设 \(1\le p<\infty\)。通过利用函数 \(x\mapsto|x|^p\) 的凸性，证明集合 \(\{f\in\mathbb{C}^Z:\|f\|_{L^p(Z)}\le1\}\) 是凸的，并由此得出三角不等式 \[\|f+g\|_{L^p(Z)}\le\|f\|_{L^p(Z)}+\|g\|_{L^p(Z)}.\] 对 \(p=\infty\) 的情形以及把 \(L^p\) 换成 \(l^p\) 的情形，做类似论证。
习题 4.2.2（赫尔德不等式） 设 \(1赫尔德不等式（Hölder's inequality） \[\|fg\|_{L^r(Z)}\le\|f\|_{L^p(Z)}\,\|g\|_{L^q(Z)},\] 只要 \(0
习题 4.2.3（不用复插值证明定理 4.8） 本习题的目的是给出定理 4.8 的一个不需要复插值的证明。
  1. 首先利用 (4.2)、平凡界 \[\|\hat f\|_{l^\infty(Z)}\le\|f\|_{L^1(Z)},\tag{4.20}\] 以及赫尔德不等式，建立较弱的估计 \[\|\hat f\|_{l^{p'}(Z)}=O_p\big(\|f\|_{L^p(Z)}\big),\] 其中假设 \(f\in\mathbb{C}^Z\) 的支撑落在某个集合 \(A\) 上，并且对所有 \(x\in A\) 有 \(|f(x)|=\Theta(\lambda)\)（即在某个阈值 \(\lambda\) 的常数倍范围内）。
  2. 然后，通过把上一步的不等式应用到 \(f\) 的一个二进分解（dyadic decomposition），再用三角不等式，证明对任意 \(f\in\mathbb{C}^Z\) 成立更弱的估计 \[\|\hat f\|_{l^{p'}(Z)}=O_p\big(\|f\|_{L^p(Z)}\log(1+|Z|)\big).\]
  3. 最后，去掉 \(O_p(\log(1+|Z|))\) 这个因子以建立 (4.12)：方法是把 \(Z\) 替换成它的一个大幂 \(Z^M\)，同样把 \(f\) 替换成一个大的张量幂（如推论 2.19 中那样），并令 \(M\to\infty\)。用类似论证可建立 (4.13)。
习题 4.2.3 的思路提示 “去掉对数因子”的技巧叫张量幂法（tensor power trick）：若一个不等式带了一个“恼人的常数” \(C\)，但该常数对 \(Z\to Z^M\) 而言只增长成 \(C\)（不随 \(M\) 变），那么把不等式两边各自的范数关于乘积群展开后会出现 \(M\) 次幂，开 \(M\) 次方再令 \(M\to\infty\)，常数 \(C^{1/M}\to1\) 就被“稀释”掉了。这里恼人的常数是 \(\log(1+|Z|)\)，换成 \(\log(1+|Z|^M)=M\log(1+|Z|)\) 后开 \(M\) 次方趋于 \(1\)。
习题 4.2.4 证明引理 4.9。
习题 4.2.5 设 \(A\) 是有限加法群 \(Z\) 中的一个加法集合。证明：\(\hat 1_A\) 取实值当且仅当 \(A\) 是对称的（即 \(A=-A\)）。
习题 4.2.6（有限群上的大数定律） 设 \(f:Z\to\mathbb{R}_{\ge0}\) 满足 \(\mathbb{E}_Z f=1\) 且 \(f(0)=0\)，并设 \(H\) 是由 \(\operatorname{supp}(f)\) 生成的 \(Z\) 的子群。证明 \(|\hat f(\xi)|\le1\)，且等号成立当且仅当 \(\xi\in H^\perp\)。
习题 4.2.6 的直觉 \(\hat f(\xi)=\mathbb{E}_x f(x)e(-x\cdot\xi)\) 是把若干个模长为 \(e(-x\cdot\xi)\)（模长 \(1\)）的相位用非负权重 \(f(x)\) 加权平均（总权重 \(\mathbb{E}_Z f=1\)）。一堆模长为 \(1\) 的复数取凸组合，结果的模长 \(\le1\)；要取到 \(=1\)，必须所有有权重的相位完全一致（指向同一方向），即对一切 \(x\in\operatorname{supp}(f)\) 有 \(e(-x\cdot\xi)\) 相同——这恰好就是 \(\xi\) 与整个支撑集“正交”，从而与它生成的子群 \(H\) 正交，即 \(\xi\in H^\perp\)。

返回 全书目录