Konsekuensi algoritma rumus aljabar untuk fungsi partisi?

Bruinier dan Ono telah menemukan formula aljabar untuk fungsi partisi , yang secara luas dilaporkan sebagai terobosan. Saya tidak dapat memahami makalah ini, tetapi apakah ia memiliki konsekuensi algoritmik untuk penghitungan cepat fungsi partisi?

algorithms complexity-theory number-theory sdcvvc
sumber

Bisakah Anda memberikan tautan ke pernyataan tentang terobosan? Saya ingin melihat dalam arti apa itu terobosan.

Jernej

@ Jernej Ini adalah rumus eksplisit hingga untuk

. Sebelumnya kami memiliki ekspansi Rademacher, yang merupakan seri tak terbatas, dan berbagai rumus rekursi.

p (n)

$p(n)$

Yuval Filmus

Jawaban:

Ini adalah keyakinan saya yang kurang informasi bahwa formula Rademacher lebih cepat dalam praktik (dan mungkin secara teori juga) daripada formula Bruinier dan Ono. Sementara ekspansi asimtotik Rademacher adalah jumlah yang tidak terbatas, kita tahu bahwa adalah bilangan bulat, jadi jika kita memiliki batas pada bagian belakang ekspansi, kita dapat menggunakan rumus untuk menghitung . Menurut Calkin et al. , "rumus persis Rademacher menghasilkan algoritma yang sangat cepat". $p(n)$ $p(n)$

Bruinier dan Ono menggambarkan apa yang akan dilakukan untuk mengimplementasikan algoritma mereka di Bagian 5 dari makalah mereka. Langkah pertama adalah untuk menentukan wakil-wakil untuk , yang ada . Menurut Soundararajan , kita harus mengharapkan , sehingga rumusnya akan melibatkan penjumlahan. Itu membuatnya lebih buruk daripada formula Euler untuk $\mathcal{Q}_n$ $h(-24n+1)$ $h(-24n+1) = \Theta(n)$ $\Theta(n)$ $p(n)$ (berbicara secara komputasi), meskipun yang terakhir diakui membutuhkan memori. $\Omega(n)$

Yuval Filmus
sumber

Memang, saya tunjukkan dalam (1) bahwa rumus Rademacher secara teoritis kuasi-optimal (dan, heuristik, secara praktis optimal) jika diterapkan dengan sangat hati-hati.

Fredrik Johansson