On the Möbius $\mu$ function

A search on wikipedia shows: $$\mu(n) = \sum_{k=1,gcd(k,n)=1}^{n} e^{2\pi i \frac{k}{n}}$$ But that uses complex numbers... and requires finding out the gcd...

How useful will be a method, if that could find the exact value for $\mu(n)$ function, by just knowing all the values from $\mu(1)$ till $\mu(n-1)$, which does not require factoring any integer and which uses only elementary methods?

Has this been done before? My question is more precisely:

Does any such formula exist?

-
Maybe i should move this to MathOverflow –  Roupam Ghosh Jan 31 '11 at 9:15

2 Answers

(This should be a comment.)

FWIW, you can derive from the series you gave the alternative representation

$$\mu(n)=\sum_{j=1}^n [\gcd(n,k)=1]\cos\left(\frac{2\pi k}{n}\right)$$

where $[p]$ is an Iversonian bracket for the condition $p$.

Since checking if a number is squarefree is conjectured to be at least as hard as straight factorization, I don't have much hope of an algorithm of the sort you want existing. (If there is, I too would be interested in hearing about it. ;) )

-
+1 For letting me know that checking a number is squarefree is as hard as straight factorization. –  Roupam Ghosh Jan 31 '11 at 9:28
I think I have such a formula. But I'll let you know once I find a proof of it and verify that its really correct. ;) –  Roupam Ghosh Jan 31 '11 at 9:51

The Möbius mu function is denoted by $\mu(x)$. Another function that I got while studying Dirichlet eta function $$\nu(x) = \rho\left(\frac{x}{2}\right)+\frac{1}{2} - \rho\left(\frac{x}{2}+ \frac{1}{2}\right)$$ where, $\rho(x)$ is the fractional part of $x$. Observe $\nu(x)$ only takes the values $0$ and $1$

While working with a criterion (equivalent to the Nyman-Beurling approach) for Dirichlet eta function, I observed, $$\sum_{k=1}^{n} \mu(k) \nu(n/k) = -1$$ for all $n \geq 2$

It has given me a recursive algorithm to calculate $\mu$ since calculating $\nu$ is much easier. We start with $$f_1(x) = \nu(x)$$ $$f_n(x) = f_{n-1}(x) + \mu(n)\nu(x/n)$$ Then, $$\mu(n) = -1 - f_{n-1}(n)$$

-
You could just have used $\sum_{d \mid n} \mu(d) = 0$. Checking if $d$ divides $n$ is same as confirming that the fractional part of $n/d$ is $0$. –  Aryabhata Feb 1 '11 at 3:34
Yea. That makes sense. But, doesnt that require factorization at some point? –  Roupam Ghosh Feb 1 '11 at 4:26
No. It only involves division/remainder finding, just like your fractional part computation:basically check if $\rho(n/d) = 0$. I would not call that factorization. Also, if you are going to iterate 1 to n anyway, then you can also do the factorization. In fact, if an algorithm for "fast" factorization exists, that would probably be quicker than what you have! –  Aryabhata Feb 1 '11 at 4:51
+1 I knew $\sum_{d|n} \mu(d) = 0$. But never thought of it that way. Thanks for your point of view. –  Roupam Ghosh Feb 1 '11 at 5:53