Теорема о простых числах - Prime number theorem

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

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

Заявление

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

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

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

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

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

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

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

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

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

асимптотические обозначения снова означают, что относительная погрешность этого приближения приближается к 0 при п неограниченно увеличивается. Например, 2×10¹⁷ое простое число 8512677386048191063,^[2] и (2×10¹⁷)бревно(2×10¹⁷) округляется до 7967418752291744388, относительная погрешность около 6,4%.

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

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

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

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

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

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

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

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

Доказательство эскиза

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

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

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

${ Displaystyle пси (х) = сумма _ {п Leq х} лямбда (п),}$

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

${ displaystyle Lambda (n) = { begin {case} log p & { text {if}} n = p ^ {k} { text {для некоторого простого числа}} p { text {и целое число}} k geq 1, 0 & { text {в противном случае.}} end {case}}}$

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

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

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

${ displaystyle psi (x) = сумма _ {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}$

и (используя большой О обозначение ) для любого ε > 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.}$

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

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

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

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

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

Следующий шаг доказательства включает изучение нулей дзета-функции. Тривиальные нули −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),}$

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

Для этого мы считаем само собой разумеющимся, что ζ(s) является мероморфный в полуплоскости Re (s) > 0, и там аналитична за исключением простого полюса в точке s = 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 = Икс + иу; тогда

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

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

${ Displaystyle 3 + 4 соз фи + соз 2 фи = 2 (1+ соз фи) ^ {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}$

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

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

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

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

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

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

Вторая серия получается отбрасыванием членов с ${ Displaystyle к geq 2}$ с первого. PNT эквивалентен ${ Displaystyle lim _ {х к infty} psi (x) / x = 1}$ или же ${ Displaystyle lim _ {х к infty} vartheta (х) / х = 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 к geq 2}$ с первого. Ряд Дирихле, образованный членами с ${ Displaystyle к 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 (х) / х}$ ограничено. Это легко доказать элементарными методами.

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

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

сходится, поэтому подынтегральное выражение стремится к нулю при ${ Displaystyle т к 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)}$

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

Разница ${ 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}$ быть его границей. Поскольку 0 находится внутри, Интегральная формула Коши дает

${ 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 (е ^ {т}) / {е ^ {т}} - 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 С крышка влево { Re Z Leq 0 вправо }}$ . Функция ${ 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}}.}$

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

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

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

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

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

${ 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 х) ^ {3}}} + cdots}$

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

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

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

${ 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)}$ куда ${ displaystyle A = 0.2098}$.^[11]

В 2016 году Труджян доказал явную верхнюю границу разницы между ${ Displaystyle пи (х)}$ и ${ 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)}$

за ${ Displaystyle х geq 229}$.^[12]

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

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

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

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

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

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

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

В логарифмический интеграл ли (Икс) больше чем π(Икс) для «малых» значений Икс. Это потому, что он (в некотором смысле) считает не простые числа, а простые степени, где степень п^п премьер п считается как 1/п прайма. Это говорит о том, что ли (Икс) обычно должен быть больше, чем π(Икс) примерно ли (√Икс) / 2, и, в частности, всегда должно быть больше, чем π(Икс). Однако в 1914 г. Дж. Э. Литтлвуд доказал, что ${ displaystyle pi (x) - operatorname {li} (x)}$ меняет знак бесконечно часто.^[16] Первое значение Икс куда π(Икс) превышает ли (Икс) вероятно где-то рядом Икс = 10³¹⁶; см. статью о Число Скьюза Больше подробностей. (С другой стороны, логарифмический интеграл смещения Ли (Икс) меньше чем π(Икс) уже для Икс = 2; в самом деле, Ли (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)}}$

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

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

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

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

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

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

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

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

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

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

Гонка на простое число

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

${ Displaystyle пи _ {4,1} (х) сим пи _ {4,3} (х),}$

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

${ Displaystyle pi _ {4,1} (х) - pi _ {4,3} (х),}$

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

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

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

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

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

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

Первое неравенство выполняется для всех Икс ≥ 599 а второй для Икс ≥ 355991.^[26]

Более слабая, но иногда полезная оценка для Икс ≥ 55 является^[27]

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

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

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

Из доказательства де ла Валле Пуссен следует следующее. ε > 0, существует S такое, что для всех Икс > S,

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

Приближения для пое простое число

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

${ 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¹⁷ое простое число 8512677386048191063, это дает оценку 8512681315554715386; совпадение первых 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. }$

Таблица π(Икс), Икс / бревно Икс, и ли (Икс)

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

Икс	π(Икс)	π(Икс) − Икс/бревно Икс	π(Икс)/Икс / бревно Икс	ли (Икс) − π(Икс)	Икс/π(Икс)
10	4	−0.3	0.921	2.2	2.500
102	25	3.3	1.151	5.1	4.000
103	168	23.0	1.161	10.0	5.952
104	1229	143.0	1.132	17.0	8.137
105	9592	906.0	1.104	38.0	10.425
106	78498	6116.0	1.084	130.0	12.740
107	664579	44158.0	1.071	339.0	15.047
108	5761455	332774.0	1.061	754.0	17.357
109	50847534	2592592.0	1.054	1701.0	19.667
1010	455052511	20758029.0	1.048	3104.0	21.975
1011	4118054813	169923159.0	1.043	11588.0	24.283
1012	37607912018	1416705193.0	1.039	38263.0	26.590
1013	346065536839	11992858452.0	1.034	108971.0	28.896
1014	3204941750802	102838308636.0	1.033	314890.0	31.202
1015	29844570422669	891604962452.0	1.031	1052619.0	33.507
1016	279238341033925	7804289844393.0	1.029	3214632.0	35.812
1017	2623557157654233	68883734693281.0	1.027	7956589.0	38.116
1018	24739954287740860	612483070893536.0	1.025	21949555.0	40.420
1019	234057667276344607	5481624169369960.0	1.024	99877775.0	42.725
1020	2220819602560918840	49347193044659701.0	1.023	222744644.0	45.028
1021	21127269486018731928	446579871578168707.0	1.022	597394254.0	47.332
1022	201467286689315906290	4060704006019620994.0	1.021	1932355208.0	49.636
1023	1925320391606803968923	37083513766578631309.0	1.020	7250186216.0	51.939
1024	18435599767349200867866	339996354713708049069.0	1.019	17146907278.0	54.243
1025	176846309399143769411680	3128516637843038351228.0	1.018	55160980939.0	56.546
OEIS	A006880	A057835		A057752

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

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

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

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

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

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

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

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

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

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

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

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

где сумма по всем делители d из п. Инверсия Мёбиуса затем дает

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

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

Смотрите также

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

Примечания

Рекомендации

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

внешняя ссылка

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