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.
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.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.
Proposition 23.1.5. Recursive definition of \(\mu\).
We can define \(\mu\) by setting \(\mu(1)=1\) and
\begin{equation*}
\sum_{d\mid n}\mu(d)=0\text{.}
\end{equation*}
Proof.
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.
Fact 23.1.7.
The function \(\mu\) is multiplicative.
Proof.
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:
mathshistory.st-andrews.ac.uk/Biographies/Listing/
