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

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

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

ОпределениеПравить

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

$A+B:=\{a+b:a\in <!--\; \in \; -->A,b\in <!--\; \in \; -->B\}$$A+B:=\{a+b:a\in A,\ b\in B\}$ 

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

$kA=A+\cdots <!--\; \cdots \; -->+A=\{a_1+\cdots <!--\; \cdots \; -->+a_k:a_i\in <!--\; \in \; -->A,i=1,\dots <!--\; \dots \; -->,k\}$$kA=A+\dots +A=\{a_{1}+\dots +a_{k}:a_{i}\in A,\ i=1,\dots ,k\}$ 

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

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

$A\times <!--\; \times \; -->B=\{ab:a\in <!--\; \in \; -->A,b\in <!--\; \in \; -->B\}$$A\times B=\{ab\ :\ a\in A,\ b\in B\}$ 

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

СвойстваПравить

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

Суммы одного множестваПравить

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

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

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

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

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

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

СтруктураПравить

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

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

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

См. такжеПравить

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

ЛитератураПравить

• Фрейман, Григорий Абелевич. Начала структурной теории множеств (рус.). — Типография "Татполиграф". — 1966.

• T. Tao, Van H. Vu. Additive combinatorics (англ.). — Cambridge University Press. — 2006. — ISBN 0-511-24530-0.

• И. Д. Шкредов. Несколько новых результатов о старших энергиях (рус.) // Труды Московского математического общества. — 2013. — Т. 74, вып. 1. — С. 35—73.

• Paul Erdős, Endre Szemerédi. On sums and products of integers (англ.) // Studies in Pure Mathematics. — 1983. — P. 213—218.

• George Shakan. On higher energy decompositions and the sum-product phenomenon (англ.) // Mathematical Proceedings of the Cambridge Philosophical Society. — 2019. — Vol. 167, iss. 3. — P. 599—617.

• Ilya D. Shkredov, Dmitrii Zhelezov. On additive bases of sets with small product set (англ.). — 2016. — arXiv:math/1606.02320.

• B. Green. Arithmetic progressions in sumsets (англ.) // Geometric & Functional Analysis GAFA. — 2002. — Vol. 12. — P. 584—597.

• Ernie Croot, Izabella Laba, Olof Sisask. Arithmetic Progressions in Sumsets and $L^p$$L^{p}$ -Almost-Periodicity (англ.) // Combinatorics, Probability and Computing. — 2013. — Vol. 22, iss. 3. — P. 351—365.

• N. Alon, A. Granville, A. Ubis. The number of sumsets in a finite field (англ.) // Bulletin of the London Mathematical Society. — 2010. — Vol. 42, iss. 4.

• Imre Z. Ruzsa. Arithmetic progressions in sumsets (англ.) // Acta Arithmetica. — 1991. — Vol. 60, iss. 2. — P. 191—202.

• J. Bourgain. On arithmetic progressions in sums of sets of integers (англ.) // A Tribute to Paul Erdos. — 1990. — P. 105—110.

• Ernie Croot, Imre Z. Ruzsa, Tomasz Schoen. Arithmetic progressions in sparse sumsets (англ.). — 2007.

• I. D. Shkredov, T. Schoen. On sumsets of convex sets (англ.) // Combinatorics, Probability and Computing. — 2011. — P. 793—798. — arXiv:math/1105.3542.

• G. Elekes, M. B. Nathanson, I. Z. Ruzsa. Convexity and Sumsets (англ.) // Journal of Number Theory. — 2000. — Vol. 83, iss. 2. — P. 194—201.