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

9.2　受限和集Restricted sum sets

本页为译文 + 讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为讲解，逐步推演、举例、画图，把每一步的动机讲清楚，不用比喻。

本节目标上一节给出了组合零点定理（combinatorial Nullstellensatz）。本节把它变成一台“机器”：要证明某个受限和集（restricted sum set，即只允许某些组合相加的和集）至少有多少个元素，只需检验一个具体多项式的某一个系数在域里非零。我们用它重新证明 Cauchy–Davenport 不等式，证明困扰了三十年的 Erdős–Heilbronn 猜想，再深入研究 Vandermonde 行列式的系数，从而处理更复杂的多重受限相加。
回顾：组合零点定理（第 9.1 节，Theorem 9.1/9.2 的形态）设 \(F\) 为域，\(P\in F[t_1,\dots,t_n]\) 的总次数为 \(d_1+\dots+d_n\)，且单项式 \(t_1^{d_1}\cdots t_n^{d_n}\) 在 \(P\) 中的系数非零。若有限子集 \(S_1,\dots,S_n\subseteq F\) 满足 \(|S_i|>d_i\)，则存在 \(s_i\in S_i\) 使 \(P(s_1,\dots,s_n)\neq 0\)。
换言之：只要“最高次的那个对角单项式”系数不为零，\(P\) 就不可能在整张方格 \(S_1\times\dots\times S_n\) 上处处为零。本节所有证明都靠它。

从零点定理到下界：一条总引理

我们现在把组合零点定理应用于和集与受限和集，得到它们大小的下界。先给出一条总引理，它给出“何时能取到这种受限和集下界”的判据。

引理 9.3 [11]设 \(F\) 为域，\(n\ge 1\)，\(h\in F[t_1,\dots,t_n]\) 为一多项式。设 \(K\ge 0\)，\(A_1,\dots,A_n\) 为 \(F_p\) 中的加性集，满足 \[\sum_{i=1}^n |A_i| = K + n + \deg(h).\] 又设多项式 \((t_1+\dots+t_n)^K\,h(t_1,\dots,t_n)\) 在单项式 \(t_1^{|A_1|-1}\cdots t_n^{|A_n|-1}\) 处含有非零系数。则 \[\bigl|\{\,a_1+\dots+a_n:\ a_i\in A_i\ (1\le i\le n);\ h(a_1,\dots,a_n)\neq 0\,\}\bigr|\ \ge\ K+1.\tag{9.1}\]
证明. 反设 (9.1) 不成立；那么可找到一个基数 \(|B|=K\) 的集合 \(B\subseteq F\)，它包含 (9.1) 中那个和集。令 \(P\in F[t_1,\dots,t_n]\) 为多项式 \[P(t_1,\dots,t_n):=h(t_1,\dots,t_n)\prod_{b\in B}(t_1+\dots+t_n-b).\] 注意 \(\deg(P)=K+\deg(h)\)。另一方面，由 \(B\) 的构造可见 \(P\) 在 \(A_1\times\dots\times A_n\) 上处处为零。但这与组合零点定理矛盾。♦
为什么这步“矛盾”是核心把证明拆开看清楚每一步的动机。
  1. 反设有限。若受限和集元素个数 \(\le K\)，就能把它塞进一个大小恰为 \(K\) 的集合 \(B=\{b_1,\dots,b_K\}\)。也就是说：只要 \(a_i\in A_i\) 且 \(h(a_1,\dots,a_n)\neq 0\)，那么 \(a_1+\dots+a_n\) 一定是某个 \(b\in B\)。
  2. 造一个“到处为零”的多项式。取 \(P=h\cdot\prod_{b\in B}(t_1+\dots+t_n-b)\)。代入任意 \((a_1,\dots,a_n)\in A_1\times\dots\times A_n\)：若 \(h(a)=0\)，第一个因子让 \(P=0\)；若 \(h(a)\neq 0\)，则和 \(a_1+\dots+a_n\in B\)，于是某个因子 \((t_1+\dots+t_n-b)\) 为零，仍有 \(P=0\)。两种情形都为零，故 \(P\) 在整张方格上全为零。
  3. 看最高次系数。\(\prod_{b\in B}(t_1+\dots+t_n-b)\) 的最高次项就是 \((t_1+\dots+t_n)^K\)。所以 \(P\) 的最高次部分等于 \(h\cdot(t_1+\dots+t_n)^K\) 的最高次部分。由总次数计算，\(t_1^{|A_1|-1}\cdots t_n^{|A_n|-1}\) 正是 \(P\) 的最高次单项式，其系数就等于假设里那个非零系数。
  4. 触发零点定理。取 \(S_i=A_i\)（\(|A_i|=(|A_i|-1)+1>d_i\)），对角单项式系数非零，零点定理断言 \(P\) 在方格上必有一点非零。与第 2 步矛盾。\(\blacksquare\)

这条强有力的引理，把“证明受限和集下界”这件事，归约成“验证一个明确多项式的单一系数在域 \(F\) 中非零”。作为该引理的两个快速应用，我们重新证明 Cauchy–Davenport 不等式（定理 5.4），再导出由 Erdős 与 Heilbronn 最先猜想的一个变体——它关于受限和 \[A\hat{+}B:=\{a+b:\ a\in A,\ b\in B,\ a\neq b\}.\]

普通和 \(A+B\) 用全部格点；受限和 \(A\hat{+}B\) 去掉 \(a=b\) 的对角格点 b₁b₂b₃b₄ a₁a₂a₃a₄ 绿点：允许 红点：\(a=b\)，禁止 每点贡献一个和 \(a_i+b_j\)，再去重
受限和 \(A\hat{+}B\) 把“\(a=b\)”的配对剔除（红点）。剔除让和集可能变小，因此下界比 \(A+B\) 要弱一些——这正是 Erdős–Heilbronn 问题的难点所在。

第一个应用：再证 Cauchy–Davenport

定理 9.4（Cauchy–Davenport 不等式，再证）[47],[68]设 \(F=F_p\) 为素数阶有限域。若 \(A,B\) 是 \(F\) 中两个加性集，则 \[|A+B|\ \ge\ \min(|A|+|B|-1,\ p).\]

我们将在 9.8 节经由 Fourier 变换给出本定理的第三个证明。

证明. 当 \(|A|+|B|>p\) 时结论显然（见习题 2.1.6），故取 \(|A|+|B|\le p\)。我们对引理 9.3 取 \(n=2\)，\((A_1,A_2)=(A,B)\)，\(h\equiv 1\)，以及 \(K:=|A|+|B|-2\)；只要验证 \((t_1+t_2)^K\) 在 \(t_1^{|A|-1}t_2^{|B|-1}\) 处系数非零即可。但该系数恰为 \(\binom{K}{\,|A|-1\,}\bmod p\)，由 \(K♦
例：在 \(F_7\) 中验证取 \(p=7\)，\(A=\{0,1,3\}\)，\(B=\{0,2\}\)，则 \(|A|=3,|B|=2\)。
  1. 下界：\(\min(3+2-1,7)=\min(4,7)=4\)。
  2. 直接算 \(A+B=\{0,2,1,3,5\}=\{0,1,2,3,5\}\)，共 \(5\) 个元素，\(5\ge 4\) ✓。
  3. 看机器内部：\(K=|A|+|B|-2=3\)，需 \((t_1+t_2)^3\) 在 \(t_1^{2}t_2^{1}\) 处系数 \(=\binom{3}{2}=3\)。因为 \(3\not\equiv 0\pmod 7\)，零点定理保证了和集至少 \(K+1=4\) 个元素。

第二个应用：Erdős–Heilbronn 猜想

作为 Cauchy–Davenport 不等式的一个特例，我们看到对 \(F_p\) 中任意加性集 \(A\) 有 \(|A+A|\ge\min(2|A|-1,p)\)。受限和 \(A\hat{+}A\) 的类似结果花了远为更长的时间才被证明。容易看出当 \(2|A|-3\ge p\) 时 \(|A\hat{+}A|=p\)（习题 9.2.1）。1964 年，Erdős 与 Heilbronn（见 [89]）猜想 \(|A\hat{+}A|\ge\min(2|A|-3,p)\)；该界易见是最优的（习题 9.2.3）。这个看似无害的 Cauchy–Davenport 变体，约三十年间一直抵抗着求解的尝试；5.1 节的 e-变换方法似乎无法证明 Erdős–Heilbronn 猜想。该猜想终于在 1994 年由 da Silva 与 Hamidoune [66] 解决，他们用关于 Grassmann 空间的一个一般结果加以确认。我们现在给出 Alon、Nathanson 与 Ruzsa [11] 利用组合零点定理给出的简短证明，它展示了这一方法的威力与简洁。事实上还能多证明一点：

定理 9.5 [11]设 \(F=F_p\)（\(p\) 为素数），\(A,B\) 为 \(F\) 中两个加性集。则 \[|A\hat{+}B|\ \ge\ \min(|A|+|B|-3,\ p).\] 此外，若 \(|A|\neq|B|\)，则上界可改进为 \[|A\hat{+}B|\ \ge\ \min(|A|+|B|-2,\ p).\]
译注：关于“两集大小不等”的条件原书此处印作“若 \(|A|=|B|\)”，但由下面证明里出现的因子 \((|A|-|B|)\) 可知：改进到 \(-2\) 恰恰要求 \(|A|\neq|B|\)（否则该系数为零，机器失效）。这也与文献中 Alon–Nathanson–Ruzsa 的标准表述一致：两集等大时只能到 \(-3\)（取 \(A=B=\{0,1,\dots,k\}\) 即见 \(-2\) 不可达），两集不等大时才能到 \(-2\)。故此处按正确数学陈述为 \(|A|\neq|B|\)。
证明. 情形 \(|A|+|B|-2\ge p\) 是容易的（习题 9.2.1），故设 \(|A|+|B|-2♦
例：系数为什么这样算展开 \((t_1-t_2)(t_1+t_2)^K\)，盯住目标单项式 \(t_1^{|A|-1}t_2^{|B|-1}\)。
  1. \((t_1+t_2)^K=\sum_j\binom{K}{j}t_1^{\,j}t_2^{\,K-j}\)。
  2. 乘上 \(+t_1\)：得 \(t_1^{\,j+1}t_2^{\,K-j}\)，要它等于目标需 \(j+1=|A|-1\) 即 \(j=|A|-2\)，此时贡献 \(+\binom{K}{|A|-2}\)。
  3. 乘上 \(-t_2\)：得 \(t_1^{\,j}t_2^{\,K-j+1}\)，要它等于目标需 \(j=|A|-1\)，此时贡献 \(-\binom{K}{|A|-1}\)。
  4. 两者相加并整理出公因子，得到上面那个含 \((|A|-|B|)\) 的式子。当 \(|A|=|B|\) 时它整体为零——这就是“等大时机器卡住、必须删一个元素”的根源。♦
例：在 \(F_{11}\) 中的 \(A\hat{+}A\)取 \(p=11\)，\(A=\{0,1,2,3\}\)，\(|A|=4\)。Erdős–Heilbronn 界为 \(\min(2\cdot4-3,11)=5\)。直接算：所有 \(a+b\)（\(a\neq b\)）为 \(0{+}1,0{+}2,0{+}3,1{+}2,1{+}3,2{+}3=1,2,3,3,4,5\)，去重得 \(\{1,2,3,4,5\}\)，共 \(5\) 个，恰好达到下界。

更复杂的受限相加：Vandermonde 行列式登场

显然还能从引理 9.3 得到更多应用；例如见习题 9.2.4。但当我们考虑多个集合的受限和时，就开始需要研究越来越复杂的多项式的系数，这些表达式常涉及 Vandermonde 行列式之类的对象。因此我们接下来转向研究这类多项式及其系数。这里的计算将是完全抽象的，对取值于任意域 \(F\) 的不定元 \(x_1,\dots,x_n\) 都成立。

定义 9.6（Vandermonde 行列式）若 \(n\ge 1\)，\(x_1,\dots,x_n\) 为不定元，定义 Vandermonde 行列式为 \[\Delta_n(x_1,\dots,x_n):=\prod_{1\le i

容易验证以下对称性： \[\begin{aligned} &\Delta_n(x_1+y,\dots,x_n+y)=\Delta_n(x_1,\dots,x_n);\\ &\Delta_n(\lambda x_1,\dots,\lambda x_n)=\lambda^{\binom{n}{2}}\Delta_n(x_1,\dots,x_n);\\ &\Delta_n(\pi(x))=\operatorname{sgn}(\pi)\,\Delta_n(x) \end{aligned}\tag{9.2}\] 对任意变量 \(\lambda,y\)，任意 \(x=(x_1,\dots,x_n)\) 及任意置换 \(\pi\in S_n\) 成立。事实上这（在相差常数倍意义下）实际上确定了 \(\Delta_n\)，见习题 9.2.5。量 \(\Delta_n(1,\dots,n)=\prod_{i=1}^n (i-1)!\) 有时被称为 \(n\) 的超阶乘（superfactorial）。

平移不变 所有 \(x_i\) 同时 加 \(y\)，差不变 \(\Delta_n\) 不变 齐次缩放 所有 \(x_i\) 乘 \(\lambda\) \(\Delta_n\to\lambda^{\binom n2}\Delta_n\) 交错对称 交换两变量 \(\Delta_n\to\operatorname{sgn}(\pi)\Delta_n\)
三条对称性 (9.2)：平移不变、按 \(\binom n2\) 次齐次、按置换符号交错。第三条意味着任何两个变量相等时 \(\Delta_n=0\)（交换它们应变号，又应不变，故为零）。

下面这个著名事实留作习题：

引理 9.7设 \(n\ge 1\)，对每个 \(1\le i\le n\) 设 \(P_i(x)\) 为次数 \(i-1\) 的首一多项式。则对任意变量 \(x_1,\dots,x_n\) 有恒等式 \[\det\bigl(P_i(x_j)\bigr)_{1\le i,j\le n} =\sum_{\pi\in S_n}\operatorname{sgn}(\pi)\prod_{i=1}^n P_{\pi(i)}(x_i) =\sum_{\pi\in S_n}\operatorname{sgn}(\pi)\prod_{i=1}^n P_i\bigl(x_{\pi(i)}\bigr) =\Delta_n(x_1,\dots,x_n).\] 特别地有 \[\Delta_n(x_1,\dots,x_n)=\sum_{\pi\in S_n}\operatorname{sgn}(\pi)\prod_{i=1}^n x_i^{\pi(i)-1}.\tag{9.3}\]

公式 (9.3) 精确地算出了 \(\Delta_n(x_1,\dots,x_n)\) 的各项系数。把它与多项式定理（多项式幂展开） \[(x_1+\dots+x_n)^K=\sum_{\substack{c_1,\dots,c_n\ge 0\\ c_1+\dots+c_n=K}}\frac{K!}{c_1!\cdots c_n!}\prod_{i=1}^n x_i^{c_i}\] 相乘，便得到公式 \[(x_1+\dots+x_n)^K\,\Delta_n\bigl(x_1^{m},\dots,x_n^{m}\bigr) =\sum_{\substack{c_1,\dots,c_n\ge 0\\ c_1+\dots+c_n=K+m\binom n2}}\ \sum_{\pi\in S_n}\frac{\operatorname{sgn}(\pi)\,K!}{\prod_{i=1}^n\bigl(c_i-\pi(i)m+m\bigr)!}\prod_{i=1}^n x_i^{c_i},\tag{9.4}\] 其中约定：当 \(k\) 为负整数时 \(1/k!=0\)。

读 (9.3) 与 (9.4) 的直觉不必被记号吓住，核心只有两点。
  1. (9.3) 是“行列式 = 带符号求和”。\(\Delta_n\) 本是 \(\prod_{i
  2. (9.4) 是“两个已知展开相乘后收集同类项”。左边 \(=\) (多项式幂的展开) \(\times\) (把 \(x_i\) 换成 \(x_i^{m}\) 的 \(\Delta_n\) 展开)。两边都按单项式 \(\prod x_i^{c_i}\) 收集，指数和必为 \(K+m\binom n2\)。右边那个分母 \(\prod (c_i-\pi(i)m+m)!\) 与“\(1/(\text{负数})!=0\)”的约定，正是为了自动剔除不可能出现的项。

在某些情形下，(9.4) 右端的表达式可以化简。例如在 \(m=1\) 的情形我们有：

引理 9.8设 \(n,K\ge 0\)。则 \[(x_1+\dots+x_n)^K\,\Delta_n(x_1,\dots,x_n) =\sum_{\substack{c_1,\dots,c_n\ge 0\\ c_1+\dots+c_n=K+\binom n2}}\frac{K!}{c_1!\cdots c_n!}\,\Delta_n(c_1,\dots,c_n)\,x_1^{c_1}\cdots x_n^{c_n}.\tag{9.5}\]
证明. 由 (9.4)，只需建立恒等式 \[\sum_{\pi\in S_n}\operatorname{sgn}(\pi)\,\frac{K!}{\prod_{i=1}^n(c_i-\pi(i)+1)!} =\frac{K!}{c_1!\cdots c_n!}\,\Delta_n(c_1,\dots,c_n).\] 若引入下降阶乘 \[(x)_n:=x(x-1)\cdots(x-n+1),\tag{9.6}\] 则由引理 9.7 有 \[\Delta_n(c_1,\dots,c_n)=\sum_{\pi\in S_n}\operatorname{sgn}(\pi)\prod_{i=1}^n (c_i)_{\pi(i)-1} =\sum_{\pi\in S_n}\operatorname{sgn}(\pi)\prod_{i=1}^n\frac{c_i!}{(c_i-\pi(i)+1)!},\] 结论随之成立。♦

这条引理已经给出了 Erdős–Heilbronn 猜想的一个推广；见习题 9.2.9 与 9.2.10。

本着类似的精神我们有：

引理 9.9设 \(n,m,K,k\ge 0\) 满足 \[(k-1)+(k-2)+\dots+(k-n)=K+m\binom n2.\] 则 \(x_1^{\,k-n}x_2^{\,k-n+1}\cdots x_n^{\,k-1}\) 在 \((x_1+\dots+x_n)^K\,\Delta_n(x_1^{m},\dots,x_n^{m})\) 中的系数为 \[\frac{K!}{\prod_{i=1}^n\bigl(k-1-(i-1)m\bigr)!}\;m^{\binom n2}\,\Delta_n(1,\dots,n).\]
证明. 由 (9.4)，只需建立恒等式 \[\sum_{\pi\in S_n}\operatorname{sgn}(\pi)\,\frac{K!}{\prod_{i=1}^n\bigl(k-n-1+i-\pi(i)m+m\bigr)!} =\frac{K!}{\prod_{i=1}^n\bigl(k-1-(i-1)m\bigr)!}\;m^{\binom n2}\,\Delta_n(1,\dots,n).\] 将 \(i\) 用 \(\pi(i)\) 重新标号，并利用 \(\operatorname{sgn}(\pi)=\operatorname{sgn}(\pi^{-1})\)，左端可改写为 \[\sum_{\pi\in S_n}\operatorname{sgn}(\pi)\,\frac{K!}{\prod_{i=1}^n\bigl(k-n-1+\pi(i)-(i-1)m\bigr)!},\] 再借助下降阶乘 (9.6) 写成 \[\frac{K!}{\prod_{i=1}^n\bigl(k-1-(i-1)m\bigr)!}\sum_{\pi\in S_n}\operatorname{sgn}(\pi)\prod_{i=1}^n\bigl(k-1-(i-1)m\bigr)_{n-\pi(i)}.\] 令 \(n-\pi(i)=\alpha(i)-1\)，并注意 \(\operatorname{sgn}(\pi)=(-1)^{\binom n2}\operatorname{sgn}(\alpha)\)，进一步改写为 \[(-1)^{\binom n2}\frac{K!}{\prod_{i=1}^n\bigl(k-1-(i-1)m\bigr)!}\sum_{\alpha\in S_n}\operatorname{sgn}(\alpha)\prod_{i=1}^n\bigl(k-1-(i-1)m\bigr)_{\alpha(i)-1},\] 由引理 9.7 这变为 \[(-1)^{\binom n2}\frac{K!}{\prod_{i=1}^n\bigl(k-1-(i-1)m\bigr)!}\,\Delta_n\bigl(k-1,\,k-1-m,\,\dots,\,k-1-(n-1)m\bigr).\] 最后由对称性 (9.2)（平移不变与齐次缩放）即得结论。♦

作为此计算的一个推论，我们得到下面关于多重受限相加的加性组合学结论，其中限制具有 \(P_i(a_i)\neq P_j(a_j)\) 的形式（\(P_i,P_j\) 为多项式）。

定理 9.10 [234]设 \(k,m,n\) 为正整数，使得量 \[K:=(k-1)n-(m+1)\binom n2\] 非负。设 \(F\) 为特征是零、或是大于 \(\max(K,m,n-1)\) 的素数的域。设 \(A_1,\dots,A_n\) 为 \(F\) 的子集，满足 \(|A_i|\ge k-n+i\)（对所有 \(1\le i\le n\)）。设 \(P_1,\dots,P_n\in F[t]\) 为次数 \(m\) 的首一多项式。则 \[\bigl|\{\,a_1+\dots+a_n\mid a_i\in A_i,\ P_i(a_i)\neq P_j(a_j)\ \text{若}\ i\neq j\,\}\bigr|\ \ge\ K+1.\]
证明. 不失一般性可设 \(|A_i|=k-n+i=:k_i\)。令 \(f\in F[t_1,\dots,t_n]\) 为多项式 \[f(t_1,\dots,t_n):=\prod_{1\le i♦
例：定理 9.10 是怎样“吃掉”限制的取最简单的 \(P_i(t)=t\)（即 \(m=1\)），限制 \(P_i(a_i)\neq P_j(a_j)\) 就退化为 \(a_i\neq a_j\)，即“所有被加项两两不同”。此时 \(K=(k-1)n-2\binom n2=(k-1)n-n(n-1)\)，得到的正是“\(n\) 个两两不同元素之和”的下界——也就是把 Erdős–Heilbronn 推广到多重相加。换更高次的 \(P_i\)（\(m\ge 2\)），就能处理诸如 \(a_i^2\neq a_j^2\) 之类更花哨的限制。

把 \((x_j-x_i)\) 升幂：Dyson 猜想

接下来考虑：若把 \(\Delta_n(x_1,\dots,x_n)\) 中的因子 \((x_j-x_i)\) 升到任意幂次会怎样。这方面一个有用的结果是：

定理 9.11（Dyson 猜想）设 \(a_1,\dots,a_n\) 为正整数。则 \(\prod_{i=1}^n x_i^{(n-1)a_i}\) 在 \[\prod_{\substack{i,j\in[1,n]\\ i\neq j}}(x_j-x_i)^{a_j}\] 中的系数为 \[\frac{(a_1+\dots+a_n)!}{a_1!\cdots a_n!}.\]

此结果由 Dyson [74] 基于粒子物理中的一个问题猜出。它于 1962 年由 Gunson [165] 验证，并由 Wilson [383] 独立验证。我们呈现 Good [135] 给出的一个简短而优雅的证明。

证明. 令 \(x=(x_1,\dots,x_n)\)，\(a=(a_1,\dots,a_n)\)，并设 \[F(x,a)=\prod_{\substack{i,j\in[1,n]\\ i\neq j}}\Bigl(1-\frac{x_i}{x_j}\Bigr)^{a_j},\] 以 \(F_0(a)\) 记 \(F(x,a)\) 中的常数项。只需证明：当所有 \(a_i\) 为非负整数时 \(F_0(a)=\dfrac{(a_1+\dots+a_n)!}{a_1!\cdots a_n!}\)。 我们对 \(n\) 归纳。\(n=0\) 时结论平凡，故设 \(n\ge 1\) 且对 \(n-1\) 已证。此时可设没有任何 \(a_i\) 为零（否则可直接消去该变量——注意此时变量 \(x_i\) 只以正指数出现——再用归纳假设）。于是对所有 \(i\in[1,n]\) 有 \(a_i\ge 1\)。 设 \(e_1,\dots,e_n\) 为 \(\mathbb{Z}^n\) 的标准基向量。只需证明递推 \[F_0(a)=\sum_{i=1}^n F_0(a-e_i)\quad(\text{当所有 }a_i\ge 1),\] 因为结论随之由多项式版 Pascal 恒等式以及对 \(\sum_{i=1}^n a_i\) 的简单归纳而得。 对函数 \(f(x)\equiv 1\) 应用 Lagrange 插值公式（习题 9.2.8），得恒等式 \[1=\sum_{j=1}^n\prod_{\substack{i\in[1,n]\\ i\neq j}}(x_j-x_i)^{-1}(y-x_i)\qquad(\text{对所有 }y).\] 令 \(y=0\) 得 \[1=\sum_{j=1}^n\prod_{\substack{i\in[1,n]\\ i\neq j}}\Bigl(1-\frac{x_i}{x_j}\Bigr)^{-1}.\tag{9.7}\] 将 (9.7) 两边同乘 \(F(x,a)\)，便见若对所有 \(1\le j\le n\) 有 \(a_j>0\)，则有递推 \[F(x,a)=\sum_{j=1}^n F(x,a-e_j),\] 取常数项即得结论。♦
为什么常数项就是这个系数把 Laurent 多项式 \(F(x,a)\) 与多项式 \(\prod_{i\neq j}(x_j-x_i)^{a_j}\) 联系起来。
  1. 逐因子化简：\(\Bigl(1-\dfrac{x_i}{x_j}\Bigr)^{a_j}=\dfrac{(x_j-x_i)^{a_j}}{x_j^{\,a_j}}\)。
  2. 对所有 \(i\neq j\) 取乘积：分母里 \(x_j\) 的总幂次为 \(\sum_{i\neq j}a_j=(n-1)a_j\)，故 \(F(x,a)=\dfrac{\prod_{i\neq j}(x_j-x_i)^{a_j}}{\prod_j x_j^{(n-1)a_j}}\)。
  3. 因此 \(F\) 的常数项，恰好等于分子中单项式 \(\prod_j x_j^{(n-1)a_j}\) 的系数——这正是定理 9.11 所求。
  4. Good 的证明妙在：用 Lagrange 插值得到的 (9.7) 把 \(1\) 写成 \(n\) 个分式之和，乘进去就把 \(F(x,a)\) 拆成 \(\sum_j F(x,a-e_j)\)，于是常数项满足多项式 Pascal 递推，归纳即得多项式系数。♦

作为定理 9.11 的一个特例，我们看到 \(\prod_{i=1}^n x_i^{(n-1)m}\) 在 \(\Delta_n(x_1,\dots,x_n)^{2m}\) 中的系数为 \((nm)!/(m!)^n\)。利用此事实及一些附加论证，Hou 与 Sun [186] 证明了如下推广。

引理 9.12设 \(n,m,k\ge 0\)，并令 \(s:=k+m(n-1)\)。则 \(x_1^{s}\cdots x_n^{s}\) 在 \((x_1+\dots+x_n)^{km}\,\Delta_n(x_1,\dots,x_n)^{2m}\) 中的系数为 \[(-1)^{m\binom n2}\,\frac{(km)!}{(m!)^n}\prod_{j=1}^n\frac{(jm)!}{(s-(j-1)m)!}.\]

该定理的证明颇为技术性，细节请参阅 [186]。作为一个加性组合学推论，我们能控制这样的受限和集——其中要求各差 \(a_i-a_j\) 避开某些指定集合。

定理 9.13 [186]设 \(k,m,n\) 为正整数，\(F\) 为特征 \(p\) 的域，其中 \(p\) 为零、或为满足 \[p\ \ge\ n\,\max\{m,\ n+m-mk-1\}\] 的素数。设 \(A_1,\dots,A_k\) 为 \(F\) 的子集，基数至少为 \(n\)。对任意 \(i,j\in\{1,\dots,k\}\)、\(i\neq j\)，设 \(S_{ij}\) 为 \(F\) 的一个基数至多为 \(m\) 的子集。则集合 \[C:=\{\,a_1+\dots+a_k\mid a_i\in A_i,\ a_i-a_j\notin S_{ij}\ \text{若}\ i\neq j\,\}\] 的基数至少为 \[|C|\ \ge\ (n+m-mk-1)k+1.\]
证明. 我们先需要定理 9.3 的如下变体，其证明留作习题 9.2.11。
引理 9.14设 \(A_1,\dots,A_k\) 为域 \(F\) 的有限子集，假设 \(|A_i|\ge n_i\)。设 \(\lambda,\mu\in F[t_1,\dots,t_k]\) 满足 \(\deg(\mu)>0\)。定义 \[C:=\{\,\mu(a_1,\dots,a_k)\mid a_i\in A_i,\ \lambda(a_1,\dots,a_k)\neq 0\,\}.\] 则不存在多项式 \(\omega\in F[t_1,\dots,t_k]\) 使得多项式 \(\lambda\omega\mu^{|C|}\) 的次数为 \(\sum_{i=1}^k(n_i-1)\) 且其中 \(x_1^{n_1-1}\cdots x_k^{n_k-1}\) 的系数非零。
为证明定理 9.13，不失一般性可设对所有 \(i,j\) 有 \(|A_i|=n\) 且 \(|S_{ij}|=m\)。令 \(l:=n+m-mk-1\)。反设 \(|C|\le lk\)（与所证下界 \(lk+1\) 矛盾）。令 \(\lambda,\mu,\omega\in F[t_1,\dots,t_k]\) 为多项式 \[\lambda(t_1,\dots,t_k):=\prod_{1\le i\neq j\le k}\ \prod_{c\in S_{ij}}(t_i-t_j-c),\qquad \mu(t_1,\dots,t_k):=t_1+\dots+t_k,\qquad \omega:=\mu^{\,kl-|C|}.\] 多项式 \(\lambda\omega\mu^{|C|}\) 的总次数为 \(mk(k-1)+lk=k(n-1)=\sum_{i=1}^k(|A_i|-1)\)。此外，该多项式中 \(t_1^{n-1}\cdots t_k^{n-1}\) 的系数，与下式中同一单项式的系数相同： \[\prod_{1\le i♦
把定理 9.13 翻成大白话每个被加项 \(a_i\) 从自己的集合 \(A_i\) 里取，并且任意两项之差 \(a_i-a_j\) 都不许落在禁区 \(S_{ij}\) 里。即便加了这么多“差的限制”，所有合法的和 \(a_1+\dots+a_k\) 仍然占据相当多的值——至少 \((n+m-mk-1)k+1\) 个。证明的套路与前面完全一致：把“限制”编码进多项式 \(\lambda\)（每个禁区元素对应一个线性因子），用 \(\mu=\sum t_i\) 表示“求和”，再用引理 9.14 把“和集太小”归谬到“某系数非零”。这个非零系数来自 Dyson/Hou–Sun 关于 \(\Delta_k^{2m}\) 的计算。

习题

习题 9.2
  1. 9.2.1　设 \(Z\) 为任意奇数阶有限加性群，\(A,B\) 为 \(Z\) 中的加性集。证明：若 \(|A|+|B|-2\ge|Z|\)，则 \(A\hat{+}B=Z\)。（与习题 2.1.6 比较。）
  2. 9.2.2　当 \(|A|=1\) 或 \(|B|=1\) 时验证定理 9.5。
  3. 9.2.3　举例说明界 \(|A\hat{+}A|\ge\min(2|A|-3,p)\) 不能被改进。当 \(|A|\neq|B|\) 时，界 \(|A\hat{+}B|\ge\min(|A|+|B|-2,p)\) 又如何？
  4. 9.2.4　设 \(F=F_p\) 为素数阶有限域，\(A,B\) 为 \(F_p\) 中的加性集。证明 \[\bigl|\{\,a+b\mid a\in A,\ b\in B,\ ab=1\,\}\bigr|\ \ge\ \min(|A|+|B|-3,\ p).\]
  5. 9.2.5　验证对称性 (9.2)。进而证明：若多项式 \(P(x_1,\dots,x_n)\) 满足与 \(\Delta_n\) 相同的对称性 (9.2)，则 \(P\) 是 \(\Delta_n\) 的标量倍。
  6. 9.2.6　证明引理 9.7。（提示：可用高斯消元归约到 \(P_i(x)=x^{i-1}\) 的情形；再找出 \(\Delta_n(x_1,\dots,x_n)\) 的若干线性因子并用因式定理。或者用习题 9.2.5。）
  7. 9.2.7　证明：若 \(x_1,\dots,x_n\) 为整数，则 \(\Delta_n(x_1,\dots,x_n)\) 是 \(\Delta_n(1,\dots,n)=\prod_{i=1}^n(i-1)!\) 的倍数。
  8. 9.2.8　（Lagrange 插值公式）设 \(F\) 为域，\(n\ge 0\)，\(a_0,\dots,a_n\) 为 \(F\) 的 \(n+1\) 个不同元素，\(b_0,\dots,b_n\) 为 \(F\) 的 \(n+1\) 个任意元素。证明恰存在一个次数至多 \(n\)、系数在 \(F\) 中的多项式 \(f\in F[t]\) 使得 \(f(a_i)=b_i\)，且该多项式由下式给出： \[f(x)=\sum_{i=0}^n b_i\prod_{0\le j\neq i\le n}(a_i-a_j)^{-1}(x-a_j).\]
  9. 9.2.9　[11] 设 \(F=F_p\) 为素数阶有限域，\(A_1,\dots,A_k\) 为 \(F_p\) 中的加性集，其中 \(|A_1|,\dots,|A_k|\) 两两不同且 \(\sum_{i=1}^k|A_i|\le p+\binom{k+1}{2}-1\)。设 \(B\) 为受限和集 \[B:=\{\,a_1+\dots+a_k:\ a_i\in A_i,\ a_i\neq a_j\ \text{对所有 }1\le i
  10. 9.2.10　[66]（广义 Erdős–Heilbronn 猜想）设 \(F=F_p\) 为素数阶有限域，\(A\) 为 \(F_p\) 中的加性集。令 \[k\wedge A:=\{\,a_1+\dots+a_k:\ a_1,\dots,a_k\in A,\ a_i\neq a_j\ \text{对所有 }1\le i
  11. 9.2.11　证明引理 9.14。（提示：对多项式 \(f:=\lambda\omega\prod_{c\in C}(\mu-c)\) 应用组合零点定理。）

返回 全书目录