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

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

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

Для одного множества ${\displaystyle A}$ его множеством сумм называют ${\displaystyle A+A}$. Кратные суммы обозначаются сокращённо^[1]

${\displaystyle kA=A+\dots +A=\{a_{1}+\dots +a_{k}:a_{i}\in A,\ i=1,\dots ,k\}}$

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

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

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

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

Теорема Фреймана рассматривает размер ${\displaystyle A+A}$ как показатель структурированности множества (если константа удвоения ограничена, то структура ${\displaystyle A}$ похожа на обобщённую арифметическую прогрессию).^[7][8]

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

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

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

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

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

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

Известно, что если ${\displaystyle A,B}$ — плотные множества натуральных чисел, то ${\displaystyle A+B}$ содержит длинные арифметические прогрессии.^[16] Тем не менее, в ${\displaystyle {\mathbb {Z} }_{p}}$ известны примеры плотных множеств с сильной верхней оценкой на длину таких прогрессий.^[17][18]