Интервалы между простыми числами

Простое число — натуральное число ${\displaystyle p>1}$, имеющее только два делителя ${\displaystyle 1}$ и ${\displaystyle p}$: ${\displaystyle 2,3,5,7,11,13,17,19...}$^[1].

Разность, или интервал между соседними простыми числами — ${\displaystyle g_{n}=p_{n+1}-p_{n}}$.

Простые близнецы — два простых числа с разностью, равной ${\displaystyle 2}$: ${\displaystyle 3}$ и ${\displaystyle 5}$, ${\displaystyle 5}$ и ${\displaystyle 7}$, ${\displaystyle 11}$ и ${\displaystyle 13}$…

Обобщённые близнецы — пары соседних простых чисел с разностью ${\displaystyle 2m}$, где ${\displaystyle m}$ — фиксированное натуральное число. Для ${\displaystyle m=2}$, например, это числа ${\displaystyle 13}$ и ${\displaystyle 17}$, ${\displaystyle 19}$ и ${\displaystyle 23}$, ${\displaystyle 43}$ и ${\displaystyle 47}$ и др.^[2]

Первые ${\displaystyle 30}$ интервалов между простыми числами следующие: ${\displaystyle 1,2,2,4,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14...}$ В онлайн-энциклопедии целочисленных последовательностей OEIS данная последовательность представлена под номером A001223^[3].

Распределение простых чисел — раздел теории чисел, в котором изучаются закономерности распределения простых чисел среди натуральных чисел. Исследование распределения простых чисел начинается с Эйлера. Он доказал (1744 г.), что ${\displaystyle {\frac {\pi (x)}{x}}\to 0}$ при ${\displaystyle x\to \infty }$, где ${\displaystyle \pi (x)}$ — число простых чисел, меньших, чем ${\displaystyle x}$. Вопросом о распределении простых чисел занимались Гаусс и Лежандр. Гаусс предложил назвать ${\displaystyle \pi (x)}$ функцией Эйлера и обозначить её ${\displaystyle \varphi (x)}$ (1801 г.). Письмо Гаусса (1849 г.), в котором он выдвигает идею: ${\displaystyle {\frac {\pi (x)}{x}}\approx {\frac {1}{\ln x}}}$, стало известным лишь в 1863 году. Лежандр улучшил результат Гаусса и сформулировал асимптотический закон ${\displaystyle \pi (x)={\frac {x}{\ln x-1,08366}}}$.

Закон был впервые доказан в 1896 году одновременно Адамаром и Валле-Пуссеном. Элементарное доказательство удалось найти только в 1948 году Эрдёшу и Сельбергу^[4].

Проблема поведения функции ${\displaystyle \pi (x)}$ при ${\displaystyle x\to \infty }$ является одной из наиболее трудных и интересных проблем теории чисел. Она заключается в поиске наилучшего асимптотического выражения функции ${\displaystyle \pi (x)}$, обозначающей число простых чисел, не превосходящих ${\displaystyle x}$, а также функции ${\displaystyle \pi (x;d,l)}$, обозначающей число простых чисел, не превосходящих ${\displaystyle x}$ в арифметической прогрессии ${\displaystyle dn+l}$ при ${\displaystyle 1\leqslant l\leqslant d,n=0,1,2,...}$, для растущих вместе с ${\displaystyle x}$ значений ${\displaystyle d}$.

При рассмотрении разности между простыми числами выделяют следующие вопросы:

• поведение разности между соседними простыми числами;
• поведение разности между парами простых чисел разности ${\displaystyle 2k}$;
• разность между числами систем ${\displaystyle p,p+u_{1},...,p+u_{m}}$ из ${\displaystyle m+1}$ простых чисел, лежащих на отрезке ${\displaystyle [1,x]}$^[5].

Существует бесконечное множество простых чисел. Это утверждение приведено в книге Евклида «Начала», кн. IX, III в. до н. э. В течение более 2000 лет это был единственный строго доказанный результат, относящийся к распределению простых чисел^[6].

Теорема описывает асимптотику распределения простых чисел, которая утверждает, что функция распределения простых чисел ${\displaystyle \pi (x)}$ растёт с увеличением ${\displaystyle x}$ как ${\displaystyle {\frac {x}{\ln x}}}$, то есть: ${\displaystyle {\frac {\pi (x)}{x/\ln x}}\to 1}$, когда ${\displaystyle n\to \infty .}$ Это означает, что у случайно выбранного числа от 1 до ${\displaystyle x}$ вероятность оказаться простым числом примерно равна ${\displaystyle {\frac {1}{\ln x}}}$.

Также эта теорема может быть эквивалентным образом переформулирована для описания поведения ${\displaystyle k}$-го простого числа ${\displaystyle p_{k}}$: она утверждает, что ${\displaystyle p_{k}\sim k\ln k,\quad k\to \infty }$(здесь и далее запись ${\displaystyle f\sim g}$ означает, что ${\displaystyle f/g\to 1}$, когда аргумент функций стремится к бесконечности).

Пусть ${\displaystyle \pi (x)}$ — число простых чисел, меньших ${\displaystyle x}$. Тогда при ${\displaystyle x\geqslant 1}$ выполняется равенство ${\displaystyle \pi (x)={\text{li}}\,x+O(xe^{-C{\sqrt {\ln x}}})}$, где ${\displaystyle O}$ используется в смысле O большое, ${\displaystyle C}$ — некоторая положительная постоянная, а ${\displaystyle {\text{li}}\,x}$ — интегральный логарифм ${\displaystyle x}$. 

Из этой теоремы следует справедливость гипотезы Гаусса о распределении простых чисел, то есть при ${\displaystyle x\to +\infty }$ интегральный логарифм ${\displaystyle {\text{li}}\,x\sim {\frac {x}{\ln x}}}$^[7].

Каждая бесконечная арифметическая прогрессия, первый член и разность которой — натуральные взаимно простые числа, содержит бесконечное число простых чисел.

Постулат Бертрана утверждает, что для любого ${\displaystyle k}$ всегда существует хотя бы одно простое число между ${\displaystyle k}$ и ${\displaystyle 2k}$, поэтому, в частности, ${\displaystyle p_{n+1}<2p_{n}}$, откуда ${\displaystyle g_{n}<p_{n}}$. Постулат был сформулирован в качестве гипотезы в 1845 году французским математиком Бертраном (проверившим её до ${\displaystyle n=3000000}$) и доказан в 1852 году Чебышёвым. Рамануджан в 1919 году нашёл более простое доказательство и доказал, что число простых чисел в интервале ${\displaystyle n<p<2n}$ можно ограничить снизу неубывающей последовательностью, которая стремится к бесконечности, такой, что в простых числах Рамануджана достигается равенство. Эрдёш в 1932 году ещё более упростил доказательство этого постулата.

В 1919 году В. Брун нашёл метод, который позволил получить ожидаемую оценку сверху для арифметической прогрессии ${\displaystyle dn+l}$, первый член которой ${\displaystyle l}$ и разность ${\displaystyle d}$ взаимно просты. Этот метод, как и его модификация, предложенная А. Сельбергом в 1947 году, показывает, что для всех ${\displaystyle 1\leqslant d<x,1\leqslant l\leqslant d,(l,d)=1}$, имеет место неравенство сверху ${\displaystyle \pi (x;d,l)\ll {\frac {x}{\varphi (d)\log {\tfrac {x}{d}}}}}$ с абсолютной константой ${\displaystyle \ll }$. Но эти методы не дают оценок снизу^[8].

Хохайзель первым показал, что существует такое постоянное ${\displaystyle \theta <1}$: ${\displaystyle \pi (x+x^{\theta })-\pi (x)\sim {\frac {x^{\theta }}{\ln x}}}$ при ${\displaystyle x\to +\infty }$; отсюда следует, что ${\displaystyle g_{n}<p_{n}^{\theta },}$ для достаточно большого ${\displaystyle n}$. Отсюда следует, что интервалы между простыми числами становятся сколь угодно меньше по отношению к простым числам: частное ${\displaystyle {\frac {g_{n}}{p_{n}}}}$ стремится к нулю при ${\displaystyle n\to \infty }$.

Он получил возможное значение ${\displaystyle 32999/33000}$ для ${\displaystyle \theta }$. Эта оценка была улучшена до ${\displaystyle 249/250}$ Хайльброном, и до ${\displaystyle \theta ={\frac {3}{4}}+\varepsilon }$ для любого ${\displaystyle \varepsilon >0}$ Чудаковым^[9].

Основное улучшение было получено Ингамом, который показал, что если ${\displaystyle \zeta (1/2+it)=O(t^{c})}$ для некоторой константы ${\displaystyle c>0}$, где O используется в смысле O большое, то ${\displaystyle \pi (x+x^{\theta })-\pi (x)\sim {\frac {x^{\theta }}{\ln x}}}$ для любого ${\displaystyle \theta >{\frac {1+4c}{2+4c}}}$. Здесь ${\displaystyle \zeta }$ обозначает дзета функцию Римана, Известно, что допускается ${\displaystyle c>{\frac {1}{6}}}$, откуда в качестве ${\displaystyle \theta }$ можно взять любое число, большее ${\displaystyle {\frac {5}{8}}}$. Из результата Ингама сразу следует, что всегда существует простое число между числами ${\displaystyle n^{3}}$ и ${\displaystyle (n+1)^{3}}$ для достаточно больших ${\displaystyle n}$. Заметим, что ещё не доказана гипотеза Линделёфа, которая утверждает, что в качестве c может быть выбрано любое положительное число, но из неё следует, что всегда существует простое число между ${\displaystyle n^{2}}$ и ${\displaystyle (n+1)^{2}}$ для достаточно больших ${\displaystyle n}$. Если эта гипотеза верна, то, возможно, необходима ещё более строгая гипотеза Крамера. Одним из достигнутых приближений к гипотезе Лежандра является доказанный факт о том, что ${\displaystyle g(p_{n})=O({p_{n}}^{\frac {21}{40}})}$.

17 апреля 2013 года Итан Чжан сообщил о доказательстве того, что существует бесконечно много пар простых чисел, которые отличаются не более чем на ${\displaystyle 70}$ миллионов. Работа была принята в Анналы математики в мае 2013 года. 30 мая 2013 года австралийский математик Скотт Моррисон сообщил о снижении оценки до ${\displaystyle 59470640}$. Через несколько дней австралийский математик, лауреат Филдсовской медали Теренс Тао доказал, что граница может быть уменьшена на порядок — до ${\displaystyle 4982086}$^[10].

В ноябре 2013 года 27-летний британский математик Джеймс Мейнард применил алгоритм GPY, разработанный в 2005 году, и доказал, что существует бесконечно много соседних простых чисел, лежащих на расстоянии не более ${\displaystyle 600}$ друг от друга. В день выхода препринта работы Джеймса Мейнарда Теренс Тао опубликовал в личном блоге пост с предложением запустить новый проект, и уже через неделю оценка была снижена до ${\displaystyle 576}$, а 6 января 2014 года — до ${\displaystyle 270}$. Наилучший научно доказанный результат был достигнут в апреле 2014 года Пэйсом Нильсеном из университета Брайгама Янга в Юте — ${\displaystyle 246}$^[11].

Р. Ранкин доказал, что существует константа ${\displaystyle c>0}$ такая, что неравенство ${\displaystyle g_{n}>{\frac {c\cdot \ln n\cdot \ln \ln n\cdot \ln \ln \ln \ln n}{(\ln \ln \ln n)^{2}}}}$ сохраняется для бесконечно многих значений ${\displaystyle n}$. Наилучшее известное значение для ${\displaystyle c}$ — это ${\displaystyle c=2e^{\gamma }}$, где ${\displaystyle \gamma }$ — постоянная Эйлера-Маскерони.

Гипотеза Римана утверждает:

Все нетривиальные нули дзета-функции имеют вещественную часть, равную ${\displaystyle {\frac {1}{2}}}$, то есть являются комплексными числами, расположенными на прямой ${\displaystyle \operatorname {Re} s={\frac {1}{2}}}$.

Дзета-функция Римана ${\displaystyle \zeta (s)}$ определена для всех комплексных ${\displaystyle s\neq 1}$ и имеет нули в отрицательных чётных, то есть ${\displaystyle 0=\zeta (-2)=\zeta (-4)=\zeta (-6)\dots }$; такие нули называются тривиальными^[12].

С помощью гипотезы Римана доказано, что ${\displaystyle d_{n}\ll {\sqrt {p_{n}}}\log {p_{n}}}$, а некоторые эвристические рассуждения показывают, что, вероятно, справедлива оценка ${\displaystyle d_{n}\ll \log ^{2}{p_{n}}}$. Лучшей к 1983 году является оценка ${\displaystyle d_{n}\ll p_{n}^{\delta }}$, где ${\displaystyle \delta ={\tfrac {7}{12}}+\varepsilon ,\varepsilon >0}$, полученная М. Н. Хаксли (1973) по методу большого решета.

Гипотеза Лежандра гласит, что для любого ${\displaystyle n\geqslant 2}$ найдётся простое число в интервале ${\displaystyle n^{2}<p<(n+1)^{2}}$. Гипотеза Оппермана и гипотеза Андрицы задают такой же порядок роста интервала, включающего хотя бы одно простое число.

Харальд Крамер доказал, что если гипотеза Римана верна, то интервалы ${\displaystyle g(p_{n})}$ удовлетворяют соотношению ${\displaystyle g(p_{n})=O({\sqrt {p_{n}}}\ln p_{n})}$. Позже он предположил, что интервалы растут гораздо меньше. Он предположил, что ${\displaystyle g(p_{n})=O(\ln ^{2}p_{n}).}$ Это подтверждают численные расчёты.

Эта гипотеза утверждает, что ${\displaystyle g(p_{n})<2{\sqrt {p_{n}}}+1.}$ Это слабое усиление гипотезы Лежандра.

Простые числа расположены в натуральном ряду крайне неравномерно. С одной стороны, известны очень большие простые числа-близнецы, например, такая пара: ${\displaystyle 242206083\cdot 2^{38880}-1}$, ${\displaystyle 242206083\cdot 2^{38880}+1}$. С другой стороны, натуральный ряд содержит длинные участки, состоящие только из составных чисел. Так, например, среди сотни натуральных чисел ${\displaystyle 1671800,...,1671900}$ нет ни одного простого числа. В натуральном ряду имеются сколько угодно большие отрезки, не содержащие простых чисел. Например, ${\displaystyle n-1}$ натуральных чисел вида ${\displaystyle n!+2,...,n!+n}$ для любого ${\displaystyle n\geqslant 2}$ являются составными числами.

Во второй тысяче ряда натуральных чисел имеется интервал, не имеющий простых чисел ${\displaystyle [1327;1361]}$ с разностью ${\displaystyle 34}$. Причём этот интервал удерживает свой рекорд разности до десятой тысячи. Лишь в девятой тысяче имеется второй интервал ${\displaystyle [8467;8501]}$ с такой же разностью, а в десятой — более длинный интервал ${\displaystyle [9551;9587]}$ (разность — ${\displaystyle 36}$), который и является наибольшим интервалом первых десяти тысяч.

Первые 81 максимальных интервалов приводятся в OEIS под номером A005669^[13].

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