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$.)
1 Answer
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.