Membuktikan (dalam) keterlacakan dari pengulangan utama Nth ini

Sebagai berikut dari pertanyaan saya sebelumnya , saya telah bermain dengan hipotesis Riemann sebagai soal matematika rekreasi. Dalam prosesnya, saya sampai pada pengulangan yang agak menarik, dan saya ingin tahu tentang namanya, pengurangannya, dan ketertelusurannya terhadap solvabilitas kesenjangan antara bilangan prima.

Singkatnya, kita dapat mendefinisikan kesenjangan antara setiap bilangan prima sebagai pengulangan bilangan prima kandidat sebelumnya . Misalnya, untuk basis kami , bilangan prima berikutnya adalah:$p_0 = 2$

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

Atau, seperti yang kita lihat dengan merencanakan ini : $p_1 = 3$ .

Kami dapat mengulangi proses untuk $n$ primes dengan mengevaluasi setiap kandidat prime berulang ke depan. Misalkan kita ingin mendapatkan prime berikutnya, $p_2$ . Fungsi kandidat kami menjadi:

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

Dimana:

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

Sangat mudah untuk melihat bahwa setiap fungsi komponen hanya menjadi nol pada nilai integer, dan sama mudahnya untuk menunjukkan bagaimana ini menangkap hubungan berbentuk AND dan XOR secara cerdik, dengan mengeksploitasi properti penambahan dan perkalian dalam konteks sistem trigonometri. persamaan.

Perulangan menjadi:

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

... di mana seluruh masalah bergantung pada apakah kita dapat mengevaluasi $\min$ operator atas fungsi ini dalam waktu polinomial. Ini, pada dasarnya, adalah generalisasi dari Saringan Eratosthenes .

Bekerja dengan kode Python untuk menunjukkan pengulangan:

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

Contoh cepat:

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

Masalahnya adalah, saya sekarang berada di atas kepala saya, baik secara matematis maupun sebagai ilmuwan komputer. Secara khusus, saya tidak kompeten dengan analisis Fourier , dengan mendefinisikan sampul seragam , atau dengan bidang kompleks pada umumnya, dan saya khawatir bahwa pendekatan ini salah atau menyembunyikan kengerian dari masalah 3SAT yang mengangkatnya menjadi Kelengkapan NP.

Jadi, saya punya tiga pertanyaan di sini:

1. Dengan pengulangan singkat saya di atas, apakah mungkin untuk secara deterministik menghitung atau memperkirakan lokasi nol dalam waktu dan ruang polinomial?
2. Jika ya atau tidak, apakah ia menyembunyikan subproblem lain yang akan membuat solusi polytime atau polyspace menjadi sulit?
3. Dan jika dengan beberapa keajaiban (1) dan (2) bertahan, peningkatan pemrograman dinamis apa yang akan Anda lakukan dalam memuaskan perulangan ini, dari level tinggi? Jelas, iterasi pada bilangan bulat yang sama melalui beberapa fungsi tidak elegan dan cukup boros.

Makalah berikut menunjukkan bahwa PRIMES ada di P (juga memenangkan penghargaan Gödel pada 2006):

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

Dengan menetapkan solusi prosedur minimalisasi prima N ke algoritma AKS PRIMES (modulo a subtraction), kita dapat secara efektif mendapatkan solusi yang dapat ditelusuri ke relasi perulangan (jika Anda dapat membuktikan bahwa celah utama diberikan oleh relasi perulangan).

Kode sumber dapat ditemukan di internet. Saya tidak menunjuk mereka di sini karena saya tidak memeriksanya secara pribadi.

Namun demikian, kita mungkin masih memiliki batas atas untuk memeriksa semua angka ...$\sqrt{n}$