# 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.

Consider a $\sqrt{n}\times\sqrt{n}$ integer grid ${\cal G}$ in ${\mathbb R}^2$. It is easy to prove that any constant-degree algebraic curve passes through $O(\sqrt{n})$ points of ${\cal G}$. This bound is tight, since a line can pass through $\Theta(\sqrt{n})$ points of ${\cal G}$. Somewhat surprisingly, every other constant-degree algebraic curve passes through an asymptotically smaller number of grid points.
Lemma 1. Let ${\cal G}$ be a $\sqrt{n}\times\sqrt{n}$ integer grid in ${\mathbb R}^2$.
(a) Let $C$ be a constant-degree algebraic curve which is not a line. Then $C$ contains $o(\sqrt{n})$ points of ${\cal G}$ (recall that little-$o()$ notation implies asymptotically smaller).
(b) Let $C$ be a strictly convex curve (not necessarily algebraic). Then $C$ contains $O(n^{1/3})$ points of ${\cal G}$.