Merlin, yang memiliki sumber daya komputasi tidak terbatas, ingin meyakinkan Arthur bahwa untuk dengan dan Menghitung jumlah ini dengan cara langsung (eksponensial dan penambahan modular) membutuhkan waktu dengan perkalian berbasis FFT. * Tetapi Arthur hanya dapat melakukan operasi .

(Notasi, untuk kompatibilitas dengan versi sebelumnya dari pertanyaan ini: Biarkan penjumlahannya sama dengan ; maka pertanyaannya adalah apakah adalah integer.)$m\alpha$$\alpha$

Bisakah Merlin meyakinkan Arthur dengan seutas panjang ? Jika tidak, bisakah dia meyakinkan Arthur dengan bukti interaktif (komunikasi total, tentu saja, harus )? Jika demikian, dapatkah Merlin menggunakan string dengan panjang ? Bisakah Arthur menggunakan waktu ?$O(N)$$O(N)$$o(N)$$o(N)$

Arthur tidak memiliki akses ke nondeterminisme atau alat khusus lainnya (metode kuantum, peramal selain Merlin, dll.) Tetapi memiliki ruang jika diperlukan. Tentu saja Arthur tidak perlu menghitung penjumlahan secara langsung, ia hanya perlu diyakinkan bahwa triple yang diberikan (N, m, k) membuat persamaan itu benar atau salah.$O(N)$

Perhatikan bahwa dengan dimungkinkan untuk menghitung jumlah waktu menggunakan metode Lagarias-Odlyzko . Untuk jumlahnya adalah superlinear dan tidak dapat disimpan secara langsung (tanpa, misalnya, pengurangan modular) tetapi tidak jelas apakah ada algoritma cepat.O ( N 1 / 2 + ε$k=0$$O(N^{1/2+\varepsilon})$$k>0$

Saya juga akan tertarik pada algoritma apa pun untuk menghitung penjumlahan (modular atau sebaliknya) selain dengan menyalakan langsung dan penambahan.

* angka untuk menghitung, waktu untuk setiap perhitungan.lg k log N ( log log N ) 1 + o ( 1 ) = log N ( log log N ) 2 + o ( 1 $N/\log N$$\lg k\log N(\log\log N)^{1+o(1)}=\log N(\log\log N)^{2+o(1)}$

Saya memposting ini secara terpisah dari kasus khusus saya sebelumnya, karena saya percaya ini adalah pendekatan yang berbeda untuk masalah ini, dan memiliki sedikit kaitan dengan jawaban saya yang lain. Mungkin tidak persis apa yang Anda cari, tetapi sederhana, dan semakin dekat.

Ada bukti yang akan selalu diterima Arthur jika buktinya benar, tetapi akan menolak dengan probabilitas . Berikut adalah cara kerjanya: Merlin mengirimkan Arthur pasangan untuk setiap prima . Arthur memverifikasi jumlah (mengambil waktu ). Arthur cek bahwa jumlah yang benar dari bilangan prima yang disediakan (dengan menghitung ) yang sublinear di . Terakhir, untuk pasangan acak , ia mengonfirmasi bahwa adalah prima dan bahwa . Ini membutuhkan waktu (pi,ci=p k i  mod m)p≤NO(N/log(N))×O(log(N))=O(N)π(N)NSNpp k $\frac{1}{(\log \log N)^{2+o(1)}}$$(p_i,c_i = p_i^k\mbox{ mod }m)$$p\leq N$$O(N/\log(N)) \times O(\log(N)) = O(N)$$\pi(N)$$N$$S N$$p$S N O ( ( log log N ) 2 + o ( 1 $p_i^k \equiv c_i \mbox{ mod }m$S = ( log log N ) - ( 2 + o ( 1 ) )$SN~O((\log \log N)^{2+o(1)})$. Mengambil , kami memperoleh skala waktu linier. Dengan demikian, sebagian kecil dari semua pasangan diverifikasi. Jika ada yang gagal, tentu saja Arthur akan menolak. Agar Arthur menerima bukti yang salah, harus ada setidaknya satu pasangan yang gagal satu dari dua tes ini (atau jumlah pasangan harus kurang dari π ( N ) yang sebelumnya diperiksa). Jadi sebagai pecahan S dari semua pasangan diperiksa, tes akan gagal untuk bukti yang salah dengan probabilitas setidaknya S .$S = (\log \log N)^{-(2+o(1))}$$S$$\pi(N)$$S$$S$

Perhatikan bahwa untuk besar ini jauh lebih baik daripada menebak acak, yang berhasil dengan probabilitas $N$ .$\frac{1}{m} = \frac{1}{O(N)}$

Ini adalah jawaban lengkap untuk masalah yang tidak menggunakan Merlin sama sekali.

Deléglise-Dusart-Roblot [1] memberikan suatu algoritma yang menentukan jumlah bilangan prima hingga yang kongruen dengan l modulo k , dalam waktu O ( x 2 / 3 / log 2 x ) . Sebuah modifikasi dari algoritma Lagarias-Odlyzko [2] memungkinkan sama harus dihitung dalam waktu O ( x 1 / 2 + o ( 1 ) ) $x$$l$$k,$$O(x^{2/3}/\log^2x).$$O(x^{1/2+o(1)}).$

Dengan menggunakan salah satu algoritma, cari jumlah bilangan prima di semua kelas residu mod bilangan prima sampai produk mereka lebih besar dari Untuk setiap q prima , ambil jumlah total bilangan prima di setiap kelas residu kali kelas residu dengan kekuatan k -th; ini memberikan nilai $m.$$q,$$k$

Gunakan Teorema Sisa Mandarin untuk menentukan nilai jumlah mod$2\cdot3\cdots\log m.$

Dengan teorema bilangan prima, bilangan prima terbesar yang dibutuhkan adalah jadi ini memberikan jumlah waktuO ( N 1 / 2 + o ( 1 ) ) $(1+o(1))\log m,$$O(N^{1/2+o(1)}).$

Referensi

[1] Marc Deléglise, Pierre Dusart, dan Xavier-François Roblot, Menghitung bilangan prima di kelas residu , Matematika Komputasi 73 : 247 (2004), hlm. 1565-1575. doi 10.1.1.100.779

[2] JC Lagarias dan AM Odlyzko, Komputasi : Metode analitik$\pi(x)$ , Jurnal Algoritma 8 (1987), hlm. 173-191.

[3] Charles, jawab di MathOverflow . (Ya, ini adalah orang yang sama. Lihat jawaban lain di sana untuk pendekatan yang berbeda.)

Ini bukan jawaban lengkap, melainkan kasus khusus (untuk nilai lebih besar dari yang Anda pertimbangkan), yang semula saya posting sebagai komentar. Dalam kasus (untuk beberapa bilangan bulat ) ada bukti sederhana dan string Merlin bisa dari nol panjang.k = x φ ( m ) $k$$k=x \phi(m)$$x$

Untuk melakukan ini, Arthur cukup menghitung . Ini dapat dilakukan dengan memfaktorkan (yang dapat dilakukan dalam waktu sublinear di bahkan menggunakan divisi percobaan). Karena untuk semua , dan jika tidak, jika maka kita memiliki , di mana adalah jumlah perbedaan pembagi utama . Seperti yang ditunjukkan di bagian komentar dapat dihitung dalam waktu sublinear dalamm $\phi(m)$$m$$N$p | m p x φ ( m ) ≡ 1  mod  m k = x φ ( m ) Σ p ≤ N , p p r i m e p k ≡ π ( N ) - y  mod  m y $p^{x \phi(m)} \equiv 0 \mbox{ mod } m$$p|m$$p^{x \phi(m)} \equiv 1 \mbox{ mod } m$$k=x \phi(m)$$\sum_{p \leq N, p~prime} p^{k} \equiv \pi(N) - y \mbox{ mod } m$$y$$m$$\pi(N)$$N$, dan karenanya jumlah ini dapat langsung dihitung oleh Arthur.

Selanjutnya, untuk kasus khusus yang maka jumlahnya tidak dapat sama dengan , seperti .m α 1 < π ( N ) < $1<N<m$$m\alpha$$1<\pi(N)<m$