Construcción de números primos

Question

La prueba clásica de la infinitud de los números primos consiste en tomar el $k$ primeros números primos $p_1,\ldots,p_k$ para formar $$n_k:=1+p_1\cdots p_k.$$ Entonces $n_k$ tiene un factor primo, que no es ninguno de los $p_j$ .

Obsérvese que se podría formar en su lugar el número $$n_{k,I}:=\prod_{i\in I}p_i+\prod_{j\not\in I}p_j$$ donde $I$ es cualquier subconjunto de $[1,\ldots,k]$ (tenemos $n_k=n_{k,\emptyset}$ ), o incluso $$m_{k,I}:=\prod_{i\in I}p_i-\prod_{j\not\in I}p_j,$$ siempre que este número no sea $\pm1$ .

Esto sugiere la siguiente construcción de números primos $q_k$ por inducción. S $k=1$ y $q_1=2$ . En el paso $k$ forman los números $$M_{k,I}:=\left|\prod_{i\in I}q_i-\prod_{j\not\in I}q_j\right|.$$ Entonces $q_{k+1}$ es el menor de los factores primos de todos estos números (es decir, de su producto como $I$ recorre los subconjuntos de $[1,\ldots,k]$ ).

¿Es cierto que $q_k=p_k$ para todos $k$ ? En caso negativo, ¿cubre la secuencia todos los números primos? Si no es así, ¿a qué velocidad aumenta esta secuencia a medida que $k\rightarrow+\infty$ ?

Se podría ampliar la construcción teniendo en cuenta las cifras $M_{k,I}$ y $$N_{k,I}:=\prod_{i\in I}q_i+\prod_{j\not\in I}q_j,$$ pero son mucho más grandes.

Answer 1

Se puede obtener una imagen heurística completa de lo que ocurre, suponiendo que los residuos cuadráticos (como sugiere Laurent) son el único obstáculo probable para obtener el siguiente primo. Más concretamente, si se deja que $Q_n = \prod_{k \le n} q_k$ sea el producto de todos los primos descubiertos hasta ahora, entonces se puede dejar que $p_{n+1} = p$ sea el primer primo restante tal que $Q_n$ es un residuo cuadrático mod $p$ asumiendo la primera propuesta de Denis. O, asumiendo la segunda propuesta de Denis, puedes dejar que $p$ sea el primer primo restante tal que $Q_n$ o $-Q_n$ es un residuo cuadrático mod $p$ . (Por tanto, será simplemente el siguiente primo si ese primo resulta ser 3 mod 4.) O, suponiendo que sólo se utilice la fórmula de la suma, sólo habría que comprobar $-Q_n$ . Entonces, experimentalmente, $q_{n+1} = p_{n+1}$ en los tres casos.

Aquí se describe la secuencia que obtuvo Charles, que yo también obtuve (al menos la primera mitad) con un programa de Sage.

qseq = [2]
for z in range(16):
    attain = set(); Q = prod(qseq)
    prediction = [p for p in list(primes(500)) if not p in qseq and
        (legendre_symbol(-1,p) == -1 or legendre_symbol(Q,p) == 1)][0]

    for S in Combinations(qseq):
        A = prod(S); attain.update([abs(A-Q/A),A+Q/A])

    best = 10000
    attain.discard(1)
    best = min([min(factor(m))[0] for m in attain])
    print prediction,':',qseq,'->',best
    qseq.append(best)

Suponiendo que se utilicen tanto la suma como la diferencia, la validez de esta predicción se reduce a lo siguiente: Si $p$ es este próximo primo, entonces la pregunta es si $1$ aparece en el conjunto producto de los subconjuntos $\{q_k,1/q_k\}$ y $\{\pm 1\}$ en el grupo multiplicativo $(\mathbb{Z}/p)^*$ . Esta es una pregunta en teoría aditiva de conjuntos si se toma un logaritmo formal y se pasa al grupo aditivo $\mathbb{Z}/(p-1)$ . Una conjetura razonable es que estás convolucionando un montón de subconjuntos que no se acercan a estar en un subgrupo de $\mathbb{Z}/(p-1)$ por lo que puede esperar $0$ que aparezca en la suma. La heurística tiene un margen tan grande que puede que con los métodos existentes sea posible demostrar que siempre es así.

La otra parte de la cuestión es cuánto te desvías de ver los primos en orden. De nuevo, utilizando una heurística de la aleatoriedad en la teoría de números, la "probabilidad" de que un primo $p$ se saltará en una etapa dada es 1/2 (suponiendo que es 1 mod 4 en el segundo caso). Por tanto, se espera que el primer primo omitido se incluya finalmente con una "vida media" de una ronda. Por lo tanto, se espera que la secuencia sólo se sitúe ligeramente por delante de la lista de primos, y se espera que $q_n$ ser el $n$ infinitamente a menudo.

Answer 2

Para la variante que permite M y N, obtengo

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 29, 37, 43, 47, 41, 59, 61, 53, 67, 71, 79, 83, 73, 101, 89, 103, 107, 97, 109, 113, 127, 131, 139, 151, 149, ...

que, sorprendentemente, dista mucho de contener los primos en orden, como cabía esperar (salvo una o dos excepciones, como A063884 ). ¿Podría alguien comprobarme estos cálculos?

Posiblemente relevante:

R. K. Guy, C. B. Lacampagne y J. L. Selfridge, "Primes at a glance", Matemáticas del cálculo 48 :177 (1987), pp. 183-202.

Answer 3

Tal vez podrias tomar los primos de los productos en cualquier potencia que quieras, es un pensamiento que tuve antes de algunos años y es tambien una pregunta natural que uno puede hacer leyendo la prueba de Euclides ya que todavia la diferencia de los productos no es divisible por ninguno de estos primos ¿tomas de esta manera siempre el siguiente primo?