Interested Article - Теорема Семереди

Теорема Семереди (ранее известная как гипотеза Эрдёша — Турана ) — утверждение комбинаторной теории чисел о наличии длинных арифметических прогрессий в плотных множествах.

Является классическим примером теоремы аддитивной комбинаторики . Некоторые приёмы её доказательства были использованы при доказательстве теоремы Грина — Тао .

Формулировка

Изначальная формулировка теоремы содержала только условие на плотность множества в целом.

В любом бесконечном множестве $A\subset {\mathbb {N} }$ положительной асимптотической плотности $D(A)>0$ существует прогрессия любой длины $k$ .

Существует эквивалентный приведённому выше конечный вариант.

Для любого $\delta >0$ и достаточно больших $N>N(k,\delta )$ любое множество $A\subset \{1,\dots ,N\}$ размера $|A|\geqslant \delta N$ содержит арифметическую прогрессию длины $k$ .

Конечный вариант важен в связи с возможностью формулировки количественных результатов о связи $\delta$ и $N$ . Он показывает, что в первом (бесконечном) варианте границей, за которой наличие прогрессий становится неизбежным, является не само по себе значение плотности, а некоторый закон распределения. Точное описание этой границы по состоянию на 2019 год неизвестно.

Конечный вариант теоремы останется эквивалентным если рассматривать $A\subset \mathbb {Z} _{N}$ и, соответственно, прогрессии в кольце вычетов по модулю $N$ . Такой подход открывает путь к доказательству с помощью тригонометрических сумм .

При $k=1$ или $k=2$ утверждение теоремы тривиально. Частный случай $k=3$ называется теоремой Рота . Его доказательство намного проще, чем для общего случая, и в литературе часто излагается отдельно. Кроме того, для теоремы Рота известны намного лучшие по сравнению с общими критических значений $\delta$ , в том числе для обобщений на различные группы .

История

Впервые утверждение теоремы было сформулировано в качестве гипотезы Эрдёшом и Тураном в 1936 году.

Случай $k=3$ был доказан в 1953 году Клаусом Ротом путём адаптации .

Случай $k=4$ доказал в 1969 году Эндре Семереди , используя комбинаторный метод, близкий к тому, какой был применён для доказательства случая $k=3$ . Рот дал второе доказательство этого же случая в 1972 году.

Общий случай для любого $k$ доказал в 1975 году также Семереди , использовав изобретательные и сложные комбинаторные аргументы. Основу его доказательства составляет так называемая лемма регулярности , описывающая устройство произвольных графов с точки зрения псевдослучайности.

Позднее были найдены другие доказательства теоремы, среди них наиболее важные — это доказательство ( нем. ) 1977 года, использующее эргодическую теорию , и доказательство Гауэрса 2001 года, использующее гармонический анализ и комбинаторику .

Оценки

Говоря о количественных оценках для теоремы Семереди, обычно имеют в виду размер наибольшего подмножества интервала $\{1,\dots ,N\}$ , не содержащего прогрессий заданной длины:

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 \}}.

Таким образом, для вывода верхних оценок на $a_{k}(N)$ нужны общие доказательства, а для доказательства нижних (то есть опровержения соответствующих верхних) достаточно предъявить конструкцию одного контрпримера.

Верхние оценки

Первое общее доказательство теоремы Семереди ввиду использования леммы регулярности давало очень плохие оценки на зависимость $\delta =\delta (N)$ , выражаемые через башни из экспонент .

Количественные оценки, сходные с соответствующими оценками для теоремы Рота , получил Гауэрс в 2001 году :

$a_{k}(N)\ll {\frac {N}{(\log N)^{c_{k}}}}$ , где $c_{k}=2^{-2^{k+9}}.$

Для случая $k=3$ существуют намного лучшие оценки , полученные специфичными для этого случая методами.

Нижние оценки

В случае $k=3$ наибольшей (на 2019 год) конструкцией множества без прогрессий является конструкция Беренда . Она даёт множества размера $\exp {\Big (}{-}O{\big (}(\log N)^{1/2}{\big )}{\Big )}N$ .

Ранкин в 1961 году обобщил эту конструкцию на произвольные $k$ , построив множество размера $\exp \left({-}O\left((\log N)^{\frac {1}{k-1}}\right)\right)N$ без прогрессий длины $k$ .

Краткое описание конструкции

Конструкция Беренда ставит в соответствие числу точку в многомерном пространстве, координаты которой соответствуют разрядам числа в некоторой системе счисления. Множество составляется из точек, соответствующих в этом смысле точкам некоторой сферы. Строгая выпуклость сферы гарантирует отсутствие трёх точек на одной прямой, а значит, и трёхчленных прогрессий.

Идея Ранкина заключается в итерировании этого приёма. Например, для $k=4$ берутся точки (и их образы в системе счисления) не из одной сферы, а из всех сфер, квадраты радиусов которых принадлежат множеству, образованному по типу множества Беренда (конструкции для $k=3$ ). Для $k=5$ — из сфер, квадраты радиусов которых принадлежат множеству точек из предыдущего предложения, и т. п.

При этом основание системы счисления и ограничения на значение цифр на каждой итерации подбираются специальным образом, чтобы можно было доказать лемму о числе решений уравнения $x_{1}^{2}+\dots +x_{k}^{2}=N$ при таких условиях, поэтому фактически множества точек, возникающих на промежуточных этапах построения, не являются оптимальными по размеру для меньших значений $k$ .

Связь с другими теоремами

Теорема Семереди является прямым обобщением теоремы ван дер Вардена , поскольку при разделении натуральных чисел на конечное число классов хотя бы один из них будет иметь положительную плотность.

Из достаточно хороших верхних оценок на критические значения плотности в теореме Семереди может следовать гипотеза Эрдёша об арифметических прогрессиях .

См. также

Литература

Руэ, Хуанхо. Искусство подсчёта. Комбинаторика и перечисление. — М. : Де Агостини, 2014. — С. 123—132. — 144 с. — (Мир математики: в 45 томах, том 34). — ISBN 978-5-9774-0729-8 .
(англ.) ( . The ergodic and combinatorial approaches to Szemerédi's theorem // Additive Combinatorics (неопр.) / Granville, Andrew; Nathanson, Melvyn B.; Solymosi, József. — American Mathematical Society , 2007. — Т. 43. — С. 145—193. — (CRM Proceedings & Lecture Notes). — ISBN 978-0-8218-4351-2 .
И. Д. Шкредов. (рус.) // Успехи математических наук . — Российская академия наук , 2006. — Вып. 6 . — С. 111—179 .

Примечания

Существует также другая гипотеза, названная именами этих учёных — .
, с. 159—165.
Из теоремы не следует существование в $A$ бесконечных арифметических прогрессий, и такое утверждение действительно было бы неверно. Например, контрпримером является множество чисел, содержащих единицу в первом разряде десятичной записи.
, с. 113.
Erdős, Paul ; (1936), (PDF) , Journal of the London Mathematical Society , 11 (4): 261—264, doi : от 23 июля 2020 на Wayback Machine .
Roth, Klaus Friedrich (1953), "On certain sets of integers, I", Journal of the London Mathematical Society , 28 : 104—109, doi : , Zbl 0050.04002, MR : .
Szemerédi, Endre (1969), "On sets of integers containing no four elements in arithmetic progression", Acta Math. Acad. Sci. Hung. , 20 : 89—104, doi : , Zbl 0175.04301, MR :
Roth, Klaus Friedrich (1972), "Irregularities of sequences relative to arithmetic progressions, IV", Periodica Math. Hungar. , 2 : 301—326, doi : , MR : .
Szemerédi, Endre (1975), (PDF) , Acta Arithmetica , 27 : 199—245, Zbl 0303.10056, MR : от 10 декабря 2020 на Wayback Machine .
(1977), "Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions", J. D’Analyse Math. , 31 : 204—256, doi : , MR : .
↑ Gowers, Timothy (2001), , Geom. Funct. Anal. , 11 (3): 465—588, doi : , MR : от 26 сентября 2020 на Wayback Machine .
Или циклической группы $\mathbb {Z} _{N}$ , что совпадает с точностью до константы.
"A quantitative improvement for Roth's theorem on arithmetic progressions", Journal of the London Mathematical Society , 93 (3): 643—663, 2016 .
(1962), "Sets of integers containing not more than a given number of terms in arithmetical progression", Proc. Roy. Soc. Edinburgh Sect. A , 65 : 332—344, Zbl 0104.03705, MR : .
, с. 139—140.