Möbius Inversion and Beyond
🏛 A Project Cauchy Op-ed
Named after French mathematician Augustin-Louis Cauchy, Project Cauchy column is where I invite some of the HFI Programming club members to provide neat proofs or explanations about some number theory puzzles. I highly suggest that you read these articles with a pencil and paper so you can sketch things out and scribble solutions to exercises as you come across them. This time, we have Travor Liu, one of the great mass communicators of Maths in our school. If you want good, honest worked examples of practice problems, especially for group theory, it’s hard to find a deeper well of examples than what Travor provides. In this article, he will elegantly lead us to the algebraic properties of multiplicative functions, using Möbius inversion formula and Dirichlet convolutions.
In number theory, Möbius inversion is a common technique to study the properties of arithmetic functions (i.e. those that map to ), and all of these brilliant things are derived from the following formula:
To understand this formula, let's first understand what it says:
Summation over Divisors
The first part of (1) is the summation symbol: . Instead of summing over all positive integers within , it is summing over the divisors of . For instance, if , then sums over . Pedantically, we write
To enhance your understanding of this operator, try these exercises:
- Explain the meaning of
, the Möbius FunctionFormulating
Usually, the Möbius function is defined as
This standard definition may appear to be strange: why would people care whether some number is square-free or not? To address this, let's turn to a totally different perspective: to expand the following product that runs over all prime numbers:
By some combinatoric skills, we are able to expand it like this:
By observing the expansion, we discover that must satisfy
- when the is composed of odd number of prime factors
- when the consists of even number of prime factors .
- Because each prime only appears only once in the product, for all that contains square factors
As a result, is the Möbius function .
With our understanding of the symbols, we can now be capable of understanding the implication of (1). That is, (1) declares that the summation of the Möbius function over divisors of some certain number is one for and zero for all . Obviously, when , we have
Did you understand the definition of ? Try these problems!
Generally, we say some arithmetic function to be multiplicative when for all coprime positive integers and , . Now, let's show the following fact of :
Theorem: is multiplicative
Proof. For coprime positive integers and , we may divide this proof into two situations:
- and/or contains square factors, their product would also have square factors. As a result,
- For and being square free, let's denote be the number of prime factors in , so we have
which completes the proof.
With these tools being prepared, we can delve into proving (1).
Proof of (1)
Let where and are coprime positive integers, then
Now, let's plug prime powers into (1), so we have
Due to the fact that is multiplicative, we conclude (1) is true.
Application of Möbius Inversion: Euler's Totient Function
In fact, (1) can help us find a definition for Euler's totient function , i.e. number of positive integers within that are coprime to :
First, we write down in terms of summation:
Then, using the identity given by , we have
Eventually, we obtain the formula for Euler's totient function:
As we can see, (1) actually helps us give definition to other arithmetic functions. Now, it is your job to discover the properties of this function:
Show that is multiplicative and, in addition, can be expressed by
Divisor sum of Euler's totient function
If we were to sum over divisors of , we could magically obtain :
This identity can also be seen by listing fractions. For instance let's consider the case for
In total, there are fractions. If we were to simplify these fractions, we get
Particularly, the denominators in these simplified fractions are always the divisor of . Moreover, for each there are exactly simplified fractions with denominator . As a result, we can also observe that
If we juxtapose (2) and (3), we can see that and are closely related to each other, particularly if we define (4) as Dirichlet convolution, then we can say that can be obtained by convolving Möbius function with . Similarly, can be obtained by convolving with .
- Commutativity and associativity: Obviously this operation commutative. Moreover, it can be easily verified that Dirichlet convolution is also associative using similar techniques to prove (3).
- Identity element: There is also an identity function for Dirichlet convolution. That is, Dirichlet convolution between any arithmetic function and gives the original function:
- Dirichlet inverse: If and are Dirichlet inverse to each other, then
Although and are inverses to each other, not every arithmetic function has Dirichlet inverse. Hopefully, the following theorem helps us determine whether some arithmetic function is Dirichlet-invertible or not:
Theorem: An arithmetic function has Dirichlet inverse if and only if
Proof. For convenience, suppose has a Dirichlet inverse , so we need to ensure
For , we have , so must be non-zero in order for its Dirichlet inverse to exist. In addition, for we have
which also implies the theorem.
Algebraic Properties of Multiplicative Functions
Let be the set containing all multiplicative functions and be the Dirichlet convolution operator, then we can verify that
- For all , we have
- For all ,
- For all ,
- For all , there exists such that
In order for the last condition to hold, readers could consider proving that every multiplicative function satisfies .
As a result, we conclude that all multiplicative functions form an abelian group under Dirichlet convolution.
In a nutshell, we begin our discussion with the explanation and proof Möbius inversion formula as in (1), and then we present Dirichlet convolution, a generalization of the sum-of-divisor operation. At last, we discover an algebraic property in multiplicative functions: that is, all multiplicative functions form an abelian group under Dirichlet convolution.