Теорема о простых числах

В математике теорема о простых числах ( PNT ) описывает асимптотическое распределение простых чисел среди натуральных чисел. Он формализует интуитивную идею о том, что простые числа становятся менее распространенными по мере их увеличения, путем точного количественного определения скорости, с которой это происходит. Теорема была независимо доказана Жаком Адамаром. и Шарль Жан де ла Валле Пуссен в 1896 году с использованием идей Бернхарда Римана (в частности, дзета-функции Римана ).

Первое найденное такое распределение — π ( N ) ~ ⁠ N / log( N ) ⁠ , где π ( N ) — функция подсчета простых чисел (количество простых чисел, меньше или равное ) , а log( N ) — натуральный логарифм N N . Это означает, что для достаточно большого N вероятность того , что случайное целое число, не большее N, является простым, очень близка к 1/log( N ) . Следовательно, случайное целое число, содержащее не более 2 n цифр (при достаточно большом n ), примерно в два раза реже будет простым, чем случайное целое число, содержащее не более n цифр. Например, среди натуральных чисел, содержащих не более 1000 цифр, примерно одно из 2300 является простым ( log(10 ¹⁰⁰⁰ ) ≈ 2302,6 ), тогда как среди натуральных чисел длиной не более 2000 цифр примерно одно из 4600 является простым ( log(10 ²⁰⁰⁰ ) ≈ 4605,2 ). Другими словами, средний разрыв между последовательными простыми числами среди первых N целых чисел примерно равен log( N ) .

Заявление

График, показывающий отношение функции подсчета простых чисел π ( x ) к двум ее аппроксимациям, x / log x и Li( x ) . По мере увеличения x (обратите внимание, что ось x логарифмическая), оба отношения стремятся к 1. Отношение для x / log x сходится сверху очень медленно, тогда как отношение для Li( x ) сходится быстрее снизу.

Логарифмический график, показывающий абсолютную ошибку x / log x и Li( x ) , двух приближений к функции подсчета простых чисел π ( x ) . В отличие от отношения, разница между π ( x ) и x / log x неограниченно увеличивается с увеличением x . С другой стороны, Li( x ) − π ( x ) меняет знак бесконечное число раз.

Пусть π ( x ) будет функцией подсчета простых чисел, определяемой как количество простых чисел, меньших или равных x , для любого действительного числа x . Например, π (10) = 4 , потому что есть четыре простых числа (2, 3, 5 и 7), которые меньше или равны 10. Тогда теорема о простых числах утверждает, что x / log x является хорошим приближением к π ( x ) (где log здесь означает натуральный логарифм) в том смысле, что двух функций предел частного π ( x ) и x / log x при x неограниченном увеличении равен 1:

$\lim _{x\to \infty }{\frac {\;\pi (x)\;}{\;\left[{\frac {x}{\log(x)}}\right]\;}}=1,$

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

$\pi (x)\sim {\frac {x}{\log x}}.$

Эти обозначения (и теорема) ничего не говорят о пределе разности двух функций при x неограниченном увеличении . Вместо этого теорема утверждает, что x / log x приближает π ( x ) в том смысле, что относительная ошибка этого приближения приближается к 0 по мере x неограниченного увеличения .

Теорема о простых числах эквивалентна утверждению, что n- е простое число p _n удовлетворяет условию

$p_{n}\sim n\log(n),$

асимптотические обозначения, опять же, означают, что относительная ошибка этого приближения приближается к 0 по мере n неограниченного увеличения . Например, 2 × 10 ¹⁷ шестое простое число: 8  512  677  386  048  191  063 , и ( 2 × 10 ¹⁷ )log( 2 × 10 ¹⁷ ) округляется до 7 967 418 752 291 744 388 , относительная ошибка около 6,4%.

С другой стороны, следующие асимптотические соотношения логически эквивалентны:

${\begin{aligned}\lim _{x\rightarrow \infty }{\frac {\pi (x)\log x}{x}}&=1,\\\lim _{x\rightarrow \infty }{\frac {\pi (x)\log \pi (x)}{x}}&=1.\end{aligned}}$

Как указано ниже , теорема о простых числах также эквивалентна формуле

$\lim _{x\to \infty }{\frac {\vartheta (x)}{x}}=\lim _{x\to \infty }{\frac {\psi (x)}{x}}=1,$

где ϑ и ψ — первая и вторая функции Чебышева соответственно, а

$\lim _{x\to \infty }{\frac {M(x)}{x}}=0,$

где $M(x)=\sum _{n\leq x}\mu (n)$ – функция Мертенса .

История доказательства асимптотического закона простых чисел

Основываясь на таблицах Антона Фелькеля и Юрия Веги , Адриен-Мари Лежандр в 1797 или 1798 году предположила, что π ( a ) аппроксимируется функцией a / ( A log a + B ) , где A и B — неуказанные константы. Во втором издании своей книги по теории чисел (1808 г.) он затем сделал более точную гипотезу с A = 1 и B = -1,08366 . Карл Фридрих Гаусс задавался тем же вопросом в возрасте 15 или 16 лет «в 1792 или 1793 году», по его собственным воспоминаниям, в 1849 году. В 1838 году Петер Густав Лежен Дирихле придумал свою собственную аппроксимирующую функцию — логарифмический интеграл li( x ) (в несколько иной форме ряда, которую он сообщил Гауссу). Формулы Лежандра и Дирихле подразумевают одну и ту же предполагаемую асимптотическую эквивалентность π ( x ) и x / log ( x ), указанную выше, хотя оказалось, что приближение Дирихле значительно лучше, если рассматривать различия вместо частных.

В двух статьях 1848 и 1850 годов русский математик Пафнутий Чебышев попытался доказать асимптотический закон распределения простых чисел. Его работа примечательна использованием дзета-функции ζ ( s ) для действительных значений аргумента « s », как в работах Леонарда Эйлера еще в 1737 году. Статьи Чебышева предшествовали знаменитым мемуарам Римана 1859 года, и ему удалось в доказательстве несколько более слабой формы асимптотического закона, а именно, что если предел при стремлении x к бесконечности для π ( x ) / ( x / log( x )) вообще существует, то он обязательно равен единице. Ему удалось безоговорочно доказать, что это отношение ограничено сверху и снизу двумя явно заданными константами вблизи 1 для всех достаточно больших x . Хотя статья Чебышева не доказала теорему о простых числах, его оценки π ( x ) были достаточно сильными, чтобы он мог доказать постулат Бертрана о том, что существует простое число между n и 2 n для любого целого числа n ≥ 2 .

Важным документом, посвященным распределению простых чисел, были мемуары Римана 1859 года « О числе простых чисел, меньших заданной величины », единственная статья, которую он когда-либо писал на эту тему. Риман внес в эту тему новые идеи, главным образом, о том, что распределение простых чисел тесно связано с нулями аналитически расширенной дзета-функции Римана комплексной переменной. В частности, именно в этой работе зарождается идея применить методы комплексного анализа к исследованию действительной функции π ( x ) . Развивая идеи Римана, два доказательства асимптотического закона распределения простых чисел были независимо найдены Жаком Адамаром. и Шарль Жан де ла Валле Пуссен и появился в том же году (1896). В обоих доказательствах использовались методы комплексного анализа, устанавливающие в качестве основного шага доказательства, что дзета-функция Римана ζ ( s ) отлична от нуля для всех комплексных значений переменной s , которые имеют форму s = 1 + it с t > 0 .

В 20 веке теорема Адамара и Валле Пуссена также стала известна как теорема о простых числах. Было найдено несколько различных доказательств этого, в том числе «элементарные» доказательства Атле Сельберга. и Пол Эрдеш (1949). Оригинальные доказательства Адамара и Валле Пуссена длинные и тщательно продуманные; более поздние доказательства вводили различные упрощения за счет использования тауберовых теорем, но оставались трудными для понимания. Краткое доказательство было обнаружено в 1980 году американским математиком Дональдом Дж. Ньюманом . Доказательство Ньюмана, возможно, является самым простым известным доказательством теоремы, хотя оно и неэлементарно в том смысле, что использует интегральную теорему Коши из комплексного анализа.

Эскиз доказательства

Вот набросок доказательства, упомянутого в одной из лекций Теренса Тао . Как и большинство доказательств PNT, оно начинается с переформулировки проблемы в терминах менее интуитивной, но более эффективной функции подсчета простых чисел. Идея состоит в том, чтобы посчитать простые числа (или связанный с ними набор, например, набор степеней простых чисел) с весами , чтобы получить функцию с более гладким асимптотическим поведением. Наиболее распространенной такой обобщенной считающей функцией является функция Чебышева ψ ( x ) , определяемая формулой

$\psi (x)=\!\!\!\!\sum _{\stackrel {p^{k}\leq x,}{p{\text{ is prime}}}}\!\!\!\!\log p\;.$

Иногда это пишут как

$\psi (x)=\sum _{n\leq x}\Lambda (n)\;,$

где Λ ( n ) — функция Мангольдта , а именно

$\Lambda (n)={\begin{cases}\log p&{\text{ if }}n=p^{k}{\text{ for some prime }}p{\text{ and integer }}k\geq 1,\\0&{\text{otherwise.}}\end{cases}}$

Теперь относительно легко проверить, что PNT эквивалентно утверждению, что

$\lim _{x\to \infty }{\frac {\psi (x)}{x}}=1\;.$

Действительно, это следует из простых оценок

$\psi (x)=\sum _{\stackrel {p\leq x}{p{\text{ is prime}}}}\log p\left\lfloor {\frac {\log x}{\log p}}\right\rfloor \leq \sum _{\stackrel {p\leq x}{p{\text{ is prime}}}}\log x=\pi (x)\log x$

и (используя big O обозначение ) для любого ε > 0 ,

$\psi (x)\geq \!\!\!\!\sum _{\stackrel {x^{1-\varepsilon }\leq p\leq x}{p{\text{ is prime}}}}\!\!\!\!\log p\geq \!\!\!\!\sum _{\stackrel {x^{1-\varepsilon }\leq p\leq x}{p{\text{ is prime}}}}\!\!\!\!(1-\varepsilon )\log x=(1-\varepsilon )\left(\pi (x)+O\left(x^{1-\varepsilon }\right)\right)\log x\;.$

Следующий шаг — найти полезное представление для ψ ( x ) . Пусть ζ ( s ) — дзета-функция Римана. Можно показать, что ζ ( s ) связана с функцией фон Мангольдта Λ ( n ) и, следовательно, с ψ ( x ) соотношением

$-{\frac {\zeta '(s)}{\zeta (s)}}=\sum _{n=1}^{\infty }\Lambda (n)\,n^{-s}\;.$

Тонкий анализ этого уравнения и связанных с ним свойств дзета-функции с использованием преобразования Меллина и формулы Перрона показывает, что для нецелого числа x уравнение

$\psi (x)=x\;-\;\log(2\pi )\;-\sum \limits _{\rho :\,\zeta (\rho )=0}{\frac {x^{\rho }}{\rho }}$

где сумма ведется по всем нулям (тривиальным и нетривиальным) дзета-функции. Эта поразительная формула является одной из так называемых явных формул теории чисел и уже наводит на мысль о результате, который мы хотим доказать, поскольку член x (который считается правильным асимптотическим порядком ψ ( x ) ) появляется справа. -сторона, за которой следуют (предположительно) асимптотические члены низшего порядка.

Следующий шаг доказательства предполагает исследование нулей дзета-функции. Тривиальные нули −2, −4, −6, −8, ... можно обрабатывать отдельно:

$\sum _{n=1}^{\infty }{\frac {1}{2n\,x^{2n}}}=-{\frac {1}{2}}\log \left(1-{\frac {1}{x^{2}}}\right),$

который исчезает при больших x . Нетривиальные нули, а именно нули в критической полосе 0 ⩽ Re( s ) ⩽ 1 , потенциально могут иметь асимптотический порядок, сравнимый с основным членом x, если Re( ρ ) = 1 , поэтому нам нужно показать, что все нули имеют действительные значения. часть строго меньше 1.

Неисчезающее на Re( s ) = 1

Для этого примем как данность, что ζ ( s ) мероморфна Re в полуплоскости ( s ) > 0 и аналитична там, за исключением простого полюса в точке s = 1 , и что существует формула произведения

$\zeta (s)=\prod _{p}{\frac {1}{1-p^{-s}}}$

для Re( s ) > 1 . Эта формула произведения следует из существования уникальной простой факторизации целых чисел и показывает, что ζ ( s ) никогда не равняется нулю в этой области, так что ее логарифм определен там и

$\log \zeta (s)=-\sum _{p}\log \left(1-p^{-s}\right)=\sum _{p,n}{\frac {p^{-ns}}{n}}\;.$

Напишите s = x + iy ; затем

${\big |}\zeta (x+iy){\big |}=\exp \left(\sum _{n,p}{\frac {\cos ny\log p}{np^{nx}}}\right)\;.$

Теперь обратите внимание на тождество

$3+4\cos \phi +\cos 2\phi =2(1+\cos \phi )^{2}\geq 0\;,$

так что

$\left|\zeta (x)^{3}\zeta (x+iy)^{4}\zeta (x+2iy)\right|=\exp \left(\sum _{n,p}{\frac {3+4\cos(ny\log p)+\cos(2ny\log p)}{np^{nx}}}\right)\geq 1$

для всех х > 1 . Предположим теперь, что ζ (1 + iy ) = 0 . Конечно, y не равен нулю, поскольку ζ ( s ) имеет простой полюс в точке s = 1 . Предположим, что x > 1 , и пусть x стремится к 1 сверху. С $\zeta (s)$ имеет простой полюс в точке s = 1 и ζ ( x + 2 iy ) остается аналитическим, левая часть предыдущего неравенства стремится к 0, противоречие.

Наконец, мы можем заключить, что PNT эвристически верна. Чтобы строго завершить доказательство, необходимо преодолеть еще серьезные технические трудности, связанные с тем, что суммирование по дзета-нулим в явной формуле для ψ ( x ) сходится не абсолютно, а только условно и в смысле «главного значения». Существует несколько способов решения этой проблемы, но многие из них требуют весьма тонких комплексно-аналитических оценок. Книга Эдвардса предоставляет подробности. Другой метод — использовать тауберову теорему Икехары , хотя эту теорему доказать довольно сложно. Дж. Ньюман заметил, что для теоремы о простых числах не требуется полная сила теоремы Икехары, и можно обойтись частным случаем, который гораздо легче доказать.

Доказательство Ньюмана теоремы о простых числах

DJ Newman дает быстрое доказательство теоремы о простых числах (PNT). Доказательство является «неэлементарным», поскольку основано на комплексном анализе, но использует только элементарные методы из первого курса предмета: интегральную формулу Коши , интегральную теорему Коши и оценки комплексных интегралов. Вот краткая схема этого доказательства. Видеть для получения полной информации.

В доказательстве используются те же предварительные сведения, что и в предыдущем разделе, за исключением функции ${\textstyle \psi }$, функция Чебышева ${\textstyle \quad \vartheta (x)=\sum _{p\leq x}\log p}$ используется, который получается отбрасыванием некоторых членов ряда за ${\textstyle \psi }$. Легко показать, что PNT эквивалентна $\lim _{x\to \infty }\vartheta (x)/x=1$. Аналогично вместо $-{\frac {\zeta '(s)}{\zeta (s)}}$ функция $\Phi (s)=\sum _{p\leq x}\log p\,\,p^{-s}$ используется, который получается отбрасыванием некоторых членов ряда для $-{\frac {\zeta '(s)}{\zeta (s)}}$. Функции $\Phi (s)$ и $-\zeta '(s)/\zeta (s)$ отличаются функцией, голоморфной на $\Re s=1$. Поскольку, как было показано в предыдущем разделе, $\zeta (s)$ не имеет нулей в строке $\Re s=1$ , $\Phi (s)-{\frac {1}{s-1}}$ не имеет особенностей на $\Re s=1$.

Еще одна информация, необходимая для доказательства Ньюмана и являющаяся ключом к оценкам его простого метода, заключается в том, что $\vartheta (x)/x$ ограничен. Это доказывается остроумным и простым методом Чебышева.

Интегрирование по частям показывает, как $\vartheta (x)$ и $\Phi (s)$ связаны. Для $\Re s>1$,

$\Phi (s)=\int _{1}^{\infty }x^{-s}d\vartheta (x)=s\int _{1}^{\infty }\vartheta (x)x^{-s-1}\,dx=s\int _{0}^{\infty }\vartheta (e^{t})e^{-st}\,dt.$

Метод Ньюмана доказывает PNT, показывая интеграл

$I=\int _{0}^{\infty }\left({\frac {\vartheta (e^{t})}{e^{t}}}-1\right)\,dt.$

сходится, и поэтому подынтегральная функция обращается в ноль при $t\to \infty$, то есть ПНТ. В общем, сходимость несобственного интеграла не означает, что подынтегральная функция обращается в ноль на бесконечности, поскольку она может колебаться, но поскольку $\vartheta$ возрастает, это легко показать в этом случае.

Чтобы показать сходимость $I$, для $\Re z>0$ позволять

$g_{T}(z)=\int _{0}^{T}f(t)e^{-zt}\,dt$ и $g(z)=\int _{0}^{\infty }f(t)e^{-zt}\,dt$ где $f(t)={\frac {\vartheta (e^{t})}{e^{t}}}-1$

затем

$\lim _{T\to \infty }g_{T}(z)=g(z)={\frac {\Phi (s)}{s}}-{\frac {1}{s-1}}\quad \quad {\text{where}}\quad z=s-1$

что равно функции, голоморфной на прямой $\Re z=0$ .

Сходимость интеграла $I$, и, следовательно, PNT, доказывается, показывая, что $\lim _{T\to \infty }g_{T}(0)=g(0)$. Это предполагает изменение порядка пределов, поскольку можно записать ${\textstyle \lim _{T\to \infty }\lim _{z\to 0}g_{T}(z)=\lim _{z\to 0}\lim _{T\to \infty }g_{T}(z)}$ и поэтому классифицируется как тауберова теорема.

Разница $g(0)-g_{T}(0)$ выражается с использованием интегральной формулы Коши , а затем оказывается малой для $T$ большой путем оценки подынтегральной функции. Исправить $R>0$ и $\delta >0$ такой, что $g(z)$ голоморфен в области, где $|z|\leq R{\text{ and }}\Re z\geq -\delta$, и пусть $C$ быть границей этой области. Поскольку 0 находится внутри области, интегральная формула Коши дает

$g(0)-g_{T}(0)={\frac {1}{2\pi i}}\int _{C}\left(g(z)-g_{T}(z)\right){\frac {dz}{z}}={\frac {1}{2\pi i}}\int _{C}\left(g(z)-g_{T}(z)\right)F(z){\frac {dz}{z}}$

где $F(z)=e^{zT}\left(1+{\frac {z^{2}}{R^{2}}}\right)$ – множитель, введенный Ньюманом, который не меняет интеграл, поскольку $F$ является целым и $F(0)=1$.

Чтобы оценить интеграл, разорвите контур $C$ на две части, $C=C_{+}+C_{-}$ где $C_{+}=C\cap \left\{z\,\vert \,\Re z>0\right\}$ и $C_{-}\cap \left\{\Re z\leq 0\right\}$. Затем $g(0)-g_{T}(0)=\int _{C_{+}}\int _{T}^{\infty }H(t,z)dtdz-\int _{C_{-}}\int _{0}^{T}H(t,z)dtdz+\int _{C_{-}}g(z)F(z){\frac {dz}{2\pi iz}}$где $H(t,z)=f(t)e^{-tz}F(z)/2\pi i$. С $\vartheta (x)/x$, и, следовательно, $f(t)$, ограничено, пусть $B$ быть верхней границей абсолютного значения $f(t)$. Это связано с оценкой $|F|\leq 2\exp(T\Re z)|\Re z|/R$ для $|z|=R$ дает, что первый интеграл по абсолютной величине равен $\leq B/R$. Подынтегральное выражение над $C_{-}$ во втором интеграле целая , поэтому по интегральной теореме Коши контур $C_{-}$ можно изменить на полукруг радиуса $R$ в левой полуплоскости без изменения интеграла, и то же рассуждение, что и для первого интеграла, дает абсолютное значение второго интеграла: $\leq B/R$. Наконец, позволив $T\to \infty$ , третий интеграл обращается в ноль, так как $e^{zT}$ и, следовательно, $F$ обращается в ноль на контуре. Объединив две оценки и предел, получим

$\limsup _{T\to \infty }|g(0)-g_{T}(0)|\leq {\frac {2B}{R}}.$

Это справедливо для любого $R$ так $\lim _{T\to \infty }g_{T}(0)=g(0)$, и следует PNT.

Функция подсчета простых чисел в терминах логарифмического интеграла

В рукописной заметке к переизданию своей статьи 1838 года « Sur l'usage des infinies dans la theorie des nombres », которую он отправил Гауссу, Дирихле предположил (в несколько иной форме, апеллирующей к ряду, а не к интегралу), что еще лучшее приближение к π ( x ) дается смещенной логарифмической интегральной функцией Li( x ) , определенной формулой

$\operatorname {Li} (x)=\int _{2}^{x}{\frac {dt}{\log t}}=\operatorname {li} (x)-\operatorname {li} (2).$

Действительно, этот интеграл убедительно свидетельствует о том, что «плотность» простых чисел вокруг t должна быть 1/log t . Эта функция связана с логарифмом асимптотическим разложением

$\operatorname {Li} (x)\sim {\frac {x}{\log x}}\sum _{k=0}^{\infty }{\frac {k!}{(\log x)^{k}}}={\frac {x}{\log x}}+{\frac {x}{(\log x)^{2}}}+{\frac {2x}{(\log x)^{3}}}+\cdots$

Итак, теорему о простых числах также можно записать как π ( x ) ~ Li ( x ) . Кстати, в другой статье в 1899 году де ла Валле Пуссен доказал, что

$\pi (x)=\operatorname {Li} (x)+O\left(xe^{-a{\sqrt {\log x}}}\right)\quad {\text{as }}x\to \infty$

для некоторой положительной константы a , где O (...) это большое O. обозначение — Это было улучшено до

$\pi (x)=\operatorname {li} (x)+O\left(x\exp \left(-{\frac {A(\log x)^{\frac {3}{5}}}{(\log \log x)^{\frac {1}{5}}}}\right)\right)$ где $A=0.2098$.

В 2016 году Труджиан доказал явную верхнюю границу разницы между $\pi (x)$ и $\operatorname {li} (x)$:

${\big |}\pi (x)-\operatorname {li} (x){\big |}\leq 0.2795{\frac {x}{(\log x)^{3/4}}}\exp \left(-{\sqrt {\frac {\log x}{6.455}}}\right)$

для $x\geq 229$.

Связь между дзета-функцией Римана и π ( x ) является одной из причин, по которой гипотеза Римана имеет большое значение в теории чисел: если она будет установлена, она даст гораздо лучшую оценку ошибки, связанной с теоремой о простых числах, чем доступна сегодня. Точнее, Хельге фон Кох показал в 1901 году. что, если гипотеза Римана верна, член ошибки в приведенном выше соотношении можно улучшить до

$\pi (x)=\operatorname {Li} (x)+O\left({\sqrt {x}}\log x\right)$

(последняя оценка фактически эквивалентна гипотезе Римана). Константа, входящая в обозначение большого О, была оценена в 1976 году Лоуэллом Шенфельдом : предполагая гипотезу Римана,

${\big |}\pi (x)-\operatorname {li} (x){\big |}<{\frac {{\sqrt {x}}\log x}{8\pi }}$

для всех x ≥ 2657 . Он также получил аналогичную оценку для функции Чебышева, считающей простые числа ψ :

${\big |}\psi (x)-x{\big |}<{\frac {{\sqrt {x}}(\log x)^{2}}{8\pi }}$

для всех x ≥ 73,2 . Было показано, что эта последняя граница выражает отклонение от закона средней степени (если рассматривать его как случайную функцию над целыми числами) и ⁠ 1 /   f   ⁠   шума и также соответствовать распределению Пуассона соединения Твиди . (Распределения Твиди представляют собой семейство масштабно-инвариантных распределений, которые служат фокусами сходимости для обобщения центральной предельной теоремы . )

Логарифмический интеграл li( x ) больше π ( x ) для «маленьких» значений x . Это потому, что он (в некотором смысле) считает не простые числа, а степени простых чисел, где степень p ^н простого числа p считается как ⁠ 1 /   n   ⁠ простого числа. Это говорит о том, что li( x ) обычно должно быть больше π ( x ) примерно на $\ {\tfrac {1}{2}}\operatorname {li} ({\sqrt {x}})\ ,$ и, в частности, всегда должно быть больше π ( x ) . Однако в 1914 году Дж. Э. Литтлвуд доказал, что $\ \pi (x)-\operatorname {li} (x)\$ меняет знак бесконечно часто. Первое значение x, при котором π ( x ) превышает li( x ) , вероятно, составляет около x ~ 10. ³¹⁶ ; более подробную информацию см. в статье о номере Скьюза . (С другой стороны, смещенный логарифмический интеграл Li( x ) меньше π ( x ) уже для x = 2 ; действительно, Li(2) = 0 , а π (2) = 1 .)

Элементарные доказательства

В первой половине двадцатого века некоторые математики (особенно Г.Х. Харди ) считали, что в математике существует иерархия методов доказательства в зависимости от того, какие виды чисел ( целые , действительные , комплексные ) требуются для доказательства, и что теорема о простых числах (PNT) является «глубокой» теоремой, поскольку требует комплексного анализа . Это убеждение было несколько поколеблено доказательством PNT, основанным на тауберовой теореме Винера , хотя доказательство Винера в конечном итоге опирается на свойства дзета-функции Римана на прямой ${\text{re}}(s)=1$, где необходимо использовать комплексный анализ.

В марте 1948 года Атле Сельберг «элементарными» средствами установил асимптотическую формулу

$\vartheta (x)\log(x)+\sum \limits _{p\leq x}{\log(p)}\ \vartheta \left({\frac {x}{p}}\right)=2x\log(x)+O(x)$

где

$\vartheta (x)=\sum \limits _{p\leq x}{\log(p)}$

для простых чисел p . К июлю того же года Сельберг и Пол Эрдеш каждый из них получил элементарные доказательства PNT, оба использовали асимптотическую формулу Сельберга в качестве отправной точки. Эти доказательства фактически положили конец представлению о том, что PNT был «глубоким» в этом смысле, и показали, что технически «элементарные» методы были более мощными, чем считалось. Об истории элементарных доказательств PNT, включая спор о приоритете Эрдеша-Сельберга , см. статью Дориана Голдфельда .

Существуют некоторые споры о значении результата Эрдеша и Сельберга. В теории чисел не существует строгого и общепринятого определения понятия элементарного доказательства , поэтому неясно, в каком именно смысле их доказательство является «элементарным». Хотя он не использует сложный анализ, на самом деле он гораздо более технический, чем стандартное доказательство PNT. Одним из возможных определений «элементарного» доказательства является «то, которое может быть выполнено с помощью арифметики Пеано первого порядка ». Существуют теоретико-числовые утверждения (например, теорема Пэрис-Харрингтона ), доказуемые с использованием методов второго , но не первого порядка , но такие теоремы на сегодняшний день редки. Доказательство Эрдеша и Сельберга, безусловно, можно формализовать в арифметике Пеано, а в 1994 году Хараламбос Корнарос и Костас Димитракопулос доказали, что их доказательство можно формализовать в очень слабом фрагменте PA, а именно I ∆ ₀ + exp . Однако это не решает вопрос о том, может ли стандартное доказательство PNT быть формализовано в PA.

Более позднее «элементарное» доказательство теоремы о простых числах использует эргодическую теорию , предложенную Флорианом Рихтером. Там получена теорема о простых числах в эквивалентной форме, согласно которой сумма Чезаро значений функции Лиувилля равна нулю. Функция Лиувилля $(-1)^{\omega (n)}$ где $\omega (n)$ - количество простых делителей с кратностью целого числа $n$. Бергельсон и Рихтер (2022) затем получают эту форму теоремы о простых числах из эргодической теоремы, которую они доказывают:

Позволять $X$ быть компактным метрическим пространством, $T$ непрерывная карта самого себя $X$, и $\mu$ а $T$-инвариантная борелевская вероятностная мера, для которой $T$ однозначно эргодична . Тогда для каждого $f\in C(X)$,

$${\tfrac {1}{N}}\sum _{n=1}^{N}f(T^{\omega (n)}x)\to \int _{X}f\,d\mu ,\quad \forall x\in X.$$Эту эргодическую теорему также можно использовать для предоставления «мягких» доказательств результатов, связанных с теоремой о простых числах, таких как теорема Пиллаи–Сельберга и теорема Эрдеша–Деланжа .

Компьютерные проверки

В 2005 году Авигад и др. использовал средство доказательства теоремы Изабель , чтобы разработать проверенный на компьютере вариант доказательства PNT Эрдеша – Сельберга. Это было первое подтвержденное машиной доказательство PNT. Авигад решил формализовать доказательство Эрдеша-Сельберга, а не аналитическое, потому что, хотя библиотека Изабель в то время могла реализовать понятия предела, производной и трансцендентной функции , в ней почти не было теории интегрирования, о которой можно было бы говорить.

В 2009 году Джон Харрисон использовал HOL Light для формализации доказательства с использованием комплексного анализа . Разработав необходимый аналитический аппарат, включая интегральную формулу Коши , Харрисон смог формализовать «прямое, современное и элегантное доказательство вместо более сложного« элементарного »аргумента Эрдеша-Сельберга».

Теорема о простых числах для арифметических прогрессий

Пусть π _{d , a} ( x ) обозначает количество простых чисел в арифметической прогрессии a , a + d , a + 2 d , a + 3 d , ... которые меньше x . Дирихле и Лежандр предположили, а де ла Валле Пуссен доказали, что если a и d взаимно просты , то

$\pi _{d,a}(x)\sim {\frac {\operatorname {Li} (x)}{\varphi (d)}}\ ,$

где φ — функция тотента Эйлера . Другими словами, простые числа распределяются равномерно среди классов вычетов [ a ] по модулю d с НОД( a , d ) = 1 . Это сильнее, чем теорема Дирихле об арифметических прогрессиях (которая лишь утверждает, что в каждом классе существует бесконечное количество простых чисел) и может быть доказана с использованием аналогичных методов, использованных Ньюманом для доказательства теоремы о простых числах.

Теорема Зигеля –Вальфиса дает хорошую оценку распределения простых чисел в классах вычетов.

Беннетт и др. доказал следующую оценку, имеющую явные константы A и B (теорема 1.3):Пусть д $\geq 3$ — целое число, и пусть a — целое число, взаимно простое с d . Тогда существуют положительные константы A и B такие, что

$\left|\pi _{d,a}(x)-{\frac {\ \operatorname {Li} (x)\ }{\ \varphi (d)\ }}\right|<{\frac {A\ x}{\ (\log x)^{2}\ }}\quad {\text{ for all }}\quad x\geq B\ ,$

где

$A={\frac {1}{\ 840\ }}\quad {\text{ if }}\quad 3\leq d\leq 10^{4}\quad {\text{ and }}\quad A={\frac {1}{\ 160\ }}\quad {\text{ if }}\quad d>10^{4}~,$

и

$B=8\cdot 10^{9}\quad {\text{ if }}\quad 3\leq d\leq 10^{5}\quad {\text{ and }}\quad B=\exp(\ 0.03\ {\sqrt {d\ }}\ (\log {d})^{3}\ )\quad {\text{ if }}\quad d>10^{5}\ .$

Гонка за простыми числами

График функции $\ \pi (x;4,3)-\pi (x;4,1)\$ для n ≤ 30000

Хотя у нас, в частности,

$\pi _{4,1}(x)\sim \pi _{4,3}(x)\ ,$

эмпирически простые числа, соответствующие 3, более многочисленны и почти всегда опережают в этой «гонке простых чисел»; первый разворот происходит в точке x = 26861 . Однако Литтлвуд показал в 1914 г. что функция имеет бесконечно много перемен знака

$\pi _{4,1}(x)-\pi _{4,3}(x)~,$

поэтому лидерство в гонке меняется туда и обратно бесконечное число раз. Явление того, что π _4,3 ( x ) большую часть времени опережает, называется смещением Чебышева . Гонка простых чисел распространяется на другие модули и является предметом многочисленных исследований; Пал Туран спросил, всегда ли π ( x ; a , c ) и π ( x ; b , c ) меняются местами, когда a и b взаимно просты с c . Гранвиль и Мартин дают подробное изложение и обзор.

График количества простых чисел, оканчивающихся на 1, 3, 7 и 9, до n для n < 10 000

Другой пример — распределение последней цифры простых чисел. За исключением 2 и 5, все простые числа оканчиваются на 1, 3, 7 или 9. Теорема Дирихле утверждает, что асимптотически 25% всех простых чисел оканчиваются на каждую из этих четырех цифр. Однако эмпирические данные показывают, что количество простых чисел, оканчивающихся на 3 или 7 меньше, чем n, имеет тенденцию быть немного больше, чем количество простых чисел, оканчивающихся на 1 или 9 меньше, чем n (поколение предвзятости Чебышева). Отсюда следует, что 1 и 9 — квадратичные вычеты по модулю 10, а 3 и 7 — квадратичные невычеты по модулю 10.

Неасимптотические границы функции счета простых чисел

Теорема о простых числах является асимптотическим результатом. Это дает неэффективную оценку π ( x ) как прямое следствие определения предела: для всех ε > 0 существует S такое, что для x > S всех

$(1-\varepsilon ){\frac {x}{\log x}}\;<\;\pi (x)\;<\;(1+\varepsilon ){\frac {x}{\log x}}\;.$

лучшие оценки π ( x ) Однако известны , например, Пьера Дюсара .

${\frac {x}{\log x}}\left(1+{\frac {1}{\log x}}\right)\;<\;\pi (x)\;<\;{\frac {x}{\log x}}\left(1+{\frac {1}{\log x}}+{\frac {2.51}{(\log x)^{2}}}\right)\;.$

Первое неравенство справедливо для всех x ≥ 599 , а второе — для x ≥ 355991 .

Более слабая, но иногда полезная оценка для x ≥ 55 :

${\frac {x}{\log x+2}}\;<\;\pi (x)\;<\;{\frac {x}{\log x-4}}\;.$

В диссертации Пьера Дюсара есть более сильные версии неравенства этого типа, справедливые для больших x . Позже в 2010 году Дюсарт доказал:

${\begin{aligned}{\frac {x}{\log x-1}}\;&<\;\pi (x)&&{\text{ for }}x\geq 5393\;,{\text{ and }}\\\pi (x)\;&<\;{\frac {x}{\log x-1.1}}&&{\text{ for }}x\geq 60184\;.\end{aligned}}$

Доказательство де ла Валле Пуссена подразумевает следующее: для каждого ε > 0 существует S такое, что для всех x > S ,

${\frac {x}{\log x-(1-\varepsilon )}}\;<\;\pi (x)\;<\;{\frac {x}{\log x-(1+\varepsilon )}}\;.$

Приближения для n- го простого числа

Как следствие теоремы о простых числах, получается асимптотическое выражение для - го простого числа, обозначаемого pn _n :

$p_{n}\sim n\log n.$

Лучшее приближение

${\frac {p_{n}}{n}}=\log n+\log \log n-1+{\frac {\log \log n-2}{\log n}}-{\frac {(\log \log n)^{2}-6\log \log n+11}{2(\log n)^{2}}}+o\left({\frac {1}{(\log n)^{2}}}\right).$

Снова учитывая 2 × 10 ¹⁷ е-е простое число 8 512 677 386 048 191 063 , это дает оценку 8 512 681 315 554 715 386 ; первые 5 цифр совпадают, и относительная ошибка составляет около 0,00005%.

Теорема Россера утверждает, что

$p_{n}>n\log n.$

Это можно улучшить с помощью следующей пары границ:

$\log n+\log \log n-1<{\frac {p_{n}}{n}}<\log n+\log \log n\quad {\text{for }}n\geq 6.$

Таблица π ( x ) , x / log x и li ( x )

В таблице сравниваются точные значения π ( x ) с двумя приближениями x / log x и li ( x ) . Последний столбец, x / π ( x ) , представляет собой средний разрыв простых чисел ниже x .

х	π ( Икс )	π ( Икс ) - ⁠ х / журнал( х ) ⁠	li( Икс ) - π ( Икс )	⁠ х / журнал( х ) ⁠ % ошибка	ли ( х ) % ошибка	⁠ Икс / π ( Икс ) ⁠
10	4	0	2	8.22%	42.606%	2.500
10 2	25	3	5	14.06%	18.597%	4.000
10 3	168	23	10	14.85%	5.561%	5.952
10 4	1,229	143	17	12.37%	1.384%	8.137
10 5	9,592	906	38	9.91%	0.393%	10.425
10 6	78,498	6,116	130	8.11%	0.164%	12.739
10 7	664,579	44,158	339	6.87%	0.051%	15.047
10 8	5,761,455	332,774	754	5.94%	0.013%	17.357
10 9	50,847,534	2,592,592	1,701	5.23%	3.34 × 10 −3  %	19.667
10 10	455,052,511	20,758,029	3,104	4.66%	6.82 × 10 −4  %	21.975
10 11	4,118,054,813	169,923,159	11,588	4.21%	2.81 × 10 −4  %	24.283
10 12	37,607,912,018	1,416,705,193	38,263	3.83%	1.02 × 10 −4  %	26.590
10 13	346,065,536,839	11,992,858,452	108,971	3.52%	3.14 × 10 −5  %	28.896
10 14	3,204,941,750,802	102,838,308,636	314,890	3.26%	9.82 × 10 −6  %	31.202
10 15	29,844,570,422,669	891,604,962,452	1,052,619	3.03%	3.52 × 10 −6  %	33.507
10 16	279,238,341,033,925	7,804,289,844,393	3,214,632	2.83%	1.15 × 10 −6  %	35.812
10 17	2,623,557,157,654,233	68,883,734,693,928	7,956,589	2.66%	3.03 × 10 −7  %	38.116
10 18	24,739,954,287,740,860	612,483,070,893,536	21,949,555	2.51%	8.87 × 10 −8  %	40.420
10 19	234,057,667,276,344,607	5,481,624,169,369,961	99,877,775	2.36%	4.26 × 10 −8  %	42.725
10 20	2,220,819,602,560,918,840	49,347,193,044,659,702	222,744,644	2.24%	1.01 × 10 −8  %	45.028
10 21	21,127,269,486,018,731,928	446,579,871,578,168,707	597,394,254	2.13%	2.82 × 10 −9  %	47.332
10 22	201,467,286,689,315,906,290	4,060,704,006,019,620,994	1,932,355,208	2.03%	9.59 × 10 −10  %	49.636
10 23	1,925,320,391,606,803,968,923	37,083,513,766,578,631,309	7,250,186,216	1.94%	3.76 × 10 −10  %	51.939
10 24	18,435,599,767,349,200,867,866	339,996,354,713,708,049,069	17,146,907,278	1.86%	9.31 × 10 −11  %	54.243
10 25	176,846,309,399,143,769,411,680	3,128,516,637,843,038,351,228	55,160,980,939	1.78%	3.21 × 10 −11  %	56.546
10 26	1,699,246,750,872,437,141,327,603	28,883,358,936,853,188,823,261	155,891,678,121	1.71%	9.17 × 10 −12  %	58.850
10 27	16,352,460,426,841,680,446,427,399	267,479,615,610,131,274,163,365	508,666,658,006	1.64%	3.11 × 10 −12  %	61.153
10 28	157,589,269,275,973,410,412,739,598	2,484,097,167,669,186,251,622,127	1,427,745,660,374	1.58%	9.05 × 10 −13  %	63.456
10 29	1,520,698,109,714,272,166,094,258,063	23,130,930,737,541,725,917,951,446	4,551,193,622,464	1.53%	2.99 × 10 −13  %	65.759

Значение π (10 ²⁴ ) первоначально рассчитывался с учетом гипотезы Римана ; с тех пор это было безоговорочно подтверждено.

Аналог для неприводимых многочленов над конечным полем

Существует аналог теоремы о простых числах, описывающий «распределение» неприводимых многочленов по конечному полю ; форма, которую он принимает, поразительно похожа на случай классической теоремы о простых числах.

Точнее говоря, пусть F = GF( q ) будет конечным полем с q элементами для некоторого фиксированного q , и пусть N _n будет числом монических неприводимых многочленов над F, которых степень равна n . То есть мы рассматриваем полиномы с коэффициентами, выбранными из F , которые нельзя записать как произведения полиномов меньшей степени. В этом случае эти многочлены играют роль простых чисел, поскольку все остальные монические многочлены состоят из их произведений. Тогда можно доказать, что

$N_{n}\sim {\frac {q^{n}}{n}}.$

Если мы сделаем замену x = q ^н , то правая часть просто

${\frac {x}{\log _{q}x}},$

что делает аналогию более понятной. Поскольку существует ровно q ^н монических полиномов степени n (включая приводимые), это можно перефразировать следующим образом: если монический многочлен степени n выбран случайным образом, то вероятность того, что он будет неприводимым, равна примерно ⁠ 1 / n ⁠ .

Можно даже доказать аналог гипотезы Римана, а именно, что

$N_{n}={\frac {q^{n}}{n}}+O\left({\frac {q^{\frac {n}{2}}}{n}}\right).$

Доказательства этих утверждений гораздо проще, чем в классическом случае. Он включает в себя короткий комбинаторный аргумент, резюмируется следующим образом: каждый элемент степени n расширения F является корнем некоторого неприводимого многочлена, степень d которого делит n ; подсчитав эти корни двумя разными способами, можно установить, что

$q^{n}=\sum _{d\mid n}dN_{d},$

где сумма ведется по всем делителям d числа n . Тогда обращение Мёбиуса дает

$N_{n}={\frac {1}{n}}\sum _{d\mid n}\mu \left({\frac {n}{d}}\right)q^{d},$

где µ ( k ) — функция Мёбиуса . (Эта формула была известна Гауссу.) Главный член встречается при d = n , и нетрудно оценить остальные члены. Утверждение «гипотезы Римана» основано на том факте, что наибольший собственный делитель n чем не может быть больше, ⁠ n / 2 ⁠ .

См. также

• Абстрактная аналитическая теория чисел для получения информации об обобщениях теоремы.
• Теорема Ландау о простых идеалах для обобщения на простые идеалы в полях алгебраических чисел.
• Гипотеза Римана

Ссылки

• Гранвилл, Эндрю (1995). «Харальд Крамер и распределение простых чисел» (PDF) . Скандинавский актуарный журнал . 1 : 12–28. CiteSeerX   10.1.1.129.6847 . дои : 10.1080/03461238.1995.10413946 .
• Харди, штат Джорджия ; Литтлвуд, Дж. Э. (1916). «Вклад в теорию дзета-функции Римана и теорию распределения простых чисел» . Акта Математика . 41 : 119–196. дои : 10.1007/BF02422942 . S2CID   53405990 .
• Харди, штат Джорджия ; Райт, Э.М. (2008) [1-е изд. 1938], «Введение в теорию чисел» , отредактированное Д. Р. Хит-Брауном и Дж. Х. Сильверманом , с предисловием Эндрю Уайлса (6-е изд.), Оксфорд: Oxford University Press, ISBN  978-0-19-921985-8
• Наркевич, Владислав (2000), Развитие теории простых чисел: от Евклида до Харди и Литтлвуда , Монографии Спрингера по математике, Springer-Verlag, doi : 10.1007/978-3-662-13157-2 , ISBN  978-3-540-66289-1 , ISSN   1439-7382

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

• «Распределение простых чисел» , Энциклопедия математики , EMS Press , 2001 [1994]
• Таблица простых чисел Антона Фелькеля .
• Короткое видео, визуализирующее теорему о простых числах.
• Формулы простых чисел и теорема о простых числах в MathWorld .
• Сколько существует простых чисел? Архивировано 15 октября 2012 г. в Wayback Machine и The Gaps Between Primes Крисом Колдуэллом, Университет Теннесси в Мартине .
• Таблицы функций счета простых чисел Томаса Оливейры и Сильвы
• Эберл, Мануэль и Полсон, Л. К. Теорема о простых числах (разработка формального доказательства в Isabelle/HOL, Архив формальных доказательств)
• Теорема о простых числах: «элементарное» доказательство — изложение элементарного доказательства теоремы о простых числах Атле Сельберга и Пауля Эрдеша на www.dimostriamogoldbach.it/en/