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

---

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

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

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

Для любого ${\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}$. Такой подход открывает путь к доказательству с помощью тригонометрических сумм.

---