Теорема Семереді (раніше відома як гіпотеза Ердеша — Турана) — твердження комбінаторної теорії чисел про наявність довгих арифметичних прогресій у щільних множинах.
Є класичним прикладом теореми адитивної комбінаторики. Деякі прийоми її доведення використано для доведення теореми Ґріна — Тао.
Формулювання
Початкове формулювання теореми містило лише умову щільності множини в цілому.
У будь-якій нескінченній множині додатної асимптотичної щільності існує прогресія будь-якої довжини . |
Існує еквівалентний наведеному вище скінченний варіант.
Для довільного і достатньо великих довільна множина розміру містить арифметичну прогресію довжини . |
Скінченний варіант важливий у зв'язку з можливістю формулювання кількісних результатів зв'язку і . Він показує, що в першому (нескінченному) варіанті межею, після якої наявність прогресій стає неминучою, є не саме значення щільності, а певний закон розподілу. Точний опис цієї межі станом на 2019 рік невідомий.
Скінченний варіант теореми залишиться еквівалентним, якщо розглядати і, відповідно, прогресії в кільці лишків за модулем . Такий підхід відкриває шлях до доведення за допомогою тригонометричних сум.
При або твердження теореми тривіальне. Окремий випадок називають теоремою Рота. Його доведення є значно простішим, ніж для загального випадку, і в літературі часто викладається окремо. Крім того, для теореми Рота відомі значно кращі, порівняно із загальними, оцінками критичних значень , зокрема й для узагальнень на різні групи.
Історія
Вперше твердження теореми сформулювали 1936 року як гіпотезу Ердеш і Туран.
Випадок довів 1953 року Клаусом Ротом, адаптувавши кругового методу Гарді — Літлвуда.
Випадок довів 1969 року Ендре Семереді, використовуючи комбінаторний метод, близький до застосованого для доведення випадку . 1972 року Рот дав друге доведення цього ж випадку.
Загальний випадок для довільного довів 1975 року також Семереді, використавши винахідливі та складні комбінаторні аргументи. Основу його доведення становить так звана , що описує будову довільних графів із погляду псевдовипадковості.
Пізніше знайдено інші доведення теореми, серед них найважливіші — це доведення [de] 1977 року, що використовує ергодичну теорію, і доведення Гауерса 2001 року, що використовує гармонічний аналіз та комбінаторику.
Оцінки
Говорячи про кількісні оцінки для теореми Семереді, зазвичай мають на увазі розмір найбільшої підмножини інтервалу , що не містить прогресій заданої довжини:
Таким чином, для виведення верхніх оцінок на потрібні загальні доведення, а для доведення нижчих (тобто спростування відповідних верхніх) достатньо пред'явити побудову одного контрприкладу.
Верхні оцінки
Перше загальне доведення теореми Семереді через використання леми регулярності давало дуже погані оцінки залежності , що виражаються через (вежі степенів).
Кількісні оцінки, подібні до відповідних оцінок для теореми Рота, отримав 2001 року Гауерс:
, де |
Для випадку існують набагато кращі оцінки, отримані специфічними для цього випадку методами.
Нижні оцінки
У випадку найбільшою (на 2019 рік) побудовою множини без прогресій є (побудова Беренда). Вона дає множину розмірів .
Ранкін 1961 року узагальнив цю побудову на довільні , побудувавши множину розмірів без прогресій довжини .
Побудова Беренда ставить у відповідність числу точку в багатовимірному просторі, координати якої відповідають розрядам числа в деякій системі числення. Множина складається з точок, що відповідають у цьому сенсі точкам певної сфери. Строга опуклість сфери гарантує відсутність трьох точок на одній прямій, а отже, й тричленних прогресій.
Ідея Ранкіна полягає в ітеруванні цього прийому. Наприклад, для беруться точки (та їх образи в системі числення) не з одної сфери, а зі всіх сфер, квадрати радіусів яких належать множині, утвореній за типом множини Беренда (побудови для ). Для — зі сфер, квадрати радіусів яких належать множині точок із попереднього речення, і т. д.
При цьому основу системи числення та обмеження на значення цифр на кожній ітерації підбирають так, щоб можна було довести лему про кількість розв'язків рівняння за таких умов, тому фактично множини точок, що виникають на проміжних етапах побудови, не є оптимальними за розміром для менших значень .Зв'язок з іншими теоремами
Теорема Семереді є прямим узагальненням теореми ван дер Вардена, оскільки під час поділу натуральних чисел на скінченне число класів хоча б один з них матиме додатну щільність.
Із (досить хороших) верхніх оцінок критичних значень щільності в теоремі Семереді може випливати гіпотеза Ердеша про арифметичні прогресії.
Див. також
Література
- Руэ, Хуанхо. Искусство подсчёта. Комбинаторика и перечисление. — М. : Де Агостини, 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 (16 июня). — С. 111—179.
Примітки
- Існує також інша гіпотеза, названа іменами цих учених — .
- Шкредов, 2006, с. 159—165.
- Із теореми не випливає існування в нескінченних арифметичних прогресій, і таке твердження справді було б хибним. Наприклад, контрприкладом є множина чисел, які містять одиницю в першому розряді десяткового запису.
- Шкредов, 2006.
- 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.
- 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.
- 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
- (1972), Irregularities of sequences relative to arithmetic progressions, IV, Periodica Math. Hungar., 2: 301—326, doi:10.1007/BF02018670, MR0369311.
- (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.
- Або циклічної групи , що збігається з точністю до сталої.
- (2001), , Geom. Funct. Anal., 11 (3): 465—588, doi:10.1007/s00039-001-0332-9, MR1844079, архів оригіналу за 13 жовтня 2022, процитовано 21 серпня 2023.
- A quantitative improvement for Roth's theorem on arithmetic progressions, Journal of the London Mathematical Society, 93 (3), 2016: 643—663.
- (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.
- Шкредов, 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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Teorema Semeredi ranishe vidoma yak gipoteza Erdesha Turana tverdzhennya kombinatornoyi teoriyi chisel pro nayavnist dovgih arifmetichnih progresij u shilnih mnozhinah Ye klasichnim prikladom teoremi aditivnoyi kombinatoriki Deyaki prijomi yiyi dovedennya vikoristano dlya dovedennya teoremi Grina Tao FormulyuvannyaPochatkove formulyuvannya teoremi mistilo lishe umovu shilnosti mnozhini v cilomu U bud yakij neskinchennij mnozhini A N displaystyle A subset mathbb N dodatnoyi asimptotichnoyi shilnosti D A gt 0 displaystyle D A gt 0 isnuye progresiya bud yakoyi dovzhini k displaystyle k Isnuye ekvivalentnij navedenomu vishe skinchennij variant Dlya dovilnogo d gt 0 displaystyle delta gt 0 i dostatno velikih N gt N k d displaystyle N gt N k delta dovilna mnozhina A 1 N displaystyle A subset 1 dots N rozmiru A d N displaystyle A geqslant delta N mistit arifmetichnu progresiyu dovzhini k displaystyle k Skinchennij variant vazhlivij u zv yazku z mozhlivistyu formulyuvannya kilkisnih rezultativ zv yazku d displaystyle delta i N displaystyle N Vin pokazuye sho v pershomu neskinchennomu varianti mezheyu pislya yakoyi nayavnist progresij staye neminuchoyu ye ne same znachennya shilnosti a pevnij zakon rozpodilu Tochnij opis ciyeyi mezhi stanom na 2019 rik nevidomij Skinchennij variant teoremi zalishitsya ekvivalentnim yaksho rozglyadati A Z N displaystyle A subset mathbb Z N i vidpovidno progresiyi v kilci lishkiv za modulem N displaystyle N Takij pidhid vidkrivaye shlyah do dovedennya za dopomogoyu trigonometrichnih sum Pri k 1 displaystyle k 1 abo k 2 displaystyle k 2 tverdzhennya teoremi trivialne Okremij vipadok k 3 displaystyle k 3 nazivayut teoremoyu Rota Jogo dovedennya ye znachno prostishim nizh dlya zagalnogo vipadku i v literaturi chasto vikladayetsya okremo Krim togo dlya teoremi Rota vidomi znachno krashi porivnyano iz zagalnimi ocinkami kritichnih znachen d displaystyle delta zokrema j dlya uzagalnen na rizni grupi IstoriyaVpershe tverdzhennya teoremi sformulyuvali 1936 roku yak gipotezu Erdesh i Turan Vipadok k 3 displaystyle k 3 doviv 1953 roku Klausom Rotom adaptuvavshi krugovogo metodu Gardi Litlvuda Vipadok k 4 displaystyle k 4 doviv 1969 roku Endre Semeredi vikoristovuyuchi kombinatornij metod blizkij do zastosovanogo dlya dovedennya vipadku k 3 displaystyle k 3 1972 roku Rot dav druge dovedennya cogo zh vipadku Zagalnij vipadok dlya dovilnogo k displaystyle k doviv 1975 roku takozh Semeredi vikoristavshi vinahidlivi ta skladni kombinatorni argumenti Osnovu jogo dovedennya stanovit tak zvana sho opisuye budovu dovilnih grafiv iz poglyadu psevdovipadkovosti Piznishe znajdeno inshi dovedennya teoremi sered nih najvazhlivishi ce dovedennya de 1977 roku sho vikoristovuye ergodichnu teoriyu i dovedennya Gauersa 2001 roku sho vikoristovuye garmonichnij analiz ta kombinatoriku OcinkiGovoryachi pro kilkisni ocinki dlya teoremi Semeredi zazvichaj mayut na uvazi rozmir najbilshoyi pidmnozhini intervalu 1 N displaystyle 1 dots N sho ne mistit progresij zadanoyi dovzhini a k N max A A 1 N a d a a d a k 1 d A 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 Takim chinom dlya vivedennya verhnih ocinok na a k N displaystyle a k N potribni zagalni dovedennya a dlya dovedennya nizhchih tobto sprostuvannya vidpovidnih verhnih dostatno pred yaviti pobudovu odnogo kontrprikladu Verhni ocinki Pershe zagalne dovedennya teoremi Semeredi cherez vikoristannya lemi regulyarnosti davalo duzhe pogani ocinki zalezhnosti d d N displaystyle delta delta N sho virazhayutsya cherez vezhi stepeniv Kilkisni ocinki podibni do vidpovidnih ocinok dlya teoremi Rota otrimav 2001 roku Gauers a k N N log N c k displaystyle a k N ll frac N log N c k de c k 2 2 k 9 displaystyle c k 2 2 k 9 Dlya vipadku k 3 displaystyle k 3 isnuyut nabagato krashi ocinki otrimani specifichnimi dlya cogo vipadku metodami Nizhni ocinki U vipadku k 3 displaystyle k 3 najbilshoyu na 2019 rik pobudovoyu mnozhini bez progresij ye pobudova Berenda Vona daye mnozhinu rozmiriv exp O log N 1 2 N displaystyle exp Big O big log N 1 2 big Big N Rankin 1961 roku uzagalniv cyu pobudovu na dovilni k displaystyle k pobuduvavshi mnozhinu rozmiriv exp O log N 1 k 1 N displaystyle exp left O left log N frac 1 k 1 right right N bez progresij dovzhini k displaystyle k Korotkij opis pobudoviPobudova Berenda stavit u vidpovidnist chislu tochku v bagatovimirnomu prostori koordinati yakoyi vidpovidayut rozryadam chisla v deyakij sistemi chislennya Mnozhina skladayetsya z tochok sho vidpovidayut u comu sensi tochkam pevnoyi sferi Stroga opuklist sferi garantuye vidsutnist troh tochok na odnij pryamij a otzhe j trichlennih progresij Ideya Rankina polyagaye v iteruvanni cogo prijomu Napriklad dlya k 4 displaystyle k 4 berutsya tochki ta yih obrazi v sistemi chislennya ne z odnoyi sferi a zi vsih sfer kvadrati radiusiv yakih nalezhat mnozhini utvorenij za tipom mnozhini Berenda pobudovi dlya k 3 displaystyle k 3 Dlya k 5 displaystyle k 5 zi sfer kvadrati radiusiv yakih nalezhat mnozhini tochok iz poperednogo rechennya i t d Pri comu osnovu sistemi chislennya ta obmezhennya na znachennya cifr na kozhnij iteraciyi pidbirayut tak shob mozhna bulo dovesti lemu pro kilkist rozv yazkiv rivnyannya x 1 2 x k 2 N displaystyle x 1 2 dots x k 2 N za takih umov tomu faktichno mnozhini tochok sho vinikayut na promizhnih etapah pobudovi ne ye optimalnimi za rozmirom dlya menshih znachen k displaystyle k Zv yazok z inshimi teoremamiTeorema Semeredi ye pryamim uzagalnennyam teoremi van der Vardena oskilki pid chas podilu naturalnih chisel na skinchenne chislo klasiv hocha b odin z nih matime dodatnu shilnist Iz dosit horoshih verhnih ocinok kritichnih znachen shilnosti v teoremi Semeredi mozhe viplivati gipoteza Erdesha pro arifmetichni progresiyi Div takozhLema regulyarnosti Semeredi Teorema Rota Teorema pro kutiki Teorema van der VardenaLiteraturaRue Huanho Iskusstvo podschyota Kombinatorika i perechislenie M De Agostini 2014 S 123 132 Mir matematiki v 45 tomah tom 34 ISBN 978 5 9774 0729 8 Tao Terence The ergodic and combinatorial approaches to Szemeredi s theorem Additive Combinatorics Granville Andrew Nathanson Melvyn B Solymosi Jozsef American Mathematical Society 2007 T 43 S 145 193 CRM Proceedings amp Lecture Notes ISBN 978 0 8218 4351 2 I D Shkredov Teorema Semeredi i zadachi ob arifmeticheskih progressiyah Uspehi matematicheskih nauk Rossijskaya akademiya nauk 2006 Vyp 6 16 iyunya S 111 179 PrimitkiIsnuye takozh insha gipoteza nazvana imenami cih uchenih Shkredov 2006 s 159 165 Iz teoremi ne viplivaye isnuvannya v A displaystyle A neskinchennih arifmetichnih progresij i take tverdzhennya spravdi bulo b hibnim Napriklad kontrprikladom ye mnozhina chisel yaki mistyat odinicyu v pershomu rozryadi desyatkovogo zapisu Shkredov 2006 Erdos Paul Turan Paul 1936 PDF Journal of the London Mathematical Society 11 4 261 264 doi 10 1112 jlms s1 11 4 261 arhiv originalu PDF za 22 sichnya 2022 procitovano 21 serpnya 2023 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 Szemeredi 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 1972 Irregularities of sequences relative to arithmetic progressions IV Periodica Math Hungar 2 301 326 doi 10 1007 BF02018670 MR0369311 1977 Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions J D Analyse Math 31 204 256 doi 10 1007 BF02813304 MR0498471 Abo ciklichnoyi grupi Z N displaystyle mathbb Z N sho zbigayetsya z tochnistyu do staloyi 2001 Geom Funct Anal 11 3 465 588 doi 10 1007 s00039 001 0332 9 MR1844079 arhiv originalu za 13 zhovtnya 2022 procitovano 21 serpnya 2023 A quantitative improvement for Roth s theorem on arithmetic progressions Journal of the London Mathematical Society 93 3 2016 643 663 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 Shkredov 2006 s 139 140 PosilannyaAnnouncement by Ben Green and Terence Tao preprint dostupnij na Discussion of Szemeredi s theorem part 1 of 5 Ben Green and Terence Tao Szemeredi s theorem na Scholarpedia Weisstein Eric W SzemeredisTheorem angl na sajti Wolfram MathWorld