28
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Could you say something about your motivation? Looking for generalizations in different directions? Maybe geometric insight? $\endgroup$ – Per Vognsen Sep 29 '10 at 6:32
  • $\begingroup$ I don't really have any particular motivation. I will be very surprised that those are the only two possible ways to prove this important lemma! $\endgroup$ – Dai Le Sep 29 '10 at 6:55
  • $\begingroup$ While I agree that this lemma is important, important lemmas do not necessarily have many different known proofs. Therefore, your reason sounds a little bit strange to me. $\endgroup$ – Tsuyoshi Ito Sep 30 '10 at 0:34
  • 1
    $\begingroup$ @Tsuyushi Ito: I agree with your comment that important lemmas might not have many known proofs. But I think it's meaningful to ask if that's also the case for S-Z Lemma. Since S-Z is fundamental, it's likely that it was discovered independently by many people from different contexts. Thus, to learn different proofs is sometimes quite enlightening IMHO. Thanks again for great comments from everyone! $\endgroup$ – Dai Le Sep 30 '10 at 1:59
16
$\begingroup$

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}|$.

$\endgroup$
  • $\begingroup$ Beautiful! And just to emphasize a crucial point, the line isn't contained in the hypersurface because it goes through the point c, which is outside the surface. $\endgroup$ – arnab Oct 3 '10 at 4:44
  • 1
    $\begingroup$ @arnab: Indeed, you already made that point nicely in your own post. $\endgroup$ – Per Vognsen Oct 3 '10 at 4:52
  • 1
    $\begingroup$ @arnab: BTW, I hope it's clear that I'm not claiming this idea is truly "new". All these proofs have a similar smell. That's probably to be expected. $\endgroup$ – Per Vognsen Oct 3 '10 at 4:58
  • 2
    $\begingroup$ @Per: Yes, but for some reason, I like your version of the argument better than Moshkovitz's because it seems somehow more geometric and you don't have to think about leading monomials. But I agree, the basic idea is very much the same. $\endgroup$ – arnab Oct 3 '10 at 5:07
  • $\begingroup$ @Per: your contributions have already been wonderful. Yes, they're not truly new, but I like your interpretation a lot. It's like giving new interpretations to a classical piece of music. :-) $\endgroup$ – Dai Le Oct 3 '10 at 5:07
18
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Very nice! Did you know she does the exact same thing, only with a projective point at infinity rather than an affine point? I added a paragraph to my original answer to explain the relationship more. $\endgroup$ – Per Vognsen Sep 30 '10 at 2:51
  • 1
    $\begingroup$ Ah, that's a great interpretation! Thanks! $\endgroup$ – arnab Sep 30 '10 at 3:12
14
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, I did. But this proof is essentially the same as the one from wikipedia. $\endgroup$ – Dai Le Sep 29 '10 at 6:27
4
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Can you take a look at lemma 2.2 in web.stanford.edu/~rrwill/graph-cr.pdf? This is what Ryan Williams means by his comment under my answer, and it's on my ToDo list ever since to check whether it can be generalized to commutative rings. It seems to me you are currently much deeper into this than me, so why don't you give it a try? $\endgroup$ – Thomas Klimpel Sep 4 '15 at 11:08
  • $\begingroup$ @ThomasKlimpel: I'll modify the answer. I wrote it when I just started using CS theory stackexchange. And yes, Lemma 2.2 works over arbitrary commutative rings since {0,1}^n always satisfies Condition (D). $\endgroup$ – Anurag Sep 4 '15 at 13:09
  • $\begingroup$ A subset $S$ of an arbitrary commutative ring $R$ is said to satisfy Condition (D) if for all $x \neq y \in S$, $x - y$ is not a zero divisor. A "grid" $A_1 \times \dots \times A_n \subseteq R^n$ is said to satisfy this condition if all $A_i$'s satisfy them. Schwartz-Zippel, and other related results, work under these generalization as shown in the paper. $\endgroup$ – Anurag Sep 4 '15 at 13:23
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Polynomials are the free algebra for commutative rings, i.e. the free algebra generated by addition, additive inverses, multiplication and constants relative to the axioms of commutative rings. The initial hope was to find a generalization of the Schwartz-Zippel lemma for the free algebra which additionally contains (generalized) multiplicative inverses relative to the axioms of commutative regular rings. See also work by Jan A. Bergstra. $\endgroup$ – Thomas Klimpel Mar 10 '15 at 9:21
  • 1
    $\begingroup$ Another version of this observation with fewer assumptions and a weaker error bound appears and is applied in a restricted form (just stated for $Z_m$) in a paper with Virginia, Josh Wang, and Huacheng Yu in SODA'15: "Finding four node subgraphs in triangle time"... $\endgroup$ – Ryan Williams Apr 18 '15 at 17:00
  • 1
    $\begingroup$ @RyanWilliams The paper On Zeros of a Polynomial in a Finite Grid cited in the recent answer by Anurag Bishnoi generalizes both the above lemma, the Alon-Furedi theorem and the lemma 2.2 from that SODA'15 paper (and prove sharpness of the bound). It was on my ToDo list ever since your comment to find such a generalization, so it is a significant achievement from my point of view (so one might congratulate the authors). $\endgroup$ – Thomas Klimpel Sep 16 '15 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.