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.