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

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

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

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

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

${\displaystyle |A+B|\geq \min(|A|+|B|-1,p)}$

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

${\displaystyle |A+B|\leq |A|+|B|-1\leq p-2,}$

тогда и являются арифметическими прогрессиями с той же разницей. Это иллюстрирует структуры, которые часто изучаются в аддитивной комбинаторике: комбинаторная структура по сравнению с алгебраической структурой арифметических прогрессий.${\displaystyle А}$${\displaystyle Б}$${\displaystyle А+Б}$

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

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

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

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

${\displaystyle AB=\{ab:a\in A,b\in B\}.}$

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

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

Не путать с

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

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

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

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

${\displaystyle d(A,B)=\log {\dfrac {|AB|}{\sqrt {|A||B|}}}.}$

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

${\displaystyle d(B,C)\leq d(A,B)+d(A,C).}$

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

• Арифметическая комбинаторика
• Аддитивная теория чисел

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