随机算法 \ 高级算法 (Fall 2016)/Problem Set 3

Problem 1

The Schwartz-Zippel theorem works well for large enough fields [math]\displaystyle{ \mathbb{F} }[/math], but works poorly for fields of small size, such as the binary field [math]\displaystyle{ \mathbb{Z}_2 }[/math].

Let [math]\displaystyle{ Q(x_1,x_2,\ldots,x_n) }[/math] be a multivariate polynomial over a field [math]\displaystyle{ \mathbb{Z}_2 }[/math] with the degree sequence [math]\displaystyle{ (d_1,d_2,\ldots,d_n) }[/math]. A degree sequence is defined as follows: let [math]\displaystyle{ d_1 }[/math] be the maximum exponent of [math]\displaystyle{ x_1 }[/math] in [math]\displaystyle{ Q }[/math], and [math]\displaystyle{ Q_1(x_2,\ldots,x_n) }[/math] be the coefficient of [math]\displaystyle{ x_1^{d_1} }[/math] in [math]\displaystyle{ Q }[/math]; then let [math]\displaystyle{ d_2 }[/math] be the maximum exponent of [math]\displaystyle{ x_2 }[/math] in [math]\displaystyle{ Q_1 }[/math], and [math]\displaystyle{ Q_2(x_3,\ldots,x_n) }[/math] be the coefficient of [math]\displaystyle{ x_2^{d_2} }[/math] in [math]\displaystyle{ Q_1 }[/math]; and so on.

Let [math]\displaystyle{ S_1,S_2,\ldots,S_n\subseteq\mathbb{Z}_2 }[/math] be arbitrary finite subsets. For [math]\displaystyle{ r_i\in S_i }[/math] chosen independently and uniformly at random, show that

[math]\displaystyle{ \Pr\left[Q(r_1,r_2,\ldots,r_n)=0\mid Q\not\equiv 0\right]\le\sum_{i=1}^n\frac{d_i}{|S_i|} }[/math].