Abstract   A 1993 result of Alon and Furedi 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-Furedi Theorem and discuss the relationship between Alon-Furedi, 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-Furedi Theorem to quickly recover – and sometimes strengthen – some old and new results in finite geometry.
['Anurag Bishnoi', 'Pete L. Clark', 'Aditya Potukuchi', 'John R. Schmitt']
On the Alon-Füredi bound