Проблема Литтлвуда – Оффорда - Littlewood–Offord problem

В математический поле комбинаторная геометрия, то Проблема Литтлвуда – Оффорда проблема определения количества подсуммы набора векторов это падение в данном выпуклый набор. Более формально, если V векторное пространство измерение d, задача состоит в том, чтобы определить, учитывая конечное подмножество векторов S и выпуклое подмножество А, количество подмножеств S чей суммирование в А.

Первый верхняя граница для этой проблемы была доказана (для d = 1 и d = 2) в 1938 г. Джон Эденсор Литтлвуд и А. Сирил Оффорд.^[1] Этот Лемма Литтлвуда – Оффорда. заявляет, что если S это набор п действительные или комплексные числа абсолютная величина хотя бы один и А есть ли диск из радиус один, затем не более ${\displaystyle {\Big (}c\,\log n/{\sqrt {n}}{\Big )}\,2^{n}}$ из 2^п возможные подсуммы S упасть в диск.

В 1945 г. Пол Эрдёш улучшена верхняя оценка для d = От 1 до

${\displaystyle {n \choose \lfloor {n/2}\rfloor }\approx 2^{n}\,{\frac {1}{\sqrt {n}}}}$

с помощью Теорема Спернера.^[2] Эта оценка точна; равенство достигается, когда все векторы в S равны. В 1966 году Клейтман показал, что такая же оценка верна и для комплексных чисел. В 1970 году он расширил это до настройки, когда V это нормированное пространство.^[2]

Предполагать S = {v₁, …, v_п}. Вычитая

${\displaystyle {\frac {1}{2}}\sum _{i=1}^{n}v_{i}}$

от каждой возможной подсуммы (то есть путем изменения начала координат и последующего масштабирования в два раза) проблема Литтлвуда – Оффорда эквивалентна задаче определения количества сумм вида

${\displaystyle \sum _{i=1}^{n}\epsilon _{i}v_{i}}$

что попадают в целевой набор А, куда ${\displaystyle \epsilon _{i}}$ принимает значение 1 или -1. Это превращает проблему в вероятностный один, в котором вопрос заключается в распределении этих случайные векторы, и что можно сказать, ничего не зная о v_я.

Рекомендации

1. Littlewood, J.E .; Оффорд, A.C. (1943). «О числе действительных корней случайного алгебраического уравнения (III)». Рек. Математика. (Мат. Сборник) Н.С.. 12 (54): 277–286.
2. Боллобаш, Бела (1986). Комбинаторика. Кембридж. ISBN  0-521-33703-8.