¿Es el notorio $n^2 + n + 41$ ¿Generador primario el último de su tipo?

Question

El polinomio $n^2+n+41$ es famoso por tomar valores primos para todos los $0\le n\lt 40$ . He leído que esto está estrechamente relacionado con el hecho de que 163 es un número de Heegner, aunque no entiendo el argumento, salvo que el discriminante de $n^2+n+41$ es $-163$ . El siguiente número más pequeño de Heegner es el 67, y de hecho $n^2+n+17$ muestra el mismo comportamiento, tomando valores primos para $0\le n\lt 16$ .

Pero 163 es el mayor número de Heegner, lo que sugiere que esta es la última coincidencia de este tipo, y que podría no haber ninguna $k>41$ tal que $n^2+n+k$ adquiere una secuencia ininterrumpida de valores primos.

¿Es este el caso? Si no es así, ¿por qué no?

En segundo lugar, ¿hay una $k>41$ , tal vez extremadamente grande, de manera que $n^2+n+k$ adquiere valores primos para $0<n<j$ para algunos $j>39$ ?

Answer 1

Ver http://en.wikipedia.org/wiki/Heegner_number#Consecutive_primes

Aquí está un artículo más largo que Rabinowitz publicó sobre el tema a continuación

Rabinowitz demostró, en 1913, que $x^2 + x + p$ representan el máximo número de primos consecutivos si y sólo si $x^2 + x y + p y^2$ es la única (clase de equivalencia de) forma cuadrática binaria positiva de su discriminante. Esta condición se llama "clase número uno". Para los discriminantes negativos, el conjunto de tales discriminantes es finito, llamado números de Heegner.

Obsérvese que si tomamos $x^2 + x + ab$ para que el término constante sea compuesto, obtenemos un resultado compuesto tanto para $x=a$ y $x=b,$ por lo que la cosa se apaga antes de tiempo. En los términos de Rabinowitz, también tendríamos la forma $a x^2 + x y + b y^2,$ que sería una "clase" distinta en el mismo discriminante, violando así la clase número uno. Así que todo encaja. Es decir, se "reduce" si $0 < a \leq b,$ y distinta de la forma principal si también $a > 1.$

Para las formas binarias, me gusta especialmente Buell, aquí está su página sobre la clase número uno: BUELL . Lo hace todo en términos de formas binarias, pero también da la relación con los campos cuadráticos. Además, permite tanto las formas positivas como las indefinidas y, por último, permite el uso de impar $b$ en $a x^2 + b x y + c y^2.$ Nótese que a menudo he respondido a preguntas de MSE sobre ideales en campos cuadráticos con estas técnicas, que son, sencillamente, fáciles. Además, muestra la forma correcta de hacer la ecuación de Pell y sus variantes como algoritmos, que la gente parece entender mal a menudo. Aquí me refiero al método de Lagrange principalmente.

EEDDIITT: Decidí averiguar la dirección más fácil del resultado de Rabinowitz en mi propio idioma. Así que empezamos con la forma principal, $\langle 1,1,p \rangle$ con algún primo $p \geq 3. $ De ello se desprende que $2p-4 \geq p-1$ y $$ p-2 \geq \frac{p-1}{2}. $$ Ahora, supongamos que tenemos otra forma reducida, distinta, del mismo discriminante, $$ \langle a,b,c \rangle. $$ No hay pérdida de generalidad al exigir $b > 0.$ Así que reducido significa $$ 1 \leq b \leq a \leq c $$ con $b$ impar, ambos $a,c \geq 2,$ y $$ 4ac - b^2 = 4 p - 1. $$ Como $b^2 \leq ac,$ encontramos $3 b^2 \leq 4p-1 $ y, como $p$ es positivo, $ b \leq p.$

Ahora, define $$ b = 2 \beta + 1 $$ o $ \beta = \frac{b-1}{2}. $ Desde antes tenemos $$ \beta \leq p-2. $$ Sin embargo, desde $4ac - b^2 = 4p-1$ obtenemos $4ac+1 = b^2 + 4 p,$ entonces $ 4ac + 1 = 4 \beta^2 + 4 \beta + 1 + 4 p, $ entonces $4ac = 4 \beta^2 + 4 \beta + 4 p, $ entonces $$ ac = \beta^2 + \beta + p, $$ con $0 \leq \beta \leq p-2.$ Es decir, la presencia de una segunda clase de equivalencia de formas ha obligado a $x^2 + x + p$ para representar un número compuesto ( $ac$ ) con un valor pequeño $ x = \beta \leq p-2,$ interrumpiendo así la supuesta secuencia de primos. $\bigcirc \bigcirc \bigcirc \bigcirc \bigcirc$

EEDDIITTEEDDIITT: Debo señalar que los discriminantes en cuestión deben ser realmente discriminantes de campo, ciertas cosas deben ser libres de cuadrados. Si empiezo con $x^2 + x + 7,$ los relacionados $x^2 + x y + 7 y^2$ del discriminante $-27$ es de la clase número uno, pero existe la forma imprimible $ \langle 3,3,3 \rangle $ con el mismo discriminante. Entonces, como en el caso anterior, vemos que $x^2 + x + 7 = 9$ con $x=1 =(3-1)/2.$

[ Rabinowitz, G. "Unicidad de la descomposición en factores primos en campos numéricos cuadráticos". Proc. Fifth Internat. Congreso de Matemáticas. (Cambridge) 1 , 418-421, 1913. ]

Editar 30 de octubre de 2013. Alguien ha preguntado en la pregunta borrada El menor número entero positivo $n$ f(n) = $n^2 + n + 41$ ¿es compuesto? sobre la otra dirección en Rabinowitz (1913), y un poco de toqueteo reveló que también sé cómo hacerlo. Tenemos una forma principal positiva $$ \langle 1,1,p \rangle $$ donde $$ - \Delta = 4 p - 1 $$ también es primo. En caso contrario, hay un segundo género, a menos que $ - \Delta = 27 $ o $ - \Delta = 343 $ o una potencia prima similar, lo cual es un problema que voy a ignorar; nuestro discriminante es menos un primo, $ \Delta = 1- 4 p . $

Nos interesa la posibilidad de que $n^2 + n + p$ es compuesto para $0 \leq n \leq p-2.$ Si es así, que $q$ sea el primo más pequeño que divide a dicho número compuesto. Tenemos $n^2 + n + p \equiv 0 \pmod q.$ Esto significa que $(2n+1)^2 \equiv \Delta \pmod q,$ para que sepamos $\Delta$ es un residuo cuadrático. Siguiente $n^2 + n + p \leq (p-1)^2 + 1.$ Por lo tanto, el factor primo más pequeño es menor que $p-1,$ y $q < p,$ así que $q < - \Delta.$

Veamos, las dos raíces de $n^2 + n + p \pmod q$ suman $q-1.$ Se puede confirmar que si $m = q-1-n,$ entonces $m^2 + m + p \equiv 0 \pmod q.$ Sin embargo, no podemos tener $n = (q-1)/2$ con $n^2 + n + p \pmod q,$ porque eso implica $\Delta \equiv 0 \pmod q,$ y tuvimos cuidado de hacer $- \Delta$ primo, con $q < - \Delta.$ Por lo tanto, hay dos valores distintos de $n \pmod q,$ los dos valores suman $q-1.$ Como resultado, hay un valor de $n$ con $n^2 + n + p \equiv 0 \pmod q$ y $n < \frac{q-1}{2}.$

Utilizando la matriz de cambio de variable $$ \left( \begin{array}{cc} 1 & n \\ 0 & 1 \end{array}\right) $$ escrito a la derecha, encontramos que $$ \langle 1,1,p \rangle \sim \langle 1,2n+1,qs \rangle $$ donde $n^2 + n + p = q s,$ con $2n+1 < q$ y $q \leq s.$ Como resultado, la nueva forma $$ \langle q,2n+1,s \rangle $$ es del mismo discriminante pero ya está reducido, y por tanto no es equivalente a la forma principal. Así, el número de clase es mayor que uno.

Answer 2

Para responder a la segunda parte de su pregunta: El requisito de que $n^2+n+k$ sea primordial para $0\lt n\lt40$ define un primera constelación . El primera conjetura de Hardy-Littlewood , que se considera ampliamente probable, afirma que la densidad asintótica de las constelaciones de primos se predice correctamente mediante un modelo probabilístico basado en residuos distribuidos uniformemente de forma independiente con respecto a todos los primos. Aquí hay una sesión de Sage que calcula el coeficiente de su constelación de primos:

sage: P = Primes ();
sage: coefficient = 1;
sage: for i in range (0,10000) :
...       p = P.unrank (i);
...       if (p < 39^2 + 39) :
...           admissible = list (true for j in range (0,p));
...           for n in range (1,40) :
...               admissible [(n^2+n) % p] = false;
...           count = 0;
...           for j in range (0,p) :
...               if (admissible [j]) :
...                   count = count + 1;
...       else :
...           count = p - 39;
...       coefficient = coefficient * (count / p) / (1 - 1 / p)^39;
...
sage: coefficient.n ()
2.22848364649549e27

El cambio al duplicar el corte $10000$ está en el tercer dígito, por lo que el número de tales constelaciones primos hasta $N$ se espera que esté asintóticamente dada aproximadamente por $2\cdot10^{27}N/\log^{39}N$ . Esto es $1$ para $N\approx4\cdot10^{54}$ Aunque se espera que haya infinidad de ellos, es probable que tenga que buscar bastante para encontrar uno. No hay ninguno, excepto el de $k=41$ hasta $k=1000000$ :

sage: P = Primes ();
sage: for k in range (0,1000000) :
...       success = true;
...       for n in range (1,40) :
...           if not (n^2 + n + k) in P :
...               success = false;
...               break;
...       if success :
...           print k;
41

Answer 3

Si permitimos el polinomio más general $an^2+bn+c$ entonces,

$$P(n) = 9n^2-163\,(3n-41)$$

también toma valores primos para TODOS $1\leq n \leq 40$ . Esto se puede derivar del polinomio de Euler, pero tiene una secuencia de $40$ primos que comienzan y terminan de forma diferente a la suya.

Answer 4

Sí, a continuación está el resultado clave.

Teorema $ $ $\rm\ (x\!-\!\alpha)\:(x\!-\!\alpha') = x^2\! + x + k\ $ es primordial para $\rm\, 0 \le x \le k\!-\!2 \iff \mathbb Z[\alpha]\, $ es un PID

Sugerencia $\, (\Rightarrow)\ $ Mostrar todos los primos $\rm\ p \le \sqrt{n},\; n = 1\!-\!4k\ $ satisfacer $\rm\ (n/p) = -1\ $ por lo que ninguna división/ramificación

Para las pruebas, véase, por ejemplo, Cohn, Teoría avanzada de los números , pp. 155-156, o Ribenboim, Mis números, mis amigos , 5.7 p.108. Obsérvese que ambas pruebas emplean el límite $\rm\ p < \sqrt{n}\ $ sin mencionar explícitamente que se trata de una consecuencia del límite de Minkowski -suponiendo, presumiblemente, que es obvio para el lector basándose en los resultados anteriores. Por lo tanto, tendrá que leer las secciones anteriores sobre el límite de Minkowski. Compara Stewart y Tall, Teoría algebraica de los números y FLT , 3ed, Teorema 10.4 p.176 donde se menciona explícitamente el uso del límite de Minkowski.

Como alternativa, véase el programa autónomo papel [1] que procede de forma un poco más sencilla, empleando la aproximación de Dirichlet para obtener una generalización del algoritmo euclidiano (el criterio Dedekind-Rabinowitsch-Hasse para un PID). Si la memoria no me falla, esto se aproxima al enfoque empleado originalmente por Rabinowitsch cuando publicó por primera vez este teorema en 1913.

[1] Daniel Fendel, Polinomios productores de primos y dominios ideales principales,
Revista de Matemáticas, Vol. 58, 4, 1985, 204-210

Answer 5

Véase también la página de Mathworld "Polinomio generador de primas" http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html