Difference between revisions of "Mobius function"

(Added a property of being multiplicative with a proof)
Line 29: Line 29:
 
Proof:If <math>n=1</math> or <math>p^2|n</math> for a prime <math>p</math>, we are done.Else let <math>m=\prod_{j=1}^{k} {p_j}</math> and <math>n=\prod_{i=1}^{h} {q_i}</math> where <math>gcd(m,n)=1</math>,then <math>\mu(m)\mu(n)=(-1)^{k} (-1)^{h}=(-1)^{k+h}=\mu(mn)</math>.
 
Proof:If <math>n=1</math> or <math>p^2|n</math> for a prime <math>p</math>, we are done.Else let <math>m=\prod_{j=1}^{k} {p_j}</math> and <math>n=\prod_{i=1}^{h} {q_i}</math> where <math>gcd(m,n)=1</math>,then <math>\mu(m)\mu(n)=(-1)^{k} (-1)^{h}=(-1)^{k+h}=\mu(mn)</math>.
  
 +
Property 2:If <math>F(n)=\sum_{d|n} f(d)</math> for every positive integer <math>n</math>, then <cmath>f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})</cmath>.
 +
Proof:We have <cmath>\sum_{d|n}\mu(d)F(\frac{n}{d})=\sum_{d|n}\mu(d)\sum_{k|n/d}f(k)=\sum_{k|n}\sum_{d|n/k}\mu(d)f(k)
 +
 +
=\sum_{k|n}f(k)\sum_{d|n/d}\mu(d)= f(n)</cmath> .
  
 
The Mobius function is also closely related to the [[Riemann zeta function]], as
 
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>
 
<cmath>\frac{1}{\zeta(s)} = \sum \frac{\mu(k)}{n^s}.</cmath>

Revision as of 02:46, 12 March 2012

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}\]

Property 1: The function $\mu(n)$ is multiplicative .

Proof:If $n=1$ or $p^2|n$ for a prime $p$, we are done.Else let $m=\prod_{j=1}^{k} {p_j}$ and $n=\prod_{i=1}^{h} {q_i}$ where $gcd(m,n)=1$,then $\mu(m)\mu(n)=(-1)^{k} (-1)^{h}=(-1)^{k+h}=\mu(mn)$.

Property 2:If $F(n)=\sum_{d|n} f(d)$ for every positive integer $n$, then \[f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})\].

Proof:We have

\[\sum_{d|n}\mu(d)F(\frac{n}{d})=\sum_{d|n}\mu(d)\sum_{k|n/d}f(k)=\sum_{k|n}\sum_{d|n/k}\mu(d)f(k)

=\sum_{k|n}f(k)\sum_{d|n/d}\mu(d)= f(n)\] (Error compiling LaTeX. Unknown error_msg)

.

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