Difference between revisions of "Mobius function"
(4 intermediate revisions by 2 users not shown) | |||
Line 7: | Line 7: | ||
First, it conveniently encodes [[Principle of Inclusion-Exclusion]]. | First, it conveniently encodes [[Principle of Inclusion-Exclusion]]. | ||
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 | 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" | |
− | \phi(n) = | + | | <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 | more succinctly expressed as | ||
<cmath>\phi(n) = \sum_{d|n} \mu(d) \frac{n}{d}.</cmath> | <cmath>\phi(n) = \sum_{d|n} \mu(d) \frac{n}{d}.</cmath> | ||
+ | |||
+ | 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 & \text{otherwise}. \end{cases}</cmath> | ||
+ | |||
+ | Property 1: The function <math>\mu(n)</math> is 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>. | ||
+ | |||
+ | 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 | ||
+ | <cmath>\frac{1}{\zeta(s)} = \sum \frac{\mu(k)}{n^s}.</cmath> |
Revision as of 00:05, 22 September 2020
The Mobius function is a multiplicative number theoretic function defined as follows: In addition, .
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 and relatively prime to , we have
more succinctly expressed as
One unique fact about the Mobius function, which leads to the Mobius inversion formula, is that
Property 1: The function is multiplicative .
Proof:If or for a prime , we are done.Else let and where ,then .
Property 2:If for every positive integer , then . Proof:We have .
The Mobius function is also closely related to the Riemann zeta function, as