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

9.1　组合零点定理The combinatorial Nullstellensatz

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演 / 自测）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。本节用到的“域、多项式、次数”等概念会在用到处随手解释。

本节目标一个一元多项式的根不会太多——次数是 \(d\)，最多 \(d\) 个根。本节要把这条人人熟悉的事实推广到多元多项式：只要每个变量允许取的值的个数都足够多（多到超过该变量在某个“领头单项式”里的指数），就一定能找到一组取值，使整个多项式不为零。这就是 Alon 的组合零点定理（combinatorial Nullstellensatz）。它是后面若干节“多项式方法”的总开关，用来证明各种和集大小的下界，例如 Cauchy–Davenport 不等式。

第 9 章引言（节选）

……（一个多项式）若它的某些系数的某种组合以某种方式能被 \(p\) 整除（或不能被 \(p\) 整除），则它就不可能拥有某些类型的零点；这方面最著名的例子是 Eisenstein 判别法（习题 9.8.2），不过组合零点定理也可以看作这一类型的命题，另一个例子出现在分圆域中（引理 9.49）。作为这些判别法的一个应用，我们将给出 \(\mathbb{Z}_p\) 上的一个测不准原理，由它可得 Cauchy–Davenport 不等式（定理 5.4）的一个傅里叶分析证明。

本章理论大多对任意域 \(F\) 成立。然而，我们有时需要把注意力集中到两类特殊的域上。第一类是有限域，其首要的例子是素数阶的域 \(F_p=\mathbb{Z}_p\)；我们将在 9.4 节回顾这类域的理论。第二类是分圆域，由 \(p\) 次单位根生成；我们将在 9.8 节回顾这类域的理论。

容易看出，在一个域 \(F\) 中，所有非零元素都与单位元 \(1\) 具有相同的挠数（torsion）。我们把这个挠数称为 \(F\) 的特征（characteristic），记作 \(\operatorname{char}(F)\)；它要么是零（当 \(F\) 无挠时），要么是某个素数 \(p\)（例如当 \(F\) 是有限域时就是这种情形）。我们的一些结论只在 \(F\) 的特征足够大（或等于零）时才成立。

术语小抄（高中向）

9.1　组合零点定理

众所周知，域 \(F\) 上的一个一元多项式 \(P\in F[t]\) 至多有 \(\deg(P)\) 个零点，这里 \(\deg(P)\) 表示 \(P\) 的次数。我们把这一事实改写成如下形式。

引理 9.1 设 \(P\in F[t]\) 是域 \(F\) 上的一元多项式，次数为 \(d\)（即 \(P\) 中 \(t^d\) 的系数非零），并设 \(S\) 是 \(F\) 的一个子集，满足 \(|S|>\deg(P)\)。那么存在 \(x\in S\) 使得 \[P(x)\neq 0.\]

换句话说：把所有候选取值放进集合 \(S\) 里，只要 \(S\) 的元素个数超过多项式的次数，那么 \(S\) 里就不可能全是根——必有某个 \(x\) 让 \(P(x)\neq 0\)。

例（引理 9.1 的具体感受） 取 \(P(t)=t^2-1\)，次数 \(d=2\)，它的全部根是 \(t=1\) 与 \(t=-1\)，只有两个。若 \(S=\{-1,0,1\}\)，则 \(|S|=3>2=\deg(P)\)。引理保证 \(S\) 中存在非根：
  1. \(P(-1)=1-1=0\)（是根）。
  2. \(P(1)=1-1=0\)（是根）。
  3. \(P(0)=0-1=-1\neq 0\)。找到了！\(x=0\) 即为所求。♦
道理很朴素：根最多 \(2\) 个，而我们手里有 \(3\) 个互不相同的候选，抽屉原理告诉我们至少有一个不是根。
−1 根 1 根 0：P=−1≠0 P(t)=t²−1
抛物线只在 \(\pm1\) 处穿过横轴（两个根）。候选集 \(S=\{-1,0,1\}\) 有 \(3\) 个点，比根多，于是必有点（这里是 \(0\)）落在轴外，对应 \(P\neq0\)。

下面我们把这一事实强有力地推广到多元多项式，即 Alon [4] 的组合零点定理。

定理 9.2（组合零点定理）[4] 设 \(F\) 为任意域，\(P\in F[t_1,\dots,t_n]\) 是一个 \(d\) 次多项式，它在某个单项式 \(t_1^{d_1}\cdots t_n^{d_n}\) 处含有非零系数，其中 \(d_1+\cdots+d_n=d\)；又设 \(S_1,\dots,S_n\) 是 \(F\) 的子集，满足 \(|S_i|>d_i\) 对所有 \(1\le i\le n\) 成立。那么存在 \(x_1\in S_1,\dots,x_n\in S_n\)，使得 \[P(x_1,\dots,x_n)\neq 0.\]
怎样读这条定理
例（\(n=2\) 的完整演示） 取 \(P(t_1,t_2)=t_1t_2\)，总次数 \(d=2\)。钥匙单项式取它自己 \(t_1^1t_2^1\)，故 \(d_1=d_2=1\)，系数为 \(1\neq0\)。按定理需 \(|S_1|>1,\ |S_2|>1\)，于是取 \(S_1=S_2=\{0,1\}\)（各 \(2\) 个元素）。定理断言 \(S_1\times S_2\) 这个 \(2\times2\) 网格上必有一点使 \(P\neq0\)。逐点验算：
  1. \((0,0)\)：\(P=0\cdot0=0\)。
  2. \((0,1)\)：\(P=0\cdot1=0\)。
  3. \((1,0)\)：\(P=1\cdot0=0\)。
  4. \((1,1)\)：\(P=1\cdot1=1\neq0\)。找到了！♦
注意：若把 \(S_1\) 缩成只含一个元素 \(\{0\}\)（这违反 \(|S_1|>1\)），则在 \(\{0\}\times\{0,1\}\) 上 \(P\) 恒为 \(0\)，定理失效——可见“候选值够多”的条件不可省。
t₂=1 t₂=0 t₁=0 t₁=1 0 0 0 1 P≠0 在此
\(2\times2\) 网格上 \(P=t_1t_2\) 的四个取值。三处为 \(0\)，唯独 \((1,1)\) 处非零。定理保证：网格够大时，这样的非零点一定存在。

定理 9.2 的证明

证明. 我们对 \(n\) 作归纳。\(n=1\) 的情形正是引理 9.1。现在设 \(n\ge2\)，并假设命题对 \(n-1\) 已经成立。

令 \(g_n(t_n)\) 是如下的一元多项式： \[g_n(t_n)=\prod_{s_n\in S_n}(t_n-s_n)=t_n^{|S_n|}+\text{（较低次项）}.\] 于是 \(g_n\) 的次数为 \(|S_n|\)，且首项是首一的（即系数为 \(1\)）。对 \(P\)（视为关于 \(t_n\) 的多项式）施行带余长除法（除以 \(g_n\)），可写成 \[P(t_1,\dots,t_n)=q_n(t_1,\dots,t_n)\,g_n(t_n)+r_n(t_1,\dots,t_n),\] 其中商 \(q_n\) 的次数至多为 \(d-|S_n|\)，余式 \(r_n\) 的次数至多为 \(d\)，并且 \(r_n\) 的任何单项式都不含 \(t_n^{|S_n|}\) 这个因子，从而 \[r_n(t_1,\dots,t_n)=\sum_{j=0}^{|S_n|-1}r_{n,j}(t_1,\dots,t_{n-1})\,t_n^{\,j}.\]

我们可以把 \(q_ng_n\) 展开成 \(q_n t_n^{|S_n|}\) 加上较低次项，后者的次数至多为 \[\deg(q_n)+|S_n|-1\le (d-|S_n|)+|S_n|-1d_n\)，可知 \(q_n t_n^{|S_n|}\) 中 \(t_1^{d_1}\cdots t_n^{d_n}\) 的系数也为零（它里面 \(t_n\) 的幂次至少是 \(|S_n|>d_n\)，凑不出 \(t_n^{d_n}\)）。于是，由关于 \(P\) 的假设（\(P\) 中 \(t_1^{d_1}\cdots t_n^{d_n}\) 的系数非零），余式 \(r_n\) 必含一个非零的 \(t_1^{d_1}\cdots t_n^{d_n}\) 系数。特别地，\(r_{n,d_n}\) 含一个非零的 \(t_1^{d_1}\cdots t_{n-1}^{d_{n-1}}\) 系数。

应用归纳假设（对 \(n-1\) 元多项式 \(r_{n,d_n}\) 及集合 \(S_1,\dots,S_{n-1}\)），可找到 \(x_1\in S_1,\dots,x_{n-1}\in S_{n-1}\)，使得 \(r_{n,d_n}(x_1,\dots,x_{n-1})\) 非零。再应用引理 9.1，便能找到 \(x_n\in S_n\) 使得 \[r_n(x_1,\dots,x_n)=\sum_{j=0}^{|S_n|-1}r_{n,j}(x_1,\dots,x_{n-1})\,x_n^{\,j}\neq 0.\] 由于 \(g_n(x_n)=0\)（因为 \(x_n\in S_n\)），于是 \[P(x_1,\dots,x_n)=q_n(x_1,\dots,x_n)\underbrace{g_n(x_n)}_{=0}+r_n(x_1,\dots,x_n)=r_n(x_1,\dots,x_n)\neq 0,\] 正如所要证明的。♦

证明的脉络（动机版）

整个证明的核心想法只有一句话：“在网格 \(S_1\times\cdots\times S_n\) 上，\(g_n(t_n)\) 永远等于 \(0\)，所以可以被自由地丢掉。” 围绕这句话，步骤是：

  1. 造一个会“自爆”的多项式 \(g_n\)。 把 \(S_n\) 里所有数当作根做成 \(g_n(t_n)=\prod_{s\in S_n}(t_n-s)\)。只要 \(t_n\) 取在 \(S_n\) 内，\(g_n\) 必为 \(0\)。它的次数恰是 \(|S_n|\)，且首项首一（方便做除法）。
  2. 用长除法把 \(P\) 拆成 \(q_n g_n+r_n\)。 商 \(q_n\) 那一块乘了 \(g_n\)，在网格上自动归零；真正起作用的是余式 \(r_n\)。所以只要证 \(r_n\) 在网格上某点非零，\(P\) 就在该点非零。
  3. 盯住“钥匙单项式”\(t_1^{d_1}\cdots t_n^{d_n}\)。 通过数次数证明：被丢掉的 \(q_n g_n\) 那部分根本贡献不出这个单项式（要么次数太低，要么 \(t_n\) 的幂次太高）。所以 \(P\) 里那个非零系数必然“原封不动”地留在余式 \(r_n\) 中。
  4. 降维。 \(r_n\) 中 \(t_n^{d_n}\) 的系数 \(r_{n,d_n}\) 是一个少一个变量的多项式，且仍带非零的钥匙系数 \(t_1^{d_1}\cdots t_{n-1}^{d_{n-1}}\)。归纳假设直接给出前 \(n-1\) 个坐标的取值，让 \(r_{n,d_n}\neq0\)。
  5. 收尾。 固定住前 \(n-1\) 个坐标后，\(r_n\) 变成关于 \(t_n\) 的、次数恰为 \(d_n\) 的一元多项式（领头系数 \(r_{n,d_n}\neq0\)）。因 \(|S_n|>d_n\)，引理 9.1 给出 \(S_n\) 中一个非根 \(x_n\)。大功告成。
P = qₙ·gₙ + rₙ　（按 tₙ 的幂次分块看） qₙ·gₙ 部分 tₙ 幂次 ≥ |Sₙ| > dₙ 或 次数 < d → 凑不出钥匙单项式 rₙ 部分 tₙ 幂次 ≤ |Sₙ|−1 钥匙单项式 t₁^d₁···tₙ^dₙ 的非零系数落在这里
长除法把 \(P\) 切成两块：左块 \(q_ng_n\) 在网格上恒为零、且贡献不出钥匙单项式；于是 \(P\) 里那个非零系数被“逼”到右块 \(r_n\) 中。这正是证明能降维推进的关键。

关于“组合零点定理”这一术语的解释，参见习题 9.1.3。基于组合零点定理，Alon、Nathanson 与 Ruzsa 发展出了所谓的多项式方法（polynomial method），它是证明和集（sum set）基数的各类界限的极有力工具。接下来的若干节将给出该方法的种种应用。

名字从何而来“Nullstellensatz”是德语，字面意思是“零点定理”（Nullstelle = 零点，Satz = 定理）。经典的希尔伯特零点定理刻画了“一组多项式的公共零点集”与“由它们生成的理想”之间的对应。Alon 这条定理给出了一个反向的、组合味十足的判据：在乘积网格 \(S_1\times\cdots\times S_n\) 上，只要钥匙单项式系数非零且网格够大，\(P\) 就不会在整张网格上全为零——故名“组合零点定理”。

习题

习题 9.1.1（Schwartz–Zippel 引理） 设 \(F\) 为域，\(Q\in F[t_1,\dots,t_n]\) 是一个 \(n\ge1\) 元的非零多项式，\(S\) 是 \(F\) 的非空有限子集。设 \(x_1,\dots,x_n\) 是从 \(S\) 中独立随机选取的元素。那么 \[\Pr\big(Q(x_1,\dots,x_n)=0\big)\le \frac{\deg(Q)}{|S|}.\] （提示：修改用于证明零点定理的归纳论证。）
习题 9.1.2 设 \(F\) 为域，\(d_1,\dots,d_n\ge0\)，且 \(P\in F[t_1,\dots,t_n]\) 是一个非零多项式，使得 \(P\) 中出现的每一个单项式都整除 \(t_1^{d_1}t_2^{d_2}\cdots t_n^{d_n}\)。证明：对每个 \(1\le i\le n\)，存在函数 \(f_{i,1},\dots,f_{i,d_i}:F^{i-1}\to F\)，使得 \[\{(x_1,\dots,x_n)\in F^n:P(x_1,\dots,x_n)=0\}\subseteq\bigcup_{i=1}^{n}\bigcup_{j=1}^{d_i}\{(x_1,\dots,x_n)\in F^n:x_i=f_{i,j}(x_1,\dots,x_{i-1})\};\] 也就是说，\(P\) 的零点集可以被少数几张“函数图像”覆盖。注意，当 \(i=1\) 时函数 \(f_{1,j}\) 就是一些常数。特别地，由此推出组合零点定理对这种 \(P\) 与 \(d_1,\dots,d_n\) 成立。
习题 9.1.3 [4] 设 \(F\) 为任意域，\(P\in F[t_1,\dots,t_n]\) 为多项式。设 \(S_1,\dots,S_n\) 是 \(F\) 的非空子集，并令 \(g_1,\dots,g_n\in F[t_1,\dots,t_n]\) 为多项式 \(g_i(t_1,\dots,t_n):=\prod_{s\in S_i}(t_i-s)\)（\(1\le i\le n\)）。若 \(P\) 在 \(S_1\times\cdots\times S_n\) 上恒为零，证明：存在多项式 \(h_1,\dots,h_n\in F[t_1,\dots,t_n]\)，满足 \(\deg h_i\le\deg P-\deg g_i\)，使得 \[P=\sum_{i=1}^{n}h_i g_i.\] 此外，\(h_1,\dots,h_n\) 的系数可取在由 \(P\) 与 \(g_1,\dots,g_n\) 的系数所生成的环内。利用本题与上一题，给出定理 9.2 的另一种证明。请将此与希尔伯特零点定理对照：后者断言，给定任意多项式 \(P,g_1,\dots,g_n\in F[t_1,\dots,t_n]\)，若 \(P\) 在由 \(g_1,\dots,g_n\) 决定的代数簇上恒为零，则 \(P\) 的某个幂 \(P^K\) 可写成 \(g_1,\dots,g_n\) 的线性组合 \(P^K=\sum_{i=1}^{n}h_i g_i\)。
习题 9.1.4 设 \(d_1,\dots,d_n\ge0\) 为整数，\(F\) 是一个特征为零、或特征大于 \(\max(d_1,\dots,d_n)\) 的域。设 \(P\in F[t_1,\dots,t_n]\) 满足：\(t_1^{d_1}\cdots t_n^{d_n}\) 的系数非零，但 \(P\) 中其他任何非零单项式都不被 \(t_1^{d_1}\cdots t_n^{d_n}\) 整除。设 \(S_1,\dots,S_n\subset F\) 满足 \(|S_i|>d_i\) 对所有 \(1\le i\le n\) 成立。证明：存在 \(x_1\in S_1,\dots,x_n\in S_n\)，使得 \(P(x_1,\dots,x_n)\neq0\)。（提示：对每个 \(1\le i\le n\)，构造函数 \(g_i:S_i\to F\)，使得 \(\sum_{x_i\in S_i}g_i(x_i)\,x_i^{\,j}=I(j=d_i)\) 对所有 \(0\le j\le d_i\) 成立；这里 \(I(\cdot)\) 是示性函数。然后考察量 \(\sum_{x_1\in S_1,\dots,x_n\in S_n}P(x_1,\dots,x_n)\,g_1(x_1)\cdots g_n(x_n)\)。）
习题 9.1.5 设 \(F\) 为域，\(m\) 为正整数。设 \(F^{\{0,1\}^m}\) 是从 \(\{0,1\}^m\) 到 \(F\) 的全体函数构成的环，对每个 \(i\in[1,m]\)，令 \(x_i\in F^{\{0,1\}^m}\) 为……（原文 PDF 在此处转入下一页/下一节，余文从略。）
即时自测
  1. 用引理 9.1 说明：取 \(P(t)=t^3-t\)（次数 \(3\)），\(S=\{0,1,2,3\}\subset\mathbb{Z}_5\)，必有 \(x\in S\) 使 \(P(x)\neq0\)。请找出一个这样的 \(x\)。
  2. 在组合零点定理中，若 \(P(t_1,t_2)=t_1^2t_2\)，钥匙单项式取 \(t_1^2t_2^1\)，那么 \(d_1,d_2\) 各是多少？\(S_1,S_2\) 至少各需多少个元素？
  3. 用 \(n=2\) 的特殊情形，把组合零点定理逐字对照引理 9.1，说出证明中“\(g_n\) 在 \(S_n\) 上恒为零”这一步在 \(n=1\) 时退化成了什么。

返回 全书目录