Множина сум — поняття адитивної комбінаторики, що відповідає сумі Мінковського скінченних множин.
Визначення
Нехай — будь-яка група, — скінченні множини. Тоді їх сумою називають множину
Для однієї множини її множиною сум називають . Кратні суми позначають скорочено
Пов'язані визначення
Аналогічно визначають множину різниць, множину добутків, множину часток тощо для будь-якої операції. Наприклад, множину добутків визначають так:
Величину називають сталою подвоєння, а про множини, в яких вона обмежена, кажуть, що вони мають мале подвоєння. У зв'язку з теоремою сум-добутків часто розглядають множини з малим мультиплікативним подвоєнням, тобто для яких є обмеженою величина .
Властивості
Потужність множини сум пов'язана з адитивною енергією нерівністю , тому останню часто використовують для її оцінення.
Суми однієї множини
розглядає розмір як показник структурованості множини (якщо стала подвоєння обмежена, то структура схожа на узагальнену арифметичну прогресію).
Теорема сум-добутків пов'язує розмір множини сум та множини добутків. Основна гіпотеза каже, що для . Поєднання підсумовування та добутку в одному виразі привело до виникнення арифметичної комбінаторики.
Вивчається вплив поелементного застосування опуклої функції до множин, що підсумовуються, на розмір множини сум. Для відомі нижні оцінки на і . Загальніше, для опуклої функції і множини задачу оцінки і деякі схожі іноді розглядають як узагальнення теореми сум-добутків, оскільки і тому , а функція опукла.
Суми кількох множин
Нерівність Плюннеке — Ружі стверджує, що розростання (збільшення розміру відносно множин, що додаються) кратних сум в середньому (відносно ) не дуже перевищує розростання .
Нерівність трикутника Ружі пов'язує розміри для будь-яких множин і показує, що нормалізований розмір різниці множин можна розглядати як псевдометрику, що відбиває близькість структури цих множин.
Структура
Одне з фундаментальних питань адитивної комбінаторики: яку структуру можуть або повинні мати множини сум. Станом на початок 2020 року не відомо якогось нетривіально швидкого алгоритму, що дозволяє визначити, чи подавана задана велика множина у вигляді або . Однак відомі деякі окремі результати про структуру множин сум.
Наприклад, множини сум дійсних чисел не можуть мати малого мультиплікативного подвоєння, тобто якщо , то для деякого . А в групі лишків за простим модулем є лише множин, подаваних у вигляді .
Відомо, що якщо — щільні множини натуральних чисел, то містить довгі арифметичні прогресії. Проте, в відомі приклади щільних множин із сильною верхньою оцінкою на довжину таких прогресій.
Див. також
- Сума Мінковського
- Теорема сум-добутків
- (Теорема Шнірельмана)
Примітки
- Фрейман, 1966, с. 7-8
- Тао, Ву, 2006, с. 54, с. 92
- Тао, Ву, 2006, с. 57
- Тао, Ву, 2006, с. 240
- Тао, Ву, 2006, с. 188; Шкредов, 2013, § 5
- За нерівністю Коші — Буняковського, , де — число подань
- Фрейман, 1966.
- Це питання часто називають оберненою задачею адитивної комбінаторики (див., наприклад, Фрейман, 1966, розділ 1.8, с. 19)
- Erdős, Szemerédi, 1983; Shakan, 2019
- Shkredov, Schoen, 2011.
- Elekes, Nathanson, Ruzsa, 2000.
- Тао, Ву, 2006, с. 60
- Shkredov, Zhelezov, 2016, наслідок 2
- Alon, Granville, Ubis, 2010.
- При тому, що (загальне число множин) у цій групі, очевидно,
- Вперше це довів Бургейн у Bourgain, 1990. Найкращий на 2020 рік результат отримано в Green, 2002, а пізніше передоведено новим, загальнішим, методом у Croot, Laba, Sisask, 2013
- Ruzsa, 1991.
- Огляд результатів із цієї теми можна знайти в статье[недоступне посилання] Croot, Ruzsa, Schoen, 2007
Література
- . Начала структурной теории множеств. — Типография "Татполиграф". — 1966.
- T. Tao, Van H. Vu. Additive combinatorics. — Cambridge University Press. — 2006. — .
- . Несколько новых результатов о старших энергиях // Труды Московского математического общества. — 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.
- . 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 -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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Mnozhina sum ponyattya aditivnoyi kombinatoriki sho vidpovidaye sumi Minkovskogo skinchennih mnozhin Ilyustraciya viznachennya mnozhini sum na prikladi dekilkoh 4 elementnih mnozhin A displaystyle A z riznimi rozmirami A A displaystyle A A Odinakovim kolorom poznacheno rizni znachennya U tablici pershimi vidilyayutsya kolorom znachennya z kilkoma riznimi podannyami ViznachennyaNehaj G displaystyle mbox G bud yaka grupa A B G displaystyle A B subset mbox G skinchenni mnozhini Todi yih sumoyu nazivayut mnozhinu A B a b a A b B displaystyle A B a b a in A b in B Dlya odniyeyi mnozhini A displaystyle A yiyi mnozhinoyu sum nazivayut A A displaystyle A A Kratni sumi poznachayut skorocheno k A A A a 1 a k a i A i 1 k displaystyle kA A dots A a 1 dots a k a i in A i 1 dots k Pov yazani viznachennya Analogichno viznachayut mnozhinu riznic mnozhinu dobutkiv mnozhinu chastok tosho dlya bud yakoyi operaciyi Napriklad mnozhinu dobutkiv viznachayut tak A B a b a A b B displaystyle A times B ab a in A b in B Velichinu K A A A A displaystyle K A frac A A A nazivayut staloyu podvoyennya a pro mnozhini v yakih vona obmezhena kazhut sho voni mayut male podvoyennya U zv yazku z teoremoyu sum dobutkiv chasto rozglyadayut mnozhini z malim multiplikativnim podvoyennyam tobto dlya yakih ye obmezhenoyu velichina A A A displaystyle frac AA A VlastivostiPotuzhnist mnozhini sum A B displaystyle A B pov yazana z aditivnoyu energiyeyu E A B displaystyle E A B nerivnistyu A B E A B A 2 B 2 displaystyle A B E A B leq A 2 B 2 tomu ostannyu chasto vikoristovuyut dlya yiyi ocinennya Sumi odniyeyi mnozhini rozglyadaye rozmir A A displaystyle A A yak pokaznik strukturovanosti mnozhini yaksho stala podvoyennya obmezhena to struktura A displaystyle A shozha na uzagalnenu arifmetichnu progresiyu Teorema sum dobutkiv pov yazuye rozmir mnozhini sum ta mnozhini dobutkiv Osnovna gipoteza kazhe sho max A A A A A 2 o 1 displaystyle max A A AA geq A 2 o 1 dlya A R displaystyle A subset mathbb R Poyednannya pidsumovuvannya ta dobutku v odnomu virazi privelo do viniknennya arifmetichnoyi kombinatoriki Vivchayetsya vpliv poelementnogo zastosuvannya opukloyi funkciyi do mnozhin sho pidsumovuyutsya na rozmir mnozhini sum Dlya vidomi nizhni ocinki na A A displaystyle A A i A A displaystyle A A Zagalnishe dlya opukloyi funkciyi f displaystyle f i mnozhini f A f a a A displaystyle f A f a a in A zadachu ocinki max A A f A f A displaystyle max A A f A f A i deyaki shozhi inodi rozglyadayut yak uzagalnennya teoremi sum dobutkiv oskilki A A exp log A log A displaystyle AA exp left log A log A right i tomu A A log A log A displaystyle AA log A log A a funkciya exp displaystyle exp opukla Sumi kilkoh mnozhin Nerivnist Plyunneke Ruzhi stverdzhuye sho rozrostannya zbilshennya rozmiru vidnosno mnozhin sho dodayutsya kratnih sum k A l B k l N displaystyle kA lB k l in mathbb N v serednomu vidnosno k l displaystyle k l ne duzhe perevishuye rozrostannya A B displaystyle A B Nerivnist trikutnika Ruzhi pov yazuye rozmiri A B B C C A displaystyle A B B C C A dlya bud yakih mnozhin A B C displaystyle A B C i pokazuye sho normalizovanij rozmir riznici mnozhin A B A B displaystyle frac A B sqrt A B mozhna rozglyadati yak psevdometriku sho vidbivaye blizkist strukturi cih mnozhin Struktura Odne z fundamentalnih pitan aditivnoyi kombinatoriki yaku strukturu mozhut abo povinni mati mnozhini sum Stanom na pochatok 2020 roku ne vidomo yakogos netrivialno shvidkogo algoritmu sho dozvolyaye viznachiti chi podavana zadana velika mnozhina u viglyadi A B A B 2 displaystyle A B A B geq 2 abo A A A 2 displaystyle A A A geq 2 Odnak vidomi deyaki okremi rezultati pro strukturu mnozhin sum Napriklad mnozhini sum dijsnih chisel ne mozhut mati malogo multiplikativnogo podvoyennya tobto yaksho A B C displaystyle A B C to A A A 1 c displaystyle AA geq A 1 c dlya deyakogo c gt 0 displaystyle c gt 0 A v grupi lishkiv za prostim modulem p displaystyle p ye lishe 2 1 2 o 1 p displaystyle 2 left frac 1 2 o 1 right p mnozhin podavanih u viglyadi A B A B displaystyle A B A B to infty Vidomo sho yaksho A B displaystyle A B shilni mnozhini naturalnih chisel to A B displaystyle A B mistit dovgi arifmetichni progresiyi Prote v Z p displaystyle mathbb Z p vidomi prikladi shilnih mnozhin iz silnoyu verhnoyu ocinkoyu na dovzhinu takih progresij Div takozhSuma Minkovskogo Teorema sum dobutkiv Teorema ShnirelmanaPrimitkiFrejman 1966 s 7 8 Tao Vu 2006 s 54 s 92 Tao Vu 2006 s 57 Tao Vu 2006 s 240 Tao Vu 2006 s 188 Shkredov 2013 5 Za nerivnistyu Koshi Bunyakovskogo A B 2 x A B A B x 2 A B x A B A B x 2 A B E A B 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 de A B x displaystyle A B x chislo podan x a b a A b B displaystyle x a b a in A b in B Frejman 1966 Ce pitannya chasto nazivayut obernenoyu zadacheyu aditivnoyi kombinatoriki div napriklad Frejman 1966 rozdil 1 8 s 19 Erdos Szemeredi 1983 Shakan 2019 Shkredov Schoen 2011 Elekes Nathanson Ruzsa 2000 Tao Vu 2006 s 60 Shkredov Zhelezov 2016 naslidok 2 Alon Granville Ubis 2010 Pri tomu sho zagalne chislo mnozhin u cij grupi ochevidno 2 p displaystyle 2 p Vpershe ce doviv Burgejn u Bourgain 1990 Najkrashij na 2020 rik rezultat otrimano v Green 2002 a piznishe peredovedeno novim zagalnishim metodom u Croot Laba Sisask 2013 Ruzsa 1991 Oglyad rezultativ iz ciyeyi temi mozhna znajti v state nedostupne posilannya Croot Ruzsa Schoen 2007Literatura Nachala strukturnoj teorii mnozhestv Tipografiya Tatpoligraf 1966 T Tao Van H Vu Additive combinatorics Cambridge University Press 2006 ISBN 0 511 24530 0 Neskolko novyh rezultatov o starshih energiyah Trudy Moskovskogo matematicheskogo obshestva 2013 T 74 vyp 1 S 35 73 Paul Erdos Endre Szemeredi 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 Arithmetic progressions in sumsets Geometric amp Functional Analysis GAFA 2002 Vol 12 P 584 597 Ernie Croot Izabella Laba Olof Sisask Arithmetic Progressions in Sumsets and L p 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