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

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

История

 Большой интерес в теории чисел представляет скорость роста пи-функции. В конце 18-го столетия Гауссом и Лежандром было выдвинуто предположение, что пи-функция оценивается как
 
  xlnx$\frac{x}{\ln x}$
  в смысле, что
 
  limx→+∞π(x)x/lnx=1.$\underset{x\to +\mathrm{\infty }}{lim}\frac{\pi (x)}{x/\ln x}=1.$
  Это утверждение — теорема о распределении простых чисел. Оно эквивалентно утверждению
 
  limx→+∞π(x)li(x)=1$\underset{x\to +\mathrm{\infty }}{lim}\frac{\pi (x)}{\mathrm{li}(x)}=1$
  где li$\mathrm{li}$ — это интегральный логарифм. Теорема о простых числах впервые была доказана в 1896 Жаком Адамаром и независимо Валле-Пуссеном, используя дзета-функцию Римана введенную Риманом в 1859.
 Точнее рост π(x)$\pi (x)$ сейчас описывается как
 
  π(x)=li(x)+O(xe−lnx√/15)$\pi (x)=\mathrm{li}(x)+O(x{e}^{-\sqrt{\ln x}/15})$
  где O$O$ обозначает O большое. Для чаще всего используемых значений x (то есть когда x не сильно велико) li(x)$\mathrm{li}(x)$ больше чем π(x)$\pi (x)$, однако разность π(x)−li(x)$\pi (x)-\mathrm{li}(x)$ меняет свой знак бесконечное число раз. См. также Число Скьюза.
 Доказательства теоремы о простых числах, не использующие дзета-функцию или комплексный анализ были найдены в 1948 году Атле Сельбергом и Паулем Эрдёшом (большей частью независимо).
 

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

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

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

 Простой способ найти π(x)$\pi (x)$, если x$x$ не очень велико, — это использование решета Эратосфена выдающего простые, не превосходящие x$x$ и подсчитать их.
 Более продуманный способ вычисления π(x)$\pi (x)$ был дан Лежандром: дан x$x$, если p1,p2,…,pk$p_1,p_2,\dots ,p_k$ — различные простые числа, то число целых чисел, не превосходящих x$x$ и не делящихся на все pi$p_i$ равно
 
  $\lfloor x\rfloor - \sum_{i}\left\lfloor\frac{x}{p_i}\right\rfloor + \sum_{i  (где ⌊⋯⌋$\lfloor \cdots \rfloor$ обозначает целую часть). Следовательно, полученное число равно
 
  π(x)−π(x√)+1$\pi (x)-\pi \left(\sqrt{x}\right)+1$
  если числа p1,p2,…,pk$p_1,p_2,\dots ,p_k$ — это все простые числа, не превосходящие x√$\sqrt{x}$.
 В 1870—1885 годах в серии статей Эрнст Мейссель описал (и использовал) практический комбинаторный способ вычисления π(x)$\pi (x)$. Пусть p1,p2,…,pn$p_1,p_2,\dots ,p_n$ — первые n$n$ простых, обозначим Φ(m,n)$\mathrm{\Phi }(m,n)$ число натуральных чисел, не превосходящих m$m$, которые не делятся ни на одноpi$p_i$. Тогда
 
  Φ(m,n)=Φ(m,n−1)−Φ([mpn],n−1)$\mathrm{\Phi }(m,n)=\mathrm{\Phi }(m,n-1)-\mathrm{\Phi }(\left[\frac{m}{p_n}\right],n-1)$
  Возьмем натуральное m$m$, если n=π(m−−√3)$n=\pi \left(\sqrt[3]{m}\right)$ и если μ=π(m−−√)−n$\mu =\pi \left(\sqrt{m}\right)-n$, то
 
  π(m)=Φ(m,n)+n(μ+1)+μ2−μ2−1−∑μk=1π(mpn+k)$\pi (m)=\mathrm{\Phi }(m,n)+n(\mu +1)+\frac{{\mu }^2-\mu }{2}-1-\sum _{k=1}^{\mu }\pi \left(\frac{m}{p_{n+k}}\right)$
  Используя этот подход, Мейссель вычислил π(x)$\pi (x)$ для x=5⋅105;106;107;108$x=5\cdot {10}^5;{10}^6;{10}^7;{10}^8$.
 В 1959 году Деррик Генри Лемер расширил и упростил метод Мейсселя. Определим, для действительного m$m$ и для натуральных n,k$n,k$ величину Pk(m,n)$P_k(m,n)$ как число чисел, не превосходящих m имеющих ровно k простых множителей, причем все они превосходят pn$p_n$. Кроме того, положим P0(m,n)=1$P_0(m,n)=1$. Тогда
 
  Φ(m,n)=∑+∞k=0Pk(m,n)$\mathrm{\Phi }(m,n)=\sum _{k=0}^{+\mathrm{\infty }}{P}_k(m,n)$
  где сумма явно всегда имеет конечное число ненулевых слагаемых. Пусть y$y$ — целое, такое, что m−−√3⩽y⩽m−−√$\sqrt[3]{m}⩽y⩽\sqrt{m}$, и положим n=π(y)$n=\pi (y)$. Тогда P1(m,n)=π(m)−n$P_1(m,n)=\pi (m)-n$ и Pk(m,n)=0$P_k(m,n)=0$ при k⩾3$k⩾3$. Следовательно
 
  π(m)=Φ(m,n)+n−1−P2(m,n)$\pi (m)=\mathrm{\Phi }(m,n)+n-1-P_2(m,n)$
  Вычисление P2(m,n)$P_2(m,n)$ может быть получено следующим способом:
 
  $P_2(m,n)=\sum_{y  С другой стороны, вычисление Φ(m,n)$\mathrm{\Phi }(m,n)$ может быть выполнено с помощью следующих правил:
 

 
1. Φ(m,0)=⌊m⌋$\mathrm{\Phi }(m,0)=\lfloor m\rfloor$
    
2. Φ(m,b)=Φ(m,b−1)−Φ(mpb,b−1)$\mathrm{\Phi }(m,b)=\mathrm{\Phi }(m,b-1)-\mathrm{\Phi }(\frac{m}{p_b},b-1)$

 Используя этот метод и IBM 701, Лемер смог вычислить π(1010)$\pi \left({10}^{10}\right)$.
 Дальнейшие усовершенствования этого метода были сделаны Lagarias, Miller, Odlyzko, Deleglise и Rivat.
 Китайский математик Hwang Cheng использовал следующие тождества:
 
  e(a−1)Θf(x)=f(ax),$e^{(a-1)\mathrm{\Theta }}f(x)=f(ax),$
 
 
 J(x)=∑∞n=1π(x1/n)n$J(x)=\sum _{n=1}^{\mathrm{\infty }}\frac{\pi (x^{1/n})}{n}$
  и, полагая x=et$x=e^t$, выполняя преобразование Лапласа обеих частей и применяя сумму геометрической прогрессии с enΘ$e^{n\mathrm{\Theta }}$, получил выражение:
 
  12πi∫c+i∞c−i∞g(s)tsds=π(t)$\frac{1}{2\pi i}{\int }_{c-i\mathrm{\infty }}^{c+i\mathrm{\infty }}g(s)t^{s}ds=\pi (t)$
 
 
 lnζ(s)s=(1−eΘ(s))−1g(s)$\frac{\ln \zeta (s)}{s}=(1-e^{\mathrm{\Theta }(s)}{)}^{-1}g(s)$
 
 
 Θ(s)=sdds$\mathrm{\Theta }(s)=s\frac{d}{ds}$
 

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

 Другие функции, подсчитывающие простые числа, также используются, поскольку с ними удобнее работать. Одна из них — функция Римана, часто обозначаемая как Π0(x)${\mathrm{\Pi }}_0(x)$ или J0(x)$J_0(x)$. Она испытывает прыжок на 1/n для степеней простых pn$p^n$, причем в точке прыжка x$x$ её значение равно полусумме значений на обеих сторонах от x$x$. Эти дополнительные детали нужны для того, чтобы она могла быть определена обратным преобразованием Меллина. Формально, мы определим Π0(x)${\mathrm{\Pi }}_0(x)$ как
 
  Π0(x)=12(∑pn<x1n +∑pn≤x1n)${\mathrm{\Pi }}_0(x)=\frac{1}{2}(\sum _{p^n<x}\frac{1}{n}+\sum _{p^n\le x}\frac{1}{n})$
  где p простое.
 Мы также можем записать
 
  Π0(x)=∑n=2xΛ(n)lnn−12Λ(x)lnx=∑∞n=11nπ0(x√n)${\mathrm{\Pi }}_0(x)=\sum _{n=2}^x\frac{\mathrm{\Lambda }(n)}{\ln n}-\frac{1}{2}\frac{\mathrm{\Lambda }(x)}{\ln x}=\sum _{n=1}^{\mathrm{\infty }}\frac{1}{n}{\pi }_0(\sqrt[n]{x})$
  где Λ(n)$\mathrm{\Lambda }(n)$ — функция Мангольдта и
 
  π0(x)=limε→0π(x−ε)+π(x+ε)2.${\pi }_0(x)=\underset{\epsilon \to 0}{lim}\frac{\pi (x-\epsilon )+\pi (x+\epsilon )}{2}.$
  Формула обращения Мёбиуса дает
 
  π0(x)=∑∞n=1μ(n)nΠ0(x√n)${\pi }_0(x)=\sum _{n=1}^{\mathrm{\infty }}\frac{\mu (n)}{n}{\mathrm{\Pi }}_0(\sqrt[n]{x})$
  Используя известное соотношение между логарифмом дзета-функции Римана и функцией Мангольдта Λ$\mathrm{\Lambda }$, и используя формулу Перрона мы получим
 
  lnζ(s)=s∫∞0Π0(x)x−s−1dx$\ln \zeta (s)=s{\int }_0^{\mathrm{\infty }}{\mathrm{\Pi }}_0(x)x^{-s-1}dx$
  Функция Римана имеет производящую функцию
 
  \{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$p^n$ с весом lnp$\ln p$:
 
  θ(x)=∑p⩽xlnp$\theta (x)=\sum _{p⩽x}\ln p$
 ψ(x)=∑pn⩽xlnp=∑∞n=1θ(x√n)=∑n⩽xΛ(n).$\psi (x)=\sum _{p^n⩽x}\ln p=\sum _{n=1}^{\mathrm{\infty }}\theta (\sqrt[n]{x})=\sum _{n⩽x}\mathrm{\Lambda }(n).$
 

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

 Формулы для функций, подсчитывающих простые числа, бывают двух видов: арифметические формулы и аналитические формулы. Аналитические формулы для таких функций были впервые использованы для доказательства теоремы о простых числах. Они происходят от работ Римана и Мангольдта и в общем известны как явные формулы.
 Существует следующее выражение для ψ$\psi$-функции Чебышёва:
 
  ψ0(x)=x−∑ρxρρ−ln2π−12ln(1−x−2)${\psi }_0(x)=x-\sum _{\rho }\frac{x^{\rho }}{\rho }-\ln 2\pi -\frac{1}{2}\ln (1-x^{-2})$
  где
 
  ψ0(x)=limε→0ψ(x−ε)+ψ(x+ε)2.${\psi }_0(x)=\underset{\epsilon \to 0}{lim}\frac{\psi (x-\epsilon )+\psi (x+\epsilon )}{2}.$
  Здесь ρ$\rho$ пробегает нули дзета-функции в критической полосе, где действительная часть ρ$\rho$ лежит между нулем и единицей. Формула верна для всех x>1$x>1$. Ряд по корням сходится условно, и может быть взят в порядке абсолютного значения возрастания мнимой части корней. Заметим, что аналогичная сумма по тривиальным корням дает последнее слагаемое в формуле.
 Для Π0(x)${\mathrm{\Pi }}_0(x)$ мы имеем следующую сложную формулу
 
  Π0(x)=li(x)−∑ρli(xρ)−ln2+∫∞xdtt(t2−1)lnt.${\mathrm{\Pi }}_0(x)=\mathrm{li}(x)-\sum _{\rho }\mathrm{li}(x^{\rho })-\ln 2+{\int }_x^{\mathrm{\infty }}\frac{dt}{t(t^2-1)\ln t}.$
  Опять же, формула верна для всех x>1$x>1$, где ρ$\rho$ — нетривиальные нули зета-функции, упорядоченные по их абсолютному значению, и, снова, последний интеграл берется со знаком «минус» и является такой же суммой, но по тривиальным нулям. Выражение li(xρ)$\mathrm{li}(x^{\rho })$ во втором члене может быть рассмотренно как Ei(ρlnx)$\mathrm{Ei}(\rho \ln x)$, где Ei$\mathrm{Ei}$ — это аналитическое продолжение интегральной показательной функции на комплексную плоскость с ветвью, вырезанной вдоль прямой x<0$x<0$.
 Таким образом, формула обращения Мёбиуса дает нам
 
  π0(x)=R(x)−∑ρR(xρ)−1lnx+1πarctgπlnx${\pi }_0(x)=\mathrm{R}(x)-\sum _{\rho }\mathrm{R}(x^{\rho })-\frac{1}{\ln x}+\frac{1}{\pi }\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{g}\frac{\pi }{\ln x}$
  верное для x>1$x>1$, где
 
  R(x)=∑∞n=1μ(n)nli(x1/n)=1+∑∞k=1(lnx)kk!kζ(k+1)$\mathrm{R}(x)=\sum _{n=1}^{\mathrm{\infty }}\frac{\mu (n)}{n}\mathrm{li}(x^{1/n})=1+\sum _{k=1}^{\mathrm{\infty }}\frac{(\ln x{)}^k}{k!k\zeta (k+1)}$
  называется R-функцией также в честь Римана. Последний ряд в ней известен как ряд Грама и сходится для всех x>0$x>0$.
 Сумма по нетривиальным нулям дзета-функции в формуле для π0(x)${\pi }_0(x)$ описывает флуктуации π0(x)${\pi }_0(x)$, в то время как остальные слагаемые дают гладкую часть пи-функции, поэтому мы можем использовать
 
  R(x)−1lnx+1πarctgπlnx$\mathrm{R}(x)-\frac{1}{\ln x}+\frac{1}{\pi }\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{g}\frac{\pi }{\ln x}$
  как наилучшее приближение для π(x)$\pi (x)$ для x>1$x>1$.
 Амплитуда «шумной» части эвристически оценивается как x√/lnx$\sqrt{x}/\ln x$, поэтому флуктуации в распределении простых могут быть явно представлены Δ$\mathrm{\Delta }$-функцией:
 
  Δ(x)=(π0(x)−R(x)+1lnx−1πarctgπlnx)lnxx√.$\mathrm{\Delta }(x)=({\pi }_0(x)-\mathrm{R}(x)+\frac{1}{\ln x}-\frac{1}{\pi }\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{g}\frac{\pi }{\ln x})\frac{\ln x}{\sqrt{x}}.$
  Обширные таблицы значений Δ(x)$\mathrm{\Delta }(x)$ доступны здесь.
 

Неравенства

 Здесь выписаны некоторые неравенства для π(x)$\pi (x)$.
 
  xlnx<π(x)<1,25506⋅xlnxx⩾17.$\frac{x}{\ln x}<\pi (x)<\mathrm{1,255}06\cdot \frac{x}{\ln x}x⩾17.$
  Левое неравенство выполняется при x⩾17$x⩾17$, а правое — при x>1.$x>1.$
 Неравенства для n$n$-го простого числа pn$p_n$:
 
  $n\ln n+n\ln\ln n -n  Левое неравенство верно при n⩾1$n⩾1$, а правое — при n⩾6$n⩾6$.
 Имеет место следующая асимптотика для n$n$-го простого числа pn$p_n$:
 
  pn=nlnn(1+lnlnn−1lnn+lnlnn−2ln2n+−1/2ln2lnn+3lnlnn−11/2ln3n+O(ln3lnnln4n))$p_n=n\ln n(1+\frac{\ln \ln n-1}{\ln n}+\frac{\ln \ln n-2}{{\ln }^{2}n}+\frac{-1/2{\ln }^2\ln n+3\ln \ln n-11/2}{{\ln }^{3}n}+O\left(\frac{{\ln }^3\ln n}{{\ln }^{4}n}\right))$
 

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

 Гипотеза Римана эквивалентна более точной границе ошибки приближения π(x)$\pi (x)$ интегральным логарифмом, а отсюда и более регулярному распределению простых чисел
 
  π(x)=li(x)+O(x√lnx).$\pi (x)=\mathrm{li}(x)+O(\sqrt{x}\ln x).$
  В частности,
 
  |π(x)−li(x)|<18πx√lnx,x⩾2657.$|\pi (x)-\mathrm{li}(x)|<\frac{1}{8\pi }\sqrt{x}\ln x,x⩾2657.$