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 n is even. What is the maximum number of subsets of [n]:=\{1,\ldots,n\} with the property that each has odd size and the intersection between any two has even size?

For each set S, consider its indicator function 1_S\colon [n]\rightarrow \mathbb{F}_2. (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 \leq n. Furthermore, we can saturate this bound by selecting all singletons, and so the bound is sharp.

Next, consider a (v,b,r,k,\lambda)-balanced incomplete block design, that is, a collection of b size-k subsets of [v], called blocks, with the property that every point in [v] belongs to exactly r blocks, and every pair of distinct points is contained in exactly \lambda blocks. We take 0<k<v to prevent degenerate cases.

Fisher’s inequality. A (v,b,r,k,\lambda)-balanced incomplete block design exists only if b\geq v.

Consider the b\times v matrix A whose ith row is the indicator function of the ith block. (Here, we view the entries as real numbers.) First, 0<k<v implies \lambda<r (why?). Next, the definition gives A^\top A=(r-\lambda)I+\lambda J, where J denotes the all-ones matrix. Since A^\top A is positive definite, it has rank v, which in turn implies that A has rank v, which is only possible if b\geq v.

Notice that in this case, the linearly independent vectors are the columns of A, 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 v_1,\ldots,v_n\in\mathbb{C}^d of unit norm such that |\langle v_i,v_j\rangle|=\alpha<1 whenever i\neq j. Then n\leq d^2.

Here, the matrices \{v_iv_i^\top\}_{i=1}^n are linearly independent in the d^2-dimensional real vector space of d\times d 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 d.

— 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 F be a field. A nonzero polynomial p\in F[x] of degree at most d has at most d roots.

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

Corollary. Let F be a field. If p\in F[x_1,\ldots,x_n] has degree at most d and vanishes on more than d points of a line in F^n, then it vanishes on the entire line.

To see this, parameterize the line in terms of a variable t, and then plug this parameterization into p to get a polynomial q in F[t] of degree at most d. Then by the previous theorem, this has more than d roots only if q=0, which in turn establishes that p 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 F be a field, and suppose p\in F[x_1,\ldots,x_n] has total degree t_1+\cdots+t_n. If the coefficient of x_1^{t_1}\cdots x_n^{t_n} is nonzero and S_1,\ldots,S_n\subseteq F satisfy |S_i|>t_i for each i, then there exists (s_1,\ldots,s_n)\in S_1\times\cdots\times S_n such that p(s_1,\ldots,s_n)\neq 0.

As an application of this result, consider the following:

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

S=\{(x,y,z):x,y,z\in\{0,1,\ldots,n\},~x+y+z>0\}

as a set of (n+1)^3-1 points in \mathbb{R}^3. Determine the smallest number of planes, the union of which contains S but does not include (0,0,0).

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

Suppose to the contrary that 3n-1 planes are sufficient, and let \{(x,y,z):a_ix+b_iy+c_iz+d_i\} denote the ith plane. Put

\displaystyle{q(x,y,z):=\prod_{i=1}^{3n-1}(a_ix+b_iy+c_iz+d_i)}.

Then the zero set of q is the union of the 3n-1 planes, and so q(0,0,0)\neq 0 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 q so as to vanish over all of S\cup\{(0,0,0)\}. To this end, we know that

\displaystyle{r(x,y,z):=\prod_{k=1}^n(x-k)(y-k)(z-k)}

is also zero on S, and furthermore, r(0,0,0)=-(n!)^3. As such,

\displaystyle{p(x,y,z):=q(x,y,z)+\frac{q(0,0,0)}{(n!)^3}r(x,y,z)}

will serve as the desired modification. This polynomial has total degree 3n, and the coefficient of x^ny^nz^n is q(0,0,0)/(n!)^3\neq 0. Furthermore, taking S_1=S_2=S_3=\{0,1,\ldots,n\} satisfies the hypothesis of Alon’s Combinatorial Nullstellensatz, which then gives that p fails to vanish on all of S\cup\{(0,0,0)\}, 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 F be a field, and take S\subseteq F of size at most d. Then there exists a nonzero polynomial p\in F[x] of degree at most d that vanishes on S.

This can be proven explicitly or implicitly. For the explicit version, just take p(x)=\prod_{s\in S}(x-s). For the implicit version, take the linear operator that maps F[x] to F^{|S|} by evaluating a given polynomial at each point in S. Since the subspace of polynomials in F[x] of degree at most d has dimension d+1, this mapping has a nontrivial nullspace, thereby implicating the desired nonzero polynomial p. This latter proof can be used to obtain a more general lemma:

Theorem. Let F be a field, and take S\subseteq F^n of size strictly less than \binom{d+n}{n}. Then there exists a nonzero polynomial p\in F[x_1,\ldots,x_n] of degree at most d that vanishes on S.

Indeed, the dimension of the subspace of F[x_1,\ldots,x_n] of polynomials with degree at most d is the number of monomials of degree at most d, which equals the number of n-tuples of nonnegative integers whose sum is at most d. A stars and bars argument then gives that this dimension is

\displaystyle{\sum_{k=0}^d\binom{k+n-1}{k}=\binom{d+n}{n},}

where the last step follows from Pascal’s identity by induction on d. From this, one may conclude (for example) that any two points in F^2 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 F be a finite field, and suppose S\subseteq F^n contains a line in every direction (i.e., S is a Kakeya set). Then S has size at least c_n|F|^n, where c_n depends only on n (and not F).

More explicitly, we will show that S has size at least

\displaystyle{\binom{|F|+n-2}{n}\geq\frac{1}{n!}(|F|-1)^n\geq\frac{1}{2^nn!}|F|^n}.

(Note that this differs slightly from Terry Tao’s exposition.) To do this, we suppose to the contrary that S<\binom{|F|+n-2}{n}. Then by the previous result, there exists a nonzero polynomial p\in F[x_1,\ldots,x_n] of degree d\leq |F|-2 that vanishes on S. Use this to form a homogeneous polynomial q\in F[x_1,\ldots,x_n,z] by multiplying terms of degree k by z^{d-k}. Put x=(x_1,\ldots,x_n). Then q(x,1)=p(x). By assumption, we have that for every v\in F^n\setminus\{0\}, there exists x\in F^n such that \{x+tv:t\in F\} is in the zero set of p. This then implies that \{(x,1)+t(v,0):t\in F\} is in the zero set of q. Note that for every t\in F\setminus\{0\}, the homogeneity of q gives

\displaystyle{q\Big(t^{-1}(x,1)+(v,0)\Big)=\frac{1}{t^d}\cdot q\Big((x,1)+t(v,0)\Big)=\frac{1}{t^d}\cdot p(x+tv)=0.}

That is, q has degree at most |F|-2 and is zero at (v,0)+s(x,1) for every nonzero s. Since this makes up |F|-1 different points on a line, the corollary of the previous section gives that q is also zero when s=0, namely, at (v,0). Since the choice of v was arbitrary, this means q(x,z)=0 whenever z=0. But q(x,0) is the polynomial made up of the terms of maximum degree in p, 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 S\subseteq\mathbb{F}_3^n be if it contains no lines?

Such a set S is known as a capset. The obvious bounds on |S| are \leq 3^n and \geq 2^n, and with a bit of extra work, these were improved to O(3^n/n^{1+\epsilon}) and \geq 2.217^n. On his blog, Terry Tao suspected that the lower bound could be improved all the way up to (3-o(1))^n, 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 S\subseteq\mathbb{F}_3 contains no lines, then |S|\leq o(2.756^n).

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

\displaystyle{\delta_0(x+y+z)=\sum_{a\in S}\delta_a(x)\delta_a(y)\delta_a(z)\qquad \forall x,y,z\in S}.

Indeed, x+y+z=0 precisely when either \{x,y,z\} forms a line in \mathbb{F}_3^n or x=y=z. Since S contains no lines by assumption, both sides of the above identity are zero unless x=y=z, in which case both sides are 1.

The above identity equates functions of the form f\colon S^3\rightarrow \mathbb{F}_3. View this as a 3-way tensor whose entries lie in \mathbb{F}_3 and whose rows, columns and tubes are indexed by members of S. 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

f(x,y,z)=g(x)h(y,z) \quad \text{or} \quad g(y)h(x,z) \quad \text{or} \quad g(z)h(x,y)

and a tensor T has slice rank r if there are r decomposable tensors that sum to T 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 |S|. 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 \delta_0(x+y+z), defined over all x,y,z\in\mathbb{F}_3^n, 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 \delta_0(x+y+z) over x,y,z\in\mathbb{F}_3^n is at most 3R, where

\displaystyle{R=\sum_{\substack{a,b,c\geq0\\a+b+c=n\\b+2c\leq2n/3}}\frac{n!}{a!b!c!}.}

The result then follows from analyzing the asymptotic behavior of R (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 \mathbb{F}_3, we have \delta_0(x)=1-x^2. As such,

\displaystyle{\delta_0(x+y+z)=\prod_{i=1}^n\Big(1-(x_i+y_i+z_i)^2\Big).}

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

To this end, consider the x, y and z-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 2n, implying that one the x, y or z-degrees is at most 2n/3. Partition the monomials according to which degree is smallest (breaking ties arbitrarily). For the moment, let’s focus on the monomials for which the x-degree is smallest. Then we combine like terms according to the contribution from the x variables, resulting in combined terms of the form x_1^{i_1}\cdots x_n^{i_n} h(y,z). How many such terms are there? Considering the polynomial’s definition, we know that each i_j lies in \{0,1,2\}. Then letting a, b and c denote the numbers of i_j‘s that are 0, 1 and 2, respectively, it follows that R counts the total number of possible combined terms that were combined according to x. Since the same number R arises from combining terms according to y or z, we end up with the bound 3R.

Advertisements

2 thoughts on “Introduction to the polynomial method (and other similar things)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s