Skip to main content

Mobius Inversion

The word 'Mobius' would instantly remind the readers of the Mobius strip, the famous object used to attract fellow students to the wonders of topology. But the discoverer of this object, August Ferdinand Mobius was also responsible for the creation of another amazing thing, the theory of Mobius inversions. It is a formula in number theory that answers the following question:

Given two functions $f$ and $g$ on the set of naturals, if it is known that $$f(n)=\sum_{d\vert n}g(d),$$ how do you express $g$ in terms of $f$?

Actually, the Mobius inversion formula that is applied in number theory is a special case of a more general theorem in the branch of Order theory. Without any doubt, we explore the general theorem first! For that, we need to build up some theory though...


A poset is a short word for 'partially ordered sets'. It is a set $P$ equipped with a binary relation $\leq$ that satisfies the following three conditions:
  • $\forall a\in P$, $a\leq a$ (Reflexivity).
  • for $a,b\in P$, if $a\leq b$ and $b\leq a$ then $a=b$ (Antisymmetry).
  • for $a,b,c\in P$, if $a\leq b$ and $b\leq c$ then $a\leq c$ (Transitivity).
Sounds simple enough right? It is just a set for which we know that certain elements have higher precedence than certain other elements. However an important thing to note is that there might be elements $a$ and $b$ in $P$ for which neither $a\leq b$ nor $b\leq a$ holds. That is why it is called a partially ordered set. If $a\leq b$ or $b\leq a$ holds for all $(a,b)\in P\times P$ (Law of Trichotomy), then the poset is termed as a totally ordered set. Let us see some examples of posets:
  1. P is the set of natural numbers and $a\leq b\iff$ $a$ is smaller than or equal to $b$.This is a totally ordered infinite set.
  2. For any natural $n$, consider $P$ to be its set of divisors and for $a,b\in P$, $a\leq b \iff a\vert b.$ Verify that it is a poset and not totally ordered.
  3. For any set $S$, let $P=P(S)$ where $P(S)$ is the power set of $S$ (set of all subsets of $S$), and for $A,B\in P$, $A\leq B\iff A\subseteq B$. Verify that it is a poset and not totally ordered.
In the discussions further, we would be concerned only with finite posets. Also by $\leq$ we are meaning the poset relation unless mentioned otherwise and by $x<y$ we mean that $x\leq y$ and $x\neq y$.


The incidence algebra associated with a poset $P$ is denoted by $A(P)$.
$A(P)=${$f:P\times P\rightarrow \mathbb{C}|f(x,y)=0$ unless $x\leq y$}.

Consider any bijection $h$ from $[|P|]$ to $P$ ($[|P|]$ is the set of first $|P|$ natural numbers). Think of a $|P|\times |P|$ matrix $M$ for which $m_{ij}=f(h(i),h(j))$. Thus the incidence algebra of $P$ can be visualized as a set of order $|P|$ matrices satisfying certain conditions. This correspondence is crucial in understanding Mobius inversion. Clearly, there was nothing special of $h$ described above. So imagine the incidence algebra as a set of matrices whose rows and columns are bijectively labeled by elements of the poset in the same manner (The $i$th row and column are labeled by the same element $x_i$. This labeling of the elements would be fixed henceforth and whenever we use the variable $x_i$, we are referring to that same particular element of the poset). Thus the entry of row $x$ and column $y$, $M(x,y)$ is $f(x,y)$. Denote the matrix equivalent of $A(P)$ by $M(P)$.

Zeta Matrix (Z):

Consider the order $|P|$ matrix $Z$ for which $Z(x,y)=1$ for $x\leq y$ and $0$ otherwise. Clearly $Z\in M(P)$.

Mobius Matrix (U):

We define the entries of this matrix dynamically:
$U(x,x)=1\:\forall x\in P$
$U(x,y)=-\sum_{x\leq z< y}U(x,z)$ for $x< y$
$U(x,y)=0$ otherwise.
By $x\leq z< y$, we mean that both $x\leq z$ and $z< y$ must hold and the summation is taken over all such $z$. (Note that $x\leq z<y$ and $x\leq y<z$ cannot both hold. The reason to emphasize this is that for $y\neq z$, $U(x,y)$ and $U(x,z)$ are not simultaneously dependent on each other, so $U(x,y)$ can be calculated uniquely without falling in an infinite loop).

Note that the Mobius matrix can be equivalently defined as:
 $\sum_{x\leq z\leq y} U(x,z)=1$ if $y=x$ and $0$ otherwise ($\star$)

Consider $I(x,y)=\sum_{z\in P}U(x,z)Z(z,y)$.
By definition of $Z$, $\sum_{z\in P}U(x,z)Z(z,y)=\sum_{z\leq y}U(x,z)$.
Since $U(x,z)=0$ if $x\nleq z$, $\sum_{z\leq y}U(x,z)$=$\sum_{x\leq z\leq y} U(x,z)$.
Thus by $\star$, $I(x,y)=1\iff x=y$ and $0$ otherwise.

Does this ring a bell?
 $ZU=I_{|P|}$ where $I_{|P|}$ is the identity matrix of order $|P|$ !
And by the theory of matrices, $ZU=I_{|P|}\Rightarrow UZ=I_{|P|}.$
This gives rise to the beautiful theorem of Mobius.


Let $P$ be a poset with $\leq$ as its associated binary operation and $U$ its associated Mobius matrix.
Given $f:P\rightarrow \mathbb{C}$ and $g:P\rightarrow \mathbb{C}$, $$f(x)=\sum_{y\leq x}g(y)$$ $$\iff $$ $$g(x)=\sum_{y\leq x}U(y,x)f(y)$$

Denote by $F$ the $1\times |P|$ matrix whose entry in column $i$ is $f(x_i)$ and similarly define $G$. 
To prove the then part assume
$$f(x)=\sum_{y\leq x}g(y)=\sum_{y\in P}Z(y,x)g(y).$$
$$\Rightarrow F=GZ\Rightarrow FU=GZU\Rightarrow FU=G.$$
 $$\therefore g(x)=\sum_{y\in P}U(y,x)f(y)=\sum_{y\leq x}U(y,x)f(y).$$To prove the if part assume$$g(x)=\sum_{y\leq x}U(y,x)f(y).$$$$\implies G=FU\Rightarrow GZ=FUZ\Rightarrow GZ=F.$$$$\therefore f(x)=\sum_{y\in P}Z(y,x)g(y)=\sum_{y\leq x}Z(y,x)f(y).$$That was the general version of the Mobius formula. Ok great, but how does it even relate to the problem that we began with? We have seen that the set of divisors of $n$ with the binary relation $a\leq b$ as $a\vert b$ forms a poset. Denote this poset by $D$ and its associated Mobius matrix by $U$.
Thus the condition $f(n)=\sum_{d\vert n}g(d)$ can be written as $f(n)=\sum_{d\in D,\:d\leq n} g(d)$.
So $g(n)=\sum_{d\in D,\: d\leq n}U(d,n)f(d)$.

But what would $U(d,n)$ be?

It turns out that $U(d,n)$ is independent of $d$ and depends only on $\frac {n}{d}$ (here we are assuming $d\leq n$ as for $d\nleq n,\:\:U(d,n)=0$). So for $d\leq n$ denote $U(d,n)$ by $\mu(\frac {n}{d})$. Then,
  1. $\mu(1)=1$
  2. If $n$ is not square-free (that is $\exists$ a prime $p$ such that $p^2\vert n$) then $\mu(n)=0$
  3. If $n$ is square-free (that is $\nexists$ a prime $p$ such that $p^2\vert n$) then $\mu(n)=(-1)^k$ where $k$ is the number of distinct prime divisors of $n$.
To verify this construction works, $\star$ must hold true.
Let $\frac {n}{d}=q=p_1^{a_1}p_2^{a_2}$.....$p_k^{a_k}$.
Then $\sum_{d\leq m\leq n}U(d,m)=\sum_{m\vert q}\mu(m)$.
Clearly, we need to consider only those $m$ which are square-free.
Therefore, $\sum_{m\vert q}\mu(m)=\mu(1)+\sum_{i=1}^{i=k} B_i$, where $B_i$ is the sum of the $\mu$ values of the product of the $k$ primes taken $i$ at a time.
That is,
$B_1=\sum_{l=1}^{l=k} \mu(p_l)$.
$B_2=\sum_{l=1}^{l=k}\sum_{m=l+1}^{m=k} \mu(p_lp_m)$.
$B_3=\sum_{l=1}^{l=k} \sum_{m=l+1}^{m=k}\sum_{n=m+1}^{n=k} \mu(p_lp_mp_n)$.
and so on...

By definition of $\mu$, $B_i=(-1)^i$$ k\choose i$.
Thus $\sum_{m\vert q}\mu(m)= 1+\sum_{i=1}^{i=k} (-1)^i$$k\choose i$$=\sum_{i=0}^{i=k} (-1)^i $$k\choose i$$=0.$ if $q\neq 1$ and $1$ for $q=1$.
Hence this construction works. Would there be any other possible construction of $U(x,y)$?
No, because $U(x,x)$ is defined to be $1$ for all $x$ and $\star$ guarantees that $U(x,y)$ would be unique $\forall y\:\: x\leq y$.  Also $U(x,y)$ is forced to be $0$ for $x\nleq y$.

If you are thinking that how does one even come up with such construction, the best answer would be trying a lot of different values of $d$ and $n$ and evaluating $U(d,n)$ until you see a pattern. Once you guess the pattern, proving it is not that difficult. This method of working is in fact true in every branch of mathematics. You guess or conjecture a certain pattern to a certain problem and then try to prove it.
Thus, $$f(n)=\sum_{d\vert n}g(d)\iff g(n)=\sum_{d\vert n}\mu(\frac {n}{d})f(d)$$Now let us see some applications of the Mobius inversion formula. Before seeing the solutions , think in what form the Mobius inversion formula would apply to each of them:

Example 1:
Find an expression to evaluate $\phi(n)$ where $\phi$ is the Euler's totient function (number of naturals $k\leq n$ which satisfy gcd$(k,n)=1$).

We first prove an interesting identity:   $\sum_{d\vert n}\phi (d)=n$.
Consider $A$ to be the set of first $n$ naturals and $B$ to be the set of divisors of $n$.
Consider the mapping $h: A\rightarrow B$ satisfying gcd $(x,n)=h(x)$.
Now how many elements of $A$ map to the same element $y$ of $B$? Precisely those for which gcd$(\frac {x}{y},\frac {n}{y})=1$. 
So $x$ must be of the form $ky$ where gcd$(k,\frac {n}{y})=1.$
And how many such $k$ exist?  Precisely $\phi (\frac {n}{y})$.
Thus by double counting, $\sum_{d\vert n}\phi (\frac{n}{d})=n\:\:\Rightarrow \sum_{d\vert n}\phi (d)=n$.

So letting $f(n)=n$ and $g(n)=\phi (n)$ and applying the Mobius inversion formula,
$\phi (n)=\sum_{d\vert n}\mu (\frac {n}{d})d\:=\:\sum_{d\vert n}\mu(d)\frac {n}{d}.$ 

Let $p_1,p_2,$.....$,p_k$ be the distinct prime divisors of $n$. Simplyfying the above summation,
 $\phi (n)=n+\sum_{i=1}^{i=k} (-1)^iB_i$ where $B_i$ is $n$ times the sum of the product of the reciprocals of the $k$ prime divisors taken $i$ at a time. That is,
$B_2=n\sum_{l=1}^{l=k}\sum_{m=l+1}^{m=k} \frac {1}{p_lp_m}$.
$B_3=n\sum_{l=1}^{l=k} \sum_{m=l+1}^{m=k}\sum_{n=m+1}^{n=k} \frac {1}{p_lp_mp_n}$.
and so on...

Thus on further easy simplifications to the above summation, we obtain $$\phi(n)=n\prod_{i=1}^{k} (1-\frac {1}{p_i})$$

Example 2:
Prove that $\mu (n)=\sum_{k\leq n,(k,n)=1} cos(\frac {2\pi k}{n})$.

Let $g(n)=\sum_{k\leq n,(k,n)=1} cos(\frac {2\pi k}{n}).$
Recall that for a natural $n$, $f(n)=\sum_{k=1}^{k=n} cos(\frac {2\pi k}{n})=0$ for $n\neq 1$ and $1$ otherwise (can be proved by considering the real part of the sum of $n$th roots of unity).
For every $x\leq n$, $\exists\:d$ such that $d\vert n$ and $\frac{x}{n}=\frac {c}{d}$ for some $c\leq d$ satisfying gcd $(c,d)=1$. To be precise, $d=\frac{n}{(x,n)}.$ And as $x$ would vary from $1$ to $n$, $c$ would eventually take all possible $\phi(d)$ values. Thus,
$$f(n)=\sum_{k=1}^{k=n} cos(\frac {2\pi k}{n})=\sum_{d\vert n}\sum_{k\leq d, (k,d)=1}cos(\frac {2\pi k}{d})=\sum_{d\vert n}  g(d).$$ And ye! We can now apply the Mobius inversion to get$$g(n)=\sum_{d\vert n} \mu(\frac {n}{d})f(d)=\mu(n).$$
Thus $g(n)=\mu(n) \:\forall\: n\:\blacksquare$

Example 3:
Given a natural $n$, evaluate $\sum_{d=1}^{d=n}\mu(d)\lfloor \frac{n}{d}\rfloor$.

So here the summation is not of the form $\sum_{d\vert n}$ but $d$ takes all values less than or equal to $n$. So Mobius inversion cannot be directly applied here. Let $F(n)$ denote $\sum_{d=1}^{d=n}\mu(d)\lfloor \frac{n}{d}\rfloor$. The main idea is to concentrate on $F(n+1)-F(n)$. $$F(n+1)-F(n)=\mu(n+1)+\sum_{d=1}^{d=n}\mu(d)(\lfloor \frac{n+1}{d}\rfloor - \lfloor \frac{n}{d}\rfloor).$$
If $d\vert n+1,\:\:\lfloor \frac{n+1}{d}\rfloor=\lfloor \frac{n}{d}\rfloor +1$, 
else $\lfloor \frac{n+1}{d}\rfloor=\lfloor \frac{n}{d}\rfloor.$
Thus $F(n+1)-F(n)=\mu (n+1)+\sum_{d\vert n+1 ,d\leq n} \mu(d)=\sum_{d\vert n+1}\mu(d).$

Claim: $\sum_{d\vert n}\mu(d)=0\:\:\forall$ naturals $n\neq 1$.
Consider the function $f(n)=0 \forall\: n\neq 1$ and $f(1)=1.$ 
Defining $g(n)=\sum_{d\vert n}f(d)$, we see that $g(n)=1$ for all naturals $n$. Applying Mobius inversion, $\sum_{d\vert n}\mu(d)g(d)=f(n)\Rightarrow \sum_{d\vert n}\mu(d)=0\:\: \forall$ naturals $n\neq 1.$

$\therefore F(n+1)-F(n)=0$ as $n+1\geq 2$.
That means $F(n)=F(1)=1$ $\forall n\in \mathbb{N}$!

Example 4:
Given an integer $m$, find an expression for the number of distinct $n$ tuples $(x_1,x_2,$..$,x_n)$ of naturals that satisfy gcd$(x_1,x_2,$.....$,x_n)=1$ and $\sum_{i=1}^{i=n} x_i=m$. Note that $n$ here is a parameter and not a constant variable.

Let $F(m)$ denote the desired expression. How many $n$ tuples $(x_1,x_2,$...$,x_n)$ of naturals would be there for which $x_1+x_2+$...$+x_n=m$ ? where $n$ is a parameter? 
They would be $\sum_{n=1}^{n=m}$ $m-n+n-1\choose n-1$ $=2^{m-1}.$ (Here the minimum and maximum possible value of $n$ is $1$ and $m$ respectively due to the tuple being of natural numbers.)
And for any such tuple, gcd$(x_1,x_2,$...$,x_n)$ $=\:g$$\vert m$. So converting this tuple to $(y_1,y_2,$...$,y_n)$ where $y_i=\frac{x_i}{g}$, we get $\sum_{i=1}^{i=n} y_i=\frac {m}{g}$ and $(y_1,y_2,$...$,y_n)$ $=\:1$. So this tuple would be "effectively" counted in $F(\frac {m}{g})$. Thus $$2^{m-1}\:=\:\sum_{d\vert m} F(\frac {m}{d})\:=\:\sum_{d\vert m}F(d)$$
Thus by Mobius inversion,
$$F(m)=\sum_{d\vert m}\:2^{d-1}\mu(\frac {m}{d})$$

Here is a last example that applies Mobius inversion to a poset other than $D$:

Example 5: 
Given two sets $A$ and $B$ of size $n$ and $m$ respectively, find the number of onto functions from $A$ to $B$.

Consider the poset $S$ as the power set of $B$ and for $C,D\in S$, $C\leq D\iff C\subseteq D$. We first need to know the Mobius matrix corresponding to $S$. It is given by:
$$U(C,D)=(-1)^{|D|-|C|} \iff C\leq D$$ else $$U(C,D)=0$$ The proof that this matrix is valid is left to the reader. So define $f:S\rightarrow \mathbb{C}$ and $g:S\rightarrow \mathbb{C}$ as follows:
 $g(C)=$ Number of surjective functions from $A$ to $C$.
Then note that, $$f(C)=\sum_{D\leq C}g(D)\Rightarrow g(C)=\sum_{D\leq C}U(D,C)f(D)$$
by Mobius inversion. Clearly we need to find $g(B)$.
Thus $g(B)=\sum_{D\leq B}(-1)^{|B|-|D|}|D|^{|A|}.$
Now note that we are only concerned with the size of $D$ in this summation and not its contents, therefore we express this sum by iterating over sizes of $D$ and finding number of $D$'s of same size.
Thus we conclude $g(B)=\sum_{i=0}^{i=n}(-1)^{i}$$n\choose i$$i^ {|A|}\:\:$$\blacksquare$

So this is it for this blog. If you have any doubts, feel free to post it in the comments. See ya next time!

Mihir. M. Kaskhedikar


Post a Comment

Popular posts from this blog

EGMO solutions, motivations and reviews ft. Atul, Pranjal and Abhay

The  European Girls' Mathematical Olympiad a.k.a EGMO 2022 just ended. Congrats to Jessica Wan from USA, Taisiia Korotchenko, and Galiia Sharafetdinova for the perfect scores! Moreover, the Indian girls brought home 4 bronze medals! By far, this is the best result the EGMO India Team has ever achieved! To celebrate the brilliant result, here's a compilation of EGMO 2022 solutions and motivations written by my and everyone's favorite IMOTCer Atul ! And along with that, we also have reviews of each problem written by everyone's favorite senior, Pranjal !  These solutions were actually found by Atul, Pranjal,  and Abhay  during the 3-hour live solve. In the live solve, they solved all the 6 problems in 3 hours 😍!!! Okie Dokie, I think we should get started with the problems! Enjoy! Problem 1:  Let $ABC$ be an acute-angled triangle in which $BC<AB$ and $BC<CA$. Let point $P$ lie on segment $AB$ and point $Q$ lie on segment $AC$ such that $P \neq B$, $Q \neq C$ and

Kőnig-Egerváry theorem

Graph theory has been my most favourite thing to learn in maths and and in this blog i hope to spread the knowledge about Kőnig's theorem. It is advised that the readers are aware about basic graph theory terminologies including bipartite graphs. Before going on to the theorem i would like to go on about matchings and vertex cover which we are going to use in the theorem  Matchings A matching $M$ of a graph $G$ is a subset of the edges of a graph in which no two edge share a common vertex (non adjacent edges). For example :- The Matching $M$ over here is edge $\{ 3 - 5 , 1-2 , \}$ or $\{ 1 - 2 , 4 - 3 \}$ etc .  Maximum Matching is a matching that contains the largest possible number of edges for instance in the above example the maximum matching is 2 edges as there cannot be a subset of non adjacent edges having greater than 2 edges (Readers are advised to try so they can convince themselves) A Perfect Matching  is a matching that matches all vertices of the graph or in other sen

Algorithms, or Mathematics?!

Hi everyone! In my last blog, I spoke about a couple of very interesting algorithmic techniques and how they can be used to solve a variety of very interesting problems. This blog however, is going to be completely different.   When we’re young we begin by learning the steps to add – we’re given the rules and we must learn to repeat them – no questions asked. Why does carry forward work the way it does? Well, no questions asked. To some extent, it is important to know how exactly to do a certain set of things while first learning maths. We may not be able to get anywhere in a subject if we’re unable to learn a few basic rules and know how to use them. However, after a certain point it is important to bring in the spirit of mathematical thinking within each student too – something missing in almost every form of school math education. Mathematical miseducation is so common, we wouldn’t even see it. We practically expect a math class to look like repetition and memorisation of disjointed