An Incidence Theorem in Higher Dimensions

Abstract

We prove almost tight bounds on the number of incidences between points and k-dimensional varieties of bounded degree in R ^d. Our main tools are the polynomial ham sandwich theorem and induction on both the dimension and the number of points.

1 Introduction

Given a collection P of points in some space, and a collection L of sets in that same space, let I(P,L):={(p,ℓ)∈P×L:p∈ℓ} be the set of incidences. One of the objectives in combinatorial incidence geometry is to obtain good bounds on the cardinality |I(P,L)| on the number of incidences between finite collections P,L, subject to various hypotheses on P and L. For instance, we have the classical result of Szemerédi and Trotter [48]:

Theorem 1.1

(Szemerédi–Trotter Theorem [48])

Let P be a finite set of points in R ^d for some d≥2, and let L be a finite set of lines in R ^d. Then

$$ \bigl|I(P,L)\bigr| \leq C\bigl( |P|^{2/3}|L|^{2/3} +|P| + |L| \bigr)$$

(1.1)

for some absolute constant C.

This theorem is usually stated in the two-dimensional setting d=2, but the higher-dimensional case is an immediate consequence by applying a generic projection from R ^d to R ² (see Sect. 5.1 for a discussion of this argument). It is known that this bound is sharp except for the constant C; see [48].

Various mathematical problems can be transformed to a question about incidence bounds of Szemerédi–Trotter-type. For instance, Elekes [11] used the above theorem in an unexpected fashion to obtain new bounds on the sum-product problem. In the 1990s, Wolff [53] observed that bounds on the number of incidences might be used in problems related to the Kakeya conjecture, one of the central conjectures in harmonic analysis. Bennett, Carbery and Tao [6] established a connection between multilinear Kakeya estimates and bounds on number of incidences between points and lines in three dimensions. Very recently, Guth and Katz [18] used bounds on the number of incidences between points and lines in three dimensions as part of their solution to the Erdős Distinct Distances Problem. They used an important tool, the so-called polynomial ham sandwich theorem. This theorem will be a crucial part of this paper as well. The applicability of the polynomial ham sandwich theorem to Szemerédi–Trotter-type theorems was also recently emphasized in [25].

Further applications of Szemerédi–Trotter-type incidence bounds in mathematics and theoretical computer science, as well as several open problems, are discussed in the surveys and books of Elekes [12], Székely [47], Pach and Sharir [36], Brass, Moser, and Pach [7], and Matoušek [29].

In the survey [12], Elekes listed some nice applications of point-line incidence bounds in the complex plane ℂ², where the lines are now complex lines (and thus are also real planes). In this paper he referred to a (then) recent result of Tóth [52] which proves the point-line incidence bound (1.1) in this situation (with a different constant C). Up to this constant multiplier, this bound is optimal. Our argument is different from and simpler than the one in Tóth’s paper; however, the bounds in this paper are slightly weaker than those in [52].

The main goal of our paper is to establish near-sharp Szemerédi–Trotter-type bounds on the number of incidences between points and k-dimensional algebraic varieties in R ^d for various values of k and d, under some “pseudoline” hypotheses on the algebraic varieties; see Theorem 2.1 for a precise statement. In particular, we obtain near-sharp bounds for point-line incidences in ℂ², obtaining a “cheap” version of the result of Tóth mentioned previously.

Our argument is based on the “polynomial method” as used by Guth and Katz [18], combined with an induction on the size of the point set P. The inductive nature of our arguments causes us to lose an arbitrarily small epsilon term in the exponents, but the bounds are otherwise sharp.

As in [18], our arguments rely on an efficient cell decomposition provided to us by the polynomial ham sandwich theorem (see Corollary 5.3). However, the key innovation here, as compared to the arguments in [18], is that this decomposition will only be used to partition the point set into a bounded number of cells, rather than a large number of cells. (Similar recursive space partitioning techniques were used by Agarwal and Sharir [1].) This makes the contribution of the cell boundaries much easier to handle (as they come from varieties of bounded degree, rather than large degree). The price one pays for using this milder cell decomposition is that the contribution of the cell interiors can no longer be handled by “trivial” bounds. However, it turns out that one can use a bound coming from an induction hypothesis as a substitute for the trivial bounds, so long as one is willing to concede an epsilon factor in the inductive bound. This technique appears to be quite general, and suggests that one can use induction to significantly reduce the need for quantitative control of the geometry of high-degree algebraic varieties when applying the polynomial method to incidence problems, provided that one is willing to lose some epsilons in the final bounds.

Our results have some similarities with existing results in the literature; we discuss these connections in Sect. 2.2.

Notation

We use the usual asymptotic notation X=O(Y) or X≪Y to denote the estimate X≤CY for some absolute constant C. If we need the implied constant C to depend on additional parameters, we indicate this by subscripts, thus for instance X=O _d (Y) or X≪ _d Y denotes the estimate X≤C _d Y for some quantity C _d depending on d.

2 Main Theorem

In what follows we are going to use some standard notations and definitions from algebraic geometry. In Sect. 4 we provide the basic definitions and tools we will need from algebraic geometry, although this is only the barest of introductions and we refer the reader to standard textbooks like [16, 20, 21, 32] (or general reference works such as [15, 22]) for a detailed treatment.

Our main result (proven in Sect. 5) is as follows.

Theorem 2.1

(Main Theorem)

Let k,d≥0 be integers such that d≥2k, and let ε>0 and C ₀≥1 be real numbers. Let P be a finite collection of distinct points in  R ^d, let L be a finite collection of real algebraic varieties in R ^d, and let ${\mathcal{I}}\subset I(P,L)$ be a set of incidences between P and L. Assume the following “pseudoline-type” axioms:

• (i) For each ℓ∈L, ℓ is a real algebraic variety, which is the restriction to R ^d of a complex algebraic variety ℓ _ℂ of dimension k and degree at most C ₀.

• (ii) If ℓ,ℓ′∈L are distinct, then there are at most C ₀ points p in P such that $(p,\ell), (p,\ell') \in{\mathcal{I}}$.

• (iii) If p,p′∈P are distinct, then there are at most C ₀ varieties ℓ in L such that $(p,\ell), (p',\ell) \in {\mathcal{I}}$. (Note that for C ₀=1, this is equivalent to (ii).)

• (iv) If $(p,\ell) \in{\mathcal{I}}$, then p is a smooth (real) point of ℓ, with a real tangent space. In other words, for each $(p,\ell)\in{\mathcal{I}}$, there is a unique tangent space T _p ℓ of ℓ at p, which is a k-dimensional real affine space containing p.

• (v) If ℓ,ℓ′∈L are distinct, and p∈P are such that $(p,\ell), (p,\ell') \in{\mathcal{I}}$, then the tangent spaces T _p ℓ and T _p ℓ′ are transverse, in the sense that they only intersect at p.

Then one has

$$ |{\mathcal{I}}| \leq A |P|^{\frac{2}{3}+\varepsilon}|L|^{\frac{2}{3}} +\frac{3}{2}|P| + \frac{3}{2} |L|$$

(2.1)

for some constant $A = A_{k,\varepsilon,C_{0}}$ that depends only on the quantities k,ε,C ₀.

Remark 2.2

The condition d≥2k is natural, as we expect the tangent spaces T _p ℓ, T _p ℓ′ in Axiom (v) to be k-dimensional;¹ if d<2k, such spaces cannot be transverse in R ^d. As we will see shortly, the most interesting applications occur when d=2k and k≥1, with C ₀ being an extremely explicit constant such as 1, 2, or 4, the varieties in L being smooth (e.g. lines, planes, or circles), and the incidences ${\mathcal{I}}$ comprising all of I(P,L); but for inductive reasons it is convenient to consider the more general possibilities for d, k, C ₀, L, and ${\mathcal{I}}$ allowed by the above theorem. The constants $\frac{3}{2}$ could easily be replaced in the argument by any constant greater than 1. We choose the constant here to be less than 2 so that the bound (2.1) can be used to control r-rich points and lines for r as low as 2 (though in that particular case, the trivial bounds in Lemma 5.1 already suffice).

In Sect. 3 we will sketch a simplified special case of the above theorem which can be proven using less of the machinery from algebraic geometry; it is conceivable that many of our applications can be handled by this simpler method. On the other hand we expect that there are further applications where the whole generality of our result is needed.

2.1 Applications

Suppose we specialize Theorem 1.1 to the case when the varieties in L are k-dimensional affine subspaces, such that any two of these subspaces meet in at most one point. Then one easily verifies that Axioms (i)–(v) hold with C ₀=1 and ${\mathcal{I}}:=I(P,L)$. We conclude:

Corollary 2.3

(Cheap Szemerédi–Trotter for k-Flats)

Let ε>0, k≥1, and d≥2k. Then there exists a constant A=A _ε,k >0 such that

$$ \bigl|I(P,L)\bigr| \leq A |P|^{2/3+\varepsilon}|L|^{2/3} +\frac{3}{2}|P| + \frac {3}{2} |L|$$

(2.2)

whenever P is a finite set of points in R ^d, and L is a finite set of k-dimensional affine subspaces in R ^d, such that any two distinct spaces in L intersect in at most one point.

Except for the ε loss, this answers a conjecture of Tóth [52, Conjecture 3] affirmatively. The hypothesis d≥2k can be dropped for the trivial reason that it is no longer possible for the k-dimensional subspaces in L to intersect each other transversely for d<2k, but of course the result is not interesting in this regime.

If r≥2, and L is a collection of k-dimensional affine subspaces, define an r-rich point to be a point that is incident to at least r subspaces in L. If we apply (2.2) to the set P of r-rich points in a standard manner, we have

$$r |P|\leq\bigl|I(P,L)\bigr| \leq A |P|^{2/3+\varepsilon} |L|^{2/3} +\frac{3}{2}|P| + \frac{3}{2} |L|.$$

As $r \geq2>\frac{3}{2}$, we may absorb the $\frac{3}{2} |P|$ term onto the left-hand side, and conclude that if L is any finite collection k-dimensional affine subspaces in R ^d, any two of which intersect in at most one point, then the number of r-rich points is $O_{\varepsilon}( \frac{|L|^{2+\varepsilon}}{r^{3}} + \frac{|L|}{r} )$ for any ε>0 and r≥2.

As special cases of Corollary 2.3, we almost recover (but for epsilon losses) the classic Szemerédi–Trotter theorem (Theorem 1.1), as well as the complex Szemerédi–Trotter theorem of Tóth [52]. More precisely, from the k=2 case of Corollary 2.3, we have

Corollary 2.4

(Cheap Complex Szemerédi–Trotter)

Let ε>0 and d≥2. Then there exists a constant A=A _ε >0 such that

$$ \bigl|I(P,L)\bigr| \leq A |P|^{2/3+\varepsilon}|L|^{2/3} +\frac{3}{2} |P| + \frac {3}{2} |L|$$

(2.3)

whenever P is a finite set of points in ℂ², and L is a finite set of complex lines in ℂ².

We will sketch a separate proof of this corollary in Sect. 3, in order to motivate the more complicated argument needed to establish Theorem 1.1 in full generality.

One can also establish the same bound for the quaternions ℍ. Define a quarternionic line to be any set in ℍ² of the form {(a,b)+t(c,d):t∈ℍ} for some a,b,c,d∈ℍ with (c,d)≠(0,0). Because ℍ is a division ring, we see that any two distinct quarternionic lines meet in at most one point. After identifying ℍ with R ⁴, we conclude:

Corollary 2.5

(Cheap Quaternionic Szemerédi–Trotter)

Let ε>0. Then there exists a constant A=A _ε >0 such that

$$ \bigl|I(P,L)\bigr| \leq A|P|^{2/3+\varepsilon} |L|^{2/3} +\frac{3}{2} |P| + \frac {3}{2} |L|$$

(2.4)

whenever P is a finite set of points in ℍ², and L is a finite set of quaternionic lines in ℍ².

We can also replace lines with circles. Define a complex unit circle to be a set of the form {(z,w)∈ℂ²:(z-z ₀)²+(w-w ₀)²=1} for some z ₀,w ₀∈ℂ. It is easy to verify that complex unit circles are real algebraic varieties in ℂ²≡R ⁴ of (real) dimension 2 and (real) degree 2×2=4 (because the real and imaginary parts of the defining equation (z-z ₀)²+(w-w ₀)²=1 are both quadratic constraints), that two complex unit circles meet in at most two points, and that two points determine at most two complex unit circles. It is possible for a point to be incident to two distinct complex unit circles in such a fashion that their tangent spaces (which are complex lines, or real planes) coincide, when the two circles are reflections of each other across their common tangent space; however, if we first pigeonhole the incidences into O(1) classes, based on the orientation of the radial vector (z-z ₀,w-w ₀) connecting the center (z ₀,w ₀) of the complex unit circle to the point (z,w), then we can eliminate these unwanted tangencies. We conclude

Corollary 2.6

(Cheap Szemerédi–Trotter for Complex Unit Circles)

Let ε>0. Then there exist constants C>0 and A=A _ε such that

$$ \bigl|I(P,L)\bigr| \leq A |P|^{2/3+\varepsilon } |L|^{2/3} + C|P| + C |L|$$

(2.5)

for all finite sets of points P and complex unit circles L in ℂ².

This gives the following application to the complex unit distance problem:

Corollary 2.7

(Complex Unit Distances)

Let ε>0. Then there exists a constant A=A _ε >0 such that

$$\bigl|\bigl\{ \bigl((z,w),\bigl(z',w'\bigr)\bigr) \in P\times P: \bigl(z-z'\bigr)^2 + \bigl(w-w'\bigr)^2 = 1 \bigr\}\bigr| \leq A_\varepsilon|P|^{\frac {4}{3}+\varepsilon}$$

for any finite set of points P in ℂ².

Indeed, this claim follows from applying (2.5) to the family L of complex unit circles with centers in P. We remark that the real-variable analogue of this result was established by Spencer, Szemerédi, and Trotter [44].

Elekes used the Szemerédi–Trotter theorem to give a good bound on the Sum-Product problem of Erdős and Szemerédi in [12]. A variant of the original Sum-Product problem was considered by Chang who proved the following in [10]. Let us suppose that ${\mathcal {A}}$ is an n-element set of k×k matrices with real coefficients such that det(A-B)≠0 for any distinct A,B elements of ${\mathcal{A}}$. Then²

$$|{\mathcal{A}}+{\mathcal{A}}|+|{\mathcal{A}} {\mathcal{A}}|\geq g\bigl(|{\mathcal{A}}|\bigr)|{\mathcal{A}}|,$$

where g(n) goes to infinity as n grows. In [49], the second author showed that g(n) grows polynomially with n.

Corollary 2.8

(Sum-Product)

Let us suppose that ${\mathcal{A}}$ is an n-element set of k×k matrices with real coefficients such that det(A-B)≠0 for any distinct A,B elements of ${\mathcal{A}}$ and V,W⊂R ^k are n-element sets of k dimensional vectors. Then for every ε>0 there exists a constant c _k,ε >0 independent of ${\mathcal{A}}$ and n such that

$$|V+W|+|{\mathcal{A}}W|\geq c n^{5/4-\varepsilon}.$$

Proof

We will apply Corollary 2.3, where the k-flats are given by $\{ (\vec{x}, \vec{y}) \in {\mathbf{R}}^{k} \times{\mathbf{R}}^{k}: \vec {y}=A(\vec{x}-\vec {v})\}$ with $\vec{v}\in V$ and $A\in\mathcal{A}$ and the points are the elements of the Cartesian product $\{V+W\}\times\{{\mathcal{A}}W\}$. Any two flats have at most one common point since det(A-B)≠0 and each of them has dimension k in the 2k-dimensional real space. Any point with coordinates $(\vec{w}+\vec{v}, A\vec{w})$ is incident to $\vec{y}=A(\vec{x}-\vec{v})$. So, we have n ² k-dimensional flats and $|V+W||{\mathcal{A}}W|$ points where each flat is incident to at least n points. We can apply Corollary 2.3 now to prove our bound. □

Remark 2.9

The same argument also applies to matrices and point sets with complex coefficients; we omit the details. In the complex case with k=1, we almost obtain the complex version of the sum-product estimate

$$|A + A| + |A \cdot A| \geq c |A|^{5/4}$$

obtained by Elekes [12], but with an epsilon loss in the exponents.

We show yet another application which is similar to the previous one. It is about r-rich affine transformations. Elekes proposed in [13] a systematic investigation of the following general problem:

… Given a group G of transformations of R ^d and a finite pointset $\mathcal{P}\subset{\mathbf{R}}^{d}$ we shall be interested in the number of transformations φ∈G which map many points of $\mathcal {P}$ to some other points of $\mathcal{P}$ …

Here we consider affine transformations in R ^d. We need some notation. An affine transformation is r-rich with respect to $\mathcal {P}$ if $|A(\mathcal{P})\cap\mathcal{P}|\geq r$. Elekes’ question is to bound the number of r-rich transformations. A finite set of affine transformations, $\mathcal{A}$ is said to be pairwise independent if A ^-1 B has at most one fixpoint for any $A,B\in\mathcal{A}$.

Corollary 2.10

(Affine Transformations)

Given an n-element pointset $\mathcal{P}\subset{\mathbf{R}}^{d}$, and let ε>0 and r≥2. Any set X of pairwise independent r-rich affine transformations has cardinality at most An ^4+ε/r ³, where A=A _ε,d >0 depends only on ε and d.

Proof

Each affine transformation in X can be written as $\vec {x}\rightarrow A\vec{x}+\vec{v}$, which we can view as a d-flat $\{(\vec{x}, \vec{y}) \in{\mathbf{R}}^{d} \times{\mathbf{R}}^{d}: \vec{y} = A\vec{x} + \vec{v}\}$ in R ^d×R ^d. Each such flat is incident to at least r points of the Cartesian product $\mathcal{P}\times\mathcal{P}$. There are |X| d-dimensional flats and n ² points where each flat is incident to at least r points. Any two flats have at most one common point since the transformations are pairwise independent (two or more common points would mean that the corresponding affine transformations are identical on a line). One can apply Corollary 2.3 again to prove the bound |X|≪n ^4+ε/r ³. □

2.2 Comparison with Existing Results

The polynomial partitioning method is not the only method to establish incidence bounds between points and varieties. In particular, there are other methods to obtain cell decompositions which can achieve a similar effect to the decomposition given by the polynomial Ham Sandwich theorem, though the hypotheses on the configuration of points and varieties can be quite different from those considered here. A model case is when the point set is assumed to be homogeneous, which roughly speaking means that the point set resembles a perturbation of a grid. In such cases one can use the cubes of the grid to form the cells. For instance, in [42] and [43] sharp incidence bounds between a homogeneous set of points and k-dimensional subspaces were given. In [27] sharp point-pseudoplane incidence bounds were proved in R ³. Similar bounds on point-surface incidences were proved for the non-homogeneous case by Zahl [54].

Elekes [13], Sharir and Welzl [40], and Guth and Katz [17] gave bounds on the number of joints. We omit the details but we should mention that the latter paper in particular uses the polynomial space partition method to give a satisfactory bound on the number of joints.

Pach and Sharir [34, 35] considered incidences between points and pseudolines in the plane—curves which obey axioms similar to Axioms (ii) and (iii) in Theorem 2.1, using crossing number inequalities. Such methods work particularly well in the plane, but are somewhat difficult to extend to higher dimensions; for some partial results in three and higher dimensions, see [3].

In the hyperplane case k=d-1, sharp incidence bounds were obtained in [14] (of course, the transversality hypothesis needs to be modified in this regime).

In [24], Fourier-analytic methods were used to obtain incidence bounds of Szemerédi–Trotter-type. In this method, the manifolds ℓ are not required to be algebraic varieties, but they are required to obey certain regularity hypotheses relating to the smoothing properties an associated generalized Radon transform (which usually forces them to be fairly high dimensional. Also, the point set P is assumed to obey a homogeneity assumption.

In [41] a simple proof was given to a Szemerédi–Trotter-type bound for incidences between complex points and lines, however, the point set is assumed to be of Cartesian product of the form A×B⊂ℂ^d.

3 A Special Case

Before we prove Theorem 2.1, we illustrate the key elements of the proof by sketching the proof of the (cheap) complex Szemerédi–Trotter Theorem which was stated earlier as Corollary 2.4. In this low-dimensional setting one can avoid an induction on dimension, instead using the crossing number machinery of Székely [46] to deal with the contribution of various lower dimensional objects. The reader who is impatient to get to the proof of the full theorem may skip this section if desired.

Let C ₁ be a large constant to be chosen later, and let C ₃ be an even larger constant (depending on C ₁) to be chosen later. (The subscripts here are chosen to conform to the notation of subsequent sections.) We will show that

$$ |{\mathcal{I}}| \leq C_3n^{2/3+\varepsilon}m^{2/3}+C_1(n+m)$$

(3.1)

for all n,m≥0 and sets P, L of points and complex lines in ℂ² with |P|=n and |L|=m, by induction on n. The claim is trivial when n=0, so suppose that n≥1, and that the claim has already been proven for smaller n.

A well-known Cauchy–Schwarz argument (based on the fact that two lines determine at most one point) gives the bounds

$$|{\mathcal{I}}| \ll n^{1/2} m + n, m^{1/2} n + m$$

(see Lemma 5.1 below). As a consequence, we may restrict attention to the regime

$$ m^{1/2} \ll n \ll m^2$$

(3.2)

for the purposes of establishing (3.1).

One can suppose that every point has at least half of the average incident lines w.l.o.g. (If a point has less than $|{\mathcal{I}}|/2m$ lines incident to it then simply remove it from P.) Then counting the points gives a lower bound on the incidences, e.g. if a region of ℂ² contains k points then there are at least $k|{\mathcal{I}}|/2m$ incidences between the k points and the set L.

Let us identify ℂ with R ² and partition ℂ²={R}⁴ into M cells plus a boundary hypersurface, where M is to be determined later. One can use a degree D<(12M)^1/4 polynomial Q so that R ⁴∖{Q=0} has M components and no component contains more than n/M points:

$${\mathbf{R}}^{4} = \{ Q = 0 \} \cup\varOmega_1 \cup\cdots\cup \varOmega_M.$$

The existence of such polynomial follows from Corollary 5.3 below.

If most of the incidences are in R ⁴∖{Q=0} (inside a cell) then a simple double-counting argument gives the desired bound. This is the case when we are going to use the induction hypothesis. If most of the incidences are on {Q=0} then we will bound the number of incidences directly.

Let ℓ∈L be one of the complex lines. Assume first that ℓ is not on the surface {Q=0}. We will now bound the number of cells that ℓ intersects as follows. We can parameterize ℓ in ℂ² as

$$\ell= \bigl\{ (z,Az+B): z \in{\mathbb{C}}\bigr\}$$

for some complex numbers A,B (ignoring for the sake of the sketch the “vertical” case when A is infinite). Writing ℂ² as R ⁴, this becomes

$$\ell= \bigl\{ (s,t,as-bt+c,at+bs+d): s,t \in{\mathbf{R}}\bigr\}$$

for some real numbers a,b,c,d. The polynomial Q(x ₁,x ₂,x ₃,x ₄) restricted to ℓ is then a degree D polynomial of variables s and t. As {Q=0} is a degree D curve, the number of connected components of ℓ∖{Q=0} is at most $2(\binom{D-1}{2}+1)$ by the Harnack curve theorem [19] (note that each component of ℓ∖{Q=0} will contain a component of {Q=±ε} if ε is small enough); thus each line ℓ meets at most D ² cells Ω _i .

Let L _i denotes the set of lines in L that have non-empty intersection with Ω _i . By (3.1), the number of incidences in each cell is bounded by

On the other hand, as each line ℓ meets at most D ² cells, we have

$$\sum_{i=1}^M |L_i| \leq D^2|L|$$

and hence by Hölder’s inequality

$$\sum_{i=1}^M |L_i|^{\frac{2}{3}}\leq\bigl(D^2 |L| \bigr)^{\frac {2}{3}}M^{\frac{1}{3}}.$$

Inserting this into our preceding bound and using the fact that D≤(12M)^1/4, we conclude that

$$\sum_{i=1}^M \bigl|{\mathcal{I}}\cap I(P \cap \varOmega_i, L_i)\bigr| \leq12^{\frac {1}{3}}M^{-\varepsilon}C_3n^{\frac{2}{3}+\varepsilon} m^{\frac{2}{3}} + C_1(n + Mm).$$

Using the hypothesis, we thus conclude (if we choose $M \geq(4\times 12^{\frac{1}{3}})^{\frac{1}{\varepsilon}}$, and then choose C ₃ large enough depending on C ₁,M so that the C ₁(n+Mm) term here can be absorbed into the main term using (3.2)) that

$$\sum_{i=1}^M \bigl|{\mathcal{I}}\cap I(P \cap \varOmega_i, L_i)\bigr| \leq\frac{1}{2} C_3n^{\frac{2}{3}+\varepsilon} m^{\frac{2}{3}}.$$

The above estimate handles all the incidences that lie outside of {Q=0}. To close the induction, it will thus suffice (if C ₃,C ₁ are chosen large enough) to show that

$$ \bigl|{\mathcal{I}}\cap I\bigl(P \cap\{Q=0\},L\bigr)\bigr| \ll_{M}n^{\frac{2}{3}+\varepsilon} m^{\frac {2}{3}} + n + m.$$

(3.3)

To establish this, we first perform a technical decomposition to avoid the issue of singular points on the hypersurface {Q=0}. More specifically, we introduce a sequence of hypersurfaces S ₀,S ₁,…,S _D by setting S ₀:={Q=0}, Q ₀:=Q, and

$$Q_{i+1}:=\sum_{j=1}^4\displaystyle\alpha_j^{(i)}\frac{\partial }{\partial x_j}Q_i$$

for 1≤i≤D, which defines the surface S _i+1={Q _i+1=0}; here the $\alpha_{j}^{(i)}$ are generic reals. All of the S _i have degree at most D. For each point p∈P∩{Q=0} there is an index $i=\operatorname{ind}(p)$ between 0 and D which is the first i when $p\not\in S_{i+1}$. Note that this implies that p is a smooth point of S _i , so that the tangent space to S _i at p is three-dimensional, and in particular can contain at most one complex line. In particular, at most one complex line incident to p is on the hypersurface S _i ; all other incident complex lines intersect S _i in a one-dimensional curve. Let us consider the set of points $P_{i}=\{p\in P, \operatorname{ind}(p)=i\}$. We bound the number of incidences ${\mathcal{I}}_{i}$ between P _i and L. We will follow Székely’s method [46]. The complex lines on the surface S _i give no more than |P _i | incidences, so it is enough to consider incidences between P _i and complex lines intersecting S _i in a curve. The degree of the intersection curve is at most D. Let us project the points P _i and the intersection curves onto a generic plane. We will define a geometric graph G ⁽ⁱ⁾ drawn on this generic plane so that the vertex set is the projection of P _i . If a curve is incident to s+D ²/2 vertices then we can draw at least s edges along (a component of) the curve without multiple edges. The total number of edge intersections is bounded by Bézout’s theorem, it is not more than $\binom{m}{2}D^{2}$. On the other hand one can apply the crossing number inequality [2, 28] to get a lower bound on the number of crossings. The graph G ⁽ⁱ⁾ has at least $|{\mathcal{I}}_{i}|-mD^{2}/2$ edges. If $|{\mathcal{I}}_{i}|-mD^{2}/2\geq4|P_{i}|$ then

$$\binom{m}{2}D^2\geq\frac{(|{\mathcal{I}}_i|-mD^2/2)^3}{64|P_i|^2}.$$

So either $|{\mathcal{I}}_{i}|\leq mD^{2}/2 + 4|P_{i}|$ or $|{\mathcal {I}}_{i}|\leq 4(mD|P_{i}|)^{2/3}$. Summing the number of incidences over the P _i , i=1,…,D gives the desired inequality (3.3) (noting that the implied constants can depend on M and hence on D).

Remark 3.1

One can also view this argument from a recursive perspective rather than an inductive one. With this perspective, one starts with a collection of n points and m lines and repeatedly passes to smaller configurations of about n/M points and a smaller number of lines as well. Thus, one expects about log _M n iterations in procedure. Collecting all the bounds together to obtain a final bound of the form An ^2/3 m ^2/3 (ignoring the lower order terms n,m for now), we see that with each iteration, the constant A increases by a bounded multiplicative factor (independent of M), assuming that A was chosen sufficiently large depending on M. Putting together these increases, one obtains a final value of A of the shape $C_{M} \times C^{\log_{M} n}$; letting M become large, this gives bounds of the shape C _ε n ^ε as claimed. The key point is that the main term in the estimate only grows by a constant factor independent of M with each step of the iteration; the lower order terms, on the other hand, are permitted to grow by constants depending on C _M , as they can be absorbed into the main term (using the reduction to the regime (3.2)).

4 Some Algebraic Geometry

In this section we review some notation and facts from algebraic geometry that we will need here. Standard references for this material include [16, 20] or [32].

It will be convenient to define algebraic geometric notions over the field ℂ, as it is algebraically complete. However, for our applications we will only need to deal with the real points of algebraic sets.

Definition 4.1

(Algebraic Sets)

Let d≥1 be a dimension. An algebraic set in ℂ^d is any set of the form

$$\bigl\{ x \in{\mathbb{C}}^d: P_1(x) =\cdots=P_m(x) =0\bigr\},$$

where P ₁,…,P _m :ℂ^d→ℂ are polynomials. If one can take m=1, we call the algebraic set a hypersurface. An algebraic set is irreducible if it cannot be expressed as the union of two strictly smaller algebraic sets. An irreducible algebraic set will be referred to as an algebraic variety, or variety for short.

The intersection of any subset of ℂ^d with R ^d will be referred to as the real points of that subset. A real algebraic variety is the real points V _R of a complex algebraic variety V.³

If V is a variety in ℂ^d, we can define the dimension dim(V)=r of V to be the largest natural number for which there exists a sequence

$$\emptyset\neq V_0 \subsetneq V_1 \subsetneq\cdots \subsetneq V_r = V$$

of varieties between ∅ and V. There are many alternate definitions of this quantity. For instance, r is also the transcendence degree of the function field ℂ(V) of V (see [32, Sect. I.7]). Thus, for instance dim(ℂ^d)=d, and one has dim(V)≤dim(W) whenever V⊂W are varieties, with the inequality being strict if V≠W; in particular, for V⊂ℂ^d, dim(V) is an integer between 0 and d. The quantity d-dim(V) is called the codimension of V.

It is known (see e.g. [16, Sect. 1.3]) that to any r-dimensional variety one can associate a unique natural number D, called the degree of V, with the property that almost every codimension r affine subspace of ℂ^d intersects V in exactly D points. Thus, for instance, if P:ℂ^d→ℂ is an irreducible polynomial of degree D, then the hypersurface {P=0} has dimension d-1 (and thus codimension 1) and degree D.

We do not attempt to define the notions of degree and dimension directly for real algebraic varieties, as there are some subtle issues that arise in this setting (see e.g. [37]). However, in our applications every real algebraic variety will be associated with a complex one, which of course will carry a notion of degree and dimension. Later on (by using Proposition 4.6 below) we will see that we may easily reduce to the model case in which the real algebraic varieties have full dimension inside their complex counterparts, in the sense that the real tangent spaces have the same dimension as the complex ones.

Every algebraic set can be uniquely decomposed as the union of finitely many varieties, none of which are contained in any other (see e.g. [32, Proposition I.5.3]). We define the dimension of the algebraic set to be the largest dimension of any of its component varieties.

If V is an r-dimensional variety in ℂ^d, and P:ℂ^d→V is a polynomial which is not identically zero on V, then every component of V∩{P=0} has dimension r-1 (see [32, Sect. I.8]).

A basic fact is that the degree of a variety controls its complexity:⁴

Lemma 4.2

(Degree Controls Complexity)

Let V be an algebraic variety in ℂ^d of degree at most D. Then we can write

$$V = \bigl\{ x \in{\mathbb{C}}^d: P_1(x) =\cdots=P_m(x)= 0\bigr\}$$

for some m=O _d,D (1) and some polynomials P ₁,…,P _m of degree at most D.

Proof

See [8, Theorem A.3] or [31]. Indeed, one can take P ₁,…,P _m to be a linear basis for the vector space of all the polynomials of degree at most D that vanish identically on V. □

We have the following converse:

Lemma 4.3

(Complexity Controls Degree)

Let

$$V = \bigl\{ x \in{\mathbb{C}}^d: P_1(x) =\cdots=P_m(x)= 0\bigr\}$$

for some m≥0 and some polynomials P ₁,…,P _m :ℂ^d→ℂ of degree at most D. Then V is the union of O _m,D,d (1) varieties of degree O _m,D,d (1).

Proof

See [8, Lemma A.4] (to obtain the decomposition) and [8, Lemma 3.5] (to bound the degree). □

A smooth point of a k-dimensional algebraic variety V is an element p of V such that V can be locally described by a smooth k-dimensional complex manifold in a neighbourhood of p. Points in V that are not smooth will be called singular. We let $V^{\operatorname{smooth}}$ denote the smooth points of V, and $V^{\operatorname{sing}} := V \backslash V^{\operatorname{smooth}}$ denote the singular points.

It is well known that “most” points in an algebraic variety V are smooth (see e.g. [50, Theorem 5.6.8]). In fact, we have the following quantitative statement:

Proposition 4.4

(Most Points Smooth)

Let V be a k-dimensional algebraic variety in ℂ^d of degree at most D. Then $V^{\operatorname{sing}}$ can be covered by O _D,d (1) algebraic varieties in V of dimension at most k-1 and degree O _D,d (1).

Proof

We will prove the more general claim that for any integer r with k≤r≤d, there exists an algebraic variety W in ℂ^d containing V of dimension at most r and degree O _D,d (1), such that $V \cap W^{\operatorname{sing}}$ can be covered by O _D,d (1) algebraic varieties of dimension at most k-1 and degree O _D,d (1). If we apply this claim with r=k, then W must equal V, giving the proposition (after restricting the algebraic varieties produced by the claim to V).

We establish the claim by downward induction on r. The case r=d is trivial, as we can set W=ℂ^d, so assume now that k≤r<d and that the claim has already been established for r+1. Thus there exists an algebraic variety W containing V of dimension at most r+1 and degree O _D,d (1) such that $V \cap W^{\operatorname {sing}}$ can be covered by O _D,d (1) algebraic varieties of dimension at most k-1 and degree O _D,d (1).

If W has dimension r or less, then we are already done, so we may assume that W has dimension exactly r+1; in particular W is not equal to V. By Lemma 4.2, we may write

$$V = \bigl\{ x \in{\mathbb{C}}^d: P_1(x) =\cdots=P_m(x)= 0\bigr\}$$

for some m=O _d,D (1) and some polynomials P ₁,…,P _m of degree O _d,D (1).

Since V is not equal to W, the polynomials P _i cannot all vanish identically on W. Without loss of generality we may assume that P ₁ does not vanish identically on W. We then subdivide into three cases:

• (i) The gradient ∇P ₁ does not vanish identically on V.

• (ii) ∇P ₁ vanishes identically on V, but does not vanish identically on W.

• (iii) ∇P ₁ vanishes identically on W.

Suppose we are in case (i). Let W′:={x∈W:P ₁(x)=0}. This algebraic set is strictly contained in W and thus has dimension precisely r, by the discussion prior to Lemma 4.2. By Lemma 4.2, W′ is cut out by O _D,d (1) polynomials of degree O _D,d (1). By Lemma 4.3, W′ is thus the union of O _D,d (1) varieties of dimension r and degree O _D,d (1). One of these varieties, call it W″, must contain V.

Let x be a point in $V \cap W^{\operatorname{smooth}}$ with ∇P ₁(x)≠0, then by the (complex)⁵ inverse function theorem, the set {x∈W:P ₁(x)=0} is a smooth r-dimensional complex manifold in a neighbourhood of x. As such, we see that x is a smooth point of W″. On the other hand, by Lemma 4.3, the set {x∈V:∇P ₁(x)=0} can be covered by O _D,d (1) varieties of dimension at most k-1 and degree O _D,d (1). We thus see that the claim holds for r by using W″ in place of W.

Now suppose we are in case (ii). Then there is a partial derivative $\partial_{x_{i}} P_{1}$ of P ₁ that vanishes identically on V but does not vanish identically on W. We then replace P ₁ by $\partial_{x_{i}}P_{1}$ (lowering the degree by one) and return to the above subdivision of cases. We continue doing this until we end up in case (i) or case (iii). Since case (ii) cannot hold for polynomials of degree zero or one, we see that we must eventually leave case (ii) and end up in one of the other cases.

Finally, suppose we are in case (iii). Then, by the fundamental theorem of calculus, P ₁ is constant in a neighbourhood of every smooth point of W. In particular, there is some constant c for which set {P ₁=c} is non-empty and has the same dimension as W, and thus (by irreducibility of W) we conclude that P ₁ is constant on W; since P ₁ vanishes on V, it thus vanishes on W, a contradiction. Thus case (iii) cannot actually occur, and we are done. □

We may iterate this proposition (performing an induction on the dimension k) to obtain

Corollary 4.5

(Decomposition into Smooth Points)

Let V be a k-dimensional algebraic variety in ℂ^d of degree at most D. Then one can cover V by $V^{\operatorname{smooth}}$ and O _D,d (1) sets of the form $W^{\operatorname{smooth}}$, where each W is an algebraic variety in V of dimension at most k-1 and degree O _D,d (1).

Finally, we address a technical point regarding the distinction between real and complex algebraic varieties. If p∈ℓ⊂R ^d is a smooth real point of a k-dimensional complex algebraic variety ℓ _ℂ∈ℂ^d, then it must have a k-dimensional complex tangent space T _p ℓ _ℂ⊂ℂ^d, by definition. However, its real tangent space T _p ℓ:=T _p ℓ _ℂ∩R ^d may have dimension smaller than k. For instance, in the case k=1, d=2, the complex line ℓ _ℂ:={(z,w)∈ℂ²:z=iw} has a smooth point at (0,0) with a one-dimensional complex tangent space (also equal to ℓ _ℂ), but the real tangent space is only zero-dimensional. Of course, in this case, the real portion ℓ:=ℓ _ℂ∩R ² of the complex line is just a zero-dimensional point. This phenomenon generalizes:

Proposition 4.6

Let V be a k-dimensional algebraic variety in ℂ^d of degree at most D. Then at least one of the following statements is true:

• (i) The real points V _R of V are covered by the smooth points $W^{\operatorname{smooth}}$ of O _D,d (1) algebraic varieties W of dimension at most k-1 and degree O _D,d (1) which are contained in V.

• (ii) For every smooth real point $p \in V^{\operatorname {smooth}}_{\mathbf{R}}$ of V, the real tangent space T _p V _R :=T _p V∩R ^d is k-dimensional (and thus T _p V is the complexification of T _p V _R ). In particular, $V^{\operatorname {smooth}}_{\mathbf{R}}$ is k-dimensional.

Proof

By Lemma 4.2, V can be cut out by polynomials P ₁,…,P _m of degree O _D,d (1) with m=O _D,d (1). Let $\tilde{V}$ be the algebraic set cut out by both P ₁,…,P _m and their complex conjugates $\overline{P_{1}},\ldots,\overline{P_{m}}$, defined as the complex polynomials whose coefficients are the conjugates of those for P ₁,…,P _m . Clearly V and $\tilde{V}$ have the same real points. If $\tilde{V}$ is strictly smaller than V, then it has dimension at most k-1, and by Lemma 4.3 and Corollary 4.5 we are thus in case (i). Now suppose instead that V is equal to $\tilde{V}$. Then at every smooth point p of V (or $\tilde{V}$), the k-dimensional complex tangent space $T_{p} V = T_{p}\tilde{V}$ is cut out by the orthogonal complements of the gradients ∇P ₁,…,∇P _m and their complex conjugates. As such, it is manifestly closed with respect to complex conjugation, and is thus the complexification of its real counterpart $T_{p} \tilde{V}_{\mathbf{R}}$. We are thus in case (ii). □

Note that by iterating the above proposition, we may assume that each of the varieties W occurring in case (i) obey the properties stated in case (ii).

5 Proof of Main Theorem

We now prove Theorem 2.1. We will prove this theorem by an induction on the quantity d+k. The case d+k=0 is trivial, so we assume inductively that d+k≥1 and that the claim has already been proven for all smaller values of d+k.

We can dispose of the easy case k=0, because in this case L consists entirely of points, and in particular each ℓ in L is incident to at most one point in P, giving the bound $|{\mathcal {I}}| \leq|L|$ which is acceptable. Hence we may assume that k≥1, and thus d≥2.

We now perform a technical reduction to eliminate some distinctions between the real and complex forms of the variety ℓ. We may apply Proposition 4.6 to each variety ℓ. Those varieties ℓ which obey conclusion (i) of that proposition can be easily handled by the induction hypothesis, since the varieties W arising from that conclusion have dimension strictly less than k. Thus we may restrict attention to varieties which obey conclusion (ii), namely that for every smooth real point p in ℓ (and in particular, for all $(p,\ell) \in{\mathcal{I}}$), the real tangent space T _p ℓ has full dimension k.

We now divide into two subcases: the case d>2k and the case d=2k, and deduce each case from the induction hypothesis. The main case is the latter; the former case will be obtainable from the induction hypothesis by a standard projection argument.

5.1 The Case of Excessively Large Ambient Dimension

We first deal with the case d>2k. Here, we can use a generic projection argument to deduce the theorem from the induction hypothesis. Indeed, fix ε,C ₀,P,L, and let π:R ^d→R ^2k be a generic linear transformation (avoiding a finite number of positive codimension subvarieties of the space $\operatorname {Hom}({\mathbf{R}}^{d},{\mathbf{R}}^{2k}) \equiv{\mathbf{R}}^{2kd}$ of linear transformations from R ^d to R ^2k). Since k≥1, we see that for any two distinct points p,p′∈P, the set of transformations π for which π(p)=π(p′) has positive codimension in $\operatorname{Hom}({\mathbf {R}}^{d},{\mathbf{R}}^{2k})$. Hence for generic π, the map from P to π(P) is bijective.

Similarly, let ℓ,ℓ′ be two distinct k-dimensional varieties in L. Then generically π(ℓ),π(ℓ′) will be k-dimensional varieties in R ^2k. We claim that for generic π, the varieties π(ℓ),π(ℓ′) are distinct. Indeed, since ℓ,ℓ′ are distinct varieties of the same dimension, there exists a point p on ℓ′ that does not lie on ℓ. Since ℓ has codimension d-k>d-2k, we conclude that for generic π, the d-2k-dimensional plane π ^-1(π(p)) does not intersect ℓ′, and the claim follows. Thus the map π:L→π(L) is bijective.

Next, let $(p,\ell) \in{\mathcal{I}}$. Clearly, π(p)∈π(ℓ), and so π induces a bijection from ${\mathcal{I}}$ to some set of incidences $\pi ({\mathcal{I}})\subset I(\pi(P), \pi(L))$.

To summarize, we have established that for generic π,

We would now like to apply the induction hypothesis to the configuration of points π(P), varieties π(L), and incidences $\pi({\mathcal{I}})$, which will clearly establish the desired claim. To do this, we need to verify that π(P), π(L), $\pi({\mathcal{I}})$ obey Axioms (i)–(v) for generic π.

If ℓ∈L, then ℓ is a k-dimensional variety of degree at most C ₀, and so generically π(ℓ) will also be a k-dimensional variety of degree at most C ₀, which gives Axiom (i).

Axioms (ii) and (iii) for $\pi(P), \pi(L), \pi({\mathcal{I}})$ are generically inherited from those of $P, L, {\mathcal{I}}$ thanks to the bijection between ${\mathcal{I}}$ and $\pi({\mathcal{I}})$.

Now we turn to Axiom (iv). Fix $(p,\ell) \in{\mathcal{I}}$, then p is a smooth point of ℓ. Since d>2k and k≥1, it will generically hold that the codimension 2k affine space π ^-1(π(p)) will intersect the codimension d-k variety ℓ only at p. Thus, π(p) will generically be a smooth point of π(ℓ), which gives Axiom (iv).

Finally, if $(p,\ell), (p,\ell') \in{\mathcal{I}}$, then by hypothesis, the k-dimensional tangent spaces T _p ℓ,T _p ℓ′ are transverse and thus span a 2k-dimensional affine space through p. Generically, π will be bijective from this space to ℂ^2k, and thus T _π(p) π(ℓ)=π(T _p ℓ) and T _π(p) π′(ℓ′)=π(T _p ℓ′) remain transverse. This gives Axiom (v).

Now that all the axioms are verified, the induction hypothesis gives

$$\bigl|\pi({\mathcal{I}})\bigr| \leq A \bigl|\pi(P)\bigr|^{\frac {2}{3}+\varepsilon} \bigl|\pi(L)\bigr|^{\frac {2}{3}} +\frac{3}{2} \bigl|\pi(P)\bigr| + \frac{3}{2} \bigl|\pi(L)\bigr|$$

for generic π and some A depending only on k,ε,C ₀, and the claim follows.

5.2 The Case of Sharp Ambient Dimension

It remains to handle the case when d=2k and k≥1. Here we fix d,k,C ₀,ε, and allow all implied constants in the asymptotic notation to depend on these parameters. We will need some additional constants

$$C_3 > C_2 > C_1 > C_0,$$

where

• C ₁ is assumed to be sufficiently large depending on C ₀, k and ε;

• C ₂ is assumed to be sufficiently large depending on C ₁,C ₀,k, and ε; and

• C ₃ is assumed to be sufficiently large depending on C ₂,C ₁,C ₀,k, and ε.

For suitable choices of C ₁,C ₂,C ₃, we will establish the inequality

$$ |{\mathcal{I}}| \leq C_3 |P|^{2/3+\varepsilon} |L|^{2/3} +\frac{3}{2} |P| + \frac{3}{2} |L|$$

(5.1)

by an induction on the number of points P. The inequality is trivial for |P|=0, so we assume that |P|≥1 and that the claim has been proven for all smaller sets of points P.

Suppose $P, L, {\mathcal{I}}$ obey all the specified axioms. We begin with two standard trivial bounds:

Lemma 5.1

(Trivial Bounds)

We have

$$ |{\mathcal{I}}| \leq C_0^{1/2} |P| |L|^{1/2} +|L|$$

(5.2)

and

$$|{\mathcal{I}}| \leq C_0^{1/2} |L| |P|^{1/2} + |P|.$$

Proof

Consider the set Σ of triples (p,p′,ℓ)∈P×P×L such that $(p,\ell), (p',\ell) \in\nobreak {\mathcal {I}}$. If p≠p′, then from Axiom (iii) this pair contributes at most C ₀ triples to Σ, while the case p=p′ contributes exactly $|{\mathcal {I}}|$ triples. We thus have

$$|\varSigma| \leq C_0 |P|^2 + |{\mathcal{I}}|.$$

On the other hand, from Cauchy–Schwarz

$$|\varSigma| \geq\frac{|{\mathcal{I}}|^2}{|L|}$$

and thus

$$|{\mathcal{I}}|^2 - |L| |{\mathcal{I}}| \leq C_0 |P|^2 |L|.$$

We rearrange this as

$$\biggl(|{\mathcal{I}}|-\frac{|L|}{2} \biggr)^2 \leq\frac {|L|^2}{4} +C_0 |P|^2 |L|.$$

The right-hand side is bounded by $(\frac{|L|}{2} + C_{0}^{1/2} |P||L|^{1/2} )^{2}$, which gives (5.2). The second bound is proven similarly by swapping the roles of P and L (and using Axiom (ii) instead of Axiom (iii)). □

One can also view this lemma as a special case of the classical Kővári–Sós–Turán theorem [26].

In view of this lemma, we can obtain the desired bound (5.1) whenever we are outside the regime

$$ C_2 |P|^{1/2} \leq|L| \leq C_2^{-1} |P|^2$$

(5.3)

provided that C ₂ is large enough depending on C ₀, and C ₃ is large enough depending on C ₀,C ₂. Thus we may assume without loss of generality that we are in the regime (5.3).

Following Guth and Katz [18], the next step is to apply the polynomial ham sandwich theorem of Stone and Tukey [45]. We will sketch their argument here. For more details we refer to the excellent review of the polynomial decomposition method in [25].

Theorem 5.2

(Polynomial Ham Sandwich Theorem)

Let D,M,d≥1 be integers with $M = \binom{D+d}{d} -1$, and let S ₁,…,S _M be finite sets of points of R ^d. Then there exists a polynomial Q:R ^d→R of degree at most D such that the real algebraic hypersurface {x∈R ^d:Q(x)=0} bisects each of the S ₁,…,S _M , in the sense that

$$\bigl|\bigl\{ x \in S_i: Q(x) < 0 \bigr\}\bigr| \leq\frac{1}{2}|S_i|$$

and

$$\bigl|\bigl\{ x \in S_i: Q(x) > 0 \bigr\}\bigr| \leq\frac{1}{2}|S_i|$$

for all i=1,…,M.

As observed in [18], we may iterate this to obtain

Corollary 5.3

(Cell Decomposition [18])

Let D,d≥1 be integers, and let P be a finite set of points in R ^d. Then there exists a decomposition

$${\mathbf{R}}^d = \{ Q = 0 \} \cup\varOmega_1 \cup\cdots\cup \varOmega_M,$$

where Q:R ^d→R is a polynomial of degree at most D, M=O _d (D ^d), and Ω ₁,…,Ω _M are open sets bounded by {Q=0} (i.e. the topological boundary of any Ω _i is contained in {Q=0}), such that |P∩Ω _i |=O _d (|P|/D ^d) for each 1≤i≤M.

Proof

We may assume that D is large depending on d, as the claim is trivial otherwise. By Theorem 5.2 and induction on M, there is a constant A=A _d >0 such that for every power of two M≥1 we can find a partition

$${\mathbf{R}}^d = \{Q_M = 0 \} \cup\varOmega_{M,1} \cup\cdots \cup\varOmega_{M,M},$$

where Q _M :R ^d→R is a polynomial of degree at most AM ^1/d, and Ω _M,1,…,Ω _M,M are open sets bounded by {Q _M =0} such that |P∩Ω _i |≤|P|/M for each 1≤i≤M. The claim follows by selecting M comparable to a large multiple of D ^1/d. □

We apply this corollary to our situation with D:=C ₁, to give a decomposition

$${\mathbf{R}}^{2k} = \{ Q = 0 \} \cup\varOmega_1 \cup\cdots\cup \varOmega_M,$$

where Q:R ^2k→R has degree at most C ₁, $M = O( C_{1}^{2k})$, and the Ω _i are open sets bounded by {Q=0} such that $|P\cap\varOmega_{i}| = O( |P| / C_{1}^{2k} )$ for each i. (Recall that we allow implied constants in the O() notation to depend on k.) In particular, we have |P∩Ω _i |<|P| for each i, which will allow us to apply the induction hypothesis to each P∩Q _i .

For each 1≤i≤M, let L _i be the sets ℓ in L that have non-empty intersection with Ω _i . Clearly

$$|{\mathcal{I}}| = \bigl|{\mathcal{I}}\cap I\bigl(P \cap\{Q=0\},L\bigr)\bigr| + \sum _{i=1}^M \bigl|{\mathcal{I}}\cap I( P \cap\varOmega_i,L_i )\bigr|.$$

We first estimate the latter sum. Applying the induction hypothesis, we have

Note the factor of $C_{1}^{-2k\varepsilon}$ in the main term, which will be crucial in closing the induction.

Let ℓ be a variety in L, then ℓ is k-dimensional and has degree O(1). Meanwhile, the set {Q=0} is a hypersurface of degree at most C ₁. We conclude that ℓ either lies in {Q=0}, or intersects {Q=0} in an algebraic set of dimension at most k-1. In the former case, ℓ cannot belong to any of the L _i . In the latter case we apply a generalization of a classical result established independently by Oleinik and Petrovsky [33], Milnor [30], and Thom [51], such that the number of connected components of ℓ\{Q=0} is at most $O( C_{1}^{k} )$; we give a proof of this fact in Theorem A.2. Recently a more general bound was proved by Barone and Basu [4].

From Theorem A.2 we will use here that ℓ can belong to at most $O(C_{1}^{k})$ of the sets L _i .

This implies that

$$\sum_{i=1}^M |L_i| \ll C_1^k |L|$$

and thus by Hölder’s inequality and the bound $M = O(C_{1}^{2k})$

$$\sum_{i=1}^M |L_i|^{\frac{2}{3}}\ll C_1^{\frac{4k}{3}} |L|^{\frac{2}{3}}.$$

Inserting this into our preceding bounds, we conclude that

$$\sum_{i=1}^M \bigl|{\mathcal{I}}\cap I(P \cap \varOmega_i, L_i)\bigr| \ll C_1^{-2k\varepsilon}C_3 |P|^{\frac{2}{3}+\varepsilon} |L|^{\frac{2}{3}} + |P| +C_1^k |L|.$$

Using the hypothesis (5.3), we thus conclude (if C ₁ is large enough depending on k,ε, and C ₂ is large enough depending on C ₁, k, ε) we have

$$\sum_{i=1}^M \bigl|{\mathcal{I}}\cap I(P \cap \varOmega_i, L_i)\bigr| \leq\frac{1}{2} C_3|P|^{\frac{2}{3}+\varepsilon} |L|^{\frac{2}{3}}.$$

To close the induction, it will thus suffice (again by using (5.3)) to show that

$$ \bigl|{\mathcal{I}}\cap I\bigl(P \cap\{Q=0\}, L\bigr )\bigr| \ll_{C_1}|P|^{\frac{2}{3}+\varepsilon} |L|^{\frac{2}{3}} + |P| + |L|.$$

(5.4)

Remark 5.4

A modification of the above argument shows that if one applied Corollary 5.3 not with a bounded degree D=C ₁, but instead with a degree D comparable to (|P|^2/3|L|^-1/3)^1/k, then one could control the contribution of the cell interiors Ω _i by the trivial bound (5.2), rather than the inductive hypothesis, thus removing the need to concede an epsilon in the exponents. However, the price one pays for this is that the hypersurface {Q=0} acquires a much higher degree, and the simple arguments given below to handle the incidences on this hypersurface are insufficient to give good bounds (except in the original Szemerédi–Trotter context when k=1 and d=2). Nevertheless, it may well be that a more careful analysis, using efficient quantitative bounds on the geometry of high-degree varieties, may be able to recover good bounds for this strategy, and in particular in removing the epsilon loss in Theorem 2.1.

For inductive reasons, it will be convenient to prove the following generalisation:

Proposition 5.5

Let the notation and hypotheses be as above. (In particular, we are assuming Theorem 2.1 to already be proven for all smaller values of d+k, and continue to allow all implied constants to depend on k.) Let 0≤r<2k, and let Σ be an r-dimensional variety in R ^2k of degree at most D. Then

$$\bigl|{\mathcal{I}}\cap I(P \cap\varSigma, L)\bigr| \ll_{D}|P|^{\frac{2}{3}+\varepsilon}|L|^{\frac {2}{3}} + |P| + |L|.$$

Clearly, (5.4) follows by specialising to the case r=2k-1, D=C ₁, and Σ={Q=0}.

Proof

We induct on r. If r=0, then Σ is a single point, and so each set ℓ in L has at most one incidence in P∩Σ, giving the net bound $|{\mathcal{I}}| \leq|L|$, which is acceptable.

Now suppose that 1≤r<2k-1, and that the claim has already been proven for smaller values of r.

We may of course delete all points of P outside of Σ. If p is a point in Σ, then p is either a smooth point in Σ or a singular point. Let us first deal with the contribution of the latter case. As Σ is an r-dimensional variety of degree at most D, the singular points in Σ lie in a union of O _D (1) varieties Σ ₁,…,Σ _m of degree O _D (1) and dimension strictly less than r (see Proposition 4.4). By the induction hypothesis, we have

$$\bigl|{\mathcal{I}}\cap I(P \cap\varSigma_i, L)\bigr| \ll_{D}|P|^{\frac{2}{3}+\varepsilon}|L|^{\frac{2}{3}} + |P| + |L|$$

for each such variety Σ _i , and so on summing in i we see that the contribution of the singular points is acceptable.

By deleting the singular points of Σ from P, we may thus assume without loss of generality that all the points in P are smooth points of Σ. For each ℓ∈L, consider the intersection ℓ∩Σ. As ℓ is a variety of degree k, we see that ℓ is either contained in Σ, or ℓ∩Σ will be a algebraic set of dimension strictly less than k.

Consider the contribution of the first case when ℓ is contained in Σ. If we have two distinct incidences $(p,\ell), (p,\ell')\in{\mathcal{I}}$ such that ℓ,ℓ′ both lie in Σ, then the k-dimensional tangent spaces T _p ℓ,T _p ℓ′ lie in the r-dimensional space T _p Σ. On the other hand, by Axiom (iv), T _p ℓ and T _p ℓ′ are transverse. Since r<2k, this is a contradiction. Thus, each point in P is incident to at most one variety ℓ∈L that lies in Σ, and so there are at most |L| incidences that come from this case.

We may thus assume that each variety ℓ∈L intersects Σ in an algebraic set of dimension strictly less than k. Since ℓ has degree at most C ₀, and Σ has degree at most D, we see from Corollary 4.5 that ℓ∩Σ is the union of the smooth points of O _D (1) algebraic varieties of dimension between 0 and k-1 and degree O _D (1).

Thus we may write $\ell\cap\varSigma= \bigcup_{k' = 0}^{k-1}\bigcup_{j=1}^{J} \ell_{k',j}^{\operatorname{smooth}}$ for some J=O _D (1), where for each 0≤k′<k-1 and 1≤j≤J, ℓ _k′,j is either empty, or is an algebraic variety of dimension k′ and degree O _D (1), and $\ell_{k',j}^{\operatorname{smooth}}$ are the smooth points of ℓ _k′,j . Note that by padding the decomposition with empty varieties, we may assume that J is independent of ℓ. We may then estimate

$$\bigl|{\mathcal{I}}\cap I(P \cap\varSigma, L)\bigr| \leq\sum_{k'=0}^{k-1}\sum_{j=1}^J |{\mathcal{I}}_{k',j}|,$$

where ${\mathcal{I}}_{k',j}$ is the set of all incidences $(p,\ell)\in{\mathcal{I}}$ such that $p \in\ell_{k',j}^{\operatorname{smooth}}$. It thus suffices to show that

$$ |{\mathcal{I}}_{k',j}| \ll_{D} |P|^{\frac {2}{3}+\varepsilon}|L|^{\frac{2}{3}} + |P| + |L|$$

(5.5)

for each k′ and j.

Fix k′ and j. Those varieties ℓ∈L for which $|{\mathcal {I}}\cap(P\times\{\ell\})| \leq C_{0}$ will contribute at most C ₀|L| incidences to (5.5), so we may assume that $|{\mathcal{I}}\cap(P \times \{\ell\})| >C_{0}$ for all ℓ∈L. By Axiom (ii), this forces the ℓ _k′,j to be distinct. If we then let $L' = L'_{k',j}$ be the set of all the ℓ _k′,j , we can thus identify ${\mathcal{I}}_{k',j}$ with a subset ${\mathcal{I}}'$ of I(P,L′). However, by induction hypothesis, Theorem 2.1 is already known to hold if k is replaced by k′ (keeping d=2k fixed). So, to conclude the argument, it suffices to show that $P, L', {\mathcal {I}}'$ obey the axioms of Theorem 2.1, with C ₀ replaced by $O_{C_{0},D}(1)$. But Axiom (i) is clear from construction, while Axioms (ii), (iii), (iv), and (v) are inherited from the corresponding axioms for $P, L,{\mathcal{I}}$. This closes the induction and proves the lemma. □

The proof of Theorem 2.1 is now complete.

Remark 5.6

It is reasonable to conjecture that one can set ε=0 in Theorem 2.1. From k=1, this can be established using the crossing number inequality [2, 28] and the Harnack curve theorem [19], following the arguments of Székely [46]; it is also possible to establish this inequality via the polynomial partitioning method. For k=2, a more careful analysis of the above arguments (using the refinement to the k=1 case mentioned above) eventually shows that one can take A to be of the shape $\exp(O_{C_{0}}(1/\varepsilon))$; optimizing in ε, one can thus replace the A|P|^ε factor by $\exp( O_{C_{0}}( \sqrt{\log|P|} ) )$. However, for k>2, the highly inductive nature of the argument causes A to depend on ε in an iterated exponential manner.

Remark 5.7

One can construct many examples in which |I(P,L)| is comparable to $|P|^{\frac{2}{3}} |L|^{\frac{2}{3}} + |P| + |L|$ by taking k of the standard point-line configurations in R ² that demonstrate that the original Szemerédi–Trotter theorem (Theorem 1.1) is sharp, and then taking Cartesian products (and increasing the ambient dimension if desired). It is natural to conjecture that the ε loss in (2.1) can be eliminated, but our methods do not seem to easily give this improvement.

It is possible to drop Axiom (iv), at the cost of making Axiom (v) more complicated. For any point p on a real algebraic variety ℓ⊂R ^d, define the tangent cone C _p ℓ to be the set of all elements in R ^d of the form γ′(0), where γ:[-1,1]→ℓ is a smooth map with γ(0)=p. Note that at a smooth point p of ℓ, the tangent cone is nothing more than the tangent space T _p ℓ (translated to the origin). However, the tangent cone continues to be well-defined at singular points, while the tangent space is not.

Corollary 5.8

The conclusions of Theorem 2.1 continue to hold if Axiom (iv) is dropped, but the tangent space T _p ℓ in Axiom (v) is replaced by the tangent cone, but where the constant A is now allowed to depend on the ambient dimension d in addition to k and ε.

Proof

(Sketch) We perform strong induction on k, assuming that the claim has already been proven for smaller k. For those incidences (p,ℓ) in ${\mathcal{I}}$ for which p is a smooth point of ℓ, one can apply Theorem 2.1 to get a good bound, so we may restrict attention to those incidences in which p is a singular point of ℓ. But then we can use Corollary 4.5 to cover the singular portion of ℓ by $O_{C_{0},k,d}(1)$ irreducible components in ℓ of dimension at most k-1 and degree $O_{C_{0},k,d}(1)$. Applying the induction hypothesis to each of these components (noting that Axioms (i)–(iii) and the modified Axiom (v) are inherited by these components, increasing C ₀ if necessary) we obtain the claim. □

Appendix: Connected Components of Real Semi-algebraic Sets

In this appendix we give some standard bounds on the number of connected components of various real semi-algebraic sets. We first bound the number of connected components cut out by a hypersurface {P=0} of bounded degree. This result was proved by independently by Oleinik and Petrovsky [33], Milnor [30], and Thom [51]. (They proved the stronger result that under the conditions of the theorem below the sum of the Betti numbers of X is O _d (D ^d). See further refinements of the statement in [5].) Recently a more general bound was presented by Barone and Basu [4]. They gave tight estimates on the dependence on the various parameters which are hidden in the big-Oh notation in Theorem A.2.

Theorem A.1

Let P:R ^d→R be a polynomial of degree at most D for some D≥1 and d≥0. Then the set {x∈R ^d:P(x)≠0} has O _d (D ^d) connected components.

Proof

We proceed by induction on d. The case d=0 is trivial, so suppose that d≥1 and that the claim is already proven for d-1. By a limiting argument, it suffices to show that for any cube Q in R ^d, the number of components of {x∈Q:P(x)≠0} has O _d (D ^d) connected components, uniformly in Q. The number of components that intersect the boundary ∂Q of Q is O _d (D ^d-1) by the induction hypothesis, so it suffices to control the number of components that lie completely in the interior of Q.

Let C ₁,…,C _m be the components of {x∈Q:P(x)≠0} that avoid ∂Q; our task is to show that m=O _d (D ^d). Observe that each C _i is an open set, with P non-zero in C _i and vanishing on the boundary of C _i . By the continuity of P, we can thus find a compact subset K _i of C _i such that on K _i , at least one of the maximum or minimum of P is attained only in the interior of K _i (i.e. one either has $\sup_{x \in K_{i}} P(x) > \sup_{x \in \partial K_{i}} P(x)$ or $\inf_{x \in K_{i}} P(x) < \inf_{x \in\partial K_{i}} P(x)$). In particular, P has at least one critical point in the interior of K _i , and so ∇P has at least one zero in the interior of K _i , and so the preimage ∇P ^-1({0}) of 0 under the gradient map ∇P:R ^d→R ^d has cardinality at least m.

To avoid degeneracy issues we now perform a perturbation argument. Let u∈R ^d be a sufficiently small vector, then we see that the function x↦P(x)-u⋅x also has the property that at least one of the maximum or minimum of this function is attained only in the interior of K _i . In particular, ∇P-u has at least one zero in the interior of K _i , and so the preimage ∇P ^-1({u}) of u under ∇P also has cardinality at least m.

Now take u to be a sufficiently small generic vector. As the domain and range of the polynomial map ∇P have the same dimension, we see that ∇P ^-1({u}) is finite for generic u (even when P is extended to the complex domain ℂ^d). As such, we can invoke Bézout’s theorem (considering the complex zeros) and conclude that the number of solutions is in fact bounded by (D-1)^d=O(D ^d) for generic u, as each component of ∇P has degree at most D-1. The claim follows. □

A more complicated version of the above argument also works on general algebraic sets:

Theorem A.2

Let d≥k≥0, let V be a k-dimensional real algebraic set in R ^d of complexity at most M, let W be another real algebraic set in R ^d of complexity at most M, and let P:R ^d→R be a polynomial of degree at most D, for some D≥1. Then the set {x∈V\W:P(x)≠0} has O _M,d,k (D ^k) connected components.

Proof

We allow all implied constants to depend on M, d, and k. To give some additional flexibility we allow P to have degree O(D), rather than just having degree at most D.

We induct on the quantity k+d. The case k=0 follows from Lemma 4.3, so suppose that k≥1 and the claim has already been proven for smaller values of k+d. By Lemma 4.3 we may assume V to be irreducible. We may assume that P is non-vanishing on V, as the claim is trivial otherwise.

By Proposition 4.6 and the induction hypothesis we may assume that $V^{\operatorname{smooth}}_{\mathbf{R}}$ is k-dimensional, and by Proposition 4.4 and the induction hypothesis we can handle the contribution of the singular points of V. Thus, by enlarging W if necessary, we may assume without loss of generality that all real points of V\W are smooth.

In particular, all connected components of {x∈V\W:P(x)≠0} are now full dimensional in V. This has the following consequence: if P′ is any multiple of P that is still of degree O(D) and still not vanishing identically on V, and {x∈V\W:P′(x)≠0} is known to have O(D ^k) components, then {x∈V\W:P(x)≠0} also has O(D ^k) components (since any component of the latter contains a component of the former). As such, we now have the freedom to multiply P at will by any polynomial of degree O(D) that does not vanish identically on V. In particular, by using polynomials on the bounded complexity set W that do not vanish on V, we may assume that P vanishes on W, at which point we can remove the role of W; thus we now assume that P vanishes at all singular points of V, and our task is to show that X={x∈V:P(x)≠0} has O(D ^k) components.

As V has complexity O(1), it is not difficult to show (for instance, using an ultralimit compactness argument as in [8]) that the (Zariski closure of the) normal bundle

$$NV := \bigl\{ (x,v) \in{\mathbf{R}}^d \times{\mathbf{R}}^d: x \in V^{\operatorname{smooth}}_{\mathbf{R}}; v \perp T_x V^{\operatorname {smooth}}_{\mathbf{R}}\bigr\}$$

of V has complexity O(1) as well.

Now we repeat the argument used to prove Theorem A.1. It suffices to show for each cube Q that the set

$$\bigl\{ x \in V \cap Q: P(x) \neq0 \bigr\}$$

has O(D ^k) components. The components that touch the boundary of the cube can again be handled by the induction hypothesis, so we may restrict attention to the components that are in the interior of the cube. By arguing as in the proof of Theorem A.1, it suffices to show that for generic u∈R ^d, the function x↦P(x)-u⋅x on $V^{\operatorname{smooth}}_{\mathbf{R}}\cap Q$ has O(D ^k) interior critical points.

By the method of Lagrange multipliers, a point $x \in V^{\operatorname {smooth}}_{\mathbf{R}}$ is a critical point of x↦P(x)-u⋅x if and only if the point (x,∇P(x)-u) lies in NV. On the other hand, for generic u, the set {x∈V:(x,∇P(x)-u)∈NV} (which is the intersection of the codimension k set NV with a generic translate of the graph of ∇P on the dimension k set V) is finite. As ∇P-u has degree O(D) and NV has complexity O(1), an application of Bézout’s theorem⁶ shows that this set has cardinality O(D ^k), and the claim follows. □