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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

История[править | править код]

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

в смысле, что

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

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

Точнее рост сейчас описывается как

где обозначает O большое. Для чаще всего используемых значений x (то есть когда x не сильно велико) больше чем , однако разность меняет свой знак бесконечное число раз. См. также Число Скьюза.

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

Таблицы для пи-функции, x / ln x и li(x)[править | править код]

В следующей таблице показан рост функций по степеням 10[3][6][7][8].

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 первая колонка значений  — это последовательность A006880,  — это последовательность A057835, а  — это последовательность A057752.

Алгоритмы вычисления пи-функции[править | править код]

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

Более продуманный способ вычисления был дан Лежандром: дан , если  — различные простые числа, то число целых чисел, не превосходящих и не делящихся на все равно

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

если числа  — это все простые числа, не превосходящие .

В 1870—1885 годах в серии статей Эрнст Мейссель описал (и использовал) практический комбинаторный способ вычисления . Пусть  — первые простых, обозначим число натуральных чисел, не превосходящих , которые не делятся ни на одно. Тогда

Возьмем натуральное , если и если , то

Используя этот подход, Мейссель вычислил для .

В 1959 году Деррик Генри Лемер расширил и упростил метод Мейсселя. Определим, для действительного и для натуральных величину как число чисел, не превосходящих m имеющих ровно k простых множителей, причем все они превосходят . Кроме того, положим . Тогда

где сумма явно всегда имеет конечное число ненулевых слагаемых. Пусть  — целое, такое, что , и положим . Тогда и при . Следовательно

Вычисление может быть получено следующим способом:

С другой стороны, вычисление может быть выполнено с помощью следующих правил:

Используя этот метод и IBM 701, Лемер смог вычислить .

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

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

и, полагая , выполняя преобразование Лапласа обеих частей и применяя сумму геометрической прогрессии с , получил выражение:

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

Другие функции, подсчитывающие простые числа, также используются, поскольку с ними удобнее работать. Одна из них — функция Римана, часто обозначаемая как или . Она испытывает прыжок на 1/n для степеней простых , причем в точке прыжка её значение равно полусумме значений на обеих сторонах от . Эти дополнительные детали нужны для того, чтобы она могла быть определена обратным преобразованием Меллина. Формально, мы определим как

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

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

где  — функция Мангольдта и

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

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

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

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

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

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

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

где

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

Для мы имеем следующую сложную формулу

Опять же, формула верна для всех , где  — нетривиальные нули зета-функции, упорядоченные по их абсолютному значению, и, снова, последний интеграл берется со знаком «минус» и является такой же суммой, но по тривиальным нулям. Выражение во втором члене может быть рассмотренно как , где  — это аналитическое продолжение интегральной показательной функции на комплексную плоскость с ветвью, вырезанной вдоль прямой .

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

верное для , где

называется R-функцией также в честь Римана.[13] Последний ряд в ней известен как ряд Грама[14] и сходится для всех .

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

как наилучшее приближение для для .

Амплитуда «шумной» части эвристически оценивается как , поэтому флуктуации в распределении простых могут быть явно представлены -функцией:

Обширные таблицы значений доступны здесь.[7]

Неравенства[править | править код]

Здесь выписаны некоторые неравенства для .

Левое неравенство выполняется при , а правое — при

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

Левое неравенство верно при , а правое — при .

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

Гипотеза Римана[править | править код]

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

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

См. также[править | править код]

Примечания[править | править код]

  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. Проверено 2 декабря 2008. Архивировано 20 сентября 2012 года.
  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. Проверено 14 сентября 2008. Архивировано 20 сентября 2012 года.
  7. 1 2 Values of π(x) and Δ(x) for various x's. Andrey V. Kulsha. Проверено 14 сентября 2008. Архивировано 20 сентября 2012 года.
  8. A table of values of pi(x). Xavier Gourdon, Pascal Sebah, Patrick Demichel. Проверено 14 сентября 2008. Архивировано 20 сентября 2012 года.
  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. Проверено 14 сентября 2008. Архивировано 20 сентября 2012 года.
  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. Проверено 14 сентября 2008. Архивировано 20 сентября 2012 года.
  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.

Литература[править | править код]

Ссылки[править | править код]