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

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

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

Названі на честь німецького математика H. Plünnecke та угорського математика Шаблон:Не перекладено.

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

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

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

$nA=\left\{a_1+\dots +a_n:a_1,\dots ,a_n\in A\right\}$

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

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

Шаблон:РамкаНехай $(G,+)$ — абелева група, $A\subset G,K\in ℝ$. Тоді з $|A+A|\le K|A|$ випливає $|nA-mA|<K^{n+m}|A|$ Шаблон:/рамка Шаблон:Hider

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

Шаблон:РамкаДля будь-яких $n_1,n_2,n_3,n_4\ge 0$ існує $c=c(n_1,n_2,n_3,n_4)$ таке, що якщо $(G,+)$ — група, $A,B\subset G,|A|=|B|>1$, $K\in ℝ$ то з $|A+B|\le K|A|$ випливає $|n_{1}A+n_{2}A-n_{3}B-n_{4}B|\le K^c|A|$ Шаблон:/рамка Шаблон:Hider

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

Шаблон:РамкаНехай $(G,+)$ — абелева група, $X,B_1,\dots ,B_k\subset G$, $|B_i+X|\le K_i|X|,i=1,\dots ,k$. Тоді $|B_1+\dots +B_k|\le K_1\dots K_k|X|$ Тоді існує непорожня підмножина $X^{\prime }\subset X$ така, що $|X^{\prime }+B_1+\dots +B_k|\le {\alpha }_1\dots {\alpha }_k|X_1|$ Шаблон:/рамка

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

Якщо $|A+A|\le K|A|$, то $|A-A|\le K|A|$

Якщо $|A-A|\le K|A|$, то $|A+A|\le K^8|A|$

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

$|A+A|\le K^{\mathrm{\Theta }(1)}|A|⟺|A-A|\le K^{\mathrm{\Theta }(1)}|A|$

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

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

Посилання

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