Теорема Семереди

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

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

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

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

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

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

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

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

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

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

История

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

Случай ${\displaystyle k=3}$ был доказан в 1953 году Клаусом Ротом^[6] путём адаптации кругового метода Харди — Литлвуда.

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

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

Позднее были найдены другие доказательства теоремы, среди них наиболее важные — это доказательство Фюрстенберга (нем. Hillel Fürstenberg)^[10] 1977 года, использующее эргодическую теорию, и доказательство Гауэрса^[11] 2001 года, использующее гармонический анализ и комбинаторику.

Оценки

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

${\displaystyle 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 \}}.}$

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

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

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

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

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

Для случая ${\displaystyle k=3}$ существуют намного лучшие оценки, полученные специфичными для этого случая методами.^[13]

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

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

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

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

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

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

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

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

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

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

См. также

• Лемма регулярности Семереди
• Теорема Рота
• Теорема об уголках
• Теорема ван дер Вардена

Литература

• Руэ, Хуанхо. Искусство подсчёта. Комбинаторика и перечисление. — М.: Де Агостини, 2014. — С. 123—132. — 144 с. — (Мир математики: в 45 томах, том 34). — ISBN 978-5-9774-0729-8.
• Tao, Terence. 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. — Zbl 1159.11005.
• И. Д. Шкредов. Теорема Семереди и задачи об арифметических прогрессиях (рус.) // Успехи математических наук. — Российская академия наук, 2006. — Вып. 6. — С. 111—179.