Skip to main content
🔗

Section 23.1 The Moebius Function

🔗

Subsection 23.1.1 Möbius mu

🔗
Let's define the function which gives the numerator associated with denominator n in the products above.

🔗
Definition 23.1.1. Moebius mu.

Let N=2⋅3⋅5⋯q be the product of the first few primes, up to q. Then we define μ(d) as follows:

∏p∣N(1−1p)=∑d∣Nμ(d)d.

The product is over prime factors of N but the sum is over all factors of N.

🔗
It is not at all obvious that μ will have the same value regardless of N, and much of the rest of this section will confirm this.

🔗
Historical remark 23.1.2. August Möbius.

Yes, this is the same August Moebius (or Möbius) as the Moebius strip; however, it was not he, but Johann Listing who first discovered that object. On the other hand, his work with this function and the Möbius Inversion Formula has stood the test of time. A student of Gauss, Möbius' positions were mostly directorships of major observatories and professor of astronomy. See [E.7.26] for some historical details of the function, including Euler's discovery of the same general idea via infinite products.

🔗
Example 23.1.3.

Using the example in the chapter introduction,

D(3)=(1−1/2)(1−1/3)=(11−12−13+16)

implies that μ(2)=−1=μ(3) while μ(6)=1=μ(1).

🔗
There is no product of (1−1/p) that will yield a four in the denominator, since (1−1/2) only occurs once in such a product. So μ(4)=0, as the example above already implies.

🔗

Subsection 23.1.2 A formula

🔗
Before describing this function further, let's think more about the product ∏p<N(1−1p).

  • First, as the comment at the end of the last subsection points out, it seems to create denominators with each prime factor to just the first power. We couldn't get a square or cube of any given p in the denominator.

  • Similarly, the numerators really can only be products of 1 and −1. For a moment, think about why there are no other numerators available.

  • Finally, the number of prime factors in the denominator should be the same as the number of times −1 is part of the product in the numerator.

🔗
This essentially proves the following proposition.

See above.

🔗

Subsection 23.1.3 Another definition

🔗
The μ function is so important that we will want several more approaches as well. It is a mark of an important concept that there are ways to define it from many directions.

🔗
One important way that μ is often defined is via a recurrence relation. That is, one defines

μ(1)=1, and ∑d∣nμ(d)=0.

🔗
Now, we haven't proved this identity yet, and probably the reader hasn't even noticed it. But if we can prove the identity works for μ, then since μ(1)=1 is true, this would give an alternate definition.

Let's rewrite the sum \(\sum_{d\mid n}\mu(d)=0\) by trying to omit the \(\mu(d)\) that equal zero. If we do this, the sum reduces to the long, but correct,

\begin{equation*} \sum_{d\mid n}\mu(d)=\sum_{\substack{\text{all divisors }d\text{ with just one or zero}\\\text{ of each prime factor }p_{i}\text{ of }n}}(-1)^{\text{the number of primes dividing } d}\text{.} \end{equation*}

Now let's set up a little notation. First, let's borrow from Definition 23.3.3 the notation \(\omega(d)\) for the number of distinct prime divisors of a divisor \(d\) of \(n\text{.}\) Next, for convenience we will write \(k=\omega(n)\) for the number of (again, distinct) prime divisors of \(n\) itself.

Then the crazy sum \(\sum_{d\mid n}\mu(d)\) becomes easier to write:

\begin{equation*} \sum_{\substack{\text{all divisors }d\text{ with just one or zero}\\\text{ of each prime factor }p_{i}\text{ of }n}}(-1)^{\omega(d)}\text{.} \end{equation*}

If at this point you are asking yourself why I bothered introducing \(k\text{,}\) you may want to think about that briefly while reading the next formula:

\begin{equation*} \sum_{\substack{\text{all divisors }d\text{ with just one or zero}\\\text{ of each prime factor }p_{i}\text{ of }n}}(-1)^{\omega(d)} =\sum_{d\text{ that work}}(1)^{k-\omega(d)}(-1)^{\omega(d)}\text{.} \end{equation*}

Note that \((k-\omega(d))+\omega(d)=k\text{.}\)

Let's step back for a rationale for all this manipulation. Consider each of the divisors \(d\) with no square factors (the ones in question that we are indexing by). Each of these have \(\omega(d)\) of the prime factors of \(n\text{;}\) that means that they do not have the other \(k-\omega(d)\) possible prime factors available to us from \(n\text{.}\) So in the expression \((1)^{k-\omega(d)}(-1)^{\omega(d)}\) we are, in some sense, picking a subset (of size \(\omega(d)\)) of the primes dividing \(n\) and multiplying by \(1\) for each of those; likewise we multiply by \(-1\) for each possible prime not picked.

This is a combinatorial point of view, which means we can count all this picking another way. Instead, consider just picking a subset of \(\{1,2,\ldots,k\}\) and assigning \(\pm 1\) respectively; that would be the same thing. However, we can reinterpret that as picking a particular term in the full expansion of the \(k\)th power of the binomial \(1+(-1)\text{:}\)

\begin{equation*} (1+(-1))^{k}=(1+(-1))(1+(-1))\cdots(1+(-1))\text{ (k }\text{ times, for }2,3,\ldots , p_k)\text{.} \end{equation*}

Summing all the possible terms must be the same as calculating this power, so an easy computation finishes the proof:

\begin{equation*} \sum_{d\text{ that work}}(-1)^{\omega(d)}=(1+(-1))^{k}=0\text{.} \end{equation*}
🔗
Sage note 23.1.6. Check your work again.

Remember, we can always check calculations like this with our computational assistant.

We will postpone a formal proof of this to a much bigger theorem, from which this result (Corollary 23.4.15) will fall “for free”.

🔗
Let's check it: