13
$\begingroup$

For $k \ge 1$, let $f_d(k)$ be the largest possible number of points $p_i$ in $\mathbb{R}^d$ that determine at most $k$ distinct (Euclidean) distances, $\|p_i-p_j\|$.

Example. For points in the plane $\mathbb{R}^2$, $f_2(1)=3$ via an equilateral triangle, and $f_2(2)=5$ via the regular pentagon.

RegPentagon
It is clear that $f_d(k)$ is finite: it is not possible to "pack" an infinite number of points into $\mathbb{R}^d$ while only determining a finite number of point-to-point distances.

Q. What is the growth rate of a reasonable upper bound for $f_d(k)$?

I am particularly interested in $\mathbb{R}^3$. $f_3(1)=4$ via the regular simplex. I am not even certain what is $f_3(2)$. Does anyone know? Certainly $f_3(2) \ge 6$ just by placing one point immediately above the centroid of the pentagon.

But regardless of exact values, I would be interested in an upper bound for $f_3(k)$. As well as pointers to results in the literature. This question has an Erdős-like flavor, and undoubtedly has been considered previously. Thanks!

Improve this question
$\endgroup$
13
  • 1
    $\begingroup$ Is this not a very well-known problem?: en.wikipedia.org/wiki/Erd%C5%91s_distinct_distances_problem $\endgroup$
    – Sam Hopkins
    Commented May 24, 2015 at 1:41
  • 3
    $\begingroup$ It is related, but not exactly the same. In Joseph's version, k (number of distinct distances) is fixed and n is wanted, whereas the literature you mention seems to me to have n fixed and estimates k given n and d. However, that entry a good place to start. Also, the book titled something like "Unsolved problems in geometry" might have a discrete portion that gets closer to Joseph's question. Gerhard "Looking From The Other End" Paseman, 2015.05.23 $\endgroup$
    – Gerhard Paseman
    Commented May 24, 2015 at 1:54
  • 1
    $\begingroup$ Don't know if this helps, but the octahedron is another example showing $f_3(2) \geq 6$. $\endgroup$
    – Will Brian
    Commented May 24, 2015 at 3:23
  • 2
    $\begingroup$ Also, $f_d(k) < R(d+2,\dots,d+2)$ (where $R$ denotes the Ramsey number and there are $k$ entries). This is because you cannot have $d+2$ points that are all mutually the same distance from each other. Suppose you had $R(d+2,\dots,d+2)$ or more points and only $k$ distances represented. Think of these points as the vertices of a complete graph, and think of the distance between two points as the "color" of their edge. The definition of $R$ tells you that you have $d+2$ points all the same distance apart, a contradiction. Thus, for example, $f_3(2)$ is less than $R(5,5) \leq 49$. $\endgroup$
    – Will Brian
    Commented May 24, 2015 at 3:46
  • 2
    $\begingroup$ Doesn't the pentagon give you $f_3(2)\ge 7$ if you add a point below also? $\endgroup$
    – Anthony Quas
    Commented May 24, 2015 at 4:51

2 Answers 2

Reset to default
9
$\begingroup$

Bannai, Bannai and Stanton proved that $f_d(k) \leq {d + k \choose k}$ in 1983. See: http://link.springer.com/article/10.1007%2FBF02579288

I don't think this bound has been improved in general. It is certainly not tight for every value of the parameters.

The first good bound for this function was for $k = 2$, as given by Larman Rogers and Seidel in 1977, "On Two-Distance Sets in Euclidean Space". They proved that $f_d(2) \leq (d+1)(d+4)/2$ using a nice dimension argument. This bound was later improved by Blokhuis in 1981 to $(d+1)(d+2)/2 = {d+2 \choose 2}$, which was later generalised to $f_d(k) = {d+k \choose k}$.

This problem is also discussed in the manuscript "Linear Algebra Methods in Combinatorics" by Babai and Frankl, where you can find some of these proofs.

Improve this answer
$\endgroup$
1
3
$\begingroup$

In Graham's handbook of combinatorics volume one, chapter 17, Extremal problems in combinatorial geometry by Erdos and Purdy, section 5.3.1 has some upper bounds. It cites a paper showing $f_3(2)$ is 6 and it has some upper bounds for $f_d(2)$ and an upper bound for $f_d(k)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Great, just what I need---Thanks! (I cannot access the handbook until next week.) $\endgroup$
    – Joseph O'Rourke
    Commented May 24, 2015 at 16:26
  • $\begingroup$ Parts of the book can be viewed on google books and I think that includes all of section 5.3.1 of chapter 17. $\endgroup$
    – Kristal Cantwell
    Commented May 24, 2015 at 16:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .