What is the maximum distance of k points in an n-dimensional hypercube?

Question

For this question, I'm thinking only about the euclidean distance:

Let $p_1 = (x_1^{(1)}, \dots, x_n^{(1)})$ and $p_2 = (x_1^{(2)}, \dots, x_n^{(2)})$ be $n$-dimensional points. The euclidean distance of $p_1$ and $p_2$ is $$d(p_1, p_2) = \sqrt{\sum_{i=1}^n {\left (x_i^{(1)} - x_i^{(2)} \right )}^2}$$

Lets say $\alpha(n, k)$ is the maximum distance for $k$ points in the unit-hypercube of $\mathbb{R}^n$:

$$\alpha(n, k) = \max( \left \{\min(d(p_i, p_j))| (p_1, \dots, p_k) \in [0, 1]^n, i, j \in \{1, \dots, k\} \right \})$$

$n = 1$

• $\alpha(1, k = 2 = 2^n) = 1$
• $\alpha(1, k = 3)= 0.5$
• $\alpha(1, k) = \frac{1}{k-1}$

$n = 2$

• $\alpha(2, k = 2) = \sqrt{2}$: The maximum distance is the diagonal and hence $\sqrt{1+1}$
• $\alpha(2, k = 3)=?$
• $\alpha(2, k = 4 = 2^n) = 1$: Putting each point at the corners of the square.
• $\alpha(2, k = 5)$: I guess like 4 but with one point in the center? (hence $\frac{\sqrt 2}{2}$?)

n = 3

• $\alpha(3, k = 2) = \sqrt{3}$: The diagonal again and hence $\sqrt{1+1+1}$
• $\alpha(3, k = 2^n)$: The corners again and hence 1

Arbitrary $n$

• $\alpha(n, k=2) = \sqrt{n}$
• $\alpha(n, 2^n) = 1$

What is $\alpha(n, k)$?

Answer 1

(This should be a comment but I'll post it as an answer since I don't have enough reputation to comment.)

I'd like to answer the case with $n = 2$ and $k = 3$. The proof is really simple and can be found geometrically, if you assume two facts:

• the first point is on a vertex of the 2D hypercube, and the two others are on the opposite edges. It makes sense all 3 points should be on the edges to maximize distance.
• the resulting triangle is equilateral. This also makes sense, as in a non-equilateral triangle, one of the sides would have a smaller length and thus penalize the minimal distance between the points.

The triangle will look like this:

Equilateral triangle inside unit square

Solving for $x$ (using the fact than the triangle is equilateral), we find $x = 2-\sqrt{3} \approx 0.2679$, and finally:

$$ a = \alpha(2, k=3) = \sqrt{6} - \sqrt{2} \approx 1.035276\dots $$

But solving for $\alpha(n, k)$ in the general case seems challenging and I did not find a solution on the internet, interesting problem!

Answer 2

Let's start with the $2$D case.

Consider to have $m$ circles of radius $r$.

Packing them inside a square $C_r$ of size $(1+2r) \times (1+2r)$, will be equvalent to ask that their centers be inside the unit square and at mutual distance $r \le d$.

Then your question is equivalent to:
what is the maximum $r$ such that it is still possible to pack $m$ circles in the square $C_r$ ?

Clearly the same holds for any dimension $n$ and of course, you can size down the square to become unitary and correspondingly the radius of the balls by $\frac{1}{1+2r}$, and ask
in $n$ dimension, what is the maximum $\rho = r/(1+2r)$ such that it is still possible to pack $m$ balls of radius $\rho$ in the unit cube ?
and that is a typical Packing problem, whose difficulty is well known.

Some results have been reached and published in specialized literature and sites, and some of them are proved.

For example, for $n = 2$ in this site it is stated that the minimum side of the square containing $3$ unitary circles is $$ s = 2 + {{\sqrt 2 + \sqrt 6 } \over 2} $$ then the corresponding radius for your problem will be $$ {s \over 1} = {{1 + 2r} \over r}\quad \Rightarrow \quad r = {1 \over {s - 2}} = {2 \over {\sqrt 2 + \sqrt 6 }} = 0.5176 \ldots $$