Перегляд вихідного коду сторінки Теорема Семереді

'''Теорема Семереді''' (раніше відома як '''гіпотеза Ердеша&nbsp;— Турана'''<ref>Існує також інша гіпотеза, названа іменами цих учених&nbsp;— [[гіпотеза Ердеша — Турана на адитивних базисах]].</ref>)&nbsp;— твердження комбінаторної теорії чисел про наявність довгих [[Арифметична прогресія|арифметичних прогресій]] у щільних множинах.

Є класичним прикладом теореми [[Адитивна комбінаторика|адитивної комбінаторики]]. Деякі прийоми її доведення використано для доведення [[Теорема Ґріна — Тао|теореми Ґріна&nbsp;— Тао]]{{Sfn|Шкредов|2006|с=159—165}}.

== Формулювання ==
Початкове формулювання теореми містило лише умову щільності множини в цілому.{{Рамка}}
У будь-якій нескінченній множині <math>A \subset {\mathbb N}</math> додатної [[Асимптотична щільність|асимптотичної щільності]] <math>D(A) > 0</math> існує прогресія будь-якої довжини <math>k</math>.<ref>Із теореми не випливає існування в <math>A</math> ''нескінченних'' арифметичних прогресій, і таке твердження справді було б хибним. Наприклад, контрприкладом є множина чисел, які містять одиницю в першому розряді десяткового запису.</ref>
{{/рамка}}Існує [[Логічна еквівалентність|еквівалентний]] наведеному вище{{Sfn|Шкредов|2006|c=113}} скінченний варіант.{{Рамка}}
Для довільного <math>\delta > 0</math> і достатньо великих <math>N > N(k, \delta)</math> довільна множина <math>A \subset \{1, \dots, N\}</math> розміру <math>|A| \geqslant \delta N</math> містить арифметичну прогресію довжини <math>k</math>.
{{/рамка}}Скінченний варіант важливий у зв'язку з можливістю формулювання кількісних результатів зв'язку <math>\delta</math> і <math>N</math>. Він показує, що в першому (нескінченному) варіанті межею, після якої наявність прогресій стає неминучою, є не саме значення щільності, а певний закон розподілу. Точний опис цієї межі станом на 2019 рік невідомий.

Скінченний варіант теореми залишиться еквівалентним, якщо розглядати <math>A \subset \mathbb Z_N</math> і, відповідно, прогресії в кільці лишків за модулем <math>N</math>. Такий підхід відкриває шлях до доведення за допомогою [[Суми Вейля|тригонометричних сум]].

При <math>k = 1</math> або <math>k = 2</math> твердження теореми тривіальне. Окремий випадок <math>k = 3</math> називають [[Теорема Рота|теоремою Рота]]. Його доведення є значно простішим, ніж для загального випадку, і в літературі часто викладається окремо. Крім того, для теореми Рота відомі значно кращі, порівняно із загальними, [[Теорема Семереді#Оцінки|оцінками]] критичних значень <math>\delta</math>, зокрема й для узагальнень на різні [[Група (математика)|групи]].

== Історія ==
Вперше твердження теореми сформулювали 1936 року як гіпотезу [[Пал Ердеш|Ердеш]] і [[Пал Туран|Туран]]<ref name="erdos turan">{{Citation|authorlink1=Пал Ердеш|first1=Paul|last1=Erdős|authorlink2=Пал Туран|first2=Paul|last2=Turán|title=On some sequences of integers|journal=[[Journal of the London Mathematical Society]]|volume=11|issue=4|year=1936|pages=261–264|url=http://www.renyi.hu/~p_erdos/1936-05.pdf|doi=10.1112/jlms/s1-11.4.261|accessdate=2023-08-21|archive-date=2022-01-22|archive-url=https://web.archive.org/web/20220122002053/https://www.renyi.hu/~p_erdos/1936-05.pdf}}.</ref>.

Випадок <math>k = 3</math> довів 1953 року [[Клаус Рот|Клаусом Ротом]]<ref>{{Citation|author-link=Клаус Рот|first=Klaus Friedrich|last=Roth|title=On certain sets of integers, I|journal=[[Journal of the London Mathematical Society]]|volume=28|pages=104–109|year=1953|id=Zbl 0050.04002, {{MathSciNet|id=0051853}}|doi=10.1112/jlms/s1-28.1.104}}.</ref>, адаптувавши [[Круговий метод Гарді — Літлвуда|кругового методу Гарді&nbsp;— Літлвуда]].

Випадок <math>k = 4</math> довів 1969 року [[Ендре Семереді]]<ref>{{Citation|author-link=Ендре Семереді|first=Endre|last=Szemerédi|title=On sets of integers containing no four elements in arithmetic progression|journal=Acta Math. Acad. Sci. Hung.|volume=20|pages=89–104|year=1969|id=Zbl 0175.04301, {{MathSciNet|id=0245555}}|doi=10.1007/BF01894569}}</ref>, використовуючи комбінаторний метод, близький до застосованого для доведення випадку <math>k = 3</math>. 1972 року Рот<ref>{{Citation|author-link=Рот, Клаус Фридрих|first=Klaus Friedrich|last=Roth|title=Irregularities of sequences relative to arithmetic progressions, IV|journal=Periodica Math. Hungar.|volume=2|pages=301–326|year=1972|id={{MathSciNet|id=0369311}}|doi=10.1007/BF02018670}}.</ref> дав друге доведення цього ж випадку.

Загальний випадок для довільного <math>k</math> довів 1975 року також Семереді, використавши винахідливі та складні комбінаторні аргументи. Основу його доведення становить так звана [[Лемма регулярності Семереді|лема регулярності]], що описує будову довільних графів із погляду псевдовипадковості.

Пізніше знайдено інші доведення теореми, серед них найважливіші&nbsp;— це доведення {{Iw|Гілель Фюрстенберг|Фюрстенберга|de|Hillel Fürstenberg}}<ref>{{Citation|author-link=Гілель Фюрстенберг|first=Hillel|last=Furstenberg|title=Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions|journal=J. D’Analyse Math.|volume=31|pages=204–256|year=1977|id={{MathSciNet|id=0498471}}|doi=10.1007/BF02813304}}.</ref> 1977 року, що використовує [[Ергодичність|ергодичну теорію]], і доведення [[Тімоті Гауерс|Гауерса]] 2001 року, що використовує [[гармонічний аналіз]] та [[Комбінаторика|комбінаторику]].

== Оцінки ==
Говорячи про кількісні оцінки для теореми Семереді, зазвичай мають на увазі розмір найбільшої підмножини інтервалу <math>\{1, \dots, N\}</math><ref>Або циклічної групи <math>\mathbb Z_N</math>, що збігається з точністю до сталої.</ref>, що не містить прогресій заданої довжини:

: <math>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\}.</math>

Таким чином, для виведення верхніх оцінок на <math>a_k(N)</math> потрібні загальні доведення, а для доведення нижчих (тобто спростування відповідних верхніх) достатньо пред'явити побудову одного контрприкладу.

=== Верхні оцінки ===
Перше загальне доведення теореми Семереді через використання [[Лема регулярності Семереді|леми регулярності]] давало дуже погані оцінки залежності <math>\delta = \delta(N)</math>, що виражаються через [[Тетрація#Термінологія|вежі степенів]].

Кількісні оцінки, подібні до відповідних оцінок для [[Теорема Рота|теореми Рота]], отримав [[2001 у науці|2001]] року [[Тімоті Гауерс|Гауерс]]<ref name="gowers">{{Citation|author-link=Гауэрс, Уильям Тимоти|first=Timothy|last=Gowers|title=A new proof of Szemerédi's theorem|journal=Geom. Funct. Anal.|volume=11|issue=3|pages=465–588|url=http://www.dpmms.cam.ac.uk/~wtg10/sz898.dvi|year=2001|id={{MathSciNet|id=1844079}}|doi=10.1007/s00039-001-0332-9|accessdate=2023-08-21|archive-date=2022-10-13|archive-url=https://web.archive.org/web/20221013225759/https://www.dpmms.cam.ac.uk/~wtg10/sz898.dvi}}.</ref>:{{Рамка}}
<math>a_k(N) \ll \frac{N}{(\log N)^{c_k}}</math>, де <math>c_k = 2^{-2^{k+9}}.</math>
{{/рамка}}Для випадку <math>k = 3</math> існують [[Теорема Рота|набагато кращі оцінки]], отримані специфічними для цього випадку методами<ref>{{Citation|author-link=T. F. Bloom|title=A quantitative improvement for Roth's theorem on arithmetic progressions|journal=Journal of the London Mathematical Society|volume=93|issue=3|pages=643—663|year=2016}}.</ref>.

=== Нижні оцінки ===
У випадку <math>k = 3</math> найбільшою (на 2019 рік) побудовою множини без прогресій є [[Теорема Рота#Беренд (1946)|побудова Беренда]]. Вона дає множину розмірів <math>\exp\Big({-}O\big((\log N)^{1/2}\big)\Big) N</math>.

Ранкін 1961 року узагальнив цю побудову на довільні <math>k</math>, побудувавши множину розмірів <math>\exp\left({-}O\left( (\log N)^{\frac{1}{k-1}}\right)\right) N</math> без прогресій довжини <math>k</math><ref>{{Citation|author-link=Роберт Ранкін|first=Robert A.|last=Rankin|title=Sets of integers containing not more than a given number of terms in arithmetical progression|journal=Proc. Roy. Soc. Edinburgh Sect. A|volume=65|pages=332–344|year=1962|id=Zbl 0104.03705, {{MathSciNet|id=0142526}}}}.</ref>.

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

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

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

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

Із [[Гіпотеза Ердеша про арифметичні прогресії#Твердження, з яких випливає гіпотеза|досить хороших]] верхніх оцінок критичних значень щільності в теоремі Семереді може випливати [[гіпотеза Ердеша про арифметичні прогресії]]{{Sfn|Шкредов|2006|с=139—140}}.

== Див. також ==

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

== Література ==

* {{Книга
|автор = Руэ, Хуанхо
|заголовок = Искусство подсчёта. Комбинаторика и перечисление
|місце = М.
|видавництво = Де Агостини
|рік = 2014
|сторінок = 144
|сторінки = 123—132
|ISBN = 978-5-9774-0729-8
|серія = Мир математики: в 45 томах, том 34
}}
* {{Книга
|частина = The ergodic and combinatorial approaches to Szemerédi's theorem
|сторінки = 145—193
|серія = CRM Proceedings & Lecture Notes
|том = 43
|видавництво = [[Американське математичне товариство|American Mathematical Society]]
|рік = 2007
|ISBN = 978-0-8218-4351-2
|ref = Tao
|мова = und
|автор = [[Теренс Тао|Tao, Terence]]
|відповідальний = Granville, Andrew; Nathanson, Melvyn B.; Solymosi, József
|назва = Additive Combinatorics
}}
* {{Стаття|author=И. Д. Шкредов|title=Теорема Семереди и задачи об арифметических прогрессиях|url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=5293&option_lang=rus|language=ru|видання=[[Успехи математических наук]]|date=2006|issue=6|pages=111—179|ref=Шкредов|publisher=[[Математичний інститут імені В. А. Стеклова РАН|Российская академия наук]]}}

== Примітки ==
{{примітки|2}}

== Посилання ==
* [http://www.math.ucla.edu/~tao/whatsnew.html Announcement by Ben Green and Terence Tao]&nbsp;— препринт доступний на [https://web.archive.org/web/20170710061159/http://front.math.ucdavis.edu/math.NT/0404188 math.NT/0404188]
* [http://in-theory.blogspot.com/2006/06/szemeredis-theorem.html Discussion of Szemerédi's theorem (part 1 of 5)]
* Ben Green and Terence Tao: [http://www.scholarpedia.org/article/Szemeredi's_Theorem Szemerédi's theorem] на [[Сколарпедія|Scholarpedia]]
* {{MathWorld|SzemeredisTheorem|SzemeredisTheorem}}
{{Бібліоінформація}}
[[Категорія:Арифметична комбінаторика]]
[[Категорія:Теорія Ремзі]]
[[Категорія:Теореми в теорії чисел]]
[[Категорія:Теорія чисел]]
[[Категорія:Комбінаторика]]