Schwartz-Zippel引理

的<年代trong>Schwartz-Zippel引理是一个帮助检测何时多项式等于零。它在以下方面很有用图论以及理论计算机科学。

内容

动机
引理的表述
图论的应用
引理的证明

动机

引理的动机是以下问题:

给定一个多项式<年代pan class="katex"> $f (x_1、x_2 \ ldots x_n)$ $f （ x_{1} ， x_{2} ， .．. ， x_{n} ）$ a中的系数场 $F,$ 是<年代pan class="katex"> $f$ $f$ 零多项式?

这取决于<年代pan class="katex"> $f$ $f$ 的定义，有时显式地代入变量的值比完全展开多项式并检查至少一个系数非零要容易得多。例如,如果<年代pan class="katex"> $f$ $f$ 是大量术语(例如行列式)，展开乘积和求系数具有指数级的复杂度<年代pan class="katex"> $f。$ $f ．$

如果在某一组值处求值得到非零答案，则该多项式不是零多项式;但如果在一组随机选择的值处求值<年代pan class="katex"> $0，$ $0 ，$ 多项式可能为零也可能不为零。Schwartz-Zippel引理给出了多项式在后一种情况下为零的概率上限，这使得它对于概率检验足够的应用非常有用。

引理的表述

让<年代pan class="katex"> $F$ $F$ 是一个场．让<年代pan class="katex"> $f (x_1、x_2 \ ldots x_n)$ $f （ x_{1} ， x_{2} ， .．. ， x_{n} ）$ 是总次数的多项式<年代pan class="katex"> $d$ $d$ ，假设<年代pan class="katex"> $f$ $f$ 不是零多项式。让<年代pan class="katex"> $年代$ $年代$ 的有限子集<年代pan class="katex"> $F。$ $F ．$ 让<年代pan class="katex"> $r_1, r_2 \ ldots r_n$ $r_{1} ， r_{2} ， .．. ， r_{n}$ 随机、一致、独立地选择<年代pan class="katex"> $年代。$ $年代．$ 那么这个概率<年代pan class="katex"> $f (r_1, r_2 \ ldots r_n) = 0$ $f （ r_{1} ， r_{2} ， .．. ， r_{n} ）＝ 0$ 是<年代pan class="katex"> $le \ \压裂{d}{| |}。$ $\leq \frac{d}{∣ 年代 ∣} ．$

备注:

(1)如果<年代pan class="katex"> $n = 1,$ $n ＝ 1 ，$ 然后根据一个次多项式的事实得到结果<年代pan class="katex"> $d$ $d$ 在一片田野上最多<年代pan class="katex"> $d$ $d$ 田地里的根。<年代pan class="katex"> $（$ $（$ 这是根据辗转相除法为<年代pan class="katex"> $F (x)$ $F ［ x ］$ 并且存在独特的因式分解成不可约项<年代pan class="katex"> $F (x);$ $F ［ x ］；$ 注意这个事实不是真的，如果<年代pan class="katex"> $F$ $F$ 替换为整数mod<年代pan class="katex"> $8)。$ $8 ．）$ 当且仅当，相等在引理的不相等中成立<年代pan class="katex"> $f$ $f$ 有<年代pan class="katex"> $d$ $d$ 根和<年代pan class="katex"> $年代$ $年代$ 包含所有它们。上一节给出的引理的证明是一个归纳<年代pan class="katex"> $n,$ $n ，$ 所以这个论点<年代pan class="katex"> $n = 1$ $n ＝ 1$ 建立基本情况。

(2)重复选择元素的过程<年代pan class="katex"> $年代$ $年代$ 说,<年代pan class="katex"> $k$ $k$ 乘以<年代pan class="katex"> $f$ $f$ 计算结果为<年代pan class="katex"> $0$ $0$ 每次都是<年代pan class="katex"> $le \ \离开(\压裂{d} {S | |} \右)^ k。$ $\leq （ \frac{d}{∣ 年代 ∣} ）^{k} ．$ 如果<年代pan class="katex"> $d < | |$ $d < ∣ 年代 ∣$ 而且<年代pan class="katex"> $k$ $k$ 如果足够大，这个概率就会变得非常小。这就是重点:如果这个过程重复了足够多的次数，那么一个非零多项式每次求值为零的概率就会小于<年代pan class="katex"> $\ frac1 {10 ^ 6}$ $\frac{1}{1 0 ^{6}}$ ——并且给定的多项式每次都求0，那么我们很有信心这个多项式等于0。这不是一个确定的算法，当然有可能<年代pan class="katex"> $f$ $f$ 并不等于零，而且这个过程碰巧做出了百万分之一的选择，但它又快又实用。

(3)引理还有其他类似的版本。例如，如果每个<年代pan class="katex"> $r_i$ $r_{我}$ 是从子集中选择的<年代pan class="katex"> $S_i$ $年代_{我}$ 的<年代pan class="katex"> $F,$ $F ，$ 和程度<年代pan class="katex"> $f$ $f$ 作为一个多项式<年代pan class="katex"> $x_i$ $x_{我}$ 是<年代pan class="katex"> $d1,$ $d_{我} ，$ 引理的另一种形式是概率<年代pan class="katex"> $f (r_1, r_2 \ ldots r_n) = 0$ $f （ r_{1} ， r_{2} ， .．. ， r_{n} ）＝ 0$ 最多是<年代pan class="katex"> $\ \和limits_ {i = 1} ^ n \ dfrac {d_i} {| S_i |}。$ $我＝ 1 \sum n \frac{d _{我}}{∣ 年代 _{我} ∣} ．$

(4)如果<年代pan class="katex"> $年代$ $年代$ 是一个有限域，这里有一个额外的问题，一些不是零多项式的多项式仍然求值为<年代pan class="katex"> $0$ $0$ 无处不在。例如,费马小定理意味着<年代pan class="katex"> $x ^ px$ $x^{p} - x$ 有一个这样的多项式吗<年代pan class="katex"> ${\ mathbb F} _p [x]。$ $F_{p} ［ x ］．$ 对于这样的多项式，Schwartz-Zippel不能给出任何有意义的信息，实际上这是因为度<年代pan class="katex"> $d = p$ $d ＝ p$ 是<年代pan class="katex"> $通用电气\ | |$ $\geq ∣ 年代 ∣$ 对于任何一个子集<年代pan class="katex"> $年代$ $年代$ 的<年代pan class="katex"> ${\ mathbb F} _p。$ $F_{p} ．$ 也就是说,Schwartz-Zippel仅在多项式的次d小于场的大小时才有用<年代pan class="katex"> $F。$ $F ．$

让<年代pan class="katex"> $F = {\mathbb F}_3，$ $F ＝ F_{3.} ，$ 国防部的整数<年代pan class="katex"> $3.$ $3. ．$ 让<年代pan class="katex"> $f (x, y) = x (x + y)。$ $f （ x ， y ）＝ x （ x + y ）．$ 让<年代pan class="katex"> $S = F。$ $年代＝ F ．$ 然后schwarz - zippel说概率<年代pan class="katex"> $(r, s)$ $（ r ，年代）$ 是0<年代pan class="katex"> $f$ $f$ 是<年代pan class="katex"> $\ \ frac23。$ $\leq \frac{2}{3.} ．$ 九对有序的<年代pan class="katex"> $(r, s)$ $（ r ，年代）$ 考虑一下，它们中有五个是零:<年代pan class="katex"> $(0,0)(0,1)(0,2)(1,2)(2,1)。$ $（ 0 ， 0 ），（ 0 ， 1 ），（ 0 ， 2 ），（ 1 ， 2 ），（ 2 ， 1 ）．$ 的确,<年代pan class="katex"> $\ frac59 \ \ frac23。$ $\frac{5}{9} \leq \frac{2}{3.} ．$ Schwartz-Zippel给出了一个非零多项式零个数的非平凡上界;对于2次多项式<年代pan class="katex"> ${\ mathbb F}、$ $F_{3.} ，$ 最多只有一个<年代pan class="katex"> $6.$ $6 ．$

图论的应用

让<年代pan class="katex"> $G$ $G$ 是一个图有偶数个顶点<年代pan class="katex"> $2 n。$ $2 n ．$ 一个完美的匹配在<年代pan class="katex"> $G$ $G$ 是一种<年代pan class="katex"> $n$ $n$ 的每一个顶点<年代pan class="katex"> $G$ $G$ 是其中一条边的端点。

红边在这张图上是完美匹配的。

关于完美匹配的自然计算问题如下:

给定一个图<年代pan class="katex"> $克,$ $G ，$ 我们能有多高效
(1)确定是否有完美匹配上<年代pan class="katex"> $G ?$ $G ?$
(2)找到一个完美的匹配，如果一个存在?

本节将描述一个使用Schwartz-Zippel引理解决问题(1)的概率算法。决定完美匹配是否存在的多项式原来是下面定义的某个矩阵的行列式。

让<年代pan class="katex"> $G$ $G$ 是一个有顶点的图<年代pan class="katex"> $V_1, v_2， \ldots, v_{2n}。$ $v_{1} ， v_{2} ， .．. ， v_{2 n} ．$ 让<年代pan class="katex"> $一个$ $一个$ 是<年代pan class="katex"> $2 n \ n乘以2$ $2 n \times 2 n$ 矩阵的多项式项定义如下<年代pan class="katex"> $ij$ $我 j$ 条目<年代pan class="katex-display"> $A_{ij} = \begin{cases} x_{ij} &\text{if} v_i \text{和}v_j \text{共享一条边}i < j \\ \ -x_{ji} &\text{if} v_i \text{和}v_j \text{共享一条边}i > j \\ 0&\text{else}。\{病例}结束$ 然后<年代pan class="katex"> $一个$ $一个$ 被称为<年代trong>Tutte矩阵的<年代pan class="katex"> $G。$ $G ．$

注意Tutte矩阵的行列式在变量中是一个多项式<年代pan class="katex"> $间{ij}。$ $x_{我 j} ．$

让<年代pan class="katex"> $G$ $G$ 是一个正方形，带有标记的顶点<年代pan class="katex"> $v_1, v_2 v_3,两者$ $v_{1} ， v_{2} ， v_{3.} ， v_{4}$ 绕着广场走。然后是Tutte矩阵<年代pan class="katex"> $G$ $G$ 是<年代pan class="katex-display"> $\ 0间开始{pmatrix} {12} &0&x_ {14} \ \ -x_ {12} &0&x_{23}四维\ \ 0 &-x_ {23} &0&x_ {34} \ \ -x_ {14} &0&-x_{34}四维\ {pmatrix}结束。$

(图特，1947)有一个完美的匹配<年代pan class="katex"> $G$ $G$ 当且仅当Tutte矩阵的行列式不是零多项式。

这里是证明的大纲。细节留给感兴趣的读者。

首先，如果有一个完美的匹配<年代pan class="katex"> $克,$ $G ，$ 代入<年代pan class="katex"> $间{ij} = 1$ $x_{我 j} ＝ 1$ 如果<年代pan class="katex"> $v_i$ $v_{我}$ 而且<年代pan class="katex"> $v_j$ $v_{j}$ 是匹配的,<年代pan class="katex"> $间{ij} = 0$ $x_{我 j} ＝ 0$ 否则。不难看出行列式的取值为<年代pan class="katex"> $下午\ 1$ $\pm 1$ 对于这些变量的值，所以它不可能是零多项式。另一方面，如果行列式非零，则证明完美匹配存在的方法是:将行列式写成元素乘积的带符号和，并对消去的项进行配对，直到剩下的项对应于顶点的组，它们的起始点和结束点长度相等。任何这样的路径都允许完美匹配。<年代pan class="katex"> $_ \广场$ $_{□}$

上面这个正方形的Tutte矩阵的行列式是<年代pan class="katex-display"> $间{12}^ 2间{34}^ 2 +间{14}^ 2间{23}^ 2 + 2间{12}间{23}间{34}间{14}\ 0。$

这个多项式可以通过Schwartz-Zippel检验概率非零<年代pan class="katex"> ${\ mathbb F} _p$ $F_{p}$ $（$ 我们可以检验，如果它在有理数上非零，它在任何有限域上也非零，因为它包含一个带系数的单项<年代pan class="katex"> $1）.$ $1 ）．$ 这就解决了问题(1)。

对于问题(2)，可以将(1)中的步骤转化为一种低效算法:从一条边开始，检查去掉那条边后的图是否具有完美匹配(使用Tutte矩阵);如果不是，那么这条边就是任何匹配的一部分，所以把它写下来，然后删除这两个顶点和所有相关的边，然后继续;如果是，那么删除这条边并继续前进。

如果这个图有很多条边那么这个过程显然会非常慢。这个想法有一个有效并行的版本，但细节超出了本wiki的范围。

引理的证明

如前所述，证明是用归纳法<年代pan class="katex"> $n,$ $n ，$ 在基本情况下<年代pan class="katex"> $n = 1$ $n ＝ 1$ 已经建立。

现在假设结果为真<年代pan class="katex"> $n - 1$ $n - 1$ 变量。写<年代pan class="katex"> $f$ $f$ 作为第一个变量的多项式:<年代pan class="katex-display"> $f (x_1 \ ldots x_n) = x_1 ^ k c_k (x_2 \ ldots, x_n) + x_1 ^ {k - 1} c_ {k - 1} (x_2 \ ldots, x_n) + \ cdots + c_0 (x_2 \ ldots, x_n),$ 与<年代pan class="katex"> $c_k (x_2 \ ldots x_n)$ $c_{k} （ x_{2} ， .．. ， x_{n} ）$ 不是零多项式。

根据归纳假设，概率<年代pan class="katex"> $c_k (r_2 \ ldots r_n) = 0$ $c_{k} （ r_{2} ， .．. ， r_{n} ）＝ 0$ 对于一个随机均匀独立选择的集合<年代pan class="katex"> $r_i \ S$ $r_{我} \in 年代$ 是<年代pan class="katex"> $le \ \压裂{d-k}{| |}。$ $\leq \frac{d - k}{∣ 年代 ∣} ．$ 如果它不为零，多项式<年代pan class="katex"> $f (x_1 r_2, r_3 \ ldots r_n)$ $f （ x_{1} ， r_{2} ， r_{3.} ， .．. ， r_{n} ）$ 将是非零的，因为的系数<年代pan class="katex"> $x_1 ^ k$ $x_{1}^{k}$ 是零。根据基本情况，代入的概率<年代pan class="katex"> $r_1$ $r_{1}$ 将会给<年代pan class="katex"> $0$ $0$ 对于随机的均匀选择<年代pan class="katex"> $r_1 \ S$ $r_{1} \in 年代$ 是<年代pan class="katex"> $le \ \压裂{k}{| |}。$ $\leq \frac{k}{∣ 年代 ∣} ．$

总而言之,如果<年代pan class="katex"> $f (r_1, r_2 \ ldots r_n) = 0,$ $f （ r_{1} ， r_{2} ， .．. ， r_{n} ）＝ 0 ，$ 然后要么<年代pan class="katex"> $c_k (r_2 \ ldots r_n) = 0,$ $c_{k} （ r_{2} ， .．. ， r_{n} ）＝ 0 ，$ 或者非零次-<年代pan class="katex"> $k$ $k$ 变量多项式<年代pan class="katex"> $f (x_1 r_2, r_3 \ ldots r_n)$ $f （ x_{1} ， r_{2} ， r_{3.} ， .．. ， r_{n} ）$ 计算结果为<年代pan class="katex"> $0$ $0$ 在<年代pan class="katex"> $r_1。$ $r_{1} ．$ 第一种情况的概率是<年代pan class="katex"> $le \ \压裂{d-k} {S | |}$ $\leq \frac{d - k}{∣ 年代 ∣}$ 第二种情况的概率是<年代pan class="katex"> $\le \frac{k}{|S|} \cdot p，$ $\leq \frac{k}{∣ 年代 ∣} \cdot p ，$ 在哪里<年代pan class="katex"> $p$ $p$ 是概率<年代pan class="katex"> $c_k (r_2 \ ldots r_n)$ $c_{k} （ r_{2} ， .．. ， r_{n} ）$ 是零。所以这个概率<年代pan class="katex"> $f (r_1, r_2 \ ldots r_n) = 0$ $f （ r_{1} ， r_{2} ， .．. ， r_{n} ）＝ 0$ 是<年代pan class="katex-display"> $le \ \压裂{d-k} {S | |} + \压裂{k} {S | |} \ cdot p \ le \压裂{d-k} {S | |} + \压裂{k} {S | |} = \压裂{d} {| |},$ 根据需要。<年代pan class="katex"> $_ \广场$ $_{□}$

有关……

内容