Карта → событие
Грин — Тао: прогрессии в простых
Вопрос
Простые числа $3,5,7$ образуют арифметическую прогрессию длины 3. Прогрессия длины 5: $5,11,17,23,29$ (разность 6). Длины 6: $7,37,67,97,127,157$ (разность 30). Есть ли сколь угодно длинные?
Вопрос ставился ещё ЛагранжемЖозеф Луи ЛагранжНаписал механику без единого чертежа, довёл до конца всё, что начали Эйлер и Ферма, и первым понял, что решаемость уравнения зависит от перестановок его корней. и Уорингом в XVIII веке. К 2004 году были найдены прогрессии длины 22, а доказано не было ничего — даже существование прогрессий длины 4 не следовало ни из какой теоремы.
Чего не хватало
Соседняя область к тому времени была разработана прекрасно.
Теорема ван дер Вардена (1927). Как ни раскрасить натуральные числа в конечное число цветов, найдётся сколь угодно длинная одноцветная прогрессия.
Теорема Семереди (1975). Пусть $A\subset\mathbb{N}$ имеет положительную верхнюю плотность. Тогда $A$ содержит прогрессии любой длины.
Гипотезу высказали ЭрдёшПал ЭрдёшПолторы тысячи статей, пятьсот соавторов, ни дома, ни семьи, ни постоянной работы — сорок лет он ездил из университета в университет с одним чемоданом. и Туран в 1936-м; Рот доказал случай длины 3 (1953), Семереди — длины 4 (1969) и общий случай (1975) чрезвычайно сложной комбинаторной конструкцией. Позже появились ещё два принципиально разных доказательства: эргодическое (Фюрстенберг, 1977 — он перевёл задачу на язык динамических систем и доказал теорему о кратном возвращении) и аналитическое (Гауэрс, 1998–2001 — с явными оценками и введением норм, носящих теперь его имя).
И вот в чём беда. Простые числа имеют плотность нуль: их доля среди первых $N$ чисел равна примерно $1/\ln N\to0$. Теорема Семереди к ним неприменима, и никакое её усиление в лоб не помогает: существуют множества нулевой плотности вовсе без прогрессий длины 3.
Ход Грина и Тао
Бен Грин и Теренс Тао в 2004 году (публикация в «Annals of Mathematics», 2008) нашли обход, который стал образцом целого жанра.
Принцип переноса. Теорема Семереди верна не только для множеств, плотных в $\mathbb{N}$, но и для множеств, плотных внутри достаточно случайно устроенного объемлющего множества. Точнее: если построить весовую функцию $\nu$ (меру), которая (а) мажорирует индикатор простых с точностью до постоянного множителя и (б) удовлетворяет определённым условиям псевдослучайности — так называемым условиям линейных форм и корреляции, — то относительный вариант теоремы Семереди применим.
Где взять такую меру. Здесь в дело идут решётные веса Голдстона — Йылдырыма: конструкция из теории решёт (потомок большого решета Линника и решета СельбергаАтле СельбергВ оккупированной Норвегии в одиночку доказал, что положительная доля нулей дзета-функции лежит на критической прямой; потом получил элементарное доказательство теоремы о простых числах — и рассорился из-за…), которая приписывает числу вес, тем больший, чем меньше у него мелких простых делителей. Относительно такой меры простые имеют положительную плотность — примерно константу вместо $1/\ln N$. Псевдослучайность меры проверяется методами аналитической теории чисел.
Схема целиком выглядит так:
$$\underbrace{\text{простые}}_{\text{плотность }0}\ \subset\ \underbrace{\text{почти-простые с весами}}_{\text{псевдослучайная мера }\nu}\quad\Longrightarrow\quad \underbrace{\text{относительная теорема Семереди}}_{\text{прогрессии есть}}$$
Замечательное свойство доказательства: оно не даёт никакого способа найти прогрессию. Утверждается существование, а конкретные длинные прогрессии по-прежнему ищут перебором на компьютерах. Рекорд на сегодня — прогрессия из 27 простых чисел (найдена в 2019 году); прогрессия из 26 членов, найденная в 2010-м, начинается с числа 43 142 746 595 714 191 и имеет разность 23 681 770 · 23 #, где $23\#$ — произведение простых до 23.
Разность длинной прогрессии из простых обязана делиться на все простые, не превосходящие её длины, — иначе один из членов делился бы на такое простое. Отсюда и огромные разности: для длины 27 разность не меньше $23\#\approx2\cdot10^{8}$.
Что было дальше
Тао получил Филдсовскую медаль в 2006 году — в том числе за эту работу.
Грин — Тао — Циглер (2010–2012) обобщили результат на произвольные системы линейных уравнений: например, доказано, что существует бесконечно много четвёрок простых вида $p,\ p+d,\ p+2d,\ p+3d$ вместе с $d$ вида, задаваемого линейно, — и вообще получен ответ почти для всех систем, кроме тех, что содержат «бинарные» конфигурации. Гипотеза о простых-близнецах и гипотеза ГольдбахаХристиан ГольдбахПрофессиональным математиком не был; его роль оказалась важнее — он читал Ферма и не давал Эйлеру покоя. Гипотеза, высказанная им на полях письма, не доказана 283 года. как раз бинарны — и потому остаются вне досягаемости.
Ограниченные промежутки. В 2013 году Чжан Итан, до того не имевший постоянной академической позиции, доказал, что существует бесконечно много пар простых, отличающихся не более чем на 70 миллионов. Через несколько месяцев Джеймс Мейнард и независимо Тао упростили и усилили метод, а коллективный проект Polymath довёл границу до 246. До гипотезы о близнецах (граница 2) остаётся сделать шаг, который пока никому не даётся: мешает уже упоминавшийся паритетный барьер решётных методов.
Открытая гипотеза Эрдёша. Если $\sum_{a\in A}1/a=\infty$, то $A$ содержит сколь угодно длинные прогрессии. Из неё следовала бы и теорема Грина — Тао (поскольку $\sum1/p=\infty$ по Эйлеру), и многое сверх того. Доказан пока лишь случай прогрессий длины 3 (Блум и Сисаск, 2020) — и это считается крупным достижением.
Задача. Докажите, что если $p,\ p+d,\ p+2d,\ p+3d,\ p+4d$ — пять простых чисел и $p>5$, то $d$ делится на 2, 3 и 5, то есть на 30.
(Указание: если $d$ не делится на простое $q\leqslant5$, то остатки $p,p+d,\dots$ по модулю $q$ пробегают все классы, значит одно из чисел делится на $q$; при $p>5$ это невозможно. Проверьте на прогрессии $7,37,67,97,127$: разность 30.)
Следующая точка: Дарем в Нью-Гэмпшире — где преподаватель начальных курсов докажет то, к чему не подступались с античности.