Schwartz-Zippel 引理
零多项式(0-polynomial):所有系数都为 0 的多项式。
其实就是 0
多元多项式是一种多项式,其包含多个变量。如果一个多项式只有一个变量,那么它就是一元多项式。多元多项式可以表示为若干个单项式的和,其中每个单项式都是由若干个变量的幂次和系数相乘得到的。例如,下面是一个三元多项式的例子:
f(x, y, z) = 2x^2y^3z + 3xy^2z^2 + 4xyz^3
其中,2x^2y^3z、3xy^2z^2 和 4xyz^3 都是单项式,它们的系数分别为 2、3 和 4,幂次分别为 (2, 3, 1)、(1, 2, 2) 和 (1, 1, 3)。
有限域也称为伽罗瓦域(Galois field)。它是一个包含有限个元素的域,其中每个元素都可以进行加、减、乘和除运算。如果一个有限域的特征是素数 p,它所含的素域是△,而它有 q=pⁿ 个元素,那么它就是多项式在△上的分裂域。任何两个这样的域都同构。
Schwartz-Zippel 引理是一种常用于概率多项式恒等式检验的工具,即用于判断一个多元多项式是否为零多项式。假设 P 是一个多元多项式,其最高次数为 d,给定一个有限域 S 和 n 个随机数 r1, r2, …, rn,其中每个随机数都是从 S 中随机独立选取的。Schwartz-Zippel 引理指出,如果 P 不是零多项式,则 Pr(P(r1, r2, …, rn) = 0) <= d/|S|。其中 |S| 表示 S 中元素的个数。
同态(homomorphism) 对于集合 X 上的运算 Rx 和 集合 Y 上的运算 Ry,如果存在一个映射 f: X -> Y,使得对于任意 x1, x2 ∈ X,都有 f(x1 Rx x2) = f(x1) Ry f(x2),那么我们就称 f 是一个同态。这个定义可以扩展到任意个集合。
同余(Modular arithmetic) 对于整数 a, b 和正整数 n,如果 n 能整除 a-b,那么我们就称 a 和 b 在模 n 下同余,记作 a ≡ b (mod n)。例如,3 ≡ 11 (mod 4)。