Combinatorics Seminar

If a polynomial f vanishes on all points of a finite grid A_1 x...x A_n in F^n, then the degree of f is at least \sum_i (|A_i|-1). I will talk about two generalizations of this result and their applications. One of them is about f vanishing on all points except some point of a subgrid, which will lead us to a new generalization of the Chevalley-Warning theorem. And the other one is about a lower bound on the number of non-zeros of f in the grid, know as the Alon-Füredi theorem. I will give a generalization of this Alon-Füredi theorem and explain its connections with the Schwartz-Zippel lemma. We will also see that much like the Combinatorial Nullstellensatz, the Alon-Füredi theorem is a fundamental result on polynomials that has applications to various important problems in Coding Theory, Finite Geometry, Additive Combinatorics and Graph Theory.