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

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)$?

• if $k\leq n$ isn't it sufficent to consider the graph made up by the corners of the hypercube? – tired Oct 19 '16 at 20:33
• @tired: I'm not sure. This would mean $\alpha(2, 3) = 1$, but I'm relatively certain that you could place the points on the edges (not the corners) and get a bigger distance. – Martin Thoma Oct 19 '16 at 20:40
• @tired: No. This would mean $\alpha(2, 3) = 1$. But $p_1 = (0, 0.5)$, $p_2 = (0, 0.75)$, $p_3 = (1, 1)$ has a bigger distance than 1. – Martin Thoma Oct 19 '16 at 20:49
• Am I the only one not grasping how the (maximum) distance between $k>2$ points is defined here? – Jack D'Aurizio Oct 19 '16 at 20:51
• @JackD'Aurizio I've added a definition of the distance. I hope that helps. – Martin Thoma Oct 19 '16 at 21:01

(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!

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$$