Множина сум

Множина сум — поняття адитивної комбінаторики, що відповідає сумі Мінковського скінченних множин.

Ілюстрація визначення множини сум на прикладі декількох 4-елементних множин $A$ з різними розмірами $A+A$. Одинаковим кольором позначено різні значення. У таблиці першими виділяються кольором значення з кількома різними поданнями.

Визначення

Нехай ${\mbox{G}}$ — будь-яка група, $A,B\subset {\mbox{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)\leq |A|^{2}|B|^{2}$, тому останню часто використовують для її оцінення.

Суми однієї множини

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

Теорема сум-добутків пов'язує розмір множини сум та множини добутків. Основна гіпотеза каже, що $\max\{|A+A|,\ |AA|\}\geq |A|^{2-o(1)}$ для $A\subset \mathbb {R}$. Поєднання підсумовування та добутку в одному виразі привело до виникнення арифметичної комбінаторики.

Вивчається вплив поелементного застосування опуклої функції до множин, що підсумовуються, на розмір множини сум. Для опуклих послідовностей відомі нижні оцінки на $|A+A|$ і $|A-A|$. Загальніше, для опуклої функції $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$ опукла.

Суми кількох множин

Нерівність Плюннеке — Ружі стверджує, що розростання (збільшення розміру відносно множин, що додаються) кратних сум $|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|\geq 2)$ або $A+A,\ |A|\geq 2$. Однак відомі деякі окремі результати про структуру множин сум.

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

Відомо, що якщо $A,B$ — щільні множини натуральних чисел, то $A+B$ містить довгі арифметичні прогресії. Проте, в ${\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}$-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.