Множина сум

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

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

Визначення

Нехай ${\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].

Див. також

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

Примітки

1. Фрейман, 1966, с. 7-8
2. Тао, Ву, 2006, с. 54, с. 92
3. Тао, Ву, 2006, с. 57
4. Тао, Ву, 2006, с. 240
5. Тао, Ву, 2006, с. 188; Шкредов, 2013, § 5
6. За нерівністю Коші — Буняковського, ${\displaystyle (|A||B|)^{2}={\left({\sum \limits _{x\in A+B}{(A*B)(x)}}\right)}^{2}\leq |A+B|\sum \limits _{x\in A+B}{(A*B)(x)^{2}}=|A+B|E(A,B)}$, де ${\displaystyle (A*B)(x)}$ — число подань ${\displaystyle x=a+b,\ a\in A,\ b\in B}$
7. Фрейман, 1966.
8. Це питання часто називають оберненою задачею адитивної комбінаторики (див., наприклад, Фрейман, 1966, розділ 1.8, с. 19)
9. Erdős, Szemerédi, 1983; Shakan, 2019
10. Shkredov, Schoen, 2011.
11. Elekes, Nathanson, Ruzsa, 2000.
12. Тао, Ву, 2006, с. 60
13. Shkredov, Zhelezov, 2016, наслідок 2
14. Alon, Granville, Ubis, 2010.
15. При тому, що загальне число множин у цій групі, очевидно, ${\displaystyle 2^{p}}$
16. Вперше це довів Бургейн у Bourgain, 1990. Найкращий на 2020 рік результат отримано в Green, 2002, а пізніше передоведено новим, загальнішим, методом у Croot, Laba, Sisask, 2013
17. Ruzsa, 1991.
18. Огляд результатів із цієї теми можна знайти в статье^[недоступне посилання] Croot, Ruzsa, Schoen, 2007

Література

• Фрейман, Григорий Абелевич. Начала структурной теории множеств. — Типография "Татполиграф". — 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 ${\displaystyle 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.