In the Schwartz–Zippel algorithm for bounded error probabilistic polynomial identity testing, the main theorem is the following:
For a non-zero multivariate polynomial $p(x_1,...,x_n)$ of total degree $d \ge 0$ over a field, $F$. Let $S$ be a finite subset of $F$ and let $r_1, r_2, ..., r_n$ be selected at random independently and uniformly from $S$. Then
The proof is short and can be read on the wiki page linked above. What I am having trouble understanding is the requirements on the sampling of values to test the polynomial. For example if
$$p(x,y,z) = xz-yz$$
then testing only values of the form $(a,a,a)$ would not be sufficient. However, for that polynomial, or indeed any ternary polynomial with degree in each individual variable no more than 1, it is okay to randomly equate two of the variables during testing (using test values of the form $(a,b,b), (b,a,b), (b,b,a)$ will allow testing if the polynomial is zero).
So my question is:
- Where does the proof implicitly rely on the requirement of the values being "selected at random independently and uniformly"?
- Is it known in what cases this can be relaxed?
For example, considering polynomials where the degree in each individual variable is no more than 1, can this restriction be used to extend the example above with duplicate variable values to polynomials with more than three variables?