Не плутати з теоремою Туе Зігеля Рота Теорема Рота результат адитивної комбінаторики окремий випадок теореми Семереді дл

Не плутати з (теоремою_Туе_—_Зігеля_—_Рота).

Теорема Рота — результат адитивної комбінаторики, окремий випадок теореми Семереді для прогресій довжини 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$	^[en]
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)}}}$	^[en]
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$	^[pl]
2020 (препринт)	${\frac {N}{(\log N)^{1+c}}},\ c>0$	Блум, Сісаск

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

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

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

Метод дозволяє вивести оцінку $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 року ^[en] додав геометричну інтерпретацію, зіставивши розрядам числа координати точок у багатовимірному просторі і розглядаючи числа, відповідні в цьому сенсі точкам сфери. Це дозволило побудувати множину розміру $\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$ вважають теорему про кутики. Хоча там і не згадано про арифметичні прогресії (у двовимірному сенсі), але теорема Рота з неї випливає.

Див. також

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

Примітки

И. Д. Шкредов, «Теорема Семереди и задачи об арифметических прогрессиях», УМН, 61:6(372) (2006), 111—178; Russian Math. Surveys, 61:6 (2006), 1101—1166. оригіналу за 24 грудня 2017. Процитовано 23 грудня 2017.
Roth, 1953.
Heath-Brown, 1987.
Szemerédi, 1990.
Bourgain, 1999.
Bourgain, 2008.
Sanders, 2012.
Sanders, 2011.
Bloom, 2014.
Schoen, 2020.
Bloom, Sisask, 2020.
(PDF). Архів оригіналу (PDF) за 24 грудня 2017. Процитовано 23 грудня 2017.
Постнаука, Илья Шкредов — Теорема Семереди
Лаборатория Чебышёва, курс лекций «Аддитивная комбинаторика», лекция 3
P. Erdős, P. Turán, "On some sequences of integers", Journal of the London Mathematical Society (June 1936). оригіналу за 23 грудня 2019. Процитовано 23 грудня 2019.
R. Salem, D. C. Spencer, Proc. Natl. Acad. Sci. USA, 28 (1942), 561—563. оригіналу за 3 червня 2018. Процитовано 23 грудня 2017.
F. A. Behrend, «On sets of integers which contain no three terms in arithmetic progression», Proc. Natl. Acad. Sci. USA, 32 (1946), 331—332. оригіналу за 4 червня 2018. Процитовано 23 грудня 2017.
Michael Elkin, "An improved construction of progression-free sets", Israel Journal of Mathematics, 184:93 (August 2011). оригіналу за 27 листопада 2018. Процитовано 23 грудня 2019.
T. Schoen, I. D. Shkredov, «Roth's theorem in many variables», Israel Journal of Mathematics, volume 199, pages 287—308 (2014) [ 2023-08-30 у Wayback Machine.] (arXiv:1106.1601 Архівна копія на сайті Wayback Machine.)
T. Schoen, O. Sisask, «Roth's theorem for four variables and additive structures in sums of sparse sets», Forum of Mathematics Forum of Mathematics, Sigma, 4, E5. doi:10.1017/fms.2016.2 [ 2023-08-29 у Wayback Machine.] (arXiv:1408.2568 Архівна копія на сайті Wayback Machine.)
T. C. Brown and J. P. Buhler, A density version of a geometric Ramsey theorem, Journal of Combinatorial Theory, Series A 32 (1982), no. 1, 20—34 (PDF). (PDF) оригіналу за 9 серпня 2017. Процитовано 23 грудня 2017.
R. Meshulam, On subsets of finite abelian groups with no 3-term arithmetic progressions, Journal of Combinatorial Theory, Series A 71 (1995), no. 1, 168—172.^{[недоступне посилання з Февраль 2020]}
A mini course on additive combinatorics [ 2017-08-29 у Wayback Machine.], p. 39-42
Лаборатория Чебышёва, Илья Шкредов, Аналитические методы в аддитивной комбинаторике, обзорная лекция
M. Bateman and N. Katz, New bounds on cap sets, Journal of the American Mathematical Society 25 (2012), no. 2, 585—613 (PDF). (PDF) оригіналу за 9 січня 2018. Процитовано 23 грудня 2017.
E. Croot, V. Lev, and P. P. Pach, Progression-free sets in Z_n^4 are exponentially small (2016). arXiv preprint 1605.01506. оригіналу за 12 червня 2018. Процитовано 23 грудня 2017.
Доказательство теоремы Рота для групп с малым кручением на arxiv.org. оригіналу за 12 червня 2018. Процитовано 23 грудня 2017.
Изложение доказательства Ellenberg и Gijswijt на русском языке
Y. Edel, Extensions of generalized product caps, Designs, Codes and Cryptography 31 (2004), no. 1, 5—14. оригіналу за 10 січня 2018. Процитовано 23 грудня 2017.

Література

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.

[Shkredov-1] И. Д. Шкредов, «Теорема Семереди и задачи об арифметических прогрессиях», УМН, 61:6(372) (2006), 111—178; Russian Math. Surveys, 61:6 (2006), 1101—1166. оригіналу за 24 грудня 2017. Процитовано 23 грудня 2017.

[FOOTNOTERoth1953-2] Roth, 1953.

[FOOTNOTEHeath-Brown1987-3] Heath-Brown, 1987.

[FOOTNOTESzemerédi1990-4] Szemerédi, 1990.

[FOOTNOTEBourgain1999-5] Bourgain, 1999.

[FOOTNOTEBourgain2008-6] Bourgain, 2008.

[FOOTNOTESanders2012-7] Sanders, 2012.

[FOOTNOTESanders2011-8] Sanders, 2011.

[FOOTNOTEBloom2014-9] Bloom, 2014.

[FOOTNOTESchoen2020-10] Schoen, 2020.

[FOOTNOTEBloom,_Sisask2020-11] Bloom, Sisask, 2020.

[12] (PDF). Архів оригіналу (PDF) за 24 грудня 2017. Процитовано 23 грудня 2017.

[13] Постнаука, Илья Шкредов — Теорема Семереди

[14] Лаборатория Чебышёва, курс лекций «Аддитивная комбинаторика», лекция 3

[15] P. Erdős, P. Turán, "On some sequences of integers", Journal of the London Mathematical Society (June 1936). оригіналу за 23 грудня 2019. Процитовано 23 грудня 2019.

[16] R. Salem, D. C. Spencer, Proc. Natl. Acad. Sci. USA, 28 (1942), 561—563. оригіналу за 3 червня 2018. Процитовано 23 грудня 2017.

[17] F. A. Behrend, «On sets of integers which contain no three terms in arithmetic progression», Proc. Natl. Acad. Sci. USA, 32 (1946), 331—332. оригіналу за 4 червня 2018. Процитовано 23 грудня 2017.

[18] Michael Elkin, "An improved construction of progression-free sets", Israel Journal of Mathematics, 184:93 (August 2011). оригіналу за 27 листопада 2018. Процитовано 23 грудня 2019.

[19] T. Schoen, I. D. Shkredov, «Roth's theorem in many variables», Israel Journal of Mathematics, volume 199, pages 287—308 (2014) [ 2023-08-30 у Wayback Machine.] (arXiv:1106.1601 Архівна копія на сайті Wayback Machine.)

[20] T. Schoen, O. Sisask, «Roth's theorem for four variables and additive structures in sums of sparse sets», Forum of Mathematics Forum of Mathematics, Sigma, 4, E5. doi:10.1017/fms.2016.2 [ 2023-08-29 у Wayback Machine.] (arXiv:1408.2568 Архівна копія на сайті Wayback Machine.)

[21] T. C. Brown and J. P. Buhler, A density version of a geometric Ramsey theorem, Journal of Combinatorial Theory, Series A 32 (1982), no. 1, 20—34 (PDF). (PDF) оригіналу за 9 серпня 2017. Процитовано 23 грудня 2017.

[Meshulam-22] R. Meshulam, On subsets of finite abelian groups with no 3-term arithmetic progressions, Journal of Combinatorial Theory, Series A 71 (1995), no. 1, 168—172.^{[недоступне посилання з Февраль 2020]}

[f_p^n_minicourse-23] A mini course on additive combinatorics [ 2017-08-29 у Wayback Machine.], p. 39-42

[24] Лаборатория Чебышёва, Илья Шкредов, Аналитические методы в аддитивной комбинаторике, обзорная лекция

[25] M. Bateman and N. Katz, New bounds on cap sets, Journal of the American Mathematical Society 25 (2012), no. 2, 585—613 (PDF). (PDF) оригіналу за 9 січня 2018. Процитовано 23 грудня 2017.

[26] E. Croot, V. Lev, and P. P. Pach, Progression-free sets in Z_n^4 are exponentially small (2016). arXiv preprint 1605.01506. оригіналу за 12 червня 2018. Процитовано 23 грудня 2017.

[f_p_n_best-27] Доказательство теоремы Рота для групп с малым кручением на arxiv.org. оригіналу за 12 червня 2018. Процитовано 23 грудня 2017.

[28] Изложение доказательства Ellenberg и Gijswijt на русском языке

[29] Y. Edel, Extensions of generalized product caps, Designs, Codes and Cryptography 31 (2004), no. 1, 5—14. оригіналу за 10 січня 2018. Процитовано 23 грудня 2017.