Задача Литтлвуда – Оффорда

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

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

В 1945 г. Пол Эрдеш улучшил верхнюю границу для d = 1 до

$(n\; \lfloor \; n\; /\; 2\; \rfloor )\; \approx \; 2\; n\; 1\; n\; \{\backslash \; displaystyle\; \{n\; \backslash \; choose\; \backslash \; lfloor\; \{n\; /\; 2\}\; \backslash \; rfloor\}\; \backslash \; приблизительно\; 2\; ^\; \{n\}\; \backslash ,\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{n\}\}\}\}$

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

Предположим, S = {v 1,…, v n }. Вычитая

$1\; 2\; \sum \; i\; =\; 1\; nvi\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; v\_\; \{i\}\}$

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

$\sum \; i\; =\; 1\; n\; ϵ\; ivi\; \{\backslash \; displaystyle\; \backslash \; сумма\; \_\; \{i\; =\; 1\}\; ^\; \{n\}\; \backslash \; epsilon\; \_\; \{i\}\; v\_\; \{i\}\}$

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

1. ^Литтлвуд, Дж. Э.; Оффорд, A.C. (1943). «О числе действительных корней случайного алгебраического уравнения (III)». Рек. Математика. (Мат. Сборник) Н.С. 12 (54): 277–286.
2. ^ Bollobás, Béla (1986). Комбинаторика. Кембридж. ISBN 0-521-33703-8.