Función de conteo de números primos

En matemáticas , la función de conteo de primos es la función que cuenta la cantidad de números primos menores o iguales a algún número real x . ^{[ 1 ] [ 2 ]} Se denota por π ( x ) (sin relación con el número π ).

Una variante simétrica que se observa a veces es π ₀ ( x ) , que es igual a π ( x ) − 1 ⁄ 2 si x es exactamente un número primo, e igual a π ( x ) en caso contrario. Es decir, la cantidad de números primos menores que x , más la mitad si x es un número primo.

De gran interés en la teoría de números es la tasa de crecimiento de la función de conteo de primos. ^{[ 3 ] [ 4 ]} Gauss y Legendre conjeturaron a finales del siglo XVIII que era aproximadamente donde log es el logaritmo natural , en el sentido de que Esta afirmación es el teorema de los números primos . Una afirmación equivalente es donde li es la función integral logarítmica . El teorema de los números primos fue demostrado por primera vez en 1896 por Jacques Hadamard y por Charles de la Vallée Poussin de forma independiente, utilizando propiedades de la función zeta de Riemann introducida por Riemann en 1859. Demostraciones del teorema de los números primos que no utilizan la función zeta ni el análisis complejo fueron encontradas alrededor de 1948 por Atle Selberg y por Paul Erdős (en su mayor parte de forma independiente). ^{[ 5 ]}$${\displaystyle {\frac {x}{\log x}}}$$$${\displaystyle \lim _{x\rightarrow \infty }{\frac {\pi (x)}{x/\log x}}=1.}$$$${\displaystyle \lim _{x\rightarrow \infty }{\frac {\pi (x)}{\operatorname {li} (x)}}=1}$$

In 1899, de la Vallée Poussin proved that ^[6]$${\displaystyle \pi (x)=\operatorname {li} (x)+O\left(xe^{-a{\sqrt {\log x}}}\right)\quad {\text{cuando }}x\to \infty }$$ for some positive constant a. Here, O(...) is the big O notation.

More precise estimates of π(x) are now known. For example, in 2002, Kevin Ford proved that^[7]$${\displaystyle \pi (x)=\operatorname {li} (x)+O\left(x\exp \left(-0.2098(\log x)^{3/5}(\log \log x)^{-1/5}\right)\right).}$$

Mossinghoff and Trudgian proved^[8] an explicit upper bound for the difference between π(x) and li(x): $${\displaystyle {\bigl |}\pi (x)-\operatorname {li} (x){\bigr |}\leq 0.2593{\frac {x}{(\log x)^{3/4}}}\exp \left(-{\sqrt {\frac {\log x}{6.315}}}\right)\quad {\text{para }}x\geq 229.}$$

For values of x that are not unreasonably large, li(x) is greater than π(x). However, π(x) − li(x) is known to change sign infinitely many times. For a discussion of this, see Skewes' number.

For x > 1 let π₀(x) = π(x) − ⁠1/2⁠ when x is a prime number, and π₀(x) = π(x) otherwise. Bernhard Riemann, in his work On the Number of Primes Less Than a Given Magnitude, proved that π₀(x) is equal to^[9]

$${\displaystyle \pi _{0}(x)=\operatorname {R} (x)-\sum _{\rho }\operatorname {R} (x^{\rho }),}$$ where $${\displaystyle \operatorname {R} (x)=\sum _{n=1}^{\infty }{\frac {\mu (n)}{n}}\operatorname {li} \left(x^{1/n}\right),}$$μ(n) is the Möbius function, li(x) is the logarithmic integral function, ρ indexes every zero of the Riemann zeta function, and li(x^⁠ρ/n⁠) is not evaluated with a branch cut but instead considered as Ei(⁠ρ/n⁠ log x) where Ei(x) is the exponential integral. If the trivial zeros are collected and the sum is taken only over the non-trivial zeros ρ of the Riemann zeta function, then π₀(x) may be approximated by^[10]$${\displaystyle \pi _{0}(x)\approx \operatorname {R} (x)-\sum _{\rho }\operatorname {R} \left(x^{\rho }\right)-{\frac {1}{\log x}}+{\frac {1}{\pi }}\arctan {\frac {\pi }{\log x}}.}$$

La hipótesis de Riemann sugiere que cada cero no trivial de este tipo se encuentra a lo largo de Re( s ) = ⁠1/2⁠ .

La tabla muestra cómo las tres funciones π ( x ) , ⁠incógnita/logaritmo x⁠ , y li( x ) comparados en potencias de 10. Véase también, ^{[ 3 ] [ 11 ]} y ^{[ 12 ]}

En la Enciclopedia en línea de secuencias de enteros , la columna π ( x ) es la secuencia OEIS :  A006880 , π ( x ) − ⁠incógnita/logaritmo x⁠ es la secuencia OEIS :  A057835 , y li( x ) − π ( x ) es la secuencia OEIS :  A057752 .

El valor de π (10 ²⁴ ) fue calculado originalmente por J. Buethe, J. Franke , A. Jost y T. Kleinjung asumiendo la hipótesis de Riemann . ^{[ 13 ]} Posteriormente fue verificado incondicionalmente en un cálculo por DJ Platt. ^{[ 14 ]} El valor de π (10 ²⁵ ) es de los mismos cuatro autores. ^{[ 15 ]} El valor de π (10 ²⁶ ) fue calculado por DB Staple. ^{[ 16 ]} Todas las demás entradas anteriores en esta tabla también fueron verificadas como parte de ese trabajo.

Los valores para 10 ²⁷ , 10 ²⁸ y 10 ²⁹ fueron anunciados por David Baugh y Kim Walisch en 2015, ^{[ 17 ]} 2020, ^{[ 18 ]} y 2022, ^{[ 19 ]} respectivamente.

Una forma sencilla de encontrar π ( x ) , si x no es demasiado grande, es usar la criba de Eratóstenes para producir los primos menores o iguales a x y luego contarlos.

Una forma más elaborada de encontrar π ( x ) se debe a Legendre (utilizando el principio de inclusión-exclusión ): dado x , si p ₁ , p ₂ ,…, p _n son números primos distintos, entonces el número de enteros menores o iguales a x que no son divisibles por ningún p _i es

${\displaystyle \lfloor x\rfloor -\sum _{i}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor +\sum _{i<j}\left\lfloor {\frac {x}{p_{i}p_{j}}}\right\rfloor -\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_{j}p_{k}}}\right\rfloor +\cdots }$

(donde ⌊ x ⌋ denota la función piso ). Por lo tanto, este número es igual a

${\displaystyle \pi (x)-\pi \left({\sqrt {x}}\right)+1}$

cuando los números p ₁ , p ₂ ,…, p _n son los números primos menores o iguales a la raíz cuadrada de x .

En una serie de artículos publicados entre 1870 y 1885, Ernst Meissel describió (y utilizó) una forma combinatoria práctica de evaluar π ( x ) : Sean p ₁ , p ₂ ,…, p _n los primeros n primos y denotemos por Φ( m , n ) el número de números naturales no mayores que m que no son divisibles por ninguno de los p _i para cualquier i ≤ n . Entonces

${\displaystyle \Phi (m,n)=\Phi (m,n-1)-\Phi \left({\frac {m}{p_{n}}},n-1\right).}$

Dado un número natural m , si n = π ( ³ √ m ) y si μ = π ( √ m ) − n , entonces

${\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}}}\right).}$

Utilizando este enfoque, Meissel calculó π ( x ) , para x igual a5 × 10 ⁵ , 10 ⁶ , 10 ⁷ , y 10 ⁸ .

En 1959, Derrick Henry Lehmer extendió y simplificó el método de Meissel. Definimos, para m real y para números naturales n y k , P _k ( m , n ) como el número de números no mayores que m con exactamente k factores primos, todos mayores que p _n . Además, establecemos P ₀ ( m , n ) = 1 . Entonces

${\displaystyle \Phi (m,n)=\sum _{k=0}^{+\infty }P_{k}(m,n)}$

donde la suma en realidad tiene solo un número finito de términos distintos de cero. Sea y un entero tal que ³ √ m ≤ y ≤ √ m , y sea n = π ( y ) . Entonces P ₁ ( m , n ) = π ( m ) − n y P _k ( m , n ) = 0 cuando k ≥ 3 . Por lo tanto,

${\displaystyle \pi (m)=\Phi (m,n)+n-1-P_{2}(m,n)}$

El cálculo de P ₂ ( m , n ) se puede obtener de esta manera:

${\displaystyle P_{2}(m,n)=\sum _{y<p\leq {\sqrt {m}}}\left(\pi \left({\frac {m}{p}}\right)-\pi (p)+1\right)}$

donde la suma se realiza sobre números primos.

Por otro lado, el cálculo de Φ( m , n ) se puede realizar utilizando las siguientes reglas:

1. ${\displaystyle \Phi (m,0)=\lfloor m\rfloor }$
2. ${\displaystyle \Phi (m,b)=\Phi (m,b-1)-\Phi \left({\frac {m}{p_{b}}},b-1\right)}$

Utilizando su método y una IBM 701 , Lehmer pudo calcular el valor correcto de π (10 ⁹ ) y falló en el valor correcto de π (10 ¹⁰ ) por 1. ^{[ 20 ]}

Lagarias, Miller, Odlyzko, Deléglise y Rivat realizaron mejoras adicionales a este método. ^{[ 21 ]}

También se utilizan otras funciones de conteo de números primos porque son más fáciles de usar.

La función de conteo de potencias primas de Riemann se suele denotar como Π ₀ ( x ) o J ₀ ( x ) . Tiene saltos de ⁠1/norte⁠ en potencias primas p ⁿ y toma un valor a medio camino entre los dos lados en las discontinuidades de π ( x ) . Ese detalle adicional se utiliza porque la función puede definirse entonces mediante una transformada inversa de Mellin .

Formalmente, podemos definir Π ₀ ( x ) mediante

${\displaystyle \Pi _{0}(x)={\frac {1}{2}}\left(\sum _{p^{n}<x}{\frac {1}{n}}+\sum _{p^{n}\leq x}{\frac {1}{n}}\right)\ }$

donde la variable p en cada suma abarca todos los números primos dentro de los límites especificados.

También podemos escribir

${\displaystyle \ \Pi _{0}(x)=\sum _{n=2}^{x}{\frac {\Lambda (n)}{\log n}}-{\frac {\Lambda (x)}{2\log x}}=\sum _{n=1}^{\infty }{\frac {1}{n}}\pi _{0}\left(x^{1/n}\right)}$

donde Λ es la función de von Mangoldt y

${\displaystyle \pi _{0}(x)=\lim _{\varepsilon \to 0}{\frac {\pi (x-\varepsilon )+\pi (x+\varepsilon )}{2}}.}$

La fórmula de inversión de Möbius da entonces

${\displaystyle \pi _{0}(x)=\sum _{n=1}^{\infty }{\frac {\mu (n)}{n}}\ \Pi _{0}\left(x^{1/n}\right),}$

donde μ ( n ) es la función de Möbius .

Conociendo la relación entre el logaritmo de la función zeta de Riemann y la función de von Mangoldt Λ , y utilizando la fórmula de Perron tenemos

${\displaystyle \log \zeta (s)=s\int _{0}^{\infty }\Pi _{0}(x)x^{-s-1}\,\mathrm {d} x}$

La función de Chebyshev pondera los números primos o potencias de números primos p ⁿ mediante log p :

${\displaystyle {\begin{aligned}\vartheta (x)&=\sum _{p\leq x}\log p\\\psi (x)&=\sum _{p^{n}\leq x}\log p=\sum _{n=1}^{\infty }\vartheta \left(x^{1/n}\right)=\sum _{n\leq x}\Lambda (n).\end{aligned}}}$

Para x ≥ 2 , ^{[ 22 ]}

${\displaystyle \vartheta (x)=\pi (x)\log x-\int _{2}^{x}{\frac {\pi (t)}{t}}\,\mathrm {d} t}$

y

${\displaystyle \pi (x)={\frac {\vartheta (x)}{\log x}}+\int _{2}^{x}{\frac {\vartheta (t)}{t\log ^{2}(t)}}\mathrm {d} t.}$

Las fórmulas para funciones de conteo de números primos se dividen en dos tipos: fórmulas aritméticas y fórmulas analíticas. Las fórmulas analíticas para el conteo de números primos fueron las primeras en utilizarse para demostrar el teorema de los números primos . Provienen del trabajo de Riemann y von Mangoldt , y generalmente se conocen como fórmulas explícitas . ^{[ 23 ]}

Tenemos la siguiente expresión para la segunda función de Chebyshev ψ :

${\displaystyle \psi _{0}(x)=x-\sum _{\rho }{\frac {x^{\rho }}{\rho }}-\log 2\pi -{\frac {1}{2}}\log \left(1-x^{-2}\right),}$

dónde

${\displaystyle \psi _{0}(x)=\lim _{\varepsilon \to 0}{\frac {\psi (x-\varepsilon )+\psi (x+\varepsilon )}{2}}.}$

Aquí, ρ representa los ceros de la función zeta de Riemann en la banda crítica, donde la parte real de ρ se encuentra entre cero y uno. La fórmula es válida para valores de x mayores que uno, que es la región de interés. La suma sobre las raíces converge condicionalmente y debe tomarse en orden creciente del valor absoluto de la parte imaginaria. Nótese que la misma suma sobre las raíces triviales proporciona el último sustraendo de la fórmula.

Para Π ₀ ( x ) tenemos una fórmula más complicada

${\displaystyle \Pi _{0}(x)=\operatorname {li} (x)-\sum _{\rho }\operatorname {li} \left(x^{\rho }\right)-\log 2+\int _{x}^{\infty }{\frac {\mathrm {d} t}{t\left(t^{2}-1\right)\log t}}.}$

Nuevamente, la fórmula es válida para x > 1 , mientras que ρ son los ceros no triviales de la función zeta ordenados según su valor absoluto. El primer término li( x ) es la función integral logarítmica usual ; la expresión li( x ^ρ ) en el segundo término debe considerarse como Ei( ρ log x ) , donde Ei es la continuación analítica de la función integral exponencial desde los reales negativos al plano complejo con corte de rama a lo largo de los reales positivos. La integral final es igual a la serie sobre los ceros triviales:

${\displaystyle \int _{x}^{\infty }{\frac {\mathrm {d} t}{t\left(t^{2}-1\right)\log t}}=\int _{x}^{\infty }{\frac {1}{t\log t}}\left(\sum _{m}t^{-2m}\right)\,\mathrm {d} t=\sum _{m}\int _{x}^{\infty }{\frac {t^{-2m}}{t\log t}}\,\mathrm {d} t\,\,{\overset {\left(u=t^{-2m}\right)}{=}}-\sum _{m}\operatorname {li} \left(x^{-2m}\right)}$

Así, la fórmula de inversión de Möbius nos da ^{[ 10 ]}

${\displaystyle \pi _{0}(x)=\operatorname {R} (x)-\sum _{\rho }\operatorname {R} \left(x^{\rho }\right)-\sum _{m}\operatorname {R} \left(x^{-2m}\right)}$

válido para x > 1 , donde

${\displaystyle \operatorname {R} (x)=\sum _{n=1}^{\infty }{\frac {\mu (n)}{n}}\operatorname {li} \left(x^{1/n}\right)=1+\sum _{k=1}^{\infty }{\frac {\left(\log x\right)^{k}}{k!k\zeta (k+1)}}}$

es la función R de Riemann ^{[ 24 ]} y μ ( n ) es la función de Möbius . Esta última serie se conoce como serie de Gram . ^{[ 25 ] [ 26 ]} Debido a que log x < x para todo x > 0 , esta serie converge para todo x positivo por comparación con la serie para e ^x . El logaritmo en la serie de Gram de la suma sobre la contribución cero no trivial debe evaluarse como ρ log x y no como log x ^ρ .

Folkmar Bornemann demostró, ^{[ 27 ]} al asumir la conjetura de que todos los ceros de la función zeta de Riemann son simples, ^{[ nota 1 ]} que

${\displaystyle \operatorname {R} \left(e^{-2\pi t}\right)={\frac {1}{\pi }}\sum _{k=1}^{\infty }{\frac {(-1)^{k-1}t^{-2k-1}}{(2k+1)\zeta (2k+1)}}+{\frac {1}{2}}\sum _{\rho }{\frac {t^{-\rho }}{\rho \cos {\frac {\pi \rho }{2}}\zeta '(\rho )}}}$

donde ρ recorre los ceros no triviales de la función zeta de Riemann y t > 0 .

La suma sobre ceros zeta no triviales en la fórmula para π ₀ ( x ) describe las fluctuaciones de π ₀ ( x ) mientras que los términos restantes dan la parte "suave" de la función de conteo de primos, ^{[ 28 ]} por lo que se puede usar

${\displaystyle \operatorname {R} (x)-\sum _{m=1}^{\infty }\operatorname {R} \left(x^{-2m}\right)}$

como un buen estimador de π ( x ) para x > 1 . De hecho, dado que el segundo término se aproxima a 0 cuando x → ∞ , mientras que la amplitud de la parte "ruidosa" es heurísticamente aproximadamente ⁠√ x/logaritmo x⁠ , estimar π ( x ) solo con R( x ) es igual de bueno, y las fluctuaciones de la distribución de primos pueden representarse claramente con la función

${\displaystyle {\bigl (}\pi _{0}(x)-\operatorname {R} (x){\bigr )}{\frac {\log x}{\sqrt {x}}}.}$

Ramanujan ^{[ 29 ]} demostró que la desigualdad

${\displaystyle \pi (x)^{2}<{\frac {ex}{\log x}}\pi \left({\frac {x}{e}}\right)}$

se cumple para todos los valores suficientemente grandes de x .

Aquí hay algunas desigualdades útiles para π ( x ) .

${\displaystyle {\frac {x}{\log x}}<\pi (x)<1.25506{\frac {x}{\log x}}\quad {\text{for }}x\geq 17.}$

La desigualdad de la izquierda se cumple para x ≥ 17 y la desigualdad de la derecha se cumple para x > 1. La constante 1,25506 es 30 .registro 113/113⁠ hasta 5 decimales, como π ( x ) ⁠logaritmo x/incógnitatiene su valor máximo en x = p ₃₀ = 113 . ^{[ 30 ]}

Pierre Dusart demostró en 2010: ^{[ 31 ]}

${\displaystyle {\frac {x}{\log x-1}}<\pi (x)<{\frac {x}{\log x-1.1}}\quad {\text{for }}x\geq 5393{\text{ and }}x\geq 60184,{\text{ respectively.}}}$

Más recientemente, Dusart ha demostrado ^{[ 32 ]} (Teorema 5.1) que

${\displaystyle {\frac {x}{\log x}}\left(1+{\frac {1}{\log x}}+{\frac {2}{\log ^{2}x}}\right)\leq \pi (x)\leq {\frac {x}{\log x}}\left(1+{\frac {1}{\log x}}+{\frac {2}{\log ^{2}x}}+{\frac {7.59}{\log ^{3}x}}\right),}$

para x ≥ 88789 y x > 1 , respectivamente.

En la otra dirección, una aproximación para el n -ésimo primo, p _n , es

${\displaystyle p_{n}=n\left(\log n+\log \log n-1+{\frac {\log \log n-2}{\log n}}+O\left({\frac {(\log \log n)^{2}}{(\log n)^{2}}}\right)\right).}$

Aquí se presentan algunas desigualdades para el n- ésimo número primo. La cota inferior se debe a Dusart (1999) ^{[ 33 ]} y la cota superior a Rosser (1941). ^{[ 34 ]}

${\displaystyle n(\log n+\log \log n-1)<p_{n}<n(\log n+\log \log n)\quad {\text{for }}n\geq 6.}$

La desigualdad de la izquierda se cumple para n ≥ 2 y la desigualdad de la derecha se cumple para n ≥ 6. Una forma variante que a veces se ve sustituye Una cota inferior aún más simple es ^{[ 35 ]}${\displaystyle \log n+\log \log n=\log(n\log n).}$

${\displaystyle n\log n<p_{n},}$

lo cual se cumple para todo n ≥ 1 , pero el límite inferior anterior es más ajustado para n > e ^e ≈15,154 .

En 2010 Dusart demostró ^{[ 31 ]} (Proposiciones 6.7 y 6.6) que

${\displaystyle n\left(\log n+\log \log n-1+{\frac {\log \log n-2.1}{\log n}}\right)\leq p_{n}\leq n\left(\log n+\log \log n-1+{\frac {\log \log n-2}{\log n}}\right),}$

para n ≥ 3 y n ≥ 688383 , respectivamente.

En 2024, Axler ^{[ 36 ]} ajustó aún más esto (ecuaciones 1.12 y 1.13) utilizando límites de la forma

${\displaystyle f(n,g(w))=n\left(\log n+\log \log n-1+{\frac {\log \log n-2}{\log n}}-{\frac {g(\log \log n)}{2\log ^{2}n}}\right)}$

demostrando que

${\displaystyle f(n,w^{2}-6w+11.321)\leq p_{n}\leq f(n,w^{2}-6w)}$

para n ≥ 2 y n ≥ 3468 , respectivamente. El límite inferior también puede simplificarse a f ( n , w ² ) sin alterar su validez. El límite superior puede ajustarse a f ( n , w ² − 6 w + 10.667) si n ≥ 46254381 .

Hay límites adicionales de complejidad variable. ^{[ 37 ] [ 38 ] [ 39 ]}

La hipótesis de Riemann implica una cota mucho más ajustada para el error en la estimación de π ( x ) , y por lo tanto a una distribución más regular de los números primos,

${\displaystyle \pi (x)=\operatorname {li} (x)+O({\sqrt {x}}\log {x}).}$

Específicamente, ^{[ 40 ]}

${\displaystyle |\pi (x)-\operatorname {li} (x)|<{\frac {\sqrt {x}}{8\pi }}\,\log {x},\quad {\text{for all }}x\geq 2657.}$

Dudek (2015) demostró que la hipótesis de Riemann implica que para todo x ≥ 2 existe un primo p que satisface

${\displaystyle x-{\frac {4}{\pi }}{\sqrt {x}}\log x<p\leq x.}$

• El postulado de Bertrand
• La conjetura de Oppermann
• Ramanujan primo

• Chris Caldwell, The Nth Prime Page en The Prime Pages .
• Tomás Oliveira e Silva, Tablas de funciones de conteo de primos .
• Dudek, Adrian W. (2015), "Sobre la hipótesis de Riemann y la diferencia entre primos", International Journal of Number Theory , 11 (3): 771– 778, arXiv : 1402.6417 , Bibcode : 2014arXiv1402.6417D , doi : 10.1142/S1793042115500426 , ISSN  1793-0421 , S2CID  119321107