Tao–Vu · 加性组合学 · 第 9 章 代数方法

9.8　分圆域与不确定性原理Cyclotomic fields, and the uncertainty principle

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

本节目标本节要做两件事。第一，复习一套纯代数的工具——分圆域与分圆多项式 \(\Phi_n\)，它们能精确控制“单位根的整系数多项式表达式什么时候为零、它们的整数取值能被哪个素数整除”。第二，把这套工具用到 \(\mathbb{Z}_p\)（\(p\) 为素数）上的傅里叶变换，得到一条很强的不确定性原理：一个函数 \(f\) 与它的傅里叶变换 \(\hat f\) 不可能同时“很集中”，它们的支撑大小之和至少是 \(p+1\)。作为回报，我们还会用它再次证明 Cauchy–Davenport 不等式。核心链条是：
分圆多项式不可约 \(\Rightarrow\) Chebotarev 引理（广义 Vandermonde 行列式非零）\(\Rightarrow\) 不确定性原理。

我们现在复习一些分圆域 \(\mathbb{Q}(\omega)\) 的初等理论，并把它应用于在 \(\mathbb{Z}_p\) 上的傅里叶变换，从而得到一条不确定性原理。

分圆域与分圆多项式

定义 9.47（分圆域）设 \(n\ge 1\) 为任意正整数。一个 \(n\) 次单位根是指任意满足 \(\omega^n=1\) 的复数 \(\omega\in\mathbb{C}\)。一个 \(n\) 次单位根 \(\omega\) 称为本原的（primitive），如果对任何 \(1\le m\(n\) 阶分圆域定义为把一个本原 \(n\) 次单位根添加（adjoin）到有理数域 \(\mathbb{Q}\) 上所得到的域 \(\mathbb{Q}(\omega)\)。我们把\(n\) 次分圆多项式 \(\Phi_n\in\mathbb{C}[z]\) 定义为 \[\Phi_n(z):=\prod_{\omega}(z-\omega),\] 其中 \(\omega\) 取遍所有本原 \(n\) 次单位根。

容易看出，对每个 \(n\)，恰有 \(\varphi(n)\) 个本原单位根（\(\varphi\) 是欧拉函数），并且它们彼此都是对方的幂。于是对每个阶 \(n\)，分圆域 \(\mathbb{Q}(\omega)\) 实际上只有一个。特别地，\(\Phi_n\) 是一个次数为 \(\varphi(n)\) 的首一（monic，即最高次项系数为 \(1\)）多项式。\(\Phi_n\) 的更多基本性质如下。

例：小 \(n\) 的单位根 \(n\) 次单位根就是把单位圆等分成 \(n\) 份的那些点 \(e^{2\pi i k/n}\)（\(k=0,1,\dots,n-1\)）。哪些是本原的？正是那些 \(k\) 与 \(n\) 互素的点（这样的 \(k\) 恰有 \(\varphi(n)\) 个）。
  1. \(n=1\)：只有 \(\omega=1\)，本原根 \(\{1\}\)，\(\varphi(1)=1\)。
  2. \(n=2\)：\(\{1,-1\}\)，本原根只有 \(-1\)，\(\varphi(2)=1\)。
  3. \(n=3\)：\(\{1,\omega,\omega^2\}\)，\(\omega=e^{2\pi i/3}\)；本原根是 \(\omega,\omega^2\)（不含 \(1\)），\(\varphi(3)=2\)。
  4. \(n=4\)：\(\{1,i,-1,-i\}\)；本原根是 \(i,-i\)（\(-1\) 是 \(2\) 次根、\(1\) 是 \(1\) 次根，都不本原），\(\varphi(4)=2\)。
  5. \(n=6\)：六个点中，本原的是 \(e^{\pm\pi i/3}\)（即 \(k=1,5\)），\(\varphi(6)=2\)。
k=0 k=1 本原 k=2 k=3 k=4 k=5 本原 蓝点：非本原（是更小阶的单位根）；橙点：本原 6 次单位根
六次单位根 \(e^{2\pi i k/6}\)。本原根是 \(k\) 与 \(6\) 互素的两个，即 \(k=1,5\)；其余 \(k=0,2,3,4\) 分别是 \(1,3,2,2\) 次单位根。所以 \(\Phi_6\) 只由橙点贡献因子。
例：小 \(n\) 的分圆多项式 把本原根对应的 \((z-\omega)\) 乘起来： \[\Phi_1=z-1,\quad \Phi_2=z+1,\quad \Phi_3=z^2+z+1,\quad \Phi_4=z^2+1,\quad \Phi_6=z^2-z+1.\] 以 \(\Phi_4\) 为例分步算：本原 \(4\) 次根是 \(i\) 和 \(-i\)，故 \[\Phi_4(z)=(z-i)(z+i)=z^2-(i)(-i)=z^2+1.\] 注意结果系数都是整数——这正是下面引理 9.48 要证的一般现象。
引理 9.48 \(\Phi_n\) 具有整数系数（因此 \(\Phi_n\in\mathbb{Z}[z]\)），并且在 \(\mathbb{Z}[z]\) 中不可约。此外，当 \(n\) 是素数幂 \(n=p^k\) 时 \(\Phi_n(1)=p\)；\(\Phi_1(1)=0\)；其余情形 \(\Phi_n(1)=1\)。
证明. 我们首先由因式定理观察到，对任意 \(n\ge 1\)， \[z^n-1=\prod_{\omega:\,\omega^n=1}(z-\omega).\] 由于每个 \(n\) 次单位根都是某个 \(d\)（\(d\mid n\)）的本原 \(d\) 次单位根，我们把右边按“它本原地属于哪个阶 \(d\)”分组，得到 \[\begin{equation}\tag{9.21}z^n-1=\prod_{d\mid n}\Phi_d(z).\end{equation}\] 于是可以通过从 \(z^n-1\) 中除去 \(\prod_{d\mid n;\,d
由于 \((z^n-1)/\Phi_1(z)=(z^n-1)/(z-1)\) 当 \(z\to 1\) 时趋于 \(n\)，我们得到公式 \[n=\prod_{d\mid n;\,d>1}\Phi_d(1).\] 取对数并使用习题 9.4.1，我们对所有 \(n\ge 1\) 得出 \[\sum_{d\mid n;\,d>1}\Lambda(d)=\sum_{d\mid n;\,d>1}\log\Phi_d(1),\] 其中当 \(d\) 是素数幂 \(d=p^k\)（某个 \(k\ge 1\)）时 \(\Lambda(d):=\log p\)，否则 \(\Lambda(d)=0\)（参见习题 1.10.6）。再对 \(n\) 作一个简单归纳便可证明：对所有 \(n>1\) 有 \(\Phi_n(1)=e^{\Lambda(n)}\)，这正给出了关于 \(\Phi_n(1)\) 的所求公式。

现在证明不可约性。当 \(n\) 为素数时，这可由 Eisenstein 判别法轻松验证（习题 9.8.3），但一般情形更微妙。我们采用 Gauss 的一个论证。反设 \(\Phi_n\) 在 \(\mathbb{Z}[z]\) 中可约，那么我们可以把所有本原 \(n\) 次单位根划分成两个不相交的非空类 \(A\) 与 \(B\)，使得首一多项式 \[f(z):=\prod_{\omega\in A}(z-\omega),\qquad g(z):=\prod_{\omega\in B}(z-\omega)\] 都落在 \(\mathbb{Z}[z]\) 中。当然有 \(\Phi_n=fg\)。由于任意两个本原 \(n\) 次根都是彼此的幂，我们能找到一个 \(\omega\in A\)，使得对某整数 \(m\) 有 \(\omega^m\in B\)。把 \(m\) 分解为素数并用反证法论证，事实上我们可以定位到一个素数 \(p\) 和一个 \(\omega\in A\)，使得 \(\omega^p\in B\)。这意味着多项式 \(f(z)\) 与 \(g(z^p)\) 有一个公共根，从而由欧几里得算法可以找到一个非平凡的首一多项式 \(h(z)\in\mathbb{Z}[z]\)，它同时整除 \(f(z)\) 与 \(g(z^p)\)。这就推出 \(\Phi_n(z^p)=f(z^p)g(z^p)\) 含有因子 \(h(z^p)h(z)\)；再由 (9.21) 可见 \(z^{np}-1\) 也含有因子 \(h(z^p)h(z)\)。

现在我们到有限域 \(\mathbb{F}_p\) 中工作。在那里我们有 \(h(z^p)=h(z)^p\) 以及 \((z^n-1)^p=z^{np}-1\)（参见习题 9.4.7），因此 \((z^n-1)^p\) 含有因子 \(h(z)^{p+1}\)；特别地，在 \(\mathbb{F}_p\) 中 \(z^n-1\) 必含有因子 \(h(z)^2\)（参见习题 9.4.1）。取形式导数，这就意味着 \(z^n-1\) 与 \(nz^{n-1}\) 有公共因子 \(h(z)\)；但由欧几里得算法以及 \(n\not\equiv 0\pmod p\) 这一事实可知，这两个多项式的最大公因式为 \(1\)，矛盾。♦
把证明拆细：四块在做什么
  1. 整系数：用 (9.21) 这条“拼图”——\(z^n-1\) 恰好等于所有 \(\Phi_d\)（\(d\mid n\)）的乘积。已知小的 \(\Phi_d\) 都是整系数首一，用整数多项式的长除法把它们除掉，剩下的 \(\Phi_n\) 仍是整系数首一。
  2. \(\Phi_n(1)\) 的取值：在 (9.21) 里把 \(z\to 1\)，\(z^n-1\) 与 \((z-1)=\Phi_1\) 都趋于 \(0\)，约掉这个零因子后两边取极限得 \(n=\prod_{d\mid n,d>1}\Phi_d(1)\)。取对数后这是“von Mangoldt 函数”\(\Lambda\) 的累加恒等式 \(\sum_{d\mid n}\Lambda(d)=\log n\) 的翻版，反解出单个 \(\Phi_n(1)=e^{\Lambda(n)}\)。
  3. 不可约（核心）：反设可分成 \(f,g\)。利用“本原根互为幂”找到素数 \(p\) 与 \(\omega\)，使 \(\omega\in A\) 而 \(\omega^p\in B\)。这制造出 \(f(z)\) 与 \(g(z^p)\) 的公共根，进而一个公因式 \(h\)。
  4. 降到 \(\mathbb{F}_p\) 取矛盾：模 \(p\) 后冻结律 \(h(z^p)=h(z)^p\) 让 \(h^2\) 整除 \(z^n-1\)，即 \(z^n-1\) 有重因式。但有重因式 \(\Leftrightarrow\) 与自己的导数有公因式；\(\gcd(z^n-1,\,nz^{n-1})=1\)（因 \(p\nmid n\)，\(n\) 可逆，而 \(z^n-1\) 常数项 \(-1\neq 0\)），无重因式，矛盾。
例：验证 \(\Phi_n(1)\) 公式与 (9.21)
  1. \(\Phi_3(1)=1^2+1+1=3=p\)（\(3=3^1\) 是素数幂）。✓
  2. \(\Phi_4(1)=1^2+1=2=p\)（\(4=2^2\) 是素数幂，\(p=2\)）。✓
  3. \(\Phi_6(1)=1^2-1+1=1\)（\(6=2\cdot3\) 不是素数幂）。✓
  4. 验证 (9.21) 对 \(n=6\)：\(\Phi_1\Phi_2\Phi_3\Phi_6=(z-1)(z+1)(z^2+z+1)(z^2-z+1)\)。先 \((z-1)(z+1)=z^2-1\)，再 \((z^2+z+1)(z^2-z+1)=z^4+z^2+1\)，最后 \((z^2-1)(z^4+z^2+1)=z^6-1\)。✓

单位根表达式的非零判据

作为引理 9.48 的一个推论，我们得到一条关于“单位根的多项式表达式何时非零”的有用判据，它在定理 9.20 的证明中已被利用过。

引理 9.49 设 \(p\) 为素数，\(q\) 是 \(p\) 的一个幂。设 \(P\in\mathbb{Z}[t_1,\dots,t_k]\) 是一个整系数多项式，使得对某些 \(q\) 次单位根 \(z_1,\dots,z_k\) 有 \(P(z_1,\dots,z_k)=0\)。那么整数 \(P(1,\dots,1)\) 能被 \(p\) 整除。
证明. 设 \(\omega\) 是一个本原 \(q\) 次单位根，那么 \(z_i=\omega^{n_i}\) 对某些整数 \(n_i\) 成立。若令 \(Q(t):=P(t^{n_1},\dots,t^{n_k})\)，则 \(Q(\omega)=0\)。于是 \(Q(t)\) 与不可约多项式 \(\Phi_q(t)\) 共享一个根，因此 \(\Phi_q(t)\) 必是 \(Q(t)\) 的因子。从而 \(Q(1)=P(1,\dots,1)\) 含有因子 \(\Phi_q(1)=p\)。♦
例：判据怎么用 取 \(p=q=3\)，三个立方根 \(z_1=1,\ z_2=\omega,\ z_3=\omega^2\)（\(\omega=e^{2\pi i/3}\)），多项式 \(P(t_1,t_2,t_3)=t_1+t_2+t_3\)。
  1. 代入：\(P(z_1,z_2,z_3)=1+\omega+\omega^2=0\)（这是因为 \(1+\omega+\omega^2=\Phi_3(\omega)+ \ldots\)，更直接地 \(\frac{\omega^3-1}{\omega-1}=0\)）。所以前提满足。
  2. 结论断言 \(P(1,1,1)\) 被 \(p=3\) 整除。直接算 \(P(1,1,1)=1+1+1=3\)，确实被 \(3\) 整除。✓
直觉：单位根上“凑成零”的整系数关系，落回到 \(t_i=1\) 时不会随便取任何整数，它被锁死在 \(p\) 的倍数上——因为这种关系背后必然藏着不可约的 \(\Phi_q\)，而 \(\Phi_q(1)=p\)。

我们把这条引理用来证明关于广义 Vandermonde 行列式的一个非零结果。先需要一项系数计算。这里记号 \(\Delta_k\) 表示 Vandermonde 多项式 \[\Delta_k(x_1,\dots,x_k):=\prod_{1\le i

命题 9.50 设 \(n_1,\dots,n_k\) 是非负整数，令 \(P\in\mathbb{Z}[z_1,\dots,z_k]\) 为多项式 \[P(z_1,\dots,z_k)=\sum_{\pi\in S_k}\operatorname{sgn}(\pi)\prod_{i=1}^k z_i^{\,n_{\pi(i)}}\qquad(\text{参见 (9.3)}).\] 那么我们可以分解 \(P=\Delta_k\,Q\)，其中 \(Q\in\mathbb{Z}[z_1,\dots,z_k]\) 满足 \[Q(1,\dots,1)=\frac{\Delta_k(n_1,\dots,n_k)}{\Delta_k(1,\dots,k)}.\]
证明. 表达式 \(P(z_1,\dots,z_k)\) 也可解释为 \(k\times k\) 矩阵 \((z_i^{\,n_j})_{1\le i,j\le k}\) 的行列式。这特别表明：当任意两个 \(z_i\) 相等时 \(P\) 为零（行列式有两行相同）。用长除法除去诸因子 \(z_i-z_j\) 并应用定义 9.6，我们断定存在多项式 \(Q\in\mathbb{Z}[z_1,\dots,z_k]\) 使得 \(P=\Delta_k Q\)。

剩下要计算 \(Q(1,\dots,1)\)。为此引入归一化微分算子 \(D_i:=z_i\,\dfrac{d}{dz_i}\)，并考虑表达式 \(D_1^0 D_2^1\cdots D_k^{k-1}P(1,\dots,1)\)。我们把 \(P\) 分解为因子 \[P(z_1,\dots,z_k)=\prod_{1\le i不同的线性因子上才能给出非零项。但这意味着：\(D_k\) 那 \((k-1)\) 次求导必须落在某个 \(z_k-z_i\)（\(i♦
例：\(k=2\) 时把命题看穿 此时 \(S_2=\{\text{id},(12)\}\)， \[P(z_1,z_2)=z_1^{n_1}z_2^{n_2}-z_1^{n_2}z_2^{n_1}=\det\begin{pmatrix}z_1^{n_1}&z_1^{n_2}\\ z_2^{n_1}&z_2^{n_2}\end{pmatrix}.\] 而 \(\Delta_2(z_1,z_2)=z_2-z_1\)。命题说 \(P=(z_2-z_1)Q\)，且 \(Q(1,1)=\dfrac{\Delta_2(n_1,n_2)}{\Delta_2(1,2)}=\dfrac{n_2-n_1}{2-1}=n_2-n_1\)。
  1. 取 \(n_1=0,n_2=1\)：\(P=z_2-z_1=(z_2-z_1)\cdot 1\)，\(Q=1\)，\(Q(1,1)=1=n_2-n_1\)。✓
  2. 取 \(n_1=0,n_2=2\)：\(P=z_2^2-z_1^2=(z_2-z_1)(z_1+z_2)\)，\(Q=z_1+z_2\)，\(Q(1,1)=2=n_2-n_1\)。✓
关键收获：\(Q(1,1)=n_2-n_1\)。一般地 \(Q(1,\dots,1)=\Delta_k(n_1,\dots,n_k)/\Delta_k(1,\dots,k)\) 是一个有理数，它衡量“当所有变量取 \(1\) 时，广义 Vandermonde 相对普通 Vandermonde 的比值”——下面就靠它来判断行列式非零且不被 \(p\) 整除。

Chebotarev 引理

把命题 9.50 与引理 9.49 结合，我们得到

引理 9.51（Chebotarev 引理） 设 \(q=p^\alpha\) 为素数幂，设 \(1\le k

事实上，Chebotarev 引理之所以成立，是因为 \(\Delta_k(z_1,\dots,z_k)\) 非零，而 \(\Delta_k(n_1,\dots,n_k)\) 不被 \(p\) 整除。我们指出：尽管此结果由 Chebotarev 于 1926 年证明（见 [338]），它已被多次独立地重新发现和重新证明（[278]、[71]、[263]、[102]、[355]、[120]、[131]）。

为什么这两点就够了
  1. 该矩阵的行列式正是命题 9.50 里的 \(P(z_1,\dots,z_k)=\Delta_k(z_1,\dots,z_k)\,Q(z_1,\dots,z_k)\)。
  2. 第一个因子 \(\Delta_k(z_1,\dots,z_k)=\prod_{i
  3. 对第二个因子用引理 9.49：若 \(P(z_1,\dots,z_k)=0\)，则 \(p\mid P(1,\dots,1)=\Delta_k(1,\dots,k)Q(1,\dots,1)=\Delta_k(n_1,\dots,n_k)\)。但 \(\Delta_k(n_1,\dots,n_k)=\prod_{i不被 \(p\) 整除，且因 \(k
注意条件 \(k
例：一个具体的非零行列式 取 \(p=q=5\)，\(k=2<5\)。选两个不同的 \(5\) 次根 \(z_1=1,\ z_2=\zeta=e^{2\pi i/5}\)，指数 \(n_1=0,\ n_2=1\)（模 \(5\) 不同）。矩阵 \[\begin{pmatrix}z_1^{0}&z_1^{1}\\ z_2^{0}&z_2^{1}\end{pmatrix}=\begin{pmatrix}1&1\\ 1&\zeta\end{pmatrix},\quad \det=\zeta-1\neq 0.\] 若违反“模 \(p\) 互异”，比如 \(n_1=0,n_2=5\)（模 \(5\) 都是 \(0\)），则两列相同、行列式为零，结论失效——这说明条件是本质的。

不确定性原理

作为这条引理的一个推论，人们很容易建立下面这条关于 \(\mathbb{Z}_p\) 的不确定性原理。

定理 9.52 设 \(p\) 为素数。设 \(f:\mathbb{Z}_p\to\mathbb{C}\) 为一个函数，并设 \(\hat f:\mathbb{Z}_p\to\mathbb{C}\) 为它的傅里叶变换（使用标准双特征标 \(e(x,\xi)=\exp(2\pi i x\xi/p)\)）。那么 \[|\operatorname{supp}(f)|+|\operatorname{supp}(\hat f)|\ge p+1.\] 反过来，如果 \(A,B\) 是 \(\mathbb{Z}/p\mathbb{Z}\) 的两个非空子集，满足 \(|A|+|B|\ge p+1\)，那么存在一个函数 \(f\) 使得 \(\operatorname{supp}(f)=A\) 且 \(\operatorname{supp}(\hat f)=B\)。

我们把由引理 9.51 推出定理 9.52 留作习题 9.8.9。这个结果应与 (4.21) 作比较。

名词速记 \(\operatorname{supp}(f)=\{x:f(x)\neq 0\}\) 称为 \(f\) 的支撑，\(|\operatorname{supp}(f)|\) 是它非零位置的个数，衡量 \(f\) “有多集中”。不确定性原理说：\(f\) 与 \(\hat f\) 不能同时太集中，它们非零位置数之和至少 \(p+1\)（比元素总数 \(p\) 还多 \(1\)）。这比一般群上较弱的乘积型估计 (4.21)（约为 \(|\operatorname{supp}(f)|\cdot|\operatorname{supp}(\hat f)|\ge p\)）更强；关键就在于 \(p\) 是素数——此时 \(\mathbb{Z}_p\) 除 \(\{0\}\) 和全体外没有别的子群，傅里叶矩阵的所有子式都可逆（这正是 Chebotarev 引理的内容）。
例：取 \(p=5\) 看两端的极端情形 傅里叶变换 \(\hat f(\xi)=\sum_{x\in\mathbb{Z}_5}f(x)e^{-2\pi i x\xi/5}\)。
  1. 最集中的 \(f\)：取 \(f=\mathbf{1}_{\{0\}}\)（只在 \(x=0\) 处为 \(1\)）。则 \(\hat f(\xi)=\sum_x f(x)e^{\cdots}=f(0)=1\) 对所有 \(\xi\)。于是 \(|\operatorname{supp} f|=1\)，\(|\operatorname{supp}\hat f|=5\)，和 \(=6=p+1\)。恰好取到下界。
  2. 最分散的 \(f\)：取 \(f\equiv 1\)（处处为 \(1\)）。则 \(\hat f(\xi)=\sum_x e^{-2\pi i x\xi/5}=5\)（当 \(\xi=0\)）或 \(0\)（当 \(\xi\neq 0\)，几何级数求和为零）。于是 \(|\operatorname{supp} f|=5\)，\(|\operatorname{supp}\hat f|=1\)，和 \(=6\)。同样取到下界。
  3. 结论：\(f\) 越集中（支撑越小），\(\hat f\) 就越分散（支撑越大），二者此消彼长，和被钉在 \(\ge 6\)。
支撑大小之和 \(\ge p+1\)（图示 p=5） f（集中） |supp f|=1 f̂（分散） |supp f̂|=5 1 + 5 = 6 = p+1，下界达到 f 越窄，f̂ 越宽；二者不能同时窄
当 \(f\) 是单点（delta）时支撑为 \(1\)，其傅里叶变换却铺满整个 \(\mathbb{Z}_5\)（支撑 \(5\)）。这正是“不能同时集中”的图像。

作为这条定理的一个应用，我们再给出一个 Cauchy–Davenport 不等式的证明，这个证明本质上是傅里叶分析的（更确切地说是傅里叶–代数的）。

定理 9.53（Cauchy–Davenport 不等式，再来一次） 设 \(F=\mathbb{F}_p\) 为素数阶有限域。若 \(A,B\) 是 \(F\) 中两个加性集合，则 \[|A+B|\ge\min(|A|+|B|-1,\,p).\]
证明（[355] 及 Robin Chapman 的私人通信）. 由于 \(A,B\) 非空，我们可以找到 \(\mathbb{Z}/p\mathbb{Z}\) 的两个子集 \(X,Y\)，使得 \[|X|=p+1-|A|,\quad |Y|=p+1-|B|,\quad |X\cap Y|=\max(|X|+|Y|-p,\,1).\] 由定理 9.52，我们可以找到一个函数 \(f\) 使 \(\operatorname{supp}(f)=A\) 且 \(\operatorname{supp}(\hat f)=X\)，以及一个函数 \(g\) 使 \(\operatorname{supp}(g)=B\) 且 \(\operatorname{supp}(\hat g)=Y\)。那么卷积 \(f*g\) 的支撑包含在 \(A+B\) 中，而其傅里叶支撑等于 \(X\cap Y\)（特别地，\(f*g\) 非零），于是再次由定理 9.52 得到 \[|A+B|+|X\cap Y|\ge p+1,\] 这就给出 \(|A+B|\ge \min(|A|+|B|-1,\,p)\)，正是所求。♦
把这个巧妙证明分步看
  1. 反着用不确定性原理（构造）：要 \(f\) 的频谱支撑 \(X\) 小（这样 \(f\) 的时域支撑 \(=A\) 能大），按定理 9.52 的“反过来”部分，只要 \(|A|+|X|\ge p+1\) 就能造出 \(f\)。取 \(|X|=p+1-|A|\) 恰好卡在边界。同理造 \(g\) 与 \(|Y|=p+1-|B|\)。
  2. 卷积定理：\(\widehat{f*g}=\hat f\cdot\hat g\)。乘积非零的位置 \(=\operatorname{supp}(\hat f)\cap\operatorname{supp}(\hat g)=X\cap Y\)。又卷积的时域支撑满足 \(\operatorname{supp}(f*g)\subseteq \operatorname{supp}(f)+\operatorname{supp}(g)=A+B\)。
  3. 对 \(f*g\) 再用一次不确定性原理：\(|\operatorname{supp}(f*g)|+|X\cap Y|\ge p+1\)，而左边第一项 \(\le|A+B|\)，所以 \(|A+B|\ge p+1-|X\cap Y|\)。
  4. 算交集：\(|X\cap Y|=\max((p+1-|A|)+(p+1-|B|)-p,\,1)=\max(p+2-|A|-|B|,\,1)\)。于是 \(p+1-|X\cap Y|=\min\big(|A|+|B|-1,\ p\big)\)。✓

第 4 步里 \(|X\cap Y|\) 用了集合交的下界 \(|X\cap Y|\ge |X|+|Y|-p\)（容斥）和 \(\ge 1\)（非空）取较大者；为让最终下界尽量大，构造时把交集取到这个最小可能值。

推广到 \(\mathbb{Z}_p^n\)

可以迭代定理 9.52，使其同样适用于群 \(\mathbb{Z}_p^n\)（任意 \(n\ge 1\)），我们在其上赋予标准双线性型，如例 4.2 所述。

推论 9.54 设 \(p\) 为素数，\(n\ge 1\) 为整数，\(f:\mathbb{Z}_p^n\to\mathbb{C}\) 为非零函数。那么对所有 \(0\le k\le n-1\)， \[p^{k}\,|\operatorname{supp}(f)|+p^{n-k-1}\,|\operatorname{supp}(\hat f)|\ge p^n+p^{n-1}.\]
注记 9.55　通过把定理 9.52 中的例子与 \(\mathbb{Z}_p\) 的子群作笛卡尔积，可以看出这些界在大量情形下是紧的。它有一个漂亮的几何解释：若把点 \((|\operatorname{supp}(f)|,\,|\operatorname{supp}(\hat f)|)\) 画在 \(\mathbb{Z}\times\mathbb{Z}\) 中，则该点落在点 \((p^j,p^{n-j})\)（\(0\le j\le n\)）的凸包之上或之内的上方——这些点对应于 \(f\) 是 \(\mathbb{Z}_p^n\) 某子群的指示函数的情形；这个凸包应与 (4.21) 对应的双曲线相对照。在 [249] 中，此结果被进一步推广到任意有限加性群 \(Z\)，见习题 9.8.11。
|supp f| |supp f̂| (1,9) (3,3) (9,1) 凸包（强：折线） 双曲线 xy=p^n（弱） n=2, p=3：允许的支撑点落在蓝色折线之上
以 \(n=2,p=3\) 为例。子群指示函数给出顶点 \((1,9),(3,3),(9,1)\)；推论 9.54 说所有非零 \(f\) 的支撑点都在这条蓝色凸包折线之上。橙色虚线是较弱的双曲线型界 (4.21)，凸包比它更靠外、更强。
证明. 我们对 \(n\) 作归纳。当 \(n=1\) 时这正是定理 9.52。现在设 \(n>1\)，且推论对所有更小的 \(n\) 值已被证明。固定 \(f\)。把 \(\mathbb{Z}_p^n\) 参数化为 \(x=(x',x_n)\)，其中 \(x'\in\mathbb{Z}_p^{n-1}\)，\(x_n\in\mathbb{Z}_p\)。若 \(g(\xi',x_n)\) 是 \(f(x',x_n)\) 关于 \(x'\) 变量（固定 \(x_n\)）的傅里叶变换，则 \(\hat f(\xi',\xi_n)\) 是 \(g(\xi',x_n)\) 关于 \(x_n\) 变量（固定 \(\xi'\)）的傅里叶变换。

设 \(A\subset\mathbb{Z}_p\) 为所有使 \(f(\cdot,x_n)\)（从而 \(g(\cdot,x_n)\)）不恒为零的 \(x_n\) 之集合。注意 \(1\le|A|\le p\)，且 \[|\operatorname{supp}(f)|=\sum_{x_n\in A}|\operatorname{supp}(f(\cdot,x_n))|.\] 于是由鸽笼原理，存在某个 \(x_n\) 使得 \[\begin{equation}\tag{9.22}|A|\,|\operatorname{supp}(f(\cdot,x_n))|\le|\operatorname{supp}(f)|.\end{equation}\] 固定这个 \(x_n\)。由归纳假设，对所有 \(0\le k\le n-2\)， \[\begin{equation}\tag{9.23}p^{k}|\operatorname{supp}(f(\cdot,x_n))|+p^{\,n-k-1}|\operatorname{supp}(g(\cdot,x_n))|\ge p^{n-1}+p^{n-2}.\end{equation}\] 另外，对于 \(g(\cdot,x_n)\) 支撑中的任意 \(\xi'\)，可见 \(g(\xi',\cdot)\) 的支撑落在 \(A\) 中，故由定理 9.52， \[|\operatorname{supp}(\hat f(\xi',\cdot))|\ge p+1-|A|.\] 对 \(g(\cdot,x_n)\) 支撑中所有 \(\xi'\) 求和，得到 \[|\operatorname{supp}(\hat f)|\ge(p+1-|A|)\,|\operatorname{supp}(g(\cdot,x_n))|.\] 将此与 (9.22) 结合，得到 \[p^{k}|\operatorname{supp}(f)|+p^{\,n-k-1}|\operatorname{supp}(\hat f)|\ge p^{k}|A|\,|\operatorname{supp}(f(\cdot,x_n))|+(p+1-|A|)\,p^{\,n-k-1}|\operatorname{supp}(g(\cdot,x_n))|.\] 当 \(|A|\) 等于 \(1\) 或 \(p\) 时，借助 (9.23)，此处右端至少为 \(p^n+p^{n-1}\)。由于右端关于 \(|A|\) 是线性的，对中间情形 \(1<|A|♦
归纳的骨架
  1. 切片：把 \(n\) 维问题沿最后一个坐标 \(x_n\) 切成一摞 \((n-1)\) 维切片 \(f(\cdot,x_n)\)。傅里叶变换分两步走：先对前 \(n-1\) 维变换得 \(g\)，再对最后一维变换得 \(\hat f\)。
  2. 挑一片好切片：鸽笼原理 (9.22) 找到一个支撑不太大的切片。
  3. 两条已知不等式：对这片切片用归纳假设 (9.23)（低一维的结论）；对“沿 \(x_n\) 方向”用一维定理 9.52。
  4. 线性插值收尾：合成的下界是关于 \(|A|\) 的线性式，只需在两端点 \(|A|=1,p\) 验证 \(\ge p^n+p^{n-1}\)，中间自动成立。

习题

习题 9.8（译文）
  1. 9.8.1　设 \(p\) 为素数，\(k\ge 1\)。证明 \(\Phi_p(z)=1+z+z^2+\cdots+z^{p-1}\)，且 \(\Phi_{p^k}(z)=\Phi_p\big(z^{p^{k-1}}\big)\)。
  2. 9.8.2（Eisenstein 判别法）　设 \(p\) 为素数，\(P(t)=a_nt^n+\cdots+a_0\in\mathbb{Z}[t]\) 满足：\(a_n\) 不被 \(p\) 整除，\(a_{n-1},\dots,a_0\) 都被 \(p\) 整除，且 \(a_0\) 不被 \(p^2\) 整除。证明 \(P\) 在 \(\mathbb{Z}[t]\) 中不可约。
  3. 9.8.3　设 \(p\) 为素数。显式计算多项式 \(\Phi_p(t-1)\)，然后用 Eisenstein 判别法在不使用引理 9.48 的前提下证明 \(\Phi_p(t-1)\)（从而 \(\Phi_p\) 本身）在 \(\mathbb{Z}[t]\) 中不可约。
  4. 9.8.4　设 \(n\ge 1\) 为整数，并设 \(x\in\mathbb{F}_p^\times\) 满足 \(\Phi_n(x)=0\)。证明 \(\operatorname{ord}^\times(x)=n\)，特别地 \(n\) 整除 \(p-1\)。
  5. 9.8.5　设 \(n,m\) 为整数。利用习题 9.8.4，证明 \(\Phi_n(m)\) 的所有素因子都模 \(n\) 余 \(1\) 且与 \(m\) 互素。利用这一点（并修改 Euclid 关于素数无穷的证明）证明：存在无穷多个模 \(n\) 余 \(1\) 的素数；这是 Dirichlet 定理的一个特例。
  6. 9.8.6　设 \(n\ge 1\)，\(\omega\) 为本原 \(n\) 次单位根。证明分圆域 \(\mathbb{Q}(\omega)\) 是 \(\mathbb{Q}\) 上的一个 \(\varphi(n)\) 维向量空间，且复数 \(1,\omega,\omega^2,\dots,\omega^{\varphi(n)-1}\) 构成 \(\mathbb{Q}(\omega)\) 的一组线性基。
  7. 9.8.7　设 \(p\) 为素数，\(\omega\) 为本原 \(p\) 次单位根。设 \(\mathbb{Z}[\omega]\) 是由 \(\omega\) 生成的环。证明商环 \(\mathbb{Z}[\omega]/((1-\omega)\cdot\mathbb{Z}[\omega])\) 同构于域 \(\mathbb{F}_p\)。（提示：利用 \(\Phi_p(1)=p\)，从而 \(\Phi_p(\omega)-p\) 含有因子 \((1-\omega)\)。）
  8. 9.8.8　[120] 设 \(p\) 为素数，\(\omega\) 为本原 \(p\) 次单位根，\(z_1,\dots,z_k\) 为互不相同的 \(p\) 次单位根，\(n_1,\dots,n_k\) 为 \([0,p)\) 中互不相同的整数。假设存在一个次数至多 \(p-1\) 的多项式 \(P\in\mathbb{Z}[\omega][z]\)，它在 \(z_1,\dots,z_k\) 处为零且至多有 \(k\) 个非零系数。利用习题 9.8.7 与引理 9.26 证明 \(P\) 是 \((1-\omega)\) 的倍数。用此并配合无穷递降论证，得到引理 9.51 的另一个证明（至少在 \(q=p\) 情形，而这对定理 9.52 已足够）。
  9. 9.8.9　[355] 由引理 9.51 推出定理 9.52。（提示：引理 9.51 表明傅里叶矩阵 \((e^{2\pi i jk/p})_{1\le j,k\le p}\) 的所有子式都可逆。）反过来，证明定理 9.52 蕴含引理 9.51 的 \(q=p\) 情形。
  10. 9.8.10　设 \(p\) 为素数，\(G:=\{z\in\mathbb{C}:z^p=1\}\) 为 \(p\) 次单位根集合，\(P\in\mathbb{C}[z]\) 为非零多项式且 \(\deg(P)
  11. 9.8.11　[249] 给定任意有限加性群 \(Z\) 及任意实数 \(k\)，令 \(\theta(Z;k)\) 表示量 \[\theta(Z;k):=\inf\{|\operatorname{supp}(\hat f)|:f\in L^2(Z);\ f\not\equiv 0;\ |\operatorname{supp}(f)|\le k\}.\] 证明对 \(Z\) 的每个子群 \(G\) 与任意 \(1\le k\le|Z|\)，有不等式 \[\theta(Z;k)\ge\sup_{st=k}\theta(G;s)\,\theta(Z/G;t),\] 方法是改造推论 9.54 的证明。再通过一个归纳论证得出：对 \(L^2(Z)\) 中任意非零函数 \(f\)，格点 \((|\operatorname{supp}(f)|,|\operatorname{supp}(\hat f)|)\) 落在点 \((|G|,|Z|/|G|)\)（\(G\) 取遍 \(Z\) 的所有子群）的凸包之上或其上方。

返回 全书目录