8
$\begingroup$

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

$\endgroup$
5
  • $\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$ Aug 9, 2010 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$ Aug 9, 2010 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, 2010 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, 2010 at 22:20
  • $\begingroup$ Ronald, can you elaborate a bit about Finslerian norms please? $\endgroup$
    – gondolier
    Aug 9, 2010 at 22:58

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\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, 2010 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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