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

9.3　Snevily 猜想Snevily’s conjecture

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。本节用上一节的组合零点定理（combinatorial Nullstellensatz）这把“代数钥匙”去攻一个看起来很组合的问题：能否把两个集合恰好配对，使配出来的和两两不同。

本节目标给定一个奇数阶的加法群里两个一样大的集合 \(A,B\)，问：能不能找到一个一一对应 \(\varphi:A\to B\)，把每个 \(a\) 跟它的搭档 \(\varphi(a)\) 加起来，得到的 \(|A|\) 个和\(\,a+\varphi(a)\,\)互不相同？这就是 Snevily 猜想。本节用多项式的方法（组合零点定理 + Vandermonde 行列式/积和式）证明它在若干重要特例下成立。

在文献 [322] 中，Snevily 提出了如下猜想。

猜想 9.15（Snevily 猜想）[322]设 \(Z\) 是一个奇数阶的加法群，\(A,B\) 是 \(Z\) 中两个加法集（additive set），满足 \(|A|=|B|\)。则存在一个双射 \(\varphi:A\to B\)，使得诸和 \[\{\,a+\varphi(a):a\in A\,\}\] 两两不同（all distinct）。
先把猜想读懂：一个能成的例子 取群 \(Z=\mathbb{Z}_5\)（模 \(5\) 的整数，阶为 \(5\)，是奇数）。令 \(A=\{0,1,2\}\)，\(B=\{0,1,3\}\)，\(|A|=|B|=3\)。我们要把 \(A\) 的三个元素和 \(B\) 的三个元素一对一地配起来，使三个和（模 \(5\)）互不相同。试一组配法： \[\varphi(0)=0,\quad \varphi(1)=3,\quad \varphi(2)=1.\] 对应的和是 \[0+0=0,\qquad 1+3=4,\qquad 2+1=3\ (\bmod 5),\] 即 \(\{0,4,3\}\)，确实两两不同。所以这一对 \(A,B\) 通过了检验。Snevily 猜想断言：在奇数阶群里，无论 \(A,B\) 怎么取（只要一样大），总能找到这样的好配法。
A B 和 a+φ(a) 0 1 2 0 1 3 0+0=0 1+3=4 2+1=3
双射 \(\varphi:A\to B\) 是 \(A\) 与 \(B\) 之间的完美配对（每个箭头出发点和到达点都恰好用一次）；右列三个和 \(0,4,3\) 互不相同，这正是 Snevily 猜想要的“好配对”。
为什么必须“奇数阶”：一个偶数阶的反例 取 \(Z=\mathbb{Z}_2\)（阶 \(2\)，偶数），\(A=B=\{0,1\}\)。只有两种配法：
  1. 恒等配 \(\varphi(0)=0,\varphi(1)=1\)：和为 \(0+0=0\) 与 \(1+1=0\)（模 \(2\)），两个都是 \(0\)，不两两不同。
  2. 交换配 \(\varphi(0)=1,\varphi(1)=0\)：和为 \(0+1=1\) 与 \(1+0=1\)，又都相等。
两种配法都失败，所以在偶数阶群里猜想不成立。根本原因是：偶数阶群里 \(2\) 不可逆，映射 \(a\mapsto 2a\) 不是单射；而奇数阶里 \(a\mapsto 2a\) 是双射——这一点下面证明里会直接用到。

这个猜想的一般情形仍未解决，但许多特例已经被证明。例如，Alon [5] 利用组合零点定理证明了猜想对素数阶循环群成立。

复习：组合零点定理（上一节的工具）设 \(F\) 是域，\(P\in F[x_1,\dots,x_n]\) 的次数恰为 \(d_1+\dots+d_n\)，且单项式 \(x_1^{d_1}\cdots x_n^{d_n}\) 在 \(P\) 中的系数非零。若取子集 \(S_1,\dots,S_n\subseteq F\) 满足 \(|S_i|>d_i\)（每个变量的取值集都比它的次数大），则一定能在格点 \(S_1\times\dots\times S_n\) 里找到一点 \((s_1,\dots,s_n)\) 使 \(P(s_1,\dots,s_n)\neq 0\)。
用法套路：把“想要的结论不成立”写成“某些因子为零”，再把这些因子乘成一个多项式 \(P\)；只要 \(P\) 在某点非零，就说明那些因子在这点全都不为零——结论成立。
定理 9.16 [5]设 \(F=\mathbb{F}_p\)，其中 \(p>2\) 是奇素数；\(A,B\) 是 \(F\) 中两个加法集，满足 \(|A|=|B|\)。则存在双射 \(\varphi:A\to B\)，使诸和 \(\{a+\varphi(a):a\in A\}\) 两两不同。
证明. 若 \(A=B\)，可直接取 \(\pi\) 为恒等映射——这里用到 \(p\) 为奇数（于是 \(a\mapsto 2a\) 是双射，诸和 \(2a\) 自然互不相同）。故下设 \(A\neq B\)。特别地我们可取 \(|A|=|B|♦

这里取值集为 \(S_1=\dots=S_k=B\)。

  1. 把“坏事”翻译成因子为零。我们想要的双射 \(\varphi(a_i)=s_i\)（其中 \(s_i\in B\)）要满足两件事：第一，\(\varphi\) 是单射，即不同的 \(a_i\) 配到不同的 \(s_i\)，也就是 \(i\neq j\) 时 \(s_i\neq s_j\)，等价于因子 \(t_j-t_i\) 在 \(s\) 处非零；第二，诸和互不相同，即 \(a_i+s_i\neq a_j+s_j\)，移项得 \(s_j-s_i+a_i-a_j\neq 0\)，正是第二个因子非零。
  2. 把所有“非零要求”乘起来。对每一对 \(i
  3. 数次数。每对 \((i,j)\) 贡献 \(2\) 次，共 \(\binom{k}{2}\) 对，故 \(\deg P=2\binom{k}{2}=k(k-1)\)；摊到 \(k\) 个变量上，最高次单项式 \(t_1^{k-1}\cdots t_k^{k-1}\) 的每个指数都是 \(k-1\)。
  4. 验“钥匙”不为零。定理 9.11（Dyson 猜想的一个特例）给出该单项式系数恰为 \(k!\)。因为 \(k
  5. 验“格点够大”。取 \(S_i=B\)，则 \(|S_i|=|B|=k> k-1=\deg_{t_i}P\)，组合零点定理的前提满足。
  6. 收网。定理保证存在 \((s_1,\dots,s_k)\in B^k\) 使 \(P(s)\neq 0\)，于是两件事同时成立，得到所需的双射。♦
用上面的例子复核多项式 P 回到 \(\mathbb{F}_5\)、\(A=\{a_1,a_2,a_3\}=\{0,1,2\}\)。前面我们找到的好配对是 \(s=(s_1,s_2,s_3)=(0,3,1)\)（即 \(0\!\to\!0,1\!\to\!3,2\!\to\!1\)）。逐对验证 (9.16a) 的两个因子：
  1. \((i,j)=(1,2)\)：\(s_2-s_1=3\neq0\)；\(s_2-s_1+a_1-a_2=3+0-1=2\neq0\)。
  2. \((i,j)=(1,3)\)：\(s_3-s_1=1\neq0\)；\(s_3-s_1+a_1-a_3=1+0-2=-1=4\neq0\)。
  3. \((i,j)=(2,3)\)：\(s_3-s_2=1-3=-2=3\neq0\)；\(s_3-s_2+a_2-a_3=3+1-2=2\neq0\)。
六个因子全非零，故 \(P(0,3,1)\neq0\)——与“这是一个好配对”一致。组合零点定理保证这样的点必存在。

让我们注意：在 \(k

定理 9.17设 \(F=\mathbb{F}_p\) 是素数阶的域，\(k(k-1)(r_i+1)\)（这里 \(r_i:=|R_i|\)）。则存在 \(k\) 个两两不同的元素 \(\{b_1,\dots,b_k\}\)，其中 \(b_i\in B_i\)，使得诸和 \(a_i+b_i\) 两两不同，并且对每一对 \(i\neq j\) 都有 \[a_i+b_i-(a_j+b_j)\notin R_i.\]
定理 9.17 在加强什么定理 9.16 只要求“诸和互不相同”，即差 \(a_i+b_i-(a_j+b_j)\neq 0\)，也就是禁止差落进单点集 \(\{0\}\)。定理 9.17 把这个“禁区”从一个点 \(\{0\}\) 扩大成一整个集合 \(R_i\)：要求每个差都不落进 \(R_i\)。代价是 \(B_i\) 必须更大（\(|B_i|>(k-1)(r_i+1)\)，禁区越大要求越宽）。当所有 \(R_i=\{0\}\)（\(r_i=0\)）时，条件退回到 \(|B_i|>k-1\)，就回到定理 9.16 的情形。
证明. 设 \(P\in F[t_1,\dots,t_k]\) 为多项式 \[P(t_1,\dots,t_k):=\prod_{1\le i♦
  1. 因子怎么来的。第一组因子 \(\prod_{i
  2. 数次数。第一组贡献 \(2\binom{k}{2}=k(k-1)\)；第二组对每个有序对 \(i\neq j\) 贡献 \(|R_i|\) 个一次因子，共 \(\sum_{i\neq j}|R_i|=(k-1)\sum_i|R_i|\)。合计 \(k(k-1)+(k-1)\sum_i|R_i|=(k-1)\sum_i(|R_i|+1)=\sum_i(k-1)(|R_i|+1)\)，与上式一致。
  3. 多项式系数非零。那个最高次单项式的系数是一个多项系数（multinomial coefficient）\(\binom{\sum(|R_i|+1)}{|R_1|+1,\dots,|R_k|+1}\)。只要 \(\sum_i(|R_i|+1)(k-1)(|R_i|+1)=\deg_{t_i}P\)，组合零点定理给出所需的点。♦

9.3.1　乘法版本与奇数阶循环群

DasGupta、Károly、Serra 与 Szegedy [67] 得到了 Snevily 猜想的一个乘法版本。定义 \(n\) 个变量的 Vandermonde 积和式（Vandermonde permanent）\(\operatorname{Per}_n(x_1,\dots,x_n)\) 为 \[\operatorname{Per}_n(x_1,\dots,x_n)=\sum_{\pi\in S_n}\ \prod_{i=1}^n x_i^{\pi(i)-1}\tag{9.3'}\] （参看 (9.3)）。

积和式 vs 行列式把矩阵 \(M=(x_i^{\,j-1})_{i,j}\)（第 \(i\) 行是 \(1,x_i,x_i^2,\dots,x_i^{n-1}\)，即 Vandermonde 矩阵）。行列式是 \(\det M=\sum_{\pi}\operatorname{sgn}(\pi)\prod_i x_i^{\pi(i)-1}\)，每项带正负号；积和式 \(\operatorname{Per}\) 把所有符号都换成 \(+\)。著名的 Vandermonde 公式给出 \[\det M=\Delta_n(x_1,\dots,x_n)=\prod_{1\le i特征为 \(2\) 的域里 \(+1=-1\)，于是积和式和行列式相等——这正是下面把奇数阶群塞进特征 \(2\) 域里的关键。
Vandermonde 矩阵（以 k=3 为例） ⎡ 1x₁x₁²⎤ ⎢ 1x₂x₂²⎥ ⎣ 1x₃x₃²⎦ det = ∏(xⱼ−xᵢ) （带 ± 号） Per = 全用 + 号求和 特征 2 时：det = Per
同一个 Vandermonde 矩阵，按所有置换求和：保留符号得行列式（有乘积公式），全取正号得积和式；在特征 \(2\) 的域里两者重合。
引理 9.18 [67]设 \(F\) 是任意域，\(a_1,\dots,a_k\) 是 \(F\) 的元素。假设 Vandermonde 积和式 \(\operatorname{Per}_k(a_1,\dots,a_k)\) 非零。则对 \(F\) 的任意子集 \(B=\{b_1,\dots,b_k\}\)，存在置换 \(\pi\in S_k\)，使得诸乘积 \(a_1 b_{\pi(1)},\dots,a_k b_{\pi(k)}\) 两两不同。
证明. 设 \(f\in F[t_1,\dots,t_k]\) 为多项式 \[f(t_1,\dots,t_k):=\Delta_k(t_1,\dots,t_k)\,\Delta_k(a_1t_1,\dots,a_kt_k),\] 其中 \(\Delta_k\) 是 Vandermonde 行列式。则 \(\deg(f)\le k(k-1)\)。取 \(S_1=B,\dots,S_k=B\)。由组合零点定理，只需证明单项式 \(t_1^{k-1}\cdots t_k^{k-1}\) 的系数非零。注意 \[f(t_1,\dots,t_k)=\Bigl(\sum_{\pi\in S_k}(-1)^{\sigma(\pi)}\prod_{i=1}^k t_{\pi(i)}^{\,i-1}\Bigr)\Bigl(\sum_{\tau\in S_k}(-1)^{\sigma(\tau)}\prod_{i=1}^k (a_{\tau(i)}t_{\tau(i)})^{\,i-1}\Bigr)\] \[=\Bigl(\sum_{\pi\in S_k}(-1)^{\sigma(\pi)}\prod_{i=1}^k t_{\pi(i)}^{\,i-1}\Bigr)\Bigl(\sum_{\pi\in S_k}(-1)^{\binom{k}{2}-\sigma(\pi)}\prod_{i=1}^k (a_{\pi(i)}t_{\pi(i)})^{\,k-i}\Bigr).\] 于是所关心的系数恰为 \[\sum_{\pi\in S_k}(-1)^{\binom{k}{2}}\prod_{i=1}^k a_{\pi(i)}^{\,i-1}=(-1)^{\binom{k}{2}}\operatorname{Per}_k(a_1,\dots,a_k)\cdot 1,\] 由引理的假设它非零。证毕。（另一种证明见习题 9.3.3。）♦
  1. 为什么造这个 \(f\)。“乘积 \(a_i b_{\pi(i)}\) 两两不同”等价于：把 \(b_i\) 当成变量 \(t_i\) 的取值（取自 \(B\)），存在一组取值使得所有 \(a_i t_i\) 互不相同、且所有 \(t_i\) 也互不相同。两个 Vandermonde 行列式 \(\Delta_k(t)\) 与 \(\Delta_k(a t)\) 分别在“\(t_i\) 互不相同”、“\(a_i t_i\) 互不相同”时非零（因为 \(\Delta_k(x)=\prod_{i
  2. 抓最高次系数。第一个行列式按置换 \(\pi\) 展开，\(t_{\pi(i)}\) 出现 \(i-1\) 次；第二个改写后让 \(t_{\pi(i)}\) 出现 \(k-i\) 次。要凑出 \(t_1^{k-1}\cdots t_k^{k-1}\)，每个 \(t_j\) 的指数得是 \((i-1)+(k-i)=k-1\)，这迫使两个和式用同一个 \(\pi\) 配对。
  3. 符号相消。两处符号 \((-1)^{\sigma(\pi)}\) 与 \((-1)^{\binom{k}{2}-\sigma(\pi)}\) 相乘得 \((-1)^{\binom{k}{2}}\)，与 \(\pi\) 无关；剩下 \(\sum_\pi\prod_i a_{\pi(i)}^{\,i-1}\) 正是积和式（全正号求和）。只要它非零，系数非零，组合零点定理收尾。♦

可以把这个乘法陈述转换成加法陈述，办法是把加法群嵌入为某个合适域的乘法子群。例如，现在可以证明 Snevily 猜想对奇数阶循环群成立：

推论 9.19 [67]设 \(n\ge 1\) 为奇数，\(A,B\) 是 \(\mathbb{Z}_n\) 中两个加法集，满足 \(|A|=|B|\)。则存在双射 \(\varphi:A\to B\)，使诸和 \(\{a+\varphi(a):a\in A\}\) 两两不同。
证明. 我们将用到有限域理论，这将在 9.4 节复习。设 \(\mathbb{Z}_n^\times\) 为 \(\mathbb{Z}_n\) 中乘法可逆的元素，记 \(\phi(n):=|\mathbb{Z}_n^\times|\) 为 \(n\) 的 Euler 函数。由 Cauchy 定理（习题 3.1.2），有 \(2^{\phi(n)}\equiv 1\ (\bmod\ n)\)。设 \(F\) 为阶 \(2^{\phi(n)}\)、特征 \(2\) 的有限域（这种域的存在性由习题 9.4.4 给出）。由引理 9.22，\(F\) 的乘法群 \(F^\times\) 含有一个阶为 \(n\) 的元素，从而含有一个与加法群 \(\mathbb{Z}_n\) 同构的子群 \(G\)。于是只需对 \(G\) 验证 Snevily 猜想的乘法形式。但若 \(A=\{a_1,\dots,a_k\}\) 是 \(G\) 的子集，则由于 \(F\) 的特征为 \(2\)，可以把积和式换成行列式，并计算 \[\operatorname{Per}_k(a_1,\dots,a_k)=\Delta_k(a_1,\dots,a_k)=\prod_{1\le i♦
这步“加法变乘法”的精髓加法群 \(\mathbb{Z}_n\) 看上去和乘法毫无关系，但我们把它搬进一个域 \(F\) 的乘法群里：在 \(F^\times\) 中找一个 \(n\) 阶元素 \(g\)，它生成的循环子群 \(G=\{g^0,g^1,\dots,g^{n-1}\}\) 与 \(\mathbb{Z}_n\) 同构，其中“加 \(1\)”对应“乘以 \(g\)”。于是 \(\mathbb{Z}_n\) 里的加法 Snevily 问题，变成 \(G\) 里的乘法问题，正好用引理 9.18。最后还需要 \(\operatorname{Per}_k(a_1,\dots,a_k)\neq0\)：直接算积和式很难，但特征 \(2\) 让它等于 Vandermonde 行列式 \(\prod_{i
  1. 为什么阶是 \(2^{\phi(n)}\)。要把 \(n\) 阶循环群放进 \(F^\times\)，需要 \(n\mid |F^\times|=|F|-1\)。取 \(|F|=2^{\phi(n)}\)，则 \(|F^\times|=2^{\phi(n)}-1\)。由 \(2^{\phi(n)}\equiv1\ (\bmod\ n)\)（Euler/Cauchy）得 \(n\mid 2^{\phi(n)}-1\)，恰好整除。
  2. 为什么用特征 \(2\)。因为只有特征 \(2\) 时 \(\operatorname{Per}=\det\)，才能把难算的积和式换成有乘积公式的行列式，并立刻看出它非零。
  3. \(n\) 为奇数用在哪。要让 \(2^{\phi(n)}\equiv1\ (\bmod\ n)\)（即 \(2\) 在 \(\mathbb{Z}_n^\times\) 里），必须 \(\gcd(2,n)=1\)，也就是 \(n\) 为奇数。偶数 \(n\) 时这套构造直接崩掉，与猜想只对奇数阶成立完全吻合。♦

上述论证的一个变体，在循环群的阶为 \(p^k\) 时给出加强版结果。

定理 9.20 [67]设 \(p>2\) 为奇素数，\(q=p^\alpha\) 为 \(p\) 的某个幂（\(\alpha>1\)），\(1\le k
证明. 我们需要分圆域（cyclotomic field）的机制，这将在 9.8 节复习。设 \(\omega\) 为本原 \(q\) 次单位根，\(\mathbb{Q}(\omega)\) 为相应的分圆域。注意到 \(\mathbb{Q}(\omega)\) 含有乘法子群 \[G:=\{\xi^n:n\in\mathbb{Z}\}\subset\mathbb{Q}(\omega),\] 它与加法群 \(\mathbb{Z}_q\) 群同构。于是只需证明：对任意 \(a_1,\dots,a_k\in G\) 与任意 \(B=\{b_1,\dots,b_k\}\subseteq G\)……（原文摘录至此结束）

说明：本节 PDF 摘录到定理 9.20 证明的中途即结束。定理 9.20 的完整证明（在分圆域 \(\mathbb{Q}(\omega)\) 中验证乘法形式，并借助引理 9.18 与积和式非零性收尾）见原书后续页与 9.8 节。其思路与推论 9.19 完全平行：把 \(\mathbb{Z}_q\) 的加法搬到分圆域乘法子群 \(G\) 上，再套用引理 9.18。

本节脉络回顾
  1. 问题（猜想 9.15）：奇数阶群里，等大的 \(A,B\) 总能配出互不相同的和。
  2. 素数阶（定理 9.16）：把“配对成功”写成多项式 \(P\) 不为零，用组合零点定理 + Dyson 系数 \(k!\neq0\)。
  3. 更强（定理 9.17）：把禁区从单点 \(\{0\}\) 扩成集合 \(R_i\)，多项系数非零保证之。
  4. 乘法版（引理 9.18）：积和式 \(\operatorname{Per}_k\neq0\) 时乘积可配成互异。
  5. 奇数阶循环群（推论 9.19）：嵌入特征 \(2\) 有限域的乘法群，借 \(\operatorname{Per}=\det=\prod(a_j-a_i)\neq0\)。
  6. \(p^\alpha\) 阶加强版（定理 9.20）：同样的“加法搬乘法”技巧，换到分圆域里做。

返回 全书目录