Loading [MathJax]/jax/element/mml/optable/SuppMathOperators.js

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

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

История


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

xlnx
 в смысле, что

limx+π(x)x/lnx=1.
 Это утверждение — теорема о распределении простых чисел. Оноэквивалентно утверждению

limx+π(x)li(x)=1
 где li — это интегральный логарифм. Теорема о простыхчислах впервые была доказана в 1896 Жаком Адамаром и независимоВалле-Пуссеном, используя дзета-функцию Римана введенную Риманом в 1859.
 Точнее рост π(x) сейчас описывается как

π(x)=li(x)+O(xelnx/15)
 где O обозначает O большое. Для чаще всего используемых значенийx (то есть когда x не сильно велико)li(x) больше чем π(x), однако разностьπ(x)li(x) меняет свой знак бесконечное число раз.См. также Число Скьюза.
 Доказательства теоремы о простых числах, не использующие дзета-функциюили комплексный анализ были найдены в 1948 году Атле Сельбергом и ПаулемЭрдёшом (большей частью независимо).

Таблицы для пи-функции, x

/ ln \emphx иli(x)
 В следующей таблице показан рост функцийπ(x),xlnx,li(x) по степеням 10.
 : \{\textbar ! x ! π(x) ! π(x) − x / lnx ! li(x) − π(x) ! x / π(x)\textbar- \textbar 10 \textbar 4 \textbar −0,3 \textbar 2,2\textbar 2,500 \textbar- \textbar 10\textsuperscript2 \textbar25 \textbar 3,3 \textbar 5,1 \textbar 4,000 \textbar- \textbar10\textsuperscript3 \textbar 168 \textbar 23 \textbar 10\textbar 5,952 \textbar- \textbar 10\textsuperscript4 \textbar1 229 \textbar 143 \textbar 17 \textbar 8,137 \textbar-\textbar 10\textsuperscript5 \textbar 9 592 \textbar 906\textbar 38 \textbar 10,425 \textbar- \textbar10\textsuperscript6 \textbar 78 498 \textbar 6 116 \textbar 130\textbar 12,740 \textbar- \textbar 10\textsuperscript7\textbar 664 579 \textbar 44 158 \textbar 339 \textbar 15,047\textbar- \textbar 10\textsuperscript8 \textbar 5 761 455\textbar 332 774 \textbar 754 \textbar 17,357 \textbar-\textbar 10\textsuperscript9 \textbar 50 847 534 \textbar2 592 592 \textbar 1 701 \textbar 19,667 \textbar- \textbar10\textsuperscript10 \textbar 455 052 511 \textbar 20 758 029\textbar 3 104 \textbar 21,975 \textbar- \textbar10\textsuperscript11 \textbar 4 118 054 813 \textbar 169 923 159\textbar 11 588 \textbar 24,283 \textbar- \textbar10\textsuperscript12 \textbar 37 607 912 018 \textbar1 416 705 193 \textbar 38 263 \textbar 26,590 \textbar- \textbar10\textsuperscript13 \textbar 346 065 536 839 \textbar11 992 858 452 \textbar 108 971 \textbar 28,896 \textbar-\textbar 10\textsuperscript14 \textbar 3 204 941 750 802\textbar 102 838 308 636 \textbar 314 890 \textbar 31,202\textbar- \textbar 10\textsuperscript15 \textbar29 844 570 422 669 \textbar 891 604 962 452 \textbar 1 052 619\textbar 33,507 \textbar- \textbar 10\textsuperscript16\textbar 279 238 341 033 925 \textbar 7 804 289 844 393 \textbar3 214 632 \textbar 35,812 \textbar- \textbar10\textsuperscript17 \textbar 2 623 557 157 654 233 \textbar68 883 734 693 281 \textbar 7 956 589 \textbar 38,116 \textbar-\textbar 10\textsuperscript18 \textbar 24 739 954 287 740 860\textbar 612 483 070 893 536 \textbar 21 949 555 \textbar 40,420\textbar- \textbar 10\textsuperscript19 \textbar234 057 667 276 344 607 \textbar 5 481 624 169 369 960 \textbar99 877 775 \textbar 42,725 \textbar- \textbar10\textsuperscript20 \textbar 2 220 819 602 560 918 840 \textbar49 347 193 044 659 701 \textbar 222 744 644 \textbar 45,028\textbar- \textbar 10\textsuperscript21 \textbar21 127 269 486 018 731 928 \textbar 446 579 871 578 168 707 \textbar597 394 254 \textbar 47,332 \textbar- \textbar10\textsuperscript22 \textbar 201 467 286 689 315 906 290 \textbar4 060 704 006 019 620 994 \textbar 1 932 355 208 \textbar 49,636\textbar- \textbar 10\textsuperscript23 \textbar1 925 320 391 606 803 968 923 \textbar 37 083 513 766 578 631 309\textbar 7 250 186 216 \textbar 51,939 \textbar- \textbar10\textsuperscript24 \textbar 18 435 599 767 349 200 867 866\textbar 339 996 354 713 708 049 069 \textbar 17 146 907 278\textbar 54,243 \textbar\}
 В OEIS первая колонка значений π(x) — это последовательность ,π(x)xlnx+0,5 — этопоследовательность , аli(x)+0,5π(x) — этопоследовательность .

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


 Простой способ найти π(x), если x не очень велико, — этоиспользование решета Эратосфена выдающего простые, не превосходящие xи подсчитать их.
 Более продуманный способ вычисления π(x) был дан Лежандром: дан x,если p1,p2,,pk — различные простые числа, то число целыхчисел, не превосходящих x и не делящихся на все pi равно

 $\lfloor x\rfloor - \sum_{i}\left\lfloor\frac{x}{p_i}\right\rfloor + \sum_{i (где обозначает целую часть). Следовательно,полученное число равно

π(x)π(x)+1
 если числа p1,p2,,pk — это все простые числа, непревосходящие x.
 В 1870—1885 годах в серии статей Эрнст Мейссель описал (и использовал)практический комбинаторный способ вычисления π(x). Пустьp1,p2,,pn — первые n простых, обозначим Φ(m,n) числонатуральных чисел, не превосходящих m, которые не делятся ни наодноpi. Тогда

Φ(m,n)=Φ(m,n1)Φ([mpn],n1)
 Возьмем натуральное m, если n=π(3m) и еслиμ=π(m)n, то

π(m)=Φ(m,n)+n(μ+1)+μ2μ21μk=1π(mpn+k)
 Используя этот подход, Мейссель вычислил π(x) дляx=5105;106;107;108.
 В 1959 году Деррик Генри Лемер расширил и упростил метод Мейсселя.Определим, для действительного m и для натуральных n,k величинуPk(m,n) как число чисел, не превосходящих m имеющих ровноk простых множителей, причем все они превосходят pn. Крометого, положим P0(m,n)=1. Тогда

Φ(m,n)=+k=0Pk(m,n)
 где сумма явно всегда имеет конечное число ненулевых слагаемых. Пустьy — целое, такое, что 3m, иположим 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 С другой стороны, вычисление \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) = \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})
 где \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 - \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.
 Таким образом, формула обращения Мёбиуса дает нам

\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 -n Левое неравенство верно при 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).
 В частности,

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