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\cdot 3\cdot 5\cdots q\) be the product of the first few primes, up to \(q\text{.}\) Then we define \(\mu(d)\) as follows:

\begin{equation*} \prod_{p\mid N}\left(1-\frac{1}{p}\right)=\sum_{d\mid N}\frac{\mu(d)}{d}\text{.} \end{equation*}

The product is over prime factors of \(N\) but the sum is over all factors of \(N\text{.}\)

It is not at all obvious that \(\mu\) will have the same value regardless of \(N\text{,}\) 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,

\begin{equation*} D(3)=(1-1/2)(1-1/3) = \left(\frac{1}{1}-\frac{1}{2}-\frac{1}{3}+\frac{1}{6}\right) \end{equation*}

implies that \(\mu(2)=-1=\mu(3)\) while \(\mu(6)=1=\mu(1)\text{.}\)

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 \(\mu(4)=0\text{,}\) as the example above already implies.

Subsection 23.1.2 A formula

Before describing this function further, let's think more about the product \(\prod_{p<N}\left(1-\frac{1}{p}\right)\text{.}\)

  • 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\text{.}\) 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 \(\mu\) 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 \(\mu\) is often defined is via a recurrence relation. That is, one defines

\begin{equation*} \mu(1)=1,\text{ and }\sum_{d\mid n}\mu(d)=0\text{.} \end{equation*}

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 \(\mu\text{,}\) then since \(\mu(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{.}\)

The rationale for all this manipulation is that we can think of each of the divisors \(d\) that have no square factors (the ones in question) as having \(\omega(d)\) of the prime factors of \(n\) picked, and the other \(k-\omega(d)\) factors omitted. So, in some sense, for each \(d\) we are really picking a subset of the primes dividing \(n\text{,}\) of size \(\omega(d)\text{,}\) and then multiplying by \(1\) for each prime picked and \(-1\) for each one not picked.

But if instead we consider just picking a subset of \(\{1,2,\ldots,k\}\) and assigning \(\pm 1\text{,}\) that would be the same thing, with the difference that we know this is the same as the result of expanding

\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*}

So the sum is

\begin{equation*} \sum_{d\text{ that work}}(-1)^{\omega(d)}=(1+(-1))^{k}=0\text{.} \end{equation*}

This finishes the proof.

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: