Difficulty: Intermediate | Prerequisites: Polynomials, degree, roots of polynomials, basic probability, Schwartz-Zippel intuition.
Polynomial identity testing is a fundamental problem: given a polynomial in some implicit form (products, powers, sums), determine whether it simplifies to zero. Expanding it out can be very slow, but evaluating at a random point is fast and gives the right answer with high probability. This "evaluate and check" strategy is a cornerstone of randomised algorithm design, with applications from verifying polynomial multiplication to graph algorithms (e.g. checking whether a graph has a perfect matching via determinants).
To test whether a polynomial is identically zero, evaluate it at a random integer from a large enough set. If it evaluates to zero, accept (guess it is the zero polynomial). If nonzero, reject. A degree-d polynomial has at most d roots, so choosing from a set of size at least 2d ensures the false-accept probability is at most 1/2.
Zero polynomial
The polynomial that equals 0 for every input. In simple terms, all its coefficients are zero.
Degree of a polynomial
The largest exponent with a nonzero coefficient. For instance, 2x³ + 8x⁷ + x⁶ has degree 7. The zero polynomial's degree is undefined.
Root of a polynomial
A value r such that p(r) = 0. A nonzero degree-d polynomial has at most d roots over any field (or over the integers).
Schwartz-Zippel lemma (informal)
If p(x) is a nonzero polynomial of degree d, and you evaluate it at a uniformly random element from a set S, then Pr[p(r) = 0] ≤ d / |S|. Think of it as: the bigger your sample space relative to the degree, the less likely you are to accidentally hit a root.
The algorithm template:
Choose an integer r ∈ {1, 2, ..., 2d} uniformly at random.
If p(r) = 0 then accept (output "zero polynomial").
Else reject (output "nonzero").
Why 2d? A nonzero degree-d polynomial has at most d integer roots. If we sample from {1, ..., 2d}, the probability of landing on a root is at most d/(2d) = 1/2. So:
If p(x) is the zero polynomial, p(r) = 0 for every r, so the algorithm always accepts. ✓
If p(x) is nonzero, it has at most d roots in {1, ..., 2d}, so Pr[p(r) = 0] ≤ d/(2d) = 1/2. Therefore Pr[reject] ≥ 1/2. ✓
Any set of size at least 2d works. The number 2d is the simplest choice that gives the 1/2 bound.
Method 1: Independent repetition.
Run ZeroTest independently k times. Reject if any trial rejects, accept only if all trials accept.
Zero polynomial: every trial accepts (probability 1). ✓
Nonzero polynomial: each trial fails to reject with probability at most 1/2. All k trials failing to reject has probability at most (1/2)^k. For (1/2)^k ≤ 0.01, we need k ≥ 7 (since (1/2)^7 = 1/128 < 0.01).
Method 2: Larger sample space.
Instead of sampling from {1, ..., 2d}, sample from {1, ..., 200d}.
Zero polynomial: still always accepts. ✓
Nonzero polynomial: Pr[p(r) = 0] ≤ d/(200d) = 1/200 = 0.5%, so Pr[reject] ≥ 99.5% > 99%. ✓
This uses a single evaluation but requires a larger random range.
Interpret Alice's n-bit string as a degree-(n-1) polynomial: if x = b_{n-1}b_{n-2}...b_0, define p_A(t) = Σ b_i · t^i.
Alice picks a random prime p of size O(n) and a random evaluation point r ∈ {0, ..., p-1}. She sends p, r, and p_A(r) mod p to Bob (all O(log n) bits each).
Bob computes p_B(r) mod p and compares. If the strings are the same, the values match. If different, p_A(t) - p_B(t) is a nonzero polynomial of degree at most n-1, which has at most n-1 roots mod p. For p ≥ 2n, the false-accept probability is at most (n-1)/p ≤ 1/2.
⚠️ Know exactly how to fill in the three blanks of ZeroTest: sample range = 2d, accept if p(r) = 0, reject otherwise.
⚠️ Students often confuse the two boosting methods. Repetition reduces failure exponentially in the number of trials. Enlarging the sample space reduces it in proportion to the new set size. Both are valid; know both.
⚠️ A common mistake is choosing the sample range as {1, ..., d} instead of {1, ..., 2d}. With only d values, the probability of hitting a root could be as high as 1 (every value could be a root).
⚠️ Remember that the zero polynomial has no degree, so a degree-d polynomial given as input is guaranteed nonzero.
Quick Self-Test
True or False: A degree-5 polynomial can have at most 5 integer roots. (True)
Fill in the blank: If we sample r from {1, ..., 100d}, the rejection probability for a nonzero degree-d polynomial is at least ______. (99/100 = 99%)
True or False: ZeroTest can produce a false negative (reject the zero polynomial). (False: p(r) = 0 for all r when p is the zero polynomial.)
Practice Q&A
Q: Complete the ZeroTest algorithm for a polynomial of degree at most d.
A: Sample r uniformly from {1, ..., 2d}. If p(r) = 0, accept. Else reject. The zero polynomial always gives p(r) = 0, so it always accepts. A nonzero polynomial has at most d roots in {1, ..., 2d}, so it evaluates to zero with probability at most d/(2d) = 1/2, meaning rejection probability is at least 1/2.
Q: Give two ways to boost the rejection probability to 99%.
A: (1) Run 7 independent trials, rejecting if any trial rejects. Failure probability ≤ (1/2)^7 < 1%. (2) Sample from {1, ..., 200d} in a single trial. Pr[p(r) = 0] ≤ d/(200d) = 0.5%, so rejection probability ≥ 99.5%.
Q: Why does the polynomial fingerprinting scheme send only O(log n) bits?
A: Alice sends a prime p = O(n), a point r ∈ {0, ..., p-1}, and p_A(r) mod p. Each is an integer of size O(n), which takes O(log n) bits to represent.
Zero testing is the univariate case of the Schwartz-Zippel lemma, which generalises to multivariate polynomials and underpins randomised algorithms for perfect matching (via the Tutte matrix). The polynomial fingerprinting method in part (c) connects back to the integer fingerprinting protocol from earlier in the homework, with the polynomial interpretation giving a cleaner analysis.
Zero testing, polynomial identity testing, PIT, Schwartz-Zippel lemma, evaluate at random point, degree, roots, false positive, one-sided error, boosting, repetition, amplification, polynomial fingerprinting, EECS 376, randomised algorithms