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 isIn , 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 .

Advertisements

Hi Adam,

For two parallel planes, it seems that the conjecture follows from Guth-Katz, since in the Elekes-Sharir set up, it suffices to consider isometries that fix the planes. That is, if a,b are points in the plane z=0, and p,q are points in the plane z=1, then d(a,p)=d(b,q) IFF there exists a translation T parallel to the xy-plane and a rotation R about a vertical axis such that Ra+T=b and Rp+T=q. (Of course, more rotations could work, but this family of rotations suffices to describe congruent segments.)

There might be a way to generalize this argument to general S_1 and S_2, although it doesn’t seem completely straight forward (heuristically, if the set of transformations mapping a in S_1 to b in S_1 can be described using 4 parameters, then a transverse 3D variety (e.g. associated to pairs of points from S_2) should intersect this 4D space in a curve; 4D might suffice by an observation of Misha Rudnev, that you can match/overlay congruent line segments using a translation, followed by a rotation about the y-axis, followed by a rotation about the z-axis, similar to spherical coordinates, requiring 4 parameter if the set of translations is 2D). Although as you point out, if the planes aren’t parallel, you might expect to do better than n/log n.

Best,

Brendan

Hi Brendan,

Frank and I were playing a bit with a similar idea in IPAM. If you have two planes (not necessarily parallel), let be a rigid motion that maps to . Now, every rigid motion in that takes to can be written as composed with a rigid motion from to itself. That is, we have a three-dimensional parametrization of the relevant motions. I assume that this leads to the exact same problem as in the Guth-Katz paper, and thus to the same bound, but I never fully wrote all of the details.

Something similar can be done also for the case of two spheres, but I don’t know anything regarding any other types of surfaces.

I’m not sure that I understand your argument regarding 4d space. The general set of motions in 3d is six-dimensional, and the set of rotations taking a point a to point is three-dimensional, no? Or did you refer to some other type of parametrization?

Best,

Adam

Sorry, I think the 2nd part may be incorrect. It seems that I cannot remember Misha’s idea, but in general terms, the idea is to use a special parameterization to replace the 3D set of transformations mapping a —> b, with a 2D set of transformations in a way that is consistent for all pairs. I’ll try to get back to you with an answer.

Best,

Brendan

Thanks! I’d be interested to hear about that.

Hey Adam and Brendan,

Here is an easier way to see why Guth-Katz solves the case of two parallel planes.

Assume the planes are z=0 and z=1. Then the square of the distance between (a,b,0) and (c,d,1) is just the distance between (a,b) and (c,d) plus 1. So you may as well leave out the 1.

Best,

Frank