In this week's edition of Monday Math we look at what I regard as one of the prettiest equations in number theory. Here it is:
\[
\sum_{n=1}^\infty \frac{1}{n^s} = \prod_p \left( \frac{1}{1-\frac{1}{p^s}}\right)
\]
Doesn't it just make your heart go pitter-pat?
You are probably familiar with the big sigma notation for sums. The big pi indicates an infinite product. In this case the product is indexed over the primes. In other words, the product contains one factor for each prime.
There is something very counter-intuitive in this equation, which is a large part of why I find it so pretty. It turns out, though, that it's really just a consequence of the fundamental theorem of arithmetic. Permit me to explain...
Remember FOIL? That was the acronym you learned back in Algebra I for how to multiply binomials. It stands for “First, Outer, Inner Last,” which makes sense when you ruminate on the equation:
\[
(a+b)(c+d)=ac+ad+bc+bd
\]
Pretty basic. There is another way to think about what you are doing here, however. What you are really doing is picking one letter out of each factor, and doing that in all possible ways. For example, if we were working with trinomials the product would look lilke this:
\[
\begin{align*}
(a+b+c)(d+e+f)= &ad+ae+af \\
&bd+be+bf \\
&cd+ce+cf
\end{align*}
\]
Now let's apply this principle to a more general problem. Suppose you were multiplying two infinite series like this:
\[
\left(1+\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+ \dots \right)
\left(1+\frac{1}{3}+\frac{1}{3^2}+\frac{1}{3^3}+\dots \right)
\]
Then our rule says that the product is found by selecting one term out of each of the two factors, and by doing this in all possible ways. That means that every term in the product will have the form
\[
\frac{1}{2^a 3^b}
\]
where we allow the possibility that either a or b could be zero. (That corresponds to selecting the one out of either or both of the two factors.)
As a result, our product will contain all fractions 1/n where n is a number having only twos and threes in its prime factorization. Moreover, each such number will appear exactly once, since prime factorizations are unique.
For example, notice that
\[
\frac{1}{72}=\left( \frac{1}{2^3} \right) \left( \frac{1}{3^2} \right)
\]
That is the only way to express 1/72 as a product of terms drawn from our factors.
Now suppose that we extended our product to include all of the primes:
\[
\left(1+\frac{1}{2} + \frac{1}{2^2}+\frac{1}{2^3}+\dots \right) \times
\left(1+\frac{1}{3}+\frac{1}{3^2}+\frac{1}{3^3}+\dots \right) \times
\]
\[
\left(1+\frac{1}{5}+\frac{1}{5^2}+\frac{1}{5^3}+\dots \right) \times
\left(1+\frac{1}{7}+\frac{1}{7^2}+\frac{1}{7^3}+\dots \right) \dots
\]
We now have an infinite product, each of whose factors is an infinite sum. To do this right we would now have to introduce the language of limits and convergence to make everything precise. However, we will not go wrong by asserting the following rule: In multiplying this out we choose one fraction out of each factor in all possible ways, with the proviso that we are required to choose the one out of all but finitely many of the factors.
With that rule in place, watch what hapens. Pick a number n. This number has a prime factorization, say
\[
n=p_1^{a_1}p_2^{a_2} \dots p_k^{a_k}.
\]
When we multiply things out we obtain
\[
\frac{1}{n}=\frac{1}{p_1^{a_1}} \times \frac{1}{p_2^{a_2}} \times \dots \times \frac{1}{p_k^{a_k}},
\]
and we now select the ones out of each of the other factors. That means that 1/n will appear in the product. Since prime factorizations are unique, we know that 1/n will appear exactly once.
We have therefore established the formula:
\[
\sum_{n=1}^\infty \frac{1}{n}=\prod_p \left( 1+\frac{1}{p}+\frac{1}{p^2}+\frac{1}{p^3}+\dots \right)
\]
Notice that the expression in the parentheses on the right is a geometric series, which means that every term after the first is obtained from the one before by multiplying by the same thing. You might recall that such series converge so long as the thing you multiply by is smaller than one in absolute value, and that we have the following formula:
\[
a+ar+ar^2+ar^3+\dots=\frac{a}{1-r}
\]
where a is the first term in our series and r is the thing you keep multiplying by. It follows that
\[
1+\frac{1}{p}+\frac{1}{p^2}+\frac{1}{p^3}+\dots=\frac{1}{1-\frac{1}{p}}
\]
and this gives us the formula we set out to prove, at least in the case s=1. The general case follows immediately.
We can define the function
\[
\zeta(s)=\sum_{n=1}^\infty \frac{1}{n^s}
\]
When s=1 this is just the harmonic series, which we know to diverge. This implies that our product must diverge as well. But that is only possible if there are infinitely many primes, meaning we now have one more proof of that amusing little fact.
In general, if s is larger than one (or is a complex number with real part greater than one) then the series will converge and we have a well-defined function. This is known as the Riemann zeta function, and it plays a big role in number theory. Our infinite product formula was first proved by Euler (pronounced like a former football team from Houston), hence the title of this post. Euler products come up in other contexts within number theory, but that is a different post.
Recall that our goal, laid out a few posts back is to prove that the sum of the reciprocals of the primes diverges. That is, we want to show that
\[
\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\dots=\infty
\]
I commented in an earlier post that this is hard to prove because it is difficult to work with a sum that is indexed over the primes. We have just taken a big step in the right direction, since we now at least have a product that is indexed over the primes. What we need now is some tool that transforms products into sums. Yes, if only we had such a thing.
- Log in to post comments
Recall that our goal, laid out a few posts back is to prove that the sum of the reciprocals of the primes converges.
You mean diverges, right? Don't mess with me now, I'm confused enough as it is.
Oops! I've corrected the error. Thanks for pointing it out.
I was struggling there for a while until I realised that what looked like an "8" was in fact an "s". :)
Very cool! These posts are threatening to make me like what I call "real math." I use math all the time (grad student in engineering), but never proofs and primes and crazy stuff like this.
OK, You need to write a book for us dunderhead math people (I'm a biology/geology major because I couldn't do the math).
This is clear, easy to follow. I'm still not sure what it all means, but I understood a bunch of mathtype for the first time ever.
I glazed over once, but recovered and read the whole thing. I'm impressed.
Thanks
cheglabratjoe and OgreMkV --
Thanks for the encouragement. I sometimes wonder if I am talking to myself with the math posts.
@ Jason: Please do keep the math posts. I enjoy the blog very much, and I think the math is a great addition.
Another vote for the math. While I have a degree in math, I don't really use it anymore. It's nice to see I can still follow along (and fill in the details you've, very smartly I suspect, chosen to gloss over). Apparently, disuse of those muscles doesn't kill them outright.
I normally just lurk, but I feel I should follow others and add another vote of encouragement. These math posts are great; please keep them coming.
thank you
I'm looking for thank you thank all persons who contributed all the issues existing in a place