Арифметична комбінаторика — Вікіпедія

Арифмети́чна комбінато́рика — міждисциплінарна галузь математики, що вивчає залежність між структурами, що утворюються в полі (рідше — в кільці) операцією додавання і операцією множення.

Підхід до поняття структури тут аналогічний адитивній комбінаториці і ґрунтується переважно на розмірі множини сум (або добутків), адитивної (або мультиплікативної) енергії та різних їх комбінаціях. Як поле зазвичай розглядають дійсні чи раціональні числа (${\displaystyle {\mathbb {R} }}$, ${\displaystyle {\mathbb {Q} }}$) та остачі за простим модулем (${\displaystyle {\mathbb {F} }_{p}}$).

Неоднозначність термінології та предмет статті[ред. | ред. код]

Адитивна й арифметична комбінаторика — молоді науки, що активно розвиваються. Їхні методи та способи постановки завдань дуже схожі, тому, як правило, адитивну комбінаторику вважають частиною арифметичної^[1]. У цій статті описано лише теми, що містять у тому чи іншому вигляді обидві операції поля або зворотні до них, тобто які не належать до суто адитивної комбінаторики (хоча остання становить значну частину арифметичної).

Крім того, тут не порушуються питання про адитивно-комбінаторні властивості мультиплікативних підгруп ${\displaystyle {\mathbb {F} }_{p}^{*}}$ і пов'язаних з ними множин, оскільки, хоча їх визначення пов'язане зі множенням, але їхня мультиплікативна структура жорстко зафіксована, а комбінаторна складова цієї науки передбачає ту чи іншу спільність щодо ступеня структурованості (хоча б із параметром, що виступає в ролі константи).

Мотивація[ред. | ред. код]

Розвиток арифметичної комбінаторики значною мірою мотивований появою теореми сум-добутків, яка говорить про неодмінне розростання множини від застосування до неї або комбінаторного підсумовування, або перемноження, тобто однієї з двох операцій:

${\displaystyle A+A=\left\lbrace {a_{1}+a_{2}:a_{1},a_{2}\in A}\right\rbrace }$

${\displaystyle A\times A=\left\lbrace {a_{1}\cdot a_{2}:a_{1},a_{2}\in A}\right\rbrace }$

З цього випливає, що комбінування цих операцій також тягне за собою розростання: якщо ${\displaystyle \{0,1\}\subset A}$, то

${\displaystyle |A(A+A)|\gg \max\{|A(A+0)|,|1(A+A)|\}=\max\{|AA|,|A+A|\}}$ ,

а додавання до ${\displaystyle A}$ скінченного числа елементів впливає на зростання лише несуттєво. Оскільки теорему сум-добутків доведено лише в слабкій формі (далекій від гіпотези), деякі вчені почали цікавитися отриманням тверджень такого роду, які випливали б із сильніших форм гіпотези, ніж доведені, а згодом — загалом вивченням співвідношення між результатами різних комбінацій двох операцій поля.

Наприклад, гіпотеза Ердеша — Семереді про суми-добутки стверджує, що^[2]

${\displaystyle \max\{|A+A|,|AA|\}\geq |A|^{2-o(1)}\ \forall A\subset {\mathbb {R} }}$

З цієї гіпотези випливало б, що ${\displaystyle |AA+A|\geq |A|^{2-o(1)}}$, але для множин ${\displaystyle A\subset {\mathbb {N} }}$ такий результат легко отримати і без неї простим комбінаторним міркуванням^[3].

Завдання та результати[ред. | ред. код]

У цьому розділі для опису результатів використовуються загальноприйняті записи (пояснення наведено в O-нотації):

• ${\displaystyle X\ll Y}$ означає, що ${\displaystyle X=O(Y)}$

• ${\displaystyle X\lesssim Y}$ означає, що ${\displaystyle X\leq (\log |A|)^{O(1)}Y}$

Раціональні вирази[ред. | ред. код]

Постановка питання[ред. | ред. код]

Назвемо раціональним виразом над множинами ${\displaystyle A_{1},\dots ,A_{k}}$ будь-яку комбінацію арифметичних операцій (${\displaystyle +,-,\times ,/}$) між ними. Під операцією тут мають на увазі застосування за принципом множини сум:

${\displaystyle A\circ B=\{a\circ b\ :\ a\in A,\ b\in B\}}$

Наприклад, такі множини є раціональними виразами над ${\displaystyle A,B,C}$:

• самі множини ${\displaystyle A,\ B,\ C}$;

• ${\displaystyle A(A-A)=\{a(b-c)\ :\ a,b,c\in A\}}$ — раціональний вираз над ${\displaystyle A}$;

• ${\displaystyle A+BC=\{a+bc\ :\ a\in A,\ b\in B,\ c\in C\}}$.

За аналогією з адитивною енергією, яку часто використовують для оцінки множини сум, буває зручно розглядати число розв'язків симетричного рівняння з раціональним виразом. Наприклад,

${\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}\}}$^[4]

Істотну частину проблематики арифметичної комбінаторики можна виразити такою постановкою питання.

Наприклад, гіпотеза про суми-добутки стверджує, що якщо ${\displaystyle {\mathbb {F} }={\mathbb {R} }}$, ${\displaystyle R_{1}(A)=A+A}$, ${\displaystyle R_{2}(A)=A\cdot A}$, то ${\displaystyle \max\{\gamma _{1},\gamma _{2}\}=2}$ (тут ${\displaystyle k=1,\ n=2}$).

Як правило, вдається вивести лінійні співвідношення між величинами ${\displaystyle \alpha _{1},\dots ,\gamma _{n}}$, тобто нерівності між добутками та степенями різних величин ${\displaystyle |A_{j}|,\ |R_{i}(A_{1},\dots ,A_{k})|,\ E_{R_{i}(A_{1},\dots ,A_{k})}}$.

Деякі результати[ред. | ред. код]

Про узагальнення сум та добутків:

${\displaystyle \forall A\subset {\mathbb {R} }:\ |AA+AA+AA+AA|\geq {\frac {1}{2}}|A|^{2}}$^[6];

${\displaystyle \forall A\subset {\mathbb {F} }_{p}:|A|<p^{1/4}\Rightarrow |A(A-A+A-A)+A(A-A)|\geq |A|^{2}}$^[7];

${\displaystyle \exists c>0:\ \forall B,C\subset {\mathbb {R} }:\ |(B+C)(B+C)|\geq |B+C|^{1+c}}$^[8];

${\displaystyle \exists c>0:\ \forall A\subset {\mathbb {R} }:\ |AA+A|\geq |A|^{{\frac {3}{2}}+c}}$^[9];

${\displaystyle \exists c_{1},c_{2}>0:\ \forall A\subset {\mathbb {R} }:\ |A+A|\leq |A|^{1+c_{1}}\Rightarrow |AAA|\geq |A|^{2+c_{2}}}$^[10];

${\displaystyle \forall A\subset {\mathbb {R} }:\ |(A-A)(A-A)(A-A)|\gtrsim |A|^{2+{\frac {1}{8}}}}$^[11].

Про узагальнення енергій:

• ${\displaystyle E_{A+B}^{2}\leq |A/B|E_{(A+B)/B}}$^[12];

• для будь-кого ${\displaystyle k\in {\mathbb {N} }}$ якщо ${\displaystyle A\subset {\mathbb {F} }_{p},\ |A|\geq p^{c(k)}}$, то ${\displaystyle E_{(A-A)^{k}}\sim {\frac {|A|^{4k}}{p}}}$, причому ${\displaystyle c(k)\to {\frac {1}{2}}}$ при ${\displaystyle k\to \infty }$^[13].

Зсуви[ред. | ред. код]

Постановка питання[ред. | ред. код]

Ідея оцінки раціональних виразів, що поєднують різні операції, виходить з того, що застосування до множини адитивної операції позбавляє її мультиплікативної структури. Цей принцип можна розширити на випадок, коли множина змінюється не складною комбінаторною операцією поелементного додавання, а звичайним адитивним зсувом — додаванням до всіх елементів множини одного числа. Очікується, що від цього мультиплікативна структура множини повинна в більшості випадків змінюватись (наприклад, якщо ${\displaystyle |AA|\ll |A|}$, то ${\displaystyle |(A+d)(A+d)|\gg |A|^{1+c}}$ для деякого ${\displaystyle c>0}$ при всіх чи майже всіх ${\displaystyle d}$)^[14].

Деякі результати[ред. | ред. код]

• якщо ${\displaystyle A\subset {\mathbb {F} }_{p}}$ при простому ${\displaystyle p}$, то:

• • ${\displaystyle |A|<p^{5/8}\Rightarrow |A(A+1)|\gg |A|^{6/5}}$^[15];

• • ${\displaystyle |A|<p^{1/4}\Rightarrow |A(A+1)|\gtrsim |A|^{11/9-o(1)}}$^[16];

• ${\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}}$^[17];

• ${\displaystyle \forall A\subset {\mathbb {Q} }_{+}:\ |AA|\ll |A|\Rightarrow |(A+1)^{k}|\gg _{k}|A|^{k}}$^[18];

• ${\displaystyle \forall A\subset {\mathbb {R} }_{+}:\ |AA|^{4}|(A+1)(A+1)|\gtrsim |A|^{6}}$^[19];

• ${\displaystyle \forall A\subset {\mathbb {R} }_{+}:\ |(A+1)(A+1)(A+1)|^{16}|AA|^{78}\gtrsim |A|^{111}}$^[20];

• ${\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)}}$, где ${\displaystyle b(k)\to \infty }$ при ${\displaystyle k\in \infty }$^[21].

Многочлени[ред. | ред. код]

Постановка питання[ред. | ред. код]

Ідея комбінування додавання та множення природно приводить до розгляду многочленів, тобто таких самих раціональних виразів, але в яких одна змінна може з'являтися кілька разів (і тим самим складніше впливати на структуру отримуваної множини). Виявляється, в цьому випадку для забезпечення безумовного зростання не обов'язково використовувати три копії множини (як у виразі ${\displaystyle A+AA}$), а досить підібрати потрібний многочлен від двох змінних^[22]. Вперше таку властивість помітив Бургейн для многочлена ${\displaystyle x^{2}+xy}$^[23].

Також, за аналогією з теоремою сум-добутків, вивчаються оцінки знизу на ${\displaystyle \max\{|A+A|,|f(A,A)|\}}$ для довільних многочленів ${\displaystyle f}$.

Деякі результати[ред. | ред. код]

Перший результат Бургейна: нехай ${\displaystyle A,B\subset {\mathbb {F} }_{p},\ |A|\sim |B|\sim p^{\alpha },\ \alpha \in (0;1)}$ . Тоді для деякого ${\displaystyle \varepsilon =\varepsilon (\alpha )>0}$ істинне, що

${\displaystyle \#\{a^{2}+ab\ :\ a\in A,\ b\in B\}\geq N^{1+\varepsilon }}$^[24].

Під час порівняння ${\displaystyle |A+A|}$ і ${\displaystyle |f(A,A)|}$ велике значення має виродженість многочлена ${\displaystyle f}$. Якщо він вироджений, тобто подаваний у вигляді ${\displaystyle f=g(l(x,y))}$, де ${\displaystyle l,g}$ — многочлени і ${\displaystyle \deg l=1}$, то обидві суми можуть виявитися малими, якщо ${\displaystyle A}$ — арифметична прогресія, адже ${\displaystyle |f(A,A)|\leq |l(A,A)|}$. Тому результати формулюються лише для невироджених многочленів:

• якщо ${\displaystyle \deg f=2}$, то ${\displaystyle \forall A\subset {\mathbb {F} }_{p}\ :\ |A|\leq p^{5/8}\Rightarrow \max\{|A+A|,|f(A,A)|\}\gg |A|^{6/5}}$^[25];

• якщо ${\displaystyle \deg f=d}$, то ${\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 }$^[26].

Матричне множення[ред. | ред. код]

Властивості[ред. | ред. код]

Існують результати про множини добутків набору матриць з тієї чи іншої матричної підгрупи (наприклад, ${\displaystyle {\mbox{SL}}_{2}({\mathbb {R} })}$ або групи Гейзенберга). Строго кажучи, ці результати стосуються однієї групової операції (матричного множення), так що їх можна віднести до адитивної комбінаторики. Але злиття у визначенні цієї операції і додавання, і множення елементів^[27], а також некоммутативність, що виникає з цього, роблять її властивості дуже нетиповими в порівнянні зі звичайними груповими операціями, на зразок додавання дійсних чисел.

Наприклад, множина матриць часто може зростати від добутку на самого себе за дуже простих умов (великого розміру, обмеження на окремі елементи або відмінності від підгруп).

Деякі результати[ред. | ред. код]

Більшість результатів про матричні групи, коли вони стосуються довільних наборів матриць, аналізує величину ${\displaystyle |AAA|}$, а не ${\displaystyle |AA|}$. Це не випадковість, а технічна потреба, пов'язана з некомутативністю^[28]:

• якщо ${\displaystyle A\subset {\mathbb {R} }}$, то для множини матриць ${\displaystyle {\mathcal {A}}=\left\lbrace {{\begin{pmatrix}1&a&0\\0&1&b\\0&0&1\end{pmatrix}}\ :\ a,b\in A}\right\rbrace }$ (воно лежить у групі Гейзенберга) істинне, що ${\displaystyle |{\mathcal {A}}{\mathcal {A}}|\gg |{\mathcal {A}}|^{7/4+c}}$, де ${\displaystyle c>0}$^[29];

• нехай ${\displaystyle A\subset {\mbox{SL}}_{2}({\mathbb {F} }_{p})}$ породжує всю групу ${\displaystyle {\mbox{SL}}_{2}({\mathbb {F} }_{p})}$ і ${\displaystyle \forall a\in A\ :\ a^{-1}\in A}$ . Тоді ${\displaystyle |AAA|\gg \min\{|A|^{21/20},\ |{\mbox{SL}}_{2}({\mathbb {F} }_{p})|\}}$^[30];

• ${\displaystyle \forall A\subset {\mbox{SL}}_{n}({\mathbb {F} }_{p})\ :\ |A|>2|G|^{1-{\frac {1}{3(n+1)}}}\Rightarrow AAA={\mbox{SL}}_{n}({\mathbb {F} }_{p})}$ (Для інших груп можлива аналогічна оцінка, яка залежить від розмірності її представлень)^[31];

• якщо ${\displaystyle A\subset {\mbox{SL}}_{3}({\mathbb {F} }_{p})}$ і ${\displaystyle |AAA|\ll |A|^{1+\delta },\ \delta >0}$, то структура ${\displaystyle A}$ сильно пов'язана з підгрупами ${\displaystyle A\subset {\mbox{SL}}_{3}({\mathbb {F} }_{p})}$ (цей зв'язок можна виразити в термінах ${\displaystyle \delta }$)^[32].

Застосування[ред. | ред. код]

Аналітичні методи вивчення зростання в групі ${\displaystyle {\mbox{SL}}_{2}({\mathbb {F} }_{p})}$ та групах Шевале можна використати для виведення спеціальної форми гіпотези Заремби^[33][34].

Див. також[ред. | ред. код]

• Адитивна комбінаторика
• Адитивна теорія чисел
• Теорема сум-добутків

Примітки[ред. | ред. код]

Література[ред. | ред. код]

• 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 ${\displaystyle AA+A}$. — 2018. — arXiv:1801.10431v1.
• Oliver Roche-Newton, Ilya D. Shkredov. If ${\displaystyle A+A}$ is small then ${\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.
• М. З. Гараев. Суммы и произведения множеств и оценки рациональных тригонометрических сумм в полях простого порядка, // Успехи математических наук. — Российская академия наук, 2010. — Т. 65, вып. 4 (394). — С. 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.
• А. А. Глибичук. Комбинаторные свойства множеств вычетов по простому модулю и задача Эрдёша — Грэхэма // Математические заметки. — 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: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.
• И. Д. Шкредов. Несколько замечаний о множествах с малым частным // Математический сборник. — 2017. — Т. 208, вып. 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.
• И. Д. Шкредов. Несколько новых результатов о старших энергиях // Труды Московского математического общества. — 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: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 ${\displaystyle {\mbox{SL}}_{2}({\mathbb {F} }_{p})}$, the affine group and sum-product type implications. — 2019. — arXiv:1812.01671v3.
• H. A. Helfgott. Growth in ${\displaystyle {\mbox{SL}}_{3}({\mathbb {Z} }/p{\mathbb {Z} })}$. — 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: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.

п о р Розділи математики огляд[en] переліки тем Галузі Алгебра елементарна лінійна полілінійна абстрактна Теорія груп геометрична комбінаторна обчислювальна Алгоритми Арифметика / Теорія чисел адитивна алгебрична аналітична Геометрія дискретна алгебрична біраціональна диференціальна синтетична скінченна Диференціальні рівняння / Динамічні системи Комбінаторика адитивна алгебрична арифметична геометрична многогранників нумераційна топологічна Математика та мистецтво Математична логіка Математична статистика Математична фізика Обчислення / Аналіз Оптимізація Опуклий аналіз Рекреаційна математика Статистика Теорія графів алгебрична екстремальна спектральна Теорія ігор Теорія інформації Теорія ймовірності Теорія категорій Теорія керування Теорія Лі Теорія множин Теорія порядку Теорія представлень Топологія загальна алгебрична диференціальна Тригонометрія Функціональний аналіз Чисельний аналіз Підрозділи Чиста Прикладна Дискретна Обчислювальна Експериментальна   Категорія   Портал