Теорема Рота

См. также: Теорема Туэ — Зигеля — Рота

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

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

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

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

История улучшения количественных оценокПравить

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

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

Гармонический анализПравить

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

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

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

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

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

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

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

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

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

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

Эрдёш, Туран (1936)Править

Первый пример множества без прогрессий привели в 1936 году Эрдёш и Туран, предложив рассмотреть числа, которые в троичной системе содержат только цифры 0 и 2. Такое множество содержит всего лишь $N^{{\log }_3<!--\; \; -->2}$$N^{\log _{3}{2}}$  чисел, что очень мало по сравнению с верхними оценками.

Доказательство корректности конструкции

Пусть $A$$A$  --- множество Эрдёша--Турана.

Если $a,b\in <!--\; \in \; -->A$$a,b\in A$  и $a<b$ , то в троичной системе в самом старшем разряде $i$$i$ , где различны эти числа выполняются равенства $a_i=0,b_i=2$$a_{i}=0,\ b_{i}=2$ . Поэтому в арифметической прогрессии $a<c<b$  выполнялось бы $c_i=1$$c_{i}=1$ , а значит, $c\notin A$$c\not \in A$ .

Салем, Спенсер (1942)Править

Салем и Спенсер в 1942 году обобщили идею Эрдёша и Турана на системы счисления с растущим (зависящим от размера множества) основанием и получили множество без прогрессий размера $\exp <!--\; \; -->\left(-<!--\; -\; -->O\left(\frac{\log <!--\; \; -->N}{\log <!--\; \; -->\log <!--\; \; -->N}\right)\right)N$$\exp \left({-O\left({\frac {\log N}{\log \log N}}\right)}\right)N$ .

Краткое описание конструкции

В конструкции Эрдёша--Турана вполне можно разрешать цифры 0 и 1 вместо 0 и 2 (тогда в доказательстве корректности место среднего числа в прогрессии будет занимать большее). По аналогии с этим Салем и Спенсер в $d$$d$ -ичной системе рассматривали числа, содержащие только цифры от 0 до $\frac{d-<!--\; -\; -->1}{2}$${\frac {d-1}{2}}$ , причём равное количество входений каждой цифры (с попарвкой на асимптотику $d$$d$  можно считать нечётным, а общее число цифр --- делящим $\frac{d-<!--\; -\; -->1}{2}$${\frac {d-1}{2}}$ ).

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

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

Беренд (1946)Править

В 1946 году Беренд^[en] добавил геометрическую интерпретацию, сопоставив разрядам числа координаты точек в многомерном пространстве и рассматривая числа, соответствующие в этом смысле точкам сферы. Это позволило построить не содержащее прогрессий множество размера $\exp <!--\; \; -->\left(-<!--\; -\; -->O\left(\sqrt{\log <!--\; \; -->N}\right)\right)N$$\exp \left({-O\left({\sqrt {\log N}}\right)}\right)N$ .

Краткое описание конструкции

Все числа $x<(2m+1)^{n}$  с цифрами не больше $m$$m$  и $(2m+1)$$(2m+1)$ -ричным представление $x=x_1{x}_2\dots <!--\; \dots \; -->x_n$$x=x_{1}x_{2}\dots x_{n}$  разбиваются на группы с одинаковыми значениями $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{x}_i^2$$\sum \limits _{i=1}^{n}{x_{i}^{2}}$ . В качестве множества выбирается наибольшая из этих групп и её размер оценивается по принципу Дирихле.

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

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

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

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

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

Для конечных циклических группПравить

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

Для любого $\mathrm{\delta <!--\; \delta \; -->}\in <!--\; \in \; -->(0;1)$$\delta \in (0;1)$  существует $N_0=N_0(\mathrm{\delta <!--\; \delta \; -->})$$N_{0}=N_{0}(\delta )$  такое, что если $N>N_0$$N>N_{0}$ , $A\subset <!--\; \subset \; -->{\mathbb{Z}}_N$$A\subset \mathbb {Z} _{N}$  и $|A|>\mathrm{\delta <!--\; \delta \; -->}N$$|A|>\delta N$ , то $A$$A$  содержит тройку $(a,a+d,a+2d),d\ne 0$$(a,a+d,a+2d),\ d\not =0$ , где под сложением понимается именно сложение по модулю

Обещаемые данной формулировкой прогрессии могут быть прогрессиями в ${\mathbb{Z}}_N$${\mathbb {Z} }_{N}$ , но не быть таковыми в $\mathbb{N}$${\mathbb {N} }$  (например, $(N-<!--\; -\; -->2,N-<!--\; -\; -->1,0)$$(N-2,N-1,0)$ ). Однако теорема Рота очевидным образом следует из неё если рассмотреть множество $\left\{N+a:a\in <!--\; \in \; -->A\right\}$$\left\lbrace {N+a:a\in A}\right\rbrace$  как множество вычетов в ${\mathbb{Z}}_{3N}$$\mathbb {Z} _{3N}$ . Это лишь на константу меняет плотность, но делает все прогрессии подходящими для $\mathbb{N}$${\mathbb {N} }$ . Следовательно, эта теорема эквивалентна основной теореме Рота.

Для групп с малым фиксированным кручениемПравить

Следующая теорема, сходная по идее с теоремой Рота, не следует из неё и не влечет её, но представляет интерес для отдельного изучения.

Пусть фиксированно некоторое $q\ge <!--\; \ge \; -->3$$q\geq 3$ . Тогда для любого $\mathrm{\delta <!--\; \delta \; -->}\in <!--\; \in \; -->(0;1)$$\delta \in (0;1)$  существует такое $n_0=n_0(\mathrm{\delta <!--\; \delta \; -->},q)$$n_{0}=n_{0}(\delta ,q)$ , что если $n>n_0,A\subset <!--\; \subset \; -->{\mathbb{F}}_q^n,|A|>\mathrm{\delta <!--\; \delta \; -->}{q}^n$$n>n_{0},\ A\subset {\mathbb {F} }_{q}^{n},\ |A|>\delta q^{n}$ , то $\mathrm{\exists <!--\; \exists \; -->}a,d(d\ne (0,\dots <!--\; \dots \; -->,0)):a,a+d,a+2d\in <!--\; \in \; -->A$$\exists a,d(d\not =(0,\dots ,0)):a,a+d,a+2d\in A$

Верхние оценкиПравить

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

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

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

В 2016 году Крут, Лев и Пах доказали для случая $q=4$$q=4$ , что $|A|\le <!--\; \le \; -->{3.62}^n$$|A|\leq {3.62}^{n}$  для множеств $A\subset <!--\; \subset \; -->{\mathbb{F}}_4^n$$A\subset {\mathbb {F} }_{4}^{n}$  без прогрессий. Ellenberg и Gijswijt, обобщая метод Крута, Лева и Паха, используя алгебру многочленов, доказали существование для каждого просто $q\ge <!--\; \ge \; -->3$$q\geq 3$  константы $c=c(q)<q$  такой, что $|A|=O(c^n)$$|A|=O(c^{n})$  если $A\subset <!--\; \subset \; -->{\mathbb{F}}_q^n$$A\subset {\mathbb {F} }_{q}^{n}$  не содержит прогрессий длины 3. В их работе $c(q)=\frac{q}{exp(\underset{\mathrm{\theta <!--\; \theta \; -->}}{sup}\left\{\frac{q-<!--\; -\; -->1}{3}\mathrm{\theta <!--\; \theta \; -->}+\ln <!--\; \; -->\frac{e^{q\mathrm{\theta <!--\; \theta \; -->}}-<!--\; -\; -->1}{q(e^{\mathrm{\theta <!--\; \theta \; -->}}-<!--\; -\; -->1)}\right\})}$$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$$q=3$  выполняется $|A|=o({2.756}^n)$$|A|=o(2.756^{n})$ . При предположении $\mathrm{\theta <!--\; \theta \; -->}=\frac{c_0}{q}$$\theta ={\frac {c_{0}}{q}}$  из оптимизации функции $\frac{c}{3}-<!--\; -\; -->\ln <!--\; \; -->\frac{e^c-<!--\; -\; -->1}{c}$${\frac {c}{3}}-\ln {\frac {e^{c}-1}{c}}$  следует, что $c(q)\sim <!--\; \sim \; -->\frac{e^{c_0}-<!--\; -\; -->1}{c_0{e}^{(c_0/3)}}q$$c(q)\sim {\frac {e^{c_{0}}-1}{c_{0}e^{(c_{0}/3)}}}q$ , где $c_0$$c_{0}$  — абсолютная константа, являющаяся решением уравнения $2c{e}^c-<!--\; -\; -->3e^c+c+3=0$$2ce^{c}-3e^{c}+c+3=0$ , то есть $c(q)\sim <!--\; \sim \; -->c_{1}q$$c(q)\sim c_{1}q$ , где $c_1\approx <!--\; \approx \; -->\mathrm{0.841434...}$$c_{1}\approx 0.841434...$ 

Нижние оценкиПравить

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

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

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

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

Двумерное обобщениеПравить

Основная статья: Теорема об уголках

Классическим обобщением теоремы Рота для двумерных множеств $A\subset <!--\; \subset \; -->\left\{1,\dots <!--\; \dots \; -->,N\right\}\times <!--\; \times \; -->\left\{1,\dots <!--\; \dots \; -->,N\right\}$$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. — doi:10.1007/s11854-012-0003-9. — arXiv:1007.5444.
• T. Sanders. On Roth’s theorem on progressions (англ.) // Annals of Mathematics. — 2011. — Vol. 174. — P. 619—636. — doi:10.4007/annals.2011.174.1.20. — arXiv:1011.0104.
• 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. — doi:10.1112/jlms/jdw010. — arXiv:1405.5800.
• 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.