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

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

При этом если опредеелить функцию ${\displaystyle \lambda$ как $\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]

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

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

Примечания

H. Pl¨unnecke. Eine zahlentheoretische anwendung der graphtheorie. J. Reine Angew. Math., 243:171–183, 1970
I. Z. Ruzsa, “An application of graph theory to additive number theory”, Sci. Ser. A Math. Sci. (N. S.), 3 (1989), 97–109.
Текстовое изложение лекции Харальда Хельфготта в СПбГУ (недоступная ссылка)
Лекция Харальда Хельфготта в СПбГУ
Boaz Barak, Luca Trevisan, Avi Wigderson, "Mini course of additive combinatorics" (неопр.) (недоступная ссылка). Дата обращения: 8 октября 2017. Архивировано 6 февраля 2015 года.
I. Z. Ruzsa, “Sums of finite sets”, Number theory (New York, 1991–1995), Springer, New York, 1996, 281–293.
М. З. Гараев, Суммы и произведения множеств и оценки рациональных тригонометрических сумм в полях простого порядка, УМН, 2010, том 65, выпуск 4(394), DOI: http://dx.doi.org/10.4213/rm9367

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] H. Pl¨unnecke. Eine zahlentheoretische anwendung der graphtheorie. J. Reine Angew. Math., 243:171–183, 1970

[ruzsa1989-2] I. Z. Ruzsa, “An application of graph theory to additive number theory”, Sci. Ser. A Math. Sci. (N. S.), 3 (1989), 97–109.

[3] Текстовое изложение лекции Харальда Хельфготта в СПбГУ (недоступная ссылка)

[4] Лекция Харальда Хельфготта в СПбГУ

[5] Boaz Barak, Luca Trevisan, Avi Wigderson, "Mini course of additive combinatorics" (неопр.) (недоступная ссылка). Дата обращения: 8 октября 2017. Архивировано 6 февраля 2015 года.

[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