Русская Википедия:Неравенство Плюннеке — Ружа

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

<math>A+B = \left\lbrace{a+b : a \in A, b \in B}\right\rbrace</math>

<math>n A = \left\lbrace{a_1 + \dots + a_n : a_1, \dots, a_n \in A}\right\rbrace</math>

<math>-A = \left\lbrace{-a : a \in A}\right\rbrace</math>

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

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

Шаблон:Hider</math>, то есть удовлетворяющее требованиям леммы. Тогда, согласно лемме при <math>S=(n-1)A</math>,

<math>|nA+B| = |A+B+(n-1)A| \le K |(n-1)A + B| = |A+B+(n-2)A| \le K^2 |(n-2)A+B| \le ... \le K^{(n-1)} |A+B| \le K^n |A|</math>

Далее воспользуемся неравенством треугольника Ружа.

<math>|B||n A - m A| = |-B||n A - m A| \le |nA + B| |mA + B| \le K^{(n+m)} |A|</math>

}}

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

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

Шаблон:Hider\right) |C+D|</math>.

Это утверждение напрямую следует из неравенства треугольника Ружа

Лемма 2

Если <math>A, B \in G, |A|=|B|, K \in {\mathbb R}</math>, то из <math>|A+B| \le K |A|</math> следует, что существует <math>S \subset A+B</math> такое, что <math>|S| > \frac{|A|}{2}</math> и <math>|A+B+S| < K^3 |A|</math>.

Для доказательства рассмотрим множество <math>S \in A+B</math> элементов, имеющих не менее, чем <math>\frac{|A|}{2K}</math> представлений в виде <math>a+b, a \in A, b \in B</math>. Общее количество пар <math>(a,b) \in A \times B</math> можно оценить сверху как <math>|A|^2 = |A| |B| \le |S| |A| + (|A+B|-|S|) \frac{|A|}{2K} \le |S| |A| + \frac{K |A|^2}{2K} = |S| |A| + \frac{|A^2|}{2}</math>, так что <math>|S| > \frac{|A|}{2}</math>.

При этом если опредеелить функцию <math>\lambda : (A+B) \times (A+B) \to G</math> как <math>\lambda(x,y) = x+y</math>, то для всякого образа вида <math>a+b+s \in A+B+S</math> найдётся не менее <math>\frac{|A|}{2K}</math> различныых прообразов вида <math>(a+b',a'+b)</math>, соответствующих различным представлениям <math>a'+b'=s (a \in A, b \in B)</math>. Важно рассматривать именно такую расстановку слагаемых в прообразе, потому что все пары <math>(a+b,a'+b')</math>, очевидно, одинаковы по определению.

Так как каждый элемент из <math>A+B+S</math> имеет не менее <math>\frac{|A|}{2K}</math> различных прообразов, то

<math>|A+B+S| \frac{|A|}{2K} \le |A+B|^2</math>

<math>|A+B+S| \le \frac{(K |A|)^2}{\left({\frac{|A|}{2K}}\right)} = K^3 |A|</math>

Вывод неравенства из лемм

Для данных <math>A, B \in G</math> рассмотрим множество <math>S</math>, получаемое в лемме 2, и обозначим для леммы 1 <math>C=A+B, D=S</math>. Тогда, по лемме 1,

<math>|(A+B)-(A+B)| \le \left({\frac{|A+B+S|}{|S|}}\right) |A+B+S| \le \frac{(K^3 |A|)^2}{\left({\frac{|A|}{2}}\right)} \le 2 K^6 |A| \le K^8 |A|</math>.

Последнее неравенство верно, поскольку <math>K>\frac{3}{2}</math> при <math>|A|>1</math>.

Итак, <math>|(A-A)+(B-B)| \le K^8 |A|</math> и, повторяя ту же процедуру для <math>(A-A), (B-B)</math> вместо <math>A, B</math>, можно получить <math>|(A+A-A-A)+(B+B-B-B)| \le (K^8)^8 |A-A| \le K^{64} K^8 |A| = K^{72} |A|</math>, и вообще

<math>|nA - nA + nB - nB| \le K^c |A| \Rightarrow |2nA - 2nA + 2nB - 2nB| \le (K^c)^8 |nA - nA| \le K^{(9c)} |A|</math>.

Значит,

<math>|(2^k)A - (2^k)A + (2^k)B - (2^k)B| \le K^{(9^(k+1))} |A|</math>

<math>|n_1 A - n_2 A + n_3 B - n_4 B| \le K^{81 \max(n_1, n_2, n_3, n_4)^{\log_2 {9}}} |A| \le K^{(81 (n_1+n_2+n_3+n_4)^{3.17})} |A|</math>

}}

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

Шаблон:Рамка Пусть <math>(G, +)</math> - абелева группа, <math>X, B_1, \dots, B_k \subset G</math>, <math>|B_i+X| \le K_i |X|, i=1,\dots,k</math>. Тогда <math>|B_1 + \dots + B_k| \le K_1 \dots K_k |X|</math> Тогда существует непустое подмножество <math>X' \subset X</math> такое, что <math>|X'+B_1+\dots+B_k| \le \alpha_1 \dots \alpha_k |X_1|</math> Шаблон:Конец рамки

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

Если <math>|A+A| \le K |A|</math>, то <math>|A-A| \le K |A|</math>

Если <math>|A-A| \le K |A|</math>, то <math>|A+A| \le K^8 |A|</math>

Следовательно, если для величин <math>K \in {\mathbb R}</math> и <math>|A+A|, A \subset {\mathbb F}_p</math> известен порядок роста при росте <math>p</math>, то

<math>|A+A| \le K^{\Theta(1)} |A| \iff |A-A| \le K^{\Theta(1)} |A|</math>

Приложения

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

Ссылки

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