Udowodnienie (nie) wykonalności tego N-tego pierwszego wznowienia

18

Jak wynika z mojego poprzedniego pytania , bawiłem się hipotezą Riemanna jako zagadnieniem matematyki rekreacyjnej. W trakcie tego procesu doszłam do dość interesującego nawrotu i jestem ciekawa jego nazwy, jej redukcji i podatności na rozwiązywanie luki między liczbami pierwszymi.

Krótko mówiąc, możemy zdefiniować odstęp między każdą liczbą pierwszą jako powtórzenie poprzednich liczb pierwszych kandydujących . Na przykład dla naszej podstawy p0=2) następną liczbą pierwszą będzie:

p1=min{x>p0-sałata(2)π(x+1)/p0)+1=0)}

Lub, jak widzimy, wykreślając to : .p1=3

Możemy powtórzyć ten proces dla liczb pierwszych, oceniając każdą kandydującą liczbę pierwszą powracającą do przodu. Załóżmy, że chcemy uzyskać następną pierwszą, . Nasza funkcja kandydacka staje się:p 2np2

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

Gdzie:

fp1(x)=cos(2π(x+1)/p0)+1 , jak wyżej.

Łatwo zauważyć, że każda funkcja składowa staje się zerowa na wartościach całkowitych, a równie łatwo jest pokazać, jak to sprytnie ujmuje nasze relacje w kształcie AND i XOR, wykorzystując właściwości dodawania i mnożenia w kontekście systemu trygonometrycznego równania.

Nawrót staje się:

fap0=0p0=2)fapn(x)=fapn-1(x)+k=2)pn-1(-sałata(2)π(x+k-1)/pn-1)+1)pn=min{x>pn-1fapn(x)=0}

... gdzie cały problem zależy od tego, czy możemy ocenić operatora na tej funkcji w czasie wielomianowym. Jest to w rzeczywistości uogólnienie sita Eratostenesa .min

Działający kod Python w celu zademonstrowania powtarzalności:

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

Szybki przykład:

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

Problem polega na tym, że jestem teraz nad głową, zarówno matematycznie, jak i jako informatyk. W szczególności nie jestem kompetentny w analizie Fouriera , w definiowaniu jednolitych okładek , ani ogólnie w złożonej płaszczyźnie , i martwię się, że to podejście jest całkowicie błędne lub ukrywa przerażający problem 3SAT, który podnosi go do NP-kompletność.

Tak więc mam tutaj trzy pytania:

  1. Biorąc pod uwagę moją zwięzłość powyżej, czy można deterministycznie obliczyć lub oszacować położenie zer w wielomianowym czasie i przestrzeni?
  2. Jeśli tak, a jeśli nie, to czy ukrywa on inne podproblemy, które sprawiłyby, że rozwiązanie dla politytime lub polyspace byłoby trudne?
  3. A jeśli jakimś cudem (1) i (2) utrzyma się, jakie ulepszenia w zakresie programowania dynamicznego wprowadzilibyście, aby zaspokoić ten nawrót, z wysokiego poziomu? Oczywiście, iteracja po tych samych liczbach całkowitych przez wiele funkcji jest nieelegancka i dość marnotrawna.
MrGomez
źródło
A dla tych, którzy wciąż tu są, pomimo mojej ściany tekstu: nie jestem pewien, czy to zredukuje się do zeta Riemanna, tym samym nadając mu tę samą złożoność. Jednak nie sądzę, żeby tak było.
MrGomez
1
1) Jakie tagi chciałbyś? Możesz je stworzyć samodzielnie, korzystając z nich. 2) Podaj ogólną definicję , tj. Czym jest ? 3) Jeśli nie dostaniesz odpowiedzi na ten temat po upływie około tygodnia, możesz chcieć przenieść go tak cstheory.SE. fafa(pn)
Raphael
1
Nie śledzę wszystkiego w twoim poście. Myślę, że masz na myśli NP-zupełne, a nie NP. Generalnie udowodnienie, że funkcja teorii liczb jest NP-zupełna, jest dość trudnym zadaniem, ponieważ często brakuje im / ukrywają jakąkolwiek kombinatoryczną strukturę, która pozwoliłaby nam zaprojektować gadżety do redukcji.
Kaveh
1
fa(x)
fa

Odpowiedzi:

1

Poniższy artykuł pokazuje, że PRIMES jest w P (wygrał także nagrodę Gödela w 2006 roku):

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

Ustawiając rozwiązanie N-tej procedury minimalizacji liczby pierwszej w algorytmie AKS PRIMES (modulo odejmowanie), możemy skutecznie uzyskać realne rozwiązanie relacji rekurencji (jeśli możesz udowodnić, że przerwa pierwsza jest podana w relacji rekurencji).

Kody źródłowe można znaleźć w Internecie. Nie wskazuję ich tutaj, ponieważ nie sprawdziłem ich osobiście.

n

użytkownik13675
źródło
1
Strona Rosettacode jest całkowicie błędnie nazwana. To nie jest test pierwotności AKS i jest to powtórzenie podziału próby przez wszystkie liczby całkowite mniejsze niż n. Z drugiej strony warto zwrócić uwagę na to, że pierwszeństwo występuje w P i sprawdzić, czy to rzuca światło na pierwotne pytanie.
DanaJ
Dobra uwaga ... Naprawię to ...
użytkownik13675,
1
nlgn