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...

POSETS:

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$.

INCIDENCE ALGEBRA OF POSETS:

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.

MOBIUS THEOREM:

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)$$

Proof:
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$$ n\choose i$.
Thus $\sum_{m\vert q}\mu(m)= 1+\sum_{i=1}^{i=k} (-1)^i$$n\choose i$$=\sum_{i=0}^{i=k} (-1)^i $$n\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$).

Solution: 
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_1=n\sum_{l=1}^{l=k}\frac{1}{p_l}$.
$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})$.

Solution:
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$.

Solution:
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.

Solution:
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$.

Solution:
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:
$f(C)=|C|^{|A|}$
 $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

Comments

Post a Comment

Popular posts from this blog

Constructions in Number Theory

Hi, I am Emon, a ninth grader, an olympiad aspirant, hailing from Kolkata. I love to do olympiad maths and do some competitive programming in my leisure hours, though I take it seriously. I had written INOI this year. Today, I would be giving you a few ideas on how to Construct in Number Theory . Well, so we shall start from the basics and shall try to dig deeper into it with the help of some important and well-known theorems and perhaps, some fancy ones as well. Okay, so without further delay, let's start off... What do we mean by "Constructions"? If noticed, you can see that you often face with some problems in olympiad saying, "... Prove that there exists infinitely many numbers satisfying the given conditions" or "... Prove that there exists a number satisfying the above conditions." These are usually the construction-problems .  For example, let's consider a trivial example : Problem. Prove that there exist infinitely many integers $a$ such th

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

Q&A with experts about bashing

Heyy everyone! From the title, you can see that we are going to talk about  BASH.  Yesss, we are going to discuss whether you really need to learn bash or not?  Let me first introduce myself, I am Pranav Choudhary, a 10th grader from Haryana(India). I like to do geo and combo the most :PP. Oki so let's begin! For those of you who don't know what bashing is, lemme give you a brief introduction first. Bashing is basically a technique used to solve Geometry Problems. In general, when you try a geo problem you might think of angles, similarities, and some other techniques (e.g. Inversion, spiral similarity etc). All of which are called synthetic geometry. But sometimes people use various other techniques called "bash" to solve the same problems.  Now there are different kinds of bashing techniques, e.g. - Coordinate bash, Trig Bash, Complex bash, Barycentric Coordinates. Let me give you a brief introduction to each of them.  Coordinate Bash : You set one point as the orig