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

9.6　Kemnitz 猜想Kemnitz’s conjecture

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 定义 / 定理 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。本节是全书较难的一节，用到“多项式方法”（组合零点定理）。我们会把每一步的动机讲清。

本节目标研究一个量 \(s(n,d)\)：要在 \(\mathbb{Z}_n^d\)（\(d\) 维、每个坐标模 \(n\)）里随手抓出多少个向量，才能保证其中必有 \(n\) 个加起来等于零。第 9.2 节的 Erdős–Ginzburg–Ziv 定理给出了一维答案 \(s(n,1)=2n-1\)。Kemnitz 猜想说二维答案恰好是 \(s(n,2)=4n-3\)。本节给出 Rónyai 的重大进展：对素数 \(p\) 有 \(s(p,2)\le 4p-2\)，并完整讲解它的多项式方法证明。

9.6.1　参数 \(s(n,d)\)：要抓多少个才一定凑得出零和

定义（参数 \(s(n,d)\)）定义参数 \(s(n,d)\) 为最小的整数 \(s\)，使得 \(\mathbb{Z}_n^d\) 中任意一串长度为 \(s\) 的元素，都含有一个长度为 \(n\) 的子序列，其和在 \(\mathbb{Z}_n^d\) 中为 \(0\)。

用这套术语，定理 9.28（即 Erdős–Ginzburg–Ziv 定理）说的就是 \[ s(n,1)=2n-1. \] Harborth [176] 考虑了对更高的 \(d\) 来控制 \(s(n,d)\) 的问题。他首先观察到下面两个容易的估计 \[ (n-1)\,2^{d}+1 \;\le\; s(n,d)\;\le\;(n-1)\,n^{d}+1 \tag{9.13}\] 并进一步导出一个递归不等式 \[ s(mk,d)\;\le\; s(m,d)+m\bigl(s(k,d)-1\bigr); \tag{9.14}\] 我们把这些证明留作习题。

“长度为 \(n\) 的子序列、和为零”这件事可能比较抽象，先看一个最小的具体例子。

例：\(s(n,d)\) 在数什么 取 \(n=3,\ d=1\)，即在 \(\mathbb{Z}_3=\{0,1,2\}\) 里工作。EGZ 定理说 \(s(3,1)=2\cdot3-1=5\)：随手写下 \(5\) 个模 \(3\) 的数，一定能从中挑出 \(3\) 个加起来 \(\equiv 0\pmod 3\)。
  1. 比如序列 \(1,1,1,2,2\)。挑 \(1,1,1\)：和 \(=3\equiv0\)。成功。
  2. 再如 \(0,1,2,2,1\)。挑 \(0,1,2\)：和 \(=3\equiv0\)。成功。
  3. 关键是“无论怎么写”都办得到——这正是 \(s(n,d)\) 要保证的。\(4\) 个就不一定行（见下方下界例子），所以临界值恰是 \(5\)。
一串 \(s\) 个向量中，必能挑出 \(n\) 个使其和为 0 v₁ v₂ v₃ v₄ v₅ v₆ v₇ … vₛ 绿框这 \(n\) 个的和 \(v_{i_1}+\dots+v_{i_n}=0\)
\(s(n,d)\) 是“无论对手怎么排这串向量，我都保证能挑出 \(n\) 个零和”的最小串长。
例：下界 \((n-1)2^{d}+1\) 从哪来（以 \(d=1\) 验证 EGZ） 取 \(d=1\)，下界给出 \((n-1)\cdot2+1=2n-1\)，正是 EGZ 的精确值。构造一串“凑不出零和”的元素来说明 \(2n-2\) 个还不够：
  1. 放 \(n-1\) 个 \(0\) 和 \(n-1\) 个 \(1\)，共 \(2n-2\) 个。
  2. 任取其中 \(n\) 个：设里头有 \(j\) 个 \(1\)。因为总共只有 \(n-1\) 个 \(1\)，所以 \(j\le n-1\)；又要凑满 \(n\) 个，必须至少用 \(1\) 个 \(0\)。
  3. 这 \(n\) 个的和恰为 \(j\)，而 \(1\le\) 可能取值 \(\le n-1\)（或 \(j=0\)，但 \(j=0\) 要用 \(n\) 个 \(0\)，可我们只有 \(n-1\) 个）。无论如何 \(j\not\equiv 0\pmod n\)。
  4. 所以这 \(2n-2\) 个里挑不出长度 \(n\) 的零和子序列，于是 \(s(n,1)\ge 2n-1\)。
一般 \(d\)：把 \(\{0,1\}^d\) 里的 \(2^d\) 个 \(0\!-\!1\) 向量各放 \(n-1\) 份，同理凑不出零和，给出下界 \((n-1)2^d+1\)。
\(d=1\)：\(n-1\) 个 0 与 \(n-1\) 个 1（这里 \(n=4\)） 0 0 0 1 1 1 \(n-1=3\) 个 0 \(n-1=3\) 个 1 任取 4 个，和介于 1 与 3 之间，永远 \(\not\equiv0\pmod4\)
\(2n-2\) 个元素凑不出长度 \(n\) 的零和，说明 \(s(n,1)\) 至少要到 \(2n-1\)。

精确计算 \(s(n,d)\) 是一项困难的任务，尤其当 \(d\) 较大时；例如量 \(s(3,d)\) 与“在 \(\mathbb{Z}_3^d\) 中求 Roth 定理的尖锐常数”这一至今未解的问题密切相关（见习题 10.2.4）。但在 \(d\) 固定、\(n\) 很大的情形，人们知道得更多。Alon 与 Dubiner [6] 证明了 \(s(n,d)=O_d(n)\)。Kemnitz 猜测：(9.13) 中的下界在 \(d=2\) 时是尖锐的，即下界其实就是答案。

猜想 9.35（Kemnitz [200]）对任意 \(n\ge1\)，有 \[ s(n,2)=4n-3. \]

注意 \(4n-3=(n-1)\cdot2^{2}+1\)，正是 (9.13) 在 \(d=2\) 的下界；所以 Kemnitz 猜想等价于“二维的下界就是真值”。在文献 [200] 中，当 \(n\) 的素因子都取自集合 \(\{2,3,5,7\}\) 时该猜想已被验证。Alon 与 Dubiner [6] 证明了 \(s(n,2)\le 6n-5\)。他们还概述了一个论证，对所有充分大的素数 \(p\) 给出 \(s(p,2)\le 5p-2\)。

Rónyai [286] 作出了重大进展，证明了：

定理 9.36（Rónyai [286]）对每个素数 \(p\)，有 \[ s(p,2)\le 4p-2. \]
推论（与递归式合并）定理 9.36 与 (9.14) 一起，蕴含 \[ s(n,2)\le \tfrac{41}{11}\,n; \] 见习题 9.6.3。（注意 \(\tfrac{41}{11}\approx3.73\)，已经很接近猜想里的系数 \(4\)。）

9.6.2　定理 9.36 的证明：多项式方法登场

先看证明的总路线 我们要证：在 \(\mathbb{F}_p^2\) 里任意 \(4p-2\) 个向量中，必有 \(p\) 个加起来为零。思路分三层：
① 归约：借助习题 9.5.5，只需找到一个下标子集 \(J\)，其大小是 \(p\) 或 \(3p\)，且对应向量之和为零（\(3p\) 个零和能再切出 \(p\) 个零和）。
② 反证：假设这样的 \(J\) 不存在。
③ 多项式方法：用每个下标的一个 \(0/1\) 变量编码“它在不在 \(J\) 里”，构造一个多项式 \(P\)。借助费马小定理做“是否为零”的开关，证明在反证假设下 \(P\) 在整个 \(\{0,1\}^m\) 上恒为零；但 \(P\) 的最高次单项式系数又不为零——这与组合零点定理矛盾。矛盾说明假设错，故 \(J\) 存在。

先回顾两个工具。

工具一（费马小定理做开关，对应 (9.8)）对 \(a\in\mathbb{F}_p\)，有 \(a^{p-1}=1\)（若 \(a\neq0\)）或 \(a^{p-1}=0\)（若 \(a=0\)）。因此 \[ 1-a^{p-1}=\begin{cases}1,&a=0,\\[2pt]0,&a\neq0,\end{cases} \] 它是一个“\(a\) 是否等于 \(0\)”的指示器：和为零时亮 \(1\)，否则灭为 \(0\)。
工具二（组合零点定理，Combinatorial Nullstellensatz）设 \(P\in\mathbb{F}[t_1,\dots,t_m]\)，其总次数 \(\deg P=\sum_i k_i\)，且单项式 \(\prod_i t_i^{k_i}\) 的系数非零。则对任意满足 \(|S_i|>k_i\) 的集合 \(S_1,\dots,S_m\)，\(P\) 必在某个点 \((x_1,\dots,x_m)\in S_1\times\dots\times S_m\) 处不为零。
换言之：若一个多项式在整张网格上恒为零，它就不可能有这样一个“顶端”单项式系数非零。我们后面正是要制造这个矛盾——取 \(S_i=\{0,1\}\)（\(|S_i|=2>1=k_i\)）。
定理 9.36 之证明. \(p=2\) 的情形是平凡的，故可设 \(p\) 为奇素数。令 \(m:=4p-2\)，并记这 \(m\) 个向量为 \[ v_1=(a_1,b_1),\ \dots,\ v_m=(a_m,b_m)\in\mathbb{F}_p^2. \] 由习题 9.5.5，只需证明：存在子集 \(J\subset\{1,\dots,m\}\)，满足 \(|J|=p\) 或 \(|J|=3p\)，使得 \(\sum_{j\in J} v_j=0\)。
（为何“\(p\) 或 \(3p\)”就够？习题 9.5.5 说：\(\mathbb{F}_p^2\) 里若 \(3p\) 个向量之和为零，则其中必有 \(p\) 个之和为零。所以一旦拿到 \(|J|=3p\) 的零和，就能再切出 \(|J|=p\) 的零和；而 \(|J|=p\) 本身正是我们要的。）

反证假设：设不存在这样的 \(J\)。也就是说，对一切 \(|J|=p\) 或 \(3p\) 的子集，都有 \(\sum_{j\in J}v_j\neq0\)。

构造多项式。对每个下标 \(i\) 设一个变量 \(t_i\)；约定取 \(t_i\in\{0,1\}\)，并令 \(J:=\{i:t_i=1\}\)，于是 \(t=(t_1,\dots,t_m)\) 恰好编码了一个子集。在 \(\mathbb{F}_p[t_1,\dots,t_m]\) 中定义 \[ \sigma(t_1,\dots,t_m):=\sum_{I\subset[1,m],\,|I|=p}\ \prod_{i\in I}t_i, \] \[ P_1(t_1,\dots,t_m):=\Bigl(1-\bigl(\textstyle\sum_{i=1}^{m}a_it_i\bigr)^{p-1}\Bigr)\Bigl(1-\bigl(\textstyle\sum_{i=1}^{m}b_it_i\bigr)^{p-1}\Bigr)\Bigl(1-\bigl(\textstyle\sum_{i=1}^{m}t_i\bigr)^{p-1}\Bigr)\bigl(2-\sigma(t_1,\dots,t_m)\bigr), \] \[ P_2(t_1,\dots,t_m):=\prod_{i=1}^{m}(1-t_i), \] 并令 \(P:=P_1-2P_2\)。
每个因子的含义（用工具一读它）：当 \(t\in\{0,1\}^m\) 给出子集 \(J\) 时，\(\sum a_it_i\) 是 \(J\) 中向量第一坐标之和 \(A\)，\(\sum b_it_i\) 是第二坐标之和 \(B\)，\(\sum t_i=|J|\)。于是 \((1-A^{p-1})(1-B^{p-1})\) 是“\(J\)-向量和是否为零”的指示器；\((1-|J|^{p-1})\) 是“\(|J|\) 是否被 \(p\) 整除”的指示器；\(\sigma(t)=\binom{|J|}{p}\) 数的是 \(J\) 的 \(p\)-元子集个数。

断言：只要 \(x_1,\dots,x_m\in\{0,1\}\subset\mathbb{F}_p\)，就有 \(P(x_1,\dots,x_m)=0\)。按 \(J:=\{i\in[1,m]:x_i=1\}\) 的大小分情形讨论。
  1. \(J\) 为空集（\(|J|=0\)）。此时全部 \(x_i=0\)，容易看出 \(P_1=2\)（三个指示器都取 \(1\)，且 \(\sigma=0\) 使 \(2-\sigma=2\)），而 \(P_2=\prod(1-0)=1\)。于是 \(P=P_1-2P_2=2-2\cdot1=0\)。
  2. \(J\) 非空。此时存在某个 \(x_i=1\)，使 \((1-x_i)=0\)，故 \(P_2(x_1,\dots,x_m)=0\)。要证 \(P=P_1\) 也为零，只需证 \(P_1(x_1,\dots,x_m)=0\)，再细分：
    • \(|J|\) 不被 \(p\) 整除。由工具一 (9.8)，因 \(\sum_{i}x_i=|J|\not\equiv0\)，得 \(1-\bigl(\sum_{i=1}^{m}x_i\bigr)^{p-1}=0\)。这一因子为零，\(P_1=0\)。
    • \(|J|=2p\)。由 Wilson 定理（习题 9.4.9）可算出 \(\sigma(x_1,\dots,x_m)=2\)，于是 \(2-\sigma=0\)，\(P_1=0\)。
    • \(|J|=p\) 或 \(|J|=3p\)。由反证假设，\(\sum_{i=1}^{m}(a_i,b_i)x_i=\sum_{i\in J}(a_i,b_i)\neq0\)，即第一坐标之和 \(A\) 与第二坐标之和 \(B\) 不全为零。于是指示器 \[ \Bigl(1-\bigl(\textstyle\sum_{i=1}^{m}a_ix_i\bigr)^{p-1}\Bigr)\Bigl(1-\bigl(\textstyle\sum_{i=1}^{m}b_ix_i\bigr)^{p-1}\Bigr)=0, \] （因为 \(A\neq0\) 或 \(B\neq0\) 时，对应那个 \((1-(\cdot)^{p-1})\) 因子取 \(0\)），故 \(P_1=0\)。
由于 \(\{0,1\}^m\) 中每个点的 \(|J|\) 必落入上述某一类（空集；不整除；\(2p\)；\(p\) 或 \(3p\)；注意 \(m=4p-2<4p\)，故被 \(p\) 整除的非零取值只有 \(p,2p,3p\)），所以 \(P\) 在整个 \(\{0,1\}\times\dots\times\{0,1\}\) 上恒为零。

另一方面看次数与最高系数。逐项数次数：\(\deg P_1=(p-1)+(p-1)+(p-1)+p=4p-3\)，而 \(\deg P_2=m=4p-2\)，故 \(\deg P=4p-2\)。再看单项式 \(x_1x_2\cdots x_m\)（每个变量一次方、总次数恰为 \(m=4p-2\)）的系数：\(P_1\) 的次数 \(4p-3\) 不够高，贡献为零；它只来自 \(P_2=\prod(1-t_i)\) 的最高项 \((-1)^m\prod t_i\)。因此该系数为 \[ 2\,(-1)^{m}\cdot 1\neq0. \] 这与组合零点定理矛盾（一个在网格 \(\{0,1\}^m\) 上恒为零的多项式，其顶端单项式系数本应为零）。矛盾即告完成证明。♦
逐点检验（情形分析） 在所有 \(2^m\) 个 \(0/1\) 点上 \(P\equiv0\) 代数检验（次数与系数） 顶端项 \(x_1\cdots x_m\) 系数 \(=2(-1)^m\neq0\) 组合零点定理：二者不可兼得 ⇒ 矛盾 ⇒ 反证假设不成立 故存在 \(|J|=p\) 或 \(3p\) 的零和子集
多项式方法的“两面夹击”：组合那面说 \(P\) 处处为零，代数那面说它有非零顶端系数；组合零点定理判定二者矛盾，从而推翻反证假设。
把规模具体化（\(p=3\)） 取 \(p=3\)，则 \(m=4p-2=10\)：在 \(\mathbb{F}_3^2\) 中给 \(10\) 个向量，要找出 \(3\) 个（或 \(9\) 个）和为零。
  1. 变量 \(t_1,\dots,t_{10}\) 各取 \(0/1\)，共 \(2^{10}=1024\) 个 \(0/1\) 点，对应 \(1024\) 个子集 \(J\)。
  2. 被 \(p=3\) 整除且非空的子集大小只有 \(3,6,9\)（\(12>10\) 不可能）；\(6=2p\) 由 Wilson 那条 \((2-\sigma)\) 处理，\(3,9\) 由零和指示器处理，其余大小由 \((1-|J|^{p-1})\) 处理，空集对上 \(P_2\)。
  3. 各因子的次数：\(2,2,2\) 加上 \(\sigma\) 的 \(3\)，合计 \(\deg P_1=9=4p-3\)；\(\deg P_2=10\)；最高项 \(t_1\cdots t_{10}\) 系数 \(2(-1)^{10}=2\neq0\)。两面对撞即得矛盾。
补一笔：\((2-\sigma)\) 在 \(|J|=2p\) 时为何为零 \(\sigma(x)=\binom{|J|}{p}\bmod p\)。当 \(|J|=2p\) 时，由 Lucas 定理 \(\binom{2p}{p}\equiv\binom{2}{1}\binom{0}{0}=2\pmod p\)，故 \(2-\sigma=0\)。 对照其它整除情形：\(|J|=p\) 时 \(\binom{p}{p}=1\)，\(2-\sigma=1\neq0\)；\(|J|=3p\) 时 \(\binom{3p}{p}\equiv\binom{3}{1}=3\)，\(2-\sigma=-1\neq0\)——所以 \(p\) 与 \(3p\) 不能靠这个因子归零，必须由零和指示器（反证假设）来归零，分工正好对上。

9.6.3　两则注记：更省力的证法，以及猜想的最终解决

注记 9.37在上面的证明中，我们只用到了组合零点定理的一个非常特殊的情形；事实上，只需依赖习题 9.1.5 即可，而后者可用更初等的方法证明——这正是 [286] 中原始的处理方式。
注记 9.38非常近期，Reiher [279] 证明了 Kemnitz 猜想，他把 Chevalley–Warning 定理与一个巧妙的组合论证结合起来。关于这一领域结果的进一步综述，见 [81]。
小结 本节从一个统一的参数 \(s(n,d)\) 出发：一维由 EGZ 定理钉死为 \(2n-1\)；二维 Kemnitz 猜测为 \(4n-3\)。围绕这个猜想，估计逐步逼近——\(6n-5\)（Alon–Dubiner）→ 对素数 \(4p-2\)（Rónyai，本节主证）→ 合并递归式得 \(\tfrac{41}{11}n\) → 最终 Reiher 用 Chevalley–Warning 完全证明了猜想。本节的核心技术是多项式方法：把组合问题里的“某子集和是否为零”翻译成费马小定理给出的开关因子，构造一个在 \(\{0,1\}^m\) 上应当处处为零、但最高系数又非零的多项式，借组合零点定理制造矛盾。

返回 全书目录