Schwartz-Zippel Lemma

1. 引言

对于多项式$f(x_1,x_2,…,x_n)$f(x1​,x2​,…,xn​)，其系数在$F$F field域内，如何判断$f$f是否为零多项式？
第一反应是将$f(x_1,x_2,…,x_n)$f(x1​,x2​,…,xn​)完全展开，只要其中任一系数不为0，则其为非零多项式。当对多项式展开的复杂度较高时，则可任意取一组值$r_1,r_2,…,r_n$r1​,r2​,…,rn​，若$f(r_1,r_2,…,r_n)!=0$f(r1​,r2​,…,rn​)!=0，则$f$f为非零对象是。反之则不成立。
Schwartz-Zippel lemma可用于判断$f=0$f=0的概率上限的方法，具体内容为：

举例如下：

参考资料：
[1] https://brilliant.org/wiki/schwartz-zippel-lemma/