A Feasibly Constructive Proof of the Schwartz-Zippel Lemma

Verifying the validity of polynomial identities presented as algebraic equations is one of the most fundamental (meta-)tasks of mathematics. Yet, the exact computational complexity of the associated computational problem, called Polynomial Identity Testing (PIT), remains unsettled. While it is known that the problem can be solved in probabilistic polynomial time, finding an algorithm that would solve it in deterministic subexponential time would be a major breakthrough in complexity theory. The correctness of the probabilistic algorithm relies on the Schwartz-Zippel Lemma, which can be interpreted to state that if an algebraic circuit with n variables and syntactic degree d has at least one non-root on an n-dimensional subcube of side q > d of the underlying field, then a fraction of at least 1 - d/q of the points on that cube are non-roots. The standard proof is an easy induction on the number of variables of the circuit, but the argument is computationally infeasible in that the inductive hypothesis is applied to the expansion of the algebraic circuit into an exponentially large sum of monomials. We give a new proof of this form of the Schwartz-Zippel Lemma that involves only polynomial time concepts and is hence formalizable in low levels of the bounded arithmetic hierarchy. Concretely, our new proof formalizes in the bounded arithmetic theory S12, i.e., Buss’s theory for polynomial-time reasoning. One further consequence of our new proof is that the theory S12 + dWPHP(PV) that has the dual weak pigeonhole principle for polynomial-time functions as an additional axiom scheme proves that PIT for algebraic formulas is solvable by polynomial-size Boolean circuits.

This solves one of the problems that was raised (by the speaker) at the open problems session of the program.

Joint work with Iddo Tzameret, Imperial College, London