We finished our IPAM semester with a workshop at lake arrowhead. You can find our “graduation pictures” at the IPAM facebook page (just don’t look at my horrible picture…). In honor of this amazing semester, here are some pictures that I have from it. If you have other nice pictures, you’re welcome to send them to me and I’ll place them here.
If you have been following this blog for a while, you might have noticed that I have been slowly surveying the various open problems that are related to distinct distances, and the best known bounds for them. I think that my survey is now in a decent shape, so I uploaded it on arXiv.
For this occasion, I wish to mention an open problem concerning surfaces in . It is far from being one of the main problems of this subfield. However, since currently no non-trivial bounds are known for it, it seems like a good problem for a student or for someone who wishes to start working on distinct distances problems.
Recall that in bipartite distinct distances problems we have two sets of points and , and are interested only in distinct distances that are spanned by pairs of (i.e., distances between points from different sets). For simplicity, in this post we assume that both sets are of cardinality . One example of such a result, by Pach and de Zeeuw, is that if each of the two point sets is on a planar curve that contains no lines or circles, then the number of distinct distances between and is
In , the similar (yet non-bipartite) case where one point set is placed a curve was studied by Charalambides and by Raz, Sharir, and Solymosi. However, nothing non-trivial is known for point sets on two-dimensional surfaces. That is, consider, in , the minimum number of distinct distances between a set of points on a two-dimensional surface , and a set of points on a two-dimensional surface .
Before we properly formulate any questions for this scenario, let us first consider some examples. First, consider the case where and are non-parallel planes in . In this case there exist two orthogonal lines such that , , and is a point on . We can place the two sets of points on such that the number of distinct distances between the two sets is (e.g., see Section 3 of the survey). The same bound can be obtained between two spheres and between a sphere and a plane (in both cases by placing the points on two parallel circles).
A slightly better bound can be obtained in the case where and are parallel planes. In this case we can place a subset of the integer lattice on each of the planes. For example, we may assume that the planes are defined by and , and that the points of the two sets are
A variant of Erdős’ analysis of the planar lattice (e.g., see Section 2 of the survey) implies that the number of distinct distances between the two sets is .
Unlike the planar case, it is not immediately clear whether the above examples are tight. For example, the integer lattice determines only distinct distances. This leads to the following conjecture.
Conjecture. Given a set of points on a two-dimensional surface , and a set of points on a two-dimensional surface , both in , the number of distinct distances between the two sets is (or at least ?).
Assuming that the conjecture is true, we have the following natural question.
Problem. Characterize which pairs of surfaces can yield distinct distances. Moreover, provide a lower bound for the minimum number of distinct distances for the case of any other pair of surfaces.
This problem formulation is motivated by aforementioned result of Pach and de Zeeuw for the case of points on two planar curves, where the only “exceptional” cases are when the two curves contain parallel lines or concentric circles, and then the number of distinct distances can be . For any other pair of curves, the number of distinct distances is .
This is the first in a new series of posts, in which I will survey the constructions leading to the best known lower bounds for the various incidence problems. Although recently many improved upper bounds for incidence problems were proven, not much progress was made concerning the lower bounds.
We begin with the case of point-line incidences in the plane. This is of course the matching lower bound for the famous Szemerédi–Trotter Theorem.
Theorem 1 (Szemerédi and Trotter). The maximum number of incidences between a set of points and a set of lines, both in , is
Notice that the linear terms dominate this bound when either or . Since a point-line configuration with incidences is easy to construct, we focus on obtaining incidences when .
Today the “common” construction for the planar point-line incidence bound is by Elekes. Elekes’ construction will be described in the next post of the series. Before that, in this post we present the original construction of Erdős. While this construction is mentioned in several places (e.g., see here), I could not locate the original paper that describes it. Many years later Edelsbrunner and Welzl rediscovered this construction.
Pach and Tóth use a variant of this construction to obtain the best known constant for the lower bound for the maximum number of point-line incidences. Specifically,
Recall that our goal is to construct a set of points and a set of lines, for any . Specifically, we assume that for a sufficiently large constant whose value will be determined below. As our point set, we take the following subset of the integer lattice.
Given a pair of relatively prime integers , we define the line set:
Notice that . Our set of lines is the union of many sets of the form . Specifically, we set (for a constant that will be set below) and
The resulting point-line configuration is depicted in the following figure.