How to recognise that the polynomial method might work - MathOverflow

How to recognise that the polynomial method might work

2010-10-23T17:12:12Z

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 by Gjergji Zaimi for How to recognise that the polynomial method might work

2010-10-23T22:42:58Z

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 by Fedor Petrov for How to recognise that the polynomial method might work

2010-10-24T10:23:56Z

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.

Answer by Seva for How to recognise that the polynomial method might work

2010-10-25T15:44:57Z

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 by Terry Tao for How to recognise that the polynomial method might work

2010-10-25T17:29:22Z

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 by domotorp for How to recognise that the polynomial method might work

2010-10-26T06:17:10Z

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.