Теорема Рота

Теорема Рота — результат адитивної комбінаторики, окремий випадок теореми Семереді для прогресій довжини 3; стверджує наявність арифметичних прогресій ${\displaystyle (a,a+d,a+2d),\ d\not =0}$ у будь-якій достатньо щільній множині.

Точне формулювання: для будь-якого ${\displaystyle \delta \in (0;1)}$ будь-яка множина ${\displaystyle A\subset {\mathbb {N} }}$, що має асимптотичну щільність ${\displaystyle d(A)>\delta }$ містить арифметичну прогресію довжини 3.

Аналогічні формулювання, що використовують верхню та нижню асимптотичну щільність, еквівалентні^[1].

Також еквівалентне початковому і формулювання для скінченних множин: для будь-якої ${\displaystyle \delta \in (0;1)}$ існує ${\displaystyle N_{0}=N_{0}(\delta )}$ таке, що якщо ${\displaystyle N>N_{0}}$, ${\displaystyle A\subset \left\lbrace {1,2,\dots ,N}\right\rbrace }$ і ${\displaystyle |A|>\delta N}$, то ${\displaystyle A}$ містить арифметичну прогресію довжини 3. У переважній більшості доведень доводиться саме формулювання для скінченних множин.

Розмір максимальної підмножини ${\displaystyle \{1,\dots ,N\}}$ без прогресій довжини 3
Рік публікації	Розмір (з точністю до константи)	Автор(и)
1953	${\displaystyle {\frac {N}{\log \log N}}}$	Рот[2]
1987	${\displaystyle {\frac {N}{(\log N)^{c}}},\ c>0}$	Гіз-Браун[3][4]
1999	${\displaystyle {\frac {N(\log \log N)^{1/2}}{(\log N)^{1/2}}}}$	Бурген[5]
2008	${\displaystyle {\frac {N(\log \log N)^{2}}{(\log N)^{2/3}}}}$	Бурген[6]
2012	${\displaystyle {\frac {N}{(\log N)^{3/4-o(1)}}}}$	Сандерс [7]
2011	${\displaystyle {\frac {(\log \log N)^{5}}{\log N}}N}$	Сандерс[8]
2014	${\displaystyle {\frac {(\log \log N)^{4}}{\log N}}N}$	Блум[9]
2020 (препринт)	${\displaystyle {\frac {(\log \log N)^{3}(\log \log \log N)^{5}}{\log N}}N}$	Шоен [10]
2020 (препринт)	${\displaystyle {\frac {N}{(\log N)^{1+c}}},\ c>0}$	Блум, Сісаск[11]

Теорему вперше довів 1953 року Клаус Рот^[2][12], адаптувавши круговий методу Гарді — Літтлвуда. У доведенні використано ідею^[13], згодом узагальнену і для загального доведення теореми Семереді: всі множини заданої щільності розбиваються на дві групи — «рівномірні» та «нерівномірні», причому під «рівномірністю» розуміється верхня оцінка на коефіцієнти Фур'є. Якщо множина рівномірна, то наявність прогресій у ній можна довести безпосередньо, а інакше можна довести наявність підпрогресії, в якій щільність множини більша, ніж серед відрізка натурального ряду, якому вона належить.

Метод дозволяє вивести оцінку ${\displaystyle N_{0}(\delta )\leqslant e^{e^{\frac {c}{\delta }}}}$. Технічні подробиці доведення, межа коефіцієнтів Фур'є, що визначає «рівномірність», і отримувані сталі можуть відрізнятися в різних джерелах.

Доведення теореми Рота можна вивести^[14] як окремий випадок теореми Семереді з доведення Семереді. Такий спосіб доведення вимагає використання леми регулярності Семереді та теореми про кутики, звідки теорема Рота випливає безпосередньо. Можна навіть обійтися без використання теореми про кутики, а виводити теорему Рота безпосередньо з леми про видалення трикутників але тільки у формулюванні для скінченних циклічних груп (див. розділ «Варіації та узагальнення на різні групи»).

Оскільки лема регулярності Семереді дає надзвичайно великі верхні оцінки на отримувану через неї величину (як мінімум, вежі з експонент), то й сам метод не дозволяє отримати оцінки кращі від цих.

Рональд Грем у своїй книзі про теорію Ремзі наводить спрощений варіант доведення, також заснований на методі Семереді, проте не використовує леми регулярності. У доведенні використовуються узагальнені арифметичні прогресії вигляду ${\displaystyle a+\sum \limits _{k=1}^{n}{\epsilon _{k}x_{k}}\ (\epsilon _{i}\in \left\lbrace {0,1}\right\rbrace )}$, довести наявність яких у множині значно простіше, а з цього вже виводиться сама теорема Рота.

Доведення Грема не дає оцінок на ${\displaystyle N}$, лише показує існування, оскільки використовує існування точки в послідовності, починаючи з якої всі точки досить близькі до границі, але для границі також доведено лише існування, а характер збіжності в принципі не аналізується.

Поряд із знаходженням верхніх оцінок розміру множини ${\displaystyle A\subset \left\lbrace {1,\dots ,N}\right\rbrace }$ без арифметичних прогресій, існує також обернена задача — побудова якомога більшої множини ${\displaystyle A}$, що не містить арифметичних прогресій, тобто контрприкладу для позначення меж покращення оцінок на ${\displaystyle N_{0}(\delta )}$. Усі відомі побудови таких множин ґрунтуються на ідеї розгляду окремих розрядів чисел у деякій системі числення та задання умов на значення цих розрядів.

Перший приклад множини без прогресій навели 1936 року Ердеш і Туран, запропонувавши розглянути числа, які в трійковій системі містять тільки цифри 0 і 2. Така множина містить лише ${\displaystyle N^{\log _{3}{2}}}$ чисел, що дуже мало, порівняно з верхніми оцінками^[15].

Доведення коректності побудови

Нехай ${\displaystyle A}$ — множина Ердеша — Турана.

Якщо ${\displaystyle a,b\in A}$ і ${\displaystyle a<b}$, то в трійковій системі в найстаршому розряді ${\displaystyle i}$, де ці числа відрізняються, виконуються рівності ${\displaystyle a_{i}=0,\ b_{i}=2}$. Тому в арифметичній прогресії ${\displaystyle a<c<b}$ виконувалося б ${\displaystyle c_{i}=1}$, а отже, ${\displaystyle c\not \in A}$.

Салем і Спенсер 1942 року узагальнили ідею Ердеша та Турана на системи числення зі зростанням (залежно від розміру множини) основи та отримали множину без прогресій розміру ${\displaystyle \exp \left({-O\left({\frac {\log N}{\log \log N}}\right)}\right)N}$^[16].

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

У побудові Ердеша — Турана цілком можна дозволити цифри 0 і 1 замість 0 і 2 (тоді в доведенні коректності місце середнього числа в прогресії буде займати більше). За аналогією з цим Салем і Спенсер у ${\displaystyle d}$-ковій системі розглядали числа, які містять тільки цифри від 0 до ${\displaystyle {\frac {d-1}{2}}}$, причому однакову кількість входжень кожної цифри (з поправкою на асимптотику ${\displaystyle d}$ можна вважати непарним, а загальне число цифр — дільником ${\displaystyle {\frac {d-1}{2}}}$).

Наявність прогресій блокується умовою входження окремих цифр. Справді, якщо ${\displaystyle a+c=2b}$ і при додаванні не використовується перенесення, то всі нулі в ${\displaystyle 2b}$ (а отже, і в ${\displaystyle b}$) можуть утворитися лише додаванням нулів із відповідних розрядів ${\displaystyle a}$ і ${\displaystyle c}$. Далі за індукцією можна довести збіг у ${\displaystyle a,b,c}$ позицій усіх одиниць, двійок і т. д. і прийти до висновку, що ${\displaystyle a=b=c}$.

Заявлена оцінка виходить при розгляді ${\displaystyle d\asymp {\frac {\log N}{(\log \log N)^{2}}}}$.

1946 року Беренд додав геометричну інтерпретацію, зіставивши розрядам числа координати точок у багатовимірному просторі і розглядаючи числа, відповідні в цьому сенсі точкам сфери. Це дозволило побудувати множину розміру ${\displaystyle \exp \left({-O\left({\sqrt {\log N}}\right)}\right)N}$, що не містить прогресій^[17].

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

Всі числа ${\displaystyle x<(2m+1)^{n}}$ з цифрами не більше ${\displaystyle m}$ і ${\displaystyle (2m+1)}$-ковим поданням ${\displaystyle x=x_{1}x_{2}\dots x_{n}}$ розбивають на групи з однаковими значеннями ${\displaystyle \sum \limits _{i=1}^{n}{x_{i}^{2}}}$. Як множину вибирають найбільшу з цих груп і її розмір оцінюється за принципом Діріхле.

Завдяки обмеженості цифр, при додаванні таких чисел не відбувається перенесення розрядів, так що прогресії довжини 3 також мають геометричну інтерпретацію (як точки на одній прямій). Але, оскільки куля --- строго опукле тіло, то сфера, як його межа, не може містити трьох точок на одній прямій. Із цього випливає відсутність прогресій у вибраній множині.

Розмір множини оцінюється найкраще при ${\displaystyle n\asymp {\sqrt {\log N}}}$

Згодом невеликим уточненням методу оцінку Беренда збільшено на логарифмічний множник^[18], але суттєво кращих результатів станом на 2019 рік немає.

Оскільки для деяких узагальнень теореми Рота відомі верхні оцінки схожого типу^[19][20], є підстави вважати, що оцінка Беренда точна.

І доведення через гармонічний аналіз, і певний спосіб застосування леми Семереді доводять не саму теорему, а її «циклічний» варіант.

Обіцяні цим формулюванням прогресії можуть бути прогресіями в ${\displaystyle {\mathbb {Z} }_{N}}$, але не бути такими в ${\displaystyle {\mathbb {N} }}$ (наприклад, ${\displaystyle (N-2,N-1,0)}$). Однак теорема Рота очевидно випливає з нього якщо розглянути множину ${\displaystyle \left\lbrace {N+a:a\in A}\right\rbrace }$ як множину лишків у ${\displaystyle \mathbb {Z} _{3N}}$. Це лише на сталу змінює щільність, але робить усі прогресії придатними для ${\displaystyle {\mathbb {N} }}$. Отже, ця теорема еквівалентна основній теоремі Рота.

Наступна теорема, подібна до теореми Рота, не випливає з неї і не тягне її, але цікава для окремого вивчення.

Вперше теорему для груп ${\displaystyle {\mathbb {F} }_{p}^{n}}$ довели 1982 року Браун і Бахлер^[21], проте вони тільки довели, що для множин без арифметичних прогресій виконується ${\displaystyle |A|=o(q^{n})}$, але точніші обмеження на ${\displaystyle |A|}$ залишалися відкритим питанням.

1993 року (опубліковано 1995 року) Рой Мешулам (Roy Meshulam) довів^[22], що ${\displaystyle |A|\leq 2{\frac {q^{n}}{n}}}$. У його доведенні розглянуто довільні групи та їхні характери. Існують також спрощені^[23] варіанти цього доведення виключно для ${\displaystyle {\mathbb {F} }_{p}^{n}}$, які, використовуючи коефіцієнти Фур'є в ${\displaystyle {\mathbb {F} }_{p}^{n}}$, прямо узагальнюють ідеї з аналітичного доведення теореми Рота. Доведення виходить технічно навіть простішим, ніж доведення самої теореми Рота, так що часто^[23][24] наводиться як перший приклад застосування методу.

2012 року Бейтман і Кац, розглядаючи випадок ${\displaystyle q=3}$, довели^[25] існування ${\displaystyle \epsilon >0}$ та абсолютної сталої ${\displaystyle C}$, такий, що для ${\displaystyle A\subset {\mathbb {F} }_{3}^{n}}$ без арифметичних прогресій виконується ${\displaystyle |A|\leq {\frac {3^{n}}{n^{1+\epsilon }}}}$.

2016 року Крут, Лев та Пах довели^[26] для випадку ${\displaystyle q=4}$, що ${\displaystyle |A|\leq {3.62}^{n}}$ для множин ${\displaystyle A\subset {\mathbb {F} }_{4}^{n}}$ без прогресії. Елленберг (Ellenberg) і Гейсвейт (Gijswijt), узагальнюючи метод Крута, Льова і Паха, використовуючи алгебру многочленів, довели^[27][28] існування для кожного простого ${\displaystyle q\geq 3}$ сталої ${\displaystyle c=c(q)<q}$ такої, що ${\displaystyle |A|=O(c^{n})}$ якщо ${\displaystyle A\subset {\mathbb {F} }_{q}^{n}}$ не містить прогресії довжини 3. У їхній роботі ${\displaystyle c(q)={\frac {q}{exp({\sup \limits _{\theta }\left\lbrace {{\frac {q-1}{3}}\theta +\ln {\frac {e^{q\theta }-1}{q(e^{\theta }-1)}}}\right\rbrace })}}}$. Зокрема, для випадку ${\displaystyle q=3}$ виконується ${\displaystyle |A|=o(2.756^{n})}$. За припущення ${\displaystyle \theta ={\frac {c_{0}}{q}}}$ з оптимізації функції ${\displaystyle {\frac {c}{3}}-\ln {\frac {e^{c}-1}{c}}}$ випливає, що ${\displaystyle c(q)\sim {\frac {e^{c_{0}}-1}{c_{0}e^{(c_{0}/3)}}}q}$, де ${\displaystyle c_{0}}$ — абсолютна стала, що є розв'язком рівняння ${\displaystyle 2ce^{c}-3e^{c}+c+3=0}$, тобто ${\displaystyle c(q)\sim c_{1}q}$, де ${\displaystyle c_{1}\approx 0.841434...}$

Найкраща^[27] станом на 2016 побудова-контрприклад дозволяє^[29] будувати для груп виду ${\displaystyle {\mathbb {F} }_{3}^{n}}$ множини розміру ${\displaystyle \Omega (2.2^{n})}$, які не містять арифметичних прогресій довжини 3.

У роботі Мешулама розглянуто^[22] теорему Рота для довільної групи ${\displaystyle G={\mathbb {Z} }_{k_{1}}\oplus \dots \oplus {\mathbb {Z} }_{k_{n}}}$ та виведено оцінку ${\displaystyle |A|<2{\frac {|G|}{n}}}$ для множини без арифметичних прогресій довжини 3.

З цього випливає існування абсолютної сталої ${\displaystyle \beta >0}$ такої, що для множини ${\displaystyle A\subset G}$ без прогресій виконується ${\displaystyle |A|<{\frac {|G|}{(\log {|G|})^{\beta }}}}$.

Класичним узагальненням теореми Рота для двовимірних множин ${\displaystyle A\subset \left\lbrace {1,\dots ,N}\right\rbrace \times \left\lbrace {1,\dots ,N}\right\rbrace }$ вважають теорему про кутики. Хоча там і не згадано про арифметичні прогресії (у двовимірному сенсі), але теорема Рота з неї випливає.

• Теорема ван дер Вардена

• K. F. Roth. On Certain Sets of Integers // Journal of the London Mathematical Society. — 1953. — P. 104—109. — DOI:10.1112/jlms/s1-28.1.104.
• D. R. Heath-Brown. Integer Sets Containing No Arithmetic Progressions // Journal of the London Mathematical Society. — 1987. — Vol. s2-35, iss. 3. — P. 385—394. — DOI:10.1112/jlms/s2-35.3.385.
• E. Szemerédi. Integer sets containing no arithmetic progressions // Acta Mathematica Hungarica. — 1990. — Vol. 56. — P. 155—159. — DOI:10.1007/BF01903717.
• J. Bourgain. On Triples in Arithmetic Progression // Geometric & Functional Analysis GAFA. — 1999. — Vol. 9. — P. 968—984. — DOI:10.1007/s000390050105.
• J. Bourgain. Roth’s theorem on progressions revisited // Journal d'Analyse Mathématique. — 2008. — Vol. 104. — P. 155—192. — DOI:10.1007/s11854-008-0020-x.
• T. Sanders. On certain other sets of integers // Journal d’Analyse Mathématique. — 2012. — Vol. 116. — P. 53—82. — arXiv:1007.5444. — DOI:10.1007/s11854-012-0003-9.
• T. Sanders. On Roth’s theorem on progressions // Annals of Mathematics. — 2011. — Vol. 174. — P. 619—636. — arXiv:1011.0104. — DOI:10.4007/annals.2011.174.1.20.
• T. F. Bloom. A quantitative improvement for Roth's theorem on arithmetic progressions // Journal of the London Mathematical Society. — 2014. — Vol. 93, iss. 3. — P. 643—663. — arXiv:1405.5800. — DOI:10.1112/jlms/jdw010.
• T. Schoen. Improved bound in Roth’s theorem on arithmetic progressions. — 2020. — arXiv:2005.01145.
• T. F. Bloom, O. Sisask. Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions. — 2020. — arXiv:2007.03528.