Неравенство Плюнеке

В аддитивной комбинаторике неравенство Плюнеке -Рузсы представляет собой неравенство, которое ограничивает размер различных сумм множества. $B$ , учитывая, что существует другой набор $A$ так что $A+B$ не намного больше, чем $A$ . Несколько более слабая версия этого неравенства была первоначально доказана и опубликована Хельмутом Плюнеке (1970). ^{[ 1 ]} Имре Ружа (1989) ^{[ 2 ]} позже опубликовал более простое доказательство текущей, более общей версии неравенства. Это неравенство является решающим шагом в доказательстве теоремы Фреймана .

Заявление

Следующее обозначение суммы является стандартным в аддитивной комбинаторике. Для подмножеств $A$ и $B$ абелевой группы и натурального числа $k$ , определены следующие:

$A+B=\{a+b:a\in A,b\in B\}$
$A-B=\{a-b:a\in A,b\in B\}$
$kA=\underbrace {A+A+\cdots +A} _{k{\text{ times}}}$

Набор $A+B$ известен сумма как $A$ и $B$ .

Неравенство Плюнеке-Рузы

Наиболее часто цитируемая версия утверждения неравенства Плюннеке – Ружи следующая. ^{[ 3 ]}

Теорема (неравенство Плюнеке-Рузы) — Если $A$ и $B$ являются конечными подмножествами абелевой группы и $K$ является константой, так что $|A+B|\leq K|A|$ , то для всех неотрицательных целых чисел $m$ и $n$ ,

|mB-nB|\leq K^{m+n}|A|.

Это часто используется, когда $A=B$ , и в этом случае константа $K=|2A|/|A|$ известна как удвоения константа $A$ . В этом случае неравенство Плюнеке – Ружи утверждает, что суммы, сформированные из набора с малой константой удвоения, также должны быть малы.

Версия этого неравенства, первоначально доказанная Плюннеке (1970). ^{[ 1 ]} немного слабее.

Теорема (неравенство Плюнеке) — Предположим , $A$ и $B$ являются конечными подмножествами абелевой группы и $K$ является константой, так что $|A+B|\leq K|A|$ . Тогда для всех неотрицательных целых чисел $m$ , $|mB|\leq K^{m}|A|.$

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

Неравенство треугольника Ружи

Неравенство треугольника Рузсы является важным инструментом, который используется для обобщения неравенства Плюнеке на неравенство Плюнеке – Ружи. Его заявление:

Теорема (неравенство треугольника Рузсы) — Если $A$ , $B$ , и $C$ являются конечными подмножествами группы, то

|A||B-C|\leq |A-B||A-C|.

Доказательство неравенства Плюнеке-Ружсы.

Следующее простое доказательство неравенства Плюнеке – Ружи принадлежит Петридису (2014). ^{[ 4 ]}

Лемма: Пусть $A$ и $B$ — конечные подмножества абелевой группы $G$ . Если $X\subseteq A$ является непустым подмножеством, которое минимизирует значение $K'=|X+B|/|X|$ , то для всех конечных подмножеств $C\subset G$ ,

|X+B+C|\leq K'|X+C|.

Доказательство. Это демонстрируется индукцией по размеру $|C|$ . Для базового случая $|C|=1$ , Обратите внимание, что $S+C$ это просто перевод $S$ для любого $S\subseteq G$ , так

|X+B+C|=|X+B|=K'|X|=K'|X+C|.

Для индуктивного шага предположим, что неравенство выполнено для всех $C\subseteq G$ с $|C|\leq n$ для некоторого положительного целого числа $n$ . Позволять $C$ быть подмножеством $G$ с $|C|=n+1$ , и пусть $C=C'\sqcup \{\gamma \}$ для некоторых $\gamma \in C$ . (В частности, неравенство справедливо для $C'$ .) Наконец, пусть $Z=\{x\in X:x+B+\{\gamma \}\subseteq X+B+C'\}$ . Определение $Z$ подразумевает, что $Z+B+\{\gamma \}\subseteq X+B+C'$ . Таким образом, по определению этих множеств,

X+B+C=(X+B+C')\cup ((X+B+\{\gamma \})\backslash (Z+B+\{\gamma \})).

Следовательно, учитывая размеры множеств,

{\begin{aligned}|X+B+C|&\leq |X+B+C'|+|(X+B+\{\gamma \})\backslash (Z+B+\{\gamma \})|\\&=|X+B+C'|+|X+B+\{\gamma \}|-|Z+B+\{\gamma \}|\\&=|X+B+C'|+|X+B|-|Z+B|.\end{aligned}}

Определение $Z$ подразумевает, что $Z\subseteq X\subseteq A$ , поэтому по определению $X$ , $|Z+B|\geq K'|Z|$ . Таким образом, применяя индуктивную гипотезу о $C'$ и используя определение $X$ ,

{\begin{aligned}|X+B+C|&\leq |X+B+C'|+|X+B|-|Z+B|\\&\leq K'|X+C'|+|X+B|-|Z+B|\\&\leq K'|X+C'|+K'|X|-|Z+B|\\&\leq K'|X+C'|+K'|X|-K'|Z|\\&=K'(|X+C'|+|X|-|Z|).\end{aligned}}

Чтобы ограничить правую часть этого неравенства, положим $W=\{x\in X:x+\gamma \in X+C'\}$ . Предполагать $y\in X+C'$ и $y\in X+\{\gamma \}$ , то существует $x\in X$ такой, что $x+\gamma =y\in X+C'$ . Таким образом, по определению $x\in W$ , так $y\in W+\{\gamma \}$ . Следовательно, множества $X+C'$ и $(X+\{\gamma \})\backslash (W+\{\gamma \})$ непересекающиеся. Определения $W$ и $C'$ таким образом подразумевать, что

X+C=(X+C')\sqcup ((X+\{\gamma \})\backslash (W+\{\gamma \})).

Опять же по определению $W\subseteq Z$ , так $|W|\leq |Z|$ . Следовательно,

{\begin{aligned}|X+C|&=|X+C'|+|(X+\{\gamma \})\backslash (W+\{\gamma \})|\\&=|X+C'|+|X+\{\gamma \}|-|W+\{\gamma \}|\\&=|X+C'|+|X|-|W|\\&\geq |X+C'|+|X|-|Z|.\end{aligned}}

Соединение двух приведенных выше неравенств вместе дает

|X+B+C|\leq K'(|X+C'|+|X|-|Z|)\leq K'|X+C|.

Это завершает доказательство леммы.

Чтобы доказать неравенство Плюнеке–Рузсы, возьмем $X$ и $K'$ как в утверждении леммы. Прежде всего необходимо показать, что

|X+nB|\leq K^{n}|X|.

Это можно доказать методом индукции. В базовом случае определения $K$ и $K'$ подразумеваю, что $K'\leq K$ . Таким образом, определение $X$ подразумевает, что $|X+B|\leq K|X|$ . Для индуктивного шага предположим, что это верно для $n=j$ . Применяя лемму с $C=jB$ и индуктивная гипотеза дает

|X+(j+1)B|\leq K'|X+jB|\leq K|X+jB|\leq K^{j+1}|X|.

На этом индукция завершена. Наконец, неравенство треугольника Рузсы дает

|mB-nB|\leq {\frac {|X+mB||X+nB|}{|X|}}\leq {\frac {K^{m}|X|K^{n}|X|}{|X|}}=K^{m+n}|X|.

Потому что $X\subseteq A$ , должно быть так, что $|X|\leq |A|$ . Поэтому,

|mB-nB|\leq K^{m+n}|A|.

Это завершает доказательство неравенства Плюннеке–Ружсы.

Графики Плюннеке

И доказательство Плюнеке неравенства Плюнеке, и оригинальное доказательство Ружи неравенства Плюнеке – Ружи используют метод графов Плюнеке. Графы Плюнеке — это способ отразить аддитивную структуру множеств. $A,A+B,A+2B,\dots$ теоретико-графовым способом ^{[ 5 ]}^{[ 6 ]}

Чтобы определить граф Плюнеке, мы сначала определяем коммутативные графы и слоистые графы:

Определение . граф Ориентированный $G$ называется полукоммутативным , если всякий раз, когда существуют различные $x,y,z_{1},z_{2},\dots ,z_{k}$ такой, что $(x,y)$ и $(y,z_{i})$ находятся края в $G$ для каждого $i$ , то также существуют различные $y_{1},y_{2},\dots ,y_{k}$ так что $(x,y_{i})$ и $(y_{i},z_{i})$ находятся края в $G$ для каждого $i$ .

$G$ называется коммутативным, если он полукоммутативен и граф, образованный перестановкой всех его ребер, также полукоммутативен.

Определение . — Слоистый граф это (ориентированный) граф. $G$ чье множество вершин можно разделить $V_{0}\cup V_{1}\cup \dots \cup V_{m}$ так, чтобы все ребра вошли $G$ из $V_{i}$ к $V_{i+1}$ , для некоторых $i$ .

Определение . Граф Плюнеке — это многослойный граф, который является коммутативным.

Каноническим примером графа Плюннеке является следующий, который показывает, как структура множеств $A,A+B,A+2B,\dots ,A+mB$ образуют граф Плюнеке.

Пример . Позволять $A,B$ являются подмножествами абелевой группы. Тогда пусть $G$ быть многоуровневым графом, так что каждый слой $V_{j}$ является копией $A+jB$ , так что $V_{0}=A$ , $V_{1}=A+B$ , ..., $V_{m}=A+mB$ . Создайте преимущество $(x,y)$ (где $x\in V_{i}$ и $y\in V_{i+1}$ ) всякий раз, когда существует $b\in B$ такой, что $y=x+b$ . (В частности, если $x\in V_{i}$ , затем $x+b\in V_{i+1}$ по определению, поэтому каждая вершина имеет исходящую степень, равную размеру $B$ .) Затем $G$ является графом Плюннеке. Например, чтобы проверить это $G$ полукоммутативен, если $(x,y)$ и $(y,z_{i})$ находятся края в $G$ для каждого $i$ , затем $y-x,z_{i}-y\in B$ . Тогда пусть $y_{i}=x+z_{i}-y$ , так что $y_{i}-x=z_{i}-y\in B$ и $z_{i}-y_{i}=y-x\in B$ . Таким образом, $G$ является полукоммутативным. Аналогично можно проверить, что граф, образованный перестановкой всех ребер $G$ также полукоммутативен, поэтому $G$ является графом Плюннеке.

В графе Плюннеке образ множества $X\subseteq V_{0}$ в $V_{j}$ , написано ${\text{im}}(X,V_{j})$ , определяется как множество вершин в $V_{j}$ до которого можно добраться по пути, начинающемуся из некоторой вершины в $X$ . В частности, в приведенном выше примере ${\text{im}}(X,V_{j})$ это просто $X+jB$ .

Коэффициент увеличения между $V_{0}$ и $V_{j}$ , обозначенный $\mu _{j}(G)$ , затем определяется как минимальный коэффициент, на который изображение набора должно превышать размер исходного набора. Формально,

\mu _{j}(G)=\min _{X\subseteq V_{0},X\neq \emptyset }{\frac {|{\text{im}}(X,V_{j})|}{|X|}}.

Теорема Плюнеке представляет собой следующее утверждение о графах Плюнеке.

Теорема (теорема Плюннеке) — Пусть $G$ быть графом Плюнеке. Затем, $\mu _{j}(G)^{1/j}$ уменьшается в $j$ .

Доказательство теоремы Плюннеке включает в себя технику, известную как «трюк с тензорным произведением», в дополнение к применению теоремы Менгера . ^{[ 5 ]}

Неравенство Плюнеке-Ружсы является довольно прямым следствием теоремы Плюнеке и неравенства треугольника Ружи. Применяя теорему Плюнеке к графику, приведенному в примере, при $j=m$ и $j=1$ , получается, что если $|A+B|/|A|=K$ , то существует $X\subseteq A$ так что $|X+mB|/|X|\leq K^{m}$ . Применяя этот результат еще раз с помощью $X$ вместо $A$ , существует $X'\subseteq X$ так что $|X'+nB|/|X'|\leq K^{n}$ . Тогда по неравенству треугольника Ружи (на $-X',mB,nB$ ),

|mB-nB|\leq |X'+mB||X'+nB|/|X'|\leq K^{m}|X|K^{n}=K^{m+n}|X|,

тем самым доказывая неравенство Плюнеке – Ружи.

См. также

Ссылки

^ Перейти обратно: ^а ^б Плюннеке, Хельмут (1970). «Теоретико-числовое приложение теории графов». Журнал чистой и прикладной математики . 243 : 171–183. дои : 10.1515/crll.1970.243.171 .
^ Ружа, Имре (1989). «Применение теории графов к аддитивной теории чисел». Сайентия, серия А. 3 : 97–109.
^ Кандела, Пабло; Гонсалес-Санчес, Диего; де Ротон, Энн (2019). «Неравенство Плюннеке-Рузсы в компактных абелевых группах». Иберо-американский математический журнал . 35 (7): 2169–2186. arXiv : 1712.07615 . дои : 10.4171/rmi/1116 .
^ Петридис, Гиоргис (2014). «Неравенство Плюннеке – Ружи: обзор». Комбинаторная и аддитивная теория чисел . Спрингерские труды по математике и статистике. Том. 101. С. 229–241. дои : 10.1007/978-1-4939-1601-6_16 . ISBN 978-1-4939-1600-9 .
^ Перейти обратно: ^а ^б Тао, Т.; Ву, В. (2006). Аддитивная комбинаторика . Кембридж: Издательство Кембриджского университета. ISBN 978-0-521-85386-6 .
^ Ружа И., Суммы и структура (PDF) .

[Plu-1] Перейти обратно: ^а ^б Плюннеке, Хельмут (1970). «Теоретико-числовое приложение теории графов». Журнал чистой и прикладной математики . 243 : 171–183. дои : 10.1515/crll.1970.243.171 .

[2] Ружа, Имре (1989). «Применение теории графов к аддитивной теории чисел». Сайентия, серия А. 3 : 97–109.

[3] Кандела, Пабло; Гонсалес-Санчес, Диего; де Ротон, Энн (2019). «Неравенство Плюннеке-Рузсы в компактных абелевых группах». Иберо-американский математический журнал . 35 (7): 2169–2186. arXiv : 1712.07615 . дои : 10.4171/rmi/1116 .

[4] Петридис, Гиоргис (2014). «Неравенство Плюннеке – Ружи: обзор». Комбинаторная и аддитивная теория чисел . Спрингерские труды по математике и статистике. Том. 101. С. 229–241. дои : 10.1007/978-1-4939-1601-6_16 . ISBN 978-1-4939-1600-9 .

[TaoVu-5] Перейти обратно: ^а ^б Тао, Т.; Ву, В. (2006). Аддитивная комбинаторика . Кембридж: Издательство Кембриджского университета. ISBN 978-0-521-85386-6 .

[6] Ружа И., Суммы и структура (PDF) .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]