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

Нері́вності Плюннеке — Ружі — класична лема адитивної комбінаторики. Описує обмеження на багаторазові множини сум за відомих обмежень на аналогічні короткі суми. Наприклад, обмеження на ${\displaystyle |A+A-B-B|}$ за відомих обмежень на ${\displaystyle |A+B|}$.

У доведеннях нерівностей Плюннеке — Ружі зазвичай не використовують структуру спільної множини, якій належать ${\displaystyle A}$ і ${\displaystyle B}$, а використовують тільки загальні аксіоми групової операції, що робить їх істинними для довільних груп (зокрема, для множин натуральних і дійсних чисел, а також остач від ділення на дане число).

Названі на честь німецького математика H. Plünnecke та угорського математика ^[en].

Формулювання

Нижче використовуються позначення

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

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

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

Для однієї множини

Нехай ${\displaystyle (G,+)}$ — абелева група, ${\displaystyle A\subset G,K\in {\mathbb {R} }}$. Тоді з ${\displaystyle |A+A|\leq K|A|}$ випливає ${\displaystyle |nA-mA|<K^{n+m}|A|}$

Доведення  

Лема

Якщо ${\displaystyle A,B,S\in G,|A+B|\leq K|B|,\forall Z\subset B(Z\not =B):\ |A+Z|\geq K|Z|}$, то ${\displaystyle |A+B+S|\leq K|B+S|}$.

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

Розглянемо множину ${\displaystyle Z_{x}=\left\lbrace {b+x\in B+S':b\in B}\right\rbrace }$. Якщо ${\displaystyle Z_{x}=B}$, то ${\displaystyle |A+B+S|=|A+B+S'|\leq K|B+S'|=K|B+S|}$. Інакше

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

${\displaystyle |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}|)}$

Причому, за визначенням ${\displaystyle Z_{x}}$,

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

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

${\displaystyle |A+B+S|\leq K|B+S|}$

Виведення теореми з леми

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

${\displaystyle |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|}$

Далі використаємо нерівність трикутника Ружі.

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

Для двох множин

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

Доведення  

Лема 1

Якщо ${\displaystyle C,D\in G}$, то ${\displaystyle |C-C|<\left({\frac {|C+D|}{|D|}}\right)|C+D|}$.

Це твердження випливає безпосередньо з нерівності трикутника Ружі.

Лема 2

Якщо ${\displaystyle A,B\in G,|A|=|B|,K\in {\mathbb {R} }}$, то з ${\displaystyle |A+B|\leq K|A|}$ випливає, що існує ${\displaystyle S\subset A+B}$ така, що ${\displaystyle |S|>{\frac {|A|}{2}}}$ і ${\displaystyle |A+B+S|<K^{3}|A|}$.

Для доведення розглянемо множину ${\displaystyle S\in A+B}$ елементів, які мають не менше, ніж ${\displaystyle {\frac {|A|}{2K}}}$ подань у вигляді ${\displaystyle a+b,a\in A,b\in B}$. Загальне число пар ${\displaystyle (a,b)\in A\times B}$ можна оцінити зверху як ${\displaystyle |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}}}$, так що ${\displaystyle |S|>{\frac {|A|}{2}}}$.

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

Оскільки кажен елемент із ${\displaystyle A+B+S}$ має не менше ${\displaystyle {\frac {|A|}{2K}}}$ різних прообразів, то

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

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

Виведення нерівності з лем

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

${\displaystyle |(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|}$.

Остання нерівність істинна, оскільки ${\displaystyle K>{\frac {3}{2}}}$ при ${\displaystyle |A|>1}$.

Отжє, ${\displaystyle |(A-A)+(B-B)|\leq K^{8}|A|}$ і, повторюючи ту саму процедуру для ${\displaystyle (A-A),(B-B)}$ замість ${\displaystyle A,B}$, можна отримати ${\displaystyle |(A+A-A-A)+(B+B-B-B)|\leq (K^{8})^{8}|A-A|\leq K^{64}K^{8}|A|=K^{72}|A|}$, і взагалі

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

Значить,

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

${\displaystyle |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|}$

Узагальнення на довільну кількість множин

Нехай ${\displaystyle (G,+)}$ — абелева група, ${\displaystyle X,B_{1},\dots ,B_{k}\subset G}$, ${\displaystyle |B_{i}+X|\leq K_{i}|X|,i=1,\dots ,k}$. Тоді ${\displaystyle |B_{1}+\dots +B_{k}|\leq K_{1}\dots K_{k}|X|}$ Тоді існує непорожня підмножина ${\displaystyle X'\subset X}$ така, що ${\displaystyle |X'+B_{1}+\dots +B_{k}|\leq \alpha _{1}\dots \alpha _{k}|X_{1}|}$

Основні наслідки

Якщо ${\displaystyle |A+A|\leq K|A|}$, то ${\displaystyle |A-A|\leq K|A|}$

Якщо ${\displaystyle |A-A|\leq K|A|}$, то ${\displaystyle |A+A|\leq K^{8}|A|}$

Отже, якщо для величин ${\displaystyle K\in {\mathbb {R} }}$ і ${\displaystyle |A+A|,A\subset {\mathbb {F} }_{p}}$ відомий порядок зростання при зростанні ${\displaystyle p}$, то

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

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

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

Примітки

1. H. Pl¨unnecke. Eine zahlentheoretische anwendung der graphtheorie. J. Reine Angew. Math., 243:171–183, 1970
2. Текстовий виклад лекції Гаральда Гельфготта в СПбДУ^{[недоступне посилання]}
3. Лекция Гаральда Гельфготта в СПбДУ
4. . Архів оригіналу за 6 лютого 2015. Процитовано 8 жовтня 2017.
5. I. Z. Ruzsa, «An application of graph theory to additive number theory», Sci. Ser. A Math. Sci. (N. S.), 3 (1989), 97–109.
6. I. Z. Ruzsa, «Sums of finite sets», Number theory (New York, 1991—1995), Springer, New York, 1996, 281—293.
7. М. З. Гараев, Суммы и произведения множеств и оценки рациональных тригонометрических сумм в полях простого порядка, УМН, 2010, том 65, выпуск 4(394), DOI: http://dx.doi.org/10.4213/rm9367

Посилання

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