MAT 338 Day 39 2011

2331 days ago by kcrisman

Let's start off with introducing some of the topics on the second take-home 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?

  • What denominators show up?
  • Which ones don't?
  • For the ones that do, what are the values of the numerator?
  • Can you predict the value of the numerator for some types of denominators? (E.g., primes, perfect squares, prime powers, etc.)




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.

  • Let's think about this product.  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$; 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.
  • So we get a nice 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.


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.

  • If $d$ is such a divisor, let $\omega_d$ be the number of distinct prime factors of $d$.
  • Let $k$ be the total number of prime divisors of $n$ itself.  (This is the biggest $\omega_d$ could be.) 

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)}\, .$$ 

  • We see that we get a bunch of stuff that looks like $(1)^{k-a}(-1)^{a}$.
  • In fact, we get one of them for each subset of $\{1,2,\ldots,k\}$.  
  • But that is the same as picking a subset of the primes dividing $n$...
  • Which is the same as picking a $d$ that has $\omega_d=a$.

So the sum $$\sum_{d\text{ that work}}(-1)^{\omega_d}=(1+(-1))^{k}=0\, .$$  Hence, we have proved that $\sum_{d|n}\mu(d)=0$.


By the way, it should be obvious from the formula above that $\mu$ is multiplicative.  


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.  

  • Let $f$ and $g$ be arithmetic functions.
  • Then we define the new function $f\star g$ via the formula $$(f\star g)(n)=\sum_{de=n}f(d)g(e)=\sum_{d\mid n}f(d)g\left(\frac{n}{d}\right)\, .$$  
  • For example, if $u(n)=1$ and $N(n)=n$, then $$(\varphi\star u)(n)=\sum_{d\mid n}\varphi(d)u\left(\frac{n}{d}\right)=\sum_{d\mid n}\varphi(d)=n=N(n)\; .$$ 
    • We really knew this long ago, of course, but now we can write it concisely as $\varphi\star u=N$.

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.


  • Let's expand the formula for $g(n)$ the theorem would give, in terms of $g$ itself: $$\sum_{d\mid n}\mu(d)f\left(\frac{n}{d}\right)=\sum_{d\mid n}\mu(d)\left[\sum_{e\mid \frac{n}{d}}g(e)\right]\, .$$  
  • Each time $g(e)$ appears in this sum, it has a coefficient of $\mu(d)$.  How often does this happen, and what is $d$ anyway?  
  • If $e\mid \frac{n}{d}$, then $e\mid n$, which means $\frac{n}{e}$ is an integer.  
  • This integer must have at least a factor of $d$ left.
    • Why? Since $e$ divides $\frac{n}{d}$, we have $ed\mid n$, in which case certainly $d\mid \frac{n}{e}$.  
  • So $g(e)$ shows up once for each $d\mid \frac{n}{e}$, with coefficient $\mu(d)$.
  • Thus, $$\sum_{d\mid n}\mu(d)f\left(\frac{n}{d}\right)=\sum_{e\mid n}\left(\sum_{d\mid \frac{n}{e}}\mu(d)\right)g(e)\, .$$ 
  • But unless $\frac{n}{e}=1$, $\sum \mu(d)=0$, so the only one that sticks around is the term for $\frac{n}{e}=1$, or when $e=n$.  
  • Thus the whole sum collapses to $g(n)$, as desired!


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:

  • $u(n)=1$ for all $n$
  • $N(n)=n$ for all $n$
  • $I(n)=\begin{cases}1& n=1\\0 & n>1\end{cases}$

In the next computational cell, we define these, as well as a Dirichlet product function.  Now let's see what we get!

def u(n): return 1 def N(n): return n def I(n): return floor(1/n) def DirichletProduct(f,g,n): return sum(f(d)*g(n/d) for d in divisors(n)) 

For instance, what happens if we look for the inverse of $N$?

@interact def _(n=10): H = [['$i$','$(N\star \mu)(i)$']] T = [(i,DirichletProduct(N,moebius,i)) for i in [1..n]] html.table(H+T,header=True) 

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.

@interact def _(n=10): H = [['$i$','$(\\varphi\star u)(i)$']] T = [(i,DirichletProduct(u,euler_phi,i)) for i in [1..n]] html.table(H+T,header=True) 

Click to the left again to hide and once more to show the dynamic interactive window

Interestingly, this means that

  • $N=\varphi\star u$
  • $N\star\mu=\varphi$

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!)

@interact def _(n=10): H = [['$i$','$(\\tau\star \mu)(i)$']] T = [(i,DirichletProduct(lambda y: sigma(y,0),moebius,i)) for i in [1..n]] html.table(H+T,header=True) 

Click to the left again to hide and once more to show the dynamic interactive window

@interact def _(n=10): H = [['$i$','$(\sigma\star \mu)(i)$']] T = [(i,DirichletProduct(sigma,moebius,i)) for i in [1..n]] html.table(H+T,header=True) 

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.

  • Let $A$ be the set of all arithmetic functions.
  • Then $\star$ turns the set $A$ into a commutative monoid.
    • That's a set with multiplication that has an identity, is associative and commutative.  You can think of it as a group without inverses.
    • The function $I(n)$, which is equal to zero except when $n=1$, plays the role of identity.  
  • One would need to prove the following:
    • $f\star g=g\star f$
    • $(f\star g)\star h = f\star (g\star h)$
    • $f\star I=f = I\star f$

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$.

  • Hence the subset of $A$ where $f(1)\neq 0$ is actually a group!
  • We call the inverse $f^{-1}$, unsurprisingly.
  • The inverse is given by $f^{-1}(1)=\frac{1}{f(1)}$ and, for $n>1$, the condition $$\sum_{d\mid n}f^{-1}(d)f\left(\frac{n}{d}\right)=\sum_{de=n}f^{-1}(d)f(e)=0\, .$$  

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:

  • The Moebius inversion formula that $f=g\star u$ then $g=f\star \mu$ can be proved concisely by $$g=g\star I=g\star u\star \mu=f\star \mu$$ (no parentheses needed since $\star$ is associative).
  • Conversely, if $g=f\star \mu$, then $f=f\star I=f\star \mu\star u=g\star u$!  So the inversion formula is true in both directions.
  • If $f$ is multiplicative and $f(1)\neq 0$, then $f^{-1}$ is also multiplicative.  (We'll prove this below.)
    • As a corollary, $\mu$ is multiplicative, since $u$ is multiplicative (trivially) and $\mu=u^{-1}$!  
  • If $g$ and $h$ are multiplicative, then $f=g\star h$ is also multiplicative.  The proof is well worth doing, and will just follow from using the definitions and calculating.
  • If $f=g\star u$ (equivalently, if $g=f\star \mu$), then $f$ and $g$ are either both multiplicative or both not.  
    • This follows because if $f$ is multiplicative, we use the previous bullet point with $u$, and if $g$ is multiplicative, we use the previous bullet point with $\mu$.


Proof (that if $f$ is multiplicative and $f(1)\neq 0$, then $f^{-1}$ is also multiplicative):

  • This basically can be done by induction.  
  • Recall that the inverse is defined by by $$f^{-1}(1)=\frac{1}{f(1)}$ and, for $n>1$, the condition $$\sum_{d\mid n}f^{-1}(d)f\left(\frac{n}{d}\right)=\sum_{de=n}f^{-1}(d)f(e)=0\, .$$
  • First, $$f^{-1}(1)=\frac{1}{f(1)}\neq 0\; .$$
  • Also, $$f(1\cdot n)=f(1)f(n)\text{ so }f(1)=1=f^{-1}(1)\; .$$
  • Next, assume that $f^{-1}$ is multiplicative for inputs less than $mn$, with $gcd(m,n)=1$.  
  • Then let $m,n>1$ and coprime.  We will be able to dissolve everything.  
    • By the definition of inverse, we have $$0=(f^{-1}\star f)(mn)=\sum_{x<mn,\; xy=mn}\left(f^{-1}(x)f(y)\right)+f^{-1}(mn)f(1)\; .$$ 
    • Note that the only piece we do not know is multiplicative here is $f^{-1}(mn)$; all the others ($x,y$, and anything to do with $f$) are multiplicative by induction or by assumption.
    • Each summand is over $xy$.  Each $xy$ is itself, by coprimeness of $m$ and $n$, itself a product $x=ab$ and $y=cd$ of things that are coprime - $a,c\mid m$ and $b,d\mid n$.
    • So multiplicativity implies $$f^{-1}(x)f(y)=f^{-1}(a)f^{-1}(b)f(c)f(d)\; .$$
  • This gives, along with $f(1)=1$ and the sum being zero, $$f^{-1}(mn)=-\sum_{(ac)(bd)=(m)(n),ab<mn}f^{-1}(a)f^{-1}(b)f(c)f(d)$$  So now we have to figure out how to write this sum in terms of things we already know.
    • Notice that if we didn't have $ab<mn$, the sum would easily simplify as a product: $$\sum_{(ac)(bd)=(m)(n)}f^{-1}(a)f^{-1}(b)f(c)f(d)=\sum_{ac=m}f^{-1}(a)f(c)\sum_{bd=n}f^{-1}(b)f(d)$$
    • We are only missing the term with $a=m,b=n$ from this sum, in fact.
    • So $$\sum_{(ac)(bd)=(m)(n),ab<mn}f^{-1}(a)f^{-1}(b)f(c)f(d)=\sum_{ac=m}f^{-1}(a)f(c)\sum_{bd=n}f^{-1}(b)f(d)-f^{-1}(m)f^{-1}(n)f(1)f(1)$$
  • Now we plug this back into the previous characterization of $f^{-1}(mn)$: $$f^{-1}(mn)=- \left[\sum_{ac=m}f^{-1}(a)f(c)\sum_{bd=n}f^{-1}(b)f(d)-f^{-1}(m)f^{-1}(n)f(1)f(1)\right]$$
  • And since $m,n>1$, the sums are just $$(f^{-1}\star f)(m)=u(m)=0=u(n)=(f^{-1}\star f)(n)$$
  • That means $$f(m)f(n)=f^{-1}(m)f^{-1}(n)$$ as well. 


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!

@interact def _(n=10): H = [['$i$','$(\mu\star \mu)(i)$']] T = [(i,DirichletProduct(moebius,moebius,i)) for i in [1..n]] html.table(H+T,header=True) 

Click to the left again to hide and once more to show the dynamic interactive window

@interact def _(n=10): H = [['$i$','$(u\star u)(i)$']] T = [(i,DirichletProduct(u,u,i)) for i in [1..n]] html.table(H+T,header=True) 

Click to the left again to hide and once more to show the dynamic interactive window