1.6. Chebyshev's theta function

The first real progress towards the prime number theorem was achieved by Chebyshev in 1850. In a flash of inspiration, he saw that instead of simply counting primes, it might be easier to count them with ``weights". In other words, take a function $f$ and consider sums like $\sum_{p\in P[x]} f(p)$, where again $P[x]$ denotes the set of primes not greater than $x$. As we have seen, Abel summation can then be used to relate such quantities to $\pi (x)$ itself.

In particular, Chebyshev considered the function $\theta (x)$ defined in this way, with $f(x)$ chosen to be $\log x$:

$$\theta (x) = \sum_{p\in P[x]} \log p.$$

The idea is very roughly that the weight $\log p$ will compensate for the decreasing density of primes, which we conjecture to be (in some sense) $1/\log n$ around the integer $n$. So we expect the growth of $\theta (x)$ to be linear.

The notation $\theta (x)$ is now standard. Another way to describe it is: if $p_1,p_2, \ldots ,p_n$ are the primes not greater than $x$, then

$$\theta (x) = \log p_1 + \cdots + \log p_n = \log (p_1 p_2 \ldots p_n).$$

So by considering $\theta (x)$, we are effectively considering the quite natural quantity $p_1 p_2 \ldots p_n$. An obvious inequality is:

Proposition 1.6.1. For all $x > 0$, we have  $\theta (x) \leq \pi(x) \log x$.

Proof. With the above notation, $n = \pi (x)$ and $\log p_j \leq \log x$ for each $j \leq n$. $\Box$

The relationship is expressed more exactly by Abel's summation formula. Recall that $u_P(n)$ is 1 if $n$ is prime and 0 otherwise. By 1.3.6, we have

$$\theta (x) = \sum_{n \leq x} u_P(n) \log n = \pi (x)\log x - \int_2^x \frac{\pi (t)}{t} \; dt.$$

If $\pi (x)$ really is roughly $x/\log x$, then $\theta (x)$ will be roughly $x$ (the integral term will be roughly li$(x)$, hence small compared to $x$).

Conversely, we can express $\pi (x)$ in terms of $\theta (x)$. Clearly,  $\theta (x) = \sum_{n \leq x}b(n)$, where

$$b(n) = \left\{ \begin{array}{ll} \log n & \mbox{if $n$\ is prime} \\ 0 & \mbox{otherwise} \end{array}\right.$$

Since $b(n)/\log n$ is 1 for $n$ prime, we have

$$\pi (x) = \sum_{2 \leq n \leq x} \frac{b(n)}{\log n}.$$

Since $b(1) = 0$, version 1.3.7 of Abel's summation formula gives

$$\pi (x) = \frac{\theta (x)}{\log x} + \int_2^x \frac {\theta (t)}{t(\log t)^2}\; dt$$ (1)

for all $x \geq 2$. Using this expression, we now show more precisely how an estimation for $\theta (x)$ will lead to one for $\pi (x)$. This is one of the fundamental steps on our journey to the prime number theorem.

Theorem 1.6.2. Suppose that for some constants $c_0,\; C_0$ we have

$$c_0x \leq \theta (x) \leq C_0x$$

for all $x \geq 2$. Then

$$c_0 \; [\mbox{li}(x) + \alpha] \leq \pi (x) \leq C_0\; [\mbox{li}(x) + \alpha ]$$

for all $x \geq 2$, where $\alpha = 2/\log 2$. Further, suppose that for some constants c, C and some $x_0$, we have $cx \leq \theta (x) \leq Cx$  for all $x \geq x_0$. Let $\varep > 0$. Then there exists $x_1$ such that

$$(c - \varep )\mbox{li}(x) \leq \pi (x) \leq (C + \varep)\mbox{li}(x)$$

for all $x \geq x_1$.

Proof. Integration by parts, with 1 as one factor, gives

$$\mbox{li}(x) = \int_2^x \frac{1}{\log t}\; dt = \frac{x}{\log x} - \alpha + \int_2^x \frac{1}{(\log t)^2}\; dt.$$ (2)

The first statement now follows at once by comparing (1) and (2). For the second statement, take $x > x_0$. Then

$$\begin{eqnarray*} \pi (x)& = &\frac{\theta (x)}{\log x} + \int_2^{x_0} \frac {\t... ...} \; dt + K + \int_{x_0}^x \frac{\theta (t)}{t(\log t)^2}\; dt , \end{eqnarray*}$$

where

$$K = \int_2^{x_0} \left( \frac{\theta (t)}{t(\log t)^2} - \frac{C}{(\log t)^2} \right) \; dt.$$

Hence

$$\begin{eqnarray*} \pi (x) & \leq & \frac{Cx}{\log x} + C\int_2^x \frac{1}{(\log ... ...C(\mbox{li}(x) + \alpha ) + K \\ & = & C \; \mbox{li}(x) + K', \end{eqnarray*}$$

where  $K' = K + \alpha C$. Since li $(x) \to \infty$ as $x \to \infty$, there exists $x_1$ such that for $x \geq x_1$, we have $K' \leq \varep \; \mbox{li}(x)$, so that  $\pi (x) \leq (C + \varep )\mbox{li}(x)$. The left-hand inequality is proved in exactly the same way. $\Box$

Note. A similar proof using discrete Abel summation delivers a variant of the theorem in terms of ls$(x)$ instead of li$(x)$.

A numerical example. Some actual numbers will help to illustrate how $\theta (x)$ proceeds in ``jerks", and the limits to how well it can be expected to approximate to $x$. Computation gives  $\theta (181) \approx 167.47$. There are no primes between 181 and 191, so $\theta (x)$ remains constant at this value for $181 \leq x < 191$. The numbers 191, 193, 197, 199 are all prime, each adding slightly more than 5 to $\theta (x)$, with the result that  $\theta (199) \approx 188.56$. This value then persists until we reach 211, the next prime.

Since the jumps $\log p$ in the value of $\theta (x)$ become increasingly large, it is clear that the difference $\theta (x) - x$ is unbounded, even if (as we hope) it is ultimately small compared to $x$.

To prove the prime number theorem, we will have to show that $\theta (x)$ satisfies the hypothesis of Theorem 1.6.2 with $c = 1 - \varep$ and $C = 1 + \varep$ (for any given $\varep > 0$). Apart from diversions, this task will occupy most of the next two chapters. However, one can show by much more direct methods that the stated inequalities hold for some $c$ and $C$. This is what Chebyshev did. Our first proof of the prime number theorem does not actually need these results, while our second and third proofs require the upper estimate but not the lower one. However, the estimates (particularly the upper one) have numerous other applications. Also, their proofs are both ingenious and instructive. Here we prove the upper estimate, leaving the lower one until later (section 2.4), when we will have the machinery to prove it much more neatly.

The proof is rather more number-theoretic in nature than anything we have encountered yet. In particular, we need to recall two statements from elementary number theory.

(NT1) If $p$ is prime and $p\vert ab$, then $p\vert a$ or $p\vert b$.

(NT2) If $p_1\vert a, \; p_2\vert a$ and the greatest common divisor of $p_1$ and $p_2$ is 1 (in particular, if $p_1, p_2$ are distinct primes), then $p_1p_2\vert a$.

These statements are easy consequences of unique prime factorization, but in the usual approach they are actually used in proving it.

Note that by (NT1), if $p\vert n!$, then $p\vert k$ for some $k \leq n$, so certainly $p \leq n$.

Theorem 1.6.3. For all $x > 1$, we have

$$\theta (x) \leq (\log 4)x ,$$

$$\pi (x) \leq (\log 4)\; \mbox{li}(x) + 4 .$$

Note. $\log 4 \approx 1.3863$: our constant $C$ is not much bigger than 1.

Proof. It is sufficient to consider integers $n$. Fix $n$, and let

$$N = {2n+1 \choose n} = \frac{(2n+1)(2n) \ldots (n+2)}{n!}.$$

Now ${2n+1 \choose n} = {2n+1 \choose n+1}$, and these are two terms from the binomial expansion of $\; 2^{2n+1} = (1+1)^{2n+1}$. Hence $N < 2^{2n} = 4^n$. (Of course, this is a very weak estimation of $N$, but it is all we need for the present proof; for an alternative proof, see exercise 3.)

Let $p_{k+1}, \ldots , p_m$ be the primes $p$ such that $n+2 \leq p \leq 2n+1$, so that

$$\sum_{j=k+1}^m \log p_j = \theta (2n+1) - \theta (n+1).$$

By (NT1), these primes do not divide into $n!\;$. But they do divide into $\; (2n+1) \ldots (n+2) = n! N$, so by (NT1) again, they divide into $N$. By (NT2), their product $p_{k+1} \ldots p_m$ divides into $N$, hence is not greater than $N$. Therefore

$$\theta (2n+1) - \theta (n+1) = \log (p_{k+1} \ldots p_m) \leq \log N \leq n\log 4.$$ (3)

It is easily verified that $\theta (n) \leq n \log 4$ for $n = 2,3,4$. Suppose for induction that $\theta (k) \leq k \log 4$ for all $k \leq 2n$, where $n > 1$. Then in particular $\theta (n+1) \leq (n+1)\log 4$, so by (3) we have $\theta (2n+1) \leq (2n+1) \log 4$. Also, $\theta (2n+2) = \theta (2n+1)$, since $2n+2$ is not prime. Hence the required inequality holds for all $k \leq 2n+2$, completing the induction step.

The statement for $\pi (x)$ follows, by 1.6.2, since $\alpha \log 4 = 4$. $\Box$

Corollary 1.6.4. There is a constant $C_1 \leq 3\frac{1}{10}\; \log 4$ such that

$$\pi (x) \leq C_1\frac{x}{\log x} \qquad \mbox{for all } x \geq 2.$$

Proof. This follows at once from 1.6.3 and 1.5.5. $\Box$

Short alternative proofs of this theorem will appear in sections 2.4 and 6.1; however, they do not yield such a good value for the constant.

We finish this section by showing how the last result, combined with Abel summation, can be used to give an upper estimate for $\sum_{p \in P[x]} (1/p)$. (More accurate estimates, both upper and lower, will be obtained in sections 2.1 and 2.6.)

Proposition 1.6.5. Let $C_1$ be as in 1.6.4. Then for another constant $c$,

$$\sum_{p \in P[x]} \frac{1}{p} \leq C_1 \log \log x + c$$

for all $x \geq 2$.

Proof. Denote the sum by $S(x)$. With $u_P$ defined as before, we have by Abel's summation formula,

$$\begin{eqnarray*} S(x) = \sum_{n \leq x} \frac{u_P(n)}{n} & = & \frac{\pi (x)}... ...quad \mbox{(since $\pi (x) < x$)} \\ & = & C_1 \log \log x + c, \end{eqnarray*}$$

where  $c = 1 - C_1 \log \log 2$  (note that $\log \log 2 < 0$). $\Box$

Exercises

1. Modify the proof of 1.6.5 to show that  $\sum_{p \in P} 1/(p \log p)$  is convergent.

2. Let $C$ be such that  $\theta (x) \leq Cx$  for all $x \geq 2$. Show that

$$\sum_{p \in P[x]} \frac{\log p}{p} \leq C(\log x + 1) \qquad \mbox{for } x \geq 2.$$

3. Write  $(2n)!$  as $u_n v_n$, where

$$u_n = 1.3. \ldots (2n-1), \qquad v_n = 2.4. \ldots (2n).$$

Show that $u_n \leq \half v_n$, and hence that

$${2n \choose n} \leq 2^{2n-1} \qquad \mbox{and} \qquad {2n+1 \choose n} \leq 2^{2n}.$$

4. Show that there is a constant $C$ such that for all $x > 2$,

$$\sum_{p \in P,\,p > x} \frac{1}{p^2} \leq \frac{C}{x \log x}.$$