Probar la (in) trazabilidad de esta enésima recurrencia principal

18

Como se desprende de mi pregunta anterior , he estado jugando con la hipótesis de Riemann como una cuestión de matemática recreativa. En el proceso, he llegado a una recurrencia bastante interesante, y tengo curiosidad por su nombre, sus reducciones y su capacidad de seguimiento hacia la capacidad de solución de la brecha entre los números primos.

Hablando en términos generales, podemos definir la brecha entre cada número primo como una recurrencia de primos candidatos anteriores . Por ejemplo, para nuestra base de p0=2 , el siguiente primo sería:

p1=min{x>p0cos(2π(x+1)/p0)+1=0)}

O, como vemos al trazar esto : .p1=3

Podemos repetir el proceso para norte primos evaluando cada candidato primario recurrente hacia adelante. Supongamos que queremos obtener el próximo primo, pag2 . Nuestra función candidata se convierte en:

p2=min{x>p1fp1(x)+((cos(2π(x+1)/p1)+1)(cos(2π(X+2)/ /pag1)+1))=0 0}

Dónde:

Fp1(X)=-cos(2π(X+1)/ /pag0 0)+1 , como arriba.

Es fácil ver que cada función de componente solo se convierte en cero en los valores enteros, y es igualmente fácil mostrar cómo esto captura nuestras relaciones en forma de AND y XOR de manera inteligente, explotando las propiedades de suma y multiplicación en el contexto de un sistema trigonométrico ecuaciones

La recurrencia se convierte en:

Fpag0 0=0 0pag0 0=2Fpagnorte(X)=Fpagnorte-1(X)+k=2pagnorte-1(-cos(2π(X+k-1)/ /pagnorte-1)+1)pagnorte=min{X>pagnorte-1Fpagnorte(X)=0 0}

... donde todo el problema depende de si podemos evaluar el operador min sobre esta función en tiempo polinómico. Esto es, en efecto, una generalización del Tamiz de Eratóstenes .

Código de Python de trabajo para demostrar la recurrencia:

from math import cos,pi

def cosProduct(x,p):
    """ Handles the cosine product in a handy single function """
    ret = 1.0
    for k in xrange(2,p+1):
        ret *= -cos(2*pi*(x+k-1)/p)+1.0
    return ret

def nthPrime(n):
    """ Generates the nth prime, where n is a zero-based integer """

    # Preconditions: n must be an integer greater than -1
    if not isinstance(n,int) or n < 0:
        raise ValueError("n must be an integer greater than -1")

    # Base case: the 0th prime is 2, 0th function vacuous
    if n == 0:
        return 2,lambda x: 0

    # Get the preceding evaluation
    p_nMinusOne,fn_nMinusOne = nthPrime(n-1)

    # Define the function for the Nth prime
    fn_n = lambda x: fn_nMinusOne(x) + cosProduct(x,p_nMinusOne)

    # Evaluate it (I need a solver here if it's tractable!)
    for k in xrange(p_nMinusOne+1,int(p_nMinusOne**2.718281828)):
        if fn_n(k) == 0:
            p_n = k
            break

    # Return the Nth prime and its function
    return p_n,fn_n

Un ejemplo rápido:

>>> [nthPrime(i)[0] for i in range(20)]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

El problema es que ahora estoy muy por encima, tanto matemáticamente como informático. Específicamente, no soy competente con el análisis de Fourier , con la definición de cubiertas uniformes , o con el plano complejo en general, y me preocupa que este enfoque sea totalmente incorrecto u oculte el horror al acecho de un problema de 3SAT que lo eleva a NP-completitud.

Por lo tanto, tengo tres preguntas aquí:

  1. Dada mi breve recurrencia anterior, ¿es posible calcular o estimar determinísticamente la ubicación de los ceros en el tiempo y el espacio polinomiales?
  2. Si es así o si no, ¿está ocultando otros subproblemas que harían que una solución polytime o polyspace sea intratable?
  3. Y si por algún milagro (1) y (2) se mantienen, ¿qué mejoras dinámicas de programación harías para satisfacer esta recurrencia, desde un nivel alto? Claramente, la iteración sobre los mismos enteros a través de múltiples funciones es poco elegante y bastante derrochadora.
MrGomez
fuente
Y para aquellos que todavía están aquí a pesar de mi muro de texto: no estoy seguro de si esto se reduce a la zeta de Riemann, lo que le da la misma complejidad. Sin embargo, no creo que lo haga.
MrGomez
1
1) ¿Qué etiquetas te gustaría? Puede crearlos usted mismo simplemente usándolos. 2) Por favor, dé una definición general para , es decir, ¿qué es ? 3) Si no obtiene una respuesta sobre esto después de una semana más o menos, es posible que desee moverlo de manera tan teórica. FF(pagnorte)
Raphael
1
No estoy siguiendo todo en tu publicación. Supongo que te refieres a NP completo, no NP. En general, demostrar que una función teórica de números es NP-completa es una tarea bastante difícil ya que a menudo carecen / ocultan cualquier estructura combinatoria que nos permita diseñar dispositivos para la reducción.
Kaveh
1
Revisión completa. Seguramente habrá otros problemas al acecho, pero mi representación original estaba bastante fuera de lugar. Debería consultar con mi yo 24 horas más joven y darle un repaso sobre las definiciones adecuadas deF(X) . En cualquier caso, gracias por su paciencia y sus ediciones hasta ahora. Las etiquetas actuales también están ahora a mi entera satisfacción. :)
MrGomez
F

Respuestas:

1

El siguiente documento muestra que PRIMES está en P (también ganó un premio Gödel en 2006):

http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf

Al establecer la solución del procedimiento de minimización de enésima enésima en el algoritmo AKS PRIMES (módulo a resta), podemos obtener efectivamente una solución manejable para la relación de recurrencia (si puede probar que la relación de recurrencia proporciona el espacio de primo).

Los códigos fuente se pueden encontrar en internet. No los estoy señalando aquí porque no los revisé personalmente.

norte

usuario13675
fuente
1
La página de Rosettacode está completamente mal nombrada. Esta no es la prueba de primalidad AKS, y es una reexpresión de la división de prueba por todos los enteros menores que n. Por otro lado, vale la pena hacer notar que la primalidad está en P y ver si eso arroja alguna luz sobre la pregunta original.
DanaJ
Buen punto ... lo arreglaré ...
user13675
1
nortelgnorte