Today I wish to discuss several problems concerning finding a subset of a point set , such that the points of do not span any distance more than once. This is another family of problems for my survey of open variants of the distinct distances problem. I also present a surprisingly short and elegant proof that was recently observed by Charalambides (and is a simple combination of a proof by Lefmann and Thiele with a result from Guth and Katz’s distinct distances paper). The following table lists the best known bounds for the problems that are presented in this post.

Variant | Lower Bound | Upper Bound |
---|---|---|

Given a set of points in , let denote the size of the largest subset such that every distance is spanned by the points of at most once; that is, there are no points such that (including cases where ). The following figure depicts a set of 25 points and a subset of 5 points that span every distance at most once.

Let . In other words, is the maximum number satisfying the property that every set of points in the plane contains a subset of points that do not span any distance more than once. Erdős posed the following problem (see here (in Hungarian), here, and here (page 838)).

**Problem 1. (Erdős)**

*Find the asymptotic value of*.

Let be a point set that spans distinct distances. Notice that if all of the distances that are spanned by the points of a subset are unique, then . Let be a integer lattice. Erdős proved that the number of distinct distances that are spanned by is (for more details see this post). Therefore, we have . Lefmann and Thiele derived the bound by using a probabilistic argument. Dumitrescu improved this bound to by combining it with an upper bound of Pach and Tardos on the maximum number of isosceles triangles that can be spanned by a set of points. Recently, Charalambides combined the probabilistic argument of Lefmann and Thiele with a result from Guth and Katz’s distinct distances paper, to obtain the following improved result and simple proof.

**Theorem 1.**

*Proof.*Consider a set of points in . Similarly to the Elekes-Sharir reduction (e.g., see this post), we define the set

such that every quadruple of consists of four distinct points. Guth and Katz proved that (also for the case where is allowed to contain quadruples where not all four points are distinct). Let be the set of isosceles and equilateral triangles that are spanned by points of . Pach and Tardos proved that .

Let be a subset that is obtained by selecting every point of with probability that we will fix later. We have . Let be the set of quadruples of that contain only points of . Every quadruple of is in with a probability of , so , for a sufficiently large constant . Let be the set of triangles of that contain only points of . The bound of Pach and Tardos implies , for a sufficiently large constant . Notice that the points of span every distance at most once if and only if . By linearity of expectation, we have

By setting , when is sufficiently larger we obtain

Therefore, there exists a subset for which . Let be a subset of that is obtained by removing from a point from every element of and . The subset does not span any repeated distances and contains points, concluding the proof.

Let denote the maximum number satisfying the property that every set of points on a sphere in contains a subset of points that do not span any distance more than once. Charalambides showed that a simple extension of the proof of Theorem 1 implies . This requires an extension of Guth and Katz’s distinct distances result to points on a sphere, as derived by Tao. Let be the set of vertices of a regular -gon in . It can be easily verified that the points of determine distinct distances and are contained in a common sphere. This implies .

**Problem 2.**

*Find the asymptotic value of*.

Erdős and Guy considered the following special case of Problem 1.

**Problem 3. (Erdős and Guy)**

*Find the asymptotic value of , where is a integer lattice*.

As mentioned above, the best known upper bound on is the trivial . Erdős and Guy derived the bound , which was later improved by Lefmann and Thiele to . This bound is still slightly better than the bound implied by Theorem 1.

Erdős and Guy also considered the higher dimensional variant of Problem 3. That is, they considered higher dimensional lattices of the form , and conjectured that . This conjecture was proved by Lefmann and Thiele. It is simple to show that the points of span distinct distances (e.g., see this post), which implies .

**Problem 4. (Erdős and Guy)**

*Find the asymptotic value of , where is an integer lattice.*

We can also consider the higher dimensional variant of Problem 1. Let denote the maximum number satisfying the property that every set of points in contains a subset of points that do not span any distance more than once.

**Problem 5.**

*Find the asymptotic value of , for .*

I am not aware of any non-trivial bounds for this case.

In the open problems book by Brass, Moser, and Pach, they suggest the following variant of Probelm 1. Let denote the maximum number satisfying the property that every set of points in the plane contains a subset of points that do not span any isosceles triangles.

**Problem 6. (Brass, Moser, and Pach)**

*Find the asymptotic value of*.

For a trivial upper bound, we have . By adapting the proof of Theorem 1 (i.e., removing from the analysis), we obtain .

Advertisements

Hello Adam,

The formula defining subset(n) doesn’t seem to match the verbal description…

Reading your blog with interest,

Frank de Zeeuw

Thanks for the comment Frank!

I need more help with it, since it seems to me that the two do match. Why don’t they?

Adam

Right after the picture with 25 and 5 points, it says subset(n)=min_P D(P), which sounds like something else to me…

Oh I see. That seems correct, but perhaps not written quite clearly.

The minimum is basically going over every possible set of n points and selecting the set for which D(P) is the smallest. If this yielded a value of x, then the corresponding point set contains no good subset of size x+1, so x is indeed the largest integer satisfying the verbal description.

It’s good that someone is verifying that I’m not writing nonsense! Do tell me about any other problems that you notice in the future.

By D(P), do you mean subset(P)?

Oh! I really had a blind spot with regard to this. Fixed.

Thanks Frank!

Pingback: Subsets with distinct volumes | Some Plane Truths