Вычисление функции Мебиуса

Функция Мебиуса определяется как μ ( 1 ) = 1 , μ ( n ) = 0, если n имеет квадратный простой множитель, и μ ( p 1 … p k ) = ( - 1 ) k, если все простые числа p 1 , … , p k разные. Можно ли вычислить μ ( n $\mu(n)$$\mu(1)=1$$\mu(n)=0$$n$$\mu(p_1 \dots p_k)= (-1)^k$$p_1,\dots,p_k$$\mu(n)$без вычисления простой факторизации ?$n$

Один из ответов на ваш вопрос заключается в том, что SQUARE-FREE (это число без квадрата), как известно, не находится в P, и вычисление функции Мёбиуса решило бы эту проблему (так как число без квадрата имеет ).$\mu(n) \neq 0$

Если вы не ответите, вас может заинтересовать гипотеза Сарнака (см., Например, http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/ , http: //rjlipton.wordpress. .com / 2011/02/23 / функция глубины мобильности / , /mathpro/57543/walsh-fourier-transform-of-the-mobius-function ), которая в основном говорится, что функция Мёбиуса не связана с какой-либо «простой» булевой функцией. Нередко ожидать, что оно должно сохраняться, когда «простое» интерпретируется как полиномиальное время. Что мы знаем до сих пор, так это то, что гипотеза верна для -функций (доказано Беном Грином ) и всех монотонных функций (доказано Жаном Бургейном ).$\mathrm{AC}^0$

Одна из рекурсивных формул, относящихся к значениям подвижной функции:

$$\sum_{m \leq n} \left\lfloor \dfrac {n}{m} \right\rfloor \mu (m) = 1.$$ Но для того, чтобы найти $\mu(n)$нам нужно знать подвижные значения для$m < n$. Следовательно $$\mu (n) =1-\sum_{m < n} \left \lfloor \dfrac {n}{m}\right \rfloor \mu (m) .$$ Здесь мы делим$n$на меньшие положительные целые числа$m<n$, нам не нужно знать, являются ли они факторами$n$когда$m$имеет квадратный фактор! ($\mu(m)=0$), но все же мы должны знать факторы$m$чтобы сделать вывод !! Следовательномы имеем: $$\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}$$ Обратитесь к этому документу:https://projecteuclid.org/euclid.mjms/1513306829для доказательства формулы.

$n=p_1 \dots p_k$$p_j$

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

Вот аналогия: чтобы узнать, есть ли в банке нечетное или четное количество желейных бобов, нужно сосчитать желейные бобы. Вот почему вы должны вычислить простую факторизацию числа, чтобы вычислить его функцию Мёбиуса, когда она не делится на квадрат. Но чтобы знать, что в банке находится более одного желе, не нужно проверять какие-либо желе в банке. Можно просто встряхнуть банку и услышать, что есть более одного желе. Вот почему вам не нужно учитывать число, чтобы знать, что оно составное. Алгоритмы, такие как маленькая теорема Ферма, позволяют «встряхнуть число», чтобы понять, что оно составное.

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