## Sunday, November 25, 2012

### Discovery Cafe Day 3: A Prime Day

Here is a quick account of what happened in our third Cafe meeting on Nov. 20th.  As I was walking down the hall to go to our weekly meeting, I got the idea of expanding a bit on a theme that was touched on last week. As we saw in the last post, Euclid had proved in 300 BC that there are infinitely many  prime numbers (I think his actual statement  is that there is no biggest prime number). His method of proof was  proof by  contradiction as students saw last week.

Now this result opened the doors to  so many questions about the statistics of primes, many  of which are  still unanswered! I tried to expand on this  theme of how many primes are out there.

After nearly 2000 years Euler took the next giant step in this question. Around  1737 he not only gave a different proof of Euclid's theorem, but  he went  way beyond  that  and showed that the  set of primes is not too thin and in a sense there are many primes! See below for more about this.  One of his  statements  is so intriguing when  he writes
$$\sum \frac{1}{p} =\log \log \infty$$
What he meant by this? Not so clear, but on a heuristic level one can argue that this hints at the famous prime number theorem which was precisely conjectured many years later and proved even many more years later down the road in 1890's. But we are  of course not yet ready to discuss all this.

To prepare for all this  we decided to discuss and prove a simpler    well formulated statement.  More precisely  we settled to prove another statement of Euler's    that
$$\sum \frac{1}{p} =\infty,$$
where the sum is over all primes of course. This statement not only shows that there are infinitely many  primes, it shows that in a sense the set of primes cannot be  thin! Taking a clue from the fact that the harmonic series
$$\sum \frac{1}{n} =\infty$$ is divergent, let us call  a subset $$S$$ of integers fat if $$\sum_{n\in S} \frac{1}{n} =\infty$$ and thin if  $$\sum_{n\in S} \frac{1}{n} < \infty.$$ For example the set  of perfect squares is thin since we know that $$\sum \frac{1}{n^2} <\infty.$$ So we set out to show that the set of all primes is a `fat'  subset of the set of natural numbers. Students noticed  that this is already a huge improvement over Euclid's theorem.

Euler's  main tool  in these types of questions related to primes  was an amazing formula that he found,    now called the Euler Product Formula:
$$\sum_n \frac{1}{n^s}= \prod_p (1-\frac{1}{p^s})^{-1}, \quad s>1.$$
(The sum is over all natural numbers and the product is over all primes). We spent some time proving this. To do this we
1. Carefully defined  infinite products,
2. Showed that in an infinite product
$$\prod_n(1+a_n)$$
if  $$\sum_n |a_n|$$ is convergent then the product is convergent and in that case the product is zero iff one of its terms is zero.
3. Used unique factorization of integers into primes to prove the identity.
4. Take limits  as $$s \to 1$$ and use the fact that the harmonic series is divergent, to derive the divergence of the inverse primes series $$\sum \frac{1}{p}$$,  and  hence the fact that the set of primes is not thin.