Множество сумм

Иллюстрация определения множества сумм на примере нескольких 4-элементных множеств $A$ с разными размерами $A+A$. Одинаковым цветом обозначены разные значения. В таблице первыми выделяются цветом значения с несколькими различными представлениями.

Множество сумм — концепт аддитивной комбинаторики, соответствующий сумме Минковского конечных множеств.

Определение

Пусть $\text{G}$ — любая группа, $A,B\subset \text{G}$ — конечные множества. Тогда их суммой называется множество

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

Для одного множества $A$ его множеством сумм называют $A+A$. Кратные суммы обозначаются сокращённо

$kA=A+\dots +A=\{a_1+\dots +a_k:a_i\in A,i=1,\dots ,k\}$

Связанные определения

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

$A\times B=\{ab:a\in A,b\in B\}$

Величину $K(A)=\frac{|A+A|}{|A|}$ называют константой удвоения, а про множества, у которых она ограничена, говорят, что они имеют малое удвоение. В связи с теоремой сумм-произведений часто рассматривают множества с малым мультипликативным удвоением, то есть для которых ограничена величина $\frac{|AA|}{|A|}$.

Свойства

Мощность множества сумм $A+B$ связана с аддитивной энергией $E(A,B)$ неравенством $|A+B|E(A,B)\le |A{|}^2|B{|}^2$, поэтому последняя часто используется для её оценки.

Суммы одного множества

Теорема Фреймана рассматривает размер $A+A$ как показатель структурированности множества (если константа удвоения ограничена, то структура $A$ похожа на обобщённую арифметическую прогрессию).Шаблон:Sfn

Теорема сумм-произведений связывает размер множества сумм и множества произведений. Основная гипотеза гласит, что $\max \{|A+A|,|AA|\}\ge |A{|}^{2-o(1)}$ для $A\subset ℝ$. Сочетание суммирования и произведения в одном выражении привело к возникновению арифметической комбинаторики.

Изучается влияние поэлементного применения выпуклой функции к суммируемым множествам на размер множества сумм. Для выпуклых последовательностей известны нижние оценки на $|A+A|$ и $|A-A|$.Шаблон:Sfn Более общо, для выпуклой функции $f$ и множества $f(A):=\{f(a):a\in A\}$ задачу оценки $\max \{|A+A|,|f(A)+f(A)|\}$ и некоторые похожие иногда рассматривают как обобщение теоремы сумм-произведений, поскольку $AA=\exp \left(\log A+\log A\right)$ и поэтому $|AA|=|\log A+\log A|$, а функция $\exp$ выпукла.Шаблон:Sfn

Суммы нескольких множеств

Неравенство Плюннеке — Ружа утверждает, что разрастание (увеличение размера относительно складываемых множеств) кратных сумм $|kA+lB|,k,l\in \mathbb{N}$ в среднем (относительно $k,l$) не сильно превышает разрастание $|A+B|$.

Неравенство треугольника Ружа связывает размеры $A-B,B-C,C-A$ для любых множеств $A,B,C$ и показывает, что нормализованный размер разности множеств $\frac{|A-B|}{\sqrt{|A||B|}}$ можно рассматривать как псевдометрику, отражающую близость структуры этих множеств.

Структура

Один из фундаментальных вопросов аддитивной комбинаторики: какую структуру могут или должны иметь множества сумм. По состоянию на начало 2020 года не известно какого-либо нетривиально быстрого алгоритма, позволяющего определить, представимо ли заданное большое множество в виде $A+B,(|A|,|B|\ge 2)$ или $A+A,|A|\ge 2$. Однако известны некоторые частные результаты о структуре множеств сумм.

Например, множества сумм вещественных чисел не могут иметь малого мультипликативного удвоения, то есть если $A=B+C$, то $|AA|\ge |A{|}^{1+c}$ для некоторого $c>0$. А в группе вычетов по простому модулю $p$ есть лишь $2^{\left(\frac{1}{2}+o(1)\right)p}$ множеств, представимых в виде $A+B,|A|,|B|\to \mathrm{\infty }$.Шаблон:Sfn

Известно, что если $A,B$ — плотные множества натуральных чисел, то $A+B$ содержит длинные арифметические прогрессии. Тем не менее, в ${\mathbb{Z}}_p$ известны примеры плотных множеств с сильной верхней оценкой на длину таких прогрессий.Шаблон:Sfn

См. также

• Сумма Минковского
• Теорема сумм-произведений
• Теорема Фреймана
• Теорема Шнирельмана

Литература

• Шаблон:Книга

• Шаблон:Книга

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья