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:

- Chevalley-Warning theorem, Warning’s second theorem and their generalizations.
- Olson’s theorem on the Davenport constant of p-groups.
- Schwartz-Zippel lemma (or rather DeMillo-Lipton-Schwartz-Zippel lemmas).
- Minimum Hamming distance of Reed-Muller type affine variety codes.
- 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.

### Like this:

Like Loading...

*Related*

##
About Anurag Bishnoi

A mathematician working at TU Delft.
I am broadly interested in combinatorics and finite geometry.

Reblogged this on Gentzen translated and commented:

This paper is a great achievement. Not just that it formulates and proves a very appropriate common generalization of Alon-Furedi, Schwartz-Zippel and other theorems, it is well organized, easy to read, and very inspiring.

Thanks a lot for your positive feedback and praise. It is much appreciated.

Pingback: Alon-Furedi, Schwartz-Zippel, DeMillo-Lipton and their common generalization | Anurag's Math Blog

Pingback: The footprint bound | Anurag's Math Blog

Pingback: A coding theoretic application of the Alon-Füredi theorem | Anurag's Math Blog