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

Теорема Семереді (раніше відома як гіпотеза Ердеша — Турана) — твердження комбінаторної теорії чисел про наявність довгих арифметичних прогресій у щільних множинах.

Є класичним прикладом теореми адитивної комбінаторики. Деякі прийоми її доведення використано для доведення теореми Ґріна — Тао.

Формулювання

Початкове формулювання теореми містило лише умову щільності множини в цілому.

У будь-якій нескінченній множині $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. — (Мир математики: в 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.
• И. Д. Шкредов. Теорема Семереди и задачи об арифметических прогрессиях // Успехи математических наук. — Российская академия наук, 2006. — Вып. 6 (21 апреля). — С. 111—179.

Посилання

• Announcement by Ben Green and Terence Tao — препринт доступний на math.NT/0404188
• Discussion of Szemerédi's theorem (part 1 of 5)
• Ben Green and Terence Tao: Szemerédi's theorem на Scholarpedia
• Weisstein, Eric W. SzemeredisTheorem(англ.) на сайті Wolfram MathWorld.