Bolas no espaço de Hilbert
Recentemente, notei um fato interessante que leva a uma questão talvez difícil. E se$n$ é um número natural, vamos $k_n$ seja o menor número $k$ de modo que uma bola aberta de raio $k$ em um espaço de Hilbert real de dimensão suficientemente grande ou dimensão infinita contém $n$ bolas abertas disjuntas aos pares de raio 1. (A dimensão do espaço de Hilbert é irrelevante, desde que seja pelo menos $n-1$ uma vez que pode ser substituído pelo subespaço afim estendido pelos centros das bolas.) Obviamente, temos $k_1=1$ e $k_2=2$, e é fácil ver que $k_3=1+\frac{2}{\sqrt{3}}\approx 2.1547$. O interessante é que$k_n\leq 1+\sqrt{2}\approx 2.414$ para todos $n$, já que em um espaço de Hilbert de dimensão infinita uma bola aberta deste raio contém infinitamente muitas bolas abertas disjuntas de pares de raio 1 [considere bolas centradas em pontos de uma base ortonormal]. As perguntas óbvias são: (1) O que é$k_n$? Isso pode ser conhecido, mas parece difícil, pois está relacionado ao empacotamento de esferas. (2) É$k_n$ mesmo aumentando estritamente em $n$? (3) É$k_n<1+\sqrt{2}$ para todos $n$, ou são iguais para suficientemente grandes $n$? (4) É mesmo verdade que$\sup_n k_n=1+\sqrt{2}$? Nem mesmo é completamente óbvio que$k_n$ existe para todos $n$, ou seja, que há um menor $k$ para cada $n$, mas deve haver algum argumento de compactação que mostra isso. Acho interessante que os números$1+\frac{2}{\sqrt{3}}$ e $1+\sqrt{2}$estão tão próximos, mas o comportamento das bolas é dramaticamente diferente. Suponho que a questão também seja interessante em espaços de Hilbert de dimensões menores: deixe$k_{n,d}$ seja o menor $k$ de modo que uma bola aberta de raio $k$ em um espaço de dimensão de Hilbert $d$ contém $n$ bolas abertas disjuntas aos pares de raio 1. Então $k_{n,d}$ estabiliza em $k_n$ para $d\geq n-1$. O que é$k_{n,d}$? (Isso pode ser muito mais difícil, pois é virtualmente a questão do empacotamento de esferas se$n>>d$.)
Respostas
Por conveniência de notação, deixe-me escrever a expectativa $\mathop{\mathbb{E}}_i t_i$ para denotar a média $(\sum_{i=1}^n t_i)/n$.
Se entendi sua construção corretamente, você tem bolas de raio disjuntas $1$ centrado em $x_i = \sqrt{2} e_i$ contido em uma bola de raio $1+\sqrt{2}$ centrado em $y = 0$. Esta construção, que coloca$n$ bolas bem compactadas nos vértices de um simplex regular, é ideal em termos de posições $x_i$. Para obter o limite ideal exato para o seu problema, você deve escolher$y=\mathop{\mathbb{E}}_i x_i$ para obter o raio $$\boxed{k_n = 1+\sqrt{2 (1-1/n)}}.$$
A afirmação de que colocar o $x_i$ nos vértices de um regular $(n-1)$-simplex e $y$no centroide deste simplex é ótimo foi provado muitas vezes antes em muitos contextos diferentes. Por exemplo, está implícito em um limite conhecido por vários substrings do " limite simplex de Welch-Rankin " na teoria do frame. Aqui está uma prova direta simples:
Pela desigualdade do triângulo, uma bola de raio $1+r$ centrado em $y$ contém uma bola de raio $1$ centrado em $x_i$ sse $\lVert x-y\rVert \le r$. Duas bolas de raio$1$ centrado em $x_i$ e $x_j$ são disjuntos se $\lVert x_i - x_j \rVert \ge 2$. Portanto, seu problema pede para minimizar$1 + \max_i \lVert y-x_i\rVert$ sujeito a $\min_{i\ne j} \lVert x_i - x_j\rVert \ge 2$.
Trabalhar com distâncias quadradas é mais fácil. A distância quadrada máxima$\max_i \lVert y-x_i\rVert^2$ é certamente pelo menos a média $\mathop{\mathbb{E}}_i \lVert y-x_i\rVert^2$. Esta média é minimizada quando$y$ é em si a média $\mathop{\mathbb{E}}_i x_i$, nesse caso é igual a $\mathop{\mathbb{E}}_i \mathop{\mathbb{E}}_j \lVert x_i-x_j\rVert^2/2$. Cada termo onde$i=j$ contribui $0$ a esta expectativa, enquanto cada termo onde $i\ne j$ contribui pelo menos $2$, então no geral essa expectativa é de pelo menos $2(n-1)/n$. Assim, a distância máxima ao quadrado$\max_i\lVert y-x_i\rVert^2$ é pelo menos $2(n-1)/n$ e assim $1+r \ge 1+\sqrt{2(n-1)/n}.$ Podemos verificar se a configuração ótima mencionada antes atinge esse limite por cálculo direto ou observando que atinge a igualdade em todas as etapas de nosso argumento.