Множина сум

Ілюстрація визначення множини сум на прикладі декількох 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.

Див. також

• Сума Мінковського
• Теорема сум-добутків
• Теорема Шнірельмана

Література

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття