Теорема Рота

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

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

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

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

Історія покращення кількісних оцінок

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

Різні доведення

Елементарне (через узагальнені арифметичні прогресії)

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

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

Комбінаторне (через лему Семереді)

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

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

Гармонічний аналіз

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

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

Контрприклади для нещільних множин

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

Ердеш, Туран (1936)

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

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

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

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

Салем, Спенсер (1942)

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

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

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

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

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

Беренд (1946)

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

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

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

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

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

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

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

Варіації та узагальнення для різних груп

Для скінченних циклічних груп

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

Для будь-якого $\delta \in (0;1)$ існує $N_{0}=N_{0}(\delta )$ таке, що якщо $N>N_{0}$, $A\subset \mathbb {Z} _{N}$ і $|A|>\delta N$, то $A$ містить трійку $(a,a+d,a+2d),\ d\not =0$, де під додаванням розуміють саме додавання за модулем.

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

Для груп з малим фіксованим скрутом

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

Нехай зафіксовано деяке $q\geq 3$. Тоді для будь-якого $\delta \in (0;1)$ існує таке $n_{0}=n_{0}(\delta ,q)$, що якщо $n>n_{0},\ A\subset {\mathbb {F} }_{q}^{n},\ |A|>\delta q^{n}$, то $\exists a,d(d\not =(0,\dots ,0)):a,a+d,a+2d\in A$

Верхні оцінки

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

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

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

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

Нижні оцінки

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

Для довільних груп

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

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

Двовимірне узагальнення

Класичним узагальненням теореми Рота для двовимірних множин $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.