Просмотр кода страницы Теорема Рота

{{see also|Теорема Туэ — Зигеля — Рота}}
'''Теорема Рота''' — результат [[Аддитивная комбинаторика|аддитивной комбинаторики]], частный случай [[Теорема Семереди|теоремы Семереди]] для прогрессий длины 3; утверждает присутствие арифметических прогрессий <math>(a,a+d,a+2d),\ d \not = 0</math> в любых достаточно плотных множествах.

Точная формулировка: для любого <math>\delta \in (0;1)</math> любое множество <math>A \subset {\mathbb N}</math>, имеющее [[Асимптотическая плотность|асимптотическую плотность]] <math>d(A)>\delta</math>, содержит [[Арифметическая прогрессия|арифметическую прогрессию длины]] 3. 

Аналогичные формулировки, использующие верхнюю и нижнюю асимптотическую плотность, [[Тогда и только тогда|эквивалентны]]<ref name="Shkredov">{{Cite web |url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=5293 |title=И. Д. Шкредов, «Теорема Семереди и задачи об арифметических прогрессиях», УМН, 61:6(372) (2006), 111—178; Russian Math. Surveys, 61:6 (2006), 1101—1166  |access-date=2017-12-23 |archive-date=2017-12-24 |archive-url=https://web.archive.org/web/20171224213855/http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=5293 |deadlink=no }}</ref>.

Также эквивалентна исходной и формулировка для конечных множеств: для любого <math>\delta \in (0;1)</math> существует <math>N_0 = N_0(\delta)</math> такое, что если <math>N > N_0</math>, <math>A \subset \left\lbrace{1,2,\dots,N}\right\rbrace</math> и <math>|A| > \delta N</math>, то <math>A</math> содержит арифметическую прогрессию длины 3. Подавляющее большинство доказательств доказывает именно формулировку для конечных множеств.

== История улучшения количественных оценок ==
{{якорь|верхние_оценки}}

{| class="wikitable"
! colspan="3" | Размер максимального подмножества
<math>\{ 1, \dots, N \}</math>
без прогрессий длины 3
|-
! Год публикации !! Размер<br>(с точностью до константы) !! Автор(ы)
|- align="center"
| 1953
| <math>\frac{N}{\log \log N}</math>
| [[Рот, Клаус Фридрих|Рот]]{{sfn|Roth|1953}}
|- align="center"
| 1987
| <math>\frac{N}{(\log N)^c},\ c>0</math>
| {{iw|Роджер Хиз-Браун|Хиз-Браун|en|Roger Heath-Brown}}{{sfn|Heath-Brown|1987}}{{sfn|Szemerédi|1990}}
|- align="center"
| 1999
| <math>\frac{N (\log \log N)^{1/2}}{(\log N)^{1/2}}</math>
| [[Бургейн, Жан|Бургейн]]{{sfn|Bourgain|1999}}
|- align="center"
| 2008
| <math>\frac{N (\log \log N)^2}{(\log N)^{2/3}}</math>
| Бургейн{{sfn|Bourgain|2008}}
|- align="center"
| 2012
| <math>\frac{N}{(\log N)^{3/4-o(1)}}</math>
| {{iw|Том Сандерс (математик)|Сандерс|en|Tom Sanders (mathematician)}}{{sfn|Sanders|2012}}
|- align="center"
| 2011
| <math>\frac{(\log \log N)^5}{\log N} N</math>
| Сандерс{{sfn|Sanders|2011}}
|- align="center"
| 2014
| <math>\frac{(\log \log N)^4}{\log N} N</math>
| Блум{{sfn|Bloom|2014}}
|- align="center"
| 2020 (препринт)
| <math>\frac{(\log \log N)^3 (\log \log \log N)^5}{\log N} N</math>
| {{iw|Шоен, Томас|Шоен|pl|Tomasz Schoen (matematyk)}}{{sfn|Schoen|2020}}
|- align="center"
| 2020 (препринт)
| <math>\frac{N}{(\log N)^{1+c}},\ c > 0</math>
| Блум, Сисаск{{sfn|Bloom, Sisask|2020}}
|}

== Различные доказательства ==

=== Гармонический анализ ===
Теорема была впервые доказана в [[1953 год в науке|1953 году]] Клаусом Ротом{{sfn|Roth|1953}}<ref>{{Cite web |url=http://www.chebyshev.spbu.ru/userfiles/file/vsn201014.pdf |title=Доказательство Рота в изложении Харольда Хельфготта на русском языке |accessdate=2017-12-23 |archiveurl=https://web.archive.org/web/20171224213703/http://www.chebyshev.spbu.ru/userfiles/file/vsn201014.pdf |archivedate=2017-12-24 |deadlink=yes }}</ref> путём адаптации кругового метода Харди — Литтлвуда. Доказательство использовало идею<ref>[https://www.youtube.com/watch?v=BE0MvR7NJVg&feature=youtu.be&t=415 Постнаука, Илья Шкредов — Теорема Семереди]</ref>, впоследствии обобщённую и для общего доказательства теоремы Семереди: все множества заданной плотности разбиваться на две группы — «равномерные» и «неравномерные», причём под «равномерностью» понимается верхняя оценка на [[Дискретное преобразование Фурье над конечным полем|коэффициенты Фурье]]. Если множество равномерно, то наличие прогрессий в нём можно доказать напрямую, а иначе можно доказать наличие подпрогрессии, в которой плотность множества больше чем среди отрезка натурального ряда, к которому оно принадлежит.

Метод позволяет вывести оценку <math>N_0(\delta) \leqslant e^{e^{\frac{c}{\delta}}}</math>. Технические подробности доказательства, граница коэффициентов Фурье, определяющая «равномерность», и получаемые константы могут отличаться в разных источниках.

=== Комбинаторное (через лемму Семереди) ===
Доказательство теоремы Рота можно вывести<ref>[https://www.youtube.com/watch?v=SaFBAlG5FMY&list=PL-_cKNuVAYAU3OswJP0-lBnNAPs0MlMej&index=3 Лаборатория Чебышёва, курс лекций «Аддитивная комбинаторика», лекция 3]</ref> как частный случай теоремы Семереди из доказательства Семереди. Такой способ доказательства требует использования [[Лемма регулярности Семереди|леммы регулярности Семереди]] и [[Теорема об уголках|теоремы об уголках]], откуда теорема Рота следует напрямую. Возможно<ref>[http://www.math.cmu.edu/~af1p/Teaching/AdditiveCombinatorics/allnotes.pdf A mini course on additive combinatorics] {{Wayback|url=http://www.math.cmu.edu/~af1p/Teaching/AdditiveCombinatorics/allnotes.pdf |date=20170829160603 }}, p. 6</ref> даже обойтись без использования теоремы об уголках, а выводить теорему Рота напрямую из [[Лемма об удалении треугольников|леммы об удалении треугольников]], но только в формулировке для конечных циклических групп (см. раздел «Обобщения на различные группы»).

Поскольку лемма регулярности Семереди даёт чрезвычайно большие верхние оценки на получаемую через неё величину (как минимум, [[Тетрация|башни из экспонент]]), то и сам метод не позволяет получить оценки лучше этих.

=== Элементарное (через обобщённые арифметические прогрессии) ===
[[Роналд Грэхем]] в своей книге о [[Теория Рамсея|теории Рамсея]] приводит упрощённый вариант доказательства, также основанный на методе Семереди, однако не использующий лемму регулярности. В доказательстве используются [[Обобщённая арифметическая прогрессия|обобщённые арифметические прогрессии]] вида <math>a+\sum \limits_{k=1}^{n} {\epsilon_k x_k}\ (\epsilon_i \in \left\lbrace{0,1}\right\rbrace)</math>, доказать присутствие которых во множестве намного более просто, а из этого уже выводится сама теорема Рота.

Доказательство Грэхема не даёт оценок на <math>N</math>, а только показывает существование, поскольку использует существование точки в последовательности, начиная с которой все точки достаточно близки к [[Предел (математика)|пределу]], но для предела также доказано только существование, а характер сходимости в принципе не анализируется.

== Контрпримеры для неплотных множеств ==
Наряду с нахождением верхних оценок размера множества <math>A \subset \left\lbrace{1, \dots, N}\right\rbrace</math> без арифметических прогрессий, существует также обратная задача — конструирование как можно большего множества <math>A</math>, не содержащего арифметических прогрессий, то есть контрпримера для обозначения границ улучшаемости оценок на <math>N_0(\delta)</math>. Все известные конструкции таких множеств основываются на идее рассмотрения отдельных разрядов чисел в некоторой системе счисления и задания условий на значения этих разрядов.

=== Эрдёш, Туран (1936) ===
Первый пример множества без прогрессий привели в 1936 году Эрдёш и Туран, предложив рассмотреть числа, которые в троичной системе содержат только цифры 0 и 2. Такое множество содержит всего лишь <math>N^{\log_3 {2}}</math> чисел, что очень мало по сравнению с верхними оценками.<ref>{{Cite web |url=https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms/s1-11.4.261 |title=P. Erdős, P. Turán, "On some sequences of integers", Journal of the London Mathematical Society (June 1936) |access-date=2019-12-23 |archive-date=2019-12-23 |archive-url=https://web.archive.org/web/20191223144612/https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms/s1-11.4.261 |deadlink=no }}</ref>

{{Hider|
  title = Доказательство корректности конструкции|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
Пусть <math>A</math> --- множество Эрдёша--Турана.

Если <math>a,b \in A</math> и <math>a<b</math>, то в троичной системе в самом старшем [[Числовой разряд|разряде]] <math>i</math>, где различны эти числа выполняются равенства <math>a_i=0,\ b_i=2</math>. Поэтому в арифметической прогрессии <math>a < c < b</math> выполнялось бы <math>c_i=1</math>, а значит, <math>c \not \in A</math>.
}}

=== Салем, Спенсер (1942) ===
Салем и Спенсер в 1942 году обобщили идею Эрдёша и Турана на системы счисления с растущим (зависящим от размера множества) основанием и получили множество без прогрессий размера <math>\exp\left({-O \left( { \frac{\log N}{\log \log N} } \right)}\right) N</math>.<ref>{{Cite web |url=http://www.pnas.org/content/28/12/561 |title=R. Salem, D. C. Spencer, Proc. Natl. Acad. Sci. USA, 28 (1942), 561—563 |access-date=2017-12-23 |archive-date=2018-06-03 |archive-url=https://web.archive.org/web/20180603050631/http://www.pnas.org/content/28/12/561 |deadlink=no }}</ref>

{{Hider|
  title = Краткое описание конструкции|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
В конструкции Эрдёша--Турана вполне можно разрешать цифры 0 и 1 вместо 0 и 2 (тогда в доказательстве корректности место среднего числа в прогрессии будет занимать большее). По аналогии с этим Салем и Спенсер в <math>d</math>-ичной системе рассматривали числа, содержащие только цифры от 0 до <math>\frac{d-1}{2}</math>, причём равное количество вхождений каждой цифры (с поправкой на [[Асимптотика|асимптотику]] <math>d</math> можно считать нечётным, а общее число цифр --- делящим <math>\frac{d-1}{2}</math>).

Наличие прогрессий блокируется условием на вхождения отдельных цифр. Действительно, если <math>a+c=2b</math> и при сложении не используется [[Перенос (арифметика)|перенос]], то все нули в <math>2b</math> (а значит, и в <math>b</math>) могут быть образованы только сложением нулей из соответствующих разрядов <math>a</math> и <math>c</math>. Далее по индукции можно доказать совпадение у <math>a,b,c</math> позиций всех единиц, двоек и т. д. и прийти к выводу, что <math>a=b=c</math>.

Заявленная оценка получается при рассмотрении <math>d \asymp \frac{\log N}{(\log \log N)^2}</math>.
}}

=== Беренд (1946) ===
В 1946 году {{iw|Феликс Беренд|Беренд|en|Felix Behrend}} добавил геометрическую интерпретацию, сопоставив разрядам числа координаты точек в многомерном пространстве и рассматривая числа, соответствующие в этом смысле точкам [[Сфера|сферы]]. Это позволило построить не содержащее прогрессий множество размера <math>\exp\left({ -O\left({\sqrt{\log N}}\right) }\right) N</math>.<ref>{{Cite web |url=http://www.pnas.org/content/32/12/331 |title=F. A. Behrend, «On sets of integers which contain no three terms in arithmetic progression», Proc. Natl. Acad. Sci. USA, 32 (1946), 331—332. |access-date=2017-12-23 |archive-date=2018-06-04 |archive-url=https://web.archive.org/web/20180604022013/http://www.pnas.org/content/32/12/331 |deadlink=no }}</ref>

{{Hider|
  title = Краткое описание конструкции|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
Все числа <math>x < (2m+1)^n</math> с цифрами не больше <math>m</math> и <math>(2m+1)</math>-ричным представление <math>x = x_1 x_2 \dots x_n</math> разбиваются на группы с одинаковыми значениями <math>\sum \limits_{i=1}^{n} {x_i^2}</math>. В качестве множества выбирается наибольшая из этих групп и её размер оценивается по [[Принцип Дирихле (комбинаторика)|принципу Дирихле]].

Благодаря ограниченности цифр, при сложении таких чисел не происходит [[Перенос (арифметика)|перенос разрядов]], так что прогрессии длины 3 также имеют геометрическую интерпретацию (как точки на одной прямой). Но, поскольку шар --- строго [[Выпуклое множество|выпуклое тело]], то сфера, как его граница, не может содержать трёх точек на одной прямой. Из этого следует отсутствие прогрессий в выбранном множестве.

Размер множество оценивается лучше всего при <math>n \asymp \sqrt{\log N}</math>
}}

Впоследствии оценка Беренда была увеличена на логарифмический множитель небольшим уточнением метода<ref>{{Cite web |url=https://link.springer.com/article/10.1007/s11856-011-0061-1 |title=Michael Elkin, "An improved construction of progression-free sets", Israel Journal of Mathematics, 184:93 (August 2011) |access-date=2019-12-23 |archive-date=2018-11-27 |archive-url=https://web.archive.org/web/20181127182540/https://link.springer.com/article/10.1007/s11856-011-0061-1 |deadlink=no }}</ref>, но существенно лучших результатов по состоянию 2019 год нет.

Поскольку для некоторых обобщений теоремы Рота известны ''верхние'' оценки похожего типа<ref>[https://link.springer.com/article/10.1007/s11856-013-0049-0 T. Schoen, I. D. Shkredov, «Roth’s theorem in many variables», Israel Journal of Mathematics, volume 199, pages 287—308 (2014)] {{Wayback|url=https://link.springer.com/article/10.1007/s11856-013-0049-0 |date=20191223144612 }} ([https://arxiv.org/abs/1106.1601 arXiv:1106.1601] {{Wayback|url=https://arxiv.org/abs/1106.1601 |date=20191223144613 }})</ref><ref>[https://www.cambridge.org/core/journals/forum-of-mathematics-sigma/article/roths-theorem-for-four-variables-and-additive-structures-in-sums-of-sparse-sets/7FF78FC00DA78FF8EAB301A1E4A30144 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] {{Wayback|url=https://www.cambridge.org/core/journals/forum-of-mathematics-sigma/article/roths-theorem-for-four-variables-and-additive-structures-in-sums-of-sparse-sets/7FF78FC00DA78FF8EAB301A1E4A30144 |date=20200501014913 }} ([https://arxiv.org/abs/1408.2568 arXiv:1408.2568] {{Wayback|url=https://arxiv.org/abs/1408.2568 |date=20191223144609 }})</ref>, есть основания полагать, что оценка Беренда точна.

== Вариации и обобщения для различных групп ==

=== Для конечных циклических групп ===
И доказательство через гармонический анализ, и определённый способ применения леммы Семереди доказывают не саму теорему, а её «циклический» вариант.
{{рамка}}
Для любого <math>\delta \in (0;1)</math> существует <math>N_0 = N_0(\delta)</math> такое, что если <math>N > N_0</math>, <math>A \subset \Z_N</math> и <math>|A| > \delta N</math>, то <math>A</math> содержит тройку <math>(a,a+d,a+2d),\ d \not = 0</math>, где под сложением понимается именно [[Сравнение по модулю#Операции со сравнениями|сложение по модулю]]
{{конец рамки}}
Обещаемые данной формулировкой прогрессии могут быть прогрессиями в <math>{\Z}_N</math>, но не быть таковыми в <math>{\N}</math> (например, <math>(N-2,N-1,0)</math>).
Однако теорема Рота очевидным образом следует из неё если рассмотреть множество <math>\left\lbrace{N+a : a \in A}\right\rbrace</math> как множество вычетов в <math>\Z_{3N}</math>. Это лишь на константу меняет плотность, но делает все прогрессии подходящими для <math>{\N}</math>. Следовательно, эта теорема эквивалентна основной теореме Рота.

{{якорь|Обобщения для групп с малым фиксированным кручением}}

=== Для групп с малым фиксированным кручением ===
Следующая теорема, сходная по идее с теоремой Рота, не следует из неё и не влечет её, но представляет интерес для отдельного изучения.
{{рамка}}
Пусть фиксированно некоторое <math>q \ge 3</math>. Тогда для любого <math>\delta \in (0;1)</math> существует такое <math>n_0=n_0(\delta, q)</math>, что если <math>n>n_0,\ A \subset {\mathbb F}_{q}^{n},\ |A|>\delta q^n</math>, то <math>\exists a,d (d \not = (0,\dots,0)): a,a+d,a+2d \in A</math>
{{конец рамки}}

==== Верхние оценки ====
Впервые теорема для групп <math>{\mathbb F}_p^n</math> была доказана доказана Брауном и Бахлером в 1982 году<ref>{{Cite web |url=http://people.math.sfu.ca/~vjungic/tbrown/tom-51.pdf |title=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. |access-date=2017-12-23 |archive-date=2017-08-09 |archive-url=https://web.archive.org/web/20170809042902/http://people.math.sfu.ca/~vjungic/tbrown/tom-51.pdf |deadlink=no }}</ref>, однако они только доказали, что для множеств без арифметических прогрессий выполняется <math>|A| = o(q^n)</math>, но более точные ограничения на <math>|A|</math> оставались открытым вопросом.

В 1993 году (опубликовано в 1995) Рой Мешулам (Roy Meshulam) доказал<ref name="Meshulam">[https://ac.els-cdn.com/0097316595900241/1-s2.0-0097316595900241-main.pdf?_tid=3dcedab4-e7b1-11e7-a9fc-00000aab0f6c&acdnat=1514013589_9ce279418d6a64240df20581b322e980 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.]{{Недоступная ссылка|date=Февраль 2020 |bot=InternetArchiveBot }}</ref>, что <math>|A| \le 2\frac{q^n}{n}</math>. Его доказательство рассматривало произвольные группы и их [[Характер (теория групп)#Характеры в U(1)|характеры]]. Существуют также более упрощённые<ref name="f_p^n_minicourse">[http://www.math.cmu.edu/~af1p/Teaching/AdditiveCombinatorics/allnotes.pdf A mini course on additive combinatorics] {{Wayback|url=http://www.math.cmu.edu/~af1p/Teaching/AdditiveCombinatorics/allnotes.pdf |date=20170829160603 }}, p. 39-42</ref> варианты этого доказательства, исключительно для <math>{\mathbb F}_p^n</math>, которые, используя коэффициенты Фурье в <math>{\mathbb F}_p^n</math>, напрямую обобщают идеи из аналитического доказательства теоремы Рота. Доказательство получается технически даже более простым, чем доказательство самой теоремы Рота, так что часто<ref name="f_p^n_minicourse" /><ref>[https://www.youtube.com/watch?v=9s88mzq9BHc Лаборатория Чебышёва, Илья Шкредов, Аналитические методы в аддитивной комбинаторике, обзорная лекция]</ref> даётся в качестве первого примера применения метода.

В 2012 году Бэйтман и Кац, рассматривая случай <math>q=3</math>, доказали<ref>{{Cite web |url=https://scholarworks.iu.edu/dspace/bitstream/handle/2022/19057/S0894-0347-2011-00725-X.pdf?sequence=1&isAllowed=y |title=M. Bateman and N. Katz, New bounds on cap sets, Journal of the American Mathematical Society 25 (2012), no. 2, 585—613. |access-date=2017-12-23 |archive-date=2018-01-09 |archive-url=https://web.archive.org/web/20180109235515/https://scholarworks.iu.edu/dspace/bitstream/handle/2022/19057/S0894-0347-2011-00725-X.pdf?sequence=1&isAllowed=y |deadlink=no }}</ref> существование <math>\epsilon > 0</math> и абсолютной константы <math>C</math>, такой, что для <math>A \subset {\mathbb F}_3^n</math> без арифметических прогрессий выполняется <math>|A| \le \frac{3^n}{n^{1+\epsilon}}</math>.

В 2016 году Крут, Лев и Пах доказали<ref>{{Cite web |url=http://www.arxiv.org/abs/1605.01506 |title=E. Croot, V. Lev, and P. P. Pach, Progression-free sets in Z_n^4 are exponentially small (2016). arXiv preprint 1605.01506. |access-date=2017-12-23 |archive-date=2018-06-12 |archive-url=https://web.archive.org/web/20180612162552/https://arxiv.org/abs/1605.01506 |deadlink=no }}</ref> для случая <math>q=4</math>, что <math>|A| \le {3.62}^{n}</math> для множеств <math>A \subset {\mathbb F}_4^n</math> без прогрессий. Ellenberg и Gijswijt, обобщая метод Крута, Лева и Паха, используя [[Кольцо многочленов|алгебру многочленов]], доказали<ref name="f_p_n_best">{{Cite web |url=https://arxiv.org/abs/1605.09223 |title=Доказательство теоремы Рота для групп с малым кручением на arxiv.org |access-date=2017-12-23 |archive-date=2018-06-12 |archive-url=https://web.archive.org/web/20180612140604/https://arxiv.org/abs/1605.09223 |deadlink=no }}</ref><ref>[https://rus4.livejournal.com/83842.html Изложение доказательства Ellenberg и Gijswijt на русском языке]</ref> существование для каждого просто <math>q \ge 3</math> константы <math>c=c(q)<q</math> такой, что <math>|A|=O(c^n)</math> если <math>A \subset {\mathbb F}_q^n</math> не содержит прогрессий длины 3. В их работе <math>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 })}</math>. В частности, для случая <math>q=3</math> выполняется <math>|A|=o(2.756^n)</math>. При предположении <math>\theta = \frac{c_0}{q}</math> из оптимизации функции <math>\frac{c}{3} - \ln{\frac{e^c-1}{c}}</math> следует, что <math>c(q) \sim \frac{e^{c_0}-1}{c_0 e^{(c_0/3)}}q</math>, где <math>c_0</math> — абсолютная константа, являющаяся решением уравнения <math>2 c e^c - 3 e^c + c + 3 = 0</math>, то есть <math>c(q) \sim c_1 q</math>, где <math>c_1 \approx 0.841434...</math>

==== Нижние оценки ====
Наилучшая<ref name="f_p_n_best" /> по состоянию {{на|2016}} конструкция-контрпример позволяет<ref>{{Cite web |url=https://link.springer.com/article/10.1023/A:1027365901231 |title=Y. Edel, Extensions of generalized product caps, Designs, Codes and Cryptography 31 (2004), no. 1, 5—14. |access-date=2017-12-23 |archive-date=2018-01-10 |archive-url=https://web.archive.org/web/20180110054702/https://link.springer.com/article/10.1023/A:1027365901231 |deadlink=no }}</ref> строить для групп вида <math>{\mathbb F}_3^n</math> множества размера <math>\Omega(2.2^n)</math>, не содержащие арифметических прогрессий длины 3.

=== Для произвольных групп ===
В работе Мешулама рассматривается<ref name="Meshulam" /> теорема Рота для произвольной группы <math>G={\Z}_{k_1} \oplus \dots \oplus {\Z}_{k_n}</math> и выводится оценка <math>|A| < 2 \frac{|G|}{n}</math> для множества без арифметических прогрессий длины 3.

Из этого следует существование абсолютной константы <math>\beta > 0</math> такой, что для множества <math>A \subset G</math> без прогрессий выполняется <math>|A|<\frac{|G|}{(\log{|G|})^{\beta}}</math>

=== Двумерное обобщение ===
{{основная статья|Теорема об уголках}}

Классическим обобщением теоремы Рота для двумерных множеств <math>A \subset \left\lbrace{1,\dots,N}\right\rbrace \times \left\lbrace{1,\dots,N}\right\rbrace</math> считается [[теорема об уголках]]. Хотя там и не упоминаются арифметические прогрессии (в двумерном смысле), но теорема Рота из неё следует.

== См. также ==
* [[Теорема ван дер Вардена]]

== Литература ==
* {{статья
 | автор         = K. F. Roth
 | заглавие      = On Certain Sets of Integers
 | ссылка        = https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms/s1-28.1.104
 | язык          = en
 | издание       = Journal of the London Mathematical Society
 | год           = 1953
 | страницы      = 104—109
 | doi           = 10.1112/jlms/s1-28.1.104
 | ref           = Roth
}}
* {{статья
 | автор         = D. R. Heath-Brown
 | заглавие      = Integer Sets Containing No Arithmetic Progressions
 | ссылка        = https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms/s2-35.3.385
 | язык          = en
 | издание       = Journal of the London Mathematical Society
 | год           = 1987
 | том           = s2-35
 | выпуск        = 3
 | страницы      = 385—394
 | doi           = 10.1112/jlms/s2-35.3.385
 | ref           = Heath-Brown
}}
* {{статья
 | автор         = E. Szemerédi
 | заглавие      = Integer sets containing no arithmetic progressions
 | ссылка        = https://link.springer.com/article/10.1007/BF01903717
 | язык          = en
 | издание       = Acta Mathematica Hungarica
 | год           = 1990
 | том           = 56
 | страницы      = 155—159
 | doi           = 10.1007/BF01903717
 | ref           = Szemerédi
}}
* {{статья
 | автор         = J. Bourgain 
 | заглавие      = On Triples in Arithmetic Progression
 | ссылка        = https://link.springer.com/article/10.1007/s000390050105
 | язык          = en
 | издание       = Geometric & Functional Analysis GAFA
 | год           = 1999
 | том           = 9
 | страницы      = 968—984
 | doi           = 10.1007/s000390050105
 | ref           = Bourgain
}}
* {{статья
 | автор         = J. Bourgain 
 | заглавие      = Roth’s theorem on progressions revisited
 | ссылка        = https://link.springer.com/article/10.1007/s11854-008-0020-x
 | язык          = en
 | издание       = Journal d'Analyse Mathématique
 | год           = 2008
 | том           = 104
 | страницы      = 155—192
 | doi           = 10.1007/s11854-008-0020-x
 | ref           = Bourgain
}}
* {{статья
 | автор         = T. Sanders
 | заглавие      = On certain other sets of integers
 | ссылка        = https://link.springer.com/article/10.1007/s11854-012-0003-9
 | язык          = en
 | издание       = Journal d’Analyse Mathématique
 | год           = 2012
 | том           = 116
 | страницы      = 53—82
 | doi           = 10.1007/s11854-012-0003-9
 | arxiv         = 1007.5444
 | ref           = Sanders
}}
* {{статья
 | автор         = T. Sanders
 | заглавие      = On Roth’s theorem on progressions
 | ссылка        = https://annals.math.princeton.edu/2011/174-1/p20
 | язык          = en
 | издание       = Annals of Mathematics
 | год           = 2011
 | том           = 174
 | страницы      = 619—636
 | doi           = 10.4007/annals.2011.174.1.20 
 | arxiv         = 1011.0104
 | ref           = Sanders
}}
* {{статья
 | автор         = T. F. Bloom
 | заглавие      = A quantitative improvement for Roth's theorem on arithmetic progressions
 | ссылка        = https://londmathsoc.onlinelibrary.wiley.com/doi/full/10.1112/jlms/jdw010
 | язык          = en
 | издание       = Journal of the London Mathematical Society
 | год           = 2014
 | том           = 93
 | выпуск        = 3
 | страницы      = 643—663
 | doi           = 10.1112/jlms/jdw010
 | arxiv         = 1405.5800
 | ref           = Bloom
}}
* {{статья
 | автор         = T. Schoen
 | заглавие      = Improved bound in Roth’s theorem on arithmetic progressions
 | язык          = en
 | год           = 2020
 | arxiv         = 2005.01145
 | ref           = Schoen
}}
* {{статья
 | автор         = T. F. Bloom, O. Sisask
 | заглавие      = Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions
 | язык          = en
 | год           = 2020
 | arxiv         = 2007.03528
 | ref           = Bloom, Sisask
}}

== Примечания ==
{{примечания}}

{{rq|style}}
[[Категория:Аддитивная теория чисел]]
[[Категория:Арифметическая комбинаторика]]