<p>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. </p>

<p>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$ <em>univariate</em> 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}$.</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-30T02:51:50.683Z
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.
Per Vognsen
CC BY-SA 2.5
2010-09-30T03:12:03.690Z
Ah, that's a great interpretation!  Thanks!
arnab
CC BY-SA 2.5
2010-09-29T17:09:06.297Z
2010-09-30T02:49:00.330Z
2010-09-30T02:49:00.330Z
arnab
<p>Moshkovitz's proof is based on simple geometry but the paper is not too clear on that. Here's the idea:</p>

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

<p>This suggests that other proofs along similar lines could work.</p>

<p>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.</p>

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

CC BY-SA 2.5
2010-09-29T06:52:57.107Z
2010-10-03T04:19:13.070Z
2010-10-03T04:19:13.070Z
Per Vognsen
<h3>Attempt 1:</h3>
<p>Have you looked at Lemma A.36 (page 529) of <a href="https://rads.stackoverflow.com/amzn/click/com/0521424267" rel="noreferrer" rel="nofollow noreferrer">Arora/Barak's book</a>? It's almost half a page, and is based on induction.</p>
<p>If you don't have access to the book, I can carry out the proof here.</p>
<hr />
<h3>Attempt 2:</h3>
<p>What about <a href="http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the-schwartz-zippel-lemma/" rel="noreferrer">The Curious History of the Schwartz-Zippel Lemma</a>? Among the others, it cites <a href="http://rjlipton.files.wordpress.com/2009/11/demillolipton.pdf" rel="noreferrer">DeMillo-Lipton's paper</a>, dating back to 1977. Several other papers are named and compared as well.</p>
<hr />
<h3>Attempt 3:</h3>
<p>The following MathOverflow topic might be of interest as well: <a href="https://mathoverflow.net/questions/35301/">P/poly algorithm for polynomial identity testing</a>.</p>

CC BY-SA 2.5
2010-09-29T06:27:08.660Z
Yes, I did. But this proof is essentially the same as the one from wikipedia.
Dai Le
CC BY-SA 2.5
2010-09-29T06:23:32.823Z
2010-09-29T07:10:40.193Z
2020-06-17T09:38:08.363Z
Sadeq Dousti
<p>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: <a href="http://arxiv.org/abs/1508.06020" rel="nofollow">On Zeros of a Polynomial in a Finite Grid</a>, 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.  </p>

<p>The Alon-Furedi theorem says the following:</p>

<p>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$. </p>

<p>In this if you assume $\deg f &lt; \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). </p>

CC BY-SA 3.0
2015-09-04T11:08:18.980Z
Can you take a look at lemma 2.2 in http://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?
Thomas Klimpel
CC BY-SA 3.0
2015-09-04T13:09:14.710Z
@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).
Anurag
CC BY-SA 3.0
2015-09-04T13:23:06.767Z
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.
Anurag
CC BY-SA 3.0
2015-03-31T04:31:02.030Z
2015-09-04T13:19:34.250Z
2015-09-04T13:19:34.250Z
Anurag
<p>The original formulation of the Schwartz–Zippel lemma only applies to fields:</p>

<blockquote>
  <p><strong>Lemma</strong> (Schwartz, Zippel).<br>
  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$.<br>
  Then
  $\Pr[P(r_1,r_2,\ldots,r_n)=0]\leq\frac{d}{|S|}.$</p>
</blockquote>

<p>One can reformulate the lemma such that it makes sense for arbitrary commutative rings:</p>

<blockquote>
  <p><strong>Lemma</strong> (Jeřábek).<br>
  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$.<br>
  Then
  $\Pr[P(r_1,r_2,\ldots,r_n)=0]\leq\frac{d}{|S|}.$</p>
</blockquote>

<p>The advantage of the <a href="http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma" rel="nofollow noreferrer">proof from wikipedia</a> is that it generalizes to show that the reformulation holds true for arbitrary commutative rings, <a href="https://mathoverflow.net/a/186103">which has been noticed and worked out by Emil Jeřábek here</a>.</p>

<p>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.</p>

CC BY-SA 3.0
2015-03-10T09:21:14.640Z
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](https://gentzen.wordpress.com/2014/12/06/algebraic-characterizations-of-inverse-semigroups-and-strongly-regular-rings/). See also [work by Jan A. Bergstra](http://arxiv.org/abs/0803.3969v3).
Thomas Klimpel
CC BY-SA 3.0
2015-04-18T17:00:49.760Z
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"...
Ryan Williams
CC BY-SA 3.0
2015-09-16T08:52:55.187Z
@RyanWilliams The paper [On Zeros of a Polynomial in a Finite Grid](http://arxiv.org/abs/1508.06020) 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).
Thomas Klimpel
CC BY-SA 3.0
2015-03-10T09:01:48.197Z
2015-03-10T09:01:48.197Z
2017-04-13T12:57:54.777Z
Thomas Klimpel
<p>Here's another idea I had for a geometric proof. It uses projective geometry in an essential way.</p>

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

CC BY-SA 3.0
2015-05-08T15:47:35.707Z
@PerVognsen: I think you have made an error in your proof. The hyperplane at infinity does not have cardinality $q^{m-1}$, where $q$ is the size of the finite field. The correct size is $(q^m - 1)/(q-1) = 1 + q + \dots + q^{m-1}$. So, this only gives a weaker bound.
Anurag
CC BY-SA 3.0
2015-09-04T13:20:41.387Z
The size of the hyperplane at infinity in $\mathbb{F}_q^m$ is not $q^{m-1}$, it is $1 + q + \cdots + q^{m-1}$, and hence it doesn't give a new proof of the Schwartz-Zippel lemma. There is a crucial difference between the argument of Dana Moshkovitz and the arguments given here.
Anurag
CC BY-SA 3.0
2015-09-04T13:20:45.673Z
In Moshkovitz's proof we are also fixing a point that doesn't lie in $Z$, a point $x$ at infinity. But instead of looking at all lines through $x$ we are only looking at those that do not lie in the hyperplane at infinity, i.e., the set of parallel lines that determine this point $x$. The number of such lines is $q^{m-1}$. While the total number of lines through any fixed point in $\mathbb{F}_q^n$ is $(q^m - 1)/(q-1) = 1 + q + \cdots + q^{m-1}$.
Anurag
CC BY-SA 2.5
2010-10-03T04:44:05.107Z
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.
arnab
CC BY-SA 2.5
2010-10-03T04:52:59.773Z
@arnab: Indeed, you already made that point nicely in your own post.
Per Vognsen
CC BY-SA 2.5
2010-10-03T04:58:11.293Z
@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.
Per Vognsen
CC BY-SA 2.5
2010-10-03T05:07:26.820Z
@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.
arnab
CC BY-SA 2.5
2010-10-03T05:07:47.293Z
@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. :-)
Dai Le
CC BY-SA 2.5
2010-10-03T05:14:10.770Z
@Dai Le: The inductive proof on Wikipedia is also more or less geometric if you look at it right. When they consider $P$ as a polynomial in $x_1$, they are essentially parallel-projecting the surface onto the $x_2 x_3 \ldots x_n$ hyperplane, solving the problem recursively on the subspace, and then taking preimages under the projection.
Per Vognsen
CC BY-SA 2.5
2010-10-03T04:12:02.260Z
2010-10-03T04:12:02.260Z
Per Vognsen
<p>I'm only aware of two proofs of Schwartz–Zippel lemma. The first (more common) proof is described in the <a href="http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma">wikipedia entry</a>. The second <a href="http://www.eccc.uni-trier.de/report/2010/096/">proof</a> was discovered by Dana Moshkovitz. </p>

<p>Are there any other proofs which use substantially different ideas? </p>

CC BY-SA 2.5
2010-09-29T06:32:00.107Z
Could you say something about your motivation? Looking for generalizations in different directions? Maybe geometric insight?
Per Vognsen
CC BY-SA 2.5
2010-09-29T06:55:43.113Z
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!
Dai Le
CC BY-SA 2.5
2010-09-30T00:34:50.120Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-30T01:59:17.083Z
@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!
Dai Le
<cc.complexity-theory><reference-request><algebra><polynomials><finite-fields>
Alternative proofs of Schwartz–Zippel lemma
Dai Le
# Alternative proofs of Schwartz–Zippel lemma

(Asked by: username_0 on 2010-09-29)

I'm only aware of two proofs of Schwartz–Zippel lemma. The first (more common) proof is described in the [wikipedia entry](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma). The second [proof](http://www.eccc.uni-trier.de/report/2010/096/) was discovered by Dana Moshkovitz.

Are there any other proofs which use substantially different ideas?

**Tags:** cc.complexity-theory, reference-request, algebra, polynomials, finite-fields
> **Comments:**
> **username_1**: Could you say something about your motivation? Looking for generalizations in different directions? Maybe geometric insight?  
> **username_0**: 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!  
> **username_2**: 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.  
> **username_0**: @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!  

---

## 6 answers

### Answer by username_1 on 2010-10-03. Score: 16 | Accepted answer

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

> **Comments:**
> **username_3**: 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.  
> **username_1**: @arnab: Indeed, you already made that point nicely in your own post.  
> **username_1**: @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.  
> **username_3**: @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.  
> **username_0**: @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. :-)  
> **username_1**: @Dai Le: The inductive proof on Wikipedia is also more or less geometric if you look at it right. When they consider $P$ as a polynomial in $x_1$, they are essentially parallel-projecting the surface onto the $x_2 x_3 \ldots x_n$ hyperplane, solving the problem recursively on the subspace, and then taking preimages under the projection.  
> **username_5**: @PerVognsen: I think you have made an error in your proof. The hyperplane at infinity does not have cardinality $q^{m-1}$, where $q$ is the size of the finite field. The correct size is $(q^m - 1)/(q-1) = 1 + q + \dots + q^{m-1}$. So, this only gives a weaker bound.  
> **username_5**: The size of the hyperplane at infinity in $\mathbb{F}_q^m$ is not $q^{m-1}$, it is $1 + q + \cdots + q^{m-1}$, and hence it doesn't give a new proof of the Schwartz-Zippel lemma. There is a crucial difference between the argument of Dana Moshkovitz and the arguments given here.  
> **username_5**: In Moshkovitz's proof we are also fixing a point that doesn't lie in $Z$, a point $x$ at infinity. But instead of looking at all lines through $x$ we are only looking at those that do not lie in the hyperplane at infinity, i.e., the set of parallel lines that determine this point $x$. The number of such lines is $q^{m-1}$. While the total number of lines through any fixed point in $\mathbb{F}_q^n$ is $(q^m - 1)/(q-1) = 1 + q + \cdots + q^{m-1}$.  

---

### Answer by username_3 on 2010-09-29. Score: 18

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.

> **Comments:**
> **username_1**: 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.  
> **username_3**: Ah, that's a great interpretation!  Thanks!  

---

### Answer by username_1 on 2010-09-29. Score: 14

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 by username_4 on 2010-09-29. Score: 6

### Attempt 1:

Have you looked at Lemma A.36 (page 529) of [Arora/Barak's book](https://rads.stackoverflow.com/amzn/click/com/0521424267)? 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](http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the-schwartz-zippel-lemma/)? Among the others, it cites [DeMillo-Lipton's paper](http://rjlipton.files.wordpress.com/2009/11/demillolipton.pdf), 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](https://mathoverflow.net/questions/35301/).

> **Comments:**
> **username_0**: Yes, I did. But this proof is essentially the same as the one from wikipedia.  

---

### Answer by username_5 on 2015-03-31. Score: 4

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](http://arxiv.org/abs/1508.06020), 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).

> **Comments:**
> **username_6**: Can you take a look at lemma 2.2 in http://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?  
> **username_5**: @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).  
> **username_5**: 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.  

---

### Answer by username_6 on 2015-03-10. Score: 3

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](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma) 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](https://mathoverflow.net/a/186103).

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.

> **Comments:**
> **username_6**: 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](https://gentzen.wordpress.com/2014/12/06/algebraic-characterizations-of-inverse-semigroups-and-strongly-regular-rings/). See also [work by Jan A. Bergstra](http://arxiv.org/abs/0803.3969v3).  
> **username_7**: 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"...  
> **username_6**: @RyanWilliams The paper [On Zeros of a Polynomial in a Finite Grid](http://arxiv.org/abs/1508.06020) 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).  

---

