Difference between revisions of "Mobius function"

Latest revision as of 01:58, 1 March 2022

The Möbius function is a multiplicative number theoretic function defined as follows: $\mu(n) = \begin{cases} 1 &\text{if}~n=1\\ 0 & \text{if}~n~\text{has a square factor} \\ (-1)^k & n = p_1p_2\cdots{p_k} .\end{cases}$ Hence, we see that $\mu(5)=-1$ , $\mu(8)=0$ and $\mu(6)=1$ .

Multiplicity of the Function

One of the most important results of the Möbius function is that it is multiplicative, or that $\mu(ab)=\mu(a)\mu(b)$ .

Proof. Let $\left[\frac{n}{a}\right]$ denote the number of integers not greater than $n$ and divisible by $a$ . If $a$ and $b$ are coprime then $\left[\frac{n}{ab}\right]$ denotes the number of integers not greater than $n$ and divisible by $a$ and $b$ . Via a combinatorial argument using the Principle of Inclusion-Exclusion (PIE), it can be seen that the number of integers less than or equal to $n$ and not divisible by any one of a coprime set of integers $a_1,a_2,\ldots$ is

$\left[n\right]-\sum\left[\frac{n}{a_1}\right]+\sum\left[\frac{n}{a_1a_2}\right]-\ldots$ .

and by taking the coprime set of integers $a_1,a_2,\ldots$ to be the different (and distinct) prime factors of $n$ we get

$\phi(n)=n-\sum\left[\frac{n}{p}\right]+\sum\left[\frac{n}{pp'}\right]-\ldots=n\prod_{p|n}\left(1-\frac{1}{p}\right)$ .

Now the proof of the multiplicity of $\mu(n)$ comes naturally from its definition and what we previously established. We see that

$\phi(n)=n\sum_{d|n}\frac{\mu(d)}{d}=\sum_{d|n}\frac{n\mu(d)}{d}=\sum_{d|n}d\mu\left(\frac{n}{d}\right)=\sum_{dd'=n}d'\mu(d)$

completing the proof $\square$

Sums of Divisors

While the multiplicity of the Möbius function is its most crucial component, there are other relationships that we can draw from as well. One of the most notable is the following: $\sum_{d|n}\mu(d) = \begin{cases} 1 &\text{if}~n=1\\ 0 & \text{if}~n>1.\end{cases}$

Proof.If $n=p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}$ where $k\ge 1$ then

$\sum_{d|n}\mu(d)=1+\sum_{i}\mu{p_i}+\sum_{i,j}\mu(p_ip_j)+\ldots=1-k+\binom{k}{2}-\binom{k}{3}-\ldots=(1-1)^k=0^k=0$ .

To finish, we simply can use the fact that $\mu(1)=1$ , completing the proof. By a similar argument, one can also prove that

$\sum_{d|n}|\mu(d)|=2^k$

where $k$ is the number of distinct prime factors of $n$ $\square$

Implications to Other Functions

Let $f(n)$ be a multiplicative function with respect to $n$ . If there is such an $f$ , then

$g(n)=\sum_{d|n}f(d)$

is also multiplicative.

Proof. If, for some $m$ , that $\gcd(n,m)=1$ , $d_1|n$ and $d_2|m$ then $\gcd(d_1,d_2)=1$ and $c=d_1d_2$ runs through all divisors of $nm$ . This means we have

$g(mn)=\sum_{c|nm}f(c)=\sum_{d_1|n,d_2|m}f(d_1d_2)=\sum_{d_1|n}f(d_1)\sum_{d_2|m}f(d_2)=g(n)g(m)$

which completes the proof. On a different note, this also provides an alternative proof for the theorem we proved earlier. By letting

$g(n)=\sum_{d|n}\mu(d)$

the result follows by taking $g(1)$ and $g(p^k)$ for $k\ge 1$ $\square$

Applications

One of the major uses of the Möbius function is in the Mobius inversion formula. It also has ties to the Riemann zeta function, mainly that for $s>1$ ,

$\frac{1}{\zeta(s)}=\sum_{n=1}^{\infty}\frac{\mu(n)}{n^s}$ .

This comes from a couple of theorems. Firstly, if $s>1$ then

$\zeta(s)=\prod_{p}\frac{1}{1-p^{-s}}$ .

Secondly, if $f$ is an arithmetic function such that $f(1)=1$ and $f(n)$ is multiplicative such that $\sum |f(n)|n^{-s}$ is convergent, then

$F(s)=\sum f(n)n^{-s}=\prod_{p}\{1+f(p)p^{-s}+f(p^2)p^{-2s}+\ldots\}.$

Our theorem follows by using the multiplicity of $\mu(n)$ lastly. Doing so gives

$\frac{1}{\zeta(s)}=\prod_{p}(1-p^{-s})=\prod_{p}\{1+\mu(p)p^{-s}+\mu(p^2)p^{-2s}+\ldots\}=\sum_{n=1}^{\infty}\mu(n)n^{-s}=\sum_{n=1}^{\infty}\frac{\mu(n)}{n^{s}}$

which is what we wanted. The reason why this is important is because we can do more things by using this as a baseline. For example, it follows trivially that for $s>2$

$\frac{\zeta(s-1)}{\zeta(s)}=\sum_{n=1}^{\infty}\frac{\phi(n)}{n^s}$ .

@@ Line 1: / Line 1: @@
-The Mobius function is a multiplicative number theoretic function defined as follows:
+The '''Möbius function''' is a multiplicative number theoretic function defined as follows:
-<cmath>\mu(n) = \begin{cases} 0 & d^2 | n, \\ (-1)^k & n = p_1p_2\cdots{p_k} .\end{cases}</cmath>
+<cmath>\mu(n) = \begin{cases} 1 &\text{if}~n=1\\ 0 & \text{if}~n~\text{has a square factor} \\ (-1)^k & n = p_1p_2\cdots{p_k} .\end{cases}</cmath>
-In addition, <math>\mu(1) = 1</math>.
+Hence, we see that <math>\mu(5)=-1</math>, <math>\mu(8)=0</math> and <math>\mu(6)=1</math>.
+==Multiplicity of the Function==
+One of the most important results of the Möbius function is that it is multiplicative, or that <math>\mu(ab)=\mu(a)\mu(b)</math>.
-The Mobius function is useful for a variety of reasons.
+''Proof.'' Let <math>\left[\frac{n}{a}\right]</math> denote the number of integers not greater than <math>n</math> and divisible by <math>a</math>.  If <math>a</math> and <math>b</math> are coprime then <math>\left[\frac{n}{ab}\right]</math> denotes the number of integers not greater than <math>n</math> and divisible by <math>a</math> and <math>b</math>.  Via a combinatorial argument using the [[Principle of Inclusion-Exclusion]] (PIE), it can be seen that the number of integers less than or equal to <math>n</math> and not divisible by any one of a coprime set of integers <math>a_1,a_2,\ldots</math> is
+<center><math>\left[n\right]-\sum\left[\frac{n}{a_1}\right]+\sum\left[\frac{n}{a_1a_2}\right]-\ldots</math>.</center>
+and by taking the coprime set of integers <math>a_1,a_2,\ldots</math> to be the different (and distinct) prime factors of <math>n</math> we get
+<center><math>\phi(n)=n-\sum\left[\frac{n}{p}\right]+\sum\left[\frac{n}{pp'}\right]-\ldots=n\prod_{p|n}\left(1-\frac{1}{p}\right)</math>.</center>
+Now the proof of the multiplicity of <math>\mu(n)</math> comes naturally from its definition and what we previously established.  We see that
+<center><math>\phi(n)=n\sum_{d|n}\frac{\mu(d)}{d}=\sum_{d|n}\frac{n\mu(d)}{d}=\sum_{d|n}d\mu\left(\frac{n}{d}\right)=\sum_{dd'=n}d'\mu(d)</math></center>
-First, it conveniently encodes [[Principle of Inclusion-Exclusion]].
+completing the proof <math>\square</math>
-For example, to count the number of positive integers less than or equal to <math>n</math> and relatively prime to <math>n</math>, we have
-{| class="wikitable" style="margin: 1em auto 1em auto"
-| <math>\phi(n)</math> || <math> =n</math>
-|-
-| || <math>- \frac{n}{p_1} - \frac{n}{p_2} - \cdots - \frac{n}{p_k}</math>
-|-
-| || <math>+ \frac{n}{p_1p_2} + \frac{n}{p_1p_3} + \cdots + \frac{n}{p_{k-1}p_k}</math>
-|-
-| || <math>\vdots</math>
-|-
-| || <math>+ (-1)^k \frac{n}{p_1 p_2 \cdots p_k},</math>
-|}
-more succinctly expressed as
+==Sums of Divisors==
-<cmath>\phi(n) = \sum_{d|n} \mu(d) \frac{n}{d}.</cmath>
+While the multiplicity of the Möbius function is its most crucial component, there are other relationships that we can draw from as well.  One of the most notable is the following:
+<cmath>\sum_{d|n}\mu(d) = \begin{cases} 1 &\text{if}~n=1\\ 0 & \text{if}~n>1.\end{cases}</cmath>
-One unique fact about the Mobius function, which leads to the Mobius inversion formula, is that
+''Proof.''If <math>n=p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k}</math> where <math>k\ge 1</math> then
-<cmath>\sum_{d|n} \mu(d) = \begin{cases} 1 & n = 1, \\ 0 & \text{otherwise}. \end{cases}</cmath>
+<center><math>\sum_{d|n}\mu(d)=1+\sum_{i}\mu{p_i}+\sum_{i,j}\mu(p_ip_j)+\ldots=1-k+\binom{k}{2}-\binom{k}{3}-\ldots=(1-1)^k=0^k=0</math>.</center>
-Property 1: The function <math>\mu(n)</math> is multiplicative .
+To finish, we simply can use the fact that <math>\mu(1)=1</math>, completing the proof.  By a similar argument, one can also prove that
+<center><math>\sum_{d|n}|\mu(d)|=2^k</math></center>
+where <math>k</math> is the number of distinct prime factors of <math>n</math> <math>\square</math>
+==Implications to Other Functions==
+Let <math>f(n)</math> be a multiplicative function with respect to <math>n</math>.  If there is such an <math>f</math>, then
+<center><math>g(n)=\sum_{d|n}f(d)</math></center>
+is also multiplicative.
-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, for some <math>m</math>, that <math>\gcd(n,m)=1</math>, <math>d_1|n</math> and <math>d_2|m</math> then <math>\gcd(d_1,d_2)=1</math> and <math>c=d_1d_2</math> runs through all divisors of <math>nm</math>.  This means we have
+<center><math>g(mn)=\sum_{c|nm}f(c)=\sum_{d_1|n,d_2|m}f(d_1d_2)=\sum_{d_1|n}f(d_1)\sum_{d_2|m}f(d_2)=g(n)g(m)</math></center>
-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>.
+which completes the proof.  On a different note, this also provides an alternative proof for the theorem we proved earlier.  By letting
-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)
+<center><math>g(n)=\sum_{d|n}\mu(d)</math></center>
+the result follows by taking <math>g(1)</math> and <math>g(p^k)</math> for <math>k\ge 1</math> <math>\square</math>
-=\sum_{k|n}f(k)\sum_{d|n/d}\mu(d)= f(n)</cmath> .
+==Applications==
+One of the major uses of the Möbius function is in the [[Mobius inversion formula]].  It also has ties to the [[Riemann zeta function]], mainly that for <math>s>1</math>,
-The Mobius function is also closely related to the [[Riemann zeta function]], as
+<center><math>\frac{1}{\zeta(s)}=\sum_{n=1}^{\infty}\frac{\mu(n)}{n^s}</math>.</center>
-<cmath>\frac{1}{\zeta(s)} = \sum \frac{\mu(k)}{n^s}.</cmath>
+This comes from a couple of theorems.  Firstly, if <math>s>1</math> then
+<center><math>\zeta(s)=\prod_{p}\frac{1}{1-p^{-s}}</math>.</center>
+Secondly, if <math>f</math> is an arithmetic function such that <math>f(1)=1</math> and <math>f(n)</math> is multiplicative such that <math>\sum |f(n)|n^{-s}</math>is convergent, then
+<center><math>F(s)=\sum f(n)n^{-s}=\prod_{p}\{1+f(p)p^{-s}+f(p^2)p^{-2s}+\ldots\}.</math></center>
+Our theorem follows by using the multiplicity of <math>\mu(n)</math> lastly.  Doing so gives
+<center><math>\frac{1}{\zeta(s)}=\prod_{p}(1-p^{-s})=\prod_{p}\{1+\mu(p)p^{-s}+\mu(p^2)p^{-2s}+\ldots\}=\sum_{n=1}^{\infty}\mu(n)n^{-s}=\sum_{n=1}^{\infty}\frac{\mu(n)}{n^{s}}</math></center>
+which is what we wanted.  The reason why this is important is because we can do more things by using this as a baseline.  For example, it follows trivially that for <math>s>2</math>
+<center><math>\frac{\zeta(s-1)}{\zeta(s)}=\sum_{n=1}^{\infty}\frac{\phi(n)}{n^s}</math>.</center>

Page

Toolbox

Search