We know a lot about the and -functions, we've learnt all about the different prime counting functions, most notably , so it's high time we found a connection between the two. Probably not too surprisingly, the crucial link is our good friend, the Euler product
What we want to develop now is a version of this product that will suit us to find a formula that magically can count primes. (Remember that the Euler product is an analytical version of the fundamental theorem of arithmetic, so this is a natural starting point for our search.)
The only trouble is that we have a product, but analysis is all about series. Luckily, we have another good and reliable friend that can transform a product into a sum: the logarithm. So, by taking on both sides, we obtain something easier to handle:
The cool bit is that there is a classical result that gives us a series expression for . This dates back to Isaac Newton and goes as follows:
which immediately allows us to substitute the inner term:
With some technical acrobatics we can convince ourselves that the series are sufficiently well behaved, such that we can swap the order of summation and write instead
Granted, this doesn't look any easier or even friendly than our nice, familiar Euler product, but remember the slightly esoteric function we defined to count prime powers:
As you see, the only real differences are that the innermost sum is truncated at , and the additional factor in the sum. We will handle both issues by introducing analysis' killer feature: integrals. If you just exercise a little basic calculus, it's easy to see that can be expressed as
(Just notice that the antiderivative of is which is zero at infinity since we assume here .) Now, let's plug this into our expression above:
Yes, I know this looks even messier than before, but bare with me, it's worth it and will become clearer shortly. What we want to do next is drag the integral sign out of the sums. This is no problem in principal since integration is "transparent" under addition, but we have to keep two things in mind: First, since we talk about infinite sums, caution is in order to ensure convergence, and second, the range of integration depends on the variables we're summing over, so we need to think how this range may change. As usual, we don't pay too much attention to the question of convergence, but are just happy for others to take care of the technicalities. The second point, however, needs some thinking. The easiest way to find the right boundaries for integration and summation is to consider the different ranges and formulate common constraints. In this case we sum over all (this will remain unchanged), all primes , and integrate over all . So, if we want to take the integral out of the sums and make the range independent of and , we extend it to , but need to add the restriction then to the summation over the primes . That's it! We obtain:
I've already put the parentheses in the right place, so we only need to compare this to our definition above, and notice with a sign of relieve that things start to look prettier:
John Derbyshire dubbed this formula the Calculus Version of the Golden Key, his nickname to the Euler product. He also gave a little more (graphical) intuition behind the deduction of the formula in chapter 19.V-VI of his book.
You may still not be convinced that any of this is useful. After all, we didn't get anything other than an expression for that not only contains a formula we can hardly control, but on top of it all is even hidden away in an integral. But just as we recovered from the definition of through a clever trick known as Möbius-inversion, we can now recover from the formula we found through an even more powerful tool called Fourier-inversion. Again, this would not only deserve its own article, but rather its own blog. Instead, I will just present you the result that we obtain by applying a little Fourier-magic to the Golden Key:
where is any real number with . Now, recall that we can express as a product over its zeros (which means we have a series expression for ), and hence we will be able to express as a sum over the legendary -zeros. Further, we can calculate from (in fact, these behave the same asymptotically), and so we can exactly (mind, these are strict equalities, not only approximations) count the primes by virtue of calculating the zeros.
These stubborn, erratic creatures that we call primes are thereby completely determined by the zeros of Riemann's -function. This is what makes the Riemann Hypothesis so powerful and surprising: Primes are volatile and unpredictable, but they obey the law of the zeros, and if Riemann was right, these zeros fall all on one single straight line, out of all possible places in the critical strip. Bernhard Riemann brought order to the chaos that governed the prime research for two millennia!