Theoretical Computer Science

Alternative proofs of Schwartz–Zippel lemma


I'm only aware of two proofs of SchwartzZippel 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?




Solution

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 (5)

  • +0 – 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. — Oct 03, 2010 at 04:44  
  • +1 – @arnab: Indeed, you already made that point nicely in your own post. — Oct 03, 2010 at 04:52  
  • +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. — Oct 03, 2010 at 04:58  
  • +2 – @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. — Oct 03, 2010 at 05:07  
  • +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. :-) — Oct 03, 2010 at 05:07