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.

Advertisements

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…

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.

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…

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.

Pingback: Recent Results (Feb `14) | Some Plane Truths

Pingback: Incidences and the Sum-Product Problem | Some Plane Truths