Difference between revisions of "Mobius function"

Line 23: Line 23:
  
 
One unique fact about the Mobius function, which leads to the Mobius inversion formula, is that
 
One unique fact about the Mobius function, which leads to the Mobius inversion formula, is that
<cmath>\sum_{d|n} mu(d) = \begin{cases} 1 & n = 1, \\ (0 & otherwise. \end{cases}</cmath>
+
<cmath>\sum_{d|n} \mu(d) = \begin{cases} 1 & n = 1, \\ 0 & \text{otherwise}. \end{cases}</cmath>
 +
 
 +
The Mobius function is also closely related to the [[Riemann zeta function]], as
 +
<cmath>\frac{1}{\zeta(s)} = \sum \frac{\mu(k)}{n^s}.</cmath>

Revision as of 19:44, 26 January 2011

The Mobius function is a multiplicative number theoretic function defined as follows: \[\mu(n) = \begin{cases} 0 & d^2 | n, \\ (-1)^k & n = p_1p_2\cdots{p_k} .\end{cases}\] In addition, $\mu(1) = 1$.

The Mobius function is useful for a variety of reasons.

First, it conveniently encodes Principle of Inclusion-Exclusion. For example, to count the number of positive integers less than or equal to $n$ and relatively prime to $n$, we have

$\phi(n)$ $=n$
$- \frac{n}{p_1} - \frac{n}{p_2} - \cdots - \frac{n}{p_k}$
$+ \frac{n}{p_1p_2} + \frac{n}{p_1p_3} + \cdots + \frac{n}{p_{k-1}p_k}$
$\vdots$
$+ (-1)^k \frac{n}{p_1 p_2 \cdots p_k},$

more succinctly expressed as \[\phi(n) = \sum_{d|n} \mu(d) \frac{n}{d}.\]

One unique fact about the Mobius function, which leads to the Mobius inversion formula, is that \[\sum_{d|n} \mu(d) = \begin{cases} 1 & n = 1, \\ 0 & \text{otherwise}. \end{cases}\]

The Mobius function is also closely related to the Riemann zeta function, as \[\frac{1}{\zeta(s)} = \sum \frac{\mu(k)}{n^s}.\]