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

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

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

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

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

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

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

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

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

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

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