16
$\begingroup$

I recently noticed an interesting fact which leads to a perhaps difficult question. If $n$ is a natural number, let $k_n$ be the smallest number $k$ such that an open ball of radius $k$ in a real Hilbert space of sufficiently large dimension or infinite dimension contains $n$ pairwise disjoint open balls of radius 1. (The dimension of the Hilbert space is irrelevant as long as it is at least $n-1$ since it can be replaced by the affine subspace spanned by the centers of the balls.) We obviously have $k_1=1$ and $k_2=2$, and it is easy to see that $k_3=1+\frac{2}{\sqrt{3}}\approx 2.1547$. The interesting fact is that $k_n\leq 1+\sqrt{2}\approx 2.414$ for all $n$, since in an infinite-dimensional Hilbert space an open ball of this radius contains infinitely many pairwise disjoint open balls of radius 1 [consider balls centered at points of an orthonormal basis]. The obvious questions are: (1) What is $k_n$? This may be known, but looks difficult since it is related to sphere packing. (2) Is $k_n$ even strictly increasing in $n$? (3) Is $k_n<1+\sqrt{2}$ for all $n$, or are they equal for sufficiently large $n$? (4) Is it even true that $\sup_n k_n=1+\sqrt{2}$? It is not even completely obvious that $k_n$ exists for all $n$, i.e. that there is a smallest $k$ for each $n$, but there should be some compactness argument which shows this. I find it interesting that the numbers $1+\frac{2}{\sqrt{3}}$ and $1+\sqrt{2}$ are so close but the behavior of balls is so dramatically different. I suppose the question is also interesting in smaller-dimensional Hilbert spaces: let $k_{n,d}$ be the smallest $k$ such that an open ball of radius $k$ in a Hilbert space of dimension $d$ contains $n$ pairwise disjoint open balls of radius 1. Then $k_{n,d}$ stabilizes at $k_n$ for $d\geq n-1$. What is $k_{n,d}$? (This my be much harder since it is virtually the sphere-packing question if $n>>d$.)

$\endgroup$
  • $\begingroup$ Perhaps $k_n=1+\sqrt{2(1-1/n)}$? $\endgroup$ – aorq Aug 18 '20 at 8:29
8
$\begingroup$

For convenience of notation, let me write the expectation $\mathop{\mathbb{E}}_i t_i$ to denote the average $(\sum_{i=1}^n t_i)/n$.

If I understand your construction correctly, you have disjoint balls of radius $1$ centered at $x_i = \sqrt{2} e_i$ contained in a ball of radius $1+\sqrt{2}$ centered at $y = 0$. This construction, which places $n$ balls tightly packed at the vertices of a regular simplex, is optimal in terms of the positions $x_i$. For the exact optimal bound for your problem, you should pick $y=\mathop{\mathbb{E}}_i x_i$ to get the radius $$\boxed{k_n = 1+\sqrt{2 (1-1/n)}}.$$

The claim that placing the $x_i$ at the vertices of a regular $(n-1)$-simplex and $y$ at the centroid of this simplex is optimal has been proven many times before in many different contexts. For example, it is implied by a bound known by various substrings of "the Welch-Rankin simplex bound" in frame theory. Here's a simple direct proof:

By the triangle inequality, a ball of radius $1+r$ centered at $y$ contains a ball of radius $1$ centered at $x_i$ iff $\lVert x-y\rVert \le r$. Two balls of radius $1$ centered at $x_i$ and $x_j$ are disjoint iff $\lVert x_i - x_j \rVert \ge 2$. Therefore, your problem asks to minimize $1 + \max_i \lVert y-x_i\rVert$ subject to $\min_{i\ne j} \lVert x_i - x_j\rVert \ge 2$.

Working with squared distances is easier. The maximum squared distance $\max_i \lVert y-x_i\rVert^2$ is surely at least the average $\mathop{\mathbb{E}}_i \lVert y-x_i\rVert^2$. This average is minimized when $y$ is itself the average $\mathop{\mathbb{E}}_i x_i$, in which case it equals $\mathop{\mathbb{E}}_i \mathop{\mathbb{E}}_j \lVert x_i-x_j\rVert^2/2$. Each term where $i=j$ contributes $0$ to this expectation, while each term where $i\ne j$ contributes at least $2$, so overall this expectation is at least $2(n-1)/n$. Thus the maximum squared distance $\max_i\lVert y-x_i\rVert^2$ is at least $2(n-1)/n$ and thus $1+r \ge 1+\sqrt{2(n-1)/n}.$ We can check that the optimal configuration mentioned before achieves this bound either by direct calculation or by noting that it achieves equality in every step of our argument.

$\endgroup$

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.