В математике функция распределения простых чисел, или пи-функция π ( 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 / ln x и li(x)

В следующей таблице показан рост функций π ( 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)} может быть выполнено с помощью следующих правил:

  • Φ ( m , 0 ) = ⌊ m ⌋ {displaystyle Phi (m,0)=lfloor m floor }
  • Φ ( m , b ) = Φ ( m , b − 1 ) − Φ ( m p b , b − 1 ) {displaystyle Phi (m,b)=Phi (m,b-1)-Phi left({frac {m}{p_{b}}},b-1 ight)}
  • Используя этот метод и 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.}

    Имя:*
    E-Mail:
    Комментарий: