Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Maybe i should move this to MathOverflow –  Roupam Ghosh Jan 31 '11 at 9:15
add comment

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

share|improve this answer
    
+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
add comment
up vote 1 down vote accepted

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

share|improve this answer
    
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
2  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.