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

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

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

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

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

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

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

$nA=\left\lbrace {a_{1}+\dots +a_{n}:a_{1},\dots ,a_{n}\in A}\right\rbrace$

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

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

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

Доказательство^[3]^[4]

Лемма

Если $A,B,S\in G,|A+B|\leq K|B|,\forall Z\subset B(Z\not =B):\ |A+Z|\geq K|Z|$ , то $|A+B+S|\leq K|B+S|$ .

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

Рассмотрим множество $Z_{x}=\left\lbrace {b+x\in B+S':b\in B}\right\rbrace$ . Если $Z_{x}=B$ , то $|A+B+S|=|A+B+S'|\leq K|B+S'|=K|B+S|$ . Иначе

$A+B+S=(A+B+S')\cup ((A+B+\left\lbrace {x}\right\rbrace )\setminus (A+Z_{x}+\left\lbrace {x}\right\rbrace ))$

$|A+B+S|=|A+B+S'|+|A+B|-|A+Z_{x}|\leq K|B+S'|+K|B|-K|Z_{x}|=K(|B+S'|+|B|-|Z_{x}|)$

Причём, по определению $Z_{x}$ ,

$B+S=(B+S')\cup ((B\setminus Z_{x})+\left\lbrace {x}\right\rbrace )$

$|B+S|=|B+S'|+|B|-|Z_{x}|$

$|A+B+S|\leq K|B+S|$

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

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

$|nA+B|=|A+B+(n-1)A|\leq K|(n-1)A+B|=|A+B+(n-2)A|\leq K^{2}|(n-2)A+B|\leq ...\leq K^{(n-1)}|A+B|\leq K^{n}|A|$

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

$|B||nA-mA|=|-B||nA-mA|\leq |nA+B||mA+B|\leq K^{(n+m)}|A|$

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

Для всяких $n_{1},n_{2},n_{3},n_{4}\geq 0$ существует $c=c(n_{1},n_{2},n_{3},n_{4})$ такое, что если $(G,+)$ - группа, $A,B\subset G,|A|=|B|>1$ , $K\in {\mathbb {R} }$ то из $|A+B|\leq K|A|$ следует $|n_{1}A+n_{2}A-n_{3}B-n_{4}B|\leq K^{c}|A|$

Доказательство^[5]

Лемма 1

Если $C,D\in G$ , то $|C-C|<\left({\frac {|C+D|}{|D|}}\right)|C+D|$ .

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

Лемма 2

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

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

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

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

$|A+B+S|{\frac {|A|}{2K}}\leq |A+B|^{2}$

$|A+B+S|\leq {\frac {(K|A|)^{2}}{\left({\frac {|A|}{2K}}\right)}}=K^{3}|A|$

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

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

$|(A+B)-(A+B)|\leq \left({\frac {|A+B+S|}{|S|}}\right)|A+B+S|\leq {\frac {(K^{3}|A|)^{2}}{\left({\frac {|A|}{2}}\right)}}\leq 2K^{6}|A|\leq K^{8}|A|$ .

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

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

$|nA-nA+nB-nB|\leq K^{c}|A|\Rightarrow |2nA-2nA+2nB-2nB|\leq (K^{c})^{8}|nA-nA|\leq K^{(9c)}|A|$ .

Значит,

$|(2^{k})A-(2^{k})A+(2^{k})B-(2^{k})B|\leq K^{(9^{(}k+1))}|A|$

$|n_{1}A-n_{2}A+n_{3}B-n_{4}B|\leq K^{81\max(n_{1},n_{2},n_{3},n_{4})^{\log _{2}{9}}}|A|\leq K^{(81(n_{1}+n_{2}+n_{3}+n_{4})^{3.17})}|A|$

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

Пусть $(G,+)$ - абелева группа, $X,B_{1},\dots ,B_{k}\subset G$ , $|B_{i}+X|\leq K_{i}|X|,i=1,\dots ,k$ . Тогда $|B_{1}+\dots +B_{k}|\leq K_{1}\dots K_{k}|X|$ Тогда существует непустое подмножество $X'\subset X$ такое, что $|X'+B_{1}+\dots +B_{k}|\leq \alpha _{1}\dots \alpha _{k}|X_{1}|$ ^[2]^[6]^[7]