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

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

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

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

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

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

Існує еквівалентний наведеному вище скінченний варіант.

Для довільного ${\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 }$, зокрема й для узагальнень на різні групи.

Історія

Вперше твердження теореми сформулювали 1936 року як гіпотезу Ердеш і Туран.

Випадок ${\displaystyle k=3}$ довів 1953 року Клаусом Ротом, адаптувавши кругового методу Гарді — Літлвуда.

Випадок ${\displaystyle k=4}$ довів 1969 року Ендре Семереді, використовуючи комбінаторний метод, близький до застосованого для доведення випадку ${\displaystyle k=3}$. 1972 року Рот дав друге доведення цього ж випадку.

Загальний випадок для довільного ${\displaystyle k}$ довів 1975 року також Семереді, використавши винахідливі та складні комбінаторні аргументи. Основу його доведення становить так звана , що описує будову довільних графів із погляду псевдовипадковості.

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

Оцінки

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

${\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 року Гауерс:

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

Для випадку ${\displaystyle k=3}$ існують набагато кращі оцінки, отримані специфічними для цього випадку методами.

Нижні оцінки

У випадку ${\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}$.

Короткий опис побудови

Побудова Беренда ставить у відповідність числу точку в багатовимірному просторі, координати якої відповідають розрядам числа в деякій системі числення. Множина складається з точок, що відповідають у цьому сенсі точкам певної сфери. Строга опуклість сфери гарантує відсутність трьох точок на одній прямій, а отже, й тричленних прогресій.

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

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

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

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

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

Див. також

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

Література

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

Примітки

1. Існує також інша гіпотеза, названа іменами цих учених — .
2. Шкредов, 2006, с. 159—165.
3. Із теореми не випливає існування в ${\displaystyle A}$ нескінченних арифметичних прогресій, і таке твердження справді було б хибним. Наприклад, контрприкладом є множина чисел, які містять одиницю в першому розряді десяткового запису.
4. Шкредов, 2006.
5. Erdős, Paul; Turán, Paul (1936), (PDF), Journal of the London Mathematical Society, 11 (4): 261—264, doi:10.1112/jlms/s1-11.4.261, архів оригіналу (PDF) за 22 січня 2022, процитовано 21 серпня 2023.
6. Roth, Klaus Friedrich (1953), On certain sets of integers, I, Journal of the London Mathematical Society, 28: 104—109, doi:10.1112/jlms/s1-28.1.104, Zbl 0050.04002, MR0051853.
7. Szemerédi, Endre (1969), On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hung., 20: 89—104, doi:10.1007/BF01894569, Zbl 0175.04301, MR0245555
8. (1972), Irregularities of sequences relative to arithmetic progressions, IV, Periodica Math. Hungar., 2: 301—326, doi:10.1007/BF02018670, MR0369311.
9. (1977), Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. D’Analyse Math., 31: 204—256, doi:10.1007/BF02813304, MR0498471.
10. Або циклічної групи ${\displaystyle \mathbb {Z} _{N}}$, що збігається з точністю до сталої.
11. (2001), , Geom. Funct. Anal., 11 (3): 465—588, doi:10.1007/s00039-001-0332-9, MR1844079, архів оригіналу за 13 жовтня 2022, процитовано 21 серпня 2023.
12. A quantitative improvement for Roth's theorem on arithmetic progressions, Journal of the London Mathematical Society, 93 (3), 2016: 643—663.
13. (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, MR0142526.
14. Шкредов, 2006, с. 139—140.

Посилання

• Announcement by Ben Green and Terence Tao — препринт доступний на
• 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.