On zeros of a polynomial in a finite grid

A 1993 result of Alon and Furedi gives a sharp upper bound on the number of zeros of a multivariate polynomial over an integral domain in a finite grid, in terms of the degree of the polynomial. This result was recently generalized to polynomials over an arbitrary commutative ring, assuming a certain Condition (D) on the grid which holds vacuously when the ring is a domain. In the first half of this paper we give a further Generalized Alon-Furedi Theorem which provides a sharp upper bound when the degrees of the polynomial in each variable are also taken into account. This yields in particular a new proof of Alon-Furedi. We then discuss the relationship between Alon-Furedi and results of DeMillo-Lipton, Schwartz and Zippel. A direct coding theoretic interpretation of Alon-Furedi Theorem and its generalization in terms of Reed--Muller type affine variety codes is shown which gives us the minimum Hamming distance of these codes. Then we apply the Alon-Furedi Theorem to quickly recover (and sometimes strengthen) old and new results in finite geometry, including the Jamison/Brouwer-Schrijver bound on affine blocking sets. We end with a discussion of multiplicity enhancements.

Warnings Second Theorem with Resricted Variables

We present a restricted variable generalization of Warnings Second Theorem (a result giving a lower bound on the number of solutions of a low degree polynomial system over a finite field, assuming one solution exists). This is analogous to Brinks restricted variable generalization of Chevalleys Theorem (a result giving conditions for a low degree polynomial system not to have exactly one solution). Just as Warnings Second Theorem implies Chevalleys Theorem, our result implies Brinks Theorem. We include several combinatorial applications, enough to show that we have a general tool for obtaining quantitative refinements of combinatorial existence theorems.