¿Cuál es la historia del resultado que $p_{n+1} < p_n^2$ ¿Y qué dificultad tiene la prueba?

Question

En la monografía de Edsger Dijkstra "Notes on Structured Programming", describe un sencillo programa imperativo para generar una matriz de la primera $n$ primos. Para cada primo $p_n$ encuentra el siguiente primo comprobando cada impar $j \gt p_n$ para ver si tiene un divisor primo $d$ en la gama $2 \lt d \le \sqrt j$ . El algoritmo extrae estos candidatos de la matriz de números primos que ha ido construyendo, que en cualquier iteración contiene los primos comprendidos entre $2$ y $p_n$ inclusivo, por lo que hay una suposición implícita es que $\sqrt j \le p_n$ (el algoritmo itera sobre la matriz de primos hasta $p_n$ siendo las únicas condiciones de terminación $d|j$ o $d > \sqrt j$ por lo que si $\sqrt j$ podría ser $\ge p_n$ corremos el riesgo de leer más allá del final de la matriz). Citando a Dijkstra:

Con toda humildad cito el comentario de Don Knuth sobre una versión anterior de este programa, en la que daba por sentado este hecho:

"¡Aquí es usted culpable de una grave omisión! Su programa hace uso de un profundo resultado de la teoría de números, a saber, que si $p_n$ denota el $n$ ésimo número primo siempre tienen $p_{n+1} < p_n^2$ ."

Así que tengo curiosidad por conocer la historia de este "resultado profundo" y la dificultad de su demostración.

Answer 1

No estoy seguro de esa prueba en particular, pero conozco algunas pruebas de Postulado de Bertrand . Bertrand dice que para todos $n > 3$ hay un primo entre $n$ y $2n$ . En particular, esto significa que dado un primo $p_0$ hay otro primo $p_1$ s.t. $p_0 < p_1 < 2p_0$ En $2 < p_0$ tenemos entonces que existe un $p_1$ s.t.

$$p_0 < p_1 < 2p_0 < p_0 ^2$$

Creo que el Prueba de Wikipedia no está tan mal. De hecho, Bertrand demostró su conjetura él mismo a finales del siglo XIX, y hay muchas pruebas. Ramanujan hizo una, Erdos la mejoró. También hay muchos mejores resultados y resultados asintóticos - He utilizado la mejora de Pierre Dusart antes, que dice que para x suficientemente grande (mayor que 3275), hay un primo entre $x$ y $x + \dfrac{x}{1 + 2\log^2 x}$ . ¡Eso es muy intenso!

Pero esa idea es algo profunda, y está relacionada con el Teorema de los Números Primos sobre la distribución de los primos (que yo calificaría de muy profunda).

Answer 2

En realidad, el programa descrito no requiere tal suposición. Recuerde que parte del último primo encontrado hasta el momento y comprueba cada (impar) a su vez para ver si es compuesto; por lo tanto, el primer número no compuesto así encontrado debe sea el próximo primo.

La comprobación de la primalidad se basa simplemente en el siguiente resultado bastante trivial:

Lema: Todo número compuesto es divisible por algún primo no mayor que su raíz cuadrada.

Prueba: Tenemos que demostrar que cada número compuesto debe tener un divisor (posiblemente no primo) no mayor que su raíz cuadrada; este divisor debe entonces tener un factor primo no mayor que él mismo. Para demostrarlo, supongamos lo contrario, es decir, que existe un número compuesto $n$ tal que su divisor propio más pequeño $k$ satisface $k > \sqrt n$ . Pero entonces $n/k < \sqrt n$ también es divisor de $n$ que es una contradicción.

---

Edito: Perdón, ahora veo mi error. Efectivamente no es trivial demostrar que el programa nunca leerá más allá del final de la lista de primos si eso no se comprueba. Dejaré mi respuesta para que quede constancia de la conversación, pero la marcaré como wiki de la comunidad. Por favor, no lo upvote.