Братишка, ты цел?

Если смотреть на первые элементы последовательности простых чисел, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, кажется, что вот-вот поймешь ее секрет, увидишь зависимость, общую формулу, дающую следующие члены - то оказывающиеся по-соседству, то прыгающие сразу через несколько позиций натурального ряда. На самом деле, такой формулы не существует. При всей кажущейся простоте, в математике немного более загадочных и труднопостижимых объектов, чем простые числа.

Ряд простых чисел постепенно становится все более редким. Если взять отрезок фиксированной длинны и перемещать его вперед по числовой оси, он все реже будет «зацеплять» хотя бы одно простое число. На самом деле верно даже более сильное утверждение: для отрезка любой длины можно уехать так далеко, что в какой-то момент в него не попадет ни одного простого числа! То есть щели между простыми числами могут быть сколь угодно большими.

Но иногда соседние числа идут буквально друг за другом. С помощью современного компьютера мы можем найти практически любое количество простых чисел, но этого мало, для того, чтобы понять, как они ведут себя еще дальше, для того, чтобы сделать выводы о поведении их ряда в целом. Именно с распределением простых чисел связано множество интересных гипотез.

Одна из них — гипотеза о простых числах-близнецах: существует бесконечное количество простых чисел, отличающихся друг от друга на 2. Таких пар много в начале ряда: 3 и 5, 5 и 7, 11 и 13, 17 и 19, 29 и 31. Наибольшие известные на сегодняшний день простые близнецы, полученные с помощью компьютерных вычислений, это 3,756,801,695,685×2

 — 1 и 3,756,801,695,685×2

+ 1. Но будут ли простые близнецы встречаться сколь угодно далеко, до сих пор неизвестно.

На самом деле до недавнего времени не было ответа на более простой вопрос: верно ли, что расстояния между соседними простыми числами растут с ростом простых чисел? Используя аналогию с линейкой, верно ли, что для любой линейки, начиная с какого-то момента, она начнет зацеплять не больше одного простого числа за раз? Разумеется, если гипотеза о числах близнецах верна, то ответ на этот вопрос отрицательный.

Ответ (разумеется, отрицательный) на этот более простой вопрос впервые дал малоизвестный математик Итан Чжан из Университета Нью-Гэмпшира.

Чжана, опубликованная в мае 2013 года в научном журнале Annals of Mathematics оказалась полнейшей неожиданностью для математического сообщества. Чжану удалось сделать самый существенный прорыв в понимании поведения последовательных простых чисел за последние несколько сотен лет.

Чжан доказал, что существует бесконечное количество пар подряд идущих простых чисел, отстоящих друг от друга на 70 миллионов. 70 000 000 это еще не 2, что требовалось бы для доказательства гипотезы о простых близнецах, но уже и далеко не бесконечность.

70 000 000: Итан Чжан

В основе доказательства Чжана лежит специальный объект — так называемый подтверждающий гребень.
Назовем гребнем упорядоченное множество различных неотрицательных целых чисел {h₁....h_k}. Его можно представлять себе как расческу шириной в h_k зубьев, у которой выломаны все зубья, кроме тех, которые стоят на позициях с номерами h_i. Мы хотим двигать гребень по натуральному ряду и смотреть, попадают ли одновременно все его зубья на простые числа, другими словами, являются ли для данного n все числа вида n+h₁,...,n+h_k простыми.

Возьмем простейший пример, гребень вида {0, 1}. В таком гребне k = 2, h₁ = 0, h₂=1. Число 1 по определению не считается простым, так что гребень интересно примерять к натуральным числам начиная со второй позиции. Тогда его зубцы укажут на 2 и 3 — оба эти числа простые. Но очевидно, что если двигать расческу дальше, то один из ее зубцов будет обязательно указывать на четное число большее 2-х, которое не является простым. Неинтересный случай.
А что, если взять гребень {0, 2}? Ясно, что оба его зубца будут попадать на простые числа, пока будут находиться те самые пары простых близнецов. Из этих примеров можно сделать два вывода. Во-первых, изучение свойств «гребней» тесно связано с исходной задачей (точнее, они эквивалентны). Во-вторых, среди гребней есть такие, которые, как {0,1} изначально неинтересны, потому что какой-то из их зубцов обязательно будет указывать на составное число. Можно ли заранее описать класс интересных гребней и дальше изучать именно их? Оказывается, — и это самое удивительное — да.

Гребень называется подтверждающим, если для любого простого числа p множество остатков от деления

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

могли бы попадать на наборы, состоящие только из простых чисел. Почему?

Давайте предположим, что наш гребень — не подтверждающий. Значит, для какого-то простого числа

 остатки от деления

на p пробегают все значения от 0 до 

. Продвинем гребень на любую позицию

. Его зубья указывают на числа

. Пусть остаток от деления

 на 

 равен 

. Так как гребень у нас не подтверждающий, среди в наборе зубцов есть один, скажем

, остаток от деления которого на 

 равен

. Тогда в сдвинутом на 

-ю позицию гребне этот зубец укажет на число

, остаток которого при делении на 

 равен

. Значит, этот зубец указывает на число делящееся на 

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

, приходится на составное число.

Кстати, гребень

- как раз самый простой пример не подтверждающего гребня. Остатки от деления его зубьев на наименьшее простое число, 2, пробегают все значения - и 0 и 1. Именно поэтому куда не подвинь гребень на натуральном ряду начиная со второй позиции, один из зубцов будет составным числом.

Тут, конечно, возникает вопрос - а существуют ли вообще подтверждающие гребни? Ответить на этот вопрос не очень просто, поэтому читателю придется поверить нам на слово: такие гребни есть. Более того, главная теорема, доказанная Итаном Чжаном состоит в том, что если

некоторый подтверждающий гребень, в котором есть как минимум 3,5 миллиона зубцов, то при его сдвигах по натуральному ряду будет бесконечно много ситуаций, когда хотя бы два зубца указывают на простые числа. Из этого следует, что существует бесконечно много пар подряд идущих простых чисел, расстояние между которыми не превышает 70 миллионов.

Действительно, чтобы проверить этот переход достаточно построить подтверждующий гребень, в котором будет не меньше 3.5 миллионов зубцов, но расстояние между крайними зубцами не превышает 70 миллионов. Оказывается, что гребень, состоящий из зубьев, стоящих только на простых позициях, но больших, чем общее число зубцов в нем, является подтверждающим. А сколько можно найти простых чисел между 3,5x10

и 7x10

? Согласно неравенствам, доказанном Пьером Дюсаром в 2010 году п(x), число простых чисел, не превышающих данное число x, при достаточно больших x (как в нашем случае) можно оценить с двух сторон вот таким образом:

Из первого неравенства следует, что число простых чисел в пределах 70 миллионов превышает 4 миллиона. Из второго - что количество простых чисел, меньших 3,5 миллионов (они нам не подходят для построения подтверждающего гребня) не превышает 215 109. Значит, количество подходящих для построение подтверждающего гребня, то есть лежащих в пределах между 3 500 000 и 70 000 000 простых чисел - как минимум 4 000 000 - 215 109 = 3 784 891, а это больше, чему нужные по условия теоремы 3,5 миллиона.

Ну что же, вот и возьмем все простые числа между 3,5x10⁶ и 7x10⁷, они образуют подтверждающий гребень, в котором достаточно много зубцов (не меньше 3,5 миллионов), но расстояние между самым маленьким и самым большим зубцами не превышает 70 миллионов. Из теоремы Чжана следует, что сдвигая его по натуральному ряду, мы будем бесконечно часто натыкаться на лежащие в этих рамках пары простых чисел. Значит, мы доказали, что есть бесконечное число пар соседних простых чисел, лежащих на расстоянии не более 70 миллионов друг от друга - это можно считать значительно ослабленной версией гипотезы о близнецах.

Даже на этом этапе видно, что результат Итана Чжана можно немного улучшить. Переход от его теоремы о подтверждающем гребне к оценке минимальной границы, в которой можно найти бесконечное число пар соседних простых чисел основан на относительно грубых прикидках. Ясно, что американо-китайский математик выбрал 70 миллионов как некое удобное круглое число, его главное задачей было доказать, что расстояние между соседними простыми числами не растет со временем до бесконечности, и это было блестяще произведено. А вопросы об улучшении оценки, и, возможно, последующем доказательстве гипотезы о простых близнецах были делом дальнейшей работы - об этом Чжан прямо пишет в своей статье.

4680: Polymath project

И действительно, если бы Чжан не гнался за круглым числом, он мог бы указать в качестве оценки чуть меньшее число, а именно 59 874 594. Для уточнения оценки достаточно найти первое простое число, больше 3,5 миллионов (это 3 500 017), отсчитать от него 3,5 миллиона подряд идущих простых чисел (получится 63 374 611) и вычислить разницу между ними - с этим легко справится любой лэптоп.
Вспомним, что для того, чтобы перейти от теоремы Чжана к оценке максимального расстояния между соседними простыми числами, нужно построить как можно более узкий  подтверждающий гребень, в котором было бы 3,5 миллиона зубцов. Чжан воспользовался самым простым методом: если взять в гребень 3,5 миллиона подряд идущих простых чисел, каждое из которых больше 3,5 миллионов, гребень автоматически получится подтверждающим. Если же взять цепочку из 3,5 миллионов подряд идущих простых чисел, первое из которых меньше 3,5 миллионов - гребень может получиться уже, но гарантии, что он окажется подтверждающим нет.
Пусть p_n - ряд простых чисел. Обозначим H_m множество из 3,5 миллионов подряд идущих простых чисел, начиная с p_m. Гребень Чжана - H₂₅₀₁₅₁, так как простое число с порядковым номером 250151, это 3 500 017, и это первое простое число, большее 3,5 миллионов. Если найти подтверждающий гребень H_m с m<250151, он будет уже, а значит даст улучшенный результат.
30 мая 2013 года австралийский математик Скотт Морисон опубликовал запись в блоге SBSEMINAR, объединяющем нескольких недавних аспирантов-математиков Беркли Морисон с помощью компьютерных вычислений доказал, что гребень H₁₂₅₀₇₅ - подтверждающий. Его ширина, 59 470 640, дала новую оценку на асимптотически максимальное расстояние между соседними простыми числами, улучшив предыдущую примерно на 400 000.
Как заметил в своей записи сам Морисон, дальнейшие улучшения должны основываться не столько на поиске более узких подтверждающих гребней с 3,5 миллионами зубцов, сколько на ослаблении самой константы 3,5 миллиона из теоремы Чжана.
Буквально через несколько дней австралийский математик, лауреат Филдсовской медали Теренс Тао доказал, что количество зубцов подтверждающего гребня в теореме Чжана может быть уменьшено на порядок - до 341 640. Несложно построить такой гребень ширины 4 982 086 - и это десятикратно улучшает результат Чжана.

Тао было очевидно, что Итан Чжан придумал метод, с помощью которого можно все дальше и дальше улучшать оценку асимптотически максимального расстояния между соседними простыми числами, постепенно приближаясь к 2, то есть к проверке гипотезы гипотезу о простых близнецах. Однако такая работа требовала значительных ресурсов (в том числе и вычислительных) и заниматься ей эффективнее всего могла бы коллаборация, включающая множество математиков. К счастью, среда для такой совместной работы была уже создана и с успехом опробована другим филдсовским лауреатом, британцем Тимоти Гауэрсом. В 2009 году Гауэрс запустил онлайн проект Polymath project, и пригласил коллег со всего мира принять участие в поиске комбинаторного доказательства одного из вариантов

.

В итоге доказательство было найдено за несколько месяцев, результаты были опубликованы в двух работах, подписанных псевдонимом D.H.J. Polymath, за которым скрывались имена более чем 40 исследователей. Среда проекта Polymath стала использоваться для решения других сложных математических задач, коллективная работа над которыми обещала быть плодотворной. За четыре года таких задач набралось семь, а  4 июня 2013 года Теренс Тао открыл очередной проект, polymath8, посвященный на этот раз

. И дело пошло неожиданно здорово, куда лучше, чем кто-либо мог ожидать. “Порой оценка улучшалась каждые полчаса”, -

Теренс Тао в интервью изданию Quanta.

Работа шла по двум направлениям - уменьшению числа зубцов нужного для “вычесывания” простых чисел подтверждающего гребня и поиску самых узких гребней с таким количеством зубцов. Первая задача была более теоретической и требовала достаточно глубоких математических рассуждений, вторая была чисто расчетной, но участники Polymath Project быстро продвигались в обоих направлениях. К концу июля того же 2013 года было доказано, что есть бесконечно много пар подряд идущих простых чисел, расстояние между которыми не превосходит 4 680. Эти пары можно “вычесать” из натурального ряда подтверждающим гребнем всего с 632 зубцами (процесс его построения можно увидеть

). Исходная оценка Чжана была улучшена примерно в 15 тысяч раз!

600: Джеймс Мэйнард

В ноябре 2013 года, в самый разгар работы проекта polymath8 в истории случился крутой поворот. В дело вмешался 27-летний британский математик Джэймс Мэйнард, только что защитивший диссертацию в Оксфорде и теперь занимавший постдокторскую позицию в университете Монреаля.

Мэйнард, по его собственному признанию, не следивший за происходящей на polymath8 гонкой, сумел улучшить не только результат, но и метод Чжана, которым пользовались участники коллаборации на Polymath project. А точнее Мэйнард нашел способ сделать более острым главный инструмент, который использовал в своей работе Чжан - алгоритм, разработанный в 2005 году математиками  Дэниелем Голдстоном, Яношом Пинтцем и Семом Йилдиримом и по их фамилиям названный

.

В итоге Мэйнарду удалось доказать, что существует бесконечно много соседних простых чисел, лежащих на расстоянии

. Для этого потребовалось в некотором смысле изменить парадигму исходного доказательства, на которой основывались участники polymath8, хотя в конечном итоге Мэйнард тоже построил подтверждающий гребень: на этот раз шириной 600 и состоящий всего из 105 зубцов. Кроме того, молодой математик доказал, что для любого n можно найти константу C, такую что найдется бесконечно много наборов n подряд идущих простых числел, лежащих в пределах отрезка длины C.

Любопытно, что Мэйнрад начал работать над своим результатом еще до того, как была опубликована статья Чжана; их методы происходят из общего источника - алгоритма GPY, и почти одновременное, с разницей в несколько месяцев, публикация оценки на расстояние между соседними простыми числами - не более, чем совпадение.

Как раз в то время, когда Мэйнард выложил свою статью в интернет, участники проекта polymath8 под руководством Тэренса Тао заканчивали длившуюся уже несколько месяцев подготовку к публикации пространной работы (ее длина составляла более полутора сотен страниц, в три раза больше, чем в работе Итана Чжана), которая должна была описывать полученную ими оценку - 4680. Но возникший словно из ниоткуда (как, впрочем, и работа Итана) результат Мэйнарда перепутал все карты. Он означал, что проект polymath8 в его текущей инкарнации исчерпал себя: собравшееся вокруг него математическое коммьюнити могло теперь заняться улучшением окончательной оценки на основе нового, более эффективного метода.

246: Polymath8b

В день выхода препринта работы Джеймса Мэйнарда Теренс Тао опубликовал в своем личном блоге

 с предложением запустить новый проект, который был бы посвящен улучшению оценки на асимптотическое максимальное расстояние между соседними простыми числами на основе нового подхода Мэйнарда. Первый, “домэйнардский” этап коллаборации получил название polymath8a, второй, только что начавшийся - polymath8b.

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

Если взглянуть на таймлайн проекта polymath8b, можно увидеть, что первые улучшения основного результата появлялись уже через неделю: новый гребень с 102 зубцами имел ширину 576 (результат Дэида Кларка и Нормана Джарвиса). В начале следующего года, 6 января 2014, был найден гребень из 54 зубцов шириной 270. А наилучший на сегодняшний день результат был достигнут в апреле 2014 года Пэйсом Нильсеном из университета Брайгама Янга в Юте. Это - гребень из 50 зубцов шириной 246.
Итак, на сегодняшний день человечеству доподлинно известно, что если взять отрезок длиной 246 и сдвигать его вдоль натурального ряда до бесконечности, в нем время от времени будут попадаться пары подряд идущих простых чисел. Ретроспективная статья, посвященная итогам работы проекта polymath8 была опубликована (разумеется, под псевдонимом D.H.J. Polymath) в конце сентября 2014 года. Авторы подводят итог полуторалетней работы “Новая техника позволила еще немного снизить оценку H₁ до 246, но дальнейшее улучшение результата судя по всему потребует огромного объема вычислений и к концу мая 2014 года мы с удовольствием объявили промежуточную победу и приступили к подготовке результатов polymath8b к публикации”.

2?

К сожалению, возможности методов, предложенных Чжаном и Мэйнардом ограничены. С их помощью в лучшем случае удастся доказать, что расстояние между соседними простыми числами асимптотически ограничено шестью. Более того, эта оценка уже получена участниками polymath8b, правда, при условии, что выполнена некоторая гипотеза, описывающая распределение простых чисел и называющаяся обобщенной гипотезой Эллиота-Хальберстама.
Казалось бы, теперь мы подошли вплотную к проверке гипотезы о простых близнецах, ведь 246 (а тем более, 6) неизмеримо ближе к 2, чем 70 000 000, полученные Итаном Чжаном. На самом деле, между ними такая же пропасть, как между 70 миллионами и бесконечностью, на предоление которой у людей ушло около 200 лет. Коллективное улучшение оценки оказалось чрезвычайно плодотворным, совместный труд хорош, когда надо прорубать тропинку в глухих зарослях. Но для того, чтобы построить мостик через пропасть, нам нужен еще один упавший с неба неожиданный результат, прозрение, какое было у Итана Чжана и Джеймса Мэйнарда.
“У меня есть чувство, что для доказательства гипотезы о простых близнецах нам все еще недостает огромного концептуального прорыва”, - сказал Джэймс Мэйнард в интервью Quanta Mag. 

Сергей Немалевич