El mito de que no prime la leche de fórmula?

Question

Terence Tao reclamaciones:

Por ejemplo, tenemos una fórmula exacta para el $n^\text{th}$ plaza número de $n^2$–, pero no tenemos un (útil) exacto fórmula para el $n^\text{th}$ primer número $p_n$!
"Dios no juega a los dados con el universo, pero algo extraño está sucediendo con los números primos." (Paul Erdős, 1913-1996)

Sin embargo no existe una fórmula exacta para el enésimo primer

Un doble de la suma de los nth primer p_n es $$p_n=1+\sum_{k=1}^{2(\lfloor n\ln n\rfloor+1)}\Biggl[1-\Biggl\lfloor\frac{\sum_{j=2}^k 1+\lfloor s(j)\rfloor}n\Biggr\rfloor\Biggr],\tag{13}$$ where $$s(j)\equiv-\frac{\sum_{s=1}^j \bigl(\bigl\lfloor\frac js\bigr\rfloor-\bigl\lfloor\frac{j-1}s\bigr\rfloor\bigr)-2}j\tag{14}$$

(Véase el Primer fórmulas en MathWorld.) Existe incluso una fórmula exacta para la primer función de recuento $\pi (x)$. Entonces, ¿por qué los matemáticos tratando de demostrar la hipótesis de Riemann para encontrar una mejor estimación de $\pi(x)$ $p_n$ cuando tienen exactamente esas fórmulas?

Answer 1

Si hay un cuerpo matemático de conocimiento que le permite manipular las fórmulas (13) y (14) a través de una mejor forma, pues genial! La Riemann zeta función ya ha demostrado su valía en este campo. Fue instrumental en la pruebas por Hadamard y de la Vallée-Poussin del Teorema de los números Primos. Lo que permitió que eso sucediera era que los zeta función es una función de meromorphic, y así la teoría de variable compleja se podría aplicar a su estudio. Uno nunca sabe con certeza si el estudio de la función zeta va a pagar, pero la gente está apostando a que, basado en los éxitos del pasado.

No sé si alguien está promoviendo (13) y (14) como herramientas útiles en el estudio de los números primos, pero si es así, la responsabilidad recae sobre aquellas personas que exhiben las herramientas matemáticas que permiten manipular (13) y (14) de manera efectiva.

Debido a todo el piso funciones, (13) y (14) no tienen muy agradable propiedades analíticas. Como otros carteles han señalado, que codifican una primaria algoritmo para la identificación de los números primos. En particular, la expresión $$ \left\lfloor\frac{j}{s}\right\rfloor-\left\lfloor\frac{j-1}{s}\right\rfloor $$ que aparece en el numerador de (14) es igual a $1$ si $s$ uniformemente divide $j$ y es igual a $0$ si no lo hace. Sumando esta cantidad de $s$ $1$ $j$le da el número de divisores de a $j.$ números Primos tienen exactamente dos divisores; compuesto de números, todos tienen al menos tres. El numerador en (14) por lo tanto es $0$ al $j$ es primo, y positiva cuando es compuesto. Dividiendo por $j$ y multiplicando por $-1$ resultados en la cantidad de $s(j),$ $0$ al $j$ es primo y se encuentra en el intervalo de $(-1,0)$ al $j$ es compuesto. El piso de $s(j$) por lo tanto es igual a $0$ al $j$ es el primer y $-1$ al $j$ es compuesto. La adición de $1$ $\lfloor s(j)\rfloor$da la función característica de los números primos.

Observe que el uso de la fórmula (14), se requiere hacer más divisiones que incluso ingenua de un ataque de fuerza bruta algoritmo para calcular el número de divisores. Que precio podría ser vale la pena pagar si la fórmula se había agradable propiedades matemáticas que les permitía extraer más información de él, pero yo no veo que esto ha sido demostrado. Para mí, se parece a un engorroso codificación aritmética de un algoritmo ineficaz. Yo sería feliz de estar equivocado acerca de esto!

La fórmula (13) del mismo modo se parece a un engorroso codificación aritmética de un método de fuerza bruta para calcular el $n^\text{th}$ la primera, y parece probable que requiera más de cálculo de estado-of-the-art de los algoritmos. De nuevo, sería bueno si alguien podría mostrar cómo extraer información útil a partir de la fórmula, pero no se ve muy prometedor.

Añadido: creo que vale la pena señalar que algunos no trivial de la teoría analítica de números entra en la fórmula (13) en la elección del límite superior de la sumatoria de más de $k.$ Usted necesita para asegurarse de que el $p_n$ se encuentra en el rango de la suma, pero que $p_{2n}$ no. La razón es que el sumando es igual a $1$ al $k<p_n,$ es igual a $0$ $p_n\le k<p_{2n},$ y pasa a ser negativo para $k\ge p_{2n}.$ por Lo que necesita la suma de más de $k$ para incluir a todos los $p_n-1$ términos donde el sumando es igual a $1$, pero ninguno de los términos donde es negativa. Esto asegurará que la suma evalúa a $p_n-1.$

A mí me parece que necesita algo como (3.12) y (3.13) en este papel de Rosser y Schoenfeld para justificar el límite superior. La fórmula (3.12) es Rosser del Teorema que Dietrich Burde la respuesta a este post sugiere que se requiere un profundo conocimiento de la función zeta de ceros. Curiosamente, el autor de las fórmulas (13) y (14) (Sebastián Martín Ruiz) no rigurosamente justificar el límite superior en su artículo, dando sólo un argumento heurístico y declarando que es "muy probable" que las desigualdades están satisfechos.

Tal vez se podría jugar con la constante delante de $\lfloor n\log n\rfloor$ e intente utilizar de Chebyshev límites (Teorema 3.1 aquí) en lugar de Rosser del Teorema. (La derivación de Chebyshev límites no necesita el conocimiento de la función zeta de ceros.) Pero esto parece posiblemente bastante delicada, y puede que no funcione.

Segunda adición: Algunos de discusión de la fórmula, y Ruiz de la vista de ella, se pueden encontrar aquí.

Answer 2

Los matemáticos no están realmente interesados en los valores particulares de la función de conteo. (Ellos ya saben toneladas de ellos, obtenidos mediante la ejecución eficiente de los tamices.)

Lo que está después de la penetración en su comportamiento asintótico (la precisión con que se puede valorar como $x$ crece). Mejor, que como para entender la intrigante irregularidad en la distribución y poner un poco de orden en ella.

La fórmula, así como muchos otros similares, no es de ninguna utilidad para calcular los valores de la función (es demasiado ineficiente) y no trae ningún insight (se trata de una reescritura de un algoritmo trivial).

La relación con los ceros de la función Zeta es mucho más profundo.

Answer 3

Las fórmulas de los números primos es un precioso documento de 1983 por Underwood Dudley en Matemáticas de la Revista. Se explica cómo cocinar el impresionante aspecto, pero trivial/inútil fórmulas para el $n$th primer o del primer función de recuento, y le da un puñado de referencias a casos desafortunados en la literatura de tales fórmulas de ser publicado.

Answer 4

Por lo general, cuando alguien dice que "tenemos una fórmula para $f(x)$", lo que significa que tenemos una manera de computar $f$ más rápido de lo que es dirigir a la definición (o por la definición, si es que es lo suficientemente rápido).

Por ejemplo, la función de $f(x) = x^2$ puede ser calculado por el si $x$ es dado en binario (o cualquier radix) por la forma en que probablemente aprendió en la escuela primaria. Por otro lado, si se te pide para factorizar un número grande, que rápidamente aprenden que no se conoce "la fórmula", en otras palabras, nada es mucho más rápido que simplemente la comprobación de todos los números (el más rápido que se conoce enfoques son casi tan rápido como el control de los factores de un número con 1/3 del número de dígitos IIRC).

Answer 5

Esas fórmulas no nos ayudan a demostrar nada de uso. Por ejemplo, puede usar esas fórmulas que se derivan del teorema de Dirichlet (que cada progresión aritmética $ax+b$ donde $\gcd(a,b)=1$ tiene un número infinito de números primos)*? No. Esas fórmulas no hacer que sea más fácil a todos.

*Es muy difícil teorema a demostrar.

También hay un montón de conjeturas (tales como la Bunyakovsky conjetura) que actualmente están sin resolver, y esas fórmulas no hacer que sea más fácil para nosotros para resolverlos.