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

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

История


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

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

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

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

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

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

/ ln \emphx и li(x)
 В следующей таблице показан рост функций π(x),xlnx,li(x) по степеням 10.
 : \{ ! x ! π(x) ! π(x) − x / ln x ! li(x) − π(x) ! x / π(x) - 10 4 −0,3 2,2 2,500 - 102 25 3,3 5,1 4,000 - 103 168 23 10 5,952 - 104 1 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 534 2 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 018 1 416 705 193 38 263 26,590 - 1013 346 065 536 839 11 992 858 452 108 971 28,896 - 1014 3 204 941 750 802 102 838 308 636 314 890 31,202 - 1015 29 844 570 422 669 891 604 962 452 1 052 619 33,507 - 1016 279 238 341 033 925 7 804 289 844 393 3 214 632 35,812 - 1017 2 623 557 157 654 233 68 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 - 1019 234 057 667 276 344 607 5 481 624 169 369 960 99 877 775 42,725 - 1020 2 220 819 602 560 918 840 49 347 193 044 659 701 222 744 644 45,028 - 1021 21 127 269 486 018 731 928 446 579 871 578 168 707 597 394 254 47,332 - 1022 201 467 286 689 315 906 290 4 060 704 006 019 620 994 1 932 355 208 49,636 - 1023 1 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)xlnx+0,5 — это последовательность , а li(x)+0,5π(x) — это последовательность .

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


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

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

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

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

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

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

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

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

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

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

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


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

12πicic+ig(s)tsds=π(t)


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


Θ(s)=sdds

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


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

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

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

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

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

lnζ(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
 Функции Чебышёва — это функции, подсчитывающие степени простых чисел pn с весом lnp:

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

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


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

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

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

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

π0(x)=R(x)ρR(xρ)1lnx+1πarctgπlnx
  верное для x>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.