Теорема сум-добутків — теорема арифметичної комбінаторики, що встановлює неструктурованість будь-якої досить великої множини відносно хоча б однієї з операцій поля (додавання та множення). Як показник структурованості використовують, відповідно, розміри множини сум і множини добутків.
Формулювання
Нехай — підмножина деякого кільця (зазвичай є полем, але формально можна розглядати і кільце) з операціями і . Розглянемо дві похідні від множини:
Якщо множина структурована відносно додавання (наприклад, у ній багато арифметичних прогресій, або узагальнених арифметичних прогресій, або їх великих шматків), то множина буде відносно невеликою — адже суми багатьох пар елементів збіжаться.
Якщо ж структурована відносно множення, то, з аналогічної причини, не дуже великою буде множина .
Теорема стверджує, що хоча б одна з множин і дуже велика відносно , тобто відносно хоча б однієї з операцій структура буде нерегулярною.
Конкретніше, теорема встановлює степеневе зростання розміру більшої з похідних множин відносно розміру початкової:
Теорема Для деякої сталої і довільної множини (для скінченної — з обмеженнями на розмір) виконується співвідношення |
Для різних кілець удається отримати оцінки з різними . Також для деяких (особливо для скінченних) кілець можливе додавання умов на розмір множини , за яких виконується теорема для даної .
Останні випадки
Найзручнішими для вивчення виявляються крайні випадки гіпотези:
- мало сум, багато добутків: якщо , то
- мало добутків, багато сум: якщо , то
Приклади
Класичними прикладами, що ілюструють теорему сум-добутків, є арифметична прогресія та геометрична прогресія .
Арифметична прогресія максимально впорядкована відносно додавання, так що , Однак із її чисел можна скласти багато різних добутків, так що , тому відносно множення вона зовсім невпорядкована.
Так само для геометричної прогресії виконується але очевидно (якщо розглянути двійкове подання чисел), що .
Результати
Для дійсних чисел
При теорему сум-добутків іноді називають також теоремою Ердеша — Семереді, оскільки саме вони 1983 року підняли питання розгляду співвідношення кількостей сум і добутків. У тій самій праці вони висунули гіпотезу про те, що величина може бути як завгодно близькою до одиниці (тобто ). Однак там само вони висунули ще кілька гіпотез, зокрема, аналогічну для доданків та множин: .
Хронологія покращення в оцінці | ||
---|---|---|
Рік | Значення | Автор(и) |
1983 | (*)(**) | Ердеш, Семереді замість |
1998 | (*)(**) | [en] |
1997 | (**) | [en] |
2005 | [en] | |
2009 | Шоймоші | |
2015 | [ru], [ru] | |
2016 | Конягін, Шкредов | |
2016 | Руднєв, Шкредов, Стівенс | |
2019 | Шакан | |
2020 (препринт) | Руднєв, Стівенс | |
(*) Тільки для (**) Правильно і для степеня замість |
Для полів лишків за простим модулем
Теренс Тао у своїй монографії зазначає, що задачу про отримання аналога результату Ердеша та Семереді в полях поставив 1999 року Т. Вольф (у приватній бесіді) для підмножин потужності порядку .
Задачу сум-добутків у розв'язано в працях Бургена, Гліббичука та і Бургейна, Каца та Тао. Вони довели таку теорему:
Для будь-якого існує таке, що якщо і , то виконується оцінка |
Вимога вумові теоремиє природниою т скільки, якщо має порядок близький до , то обидві величини і будуть пзапорядкуомблизькіимидо .
Для довільних кілець
Теренс Тао досліджував межі можливостей узагальнення теореми на довільні кільця та, зокрема, зв'язок екстремальних випадків малих значень і з кількістю дільників нуля у множині та близькістю її структури до підкільця.
Методи доведення
Для дійсних чисел
Перші доведення
У доведенні Ердеша та Семереді використано той факт, що за малих і існує розв'язок системи
де належать деяким (різним) підмножинам , а на множину накладено особливі умови. Використовуючи таке твердження як лему, можна довести теорему і для довільної множини .
Теорема Семереді — Троттера (Елекеш, 1997)
Якщо всі елементи мають багато подань у вигляді для деяких невеликих множин , то для оцінки числа розв'язків рівняння
з будь-якими множинами можна використовувати рівняння
З іншого боку, розв'язки такого рівняння відповідають інциденціям між прямими, які параметризуються парами , і точками, які параметризуються парами . Тому для їх оцінки виявляється зручно використовувати загальні результати про інциденції, найкращий із яких — теорема Семереді — Троттера.
Саме це використав Елекеш для доведення теореми з показником . Неявно його доведення можна поділити на два етапи:
- аналіз рівняння (тривіально, за допомогою розкладання )
- застосування отриманих оцінок (тривіально, для )
Така декомпозиція важлива для осмислення методів, що виникли пізніше.
Побудова Шоймоші (Шоймоші, 2009)
Шоймоші використав той факт, що якщо , то
З цього випливає, що якщо , то
Разом з тим, за фіксованих значень усі пари , що утворюються поданнями
будуть різними, тому, підсумувавши їх за «сусідніми» парами , можна отримати оцінку на в термінах числа таких подань. А воно, у свою чергу, виражається (опосередковано) через .
Найнаочніше цю ідею можна виразити геометрично, як підсумовування точок з , які лежать на сусідніх прямих, що виходять із початку координат.
Розбиття побудови Шоймоші (Конягін, Шкредов, 2015)
Якщо в побудові Шоймоші прибрати умову про те, що підсумовуювані очки, повинні належати сусіднім прямим, то вже ніщо не буде гарантувати, що всі отримувані суми будуть різними. Наприклад, узагалі всі суми точок із можуть бути різними лише в екстремальному випадку , а він уже задовольняє гіпотезу сум-добутків.
Виходячи з цього, Конягін та Шкредов оцінили мінімальну кількість збігів таких сум у проміжному випадку (коли і дорівнюють нижній оцінці, тобто ). Щоб оцінити кількість збігів, вони розбили всі прямі на блоки з однакового числа таких, що йдуть підряд, і оцінювали кількість збігів у кожному блоці для більшості з них. Використовуючи ці оцінки, вони отримали результат із .
Нетривіальний мультиплікативний розклад (Руднєв, Стівенс, 2020)
Збіги двох сум точок, які розглядали Конягін і Шкредов, означають наявність розв'язку системи рівнянь
де і всі та пари різні. Редукуючи систему за методом Гаусса (за одну дію), можна отримати рівняння
зі сталими і тими ж умовами на . Руднєв і Стівенс застосували це для явної побудови мультиплікативного розкладу великої підмножини зі кращими властивостями, ніж у тривіального.
За аналогією з , це дозволяє розділити доведення оцінок із показником на два етапи:
- застосування нового мультиплікативного розкладання;
- нетривіальне застосування рівняння для оцінки .
Використання старших енергій
Найпопулярніший шлях використання рівнянь для оцінення — використання адитивної енергії та її узагальнень. Результати застосування теореми Семереді — Троттера дозволяють найкраще аналізувати рівняння вигляду
для довільного . Руднєв і Стівенс запропонували метод використання такої адитивної енергії за допомогою розгляду рівняння
де відповідає множині популярних (із багатьма поданнями) різниць, а належить множині популярних сум. Крім задачі сум-добутків, розробка подібних методів є актуальною для оцінення сум .
Існує схожий операторний метод, який менш ефективний для оцінення , але дозволяє краще вивчати зв'язок між і .
Для простих полів
Під час доведення теореми для широко використовують поняття адитивної енергії, нерівність Плюннеке — Ружі та оцінки Балога — Семереді — Гауерса. Одне з можливих доведень використовує нижню оцінку розміру множини і той факт, що з верхніх оцінок розмірів і випливає верхня оцінка розміру , що суперечить нижній.
Застосування
Бурген, Глібичук і використали частковий випадок теореми при для оцінки . Це, зокрема, дозволило отримати нетривіальні верхні оцінки для сум Гаусса за малими мультиплікативними підгрупами . Бурген, Кац і Тао, використовуючи цей самий випадок, посилили оцінку в проблемі Семереді — Троттера в , довівши, що для множини пар для множини точок з та прямих при виконується оцінка при деякому .
У цій самій праці вони застосували теорему для дослідження множин Какеї в багатовимірному просторі . Для розміру такої множини вони отримали оцінку .
Межі можливого покращення гіпотези
У тій самій статті, де Ердеш та Семереді висунули гіпотезу про те, що для , вони навели й приклад побудови як завгодно великої множини , для котрої . Такою множиною виступала множина чисел, одержуваних множенням не більше ніж простих чисел (не обов'язково різних), кожне з яких не перевищує , де — довільне достатньо велике число.
Узагальнення
Для комбінації операцій
Бурген і [en] розглядали оцінки вигляду
для довільного і .
У багатьох працях додавання та множення поєднують в одному виразі: наприклад, отримують безумовні нижні оцінки для .
Для набору пар доданків/множників
Одне з узагальнень гіпотези — питання про суми та добутки, відповідні ребрам довільного графа на елементах множини.
Нехай — граф, , . Позначимо і через рівності
Як залежать одне від одного значення і при ? |
На відміну від випадку , тут може не спостерігатися екстремального зростання ні сум, ані добутків: при можлива ситуація, коли . Тому, крім нижніх, виявляється актуальним питання верхніх оцінок на . Втім, нижні оцінки також досліджують.
Для оцінки енергій
Нижні оцінки розміру множини сум легко виводити з верхніх оцінок на адитивну енергію, тому гіпотезу про перші природно узагальнити до гіпотези про другі, використовуючи аналогічне поняття мультиплікативної енергії.
Але у множині чисел цілком можуть бути більшими одночасно обидві енергії, оскільки нижня оцінка може керуватися внеском окремої підмножини. Наприклад, якщо , то для множини виконується співвідношення
Тому при формулюванні відповідної теореми про енергії використовується співвідношення енергій різних підмножин.
Теорема Балога — Вулі Існує стала така, що для будь-якої множини існує розбиття з умовою |
Найкращий варіант цієї теореми доведено для . Відомо, що аналогічне хибне для .
Для довільних опуклих функцій
Добуток двох чисел можна подати як функцію від суми їхніх логарифмів: . Поелементне застосування строго висхідної функції до множини не змінює її розміру, тому
і основну гіпотезу сум-добутків можна переформулювати як
або (підставляючи ) як
Виявляється, що схожі оцінки можна довести для довільної опуклої функції .
Теорема Якщо — довільна множина, — довільна строго опукла функція, то |
Питання про те, чи правильні такі ж оцінки з показником у правій частині залишається відкритим.
Аналогічні результати отримано і для більшої кількості доданків.
Література
- Гараев М. З.. Суммы и произведения множеств и оценки рациональных тригонометрических сумм в полях простого порядка, // Успехи математических наук. — Российская академия наук, 2010. — Т. 65, вып. 4 (394). — С. 5—66. — DOI: .
- 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 . — 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 -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.
Примітки
- Розв'язано в Elekes, Ruzsa, 2003
- У Murphy, Rudnev, Shkredov, Shteinikov, 2019 отримано кращі результати, ніж у загальному випадку
- Источник. оригіналу за 22 січня 2018. Процитовано 21 січня 2018.
- У першій праці Erdös, Szemerédi, 1983 не уточнювалося значення , а лише доводилось існування. Тим не менш, пряме слідування міркуванням тої праці показує, що вона істинна для . У явному вигляді це значення згадано пізніше в Nathanson, 1997
- Ford, 1998.
- Elekes, 1997.
- Solymosi, 2005.
- Solymosi, 2009.
- Konyagin, Shkredov, 2015.
- Konyagin, Shkredov, 2016.
- Rudnev, Shkredov, Stevens, 2020.
- Shakan, 2019.
- Rudnev, Stevens, 2020.
- Гараев, 2010, с. 1—2.
- Tao, Terence (2009), The sum-product phenomenon in arbitrary rings, Contributions to Discrete Mathematics, 4 (2): 59—82, arXiv:0806.2497, MR 2592424, hdl:10515/sy5r78637.
- Erdös, Szemerédi, 1983.
- Див. Rudnev, Stevens, 2020, лема 3
- Подібно до цього розклад можна використати для аналізу . Див. Rudnev, Stevens, 2020, лема 4.
- Див. Solymosi, 2009, формула (2).
- Див. Konyagin, Shkredov, 2015, доведення леми 10
- Див. Rudnev, Stevens, 2020, с. 10 (після речення 1)
- Якщо застосовувати ці оцінки тривіально, так само, як і в Елекеша, то результатом буде
- Див. Rudnev, Stevens, 2020, теорема 5, особливо формулу (25)
- Див. Olmezov, Semchankau, Shkredov, 2020, теорема 2
- Гараев, 2010, с. 14—25.
- Mini course of additive combinatorics [ 2017-08-29 у Wayback Machine.], замітки за лекціями Принстонського університету
- 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. оригіналу за 22 січня 2018. Процитовано 21 січня 2018.
- Гараев, 2010, с. 7—9.
- K. N. Bourgain, J. and T. Tao. A Sum-Product Estimate in Finite Fields, and Applications. GAFA, 14(1):27-57, 2004. arXiv: math/0301343 [ 2018-01-22 у Wayback Machine.]
- Bourgain, Chang, 2004.
- Rudnev, Stevens, 2020, теорема 2
- Alon, Ruzsa, Solymosi, 2020, теорема 3
- Alon, Angel, Benjamini, Lubetzky, 2012, наслідок 4
- Shkredov, Solymosi, 2020, теорема 3
- Balog, Wooley, 2017, теорема 1.2
- Li, Roche-Newton, 2012, теореми 1.1, 1.2
- Hanson, Roche-Newton, Rudnev, 2020, теорема 1.4
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Teorema sum dobutkiv teorema arifmetichnoyi kombinatoriki sho vstanovlyuye nestrukturovanist bud yakoyi dosit velikoyi mnozhini vidnosno hocha b odniyeyi z operacij polya dodavannya ta mnozhennya Yak pokaznik strukturovanosti vikoristovuyut vidpovidno rozmiri mnozhini sum i mnozhini dobutkiv FormulyuvannyaNehaj A F displaystyle A subset mathbb F pidmnozhina deyakogo kilcya F displaystyle mathbb F zazvichaj F displaystyle mathbb F ye polem ale formalno mozhna rozglyadati i kilce z operaciyami displaystyle i displaystyle cdot Rozglyanemo dvi pohidni vid A displaystyle A mnozhini A A a 1 a 2 a 1 a 2 A displaystyle A A left lbrace a 1 a 2 a 1 a 2 in A right rbrace A A a 1 a 2 a 1 a 2 A displaystyle A times A left lbrace a 1 cdot a 2 a 1 a 2 in A right rbrace Yaksho mnozhina A displaystyle A strukturovana vidnosno dodavannya napriklad u nij bagato arifmetichnih progresij abo uzagalnenih arifmetichnih progresij abo yih velikih shmatkiv to mnozhina A A displaystyle A A bude vidnosno nevelikoyu adzhe sumi bagatoh par elementiv zbizhatsya Yaksho zh A displaystyle A strukturovana vidnosno mnozhennya to z analogichnoyi prichini ne duzhe velikoyu bude mnozhina A A displaystyle A times A Teorema stverdzhuye sho hocha b odna z mnozhin A A displaystyle A A i A A displaystyle A times A duzhe velika vidnosno A displaystyle A tobto vidnosno hocha b odniyeyi z operacij struktura bude neregulyarnoyu Konkretnishe teorema vstanovlyuye stepeneve zrostannya rozmiru bilshoyi z pohidnih mnozhin vidnosno rozmiru pochatkovoyi Teorema Dlya deyakoyi staloyi d d F gt 0 displaystyle delta delta mathbb F gt 0 i dovilnoyi mnozhini A F displaystyle A subset mathbb F dlya skinchennoyi F displaystyle mathbb F z obmezhennyami na rozmir vikonuyetsya spivvidnoshennya max A A A A gt A 1 d displaystyle max left lbrace A A A times A right rbrace gt A 1 delta Dlya riznih kilec udayetsya otrimati ocinki z riznimi d displaystyle delta Takozh dlya deyakih osoblivo dlya skinchennih kilec mozhlive dodavannya umov na rozmir mnozhini A displaystyle A za yakih vikonuyetsya teorema dlya danoyi d displaystyle delta Ostanni vipadki Najzruchnishimi dlya vivchennya viyavlyayutsya krajni vipadki gipotezi malo sum bagato dobutkiv yaksho A A A displaystyle A A ll A to A A A 2 o 1 displaystyle AA geq A 2 o 1 malo dobutkiv bagato sum yaksho A A A displaystyle AA ll A to A A A 2 o 1 displaystyle A A geq A 2 o 1 PrikladiKlasichnimi prikladami sho ilyustruyut teoremu sum dobutkiv ye arifmetichna progresiya A 1 n displaystyle A left lbrace 1 dots n right rbrace ta geometrichna progresiya B 1 2 4 2 n 1 displaystyle B left lbrace 1 2 4 dots 2 n 1 right rbrace Arifmetichna progresiya maksimalno vporyadkovana vidnosno dodavannya tak sho A A lt 2 A displaystyle A A lt 2 A Odnak iz yiyi chisel mozhna sklasti bagato riznih dobutkiv tak sho A A W A 2 log A displaystyle A times A Omega left frac A 2 log A right tomu vidnosno mnozhennya vona zovsim nevporyadkovana Tak samo dlya geometrichnoyi progresiyi vikonuyetsya B B lt 2 B displaystyle B times B lt 2 B ale ochevidno yaksho rozglyanuti dvijkove podannya chisel sho B B W B 2 displaystyle B B Omega B 2 RezultatiDlya dijsnih chisel Pri F R displaystyle mathbb F mathbb R teoremu sum dobutkiv inodi nazivayut takozh teoremoyu Erdesha Semeredi oskilki same voni 1983 roku pidnyali pitannya rozglyadu spivvidnoshennya kilkostej sum i dobutkiv U tij samij praci voni visunuli gipotezu pro te sho velichina e displaystyle varepsilon mozhe buti yak zavgodno blizkoyu do odinici tobto max A A A A gt A 2 o 1 displaystyle max left lbrace A A A times A right rbrace gt A 2 o 1 Odnak tam samo voni visunuli she kilka gipotez zokrema analogichnu dlya k displaystyle k dodankiv ta mnozhin max A A A A gt A k o 1 displaystyle max left lbrace A dots A A times dots times A right rbrace gt A k o 1 Hronologiya pokrashennya d displaystyle delta v ocinci max A A A A A 1 d o 1 A R displaystyle max A A AA geq A 1 delta o 1 A subset mathbb R Rik Znachennya d displaystyle delta Avtor i 1983 1 31 displaystyle 1 31 Erdesh Semeredi 1 d displaystyle 1 delta zamist 1 d o 1 displaystyle 1 delta o 1 1998 1 15 displaystyle 1 15 en 1997 1 4 displaystyle 1 4 en 2005 3 11 displaystyle 3 11 en 2009 1 3 displaystyle 1 3 Shojmoshi 2015 1 3 1 20598 0 333381 displaystyle frac 1 3 frac 1 20598 approx 0 333381 ru ru 2016 1 3 5 9813 0 333842 displaystyle frac 1 3 frac 5 9813 approx 0 333842 Konyagin Shkredov 2016 1 3 1 1509 0 333996 displaystyle frac 1 3 frac 1 1509 approx 0 333996 Rudnyev Shkredov Stivens 2019 1 3 5 5277 0 334280 displaystyle frac 1 3 frac 5 5277 approx 0 334280 Shakan 2020 preprint 1 3 2 1167 0 335047 displaystyle frac 1 3 frac 2 1167 approx 0 335047 Rudnyev Stivens Tilki dlya A Z displaystyle A subset mathbb Z Pravilno i dlya stepenya 1 d displaystyle 1 delta zamist 1 d o 1 displaystyle 1 delta o 1 Dlya poliv lishkiv za prostim modulem Terens Tao u svoyij monografiyi zaznachaye sho zadachu pro otrimannya analoga rezultatu Erdesha ta Semeredi v polyah F p displaystyle mathbb F p postaviv 1999 roku T Volf u privatnij besidi dlya pidmnozhin A F p displaystyle A subset mathbb F p potuzhnosti poryadku p 1 2 displaystyle p 1 2 Zadachu sum dobutkiv u F p displaystyle mathbb F p rozv yazano v pracyah Burgena Glibbichuka ta i Burgejna Kaca ta Tao Voni doveli taku teoremu Dlya bud yakogo e gt 0 displaystyle varepsilon gt 0 isnuye d d e gt 0 displaystyle delta delta varepsilon gt 0 take sho yaksho A F p displaystyle A subset mathbb F p i A lt p 1 e displaystyle A lt p 1 varepsilon to vikonuyetsya ocinka max A A A A A 1 d displaystyle max left lbrace A A A times A right rbrace geq A 1 delta Vimoga A lt p 1 e displaystyle A lt p 1 varepsilon vumovi teoremiye prirodnioyu t skilki yaksho A displaystyle A maye poryadok blizkij do p displaystyle p to obidvi velichini A A displaystyle A A i A A displaystyle A times A budut pzaporyadkuomblizkiimido A displaystyle A Dlya dovilnih kilec Terens Tao doslidzhuvav mezhi mozhlivostej uzagalnennya teoremi na dovilni kilcya ta zokrema zv yazok ekstremalnih vipadkiv malih znachen A A displaystyle A A i A A displaystyle A cdot A z kilkistyu dilnikiv nulya u mnozhini A displaystyle A ta blizkistyu yiyi strukturi do pidkilcya Metodi dovedennyaDlya dijsnih chisel Pershi dovedennya U dovedenni Erdesha ta Semeredi vikoristano toj fakt sho za malih A A displaystyle A A i A A displaystyle A times A isnuye rozv yazok sistemi b 1 b 3 b 2 b 4 b 1 b 5 b 2 b 6 displaystyle begin cases b 1 b 3 b 2 b 4 b 1 b 5 b 2 b 6 end cases de b i displaystyle b i nalezhat deyakim riznim pidmnozhinam A displaystyle A a na mnozhinu A displaystyle A nakladeno osoblivi umovi Vikoristovuyuchi take tverdzhennya yak lemu mozhna dovesti teoremu i dlya dovilnoyi mnozhini A displaystyle A Teorema Semeredi Trottera Elekesh 1997 Yaksho vsi elementi a A displaystyle a in A mayut bagato podan u viglyadi a p 1 p 2 p 1 P 1 p 2 P 2 displaystyle a p 1 p 2 p 1 in Pi 1 p 2 in Pi 2 dlya deyakih nevelikih mnozhin P 1 P 2 displaystyle Pi 1 Pi 2 to dlya ocinki chisla rozv yazkiv rivnyannya a b c a A b B c C displaystyle a b c a in A b in B c in C z bud yakimi mnozhinami B C displaystyle B C mozhna vikoristovuvati rivnyannya p 1 p 2 b c p 1 P 1 p 2 P 2 b B c C displaystyle p 1 p 2 b c p 1 in Pi 1 p 2 in Pi 2 b in B c in C Z inshogo boku rozv yazki takogo rivnyannya vidpovidayut incidenciyam mizh pryamimi yaki parametrizuyutsya parami p 1 b displaystyle p 1 b i tochkami yaki parametrizuyutsya parami p 2 c displaystyle p 2 c Tomu dlya yih ocinki viyavlyayetsya zruchno vikoristovuvati zagalni rezultati pro incidenciyi najkrashij iz yakih teorema Semeredi Trottera Same ce vikoristav Elekesh dlya dovedennya teoremi z pokaznikom d 1 4 displaystyle delta frac 1 4 Neyavno jogo dovedennya mozhna podiliti na dva etapi analiz rivnyannya a b c a A b B c C displaystyle a b c a in A b in B c in C trivialno za dopomogoyu rozkladannya P 1 A A P 2 1 A displaystyle Pi 1 AA Pi 2 1 A zastosuvannya otrimanih ocinok trivialno dlya B A C A A displaystyle B A C A A Taka dekompoziciya vazhliva dlya osmislennya metodiv sho vinikli piznishe Pobudova Shojmoshi Shojmoshi 2009 Pobudova Shojmoshi Chervoni tochki mayut koordinati z A A displaystyle A times A Zeleni tochki vidpovidayut sumam chervonih iz susidnih pryamih Usi voni garantovano rizni ta nalezhat A A A A displaystyle A A times A A Kilkist linij iz chervonimi tochkami virazhayetsya cherez A A displaystyle AA Shojmoshi vikoristav toj fakt sho yaksho a b lt c d displaystyle frac a b lt frac c d to a b lt a c b d lt c d displaystyle frac a b lt frac a c b d lt frac c d Z cogo viplivaye sho yaksho a 1 b 1 lt a 2 b 2 lt a 3 b 3 displaystyle frac a 1 b 1 lt frac a 2 b 2 lt frac a 3 b 3 to a 1 a 2 b 1 b 2 lt a 2 a 3 b 2 b 3 displaystyle frac a 1 a 2 b 1 b 2 lt frac a 2 a 3 b 2 b 3 Razom z tim za fiksovanih znachen l A A m A A displaystyle lambda in A A mu in A A usi pari a c b d displaystyle a c b d sho utvoryuyutsya podannyami l a b m c d a b c d A displaystyle lambda frac a b mu frac c d a b c d in A budut riznimi tomu pidsumuvavshi yih za susidnimi parami l m displaystyle lambda mu mozhna otrimati ocinku na A A displaystyle A A v terminah chisla takih podan A vono u svoyu chergu virazhayetsya oposeredkovano cherez A A displaystyle AA Najnaochnishe cyu ideyu mozhna viraziti geometrichno yak pidsumovuvannya tochok z A A displaystyle A times A yaki lezhat na susidnih pryamih sho vihodyat iz pochatku koordinat Rozbittya pobudovi Shojmoshi Konyagin Shkredov 2015 Rozbittya pobudovi Shojmoshi za metodom Konyagina Shkredova Kolori linij sho vihodyat iz pochatku koordinat vidpovidayut blokam u kozhnomu z yakih ocinyuyetsya kilkist zbigiv sum Sini ta fioletovi liniyi poznachayut pidsumovuvani pari chervonih tochok iz odnakovimi sumami Yaksho v pobudovi Shojmoshi pribrati umovu pro te sho pidsumovuyuvani ochki povinni nalezhati susidnim pryamim to vzhe nisho ne bude garantuvati sho vsi otrimuvani sumi budut riznimi Napriklad uzagali vsi sumi tochok iz A A displaystyle A times A mozhut buti riznimi lishe v ekstremalnomu vipadku A A A 2 displaystyle A A gg A 2 a vin uzhe zadovolnyaye gipotezu sum dobutkiv Vihodyachi z cogo Konyagin ta Shkredov ocinili minimalnu kilkist zbigiv takih sum u promizhnomu vipadku koli A A displaystyle A A i A A displaystyle AA dorivnyuyut nizhnij ocinci tobto A 4 3 displaystyle A 4 3 Shob ociniti kilkist zbigiv voni rozbili vsi pryami na bloki z odnakovogo chisla takih sho jdut pidryad i ocinyuvali kilkist zbigiv u kozhnomu bloci dlya bilshosti z nih Vikoristovuyuchi ci ocinki voni otrimali rezultat iz d gt 1 3 displaystyle delta gt frac 1 3 Netrivialnij multiplikativnij rozklad Rudnyev Stivens 2020 Zbigi dvoh sum tochok yaki rozglyadali Konyagin i Shkredov oznachayut nayavnist rozv yazku sistemi rivnyan l 1 a 1 l 2 a 2 l 3 a 3 l 4 a 4 a 1 a 2 a 3 a 4 displaystyle 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 de a i l i a i A A displaystyle a i lambda i a i in A times A i vsi l i displaystyle lambda i ta pari l 1 l 2 l 3 l 4 displaystyle lambda 1 lambda 2 lambda 3 lambda 4 rizni Redukuyuchi sistemu za metodom Gaussa za odnu diyu mozhna otrimati rivnyannya a 3 c 1 a 1 c 2 a 2 displaystyle a 3 c 1 a 1 c 2 a 2 zi stalimi c 1 c 2 displaystyle c 1 c 2 i timi zh umovami na a 1 a 2 displaystyle a 1 a 2 Rudnyev i Stivens zastosuvali ce dlya yavnoyi pobudovi multiplikativnogo rozkladu velikoyi pidmnozhini A displaystyle A zi krashimi vlastivostyami nizh u trivialnogo Za analogiyeyu z ce dozvolyaye rozdiliti dovedennya ocinok iz pokaznikom d 1 3 c displaystyle delta frac 1 3 c na dva etapi zastosuvannya novogo multiplikativnogo rozkladannya netrivialne zastosuvannya rivnyannya a b c displaystyle a b c dlya ocinki A A displaystyle A A Vikoristannya starshih energij Najpopulyarnishij shlyah vikoristannya rivnyan dlya ocinennya A A displaystyle A A vikoristannya aditivnoyi energiyi ta yiyi uzagalnen Rezultati zastosuvannya teoremi Semeredi Trottera dozvolyayut najkrashe analizuvati rivnyannya viglyadu E 3 A D a 1 a 2 a 3 d 1 d 2 d 3 A 3 D 3 a 1 d 1 a 2 d 2 a 3 d 3 displaystyle 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 dlya dovilnogo D displaystyle D Rudnyev i Stivens zaproponuvali metod vikoristannya takoyi aditivnoyi energiyi za dopomogoyu rozglyadu rivnyannya d a b a c a b c A d D displaystyle d a b a c a b c in A d in D de D displaystyle D vidpovidaye mnozhini populyarnih iz bagatma podannyami riznic a a b displaystyle a b nalezhit mnozhini populyarnih sum Krim zadachi sum dobutkiv rozrobka podibnih metodiv ye aktualnoyu dlya ocinennya sum Isnuye shozhij operatornij metod yakij mensh efektivnij dlya ocinennya A A displaystyle A A ale dozvolyaye krashe vivchati zv yazok mizh E A displaystyle E A i A A displaystyle AA Dlya prostih poliv Pid chas dovedennya teoremi dlya F F p displaystyle mathbb F mathbb F p shiroko vikoristovuyut ponyattya aditivnoyi energiyi nerivnist Plyunneke Ruzhi ta ocinki Baloga Semeredi Gauersa Odne z mozhlivih doveden vikoristovuye nizhnyu ocinku rozmiru mnozhini R A A A A A A A A A displaystyle R A A left frac A times A A times A A A A right i toj fakt sho z verhnih ocinok rozmiriv A A displaystyle A A i A A displaystyle A times A viplivaye verhnya ocinka rozmiru R A displaystyle R A sho superechit nizhnij ZastosuvannyaBurgen Glibichuk i vikoristali chastkovij vipadok teoremi pri F F p displaystyle mathbb F mathbb F p dlya ocinki Ce zokrema dozvolilo otrimati netrivialni verhni ocinki dlya sum Gaussa g G e 2 p a g p i x 0 p 1 e 2 p a x n p i displaystyle 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 za malimi multiplikativnimi pidgrupami G F p G p 1 n displaystyle G subset mathbb F p G frac p 1 n Burgen Kac i Tao vikoristovuyuchi cej samij vipadok posilili ocinku v problemi Semeredi Trottera v F p displaystyle mathbb F p dovivshi sho dlya mnozhini par I p l p l p P l L displaystyle I left lbrace p l p in l p in P l in L right rbrace dlya mnozhini P displaystyle P tochok z F p 2 displaystyle left mathbb F p right 2 ta pryamih L displaystyle L pri P L n displaystyle P L n vikonuyetsya ocinka I n 3 2 e displaystyle I leq n frac 3 2 varepsilon pri deyakomu e gt 0 displaystyle varepsilon gt 0 U cij samij praci voni zastosuvali teoremu dlya doslidzhennya mnozhin Kakeyi v bagatovimirnomu prostori F p d displaystyle mathbb F p d Dlya rozmiru takoyi mnozhini voni otrimali ocinku S gt p d 2 1 10 10 displaystyle S gt p frac d 2 1 10 10 Mezhi mozhlivogo pokrashennya gipoteziU tij samij statti de Erdesh ta Semeredi visunuli gipotezu pro te sho max A A A A gt c d A 2 d displaystyle max left lbrace A A A times A right rbrace gt c delta A 2 delta dlya A Z d gt 0 displaystyle A subset mathbb Z delta gt 0 voni naveli j priklad pobudovi yak zavgodno velikoyi mnozhini A displaystyle A dlya kotroyi A A A A A 2 c log log A displaystyle A A A times A leq A 2 frac c log log A Takoyu mnozhinoyu vistupala mnozhina chisel oderzhuvanih mnozhennyam ne bilshe nizh 2 log x 6 log log x displaystyle 2 left lfloor frac log x 6 log log x right rfloor prostih chisel ne obov yazkovo riznih kozhne z yakih ne perevishuye log x 3 displaystyle log x 3 de x displaystyle x dovilne dostatno velike chislo UzagalnennyaDlya kombinaciyi operacij Burgen i en rozglyadali ocinki viglyadu max A A k A A k A b k displaystyle max underbrace A dots A k underbrace A times dots times A k geq A b k dlya dovilnogo k displaystyle k i b k displaystyle b k to infty U bagatoh pracyah dodavannya ta mnozhennya poyednuyut v odnomu virazi napriklad otrimuyut bezumovni nizhni ocinki dlya A A A A displaystyle AA AA Dlya naboru par dodankiv mnozhnikiv Odne z uzagalnen gipotezi pitannya pro sumi ta dobutki vidpovidni rebram dovilnogo grafa na elementah mnozhini Nehaj G A E displaystyle G A E graf E A A displaystyle E subset A times A A n displaystyle A n Poznachimo c displaystyle c i d displaystyle delta cherez rivnosti E n 1 c displaystyle E n 1 c max A G A A G A n 1 d displaystyle max A G A A cdot G A n 1 delta de A G A a b a b E displaystyle A G A a b a b in E A G A a b a b E displaystyle A cdot G A ab a b in E Yak zalezhat odne vid odnogo znachennya c displaystyle c i d displaystyle delta pri A displaystyle A to infty Na vidminu vid vipadku G A A displaystyle G A times A tut mozhe ne sposterigatisya ekstremalnogo zrostannya ni sum ani dobutkiv pri c lt 1 displaystyle c lt 1 mozhliva situaciya koli d lt c displaystyle delta lt c Tomu krim nizhnih viyavlyayetsya aktualnim pitannya verhnih ocinok na max A A A A displaystyle max A A AA Vtim nizhni ocinki takozh doslidzhuyut Dlya ocinki energij Nizhni ocinki rozmiru mnozhini sum legko vivoditi z verhnih ocinok na aditivnu energiyu tomu gipotezu pro pershi prirodno uzagalniti do gipotezi pro drugi vikoristovuyuchi analogichne ponyattya multiplikativnoyi energiyi Ale u mnozhini chisel cilkom mozhut buti bilshimi odnochasno obidvi energiyi oskilki nizhnya ocinka mozhe keruvatisya vneskom okremoyi pidmnozhini Napriklad yaksho E A 1 A 3 E A 2 A 3 displaystyle E A 1 gg A 3 E times A 2 gg A 3 to dlya mnozhini A A 1 A 2 displaystyle A A 1 cup A 2 vikonuyetsya spivvidnoshennya min E A E A min E A 1 E A 2 A 3 displaystyle min E A E times A geq min E A 1 E times A 2 gg A 3 Tomu pri formulyuvanni vidpovidnoyi teoremi pro energiyi vikoristovuyetsya spivvidnoshennya energij riznih pidmnozhin Teorema Baloga Vuli Isnuye stala d gt 0 displaystyle delta gt 0 taka sho dlya bud yakoyi mnozhini A R displaystyle A subset mathbb R isnuye rozbittya A B C displaystyle A B sqcup C z umovoyu E B A 3 d E C A 3 d displaystyle E B leq A 3 delta E times C leq A 3 delta Najkrashij variant ciyeyi teoremi dovedeno dlya d 7 26 o 1 displaystyle delta frac 7 26 o 1 Vidomo sho analogichne hibne dlya d gt 2 3 displaystyle delta gt frac 2 3 Dlya dovilnih opuklih funkcij Dobutok dvoh chisel mozhna podati yak funkciyu vid sumi yihnih logarifmiv a b exp log a log b displaystyle ab exp log a log b Poelementne zastosuvannya strogo vishidnoyi funkciyi do mnozhini ne zminyuye yiyi rozmiru tomu A A exp log A log A log A log A displaystyle AA exp log A log A log A log A i osnovnu gipotezu sum dobutkiv mozhna pereformulyuvati yak max A A log A log A A 2 o 1 displaystyle max A A log A log A geq A 2 o 1 abo pidstavlyayuchi A log A displaystyle A log A yak max exp A exp A A A A 2 o 1 displaystyle max exp A exp A A A geq A 2 o 1 Viyavlyayetsya sho shozhi ocinki mozhna dovesti dlya dovilnoyi opukloyi funkciyi exp displaystyle exp Teorema Yaksho A R displaystyle A subset mathbb R dovilna mnozhina f R R displaystyle f mathbb R to mathbb R dovilna strogo opukla funkciya to max A A f A f A A 14 11 o 1 displaystyle max A A f A f A geq A 14 11 o 1 max A A f A f A A 24 19 o 1 displaystyle max A A f A f A geq A 24 19 o 1 Pitannya pro te chi pravilni taki zh ocinki z pokaznikom 2 o 1 displaystyle 2 o 1 u pravij chastini zalishayetsya vidkritim Analogichni rezultati otrimano i dlya bilshoyi kilkosti dodankiv LiteraturaGaraev M Z 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 P Erdos E Szemeredi On sums and products of integers Birkhauser 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 R displaystyle mathbb R 2016 arXiv 1602 03473 M Rudnev I D Shkredov S Stevens On The Energy Variant of the Sum Product Conjecture Revista Matematica 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 Theorie 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 Matematiques 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 displaystyle 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 K I Olmezov A S Semchenkov I D Shkredov O populyarnyh summah i raznostyah dlya mnozhestv s malym multiplikativnym udvoeniem Matematicheskie zametki 2020 T 108 vyp 4 S 561 571 arXiv 1911 12005 PrimitkiRozv yazano v Elekes Ruzsa 2003 U Murphy Rudnev Shkredov Shteinikov 2019 otrimano krashi rezultati nizh u zagalnomu vipadku Istochnik originalu za 22 sichnya 2018 Procitovano 21 sichnya 2018 U pershij praci Erdos Szemeredi 1983 ne utochnyuvalosya znachennya d displaystyle delta a lishe dovodilos isnuvannya Tim ne mensh pryame sliduvannya mirkuvannyam toyi praci pokazuye sho vona istinna dlya d 1 31 displaystyle delta 1 31 U yavnomu viglyadi ce znachennya zgadano piznishe v Nathanson 1997 Ford 1998 Elekes 1997 Solymosi 2005 Solymosi 2009 Konyagin Shkredov 2015 Konyagin Shkredov 2016 Rudnev Shkredov Stevens 2020 Shakan 2019 Rudnev Stevens 2020 Garaev 2010 s 1 2 Tao Terence 2009 The sum product phenomenon in arbitrary rings Contributions to Discrete Mathematics 4 2 59 82 arXiv 0806 2497 MR 2592424 hdl 10515 sy5r78637 Erdos Szemeredi 1983 Div Rudnev Stevens 2020 lema 3 Podibno do cogo rozklad a p 1 p 2 p 1 P 1 p 2 P 2 displaystyle a p 1 p 2 p 1 in Pi 1 p 2 in Pi 2 mozhna vikoristati dlya analizu E A displaystyle E times A Div Rudnev Stevens 2020 lema 4 Div Solymosi 2009 formula 2 Div Konyagin Shkredov 2015 dovedennya lemi 10 Div Rudnev Stevens 2020 s 10 pislya rechennya 1 Yaksho zastosovuvati ci ocinki trivialno tak samo yak i v Elekesha to rezultatom bude d 1 3 displaystyle delta frac 1 3 Div Rudnev Stevens 2020 teorema 5 osoblivo formulu 25 Div Olmezov Semchankau Shkredov 2020 teorema 2 Garaev 2010 s 14 25 Mini course of additive combinatorics 2017 08 29 u Wayback Machine zamitki za lekciyami Prinstonskogo universitetu 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 originalu za 22 sichnya 2018 Procitovano 21 sichnya 2018 Garaev 2010 s 7 9 K N Bourgain J and T Tao A Sum Product Estimate in Finite Fields and Applications GAFA 14 1 27 57 2004 arXiv math 0301343 2018 01 22 u Wayback Machine Bourgain Chang 2004 Rudnev Stevens 2020 teorema 2 Alon Ruzsa Solymosi 2020 teorema 3 Alon Angel Benjamini Lubetzky 2012 naslidok 4 Shkredov Solymosi 2020 teorema 3 Balog Wooley 2017 teorema 1 2 Li Roche Newton 2012 teoremi 1 1 1 2 Hanson Roche Newton Rudnev 2020 teorema 1 4