Prouver la (in) tractabilité de cette Nième récurrence première

Comme suit de ma question précédente , j'ai joué avec l' hypothèse de Riemann comme une question de mathématiques récréatives. Dans le processus, je suis arrivé à une récurrence assez intéressante, et je suis curieux de son nom, de ses réductions et de son aptitude à la solvabilité de l'écart entre les nombres premiers.

D'une manière générale, nous pouvons définir l' écart entre chaque nombre premier comme une récurrence des nombres premiers candidats précédents . Par exemple, pour notre base de , le premier premier serait:$p_0 = 2$

$\qquad \displaystyle p_1 = \min \{ x > p_0 \mid -\cos(2\pi(x+1)/p_0) + 1 = 0) \}$

Ou, comme nous le voyons en traçant ceci : $p_1 = 3$ .

On peut répéter le processus pour $n$ nombres premiers en évaluant chaque premier candidat candidat récurrent. Supposons que nous voulons obtenir le prochain nombre premier, $p_2$ . Notre fonction candidate devient:

$\qquad \displaystyle \begin{align} p_2 = \min\{ x > p_1 \mid f_{p_1}(x) + (&(-\cos(2\pi(x+1)/p_1) + 1) \\ \cdot &(-\cos(2\pi(x+2)/p_1) + 1)) = 0\} \end{align}$

Où:

$\qquad \displaystyle f_{p_1}(x) = -\cos(2\pi(x+1)/p_0) + 1$ , comme ci-dessus.

Il est facile de voir que chaque fonction de composant ne devient nulle que sur des valeurs entières, et il est tout aussi facile de montrer comment cela capture intelligemment nos relations en forme ET et XOR, en exploitant les propriétés d'addition et de multiplication dans le contexte d'un système de trigonométrie équations.

La récurrence devient:

$\qquad f_{p_0} = 0\\ \qquad p_0 = 2\\ \qquad \displaystyle f_{p_n}(x) = f_{p_{n-1}}(x) + \prod_{k=2}^{p_{n-1}} (-\cos(2\pi(x+k-1)/p_{n-1}) + 1)\\ \qquad \displaystyle p_n = \min\left\{ x > p_{n-1} \mid f_{p_n}(x) = 0\right\}$

... où tout le problème dépend de la possibilité d'évaluer l' opérateur $\min$ sur cette fonction en temps polynomial. Il s'agit, en effet, d'une généralisation du Tamis d'Ératosthène .

Code Python fonctionnel pour démontrer la récurrence:

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 exemple rapide:

>>> [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]

Le problème, c'est que je suis en train de dépasser ma tête, à la fois mathématiquement et en tant qu'informaticien. Plus précisément, je ne suis pas compétent avec l'analyse de Fourier , avec la définition de couvertures uniformes , ou avec le plan complexe en général, et je crains que cette approche soit complètement fausse ou cache une horreur cachée d'un problème 3SAT qui l'élève à NP-complétude.

Ainsi, j'ai trois questions ici:

1. Étant donné ma récurrence laconique ci-dessus, est-il possible de calculer ou d'estimer de façon déterministe l'emplacement des zéros dans le temps et l'espace polynomial?
2. Si oui ou non, cache-t-il d'autres sous-problèmes qui rendraient intraitable une solution de polytime ou de polyspace?
3. Et si, par miracle (1) et (2), quelles améliorations dynamiques de programmation apporteriez-vous pour satisfaire cette récurrence, à partir d'un niveau élevé? De toute évidence, l'itération sur les mêmes nombres entiers via plusieurs fonctions est inélégante et assez inutile.

L'article suivant montre que PRIMES est en P (il a également remporté un prix Gödel en 2006):

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

En définissant la solution de la procédure de minimisation Nth prime à l'algorithme AKS PRIMES (modulo une soustraction), nous pouvons effectivement obtenir une solution traitable à la relation de récurrence (si vous pouvez prouver que l'écart principal est donné par la relation de récurrence).

Les codes sources peuvent être trouvés sur Internet. Je ne les désigne pas ici parce que je ne les ai pas vérifiés personnellement.

$\sqrt{n}$