(More) Local Properties that imply Many Distinct Distances

Last year I wrote a post about a distinct distances problem that involves local properties of the point set. Specifically, let \phi(n,k,l)  denote the minimum number of distinct distances that can be determined by a set {\cal P} \subset {\mathbb R}^2  of n  points, such that any k  points of \cal P  determine at least l  distinct distances. That is, by assuming that the point set satisfies a local property, we wish to conclude the global property of many distinct distances. For more details and examples, see the original post.

A while ago I noticed another nice bound for this set of problems. Unfortunately the proof is very simple, which prevents it from being published in a “decent” journal. I’ve been trying to push it further, so far without success. Perhaps someone else would see how this idea can be extended.

As discussed in the previous post, Fox, Pach, and Suk proved that for every k\ge 6  and \varepsilon>0  , we have

\phi\left(n,k,\binom{k}{2}-k+6\right) = \Omega(n^{8/7-\varepsilon}).

A simple argument shows that for every k\ge 4  we have

\phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +2\right) = \Omega(n^2).

Our interest in this post lies in between these two bounds. That is, what happens between the values \binom{k}{2}-k+6  and \binom{k}{2}- k/2 +2  . I am only aware of one previous result in thie range: Erdős and Gyárfás showed that \phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +1\right) = \Omega(n^{4/3})  . We will now prove a stronger result.

Theorem 1. For every k\ge 8  that is divisible by four, we have

\phi\left(n,k,\binom{k}{2}- 3k/4 +3\right) = \Omega_k(n^{4/3}).

Continue reading

Advertisements