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

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

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

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

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

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

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

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

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

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

Теорема Для деякої сталої $\delta =\delta ({\mathbb {F} })>0$ і довільної множини $A\subset {\mathbb {F} }$ (для скінченної ${\mathbb {F} }$ — з обмеженнями на розмір) виконується співвідношення $\max \left\lbrace {|A+A|,|A\times A|}\right\rbrace >|A|^{1+\delta }$

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

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

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

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

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

Приклади

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

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

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

Результати

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

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

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

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

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

Задачу сум-добутків у ${\mathbb {F} }_{p}$ розв'язано в працях Бургена, Гліббичука та Конягіна і Бургейна, Каца та Тао. Вони довели таку теорему:

Для будь-якого $\varepsilon >0$ існує $\delta =\delta (\varepsilon )>0$ таке, що якщо $A\subset {\mathbb {F} }_{p}$ і $|A|<p^{1-\varepsilon }$, то виконується оцінка $\max \left\lbrace {|A+A|,|A\times A|}\right\rbrace \geq |A|^{1+\delta }$

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

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

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

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

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

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

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

${\begin{cases}b_{1}+b_{3}=b_{2}+b_{4}\\b_{1}b_{5}=b_{2}b_{6}\,\end{cases}}$

де $b_{i}$ належать деяким (різним) підмножинам $A$, а на множину $A$ накладено особливі умови. Використовуючи таке твердження як лему, можна довести теорему і для довільної множини $A$.

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

Якщо всі елементи $a\in A$ мають багато подань у вигляді $a=p_{1}p_{2},\ p_{1}\in \Pi _{1},\ p_{2}\in \Pi _{2}$ для деяких невеликих множин $\Pi _{1}\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 \Pi _{1},\ p_{2}\in \Pi _{2},\ b\in B,\ c\in C\ .$

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

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

• аналіз рівняння $a+b=c,\ a\in A,b\in B,c\in C$ (тривіально, за допомогою розкладання $\Pi _{1}:=AA,\ \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{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}}$

де $(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|$.

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

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

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

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

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

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

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

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

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

Бурген і Чанг розглядали оцінки вигляду

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

для довільного $k$ і $b(k)\to \infty$.

У багатьох працях додавання та множення поєднують в одному виразі: наприклад, отримують безумовні нижні оцінки для $|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 \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)\}\geq \min\{E^{+}(A_{1}),E^{\times }(A_{2})\}\gg |A|^{3}\ .$

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

Теорема Балога — Вулі Існує стала $\delta >0$ така, що для будь-якої множини $A\subset {\mathbb {R} }$ існує розбиття $A=B\sqcup C$ з умовою $E^{+}(B)\leq |A|^{3-\delta },\ E^{\times }(C)\leq |A|^{3-\delta }$

Найкращий варіант цієї теореми доведено для $\delta ={\frac {7}{26}}-o(1)$. Відомо, що аналогічне хибне для $\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|\}\geq |A|^{2-o(1)}$

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

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

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

Теорема Якщо $A\subset {\mathbb {R} }$ — довільна множина, $f:{\mathbb {R} }\to {\mathbb {R} }$ — довільна строго опукла функція, то $\max\{|A-A|,|f(A)+f(A)|\}\geq |A|^{14/11-o(1)}$ $\max\{|A+A|,|f(A)+f(A)|\}\geq |A|^{24/19-o(1)}$

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

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

Література

• Гараев М. З.. Суммы и произведения множеств и оценки рациональных тригонометрических сумм в полях простого порядка, // Успехи математических наук. — Российская академия наук, 2010. — Т. 65, вып. 4 (394). — С. 5—66. — DOI:10.4213/rm9367.
• P. Erdös, E. Szemerédi. On sums and products of integers // Birkhäuser Verlag. — 1983. — P. 213–218.
• M. Nathanson. On sums and products of integers // Proceedings of the American Mathematical. — 1997. — Vol. 125, iss. 1.
• K. Ford. Sums and Products from a Finite Set of Real Numbers // The Ramanujan Journal. — 1998. — Vol. 2. — P. 59–66.
• G. Elekes. On the number of sums and products // Acta Arithmetica. — 1997. — Vol. 81, iss. 4. — P. 365–367.
• J. Solymosi. Bounding multiplicative energy by the sumset // Advances in Mathematics. — 2009. — Vol. 222, iss. 2. — P. 402–408. — arXiv:0806.1040v3.
• S. V. Konyagin, I. D. Shkredov. On sum sets of sets having small product set // Proceedings of the Steklov Institute of Mathematics. — 2015. — Vol. 290. — P. 288–299. — arXiv:1503.05771.
• S. V. Konyagin, I. D. Shkredov. New results on sum-products in ${\mathbb {R} }$. — 2016. — arXiv:1602.03473.
• M. Rudnev, I. D. Shkredov, S. Stevens. On The Energy Variant of the Sum-Product Conjecture // Revista Matemática Iberoamericana. — 2020. — Vol. 36, iss. 1. — P. 207–232. — arXiv:1607.05053.
• G. Shakan. On higher energy decompositions and the sum–product phenomenon // Mathematical Proceedings of the Cambridge Philosophical Society. — 2019. — Vol. 167, iss. 3. — P. 599–617. — arXiv:1803.04637.
• M. Rudnev, S. Stevens. An update on the sum-product problem. — 2020. — arXiv:2005.11145.
• G. Elekes, I. Z. Ruzsa. Few sums, many products // Studia Scientiarum Mathematicarum Hungarica. — 2003. — Vol. 40, iss. 3. — P. 301–308.
• B. Murphy, M. Rudnev, I. Shkredov, Y. Shteinikov. On the few products, many sums problem // Journal de Théorie des Nombres de Bordeaux. — 2019. — Vol. 31, iss. 3. — P. 573–602. — arXiv:1712.00410.
• N. Alon, I. Ruzsa, J. Solymosi. Sums, products and ratios along the edges of a graph // Publicacions Matemàtiques. — 2020. — Vol. 64, iss. 1. — P. 143–155. — arXiv:1802.06405.
• N. Alon, O. Angel, I. Benjamini, E. Lubetzky. Sums and products along sparse graphs // Israel Journal of Mathematics. — 2012. — Vol. 188, iss. 1. — P. 353–384. — arXiv:0905.0135.
• I. Shkredov, J. Solymosi. The Uniformity Conjecture in Additive Combinatorics. — 2020. — arXiv:2005.11559.
• J. Solymosi. On the number of sums and products // Bulletin of the London Mathematical Society. — 2005. — Vol. 37, iss. 4. — P. 491–494.
• A. Balog, T. D. Wooley. A low-energy decomposition theorem // The Quarterly Journal of Mathematics. — 2017. — Vol. 68, iss. 1. — P. 207–226. — arXiv:1510.03309.
• B. Hanson, O. Roche-Newton, M. Rudnev. Higher convexity and iterated sum sets. — 2020. — arXiv:2005.00125.
• L. Li, O. Roche-Newton. Convexity and a sum-product type estimate // Acta Arithmetica. — 2012. — Vol. 156. — P. 247–255. — arXiv:1111.5159v1.
• J. Bourgain, M.-C. Chang. On the size of $k$-fold sum and product sets of integers // Journal of the American Mathematical Society. — 2004. — Vol. 17, iss. 2. — P. 473–497. — arXiv:math/0309055.
• К. И. Ольмезов, А. С. Семченков, И. Д. Шкредов. О популярных суммах и разностях для множеств с малым мультипликативным удвоением // Математические заметки. — 2020. — Т. 108, вып. 4. — С. 561–571. — arXiv:1911.12005.