# Tag Archives: riemann zeta function

## A Bound on the Prime Counting Function

The idea for this post arose from this quora answer.

Let $\pi(n)$ denote the number of primes up to $n$. It is well-known that

$\displaystyle\pi(n)\sim\frac{n}{\log n}$,

which is the celebrated prime number theorem. Although “elementary” proofs exist, most proofs of the prime number theorem are technical. Nevertheless, we can obtain some simple bounds as follows.

Let $p_1,\ldots,p_k$ denote fixed prime numbers $\leq n$. By the inclusion-exclusion principle, the number of positive integers $\leq n$ not divisible by any of the $p_i$ is

\displaystyle\begin{aligned}&n-\sum_{i}\left\lfloor\frac{n}{p_i}\right\rfloor+\sum_{i

Therefore, we have the following (rather weak) bound for the prime-counting function $\pi(n)$:

$\boxed{\displaystyle \pi(n)< n\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_k}\right) + k + 2^{k-1}}$.

This implies the following result.

Theorem. $\displaystyle\lim_{n\to\infty}\frac{\pi(n)}{n}=0$.

For example, let’s say we want to find all $n$ such that at least 20% of the natural numbers below $n$ are prime. Then

$\displaystyle\pi(n)\geq\frac n5$.

If $p_1,\ldots,p_k$ are the prime numbers $\leq n$, then this means that

$\displaystyle n\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_k}\right) + k + 2^{k-1}>\frac n5$
$\displaystyle\iff n\left(\frac 15-\frac{\phi(p_k!)}{p_k!}\right).

The left-hand side is positive for $k=6$, for which the inequality has the solution $n<6041035/1657\approx 4638.78$. Trying the values in this range we obtain the following set of solutions

$n\in[2,330]\cup[331,335]\cup[337,340]\cup[349,350]\cup[353,355]\cup[359,360]$.

In general, if we want to find all $n$ such that $\pi(n)\geq\varepsilon n$, then we start by finding the least $k$ such that the $k$-th prime $p_k$ satisfies

$\displaystyle\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_k}\right)=\frac{\phi(p_k!)}{p_k!}<\varepsilon$.

(Note that such a $k$ is guaranteed to exist since the left-hand side approaches $0$ as $k\to\infty$, since the harmonic series diverges.) Then we can bound $n$ using

$\displaystyle n<\frac{k+2^{k-1}}{\varepsilon-\frac{\phi(p_k!)}{p_k!}}$.

(Observe also that $\displaystyle\frac{\phi(n!)}{n!}<\frac{\phi((n-1)!)}{(n-1)!}\Leftrightarrow n$ is prime.)

Filed under Number Theory

## Trivial Zeros of the Riemann Zeta Function

The Riemann hypothesis is perhaps the most famous unsolved problem in mathematics. It says that all non-trivial zeros of the Riemann zeta function have real part $1/2$. What is the Riemann zeta function? A common misconception is that it is defined as

$\displaystyle\zeta (z)=\sum_{k=1}^\infty k^{-z}=\frac{1}{1^z}+\frac{1}{2^z}+\frac{1}{3^z}+\dots,\quad z\in\mathbb C$.

This is false! Because the series on the right only converges for $\Re(z)>1$. Also, it is a well-established fact that the trivial zeros of the Riemann zeta function occur at the negative even numbers $-2,-4,-6\dots$. If we substitute $z=-2$ in the above equation we get $1^2+2^2+3^2+\dots$ which is far from being zero. So even though these are called ‘trivial’ zeros, it seems highly non-trivial why these are actually zeros. What’s going on?

The problem lies in the above definition. This equation does NOT define the Riemann zeta function, which is a meromorphic function (see below) on the whole complex plane. The above definition only works for $\Re(z)>1$. Then what about the other values of $z$? Before proceeding further, let us familiarise ourselves with some terminology from the theory of complex analysis.

Complex analysis is one of the most beautiful branches of mathematics. It deals with functions $f:\mathbb C\to \mathbb C$ in the complex plane that are differentiable in some open subset $D\subseteq \mathbb C$. (Open sets are like open intervals; open intervals are line segments excluding the endpoints, open sets in the complex plane can be thought of as discs excluding their boundaries.) Some basic definitions are:

• $f:D\to\mathbb C$ is said to be analytic (or holomorphic) at $z_0$ if it is differentiable in a neighbourhood of $z_0$, i.e. at all points $z$ such that $|z-z_0|<\varepsilon$ for some $\varepsilon >0$.
• $f$ above is called entire if it is analytic at every $z\in\mathbb C$.
• Every analytic function has a Laurent series, which is like a Taylor series, but negative powers are allowed.
• If $\displaystyle f(z)=\sum_{k=-n}^\infty a_k(z-z_0)^k$ is a Laurent series in some neighbourhood of $z_0$ then $(z-z_0)^nf(z)$ is analytic, and $z_0$ is called a pole of $f$ of order $n$. The coefficient $a_{-1}$ of $(z-z_0)^{-1}$ is the residue of $f$ at $z_0$, which we shall denote as $\text{res}(f,z_0)$.
• If $f:D\to\mathbb C$ is analytic except for a set of isolated poles, it is called meromorphic.

Unlike real analysis, amazing things happen when analysis is done in the complex plane. Some important results in complex analysis are:

• Cauchy’s integral theorem, that says if $f$ is analytic on some open set $D\subseteq\mathbb C$ and $\gamma$ is any closed curve in $D$, then

$\displaystyle\int_\gamma f(z)dz=0$.

• Cauchy’s integral formula: If $\gamma$ above is a circle oriented counter-clockwise and $w$ is any interior point, then

$\displaystyle f(w)=\frac{1}{2\pi i}\int_\gamma \frac{f(z)}{z-w}dz$.

• Cauchy’s residue theorem: If $A$ is the set of poles of $f$ inside the closed curve $\gamma$ and $f$ is analytic inside $\gamma$ except for these poles, then

$\displaystyle \int_\gamma f(z)dz=2\pi i\sum_{a\in A}\text{res}(f,a)$,

• Liouville’s theorem: Any entire function that is bounded must be constant.
• Identity theorem: If $D'\subseteq D\subseteq\mathbb C$ are (connected) open sets with $f,g$ analytic on $D$, such that $f=g$ on $D'$, then $f=g$ on $D$.

The identity theorem gives a useful method of extending a function analytically. Suppose $D'\subseteq D\subseteq\mathbb C$ are open sets and $f:D'\to\mathbb C$ and $g:D\to\mathbb C$ are analytic. If $f=g$ on $D'$, and we were to define $f$ on $D$ preserving analyticity, then the identity theorem says $f=g$ on $D$. $g$ in this case is called the (unique) analytic continuation of $f$ to $D$. Now let’s go back to the Riemann zeta function. It’s proper definition is the following:

$\zeta(z)=\begin{cases}&\displaystyle\sum_{k=1}^\infty k^{-z},\;\Re(z)>1,\\ &\text{analytic continuation elsewhere.}\end{cases}$

Recall the gamma function

$\displaystyle\Gamma(z)=\int_0^\infty t^{z-1}e^{-t}dt,\; \Re(z)>0$.

It can be shown using integration by parts that $\Gamma(z+1)=z\Gamma(z)$. The function $\Gamma(z+1)$ is analytic for $\Re(z)>-1$, so this equation provides the analytic continuation of $\Gamma(z)$ to $\Re(z)>-1$. By repeating this procedure we obtain the analytic continuation of $\Gamma$ to the whole complex plane (except for the non-positive integers, which are in fact the poles of $\Gamma$).

It is an exercise to show that

$\displaystyle \zeta(z)=\frac{1}{\Gamma(z)}\int_0^\infty\frac{t^{z-1}}{e^t-1} dt,\; \Re(z)>1$.

It is another exercise to show that

$\displaystyle \frac{1}{\Gamma(z)}\int_0^\infty\frac{t^{z-1}}{e^t-1} dt=\frac{\Gamma(1-z)}{2\pi i}\int_{\gamma}\frac{t^{z-1}}{e^{-t}-1}dt$

where $\gamma$ is the Hankel contour:

Now the right side of the above equation is analytic for $\Re(z)<1$. Hence this equation provides the analytic continuation of $\zeta(z)$ to $\mathbb C\backslash\{1\}$ (in fact, there is a pole at $z=1$.)

The Bernoulli numbers $B_n$ are defined by the equation

$\displaystyle \frac{1}{e^t-1}=\sum_{m=0}^\infty B_m\frac{t^{m-1}}{m!}$,

and $B_0=1, B_1=1/2, B_{2m+1}=0$ for $m=1,2,\dots$. Substituting this into the equation above, setting $z=-n$ and using $\Gamma(n+1)=n!$ we obtain

$\displaystyle \zeta(-n)=\frac{n!}{2\pi i}\int_{\gamma}\frac{t^{-n-1}}{e^{-t}-1}dt =\frac{n!}{2\pi i}\sum_{m=0}^\infty (-1)^{m-1}\frac{B_m}{m!}\int_\gamma t^{m-n-2}dt$

By Cauchy’s residue theorem,

$\displaystyle\int_\gamma t^{m-n-2} dt=\begin{cases} &2\pi i\;\text{ if }m=n+1\\ & 0 \; \text{ otherwise}.\end{cases}$

Thus $\displaystyle\zeta(-n)=(-1)^n\frac{B_{n+1}}{n+1}$, which is zero if $n>1$ is even.