Archive for Сентябрь 2011

Сечения куба и проблема Басманна-Петти

Сентябрь 25, 2011

Представьте себе, что у нас есть два выпуклых центрально-симметричных относительно нуля компакта A, B \subseteq \mathbb{R}^n. Кроме того, для любой гиперплоскости H, которая проходит через ноль, мера A \cap H не превосходит меры B \cap H. Верно ли, что мера A не превосходит меры B?

Оказывается, что ответ на этот вопрос принципиально зависит от n: для n \leq 4 ответ утвердительный, для n \geq 5 — отрицательный.
Мы покажем, что ответ отрицательный при больших n.

Рассмотрим шар и куб единичного объема. Путем несложных подсчетов легко убедиться, что мера любого сечения шара равна \sqrt{e} \cdot (1 + o(1)). Оказывается, что мера всех сечений куба не превосходит \sqrt{2}. Если мы это докажем, то дело сделано, так как можно слегка уменьшить шар и получить отрицательный ответ на изначальный вопрос.

Итак, осталось доказать, что все сечения куба не превосходят \sqrt{2}. На удивление, это весьма нетривиальный результат, который был получен лишь в 1989 году Боллом (см. [1]).

Итак, пусть задан единичный вектор v \in S^{n - 1}, и мы хотим посчитать меру сечения куба [-1/2, 1/2]^n гиперплоскостью \{(x, v) = 0\}, то есть интеграл

\int_{\{(x, v) = 0\}} \chi_{[-1/2, 1/2]}(\|x\|_{\infty}).

С виду совершенно непонятно, как считать такой интеграл, но, оказывается, что в данном случае нам поможет преобразование Фурье. Слегка обобщим нашу задачу: будем рассматривать не только центральные сечения, но и сечения аффинными плоскостями вида \{(x, v) = t\}. Обозначим

f(t) = \int_{\{(x, v) = t\}} \chi_{[-1/2, 1/2]}(\|x\|_{\infty}).

Вычислим преобразование Фурье f:

\hat{f}(\lambda) = \int_{t} e^{-i \lambda t}\int_{\{(x, v) = t\}} \chi_{[-1/2, 1/2]}(\|x\|_{\infty}) =
= \int_x e^{-i \lambda (x, v)} \chi_{[-1/2, 1/2]}(\|x\|_{\infty}) = \prod_{k=1}^n \int_{-1/2}^{1/2} e^{-i \lambda v_k x} dx =
= \prod_{k=1}^n 2 \cdot \frac{\sin \frac{\lambda v_k}{2}}{\lambda v_k}.

Теперь воспользуемся обратным преобразованием Фурье и вычислим f(0), то есть меру искомого сечения.

f(0) = \frac{1}{2 \pi} \int_{-\infty}^{\infty} \hat{f}(\lambda) d \lambda = \frac{1}{\pi} \int_{-\infty}^{\infty} \prod_{k = 1}^{n} \frac{\sin \lambda v_k}{\lambda v_k} d \lambda

Таким образом, осталось доказать, что для любого единичного v имеет место неравенство \frac{1}{\pi} \int_{-\infty}^{\infty} \prod_{k = 1}^{n} \frac{\sin \lambda v_k}{\lambda v_k} d \lambda \leq \sqrt{2}. Рассмотрим два случая.

Пусть существует k такое, что |v_k| \geq 1 / \sqrt{2} (не умаляя общности, будем считать, что k = 1). Тогда мера проекции сечения на гиперплоскость x_1 = 0 с одной стороны равна мере исходного сечения умножить на |v_k|, а, с другой стороны, очевидно, что не превосходит единицы. Отсюда все получается.

Пусть теперь для всех k выполнено |v_k| \leq 1 / \sqrt{2}. Тогда воспользуемся неравенством Гельдера:

\int_{-\infty}^{\infty} \prod_{k = 1}^{n} \frac{\sin \pi \lambda v_k}{\pi \lambda v_k} d \lambda \leq   \prod_{k=1}^{n} \|u_k\|_{1/v_k^2}, где u_k(\lambda) = \frac{\sin \pi \lambda v_k}{\pi \lambda v_k}.

Нетривиальный факт состоит в том, что
\|u_k\|_{1/v_k^2} \leq 2^{v_k^2 / 2}, если v_k^2 \leq 1 / 2. Это неравенство называется интегральным неравенством Болла и доказывается довольно тяжелыми вычислениями (самое простое доказательство см. в [2]). Но видно, что если его доказать, то все получается.

Реклама

Частичные порядки и геометрия

Сентябрь 25, 2011

Представьте себе, что у нас есть частичный порядок P на \{1, 2, \ldots, n\}. Будем интересоваться множеством полных порядков, которые согласованы с P (обозначим это множество E(P)). Например, если n = 3, P = \{1 < 2, 1 < 3\}, то в E(P) содержатся два элемента — \{1 < 2 < 3\} и \{1 < 3 < 2\}.

С E(P) можно связать политоп K(P) \subseteq \mathbb{R}^n, который устроен так: K(P) = \{f \colon \{1, 2, \ldots, n\} \to [0, 1] \mid f(x) \leq f(y) \; \forall x <_{P} y\}. Важное свойство K(P) состоит в том, что его объем равен \frac{|E(P)|}{n!}. Это можно понять, к примеру, так. Рассмотрим полный порядок \pi \in E(P). Ему соответствует симплекс K(\pi). Очевидны следующие утверждения:

  1. K(\pi) \subseteq K(P),
  2. объем K(\pi) равен 1 / n!,
  3. объединение всех K(\pi) в точности равно K(P).

Пользуясь формулой для объема K(P) можно получить следующие забавные факты.

Во-первых, задача подсчета |E(P)| трудная: более формально, \mathbf{\#P}-трудная (см. [1]). Но, оказывается, для этой задачи есть FPRAS (то есть алгоритм, который по P, \epsilon и \delta выдает число между (1 - \epsilon) |E(P)| и (1 + \epsilon) |E(P)| с вероятностью 1 - \delta и работает за время \mathrm{poly}(n, 1 / \epsilon, 1 / \delta)). Действительно, достаточно построить FPRAS для подсчета объема K(P), а для этого можно воспользоваться FPRAS для оценки объема выпуклого компакта (см. [2]).

Во-вторых, можно рассмотреть такую задачу. Пусть на \{1, 2, \ldots, n\} есть какой-то полный порядок \pi, который мы не знаем, но хотим узнать. Все, что мы знаем — это некоторый частичный порядок P, который согласован с \pi. Пусть есть оракул, у которого можно спрашивать результаты сравнений элементов. Мы хотим за минимальное число вопросов восстановить \pi. Очевидно, что необходимо \Omega(\log |E(P)|) вопросов, так как всего возможно |E(P)| вариантов для \pi. Забавный факт состоит в том, что O(\log |E(P)|) вопросов достаточно. Это можно понять так. Сравнения элементам соответствуют разрезам K(P) специального вида. Таким образом, достаточно доказать, что один из этих разрезов разбивает K(P) на части примерно одинакового объема. Это несложно делается с помощью неравенства Брунна-Минковского (см. [3]).