# The Elekes-Sharir Framework (part 3)

In the previous posts of this series (part 1 and part 2), we discussed the history of the Elekes-Sharir reduction, the basic technical details, and applied the reduction to reprove a result of Szemerédi. In this post, the third and final one of the series, we present another application of the reduction.

Let ${\cal P}_1$ (resp., ${\cal P}_2$) be a sets of $m$ (resp., $n$) points, all on a common line $\ell_1$ (resp., $\ell_2$). Let $D({\cal P}_1,{\cal P}_2)$ denote the number of distinct distances between the pairs of ${\cal P}_1\times{\cal P}_2$ (that is, only distinct distances between points on different lines are considered). There exist configurations where $\ell_1$ and $\ell_2$ are either parallel or orthogonal and $D_{\text{lines}}({\cal P}_1,{\cal P}_2) = \Theta(\max\{m,n\})$. For example, see the following figure.

The case where $\ell_1$ and $\ell_2$ are neither parallel nor orthogonal is more difficult and has prompted various works in the past 15 years (see Elekes and Rónyai, Elekes, Schwartz, Solymosi, and de Zeeuw, and Sharir, Sheffer, and Solymosi). Let $D_{\text{lines}}(m,n)$ denote the minimum number of distinct distances in such a scenario. Elekes observed the subquadratic upper bound $D_{\text{lines}}(m,n) = O(\max\{n^2/\log n, m^2/\log m\})$. The best known lower bound $D_{\text{lines}}(m,n)=\Omega\left( \min\left\{m^{2/3}n^{2/3},m^2,n^2 \right\}\right)$ was recently derived by Sharir, Sheffer, and Solymosi). Notice the large gap between the two bounds — one of the largest among the variants of the distinct distances problem.

We now explain how to derive the lower bound of Sharir, Sheffer, and Solymosi by applying the Elekes-Sharir framework. Recently, we learned that this proof can be slightly simplified by removing the use of the framework from it (see here for more details).

Theorem. (Sharir, Sheffer, and Solymosi)

$D_{\text{lines}}(m,n)=\Omega\left( \min\left\{m^{2/3}n^{2/3},m^2,n^2 \right\}\right).$

Proof.     Consider a set ${\cal P}_1$ of $m$ points (resp., a set ${\cal P}_2$ of $n$ points), all on a common line $\ell_1$ (resp., $\ell_2$). Additionally, the lines $\ell_1$ an $\ell_2$ are neither parallel nor orthogonal. We set $x=D({\cal P}_1,{\cal P}_2)$ and denote the $x$ distinct distances in ${\cal P}_1\times{\cal P}_2$ as $\delta_1,\ldots, \delta_x$. We apply the Elekes-Sharir framework with a small change. This time, we define

$Q =\left\{ (a,p,b,q) \mid a,b\in{\cal P}_1, \quad p,q\in{\cal P}_2, \quad \text{and}\quad |ap|=|bq|>0 \right\}$

($Q$ does not include quadruples of the form $(a,p,a,p)$). As before, we begin by deriving a lower bound on $|Q|$. Let $E_i = \{(a,p)\in {\cal P}_1 \times {\cal P}_2 \mid |ap|=\delta_i \}$, for $i=1,\ldots,x$. Notice that $\sum_{i=1}^x |E_i| = mn$. By the Cauchy-Schwarz inequality, we have

$|Q| = 2\sum_{i=1}^x\binom{|E_i|}{2} \ge \sum_{i=1}^x \left(|E_i|-1 \right)^2$ $\ge \frac{1}{x}\left(\sum_{i=1}^x (|E_i|-1) \right)^2 = \frac{\left(mn -x\right)^2}{x}. \ \ \ \ (1)$

Next, we upper bound $|Q|$. In this case, no quadruple in $Q$ can correspond to a translation, so it suffices to bound the number of quadruples that correspond to a rotation. That is, we consider quadruples $(a,p,b,q)\in Q$ such that there exists a rotation taking $a$ to $b$ and $p$ to $dq$. For example, see the following figure.

For every pair of points $a,b\in {\cal P}_1$, we say that $\ell_{ab}$ is a blue line (recall the definition of $\ell_{ab}$ from the first post of the series) and for every pair of points $p,q\in {\cal P}_2$, we say that $\ell_{pq}$ is a red line. Notice that the quadruple $(a,p,b,q) \in ({\cal P}_1\times{\cal P}_2)^2$ is in $Q$ if and only if the lines $\ell_{ab}$ and $\ell_{pq}$ intersect. That is, in this case we have $m(m-1)$ blue lines and $n(n-1)$ red lines, and there is a bijection between the quadruples of $Q$ and the set of red-blue intersections.

It seems unlikely that a meaningful bound on the number of red-blue intersections can be obtained without any additional information about the lines. Fortunately, these lines are very restricted. Recall that the projection of a line $\ell_{ab}$ on the $xy$-plane is the perpendicular bisector of the segment $ab$. The projections of all of the blue lines on the $xy$-plane are orthogonal to $\ell_1$ and are thus parallel to each other (and the same holds for the red lines and $\ell_2$). Moreover, two quadruples in $Q$ cannot correspond to the same rotation; this is almost immediate from the fact that any rotation with an origin not on $\ell_1$ can take at most one point of $\ell_1$ to a point of $\ell_1$. It is not difficult to find other restrictions on these lines, such as that all the blue lines intersect the instance of $\ell_1$ on the $xy$-plane, and that all the red lines intersect the instance of $\ell_2$ on the $xy$-plane. Such a configuration is depicted in the following figure.

To simplify the analysis, we rotate and translate the plane so that $\ell_1$ becomes the $x$-axis and $\ell_1 \cap \ell_2$ becomes the origin $(0,0)$. This transformation does not have any effect on $D({\cal P}_1,{\cal P}_2)$. Let $s$ denote the slope of $\ell_2$ after the rotation. Since $\ell_1$ and $\ell_2$ are neither parallel nor orthogonal, $s$ is finite and nonzero. For $a,b\in{\cal P}_1$ and $p,q\in{\cal P}_2$ we have (recalling the line equations from the first post)

$\ell_{ab} = \left(\frac{a_x+b_x}{2}, t\cdot\frac{a_x-b_x}{2},t\right), \quad \text{ for } t\in{\mathbb R}, \quad \text{and}$ $\ell_{pq} = \left(\frac{(p_x+q_x)+t's(q_x-p_x)}{2}, \frac{s(p_x+q_x)+t'(p_x-q_x)}{2},0\right), \quad \text{ for } t'\in{\mathbb R}.$

To simplify these equations, we set $\phi_{ab} = \frac{a_x+b_x}{2}$ and $\mu_{ab} = \frac{a_x-b_x}{2}$. We can now write

$\ell_{ab} = \left(\phi_{ab}, t\mu_{ab},t\right), \quad \text{ for } t\in{\mathbb R}, \quad \text{and}$ $\ell_{pq} = \left(\phi_{pq}-t's\mu_{pq}, s\phi_{pq}+t'\mu_{pq},t'\right), \quad \text{ for } t'\in{\mathbb R}.$

The quadruple $(a,p,b,q)$ is in $Q$ if and only if $\ell_{ab}$ and $\ell_{pq}$ intersect; that is, if there is a solution to the system

$\phi_{ab} = \phi_{pq}-ts\mu_{pq},$
$t\cdot\mu_{ab} = s\phi_{pq}+t\mu_{pq}.$

If we ignore the cases where $\mu_{pq}=0$ and/or $\mu_{ab}-\mu_{pq}=0$ (which are easy to handle), then by eliminating $t$ we get that $(a,p,b,q)$ is in $Q$ if and only if

$\frac{\phi_{pq}-\phi_{ab}}{s\mu_{pq}} = \frac{s\phi_{pq}}{\mu_{ab}-\mu_{pq}},$

or

$(\phi_{pq}-\phi_{ab})(\mu_{ab}-\mu_{pq}) = s^2\mu_{pq}\phi_{pq}. \ \ \ \ (2)$

To get a bound on the number of pairwise intersecting lines (pairs for which $(2)$ holds), we apply a second reduction, this time to a parametric plane. For every pair of points $p,q\in {\cal P}_2$, which define the red line $\ell_{pq}$, we define a corresponding point $(\phi_{pq},\mu_{pq})\in{\mathbb R}^2$. For every pair of points $a,b\in {\cal P}_1$, which define the blue line $\ell_{ab}$, we define a corresponding hyperbola

$\gamma_{ab} = (x-\phi_{ab})(\mu_{ab}-y) - s^2xy.$

Notice that $\gamma_{ab}$ is incident to $(\phi_{pq},\mu_{pq})$ if and only if $(2)$ holds, so the quadruple $(a,p,b,q)$ is in $Q$ if and only if $\gamma_{ab}$ is incident to $(\phi_{pq},\mu_{pq})$. That is, to upper bound $|Q|$, it suffices to upper bound the number of incidences between a set $\cal H$ of $\Theta(m^2)$ hyperbolas and a set ${\cal P}'$ of $\Theta(n^2)$ points, both in ${\mathbb R}^2$. With the existing tools for solving incidence problems, it appears hard to obtain a good bound on the number of point-hyperbola incidences. Fortunately, the point-hyperbola configuration that we have is degenerate.

By definition, two hyperbolas intersect in at most four points. That is, any pair of hyperbolas from $\cal H$ can be incident to at most four common points from ${\cal P}'$. Moreover, the roles of $\ell_1$ and $\ell_2$ (and of ${\cal P}_1$ and ${\cal P}_2$) are fully symmetric, and can be interchanged, by regarding the pairs of distinct points in ${\cal P}_1^2$ (resp., ${\cal P}_1^2$) as a set of points $(a,b)$ in the plane (resp., as a set of hyperbolas $\gamma_{p,q}$, defined in a fully symmetric manner). This implies, in particular, that there are at most four hyperbolas of $\cal H$ that pass through a given pair of points in ${\cal P}'$. According to a result by Pach an Sharir, the number of point-hyperbola incidences with such a restriction is $O(|{\cal P}'|^{2/3}|{\cal H}|^{2/3} + |{\cal P}'| + |{\cal H}|)$. Thus, we have

$|Q| = O(|{\cal P}'|^{2/3}|{\cal H}|^{2/3} + |{\cal P}'| + |{\cal H}|) = O(m^{4/3}n^{4/3} + m^2 + n^2).$

Combining this bound with the lower bound in $(1)$ implies the assertion of the theorem.     $\Box$