How to recognise that the polynomial method might work

Question

A couple of days ago I was at a nice seminar given by Christian Reiher, during which he told us about a short proof of the following special case of a theorem of Olson.

Theorem. Let $(a_1,b_1),\dots,(a_n,b_n)$ be a sequence of points in ${\mathbb{Z}}_p^2$ with $n\geq 2p-1$. Then there is a non-empty subset $A\subset\{1,2,\dots,n\}$ such that $\sum_{i\in A}(a_i,b_i)=(0,0)$.

The short proof wasn't short in absolute terms, but was short if you were prepared to accept the following result of Noga Alon, known as the combinatorial nullstellensatz.

Theorem. Let F be a field and let P be a polynomial in n variables $x_1,\dots,x_n$ over F. Let $x_1^{t_1}\dots x_n^{t_n}$ be a monomial of maximal total degree $t_1+\dots+t_n$ that occurs in P with a non-zero coefficient, and let $S_1,\dots,S_n$ be subsets of F such that $|S_i|>t_i$ for every i. Then there exist $s_i\in S_i$ such that $P(s_1,\dots,s_n)\ne 0.$

Once you have the combinatorial nullstellensatz, the special case of Olson's theorem (and I think the whole theorem) is reduced to a nice exercise: basically, once you sit down and think about it you quickly see that it makes sense to choose each $S_i$ to be {0,1}, and then a few simple tricks using Fermat's little theorem (the polynomial $1-x^{p-1}$ is zero if $x\ne 0$ and 1 otherwise) you can finish off quite easily.

This method is known as the polynomial method. My question is not how to apply the combinatorial nullstellensatz. It's how to recognise, when you see a problem, that the polynomial method might work. In this case, once you have that clue, it's easy to finish off. But how do you manage if there's nobody there to give you the clue?

I'm interested in this question in general: I've always found spotting that mathematical results can be used quite a difficult process -- somehow I have to do it for myself in one problem before I truly understand how to do it in other problems. And here's a good example where I have never spotted how to use the result. And had I been faced with the task of proving Olson's theorem, I don't think it would have occurred to me to use it.

Answer 1

My feeling is that it may be premature to declare what types of problems look tractable with respect to the polynomial method. For instance, the idea of using the polynomial method to attack the finite field Kakeya problem, while "obvious" in retrospect, was certainly a big shock to many of us working on the Kakeya problem at the time Dvir's argument came out.

In contrast, the question of getting a non-trivial Szemeredi-Trotter or sum-product theorem in finite fields, while closely related to the Kakeya problem (see e.g. my paper with Bourgain and Katz on this topic), has so far resisted all attempts at a polynomial method proof. But this could simply be because we haven't yet found the right way to generate the right sort of polynomials for this problem. Similarly, the capset problem of determining better bounds on $r_3(F_3^n)$ than what one can get from Fourier methods is one that at first looks very amenable to a polynomial method approach, but again there has been no progress on this front. (These are great problems to look at, by the way, if someone in this area is looking for a high-risk, high-reward task to add to their research projects.)

What I would like to see more of in the future is more development of the somewhat vague idea of the "Zariski complexity" of various sets, by which I mean something like the least degree of a non-trivial polynomial which vanishes on that set. One can view the polynomial method as the strategy of comparing upper and lower bounds on the Zariski complexity of sets to obtain nontrivial combinatorial consequences. I have the vague feeling that ultimately, such notions of complexity should play as prominent a role in these sorts of combinatorial problems as existing notions of "size" for such sets, such as cardinality, dimension, or Fourier uniformity.

Answer 2

I have noticed that most problems which can be solved by the combinatorial nullstellensatz share a common theme; you start by being given a collection of objects (vectors, sets, collection of points or whatever) which appear to be symmetric or random in the sense that they don't satisfy any imposed relation between each other, except that they all come from a given field, and you are asked to show the existence (or non-existence, or prove a lower bound on the number etc.) of some of them satisfying a property which can easily be written as a polynomial condition (having the property is related to membership in the zero set of a polynomial, such as being collinear or coplanar, having sum divisible by a certain prime, or being different).

I will need to write a few examples to illustrate what I mean.

Example 1 Given $2n$ sets $A_i=\{x_i,y_i\}$ whose elements are real numbers and the indices are mod $2n$, show that you can pick $z_i\in A_i$ so that $z_i\neq z_{i+1}$ for all $i$.

This one is solvable by a direct argument too, but CN gives a quick proof once we see that what is being asked is to find $z_i$'s so that $\prod(z_i-z_{i+1})\neq 0$ (so it is a polynomial property). The problem of Snevily falls in this category as well.

Example 2 (Erdos-Ginzburg-Ziv) Given $2p-1$ integers one can find $p$ of them whose sum is divisible by $p$.

This one is similar to Olson's theorem, and one realizes that divisibility by a prime for a sum $\sum x_i$ is a "polynomial condition" in the sense that it is equivalent to $(\sum x_i)^{p-1}-1\neq 0$ in $\mathbb{F}_p[x]$. CN gives the conclusion.

Example 3 (Alon–Furedi) Consider the lattice points $(x_1,\cdots,x_k)$ where $0\le x_i \le n_i$ for each $i$ but not all $x_i$ vanish. The minimum number of hyperplanes that do not pass from the origin needed to cover all of these lattice points is $\sum n_i$.

This result was, I think, one of the theorems designed to show the strength of the combinatorial nullstellensatz because it follows readily from it, however finding a purely combinatorial proof is still an open problem.

In this one (and other statements where one proves lower bounds using CN, such as Erdos-Heilbronn) there is a collection of objects which have a polynomial property and somehow it is natural to think of the one big polynomial (the product of all linear equations defining the hyperplanes in our case) and by contradiction use CN to get a lower bound on its degree.

My impression is that it is easier to judge if the polynomial method would work for existence results than problems which ask you to prove a lower bound (unless one thinks of the lower bounds as non-existence results in which case it becomes the same matter). However I should end by acknowledging (an apologizing) that this answer is pretty useless not only because it describes a trivial observation, but also because it doesn't say anything about results that can be proven using the polynomial method, yet they are formulated very far from theorems like the ones above. One example I have in mind is the Alon–Friedland–Kalai result that a 4-regular simple graph plus one edge contains a 3-regular subgraph.

Answer 3

As I see it, the polynomial method is not limited to applications of the Combinatorial Nullstellensatz or any other specific result (as the Schwartz-Zippel lemma). Known for several decades at least, this method involves encoding combinatorial problems in fields (more generally rings, or even generic abelian groups) in terms of (non)vanishing of some polynomials, and then studying the resulting polynomial problem using various tools -- such as CN, SZ, and so on. One common theme (but certainly not exhausting the whole subject) is showing that a set with some particular combinatorial property is large: if it were small, we could construct a low-degree polynomial vanishing on this set (or its cartesian power), while such polynomial cannot exist by virtue of the combinatorial property under consideration.

As Fedor mentioned, this method usually works when we have a sharp result to prove, although there are some exceptions: say, the best up-to-date results on the finite fields Kakeya problem, obtained using the polynomial method, are unlikely to be sharp.

Anyway, absolutely vital seems to be our ability to express the problem in terms of (non)vanishing of some polynomial.

---

Two more comments. First, it has been observed very recently that in the Combinatorial Nullstellensatz, one does not need $x_1^{t_1}\dots x_n^{t_n}$ to be a monomial of the largest possible degree; it suffices that it is not majorated by any other monomial.

Second, one does not have to confine to just vanishing: a very fruitful approach, to my knowledge first suggested by Saraf and Sudan and then further developed in their joint paper with Dvir and Kopparty, is to take into account the multiplicity with which a polynomial vanishes.

Answer 4

Two obvious reasons to try polynomial method:

1) The problem may be formulated as vanishing/non-vanishing of some polynomial.

2) The problem is similar to one of already solved by polynomial method, say, to one of problems considered in fundamental Alon's article http://www.tau.ac.il/~nogaa/PDFS/null2.pdf

Some hints, based on my own impressions:

3) The problem solvable by polynomial method is rather sharp, then asymptotic in nature. So, I doubt that Freiman's theorem may be proved on this way, while Cauchy-Davenport is ok. Often slightly weaker results are obvious (for example, in Cauchy-Davenport, if we replace $|A+B|\geq |A|+|B|-1$ to $|A+B|\geq (|A|+|B|)/2$, it becomes obvious. If we replace $d$-choosability of a graph with degrees about $2d$ to $(2d+1)$-choosability, it becomes obvious.)

4) Some algebraic structure must exist in the problem. Say, planarity of a graph is not very algebraic condition:) Further update: my intuition got slightly wrong here. There is a polynomial proof by Ellingham and Goddyn that $r$-regular edge-$r$-colorable planar graph is edge-$r$-choosable. The reason with parity is quite cute.

5) be careful on wether you prove what is true or even more. Say, CN is often applied for graph choosability, and I do not know applications to graph colorings different from proving choosability. Thus, if your graph is not a priori d-choosable, it can hardly be shown with CN that it is d-colorable.

I may remember some other impressions later.

Answer 5

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" 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 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 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 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 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 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. 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.

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.
• A. A. Bruen, J. C. Fisher, The Jamison method in galois geometries.
• Noga Alon, Discrete mathematics: methods and challenges.
• Gyula Károlyi, The polynomial method in additive combinatorics.
• Simeon Ball, Polynomials in Finite Geometries and The Polynomial Method in Galois Geometries.
• Terence Tao and Van Vu, Chapter 9 in Additive Combinatorics.
• Zeev Dvir, Incidence Theorems and Their Applications.
• Terence Tao, Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory.
• Peter Sziklai, Polynomials in finite geometries and Applications of Polynomials over Finite Fields.
• Larry Guth, Polynomial Method in Combinatorics.

Answer 6

I always thought that the polynomial method might be related to parity arguments or Borsuk-Ulam type theorems. For a theorem that has a short proof with both the CN and BU, see http://arxiv.org/abs/1005.1177. Unfortunately I do not have any good intuition about when to try applying them.