Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Mobius inversion formula"

m (Cosmetic edit for parentheses)
(Made major edits to this.)
 
Line 1: Line 1:
−
Suppose that <math>f</math> and <math>g</math> are [[function|functions]] from the [[natural number|natural numbers]] to the [[real number|real numbers]] such that <math>f(n) = \sum_{d|n}g(d)</math>. Then we can express <math>g</math> in terms of <math>f</math> as <math>g(n) = \sum_{d|n} \mu\left(\frac{n}{d}\right)f(d)</math> where <math>\mu</math> is the [[Mobius function]]. This formula is useful in [[number theory]].
+
The '''Möbius Inversion Formula''' is a relation between pairs of arithmetic functions, each defined from the other by sums over divisors. Originally proposed by August Ferdinand Möbius in 1832, it has many uses in [[Number Theory]] and [[Combinatorics]].
  
−
{{stub}}[[Category:Number Theory]]
+
===The Formula===
 +
Let <math>g</math> and <math>f</math> be arithmetic functions and <math>\mu</math> denote the [[Möbius Function]].  Then it follows that
 +
<center><math>g(n)=\sum_{d|n}f(d)\leftrightarrow f(n)=\sum_{d|n}\mu(d)g\left(\frac{n}{d}\right)=\sum_{d|n}\mu\left(\frac{n}{d}\right)g(d).</math></center>
 +
 
 +
<math>\textit{Proof}</math>: Notice the double implication, so we have two directions to prove.  We proceed with the proof of the backwards direction first.  We have
 +
<center><math>\sum_{d|n}\mu(d)g\left(\frac{n}{d}\right)=\sum_{d|n}\mu(d)\sum_{c|\frac{n}{d}}f(c)=\sum_{cd|n}\mu(d)f(c)=\sum_{c|n}f(c)\sum_{d|\frac{n}{c}}\mu(d).</math></center>
 +
To finish, we will use the fact that
 +
<center><math>\sum_{d|n}\mu(d)=1~\text{for}~n=1~,\sum_{d|n}\mu(d)=0~\text{for}~n>1.</math></center>
 +
If we have <math>\frac{n}{c}=1\leftrightarrow n=c</math> then we have
 +
<center><math>\sum_{d|\frac{n}{c}}\mu(d)=\sum_{d|1}\mu(d)=1</math></center>
 +
and that <math>\sum_{d|\frac{n}{c}}\mu(d)=0</math> if otherwise.  Hence by considering <math>n=c</math> we get
 +
<center><math>\sum_{c|n}f(c)\sum_{d|\frac{n}{c}}\mu(d)=\sum_{c|n}f(c)=f(n).</math></center>
 +
The first direction is satisfied, and now we must prove the second.  We see that
 +
<center><math>\sum_{d|n}f(d)=\sum_{d|n}f\left(\frac{n}{d}\right)=\sum_{d|n}\sum_{c|\frac{n}{d}}\mu\left(\frac{n}{cd}\right)g(c)=\sum_{cd|n}\mu\left(\frac{n}{cd}\right)g(c)=\sum_{c|n}g(c)\sum_{d|\frac{n}{c}}\mu\left(\frac{n}{cd}\right)=g(n).</math> </center>
 +
Both directions have been proven, which completes our work <math>\square</math>
 +
 
 +
===Applications===
 +
One of the most common applications of the formula is by proving that
 +
<center><math>n=\sum_{d|n}\varphi(d)</math>.</center>
 +
While there are some common combinatorial and group theoretic arguments one could use, a Möbius Inversion Formula solution also suffices.  Clearly by choosing <math>g(n)=n</math> and <math>f(n)=\varphi(n)</math> the theorem is proven.

Latest revision as of 18:54, 15 March 2022

The Möbius Inversion Formula is a relation between pairs of arithmetic functions, each defined from the other by sums over divisors. Originally proposed by August Ferdinand Möbius in 1832, it has many uses in Number Theory and Combinatorics.

The Formula

Let $g$ and $f$ be arithmetic functions and $\mu$ denote the Möbius Function. Then it follows that

$g(n)=\sum_{d|n}f(d)\leftrightarrow f(n)=\sum_{d|n}\mu(d)g\left(\frac{n}{d}\right)=\sum_{d|n}\mu\left(\frac{n}{d}\right)g(d).$

$\textit{Proof}$: Notice the double implication, so we have two directions to prove. We proceed with the proof of the backwards direction first. We have

$\sum_{d|n}\mu(d)g\left(\frac{n}{d}\right)=\sum_{d|n}\mu(d)\sum_{c|\frac{n}{d}}f(c)=\sum_{cd|n}\mu(d)f(c)=\sum_{c|n}f(c)\sum_{d|\frac{n}{c}}\mu(d).$

To finish, we will use the fact that

$\sum_{d|n}\mu(d)=1~\text{for}~n=1~,\sum_{d|n}\mu(d)=0~\text{for}~n>1.$

If we have $\frac{n}{c}=1\leftrightarrow n=c$ then we have

$\sum_{d|\frac{n}{c}}\mu(d)=\sum_{d|1}\mu(d)=1$

and that $\sum_{d|\frac{n}{c}}\mu(d)=0$ if otherwise. Hence by considering $n=c$ we get

$\sum_{c|n}f(c)\sum_{d|\frac{n}{c}}\mu(d)=\sum_{c|n}f(c)=f(n).$

The first direction is satisfied, and now we must prove the second. We see that

$\sum_{d|n}f(d)=\sum_{d|n}f\left(\frac{n}{d}\right)=\sum_{d|n}\sum_{c|\frac{n}{d}}\mu\left(\frac{n}{cd}\right)g(c)=\sum_{cd|n}\mu\left(\frac{n}{cd}\right)g(c)=\sum_{c|n}g(c)\sum_{d|\frac{n}{c}}\mu\left(\frac{n}{cd}\right)=g(n).$

Both directions have been proven, which completes our work $\square$

Applications

One of the most common applications of the formula is by proving that

$n=\sum_{d|n}\varphi(d)$.

While there are some common combinatorial and group theoretic arguments one could use, a Möbius Inversion Formula solution also suffices. Clearly by choosing $g(n)=n$ and $f(n)=\varphi(n)$ the theorem is proven.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mobius_inversion_formula&oldid=172636"