On the Alon-Füredi bound

A 1993 result of Alon and Füredi gives a sharp upper bound on the number of zeros of a multivariate polynomial in a finite grid over an integral domain. We give a generalization of the Alon-Füredi Theorem and discuss the relationship between Alon-Füredi, our generalization and the results of DeMillo-Lipton, Schwartz and Zippel. A direct coding theoretic interpretation of our main result in terms of Reed-Muller type affine variety codes is shown, which gives us the minimum Hamming distance of these codes. We also apply the Alon-Füredi Theorem to quickly recover - and sometimes strengthen - some old and new results in finite geometry.