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

4.1　基础理论Basic theory

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 定义 / 引理 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。本节较抽象，凡有公式都先给出最小的具体例子（常取循环群 \(\mathbf Z_N\)）再讲一般情形。

傅里叶分析（Fourier analysis）以多种方式刻画随机性与结构之间的二分法，其中最引人注目的是它能用来证明罗斯（Roth）的著名定理（我们将在第 10 章讨论）：上密度为正的整数子集中含有无穷多个长度为 \(3\) 的等差数列。（更长的等差数列无法用线性傅里叶技术处理，需要高阶傅里叶分析或其他方法；见第 11 章。）

傅里叶分析可以在任意加法群 \(Z\) 上进行（甚至在非交换群上）。然而，我们只需要在有限群上做这种变换，那里理论在技术上稍微简单一些。因此我们将把注意力完全限制在有限的情形。\(Z=\mathbf Z\)、\(Z=\mathbf R/\mathbf Z\)、\(Z=\mathbf R\) 这几种情形对加性组合学也很重要（特别是会导出解析数论中的哈代–李特尔伍德圆法），但事实表明，在我们的应用中，有限傅里叶理论可以作为这些无穷傅里叶理论的一个可接受的替代品。

本节目标 在一个有限加法群 \(Z\)（例如循环群 \(\mathbf Z_N\)）上把“有限傅里叶变换”这套工具从零搭起来。要做四件事：(1) 用双线性型 \(\xi\cdot x\) 把群和它的对偶等同起来；(2) 引入一组叫特征 \(e_\xi\) 的函数，证明它们正交；(3) 定义傅里叶变换 \(\hat f(\xi)\)，并得到帕塞瓦尔 / 普朗歇尔 / 反演三个核心恒等式；(4) 引入卷积 \(f*g\)，说明它正好把“两个集合相加 \(A+B\)”这件事翻译成乘法 \(\hat f\cdot\hat g\)。这就是后续所有傅里叶方法的地基。

4.1.1　双线性型：把群和它的对偶等同起来

设 \(Z\) 是一个有限加法群（例如 \(Z\) 可以是循环群 \(Z=\mathbf Z_N\)）。本节回顾这类群上有限傅里叶变换的基础理论。傅里叶分析依赖于群 \(Z\) 与它的庞特里亚金对偶（Pontryagin dual）\(\hat Z\) 之间的对偶性；\(\hat Z\) 可以定义为从 \(Z\) 到圆群 \(\mathbf R/\mathbf Z\) 的所有同态构成的空间。在有限群的情形，事实表明群 \(Z\) 与它的对偶 \(\hat Z\) 总是同构的，因此为了让理论稍微简化，把两者等同起来是方便的。这件事可以借助一个非退化双线性型来完成。

定义 4.1（双线性型） 加法群 \(Z\) 上的一个双线性型（bilinear form）是一个映射 \((\xi,x)\mapsto \xi\cdot x\)，把 \(Z\times Z\) 送到 \(\mathbf R/\mathbf Z\)，并且对两个变量 \(\xi,x\) 中的每一个单独来看都是同态。若对每个非零的 \(\xi\)，映射 \(x\mapsto \xi\cdot x\) 都不恒为零，并且对每个非零的 \(x\)，映射 \(\xi\mapsto \xi\cdot x\) 也都不恒为零，则称该双线性型是非退化的（non-degenerate）。若 \(\xi\cdot x=x\cdot\xi\)，则称它是对称的（symmetric）。

逐字拆开看这个定义：“值落在 \(\mathbf R/\mathbf Z\) 里”意思是把一个实数只看小数部分（模 \(1\) 相加），所以 \(\tfrac34+\tfrac34=\tfrac32\equiv\tfrac12\)。“对每个变量是同态”意思是 \((\xi_1+\xi_2)\cdot x=\xi_1\cdot x+\xi_2\cdot x\)，以及 \(\xi\cdot(x_1+x_2)=\xi\cdot x_1+\xi\cdot x_2\)（都在 \(\bmod 1\) 的意义下）。“非退化”是说：没有哪个非零元素会被这个配对“看不见”。

例 4.2 若 \(Z\) 是循环群 \(\mathbf Z_N\)，则双线性型 \[ x\cdot\xi:=\frac{x\xi}{N} \pmod 1 \] 是对称且非退化的。若 \(Z\) 是有限域 \(F\) 上的标准向量空间 \(F^n\)，则当 \(\phi:F\to\mathbf R/\mathbf Z\) 是从 \(F\) 到 \(\mathbf R/\mathbf Z\) 的任意非平凡同态时，双线性型 \[ (x_1,\dots,x_n)\cdot(\xi_1,\dots,\xi_n):=\phi(x_1\xi_1+\cdots+x_n\xi_n) \] 是对称且非退化的（例如当 \(F=\mathbf Z_p\) 时可取 \(\phi(x):=x/p\)）。这个特定的选择还有一个有用的额外性质：对所有 \(a\in F\) 与 \(x,\xi\in Z\)，有 \(a\xi\cdot x=\xi\cdot ax\)。
动手算（\(\mathbf Z_5\) 上的配对） 取 \(N=5\)，配对 \(x\cdot\xi=\dfrac{x\xi}{5}\bmod 1\)。
  1. \(2\cdot 3=\dfrac{6}{5}=1\tfrac15\equiv\dfrac15\)（扔掉整数部分 \(1\)）。
  2. 验证对加法是同态：\((2+4)\cdot 3=6\cdot3=1\cdot3\)（因为 \(6\equiv1\bmod5\)）\(=\dfrac35\)；而 \(2\cdot3+4\cdot3=\dfrac65+\dfrac{12}{5}=\dfrac{18}{5}\equiv\dfrac35\)。两者相符。
  3. 验证非退化：取非零 \(\xi=1\)，则 \(x\mapsto \dfrac{x}{5}\) 在 \(x=1,2,3,4\) 处取 \(\tfrac15,\tfrac25,\tfrac35,\tfrac45\)，不恒为零。对每个非零 \(\xi\) 都如此，故非退化。
引理 4.3（双线性型的存在性） 每个有限加法群 \(Z\) 都至少有一个非退化对称双线性型。
证明. 由推论 3.8 我们知道，每个有限加法群都是若干个循环群的直和。我们已在例 4.2 中看到，每个循环群都带有一个对称非退化的双线性型。最后，注意到：若 \(Z_1\) 与 \(Z_2\) 各自带有对称非退化的双线性型，则它们的直和 \(Z_1\oplus Z_2\) 也带有一个对称非退化的双线性型，由 \[ (\xi_1,\xi_2)\cdot(x_1,x_2):=\xi_1\cdot x_1+\xi_2\cdot x_2 \] 给出。结论随之成立。♦

这条证明是“搭积木”：把大群拆成循环群（结构定理），每块循环群已经会配（例 4.2），再说明拼起来的直和也会配。下面把“为什么直和的配对仍非退化”补一句：若 \((\xi_1,\xi_2)\neq 0\)，则 \(\xi_1,\xi_2\) 中至少有一个非零，不妨设 \(\xi_1\neq0\)，则取合适的 \(x_1\) 使 \(\xi_1\cdot x_1\neq0\)、并令 \(x_2=0\)，整个配对就非零。

注记 4.4 一个给定的加法群 \(Z\) 一般有多个双线性型（见习题 4.1.10），但从傅里叶分析的角度看，它们全都是等价的1。对称性带来一些次要的美学上的好处，但对傅里叶理论并非必需，因为物理空间变量与频率空间变量通常扮演完全不同的角色。

1 看待这件事的一种方式是：\(\hat Z\) 与 \(Z\) 之间的等同是非典范的，本应把频率变量放进 \(\hat Z\) 而不是 \(Z\)。这终究是更正确的观点；不过既然我们通常工作在像循环群 \(\mathbf Z_N\) 这样非常具体的情形里（那里确有一个标准的等同），我们在此选择依赖双线性型的方法，而非抽象的方法。

此后，我们固定一个有限加法群 \(Z\)，并为它配上一个非退化对称双线性型 \(\xi\cdot x\)；在实践中我们通常使用例 4.2 中的两个例子之一。

4.1.2　“遍历”记号：期望与密度

为了做傅里叶分析，采用下面这套“遍历（ergodic）”记号会很方便。用 \(\mathbf C^Z\) 表示所有复值函数 \(f:Z\to\mathbf C\) 构成的空间。若 \(f\in\mathbf C^Z\)，我们把 \(f\) 的均值或期望定义为 \[ \mathbf E_Z(f)=\mathbf E_{x\in Z}f(x):=\frac{1}{|Z|}\sum_{x\in Z}f(x). \] 类似地，若 \(A\subseteq Z\)，我们把 \(A\) 的密度或概率定义为 \[ \mathbf P_Z(A)=\mathbf P_{x\in Z}(x\in A):=\mathbf E_Z(1_A)=\frac{|A|}{|Z|}. \] 我们可以把这套记号推广到 \(Z\) 之外的其他有限非空定义域，例如 \[ \mathbf E_{x\in A,\,y\in B}f(x,y):=\frac{1}{|A||B|}\sum_{x\in A,\,y\in B}f(x,y). \] 这套记号不仅暗示了傅里叶分析、遍历理论与概率论之间的联系，而且还有用地把一堆 \(|Z|\) 的归一化幂次藏到视线之外——否则这些因子会把估计式弄得很杂乱。一般来说，我们对物理变量使用这套遍历记号，而对频率变量则使用离散记号 \(\sum_{\xi\in Z}f(\xi)\) 与 \(|A|\)（不带归一化的 \(|Z|\) 因子）。

我们还将大量依赖指数映射 \(e:\mathbf R/\mathbf Z\to\mathbf C\)，其定义为 \[ e(\theta):=e^{2\pi i\theta}.\tag{4.1} \]

关键直觉：\(e(\theta)\) 把“小数部分 \(\theta\)”绕到单位圆上的一点。\(\theta=0\) 对应 \(1\)；\(\theta=\tfrac12\) 对应 \(-1\)；\(\theta=\tfrac14\) 对应 \(i\)。因为 \(e(\theta+1)=e(\theta)\)，所以它在 \(\mathbf R/\mathbf Z\)（模 \(1\)）上是良定义的——这正是我们让配对取值在 \(\mathbf R/\mathbf Z\) 里的原因。

\(e(0)=1\) \(e(1/5)\) \(e(2/5)\) \(e(3/5)\) \(e(4/5)\) \(N=5\)：\(e(k/5)\) 是 5 个等分单位圆的点（五次单位根）
指数映射 \(e(\theta)=e^{2\pi i\theta}\)：把 \(\mathbf Z_5\) 上的配对值 \(0,\tfrac15,\tfrac25,\tfrac35,\tfrac45\) 送到单位圆上 5 个均匀分布的点。它们之和为 \(0\)——这是下一条正交性引理的几何根源。

4.1.3　正交性与特征

下面两条正交性性质构成了傅里叶分析的基础。

引理 4.5（正交性） 对任意 \(\xi,\xi'\in Z\)，有 \[ \mathbf E_{x\in Z}\,e(\xi\cdot x)\overline{e(\xi'\cdot x)}=\mathbf I(\xi=\xi'), \] 并且对任意 \(x,x'\in Z\)，有 \[ \sum_{\xi\in Z}e(\xi\cdot x)\overline{e(\xi\cdot x')}=|Z|\,\mathbf I(x=x'). \] （这里 \(\mathbf I(\cdot)\) 是指示量：命题为真取 \(1\)，为假取 \(0\)。）
证明. 我们只证第一个恒等式，第二个类似。由于 \(e(\xi\cdot x)\overline{e(\xi'\cdot x)}=e\big((\xi-\xi')\cdot x\big)\)，只需证明 \(\xi'=0\) 的情形，即只需证明 \[ \mathbf E_{x\in Z}\,e(\xi\cdot x)=\mathbf I(\xi=0). \] 在 \(\xi=0\) 时这是显然的（被求平均的全是 \(e(0)=1\)）。若 \(\xi\neq0\)，则由非退化性，存在 \(h\in Z\) 使得 \(e(\xi\cdot h)\neq1\)。把 \(x\) 平移 \(h\)（这只是把求和的项重新排序，不改变平均值），于是 \[ \mathbf E_{x\in Z}\,e(\xi\cdot x)=\mathbf E_{x\in Z}\,e(\xi\cdot(x+h))=e(\xi\cdot h)\,\mathbf E_{x\in Z}\,e(\xi\cdot x), \] 因此 \(\big(1-e(\xi\cdot h)\big)\,\mathbf E_{x\in Z}\,e(\xi\cdot x)=0\)。由于 \(e(\xi\cdot h)\neq1\)，得 \(\mathbf E_{x\in Z}\,e(\xi\cdot x)=0=\mathbf I(\xi=0)\)，正如所求。♦
分步看“平移技巧”为什么管用（\(\mathbf Z_5\)） 取 \(\xi=1\)，则 \(S:=\sum_{x=0}^{4}e(x/5)\) 是上图 5 个点之和。
  1. 取 \(h=1\)，则 \(e(\xi\cdot h)=e(1/5)\neq1\)。
  2. 把每个点旋转 \(e(1/5)\)（即 \(x\to x+1\)）后，5 个点还是原来那 5 个点，只是换了名字，所以和不变：\(S=e(1/5)\,S\)。
  3. 于是 \((1-e(1/5))S=0\)，而 \(1-e(1/5)\neq0\)，故 \(S=0\)。一组均匀分布在圆上的单位根，向量首尾相接刚好回到原点。
这正是“非零频率的平均为零”的几何画面。

对每个 \(\xi\in Z\)，我们可以定义相应的特征（character）\(e_\xi\in\mathbf C^Z\)，其定义为 \(e_\xi(x):=e(\xi\cdot x)\)。上面的引理表明，关于复希尔伯特空间结构 \[ \langle f,g\rangle_{\mathbf C^Z}:=\mathbf E_Z(f\bar g)=\mathbf E_{x\in Z}f(x)\overline{g(x)}, \] 这些 \(e_\xi\) 构成一个规范正交系（orthonormal system）。由于特征的个数 \(|Z|\) 等于空间的维数 \(|Z|\)，我们看到这个系实际上是一个完备的规范正交系。这促使我们给出如下定义。

“规范正交基”三个字逐字翻译成有限维线性代数的话：在 \(|Z|\) 维的复向量空间 \(\mathbf C^Z\) 里，\(\{e_\xi\}\) 就像 \(\mathbf R^n\) 里的标准坐标轴 \(\hat e_1,\dots,\hat e_n\)——两两垂直、长度为 \(1\)、个数正好等于维数，所以任何函数都能唯一地写成它们的线性组合。傅里叶变换做的事，就是把函数“在这组轴上分解、读出每根轴方向的坐标”。

\(e_{\xi_1}\) \(e_{\xi_2}\) 任意 \(f\) \(\hat f(\xi)=\langle f,e_\xi\rangle\) 就是 \(f\) 在 \(e_\xi\) 这根“轴”上的投影坐标
特征 \(e_\xi\) 两两正交、长度为 \(1\)、个数等于维数，因此构成完备规范正交基；傅里叶系数 \(\hat f(\xi)\) 是 \(f\) 沿该轴的坐标。
定义 4.6（傅里叶变换） 若 \(f\in\mathbf C^Z\)，我们用公式 \[ \hat f(\xi):=\langle f,e_\xi\rangle_{\mathbf C^Z}=\mathbf E_{x\in Z}f(x)\overline{e(\xi\cdot x)} \] 定义其傅里叶变换 \(\hat f\in\mathbf C^Z\)。我们把 \(\hat f(\xi)\) 称为 \(f\) 在频率（或模式 mode）\(\xi\) 处的傅里叶系数。

由于 \(e_\xi\) 是一组完备的规范正交基，我们得到帕塞瓦尔恒等式（Parseval identity） \[ \big(\mathbf E_Z|f|^2\big)^{1/2}=\Big(\sum_{\xi\in Z}|\hat f(\xi)|^2\Big)^{1/2},\tag{4.2} \] 普朗歇尔定理（Plancherel theorem） \[ \langle f,g\rangle_{\mathbf C^Z}=\sum_{\xi\in Z}\hat f(\xi)\overline{\hat g(\xi)},\tag{4.3} \] 以及傅里叶反演公式（Fourier inversion formula） \[ f=\sum_{\xi\in Z}\hat f(\xi)\,e_\xi.\tag{4.4} \] 特别地，我们看到：两个函数相等，当且仅当它们在每个频率上的傅里叶系数都相同。换句话说，傅里叶变换是从 \(\mathbf C^Z\) 到 \(\mathbf C^Z\) 的一个双射（事实上，由 (4.2)、(4.3)，它是一个酉等距）。

这三条都是“正交基”的标准结论，逐条翻译为：(4.4) 反演——把 \(f\) 写成各坐标轴 \(e_\xi\) 的组合，系数就是坐标 \(\hat f(\xi)\)，正如 \(\mathbf R^n\) 里 \(v=\sum_i(v\cdot\hat e_i)\hat e_i\)；(4.2) 帕塞瓦尔——“勾股定理”，函数长度的平方等于各坐标平方之和；(4.3) 普朗歇尔——“内积在两个表象里相等”，是帕塞瓦尔的极化版本。

例（在 \(\mathbf Z_3\) 上亲手算一次傅里叶变换） 取 \(Z=\mathbf Z_3\)，配对 \(\xi\cdot x=\xi x/3\)。记 \(\omega:=e(1/3)=e^{2\pi i/3}\)，满足 \(1+\omega+\omega^2=0\)。设函数 \(f(0)=1,\ f(1)=0,\ f(2)=0\)（即 \(f=1_{\{0\}}\)）。
  1. \(\hat f(\xi)=\dfrac13\sum_{x}f(x)\overline{e(\xi x/3)}=\dfrac13 f(0)\cdot1=\dfrac13\)，对所有 \(\xi=0,1,2\) 都成立。
  2. 所以 \(\hat f\equiv\tfrac13\)：一个集中在一点的函数，其傅里叶变换在所有频率上均匀铺开。
  3. 验证反演 (4.4)：\(\sum_\xi\hat f(\xi)e_\xi(0)=\tfrac13(1+1+1)=1=f(0)\)；在 \(x=1\) 处 \(\tfrac13(1+\omega+\omega^2)=0=f(1)\)。✓
  4. 验证帕塞瓦尔 (4.2)：左 \(\mathbf E|f|^2=\tfrac13(1+0+0)=\tfrac13\)；右 \(\sum_\xi|\hat f(\xi)|^2=3\cdot\tfrac19=\tfrac13\)。两边相等。✓

由引理 4.5 我们看到，一个特征 \(e_\xi\) 的傅里叶系数恰好是一个克罗内克 delta 函数： \[ \widehat{e_\xi}(\xi')=\mathbf I(\xi=\xi'). \] 特别地，\(\hat 1(\xi)=\mathbf I(\xi=0)\)（这里 \(1=e_0\) 是常值函数 \(1\)）。

在傅里叶变换的加性理论中，零频率 \(\xi=0\) 扮演着特殊的角色。这是因为零傅里叶系数与期望是同一个概念： \[ \hat f(0)=\langle f,1\rangle_{\mathbf C^Z}=\mathbf E_Z(f).\tag{4.5} \]

为什么零频率就是平均？因为 \(e_0(x)=e(0\cdot x)=e(0)=1\) 是常值函数，沿这根“轴”的坐标 \(\hat f(0)=\mathbf E_x f(x)\) 自然就是 \(f\) 的平均值。后面凡是看到“某物的平均”，都可以翻译成“它的零频率系数”。

4.1.4　正交补与子群

若 \(S\) 是 \(Z\) 的任意子集，定义 \(S\) 的正交补（orthogonal complement）\(S^\perp\subseteq Z\) 为集合 \[ S^\perp:=\{\xi\in Z:\ \xi\cdot x=0\ \text{对所有}\ x\in S\}. \] 容易验证 \(S^\perp\) 是 \(Z\) 的一个子群。此外，当 \(G\) 是一个子群时，有令人愉快的恒等式 \[ \widehat{1_G}=\mathbf P_Z(G)\,1_{G^\perp};\tag{4.6} \] 见习题 4.1.6。对 (4.6) 应用 (4.2)，我们特别得到 \[ |G|\,|G^\perp|=|Z|.\tag{4.7} \]

例（\(\mathbf Z_6\) 中的子群与正交补） 取 \(Z=\mathbf Z_6\)，\(\xi\cdot x=\xi x/6\)。设 \(G=\{0,2,4\}\)（偶数子群，\(|G|=3\)）。
  1. 求 \(G^\perp\)：要 \(\xi\cdot x=\dfrac{\xi x}{6}\equiv0\) 对所有 \(x\in\{0,2,4\}\)，即 \(\dfrac{2\xi}{6}\in\mathbf Z\)，得 \(\xi\in\{0,3\}\)。所以 \(G^\perp=\{0,3\}\)，\(|G^\perp|=2\)。
  2. 核对 (4.7)：\(|G||G^\perp|=3\times2=6=|Z|\)。✓ 子群越大，它的正交补越小，乘积恒为群的阶。
  3. 核对 (4.6)：\(\widehat{1_G}(\xi)=\dfrac16\sum_{x\in G}\overline{e(\xi x/6)}\)。当 \(\xi\in G^\perp\) 时三项都是 \(1\)，得 \(\tfrac36=\tfrac12=\mathbf P_Z(G)\)；当 \(\xi\notin G^\perp\) 时三项是均匀分布的单位根、和为 \(0\)。正好是 \(\mathbf P_Z(G)1_{G^\perp}\)。✓
\(|G^\perp|=2\) \(|G|=3\) 面积示意：\(|G|\times|G^\perp|=|Z|=6\)（\(G\) 越大 \(G^\perp\) 越小） \(Z=\mathbf Z_6\)
\(\mathbf Z_6\) 中 \(G=\{0,2,4\}\) 与 \(G^\perp=\{0,3\}\)：阶互补，\(|G||G^\perp|=|Z|\)（公式 4.7）。

4.1.5　卷积：把 \(A+B\) 翻译成乘法

我们现在引入卷积（convolution）这个根本概念，它把傅里叶变换与和集（sum set）理论联系起来。

定义 4.7（卷积） 若 \(f,g\in L^2(Z)\) 是随机变量，我们把它们的卷积 \(f*g\) 定义为随机变量 \[ f*g(x)=\mathbf E_{y\in Z}f(x-y)g(y)=\mathbf E_{y\in Z}f(y)g(x-y). \] 我们还把 \(f\) 的支撑（support）\(\operatorname{supp}(f)\) 定义为集合 \(\operatorname{supp}(f)=\{f\neq0\}=\{x\in Z:f(x)\neq0\}\)。

卷积对和集的重要意义，体现在显然的包含关系 \[ \operatorname{supp}(f*g)\subseteq\operatorname{supp}(f)+\operatorname{supp}(g) \] 之中，尤其体现在恒等式 \[ A+B=\operatorname{supp}(1_A*1_B) \] 之中。事实上，我们有更精确的陈述 \[ 1_A*1_B(x)=\mathbf P_Z\big(A\cap(x-B)\big).\tag{4.8} \]

把 (4.8) 翻成大白话：\(1_A*1_B(x)\) 数的是“有多少种方式把 \(x\) 写成 \(x=a+b\)，其中 \(a\in A,\ b\in B\)”（再除以 \(|Z|\) 归一化）。因为 \(x=a+b\) 等价于 \(a=x-b\in A\) 且 \(a\in A\)，即 \(a\in A\cap(x-B)\)。所以：只要存在一种写法，\(x\) 就落在 \(A+B\) 里、卷积非零；一种写法都没有，卷积为零。这就是 \(A+B=\operatorname{supp}(1_A*1_B)\) 的全部含义——“能否相加得到 \(x\)”被翻译成了“卷积在 \(x\) 处是否为零”。

\(A=\{0,1,3\}\) \(B=\{0,2\}\)（在 \(\mathbf Z_6\) 中） \(x\) 0 1 2 3 … 写法数 1 1 1 2 … 例：\(x=3\) 有两种写法 \(3=3+0=1+2\)，故卷积在 3 处最大（\(=2/6\)）。 凡写法数 \(>0\) 的 \(x\) 合起来 \(=A+B\)；其余 \(x\) 卷积为 0。
\(1_A*1_B(x)\) 数“\(x=a+b\) 的写法个数”（再除 \(|Z|\)）。支撑集（写法数 \(>0\) 的那些 \(x\)）正好是和集 \(A+B\)。

傅里叶变换与卷积的关联，在于容易验证的恒等式 \[ \widehat{f*g}=\hat f\cdot\hat g.\tag{4.9} \] 在零频率处应用 (4.9)，我们得到基本公式 \[ \mathbf E_Z(f*g)=(\mathbf E_Z f)\cdot(\mathbf E_Z g).\tag{4.10} \] 特别地，若 \(f\) 或 \(g\) 的均值为零，则 \(f*g\) 的均值也为零。

(4.9) 是整套傅里叶方法的核心引擎，可以一句话记住：“卷积变乘积”。物理空间里很难算的卷积（要遍历所有写法 \(x=a+b\)），到了频率空间就变成逐点相乘。研究 \(A+B\) 的大小、结构，于是可以先做傅里叶变换、在频率端把问题做完、再变回来。这正是后续章节反复使用的策略。

作为 (4.9) 的一个推论，我们看到卷积是双线性的、对称的、结合的。我们还有 (4.9) 的对偶版本，即公式 \[ \widehat{fg}(\xi)=\sum_{\eta\in Z}\hat f(\eta)\hat g(\xi-\eta),\tag{4.11} \] 它把逐点乘积变回卷积；这些恒等式的验证留作习题。

为什么 (4.9) 成立（一行推导的展开）
  1. 按定义 \(\widehat{f*g}(\xi)=\mathbf E_x\big[(f*g)(x)\big]\overline{e(\xi\cdot x)}=\mathbf E_x\,\mathbf E_y f(x-y)g(y)\,\overline{e(\xi\cdot x)}\)。
  2. 令 \(x=u+y\)（对固定 \(y\) 把 \(x\) 换成 \(u\)），并用配对的同态性 \(\xi\cdot x=\xi\cdot u+\xi\cdot y\)，故 \(\overline{e(\xi\cdot x)}=\overline{e(\xi\cdot u)}\,\overline{e(\xi\cdot y)}\)。
  3. 分离求和：\(=\big(\mathbf E_u f(u)\overline{e(\xi\cdot u)}\big)\big(\mathbf E_y g(y)\overline{e(\xi\cdot y)}\big)=\hat f(\xi)\hat g(\xi)\)。♦
关键就一处：指数对加法拆成乘法 \(e(\xi\cdot(u+y))=e(\xi\cdot u)e(\xi\cdot y)\)，于是双重求和分家成两个独立的傅里叶系数。

习题

在下面的习题中，\(Z\) 是一个固定的有限加法群，并配有一个固定的对称非退化双线性型 \(\cdot\)。

习题
  1. 4.1.1　设 \(\hat Z\) 是由从 \(Z\) 到 \(\mathbf R/\mathbf Z\) 的所有同态构成的加法群。证明：把频率 \(\xi\in Z\) 与同态 \(x\mapsto\xi\cdot x\) 等同起来，给出从 \(Z\) 到 \(\hat Z\) 的一个同构。
  2. 4.1.2　把特征定义为任意满足 \(\chi(0)=1\) 且对所有 \(x,y\in Z\) 有 \(\chi(x+y)=\chi(x)\chi(y)\) 的映射 \(\chi:Z\to\mathbf C\)。证明所有特征构成的集合恰好是 \(\{e_\xi:\xi\in Z\}\)。
  3. 4.1.3　证明：对任意 \(\xi\in Z\)，\(e_\xi\) 的取值都是 \(|Z|\) 次单位根。
  4. 4.1.4　把线性相位函数定义为任意满足下述性质的映射 \(\phi:Z\to\mathbf R/\mathbf Z\)： \[ \phi(x+h_1+h_2)-\phi(x+h_1)-\phi(x+h_2)+\phi(x)=0\quad\text{对所有 }x,h_1,h_2\in Z. \] 证明：\(\phi:Z\to\mathbf R/\mathbf Z\) 是线性相位函数当且仅当存在 \(\xi\in Z\) 与 \(c\in\mathbf R/\mathbf Z\) 使得 \(\phi(x)=\xi\cdot x+c\) 对所有 \(x\) 成立。（映射 \(\phi\) 也是一个二阶弗赖曼同态；见定义 5.21。）
  5. 4.1.5　设 \(x\) 是从 \(Z\) 中均匀随机选取的元素。证明随机变量 \(\{e_\xi(x):\xi\in Z\}\) 两两独立，且对 \(\xi\neq0\) 方差为 \(1\)、均值为 \(0\)，对 \(\xi=0\) 方差为 \(0\)、均值为 \(1\)。利用这一点以及 (1.9)、(4.4) 给出 (4.2) 的另一种证明。
  6. 4.1.6　证明 (4.6)。
  7. 4.1.7　设 \(f:Z\to\mathbf C\)。若 \(H\) 是 \(Z\) 的子群，且 \(g:=f1_H\)，证明 \[ \hat g(\xi)=\mathbf E_{\eta\in H^\perp}\hat f(\xi+\eta)\quad\text{对所有 }\xi\in Z, \] 并特别地推出泊松求和公式 \[ \mathbf E_{x\in H}f(x)=\mathbf E_{\xi\in H^\perp}\hat f(\xi). \] 反方向，若 \(h=f*\tfrac{1}{\mathbf P_Z(H)}1_H\) 是 \(f\) 在 \(H\) 的陪集上的平均，即 \(h(x):=\mathbf E_{y\in H}f(x+y)\)，证明 \(\hat h=\hat f\cdot 1_{H^\perp}\)。
  8. 4.1.8　若 \(\phi:Z\to Z\) 是 \(Z\) 的群同构，则存在唯一的群同构 \(\phi^\dagger:Z\to Z\)，称为 \(\phi\) 的伴随，使得 \(\xi\cdot\phi(x)=\phi^\dagger(\xi)\cdot x\) 对所有 \(x,\xi\in Z\) 成立。此外，若 \(g(x)=f(\phi(x))\) 对所有 \(x\in Z\) 成立，则 \(\hat g(x)=\hat f((\phi^\dagger)^{-1}(x))\) 对所有 \(x\in Z\) 成立。
  9. 4.1.9　若 \(\phi:Z\to Z\) 与 \(\psi:Z\to Z\) 是群同构，证明 \((\phi\circ\psi)^\dagger=\psi^\dagger\circ\phi^\dagger\)。
  10. 4.1.10　设 \(\bullet:Z\times Z\to\mathbf R/\mathbf Z\) 与 \(\tilde\bullet:Z\times Z\to\mathbf C\) 是有限加法群 \(Z\) 上的两个非退化对称双线性型。证明存在一个自伴的群同构 \(\phi:Z\to Z\) 使得 \(\xi\,\tilde\bullet\,x=\xi\bullet\phi(x)=\phi^\dagger(\xi)\bullet x\) 对所有 \(x,\xi\in Z\) 成立。这表明：所有傅里叶变换在 \(x\) 或 \(\xi\) 变量的同构意义下都是等价的。
  11. 4.1.11　证明 (4.9) 与 (4.11)。
  12. 4.1.12　设 \(x\) 是从 \(Z\) 中均匀随机选取的元素，且 \(\xi_1,\dots,\xi_n\in Z\)。证明随机变量 \(e_{\xi_1}(x),\dots,e_{\xi_n}(x)\) 联合独立，当且仅当由 \(\xi_1,\dots,\xi_n\) 生成的群 \(\langle\xi_1,\dots,\xi_n\rangle\) 的阶等于 \(\operatorname{ord}(\xi_1)\cdots\operatorname{ord}(\xi_n)\)。
  13. 4.1.13　设 \(G,H\) 是 \(Z\) 的两个子群。证明 \((G+H)^\perp=G^\perp\cap H^\perp\)，\((G\cap H)^\perp=G^\perp+H^\perp\)，以及 \(d(G^\perp,H^\perp)=d(G,H)\)，其中 \(d\) 是定义 2.5 中的鲁萨距离。这或许有助于解释习题 2.3.11 的估计中 \(G+H\) 与 \(G\cap H\) 所呈现的对称性。

返回 全书目录