Introduction to the polynomial method (and other similar things)

The polynomial method has made some waves recently (see this and that, for instance), and last week, Boris Alexeev gave a very nice talk on various applications of this method. This post is loosely based on his talk. All errors are my own.

It’s hard to pin down what exactly the polynomial method is. It’s a technique in algebraic extremal combinatorics, where the goal is to provide bounds on the sizes of objects with certain properties. The main idea is to identify the desired cardinality with some complexity measure of an algebraic object (e.g., the dimension of a vector space, the degree of a polynomial, or the rank of a tensor), and then use algebraic techniques to estimate that complexity measure. If at some point you use polynomials, then you might say you applied the polynomial method.

What follows is a series of instances of this meta-method.

— Linear algebraic bounds —

In this section, we identify certain combinatorial structures with vectors in a vector space. After identifying that these vectors must be linearly independent, we conclude an upper bound on the cardinality of these structures (namely, the dimension of the vector space).

Problem (from the Tricki). Suppose is even. What is the maximum number of subsets of with the property that each has odd size and the intersection between any two has even size?

For each set , consider its indicator function . (We let our indicator functions take values in the field of order 2 since parity plays a leading role in this problem.) We seek indicator functions of odd support that are pairwise orthogonal. In this case, orthogonality implies linear independence (why?), and so we know that the maximum possible number is . Furthermore, we can saturate this bound by selecting all singletons, and so the bound is sharp.

Next, consider a -balanced incomplete block design, that is, a collection of size- subsets of , called blocks, with the property that every point in belongs to exactly blocks, and every pair of distinct points is contained in exactly blocks. We take to prevent degenerate cases.

Fisher’s inequality. A -balanced incomplete block design exists only if .

Consider the matrix whose th row is the indicator function of the th block. (Here, we view the entries as real numbers.) First, implies (why?). Next, the definition gives , where denotes the all-ones matrix. Since is positive definite, it has rank , which in turn implies that has rank , which is only possible if .

Notice that in this case, the linearly independent vectors are the columns of , as opposed to the blocks’ indicator functions. The block designs which achieve equality in Fisher’s inequality are called symmetric designs. The Fano plane is an example.

The following result has a similar proof:

The Gerzon bound. Take of unit norm such that whenever . Then .

Here, the matrices are linearly independent in the -dimensional real vector space of self-adjoint matrices, which can be seen from their Gram matrix. The ensembles which achieve equality in the Gerzon bound are called symmetric informationally complete positive operator–valued measures (SIC-POVMs), and they are conjectured to exist for every dimension .

— Simple polynomials have simple zero sets —

In this section, the main idea is that simple polynomials have simple zero sets. The following is the most basic instance of this idea:

Theorem. Let be a field. A nonzero polynomial of degree at most has at most roots.

This immediately produces a similar instance for polynomials of multiple variables:

Corollary. Let be a field. If has degree at most and vanishes on more than points of a line in , then it vanishes on the entire line.

To see this, parameterize the line in terms of a variable , and then plug this parameterization into to get a polynomial in of degree at most . Then by the previous theorem, this has more than roots only if , which in turn establishes that vanishes on the entire line. The following provides yet another example of simple multivariate polynomials having simple zero sets:

Theorem (Alon’s Combinatorial Nullstellensatz). Let be a field, and suppose has total degree . If the coefficient of is nonzero and satisfy for each , then there exists such that .

As an application of this result, consider the following:

Problem (Problem 6 from IMO 2007). Let be a positive integer, and consider

as a set of points in . Determine the smallest number of planes, the union of which contains but does not include .

There are a couple of obvious choices of planes, for example shifts of each coordinate plane, or shifts of the orthogonal complement of the all-ones vector. We will show that is the smallest possible number of planes by showing that planes are insufficient. In particular, having only  planes will lead to a polynomial that is too simple for the zero set to satisfy the desired constraints.

Suppose to the contrary that planes are sufficient, and let  denote the th plane. Put

Then the zero set of is the union of the planes, and so by assumption. Since we want to apply Alon’s Combinatorial Nullstellensatz, we want a polynomial whose zero set contains an entire grid, so we will modify so as to vanish over all of . To this end, we know that

is also zero on , and furthermore, . As such,

will serve as the desired modification. This polynomial has total degree , and the coefficient of is . Furthermore, taking satisfies the hypothesis of Alon’s Combinatorial Nullstellensatz, which then gives that fails to vanish on all of , a contradiction.

— Simple sets are zero sets of simple polynomials —

Given a sufficiently small set, there is a low-degree nonzero polynomial that vanishes on that set. For example:

Theorem. Let be a field, and take of size at most . Then there exists a nonzero polynomial of degree at most that vanishes on .

This can be proven explicitly or implicitly. For the explicit version, just take . For the implicit version, take the linear operator that maps to by evaluating a given polynomial at each point in . Since the subspace of polynomials in of degree at most has dimension , this mapping has a nontrivial nullspace, thereby implicating the desired nonzero polynomial . This latter proof can be used to obtain a more general lemma:

Theorem. Let be a field, and take of size strictly less than . Then there exists a nonzero polynomial of degree at most that vanishes on .

Indeed, the dimension of the subspace of of polynomials with degree at most is the number of monomials of degree at most , which equals the number of -tuples of nonnegative integers whose sum is at most . A stars and bars argument then gives that this dimension is

where the last step follows from Pascal’s identity by induction on . From this, one may conclude (for example) that any two points in lie on a line, any five points lie on a (possibly degenerate) conic section, and any three points lie on a (possibly degenerate) cubic curve.

This theorem was used to prove the following:

Theorem (Finite field Kakeya conjecture, Dvir 2008). Let be a finite field, and suppose contains a line in every direction (i.e., is a Kakeya set). Then has size at least , where depends only on (and not ).

More explicitly, we will show that has size at least

(Note that this differs slightly from Terry Tao’s exposition.) To do this, we suppose to the contrary that . Then by the previous result, there exists a nonzero polynomial of degree that vanishes on . Use this to form a homogeneous polynomial by multiplying terms of degree by . Put . Then . By assumption, we have that for every , there exists such that is in the zero set of . This then implies that is in the zero set of . Note that for every , the homogeneity of gives

That is, has degree at most and is zero at for every nonzero . Since this makes up different points on a line, the corollary of the previous section gives that is also zero when , namely, at . Since the choice of was arbitrary, this means whenever . But is the polynomial made up of the terms of maximum degree in , which cannot be identically zero (by Alon’s Combinatorial Nullstellensatz, for example, though this is overkill).

— Capset bounds —

A particularly recent application of the polynomial method made a surprising contribution to the following open problem:

The Capset Problem. How large can a subset be if it contains no lines?

Such a set is known as a capset. The obvious bounds on are and , and with a bit of extra work, these were improved to and . On his blog, Terry Tao suspected that the lower bound could be improved all the way up to , and in one of his MathOverflow answers, he suspected that the polynomial method might be leveraged to improve the known bounds. He was recently proven both wrong and right when the polynomial method was used to establish the following:

Theorem (Ellenberg–Gijswijt 2016). If contains no lines, then .

The proof uses ideas from Croot–Lev–Pach 2016. First observe the following identity:

Indeed, precisely when either forms a line in or . Since contains no lines by assumption, both sides of the above identity are zero unless , in which case both sides are 1.

The above identity equates functions of the form . View this as a 3-way tensor whose entries lie in and whose rows, columns and tubes are indexed by members of . We will estimate a certain complexity measure of 3-way tensors known as slice rank: Here, a tensor is said to be decomposable if it can be expressed as

and a tensor has slice rank if there are decomposable tensors that sum to and no fewer. As one might expect, the slice rank of a diagonal tensor is the number of nonzero diagonal entries, and so the right-hand side of the above identity has slice rank . As such, it suffices to bound the slice rank of the left-hand side.

To this end, we view the left-hand side as a subtensor of , defined over all , whose slice rank is an upper bound on the desired slice rank. The following lemma estimates the slice rank of this larger tensor:

Lemma. The slice rank of  over is at most , where

The result then follows from analyzing the asymptotic behavior of (see this post for details). The proof of the lemma is perhaps more interesting, considering this is where polynomials actually play a role. The first step is to express the tensor as a polynomial. To do this, note that over , we have . As such,

Bounding the slice rank then amounts to decomposing the above polynomial into only a few terms, where either , , or -dependence can be factored out of each term.

To this end, consider the , and -degrees of each monomial, the sum of which gives the total degree of that monomial. Observe from the polynomial’s definition that each monomial has total degree at most , implying that one the , or -degrees is at most . Partition the monomials according to which degree is smallest (breaking ties arbitrarily). For the moment, let’s focus on the monomials for which the -degree is smallest. Then we combine like terms according to the contribution from the variables, resulting in combined terms of the form . How many such terms are there? Considering the polynomial’s definition, we know that each lies in . Then letting , and denote the numbers of ‘s that are 0, 1 and 2, respectively, it follows that counts the total number of possible combined terms that were combined according to . Since the same number arises from combining terms according to or , we end up with the bound .