Теорема Семереді (раніше відома як гіпотеза Ердеша — Турана[1]) — твердження комбінаторної теорії чисел про наявність довгих арифметичних прогресій у щільних множинах.
Є класичним прикладом теореми адитивної комбінаторики. Деякі прийоми її доведення використано для доведення теореми Ґріна — Тао[2].
Початкове формулювання теореми містило лише умову щільності множини в цілому.
У будь-якій нескінченній множині A ⊂ ⊂ --> N {\displaystyle A\subset {\mathbb {N} }} додатної асимптотичної щільності D ( A ) > 0 {\displaystyle D(A)>0} існує прогресія будь-якої довжини k {\displaystyle k} .[3]
Існує еквівалентний наведеному вище[4] скінченний варіант.
Для довільного δ δ --> > 0 {\displaystyle \delta >0} і достатньо великих N > N ( k , δ δ --> ) {\displaystyle N>N(k,\delta )} довільна множина A ⊂ ⊂ --> { 1 , … … --> , N } {\displaystyle A\subset \{1,\dots ,N\}} розміру | A | ⩾ ⩾ --> δ δ --> N {\displaystyle |A|\geqslant \delta N} містить арифметичну прогресію довжини k {\displaystyle k} .
Скінченний варіант важливий у зв'язку з можливістю формулювання кількісних результатів зв'язку δ δ --> {\displaystyle \delta } і N {\displaystyle N} . Він показує, що в першому (нескінченному) варіанті межею, після якої наявність прогресій стає неминучою, є не саме значення щільності, а певний закон розподілу. Точний опис цієї межі станом на 2019 рік невідомий.
Скінченний варіант теореми залишиться еквівалентним, якщо розглядати A ⊂ ⊂ --> Z N {\displaystyle A\subset \mathbb {Z} _{N}} і, відповідно, прогресії в кільці лишків за модулем N {\displaystyle N} . Такий підхід відкриває шлях до доведення за допомогою тригонометричних сум.
При k = 1 {\displaystyle k=1} або k = 2 {\displaystyle k=2} твердження теореми тривіальне. Окремий випадок k = 3 {\displaystyle k=3} називають теоремою Рота. Його доведення є значно простішим, ніж для загального випадку, і в літературі часто викладається окремо. Крім того, для теореми Рота відомі значно кращі, порівняно із загальними, оцінками критичних значень δ δ --> {\displaystyle \delta } , зокрема й для узагальнень на різні групи.
Вперше твердження теореми сформулювали 1936 року як гіпотезу Ердеш і Туран[5].
Випадок k = 3 {\displaystyle k=3} довів 1953 року Клаусом Ротом[6], адаптувавши кругового методу Гарді — Літлвуда.
Випадок k = 4 {\displaystyle k=4} довів 1969 року Ендре Семереді[7], використовуючи комбінаторний метод, близький до застосованого для доведення випадку k = 3 {\displaystyle k=3} . 1972 року Рот[8] дав друге доведення цього ж випадку.
Загальний випадок для довільного k {\displaystyle k} довів 1975 року також Семереді, використавши винахідливі та складні комбінаторні аргументи. Основу його доведення становить так звана лема регулярності, що описує будову довільних графів із погляду псевдовипадковості.
Пізніше знайдено інші доведення теореми, серед них найважливіші — це доведення Фюрстенберга[de][9] 1977 року, що використовує ергодичну теорію, і доведення Гауерса 2001 року, що використовує гармонічний аналіз та комбінаторику.
Говорячи про кількісні оцінки для теореми Семереді, зазвичай мають на увазі розмір найбільшої підмножини інтервалу { 1 , … … --> , N } {\displaystyle \{1,\dots ,N\}} [10], що не містить прогресій заданої довжини:
Таким чином, для виведення верхніх оцінок на a k ( N ) {\displaystyle a_{k}(N)} потрібні загальні доведення, а для доведення нижчих (тобто спростування відповідних верхніх) достатньо пред'явити побудову одного контрприкладу.
Перше загальне доведення теореми Семереді через використання леми регулярності давало дуже погані оцінки залежності δ δ --> = δ δ --> ( N ) {\displaystyle \delta =\delta (N)} , що виражаються через вежі степенів.
Кількісні оцінки, подібні до відповідних оцінок для теореми Рота, отримав 2001 року Гауерс[11]:
a k ( N ) ≪ ≪ --> N ( log --> N ) c k {\displaystyle a_{k}(N)\ll {\frac {N}{(\log N)^{c_{k}}}}} , де c k = 2 − − --> 2 k + 9 . {\displaystyle c_{k}=2^{-2^{k+9}}.}
Для випадку k = 3 {\displaystyle k=3} існують набагато кращі оцінки, отримані специфічними для цього випадку методами[12].
У випадку k = 3 {\displaystyle k=3} найбільшою (на 2019 рік) побудовою множини без прогресій є побудова Беренда. Вона дає множину розмірів exp --> ( − − --> O ( ( log --> N ) 1 / 2 ) ) N {\displaystyle \exp {\Big (}{-}O{\big (}(\log N)^{1/2}{\big )}{\Big )}N} .
Ранкін 1961 року узагальнив цю побудову на довільні k {\displaystyle k} , побудувавши множину розмірів exp --> ( − − --> O ( ( log --> N ) 1 k − − --> 1 ) ) N {\displaystyle \exp \left({-}O\left((\log N)^{\frac {1}{k-1}}\right)\right)N} без прогресій довжини k {\displaystyle k} [13].
Побудова Беренда ставить у відповідність числу точку в багатовимірному просторі, координати якої відповідають розрядам числа в деякій системі числення. Множина складається з точок, що відповідають у цьому сенсі точкам певної сфери. Строга опуклість сфери гарантує відсутність трьох точок на одній прямій, а отже, й тричленних прогресій.
Ідея Ранкіна полягає в ітеруванні цього прийому. Наприклад, для k = 4 {\displaystyle k=4} беруться точки (та їх образи в системі числення) не з одної сфери, а зі всіх сфер, квадрати радіусів яких належать множині, утвореній за типом множини Беренда (побудови для k = 3 {\displaystyle k=3} ). Для k = 5 {\displaystyle k=5} — зі сфер, квадрати радіусів яких належать множині точок із попереднього речення, і т. д.
Теорема Семереді є прямим узагальненням теореми ван дер Вардена, оскільки під час поділу натуральних чисел на скінченне число класів хоча б один з них матиме додатну щільність.
Із досить хороших верхніх оцінок критичних значень щільності в теоремі Семереді може випливати гіпотеза Ердеша про арифметичні прогресії[14].
Lokasi Pengunjung: 3.142.40.44