Welcome to MathOverflow

Question

5

1

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

edited Aug 9 2010 at 14:05

Charles Matthews
9,720●12●39

asked Aug 9 2010 at 4:56

mr.gondolier
925●3●7

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 2010 at 5:15

1

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 2010 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 2010 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 2010 at 22:20

Ronald, can you elaborate a bit about Finslerian norms please? – mr.gondolier Aug 9 2010 at 22:58

Aaron Meyerowitz · Answer 1 · 2010-08-09 07:23:19Z UTC

2

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

answered Aug 9 2010 at 7:23

Aaron Meyerowitz
11.5k●1●10●31

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 2010 at 21:53

Point cloud that maximizes the minimum pairwise distance in Euclidean space

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.