Yesterday I mentioned Möbius inversion, and I decided that it was worth looking at a little bit more. First of all, it’s pretty fun. Secondly, it’ll give us a useful identity concerning .
Before I get too far, I should add another reference to my growing list. With Edwards’ book, and Hardy and Wright, include Apostol’s “Introduction to Analytic Number Theory.”
Anyway, yesterday I defined the Möbius function
and stated Möbius inversion as follows:
Thm: If then .
Let’s begin today with a proof of this statement. Pf: Suppose is as stated, and consider . By assumption on , this is which I’ll write as . Now in this sum, what is the coefficient of ? Well, it is . We saw yesterday that this sum is 0 unless , i.e., unless . So , as claimed.
That’s pretty fun, I think.
There’s another way to go about these things, and it is by way of what are called Dirichlet series (according to Wikipedia, Dirichlet had many names). Suppose is a function defined on the positive integers (such a function seems to sometimes get called an arithmetic function). I’ll say that the Dirichlet series for is the series . I’ve written it this way, so that I have a function defined whenever the series converges, but I’ll pretty much ignore convergence aspects in what follows.
Suppose and are the Dirichlet series associated to some , respectively. What does the product of these two series look like? Well, since , you can determine that the product of these two Dirichlet series is another Dirichlet series, this one associated to the function . Indeed, just ask yourself, “what is the coefficient of in the product of the series and ?”
By the way, I’ve called the product series because it also gets called the convolution of and . The convolution of and is denoted , and is simply the function .
Now you’ve got an operation, , on arithmetic functions, and you can start asking what properties it has. It turns out that gives the set of arithmetic functions (well, those functions that aren’t 0 on the input 1) the structure of a commutative group. The identity is the function with and if (corresponding to the identity Dirichlet series, the constant function 1). It’s sort of a fun little induction problem to find a formula for the inverse of a given arithmetic series. We won’t need the formula exactly, so perhaps I’ll leave it for you.
Let , so that the associated Dirichlet series is .
We now have another language in which to state Möbius inversion:
Thm: If then .
In this statement, let (the identity of convolution) so that . Then we obtain . On taking Dirichlet series, we find that
or, in other words,
How’s that for an identity?
There’s another way to get at this identity, without the language of Dirichlet series (explicitly anyway), which I wrote “holy crap” next to in the book (Hardy and Wright) when I read it. So probably I should share. Using Euler’s product (recall the indexing is over primes)
Here’s the part that rocked me: Look at and write it as , i.e. as . Because the first thing I think to do when I see a binomial is to write it as an infinite series of mostly 0s. Like I said yesterday, I guess it helps if you know where you are going. So anyway, we’ve got
Now, like we’ve been doing, let’s ask, “what is the coefficient of when the product is all written out?” Well, the only way to get is the term corresponding to the prime factorization of . If , then the coefficient is . But is “multiplicative,” meaning that if and are relatively prime then . So the coefficient of is just . This proves the identity.
That’s the identity we’ll use in the next post or two to finally tie together Farey sequences and the zeta function, believe it or not. So I’ll basically stop here. But I do want to mention that you can do some of the things we’ve done above in slightly more general contexts, and I remember really enjoying reading about them. Namely, you can work in other posets. In what we’ve been doing above, there has, somewhere in the background, been the poset of positive integers ordered by iff . Probably a good place to start reading about the generalization is Wikipedia, as usual. If I find, sometime, the paper I read where I first saw these things, I’ll update this post.
In the mean time…