Множество сумм — концепт аддитивной комбинаторики, соответствующий сумме Минковского конечных множеств.
Определение Пусть — любая группа, — конечные множества. Тогда их суммой называется множество
Для одного множества его множеством сумм называют . Кратные суммы обозначаются сокращённо, с. 7-8
Связанные определения Аналогично определяются множество разностей, множество произведений, множество частных и тому подобные для любой операции. Например, множество произведений определяется так, с. 54, с. 92:
Величину называют константой удвоения, с. 57, а про множества, у которых она ограничена, говорят, что они имеют малое удвоение, с. 240. В связи с теоремой сумм-произведений часто рассматривают множества с малым мультипликативным удвоением, то есть для которых ограничена величина , с. 188; , § 5.
Свойства Мощность множества сумм связана с аддитивной энергией неравенством Согласно неравенству Коши — Буняковского, , где — число представлений , поэтому последняя часто используется для её оценки.
Суммы одного множества Теорема Фреймана рассматривает размер как показатель структурированности множества (если константа удвоения ограничена, то структура похожа на обобщённую арифметическую прогрессию).Этот вопрос часто называется обратной задачей аддитивной комбинаторики (см., например, , раздел 1.8, с. 19)
Теорема сумм-произведений связывает размер множества сумм и множества произведений. Основная гипотеза гласит, что для .; Сочетание суммирования и произведения в одном выражении привело к возникновению арифметической комбинаторики.
Изучается влияние поэлементного применения выпуклой функции к суммируемым множествам на размер множества сумм. Для выпуклых последовательностей известны нижние оценки на и . Более общо, для выпуклой функции и множества задачу оценки и некоторые похожие иногда рассматривают как обобщение теоремы сумм-произведений, поскольку и поэтому , а функция выпукла.
Суммы нескольких множеств Неравенство Плюннеке — Ружа утверждает, что разрастание (увеличение размера относительно складываемых множеств) кратных сумм в среднем (относительно ) не сильно превышает разрастание .
Неравенство треугольника Ружа связывает размеры для любых множеств и показывает, что нормализованный размер разности множеств можно рассматривать как псевдометрику, отражающую близость структуры этих множеств., с. 60
Структура Один из фундаментальных вопросов аддитивной комбинаторики: какую структуру могут или должны иметь множества сумм. По состоянию на начало 2020 года не известно какого-либо нетривиально быстрого алгоритма, позволяющего определить, представимо ли заданное большое множество в виде или . Однако известны некоторые частные результаты о структуре множеств сумм.
Например, множества сумм вещественных чисел не могут иметь малого мультипликативного удвоения, то есть если , то для некоторого ., следствие 2 А в группе вычетов по простому модулю есть лишь множеств, представимых в виде .При том, что общее число множеств в этой группе, очевидно,
Известно, что если — плотные множества натуральных чисел, то содержит длинные арифметические прогрессии.Впервые это доказал Бургейн в . Лучший на 2020 год результат получен в , а впоследствии передоказно новым, более общим, методом в Тем не менее, в известны примеры плотных множеств с сильной верхней оценкой на длину таких прогрессий.Обзор результатов на эту тему можно найти в статье
См. также Сумма Минковского Теорема сумм-произведений Теорема Фреймана Теорема Шнирельмана
Литература
Примечания
Категория:Арифметическая комбинаторика