В математике функция распределения простых чисел, или пи-функция π ( x ) {displaystyle pi (x)} , — это функция, равная числу простых чисел, меньших либо равных действительному числу x. Она обозначается π ( x ) {displaystyle pi (x)} (это никак не связано с числом пи).
Большой интерес в теории чисел представляет скорость роста пи-функции. В конце XVIII столетия Гауссом и Лежандром было выдвинуто предположение, что пи-функция оценивается как
x ln x {displaystyle {frac {x}{ln x}}}в смысле, что
lim x → + ∞ π ( x ) x / ln x = 1. {displaystyle lim limits _{x o +infty }{frac {pi (x)}{x/ln x}}=1.}Это утверждение — теорема о распределении простых чисел. Оно эквивалентно утверждению
lim x → + ∞ π ( x ) li ( x ) = 1 {displaystyle lim limits _{x o +infty }{frac {pi (x)}{operatorname {li} (x)}}=1}где li {displaystyle operatorname {li} } — это интегральный логарифм. Теорема о простых числах впервые была доказана в 1896 Жаком Адамаром и независимо Валле-Пуссеном, используя дзета-функцию Римана введенную Риманом в 1859.
Точнее рост π ( x ) {displaystyle pi (x)} сейчас описывается как
π ( x ) = li ( x ) + O ( x e − ln x / 15 ) {displaystyle pi (x)=operatorname {li} (x)+O{igl (}xe^{-{sqrt {ln x}}/15}{igr )}}где O {displaystyle O} обозначает O большое. Для чаще всего используемых значений x (то есть когда x не сильно велико) li ( x ) {displaystyle operatorname {li} (x)} больше, чем π ( x ) {displaystyle pi (x)} , однако разность π ( x ) − li ( x ) {displaystyle pi (x)-operatorname {li} (x)} меняет свой знак бесконечное число раз. См. также Число Скьюза.
Доказательства теоремы о простых числах, не использующие дзета-функцию или комплексный анализ, были найдены в 1948 году Атле Сельбергом и Паулем Эрдёшом (большей частью независимо).
В следующей таблице показан рост функций π ( x ) , x ln x , li ( x ) {displaystyle pi (x),{frac {x}{ln x}},operatorname {li} (x)} по степеням 10.
В OEIS первая колонка значений π ( x ) {displaystyle pi (x)} — это последовательность A006880, π ( x ) − ⌊ x ln x + 0 , 5 ⌋ {displaystyle pi (x)-leftlfloor {frac {x}{ln x}}+0{,}5 ight floor } — это последовательность A057835, а ⌊ li ( x ) + 0 , 5 ⌋ − π ( x ) {displaystyle lfloor operatorname {li} (x)+0{,}5 floor -pi (x)} — это последовательность A057752.
Простой способ найти π ( x ) {displaystyle pi (x)} , если x {displaystyle x} не очень велико, — это использование решета Эратосфена выдающего простые, не превосходящие x {displaystyle x} и подсчитать их.
Более продуманный способ вычисления π ( x ) {displaystyle pi (x)} был дан Лежандром: дан x {displaystyle x} , если p 1 , p 2 , … , p k {displaystyle p_{1},p_{2},ldots ,p_{k}} — различные простые числа, то число целых чисел, не превосходящих x {displaystyle x} и не делящихся на все p i {displaystyle p_{i}} равно
⌊ x ⌋ − ∑ i ⌊ x p i ⌋ + ∑ i < j ⌊ x p i p j ⌋ − ∑ i < j < k ⌊ x p i p j p k ⌋ + ⋯ {displaystyle lfloor x floor -sum _{i}leftlfloor {frac {x}{p_{i}}} ight floor +sum _{i<j}leftlfloor {frac {x}{p_{i}p_{j}}} ight floor -sum _{i<j<k}leftlfloor {frac {x}{p_{i}p_{j}p_{k}}} ight floor +cdots }(где ⌊ ⋯ ⌋ {displaystyle lfloor cdots floor } обозначает целую часть). Следовательно, полученное число равно
π ( x ) − π ( x ) + 1 {displaystyle pi (x)-pi left({sqrt {x}} ight)+1}если числа p 1 , p 2 , … , p k {displaystyle p_{1},p_{2},ldots ,p_{k}} — это все простые числа, не превосходящие x {displaystyle {sqrt {x}}} .
В 1870—1885 годах в серии статей Эрнст Мейссель описал (и использовал) практический комбинаторный способ вычисления π ( x ) {displaystyle pi (x)} . Пусть p 1 , p 2 , … , p n {displaystyle p_{1},p_{2},ldots ,p_{n}} — первые n {displaystyle n} простых, обозначим Φ ( m , n ) {displaystyle Phi (m,n)} число натуральных чисел, не превосходящих m {displaystyle m} , которые не делятся ни на одно p i {displaystyle p_{i}} . Тогда
Φ ( m , n ) = Φ ( m , n − 1 ) − Φ ( [ m p n ] , n − 1 ) {displaystyle Phi (m,n)=Phi (m,n-1)-Phi left(left[{frac {m}{p_{n}}} ight],n-1 ight)}Возьмем натуральное m {displaystyle m} , если n = π ( m 3 ) {displaystyle n=pi left({sqrt[{3}]{m}} ight)} и если μ = π ( m ) − n {displaystyle mu =pi left({sqrt {m}} ight)-n} , то
π ( m ) = Φ ( m , n ) + n ( μ + 1 ) + μ 2 − μ 2 − 1 − ∑ k = 1 μ π ( m p n + k ) {displaystyle 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}}} ight)}Используя этот подход, Мейссель вычислил π ( x ) {displaystyle pi (x)} для x = 5 ⋅ 10 5 ; 10 6 ; 10 7 ; 10 8 {displaystyle x=5cdot 10^{5};10^{6};10^{7};10^{8}} .
В 1959 году Деррик Генри Лемер расширил и упростил метод Мейсселя. Определим, для действительного m {displaystyle m} и для натуральных n , k {displaystyle n,k} величину P k ( m , n ) {displaystyle P_{k}(m,n)} как число чисел, не превосходящих m имеющих ровно k простых множителей, причем все они превосходят p n {displaystyle p_{n}} . Кроме того, положим P 0 ( m , n ) = 1 {displaystyle P_{0}(m,n)=1} . Тогда
Φ ( m , n ) = ∑ k = 0 + ∞ P k ( m , n ) {displaystyle Phi (m,n)=sum _{k=0}^{+infty }P_{k}(m,n)}где сумма явно всегда имеет конечное число ненулевых слагаемых. Пусть y {displaystyle y} — целое, такое, что m 3 ⩽ y ⩽ m {displaystyle {sqrt[{3}]{m}}leqslant yleqslant {sqrt {m}}} , и положим n = π ( y ) {displaystyle n=pi (y)} . Тогда P 1 ( m , n ) = π ( m ) − n {displaystyle P_{1}(m,n)=pi (m)-n} и P k ( m , n ) = 0 {displaystyle P_{k}(m,n)=0} при k ⩾ 3 {displaystyle kgeqslant 3} . Следовательно
π ( m ) = Φ ( m , n ) + n − 1 − P 2 ( m , n ) {displaystyle pi (m)=Phi (m,n)+n-1-P_{2}(m,n)}Вычисление P 2 ( m , n ) {displaystyle P_{2}(m,n)} может быть получено следующим способом:
P 2 ( m , n ) = ∑ y < p ⩽ m ( π ( m p ) − π ( p ) + 1 ) {displaystyle P_{2}(m,n)=sum _{y<pleqslant {sqrt {m}}}left(pi left({frac {m}{p}} ight)-pi (p)+1 ight)}С другой стороны, вычисление Φ ( m , n ) {displaystyle Phi (m,n)} может быть выполнено с помощью следующих правил:
Используя этот метод и IBM 701, Лемер смог вычислить π ( 10 10 ) {displaystyle pi left(10^{10} ight)} .
Дальнейшие усовершенствования этого метода были сделаны Lagarias, Miller, Odlyzko, Deleglise и Rivat.
Китайский математик Hwang Cheng использовал следующие тождества:
e ( a − 1 ) Θ f ( x ) = f ( a x ) , {displaystyle e^{(a-1)Theta }f(x)=f(ax),} J ( x ) = ∑ n = 1 ∞ π ( x 1 / n ) n {displaystyle J(x)=sum _{n=1}^{infty }{frac {pi (x^{1/n})}{n}}}и, полагая x = e t {displaystyle x=e^{t}} , выполняя преобразование Лапласа обеих частей и применяя сумму геометрической прогрессии с e n Θ {displaystyle e^{nTheta }} , получил выражение:
1 2 π i ∫ c − i ∞ c + i ∞ g ( s ) t s d s = π ( t ) {displaystyle {frac {1}{2{pi }i}}int _{c-iinfty }^{c+iinfty }g(s)t^{s},ds=pi (t)} ln ζ ( s ) s = ( 1 − e Θ ( s ) ) − 1 g ( s ) {displaystyle {frac {ln zeta (s)}{s}}=(1-e^{Theta (s)})^{-1}g(s)} Θ ( s ) = s d d s {displaystyle Theta (s)=s{frac {d}{ds}}}Другие функции, подсчитывающие простые числа, также используются, поскольку с ними удобнее работать. Одна из них — функция Римана, часто обозначаемая как Π 0 ( x ) {displaystyle Pi _{0}(x)} или J 0 ( x ) {displaystyle J_{0}(x)} . Она испытывает прыжок на 1/n для степеней простых p n {displaystyle p^{n}} , причем в точке прыжка x {displaystyle x} её значение равно полусумме значений на обеих сторонах от x {displaystyle x} . Эти дополнительные детали нужны для того, чтобы она могла быть определена обратным преобразованием Меллина. Формально, мы определим Π 0 ( x ) {displaystyle Pi _{0}(x)} как
Π 0 ( x ) = 1 2 ( ∑ p n < x 1 n + ∑ p n ≤ x 1 n ) {displaystyle Pi _{0}(x)={frac {1}{2}}{igg (}sum _{p^{n}<x}{frac {1}{n}} +sum _{p^{n}leq x}{frac {1}{n}}{igg )}}где p простое.
Мы также можем записать
Π 0 ( x ) = ∑ n = 2 x Λ ( n ) ln n − 1 2 Λ ( x ) ln x = ∑ n = 1 ∞ 1 n π 0 ( x n ) {displaystyle 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}})}где Λ ( n ) {displaystyle Lambda (n)} — функция Мангольдта и
π 0 ( x ) = lim ε → 0 π ( x − ε ) + π ( x + ε ) 2 . {displaystyle pi _{0}(x)=lim _{varepsilon ightarrow 0}{frac {pi (x-varepsilon )+pi (x+varepsilon )}{2}}.}Формула обращения Мёбиуса дает
π 0 ( x ) = ∑ n = 1 ∞ μ ( n ) n Π 0 ( x n ) {displaystyle pi _{0}(x)=sum _{n=1}^{infty }{frac {mu (n)}{n}}Pi _{0}({sqrt[{n}]{x}})}Используя известное соотношение между логарифмом дзета-функции Римана и функцией Мангольдта Λ {displaystyle Lambda } , и используя формулу Перрона мы получим
ln ζ ( s ) = s ∫ 0 ∞ Π 0 ( x ) x − s − 1 d x {displaystyle ln zeta (s)=sint _{0}^{infty }Pi _{0}(x)x^{-s-1},dx}Функция Римана имеет производящую функцию
∑ n = 1 ∞ Π 0 ( n ) x n = ∑ a = 2 ∞ x a 1 − x − 1 2 ∑ a = 2 ∞ ∑ b = 2 ∞ x a b 1 − x + 1 3 ∑ a = 2 ∞ ∑ b = 2 ∞ ∑ c = 2 ∞ x a b c 1 − x − 1 4 ∑ a = 2 ∞ ∑ b = 2 ∞ ∑ c = 2 ∞ ∑ d = 2 ∞ x a b c d 1 − x + ⋯ {displaystyle 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 {displaystyle p^{n}} с весом ln p {displaystyle ln p} :
θ ( x ) = ∑ p ⩽ x ln p {displaystyle heta (x)=sum _{pleqslant x}ln p} ψ ( x ) = ∑ p n ⩽ x ln p = ∑ n = 1 ∞ θ ( x n ) = ∑ n ⩽ x Λ ( n ) . {displaystyle psi (x)=sum _{p^{n}leqslant x}ln p=sum _{n=1}^{infty } heta ({sqrt[{n}]{x}})=sum _{nleqslant x}Lambda (n).}Формулы для функций, подсчитывающих простые числа, бывают двух видов: арифметические формулы и аналитические формулы. Аналитические формулы для таких функций были впервые использованы для доказательства теоремы о простых числах. Они происходят от работ Римана и Мангольдта и в общем известны как явные формулы.
Существует следующее выражение для ψ {displaystyle psi } -функции Чебышёва:
ψ 0 ( x ) = x − ∑ ρ x ρ ρ − ln 2 π − 1 2 ln ( 1 − x − 2 ) {displaystyle psi _{0}(x)=x-sum _{ ho }{frac {x^{ ho }}{ ho }}-ln 2pi -{frac {1}{2}}ln(1-x^{-2})}где
ψ 0 ( x ) = lim ε → 0 ψ ( x − ε ) + ψ ( x + ε ) 2 . {displaystyle psi _{0}(x)=lim _{varepsilon ightarrow 0}{frac {psi (x-varepsilon )+psi (x+varepsilon )}{2}}.}Здесь ρ {displaystyle ho } пробегает нули дзета-функции в критической полосе, где действительная часть ρ {displaystyle ho } лежит между нулем и единицей. Формула верна для всех x > 1 {displaystyle x>1} . Ряд по корням сходится условно, и может быть взят в порядке абсолютного значения возрастания мнимой части корней. Заметим, что аналогичная сумма по тривиальным корням дает последнее слагаемое в формуле.
Для Π 0 ( x ) {displaystyle scriptstyle Pi _{0}(x)} мы имеем следующую сложную формулу
Π 0 ( x ) = li ( x ) − ∑ ρ li ( x ρ ) − ln 2 + ∫ x ∞ d t t ( t 2 − 1 ) ln t . {displaystyle Pi _{0}(x)=operatorname {li} (x)-sum _{ ho }operatorname {li} (x^{ ho })-ln 2+int _{x}^{infty }{frac {dt}{t(t^{2}-1)ln t}}.}Опять же, формула верна для всех x > 1 {displaystyle x>1} , где ρ {displaystyle ho } — нетривиальные нули зета-функции, упорядоченные по их абсолютному значению, и, снова, последний интеграл берется со знаком «минус» и является такой же суммой, но по тривиальным нулям. Выражение li ( x ρ ) {displaystyle operatorname {li} (x^{ ho })} во втором члене может быть рассмотренно как Ei ( ρ ln x ) {displaystyle operatorname {Ei} ( ho ln x)} , где Ei {displaystyle operatorname {Ei} } — это аналитическое продолжение интегральной показательной функции на комплексную плоскость с ветвью, вырезанной вдоль прямой x < 0 {displaystyle x<0} .
Таким образом, формула обращения Мёбиуса дает нам
π 0 ( x ) = R ( x ) − ∑ ρ R ( x ρ ) − 1 ln x + 1 π a r c t g π ln x {displaystyle pi _{0}(x)=operatorname {R} (x)-sum _{ ho }operatorname {R} (x^{ ho })-{frac {1}{ln x}}+{frac {1}{pi }}mathop {mathrm {arctg} } {frac {pi }{ln x}}}верное для x > 1 {displaystyle x>1} , где
R ( x ) = ∑ n = 1 ∞ μ ( n ) n li ( x 1 / n ) = 1 + ∑ k = 1 ∞ ( ln x ) k k ! k ζ ( k + 1 ) {displaystyle 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!kzeta (k+1)}}}называется R-функцией также в честь Римана. Последний ряд в ней известен как ряд Грама и сходится для всех x > 0 {displaystyle x>0} .
Сумма по нетривиальным нулям дзета-функции в формуле для π 0 ( x ) {displaystyle pi _{0}(x)} описывает флуктуации π 0 ( x ) {displaystyle pi _{0}(x)} , в то время как остальные слагаемые дают гладкую часть пи-функции, поэтому мы можем использовать
R ( x ) − 1 ln x + 1 π a r c t g π ln x {displaystyle operatorname {R} (x)-{frac {1}{ln x}}+{frac {1}{pi }}mathop {mathrm {arctg} } {frac {pi }{ln x}}}как наилучшее приближение для π ( x ) {displaystyle pi (x)} для x > 1 {displaystyle x>1} .
Амплитуда «шумной» части эвристически оценивается как x / ln x {displaystyle {sqrt {x}}/ln x} , поэтому флуктуации в распределении простых могут быть явно представлены Δ {displaystyle Delta } -функцией:
Δ ( x ) = ( π 0 ( x ) − R ( x ) + 1 ln x − 1 π a r c t g π ln x ) ln x x . {displaystyle Delta (x)=left(pi _{0}(x)-operatorname {R} (x)+{frac {1}{ln x}}-{frac {1}{pi }}mathop {mathrm {arctg} } {frac {pi }{ln x}} ight){frac {ln x}{sqrt {x}}}.}Обширные таблицы значений Δ ( x ) {displaystyle Delta (x)} доступны здесь.
Здесь выписаны некоторые неравенства для π ( x ) {displaystyle pi (x)} .
x ln x < π ( x ) < 1,255 06 ⋅ x ln x x ⩾ 17. {displaystyle {frac {x}{ln x}}<pi (x)<1{,}25506cdot {frac {x}{ln x}}qquad xgeqslant 17.}Левое неравенство выполняется при x ⩾ 17 {displaystyle xgeqslant 17} , а правое — при x > 1. {displaystyle x>1.}
Неравенства для n {displaystyle n} -го простого числа p n {displaystyle p_{n}} :
n ln n + n ln ln n − 3 / 2 ⋅ n < p n < n ln n + n ln ln n , n ⩾ 6. {displaystyle nln n+nln ln n-3/2cdot n<p_{n}<nln n+nln ln n, ngeqslant 6.}Левое неравенство верно при n ⩾ 2 {displaystyle ngeqslant 2} , а правое — при n ⩾ 6 {displaystyle ngeqslant 6} .
Имеет место следующая асимптотика для n {displaystyle n} -го простого числа p n {displaystyle p_{n}} :
p n = n ln n ( 1 + ln ln n − 1 ln n + ln ln n − 2 ln 2 n + − 1 / 2 ln 2 ln n + 3 ln ln n − 11 / 2 ln 3 n + O ( ln 3 ln n ln 4 n ) ) {displaystyle p_{n}=nln nleft(1+{frac {ln ln n-1}{ln n}}+{frac {ln ln n-2}{ln ^{2}n}}+{frac {-1/2ln ^{2}ln n+3ln ln n-11/2}{ln ^{3}n}}+Oleft({frac {ln ^{3}ln n}{ln ^{4}n}} ight) ight)}Гипотеза Римана эквивалентна более точной границе ошибки приближения π ( x ) {displaystyle pi (x)} интегральным логарифмом, а отсюда и более регулярному распределению простых чисел
π ( x ) = li ( x ) + O ( x ln x ) . {displaystyle pi (x)=operatorname {li} (x)+O({sqrt {x}}ln x).}В частности,
| π ( x ) − li ( x ) | < 1 8 π x ln x , x ⩾ 2657. {displaystyle |pi (x)-operatorname {li} (x)|<{frac {1}{8pi }}{sqrt {x}},ln x,qquad xgeqslant 2657.}