Шары в гильбертовом пространстве
Недавно я заметил интересный факт, который приводит к, возможно, сложному вопросу. Если$n$ натуральное число, пусть $k_n$ быть наименьшим числом $k$ такой, что открытый шар радиуса $k$ в реальном гильбертовом пространстве достаточно большой или бесконечной размерности содержит $n$ попарно непересекающиеся открытые шары радиуса 1. (Размерность гильбертова пространства не имеет значения, пока она не меньше $n-1$ поскольку его можно заменить аффинным подпространством, натянутым на центры шаров.) Очевидно, что $k_1=1$ и $k_2=2$, и легко увидеть, что $k_3=1+\frac{2}{\sqrt{3}}\approx 2.1547$. Интересен тот факт, что$k_n\leq 1+\sqrt{2}\approx 2.414$ для всех $n$, поскольку в бесконечномерном гильбертовом пространстве открытый шар этого радиуса содержит бесконечно много попарно непересекающихся открытых шаров радиуса 1 (рассмотрим шары с центрами в точках ортонормированного базиса). Очевидные вопросы: (1) Что такое$k_n$? Это может быть известно, но выглядит трудным, поскольку связано с упаковкой сфер. (2) Есть$k_n$ даже строго возрастает $n$? (3) Есть$k_n<1+\sqrt{2}$ для всех $n$, или они равны при достаточно больших $n$? (4) Верно ли вообще, что$\sup_n k_n=1+\sqrt{2}$? Даже не совсем очевидно, что$k_n$ существует для всех $n$, т. е. существует наименьшее $k$ для каждого $n$, но должен быть аргумент компактности, подтверждающий это. Мне интересно, что числа$1+\frac{2}{\sqrt{3}}$ и $1+\sqrt{2}$настолько близки, но поведение мячей настолько разительно отличается. Я полагаю, этот вопрос также интересен для гильбертовых пространств меньшей размерности: пусть$k_{n,d}$ быть самым маленьким $k$ такой, что открытый шар радиуса $k$ в гильбертовом пространстве размерности $d$ содержит $n$ попарно непересекающиеся открытые шары радиуса 1. Тогда $k_{n,d}$ стабилизируется на $k_n$ за $d\geq n-1$. Что$k_{n,d}$? (Это будет намного сложнее, так как это фактически вопрос упаковки сфер, если$n>>d$.)
Ответы
Для удобства обозначений напишу математическое ожидание $\mathop{\mathbb{E}}_i t_i$ для обозначения среднего $(\sum_{i=1}^n t_i)/n$.
Если я правильно понимаю вашу конструкцию, у вас непересекающиеся шары радиуса $1$ сосредоточен на $x_i = \sqrt{2} e_i$ содержится в шаре радиуса $1+\sqrt{2}$ сосредоточен на $y = 0$. Эта конструкция, которая ставит$n$ шары, плотно упакованные в вершинах регулярного симплекса, оптимальны по позициям $x_i$. Чтобы получить точную оптимальную границу для вашей проблемы, вы должны выбрать$y=\mathop{\mathbb{E}}_i x_i$ получить радиус $$\boxed{k_n = 1+\sqrt{2 (1-1/n)}}.$$
Утверждение, что размещение $x_i$ в вершинах регулярного $(n-1)$-простой и $y$в центроиде этого симплекса является оптимальным, что было многократно доказано ранее во многих различных контекстах. Например, это подразумевается границей, известной по различным подстрокам « симплексной границы Велча-Ранкина » в теории фреймов. Вот простое прямое доказательство:
По неравенству треугольника шар радиуса $1+r$ сосредоточен на $y$ содержит шар радиуса $1$ сосредоточен на $x_i$ если только $\lVert x-y\rVert \le r$. Два шара радиуса$1$ сосредоточен на $x_i$ и $x_j$ не пересекаются тогда и только тогда $\lVert x_i - x_j \rVert \ge 2$. Поэтому ваша проблема просит минимизировать$1 + \max_i \lVert y-x_i\rVert$ при условии $\min_{i\ne j} \lVert x_i - x_j\rVert \ge 2$.
Работать с квадратами расстояний проще. Максимальное квадратное расстояние$\max_i \lVert y-x_i\rVert^2$ конечно, по крайней мере, средний $\mathop{\mathbb{E}}_i \lVert y-x_i\rVert^2$. Это среднее минимизируется, когда$y$ сам по себе средний $\mathop{\mathbb{E}}_i x_i$, в этом случае он равен $\mathop{\mathbb{E}}_i \mathop{\mathbb{E}}_j \lVert x_i-x_j\rVert^2/2$. Каждый термин, где$i=j$ способствует $0$ к этому ожиданию, а каждый член, где $i\ne j$ вносит как минимум $2$, поэтому в целом это ожидание не менее $2(n-1)/n$. Таким образом, максимальное квадратичное расстояние$\max_i\lVert y-x_i\rVert^2$ по крайней мере $2(n-1)/n$ и поэтому $1+r \ge 1+\sqrt{2(n-1)/n}.$ Мы можем проверить, что оптимальная конфигурация, упомянутая ранее, достигает этой границы, либо прямым вычислением, либо отметив, что она достигает равенства на каждом шаге нашего аргумента.