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

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

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

История

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

${\displaystyle {\frac {x}{\ln x}}}$

в смысле, что

${\displaystyle \lim \limits _{x\to +\infty }{\frac {\pi (x)}{x/\ln x}}=1.}$

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

${\displaystyle \lim \limits _{x\to +\infty }{\frac {\pi (x)}{\operatorname {li} (x)}}=1}$

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

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

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

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

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

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

В следующей таблице показан рост функций ${\displaystyle \pi (x),{\frac {x}{\ln x}},\operatorname {li} (x)}$ по степеням 10.

x	π(x)	π(x) − x / ln x	li(x) − π(x)	x / π(x)	π(x)/x (доля простых чисел)
10	4	−0,3	2,2	2,500	40 %
10^2	25	3,3	5,1	4,000	25 %
10^3	168	23	10	5,952	16,8 %
10^4	1 229	143	17	8,137	12,3 %
10^5	9 592	906	38	10,425	9,59 %
10^6	78 498	6 116	130	12,740	7,85 %
10^7	664 579	44 158	339	15,047	6,65 %
10^8	5 761 455	332 774	754	17,357	5,76 %
10^9	50 847 534	2 592 592	1 701	19,667	5,08 %
10^10	455 052 511	20 758 029	3 104	21,975	4,55 %
10^11	4 118 054 813	169 923 159	11 588	24,283	4,12 %
10^12	37 607 912 018	1 416 705 193	38 263	26,590	3,76 %
10^13	346 065 536 839	11 992 858 452	108 971	28,896	3,46 %
10^14	3 204 941 750 802	102 838 308 636	314 890	31,202	3,20 %
10^15	29 844 570 422 669	891 604 962 452	1 052 619	33,507	2,98 %
10^16	279 238 341 033 925	7 804 289 844 393	3 214 632	35,812	2,79 %
10^17	2 623 557 157 654 233	68 883 734 693 281	7 956 589	38,116	2,62 %
10^18	24 739 954 287 740 860	612 483 070 893 536	21 949 555	40,420	2,47 %
10^19	234 057 667 276 344 607	5 481 624 169 369 960	99 877 775	42,725	2,34 %
10^20	2 220 819 602 560 918 840	49 347 193 044 659 701	222 744 644	45,028	2,22 %
10^21	21 127 269 486 018 731 928	446 579 871 578 168 707	597 394 254	47,332	2,11 %
10^22	201 467 286 689 315 906 290	4 060 704 006 019 620 994	1 932 355 208	49,636	2,01 %
10^23	1 925 320 391 606 803 968 923	37 083 513 766 578 631 309	7 250 186 216	51,939	1,92 %
10^24	18 435 599 767 349 200 867 866	339 996 354 713 708 049 069	17 146 907 278	54,243	1,84 %
10^25	176 846 309 399 143 769 411 680	3 128 516 637 843 038 351 228	55 160 980 939	56,546	1,77 %
10^26	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 %
10^27	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) первая колонка значений ${\displaystyle \pi (x)}$ — это последовательность A006880, ${\displaystyle \pi (x)-\left\lfloor {\frac {x}{\ln x}}+0{,}5\right\rfloor }$ — это последовательность A057835, а ${\displaystyle \lfloor \operatorname {li} (x)+0{,}5\rfloor -\pi (x)}$ — это последовательность A057752.

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

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

Более продуманный способ вычисления ${\displaystyle \pi (x)}$ был дан (Лежандром): дан ${\displaystyle x}$, если ${\displaystyle p_{1},p_{2},\ldots ,p_{k}}$ — различные простые числа, то число целых чисел, не превосходящих ${\displaystyle x}$ и не делящихся на все ${\displaystyle p_{i}}$ равно

${\displaystyle \lfloor x\rfloor -\sum _{i}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor +\sum _{i<j}\left\lfloor {\frac {x}{p_{i}p_{j}}}\right\rfloor -\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_{j}p_{k}}}\right\rfloor +\cdots }$

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

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

если числа ${\displaystyle p_{1},p_{2},\ldots ,p_{k}}$ — это все простые числа, не превосходящие ${\displaystyle {\sqrt {x}}}$.

В 1870—1885 годах в серии статей (Эрнст Майссель) описал (и использовал) практический комбинаторный способ вычисления ${\displaystyle \pi (x)}$. Пусть ${\displaystyle p_{1},p_{2},\ldots ,p_{n}}$ — первые ${\displaystyle n}$ простых, обозначим ${\displaystyle \Phi (m,n)}$ число натуральных чисел, не превосходящих ${\displaystyle m}$, которые не делятся ни на одно ${\displaystyle p_{i}}$. Тогда

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

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

${\displaystyle \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)}$

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

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

${\displaystyle \Phi (m,n)=\sum _{k=0}^{+\infty }P_{k}(m,n)}$

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

${\displaystyle \pi (m)=\Phi (m,n)+n-1-P_{2}(m,n)}$

Вычисление ${\displaystyle P_{2}(m,n)}$ может быть получено следующим способом:

${\displaystyle P_{2}(m,n)=\sum _{y<p\leqslant {\sqrt {m}}}\left(\pi \left({\frac {m}{p}}\right)-\pi (p)+1\right)}$

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

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

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

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

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

${\displaystyle e^{(a-1)\Theta }f(x)=f(ax),}$

${\displaystyle J(x)=\sum _{n=1}^{\infty }{\frac {\pi (x^{1/n})}{n}}}$

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

${\displaystyle {\frac {1}{2{\pi }i}}\int _{c-i\infty }^{c+i\infty }g(s)t^{s}\,ds=\pi (t)}$

${\displaystyle {\frac {\ln \zeta (s)}{s}}=(1-e^{\Theta (s)})^{-1}g(s)}$

${\displaystyle \Theta (s)=s{\frac {d}{ds}}}$

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

Другие функции, подсчитывающие простые числа, также используются, поскольку с ними удобнее работать. Одна из них — функция Римана, часто обозначаемая как ${\displaystyle \Pi _{0}(x)}$ или ${\displaystyle J_{0}(x)}$. Она испытывает прыжок на 1/n для степеней простых ${\displaystyle p^{n}}$, причем в точке прыжка ${\displaystyle x}$ её значение равно полусумме значений на обеих сторонах от ${\displaystyle x}$. Эти дополнительные детали нужны для того, чтобы она могла быть определена обратным (преобразованием Меллина). Формально, мы определим ${\displaystyle \Pi _{0}(x)}$ как

${\displaystyle \Pi _{0}(x)={\frac {1}{2}}{\bigg (}\sum _{p^{n}<x}{\frac {1}{n}}\ +\sum _{p^{n}\leq x}{\frac {1}{n}}{\bigg )}}$

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

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

${\displaystyle \Pi _{0}(x)=\sum \limits _{n=2}^{x}{\frac {\Lambda (n)}{\ln n}}-{\frac {1}{2}}{\frac {\Lambda (x)}{\ln x}}=\sum _{n=1}^{\infty }{\frac {1}{n}}\pi _{0}({\sqrt[{n}]{x}})}$

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

${\displaystyle \pi _{0}(x)=\lim _{\varepsilon \rightarrow 0}{\frac {\pi (x-\varepsilon )+\pi (x+\varepsilon )}{2}}.}$

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

${\displaystyle \pi _{0}(x)=\sum _{n=1}^{\infty }{\frac {\mu (n)}{n}}\Pi _{0}({\sqrt[{n}]{x}})}$

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

${\displaystyle \ln \zeta (s)=s\int _{0}^{\infty }\Pi _{0}(x)x^{-s-1}\,dx}$

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

${\displaystyle \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 }$

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

${\displaystyle \theta (x)=\sum _{p\leqslant x}\ln p}$

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

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

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

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

${\displaystyle \psi _{0}(x)=x-\sum _{\rho }{\frac {x^{\rho }}{\rho }}-\ln 2\pi -{\frac {1}{2}}\ln(1-x^{-2})}$

где

${\displaystyle \psi _{0}(x)=\lim _{\varepsilon \rightarrow 0}{\frac {\psi (x-\varepsilon )+\psi (x+\varepsilon )}{2}}.}$

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

Для ${\displaystyle \scriptstyle \Pi _{0}(x)}$ мы имеем следующую сложную формулу

${\displaystyle \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}}.}$

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

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

${\displaystyle \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}}}$

верное для ${\displaystyle x>1}$, где

${\displaystyle \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-функцией также в честь Римана. Последний ряд в ней известен как ряд (Грама) и сходится для всех ${\displaystyle x>0}$.

Сумма по нетривиальным нулям дзета-функции в формуле для ${\displaystyle \pi _{0}(x)}$ описывает флуктуации ${\displaystyle \pi _{0}(x)}$, в то время как остальные слагаемые дают гладкую часть пи-функции, поэтому мы можем использовать

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

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

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

${\displaystyle \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}}}.}$

Обширные таблицы значений ${\displaystyle \Delta (x)}$ доступны здесь.

Неравенства

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

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

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

Неравенства для ${\displaystyle n}$-го простого числа ${\displaystyle p_{n}}$:

${\displaystyle n\ln n+n\ln \ln n-3/2\cdot n<p_{n}<n\ln n+n\ln \ln n,\ n\geqslant 6.}$

Левое неравенство верно при ${\displaystyle n\geqslant 2}$, а правое — при ${\displaystyle n\geqslant 6}$.

Имеет место следующая асимптотика для ${\displaystyle n}$-го простого числа ${\displaystyle p_{n}}$:

${\displaystyle 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)}$

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

Основная статья: (Гипотеза Римана)

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

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

В частности,

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

См. также

• (Теорема о распределении простых чисел)
• (Постулат Бертрана)
• (Число Скьюза)

Примечания

1. Bach, Eric; Shallit, Jeffrey. Section 8.8 // Algorithmic Number Theory (неопр.). — MIT Press, 1996. — Т. 1. — С. 234. — .
2. Weisstein, Eric W. Prime Counting Function (англ.) на сайте Wolfram (MathWorld).
3. How many primes are there?  (неопр.) Chris K. Caldwell. Дата обращения: 2 декабря 2008. Архивировано 20 сентября 2012 года.
4. ^[англ.]. History of the Theory of Numbers I: Divisibility and Primality (англ.). — (Dover Publications), 2005. — .
5. K. Ireland, M. Rosen. A Classical Introduction to Modern Number Theory (англ.). — Second. — Springer, 1998. — .
6. Tables of values of pi(x) and of pi2(x)  (неопр.). . Дата обращения: 14 сентября 2008. Архивировано 20 сентября 2012 года.
7. 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 (2001). "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. ^[англ.]; Gohl, Gunnar. Some calculations related to Riemann's prime number formula (англ.) // ^[англ.] : journal. — American Mathematical Society, 1970. — Vol. 24, no. 112. — P. 969—983. — ISSN 0025-5718. — doi:10.2307/2004630. — JSTOR 2004630.
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. ^[англ.]; Schoenfeld, Lowell. Approximate formulas for some functions of prime numbers (англ.) // Illinois J. Math. : journal. — 1962. — Vol. 6. — P. 64—94. — ISSN 0019-2082. 28 февраля 2019 года.
17. Lowell Schoenfeld. Sharper bounds for the Chebyshev functions θ(x) and ψ(x). II (англ.) // ^[англ.] : journal. — American Mathematical Society, 1976. — Vol. 30, no. 134. — P. 337—360. — ISSN 0025-5718. — doi:10.2307/2005976. — JSTOR 2005976.

Литература

• К. Прахар. Распределение простых чисел. — Мир, 1967.
• В. И. Зенкин. Распределение простых чисел. Элементарные методы. Калининград, 2008.

Ссылки

• Chris Caldwell, The Nth Prime Page at The .