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

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

Первое найденное такое распределение — π ( N ) ~ N / log( N ) , где π ( N ) — функция подсчета простых чисел меньше или равное N ), а log( 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 Ньюман дает быстрое доказательство теоремы о простых числах (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 /   н   простого числа. Это говорит о том, что 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.

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

В 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}={\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 чем не может быть больше, н / 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/