Аддитивная комбинаторика

Аддитивная комбинаторика — это область комбинаторики в математике. Одной из основных областей исследования аддитивной комбинаторики являются обратные задачи : учитывая, что размер суммы A + B невелик , что мы можем сказать о структурах $A$ и $B$ ? В случае целых чисел классическая теорема Фреймана дает частичный ответ на этот вопрос в терминах многомерных арифметических прогрессий .

Другой типичной проблемой является нахождение нижней границы для $|A+B|$ с точки зрения $|A|$ и $|B|$ . Это можно рассматривать как обратную задачу с заданной информацией, которая $|A+B|$ достаточно мала, и тогда структурный вывод имеет вид, что либо $A$ или $B$ – пустое множество; однако в литературе такие проблемы иногда рассматриваются и как прямые проблемы. Примеры этого типа включают гипотезу Эрдеша-Хейльбронна (для ограниченного множества ) и теорему Коши-Дэвенпорта . Методы, используемые для решения таких вопросов, часто происходят из многих различных областей математики, включая комбинаторику , эргодическую теорию , анализ , теорию графов , теорию групп , а также линейные алгебраические и полиномиальные методы.

История аддитивной комбинаторики [ править ]

Хотя аддитивная комбинаторика является довольно новой ветвью комбинаторики (на самом деле термин «аддитивная комбинаторика» был придуман Теренсом Тао и Ван Х. Ву в их книге в 2000-х годах), чрезвычайно старая проблема, теорема Коши-Дэвенпорта, является одним из наиболее фундаментальных результатов в это поле.

– Дэвенпорта Теорема Коши

Предположим, что A и B — конечные подмножества циклической группы $\mathbb {Z} /p\mathbb {Z}$ для простого $p$ , то имеет место следующее неравенство.

|A+B|\geq \min(|A|+|B|-1,p)

Теорема Воспера [ править ]

Теперь мы имеем неравенство для мощности множества сумм $A+B$ , естественно задаться обратной задачей, а именно, при каких условиях на $A$ и $B$ сохраняется ли равенство? Теорема Воспера отвечает на этот вопрос. Предположим, что $|A|,|B|\geq 2$ (то есть, исключая крайние случаи) и

|A+B|\leq |A|+|B|-1\leq p-2,

затем $A$ и $B$ являются арифметическими прогрессиями с одинаковой разницей. Это иллюстрирует структуры, которые часто изучаются в аддитивной комбинаторике: комбинаторная структура $A+B$ по сравнению с алгебраической структурой арифметических прогрессий.

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

Полезной теоремой аддитивной комбинаторики является неравенство Плюннеке-Рузы . Эта теорема дает верхнюю оценку мощности $|nA-mA|$ с точки зрения константы удвоения $A$ . Например, используя неравенство Плюнеке – Ружи, мы можем доказать версию теоремы Фреймана в конечных полях.

Основные понятия [ править ]

Операции над множествами [ править ]

Пусть A и B — конечные подмножества абелевой группы, тогда совокупное множество определяется как

A+B=\{a+b:a\in A,b\in B\}.

Например, мы можем написать $\{1,2,3,4\}+\{1,2,3\}=\{2,3,4,5,6,7\}$ . Аналогичным образом мы можем определить разностный набор A и B как

A-B=\{a-b:a\in A,b\in B\}.

Здесь мы приводим другие полезные обозначения.

kA=\underbrace {A+A+\cdots +A} _{k{\text{ terms }}}=\{a_{1}+\cdots +a_{k}:a_{1}\in A,\dots ,a_{k}\in A\}.

Не путать с

k\cdot A=\{ka:a\in A\}

Константа удвоения [ править ]

Пусть A — подмножество абелевой группы. Константа удвоения показывает, насколько велика совокупная сумма. $|A+A|$ сравнивается с исходным размером | А |. Мы определяем константу удвоения A как

K={\dfrac {|A+A|}{|A|}}.

Расстояние Ружа [ править ]

Пусть A и B — два подмножества абелевой группы. Мы определяем расстояние Ружи между этими двумя наборами как величину

d(A,B)=\log {\dfrac {|A-B|}{\sqrt {|A||B|}}}.

Неравенство треугольника Ружи говорит нам, что расстояние Рузсы подчиняется неравенству треугольника:

d(B,C)\leq d(A,B)+d(A,C).

Однако, поскольку $d(A,A)$ не может быть нулем, обратите внимание, что расстояние Рузсы на самом деле не является метрикой.

Ссылки [ править ]

Цитаты [ править ]

Тао Т. и Ву В. (2012). Аддитивная комбинаторика . Кембридж: Издательство Кембриджского университета.
Грин, Б. (15 января 2009 г.). Рецензия на книгу «Аддитивная комбинаторика». Получено с https://www.ams.org/journals/bull/2009-46-03/S0273-0979-09-01231-2/S0273-0979-09-01231-2.pdf.