Euler's Golden Bridge

Euler was the first to find a connection between the world of primes and the world of ordinary counting numbers. Many insights about the primes have been revealed by travelling over this `golden bridge'.

Let's recreate Euler's discovery for ourselves. 

Video: [youtube]

Slides: [pdf]

Reimann Zeta Function

We know the harmonic series $\sum1/n$ diverges. We also know the series $\sum1/n^{2}$ converges. 

It's natural to ask for which values of $s$ the more general series, known as the Riemann Zeta function $\zeta(s)$, converges.

$$\zeta(s)=\sum_{n=1}^{\infty}\frac{1}{n^{s}}=\frac{1}{1^{s}}+\frac{1}{2^{s}}+\frac{1}{3^{s}}+\frac{1}{4^{s}}+\ldots$$

Series like $\sum1/n^{3}$ and $\sum1/n^{4}$ converge because each term is smaller than the corresponding one in $\sum1/n^{2}$. Less obvious is when $s<2$.

A separate blog post presents a short proof that $\zeta(s)$ converges for $s>1$. 

Sieving The Zeta Function

Let's write out the zeta function again, noting that $1^{s}=1$.

$$\zeta(s)=1+\frac{1}{2^{s}}+\frac{1}{3^{s}}+\frac{1}{4^{s}}+\frac{1}{5^{s}}+\frac{1}{6^{s}}+\ldots$$

We can divide this series by $2^{s}$. 

$$\frac{1}{2^{s}}\zeta(s)=\frac{1}{2^{s}}+\frac{1}{4^{s}}+\frac{1}{6^{s}}+\frac{1}{8^{s}}+\frac{1}{10^{s}}+\frac{1}{12^{s}}\ldots$$

These denominators are multiples of $2^{s}$. By subtracting these terms from $\zeta(s)$, we sieve out terms with these multiples of $2^{s}$. 

$$(1-\frac{1}{2^{s}})\cdot\zeta(s)=1+\frac{1}{3^{s}}+\frac{1}{5^{s}}+\frac{1}{7^{s}}+\frac{1}{9^{s}}+\frac{1}{11^{s}}+\ldots$$

This dividing and subtracting of infinite series is only valid because they are absolutely convergent for $s>1$.

Let's now divide this series by $3^{s}$.

$$\frac{1}{3^{s}}\cdot(1-\frac{1}{2^{s}})\cdot\zeta(s)=\frac{1}{3^{s}}+\frac{1}{9^{s}}+\frac{1}{15^{s}}+\frac{1}{21^{s}}+\frac{1}{27^{s}}+\ldots$$

These denominators are all multiples of $3^{s}$, but not all multiples of $3^{s}$ are here. Some like $6^{s}$ and $12^{s}$ were removed in the previous step. Subtracting these from the previous series leaves terms with denominators that are not multiples of 2 or 3.

$$(1-\frac{1}{3^{s}})\cdot(1-\frac{1}{2^{s}})\cdot\zeta(s)=1+\frac{1}{5^{s}}+\frac{1}{7^{s}}+\frac{1}{11^{s}}+\frac{1}{13^{s}}+\ldots$$

We can't remove terms with multiples of $4^{s}$ because they were sieved out when we removed multiples of $2^{s}$. The next useful step is to remove multiples of $5^{s}$.

Repeating this process leaves terms with denominators that are not multiples of 2, 3 or 5.

$$(1-\frac{1}{5^{s}})\cdot(1-\frac{1}{3^{s}})\cdot(1-\frac{1}{2^{s}})\cdot\zeta(s)=1+\frac{1}{7^{s}}+\frac{1}{11^{s}}+\frac{1}{13^{s}}+\ldots$$

Again, we can't remove multiples of $6^{s}$ because they were already removed. If we repeat this several times, we'll see we can only remove multiples of successive primes. We'll also see that after each removal, the very first term 1 always survives. 

If we kept going, we'd end up with an infinite product on the left, and only 1 on the right.

$$\ldots\cdot(1-\frac{1}{11^{s}})\cdot(1-\frac{1}{7^{s}})(1-\frac{1}{5^{s}})\cdot(1-\frac{1}{3^{s}})\cdot(1-\frac{1}{2^{s}})\cdot\zeta(s)=1$$

We can rearrange this to isolate $\zeta(s)$. 

$$\zeta(s)=\prod_{p}(1-\frac{1}{p^{s}})^{-1}$$

The symbol $\prod$ means product, just like $\sum$ means sum.

Euler's Product Formula

We've arrived at Euler's product formula.

$$\boxed{\sum_{n}\frac{1}{n^{s}}=\prod_{p}(1-\frac{1}{p^{s}})^{-1}}$$

The product of $(1-\frac{1}{p^{s}})^{-1}$ over all primes $p$ is the sum of $\frac{1}{n^{s}}$ over all positive integers $n$, as long as we remember to keep $s>1$.

To say this result is amazing would not be an exaggeration. It reveals a deep connection between the primes and the ordinary counting numbers, a connection that doesn't appear too complicated at first sight.