Schwartz–Zippel lemma

In mathematics, the Schwartz–Zippel lemma (also called the DeMillo-Lipton-Schwartz–Zippel lemma) is a tool commonly used in probabilistic polynomial identity testing, i.e. in the problem of determining whether a given multivariate polynomial is the0-polynomial (or identically equal to 0). It was discovered independently by Jack Schwartz, Richard Zippel, and Richard DeMillo and Richard J. Lipton, although DeMillo and Lipton's version was shown a year prior to Schwartz and Zippel's result. The finite field version of this bound was proved by Øystein Ore in 1922. In mathematics, the Schwartz–Zippel lemma (also called the DeMillo-Lipton-Schwartz–Zippel lemma) is a tool commonly used in probabilistic polynomial identity testing, i.e. in the problem of determining whether a given multivariate polynomial is the0-polynomial (or identically equal to 0). It was discovered independently by Jack Schwartz, Richard Zippel, and Richard DeMillo and Richard J. Lipton, although DeMillo and Lipton's version was shown a year prior to Schwartz and Zippel's result. The finite field version of this bound was proved by Øystein Ore in 1922. The input to the problem is an n-variable polynomial over a field F. It can occur in the following forms: