stringtranslate.com

Función de conteo de primos

En matemáticas , la función de conteo de primos es la función que cuenta el número 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 π ).

Los valores de π ( n ) para los primeros 60 números enteros positivos

Índice de crecimiento

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] A finales del siglo XVIII, Gauss y Legendre conjeturaron 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. Atle Selberg y Paul Erdős encontraron pruebas del teorema de los números primos que no utilizaban la función zeta ni el análisis complejo alrededor de 1948 (en su mayor parte de forma independiente). [5]

Estimaciones más precisas

En 1899, de la Vallée Poussin demostró que [6] para alguna constante positiva a . Aquí, O (...) es la notación O mayúscula .

Ahora se conocen estimaciones más precisas de π ( x ) . Por ejemplo, en 2002, Kevin Ford demostró que [7]

Mossinghoff y Trudgian demostraron [8] un límite superior explícito para la diferencia entre π ( x ) y li( x ) :

Para valores de x que no sean irrazonablemente grandes, li( x ) es mayor que π ( x ) . Sin embargo, se sabe que π ( x ) − li( x ) cambia de signo una cantidad infinita de veces. Para una discusión sobre esto, consulte el número de Skewes .

Forma exacta

Para x > 1 sea π 0 ( x ) = π ( x ) − 1/2 cuando x es un número primo, y π 0 ( x ) = π ( x ) en caso contrario. Bernhard Riemann , en su obra Sobre el número de primos menores que una magnitud dada , demostró que π 0 ( x ) es igual a [9]

Fórmula explícita de Riemann que utiliza los primeros 200 ceros no triviales de la función zeta

donde μ ( n ) es la función de Möbius , li( x ) es la función integral logarítmica , ρ indexa cada cero de la función zeta de Riemann y li( x ρ/norte )​​no se evalúa con uncorte de ramasino que se considera comoEi(ρ/norte log x ) donde Ei( x ) es la integral exponencial . Si se recogen los ceros triviales y se toma la suma solo sobre los ceros no triviales ρ de la función zeta de Riemann, entonces π 0 ( x ) puede aproximarse mediante [10]

La hipótesis de Riemann sugiere que cada uno de esos ceros no triviales se encuentra a lo largo de Re( s ) = 1/2 .

Tabla deπ ( x ),⁠incógnita/registro( x )⁠, yli( x )

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

Gráfico que muestra la relación entre la función de conteo de primos π ( x ) y dos de sus aproximaciones ,incógnita/registro x y Li( x ) . A medida que x aumenta (nótese que el eje x es logarítmico), ambas razones tienden hacia 1. La razón paraincógnita/registro x converge desde arriba muy lentamente, mientras que la relación para Li( x ) converge más rápidamente desde abajo.

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

El valor de π (10 24 ) 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 25 ) se debe a J. Buethe, J. Franke , A. Jost y T. Kleinjung. [15] El valor de π (10 26 ) 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 de 10 27 , 10 28 y 10 29 fueron anunciados por David Baugh y Kim Walisch en 2015, [17] 2020, [18] y 2022, [19] respectivamente.

Algoritmos para evaluarπ ( x )

Una forma sencilla de encontrar π ( x ) , si x no es demasiado grande, es utilizar 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 (usando el principio de inclusión-exclusión ): dado x , si p 1 , p 2 ,…, p n son números primos distintos, entonces el número de enteros menores o iguales a x que son divisibles por ningún p i es

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

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

El algoritmo de Meissel-Lehmer

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 1 , p 2 ,…, 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 in . Entonces

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

Utilizando este enfoque, Meissel calculó π ( x ) , para x igual a5 × 10 5 , 10 6 , 10 7 y 10 8 .

En 1959, Derrick Henry Lehmer amplió y simplificó el método de Meissel. Defina, 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, fije P 0 ( m , n ) = 1 . Entonces

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

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

donde la suma es sobre números primos.

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

Utilizando su método y un IBM 701 , Lehmer pudo calcular el valor correcto de π (10 9 ) y falló el valor correcto de π (10 10 ) por 1. [20]

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

Otras funciones de conteo de primos

También se utilizan otras funciones de conteo de números primos porque es más cómodo trabajar con ellas.

Función de conteo de potencias primos de Riemann

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

Formalmente, podemos definir Π 0 ( x ) por

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

También podemos escribir

donde Λ es la función de von Mangoldt y

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

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

Función de Chebyshev

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

Para x ≥ 2 , [22]

y

Fórmulas para funciones de conteo de primos

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

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

dónde

Aquí ρ son los ceros de la función zeta de Riemann en la franja crítica, donde la parte real de ρ está 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 es condicionalmente convergente y debe tomarse en orden de valor absoluto creciente de la parte imaginaria. Nótese que la misma suma sobre las raíces triviales da el último sustraendo de la fórmula.

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

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. La integral es igual a la serie sobre los ceros triviales:

El primer término li( x ) es la función integral logarítmica habitual ; 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 hasta el plano complejo con corte de rama a lo largo de los reales positivos.

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

válido para x > 1 , donde

es la función R de Riemann [24] y μ ( n ) es la función de Möbius . La última serie para ella 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 en 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 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

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

La suma de los ceros zeta no triviales en la fórmula para π 0 ( x ) describe las fluctuaciones de π 0 ( 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

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

Desigualdades

A continuación se presentan algunas desigualdades útiles para π ( x ) .

para x ≥ 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ógnita tiene su valor máximo en x = 113. [29 ]

Pierre Dusart demostró en 2010: [30]

y

A continuación se presentan algunas desigualdades para el primo n , p n . El límite superior se debe a Rosser (1941), [31] el inferior a Dusart (1999): [32]

La desigualdad de la izquierda se cumple para n ≥ 2 y la desigualdad de la derecha se cumple para n ≥ 6 .

Una aproximación para el n- ésimo número primo es

Ramanujan [33] demostró que la desigualdad

se cumple para todos los valores suficientemente grandes de x .

En 2010 [30] Dusart demostró (Proposición 6.6) que, para n ≥ 688383 ,

y (Proposición 6.7) que, para n ≥ 3 ,

Más recientemente, Dusart [34] ha demostrado (Teorema 5.1) que, para x > 1 ,

y que, para x ≥ 88789 ,

La hipótesis de Riemann

La hipótesis de Riemann implica un límite mucho más estricto para el error en la estimación de π ( x ) y, por lo tanto, una distribución más regular de números primos.

En concreto, [35]

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

Véase también

Referencias

  1. ^ Bach, Eric; Shallit, Jeffrey (1996). Teoría algorítmica de números . MIT Press. Volumen 1, página 234, sección 8.8. ISBN 0-262-02405-5.
  2. ^ Weisstein, Eric W. "Función de conteo de primos". MathWorld .
  3. ^ ab "¿Cuántos números primos hay?". Chris K. Caldwell. Archivado desde el original el 15 de octubre de 2012. Consultado el 2 de diciembre de 2008 .
  4. ^ Dickson, Leonard Eugene (2005). Historia de la teoría de los números, vol. I: divisibilidad y primalidad . Publicaciones de Dover. ISBN 0-486-44232-2.
  5. ^ Ireland, Kenneth; Rosen, Michael (1998). Una introducción clásica a la teoría de números moderna (segunda edición). Springer. ISBN 0-387-97329-X.
  6. ^ Véase también el teorema 23 de AE ​​Ingham (2000). La distribución de los números primos . Cambridge University Press. ISBN 0-521-39789-8.
  7. ^ Kevin Ford (noviembre de 2002). "Integral y límites de Vinogradov para la función zeta de Riemann" (PDF) . Proc. London Math. Soc . 85 (3): 565–633. arXiv : 1910.08209 . doi :10.1112/S0024611502013655. S2CID  121144007.
  8. ^ Mossinghoff, Michael J.; Trudgian, Timothy S. (2015). "Polinomios trigonométricos no negativos y una región libre de ceros para la función zeta de Riemann". J. Number Theory . 157 : 329–349. arXiv : 1410.3926 . doi :10.1016/J.JNT.2015.05.010. S2CID  117968965.
  9. ^ Hutama, Daniel (2017). "Implementación de la fórmula explícita de Riemann para primos racionales y gaussianos en Sage" (PDF) . Instituto de Ciencias Matemáticas .
  10. ^ ab Riesel, Hans ; Göhl, Gunnar (1970). "Algunos cálculos relacionados con la fórmula de los números primos de Riemann" (PDF) . Matemáticas de la computación . 24 (112). Sociedad Matemática Americana: 969–983. doi :10.2307/2004630. ISSN  0025-5718. JSTOR  2004630. MR  0277489.
  11. ^ "Tablas de valores de π (x) y de π2 (x)". Tomás Oliveira y Silva . Consultado el 31 de marzo de 2024 .
  12. ^ "Tabla de valores de π(x)". Xavier Gourdon, Pascal Sebah, Patrick Demichel . Consultado el 14 de septiembre de 2008 .
  13. ^ "Cálculo condicional de π(1024)". Chris K. Caldwell . Consultado el 30 de marzo de 2024 .
  14. ^ Platt, David J. (2012). "Cálculo analítico de π ( x ) ". arXiv : 1203.5712 [math.NT].
  15. ^ "¿Cuántos números primos hay?". J. Buethe . Consultado el 1 de septiembre de 2015 .
  16. ^ Staple, Douglas (19 de agosto de 2015). El algoritmo combinatorio para calcular π(x) (Tesis). Universidad de Dalhousie . Consultado el 1 de septiembre de 2015 .
  17. ^ Walisch, Kim (6 de septiembre de 2015). "Nuevo registro de función de recuento de primos π (1027) confirmado". Foro de Mersenne .
  18. ^ Baugh, David (30 de agosto de 2020). "Nuevo registro de función de conteo de primos, pi(10^28)". Foro Mersenne .
  19. ^ Walisch, Kim (4 de marzo de 2022). "Nuevo registro de función de conteo de primos: PrimePi (10 ^ 29)". Foro de Mersenne .
  20. ^ Lehmer, Derrick Henry (1 de abril de 1958). «Sobre el número exacto de primos menores que un límite dado». Illinois J. Math . 3 (3): 381–388 . Consultado el 1 de febrero de 2017 .
  21. ^ Deléglise, Marc; Rivat, Joel (enero de 1996). "Cálculo de π (x): el método de Meissel, Lehmer, Lagarias, Miller, Odlyzko" (PDF) . Matemáticas de la Computación . 65 (213): 235–245. doi : 10.1090/S0025-5718-96-00674-6 .
  22. ^ Apostol, Tom M. (2010). Introducción a la teoría analítica de números . Springer.
  23. ^ Titchmarsh, EC (1960). La teoría de funciones, 2.ª ed . Oxford University Press.
  24. ^ Weisstein, Eric W. "Función de conteo de primos de Riemann". MathWorld .
  25. ^ Riesel, Hans (1994). Números primos y métodos informáticos para la factorización . Progreso en matemáticas. Vol. 126 (2.ª ed.). Birkhäuser. págs. 50-51. ISBN. 0-8176-3743-5.
  26. ^ Weisstein, Eric W. "Serie Gram". MathWorld .
  27. ^ Bornemann, Folkmar. "Solución de un problema planteado por Jörg Waldvogel" (PDF) .
  28. ^ "La codificación de la distribución de primos por los ceros zeta". Matthew Watkins . Consultado el 14 de septiembre de 2008 .
  29. ^ Rosser, J. Barkley ; Schoenfeld, Lowell (1962). "Fórmulas aproximadas para algunas funciones de números primos". Illinois J. Math . 6 : 64–94. doi : 10.1215/ijm/1255631807 . ISSN  0019-2082. Zbl  0122.05001.
  30. ^ ab Dusart, Pierre (2 de febrero de 2010). "Estimaciones de algunas funciones sobre números primos sin RH". arXiv : 1002.0442v1 [math.NT].
  31. ^ Rosser, Barkley (1941). "Límites explícitos para algunas funciones de números primos". American Journal of Mathematics . 63 (1): 211–232. doi :10.2307/2371291. JSTOR  2371291.
  32. ^ Dusart, Pierre (1999). "El k-ésimo primo es mayor que k(ln k + ln ln k − 1) para k ≥ 2". Matemáticas de la computación . 68 (225): 411–415. doi : 10.1090/S0025-5718-99-01037-6 .
  33. ^ Berndt, Bruce C. (6 de diciembre de 2012). Cuadernos de Ramanujan, parte IV. Springer Science & Business Media. págs. 112-113. ISBN 9781461269328.
  34. ^ Dusart, Pierre (enero de 2018). "Estimaciones explícitas de algunas funciones sobre números primos". Ramanujan Journal . 45 (1): 225–234. doi :10.1007/s11139-016-9839-4. S2CID  125120533.
  35. ^ Schoenfeld, Lowell (1976). "Límites más precisos para las funciones de Chebyshev θ ( x ) y ψ ( x ). II". Matemáticas de la computación . 30 (134). Sociedad Matemática Americana: 337–360. doi :10.2307/2005976. ISSN  0025-5718. JSTOR  2005976. MR  0457374.

Notas

  1. ^ Montgomery demostró que (asumiendo la hipótesis de Riemann) al menos dos tercios de todos los ceros son simples.

Enlaces externos