NTIC The Moebius Function

🔗

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. Yes, this is the same Moebius (or Möbius) as the Moebius strip¹See [C.7.26] for some historical details, including Euler's discovery of the same idea via infinite products.

🔗

Example 23.1.2.

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.

🔗

Proposition 23.1.3.

If $n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}$ then a nice formula for $\mu(n)$ is

$\begin{equation*} \mu(n)=\begin{cases}0 & \text{ if any }e_{i}>1 \\(-1)^{k} & \text{ otherwise}\end{cases}\text{.} \end{equation*}$

🔗

Proof.

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.

🔗

Proposition 23.1.4. 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{.}$

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.5. Check your work again.

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

xxxxxxxxxx
 
moebius(30) + moebius(15) + moebius(10) + moebius(6) + moebius(5) + moebius(3) + moebius(2) + moebius(1)

🔗

Fact 23.1.6.

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:

xxxxxxxxxx
 
print(gcd(111,41))
print(moebius(111)*moebius(41)==moebius(41*111))

Section 23.1 The Moebius Function

Subsection 23.1.1 Möbius mu

Definition 23.1.1. Moebius mu.

Example 23.1.2.

Subsection 23.1.2 A formula

Proposition 23.1.3.

Proof.

Subsection 23.1.3 Another definition

Proposition 23.1.4. Recursive definition of μ\mu.

Proof.

Sage note 23.1.5. Check your work again.

Fact 23.1.6.

Proof.

Proposition 23.1.4. Recursive definition of $\mu$ .