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

18

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:p0=2

p1=min{X>p0-cos(2π(X+1)/p0)+1=0)}

Ou, comme nous le voyons en traçant ceci : p1=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, p2 . Notre fonction candidate devient:

p2=min{X>p1Fp1(X)+((-cos(2π(X+1)/p1)+1)(-cos(2π(X+2)/p1)+1))=0}

Où:

Fp1(X)=-cos(2π(X+1)/p0)+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:

fp0=0p0=2fpn(x)=fpn1(x)+k=2pn1(cos(2π(x+k1)/pn1)+1)pn=min{x>pn1fpn(x)=0}

... 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.
MrGomez
la source
Et pour ceux qui sont toujours là malgré mon mur de texte: je ne sais pas si cela se réduit à la zêta de Riemann, lui donnant ainsi la même complexité. Je ne pense pas que ce soit le cas, cependant.
MrGomez
1
1) Quelles balises aimeriez-vous? Vous pouvez les créer vous-même en les utilisant simplement. 2) Veuillez donner une définition générale de , c'est-à-dire qu'est-ce que ? 3) Si vous n'obtenez pas de réponse à ce sujet après une semaine ou deux, vous voudrez peut-être le déplacer de façon cstheory.SE. FF(pn)
Raphael
1
Je ne suis pas tout suivre dans votre message. Je suppose que vous voulez dire NP-complet et non NP. Prouver généralement qu'une fonction théorique des nombres est NP-complète est une tâche assez difficile car ils manquent / cachent souvent toute structure combinatoire qui nous permettrait de concevoir des gadgets pour la réduction.
Kaveh
1
Révision terminée. Il y a certainement d'autres problèmes qui se cachent, mais ma représentation d'origine était tout à fait hors de propos. Je devrais consulter mon moi de 24 heures plus jeune et lui donner un rappel sur les définitions appropriées de . En tout cas, merci pour votre patience et vos retouches jusqu'à présent. Les balises actuelles sont également maintenant à ma satisfaction. :)F(X)
MrGomez
Concernant , ne suffit-il pas de "vérifier" tous les plus petits nombres premiers par opposition à tous les plus petits nombres? F
Raphael

Réponses:

1

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.

n

user13675
la source
1
La page Rosettacode est complètement mal nommée. Ce n'est pas le test de primalité AKS, et c'est un retraitement de la division d'essai par tous les entiers inférieurs à n. D'un autre côté, noter que la primauté est en P et voir si cela éclaire la question d'origine mérite d'être demandé.
DanaJ
Bon point ... je vais arranger ça ...
user13675
1
nlgn