In the previous posts of this series (part 1 and part 2), we discussed the history of the Elekes-Sharir reduction, the basic technical details, and applied the reduction to reprove a result of Szemerédi. In this post, the third and final one of the series, we present another application of the reduction.
Let (resp., ) be a sets of (resp., ) points, all on a common line (resp., ). Let denote the number of distinct distances between the pairs of (that is, only distinct distances between points on different lines are considered). There exist configurations where and are either parallel or orthogonal and . For example, see the following figure.
The case where and are neither parallel nor orthogonal is more difficult and has prompted various works in the past 15 years (see Elekes and Rónyai, Elekes, Schwartz, Solymosi, and de Zeeuw, and Sharir, Sheffer, and Solymosi). Let denote the minimum number of distinct distances in such a scenario. Elekes observed the subquadratic upper bound . The best known lower bound was recently derived by Sharir, Sheffer, and Solymosi). Notice the large gap between the two bounds — one of the largest among the variants of the distinct distances problem.
We now explain how to derive the lower bound of Sharir, Sheffer, and Solymosi by applying the Elekes-Sharir framework. Recently, we learned that this proof can be slightly simplified by removing the use of the framework from it (see here for more details).
Theorem. (Sharir, Sheffer, and Solymosi)
Proof. Consider a set of points (resp., a set of points), all on a common line (resp., ). Additionally, the lines an are neither parallel nor orthogonal. We set and denote the distinct distances in as . We apply the Elekes-Sharir framework with a small change. This time, we define
( does not include quadruples of the form ). As before, we begin by deriving a lower bound on . Let , for . Notice that . By the Cauchy-Schwarz inequality, we have
Next, we upper bound . In this case, no quadruple in can correspond to a translation, so it suffices to bound the number of quadruples that correspond to a rotation. That is, we consider quadruples such that there exists a rotation taking to and to . For example, see the following figure.
For every pair of points , we say that is a blue line (recall the definition of from the first post of the series) and for every pair of points , we say that is a red line. Notice that the quadruple is in if and only if the lines and intersect. That is, in this case we have blue lines and red lines, and there is a bijection between the quadruples of and the set of red-blue intersections.
It seems unlikely that a meaningful bound on the number of red-blue intersections can be obtained without any additional information about the lines. Fortunately, these lines are very restricted. Recall that the projection of a line on the -plane is the perpendicular bisector of the segment . The projections of all of the blue lines on the -plane are orthogonal to and are thus parallel to each other (and the same holds for the red lines and ). Moreover, two quadruples in cannot correspond to the same rotation; this is almost immediate from the fact that any rotation with an origin not on can take at most one point of to a point of . It is not difficult to find other restrictions on these lines, such as that all the blue lines intersect the instance of on the -plane, and that all the red lines intersect the instance of on the -plane. Such a configuration is depicted in the following figure.
To simplify the analysis, we rotate and translate the plane so that becomes the -axis and becomes the origin . This transformation does not have any effect on . Let denote the slope of after the rotation. Since and are neither parallel nor orthogonal, is finite and nonzero. For and we have (recalling the line equations from the first post)
To simplify these equations, we set and . We can now write
The quadruple is in if and only if and intersect; that is, if there is a solution to the system
If we ignore the cases where and/or (which are easy to handle), then by eliminating we get that is in if and only if
To get a bound on the number of pairwise intersecting lines (pairs for which holds), we apply a second reduction, this time to a parametric plane. For every pair of points , which define the red line , we define a corresponding point . For every pair of points , which define the blue line , we define a corresponding hyperbola
Notice that is incident to if and only if holds, so the quadruple is in if and only if is incident to . That is, to upper bound , it suffices to upper bound the number of incidences between a set of hyperbolas and a set of points, both in . With the existing tools for solving incidence problems, it appears hard to obtain a good bound on the number of point-hyperbola incidences. Fortunately, the point-hyperbola configuration that we have is degenerate.
By definition, two 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 . According to a result by Pach an Sharir, the number of point-hyperbola incidences with such a restriction is . Thus, we have
Combining this bound with the lower bound in implies the assertion of the theorem.