I wanted to write this post yesterday, but I couldn’t work out some of the steps that I wanted to be able to work out, so I had to wait a day and try again. But I think I’ve got it now, let’s see…

We’ve been working with the function

Last time, we arrived (skipping over some rather large gaps) at an analytic formula for , namely:

where (mod issues)

The goal today is to use this formula for to find a formula for primes. In particular, we will find a formula for , which is the number of primes no larger than . These two functions are related, as follows: recall that is a step function which jumps by at every prime power . Pick an . How many jumps of size 1 does make before getting to ? Well, it jumps by 1 at the primes, so it makes jumps of size 1. How many jumps of size 1/2? These are jumps at prime squares, . This inequality is the same as , so we make jumps of size 1/2. Similarly, we’ll make jumps of size to calculate . Eventually (for some large enough ) will be less than 2, and so , and we can stop looking for jumps.

Translating the above into symbols, we have just decided that

I’ve written it as an infinite sum, but eventually (like I said) those values will be 0, so we’ve really got a finite sum.

Now wait, our goal was a formula for , in terms of , and I’ve got a formula the other way, in terms of .

This is the part I got stuck on yesterday. Edwards’ book says (or perhaps doesn’t, causing my problems) that basically you do Möbius inversion to the sum above, and obtain a formula for in terms of . He says slightly more than that, but I wasn’t able to piece it together as easily as he seemed to indicate it should work. But anyway, what’s this Möbius inversion thing? I’ll take a pretty low-level account, leaving lots of room for things to be jazzed up (which I may return to and do sometime soonish).

An integer is said to be “squarefree” if it factors into the product of distinct primes or, equivalently, it is not divisible by a square. Define the following function, called the Möbius function, on positive integers ( is supposed to indicate a prime):

So, for example, is -1 at any prime, , and .

Möbius inversion is then the following:

If then , and conversely.

Well, I tried to figure out how my expression for , in terms of s was such an of . I don’t see it, as stated. Perhaps somebody can point me in the right direction in the comments.

The observation you are supposed to make comes when you consider something like . Using our formula above, we can write

or, more generally, we have

If we subtract this equation (with ) from the equation for in terms of s, we can eliminate one term from the right-hand side. The idea is to iterate this process. I think a (reasonably, by my blog’s standards) clean way to write what is happening is as follows (it helps when you know the answer you are supposed to get :)):

Consider the sum

which by our most recent formula is the same as

Now, fix a positive integer . The coefficient of in this last double sum is

Almost there… what is ? Turns out, it is 1 if (which is clear), and 0 otherwise. Indeed, suppose has prime factorization . Then all of the divisors, in the sum we’re after, are of the form where each . The only divisors, , where are those where the are all either 0 or 1. So the worthwhile could be 1, or some , or a (), or (, , ), etc. So

(By the way, this is (almost verbatim) the proof in Hardy and Wright’s “An Introduction to the Theory of Numbers”, and I’ll count that as one of my references for anything I say about ).

So, let’s gather back up here. We’ve now shown that in the sum

the coefficient of is 0 unless , when the coefficient is 1. Therefore, we have obtained out formula for :

I guess the point of Riemann’s paper was that the terrible integral formula he obtained for could then be used in this expression for , to give an exact *analytic* expression (that is, one only an analyst would find pretty) for . Pretty wild, in my mind.

It seems that if you get some feeling for the terms in , you can decide that the “dominant” term is the term. And then that still ends up as the dominant term in the expression above for . And so you get to say

So you’ve got that going for you, which is nice.

Tags: mablowrimo, mobius, primes, riemann

January 7, 2010 at 2:00 pm |

interesting