Schwartz-Zippel引理
动机
引理的动机是以下问题:
给定一个多项式<年代pan class="katex"> 系数是a场 是<年代pan class="katex"> 零多项式?
这取决于<年代pan class="katex"> 定义后,有时显式地为变量代入值比完全展开多项式并检查至少有一个系数非零要容易得多。例如,如果<年代pan class="katex"> 是大量项的乘积的和(例如行列式),展开乘积和求系数的复杂程度是指数级的<年代pan class="katex">
如果在某一组值处求值得到一个非零的答案,则该多项式就不是零多项式;但是如果在一个随机选择的值集上求值<年代pan class="katex"> 这个多项式可能是零,也可能不是。Schwartz-Zippel引理给出了后一种情况下多项式为零的概率的上界,这使得它对于概率检验足够的应用非常有用。
引理的表述
让<年代pan class="katex"> 是一个场.让<年代pan class="katex"> 是总次的多项式<年代pan class="katex"> ,假设<年代pan class="katex"> 不是零多项式。让<年代pan class="katex"> 的有限子集<年代pan class="katex"> 让<年代pan class="katex"> 随机地、一致地、独立地从<年代pan class="katex"> 那么概率是<年代pan class="katex"> 是<年代pan class="katex">
备注:
(1)如果<年代pan class="katex"> 然后根据一个多项式的次数得出这个结果<年代pan class="katex"> 在一个领域最多<年代pan class="katex"> 田野里的根。<年代pan class="katex"> 这是根据辗转相除法为<年代pan class="katex"> 并存在唯一性分解成不可约项<年代pan class="katex"> 请注意,这个事实不是真的,如果<年代pan class="katex"> 被替换为整数mod<年代pan class="katex"> 当且仅当引理的不等式成立<年代pan class="katex"> 有<年代pan class="katex"> 根和<年代pan class="katex"> 包含所有这些。引理的证明,在最后一节,是一个归纳<年代pan class="katex"> 所以这个论证<年代pan class="katex"> 建立基本情况。
(2)重复选择元素的过程<年代pan class="katex"> 说,<年代pan class="katex"> 乘以<年代pan class="katex"> 计算结果为<年代pan class="katex"> 每次都是<年代pan class="katex"> 如果<年代pan class="katex"> 而且<年代pan class="katex"> 足够大,这个概率就会变得小到消失。这就是问题的关键:如果这个过程重复了足够多的次数,比如说,一个非零多项式每次求值为零的概率就会小于<年代pan class="katex"> 给定的多项式每次都等于0,那么我们就很有信心这个多项式等于0。这不是一个确定的算法——当然有可能<年代pan class="katex"> 并不等于零,而且这个过程碰巧做出了百万分之一的选择,但它又快又实用。
(3)引理还有其他类似的版本。例如,如果每个<年代pan class="katex"> 是从子集中选择的<年代pan class="katex"> 的<年代pan class="katex"> 以及<年代pan class="katex"> 作为一个多项式<年代pan class="katex"> 是<年代pan class="katex"> 引理的另一种形式是<年代pan class="katex"> 最多是<年代pan class="katex">
(4)如果<年代pan class="katex"> 是一个有限域,有一个额外的皱纹,一些多项式不是零多项式,但计算为<年代pan class="katex"> 无处不在。例如,费马小定理意味着<年代pan class="katex"> 有这样的多项式吗<年代pan class="katex"> 对于这样的多项式,Schwartz-Zippel不能期望给出任何有意义的信息,这实际上是因为度<年代pan class="katex"> 是<年代pan class="katex"> 对于任何子集<年代pan class="katex"> 的<年代pan class="katex"> 也就是说,Schwartz-Zippel仅在多项式的次d小于场的大小时有用<年代pan class="katex">
让<年代pan class="katex"> 整数mod<年代pan class="katex"> 让<年代pan class="katex"> 让<年代pan class="katex"> schwarz - zippel说<年代pan class="katex"> 是0<年代pan class="katex"> 是<年代pan class="katex"> 在9个有序的对中<年代pan class="katex"> 考虑一下,其中有5个是0:<年代pan class="katex"> 的确,<年代pan class="katex"> Schwartz-Zippel给出了非零多项式零点个数的非平凡上界;对于2次多项式<年代pan class="katex"> 最多只有<年代pan class="katex">
图论的应用
让<年代pan class="katex"> 是一个图假设顶点数为偶数<年代pan class="katex"> 一个完美的匹配在<年代pan class="katex"> 是一种选择<年代pan class="katex"> 的每一个顶点<年代pan class="katex"> 是其中一条边的端点。
关于完全匹配的自然计算问题如下:
给定一张图<年代pan class="katex"> 我们能有多高效
(1)确定是否有完美的匹配上<年代pan class="katex">
(2)找到一个完美的匹配是否存在?
本节将描述使用Schwartz-Zippel引理解决问题(1)的概率算法。决定完美匹配存在的多项式原来是下面定义的某个矩阵的行列式。
让<年代pan class="katex"> 是一个有顶点的图<年代pan class="katex"> 让<年代pan class="katex"> 是<年代pan class="katex"> 矩阵与多项式项定义如下<年代pan class="katex"> 条目<年代pan class="katex-display"> 然后<年代pan class="katex"> 叫做<年代trong>Tutte矩阵的<年代pan class="katex">
注意Tutte矩阵的行列式是变量中的多项式<年代pan class="katex">
让<年代pan class="katex"> 是一个带有顶点标记的正方形<年代pan class="katex"> 绕着广场走。的Tutte矩阵<年代pan class="katex"> 是<年代pan class="katex-display">
(Tutte, 1947)有一个完美的匹配<年代pan class="katex"> 当且仅当Tutte矩阵的行列式不是零多项式。
下面是证明的大纲。细节留给感兴趣的读者。
首先,如果有一个完美的匹配上<年代pan class="katex"> 代入<年代pan class="katex"> 如果<年代pan class="katex"> 而且<年代pan class="katex"> 匹配,并且<年代pan class="katex"> 否则。不难证明行列式等于<年代pan class="katex"> 对于这些变量的值,它不可能是零多项式。另一方面,如果行列式非零,则完全匹配存在的证明是这样进行的:将行列式写成有符号的项的乘积和,并配对掉这些消去的项,直到剩下的项对应于顶点组成的起始和结束于同一点的长度为偶数的路径组。任何这样的路径都允许一个完美的匹配。<年代pan class="katex">
上面这个正方形的Tutte矩阵的行列式是<年代pan class="katex-display">
所以这个多项式可以通过Schwartz-Zippel检验概率为非零<年代pan class="katex"> 我们可以证明,如果它在有理数上是非零,它在任何有限域上也是非零,因为它包含一个带系数的单项<年代pan class="katex"> 这就解决了问题(1)。
对于问题(2),(1)中的过程可以转换为一种低效算法:从一条边开始,检查去掉那条边的图是否具有完美匹配(使用Tutte矩阵);如果不是,那么这条边就是任何匹配的一部分,所以把它写下来,然后删除这两个顶点和所有相关的边,然后继续;如果是,那么删除这条边并继续前进。
如果这个图有很多条边这显然会很慢。这个想法有一个有效的并行版本,但细节超出了本wiki的范围。
引理的证明
如上所述,证明是用归纳法<年代pan class="katex"> 在基本情况下<年代pan class="katex"> 已经建立了。
现在假设结果为真<年代pan class="katex"> 变量。写<年代pan class="katex"> 作为第一个变量的多项式:<年代pan class="katex-display"> 与<年代pan class="katex"> 不是零多项式。
根据归纳假设,概率<年代pan class="katex"> 对于随机、一致、独立选择的一组<年代pan class="katex"> 是<年代pan class="katex"> 如果它不为零,这个多项式<年代pan class="katex"> 非零,因为的系数<年代pan class="katex"> 是零。根据基本情况,代入的概率<年代pan class="katex"> 将会给<年代pan class="katex"> 的随机均匀选择<年代pan class="katex"> 是<年代pan class="katex">
总结一下,如果<年代pan class="katex"> 然后要么<年代pan class="katex"> 或者非零度-<年代pan class="katex"> 变量多项式<年代pan class="katex"> 计算结果为<年代pan class="katex"> 在<年代pan class="katex"> 第一种情况的概率是<年代pan class="katex"> 第二种情况的概率是<年代pan class="katex"> 在哪里<年代pan class="katex"> 概率是<年代pan class="katex"> 是零。所以概率是<年代pan class="katex"> 是<年代pan class="katex-display"> 根据需要。<年代pan class="katex">