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

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

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

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

Початкове формулювання теореми містило лише умову щільності множини в цілому.Шаблон:Рамка У будь-якій нескінченній множині $A\subset \mathbb{N}$ додатної асимптотичної щільності $D(A)>0$ існує прогресія будь-якої довжини $k$. Шаблон:/рамкаІснує еквівалентний наведеному вищеШаблон:Sfn скінченний варіант.Шаблон:Рамка Для довільного $\delta >0$ і достатньо великих $N>N(k,\delta )$ довільна множина $A\subset \{1,\dots ,N\}$ розміру $|A|⩾\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 року також Семереді, використавши винахідливі та складні комбінаторні аргументи. Основу його доведення становить так звана лема регулярності, що описує будову довільних графів із погляду псевдовипадковості.

Пізніше знайдено інші доведення теореми, серед них найважливіші — це доведення Шаблон:Iw 1977 року, що використовує ергодичну теорію, і доведення Гауерса 2001 року, що використовує гармонічний аналіз та комбінаторику.

Оцінки

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

$a_k(N)=\max \{|A|:A\subset \{1,\dots ,N\},\nexists a,d:\{a,a+d,\dots ,a+(k-1)d\}\subset A\}.$

Таким чином, для виведення верхніх оцінок на $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 (-O((\log N{)}^{1/2}))N$.

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

Зв'язок з іншими теоремами

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

Із досить хороших верхніх оцінок критичних значень щільності в теоремі Семереді може випливати гіпотеза Ердеша про арифметичні прогресіїШаблон:Sfn.

Див. також

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

Література

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття

Посилання

• 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
• Шаблон:MathWorld