# Point cloud that maximizes the minimum pairwise distance in Euclidean space

I am interested finding the collection of points in the Euclidean space that has the maximal minimal pairwise distance subject to an average norm constraint, that is, how to maximize

$min_{i \neq j} |x_i - x_j|$

subject to $\frac{1}{n} \sum_{i=1}^n |x_j|^2 \leq1$ where $\{x_1, \ldots, x_n\} \subset \mathbb{R}^d$.

I wonder if this problem has a name and what is known about it. Of course $d = 1$ is easy: just choose $n$ uniformly spaced points that satisfies the constraint with equality. I am especially interested in $d=2$. If little is known in the non-asymptotic case, maybe we know more when $n$ and/or $d$ is large? Is it related to sphere packing?

(BTW, I heard that the answer is given by vertices on the simplex when $n \leq d -1$ (or maybe the other way around?))

-
1. If $d=1,$ in addition to being equally spaced, the optimal configuration must be centrally symmetric w.r.t. 0. 2. If $n\leq d+1$ then a moment's thought shows that the optimal configuration is a regular simplex with the center at the origin. 3. You must have encountered this problem somewhere (e.g. this is implied by "I heard that..."): can you, please, state the context? – Victor Protsak Aug 9 '10 at 5:15
This is almost a packing problem (with respect to Finslerian norms), except that it mixes two different norms. Using easy inequalities among the $l_2$ and the $l_\infty$ norm one can at least get inequalities relating it to the classical problem of packing (with respect to the Euclidean norm) $n$ balls of radius $\alpha$ into a ball of radius $1$. Maximising $\alpha$ and dilating the maximal solution by $1/(1-\alpha)$ yields the optimal Euclidean solution. Sloane's web-page gives probably useful information on this. – Roland Bacher Aug 9 '10 at 7:16
The case $d=1$ appeared as problem 11450 in the American Mathematical Monthly in the August-September 2009 issue. The solution has not been published yet, but indeed the "obvious" answer is correct. – Byron Schmuland Aug 9 '10 at 14:32
The context is some communication problem, where I found that the input distribution converges to the uniform distribution supported on the configuration that maximize the minimal distance. I did not find it quite relevant so I omitted it... – mr.gondolier Aug 9 '10 at 22:20
Ronald, can you elaborate a bit about Finslerian norms please? – mr.gondolier Aug 9 '10 at 22:58

Consider fixing $\min_{i \ne j}|x_i-x_j|=1$ and try to minimize $S=\sum_{1}^{n}|x_j|^2$. Then it is a sphere packing problem and the answer to your question would be $\frac{1}{\sqrt{S}}$
But the sphere packing problem (at least the version that I heard of) is to minimize the volume of the ball that contains these $n$ disjoint unit balls, which corresponds to minimize $\max |x_i|$ subject to $\min_{i \neq j} |x_i-x_j| \geq 2$. This does not seem to be equivalent to minimizing $\sum_1^n |x_j|^2$? – mr.gondolier Aug 9 '10 at 21:53