A while ago, I had a post about lower bounding the minimum number of distinct distances between points on two lines in . 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 . 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 of points on a line , and a set of points on a line (such that and are distinct) and let denote the number of distinct distances between pairs of points from . Consider first the “balanced” case, where . When the two lines are parallel or orthogonal, the points can be arranged so that . For example, see the following figure.
Purdy conjectured that if the lines are neither parallel nor orthogonal then . 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 for some . Elekes derived the improved and concrete bound (when the lines are neither parallel nor orthogonal) and gave a construction, reminiscent of the one by Erdős, with , in which the angle between the two lines is . The unbalanced case, where , 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 and , for any .
Our result, taken from this paper is:
Theorem 1. Let and be two sets of points in of cardinalities and , respectively, such that the points of all lie on a line , the points of all lie on a line and the two lines are neither parallel nor orthogonal. Then
Notice that Theorem 1 immediately improves Elekes’s lower bound from to . Moreover, the theorem is a generalization of the aformentioned bound by Schwartz, Solymosi, and de Zeeuw.
Proof. We rotate the plane so that becomes the -axis and translate the plane so that is the origin. Let denote the slope of after the rotation. We set and denote the distinct distances in as . For a pair of points and , we denote by the (Euclidean) length of the straight segment . Let be the set of quadruples where and , such that and (the two segments are allowed to share at most one endpoint). The quadruples are ordered, so that and are considered as two distinct elements of . The following figure depicts a valid quadruple .
Let , for . We have, by the Cauchy-Schwarz inequality,
In the remainder of the proof we derive an upper bound on , showing that . This, combined with , yields the lower bound asserted in the theorem.
Consider a quadruple where and . Write , and . Recall that this quadruple is in if and only if , or
We apply a reduction to a parametric plane. For every pair of points , we define a corresponding point . We denote the set of these points as . For every pair of points , we define a corresponding hyperbola given by the equation
We denote the set of these hyperbolas as . Notice that is satisfied if and only if the point is incident to the hyperbola . That is, to upper bound , it suffices to upper bound the number of incidences in .
It can be easily verified that, since , no hyperbola in is degenerate (i.e., the product of two lines). Moreover, the same hyperbola of cannot be obtained by two different pairs of points .
By definition, two (non-degenerate) hyperbolas intersect in at most four points. That is, any pair of hyperbolas from can be incident to at most four common points from . Moreover, the roles of and (and of and ) are fully symmetric, and can be interchanged, by regarding the pairs of distinct points in (resp., ) as a set of points in the plane (resp., as a set of hyperbolas , defined in a fully symmetric manner). This implies, in particular, that there are at most four hyperbolas of that pass through a given pair of points in . We can thus apply an incidence bound of Pach and Sharir.
Theorem 2 (Pach and Sharir `98). Consider a point set , a set of simple curves , both in , and two constant positive integers and , such that
- For every points of there are at most curves of that are incident to each of the points.
- Every two curves of intersect in at most points.
We can apply Theorem 2 on with and , to obtain
Combining this bound with the lower bound in implies the assertion of the theorem.