Hilbert uzayında toplar
Geçenlerde belki de zor bir soruya yol açan ilginç bir gerçeği fark ettim. Eğer$n$ doğal bir sayıdır $k_n$ en küçük sayı ol $k$ öyle ki yarıçaplı açık bir top $k$ yeterince büyük boyutta veya sonsuz boyutta gerçek bir Hilbert uzayında $n$ yarıçapı 1 olan ikili ayrık açık toplar. (Hilbert uzayının boyutu en az olduğu sürece ilgisizdir. $n-1$ çünkü topların merkezlerinin yaydığı afin alt uzay ile değiştirilebilir.) $k_1=1$ ve $k_2=2$ve bunu görmek çok kolay $k_3=1+\frac{2}{\sqrt{3}}\approx 2.1547$. İlginç gerçek şu ki$k_n\leq 1+\sqrt{2}\approx 2.414$ hepsi için $n$çünkü sonsuz boyutlu bir Hilbert uzayında bu yarıçapa sahip bir açık top, yarıçapı 1 olan sonsuz sayıda çiftli ayrık açık top içerir [topların ortonormal bir temelde merkezlenmiş olduğunu düşünün]. Açıkça sorulan sorular şunlardır: (1)$k_n$? Bu bilinebilir, ancak küre paketleme ile ilgili olduğu için zor görünüyor. (2)$k_n$ hatta kesinlikle artıyor $n$? (3)$k_n<1+\sqrt{2}$ hepsi için $n$veya yeterince büyük için eşitler mi? $n$? (4) Hatta doğru mu$\sup_n k_n=1+\sqrt{2}$? Hatta tam olarak belli değil$k_n$ herkes için var $n$yani en küçüğü var $k$ her biri için $n$, ancak bunu gösteren bazı kompaktlık argümanları olmalıdır. Rakamların ilginç buluyorum$1+\frac{2}{\sqrt{3}}$ ve $1+\sqrt{2}$çok yakın ama topların davranışları çok çarpıcı. Sanırım soru daha küçük boyutlu Hilbert uzaylarında da ilginç:$k_{n,d}$ en küçüğü ol $k$ öyle ki yarıçaplı açık bir top $k$ Hilbert boyut uzayında $d$ içerir $n$ yarıçap 1 olan ikili ayrık açık bilyeler. Sonra $k_{n,d}$ stabilize $k_n$ için $d\geq n-1$. Nedir$k_{n,d}$? (Bu, neredeyse küre paketleme sorusu olduğu için, eğer$n>>d$.)
Yanıtlar
Gösterim kolaylığı için beklentiyi yazmama izin verin $\mathop{\mathbb{E}}_i t_i$ ortalamayı belirtmek için $(\sum_{i=1}^n t_i)/n$.
Yapınızı doğru anlarsam, yarıçaplı ayrık toplarınız var $1$ merkezli $x_i = \sqrt{2} e_i$ yarıçaplı bir topun içinde $1+\sqrt{2}$ merkezli $y = 0$. Bu inşaat, hangi yerler$n$ düzenli bir simpleksin köşelerinde sıkıca paketlenmiş toplar, konumlar açısından idealdir $x_i$. Probleminize tam olarak en uygun sınır için,$y=\mathop{\mathbb{E}}_i x_i$ yarıçapı almak için $$\boxed{k_n = 1+\sqrt{2 (1-1/n)}}.$$
Yerleştirme iddiası $x_i$ normalin köşelerinde $(n-1)$- basit ve $y$Bu simpleksin centroidinin optimal olduğu daha önce birçok farklı bağlamda birçok kez kanıtlanmıştır. Örneğin, çerçeve teorisinde " Welch-Rankin simpleks sınırının " çeşitli alt dizileriyle bilinen bir sınırla ifade edilir . İşte basit bir doğrudan kanıt:
Üçgen eşitsizliğine göre, yarıçaplı bir top $1+r$ merkezli $y$ yarıçaplı bir top içerir $1$ merkezli $x_i$ iff $\lVert x-y\rVert \le r$. İki yarıçaplı top$1$ merkezli $x_i$ ve $x_j$ ayrık $\lVert x_i - x_j \rVert \ge 2$. Bu nedenle, sorununuz en aza indirmenizi ister$1 + \max_i \lVert y-x_i\rVert$ tabi $\min_{i\ne j} \lVert x_i - x_j\rVert \ge 2$.
Kare mesafelerle çalışmak daha kolaydır. Maksimum kare mesafe$\max_i \lVert y-x_i\rVert^2$ kesinlikle en azından ortalama $\mathop{\mathbb{E}}_i \lVert y-x_i\rVert^2$. Bu ortalama ne zaman minimize edilir$y$ kendisi ortalama mı $\mathop{\mathbb{E}}_i x_i$, bu durumda eşittir $\mathop{\mathbb{E}}_i \mathop{\mathbb{E}}_j \lVert x_i-x_j\rVert^2/2$. Her dönem nerede$i=j$ katkıda bulunur $0$ bu beklentiye, her terim nerede $i\ne j$ en azından katkıda bulunur $2$yani genel olarak bu beklenti en azından $2(n-1)/n$. Böylece maksimum kare mesafe$\max_i\lVert y-x_i\rVert^2$ en azından $2(n-1)/n$ ve böylece $1+r \ge 1+\sqrt{2(n-1)/n}.$ Daha önce bahsedilen en uygun konfigürasyonun, doğrudan hesaplamayla veya argümanımızın her adımında eşitliği sağladığını belirterek bu sınıra ulaştığını kontrol edebiliriz.