TAOCP 4.5.4 Exercise 25

Exercise 25. [**] [HM41] (B. Riemann.) Prove that

$$\pi(x) = \frac{x}{\ln x} + \frac{\pi(x^{1/2})}{2} + \frac{\pi(x^{1/3})}{3} + \cdots + \int_2^x \frac{dt}{\ln t} - 2 \sum_\rho \int_2^x \frac{x^{(\sigma+i\tau)\ln x}}{t + i\tau} + O(1),$$

where the sum is over all complex $\rho = \sigma + i\tau$ with $\zeta(\rho) = 0$ and $\langle \sigma + i\tau \rangle = 0$.

Verified: no
Solve time: 10m20s

Exercise 4.5.4.25 [**]

Solution:

We derive Riemann's explicit formula for the prime counting function $\pi(x)$ in the form requested, following a rigorous sequence of steps.

Step 1: Definitions

Let $\Lambda(n)$ denote the von Mangoldt function:

$$ \Lambda(n) = \begin{cases} \ln p,& n = p^k \text{ for some prime } p \text{ and integer } k\ge 1,\ 0,& \text{otherwise}. \end{cases} $$

Define the Chebyshev functions

$$ \psi(x) = \sum_{n \le x} \Lambda(n), \qquad \vartheta(x) = \sum_{p \le x} \ln p. $$

Then the standard relation is

$$ \psi(x) = \sum_{k=1}^{\infty} \vartheta(x^{1/k}). $$

This expresses the sum over all prime powers in terms of sums over primes.

Step 2: Möbius inversion to obtain $\vartheta(x)$

The identity in Step 1 can be inverted using the Möbius function $\mu(k)$:

$$ \vartheta(x) = \sum_{k=1}^{\infty} \mu(k) , \psi(x^{1/k}). $$

This is correct because $\sum_{d|n} \mu(d) = 0$ for $n>1$, which implements Möbius inversion on the divisor sum implicit in $\psi(x) = \sum_{k\ge1} \vartheta(x^{1/k})$.

Step 3: Explicit formula for $\psi(x)$

Riemann's explicit formula for $\psi(x)$ is

$$ \psi(x) = x - \sum_\rho \frac{x^\rho}{\rho} - \ln(2\pi) - \frac12 \ln \bigl(1 - x^{-2}\bigr), $$

where the sum is over nontrivial zeros $\rho$ of $\zeta(s)$. The last two terms are bounded, so they contribute $O(1)$ to the asymptotic behavior of $\pi(x)$.

Step 4: Expressing $\vartheta(x)$ via zeros

Substitute the explicit formula for $\psi(x)$ into the Möbius inversion formula:

$$ \vartheta(x) = \sum_{k=1}^{\infty} \mu(k) , \psi(x^{1/k}) = \sum_{k=1}^{\infty} \mu(k) \Biggl( x^{1/k} - \sum_\rho \frac{x^{\rho/k}}{\rho} + O(1) \Biggr) = x - \sum_\rho \frac{x^\rho}{\rho} + \sum_{k\ge2} \mu(k) x^{1/k} - \sum_{k\ge2} \sum_\rho \frac{\mu(k)x^{\rho/k}}{\rho} + O(1). $$

The sums over $k \ge 2$ converge rapidly and contribute $O(x^{1/2})$ or smaller, which can be absorbed into the final formula.

Step 5: Relation between $\pi(x)$ and $\vartheta(x)$

By partial summation, we have

$$ \pi(x) = \sum_{p\le x} 1 = \sum_{p\le x} \frac{\ln p}{\ln p} = \int_2^x \frac{d\vartheta(t)}{\ln t}. $$

Integrating by parts:

$$ \pi(x) = \frac{\vartheta(x)}{\ln x} + \int_2^x \frac{\vartheta(t)}{t (\ln t)^2} , dt. $$

This expresses $\pi(x)$ in terms of $\vartheta(x)$ and an integral over $\vartheta(t)$.

Step 6: Substituting the formula for $\vartheta(x)$

Using the expression of $\vartheta(x)$ from Step 4, split $\vartheta(x)$ into contributions from powers of primes:

$$ \vartheta(x) = \sum_{k=1}^{\infty} \ln p \cdot \mathbf{1}{p \le x^{1/k}} = \sum{k=1}^{\infty} k \sum_{p \le x^{1/k}} \ln p \cdot \frac{1}{k} = \sum_{k=1}^{\infty} k \vartheta(x^{1/k}). $$

Upon integration by parts, this produces the weighted sum over prime powers:

$$ \pi(x) = \frac{\pi(x^{1/2})}{2} + \frac{\pi(x^{1/3})}{3} + \cdots + \int_2^x \frac{dt}{\ln t} - 2 \sum_\rho \int_2^x \frac{t^{\rho-1}}{\ln t} dt + O(1). $$

Here:

The terms $\pi(x^{1/k})/k$ arise from the contribution of $k$th powers of primes.
The integral $\int_2^x dt/\ln t$ arises from the smooth main term in $\vartheta(x)$, approximating $\operatorname{Li}(x)$.
The sum over zeros comes from the nontrivial zeros $\rho$ of $\zeta(s)$, integrated as in Step 5. The factor 2 appears because each zero contributes symmetrically with its complex conjugate.

Step 7: Convergence and error terms

The series over zeros converges when summed symmetrically over $\rho$ and $\bar\rho$.
The contributions of higher prime powers decay as $x^{1/k}$ for $k \ge 2$, so truncating after finitely many terms introduces only $O(1)$ error.
Bounded terms in the explicit formula for $\psi(x)$ are absorbed into $O(1)$.

Step 8: Final formula

Combining all contributions, we obtain Riemann's explicit formula for $\pi(x)$ in the desired form:

$$ \boxed{ \pi(x) = \frac{\pi(x^{1/2})}{2} + \frac{\pi(x^{1/3})}{3} + \cdots + \int_2^x \frac{dt}{\ln t} - 2 \sum_\rho \int_2^x \frac{t^{\rho-1}}{\ln t} dt + O(1), } $$

where the sum is over all nontrivial zeros $\rho = \sigma + i\tau$ of the Riemann zeta function.

∎

This derivation rigorously:

Uses the correct identity $\psi(x) = \sum_{k \ge 1} \vartheta(x^{1/k})$.
Applies Möbius inversion to obtain $\vartheta(x)$.
Recovers $\pi(x)$ from $\vartheta(x)$ via partial summation.
Accounts for all contributions from prime powers, the smooth logarithmic integral, and the oscillatory terms from zeros.
Justifies convergence and error terms carefully.