Jump to content

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

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

Заявление

[ редактировать ]

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

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

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

[ редактировать ]

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

Теорема   (неравенство Плюнеке-Рузы) Если и являются конечными подмножествами абелевой группы и является константой, так что , то для всех неотрицательных целых чисел и ,

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

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

[ редактировать ]

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

Теорема   (неравенство Плюнеке) Предположим , и являются конечными подмножествами абелевой группы и является константой, так что . Тогда для всех неотрицательных целых чисел ,

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

[ редактировать ]

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

[ редактировать ]

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

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


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

[ редактировать ]

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

Лемма: Пусть и — конечные подмножества абелевой группы . Если является непустым подмножеством, которое минимизирует значение , то для всех конечных подмножеств ,

Доказательство. Это демонстрируется индукцией по размеру . Для базового случая , Обратите внимание, что это просто перевод для любого , так

Для индуктивного шага предположим, что неравенство выполнено для всех с для некоторого положительного целого числа . Позволять быть подмножеством с , и пусть для некоторых . (В частности, неравенство справедливо для .) Наконец, пусть . Определение подразумевает, что . Таким образом, по определению этих множеств,

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

Определение подразумевает, что , поэтому по определению , . Таким образом, применяя индуктивную гипотезу о и используя определение ,

Чтобы ограничить правую часть этого неравенства, положим . Предполагать и , то существует такой, что . Таким образом, по определению , так . Следовательно, множества и непересекающиеся. Определения и таким образом подразумевать, что

Опять же по определению , так . Следовательно,

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

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

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

Это можно доказать методом индукции. В базовом случае определения и подразумеваю, что . Таким образом, определение подразумевает, что . Для индуктивного шага предположим, что это верно для . Применяя лемму с и индуктивная гипотеза дает

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

Потому что , должно быть так, что . Поэтому,

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

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

[ редактировать ]

И доказательство Плюнеке неравенства Плюнеке, и оригинальное доказательство Ружи неравенства Плюнеке – Ружи используют метод графов Плюнеке. Графы Плюнеке — это способ отразить аддитивную структуру множеств. теоретико-графовым способом [ 5 ] [ 6 ]

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

Определение . граф Ориентированный называется полукоммутативным , если всякий раз, когда существуют различные такой, что и находятся края в для каждого , то также существуют различные так что и находятся края в для каждого .

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

Определение . — Слоистый граф это (ориентированный) граф. чье множество вершин можно разделить так, чтобы все ребра вошли из к , для некоторых .

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

Каноническим примером графа Плюннеке является следующий, который показывает, как структура множеств образуют граф Плюнеке.

Пример . Позволять являются подмножествами абелевой группы. Тогда пусть быть многоуровневым графом, так что каждый слой является копией , так что , , ..., . Создайте преимущество (где и ) всякий раз, когда существует такой, что . (В частности, если , затем по определению, поэтому каждая вершина имеет исходящую степень, равную размеру .) Затем является графом Плюннеке. Например, чтобы проверить это полукоммутативен, если и находятся края в для каждого , затем . Тогда пусть , так что и . Таким образом, является полукоммутативным. Аналогично можно проверить, что граф, образованный перестановкой всех ребер также полукоммутативен, поэтому является графом Плюннеке.

В графе Плюннеке образ множества в , написано , определяется как множество вершин в до которого можно добраться по пути, начинающемуся из некоторой вершины в . В частности, в приведенном выше примере это просто .

Коэффициент увеличения между и , обозначенный , затем определяется как минимальный коэффициент, на который изображение набора должно превышать размер исходного набора. Формально,

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

Теорема   (теорема Плюннеке) Пусть быть графом Плюнеке. Затем, уменьшается в .

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

Неравенство Плюнеке-Ружсы является довольно прямым следствием теоремы Плюнеке и неравенства треугольника Ружи. Применяя теорему Плюнеке к графику, приведенному в примере, при и , получается, что если , то существует так что . Применяя этот результат еще раз с помощью вместо , существует так что . Тогда по неравенству треугольника Ружи (на ),

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


См. также

[ редактировать ]
  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 .
  5. ^ Перейти обратно: а б Тао, Т.; Ву, В. (2006). Аддитивная комбинаторика . Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-85386-6 .
  6. ^ Ружа И., Суммы и структура (PDF) .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: ef4f69999265481f3da7918730352b21__1674103920
URL1:https://arc.ask3.ru/arc/aa/ef/21/ef4f69999265481f3da7918730352b21.html
Заголовок, (Title) документа по адресу, URL1:
Plünnecke–Ruzsa inequality - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)