Infinitos primos de la forma $2^n+c$ como $n$ ¿varía?

Question

En el momento de escribir estas líneas, la pregunta 5191 está cerrada con la acusación de deberes. Pero no tengo ni idea de lo que pasa en esa pregunta (aparte de la parte 3) [Edit: Los comentarios de Anton en la 5191 aclaran al menos algunas de las cosas que pasan y merece la pena leerlos]. [Editar: las excelentes respuestas de FC demuestran que mi falta de conocimiento se debe simplemente a mi propia ignorancia], así que preguntaré algo relacionado.

Mi impresión es que generalmente se cree que hay infinitos primos de Mersenne, es decir, primos de la forma $2^n-1$ . Mi impresión es también que se sospecha que sólo hay un número finito de primos de Fermat, es decir, primos de la forma $2^n+1$ (un argumento heurístico se encuentra en la página de la wikipedia sobre los primos de Fermat). [EDIT: ¡en la página de Wikipedia también hay un argumento heurístico de que hay infinitos primos de Fermat!]

Así que básicamente voy a volver a preguntar algunas partes de la P5191, porque no sé cómo pedir que se reabra una pregunta de otra manera, además de algunas generalizaciones.

1) Para qué enteros de impar $c$ se conjetura generalmente que hay infinitos primos de la forma $2^n+c$ ? Por qué $c$ ¿se conjetura en general que sólo hay un número finito de ellas? ¿Para qué? $c$ ¿no tenemos idea de lo que hay que conjeturar? [Editar: FC nos ha mostrado que habrá un montón de $c$ para los que $2^n+c$ es (demostrablemente) primo sólo con una frecuencia finita. ¿Seguimos teniendo sólo una $c$ (a saber $c=-1$ ) para el que se cree generalmente que $2^n+c$ ¿es primo infinitamente a menudo?]

2) ¿Existe algún tipo de impar $c$ por lo que es una conjetura sensata que hay infinitas $n$ tal que $2^n+c$ y $2^{n+1}+c$ son simultáneamente primos? La misma pregunta para "finitely many $n$ ".

3) ¿Existen parejas $c,d$ de enteros Impares para los que es una conjetura sensata que $2^n+c$ y $2^n+d$ son simultáneamente primos con una frecuencia infinita? Lo mismo para "finitamente a menudo".

Answer 1

Buzzard tiene razón al ser escéptico con los argumentos más ingenuos: Erdos observó que $2^n + 9262111$ nunca es primo.

[ editar Ene 2017 por Buzzard: el 9262111 ha estado sentado aquí durante 7 años pero hay un desliz en las diapositivas de Pomerance donde calcula la solución CRT. La conclusión correcta de los argumentos de Pomerance es que $2^n+1518781$ nunca es primo. Gracias a Robert Israel por señalar que $2^{104}+9262111$ es primordial].

La primera pregunta es un problema increíblemente clásico, por supuesto. Obsérvese que la prueba de que $2^n + 3$ y $2^n + 5$ son ambos primos finitos puede funcionar plausiblemente para una sola expresión $2^n + c$ para ciertos $c$ . Basta con encontrar un conjunto finito de pares $(a,p)$ donde $p$ son primos distintos tales que cada número entero es congruente con $a$ modulo $p - 1$ para al menos un par $(a,p)$ . Entonces toma $-c$ para ser congruente con $2^{a}$ modulo $p$ . (Frase clave: cubrir las congruencias). Podría escribir algo más, pero realmente no puedo hacerlo mejor que la siguiente charla elemental muy agradable de Carl Pomerance:

www.math.dartmouth.edu/~carlp/PDF/covertalkunder.pdf

Al parecer, el cerebro colectivo de teoría de números de mathoverflow está rehaciendo conjeturas de hace 150 años que se sabe que son falsas desde hace más de 50 años. Iba a dejar que este post consistiera en la primera línea, pero supongo que hoy me siento generoso. Por otro lado, cada vez dudo más de que vaya a obtener una respuesta a pregunta 2339 .

Answer 2

Hay ciertamente (¡muchos!) pares de enteros $c$ , $d$ para lo cual es conocido que $2^n + c$ , $2^n + d$ no pueden ser simultáneamente primos con una frecuencia infinita -- toma $c = 1$ , $d = -1$ , por ejemplo, donde $2^n - 1$ sólo puede ser primo si $n$ es primo, pero $2^n + 1$ sólo puede ser primo si $n$ es una potencia de $2$ . Alternativamente, tomando todo $\bmod 3$ vemos que $c = -1$ , $d = 7$ sólo son simultáneamente primos en $n = 2$ .

Por lo tanto, hay muchos obstáculos locales para que estos pares sean simultáneamente primos, aunque probablemente no sean suficientes para descartar todos ellos, salvo un número finito.

[Editado porque es poco probable que esto quepa en un comentario]: Aquí hay un intento aproximado de una heurística muy básica (para la parte 1 y la parte 3) que no veo la manera de hacer que funcione realmente, pero tal vez alguien más lo haga...

Así que vamos a arreglar $c$ y considerar la $\bmod p$ comportamiento de $2^n + c$ para cada primo impar $p$ . Desde $2^n$ es periódico $\bmod p$ para grandes $n$ tenemos algunas clases de congruencia $\bmod {(p-1)}$ para lo cual $2^n + c$ es siempre compuesto. Para simplificar el análisis, podemos considerar únicamente el comportamiento en $p$ tal que $2$ es una raíz primitiva $\bmod p$ en cuyo caso hay exactamente una clase de congruencia $\bmod {(p-1)}$ por cada $p$ .

El problema ahora es que no hay una forma obvia de colar esto, ya que los primos menos uno no se comportan muy bien con respecto a la multiplicación. Mi corazonada inicial -que es sólo una corazonada, no respaldada por nada parecido a la lógica- es que genéricamente hablando, podríamos ver más o menos el mismo comportamiento que si tamizáramos por los primos, es decir, $2^n + c$ es coprima de todos los primos para los que $2$ es una raíz primitiva con probabilidad $1/\log n$ . Esto es mucho más grande de lo que predice la PNT, por supuesto, pero notablemente sigue siendo lo suficientemente pequeño como para que (asumiendo que mi cálculo de vuelta al sobre y mi corazonada salvajemente especulativa sean correctos) debamos esperar que $2^n + c$ , $2^n + d$ son típicamente primos simultáneos sólo finitamente a menudo.

[Edición 2]: Así que después de pensarlo un poco más veo donde mi corazonada está horriblemente, horriblemente equivocada, es decir, que no hay ninguna razón para creer que $a \equiv b \pmod {(p-1)}$ y $a \equiv d \pmod {(q-1)}$ tiene alguna solución. Pero sí sospecho que tenemos algunos "nuevos" exponentes prohibidos para casi todos los primos, lo que ::agita las manos vigorosamente:: sugiere que los valores de $n$ con $2^n + c$ primo tienen densidad $0$ y, en particular, probablemente tengan una densidad como máximo $O(1/\log n)$ que sigue siendo buena para una heurística para (3). ¿Puede alguien precisar esto?

Answer 3

Hola, espero no duplicar nada con lo que voy a escribir. Aquí va: Si uno considera la conjetura de Bateman-Horn, predice que $$ \sum_{n \leq x}\Lambda(f(n)) \sim \prod_p\left(\frac{p-n_p}{p-1}\right)x $$

donde $\Lambda(n)$ es la función de von Mangoldt y $n_p$ es el número de soluciones de la ecuación $f(n) \equiv 0 \bmod p$ en $\mathbb{Z}/p\mathbb{Z}$ . La razón de la forma de cada factor de Euler es la siguiente: Para cada $p$ Normalmente, hay $(p-1)/p$ posibilidad de no ser identificado por $p$ en los números enteros. Pero si el conjunto en consideración es la imagen del polinomio $f$ entonces la nueva probabilidad de no divisibilidad por $p$ es $(p-n_p)/p$ . Así que el factor de Euler es $((p-n_p)/p)/((p-1)/p) = (p-n_p)/(p-1)$ . Que el producto infinito sobre estos factores sea cero o no es como una competencia entre primos con $n_p=0$ y $n_p>1$ . Realmente depende de la densidad de estos primos con varios $n_p$ .

Por lo tanto, me gustaría saber si la conjetura de Bateman-Horn antes mencionada se puede generalizar a este caso de la siguiente manera(?): $$ \sum_{n \leq x}\Lambda(2^n+c) \sim \prod_p\left(\mbox{something}\right)x. $$

¿O hay alguna razón por la que la heurística para $2^n+c$ debe ser tratada de forma diferente a $f \in \mathbb{Z}[x]$ ?

Es interesante considerar algo análogo a $n_p$ en el caso de $2^n+c \equiv 0 \bmod p$ . Para $p|c$ tenemos $n_p=0$ desde $2^n$ nunca será $0 \bmod p$ . Para $p\nmid c$ hay que considerar el subgrupo cíclico $<2>$ generado por $2$ en $(\mathbb{Z}/p\mathbb{Z})^{*}$ . Sea $h$ sea el orden de este subgrupo. Tenemos $h | p-1$ . Sea $\delta_p = 1$ si $c \in <2>$ y $\delta_p=0$ de lo contrario.

Entonces, para cada $p$ números de la forma $2^n+c$ tienen probabilidad $$(\delta_p \times (p-1)/h)/(p-1) = \delta_p / h$$ de divisibilidad por $p$ . Por lo tanto, perhas el factor de Euler aquí debe ser (?) $$ \left(\frac{(h-\delta_p)/h}{(p-1)/p}\right). $$

Si se combina todo esto, ¿se puede conjeturar (?) $$ \sum_{n \leq x}\Lambda(2^n+c) \sim \prod_{p|c}\left(\frac{p}{p-1}\right)\prod_{p \nmid c}\left(\frac{(h-\delta_p)/h}{(p-1)/p}\right)x. $$

Gracias.

Answer 4

La conjetura ingenua para (2) y (3) sería que sólo hay un número finito de tales $n$ (a menos que $c=d$ ya que entonces (3) se convierte en (1)). La razón es que heurísticamente la "probabilidad" de que un número de orden $m$ es primo es aproximadamente $1/\log(m)$ y la suma $$\sum_n \frac{1}{\log(2^n+c)\log(2^n+d)}$$ converge.

Answer 5

Un enfoque heurístico podría ser examinar cuántos primos grandes se conocen para un determinado $c$ .

Una buena fuente es Probables Primas Top 10000

El formulario de búsqueda es aquí

Algunos resultados de la base de datos PRP Top 10000:

c largest-n number-of-primes-in-the-database:
3 479844 11
5 193965 4
7 566496 6
9 173727 6
11 345547 6
13 175628 2

Probablemente el esfuerzo computacional para diferentes $c$ en la base de datos es muy diferente.

La OEIS ha datos también.