16
$\begingroup$

It is well known and not hard to prove that the regular simplex in n-dimensions is the only way to place n+1 points so that the distance between distinct pairs of points is always the same. My general question is what happens when we allow more than one distance?

On the plane it is a good exercise to show that this is the complete list of diagrams with 2 distances and 4 or 5 points:

Sets on the plane with 2 distinct distances

You can go further on the plane for example see:

Harborth, H and Piepmeyer, L (1996). Three distinct distances in the plane
Geometriae Dedicata 61, No. 3, 315-327
Link

Shinohara, M (2008). Uniqueness of maximum planar five-distance sets.
Discrete Mathematics, 308(14), 3048-3055.
http://linkinghub.elsevier.com/retrieve/pii/S0012365X07006498

What about higher dimensions? The cross-polytope in n-dimensions is always a 2-distance set with 2n points. Even better taking the set of mid-points of edges of the n-simplex gives a 2-distance set with n(n+1)/2 points (of course in 3d this gives the vertices of the octahedron). Are their better examples?

My motivation for this is mainly visual, the requirements that a small set of distances places on symmetry mean that these sets should give interesting forms. It should also be noted that (perhaps unsurprisingly given the elementary nature) it was also a problem that attracted Erdös, for example see:

Erdös, P (1970) On Sets of Distances of n Points
The American Mathematical Monthly 77, No. 7, pp. 738-740 http://www.jstor.org/pss/2316209

To finish with a precise question: What is known about n-distance sets in 3 and 4 dimensions?

$\endgroup$
6
  • 5
    $\begingroup$ There's general theory (in all dimensions) due to Delsarte, Goethals and Seidel. This provides good upper bounds on the size of an $s$-distance set, and some examples. $\endgroup$ Nov 6, 2011 at 16:57
  • 2
    $\begingroup$ Doesn't that assume that all points lie on the unit sphere in d-dimensions? $\endgroup$ Nov 6, 2011 at 17:14
  • 2
    $\begingroup$ It's true that what I was thinking of was points on the sphere. But there is also work by Seidel and other on Euclidean distance sets, where the points do not lie on a sphere. $\endgroup$ Nov 6, 2011 at 18:14
  • 2
    $\begingroup$ You're probably aware that Guth and Katz solved the Erdos problem? arxiv.org/abs/1011.4105 For 3D, see: arxiv.org/abs/1107.1077 $\endgroup$
    – Ian Agol
    Jul 28, 2012 at 1:10
  • 1
    $\begingroup$ When was the planar 12-point set with 5 distinct distances discovered, i.e. when was the date of the first publication? And when did it become publically known? --I 'd really appreciate this information. $\endgroup$ Oct 27, 2016 at 4:35

4 Answers 4

9
$\begingroup$

There's a nice book by Garibaldi, Iosevich, and Senger, The Erdős Distance Problem, in the Student Mathematical Library series of the American Mathematical Society (AMS link). Mostly it's about the problem in the plane, but there is some discussion of, and references to, work on higher dimensions.


           

$\endgroup$
1
  • 1
    $\begingroup$ Thanks! Looks like "Erdös Distance problem" is the correct thing to google! $\endgroup$ Nov 7, 2011 at 13:09
9
$\begingroup$

Here I mention some asymptotic results—valid when the number of points $n$ grows large—which may not be directly relevant to your concentration on few distances.

The 2003 paper, "Distinct distances in three and higher dimensions," by Aronov, Pach, Sharir, Tardos, established that the number of distinct distances determined by $n$ points in $\mathbb{R}^3$ is $\Omega( n^{77/141 - \epsilon} )$ for any $\epsilon > 0$. Their result holds for points on a sphere as well. For $\mathbb{R}^d$ they achieved a lower bound of about $n^{1/(d-90/77)}$, again also for points on a $d$-sphere.

These lower bounds can be contrasted to the number of distinct distances achieved by points in a $n^{1/d} \times ... \times n^{1/d}$ integer lattice, which is $O(n^{2/d})$. Erdős conjectured the matching lower bound $\Omega(n^{2/d})$.

A bit later (2006), their results were improved by Solymosi and Vu in the paper, "Near optimal bounds for the Erdős distinct distances problem in high dimensions," establishing $\Omega(n^{(2/d)-2/(d(d+2))})$.

$\endgroup$
4
$\begingroup$

This paper:

http://maths.ucd.ie/~osburn/lattices.pdf

Has very cool results/connections of this (essentially, the question is: if you assume that lattices are best, which lattices are best among them).

$\endgroup$
4
$\begingroup$

I have some maximal results up to 20 points at Maximal Unit Lengths in 3D.

The maximal log(unit edges)/log(points) so far is 1.43392 with 14 points producing 44 unit edges. The points are {{0,0,0}, {3,0,3}, {3,3,0}, {3,-3,0}, {3,0,-3},{0,3,-3}, {6,0,0}, {2,-1,1}, {-1,2,1}, {-1,-1,-2}, {-1,-1,4}, {-1,-4,1},{-4,-1,1}, {2,-4,4}}/(3 sqrt(2)). The graph looks like the following:

max 3D unit graph

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.