Obliczanie funkcji Mobiusa

13

Funkcja Mobiusa jest zdefiniowana jako , jeśli ma kwadratowy współczynnik liczby pierwszej , a jeśli wszystkie liczby pierwsze są różne. Czy można obliczyć $\mu(n)$ $\mu(1)=1$ $\mu(n)=0$ $n$ $\mu(p_1 \dots p_k)= (-1)^k$ $p_1,\dots,p_k$ $\mu(n)$ bez obliczania pierwszej faktoryzacji ? $n$

comp-number-theory Craig Feinstein
źródło

6

Myślę, że on tylko pyta, czy istnieje sposób obliczenia

którym nie wiadomo, że zapewnia również faktoryzację.

μ (n)

$\mu(n)$

Suresh Venkat

2

@Kaveh, nie mówię tu o złożoności obliczeniowej. Suresh ma rację w swojej interpretacji. Jest to podobne do ustalenia, że liczba jest złożona bez określania jej faktoryzacji. Czy coś takiego można zrobić również dla funkcji Mobiusa?

Craig Feinstein

1

Nie sądzę, żeby to było prawdziwe pytanie. Pomyślałem, że warto przypomnieć, że na cstheory mamy surową politykę przeciwko tematom przyjaznym dla korb na wypadek, gdybyś próbował zareklamować zawarte w nich pomysły .

Kaveh

3

@Kaveh, zadałem poważne pytanie, które ma 4 kciuki do góry. Jasne, moja odpowiedź obniżyła 8 kciuków, ale takie jest życie. Do dziś nie znałem mojej odpowiedzi na pytanie, więc opublikowałem odpowiedź. Wydaje mi się, że próbujesz mnie ostracyzować, twierdząc, że mam tutaj jakiś ukryty motyw. Zapewniam cię, że nie mam żadnego ukrytego motywu poza uzyskaniem odpowiedzi na pytanie.

Craig Feinstein

5

@Kaveh: OP to dobrze znany trisector na wielu forach. To powiedziawszy, czy widziałeś go niegrzecznego wobec kogoś? Nie mam Po prostu źle rozumie, co to znaczy udowodnić dolne granice. Pytanie wydaje mi się na temat. Jest takie powiedzenie: „Nawet zatrzymany zegar ma rację dwa razy dziennie”.

Aaron Sterling

34

Jedną z braku odpowiedzi na twoje pytanie jest to, że BEZ KWADRATU (jest liczbą wolną od kwadratów) sama nie jest znana jako P, a obliczenie funkcji Möbiusa rozwiązałoby ten problem (ponieważ liczba wolna od kwadratów ma ). $\mu(n) \neq 0$

Suresh Venkat
źródło

7

czy znasz jakieś dokumenty, które omawiają złożoność kwadratowości? wszystko, co mogłem znaleźć, to: dl.acm.org/citation.cfm?id=371327&dl=GUIDE&coll=GUIDE , co daje dolne granice rozmiaru formuły. patrząc na mathoverflow.net/questions/16098/… , myślę, że niewiele wiadomo na temat tego, czy uda się zredukować faktoring do kwadratowej chudości.

Sasho Nikolov,

15

$\mathrm{AC}^0$

Emil Jeřábek
źródło

4

Myślę, że to zielona księga Bena: arxiv.org/abs/1103.4991

Suresh Venkat

0

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

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

μ (n)

$\mu(n)$

m < n

$m < n$

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

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

n

$n$

m < n

$m<n$

n

$n$

m

$m$

μ (m) = 0

$\mu(m)=0$

m

$m$

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

Hunde Eba
źródło

n = 120

$n=120$

Sprawdź edytowaną wersję !! @Craig

Hunde Eba

-22

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

p_{1} \dots p_{k}

$p_1 \dots p_k$

n

$n$

Oto analogia: aby wiedzieć, czy w słoiku znajduje się nieparzysta, czy parzysta liczba żelków, należy policzyć żelki. Dlatego musisz obliczyć pierwszą faktoryzację liczby, aby obliczyć jej funkcję Mobiusa, gdy nie jest ona podzielna przez kwadrat. Ale aby wiedzieć, że w słoiku jest więcej niż jedna żelka, nie trzeba badać żadnej żelki w słoiku. Wystarczy potrząsnąć słoikiem i usłyszeć, że jest więcej niż jedna żelka. Dlatego nie musisz uwzględniać liczby, aby wiedzieć, że jest złożona. Algorytmy takie jak Małe Twierdzenie Fermata pozwalają „wstrząsnąć liczbą”, aby wiedzieć, że jest złożona.

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

Craig Feinstein
źródło

6

@Craig Nadal jest źle. Możesz użyć tego samego (błędnego) argumentu dla problemu złożonego testowania, jak powiedział Peter Shor. Zasadniczo podajesz algorytm dla swojego problemu i stwierdzasz, że jest to jedyny sposób, aby kontynuować. Wykazanie, że oczywisty algorytm jest najlepszym rozwiązaniem problemu, jest jednym z największych wyzwań w teorii złożoności.

Michael Blondin,

6

n \times n

$n \times n$

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

O (n^{3})

$O(n^3)$

O (n^{2.807})

$O(n^{2.807})$

14

Re „Aby wiedzieć, czy w słoiku znajduje się nieparzysta, czy parzysta liczba żelków, należy policzyć żelki”. - nawet to nie jest prawda. Możesz wyciągać je w parach (jedna dla mnie jedna dla ciebie ...) bez faktycznego liczenia ich podczas podróży. Następnie, gdy zabraknie par do pociągnięcia, masz zero lub jeden i znasz parzystość.

David Eppstein,

12

M

$M$

6

Craig, bez dzielenia go na liczby pierwsze , tak, poprzez obliczanie pierwiastka z liczby całkowitej (pierwiastek obliczany w czasie wielomianowym w przeciwieństwie do faktoringu), to 69 ^ 2. Nie muszę uwzględniać 69. Argumentacja z fasoli sugeruje, że faktoring jest obowiązkowy, ponieważ musisz spojrzeć na każdą galaretkę, aby sprawdzić, czy każdy smak występuje nawet kilka razy.

sdcvvc

Obliczanie funkcji Mobiusa

Odpowiedzi: