Неравенство Плюннеке — Ружа

Неравенства Плюннеке — Ружа — классическая лемма аддитивной комбинаторики. Описывает ограничения на многократные суммы множеств при известных ограничениях на аналогичные короткие суммы. Например, ограничения на $|A+A-B-B|$ при известных ограничениях на $|A+B|$.

Доказательства неравенств Плюннеке — Ружа, как правило, не используют структуру общего множества, которому принадлежат $A$ и $B$, а используют только общие аксиомы групповой операции, что делает их верными для произвольных групп (в частности, для множеств натуральных и вещественных чисел, а также остатков от деления на заданное число)

Названы в честь немецкого математика H. Plünnecke и венгерского математика Шаблон:Не переведено 5.

Формулировки

Ниже используются обозначения

$A+B=\left\{a+b:a\in A,b\in B\right\}$

$nA=\left\{a_1+\dots +a_n:a_1,\dots ,a_n\in A\right\}$

$-A=\left\{-a:a\in A\right\}$

Для одного множества

Шаблон:Рамка Пусть $(G,+)$ - абелева группа, $A\subset G,K\in ℝ$. Тогда из $|A+A|\le K|A|$ следует $|nA-mA|<K^{n+m}|A|$ Шаблон:Конец рамки

Для двух множеств

Шаблон:Рамка Для всяких $n_1,n_2,n_3,n_4\ge 0$ существует $c=c(n_1,n_2,n_3,n_4)$ такое, что если $(G,+)$ - группа, $A,B\subset G,|A|=|B|>1$, $K\in ℝ$ то из $|A+B|\le K|A|$ следует $|n_{1}A+n_{2}A-n_{3}B-n_{4}B|\le K^c|A|$ Шаблон:Конец рамки

Шаблон:Hider

Обобщение на произвольное количество множеств

Шаблон:Рамка Пусть $(G,+)$ - абелева группа, $X,B_1,\dots ,B_k\subset G$, $|B_i+X|\le K_i|X|,i=1,\dots ,k$. Тогда $|B_1+\dots +B_k|\le K_1\dots K_k|X|$ Тогда существует непустое подмножество $X^{\prime }\subset X$ такое, что $|X^{\prime }+B_1+\dots +B_k|\le {\alpha }_1\dots {\alpha }_k|X_1|$ Шаблон:Конец рамки

Основные следствия

Если $|A+A|\le K|A|$, то $|A-A|\le K|A|$

Если $|A-A|\le K|A|$, то $|A+A|\le K^8|A|$

Следовательно, если для величин $K\in ℝ$ и $|A+A|,A\subset {𝔽}_p$ известен порядок роста при росте $p$, то

$|A+A|\le K^{\mathrm{\Theta }(1)}|A|⟺|A-A|\le K^{\mathrm{\Theta }(1)}|A|$

Приложения

Неравенство Плюннеке-Ружа используется для доказательства теоремы сумм-произведений

Ссылки

• М. З. Гараев, Суммы и произведения множеств и оценки рациональных тригонометрических сумм в полях простого порядка Шаблон:Wayback