On Zeros of a Polynomial in a Finite Grid: the Alon-Furedi bound

My joint paper with Aditya Potukuchi, Pete L. Clark and John R. Schmitt is now up on arXiv: arXiv:1508.06020.

This work started a few months back when I emailed Pete and John, pointing out an easy generalization of Chevalley-Warning theorem using something known as the punctured combinatorial nullstellensatz, after reading their paper on Warning’s second theorem: arXiv:1404.7793. They got pretty excited about it and we started discussing some related things. Finally, it’s not the generalization of Chevalley-Warning that this paper is about but the theorem of Alon-Füredi itself, which is the main tool they used in their paper to generalize Warning’s second theorem. In our discussions we found several unexplored connections between this elementary result on polynomials and results from different areas of maths. My friend Aditya joined us in between with his amazingly simple proof of Alon-Füredi which, along with the annoying realization that a result of DeMillo-Lipton-Zippel doesn’t follow from Alon-Füredi, led us to generalize Alon-Füredi.

These results when combined with the recent work by Pete, Aden Forrow and John (and the follow up by Pete: arXiv:1506.06743) shows how powerful this Alon-Füredi bound is. Among many other things, it implies the following results:

1. Chevalley-Warning theorem, Warning’s second theorem and their generalizations.
2. Olson’s theorem on the Davenport constant of p-groups.
3. Schwartz-Zippel lemma (or rather DeMillo-Lipton-Schwartz-Zippel lemmas).
4. Minimum Hamming distance of Reed-Muller type affine variety codes.
5. Jamison/Brouwer-Schrijver bound on affine blocking sets.

I am hopeful that there are many other connections which will be discovered. Much like Alon’s Combinatorial Nullstellensatz, this is a pretty basic result on polynomials with several interesting applications. In some subsequent posts, I will try to discuss this in much more detail.