В математике
функция распределения простых чисел или
пи-функция π(x) — это функция, равная числу простых
чисел, меньших либо равных действительному числу
x. Она
обозначается
π(x) (это никак не связано с числом пи).
История
Большой интерес в теории чисел представляет скорость роста пи-функции. В
конце 18-го столетия Гауссом и Лежандром было выдвинуто предположение,
что пи-функция оценивается как
xlnx
в смысле, что
limx→+∞π(x)x/lnx=1.
Это утверждение — теорема о распределении простых чисел. Оно
эквивалентно утверждению
limx→+∞π(x)li(x)=1
где
li — это интегральный логарифм. Теорема о простых
числах впервые была доказана в 1896 Жаком Адамаром и независимо
Валле-Пуссеном, используя дзета-функцию Римана введенную Риманом в 1859.
Точнее рост
π(x) сейчас описывается как
π(x)=li(x)+O(xe−lnx√/15)
где
O обозначает O большое. Для чаще всего используемых значений
x (то есть когда
x не сильно велико)
li(x) больше чем
π(x), однако разность
π(x)−li(x) меняет свой знак бесконечное число раз.
См. также Число Скьюза.
Доказательства теоремы о простых числах, не использующие дзета-функцию
или комплексный анализ были найдены в 1948 году Атле Сельбергом и Паулем
Эрдёшом (большей частью независимо).
Таблицы для пи-функции, x
/ ln \emphx и
li(
x)
В следующей таблице показан рост функций
π(x),xlnx,li(x) по степеням 10.
: \{ !
x ! π(
x) ! π(
x) −
x / ln
x ! li(
x) − π(
x) !
x / π(
x)
- 10 4 −0,3 2,2
2,500 - 10
2
25 3,3 5,1 4,000 -
10
3 168 23 10
5,952 - 10
4
1 229 143 17 8,137 -
10
5 9 592 906
38 10,425 -
10
6 78 498 6 116 130
12,740 - 10
7
664 579 44 158 339 15,047
- 10
8 5 761 455
332 774 754 17,357 -
10
9 50 847 534
2 592 592 1 701 19,667 -
10
10 455 052 511 20 758 029
3 104 21,975 -
10
11 4 118 054 813 169 923 159
11 588 24,283 -
10
12 37 607 912 018
1 416 705 193 38 263 26,590 -
10
13 346 065 536 839
11 992 858 452 108 971 28,896 -
10
14 3 204 941 750 802
102 838 308 636 314 890 31,202
- 10
15
29 844 570 422 669 891 604 962 452 1 052 619
33,507 - 10
16
279 238 341 033 925 7 804 289 844 393
3 214 632 35,812 -
10
17 2 623 557 157 654 233
68 883 734 693 281 7 956 589 38,116 -
10
18 24 739 954 287 740 860
612 483 070 893 536 21 949 555 40,420
- 10
19
234 057 667 276 344 607 5 481 624 169 369 960
99 877 775 42,725 -
10
20 2 220 819 602 560 918 840
49 347 193 044 659 701 222 744 644 45,028
- 10
21
21 127 269 486 018 731 928 446 579 871 578 168 707
597 394 254 47,332 -
10
22 201 467 286 689 315 906 290
4 060 704 006 019 620 994 1 932 355 208 49,636
- 10
23
1 925 320 391 606 803 968 923 37 083 513 766 578 631 309
7 250 186 216 51,939 -
10
24 18 435 599 767 349 200 867 866
339 996 354 713 708 049 069 17 146 907 278
54,243 \}
В 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,n−1)−Φ([mpn],n−1)
Возьмем натуральное m, если n=π(m−−√3) и если
μ=π(m−−√)−n, то
π(m)=Φ(m,n)+n(μ+1)+μ2−μ2−1−∑μk=1π(mpn+k)
Используя этот подход, Мейссель вычислил π(x) для
x=5⋅105;106;107;108.
В 1959 году Деррик Генри Лемер расширил и упростил метод Мейсселя.
Определим, для действительного m и для натуральных n,k величину
Pk(m,n) как число чисел, не превосходящих m имеющих ровно
k простых множителей, причем все они превосходят pn. Кроме
того, положим P0(m,n)=1. Тогда
Φ(m,n)=∑+∞k=0Pk(m,n)
где сумма явно всегда имеет конечное число ненулевых слагаемых. Пусть
y — целое, такое, что m−−√3⩽y⩽m−−√, и
положим n=π(y). Тогда P1(m,n)=π(m)−n и Pk(m,n)=0 при
k⩾3. Следовательно
π(m)=Φ(m,n)+n−1−P2(m,n)
Вычисление P2(m,n) может быть получено следующим способом:
$P_2(m,n)=\sum_{y
С другой стороны, вычисление Φ(m,n) может быть выполнено с помощью
следующих правил:
-
Φ(m,0)=⌊m⌋
-
Φ(m,b)=Φ(m,b−1)−Φ(mpb,b−1)
Используя этот метод и IBM 701, Лемер смог вычислить
π(1010).
Дальнейшие усовершенствования этого метода были сделаны Lagarias,
Miller, Odlyzko, Deleglise и Rivat.
Китайский математик Hwang Cheng использовал следующие тождества:
e(a−1)Θf(x)=f(ax),
J(x)=∑∞n=1π(x1/n)n
и, полагая x=et, выполняя преобразование Лапласа обеих частей и
применяя сумму геометрической прогрессии с enΘ, получил
выражение:
12πi∫c+i∞c−i∞g(s)tsds=π(t)
lnζ(s)s=(1−eΘ(s))−1g(s)
Θ(s)=sdds
Другие функции, подсчитывающие простые
числа
Другие функции, подсчитывающие простые числа, также используются,
поскольку с ними удобнее работать. Одна из них — функция Римана, часто
обозначаемая как Π0(x) или J0(x). Она испытывает прыжок на
1/n для степеней простых pn, причем в точке прыжка x её
значение равно полусумме значений на обеих сторонах от x. Эти
дополнительные детали нужны для того, чтобы она могла быть определена
обратным преобразованием Меллина. Формально, мы определим Π0(x) как
Π0(x)=12(∑pn<x1n +∑pn≤x1n)
где p простое.
Мы также можем записать
Π0(x)=∑n=2xΛ(n)lnn−12Λ(x)lnx=∑∞n=11nπ0(x√n)
где Λ(n) — функция Мангольдта и
π0(x)=limε→0π(x−ε)+π(x+ε)2.
Формула обращения Мёбиуса дает
π0(x)=∑∞n=1μ(n)nΠ0(x√n)
Используя известное соотношение между логарифмом дзета-функции Римана и
функцией Мангольдта Λ, и используя формулу Перрона мы получим
lnζ(s)=s∫∞0Π0(x)x−s−1dx
Функция Римана имеет производящую функцию
\{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
Функции Чебышёва — это функции, подсчитывающие степени простых чисел
pn с весом lnp:
θ(x)=∑p⩽xlnp
ψ(x)=∑pn⩽xlnp=∑∞n=1θ(x√n)=∑n⩽xΛ(n).
Формулы для функций, подсчитывающих простые
числа
Формулы для функций, подсчитывающих простые числа, бывают двух видов:
арифметические формулы и аналитические формулы. Аналитические формулы
для таких функций были впервые использованы для доказательства теоремы о
простых числах. Они происходят от работ Римана и Мангольдта и в общем
известны как явные формулы.
Существует следующее выражение для ψ-функции Чебышёва:
ψ0(x)=x−∑ρxρρ−ln2π−12ln(1−x−2)
где
ψ0(x)=limε→0ψ(x−ε)+ψ(x+ε)2.
Здесь ρ пробегает нули дзета-функции в критической полосе, где
действительная часть ρ лежит между нулем и единицей. Формула верна
для всех x>1. Ряд по корням сходится условно, и может быть взят в
порядке абсолютного значения возрастания мнимой части корней. Заметим,
что аналогичная сумма по тривиальным корням дает последнее слагаемое в
формуле.
Для Π0(x) мы имеем следующую сложную формулу
Π0(x)=li(x)−∑ρli(xρ)−ln2+∫∞xdtt(t2−1)lnt.
Опять же, формула верна для всех x>1, где ρ — нетривиальные
нули зета-функции, упорядоченные по их абсолютному значению, и, снова,
последний интеграл берется со знаком «минус» и является такой же суммой,
но по тривиальным нулям. Выражение li(xρ) во
втором члене может быть рассмотренно как Ei(ρlnx),
где Ei — это аналитическое продолжение интегральной
показательной функции на комплексную плоскость с ветвью, вырезанной
вдоль прямой x<0.
Таким образом, формула обращения Мёбиуса дает нам
π0(x)=R(x)−∑ρR(xρ)−1lnx+1πarctgπlnx
верное для x>1, где
R(x)=∑∞n=1μ(n)nli(x1/n)=1+∑∞k=1(lnx)kk!kζ(k+1)
называется R-функцией также в честь Римана. Последний ряд в ней известен
как ряд Грама и сходится для всех x>0.
Сумма по нетривиальным нулям дзета-функции в формуле для π0(x)
описывает флуктуации π0(x), в то время как остальные слагаемые дают
гладкую часть пи-функции, поэтому мы можем использовать
R(x)−1lnx+1πarctgπlnx
как
наилучшее
приближение для π(x) для x>1.
Амплитуда «шумной» части эвристически оценивается как x√/lnx,
поэтому флуктуации в распределении простых могут быть явно представлены
Δ-функцией:
Δ(x)=(π0(x)−R(x)+1lnx−1πarctgπlnx)lnxx√.
Обширные таблицы значений Δ(x) доступны здесь.
Неравенства
Здесь выписаны некоторые неравенства для π(x).
xlnx<π(x)<1,25506⋅xlnxx⩾17.
Левое неравенство выполняется при x⩾17, а правое — при
x>1.
Неравенства для n-го простого числа pn:
$n\ln n+n\ln\ln n -n
Левое неравенство верно при n⩾1, а правое — при
n⩾6.
Имеет место следующая асимптотика для n-го простого числа pn:
pn=nlnn(1+lnlnn−1lnn+lnlnn−2ln2n+−1/2ln2lnn+3lnlnn−11/2ln3n+O(ln3lnnln4n))
Гипотеза
Римана
Гипотеза Римана эквивалентна более точной границе ошибки приближения
π(x) интегральным логарифмом, а отсюда и более регулярному
распределению простых чисел
π(x)=li(x)+O(x√lnx).
В частности,
|π(x)−li(x)|<18πx√lnx,x⩾2657.