Proposition

Tag 0A73, permanent. Cite it as [Bourbaki, Tag 0A73].

Lie Groups and Lie Algebras, chapter II, Appendix 0. Möbius function

(i) The function $\mu$ is the unique mapping of $\mathbf{N}^*$ into $\mathbf{Z}$ such that $\mu(1) = 1$ and

\sum_{d|n} \mu(d) = 0

for every integer $n > 1$ .

(ii) Let s and t be two mappings of $\mathbf{N}^*$ into a commutative group written additively. In order that

s(n) = \sum_{d|n} t(d) \quad \text{for every integer } n \geq 1,

it is necessary and sufficient that

t(n) = \sum_{d|n} \mu(d) s\left(\frac{n}{d}\right) \quad \text{for every integer } n \geq 1.

The uniqueness assertion in (i) is obvious, for (1) allows us to determine $\mu(n)$ by induction on n. We show that the function $\mu$ satisfies (1). Let n be an integer $> 1$ . Let P be the set of prime divisors of n and let $n = \prod_{p \in P} p^{\nu_p(n)}$ be the decomposition of n into prime factors. If d is a divisor of n, then $\mu(d) = 0$ unless d is of the form $\prod_{p \in H} p$ , where H is a subset of P. Then

\sum_{d|n} \mu(d) = \sum_{H \subset P} (-1)^{\mathrm{Card}\ H} = \sum_{k=0}^{\mathrm{Card}\ P} \binom{n}{k} (-1)^k = (1 - 1)^{\mathrm{Card}\ P} = 0.

Let s and t be two mapping of $\mathbf{N}^*$ into a commutative group written additively. Let $n \in \mathbf{N}^*$ . If (2) holds, then

\sum_{d|n} \mu(d)s\left(\frac{n}{d}\right) = \sum_{d|n} \mu(d) \sum_{\delta|(n/d)} t(\delta) = \sum_{d|n} \mu(d)t(\delta)

= \sum_{\delta|n} t(\delta) \sum_{d|(n/\delta)} \mu(d) = t(n).

Conversely, if (3) holds, then

\sum_{d|n} t(d) = \sum_{d|n} \sum_{\delta|d} \mu(\delta)s\left(\frac{d}{\delta}\right) = \sum_{d|n} s(d) \sum_{\delta|(n/d)} \mu(\delta) = s(n),

which completes the proof.

Formula (3) is called the Möbius inversion formula.

Bourbaki puts the proof directly after the statement, so what is above is the statement and its proof together.

Cited by

Nothing.

Cites

Nothing.