Bola di ruang Hilbert
Saya baru-baru ini memperhatikan fakta menarik yang mengarah pada pertanyaan yang mungkin sulit. Jika$n$ adalah bilangan asli, biarkan $k_n$ menjadi angka terkecil $k$ sedemikian rupa sehingga radius bola terbuka $k$ dalam ruang Hilbert nyata yang memiliki dimensi cukup besar atau dimensi tak terbatas $n$ bola terbuka berpasangan terputus-putus dengan radius 1. (Dimensi ruang Hilbert tidak relevan selama setidaknya $n-1$ karena dapat digantikan oleh ruang angkasa affine yang direntang oleh pusat-pusat bola.) Kami jelas punya $k_1=1$ dan $k_2=2$, dan mudah untuk melihatnya $k_3=1+\frac{2}{\sqrt{3}}\approx 2.1547$. Fakta yang menarik adalah itu$k_n\leq 1+\sqrt{2}\approx 2.414$ untuk semua $n$, karena dalam ruang Hilbert berdimensi tak-hingga, bola terbuka dengan radius ini berisi banyak bola terbuka terputus-putus berpasangan yang tak terhingga dengan radius 1 [anggap bola berpusat pada titik-titik basis ortonormal]. Pertanyaan yang jelas adalah: (1) Apakah$k_n$? Ini mungkin diketahui, tetapi tampak sulit karena terkait dengan pengepakan bola. (2) Apakah$k_n$ bahkan meningkat tajam $n$? (3) Apakah$k_n<1+\sqrt{2}$ untuk semua $n$, atau apakah mereka sama untuk cukup besar $n$? (4) Apakah benar itu$\sup_n k_n=1+\sqrt{2}$? Bahkan tidak sepenuhnya jelas itu$k_n$ ada untuk semua $n$, yaitu ada yang terkecil $k$ untuk setiap $n$, tetapi harus ada beberapa argumen kekompakan yang menunjukkan hal ini. Saya merasa menarik bahwa angka-angka itu$1+\frac{2}{\sqrt{3}}$ dan $1+\sqrt{2}$sangat dekat tetapi perilaku bola sangat berbeda secara dramatis. Saya kira pertanyaannya juga menarik dalam ruang Hilbert berdimensi lebih kecil: mari$k_{n,d}$ jadilah yang terkecil $k$ sedemikian rupa sehingga radius bola terbuka $k$ dalam ruang dimensi Hilbert $d$ mengandung $n$ bola terbuka terputus-putus berpasangan dengan radius 1. Kemudian $k_{n,d}$ stabil di $k_n$ untuk $d\geq n-1$. apa yang$k_{n,d}$? (Ini saya jauh lebih sulit karena ini sebenarnya adalah pertanyaan pengepakan bola jika$n>>d$.)
Jawaban
Untuk kenyamanan notasi, izinkan saya menulis ekspektasinya $\mathop{\mathbb{E}}_i t_i$ untuk menunjukkan rata-rata $(\sum_{i=1}^n t_i)/n$.
Jika saya memahami konstruksi Anda dengan benar, Anda memiliki bola jari-jari yang terputus-putus $1$ berpusat pada $x_i = \sqrt{2} e_i$ terkandung dalam bola jari-jari $1+\sqrt{2}$ berpusat pada $y = 0$. Konstruksi ini, yang menempatkan$n$ bola yang dikemas dengan rapat pada simpul simpleks biasa, optimal dalam hal posisi $x_i$. Untuk batasan optimal yang tepat untuk masalah Anda, Anda harus memilih$y=\mathop{\mathbb{E}}_i x_i$ untuk mendapatkan radius $$\boxed{k_n = 1+\sqrt{2 (1-1/n)}}.$$
Klaim yang menempatkan $x_i$ di simpul biasa $(n-1)$-simplex dan $y$di pusat simpleks ini optimal telah terbukti berkali-kali sebelumnya dalam banyak konteks yang berbeda. Misalnya, ini tersirat oleh suatu ikatan yang dikenal oleh berbagai substring dari " ikatan simpleks Welch-Rankin " dalam teori bingkai. Inilah bukti langsung sederhana:
Dengan pertidaksamaan segitiga, bola jari-jari $1+r$ berpusat pada $y$ berisi bola berjari-jari $1$ berpusat pada $x_i$ iff $\lVert x-y\rVert \le r$. Dua bola jari-jari$1$ berpusat pada $x_i$ dan $x_j$ terputus-putus jikaf $\lVert x_i - x_j \rVert \ge 2$. Oleh karena itu, masalah Anda meminta untuk diminimalkan$1 + \max_i \lVert y-x_i\rVert$ tunduk pada $\min_{i\ne j} \lVert x_i - x_j\rVert \ge 2$.
Bekerja dengan jarak kuadrat lebih mudah. Jarak kuadrat maksimum$\max_i \lVert y-x_i\rVert^2$ pasti setidaknya rata-rata $\mathop{\mathbb{E}}_i \lVert y-x_i\rVert^2$. Rata-rata ini diminimalkan saat$y$ itu sendiri adalah rata-rata $\mathop{\mathbb{E}}_i x_i$, dalam hal ini sama dengan $\mathop{\mathbb{E}}_i \mathop{\mathbb{E}}_j \lVert x_i-x_j\rVert^2/2$. Setiap istilah dimana$i=j$ berkontribusi $0$ untuk harapan ini, sedangkan setiap istilah di mana $i\ne j$ berkontribusi setidaknya $2$, jadi secara keseluruhan ekspektasi ini setidaknya $2(n-1)/n$. Jadi jarak kuadrat maksimum$\max_i\lVert y-x_i\rVert^2$ setidaknya $2(n-1)/n$ dan dengan demikian $1+r \ge 1+\sqrt{2(n-1)/n}.$ Kita dapat memeriksa bahwa konfigurasi optimal yang disebutkan sebelumnya mencapai batas ini baik dengan perhitungan langsung atau dengan mencatat bahwa konfigurasi tersebut mencapai persamaan di setiap langkah argumen kita.