You are currently browsing the monthly archive for August 2012.
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 .
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 that contains a unit line segment in every direction. Besicovitch showed that such sets may have Lebesgue measure zero for . However, Davies showed that for , Kakeya sets must have Hausdorff dimension , so that a Kakeya set is actually a two dimensional object, despite having no area. The Kakeya conjecture is that for all , Kakeya sets must have full Hausdorff dimension. Wolff was able to show that the Hausdorff dimension of a Kakeya set must be at least for , but progress beyond this has been slow.
In a survey paper, Wolff introduced a finite field analog of the Kakeya conjecture. Let be the finite field with elements. A Kakeya set in is a set that contains a line in every direction. That is, is a Kakeya set if for all in , there exists a in such that the set is a subset of . The finite field Kakeya conjecture is that for any Kakeya set we have for some fixed constant that is independent of .
Theorem 1 (Dvir 2008) If is a Kakeya set in , then , where is a constant that we may choose to be .
Wolff showed that using a proof similar in spirit to his lower bound on the Hausdorff dimension of Kakeya sets in . Since proofs in the finite field case use similar tools to attacks on the , 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 numbers, there is a non-zero polynomial of degree vanishing at those numbers:
Lemma 2 (Fundamental Lemma) Let be a field and let be a finite subset of . If , then there is a non-zero polynomial of degree that vanishes on .
Proof: Let be the least integer such that . By elementary combinatorics, the number of monomials in of degree at most is , so a polynomial in with variable coefficients will have degrees of freedom. Requiring that vanishes on imposes constraints. Since we have more degrees of freedom than constraints, our linear system for the coefficients of has a non-trivial solution.
By a previous post, we know that if is the least integer such that , then , which completes the proof.
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 . This allows us to find a non-zero polynomial of degree less than vanishing on our Kakeya set. However, we will show that a polynomial of degree less than vanishing on a Kakeya set must vanish at every point of , contradicting the fact that the polymomial was non-zero.
Proof: Let be a Kakeya set in . Suppose by way of contradiction that for some constant , which we will choose during the course of the proof. By the fundamental lemma, there exists a non-zero polymomial in of degree vanishing on , where . Choosing will ensure that .
Fix a point in . We wish to show that . Since is a Kakeya set, there exists a point in such that is a subset of . Let ; is a degree polynomial in . Since vanishes on we have for each in . Thus vanishes identically, because it has more roots than its degree.
Since vanishes identically, it’s coefficients must be zero. The coefficients of are polynomials in and , and it turns out that the coefficients of is the degree homogeneous part of evaluated at . (Recall that a polynomial may be split up at a sum of its homogenous parts , where all of the monomials in are of degree .) Thus we have shown that .
Since was arbitrary, vanishes identically on , which contradicts the fact that is degree .
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 is a point where lines intersect in indepedent directions. The joints problem is to find an upper bound the number of joints formed by lines in .
A lower bound on the maximum number of joints in is given by the example of a cube lattice . Each side of the cube has roughly lattice points, and we take as our set of lines the lines through these lattice points that are parallel to either the , , or axes—this gives us roughly lines. There are roughly 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: lines determine at most joints.
After Dvir’s proof of the finite field Kakeya problem, there were hopes that the polynomial method could be applied to problems in . 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 be a set of lines in . If is the set of joints formed by , then there exists a constant such that .
Proof: Let’s set for convenience. Suppose by way of contradiction that , where is a constant that we will choose during the course of the proof.
Let . We will refine so that each remaining line contains at least joints. We begin by picking a line in . If contains fewer than points of , we will discard and remove all of the points on from . We continue this process until all of the remaining lines contain at least joints. We will call the resulting sets and . Note that every point of is a joint of . Since we removed at most joints from , we have .
Next we will find a non-zero polynomial that vanishes on and all of the lines of . Since , the fundamental lemma provides a non-zero polynomial of degree that vanishes on . We would also like to vanish on all of the lines of . Because is degree , will vanish on any line that contains more than zeros of . By our refining process, each line of contains at least zeros of . Since , we can make by choosing , in which case vanishes on all of the lines of , as desired.
The polynomial has a peculiar property: at each point in , vanishes along lines in , which run in independent directions. Suppose that runs in direction , so that . The directional derivative of at in the direction of must be zero, since it is evaluated along ; that is, . The direction vectors span all of , because they are independent. Thus is perpedicular to every vector in , and so . Since was arbitrary, vanishes at every point of .
Now we can iterate the preceeding argument: since the components of vanish on and have degree less than , they also vanish on every line of . If we take one component of , say , we can use that fact that vanishes on the lines of to show that vanishes on . Continuing in this way, we see that all of the iterated partial derivatives of must be zero. But the degree partial derivatives of are multiples of the coefficients of . Thus the coefficients of must zero, which contradicts the fact that is a non-zero polynomial.
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
I would like to record a few propositions about number of monomials of a given degree in the ring of polynomials in several variables. We begin with a basic counting problem: suppose we have boxes and balls—how many ways can we place the balls in the boxes? The boxes may be empty, or they may contain any number of balls, we only require that all are placed. There is a clever way of reducing this problem to the easier problem of counting the number of ways to select items out of a larger set.
Proposition 1 The number of ways to place balls into boxes is .
Proof: We will represent the problem typographically, using vertical bars to form the boxes, and representing the balls by dots. Thus if and , one arrangement might look like , where the first box contains one ball, the second box is empty, and the last box contains three balls.
Notice that we have symbols. Since the first and last symbols are always lines, out of the inside symbols, we must choose of these to be dots. The number of ways to choose dots out of symbols is , and since every choice of dots corresponds to a way of placing balls into boxes, our desired count is .
With this proposition in hand, we can proceed to counting monomials. First, let’s recall some definitions. Let be any commutative ring (e.g. the integers ), and let be the ring of polynomials over in variables. A monomial in is a product of the variables: . The degree of a monomial is the sum of its exponents: . For example, the monomials of degree three in are , , , and .
First we count monomials of fixed degree.
Proposition 2 The number of monomials in of degree is .
Proof: We can reduce the problem of counting monomials to the problem of counting balls in boxes. We create a box for each variable, and we let the degree of each variable be the number of balls in its box. Using the example from before, if and , a possible arrangement is , which corresponds to the monomial . Of course we could use the monomial to place balls in boxes, so the two counting problems are equivalent. Hence the number of monomials in of degree is , the number of ways to place balls in boxes.
Next we’ll count the number of monomials of degree less than or equal to .
Proposition 3 The number of monomials in of degree less than or equal to is .
Proof: Again we reduce the problem of counting monomials to the problem of counting balls in boxes, but this time we add an extra box to get the monomials of lower degree. So if and , a possible arrangement is , which corresponds to . Notice that the dot in the last box isn’t counted, so our monomial is degree three instead of degree four. Since we have boxes and balls, the number of possibilities is , as desired.
We also could have proved this using the previous proposition by noting that the number of monomials in variables of degree less than or equal to is the same as the number of monomials in variables of degree equal to . To get from the monomials of degree in variables to the monomials of degree at most in variables, we simply substitute 1 into the last variable. To get back the other way we must “homogenize.” For example, goes to the degree 5 monomial .
The last two propositions yield a nice corollary. Since the number of monomials in variables of degree less than or equal to is the sum of the number of monomials of degree equal to , we have a combinatorial proof of the identity