How to recognise that the polynomial method might work

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.

-
I was going to comment that syntactic similarity is one clue, then I noticed that one result says = 0 and another does not. Did you quote both results correctly? Gerhard "Ask Me About System Design" Paseman, 2010.10.23 – Gerhard Paseman Oct 23 2010 at 17:19
The combinatorial nullstensatz is remarkably similar to the Schwartz-Zippel(-DeMillo-Lipton) lemma, whose history is summarized <a href="rjlipton.wordpress.com/2009/11/30/…; (by Lipton). What's the history of Alon's theorem? – Dylan Thurston Oct 23 2010 at 17:52
@Gerhard Paseman: Yes, it's that way round, which is why Fermat's little theorem is helpful. I agree that it makes the use of the result harder to spot. @Dylan Thurston: I'm not sure, but I seem to remember he discovered it about fifteen years ago (plus or minus five perhaps) along with several nice applications. – gowers Oct 23 2010 at 18:09
@Dylan: in fact it implies Schwartz-Zippel. This is exercise 9.1.1 in Tao and Vu's Additive Combinatorics, right after they introduce the combinatorial nullstellensatz. They remark that it is "particularly useful for obtaining lower bounds on the size of restricted sum sets and similar objects." – Qiaochu Yuan Oct 23 2010 at 19:19
After looking a little further, it seems like Alon's theorem is an improvement of the Schwartz-Zippel lemma, with a more precise statement about the individual degrees. – Dylan Thurston Oct 23 2010 at 19:21

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.

-

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.

-
I wonder whether this has anything to do with the notion of complexity of sets in elementary abelian $2$-groups I thought on some five+ years ago. Specifically, I defined the complexity of a set $S\subset{\mathbb F}_2^n$ as the length of the shortest chain $\emptyset=S_0\subset\dotsb\subset S_k=S$ such that for each $i\in[k]$ we have either $S_i=S_{i-1}\cup H$, or $S_i=S_{i-1}\setminus H$, for a subgroup $H\le{\mathbb F}_2^n$. I have never had any applications to this notion though, neither could I prove anything really ingenious about it. – Seva Oct 26 2010 at 7:07
I don't know if my comment has a chance of being detected. Anyway: people in Diophantine geometry have been using the polynomial method and studying the Zariski complexity of sets for a long time. Pascal's theorem (about points on conics), its generalization by Cayley-Bacharach are also typical examples of that. The Schneider-Lang theorem of Bombieri bounds the Zariski complexity of the set of points at which some meromorphic function of finite order (in $n$ variables) together with its derivatives takes its values in a given number field. Amoroso-David's extension of Lehmer conjecture. – ACL Mar 15 2011 at 16:31

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.

-
 Remark on Lason's paper. As I know (from Noga Alon), formula for coefficient (Theorem 3 in the paper you cite), proving CN, was known before. And in any case, it may be proved much easier, then in this paper. Just note that both LHS and КРЫ are linear in $f$, so we may think that $f$ is monomial. For monomial, everything reduces to dimension 1 (it factors into product over all variables). For dimension 1 it is nothing but Lagrange interpolation. Some applications of it see here lanl.arxiv.org/abs/1005.1177 (I am very sorry for self-advertising). – Fedor Petrov Oct 25 2010 at 21:44 @Fedor: for me, the major thing to learn for Lason's paper is not the formula, but the fact that the assumptions of the CN can be slightly relaxed. – Seva Oct 26 2010 at 6:57 @Seva: OK, but this fact immediately follows from the formula (and from other proofs of CN: we use degree condition exactly for showing that any other monomial has less degree then our in at least one variable.) But I agree that it is worth to state such fact explicitly. – Fedor Petrov Oct 26 2010 at 8:50

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. ften 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 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:)

5) be careful on wether you prove what is true and more. Say, CN is often applied for graph choosability, and I do not know applications to graph colorings different from proving choosability. hence 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.

-
As an exercise, I tried doing the Cauchy-Davenport theorem without looking up how it is done. At first I couldn't see what to do at all, but eventually, after some false starts, I realized that the polynomial $\prod_{c\in A+B}(x+y-c)$ and the sets A and B would contradict the combinatorial nullstellensatz if Cauchy-Davenport was false. Somehow this application feels very different from the Olson theorem application. – gowers Oct 24 2010 at 16:21
In a sense, they are very similar. We assume a contrary and reformulate it as a system of algebraic equalities holding for free (independent) variables chosen from appropriate set. In case of Olson we know that all vectots $(\sum x_ia_i,\sum x_i b_i)$ belong to $\mathbb{F}_p^2\setminus (0,0)$ for $x_i\in \{0,1\}$. In case of Cauchy-Davenport we know that $x+y\in C$ for some $C$ of cardinality $|A|+|B|-2$ and $(x,y)\in A\times B$. Then we find one polynomial which respects all these conditions. It is a product of linear forms. Then we apply CN. – Fedor Petrov Oct 24 2010 at 22:18

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.

-
I have to disagree with your self-assessment there: I found the answer very interesting and helpful. And the fact that you've drawn attention to the Alon-Friedland-Kalai result (which I didn't know) makes it all the more so, since it suggests that understanding that example would be a good idea. – gowers Oct 24 2010 at 9:48
By the way, Olson's result is a special case of Alon-Furedi (which holds over nay field, in our case $\mathbb{F}_p$): all points of the cube $\{0,1\}^{2p−1}$ but origin can not be covered by $2p−2$ hyperplanes $\sum a_i x_i=m$, $\sum b_ix_i=m$, $m=1,2,\dots,p−1$. – Fedor Petrov Oct 25 2010 at 8:08