Nachweis der (In-) Traktabilität dieser N-ten Hauptrezidivfolge

Wie aus meiner vorherigen Frage hervorgeht , habe ich mit der Riemannschen Hypothese als Frage der Freizeitmathematik gespielt. Dabei bin ich zu einer interessanten Wiederholung gekommen und bin gespannt auf seinen Namen, seine Verringerungen und seine Fähigkeit, die Lücke zwischen Primzahlen zu schließen.

Um genau zu sein, wir können die Lücke zwischen jeder Primzahl als eine Wiederholung der vorhergehenden Kandidatenprimzahlen definieren . Für unsere Basis von wäre zum Beispiel die nächste Primzahl:$p_0 = 2$

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

Oder, wie wir sehen, indem wir dies zeichnen : .$p_1 = 3$

Wir können den Prozess für Primzahlen wiederholen, indem wir jede Kandidat-Primzahl bewerten, die sich vorwärts wiederholt. Angenommen, wir möchten die nächste Primzahl . Unsere Kandidatenfunktion wird:p $n$$p_2$

$\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}$

Wo:

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

Es ist leicht zu erkennen, dass jede Komponentenfunktion bei ganzzahligen Werten nur Null wird, und es ist ebenso leicht zu zeigen, wie dies unsere AND- und XOR-förmigen Beziehungen geschickt erfasst, indem die Eigenschaften der Addition und Multiplikation im Kontext eines trigonometrischen Systems ausgenutzt werden Gleichungen.

Die Wiederholung wird:

$\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\}$

... wo das gesamte Problem davon abhängt, ob wir den Operator über diese Funktion in Polynomialzeit auswerten können . Dies ist im Endeffekt eine Verallgemeinerung des Siebs von Eratosthenes .$\min$

Arbeitender Python-Code, um die Wiederholung zu demonstrieren:

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

Ein kurzes Beispiel:

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

Das Problem ist, dass ich jetzt sowohl als Mathematiker als auch als Informatiker über den Kopf komme. Insbesondere bin ich mit der Fourier-Analyse , der Definition von einheitlichen Deckungen oder der komplexen Ebene im Allgemeinen nicht kompetent , und ich bin besorgt, dass dieser Ansatz entweder völlig falsch ist oder einen lauernden Schrecken vor einem 3SAT-Problem verbirgt, das ihn in die Höhe treibt NP-Vollständigkeit.

Daher habe ich hier drei Fragen:

1. Ist es angesichts meiner knappen Wiederholung oben möglich, die Position der Nullen in Zeit und Raum des Polynoms deterministisch zu berechnen oder zu schätzen?
2. Wenn ja, oder wenn nicht, verbirgt es irgendwelche anderen Unterprobleme, die eine Polytime- oder Polyspace-Lösung unlösbar machen würden?
3. Und wenn durch ein Wunder (1) und (2), welche dynamischen Programmierverbesserungen würden Sie machen, um diese Wiederholung von einem hohen Niveau aus zu erfüllen? Es ist klar, dass die Iteration derselben ganzen Zahlen durch mehrere Funktionen unelegant und ziemlich verschwenderisch ist.

Das folgende Papier zeigt, dass PRIMES in P ist (es wurde auch 2006 mit einem Gödel-Preis ausgezeichnet):

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

Wenn Sie die Lösung der N-ten Prim-Minimierungsprozedur auf den AKS-PRIMES-Algorithmus setzen (Modulo-A-Subtraktion), erhalten Sie möglicherweise eine nachvollziehbare Lösung für die Wiederholungsrelation (wenn Sie nachweisen können, dass die Primlücke durch die Wiederholungsrelation gegeben ist).

Quellcodes finden Sie im Internet. Ich zeige hier nicht auf sie, weil ich sie nicht persönlich überprüft habe.

Möglicherweise haben wir jedoch noch die Obergrenze von um alle Zahlen zu überprüfen ...$\sqrt{n}$