Rolfe Schmidt

I’m learning. Slowly.

Zeta and the Prime Numbers

with 9 comments

Whenever my kids ask a good question, I like to do my best to give them a good answer. So I was pretty frustrated when Gunnar asked me

If I take one half, plus one third, plus one fifth, plus for all of the prime numbers, will that make one?

The answer is no, the sum just keeps growing, getting larger than any number you can think of. But I have no idea how to explain it to him.

Here I’ll give the simplest proof I can think of, relying only on a little bit of Algebra II. If anyone can do better, please let me know! I’m not aiming for rigor here, although I’m happy to provide rigor on request. I’m just thinking about how I can get my boys interested in this stuff when the time comes. Or at least explain to them why I love it.

Adding All the Numbers

I want to start by playing some games with multiplication and addition.

First, notice that

(1 + 2)(1 + 3) = 1 + 2 + 3 + 6

For the moment, don’t try to add the numbers. Just think of addition as a way to write a list of numbers. This example shows how we can use multiplication to take two short lists and make a longer list.
What if we want a 4 to show up in the list? We can just write

(1 + 2 + 4)(1 + 3) = 1 + 2 + 3 + 4 + 6 +12

Now we are missing 5, so we fix it like this

(1 + 2 + 4)(1 + 3)(1 + 5) = 1 + 2 + 3 + 4 + 5 + 6 + 10 + 12 + 15 + 20 + 30 + 60

We can keep going like this: multiply by (1 + 7) to put 7 in the list, multiply by (1 + 2 + 4 + 8 ) instead of (1 + 2 + 4) to get 8 in the list, multiply by (1 + 3 + 9) instead of (1 + 3) to put 9 in the list. Play around with it, and you’ll see that

(1 + 2 + 4 + 8)(1 + 3 + 9)(1 + 5)(1 + 7)(1 + 11)(1 + 13) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14+ 15 + \text{bigger stuff, no number appears twice}

We can keep going like this, and will hit a hole in our list every time we hit either (1) a new prime number, or (2) a power of a prime number that we’ve already seen. We know how to fill in those holes

  1. When we hit a new prime number, p, multiply by (1 + p)
  2. When we hit a power of a prime number that we’ve already seen, say p^n, we will already have a term in our product that looks like (1 + p + p^2 + ... + p^{n-1}), so just add p^n to this term, giving you (1 + p + p^2 + ... + p^{n-1} + p^n)

If we keep going this way, we’ll put every number in our long list and no number will show up twice (this is another way to say that numbers can be uniquely factored into primes). We’ll end up with this interesting equation

(1 + 2 + 4 + ... + 2^n + ...)(1 + 3 + 9 + ...)(1 + 5 + 25 + ...)... = 1 + 2 + 3 + 4 + 5 + ...

Of course this is meaningless. Interesting, but meaningless. But interesting is good enough for me, so let’s charge forward.

In my first post in this series I introduced the Sigma notation for sums, so we didn’t have to write out all of those +-signs and ‘…’ marks. We can use that to make our formula a little more concise and precise here:

(\sum_0^\infty 2^i)((\sum_0^\infty 3^i)(\sum_0^\infty 5^i)... = \sum_0^\infty i

But we still have an infinite number of multiplications cluttering up the equation. We can use the Greek capital Pi, \Pi, just like we used Sigma before to take care of this. So, for example

\prod_{i=1}^{10} i

is just a shorthand way to write

1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 \times 10

Using the Pi notation, we can write

\prod_{p \textbf{ prime} }(\sum_{i = 0}^{\infty} p^i) = \sum_{i=0}^{\infty} i

Still meaningless, but it looks impressive!

Back to the zeta function

Now let’s make it meaningful. We weren’t interested in adding up whole numbers anyway. In our last post we found that when s > 1 we can define the Riemann zeta function

\zeta(s) = \sum_{n=0}^{\infty}\frac{1}{n^{s} }

Well we can play the same sort of list-making games with the numbers \frac{1}{n^s} that we did with the whole numbers. For example

(1 + \frac{1}{2^s})(1 + \frac{1}{3^s}) = 1 + \frac{1}{2^s} + \frac{1}{3^s} + \frac{1}{6^s}

(1 + \frac{1}{2^s} + \frac{1}{4^s})(1 + \frac{1}{3^s}) = 1 + \frac{1}{2^s} + \frac{1}{3^s} + \frac{1}{4^s} + \frac{1}{6^s}+ \frac{1}{12^s}

And so on. Try it.

This happens because the function f(n) = \frac{1}{n^s} is a homomorphism: f(nm) = f(n)f(m). [Excercise: Verify this.] If we repeat our argument from above, we’ll be able to write down a very fancy looking formula that actually means something

\prod_{p \textbf{ prime} }(\sum_{i = 0}^{\infty} \frac{1}{p^{si} }) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \zeta(s)

But wait a minute. Look at all of those sums on the left hand side — the ones that look like \sum_{i = 0}^{\infty} \frac{1}{p^{si}}. These are just geometric series, and we know that this just equals \frac{1}{1 - \frac{1}{p^{s}}}! So we can simplify the expression and write

\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p \textbf{ prime} }\frac{1}{1 - \frac{1}{p^{s}}}

This is called Euler’s product formula for the zeta function.

This is starting to look good. We’ve found a way to write the zeta function that only involves the prime numbers. And it is a neat expression, an analytic way to say that every number can be uniquely factored into primes. Any number that can’t be factored wouldn’t show up in our list-building exercises, and any number that can be factored two ways would have shown up in our list twice. I never proved that this can’t happen, so you might want to think about it a little more.

Turning products into sums

The problem is that we have an infinite product, and I had set out to study an infinite sum of primes. Luckily there is a function called the logarithm that turns multiplication into addition: \log(ab) = \log(a) + \log(b). I’m going to use the natural logarithm because, well, it’s natural. (Unless you’re doing computer science, when it’s natural to let e = 2.) Applying logs gives us the equation

\log(\zeta(s)) = \log(\prod_{p \textbf{ prime} }\frac{1}{1 - \frac{1}{p^{s}}}) = \sum_{p \textbf{ prime}} \log(\frac{1}{1 - \frac{1}{p^{s}}})

But it’s easy to check that \log(\frac{1}{x}) = -\log(x) (just look at \log(1) = \log (1\times\frac{x}{x}) = \log(1) + \log(x) + \log(\frac{1}{x})), so we can now write

\log(\zeta(s)) = \sum_{p \textbf{ prime}} -\log(1 - \frac{1}{p^s})

Approximate, simplify, and control the error

Now as p gets big, the value \frac{1}{p^s} is going to get really small. We know that \log (1) = 0, so we would expect \log(1 - \frac{1}{p^s}) to be really close to zero. If we knew how fast the logarithm function was changing near zero, we could get a pretty good estimate for these terms in the sum. Well here is a graph of the function -\log(1-x) and the function x near x = 0.

Approximating the natural logarithm

It turns out that x is a pretty good approximation. If we could just swap this function for the log function it would be great! We’d have

\log(\zeta(s)) \approx \sum_{p \textbf{ prime}} \frac{1}{p^s}

Which is just the sort of sum we wanted to study. This is why we used the natural logarithm instead of , say a base 10 or base 2 logarithm: the natural logarithm is the only one that is well approximated by a line with slope 1. If we used a different logarithm, we’d get some messy looking constants in our approximation.

Now we should make sure that our approximation is good enough!

To do that, let’s plot the error we make when we swap x for -\log(1-x) and compare it to the function x^2.

Controlling the approximation error

Notice that if x is close to 1, our error is much bigger than x^2, but as long as x < \frac{1}{2}, the error we make is certainlyless than x^2. For prime numbers p, \frac{1}{p^s} is always going to be less than a half, so we can write

\log(\zeta(s)) < \sum_{p \textbf{ prime}} \frac{1}{p^s} + \sum_{p \textbf{ prime}} \frac{1}{p^{2s}}

But now we know that \sum_{p \textbf{ prime}} \frac{1}{p^{2s}} < \sum_{n=1}^{\infty}\frac{1}{n^2} because the second sum ranges over all of the numbers, not just the primes. We also know, from our last post, that

\sum_{n=1}^{\infty}\frac{1}{n^2} < 2

So we can write

\sum_{p \textbf{ prime}} \frac{1}{p^s} < \log(\zeta(s)) < \sum_{p \textbf{ prime} } \frac{1}{p^s} + 2

And we have a pretty good idea how big our sum over the primes must be.

Now here is the fun part: \zeta(1) = \sum_{n=1}^{\infty}\frac{1}{n} = \infty, as we saw in our last post. This means that

\infty = \log(\zeta(1)) < \sum_{p \textbf{ prime}} \frac{1}{p} + 2

This can only happen if \sum_{p \textbf{ prime}} \frac{1}{p} is infinite.

Earlier I said this means that there are “a lot” of primes — enough to make this sum go to infinity. In a later post I’ll go into some more detail about exactly what that means, but this is enough for today.

Now how do I explain that to a 5-year-old?

Written by Rolfe Schmidt

March 14, 2008 at 9:07 am

Posted in Math

«
»

9 Responses

Subscribe to comments with RSS.

  1. Happy Pi Day!

    One half plus one third plus one fifth is already larger than one. So proved.

    Uncle Scott

    March 14, 2008 at 5:33 pm

  2. Show off.

    I guess they teach you that fancy stuff in the School of Foreign Service, eh?

    I should have said that I had no idea how to explain that it was not only bigger than one, but it was bigger than any other number he could think of. Careless. I edited it. He already had me start adding the fractions by hand while we were waiting for his last karate class. I told him I had to stop at 13. It’s like the fraction excercise from hell.

    What is Pi day?

    Rolfe Schmidt

    March 15, 2008 at 7:22 am

  3. That is a great explanation and I’m going to bookmark it or perhaps even print it out.

    Rolfe, my greatest problem with self-education is that I can’t stick with any one topic long enough to learn the technical details of what it takes to get it right. This is very true in math where it may take months of study to figure something out. About two years ago I really became fascinated with why PI is transcendental and my husband told me that if I worked my way through an Abstract Algebra book that I’d have my answer. I took him at his word, but as it turns out I can’t pick up on the concepts as quick as a math major can and so I’m going to have to stop and learn set theory and logic first. That is a whole lot of delay of gratification just to get to the answer to one question! Maybe I will do it though.

    Myrtle

    March 17, 2008 at 3:55 pm

  4. Thanks Myrtle, I’m glad you enjoyed it. I thoroughly enjoy reading your blog, so the complement means even more.

    I understand the problem you have with self-education, and I imagine a lot of people have it. I certainly do. I find that even though I rarely end up answering the questions that get me started, I learn a surprising amount of stuff on the way. Eventually the technical details accumulate. Let the Math majors be fast, I want to take my time and enjoy.

    Why is PI transcendental? That’s a good question — you’ll have to dig deep into your algebra book for that. I know I don’t have a quick answer, although I’d like to. And logic can be a lot of fun too. So hopefully you’ll get some gratification on the way!

    Rolfe Schmidt

    March 17, 2008 at 8:13 pm

  5. it’s worse than you think.
    you’ll probably only get to
    a proof that pi is *irrational*
    in a first course in abstract algebra …

    kibrolv

    March 25, 2008 at 8:48 am

  6. I just pulled out a couple of my Algebra books, and noticed that Hungerford punts on the question, he just says “See Herstein”.

    Herstein gives a nice, if sort of magical, proof that e is transcendental. It doesn’t really require the infrastructure of Algebra, just a bit of Calculus and some patience with special polynomials. He doesn’t prove the result for \pi, he says it is hard and refers you to:

    Niven’s A Simple Proof the \pi is Irrational to see why it is irrational, and
    Transcendental Numbers by C.L. Siegel and Irrational Numbers by I.Niven

    Now I’m curious.

    By the way, thanks for the plug, V. I like the manifold pun.

    Rolfe Schmidt

    March 25, 2008 at 9:51 am

  7. [...]  A primer on the zeta function: you know this person knows how to break something down and present it in a clear way. It builds up, from smaller simple examples to build intuition, to a grand finish. [...]

    And the blogosphere keeps marching on… « Continuous Everywhere but Differentiable Nowhere

    March 27, 2008 at 6:01 pm

  8. I got interested with studying the zeta function when I came across the strange result of getting sums for divergent series. For example 1+1+1+1+… = -1/2 or 1+2+3+4+…= -1/12.

    I’m still clueless what it means exactly but hopefully not for long. Things should be clear once I get to understand your explanation.

    supermario

    May 12, 2008 at 7:04 am

  9. supermario- Those are interesting sums, but you won’t find the explanation in this post. I only have a couple of minutes online right now. When I get a chance I give you a link to some good explanations…

    Rolfe Schmidt

    May 19, 2008 at 12:30 am


Leave a Reply