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

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

Файл:PrimePi.svg
Значения пи-функции для первых 60 натуральных чисел

История

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

<math> \frac{x}{\ln x}</math>

в смысле, что

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

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

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

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

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

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

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

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

Таблицы для пи-функции, x / ln x и li(x)

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

x π(x) π(x) − x / ln x li(x) − π(x) x / π(x) π(x)/x (доля простых чисел)
10 4 −0,3 2,2 2,500 40 %
102 25 3,3 5,1 4,000 25 %
103 168 23 10 5,952 16,8 %
104 1 229 143 17 8,137 12,3 %
105 9 592 906 38 10,425 9,59 %
106 78 498 6 116 130 12,740 7,85 %
107 664 579 44 158 339 15,047 6,65 %
108 5 761 455 332 774 754 17,357 5,76 %
109 50 847 534 2 592 592 1 701 19,667 5,08 %
1010 455 052 511 20 758 029 3 104 21,975 4,55 %
1011 4 118 054 813 169 923 159 11 588 24,283 4,12 %
1012 37 607 912 018 1 416 705 193 38 263 26,590 3,76 %
1013 346 065 536 839 11 992 858 452 108 971 28,896 3,46 %
1014 3 204 941 750 802 102 838 308 636 314 890 31,202 3,20 %
1015 29 844 570 422 669 891 604 962 452 1 052 619 33,507 2,98 %
1016 279 238 341 033 925 7 804 289 844 393 3 214 632 35,812 2,79 %
1017 2 623 557 157 654 233 68 883 734 693 281 7 956 589 38,116 2,62 %
1018 24 739 954 287 740 860 612 483 070 893 536 21 949 555 40,420 2,47 %
1019 234 057 667 276 344 607 5 481 624 169 369 960 99 877 775 42,725 2,34 %
1020 2 220 819 602 560 918 840 49 347 193 044 659 701 222 744 644 45,028 2,22 %
1021 21 127 269 486 018 731 928 446 579 871 578 168 707 597 394 254 47,332 2,11 %
1022 201 467 286 689 315 906 290 4 060 704 006 019 620 994 1 932 355 208 49,636 2,01 %
1023 1 925 320 391 606 803 968 923 37 083 513 766 578 631 309 7 250 186 216 51,939 1,92 %
1024 18 435 599 767 349 200 867 866 339 996 354 713 708 049 069 17 146 907 278 54,243 1,84 %
1025 176 846 309 399 143 769 411 680 3 128 516 637 843 038 351 228 55 160 980 939 56,546 1,77 %
1026 1 699 246 750 872 437 141 327 603 28 883 358 936 853 188 823 261 155 891 678 121 58,850 1,70 %
1027 16 352 460 426 841 680 446 427 399 267 479 615 610 131 274 163 365 508 666 658 006 61,153 1,64 %

В OEIS первая колонка значений <math>\pi(x)</math> — это последовательность Шаблон:OEIS2C, <math>\pi(x)-\left\lfloor\frac{x}{\ln x}+0{,}5\right\rfloor</math> — это последовательность Шаблон:OEIS2C, а <math>\lfloor\operatorname{li}(x)+0{,}5\rfloor-\pi(x)</math> — это последовательность Шаблон:OEIS2C.

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

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

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

<math>\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</math>

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

<math>\pi(x)-\pi\left(\sqrt{x}\right)+1</math>

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

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

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

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

<math>\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)</math>

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

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

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

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

<math>\pi(m)=\Phi(m,n)+n-1-P_2(m,n)</math>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

<math>\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})</math>

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

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

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

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

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

<math>\ln \zeta(s) = s \int_0^\infty \Pi_0(x) x^{-s-1}\,dx</math>

Функция Римана имеет производящую функцию

<math>\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 </math>

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

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

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

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

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

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

где

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

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

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

<math>\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}.</math>

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

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

<math>\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}</math>

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

<math>\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)}</math>

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

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

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

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

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

<math>\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}.</math>

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

Неравенства

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

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

Левое неравенство выполняется при <math>x \geqslant 17</math>, а правое — при <math>x>1.</math>[16]

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

<math>n\ln n+n\ln\ln n -3/2\cdot n<p_n<n\ln n +n\ln\ln n, \ n\geqslant 6.</math>

Левое неравенство верно при <math>n \geqslant 2</math>, а правое — при <math>n \geqslant 6</math>.

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

<math> 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)</math>

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

Шаблон:Main

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

<math>\pi(x) = \operatorname{li}(x) + O(\sqrt{x} \ln x).</math>

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

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

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки