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

Неравенства Плюннеке — Ружа  — неравенства из областиаддитивной комбинаторики, описывающие ограничения на многократные суммымножеств при известных ограничениях на аналогичные короткие суммы.Например, ограничения на |A+ABB| при известных ограничениях на|A+B|.
 Доказательства неравенств Плюннеке — Ружа, как правило, не используютструктуру общего множества, которому принадлежат A и B, а используюттолько общие аксиомы групповой операции, что делает их верными дляпроизвольных групп (в частности, для множеств натуральных и вещественныхчисел, а также остатков от деления на заданное число)
 Названы в честь немецкого математика H. Plünnecke и венгерскогоматематика .

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


 Ниже используются обозначения
A+B={a+b:aA,bB}
nA={a1++an:a1,,anA}
A={a:aA}

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


 Пусть (G,+) - группа, AG,KR. Тогда из|A+A|K|A| следует |nAmA|<Kn+m|A|

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


 Для всяких n1,n2,n3,n40 существует c=c(n1,n2,n3,n4)такое, что если (G,+) - группа, A,BG,|A|=|B|>1,KR то из |A+B|K|A| следует|n1A+n2An3Bn4B|Kc|A|
 \} A \{le K\^\{(81(n\_1+n\_2+n\_3+n\_4)\^\{3.17\})\} A
 \}\}

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


 Пусть (G,+) - группа, X,B1,,BkG,|Bi+X|Ki|X|,i=1,,k. Тогда|B1++Bk|K1Kk|X| Тогда существует непустоеподмножество XX такое, что|X+B1++Bk|α1αk|X1|

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


 Если |A+A|K|A|, то |AA|K|A|
 Если |AA|K|A|, то |A+A|K8|A|
 Следовательно, если для величин KR и|A+A|,AFp известен порядок роста при росте p,то
|A+A|KΘ(1)|A||AA|KΘ(1)|A|

Приложения


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