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

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

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

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

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

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

$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|$

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

Лемма

Если $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|$

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

Лемма 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}|$

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

Если $|A+A|\leq K|A|$, то $|A-A|\leq K|A|$

Если $|A-A|\leq K|A|$, то $|A+A|\leq K^{8}|A|$

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

$|A+A|\leq K^{\Theta (1)}|A|\iff |A-A|\leq K^{\Theta (1)}|A|$

Приложения

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

Ссылки

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