Combinatorial incidence geometry is the study of the possible combinatorial configurations between geometric objects such as lines and circles. One of the basic open problems in the subject has been the Erdős distance problem, posed in 1946:

Problem 1 (Erdős distance problem) Let {N} be a large natural number. What is the least number {\# \{ |x_i-x_j|: 1 \leq i < j \leq N \}} of distances that are determined by {N} points {x_1,\ldots,x_N} in the plane?

Erdős called this least number {g(N)}. For instance, one can check that {g(3)=1} and {g(4)=2}, although the precise computation of {g} rapidly becomes more difficult after this. By considering {N} points in arithmetic progression, we see that {g(N) \leq N-1}. By considering the slightly more sophisticated example of a {\sqrt{N} \times \sqrt{N}} lattice grid (assuming that {N} is a square number for simplicity), and using some analytic number theory, one can obtain the slightly better asymptotic bound {g(N) = O( N / \sqrt{\log N} )}.

On the other hand, lower bounds are more difficult to obtain. As observed by Erdős, an easy argument, ultimately based on the incidence geometry fact that any two circles intersect in at most two points, gives the lower bound {g(N) \gg N^{1/2}}. The exponent {1/2} has been slowly increasing over the years by a series of increasingly intricate arguments combining incidence geometry facts with other known results in combinatorial incidence geometry (most notably the Szemerédi-Trotter theorem) and also some tools from additive combinatorics; however, these methods seemed to fall quite short of getting to the optimal exponent of {1}. (Indeed, previously to last week, the best lower bound known was approximately {N^{0.8641}}, due to Katz and Tardos.)

Very recently, though, Guth and Katz have obtained a near-optimal result:

Theorem 2 One has {g(N) \gg N / \log N}.

The proof neatly combines together several powerful and modern tools in a new way: a recent geometric reformulation of the problem due to Elekes and Sharir; the polynomial method as used recently by Dvir, Guth, and Guth-Katz on related incidence geometry problems (and discussed previously on this blog); and the somewhat older method of cell decomposition (also discussed on this blog). A key new insight is that the polynomial method (and more specifically, the polynomial Ham Sandwich theorem, also discussed previously on this blog) can be used to efficiently create cells.

In this post, I thought I would sketch some of the key ideas used in the proof, though I will not give the full argument here (the paper itself is largely self-contained, well motivated, and of only moderate length). In particular I will not go through all the various cases of configuration types that one has to deal with in the full argument, but only some illustrative special cases.

To simplify the exposition, I will repeatedly rely on “pigeonholing cheats”. A typical such cheat: if I have {n} objects (e.g. {n} points or {n} lines), each of which could be of one of two types, I will assume that either all {n} of the objects are of the first type, or all {n} of the objects are of the second type. (In truth, I can only assume that at least {n/2} of the objects are of the first type, or at least {n/2} of the objects are of the second type; but in practice, having {n/2} instead of {n} only ends up costing an unimportant multiplicative constant in the type of estimates used here.) A related such cheat: if one has {n} objects {A_1,\ldots,A_n} (again, think of {n} points or {n} circles), and to each object {A_i} one can associate some natural number {k_i} (e.g. some sort of “multiplicity” for {A_i}) that is of “polynomial size” (of size {O(N^{O(1)})}), then I will assume in fact that all the {k_i} are in a fixed dyadic range {[k,2k]} for some {k}. (In practice, the dyadic pigeonhole principle can only achieve this after throwing away all but about {n/\log N} of the original {n} objects; it is this type of logarithmic loss that eventually leads to the logarithmic factor in the main theorem.) Using the notation {X \sim Y} to denote the assertion that {C^{-1} Y \leq X \leq CY} for an absolute constant {C}, we thus have {k_i \sim k} for all {i}, thus {k_i} is morally constant.

I will also use asymptotic notation rather loosely, to avoid cluttering the exposition with a certain amount of routine but tedious bookkeeping of constants. In particular, I will use the informal notation {X \lll Y} or {Y \ggg X} to denote the statement that {X} is “much less than” {Y} or {Y} is “much larger than” {X}, by some large constant factor.

See also Janos Pach’s recent reaction to the Guth-Katz paper on Kalai’s blog.

— 1. Reduction to a linear problem —

Traditionally, the Erdős distance problem has been attacked by first casting it as a question about incidences between circles, by starting with the trivial observation that if two points {x_i,x_j} are equidistant from a third point {x_k}, then {x_i, x_j} lie on a circle centred at {x_k}.

The incidence geometry of circles, however, is not quite as well understood as the incidence geometry of lines, and so one often then converted the circle incidence problem to a line incidence problem, for instance by using the elementary Euclidean geometry fact that if two circles intersected at a pair of points, then the centres of these circles would lie on the perpendicular bisector of that pair of points. Indeed, by combining this elementary observation with the celebrated Szemerédi-Trotter theorem that gives a sharp incidence bound for a collection of lines and points, Chung, Szemerédi, and Trotter were already able to obtain the respectable lower bound of {g(N) \gg N^{4/5-o(1)}}.

The first innovation of Guth and Katz (which builds upon earlier work in this direction by Elekes and Sharir) is to use elementary Euclidean geometry to recast the distance problem as a linear problem in a slightly different fashion, namely as an incidence problem of lines in three dimensions {{\bf R}^3} rather than two.

Let’s see how this works. To prove the main theorem, we will argue by contradiction, assuming that {g(N) \lll N/\log N} for some large {N}. Thus, we can find {N} points {x_1,\ldots,x_N} in the plane which only subtend {g(N) \lll N/\log N} distances. We think of these distances as the lengths of line segments {\overline{x_i x_j}} connecting two of the points {x_i, x_j}. There are {\binom{N}{2} \sim N^2} different line segments {\overline{x_i x_j}} that have these lengths. A standard application of the Cauchy-Schwarz inequality then shows that there must be many pairs of distinct but congruent line segments {\overline{x_i x_j}}, {\overline{x_k x_l}} (i.e. line segments of equal length {|x_i-x_j| = |x_k-x_l|}); in fact, their number must be

\displaystyle \frac{\binom{N}{2}^2}{g(N)} - \binom{N}{2} \ggg N^3 \log N.

So, we have a lot ({\ggg N^3 \log N}) of pairs {\overline{x_i x_j}, \overline{x_k x_l}} of congruent line segments. Now we use a trivial but fundamentally important observation of Elekes and Sharir to recast the problem in terms of rigid motions:

Proposition 3 Two line segments {\overline{AB}, \overline{CD}} in the plane are congruent if and only if there is an orientation-preserving rigid motion that maps {A} to {C} and {B} to {D}. Furthermore, this rigid motion is unique.

Proof: Translate {A} to {C} and then rotate appropriately. \Box

Let us call the space of orientation-preserving rigid motions {SE(2) \equiv SO(2) \ltimes {\bf R}^2} (the two-dimensional special Euclidean group); it is a three-dimensional Lie group. From the above proposition we thus see that we can find {\ggg N^3\log N} quintuples {(x_i, x_j, x_k, x_l, R)}, where {R \in SE(2)} is such that {R(x_i) = R(x_k)} and {R(x_j) = R(x_l)}.

We now dualise the problem; rather than think about rigid motions acting on pairs of points, we think about pairs of points describing a set of rigid motions. For any pair of points {x, y}, let {\ell_{x \rightarrow y} \subset SE(2)} of all rigid motions that map {x} to {y}. This is a one-dimensional subset of {SE(2)}; indeed, {\ell_{x \rightarrow y}} consists of the translation from {x} to {y}, together with rotations around an origin {p} that lies on the perpendicular bisector of {\overline{xy}}, with a rotation angle {\theta} obeying the relation

\displaystyle |\cot \frac{\theta}{2}| = \frac{|\overline{pm}|}{|\overline{mx}|}

where {m := \frac{x+y}{2}} is the midpoint of {x} and {y}. If we discard the translation (which can easily be dealt with by a separate argument) as well as the point reflection (corresponding to the case {p=m, \theta=\pi}), and focus only on the rotations by angles less than {\pi}, we in fact see that the origin {p} of the rotation depends in a linear fashion on the quantity {\cot \frac{\theta}{2}}. Thus, if we parameterise (most of) {SE(2)} by the coordinates {(p, \cot \frac{\theta}{2}) \in {\bf R}^3}, we thus see that we can view each {\ell_{x \rightarrow y}} as a line in {{\bf R}^3}, and we will adopt this perspective for the rest of this post.

[I do not know if there is any higher explanation (coming, say, from Lie group theory) as to why the set of rigid motions from {x} to {y} in {{\bf R}^2} happens to form a line in {{\bf R}^3} when viewed in the appropriate coordinate system. Perhaps this is just a miraculous coincidence arising from the low-dimensional (and low-degree) nature of the problem.]

Let {{\mathcal L}} be the collection of all the lines {\ell_{x_i \rightarrow x_k} \subset {\bf R}^3} generated by pairs of points {x_i, x_k} from our collection, thus there are {\sim N^2} such lines. (It is easy to see that different pairs of points {(x_i,x_k)} lead to different lines.) The {\ggg N^3 \log N} quintuples {(x_i, x_j, x_k, x_l, R)} described earlier give rise to {\ggg N^3 \log N} intersecting pairs {\ell, \ell' \in {\mathcal L}} of lines in {{\mathcal L}}. So the question now comes down to a simple question about incidences of lines: is it possible for {\sim N^2} lines in three-dimensional space {{\bf R}^3} to generate {\ggg N^3 \log N} pairs {\ell, \ell'} of intersecting lines? If the answer to this question is “no”, then we are done.

Unfortunately, the answer to the question is “yes”. One quickly comes up with two basic counterexamples to that question:

  1. (Concurrency) If one has {\sim N^2} lines that all go through the same point {p}, then we will have {\sim N^4} pairs of intersecting lines.
  2. (Coplanarity) If one has {\sim N^2} lines that all lie in the same plane {\pi}, with no two lines being parallel, then we will have {\sim N^4} pairs of intersecting lines.

Slightly less obviously, there is a third counterexample that comes from a regulus (or hyperbolic paraboloid) – a doubly ruled surface in {{\bf R}^3}. A typical example of a regulus is the set {\{ (x,y,z) \in {\bf R}^3: z = xy \}}. On the one hand, this surface is ruled by the lines {\{ (x,y,xy): y \in {\bf R} \}} for {x \in {\bf R}}; on the other hand, it is also ruled by the lines {\{ (x,y,xy): x \in {\bf R} \}} for {y \in {\bf R}}. If we then pick {\sim N^2} lines from the first family of lines and {\sim N^2} from the second family, then we obtain another family of {\sim N^2} lines that lead to {\sim N^4} pairs of intersecting lines.

However, all is not lost here, because we are not dealing with an arbitrary family {{\mathcal L}} of {\sim N^2} lines in {{\bf R}^3}, but rather with a special family that was generated ultimately by {N} points {x_1,\ldots,x_N} in {{\bf R}^2}. As such, the special structure of this family can be used to rule out the concurrency, coplanarity, and regulus counterexmaples. Indeed, observe that if a rigid motion {R} maps {x_i} to {x_j}, then it cannot also map {x_i} to {x_k} for some {k \neq j}. This implies that {\ell_{x_i \rightarrow x_j}} and {\ell_{x_i \rightarrow x_k}} cannot intersect. This limits the amount of concurrency in {{\mathcal L}}; letting {i} run from {1} to {N}, we indeed conclude that at most {N} lines in {{\mathcal L}} can meet at a point, which eliminates the concurrency counterexample. (Now, the best one can do is get {\sim N} groups of {N} concurrent lines, but this only yields {\sim N^3} pairs of intersecting lines, which is acceptable.)

In a similar spirit, observe that for a given plane {\pi}, the requirement that a line in {{\bf R}^3} lie in that plane is a codimension two constraint on that line (the space of lines in a plane is two-dimensional, while the space of lines in {{\bf R}^3} is four-dimensional). Thus, for fixed {x_i}, the requirement that {\ell_{x_i \rightarrow x_j}} lie in {\pi} is a codimension two constraint on {x_j}, and thus by Bezout’s theorem, it should only be satisfiable by {O(1)} values of {x_j}. (One has to check that the constraints are non-degenerate, but this is routine; actually, in this particular case one can also argue directly using elementary Euclidean geometry.) Letting {i} run from {1} to {N}, we conclude that any plane {\pi} can contain at most {O(N)} lines from {{\mathcal L}}, thus neutralising the coplanarity counterexample. The same argument also shows that any regulus also can contain at most {O(N)} lines from {{\mathcal L}} (because a regulus is an algebraic surface of degree {2}, and so the Bezout argument still applies).

Now, it turns out that the elimination of the concurrency, coplanarity, and regulus obstructions allows us to now give the right answer to the previous question. Indeed, Guth and Katz show

Theorem 4 Let {{\mathcal L}} be a collection of {\sim N^2} lines in {{\bf R}^3}, such that at most {N} lines in {{\mathcal L}} meet at a point, and such that any plane or regulus contains at most {O(N)} lines in {{\mathcal L}}. Then there are at most {O(N^3 \log N)} pairs {\ell, \ell' \in {\mathcal L}} of intersecting lines in {{\mathcal L}}.

The above discussion has shown (modulo a few details) that Theorem 4 implies Theorem 2, so it suffices now to show Theorem 4. This is a significant simplification, because it is an assertion about incidences of lines, rather than congruence of line segments or incidences of circles, and we know a lot more about how configurations of lines intersect than we do about configurations of circles or of congruences of line segments.

Of course, it remains to prove Theorem 4. It is convenient to pigeonhole based on the concurrency of the lines in {{\mathcal L}}. Let {k \geq 2}, and suppose that has a set of points {S}, such that for each point {p} in {S} there are at least {k} lines in {{\mathcal L}} passing through {p}. From the concurrency bound we know that {k \leq N}. Then each point in {p} contributes {\sim k^2} pairs of intersecting lines, so we need to show that {P} does not get much larger than {N^3/k^2}. And indeed this is the case:

Theorem 5 Let {{\mathcal L}} be a collection of {\sim N^2} lines in {{\bf R}^3}, such that any plane or regulus contains at most {O(N)} lines in {{\mathcal L}}. Let {2 \leq k \leq N}, and let {S} be a set of points, each of which has at least {k} lines in {{\mathcal L}} passing through it. Then {|S| \ll N^3/k^2}.

A simple dyadic summation argument allows one to deduce Theorem 4 from Theorem 5. (Note that the case {k=1} is not relevant, as such points do not contribute any pairs of intersecting lines.) The hypothesis that each plane or regulus contains at most {O(N)} lines, incidentally, is very reminiscent of the Wolff axiom in the work on the Kakeya conjecture.

It is worth noting that the bound in Theorem 5 is completely sharp. Indeed, consider two parallel grids

\displaystyle \{ (i,j,0) \in {\bf Z}^2 \times \{0\}: 1 \leq i,j \leq \sqrt{N} \}

and

\displaystyle \{ (i,j,1) \in {\bf Z}^2 \times \{0\}: 1 \leq i,j \leq \sqrt{N} \}

and let {{\mathcal L}} be the set of lines connecting a point in the first grid to a point in the second grid. Then one can verify that {{\mathcal L}} obeys the required hypotheses for Theorem 5, and a number-theoretic calculation shows that for any {2 \leq k \ll N}, the number of points in {{\bf R}^3} that are incident to at least {k} lines in {{\mathcal L}} is {\sim N^3/k^2}. (To see this, first look at the cases {k=2} and {k \sim N^2}, and then interpolate the arguments; details are given in the Guth-Katz paper.)

It is also worth noting that if one replaces the real line {{\bf R}} by a finite field {{\bf F}_q}, then the claim fails for large {k}. Indeed, if one sets {N = q^2} and {{\mathcal L}} to be the set of all lines in {{\bf F}_q^3}, then the hypotheses of Theorem 5 hold, but each of the {q^3} points in {{\bf F}_q^3} is incident to {\sim q^2} lines in {{\mathcal L}}, which soon leads to a significant violation of the conclusion of that theorem. Thus, any proof of Theorem 5 in the large {k} case cannot be purely algebraic in nature must somehow use a property of the real line that is not shared by finite fields. This property will be the ordered nature of the real line, which manifests itself in the Szemerédi-Trotter theorem and in the ham sandwich theorem, both of which are used in the proof. However, this example does not prevent the small {k} case from being purely algebraic.

So, the only thing left to do is to prove Theorem 5. It turns out that the multiplicity {2} case {k=2} and the higher multiplicity case {k > 2} have to be treated separately, basically because {k} concurrent lines will be trapped in a plane when {k=2}, but will usually not be so trapped when {k>2}. Also, note that the regulus obstruction only generates intersections of multiplicity {2}; when {k>2}, the hypothesis that a regulus contains {O(N)} points is not used and so can be dropped.

— 2. The {k=2} case —

We first verify Theorem 5 in the {k=2} case, i.e. we show that the lines {{\mathcal L}} in that theorem can intersect in at most {O(N^3)} points. As hinted in the previous discussion, the argument here is purely algebraic in nature, using just the polynomial method (similar to, say, how Dvir proved the finite fields Kakeya conjecture, as discussed in this previous blog post). As such, the {k=2} result in fact holds over an arbitrary field, but we will stick to {{\bf R}} for sake of notational consistency.

The polynomial method rests on two basic facts:

  1. Given a set {S} of points in {{\bf R}^3}, there is a non-trivial polynomial {P: {\bf R}^3 \rightarrow {\bf R}} of degree {O(|S|^{1/3})} that vanishes at all of these points simultaneously.
  2. If a polynomial {P: {\bf R}^3 \rightarrow {\bf R}} of degree at most {d} vanishes on more than {d} points of a line {\ell}, then it must in fact vanish on all of {\ell}.

Both facts are easy to prove (see e.g. this previous blog post). But, as we will see, they have to be applied carefully in order to obtain a good estimate.

Suppose for sake of contradiction that we can find a set {S} of points in {{\bf R}^3} of cardinality {|S| \gg N^3} such that each point in {S} is incident to at least two lines from {{\mathcal L}}. The strategy is then to use Fact 1 find a low-degree polynomial {P} that vanishes on {S}, so that {S} is contained in the low-degree surface {\Sigma := \{ x \in {\bf R}^3: P(x)=0\}}. This surface {\Sigma} is not necessarily irreducible; it may be the union of several irreducible subsurfaces. By the nature of {S}, there will be lots of lines in {{\mathcal L}} that intersect this surface {\Sigma} quite frequently; by Fact 2, this should force the lines to be trapped inside {\Sigma}. Thus we have a low-degree surface {\Sigma} that contains a lot of lines. Hopefully, this forces many of the irreducible components of {\Sigma} to be singly ruled surfaces, doubly ruled surfaces, or planes. The latter two cases cannot contain too many lines in {{\mathcal L}} by hypothesis, so we expect the dominant family of lines in {{\mathcal L}} to be those coming from the singly ruled surfaces. But one can use Bezout-type theorems to control the number of times lines from one singly ruled surface of controlled degree can intersect lines from another such surface, and hopefully this gives the desired {O(N^3)} bound for {P}.

Let’s now execute this strategy. Fact 1 gives a non-trivial polynomial {P} of degree {O(|S|^{1/3})} that vanishes at all the points in {S}. This turns out to be too large of a degree bound to close the argument. The problem is that the set of points {S} that we want to apply this fact to is not completely arbitrary; in fact, by its nature, many points in {S} are going to be collinear (because each point in {S} is incident to at least two lines from {{\mathcal L}}), and so heuristically many of these points in {S} are in fact “redundant” for the purposes of finding a polynomial that vanishes on all of {S}.

We can handle this by the “random refinement” trick. Let us write {|S| = Q N^3} for some {Q \ggg 1}. Each of these {Q N^3} points is incident to two lines in {{\mathcal L}}; as there are {\sim N^2} lines in {{\mathcal L}}, we thus expect each line in {{\mathcal L}} to be incident to {\sim QN} points in {S}. (Actually, what could happen more generally is that only a fraction of the lines in {{\mathcal L}}, say {\alpha N^2} lines for some {0 < \alpha \leq 1}, are contributing the bulk of the incidences, with each line being incident to about {\sim QN/\alpha} points in {S}; but let us consider the {\alpha=1} case here for simplicity, as it is the worst case, and the other cases are similar but require a bit more bookkeeping.)

Now, let us destroy some of this collinearity by taking a random subset {S'} of {S} of density about {1/Q}. Then {S'} will have size about {N^3}, and each line in {{\mathcal L}} is now expected to be incident to {O(N)} elements of {S'}. We apply Fact 1 to get a non-trivial polynomial {P} of degree {O(N)} that vanishes at every point in {S'}. Applying Fact 2 (and assuming that certain constants were chosen properly), this implies that {P} also vanishes at every line in {{\mathcal L}}, and thus also at every point in {S}. This should be contrasted with what would have happened if we applied Fact 1 to {S} directly, giving a degree bound of {O(Q^{1/3} N)} rather than {O(N)}.

So now we have a surface {\Sigma := \{ x \in {\bf R}^3: P(x)=0\}} of degree {O(N)} that contains all the {\sim N^2} lines in {{\mathcal L}}. We split this surface into irreducible components. These components may be planes, reguli, singly ruled surfaces, or not ruled at all. To simplify things let us just consider four extreme cases:

  1. {\Sigma} consists of the union of planes.
  2. {\Sigma} consists of the union of reguli.
  3. {\Sigma} consists of the union of singly ruled surfaces.
  4. {\Sigma} consists of the union of non-ruled surfaces.

(For the full proof, one also has to consider hybrid cases in which more than one of the above four types appear, and so there are some cross-terms to deal with, but these are relatively easy to control and will not be discussed here.)

In the first case, degree considerations tell us that there are at most {O(N)} planes, and by hypothesis each of them contains {O(N)} lines in {{\mathcal L}}. Within each plane, there are at most {O(N^2)} points of intersection, and between any two planes {\pi_1, \pi_2}, all points of intersection must lie in the common line {\pi_1 \cap \pi_2}, which is incident to the {O(N)} lines of {{\mathcal L}} in {\pi_1, \pi_2} in at most {O(N)} points. Adding this all together we get at most {O(N^3)} points of intersection, which is acceptable.

A similar argument (which we omit) handles the second case, so we move on to the third case. Let’s assume for simplicity that each singly ruled surface has the same degree {d}; since the total degree of {\Sigma} is {O(N)}, we must then have at most {O(N/d)} such surfaces. In a singly ruled surface {\Gamma}, all but {O(1)} of the lines in {\Gamma} will come from the single ruling of {\Gamma} (i.e. all but {O(1)} of the lines will be generators); the contribution of these exceptional lines is negligible (as there at most {O(N)} such lines in all, leading to {O(N^3)} points of intersection) and we shall simply ignore them. There are two remaining types of intersection to consider; the intersections between two lines from the same ruling of a single ruled surface, and the intersections from lines that do not lie in the same ruled surface.

For the first type of intersection, one can show that in a ruled surface of degree {d}, any line in the ruling can intersect the other lines in the ruling in at most {O(d)} points. So the total number of intersections arising in this way is {O(N^2 d)}; since {d = O(N)}, this is acceptable.

To handle the second type of intersection, observe that any line not incident to a ruled surface {\Gamma} can intersect {\Gamma} at most {O(d)} times; summing over the {O(N/d)} surfaces {\Gamma} and the {O(N^2)} lines in {{\mathcal L}} we obtain at most {O(N^3)} incidences, as desired.

Finally, we consider the fourth case, where there are no ruled surfaces anywhere in {\Sigma}. Here, one uses an algebraic observation of Cayley that classifies ruled surfaces by a bounded number of algebraic conditions:

Proposition 6 A surface {\Gamma} is ruled if and only if, for every point {p} in {\Gamma}, there exists a line {\ell_p} through {p} that is tangent to {\Gamma} to order three (thus, if {P} is a defining function for {\Gamma}, there exists a non-zero vector {v} such that {P(p) = D_v P(p) = D_v^2 P(p) = D_v^3 P(p) = 0}).

The “only if” direction is obvious, but what we need here is the more difficult “if” operation. The basic idea is to show (e.g. by using the Picard uniqueness theorem for ODE) that the foliation induced by the tangent lines {\ell_p} consist entirely of straight lines, thus giving the desired ruling of {\Sigma}. The precise order of vanishing is not required for this argument; any bounded number instead of three would suffice here. (I would be interested to know that if there was a slick, computation-free proof of the above proposition, perhaps using a larger order of vanishing than three.)

The condition that there exists a non-zero vector {v \in {\bf R}^3} such that {D_v P(p)= D_v^2 P(p) = D_v^3 P(p)=0} can be combined by elementary elimination theory (or high school algebra, for that matter) into a single algebraic condition {FL(P)(p)=0} on {p}, where {FL(P)} is a polynomial of degree {O( \hbox{deg}(P) )} known as the flecnode polynomial of {P}. If {\Sigma := \{ x: P(x) = 0 \}} contains no ruled surfaces, then the above proposition tells us that the flecnode polynomial {FL(P)} shares no common factors with {P}.

On the other hand, if {\ell} is a line in {{\mathcal L}} oriented in the direction {v}, and {p} is a point in {{\mathcal L}}, then {\ell} lies in {\Sigma}, and thus {P(p) = D_v P(p)= D_v^2 P(p) = D_v^3 P(p)=0}. Thus we see that each line {\ell} in {{\mathcal L}} is contained in the zero locus of both {P} and its flecnode polynomial {FL(P)}. However, by applying Bezout’s theorem to a generic two-dimensional slice of {{\bf R}^3}, we see that the zero locus of {P} and of {FL(P)} can only intersect in {O( \hbox{deg}(P) \times \hbox{deg}(FL(P)) ) = O( \hbox{deg}(P)^2 )} lines at most. But if we chose the constants correctly, this number will be less than the number of lines in {{\mathcal L} \sim N^2}, leading to the required contradiction.

— 3. The {k>2} case —

Now we turn to the {k>2} case. Our starting point here will be the Szemerédi-Trotter theorem, which asserts that given a finite set {P} of points and a finite set {L} of lines, the number of incidences {|I(P,L)| := |\{ (p,\ell) \in P \times L: p \in \ell \}|} is bounded by

\displaystyle |I(P,L)| \ll |P|^{2/3} |L|^{2/3} + |P| + |L|.

The theorem is usually stated in the plane {{\bf R}^2}, but it automatically extends to higher dimensions, and in particular to {{\bf R}^3}, by a random projection argument. This theorem can be proven by crossing number methods (as discussed in this previous blog post) or by cell decomposition (as discussed in this previous blog post). In both cases, the order structure of {{\bf R}} (and in particular, the fact that a line divides a plane into two half-planes) is crucial. But we will not need to know the proof of this theorem, instead using it as a black box.

An easy corollary of this theorem is that if {L} is a family of lines, {P} is a family of points, and {2 \leq k \ll |L|^{1/2}} is such that each point in {P} is incident to at least {k} points in {L}, then

\displaystyle |P| \ll |L|^2/k^3. \ \ \ \ \ (1)

If one applies this bound directly to our situation, we obtain the bound {|P| \ll N^4/k^3}, which is inferior to the desired bound {|P| \ll N^3/k^2}. Actually, it is not surprising that we get an inferior bound, because we have not yet exploited the crucial non-coplanarity hypothesis.

However, it is possible to amplify the Szemerédi-Trotter bound by the method of cell decomposition. As discussed in this previous blog post, the idea is to carefully carve up the ambient space (which, in this case, is {{\bf R}^3}) into smaller regions or “cells”, each of which only contains a small fraction of the points {P} and which encounters only a small fraction of the lines {L}. One then applies an existing bound (in this case, (1)) to each cell, and sums up over all cells to get what should presumably be a better bound (where the key point being that the cells should be constructed in such a way that each line only encounters a small fraction of the cells).

There is however a catch to this method: if one creates too many cells, then one starts running into the problem that too many points in {P} and too many lines in {L} will now lie on the boundary of the cell, rather than in the interior. So one has to carefully optimise the complexity of the cell decomposition.

In previous literature, the most popular way to create cells was by a random construction, for instance using randomly chosen points and lines from {P} and {L} to create planes, which one then uses to slice up space into polytope cells, possibly with an additional non-random “cleanup” stage to remove some degeneracies or other potential difficulties in the cell structure. One of the key innovations in the Guth-Katz paper is to instead create cells via the polynomial method, and specifically by the polynomial Ham Sandwich theorem. This allows for a very efficient and even cell decomposition; the walls of the cell will no longer be flat planes, but will still be algebraic sets of controlled degree, and this turns out to be good enough for the application at hand. This is inspired by previous applications of the polynomial ham sandwich theorem to incidence geometry problems, as discussed in this previous blog post.

Let us first recall the polynomial ham sandwich theorem (for three dimensions), which one can think of as a continuous version of Fact 1 from the previous section:

Theorem 7 (Polynomial ham sandwich theorem) Let {X_1,\ldots,X_m} be {m} bounded open sets in {{\bf R}^3}. Then there exists a non-trivial polynomial {P: {\bf R}^3 \rightarrow {\bf R}} of degree {O(m^{1/3})} such that the algebraic set {\{ x \in {\bf R}^3: P(x)=0\}} bisects each of the {X_i}, thus {\{ x \in X_i: P(x) < 0\}} and {\{ x \in X_i: P(x) > 0\}} have volume equal to half that of {X_i}.

See for instance this previous blog post for a proof of this fact (based on the Borsuk-Ulam theorem).

By taking the {X_1,\ldots,X_m} to be the {\varepsilon}-neighbourhood of finite sets {S_1,\ldots,S_m}, and sending {\varepsilon} to zero (using some basic compactness properties of the (projective) space of polynomials to extract a limit), one can conclude a useful combinatorial corollary:

Corollary 8 (Discretised polynomial ham sandwich theorem) Let {S_1,\ldots,S_m} be finite sets of points in {{\bf R}^3}. Then there exists a non-trivial polynomial {P: {\bf R}^3 \rightarrow {\bf R}} of degree {O(m^{1/3})} such that the algebraic set {\{ x \in {\bf R}^3: P(x)=0\}} bisects each of the {S_i}, in the sense that {\{ x \in S_i: P(x) < 0\}} and {\{ x \in S_i: P(x) > 0\}} each have cardinality at most {|S_i|/2}.

Note that the algebraic set {\{ x \in {\bf R}^3: P(x)=0\}} may capture some of the points of {S_i}; indeed, this is necessarily the case if {|S_i|} is odd. This possibility will need to be addressed later in the argument.

We can iterate this corollary to obtain a nice cell decomposition:

Corollary 9 (Cell decomposition) Let {S} be a finite set of points in {{\bf R}^3}, and let {m \geq 1}. Then there exists a non-trivial polynomial {P} of degree {O(m^{1/3})} and a decomposition of {\{ x \in {\bf R}^3: P(x) \neq 0 \}} into at most {O(m)} cells {C}, each of which is an open set with boundary in {\{ x \in {\bf R}^3: P(x) = 0 \}}, and each of which contains at most {O(|S|/m)} points of {S}. (We allow {C} to be disconnected.)

Proof: Without loss of generality we may take {m=2^j} to be a power of two. The proposition is trivial for {m=1}, and by using Corollary 8 it is easy to see (with the right choice of implied constants) that the claim for {m} implies the claim for {2m} (with the same implied constants), by bisecting each of the cells obtained for {m} by an additional bisecting polynomial that one then multiplies with the existing polynomial. \Box

Note that Fact 1 from the previous section can be viewed as the case {m=|S|} of the above decomposition, in which the cell walls have now absorbed all the points in {S}. But for us, the optimal value of {m} will be significantly less than {|S|}, to balance the contribution of the points on the cell walls with the points in the interior.

We now apply this situation to the situation in Theorem 5. Fix {3 \leq k \leq N}, and suppose for contradiction that we can find a set {S} of points with {|S| \ggg N^3/k^2}, with each point in {S} incident to at least {k} lines in {{\mathcal L}}.

We will apply the cell decomposition for a certain parameter {m}; it turns out that the optimal value here is {m \sim (N/k)^3}. Thus we obtain a non-trivial polynomial {P} of degree {O(N/k)}, and a collection of {O((N/k)^3)} cells, each of which contains {O((k/N)^3 |S|)} points of {S} in the interior.

By throwing away at most half of the points in {S}, we can end up in one of two extreme cases:

  1. (Cellular case) All points in {S} are in the interior of a cell.
  2. (Algebraic case) All points in {S} are in the boundary of a cell.

The cellular case becomes easier for {m} large, while the algebraic case becomes easier for {m} small; the choice {m \sim (N/k)^3} is used to balance the two cases.

Let us first consider the cellular case. Then we {\gg (N/k)^3} cells {C} will contain {\gg (k/N)^3 |S|} points of {S}. Each such point in such a cell {C} is incident to at least {k} lines from {{\mathcal L}}. Applying the Szemerédi-Trotter bound (1) inside this cell {C}, we conclude that

\displaystyle (k/N)^3 |S| \ll |{\mathcal L}_C|^2/k^3,

where {{\mathcal L}_C} is the set of lines in {{\mathcal L}} that intersect {C}. Since {|S| \ggg N^3/k^2}, we conclude that

\displaystyle |{\mathcal L}_C| \ggg k^2.

On the other hand, as {P} has degree {O(N/k)}, we see from Bezout’s theorem that each line in {{\mathcal L}} intersects {O(N/k)} cells, and so

\displaystyle \sum_C |{\mathcal L}_C| \ll (N/k) |{\mathcal L}| \ll N^3 / k.

Since the number of cells here is {\gg (N/k)^3}, we obtain

\displaystyle (N/k)^3 k^2 \lll N^3/k

which is a contradiction.

Now consider the algebraic case. We have {S} points, each incident to {k} lines from {{\mathcal L}}, which has cardinality {\sim N^2}. We thus expect each line to be incident to {\sim k|S|/N^2 \ggg N/k} points in {S}. For simplicity we will assume that every line is of this type (in reality, we would have to throw out some lines that do not intersect enough points in {S}).

By construction, all the points in {S} lie in the algebraic set {\Sigma := \{ x \in {\bf R}^3: P(x)=0\}}, which has degree {O(N/k)}. Applying Fact 2, we conclude that every line in {{\mathcal L}} is in fact trapped inside {\Sigma}.

This is now a situation fairly similar to that of the previous section. However, we now use the hypothesis that {k \geq 3} to obtain a better bound. Every point {p} in {S} has at least three lines of {{\mathcal L}} passing through it, each of which lies in {\Sigma}. This leads to two possibilities for {p}:

  1. (Singular case) {p} is a singular point of {\Sigma} (i.e. {\nabla P(p) = 0}).
  2. (Flat case) {p} is a flat point of {\Sigma} (i.e. the {p} is non-singular, but the second fundamental form of {\Sigma} vanishes at {p}).

Indeed, if {p} was non-singular, then {\Sigma} has a unique tangent plane at {p} along which at least three lines of {{\mathcal L}} are tangent; as they all lie in {\Sigma}, this forces the second fundamental form of {\Sigma} to vanish.

By throwing out at most half of the points in {S}, we may now reduce to two subcases:

  1. (Singular subcase) All points of {S} are singular points of {\Sigma}.
  2. (Flat subcase) All points of {S} are flat points of {\Sigma}.

Let us consider first the singular subcase. The points {S} are now contained in the zero locus of {P} and of {\nabla P}; the latter is an intersection of three algebraic surfaces of degree {O(N/k)}; by reducing {P} to be square-free, we can assume that {P} and {\nabla P} have no common factor. We already saw from Fact 2 that all the lines in {{\mathcal L}} were trapped in the zero locus of {P}; the same argument shows that they are also trapped in the zero locus of {\nabla P}. But by Bezout’s theorem applied to a generic two-dimensional slice of {{\bf R}^3} (as was done in the previous section, using {FL(P)} instead of {\nabla P}), we see that the zero locus of {P} and {\nabla P} can intersect in at most {O( N/k) \times O(N/k)} lines, which will contradict the bound {|{\mathcal L}| \sim N^2} if the constants are chosen properly.

Now we turn to the flat subcase. Just as the three polynomial components {\partial_{e_1} P, \partial_{e_2} P, \partial_{e_3} P} of {\nabla P} detects singular points of {\Sigma}, there are nine polynomials that detect flat points of {\Sigma}, namely the components {Q_{i,j}} of the three-dimensional vector fields

\displaystyle Q_i := (D_{e_i \times \nabla P} \nabla P) \times \nabla P

for {i,j=1,2,3}. All nine polynomials {Q_{i,j}} vanish at a flat point. (This observation was also used in a previous paper of Guth and Katz in which they solve the joints problem.)

The argument for the singular subcase almost carries over without difficulty to the flat subcase, but there is one problem: it is not necessarily the case that {P} does not share a common factor with the {Q_{i,j}}, so that we cannot quite apply the Bezout argument immediately. Indeed, {P} could contain a plane, which of course consists entirely of flat points. However, if {P} has no planes, then the set of flat points has positive codimension, and the argument proceeds as before. At the other extreme, if {P} consists entirely of planes, then by degree considerations there are at most {O(N/k)} planes present. But by hypothesis, each plane contains at most {O(N)} lines from {{\mathcal L}}. Since {|{\mathcal L}| \sim N^2}, this leads to a contradiction (if the implied constants are chosen correctly). The general case (in which {P} has some planes, but does not consist entirely of planes) can be established by combining the previous two arguments properly.