Tao–Vu · 加性组合学 · 第 4 章 傅里叶分析方法
4.3 线性偏差Linear bias
本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演 / 自测）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。
本节目标给一个有限群里的集合 \(A\) 定义一个数字——傅里叶偏差 \(\|A\|_u\)，用它来衡量“\(A\) 离随机集合有多近”。本节要把这件事讲清楚，并证明一个核心结论：偏差越小（越“随机”），把若干个这样的集合相加，和集就越容易铺满整个群。作为应用，我们会看到有限域里的“平方数集合”虽然只占一半，但只要相加三次就能取遍整个域。
把傅里叶变换应用到和集理论或等差数列理论，一种常见的做法是引入某个集合的傅里叶偏差（Fourier bias，也叫线性偏差或伪随机性）这一概念。粗略地说，这个概念把集合分成两个极端：一类是高度均匀的（其行为像随机集合，尤其在反复求和集时如此），另一类是高度不均匀的（其行为像等差数列）。
定义 4.12（傅里叶偏差）设 \(Z\) 是一个有限加法群。若 \(A\) 是 \(Z\) 的子集，我们定义集合 \(A\) 的傅里叶偏差 \(\|A\|_u\) 为如下的量：
\[\|A\|_u := \sup_{\xi\in Z\setminus\{0\}} |\widehat{1_A}(\xi)|.\]
这个量总是非负的；并且 \(\|A\|_u=0\) 当且仅当 \(A\) 等于 \(Z\) 或空集（习题 4.3.1）。它服从如下对称性：对任意 \(h\in Z\) 有 \(\|A\|_u=\|-A\|_u=\|A+h\|_u=\|Z\setminus A\|_u\)（习题 4.3.2）。我们提醒：这个量不是单调的——\(A\subseteq B\) 并不蕴含 \(\|A\|_u\le\|B\|_u\)。不过，傅里叶偏差确实服从三角不等式（习题 4.3.3）。傅里叶偏差 \(\|A\|_u\) 最大可以达到密度 \(P_Z(A)\)，但通常比它小（习题 4.3.4）。傅里叶偏差小于 \(\alpha\) 的集合 \(A\) 有时被称为 \(\alpha\)-均匀或 \(\alpha\)-伪随机；偏差很小的集合则被称为线性均匀、一阶 Gowers 均匀或伪随机。
先把符号读懂
- \(1_A\)：集合 \(A\) 的指示函数，\(x\in A\) 时取 \(1\)，否则取 \(0\)。
- \(\widehat{1_A}(\xi)\)：它的傅里叶系数，本书的归一化约定是 \(\displaystyle\widehat{1_A}(\xi)=\frac{1}{|Z|}\sum_{x\in A} e(-x\cdot\xi)\)，其中 \(e(t)=e^{2\pi i t}\)。
- 在 \(\xi=0\) 处，\(\widehat{1_A}(0)=\dfrac{|A|}{|Z|}=P_Z(A)\)，这就是 \(A\) 的密度（占整个群的比例）。
- 偏差 \(\|A\|_u\) 故意把 \(\xi=0\) 排除在外，只看其余频率上系数的最大模长。直觉：\(\xi=0\) 那一项永远是密度，没信息；其余频率若都很小，说明 \(A\) “没有偏向任何方向”，看起来像随机撒的点。
傅里叶偏差与和集之间的联系，可由下面的引理来描述。
引理 4.13（均匀性蕴含大和集）设 \(n\ge 3\)，又设 \(A_1,\dots,A_n\) 是有限加法群 \(Z\) 中的加性集合。那么对任意 \(x\in Z\)，有
\[\left|\frac{1}{|Z|^{n-1}}\bigl|\{(a_1,\dots,a_n)\in A_1\times\cdots\times A_n : x=a_1+\cdots+a_n\}\bigr|-P_Z(A_1)\cdots P_Z(A_n)\right|\]
\[\le \|A_1\|_u\cdots\|A_{n-2}\|_u\, P_Z(A_{n-1})^{1/2}P_Z(A_n)^{1/2}.\]
特别地，如果
\[\|A_1\|_u\cdots\|A_{n-2}\|_u < P_Z(A_1)\cdots P_Z(A_{n-2})P_Z(A_{n-1})^{1/2}P_Z(A_n)^{1/2},\tag{$\star$}\]
那么 \(A_1+\cdots+A_n=Z\)。
当然，若把 \(A_1,\dots,A_n\) 的次序作排列，类似结论仍成立。注意，量 \(P_Z(A_1)\cdots P_Z(A_n)\) 正是：在“条件 \(x=a_1+\cdots+a_n\) 之下，事件 \(a_1\in A_1,\dots,a_n\in A_n\) 相互独立”的假设下，\(\dfrac{1}{|Z|^{n-1}}\bigl|\{(a_1,\dots,a_n)\in A_1\times\cdots\times A_n : x=a_1+\cdots+a_n\}\bigr|\) 所应取的值。这或许有助于解释为何均匀性有时被称为伪随机性。
引理在说什么（先抓直觉）把 \(N(x):=\bigl|\{(a_1,\dots,a_n): x=a_1+\cdots+a_n\}\bigr|\) 理解为“用各集合各取一个元素相加得到 \(x\) 的方法数”。若各集合是随机的，那么把所有 \(|Z|^n\) 种取法平摊到 \(|Z|\) 个可能的和上，每个和 \(x\) 期望得到 \(\dfrac{|A_1|\cdots|A_n|}{|Z|}=P_Z(A_1)\cdots P_Z(A_n)\,|Z|^{n-1}\) 种。引理说：真实方法数与这个“随机期望值”之差，被偏差的乘积控制住了。如果偏差足够小（条件 \((\star)\)），那么每个 \(x\) 的方法数都 \(>0\)，于是每个 \(x\) 都能被表示，即和集铺满 \(Z\)。
证明. 由 (4.9)（卷积定理），函数 \(1_{A_1}*\cdots*1_{A_n}\) 的傅里叶变换为 \(\widehat{1_{A_1}}\cdots\widehat{1_{A_n}}\)。应用傅里叶反演公式 (4.4)、等式 (4.15)、Cauchy–Schwarz 不等式以及 (4.16)，我们得到
\[1_{A_1}*\cdots*1_{A_n}(x)=\operatorname{Re}\,1_{A_1}*\cdots*1_{A_n}(x)\]
\[=\operatorname{Re}\sum_{\xi\in Z}\widehat{1_{A_1}}(\xi)\cdots\widehat{1_{A_n}}(\xi)\,e(x\cdot\xi)\]
\[\ge \widehat{1_{A_1}}(0)\cdots\widehat{1_{A_n}}(0)-\sum_{\xi\in Z\setminus\{0\}}|\widehat{1_{A_1}}(\xi)|\cdots|\widehat{1_{A_n}}(\xi)|\]
\[\ge P_Z(A_1)\cdots P_Z(A_n)-\|A_1\|_u\cdots\|A_{n-2}\|_u\sum_{\xi\in Z}|\widehat{1_{A_{n-1}}}(\xi)||\widehat{1_{A_n}}(\xi)|\]
\[\ge P_Z(A_1)\cdots P_Z(A_n)-\|A_1\|_u\cdots\|A_{n-2}\|_u\,\|\widehat{1_{A_{n-1}}}\|_{\ell^2(Z)}\|\widehat{1_{A_n}}\|_{\ell^2(Z)}\]
\[= P_Z(A_1)\cdots P_Z(A_n)-\|A_1\|_u\cdots\|A_{n-2}\|_u\,P_Z(A_{n-1})^{1/2}P_Z(A_n)^{1/2}.\]
类似的论证给出
\[1_{A_1}*\cdots*1_{A_n}(x)\le P_Z(A_1)\cdots P_Z(A_n)+\|A_1\|_u\cdots\|A_{n-2}\|_u\,P_Z(A_{n-1})^{1/2}P_Z(A_n)^{1/2}.\]
而由卷积的定义，
\[1_{A_1}*\cdots*1_{A_n}(x)=|Z|^{1-n}\bigl|\{(a_1,\dots,a_n)\in A_1\times\cdots\times A_n : x=a_1+\cdots+a_n\}\bigr|,\]
于是引理得证。♦
- 第一步：把“方法数”写成卷积。卷积 \(1_{A_1}*\cdots*1_{A_n}(x)\) 按定义恰好等于 \(|Z|^{1-n}N(x)\)。所以只要估计这个卷积，就估计了方法数 \(N(x)\)。
- 第二步：到频率侧去算。卷积定理 (4.9) 说“卷积的傅里叶变换 = 各自傅里叶变换相乘”；反演公式 (4.4) 把卷积写回成对所有频率 \(\xi\) 求和：\(\sum_\xi \widehat{1_{A_1}}(\xi)\cdots\widehat{1_{A_n}}(\xi)e(x\cdot\xi)\)。
- 第三步：拆出零频主项。取实部后，\(\xi=0\) 那一项是 \(\widehat{1_{A_1}}(0)\cdots\widehat{1_{A_n}}(0)=P_Z(A_1)\cdots P_Z(A_n)\)（每个零频系数就是密度）。这就是“随机期望主项”。
- 第四步：把误差（非零频之和）压小。其余项的总和不超过 \(\sum_{\xi\ne0}|\widehat{1_{A_1}}(\xi)|\cdots|\widehat{1_{A_n}}(\xi)|\)。先把前 \(n-2\) 个因子各自用偏差的上界 \(\|A_i\|_u\) 替换（因为 \(\xi\ne0\)），提到求和号外面。
- 第五步：最后两个因子用 Cauchy–Schwarz。剩下的 \(\sum_\xi |\widehat{1_{A_{n-1}}}(\xi)||\widehat{1_{A_n}}(\xi)|\le \|\widehat{1_{A_{n-1}}}\|_{\ell^2}\|\widehat{1_{A_n}}\|_{\ell^2}\)。再由 Plancherel 等式 (4.16)，\(\|\widehat{1_A}\|_{\ell^2}^2=\mathbb{E}_x|1_A(x)|^2=P_Z(A)\)，故 \(\|\widehat{1_A}\|_{\ell^2}=P_Z(A)^{1/2}\)。这正好补上结论右端最后那两个 \(1/2\) 次幂的因子。
- 结论：主项 \(=\) 随机期望，误差 \(\le\) 偏差乘积。若误差小于主项，则方法数恒正，每个 \(x\) 都可表示，于是 \(A_1+\cdots+A_n=Z\)。♦
现在我们给出上述机器在有限域 Waring 问题上的一个应用。先需要一条标准的引理。
引理 4.14（Gauss 和估计）设 \(F\) 是一个奇阶有限域，又设 \(A:=F^{\wedge 2}=\{a^2 : a\in F\}\) 为 \(F\) 中的平方数集合。那么
\[\|A\|_u\le \frac{1}{2|F|}+\frac{1}{2|F|^{1/2}}.\]
证明. 设 \(\xi\in F\setminus 0\)。由于 \(A\) 中每个非零元素恰好有两种形如 \(a^2\) 的表示，我们有
\[\widehat{1_A}(\xi)=\frac{1}{|F|}\sum_{x\in A}e(-\xi\cdot x)=\frac{1}{2|F|}+\frac{1}{2|F|}\sum_{a\in F}e(-\xi\cdot a^2).\]
另一方面，我们可以对 Gauss 和取平方：
\[\left|\sum_{a\in F}e(-\xi\cdot a^2)\right|^2=\left|\sum_{a\in F}e(\xi\cdot a^2)\right|^2=\sum_{a,b\in F}e(\xi\cdot(a^2-b^2))\]
\[=\sum_{a,h\in F}e(\xi\cdot(a^2-(a+h)^2))=\sum_{h\in F}e(-\xi\cdot h^2)\sum_{a\in F}e(\xi\cdot 2ah).\]
若 \(h\neq 0\)，则 \(2h\neq 0\)（因为 \(F\) 是奇阶域），从而 \(\sum_{a\in F}e(\xi\cdot 2ah)=\sum_{c\in F}e(\xi\cdot c)=0\)（这一步用到引理 4.5）。另一方面，若 \(h=0\)，则 \(\sum_{a\in F}e(\xi\cdot 2ah)=|F|\)。于是我们得出 \(\bigl|\sum_{a\in F}e(\xi\cdot a^2)\bigr|^2=|F|\)，断言随之成立。♦
例：\(F=\mathbb{F}_7\) 里的平方数集合
逐个算 \(\mathbb{F}_7=\{0,1,2,3,4,5,6\}\) 各元素的平方（模 \(7\)）：
- \(0^2=0,\;1^2=1,\;2^2=4,\;3^2=2,\;4^2=2,\;5^2=4,\;6^2=1\)。
- 把出现的值收集起来：\(A=\{0,1,2,4\}\)，共 \(|A|=4=\dfrac{|F|+1}{2}\) 个。可见每个非零平方（\(1,2,4\)）都恰有两个平方根，例如 \(1=1^2=6^2\)。
- 密度 \(P_F(A)=\dfrac{4}{7}\approx 0.571\)，约等于 \(\tfrac12\)。
- 把引理 4.14 的上界代进去：\(\|A\|_u\le \dfrac{1}{14}+\dfrac{1}{2\sqrt7}\approx 0.071+0.189=0.260\)。
- 关键对比：偏差 \(0.260\) 明显小于密度 \(0.571\)。也就是说，平方数集合虽然只占一半，却已经相当“均匀”——这正是下面推论能成立的原因。
把这条引理与引理 4.13 结合起来，立即得到
推论 4.15设 \(F\) 是奇阶有限域，又设 \(A=F^{\wedge 2}\) 是平方数集合。那么对一切 \(k\ge 3\)，有 \(kA=F\)。事实上，对任意 \(x\in F\)，把 \(x\) 表示为和 \(x=a_1+\cdots+a_k\)（其中 \(a_1,\dots,a_k\in A\)）的方法数为
\[\bigl(2^{1-k}+O_k(|F|^{-(k-2)/2})\bigr)|F|^{k-1}.\]
我们把这条推论的验证留作习题（习题 4.3.10）。它表明：当 \(k\ge 3\) 时，和集 \(kA\) 大致是均匀分布的。注意，当 \(k=2\) 时，人们仍能证明 \(2A=F\)，但此时的和集可能相当不规则；例如，若 \(-1\) 在 \(F\) 中不是平方数，那么 \(0\) 只有唯一一种表示成 \(A\) 中两个元素之和的方式。
为什么 \(k=2\) 与 \(k\ge3\) 差别这么大引理 4.13 要求 \(n\ge 3\)：它至少要留出 \(n-2\ge 1\) 个偏差因子来压制误差。\(k=2\) 时根本没有偏差因子可用，误差控制不住，于是和集可以很不均匀（例如某些 \(x\) 的表示方法数为 \(0\) 或极少）。\(k\ge 3\) 时偏差因子 \(\|A\|_u^{k-2}\) 把误差压到比主项小，方法数处处为正且接近期望，于是 \(kA=F\) 且分布均匀。
分步验证 \(k=2\) 的不规则：\(0\) 在 \(\mathbb{F}_7\) 中有几种写法
- 在 \(\mathbb{F}_7\) 中 \(-1=6\)，而平方数集合是 \(\{0,1,2,4\}\)，\(6\notin A\)，所以 \(-1\) 不是平方数。
- 要把 \(0\) 写成两个平方数之和 \(0=x+y\)（\(x,y\in A\)），需 \(y=-x\)。若 \(x\neq0\)，则 \(-x=y\) 也是平方数，于是 \(-1=y\cdot x^{-1}\) 是两个平方数之商，仍是平方数——矛盾。
- 故只能 \(x=y=0\)，即 \(0=0+0\) 是唯一写法。可见 \(2A\) 处的方法数极不均匀。
- 但若改用 \(k=3\)：由推论 4.15，每个 \(x\)（含 \(0\)）的表示方法数约为 \(2^{1-3}|F|^{2}=\tfrac14\cdot49\approx12\) 种，处处都有，\(3A=F\) 且分布平整。
下面我们给出一条引理，它粗略地断言：若 \(B\) 是 \(A\) 的一个随机选取的子集，则 \(\|B\|_u\) 近似等于 \(\dfrac{|B|}{|A|}\|A\|_u\)；也就是说，传到随机子集时，傅里叶偏差按比例下降。
引理 4.16 [149]设 \(A\) 是有限加法群 \(Z\) 中的加性集合，又设 \(0<\tau\le 1\)。设 \(B\) 是 \(A\) 的一个随机子集，由如下方式定义：让各事件 \(a\in B\) 相互独立、各以概率 \(\tau\) 发生。那么对任意 \(\lambda>0\)，有
\[\mathbb{P}\bigl(|\,\|B\|_u-\tau\|A\|_u\,|\ge\lambda\sigma\bigr)\le 4|Z|\max\Bigl(e^{-\lambda^2/8},\,e^{-\lambda\sigma/2\sqrt2}\Bigr),\]
其中 \(\sigma^2:=|A|\tau(1-\tau)/|Z|^2\)。
这条引理是 Chernoff 不等式的一个容易推论，留作习题（习题 4.3.11）。取 \(\lambda=C\log^{1/2}|Z|\)（\(C\) 为某个大常数），并假设 \(|A|\tau(1-\tau)\gg\log|Z|\)，我们尤其得到（例如） \[\mathbb{P}\Bigl(\|B\|_u=\tau\|A\|_u+O\bigl(\sigma\log^{1/2}|Z|\bigr)\Bigr)=1-O(|Z|^{-100}).\] 特别地，若取 \(A=Z\)，则以高概率有 \[\|B\|_u=\tau\|Z\|_u+O\!\left(\sqrt{\frac{\tau(1-\tau)\log|Z|}{|Z|}}\right);\] 由于 \(\|Z\|_u=0\)，因此\(Z\) 的随机子集往往极其均匀。注意，由推论 1.10，以高概率有 \(P_Z(B)\approx\tau\)。
这条引理的含义把 \(A\) 的每个元素独立地“以概率 \(\tau\) 保留”，得到子集 \(B\)。那么 \(B\) 的偏差大约是 \(A\) 偏差的 \(\tau\) 倍——和它的密度同步缩小。尤其当 \(A=Z\)（整个群，偏差为 \(0\)）时，随机子集 \(B\) 的偏差几乎为 \(0\)，即随便随机抽出的集合天生就很“伪随机”。这从概率角度解释了“均匀 = 像随机”的说法。
傅里叶偏差的一项重要应用是研究长度为 3 的等差数列。我们将在第 10 章详细研究这一应用。
习题
习题 4.3.1–4.3.13
- 4.3.1. 设 \(A\) 是有限加法群 \(Z\) 的子集。证明 \(\|A\|_u=0\) 当且仅当 \(A=Z\) 或 \(A=\varnothing\)。
- 4.3.2. 设 \(A\) 是有限加法群 \(Z\) 的子集。证明对任意 \(h\in Z\) 有 \(\|A\|_u=\|-A\|_u=\|T_hA\|_u=\|Z\setminus A\|_u\)。更一般地，若 \(\varphi:Z\to Z'\) 是从一个加法群到另一个加法群的任意同构，证明 \(\|\varphi(A)\|_u=\|A\|_u\)。同理，证明集合 \(A\) 的傅里叶偏差不依赖于对称非退化双线性型的选取。
- 4.3.3. 设 \(A,B\) 是有限加法群 \(Z\) 中不相交的子集。证明 \(|\,\|A\|_u-\|B\|_u\,|\le\|A\cup B\|_u\le\|A\|_u+\|B\|_u\)。
- 4.3.4. 设 \(A\) 是有限加法群 \(Z\) 中的加性集合。证明 \(\|A\|_u\le P_Z(A)\)，且等号成立当且仅当 \(A\) 含于 \(Z\) 的某个真子群的一个陪集之中。
- 4.3.5. 设 \(A,A'\) 分别是有限加法群 \(Z,Z'\) 的子集。证明 \(\|A\times A'\|_u=\|A\|_u\|A'\|_u\)。
- 4.3.6. 设 \(A\) 是有限加法群 \(Z\) 的子集。证明 \(\|A\|_u=\sup_\varphi|\langle 1_A,e(\varphi)\rangle_{C(Z)}|\)，其中 \(\varphi:Z\to\mathbb{R}/\mathbb{Z}\) 取遍所有非常值线性相位函数（如习题 4.1.4 中所定义）。
- 4.3.7. 设 \(A,B\) 是有限加法群 \(Z\) 中的加性集合。证明 \[E(A,B)\le\frac{|A|^2|B|^2}{|Z|}+|Z|^2\|A\|_u^2|B|.\] 利用 (2.8) 推出：若 \(\|A\|_u\le\alpha P_Z(A)\)，则 \[|A+B|\ge\frac{1}{2}\min\!\left(|Z|,\frac{1}{\alpha^2}|B|\right).\tag{4.22}\] 因此 \(\alpha\)-均匀的集合往往把和集放大约 \(\alpha^{-2}\) 倍（除非由于平凡上界 \(|A+B|\le|Z|\) 而不可能）。
- 4.3.8. 设 \(A\) 是有限加法群 \(Z\) 中的加性集合。证明 \[\|A\|_u^4\le\frac{1}{|Z|^3}E(A,A)-P_Z(A)^4\le\|A\|_u^2 P_Z(A).\tag{4.23}\] 因此均匀集合的加性能量 \(E(A,A)\) 接近其最小值 \(P_Z(A)^4|Z|^3\)，反之亦然。
- 4.3.9. 设 \(A\) 是有限加法群 \(Z\) 中的加性集合，又设 \(n\ge 3\) 为整数。利用引理 4.13，证明：若 \(nA=Z\)，则 \(P_Z(A)^{1+\frac{1}{n-2}}\le\|A\|_u\le P_Z(A)\)。当 \(n\) 很大时这个估计尤其有用，因为它表明 \(1_A\) 有一个很大的非平凡傅里叶系数。
- 4.3.10. 证明推论 4.15。并证明恒等式 \(A\cdot 2A=A\)，进而推出 \(2A=F\)（利用 \(3A=F\) 来证明 \(2A=A\)）。
- 4.3.11. 利用 Chernoff 不等式（习题 1.3.4 的形式）证明引理 4.16。
- 4.3.12. [149] 设 \(A,B\) 是有限加法群 \(Z\) 中的加性集合。利用引理 4.13 建立不等式 \[\|S\|_u\ge P_Z(A)^{1/2}P_Z(B)^{1/2}P_Z(S),\] 只要 \(S\) 与 \(A+B\) 不相交。特别地，当 \(S=Z\setminus(A+B)\) 时此不等式成立。这表明和集的补集是“遗传性非均匀”的。
- 4.3.13. 设 \(A\) 是素数阶循环群 \(Z_p\) 的子集。证明对 \(Z_p\) 中任意等差数列 \(P\)，有均匀分布估计 \[P_{Z_p}(A\cap P)=P_{Z_p}(A)P_{Z_p}(P)+O(\varepsilon)+O\!\left(\frac{1}{\varepsilon}\log\frac{1}{\|A\|_u}\right)\] 对任意 \(0<\varepsilon\le 1\) 成立。（提示：作变量替换使 \(P=[-N,N]\)；再用某种光滑一点的函数逼近指示函数 \(1_P\)。）
返回 全书目录