Неравенства Плюннеке — Ружа — классическая лемма аддитивной комбинаторики. Описывает ограничения на многократные суммы множеств при известных ограничениях на аналогичные короткие суммы. Например, ограничения на при известных ограничениях на .
Доказательства неравенств Плюннеке — Ружа, как правило, не используют структуру общего множества, которому принадлежат и , а используют только общие аксиомы групповой операции, что делает их верными для произвольных групп (в частности, для множеств натуральных и вещественных чисел, а также остатков от деления на заданное число)
Названы в честь немецкого математика H. PlünneckeH. Pl¨unnecke. Eine zahlentheoretische anwendung der graphtheorie. J. Reine Angew. Math., 243:171–183, 1970 и венгерского математика .
Формулировки
Ниже используются обозначения
Для одного множества
Пусть - абелева группа, . Тогда из следует
Для двух множеств
Для всяких существует такое, что если - группа, , то из
следует
Обобщение на произвольное количество множеств
Пусть - абелева группа, , . Тогда Тогда существует непустое подмножество такое, что I. Z. Ruzsa, “An application of graph theory to additive number theory”, Sci. Ser. A Math. Sci. (N. S.), 3 (1989), 97–109.I. Z. Ruzsa, “Sums of finite sets”, Number theory (New York, 1991–1995), Springer, New York, 1996, 281–293.М. З. Гараев, Суммы и произведения множеств и оценки рациональных тригонометрических сумм в полях простого порядка, УМН, 2010, том 65, выпуск 4(394), DOI: http://dx.doi.org/10.4213/rm9367
Основные следствия
Если , то
Если , то
Следовательно, если для величин и известен порядок роста при росте , то
Приложения
Неравенство Плюннеке-Ружа используется для доказательства теоремы сумм-произведений
Ссылки
М. З. Гараев, Суммы и произведения множеств и оценки рациональных тригонометрических сумм в полях простого порядка
Примечания
Категория:Арифметическая комбинаторика