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.

About Anurag Bishnoi

A mathematician working at TU Delft. I am broadly interested in combinatorics and finite geometry.
This entry was posted in Combinatorics, Finite Geometry, Polynomial Method and tagged , , , . Bookmark the permalink.

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

  1. gentzen says:

    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.

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

  3. Pingback: The footprint bound | Anurag's Math Blog

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s