Теорема сум-добутків

Теорема сум-добутків — теорема арифметичної комбінаторики, що встановлює неструктурованість будь-якої досить великої множини відносно хоча б однієї з операцій поля (додавання та множення). Як показник структурованості використовують, відповідно, розміри множини сум і множини добутків.

Формулювання

Нехай $A\subset 𝔽$ — підмножина деякого кільця $𝔽$ (зазвичай $𝔽$ є полем, але формально можна розглядати і кільце) з операціями $+$ і $\cdot$. Розглянемо дві похідні від $A$ множини:

$A+A=\left\{a_1+a_2:a_1,a_2\in A\right\}$

$A\times A=\left\{a_1\cdot a_2:a_1,a_2\in A\right\}$

Якщо множина $A$ структурована відносно додавання (наприклад, у ній багато арифметичних прогресій, або узагальнених арифметичних прогресій, або їх великих шматків), то множина $A+A$ буде відносно невеликою — адже суми багатьох пар елементів збіжаться.

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

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

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

Для деякої сталої $\delta =\delta (𝔽)>0$ і довільної множини $A\subset 𝔽$ (для скінченної $𝔽$ — з обмеженнями на розмір) виконується співвідношення

$\max \left\{|A+A|,|A\times A|\right\}>|A{|}^{1+\delta }$

Шаблон:/рамкаДля різних кілець удається отримати оцінки з різними $\delta$. Також для деяких (особливо для скінченних) кілець можливе додавання умов на розмір множини $A$, за яких виконується теорема для даної $\delta$.

Останні випадки

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

• мало сум, багато добутків: якщо $|A+A|\ll |A|$, то $|AA|\ge |A{|}^{2-o(1)}$

• мало добутків, багато сум: якщо $|AA|\ll |A|$, то $|A+A|\ge |A{|}^{2-o(1)}$

Приклади

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

Арифметична прогресія максимально впорядкована відносно додавання, так що $|A+A|<2|A|$, Однак із її чисел можна скласти багато різних добутків, так що $|A\times A|=\mathrm{\Omega }\left(\frac{|A{|}^2}{\log |A|}\right)$, тому відносно множення вона зовсім невпорядкована.

Так само для геометричної прогресії виконується $|B\times B|<2|B|$ але очевидно (якщо розглянути двійкове подання чисел), що $|B+B|=\mathrm{\Omega }(|B{|}^2)$.

Результати

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

При $𝔽=ℝ$ теорему сум-добутків іноді називають також теоремою Ердеша — Семереді, оскільки саме вони 1983 року підняли питання розгляду співвідношення кількостей сум і добутків. У тій самій праці вони висунули гіпотезу про те, що величина $\epsilon$ може бути як завгодно близькою до одиниці (тобто $\max \left\{|A+A|,|A\times A|\right\}>|A{|}^{2-o(1)}$). Однак там само вони висунули ще кілька гіпотез, зокрема, аналогічну для $k$ доданків та множин: $\max \left\{|A+\dots +A|,|A\times \dots \times A|\right\}>|A{|}^{k-o(1)}$.

Хронологія покращення $\delta$ в оцінці $\max \{|A+A|,|AA|\}\ge |A{|}^{1+\delta -o(1)},A\subset ℝ$
Рік	Значення $\delta$	Автор(и)
1983	$1/31$ (*)(**)	Ердеш, Семереді $1+\delta$ замість $1+\delta -o(1)$
1998	$1/15$ (*)(**)	Шаблон:Не перекладено Шаблон:Sfn
1997	$1/4$ (**)	Шаблон:Не перекладено Шаблон:Sfn
2005	$3/11$	Шаблон:Не перекладено Шаблон:Sfn
2009	$1/3$	Шоймоші Шаблон:Sfn
2015	$\frac{1}{3}+\frac{1}{20598}\approx 0.333381...$	Шаблон:Нп, Шаблон:НпШаблон:Sfn
2016	$\frac{1}{3}+\frac{5}{9813}\approx 0.333842...$	Конягін, Шкредов Шаблон:Sfn
2016	$\frac{1}{3}+\frac{1}{1509}\approx 0.333996...$	Руднєв, Шкредов, СтівенсШаблон:Sfn
2019	$\frac{1}{3}+\frac{5}{5277}\approx 0.334280...$	Шакан Шаблон:Sfn
2020 (препринт)	$\frac{1}{3}+\frac{2}{1167}\approx 0.335047...$	Руднєв, Стівенс Шаблон:Sfn
(*) Тільки для $A\subset \mathbb{Z}$ (**) Правильно і для степеня $1+\delta$ замість $1+\delta -o(1)$

Для полів лишків за простим модулем

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

Задачу сум-добутків у ${𝔽}_p$ розв'язано в працях Бургена, Гліббичука та Конягіна і Бургейна, Каца та Тао. Вони довели таку теорему:Шаблон:Рамка Для будь-якого $\epsilon >0$ існує $\delta =\delta (\epsilon )>0$ таке, що якщо $A\subset {𝔽}_p$ і $|A|<p^{1-\epsilon }$, то виконується оцінка

$\max \left\{|A+A|,|A\times A|\right\}\ge |A{|}^{1+\delta }$

Шаблон:/рамкаВимога $|A|<p^{1-\epsilon }$ вумові теоремиє природниою т скільки, якщо $|A|$ має порядок близький до $p$, то обидві величини $|A+A|$ і $|A\times A|$ будуть пзапорядкуомблизькіимидо $|A|$Шаблон:Sfn.

Для довільних кілець

Теренс Тао досліджував межі можливостей узагальнення теореми на довільні кільця та, зокрема, зв'язок екстремальних випадків малих значень $|A+A|$ і $|A\cdot A|$ з кількістю дільників нуля у множині $A$ та близькістю її структури до підкільця.

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

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

Перші доведення

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

$\{\begin{array}{c}{b}_1+b_3=b_2+b_4\\ b_1{b}_5=b_2{b}_6\end{array}$

де $b_i$ належать деяким (різним) підмножинам $A$, а на множину $A$ накладено особливі умови. Використовуючи таке твердження як лему, можна довести теорему і для довільної множини $A$Шаблон:Sfn.

Теорема Семереді — Троттера (Елекеш, 1997)

Якщо всі елементи $a\in A$ мають багато подань у вигляді $a=p_1{p}_2,p_1\in {\mathrm{\Pi }}_1,p_2\in {\mathrm{\Pi }}_2$ для деяких невеликих множин ${\mathrm{\Pi }}_1{\mathrm{\Pi }}_2$, то для оцінки числа розв'язків рівняння

$a+b=c,a\in A,b\in B,c\in C.$

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

$p_1{p}_2+b=c,p_1\in {\mathrm{\Pi }}_1,p_2\in {\mathrm{\Pi }}_2,b\in B,c\in C.$

З іншого боку, розв'язки такого рівняння відповідають інциденціям між прямими, які параметризуються парами $(p_1,b)$, і точками, які параметризуються парами $(p_2,c)$. Тому для їх оцінки виявляється зручно використовувати загальні результати про інциденції, найкращий із яких — теорема Семереді — Троттера.

Саме це використав Елекеш для доведення теореми з показником $\delta =\frac{1}{4}$Шаблон:Sfn. Неявно його доведення можна поділити на два етапи:

• аналіз рівняння $a+b=c,a\in A,b\in B,c\in C$ (тривіально, за допомогою розкладання ${\mathrm{\Pi }}_1:=AA,{\mathrm{\Pi }}_2:=1/A$)

• застосування отриманих оцінок (тривіально, для $B:=A,C:=A+A$)

Така декомпозиція важлива для осмислення методів, що виникли пізніше.

Побудова Шоймоші (Шоймоші, 2009)

Побудова Шоймоші. Червоні точки мають координати з $A\times A$.
Зелені точки відповідають сумам червоних із сусідніх прямих. Усі вони гарантовано різні та належать $(A+A)\times (A+A)$.
Кількість ліній із червоними точками виражається через $|AA|$

Шоймоші використав той факт, що якщо $\frac{a}{b}<\frac{c}{d}$, то

$\frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d}.$

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

$\frac{a_1+a_2}{b_1+b_2}<\frac{a_2+a_3}{b_2+b_3}.$

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

$\lambda =\frac{a}{b},\mu =\frac{c}{d},a,b,c,d\in A$

будуть різними, тому, підсумувавши їх за «сусідніми» парами $(\lambda ,\mu )$, можна отримати оцінку на $|A+A|$ в термінах числа таких подань. А воно, у свою чергу, виражається (опосередковано) через $|AA|$.

Найнаочніше цю ідею можна виразити геометрично, як підсумовування точок з $A\times A$, які лежать на сусідніх прямих, що виходять із початку координат.

Розбиття побудови Шоймоші (Конягін, Шкредов, 2015)

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

Якщо в побудові Шоймоші прибрати умову про те, що підсумовуювані очки, повинні належати сусіднім прямим, то вже ніщо не буде гарантувати, що всі отримувані суми будуть різними. Наприклад, узагалі всі суми точок із $A\times A$ можуть бути різними лише в екстремальному випадку $|A+A|\gg |A{|}^2$, а він уже задовольняє гіпотезу сум-добутків.

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

Нетривіальний мультиплікативний розклад (Руднєв, Стівенс, 2020)

Збіги двох сум точок, які розглядали Конягін і Шкредов, означають наявність розв'язку системи рівнянь

$\{\begin{array}{c}{\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{array}$

де $(a_i,{\lambda }_i{a}_i)\in A\times A$ і всі ${\lambda }_i$ та пари $({\lambda }_1,{\lambda }_2),({\lambda }_3,{\lambda }_4)$ різні. Редукуючи систему за методом Гаусса (за одну дію), можна отримати рівняння

$a_3=c_1{a}_1-c_2{a}_2$

зі сталими $c_1,c_2$ і тими ж умовами на $a_1,a_2$. Руднєв і Стівенс застосували це для явної побудови мультиплікативного розкладу великої підмножини $A$ зі кращими властивостями, ніж у тривіального.

За аналогією з доведенням Елекеша, це дозволяє розділити доведення оцінок із показником $\delta =\frac{1}{3}+c$ на два етапи:

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

• нетривіальне застосування рівняння $a-b=c$ для оцінки $|A+A|$ .

Використання старших енергій

Найпопулярніший шлях використання рівнянь для оцінення $|A+A|$ — використання адитивної енергії та її узагальнень. Результати застосування теореми Семереді — Троттера дозволяють найкраще аналізувати рівняння вигляду

$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\}$

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

$d=(a+b)-(a+c)a,b,c\in A,d\in D,$

де $D$ відповідає множині популярних (із багатьма поданнями) різниць, а $a+b$ належить множині популярних сум. Крім задачі сум-добутків, розробка подібних методів є актуальною для оцінення сум опуклих послідовностей.

Існує схожий операторний метод, який менш ефективний для оцінення $|A+A|$, але дозволяє краще вивчати зв'язок між $E(A)$ і $|AA|$.

Для простих полів

Під час доведення теореми для $𝔽={𝔽}_p$ широко використовують поняття адитивної енергії, нерівність Плюннеке — Ружі та оцінки Балога — Семереді — Гауерса. Одне з можливих доведень використовує нижню оцінку розміру множини $R(A)=A\left(\frac{A\times A-A\times A}{A-A}+A\right)$ і той факт, що з верхніх оцінок розмірів $A+A$ і $A\times A$ випливає верхня оцінка розміру $R(A)$, що суперечить нижнійШаблон:Sfn.

Застосування

Бурген, Глібичук і Конягін використали частковий випадок теореми при $𝔽={𝔽}_p$ для оцінки полілінійних тригонометричних сум. Це, зокрема, дозволило отримати нетривіальні верхні оцінки для сум Гаусса $\left|\sum _{g\in G}{e}^{2\pi \frac{ag}{p}i}\right|=\left|\sum _{x=0}^{p-1}{e}^{2\pi \frac{a{x}^n}{p}i}\right|$ за малими мультиплікативними підгрупами $G\subset {𝔽}_p^{*},|G|=\frac{p-1}{n}$Шаблон:Sfn. Бурген, Кац і Тао, використовуючи цей самий випадок, посилили оцінку в проблемі Семереді — Троттера в ${𝔽}_p$, довівши, що для множини пар $I=\left\{(p,l):p\in l,p\in P,l\in L\right\}$ для множини $P$ точок з ${\left({𝔽}_p\right)}^2$ та прямих $L$ при $|P|=|L|=n$ виконується оцінка $|I|\le n^{\frac{3}{2}-\epsilon }$ при деякому $\epsilon >0$.

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

Межі можливого покращення гіпотези

У тій самій статті, де Ердеш та Семереді висунули гіпотезу про те, що $\max \left\{|A+A|,|A\times A|\right\}>c(\delta )|A{|}^{2-\delta }$ для $A\subset \mathbb{Z},\delta >0$, вони навели й приклад побудови як завгодно великої множини $A$, для котрої $|A+A|+|A\times A|\le |A{|}^{2-\frac{c}{\log \log |A|}}$. Такою множиною виступала множина чисел, одержуваних множенням не більше ніж $2\lfloor \frac{\log x}{6\log \log x}\rfloor$ простих чисел (не обов'язково різних), кожне з яких не перевищує $(\log x{)}^3$, де $x$ — довільне достатньо велике числоШаблон:Sfn.

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

Для комбінації операцій

Бурген і Шаблон:Не перекладено розглядали оцінки вигляду

$\max \{|\underset{k}{\underbrace{A+\dots +A}}|,|\underset{k}{\underbrace{A\times \dots \times A}}|\}\ge |A{|}^{b(k)}$

для довільного $k$ і $b(k)\to \mathrm{\infty }$Шаблон:Sfn.

У багатьох працях додавання та множення поєднують в одному виразі: наприклад, отримують безумовні нижні оцінки для $|AA+AA|$.

Для набору пар доданків/множників

Одне з узагальнень гіпотези — питання про суми та добутки, відповідні ребрам довільного графа на елементах множини.Шаблон:Рамка Нехай $G=(A,E)$ — граф, $E\subset A\times A$, $|A|=n$. Позначимо $c$ і $\delta$ через рівності

• $|E|=n^{1+c}$

• $\max \{|A{+}_{G}A|,|A{\cdot }_{G}A|\}=n^{1+\delta }$, де $A{+}_{G}A:=\{a+b:(a,b)\in E\}$, $A{\cdot }_{G}A:=\{ab:(a,b)\in E\}$

Як залежать одне від одного значення $c$ і $\delta$ при $|A|\to \mathrm{\infty }$? Шаблон:/рамкаНа відміну від випадку $G=A\times A$, тут може не спостерігатися екстремального зростання ні сум, ані добутків: при $c<1$ можлива ситуація, коли $\delta <c$. Тому, крім нижніх, виявляється актуальним питання верхніх оцінок на $\max \{|A+A|,|AA|\}$. Втім, нижні оцінки також досліджують.

Для оцінки енергій

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

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

$\min \{E^{+}(A),E^{\times }(A)\}\ge \min \{E^{+}(A_1),E^{\times }(A_2)\}\gg |A{|}^3.$

Тому при формулюванні відповідної теореми про енергії використовується співвідношення енергій різних підмножин.Шаблон:Рамка Теорема Балога — Вулі

Існує стала $\delta >0$ така, що для будь-якої множини $A\subset ℝ$ існує розбиття $A=B\bigsqcup C$ з умовою

$E^{+}(B)\le |A{|}^{3-\delta },E^{\times }(C)\le |A{|}^{3-\delta }$

Шаблон:/рамкаНайкращий варіант цієї теореми доведено для $\delta =\frac{7}{26}-o(1)$Шаблон:Sfn. Відомо, що аналогічне хибне для $\delta >\frac{2}{3}$.

Для довільних опуклих функцій

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

$|AA|=|\exp (\log A+\log A)|=|\log A+\log A|$

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

$\max \{|A+A|,|\log A+\log A|\}\ge |A{|}^{2-o(1)}$

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

$\max \{|\exp (A)+\exp (A)|,|A+A|\}\ge |A{|}^{2-o(1)}.$

Виявляється, що схожі оцінки можна довести для довільної опуклої функції $\exp$.Шаблон:Рамка Теорема

Якщо $A\subset ℝ$ — довільна множина, $f:ℝ\to ℝ$ — довільна строго опукла функція, то

$\max \{|A-A|,|f(A)+f(A)|\}\ge |A{|}^{14/11-o(1)}$

$\max \{|A+A|,|f(A)+f(A)|\}\ge |A{|}^{24/19-o(1)}$

Шаблон:/рамкаПитання про те, чи правильні такі ж оцінки з показником $2-o(1)$ у правій частині залишається відкритим.

Аналогічні результати отримано і для більшої кількості доданків.

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття