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

 В математике функция распределения простых чисел илипи-функция π(x)π(x) — это функция, равная числу простыхчисел, меньших либо равных действительному числу x. Онаобозначается π(x)π(x) (это никак не связано с числом пи).

История


 Большой интерес в теории чисел представляет скорость роста пи-функции. Вконце 18-го столетия Гауссом и Лежандром было выдвинуто предположение,что пи-функция оценивается как

xlnxxlnx
 в смысле, что

limx+π(x)x/lnx=1.limx+π(x)x/lnx=1.
 Это утверждение — теорема о распределении простых чисел. Оноэквивалентно утверждению

limx+π(x)li(x)=1limx+π(x)li(x)=1
 где lili — это интегральный логарифм. Теорема о простыхчислах впервые была доказана в 1896 Жаком Адамаром и независимоВалле-Пуссеном, используя дзета-функцию Римана введенную Риманом в 1859.
 Точнее рост π(x)π(x) сейчас описывается как

π(x)=li(x)+O(xelnx/15)π(x)=li(x)+O(xelnx/15)
 где OO обозначает O большое. Для чаще всего используемых значенийx (то есть когда x не сильно велико)li(x)li(x) больше чем π(x)π(x), однако разностьπ(x)li(x)π(x)li(x) меняет свой знак бесконечное число раз.См. также Число Скьюза.
 Доказательства теоремы о простых числах, не использующие дзета-функциюили комплексный анализ были найдены в 1948 году Атле Сельбергом и ПаулемЭрдёшом (большей частью независимо).

Таблицы для пи-функции, x

/ ln \emphx иli(x)
 В следующей таблице показан рост функцийπ(x),xlnx,li(x)π(x),xlnx,li(x) по степеням 10.
 : \{ ! x ! π(x) ! π(x) − x / lnx ! li(x) − π(x) ! x / π(x)- 10 4 −0,3 2,2 2,500 - 10225 3,3 5,1 4,000 -103 168 23 10 5,952 - 1041 229 143 17 8,137 - 105 9 592 906 38 10,425 -106 78 498 6 116 130 12,740 - 107 664 579 44 158 339 15,047- 108 5 761 455 332 774 754 17,357 - 109 50 847 5342 592 592 1 701 19,667 -1010 455 052 511 20 758 029 3 104 21,975 -1011 4 118 054 813 169 923 159 11 588 24,283 -1012 37 607 912 0181 416 705 193 38 263 26,590 -1013 346 065 536 83911 992 858 452 108 971 28,896 - 1014 3 204 941 750 802 102 838 308 636 314 890 31,202- 101529 844 570 422 669 891 604 962 452 1 052 619 33,507 - 1016 279 238 341 033 925 7 804 289 844 3933 214 632 35,812 -1017 2 623 557 157 654 23368 883 734 693 281 7 956 589 38,116 - 1018 24 739 954 287 740 860 612 483 070 893 536 21 949 555 40,420- 1019234 057 667 276 344 607 5 481 624 169 369 96099 877 775 42,725 -1020 2 220 819 602 560 918 84049 347 193 044 659 701 222 744 644 45,028- 102121 127 269 486 018 731 928 446 579 871 578 168 707597 394 254 47,332 -1022 201 467 286 689 315 906 2904 060 704 006 019 620 994 1 932 355 208 49,636- 10231 925 320 391 606 803 968 923 37 083 513 766 578 631 309 7 250 186 216 51,939 -1024 18 435 599 767 349 200 867 866 339 996 354 713 708 049 069 17 146 907 278 54,243 \}
 В OEIS первая колонка значений π(x)π(x) — это последовательность ,π(x)xlnx+0,5π(x)xlnx+0,5 — этопоследовательность , аli(x)+0,5π(x)li(x)+0,5π(x) — этопоследовательность .

Алгоритмы вычисленияпи-функции


 Простой способ найти π(x)π(x), если xx не очень велико, — этоиспользование решета Эратосфена выдающего простые, не превосходящие xxи подсчитать их.
 Более продуманный способ вычисления π(x)π(x) был дан Лежандром: дан xx,если p1,p2,,pkp1,p2,,pk — различные простые числа, то число целыхчисел, не превосходящих xx и не делящихся на все pipi равно

 $\lfloor x\rfloor - \sum_{i}\left\lfloor\frac{x}{p_i}\right\rfloor + \sum_{i (где обозначает целую часть). Следовательно,полученное число равно

π(x)π(x)+1π(x)π(x)+1
 если числа p1,p2,,pkp1,p2,,pk — это все простые числа, непревосходящие xx.
 В 1870—1885 годах в серии статей Эрнст Мейссель описал (и использовал)практический комбинаторный способ вычисления π(x)π(x). Пустьp1,p2,,pnp1,p2,,pn — первые nn простых, обозначим Φ(m,n)Φ(m,n) числонатуральных чисел, не превосходящих mm, которые не делятся ни наодноpipi. Тогда

Φ(m,n)=Φ(m,n1)Φ([mpn],n1)Φ(m,n)=Φ(m,n1)Φ([mpn],n1)
 Возьмем натуральное mm, если n=π(3m)n=π(m3) и еслиμ=π(m)nμ=π(m)n, то

π(m)=Φ(m,n)+n(μ+1)+μ2μ21μk=1π(mpn+k)π(m)=Φ(m,n)+n(μ+1)+μ2μ21μk=1π(mpn+k)
 Используя этот подход, Мейссель вычислил π(x)π(x) дляx=5105;106;107;108x=5105;106;107;108.
 В 1959 году Деррик Генри Лемер расширил и упростил метод Мейсселя.Определим, для действительного mm и для натуральных n,kn,k величинуPk(m,n)Pk(m,n) как число чисел, не превосходящих m имеющих ровноk простых множителей, причем все они превосходят pnpn. Крометого, положим P0(m,n)=1P0(m,n)=1. Тогда

Φ(m,n)=+k=0Pk(m,n)Φ(m,n)=+k=0Pk(m,n)
 где сумма явно всегда имеет конечное число ненулевых слагаемых. Пустьyy — целое, такое, что 3mymm3ym, иположим n=π(y)n=π(y). Тогда P1(m,n)=π(m)nP1(m,n)=π(m)n и Pk(m,n)=0Pk(m,n)=0 приk3k3. Следовательно

π(m)=Φ(m,n)+n1P2(m,n)π(m)=Φ(m,n)+n1P2(m,n)
 Вычисление P2(m,n)P2(m,n) может быть получено следующим способом:

 $P_2(m,n)=\sum_{y С другой стороны, вычисление Φ(m,n)Φ(m,n) может быть выполнено с помощьюследующих правил:

  1. Φ(m,0)=mΦ(m,0)=m
  2. Φ(m,b)=Φ(m,b1)Φ(mpb,b1)Φ(m,b)=Φ(m,b1)Φ(mpb,b1)

 Используя этот метод и IBM 701, Лемер смог вычислитьπ(1010)π(1010).
 Дальнейшие усовершенствования этого метода были сделаны Lagarias,Miller, Odlyzko, Deleglise и Rivat.
 Китайский математик Hwang Cheng использовал следующие тождества:

e(a1)Θf(x)=f(ax),e(a1)Θf(x)=f(ax),


J(x)=n=1π(x1/n)nJ(x)=n=1π(x1/n)n
 и, полагая x=etx=et, выполняя преобразование Лапласа обеих частей иприменяя сумму геометрической прогрессии с enΘenΘ, получилвыражение:

12πic+icig(s)tsds=π(t)12πic+icig(s)tsds=π(t)


lnζ(s)s=(1eΘ(s))1g(s)lnζ(s)s=(1eΘ(s))1g(s)


Θ(s)=sddsΘ(s)=sdds

Другие функции, подсчитывающие простыечисла


 Другие функции, подсчитывающие простые числа, также используются,поскольку с ними удобнее работать. Одна из них — функция Римана, частообозначаемая как Π0(x)Π0(x) или J0(x)J0(x). Она испытывает прыжок на1/n для степеней простых pnpn, причем в точке прыжка xx еёзначение равно полусумме значений на обеих сторонах от xx. Этидополнительные детали нужны для того, чтобы она могла быть определенаобратным преобразованием Меллина. Формально, мы определим Π0(x)Π0(x) как

Π0(x)=12(pn<x1n +pnx1n)Π0(x)=12(pn<x1n +pnx1n)
 где p простое.
 Мы также можем записать

Π0(x)=xn=2Λ(n)lnn12Λ(x)lnx=n=11nπ0(nx)Π0(x)=n=2xΛ(n)lnn12Λ(x)lnx=n=11nπ0(xn)
 где Λ(n)Λ(n) — функция Мангольдта и

π0(x)=limε0π(xε)+π(x+ε)2.π0(x)=limε0π(xε)+π(x+ε)2.
 Формула обращения Мёбиуса дает

π0(x)=n=1μ(n)nΠ0(nx)π0(x)=n=1μ(n)nΠ0(xn)
 Используя известное соотношение между логарифмом дзета-функции Римана ифункцией Мангольдта ΛΛ, и используя формулу Перрона мы получим

lnζ(s)=s0Π0(x)xs1dxlnζ(s)=s0Π0(x)xs1dx
 Функция Римана имеет производящую функцию

 \{sum\_\{n=1\}\^\{infty\{Pi\_0(n)x\^n =\{sum\_\{a=2\}\^\{infty\{frac\{x\^\{a\}\}\{1-x\} -\{frac\{1\}\{2\}\{sum\_\{a=2\}\^\{infty
 \{sum\_\{b=2\}\^\{infty\{frac\{x\^\{ab\}\}\{1-x\} +\{frac\{1\}\{3\}\{sum\_\{a=2\}\^\{infty\{sum\_\{b=2\}\^\{infty\{sum\_\{c=2\}\^\{infty\{frac\{x\^\{abc\}\}\{1 -x\} -\{frac\{1\}\{4\}\{sum\_\{a=2\}\^\{infty\{sum\_\{b=2\}\^\{infty\{sum\_\{c=2\}\^\{infty\{sum\_\{d=2\}\^\{infty\{frac\{x\^\{abcd\}\}\{1-x\} + \{cdots
 Функции Чебышёва — это функции, подсчитывающие степени простых чиселpnpn с весом lnplnp:

θ(x)=pxlnpθ(x)=pxlnp
ψ(x)=pnxlnp=n=1θ(nx)=nxΛ(n).ψ(x)=pnxlnp=n=1θ(xn)=nxΛ(n).

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


 Формулы для функций, подсчитывающих простые числа, бывают двух видов:арифметические формулы и аналитические формулы. Аналитические формулыдля таких функций были впервые использованы для доказательства теоремы опростых числах. Они происходят от работ Римана и Мангольдта и в общемизвестны как явные формулы.
 Существует следующее выражение для ψψ-функции Чебышёва:

ψ0(x)=xρxρρln2π12ln(1x2)ψ0(x)=xρxρρln2π12ln(1x2)
 где

ψ0(x)=limε0ψ(xε)+ψ(x+ε)2.ψ0(x)=limε0ψ(xε)+ψ(x+ε)2.
 Здесь ρρ пробегает нули дзета-функции в критической полосе, гдедействительная часть ρρ лежит между нулем и единицей. Формула вернадля всех x>1x>1. Ряд по корням сходится условно, и может быть взят впорядке абсолютного значения возрастания мнимой части корней. Заметим,что аналогичная сумма по тривиальным корням дает последнее слагаемое вформуле.
 Для Π0(x)Π0(x) мы имеем следующую сложную формулу

Π0(x)=li(x)ρli(xρ)ln2+xdtt(t21)lnt.Π0(x)=li(x)ρli(xρ)ln2+xdtt(t21)lnt.
 Опять же, формула верна для всех x>1x>1, где ρρ — нетривиальныенули зета-функции, упорядоченные по их абсолютному значению, и, снова,последний интеграл берется со знаком «минус» и является такой же суммой,но по тривиальным нулям. Выражение li(xρ)li(xρ) вовтором члене может быть рассмотренно как Ei(ρlnx)Ei(ρlnx),где EiEi — это аналитическое продолжение интегральнойпоказательной функции на комплексную плоскость с ветвью, вырезаннойвдоль прямой x<0x<0.
 Таким образом, формула обращения Мёбиуса дает нам

π0(x)=R(x)ρR(xρ)1lnx+1πarctgπlnxπ0(x)=R(x)ρR(xρ)1lnx+1πarctgπlnx
 верное для x>1x>1, где

R(x)=n=1μ(n)nli(x1/n)=1+k=1(lnx)kk!kζ(k+1)R(x)=n=1μ(n)nli(x1/n)=1+k=1(lnx)kk!kζ(k+1)
 называется R-функцией также в честь Римана. Последний ряд в ней известенкак ряд Грама и сходится для всех x>0.
 Сумма по нетривиальным нулям дзета-функции в формуле для π0(x)описывает флуктуации π0(x), в то время как остальные слагаемые даютгладкую часть пи-функции, поэтому мы можем использовать

R(x)1lnx+1πarctgπlnx
 какнаилучшееприближение для π(x) для x>1.
 Амплитуда «шумной» части эвристически оценивается как x/lnx,поэтому флуктуации в распределении простых могут быть явно представленыΔ-функцией:

Δ(x)=(π0(x)R(x)+1lnx1πarctgπlnx)lnxx.
 Обширные таблицы значений Δ(x) доступны здесь.

Неравенства


 Здесь выписаны некоторые неравенства для π(x).

xlnx<π(x)<1,25506xlnxx17.
 Левое неравенство выполняется при x17, а правое — приx>1.
 Неравенства для n-го простого числа pn:

 $n\ln n+n\ln\ln n -n Левое неравенство верно при n1, а правое — приn6.
 Имеет место следующая асимптотика для n-го простого числа pn:

pn=nlnn(1+lnlnn1lnn+lnlnn2ln2n+1/2ln2lnn+3lnlnn11/2ln3n+O(ln3lnnln4n))

ГипотезаРимана


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

π(x)=li(x)+O(xlnx).
 В частности,

|π(x)li(x)|<18πxlnx,x2657.