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]