### Abstract

This short entry formalizes a version of the Schwartz-Zippel lemma for probabilistic (multivariate) polynomial identity testing. The entry includes a textbook example using the lemma to test for perfect matchings in a bipartite graph. The lemma is attributed to several independent authors, including Schwartz, Zippel, and DeMillo and Lipton; a historical perspective is given by Lipton.

### License

BSD License

### Topics

- Computer science/Algorithms/Randomized
- Mathematics/Algebra

### Session Schwartz_Zippel

- Schwartz_Zippel
- Rand_Perfect_Matching

### Depends on

- Factorization of Polynomials with Algebraic Coefficients
- Matrices, Jordan Normal Forms, and Spectral Radius Theory
- Skip Lists

## Cite

×

Schwartz_Zippel-AFP

    @article{Schwartz_Zippel-AFP,
      author  = {Sunpill Kim and Yong Kiam Tan},
      title   = {The Schwartz-Zippel Lemma},
      journal = {Archive of Formal Proofs},
      month   = {April},
      year    = {2023},
      note    = {\url{https://isa-afp.org/entries/Schwartz_Zippel.html},
                 Formal proof development},
      ISSN    = {2150-914x},
    }

Download

## Download

× Download latest

Older releases:

- Sep 13, 2023 : Isabelle2023
- May 3, 2023 : Isabelle2022