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

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

The importance of "intuition" in geometry

Hii everyone! Today I will be discussing a few geometry problems in which once you "guess" or "claim" the important things, then the problem can easily be finished using not-so-fancy techniques (e.g. angle chasing, power-of-point etc. Sometimes you would want to use inversion or projective geometry but once you have figured out that some particular synthetic property should hold, the finish shouldn't be that non trivial) This post stresses more about intuition rather than being rigorous. When I did these problems myself, I used freehand diagrams (not geogebra or ruler/compass) because I feel that gives a lot more freedom to you. By freedom, I mean, the power to guess. To elaborate on this - Suppose you drew a perfect  diagram on paper using ruler and compass, then you would be too rigid on what is true in the diagram which you drew. But sometimes that might just be a coincidence. e.g. Let's say a question says $D$ is a random point on segment $BC$, so maybe

LMAO Revenge

Continuing the tradition of past years, our seniors at the Indian IMO camp(an unofficial one happened this year) once again conducted LMAO, essentially ELMO but Indian. Sadly, only those who were in the unofficial IMOTC conducted by Pranav, Atul, Sunaina, Gunjan and others could participate in that. We all were super excited for the problems but I ended up not really trying the problems because of school things and stuff yet I solved problem 1 or so did I think. Problem 1:  There is a   grid of real numbers. In a move, you can pick any real number  ,  and any row or column and replace every entry   in it with  .  Is it possible to reach any grid from any other by a finite sequence of such moves? It turned out that I fakesolved and oh my god I was so disgusted, no way this proof could be false and then when I was asked Atul, it turns out that even my answer was wrong and he didn't even read the proof, this made me even more angry and guess what? I was not alone, Krutarth too fakesol

Edge querying in graph theory

In this post, I will present three graph theory problems in increasing difficulty, each with a common theme that one would determine a property of an edge in a complete graph through repeated iterations, and seek to achieve a greater objective. ESPR Summer Program Application: Alice and Bob play the following game on a $K_n$ ($n\ge 3$): initially all edges are uncolored, and each turn, Alice chooses an uncolored edge then Bob chooses to color it red or blue. The game ends when any vertex is adjacent to $n-1$ red edges, or when every edge is colored; Bob wins if and only if both condition holds at that time. Devise a winning strategy for Bob. This is more of a warm-up to the post, since it has a different flavor from the other two problems, and isn't as demanding in terms of experience with combinatorics. However, do note that when this problem was first presented, applicants did not know the winner ahead of time; it would be difficult to believe that Bob can hold such a strong