Bisector Energy and Few Distinct Distances

Abstract

We define the bisector energy $\mathcal E(\mathcal P)$ of a set $\mathcal P$ in $\mathbb R^2$ to be the number of quadruples $(a,b,c,d)\in \mathcal P^4$ such that a, b determine the same perpendicular bisector as c, d. Equivalently, $\mathcal E(\mathcal P)$ is the number of isosceles trapezoids determined by $\mathcal P$. We prove that for any $\varepsilon >0$, if an n-point set $\mathcal P$ has no M(n) points on a line or circle, then we have

$$\begin{aligned} \mathcal E(\mathcal P) = O\big (M(n)^{\frac{2}{5}}n^{\frac{12}{5}+\varepsilon } + M(n)n^2\big ). \end{aligned}$$

We derive the lower bound $\mathcal E(\mathcal P)=\Omega (M(n)n^2)$, matching our upper bound when M(n) is large. We use our upper bound on $\mathcal E(\mathcal P)$ to obtain two rather different results:

• (i) If $\mathcal P$ determines $O(n/\sqrt{\log n})$ distinct distances, then for any $0<\alpha \le 1/4$, there exists a line or circle that contains at least $n^\alpha$ points of $\mathcal P$, or there exist $\Omega (n^{8/5-12\alpha /5-\varepsilon })$ distinct lines that contain $\Omega (\sqrt{\log n})$ points of $\mathcal P$. This result provides new information towards a conjecture of Erdős (Discrete Math 60:147–153, 1986) regarding the structure of point sets with few distinct distances.

• (ii) If no line or circle contains M(n) points of $\mathcal P$, the number of distinct perpendicular bisectors determined by $\mathcal P$ is $\Omega \left( \min \left\{ M(n)^{-2/5}n^{8/5-\varepsilon }, M(n)^{-1} n^2\right\} \right)$.

1 Introduction

Guth and Katz [13] proved that every set of n points in $\mathbb R^2$ determines $\Omega (n/ \log n)$ distinct distances. This almost completely settled a conjecture of Erdős [7], who observed that the $\sqrt{n}\times \sqrt{n}$ integer lattice determines $\Theta (n/\sqrt{\log n})$ distances, and conjectured that every set of n points determines at least this number of distances. Beyond the remaining $\sqrt{\log n}$ gap, this leaves open the question of which point sets determine few distances. Erdős [9] asked whether every set that determines $O(n/\sqrt{\log n})$ distances “has lattice structure”. He then wrote: The first step would be to decide if there always is a line which contains $cn^{1/2}$ of the points (and in fact $n^{\varepsilon }$ would already be interesting).’

Embarrassingly, almost three decades later the bound $n^{\varepsilon }$ seems as distant as it ever was. The following bound is a consequence of an argument of Szemerédi, presented by Erdős [8].

Theorem 1.1

(Szemerédi) If a set $\mathcal P$ of n points in $\mathbb R^2$ determines $O(n/\sqrt{\log n})$ distances, then there exists a line containing $\Omega (\sqrt{\log n})$ points of $\mathcal P$.

Recently, it was noticed that this bound can be slightly improved to $\Omega (\log n)$ points on a line (see [21]). Assuming that no line contains an asymptotically larger number of points, one can deduce the existence of $\Omega (n/\log n)$ distinct lines that contain $\Omega (\log n)$ points of $\mathcal P$. By inspecting Szemerédi’s proof, it is also apparent that these lines are perpendicular bisectors of pairs of points of $\mathcal P$.

This problem was recently approached from the other direction in [17, 18, 22]. Combining the results of these three papers implies the following. If an n-point set $\mathcal P\subset \mathbb R^2$ determines o(n) distances, then no line contains $\Omega (n^{43/52+\varepsilon })$ points of $\mathcal P$, no circle contains $\Omega (n^{5/6})$ points, and no other constant-degree irreducible algebraic curve contains $\Omega (n^{3/4})$ points.

In the current paper we study a different aspect of sets with few distinct distances. Our main tool is a bound on the bisector energy of the point set (see below for a formal definition). Using this tool, we prove that if a point set $\mathcal P$ determines $O(n/\sqrt{\log n})$ distinct distances, then there exists a line or a circle with many points of $\mathcal P$, or the number of lines containing $\Omega (\sqrt{\log n})$ points must be significantly larger than implied by Theorem 1.1. As another application of bisector energy, we prove that if no line or circle contains many points of a point set $\mathcal P$, then $\mathcal P$ determines a large number of distinct perpendicular bisectors. We will provide more background to both results after we have properly stated them.

2 Results

2.1 Bisector Energy

Given two distinct points $a,b\in \mathbb R^2$, we denote by $\mathcal {B}(a,b)$ their perpendicular bisector (i.e., the line consisting of all points that are equidistant from a and b); for brevity, we usually refer to it as the bisector of a and b. We define the bisector energy of $\mathcal P$ as

$$\begin{aligned} \mathcal E(\mathcal P) = \big |\big \{(a,b,c,d)\in \mathcal P^4 : \ a\ne b, \ c\ne d,\ \text {and}~ \ \mathcal {B}(a,b) = \mathcal {B}(c,d)\big \}\big |. \end{aligned}$$

Equivalently, $\mathcal E(\mathcal P)$ is the number of isosceles trapezoids determined by $\mathcal P$ (not counting isosceles triangles). Note that if each distinct pair of points of $\mathcal P$ determines a distinct bisector, then $\mathcal E(\mathcal P) = 2n(n-1)$, since quadruples of the form (a, b, a, b), (a, b, b, a), (b, a, a, b), and (b, a, b, a) are counted for each of the $\left( {\begin{array}{c}n\\ 2\end{array}}\right)$ choices for distinct $a,b \in \mathcal P$. In Sect. 3, we prove the following upper bound on this quantity.

Theorem 2.1

Let M(n) be an arbitrary function with positive values. For any n-point set $\mathcal P\subset \mathbb R^2$, such that no line or circle contains M(n) points of $\mathcal P$, we have¹

$$\begin{aligned} \mathcal E(\mathcal P) = O\big (M(n)^{\frac{2}{5}}n^{\frac{12}{5}+\varepsilon } + M(n)n^2\big ). \end{aligned}$$

We note that one important ingredient of our proof is the result of Guth and Katz [13]; without it, we would obtain a weaker (although nontrivial) bound on the bisector energy (see the remark at the end of Sect. 3.3).

In Sect. 4, we present a construction that implies a lower bound for the maximum bisector energy. It shows that Theorem 2.1 is tight when its second term dominates, i.e., when $M(n)=\Omega (n^{2/3+\varepsilon '})$.

Theorem 2.2

For any n and M(n), there exists a set $\mathcal P$ of n points in $\mathbb {R}^2$ such that no line or circle contains M(n) points of $\mathcal P$, and $\mathcal E(\mathcal P) = \Omega (M(n)n^2)$.

We conjecture that $\mathcal E(\mathcal P) = O(M(n)n^2)$ is true for all M(n).

Let $\mathcal P$ be a $\sqrt{n}\times \sqrt{n}$ section of the integer lattice. It is well known that $\mathcal P$ determines $\Theta (n/\sqrt{\log n})$ distinct distances (see [7]). It can be easily verified that no line or circle contains more than $\sqrt{n}$ points of $\mathcal P$ (a more involved argument shows that no circle contains $n^\varepsilon$ points of $\mathcal P$, for any $\varepsilon >0$). In this case we have $\mathcal E(\mathcal P)=O(n^{5/2})$, which fits our conjectured bound $\mathcal E(\mathcal P)=O(M(n)n^2)$.

In concurrent work, Hanson et al. [14] proved a finite field analogue of Theorem 2.1. They showed that for any $\mathcal P\subset \mathbb {F}_q^2$ we have $|\mathcal E(\mathcal P)|=O(|\mathcal P|^4q^{-2}+q|\mathcal P|^2)$, where $\mathcal E(\mathcal P)$ is analogously defined, and q is an odd prime power.

2.2 Few Distinct Distances

Pach and Tardos [16] proved that an n-point set $\mathcal P\subset \mathbb R^2$ determines $O(n^{2.137})$ isosceles triangles. They also observed that this bound implies that $\mathcal P$ contains a point from which there are $\Omega (n^{0.863})$ distinct distances (a result obtained earlier in [26] and improved slightly in [15]). Similarly, our upper bound on the number of isosceles trapezoids determined by a point set $\mathcal P$ has implications concerning the distinct distances that are determined by $\mathcal P$.

We deduce the following theorem from Theorem 2.1. More precisely, it follows from the slightly more general Theorem 5.1 that we prove in Sect. 5.

Theorem 2.3

Let $\mathcal P\subset \mathbb R^2$ be a set of n points that spans $O(n/\sqrt{\log n})$ distinct distances. For any $0<\alpha \le 1/4$, at least one of the following holds (with constants independent of $\alpha$).

• (i) There exists a line or a circle containing $\Omega (n^\alpha )$ points of $\mathcal P$.

• (ii) There are $\Omega (n^{\frac{8}{5}-\frac{12\alpha }{5}-\varepsilon })$ lines that contain $\Omega (\sqrt{\log n})$ points of $\mathcal P$.

If our conjecture that $\mathcal E(\mathcal P)=O(M(n)n^2)$ is true, alternative (ii) in the conclusion of Theorem 2.3 improves to $\Omega (n^{2 - 3\alpha }\log n)$ lines that contain $\Omega (\sqrt{\log n})$ points of $\mathcal P$.

We believe that Theorem 2.3 is a step towards Erdős’s lattice conjecture. We mention several recent results and conjectures that together paint an interesting picture.

Green and Tao [12] proved that, given an n-point set in $\mathbb R^2$ such that more than $n^2/6-O(n)$ lines contain at least three of the points, most of the points must lie on a cubic curve (an algebraic curve of degree three, which need not be irreducible). Elekes and Szabó [6] stated the stronger conjecture that if an n-point set determines $\Omega (n^2)$ collinear triples, then many of the points lie on a cubic curve; unfortunately, at this point it is not even known whether there must be a cubic that contains ten points of the set. Erdős and Purdy [10] conjectured that if n points determine $\Omega (n^2)$ collinear quadruples, then there must be five points on a line. If the point set is already known to lie on a low-degree algebraic curve, then both conjectures hold [6, 20]. On the other hand, Solymosi and Stojaković [23] proved that for any constant k, there are point sets with $\Omega (n^{2-\varepsilon })$ lines containing exactly k points, but no line with $k+1$ points.

The philosophy of these statements is that if there are many lines containing many points, then most points must lie on some low-degree algebraic curve. Our result shows that for an n-point set with few distinct distances, there is a line or circle with very many points, or else there are many lines with many points. In particular, in the second case there would be many collinear triples (although not quite as many as $\Omega (n^2)$), and many lines with very many points (more than a constant number). This suggests that few distinct distances should imply some algebraic structure. Let us pose a specific question in this direction: Are there constants $0<\beta ,\beta '<1$ such that if n points determine $\Omega (n^{1+\beta })$ lines with $\Omega (\sqrt{\log n})$ points, then $\Omega (n^{\beta '})$ points lie on a constant degree algebraic curve?

2.3 Distinct Bisectors

Let $\mathcal B(\mathcal P)$ be the set of those lines that are (distinct) perpendicular bisectors of $\mathcal P$. Since any point of $\mathcal P$ determines $n-1$ distinct bisectors with the other points of $\mathcal P$, we have a trivial lower bound $|\mathcal B(\mathcal P)|\ge n-1$. If $\mathcal P$ is a set of equally spaced points on a circle, then $|\mathcal B(\mathcal P)|= n$. Similarly, if $\mathcal P$ is a set of n equally spaced points on a line, then $|\mathcal B(\mathcal P)|= 2n-3$. As we now show, forbidding many points on a line or circle forces $|\mathcal B(\mathcal P)|$ to be significantly larger.

Theorem 2.4

If an n-point set $\mathcal P\subset \mathbb R^2$ has no M(n) points on a line or circle, then

$$\begin{aligned} |\mathcal B(\mathcal P)| = \Omega \big (\min \big \{M(n)^{-\frac{2}{5}}n^{\frac{8}{5}-\varepsilon }, M(n)^{-1} n^2\big \}\big ). \end{aligned}$$

Proof

For any line $\ell \subset \mathbb R^2$, set $E_\ell = \{(a,b)\in \mathcal P^2: a\ne b, ~\mathcal {B}(a,b) = \ell \}$. By the Cauchy–Schwarz inequality, we have

$$\begin{aligned} \mathcal E(\mathcal P) = \sum _{\ell \in \mathcal B(\mathcal P)} |E_\ell |^2 \ge \frac{1}{|\mathcal B(\mathcal P)|}\Big (\sum _{\ell \in \mathcal B(\mathcal P)} |E_\ell |\Big )^2 = \Omega \Big (\frac{n^4}{|\mathcal B(\mathcal P)|}\Big ). \end{aligned}$$

Combining this with the bound of Theorem 2.1 immediately implies the theorem. $\square$

Note that, as in Theorem 2.1, the minimum is the first expression as long as $M(n) =O(n^{2/3+\varepsilon '})$. We are not aware of any previous bound on the minimum number of distinct bisectors determined by a point set in $\mathbb {R}^2$. As a consequence of their bound on the bisector energy, Hanson et al. [14] proved that a set of at least $q^{3/2}$ points in $\mathbb {F}_q^2$ (where q is an odd prime power) determines $\Omega (q^2)$ distinct perpendicular bisectors.

We are not aware of any point set that determines $o(n^2)$ distinct bisectors without having the vast majority of the points on a single line or circle. We conjecture that for any $c<1$, if a set $\mathcal P$ of n points in $\mathbb R^2$ has the property that no line or circle contains cn points of $\mathcal P$, then the number of distinct bisectors that are determined by $\mathcal P$ is $\Omega (n^{2})$. We note that while Theorem 2.1 is tight for $M(n) = \Omega (n^{2/3+\varepsilon })$, applying it in the proof of Theorem 2.4 leads to a bound that seems not to be tight (excluding the trivial case of $M(n) = n - O(1)$).

Theorem 2.4 is related to a series of results initiated by Elekes and Rónyai [4], studying the expansion properties of polynomials and rational functions. For instance, in [19] it is proved that a polynomial function $F:\mathbb R\times \mathbb R\rightarrow \mathbb R$ takes $\Omega (n^{4/3})$ values on the $n^2$ pairs from a finite set in $\mathbb R$ of size n, unless F has a special form. Elekes and Szabó [5] derived, among other things, the following two-dimensional generalization (rephrased for our convenience, and omitting some details). If $F:\mathbb R^2\times \mathbb R^2\rightarrow \mathbb R^2$ is a rational function that is not of a special form, and $\mathcal P\subset \mathbb R^2$ is an n-point set such that no low-degree curve contains more than a constant number of points of $\mathcal P$, then F takes $\Omega (n^{1+\varepsilon })$ values on $\mathcal P\times \mathcal P$. Note that the condition on avoiding low-degree curves is very restrictive.

Theorem 2.4 proves a better bound for the function $\mathcal B$, with a less restrictive condition on $\mathcal P$. If we view a line $y=sx+t$ as a point $(s,t)\in \mathbb R^2$, then (see the proof of Lemma 3.1)

$$\begin{aligned} \mathcal B(a_x,a_y,b_x,b_y) = \Big (-\frac{a_x-b_x}{a_y-b_y}, \frac{(a_x^2+a_y^2) - (b_x^2+b_y^2)}{2(a_y-b_y)}\Big ) \end{aligned}$$

is a rational function $\mathbb R^2\times \mathbb R^2\rightarrow \mathbb R^2$. Theorem 2.4 says that $\mathcal B$ takes many distinct values on $\mathcal P\times \mathcal P$ if $\mathcal P$ has few points on a line or circle. So we have replaced the broad condition of [5] that not too many points lie on a low-degree curve, with the very specific condition that not too many points lie on a line or circle.

2.4 An Incidence Bound

One of the tools we use to prove Theorem 2.1 is the incidence bound below, which is a refined version of a theorem of Fox et al. [11].

Given a set $\mathcal P\subset \mathbb R^d$ of points and a set $\mathcal S\subset \mathbb R^d$ of varieties, the incidence graph is a bipartite graph with vertex sets $\mathcal P$ and $\mathcal S$, such that $(p,S)\in \mathcal P\times \mathcal S$ is an edge in the graph if $p\in S$. We write $I(\mathcal P,\mathcal S)$ for the number of edges of this graph, or in other words, for the number of incidences between $\mathcal P$ and $\mathcal S$. We denote the complete bipartite graph on s and t vertices by $K_{s,t}$ (in the incidence graph, such a subgraph corresponds to s points that are contained in t varieties). For the definitions of the algebraic terms in this statement we refer to [11].

Theorem 2.5

Let $\mathcal S$ be a set of n constant-degree varieties and let $\mathcal P$ be a set of m points, both in $\mathbb R^d$, such that the incidence graph of $\mathcal P\times \mathcal S$ contains no copy of $K_{s,t}$ (where s is a constant, but t may depend on m, n). Moreover, suppose that $\mathcal P\subset V$, where V is an irreducible constant-degree variety of dimension e. Then

$$\begin{aligned} I(\mathcal P,\mathcal S) = O\big (m^{\frac{s(e-1)}{es-1}+\varepsilon }n^{\frac{e(s-1)}{es-1}}t^{\frac{e-1}{es-1}} +tm+n\big ). \end{aligned}$$

The main difference between Theorem 2.5 and the corresponding theorem in Fox et al. [11] is that Theorem 2.5 shows the dependence of the bound on t, which was left implicit in [11]. The proof that we give in Sect. 6 is a slight modification of the proof in [11].

3 Proof of Theorem 2.1

In this section we prove Theorem 2.1 by relating the bisector energy to an incidence problem between points and algebraic surfaces in $\mathbb R^4$. In Sect. 3.1 we define the surfaces, in Sect. 3.2 we analyze their intersection properties, and in Sect. 3.3 we apply the incidence bound of Theorem 2.5 to prove Theorem 2.1.

Throughout this section we assume that we have rotated $\mathcal P$ so that no two points have the same x- or y-coordinate; in particular, we assume that no perpendicular bisector is horizontal or vertical.

3.1 Bisector Surfaces

Recall that in Theorem 2.1 we consider an n-point set $\mathcal P\subset \mathbb R^2$. We define

$$\begin{aligned} {\mathcal P}^{2*}= \{(a,c)\in \mathcal P^2: a\ne c\}, \end{aligned}$$

and we view it as a point set in $\mathbb R^4$. Similarly, we define

$$\begin{aligned} {\mathcal P}^{4*}= \{(a,b,c,d)\in \mathcal P^4: a\ne b, c\ne d; a\ne c, b\ne d\}. \end{aligned}$$

Also recall that for distinct $a,b\in \mathcal P$, we denote by $\mathcal {B}(a,b)$ the perpendicular bisector of a and b. We define the bisector surface of a pair $(a,c)\in {\mathcal P}^{2*}$ as

$$\begin{aligned} S_{ac} = \{(b,d)\in \mathbb R^2\times \mathbb R^2: a \ne b,~ c \ne d, \text { and } \mathcal {B}(a,b) = \mathcal {B}(c,d)\}, \end{aligned}$$

and we set $\mathcal S= \{ S_{ac}: (a,c)\in {\mathcal P}^{2*}\}$. The surface $S_{ac}$ is not an algebraic variety (so we are using the word “surface” loosely), but the lemma below shows that $S_{ac}$ is “close to” a variety $\overline{S}_{ac}$. That $S_{ac}$ is contained in a constant-degree two-dimensional² variety is no surprise (one can take the Zariski closure), but we need to analyze this variety in detail to establish the exact relationship.

We will work mostly with the surface $S_{ac}$ in the rest of this proof, rather than with the variety $\overline{S}_{ac}$, because its definition is easier to handle. Then, when we apply our incidence bound, which holds only for varieties, we will switch to $\overline{S}_{ac}$. Fortunately, the following lemma shows that it is easy to characterize the points of ${\mathcal P}^{2*}$ that are in $\overline{S}_{ac}$ but not in $S_{ac}$.

Lemma 3.1

For distinct $a,c\in \mathcal P$, there exists a two-dimensional constant-degree algebraic variety $\overline{S}_{ac}$ such that $S_{ac}\subset \overline{S}_{ac}$. Moreover, if $(b,d)\in (\overline{S}_{ac}\backslash S_{ac})\cap {\mathcal P}^{2*}$, then $b=a$ or $d = c$.

Proof

Consider a point $(b,d)\in S_{ac}$. Write the equation defining the perpendicular bisector $\mathcal {B}(a,b)=\mathcal {B}(c,d)$ as $y=sx+t$. The slope s satisfies

$$\begin{aligned} s = -\frac{a_x-b_x}{a_y-b_y} = -\frac{c_x-d_x}{c_y-d_y}. \end{aligned}$$

(1)

By definition $\mathcal {B}(a,b)$ passes through the midpoint $((a_x+b_x)/2$, $(a_y+b_y)/2)$ of a and b, as well as through the midpoint $\left( (c_x+d_x)/2,(c_y+d_y)/2\right)$ of c and d. We thus have

$$\begin{aligned} \frac{a_y+b_y}{2} - s\frac{a_x+b_x}{2} = t = \frac{c_y+d_y}{2} - s\frac{c_x+d_x}{2}. \end{aligned}$$

(2)

By combining (1) and (2) we obtain

$$\begin{aligned} (a_y-b_y)(c_x^2+c_y^2-d_x^2-d_y^2) = (c_y-d_y)(a_x^2+a_y^2-b_x^2-b_y^2). \end{aligned}$$

(3)

From (1) and (3) we see that $(b,d)=(x_1,x_2,x_3,x_4)$ satisfies

$$\begin{aligned} f_{ac}(x_1,x_2,x_3,x_4)= & {} (a_x-x_1)(c_y-x_4) - (a_y-x_2)(c_x-x_3) = 0, \\ g_{ac}(x_1,x_2,x_3,x_4)= & {} (a_y-x_2)(c_x^2+c_y^2-x_3^2-x_4^2)\\&- (c_y-x_4)(a_x^2+a_y^2-x_1^2-x_2^2)=0. \end{aligned}$$

Since any point $(b,d)\in S_{ac}$ satisfies these two equations, we have

$$\begin{aligned} S_{ac}\subset Z(f_{ac},g_{ac}) = \overline{S}_{ac}. \end{aligned}$$

Consider a point $(b,d)\in (\overline{S}_{ac}\backslash S_{ac})\cap {\mathcal P}^{2*}$. By reexamining the above analysis, we see that for this to happen we must have $a_y=b_y$ or $c_y=d_y$ (since then (1) is not well defined). By the assumption that no two points of $\mathcal P$ have the same y-coordinate, this implies $a = b$ or $c = d$.

It remains to prove that $\overline{S}_{ac}$ is a constant-degree two-dimensional variety. The constant degree is immediate from $f_{ac}$ and $g_{ac}$ being polynomials of degree at most three. As just observed, a point $(b,d)\in \overline{S}_{ac} \backslash S_{ac}$ satisfies $a_y=b_y$ or $c_y=d_y$. If $a_y=b_y$, then for $f_{ac}(b,d)=g_{ac}(b,d)=0$ to hold, we must have $a_x=b_x$ or $c_y=d_y$. Similarly, if $c_y=d_y$, then $c_x=d_x$ or $a_y=b_y$. We see that in each case we get two independent linear equations, which define a plane, so $\overline{S}_{ac} \backslash S_{ac}$ is the union of three two-dimensional planes. Thus, it suffices to prove that $S_{ac}$ is two-dimensional. For this, we simply show that for any valid value of b there is at most one valid value of d. Let $C_{ac}\subset \mathbb R^2$ denote the circle that is centered at c and incident to a (here we use $a\ne c$). It is impossible for b to lie on $C_{ac}$, since this would imply that the bisector $\mathcal {B}(a,b)$ contains c, and thus that $\mathcal {B}(a,b)\ne \mathcal {B}(c,d)$. For any choice of $b\notin C_{ac}$, the bisector $\mathcal {B}(a,b)$ is well-defined and is not incident to c, so there is a unique $d\in \mathbb R^2$ with $\mathcal {B}(a,b)=\mathcal {B}(c,d)$ (i.e., so that $(b,d)\in S_{ac}$). $\square$

Remark

Note that the variety $\overline{S}_{ac}$ is not the Zariski closure of $S_{ac}$. For example, $\overline{S}_{ac}$ also contains the two-dimensional plane that is defined by $x_2=a_y$ and $x_4=c_y$.

3.2 Intersections of Bisector Surfaces

We denote by $\mathbf R _{ab}$ the reflection of $\mathbb R^2$ across the line $\mathcal {B}(a,b)$. Observe that if $\mathcal {B}(a,b) = \mathcal {B}(c,d)$, then $\mathbf R _{ab} = \mathbf R _{cd}$, and this reflection maps a to b and c to d; this in turn implies that $|ac| = |bd|$. That is, $(b,d)\in S_{ac}$ implies $|ac|=|bd|$. It follows that if $|ac| = \delta$, then the surface $S_{ac}$ is contained in the hypersurface

$$\begin{aligned} H_\delta = \{(b,d)\in \mathbb R^2\times \mathbb R^2 : |bd| = \delta \}. \end{aligned}$$

We can thus partition $\mathcal S$ into classes corresponding to the distances $\delta$ that are determined by pairs of points of $\mathcal P$. Each class consists of the surfaces $S_{ac}$ with $|ac|=\delta$, all of which are fully contained in $H_\delta$.

We now study the intersection of two surfaces contained in a hypersurface $H_\delta$.

Lemma 3.2

Let $(a,c)\ne (a',c')$, $|ac| = |a'c'| = \delta \ne 0$, and $S_{a,c} \cap S_{a,c'} \ne \emptyset$. Then there exist curves $C_1,C_2\subset \mathbb R^2$, which are either two concentric circles or two parallel lines, such that $a,a'\in C_1$, $c,c'\in C_2$, and $S_{ac}\cap S_{a'c'}$ is contained in the set

$$\begin{aligned} H_\delta \cap (C_1\times C_2) = \{(b,d)\in \mathbb R^2\times \mathbb R^2: b\in C_1,d\in C_2,|bd| = \delta \}. \end{aligned}$$

Proof

We first consider the case where $a=a'$, and let $(b,d)\in S_{a,c} \cap S_{a,c'}$. That is, we have $\mathcal {B}(c,d) = \mathcal {B}(a,b)= \mathcal {B}(c',d)$, which in turn implies $c = c'$. Since this contradicts an assumption of the lemma, we may assume that $a\ne a'$. By a symmetric argument we may assume that $c \ne c'$.

We split the analysis into three cases: (i) $|\mathcal {B}(a,a')\cap \mathcal {B}(c,c')|=1$, (ii) $\mathcal {B}(a,a') = \mathcal {B}(c,c')$, and (iii) $\mathcal {B}(a,a')\cap \mathcal {B}(c,c') =\emptyset$. The three cases are depicted in Fig. 1.

Fig. 1

The three cases in the analysis of Lemma 3.2

Case (i) Let $o = \mathcal {B}(a,a')\cap \mathcal {B}(c,c')$. Then there exist two (not necessarily distinct) circles $C_1,C_2$ around o such that $a,a'\in C_1$ and $c,c'\in C_2$ . If $(b,d)\in S_{ac}\cap S_{a'c'}$, then the reflection $\mathbf R _{ab}$ maps a to b and c to d, and similarly, $\mathbf R _{a'b}$ maps b to $a'$ and d to $c'$. We set $\mathbf T = \mathbf R _{a'b}\circ \mathbf R _{ab}$, and notice that this is a rotation whose center $o^*$ is the intersection point of $\mathcal {B}(a,b)=\mathcal {B}(c,d)$ and $\mathcal {B}(a',b)=\mathcal {B}(c',d)$. Note that $\mathbf T (a) = a'$ and $\mathbf T (c) = c'$, so $o^*$ lies on both $\mathcal {B}(a,a')$ and $\mathcal {B}(c,c')$. Since $o=\mathcal {B}(a,a')\cap \mathcal {B}(c,c')$, we obtain that $o=o^*$. Since $\mathcal {B}(a,b)$ passes through o, we have that b is incident to $C_1$. Similarly, since $\mathcal {B}(c,d)$ passes through o, we have that d is incident to $C_2$. This implies that (b, d) lies in $H_\delta \cap (C_1\times C_2)$.

Case (ii) Let $\ell$ be the line $\mathcal {B}(a,a') = \mathcal {B}(c,c')$. The line segment ac is a reflection across $\ell$ of the line segment $a'c'$. Thus, the intersection point o of the lines that contains these two segments is incident to $\ell$. Let $C_1$ be the circle centered at o that contains a and $a'$, and let $C_2$ be the circle centered at o that contains c and $c'$. With this definition of o, $C_1$, and $C_2$, we can repeat the analysis of case (i), obtaining the same conclusion.

Case (iii) In this case $\mathcal {B}(a,a')$ and $\mathcal {B}(c,c')$ are parallel. The analysis of this case is similar to that in case (i), but with lines instead of circles.

Let $C_1$ be the line that is incident to a and $a'$, and let $C_2$ be the line that is incident to c and $c'$. Note that $C_1$ and $C_2$ are parallel lines, each perpendicular to $\mathcal {B}(a,a')$ and $\mathcal {B}(c,c')$. If $(b,d)\in S_{ac}\cap S_{a'c'}$, then, as before, $\mathbf R _{ab}$ maps a to b and c to d, and $\mathbf R _{a'b}$ maps b to $a'$ and d to $c'$. Since $\mathbf T = \mathbf R _{a'b}\circ \mathbf R _{ab}$ maps a to $a'$ and c to $c'$, it is a translation in the direction parallel to the lines $C_1$ and $C_2$; hence, $\mathbf R _{a'b}$ and $\mathbf R _{ab}$ are reflections over lines that are perpendicular to $C_1$ and $C_2$. This implies that $b\in C_1$ and $d\in C_2$, which completes the analysis of this case. $\square$

In Sect. 3.3, we will use Theorem 2.5 to bound the number of incidences between the point set ${\mathcal P}^{2*}=\{(b,d)\in \mathcal P^2: b\ne d\}$ and the set of surfaces $\mathcal S$. For this we need to show that the incidence graph contains no complete bipartite graph $K_{2,M}$; that is, that for any two points of ${\mathcal P}^{2*}$ there is a bounded number of surfaces of $\mathcal S$ that contain both points. In the following lemma we prove the more general statement that the incidence graph contains no $K_{2,M}$ and no $K_{M,2}$, although we will only make use of the fact that there is no $K_{2,M}$.

Corollary 3.3

If no line or circle contains M points of $\mathcal P$, then the incidence graph of ${\mathcal P}^{2*}\times \mathcal S$ contains neither a copy of $K_{2,M}$ nor a copy of $K_{M,2}$.

Proof

As mentioned above, $(b,d) \in \mathcal S_{ac}$ implies $|ac| = |bd|$. Hence, it suffices to consider pairs of surfaces $S_{ac}, S_{a'c'}$ with $|ac| = |a'c'|$.

Consider two distinct surfaces $S_{ac},S_{a'c'}\in \mathcal S$ with $|ac|=|a'c'|=\delta$. Lemma 3.2 implies that there exist two lines or circles $C_1,C_2$ such that $(b,d)\in S_{ac}\cap S_{a'c'}$ only if $b\in C_1$ and $d\in C_2$. Since no line or circle contains M points of $\mathcal P$, we have $|C_1\cap \mathcal P|< M$. Given $b\in (C_1\cap \mathcal P)\backslash \{a\}$, there is at most one $d\in \mathcal P$ such that $\mathcal {B}(a,b) = \mathcal {B}(c,d)$, and thus at most one point $(b,d)\in S_{ac}$. (Notice that no points of the form $(a,d)\in {\mathcal P}^{2*}$ are in $S_{ac}$.) Thus

$$\begin{aligned} |(S_{ac}\cap S_{a'c'})\cap {\mathcal P}^{2*}| < M. \end{aligned}$$

That is, the incidence graph contains no copy of $K_{M,2}$.

We now define “dual” surfaces for pairs $(b,d)\in {\mathcal P}^{2*}$ by

$$\begin{aligned} S_{bd}^* = \{(a,c)\in \mathbb R^2\times \mathbb R^2: a\ne b,~ c\ne d, \text { and } \mathcal {B}(a,b) = \mathcal {B}(c,d)\}, \end{aligned}$$

and set $\mathcal {S}^* = \{S_{bd}^*: (b,d)\in {\mathcal P}^{2*}\}$. By a symmetric argument, we get

$$\begin{aligned} |(S^*_{bd}\cap S^*_{b'd'})\cap {\mathcal P}^{2*}| < M \end{aligned}$$

for all $(b,d)\ne (b',d')$. Observe that $(a,c)\in S^*_{bd}$ if and only if $(b,d)\in S_{ac}$. Hence, having fewer than M points $(a,c)\in (S^*_{bd}\cap S^*_{b'd'})\cap {\mathcal P}^{2*}$ is equivalent to having fewer than M surfaces $S_{ac}$ that contain both (b, d) and $(b',d')$; i.e., the incidence graph contains no $K_{2,M}$. $\square$

Remark

Set $\overline{\mathcal S} = \{\overline{S}_{ac}:(a,c)\in {\mathcal P}^{2*}\}$. Because the surfaces in $\mathcal S$ are not varieties, and our incidence bound applies only to varieties, we will actually apply it to $\overline{\mathcal S}$. This leads to the following complication, which will be dealt with below. The incidence graph of ${\mathcal P}^{2*}\times \overline{\mathcal S}$ does contain large complete bipartite graphs. Indeed, for fixed $a\in \mathcal P$ we have $(a,d)\in \overline{S}_{ac}$ for all d, c not equal to a, which gives a copy of $K_{n-1,n-1}$ in the incidence graph.

3.3 Applying the Incidence Bound

For simplicity, we write $M=M(n)$ throughout this proof. We set

$$\begin{aligned} Q = \{ (a,b,c,d) \in {\mathcal P}^{4*}: \ \mathcal {B}(a,b) = \mathcal {B}(c,d)\}, \end{aligned}$$

and note that $|Q|+n(n-1) = \mathcal E(\mathcal P)$, where the term $n(n-1)$ accounts for the quadruples of the form (a, b, a, b). As we saw in Sect. 3.2, every quadruple $(a,b,c,d)\in Q$ satisfies $|ac|=|bd|$.

Let $\delta _1,\ldots , \delta _D$ denote the distinct distances that are determined by pairs of distinct points in $\mathcal P$. We partition ${\mathcal P}^{2*}$ into the disjoint subsets $\Pi _1,\ldots ,\Pi _D$, where

$$\begin{aligned} \Pi _i = \{(u,v)\in {\mathcal P}^{2*}: |uv|=\delta _i\}. \end{aligned}$$

We also partition $\mathcal S$ into disjoint subsets $\mathcal S_1,\ldots ,\mathcal S_D$, defined by

$$\begin{aligned} \mathcal S_i = \{S_{ac}\in \mathcal S: |ac| = \delta _i\}. \end{aligned}$$

Similarly, we set $\overline{\mathcal S}_i = \{\overline{S}_{ac}\in \mathcal S: |ac| = \delta _i\}$. Let $m_i$ be the number of $(a,c)\in {\mathcal P}^{2*}$ such that $|ac| =\delta _i$. Note that $|\Pi _i| = |\mathcal S_i| = m_i$ and

$$\begin{aligned} \sum m_i = n(n-1). \end{aligned}$$

A quadruple $(a,b,c,d)\in {\mathcal P}^{4*}$ is in Q if and only if the point (b, d) is incident to $S_{ac}$. Moreover, there exists a unique $1\le i\le D$ such that $(b,d)\in \Pi _i$ and $S_{ac}\in \mathcal S_i$. Therefore, it suffices to study each $\Pi _i$ and $\mathcal S_i$ separately. That is, we have

$$\begin{aligned} |Q| =\sum _{i=1}^D I(\Pi _i,\mathcal S_i). \end{aligned}$$

We have $I(\Pi _i,\mathcal S_i)\le I(\Pi _i,\overline{\mathcal S}_i)$, and we will use Theorem 2.5 to bound $I(\Pi _i,\overline{\mathcal S}_i)$ for each i. By Corollary 3.3, the incidence graph of ${\mathcal P}^{2*}\times \mathcal S$ contains no $K_{2,M}$, hence neither does the incidence graph of $\Pi _i\times \mathcal S_i$. As observed after Corollary 3.3, the incidence graph of ${\mathcal P}^{2*}\times \overline{\mathcal S}$ does contain large complete bipartite graphs. Fortunately, this is not the case for $\Pi _i\times \overline{\mathcal S}_i$, as we now argue.

Consider a point $(b,d)\in \Pi _i$ and a surface $S_{ac}\in \overline{\mathcal S}_i$ such that $(b,d)\in \overline{S}_{ac}\backslash S_{ac}$; we have $|ac| = \delta _i = |bd|$. By Lemma 3.1, we have $b=a$ or $d=c$. If $b=a$, then c lies on the circle around b of radius $\delta _i$, while if $d=c$, then a lies on the circle around d of radius $\delta _i$. By assumption, no circle contains M points of $\mathcal P$, so there are less than M points c for which $(b,d)\in \overline{S}_{bc}\backslash S_{bc}$, and less than M points a for which $(b,d)\in \overline{S}_{ad}\backslash S_{ad}$. This means that the incidence graph of $\Pi _i\times \overline{\mathcal S}_i$ has at most 2M more edges incident with (a, d) than the incidence graph of $\Pi _i\times \mathcal S_i$. It follows that the incidence graph of $\Pi _i\times \overline{\mathcal S}_i$ contains no $K_{2,3M}$.

Observe that $\Pi _i\subset H_{\delta _i}$. The hypersurface $H_{\delta _i}$ is irreducible, three-dimensional, and of a constant degree, since it is defined by the irreducible polynomial $(x_1-x_3)^2+(x_2-x_4)^2 - \delta _i$. Thus we can apply Theorem 2.5 to the incidence graph of $\Pi _i\times \overline{\mathcal S}_i$, with $m=n=m_i$, $V = H_{\delta _i}$, $d=4$, $e=3$, $s=2$, and $t=3M$. This implies that

$$\begin{aligned} I(\Pi _i,\mathcal S_i)\le I(\Pi _i,\overline{\mathcal S}_i) = O\big (M^{\frac{2}{5}} m_i^{\frac{7}{5}+\varepsilon } + Mm_i \big ). \end{aligned}$$

(4)

Let J be the set of indices $1\le j\le D$ for which the bound in (4) is dominated by the term $M^{2/5} m_j^{7/5+\varepsilon }$. By recalling that $\sum _{j=1}^D m_j = n(n-1)$, we get

$$\begin{aligned} \sum _{j\not \in J}I(\Pi _j,\mathcal S_j) = O(Mn^2). \end{aligned}$$

Next we consider $\sum _{j\in J}I(\Pi _j,\mathcal S_j) = O(\sum _{j\in J} M^{2/5} m_j^{7/5+\varepsilon } )$. By [13, Prop. 2.2], we have

$$\begin{aligned} \sum m_j^2 = O(n^3\log n). \end{aligned}$$

This implies that the number of $m_j$ for which $m_j\ge x$ is $O(n^3\log n/x^2)$. By using a dyadic decomposition, we obtain

$$\begin{aligned} M^{-\frac{2}{5}}n^{-\varepsilon }\sum _{j\in J}I(\Pi _j,\mathcal S_j)&= O\Big ( \sum _{m_j \le \Delta } m_j^{\frac{7}{5}} + \sum _{k\ge 1} \sum _{2^{k-1}\Delta <m_j\le 2^{k}\Delta } m_j^{\frac{7}{5}}\Big ) \\&= O\Big ( \Delta ^{\frac{7}{5}}\cdot \frac{n^2}{\Delta } + \sum _{k\ge 1} (2^k\Delta )^{\frac{7}{5}} \cdot \frac{n^3\log n}{(2^{k-1}\Delta )^2}\Big ) \\&= O\Big ( \Delta ^{\frac{2}{5}}n^2 + \frac{n^3\log n}{\Delta ^{\frac{3}{5}}} \Big ). \end{aligned}$$

By setting $\Delta = n\log n$, we have

$$\begin{aligned} \sum _{j\in J}I(\Pi _j,\mathcal S_j) = O(M^{\frac{2}{5}}n^{\frac{12}{5}+\varepsilon } \log ^{\frac{2}{5}} n) = O(M^{\frac{2}{5}}n^{\frac{12}{5}+\varepsilon '} ). \end{aligned}$$

In conclusion,

$$\begin{aligned} \mathcal E(\mathcal P) \le |Q| +n^2 =\sum _{j\in J}I(\Pi _j,\mathcal S_j)+\sum _{j\not \in J}I(\Pi _j,\mathcal S_j) +n^2 = O(M^{\frac{2}{5}}n^{\frac{12}{5}+\varepsilon '}+Mn^2), \end{aligned}$$

which completes the proof of Theorem 2.1.

3.4 Remark About the Incidence Bound

Instead of partitioning the problem into D separate incidence problems, one can apply an incidence bound directly to the point set ${\mathcal P}^{2*}$ and the surface set $\mathcal S$. Roughly speaking, the best known bounds for incidences with two-dimensional surfaces in $\mathbb R^4$, whose incidence graph contains no $K_{2,M}$, are of the form $|{\mathcal P}^{2*}|^{2/3}|\mathcal S|^{2/3}$. Relying on such an incidence bound (and not using [13]) would yield a bound $|Q| = O(M^{1/3}n^{8/3} +Mn^2)=O(M^{1/3}n^{8/3})$, which is nontrivial but weaker than our bound.

4 A Lower Bound for $\mathcal E(\mathcal P)$

In this section we prove Theorem 2.2. In particular, for any n and $M(n)\ge 32$, we show that there exists a set $\mathcal P$ of n points in $\mathbb {R}^2$ such that any line or circle contains at most M(n) points of $\mathcal P$, and $\mathcal E(\mathcal P) = \Omega \left( M(n)n^2 \right)$. Note that we can suppose $M(n)\ge 32$ without loss of generality since, if $M(n)<32$, an arbitrary point set has $\mathcal E(\mathcal P)=\Omega (n^2) = \Omega (M(n)n^2)$.

For simplicity, we assume that M(n) is a multiple of 8, and that n is divisible by M(n). It is straightforward to extend the construction to values that do not satisfy these conditions.

Fig. 2

The lower bound construction

Let C be an ellipse that is centered at the origin, has a major axis of length 2 that is parallel to the y-axis, and a minor axis of length 1 that is parallel to the x-axis. Let $\mathcal P^{+}$ be an arbitrary set of 4n / M(n) points on C, each having a strictly positive x-coordinate. Let $\mathcal P^{-}$ be the reflection of $\mathcal P^+$ over the y-axis, and set $\mathcal P' = \mathcal P^+ \cup \mathcal P^-$. We denote by $\mathcal P'_j$ the translate of $\mathcal P'$ by (4j, 0). Finally, we take $\mathcal P= \mathcal P'_0 \cup \mathcal P'_1 \cup \cdots \cup \mathcal P'_{M(n)/8 -1}$. An example is depicted in Fig. 2.

Note that $\mathcal P$ lies on the union of M(n) / 8 ellipses. Since a line can intersect an ellipse in at most two points, and a circle can intersect an ellipse in at most four points, we indeed have that a line or circle contains at most M(n) points of $\mathcal P$.

It remains to prove that $\mathcal E(\mathcal P) = \Omega (M(n)n^2)$. For every integer $M(n)/32 \le j \le M(n)/16$, we denote by $\ell _j$ the vertical line $x = 4j$. For every such j, there are $\Theta (n)$ points of $\mathcal P$ that are to the left $\ell _j$, and such that the reflection of every such point across $\ell _j$ is another point of $\mathcal P$. That is, for every $M(n)/32 \le j \le M(n)/16$, the line $\ell _j$ is the perpendicular bisector of $\Theta (n)$ pairs of points of $\mathcal P$. The assertion of the theorem follows, since there are $\Theta (M(n))$ such lines, each contributing $\Theta (n^2)$ to $\mathcal E(\mathcal P)$.

5 Proof of Theorem 2.3

In this section we prove that Theorem 2.3 follows from Theorem 2.1. In fact, we prove the following more general version of Theorem 2.3.

Theorem 5.1

Let K(n) and M(n) be two functions satisfying $K(n)=O(\log n)$ and $M(n)=O(n^{1/4})$. If an n-point set $\mathcal P\subset \mathbb R^2$ spans $D=O(n/K(n))$ distinct distances, then at least one of the following holds.

• (i) There exists a line or a circle containing M(n) points of $\mathcal P$.

• (ii) There are $\Omega (M(n)^{-\frac{12}{5}}n^{\frac{8}{5}-\varepsilon })$ lines that contain $\Omega (K(n))$ points of $\mathcal P$.

Since Guth and Katz [13] proved that any n-point set spans $\Omega (n/\log n)$ distinct distances, the assumption that $K=O(\log n)$ is not a real restriction. The original formulation of Theorem 2.3 is immediately obtained by setting $K(n)=\sqrt{\log n}$ and $M(n) = n^\alpha$.

Proof

For simplicity, we use the notation $K=K(n)$ and $M=M(n)$ throughout this proof. Beck [1] proved that if a set of n points in $\mathbb R^2$ does not contain $\delta n$ collinear points then the points span $\Omega (n^2)$ lines. This result is stronger than the assertion of Theorem 5.1 when $K=O(1)$. We may thus assume that K is at least some large constant.

We assume that (i) does not hold, and prove that (ii) holds in this case. Given a point set $\mathcal P\subset \mathbb R^2$, we denote by $\mathcal B^*(\mathcal P)$ the multiset of bisectors that are spanned by ordered pairs of ${\mathcal P}^{2*}$. Recall that $\mathcal B(\mathcal P)$ is the set of distinct lines of $\mathcal B^*(\mathcal P)$. For every line $\ell \in \mathcal B(\mathcal P)$, we denote by $\mu (\ell )$ its multiplicity in $\mathcal B^*(\mathcal P)$ (i.e., the number of times it occurs in the multiset), and set $\rho (\ell )=|\ell \cap \mathcal P|$. We define

$$\begin{aligned} I(\mathcal P,\mathcal B^*(\mathcal P)) = \sum _{\ell \in \mathcal B(\mathcal P)} \mu (\ell )\rho (\ell ); \end{aligned}$$

that is, $I(\mathcal P,\mathcal B^*(\mathcal P))$ is the number of incidences counted with multiplicities.

We derive a lower bound on $I(\mathcal P,\mathcal B^*(\mathcal P))$ by using an argument that is similar to the one in Szemerédi’s proof of Theorem 1.1. Let $T \subset \mathcal P^3$ be the set of triples (p, q, r) of distinct points of $\mathcal P$ such that $|pq|=|pr|$. Note that a triple (p, q, r) is in T if and only if p is incident to $\mathcal {B}(q,r)$. That is,

$$\begin{aligned} I(\mathcal P,\mathcal B^*(\mathcal P)) = |T|. \end{aligned}$$

Denote the distances that are determined by pairs of ${\mathcal P}^{2*}$ as $\delta _1,\ldots ,\delta _D$. For every point $p\in \mathcal P$ and $1\le i \le D$, let $\Delta _{i,p}$ denote the number of points of $\mathcal P$ that have distance $\delta _i$ from p. Let $T_p \subset T$ denote the set of triples of T in which the first element is p. Applying the Cauchy–Schwarz inequality yields

$$\begin{aligned} |T_p| = \Omega \Big (\sum _{i=1}^D \Delta _{i,p}^2 - \Delta _{i,p} \Big ) =\Omega \Big (\frac{1}{D}\Big (\sum _{i=1}^D \Delta _{i,p}\Big )^2 - (n-1)\Big ) = \Omega \Big (\frac{n^2}{D}\Big ), \end{aligned}$$

where the last transition comes from the assumption that K is at least some large constant.

The above implies

$$\begin{aligned} I(\mathcal P,\mathcal B^*(\mathcal P)) = |T| = \sum _{p\in \mathcal P} |T_p| = \Omega \Big (\frac{n^3}{D}\Big )=\Omega (Kn^2). \end{aligned}$$

(5)

We remark that by the Szemerédi–Trotter theorem [25], the number of incidences between n points and $n^2$ distinct lines is $O(n^2)$. This does not contradict (5) since the lines in the multiset $\mathcal B^*(\mathcal P)$ need not be distinct. A priori, it might be that $\mathcal B^*(\mathcal P)$ consists of $\Theta (n)$ distinct lines, each with multiplicity $\Theta (n)$ and incident to $\Theta (K)$ points. However, our bound on the bisector energy excludes such cases.

Let $c_t$ be the constant implicit in the lower bound on |T|; we have

$$\begin{aligned} |T| \ge c_t Kn^2. \end{aligned}$$

Let $L^+$ be the subset of lines in $\mathcal B(\mathcal P)$ that are each incident to at least $c_t K / 2$ points. Then

$$\begin{aligned} c_t Kn^2&\le \sum _{\ell \in \mathcal B(\mathcal P)} \mu (\ell )\rho (\ell )\\&= \sum _{\ell \in L^+} \mu (\ell )\rho (\ell ) + \sum _{\ell \in \mathcal B(\mathcal P) \backslash L^+} \mu (\ell )\rho (\ell )\\&\le \sum _{\ell \in L^+} \mu (\ell )\rho (\ell ) + c_t K n^2 /2, \end{aligned}$$

where we use the fact that each ordered pair of points has a unique bisector, and hence contributes to $\sum _{\ell \in \mathcal B(\mathcal P)} \mu (\ell )$ exactly once. Applying Cauchy–Schwarz, we get

$$\begin{aligned} c_t^2 K^2 n^4/4 \le \sum _{\ell \in L^+} \mu (\ell )^2 \sum _{\ell \in L^+} \rho (\ell )^2. \end{aligned}$$

Note that $\sum _{\ell \in \mathcal B(\mathcal P)} \mu (\ell )^2 = \Theta (\mathcal E(\mathcal P))$. Since $M = O(n^{1/4}) = O(n^{2/3-\varepsilon })$, Theorem 2.1 implies $\sum _{\ell \in \mathcal B(\mathcal P)} \mu (\ell )^2 = O(M^{2/5}n^{12/5+\varepsilon })$. We can bound $\sum \rho (\ell )^2$ using the assumption that no line contains more than M points, so

$$\begin{aligned} K^2 n^4 = O(M^{\frac{2}{5}}n^{\frac{12}{5}+\varepsilon }\cdot M^2 |L^+|), \end{aligned}$$

and hence

$$\begin{aligned} |L^+| = \Omega (K^2 n^{\frac{8}{5} - \varepsilon } M^{-\frac{12}{5}}). \end{aligned}$$

Since $K = O(\log n)$, the factor K can be absorbed into the factor $n^{-\varepsilon }$ in the final bound. $\square$

Remark

Notice that the proof of Theorem 5.1 also applies when $M(n)= \Omega (n^{1/4})$. However, this would lead to a bound for the number of lines in (ii) that is weaker than the bound that is implied by Theorem 1.1.

6 Proof of Theorem 2.5

We now present the proof of the incidence bound that we use. As mentioned in the introduction, this proof is essentially from [11]; we reproduce it here to determine the dependence on the parameter t. We refer to [11] for the definitions used here. We prove a more general version than we need, since it seems to come at no extra cost, and may be useful elsewhere.

The proof uses the Kővári–Sós–Turán theorem (see for example [2, Thm. IV.9]).

Lemma 6.1

(Kővári–Sós–Turán) Let G be a bipartite graph with vertex set $A\cup B$. Let $s\le t$. Suppose that G contains no $K_{s,t}$; that is, for any s vertices in A, at most $t-1$ vertices in B are connected to each of the s vertices. Then

$$\begin{aligned} |E(G)| = O(t^{\frac{1}{s}}|A||B|^{\frac{s-1}{s}}+|B|). \end{aligned}$$

We amplify the weak bound of Lemma 6.1 by using polynomial partitioning. Given a polynomial $f \in \mathbb R[x_1,\ldots , x_d]$, we write $Z(f) = \{ p \in \mathbb R^d : f(p)=0 \}$. We say that $f \in \mathbb R[x_1,\ldots , x_d]$ is an r-partitioning polynomial for a finite set $\mathcal P\subset \mathbb R^d$ if no connected component of $\mathbb R^d \backslash Z(f)$ contains more than $|\mathcal P|/r$ points of $\mathcal P$ (notice that there is no restriction on the number of points of $\mathcal P$ that are in Z(f)). Guth and Katz [13] introduced this notion and proved that for every $\mathcal P\subset \mathbb R^d$ and $1\le r \le |\mathcal P|$, there exists an r-partitioning polynomial of degree $O(r^{1/d})$. In [11], the following generalization was proved.

Theorem 6.2

(Partitioning on a variety) Let V be an irreducible variety in $\mathbb R^d$ of dimension e and degree D. Then for every finite $\mathcal P\subset V$ there exists an r-partitioning polynomial f of degree $O(r^{1/e})$ such that $V\not \subset Z(f)$. The implicit constant depends only on d and D.

We are now ready to prove our incidence bound. For the convenience of the reader, we first repeat the statement of the theorem.

Theorem 2.5. Let $\mathcal S$ be a set of n constant-degree varieties and let $\mathcal P$ be a set of m points, both in $\mathbb R^d$, such that the incidence graph of $\mathcal P\times \mathcal S$ contains no copy of $K_{s,t}$ (where s is a constant, but t may depend on m, n). Moreover, suppose that $\mathcal P\subset V$, where V is an irreducible constant-degree variety of dimension e. Then

$$\begin{aligned} I(\mathcal P,\mathcal S) = O\big (m^{\frac{s(e-1)}{es-1}+\varepsilon }n^{\frac{e(s-1)}{es-1}}t^{\frac{e-1}{es-1}} +tm+n\big ). \end{aligned}$$

Proof

Note that we may assume that no variety in $\mathcal S$ contains V. Indeed, we can assume that V contains at least s points (otherwise the bound in the theorem is trivial), so the fact that the incidence graph contains no $K_{s,t}$ implies that there are at most $t-1$ varieties in $\mathcal S$ that contain V. These at most $t-1$ varieties give altogether less than tm incidences, so they are accounted for in the bound.

We use induction on e and m, with the induction claim being that for $\mathcal P,\mathcal S,V$ as in the theorem, with the added condition that no variety in $\mathcal S$ contains V, we have

$$\begin{aligned} I(\mathcal P,\mathcal S) \le \alpha _{1,e} m^{\frac{s(e-1)}{es-1}+\varepsilon }n^{\frac{e(s-1)}{es-1}}t^{\frac{e-1}{es-1}}+\alpha _{2,e}(tm+n), \end{aligned}$$

(6)

for constants $\alpha _{1,e},\alpha _{2,e}$ depending only on $d,e,s,\varepsilon$, the degree of V, and the degrees of the varieties in $\mathcal S$. The base cases for the induction are simple. If m is sufficiently small, then (6) follows immediately by choosing sufficiently large values for $\alpha _{1,e}$ and $\alpha _{2,e}$. Similarly, when $e=0$, we again obtain (6) when $\alpha _{1,e}$ and $\alpha _{2,e}$ are sufficiently large (as a function of d and the degree of V).

The constants $d,e,s,\varepsilon$ are given and thus fixed, as are the degree of V and the degrees of the varieties in $\mathcal S$. The other constants are to be chosen, and the dependencies between them are

$$\begin{aligned} C_\text {weak}, {C_\text {part}},{C_\text {inter}}\ll {C_\text {cells}}\ll {C_\mathrm{H\ddot{o}ld}}\ll r \ll {C_\text {comps}}\ll \alpha _{2,e} \ll \alpha _{1,e}, \end{aligned}$$

where $C\ll C'$ means that $C'$ is to be chosen sufficiently large compared to C; in particular, C should be chosen before $C'$. Furthermore, the constants $\alpha _{1,e},\alpha _{2,e}$ depend on $\alpha _{1,e-1},\alpha _{2,e-1}$.

By Lemma 6.1, there exists a constant $C_\text {weak}$ depending on d, s such that

$$\begin{aligned} I(\mathcal P,\mathcal S)\le C_\text {weak}\big (mn^{1-\frac{1}{s}}t^{\frac{1}{s}}+n\big ). \end{aligned}$$

When $m\le (n/t)^{1/s}$, and $\alpha _{2,e}$ is sufficiently large, we have $I(\mathcal P,\mathcal S) \le \alpha _{2,e} n$. Therefore, in the remainder of the proof we can assume that $n < m^st$, which implies

$$\begin{aligned} n = n^{\frac{e-1}{es-1}} n^{\frac{e(s-1)}{es-1}} \le m^{\frac{s(e-1)}{es-1}} n^{\frac{e(s-1)}{es-1}}t^{\frac{(e-1)}{es-1}}. \end{aligned}$$

(7)

Partitioning By Theorem 6.2, there exists an r-partitioning polynomial f with respect to V of degree at most ${C_\text {part}}\cdot r^{1/e}$, for a constant ${C_\text {part}}$. Denote the cells of $V\backslash Z(f)$ as $\Omega _1, \ldots , \Omega _N$. Since we are working over the reals, there exists a constant-degree polynomial g such that $Z(g)=V$. Then, by [24, Theorem A.2], the number of cells is bounded by $C \cdot \deg (f)^{\dim V}={C_\text {cells}}\cdot r$, for some constant ${C_\text {cells}}$ depending on ${C_\text {part}}$.

We partition $I(\mathcal P,\mathcal S)$ into the following three subsets:

• $I_1$ consists of the incidences $(p,S) \in \mathcal P\times \mathcal S$ such that $p\in V \cap Z(f)$, and some irreducible component of $V \cap Z(f)$ contains p and is fully contained in S.

• $I_2$ consists of the incidences $(p,S) \in \mathcal P\times \mathcal S$ such that $p\in V \cap Z(f)$, and no irreducible component of $V\cap Z(f)$ that contains p is contained in S.

• $I_3 = I(\mathcal P,\mathcal S) \backslash (I_1\cup I_2)$, the set of incidences $(p,S) \in \mathcal P\times \mathcal S$ such that p is not contained in $V \cap Z(f)$.

Note that we indeed have $I(\mathcal P,\mathcal S) = |I_1| + |I_2|+|I_3|$.

Bounding $|I_1|$ The points of $\mathcal P\subset \mathbb R^d$ that participate in incidences of $I_1$ are all contained in the variety $V_0 =V \cap Z(f)$. Set $\mathcal P_0=\mathcal P\cap V_0$ and $m_0 = |\mathcal P_0|$. Since V is an irreducible variety and $V\not \subset Z(f)$, $V_0$ is a variety of dimension at most $e-1$ and of degree that depends on r. By [24, Lem. 4.3], the intersection $V_0$ is a union of ${C_\text {comps}}$ irreducible components, where ${C_\text {comps}}$ is a constant depending on r and d.³ The degrees of these components also depend only on these values (for a proper definition of degrees and further discussion, see for instance [11]).

Consider an irreducible component W of $V_0$. If W contains at most $s-1$ points of $\mathcal P_0$, it yields at most $(s-1)n$ incidences. Otherwise, since the incidence graph contains no $K_{s,t}$, there are at most $t-1$ varieties of $\mathcal S$ that fully contain W, yielding at most $(t-1)m_0$ incidences. By summing up, choosing sufficiently large $\alpha _{1,e},\alpha _{2,e}$, and applying (7), we have

$$\begin{aligned} |I_1| \le {C_\text {comps}}\left( sn + tm_0 \right)< \frac{\alpha _{2,e}}{2}(n+tm_0) < \frac{\alpha _{1,e}}{4}m^{\frac{s(e-1)}{es-1}} n^{\frac{e(s-1)}{es-1}}t^{\frac{(e-1)}{es-1}} + \frac{\alpha _{2,e}}{2}tm_0. \end{aligned}$$

(8)

Bounding $|I_2|$ The points that participate in $I_2$ lie in $V_0=V\cap Z(f)$, and the varieties that participate do not contain any component of $V_0$. Because $V_0$ has dimension at most $e-1$, we can apply the induction claim on each irreducible component W of $V_0$, for the point set $\mathcal P\cap W$ and the set of varieties in $\mathcal S$ that do not contain W. Since $V_0$ has ${C_\text {comps}}$ irreducible components, we get

$$\begin{aligned} |I_2| \le {C_\text {comps}}\alpha _{1,e-1} m_0^{\frac{s(e-2)}{(e-1)s-1}+\varepsilon }n^{\frac{(e-1)(s-1)}{(e-1)s-1}}t^{\frac{e-2}{(e-1)s-1}}+ \alpha _{2,e-1}(tm_0+n), \end{aligned}$$

with $\alpha _{1,e-1}$ and $\alpha _{2,e-1}$ depending on the degree of the irreducible component of $V_0$, which in turn depends on r. Recalling that we may assume $n<m^st$, we obtain

$$\begin{aligned} m^{\frac{s(e-2)}{(e-1)s-1}+\varepsilon }n^{\frac{(e-1)(s-1)}{(e-1)s-1}}t^{\frac{e-2}{(e-1)s-1}}&= m^{\frac{s(e-2)}{(e-1)s-1}+\varepsilon }n^{\frac{e(s-1)}{es-1}}n^{\frac{s-1}{(es-s-1)(es-1)}}t^{\frac{e-2}{(e-1)s-1}} \\&< m^{\frac{s(e-1)}{es-1}+\varepsilon }n^{\frac{e(s-1)}{es-1}}t^{\frac{e-1}{es-1}}. \end{aligned}$$

By applying (7) to remove the term $\alpha _{2,e-1} n$, and by choosing $\alpha _{1,e}$ and $\alpha _{2,e}$ sufficiently large as a function of ${C_\text {comps}},\alpha _{1,e-1},\alpha _{2,e-1}$, we obtain

$$\begin{aligned} |I_2| \le \frac{\alpha _{1,e}}{4} m^{\frac{s(e-1)}{es-1}+\varepsilon }n^{\frac{e(s-1)}{es-1}}t^{\frac{e-1}{es-1}}+\frac{\alpha _{2,e}}{2}tm_0. \end{aligned}$$

(9)

Bounding $|I_3|$ For every $1 \le i \le N$, we set $\mathcal P_i = \mathcal P\cap \Omega _i$ and denote by $\mathcal S_i$ the set of varieties of $\mathcal S$ that intersect the cell $\Omega _i$. We also set $m_i=|P_i|$ and $n_i=|\mathcal S_i|$. Then we have $m_i \le m/r$ and $\sum _{i=1}^N m_i = m-m_0$.

Let $S\in \mathcal S$. By the assumption made at the beginning of the proof, S does not contain V, so $S\cap V$ is a subvariety of V of dimension at most $e-1$. By [24, Thm. A.2], there exists a constant ${C_\text {inter}}$ such that the number of cells intersected by $S\cap V$ is at most $C \cdot \deg (f)^{\dim (S\cap V)} = {C_\text {inter}}\cdot r^{(e-1)/e}$. This implies that

$$\begin{aligned} \sum _{i=1}^N n_i \le {C_\text {inter}}\cdot r^{\frac{e-1}{e}}\cdot n. \end{aligned}$$

By Hölder’s inequality we have

$$\begin{aligned} \sum _{i=1}^N n_i^{\frac{e(s-1)}{es-1}}&\le \Big (\sum _{i=1}^N n_i\Big )^{\frac{e(s-1)}{es-1}} \Big (\sum _{i=1}^N 1\Big )^{\frac{e-1}{es-1}} \\&\le \big ({C_\text {inter}}r^{(e-1)/e} n\big )^{\frac{e(s-1)}{es-1}}({C_\text {cells}}r)^{\frac{e-1}{es-1}} \\&\le {C_\mathrm{H\ddot{o}ld}}r^{\frac{(e-1)s}{es-1}} n^{\frac{e(s-1)}{es-1}}, \end{aligned}$$

where ${C_\mathrm{H\ddot{o}ld}}$ depends on ${C_\text {inter}},{C_\text {cells}}$. Using the induction claim for each i with the point set $\mathcal P_i$, the set of varieties $\mathcal S_i$, and the same variety V, we obtain

$$\begin{aligned} \sum _{i=1}^N I(\mathcal P_i,\mathcal S_i)&\le \sum _{i=1}^N \big (\alpha _{1,e} m_i^{\frac{(e-1)s}{es-1}+\varepsilon }n_i^{\frac{e(s-1)}{es-1}}t^{\frac{(e-1)}{es-1}}+\alpha _{2,e}(tm_i+n_i)\big ) \\&\le \alpha _{1,e} \frac{m^{\frac{(e-1)s}{es-1}+\varepsilon }t^{\frac{(e-1)}{es-1}}}{r^{\frac{(e-1)s}{es-1}+\varepsilon }} \sum _{i=1}^N n_i^{\frac{e(s-1)}{es-1}} + \sum _{i=1}^N\alpha _{2,e}(tm_i+n_i) \\&\le \alpha _{1,e} {C_\mathrm{H\ddot{o}ld}}\frac{m^{\frac{(e-1)s}{es-1}+\varepsilon }n^{\frac{e(s-1)}{es-1}}t^{\frac{(e-1)}{es-1}}}{r^{\varepsilon }} + \alpha _{2,e}\big (t(m-m_0)+ {C_\text {inter}}r^{\frac{e-1}{e}}n\big ). \end{aligned}$$

By choosing $\alpha _{1,e}$ sufficiently large with respect to ${C_\text {inter}},r,\alpha _{2,e}$, and using (7), we get

$$\begin{aligned} \sum _{i=1}^N I(\mathcal P_i,\mathcal S_i) \le 2\alpha _{1,e} {C_\mathrm{H\ddot{o}ld}}\frac{m^{\frac{(e-1)s}{es-1}+\varepsilon }n^{\frac{e(s-1)}{es-1}}s^{\frac{(e-1)}{es-1}}}{r^{\varepsilon }} + \alpha _{2,e}t(m-m_0). \end{aligned}$$

Finally, choosing r sufficiently large with respect to ${C_\mathrm{H\ddot{o}ld}}$ gives

$$\begin{aligned} |I_3| = \sum _{i=1}^N I(\mathcal P_i,\mathcal S_i) \le \frac{\alpha _{1,e}}{2} m^{\frac{(e-1)s}{es-1}+\varepsilon }n^{\frac{e(s-1)}{es-1}}t^{\frac{(e-1)}{es-1}} + \alpha _{2,e}t(m-m_0). \end{aligned}$$

(10)

Summing Up By combining $I(\mathcal P,\mathcal S) = |I_1| + |I_2|+|I_3|$ with (8), (9), and (10), we obtain

$$\begin{aligned} I(\mathcal P,\mathcal S) \le \alpha _{1,e} m^{\frac{s(e-1)}{es-1}+\varepsilon }n^{\frac{e(s-1)}{es-1}}t^{\frac{(e-1)}{es-1}}+\alpha _{2,e}(tm+n), \end{aligned}$$

which completes the induction step and the proof of the theorem. $\square$