Sunday, January 11, 2015

Harman's sieve

In this post, we will derive Harman's sieve, which enables one to show that a sparse set $A$ contains the expected proportion of primes compared to a bigger set $B$ (which is usually $[\frac{x}{2},x]$), provided that one can relate linear and bilinear sums over $A$ and $B$ in suitable ranges with a sufficiently small error term. The linear sums are called type I sums, and the bilinear sums are type II sums. As an application of the method, we show that given any irrational $\xi$ and real $\kappa$, there are infinitely many primes $p$ such that $\|\xi p+\kappa\|<p^{-\frac{1}{4}}\log^{C} p$ holds, where $\|\cdot\|$ stands for the distance to the nearest integer. We already showed in this post on prime exponential sums that the fractional parts of $\xi p$ are uniformly distributed, but this result gives even more uniformity. We follow Harman's book Prime Detecting Sieves.
Two tools

Like many combinatorial sieves, Harman's sieve relies on applications of Buchstab's identity for the sifting function $S(A,P,z)$ (recall that $A\subset \mathbb{Z}_+$ is finite, $P\subset \mathbb{P}$ and $S(A,P,z)$ counts the elements of $A$ coprime to $P(z)$, which is the product of the primes in $P\cap [2,z)$) The simple but yet useful identity is stated as follows.

Lemma 1 (Buchstab's identity). Let $z_1$ and $z$ be parameters with $1\leq z_1<z$. Then
$\begin{eqnarray}S(A,P,z)=S(A,P,z_1)-\sum_{z_1\leq p<z}S(A_p,P,p),\end{eqnarray}$
where, as usual, $A_d=\{a\in A:a\equiv 0\pmod d\}$.

Proof. Let $a$ be an element of $A$ counted by $S(A,P,z_1)$ but not by $S(A,P,z)$. Let $q\in [z_1,z)$ be the smallest prime factor of $a$. Now $a$ is counted by $S(A_q,P,q)$ but not by any other $S(A_p,P,p)$ where $p\in [z_1,z)$. This completes the proof. ■

We can iterate Buchstab's identity as many times as we please, and for example the second iteration gives
$\begin{eqnarray}S(A,P,z)=S(A,P,z_1)-\sum_{z_1\leq p<z}S(A_p,P,z_1)+\sum_{z_1\leq p_1<p_2<z}S(A_{p_1p_2},P,p_2).\quad (1)\end{eqnarray}$
We see from this that Buchstab's identity is essentially just the principle of inclusion and exclusion. Its usefulness arises from the fact that it connects $S(A,P,z)$ to the expressions involving smaller sifting parameters. In addition, with $z_1=1$, formula $(1)$ tells that good upper bounds for $S(A_p,P,p)$ imply a lower bound for $S(A,P,z)$. This enables developing a lower bound counterpart of Selberg's sieve. However, for the current purposes, Buchstab's identity allows us to forge new variables in a sum such that they belong to a suitable interval, as required for type II sums.

Another tool required for Harman's sieve is what is called a ''cosmetic surgery'' in his book. What it says is that in a reasonable sum, we may remove a cross-condition $m<n$ between two variables at the cost of multiplying the sum by $\log N$, where $n$ is bounded by $N$. Another price we have to pay is that the $m$-dependence of the coefficients of the sum is altered but, importantly, the absolute values remain unchanged. In a bilinear sum, we pay no attention to the exact form of the coefficients, so for them this operation costs next to nothing. The removal of cross-conditions is based on the following complicated but advantageous way of expressing the condition $a<b$ between two real numbers analytically. This result was already used in this post to find a form of the large sieve useful for proving the Bombieri-Vinogradov theorem.

Lemma 2. For positive numbers $a$ and $b$ and for $T>0$, we have
$\begin{eqnarray}\frac{1}{\pi}\int_{-T}^{T}e^{iat}\frac{\sin bt}{t}dt=\begin{cases}1+O\left(\frac{1}{T|a-b|}\right),\quad b>a\\\frac{1}{2},\quad\quad \quad \quad \quad \quad\quad a=b\\O\left(\frac{1}{T|a-b|}\right),\quad \quad \quad a>b.\end{cases}\end{eqnarray}$
Proof. The Fourier transform of $1_{[-b,b]}(x)$ is $\frac{\sin(2\pi b\xi)}{\pi \xi}$ for $b>0$. Taking the inverse Fourier transform yields
$\begin{eqnarray}\frac{1}{\pi}\int_{-\infty}^{\infty}e^{iat}\frac{\sin bt}{t}dt=1_{(-b,b)}(a)-\frac{1}{2}1_{\{-b,b\}}(a),\end{eqnarray}$
because at points of discontinuity the Fourier transform is the average of the two limits. The error when the integral is truncated from $-T$ and $T$ can be estimated by partial integration; it is
$\begin{eqnarray}\ll \left|\int_{T}^{\infty}\frac{e^{i(a+b)t}}{t}dt\right|+\left|\int_{T}^{\infty}\frac{e^{i(a-b)t}}{t}dt\right|\ll \frac{1}{|a+b|T}+\frac{1}{|a-b|T},\end{eqnarray}$
as wanted. ■

We illustrate how the formula can be applied. Consider a bilinear sum
$\begin{eqnarray}S=\sum_{\substack{mn\in S_1\\n\in S_2\\m<n}}a_mb_nf(mn),\quad |a_n|,|b_n|\leq \tau(n), |f(n)|\leq 1;\end{eqnarray}$
the exact form of the sum is not important, so we could have a much more general sum than above. Usually $f$ is an oscillating function, such as an exponential. Say that the elements in $S_1\subset \mathbb{Z}_+$ are bounded by $M$. We take $a=\log m,b=\log(n-\frac{1}{2})$ in Lemma 2. Since $\log(n-\frac{1}{2})-\log m\geq \log\frac{n-\frac{1}{2}}{n-1}\gg \frac{1}{M}$, we get
$\begin{eqnarray}S&=&\frac{1}{\pi}\int_{-T}^{T}\sum_{\substack{mn\in S_1\\n\in S_2}}a_mb_ne^{i(\log m)t}f(mn)\frac{\sin(\log(n-\frac{1}{2})t)}{t}dt\\&+&O\left(\frac{M}{T}\sum_{mn\in S_1\atop n\in S_2}|a_mb_nf(mn)|\right)\\&=&\frac{1}{\pi}\left(\int_{[-T,-\frac{1}{T}]\cup [-\frac{1}{T},T]}+\int_{[-\frac{1}{T},\frac{1}{T}]}\right)\sum_{\substack{mn\in S_1\\ n\in S_2}}a_mm^{it}b_nf(mn)\frac{\sin(\log(n-\frac{1}{2})t)}{t}dt\\&+&O\left(\frac{M^4}{T}\right).\end{eqnarray}$
For the first integral, we apply $|\sin x|\leq 1$ to find that it contributes
$\begin{eqnarray}\ll (\log T)\max_{|t|\leq T}\left|\sum_{\substack{mn\in S_1\\n\in S_2}}a_mm^{it}b_nf(mn)\right|.\end{eqnarray}$
The second integral can be estimated using $|\sin x|\leq |x|;$ the result is
$\begin{eqnarray}\ll \frac{\log M}{T}\max_{|t|\leq T}\left|\sum_{\substack{mn\in S_1\\n\in S_2}}a_mm^{it}b_nf(mn)\right|.\end{eqnarray}$
Finally set $T=M^4$ to see that
$\begin{eqnarray}S\ll 1+\log M\left|\sum_{\substack{m\in S_1\\ n \in S_2}}a_m^{*}b_nf(mn)\right|,\end{eqnarray}$
where $a_m^{*}=a_mm^{it_0}$ for a suitable $t_0\in [-T,T]$. What matters is that $|a_m^{*}|=|a_m|$, so that the sum is still of the same form.

Harman's sieve

Theorem 3 (Harman's sieve). Let $A,B\subset [1,x]$ be finite sets of positive integers. Suppose that for any sequences $a_n,b_n$ of complex numbers such that $|a_n|,|b_n|\leq \tau(n)$, the following hold:
$\begin{eqnarray}(i)\quad \sum_{m\leq M\atop mn\in A}a_m&=&\lambda\sum_{m\leq M\atop mn\in B}a_m+O(Y),\\(ii)\quad \sum_{x^{\alpha}<m<x^{\alpha+\beta}\atop mn\in A}a_mb_n&=&\lambda\sum_{x^{\alpha}<m<x^{\alpha+\beta}\atop mn\in B}a_mb_n+O(Y)\end{eqnarray}$
for some $\lambda,Y,\alpha,\beta>0$ and $\beta\leq \frac{1}{2}$. Let $c_r$ be complex numbers with $|c_r|\leq 1$. Also suppose $M>x^{\alpha}$ and $2R<\min\{M,x^{1-\alpha}\}$, and further $M>x^{1-\alpha}$ if $2R>x^{\alpha+\beta}$. Then we have
$\begin{eqnarray}\sum_{r\sim R}c_rS(A_r,\mathbb{P},x^{\beta})=\lambda \sum_{r\sim R}c_rS(B_r,\mathbb{P},x^{\beta})+O(Y\log^3 x),\end{eqnarray}$
where $r\sim R$ means $R\leq r<2R$. In particular, taking $R=1, c_1=1$,
$\begin{eqnarray}S(A,\mathbb{P},x^{\beta})=\lambda S(A,\mathbb{P},x^{\beta})+O(Y\log^3 x).\end{eqnarray}$

Note that the sieve is a kind of comparison principle: with suitable estimates for type I and type II sums, a set $A\subset B$ contains the expected proportion of primes compared to $B$. Usually $A$ is a sparse set and $B$ is a large set, where we know how many primes there approximately are -- say $B=\{\frac{x}{2}\leq n\leq x\}$. As everything is comparative, the prime number theorem is not needed in the proof, and the only required analysis result comes from Lemma 2.

The role of the parameter $\beta$ is to measure the ''width'' of the region where type II sums can be bounded. The value of $\beta$ reflects to $S(A,\mathbb{P},x^{\beta})$, so that in particular in the case $\beta=\frac{1}{2}$ we are counting primes. The role of $\alpha$ is that we cannot estimate short type II sums well (as will be seen), so $\alpha$ and $1-\alpha$ should not be too small. The reason for considering $\sum_{r\sim R}c_rS(A_r,\mathbb{P},x^{\beta})$ instead of merely $R=1$ is that such sums arise in Buchstab's identity. Therefore, sometimes when not all the necessary type II information is directly available, bounds for these sums may compensate it.

Proof of Theorem 3. First assume $R<x^{\alpha}$. We may also assume $x^{\beta}\geq 2$. We write
$\begin{eqnarray}\sum_{r\sim R}c_rS(A_r,\mathbb{P},x^{\beta})=\sum_{r\sim R}c_r\sum_{rn\in A\atop (n,P(x^{\beta}))=1}1.\end{eqnarray}$
By Buchstab's identity, this equals
$\begin{eqnarray}&&\sum_{r\sim R}\left(c_r|A_r|-c_r\sum_{\substack{p_1rn\in A\\ (n,P(p_1))=1\\ p_1<x^{\beta}}}1\right)\\&=&\sum_{r\sim R\atop rn\in A}c_r-\sum_{r\sim R}c_r\sum_{\substack{p_1rn\in A\\ (n,P(p_1))=1\\ p_1<x^{\beta}}}1\quad \quad (2)\end{eqnarray}$
We apply Buchstab's identity again to the latter sum in $(2)$, and see that contributes
$\begin{eqnarray}-\sum_{r\sim R}c_r\sum_{\substack{p_1rn\in A\\ p_1<x^{\beta}}}1+\sum_{r\sim R}c_r\sum_{\substack{p_1p_2rn\in A\\ (n,P(p_2))=1\\ p_2<p_1<x^{\beta}}}1.\end{eqnarray}$
In general, when iterating Buchstab's identity as many times as possible, we arrive at the formula
$\begin{eqnarray}\sum_{r\sim R}c_rS(A_r,\mathbb{P},x^{\beta})=\sum_{t\geq 0}(-1)^tS_t;\end{eqnarray}$
$\begin{eqnarray}S_t:=\sum_{r\sim R}c_r\sum_{\substack{p_1...p_trn\in A\\p_t<...<p_1<x^{\beta}}}1,\end{eqnarray}$
because eventually the condition $(n,P(p_t))=1$ disappears. The total number of sums is $\ll \frac{\log x}{\log \log x}$, as any number up to $x$ has at most this many prime factors. Denote by $S_t'$ the contribution of the terms in $S_t$ with $p_1...p_tr\leq M$. This is a type I sum, and equals
$\begin{eqnarray}S_t'=\sum_{k\leq M\atop kn\in A}\sum_{\substack{k=p_1...p_tr\\ p_t<...<p_1<x^{\beta}\\r\sim R}} c_r=\lambda\sum_{k\leq M\atop kn\in B}\sum_{\substack{k=p_1...p_tr\\ p_t<...<p_1<x^{\beta}\\r\sim R}} c_r+O(Y),\end{eqnarray}$
because
$\begin{eqnarray}a_k:=\sum_{\substack{k=p_1...p_tr\\ p_t<...<p_1<x^{\beta}\\r\sim R}} c_r\end{eqnarray}$
satisfies $|a_k|\leq \tau(k)$. This is seen by noticing that for any $r\mid k$, the primes $p_1<...<p_t$ are determined at most uniquely by the fundamental theorem of arithmetic.

Consider now the contribution of the terms in $S_t$ with $p_1...p_tr>M$; call it $S_t''$. As $M>x^{\alpha}$ and $p_i<x^{\beta}$ and $r<2R<2x^{\alpha}\leq x^{\alpha+\beta}$, for any tuple $(p_1,...,p_t)$, there is a $j$ such that $p_1...p_jr\in (x^{\alpha},x^{\alpha+\beta}).$ This implies
$\begin{eqnarray}|S_t''|\leq \sum_{x^{\alpha}<k<x^{\alpha+\beta}\atop km\in A}\sum_{\substack{k=p_1...p_jr\\p_j<...<p_1<x^{\beta}\\r\sim R\\p_1...p_tr\geq M\\j\leq t}}|c_r|\sum_{\substack{m=p_{j+1}...p_tn\\ p_t<...<p_{j+1}<p_j\\ j<t}}1.\end{eqnarray}$
This is otherwise a bilinear sum, but there are two cross-conditions: $p_{j+1}<p_j$ and $p_1...p_tr\geq M$. However, Lemma 2 tells that they can be discarded at the cost of a factor of $\log^2 x$ in error terms. The sequences
$\begin{eqnarray}a_k:=\sum_{\substack{k=p_1...p_jr\\p_j<...<p_t<x^{\beta}\\r\sim R\\j\leq t}}|c_r|,\quad b_m:=\sum_{\substack{m=p_{j+1}...p_tn\\ p_t<...<p_{j+1}<x^{\beta}\\ j<t}}1\end{eqnarray}$
satisfy $|a_k|,|b_k|\leq \tau(k)$, because for a given $r\mid k$, the primes $p_i$ are at most uniquely determined from $\frac{k}{r}=p_1...p_j$ by the fundamental theorem of arithmetic, and similarly for the other sequence.

Now we have a type II sum disregarding the two cross-conditions, so
$\begin{eqnarray}S_t''=\lambda\sum_{x^{\alpha}<k<x^{\alpha+\beta}\atop km\in B}\sum_{\substack{k=p_1...p_jr\\p_j<...<p_1<x^{\beta}\\r\sim R\\ p_1...p_tr\geq M}}c_r\sum_{m=p_{j+1}...p_tn\atop p_t<...<p_{j+1}<p_j}1+O(Y\log^2 x).\end{eqnarray}$

In conclusion, each $S_t$ equals $\lambda \Sigma_t+O(Y\log^2 x)$, where $\Sigma_t$ is the same sum as $S_t$ but $A$ replaced by $B$. As there are $\ll \frac{\log x}{\log \log x}$ sums, the total error is $O(Y\log^3 x).$ This means
$\begin{eqnarray}\sum_{r\sim R}c_rS(A,\mathbb{P},x^{\beta})=\lambda\sum_{t\geq 0}(-1)^t \Sigma_t+O(Y\log^3 x)=\sum_{r\sim R}c_rS(B,\mathbb{P},x^{\beta})+O(Y\log^3 x),\end{eqnarray}$
as desired.

Next we assume $x^{\alpha}<R\leq \frac{1}{2}x^{\alpha+\beta}$. In this case, we may simply calculate
$\begin{eqnarray}\sum_{r\sim R}c_rS(A_r,\mathbb{P},x^{\beta})=\sum_{r\sim R}c_r\sum_{rn\in A\atop (n,P(x^{\beta}))=1}1=\sum_{r\sim R\atop rn\in A}c_r1_{(\cdot,P(x^{\beta}))=1}(n).\end{eqnarray}$
This is a type II sum, with coefficients bounded by $1$, so it equals
$\begin{eqnarray}\lambda \sum_{r\sim R\atop rn\in B}c_r1_{(\cdot,P(x^{\beta}))=1}(n)=\lambda \sum_{r\sim R}c_rS(B_r,\mathbb{P},x^{\beta})+O(Y).\end{eqnarray}$
The last case is $2R>x^{\alpha+\beta}$. Now in the sums with $p_1...p_tr>M$, the condition $p_1...p_trn\in A$ implies $n<\frac{x}{M}\leq x^{\alpha}$. Hence the same argument as in the first case works, with $r$ and $n$ interchanged. ■

Distribution of $\xi p$ modulo $1$

We apply Harman's sieve to the distribution of $\xi p$ modulo $1$, where $\xi$ is irrational. We will prove the following.

Theorem 4. Let $\xi$ be irrational and $\kappa\in \mathbb{R}$. There exists an unbounded sequence of numbers $x$ such that
$\begin{eqnarray}\left\{n\in \left[\frac{x}{2},x\right]:\|\xi n+\kappa\|\leq \delta\right\}=2\delta(1+o(1))\left(\pi(x)-\pi\left(\frac{x}{2}\right)\right)\end{eqnarray}$
where $\delta=x^{-\frac{1}{4}}\log^{28}x.$ In particular, there exist infinitely many primes $p$ such that $\|\xi p+\kappa\|<p^{-\frac{1}{4}}\log^{28} p.$

The exact power of the logarithm is not very important here; one could even prove a much better exponent. The best known exponent is $\frac{1}{3}-\varepsilon$, proved by Matomäki. Theorem 3 could also be proved using Vaughan's identity, but its proof using Harman's sieve allows improving the exponent $\frac{1}{4}$ with some modifications in the argument. Before we can prove Theorem 3, we need a finite Fourier expansion for the characteristic function $1_{\|\cdot \|\leq \delta}$.

Lemma 5. Let $0\leq \delta< \frac{1}{4}$ and $L\in \mathbb{Z_+}$, $\frac{1}{L}<\delta$. Then there exist two sequences $c_\ell^{+},c_{\ell}^{-}$ of complex numbers such that
$\begin{eqnarray}2\delta-\frac{2}{L}+\sum_{0<|\ell|\leq L^2}c_{\ell}^{-}e(\ell a)\leq 1_{\|\cdot\|\leq \delta}(a)\leq 2\delta-\frac{2}{L}+\sum_{0<|\ell|\leq L^2}c_{\ell}^{+}e(\ell a)\end{eqnarray}$
with
$\begin{eqnarray}|c_{\ell}^{\pm}|\ll \min\left\{\delta,\frac{1}{\ell}\right\}.\end{eqnarray}$

Proof. For a proof, see Chapter 1 of Vinogradov's Method of Trigonometrical sums in the Theory of Numbers. ■

Lemma 6 (Type I and II exponential sums). Let $a_m,b_n$ be complex numbers. Write $\xi=\frac{a}{q}+\frac{c}{q^2}, |c|\leq 1, (a,q)=1$. Then we have
$\begin{eqnarray}&&\sum_{m\leq M\atop mn\sim N}a_me(\xi mn)\ll \max_{m\leq M}|a_m|\sum_{m\leq M}\min\left\{\frac{N}{m},\frac{1}{\|\alpha m\|}\right\}\\&\ll&\max_{m\leq M}|a_m|\left(\frac{N}{q}+M+q\right)\log(MNq),\quad(3)\\&&\sum_{m\sim M}\left|\sum_{n\sim N\atop mn\sim x}a_mb_ne(\xi m n)\right|\ll \left(\sum_{m\sim M}|a_m|^2\sum_{n\sim N}|b_n|^2\right)^{\frac{1}{2}}\left(\frac{x}{q}+\frac{x}{N}+q+N\right)^{\frac{1}{2}}(\log qx)^{\frac{1}{2}},\,(4)\end{eqnarray}$
for any $M,N,x\geq 2$.

Proof. The first inequality in $(3)$ follows just by summing a geometric series over $n$, and the second was proved in this post on prime exponential sums and Vaughan's identity. The inequality $(4)$ was also essentially proved in that post, but we repeat the argument, as we had specific coefficients there. By Cauchy-Schwarz, the left-hand side of $(4)$ is
$\begin{eqnarray}\ll \left(\sum_{m\sim M}|a_m|^2\right)^{\frac{1}{2}}\left(\sum_{m\sim M}\left|\sum_{n\sim N\atop mn\sim x}b_ne(\xi mn)\right|^2\right)^{\frac{1}{2}}\end{eqnarray}$
When the latter sum is multiplied out, it becomes
$\begin{eqnarray}M\sum_{n_1,n_2\sim N\atop mn_1,mn_2\sim x}b_{n_1}\overline{b_{n_2}}+\sum_{\substack{n_1,n_2\sim N\\ mn_1,mn_2\sim x\\n_1\neq n_2}}b_{n_1}\overline{b_{n_2}}\sum_{m\sim M}e(\xi m(n_1-n_2))\quad (5)\end{eqnarray}$
Using $|b_{n_1}\overline{b_{n_2}}|\leq \frac{1}{2}(|b_{n_1}|^2+|b_{n_2}|^2)$, $(5)$ is at most
$\begin{eqnarray}&\ll& \left(\sum_{n_1\sim N}|b_n|^2\right)\left(M+\max_{n_1\sim N}\sum_{n_2\sim N\atop n_2\neq n_1}\sum_{m\sim M}e(\xi m(n_1-n_2))\right)\\&\ll& \left(\sum_{n_1\sim N}|b_n|^2\right)\left(M+\max_{n_1\sim N}\sum_{n_2\sim N}\min\left\{M,\frac{1}{\|\xi(n_1-n_2)\|}\right\}\right)\\&\ll& \left(\sum_{n_1\sim N}|b_n|^2\right)\left(M+\max_{n_1\sim N}\sum_{n_2\sim N}\min\left\{\frac{MN}{|n_1-n_2|},\frac{1}{\|\xi(n_1-n_2)\|}\right\}\right)\\&\ll& \left(\sum_{n_1\sim N}|b_n|^2\right)\left(\frac{MN}{q}+M+q+N\right)\log(qMN).\end{eqnarray}$
Taking into account that $MN\ll x$, we obtain the desired inequality. ■

We are now ready to prove Theorem 4.

Proof of Theorem 4. Define $\delta=x^{-\frac{1}{4}}\log^{28} x$, $A=\{n\in [\frac{x}{2},x):\|\xi n+\kappa\|\}\leq \delta\}$ and $B=[\frac{x}{2},x)\cap \mathbb{Z}$. We shall establish the type I and II estimates required by Harman's sieve to compare the number of primes in $A$ and $B$. For any $a_m$ with $|a_m|\leq \tau(m)$, Lemma 5 with the choice $L=x$ gives
$\begin{eqnarray}\sum_{\substack{m\leq M\\mn\sim\frac{x}{2}\\ \|\xi m n+\kappa\|\leq \delta}}a_m=2\delta\sum_{m\leq M\atop mn\sim \frac{x}{2}}a_m+O(1)+O\left(\left|\sum_{0<|\ell|\leq x^2}c_{\ell}\sum_{m\leq M\atop mn\sim\frac{x}{2}}a_me(\ell(\xi mn+\kappa))\right|\right),\quad (6)\end{eqnarray}$
where $c_{\ell}\ll\min\left\{\delta,\frac{1}{\ell}\right\}$. Clearly we may assume $\ell>0$ in the summation above. Consider first the contribution of the terms with $\ell\leq \delta^{-1}$ and $m\sim M$ into the error term. Summing a geometric series, the contribution is
$\begin{eqnarray}&\ll& \delta \max_{m\leq M}|a_m|\sum_{0<\ell\leq \delta^{-1}}\sum_{m\sim M}\min\left\{\frac{x}{m},\frac{1}{\|\xi \ell m\|}\right\}\\&\ll& \delta \sum_{k\leq M\delta^{-1}}\tau(k)\min\left\{\frac{x}{M},\frac{1}{\|\xi k\|}\right\}\\&\ll& \delta (M\delta^{-1})^{\varepsilon}\sum_{k\leq M\delta^{-1}}\min\left\{\frac{x\delta^{-1}}{M\delta^{-1}},\frac{1}{\|\xi k\|}\right\}.\end{eqnarray}$

The last sum is by Lemma 6
$\begin{eqnarray}\ll \delta (M\delta^{-1})^{\varepsilon}\left(\frac{x\delta^{-1}}{q}+M\delta^{-1}+q\right)\log(qM\delta^{-1}).\end{eqnarray}$
We assumed $m\sim M$, so we sum this over $M,\frac{M}{2},\frac{M}{4},...$. The outcome is
$\begin{eqnarray}\left|\sum_{0<|\ell|\leq \delta^{-1}}c_{\ell}\sum_{m\leq M\atop mn\sim\frac{x}{2}}a_me(\ell(\xi mn+\kappa))\right|\ll \delta (M\delta^{-1})^{\varepsilon}\left(\frac{x\delta^{-1}}{q}+M\delta^{-1}+q\right)\log(qM\delta^{-1}),\quad (7)\end{eqnarray}$
because the expression is almost linear in $M$. The expression is minimal, when $q$ is around $\sqrt{x\delta^{-1}M}$, so we choose $x$ such that $q=x^{\frac{2}{3}}$. Since there is an unbounded sequence of numbers $q$ such that $|\xi-\frac{a}{q}|<\frac{1}{q^2}$ there is also an unbounded sequence of such $x$. Now taking $M=x^{\frac{3}{4}-3\varepsilon}$, $(7)$ is bounded by
$\begin{eqnarray}\ll \delta x^{1-\varepsilon}.\end{eqnarray}$

We turn to the contribution from the terms with $\delta^{-1}<\ell\leq x^2$. For $\delta^{-1}\leq H\leq x^2$, the contribution of the terms $\ell \sim H$ is
$\begin{eqnarray}&\ll& \frac{1}{H}\sum_{\ell \leq H}\sum_{m\sim M}|a_m|\left|\sum_{mn\sim \frac{x}{2}}e(\xi \ell m n)\right|\\&\ll& \frac{1}{H}(HM)^{\varepsilon}\sum_{k\leq MH}\min\left\{\frac{xH}{MH},\frac{1}{\|\xi k\|}\right\}\\&\ll& \frac{1}{H}x^{\varepsilon}\left(\frac{xH}{q}+MH+q\right)\log(qMH).\end{eqnarray}$
This is maximal for $H=\delta^{-1}$, so the error term in $(6)$ is not greater than
$\begin{eqnarray}\delta x^{1-\varepsilon}\log x.\end{eqnarray}$

We are left with comparing type II sums. As before, taking $L=x$ in Lemma 5 gives
$\begin{eqnarray}&&\sum_{\substack{m\in (x^{\alpha},x^{\alpha+\beta})\\mn\sim\frac{x}{2}\\ \|\xi m n+\kappa\|\leq \delta}}a_mb_n=2\delta\sum_{m\in (x^{\alpha},x^{\alpha+\beta})\atop mn\sim \frac{x}{2}}a_mb_n+O(1)\\&+&O\left(\sum_{0<|\ell|\leq x}c_{\ell}\sum_{m\in (x^{\alpha},x^{\alpha+\beta})\atop mn\sim\frac{x}{2}}a_mb_ne(\ell(\xi mn+\kappa))\right),\quad (8)\end{eqnarray}$
Consider the terms in the error sum with $\ell \sim H,m\sim M',n\sim N$. We deal with the case $M'<N$; the other case is similar (but it is crucial to deal with them separately, as will be seen from the bound we obtain). An obstacle for estimating the error term in $(8)$ is that $m$ and $n$ have a cross-condition. In type I sums, this was overcome by summing first over $n$. Here we cannot do that, as we have the coefficients $b_n$. However, as we already have some coefficients depending $n$, it does no harm to alter them as long as $|b_n|$ stays the same. Therefore, we may apply Lemma 2 to get rid of the cross-condition. We find that the terms $\ell \sim H,m\sim M$ ($H\leq \delta^{-1},M'<x^{\frac{1}{2}}$) contribute
$\begin{eqnarray}\ll (\log x)\delta \sum_{\ell\sim H}\sum_{m\sim M'}\left|\sum_{n\sim \frac{x}{M}}a_m^{*}b_n^{*}e(\xi \ell m n)\right|,\end{eqnarray}$
where $|a_n{*}|=|a_n|,|b_n^{*}|=|b_n|.$ Letting $k=\ell m$ be a new variable, this becomes
$\begin{eqnarray}\ll (\log x)\delta \sum_{HM'\leq k<4HM'}A_k\left|\sum_{n\sim \frac{x}{M}}b_n^{*}e(\xi k n)\right|,\quad (9)\end{eqnarray}$
where
$\begin{eqnarray}A_k:=\sum_{\substack{k=m\ell\\ m\sim M'\\\ell \sim H}}|a_m^{*}|\leq\sum_{m\mid k}\tau(m)\leq \tau(k)^2.\end{eqnarray}$
Now Lemma 6 tells  together with the estimates
$\begin{eqnarray}\sum_{n\leq x}\tau(n)^2\ll x\log^3 x,\quad\sum_{n\leq x}\tau(n)^4\ll x\log^{15} x\end{eqnarray}$
(the first one was proved in this post and the second one is proved similarly) that $(9)$ is bounded by
$\begin{eqnarray}&\ll& \delta \sqrt{Hx}(\log^{9.5} x)\left(\frac{Hx}{q}+\frac{Hx}{\frac{x}{M'}}+q+\frac{x}{M'}\right)^{\frac{1}{2}}\\&\ll& \delta \sqrt{x\delta^{-1}}(\log^{9.5}x)\left(\frac{\delta^{-1}x}{q}+\delta^{-1}M'+q+\frac{x}{M'}\right)^{\frac{1}{2}}\\&\ll& x^{\frac{1}{2}}(\log x^{9.5})\left(\frac{x^{\frac{1}{2}}}{q^{\frac{1}{2}}}+(M')^{\frac{1}{2}}+\delta^{\frac{1}{2}}q^{\frac{1}{2}}+\delta^{\frac{1}{2}}\left(\frac{x}{M'}\right)^{\frac{1}{2}}\right)\\&=&x^{\frac{1}{2}}\log^{9.5} x\left(x^{\frac{1}{8}}+(M')^{\frac{1}{2}}+\delta^{\frac{1}{2}}\left(x^{\frac{1}{3}}+\left(\frac{x}{M'}\right)^{\frac{1}{2}}\right)\right)\quad (10)\end{eqnarray}$
since $H\leq \delta^{-1}, M'<x^{\frac{1}{2}},M'N\leq x$. If we take $\alpha=\frac{1}{4},\beta=\frac{1}{2}$, we have $x^{\frac{1}{4}}<M'<x^{\frac{1}{2}}$, so that $(10)$ is at most
$\begin{eqnarray}\ll x^{\frac{7}{8}}\delta^{\frac{1}{2}}=o\left(\delta\frac{x}{\log^5 x}\right).\end{eqnarray}$
The terms with $\delta^{-1}<\ell\leq x^2$ contribute at most $\log x$ times the same bound, which is seen similarly as for type I sums. Thus the total error term is
$\begin{eqnarray}o\left(\delta\frac{x}{\log^4 x}\right)+\delta x^{1-\varepsilon}\log x.\end{eqnarray}$
Taking for example $\varepsilon=0.1$, we have $M>x^{\frac{1}{4}}$ in type I sums, so Harman's sieve gives $S(A,\mathbb{P},x)= (1+o(1))\cdot 2\delta \left(\pi(x)-\pi(\frac{x}{2})\right)$, which finishes the proof. ■