WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

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

Формулировка

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

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

Также эквивалентна исходной и формулировка для конечных множеств:

Для любого $\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.

Подавляющее большинство доказательств доказывает именно формулировку для конечных множеств.

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

Гармонический анализ

Теорема была впервые доказана в 1953 году Клаусом Ротом^[2]^[3] путём адаптации кругового метода Харди — Литтлвуда. Доказательство использовало идею^[4], впоследствии обобщённую и для общего доказательства теоремы Семереди: все множества заданной плотности разбиваться на две группы — «равномерные» и «неравномерные», причём под «равномерностью» понимается верхняя оценка на коэффициенты Фурье. Если множество равномерно, то наличие прогрессий в нём можно доказать напрямую, а иначе можно доказать наличие подпрогрессии, в которой плотность множества больше чем среди отрезка натурального ряда, к которому оно принадлежит.

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

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

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

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

Элементарное (через обобщённые арифметические прогрессии)

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

Доказательство Грэхема не даёт оценок на $N$ , а только показывает существование, поскольку использует существование точки в последовательности, начиная с которой все точки достаточно близки к пределу, но для предела также доказано только существование, а характер сходимости в принципе не анализируется.

Лучшие оценки

Самое сильное достаточное условие плотности было найдено Т. Сандерсом в 2010 году и гласит, что если $|A|>{\frac {N(\log {\log N})^{5}}{\log {N}}}$ , то прогрессии во множестве точно будут. Это условие эквивалентно тому, что $N>e^{{\frac {1}{\delta }}\log ^{5}{\left({\frac {1}{\delta }}\right)}}$ .

Существует гипотеза Эрдёша — Турана, предполагающая, что $N>e^{\frac {C}{\delta }}$ также достаточно при некоторой абсолютной константе $C$ .

Контрпримеры для неплотных множеств

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

Лучший по состоянию на 2006 год^[1] результат по этому вопросу дал в 1946 году Ф. А. Беренд^[7], развивая метод Р. Салема и Д. Спенсера^[8]^[9]:

Пусть $\epsilon >0$ . Тогда существует $N_{\epsilon }$ такое, что для любого $N>N_{\epsilon }$ существует множество $A\subset \left\lbrace {1,\dots ,N}\right\rbrace$ размера $|A|>e^{-(1+\epsilon )C{\sqrt {\log {N}}}}N$ , не содержащее арифметических прогрессий длины 3. Здесь $C>0$ — некоторая абсолютная константа.

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

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

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

Для любого $\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 году^[10], однако они только доказали, что для множеств без арифметических прогрессий выполняется $|A|=o(q^{n})$ , но более точные ограничения на $|A|$ оставались открытым вопросом.

В 1993 году (опубликовано в 1995) Рой Мешулам (Roy Meshulam) доказал^[11], что $|A|\leq 2{\frac {q^{n}}{n}}$ . Его доказательство рассматривало произвольные группы и их характеры. Существуют также более упрощённые^[12] варианты этого доказательства, исключительно для ${\mathbb {F} }_{p}^{n}$ , которые, используя коэффициенты Фурье в ${\mathbb {F} }_{p}^{n}$ , напрямую обобщают идеи из аналитического доказательства теоремы Рота. Доказательство получается технически даже более простым, чем доказательство самой теоремы Рота, так что часто^[12]^[13] даётся в качестве первого примера применения метода.

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

В 2016 году Крут, Лев и Пах доказали^[15] для случая $q=4$ , что $|A|\leq {3.62}^{n}$ для множеств $A\subset {\mathbb {F} }_{4}^{n}$ без прогрессий. Ellenberg и Gijswijt, обобщая метод Крута, Лева и Паха, используя алгебру многочленов, доказали^[16]^[17] существование для каждого просто $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...$

Нижние оценки

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

Для произвольных групп

В работе Мешулама рассматривается^[11] теорема Рота для произвольной группы $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$ считается теорема об уголках. Хотя там и не упоминаются арифметические прогрессии (в двумерном смысле), но теорема Рота из неё следует.

См. также

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

Примечания

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии

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

[2] Roth, Klaus Friedrich (1953), "On certain sets of integers, I", Journal of the London Mathematical Society Т. 28: 104–109, Zbl 0050.04002, MR: 0051853, DOI 10.1112/jlms/s1-28.1.104

[3] Доказательство Рота в изложении Харольда Хельфготта на русском языке

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

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

[6] A mini course on additive combinatorics, p. 6

[7] F. A. Behrend, «On sets of integers which contain no three terms in arithmetic progression», Proc. Natl. Acad. Sci. USA, 32 (1946), 331—332.

[8] R. Salem, D. C. Spencer, Proc. Natl. Acad. Sci. USA, 28 (1942), 561—563

[9] R. Salem, D. C. Spencer, «On sets which do not contain a given number of terms in arithmetical progression», Nieuw Arch. Wisk. (2), 23 (1950), 133—143.

[10] 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.

[Meshulam-11] 1 2 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.

[f_p^n_minicourse-12] 1 2 A mini course on additive combinatorics, p. 39-42

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

[14] M. Bateman and N. Katz, New bounds on cap sets, Journal of the American Mathematical Society 25 (2012), no. 2, 585—613.

[15] E. Croot, V. Lev, and P. P. Pach, Progression-free sets in Z_n^4 are exponentially small (2016). arXiv preprint 1605.01506.

[f_p_n_best-16] 1 2 Доказательство теоремы Рота для групп с малым кручением на arxiv.org

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

[18] Y. Edel, Extensions of generalized product caps, Designs, Codes and Cryptography 31 (2004), no. 1, 5—14.