# Balls in Hilbert space

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

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

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.