Теорема Рота об арифметических прогрессиях

О существовании арифметических прогрессий в подмножествах натуральных чисел

Теорема Рота об арифметических прогрессиях — результат аддитивной комбинаторики, касающийся существования арифметических прогрессий в подмножествах натуральных чисел . Впервые она была доказана Клаусом Ротом в 1953 году. ^[1] Теорема Рота является частным случаем теоремы Семереди для случая . ${\displaystyle k=3}$

Заявление

Говорят, что подмножество A натуральных чисел имеет положительную верхнюю плотность, если

${\displaystyle \limsup _{n\to \infty }{\frac {|A\cap \{1,2,3,\dotsc ,n\}|}{n}}>0}$.

Теорема Рота об арифметических прогрессиях (бесконечная версия) : Подмножество натуральных чисел с положительной верхней плотностью содержит 3-членную арифметическую прогрессию.

Альтернативная, более качественная формулировка теоремы касается максимального размера множества Салема–Спенсера , которое является подмножеством . Пусть — размер наибольшего подмножества , которое не содержит 3-членной арифметической прогрессии. ${\displaystyle [N]=\{1,\dots ,N\}}$ ${\displaystyle r_{3}([N])}$ ${\displaystyle [N]}$

Теорема Рота об арифметических прогрессиях (финитная версия) : . ${\displaystyle r_{3}([N])=o(N)}$

Улучшение верхних и нижних границ все еще остается открытой исследовательской проблемой. ${\displaystyle r_{3}([N])}$

История

Первым результатом в этом направлении стала теорема Ван дер Вардена 1927 года, которая гласит, что при достаточно большом N раскрашивание целых чисел цветами приведет к члену арифметической прогрессии. ^[2] ${\displaystyle 1,\dots ,n}$ ${\displaystyle r}$ ${\displaystyle k}$

Позже в 1936 году Эрдёш и Туран выдвинули гораздо более сильный результат, что любое подмножество целых чисел с положительной плотностью содержит произвольно длинные арифметические прогрессии. В 1942 году Рафаэль Салем и Дональд С. Спенсер предложили конструкцию множества, свободного от 3-AP (т. е. множества без 3-членных арифметических прогрессий) размера , ^[3] опровергнув дополнительную гипотезу Эрдёша и Турана о том, что для некоторых . ^[4] ${\displaystyle {\frac {N}{e^{O(\log N/\log \log N)}}}}$ ${\displaystyle r_{3}([N])=N^{1-\delta }}$ ${\displaystyle \delta >0}$

В 1953 году Рот частично разрешил первоначальную гипотезу, доказав, что они должны содержать арифметическую прогрессию длины 3, используя аналитические методы Фурье. В конце концов, в 1975 году Семереди доказал теорему Семереди, используя комбинаторные методы, полностью разрешив первоначальную гипотезу.

Методы доказательства

Первоначальное доказательство, данное Ротом, использовало аналитические методы Фурье. Позднее было дано другое доказательство с использованием леммы регулярности Семереди .

Эскиз доказательства с помощью анализа Фурье

В 1953 году Рот использовал анализ Фурье , чтобы доказать верхнюю границу . Ниже приведен набросок этого доказательства. ${\displaystyle r_{3}([N])=O\left({\frac {N}{\log \log N}}\right)}$

Определим преобразование Фурье функции как функцию, удовлетворяющую ${\displaystyle f:\mathbb {Z} \rightarrow \mathbb {C} }$ ${\displaystyle {\widehat {f}}}$

${\displaystyle {\widehat {f}}(\theta )=\sum _{x\in \mathbb {Z} }f(x)e(-x\theta )}$,

где . ${\displaystyle e(t)=e^{2\pi it}}$

Пусть будет подмножеством , свободным от 3 AP . Доказательство выполняется в 3 шага. ${\displaystyle A}$ ${\displaystyle \{1,\dots ,N\}}$

1. Покажите, что a допускает большой коэффициент Фурье. ${\displaystyle A}$
2. Выведите, что существует подпрогрессия, которая имеет приращение плотности при ограничении этой подпрогрессией. ${\displaystyle \{1,\dots ,N\}}$ ${\displaystyle A}$
3. Повторите шаг 2, чтобы получить верхнюю границу . ${\displaystyle |A|}$

Шаг 1

Для функций определите ${\displaystyle f,g,h:\mathbb {Z} \rightarrow \mathbb {C} ,}$

${\displaystyle \Lambda (f,g,h)=\sum _{x,y\in \mathbb {Z} }f(x)g(x+y)h(x+2y)}$

Лемма о подсчете Пусть удовлетворяет . Определим . Тогда . ${\displaystyle f,g:\mathbb {Z} \rightarrow \mathbb {C} }$ ${\displaystyle \sum _{n\in \mathbb {Z} }|f(n)|^{2},\sum _{n\in \mathbb {Z} }|g(n)|^{2}\leq M}$ ${\displaystyle \Lambda _{3}(f)=\Lambda (f,f,f)}$ ${\displaystyle |\Lambda _{3}(f)-\Lambda _{3}(g)|\leq 3M\|{\widehat {f-g}}\|_{\infty }}$

Лемма подсчета говорит нам, что если преобразования Фурье и «близки», то число 3-членных арифметических прогрессий между ними также должно быть «близким». Пусть будет плотностью . Определим функции (т. е. индикаторную функцию ), и . Затем шаг 1 можно вывести, применив лемму подсчета к и , которая говорит нам, что существуют некоторые такие, что ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle \alpha =|A|/N}$ ${\displaystyle A}$ ${\displaystyle f=\mathbf {1} _{A}}$ ${\displaystyle A}$ ${\displaystyle g=\alpha \cdot \mathbf {1} _{[N]}}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle \theta }$

${\displaystyle \left|\sum _{n=1}^{N}(1_{A}-\alpha )(n)e(\theta n)\right|\geq {\frac {\alpha ^{2}}{10}}N}$.

Шаг 2

Учитывая шаг 1, мы сначала показываем, что возможно разбиение на относительно большие подпрогрессии таким образом, что характер будет примерно постоянным на каждой подпрогрессии. ${\displaystyle \theta }$ ${\displaystyle [N]}$ ${\displaystyle x\mapsto e(x\theta )}$

Лемма 1: Пусть . Предположим, что для универсальной константы . Тогда можно разбить на арифметические прогрессии длины так, что для всех . ${\displaystyle 0<\eta <1,\theta \in \mathbb {R} }$ ${\displaystyle N>C\eta ^{-6}}$ ${\displaystyle C}$ ${\displaystyle [N]}$ ${\displaystyle P_{i}}$ ${\displaystyle N^{1/3}\leq |P_{i}|\leq 2N^{1/3}}$ ${\displaystyle \sup _{x,y\in P_{i}}|e(x\theta )-e(y\theta )|<\eta }$ ${\displaystyle i}$

Далее мы применяем Лемму 1 для получения разбиения на подпрогрессии. Затем мы используем тот факт, что на шаге 1 был получен большой коэффициент, чтобы показать, что одна из этих подпрогрессий должна иметь приращение плотности: ${\displaystyle \theta }$

Лемма 2: Пусть — свободное от 3 AP подмножество , причем . Тогда существует подпрогрессия такая, что и . ${\displaystyle A}$ ${\displaystyle [N]}$ ${\displaystyle |A|=\alpha N}$ ${\displaystyle N>C\alpha ^{-12}}$ ${\displaystyle P\subset [N]}$ ${\displaystyle |P|\geq N^{1/3}}$ ${\displaystyle |A\cap P|\geq (\alpha +\alpha ^{2}/40)|P|}$

Шаг 3

Теперь повторяем шаг 2. Пусть будет плотностью после th итерации. Имеем, что и Во-первых, видим, что удваивается (т. е. достигает такого, что ) после максимум шагов. Мы снова удваиваемся (т. е. достигаем ) после максимум шагов. Поскольку , этот процесс должен завершиться после максимум шагов. ${\displaystyle a_{t}}$ ${\displaystyle A}$ ${\displaystyle t}$ ${\displaystyle \alpha _{0}=\alpha ,}$ ${\displaystyle \alpha _{t+1}\geq \alpha +\alpha ^{2}/40.}$ ${\displaystyle \alpha }$ ${\displaystyle T}$ ${\displaystyle \alpha _{T}\geq 2\alpha _{0}}$ ${\displaystyle 40/\alpha +1}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha _{T}\geq 4\alpha _{0}}$ ${\displaystyle 20/\alpha +1}$ ${\displaystyle \alpha \leq 1}$ ${\displaystyle O(1/\alpha )}$

Пусть будет размером нашей текущей прогрессии после итераций. По лемме 2 мы всегда можем продолжить процесс, когда бы то ни было, и, таким образом, когда процесс заканчивается, мы имеем, что Также обратите внимание, что когда мы переходим к подпрогрессии, размер нашего множества уменьшается на кубический корень. Поэтому ${\displaystyle N_{t}}$ ${\displaystyle t}$ ${\displaystyle N_{t}\geq C\alpha _{t}^{-12},}$ ${\displaystyle N_{t}\leq C\alpha _{t}^{-12}\leq C\alpha ^{-12}.}$

${\displaystyle N\leq N_{t}^{3^{t}}\leq (C\alpha ^{-12})^{3^{O(1/\alpha )}}=e^{e^{O(1/\alpha )}}.}$

Поэтому так , как и хотелось бы. ${\displaystyle \alpha =O(1/\log \log N),}$ ${\displaystyle |A|=O\left({\frac {N}{\log \log N}}\right),}$ ${\displaystyle \blacksquare }$

К сожалению, эта техника не обобщается напрямую на более крупные арифметические прогрессии для доказательства теоремы Семереди. Расширение этого доказательства ускользало от математиков на протяжении десятилетий до 1998 года, когда Тимоти Гауэрс разработал область анализа Фурье высшего порядка специально для обобщения приведенного выше доказательства для доказательства теоремы Семереди. ^[5]

Эскиз доказательства с помощью регулярности графика

Ниже приведен план доказательства с использованием леммы Семереди о регулярности .

Пусть будет графом и . Назовем -регулярной пару, если для всех с , имеем . ${\displaystyle G}$ ${\displaystyle X,Y\subseteq V(G)}$ ${\displaystyle (X,Y)}$ ${\displaystyle \epsilon }$ ${\displaystyle A\subset X,B\subset Y}$ ${\displaystyle |A|\geq \epsilon |X|,|B|\geq \epsilon |Y|}$ ${\displaystyle |d(A,B)-d(X,Y)|\leq \epsilon }$

Раздел является -регулярным разделом , если ${\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}}$ ${\displaystyle V(G)}$ ${\displaystyle \epsilon }$

${\displaystyle \sum _{(i,j)\in [k]^{2},(V_{i},V_{j}){\text{ not }}\epsilon {\text{-regular}}}|V_{i}||V_{j}|\leq \epsilon |V(G)|^{2}}$.

Тогда лемма Семереди о регулярности утверждает, что для любого существует константа такая, что каждый граф имеет -регулярное разбиение не более чем на части. ${\displaystyle \epsilon >0}$ ${\displaystyle M}$ ${\displaystyle \epsilon }$ ${\displaystyle M}$

Мы также можем доказать, что треугольники между -регулярными наборами вершин должны иметь много других треугольников. Это известно как лемма о подсчете треугольников. ${\displaystyle \epsilon }$

Лемма о подсчете треугольников: Пусть будет графом и будет подмножествами вершин из , которые являются всеми -регулярными парами для некоторых . Пусть обозначают плотности ребер соответственно. Если , то число троек таких, которые образуют треугольник в , не менее ${\displaystyle G}$ ${\displaystyle X,Y,Z}$ ${\displaystyle G}$ ${\displaystyle (X,Y),(Y,Z),(Z,X)}$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon >0}$ ${\displaystyle d_{XY},d_{XZ},d_{YZ}}$ ${\displaystyle d(X,Y),d(X,Z),d(Y,Z)}$ ${\displaystyle d_{XY},d_{XZ},d_{YZ}\geq 2\epsilon }$ ${\displaystyle (x,y,z)\in X\times Y\times Z}$ ${\displaystyle x,y,z}$ ${\displaystyle G}$

${\displaystyle (1-2\epsilon )(d_{XY}-\epsilon )(d_{XZ}-\epsilon )(d_{YZ}-\epsilon )\cdot |X||Y||Z|}$.

Используя лемму о подсчете треугольников и лемму о регулярности Семереди, мы можем доказать лемму об удалении треугольников, частный случай леммы об удалении графов . ^[6]

Лемма об удалении треугольников: Для всех существует такое, что любой граф на вершинах с числом треугольников, меньшим или равным , можно сделать свободным от треугольников, удалив не более ребер. ${\displaystyle \epsilon >0}$ ${\displaystyle \delta >0}$ ${\displaystyle n}$ ${\displaystyle \delta n^{3}}$ ${\displaystyle \epsilon n^{2}}$

Это имеет интересное следствие, касающееся графов на вершинах, где каждое ребро лежит в уникальном треугольнике. В частности, все эти графы должны иметь ребра. ${\displaystyle G}$ ${\displaystyle N}$ ${\displaystyle G}$ ${\displaystyle o(N^{2})}$

Возьмем набор без 3-членных арифметических прогрессий. Теперь построим трехдольный граф , все части которого являются копиями . Соединим вершину с вершиной , если . Аналогично соединим с , если . Наконец, соединим с , если . ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle X,Y,Z}$ ${\displaystyle \mathbb {Z} /(2N+1)\mathbb {Z} }$ ${\displaystyle x\in X}$ ${\displaystyle y\in Y}$ ${\displaystyle y-x\in A}$ ${\displaystyle z\in Z}$ ${\displaystyle y\in Y}$ ${\displaystyle z-y\in A}$ ${\displaystyle x\in X}$ ${\displaystyle z\in Z}$ ${\displaystyle (z-x)/2\in A}$

Эта конструкция настроена так, что если образуют треугольник, то мы получаем элементы , которые все принадлежат . Эти числа образуют арифметическую прогрессию в указанном порядке. Предположение о тогда говорит нам, что эта прогрессия должна быть тривиальной: перечисленные выше элементы все равны. Но это условие эквивалентно утверждению, что является арифметической прогрессией в . Следовательно, каждое ребро лежит ровно в одном треугольнике. Отсюда следует желаемый вывод. ${\displaystyle x,y,z}$ ${\displaystyle y-x,{\frac {z-x}{2}},z-y}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle x,y,z}$ ${\displaystyle \mathbb {Z} /(2N+1)\mathbb {Z} }$ ${\displaystyle G}$ ${\displaystyle \blacksquare }$

Расширения и обобщения

Теорема Семереди разрешила исходную гипотезу и обобщила теорему Рота на арифметические прогрессии произвольной длины. С тех пор она была расширена множеством способов для создания новых и интересных результатов.

Фюрстенберг и Кацнельсон ^[7] использовали эргодическую теорию для доказательства многомерной версии, а Лейбман и Бергельсон ^[8] распространили ее также на полиномиальные прогрессии. Совсем недавно Грин и Тао доказали теорему Грина–Тао , которая гласит, что простые числа содержат произвольно длинные арифметические прогрессии. Поскольку простые числа являются подмножеством плотности 0, они ввели «относительную» теорему Семереди, которая применяется к подмножествам с плотностью 0, которые удовлетворяют определенным условиям псевдослучайности . Позже Конлон , Фокс и Чжао ^{[9] [10]} усилили эту теорему, ослабив необходимое условие псевдослучайности. В 2020 году Блум и Сисаск ^[11] доказали, что любое множество , такое что расходится, должно содержать арифметические прогрессии длины 3; это первый нетривиальный случай другой гипотезы Эрдёша , постулирующей, что любое такое множество должно на самом деле содержать произвольно длинные арифметические прогрессии. ${\displaystyle A}$ ${\displaystyle \sum _{n\in A}{\frac {1}{n}}}$

Улучшение границ

Также была проделана работа по улучшению границы в теореме Рота. Граница из первоначального доказательства теоремы Рота показала, что

${\displaystyle r_{3}([N])\leq c\cdot {\frac {N}{\log \log N}}}$

для некоторой константы . На протяжении многих лет эта граница постоянно понижалась Семереди, ^[12] Хит-Брауном , ^[13] Бургейном , ^{[14] [15]} и Сандерсом . ^{[16] [17]} Текущая (июль 2020 г.) лучшая граница принадлежит Блуму и Сисаску ^[11], которые показали существование абсолютной константы c>0 такой, что ${\displaystyle c}$

${\displaystyle r_{3}([N])\leq {\frac {N}{(\log N)^{1+c}}}.}$

В феврале 2023 года в препринте ^{[18] [19]} (позже опубликованном ^[20] ) Келли и Мека была дана новая оценка:

${\displaystyle r_{3}([N])\leq 2^{-\Omega ((\log N)^{1/12})}\cdot N}$.

Четыре дня спустя Блум и Сисаск опубликовали препринт, дающий изложение результата ^[21] (позже опубликованного ^[22] ), упрощая аргументацию и приводя некоторые дополнительные приложения. Несколько месяцев спустя Блум и Сисаск получили дальнейшее улучшение и заявили (без доказательства), что их методы могут быть использованы для того, чтобы показать . ^[23] ${\displaystyle r_{3}([N])\leq \exp(-c(\log N)^{1/9})N}$ ${\displaystyle r_{3}([N])\leq \exp(-c(\log N)^{5/41})N}$

Также была проделана работа с другой стороны, построение самого большого множества без 3-членных арифметических прогрессий. Лучшая конструкция едва ли была улучшена с 1946 года, когда Беренд ^[24] улучшил начальную конструкцию Салема и Спенсера и доказал

${\displaystyle r_{3}([N])\geq N\exp(-c{\sqrt {\log N}})}$.

Из-за отсутствия улучшений за последние 70 лет предполагается, что множество Беренда асимптотически очень близко по размеру к наибольшему возможному множеству без 3-членных прогрессий. ^[11] Если это верно, граница Келли-Мека докажет эту гипотезу.

Теорема Рота в конечных полях

В качестве вариации можно рассмотреть аналогичную задачу над конечными полями . Рассмотрим конечное поле , и пусть будет размером наибольшего подмножества , которое не содержит 3-членной арифметической прогрессии. Эта задача фактически эквивалентна задаче о наборе крышек , которая требует наибольшего подмножества , такого, что никакие 3 точки не лежат на одной прямой. Задачу о наборе крышек можно рассматривать как обобщение карточной игры Set . ${\displaystyle \mathbb {F} _{3}^{n}}$ ${\displaystyle r_{3}(\mathbb {F} _{3}^{n})}$ ${\displaystyle \mathbb {F} _{3}^{n}}$ ${\displaystyle \mathbb {F} _{3}^{n}}$

В 1982 году Браун и Бюлер ^[25] первыми показали, что В 1995 году Рой Месулам ^[26] использовал технику, похожую на Фурье-аналитическое доказательство теоремы Рота, чтобы показать, что Эта граница была улучшена до в 2012 году Бейтманом и Кацем. ^[27] ${\displaystyle r_{3}(\mathbb {F} _{3}^{n})=o(3^{n}).}$ ${\displaystyle r_{3}(\mathbb {F} _{3}^{n})=O\left({\frac {3^{n}}{n}}\right).}$ ${\displaystyle O(3^{n}/n^{1+\epsilon })}$

В 2016 году Эрни Крут , Всеволод Лев, Петер Пал Пах, Джордан Элленберг и Дион Гейсвит разработали новую методику, основанную на полиномиальном методе, чтобы доказать, что . ^{[28] [29] [30]} ${\displaystyle r_{3}(\mathbb {F} _{3}^{n})=O(2.756^{n})}$

Самая известная нижняя граница — это , обнаруженная в декабре 2023 года исследователями Google DeepMind с использованием большой языковой модели (LLM). ^[31] ${\displaystyle 2.2202^{n}}$

Теорема Рота с популярными разностями

Другое обобщение теоремы Рота показывает, что для подмножеств с положительной плотностью не только существует 3-членная арифметическая прогрессия, но и существует множество 3-AP, имеющих одно и то же общее различие.

Теорема Рота с популярными разностями: Для всех существует такое , что для каждого и при существует такое , что ${\displaystyle \epsilon >0}$ ${\displaystyle n_{0}=n_{0}(\epsilon )}$ ${\displaystyle n>n_{0}}$ ${\displaystyle A\subset \mathbb {F} _{3}^{n}}$ ${\displaystyle |A|=\alpha 3^{n},}$ ${\displaystyle y\neq 0}$ ${\displaystyle |\{x:x,x+y,x+2y\in A\}|\geq (\alpha ^{3}-\epsilon )3^{n}.}$

Если выбирается случайным образом из , то мы могли бы ожидать, что будут прогрессии для каждого значения . Таким образом, популярная теорема о разностях утверждает, что для каждого с положительной плотностью существует некоторая такая, что число 3-AP с общей разностью близко к тому, что мы ожидали бы. ${\displaystyle A}$ ${\displaystyle \mathbb {F} _{3}^{n},}$ ${\displaystyle \alpha ^{3}3^{n}}$ ${\displaystyle y}$ ${\displaystyle |A|}$ ${\displaystyle y}$ ${\displaystyle y}$

Эта теорема была впервые доказана Грином в 2005 году ^[32], который дал границу того, где находится функция башни. В 2019 году Фокс и Фам недавно улучшили границу до ^[33] ${\displaystyle n_{0}={\text{tow}}((1/\epsilon )^{O(1)}),}$ ${\displaystyle {\text{tow}}}$ ${\displaystyle n_{0}={\text{tow}}(O(\log {\frac {1}{\epsilon }})).}$

Соответствующее утверждение также верно для 3-AP и 4-AP. ^[34] Однако было показано, что это утверждение ложно для 5-AP. ^[35] ${\displaystyle \mathbb {Z} }$

Ссылки

1. Рот, Клаус (1953). «О некоторых множествах целых чисел». Журнал Лондонского математического общества . 28 (1): 104–109. doi :10.1112/jlms/s1-28.1.104.
2. ван дер Варден, BL (1927). «Beweis einer Baudetschen Vermutung». Ньюв. Арх. Виск . 15 : 212–216.
3. Салем, Рафаэль; Спенсер, Дональд К. (1942). «О множествах целых чисел, которые не содержат трех членов в арифметической прогрессии». Труды Национальной академии наук Соединенных Штатов Америки . 28 (12): 561–563. Bibcode :1942PNAS...28..561S. doi : 10.1073/pnas.28.12.561 . MR  0007405. PMC 1078539 . PMID  16588588. 
4. Эрдёш, Пол; Туран, Пол (1936). «О некоторых последовательностях целых чисел». Журнал Лондонского математического общества . 4 (4): 261–264. doi :10.1112/jlms/s1-11.4.261. MR  1574918.
5. Gowers, WT (1998). «Новое доказательство теоремы Семереди для арифметических прогрессий длины четыре». Геометрический и функциональный анализ . 8 (3): 529–551. doi : 10.1007/s000390050065 .
6. Фокс, Джейкоб (2011), «Новое доказательство леммы об удалении графа», Annals of Mathematics , вторая серия, 174 (1): 561–579, arXiv : 1006.1300 , doi : 10.4007/annals.2011.174.1.17, MR  2811609, S2CID  8250133
7. Фюрстенберг, Гилель ; Кацнельсон, Ицхак (1978). «Эргодическая теорема Семереди для коммутирующих преобразований». Журнал Математического Анализа . 38 (1): 275–291. дои : 10.1007/BF02790016 . MR  0531279. S2CID  123386017.
8. Бергельсон, Виталий ; Лейбман, Александр (1996). «Полиномиальные расширения теорем Ван дер Вардена и Семереди». Журнал Американского математического общества . 9 (3): 725–753. doi : 10.1090/S0894-0347-96-00194-4 . MR  1325795.
9. Конлон, Дэвид ; Фокс, Джейкоб ; Чжао, Юфэй (2015). «Относительная теорема Семереди». Геометрический и функциональный анализ . 25 (3): 733–762. arXiv : 1305.5440 . doi : 10.1007/s00039-015-0324-9 . MR  3361771.
10. Чжао, Юфэй (2014). «Арифметическое доказательство переноса относительной теоремы Семереди». Математические труды Кембриджского философского общества . 156 (2): 255–261. arXiv : 1307.4959 . Bibcode : 2014MPCPS.156..255Z. doi : 10.1017/S0305004113000662. MR  3177868. S2CID  119673319.
11. Томас Ф. Блум, Олоф Сисаск, Преодоление логарифмического барьера в теореме Рота об арифметических прогрессиях , arXiv:2007.03528, 2020
12. Семереди, Эндре (1990). «Наборы целых чисел, не содержащие арифметических прогрессий». Acta Mathematica Hungarica . 56 (1–2): 155–158. дои : 10.1007/BF01903717 . МР  1100788.
13. Хит-Браун, Роджер (1987). «Целочисленные множества, не содержащие арифметических прогрессий». Журнал Лондонского математического общества . 35 (3): 385–394. doi :10.1112/jlms/s2-35.3.385. MR  0889362.
14. Бургейн, Жан (1999). «О тройках в арифметической прогрессии». Геометрический и функциональный анализ . 9 (5): 968–984. doi :10.1007/s000390050105. MR  1726234. S2CID  392820.
15. Бурген, Жан (2008). «Еще раз к теореме Рота о прогрессиях». Журнал Математического Анализа . 104 (1): 155–192. дои : 10.1007/s11854-008-0020-x . MR  2403433. S2CID  16985451.
16. Сандерс, Том (2012). «О некоторых других наборах целых чисел». Annals of Mathematics . 185 (1): 53–82. arXiv : 1007.5444 . doi : 10.1007/s11854-012-0003-9. MR  2892617. S2CID  119727492.
17. Сандерс, Том (2011). «О теореме Рота о прогрессиях». Annals of Mathematics . 174 (1): 619–636. arXiv : 1011.0104 . doi : 10.4007/annals.2011.174.1.20. MR  2811612. S2CID  53331882.
18. Келли, Зандер; Мека, Рагху (2023-02-10). «Сильные границы для 3-прогрессий». arXiv : 2302.05537 [math.NT].
19. Сломан, Лейла (21.03.2023). «Неожиданное доказательство компьютерной науки ошеломило математиков». Журнал Quanta .
20. Келли, Зандер; Мека, Рагху (2023-11-06). «Сильные границы для 3-прогрессий». 2023 IEEE 64-й ежегодный симпозиум по основам компьютерной науки (FOCS) . IEEE. стр. 933–973. arXiv : 2302.05537 . doi : 10.1109/FOCS57990.2023.00059. ISBN 979-8-3503-1894-4.
21. Блум, Томас Ф.; Сисаск, Олоф (2023-02-14). «Границы Келли–Мека для множеств, свободных от трехчленных арифметических прогрессий». Essential Number Theory . 2 : 15–44. arXiv : 2302.07211 . doi :10.2140/ent.2023.2.15.
22. Блум, Томас Ф.; Сисаск, Олоф (2023-12-31). «Границы Келли–Мека для множеств, свободных от трехчленных арифметических прогрессий». Essential Number Theory . 2 (1): 15–44. arXiv : 2302.07211 . doi :10.2140/ent.2023.2.15. ISSN  2834-4634.
23. Блум, Томас Ф.; Сисаск, Олоф (2023-09-05). «Улучшение границ Келли-Мека для трехчленных арифметических прогрессий». arXiv : 2309.02353 [math.NT].
24. Беренд, ФА (1946). «О множествах целых чисел, которые не содержат трех членов в арифметической прогрессии». Труды Национальной академии наук Соединенных Штатов Америки . 32 (12): 331–332. Bibcode :1946PNAS...32..331B. doi : 10.1073/pnas.32.12.331 . PMC 1078964 . PMID  16578230. 
25. Браун, TC ; Бюлер, JP (1982). «Плотностная версия геометрической теоремы Рамсея». Журнал комбинаторной теории . Серия A. 32 (1): 20–34. doi : 10.1016/0097-3165(82)90062-0 .
26. Месулам, Рой (1995). «О подмножествах конечных абелевых групп без 3-членных арифметических прогрессий». Журнал комбинаторной теории . Серия A. 71 (1): 168–172. doi : 10.1016/0097-3165(95)90024-1 .
27. Бейтман, М.; Кац, Н. (2012). «Новые границы множеств крышек». Журнал Американского математического общества . 25 (2): 585–613. doi : 10.1090/S0894-0347-2011-00725-X . hdl : 2022/19057 .
28. Элленберг, Джордан С.; Гейсвейт, Дион (2016). «О больших подмножествах без трехчленной арифметической прогрессии». Annals of Mathematics, Вторая серия . 185 (1): 339–343. arXiv : 1605.09223 . doi : 10.4007/annals.2017.185.1.8. S2CID  119683140. ${\displaystyle \mathbb {F} _{q}^{n}}$
29. Croot, Ernie; Lev, Vsevolod F.; Pach, Péter Pál (2017). «Наборы без прогрессии в экспоненциально малы». Annals of Mathematics . 2-я серия. 185 (1): 331–337. arXiv : 1605.01506 . doi : 10.4007/annals.2017.185.1.7. ${\displaystyle \mathbb {Z} _{4}^{n}}$
30. Кларрайх, Эрика (31 мая 2016 г.). «Простое доказательство игры с множеством ошеломило математиков». Quanta .
31. Ромера-Паредес, Бернардино; Барекатаин, Мохаммадамин; Новиков, Александр; Балог, Матей; Кумар, М. Паван; Дюпон, Эмильен; Руис, Франциско Дж. Р.; Элленберг, Джордан С.; Ван, Пэнминг; Фаузи, Омар; Кохли, Пушмит; Фаузи, Альхуссейн (2023-12-14). «Математические открытия из программного поиска с большими языковыми моделями». Nature . 625 (7995): 468–475. doi : 10.1038/s41586-023-06924-6 . ISSN  1476-4687. PMC 10794145 . PMID  38096900. 
32. Грин, Бен (2005). «Лемма регулярности типа Семереди в абелевых группах с приложениями». Геометрический и функциональный анализ . 15 (2): 340–376. doi : 10.1007/s00039-005-0509-8 . MR  2153903.
33. Фокс, Джейкоб ; Фам, Хай Туан (апрель 2021 г.). «Популярные различия прогрессий в векторных пространствах». Международные уведомления по математическим исследованиям . 2021 (7): 5261–5289. arXiv : 1708.08482 . Bibcode : 2017arXiv170808482F. doi : 10.1093/imrn/rny240 .
34. Грин, Бен; Тао, Терренс (2010). «Лемма арифметической регулярности, лемма ассоциированного подсчета и ее приложения». Нерегулярный ум . Математические исследования общества Бойяи. Том 21. Математические исследования общества Бойяи. С. 261–334. arXiv : 1002.2028 . Bibcode :2010arXiv1002.2028G. doi :10.1007/978-3-642-14444-8_7. ISBN 978-3-642-14443-1. S2CID  115174575.
35. Бергельсон, Виталий; Хост, Бернард; Кра, Брайна (2005). «Множественная повторяемость и нильпоследовательности. С приложением Имре Ружи». Inventiones Mathematicae . 160 (2): 261–303. doi :10.1007/s00222-004-0428-6. S2CID  1380361.

Внешние ссылки

• Эдмондс, Челси; Куцуку-Аргираки, Ангелики; Полсон, Лоуренс С. Теорема Рота об арифметических прогрессиях (Формальное доказательство, разработка в Isabelle/HOL, Архив формальных доказательств)