Revision 224fd373-74bf-48d0-9e63-1bbef32cc5c1

I would like to add some more examples and references for the so called polynomial method that can help us recognise when it can be applied. 

From what I understand so far, the polynomial method falls under these two big categories: 

**A. Construct an explicit polynomial (or a set of polynomials) that captures the given set.**

**B. Use interpolation arguments to get a polynomial whose degree (or some other property) is under control.**

An important, and well known, subcategory of **A** is the *dimension argument* using polynomial spaces. 

For example, if we want to show that there can be at most $n(n+1)/2$ equiangular lines in $\mathbb{R}^n$, then with each line we associate the polynomial $P_u = (u, x)^2 - \alpha^2(x, x)$ where $u$ is a fixed unit vector on the line and $arccos(\alpha)$ is the angle between every pair of lines. Then we show that $P_u(v) = (1 - \alpha) \delta_{u, v}$, proving that these polynomials are linearly independent. Now, all these polynomials are degree $2$ homogenous polynomials in $n$ variables, and hence the number is bounded above by the dimension of this spaces, $n(n+1)/2$. Another example that demonstrates this approach is the bound on $2$-distance sets in Euclidean spaces. For further details, and several examples I would refer to the manuscript "[Linear Algebra Methods in Combinatorics][1]" by Babai and Frankl. 

Another subcategory is when you use the coefficients or degrees of the explicit polynomial. One of the simplest examples is perhaps [the result by Blokhuis][2] on nuclei of sets in $\mathbb{F}_q^2$. A nucleus of a set $S$ of points in $\mathbb{F}_q^2$ is a point $x$, not in $S$, such that every line through $x$ intersects $S$. Blokhuis showed that if $S$ has size $q + k$, with $k \leq q$, then all nuclei of $S$ are roots of a degree $k(q-1)$ polynomial (hint: an elementary symmetric polynomial), hence proving that the total number of nuclei is at most $k(q-1)$. 

The Brouwer-Schrijver/Jamison [bound on affine blocking sets][3] also uses a property of polynomials over finite fields that, if a polynomial in $\mathbb{F}_q[t_1, \dots, t_n]$ vanishes on all points of $\mathbb{F}_q^n$ except one, then its degree must be at least $n(q-1)$. This is quite similar to the classical Chevalley-Warning theorem. And in fact, this can be proved via a [dimension argument][4] as well. 

I think Combinatorial Nullstellensatz, and all its applications that I am aware of, fall under category **A** as well. Here, we construct a polynomial that is explicit enough so that we can determine the coefficient of its leading monomial. The [answer][5] by Gjergji Zaimi covers this approach nicely. If we want estimates on the total number of non-vanishing points, instead of just existence, then we can sometimes use the result by Alon-Füredi, as it was recently done by Clark, Forrow and Schmitt in [this][6] paper. 


Category **B** seems to be somewhat more recent. It was used by Dvir in his proof of finite field Kakeya conjecture, and it has then found several applications. Terence Tao has written a nice survey on it which can be found [here][7]. Quoting Tao, 

> Broadly speaking, the strategy is to capture (or at least partition)
> the arbitrary sets of objects (viewed as points in some configuration
> space) in the zero set of a polynomial whose degree (or other measure
> of complexity) is under control; for instance, the degree may be
> bounded by some function of the number of objects. One then uses tools
> from algebraic geometry to understand the structure of this zero set,
> and thence to control the original sets of object.

Another important breakthrough using this approach was the result of Guth and Katz on [Erdős distinct distances problem][8].

Can these two approaches (**A** and **B**) be combined? I would love to see an example of that. But this is what Terence Tao had to say about combining CN and Interpolation, 

> roughly speaking, the idea is to start with a counterexample to the claimed extremal result, and then use this counterexample to design a polynomial vanishing on a large product set and which is explicit enough that one can compute a certain coefficient of the polynomial to be non-zero, thus contradicting the nullstellensatz. This should be contrasted with more recent applications of the polynomial method, in which interpolation theorems are used to produce the required polynomial. Unfortunately, the two methods cannot currently be easily combined, because the polynomials produced by interpolation methods are not explicit enough that individual coefficients can be easily computed, but it is conceivable that some useful unification of the two methods could appear in the future


**More References**

 - Aart Blokhuis, [Polynomials in finite geometries and combinatorics][9].
 - A. A. Bruen, J. C. Fisher, [The Jamison method in galois geometries][10]. 
 - Noga Alon, [Discrete mathematics: methods and challenges][11].
 - Gyula Károlyi, [The polynomial method in additive combinatorics][12].
 - Simeon Ball, [Polynomials in Finite Geometries][13] and [The Polynomial Method in Galois Geometries][14]. 
 - Terence Tao and Van Vu, Chapter 9 in [Additive Combinatorics][15].
 - Zeev Dvir, [Incidence Theorems and Their Applications][16].
 - Terence Tao, [Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory][7].
 - Peter Sziklai, [Polynomials in finite geometries][17] and [Applications of Polynomials over Finite Fields][18].

 


  [1]: https://www.google.be/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CCAQFjAA&url=http%3A%2F%2Fmatthewkahle.org%2Fdownload%2Ffile%2Ffid%2F499&ei=BUNKVcJ7w9XtBuXhgagD&usg=AFQjCNHdoK1hAfd3KNAPpS8t7Ue_PvgqxA&sig2=PEBwcTrHZRPxf4bZNAmAyA&bvm=bv.92291466,d.ZGU
  [2]: http://www.sciencedirect.com/science/article/pii/0097316594900167
  [3]: http://www.sciencedirect.com/science/article/pii/0097316578900134
  [4]: http://link.springer.com/article/10.1007%2Fs10801-009-0204-1
  [5]: http://mathoverflow.net/a/43343/34180
  [6]: http://arxiv.org/abs/1404.7793
  [7]: http://arxiv.org/abs/1310.6482
  [8]: http://en.wikipedia.org/wiki/Erd%C5%91s_distinct_distances_problem
  [9]: http://ebooks.cambridge.org/chapter.jsf?bid=CBO9780511662089&cid=CBO9780511662089A007
  [10]: http://link.springer.com/article/10.1007/BF00123760
  [11]: http://arxiv.org/abs/math/0212390
  [12]: http://link.springer.com/chapter/10.1007%2F978-3-7643-8962-8_20
  [13]: http://www-ma4.upc.es/~simeon/bcc.pdf
  [14]: http://www-ma4.upc.es/~simeon/polynomialmethod.pdf
  [15]: https://terrytao.wordpress.com/books/additive-combinatorics/
  [16]: http://www.cs.princeton.edu/~zdvir/papers/Dvir-survey.pdf
  [17]: http://www.cs.elte.hu/~sziklai/polynom/poly08feb.pdf
  [18]: http://www.cs.elte.hu/~sziklai/nagydoktori/nd.pdf