Motivation
Two algebraic expressions may describe the same polynomial even when their written forms look very different. Expanding a large expression can be expensive. Random evaluation offers a different test: evaluate the difference at a randomly chosen point. A nonzero value proves the polynomials differ, while a zero value may be a coincidence.
The Schwartz–Zippel bound limits that coincidence probability for a nonzero polynomial of bounded total degree. The test has one-sided error: it never declares a nonzero evaluation to be zero, assuming exact field arithmetic, but it can fail to detect a nonzero polynomial at a chosen root.
Definitions
Definition 6.3.1
(Total degree and the random evaluation point)
Let be a field and let be a polynomial. Its total degree is the maximum sum of exponents in any nonzero monomial; the zero polynomial is treated separately. Let be a finite nonempty set. Choose independently and uniformly from .
Definition 6.3.2
(One-sided identity test)
An identity test for an expression representing evaluates it at the chosen point. If the result is nonzero, report that is not identically zero. If it is zero, report that this trial did not find a witness. Repeating trials may reduce the chance of missing a nonzero polynomial; it does not turn a zero evaluation into a proof of identity.
Theorems
Theorem 6.3.3
(Schwartz–Zippel bound)
If is nonzero and has total degree at most , then
The bound remains valid when the right-hand side exceeds one, although it is then uninformative. For , a nonzero constant never evaluates to zero.
Theorem 6.3.4
(Bipartite matching via a determinant)
For a bipartite graph with vertices on each side, form an matrix whose entry is a distinct indeterminate for each edge and zero otherwise. Its determinant polynomial is nonzero exactly when the graph has a perfect matching.
Proof: induction on the number of variables
Proof
(Induction on the number of variables)
A nonzero univariate polynomial of degree at most has at most roots in a field. This proves the one-variable case. A nonzero constant has no roots, including when .
For the induction step, write a nonzero polynomial as a polynomial in its last variable:
The leading coefficient has total degree at most . By induction, the probability that evaluates to zero on the first choices is at most . If it does not vanish, the resulting univariate polynomial in has degree exactly and at most roots in . Conditional on the first choices, the independent last choice hits one of those roots with probability at most .
The probability of a zero value is at most the probability that the leading coefficient vanishes plus the probability of a root when it does not. This is at most . The argument also handles : then the polynomial does not depend on the last variable and the second term is zero.
Proof X-ray
How the induction closes
Three ingredients are used, each exactly once. The field hypothesis enters only through the root bound for the last variable. Independence of the last coordinate from the earlier ones lets the proof fix first and then apply that bound. The non-obvious move is to split on whether the leading coefficient vanishes at the chosen point. If it does, the degree in may drop and the root bound is unavailable, so that whole event is charged to the induction hypothesis at cost at most .
The degree accounting closes the argument. Because is part of , the polynomial has total degree at most . The two charges and add to whatever is, and a union bound combines the two events, so no independence between them is needed. If the coordinates were dependent, or not uniform on , the conditional step would fail.
Proof: determinant and matching
Proof
(Determinant and perfect matching)
Expand the determinant formally as a sum over permutations of the right-side indices:
Use the standard boundary conventions that the determinant is one and the empty graph has the empty perfect matching. A term is nonzero exactly when every selected matrix entry is an edge. Such a permutation selects one incident edge at each left vertex and each right vertex, which is a perfect matching. If the graph has no perfect matching, all terms are zero.
If a perfect matching exists, its product uses a distinct variable for each selected edge. Two different permutations select different edge sets and hence different monomials, because the edge variables are distinct. Its coefficient is or , which is nonzero in every field, including characteristic two where the signs agree. Therefore the matching term cannot cancel with a different matching term, and the determinant polynomial is nonzero. Its total degree is when .
Choose a finite field with a sampling set larger than . Independently assign each edge variable a uniform value from , then compute the determinant exactly. A nonzero determinant proves a perfect matching exists. If one exists, the probability of a zero determinant is at most . If none exists, every evaluation is zero, so the test never falsely reports a matching.
Worked examples
Worked example 6.3.5
(A univariate root coincidence)
Over the rational field, take and . The nonzero polynomial evaluates to zero at one of four choices. The bound gives , exactly the failure probability.
Worked example 6.3.6
(A nonzero polynomial with a bad point)
For and , the polynomial is nonzero, but it evaluates to zero at and . The actual probability is , while the degree-one bound is . A zero evaluation does not prove identity.
Worked example 6.3.7
(Two perfect matchings)
For the complete bipartite graph with two vertices on each side,
The two different monomials represent the two perfect matchings. Their values may cancel at a particular numerical substitution even though the formal polynomial is nonzero.
Worked example 6.3.8
(No perfect matching)
If both left vertices are adjacent only to the first right vertex, the second column of the matrix is zero. Its determinant is identically zero, matching the absence of a perfect matching. Every numerical evaluation also has determinant zero.
Repetition and implementation
Use independent random evaluation points. If any determinant is nonzero, report a perfect matching exists; otherwise report that the trials did not find a witness. When a perfect matching exists, the chance of missing it in all trials is at most , provided . When no perfect matching exists, every determinant is zero and there is no false positive.
Gaussian elimination computes a determinant over a field using polynomially many field operations. If a pivot is zero, the implementation must search for a nonzero pivot or correctly recognize singularity; division is only by nonzero field elements. An explicit finite-field representation and exact uniform sampling method determine the bit complexity. Merely saying “choose a large field” does not by itself specify those costs.
The test decides existence with one-sided error; a nonzero numerical determinant is an algebraic certificate that the formal determinant is nonzero. It does not by itself output the matching. A separate self-reduction can use existence tests on subgraphs to construct a matching, with its own error accounting.
Common mistakes
Counterexample mode
A zero evaluation can be a root
The polynomial is not identically zero, but at it evaluates to zero. Reporting “identical” after one zero evaluation can be wrong. A nonzero evaluation, in contrast, is a definite witness that the formal polynomial is nonzero.
Common mistake
(Reusing one variable for every edge)
The determinant proof uses a different variable for each edge. If all edges are assigned the same formal variable before expanding the determinant, different matching terms can cancel. For the complete two-by-two graph, replacing every entry by gives determinant despite two perfect matchings.
Common mistake
(Bounding the degree of the wrong object)
A total-degree bound must be established for the actual polynomial being tested. The degree of a written expression can be an upper bound even if cancellations lower the polynomial's true degree. A larger valid upper bound remains safe but may give a weaker probability guarantee.
Why the field assumption matters
The univariate root bound is a field fact. Over a ring with zero divisors, a nonzero degree- polynomial can have more than roots, so the induction cannot be transferred without additional conditions. Exact arithmetic is also part of the one-sided guarantee: numerical rounding can turn a small nonzero value into an apparent zero or vice versa.
The sample coordinates are independent. The proof conditions on the first coordinates and then uses a uniform independent final coordinate. Correlating all coordinates can concentrate probability on a root set: for example, choosing always makes vanish. A sampling scheme with dependencies needs its own analysis.
Concept lensCombinatorial
Counting zeros on the grid
The bound is a statement about counting points of the grid : a nonzero polynomial of total degree at most has at most zeros there. It is sharp. For and distinct , the polynomial vanishes on exactly hyperplane slices of the grid, which is points. The example on has two zeros out of four.
Constructing a matching by self-reduction
The existence test can be used to build a matching, provided we account for every randomized query. Start with the full graph. Pick a remaining left vertex and consider its incident edges. For a candidate edge , delete and and test the smaller graph's determinant using fresh independent evaluations. If any evaluation is nonzero, retain and continue with that smaller graph. If all candidate tests return zero, report failure. At the empty graph, output the retained edges.
A nonzero evaluation has no false positive, so a retained edge is always extendable to a perfect matching of the current graph. If the current graph has a perfect matching, at least one incident edge of the chosen left vertex belongs to one. Its reduced graph also has a perfect matching, but the randomized tests might miss it. With a field sampling set larger than the original size , each trial on a reduced graph has failure probability at most ; use this common upper bound even as the graph shrinks.
Test each candidate with independent evaluations. For a matching-bearing candidate the probability of all zero evaluations is at most . The adaptive procedure examines at most the original number of edge candidates. Fresh randomness makes the same conditional bound valid after any earlier history, so a union bound gives failure probability at most . If the initial graph has no perfect matching, no candidate test can produce a false nonzero determinant, and the procedure reports failure rather than outputting an invalid matching. The returned edges can also be checked directly for distinct endpoints and membership in the graph.
This construction uses at most determinant evaluations and polynomial additional graph work. It illustrates how one-sided error and fresh random choices simplify adaptive error accounting. It is a separate algorithm from the single existence test, with a separate bound and an explicit failure outcome.
The root bound behind the induction
For a nonzero univariate polynomial over a field, if is a root then polynomial division gives . Any different root has , so . Repeating this argument shows that a degree- polynomial has at most distinct roots. A nonzero constant has none.
The distinction between a polynomial and the function it induces on a finite field matters. For example, over a field with elements, is a nonzero formal polynomial that evaluates to zero at every field element. Its degree is , so the theorem gives the uninformative bound when sampling from the entire field. There is no contradiction: obtaining a useful bound requires a sample set larger than the relevant degree.
Summary
A nonzero total-degree- polynomial vanishes at a uniform independent point from with probability at most . Distinct edge variables make the bipartite matching determinant nonzero exactly for a perfect matching, giving a one-sided randomized existence test.
Exercises
Quick check
(For degree at most three and , what upper bound does the theorem give on a nonzero polynomial's zero probability?)
Apply with .
Solution · Answer
At most . The actual probability can be smaller.
Quick check
(Why do two distinct perfect matchings produce different determinant monomials?)
Compare the edge variables used by the two permutations.
Solution · Answer
They use different edge sets, and each edge has its own variable. Their products therefore differ in at least one variable factor.
Quick check
(If one trial misses a nonzero polynomial with probability at most , bound the probability that three independent trials all miss it.)
The trials are independent, so multiply the three miss probabilities.
Solution · Answer
Independence gives at most .
Quick check
(Why does a nonzero determinant evaluation prove that the formal determinant polynomial is nonzero?)
Recall the value the zero polynomial takes at every point.
Solution · Answer
The zero polynomial evaluates to zero at every point. A nonzero value contradicts the hypothesis that the formal polynomial is zero.