Distinct Distances: Open Problems and Current Bounds (part @#%)

This post surveys yet another family of variants of the distinct distances problem, for my survey of open problems and best known bounds. I think that not too many variants are still missing.

Let \phi(n,k,l)  denote the minimum number of distinct distances that are determined by a planar set \cal P  of n  points with the property that any k  points of \cal P  determine at least l  distinct distances (this notation is taken from Chapter 5 of Research Problems in discrete Geometry). That is, by having a local property of every small subset of points, we wish to obtain a global property of the entire point set. The following table lists the best known bounds for most of the problems that are discussed in this post.

Variant Lower Bound Upper Bound
\phi(n,3,2)  \Omega(n/\log n)  O(n/\sqrt{\log n})
\phi(n,3,3)  \Omega(n)  n2^{O(\sqrt{\log n})}
\phi(n,4,3)  \Omega(n/\log n)  O(n/\sqrt{\log n})
\phi(n,4,4)  \Omega(n/\log n)  n2^{O(\sqrt{\log n})}
\phi(n,4,5)  \Omega(n)  O(n^2)
\phi(n,5,9)  \Omega(n)  O(n^2)

The case of k=3

The value of \phi(n,3,2)  is the minimum number of distinct distances that are determined by a set of n  points that do not span any equilateral triangles. As discussed in a previous post in the series, Erdős noticed that a \sqrt{n}\times\sqrt{n}  integer lattice determines \Theta(n/\sqrt{\log n})  distinct distances. It is known that the points of the integer lattice do not determine any equilateral triangles, and thus \phi(n,3,2)= O(n/\sqrt{\log n})  . Guth and Katz’s bound for D(n)  (i.e., the general planar distinct distances problem) implies \phi(n,3,2)= \Omega(n/\log n)  . Thus, the best known bounds for \phi(n,3,2)  are identical to the ones for D(n)  .

Problem 1. Find the asymptotic value of \phi(n,3,2)  .

The value of \phi(n,3,3)  is the minimum number of distinct distances that are determined by a set of n  points that do not span any isosceles triangles (here and in the following cases, we also consider degenerate polygons, such as a degenerate isosceles triangle whose three vertices are collinear). Since no isosceles triangles are allowed, every point determines n-1  distinct distances with the other points of the set, and thus we have \phi(n,3,3) = \Omega(n)  . Erdős observed the following upper bound for \phi(n,3,3)  . Behrend proved that there exists a set A  of positive integers a_1<a_2<\cdots<a_n  , such that no three elements of A  determine an arithmetic progression and that a_n < n2^{O(\sqrt{\log n})}  . Therefore, the point set {\cal P}_1 = \{(a_1,0), (a_2,0),\cdots, (a_n,0)\} \subset {\mathbb R}^2  does not span an isosceles triangle. Since {\cal P}_1 \subset {\cal P}_2 = \{(1,0),(2,0),\cdots,(a_n,0) \}  and D({\cal P}_2)< n2^{O(\sqrt{\log n})}  , we have \phi(n,3,3) < n2^{O(\sqrt{\log n})}  . Erdős conjectured that \phi(n,3,3) = \omega(n)  .

Problem 2. Find the asymptotic value of \phi(n,3,3)  .

The case of k=4

The value of \phi(n,4,3)  is the minimum number of distinct distances that are determined by a set of n  points that do not span any squares. This case is somewhat similar to the one of \phi(n,3,2)  . The \sqrt{n}\times\sqrt{n}  triangular lattice determines \Theta(n/\sqrt{\log n})  distinct distances (as proved in this previous post). The triangular grid cannot contain any squares, and thus we have \phi(n,4,3) = O(n/\sqrt{\log n})  . The best known lower bound \phi(n,4,3) = \Omega(n/\log n)  is implied by Guth and Katz’s bound.

Problem 3. Find the asymptotic value of \phi(n,4,3)  .

The value of \phi(n,4,4)  is the minimum number of distinct distances that are determined by a set of n  points that do not span any Rhombuses, rectangles, or deltoids with one vertex that is equidistant to the three other three. For example, in the following figure the point p  is equidistant from the other three vertices the deltoid.

Deltoid

Dumitrescu observed that \phi(n,4,4)< n2^{O(\sqrt{\log n})}  , by using the same point set {\cal P}_1  from the analysis of \phi(n,3,3)  . Consider a subset of four points of {\cal P}_1  , as depicted in the following figure.

PointsABCD

Notice that the only pairs of segments that are allowed to have the same length (without resulting in an arithmetic progression) are |ab|=|cd|  and |ac|=|bd|  . Thus, every quadruple of points determines at least four distinct distances. No lower bound is known beyond \phi(n,4,4)=\Omega(n/\log n)  .

Problem 4. Find the asymptotic value of \phi(n,4,4)  .

Not much is known about the case of \phi(n,4,5)  . Erdős asked whether \phi(n,4,5)=\Theta(n^2)  , though the best known lower bound is only \phi(n,4,5)= \Omega(n)  . Indeed, when considering an n  point set \cal P  with this property, we notice that any circle whose center is a point of \cal P  can be incident to at most two points of \cal P  .

Problem 5. Find the asymptotic value of \phi(n,4,5)  .

Finally, we have the trivial bound \phi(n,4,6) = n(n-1)/2  , since every distance can occur at most once in this case.

The case of k=5

We do not go over all the cases of k=5  , and only mention that Erdős asked whether \phi(n,5,9)=\Omega(n^2)  . Again, nothing is known in this case beyond the trivial \phi(n,5,9)=\Omega(n)  .

Problem 6. Find the asymptotic value of \phi(n,5,9)  .

The general case

Erdős noticed that, for any k\ge 3  , we have \phi\left(n,k,\binom{k}{2}-k+3\right) = \Omega(n)  . To see why, consider a set \cal P  of n  points such that every k  -point subset of \cal P  determines at least \binom{k}{2}-k+3  distinct distances, and a point p\in{\cal P}  . If p  is the center of a circle that is incident to k-1  points of \cal P  , then together these k  points determine at most \binom{k}{2}-k+2  distinct distances, contradicting the assumption on \cap P  . Thus, the points of {\cal P}\setminus \{p\}  are contained in at least (n-1)/(k-2)  circles around p  , which in turn implies that p  determines \Omega(n)  distinct distances with the other points of \cal P  .

Another simple observation is that, for any k\ge 4  , we have \phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +2 \right) = \Omega(n^2)  , since in this case every distance can occur at most \lfloor k/2 \rfloor -1  times.

Finally, similarly to the cases of \phi(n,3,3)  and \phi(n,4,4)  , we can use the set {\cal P}_1  to obtain a bound of n2^{O(\sqrt{\log n})}  for various \phi(n,k,l)  . For example, it is not hard to show that \phi\left(n,k,2\lfloor k/2 \rfloor\right) =n2^{O(\sqrt{\log n})}  . It seems likely that a more careful analysis would yield the same bound for larger values of l  .

Advertisements

One thought on “Distinct Distances: Open Problems and Current Bounds (part @#%)

  1. Pingback: Distinct Distances for Sets with no Repeated Bisectors – Some Plane Truths

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s