Jozsef Solymosi and I have just uploaded to the arXiv our paper “An incidence theorem in higher dimensions“, submitted to Discrete and Computational Geometry. In this paper we use the polynomial Ham Sandwich method of Guth and Katz (as discussed previously on this blog) to establish higher-dimensional versions of the Szemerédi-Trotter theorem, albeit at the cost of an epsilon loss in exponents.

Recall that the Szemerédi-Trotter theorem asserts that given any finite set of points {P} and lines {L} in the plane {{\bf R}^2}, the number of incidences {I(P,L) := \{ (p,\ell) \in P \times L: p \in \ell \}} has the upper bound

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

Apart from the constant factor, this bound is sharp. As discussed in this previous blog post, this theorem can be proven by the polynomial method, and the strategy can be rapidly summarised as follows. Select a parameter {D \geq 1}. By the polynomial Ham Sandwich theorem, one can divide {{\bf R}^2} into {O(D^2)} cell interiors, each with {O(|P|/D^2)} points, and incident to {O(|L|/D)} lines on the average, plus a boundary set which is an algebraic curve of degree {O(D)}. To handle the contribution of each cell interior, one uses a more elementary incidence bound (such as the bound {|I(P,L)| \ll |P| |L|^{1/2} + |L|} coming from the fact that two points determine at most one line); to handle the contribution on the cell boundary, one uses algebraic geometry tools such as Bezout’s theorem. One then combines all the bounds and optimises in {D} to obtain the result.

As a general rule, the contribution of the cell interiors becomes easier to handle as {D} increases, while the contribution of the cell boundaries become easier as {D} decreases. As such, the optimal value of {D} is often an intermediate one (in the case of Szemerédi-Trotter, the choice {D = |P|^{2/3} |L|^{-1/3}} is typical). Among other things, this requires some control of moderately high degree algebraic sets, though in this planar case {{\bf R}^2}, one only needs to control algebraic curves in the plane, which are very well understood.

In higher dimensions, though, the complexity of the algebraic geometry required to control medium degree algebraic sets increases sharply; compare for instance the algebraic geometry of ruled surfaces appearing in the three-dimensional work of Guth and Katz as discussed here, compared with the algebraic geometry of curves in the two-dimensional Szemerédi-Trotter theorem discussed here.

However, Jozsef and I discovered that it is also possible to use the polynomial method with a non-optimised value of {D}, and in particular with a bounded value {D=O(1)} of {D}, which makes the algebraic geometry treatment of the boundary significantly easier. The drawback to this is that the cell interiors can no longer be adequately controlled by trivial incidence estimates. However, if instead one controls the cell interiors by an induction hypothesis, then it turns out that in many cases one can recover a good estimate. For instance, let us consider the two-dimensional Szemerédi-Trotter theorem in the most interesting regime, namely when the {|P|^{2/3} |L|^{2/3}} term on the RHS is dominant. If we perform the cell decomposition with some small parameter {D}, then we obtain {O(D^2)} cells with {O(|P|/D^2)} points and {O(|L|/D)} lines on the average; applying the Szemerédi-Trotter theorem inductively to each of these cells, we end up with a total contribution of

\displaystyle O( D^2 ) \times O( |P|/D^2)^{2/3} \times O( |L|/D)^{2/3} = O( |P|^{2/3} |L|^{2/3} )

for the cell interiors, and so provided that one can also control incidences on the (low degree) cell boundary, we see that we have closed the induction (up to changes in the implied constants in the {O()} notation).

Unfortunately, as is well known, the fact that the implied constants in the {O()} notation degrade when we do this prevents this induction argument from being rigorous. However, it turns out this method does work nicely to give the weaker incidence bound

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

for any fixed {\epsilon > 0}; the point being that this extra epsilon of room in the exponents means that the induction hypothesis gains a factor of {D^{-\epsilon}} or so over the desired conclusion, allowing one to close the induction with no loss of implied constants if all the parameters are chosen properly. While this bound is weaker than the full Szemerédi-Trotter theorem, the argument is simpler in the sense that one only needs to understand bounded degree algebraic sets, rather than medium degree algebraic sets. As such, this argument is easier to extend to higher dimensions.

Indeed, as a consequence of this strategy (and also a generic projection argument to cut down the ambient dimension, as used in this previous paper with Ellenberg and Oberlin, and an induction on dimension), we obtain in our paper a higher-dimensional incidence theorem:

Theorem 1 (Higher-dimensional Szemerédi-Trotter theorem) Let {d \geq 2k}, and let {P} and {L} be finite sets of points and {k}-planes in {{\bf R}^d}, such that any two {k}-planes in {L} intersect in at most one point. Then we have {|I(P,L)| \ll_{k,\epsilon} |P|^{2/3+\epsilon} |L|^{2/3} + |P| + |L|} for any {\epsilon > 0}.

Something like the transversality hypothesis that any two {k}-planes in {L} intersect in at most one point is necessary, as can be seen by considering the example in which the points {P} are all collinear, and the {k}-planes in {L} all contain the common line. As one particular consequence of this result, we recover (except for an epsilon loss in exponents) the complex Szemerédi-Trotter theorem of Toth, whose proof was significantly more complicated; it also gives some matrix and quaternionic analogues, in particular giving new sum-product theorems in these rings. Note that the condition {d \geq 2k} is natural, because when the ambient dimension is less than {2k}, it is not possible for two {k}-planes to intersect in just one point. Using the generic projection trick, one can easily reduce to the critical case {d=2k}.

Actually, for inductive reasons, we prove a more general result than Theorem 1, in which the {k}-planes are replaced instead by {k}-dimensional real algebraic varieties. The transversality condition is now that whenever a point {p} is incident to two such varieties {\ell, \ell'}, that the tangent cones of {\ell} and {\ell'} at {p} only intersect at {p}. (Also for technical reasons, it is convenient to consider a partial subset {{\mathcal I}} of incidences in {I(P,L)}, rather than the full set of incidences. Indeed, it seems most natural to consider the triplet

\displaystyle \begin{array}{ccccc} \\ && {\mathcal I} && \\ & \swarrow & & \searrow & \\ P & & & & L \end{array}

as a single diagram, rather than to consider just the sets {P} and {L}.)

The reason for working in this greater level of generality is that it becomes much easier to use an induction hypothesis to deal with the cell boundary; one simply intersects each variety {\ell} in {L} with the cell boundary, which usually lowers the dimension of the variety by one. (There are some exceptional cases in which {\ell} is completely trapped inside the boundary, but due to the transversality hypothesis, this cannot contribute many incidences if the ambient dimension is {2k} (so the cell boundary is only {2k-1} dimensional).)

As one application of this more general incidence result, we almost extend a classic result of Spencer, Szemerédi, and Trotter asserting that {n} points in the plane {{\bf R}^2} determine {O(n^{4/3})} unit distances from {{\bf R}^2} to {{\bf C}^2}, at the cost of degrading {O(n^{4/3})} to {O_\epsilon(n^{4/3+\epsilon})}.