Computing the Mobius function

Question

The Mobius function $\mu(n)$ is defined as $\mu(1)=1$, $\mu(n)=0$ if $n$ has a squared prime factor, and $\mu(p_1 \dots p_k)= (-1)^k$ if all the primes $p_1,\dots,p_k$ are different. Is it possible to compute $\mu(n)$ without computing the prime factorization of $n$?

Answer 1

One non-answer to your question is that SQUARE-FREE (is a number square free) is itself not known to be in P, and computing the Möbius function would solve this problem (since a square free number has $\mu(n) \neq 0$).

Answer 2

For another non-answer, you might be interested in Sarnak’s conjecture (see e.g. 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/, https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function), which basically states that Möbius function is not correlated with any “simple” Boolean function. It’s not unreasonable to expect it should hold when “simple” is interpreted as polynomial-time. What we know so far is that the conjecture holds for $\mathrm{AC}^0$-functions (proved by Ben Green), and all monotone functions (proved by Jean Bourgain).

Answer 3

One of the recursive formulas relating values of mobious function is $$\sum_{m \leq n} \left\lfloor \dfrac {n}{m} \right\rfloor \mu (m) = 1.$$ But inorder to find the $\mu(n)$ we need to know the mobious values for $m < n $. Hence $$\mu (n) =1-\sum_{m < n} \left \lfloor \dfrac {n}{m}\right \rfloor \mu (m) .$$ Here we are dividing $n$ by the smaller positive integers $m<n$, we don't have to know if they are factors of $n$ when $m$ has a square factor! ( $\mu(m)=0$) ,But still we have to know the factors of $m$ to conclude this!! Hence we have: \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} Refer to this paper: https://projecteuclid.org/euclid.mjms/1513306829 for the proof of the formula.

Answer 4

Let $n=p_1 \dots p_k$, where $p_j$ are distinct primes. Then $$\mu(n)=\mu(p_1 \dots p_k)=\mu(p_1)\dots \mu(p_k).$$ Then to compute $\mu(n)$, it is necessary to compute $\mu(p_j)$ for each $p_j$. This implicitly requires recognizing that $p_1 \dots p_k$ is the prime factorization of $n$.

Here's an analogy: In order to know whether there are an odd or even number of jelly beans in a jar, one must count the jelly beans. This is why you must compute the prime factorization of a number to compute its Mobius function, when it is not divisible by a square. But in order to know that there is more than one jelly bean in a jar, one does not need to examine any of the jelly beans in the jar. One can just shake the jar and hear that there is more than one jelly bean. This is why you don't have to factor a number to know it is composite. Algorithms like Fermat's Little Theorem allow one to "shake the number up" to know it is composite.

When $n$ is divisible by a square, you don't have to compute the prime factorization of $n$. But you do have to find a nontrivial factor of $n$: If $n$ is square, in order to determine that it is square, you have to take its square root, in which you find a nontirival factor of $n$. A fortiori, if $n$ is not a square but is still not squarefree, in order to determine that $\mu(n)=0$, it is necessary to find a nontrivial factor of $n$.