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

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

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

Заявление [ править ]

График, показывающий отношение функции подсчета простых чисел π ( 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 ) меняет знак бесконечно много раз.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Доказательство [ править ]

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

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

Иногда это записывается как

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

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

${\displaystyle \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 эквивалентно утверждению, что

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

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

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

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

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

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

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

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

${\displaystyle \psi (x)=x-\sum _{\rho }{\frac {x^{\rho }}{\rho }}-\log(2\pi )}$

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

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

${\displaystyle \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.

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

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

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

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

Напишите s = x + iy ; тогда

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

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

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

так что

${\displaystyle \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}$

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

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

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

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

Первая и вторая функции Чебышева соответственно

${\displaystyle \psi (x)=\sum _{k\geq 1}\sum _{p^{k}\leq x}\log p\quad {\text{ and }}\quad \vartheta (x)=\sum _{p\leq x}\log p.}$

Вторая серия получается отбрасыванием членов с из первой. PNT эквивалентен либо или .${\displaystyle k\geq 2}$${\displaystyle \lim _{x\to \infty }\psi (x)/x=1}$${\displaystyle \lim _{x\to \infty }\vartheta (x)/x=1}$

Суммы для и являются частными суммами коэффициентов ряда Дирихле${\displaystyle \psi }$${\displaystyle \vartheta }$

${\displaystyle -{\frac {\zeta '(s)}{\zeta (s)}}=\sum _{k\geq 1}\sum _{p^{k}\leq x}\log p\,\,p^{-ks}\quad {\text{ and }}\quad \quad \Phi (s)=\sum _{p\leq x}\log p\,\,p^{-s},}$

где - дзета-функция Римана . Как и в случае с частичными суммами, второй ряд получается отбрасыванием членов с из первого. В ряду Дирихле, образованном членами с , преобладает ряд Дирихле для при любом положительном значении , поэтому логарифмическая производная и отличается функцией, голоморфной в , и, следовательно, имеют одинаковые особенности на прямой .${\displaystyle \zeta }$${\displaystyle k\geq 2}$${\displaystyle k\geq 2}$${\displaystyle \zeta (2s+\varepsilon )}$${\displaystyle \varepsilon }$${\displaystyle \zeta }$${\displaystyle \Phi (s)}$${\displaystyle \Re s>{\frac {1}{2}}}$${\displaystyle \Re s=1}$

Интеграция по частям дает ,${\displaystyle \Re s>1}$

${\displaystyle \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.}$

Все аналитические доказательства теоремы о простых числах используют тот факт, что на прямой нет нулей . Еще одна информация, необходимая для доказательства Ньюмана, - это ограниченность. Это легко доказать элементарными методами. ${\displaystyle \zeta }$${\displaystyle \Re s=1}$${\displaystyle \vartheta (x)/x}$

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

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

сходится, поэтому подынтегральное выражение обращается в нуль при . Вообще говоря, сходимость несобственного интеграла не означает, что подынтегральное выражение стремится к нулю, поскольку оно может колебаться, но, поскольку при увеличении, это легко показать в этом случае. ${\displaystyle t\to \infty }$${\displaystyle \vartheta }$

Для аренды ${\displaystyle \Re z>0}$

${\displaystyle g_{T}(z)=\int _{0}^{T}\left({\frac {\vartheta (e^{t})}{e^{t}}}-1\right)e^{-zt}\,dt\quad \quad }$

тогда

${\displaystyle \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}$

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

${\displaystyle \lim _{T\to \infty }\lim _{s\to 0}g_{T}(z)=\lim _{s\to 0}\lim _{T\to \infty }g_{T}(z)}$

и поэтому классифицируется как тауберова теорема.

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

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

Чтобы получить приблизительную оценку подынтегрального выражения, пусть будет оценка сверху , а затем для${\displaystyle B}$${\displaystyle \vartheta (e^{t})/{e^{t}}-1}$${\displaystyle \Re z>0}$

${\displaystyle |g(z)-g_{T}(z)|\leq B\int _{T}^{\infty }e^{-\Re (z)t}\,dt={\frac {Be^{-\Re (z)T}}{\Re z}}.}$

Этой оценки недостаточно, чтобы доказать результат, но Ньюман вводит множитель

${\displaystyle F(z)=e^{zT}\left(1+{\frac {z^{2}}{R^{2}}}\right)}$

в подынтегральную функцию для . Поскольку фактор Ньюмана - это целое и , левая часть остается неизменной. Теперь приведенная выше оценка и оценки объединяются, чтобы дать ${\displaystyle g(0)-g_{T}(0)}$${\displaystyle F}$${\displaystyle F(0)=1}$${\displaystyle |g(z)-g_{T}(z)|}$${\displaystyle F}$

${\displaystyle \left|{\frac {1}{2\pi i}}\int _{C_{+}}\left(g(z)-g_{T}(z)\right)F(z){\frac {dz}{z}}\right|\leq {\frac {B}{R}}.}$

где - полукруг . ${\displaystyle C_{+}}$${\displaystyle C\cap \left\{z\,\vert \,\Re z>0\right\}}$

Позвольте быть контуром . Функция является целой , поэтому по интегральной теореме Коши контур может быть изменен до полукруга радиуса в левой полуплоскости без изменения интеграла от , и тот же аргумент дает абсолютное значение этого интеграла как . Наконец, позволив , интеграл по контуру стремится к нулю, так как стремится к нулю на контуре. Комбинируя три оценки, получаем${\displaystyle C_{-}}$${\displaystyle C\cap \left\{\Re z\leq 0\right\}}$${\displaystyle g_{T}}$${\displaystyle C_{-}}$${\displaystyle R}$${\displaystyle g_{T}(z)F(z)/2\pi iz}$${\displaystyle \leq B/R}$${\displaystyle T\to \infty }$${\displaystyle g(z)F(z)/z}$${\displaystyle C_{\delta }}$${\displaystyle F}$

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

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

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

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

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

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

${\displaystyle \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 г. де ла Валле Пуссен доказал, что

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

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

${\displaystyle \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)}$где . ^[11]${\displaystyle A=0.2098}$

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

${\displaystyle {\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)}$

для . ^[12]${\displaystyle x\geq 229}$

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

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

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

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

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

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

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

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

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

В первой половине двадцатого века некоторые математики (в частности, Дж. Харди ) считали, что в математике существует иерархия методов доказательства в зависимости от того, какие типы чисел ( целые , действительные , комплексные ) требует доказательство, и что теорема о простых числах (PNT) является «глубокой» теоремой в силу необходимости комплексного анализа . ^[17] Это убеждение было несколько поколеблено доказательством PNT, основанным на тауберианской теореме Винера , хотя от этого можно было бы отказаться , если бы считалось , что теорема Винера имеет «глубину», эквивалентную глубине методов комплексных переменных.

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

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

куда

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

для простых чисел p . ^[18] К июлю того же года Сельберг и Пол Эрдеш получили элементарные доказательства PNT, оба использовали асимптотическую формулу Сельберга в качестве отправной точки. ^{[17] [19]} Эти доказательства фактически опровергли представление о том, что PNT был «глубоким» в этом смысле, и показали, что технически «элементарные» методы были более мощными, чем предполагалось. Об истории элементарных доказательств PNT, включая спор о приоритете Эрдеша – Сельберга , см. Статью Дориана Гольдфельда . ^[17]

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

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

В 2005 году Авигад и др. использовал средство доказательства теорем Изабель, чтобы разработать проверенный компьютером вариант доказательства Эрдёша – Сельберга PNT. ^[21] Это было первое доказательство PNT, прошедшее машинную проверку. Авигад решил формализовать доказательство Эрдеша – Сельберга, а не аналитическое, потому что, хотя библиотека Изабель в то время могла реализовывать понятия предела, производной и трансцендентной функции , в ней почти не было теории интеграции, о которой можно было бы говорить. ^{[21] : 19}

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

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

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

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

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

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

Гонка простых чисел [ править ]

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

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

эмпирически простые числа, конгруэнтные трем, более многочисленны и почти всегда впереди в этой «гонке простых чисел»; первый разворот происходит при x = 26861 . ^{[24] : 1–2} Однако Литтлвуд в 1914 г. показал ^{[24] : 2,} что существует бесконечно много изменений знака для функции

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

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

Неасимптотические оценки функции подсчета простых чисел [ править ]

Теорема о простых числах - это асимптотический результат. Это дает неэффективное ограничение на П ( х ) , как прямое следствие определения предела: для всех х > 0 , существует S таких , что для всех х > S ,

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

Тем не менее, лучшие оценки по П ( х ) известны, например , Пьера Dusart «с

${\displaystyle {\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 . ^[26]

Более слабый , но иногда полезно для связанной х ≥ 55 является ^[27]

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

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

${\displaystyle {\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 такое , что для всех х > S ,

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

Приближение n- го простого числа [ править ]

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

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

Лучшее приближение ^[29]

${\displaystyle {\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 ^17- е простое число8 512 677 386 048 191 063 , это дает оценку8 512 681 315 554 715 386 ; совпадение первых 5 цифр и относительная погрешность около 0,00005%.

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

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

Это можно улучшить с помощью следующей пары оценок: ^{[30] [31]}

${\displaystyle \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 .

Икс	π ( х )	π ( х ) -Икс/журнал x	π ( х )/х / журнал х	li ( x ) - π ( x )	Икс/π ( х )
10	4	-0,3	0,921	2.2	2,5 00
10 2	25	3.3	1,151	5.1	4 .000
10 3	168	23 .0	1,161	10 .0	5,952
10 4	1 229	143, 0	1.132	17, 0	8,137
10 5	9 592	906, 0	1,104	38, 0	10,425
10 6	78 498	6 116 0,0	1.084	130, 0	12,740
10 7	664 579	44 158 0,0	1.071	339, 0	15.047
10 8	5 761 455	332 774 0,0	1.061	754 0,0	17,357
10 9	50 847 534	2 592 592 0,0	1.054	1 701 0,0	19,667
10 10	455 052 511	20 758 029 0,0	1.048	3 104 0,0	21,975
10 11	4 118 054 813	169 923 159 0,0	1.043	11 588 0,0	24 283
10 12	37 607 912 018	1 416 705 193 0,0	1.039	38 263 0,0	26 590
10 13	346 065 536 839	11 992 858 452 0,0	1.034	108 971 0,0	28,896
10 14	3 204 941 750 802	102 838 308 636 0,0	1.033	314 890 +0,0	31,202
10 15	29 844 570 422 669	891 604 962 452 0,0	1.031	1 052 619 0,0	33,507
10 16	279 238 341 033 925	7 804 289 844 393 0,0	1.029	3 214 632 0,0	35,812
10 17	2 623 557 157 654 233	68 883 734 693 281 0,0	1.027	7 956 589 0,0	38,116
10 18	24 739 954 287 740 860	612 483 070 893 536 0,0	1.025	21 949 555 0,0	40,420
10 19	234 057 667 276 344 607	5 481 624 169 369 960 0,0	1.024	99 877 775 0,0	42,725
10 20	2 220 819 602 560 918 840	49 347 193 044 659 701 0,0	1.023	222 744 644 0,0	45,028
10 21	21 127 269 486 018 731 928	446 579 871 578 168 707, 0	1.022	597 394 254 0,0	47,332
10 22	201 467 286 689 315 906 290	4 060 704 006 019 620 994 0,0	1.021	1 932 355 208, 0	49,636
10 23	1 925 320 391 606 803 968 923	37 083 513 766 578 631 309 0,0	1.020	7 250 186 216 0,0	51,939
10 24	18 435 599 767 349 200 867 866	339 996 354 713 708 049 069, 0	1.019	17 146 907 278 0,0	54,243
10 25	176 846 309 399 143 769 411 680	3 128 516 637 843 038 351 228 0,0	1.018	55 160 980 939 0,0	56,546
OEIS	A006880	A057835		A057752

Значение π (10 ²⁴ ) было первоначально вычислено с учетом гипотезы Римана ; ^[32] с тех пор это было проверено безоговорочно. ^[33]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

• Харди, GH; Литтлвуд, Дж. Э. (1916). «Вклад в теорию дзета-функции Римана и теорию распределения простых чисел» . Acta Mathematica . 41 : 119–196. DOI : 10.1007 / BF02422942 . S2CID  53405990 .
• Гранвиль, Эндрю (1995). «Харальд Крамер и распределение простых чисел» (PDF) . Скандинавский актуарный журнал . 1 : 12–28. CiteSeerX  10.1.1.129.6847 . DOI : 10.1080 / 03461238.1995.10413946 .

Внешние ссылки [ править ]

• "Распределение простых чисел" , Энциклопедия математики , EMS Press , 2001 [1994]
• Таблица простых чисел Антона Фелькеля .
• Короткое видео, демонстрирующее теорему о простых числах.
• Prime формулы и теоремы числа премьера в MathWorld .
• Сколько существует простых чисел? и «Разрывы между простыми числами » Криса Колдуэлла, Университет Теннесси в Мартине .
• Таблицы функций, считающих простые числа , Томаса Оливейры и Силвы