(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}).

(We ask k  to be divisible by four only for simplicity. This restriction can be easily removed.)

Proof. Let \cal P  be a set of n  points in {\mathbb R}^2  , such that every k  points of \cal P  determine at least \binom{k}{2}- 3k/4 +3  distinct distances. Let x  denote the number of distinct distances that are determined by \cal P  .

By the pigeonhole principle, there exists a distance \delta  that is determined by \Omega(n^2/x)  pairs of points of {\cal P}^2  . Let {\cal P}'  be the set of points of {\cal P}  that are at a distance of \delta  from at least one other point of {\cal P}  . By the restriction \phi\left(n,k,\binom{k}{2}- 3k/4 +3\right)  , every point of p \in {\cal P}  can be at distance \delta  from at most k/4 -2  other points of {\cal P}  . This implies that |{\cal P}'| =\Omega_k(n^2/x)  .

We claim that every distance, except for \delta  , is determined by less than k/4  pairs of ({\cal P}')^2  . Indeed, assume that that a distance \delta'  is determined by k/4  such pairs (a_1,b_1),(a_2,b_2),\ldots,(a_{k/4}, b_{k/4})  . We set {\cal S} =\{a_1,\ldots,a_{k/4},b_1,\ldots,b_{k/4}\}  . The set {\cal S}  is not a multiset. That is, if some of these points are identical, then we add just one copy of each point. We arbitrarily add |{\cal S}|-k/2  additional points of {\cal P}'  to {\cal S}  , to obtain |{\cal S}|=k/2  . Finally, for every element of p\in {\cal S}  we add to {\cal S}  one of the points of {\cal P}'  that are at a distance of \delta  from p  . Once again, if some of these points are identical, then we only add one copy of each point. We then obtain a set {\cal S}  of at most k  points of {\cal P}  . There are at least k/2  pairs of points of {\cal S}^2  are at a distance of \delta  , and at least k/4  pairs are at a distance of \delta'  . Such a case is depicted in the figure below, where the red lines represent the distance \delta  and the blue lines represent the distance \delta'  (this figure represents the simplest case, where we did not have identical points that were merged in any of the above steps). This contradicts the assumption of the theorem, and thus every distance repeats less than k/4  times in {\cal P}'  .

DDLocal34

Since every distance is determined by points of {\cal P}'  fewer than k/4  times, we get that the points of {\cal P}'  determine \Omega_k(|{\cal P}'|^2) = \Omega_k(n^4/x^2)  distinct distances. Since the number of distinct distance that are determined by {\cal P}  is x  and {\cal P}' \subset {\cal P}  , we have that n^4/x^2 = O_k(x)  . Equivalently, we get that x = \Omega_k(n^{4/3})  , as asserted.      \Box

Finally, I would like to thank Alex Mun – I came up with the idea for the above proof while discussing the problem with him.
Advertisements

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