Schwartz-Zippel Theorem d ∫丰0！ >Pr[f(r1,r2,,rn)=0]≤ induction on n: basis: n=1 single-variate case,proved by the fundamental Theorem of algebra I.H.:Schwartz-Zippel Thm is true for all smaller n
Schwartz-Zippel Theorem Pr[f(r1, r2,...,rn) = 0] d |S| f 6⌘ 0 induction on n : basis: n=1 single-variate case, proved by the fundamental Theorem of algebra I.H.: Schwartz-Zippel Thm is true for all smaller n
Schwartz-Zippel Theorem d ∫丰0 >Pr[f(r1,r2,,rn)=0]≤ s induction step: k:highest power ofxn inf ∫fk丰0 degree of fr≤d-k k f(c1,x2,,xn）=xf(1,x2,…,n-l） i=0 =xhfk(x1,c2,,xn-1）+f(ac1,2,,n） k-1 where f(ar1,tr2,…,cn）=xf(c1,x2,…,n-1） i=0 highest power of xn in f<
f(x1, x2,...,xn) = X k i=0 xi nfi(x1, x2,...,xn1) k: highest power of xn in f fk 6⌘ 0 degree of fk d k n = xk nfk(x1, x2,...,xn1) + ¯f(x1, x2,...,xn) ¯f(x1, x2,...,xn) = k X1 i=0 xi n where fi(x1, x2,...,xn1) highest power of xn in ¯f <k Schwartz-Zippel Theorem Pr[f(r1, r2,...,rn) = 0] d |S| f 6⌘ 0 induction step:
Schwartz-Zippel Theorem d ∫丰0 >Pr[f(r1,r2,,rn)=0]≤ S f(ac1,x2,,xn）=axhf(a1,2,…,xn-1）+f(ac1,2,,xn) 了fk丰0 degree of f≤d-k highest power of xn in f< law of total probability: d-k Pr[f(r1,r2,.,rn)=0] I.H.>☐s SI =Pr[f(=0|fk(r1,,rn-1)=0]Pr[f(r1,.,rn-1）=0] +Pr[f(=0|fk(r1,.,rn-1)≠0]Pr[fk(r1,,rn-1)≠0] =Prg1…m-1(n)=0|fk(1,,n-1)≠0]≤ k where91,xn-1(cn）=f(c1,,xn）
highest power of xn in ¯f <k fk 6⌘ 0 degree of fk d k = xk nfk(x1, x2,...,xn1) + ¯f(x1, x2,...,xn) Schwartz-Zippel Theorem Pr[f(r1, r2,...,rn) = 0] d |S| f 6⌘ 0 f(x1, x2,...,xn) n law of total probability: Pr[f(r1, r2,...,rn) = 0] = Pr[f(~ r)=0 | fk(r1,...,rn1) = 0] · Pr[fk(r1,...,rn1) = 0] + Pr[f(~ r)=0 | fk(r1,...,rn1) 6= 0] · Pr[fk(r1,...,rn1) 6= 0] I.H. d k |S| k |S| gx1,...,xn1 where (xn) = f(x1,...,xn) = Pr[gr1,...,rn1 (rn)=0 | fk(r1,...,rn1) 6= 0]
Schwartz-Zippel Theorem d f≠0>Pr[f(r1,r2,,rn)=0≤ IS Prf1,r2,,m）=0】≤S+ d-k k d S] ISI
Schwartz-Zippel Theorem Pr[f(r1, r2,...,rn) = 0] d |S| f 6⌘ 0 Pr[f(r1, r2,...,rn) = 0] d k |S| + k |S| = d |S|
Input:fF[1,22,...,n]of degree d Output:f≡0？ fix an arbitrary S F pick random ri,r2,...,rES uniformly and independently at random; check whether f(ri,r2,...,r)=0 f三0>f(r,r2,,rn)=0 Schwartz-Zippel Theorem d f丰0>Pr[f(1,r2,,rn)=0]≤ IS
Input: of degree d Output: f 0? f 2 F[x1, x2,...,xn] pick random r1, r2, ... , rn ∈S uniformly and independently at random; check whether f(r1, r2, ... , rn) = 0 ; fix an arbitrary S ✓ F Schwartz-Zippel Theorem Pr[f(r1, r2,...,rn) = 0] d |S| f 6⌘ 0 f ⌘ 0 f(r1, r2,...,rn)=0