The Riemann hypothesis is equivalent to the assertion that the prime counting function $\pi(x) := \sum_{p \le x} 1$ deviates from the logarithmic integral $Li(x) = \int_2^x \frac{dx}{\log x}$ in the order $O(\sqrt{x} \log x)$. Since $\log x = O(x^\alpha)$ for any $\alpha>0$, the Riemann hypothesis implies that: $$\forall \alpha > \frac12, |\pi(x) - Li(x)| = O(x^\alpha)$$ From what I understand, this is the best possible power bound available, meaning that for any $\alpha \le \frac12$, we don't have $|\pi(x) - Li(x)| = O(x^\alpha)$. (I'm not sure whether the bounds like $O(\sqrt{x} \log \log x)$ could be possible.)

Where can I read a proof that this indeed is the best possible power bound? The answer on this question claims that any textbook on analytic number theory will do, but I'd like to know an explicit textbook reference that I can look into.

More concretely, I followed the steps outlined in the question referenced above, and could not progress at one point. For the Chebyshev function $\psi(x) = \sum_{p^n \le x}\log p$, I derived that \begin{align*} \left| \psi(x) - x \right| = \left| \log 2\pi + \sum_{\rho} \frac{x^\rho}{\rho} \right| = \left| \log 2\pi + \frac12 \log (1- \frac1{x^2}) + \sum_{\rho \text{ ntv.}} \frac{x^\rho}{\rho} \right| \sim \left| \sum_{\rho \text{ ntv.}} \frac{x^\rho}{\rho} \right| \end{align*} where $f(x) \sim g(x)$ iff $\lim_{x \rightarrow \infty} f(x)/g(x) = 1$, the summation over $\rho$ is the summation over the zeroes of the Riemann zeta, and the qualifier "ntv." refers to counting only the nontrivial zeroes. Since $\psi(x) \sim \pi(x) \log x$, at this point I'd like to show two things:

  1. The Riemann hypothesis is equivalent to the assertion that $|\psi(x) - x| < \sqrt{x} \log ^2 x$ for large enough $x$ (Schoenfield 1976, according to Wikipedia)

  2. Regardless the Riemann hypothesis, one cannot have $|\psi(x) - x| = O(x^\alpha)$ for any $\alpha \le \frac12$.

It looks as if both of the equivalences should follow straightforwardly from the expression $$|\psi(x) - x| \sim \left| \sum_{\rho \text{ ntv.}} \frac{x^\rho}{\rho} \right|$$ However I don't know how to work out the phase factors appearing in the following expression: $$\frac{x^\rho}{\rho} = \left( \frac{e^{it \log x} (\sigma - it)}{\sigma^2+t^2} \right) \cdot x^\sigma \text{, where $\rho = \sigma + it$}$$ to obtain a lower bound or an upper bound to the error term. Further analysis indeed depends on the distribution of the imaginary part of the nontrivial zeroes, which will control how much the weights $\frac1\rho$ contribute in the end.

  • 1
    $\begingroup$ To follow-up on Wojowu's comment: a concrete reference is Montgomery and Vaughan's book "Multiplicative Number Theory I". Littlewood's oscillation theorem is given there as Theorem 15.11 (page 478). Also see their Corollary 15.4 (weaker version of Littlewood's theorem). $\endgroup$ Apr 23, 2021 at 10:07
  • 1
    $\begingroup$ The main procedural error you are making is using the explicit formula in its full form with no error term. You wind up wanting to estimate $|\sum_\rho x^\rho/\rho|$. However, that series (which sums over the nontrivial zeros $\rho$ with multiplicity) does not converge absolutely and there is no easy way to to estimate it directly. You need to use a truncated explicit formula, summing over nontrivial zeros $\rho$ with $|{\rm Im}(\rho)| \leq T$ and adding an error term on the right side that depends on $x$ and $T$. When $T = x$ you'll get the standard error term $O(\sqrt{x}\log x)$. $\endgroup$
    – KConrad
    Apr 24, 2021 at 1:23
  • 3
    $\begingroup$ Oops, I means $O(\sqrt{x}(\log x)^2)$. Anyway, $\psi(x) - x \not= O(\sqrt{x})$ since Littlewood showed in 1914 that $\varliminf_{x \to \infty} (\psi(x) - x)/(\sqrt{x}\log\log\log x)< 0$ and $\varlimsup_{x \to \infty} (\psi(x) - x)/(\sqrt{x}\log\log\log x) > 0$. Monach and Montgomery conjectured that $\varliminf_{x \to \infty} (\psi(x) - x)/(\sqrt{x}(\log\log\log)^2) = -1/(2\pi)$ and $\varlimsup_{x \to \infty} (\psi(x) - x)/(\sqrt{x}(\log\log\log x)^2) = 1/(2\pi)$, which if true means the "correct" term to multiply by $\sqrt{x}$ in the bound on $\psi(x) - x$ is $(\log\log\log x)^2$. $\endgroup$
    – KConrad
    Apr 24, 2021 at 1:31
  • 4
    $\begingroup$ That nobody has proved RH implies a sharper error term on $\psi(x) - x$ for all $x \geq 2$ than $O(\sqrt{x}(\log x)^2)$ could be considered more a matter of inadequate techniques than of the error term $O(\sqrt{x}(\log x)^2)$ being believed to be genuinely optimal as far as the factor $(\log x)^2$ factor is concerned. For instance, Gallagher showed RH implies $\psi(x) - x = O(\sqrt{x}(\log\log x)^2)$ outside a subset $E$ of $[3,\infty)$ with finite logarithmic measure, meaning the exceptions to such a bound are a subset $E$ such that $\int_E dx/x < \infty$. Perhaps $E$ is empty. $\endgroup$
    – KConrad
    Apr 24, 2021 at 1:35
  • 3
    $\begingroup$ If you seek a bound on $\pi(x) - {\rm Li}(x)$, Monach and Montgomery conjectured that $\varliminf_{x \rightarrow \infty} (\pi(x)-{\rm Li}(x))/(\sqrt{x}(\log\log\log x)^2/\log x) = -1/(2\pi)$ and $\varlimsup_{x \rightarrow \infty} (\pi(x)-{\rm Li}(x))/(\sqrt{x}(\log\log\log x)^2/\log x) = 1/(2\pi)$. If that's true, then $\pi(x) - {\rm Li}(x) = O(\sqrt{x}(\log\log\log x)^2/\log x) = o(\sqrt{x})$, so in particular $\pi(x) - {\rm Li}(x) = O(\sqrt{x})$. That nobody has proved RH implies a better bound than $\pi(x) - {\rm Li}(x) = O(\sqrt{x}\log x)$ probably just reflects inadequate techniques. $\endgroup$
    – KConrad
    Apr 24, 2021 at 1:43

1 Answer 1


See Chapter 15 ("Oscillation of error terms") in Montgomery-Vaughan: Multiplicative number theory I. See especially Theorems 15.2-15.3 and 15.11.

Added by Steven Clark and GH from MO. For convenience, we copied below the relevant theorems and some additional text from the book. As usual, $$M(x):=\sum\limits_{n\le x}\mu(n)$$ is the Mertens function.

Theorem 15.2. Let $\Theta$ denote the supremum of the real parts of the zeros of the zeta function. Then for every $\varepsilon>0$, $$\psi(x)-x=\Omega_\pm(x^{\Theta-\varepsilon})\tag{15.1}$$ and $$\pi(x)-\mathrm{li}(x)=\Omega_\pm(x^{\Theta-\varepsilon})\tag{15.2}$$ as $x\to\infty$.

Theorem 15.3. Suppose that $\Theta$ is the supremum of the real parts of $\zeta(s)$, and there is a zero $\rho$ with $\Re\rho=\Theta$, say $\rho=\Theta+i\gamma$. Then $$\underset{x\to\infty}{\text{lim sup}}\ \frac{\psi(x)-x}{x^{\Theta}}\geq \frac{1}{| \rho |}\tag{15.4}$$ and $$\underset{x\to\infty}{\text{lim inf}}\ \frac{\psi(x)-x}{x^{\Theta}}\leq -\frac{1}{| \rho |}.\tag{15.5}$$

Theorem 15.11. As $x\to\infty$, $$\psi(x) -x = \Omega_{\pm} \bigl(x^{1/2} \log \log \log x\bigr),$$ and $$\pi(x) - \mathrm{li}(x) = \Omega_{\pm} \bigl(x^{1/2}(\log x)^{-1}\log \log \log x\bigr).$$

Then in the manner of the proof of Theorem 15.3, we find that if $\Theta+i\gamma$ is a zero of $\zeta(s)$, then

$$\underset{x\to\infty}{\text{lim sup}}\ \frac{M(x)}{x^{\Theta}}\geq \frac{1}{| \rho\,\zeta'(\rho) |},\tag{15.11}$$


$$\underset{x\to\infty}{\text{lim inf}}\ \frac{M(x)}{x^{\Theta}}\leq -\frac{1}{| \rho\,\zeta'(\rho) |}.\tag{15.12}$$

  • 1
    $\begingroup$ Thanks! Those two theorems resolve my concerns mostly. I'll leave the question unanswered for a bit to see if others have more to say about the matter. $\endgroup$
    – Uzu Lim
    Apr 23, 2021 at 10:23
  • 3
    $\begingroup$ For those who do not have access to the book, it would be nice if you could state what these quoted results are. $\endgroup$
    – Wojowu
    Apr 23, 2021 at 10:48
  • 2
    $\begingroup$ @Wojowu I added the quoted results to the answer above but my edit is pending approval by trusted community members. $\endgroup$ Apr 23, 2021 at 14:41
  • 1
    $\begingroup$ @StevenClark: Thanks. I also added (15.1) from Theorem 15.2, which covers the case when there is no zero with real part $\theta$. $\endgroup$
    – GH from MO
    Apr 23, 2021 at 15:12
  • 1
    $\begingroup$ @AccidentalFourierTransform: I updated the text, thank you. $\endgroup$
    – GH from MO
    Apr 23, 2021 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.