Tag Archives: Riemann

The Prime Bet

Let's say you sit in a pub, minding your own business, when all of a sudden a stranger walks up to you and offers you a bet:

We'll choose two positive integers at random. If they have any divisor in common (other than 1) I'll pay you a dollar, else you'll pay me a dollar. Are you in?

Apart from the question what kind of establishments you frequent, you should be wondering: is this a good bet for you?

When two integers have no divisors in common except the trivial divisor 1 we say they are coprime or relatively prime. 6 and 9 have the common divisor 3, so they are not coprime, whilst 8 and 9 only have the trivial common divisor 1, so they are coprime.

This makes you start thinking: "As numbers grow bigger, aren't there a lot of divisors out there? After all, half the numbers are even, so if we hit two even numbers, they'll have the factor 2 in common and I'll win. And then there's 3, 5, 7, ... Seems like a good deal!" Continue reading The Prime Bet

If One at a Time is too Difficult, Try All at Once!

In the past months, I spent as much time as I had on taking online courses at Coursera. One particularly interesting course, both from a mathematical and computational point of view, is Analytic Combinatorics which applies combinatorics (i.e., the art of counting) to the analysis of algorithms by finding formulae, exact or asymptotic, for their running time.

It is notoriously difficult to find exact formulae for general combinatorial constructs. Typically, we want to know how many objects, e.g., trees, permutations, sequences, with certain properties there are of a given size. Famously, the number of binary trees (and about a million other constructions) is governed by the Catalan numbers

C_n = \frac{1}{n+1}{2n\choose n}.

Continue reading If One at a Time is too Difficult, Try All at Once!

Applying the Explicit Formula

It's quite some time since we arrived at Riemann's main result, the explicit formula

J(x)=\mathrm{Li}(x)-\sum_{\Im\varrho>0}\left(\mathrm{Li}(x^\varrho)+\mathrm{Li}(x^{1-\varrho})\right)+\int_x^\infty\frac{\mathrm{d}t}{t(t^2-1)\log t}-\log2,

where J(x) is the prime power counting function introduced even earlier. It's high time we applied this!

First, let's take a look at J(x) when calculating it exactly:

J(x) Continue reading Applying the Explicit Formula

Integral Madness

We've seen the calculus version

J(x)=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}\log\zeta(s)x^s\frac{\mathrm{d}s}{s},

of the Euler product, and we know how to express \xi(s) as a product over its roots

\xi(s)=\xi(0)\prod_\varrho\left(1-\frac{s}{\varrho}\right),

where

\begin{align}\xi(s)&=\frac{1}{2}\pi^{-s/2}s(s-1)\Pi(s/2-1)\zeta(s)\nonumber\\&=\pi^{-s/2}(s-1)\Pi(s/2)\zeta(s).\nonumber\end{align}

High time we put everything together -- the reward will be the long expected explicit formula for counting primes! Continue reading Integral Madness

In the Beginning, There Was... Euler's Formula!

I will start this blog the way Bernhard Riemann started his paper: with Euler's product formula that John Derbyshire called the golden key:

\zeta(s)=\sum_{n\ge1}n^{-s}=\prod_{p}(1-p^{-s})^{-1}

This holds for any complex number s with \Re s > 1. If you look up a proof in any modern textbook, you will find a number technical rearrangements that end up in an examination of the absolute convergence on both sides. But actually, the formula is nothing but a fancy way of writing out the Sieve of Eratosthenes. Let's start by writing out the sum on the left hand side: Continue reading In the Beginning, There Was... Euler's Formula!