A Szemerédi–Trotter Type Theorem in $\mathbb {R}^4$

Abstract

We show that m points and n two-dimensional algebraic surfaces in ${\mathbb {R}}^4$ can have at most $O(m^{{k}/({2k-1})}n^{({2k-2})/({2k-1})}+m+n)$ incidences, provided that the algebraic surfaces behave like pseudoflats with k degrees of freedom, and that $m\le n^{(2k+2)/3k}$. As a special case, we obtain a Szemerédi–Trotter type theorem for 2-planes in ${\mathbb {R}}^4$, provided $m\le n$ and the planes intersect transversely. As a further special case, we obtain a Szemerédi–Trotter type theorem for complex lines in ${\mathbb {C}}^2$ with no restrictions on m and n (this theorem was originally proved by Tóth using a different method). As a third special case, we obtain a Szemerédi–Trotter type theorem for complex unit circles in ${\mathbb {C}}^2$. We obtain our results by combining several tools, including a two-level analogue of the discrete polynomial partitioning theorem and the crossing lemma.

1 Introduction

In [9], Erdős asked how many incidences could occur between a collection of m points and n lines in the plane. The correct asymptotic bound was found by Szemerédi and Trotter in [27]. They proved what is now known as the Szemerédi–Trotter theorem.

Theorem 1.1

(Szemerédi–Trotter) The number of incidences between m points and n lines in $\mathbb {R}^2$ is $O(m^{2/3}n^{2/3}+m+n)$. This bound is tight (up to the implicit constant in the $O(\cdot )$ notation).

This theorem has seen a number of additional proofs, including one by Székely [26] which used the crossing lemma (see [1, 16]). In [20], Pach and Sharir built off Székely’s ideas and proved a Szemerédi–Trotter type theorem for curves with k degrees of freedom.

Definition 1.1

Let $\mathcal {P}\subset \mathbb {R}^2$ be a set of points and let $\Gamma$ be a set of simple open plane curves. We say the collection $(\mathcal {P},\Gamma )$ has k degrees of freedom and multiplicity type $C_0$ if the following conditions hold:

• For any k distinct points from $\mathcal {P}$, there are at most $C_0$ curves from $\Gamma$ passing through all of them.

• Any pair of curves from $\Gamma$ intersect in at most $C_0$ points.

Theorem 1.2

(Pach and Sharir [20]) Let $\mathcal {P}$ be a collection of m points and let $\Gamma$ be a collection of n simple open plane curves. Suppose that $(\mathcal {P},\Gamma )$ has k degrees of freedom and multiplicity type $C_0$. Then the number of incidences between the points and curves is

$$\begin{aligned} O\big (m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}+m+n\big ). \end{aligned}$$

The implicit constant depends only on k and $C_0$.

Similar bounds had previously been known in the special case that the curves in $\Gamma$ were real algebraic curves of bounded degree [5, 19]. In this paper we will discuss a variant of the above theorems that applies to certain families of points and two-dimensional algebraic surfaces in $\mathbb {R}^4.$ First, we will need several definitions.

Definition 1.2

Let $\mathcal {S}$ be a collection of two-dimensional real algebraic surfaces in $\mathbb {R}^4$ and let $C_0\ge 1,\ k\ge 1$ be integers. We say that $\mathcal {S}$ is a $C_0$-good collection of pseudoflats with k degrees of freedom if the following conditions are satisfied:

• (i) Every surface in $\mathcal {S}$ is smooth (i.e., it is a two-dimensional manifold) and can be defined by a (single) polynomial of degree at most $C_0$.

• (ii) If $S,S^\prime \in \mathcal {S}$, then $|S\cap S^\prime |\le C_0$.

• (iii) If $p_1,\ldots ,p_k\in \mathbb {R}^4$ are distinct points, then at most $C_0$ surfaces from $\mathcal {S}$ contain each of the points $p_1,\ldots ,p_k$.

Given a collection of points $\mathcal {P}\subset \mathbb {R}^4$ and a collection of surfaces $\mathcal {S}$ in $\mathbb {R}^4$, we define the set of incidences between $\mathcal {P}$ and $\mathcal {S}$ to be

$$\begin{aligned} {\mathcal {I}}(\mathcal {P},\mathcal {S})=\{(p,S)\in \mathcal {P}\times \mathcal {S}:~ p\in S\}. \end{aligned}$$

Definition 1.3

Let $\mathcal {P}$ be a collection of points, let $\mathcal {S}$ be a collection of two-dimensional real algebraic surfaces in $\mathbb {R}^4$, and let $I\subset {\mathcal {I}}(\mathcal {P},\mathcal {S})$. We say that I is a good collection of incidences if whenever $(p,S),(p,S^\prime )\in I$, we have that $T_p(S)\cap T_p(S^\prime )=p$, i.e., whenever two surfaces are incident to a common point, their tangent planes intersect transversely.

We are now ready to state our results.

Theorem 1.3

(Point-surface incidences in $\mathbb {R}^4$) Let $\mathcal {P}\subset \mathbb {R}^4$ be a collection of m points. Let $\mathcal {S}$ be a $C_0$-good collection of pseudoflats with k degrees of freedom. Let $n=|\mathcal {S}|$, and suppose $m\le n^{(2k+2)/3k}$. Let $I\subset \mathcal {I}(\mathcal {P},\mathcal {S})$ be a good collection of incidences. Then

$$\begin{aligned} |I| \le C_1\big (m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}+m+n\big ). \end{aligned}$$

(1.1)

The constant $C_1$ depends only on $C_0$ and k.

Remark 1.1

The requirement that $m\le n^{(2k+2)/3k}$ is a limitation arising from our proof techniques. We conjecture that the inequality holds for all m and n. For $m\ge n^2$, the inequality is trivial. In Sect. 10, we will discuss progress toward weakening the above restriction on m and n.

Corollary 1.1

(The $k=2$ case) Let $\mathcal {P}\subset \mathbb {R}^4$ be a collection of m points. Let $\mathcal {S}$ be a $C_0$-good collection of pseudoflats with 2 degrees of freedom. Let $n=|\mathcal {S}|$, and suppose $m\le n$. Let $I\subset \mathcal {I}(\mathcal {P},\mathcal {S})$ be a good collection of incidences. Then

$$\begin{aligned} |I| = O(m^{2/3}n^{2/3}+m+n). \end{aligned}$$

(1.2)

The implicit constant depends only on $C_0$.

Corollary 1.2

(2-planes in $\mathbb {R}^4$) Let $\mathcal {P}\subset \mathbb {R}^4$ be a collection of m points and let $\mathcal {S}$ be a collection of n 2-planes in $\mathbb {R}^4$ such that any two planes meet in at most one point. Suppose that $m\le n$. Then the number of point-plane incidences is

$$\begin{aligned} O(m^{2/3}n^{2/3}+m+n). \end{aligned}$$

(1.3)

We can use Corollary 1.2 to recover the Szemerédi–Trotter theorem for complex lines in $\mathbb {C}^2$, which was originally proved by Tóth in [29]. Note that by point-line duality in $\mathbb {C}^2$, we can always assume that the number of lines is at least as great as the number of points. Thus we have:

Corollary 1.3

(complex lines) Let $\mathcal {P}$ be a collection of m points and let $\mathcal {S}$ be a collection of n (complex) lines in $\mathbb {C}^2$. Then the number of point-line incidences is

$$\begin{aligned} O(m^{2/3}n^{2/3}+m+n). \end{aligned}$$

(1.4)

As another corollary, we obtain a Szemerédi–Trotter type theorem for complex unit circles in the complex plane. If $z=(z_1,z_2)\in \mathbb {C}^2$, we can define the complex unit circle centered at z to be the set $C_z=\{(w_1,w_2)\in \mathbb {C}^2:~ (z_1-w_1)^2+(z_2-w_2)^2=1\}$. If we identify $\mathbb {C}^2$ with $\mathbb {R}^4$, then $C_z$ becomes a smooth two-dimensional surface defined by a single polynomial of degree 4. If $\mathcal {S}$ is a collection of such surfaces, then $\mathcal {S}$ is a 4-good collection of pseudoflats with 2 degrees of freedom. If $\mathcal {P}\subset \mathbb {R}^4$ is a collection of points, then we can partition $\mathcal {I}(\mathcal {P},\mathcal {S})$ into O(1) collections $I_1,\ldots ,I_{O(1)}$ so that each is a good collection of incidences (see [23, Cor. 2.7] for details). Finally, if $\mathcal {P}\subset \mathbb {C}^2$ is a collection of points and $\mathcal {S}\subset \mathbb {C}^2$ is a collection of (complex) unit circles, then by point-unit circle duality we can always assume that $|\mathcal {P}|\le |\mathcal {S}|$. Thus we can apply Theorem 1.3 to each of the collections $I_1,\ldots ,I_{O(1)}$ to conclude the following:

Corollary 1.4

(Complex unit circles) Let $\mathcal {P}\subset \mathbb {C}^2$ be a collection of m points, and let $\mathcal {S}$ be a collection of n complex unit circles in $\mathbb {C}^2$. Then the number of point-circle incidences is $O(m^{2/3}n^{2/3}+m+n)$.

1.1 Previous Work

In [29], Tóth extended Szemerédi and Trotter’s original proof to the complex plane. Tóth’s result is specific to complex lines, so it does not (for example) apply to complex unit circles. Solymosi and Tardos [24] gave a simpler proof of the same bound in the special case where the point set is a Cartesian product of the form $A\times B\subset \mathbb {C}^2$.

Edelsbrunner and Sharir [6] obtained incidence results for certain configurations of points and codimension-one hyperplanes in $\mathbb {R}^4$, and Łaba and Solymosi [15] obtained incidence bounds for points and a general class of two-dimensional surfaces in $\mathbb {R}^3$, provided the points satisfied a certain homogeneity condition.

Elekes and Tóth [8] and later Solymosi and Tóth [25] obtained incidence results between points and hyperplanes in $\mathbb {R}^d$, again provided the points satisfied various non-degeneracy and homogeneity conditions.

In [23], Solymosi and Tao used the discrete polynomial partitioning theorem (this is [11, Thm. 4.1], also Theorem 2.2) to obtain bounds for the number of incidences between points and bounded-degree algebraic surfaces satisfying certain non-degeneracy and pseudoflat conditions (i.e., they behaved similarly to hyperplanes). Aside from an $\varepsilon$ loss in the exponent, Solymosi and Tao’s result resolved a conjecture of Tóth on the number of incidences between points and d-flats in $\mathbb {R}^{2d}$ (Tóth conjectured that Solymosi and Tao’s result should hold without the $\varepsilon$ loss in the exponent [28, Conj. 3]). The discrete polynomial partitioning theorem was also used by the author in [30] to obtain incidence results between points and two-dimensional surfaces in $\mathbb {R}^3$ (with no homogeneity condition), and by Kaplan et al.  in [13] to obtain similar bounds on the number of incidences between points and spheres in $\mathbb {R}^3.$

1.2 Proof Sketch

To keep the proof sketch simple, we shall assume that the surfaces in $\mathcal {S}$ are 2-planes, and that every pair of 2-planes is either disjoint or intersect transversely. The actual proof of the theorem (presented in the following sections) will not make these assumptions. The basic idea is as follows. By the assumption that 2-planes must intersect transversely, there can be at most one 2-plane passing through any pair of points. Thus we can use the Cauchy–Schwarz inequality to obtain a rudimentary bound on the cardinality of any collection of point-surface incidences. We will call this the Cauchy–Schwarz bound.

Using the discrete polynomial partitioning theorem, we find a polynomial P of controlled degree (the degree will be a suitable power of m and n) so that $\mathbb {R}^4\backslash \mathbf {Z}_{\mathbb {R}}(P)$ is a union of open cells, such that each cell contains roughly the same number of points from $\mathcal {P}$, and no surface from $\mathcal {S}$ enters too many cells (here $\mathbf {Z}_{\mathbb {R}}(P)$ is the set of points in $\mathbb {R}^4$ at which P vanishes). We can then apply the Cauchy–Schwarz bound within each cell. This allows us to count the incidences occurring between surfaces and points in $\mathcal {P}\backslash \mathbf {Z}_{\mathbb {R}}(P)$. In order to count the remaining incidences, we perform a second-level polynomial partitioning decomposition on the variety $\mathbf {Z}_{\mathbb {R}}(P)$. This gives us a polynomial Q which cuts $\mathbf {Z}_{\mathbb {R}}(P)$ into a collection of three-dimensional cells, which are open in the relative (Euclidean) topology of $\mathbf {Z}_{\mathbb {R}}(P)$. We then apply the Cauchy–Schwarz bound to each of these three-dimensional cells. The only incidences left to count are those between surfaces in $\mathcal {S}$ and points in $\mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q)$.

We can choose P and Q in such a way that $\mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q)$ is a two-dimensional variety in $\mathbb {R}^4$. Let S be a 2-plane from $\mathcal {S}.$ Then S will intersect $\mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q)$ in a union of isolated points (proper intersections) and one-dimensional curves (non-proper intersections); the case where S meets $\mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q)$ in a two-dimensional variety can be dealt with easily. The number of isolated points in the intersection can be bounded by the degrees of the polynomials P and Q (we are working over $\mathbb {R},$ where Bézout’s theorem need not hold, so we need to be a bit careful). Thus the number of incidences between points $p\in \mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q)$ and surfaces $S\in \mathcal {S}$ such that p is an isolated point of $S\cap \mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q)$ can be bounded.

The only remaining task is to bound the number of incidences between points of $\mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q)$ and one-dimensional curves arising from the intersection of $\mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q)$ and surfaces $S\in \mathcal {S}$. To simplify the exposition, we will pretend (in this sketch only!) that $\mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q)$ is a disjoint union of N 2-planes, i.e., $\mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q)=\Pi _1\sqcup \cdots \sqcup \Pi _N$. Then for each plane $\Pi _i,$ $\Pi _i\cap S=L_{S,i}$ is a line on $\Pi _i$. It remains to count the number of incidences between $\mathcal {P}\cap \Pi _i$ and $\{L_{S,i}\}_{S\in \mathcal {S}}.$ The Szemerédi–Trotter theorem for lines in $\mathbb {R}^2$ would give us the bound

$$\begin{aligned} I(\mathcal {P}\cap \Pi _i,\{L_{S,i}\}_{S\in \mathcal {S}})=O( |\mathcal {P}\cap \Pi _i|^{2/3}|\mathcal {S}|^{2/3}+|\mathcal {P}\cap \Pi _i|+|\mathcal {S}|). \end{aligned}$$

(1.5)

However, if we sum (1.5) over the N values of i, we have only bounded the number of incidences by

$$\begin{aligned} O(N^{1/3}|\mathcal {P}|^{2/3}|\mathcal {S}|^{2/3}+|\mathcal {P}|+|\mathcal {S}|). \end{aligned}$$

(1.6)

Since N can be quite large (for example, if $|\mathcal {P}|=|\mathcal {S}|$, then N could be as large as $|\mathcal {P}|^{1/3}$), this is not sufficient. Instead, recall Székely’s proof in [26] of the Szemerédi–Trotter theorem, which uses the crossing lemma (the crossing lemma and all other graph-related results are introduced in Sect. 8). Loosely speaking, we consider the graph drawing $H_i$ on $\Pi _i$ whose vertices are the points of $\mathcal {P}\cap \Pi _i$, and two vertices are connected by an edge if there is a line from $\{L_{i,S}\}_{S\in \mathcal {S}}$ passing through the two points, and the two points are adjacent on the line (i.e., there are no points in between them). Then the number of edges of the graph is comparable to the number of incidences between points and lines, and this is bounded by $\mathcal {C}(H_i)^{1/3}V_i^{2/3}$, where $\mathcal {C}(H_i)$ is the number of times two edges cross in the drawing $H_i$, and $V_i$ is the number of vertices of $H_i$. Thus in place of (1.5), we have

$$\begin{aligned} I(\mathcal {P}\cap \Pi _i,\{L_{S,i}\}_{S\in \mathcal {S}})=O( |\mathcal {P}\cap \Pi _i|^{2/3}|\mathcal {C}(H_i)|^{1/3} + |\mathcal {P}\cap \Pi _i| + |\mathcal {S}|). \end{aligned}$$

(1.7)

The key insight is that

$$\begin{aligned} \sum _{i}|\mathcal {C}(H_i)| \le |\mathcal {S}|^2. \end{aligned}$$

(1.8)

Indeed, every pair of 2-planes $S, S^\prime \in \mathcal {S}$ can intersect in at most one point, and since we assumed the planes $\{\Pi _i\}$ composing $\mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q)$ were disjoint, the intersection point of $S\cap S^\prime$ can occur on $\Pi _i$ for at most one index i. Thus we have

$$\begin{aligned}&\sum _i I(\mathcal {P}\cap \Pi _i,\{L_{S,i}\}_{S\in \mathcal {S}}) \nonumber \\&\quad =O\big (\sum _i\big (|\mathcal {P}\cap \Pi _i|^{2/3}| \mathcal {C}(H_i)|^{1/3} + |\mathcal {P}\cap \Pi _i|+|\mathcal {S}|\big )\big ) \nonumber \\&\quad =O\big ( \big (\sum _i|\mathcal {P}\cap \Pi _i|\big )^{2/3} \big (\sum _i|\mathcal {C}(H_i)|\big )^{1/3} + \sum _i|\mathcal {P}\cap \Pi _i| + \sum _i|\mathcal {S}|\big ) \nonumber \\&\quad =O( |\mathcal {P}|^{2/3}|\mathcal {S}|^{2/3}+|\mathcal {P}|+N|\mathcal {S}|) \nonumber \\&\quad =O(m^{2/3}n^{2/3}+m+Nn). \end{aligned}$$

(1.9)

This is a much better bound than (1.6), and it gives us the desired bound on the number of incidences between surfaces in $\mathcal {S}$ and points lying on $\mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q)$.

Unfortunately, the assumption that $\mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q)$ is a disjoint union of 2-planes need not be true, and dealing with this difficulty will occupy the bulk of the paper. To handle this, we must cut $\mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q)$ into pieces, each of which behaves like a 2-plane (more accurately, each piece is homeomorphic to an open set in $\mathbb {R}^2$), and we need to prove a more general form of the (planar) Szemerédi–Trotter theorem which gives an incidence bound for an arrangement of points of curves based on the number of curve crossings, rather than the number of curves.

1.3 Major Tools and Techniques

We will give a brief overview of the main tools that will be used in the proof of Theorem 1.3. First, we will require some results from real algebraic geometry. Specifically, we will make use of Barone and Basu’s refined bounds on the number of sign conditions of a real algebraic variety. This will be discussed further in Sect. 2.1. Polynomial partitionings will also play a central role. These were first developed by Guth and Katz, and later extended by Kaplan, Matoušek, Safernova, and Sharir, and by the author. These partitionings will be discussed in Sect. 2.3.

We will use some results from algebraic geometry and intersection theory. These will be discussed in Sect. 4. We will also require some elementary results from differential geometry. This will be discussed in Sect. 6. Finally, we will make use of the crossing lemma from topological graph theory. This will be discussed in Sect. 8.

1.4 Notation

Throughout this paper, $C,C_1,C_2,\ldots$ will denote large constants, and $c,c_1,$ $c_2,\ldots$ will denote small (positive) constants.

Definition 1.4

We will say that $A\lesssim B$ or $A=O(B)$ if $A\le CB$ for some constant C that depends only on $C_0$ and k from the statement of Theorem 1.3, and possibly the ambient dimension d (in the statement of Theorem 1.3 we have $d=4$. However we will sometimes state results in greater generality). Sometimes the constant C will appear to depend on other parameters as well. However, these additional parameters will ultimately only depend on $C_0$ and k. If $A\lesssim B$ and $B \lesssim A$, we say $A\approx B$ or $A=\Theta (B)$.

2 Preliminaries: Real Algebraic Geometry and Polynomial Partitions

2.1 Real Algebraic Geometry

2.1.1 Ideals and Varieties

Unless otherwise noted, all polynomials will be (affine) real polynomials, i.e., elements of $\mathbb {R}[x_1,\ldots ,x_d]$. In the first sections of this paper we will deal mainly with real affine varieties; in later sections we will be concerned with both real and complex varieties. Definitions and standard results about real algebraic varieties can be found in [3, 4].

Definition 2.1

A (real) algebraic variety $Z\subset \mathbb {R}^d$ is a set of the form $Z=\bigcap _{i=1}^\ell \{P_i=0\},$ where $P_1,\ldots ,P_\ell \in \mathbb {R}[x_1,\ldots ,x_d]$ are polynomials. Note that we do not require varieties to be irreducible.

Definition 2.2

If $J\subset \mathbb {R}[x_1,\ldots ,x_d]$ is an ideal, we define

$$\begin{aligned} \mathbf {Z}_{\mathbb {R}}(J)=\{x\in \mathbb {R}^d:~ f(x)=0\ \text {for all}\ f\in J\}. \end{aligned}$$

By abuse of notation, if $P\in \mathbb {R}[x_1,\ldots ,x_d]$, then we define $\mathbf {Z}_{\mathbb {R}}(P) = \mathbf {Z}_{\mathbb {R}}((P))$, where (P) is the ideal generated by P. Sometimes we will also need to work over $\mathbb {C}$. We define $\mathbf {Z}_{\mathbb {C}}(J)$ analogously, with $\mathbb {C}^d$ in place of $\mathbb {R}^d$.

Definition 2.3

If $Z\subset \mathbb {R}^d$ is a variety, we define

$$\begin{aligned} {\mathbf {I}}(Z) = \{P\in \mathbb {R}[x_1,\ldots ,x_d]:~\! P(x)=0\ \text {for all}\ x\in Z\}. \end{aligned}$$

2.1.2 Smooth Points and Dimension of a Real Variety

Definition 2.4

Let $Z\subset \mathbb {R}^d$ be a real algebraic variety, and let $z\in Z$. We define the dimension $\dim _{\mathbb {R},z}(Z)$ of Z at z as in  [4, Def. 2.8.11]. Informally, if $\dim _{\mathbb {R},z}(Z)=e,$ then we can find a homeomorphism from a small (Euclidean) neighborhood of $z\in Z$ to the e-dimensional cube $(0,1)^e$. We define

$$\begin{aligned} \dim _{\mathbb {R}}(Z)=\sup _{z\in Z}\dim _{\mathbb {R},z}(Z). \end{aligned}$$

To avoid confusion, if $Z\subset \mathbb {C}^d$ is a (complex) variety, we will denote the (complex) dimension of Z by $\dim _{\mathbb {C}}(Z)$.

Definition 2.5

We define the smooth locus $Z_{{\text {smooth}}}$ as in [4, Sect. 3.3] (to be more precise, we say a point z is in $Z_{{\text {smooth}}}$ if z is smooth in dimension $e=\dim _{\mathbb {R}}(Z)$). Informally, if ${\mathbf {I}}(Z)=(f_1,\ldots ,f_\ell )\subset \mathbb {R}[x_1,\ldots ,x_d]$ and $e=\dim _{\mathbb {R}}(Z)$, then $z\in Z$ is a smooth point of Z if

$$\begin{aligned} {\text {rank}} \left[ \begin{array} {c}\nabla f_1\\ \vdots \\ \nabla {f_{n}} \end{array} \right] =d-e. \end{aligned}$$

Here and throughout this paper, if $f\in \mathbb {R}[x_1,\ldots ,x_d]$, then $\nabla f$ is the vector-valued function $(\tfrac{df}{dx_1},\ldots ,\tfrac{df}{dx_d})$. If $f\in \mathbb {C}[x_1,\ldots ,x_d]$, we can define $\nabla f$ similarly.

If $z\in Z$ is a smooth point, then Z is an e-dimensional real manifold in a small (Euclidean) neighborhood of z. However the converse need not hold.

2.1.3 Real Ideals

Ideals and varieties over $\mathbb {R}$ can have some rather pathological properties. Luckily, there is a class of ideals over $\mathbb {R}$ that behave more sanely. Confusingly, these ideals are called real ideals.

Definition 2.6

An ideal $J\subset \mathbb {R}[x_1,\ldots ,x_d]$ is real if for every sequence $a_1,\ldots ,a_\ell \in \mathbb {R}[x_1,\ldots ,x_d]$, $a_1^2+\cdots +a_\ell ^2\in J$ implies $a_j\in J$ for each $j=1,\ldots ,\ell$.

The following proposition shows that real principal prime ideals and their corresponding real varieties have some of the nice properties of ideals and varieties defined over $\mathbb {C}$.

Proposition 2.1

(see [4, Sect. 4.5]) Let $(P)\subset \mathbb {R}[x_1,\ldots ,x_d]$ be a principal prime ideal. Then the following are equivalent:

• (i) (P) is real.

• (ii) $(P) = {\mathbf {I}} (\mathbf {Z}(P))$.

• (iii) $\dim _{\mathbb {R}} (\mathbf {Z}(P))=d-1$.

• (iv) $\nabla P$ does not vanish identically on $\mathbf {Z}(P)$.

• (v) The sign of P changes somewhere on $\mathbb {R}^d$.

Remark 2.1

In [4], Proposition 2.1 is stated in the more general language of real closed fields. However, $\mathbb {R}$ is an example (indeed, the motivating example) of a real closed field, so the proposition applies to ideals in $\mathbb {R}[x_1,\ldots ,x_d]$.

While not every polynomial $P\in \mathbb {R}[x_1,\ldots ,x_d]$ is a product of irreducible polynomials that generate real ideals, the following lemma shows that for our applications, we can always modify our polynomials to ensure that this is the case.

Lemma 2.1

Let $P\in \mathbb {R}[x_1,\ldots ,x_d]$ be a real polynomial. Then there exists a non-zero real polynomial $\tilde{P}$ such that $\deg \tilde{P}\le \deg P,$ $\mathbf {Z}_{\mathbb {R}}(P)\subset \mathbf {Z}_{\mathbb {R}}(\tilde{P}),$ and the irreducible components of $\tilde{P}$ generate real ideals.

Proof

We will prove the statement by induction on $\deg P$. If $\deg P=1$, then P is irreducible and (P) is real. Now suppose the statement has been proved for all polynomials of degree $\le D$. Let P be a polynomial of degree $D+1$ and factor $P=P_1\ldots P_a.$ If all the irreducible factors of P generate real ideals, we are done. If not, then without loss of generality we can assume that $(P_1)$ does not generate a real ideal. In particular, $\deg P_1\ge 2$. Let v be a generic (with respect to P) real vector.¹ Then $v\cdot \nabla P_1$ is a non-zero polynomial of degree $\deg (P_1)-1$, and by Proposition 2.1(iv), $\mathbf {Z}_{\mathbb {R}}(P_1)\subset \mathbf {Z}_{\mathbb {R}}(v\cdot \nabla P_1)$. Let $P^\prime = (v\cdot \nabla P_1)P_2\cdots P_a$. Then $\deg P^\prime \le D$ and $\mathbf {Z}_{\mathbb {R}}(P)\subset \mathbf {Z}_{\mathbb {R}}(P^\prime )$. We can now apply the induction hypothesis to $P^\prime$ to find a polynomial $\tilde{P}$ so that $\deg (P)\le \deg (P^\prime )\le \deg (\tilde{P})$, and $\mathbf {Z}_{\mathbb {R}}(P)\subset \mathbf {Z}_{\mathbb {R}}(P^\prime )\subset \mathbf {Z}_{\mathbb {R}}(\tilde{P})$. $\square$

Remark 2.2

Examining the above proof, we see that if $P\in \mathbb {R}[x_1,\ldots ,x_d]$ is a square-free polynomial whose irreducible components generate real ideals, and if $v\in \mathbb {R}^d$ is a generic vector, then $\mathbf {Z}_{\mathbb {R}}(P)_{{\text {sing}}}\subset \mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(v\cdot \nabla P)$.

If $\deg P=1$, then $\mathbf {Z}_{\mathbb {R}}(P)$ is smooth, so this statement is not very interesting. If $\deg P\ge 2$, then $v\cdot \nabla P$ is not the zero polynomial, and P and $v\cdot \nabla P$ have no common components (over $\mathbb {R}$). Since P and $v\cdot \nabla P$ are real polynomials, this also implies that P and $v\cdot \nabla P$ have no common components over $\mathbb {C}$. In particular, this means the variety $\mathbf {Z}_{\mathbb {C}}(P)\cap \mathbf {Z}_{\mathbb {C}}(v\cdot \nabla P)$ has codimension two. Complex algebraic varieties will be discussed further in Sect. 4.1.2.

2.1.4 Sign Conditions

Several of the results we will cite refer to strict sign conditions or realizations of realizable strict sign conditions. While we will not use sign conditions in our proof directly, it is useful to understand how they relate to the objects we will be studying.

Definition 2.7

Let ${\mathcal {Q}}\subset \mathbb {R}[x_1,\ldots ,x_d]$ be a collection of non-zero real polynomials. A strict sign condition on ${\mathcal {Q}}$ is a map $\sigma :~ {\mathcal {Q}}\rightarrow \{\pm 1\}$. If $Q\in {\mathcal {Q}}$, we will denote the evaluation of $\sigma$ at Q by $\sigma _Q$.

If $Z\subset \mathbb {R}^d$ is a variety and $\sigma$ is a strict sign condition on ${\mathcal {Q}}$, then we can define the realization of $\sigma$ on Z by

$$\begin{aligned} {\text {Reali}}(\sigma ,{\mathcal {Q}},Z)=\{x\in Z:~ Q(x)\sigma _Q>0\ \text {for all}\ Q\in {\mathcal {Q}}\}. \end{aligned}$$

(2.1)

We define

$$\begin{aligned} \Sigma _{{\mathcal {Q}},Z}=\{\sigma :~ {\text {Reali}}(\sigma ,{\mathcal {Q}},Z)\ne \emptyset \}, \end{aligned}$$

(2.2)

and

$$\begin{aligned} {\text {Reali}}({\mathcal {Q}},Z)=\{{\text {Reali}}(\sigma ,{\mathcal {Q}},Z) :~ \sigma \in \Sigma _{{\mathcal {Q}},Z}\}. \end{aligned}$$

(2.3)

We call ${\text {Reali}}({\mathcal {Q}},Z)$ the collection of realizations of realizable strict sign conditions of ${\mathcal {Q}}$ on Z. Note that if some $Q\in {\mathcal {Q}}$ vanishes identically on Z, then $\Sigma _{{\mathcal {Q}},Z}=\emptyset$ and thus ${\text {Reali}}({\mathcal {Q}},Z)=\emptyset$.

The key observation is that if ${\mathcal {Q}}$ is a collection of non-zero real polynomials, $Q_0=\prod _{Q\in {\mathcal {Q}}}Q$, and if $Z\subset \mathbb {R}^d$ is a variety, then every connected component of $Z\backslash \mathbf {Z}_{\mathbb {R}}(Q)$ is contained in some set from ${\text {Reali}}({\mathcal {Q}},Z)$.

Remark 2.3

The above observation has two implications: First, the number of connected components of $Z\backslash \mathbf {Z}_{\mathbb {R}}(Q)$ bounds the number of sets in ${\text {Reali}}({\mathcal {Q}},Z)$. Second, suppose that $\mathcal {P}\subset Z$ is a collection of points, and at most C points from $\mathcal {P}$ lie in any set from ${\text {Reali}}({\mathcal {Q}},Z)$. Then at most C points lie in any connected component of $Z\backslash \mathbf {Z}_{\mathbb {R}}(Q)$.

2.2 The Topology of Real Varieties: Milnor–Thom Type Theorems

In the proof below, we will find a polynomial whose zero-set partitions Euclidean space into open cells, and we will apply a rudimentary incidence bound to bound the number of incidences inside each cell. To apply this rudimentary bound, we will need to control how many surfaces from $\mathcal {S}$ enter each cell. The theorems in this section will give us the tools to do this.

Theorem 2.1

(Barone and Basu [2, Thm. 5], special case) Let $Q_1,\ldots ,Q_\ell \in \mathbb {R}[x_1,\ldots ,x_d]$. Let $D_i = \deg (Q_i)$. For $i=1,\ldots ,\ell$, let ${\mathcal {Q}}_i=\{Q_1,\ldots ,Q_i\}$, and let $V_i=\bigcap _{j=1}^i \mathbf {Z}_{\mathbb {R}}(Q_j)$. Suppose that $\dim _{\mathbb {R}}(V_i)\le e_i$ for each index i (by convention, $V_0=\mathbb {R}^d,$ and $e_0 = d$). Let $P\in \mathbb {R}[x_1,\ldots ,x_d]$, and let $D=\deg P$.

Suppose that

$$\begin{aligned} 2\le D_1\le D_2 \le \tfrac{1}{d+1}D_3 \le \tfrac{1}{(d+1)^2}D_4\le \cdots \le \tfrac{1}{(d+1)^{\ell -2}}D_\ell \le D \end{aligned}$$

(2.4)

and that $\ell \le d$. Then the number of (Euclidean) connected components of the set

$$\begin{aligned} \{x\in V_{\ell }:P(x)> 0\} \end{aligned}$$

is bounded by

$$\begin{aligned} CD^{e_{\ell }}\prod _{j=1}^{\ell }D_j^{e_{j-1}-e_j}, \end{aligned}$$

(2.5)

where the constant C depends only on d.

Remark 2.4

The bound (2.5) is a special case of the bound from [2, Thm. 5]. In [2], (2.5) appears as the inequality preceding Remark 1.13.

In [2], Barone and Basu consider a family of polynomials, while in our formulation the family is just the singleton $\{P\}$. Furthermore, Barone and Basu bound the number of connected components of all sign conditions of this family of polynomials on the variety $V_{\ell }$, while we are only interested in the sign condition $P>0$. Finally, Barone and Basu state their result for semialgebraically connected components over a real closed field. Since we are only interested in results over $\mathbb {R}$, we can restrict our attention to Euclidean connected components.

We will always be interested in the case $d=4$. We shall record three special cases that will be of particular interest to us.

Corollary 2.1

Let $f,P\in \mathbb {R}[x_1,\ldots ,x_4]$. Suppose that

• (i) $\dim _{\mathbb {R}}(\mathbf {Z}_{\mathbb {R}}(f))=2$.

• (ii) $\dim _{\mathbb {R}}(\mathbf {Z}_{\mathbb {R}}(f)\cap \mathbf {Z}_{\mathbb {R}}(P))=1$.

Then

• The number of connected components of $\{x\in \mathbf {Z}_{\mathbb {R}}(f):~ P(x)>0\}$ is $O( (\deg P)^2)$.

• The number of connected components of $\mathbf {Z}_{\mathbb {R}}(f)\cap \mathbf {Z}_{\mathbb {R}}(P)$ is $O((\deg P)^2)$.

The implicit constants depend only on $\deg f$.

Corollary 2.2

Let $f,P,Q\in \mathbb {R}[x_1,\ldots ,x_4]$. Suppose that f and P satisfy Properties (i) and (ii) from Corollary 2.1, and that $\deg P\le C\deg Q$. Then

• The number of connected components of

  $$\begin{aligned} \{x\in \mathbf {Z}_{\mathbb {R}}(f)\cap \mathbf {Z}_{\mathbb {R}}(P):~ Q(x)>0\} \end{aligned}$$

  is $O\big ((\deg P)(\deg Q)\big ).$

• The number of isolated points of

  $$\begin{aligned} \mathbf {Z}_{\mathbb {R}}(f)\cap \mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q) \end{aligned}$$

  is $O\big ((\deg P)(\deg Q)\big )$.

Again, the implicit constant depends only on $\deg f$ and the constant C.

Remark 2.5

Corollary 2.1 (resp. Corollary 2.2) is only meaningful if the degree of P (resp. P and Q) is much larger than the degree of f. In practice, the degree of f will be bounded by quantities that depend only on the constants $C_0$ and k from the statement of Theorem 1.3, while the degrees of P and Q will grow as the quantities m and n from the statement of Theorem 1.3 become larger.

2.3 Polynomial Partitioning Type Theorems

In [11], Guth and Katz proved the following theorem.

Theorem 2.2

(Discrete polynomial partitioning theorem) Let $\mathcal {P}$ be a set of m points in $\mathbb {R}^d$ and let $D\ge 1$ be an integer. Then there is a polynomial P of degree at most D with the following property: $\mathbb {R}^d \backslash \mathbf {Z}_{\mathbb {R}}(P)$ is the union of $O(D^d)$ open connected sets (cells), and each cell contains $\le m/D^d$ points of $\mathcal {P}$.

After applying Lemma 2.1, we can ensure that the irreducible components of P generate real ideals:

Corollary 2.3

Let $\mathcal {P}$ be a set of m points in $\mathbb {R}^d$ and let $D\ge 1$ be an integer. Then there is a polynomial P of degree at most D with the following property: $\mathbb {R}^d \backslash \mathbf {Z}_{\mathbb {R}}(P)$ is the union of $O(D^d)$ open connected sets (cells), and each cell contains $\le m/D^d$ points of $\mathcal {P}$. Furthermore, each irreducible component of P generates a real ideal.

Example 2.1

Consider the following collection of 72 points:

$$\begin{aligned} \mathcal {P}= \bigcup _{j=1}^3 \{(\pm j ,\pm j ,\pm j,\pm j)\}\cup \bigcup _{j=1}^3 \{(0 ,\pm j ,\pm j,\pm j)\}, \end{aligned}$$

(2.6)

and let $D=2$. Then the degree four polynomial

$$\begin{aligned} P(x_1,x_2,x_3,x_4)= x_1x_2x_3x_4 \end{aligned}$$

cuts $\mathbb {R}^4$ into 16 open cells $\Omega _1,\ldots ,\Omega _{16}$ (the cells are unbounded, but this is fine) plus the set

$$\begin{aligned} \mathbf {Z}_{\mathbb {R}}(P) = \bigcup _{i=1}^4\{x_i=0\}. \end{aligned}$$

We can verify that the polynomials $x_1,\ldots ,x_4$ generate real ideals, so P is a product of irreducible polynomials, each of which generates a real ideal. We have $|\Omega _i\cap \mathcal {P}|=3\le |\mathcal {P}|/D^4$ for each $i=1,\ldots ,16$. Thus P satisfies the requirements of Corollary 2.3 (Corollary 2.3 only specifies the degree of P up to an implicit constant, so we cannot verify that the degree is correct). Finally, note that we have $|Z\cap \mathcal {P}|=16.$

Example 2.2

Let $\mathcal {P}\subset \mathbb {R}^4$ be a large collection of points that lie in general position on the 2-plane $\{x_1=x_2=0\}$, and let D be much smaller than $|\mathcal {P}|^{1/4}.$ Then we can verify that the polynomial $P(x_1,x_2,x_3,x_4)=x_1$ satisfies the requirements of Corollary 2.3; $\mathbf {Z}_{\mathbb {R}}(P)$ cuts $\mathbb {R}^4$ into the two cells, $\Omega _1=\{x_1>0\}$ and $\Omega _2=\{x_1<0\}$. We have $\Omega _1\cap \mathcal {P}=\emptyset$ and $\Omega _2\cap \mathcal {P}=\emptyset .$ This phenomenon is unavoidable: any polynomial P satisfying the requirements of Corollary 2.3 must contain a factor that vanishes on the 2-plane $\{x_1=x_2=0\}$ (provided the points of $\mathcal {P}$ are in general position). Thus we must have $\mathcal {P}\subset \mathbf {Z}_{\mathbb {R}}(P),$ so each of the cells of the decomposition $\mathbb {R}\backslash \mathbf {Z}_{\mathbb {R}}(P)$ will be empty.

This example is interesting for the following reason. Let $(\mathcal {P}_1,{\mathcal {L}}_1)$ be a collection of m points and n lines in $\mathbb {R}^2$ that determine $\Theta (m^{2/3}n^{2/3}+m+n)$ incidences. Consider $(\mathcal {P}_1,{\mathcal {L}}_1)$ as a collection of complex points and complex lines in $\mathbb {C}^2$. Now, identify $\mathbb {C}^2$ with $\mathbb {R}^4$, and let $(\mathcal {P},\mathcal {S})$ be the corresponding collection of points and 2-planes in $\mathbb {R}^4$. Then all of the points of $\mathcal {P}$ will lie on a common 2-plane, so the situation will resemble this example.

Theorem 2.2 will be used to obtain the first-level decomposition of the point set $\mathcal {P}$. However, as seen in the above examples, many points may lie on the boundary $\mathbf {Z}_{\mathbb {R}}(P),$ and we will need to bound the number of incidences between surfaces in $\mathcal {S}$ and points on $\mathbf {Z}_{\mathbb {R}}(P)$. To do this, we shall perform a second discrete polynomial partitioning decomposition on the algebraic variety $\mathbf {Z}_{\mathbb {R}}(P)$.

Theorem 2.3

(Polynomial partitioning decomposition on a hypersurface) Let $\mathcal {P}$ be a collection of points in $\mathbb {R}^d$ lying on the set $\mathbf {Z}_{\mathbb {R}}(P),$ where P is an irreducible polynomial of degree D that generates a real ideal. Let $E\ge cD$. Then there exists a polynomial $Q\in \mathbb {R}[x_1,\ldots ,x_d]$ with the following properties:

• (i) $\deg Q \le C E$.

• (ii) Q does not vanish identically on $\mathbf {Z}_{\mathbb {R}}(P)$. In particular, $\dim _{\mathbb {R}}(\mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q))\le d-2.$

• (iii) The set $\mathbf {Z}_{\mathbb {R}}(P)\backslash \mathbf {Z}_{\mathbb {R}}(Q)$ is a union of $O(DE^{d-1})$ connected components (cells). Each cell contains at most $\tfrac{C|\mathcal {P}|}{DE^{d-1}}$ points from $\mathcal {P}$.

• (iv) Each irreducible component of Q generates a real ideal.

The constant C depends only on c and the dimension d.

Theorem 2.3 is proved in [30, Sect. A.3]. The theorem is stated in terms of realizations of strict sign conditions (discussed in Sect. 2.1.4) rather than cells. The version stated in [30, Sect. A.3] bounds the number of points that can lie in any realization of a realizable strict sign condition on $\mathbf {Z}_{\mathbb {R}}(P)$. However, as noted in Remark 2.3, the version stated above follows immediately.

We can continue Examples 2.1 and 2.2.

Example 2.1 $^{\prime }$ Let $\mathcal {P},$ D, P,  and Z be as in Example 2.1. Then $P_1(x_1,x_2,x_3,x_4)=x_1$ is the only irreducible component of P whose zero-set contains points from $\mathcal {P}$. Let $E=2$ and let ${\mathcal {Q}}=\{x_2,x_3,x_4\}.$ Then $\mathbf {Z}_{\mathbb {R}}(P_1)\backslash \mathbf {Z}_{\mathbb {R}}(Q)$ consists of the 8 octants of $\mathbb {R}^3$, where we identify $\mathbb {R}^3$ with the hyperplane $\{x_1=0\}$ in $\mathbb {R}^4$. Each of these components contains 2 points from $\mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(P_1)$, and

$$\begin{aligned} \mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(P_1)\cap \bigcup _{j=2}^4\{x_j=0\}=\emptyset , \end{aligned}$$

i.e., every point of $\mathcal {P}$ either lies in some cell of $\mathbb {R}^4\backslash \mathbf {Z}_{\mathbb {R}}(P_1)$ or some connected component of $\mathbf {Z}_{\mathbb {R}}(P_1)\backslash \mathbf {Z}_{\mathbb {R}}(Q)$.

Example 2.2 $^{\prime }$ Let $\mathcal {P},$ D, and P be as in Example 2.2, and let E be much smaller than $|\mathcal {P}|^{1/3}.$ Let ${\mathcal {Q}} = \{x_2\}$. Then $\mathbf {Z}_{\mathbb {R}}(P)\backslash \mathbf {Z}_{\mathbb {R}}(Q)$ consists of the sets $\{ x_1=0,x_2>0\}$ and $\{ x_1=0,x_2<0\}.$ Neither of these sets contains any points from $\mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(P)$; indeed, $\mathcal {P}\subset \{x_1=x_2=0\}=\mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(Q)$. Thus ${\mathcal {Q}}$ satisfies the requirements of Theorem 2.3, but none of the points of $\mathcal {P}$ lie in any cell of $\mathbb {R}^4\backslash \mathbf {Z}_{\mathbb {R}}(P)$ nor in any connected component of $\mathbf {Z}_{\mathbb {R}}(P)\backslash \mathbf {Z}_{\mathbb {R}}(Q)$. Sections 4–9 will be devoted to dealing with this type of situation.

3 Proof of Theorem 1.3 Step 1: Cell Partitionings

3.1 Initial Reductions

Let $\mathcal {P},\mathcal {S}$ be as in the statement of Theorem 1.3. First, it suffices to prove Theorem 1.3 in the special case where all the surfaces $S\in \mathcal {S}$ are irreducible. If the surfaces are reducible, then each $S\in \mathcal {S}$ can be written as $S=S_1\cup S_2\cup \cdots \cup S_{C(S)}$, where $C(S)\le C_0$ and each $S_i$ is a smooth irreducible two-dimensional surface. Since S is smooth, the surfaces $\{S_1,\ldots ,S_{C(S)}\}$ are disjoint.

Now, for each $i=1,\ldots ,C_0$, let $\mathcal {S}_i = \{S_i:~ S\in \mathcal {S}\ \text {and}\ C(S)\le i \}.$ Then $\mathcal {S}_i$ is a $C_0$-good collection of pseudoflats, and $I_i=I\cap {\mathcal {I}}(\mathcal {P},\mathcal {S}_i)$ is a good collection of incidences. We can then consider each collection $(\mathcal {P},\mathcal {S}_i,I_i)$ in turn.

Henceforth, we shall assume that all surfaces in $\mathcal {S}$ are irreducible. We will prove Theorem 1.3 by induction on $m+n$. In contrast to the proof of Solymosi and Tao in [23], the use of induction will not introduce an $\varepsilon$ loss in the exponent. The induction is merely used to streamline the argument by controlling a few minor terms in one of the bounds in Sect. 3.4. These terms can also be controlled through a lengthier argument that does not involve induction. An analogue of this lengthier argument appears around Eq. (2.9) in [30].

The base case where $m+n$ is small is obvious, provided we choose the constant $C_1$ from Theorem 1.3 to be larger than mn.

We will frequently make use of the following classical theorem of Kővari, Sós, and Turán from [14]:

Theorem 3.1

Let s, t be fixed positive integers, and let G be a bipartite graph with one vertex set of size a and one vertex set of size b. Suppose that G contains no induced subgraph isomorphic to $K_{s,t}$. Then G has at most $O(ba^{1-1/s} + a)$ edges. Symmetrically, G has at most $O(ab^{1-1/t} + b)$ edges. Here the implicit constants depend only on s and t.

From this theorem, we have that

$$\begin{aligned} |{\mathcal {I}}(\mathcal {P},\mathcal {S})|&\lesssim mn^{1-1/k}+n, \end{aligned}$$

(3.1)

$$\begin{aligned} |{\mathcal {I}}(\mathcal {P},\mathcal {S})|&\lesssim m^{1/2} n+m. \end{aligned}$$

(3.2)

In particular, we can assume

$$\begin{aligned} n < c_1m^k, \quad m < c_1n^2, \end{aligned}$$

(3.3)

where $c_1$ is a small constant that we are free to determine later; we can make $c_1$ smaller by making the constant $C_1$ from Theorem 1.3 larger. If (3.3) failed, then Theorem 1.3 would follow immediately from (3.1) or (3.2). The bounds (3.3) imply that

$$\begin{aligned} n\le c_2m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}, \quad m \le c_2m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}, \end{aligned}$$

(3.4)

where $c_2$ can be made arbitrarily small by making the constant $c_1$ from (3.3) sufficiently small. These inequalities will be useful for closing the induction.

3.2 First Polynomial Partition

Let

$$\begin{aligned} D=m^{\tfrac{k}{4k-2}}n^{-\tfrac{1}{4k-2}}. \end{aligned}$$

(3.5)

By (3.3), D satisfies the inequalities

$$\begin{aligned} C_2<D<c_3 m^{1/4}, \end{aligned}$$

(3.6)

where we can make the constant $C_2$ arbitrarily large and $c_3$ arbitrarily small by making the constant $c_1$ in (3.3) smaller.

Let P be a polynomial of degree at most D such that $\mathbf {Z}_{\mathbb {R}}(P)$ cuts $\mathbb {R}^4$ into $O(D^4)$ cells $\{\Omega _i\}$, each containing $O(m/D^4)$ points, as given by Corollary 2.3. We can assume that P is square-free and its irreducible components generate real ideals. Let $n_i$ be the number of surfaces in $\mathcal {S}$ that meet the ith cell.

Lemma 3.1

$$\begin{aligned} \sum n_i \lesssim D^2 n, \end{aligned}$$

(3.7)

where the sum is taken over all cells in the decomposition.

Proof

We will show that each surface in $\mathcal {S}$ enters $O(D^2)$ cells. Let $S\in \mathcal {S},$ let $f_S$ be a polynomial so that $S=\mathbf {Z}_{\mathbb {R}}(f_S)$, and let P be the partitioning polynomial described above. We can assume that $\dim _{\mathbb {R}}(S\cap \mathbf {Z}_{\mathbb {R}}(P^2))\le 1$, since otherwise S enters no cells. The polynomials $f_S$ and $P^2$ satisfy the requirements of Corollary 2.1, so the number of connected components of $S\cap \{P^2>0\}$ is $O(D^2)$. Thus S enters $O(D^2)$ connected components of $\mathbb {R}^4\backslash \mathbf {Z}_{\mathbb {R}}(P)$, i.e., S enters $O(D^2)$ cells. $\square$

Applying Theorem 3.1 inside each cell, we obtain

$$\begin{aligned} |I\cap {\mathcal {I}}(\mathcal {P}\backslash \mathbf {Z}_{\mathbb {R}}(P),\mathcal {S})|\lesssim & {} \sum _i|\mathcal {P}\cap \Omega _i|n_i^{1-1/k}+\sum _i n_i\nonumber \\\lesssim & {} \sum _i \tfrac{m}{D^4} n_i^{1-1/k}+D^2n\nonumber \\\lesssim & {} \tfrac{m}{D^4}\big (\sum _i 1\big )^{1/k}\big (\sum _i n_i\big )^{1-1/k}+D^2n\nonumber \\\lesssim & {} \tfrac{m}{D^4} D^{4/k}(D^2n)^{1-1/k}+D^2n\nonumber \\\lesssim & {} m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}. \end{aligned}$$

(3.8)

Here we used Hölder’s inequality on the third line, Lemma 3.1 on the fourth line (plus the fact that there are $O(D^4)$ cells), and the definition of D from (3.5) on the final line.

Recall from Definition 1.4 that the implicit constants above depend only on $C_0$ and k from the statement of Theorem 1.3. Thus, if we select $C_1$ in the statement of Theorem 1.3 sufficiently large (depending on $C_0$ and k), we have

$$\begin{aligned} |I\cap {\mathcal {I}}(\mathcal {P}\backslash \mathbf {Z}_{\mathbb {R}}(P),\mathcal {S})| \le \tfrac{C_1}{100}\big (m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}+m+n\big ). \end{aligned}$$

(3.9)

3.3 Boundary Incidences of the First Partition

Write

$$\begin{aligned} \mathcal {S}=\mathcal {S}_1\sqcup \mathcal {S}_2, \end{aligned}$$

(3.10)

where $\mathcal {S}_1$ is the set of surfaces that are contained in $\mathbf {Z}_{\mathbb {R}}(P)$, and $\mathcal {S}_2$ is the set of surfaces that properly intersect $\mathbf {Z}_{\mathbb {R}}(P)$ (since each surface is irreducible, the latter type of intersection must have dimension at most 1).

Lemma 3.2

$$\begin{aligned} |I\cap {\mathcal {I}}(\mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(P)_{{\text {smooth}}},\mathcal {S}_1)|\le m. \end{aligned}$$

(3.11)

Proof

Let $p\in \mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(P)_{{\text {smooth}}},$ and let $H = T_p(\mathbf {Z}_{\mathbb {R}}(P)).$ Suppose there exist surfaces $S_1,S_2\in \mathcal {S}_1$ with $(p,S_1),\ (p,S_2)\in I$. By Property (i) from Definition 1.2, p is a smooth point of S and of $S^{\prime }$. Since $S\subset \mathbf {Z}_{\mathbb {R}}(P)$, we have $T_p(S)\subset T_p(\mathbf {Z}_{\mathbb {R}}(P))=\Pi$. Similarly, $T_p(S^\prime )\subset \Pi$. On the other hand, from the definition of a good collection of incidences (Definition 1.3), we have that $T_p(S)\cap T_p(S^\prime )=p.$ Thus we have two affine 2-planes, $T_p(S)$ and $T_p(S^\prime )$ which meet only at the point p, but both are contained in the affine 3-plane $\Pi$. This cannot occur. Thus for each point $p\in \mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(P)_{{\text {smooth}}},$ there exists at most one surface $S\in \mathcal {S}_1$ with $(p,S)\in I(\mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(P)_{{\text {smooth}}},\mathcal {S}_1)$. $\square$

It remains to consider incidences between surfaces and points lying on $\mathbf {Z}_{\mathbb {R}}(P)_{{\text {sing}}}$. By (3.6), we can assume $\deg P\ge 2$. Let v be a generic (with respect to P) vector and let $R=v\cdot \nabla P$. By Remark 2.2, R is not the zero polynomial, $\mathbf {Z}_{\mathbb {R}}(P)_{{\text {sing}}}\subset \mathbf {Z}_{\mathbb {R}}(P)\cap \mathbf {Z}_{\mathbb {R}}(R)$, and $\dim _{\mathbb {C}}(\mathbf {Z}_{\mathbb {C}}(P)\cap \mathbf {Z}_{\mathbb {C}}(R))=2$.

Let $\mathcal {S}_1^\prime \subset \mathcal {S}_1$ be those surfaces contained in $\mathbf {Z}_{\mathbb {R}}(P)_{{\text {sing}}}.$ If $S\in \mathcal {S}_1^\prime$ and $S^*$ is the complexification of S (the smallest complex variety in $\mathbb {C}^4$ that contains S), then $S^*\subset \mathbf {Z}_{\mathbb {C}}(P)\cap \mathbf {Z}_{\mathbb {C}}(R).$ Since $\dim _{\mathbb {C}}(\mathbf {Z}_{\mathbb {C}}(P)\cap \mathbf {Z}_{\mathbb {C}}(R))=2,$ we must have that $S^*$ is a union of irreducible components of $\mathbf {Z}_{\mathbb {C}}(P)\cap \mathbf {Z}_{\mathbb {C}}(R)$. Furthermore, if $S_1,\ldots ,S_\ell \in \mathcal {S}_1^\prime$, then $S_1^*\cup \cdots \cup S_\ell ^*$ must contain at least $\ell$ irreducible components. But by Bézout’s theorem (discussed further in Sect. 4.5, or [12, Chap. 18]), $\mathbf {Z}_{\mathbb {C}}(P)\cap \mathbf {Z}_{\mathbb {C}}(R)$ can contain at most $(\deg P)(\deg R)\lesssim D^2$ irreducible components. We conclude that

$$\begin{aligned} |\mathcal {S}_1^\prime |\lesssim D^2. \end{aligned}$$

(3.12)

Applying Theorem 3.1 and (3.6), we have

$$\begin{aligned} |I\cap {\mathcal {I}}(\mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(P)_{{\text {sing}}},\mathcal {S}_1^\prime )| \lesssim D^2 m^{1/2} + m \lesssim m. \end{aligned}$$

Thus if we choose the constant $C_1$ sufficiently large depending on $C_0$ and k from the statement of Theorem 1.3, we have

$$\begin{aligned} |I\cap {\mathcal {I}}(\mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(P)_{{\text {sing}}}, \mathcal {S}_1^\prime )| \le \frac{C_1}{100}\big (m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}+m+n \big ). \end{aligned}$$

(3.13)

Let $\mathcal {S}_2^\prime \subset \mathcal {S}_1$ be those surfaces (contained in $\mathbf {Z}_{\mathbb {R}}(P)$) that are not contained in $\mathbf {Z}_{\mathbb {R}}(R)$. We must now bound $|I\cap {\mathcal {I}}(\mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(P),\mathcal {S}_2)|$ and $|I\cap {\mathcal {I}}(\mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(R),\mathcal {S}_2^\prime )|$. By Lemma 2.1, we can assume that the irreducible components of R generate real ideals. But note that both $\mathbf {Z}_{\mathbb {R}}(P)$ and $\mathbf {Z}_{\mathbb {R}}(R)$ are the zero-set of polynomials of degree O(D), and thus the two collections of incidences can be dealt with in the same fashion. In the arguments below, we will prove that

$$\begin{aligned} |I\cap {\mathcal {I}}(\mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(P), \mathcal {S}_2)|\le \tfrac{C_1}{10} \big (m^{\tfrac{k}{2k-1}} n^{\tfrac{2k-2}{2k-1}}+m+n\big ). \end{aligned}$$

(3.14)

An identical argument shows that

$$\begin{aligned} |I\cap {\mathcal {I}}(\mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(R), \mathcal {S}_2^\prime )|\le \tfrac{C_1}{10} \big (m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}+m+n\big ). \end{aligned}$$

(3.15)

Once we have established these inequalities, we can combine the bounds (3.9), (3.11), (3.13), (3.14), and (3.15) to close the induction.

3.4 Second Polynomial Partitioning Decomposition

We shall now establish inequality (3.14). Factor P into its irreducible components, $P=P_1\cdots P_\ell ,$ and let $D_i=\deg (P_i)$. Let

$$\begin{aligned} \mathcal {P}_i =(\mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(P_i))\backslash \bigcup _{j<i}\mathcal {P}_j, \end{aligned}$$

so $\mathcal {P}_1,\ldots ,\mathcal {P}_\ell$ are disjoint and $\bigcup \mathcal {P}_i = \mathcal {P}\cap \mathbf {Z}_{\mathbb {R}}(P)$.

Let

(3.16)

The (small) constant $c_4$ will be chosen later.

3.4.1 Incidences on Varieties in ${\mathcal {A}}_0$

We have

$$\begin{aligned} \big |\bigcup _{j\in {\mathcal {A}}_0}\mathcal {P}_j\big |\le & {} c_4^{1/k} \sum _{j\in A_0}n^{1/k}D_j^{\tfrac{4k-2}{k}} \nonumber \\\le & {} c_4^{1/k} n^{1/k}D^{\tfrac{4k-2}{k}} \nonumber \\\le & {} c_4^{1/k}m, \end{aligned}$$

(3.17)

We will select $c_4$ so that $c_4 <\!\!< 1$. By the induction hypothesis (discussed in Sect. 3.1), we conclude that

$$\begin{aligned} \big |I\cap {\mathcal {I}}\big ( \bigcup _{j\in A_0}\mathcal {P}_j, \mathcal {S}\big )\big | \le C_1 \big (c_4^{\tfrac{1}{2k-1}}m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}} + C_3c_4^{1/k}m + n\big ). \end{aligned}$$

(3.18)

Select the constant $c_1$ from (3.3) sufficiently small so that

$$\begin{aligned} n\le \tfrac{1}{200}m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}, \end{aligned}$$

and select the constant $c_4$ from (3.16) sufficiently small. Then from (3.4) we obtain

$$\begin{aligned} \big |I\cap {\mathcal {I}}\big ( \bigcup _{j\in A_0}\mathcal {P}_j, \mathcal {S}\big )\big | \le \tfrac{C_1}{100}\big (m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}+m+n\big ). \end{aligned}$$

(3.19)

3.4.2 Incidences on Varieties in ${\mathcal {A}}_1$

For each $i\in {\mathcal {A}}_1$, define

$$\begin{aligned} E_i = |\mathcal {P}_i|^{\tfrac{k}{3k-2}}n^{-\tfrac{1}{3k-2}}D_i^{-\tfrac{k}{3k-2}}. \end{aligned}$$

(3.20)

Note that with this choice of $E_i$, we have

$$\begin{aligned} E_i \ge c_4^{\tfrac{1}{3k-2}} D_i, \end{aligned}$$

(3.21)

where $c_4$ is the constant from (3.16).

By (3.5), (3.20), and Hölder’s inequality,

$$\begin{aligned} n\sum _{j\in {\mathcal {A}}_1} D_jE_j \le m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}. \end{aligned}$$

(3.22)

This fact will be used frequently.

Apply Theorem 2.3 to the surface $\mathbf {Z}_{\mathbb {R}}(P_i)$ and the point set $\mathcal {P}_i$ with the parameter $E_i$ [here we make use of (3.21)], and let $Q_i$ be the resulting polynomial. $Q_i$ has degree $O(E_i)$, where the implicit constant depends only on $c_4$, and the set $\mathbf {Z}_{\mathbb {R}}(P_i)\backslash \mathbf {Z}_{\mathbb {R}}(Q_i)$ is a union of $O(D_iE_i^3)$ cells; each cell contains $O( |\mathcal {P}_i|/(D_iE_i^3))$ points from $\mathcal {P}_i$. Again, the implicit constant depends only on $c_4$ from (3.16), which in turn ultimately depends only on $C_0$ and k from the statement of Theorem 1.3.

Let $n_{i,j}$ be the number of surfaces in $\mathcal {S}_2$ that meet the jth cell from $\mathbf {Z}_{\mathbb {R}}(P_i)\backslash \mathbf {Z}_{\mathbb {R}}(Q_i)$.

Lemma 3.3

For each index i, we have

$$\begin{aligned} \sum _j n_{i,j}\lesssim nD_iE_i, \end{aligned}$$

(3.23)

where the sum is taken over all cells in $\mathbf {Z}_{\mathbb {R}}(P_i)\backslash \mathbf {Z}_{\mathbb {R}}(Q_i)$.

Proof

We will prove that each surface in $\mathcal {S}_2$ enters $O(D_iE_i)$ cells. Let $S\in \mathcal {S},$ and let $f_S$ be a polynomial so that $S=\mathbf {Z}_{\mathbb {R}}(f_S)$. Since $S\in \mathcal {S}_2$, we have that $\dim _{\mathbb {R}}(S\cap \mathbf {Z}_{\mathbb {R}}(P_i))\le 1$. Thus we can apply Corollary 2.2 to conclude that the number of connected components of $S\cap \mathbf {Z}_{\mathbb {R}}(P_i)\cap \{Q_i^2>0\}$ is $O(D_iE_i)$. This implies that S enters $O(D_iE_i)$ cells, where the implicit constants depend only on $C_0$ from the statement of Theorem 1.3. $\square$

We shall now bound the number of incidences that occur in the cells $\Omega _{i,j}$. Recall that at the moment, i is fixed. We have

$$\begin{aligned} |I\cap {\mathcal {I}}(\mathcal {P}_i\backslash \mathbf {Z}_{\mathbb {R}}(Q_i), \mathcal {S}_2)|\lesssim & {} \sum _{j}|\mathcal {P}_i\cap \Omega _{i,j}|n_{i,j}^{1-1/k} + \sum _j n_{i,j} \nonumber \\\lesssim & {} \Big (\sum _j \Big (\frac{|\mathcal {P}_i|}{D_iE_i^3}\Big )^k\Big )^{1/k}\Big (\sum _j n_{i,j}\Big )^{1-1/k}+D_iE_in \nonumber \\\lesssim & {} (D_iE_i^3 |\mathcal {P}_i|^k D_i^{-k}E_i^{-3k})^{1/k}(D_iE_i n)^{1-1/k}+D_iE_in \nonumber \\\lesssim & {} \frac{|\mathcal {P}_i|n^{1-1/k}}{E_i^{2-2/k}} + D_iE_in. \end{aligned}$$

(3.24)

Summing over all indices $i\in {\mathcal {A}}_1$ and using (3.5), (3.20), and Hölder’s inequality, we obtain

$$\begin{aligned} \sum _{i\in {\mathcal {A}}_1} |I\cap {\mathcal {I}}(\mathcal {P}_i\backslash \mathbf {Z}_{\mathbb {R}}(Q_i), \mathcal {S}_2)|\lesssim & {} \sum _{i\in {\mathcal {A}}_1} \frac{|\mathcal {P}_i|n^{1-1/k}}{E_i^{2-2/k}} + \sum _{i\in {\mathcal {A}}_1}D_iE_in \nonumber \\\lesssim & {} \sum _{i\in {\mathcal {A}}_1} n^{\tfrac{3k-3}{3k-2}}|\mathcal {P}_i|^{\tfrac{k}{3k-2}}D_i^{\tfrac{2k-2}{3k-2}} + m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}} \nonumber \\\lesssim & {} n^{\tfrac{3k-3}{3k-2}}m^{\tfrac{k}{3k-2}}D^{\tfrac{2k-2}{3k-2}} + m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}} \nonumber \\\lesssim & {} m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}. \end{aligned}$$

(3.25)

Combining (3.19) and (3.25), and selecting $C_1$ sufficiently large depending on $C_0$ and k from the statement of Theorem 1.3, we obtain

$$\begin{aligned} |I\cap \mathcal {I}(\mathcal {P}\cap Z,\mathcal {S}_2)|\le & {} \frac{C_1}{50} \big (m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}+m+n\big ) \nonumber \\&+\sum _{i\in {\mathcal {A}}_1} |I\cap {\mathcal {I}}(\mathcal {P}_i \cap \mathbf {Z}_{\mathbb {R}}(Q_i),\mathcal {S}_2)|. \end{aligned}$$

(3.26)

It remains to bound the second term in (3.26).

4 A Foray into Algebraic Geometry

4.1 (Some More) Real Algebraic Geometry

4.1.1 Semialgebraic Sets

A semialgebraic set is a finite union of sets of the form

where $R_1,\ldots ,R_{\ell }$ and $R^\prime _1,\ldots ,R^\prime _{\ell ^\prime }$ are real polynomials.

Later in our arguments we will need to consider (real) algebraic curves with finitely many points deleted. These objects are semialgebraic sets.

4.1.2 Real and Complex Varieties

If $Z\subset \mathbb {C}^d$ is a complex variety, let

Thus $Z(\mathbb {R})$ is the set of real points of Z. Generally, we will be interested in varieties $Z\subset \mathbb {C}^d$ that can be defined by real polynomials. Conversely, if $Z\subset \mathbb {R}^d$ is a real variety, let $Z^*$ be the smallest complex variety containing Z, i.e., $Z^*$ is the closure of Z (after Z has been embedded into $\mathbb {C}^d$) in the Zariski topology on $\mathbb {C}^d$. Observe that if $Z(\mathbb {R})$ is Zariski dense in Z, then $Z(\mathbb {R})^*=Z$; we will only use this observation in the special case where Z is irreducible.

4.1.3 The Zariski Tangent Space of a Variety

Definition 4.1

Let $Z\subset \mathbb {C}^d$ be a variety. We define the Zariski tangent space of Z at the point z to be

(4.1)

If $I(Z)=(f_1,\ldots ,f_\ell )$, then we can replace the condition “$f(v)=0$ for all $f\in I(Z)$” with the equivalent condition “$f_1(v)=0,\ldots ,f_\ell (z)=0$.”

If $\dim (T_z(Z))=\dim (Z)$, we say that z is a smooth point of Z. Otherwise, it is a singular point. $z\in Z$ is a smooth point if and only if Z is a $\dim (Z)$-dimensional complex manifold in a (Euclidean) neighborhood of z, see [18, Chap. 1] for further details.

4.1.4 Points Where Real and Complex Dimensions do not Agree

We will be interested in a variant of the following question. Let $Z\subset \mathbb {C}^d$ be a variety that can be written as an intersection of d-$\dim _{\mathbb {C}}(Z)$ hypersurfaces, each defined by a real polynomial, and let $z\in Z(\mathbb {R})$. Suppose that $\dim _{z,\mathbb {R}}(Z(\mathbb {R}))<\dim _{\mathbb {C}} Z.$ Must z be a singular point of Z? In this section, we will show that at least in some special cases, the answer is yes. We will rely on a similar result about curves, which is proved in [7, Sect. 6].

Lemma 4.1

Let $\zeta \subset \mathbb {C}^3$ be a space curve (a one-dimensional complex variety). Suppose that $\zeta =\mathbf {Z}_{\mathbb {C}}(P_1)\cap \mathbf {Z}_{\mathbb {C}}(P_2)$, where $P_1,P_2$ are real polynomials. Let $O\in O(3;\mathbb {R})$ be a generic (with respect to $P_1$ and $P_2$) rotation (see Sect. 4.2 for the definition of a generic rotation) and let $\zeta ^\prime = O(\zeta )$. Let $\pi :~\mathbb {C}^3\rightarrow \mathbb {C}^2$ be the projection in the $x_3$-direction. If $z\in \zeta ^\prime (\mathbb {R})$ is an isolated point, then $\pi (z)$ is an isolated point of $(\pi (\zeta ^\prime ))(\mathbb {R})$.

Proof

The main tool we will use is Lemma 6.2 from [7]. Let $\zeta \subset \mathbb {C}^3$ be a space curve. We say that $\zeta$ is in generic position with respect to the projection to the $(x_1,x_2)$-plane if it satisfies the conditions from [7, Def. 4.1]. Rather than stating the definition of generic position here (it is quite technical), we will only state the properties we need.

First, by [7, Sect. 5.4], any curve $\gamma \subset \mathbb {C}^3$ may be put in generic position after applying a generic orthogonal transformation² $O\in O(3;\mathbb {R})$. Informally, a curve is in generic position if no coincidences happen when the curve $\zeta$ is projected onto the $x_1,x_2,$ or $x_3$ axes (for example, it would be bad if two distinct singular points of $\zeta$ projected to the same point).

In [7], El Kahoui also defines what he calls an event point for the (real) curve $\zeta (\mathbb {R})$. This includes objects such as critical points of $\zeta$. Again, we do not need a precise definition; the only property we will use is that the set of event points is finite, and thus they will not be relevant to our argument.

Let $\zeta \subset \mathbb {C}^3$ be a space curve in general position that is defined by real polynomials, and let $\pi :~\mathbb {C}^3\rightarrow \mathbb {C}^2$ be the projection onto the $(x_1,x_2)$-plane. Define $\alpha _\zeta = (\pi (\zeta ))(\mathbb {R})$ (while in general the projection of a space curve to the plane need not be a plane curve, after applying a generic orthogonal transformation we can ensure that this is the case).

Lemma 6.2(i) from [7] relates the properties of $\zeta (\mathbb {R})$ and $\alpha _\zeta .$ In the terminology used here, [7, Lemma 6.2(i)] says the following: if $I\subset \mathbb {R}$ is an interval that does not contain the x-coordinate of any event point, and if $\beta \subset \alpha _\zeta$ is a simple open smooth real curve (in this case not an algebraic curve, but a smooth subset of an algebraic curve that is homeomorphic to (0, 1)), then there is a simple open smooth real curve $\beta ^\prime \subset \zeta (\mathbb {R})$ whose projection to the $(x_1,x_2)$-plane is $\beta$.

We can now prove Lemma 4.1. Let $z\in \zeta ^\prime (\mathbb {R})$ be an isolated point. Suppose that $x=\pi (z)$ is not isolated. Since O was a generic rotation, we can assume that $\pi ^{-1}(x)=\{z\}$. For any $\varepsilon >0$, we can find a simple open smooth real curve $\beta \subset \pi (\zeta ^\prime )(\mathbb {R})$ such that ${\text {dist}}(x,\beta )<\varepsilon$ and the projection of $\beta$ to the $x_1$-axis does not contain any event points. We can now apply lemma 6.2(i) from [7] to conclude that there is a curve $\beta ^\prime \subset \zeta ^\prime (\mathbb {R})$ whose projection to the $(x_1,x_2)$-plane is $\beta$.

This means that for every $\varepsilon >0$ there is a curve $\beta ^\prime \subset \zeta (\mathbb {R})$ whose projection is $\varepsilon$-close to $\pi (z)$. Since $\zeta (\mathbb {R})$ is closed (in the Euclidean topology) and z is an isolated point of $\zeta (\mathbb {R})$, we conclude that the pre-image $\pi ^{-1}(x)$ contains at least two points. But we assumed that this was not the case. This contradiction establishes the lemma. $\square$

Corollary 4.1

Let $P_1,P_2\in \mathbb {R}[x_1,\ldots ,x_4]$, and let $Z=\mathbf {Z}_{\mathbb {C}}(P_1)\cap \mathbf {Z}_{\mathbb {C}}(P_2)$. Suppose that $\dim _{\mathbb {C}}(Z)=2$. If $z\in Z(\mathbb {R})$ satisfies $\dim _{z,\mathbb {R}}(Z(\mathbb {R}))\le 1$, then z is a singular point of Z.

Proof

Suppose z is a smooth point of Z; we will obtain a contradiction. Let $H\subset \mathbb {C}^4$ be a generic real 3-plane passing through z, i.e., H is the zero-set of a linear polynomial in $\mathbb {R}[x_1,\ldots ,x_4]$. Then $H\cap Z$ is a complex one-dimensional variety (i.e., a curve), z is a smooth point of $H\cap Z$, and if we identify H with $\mathbb {C}^3$, we can write $H\cap Z = \mathbf {Z}_{\mathbb {C}}(P_1^\prime )\cap \mathbf {Z}_{\mathbb {C}}(P_2^\prime ),$ where $P_1^\prime ,P_2^\prime \in \mathbb {R}[x_1,x_2,x_3]$. Furthermore, since $\dim _{z,\mathbb {R}}(Z(\mathbb {R}))\le 1$, we have $\dim _{z,\mathbb {R}}((H\cap Z)(\mathbb {R}))=0,$ i.e., z is an isolated point of $(H\cap Z)(\mathbb {R})$. Thus we can apply Lemma 4.1 to conclude that z is a singular point of $H\cap Z$. This contradicts the assumption that z was a smooth point of $H\cap Z$. We conclude that z is a singular point of Z. $\square$

4.2 Generic Points

Often in our arguments we will consider properties that hold at most places on an algebraic variety. In this section we will make the notion of “most places” precise. Specifically, we will introduce the notion of a generic point. We will begin with a motivating example.

Example 4.1

Let $Z\subset \mathbb {C}^4$ be an irreducible hypersurface and let $\mathcal {P},$ $\mathcal {S}$ be the set of points and pseudoflats from Theorem 1.3. Then a generic point of Z does not lie in $\mathcal {P}$ and does not intersect any pseudoflat from $\mathcal {S}$.

Definition 4.2

Let Z be an irreducible complex variety and let ${\mathcal {M}}$ be a finite collection of polynomials, none of which vanish on Z. We say that a point $z\in Z$ is generic with respect to ${\mathcal {M}}$ if none of the polynomials in ${\mathcal {M}}$ vanish on z. In particular, for Z and ${\mathcal {M}}$ fixed, the set of generic points is Zariski dense in Z. In practice, the collection ${\mathcal {M}}$ of polynomials will be apparent from context, so we will abuse notation and make statements such as “a generic point of Z has the following properties.” Here the set of polynomials ${\mathcal {M}}$ should be inferred from the properties we have specified.

In general, the set of polynomials ${\mathcal {M}}$ will depend on the variety Z, the set of points and pseudoflats from Theorem 1.3 as well as any intermediate objects that have already been constructed, and whatever property is currently under consideration.

If $Z(\mathbb {R})$ is Zariski dense in Z, then we define a generic real point of $Z(\mathbb {R})$ to be a point $z\in Z(\mathbb {R})$ for which no polynomial in ${\mathcal {M}}$ vanishes. In particular, if $Z(\mathbb {R})$ is dense in Z, then the set of generic real points is non-empty.

The set $\mathbb {C}^4$ will be of particular interest, and we will consider it as both a vector space and a complex variety. In our arguments below, we will refer to generic vectors in $\mathbb {C}^4$ or $\mathbb {R}^4$. This means that the vector is generic with respect to all of the objects defined previously—this includes the points $\mathcal {P}$, surfaces $\mathcal {S}$, the partitioning polynomials P and $\{Q_i\}$, and any previously defined vectors, etc.

We will also be interested in several other generic objects:

• Generic k-planes. These are generic elements of the Grassmannian ${\text {Gr}}(k,d;\mathbb {C})$ or ${\text {Gr}}(k,d;\mathbb {R})$. They will be discussed further in Sect. 6.1.

• Generic (real) rotations. These are generic elements of the orthogonal group $O(d;\mathbb {R})$ (this group has the structure of a real variety).

• Generic projections. These are projections of the form $O^{-1}\circ \pi \circ O,$ where $\pi :~\mathbb {C}^d\rightarrow \mathbb {C}^{d^\prime }$ is the projection to the first $d^\prime$ coordinates, and O is a generic rotation.

4.3 Resultants and Projections

Given two polynomials $f,g\in \mathbb {C}[x_1,\ldots ,$ $x_d]$, we define the resultant ${\text {res}}(f,g)\in \mathbb {C}[x_1,\ldots ,x_{d-1}]$ to be the resultant of f and g in the $x_d$-variable, i.e., we consider f and g to be polynomials in $x_d$ with coefficients in the ring $\mathbb {C}[x_1,\ldots ,x_{d-1}]$, and we take the (classical) resultant of these two polynomials. If f and g have real coefficients, then ${\text {res}}(f,g)$ also has real coefficients.

If $f\in \mathbb {C}[x_1,\ldots ,x_{d}]$, we say that f is $x_{d}$-monic if the coefficient of $x_d^{\deg f}$ is non-zero. If f is $x_d$-monic, f and g intersect properly (i.e., if $\dim _{\mathbb {C}}(\mathbf {Z}_{\mathbb {C}}(f)\cap \mathbf {Z}_{\mathbb {C}}(g))=d-2$), and if $\pi _d:~\mathbb {C}^{d}\rightarrow \mathbb {C}^{d-1}$ is the projection to the first $(d-1)$-coordinates, then

$$\begin{aligned} \pi _d(\mathbf {Z}_{\mathbb {C}}(f)\cap \mathbf {Z}_{\mathbb {C}}(g))\subset \mathbf {Z}_{\mathbb {C}}({\text {res}}(f,g)). \end{aligned}$$

See for example Sect. 2C from [18]. In particular, if f and g have real coefficients, f is $x_d$-monic, and if $\dim _{\mathbb {C}}(\mathbf {Z}_{\mathbb {C}}(f)\cap \mathbf {Z}_{\mathbb {C}}(g))=d-2$, then

$$\begin{aligned} \pi _d(\mathbf {Z}_{\mathbb {R}}(f)\cap \mathbf {Z}_{\mathbb {R}}(g))\subset \mathbf {Z}_{\mathbb {R}}({\text {res}}(f,g)), \end{aligned}$$

(4.2)

and $\mathbf {Z}_{\mathbb {R}}({\text {res}}(f,g))$ is a variety of dimension at most $d-2$.

Note, however, that if we only require that $\dim _{\mathbb {R}}(\mathbf {Z}_{\mathbb {R}}(f)\cap \mathbf {Z}_{\mathbb {R}}(g))=d-2$, then $\mathbf {Z}_{\mathbb {R}}({\text {res}}(f,g))$ may be all of $\mathbb {R}^{d-1}$. For example, if $f=g$ and $\dim _{\mathbb {R}}(\mathbf {Z}_{\mathbb {R}}(f))=d-2$, then $\dim _{\mathbb {R}}(\mathbf {Z}_{\mathbb {R}}(f)\cap \mathbf {Z}_{\mathbb {R}}(g))=d-2$, but ${\text {res}}(f,g)$ is the zero polynomial.

While not every polynomial $f\in \mathbb {C}[x_1,\ldots ,x_d]$ is $x_d$-monic, we can usually fix this problem by pre-composing f with a generic orthogonal transformation. More precisely, if $f\in \mathbb {C}[x_1,\ldots ,x_d]$ and if $O\in O(d;\mathbb {C})$ is a generic rotation, then $f\circ O$ is $x_d$-monic. The same statement holds if $f\in \mathbb {R}[x_1,\ldots ,x_d]$ and O is a generic real rotation.

4.3.1 Projections and Degree

If $Z\subset \mathbb {C}^d$ is an irreducible variety of dimension $\le d-2$, and $\pi :~ \mathbb {C}^{d}\rightarrow \mathbb {C}^{d-1}$ is a generic projection, then $\deg ({\overline{\pi (Z)}})=\deg (Z)$, where denotes closure in the Zariski topology. This follows from the definition of degree given in Sect. 4.5.

4.4 Singular Points of Transverse Intersections

Let $f,g\in \mathbb {C}[x_1,x_2,x_3]$ be square-free polynomials. If $z\in \mathbf {Z}_{\mathbb {C}}(f)\cap \mathbf {Z}_{\mathbb {C}}(g)$, we define the intersection multiplicity of $\mathbf {Z}_{\mathbb {C}}(f)\cap \mathbf {Z}_{\mathbb {C}}(g)$ at z to be the intersection multiplicity of the plane curves $(\mathbf {Z}_{\mathbb {C}}(f)\cap H) \cap (\mathbf {Z}_{\mathbb {C}}(g)\cap H)$ in H, where H is a generic plane passing through z. The intersection multiplicity of plane curves in $\mathbb {C}^2$ is a classical subject and has many equivalent definitions. See [18, Sect. 5.1] for further discussion. We will need the following properties of intersection multiplicity:

• If z is a smooth point of $\mathbf {Z}_{\mathbb {C}}(f)\cap \mathbf {Z}_{\mathbb {C}}(g)$ and if $\left( {\begin{array}{c}\nabla f(z)\\ \nabla g(z)\end{array}}\right)$ has rank 2, then the intersection multiplicity of $\mathbf {Z}_{\mathbb {C}}(f)\cap \mathbf {Z}_{\mathbb {C}}(g)$ at z is 1; this is because $\mathbf {Z}_{\mathbb {C}}(f),\mathbf {Z}_{\mathbb {C}}(g),$ and H form a transverse complete intersection at z.

• f and g are square-free, $z\in \mathbf {Z}_{\mathbb {C}}(f)\cap \mathbf {Z}_{\mathbb {C}}(g),$ and if z is a singular point of $\mathbf {Z}_{\mathbb {C}}(f)$, then the intersection multiplicity of $\mathbf {Z}_{\mathbb {C}}(f)\cap \mathbf {Z}_{\mathbb {C}}(g)$ at z is strictly greater than 1.

Lemma 4.2

Let Y, Z be two-dimensional varieties in $\mathbb {C}^3$ and let $\zeta \subset Y\cap Z$ be an irreducible component. Suppose that Y is smooth, and suppose that Y and Z intersect transversely on $\zeta$ (i.e., Z is smooth at a generic point of $\gamma$, and Y and Z intersect transversely at a generic point of $\zeta$). Then if $z\in \zeta$ is a singular point of Z, z must also be a singular point of $Y\cap Z$.

Proof

First, if z lies on more than one component of $Y\cap Z$, then z is a singular point of $Y\cap Z$, so we are done. Thus we may assume that z only lies on the component $\zeta$. Let $Z=\mathbf {Z}_{\mathbb {C}}(f),\ Y=\mathbf {Z}_{\mathbb {C}}(g)$ with f and g square-free. Since Y and Z intersect transversely along $\zeta$, each generic point $x\in \zeta \subset Y\cap Z$ has multiplicity 1. However, since z is a singular point of Z, $\nabla f(z)=0$, so $\left( {\begin{array}{c}\nabla f(z)\\ \nabla g(z)\end{array}}\right)$ has rank $\le 1$. Thus z is a singular point of $\zeta$. $\square$

4.5 Degree and Bézout’s Theorem

Definition 4.3

Let $Z\subset \mathbb {C}^d$ be a pure-dimensional variety (i.e., all of its irreducible components have the same dimension). We define the degree of Z to be $|Z\cap H|$, where H is a generic linear space of dimension d-$\dim _{\mathbb {C}}(Z)$. This definition is independent of the choice of (generic) hyperplane; see [12, Chap. 18] for further details. In particular, if $Z=\mathbf {Z}_{\mathbb {C}}(f)$, then $\deg Z\le \deg f$. If $Z\subset \mathbb {C}^d$ is a hypersurface (a $(d-1)$-dimensional variety), we can write $Z=\mathbf {Z}_{\mathbb {C}}(f)$ for some $f\in \mathbb {C}[x_1,\ldots ,x_d]$ with $\deg f=\deg (Z)$.

We will make frequent use of Bézout’s theorem, which gives us quantitative control on the complexity of the intersection of two varieties. There are many variants of this theorem. We will state a version below that is sufficient for our needs.

Proposition 4.1

(Bézout’s theorem for properly intersecting varieties ) Let $Y,Z\subset \mathbb {C}^d$ be pure-dimensional varieties, and suppose that

$$\begin{aligned} \dim _{\mathbb {C}}(Y\cap Z)=\dim Y + \dim Z - d. \end{aligned}$$

(4.3)

Then

$$\begin{aligned} \deg (Y\cap Z)\le \deg (Y)\deg (Z). \end{aligned}$$

(4.4)

In particular, if (4.3) holds and if $\dim Y + \dim Z=d$, then $Y\cap Z$ is a finite set, and it has cardinality at most $\deg (Y)\deg (Z)$.

Remark 4.1

The proposition above is Example 12.3.1 from [10], which is itself a special case of Theorem 12.3. In Example 12.3.1, the LHS of (4.4) is replaced by the sum of the degrees of the irreducible components of $Y\cap Z$. However, our definition of degree (Definition 4.3) allows for a variety to have several irreducible components, so (4.4) coincidences with the statement in [10].

We will also need a version of Bézout’s theorem when the varieties do not intersect properly. For simplicity, we will only state a special case.

Proposition 4.2

(Bézout’s theorem for non-properly intersecting varieties; special case) Let $Y,Z\subset \mathbb {C}^d$ be pure-dimensional varieties. Then the number of isolated points of $Y\cap Z$ is at most $\deg (Y)\deg (Z)$.

This is another special case of Example 12.3.1 from [10]. In [10], Fulton defines a distinguished component of the intersection $Y\cap Z$, and then proceeds to bound the number of distinguished components. Isolated points of $Y\cap Z$ are distinguished components of the intersection, so the bound applies here.

Finally, we will need a version of Bézout’s theorem with multiplicities for plane curves. This is also a corollary of Example 12.3.1 from [10]. We will first introduce the notion of multiplicity of a plane curve at a point and multiplicity of an intersection of plane curves.

Definition 4.4

Let $\zeta \subset \mathbb {C}^2$ be an algebraic curve and let $z\in \mathbb {C}^2$. We define the multiplicity of $\zeta$ at z, ${\text {mult}}_z(\zeta ),$ to be the order of vanishing of f at z, where f is the unique (up to scalar multiples) square-free polynomial such that $\zeta =\mathbf {Z}_{\mathbb {C}}(f)$.

Definition 4.5

Let $\zeta ,\zeta ^\prime \subset \mathbb {C}^2$ be algebraic plane curves that have no common components, and let $z\in \zeta \cap \zeta ^\prime .$ Then there is a number $m_z={\text {mult}}_z(\zeta \cap \zeta ^\prime )$ with the following property. For all sufficiently small open Euclidean neighborhoods U of z, z is the unique point in $U\cap \zeta \cap \zeta ^\prime$. For each such neighborhood U, there is a number $\varepsilon >0$ so that if v is a generic vector in $\mathbb {C}^2$ with $|v|\le \varepsilon$, then $U\cap (\zeta +v)\cap \zeta ^\prime$ is a union of $m_z$ points. In short, if we shift $\zeta$ by a small generic vector v, then the point $z\in \zeta \cap \zeta ^\prime$ splits into ${\text {mult}}_z(\zeta \cap \zeta ^\prime )$ distinct points.

Proposition 4.3

(Bézout’s theorem with multiplicity for plane curves) Let $\zeta ,\zeta ^\prime$ be plane curves with no common components. Then

$$\begin{aligned} \sum _{z\in \zeta \cap \zeta ^\prime } {\text {mult}}_z(\zeta \cap \zeta ^\prime ) \le (\deg \zeta )(\deg \zeta ^\prime ). \end{aligned}$$

4.6 Controlling the Singular Locus of a Surface

Lemma 4.3

Let $P,Q\in \mathbb {C}[x_1,\ldots ,x_4]$ be polynomials, and suppose that $\mathbf {Z}_{\mathbb {C}}(P)\cap \mathbf {Z}_{\mathbb {C}}(Q)$ is a complete intersection. Then there is a curve $\gamma$ of degree $O((\deg P)^2( \deg Q)^2)$ so that $(\mathbf {Z}_{\mathbb {C}}(P)\cap \mathbf {Z}_{\mathbb {C}}(Q))_{{\text {sing}}}\subset \gamma$.

Proof

This is a special case of the general fact that if $Z\subset \mathbb {C}^d$ is an irreducible variety, then there is a variety of degree $O((\deg Z)^2)$ and dimension $< \dim Z$ that contains $Z_{{\text {sing}}}$. However, there do not appear to be any easy references to this fact in the literature, so we will briefly sketch the proof of Lemma 4.3 here.

After a generic change of coordinates, we can assume that P and Q are $x_4$-monic, and thus $\pi (\mathbf {Z}_{\mathbb {C}}(P)\cap \mathbf {Z}_{\mathbb {C}}(Q))\subset \mathbf {Z}_{\mathbb {C}}({\text {res}}(P,Q))$. Recall from Sect. 4.1.3 that the singular points of $\mathbf {Z}_{\mathbb {C}}(P)\cap \mathbf {Z}_{\mathbb {C}}(Q)$ are precisely those points at which $\mathbf {Z}_{\mathbb {C}}(P)\cap \mathbf {Z}_{\mathbb {C}}(Q)$ fails to be a complex manifold. Thus $\pi ((\mathbf {Z}_{\mathbb {C}}(P)\cap \mathbf {Z}_{\mathbb {C}}(Q))_{{\text {sing}}})\subset (\mathbf {Z}_{\mathbb {C}}({\text {res}}(P,Q)))_{{\text {sing}}}$. But $\mathbf {Z}_{\mathbb {C}}({\text {res}}(P,Q))$ is a surface in $\mathbb {C}^3$ of degree at most $(\deg P)(\deg Q)$, and thus we can write $\mathbf {Z}_{\mathbb {C}}(P)\cap \mathbf {Z}_{\mathbb {C}}(Q)=\mathbf {Z}_{\mathbb {C}}(f)$, where $f\in \mathbb {C}[x_1,x_2,x_3]$ is a square-free polynomial of degree at most $(\deg P)(\deg Q)$.

We can now find a polynomial $g\in \mathbb {C}[x_1,x_2,x_3]$ so that $\mathbf {Z}_{\mathbb {C}}(f)\cap \mathbf {Z}_{\mathbb {C}}(g)$ is a complete intersection, and $\mathbf {Z}_{\mathbb {C}}(f)_{{\text {sing}}}\subset \mathbf {Z}_{\mathbb {C}}(f)\cap \mathbf {Z}_{\mathbb {C}}(g)$. Briefly, we do this as follows. Let $v\in \mathbb {C}^3$ be a generic vector, and let $g= v\cdot \nabla f$. Then $(\mathbf {Z}_{\mathbb {C}}(f))_{{\text {sing}}}\subset \mathbf {Z}_{\mathbb {C}}(f)\cap \mathbf {Z}_{\mathbb {C}}(g)$. Furthermore, $\mathbf {Z}_{\mathbb {C}}(f)\cap \mathbf {Z}_{\mathbb {C}}(g)$ is a complete intersection; if this were not the case, then g must vanish identically on some irreducible component of f. But since v was chosen generically, this implies that $\nabla f$ vanishes identically on some irreducible component of f, and this contradicts the assumption that f was square-free.

Let $g^\prime (x_1,x_2,x_3,x_4)=g(x_1,x_2,x_3)$ and let $\gamma = \mathbf {Z}_{\mathbb {C}}(g^\prime )\cap \mathbf {Z}_{\mathbb {C}}(P)\cap \mathbf {Z}_{\mathbb {C}}(Q)$. Then $(\mathbf {Z}_{\mathbb {C}}(P)\subset \mathbf {Z}_{\mathbb {C}}(Q))_{{\text {sing}}}\subset \gamma$, and $\gamma$ is a curve of degree $O((\deg P)^2( \deg Q)^2)$. $\square$

4.7 Branches of Algebraic Curves

Frequently, we will need to bound the number of point-surface incidences $I\subset {\mathcal {I}}(\mathcal {P},\mathcal {S})$ when the points lie on a one-dimensional algebraic curve $\zeta$, and the surfaces meet that curve in a one-dimensional intersection (which need not be all of $\zeta$, since generally $\zeta$ will not be irreducible). The idea is that if a point $p\in \mathcal {P}$ lies in $\zeta _{{\text {smooth}}}$, then there can be at most one surface $S\in \mathcal {S}$ that is incident to p and for which $S\cap \zeta$ contains an irreducible component of $\zeta$ containing p. However, if $p\in \zeta _{{\text {sing}}}$, then potentially many surfaces $S\in \mathcal {S}$ can have this property. We need to bound how many surfaces there can be. This is controlled by the number of branches of $\zeta$ at the point p. We recall [17, Lemma 3.3]:

Lemma 4.4

Let z be a non-isolated point of a real or complex one-dimensional variety V. Then a suitably chosen (Euclidean) neighborhood of z in V is the union of finitely many branches which intersect only at z. Each branch is homeomorphic to a (Euclidean) open interval of real numbers (if V is a real variety) or a (Euclidean) open disk of complex numbers (if V is a complex variety).

Definition 4.6

For $z\in \zeta$, let $G_z(\zeta )$ be the number of branches of $\zeta$ through z. For example, if z is a smooth point of $\zeta$, then $G_z(\zeta )=1$.

Lemma 4.5

Let $\zeta \subset \mathbb {C}^d$ be an algebraic curve. Suppose $z\in \zeta (\mathbb {R})$ is a non-isolated point. Then the number of real branches of $\zeta (\mathbb {R})$ through z is at most the number of complex branches of $\zeta$ through z.

See e.g. [17, p. 29].

Lemma 4.6

Let $\zeta \subset \mathbb {C}^d$ be an algebraic curve. Then

$$\begin{aligned} \sum _{z\in \zeta _{{\text {sing}}}}G_z(\zeta )\le (\deg \zeta )^2. \end{aligned}$$

(4.5)

Proof

The main observation is that if $\pi :~\mathbb {C}^d\rightarrow \mathbb {C}^2$ is a generic projection, then $G_{z}(\zeta )\le G_{\pi (z)} ({\overline{\pi (\zeta )}})$. Thus it suffices to prove the result for plane curves. However, if $\zeta$ is a plane curve, then $G_z(\zeta )\le {\text {mult}}_z(\zeta )$, where ${\text {mult}}_z(\zeta )$ is given by Definition 4.4. We have that

$$\begin{aligned} \sum _{z\in \zeta _{{\text {sing}}}}{\text {mult}}_z(\zeta )\le (\deg \zeta )^2. \end{aligned}$$

See, i.e., [21, (7) on page 54] for a discussion of this formula. Equation (7) on p. 54 of [21] defines the genus of an irreducible complex plane curve $\zeta$ to be

$$\begin{aligned} \tfrac{1}{2}(\deg \zeta )(\deg \zeta -1)-\tfrac{1}{2}\sum {\text {mult}}_z(\zeta )({\text {mult}}_z(\zeta )-1), \end{aligned}$$

where the sum is taken over all multiple points of the curve. Since the genus is non-negative, this implies

$$\begin{aligned} \sum {\text {mult}}_z(\zeta )({\text {mult}}_z(\zeta )-1)\le (\deg \zeta )(\deg \zeta -1), \end{aligned}$$

so in particular

$$\begin{aligned} \sum {\text {mult}}_z(\zeta )\le (\deg \zeta )^2. \end{aligned}$$

It remains to extend this result to reducible curves. But this follows from Bézout’s theorem for plane curves (Proposition 4.3). Factor $\zeta = \zeta _1\cup \cdots \cup \zeta _\ell$ into irreducible components. If $z\in \zeta$, then ${\text {mult}}_z(\zeta )=\sum _{i=1}^\ell {\text {mult}}_z(\zeta _i)$. We have

$\square$

Later in our proof we will be given a collection of Euclidean connected components of real algebraic curves and a collection of bad points on these curves. We will need to remove these bad points to obtain a (possibly larger) collection of curves. The following observation bounds the number of additional connected components that are created in this process. In essence, it says that when you remove a point from an interval, you are left with two connected components.

Lemma 4.7

(Real branches and connected components) Let $\zeta \subset \mathbb {C}^d$ be an algebraic curve and let $\alpha \subset \zeta (\mathbb {R})$ be a semialgebraic set. Suppose that $z\in \alpha$ and $\dim _{\mathbb {R},z}(\alpha )=1$. Then

$$\begin{aligned} b_0(\alpha \backslash z) \le b_0(\alpha ) + 2G_z(\alpha )\le b_0(\alpha ) +2 G_z(\zeta ), \end{aligned}$$

(4.6)

where $b_0(X)$ is the number of Euclidean connected components of the set X.

4.8 Incidences on Algebraic Curves

The following lemma will be used frequently to bound the number of incidences occurring on various bad sets.

Lemma 4.8

(Incidences on a curve) Let $\zeta \subset \mathbb {C}^4$ be an algebraic curve. Let $\mathcal {P}\subset \mathbb {R}^4$ be a collection of points, and suppose $\mathcal {P}\subset \zeta (\mathbb {R})$. Let ${\mathcal {S}}$ be a $C_0$-good collection of pseudoflats (in $\mathbb {R}^4$), and let $I\subset {\mathcal {I}}(\mathcal {P},{\mathcal {S}})$ be a good collection of incidences. Let

Then

$$\begin{aligned} |I^\prime |\le |\mathcal {P}| + (\deg \zeta )^2. \end{aligned}$$

(4.7)

Proof

If $p\in \zeta$ is a smooth point, then p can be incident to at most one surface in ${\mathcal {S}}$. Otherwise, there can be at most $G_\zeta (p)$ surfaces $S\in {\mathcal {S}}$ with $(p,S)\in I$. The result now follows from Lemma 4.6. $\square$

We are now ready to return to the task of bounding incidences on the surfaces $\mathbf {Z}_{\mathbb {R}}(P_i)\cap \mathbf {Z}_{\mathbb {R}}(Q_i)$.

5 Proof of Theorem 1.3 Step Two: Incidences on a Surface in $\mathbb {R}^4$

Let

$$\begin{aligned} I_0 = I\cap \bigcup _i {\mathcal {I}}(\mathcal {P}_i \cap \mathbf {Z}_{\mathbb {R}}(Q_i),\mathcal {S}_2). \end{aligned}$$

The goal of the following sections is to bound $|I_0|$. The basic idea is that problems occur when surfaces $S\in \mathcal {S}_2$ intersect $\mathbf {Z}_{\mathbb {R}}(P_i)\cap \mathbf {Z}_{\mathbb {R}}(Q_i)$ in one-dimensional curves, and many points lie on these curves. We will first deal with the incidences where this does not occur. Let

By Corollary 2.2,

$$\begin{aligned} |I_0^\prime | \lesssim n \sum _{i=1}^\ell D_iE_i\lesssim m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}. \end{aligned}$$

(5.1)

The real difficulty will be to bound $|I_0^*|$.

For each $i=1,\ldots ,\ell$, let $V_i=\mathbf {Z}_{\mathbb {C}}(P_i)\cap \mathbf {Z}_{\mathbb {C}}(Q_i)$, and let $V=\bigcup _i V_i$. For each $S\in \mathcal {S}_2$, $S^*\cap V$ is a union of isolated points and irreducible one-dimensional varieties (scheme-theoretically, $S^*\cap V$ may contain curves with embedded points, but we are only looking at the intersection set-theoretically).

If $\gamma$ is an irreducible one-dimensional variety from the above decomposition, we define $i(\gamma )$ to be the smallest index i so that $\gamma \subset V_i$. For each $i=1,\ldots ,\ell$, define

Recall that we have partitioned the points $\mathcal {P}\cap V$ in a similar fashion into the sets $\{\mathcal {P}_i\}$. Thus, if $(p,S)\in I_0^*$ and $p\in \mathcal {P}_i$, then at least one of the following two things must happen:

• There exists $\gamma \in \Gamma _{S,i}^*$ so that $p\in \gamma$.

• There exists an index $j>i$ and some $\gamma \in \Gamma _{S,j}^*$ so that $p\in \gamma$. In addition, $\gamma \cap V_i$ is a discrete set.

We will now describe several different types of incidences, and bound each type in turn

5.1 Different Types of Curves and Incidences

Let

We will now define several types of incidences. Let

$$\begin{aligned} \alpha _{S}=\bigcup _{i}\bigcup _{\gamma \in \Gamma _{S,i}^*}\gamma . \end{aligned}$$

(5.2)

Note that if $(p,S)\in I_0^*$ and $p\in (\alpha _{S})_{{\text {smooth}}}$, then there is a unique index j and a unique curve $\gamma \in \Gamma _{S,j}^*$ that contains p. If it is clear from context, we will simply call this curve $\gamma$. Define

The above definitions make reference to an index i. What we mean by this is that the condition must hold for some index i.

We will now bound the incidences $I_1,\ldots ,I_5$. Bounding $I_6$ will require significant new tools, so this will be done in Sect. 7.

5.2 Bounding $I_1,I_2,I_3$: Counting Singular Points on Algebraic Curves

We will begin with $I_1$. For each $S\in \mathcal {S}_2$, $\alpha _{S}$ is an algebraic curve of degree $O(\sum _{i=1}^\ell D_i)=O(D)$. Thus it has at most $O(D^2)$ singular points, so

$$\begin{aligned} |I_1| \lesssim nD^2\lesssim m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}. \end{aligned}$$

(5.3)

Next, we will see that $I_2$ is empty. Fix $S\in \mathcal {S}_2$. Let $p\in \mathcal {P}_i$ and suppose the following conditions hold:

• p lies on only one irreducible component (i.e., one curve) $\gamma$ of $S^*\cap V.$

• p is a smooth point of $\gamma$.

• $\gamma \in \Gamma _{S,j}^*$ for some $j>i$.

Then p is an isolated point of $S^*\cap V_j$, so $(p,S)\in I_0^\prime .$ In particular, this implies that $(p,S)\notin I_2$. We conclude that

$$\begin{aligned} |I_2|=0. \end{aligned}$$

(5.4)

We will now bound $I_3$. For each index i, use Lemma 4.3 to find a curve $\zeta _i$ of degree $O((D_iE_i)^2)$ that contains $(V_i)_{{\text {sing}}}$. Apply Lemma 4.8 to bound

$$\begin{aligned} |I_3|\le & {} \sum _{i}\big (|\mathcal {P}_i| + \sum _i (\deg \zeta _i)^2\big ) \nonumber \\\lesssim & {} m + \sum _i (D_iE_i)^4 \nonumber \\\le & {} m + \big (\sum _i D_iE_i\big )^4 \nonumber \\\lesssim & {} m+m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}. \end{aligned}$$

(5.5)

In the second last line we used the observation that $D_iE_i\ge 0$ for each index i. In the last line we used the assumption that $m\le n^{(2k+2)/3k}$. Thus we have

$$\begin{aligned} |I_3|\lesssim m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}+m. \end{aligned}$$

(5.6)

Remark 5.1

(5.5) and (5.9) are the only two places where we use the assumption that $m\le n^{(2k+2)/3k}$. Thus, if these two arguments could be avoided, we could remove the restriction that $m\le n^{(2k+2)/3k}$ in the statement of Theorem 1.3. This will be discussed further in Sect. 10.1.

5.3 Bounding $I_4$: Tangential Surface Intersections

Lemma 5.1

Let $W\subset \mathbb {C}^d$ be an irreducible variety, and let $R\in \mathbb {C}[x_1,\ldots ,x_d]$ be a non-zero polynomial. Suppose that R vanishes on W. Then there exists a polynomial $\tilde{R}$ with the following properties:

• (1) $\deg \tilde{R}\le \deg R$.

• (2) $\tilde{R}$ vanishes on W.

• (3) $\nabla \tilde{R}$ does not vanish identically on W.

Proof

(sketch) The proof follows similar ideas to the proof of Lemma 2.1, so for brevity we will only sketch it here. For each variety W, we will prove the result by induction on $\deg R$. If $\deg R=1$, then $\nabla R$ is non-zero everywhere, so we are done. Now suppose the result has been proved for all polynomials of degree at most D, and let R be a polynomial of degree $D+1$. Suppose $\nabla \tilde{R}$ vanishes identically on W. Let v be a generic vector. Then $R^\prime =v\cdot \nabla R$ is not the zero polynomial, and $R^\prime$ vanishes identically on W. We can thus apply the induction hypothesis to $R^\prime$. $\square$

Lemma 5.2

For each index $i=1,\ldots ,\ell$, we have the bound

(5.7)

Proof

Let $\{V_{i,j}\}$ be the irreducible components of $V_i.$ For each index j, let $\mathcal {P}_{i,j}$ be the points of $\mathcal {P}_i$ lying in $V_{i,j}$ that have not already been placed in some previous $\mathcal {P}_{i,j^\prime }$ with $j^\prime <j$. Similarly, for each curve $\gamma \in \Gamma _{S,i}^{(2)}$, let $j(\gamma )$ be the smallest index so that $\gamma \subset V_{i,j}$. Define

We will divide the incidences of $I_4$ into several types. Define

From tangent space considerations (see Lemma 3.2) we have $|I_4^{\prime }|\le |\mathcal {P}_i|$. If $p\in \mathcal {P}_i$, and $(p,S)\in I_4\backslash I_4^\prime$, then p is incident to precisely one curve $\gamma \in \Gamma _{S,i}^{(2)}$. Define

We will first consider $I_4^{\prime \prime \prime }$. If $(p,\gamma )\in I_4^{\prime \prime \prime }$, then p is an isolated point of $S^*\cap V_{i,j}$ (if not, then the incidence p would have been counted in $I_1$). Applying Proposition 4.2, we have

$$\begin{aligned} |I_4^{\prime \prime \prime }| \le \sum _{S\in \mathcal {S}_2} \sum _{j}(\text {number of isolated points of}\ S^*\cap V_{i,j})\le nD_iE_i. \end{aligned}$$

(5.8)

It remains to count $I_4^{\prime \prime }.$ Fix j. Let $\tilde{P}_{i,j}$ be the polynomial obtained by applying Lemma 5.1 to the polynomial $P_i$ and the variety $V_{i,j}$. Let $\zeta _{i,j}=\mathbf {Z}_{\mathbb {C}}(\tilde{P}_{i,j})\cap V_{i,j}.$ If $p\in V_{i,j}\backslash \zeta _{i,j}$ and if $(p,S)\in I_4^{\prime \prime }$, then $T_pS$ must lie in $T_p(\mathbf {Z}_{\mathbb {C}}(\tilde{P}_{i,j}))$, which is a three-dimensional vector space. Thus, for each point $p\in V_{i,j}\backslash \zeta _{i,j}$, there can be at most one $S\in \mathcal {S}_2$ with $(p,S)\in I_4^{\prime \prime }$, so the total number of incidences of this type is at most $|\mathcal {P}_i|$.

Finally, $\zeta _{i,j}$ is a curve of degree $O(D_i^2E_i)$, so by Lemma 4.8, the total number of incidences $(p,S)\in I_4^{\prime \prime }$ with $p\in \zeta _{i,j}$ is $O(D_i^4E_i^2+|\mathcal {P}_i|)$. We conclude that $|I_4^{\prime \prime }|\lesssim D_i^4E_i^2+|\mathcal {P}_i|$. $\square$

Summing the bound (5.7) over all indices i and using the assumption (from the statement of Theorem 1.3) that $m\le n^{(2k+2)/3k}$, we obtain the bound

$$\begin{aligned} |I_4| \lesssim m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}+m. \end{aligned}$$

(5.9)

5.4 Bounding $I_5$: Transverse Surface Intersections

Lemma 5.3

Let $Y\subset \mathbb {C}^4$ be a smooth bounded-degree two-dimensional variety, and let $W\subset \mathbb {C}^4$ be a two-dimensional variety. Let $\Gamma$ be the set of irreducible one-dimensional components of $Y\cap W$. Let

Then

$$\begin{aligned} \sum _{\gamma \in \Gamma ^\prime } |\gamma \cap W_{{\text {sing}}}| \le C\big ( \deg W+ \big ( \sum _{\gamma \in \Gamma }(\deg \gamma )\big )^2\big ), \end{aligned}$$

(5.10)

where the constant C depends only on $\deg Y$.

Proof

Let $v\in \mathbb {C}^4$ be a generic vector and let $\pi _v:~\mathbb {C}^4\rightarrow \mathbb {C}^3$ be the projection in the direction v. Let

$$\begin{aligned} Y^{\dagger }=\pi _v^{-1}(\pi _v(Y)). \end{aligned}$$

Then since v was chosen generically with respect to Y, $Y^{\dagger }$ is a smooth three-dimensional variety of degree $\deg (Y)$. Furthermore, $Y^{\dagger }\cap W$ is a one-dimensional curve, and each $\gamma \in \Gamma$ is a (irreducible) component of $Y^{\dagger }\cap W$. Let $\zeta$ be the union of all irreducible components of $Y^\dagger \cap W$ that are not contained in Y. We have $\deg \zeta \le \deg (Y^{\dagger }\cap W)\le C\deg W$, where the constant C depends only on $\deg Y$.

Let $\gamma \in \Gamma ^\prime$, and let $z\in \gamma \cap W_{{\text {sing}}}$. Then $\pi _v(z)\in \pi _v(Y^{\dagger })=\pi _v(Y)$ and $z\in \pi _v(W_{{\text {sing}}})\subset {\overline{\pi _v(W)}}_{{\text {sing}}}$. Note as well that $\pi _v(Y)$ and $\pi _v(W)$ intersect transversely at a generic point of $\pi _v(\gamma )$. Thus by Lemma 4.2, we have that $\pi (z)$ is a singular point of $\pi _v(Y)\cap \pi _v(W)$. But this implies that z is a singular point of $Y^\dagger \cap W$. In particular, at least one of the following three things must occur:

$$\begin{aligned} z\in \zeta \cap Y, \end{aligned}$$

(5.11)

or

$$\begin{aligned} z\in \gamma _{{\text {sing}}}, \end{aligned}$$

(5.12)

or

$$\begin{aligned} z\in \bigcup _{\gamma ^\prime \in \Gamma ,\ \gamma ^\prime \ne \gamma }\gamma \cap \gamma ^\prime . \end{aligned}$$

(5.13)

Now, considering all $\gamma \in \Gamma ^\prime$, we conclude there can be O(W) points of the form (5.11), at most $\sum _{\gamma \in \Gamma ^\prime }(\deg \gamma )^2$ points of the form (5.12), and at most $( \sum _{\gamma \in \Gamma }(\deg \gamma ))^2$ points of the form (5.13). This establishes (5.10). $\square$

Applying Lemma 5.10 to the sets $\{V_i\}$ and bounded-degree smooth surfaces $\{S^*:~ S\in \mathcal {S}_2\},$ with $\Gamma ^\prime = \Gamma _{S,i}^{(3)},$ we conclude that

$$\begin{aligned} |I_5|\lesssim & {} n\sum _i D_iE_i + n\sum _i D_i^2 \nonumber \\\lesssim & {} m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}. \end{aligned}$$

(5.14)

It remains to bound $|I_6|$. Doing so will require several new tools, which we will discuss in the next section.

6 Interlude: The Gauss Map of a Variety

6.1 Grassmannians and the Gauss Map

Let $F=\mathbb {R}$ or $\mathbb {C}$. If $v_1,\ldots ,v_k\in F^d$ are vectors, let $\langle v_1,\ldots ,v_k\rangle \subset F^d$ be the vector space spanned by $v_1,\ldots ,v_k$. In practice, the vectors $v_1,\ldots ,v_k$ will be linearly independent. Let ${\text {Gr}}(k,d;F)$ be the Grassmannian of k-dimensional vector subspaces of $F^d$. We will identify elements of ${\text {Gr}}(k,d;F)$ with planes in $F^d$ passing through the origin, and we will usually use the variable $\Pi$ for these planes.

${\text {Gr}}(k,d;\mathbb {C})$ has the structure of a projective variety (see, i.e., [12, Chap. 6]). ${\text {Gr}}(k,d;F)$ is a smooth variety and also a smooth (real or complex) manifold. If $\Pi \in {\text {Gr}}(k,d;F)$, then $T_\Pi {\text {Gr}}(k,d;F)$ is the tangent plane to ${\text {Gr}}(k,d;F)$ at $\Pi$, and $T{\text {Gr}}(k,d;F)$ is the tangent bundle.

If $\Pi ,\Pi ^\prime$ are vector spaces, let $\Pi +\Pi ^\prime$ denote the sum of the two vector spaces. We have

$$\begin{aligned} \dim _F(\Pi +\Pi ^\prime )=\dim (\Pi )+\dim _F(\Pi ^\prime )-\dim _F(\Pi \cap \Pi ^\prime ). \end{aligned}$$

Definition 6.1

If $\Pi ^\prime \in {\text {Gr}}(d-k,d;F)$, let

(6.1)

$A_{\Pi ^\prime }$ is a codimension-one subvariety of ${\text {Gr}}(k,d;F)$.

6.1.1 Orientation

When working over $\mathbb {R}$, we will frequently consider pairs of vector spaces $(\Pi ,\Pi ^\prime )$ with $\Pi \in {\text {Gr}}(k,d;\mathbb {R})$ and $\Pi ^\prime \in {\text {Gr}}(d-k,d,\mathbb {R})$. If $\Pi =\langle v_1,\ldots ,v_k\rangle$ and $\Pi ^\prime =\langle v_{k+1},\ldots ,v_d\rangle$, where $v_1,\ldots ,v_k$ and $v_{k+1},\ldots ,v_{d}$ are orthogonal unit vectors, then $\dim _{\mathbb {R}}(\Pi +\Pi ^\prime )<d$ if and only if $\det (v_1,\ldots ,v_d)=0$. If $\dim _{\mathbb {R}}(\Pi +\Pi ^\prime )=d,$ we wish to make sense of the expression $\det (\Pi ,\Pi ^\prime )$.

A reasonable first definition would be to define $\det (\Pi ,\Pi ^\prime )=\det (v_1,\ldots ,v_d)$. While the magnitude $|\det (\Pi ,\Pi ^\prime )|$ is well defined, the sign is not—if we permute two vectors from $\{v_1,\ldots ,v_k\}$ or $\{v_{k+1},\ldots ,v_d\}$, then the sign of the above determinant changes.

Ideally, we would like to find continuous functions $v_1(\Pi ),\ldots ,v_k(\Pi )$ and $v_{k+1}(\Pi ^\prime ),\ldots ,v_{d}(\Pi ^\prime )$ so that we can define

$$\begin{aligned} \det (\Pi ,\Pi ^\prime )=\det (v_1(\Pi ), \ldots ,v_k(\Pi ), v_{k+1} (\Pi ^\prime ),v_d(\Pi ^\prime )). \end{aligned}$$

(6.2)

While we cannot do this globally, we can do so locally.

Lemma 6.1

Fix $\Pi _0\in {\text {Gr}}(k,d;\mathbb {R})$ and $\Pi _0^\prime \in {\text {Gr}}(d-k,d,\mathbb {R})$. Then there exist small neighborhoods $U\subset {\text {Gr}}(k,d;\mathbb {R})$ and $U^\prime \subset {\text {Gr}}(d-k,d;\mathbb {R})$ of $\Pi$ and $\Pi ^\prime$, respectively, and functions $v_1,\ldots ,v_k:~ U\rightarrow \mathbb {R}^d$, $v_{k+1},\ldots ,v_d:~ U^\prime \rightarrow \mathbb {R}^d$ so that $v_1(\Pi ),\ldots ,v_k(\Pi )$ and $v_{k+1}(\Pi ^\prime ),\ldots ,v_{d}(\Pi ^\prime )$ are orthogonal unit vectors, and

$$\begin{aligned} \Pi =\langle v_1(\Pi ),\ldots ,v_k(\Pi )\rangle ,\ \ \Pi ^\prime = \langle v_{k+1}(\Pi ^\prime ),\ldots ,v_{d}(\Pi ^\prime )\rangle . \end{aligned}$$

We can now make sense of the expression (6.2). This observation will be used in the next lemma, which is an analogue of the intermediate value theorem. In this lemma it is essential that we work over $\mathbb {R}$.

Lemma 6.2

(Intermediate value theorem) Let $\Pi _0\in {\text {Gr}}(k,d;\mathbb {R})$ and $\Pi _0^\prime \in {\text {Gr}}(d-k,d;\mathbb {R})$. Then we can find a neighborhood $U\subset {\text {Gr}}(k,d;\mathbb {R})$ of $\Pi _0$ so that the following holds. If $\eta :~ [0,1]\rightarrow U$ is continuous, and if

$$\begin{aligned} (\det (\eta (0),\Pi ^\prime ))(\det (\eta (1),\Pi ^\prime ))<0, \end{aligned}$$

then there exists $t\in (0,1)$ so that $\eta (t)\in A_{\Pi ^\prime }$.

Proof

Let U be the neighborhood of $\Pi _0$ from Lemma 6.1, and let $v_1(\Pi ),\ldots ,$ $v_k(\Pi )$ and $v_{k+1}(\Pi ^\prime ),\ldots ,v_{d}(\Pi ^\prime )$ be the corresponding unit vectors. Then the function

$$\begin{aligned} f(t)=\det (v_1(\eta (t)),\ldots ,v_k(\eta (t)), v_{k+1} (\Pi _0^\prime ), \ldots ,v_{d}(\Pi _0^\prime )) \end{aligned}$$

(6.3)

is continuous, and $f(0)f(1)<0$. So by the intermediate value theorem, we can find $t\in (0,1)$ with $f(t)=0$. But this implies that $\eta (t) \in A_{\Pi _0^\prime }$. $\square$

6.1.2 The Gauss Map and Gauss Image of a Variety

In this section we will define the Gauss map and discuss a few of its properties. Further information can be found in [12, Chap. 15].

Definition 6.2

Let $Z\subset \mathbb {C}^d$ be a k-dimensional variety. For each point $z\in Z_{{\text {smooth}}},$ we define the Gauss map

$$\begin{aligned} G(z;Z)= T_z(Z)\in {\text {Gr}}(k,d;\mathbb {C}), \end{aligned}$$

(6.4)

and the extended Gauss map

$$\begin{aligned} G^\dagger (z;Z)= (z,T_z(Z))\in \mathbb {C}^d \times {\text {Gr}}(k,d;\mathbb {C}). \end{aligned}$$

(6.5)

Following notation from [12], we define ${\mathcal {F}}(Z)$ to be the Zariski closure of $G(Z_{{\text {smooth}}};Z)$, and we define ${\mathcal {F}}^{\dagger }(Z)$ to be the Zariski closure of $G^\dagger (Z_{{\text {smooth}}};Z)$.

6.1.3 Some Transversality Arguments

Let $Z\subset \mathbb {C}^d$ be a k-dimensional variety, and let $\zeta \subset Z$ be an irreducible curve, with $\zeta \not \subset Z_{{\text {sing}}}$. We will be interested in the tangent planes to Z at points $z\in \zeta$. To make this more precise, define

$$\begin{aligned} {\mathcal {G}}_{Z,\zeta } = {\overline{G(\zeta \cap Z_{{\text {smooth}}};Z)}.} \end{aligned}$$

The idea is that ${\mathcal {G}}_{Z,\zeta }$ is the closure of the set of k-planes tangent to Z at some point $z\in \zeta \cap Z_{{\text {smooth}}}$. ${\mathcal {G}}_{Z,\zeta }$ is a variety of dimension at most one.

Lemma 6.3

Let $\Pi \in {\text {Gr}}(k,d;\mathbb {C}),$ and let $v\in T_\Pi ({\text {Gr}}(k,d;\mathbb {C}))$ be generic (with respect to $\Pi$). Then the variety

is a subvariety of  ${\text {Gr}}(d-k,k;\mathbb {C})$ of codimension $\ge 2.$

Proof

This is simply the observation that the requirements $\Pi \in A_{\Pi ^\prime }$ and $v\in T_{\Pi }(A_{\Pi ^\prime })$ are independent constraints on $\Pi ^\prime$.

More precisely, note that $\{\Pi ^\prime \in {\text {Gr}}(d-k,d;\mathbb {C}):~ \Pi \in A_{\Pi ^\prime }\}$ is a codimension-one subvariety of ${\text {Gr}}(d-k,k;\mathbb {C})$ (indeed, it is isomorphic to $A_{\Pi }$) that contains $X_{\Pi ,v}$. Suppose there is some irreducible component $Z\subset \{\Pi ^\prime \in {\text {Gr}}(d-k,d;\mathbb {C}):~ \Pi \in A_{\Pi ^\prime }\}$ that is contained in $X_{\Pi ,v}$. In particular, this would imply that the set $\{\Pi ^\prime \in Z:~ \Pi \in (A_{\Pi ^\prime })_{{\text {smooth}}}\}$ is Zariski dense in Z.

If Z is contained in $X_{\Pi ,v}$, this implies that for a generic choice of $v\in T_\Pi ({\text {Gr}}(k,d;\mathbb {C}))$, we have $v\in T_{\Pi }(A_{\Pi ^\prime })$ for a dense set of $\Pi ^\prime \in Z$. This implies that for a dense set of $\Pi ^\prime \in Z$, $v\in T_{\Pi }(A_{\Pi ^\prime })$ for generic (and thus every) $v\in T_\Pi ({\text {Gr}}(k,d;\mathbb {C}))$. But, if $\Pi ^\prime$ is a smooth point of Z, then the tangent plane $T_{\Pi }(Z)$ has codimension-one in $T_{\Pi }A_{\Pi ^\prime }$.

We conclude that no irreducible components of $\{\Pi ^\prime \in {\text {Gr}}(d-k,d;\mathbb {C}):~ \Pi \in A_{\Pi ^\prime }\}$ can be contained in $X_{\Pi ,v}$. Thus the codimension of $X_{\Pi ,v}$ in ${\text {Gr}}(d-k,k;\mathbb {C})$ is at least two. $\square$

Lemma 6.4

Let $Z\subset \mathbb {C}^d$ be a k-dimensional variety, and let $\zeta \subset Z$ be an irreducible curve, with $\zeta \not \subset Z_{{\text {sing}}}$. If we select a generic (with respect to Z and $\zeta$) element $\Pi ^\prime \in {\text {Gr}}(d-k,d,\mathbb {C}),$ then for all pairs $(z,\Pi )$ with $z\in \zeta _{{\text {smooth}}}\cap Z_{{\text {smooth}}},$ $(z,\Pi )\in {\mathcal {F}}^{\dagger }(Z)$, and $\Pi \in A_{\Pi ^\prime }$, we have that $\Pi$ is a smooth point of $A_{\Pi ^\prime }$, and ${\mathcal {G}}_{Z,\zeta }$ is transverse to $A_{\Pi ^\prime }$ at $\Pi$.

Proof

The idea is the following. For each point $z\in \zeta \cap Z_{{\text {smooth}}}$, there is a unique tangent plane $T_z(Z)\in {\text {Gr}}(k,d;\mathbb {C})$. The set of all such points forms a curve $\alpha$ in ${\text {Gr}}(k,d;\mathbb {C})$ (technically, we need to take the closure of this curve in the Zariski topology). Now, given a $(d-k)$-plane $\Pi ^\prime \in {\text {Gr}}(d-k,d;\mathbb {C})$, we can ask: does the variety $A_{\Pi ^\prime }$ meet the curve $\alpha$ tangentially? We will show that for generic $\Pi ^\prime \in {\text {Gr}}(d-k,d;\mathbb {C})$, the answer is no. The reason is that for each point $\Pi \in \alpha$, the set of planes $\Pi ^\prime \in {\text {Gr}}(d-k,d;\mathbb {C})$ that hit the point $\Pi$ and that are tangent to $\alpha$ at $\Pi$ are contained in a codimension-two subvariety of ${\text {Gr}}(d-k,d;\mathbb {C})$. Since $\alpha$ is one-dimensional, the set of planes $\Pi ^\prime$ that are tangent at some point $\Pi \in \alpha$ is contained in a codimension-one variety. This means that generically, this does not happen.

Now for the details. Let

$$\begin{aligned} M= & {} \{((\Pi ,v), \Pi ^\prime )\in (T{\text {Gr}}(k,d;\mathbb {C}))\times {\text {Gr}}(d-k,d;\mathbb {C}):~ \nonumber \\&\quad \Pi \in {\mathcal {G}}_{Z,\zeta },\ v\in T_{\Pi }({\mathcal {G}}_{Z,\zeta }), \Pi \in (A_{\Pi ^\prime })_{{\text {smooth}}},\ v\in T_{\Pi }(A_{\Pi ^\prime })\}. \end{aligned}$$

(6.6)

We wish to show that $\dim \overline{M}\le \dim ({\text {Gr}}(d-k,d;\mathbb {C}))-1.$ By Lemma 6.3, for each $(\Pi ,v)\in (T{\text {Gr}}(k,d;\mathbb {C}))$ with $\Pi \in {\mathcal {G}}_{Z,\zeta }$ and $v\in T_{\Pi }({\mathcal {G}}_{Z,\zeta }),$ the set of $\Pi ^\prime$ so that $((\Pi ,v),\Pi ^\prime )\in M$ is contained in a variety of dimension $\dim ({\text {Gr}}(d-k,d;\mathbb {C}))-2$, i.e., each fiber of the projection map $M\rightarrow T{\text {Gr}}(k,d;\mathbb {C})$ has dimension at most $\dim ({\text {Gr}}(d-k,d;\mathbb {C}))-2$. But since ${\mathcal {G}}_{Z,\zeta }$ has dimension at most one, the image of the map $M\rightarrow T{\text {Gr}}(k,d;\mathbb {C})$ has dimension at most 1, so M has dimension at most $\dim ({\text {Gr}}(d-k,d;\mathbb {C}))-1.$

Thus if we consider the projection $M\rightarrow {\text {Gr}}(d-k,d;\mathbb {C}),$ the image of this projection is contained in a proper subvariety of ${\text {Gr}}(d-k,d;\mathbb {C})$, i.e., a generic element $\Pi ^\prime \in {\text {Gr}}(d-k,d;\mathbb {C})$ is not contained in the image of the projection.

All that remains is to show that for generic $\Pi ^\prime$, $\Pi$ is a smooth point of $A_{\Pi ^\prime }$ for all $(z,\Pi )$ with $z\in \zeta _{{\text {smooth}}}\cap Z_{{\text {smooth}}},\ (z,\Pi )\in {\mathcal {F}}^\dagger (Z)$, and $\Pi \in {\mathcal {A}}_{\Pi ^\prime }$. But if we define

$$\begin{aligned} M_1= & {} \{((\Pi ,v), \Pi ^\prime )\in (T{\text {Gr}}(k,d;\mathbb {C}))\times {\text {Gr}}(d-k,d;\mathbb {C}):~ \nonumber \\&\quad \Pi \in {\mathcal {G}}_{Z,\zeta },\ v\in T_{\Pi }({\mathcal {G}}_{Z,\zeta }), \Pi \in (A_{\Pi ^\prime })_{{\text {sing}}}\}, \end{aligned}$$

(6.7)

then since $\dim (A_{\Pi ^\prime })_{{\text {sing}}}\le \dim (d-k,d;\mathbb {C})-2,$ a similar argument shows that a generic element $\Pi ^\prime \in {\text {Gr}}(d-k,d;\mathbb {C})$ is not contained in the image of the projection $M_1\rightarrow {\text {Gr}}(d-k,d;\mathbb {C})$. $\square$

Lemma 6.5

Let $Z\subset \mathbb {C}^d$ be a k-dimensional variety defined by real polynomials, and let $\zeta \subset Z$ be an irreducible curve defined by real polynomials. Suppose that $Z(\mathbb {R})$ is k-dimensional, $\zeta (\mathbb {R})$ is one-dimensional, and that $\zeta$ is not contained in $Z_{{\text {sing}}}$. Let $\Pi ^\prime \in {\text {Gr}}(d-k,d,\mathbb {R})$ be chosen generically with respect to Z and $\zeta$.

Let $z\in \zeta (\mathbb {R})_{{\text {smooth}}}\cap Z(\mathbb {R})_{{\text {smooth}}}$ and suppose that $T_z(Z)\in A_{\Pi ^\prime }$. Then for all $\varepsilon >0$ we can find an interval $I\subset \zeta$ centered at z with the following two properties: (1) I has arclength $\le \varepsilon$. (2) If $z_1,z_2$ are the two endpoints of I, and if $\Pi _1 = T_{z_1}(Z(\mathbb {R})),\ \Pi _2 = T_{z_2}(Z(\mathbb {R})),$ then

$$\begin{aligned} (\det (\Pi _1,\Pi ^\prime ))(\det (\Pi _2,\Pi ^\prime ))<0. \end{aligned}$$

(6.8)

Remark 6.1

See Sect. 6.1.1 for a discussion of the definition of $\det$. In this context, the determinant is only defined up to a choice of sign. However, the statement that two determinants have opposite sign is well defined regardless of the orientation chosen (again, in a small neighborhood of a point $\Pi \in {\text {Gr}}(k,d;\mathbb {R})$).

Proof of Lemma 6.5

In brief, the proof consists of the following observation. If $U\subset \mathbb {R}^\ell$ is an open set and $A\subset U$ is a smooth manifold such that $U\backslash A$ contains two connected components, and if $\alpha \subset U$ is a smooth curve that meets A transversely at the point $x\in \alpha \cap A$, then $\alpha$ must enter both connected components of $U\backslash A$. Furthermore, we can find points $x_1,x_2\in \alpha$ arbitrarily close to x such that $x_1,x_2$ lie in separate connected components of $U\backslash A$.

Now for the proof. Let $\Pi _0=T_z(Z)$. By Lemma 6.4, $\Pi ^\prime$ is a smooth point of $A_{(\Pi ^\prime )^*}$, and ${\mathcal {G}}(\zeta ,Z)$ is transverse to $A_{(\Pi ^\prime )^*}$ at $\Pi ^\prime$ (recall that $\Pi ^\prime$ is a real $(d-k)$-plane, and $(\Pi ^\prime )^*$ is its complexification). Since $\zeta (\mathbb {R})$ is one-dimensional and $\Pi ^\prime$ was chosen generically, we can assume that z is a smooth point of $\zeta$, and thus $\zeta (\mathbb {R})$ is a one-dimensional smooth manifold in a (Euclidean) neighborhood of z.

We conclude that ${\mathcal {G}}(\zeta (\mathbb {R}),Z(\mathbb {R}))$ is a smooth curve in ${\text {Gr}}(k,d;\mathbb {R})$ in a neighborhood of the (real) k-plane $\Pi _0(\mathbb {R})\in {\text {Gr}}(k,d;\mathbb {R})$, and this curve is transverse to $A_{\Pi ^\prime (\mathbb {R})}$ at the point $\Pi _0(\mathbb {R})$. Use Lemma 6.1 to choose a small neighborhood U of $\Pi _0(\mathbb {R}),$ and functions $v_1(\Pi ),\ldots ,v_k(\Pi ):~ U\rightarrow \mathbb {R}^d$ so that $\Pi ={\text {span}}\{v_1(\Pi ),\ldots ,v_k(\Pi )\}$. This allows us to define $\det (\Pi ,\Pi ^\prime )$ for all $\Pi \in U$.

Now, after possibly shrinking U, $A_{\Pi ^\prime }\cap U$ is a smooth manifold, and $A_{\Pi ^\prime }\cap U$ cuts ${\text {Gr}}(k,d;\mathbb {R})\cap U$ into two connected regions: one where $\det (\Pi ,\Pi ^\prime )>0$ and one where $\det (\Pi ,\Pi ^\prime )<0.$ Select two points $z_1,z_2\in \gamma (\mathbb {R})$ so that $T_{z_1}(\gamma (\mathbb {R}),Z(\mathbb {R}))\in U$, $T_{z_2}(\gamma (\mathbb {R}),Z(\mathbb {R}))\in U,$ and with $T_{z_1}(\gamma (\mathbb {R}),Z(\mathbb {R}))$ and $T_{z_2}(\gamma (\mathbb {R}),Z(\mathbb {R}))$ in opposite regions. Since ${\mathcal {G}}(\zeta (\mathbb {R}),Z(\mathbb {R}))$ is transverse to $A_{\Pi ^\prime }\subset {\text {Gr}}(k,d;\mathbb {R})$ at $\Pi _0(\mathbb {R})$, (6.8) holds with this choice of $z_1,z_2$. $\square$

6.1.4 Complex Varieties and Some Perturbative Arguments

Definition 6.3

If $k<d$ and $\pi _v:~ F^d\rightarrow F^{d-1}$ is a projection in the direction v, let

be the associated map on the Grassmannian.

We end with the following observation. Let $Z\subset \mathbb {C}^4$ be a two-dimensional variety and let $\pi _v:~\mathbb {C}^4\rightarrow \mathbb {C}^3$ be a projection. If $z\in Z_{{\text {smooth}}},$ $\Pi \in G(z;Z),$ and $v\notin \Pi ,$ then $\tilde{\pi }(\Pi )$ is two-dimensional and $\tilde{\pi }(\Pi )\in G(z;\overline{\pi (Z)})$.

6.2 Perturbations and the Gauss Map

In this section we will prove a technical lemma that will be useful when we have to cut the surfaces $V_j(\mathbb {R})$ into pieces. In the next section we will be confronted with an irreducible two-dimensional variety W that is a component of the intersection $Z_{\mathbb {C}}(R_1)\cap Z_{\mathbb {C}}(R_2)$. We will need to understand smooth points $z\in W_{{\text {smooth}}}$ where the tangent plane $T_zW$ has certain properties. Ideally, $T_zW$ would be given by the two-dimensional vector space orthogonal to $\langle \nabla R_1(z),\nabla R_2(z)\rangle$. However, if $\langle \nabla R_1(z),\nabla R_2(z)\rangle$ is instead a zero- or one-dimensional vector space, then this will not work. Instead, we will consider $\langle \nabla R_1(z^\prime ),\nabla R_2(z^\prime )\rangle ,$ where $z^\prime$ is a point close to z. If we set things up carefully, then we can recover information about $T_zW$ from $\langle \nabla R_1(z^\prime ),\nabla R_2(z^\prime )\rangle$. This is made precise in Corollary 6.1.

Definition 6.4

For $R\in \mathbb {C}[x_1,\ldots ,x_4]$ and $z_0\in \mathbb {C}^4$, define $R^{z_0}=R(z)-R(z_0)$. In particular, $\mathbf {Z}_{\mathbb {C}}(R^{(z_0)})=\mathbf {Z}_{\mathbb {C}}(R(z)-R(z_0))$. This is the level set of R passing through the point $z_0$.

The following lemma is rather technical; the reader may wish to first look at Corollary 6.1, which may provide some motivation.

Lemma 6.6

Let $R_1,R_2\in \mathbb {C}[x_1,\ldots ,x_4]$, and let W be an irreducible component of $Z_{\mathbb {C}}(R_1)\cap Z_{\mathbb {C}}(R_2)$ and let $v,v_1\in \mathbb {C}^4$ be generic vectors (see Remark 6.2). Then there exists a curve $\zeta \subset W$ so that the following conditions hold:

• $\deg (\zeta )\lesssim (\deg R_1+\deg R_1)\deg W.$

• For all $z\in W_{{\text {smooth}}}\backslash \zeta ,$ $v_1\notin T_z(W)$.

• If $\tilde{\pi }=\tilde{\pi }_{v_1}:~{\text {Gr}}(2,4;\mathbb {C})\rightarrow {\text {Gr}}(2,3;\mathbb {C})$ is the corresponding map on the Grassmannian, $z\in W_{{\text {smooth}}}\backslash \zeta$, and if $U\subset \mathbb {C}$ is a sufficiently small neighborhood of 0, then the map

  

  (6.9)

  is continuous on U.

Remark 6.2

When we say that v is generic with respect to $R_1,R_2,W$, we mean that given any $R_1,R_2,W$, there is a Zariski open set $O\subset \mathbb {C}^4$ so that the lemma holds for any $v, v_1\in O$.

Remark 6.3

Heuristically, Lemma 6.6 says that the tangent plane to the level set of $R_1$ and $R_2$ passing through $z\in W$ is similar to that of the level set of $R_1$ and $R_2$ passing through $z+tv$, provided |t| is small and z does not lie on a small bad set. More precisely, Lemma 6.6 says that the (generic) projections of the two tangent planes into $\mathbb {C}^3$ are similar. Corollary 6.1 will let us recover the result about tangent planes in $\mathbb {C}^4$.

Remark 6.4

Let us understand the map $\rho _{\pi ,z}$. For $t\in \mathbb {C}$, let $z^\prime = z+tv$. Let

$$\begin{aligned} W^\prime =Z_{\mathbb {C}}(R_1^{(z+tv)})\cap Z_{\mathbb {C}}(R_2^{(z+tv)}). \end{aligned}$$

This is the intersection of the level sets of $R_1$ and $R_2$ that pass through $z^\prime$. Then the image of t under the above map is the projection of $T_{z^\prime }(W^\prime )$ to $\mathbb {C}^3$ (the projection is given by $\pi$).

Proof of Lemma 6.6

Let $L\subset \mathbb {C}^4$ be a 3-plane orthogonal to v, and let

First, consider the set

(6.10)

If $v_1$ (and thus $\pi$) is chosen generically³ with respect to $R_1$ and $R_2$, then (6.10) is not all of $\mathbb {C}^4$. Indeed, it is a proper algebraic variety of dimension at most three and degree $O(\deg R_1+\deg R_2)$. In particular, the intersection of (6.10) with a generic (with respect to $R_1, R_2, v_1$ and v) translate of L has dimension at most two. This implies that $B_1^\prime$ is contained in a two-dimensional variety $B_1^{\prime \prime }$ of degree $O(\deg R_1+\deg R_2)$ (to obtain such a variety, simply intersect the set (6.10) with a generic translate of L).

Let $B_1^{\prime \prime \prime }=\pi _v^{-1}(\pi _v(B_1^{\prime \prime }))$ be the extension of $B_1^{\prime \prime }$ in the direction v. So $B_1^{\prime \prime \prime }$ is a three-dimensional variety of degree $O(\deg R_1+\deg R_2).$ Let $B_1=B_1^{\prime \prime \prime }\cap W$. We can assume that $\dim _{\mathbb {C}}(B_1)\le 1$. Indeed, if $\dim _{\mathbb {C}}(B_1)=2$, then $B_1=W$, and this would imply that $(6.10) =\mathbb {C}^{4}$, and we have already shown that this is not the case.

Let $z\in W_{{\text {smooth}}}\backslash B_1$. Then for any $t\ne 0$ in a sufficiently small (Euclidean) neighborhood of 0, we have $\pi (\nabla R_1(z+tv))\times \pi (\nabla R_2(z+tv))\ne 0$. Note that since $\pi (\nabla R_1(z+tv))$ and $\pi (\nabla R_2(z+tv))$ are vectors in $\mathbb {C}^3$, the cross product is well defined.

Thus, we can define

$$\begin{aligned} \lambda (z,t) = \frac{\pi (\nabla R_1(z+tv))\times \pi (\nabla R_2(z+tv)) }{|\pi (\nabla R_1(z+tv))\times \pi (\nabla R_2(z+tv))|}. \end{aligned}$$

Note that if $z \in W\backslash B_1$, then $|\pi (\nabla R_1(z+tv))\times \pi (\nabla R_2(z+tv))|$ does not vanish identically in t. Write

$$\begin{aligned} \pi (\nabla R_1(z+tv)\times \pi (\nabla R_2(z+tv))=(v_1(z,t),v_2(z,t),v_3(z,t)). \end{aligned}$$

We can expand $v_j(z,t)=\sum t^i\theta _{i,j}(z)$. For each $j=1,2,3,$ let $i_j$ be the minimum index so that $\theta _{i,j}(z)$ does not vanish identically on W. For notational convenience, we will assume that $i_1=\min (i_1,i_2,i_3)$ (if not, then just permute the indices). Let $B_2=W\cap Z_{\mathbb {C}}(\theta _{i_1})$. Note that $\deg (\theta _{i_1})\lesssim \deg R_1 + \deg R_2$.

Let $v_j^{\dagger }(z,t)=t^{-i_1}(z,t)$, and let

$$\begin{aligned} \lambda (z,t)^{\dagger }=\frac{(v_1^{\dagger }(z,t), v_2^{\dagger }(z,t),v_3^{\dagger }(z,t))}{\big (|v_1^{\dagger } (z,t)|^2+|v_2^{\dagger }(z,t)|^2+|v_3^{\dagger }(z,t)|^2\big )^{1/2}}. \end{aligned}$$

Define $\zeta =B_1\cup B_2$ and let $W^\prime = W_{{\text {smooth}}}\backslash \zeta$. If $z\in W^\prime$, then the denominator of $\lambda ^\dagger (z,t)$ does not vanish when $t=0$, so in particular $\lambda ^\dagger (z,t)$ is a smooth function of t in a neighborhood of 0. Furthermore, for $t\ne 0$, $\lambda ^{\dagger }(z,t)=\lambda (z,t)$, and for all t (in a neighborhood of 0), $\lambda ^\dagger (z,t)$ is the normal vector to the 2-plane $\tilde{\pi }(\rho _z(t))$. This implies that $\tilde{\pi }\rho _z(t)$ is continuous for t in a neighborhood of $t=0$, as desired. $\square$

Corollary 6.1

Let $R_1,R_2\in \mathbb {C}[x_1,\ldots ,x_4]$, and let W be an irreducible component of $\mathbf {Z}_{\mathbb {C}}(R_1)\cap \mathbf {Z}_{\mathbb {C}}(R_2)$. Let $v\in \mathbb {C}^4$ be a generic vector (as described in Remark 6.2). Then there exists a curve $\zeta$ (depending only on W and v) with

$$\begin{aligned} \deg (\zeta )\lesssim (\deg R_1+\deg R_2)\deg W \end{aligned}$$

so that if $z\in W_{{\text {smooth}}}\backslash \zeta$ and if $U\subset \mathbb {C}$ is a sufficiently small neighborhood of 0, then the map

(6.11)

is continuous on U.

Proof

Let $v_1,v_2,v_3,v_4$ be generic vectors, and apply Lemma 6.6 to the collection $\{R_1,R_2,W,$ $v,v_i\},\ i=1,2,3,4.$ Let $U_1,U_2,U_3,U_4\subset \mathbb {C}$ be the resulting open neighborhoods of 0, and let $\zeta _1,\zeta _2,\zeta _3,\zeta _4\subset W$ be the resulting curves. Let $U=U_1\cap U_2\cap U_3\cap U_4$ and let $\zeta =\zeta _1\cup \zeta _2\cup \zeta _3\cup \zeta _4$.

By Lemma 6.6 the maps

$$\begin{aligned} t\mapsto \tilde{\pi }_{v_i} (T_{z+tv}(Z_{\mathbb {C}}(R_1^{(z+tv)})\cap Z_{\mathbb {C}}(R_2^{(z+tv_1)}))),\ i=1,2,3,4, \end{aligned}$$

(6.12)

are continuous for $t\in U$ and $z\in W\backslash \zeta$. However, the map

has full rank at every point $\Pi _0$ for which $(\Pi _0+\langle v_1\rangle )\cap (\Pi _0+ \langle v_2\rangle )\cap (\Pi _0+\langle v_3\rangle )\cap (\Pi _0+\langle v_4\rangle )=\Pi _0$. Since $v_1,v_2,v_3,v_4$ were chosen generically, this condition will hold at every point. This implies that the map

$$\begin{aligned} t\mapsto T_{z+tv}(Z_{\mathbb {C}}(R_1^{(z+tv)})\cap Z_{\mathbb {C}}(R_2^{(z+tv_1)})) \end{aligned}$$

(6.13)

is continuous for $t\in U$ and $z\in W\backslash \zeta$. $\square$

7 Bounding $I_6$: Cutting a Variety into Open Regions

In order to bound the incidences in $I_6$, we will cut each surface $V_i(\mathbb {R})$ and each curve $\{\gamma (\mathbb {R}):~\gamma \in \Gamma _{S,i}^{(3)}\}$ into pieces. On each piece of $V_i(\mathbb {R})$, we will have an arrangement of points and curves. In later sections, we will apply the crossing lemma to each of these arrangements to bound the number of point-curve incidences in terms of the number of curve–curve crossings, plus an error term.

7.1 Defining Some Bad Points on the Curves

In this section we will define various bad points on the curves in $\Gamma _{S,i}^{(3)}$. After these points are removed, the real locus of $\gamma$ will consist of a collection of simple open curves, which will be amenable to crossing lemma type arguments. First, we must deal with a small technical annoyance.

7.1.1 Incidences Occurring on the Bad Sets $\zeta$

Fix a generic vector $v\in \mathbb {C}^4$. For each index $i=1,\ldots ,\ell$ and each irreducible component $W\subset V_i$, let $\zeta _W$ be the bad set obtained by applying Corollary 6.1 to W, using the generic vector v. Let

$$\begin{aligned} \zeta _i = \bigcup _{W}\zeta _W, \end{aligned}$$

(7.1)

where the union is taken over all irreducible components $W\subset V_i$, and let

By Corollary 6.1, $\zeta _i$ has degree $\sum _{W} O(D_i+E_i)\deg W=O(D_iE_i^2).$ Thus if we define

$$\begin{aligned} \zeta = \bigcup _i\zeta _i, \end{aligned}$$

then $\deg \zeta =O(\sum _i(D_iE_i^2))$. By Lemma 4.8,

$$\begin{aligned} |I_7|\lesssim m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}+m. \end{aligned}$$

(7.2)

The idea is that we will decompose each variety $V_i(\mathbb {R})_{{\text {smooth}}}$ into a disjoint collection of pieces, each of which is homeomorphic to an open subset of $\mathbb {R}^2$. With a few exceptions, incidences between points on $V_i(\mathbb {R})_{{\text {smooth}}}$ and curves lying in $\Gamma _{S,i}^{(3)}$ will be counted using the crossing lemma. By $V_i(\mathbb {R})_{{\text {smooth}}},$ we will mean points of $V_i(\mathbb {R})$ that are smooth in dimension 2. If $\dim _{\mathbb {R}}(V_i(\mathbb {R}))<2$, then by Corollary 4.1, $V_i(\mathbb {R})\subset (V_i)_{{\text {sing}}}$, and all incidences on $V_i$ have already been counted.

Select a generic (real) 2-plane $\Pi ^\prime \in {\text {Gr}}(2,4;\mathbb {R})$. For each index i, define

(7.3)

For each $\gamma \in \Gamma _{S,i}^{(3)}$, we will define various types of bad points. For $S\in \mathcal {S}_2,$ define

$$\begin{aligned} \alpha _{S,i}=\bigcup _{\gamma \in \Gamma _{S,i}^{(3)}}\gamma . \end{aligned}$$

(7.4)

Define

$$\begin{aligned}&\Xi _{\gamma , {\text {sing}}} = \gamma \cap (\alpha _{S,i})_{{\text {sing}}}, \end{aligned}$$

(7.5)

$$\begin{aligned}&\Xi _{\gamma , {\text {shared}}}=\{z\in \gamma :~ z\ \text {is an isolated point of}\ \gamma \cap V_{i^\prime }\ \text {for some}\ i^\prime \ne i\}, \end{aligned}$$

(7.6)

$$\begin{aligned}&\Xi _{\gamma ,{\text {dir}}}=\{z\in \gamma _{{\text {smooth}}}:~ T_z(\gamma )\cdot v_1=0\}, \end{aligned}$$

(7.7)

$$\begin{aligned}&\Xi _{\gamma ,{\text {singPt}}}=\gamma _{{\text {smooth}}}\cap (V_i)_{{\text {sing}}}, \end{aligned}$$

(7.8)

$$\begin{aligned}&\Xi _{\gamma ,{\text {vertPt}}}=\gamma _{{\text {smooth}}}\cap B_i. \end{aligned}$$

(7.9)

In (7.7), $v_1$ is a generic unit vector. By generic, we mean that $v_1$ and $\Pi ^\prime$ are generic with respect to the collection $\mathcal {S}_2,$ the points $\mathcal {P}$, and the polynomials $\{P_j\}$ and $\{Q_j\}$.

Finally, define

$$\begin{aligned} \Xi _{\gamma ,{\text {badPt}}}= (7.5) \cup \cdots \cup (7.9). \end{aligned}$$

(7.10)

7.2 Bounding the Sets $(7.5),\ldots ,(7.9)$

We first record the following corollary of Lemma 4.6

Corollary 7.1

For each $S\in \mathcal {S}_2$ and each index i,

$$\begin{aligned} \sum _{z\in \alpha _{S,i}}G_z(\alpha _{S,i})&\lesssim D_i^2, \end{aligned}$$

(7.11)

$$\begin{aligned} \sum _{\gamma \in \Gamma _{S,i}^{(3)}} \sum _{z\in \gamma _{{\text {sing}}}}G_z(\gamma )&\lesssim D_i^2. \end{aligned}$$

(7.12)

Lemma 7.1

For each $\gamma \in \Gamma _{S,i}^{(3)}$,

$$\begin{aligned} |\Xi _{\gamma , {\text {shared}}}|\lesssim \deg \gamma \sum _i(D_i+E_i). \end{aligned}$$

(7.13)

Proof

If $x\in \Xi _{\gamma , {\text {shared}}},$ then x is an isolated intersection point of $\gamma \cap \mathbf {Z}_{\mathbb {C}}(P_{i^\prime })$ or $\gamma \cap \mathbf {Z}_{\mathbb {C}}(Q_{i^\prime })$ for some $i^\prime \ne i$. By Bézout’s theorem (Proposition 4.1), the number of times this can occur is bounded by the RHS of (7.13). $\square$

Lemma 7.2

For each $S\in \mathcal {S}_2$ and each $\gamma \in \Gamma _{S,i}^{(3)},$

$$\begin{aligned} |\Xi _{\gamma ,{\text {dir}}}|\lesssim \deg (\gamma )^2. \end{aligned}$$

(7.14)

Proof

After a rotation, we can assume that $v_1=(1,0,0,0)$. Let $\gamma ^\prime =\overline{\pi (\gamma )}$, where $\pi$ is the projection onto the $(x_1,x_2)$-plane. Note that $\deg \gamma ^\prime =\deg \gamma$. Since $v_1$ was chosen generically, $z\in \Xi _{\gamma ,{\text {dir}}}$ if and only if $z\in \gamma ^\prime _{{\text {smooth}}}$ and $T_{\pi (z)}(\pi (\gamma ^\prime ))\cdot \pi (v_1)=0$. Let $f_{\gamma ^\prime }$ be a square-free polynomial such that $Z(f_{\gamma ^\prime })=\gamma ^\prime$. We have $\deg f_{\gamma ^\prime }\le \deg \gamma ^\prime =\deg \gamma$. Then

$$\begin{aligned} \{z\in \gamma _{{\text {smooth}}}:~ T_{\pi (z)}(\pi (\gamma ))\cdot \pi (v_1)=0\}\subset \gamma ^\prime \cap \mathbf {Z}_{\mathbb {C}}( \pi (v_1)\cdot \nabla f_{\gamma ^\prime }). \end{aligned}$$

The latter set has cardinality $O(\deg (\gamma )^2)$. $\square$

Lemma 7.3

For each $S\in \mathcal {S}_2$ and each index i,

$$\begin{aligned} \sum _{\gamma \in \Gamma _{S,i}^{(3)}}| \Xi _{\gamma ,{\text {singPt}}}| \lesssim D_iE_i+\sum _{\gamma \in \Gamma _{S,i}^{(3)}}(\deg \gamma )^2. \end{aligned}$$

(7.15)

Proof

Factor $V_i$ into irreducible components $W_{i,j}$. Recall that if $\gamma \in \Gamma _{S,i}^{(3)},$ then a generic point $x\in \gamma$ lies in $(V_i)_{{\text {smooth}}},$ so in particular, $\gamma$ is contained in $W_{i,j}$ for precisely one index j. Furthermore, we have $T_x(S^*)\ne T_x(V_i)$ at a generic point $x\in \gamma$. If $x\in \Xi _{\gamma ,{\text {singPt}}}$ has not already been placed in $\Xi _{\gamma ,{\text {sing}}}$, then x is a smooth point of $\gamma$. We can now apply the argument used to bound $|I_5|$ (Sect. 5.4) to conclude that for each index j,

$$\begin{aligned} \sum _{\begin{array}{c} \gamma \in \Gamma _{S,i}^{(3)},\\ \gamma \subset W_j \end{array}}|\Xi _{\gamma ,{\text {singPt}}}|\lesssim \deg W_{i,j}+\sum _{\begin{array}{c} \gamma \in \Gamma _{S,i}^{(3)},\\ \gamma \subset W_j \end{array}}(\deg \gamma )^2. \end{aligned}$$

(7.16)

Summing (7.16) over all irreducible components of $V_i$ yields (7.3). $\square$

Lemma 7.4

For each $\gamma \in \Gamma _{S,i}^{(3)}$,

$$\begin{aligned} |\Xi _{\gamma ,{\text {vertPt}}}|\lesssim \deg (\gamma )E_i. \end{aligned}$$

(7.17)

Proof

Let $W\subset V_i$ be the (unique) irreducible component of $V_i$ that contains $\gamma$. For each $z_0\in \Xi _{\gamma ,{\text {vertPt}}}$, we can select a small interval $\beta _{z_0}\subset \gamma (\mathbb {R})$ that contains $z_0$, so that the intervals $\{\beta _{z_0}\}_{z_0\in \Xi _{\gamma ,{\text {vertPt}}}}$ are disjoint.

By Lemma 6.5, we can assume (after shrinking $\beta _{z_0}$ if necessary) that for each interval $\beta _{z_0}$, we have

$$\begin{aligned} (\det (T_{z_0^\prime }(W(\mathbb {R})),\Pi ^\prime )) (\det (T_{z_0^{\prime \prime }}(W(\mathbb {R})),\Pi ^\prime ))<-\varepsilon _1, \end{aligned}$$

(7.18)

where $z_0^\prime$ and $z_0^{\prime \prime }$ are the two endpoints of the curve $\beta _{z_0}$, and $\Pi ^\prime$ is the 2-plane from (7.3). Here $\varepsilon _1>0$ is some sufficiently small constant, depending on $W,\ \gamma ,$ and $\Pi ^\prime$.

By Corollary 6.1, we have that if we select $\varepsilon _2>0$ sufficiently small depending on $\varepsilon _1$, then if we let $\tilde{\beta }_{z_0} = \beta _{z_0}+ \varepsilon _2 v$ (here v is the vector from Sect. 7.1.1), and define $\tilde{z}_0^\prime =z_0^\prime +\varepsilon _2v,\ \tilde{z}_0^{\prime \prime }=z_0^{\prime \prime }+\varepsilon _2 v$, then

$$\begin{aligned} (\det (T_{\tilde{z}_0^\prime }(W(\mathbb {R})),\Pi ^\prime ))(\det (T_{\tilde{z}_0^{\prime \prime }}(W(\mathbb {R})),\Pi ^\prime ))<0. \end{aligned}$$

(7.19)

Fix vectors $v_3,v_4$ so that $\Pi ^\prime =\langle v_3,v_4\rangle .$ Define the function

$$\begin{aligned} \Psi (z)= \det \left[ \begin{array}{c} \nabla P_j\\ \nabla Q_j\\ v_3 \\ v_4 \end{array}\right] (z). \end{aligned}$$

Now, if $\varepsilon _2>0$ is selected generically (and still selected sufficiently small, depending on $\varepsilon _1$), the curve $\gamma +\varepsilon _2 v$ does not lie in $\mathbf {Z}_{\mathbb {C}}(\Psi )$. This means that

$$\begin{aligned} | (\gamma +\varepsilon _2v)\cap \mathbf {Z}_{\mathbb {C}}(\Psi )|\le (\deg \gamma )(\deg \Psi )\lesssim (\deg \gamma )E_i. \end{aligned}$$

(7.20)

On the other hand, Lemma 6.2 implies that at least one intersection point of $(\gamma +\varepsilon _2v)\cap \mathbf {Z}_{\mathbb {C}}(\Psi )$ must occur inside every interval of the form $\tilde{\beta }_{z_0},\ z_0\in \Xi _{\gamma ,{\text {vertPt}}}$. This gives us the bound (7.17). $\square$

Combining the previous lemmas, we obtain the following result:

Proposition 7.1

For each $S\in \mathcal {S}_2$ and index i,  we have the bound

$$\begin{aligned} \sum _{\gamma \in \Gamma _{S,i}^{(3)}}|\Xi _{\gamma ,{\text {badPt}}}| \lesssim D_iE_i. \end{aligned}$$

(7.21)

Proof

First, note that

$$\begin{aligned} \sum _{\gamma \in \Gamma _{S,i}^{(3)}}\deg \gamma \lesssim D_i. \end{aligned}$$

Now we combine the bounds from Corollary 7.12 and Lemmas 7.1, 7.2, 7.3, and 7.4, to obtain (7.21). $\square$

Combining the bounds from this section and using (3.22), we obtain the following bounds, which we will record as a lemma.

Lemma 7.5

We have the bounds

$$\begin{aligned} \sum _i\sum _{S\in \mathcal {S}_2}\sum _{\gamma \in \Gamma _{S,i}^{(3)}}| \Xi _{\gamma ,{\text {badPt}}}|&\lesssim m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}, \end{aligned}$$

(7.22)

$$\begin{aligned} \sum _i\sum _{S\in \mathcal {S}_2}\sum _{z\in (\alpha _{S,i})_{{\text {sing}}}}G_z(\alpha )&\lesssim m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}. \end{aligned}$$

(7.23)

7.3 Cutting the Curves in $\Gamma _{S,i}^{(3)}$

Fix a surface $S\in \mathcal {S}_2$ and an index i. For each $\gamma \in \Gamma _{S,i}^{(3)}$, consider the set

$$\begin{aligned} {\text {Pieces}}_{\gamma }= & {} \{\beta \subset \mathbb {R}^4:\beta \ \text {is a connected component}\; \text {of}\ \gamma (\mathbb {R})\backslash \Xi _{\gamma ,{\text {badPt}}}\}. \end{aligned}$$

(7.24)

Lemma 7.6

If $\beta \in {\text {Pieces}}_{\gamma },$ then $\beta$ is a point or a simple open curve (homeomorphic to (0, 1)).

Proof

Suppose $\beta \in {\text {Pieces}}_{\gamma }$ is not a point. Since $\beta$ does not contain any singular points, $\beta$ is a smooth one-dimensional manifold. Thus $\beta$ is either a simple open curve or is homeomorphic to a circle. However, if $\beta$ is homeomorphic to a circle, then it must contain a point $z\in \beta$ where $T_z\cdot v_1=0$, where $v_1$ is the vector from (7.7). Since we removed all points of this form, no curve $\beta \in {\text {Pieces}}_{\gamma }$ may be homeomorphic to a circle. $\square$

By Corollary 2.1,

$$\begin{aligned} \sum _{S\in \mathcal {S}_2}\sum _{i}\sum _{\gamma \in \Gamma _{S,i}^{(3)}} b_0(\gamma (\mathbb {R})) \lesssim n \sum _i D_i^2\,\lesssim m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}, \end{aligned}$$

(7.25)

where $b_0(\gamma (\mathbb {R}))$ is the number of Euclidean connected components of $\gamma (\mathbb {R})$. We need to bound the size of ${\text {Pieces}}_{\gamma }$. By Lemma 4.7, each time we remove a point $z\in \Xi _{\gamma , {\text {sing}}}$, we increase the number of connected components by at most $2G_z(\gamma )$. Each time we remove a point, we are left with a (new) semialgebraic set (indeed, this is just the previous semialgebraic set with one point removed). Thus we can apply the lemma iteratively, removing one point from $\Xi _{\gamma , {\text {sing}}}$ at a time. By (7.12), removing all the points $\Xi _{\gamma , {\text {sing}}}$ increases the number of connected components in (7.25) by at most $O(m^{k/(2k-1)}n^{(2k-2)/(2k-1)})$.

If we remove a point $z\notin \Xi _{\gamma , {\text {sing}}}$ from a curve $\gamma (\mathbb {R})$, we increase the number of connected components by at most one. Thus if we remove all the points from $\Xi _{\gamma ,{\text {badPt}}}\backslash \Xi _{\gamma , {\text {sing}}}$ as $\gamma$ ranges over all curves in $\bigcup _{S\in \mathcal {S}_2}\bigcup _i \Gamma _{S,i}^{(3)}$, we increase the number of connected components in (7.25) by at most $O(m^{k/(2k-1)}n^{(2k-2)/(2k-1)})$.

We conclude that

$$\begin{aligned} \sum _{S\in \mathcal {S}_2}\sum _j \sum _{\gamma \in \Gamma _{S,j}}|{\text {Pieces}}_{\gamma }| \lesssim m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}. \end{aligned}$$

(7.26)

7.4 Cutting the Surfaces $V_i(\mathbb {R})$

For each index i, let

$$\begin{aligned} {\mathcal {Y}}_i= & {} \big \{A\subset \mathbb {R}^4:A\ \text {is a connected component}\;\text {of}\ V_i(\mathbb {R})\backslash \big ((V_i)_{{\text {sing}}}\cup B_i \cup \zeta _i\big ) \big \}, \end{aligned}$$

(7.27)

where $B_i$ is the set from (7.3), and $\zeta _i$ is the set from (7.1).

Lemma 7.7

The sets $A\in {\mathcal {Y}}_i$ are two-dimensional smooth manifolds.

Proof

By Corollary 4.1, if $z\in V_i(\mathbb {R})\backslash (V_i)_{{\text {sing}}},$ then $\dim _{\mathbb {R},z}(V_i(\mathbb {R}))=2$. Since $z\in (V_i)_{{\text {smooth}}}$, this also implies that z is a smooth point of $V_i(\mathbb {R})$ (in dimension 2). Thus $V_i(\mathbb {R})\backslash (V_i)_{{\text {sing}}}$ is a two-dimensional smooth manifold. Since $B_i(\mathbb {R}) \cup \zeta _i(\mathbb {R})$ are algebraic curves (possibly with zero-dimensional components), $V_i(\mathbb {R})\backslash \big ((V_i)_{{\text {sing}}}\cup B_i \cup \zeta _i\big )$ is also a two-dimensional smooth manifold, and thus so are its connected components. $\square$

Lemma 7.8

Let $A\in {\mathcal {Y}}_i$, and let $\pi :~\mathbb {R}^4\rightarrow \mathbb {R}^2$ be the projection in the direction $\Pi ^\prime$ (i.e., the direction that maps $\Pi ^\prime$ to the vector space 0). Here $\Pi ^\prime$ is the (real) 2-plane from (7.3). Then the restriction of $\pi$ to A is a diffeomorphism, and $\pi (A)$ is an open subset of $\mathbb {R}^2$.

Proof

The main thing to show is that $\pi$ is injective. Suppose there exists two points $x,x^\prime \in A$ such that $\pi (x)=\pi (x^\prime )$. Let $\eta \subset A$ be a smooth curve connecting x and $x^\prime$, and let $\eta (t)$ be the parametrization of this curve by arclength, normalized so that $\eta (0)=x$ and $\eta (1)=x^\prime$. For each $t\in [0,1],$ let $r(t) = {\text {dist}}(\eta (t),x+\Pi ^\prime )^2$, where $x+\Pi ^\prime$ is the affine 2-plane obtained by translating $\Pi$ by the (vector) $x\in \mathbb {R}^4$, and ${\text {dist}}(\eta (t),x+\Pi ^\prime )$ is the (Euclidean) distance between the point $\eta (t)$ and the set $x+\Pi ^\prime$.

r(t) is smooth and $r(0)=r(1)=0$. Thus there exists some $t_0\in (0,1)$ so that $\frac{d}{dt}r(t)|_{t=t_0}=0$. This implies that the curve $\eta$ has tangent vector $w\in \Pi ^\prime$ at the point $r(t_0)$. However, at every point $z\in A$ we have that $T_z(A)\cap \Pi ^\prime = 0$. This is a contradiction. Thus $\pi$ is injective.

We can see that the map $\pi$ is a local diffeomorphism whenever the Jacobian matrix of $\pi$ has full rank. However, this occurs precisely at points $x\in A$ with $T_z(A)\cap \Pi ^\prime = 0$. By the definition of A, this happens at every point.

Since $\pi$ is injective and is everywhere a local diffeomorphism, we conclude that $\pi$ is a diffeomorphism. $\square$

7.5 Combining ${\mathcal {Y}}_i$ and $\hbox {Pieces}_{\gamma }$

Lemma 7.9

If $\gamma \in \Gamma _{S,i}^{(3)}$, and if $\beta \in {\text {Pieces}}_{\gamma },$ then $\beta$ is entirely contained in a single set $A\subset {\mathcal {Y}}_i$, and this set A is unique.

Proof

Recall that every set $\beta \in {\text {Pieces}}_{\gamma }$ is connected (in the Euclidean topology), and each set $\beta$ is contained in some set $V_i$. Thus if $\beta$ meets two sets $A,A^\prime \in {\mathcal {Y}}_i$, then by (7.27), $\beta$ must intersect a point from $(V_i)_{{\text {sing}}}\cup B_i \cup \zeta _i$. However, every point from $\beta \cap (V_i)_{{\text {sing}}}\cup B_i \cup \zeta _i$ also lies in $\Xi _{\gamma ,{\text {badPt}}}$ (where $\gamma$ is the algebraic curve associated to $\beta$). By definition, $\beta$ contains no points from this set. $\square$

Definition 7.1

If $\beta \in {\text {Pieces}}_{\gamma }$, define ${\text {shrink}}(\beta )$ to be the curve obtained by shrinking $\beta$ by a small amount. More precisely, since $\beta$ is a simple open curve, there is a homeomorphism $\eta :~(0,1)\rightarrow \beta$. Define ${\text {shrink}}(\beta )=\iota ((\varepsilon ,1-\varepsilon ))$, where $\varepsilon >0$ is a very small quantity. Specifically, we choose $\varepsilon$ so that the following two properties hold:

• If $p\in \mathcal {P}$ and p is an interior point of $\beta$, then p is an interior point of ${\text {shrink}}(\beta )$.

• If two curves $\beta ,\beta ^\prime$ are disjoint, then ${\text {shrink}}(\beta )$ and ${\text {shrink}}(\beta ^\prime )$ have disjoint (Euclidean) closures.

For each $i=1,\ldots ,\ell$, and for each $A\in {\mathcal {Y}}_i$, define

$$\begin{aligned} {{\mathcal {L}}}_A = \bigcup _{S\in \mathcal {S}_2} \bigcup _{\gamma \in \Gamma _{S,i}^{(3)}} \{{\text {shrink}}(\beta ):~ \beta \in {\text {Pieces}}_{\gamma },\ \text {and}\ \beta \subset A\}, \end{aligned}$$

(7.28)

and define

$$\begin{aligned} \mathcal {P}_A = \mathcal {P}_i \cap A, \end{aligned}$$

(7.29)

where $V_i$ is the (unique) variety such that $V_i(\mathbb {R})$ contains A.

The sets $\{\mathcal {P}_A\}$ are disjoint as A ranges over the sets in ${\mathcal {Y}}_i$ and as $i=1,\ldots ,\ell$. Furthermore, if $(p,S)\in I_7\backslash I_8$, then p lies in some set $\mathcal {P}_A$.

To bound the number of incidences in $I_7\backslash I_8$, we will need to use the crossing lemma. If $A\in {\mathcal {Y}}_i$, define

$$\begin{aligned} {\text {crossings}}(A) = \sum _{\begin{array}{c} \beta ,\beta ^\prime \in {\mathcal {L}}_A\\ \beta \ne \beta ^\prime \end{array}}|\beta \cap \beta ^\prime |. \end{aligned}$$

Lemma 7.10

(Bounding the number of crossings)

$$\begin{aligned} \sum _{i=1}^\ell \sum _{A\in {\mathcal {Y}}_j}{\text {crossings}}(A) \le C_0n^2, \end{aligned}$$

(7.30)

where $C_0$ is the constant from Property (ii) of Definition 1.2.

Proof

First, note that $\sum _{S\ne S^\prime }|S\cap S^\prime |\le C_0n^2$. The entire point is to show that if $z\in S\cap S^\prime$, then there is at most one pair $\beta ,\beta ^\prime$ with $\beta \subset S,\beta ^\prime \subset S^\prime$ so that $z\in \beta \cap \beta ^\prime$. We also need to observe that if both $\beta$ and $\beta ^\prime$ are contained in the same surface S, then $\beta \cap \beta ^\prime =\emptyset$. This is because any point $z\in \beta \cap \beta ^\prime$ is a singular point of $S^*\cap V_i$ for some index i, so this point lies in $\Xi _{\gamma ,{\text {badPt}}}\cap \Xi _{\gamma ^\prime ,{\text {badPt}}}$, where $\gamma ,\gamma ^\prime$ are the (not necessarily distinct) curves associated to $\beta$ and $\beta ^\prime$, respectively. Thus points of this form were removed in a previous step.

For contradiction, suppose there existed some indices $i_1,i_2$, some $A_1\in {\mathcal {Y}}_{i_1},\ A_2\in {\mathcal {Y}}_{i_2}$, and some curve segments $\beta _1,\beta _1^\prime \in \mathcal {L}_{A_1},\beta _2,\beta _2^\prime \in \mathcal {L}_{A_2}$ so that $\beta _1,\beta _2\subset S$, $\beta _1^\prime ,\beta _2^\prime \subset S^\prime$, and $(\beta _1\cap \beta _1^\prime ) \cap (\beta _2\cap \beta _2^\prime )\ne \emptyset$.

First, we must have $i_1\ne i_2$. Indeed, if $i_1=i_2=i$, then $\beta _1\cap \beta _2$ is a singular point of $S^*\cap V_i,$ and by (7.24), neither $\beta _1$ nor $\beta _2$ can contain any points of this type. Next, we can assume that $\beta \not \subset \big (\bigcup _{i}(V_i)_{{\text {sing}}}\big ),$ since all irreducible components of $S^*\cap \bigcup _i V_i$ that were contained in $\big (\bigcup _{i}(V_i)_{{\text {sing}}}\big )$ were already removed. In particular, since $i_1\ne i_2$, we must have that $\beta _1\cap V_{i_2}$ is a discrete set, where $\gamma _1$ is the curve associated to $\beta _1$. But every point in this intersection was already removed when we removed the set $\Xi _{\gamma , {\text {shared}}}$. Thus no points of this type may exist in any curve segment $\beta$. $\square$

Lemma 7.11

Fix an $A\in {\mathcal {Y}}_i$, and let $p_1,\ldots ,p_k\in A$. Then at most $C_0$ curves $\beta \in {\mathcal {L}}_A$ can contain the points $p_1,\ldots ,p_k$, where $C_0$ is the quantity from the statement of Theorem 1.3.

Proof

First, if two curves $\beta ,\beta ^\prime \in {\mathcal {L}}_A$ both contain $p_1$, then $\beta ,\beta ^\prime$ must come from distinct surfaces $S,S^\prime$. Otherwise $p_1$ would lie in the sets $\Xi _{\gamma ,{\text {sing}}}, \Xi _{\gamma ^\prime ,{\text {sing}}}$ (where $\gamma ,\gamma ^\prime$ are the curves associated to $\beta ,\beta ^\prime$, respectively). However, $\beta$ cannot contain any point from $\Xi _{\gamma ,{\text {sing}}}$, and similarly for $\beta ^\prime$.

Since every curve that contains the points $p_1,\ldots ,p_k$ must come from a distinct surface $S\in \mathcal {S}_2$, by Property (iii) from Definition 1.2, at most $C_0$ curves can contain the points $p_1,\ldots ,p_k$. $\square$

We must now develop the tools needed to apply the crossing lemma to the collections of curves and points on the open regions $A\in {\mathcal {Y}}_i$.

8 The Final Interlude: Some Graph Theory

In [26], Székely provided a simple proof of the Szemerédi–Trotter theorem using the crossing lemma from topological graph theory. In brief, the crossing lemma states that a graph drawing either contains very few edges, or it must have many crossings (points where two edges cross). Székely showed how a point-line arrangement could be converted into a graph drawing, where the number of point-line incidences was bounded by the number of edges. On the other hand, since every two lines cross at most once, Székely was able to bound the number of crossings in the graph drawing. This led to a bound on the number of incidences.

We wish to do something similar, but in our case we do not have a single graph but many, and the crossings are spread out amongst all of the graphs. We need to obtain an incidence bound across all of these graphs. This will be done in Lemma 8.2.

8.1 Graphs and Graph Drawings

Definition 8.1

We define a generalized undirected graph drawing to be a triple $H=(\mathcal {P},\Gamma ,E)$. Here $\mathcal {P}\subset \mathbb {R}^2$ is a finite collection of points (also called vertices); $\Gamma$ is a finite set of bounded simple open curves, with $|\gamma \cap \gamma ^\prime |$ finite for every pair of distinct curves $\gamma ,\gamma ^\prime$; and E is a set of pairs of the form $(\{p,q\},\gamma )$, where p, q are distinct points in $\mathcal {P}$ and $\gamma \in \Gamma$. If p, q are vertices of a graph drawing H, we define

$$\begin{aligned} \mathrm {edgemult}(p,q)=|\{\gamma \in \Gamma :~ (\{p,q\},\gamma )\in E\}|. \end{aligned}$$

Informally, this is the number of edges between p and q.

Definition 8.2

We say that the undirected drawing H is proper if the following properties hold:

• No point of $\mathcal {P}$ lies in the relative interior of any curve in $\Gamma$.

• $(\{p,q\},\gamma )\in E$ if and only if the endpoints of $\gamma$ are the points p and q.

Thus a proper undirected graph drawing is a special type of generalized undirected graph drawing.

Definition 8.3

Let $G=(V^\prime ,E^\prime )$ be an undirected multigraph. Thus $V^\prime$ is a set of vertices and $E^\prime$ is a multiset of pairs of distinct vertices from $V^\prime$. Let $H=(\mathcal {P},\Gamma ,E)$ be a (generalized) undirected graph drawing. We say that G is associated to H (or H is associated to G) if there is a bijection from $\mathcal {P}$ to $V^\prime$ so that for every pair of vertices $p,q\in \mathcal {P}$, $\mathrm {edgemult}(p,q)$ is equal to the number of edges between p and q in G. Given a graph drawing H, there is always a unique multigraph G associated to H.

Definition 8.4

We define a generalized directed graph drawing to be a triple $H=(\mathcal {P},\Gamma , E).$ Here $\mathcal {P}\subset \mathbb {R}^2$ is a finite collection of points (also called vertices); $\Gamma$ is a finite set of bounded simple open curves, with $|\gamma \cap \gamma ^\prime |$ finite for every pair of distinct curves $\gamma ,\gamma ^\prime$; and E is a set of pairs of the form $(p,q,\gamma )$, where p, q are distinct points in $\mathcal {P}$ and $\gamma \in \Gamma$. If a triple $(p,q,\gamma )$ is in E, we say that $p\mathop {\rightarrow }\limits ^{\gamma } q$, i.e., there is a directed edge from p to q along $\gamma$ (note that p and q need not be the endpoints of $\gamma$). The collection of all directed edges from p to q is denoted by $p\rightarrow q$, and the number of edges is denoted by $\mathrm {edgemult}(p\rightarrow q)$.

Definition 8.5

We say that a directed graph drawing is proper if the following properties hold:

• No point of $\mathcal {P}$ lies in the relative interior of any curve in $\Gamma$.

• If $p\mathop {\rightarrow }\limits ^{\gamma } q$, then p and q are the endpoints of $\gamma$. Conversely, if p, q are the endpoints of $\gamma$, then precisely one of $p\mathop {\rightarrow }\limits ^{\gamma } q$ or $q\mathop {\rightarrow }\limits ^{\gamma } p$ must hold.

The intuition is that generalized graph drawings are allowed to have multiple edges stacked on top of each other, while proper graph drawings do not permit this.

8.2 Crossings and Graph Drawings

Definition 8.6

If H is a generalized (directed or undirected) graph drawing, we define the number of crossings in H,

$$\begin{aligned} \mathcal {C}(H)=\sum _{\begin{array}{c} \gamma ,\gamma ^\prime \in \Gamma \\ \gamma \ne \gamma ^\prime \end{array}}|\gamma \cap \gamma ^\prime |. \end{aligned}$$

Since the intersection of any two curves is a discrete set, $\mathcal {C}(H)$ is finite.

Let G be an undirected multigraph. We define $\mathcal {V}(G)$ to be the number of vertices of G and $\mathcal {E}(G)$ to be the number of edges.

Theorem 8.1

(Ajtai et al. [1]; Leighton [16]; Székely [26]) Let H be a proper undirected graph drawing and let G be the multigraph associated to H. Suppose G has maximum edge multiplicity M. If $\mathcal {E}(G)\ge 5\mathcal {V}(G)$, then

$$\begin{aligned} \mathcal {C}(H)\ge \frac{\mathcal {E}(G)^3}{100M \mathcal {V}(G)^2}. \end{aligned}$$

(8.1)

8.3 Bounding Incidences by Crossings

Theorem 8.2

Let $U\subset \mathbb {R}^2$ be open. Let $\mathcal {P}\subset \mathbb {R}^2$ be a set of points, and let $\Gamma \subset \mathbb {R}^2$ be a set of simple open curves with k degrees of freedom (relative to $\mathcal {P}$), i.e., for any k points of $\mathcal {P}$, there are at most $C_0$ curves from $\Gamma$ that contain all k points, and any two curves intersect in at most $C_0$ points. Then

$$\begin{aligned} \mathcal {I}(\mathcal {P},\Gamma ) \lesssim |\mathcal {P}|^{\tfrac{k}{2k-1}} \big (\sum _{\begin{array}{c} \gamma ,\gamma ^\prime \in \Gamma \\ \gamma \ne \gamma ^\prime \end{array}} |\gamma \cap \gamma ^\prime | \big )^{\tfrac{k-1}{2k-1}} + |\mathcal {P}| + |\Gamma |. \end{aligned}$$

(8.2)

The implicit constant depends only on k and $C_0$.

The proof of Theorem 8.2 is much easier for the $k=2$ case (it is a variant of Székely’s proof in [26]), so we will provide a proof of this case first. The proof for general k also works for $k=2$.

Proof of Lemma 8.2, k=2 case

Replace each curve $\gamma \in \Gamma$ with a slightly shrunk curve $\gamma ^\prime$ (in the sense of Definition 7.1), so that $\partial (\gamma ^\prime )$ does not meet any point from $\mathcal {P}$ nor any curve from $\Gamma$. If $\Gamma ^\prime$ denotes the set of shrunk curves, then $|\mathcal {I}(\mathcal {P},\Gamma ^\prime )|\ge |\mathcal {I}(\mathcal {P},\Gamma )|-2|\Gamma |.$ Delete from $\Gamma ^\prime$ those curves that are incident to fewer than 2 points from $\mathcal {P}$, and denote the resulting set of curves $\Gamma ^{\prime \prime }$. Then $|\mathcal {I}(\mathcal {P},\Gamma ^{\prime \prime })|\ge |\mathcal {I}(\mathcal {P},\Gamma )|-4|\Gamma |.$

Let G be the undirected multigraph whose vertex set is $\mathcal {P}$, and where two vertices are connected by an edge if the two corresponding points are joined by a curve from $\Gamma ^{\prime \prime }$, and the two vertices are consecutive on this curve. Let H be the (proper, undirected) drawing of G given by the points $\mathcal {P}\subset \mathbb {R}^2$ and the curve segments joining consecutive edges from curves $\gamma \in \Gamma ^{\prime \prime }$.

The multigraph G need not be a graph, since two vertices can be connected by several edges. However, the maximum edge multiplicity of G is bounded by the constant $C_0$ from the statement of Lemma 8.2. Furthermore, $\mathcal {E}(G)\ge \frac{1}{2}|\mathcal {I}(\mathcal {P},\Gamma ^{\prime \prime })|$, so by Theorem 8.1,

$$\begin{aligned} |\mathcal {I}(\mathcal {P},\Gamma )|\lesssim & {} |\mathcal {P}|^{2/3}{\mathcal {C}}(H)^{1/3}+|\mathcal {P}|+ 4|\Gamma |\\\lesssim & {} |\mathcal {P}|^{2/3} \big (\sum _{\begin{array}{c} \gamma ,\gamma ^\prime \in \Gamma \\ \gamma \ne \gamma ^\prime \end{array}} |\gamma \cap \gamma ^\prime | \big )^{1/3} + |\mathcal {P}| + |\Gamma |. \end{aligned}$$

$\square$

We will now prove Lemma 8.2 for general k. The proof is very similar to Pach and Sharir’s proof in [20] of a Szemerédi–Trotter type theorem for curves with k degrees of freedom. However, the main term in Pach and Sharir’s bound is $|\mathcal {P}|^{k/(2k-1)}|\Gamma |^{(2k-2)/(2k-1)}$ rather than

$$\begin{aligned} |\mathcal {P}|^{\tfrac{k}{2k-1}} \big (\sum |\gamma \cap \gamma ^\prime |\big )^{\tfrac{k-1}{2k-1}}, \end{aligned}$$

and the former could potentially be much larger. This fact forces us to modify Pach and Sharir’s proof.

Proof of Lemma 8.2, general case

First, either

$$\begin{aligned} \mathcal {I}(\mathcal {P},\Gamma )\le 100k |\Gamma | \end{aligned}$$

(8.3)

or

$$\begin{aligned} \mathcal {I}(\mathcal {P},\Gamma )>100k |\Gamma |. \end{aligned}$$

(8.4)

If (8.3) holds, then the theorem follows immediately. Thus for the remainder of the proof we will assume that (8.4) holds

Let $\Gamma ^\prime \subset \Gamma$ be the set of curves that are incident to $\ge 2k$ points from $\mathcal {P}$. By (8.4),

$$\begin{aligned} \mathcal {I}(\mathcal {P},\Gamma ^\prime )>\tfrac{1}{2}\mathcal {I}(\mathcal {P},\Gamma ), \end{aligned}$$

so it suffices to consider curves in $\Gamma ^\prime$. If $p\in \mathcal {P},$ let $d_p=|\{\gamma \in \Gamma ^\prime :~ p\in \gamma \}|.$ We will call this the degree of p. Let

$$\begin{aligned} \mathcal {P}^\prime =\Big \{p\in \mathcal {P}:~ d_p\ge \frac{{\mathcal {I}}(\mathcal {P},\Gamma ^\prime )}{2|\mathcal {P}|}\Big \}. \end{aligned}$$

Then

$$\begin{aligned} \mathcal {I}(\mathcal {P}^\prime ,\Gamma ^\prime )\ge \tfrac{1}{2} \mathcal {I}(\mathcal {P},\Gamma ^\prime )\ge \tfrac{1}{4}\mathcal {I}(\mathcal {P},\Gamma ). \end{aligned}$$

(8.5)

For $p\in \mathcal {P}^\prime ,$ $\gamma \in \Gamma ^\prime ,$ and $p\in \gamma$, let

$$\begin{aligned} S_{p,\gamma }=\{q\in \mathcal {P}^\prime :~ q\in \gamma ,\ q\ne p,\ d_q\ge d_p\}. \end{aligned}$$

Let $H=(\mathcal {P}^\prime ,\Gamma ^\prime ,E)$ be a generalized directed graph drawing, where the triple $(p,q,\gamma )$ is in E if the following conditions hold:

• $p\in \mathcal {P}^\prime ,\gamma \in \Gamma ^\prime ,\ p\in \gamma ,\ q\in S_{p,\gamma }.$

• $|S_{p,\gamma }|\ge k.$

• q is one of the k closest points to p of the point set $S_{p,\gamma }$ (i.e., the curve segment of $\gamma$ connecting p and q passes through at most $k-1$ points from $S_{p,\gamma }$).

Note that H might not be a proper directed graph drawing since several edges may be drawn over the same curve segment.

Lemma 8.1

$$\begin{aligned} \mathcal {E}(H)\ge \mathcal {I}(\mathcal {P}^\prime ,\Gamma ^\prime )-k|\Gamma ^\prime |. \end{aligned}$$

(8.6)

Proof

Let $p\in \mathcal {P}^\prime ,\gamma \in \Gamma ^\prime$ with $p\in \gamma$. Then either there is an edge $p\overset{\gamma }{\rightarrow } q$ for some $q\in S_{p,\gamma }$, or $p\in X_\gamma ,$ where $X_\gamma$ is the set of the k highest degree points on $\gamma$. The lemma now follows from the observation that $|X_\gamma |\le k$. $\square$

Lemma 8.1 and (8.4) imply that

$$\begin{aligned} \mathcal {E}(H)\ge \tfrac{1}{2} \mathcal {I}(\mathcal {P}^\prime ,\Gamma ^\prime ) \ge \tfrac{1}{8}\mathcal {I}(\mathcal {P},\Gamma ). \end{aligned}$$

(8.7)

Note that a given segment of a curve $\gamma \in \Gamma$ may be part of several distinct edges, i.e., our graph drawing H may not be proper (in the sense of Definition 8.5). However, the following lemma controls the extent to which this occurs.

Lemma 8.2

Let $\gamma \in \Gamma ^\prime ,$ and let x be a point on $\gamma$. Then the number of pairs $(p,q)\in (\mathcal {P}^\prime )^2$ such that the arc $p\mathop {\rightarrow }\limits ^{\gamma } q$ contains x is at most $10k^2$.

Proof

Since $\gamma$ is a simple open curve, $\gamma \backslash x$ consists of two connected pieces, which we will call the right and left pieces. This establishes a global notion of right and left on the curve $\gamma$. We will now prove the lemma. Suppose there were more than $10k^2$ pairs $(p,q)\in (\mathcal {P}^\prime )^2$ with x contained in the arc $p\mathop {\rightarrow }\limits ^{\gamma } q$. Then without loss of generality, there are more than $5k^2$ arcs of the form $p \overset{\gamma }{\rightarrow }q$ where p is right of x and q is left of x. Since each point $p\in \mathcal {P}^\prime \cap \gamma$ has at most k curves of the form $p \overset{\gamma }{\rightarrow }q$ that exit it, there exists a set of $\ge 5k$ distinct points to the right of x, so that each of these points contains at least one arc of the form $p \overset{\gamma }{\rightarrow }q$ that contains x. Denote this set of points by $\mathcal {P}_1$. Let $\mathcal {P}_2\subset \mathcal {P}_1$ be the 2k right-most points from this collection, and let $p^*\in \mathcal {P}_2$ be the point with lowest degree. Then the arc from $p^*$ to x passes over at least 3k points of $\mathcal {P}^\prime$, but there are at least $2k-1>k$ points of $\mathcal {P}^\prime$ on the arc $\gamma$ with distance $\le 2k$. Each of these points lies in $S_{p^*,\gamma }$. This is a contradiction, since by definition $p^*$ is connected to the k closest points on $\gamma$ with degree $\ge d_{p^*}$. $\square$

Let $H^\prime$ be the generalized directed graph drawing obtained by starting with H and deleting all edges of the form $p\overset{\gamma }{\rightarrow }q$ where $p\in X_\gamma$ (recall from above that $X_\gamma$ is the set of k points on $\gamma$ that have the highest multiplicity). Then since every curve in $\Gamma ^\prime$ is incident to at least 2k edges, ${\mathcal {E}}(H^\prime )\ge \frac{1}{2}{\mathcal {E}}(H)\ge \frac{1}{16}\mathcal {I}(\mathcal {P},\Gamma )$.

Now, let $H^{\prime \prime }$ be the generalized directed graph drawing obtained by starting with $H^\prime$ and deleting all edges of the form $p\overset{\gamma }{\rightarrow }q$ whenever

$$\begin{aligned} \mathrm {edgemult}(p\rightarrow q)>Ad_p^{\tfrac{k-2}{k-1}}. \end{aligned}$$

(8.8)

Here A is a large constant (depending only on k) to be determined later. We will call $H^{\prime \prime }$ the pruned version of $H^\prime$. If an edge $p\overset{\gamma }{\rightarrow }q$ is present in $H^\prime$ but not in $H^{\prime \prime }$, we will say the edge $p\overset{\gamma }{\rightarrow }q$ has been pruned.

Lemma 8.3

(Pach and Sharir)

$$\begin{aligned} \mathcal {E}(H^{\prime \prime })\ge \frac{1}{2k}\mathcal {E}(H^\prime )\ge \frac{1}{32k}\mathcal {I}(\mathcal {P},\Gamma ). \end{aligned}$$

(8.9)

Proof

The proof of this lemma is nearly identical to the arguments of Pach and Sharir in [20, p. 124]. For the reader’s convenience, we reproduce it here. For $p,q\in \mathcal {P}^\prime ,$ let $E_p(q)$ be the set of all edges of $H^\prime$ that connect p to q, i.e., all edges of the form $p\overset{\gamma }{\rightarrow }q,$ for $\gamma \in \Gamma ^\prime$. By the definition of H, we have $\sum _{q\in \mathcal {P}^\prime }|E_p(q)|\le 2(k-1)d_p$.

Let $E_{p,q}$ be the set of edges of the form $p\overset{\gamma }{\rightarrow }r$, where $\gamma$ is a curve for which $p\overset{\gamma }{\rightarrow }q$ is an edge of $H^\prime$.

Let

$$\begin{aligned} R_p = \Big \{q \in \mathcal {P}^\prime :~ |E_p(q)|>Ad_p^{\tfrac{k-2}{k-1}}\Big \}, \end{aligned}$$

so

$$\begin{aligned} |R_p|\le 2kd_p\big (Ad_p^{\tfrac{k-2}{k-1}}\big )^{-1}\le 2kA^{-1}d_p^{\tfrac{1}{k-1}}. \end{aligned}$$

If $R_p=\emptyset ,$ there is nothing to prove. Otherwise, consider in turn each vertex $q\in R_p$ and each curve $\gamma$ that contains an edge $p\overset{\gamma }{\rightarrow }q$ from $E_p(q).$ By the definition of $H^{\prime }$, $\gamma$ must contain at least $k-1$ edges that lie in the set $E_{p,q}.$ We want to charge $p\overset{\gamma }{\rightarrow }q$ to one of these edges; we can do this as long as one of these edges is still present in the set $H^{\prime \prime }$ (i.e., we can do this as long as one of these edges has not been pruned).

We say that $p\overset{\gamma }{\rightarrow }q$ is good if there exists at least one edge from $E_{p,q}$ in the generalized directed graph drawing $H^{\prime \prime }$ (i.e., if at least one edge from $E_{p,q}$ survives the pruning process). If $p\overset{\gamma }{\rightarrow }q$ is not good, we say it is bad.

If $p\overset{\gamma }{\rightarrow }q$ is bad, then the curve $\gamma$ passes through p and through at least $k-1$ distinct points of $R_p$, and in this case $\gamma$ contains at most $2(k-1)$ bad edges. But, there are $\le C_0$ curves passing through p and any fixed set of $k-1$ points of $R_p$. Thus the number of bad edges is at most

$$\begin{aligned} 2(k-1)C_0\left( {\begin{array}{c}|R_p|\\ k-1\end{array}}\right)< & {} \frac{2C_0(k-1)|R_p|^{k-1}}{(k-1)!} \nonumber \\< & {} \frac{2C_0}{(k-1)!}\Bigg (\frac{2k}{A}\Bigg )^{k-1}d_p. \end{aligned}$$

(8.10)

If we select A sufficiently large, then

$$\begin{aligned} \frac{2C_0}{(k-1)!}\Bigg (\frac{2k}{A}\Bigg )^{k-1}d_p < \frac{1}{2}(k-1)d_p, \end{aligned}$$

and thus more than half of the edges in $E_p$ are good, and each of them can charge one of the surviving edges in $H^{\prime \prime }$. This implies that at least $\frac{1}{2k}d_p$ of the edges exiting p survive in $H^{\prime \prime }$. Since this holds true for all edges in $H^{\prime \prime },$ Lemma 8.3 follows. $\square$

For each triple $(p,q,\gamma )\in E$ in the pruned graph drawing $H^{\prime \prime }$, let $\gamma _{p,q}\subset \gamma$ be the simple open curve connecting p to q. Define $\Gamma _0=\{\gamma _{p,q}:~ (p,q,\gamma )\in E\}$. Let $\Gamma _1$ be obtained by perturbing each curve in $\gamma _0$ slightly so that the endpoints remain unchanged, but every two curves in $\Gamma _0$ intersect in a finite set. Let $H^{\prime \prime \prime }=(\mathcal {P}^\prime , \Gamma _1,E_0)$ be the directed graph drawing where $(p,q,\gamma )\in E_0$ if and only if p and q are the endpoints of $\gamma$. Then $H^{\prime \prime \prime }$ is a proper directed graph drawing (in the sense of Definition 8.5). For every pair of distinct points $p,q\in \mathcal {P}^\prime$, $\mathrm {edgemult}(p\rightarrow q)$ in $H^{\prime \prime }$ is equal to $\mathrm {edgemult}(p\rightarrow q)$ in $H^{\prime \prime \prime }$. Furthermore, by Lemma 8.2,

$$\begin{aligned} \mathcal {C}(H^{\prime \prime \prime })<100k^4\mathcal {C}(H^{\prime \prime }). \end{aligned}$$

We will now perform a diadic decomposition of vertices in the graph $H^{\prime \prime \prime }.$ For $j = 0,\ldots ,\lceil \log _2 m\rceil ,$ let $H_j$ be the proper undirected graph drawing with vertex set

$$\begin{aligned} \big \{p \in \mathcal {P}^\prime :~ d_p\ge 2^j\frac{{\mathcal {I}}(\mathcal {P},\Gamma )}{2m}\big \}. \end{aligned}$$

If $p\in \mathcal {P}^\prime$ and

$$\begin{aligned} 2^j\frac{{\mathcal {I}}(\mathcal {P},\Gamma )}{2m}\le d_p < 2^{j+1}\frac{{\mathcal {I}}(\mathcal {P},\Gamma )}{2m}, \end{aligned}$$

then all of the multi-edges $p\rightarrow q$ from $H^{\prime \prime \prime }$ are added to $H_j,$ but we add them as undirected edges. These are the only edges of $H_j$. Let $m_j$ be the number of vertices of $H_j$. Since

$$\begin{aligned} 2^j \frac{{\mathcal {I}}(\mathcal {P},\Gamma )}{2m} m_j \le {\mathcal {I}}(\mathcal {P},\Gamma ), \end{aligned}$$

we have

$$\begin{aligned} m_j \le 2^{-j+1}m. \end{aligned}$$

(8.11)

We have the following:

• Each multi-edge of $H_j$ has edge multiplicity $\le \Big (2^{j+1}\frac{{\mathcal {I}} (\mathcal {P},\Gamma )}{2m}\Big )^\frac{k-2}{k-1}$.

• Each multi-edge $p\rightarrow q$ in $H^{\prime \prime \prime }$ appears as a multi-edge in some $H_j$, so

  $$\begin{aligned} \mathcal {E}(H^{\prime \prime \prime })\le \sum _j \mathcal {E}(H_j). \end{aligned}$$

  (8.12)

• $\mathcal {C}(H_j)\le \mathcal {C}(H^{\prime \prime \prime })\le 100k^4\mathcal {C}(H).$

Let $G_j$ be the undirected multigraph associated to $H_j$. Let

$$\begin{aligned} J_1 = \bigg \{j\in \{0,\ldots ,\lceil \log _2 m\rceil \}:~\ \mathcal {E}(G_j)\le 100 m_j \Bigg (2^{j+1} \frac{{\mathcal {I}} (\mathcal {P},\Gamma )}{2m}\Bigg )^{\tfrac{k-2}{k-1}}\bigg \}, \end{aligned}$$

and let $J_2=\{0,\ldots ,\lceil \log _2 m\rceil \}\backslash J_1$. By (8.9) and (8.12), either

$$\begin{aligned} \mathcal {I}(\mathcal {P}^\prime ,\Gamma )\le \frac{1}{64k}\sum _{j\in J_1}\mathcal {E}(G_j) \end{aligned}$$

(8.13)

or

$$\begin{aligned} \mathcal {I}(\mathcal {P}^\prime ,\Gamma )\le \frac{1}{64k}\sum _{j\in J_2}\mathcal {E}(G_j). \end{aligned}$$

(8.14)

If (8.13) holds, then

$$\begin{aligned} \sum _{j\in J_1}\mathcal {E}(G_j)\lesssim & {} m^{\tfrac{1}{k-1}}\mathcal {I}(\mathcal {P},\Gamma )^{\tfrac{k-2}{k-1}} \sum _{j=0}^{\lceil \log _2 m\rceil } 2^{-j/k} \nonumber \\\lesssim & {} m^{\tfrac{1}{k-1}}\mathcal {I}(\mathcal {P},\Gamma )^{\tfrac{k-2}{k-1}} \end{aligned}$$

(recall that the $\lesssim$ notation hides an implicit constant that is allowed to depend on k). Thus if (8.13) holds, then

$$\begin{aligned} |\mathcal {I}(\mathcal {P},\Gamma )| \lesssim |\mathcal {P}|, \end{aligned}$$

(8.15)

which proves Lemma 8.2.

Alternately, if (8.14) holds, then we can apply the crossing lemma to each $j\in J_2$ to conclude

$$\begin{aligned} \mathcal {C}(H_j)\gtrsim \frac{\mathcal {E}(G_j)^3}{m_j^2 \big (2^{j+1}\frac{\mathcal {I}(\mathcal {P},\Gamma )}{2m}\big )^{\tfrac{k-2}{k-1}}}, \end{aligned}$$

(8.16)

and thus

$$\begin{aligned} \mathcal {E}(G_j)\lesssim & {} (\mathcal {C}(H_j))^{1/3}m^{\tfrac{k}{3(k-1)}} \mathcal {I}(\mathcal {P},\Gamma )^{\tfrac{k-2}{3(k-1)}}2^{\tfrac{-jk}{3(k-1)}} \nonumber \\\lesssim & {} (\mathcal {C}(H_j))^{1/3}m^{\tfrac{k}{3(k-1)}} \mathcal {I}(\mathcal {P},\Gamma )^{\tfrac{k-2}{3(k-1)}}, \end{aligned}$$

(8.17)

where the implicit constant does not depend on j (i.e., it is an absolute constant). Thus we have

$$\begin{aligned} \mathcal {I}(\mathcal {P},\Gamma )\lesssim & {} \sum _{j\in J_2}\mathcal {E}(G_j) \nonumber \\\lesssim & {} \sum _{j\in J_2} (\mathcal {C}(H_j))^{1/3}m^{\tfrac{k}{3(k-1)}} \mathcal {I}(\mathcal {P},\Gamma )^{\tfrac{k-2}{3(k-1)}} \nonumber \\\lesssim & {} (\mathcal {C}(H))^{1/3}m^{\tfrac{k}{3(k-1)}} \mathcal {I}(\mathcal {P},\Gamma )^{\tfrac{k-2}{3(k-1)}}. \end{aligned}$$

(8.18)

By Lemma 8.2, we have

$$\begin{aligned} \mathcal {C}(H)\lesssim \sum _{\begin{array}{c} \gamma ,\gamma ^\prime \in \Gamma \\ \gamma \ne \gamma ^\prime \end{array}} |\gamma \cap \gamma ^\prime |. \end{aligned}$$

Thus if (8.14) holds, then

$$\begin{aligned} |\mathcal {I}(\mathcal {P},\Gamma )| \lesssim |\mathcal {P}|^{\tfrac{k}{2k-1}} \Big (\sum _{\begin{array}{c} \gamma ,\gamma ^\prime \in \Gamma \\ \gamma \ne \gamma ^\prime \end{array}} |\gamma \cap \gamma ^\prime | \Big )^{\tfrac{k-1}{2k-1}}. \end{aligned}$$

(8.19)

Combining the bounds (8.3), (8.15), and (8.19), we conclude

$$\begin{aligned} \mathcal {I}(\mathcal {P},\Gamma )\lesssim |\mathcal {P}|^{\tfrac{k}{2k-1}} \Big (\sum _{\begin{array}{c} \gamma ,\gamma ^\prime \in \Gamma \\ \gamma \ne \gamma ^\prime \end{array}} |\gamma \cap \gamma ^\prime | \Big )^{\tfrac{k-1}{2k-1}} + |\mathcal {P}| + |\Gamma |. \end{aligned}$$

$\square$

9 Bounding $I_6$

To bound $|I_6\backslash I_7|$, we will apply Theorem 8.2 to each collection $(A,\mathcal {P}_A,\mathcal {L}_A)$ for each $A\in \bigcup _i {\mathcal {Y}}_i$. We conclude that

$$\begin{aligned} |I_6\backslash I_7|\lesssim & {} \sum _{i=1}^\ell \sum _{A\in {\mathcal {Y}}_i} |\{(p,\beta )\in \mathcal {P}_A\cap \mathcal {L}_A:~ p\in \beta \}| \nonumber \\\lesssim & {} \sum _{i=1}^\ell \sum _{A\in {\mathcal {Y}}_i} \big (|\mathcal {P}_A|^{\tfrac{k}{2k-1}}{\text {crossings}} (A)^{\tfrac{k-1}{2k-1}}+|\mathcal {P}_A|+|\mathcal {L}_A|\big ) \nonumber \\\lesssim & {} \big (\sum _{i=1}^\ell \sum _{A\in {\mathcal {Y}}_i} |\mathcal {P}_A|\big )^{\tfrac{k}{2k-1}}\big (\sum _{i=1}^\ell \sum _{A\in {\mathcal {Y}}_i} {\text {crossings}} (A)\big )^{\tfrac{k-1}{2k-1}}+\,|\mathcal {P}|+\sum _{i=1}^\ell \sum _{A\in {\mathcal {Y}}_i} |\mathcal {L}_A| \nonumber \\\lesssim & {} m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}+m, \end{aligned}$$

(9.1)

where in the second last line we used Lemma 7.10. Combining (7.2), (9.1), and the bounds on $I_1,\ldots ,I_6$ from Sects. 5.2–5.4, we obtain the bound

$$\begin{aligned} \sum _{i\in {\mathcal {A}}_1} |I\cap {\mathcal {I}}(\mathcal {P}_i \cap W_i,\mathcal {S}_2)|\lesssim m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}+m+n, \end{aligned}$$

(9.2)

where the implicit constant depends only on $C_0$ and k (indeed, each implicit constant only depended on previously defined implicit constants, and ultimately these only depended on $C_0$ and k). This is precisely the second term in (3.26), which we sought to control. Altogether, we conclude that

$$\begin{aligned} |I\cap \mathcal {I}(\mathcal {P}\cap Z,\mathcal {S}_2)| \le \frac{C_1}{10} \big (m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}+m+n\big ), \end{aligned}$$

(9.3)

provided we choose $C_1$ sufficiently large depending only on the constants $C_0$ and k from the statement of Theorem 1.3. This (at last!) concludes the proof of Theorem 1.3.

10 Open Problems and Future Work

There are a number of natural extensions and generalizations of Theorem 1.3.

10.1 Removing the Restriction on m and n

The requirement that $m\le n^{(2k+2)/3k}$ is likely not necessary; we pose the following conjecture.

Conjecture 10.1

Theorem 1.3 holds for all values of m and n.

If $m\ge n^2$, then Theorem 1.3 follows from the Kővari–Sós–Turán theorem (Theorem 3.1). Thus the critical range is $n^{(2k+2)/3k} < m < n^2$. The author believes that using the same techniques as in Sect. 3.1 of [22], it would be possible to obtain the following partial progress toward Conjecture 10.1.

Conjecture 10.2

Let $\mathcal {P}\subset \mathbb {R}^4$ be a collection of m points. Let $\mathcal {S}$ be a $C_0$-good collection of pseudoflats with k degrees of freedom, with $|\mathcal {S}|=n$, and suppose $m\le n^{2-\varepsilon }$. Let $I\subset \mathcal {I}(\mathcal {P},\mathcal {S})$ be a good collection of incidences. Then

$$\begin{aligned} |I| \le C_1\big (m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}+m+n\big ). \end{aligned}$$

(10.1)

The constant $C_1$ depends only on $C_0,k$, and $\varepsilon$.

Roughly speaking, Conjecture 10.2 should be provable as follows. In proving Theorem 1.3, we construct partitioning polynomials $\{P_i\}$, $\{Q_i\}$ of degrees $D_i,\ E_i$, respectively. As discussed in Remark 5.1, we need the bound

$$\begin{aligned} \sum _i (D_iE_i)^4 \lesssim m^{\tfrac{k}{2k-1}}n^{\tfrac{2k-2}{2k-1}}. \end{aligned}$$

(10.2)

Here, the numbers $\{D_i\}$ are essentially arbitrary positive integers satisfying $\sum D_i=D$ (D is specified in (3.5)), and $E_i$ is given by (3.20). If $m\le n^{(2k+2)/3k}$, then (10.2) holds, while if $m> n^{(2k+2)/3k}$, then (10.2) may fail.

However, one can get around this problem by using partitioning polynomials of lower degree (i.e., making $D_i$ and $E_i$ smaller), so (10.2) holds even when $m> n^{(2k+2)/3k}$. Let $\alpha =\log m/\log n$. The idea is to prove the theorem by induction on $\alpha$, starting with the base case $\alpha \le \tfrac{2k+2}{3k},$ which has already been handled by Theorem 1.3.

Now, suppose the theorem has already been proved for all $\alpha <\alpha _0$, and let $\mathcal {P},\mathcal {S}$ be collections of points and surfaces with $|\mathcal {P}|=m,\ |\mathcal {S}|=n$. Suppose that $\log m/\log n\le \alpha _0+f(\alpha _0).$ The function f(t) will be determined later; the key property is that f(t) is continuous on $[\frac{2k+2}{3k},2]$ and $f(t)>0$ for $x<2$.

Let $D^\prime$ be a small power of D ($D^\prime =D^{1/10}$ say). Instead of performing a partition using a polynomial of degree D, use a polynomial of degree $D^\prime$. A certain number of points and surfaces will enter each of the cells. There will be too many points and surfaces to apply the Kővari-Sós-Turán theorem directly. Luckily, however, if $m^\prime$ points and $n^\prime$ surfaces enter the cell, then $\log m^\prime / \log n^\prime \le \alpha _0$ (provided the function f(t) is chosen appropriately) so the induction hypothesis can be applied to bound the number of incidences inside each cell.

We must now bound the number of incidences occurring on the boundary of the partition. Define $E_i^\prime$ to be a small power of $E_i$. The incidences inside the second-level cells can again be bounded using the induction hypothesis.

It remains to bound the incidences occurring on the boundary of the second partition. Here we exploit the fact that $D_i^\prime$ and $E_i^\prime$ are much smaller than $D_i$ and $E_i$. In particular, the analogue of (10.2) will hold with $D_i^\prime$ and $E_i^\prime$ in place of $D_i$ and $E_i$. This allows us to close the induction.

Analyzing the induction, we see that for any $\varepsilon >0$, if $\mathcal {P},\mathcal {S}$ are collections of points and surfaces with $|\mathcal {P}|=m,\ |\mathcal {S}|=n$, and if $m\le n^{2-\varepsilon },$ then we only apply the induction step $O_\varepsilon (1)$ times before we are reduced to the base case $\alpha \le \tfrac{2k+2}{3}$. Each time we apply the induction step, we obtain an additional multiplicative constant in our bound. However, since we only perform this induction $O_\varepsilon (1)$ times, the total contribution is still (a multiplicative) constant.

However, proving the above result would lengthen the exposition significantly and does not introduce any new ideas, so we prefer to state it as a conjecture rather than include the argument in this manuscript.

10.2 Higher Dimensions

Extending Theorem 1.3 to dimensions higher than 4 appears to require some significant new ideas. In particular, if one tried to follow a similar proof strategy to prove an incidence theorem for 3-flats in $\mathbb {R}^6$, one would need some sort of analogue of the crossing lemma for two-dimensional surfaces in $\mathbb {R}^4$. The author is not aware of any statement of this type. It seems reasonable to conjecture that any proof of a Szeméredi–Trotter type theorem for 3-flats in $\mathbb {R}^6$ will require a different proof strategy.