Аддитивная комбинаторика — это область комбинаторики в математике. Одной из основных областей изучения аддитивной комбинаторики являются обратные задачи : учитывая, что размер суммы A + B мал , что мы можем сказать о структурах и ? В случае целых чисел классическая теорема Фреймана дает частичный ответ на этот вопрос в терминах многомерных арифметических прогрессий .
Другой типичной задачей является нахождение нижней границы для в терминах и . Это можно рассматривать как обратную задачу с заданной информацией, которая достаточно мала, и структурное заключение тогда имеет вид, что либо или является пустым множеством; однако в литературе такие задачи иногда также считаются прямыми задачами. Примерами этого типа являются гипотеза Эрдёша–Хейльбронна (для ограниченного набора сумм ) и теорема Коши–Дэвенпорта . Методы, используемые для решения таких вопросов, часто берутся из разных областей математики, включая комбинаторику , эргодическую теорию , анализ , теорию графов , теорию групп и линейные алгебраические и полиномиальные методы.
Хотя аддитивная комбинаторика является довольно новым разделом комбинаторики (фактически термин аддитивная комбинаторика был введен Теренсом Тао и Ван Х. Ву в их книге в 2000-х годах), чрезвычайно старая проблема — теорема Коши–Дэвенпорта — является одним из самых фундаментальных результатов в этой области.
Предположим, что A и B — конечные подмножества циклической группы для простого числа , тогда справедливо следующее неравенство.
Теперь, когда у нас есть неравенство для мощности множества суммы , естественно задать обратную задачу, а именно, при каких условиях на и выполняется равенство? Теорема Воспера отвечает на этот вопрос. Предположим, что (то есть, исключая крайние случаи) и
тогда и являются арифметическими прогрессиями с той же разницей. Это иллюстрирует структуры, которые часто изучаются в аддитивной комбинаторике: комбинаторная структура по сравнению с алгебраической структурой арифметических прогрессий.
Полезной теоремой в аддитивной комбинаторике является неравенство Плюннеке–Ружи . Эта теорема дает верхнюю границу мощности в терминах константы удвоения . Например, используя неравенство Плюннеке–Ружи, мы можем доказать версию теоремы Фреймана в конечных полях.
Пусть A и B — конечные подмножества абелевой группы, тогда сумма множеств определяется как
Например, мы можем написать . Аналогично мы можем определить разностный набор A и B как
Здесь мы приводим другие полезные обозначения.
Не путать с
Пусть A — подмножество абелевой группы. Константа удвоения измеряет, насколько велико множество сумм по сравнению с его исходным размером | A |. Мы определяем константу удвоения A как
Пусть A и B — два подмножества абелевой группы. Определим расстояние Ружи между этими двумя множествами как величину
Неравенство треугольника Ружи говорит нам, что расстояние Ружи подчиняется неравенству треугольника:
Однако, поскольку не может быть равен нулю, следует отметить, что расстояние Ружи на самом деле не является метрикой.
