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

У математиці функція розподілу простих чисел, або пі-функція $\pi (x)$, — це функція, що дорівнює числу простих чисел, менших або рівних дійсному числу x. Позначається $\pi (x)$ (це ніяк не пов'язано з числом пі).

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

Історія

Великий інтерес у теорії чисел викликає швидкість зростання пі-функції. Наприкінці XVIII століття Гаусс і Лежандр висунули припущення, що пі-функція оцінюється як

${\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 не дуже велике, $\operatorname {li} (x)$ перевищує $\pi (x)$, проте різниця $\pi (x)-\operatorname {li} (x)$ змінює свій знак нескінченне число разів, найменше натуральне число, для якого відбувається зміна знака, називається числом Ск'юза.

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

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

У таблиці показано зростання функцій $\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 %
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)-\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_{i}p_{j}}}\right\rfloor -\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_{j}p_{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 {m}{p}}\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.

Китайський математик Hwang Cheng використав такі тотожності:

$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)={\frac {1}{2}}{\bigg (}\sum _{p^{n}<x}{\frac {1}{n}}\ +\sum _{p^{n}\leq x}{\frac {1}{n}}{\bigg )}$

де p просте.

Також можна записати

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

де $\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).$

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

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

Існує такий вираз для $\psi$ -функції Чебишова:

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

де

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

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

Для $\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$.

Отже, формула обернення Мебіуса дає нам

$\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-функцією також на честь Рімана. Останній ряд у ній відомий як ряд Грама і збігається для всіх $x>0$.

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

$\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)$ доступні тут.

Нерівності

Тут виписано деякі нерівності для $\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-3/2\cdot n<p_{n}<n\ln n+n\ln \ln n,\ n\geqslant 6.$

Ліва нерівність істинна при $n\geqslant 2$, а права — при $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).$

Зокрема,

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

Див. також

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

Література

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

Посилання

• Chris Caldwell, The Nth Prime Page на сайті Prime Pages.