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

У математиці функція розподілу простих чисел, або пі-функція $\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)$ — це послідовність A006880, $\pi (x)-\lfloor \frac{x}{\ln x}+0,5\rfloor$ — послідовність A057835, а $\lfloor \mathrm{li}(x)+0,5\rfloor -\pi (x)$ — послідовність A057752.

Алгоритми обчислення пі-функції

Простий спосіб знайти $\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 на сайті Шаблон:Нп.