This summer I’ve been studying problems in geometric combinatorics such as the joints problem and the Erdös distinct distance problem. The joints problem was open for 20 years and the distinct distance problem was open for over 60 years before they were resolved by a new technique called the polynomial method. (Algebraic techniques have been around for longer, but their application to incidence problems is new.) In addition to solving hard problems, the polynomial method has the added virtue of producing short and simple proofs. I will showcase two examples the polynomial method in action: Dvir’s proof of the finite field Kakeya conjecture, and Kaplan, Sharir, and Shustin’s proof of the joints problem in ${{\mathbb R}^d}$.

1. The Kakeya Problem

The finite field Kakeya problem and the joints problem are related to an open problem called the Kakeya conjecture. A Kakeya set, or Besicovitch set, is a subset of ${{\mathbb R}^d}$ that contains a unit line segment in every direction. Besicovitch showed that such sets may have Lebesgue measure zero for ${d\geq 2}$. However, Davies showed that for ${d=2}$, Kakeya sets must have Hausdorff dimension ${2}$, so that a Kakeya set is actually a two dimensional object, despite having no area. The Kakeya conjecture is that for all ${d}$, Kakeya sets must have full Hausdorff dimension. Wolff was able to show that the Hausdorff dimension of a Kakeya set must be at least ${\frac{d+2}{2}}$ for ${d\geq 2}$, but progress beyond this has been slow.
In a survey paper, Wolff introduced a finite field analog of the Kakeya conjecture. Let ${{\mathbb F}_q}$ be the finite field with ${q}$ elements. A Kakeya set in ${{\mathbb F}_q^d}$ is a set that contains a line in every direction. That is, ${K\subseteq {\mathbb F}_q^d}$ is a Kakeya set if for all ${\bold{y}}$ in ${{\mathbb F}_q^d}$, there exists a ${\bold{x}}$ in ${{\mathbb F}_q^d}$ such that the set ${\{\bold{x}+t\bold{y}\colon t\in{\mathbb F}_q\}}$ is a subset of ${K}$. The finite field Kakeya conjecture is that for any Kakeya set ${K}$ we have ${|K|\geq C_dq^d}$ for some fixed constant ${C_d}$ that is independent of ${q}$.

Theorem 1 (Dvir 2008) If ${K}$ is a Kakeya set in ${{\mathbb F}_q^d}$, then ${|K|\geq C_dq^d}$, where ${C_d}$ is a constant that we may choose to be ${\frac{1}{d!}}$.

Wolff showed that ${|K|\geq C_dq^{(d+2)/2}}$ using a proof similar in spirit to his ${\frac{d+2}{2}}$ lower bound on the Hausdorff dimension of Kakeya sets in ${{\mathbb R}^d}$. Since proofs in the finite field case use similar tools to attacks on the ${{\mathbb R}^d}$, but involve fewer technicalities, it was hoped that the finite field case would serve as an instructive model. In 2008, Dvir proved the finite field Kakeya conjecture using the so-called polynomial method, which currently has no continuous analog.

2. The Fundamental Lemma

The fundamental lemma of the polynomial method is a higher dimensional analog of the fact that, given ${n}$ numbers, there is a non-zero polynomial of degree ${n}$ vanishing at those numbers:

Lemma 2 (Fundamental Lemma) Let ${k}$ be a field and let ${S}$ be a finite subset of ${k^n}$. If ${|S|=m}$, then there is a non-zero polynomial of degree ${d\leq\lceil(n!m)^{1/n}\rceil}$ that vanishes on ${S}$.

Proof: Let ${d}$ be the least integer such that ${m<{n+d\choose d}}$. By elementary combinatorics, the number of monomials in ${k[x_1,\ldots,x_n]}$ of degree at most ${d}$ is ${{n+d\choose d}}$, so a polynomial ${P}$ in ${k[x_1,\ldots,x_n]}$ with variable coefficients will have ${{n+d\choose d}}$ degrees of freedom. Requiring that ${P}$ vanishes on ${S}$ imposes ${m}$ constraints. Since we have more degrees of freedom than constraints, our linear system for the coefficients of ${P}$ has a non-trivial solution.

By a previous post, we know that if ${d}$ is the least integer such that ${m<{n+d\choose d}}$, then ${d\leq\lceil(n!m)^{1/n}\rceil}$, which completes the proof. $\Box$

3. Dvir’s Proof

The basic argument in Dvir’s proof of the finite field Kakeya conjecture is to assume that you have a Kakeya set that is smaller than ${Cq^d}$. This allows us to find a non-zero polynomial of degree less than ${q}$ vanishing on our Kakeya set. However, we will show that a polynomial of degree less than ${q}$ vanishing on a Kakeya set must vanish at every point of ${{\mathbb F}_q^d}$, contradicting the fact that the polymomial was non-zero.

Proof: Let ${K}$ be a Kakeya set in ${{\mathbb F}_q^d}$. Suppose by way of contradiction that ${K for some constant ${C}$, which we will choose during the course of the proof. By the fundamental lemma, there exists a non-zero polymomial ${P}$ in ${k[x_1,\ldots,x_d]}$ of degree ${n}$ vanishing on ${K}$, where ${n\leq\lceil (d!Cq^d)^{1/d}\rceil}$. Choosing ${C\leq\frac 1{d!}}$ will ensure that ${n.

Fix a point ${\bold{y}}$ in ${{\mathbb F}_q^d}$. We wish to show that ${P(\bold{y})=0}$. Since ${K}$ is a Kakeya set, there exists a point ${\bold{x}}$ in ${{\mathbb F}_q^d}$ such that ${\{\bold{x}+t\bold{y}\colon t\in{\mathbb F}_q\}}$ is a subset of ${K}$. Let ${\tilde{P}(t)=P(\bold{x}+t\bold{y})}$; ${\tilde{P}}$ is a degree ${n}$ polynomial in ${{\mathbb F}_q[t]}$. Since ${P}$ vanishes on ${K}$ we have ${\tilde{P}(t)=0}$ for each ${t}$ in ${{\mathbb F}_q}$. Thus ${\tilde{P}}$ vanishes identically, because it has more roots than its degree.

Since ${\tilde{P}}$ vanishes identically, it’s coefficients must be zero. The coefficients of ${\tilde{P}}$ are polynomials in ${\bold{x}}$ and ${\bold{y}}$, and it turns out that the coefficients of ${t^n}$ is the ${n^\text{th}}$ degree homogeneous part of ${P}$ evaluated at ${\bold{y}}$. (Recall that a polynomial ${P}$ may be split up at a sum of its homogenous parts ${P=\sum_{i=0}^n P_i}$, where all of the monomials in ${P_i}$ are of degree ${i}$.) Thus we have shown that ${P_n(\bold{y})=0}$.

Since ${\bold{y}}$ was arbitrary, ${P_n}$ vanishes identically on ${{\mathbb F}_q^d}$, which contradicts the fact that ${P}$ is degree ${n}$. $\Box$

4. The Joints Problem

In the same survey, Wolff describes another discrete incidence problem that is related to the Kakeya conjecture: the joints problem. A joint in ${{\mathbb R}^d}$ is a point where ${d}$ lines intersect in indepedent directions. The joints problem is to find an upper bound the number of joints formed by ${n}$ lines in ${{\mathbb R}^d}$.

A lower bound on the maximum number of joints in ${{\mathbb R}^3}$ is given by the example of a cube lattice ${[0,\sqrt{n}]\times [0,\sqrt{n}]\times [0,\sqrt{n}]}$. Each side of the cube has roughly ${n}$ lattice points, and we take as our set of lines the lines through these lattice points that are parallel to either the ${x}$, ${y}$, or ${z}$ axes—this gives us roughly ${3n}$ lines. There are roughly ${n^{3/2}}$ lattice points inside the cube, and these points are exactly the set of joints formed by our lines. The conjecture asserts that this is sharp: ${n}$ lines determine at most ${Cn^{3/2}}$ joints.

After Dvir’s proof of the finite field Kakeya problem, there were hopes that the polynomial method could be applied to problems in ${{\mathbb R}^d}$. The combined genius of Larry Guth and Nets Katz produced the first such successful application, which was futher generalized and simplified by a host of researchers. I will give a simplified proof due Kaplan, Sharir, and Shustin.

The basic outline of their proof is this: assume that the set of joints is larger than we believe it should be, which allows us to find a non-zero polynomial vanishing on all of the joints and all of the lines forming the joints. We will show that if a polynomial vanishes on all the lines forming a joint, the gradient of the polynomial must vanish at that joint too. Iterating this argument, we will show that all of the partial derivatives of the polynomial vanish. Since the partial derivatives must be constant at some point, this shows that the coefficients of the polynomial must be zero.

Theorem 3 (Guth and Katz 2009) Let ${L}$ be a set of ${n}$ lines in ${{\mathbb R}^d}$. If ${J_L}$ is the set of joints formed by ${L}$, then there exists a constant ${C}$ such that ${|J_L|\leq Cn^{d/(d-1)}}$.

Proof: Let’s set ${m=|J_L|}$ for convenience. Suppose by way of contradiction that ${m>Cn^{d/(d-1)}}$, where ${C}$ is a constant that we will choose during the course of the proof.

Let ${\rho=m/2n}$. We will refine ${L}$ so that each remaining line contains at least ${\rho}$ joints. We begin by picking a line ${\ell}$ in ${L}$. If ${\ell}$ contains fewer than ${\rho}$ points of ${J_L}$, we will discard ${\ell}$ and remove all of the points on ${\ell}$ from ${J_L}$. We continue this process until all of the remaining lines contain at least ${\rho}$ joints. We will call the resulting sets ${L'}$ and ${J_L'}$. Note that every point of ${J_L'}$ is a joint of ${L'}$. Since we removed at most ${m/2}$ joints from ${J_L}$, we have ${m\geq|J_L'|\geq m/2}$.

Next we will find a non-zero polynomial that vanishes on ${J_L'}$ and all of the lines of ${L'}$. Since ${|J_L'|\leq m}$, the fundamental lemma provides a non-zero polynomial ${P}$ of degree ${r\leq\lceil(d!m)^{1/d}\rceil<2(d!m)^{1/d}}$ that vanishes on ${J_L'}$. We would also like ${P}$ to vanish on all of the lines of ${L'}$. Because ${P}$ is degree ${r}$, ${P}$ will vanish on any line that contains more than ${r}$ zeros of ${P}$. By our refining process, each line of ${L'}$ contains at least ${\rho}$ zeros of ${P}$. Since ${\rho=m/2n>\frac 12 C^{(d-1)/d}m^{1/d}}$, we can make ${\rho>r}$ by choosing ${C>4^{d/(d-1)}(d!)^{1/(d-1)}}$, in which case ${P}$ vanishes on all of the lines of ${L'}$, as desired.

The polynomial ${P}$ has a peculiar property: at each point ${\bold{x}}$ in ${J_L'}$, ${P}$ vanishes along ${d}$ lines ${\ell_1,\ldots,\ell_d}$ in ${L'}$, which run in independent directions. Suppose that ${\ell_i}$ runs in direction ${\bold{y}_i}$, so that ${\ell_i=\{\bold{x}+t\bold{y}_i\colon t\in{\mathbb R}\}}$. The directional derivative of ${P}$ at ${\bold{x}}$ in the direction of ${\bold{y}_i}$ must be zero, since it is evaluated along ${\ell_i}$; that is, ${\nabla P(\bold{x})\cdot\bold{y}_i=0}$. The direction vectors ${\bold{y}_1,\ldots,\bold{y}_d}$ span all of ${{\mathbb R}^d}$, because they are independent. Thus ${\nabla P(\bold{x})}$ is perpedicular to every vector in ${{\mathbb R}^d}$, and so ${\nabla P(\bold{x})=0}$. Since ${\bold{x}}$ was arbitrary, ${\nabla P}$ vanishes at every point of ${J_L'}$.

Now we can iterate the preceeding argument: since the components of ${\nabla P}$ vanish on ${J_L'}$ and have degree less than ${r}$, they also vanish on every line of ${L'}$. If we take one component of ${\nabla P}$, say ${P_{x_1}}$, we can use that fact that ${P_{x_1}}$ vanishes on the lines of ${L'}$ to show that ${\nabla P_{x_1}}$ vanishes on ${J_L'}$. Continuing in this way, we see that all of the iterated partial derivatives of ${P}$ must be zero. But the ${r^\text{th}}$ degree partial derivatives of ${P}$ are multiples of the coefficients of ${P}$. Thus the coefficients of ${P}$ must zero, which contradicts the fact that ${P}$ is a non-zero polynomial. $\Box$

5. Bibliography

Here is a short bibliography for each section.

The Kakeya Problem:

Dvir’s Proof of the Finite Field Kakeya Problem:

The Joints Problem:

• Guth and Katz’s 2009 paper (difficult read)
• Kaplan, Sharir, and Shustin’s short proof
• Quilodran’s summary

Advertisements