67
$\begingroup$

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.

$\endgroup$
16
  • 1
    $\begingroup$ 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 $\endgroup$ Oct 23, 2010 at 17:19
  • 2
    $\begingroup$ @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. $\endgroup$
    – gowers
    Oct 23, 2010 at 18:09
  • 3
    $\begingroup$ @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." $\endgroup$ Oct 23, 2010 at 19:19
  • 3
    $\begingroup$ @Dylan: Schwartz-Zippel is a QUANTITATIVE statement, as opposed to the combinatorial Nullstellensatz, which is an EXISTENCE statement. When you read the proof in Schwartz' paper, you see that it implies that there are at least (|S1|-t1)(|S2|-t2)...(|Sn|-tn) nonzeros. (The t_i's are not the same as those in CNS; the assumptions on t_i's are not directly comparable; both conditions are subsumed by Michał Lasoń, A generalization of Combinatorial Nullstellensatz, The Electronic J. of Combinatorics (2010), Article no. #N32, 6 pp., mentioned in one of the answers, by "Seva". $\endgroup$ Jan 30, 2013 at 0:52
  • 5
    $\begingroup$ @Qiaochu: The combinatorial Nullstellensatz does not imply the Schwartz-Zippel lemma. Ex. 9.1.1 in Tao and Vu's Additive Combinatorics does not ask to derive the Schwartz-Zippel from the CNS but merely to prove it by modifying the argument to the proof. (You have to turn the page ;-) see books.google.de/… $\endgroup$ Jan 30, 2013 at 1:02

6 Answers 6

32
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Seva
    Oct 26, 2010 at 7:07
  • 3
    $\begingroup$ 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. $\endgroup$
    – ACL
    Mar 15, 2011 at 16:31
  • 3
    $\begingroup$ Time for an edit regarding the capset problem :) $\endgroup$
    – Anurag
    May 18, 2016 at 1:44
  • 9
    $\begingroup$ I think I'll leave the 2010 version as a record of what people like myself thought at the time. (For context: in May 2016, there was a breakthrough on the capset problem at quomodocumque.wordpress.com/2016/05/13/bounds-for-cap-sets .) $\endgroup$
    – Terry Tao
    May 18, 2016 at 2:44
20
$\begingroup$

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.

$\endgroup$
6
  • 7
    $\begingroup$ 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. $\endgroup$
    – gowers
    Oct 24, 2010 at 9:48
  • 2
    $\begingroup$ 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$. $\endgroup$ Oct 25, 2010 at 8:08
  • $\begingroup$ It's probably worthwhile to note that one can easily avoid CN in Example 3. Basically, you want to prove that any polynomial that vanishes on all points of a grid $S_1 \times \cdots \times S_n$ except one must have degree at least $\sum |S_i| - 1$. This can be proved by induction on $\sum |S_i| - 1$. For a particular case of this, see my solution here: artofproblemsolving.com/wiki/index.php/2007_IMO_Problems/…. (contd ...) $\endgroup$
    – Anurag
    Apr 13, 2015 at 21:45
  • $\begingroup$ (contd ...) A particular case of this, where each $S_i = \mathbb{F}_q$, and you are looking at polynomials over $\mathbb{F}_q$ was already proved in this paper by Bruen, sciencedirect.com/science/article/pii/009731659290035S, by more or less similar arguments. $\endgroup$
    – Anurag
    Apr 13, 2015 at 21:47
  • 1
    $\begingroup$ @FedorPetrov: only the prime case of Olson's theorem follows from Alon-Furedi hyperplane covering. Though that has been "fixed" recently by Clark et al. (and by Brink before that) by generalising another result of Alon-Furedi. See section 4 of arxiv.org/pdf/1404.7793v2.pdf. In fact many combinatorial results that follow from combinatorial nullstellensatz can alternately be seen as direct applications of this Alon-Furedi bound. $\endgroup$
    – Anurag
    Aug 3, 2015 at 17:51
12
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$ Oct 25, 2010 at 21:44
  • $\begingroup$ @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. $\endgroup$
    – Seva
    Oct 26, 2010 at 6:57
  • 2
    $\begingroup$ @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. $\endgroup$ Oct 26, 2010 at 8:50
  • 1
    $\begingroup$ @Seva: There is a multiplicity version of Combinatorial Nullstellensatz as well. See Theorem 3.1 in S. Ball and O. Serra, Punctured Combinatorial Nullstellensätze, Combinatorica 29 (2009), 511-522. $\endgroup$
    – Anurag
    May 10, 2015 at 22:47
10
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$
    – gowers
    Oct 24, 2010 at 16:21
  • $\begingroup$ 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. $\endgroup$ Oct 24, 2010 at 22:18
10
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ By the way, recently a clever student explained me how degree of simplicial map in this problem equals (a priori) a coefficient of polynomial. Though there are still more questions than answers. $\endgroup$ Aug 3, 2015 at 20:15
  • 1
    $\begingroup$ @Fedor: Interesting, let me know about the developments! $\endgroup$
    – domotorp
    Aug 3, 2015 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.