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

  • $\begingroup$ 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? $\endgroup$ – Victor Protsak Aug 9 '10 at 5:15
  • 1
    $\begingroup$ 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. $\endgroup$ – Roland Bacher Aug 9 '10 at 7:16
  • $\begingroup$ 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. $\endgroup$ – user6096 Aug 9 '10 at 14:32
  • $\begingroup$ 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... $\endgroup$ – gondolier Aug 9 '10 at 22:20
  • $\begingroup$ Ronald, can you elaborate a bit about Finslerian norms please? $\endgroup$ – 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}}$

  • $\begingroup$ 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$? $\endgroup$ – gondolier Aug 9 '10 at 21:53

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.