# The Partial Elekes-Sharir Framework

A while ago, I had a post about lower bounding the minimum number of distinct distances between points on two lines in ${\mathbb R}^2$. That post showed how such an upper bound can be obtained by applying the Elekes-Sharir framework (a pdf file of my guide to the Elekes-Sharir framework can be found here). Since then, we noticed that a much simpler technique can be used to obtain the same bound. I like to call this simpler technique the partial Elekes-Sharir framework since the analysis starts in the same way, but the more technical parts of the original framework are replaced with a simpler analysis. More specifically, the partial framework leads to a planar incidence problem, instead of to one in ${\mathbb R}^3$. Since Micha Sharir, József Solymosi, and myself introduced this idea in the spring of 2013 (later on, we discovered that a similar idea was also used by Elekes and Szabó), it was applied and extended in a few additional papers (see here, here, and here). Moreover, I know of at least a couple of additional manuscripts that apply the same ideas for problems not directly involving distinct distances.

The purpose of this post is to present the partial Elekes-Sharir framework, by applying it to obtain a bound for the problem concerning distinct distances on two lines. First, we recall the problem.

Consider a set ${\cal P}_1$ of $n$ points on a line $\ell_1$, and a set ${\cal P}_2$ of $n$ points on a line $\ell_2$ (such that $\ell_1$ and $\ell_2$ are distinct) and let $D({\cal P}_1,{\cal P}_2)$ denote the number of distinct distances between pairs of points from ${\cal P}_1\times{\cal P}_2$. Consider first the “balanced” case, where $|{\cal P}_1|=|{\cal P}_2|=n$. When the two lines are parallel or orthogonal, the points can be arranged so that $D({\cal P}_1,{\cal P}_2) = \Theta(n)$. For example, see the following figure.

Purdy conjectured that if the lines are neither parallel nor orthogonal then $D({\cal P}_1,{\cal P}_2) = \omega(n)$. Elekes and Rónyai proved that the number of distinct distances in such a scenario is indeed superlinear. They did not give an explicit bound, but a brief analysis of their proof shows that $D({\cal P}_1,{\cal P}_2) = \Omega(n^{1+\delta})$ for some $\delta>0$. Elekes derived the improved and concrete bound $D({\cal P}_1,{\cal P}_2) = \Omega(n^{5/4})$ (when the lines are neither parallel nor orthogonal) and gave a construction, reminiscent of the one by Erdős, with $D({\cal P}_1,{\cal P}_2) = O\left(n^2/\sqrt{\log n}\right)$, in which the angle between the two lines is $\pi/3$. The unbalanced case, where $|{\cal P}_1|\ne |{\cal P}_2|$, has recently been studied by Schwartz, Solymosi, and de Zeeuw, who have shown, among several other related results, that the number of distinct distances remains superlinear when $|{\cal P}_1| = n^{1/2 + \varepsilon}$ and $|{\cal P}_2| = n$, for any $\varepsilon>0$.

Our result, taken from this paper is:

Theorem 1. Let ${\cal P}_1$ and ${\cal P}_2$ be two sets of points in ${\mathbb R}^2$ of cardinalities $n$ and $m$, respectively, such that the points of ${\cal P}_1$ all lie on a line $\ell_1$, the points of ${\cal P}_2$ all lie on a line $\ell_2,$ and the two lines are neither parallel nor orthogonal. Then

$\displaystyle D({\cal P}_1,{\cal P}_2)=\Omega\left( \min\left\{n^{2/3}m^{2/3},n^2,m^2 \right\}\right)$.

Notice that Theorem 1 immediately improves Elekes’s lower bound from $\Omega(n^{5/4})$ to $\Omega(n^{4/3})$. Moreover, the theorem is a generalization of the aformentioned bound by Schwartz, Solymosi, and de Zeeuw.

Proof.     We rotate the plane so that $\ell_1$ becomes the $x$-axis and translate the plane so that $\ell_1 \cap \ell_2$ is the origin. Let $s$ denote the slope of $\ell_2$ after the rotation. We set $D=D({\cal P}_1,{\cal P}_2)$ and denote the $D$ distinct distances in ${\cal P}_1\times{\cal P}_2$ as $\delta_1,\ldots, \delta_D$. For a pair of points $u$ and $v$, we denote by $\|uv\|$ the (Euclidean) length of the straight segment $uv$. Let $Q$ be the set of quadruples $(a,p,b,q)$ where $a,b \in {\cal P}_1$ and $p,q \in {\cal P}_2$, such that $\|ap\|=\|bq\|>0$ and $ap \neq bq$ (the two segments are allowed to share at most one endpoint). The quadruples are ordered, so that $(a,p,b,q)$ and $(b,q,a,p)$ are considered as two distinct elements of $Q$. The following figure depicts a valid quadruple $(a,p,b,q)\in Q$.

Let $E_i = \{(a,p)\in {\cal P}_1 \times {\cal P}_2 \mid |ap|=\delta_i \}$, for $i=1,\ldots,D$. We have, by the Cauchy-Schwarz inequality,

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

$\displaystyle = \frac{\left(mn -D\right)^2}{D}. \qquad \qquad (1)$

In the remainder of the proof we derive an upper bound on $|Q|$, showing that $|Q|=O(m^{4/3}n^{4/3} + n^2 +m^2)$. This, combined with $(1)$, yields the lower bound asserted in the theorem.

Consider a quadruple $(a,p,b,q)$ where $a,b\in{\cal P}_1$ and $p,q\in{\cal P}_2$. Write $a=(a_x,0), b=(b_x,0),$ $p=(p_x,sp_x)$, and $q=(q_x,sq_x)$. Recall that this quadruple is in $Q$ if and only if $\|ap\|=\|bq\|$, or

$\displaystyle (a_x-p_x)^2+ s^2p_x^2 = (b_x-q_x)^2+s^2q_x^2. \qquad \qquad (2)$

We apply a reduction to a parametric plane. For every pair of points $p,q\in {\cal P}_2$, we define a corresponding point $v_{pq}=(p_x,q_x)\in{\mathbb R}^2$. We denote the set of these $\Theta(n^2)$ points as ${\cal P}'$. For every pair of points $a,b\in {\cal P}_1$, we define a corresponding hyperbola $\gamma_{ab}$ given by the equation

$\displaystyle a_x^2 - b_x^2 -2a_xx +2b_xy +x^2(1+s^2) -y^2(1+s^2) = 0.$

We denote the set of these $\Theta(n^2)$ hyperbolas as $\cal H$. Notice that $(2)$ is satisfied if and only if the point $v_{pq}$ is incident to the hyperbola $\gamma_{ab}$. That is, to upper bound $|Q|$, it suffices to upper bound the number of incidences in ${\cal P}'\times {\cal H}$.

It can be easily verified that, since $s\neq 0$, no hyperbola in ${\cal H}$ is degenerate (i.e., the product of two lines). Moreover, the same hyperbola of ${\cal H}$ cannot be obtained by two different pairs of points $a,b\in {\cal P}_1$.

By definition, two (non-degenerate) 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}_2^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}'$. We can thus apply an incidence bound of Pach and Sharir.

Theorem 2 (Pach and Sharir `98). Consider a point set $\cal P$, a set of simple curves $\Gamma$, both in ${\mathbb R}^2$, and two constant positive integers $k$ and $s$, such that
• For every $k$ points of $\cal P$ there are at most $s$ curves of $\Gamma$ that are incident to each of the $k$ points.
• Every two curves of $\Gamma$ intersect in at most $s$ points.
Then $I({\cal P},\Gamma) = O(|{\cal P}|^{k/(2k-1)}|\Gamma|^{(2k-2)/(2k-1)}+|{\cal P}|+|\Gamma|),$ where the constant of proportionality depends on $k$ and $s$.

We can apply Theorem 2 on ${\cal H} \times {\cal P}'$ with $k=2$ and $s=4$, to obtain

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

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

Advertisements

## 6 thoughts on “The Partial Elekes-Sharir Framework”

1. Frank de Zeeuw |

In my limited understanding, Elekes-Szabo used (along with a lot else) the approach that was introduced in Elekes-Ronyai (2000) and Elekes (1999), and recently used by Charalambides, as you mentioned here. I sometimes call that the “5/4 method”, to distinguish it from the “4/3 method” that you introduced with Sharir and Solymosi. Not to suggest that those are better names, just that they help to distinguish…

2. Hi Frank,

You always raise interesting issues! What I meant by saying that the Elekes-Szabo paper applies similar ideas is that it also counts quadruples, provides a lower bound for the number of quadruples by using Cauchy-Schwarz, and an upper bound by an incidence problem. If I am not mistaken, this is not the case in the other papers that you have mentioned.

• Frank de Zeeuw |

After looking at the Elekes-Szabo paper again I see that you’re right. I always thought that somewhere in there they used the “5/4 method”, but I see now that they do count quadruples, so it is more like the “4/3 method”.
I’ve always found it a very difficult paper…

3. I agree. It’s very difficult to read. I know quite a few people that tried and gave up. It would be a nice project to prepare a simplified version of it.