Теорема Рота

Шаблон:Не плутати Теорема Рота — результат адитивної комбінаторики, окремий випадок теореми Семереді для прогресій довжини 3; стверджує наявність арифметичних прогресій $(a,a+d,a+2d),d=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\{1,2,\dots ,N\right\}$ і $|A|>\delta N$, то $A$ містить арифметичну прогресію довжини 3. У переважній більшості доведень доводиться саме формулювання для скінченних множин.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Беренд (1946)

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

Згодом невеликим уточненням методу оцінку Беренда збільшено на логарифмічний множник, але суттєво кращих результатів станом на 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=0$, де під додаванням розуміють саме додавання за модулем. Шаблон:/рамкаОбіцяні цим формулюванням прогресії можуть бути прогресіями в ${\mathbb{Z}}_N$, але не бути такими в $\mathbb{N}$ (наприклад, $(N-2,N-1,0)$). Однак теорема Рота очевидно випливає з нього якщо розглянути множину $\left\{N+a:a\in A\right\}$ як множину лишків у ${\mathbb{Z}}_{3N}$. Це лише на сталу змінює щільність, але робить усі прогресії придатними для $\mathbb{N}$. Отже, ця теорема еквівалентна основній теоремі Рота.

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

Наступна теорема, подібна до теореми Рота, не випливає з неї і не тягне її, але цікава для окремого вивчення.Шаблон:Рамка Нехай зафіксовано деяке $q\ge 3$. Тоді для будь-якого $\delta \in (0;1)$ існує таке $n_0=n_0(\delta ,q)$, що якщо $n>n_0,A\subset {𝔽}_q^n,|A|>\delta q^n$, то $\mathrm{\exists }a,d(d=(0,\dots ,0)):a,a+d,a+2d\in A$ Шаблон:/рамка

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

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

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

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

2016 року Крут, Лев та Пах довели для випадку $q=4$, що $|A|\le {3.62}^n$ для множин $A\subset {𝔽}_4^n$ без прогресії. Елленберг (Ellenberg) і Гейсвейт (Gijswijt), узагальнюючи метод Крута, Льова і Паха, використовуючи алгебру многочленів, довели існування для кожного простого $q\ge 3$ сталої $c=c(q)<q$ такої, що $|A|=O(c^n)$ якщо $A\subset {𝔽}_q^n$ не містить прогресії довжини 3. У їхній роботі $c(q)=\frac{q}{exp(\sup {\mathrm{\backslash limits}}_{\theta }\left\{\frac{q-1}{3}\theta +\ln \frac{e^{q\theta }-1}{q(e^{\theta }-1)}\right\})}$. Зокрема, для випадку $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$ — абсолютна стала, що є розв'язком рівняння $2c{e}^c-3e^c+c+3=0$, тобто $c(q)\sim c_{1}q$, де $c_1\approx 0.841434...$

Нижні оцінки

Найкраща Шаблон:Станом на побудова-контрприклад дозволяє будувати для груп виду ${𝔽}_3^n$ множини розміру $\mathrm{\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\{1,\dots ,N\right\}\times \left\{1,\dots ,N\right\}$ вважають теорему про кутики. Хоча там і не згадано про арифметичні прогресії (у двовимірному сенсі), але теорема Рота з неї випливає.

Див. також

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

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття