Перегляд вихідного коду сторінки Теорема сум-добутків

'''Теорема сум-добутків'''&nbsp;— теорема [[Арифметична комбінаторика|арифметичної комбінаторики]], що встановлює неструктурованість будь-якої досить великої множини відносно хоча б однієї з операцій [[Поле (алгебра)|поля]] (додавання та множення). Як показник структурованості використовують, відповідно, розміри [[Множина сум|множини сум]] і множини добутків.

== Формулювання ==
Нехай <math>A \subset {\mathbb F}</math>&nbsp;— підмножина деякого [[Кільце (алгебра)|кільця]] <math>{\mathbb F}</math> (зазвичай <math>{\mathbb F}</math> є [[Поле (алгебра)|полем]], але формально можна розглядати і кільце) з операціями <math>+</math> і <math>\cdot</math>. Розглянемо дві похідні від <math>A</math> множини:

: <math>A+A = \left\lbrace{a_1 + a_2 : a_1, a_2 \in A}\right\rbrace</math>

: <math>A \times A = \left\lbrace{a_1 \cdot a_2 : a_1, a_2 \in A}\right\rbrace</math>

Якщо множина <math>A</math> структурована відносно додавання (наприклад, у ній багато [[Арифметична прогресія|арифметичних прогресій]], або [[Узагальнена арифметична прогресія|узагальнених арифметичних прогресій]], або їх великих шматків), то множина <math>A+A</math> буде відносно невеликою&nbsp;— адже суми багатьох пар елементів збіжаться.

Якщо ж <math>A</math> структурована відносно множення, то, з аналогічної причини, не дуже великою буде множина <math>A \times A</math>.

Теорема стверджує, що хоча б одна з множин <math>A+A</math> і <math>A \times A</math> дуже велика відносно <math>A</math>, тобто відносно хоча б однієї з операцій структура буде нерегулярною.

Конкретніше, теорема встановлює степеневе зростання розміру більшої з похідних множин відносно розміру початкової:{{Рамка}}
'''Теорема'''

Для деякої сталої <math>\delta = \delta({\mathbb F}) > 0</math> і довільної множини <math>A \subset {\mathbb F}</math> (для скінченної <math>{\mathbb F}</math>&nbsp;— з обмеженнями на розмір) виконується співвідношення

: <math>\max \left\lbrace{|A+A|,|A \times A|}\right\rbrace > |A|^{1 + \delta}</math>
{{/рамка}}Для різних кілець удається отримати оцінки з різними <math>\delta</math>. Також для деяких (особливо для [[Поле Галуа|скінченних]]) кілець можливе додавання умов на розмір множини <math>A</math>, за яких виконується теорема для даної <math>\delta</math>.

=== Останні випадки ===
Найзручнішими для вивчення виявляються крайні випадки гіпотези:

* '''мало сум, багато добутків''': якщо <math>|A+A| \ll |A|</math>, то <math>|AA| \ge |A|^{2-o(1)}</math><ref>Розв'язано в {{Sfn0|Elekes, Ruzsa|2003}}</ref>

* '''мало добутків, багато сум''': якщо <math>|AA| \ll |A|</math>, то <math>|A+A| \ge |A|^{2-o(1)}</math><ref>У {{Sfn0|Murphy, Rudnev, Shkredov, Shteinikov|2019}} отримано кращі результати, ніж у загальному випадку</ref>

== Приклади ==
Класичними прикладами, що ілюструють теорему сум-добутків, є арифметична прогресія <math>A=\left\lbrace{1,\dots,n}\right\rbrace</math> та геометрична прогресія <math>B=\left\lbrace{1,2,4,\dots,2^{n-1}}\right\rbrace</math>.

Арифметична прогресія максимально впорядкована відносно додавання, так що <math>|A+A| < 2 |A|</math>, Однак із її чисел можна скласти багато різних добутків, так що <math>|A \times A| = \Omega \left({\frac{|A|^2}{\log |A|}}\right)</math><ref>{{Cite web|url=http://oeis.org/A027424|title=Источник|accessdate=2018-01-21|archivedate=2018-01-22|archiveurl=https://web.archive.org/web/20180122125129/http://oeis.org/A027424|deadurl=no}}</ref>, тому відносно множення вона зовсім невпорядкована.

Так само для [[Геометрична прогресія|геометричної прогресії]] виконується <math>|B \times B| < 2 |B|</math> але очевидно (якщо розглянути [[Двійкова система числення|двійкове]] подання чисел), що <math>|B+B| = \Omega(|B|^2)</math>.

== Результати ==

=== Для дійсних чисел ===
При <math>{{\mathbb F}} = {{\mathbb R}}</math> теорему сум-добутків іноді називають також '''теоремою Ердеша&nbsp;— Семереді''', оскільки саме вони 1983 року підняли питання розгляду співвідношення кількостей сум і добутків. У тій самій праці вони висунули гіпотезу про те, що величина <math>\varepsilon</math> може бути як завгодно близькою до одиниці (тобто <math>\max \left\lbrace{|A+A|,|A \times A|}\right\rbrace > |A|^{2 - o(1)}</math>). Однак там само вони висунули ще кілька гіпотез, зокрема, аналогічну для <math>k</math> доданків та множин: <math>\max \left\lbrace{|A+\dots+A|,|A \times \dots \times A|}\right\rbrace > |A|^{k - o(1)}</math>.
{| class="wikitable"
! colspan="3" |Хронологія покращення <math>\delta</math> в оцінці <math>\max \{ |A+A|, |AA| \} \ge |A|^{1 + \delta - o(1)},\ A \subset {\mathbb R}</math>
|-
! Рік
! Значення <math>\delta</math>
! Автор(и)
|- align="center"
| 1983
| <math>1/31</math> <sup>(*)(**)</sup>
| [[Пал Ердеш|Ердеш]], [[Ендре Семереді|Семереді]]<ref>У першій праці {{Sfn0|Erdös, Szemerédi|1983}} не уточнювалося значення <math>\delta</math>, а лише доводилось існування. Тим не менш, пряме слідування міркуванням тої праці показує, що вона істинна для <math>\delta=1/31</math>. У явному вигляді це значення згадано пізніше в {{Sfn0|Nathanson|1997}}</ref> <math>1 + \delta</math> замість <math>1 + \delta - o(1)</math>
|- align="center"
| 1998
| <math>1/15</math> <sup>(*)(**)</sup>
| {{Не перекладено|Кевін Форд|Форд|en|Kevin Ford (mathematician)}} {{Sfn|Ford|1998}}
|- align="center"
| 1997
| <math>1/4</math> <sup>(**)</sup>
| {{Не перекладено|Дьордь Елекеш|Елекеш|en|György Elekes}} {{Sfn|Elekes|1997}}
|- align="center"
| 2005
| <math>3/11</math>
| {{Не перекладено|Джозеф Шоймоші|Шоймоши|en|József Solymosi}} {{Sfn|Solymosi|2005}}
|- align="center"
| 2009
| <math>1/3</math>
| Шоймоші {{Sfn|Solymosi|2009}}
|- align="center"
| 2015
| <math>\frac{1}{3}+\frac{1}{20598} \approx 0.333381...</math>
| {{Нп|Конягін Сергій Володимирович|Конягін|ru|Конягин, Сергей Владимирович}}, {{Нп|Шкредов Ілля Дмитрович|Шкредов|ru|Шкредов, Илья Дмитриевич}}{{Sfn|Konyagin, Shkredov|2015}}
|- align="center"
| 2016
| <math>\frac{1}{3}+\frac{5}{9813} \approx 0.333842...</math>
| Конягін, Шкредов {{Sfn|Konyagin, Shkredov|2016}}
|- align="center"
| 2016
| <math>\frac{1}{3}+\frac{1}{1509} \approx 0.333996...</math>
| Руднєв, Шкредов, Стівенс{{Sfn|Rudnev, Shkredov, Stevens|2020}}
|- align="center"
| 2019
| <math>\frac{1}{3}+\frac{5}{5277} \approx 0.334280...</math>
| Шакан {{Sfn|Shakan|2019}}
|- align="center"
| 2020<br/>(препринт)
| <math>\frac{1}{3}+\frac{2}{1167} \approx 0.335047...</math>
| Руднєв, Стівенс {{Sfn|Rudnev, Stevens|2020}}
|- align="center"
| colspan="3" | <sup>(*)</sup> Тільки для <math>A \subset {\mathbb Z}</math><br/><sup>(**)</sup> Правильно і для степеня <math>1 + \delta</math> замість <math>1 + \delta - o(1)</math>
|}

=== Для полів лишків за простим модулем ===
Теренс Тао у своїй монографії зазначає, що задачу про отримання аналога результату Ердеша та Семереді в полях <math>{\mathbb F}_p</math> поставив 1999 року Т.&nbsp;Вольф (у приватній бесіді) для підмножин <math>A \subset {\mathbb F}_p</math> потужності порядку <math>p^{1/2}</math>.

Задачу сум-добутків у <math>{\mathbb F}_p</math> розв'язано в працях [[Жан Бурген|Бургена]], Гліббичука та [[Конягін Сергій Володимирович|Конягіна]] і Бургейна, Каца та Тао. Вони довели таку теорему:{{Рамка}}
Для будь-якого <math>\varepsilon > 0</math> існує <math>\delta = \delta(\varepsilon) > 0</math> таке, що якщо <math>A \subset {\mathbb F}_p</math> і <math>|A| < p^{1-\varepsilon}</math>, то виконується оцінка
: <math>\max \left\lbrace{|A+A|, |A \times A|}\right\rbrace \ge |A|^{1+\delta}</math>
{{/рамка}}Вимога <math>|A| < p^{1 - \varepsilon}</math> вумові теоремиє природниою т скільки, якщо <math>|A|</math> має порядок близький до <math>p</math>, то обидві величини <math>|A+A|</math> і <math>|A \times A|</math> будуть пзапорядкуомблизькіимидо <math>|A|</math>{{Sfn|Гараев|2010|с=1—2}}.

=== Для довільних кілець ===
Теренс Тао досліджував межі можливостей узагальнення теореми на довільні [[Кільце (алгебра)|кільця]] та, зокрема, зв'язок екстремальних випадків малих значень <math>|A+A|</math> і <math>|A \cdot A|</math> з кількістю [[Дільник нуля|дільників нуля]] у множині <math>A</math> та близькістю її структури до [[Підкільце|підкільця]]<ref>{{Citation|last=Tao|first=Terence|author-link=Теренс Тао|arxiv=0806.2497|issue=2|journal=Contributions to Discrete Mathematics|mr=2592424|pages=59–82|title=The sum-product phenomenon in arbitrary rings|volume=4|id=hdl:[http://hdl.handle.net/10515/sy5r78637 10515/sy5r78637]|year=2009}}.</ref>.

== Методи доведення ==

=== Для дійсних чисел ===

==== Перші доведення ====
У доведенні Ердеша та Семереді використано той факт, що за малих <math>|A + A|</math> і <math>|A \times A|</math> існує розв'язок системи

: <math>\begin{cases} b_1 + b_3 = b_2 + b_4 \\ b_1 b_5 = b_2 b_6\, \end{cases}</math>

де <math>b_i</math> належать деяким (різним) підмножинам <math>A</math>, а на множину <math>A</math> накладено особливі умови. Використовуючи таке твердження як лему, можна довести теорему і для довільної множини <math>A</math>{{Sfn|Erdös, Szemerédi|1983}}.

{{Якір|Методи.Елекеш}}

==== Теорема Семереді&nbsp;— Троттера (Елекеш, 1997) ====
Якщо всі елементи <math>a \in A</math> мають багато подань у вигляді <math>a = p_1 p_2,\ p_1 \in \Pi_1,\ p_2 \in \Pi_2</math> для деяких невеликих множин <math>\Pi_1 \Pi_2</math>, то для оцінки числа розв'язків рівняння

: <math>a+b=c,\ a \in A,\ b \in B,\ c \in C\ .</math>

з будь-якими множинами <math>B, C</math> можна використовувати рівняння

: <math>p_1 p_2 + b = c,\ p_1 \in \Pi_1,\ p_2 \in \Pi_2,\ b \in B,\ c \in C\ .</math>

З іншого боку, розв'язки такого рівняння відповідають [[Інцидентність (геометрія)|інциденціям]] між прямими, які параметризуються парами <math>(p_1, b)</math>, і точками, які параметризуються парами <math>(p_2, c)</math>. Тому для їх оцінки виявляється зручно використовувати загальні результати про інциденції, найкращий із яких&nbsp;— [[теорема Семереді — Троттера]]<ref>Див. {{Sfn0|Rudnev, Stevens|2020}}, лема 3</ref><ref>Подібно до цього розклад <math>a = p_1 - p_2,\ p_1 \in \Pi_1,\ p_2 \in \Pi_2</math> можна використати для аналізу <math>E^{\times}(A)</math>. Див. {{Sfn0|Rudnev, Stevens|2020}}, лема 4.</ref>.

Саме це використав Елекеш для доведення теореми з показником <math>\delta=\frac{1}{4}</math>{{Sfn|Elekes|1997}}. Неявно його доведення можна поділити на два етапи:

* аналіз рівняння <math>a+b=c,\ a \in A, b \in B, c \in C</math> (тривіально, за допомогою розкладання <math>\Pi_1:=AA,\ \Pi_2:=1/A</math>)

* застосування отриманих оцінок (тривіально, для <math>B:=A,\ C:=A+A</math>)

Така декомпозиція важлива для осмислення [[Теорема сум-добутків#Методи.Нетривіальний розклад|методів, що виникли пізніше]].

==== Побудова Шоймоші (Шоймоші, 2009) ====
[[Файл:Sum-product-solymosi-construction.png|міні|300x300пкс| Побудова Шоймоші. Червоні точки мають координати з <math>A \times A</math>.<br/>Зелені точки відповідають сумам червоних із сусідніх прямих. Усі вони гарантовано різні та належать <math>(A+A) \times (A+A)</math>.<br/>Кількість ліній із червоними точками виражається через <math>|AA|</math>]]
Шоймоші використав той факт, що якщо <math>\frac{a}{b} < \frac{c}{d}</math>, то

: <math>\frac{a}{b} < \frac{a+c}{b+d} < \frac{c}{d}\ .</math>

З цього випливає, що якщо <math>\frac{a_1}{b_1} < \frac{a_2}{b_2} < \frac{a_3}{b_3}</math>, то

: <math>\frac{a_1+a_2}{b_1+b_2} < \frac{a_2+a_3}{b_2+b_3}\ .</math>

Разом з тим, за фіксованих значень <math>\lambda \in A/A,\ \mu \in A/A</math> усі пари <math>(a+c, b+d)</math>, що утворюються поданнями

: <math>\lambda = \frac{a}{b},\ \mu = \frac{c}{d},\ a,b,c,d \in A</math>

будуть різними, тому, підсумувавши їх за «сусідніми» парами <math>(\lambda, \mu)</math>, можна отримати оцінку на <math>|A+A|</math> в термінах числа таких подань. А воно, у свою чергу, виражається (опосередковано) через <math>|AA|</math><ref>Див. {{Sfn0|Solymosi|2009}}, формула (2).</ref>.

Найнаочніше цю ідею можна виразити геометрично, як підсумовування точок з <math>A \times A</math>, які лежать на сусідніх прямих, що виходять із [[Початок координат|початку координат]].

{{Якір|Методи.Розбиття_Шоймоші}}

===== Розбиття побудови Шоймоші (Конягін, Шкредов, 2015) =====
[[Файл:Sum-product-konyagin-shkredov-construction.png|міні|300x300пкс| Розбиття побудови Шоймоші за методом Конягіна-Шкредова<br/>Кольори ліній, що виходять із початку координат, відповідають блокам, у кожному з яких оцінюється кількість збігів сум.<br/>Сині та фіолетові лінії позначають підсумовувані пари червоних точок із однаковими сумами.]]
Якщо в побудові Шоймоші прибрати умову про те, що підсумовуювані очки, повинні належати сусіднім прямим, то вже ніщо не буде гарантувати, що всі отримувані суми будуть різними. Наприклад, узагалі всі суми точок із <math>A \times A</math> можуть бути різними лише в екстремальному випадку <math>|A+A| \gg |A|^2</math>, а він уже задовольняє гіпотезу сум-добутків.

Виходячи з цього, Конягін та Шкредов оцінили мінімальну кількість збігів таких сум у проміжному випадку (коли <math>|A+A|</math> і <math>|AA|</math> дорівнюють нижній оцінці, тобто <math>|A|^{4/3}</math>). Щоб оцінити кількість збігів, вони розбили всі прямі на блоки з однакового числа таких, що йдуть підряд, і оцінювали кількість збігів у кожному блоці для більшості з них. Використовуючи ці оцінки, вони отримали результат із <math>\delta > \frac{1}{3}</math><ref>Див. {{Sfn0|Konyagin, Shkredov|2015}}, доведення леми 10</ref>.

{{Якір|Методи.Нетривіальний_розклад}}

===== Нетривіальний мультиплікативний розклад (Руднєв, Стівенс, 2020) =====
Збіги двох сум точок, які [[Теорема сум-добутків#Методи.Розбиття Шоймоші|розглядали Конягін і Шкредов]], означають наявність розв'язку системи рівнянь

: <math>\begin{cases} \lambda_1 a_1 + \lambda_2 a_2 = \lambda_3 a_3 + \lambda_4 a_4 \\ a_1 + a_2 = a_3 + a_4\, \end{cases}</math>

де <math>(a_i, \lambda_i a_i) \in A \times A</math> і всі <math>\lambda_i</math> та пари <math>(\lambda_1, \lambda_2), (\lambda_3, \lambda_4)</math> різні. Редукуючи систему за [[Метод Гауса|методом Гаусса]] (за одну дію), можна отримати рівняння

: <math>a_3 = c_1 a_1 - c_2 a_2</math>

зі сталими <math>c_1, c_2</math> і тими ж умовами на <math>a_1, a_2</math>. Руднєв і Стівенс застосували це для явної побудови мультиплікативного розкладу великої підмножини <math>A</math> зі кращими властивостями, ніж у тривіального<ref>Див. {{Sfn0|Rudnev, Stevens|2020}}, с. 10 (після речення 1)</ref>.

За аналогією з [[Методи.Елекеш|доведенням Елекеша]], це дозволяє розділити доведення оцінок із показником <math>\delta = \frac{1}{3} + c</math> на два етапи:

* застосування нового мультиплікативного розкладання;

* [[Теорема сум-добутків#Методи.Старші енергії|нетривіальне застосування]] рівняння <math>a-b=c</math> для оцінки <math>|A+A|</math> .<ref>Якщо застосовувати ці оцінки тривіально, так само, як і в Елекеша, то результатом буде <math>\delta=\frac{1}{3}</math></ref>

==== Використання старших енергій ====
Найпопулярніший шлях використання рівнянь для оцінення <math>|A+A|</math>&nbsp;— використання [[Адитивна енергія|адитивної енергії]] та її узагальнень. Результати [[Теорема сум-добутків#Методи.Елекеш|застосування теореми Семереді — Троттера]] дозволяють найкраще аналізувати рівняння вигляду

: <math>E_3(A,D) := \{ (a_1,a_2,a_3,d_1,d_2,d_3) \in A^3 \times D^3 \ :\ a_1 - d_1 = a_2 - d_2 = a_3 - d_3 \}</math>

для довільного <math>D</math>. Руднєв і Стівенс запропонували метод використання такої адитивної енергії за допомогою розгляду рівняння

: <math>d = (a+b) - (a+c)\,\ a,b,c \in A,\ d \in D\ ,</math>

де <math>D</math> відповідає множині популярних (із багатьма поданнями) різниць, а <math>a+b</math> належить множині популярних сум. Крім задачі сум-добутків, розробка подібних методів є актуальною для оцінення сум [[Опукла послідовність|опуклих послідовностей]]<ref>Див. {{Sfn0|Rudnev, Stevens|2020}}, теорема 5, особливо формулу (25)</ref>.

Існує схожий операторний метод, який менш ефективний для оцінення <math>|A+A|</math>, але дозволяє краще вивчати зв'язок між <math>E(A)</math> і <math>|AA|</math><ref>Див. {{Sfn0|Olmezov, Semchankau, Shkredov|2020}}, теорема 2</ref>.

=== Для простих полів ===
Під час доведення теореми для <math>{\mathbb F} = {\mathbb F}_p</math> широко використовують поняття [[Адитивна енергія|адитивної енергії]], [[нерівність Плюннеке — Ружі]] та оцінки Балога&nbsp;— Семереді&nbsp;— Гауерса. Одне з можливих доведень використовує нижню оцінку розміру множини <math>R(A) = A \left({\frac{A \times A - A \times A}{A - A} + A}\right)</math> і той факт, що з верхніх оцінок розмірів <math>A+A</math> і <math>A \times A</math> випливає верхня оцінка розміру <math>R(A)</math>, що суперечить нижній{{Sfn|Гараев|2010|с=14—25}}<ref name="MCAC">[https://www.math.cmu.edu/~af1p/Teaching/AdditiveCombinatorics/allnotes.pdf Mini course of additive combinatorics] {{Webarchive|url=https://web.archive.org/web/20170829160603/https://www.math.cmu.edu/~af1p/Teaching/AdditiveCombinatorics/allnotes.pdf |date=2017-08-29 }}, замітки за лекціями [[Принстонський університет|Принстонського університету]]</ref>.

== Застосування ==
[[Жан Бурген|Бурген]], Глібичук і [[Конягін Сергій Володимирович|Конягін]]<ref>{{Cite web|url=http://onlinelibrary.wiley.com/doi/10.1112/S0024610706022721/abstract;jsessionid=49C006BC1BE5C8063CF48EB4A3F70F31.f03t02|title=J. Bourgain, A. A. Glibichuk, S. V. Konyagin, «Estimates for the number of sums and products and for exponential sums in fields of prime order», J. London Math. Soc. (2), 73:2 (2006), 380—398.|accessdate=2018-01-21|archivedate=2018-01-22|archiveurl=https://web.archive.org/web/20180122075618/http://onlinelibrary.wiley.com/doi/10.1112/S0024610706022721/abstract;jsessionid=49C006BC1BE5C8063CF48EB4A3F70F31.f03t02|deadurl=no}}</ref> використали частковий випадок теореми при <math>{\mathbb F} = {\mathbb F}_p</math> для оцінки [[Полілінійні тригонометричні суми|полілінійних тригонометричних сум]]. Це, зокрема, дозволило отримати нетривіальні верхні оцінки для [[Сума Гаусса|сум Гаусса]] <math>\Bigg\vert{\sum \limits_{g \in G} {e^{2 \pi \frac{a g}{p} i}}}\Bigg\vert = \Bigg\vert{\sum \limits_{x=0}^{p-1} {e^{2 \pi \frac{a x^n}{p} i}}}\Bigg\vert</math> за малими [[Мультиплікативна група кільця лишків за модулем n|мультиплікативними]] [[підгрупа]]ми <math>G \subset {\mathbb F}_p^{*},\ |G|=\frac{p-1}{n}</math>{{Sfn|Гараев|2010|с=7—9}}. Бурген, Кац і [[Теренс Тао|Тао]], використовуючи цей самий випадок, посилили оцінку в [[Теорема Семереді — Троттера|проблемі Семереді&nbsp;— Троттера]] в <math>{{\mathbb F}}_p</math>, довівши, що для множини пар <math>I = \left\lbrace{(p,l) : p \in l, p \in P, l \in L}\right\rbrace</math> для множини <math>P</math> точок з <math>\left({{{\mathbb F}}_p}\right)^2</math> та прямих <math>L</math> при <math>|P|=|L|=n</math> виконується оцінка <math>|I| \le n^{\frac{3}{2}-\varepsilon}</math> при деякому <math>\varepsilon > 0</math><ref name = "Bourgain, Tao">K. N. Bourgain, J. and T. Tao. A Sum-Product Estimate in Finite Fields, and Applications.
GAFA, 14(1):27-57, 2004. [https://arxiv.org/abs/math/0301343 arXiv: math/0301343] {{Webarchive|url=https://web.archive.org/web/20180122074259/https://arxiv.org/abs/math/0301343 |date=2018-01-22 }}</ref>.

У цій самій праці вони застосували теорему для дослідження [[Задача про голку|множин Какеї]] в багатовимірному просторі <math>({\mathbb F}_p)^d</math>. Для розміру такої множини вони отримали оцінку <math>|S| > p^{\frac{d}{2}+1+10^{-10}}</math>.

== Межі можливого покращення гіпотези ==
У тій самій статті, де Ердеш та Семереді висунули гіпотезу про те, що <math>\max \left\lbrace{|A+A|,|A \times A|}\right\rbrace > c(\delta) |A|^{2 - \delta}</math> для <math>A \subset {\mathbb Z},\ \delta > 0</math>, вони навели й приклад побудови як завгодно великої множини <math>A</math>, для котрої <math>|A+A| + |A \times A| \le |A|^{2 - \frac{c}{\log \log |A|}}</math>. Такою множиною виступала множина чисел, одержуваних множенням не більше ніж <math>2 \left\lfloor{\frac{\log x}{6 \log \log x}}\right\rfloor</math> [[Просте число|простих чисел]] (не обов'язково різних), кожне з яких не перевищує <math>(\log x)^3</math>, де <math>x</math>&nbsp;— довільне достатньо велике число{{Sfn|Erdös, Szemerédi|1983}}.

== Узагальнення ==

=== Для комбінації операцій ===
[[Жан Бурген|Бурген]] і {{Не перекладено|Мей-Чу Чанг|Чанг|en|Mei-Chu Chang}} розглядали оцінки вигляду

: <math>\max \{ |\underbrace{A + \dots + A}_{k}|, |\underbrace{A \times \dots \times A}_{k}| \} \ge |A|^{b(k)}</math>

для довільного <math>k</math> і <math>b(k) \to \infty</math>{{Sfn|Bourgain, Chang|2004}}.

У багатьох працях додавання та множення [[Арифметична комбінаторика|поєднують в одному виразі]]: наприклад, отримують безумовні нижні оцінки для <math>|AA+AA|</math><ref>{{Sfn0|Rudnev, Stevens|2020}}, теорема 2</ref>.

=== Для набору пар доданків/множників ===
Одне з узагальнень гіпотези&nbsp;— питання про суми та добутки, відповідні ребрам довільного [[Граф (математика)|графа]] на елементах множини.{{Рамка}}
Нехай <math>G=(A, E)</math>&nbsp;— граф, <math>E \subset A \times A</math>, <math>|A|=n</math>. Позначимо <math>c</math> і <math>\delta</math> через рівності

* <math>|E| = n^{1+c}</math>

* <math>\max \{ |A +_G A|, |A \cdot_G A| \} = n^{1 + \delta}</math>, де <math>A +_G A := \{ a + b : (a, b) \in E \}</math>, <math>A \cdot_G A := \{ ab : (a, b) \in E \}</math>

Як залежать одне від одного значення <math>c</math> і <math>\delta</math> при <math>|A| \to \infty</math>?
{{/рамка}}На відміну від випадку <math>G = A \times A</math>, тут може не спостерігатися екстремального зростання ні сум, ані добутків: при <math>c < 1</math> можлива ситуація, коли <math>\delta < c</math><ref>{{Sfn0|Alon, Ruzsa, Solymosi|2020}}, теорема 3</ref>. Тому, крім нижніх, виявляється актуальним питання верхніх оцінок на <math>\max \{ |A+A|, |AA| \}</math>. Втім, нижні оцінки також досліджують<ref>{{Sfn0|Alon, Angel, Benjamini, Lubetzky|2012}}, наслідок 4</ref><ref>{{Sfn0|Shkredov, Solymosi|2020}}, теорема 3</ref>.

=== Для оцінки енергій ===
Нижні оцінки розміру множини сум легко виводити з верхніх оцінок на [[Адитивна енергія|адитивну енергію]], тому гіпотезу про перші природно узагальнити до гіпотези про другі, використовуючи аналогічне поняття [[Адитивна енергія|мультиплікативної енергії]].

Але у множині чисел цілком можуть бути більшими одночасно обидві енергії, оскільки нижня оцінка може керуватися внеском окремої підмножини. Наприклад, якщо <math>E^+(A_1) \gg |A|^3, E^{\times}(A_2) \gg |A|^3</math>, то для множини <math>A = A_1 \cup A_2</math> виконується співвідношення

: <math>\min \{ E^+(A), E^\times(A) \} \ge \min \{ E^+(A_1), E^\times(A_2) \} \gg |A|^3\ .</math>

Тому при формулюванні відповідної теореми про енергії використовується співвідношення енергій ''різних підмножин''.{{Рамка}}
'''Теорема Балога&nbsp;— Вулі'''

Існує стала <math>\delta > 0</math> така, що для будь-якої множини <math>A \subset {\mathbb R}</math> існує розбиття <math>A = B \sqcup C</math> з умовою

: <math>E^+(B) \le |A|^{3-\delta},\ E^\times(C) \le |A|^{3-\delta}</math>
{{/рамка}}Найкращий варіант цієї теореми доведено для <math>\delta = \frac{7}{26}-o(1)</math>{{Sfn|Shakan|2019}}. Відомо, що аналогічне хибне для <math>\delta > \frac{2}{3}</math><ref>{{Sfn0|Balog, Wooley|2017}}, теорема 1.2</ref>.

=== Для довільних опуклих функцій ===
Добуток двох чисел можна подати як функцію від суми їхніх логарифмів: <math>ab = \exp(\log a + \log b)</math>. Поелементне застосування строго висхідної функції до множини не змінює її розміру, тому

: <math>|AA| = |\exp(\log A + \log A)| = |\log A + \log A|</math>

і основну гіпотезу сум-добутків можна переформулювати як

: <math>\max \{ |A+A|, |\log A + \log A| \} \ge |A|^{2-o(1)}</math>

або (підставляючи <math>A:=\log A</math>) як

: <math>\max \{ |\exp(A)+\exp(A)|, |A + A| \} \ge |A|^{2-o(1)}\ .</math>

Виявляється, що схожі оцінки можна довести для довільної опуклої функції <math>\exp</math>.{{Рамка}}
'''Теорема'''<ref>{{sfn0|Li, Roche-Newton|2012}}, теореми 1.1, 1.2</ref>

Якщо <math>A \subset {\mathbb R}</math>&nbsp;— довільна множина, <math>f : {\mathbb R} \to {\mathbb R}</math>&nbsp;— довільна строго опукла функція, то

: <math>\max \{ |A-A|, |f(A) + f(A)| \} \ge |A|^{14/11-o(1)}</math>

: <math>\max \{ |A+A|, |f(A) + f(A)| \} \ge |A|^{24/19-o(1)}</math>
{{/рамка}}Питання про те, чи правильні такі ж оцінки з показником <math>2-o(1)</math> у правій частині залишається відкритим.

Аналогічні результати отримано і для більшої кількості доданків<ref>{{Sfn0|Hanson, Roche-Newton, Rudnev|2020}}, теорема 1.4</ref>.

== Література ==
* {{Стаття|author={{nobr|Гараев М. З.}}|title=Суммы и произведения множеств и оценки рациональных тригонометрических сумм в полях простого порядка,|url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=9367&option_lang=rus|language=ru|видання=[[Успехи математических наук]]|рік=2010|том=65|issue=4 (394)|pages=5—66|doi=10.4213/rm9367|ref=Гараев|publisher=[[Математичний інститут імені В. А. Стеклова РАН|Российская академия наук]]}}
* {{Стаття|author=P. Erdös, E. Szemerédi|title=On sums and products of integers|url=https://link.springer.com/chapter/10.1007%2F978-3-0348-5438-2_19|language=en|видання=Birkhäuser Verlag|рік=1983|pages=213–218|ref=Erdös, Szemerédi}}
* {{Стаття|author=M. Nathanson|title=On sums and products of integers|url=https://www.researchgate.net/publication/265459302_On_sums_and_products_of_integers|language=en|видання=Proceedings of the American Mathematical|рік=1997|том=125|issue=1|ref=Nathanson}}
* {{Стаття|author=K. Ford|title=Sums and Products from a Finite Set of Real Numbers|url=https://link.springer.com/article/10.1023/A:1009709908223|language=en|видання=The Ramanujan Journal|рік=1998|том=2|pages=59–66|ref=Ford}}
* {{Стаття|author=G. Elekes|title=On the number of sums and products|url=https://eudml.org/doc/207071|language=en|видання=Acta Arithmetica|рік=1997|том=81|issue=4|pages=365–367|ref=Elekes}}
* {{Стаття|author=J. Solymosi|title=Bounding multiplicative energy by the sumset|url=https://www.sciencedirect.com/science/article/pii/S0001870809001182|language=en|видання=Advances in Mathematics|рік=2009|том=222|issue=2|pages=402–408|arxiv=0806.1040v3|ref=Solymosi}}
* {{Стаття|author=S. V. Konyagin, I. D. Shkredov|title=On sum sets of sets having small product set|url=https://link.springer.com/article/10.1134/S0081543815060255|language=en|видання=Proceedings of the Steklov Institute of Mathematics|рік=2015|том=290|pages=288–299|arxiv=1503.05771|ref=Konyagin, Shkredov}}
* {{Стаття|author=S. V. Konyagin, I. D. Shkredov|title=New results on sum-products in <math>{\mathbb R}</math>|language=en|рік=2016|arxiv=1602.03473|ref=Konyagin, Shkredov}}
* {{Стаття|author=M. Rudnev, I. D. Shkredov, S. Stevens|title=On The Energy Variant of the Sum-Product Conjecture|url=https://www.ems-ph.org/journals/show_abstract.php?issn=0213-2230&vol=36&iss=1&rank=8|language=en|видання=Revista Matemática Iberoamericana|рік=2020|том=36|issue=1|pages=207–232|arxiv=1607.05053|ref=Rudnev, Shkredov, Stevens}}
* {{Стаття|author=G. Shakan|title=On higher energy decompositions and the sum–product phenomenon|url=https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridge-philosophical-society/article/on-higher-energy-decompositions-and-the-sumproduct-phenomenon/E11723932CF649F57A85AE75879539BC|language=en|видання=Mathematical Proceedings of the Cambridge Philosophical Society|рік=2019|том=167|issue=3|pages=599–617|arxiv=1803.04637|ref=Shakan}}
* {{Стаття|author=M. Rudnev, S. Stevens|title=An update on the sum-product problem|language=en|рік=2020|arxiv=2005.11145|ref=Rudnev, Stevens}}
* {{Стаття|author=G. Elekes, I. Z. Ruzsa|title=Few sums, many products|url=https://www.researchgate.net/publication/265330179_Few_sums_many_products|language=en|видання=Studia Scientiarum Mathematicarum Hungarica|рік=2003|том=40|issue=3|pages=301–308|ref=Elekes, Ruzsa}}
* {{Стаття|author=B. Murphy, M. Rudnev, I. Shkredov, Y. Shteinikov|title=On the few products, many sums problem|url=https://jtnb.centre-mersenne.org/item/JTNB_2019__31_3_573_0/|language=en|видання=Journal de Théorie des Nombres de Bordeaux|рік=2019|том=31|issue=3|pages=573–602|arxiv=1712.00410|ref=Murphy, Rudnev, Shkredov, Shteinikov}}
* {{Стаття|author=N. Alon, I. Ruzsa, J. Solymosi|title=Sums, products and ratios along the edges of a graph|url=http://mat.uab.es/pubmat/fitxers/download/FileType:pdf/FolderName:v64(1)/FileName:6412006.pdf|language=en|видання=Publicacions Matemàtiques|рік=2020|том=64|issue=1|pages=143–155|arxiv=1802.06405|ref=Alon, Ruzsa, Solymosi}}
* {{Стаття|author=N. Alon, O. Angel, I. Benjamini, E. Lubetzky|title=Sums and products along sparse graphs|url=https://nyuscholars.nyu.edu/en/publications/sums-and-products-along-sparse-graphs|language=en|видання=Israel Journal of Mathematics|рік=2012|том=188|issue=1|pages=353–384|arxiv=0905.0135|ref=Alon, Angel, Benjamini, Lubetzky}}
* {{Стаття|author=I. Shkredov, J. Solymosi|title=The Uniformity Conjecture in Additive Combinatorics|language=en|рік=2020|arxiv=2005.11559|ref=Shkredov, Solymosi}}
* {{Стаття|author=J. Solymosi|title=On the number of sums and products|url=https://londmathsoc.onlinelibrary.wiley.com/doi/10.1112/S0024609305004261|language=en|видання=Bulletin of the London Mathematical Society|рік=2005|том=37|issue=4|pages=491–494|ref=Solymosi}}
* {{Стаття|author=A. Balog, T. D. Wooley|title=A low-energy decomposition theorem|url=https://academic.oup.com/qjmath/article/68/1/207/2452952|language=en|видання=The Quarterly Journal of Mathematics|рік=2017|том=68|issue=1|pages=207–226|arxiv=1510.03309|ref=Balog, Wooley}}
* {{Стаття|author=B. Hanson, O. Roche-Newton, M. Rudnev|title=Higher convexity and iterated sum sets|language=en|рік=2020|arxiv=2005.00125|ref=Hanson, Roche-Newton, Rudnev}}
* {{Стаття|author=L. Li, O. Roche-Newton|title=Convexity and a sum-product type estimate|url=https://www.impan.pl/pl/wydawnictwa/czasopisma-i-serie-wydawnicze/acta-arithmetica/all/156/3/83486/convexity-and-a-sum-product-type-estimate|language=en|видання=Acta Arithmetica|рік=2012|том=156|pages=247–255|arxiv=1111.5159v1|ref=Li, Roche-Newton}}
* {{Стаття|author=J. Bourgain, M.-C. Chang|title=On the size of <math>k</math>-fold sum and product sets of integers|url=https://www.jstor.org/stable/20161203?seq=1#metadata_info_tab_contents|language=en|видання=Journal of the American Mathematical Society|рік=2004|том=17|issue=2|pages=473–497|arxiv=math/0309055|ref=Bourgain, Chang}}
* {{Стаття|author=К. И. Ольмезов, А. С. Семченков, И. Д. Шкредов|title=О популярных суммах и разностях для множеств с малым мультипликативным удвоением|url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=mzm&paperid=12638&option_lang=rus|language=ru|видання=Математические заметки|рік=2020|том=108|issue=4|pages=561–571|arxiv=1911.12005|ref=Olmezov, Semchankau, Shkredov}}

== Примітки ==
{{примітки|2}}

[[Категорія:Арифметична комбінаторика]]