Нерівність Плюннеке — Ружі

Нері́вності Плюннеке — Ружі — класична лема адитивної комбінаторики. Описує обмеження на багаторазові множини сум за відомих обмежень на аналогічні короткі суми. Наприклад, обмеження на $|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|$

Застосування

Нерівність Плюннеке — Ружі використовують для доведення теореми сум-добутків

Посилання

• М. З. Гараєв, Суми та добутки множин та оцінки раціональних тригонометричних сум у полях простого порядку (рос.)