Alternative proofs of Schwartz–Zippel lemma

Question

I'm only aware of two proofs of Schwartz–Zippel lemma. The first (more common) proof is described in the wikipedia entry. The second proof was discovered by Dana Moshkovitz.

Are there any other proofs which use substantially different ideas?

Answer 1

Here's another idea I had for a geometric proof. It uses projective geometry in an essential way.

Let $c \in \mathbb F^m$ be an affine point outside the hypersurface $S$. Project the hypersurface onto the hyperplane at infinity using $c$ as center; that is, map every $x \in S$ onto $p(x)$, the intersection of the unique line through $c$ and $x$ with the hyperplane at infinity. The preimages under $p$ of a point at infinity all lie on the same line, and therefore (again reducing the problem to dimension 1) there are most $d$ of them. The hyperplane at infinity has cardinality $|\mathbb F^{m-1}|$, so we get the familiar upper bound $|S| \leq d\ |\mathbb F^{m-1}|$.

Answer 2

As a followup to Per Vognsen's answer, Dana Moshkovitz's proof already suggests a really easy proof for only a slightly weaker version of the Schwartz-Zippel Lemma that, I think, suffices for most applications.

Let $f : \mathbb{F}^n \to \mathbb{F}$ be a nonzero polynomial of degree $d$, where $\mathbb{F}$ is a finite field of order $q$, and let $x \in \mathbb{F}^n$ be a point such that $f(x) \neq 0$. There are $(q^n-1)/(q-1)$ many distinct lines passing through $x$ such that they partition $\mathbb{F}^n-\{x\}$. The restriction of $f$ to each of these lines is a degree $d$ univariate polynomial, which is nonzero, because it is nonzero at $x$, and so, has at most $d$ zeros. Thus, the total number of zeros of $f$ is at most $d(q^n-1)/(q-1)$. Schwartz-Zippel, for comparison, gives the stronger upper bound of $d q^{n-1}$.

Given this proof's easiness, I'm sure it's folklore; if not, it should be :) I'd appreciate if someone could provide a reference.

Answer 3

Moshkovitz's proof is based on simple geometry but the paper is not too clear on that. Here's the idea:

A degree $d$ polynomial in $m$ variables cuts out a hypersurface in $\mathbb F^m$. The intersection of the hypersurface and an independent line (i.e. the intersection isn't the whole line) has at most d points. If you can find a direction that is everywhere independent of the hypersurface, you can foliate $\mathbb F^m$ by parallel lines in that direction and count intersections within each line. The foliation is parameterized by the direction's orthogonal complement, which is a hyperplane isomorphic to $\mathbb F^{m-1}$, so the total number of hypersurface points across all of $\mathbb F^m$ is at most $d\ |F|^{m-1}$.

This suggests that other proofs along similar lines could work.

Edit: I wanted to say a little about how Arnab's proof relates to Moshkovitz's. He takes a point outside the hypersurface and considers the pencil of lines through that point. Moshkovitz considers a family of parallel lines. It seems different but it's really the same thing! A parallel family is a pencil of lines through a point at infinity. Arnab's algebra applies verbatim if you first take the homogenization of the polynomial and restrict to the hyperplane at infinity by plugging in $w = 0$, which wipes out all non-leading terms.

Edit: See my other answer for a new (but not completely unrelated) proof.

Answer 4

Attempt 1:

Have you looked at Lemma A.36 (page 529) of Arora/Barak's book? It's almost half a page, and is based on induction.

If you don't have access to the book, I can carry out the proof here.

---

Attempt 2:

What about The Curious History of the Schwartz-Zippel Lemma? Among the others, it cites DeMillo-Lipton's paper, dating back to 1977. Several other papers are named and compared as well.

---

Attempt 3:

The following MathOverflow topic might be of interest as well: P/poly algorithm for polynomial identity testing.

Answer 5

Schwartz-Zippel lemma is a special case of a theorem of Noga Alon and Zoltan Füredi as shown in Section 4 of this paper: On Zeros of a Polynomial in a Finite Grid, and hence any new proof of that theorem gives a new proof of Schwartz-Zippel. As of now, I know six different proofs, two of which appear in the paper and others are referenced there.

The Alon-Furedi theorem says the following:

Let $F$ be a field, let $A = \prod_{i=1}^n A_i \subset F^n$ be a finite grid, and let $f \in F[\underline{t}] = F[t_1,\ldots,t_n]$ be a polynomial which does not vanish identically on $A$. Then $f(x) \neq 0$ for at least $\min \prod y_i$ elements $x \in A$, where the minimum is taken over all positive integers $y_i \leq \# A_i$ with $\sum_{i=1}^n y_i = \sum_{i=1}^n \# A_i - \deg f$.

In this if you assume $\deg f < \min \#A_i$ and work out the minimum (which can be done easily using the Balls in Bins stuff mentioned in the paper), then you get Schwartz-Zippel lemma over a field (or a domain).

Answer 6

The original formulation of the Schwartz–Zippel lemma only applies to fields:

Lemma (Schwartz, Zippel).
Let $P\in F[x_1,x_2,\ldots,x_n]$ be a non-zero polynomial of total degree $d \geq 0$ over a field, $F$. Let $S$ be a finite subset of $F$ and let $r_1, r_2, \dots, r_n$ be selected at random independently and uniformly from $S$.
Then $\Pr[P(r_1,r_2,\ldots,r_n)=0]\leq\frac{d}{|S|}.$

One can reformulate the lemma such that it makes sense for arbitrary commutative rings:

Lemma (Jeřábek).
Let $P\in R[x_1,x_2,\ldots,x_n]$ be a non-zero polynomial of total degree $d \geq 0$ over a commutative ring, $R$. Let $S$ be a finite subset of $R$ with $\forall s, t\in S:((\exists u\in R:(u\neq 0\land su=tu))\Rightarrow s=t)$ and let $r_1, r_2, \dots, r_n$ be selected at random independently and uniformly from $S$.
Then $\Pr[P(r_1,r_2,\ldots,r_n)=0]\leq\frac{d}{|S|}.$

The advantage of the proof from wikipedia is that it generalizes to show that the reformulation holds true for arbitrary commutative rings, which has been noticed and worked out by Emil Jeřábek here.

This gives an alternative proof of the Schwartz-Zippel lemma, by proving the reformulation for general commutative rings, and obtaining the normal formulation for fields as a corollary.