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 (around 2016), the polynomial method has led to the development of remarkably simple solutions to several long-standing open problems. 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, have been known since the 1990s, it was not until around 2010 that a broader framework for the polynomial method has been developed.
Mathematical overview Many uses of the polynomial method follow the same high-level approach. The approach is as follows:
Embed some combinatorial problem into a vector space. Capture the hypotheses of the problem by constructing a polynomial of low-degree that is zero on a certain set After constructing the polynomial, argue about its algebraic properties to deduce that the original configuration must satisfy the desired properties.
Example As an example, we outline Dvir's proof of the Finite Field Kakeya Conjecture using the polynomial method. Finite Field Kakeya Conjecture: Let F q {\displaystyle \mathbb {F} _{q}} be a finite field with q {\displaystyle q} elements. Let K ⊆ F q n {\displaystyle K\subseteq \mathbb {F} _{q}^{n}} be a Kakeya set, i.e. for each vector y ∈ F q n {\displaystyle y\in \mathbb {F} _{q}^{n}} there exists x ∈ F q n {\displaystyle x\in \mathbb {F} _{q}^{n}} such that K {\displaystyle K} contains a line { x + t y , t ∈ F q } {\displaystyle \{x+ty,t\in \mathbb {F} _{q}\}} . Then the set K {\displaystyle K} has size at least c n q n {\displaystyle c_{n}q^{n}} where c n > 0 {\displaystyle c_{n}>0} is a constant that only depends on n {\displaystyle n} . Proof: The proof we give will show that K {\displaystyle K} has size at least c n q n − 1 {\displaystyle c_{n}q^{n-1}} . The bound of c n q n {\displaystyle c_{n}q^{n}} can be obtained using the same method with a little additional work. Assume we have a Kakeya set K {\displaystyle K} with
| K | < ( q + n − 3 n − 1 ) {\displaystyle |K|<{q+n-3 \choose n-1}}
… excerpt ends here. Continue reading the full article.
