Sharp Effective Finite-Field Nullstellensatz

The (weak) Nullstellensatz over finite fields says that if P-1,..., P-m are n-variate degree- d polynomials with no common zero over a finite field F then there are polynomials R-1,..., R-m such that R1P1 + center dot center dot center dot + RmPm = 1. Green and Tao [14, Proposition 9.1] used a regularity lemma to obtain an effective proof, showing that the degrees of the polynomials Ri can be bounded independently of n, though with an Ackermann-type dependence on the other parameters m, d, and |F|. In this paper we use the polynomial method to give a proof with a degree bound of md(|F| - 1). We also show that the dependence on each of the parameters is the best possible up to an absolute constant. We further include a generalization, offered by Pete L. Clark, from finite fields to arbitrary subsets in arbitrary fields, provided the polynomials Pi take finitely many values on said subset.