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

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

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

История

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

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

в смысле, что

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

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

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

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

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

$\pi (x)=\mathrm{li}(x)+O\left(x{e}^{-\sqrt{\ln x}/15}\right)$

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

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

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

В следующей таблице показан рост функций $\pi (x),\frac{x}{\ln x},\mathrm{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 %
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 первая колонка значений $\pi (x)$ — это последовательность Шаблон:OEIS2C, $\pi (x)-\lfloor \frac{x}{\ln x}+0,5\rfloor$ — это последовательность Шаблон:OEIS2C, а $\lfloor \mathrm{li}(x)+0,5\rfloor -\pi (x)$ — это последовательность Шаблон:OEIS2C.

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

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

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

$\lfloor x\rfloor -\sum _i\lfloor \frac{x}{p_i}\rfloor +\sum _{i<j}\lfloor \frac{x}{p_i{p}_j}\rfloor -\sum _{i<j<k}\lfloor \frac{x}{p_i{p}_j{p}_k}\rfloor +\cdots$

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

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

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

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

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

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

$\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)$

Используя этот подход, Майссель вычислил $\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$. Тогда

$\mathrm{\Phi }(m,n)=\sum _{k=0}^{+\mathrm{\infty }}{P}_k(m,n)$

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

$\pi (m)=\mathrm{\Phi }(m,n)+n-1-P_2(m,n)$

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

$P_2(m,n)=\sum _{y<p⩽\sqrt{m}}(\pi \left(\frac{m}{p}\right)-\pi (p)+1)$

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

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

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

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

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

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

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

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

$\frac{1}{2\pi i}\underset{c-i\mathrm{\infty }}{\overset{c+i\mathrm{\infty }}{\int }}g(s)t^{s}ds=\pi (t)$

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

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

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

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

${\mathrm{\Pi }}_0(x)=\frac{1}{2}(\sum _{p^n<x}\frac{1}{n}+\sum _{p^n\le x}\frac{1}{n})$

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

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

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

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

${\pi }_0(x)=\underset{\epsilon \to 0}{\lim }\frac{\pi (x-\epsilon )+\pi (x+\epsilon )}{2}.$

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

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

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

$\ln \zeta (s)=s\underset{0}{\overset{\mathrm{\infty }}{\int }}{\mathrm{\Pi }}_0(x)x^{-s-1}dx$

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

$\sum _{n=1}^{\mathrm{\infty }}{\mathrm{\Pi }}_0(n)x^n=\sum _{a=2}^{\mathrm{\infty }}\frac{x^a}{1-x}-\frac{1}{2}\sum _{a=2}^{\mathrm{\infty }}\sum _{b=2}^{\mathrm{\infty }}\frac{x^{ab}}{1-x}+\frac{1}{3}\sum _{a=2}^{\mathrm{\infty }}\sum _{b=2}^{\mathrm{\infty }}\sum _{c=2}^{\mathrm{\infty }}\frac{x^{abc}}{1-x}-\frac{1}{4}\sum _{a=2}^{\mathrm{\infty }}\sum _{b=2}^{\mathrm{\infty }}\sum _{c=2}^{\mathrm{\infty }}\sum _{d=2}^{\mathrm{\infty }}\frac{x^{abcd}}{1-x}+\cdots$

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

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

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

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

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

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

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

где

${\psi }_0(x)=\underset{\epsilon \to 0}{\lim }\frac{\psi (x-\epsilon )+\psi (x+\epsilon )}{2}.$

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

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

${\mathrm{\Pi }}_0(x)=\mathrm{li}(x)-\sum _{\rho }\mathrm{li}(x^{\rho })-\ln 2+\underset{x}{\overset{\mathrm{\infty }}{\int }}\frac{dt}{t(t^2-1)\ln t}.$

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

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

${\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$, где

$\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$.

Сумма по нетривиальным нулям дзета-функции в формуле для ${\pi }_0(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}$

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

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

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

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

Неравенства

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

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

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

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

$n\ln n+n\ln \ln n-3/2\cdot n<p_n<n\ln n+n\ln \ln n,n⩾6.$

Левое неравенство верно при $n⩾2$, а правое — при $n⩾6$.

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

$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))$

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

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

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

В частности,

$|\pi (x)-\mathrm{li}(x)|<\frac{1}{8\pi }\sqrt{x}\ln x,x⩾2657.$

См. также

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

Литература

• Шаблон:Книга
• В. И. Зенкин. Распределение простых чисел. Элементарные методы. Калининград, 2008.

Ссылки

• Chris Caldwell, The Nth Prime Page at The Prime Pages.