5
$\begingroup$

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?

  • 0
    Maybe i should $m$ove this to MathOverflow2011-01-31

2 Answers 2

1

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

  • 0
    +1 I knew $\sum_{d|n} \mu(d) = 0$. But never thought of it that way. Thanks for your point of view.2011-02-01
2

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

  • 0
    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. ;)2011-01-31