In mathematics, the polynomial method is an algebraic approach to combinatorics problems that involves capturing some combinatorial structure using polynomials and proceeding to argue about their algebraic properties.
Recently, the polynomial method has led to the development of remarkably simple solutions to several long-standing open problems.
[1] The polynomial method encompasses a wide range of specific techniques for using polynomials and ideas from areas such as algebraic geometry to solve combinatorics problems.
While a few techniques that follow the framework of the polynomial method, such as Alon's Combinatorial Nullstellensatz,[2] have been known since the 1990s, it was not until around 2010 that a broader framework for the polynomial method has been developed.
Many uses of the polynomial method follow the same high-level approach.
The approach is as follows: As an example, we outline Dvir's proof of the Finite Field Kakeya Conjecture using the polynomial method.
[3] Finite Field Kakeya Conjecture: Let
be a finite field with
be a Kakeya set, i.e. for each vector
contains a line
is a constant that only depends on
Proof: The proof we give will show that
has size at least
can be obtained using the same method with a little additional work.
Assume we have a Kakeya set
Consider the set of monomials of the form
Thus, there exists a nonzero homogeneous polynomial
that vanishes on all points in
Note this is because finding such a polynomial reduces to solving a system of
linear equations for the coefficients.
is a Kakeya set to show that
such that the line
is a polynomial of degree
roots corresponding to the nonzero elements of
in each of the variables so this is impossible by the Schwartz–Zippel lemma.
A variation of the polynomial method, often called polynomial partitioning, was introduced by Guth and Katz in their solution to the Erdős distinct distances problem.
[4] Polynomial partitioning involves using polynomials to divide the underlying space into regions and arguing about the geometric structure of the partition.
These arguments rely on results from algebraic geometry bounding the number of incidences between various algebraic curves.
The technique of polynomial partitioning has been used to give a new proof of the Szemerédi–Trotter theorem via the polynomial ham sandwich theorem and has been applied to a variety of problems in incidence geometry.
[5][6] A few examples of longstanding open problems that have been solved using the polynomial method are: