Let's start off with introducing some of the topics on the second takehome project. No more homework, just this to finish off!
In the homework for today, we introduced an interesting function, $$D(N)=\prod_{p<N}\left(1\frac{1}{p}\right)$$ where $p$ is prime; what patterns did you find?
It turns out that this function is a very important one, and indeed the key to unlocking many of the secrets of arithmetic functions, as we'll see in a moment. We can define $\mu(n)$ as the numerator associated with denominator $n$ in the products above. This function is called "Moebius mu", and yes, it is the same Moebius as the Moebius strip!
To be precise, we define $\mu$ by letting the product of the first few primes be $N=2\cdot 3\cdot 5\cdots q$ and using the property $$\prod_{p\mid N}\left(1\frac{1}{p}\right)=\sum_{d\mid N}\frac{\mu(d)}{d}\; ,$$ where the product is over prime factors of $N$ but the sum is over all factors of $N$.
That means that sometimes $\mu(n)=0$, of course.
There are several alternate descriptions, however! First, let's get a specific formula.
Fact: A nice formula for $\mu(n)$ is given thus: $$\text{If }n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}\text{ then }\begin{cases}\mu(n)=0 & \text{ any }e_{i}>1 \\\mu(n)=(1)^{k} & \text{ otherwise}\end{cases}.$$
That's pretty good!
Another way that $\mu$ is often defined is via a recurrence relation. That is, one defines $$\mu(1)=1,\text{ and }\sum_{d\mid n}\mu(d)=0\; .$$ Now, we haven't proved this identity yet, or even noticed it. But if we can prove the identity works for $\mu$, then since $\mu(1)=1$ is true, this would give an alternate definition.
Proof:
Let's rewrite the sum $\sum_{d\mid n}\mu(d)=0$ by trying to omit the ones that are zero anyway. If we do this, the sum reduces to the long, but correct, $$\sum_{d\mid n}\mu(d)=\sum_{\text{all divisors }d\text{ with just one or zero of each prime factor }p_{i}\text{ of }n}(1)^{\text{the number of primes dividing } d}\, .$$ Now let's set up a little notation.
Then the crazy sum becomes the easier to write $$\sum_{\text{all divisors }d\text{ with just one or zero of each prime factor }p_{i}\text{ of }n}(1)^{\omega_d}=\sum_{d\text{ that work}}(1)^{k\omega_d}(1)^{\omega_d}\; .$$
Now consider the seemingly unrelated issue of expanding $$(1+(1))^{k}=(1+(1))(1+(1))\cdots(1+(1))(k\text{ times)}\, .$$
So the sum $$\sum_{d\text{ that work}}(1)^{\omega_d}=(1+(1))^{k}=0\, .$$ Hence, we have proved that $\sum_{dn}\mu(d)=0$.
0 0 
By the way, it should be obvious from the formula above that $\mu$ is multiplicative.
1 True 1 True 
However, we will postpone a formal proof of this to a much bigger theorem from which that will fall 'for free'.
So what is the point of this function? Here is why  a famous theorem!
Theorem (Möbius Inversion Formula): $$\text{If }f(n)=\sum_{d\mid n}g(d)\text{, then }g(n)=\sum_{d\mid n}\mu(d)f\left(\frac{n}{d}\right)\; .$$
Briefly speaking, if you sum an arithmetic function over divisors, then summing that function over divisors along with $\mu$ gives you back the original function.
The reason we care about this is that we are able to use the $\mu$ function to get new arithmetic functions via this theorem. In particular, we can 'invert' all of our usual arithmetic functions, and this will lead to some very powerful applications.
In order to better understand what this theorem is saying, let's introduce some notation.
So we could restate the theorem as, $$\text{If }f=g\star u\text{, then }g=f\star \mu\; .$$
Such a "product" of two functions is called the Dirichlet product of the functions; we will discuss this more later.
Proof:
In order to see what good this does, let's see what happens when we mess around and make Dirichlet products with functions we know. We already know two of these functions, and I give you a third:
In the next computational cell, we define these, as well as a Dirichlet product function. Now let's see what we get!

For instance, what happens if we look for the inverse of $N$?
Click to the left again to hide and once more to show the dynamic interactive window 
Surprise! But this makes sense, if you remember our comment above about $N = \varphi\star u$.
Let's confirm this numerically.
Click to the left again to hide and once more to show the dynamic interactive window 
Interestingly, this means that
We'll get back to that observation in a second.
Sticking with $\varphi$ for a little longer, notice that this gives an alternate proof of our formula for it, based on our first definition of $\mu$!
$$\varphi(n)=N\star\mu(n)=\sum_{d\mid n}N\left(\frac{n}{d}\right)\mu(d)=n\sum_{d\mid n}\frac{\mu(d)}{d}=n\prod_{p\mid n}\left(1\frac{1}{p}\right)$$
Before we do them with Sage, try computing the Moebius inversions of our old friends, $\sigma$ and $\tau$, by hand for several values. (Hint: try primes and perfect powers first, as they don't have many divisors!)





Click to the left again to hide and once more to show the dynamic interactive window 
Click to the left again to hide and once more to show the dynamic interactive window 
There is loads of fun to be had here, and you will have some on the project.
There is a more serious side as well, though, and this is our key to arithmetic functions. We will now turn to algebra  not quite groups, but almost.
The only one of these that's even a little hard is the second one, but one can use the Transitions to Higher Math type fact that $dc=n,ab=d$ implies $abc=n$ to do it. Here is an example; the others are similar.
Proof of commutativity:
$$f\star g=\sum_{d\mid n}f(d)g\left(\frac{n}{d}\right)=\sum_{de=n}f(d)g(e)$$ $$=\sum_{de=n}g(e)f(d)=\sum_{e\mid n}g(e)f\left(\frac{n}{e}\right)$$
This algebraic structure is so neat is because it actually allows us to generalize the idea behind the Moebius function to anything in particular!
Theorem: If $f$ is an arithmetic function and $f(1)\neq 0$, then $f$ has an inverse in the set $A$ under the operation $\star$.
Notice that means exactly that the definition of the Moebius function $\mu$ is $\mu=u^{1}$.
We could also say that $f\star f^{1}=I=f^{1}\star f$.
As in the best theorems, there is really nothing to prove; we can always get the next $f^{1}(n)$ by knowledge of $f^{1}(d)$ for $d\mid n$, and that is induction since we do have a formula given for $f^{1}(1)$.
This new way of looking at things yields a slew of information about arithmetic functions which will yield dividends about analysis/calculus (no, we haven't forgotten that!) immediately. For instance:
Proof (that if $f$ is multiplicative and $f(1)\neq 0$, then $f^{1}$ is also multiplicative):
There is lots of fun to be had now. We could try to see what $\mu\star\mu$ is  or $u\star u$? Maybe a formula for $\mu$, or calculate then $\mu\star u$, or its Dirichlet inverse?
And it turns out there are all kinds of other functions you can define, like $\omega(n)$ (also called $\nu(n)$, confusingly, e.g. in your book on page 182), defined by $$\omega(n)=k\text{ if }n=\prod_{i=1}^k p_i^{e_i}\, .$$ So what is the $\star$ product of this with something, or where else does it show up?
Anyway, the sky's the limit. Enjoy!
Click to the left again to hide and once more to show the dynamic interactive window 
Click to the left again to hide and once more to show the dynamic interactive window 
