Множина сум — поняття адитивної комбінаторики, що відповідає сумі Мінковського скінченних множин.
Визначення Нехай — будь-яка група, — скінченні множини. Тоді їх сумою називають множину
Для однієї множини її множиною сум називають . Кратні суми позначають скорочено, с. 7-8
Пов'язані визначення Аналогічно визначають множину різниць, множину добутків, множину часток тощо для будь-якої операції. Наприклад, множину добутків визначають так, с. 54, с. 92:
Величину називають сталою подвоєння, с. 57, а про множини, в яких вона обмежена, кажуть, що вони мають мале подвоєння, с. 240. У зв'язку з теоремою сум-добутків часто розглядають множини з малим мультиплікативним подвоєнням, тобто для яких є обмеженою величина , с. 188; , § 5.
Властивості Потужність множини сум пов'язана з адитивною енергією нерівністю За нерівністю Коші — Буняковського, , де — число подань , тому останню часто використовують для її оцінення.
Суми однієї множини Теорема Фреймана розглядає розмір як показник структурованості множини (якщо стала подвоєння обмежена, то структура схожа на узагальнену арифметичну прогресію)Це питання часто називають оберненою задачею адитивної комбінаторики (див., наприклад, , розділ 1.8, с. 19).
Теорема сум-добутків пов'язує розмір множини сум та множини добутків. Основна гіпотеза каже, що для ; . Поєднання підсумовування та добутку в одному виразі привело до виникнення арифметичної комбінаторики.
Вивчається вплив поелементного застосування опуклої функції до множин, що підсумовуються, на розмір множини сум. Для опуклих послідовностей відомі нижні оцінки на і . Загальніше, для опуклої функції і множини задачу оцінки і деякі схожі іноді розглядають як узагальнення теореми сум-добутків, оскільки і тому , а функція опукла.
Суми кількох множин Нерівність Плюннеке — Ружі стверджує, що розростання (збільшення розміру відносно множин, що додаються) кратних сум в середньому (відносно ) не дуже перевищує розростання .
Нерівність трикутника Ружі пов'язує розміри для будь-яких множин і показує, що нормалізований розмір різниці множин можна розглядати як псевдометрику, що відбиває близькість структури цих множин, с. 60.
Структура Одне з фундаментальних питань адитивної комбінаторики: яку структуру можуть або повинні мати множини сум. Станом на початок 2020 року не відомо якогось нетривіально швидкого алгоритму, що дозволяє визначити, чи подавана задана велика множина у вигляді або . Однак відомі деякі окремі результати про структуру множин сум.
Наприклад, множини сум дійсних чисел не можуть мати малого мультиплікативного подвоєння, тобто якщо , то для деякого , наслідок 2. А в групі лишків за простим модулем є лише множин, подаваних у вигляді При тому, що загальне число множин у цій групі, очевидно, .
Відомо, що якщо — щільні множини натуральних чисел, то містить довгі арифметичні прогресіїВперше це довів Бургейн у . Найкращий на 2020 рік результат отримано в , а пізніше передоведено новим, загальнішим, методом у . Проте, в відомі приклади щільних множин із сильною верхньою оцінкою на довжину таких прогресійОгляд результатів із цієї теми можна знайти в статье .
Див. також Сума Мінковського Теорема сум-добутків Теорема Шнірельмана
Примітки
Література