下面的讨论都在域 $\mathcal{F}$ 上进行。

组合零点定理

Theorem 1: (组合零点定理) 给定任意多项式 $f \in \mathcal{F}[x_{1},x_{2},\ldots ,x_n]$ 以及 $n$ 个集合 $S_n$, 定义另外 $n$ 个多项式 $g_i\coloneqq \prod_{s \in S_i} (x_i-s)$。

若 $f$ 在 $x \in S_{1}\times S_{2}\times \ldots S_n$ 时恒为 $0$，则 $f$ 可以被 $g_1,g_2\ldots g_n$ 线性组合表示，即：

Note: $g_i$ 在 $x_i \in S_i$ 时为零，否则非零

定理证明

Lemma 1: $f \in \mathcal{F}[x_{1},x_{2},\ldots ,x_n]$，并且 $f$ 中 $x_i$ 的次幂最高是 $t_i$。则如果对任意 $i$ 都存在一个大小 大于 $t_i$ 的集合 $S_i$。使得 $f$ 在 $x \in S_{1}\times S_{2}\times \ldots \times S_n$ 上恒为 $0$，则 $f=0$.

Note: $n=1$ 的情形对应于多项式的根的个数不超过其次数。

Proof: 对 $n$ 归纳，$n=1$ 时成立，对于 $n>1$：

• 首先提取出 $x_n$，将 $f$ 表示为：

• 接下来，固定 $x_{1},x_{2},\ldots x_{n-1} \in S_{1}\times S_2 \times \ldots S_{n-1}$ 的取值，则关于的 $x_n$ 多项式在 $x_n \in S_n$ 恒为 $0$。由一维情形成立，这表示 $q_i(x_1,x_2,\ldots x_{n-1})=0, \forall x_{1},x_{2},\ldots x_{n-1} \in S_{1}\times S_2 \times \ldots S_{n-1}$。从而由于归纳假设 $q_i=0$。

Proof of Theorem 1:

令 $t_i=|S_i|-1$，则 $\deg g_i=t_i+1$。当 $f$ 中 $x_i$ 的幂次高于 $t_i$ 时，我们可以将 $f$ 对于 $g_i$ 取模（多项式意义下）。从而最终 $f$ 中剩下的所有项里面，$x_i$ 的次幂都 $\le t_i$。由于 Lemma 1 ，可知剩下的部分为 $0$，从而我们找到正确的了 $g_i$ 的线性组合。

应用

Corollary: 多项式 $f \in \mathcal{F}[x_{1},x_{2}\ldots x_n]$, $\deg f = \sum_{i=1}t_i$。 并且 $f$ 的 $\prod_{i=1}^{n} x_i^{t_i}$ 项对应系数非零。任意 $n$ 个集合 $S_{1}\ldots S_n$ （其中 $|S_i|>t_i$），$\exists x_i \in S_i, f(x_{1},x_{2},\ldots x_n)\neq 0$

Proof: 反证，如果 $f$ 在 $S_{1}\times S_{2}\times \ldots S_n$ 上全为0，则由 Theorem 1, $f=\sum_{i=1} h_i g_i$ 。然而 $f$ 中 $\prod_{i=1}^{n} x_i^{t_i}$ 一项在 RHS 无法与任何一项对应：

• 由于 $\deg \prod_{i=1}^{n} x_i^{t_i}=\deg f$ 和 $\deg g_i+\deg h_i\le \deg f$ 我们知道，只有 $g_i h_i$ 中的最高次项有可能对应上 $\prod_{i=1}^{n} x_i^{t_i}=\deg f$
• 然而 $g_i h_i$ 的最高次项必然包含 $x_i^{t_i+1}$，从而无法对应 $\prod_{i=1}^{n} x_i^{t_i}$

Note: 使用这个推论时，需要构造 $f$ 的多项式，使得 $\prod_{i=1}^{n} x_i^{t_i}$ 项非零，并且让多项式的非零赋值对应我们需要证明 存在 的某个各东西。

Permanent Lemma

Definition: (Permanent) 给定一个 $n\times n$ 的矩阵 $A$，其元素为 $a_{ij}$，则 $A$ 的 permanent 定义为：

Theorem: 给定一个 $n\times n$ 的矩阵 $A$，其元素为 $a_{ij}$，$\text{perm}(A)\neq 0$。则任给一个向量 $b$ 和 $n$ 个大小大于 $1$ 的集合 $S_{1},S_{2},\ldots ,S_n$，都存在一个向量 $x \in S_{1}\times S_{2}\times \ldots S_n$，使得 $(Ax)_i\neq b_i, \forall i$

Proof: 构造多项式 $f=\prod_{i=1}^{n} (\sum_{j=1}^{n} a_{ij}x_j -b_i)$，如果 $x$ 满足条件，则 $f(x)\neq 0$。此时，$f$ 的 $\prod_{i=1}^n x_i$ 对应系数为 $\text{perm}(A)\neq 0$。

Cauchy-Davenport Thm

Theorem: $A,B \in Z_p$, 则 $|A+B| \geq \min(p,|A|+|B|-1)$

Proof:

1. $|A|+|B|\ge p+1$ 需要说明 $A+B=Z_p$

假设 $\exists x \in Z_p \text{ s.t. } x \not\in A+B$。则 $z=0+z=1+(z-1)=2+(z-2)\ldots =(p-1)+(z-(p-1))$ 共有 $p$ 种，然而 $A+B$ 总共有 $p+1$ 个元素，因此必然有一个能成。

2. $|A|+|B|\le p$，反证，若 $|A+B|\le |A|+|B|-2$，则可以找到 $C \subset Z_p, |C|=|A|+|B|-2, A+B \subset C$。于是可以构造多项式：