Last year I wrote a post about a distinct distances problem that involves local properties of the point set. Specifically, let denote the minimum number of distinct distances that can be determined by a set of points, such that any points of determine at least 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 and , we have
A simple argument shows that for every we have
Our interest in this post lies in between these two bounds. That is, what happens between the values and . I am only aware of one previous result in thie range: Erdős and Gyárfás showed that . We will now prove a stronger result.
Theorem 1. For every that is divisible by four, we have
(We ask to be divisible by four only for simplicity. This restriction can be easily removed.)
Proof. Let be a set of points in , such that every points of determine at least distinct distances. Let denote the number of distinct distances that are determined by .
By the pigeonhole principle, there exists a distance that is determined by pairs of points of . Let be the set of points of that are at a distance of from at least one other point of . By the restriction , every point of can be at distance from at most other points of . This implies that .
We claim that every distance, except for , is determined by less than pairs of . Indeed, assume that that a distance is determined by such pairs . We set . The set 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 additional points of to , to obtain . Finally, for every element of we add to one of the points of that are at a distance of from . Once again, if some of these points are identical, then we only add one copy of each point. We then obtain a set of at most points of . There are at least pairs of points of are at a distance of , and at least pairs are at a distance of . Such a case is depicted in the figure below, where the red lines represent the distance and the blue lines represent the distance (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 times in .
Since every distance is determined by points of fewer than times, we get that the points of determine distinct distances. Since the number of distinct distance that are determined by is and , we have that . Equivalently, we get that , as asserted.
Finally, I would like to thank Alex Mun – I came up with the idea for the above proof while discussing the problem with him.