<p>One non-answer to your question is that <a href="http://mathworld.wolfram.com/Squarefree.html" rel="noreferrer">SQUARE-FREE</a> (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$). </p>

CC BY-SA 3.0
2011-12-05T23:36:37.753Z
do you know any papers that discuss the complexity of square-freeness? all i could find is this: http://dl.acm.org/citation.cfm?id=371327&dl=GUIDE&coll=GUIDE, which gives formula size lower bounds. looking at http://mathoverflow.net/questions/16098/complexity-of-testing-integer-square-freeness, i think not much is known about whether it's likely to be able to reduce factoring to square freeness.
Sasho Nikolov
CC BY-SA 3.0
2011-11-29T18:21:32.733Z
2017-01-03T11:09:20.573Z
2017-01-03T11:09:20.573Z
Suresh Venkat
<p>For another non-answer, you might be interested in Sarnak’s conjecture (see e.g. <a href="http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/" rel="nofollow noreferrer">http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/</a>, <a href="http://rjlipton.wordpress.com/2011/02/23/the-depth-of-the-mobius-function/" rel="nofollow noreferrer">http://rjlipton.wordpress.com/2011/02/23/the-depth-of-the-mobius-function/</a>, <a href="https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function">https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function</a>), 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 <a href="http://arxiv.org/abs/1103.4991" rel="nofollow noreferrer">Ben Green</a>), and all monotone functions (proved by <a href="http://arxiv.org/abs/1112.1423" rel="nofollow noreferrer">Jean Bourgain</a>).</p>

CC BY-SA 3.0
2011-12-01T17:27:41.543Z
I think this is the Ben Green paper: http://arxiv.org/abs/1103.4991
Suresh Venkat
CC BY-SA 3.0
2011-12-01T13:39:43.073Z
2011-12-09T13:20:51.413Z
2017-04-13T12:57:54.777Z
Emil Jeřábek
<p>One of the recursive formulas relating values of mobious function is
<span class="math-container">$$\sum_{m \leq n} \left\lfloor \dfrac {n}{m} \right\rfloor  \mu (m) = 1.$$</span>
But inorder to find the
 <span class="math-container">$\mu(n)$</span> we need to know the mobious values for <span class="math-container">$m &lt; n $</span>. Hence
<span class="math-container">$$\mu (n) =1-\sum_{m &lt; n} \left \lfloor \dfrac {n}{m}\right \rfloor \mu (m) .$$</span>
Here we are dividing <span class="math-container">$n$</span> by the smaller  positive integers <span class="math-container">$m&lt;n$</span>, we don't have to know if they are factors of <span class="math-container">$n$</span> when <span class="math-container">$m$</span> has a square factor! ( <span class="math-container">$\mu(m)=0$</span>) ,But still we have to know the factors of <span class="math-container">$m$</span> to conclude this!!
Hence we have: 
<span class="math-container">\begin{align}
\mu(n)=&amp;1-\sum_{a_1&lt; n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \\
+&amp;\sum_{a_1&lt; n} \left \lfloor \dfrac {n}{a_1}\right \rfloor \sum_{a_2&lt; a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor  \\
-&amp;\sum_{a_1&lt; n} \left \lfloor \dfrac {n}{a_1}\right \rfloor
\sum_{a_2&lt; a_1} \left \lfloor \dfrac {a_1}{a_2}\right \rfloor \sum_{a_3&lt; a_2} \left \lfloor \dfrac {a_2}{a_3}\right \rfloor  + \cdots
\end{align}</span>
Refer to this paper: <a href="https://projecteuclid.org/euclid.mjms/1513306829" rel="nofollow noreferrer">https://projecteuclid.org/euclid.mjms/1513306829</a> for the proof of the formula.</p>

CC BY-SA 4.0
2019-07-07T04:35:20.940Z
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.
Craig Feinstein
CC BY-SA 4.0
2019-07-19T22:14:02.250Z
Check the edited version!! @Craig
Hunde Eba
CC BY-SA 4.0
2019-07-05T14:59:16.070Z
2019-07-20T17:05:19.717Z
2019-07-20T17:05:19.717Z
Hunde Eba
<p>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$.</p>

<p>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.</p>

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

CC BY-SA 3.0
2011-12-04T18:48:06.287Z
This doesn't appear right at all. Define "the same thing as". I wonder why this answer was accepted.
Michael Blondin
CC BY-SA 3.0
2011-12-04T19:05:35.303Z
@Michael I asked the question. I thought about it for a while, came up with an answer, and accepted my own answer. Have you got a better answer? "The same thing as" in the context above means that if you compute $\mu(n)$, then you also compute $\mu(p_1)\dots \mu(p_k)$, since they are equal values.
Craig Feinstein
CC BY-SA 3.0
2011-12-04T19:09:31.270Z
I don't, but the two other answers are. Right, but why do you assume that in order to compute $\mu(p_1) \cdots \mu(p_k)$ "you have to know that each $p_j$ is prime"? That's basically your initial question.
Michael Blondin
CC BY-SA 3.0
2011-12-04T19:40:31.503Z
I changed my answer a quite a bit to make things clearer, I hope.
Craig Feinstein
CC BY-SA 3.0
2011-12-04T19:48:58.850Z
And why wouldn't a similar argument show that telling a number is composite is equivalent to factoring?
Peter Shor 
CC BY-SA 3.0
2011-12-04T20:18:02.723Z
@Peter The difference between computing the Mobius function and determining whether a number is composite is that it is part of the definition of a Mobius function that one has to compute each $\mu(q_j)$, where each $q_j$ is a prime power and a factor of $n$. The definition of whether a number of composite only concerns whether there are nontrivial factors of the number. You don't have to compute the factors to gain this information.
Craig Feinstein
CC BY-SA 3.0
2011-12-04T20:31:52.447Z
I just updated it again.
Craig Feinstein
CC BY-SA 3.0
2011-12-04T21:03:48.823Z
@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.
Michael Blondin
CC BY-SA 3.0
2011-12-04T22:04:06.113Z
Changed this again. Hopefully the last time.
Craig Feinstein
CC BY-SA 3.0
2011-12-04T22:09:12.827Z
This is the same fallacious argument again. It is not the sole identity. Moreover, the "free independent variable" argument doesn't mean much. I shall stop arguing your answer to be wrong. Please, try to see where it fails. Good luck!
Michael Blondin
CC BY-SA 3.0
2011-12-04T23:40:09.477Z
I unchecked it as "the answer", because I would like to see a better answer. I don't see how my argument is fallacious though. Also, I changed my argument slightly.
Craig Feinstein
CC BY-SA 3.0
2011-12-04T23:57:17.990Z
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.
Michael Blondin
CC BY-SA 3.0
2011-12-05T00:37:50.967Z
let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/1917/discussion-between-craig-feinstein-and-michael-blondin)
Craig Feinstein
CC BY-SA 3.0
2011-12-06T07:10:29.283Z
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.
David Eppstein
CC BY-SA 3.0
2011-12-06T13:31:46.603Z
@David That's still counting: 1,2,1,2,1,2...
Craig Feinstein
CC BY-SA 3.0
2011-12-07T02:51:46.627Z
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.
Peter Shor 
CC BY-SA 3.0
2011-12-07T03:04:10.800Z
@PeterShor that is true, but you can't do anything like this for computing the Mobius function, as this is more difficult than finding the parity of the number of jelly beans in a jar, since even if you have the factors of the number, you still have to count them (you can count 1,2,1,2,... if you want). There's simply no mathematical structure that you can take advantage of here, as you can with computing the parity of the permanent of a matrix.
Craig Feinstein
CC BY-SA 3.0
2011-12-07T03:08:47.623Z
@Craig: But how do you know there's no mathematical structure that you can take advantage of here, that we just don't know about yet? That's the big source of difficulty in complexity theory.
Peter Shor 
CC BY-SA 3.0
2011-12-07T04:01:40.370Z
@PeterShor You know this the same way you know that there is no mathematical structure that you can take advantage of when determining the parity of the number of jelly beans in a jar. They are the exact same problem except one is concrete and the other is abstract.
Craig Feinstein
CC BY-SA 3.0
2011-12-08T18:14:58.783Z
The analogy is wrong. To check if every flavour of jelly occurs even number of times, you have to look at all beans to be sure. To check if a number is a perfect square, you don't need to factor it.
sdcvvc
CC BY-SA 3.0
2011-12-08T18:17:30.920Z
If you want to check if a number is even, you do not have to compute the complete factorization. If you want to check if a jar contains some specific flavour, you have to check all beans to be sure.
sdcvvc
CC BY-SA 3.0
2011-12-08T20:19:20.933Z
@sdcvvc, can you prove that 4761 is a perfect square without factoring it?
Craig Feinstein
CC BY-SA 3.0
2011-12-08T20:42:37.200Z
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.
sdcvvc
CC BY-SA 3.0
2011-12-08T21:10:34.683Z
You are correct @sdcvvc. Good catch! I'll erase that analogy.
Craig Feinstein
CC BY-SA 3.0
2011-12-04T17:19:18.427Z
2011-12-08T21:12:43.180Z
2011-12-08T21:12:43.180Z
Craig Feinstein
<p>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$?</p>

CC BY-SA 3.0
2011-11-29T16:20:57.230Z
What do you mean by "Is it possible to compute $\mu(n)$ without computing the prime factorization of n?", are you asking if we can prove that factorization is not polynomial time reducible to $\mu$? (in which case the answer is no, we don't have even polynomial lowerbounds for factoring.) If you have something else in mind state it more preciously, otherwise the question cannot be answered because of vagueness.
Kaveh
CC BY-SA 3.0
2011-11-29T16:41:17.040Z
I think he's merely asking if there's a way to compute $\mu(n)$ that is not known to also provide a factorization.
Suresh Venkat
CC BY-SA 3.0
2011-11-29T17:47:06.500Z
@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?
Craig Feinstein
CC BY-SA 3.0
2011-12-05T00:08:00.497Z
@Suresh, I don't think that is what the question is asking. If that is the question, the post should be updated to state a clear and answerable question. In its current form it is not answerable IMHO. ps: I think the answer posted by OP shows that the intention was not asking about what is *known*.
Kaveh
CC BY-SA 3.0
2011-12-05T00:09:22.803Z
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](http://meta.cstheory.stackexchange.com/questions/274/is-it-ok-to-ask-about-the-correctness-of-preprints-on-crank-friendly-topics) in case you try to advertise the ideas in [these](http://arxiv.org/find/cs/1/au:+Feinstein_C/0/1/0/all/0/1).
Kaveh
CC BY-SA 3.0
2011-12-05T00:59:21.937Z
@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.
Craig Feinstein
CC BY-SA 3.0
2011-12-05T01:06:57.600Z
Sorry if I misjudged. You stated that you agree with Suresh's interpretation of your question but later your actions didn't seem consistent with that interpretation. I still think the question is not clear enough to get answered. It is not clear (at least to me) what would constitute an acceptable answer to the question. By not a real question I mean "*It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form.*"
Kaveh
CC BY-SA 3.0
2011-12-05T01:12:59.850Z
I think my answer to my question is completely consistent with Suresh's interpretation of my question, which I claim is the correct interpretation. How is my answer not consistent?
Craig Feinstein
CC BY-SA 3.0
2011-12-05T02:45:17.700Z
@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."
Aaron Sterling
CC BY-SA 3.0
2011-12-05T02:53:42.440Z
@Aaron, no, I haven't. My point is the question is not clear. I don't understand what is the meaning of "Is it possible to compute X without computing the Y?" If it is in the sense that Suresh explained the answer cannot be a negative i.e. there is not one. To give a negative answer one should define *mathematically* what it means to compute X without computing Y, and that is all I am asking for.
Kaveh
CC BY-SA 3.0
2011-12-05T02:57:13.493Z
@Aaron, ps: as a side note, I think questions where the OP has trouble in understanding basic material are more suitable for [Math.SE].
Kaveh
CC BY-SA 3.0
2011-12-05T02:59:19.747Z
Craig, please see my reply to Aaron above for the explanation why I think your answer is inconsistent with Suresh's interpretation.
Kaveh
CC BY-SA 3.0
2011-12-05T16:14:20.760Z
@Kaveh, it is known that it is possible to determine that a number is composite without computing its factors. My question was whether this is also the case for computing the Mobius function for a number. My answer shows that this is not the case when the number is not divisible by a square.
Craig Feinstein
CC BY-SA 3.0
2011-12-05T16:14:29.123Z
@Aaron, an angle trisector is someone who makes claims that run counter to well-known mathematics theorems. I have never done this.
Craig Feinstein
CC BY-SA 3.0
2011-12-05T18:47:33.057Z
What is known is that we have an algorithm for Primality which is in $\mathsf{P}$ and we don't haven't yet found a polytime algorithm for Factoring, nothing more, the fact that the promality algorithm doesn't explicitly compute factors doesn't say anything and is not a robust mathematical definition. If you are asking for the similar situation, then your question should be "Do we have a polynomial time algorithm for computing $\mu$?" which then Suresh's post answer your question, i.e. it is not known that it is possible to compute it in polytime. As long as you don't mathematically define
Kaveh
CC BY-SA 3.0
2011-12-05T18:49:01.993Z
"Is it possible to compute X without computing the Y?" there is not way to answer the question about the existence of such an algorithm negatively.
Kaveh
CC BY-SA 3.0
2017-01-03T11:29:38.873Z
I agree with Kaveh.  First, one must formalize the notion of "computing X without computing Y".   We sometimes informally speak about this, but to my knowledge, nobody has created a useful rigorous definition.
Jeffrey Shallit
CC BY-SA 3.0
2017-01-04T02:21:36.407Z
I agree that paradoxes can occur if one is too informal with the definition of "compute X". I found one here: https://arxiv.org/pdf/cs/0310060v19.pdf however, in this particular problem, I don't see any harm in being informal.
Craig Feinstein
CC BY-SA 3.0
2017-01-04T17:17:23.553Z
It has nothing to do with paradoxes at all, real or imagined.  If one cannot give a formal definition of "computing X without computing Y", then perhaps it is not a meaningful statement at all.
Jeffrey Shallit
CC BY-SA 3.0
2017-01-04T18:43:55.193Z
OK, "computing $\mu(n)$" means to determine the value of $\mu(n)$ when given $n$ in say binary. And "computing the prime factorization of $n$" (when $n=p_1 p_2 \dots p_m$) means to determine the values of each $p_i$, determine that $n=p_1 p_2 \dots p_m$, and also determine that each $p_i$ is prime.
Craig Feinstein
CC BY-SA 3.0
2017-01-04T20:13:35.247Z
You don't seem to understand the point.  Everyone knows what it means to compute X.  But what does "without computing Y" mean?
Jeffrey Shallit
CC BY-SA 3.0
2017-01-04T20:40:32.750Z
"without computing Y" is the negation of "computing Y".
Craig Feinstein
CC BY-SA 3.0
2017-01-06T18:24:17.560Z
That makes no sense at all.  For example, to compute something means to write it out on an output tape of a Turing machine.  But computing mu(n), even by factorization of n, might never involve writing out the factors of n on an output tape.  You need to think much more carefully and deeply to avoid nonsense.
Jeffrey Shallit
CC BY-SA 3.0
2017-01-06T19:34:50.920Z
@JeffreyShallit I never used the notion of a Turing machine in my definition I gave above for "compute X", so your statement doesn't make sense to me.
Craig Feinstein
CC BY-SA 3.0
2017-01-06T20:07:37.457Z
OK, I can see this discussion is pointless.
Jeffrey Shallit
CC BY-SA 4.0
2019-07-07T04:44:34.670Z
@JeffreyShallit I am not sure why you left the discussion prematurely. Turing machine is one out of many models of computation that are basically all equivalent to one another. I think it is possible to talk about the notion of computation without being as technical as you are demanding. You seem to believe that it is impossible to have a discussion about mathematics in natural language.
Craig Feinstein
CC BY-SA 4.0
2019-07-08T05:05:57.340Z
I can only repeat my previous comment.   Until you have a rigorous definition of "compute x without computing y", there is no point in continuing this discussion.
Jeffrey Shallit
CC BY-SA 4.0
2019-07-18T20:58:54.760Z
Try this formulation of the question: "Is computing the Mobius function of an integer at least as hard as factoring the integer?"
Craig Feinstein
CC BY-SA 4.0
2019-07-21T12:26:57.377Z
Nobody knows currently.
Jeffrey Shallit
CC BY-SA 4.0
2019-07-21T15:33:25.653Z
Are you sure? How do you know?
Craig Feinstein
<comp-number-theory>
Computing the Mobius function
Craig Feinstein
# Computing the Mobius function

(Asked by: username_0 on 2011-11-29)

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

**Tags:** comp-number-theory

> **Comments:**
> **username_1**: What do you mean by "Is it possible to compute $\mu(n)$ without computing the prime factorization of n?", are you asking if we can prove that factorization is not polynomial time reducible to $\mu$? (in which case the answer is no, we don't have even polynomial lowerbounds for factoring.) If you have something else in mind state it more preciously, otherwise the question cannot be answered because of vagueness.  
> **username_2**: I think he's merely asking if there's a way to compute $\mu(n)$ that is not known to also provide a factorization.  
> **username_0**: @username_1, 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?  
> **username_1**: @Suresh, I don't think that is what the question is asking. If that is the question, the post should be updated to state a clear and answerable question. In its current form it is not answerable IMHO. ps: I think the answer posted by OP shows that the intention was not asking about what is *known*.  
> **username_1**: 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](http://meta.cstheory.stackexchange.com/questions/274/is-it-ok-to-ask-about-the-correctness-of-preprints-on-crank-friendly-topics) in case you try to advertise the ideas in [these](http://arxiv.org/find/cs/1/au:+Feinstein_C/0/1/0/all/0/1).  
> **username_0**: @username_1, 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.  
> **username_1**: Sorry if I misjudged. You stated that you agree with Suresh's interpretation of your question but later your actions didn't seem consistent with that interpretation. I still think the question is not clear enough to get answered. It is not clear (at least to me) what would constitute an acceptable answer to the question. By not a real question I mean "*It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form.*"  
> **username_0**: I think my answer to my question is completely consistent with Suresh's interpretation of my question, which I claim is the correct interpretation. How is my answer not consistent?  
> **username_3**: @username_1: 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."  
> **username_1**: @Aaron, no, I haven't. My point is the question is not clear. I don't understand what is the meaning of "Is it possible to compute X without computing the Y?" If it is in the sense that Suresh explained the answer cannot be a negative i.e. there is not one. To give a negative answer one should define *mathematically* what it means to compute X without computing Y, and that is all I am asking for.  
> **username_1**: @Aaron, ps: as a side note, I think questions where the OP has trouble in understanding basic material are more suitable for [Math.SE].  
> **username_1**: Craig, please see my reply to Aaron above for the explanation why I think your answer is inconsistent with Suresh's interpretation.  
> **username_0**: @username_1, it is known that it is possible to determine that a number is composite without computing its factors. My question was whether this is also the case for computing the Mobius function for a number. My answer shows that this is not the case when the number is not divisible by a square.  
> **username_0**: @Aaron, an angle trisector is someone who makes claims that run counter to well-known mathematics theorems. I have never done this.  
> **username_1**: What is known is that we have an algorithm for Primality which is in $\mathsf{P}$ and we don't haven't yet found a polytime algorithm for Factoring, nothing more, the fact that the promality algorithm doesn't explicitly compute factors doesn't say anything and is not a robust mathematical definition. If you are asking for the similar situation, then your question should be "Do we have a polynomial time algorithm for computing $\mu$?" which then Suresh's post answer your question, i.e. it is not known that it is possible to compute it in polytime. As long as you don't mathematically define  
> **username_1**: "Is it possible to compute X without computing the Y?" there is not way to answer the question about the existence of such an algorithm negatively.  
> **username_4**: I agree with username_1.  First, one must formalize the notion of "computing X without computing Y".   We sometimes informally speak about this, but to my knowledge, nobody has created a useful rigorous definition.  
> **username_0**: I agree that paradoxes can occur if one is too informal with the definition of "compute X". I found one here: https://arxiv.org/pdf/cs/0310060v19.pdf however, in this particular problem, I don't see any harm in being informal.  
> **username_4**: It has nothing to do with paradoxes at all, real or imagined.  If one cannot give a formal definition of "computing X without computing Y", then perhaps it is not a meaningful statement at all.  
> **username_0**: OK, "computing $\mu(n)$" means to determine the value of $\mu(n)$ when given $n$ in say binary. And "computing the prime factorization of $n$" (when $n=p_1 p_2 \dots p_m$) means to determine the values of each $p_i$, determine that $n=p_1 p_2 \dots p_m$, and also determine that each $p_i$ is prime.  
> **username_4**: You don't seem to understand the point.  Everyone knows what it means to compute X.  But what does "without computing Y" mean?  
> **username_0**: "without computing Y" is the negation of "computing Y".  
> **username_4**: That makes no sense at all.  For example, to compute something means to write it out on an output tape of a Turing machine.  But computing mu(n), even by factorization of n, might never involve writing out the factors of n on an output tape.  You need to think much more carefully and deeply to avoid nonsense.  
> **username_0**: @JeffreyShallit I never used the notion of a Turing machine in my definition I gave above for "compute X", so your statement doesn't make sense to me.  
> **username_4**: OK, I can see this discussion is pointless.  
> **username_0**: @JeffreyShallit I am not sure why you left the discussion prematurely. Turing machine is one out of many models of computation that are basically all equivalent to one another. I think it is possible to talk about the notion of computation without being as technical as you are demanding. You seem to believe that it is impossible to have a discussion about mathematics in natural language.  
> **username_4**: I can only repeat my previous comment.   Until you have a rigorous definition of "compute x without computing y", there is no point in continuing this discussion.  
> **username_0**: Try this formulation of the question: "Is computing the Mobius function of an integer at least as hard as factoring the integer?"  
> **username_4**: Nobody knows currently.  
> **username_0**: Are you sure? How do you know?  

---

## 4 answers

### Answer by username_2 on 2011-11-29. Score: 34

One non-answer to your question is that [SQUARE-FREE](http://mathworld.wolfram.com/Squarefree.html) (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$).

> **Comments:**
> **username_5**: do you know any papers that discuss the complexity of square-freeness? all i could find is this: http://dl.acm.org/citation.cfm?id=371327&dl=GUIDE&coll=GUIDE, which gives formula size lower bounds. looking at http://mathoverflow.net/questions/16098/complexity-of-testing-integer-square-freeness, i think not much is known about whether it's likely to be able to reduce factoring to square freeness.  

---

### Answer by username_6 on 2011-12-01. Score: 15

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](http://arxiv.org/abs/1103.4991)), and all monotone functions (proved by [Jean Bourgain](http://arxiv.org/abs/1112.1423)).

> **Comments:**
> **username_2**: I think this is the Ben Green paper: http://arxiv.org/abs/1103.4991  

---

### Answer by username_7 on 2019-07-05. Score: 0

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.

> **Comments:**
> **username_0**: 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.  
> **username_7**: Check the edited version!! @Craig  

---

### Answer by username_0 on 2011-12-04. Score: -22

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

> **Comments:**
> **username_8**: This doesn't appear right at all. Define "the same thing as". I wonder why this answer was accepted.  
> **username_0**: @Michael I asked the question. I thought about it for a while, came up with an answer, and accepted my own answer. Have you got a better answer? "The same thing as" in the context above means that if you compute $\mu(n)$, then you also compute $\mu(p_1)\dots \mu(p_k)$, since they are equal values.  
> **username_8**: I don't, but the two other answers are. Right, but why do you assume that in order to compute $\mu(p_1) \cdots \mu(p_k)$ "you have to know that each $p_j$ is prime"? That's basically your initial question.  
> **username_0**: I changed my answer a quite a bit to make things clearer, I hope.  
> **username_9**: And why wouldn't a similar argument show that telling a number is composite is equivalent to factoring?  
> **username_0**: @Peter The difference between computing the Mobius function and determining whether a number is composite is that it is part of the definition of a Mobius function that one has to compute each $\mu(q_j)$, where each $q_j$ is a prime power and a factor of $n$. The definition of whether a number of composite only concerns whether there are nontrivial factors of the number. You don't have to compute the factors to gain this information.  
> **username_0**: I just updated it again.  
> **username_8**: @Craig It is still wrong. You could use the same (fallacious) argument for the composite testing problem as username_9said. 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.  
> **username_0**: Changed this again. Hopefully the last time.  
> **username_8**: This is the same fallacious argument again. It is not the sole identity. Moreover, the "free independent variable" argument doesn't mean much. I shall stop arguing your answer to be wrong. Please, try to see where it fails. Good luck!  
> **username_0**: I unchecked it as "the answer", because I would like to see a better answer. I don't see how my argument is fallacious though. Also, I changed my argument slightly.  
> **username_8**: 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.  
> **username_0**: let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/1917/discussion-between-craig-feinstein-and-michael-blondin)  
> **username_10**: 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.  
> **username_0**: @David That's still counting: 1,2,1,2,1,2...  
> **username_9**: 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.  
> **username_0**: @PeterShor that is true, but you can't do anything like this for computing the Mobius function, as this is more difficult than finding the parity of the number of jelly beans in a jar, since even if you have the factors of the number, you still have to count them (you can count 1,2,1,2,... if you want). There's simply no mathematical structure that you can take advantage of here, as you can with computing the parity of the permanent of a matrix.  
> **username_9**: @Craig: But how do you know there's no mathematical structure that you can take advantage of here, that we just don't know about yet? That's the big source of difficulty in complexity theory.  
> **username_0**: @PeterShor You know this the same way you know that there is no mathematical structure that you can take advantage of when determining the parity of the number of jelly beans in a jar. They are the exact same problem except one is concrete and the other is abstract.  
> **username_11**: The analogy is wrong. To check if every flavour of jelly occurs even number of times, you have to look at all beans to be sure. To check if a number is a perfect square, you don't need to factor it.  
> **username_11**: If you want to check if a number is even, you do not have to compute the complete factorization. If you want to check if a jar contains some specific flavour, you have to check all beans to be sure.  
> **username_0**: @username_11, can you prove that 4761 is a perfect square without factoring it?  
> **username_11**: 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.  
> **username_0**: You are correct @username_11. Good catch! I'll erase that analogy.  

---

