conjuring primes out of the riemann zeta function

September 02, 2017

Maybe you’ve heard of the Riemann zeta function before: it’s defined as

\[\zeta(s) = \sum_{n=1}^\infty \frac{1}{n^s} = \sum_{n=1}^\infty n^{-s}.\]

This function has deep connections in number theory, and it’s at the heart of the Riemann zeta hypothesis, one of the Millenium Prize Problems¹. Back in the 18th century (which was quite a bit before Riemann’s time), good old Leonhard Euler proved a quite beautiful formula for it:

\[\zeta(s) = \prod_p \frac{1}{1 - p^{-s}} \quad (s > 1),\]

where \(\prod_p\) iterates over all prime numbers \(p\). At least for me, appreciating this beauty took some time working through the proof, but I hope I can accelerate this process for you!

1. We won’t go into these deeper connections here: as it’s written, the definition doesn’t really make sense for \(s \leq 1\) (since the series doesn’t converge), so it’s so-called analytic continuation in the complex plane is used. We don’t need to worry about that for what I wanna show here though (also, I don’t really understand it). If you’re interested, you should check out 3Blue1Brown’s excellent video about this, if you haven’t seen it already. ↩

---

proving terrible lower bounds for the prime-counting function

August 31, 2017

Even if you don’t know it by its name, you’re probably familiar with Euclid’s theorem (and you’ve maybe heard its proof too at some point):

There are infinitely many prime numbers.

Now, less people are familiar with the remarkable prime number theorem:

Let \(\pi(N)\) be the number of primes \(p\) with \(p \leq N\). Then \(\pi(N)\) approaches \(\frac{N}{\log{N}}\) as \(N \rightarrow \infty\)¹².

This tells us a lot more about how many primes there are: not only are there infinitely many primes, they are actually not too rare.³ While this is significantly harder to prove (it took until 1896), we can however get some (much worse) lower bounds for the number of primes up to \(N\) (in other words: upper bounds on the \(n\)th prime) without too much hassle.⁴

1. Unless indicated otherwise, all \(\log\)s are always natural logarithms. ↩

2. This is also often written as \(\pi(N) \sim \frac{N}{\log{N}}\). ↩

3. There is a much better approximation of the number of primes up til \(N\): the so-called logrithmic integral \[\operatorname{Li}(x) = \int_2^x \frac{dt}{\log(t)}.\] As far as I understand and/or remember, assuming the Riemann hypothesis, it has been proven that the error of this approximation is as if the primes were distributed truly pseudorandomly! (I could be wrong though!) ↩

4. So what we’re basically doing is improving Euclid’s theorem over and over! ↩

---