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<j}\left\lfloor\frac{n}{p_ip_j}\right\rfloor-\sum_{i<j<k}\left\lfloor\frac{n}{p_ip_jp_k}\right\rfloor+\cdots\\&< n\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_k}\right)+2^{k-1}.\end{aligned}

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)<k+2^{k-1}.

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


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


(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.)

Leave a comment

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:

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

\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),

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.

Leave a comment

Filed under Complex Analysis