Menghitung fungsi Mobius

13

Fungsi Mobius $\mu(n)$ didefinisikan sebagai , jika memiliki faktor prima kuadrat, dan jika semua primes berbeda. Apakah mungkin untuk menghitung tanpa menghitung faktorisasi utama ? $\mu(1)=1$ $\mu(n)=0$ $n$ $\mu(p_1 \dots p_k)= (-1)^k$ $p_1,\dots,p_k$ $\mu(n)$ $n$

comp-number-theory Craig Feinstein
sumber

6

Saya pikir dia hanya bertanya apakah ada cara untuk menghitung

μ (n)

$\mu(n)$ yang tidak diketahui juga memberikan faktorisasi.

Suresh Venkat

2

@ Kaveh, saya tidak berbicara tentang kompleksitas komputasi di sini. Suresh benar dalam interpretasinya. Ini mirip dengan menentukan bahwa angka adalah komposit tanpa menentukan faktorisasi. Bisakah hal seperti ini juga dilakukan untuk fungsi Mobius?

Craig Feinstein

1

Saya tidak berpikir ini adalah pertanyaan nyata. Saya pikir mungkin berguna untuk mengingatkan Anda bahwa pada cstheory kita memiliki ketat kebijakan terhadap topik yang ramah-engkol dalam kasus Anda mencoba untuk mengiklankan ide-ide dalam ini .

Kaveh

3

@ Kaveh, saya mengajukan pertanyaan serius yang mendapat 4 jempol. Tentu, jawaban saya mendapat 8 jempol ke bawah, tapi itu hidup. Saya tidak tahu jawaban saya untuk pertanyaan sampai hari ini, jadi saya memposting jawabannya. Kedengarannya bagi saya seperti Anda mencoba mengucilkan saya dengan mengklaim saya memiliki beberapa jenis motif tersembunyi di sini. Saya dapat meyakinkan Anda bahwa saya tidak memiliki motif tersembunyi selain untuk mendapatkan jawaban atas pertanyaan itu.

Craig Feinstein

5

@Kaveh: OP adalah trisector terkenal, di banyak forum. Yang mengatakan, pernahkah Anda melihatnya kasar kepada seseorang? Saya belum. Dia hanya salah mengerti apa artinya membuktikan batas bawah. Pertanyaan itu tampaknya pada topik bagi saya. Ada pepatah: "Bahkan jam yang berhenti tepat dua kali sehari."

Aaron Sterling

34

Satu non-jawaban untuk pertanyaan Anda adalah bahwa SQUARE-FREE (adalah angka bebas persegi) itu sendiri tidak diketahui berada di P, dan menghitung fungsi Möbius akan menyelesaikan masalah ini (karena angka bebas persegi memiliki ). $\mu(n) \neq 0$

Suresh Venkat
sumber

7

Apakah Anda tahu ada makalah yang membahas kompleksitas persegi-freeness? yang bisa saya temukan adalah ini: dl.acm.org/citation.cfm?id=371327&dl=GUIDE&coll=GUIDE , yang memberikan batas formula ukuran formula lebih rendah. melihat mathoverflow.net/questions/16098/... , saya pikir tidak banyak yang diketahui tentang apakah itu mungkin dapat mengurangi anjak piutang menjadi jujur.

Sasho Nikolov

15

Untuk jawaban lain, Anda mungkin tertarik pada dugaan Sarnak (lihat misalnya http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/ , http: //rjlipton.wordpress .com / 2011/02/23 / the-depth-of-the-mobius-function / , /mathpro/57543/walsh-fourier-transform-of-the-mobius-function ), yang pada dasarnya menyatakan bahwa fungsi Möbius tidak berkorelasi dengan fungsi Boolean "sederhana". Bukan tidak masuk akal untuk mengharapkannya berlaku ketika "sederhana" ditafsirkan sebagai waktu polinomial. Apa yang kita tahu sejauh ini adalah bahwa dugaan tersebut berlaku untuk -functions (dibuktikan dengan Ben Hijau ), dan semua fungsi monoton (dibuktikan dengan Jean Bourgain ). $\mathrm{AC}^0$

Emil Jeřábek mendukung Monica
sumber

4

Saya pikir ini adalah makalah Ben Green: arxiv.org/abs/1103.4991

Suresh Venkat

0

Salah satu rumus rekursif berkaitan nilai-nilai fungsi mobious adalah

\sum_{m \leq n} ⌊ \frac{n}{m} ⌋ μ (m) = 1.

$\sum_{m \leq n} \left\lfloor \dfrac {n}{m} \right\rfloor \mu (m) = 1.$ Tetapi untuk mencari

μ (n)

$\mu(n)$ kita perlu mengetahui nilai mobilitas untuk

m < n

$m < n$ . Oleh karena itu

μ (n) = 1 - \sum_{m < n} ⌊ \frac{n}{m} ⌋ μ (m) .

$\mu (n) =1-\sum_{m < n} \left \lfloor \dfrac {n}{m}\right \rfloor \mu (m) .$ Di sini kita membagi

n

$n$ dengan bilangan bulat positif yang lebih kecil

m < n

$m<n$ , kita tidak perlu tahu apakah itu adalah faktor

n

$n$ ketika

m

$m$ memiliki faktor kuadrat! (

μ (m) = 0

$\mu(m)=0$ ), Tapi kita masih harus tahu faktor-faktor

m

$m$ untuk menyimpulkan ini !! Oleh karena itu kami memiliki:

\begin{aligned} μ (n) = & 1 - \sum_{a_{1} < n} ⌊ \frac{n}{a_{1}} ⌋ \\ + & \sum_{a_{1} < n} ⌊ \frac{n}{a_{1}} ⌋ \sum_{a_{2} < a_{1}} ⌊ \frac{a_{1}}{a_{2}} ⌋ \\ - & \sum_{a_{1} < n} ⌊ \frac{n}{a_{1}} ⌋ \sum_{a_{2} < a_{1}} ⌊ \frac{a_{1}}{a_{2}} ⌋ \sum_{a_{3} < a_{2}} ⌊ \frac{a_{2}}{a_{3}} ⌋ + \dots \end{aligned}

$\begin{align} \mu(n)=&1-\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \\ +&\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \\ -&\sum_{a_1< n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2< a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \sum_{a_3< a_2} \left \lfloor \dfrac {a_2}{a_3}\right \rfloor + \cdots \end{align}$ Lihat makalah ini:https://projecteuclid.org/euclid.mjms/1513306829untuk bukti formula.

Hunde Eba
sumber

Saya suka jawaban Anda. Sayangnya saya tidak memiliki akses ke artikel tersebut. Saya akan berdebat dengan Anda tentang mengetahui faktor-faktor n: Misalkan

. Menggunakan rumus itu, membaginya dengan 5, menggunakan pembagian panjang, Anda menemukan bahwa 24 kali 5 sama dengan 120 dengan sisa 0, jadi dalam proses menghitung fungsi bilangan bulat terbesar 120/5, orang menemukan bahwa 5 adalah faktor 120, bahkan meskipun fakta ini tidak perlu diketahui agar formula itu berfungsi.

n = 120

$n=120$

Craig Feinstein

Periksa versi yang diedit !! @Craig

Hunde Eba

-22

Biarkan , di mana adalah bilangan prima yang berbeda. Kemudian Kemudian untuk menghitung , perlu untuk menghitung untuk setiap $n=p_1 \dots p_k$ $p_j$

μ (n) = μ (p_{1} \dots p_{k}) = μ (p_{1}) \dots μ (p_{k}) .

$\mu(n)=\mu(p_1 \dots p_k)=\mu(p_1)\dots \mu(p_k).$

μ (n)

$\mu(n)$

μ (p_{j})

$\mu(p_j)$

p_{j}

$p_j$ . Ini secara implisit mensyaratkan bahwa

adalah faktorisasi utama

.

p_{1} \dots p_{k}

$p_1 \dots p_k$

n

$n$

Berikut ini analogi: Untuk mengetahui apakah ada jumlah jeli kacang ganjil atau genap dalam satu toples, orang harus menghitung jelly bean. Inilah sebabnya mengapa Anda harus menghitung faktorisasi bilangan utama untuk menghitung fungsi Mobius-nya, ketika itu tidak dapat dibagi oleh kuadrat. Tetapi untuk mengetahui bahwa ada lebih dari satu biji jeli dalam satu toples, kita tidak perlu memeriksa salah satu dari biji jelly di dalam toples. Orang hanya bisa mengocok guci dan mendengar bahwa ada lebih dari satu jelly bean. Inilah sebabnya mengapa Anda tidak perlu memperhitungkan suatu angka untuk mengetahui bahwa itu adalah komposit. Algoritma seperti Teorema Kecil Fermat memungkinkan seseorang untuk "mengguncang angka" untuk mengetahui bahwa itu adalah gabungan.

$n$ $n$ $n$ $n$ $n$ $n$ $\mu(n)=0$ $n$

Craig Feinstein
sumber

6

@Craig Masih salah. Anda bisa menggunakan argumen yang sama (keliru) untuk masalah pengujian komposit seperti yang dikatakan Peter Shor. Anda pada dasarnya memberikan algoritma untuk masalah Anda dan menyatakan bahwa itu adalah satu-satunya cara untuk melanjutkan. Menunjukkan bahwa algoritma yang jelas adalah yang terbaik untuk menyelesaikan masalah adalah salah satu tantangan terbesar dalam teori kompleksitas.

Michael Blondin

6

Saya akan coba memberi contoh. Pertimbangkan masalah mengalikan dua matriks ukuran A dan B

n \times n

$n \times n$ . Definisi AB adalah

(A B)_{i, j} = \sum_{k = 1}^{n} A_{i, k} \cdot B_{k, j}

$(AB)_{i,j} = \sum_{k=1}^n A_{i,k} \cdot B_{k,j}$ . Oleh karena itu, dengan argumen tipe Anda, ini akan menyiratkan bahwa AB harus selalu dihitung dalam waktu

O (n^{3})

$O(n^3)$ dari definisinya. Namun, diketahui bahwa AB dapat dihitung dalam waktu

O (n^{2.807})

$O(n^{2.807})$ . Jika Anda dapat melihat bagaimana yang disebut argumen gagal di sini, Anda harus dapat melihat bagaimana argumen itu gagal dalam jawaban Anda.

Michael Blondin

14

"Untuk mengetahui apakah ada jumlah jeli kacang ganjil atau genap, kita harus menghitung jeli kacang." - bahkan ini tidak benar. Anda bisa menariknya berpasangan (satu untuk saya satu untuk Anda ...) tanpa benar-benar menghitung mereka saat Anda pergi. Kemudian ketika Anda telah kehabisan pasangan untuk menarik, Anda memiliki nol atau satu yang tersisa dan Anda tahu paritasnya.

David Eppstein

12

Untuk masalah ketika penghitungan sulit tetapi paritas mudah, pertimbangkan permanen matriks 0-1

M

$M$ . (Ini sama dengan jumlah pencocokan sempurna dalam grafik bipartit.) Paritas permanen adalah sama dengan paritas determinan, yang dapat dihitung dalam waktu polinomial. Tetapi mengevaluasi yang permanen adalah # P-complete, dan karenanya NP-hard.

Peter Shor

6

Craig, tanpa memfaktorkannya menjadi bilangan prima , ya, dengan menghitung akar kuadrat integer (diketahui dapat dihitung dalam waktu polinom tidak seperti anjak) adalah 69 ^ 2. Saya tidak perlu memperhitungkan 69. Argumen kacang Anda menunjukkan bahwa anjak wajib, karena Anda harus melihat setiap jeli untuk memeriksa apakah setiap rasa muncul bahkan beberapa kali.

sdcvvc

Menghitung fungsi Mobius

Jawaban: