You are currently browsing the category archive for the ‘math.CO’ category.
This is the first of a series of three posts outlining the key ideas behind my recent paper “Growth Estimates in Postive Characteristics via Collisions”, which is joint work with Esen Aksoy Yazici, Misha Rudnev, and Ilya Shkredov.
Briefly, this paper proves a number of new sum-product type estimates by expanding on the point/plane incidence approach developed in Misha’s paper “On the number of incidences between points and planes in three dimensions” and Misha and Ilya’s joint work with Olly Roche-Newton “New sum-product type estimates over finite fields”. The heart of our new paper is a bound on the number of “collisions” between images of lines.
The first post in this series describes an incidence bound, which is one of the applications of our sum-product results. The second post will give the relevant background on the sum-product problem, and the third post will describe the “collision” bound and a sum-product corollary, which implies the incidence bound.
(Acknowledgement: I must thank Adam Sheffer for pointing out that I haven’t written about my own work yet!)
In a sense, this bound is halfway between the Szemeredi-Trotter theorem and the “trivial” Cauchy-Schwarz bound. The Szemeredi-Trotter theorem states that if is a set of point in and is a set of lines in , then
The proof of this bound relies on the ordering of the reals, and doesn’t apply to finite fields. However, there is a bound that applies over based on the Cauchy-Schwarz inequality. This bound states that
(See this previous post.) In the case where , the Cauchy-Schwarz bound was improved to
by Bourgain, Katz, and Tao using a sum-product estimate, for some small . Prior to our result, the best value for was roughly (due to Jones). We improve to , but our result only applies in case where is a Cartesian product, while the Cauchy-Schwarz bound and (3) apply to general points sets.
Proof of the incidence bound
The proof of Theorem 1 relies on a bound for the number of collinear triples of a point set .
If the points are collinear, then
The number of solutions to this equation for in is the number of collinear triples. Later we will prove that
For now, let us assume this upper bound, and use it to prove the incidence bound.
Proof: Let denote the set of lines in that are incident to at least three points of . Then
so it suffices to bound .
Now let , so that is the number of points of contained in the line . On one hand,
Since is convex in , the sum on the left side of (4) is minimized by the average of , which is :
Combining the lower bound with the upper bound, we have
Now we solve for :
Combined with initial reduction, this bound completes the proof.
Note that this proof is similar to the proof of the Cauchy-Schwarz bound (or restricted subgraph bounds in general), but we use the non-trivial bound on instead of general geometric information about points and lines.
Next post: background on the sum-product problem
The upper bound on was one of the last things we discovered while working on this paper. We started our investigation by looking for lower bounds for a certain sum-product type set . The next post will give the relevant background on the sum-product problem, and the final post in the series will describe the main technical innovation of the paper and give a proof of the bound .
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
-Incidence problems and bipartite graphs-
An important problem in combinatorial geometry is to study the number of incidences between a set of points and set of lines (or curves, surfaces, etc.). More specifically, let be a finite subset of and let be a finite set of lines (or curves, surfaces, etc.). We define the set of incidences between and by . Our problem is now to study the size of . Of course we always have the trivial bound , but we would like to do better.
Introducing the set of incidences of and may just seem like good notation, but in fact it is characterizing our incidence problem in terms of graph theory: we define the incidence graph of and to be the graph whose vertices are points of and lines of , with a point connected to a line if . So the set of edges of is .
The incidence graph is a special type of graph called a bipartite graph. A bipartite graph is a graph whose vertices form two disjoint sets, and , such that no edge joins two points of and no edge joins two points of ; that is, the edges of are of the form with in and in . We will write to specify the vertex sets and we write or for the edges of .
As with incidence graphs, we have the trivial bound and in general we can’t do any better. In the next section we will prove non-trivial bounds on the number of edges of a bipartite graph under certain restrictions. By geometric considerations, we’ll see that many incidence graphs satisfy these restrictions, thus giving us non-trivial bounds on . It turns out that these bounds are actually sharp for point-line incidences over finite fields.
-Restricted subgraph bound-
We noted above that the trivial bound cannot be improved in general. We call a graph that achieves equality a complete bipartite graph. That is, a complete bipartite graph is a bipartite graph with vertex sets and such that every vertex of is connected to every vertex of . If and , then we denote the complete bipartite graph with vertex sets and by . If we consider only bipartite graphs whose edge set does not contain a copy of for some and , we should be able to improve this trivial bound:
Restricted Subgraph Bound: Let be a bipartite graph that does not contain a as a subgraph, where “” corresponds to points of and “” corresponds to points of . The cardinality of the set of edges of satisfies
Before we prove the restricted subgraph bound, let’s note that a point-line incidence graph contains no , because any two points lie on a unique line. Thus .
Proof: For now, let’s assume that each vertex in has degree greater than , so that in particular . The general case will follow easily from this particular case.
We define the set of “fans” in :
Since is convex in , the sum on the left side of (3) is minimized by the average of the degrees:
Solving for yields the desired result:
By symmetry we have the bound
Thus we may conclude that
The proof I gave here is based off of Jacob Fox’s lecture notes from a combinatorics class at MIT.
The popularity lemma is simple lemma about refining the vertices of a bipartite graph by degree. Since it gives you a lower bound on the number of edges that remain after refining, it can be used to show that not too many edges are lost by refining.
Popularity Lemma: Let be a bipartite graph. Let be the set of vertices in with , where . Then the cardinality of the set of edges from to satisfies
We can generalize slightly: if is a constant such that , then
The first version can be recovered by setting , which is the average degree of a vertex in . From this point of view, the bound is only useful when is smaller than the average degree. In particular, if , where and is the average density of a vertex in , then
Proof: We may divide the vertices of into vertices with degree at least and vertices with degree less than : . Summing degrees over the vertices of yields
Since each vertex in has degree less than , we have
Since , we have
Rearranging yields the desired result.
Although I’m sure this is an old result, I first saw this lemma in Guth and Katz’s 2008 paper on the joints problem.
Given an arbitrary set of points in the plane, we would expect most pairs of points to determine distinct lines–this is the “generic” case. The obvious counterexample is when all of the points lie on a single line. Beck’s lemma says that one of these two situations must occur (up to constants) in any finite set of points in the plane.
Beck’s Lemma: Let be a subset of with . Then one of the following holds:
- There is a line containing points of for some constant ,
- or there are distinct lines containing at least two points of each.
Note that (2) is the generic case, while (1) is a counterexample to the generic case.
Proof of Beck’s lemma: We say that are -connected if the line determined by and contains between and points of .
Let be the set of lines determined by containing more than points of . Then by the Szemerédi-Trotter theorem:
If the max is , then we have and if the max is , then we have . Thus
If and are -connected, then they lie on a line of . Thus the number of lines created by a -connected pair is at most . Each such line contains at most pairs of points, so
Let be a positive constant that we will determine later. From now on we focus our attention on such that . For this range of , the number of -connected pairs is bounded above by :
where we bounded the sum of first term by the highest term (i.e. ) and we bounded the second term using the geometric series ().
Since there are pairs of points, if is large enough then there are more than pairs of points that are not -connected for . If one pair is above this range, then the line that they determine contains at least points, which gives us (1). Otherwise we have more than pairs below this region and so we have option (2). QED
Beck’s original proof did not use the Szemeredi-Trotter theorem—in fact, Beck’s paper was published in the same issue of Combinatorica as Szemeredi and Trotter’s paper. Instead he proved the bound on the number of lines containing between and points:
where and . This estimate is sufficient for our argument.