Меню
Главная
Случайная статья
Настройки
|
Теорема Рота — результат аддитивной комбинаторики, частный случай теоремы Семереди для прогрессий длины 3; утверждает присутствие арифметических прогрессий в любых достаточно плотных множествах.
Точная формулировка: для любого любое множество , имеющее асимптотическую плотность , содержит арифметическую прогрессию длины 3.
Аналогичные формулировки, использующие верхнюю и нижнюю асимптотическую плотность, эквивалентны[1].
Также эквивалентна исходной и формулировка для конечных множеств: для любого существует такое, что если , и , то содержит арифметическую прогрессию длины 3. Подавляющее большинство доказательств доказывает именно формулировку для конечных множеств.
Содержание
История улучшения количественных оценок
| Размер максимального подмножества
без прогрессий длины 3
|
| Год публикации |
Размер
(с точностью до константы) |
Автор(ы)
|
| 1953
|
|
Рот[2]
|
| 1987
|
|
Хиз-Браун[англ.][3][4]
|
| 1999
|
|
Бургейн[5]
|
| 2008
|
|
Бургейн[6]
|
| 2012
|
|
Сандерс[англ.][7]
|
| 2011
|
|
Сандерс[8]
|
| 2014
|
|
Блум[9]
|
| 2020 (препринт)
|
|
Шоен[пол.][10]
|
| 2020 (препринт)
|
|
Блум, Сисаск[11]
|
Различные доказательства
Гармонический анализ
Теорема была впервые доказана в 1953 году Клаусом Ротом[2][12] путём адаптации кругового метода Харди — Литтлвуда. Доказательство использовало идею[13], впоследствии обобщённую и для общего доказательства теоремы Семереди: все множества заданной плотности разбиваться на две группы — «равномерные» и «неравномерные», причём под «равномерностью» понимается верхняя оценка на коэффициенты Фурье. Если множество равномерно, то наличие прогрессий в нём можно доказать напрямую, а иначе можно доказать наличие подпрогрессии, в которой плотность множества больше чем среди отрезка натурального ряда, к которому оно принадлежит.
Метод позволяет вывести оценку . Технические подробности доказательства, граница коэффициентов Фурье, определяющая «равномерность», и получаемые константы могут отличаться в разных источниках.
Комбинаторное (через лемму Семереди)
Доказательство теоремы Рота можно вывести[14] как частный случай теоремы Семереди из доказательства Семереди. Такой способ доказательства требует использования леммы регулярности Семереди и теоремы об уголках, откуда теорема Рота следует напрямую. Возможно[15] даже обойтись без использования теоремы об уголках, а выводить теорему Рота напрямую из леммы об удалении треугольников, но только в формулировке для конечных циклических групп (см. раздел «Обобщения на различные группы»).
Поскольку лемма регулярности Семереди даёт чрезвычайно большие верхние оценки на получаемую через неё величину (как минимум, башни из экспонент), то и сам метод не позволяет получить оценки лучше этих.
Элементарное (через обобщённые арифметические прогрессии)
Роналд Грэхем в своей книге о теории Рамсея приводит упрощённый вариант доказательства, также основанный на методе Семереди, однако не использующий лемму регулярности. В доказательстве используются обобщённые арифметические прогрессии вида , доказать присутствие которых во множестве намного более просто, а из этого уже выводится сама теорема Рота.
Доказательство Грэхема не даёт оценок на , а только показывает существование, поскольку использует существование точки в последовательности, начиная с которой все точки достаточно близки к пределу, но для предела также доказано только существование, а характер сходимости в принципе не анализируется.
Контрпримеры для неплотных множеств
Наряду с нахождением верхних оценок размера множества без арифметических прогрессий, существует также обратная задача — конструирование как можно большего множества , не содержащего арифметических прогрессий, то есть контрпримера для обозначения границ улучшаемости оценок на . Все известные конструкции таких множеств основываются на идее рассмотрения отдельных разрядов чисел в некоторой системе счисления и задания условий на значения этих разрядов.
Эрдёш, Туран (1936)
Первый пример множества без прогрессий привели в 1936 году Эрдёш и Туран, предложив рассмотреть числа, которые в троичной системе содержат только цифры 0 и 2. Такое множество содержит всего лишь чисел, что очень мало по сравнению с верхними оценками.[16]
Пусть --- множество Эрдёша--Турана.
Если и , то в троичной системе в самом старшем разряде , где различны эти числа выполняются равенства . Поэтому в арифметической прогрессии выполнялось бы , а значит, .
Салем, Спенсер (1942)
Салем и Спенсер в 1942 году обобщили идею Эрдёша и Турана на системы счисления с растущим (зависящим от размера множества) основанием и получили множество без прогрессий размера .[17]
|
|