Computing the Mobius function

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

• I think he's merely asking if there's a way to compute $\mu(n)$ that is not known to also provide a factorization. Nov 29 '11 at 16:41
• @Kaveh, I'm not talking about computational complexity here. Suresh is correct in his interpretation. It's similar to determining that a number is composite without determining its factorization. Can something like this also be done for the Mobius function? Nov 29 '11 at 17:47
• I don't think this is a real question. I thought it might be useful to remind you that on cstheory we have a strict policy against crank-friendly topics in case you try to advertise the ideas in these. Dec 5 '11 at 0:09
• @Kaveh, I asked a serious question which got 4 thumbs ups. Sure, my answer got 8 thumbs down, but that's life. I didn't know my answer to the question until today, so I posted the answer. It sounds to me like you are trying to ostracize me by claiming I have some type of ulterior motive here. I can assure you that I have no ulterior motive other than to get an answer to the question. Dec 5 '11 at 0:59
• @Kaveh: The OP is a well known trisector, on multiple forums. That said, have you ever seen him be rude to someone? I haven't. He just misunderstands what it means to prove lower bounds. The question seems on topic to me. There is a saying: "Even a stopped clock is right twice a day." Dec 5 '11 at 2:45

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

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).

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, 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.

• I like your answer. Unfortunately I do not have access to the article. I would debate with you about knowing the factors of n: Suppose $n=120$. Using that formula, dividing by 5, using long division, you find that 24 times 5 equals 120 with remainder 0, so in the process of calculating the greatest integer function of 120/5, one finds that 5 is a factor of 120, even though this fact is not necessary to know for the formula to work. Jul 7 '19 at 4:35
• Check the edited version!! @Craig Jul 19 '19 at 22:14

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

• @Craig It is still wrong. You could use the same (fallacious) argument for the composite testing problem as Peter Shor said. You're basically giving an algorithm for your problem and stating that it is the only way to proceed. Showing that an obvious algorithm is the best to solve a problem is one of the biggest challenge in complexity theory. Dec 4 '11 at 21:03
• I will try to give an example. Consider the problem of multiplying two matrices A and B of size $n \times n$. The definition of AB is $(AB)_{i,j} = \sum_{k=1}^n A_{i,k} \cdot B_{k,j}$. Therefore, by an argument of your type, this would imply that AB must necessarily be computed in time $O(n^3)$ from its definition. However, it is well-known that AB can be computed in time $O(n^{2.807})$. If you can see how the so-called argument fails here, you should be able to see how it fails in your answer. Dec 4 '11 at 23:57
• Re "In order to know whether there are an odd or even number of jelly beans in a jar, one must count the jelly beans." — even this is not true. You could pull them out in pairs (one for me one for you...) without actually counting them as you go. Then when you have run out of pairs to pull, you have either zero or one left and you know the parity. Dec 6 '11 at 7:10
• For a problem where counting is hard but parity is easy, consider the permanent of a 0-1 matrix $M$. (This is the same as the number of perfect matchings in a bipartite graph.) The parity of the permanent is the same as the parity of the determinant, which can be computed in polynomial time. But evaluating the permanent is #P-complete, and thus NP-hard. Dec 7 '11 at 2:51
• Craig, without factoring it into primes, yes, by computing integer square root (known to be computable in polynomial time unlike factoring) it's 69^2. I do not have to factor 69. Your beans argument suggests that factoring is mandatory, since you have to look at every jelly to check if every flavour occurs even number of times. Dec 8 '11 at 20:42