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

Additive combinatorics

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

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

История аддитивной комбинаторики

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

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

Предположим, что А и B конечные подмножества для прайма , то имеет место следующее неравенство.

Теорема Воспера

Теперь имеем неравенство для мощности множества сумм , естественно задать обратную задачу: при каких условиях на и справедливо ли равенство? Теорема Воспера отвечает на этот вопрос. Предположим, что (то есть, исключая крайние случаи) и

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

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

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

Основные понятия

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

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

Например, мы можем написать . Аналогичным образом мы можем определить разностное множество А и B быть

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

Постоянная удвоения

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

Ружское расстояние

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

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

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

Рекомендации

Цитаты

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