Теорема Рота — результат адитивної комбінаторики, окремий випадок теореми Семереді для прогресій довжини 3; стверджує наявність арифметичних прогресій у будь-якій достатньо щільній множині.
Точне формулювання: для будь-якого будь-яка множина , що має асимптотичну щільність містить арифметичну прогресію довжини 3.
Аналогічні формулювання, що використовують верхню та нижню асимптотичну щільність, еквівалентні.
Також еквівалентне початковому і формулювання для скінченних множин: для будь-якої існує таке, що якщо , і , то містить арифметичну прогресію довжини 3. У переважній більшості доведень доводиться саме формулювання для скінченних множин.
Історія покращення кількісних оцінок Розмір максимальної підмножини без прогресій довжини 3 Рік публікації Розмір (з точністю до константи) Автор(и) 1953 Рот 1987 1999 Бурген 2008 Бурген 2012 2011 Сандерс 2014 Блум 2020 (препринт) 2020 (препринт) Блум, Сісаск
Різні доведення
Елементарне (через узагальнені арифметичні прогресії) Теорему вперше довів 1953 року Клаус Рот , адаптувавши круговий методу Гарді — Літтлвуда. У доведенні використано ідеюПостнаука, Илья Шкредов — Теорема Семереди, згодом узагальнену і для загального доведення теореми Семереді: всі множини заданої щільності розбиваються на дві групи — «рівномірні» та «нерівномірні», причому під «рівномірністю» розуміється верхня оцінка на . Якщо множина рівномірна, то наявність прогресій у ній можна довести безпосередньо, а інакше можна довести наявність підпрогресії, в якій щільність множини більша, ніж серед відрізка натурального ряду, якому вона належить.
Метод дозволяє вивести оцінку . Технічні подробиці доведення, межа коефіцієнтів Фур'є, що визначає «рівномірність», і отримувані сталі можуть відрізнятися в різних джерелах.
Комбінаторне (через лему Семереді) Доведення теореми Рота можна вивестиЛаборатория Чебышёва, курс лекций «Аддитивная комбинаторика», лекция 3 як окремий випадок теореми Семереді з доведення Семереді. Такий спосіб доведення вимагає використання леми регулярності Семереді та теореми про кутики, звідки теорема Рота випливає безпосередньо. Можна навіть обійтися без використання теореми про кутики, а виводити теорему Рота безпосередньо з леми про видалення трикутників але тільки у формулюванні для скінченних циклічних груп (див. розділ «Варіації та узагальнення на різні групи»).
Оскільки лема регулярності Семереді дає надзвичайно великі верхні оцінки на отримувану через неї величину (як мінімум, вежі з експонент), то й сам метод не дозволяє отримати оцінки кращі від цих.
Гармонічний аналіз Рональд Грем у своїй книзі про теорію Ремзі наводить спрощений варіант доведення, також заснований на методі Семереді, проте не використовує леми регулярності. У доведенні використовуються узагальнені арифметичні прогресії вигляду , довести наявність яких у множині значно простіше, а з цього вже виводиться сама теорема Рота.
Доведення Грема не дає оцінок на , лише показує існування, оскільки використовує існування точки в послідовності, починаючи з якої всі точки досить близькі до границі, але для границі також доведено лише існування, а характер збіжності в принципі не аналізується.
Контрприклади для нещільних множин Поряд із знаходженням верхніх оцінок розміру множини без арифметичних прогресій, існує також обернена задача — побудова якомога більшої множини , що не містить арифметичних прогресій, тобто контрприкладу для позначення меж покращення оцінок на . Усі відомі побудови таких множин ґрунтуються на ідеї розгляду окремих розрядів чисел у деякій системі числення та задання умов на значення цих розрядів.
Ердеш, Туран (1936) Перший приклад множини без прогресій навели 1936 року Ердеш і Туран, запропонувавши розглянути числа, які в трійковій системі містять тільки цифри 0 і 2. Така множина містить лише чисел, що дуже мало, порівняно з верхніми оцінками.
Салем, Спенсер (1942) Салем і Спенсер 1942 року узагальнили ідею Ердеша та Турана на системи числення зі зростанням (залежно від розміру множини) основи та отримали множину без прогресій розміру .
Беренд (1946) 1946 року додав геометричну інтерпретацію, зіставивши розрядам числа координати точок у багатовимірному просторі і розглядаючи числа, відповідні в цьому сенсі точкам сфери. Це дозволило побудувати множину розміру , що не містить прогресій.
Згодом невеликим уточненням методу оцінку Беренда збільшено на логарифмічний множник, але суттєво кращих результатів станом на 2019 рік немає.
Оскільки для деяких узагальнень теореми Рота відомі верхні оцінки схожого типуT. Schoen, I. D. Shkredov, «Roth's theorem in many variables», Israel Journal of Mathematics, volume 199, pages 287—308 (2014) (arXiv:1106.1601 )T. Schoen, O. Sisask, «Roth's theorem for four variables and additive structures in sums of sparse sets», Forum of Mathematics Forum of Mathematics, Sigma, 4, E5. doi:10.1017/fms.2016.2 (arXiv:1408.2568 ), є підстави вважати, що оцінка Беренда точна.
Варіації та узагальнення для різних груп
Для скінченних циклічних груп І доведення через гармонічний аналіз, і певний спосіб застосування леми Семереді доводять не саму теорему, а її «циклічний» варіант. Для будь-якого існує таке, що якщо , і , то містить трійку , де під додаванням розуміють саме додавання за модулем. Обіцяні цим формулюванням прогресії можуть бути прогресіями в , але не бути такими в (наприклад, ). Однак теорема Рота очевидно випливає з нього якщо розглянути множину як множину лишків у . Це лише на сталу змінює щільність, але робить усі прогресії придатними для . Отже, ця теорема еквівалентна основній теоремі Рота.
Для груп з малим фіксованим скрутом Наступна теорема, подібна до теореми Рота, не випливає з неї і не тягне її, але цікава для окремого вивчення. Нехай зафіксовано деяке . Тоді для будь-якого існує таке , що якщо , то
Верхні оцінки Вперше теорему для груп довели 1982 року Браун і Бахлер, проте вони тільки довели, що для множин без арифметичних прогресій виконується , але точніші обмеження на залишалися відкритим питанням.
1993 року (опубліковано 1995 року) Рой Мешулам (Roy Meshulam) довівR. Meshulam, On subsets of finite abelian groups with no 3-term arithmetic progressions, Journal of Combinatorial Theory, Series A 71 (1995), no. 1, 168—172., що . У його доведенні розглянуто довільні групи та їхні характери. Існують також спрощеніA mini course on additive combinatorics , p. 39-42 варіанти цього доведення виключно для , які, використовуючи коефіцієнти Фур'є в , прямо узагальнюють ідеї з аналітичного доведення теореми Рота. Доведення виходить технічно навіть простішим, ніж доведення самої теореми Рота, так що частоЛаборатория Чебышёва, Илья Шкредов, Аналитические методы в аддитивной комбинаторике, обзорная лекция наводиться як перший приклад застосування методу.
2012 року Бейтман і Кац, розглядаючи випадок , довели існування та абсолютної сталої , такий, що для без арифметичних прогресій виконується .
2016 року Крут, Лев та Пах довели для випадку , що для множин без прогресії. Елленберг (Ellenberg) і Гейсвейт (Gijswijt), узагальнюючи метод Крута, Льова і Паха, використовуючи алгебру многочленів, довелиИзложение доказательства Ellenberg и Gijswijt на русском языке існування для кожного простого сталої такої, що якщо не містить прогресії довжини 3. У їхній роботі . Зокрема, для випадку виконується . За припущення з оптимізації функції випливає, що , де — абсолютна стала, що є розв'язком рівняння , тобто , де
Нижні оцінки Найкраща побудова-контрприклад дозволяє будувати для груп виду множини розміру , які не містять арифметичних прогресій довжини 3.
Для довільних груп У роботі Мешулама розглянуто теорему Рота для довільної групи та виведено оцінку для множини без арифметичних прогресій довжини 3.
З цього випливає існування абсолютної сталої такої, що для множини без прогресій виконується .
Двовимірне узагальнення Класичним узагальненням теореми Рота для двовимірних множин вважають теорему про кутики. Хоча там і не згадано про арифметичні прогресії (у двовимірному сенсі), але теорема Рота з неї випливає.
Див. також Теорема ван дер Вардена
Примітки
Література