Category Archives: Polynomial Method

Introduction to polynomial method

(The following is a blog-friendly version of Chapter 7 of my PhD thesis, which is an introduction to the so-called polynomial method.) The polynomial method is an umbrella term for different techniques involving polynomials which have been used to solve … Continue reading

Posted in Combinatorics, Incidence Geometry, Polynomial Method | Tagged , , , , | Leave a comment

The coefficient formula and Chevalley-Warning

We discuss the new simultaneous generalization of Chevalley-Warning and Morlaye’s result on polynomial equations over finite fields obtained by Pete Clark. Continue reading

Posted in Number Theory, Polynomial Method | Tagged , , , , , , | 2 Comments

Applications of Alon-Furedi to finite geometry

In a previous post I discussed how the Alon-Furedi theorem serves as a common generalisation of the results of Schwartz, DeMillo, Lipton and Zippel. Here I will show some nice applications of this theorem to finite geometry (reference: Section 6 of my … Continue reading

Posted in Combinatorics, Finite Geometry, Polynomial Method | Tagged , , | Leave a comment

The Ellenberg-Gijswijt bound on cap sets

Four days back Jordan Ellenberg posted the following on his blog: Briefly:  it seems to me that the idea of the Croot-Lev-Pach paper I posted about yesterday can indeed be used to give a new bound on the size of subsets … Continue reading

Posted in Combinatorics, Finite Geometry, Polynomial Method | Tagged , , , , , | 6 Comments

The Erdős-Ginzburg-Ziv theorem

Let be  a sequence of integers (not necessarily distinct). Then there exists a subsequence of the sum of whose elements is divisible by .  This is one of the first problems I saw when learning the pigeonhole principle. And it’s … Continue reading

Posted in Combinatorics, Polynomial Method | Tagged , , , | 8 Comments

Alon-Furedi, Schwartz-Zippel, DeMillo-Lipton and their common generalization

In the post Balls in Bins I wrote about a combinatorial function which denotes the minimum value of the product among all distributions of balls (so ) in bins with the constraints . It turns out that this combinatorial function is linked … Continue reading

Posted in Combinatorics, Polynomial Method | Tagged , , , | 2 Comments

A timeline of the polynomial method up-to combinatorial nullstellensatz

Over the past 30-40 years, the so-called polynomial method has developed into a powerful tool in combinatorics and (additive) number theory. There has been a lot of recent interest in it after Dvir’s  paper on the Kakeya conjecture, where he … Continue reading

Posted in Combinatorics, Finite Geometry, Polynomial Method | Tagged , , , | 1 Comment