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

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

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

Названы в честь немецкого математика H. Plünnecke и венгерского математика Имре Ружа.

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

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

[math]\displaystyle{ A+B = \left\lbrace{a+b : a \in A, b \in B}\right\rbrace }[/math]

[math]\displaystyle{ n A = \left\lbrace{a_1 + \dots + a_n : a_1, \dots, a_n \in A}\right\rbrace }[/math]

[math]\displaystyle{ -A = \left\lbrace{-a : a \in A}\right\rbrace }[/math]

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

Пусть [math]\displaystyle{ (G, +) }[/math] - абелева группа, [math]\displaystyle{ A \subset G, K \in {\mathbb R} }[/math]. Тогда из [math]\displaystyle{ |A+A| \le K |A| }[/math] следует [math]\displaystyle{ |nA-mA| \lt K^{n+m} |A| }[/math]

Доказательство

Лемма

Если [math]\displaystyle{ A,B,S \in G, |A+B| \le K |B|, \forall Z \subset B (Z \not = B):\ |A+Z| \ge K|Z| }[/math], то [math]\displaystyle{ |A+B+S| \le K |B+S| }[/math].

Лемма доказывается индукцией по размеру [math]\displaystyle{ S }[/math]. Для [math]\displaystyle{ |S|=1 }[/math] утверждение очевидно. Далее, для некоторого [math]\displaystyle{ x \in S }[/math] обозначим [math]\displaystyle{ S' = S \setminus \left\lbrace{x}\right\rbrace }[/math]. По предположению индукции, [math]\displaystyle{ |A+B+S'| \le K |B+S'| }[/math].

Рассмотрим множество [math]\displaystyle{ Z_x = \left\lbrace{b+x \in B+S' : b \in B}\right\rbrace }[/math]. Если [math]\displaystyle{ Z_x=B }[/math], то [math]\displaystyle{ |A+B+S|=|A+B+S'| \le K |B+S'| = K |B+S| }[/math]. Иначе

[math]\displaystyle{ A+B+S = (A+B+S') \cup ((A+B+\left\lbrace{x}\right\rbrace) \setminus (A+Z_x+\left\lbrace{x}\right\rbrace)) }[/math]

[math]\displaystyle{ |A+B+S| = |A+B+S'| + |A+B| - |A+Z_x| \le K |B+S'| + K |B| - K |Z_x| = K (|B+S'|+|B|-|Z_x|) }[/math]

Причём, по определению [math]\displaystyle{ Z_x }[/math],

[math]\displaystyle{ B+S = (B+S') \cup ((B \setminus Z_x) + \left\lbrace{x}\right\rbrace) }[/math]

[math]\displaystyle{ |B+S| = |B+S'| + |B| - |Z_x| }[/math]

[math]\displaystyle{ |A+B+S| \le K |B+S| }[/math]

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

Выберем подмножество [math]\displaystyle{ B = \arg \min \limits_{B \subset A, |B| \ge 1} {\frac{|A+B|}{|B|}} }[/math], то есть удовлетворяющее требованиям леммы. Тогда, согласно лемме при [math]\displaystyle{ S=(n-1)A }[/math],

[math]\displaystyle{ |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]\displaystyle{ |B||n A - m A| = |-B||n A - m A| \le |nA + B| |mA + B| \le K^{(n+m)} |A| }[/math]

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

Для всяких [math]\displaystyle{ n_1,n_2,n_3,n_4 \ge 0 }[/math] существует [math]\displaystyle{ c=c(n_1,n_2,n_3,n_4) }[/math] такое, что если [math]\displaystyle{ (G, +) }[/math] - группа, [math]\displaystyle{ A,B \subset G, |A|=|B|\gt 1 }[/math], [math]\displaystyle{ K \in {\mathbb R} }[/math] то из [math]\displaystyle{ |A+B| \le K |A| }[/math] следует [math]\displaystyle{ |n_1 A + n_2 A - n_3 B - n_4 B| \le K^c |A| }[/math]

Доказательство

Лемма 1

Если [math]\displaystyle{ C, D \in G }[/math], то [math]\displaystyle{ |C-C| \lt \left({\frac{|C+D|}{|D|}}\right) |C+D| }[/math].

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

Лемма 2

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

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

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

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

[math]\displaystyle{ |A+B+S| \frac{|A|}{2K} \le |A+B|^2 }[/math]

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

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

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

[math]\displaystyle{ |(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]\displaystyle{ K\gt \frac{3}{2} }[/math] при [math]\displaystyle{ |A|\gt 1 }[/math].

Итак, [math]\displaystyle{ |(A-A)+(B-B)| \le K^8 |A| }[/math] и, повторяя ту же процедуру для [math]\displaystyle{ (A-A), (B-B) }[/math] вместо [math]\displaystyle{ A, B }[/math], можно получить [math]\displaystyle{ |(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]\displaystyle{ |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]\displaystyle{ |(2^k)A - (2^k)A + (2^k)B - (2^k)B| \le K^{(9^(k+1))} |A| }[/math]

[math]\displaystyle{ |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]\displaystyle{ (G, +) }[/math] - абелева группа, [math]\displaystyle{ X, B_1, \dots, B_k \subset G }[/math], [math]\displaystyle{ |B_i+X| \le K_i |X|, i=1,\dots,k }[/math]. Тогда [math]\displaystyle{ |B_1 + \dots + B_k| \le K_1 \dots K_k |X| }[/math] Тогда существует непустое подмножество [math]\displaystyle{ X' \subset X }[/math] такое, что [math]\displaystyle{ |X'+B_1+\dots+B_k| \le \alpha_1 \dots \alpha_k |X_1| }[/math]

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

Если [math]\displaystyle{ |A+A| \le K |A| }[/math], то [math]\displaystyle{ |A-A| \le K |A| }[/math]

Если [math]\displaystyle{ |A-A| \le K |A| }[/math], то [math]\displaystyle{ |A+A| \le K^8 |A| }[/math]

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

[math]\displaystyle{ |A+A| \le K^{\Theta(1)} |A| \iff |A-A| \le K^{\Theta(1)} |A| }[/math]

Приложения

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

Ссылки

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