Polynomial method in combinatorics

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.

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[3].

Finite Field Kakeya Conjecture: Let ${\displaystyle \mathbb {F} _{q}}$ be a finite field with ${\displaystyle q}$ elements. Let ${\displaystyle K\subseteq \mathbb {F} _{q}^{n}}$ be a Kakeya set, i.e. for each vector ${\displaystyle y\in \mathbb {F} _{q}^{n}}$there exists ${\displaystyle x\in \mathbb {F} _{q}^{n}}$ such that ${\displaystyle K}$ contains a line ${\displaystyle \{x+ty,t\in \mathbb {F} _{q}\}}$. Then the set ${\displaystyle K}$ has size at least ${\displaystyle c_{n}q^{n}}$where ${\displaystyle c_{n}>0}$ is a constant that only depends on ${\displaystyle n}$.

Proof: The proof we give will show that ${\displaystyle K}$ has size at least ${\displaystyle c_{n}q^{n-1}}$. The bound of ${\displaystyle c_{n}q^{n}}$ can be obtained using the same method with a little additional work.

Assume we have a Kakeya set ${\displaystyle K}$ with

${\displaystyle |K|<{q+n-3 \choose n-1}}$

Consider the set of monomials of the form ${\displaystyle x_{1}^{d_{1}}x_{2}^{d_{2}}\dots x_{n}^{d_{n}}}$ of degree exactly ${\displaystyle q-2}$. There are exactly ${\displaystyle {q+n-3 \choose n-1}}$ such monomials. Thus, there exists a nonzero homogeneous polynomial ${\displaystyle P(x_{1},x_{2},\dots ,x_{n})}$ of degree ${\displaystyle q-2}$ that vanishes on all points in ${\displaystyle K}$. Note this is because finding such a polynomial reduces to solving a system of ${\displaystyle |K|}$ linear equations for the coefficients.

Now we will use the property that ${\displaystyle K}$ is a Kakeya set to show that ${\displaystyle P}$ must vanish on all of ${\displaystyle \mathbb {F} _{q}^{n}}$. Clearly ${\displaystyle P(0,0\dots ,0)=0}$. Next, for ${\displaystyle y\neq 0}$, there is an ${\displaystyle x}$ such that the line ${\displaystyle \{x+ty,t\in \mathbb {F} _{q}\}}$ is contained in ${\displaystyle K}$. Since ${\displaystyle P}$ is homogeneous, if ${\displaystyle P(z)=0}$ for some ${\displaystyle z\in \mathbb {F} _{q}^{n}}$ then ${\displaystyle P(cz)=0}$ for any ${\displaystyle c\in \mathbb {F} _{q}}$. In particular

${\displaystyle P(tx+y)=P(t(x+t^{-1}y))=0}$

for all nonzero ${\displaystyle t\in \mathbb {F} _{q}}$. However, ${\displaystyle P(tx+y)}$ is a polynomial of degree ${\displaystyle q-2}$ in ${\displaystyle t}$ but it has at least ${\displaystyle q-1}$ roots corresponding to the nonzero elements of ${\displaystyle \mathbb {F} _{q}}$ so it must be identically zero. In particular, plugging in ${\displaystyle t=0}$ we deduce ${\displaystyle P(y)=0}$.

We have shown that ${\displaystyle P(y)=0}$ for all ${\displaystyle y\in \mathbb {F} _{q}^{n}}$ but ${\displaystyle P}$ has degree less than ${\displaystyle q-1}$ in each of the variables so this is impossible by the Schwartz–Zippel lemma. We deduce that we must actually have

${\displaystyle |K|\geq {q+n-3 \choose n-1}\sim {\frac {q^{n-1}}{(n-1)!}}}$

Polynomial partitioning

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].

Applications

A few examples of longstanding open problems that have been solved using the polynomial method are:

• The finite field Kakeya conjecture[3] by Dvir
• The cap set problem by Ellenberg and Gijswijt[7] and the analogous problem over ${\displaystyle \mathbb {Z} _{4}^{n}}$ by Croot, Lev and Pach[8]

• The Erdős distinct distances problem by Guth and Katz[4]
• The Joints Problem in 3D by Guth and Katz[9]. Their argument was later simplified by Elekes, Kaplan and Sharir[10]

See also

• Combinatorial Nullstellensatz

References

1. Guth, L. (2016). Polynomial Methods in Combinatorics. University Lecture Series. American Mathematical Society. ISBN 978-1-4704-2890-7. Retrieved 2019-12-11.
2. Alon, Noga (1999). "Combinatorial Nullstellensatz". Combinatorics, Probability and Computing. 8 (1–2): 7–29. doi:10.1017/S0963548398003411. ISSN 0963-5483.
3. Dvir, Zeev (2008). "On the size of Kakeya sets in finite fields". Journal of the American Mathematical Society. 22 (4): 1093–1097. doi:10.1090/S0894-0347-08-00607-3. ISSN 0894-0347.
4. Guth, Larry; Katz, Nets (2015). "On the Erdős distinct distances problem in the plane". Annals of Mathematics: 155–190. doi:10.4007/annals.2015.181.1.2. hdl:1721.1/92873. ISSN 0003-486X.
5. Kaplan, Haim; Matoušek, Jiří; Sharir, Micha (2012). "Simple Proofs of Classical Theorems in Discrete Geometry via the Guth–Katz Polynomial Partitioning Technique". Discrete & Computational Geometry. 48 (3): 499–517. arXiv:1102.5391. doi:10.1007/s00454-012-9443-3. ISSN 0179-5376.
6. Dvir, Zeev (2012). "Incidence Theorems and Their Applications". Foundations and Trends in Theoretical Computer Science. 6 (4): 257–393. arXiv:1208.5073. Bibcode:2012arXiv1208.5073D. doi:10.1561/0400000056. ISSN 1551-305X.
7. Ellenberg, Jordan; Gijswijt, Dion (2017). "On large subsets of ${\displaystyle \mathbb {F} _{q}^{n}}$ with no three-term arithmetic progression". Annals of Mathematics. 185 (1): 339–343. doi:10.4007/annals.2017.185.1.8. ISSN 0003-486X.
8. Croot, Ernie; Lev, Vsevolod; Pach, Péter (2017). "Progression-free sets in ${\displaystyle \mathbb {Z} _{4}^{n}}$ are exponentially small" (PDF). Annals of Mathematics. 185 (1): 331–337. doi:10.4007/annals.2017.185.1.7. ISSN 0003-486X.
9. Guth, Larry; Katz, Nets Hawk (2010). "Algebraic methods in discrete analogs of the Kakeya problem". Advances in Mathematics. 225 (5): 2828–2839. arXiv:0812.1043. doi:10.1016/j.aim.2010.05.015. ISSN 0001-8708.
10. Elekes, György; Kaplan, Haim; Sharir, Micha (2011). "On lines, joints, and incidences in three dimensions". Journal of Combinatorial Theory, Series A. 118 (3): 962–977. doi:10.1016/j.jcta.2010.11.008. ISSN 0097-3165.

External Links

• Survey on the Polynomial Method by Terence Tao
• Survey on the Polynomial Method by Larry Guth