Prime number theorem

The prime number theorem states that the prime counting function $\pi(x)$ is asymptotically equivalent to $\frac{x}{\log x}$. At some point it might be interesting to delve further into the proof of this fact, but in this post I just wanted to bring about the connection to zeroes of the Riemann zeta function.

To do this, consider the function $\psi(x)=\sum_{p^r<x} \log p,$ originally defined by Chebyshev. It is not that difficult to show that the prime number theorem is equivalent to $\psi(x)\sim x$. It is more difficult to show the following amazing formula of Von Mangoldt

$$\psi(x)=x-\log(2\pi)-\frac{1}{2}\log(1-x^{-2})-\sum_{\zeta(\rho)=0}\frac{x^\rho}{\rho},$$

where the sum is over non-trivial zeroes of the Riemann zeta function. My mind boggles at the beauty and simplicity of this formula!

Now if every zero $\rho =a +ib$ has real part $a<1$, we can see that $|x^\rho|=|x|^a$, so dividing both sides of the Von Mangoldt formula by $x$, each summand of the series approaches $0$ and with a bit more effort one can show that the whole series approaches $0$. Thus PNT follows simply from showing that there are no zeroes of the form $1+ib$.

One reason I find this formula so beautiful is that by plugging in the mysterious zeroes of $\zeta$ one gets closer and closer approximations to $\psi(x).$ See this page for more on that as well as a neat animation.

Chebyshev prime number estimates

 In my previous post, I promised that I would show how to prove that the prime counting function $\pi(n)$ is sandwiched in between two functions of the form $c_1\frac{n}{\log n}$ and $c_2\frac{n}{\log n}$ for some constants $c_1$ and $c_2$. Chebyshev was a pioneer in this area and after a lot of hard work was able to determine in an 1854 paper that this inequality is true for large $n$ and with

$$c_1=0.922\ldots\text{ and }c_2=1.105\ldots.$$

The Prime Number theorem says we should be able to get these constants arbitrarily close to $1$.

Following Lemmermeyer's exposition, we will content ourselves with getting some much cruder estimates, but for far less work! We will show you can take 

$$c_1=\frac{\log 2}{2}\approx 0.347\text{ and }c_2=6\log 2\approx 4.159$$

These are poor estimates but you can get them for some surprisingly little work.

As before the number $N=\binom{2n}{n}$ will play a critical role in the proofs. Let $\nu_p$ be the exponent of $p$ in $N$. In the second proposition of the previous post we showed

$$p^{\nu_p}\leq 2n,$$

which implies $$\nu_p\leq \lfloor\frac{\log 2n}{\log p}\rfloor.$$

Also recall the estimate $\binom{2n}{n}\geq \frac{2^{2n}}{2n}$. Taking logs, we have

$$2n\log 2-\log 2n \leq \log\binom{2n}{n}=\log\left(\prod p^{\nu_p}\right)$$

$$\leq \sum_{p\leq 2n} \left\lfloor\frac{\log 2n}{\log p}\right\rfloor \log p $$

$$\leq \sum_{p\leq 2n} \log 2n=\pi(2n)\log 2n$$

Putting these all together, we get

$$2n\log 2-\log 2n\leq \pi(2n)\log 2n,$$

and rearranging

$$\pi(2n)\geq \log 2\frac{2n}{\log 2n}-1$$

It is not difficult to see that $\log 2\frac{2n}{\log 2n}-1>\frac{\log 2}{2}\frac{2n}{\log 2n}$. This shows $\pi(2n)<\frac{\log 2}{2}\frac{2n}{\log 2n}$. In fact, for general $x$, we need a slightly stronger inequality. Assume $2n\leq x<2n+2$. Then

$$\pi(x)\geq\pi(2n)\geq \log 2\frac{2n}{\log 2n}-1$$

and in order to complete the argument showing $c_1=\frac{\log 2}{2}$, we need to show that

$$\log 2\frac{2n}{\log 2n}-1\geq \frac{(n+1)\log 2}{\log (2n+2)},$$ since this is clearly $\geq \frac{\log 2}{2}\frac{x}{\log x}$.

Lemma: $\log 2\frac{2n}{\log 2n}-1\geq \frac{(n+1)\log 2}{\log (2n+2)}$

Proof:

It suffices to show $\log 2\frac{2n}{\log (2n+2)}-1\geq \frac{(n+1)\log 2}{\log (2n+2)}$. Multiplying both sides by $\log(2n+2)$ we get the following equivalent inequalities:

$$(\log 2)(2n)-\log(2n+2)\geq (n+1)\log 2$$

$$(\log 2)(n-1)\geq \log 2+\log(n+1)$$

$$n\log 2\geq \log(n+1)$$

$$\log 2^n\geq \log (n+1)$$

which is satisfied for all $n\geq 1$. $\Box$

So we have shown $c_1=\frac{\log 2}{2}$. Let us return to the lower bound, which we talked about in the last post. We were zeroing in on Bertrand's Postulate, so the resulting estimate was not the greatest. 

Consider $\prod_{n<p \leq 2n}p.$ This is less than $4^n$ (which follows from the last post.) If we replace each $p$ in this expression with $n$, we get the inequality $n^{\pi(2n)-\pi(n)}\leq\prod_{n<p \leq 2n}p$. So we can conclude

$$n^{\pi(2n)-\pi(n)}<4^n$$

$$\pi(2n)-\pi(n)<\frac{n\log 4}{\log n}$$

Lemma: $\pi(2^k)\leq \frac{3}{k}2^k$.

Proof:

Check it directly for $k\leq 5.$ Now

$$\pi(2^{k+1})-\pi(2^k)<\frac{2^k\log 4}{\log 2^k}=\frac{2^{k+1}}{k},$$

so inductively $$\pi(2^{k+1})=\pi(2^k)+\frac{2^{k+1}}{k}\leq \frac{3}{k}2^k+\frac{2^{k+1}}{k}=\frac{5\cdot 2^k}{k}.$$ It is a simple exercise to show that $\frac{5\cdot 2^k}{k}\leq \frac{3}{k+1}2^{k+1}$, for $k\geq 5$, which will complete the proof. $\Box$.

Now suppose $2^k<x\leq 2^{k+1}$. Then we have

$$\pi(x)\leq \pi(2^{k+1})\leq \frac{6\cdot 2^k}{k+1}\leq \frac{6\cdot 2^k}{k}=6\log 2\frac{2^k}{\log 2^k}\leq 6\log 2\frac{x}{\log x}.$$ So we can take $c_2=6\log 2$.

Bertrand's Postulate

 I have always been fascinated by Bertrand's Postulate, the claim that there is always a prime number between $n$ and $2n$. When I first heard about it as an undergraduate, I tried proving it for myself but was not able to. I'd like to present here what appears to be a now standard proof of the fact due to Erdös. I am basing my exposition on two articles, one by Aigner and Ziegler from the book "Proofs from the book" as well as a PDF found on Franz Lemmermeyer's webpage.  Lemmermeyer has a short section on Bertrand's Postulate which appears to be largely based on the the Aigner-Ziegler article, but he also has a nice exposition on getting some Prime Number Theorem type estimates, which I want to talk about in my next post.

Let $\Theta(x)$ be the product of all primes less than or equal to $x$. More generally, let $\Theta(x,y)$ be the product of all primes in the interval $[x,y]$.

Here's a neat fact:

Proposition: $\Theta(x)\leq 4^{x-1}$ if $x\geq 2$.

Proof: 

Suppose we know the proposition inductively for all values less than $k$. If $k$ is even, then $\Theta(k)=\Theta(k-1)$, so $\Theta(k)<4^{k-1}<4^k$. If $k=2m+1$ is odd, consider the integer $\binom{2m+1}{m}$. By the Binomial theorem, $\binom{2m+1}{m}<2^{2m+1},$ but in fact, because there are two equal terms $\binom{2m+1}{m}=\binom{2m}{m}$, we get the better inequality  

$$\binom{2m+1}{m}<2^{2m}=4^m.$$

Moreover, we claim that $\Theta(m+2,2m+1)$ divides  $\binom{2m+1}{m}$. To see this, notice that $\binom{2m+1}{m}$ can be written as $\frac{(2m+1)(2m)\cdots(m+2)}{m!}.$ Therefore, all of the primes in the range $[m+2,2m+1]$ are factors of the numerator, and they are all larger primes than can be contained in the denominator.

Now $$\Theta(2m+1)=\Theta(m+1)\Theta(m+2,2m+1)$$

$$\leq\Theta(m+1)\binom{2m+1}{m}$$

$$<4^m\cdot 4^m=4^{2m}.$$

This completes the inductive step. $\Box$

In that argument, we used the upper bound $\binom{2m+1}{m}<4^m$. To proceed, we'll want a lower bound on $\binom{2n}{n}$. Consider the set of binomial coefficients $\{\binom{2n}{0},\binom{2n}{1},\ldots\binom{2n}{2n}\}.$ The average value is the sum $2^{2n}$ divided by $2n+1$. Since the middle term is the largest, we get the inequality $\binom{2n}{n}>\frac{2^{2n}}{2n+1}$. In fact, we can improve this to $$\binom{2n}{n}>\frac{2^{2n}}{2n},$$ by considering the set $\{\binom{2n}{0}+\binom{2n}{2n},\binom{2n}{1},\binom{2n}{2},\cdots,\binom{2n}{2n-1}\}$ instead.

Next, we'll look at what we can say about primes appearing in $N=\binom{2n}{n}.$ It is quite easy to check that no prime in the range $(2/3n,n]$ is a divisor of $N$. Think of $n=\frac{(2n)(2n-1)\cdots(n+1)}{n!}$, and notice that $p$ appears once in the denominator, $2p$ appears once in the numerator, while $3p$ is already out of range. A less obvious pair of facts is the following:

Proposition:  

(a) If a prime $p$ satisfies $p>\sqrt{2n}$, then it appears at most once in $\binom{2n}{n}$.

(b) The exponent of $p$ in $\binom{2n}{n}$ is less than or equal to $2n$.

Proof:

The proof  of both these facts uses the Legendre formula that $n!$ contains the prime factor $p$ exactly $\sum_{k\geq 1}\lfloor \frac{n}{p^k}\rfloor$ times. (Incidentally, the Beast Academy 5th Grade Series from AoPS proves this quite nicely, though not using all of the fancy language.)

So the exponent of $p$ in $N$ is given by $$\sum_{k\geq 1}(\lfloor \frac{2n}{p^k}\rfloor-2\lfloor\frac{n}{p^k}\rfloor).$$

It is a simple exercise to check that $\lfloor 2x\rfloor- 2\lfloor x\rfloor\in\{0,1\}$, so each summand is at most $1$. Moreover the summands vanish as soon as $p^k>2n$, so we can say that the exponent of $p$ in $N$ is at most $\operatorname{max}\{k:p^k\leq 2n\}$. This immediately implies statement (b) of the proposition.

To prove (a), notice that if $p>\sqrt{2n}$, the largest power of $p$ less than $2n$ is $1$, so its exponent in $N$ will be at most $1$. $\Box$

Let $\nu_p$ be the exponent of $p$ in $N$. Write

$$N=\prod_{p\leq \sqrt{2n}}p^{\nu_p} \cdot\prod_{\sqrt{2n}<p<\frac{2}{3}n}p^{\nu_p}\cdot\prod_{n<p\leq 2n}p.$$

Notice that we removed the range $[\frac{2}{3}n,n]$ since there are no prime factors of $N$ here. In a similar way to how we argued previously for $\binom{2m+1}{m}$, every prime from $n$ to $2n$ definitely appears with exponent $1$. We can also note that the exponents on the middle term must be either $0$ or $1$. Now we know that $p^{\nu_p}<2n$ from the (b) statement in the above proposition. So we have $$N\leq (2n)^{\sqrt{2n}}\cdot (4^{\frac{2}{3}n})\cdot (2n)^{P(n)},$$

where $P(n)$ denotes the number of primes between $n$ and $2n$. Recall that we are trying to show $P(n)>0$ in order to establish Bertrand's Postulate. On the other hand $N>\frac{4^n}{2n}$, so we get the following inequality:

$$4^{\frac{n}{3}}<(2n)^{\sqrt{2n}+1+P(n)},$$

and taking logarithms, we have

$$P(n)>\frac{2n}{3\log_2(2n)}-(\sqrt{2n}+1).$$

Now we are basically done. The term $\frac{2n}{3\log_2(2n)}$ is going to dominate $\sqrt{2n}+1$ in the long run, and in fact one can check that the right hand side is positive after $n=468$. One can then just verify by hand or computer that $P(n)>0$ for $n<468$. In fact one just needs to find a sequence of primes where each is smaller than twice the previous until you exceed 468. 

It is interesting to notice that this argument establishes a lot more than Bertrand's Postulate. Not only does it show $P(n)>0$, but it give a pretty substantial lower bound of $\frac{2n}{3\log_2(2n)}-(\sqrt{2n}+1)$.

If we let $\pi(n)$ denote the number of primes $\leq n$, clearly $P(n)<\pi(2n)$, so we also get a lower bound on the number of primes.

$$\pi(2n)\geq \frac{2n}{3\log_2(2n)}-(\sqrt{2n}+1).$$

In fact, using the inequality $\sqrt{2n}-1\geq \frac{21}{4}\log_2(2n)$ for $n\geq 2^{11}$, we get

$$\pi(2n)>P(n)>\frac{1}{7}\frac{2n}{\log_2(2n)}.$$

The Prime Number Theorem says that $\pi(n)$ is asymptotically the same as $\frac{n}{\log n}$, so this estimate is in the same ballpark. 

As a step toward the prime number theorem Chebyshev proved that $c_1 \frac{n}{\log n}\leq \pi(n)\leq c_2 \frac{n}{\log n}$ for some positive constants $c_1$ and $c_2$. Our estimate for $P(n)$ gives $c_1=\frac{\ln 2}{7}$. In our next post we will improve $c_1$ and find a $c_2$ that works, following Lemmermeyer's exposition.

A fun argument due to Erdös

 I wanted to share a fun argument that I read in the book Gamma, Exploring Euler's Constant by Julian Havil. Whenever I start reading through proofs of the prime number theorem, this sort of thing crops up and I always find it hard to get my mind to grok it. I understand it line by line, but have difficulty really feeling the essence.

Theorem: The number of primes less than or equal to $n$ is at least $\frac{1}{2}\log_2n.$

The proof is as follows. Let $p_1,p_2,\ldots,p_k$ be the primes less than or equal to $n$. Then any natural number less than or equal to $n$ can be uniquely written as $$p_1^{\epsilon_1}\cdots p_k^{\epsilon_k}\cdot m^2,$$ where the exponents $\epsilon_i\in\{0,1\}$ and $m$ is an integer. In other words, we have decomposed the number into a square free part times a square, and all the exponents of the primes in the square free part will be either $0$ or $1$. Obviously $m^2\leq n$, so $m\leq\sqrt{n}$.

So in order to construct any integer less than or equal to $n$ you must make $k$ binary choices on the exponents of the squarefree part as well as pick an integer $m\leq\sqrt{n}$. Not all such choices will make an integer less than or equal to $n$, but you will definitely construct every integer less than or equal to $n$ in this way! So $$n\leq\sqrt{n}\cdot 2^k.$$ Dividing both sides by $\sqrt{n}$ and taking the base $2$ logarithm, we get the desired result. $\Box$

Well, I am happy I wrote that down, and I have to say I understand the argument a lot better now! I think one of the things that made it a bit hard to grasp at first is that the inequalities are not just about numbers but about numbers of numbers. It is a really nice argument now that I understand it.

Actually, I got to thinking about how this argument fits into a set of "nearby" arguments.  The most straightforward variation is to see what happens when you dispense with the square free factorization. Every number $\leq n$ can be written as $$p_1^{r_1}\cdots p_k^{r_k},$$ but how do we bound the exponents. One try would be to note that the largest any exponent can get is when the base is $2$, where it cannot exceed $\log_2 n$. So, with a very crude estimate, each exponent can be chosen in $\leq \log_2n$ ways, leading to the the inequality $$n\leq (\log_2n)^k.$$ Taking natural logs, we derive 

$$k\geq \frac{\ln n }{\ln(\log_2 n)}. $$

I am kind of surprised this gives as much information as it does. I had expected to get an inequality with no content like $2n>n$! This crude inequality still approaches infinity as $n$ grows, implying the infinitude of primes. When $n=100,000$, we get $k\geq 4.097$ which is a fairly modest statement. On the other hand the original estimate of $1/2 \log_2n$ gives $k\geq 8.304,$ which is not much better. However, one can see that the ratio of the Erdös estimate to the crude estimate goes to infinity, so the Erdös estimate is a substantial improvement.

Another way one could vary the argument is to look at the cube free factorization instead. In that case the exponents all have three choices and there is a factor $m^3$. So we get $$n\leq 3^k\cdot \sqrt[3]{n},$$ leading to the inequality $$k\geq\frac{2}{3}\log_3 n.$$ When $n=100,000$ we get $k\geq 6.986,$ which is again not bad compared to the original, though still worse.  In fact the cubic estimate is always $\frac{4\log2}{3\log 3}\approx 0.84$ times the original estimate. So the original estimate is "only" an improvement of the multiplicative constant.