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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Значения пи-функции для первых 60-и натуральных значений

История[править | править исходный текст]

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

 \frac{x}{\ln x}

в смысле, что

\lim\limits_{x\to +\infty}\frac{\pi(x)}{x/\ln x}=1.

Это утверждение — теорема о распределении простых чисел. Оно эквивалентно утверждению

\lim\limits_{x\to +\infty}\frac{\pi(x)}{\operatorname{li}(x)}=1

где \operatorname{li}~ — это интегральный логарифм. Теорема о простых числах впервые была доказана в 1896 Жаком Адамаром и независимо Валле-Пуссеном, используя дзета-функцию Римана введенную Риманом в 1859.

Точнее рост \pi(x) сейчас описывается как

\pi(x) = \operatorname{li}(x) + O\bigl(xe^{-\sqrt{\ln x}/15}\bigr)~

где O~ обозначает O большое. Для чаще всего используемых значений x (то есть когда x не сильно велико) \operatorname{li}(x)~ больше чем\pi(x)~, однако разность \pi (x)-\operatorname{li}(x)~ меняет свой знак бесконечное число раз. См. также Число Скьюза.

Доказательства теоремы о простых числах, не использующие дзета-функцию или комплексный анализ были найдены в 1948 году Атле Сельбергом и Паулем Эрдёшом (большей частью независимо).[5]

Таблицы для пи-функции, x / ln x и li(x)[править | править исходный текст]

В следующей таблице показан рост функций \pi(x),\frac{x}{\ln x},\operatorname{li}(x)~ по степеням 10. См. также,[3][6][7] and.[8]

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 первая колонка значений \pi(x) — это последовательность A006880, \pi(x)-\left\lfloor\frac{x}{\ln x}+0{,}5\right\rfloor — это последовательность A057835, а \lfloor\operatorname{li}(x)+0{,}5\rfloor-\pi(x) — это последовательность A057752.

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

Простой способ найти \pi(x), если x не очень велико, — это использование решета Эратосфена выдающего простые, не превосходящие x и подсчитать их.

Более продуманный способ вычисления \pi(x) был дан Лежандром: дан x, если p_1,p_2,\ldots,p_k — различные простые числа, то число целых чисел, не превосходящих x и не делящихся на все p_i равно

\lfloor x\rfloor - \sum_{i}\left\lfloor\frac{x}{p_i}\right\rfloor + \sum_{i<j}\left\lfloor\frac{x}{p_ip_j}\right\rfloor - \sum_{i<j<k}\left\lfloor\frac{x}{p_ip_jp_k}\right\rfloor + \cdots

(где \lfloor\cdots\rfloor обозначает целую часть). Следовательно, полученное число равно

\pi(x)-\pi\left(\sqrt{x}\right)+1

если числа p_1, p_2,\ldots,p_k — это все простые числа, не превосходящие \sqrt{x}.

В 1870—1885 годах в серии статей Эрнст Мейссель описал (и использовал) практический комбинаторный способ вычисления \pi(x). Пусть p_1,p_2,\ldots,p_n — первые n простых, обозначим \Phi(m,n) число натуральных чисел, не превосходящих m, которые не делятся ни на одноp_i. Тогда

\Phi(m,n)=\Phi(m,n-1)-\Phi\left(\left[\frac{m}{p_n}\right],n-1\right)

Возьмем натуральное m, если n=\pi\left(\sqrt[3]{m}\right) и если \mu=\pi\left(\sqrt{m}\right)-n, то

\pi(m)=\Phi(m,n)+n(\mu+1)+\frac{\mu^2-\mu}{2}-1-\sum_{k=1}^\mu\pi\left(\frac{m}{p_{n+k}}\right)

Используя этот подход, Мейссель вычислил \pi(x) для x=5\cdot 10^5;10^6;10^7;10^8.

В 1959 году Деррик Генри Лемер расширил и упростил метод Мейсселя. Определим, для действительного m и для натуральных n,k величину P_k(m,n) как число чисел, не превосходящих m имеющих ровно k простых множителей, причем все они превосходят p_n. Кроме того, положим P_0(m,n)=1. Тогда

\Phi(m,n)=\sum_{k=0}^{+\infty}P_k(m,n)

где сумма явно всегда имеет конечное число ненулевых слагаемых. Пусть y — целое, такое, что \sqrt[3]{m}\leqslant y\leqslant\sqrt{m}, и положим n=\pi(y). Тогда P_1(m,n)=\pi(m)-n и P_k(m,n)=0 при k\geqslant 3. Следовательно

\pi(m)=\Phi(m,n)+n-1-P_2(m,n)

Вычисление P_2(m,n) может быть получено следующим способом:

P_2(m,n)=\sum_{y<p\leqslant\sqrt{m}}\left(\pi\left(\frac mp\right)-\pi(p)+1\right)

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

  1. \Phi(m,0)=\lfloor m\rfloor
  2. \Phi(m,b)=\Phi(m,b-1)-\Phi\left(\frac m{p_b},b-1\right)

Используя этот метод и IBM 701, Лемер смог вычислить \pi\left(10^{10}\right).

Дальнейшие усовершенствования этого метода были сделаны Lagarias, Miller, Odlyzko, Deleglise и Rivat.[9]

Китайский математик Hwang Cheng использовал следующие тождества:[10]

e^{(a-1)\Theta}f(x)=f(ax),
J(x)=\sum_{n=1}^{\infty}\frac{\pi(x^{1/n})}{n}

и, полагая x=e^t, выполняя преобразование Лапласа обеих частей и применяя сумму геометрической прогрессии с e^{n\Theta}, получил выражение:

\frac{1}{2{\pi}i}\int_{c-i\infty}^{c+i\infty}g(s)t^{s}\,ds = \pi(t)
\frac{\ln \zeta(s)}{s}=(1-e^{\Theta(s)})^{-1}g(s)
\Theta(s)=s\frac{d}{ds}

Другие функции, подсчитывающие простые числа[править | править исходный текст]

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

\Pi_0(x) = \frac12 \bigg(\sum_{p^n < x} \frac1n\ + \sum_{p^n \le x} \frac1n\bigg)

где p простое.

Мы также может записать

\Pi_0(x) = \sum\limits_{n=2}^x \frac{\Lambda(n)}{\ln n} - \frac12 \frac{\Lambda(x)}{\ln x} = \sum_{n=1}^\infty \frac1n \pi_0(\sqrt[n]{x})

где \Lambda(n)~ — функция Мангольдта и

\pi_0(x) = \lim_{\varepsilon \rightarrow 0}\frac{\pi(x-\varepsilon)+\pi(x+\varepsilon)}2.

Формула обращения Мёбиуса дает

\pi_{0}(x) = \sum_{n=1}^\infty \frac{\mu(n)}n \Pi_0(\sqrt[n]{x})

Используя известное соотношение между логарифмом дзета-функции Римана и функцией Мангольдта \Lambda, и используя формулу Перрона мы получим

\ln \zeta(s) = s \int_0^\infty \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

Функция Чебышёва — это функция, подсчитывающая степени простых чисел p^n с весом \ln p:

\theta(x)=\sum_{p\leqslant x}\ln p
\psi(x) = \sum_{p^n\leqslant x} \ln p = \sum_{n=1}^\infty \theta(\sqrt[n]{x}) = \sum_{n\leqslant x}\Lambda(n).

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

Формулы для функций, подсчитывающих простые числа, бывают двух видов: арифметические формулы и аналитические формулы. Аналитические формулы для таких функций были впервые использованы для доказательства теоремы о простых числах. Они происходят от работ Римана и Мангольдта и в общем известны как явные формулы.[11]

Существует следующее выражение для \psi-функции Чебышёва:

\psi_0(x) = x - \sum_\rho \frac{x^\rho}{\rho} - \ln 2\pi - \frac12 \ln(1-x^{-2})

где

\psi_0(x) = \lim_{\varepsilon \rightarrow 0}\frac{\psi(x-\varepsilon)+\psi(x+\varepsilon)}2.

Здесь \rho~ пробегает нули дзета-функции в критической полосе, где действительная часть \rho~ лежит между нулем и единицей. Формула верна для всех x>1~. Ряд по корням сходится условно, и может быть взят в порядке абсолютного значения возрастания мнимой части корней. Заметим, что аналогичная сумма по тривиальным корням дает последнее слагаемое в формуле.

Для \scriptstyle\Pi_0(x) мы имеем следующую сложную формулу

\Pi_0(x) = \operatorname{li}(x) - \sum_{\rho}\operatorname{li}(x^{\rho}) - \ln 2 + \int_x^\infty \frac{dt}{t(t^2-1) \ln t}.

Опять же, формула верна для всех x>1, где \rho~ — нетривиальные нули зета-функции, упорядоченные по их абсолютному значению, и, снова, последний интеграл берется со знаком «минус» и является такой же суммой, но по тривиальным нулям. Выражение \operatorname{li}(x^{\rho}) во втором члене может быть рассмотренно как \operatorname{Ei}(\rho\ln x), где \operatorname{Ei} — это аналитическое продолжение интегральной показательной функции на комплексную плоскость с ветвью, вырезанной вдоль прямой x<0.

Таким образом, формула обращения Мёбиуса дает нам[12]

\pi_{0}(x)=\operatorname{R}(x)-\sum_{\rho}\operatorname{R}(x^{\rho})-\frac{1}{\ln x}+\frac{1}{\pi}\mathop{\mathrm{arctg}} \frac{\pi}{\ln x}

верное для x>1, где

\operatorname{R}(x)=\sum_{n=1}^{\infty}\frac{\mu (n)}{n}\operatorname{li}(x^{1/n})=1+\sum_{k=1}^\infty \frac{(\ln x)^k}{k! k \zeta(k+1)}

называется R-функцией также в честь Римана.[13] Последний ряд в ней известен как ряд Грэма[14] и сходится для всех x>0.

Сумма по нетривиальным нулям дзета-функции в формуле для \pi_0(x) описывает флуктуации \pi_0(x), в то время как остальные слагаемые дают гладкую часть пи-функции,[15] поэтому мы можем использовать

\operatorname{R}(x) - \frac{1}{\ln x} + \frac{1}{\pi}\mathop{\mathrm{arctg}}\frac{\pi}{\ln x}

как наилучшее приближение для \pi(x) для x>1.

Амплитуда «шумной» части эвристически оценивается как \sqrt x/\ln x, поэтому флуктуации в распределении простых могут быть явно представлены \Delta~-функцией:

\Delta(x) = \left( \pi_0(x) - \operatorname{R}(x) + \frac{1}{\ln x} - \frac{1}{\pi}\mathop{\mathrm{arctg}}\frac{\pi}{\ln x} \right) \frac{\ln x}{\sqrt x}.

Общирные таблицы значений \Delta(x)~ доступны здесь.[7]

Неравенства[править | править исходный текст]

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

\frac{x}{\ln x}<\pi(x)<1{,}25506\cdot \frac{x}{\ln x} \qquad x \geqslant 17.~

Левое неравенство выполняется при x \geqslant 17~, а правое — при x>1.~

Неравенства для n-го простого числа p_n~:

n\ln n+n\ln\ln n -n<p_n<n\ln n +n\ln\ln n, \ n\geqslant 6~

Левое неравенство верно при n \geqslant 1~, а правое — при n \geqslant 6~.

Имеет место следующая асимптотика для n-го простого числа p_n~:

 p_n = n\ln n\left(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)\right)~

Гипотеза Римана[править | править исходный текст]

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

\pi(x) = \operatorname{li}(x) + O(\sqrt{x} \ln x).

В частности,[16]

|\pi(x) - \operatorname{li}(x)| < \frac{1}{8\pi} \sqrt{x} \, \ln x, \qquad x \geqslant 2657.

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  1. Bach Eric Section 8.8 // Algorithmic Number Theory. — MIT Press, 1996. — Vol. 1. — P. 234. — ISBN 0-262-02405-5
  2. Weisstein, Eric W. Prime Counting Function (англ.) на сайте Wolfram MathWorld.
  3. 1 2 How many primes are there?. Chris K. Caldwell. Проверено 2 декабря 2008. Архивировано из первоисточника 20 сентября 2012.
  4. Dickson Leonard Eugene History of the Theory of Numbers I: Divisibility and Primality. — Dover Publications, 2005. — ISBN 0-486-44232-2
  5. K. Ireland, M. Rosen A Classical Introduction to Modern Number Theory. — Second. — Springer, 1998. — ISBN 0-387-97329-X
  6. Tables of values of pi(x) and of pi2(x). Tomas Oliveira e Silva. Проверено 14 сентября 2008. Архивировано из первоисточника 20 сентября 2012.
  7. 1 2 Values of π(x) and Δ(x) for various x's. Andrey V. Kulsha. Проверено 14 сентября 2008. Архивировано из первоисточника 20 сентября 2012.
  8. A table of values of pi(x). Xavier Gourdon, Pascal Sebah, Patrick Demichel. Проверено 14 сентября 2008. Архивировано из первоисточника 20 сентября 2012.
  9. Computing ?(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko method. Marc Deleglise and Joel Rivat, Mathematics of Computation, vol. 65, number 33, January 1996, pages 235–245. Проверено 14 сентября 2008. Архивировано из первоисточника 20 сентября 2012.
  10. Hwang H., Cheng. Demarches de la Geometrie et des Nombres de l'Universite du Bordeaux, Prime Magic conference.
  11. Titchmarsh E.C. The Theory of Functions, 2nd ed.. — Oxford University Press, 1960.
  12. (1970) «Some calculations related to Riemann's prime number formula». Mathematics of Computation (American Mathematical Society) 24 (112): 969–983. DOI:10.2307/2004630. ISSN 0025-5718.
  13. Weisstein, Eric W. Riemann Prime Counting Function (англ.) на сайте Wolfram MathWorld.
  14. Weisstein, Eric W. Gram Series (англ.) на сайте Wolfram MathWorld.
  15. The encoding of the prime distribution by the zeta zeros. Matthew Watkins. Проверено 14 сентября 2008. Архивировано из первоисточника 20 сентября 2012.
  16. Lowell Schoenfeld (1976). «Sharper bounds for the Chebyshev functions θ(x) and ψ(x). II». Mathematics of Computation (American Mathematical Society) 30 (134): 337–360. DOI:10.2307/2005976. ISSN 0025-5718.

Литература[править | править исходный текст]

  • К. Прахар Распределение простых чисел. — Мир, 1967.

Ссылки[править | править исходный текст]