12
$\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!

$\endgroup$
  • 1
    $\begingroup$ Is this not a very well-known problem?: en.wikipedia.org/wiki/Erd%C5%91s_distinct_distances_problem $\endgroup$ – Sam Hopkins May 24 '15 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 May 24 '15 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 May 24 '15 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 May 24 '15 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 May 24 '15 at 4:51
8
$\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.

$\endgroup$
2
$\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)$.

$\endgroup$
  • $\begingroup$ Great, just what I need---Thanks! (I cannot access the handbook until next week.) $\endgroup$ – Joseph O'Rourke May 24 '15 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 May 24 '15 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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