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

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

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

История

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

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

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

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

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

x	π(x)	π(x) − x / ln x	li(x) − π(x)	x / π(x)
10	4	−0.3	2.2	2.500
102	25	3.3	5.1	4.000
103	168	23	10	5.952
104	1,229	143	17	8.137
105	9,592	906	38	10.425
106	78,498	6,116	130	12.740
107	664,579	44,158	339	15.047
108	5,761,455	332,774	754	17.357
109	50,847,534	2,592,592	1,701	19.667
1010	455,052,511	20,758,029	3,104	21.975
1011	4,118,054,813	169,923,159	11,588	24.283
1012	37,607,912,018	1,416,705,193	38,263	26.590
1013	346,065,536,839	11,992,858,452	108,971	28.896
1014	3,204,941,750,802	102,838,308,636	314,890	31.202
1015	29,844,570,422,669	891,604,962,452	1,052,619	33.507
1016	279,238,341,033,925	7,804,289,844,393	3,214,632	35.812
1017	2,623,557,157,654,233	68,883,734,693,281	7,956,589	38.116
1018	24,739,954,287,740,860	612,483,070,893,536	21,949,555	40.420
1019	234,057,667,276,344,607	5,481,624,169,369,960	99,877,775	42.725
1020	2,220,819,602,560,918,840	49,347,193,044,659,701	222,744,644	45.028
1021	21,127,269,486,018,731,928	446,579,871,578,168,707	597,394,254	47.332
1022	201,467,286,689,315,906,290	4,060,704,006,019,620,994	1,932,355,208	49.636
1023	1,925,320,391,606,803,968,923	37,083,513,766,578,631,309	7,250,186,216	51.939
1024	18,435,599,767,349,200,867,866	339,996,354,713,708,049,069	17,146,907,278	54.243

В OEIS первая колонка значений $\pi(x)~$ — это последовательность A006880, $\pi(x)-\frac{x}{\ln x}~$ — это последовательность A057835, а $\operatorname{li}(x)-\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_ip_j}\right\rfloor - \sum_{i<j<k}\left\lfloor\frac{x}{p_ip_jp_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 mp\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.^[9]

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

$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) = \frac12 \bigg(\sum_{p^n < x} \frac1n\ + \sum_{p^n \le x} \frac1n\bigg)$

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

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

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

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

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

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

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

$\psi_0(x) = x - \sum_\rho \frac{x^\rho}{\rho} - \ln 2\pi - \frac12 \ln(1-x^{-2})$

где

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

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

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

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

$\pi_{0}(x)=\operatorname{R}(x)-\sum_{\rho}\operatorname{R}(x^{\rho})-\frac{1}{\ln x}+\frac{1}{\pi}\arctan \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-функцией также в честь Римана.^[13] Последний ряд в ней известен как ряд Грэма^[14] и сходится для всех $x>0$.

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

$\operatorname{R}(x) - \frac{1}{\ln x} + \frac{1}{\pi}\arctan\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}\arctan\frac{\pi}{\ln x} \right) \frac{\ln x}{\sqrt x}.$

Общирные таблицы значений $\Delta(x)~$ доступны здесь.^[7]

Неравенства

Здесь выписаны некоторые неравенства для $\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 -n<p_n<n\ln n +n\ln\ln n, \ n\geqslant 6~$

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

В частности,^[16]

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

См. также

• Теорема о распределении простых чисел
• Постулат Бертрана

Примечания

1. ↑ Bach Eric Section 8.8 // Algorithmic Number Theory. — MIT Press, 1996. — Vol. 1. — P. 234. — ISBN 0-262-02405-5
2. ↑ Weisstein, Eric W. Prime Counting Function (англ.) на сайте Wolfram MathWorld.
3. ↑ ^{1 2} How many primes are there?. Chris K. Caldwell. Архивировано из первоисточника 20 сентября 2012. Проверено 2 декабря 2008.
4. ↑ Dickson Leonard Eugene History of the Theory of Numbers I: Divisibility and Primality. — Dover Publications, 2005. — ISBN 0-486-44232-2
5. ↑ K. Ireland, M. Rosen A Classical Introduction to Modern Number Theory. — Second. — Springer, 1998. — ISBN 0-387-97329-X
6. ↑ Tables of values of pi(x) and of pi2(x). Tomas Oliveira e Silva. Архивировано из первоисточника 20 сентября 2012. Проверено 14 сентября 2008.
7. ↑ ^{1 2} Values of π(x) and Δ(x) for various x's. Andrey V. Kulsha. Архивировано из первоисточника 20 сентября 2012. Проверено 14 сентября 2008.
8. ↑ A table of values of pi(x). Xavier Gourdon, Pascal Sebah, Patrick Demichel. Архивировано из первоисточника 20 сентября 2012. Проверено 14 сентября 2008.
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. Архивировано из первоисточника 20 сентября 2012. Проверено 14 сентября 2008.
10. ↑ Hwang H., Cheng. 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. ↑ (1970) «Some calculations related to Riemann's prime number formula». Mathematics of Computation (American Mathematical Society) 24 (112): 969–983. DOI:10.2307/2004630. ISSN 0025-5718.
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. Архивировано из первоисточника 20 сентября 2012. Проверено 14 сентября 2008.
16. ↑ Lowell Schoenfeld (1976). «Sharper bounds for the Chebyshev functions θ(x) and ψ(x). II». Mathematics of Computation (American Mathematical Society) 30 (134): 337–360. DOI:10.2307/2005976. ISSN 0025-5718.

Литература

• К. Прахар Распределение простых чисел. — Мир, 1967.

Ссылки

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