Арифмети́чна комбінато́рика — міждисциплінарна галузь математики, що вивчає залежність між структурами, що утворюються в полі (рідше — в кільці) операцією додавання і операцією множення.
Підхід до поняття структури тут аналогічний адитивній комбінаториці і ґрунтується переважно на розмірі множини сум (або добутків), адитивної (або мультиплікативної) енергії та різних їх комбінаціях. Як поле зазвичай розглядають дійсні чи раціональні числа (, ) та остачі за простим модулем ().
Неоднозначність термінології та предмет статті
Адитивна й арифметична комбінаторика — молоді науки, що активно розвиваються. Їхні методи та способи постановки завдань дуже схожі, тому, як правило, адитивну комбінаторику вважають частиною арифметичної. У цій статті описано лише теми, що містять у тому чи іншому вигляді обидві операції поля або зворотні до них, тобто які не належать до суто адитивної комбінаторики (хоча остання становить значну частину арифметичної).
Крім того, тут не порушуються питання про адитивно-комбінаторні властивості мультиплікативних підгруп і пов'язаних з ними множин, оскільки, хоча їх визначення пов'язане зі множенням, але їхня мультиплікативна структура жорстко зафіксована, а комбінаторна складова цієї науки передбачає ту чи іншу спільність щодо ступеня структурованості (хоча б із параметром, що виступає в ролі константи).
Мотивація
Розвиток арифметичної комбінаторики значною мірою мотивований появою теореми сум-добутків, яка говорить про неодмінне розростання множини від застосування до неї або комбінаторного підсумовування, або перемноження, тобто однієї з двох операцій:
З цього випливає, що комбінування цих операцій також тягне за собою розростання: якщо , то
,
а додавання до скінченного числа елементів впливає на зростання лише несуттєво. Оскільки теорему сум-добутків доведено лише в слабкій формі (далекій від гіпотези), деякі вчені почали цікавитися отриманням тверджень такого роду, які випливали б із сильніших форм гіпотези, ніж доведені, а згодом — загалом вивченням співвідношення між результатами різних комбінацій двох операцій поля.
Наприклад, гіпотеза Ердеша — Семереді про суми-добутки стверджує, що
З цієї гіпотези випливало б, що , але для множин
такий результат легко отримати і без неї простим комбінаторним міркуванням.
Завдання та результати
У цьому розділі для опису результатів використовуються загальноприйняті записи (пояснення наведено в O-нотації):
означає, що
означає, що
Раціональні вирази
Постановка питання
Назвемо раціональним виразом над множинами будь-яку комбінацію арифметичних операцій (
) між ними. Під операцією тут мають на увазі застосування за принципом множини сум:
Наприклад, такі множини є раціональними виразами над :
- самі множини
;
— раціональний вираз над
;
.
За аналогією з адитивною енергією, яку часто використовують для оцінки множини сум, буває зручно розглядати число розв'язків симетричного рівняння з раціональним виразом. Наприклад,
Істотну частину проблематики арифметичної комбінаторики можна виразити такою постановкою питання.
Нехай Нехай також для деяких Питання Як при Примітка Якщо поле скінченне, то набір |
Наприклад, гіпотеза про суми-добутки стверджує, що якщо ,
,
, то
(тут
).
Як правило, вдається вивести лінійні співвідношення між величинами , тобто нерівності між добутками та степенями різних величин
.
Деякі результати
Про узагальнення сум та добутків:
;
;
;
;
;
.
Про узагальнення енергій:
;
- для будь-кого
якщо
, то
, причому
при
.
Зсуви
Постановка питання
Ідея оцінки раціональних виразів, що поєднують різні операції, виходить з того, що застосування до множини адитивної операції позбавляє її мультиплікативної структури. Цей принцип можна розширити на випадок, коли множина змінюється не складною комбінаторною операцією поелементного додавання, а звичайним адитивним зсувом — додаванням до всіх елементів множини одного числа. Очікується, що від цього мультиплікативна структура множини повинна в більшості випадків змінюватись (наприклад, якщо , то
для деякого
при всіх чи майже всіх
).
Питання Як при фіксованому (але довільному) |
Деякі результати
- якщо
при простому
, то:
;
;
;
;
;
;
, где
при
.
Многочлени
Постановка питання
Ідея комбінування додавання та множення природно приводить до розгляду многочленів, тобто таких самих раціональних виразів, але в яких одна змінна може з'являтися кілька разів (і тим самим складніше впливати на структуру отримуваної множини). Виявляється, в цьому випадку для забезпечення безумовного зростання не обов'язково використовувати три копії множини (як у виразі ), а досить підібрати потрібний многочлен від двох змінних. Вперше таку властивість помітив Бургейн для многочлена
.
Також, за аналогією з теоремою сум-добутків, вивчаються оцінки знизу на для довільних многочленів
.
Деякі результати
Перший результат Бургейна: нехай . Тоді для деякого
істинне, що
.
Під час порівняння і
велике значення має виродженість многочлена
. Якщо він вироджений, тобто подаваний у вигляді
, де
— многочлени і
, то обидві суми можуть виявитися малими, якщо
— арифметична прогресія, адже
. Тому результати формулюються лише для невироджених многочленів:
- якщо
, то
;
- якщо
, то
.
Матричне множення
Властивості
Існують результати про множини добутків набору матриць з тієї чи іншої матричної підгрупи (наприклад, або групи Гейзенберга). Строго кажучи, ці результати стосуються однієї групової операції (матричного множення), так що їх можна віднести до адитивної комбінаторики. Але злиття у визначенні цієї операції і додавання, і множення елементів, а також некоммутативність, що виникає з цього, роблять її властивості дуже нетиповими в порівнянні зі звичайними груповими операціями, на зразок додавання дійсних чисел.
Наприклад, множина матриць часто може зростати від добутку на самого себе за дуже простих умов (великого розміру, обмеження на окремі елементи або відмінності від підгруп).
Деякі результати
Більшість результатів про матричні групи, коли вони стосуються довільних наборів матриць, аналізує величину , а не
. Це не випадковість, а технічна потреба, пов'язана з некомутативністю:
- якщо
, то для множини матриць
(воно лежить у групі Гейзенберга) істинне, що
, де
;
- нехай
породжує всю групу
і
. Тоді
;
(Для інших груп можлива аналогічна оцінка, яка залежить від розмірності її представлень);
- якщо
і
, то структура
сильно пов'язана з підгрупами
(цей зв'язок можна виразити в термінах
).
Застосування
Аналітичні методи вивчення зростання в групі та групах Шевале можна використати для виведення спеціальної форми гіпотези Заремби.
Див. також
Примітки
- Протилежне хибне, оскільки слово «адитивна» утворено від англ. addition (додавання), його вживання точно не доречне для предмета цієї статті. Наприклад, [en] у рецензії на монографію Тао, починаючи мову про теорему сум-добутків, зауважує, що відхиляється від визначення адитивної комбінаторики («Though I am shyingaway from a definition of additive combinatorics…»).
- Erdös, Szemerédi, 1983.
- Roche-Newton, Ruzsa, Shen, Shkredov, 2018, зауваження після теореми 1.5
- Використане тут і далі позначення
не є загальноприйнятим.
- Див. пояснення на прикладі теореми сум-добутків у Гараев, 2010 (теорема 1.1 і коментар відразу після неї)
- Balog, 2011.
- Уривок доповіді С. В. Конягіна (рос.)
- Shkredov, Zhelezov, 2016, наслідок 2
-
, докладніше див. Roche-Newton, Ruzsa, Shen, Shkredov, 2018
-
, докладніше див. Roche-Newton, Shkredov, 2019
- Balog, Roche-Newton, Zhelezov, 2016.
- Olmezov, Semchankau, Shkredov, 2019, вираз 12
- Kerr, Macourt, 2019, наслідок 2.11
- Зворотне, загалом, хибне: мультиплікативний зсув може ніяк не змінити адитивних властивостей множини. Якщо
— арифметична прогресія и
, то
для будь-якого
. Але іноді вдається використати схожі ідеї — див., наприклад, лему 2 в Глибичук, 2006, де при доведенні аналога проблеми Воринга в скінченному полі формулюється подібне твердження в термінах спільної адитивної енергії про існування потрібного зсуву.
- Stevens, de Zeeuw, 2017, наслідок 10
- Warren, 2019.
- Шкредов, 2013, наслідок 5.8
- Hanson, Roche-Newton, Zhelezov (I), 2018.
- Шкредов, 2017, теорема 12
- Hanson, Roche-Newton, Rudnev, 2020, теорема 4.1
- Hanson, Roche-Newton, Zhelezov (II), 2018.
- Многочлени, так чи інакше пов'язані із зростанням множини в літературі часто називають «розширювачами» (expanders).
- Див. розділ 5.2 у Гараев, 2010
- Bourgain, 2005, теорема 2.1 (див. також Гараев, 2010, теорема 5.2)
- Koh, Mojarrad, Pham, Valculescu, 2018, теорема 1.10
- Vu, 2007, теорема 1.2
- Будь-який елемент добутку матриць фактично є многочленом від елементів перемножуваних матриць
- Див. зауваження в Helfgott, 2009 у виносці на с. 3, а також той факт, що нерівність Плюннеке — Ружі в некомутативних групах має особливий вигляд.
- Shkredov, 2019, теорема 2
- Rudnev, Shkredov, 2019, теорема 2
- Див. Nikolov, Pyber, 2007, вираз 2 і зауваження в Helfgott, 2009 на початку розділу 1.3.1
- Helfgott, 2009, теорема 1.1
- Moshchevitin, Shkredov, 2019.
- Shkredov, 2020.
Література
- P. Erdös, E. Szemerédi. On sums and products of integers // Birkhäuser Verlag. — 1983. — P. 213–218.
- Oliver Roche-Newton, Imre Z. Ruzsa, Chun-Yen Shen, Ilya D. Shkredov. On the size of the set
. — 2018. — arXiv:1801.10431v1.
- Oliver Roche-Newton, Ilya D. Shkredov. If
is small then
is superquadratic. — 2019. — arXiv:1810.10842v2.
- Antal Balog. A note on sum-product estimates // Publicationes mathematicae. — 2011. — Vol. 79, iss. 3. — DOI: .
- М. З. Гараев. Суммы и произведения множеств и оценки рациональных тригонометрических сумм в полях простого порядка, // Успехи математических наук. — Российская академия наук, 2010. — Т. 65, вып. 4 (394). — С. 5—66. — DOI: .
- Ilya D. Shkredov, Dmitrii Zhelezov. On additive bases of sets with small product set. — 2016. — arXiv:math/1606.02320.
- А. А. Глибичук. Комбинаторные свойства множеств вычетов по простому модулю и задача Эрдёша — Грэхэма // . — 2006. — Т. 79, вып. 3. — С. 384–395.
- Brandon Hanson, Oliver Roche-Newton, Dmitrii Zhelezov. On iterated product sets with shifts. — 2018. — arXiv:1801.07982v1.
- Brandon Hanson, Oliver Roche-Newton, Dmitrii Zhelezov. On iterated product sets with shifts II. — 2018. — arXiv:math/1806.01697v1.
- Sophie Stevens, Frank de Zeeuw. An improved point-line incidence bound over arbitrary fields // Bulletin of the London Mathematical Society. — 2017. — Vol. 49, iss. 5. — arXiv:1609.06284. — DOI: .
- Audie Warren. On Products of Shifts in Arbitrary Fields. — 2019. — arXiv:1812.01981v2.
- Antal Balog, Oliver Roche-Newton, Dmitry Zhelezov. Expanders with Superquadratic Growth // The electronic journal of combinatorics. — 2016. — Vol. 24, iss. 3. — arXiv:1611.05251v1. — DOI: .
- И. Д. Шкредов. Несколько замечаний о множествах с малым частным // Математический сборник. — 2017. — Т. 208, вып. 12. — arXiv:1603.04948v2. — DOI: .
- Bryce Kerr, Simon Macourt. Multilinear Exponential Sums With A General Class Of Weights. — 2019. — arXiv:1901.00975v2.
- Konstantin I. Olmezov, Aliaksei S. Semchankau, Ilya D. Shkredov. On popular sums and differences of sets with small products. — 2019. — arXiv:1911.12005v1.
- Brandon Hanson, Oliver Roche-Newton, Misha Rudnev. Higher convexity and iterated sum sets. — 2020. — arXiv:2005.00125v1.
- И. Д. Шкредов. Несколько новых результатов о старших энергиях // Труды Московского математического общества. — 2013. — Т. 74, вып. 1.
- J. Bourgain. More on the sum-product phenomenon in prime fields and its applications // International Journal of Number Theory. — 2005. — Vol. 1, iss. 1. — DOI: .
- Doowon Koh, Hossein Nassajian Mojarrad, Thang Pham, Claudiu Valculescu. Four-variable expanders over the prime fields // Proceedings of the American Mathematical Society. — 2018. — Vol. 146, iss. 12. — arXiv:1705.04255. — DOI: .
- Van Vu. Sum-product estimates via directed expanders // Mathematical Research Letters. — 2007. — Vol. 15, iss. 2. — arXiv:0705.0715. — DOI: .
- Ilya D. Shkredov. Some remarks on products of sets in the Heisenberg group and in the affine group. — 2019. — arXiv:1907.03357.
- Misha Rudnev, Ilya D. Shkredov. On growth rate in
, the affine group and sum-product type implications. — 2019. — arXiv:1812.01671v3.
- H. A. Helfgott. Growth in
. — 2009. — arXiv:0807.2027.
- Nikolay Nikolov, László Pyber. Product decompositions of quasirandom groups and a Jordan type theorem // Journal of the European Mathematical Society. — 2007. — Vol. 13, iss. 4. — arXiv:0703343. — DOI: .
- Nikolay G. Moshchevitin, Ilya D. Shkredov. On a modular form of Zaremba's conjecture. — 2019. — arXiv:1911.07487.
- Ilya D. Shkredov. Growth in Chevalley groups relatively to parabolic subgroups and some applications. — 2020. — arXiv:2003.12785.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Arifmeti chna kombinato rika mizhdisciplinarna galuz matematiki sho vivchaye zalezhnist mizh strukturami sho utvoryuyutsya v poli ridshe v kilci operaciyeyu dodavannya i operaciyeyu mnozhennya Pidhid do ponyattya strukturi tut analogichnij aditivnij kombinatorici i gruntuyetsya perevazhno na rozmiri mnozhini sum abo dobutkiv aditivnoyi abo multiplikativnoyi energiyi ta riznih yih kombinaciyah Yak pole zazvichaj rozglyadayut dijsni chi racionalni chisla R displaystyle mathbb R Q displaystyle mathbb Q ta ostachi za prostim modulem Fp displaystyle mathbb F p Neodnoznachnist terminologiyi ta predmet stattiAditivna j arifmetichna kombinatorika molodi nauki sho aktivno rozvivayutsya Yihni metodi ta sposobi postanovki zavdan duzhe shozhi tomu yak pravilo aditivnu kombinatoriku vvazhayut chastinoyu arifmetichnoyi U cij statti opisano lishe temi sho mistyat u tomu chi inshomu viglyadi obidvi operaciyi polya abo zvorotni do nih tobto yaki ne nalezhat do suto aditivnoyi kombinatoriki hocha ostannya stanovit znachnu chastinu arifmetichnoyi Krim togo tut ne porushuyutsya pitannya pro aditivno kombinatorni vlastivosti multiplikativnih pidgrup Fp displaystyle mathbb F p i pov yazanih z nimi mnozhin oskilki hocha yih viznachennya pov yazane zi mnozhennyam ale yihnya multiplikativna struktura zhorstko zafiksovana a kombinatorna skladova ciyeyi nauki peredbachaye tu chi inshu spilnist shodo stupenya strukturovanosti hocha b iz parametrom sho vistupaye v roli konstanti MotivaciyaRozvitok arifmetichnoyi kombinatoriki znachnoyu miroyu motivovanij poyavoyu teoremi sum dobutkiv yaka govorit pro neodminne rozrostannya mnozhini vid zastosuvannya do neyi abo kombinatornogo pidsumovuvannya abo peremnozhennya tobto odniyeyi z dvoh operacij A A a1 a2 a1 a2 A displaystyle A A left lbrace a 1 a 2 a 1 a 2 in A right rbrace A A a1 a2 a1 a2 A displaystyle A times A left lbrace a 1 cdot a 2 a 1 a 2 in A right rbrace Z cogo viplivaye sho kombinuvannya cih operacij takozh tyagne za soboyu rozrostannya yaksho 0 1 A displaystyle 0 1 subset A to A A A max A A 0 1 A A max AA A A displaystyle A A A gg max A A 0 1 A A max AA A A a dodavannya do A displaystyle A skinchennogo chisla elementiv vplivaye na zrostannya lishe nesuttyevo Oskilki teoremu sum dobutkiv dovedeno lishe v slabkij formi dalekij vid gipotezi deyaki vcheni pochali cikavitisya otrimannyam tverdzhen takogo rodu yaki viplivali b iz silnishih form gipotezi nizh dovedeni a zgodom zagalom vivchennyam spivvidnoshennya mizh rezultatami riznih kombinacij dvoh operacij polya Napriklad gipoteza Erdesha Semeredi pro sumi dobutki stverdzhuye sho max A A AA A 2 o 1 A R displaystyle max A A AA geq A 2 o 1 forall A subset mathbb R Z ciyeyi gipotezi viplivalo b sho AA A A 2 o 1 displaystyle AA A geq A 2 o 1 ale dlya mnozhin A N displaystyle A subset mathbb N takij rezultat legko otrimati i bez neyi prostim kombinatornim mirkuvannyam Zavdannya ta rezultatiU comu rozdili dlya opisu rezultativ vikoristovuyutsya zagalnoprijnyati zapisi poyasnennya navedeno v O notaciyi X Y displaystyle X ll Y oznachaye sho X O Y displaystyle X O Y X Y displaystyle X lesssim Y oznachaye sho X log A O 1 Y displaystyle X leq log A O 1 Y Racionalni virazi Postanovka pitannya Nazvemo racionalnim virazom nad mnozhinami A1 Ak displaystyle A 1 dots A k bud yaku kombinaciyu arifmetichnih operacij displaystyle times mizh nimi Pid operaciyeyu tut mayut na uvazi zastosuvannya za principom mnozhini sum A B a b a A b B displaystyle A circ B a circ b a in A b in B Napriklad taki mnozhini ye racionalnimi virazami nad A B C displaystyle A B C sami mnozhini A B C displaystyle A B C A A A a b c a b c A displaystyle A A A a b c a b c in A racionalnij viraz nad A displaystyle A A BC a bc a A b B c C displaystyle A BC a bc a in A b in B c in C Za analogiyeyu z aditivnoyu energiyeyu yaku chasto vikoristovuyut dlya ocinki mnozhini sum buvaye zruchno rozglyadati chislo rozv yazkiv simetrichnogo rivnyannya z racionalnim virazom Napriklad EAB C a1 a2 b1 b2 c1 c2 A2 B2 C2 a1 b1c1 a2 b2c2 displaystyle E AB C a 1 a 2 b 1 b 2 c 1 c 2 in A 2 times B 2 times C 2 a 1 b 1 c 1 a 2 b 2 c 2 Istotnu chastinu problematiki arifmetichnoyi kombinatoriki mozhna viraziti takoyu postanovkoyu pitannya Nehaj F displaystyle mathbb F deyake pole abo neskinchenne abo dosit velike iz zadanogo simejstva skinchennih R1 Rn displaystyle R 1 dots R n racionalni virazi prichomu hocha b v odnomu z nih vikoristovuyetsya displaystyle abo displaystyle i hocha bi v odnomu displaystyle cdot abo displaystyle Nehaj takozh dlya deyakih N displaystyle N i mnozhin A1 Ak F displaystyle A 1 dots A k subset mathbb F vikonuyutsya spivvidnoshennya Aj Naj j 1 k displaystyle A j N alpha j j 1 dots k Ri A1 Ak Nbi i 1 n displaystyle R i A 1 dots A k N beta i i 1 dots n ERi A1 Ak Ngi i 1 n displaystyle E R i A 1 dots A k N gamma i i 1 dots n Pitannya Yak pri N displaystyle N to infty obmezheno mnozhinu mozhlivih znachen a1 ak b1 bk g1 gn displaystyle alpha 1 dots alpha k beta 1 dots beta k gamma 1 dots gamma n zalezhno vid F R1 Rn displaystyle mathbb F R 1 dots R n Primitka Yaksho pole skinchenne to nabir a1 gn displaystyle alpha 1 dots gamma n dorechno dopovniti parametrom e displaystyle varepsilon de N F e displaystyle N mathbb F varepsilon Napriklad gipoteza pro sumi dobutki stverdzhuye sho yaksho F R displaystyle mathbb F mathbb R R1 A A A displaystyle R 1 A A A R2 A A A displaystyle R 2 A A cdot A to max g1 g2 2 displaystyle max gamma 1 gamma 2 2 tut k 1 n 2 displaystyle k 1 n 2 Yak pravilo vdayetsya vivesti linijni spivvidnoshennya mizh velichinami a1 gn displaystyle alpha 1 dots gamma n tobto nerivnosti mizh dobutkami ta stepenyami riznih velichin Aj Ri A1 Ak ERi A1 Ak displaystyle A j R i A 1 dots A k E R i A 1 dots A k Deyaki rezultati Pro uzagalnennya sum ta dobutkiv A R AA AA AA AA 12 A 2 displaystyle forall A subset mathbb R AA AA AA AA geq frac 1 2 A 2 A Fp A lt p1 4 A A A A A A A A A 2 displaystyle forall A subset mathbb F p A lt p 1 4 Rightarrow A A A A A A A A geq A 2 c gt 0 B C R B C B C B C 1 c displaystyle exists c gt 0 forall B C subset mathbb R B C B C geq B C 1 c c gt 0 A R AA A A 32 c displaystyle exists c gt 0 forall A subset mathbb R AA A geq A frac 3 2 c c1 c2 gt 0 A R A A A 1 c1 AAA A 2 c2 displaystyle exists c 1 c 2 gt 0 forall A subset mathbb R A A leq A 1 c 1 Rightarrow AAA geq A 2 c 2 A R A A A A A A A 2 18 displaystyle forall A subset mathbb R A A A A A A gtrsim A 2 frac 1 8 Pro uzagalnennya energij EA B2 A B E A B B displaystyle E A B 2 leq A B E A B B dlya bud kogo k N displaystyle k in mathbb N yaksho A Fp A pc k displaystyle A subset mathbb F p A geq p c k to E A A k A 4kp displaystyle E A A k sim frac A 4k p prichomu c k 12 displaystyle c k to frac 1 2 pri k displaystyle k to infty Zsuvi Postanovka pitannya Ideya ocinki racionalnih viraziv sho poyednuyut rizni operaciyi vihodit z togo sho zastosuvannya do mnozhini aditivnoyi operaciyi pozbavlyaye yiyi multiplikativnoyi strukturi Cej princip mozhna rozshiriti na vipadok koli mnozhina zminyuyetsya ne skladnoyu kombinatornoyu operaciyeyu poelementnogo dodavannya a zvichajnim aditivnim zsuvom dodavannyam do vsih elementiv mnozhini odnogo chisla Ochikuyetsya sho vid cogo multiplikativna struktura mnozhini povinna v bilshosti vipadkiv zminyuvatis napriklad yaksho AA A displaystyle AA ll A to A d A d A 1 c displaystyle A d A d gg A 1 c dlya deyakogo c gt 0 displaystyle c gt 0 pri vsih chi majzhe vsih d displaystyle d Pitannya Yak pri fiksovanomu ale dovilnomu A F displaystyle A subset mathbb F zalezhat odna vid odnoyi multiplikativni vlastivosti rozmir mnozhini dobutkiv ta multiplikativna energiya mnozhin A u u F displaystyle A u u in mathbb F A takozh yaki spilni multiplikativni vlastivosti mnozhin A u1 A uk displaystyle A u 1 dots A u k za riznih u1 uk displaystyle u 1 dots u k napriklad chi isnuyut netrviialni ocinki na A A 1 displaystyle A A 1 Deyaki rezultati yaksho A Fp displaystyle A subset mathbb F p pri prostomu p displaystyle p to A lt p5 8 A A 1 A 6 5 displaystyle A lt p 5 8 Rightarrow A A 1 gg A 6 5 A lt p1 4 A A 1 A 11 9 o 1 displaystyle A lt p 1 4 Rightarrow A A 1 gtrsim A 11 9 o 1 A R a R 0 A A 1 A E A A a A 32 13 displaystyle forall A subset mathbb R forall a in mathbb R setminus 0 A A 1 ll A Rightarrow E times A A a lesssim A 32 13 A Q AA A A 1 k k A k displaystyle forall A subset mathbb Q AA ll A Rightarrow A 1 k gg k A k A R AA 4 A 1 A 1 A 6 displaystyle forall A subset mathbb R AA 4 A 1 A 1 gtrsim A 6 A R A 1 A 1 A 1 16 AA 78 A 111 displaystyle forall A subset mathbb R A 1 A 1 A 1 16 AA 78 gtrsim A 111 A Q u Q 0 max Ak A u k A b k displaystyle forall A subset mathbb Q forall u subset mathbb Q setminus 0 max left lbrace A k A u k right rbrace gg A b k gde b k displaystyle b k to infty pri k displaystyle k in infty Mnogochleni Postanovka pitannya Ideya kombinuvannya dodavannya ta mnozhennya prirodno privodit do rozglyadu mnogochleniv tobto takih samih racionalnih viraziv ale v yakih odna zminna mozhe z yavlyatisya kilka raziv i tim samim skladnishe vplivati na strukturu otrimuvanoyi mnozhini Viyavlyayetsya v comu vipadku dlya zabezpechennya bezumovnogo zrostannya ne obov yazkovo vikoristovuvati tri kopiyi mnozhini yak u virazi A AA displaystyle A AA a dosit pidibrati potribnij mnogochlen vid dvoh zminnih Vpershe taku vlastivist pomitiv Burgejn dlya mnogochlena x2 xy displaystyle x 2 xy Takozh za analogiyeyu z teoremoyu sum dobutkiv vivchayutsya ocinki znizu na max A A f A A displaystyle max A A f A A dlya dovilnih mnogochleniv f displaystyle f Deyaki rezultati Pershij rezultat Burgejna nehaj A B Fp A B pa a 0 1 displaystyle A B subset mathbb F p A sim B sim p alpha alpha in 0 1 Todi dlya deyakogo e e a gt 0 displaystyle varepsilon varepsilon alpha gt 0 istinne sho a2 ab a A b B N1 e displaystyle a 2 ab a in A b in B geq N 1 varepsilon Pid chas porivnyannya A A displaystyle A A i f A A displaystyle f A A velike znachennya maye virodzhenist mnogochlena f displaystyle f Yaksho vin virodzhenij tobto podavanij u viglyadi f g l x y displaystyle f g l x y de l g displaystyle l g mnogochleni i deg l 1 displaystyle deg l 1 to obidvi sumi mozhut viyavitisya malimi yaksho A displaystyle A arifmetichna progresiya adzhe f A A l A A displaystyle f A A leq l A A Tomu rezultati formulyuyutsya lishe dlya nevirodzhenih mnogochleniv yaksho deg f 2 displaystyle deg f 2 to A Fp A p5 8 max A A f A A A 6 5 displaystyle forall A subset mathbb F p A leq p 5 8 Rightarrow max A A f A A gg A 6 5 yaksho deg f d displaystyle deg f d to A Fp max A A f A A min A 3 2dp1 4 p1 3 A 2 3d1 3 displaystyle forall A subset mathbb F p max A A f A A gg min left lbrace frac A 3 2 dp 1 4 frac p 1 3 A 2 3 d 1 3 right rbrace Matrichne mnozhennya Vlastivosti Isnuyut rezultati pro mnozhini dobutkiv naboru matric z tiyeyi chi inshoyi matrichnoyi pidgrupi napriklad SL2 R displaystyle mbox SL 2 mathbb R abo grupi Gejzenberga Strogo kazhuchi ci rezultati stosuyutsya odniyeyi grupovoyi operaciyi matrichnogo mnozhennya tak sho yih mozhna vidnesti do aditivnoyi kombinatoriki Ale zlittya u viznachenni ciyeyi operaciyi i dodavannya i mnozhennya elementiv a takozh nekommutativnist sho vinikaye z cogo roblyat yiyi vlastivosti duzhe netipovimi v porivnyanni zi zvichajnimi grupovimi operaciyami na zrazok dodavannya dijsnih chisel Napriklad mnozhina matric chasto mozhe zrostati vid dobutku na samogo sebe za duzhe prostih umov velikogo rozmiru obmezhennya na okremi elementi abo vidminnosti vid pidgrup Deyaki rezultati Bilshist rezultativ pro matrichni grupi koli voni stosuyutsya dovilnih naboriv matric analizuye velichinu AAA displaystyle AAA a ne AA displaystyle AA Ce ne vipadkovist a tehnichna potreba pov yazana z nekomutativnistyu yaksho A R displaystyle A subset mathbb R to dlya mnozhini matric A 1a001b001 a b A displaystyle mathcal A left lbrace begin pmatrix 1 amp a amp 0 0 amp 1 amp b 0 amp 0 amp 1 end pmatrix a b in A right rbrace vono lezhit u grupi Gejzenberga istinne sho AA A 7 4 c displaystyle mathcal A mathcal A gg mathcal A 7 4 c de c gt 0 displaystyle c gt 0 nehaj A SL2 Fp displaystyle A subset mbox SL 2 mathbb F p porodzhuye vsyu grupu SL2 Fp displaystyle mbox SL 2 mathbb F p i a A a 1 A displaystyle forall a in A a 1 in A Todi AAA min A 21 20 SL2 Fp displaystyle AAA gg min A 21 20 mbox SL 2 mathbb F p A SLn Fp A gt 2 G 1 13 n 1 AAA SLn Fp displaystyle forall A subset mbox SL n mathbb F p A gt 2 G 1 frac 1 3 n 1 Rightarrow AAA mbox SL n mathbb F p Dlya inshih grup mozhliva analogichna ocinka yaka zalezhit vid rozmirnosti yiyi predstavlen yaksho A SL3 Fp displaystyle A subset mbox SL 3 mathbb F p i AAA A 1 d d gt 0 displaystyle AAA ll A 1 delta delta gt 0 to struktura A displaystyle A silno pov yazana z pidgrupami A SL3 Fp displaystyle A subset mbox SL 3 mathbb F p cej zv yazok mozhna viraziti v terminah d displaystyle delta Zastosuvannya Analitichni metodi vivchennya zrostannya v grupi SL2 Fp displaystyle mbox SL 2 mathbb F p ta grupah Shevale mozhna vikoristati dlya vivedennya specialnoyi formi gipotezi Zarembi Div takozhAditivna kombinatorika Aditivna teoriya chisel Teorema sum dobutkivPrimitkiProtilezhne hibne oskilki slovo aditivna utvoreno vid angl addition dodavannya jogo vzhivannya tochno ne dorechne dlya predmeta ciyeyi statti Napriklad en u recenziyi na monografiyu Tao pochinayuchi movu pro teoremu sum dobutkiv zauvazhuye sho vidhilyayetsya vid viznachennya aditivnoyi kombinatoriki Though I am shyingaway from a definition of additive combinatorics Erdos Szemeredi 1983 Roche Newton Ruzsa Shen Shkredov 2018 zauvazhennya pislya teoremi 1 5 Vikoristane tut i dali poznachennya EAB C displaystyle E AB C ne ye zagalnoprijnyatim Div poyasnennya na prikladi teoremi sum dobutkiv u Garaev 2010 teorema 1 1 i komentar vidrazu pislya neyi Balog 2011 Urivok dopovidi S V Konyagina ros Shkredov Zhelezov 2016 naslidok 2 c gt 2 222 displaystyle c gt 2 222 dokladnishe div Roche Newton Ruzsa Shen Shkredov 2018 c2 1392 c112556 o 1 displaystyle c 2 frac 1 392 c 1 frac 125 56 o 1 dokladnishe div Roche Newton Shkredov 2019 Balog Roche Newton Zhelezov 2016 Olmezov Semchankau Shkredov 2019 viraz 12 Kerr Macourt 2019 naslidok 2 11 Zvorotne zagalom hibne multiplikativnij zsuv mozhe niyak ne zminiti aditivnih vlastivostej mnozhini Yaksho A R displaystyle A subset mathbb R arifmetichna progresiya i k A ka a A displaystyle k cdot A ka a in A to k A k A A A displaystyle k cdot A k cdot A A A dlya bud yakogo k displaystyle k Ale inodi vdayetsya vikoristati shozhi ideyi div napriklad lemu 2 v Glibichuk 2006 de pri dovedenni analoga problemi Voringa v skinchennomu poli formulyuyetsya podibne tverdzhennya v terminah spilnoyi aditivnoyi energiyi pro isnuvannya potribnogo zsuvu Stevens de Zeeuw 2017 naslidok 10 Warren 2019 Shkredov 2013 naslidok 5 8 Hanson Roche Newton Zhelezov I 2018 Shkredov 2017 teorema 12 Hanson Roche Newton Rudnev 2020 teorema 4 1 Hanson Roche Newton Zhelezov II 2018 Mnogochleni tak chi inakshe pov yazani iz zrostannyam mnozhini v literaturi chasto nazivayut rozshiryuvachami expanders Div rozdil 5 2 u Garaev 2010 Bourgain 2005 teorema 2 1 div takozh Garaev 2010 teorema 5 2 Koh Mojarrad Pham Valculescu 2018 teorema 1 10 Vu 2007 teorema 1 2 Bud yakij element dobutku matric faktichno ye mnogochlenom vid elementiv peremnozhuvanih matric Div zauvazhennya v Helfgott 2009 u vinosci na s 3 a takozh toj fakt sho nerivnist Plyunneke Ruzhi v nekomutativnih grupah maye osoblivij viglyad Shkredov 2019 teorema 2 Rudnev Shkredov 2019 teorema 2 Div Nikolov Pyber 2007 viraz 2 i zauvazhennya v Helfgott 2009 na pochatku rozdilu 1 3 1 Helfgott 2009 teorema 1 1 Moshchevitin Shkredov 2019 Shkredov 2020 LiteraturaP Erdos E Szemeredi On sums and products of integers Birkhauser Verlag 1983 P 213 218 Oliver Roche Newton Imre Z Ruzsa Chun Yen Shen Ilya D Shkredov On the size of the set AA A displaystyle AA A 2018 arXiv 1801 10431v1 Oliver Roche Newton Ilya D Shkredov If A A displaystyle A A is small then AAA displaystyle AAA is superquadratic 2019 arXiv 1810 10842v2 Antal Balog A note on sum product estimates Publicationes mathematicae 2011 Vol 79 iss 3 DOI 10 5486 PMD 2011 5104 M Z Garaev Summy i proizvedeniya mnozhestv i ocenki racionalnyh trigonometricheskih summ v polyah prostogo poryadka Uspehi matematicheskih nauk Rossijskaya akademiya nauk 2010 T 65 vyp 4 394 S 5 66 DOI 10 4213 rm9367 Ilya D Shkredov Dmitrii Zhelezov On additive bases of sets with small product set 2016 arXiv math 1606 02320 A A Glibichuk Kombinatornye svojstva mnozhestv vychetov po prostomu modulyu i zadacha Erdyosha Grehema 2006 T 79 vyp 3 S 384 395 Brandon Hanson Oliver Roche Newton Dmitrii Zhelezov On iterated product sets with shifts 2018 arXiv 1801 07982v1 Brandon Hanson Oliver Roche Newton Dmitrii Zhelezov On iterated product sets with shifts II 2018 arXiv math 1806 01697v1 Sophie Stevens Frank de Zeeuw An improved point line incidence bound over arbitrary fields Bulletin of the London Mathematical Society 2017 Vol 49 iss 5 arXiv 1609 06284 DOI 10 1112 blms 12077 Audie Warren On Products of Shifts in Arbitrary Fields 2019 arXiv 1812 01981v2 Antal Balog Oliver Roche Newton Dmitry Zhelezov Expanders with Superquadratic Growth The electronic journal of combinatorics 2016 Vol 24 iss 3 arXiv 1611 05251v1 DOI 10 37236 7050 I D Shkredov Neskolko zamechanij o mnozhestvah s malym chastnym Matematicheskij sbornik 2017 T 208 vyp 12 arXiv 1603 04948v2 DOI 10 4213 sm8733 Bryce Kerr Simon Macourt Multilinear Exponential Sums With A General Class Of Weights 2019 arXiv 1901 00975v2 Konstantin I Olmezov Aliaksei S Semchankau Ilya D Shkredov On popular sums and differences of sets with small products 2019 arXiv 1911 12005v1 Brandon Hanson Oliver Roche Newton Misha Rudnev Higher convexity and iterated sum sets 2020 arXiv 2005 00125v1 I D Shkredov Neskolko novyh rezultatov o starshih energiyah Trudy Moskovskogo matematicheskogo obshestva 2013 T 74 vyp 1 J Bourgain More on the sum product phenomenon in prime fields and its applications International Journal of Number Theory 2005 Vol 1 iss 1 DOI 10 1142 S1793042105000108 Doowon Koh Hossein Nassajian Mojarrad Thang Pham Claudiu Valculescu Four variable expanders over the prime fields Proceedings of the American Mathematical Society 2018 Vol 146 iss 12 arXiv 1705 04255 DOI 10 1090 proc 14177 Van Vu Sum product estimates via directed expanders Mathematical Research Letters 2007 Vol 15 iss 2 arXiv 0705 0715 DOI 10 4310 MRL 2008 v15 n2 a14 Ilya D Shkredov Some remarks on products of sets in the Heisenberg group and in the affine group 2019 arXiv 1907 03357 Misha Rudnev Ilya D Shkredov On growth rate in SL2 Fp displaystyle mbox SL 2 mathbb F p the affine group and sum product type implications 2019 arXiv 1812 01671v3 H A Helfgott Growth in SL3 Z pZ displaystyle mbox SL 3 mathbb Z p mathbb Z 2009 arXiv 0807 2027 Nikolay Nikolov Laszlo Pyber Product decompositions of quasirandom groups and a Jordan type theorem Journal of the European Mathematical Society 2007 Vol 13 iss 4 arXiv 0703343 DOI 10 4171 JEMS 275 Nikolay G Moshchevitin Ilya D Shkredov On a modular form of Zaremba s conjecture 2019 arXiv 1911 07487 Ilya D Shkredov Growth in Chevalley groups relatively to parabolic subgroups and some applications 2020 arXiv 2003 12785