## Sunday, December 21, 2014

### Ingham's Theorem on primes in short intervals

In ths post, we prove a theorem of Ingham, which states that there is always a prime on the short interval $[x,x+x^{\frac{5}{8}+\varepsilon}]$ when $x\geq M_{\varepsilon}$. More precisely, the theorem even gives an asymptotic formula for the number of such primes. It may seem a priori rather surprising that we are able to show the correct asymptotic for $\pi(x+x^{\theta})-\pi(x)$ for some numbers $\theta<1$ without being able to improve the error term in the prime number theorem to $x^{1-\varepsilon}$ for any $\varepsilon>0$. A crucial ingredient in the proof is relating the number of primes in short intervals to bounds for the number of zeros of the Riemann $\zeta$ function with real part at least $\sigma$ and imaginary part bounded by $T$. Even though we can by no means say that no zeros exist for $\sigma<1-\varepsilon$ for any $\varepsilon>0$, we still manage to prove that the number of zeros with real part at least $\sigma$ decays at least like $T^{A(1-\sigma)}\log^B T$ for some constants $A$ and $B$ so that zeros far from the critical line must be quite rare. The other crucial ingredient in the proof is in fact showing that bounds for $\zeta(\frac{1}{2}+it)$ lead to bounds for the number of zeros off from the critical line via the principle of argument, among other things. In particular, we will see that the truth of the Lindelöf hypothesis $\zeta(\frac{1}{2}+it)\ll t^{\varepsilon}$ for all $\varepsilon>0$ would imply that the intervals $[x,x+x^{\frac{1}{2}+\varepsilon}]$ contain primes for all $x\geq M_{\varepsilon}$. Of course, the truth of the Riemann hypothesis would imply that the shorter interval $[x,x+C\sqrt{x}\log^2 x]$ contains a prime for all large enough $x$, and Cramér's conjecture asserts that even intervals as short as $[x,x+K\log^2 x]$ contain primes for all $x$ when $K$ is large enough. The best unconditional result is due to Baker, Harman and Pintz, and says that the interval $[x,x+x^{0.525}]$ contains a prime for all large enough $x$.

Hoheisel's theorem

We follow K. Chandrasekharan's book Arithmetical Functions throughout the proof. The first step in proving Ingham's theorem is Hoheisel's result that good upper bounds for the number of zeros off from the critical line imply the existence of primes in short intervals. Hoheisel was the first to show that there exists $\theta<1$ such that the interval $[x,x+x^{\theta}]$ contains a prime for all large $x$.

Theorem 1 (Hoheisel). Suppose that $\zeta(s)\neq 0$ whenever $\sigma>1-\frac{A\log \log t}{\log t}$ and $t\geq t_0$. Moreover, suppose that the number $N(\sigma,T)$ of zeros $\beta+i\gamma$ of $\zeta$ with $\beta\geq \sigma$ and $0<\gamma\leq T$ satisfies $N(\sigma,T)\ll T^{b(1- \sigma)}\log^{B}T$ uniformly for $\sigma\in [\frac{1}{2},1]$. Then
$\begin{eqnarray}\pi(x+x^{\theta})-\pi(x)\sim \frac{x^{\theta}}{\log x}\end{eqnarray}$
for $1-\frac{1}{b+\frac{B}{A}}<\theta<1$.

Proof. Let $\psi(x)$ be the Chebychev prime counting function. By a simple computation, for $h=x^{\theta}$ with $\theta\in (\frac{1}{2},1)$,
$\begin{eqnarray}\psi(x+h)-\psi(x)&=&\sum_{x\leq p\leq x+h}\log p+O(\sqrt{x}\log x)\\&=&(\pi(x+h)-\pi(x))(\log x+O(1))+O(\sqrt{x}\log x),\end{eqnarray}$
so that $\psi(x+h)-\psi(x)\sim h$ is equivalent to $\pi(x+h)-\pi(x)\sim h$ for such $h$. We indeed have $\theta>\frac{1}{2}$ in the theorem, because the well-known estimate $N(\frac{1}{2},T)\asymp T\log T$ (coming from the functional equation, which implies that the non-trivial zeros are symmetric with respect to the line $\sigma=\frac{1}{2}$) gives $b\geq 2.$

We apply the explicit formula for the Chebychev function to write
$\begin{eqnarray}\psi(x)=x-\sum_{|\gamma|\leq T}\frac{x^{\rho}}{\rho}+O\left(\frac{x\log^2 x}{T}\right)\end{eqnarray}$
for $3\leq T\leq x$. Consequently, for $0\leq h\leq x$
$\begin{eqnarray}\frac{\psi(x+h)-\psi(x)}{h}=1-\sum_{|\gamma|\leq T}\frac{(x+h)^{\rho}-x^{\rho}}{h\rho}+O\left(\frac{x\log^2 x}{Th}\right).\end{eqnarray}$
By the intermediate value theorem,
$\begin{eqnarray}\left|\frac{(x+h)^{\rho}-x^{\rho}}{h}\right|\leq x^{\beta-1},\end{eqnarray}$
where $\rho=\beta+i\gamma.$ Now
$\begin{eqnarray}\frac{\psi(x+h)-\psi(x)}{h}=1+O\left(\sum_{|\gamma\leq T|}x^{\beta-1}\right)+O\left(\frac{x\log^2 x}{Th}\right).\end{eqnarray}$
We have
$\begin{eqnarray}\sum_{|\gamma|\leq T}(x^{\beta-1}-x^{-1})&=&\sum_{|\gamma\leq T|}\int_{0}^{\beta}x^{\sigma-1}d\sigma\log x\\&=&\int_{0}^{1}\sum_{|\gamma\leq T\atop \beta\geq \sigma|}x^{\sigma-1}d\sigma \log x,\end{eqnarray}$
so that
$\begin{eqnarray}\sum_{|\gamma|\leq T}x^{\beta-1}=2x^{-1}N(0,T)+2\int_{0}^{1}N(\sigma,T)x^{\sigma-1}\log x d\sigma.\end{eqnarray}$
As already mentioned, we must have $b\geq 2$ in the theorem, and hence the assumed estimate for $N(\sigma,T)$ holds for all $\sigma\in [0,1]$ uniformly. If we denote $\eta(T)=\frac{A\log \log T}{\log T}$, we obtain
$\begin{eqnarray}\sum_{|\gamma|\leq T}x^{\beta-1}&\ll& \frac{T\log T}{x}+\int_{0}^{1-\eta(T)}\left(\frac{T^b}{x}\right)^{1-\sigma}\log^B T\log xd\sigma\\&\ll& \frac{T\log T}{x}+\left(\frac{T^b}{x}\right)^{1-\eta(T)}\log^B T\frac{\log x}{\log \frac{T^b}{x}}.\end{eqnarray}$
We choose $T=x^{a}$ with $a\in (0,\frac{1}{b})$ to arrive at
$\begin{eqnarray}\sum_{|\gamma|\leq T}x^{\beta-1}&\ll& x^{a-1}\log x+x^{(ab-1)\eta(x^a)}\log^B x\\&\ll& x^{a-1}\log x+\exp\left(\left(b-\frac{1}{a}\right)A\log \log x\right)\log^B x\\&\ll& (\log x)^{-\varepsilon}\end{eqnarray}$
for some $\varepsilon>0$, as long as $(a-\frac{1}{b})A+B<0$. From this we solve $a<\frac{1}{b+\frac{B}{A}}$. Therefore, for $h=x^{\theta}\leq x$, we have
$\begin{eqnarray}\frac{\psi(x+h)-\psi(x)}{h}=1+O\left((\log x)^{-\varepsilon}+x^{1-a-\theta}\log^2 x\right),\end{eqnarray}$
and if $1>\theta>1-\frac{1}{b+\frac{B}{A}}$, the left-hand side is asymptotic to $1$, as desired. ■

We notice that the assumption on the zero-free region of $\zeta$ is valid for any $A$, by the Chudakov zero-free region from this post. Hence we have the following immediate corollary to Hoheisel's result.

Corollary. Suppose $N(\sigma,T)\leq T^{b(1-\sigma)}\log^B T$ uniformly for $\sigma\in [\frac{1}{2},1]$. Then
$\begin{eqnarray}\pi(x+x^{\theta})-\pi(x)\sim\frac{x^{\theta}}{\log x},\end{eqnarray}$
for any $\theta>1-\frac{1}{b}$.

Therefore, our task in the next section is to show that $b=\frac{5}{3}$ is admissible.

Ingham's theorem

The following theorem tells that any bound for the zeta function on the critical strip gives a bound for $N(\sigma,T)$ of the desired form. For the proof we need two lemmas which will be proved in the next subsection, in order to keep the main ideas of the proof visible.

Lemma 2. Let $h$ be an analytic function in the closed disk $\overline{B(s_0,R)}$, and let $r<R$. If $m$ is the number of zeros of $h$ inside $\overline{B(s_0,r)}$, then
$\begin{eqnarray}\left(\frac{R}{r}\right)^m\leq \max_{s\in \partial B(s_0,R)}\frac{|h(s)|}{|h(s_0)|}.\end{eqnarray}$

Before formulating the other lemma, we motivate it briefly. In order to estimate the number $N(\sigma,T)$ of zeros, we use the argument principle, which leads us to bounding integrals related to the logarithmic derivative of $\zeta$. However, instead of $\zeta$, we want to consider the function
$\begin{eqnarray}f_X(s):=\zeta(s)M_X(s)-1; \quad M_X(s):=\sum_{n<X}\frac{\mu(n)}{n^s}.\end{eqnarray}$
The reason for considering this function is that $1-f_X(s)^2$ has all the zeros of $\zeta$ (and some others), but is presumably a lot smaller since $M_X(s)$ is nearly the reciprocal of $\zeta(s)$. The argument principle gives us better bounds for the number of zeros of a function if the function is small; the cost of adding some additional zeros by considering $1-f_X(s)^2$ turns out to be negligible here. Hence the following lemma will be put into use.

Lemma 3 (Ingham). Let $c$ be such that $\zeta(\frac{1}{2}+it)\ll t^c$. Then
$\begin{eqnarray}\int_{1}^{T}|f_X(\sigma+it)|^2dt\ll T^{4c(1-\sigma)}X^{1-2\sigma}(T+X)\log ^4 (T+X)\quad (3)\end{eqnarray}$
for any $T>2,X>2$ and $\sigma\in [\frac{1}{2},1]$; the implied constant is absolute.

With the necessary lemmas formulated, we proceed to Ingham's theorem.

Theorem 4 (Ingham). Let $c$ be a constant such that $\zeta(\frac{1}{2}+it)\ll t^c$. Then $N(\sigma,T)\ll T^{2(1+2c)(1-\sigma)}\log^5 T$.

Proof. Define $h_X(s):=1-f_X(s)^2=\zeta(s)M_X(s)(2-M_X(s))$. Trivially, the number of zeros of $\zeta$ in any region is bounded by the number of zeros of $h$ in the region. Let $N_h(\sigma;T,T_0)$ denote the number of zeros $\beta+i\gamma$ of $h$ such that $T_0\leq \gamma\leq T$. Here $T_0\in(3,4)$ is any fixed number such that there are no zeros of $h$ with imaginary part $T_0$. We have for any $\delta>0$ and $\sigma_0\in [\frac{1}{2},1]$ the trivial inequality
$\begin{eqnarray}N(\sigma_0+\delta;T,T_0)\leq \frac{1}{\delta}\int_{\sigma_0}^{\sigma_0+\delta}N(\sigma;T,T_1)\leq \frac{1}{\delta}\int_{\sigma}^{2} N_h(\sigma_0;T,T_1)d\sigma.\end{eqnarray}$
We are going to estimate the last integral by the argument principle and utilizing the fact that $f_X(\sigma+it)$ is known to have (in a certain sense) small second moment.

The argument principle and Fubini's theorem give
$\begin{eqnarray}\int_{\sigma_0}^{2}N_h(\sigma;T,T_0)&=&\int_{\sigma_0}^{2}\left(\int_{\sigma_0+iT_0}^{2+iT_0}+\int_{2+iT_0}^{2+iT}+\int_{2+iT}^{\sigma+iT}\right)\Im\left(\frac{h'(s)}{h(s)}\right)d\sigma\\&-&\int_{T_0}^{T}\int_{\sigma_0}^{2}\Re\left(\frac{h'(\sigma+it)}{h(\sigma+it)}\right)d\sigma dt\quad (1)\end{eqnarray}$
(it does not matter that the integrals are possibly undefined at countably many points where $\sigma$ hits the real part of a zero or $t$ hits the imaginary part of a zero).

The second integral can be evaluated as
$\begin{eqnarray}\int_{T_0}^{T}(\log |h(\sigma_0+it)|-\log |h(2+it)|)dt.\quad (2)\end{eqnarray}$
We have
$\begin{eqnarray}|h(2+it)|\geq 1-|f_X(2+it)|^2\geq 1-\left(\sum_{n\geq X}\frac{\tau(n)}{n^2}\right)^2\geq 1-\frac{1}{2X}>\frac{1}{2}\end{eqnarray}$
for large enough $X$, so $\log |h(2+it)|$ contributes only a bounded amount to the integral $(2)$, because we see similarly that $|h(2+it)|$ is bounded from bove by a constant. The contribution of $\log |h(\sigma+it)|$ to $(2)$, in turn, is bounded by
$\begin{eqnarray}\int_{T_0}^{T} \log (1+|f_X(\sigma+it)|^2)dt&\leq& \int_{T_0}^{T}|f_X(\sigma+iT)|^2dt,\end{eqnarray}$
and this is why the second monent of $f_X(\sigma+it)$ over $t\in[T_0,T]$ plays an important role in estimating $N(\sigma;T,T_0).$

When it comes to estimating the integrals in $(1)$, the second one is very easy to bound, as $\Re(h(2+it))>0$ implies
$\begin{eqnarray}\int_{\sigma_0}^2 \int_{2+iT_0}^{2+iT}\Im\left(\frac{h'(s)}{h(s)}\right)=\int_{\sigma_0}^2 \Im(\log h(2+iT_1)-\log h(2+iT_0))\ll 1.\end{eqnarray}$
The other two integrals are more compliactd, as $\Re(h(s))=0$ may happen several times on the lines of integration, preventing a direct application of the logarithmic differentiation formula. Instead, we can use the following observation. Denote by $m_1$ the number of solutions to $\Re(h(s))=0$ on the segment $I_1=[\sigma_0+iT_0,2+iT_0]$, and by $m_2$ the number of solutions to $\Re(h(s))=0$ on the segment $I_2=[\sigma+iT,2+iT]$. Then
$\begin{eqnarray}\left|\int_{I_k}\Im\left(\frac{h'(s)}{h(s)}\right)ds\right|\leq (m_k+1)\pi\end{eqnarray}$
for $k=1,2$. This is because the segment $I_k$ can be divided into at most $m_k+1$ subsegments $[a_j,b_j]$ on which $h(s)$ winds around the origin exactly once, resulting in the value $\pi$ for the integral over $[a_k,b_k]$ by the residue theorem.

Further, $m_1$ is the number of zeros of the analytic function $H_k(s)=\frac{1}{2}(h(s+iT_0)-h(s-iT_k0)$ on the real segment $s\in [\sigma_0,2]$, and similarly for $m_2$ (with $T$ in place of $T_0$). The number of zeros of $H_2$ on this segment is at most the number of its zeros in the ball $B(2,\frac{3}{2})$. As $H_2(s)$ is analytic in the bit larger circle $B(2,\frac{7}{4})$, Lemma 2 results in
$\begin{eqnarray}\left(\frac{\frac{7}{4}}{\frac{3}{2}}\right)^{m_1}\leq \max_{s\in B(2,\frac{3}{2})}\left|\frac{H_2(s)}{H_2(2)}\right|\ll \max_{\sigma\geq \frac{1}{4}\atop t\in [1,T+3]}|h_X(s)|\ll \max_{\sigma\geq \frac{1}{4}\atop t\in [1,T+3]}|\zeta(s)M_X(s)|^2. \end{eqnarray}$
We have $|M_X(s)|\leq \sum_{n<X} n^{-\frac{1}{4}}\ll X^{\frac{3}{4}}$ for $\sigma\geq \frac{3}{4}$, and $\zeta(\sigma+it)\ll T^2$ for $\sigma\geq 0$ and $t\in [1,T+3]$ by bounds for zeta sums in this post. Therefore
$\begin{eqnarray}m_2\ll \log(TX)\ll \log(T+X),\end{eqnarray}$
which is negligible compared to the contribution of $(3)$. We get an analogous bound for $m_1$, with $T$ replaced by $T_0$. In conclusion, we have by Lemma 3 the bound
$\begin{eqnarray}N(\sigma_0+\delta;T,T_0)\ll \frac{1}{\delta}T^{4c(1-\sigma_0)}(TX^{1-2\sigma_0}+X^{2(1-\sigma_0)})\log^4 (T+X).\end{eqnarray}$
We take $X=T$ and $\delta=\frac{1}{\log T}$, and use $T^{\delta}\ll 1$ to arrive at
$\begin{eqnarray}N(\sigma,T)\ll T^{(2+4c)(1-\sigma)}\log^5 T\end{eqnarray}$
when $\sigma\in [\frac{1}{2}+\frac{1}{\log T},1]$. For $\sigma\in [\frac{1}{2},\frac{1}{2}+\frac{1}{\log T}]$, we have $T^{(2+4c)(1-\sigma)}\log^5 T\asymp T^{1+2c}\log^5 T\gg N(\frac{1}{2},T)$, so the desired inequality for the number of zeros is plainly satisfied. This completes the proof. ■

Corollary. We have $\pi(x+x^{\theta})-\pi(x)\sim \frac{x^{\theta}}{\log x}$ for any $\theta>\frac{5}{8}$. In particular, the interval $[x,x+x^{\frac{5}{8}+\varepsilon}]$ contains a prime for $x>M_{\varepsilon}$. If we assume the Lindelöf hypothesis, the asymptotic holds for any $\theta>\frac{1}{2}$.

Proof. We recall the Hardy-Littlewood bound $\zeta(\frac{1}{2}+it)\ll t^{\frac{1}{6}}\log t$ from this post. We take $c=\frac{1}{6}+\delta$ for sufficiently small $\delta>0$ and $b=2+4c$ in the corollary to Theorem 1. We see that the asymptotic formula holds for all $\theta>1-\frac{1}{b}=1-\frac{1+4c}{2+4c}$. As $\delta\to 0$, we see that the asymptotic formula holds for any $\theta>\frac{5}{8}$. Under the Lindelöf hypothesis, we can take $c$ arbitrarily small, so that $1-\frac{1+4c}{2+4c}$ can be taken to be any number greater than $\frac{1}{2}.$ ■

Second moment of a Dirichlet series

We prove the two lemmas required for Ingham's theorem in this section. The first involves only standard complex analysis and can be proved as follows.

Proof of Lemma 2 By shifting the function, we may assume $s_0=0$. Let $a_1,...,a_m$ be the zeros of $h$ in $\overline{B(0,r)}$. We may write
$\begin{eqnarray}h(s)=g(s)\prod_{j=1}^m \frac{(s-a_j)R}{R^2-\bar{a_j}s},\end{eqnarray}$
where $g$ is analytic in $\overline{B(0,R)}$. The factors of the product have modulus $1$ when $|s|=R$, because if $s=Re^{i\theta}$, the factors are
$\begin{eqnarray}\frac{Re^{i\theta}-a_j}{R-\bar{a_j}e^{i\theta}},\end{eqnarray}$
and the numerator and denominator are conjugates. Therefore
$\begin{eqnarray}|g(s)|=|h(s)|\leq \max_{s\in \partial B(s_0,R)}|h(s)|\end{eqnarray}$
for $|s|=R$. The maximum principle of analytic functions yields $|g(0)|\leq \max_{s\in \partial B(s_0,R)}|h(s)|$, so that
$\begin{eqnarray}|h(0)|=|g(0)|\prod_{j=1}^m\frac{|a_j|}{R}\leq \max_{s\in \partial B(s_0,R)}|h(s)|\left(\frac{r}{R}\right)^m,\end{eqnarray}$
which was to be shown. ■

The lemma about the second moment of $f_X$ over $[1,T]$ is more complicated. The idea is to prove the result first for $\sigma=\frac{1}{2}$ and $\sigma=1+\delta$ for small $\delta>0$. On these lines we are able to control $f_X$; on $\sigma=\frac{1}{2}$, this is due to our assumption on the growth of $\zeta\left(\frac{1}{2}+it\right)$, and on $\sigma=1+\delta$, this is due to the convergence of the Dirichlet series of $\zeta.$ The purpose of the following lemma is to provide a way of interpolating the general result from bounds on these two lines.

Lemma 5 (Hardy, Ingham, Pólya) Let $f$ be an analytic function in the strip $\sigma\in [\sigma_1,\sigma_2].$ Let
$\begin{eqnarray}J_{\sigma}:=\int_{-\infty}^{\infty}|f(\sigma+it)|^2dt,\end{eqnarray}$
and assume that the integral is convergent for $\sigma\in [\sigma_1,\sigma_2].$ Assume also $\displaystyle \lim_{t\to \infty}f(\sigma+it)=0$ uniformly in $\sigma$. Then
$\begin{eqnarray}J_{\sigma}\leq J_{\sigma_1}^{\frac{\sigma_2-\sigma}{\sigma_2-\sigma_1}}\cdot J_{\sigma_2}^{\frac{\sigma-\sigma_1}{\sigma_2-\sigma_1}}.\end{eqnarray}$

Proof. The claim of the lemma is that $\log J_{\sigma}$ is a convex function. It suffices to show that
$\begin{eqnarray}J_{\frac{\sigma_1+\sigma_2}{2}}\leq J_{\sigma_1}^{\frac{1}{2}}\cdot J_{\sigma_2}^{\frac{1}{2}},\end{eqnarray}$
because if $\varphi$ is a continuous function on an interval $I$ satisfying
$\begin{eqnarray}\varphi\left(\frac{x+y}{2}\right)\leq \frac{\varphi(x)+\varphi(y)}{2}\end{eqnarray}$
for all $x,y\in I$, then $\varphi$ is convex. This is seen by proving
$\begin{eqnarray}\varphi(\alpha x+(1-\alpha y))\leq \alpha \varphi(x)+(1-\alpha)\varphi(y)\end{eqnarray}$
first when $\alpha$ is a dyadic rational number and then using continuity. The continuity of $J_{\sigma}$ is immediate by dominated convergence.

To prove midpoint convexity, we define, with $\sigma_0=\frac{\sigma_1+\sigma_2}{2},$ $f^{*}(s)=\overline{f(\sigma_0-\bar{s})}$, which is also analytic in the same strip as $f$. Let $R$ be the rectangle bounded by $\sigma=\sigma_1,\sigma=\sigma_2$, $t=-T$ and $t=T$. Let $R_1$ be the left half of $R$ and $R_2$ be its right half. Let their boundaries be $\tilde{R_1}$ and $\tilde{R_2}$, respectively. As $f^{*}(s)=\overline{f(s)}$ on the line $\sigma=\sigma_0$, Cauchy's theorem gives
$\begin{eqnarray}\int_{\sigma_0-iT}^{\sigma_+iT}|f(s)|^2ds=\int_{\sigma_0-iT}^{\sigma_+iT}f(s)f^{*}(s)ds=\int_{\tilde{R_2}}f(s)f^{*}(s)ds.\end{eqnarray}$
Now Cauchy-Schwarz gives
$\begin{eqnarray}\left|\int_{\sigma_0-iT}^{\sigma_0+iT}|f(s)|^2ds\right|&\leq& \left(\int_{\tilde{R_2}}|f(s)|^2|ds|\right)^{\frac{1}{2}}\left(\int_{\tilde{R_2}}|f^{*}(s)|^2|ds|\right)^{\frac{1}{2}}\\&=&\left(\int_{\tilde{R_2}}|f(s)|^2|ds|\right)^{\frac{1}{2}}\left(\int_{\tilde{R_1}}|f(s)|^2|ds|\right)^{\frac{1}{2}}\quad (4)\end{eqnarray}$
We finally let $T\to \infty$. By assumption,
$\begin{eqnarray}\int_{\sigma_0+iT}^{\sigma_2+iT}|f(s)|^2 |ds| \xrightarrow{T\to \infty}0,\end{eqnarray}$
so the two integrals in $(4)$ converge to $J_{\sigma_2}$ and $J_{\sigma_1}$, finishing the proof. ■

We still need two auxiliary result before proving Lemma 3. These are bounds for certain divisor sums arising in the proof.

Lemma 6. We have
$\begin{eqnarray}(i)\quad\sum_{n\leq x}\tau(n)^2\ll x\log^3 x\end{eqnarray}$
and
$\begin{eqnarray}(ii)\quad\Phi(x):=\sum_{m<n\leq x}\frac{\tau(m)\tau(n)}{(mn)^{\frac{1}{2}}\log\left(\frac{n}{m}\right)}\ll x\log^4 x.\end{eqnarray}$

One could show that actually $\Phi(x)\ll x\log^3 x$, but that would require more work and would not affect the outcome of Ingham's theorem on primes in short intervals.

Proof. $(i)$ We have
$\begin{eqnarray}\sum_{n\leq x}\tau(n)^2&=&\sum_{n\leq x}\tau(n)\sum_{d\mid n}1\\&=&\sum_{d\leq x}\sum_{k\leq \frac{x}{d}}\tau(kd)\\&\leq& \sum_{d\leq x}\tau(d)\sum_{k\leq \frac{x}{d}}\tau(k)\\&\ll& \sum_{d\leq x}\tau(d)\frac{x}{d}\log \frac{x}{d}\\&\ll& x\log x \sum_{d\leq x}\frac{\tau(d)}{d}\\&\ll& x\log^3 x\end{eqnarray}$
by applying partial summation to the divisor bound $\sum_{n\leq x}\tau(n)\ll x\log x.$

(ii) We have
$\begin{eqnarray}\left|\log\left(\frac{m}{n}\right)\right|^{-1}=\left|\log\left(1-\frac{n-m}{n}\right)\right|^{-1}<\frac{n}{n-m}<1+\frac{(mn)^{\frac{1}{2}}}{n-m}.\end{eqnarray}$
Hence,
$\begin{eqnarray}\Phi(x)\leq \sum_{m<n\leq x}\frac{\tau(m)\tau(n)}{(mn)^{\frac{1}{2}}}+\sum_{m<n\leq x}\frac{\tau(m)\tau(n)}{n-m}.\end{eqnarray}$
Here the first sum is
$\begin{eqnarray}\left(\sum_{n\leq x}\frac{\tau(n)}{n^{\frac{1}{2}}}\right)^2\ll x\log^2 x,\end{eqnarray}$
by using partial summation to the divisor bound $\sum_{n\leq x}\tau(n)\ll x\log x$. The second sum can be bounded in the following way.
$\begin{eqnarray}\sum_{m<n\leq x}\frac{\tau(m)\tau(n)}{n-m}&=&\sum_{k\leq x}\frac{1}{k}\sum_{m\leq x-k}\tau(m)\tau(m+k\\&\ll& \sum_{k\leq x}\frac{1}{k}\left(\sum_{m\leq x}\tau(m)^2\sum_{m\leq x-k}\tau(m+k)^2\right)^{\frac{1}{2}}\\&\ll& \sum_{k\leq x}\frac{1}{k}\cdot x\log^3 x\ll x\log^4 x\end{eqnarray}$
by part $(i)$ of the lemma. ■

We are finally in a position to prove Lemma 3.

Proof of Lemma 3. We have
$\begin{eqnarray}f_X(s)=\sum_{n=1}^{\infty}\frac{c_X(n)}{n^s},\end{eqnarray}$
where $c_X(1)=0$ and $c_X(n)=\sum_{d\mid n, d<X}\mu(d)$ for $n>1$. Hence $|c_X(n)|\leq \tau(n)\cdot 1_{[X,\infty]}(n)$, where $\tau(\cdot)$ counts the number of divisors. As already mentioned, we are going to estimate the integral of $|f_X(\sigma+it)|$ for $\sigma=\frac{1}{2}$ and $\sigma=1+\delta$ with $\delta\in (0,1)$, and interpolate to obtain a bound in the intermediate range.

First we bound
$\begin{eqnarray}\int_{0}^{T}|f_X(1+\delta+it)|^2dt&=&\sum_{m,n\geq X}\frac{c_X(m)c_X(n)}{(mn)^{1+\delta}}\int_{0}^{T}\left(\frac{m}{n}\right)^{it}d\\&\leq& T\sum_{n\geq X}\frac{\tau(n)^2}{n^{2+2\delta}}+4\sum_{n>m\geq X}\frac{\tau(m)\tau(n)}{(mn)^{1+\delta}\log\left(\frac{n}{m}\right)}.\end{eqnarray}$
Lemma 6 can be used to bound these two sums. By partial summation and Lemma 6 (i),
$\begin{eqnarray}\sum_{n\geq X}\frac{\tau(n)^2}{n^{2+2\delta}}\ll \frac{1}{X^{1+2\delta}}\log^3 X.\end{eqnarray}$

In addition, by Lemma 6 (ii) and the inequality $\frac{1}{\log x}<1+\frac{1}{\sqrt{x}\log x}$ for $x>1$,
$\begin{eqnarray}\sum_{n>m\geq X}\frac{\tau(m)\tau(n)}{(mn)^{1+\delta}\log\left(\frac{n}{m}\right)}&\ll& \sum_{n>m\geq X}\frac{\tau(m)\tau(n)}{(mn)^{1+\delta}}+\sum_{n>m\geq X}\frac{\tau(m)\tau(n)n^{-\frac{1}{2}}m^{\frac{1}{2}}}{(mn)^{1+\delta}\log\left(\frac{n}{m}\right)}\\&\ll& \left(\sum_{n=1}^{\infty}\frac{\tau(n)}{n^{1+\delta}}\right)^2+\sum_{n>m\geq 1}\frac{\tau(m)\tau(n)}{(mn)^{\frac{1}{2}\log\left(\frac{n}{m}\right)}}\int_{n}^{\infty}\frac{1+\delta}{x^{2+\delta}}dx\\&\ll& \zeta^4(1+\delta)+\int_{1}^{\infty} \frac{1+\delta}{x^{2+\delta}}\Phi(x)dx\\&\ll& \delta^{-4}+\int_{1}^{\infty}\frac{1+\delta}{x^{1+\delta}}\log^4 x dx\ll \delta^{-4}\end{eqnarray}$
by the Dirichlet zeries of $\zeta^2$. Moreover, $\frac{\log^3 X}{X^{1+2\delta}}\ll \frac{1}{\delta^3 X}$ as $X^{2\delta}\gg (\delta \log X)^3.$ This implies
$\begin{eqnarray}\int_{0}^{T}|f_X(1+\delta+it)|^2dt\ll\left(\frac{T}{X}+1\right)\delta^{-4}.\end{eqnarray}$
On the line $\sigma=\frac{1}{2},$ we estimate
$\begin{eqnarray}\int_{0}^{T}|f_X(\frac{1}{2}+it)|^2dt&\ll& \int_{0}^{T}|\zeta(\frac{1}{2}+it)|^2|M_X(\frac{1}{2}+it)|^2dt+T\\&\ll& T^{2c}\int_{0}^{T}|M_X(\frac{1}{2}+it)|^2dt+T\\&\ll& T^{1+2c}\sum_{n<X}\frac{\mu^2(n)}{n}+4T^{2c}\sum_{m<n<X}\frac{|\mu(m)\mu(n)|}{(mn)^{\frac{1}{2}}\log\left(\frac{n}{m}\right)}\\&\ll& T^{1+2c}\log X+4T^{2c}\sum_{m<n<X}\left(\frac{1}{(mn)^{\frac{1}{2}}}+\frac{1}{n-m}\right)\\&\ll& T^{2c}(T+X)\log X.\end{eqnarray}$
Now we will interpolate between the two integral inequalities. Define
$\begin{eqnarray}I_{\sigma}(T):=\int_{0}^{T}|f_X(\sigma+it)|^2dt.\end{eqnarray}$
The function $f_X(s)1_{[0,T]}(\Im(s))$ is of course not analytic, so we have to smoothen it in such a way that the resulting analytic function is tiny outside $[-T,T]$. To this end, we define
$\begin{eqnarray}J_{\sigma}=\int_{-\infty}^{\infty}|F_{X,\tau}(\sigma+it)|^2dt,\end{eqnarray}$
where
$\begin{eqnarray}F_{X,\alpha}(s)=\frac{s-1}{s\cos\left(\frac{s}{2\tau}\right)}|f_{X}(s)|^2\end{eqnarray}$
and $\tau>2$, say (so that the cosine term does not vanish in the strip $\sigma\in [\frac{1}{2},1+\delta]$). We have
$\begin{eqnarray}\frac{1}{\cos\left(\frac{s}{2\tau}\right)}\asymp e^{-\frac{|t|}{2\tau}}\end{eqnarray}$
in the strip $\sigma\in [\frac{1}{2},1+\delta]$, so that factor acts as a mollifier. We also have, for fixed $s$,
$\begin{eqnarray}\frac{s-1}{s}\zeta(s)M_X(s)-\frac{s-1}{s}\ll_{X} \frac{(s-1)\zeta(s)}{s}+1\ll |s|^2\ll t^2\end{eqnarray}$
by the formula
$\begin{eqnarray}\zeta(s)=\sum_{n\leq t^2}n^{-s}+O(1),\quad \sigma\geq \frac{1}{2}\end{eqnarray}$
proved in this post (the proof is just partial summation). The factor $s-1$ was necessary in the definition of $F_{X,\tau}$ to compensate for the pole of $\zeta$. In conclusion,
$\begin{eqnarray}F_{X,\tau}(s)\asymp e^{-\frac{|t|}{2\tau}}|f_X(s)|, \quad \frac{1}{2}\leq\sigma\leq 1+\delta,\quad |t|\geq 1\end{eqnarray}$
and further $\displaystyle\lim_{t\to \infty}|f(\sigma+it)|=0$ uniformly for $\sigma\in [\frac{1}{2},1+\delta]$. By partial integration, we have
$\begin{eqnarray}J_{1+\delta}\ll 1+\int_{0}^{\infty} e^{-\frac{t}{\tau}}|f_X(\sigma+it)|^2dt=1+\int_{0}^{\infty}e^{-y}I_{\sigma}(\tau y)dy,\end{eqnarray}$
and this implies
$\begin{eqnarray}J_{1+\delta}\ll 1+\int_{0}^{\infty}e^{-y}\left(\frac{\tau y}{X}+1\right)\delta^{-4}dy\ll \left(\frac{\tau}{X}+1\right)\delta^{-4}.\end{eqnarray}$
Similarly,
$\begin{eqnarray}J_{\frac{1}{2}}\ll 1+\int_{0}^{\infty}e^{-y}(\tau y)^{2c}(\tau y+X)\log Xdy\ll \tau^{2c}(\tau+X)\log X.\end{eqnarray}$
Now Lemma 5 is applied to conclude that
$\begin{eqnarray}J_{\sigma}\ll \left(\left(\frac{\tau}{X}+1\right)\delta^{-4}\right)^{\frac{\sigma-\frac{1}{2}}{\frac{1}{2}+\delta}} \left(\tau^{2c}(\tau+X)\log X\right)^{\frac{1+\delta-\sigma}{\frac{1}{2}+\delta}}.\end{eqnarray}$
$\begin{eqnarray}e^{-\frac{t}{\tau}}\int_{1}^{T}|f_X(\sigma+it)|^2dt\ll X^{\frac{1-2\sigma}{1+2\delta}}\tau^{\frac{4c(1+\delta-\sigma)}{1+2\delta}}(\tau+X)(\delta^{-4}+\log X).\end{eqnarray}$
To eliminate the exponential, we take $\tau=cT$, and we also take $\delta=\frac{c'}{\log(T+X)}$, since then $X^\delta,T^{\delta}\ll 1$. Therefore
$\begin{eqnarray}\int_{1}^{T}|f_X(\sigma+it)|^2dt\ll X^{-(2\sigma-1)}T^{4c(1-\sigma)}\log^4(T+X),\end{eqnarray}$