Möbius inversion

Section 2.4 Möbius inversion

Subsection 2.4.1 Möbius function

Theorem 2.4.1.

The following arithmetic functions are all equal:

\(\mu_1\) defined in terms of factorization:
\begin{equation} \mu_1(n) = \begin{cases} 1 \amp \text{if } n = 1 \\ (-1)^k \amp \text{if } n = p_1 p_2 \dotsm p_k \\ 0 \amp \text{if some } p^2 \mid n \end{cases}\tag{2.4.1} \end{equation}
\(\mu_2\) defined in terms of coefficients of a product: For any \(n\) we define \(\mu_2\) by
\begin{equation} \prod_{p \mid n} \left( 1 - \frac{1}{p^s} \right) = \sum_{d \mid n} \frac{\mu_2(d)}{d^s} \text{.}\tag{2.4.2} \end{equation}
Here the product is over all primes \(p\) that divide \(n\text{,}\) while the sum is over all (positive) divisors of \(n\text{.}\) The symbol \(s\) is a formal variable; alternatively we can interpret this as saying that the two sides of the equation are equal for all complex numbers \(s\text{.}\) (We follow normal exponent rules, \(1^s = 1\) and \(a^s b^s = (ab)^s\text{.}\)) We assert that this function \(\mu_2\) is well-defined in the sense that if \(d \mid n\) and \(d \mid n'\text{,}\) then \(\frac{1}{d^s}\) has the same coefficient whether the product is taken over the primes that divide \(n\text{,}\) or primes that divide \(n'\text{.}\) In fact \(\mu_2(d)\) is the coefficient of \(\frac{1}{d^s}\) in the infinite product \(\prod_p \left( 1 - \frac{1}{p^s} \right)\) over all primes (this is a formal product in the sense that we don’t worry about whether it converges).
\(\mu_3\) defined recursively: We define \(\mu_3(1) = 1\) and for \(n \gt 1\text{,}\) we define \(\mu_3(n)\) by setting \(\sum_{d \mid n} \mu_3(d) = 0\text{.}\)
\(\mu_4\) defined as the Dirichlet inverse of the arithmetic function \(1(n) = 1\) for all \(n\text{.}\)

That is, for all \(n\text{,}\) \(\mu_1(n) = \mu_2(n) = \mu_3(n) = \mu_4(n)\text{.}\)

Example 2.4.2.

For example,

\begin{equation} \prod_{p \mid 6} \left( 1 - \frac{1}{p^s} \right) = \left( 1 - \frac{1}{2^s} \right) \left( 1 - \frac{1}{3^s} \right) = 1 - \frac{1}{2^s} - \frac{1}{3^s} + \frac{1}{6^s}\text{.}\tag{2.4.3} \end{equation}

This shows that \(\mu_2(1) = 1\text{,}\) \(\mu_2(2) = -1\text{,}\) \(\mu_2(3) = -1\text{,}\) and \(\mu_2(6) = 1\text{.}\)

Likewise,

\begin{equation} \prod_{p \mid 4} \left( 1 - \frac{1}{p^s} \right) = 1 - \frac{1}{2^s} = 1 - \frac{1}{2^s} + \frac{0}{4^s}\text{.}\tag{2.4.4} \end{equation}

This gives \(\mu_2(2) = -1\text{,}\) agreeing with the result when the product was taken over primes \(p \mid 6\) instead of \(p \mid 4\text{.}\) In addition we see that \(\mu_2(4) = 0\text{.}\)

Proof.

The recursive definition of \(\mu_3\) means precisely that \(\mu_3 * 1 = e\text{.}\) Therefore \(\mu_3\) is the Dirichlet inverse of \(1\text{,}\) so \(\mu_3 = \mu_4\text{.}\) (Note: Dirichlet inverses are unique: if \(f * g_1 = f * g_2 = e\text{,}\) then \(g_1 = g_2\) (why?).)

Suppose \(d \mid n\text{,}\) \(d \gt 1\text{,}\) and \(d = p_1^{a_1} \dotsm p_k^{a_k}\) where the \(p_i\) are distinct primes and each \(a_i \geq 1\text{.}\) First, each \(p_i\) divides \(n\) as well, so the product in the definition of \(\mu_2\) includes all of the primes \(p_i\) appearing in the prime factorization of \(d\text{.}\) If any \(p_i^2 \mid d\) then \(\mu_2(d) = 0\text{,}\) since the product only includes one factor of \(1/p_i^s\text{;}\) there is no \(1/(p_i^2)^s\text{.}\) (Here is where the formal variable \(s\) plays a role: without it, we could have \(1/p_i = p_i / p_i^2\text{,}\) and the sum could be rewritten to include a term with denominator \(p_i^2\text{.}\) With the \(s\) however, we have \(1/p_i^s = p_i^s / (p_i^2)^s\text{,}\) and we are requiring that the numerators only involve \(\mu_2(d)\)’s, without any \(s\text{.}\)) Otherwise, if each \(a_i = 1\text{,}\) so \(d = p_1 p_2 \dotsm p_k\text{,}\) then

\begin{equation} \frac{\mu_2(d)}{d^s} = \frac{-1}{p_1^s} \frac{-1}{p_2^s} \dotsm \frac{-1}{p_k^s} = \frac{(-1)^k}{(p_1 \dotsm p_k)^s} \text{.}\tag{2.4.5} \end{equation}

This shows that in this case \(\mu_2(d) = (-1)^k\text{.}\) Finally for \(d = 1\) we have \(\mu_2(1) = 1\) because the term of the product with denominator \(1^s = 1\) is given by multiplying \(1\) for each prime \(p \mid n\text{.}\)

This shows that \(\mu_2(d) = \mu_1(d)\) for all \(d \mid n\text{.}\) In particular, \(\mu_2(d)\) doesn’t actually depend on which multiple \(n\) of \(d\) is used. Therefore \(\mu_2 = \mu_1\text{.}\) The fact that we can take the infinite product follows from the observation that including factors \(1 - \frac{1}{p^s}\) where \(p \gt d\) has no effect on the coefficient of \(\frac{1}{d^s}\text{.}\)

Finally we prove that \(\mu_1 * 1 = e\text{,}\) which gives \(\mu_1 = \mu_4\text{.}\) We have \((\mu_1 * 1)(1) = \mu_1(1) 1(1) = 1 = e(1)\) by definition. For \(n \gt 1\text{,}\) say \(n = p_1^{a_1} \dotsm p_k^{a_k}\) where the \(p_i\) are distinct primes and each \(a_i \geq 1\text{.}\) Let \(d \mid n\) and write \(d = p_1^{b_1} \dotsb p_k^{b_k}\text{.}\) By definition of \(\mu_1\text{,}\) if any \(b_i \gt 1\) then \(\mu_1(d) = 0\text{.}\) So in the sum \((\mu_1 * 1)(n) = \sum_{d \mid n} \mu_1(d)\) we can ignore such terms, and only include terms \(d \mid n\) such that in the prime factorization, every prime appears with power \(0\) or \(1\text{.}\)

Let \([k] = \{1,\dotsc,k\}\text{.}\) For a subset \(S \subseteq [k]\) let \(d_S = \prod_{i \in S} p_i\text{,}\) that is, \(d_S\) is the product of primes in the prime factorization of \(n\) corresponding to elements of \(n\text{.}\) In particular if \(S = \varnothing\) then \(d_{\varnothing} = 1\text{.}\) By the definition of \(\mu_1\text{,}\) \(\mu_1(d_S) = (-1)^{|S|}\text{.}\) Now

\begin{align*} (\mu_1 * 1)(n) \amp = \sum_{d \mid n} \mu_1(d) \\ \amp = \sum_{S \subseteq [k]} (-1)^{|S|} \\ \amp = \sum_{j = 0}^k \binom{k}{j} (-1)^j \\ \amp = (1-1)^k \\ \amp = 0 \\ \amp = e(n) \text{.} \end{align*}

This shows that \(\mu_1 * 1 = e\text{,}\) and hence \(\mu_1 = \mu_4\text{,}\) as claimed.

Alternative proof of \(\mu_1=\mu_4\).

We know that the arithmetic functions \(1(n) = 1\) and \(e\) are multiplicative (in fact completely multiplicative). In addition \(\mu_1\) is multiplicative (although not completely multiplicative) (exercise). Therefore \(\mu_1 * 1\) is multiplicative by Theorem 2.3.5. We compute the value

\begin{align*} (\mu_1 * 1)(p^a) \amp = \mu_1(1) + \mu_1(p) + \mu_1(p^2) + \mu_1(p^3) + \dotsb + \mu_1(p^a) \\ \amp = 1 - 1 + 0 + 0 + \dotsb + 0 \\ \amp = 0 \\ \amp = e(p^a) \text{.} \end{align*}

This shows that \((\mu_1 * 1)(p^a) = e(p^a)\) for every prime power \(p^a\text{.}\) Since both \(\mu_1 * 1\) and \(e\) are multiplicative, it follows that \(\mu_1 * 1 = e\text{.}\)

Definition 2.4.3.

The function \(\mu_1=\mu_2=\mu_3=\mu_4\) defined in the above theorem is called the Möbius function and we henceforth denote it by \(\mu\text{.}\)

Subsection 2.4.2 Möbius function and Dirichlet product

We have seen that \(\mu * 1 = e\text{.}\) Therefore if \(f\) and \(g\) are any arithmetic functions such that \(f * 1 = g\text{,}\) then \(f = g * \mu\text{.}\) This is called Möbius inversion.

Theorem 2.4.4. Möbius inversion.

\(f * 1 = g\) if and only if \(f = g * \mu\text{.}\) That is,

\begin{equation} g(n) = \sum_{d \mid n} f(d) \tag{2.4.6} \end{equation}

if and only if

\begin{equation} f(n) = \sum_{d \mid n} g(d) \mu\left(\frac{n}{d}\right) \text{.}\tag{2.4.7} \end{equation}

Proof.

Exercise.

For example we have \(\phi * 1 = N \text{,}\) and therefore \(\phi = N * \mu \text{:}\)

Corollary 2.4.5.

For all \(n \geq 1\text{,}\) \(\phi(n) = \sum_{d \mid n} \frac{n}{d} \mu(d)\text{.}\)

(As an exercise, how does this relate to our earlier result \(\phi(n) = n \prod_{p \mid n} (1 - 1/p)\text{?}\))

This gives another proof that \(\phi\) is multiplicative: Since \(\phi = N * \mu\text{,}\) and \(N\) and \(\mu\) are multiplicative, Theorem 2.3.5 shows that \(\phi\) is multiplicative.

Recall that the Von Mangoldt function \(\Lambda\) is defined by

\begin{equation} \Lambda(n) = \begin{cases} \log p, \amp \text{if } n = p^a \\ 0 , \amp \text{otherwise} \end{cases}\tag{2.4.8} \end{equation}

That is, \(\Lambda(p^a) = \log p\) for any prime power \(p^a \gt 1\text{,}\) but \(\Lambda(1)=0\) and \(\Lambda(n) = 0\) when \(n\) is not a prime power.

Theorem 2.4.6.

We have \(\Lambda * 1 = \log\text{.}\) That is,

\begin{equation} \sum_{d \mid n} \Lambda(d) = \log n\tag{2.4.9} \end{equation}

for all \(n \geq 1\text{.}\)

Proof.

For \(n = 1\) we have \(\Lambda(1) = 0\text{,}\) so \((\Lambda * 1)(1) = 0\text{.}\) And \(\log(1) = 0\text{.}\) So \((\Lambda * 1)(1) = \log(1)\text{.}\)

Let \(n \gt 1\) with prime factorization \(n = p_1^{a_1} \dotsm p_k^{a_k}\text{.}\) For \(d \mid n\text{,}\) we have \(\Lambda(d) = 0\) unless \(d\) is a prime power. Therefore

\begin{align*} (\Lambda * 1)(n) \amp = \sum_{d \mid n} \Lambda(d) \\ \amp = \sum_{j = 1}^k \Lambda(p_j) + \Lambda(p_j^2) + \dotsb + \Lambda(p_j^{a_j}) \\ \amp = \sum_{j = 1}^k \log(p_j) + \log(p_j) + \dotsb + \log(p_j) \qquad (a_j \text{ terms}) \\ \amp = \sum_{j = 1}^k a_j \log(p_j) \\ \amp = \log(p_1^{a_1}) + \log(p_2^{a_2}) + \dotsb + \log(p_k^{a_k}) \\ \amp = \log(n) \text{.} \end{align*}

Corollary 2.4.7.

For \(n \geq 1\) we have

\begin{equation} \Lambda(n) = \sum_{d \mid n} \mu(d) \log \frac{n}{d} = - \sum_{d \mid n} \mu(d) \log d\text{.}\tag{2.4.10} \end{equation}

Proof.

Since \(\Lambda * 1 = \log\text{,}\) by Möbius inversion we get \(\Lambda = \mu * \log\text{.}\) This shows

\begin{equation*} \Lambda(n) = \sum_{d \mid n} \mu(d) \log \frac{n}{d} \text{.} \end{equation*}

Now,

\begin{align*} \sum_{d \mid n} \mu(d) \log \frac{n}{d} \amp = \sum_{d \mid n} \mu(d) (\log n - \log d) \\ \amp = \sum_{d \mid n} \mu(d) \log n - \sum_{d \mid n} \mu(d) \log d \\ \amp = (\log n) \sum_{d \mid n} \mu(d) - \sum_{d \mid n} \mu(d) \log d \\ \amp = 0 - \sum_{d \mid n} \mu(d) \log d \text{.} \end{align*}

The reason \((\log n) \sum_{d \mid n} \mu(d) = 0 \) is the following. If \(n \gt 1\) then \(\sum_{d \mid n} \mu(d) = 0\text{,}\) by the recursive version of the definition of \(\mu\text{.}\) And if \(n = 1\) then \(\log n = 0\text{.}\)

Prev Top Next