动机
两个代数表达式即使写法看上去相差很大,也可能表示同一个多项式。展开一个很大的表达式代价可能很高。随机取值提供了另一种检验方法:在随机选取的点处计算二者之差的值。若值非零,则证明两个多项式不同;若值为零,则可能只是巧合。
Schwartz–Zippel 界限制了总次数有界的非零多项式出现这种巧合的概率。该检验具有单边错误:在域运算精确的前提下,它绝不会把非零的取值判为零,但可能恰好取在某个根处,从而未能检测出非零多项式。
定义
定义 6.3.1
(总次数与随机取值点)
设 为域, 为多项式。它的总次数是所有非零单项式中指数之和的最大值;零多项式另行处理。设 为有限非空集合。从 中独立且均匀地选取 。
定义 6.3.2
(单边恒等检验)
对表示 的某个表达式,恒等检验就是在所选的点处计算它的值。若结果非零,则报告 不恒为零;若结果为零,则报告本次试验没有找到见证。重复试验可以降低漏掉非零多项式的概率,但并不能把一次零取值变成恒等的证明。
定理
定理 6.3.3
(Schwartz–Zippel 界)
若 非零且总次数至多为 ,则
当右端大于 时该界仍然成立,只是此时不提供任何信息。当 时,非零常数的取值永远不为零。
定理 6.3.4
(通过行列式判定二部图匹配)
对于两侧各有 个顶点的二部图,构造一个 矩阵:对每条边 ,其对应位置的元素取为互不相同的未定元 ,其余位置取零。该矩阵的行列式多项式非零,当且仅当此图有完美匹配。
证明:对变量个数归纳
证明
(对变量个数归纳)
域上次数至多为 的非零一元多项式至多有 个根。这就证明了一元情形。非零常数没有根,包括 的情形。
对于归纳步骤,把非零多项式写成关于最后一个变量的多项式:
首项系数 的总次数至多为 。由归纳假设, 在前 个取值处为零的概率至多为 。若它不为零,则得到的关于 的一元多项式的次数恰为 ,在 中至多有 个根。在前面各次选取已确定的条件下,独立选取的最后一个值落在这些根之一的概率至多为 。
取值为零的概率至多等于首项系数为零的概率,加上首项系数不为零时取到根的概率。这至多是 。该论证同样适用于 的情形:此时多项式不依赖于最后一个变量,第二项为零。
证明透视
归纳如何收束
证明用到三个要素,各用一次。域的假设只通过最后一个变量的根的个数界起作用。最后一个坐标独立于前面的坐标,所以证明可以先固定 ,再套用该根界。不显然的一步,是按首项系数 在所选的点上是否为零来分类。若为零, 的次数可能下降,根界便不能使用,于是整个事件就归给归纳假设处理,代价至多为 。
次数的核算使论证收束。由于 是 的一部分, 的总次数至多为 。无论 取何值,两项代价 与 的和都是 ;两个事件以并集界合并,所以不需要它们之间的独立性。若各坐标互相依赖,或在 上并非均匀,条件步骤就会失效。
证明:行列式与匹配
证明
(行列式与完美匹配)
把行列式形式地展开为对右侧指标的置换 求和:
采用标准边界约定: 行列式为一,空图的空匹配是完美匹配。某一项非零,当且仅当所选取的每个矩阵元素都对应一条边。这样的置换在每个左侧顶点和每个右侧顶点处各选出一条关联边,即得到一个完美匹配。若图没有完美匹配,则所有项均为零。
若存在完美匹配,则它对应的乘积对所选的每条边使用一个互不相同的变量。两个不同的置换选出不同的边集,而各条边的变量互不相同,因此它们对应不同的单项式。该项的系数为 或 ,在任何域中都非零,包括特征为二、两种符号相同的情形。因此该匹配项不会与另一个不同匹配的项相消,行列式多项式非零。当 时,其总次数为 。
选取一个有限域,其抽样集合 的大小大于 。独立地为每个边变量从 中均匀地赋值,然后精确地计算行列式。若行列式非零,则证明存在完美匹配。若存在完美匹配,则行列式为零的概率至多为 。若不存在完美匹配,则每次取值的结果都为零,因此该检验绝不会错误地报告存在匹配。
例题详解
例题 6.3.5
(一元情形的根的巧合)
在有理数域上,取 ,。这个非零多项式在四种选择中的一种取值为零。该界给出 ,恰好等于失败概率。
例题 6.3.6
(带有坏点的非零多项式)
对于 与 ,该多项式非零,但它在 与 处取值为零。实际概率为 ,一次的界也是 。一次零取值并不能证明恒等。
例题 6.3.7
(两个完美匹配)
对于两侧各有两个顶点的完全二部图,
这两个不同的单项式分别对应两个完美匹配。尽管形式多项式非零,在某个具体的数值代入下,它们的值仍可能相互抵消。
例题 6.3.8
(没有完美匹配)
若两个左侧顶点都只与第一个右侧顶点相邻,则 矩阵的第二列为零。其行列式恒为零,这与不存在完美匹配相符。每一次数值取值得到的行列式也都为零。
重复与实现
使用 个独立的随机取值点。若其中任何一个行列式非零,则报告存在完美匹配;否则报告各次试验没有找到见证。当存在完美匹配时,所有试验都漏掉它的概率至多为 ,前提是 。当不存在完美匹配时,每个行列式都为零,不会出现假阳性。
高斯(Gauss)消元法可以用多项式个域运算在域上计算行列式。若某个主元为零,实现中必须寻找非零主元,或者正确地识别出矩阵奇异;除法只能除以非零的域元素。明确的有限域表示方式和精确的均匀抽样方法决定了比特复杂度。仅仅说“选一个足够大的域”,本身并没有确定这些代价。
该检验以单边错误判定匹配是否存在;数值行列式非零是形式行列式非零的代数证书。但它本身并不输出匹配。可以另用自归约,通过对子图的存在性检验来构造匹配,并单独核算其错误概率。
常见错误
反例模式
一次零取值可能只是落在根上
多项式 并不恒为零,但在 时取值为零。仅凭一次零取值就报告“恒等”可能是错误的。相反,一次非零取值则是形式多项式非零的确凿见证。
常见错误
(对每条边重用同一个变量)
行列式的证明对每条边使用不同的变量。如果在展开行列式之前把所有边都赋予同一个形式变量,不同匹配的项就可能相消。对于完全的二乘二二部图,把每个元素都换成 ,得到行列式 ,尽管图中有两个完美匹配。
常见错误
(对错误的对象估计次数)
总次数的界必须针对实际被检验的多项式来建立。书面表达式的次数可以作为一个上界,即使相消使多项式的真实次数变低。更大的有效上界依然安全,只是给出的概率保证可能较弱。
为什么域的假设很重要
一元多项式的根的个数界是域的性质。在含零因子的环上,次数为 的非零多项式可能有多于 个根,所以如果没有额外条件,归纳法无法照搬。精确运算也是单边保证的一部分:数值舍入可能把一个很小的非零值变成表观上的零,或者反过来。
抽样的各个坐标是相互独立的。证明先对前 个坐标取条件,再使用独立且均匀的最后一个坐标。若让所有坐标相关联,概率可能集中在根集上:例如,取 时 总是为零。带有依赖关系的抽样方案需要单独分析。
概念视角组合
数网格上的零点
这个上界可以看成对网格 上的点计数:总次数至多为 的非零多项式,在网格上至多有 个零点。这个界是精确的:当 ,取 中互不相同的 ,多项式 恰好在网格的 个超平面切片上为零,即 个点。例子 在 上,四个点中有两个零点。
通过自归约构造匹配
存在性检验可以用来构造匹配,前提是要核算每一次随机查询。从完整的图开始。选取一个剩余的左侧顶点,考察与它关联的各条边。对于候选边 ,删去 和 ,用全新的独立取值检验较小图的行列式。若有任何一次取值非零,就保留 ,并继续处理这个较小的图。若所有候选边的检验结果都为零,则报告失败。到达空图时,输出所保留的边。
非零取值不会产生假阳性,所以被保留的边总是可以扩充为当前图的完美匹配。若当前图有完美匹配,则所选左侧顶点的关联边中至少有一条属于某个完美匹配。它对应的缩小图也有完美匹配,但随机检验可能漏掉它。当域的抽样集合大于原图规模 时,在缩小图上的每次试验的失败概率至多为 ;即使图在缩小,也使用这个共同的上界。
对每条候选边做 次独立取值。对于含有匹配的候选边,所有取值均为零的概率至多为 。这个自适应过程至多检查原图的 条候选边。新的随机性使得同样的条件界在任何先前历史之后都成立,所以由并集界得出失败概率至多为 。若初始图没有完美匹配,则任何候选检验都不会产生假的非零行列式,该过程会报告失败,而不会输出无效的匹配。所返回的边也可以直接检查端点是否互不相同,以及是否属于该图。
这个构造至多使用 次行列式计算,以及多项式量级的额外图运算。它说明了单边错误与全新随机选择如何简化自适应的误差核算。它是不同于单次存在性检验的另一个算法,有单独的界和明确的失败结果。
归纳所依据的根的个数界
对于域上的非零一元多项式 ,若 是根,则由多项式除法得 。任何不同的根 都满足 ,因此 。重复这一论证可知,次数为 的多项式至多有 个不同的根。非零常数没有根。
多项式与它在有限域上诱导的函数之间的区别很重要。例如,在有 个元素的域上, 是非零的形式多项式,却在每个域元素处取值为零。它的次数为 ,所以在从整个域中抽样时,定理给出的是没有信息的界 。这并不矛盾:要得到有用的界,需要抽样集合大于相应的次数。
总结
总次数为 的非零多项式,在 中独立均匀选取的点处为零的概率至多为 。使用互不相同的边变量时,二部图匹配的行列式非零当且仅当存在完美匹配,由此得到一个单边错误的随机存在性检验。
练习
快速检查
(对于次数至多为三、 的情形,定理对非零多项式取值为零的概率给出怎样的上界?)
套用 ,取 。
解答 · 答案
至多为 。实际概率可能更小。
快速检查
(为什么两个不同的完美匹配会产生不同的行列式单项式?)
比较两个置换所用到的边变量。
解答 · 答案
它们使用不同的边集,而每条边都有各自的变量。因此它们的乘积至少在一个变量因子上不同。
快速检查
(若一次试验漏掉某个非零多项式的概率至多为 ,试给出三次独立试验全部漏掉它的概率的上界。)
各次试验独立,把三次漏掉的概率相乘。
解答 · 答案
由独立性,至多为 。
快速检查
(为什么行列式的一次非零取值就能证明形式行列式多项式非零?)
回想零多项式在每个点处的取值。
解答 · 答案
零多项式在每个点处的取值都为零。非零取值与“形式多项式为零”这一假设矛盾。