Русская Википедия:Теорема Семереди
Теорема Семереди (ранее известная как гипотеза Эрдёша — Турана[1]) — утверждение комбинаторной теории чисел о наличии длинных арифметических прогрессий в плотных множествах.
Является классическим примером теоремы аддитивной комбинаторики. Некоторые приёмы её доказательства были использованы при доказательстве теоремы Грина — ТаоШаблон:Sfn.
Формулировка
Изначальная формулировка теоремы содержала только условие на плотность множества в целом.
Шаблон:Рамка В любом бесконечном множестве <math>A \subset {\mathbb N}</math> положительной асимптотической плотности <math>D(A) > 0</math> существует прогрессия любой длины <math>k</math>.[2] Шаблон:Конец рамки
Существует эквивалентный приведённому вышеШаблон:Sfn конечный вариант.
Шаблон:Рамка Для любого <math>\delta > 0</math> и достаточно больших <math>N > N(k, \delta)</math> любое множество <math>A \subset \{1, \dots, N\}</math> размера <math>|A| \geqslant \delta N</math> содержит арифметическую прогрессию длины <math>k</math>. Шаблон:Конец рамки
Конечный вариант важен в связи с возможностью формулировки количественных результатов о связи <math>\delta</math> и <math>N</math>. Он показывает, что в первом (бесконечном) варианте границей, за которой наличие прогрессий становится неизбежным, является не само по себе значение плотности, а некоторый закон распределения. Точное описание этой границы по состоянию на 2019 год неизвестно.
Конечный вариант теоремы останется эквивалентным если рассматривать <math>A \subset \mathbb Z_N</math> и, соответственно, прогрессии в кольце вычетов по модулю <math>N</math>. Такой подход открывает путь к доказательству с помощью тригонометрических сумм.
При <math>k = 1</math> или <math>k = 2</math> утверждение теоремы тривиально. Частный случай <math>k = 3</math> называется теоремой Рота. Его доказательство намного проще, чем для общего случая, и в литературе часто излагается отдельно. Кроме того, для теоремы Рота известны намного лучшие по сравнению с общими оценки критических значений <math>\delta</math>, в том числе для обобщений на различные группы.
История
Впервые утверждение теоремы было сформулировано в качестве гипотезы Эрдёшом и Тураном[3] в 1936 году.
Случай <math>k = 3</math> был доказан в 1953 году Клаусом Ротом[4] путём адаптации кругового метода Харди — Литлвуда.
Случай <math>k = 4</math> доказал в 1969 году Эндре Семереди[5], используя комбинаторный метод, близкий к тому, какой был применён для доказательства случая <math>k = 3</math>. Рот[6] дал второе доказательство этого же случая в 1972 году.
Общий случай для любого <math>k</math> доказал в 1975 году также Семереди[7], использовав изобретательные и сложные комбинаторные аргументы. Основу его доказательства составляет так называемая лемма регулярности, описывающая устройство произвольных графов с точки зрения псевдослучайности.
Позднее были найдены другие доказательства теоремы, среди них наиболее важные — это доказательство Шаблон:Нп2[8] 1977 года, использующее эргодическую теорию, и доказательство Гауэрса[9] 2001 года, использующее гармонический анализ и комбинаторику.
Оценки
Говоря о количественных оценках для теоремы Семереди, обычно имеют в виду размер наибольшего подмножества интервала <math>\{1, \dots, N\}</math>[10], не содержащего прогрессий заданной длины:
- <math>a_k(N) = \max \big\{|A| : A \subset \{1, \dots, N\},\ \nexists a, d: \{a, a + d, \dots, a + (k - 1)d\} \subset A\big\}.</math>
Таким образом, для вывода верхних оценок на <math>a_k(N)</math> нужны общие доказательства, а для доказательства нижних (то есть опровержения соответствующих верхних) достаточно предъявить конструкцию одного контрпримера.
Верхние оценки
Первое общее доказательство теоремы Семереди ввиду использования леммы регулярности давало очень плохие оценки на зависимость <math>\delta = \delta(N)</math>, выражаемые через башни из экспонент.
Количественные оценки, сходные с соответствующими оценками для теоремы Рота, получил Гауэрс в 2001 году[9]:
Шаблон:Рамка <math>a_k(N) \ll \frac{N}{(\log N)^{c_k}}</math>, где <math>c_k = 2^{-2^{k+9}}.</math> Шаблон:Конец рамки
Для случая <math>k = 3</math> существуют намного лучшие оценки, полученные специфичными для этого случая методами.[11]
Нижние оценки
В случае <math>k = 3</math> наибольшей (на 2019 год) конструкцией множества без прогрессий является конструкция Беренда. Она даёт множества размера <math>\exp\Big({-}O\big((\log N)^{1/2}\big)\Big) N</math>.
Ранкин в 1961 году обобщил эту конструкцию на произвольные <math>k</math>, построив множество размера <math>\exp\left({-}O\left( (\log N)^{\frac{1}{k-1}}\right)\right) N</math> без прогрессий длины <math>k</math>.[12]
Связь с другими теоремами
Теорема Семереди является прямым обобщением теоремы ван дер Вардена, поскольку при разделении натуральных чисел на конечное число классов хотя бы один из них будет иметь положительную плотность.
Из достаточно хороших верхних оценок на критические значения плотности в теореме Семереди может следовать гипотеза Эрдёша об арифметических прогрессиях.Шаблон:Sfn
См. также
Литература
Примечания
Ссылки
- Announcement by Ben Green and Terence Tao — the preprint is available at math.NT/0404188
- Discussion of Szemerédi’s theorem (part 1 of 5)
- Ben Green and Terence Tao: Szemerédi’s theorem on Scholarpedia
- Шаблон:MathWorld
- ↑ Существует также другая гипотеза, названная именами этих учёных — гипотеза Эрдёша — Турана на аддитивных базисах.
- ↑ Из теоремы не следует существование в <math>A</math> бесконечных арифметических прогрессий, и такое утверждение действительно было бы неверно. Например, контрпримером является множество чисел, содержащих единицу в первом разряде десятичной записи.
- ↑ Шаблон:Citation Шаблон:Wayback.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation Шаблон:Wayback.
- ↑ Шаблон:Citation.
- ↑ 9,0 9,1 Шаблон:Citation Шаблон:Wayback.
- ↑ Или циклической группы <math>\mathbb Z_N</math>, что совпадает с точностью до константы.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
