My question concerns a technical step in the proof of Linnik's theorem on the least prime in an arithmetic progression, as presented in Chapter 18 of Iwaniec-Kowalski: Analytic number theory. 


The proof uses certain weights $\theta\_b$ coming from the theory of the Selberg sieve. The sequence is supported on square-free numbers up to $y$ coprime with $q$ (the modulus of the arithmetic progression), and its main feature is, cf. (18.19)-(18.23) in the book,
$$ |\theta\_b|\leq 1,\qquad \theta\_1=1, $$
$$ 0<\sum\_{b\_1,b\_2}\frac{\theta\_{b\_1}\theta\_{b\_2}}{[b\_1,b\_2]}\leq\frac{q}{\varphi(q)\log y}. $$
The corresponding Selberg upper sieve coefficients are defined by
$$ \sigma\_m:=\sum\_{[b\_1,b\_2]=m}\theta\_{b\_1}\theta\_{b\_2}, $$
so that with the notation
$$ \nu(n):=\sum\_{b\mid n}\theta\_b $$
we have for any integer $n\geq 1$
$$ \sum\_{m\mid n}\sigma\_m=\nu(n)^2\geq\sum\_{m\mid n}\mu(m). $$


By (18.70) of the book we have, "applying a sieve of dimension 8 (see the Fundamental Lemma 6.3)",
$$ \sum\_{n\leq x}\nu^2(n)\frac{\tau^3(n)}{n}\ll\left(\frac{\log x}{\log y}\right)^8. $$
Here $\tau(n)$ is the number of divisors of $n$.
Can anyone help me understand why this is true? The quoted lemma is about Brun's sieve (where $\sigma\_m$ would be $\mu(m)$ restricted to certain integers), but even if I accept it for the Selberg sieve, I do not see the stated bound. Similarly, I do not understand why (18.75) in the book is true.


**Added.** Based on the expert response of Dimitris Koukoulopoulos I think that the proof of Linnik's theorem, as presented in Iwaniec-Kowalski's book, works fine if we replace the Selberg sieve $\sigma\_m$ with an upper $\beta$-sieve $\beta\_m$. More precisely, we redefine $\nu(n)$ so that 
$$\nu(n)^2=\sum\_{m\mid n}\beta\_m,$$
which makes sense as the right hand side is nonnegative.



Least prime in an arithmetic progression and the Selberg sieve
The proof given in Iwaniec-Kowalski is, as it stands, wrong. It can be easily fixed, as I explain below. 


In general, one can think of $\nu(n)^2$ as the characteristic function of integers with $P^-(n):=\min(p|n)\ge y$. So
$$
\sum\_{n\le x} \frac{\nu(n)^2 f(n)}{n} \approx \sum\_{ n\le x,\ P^-(n)\ge y } \frac{f(n)}{n} \asymp \prod\_{y\le p\le x} \left(1+\frac{f(p)}{p}\right) 
$$
for any reasonable multiplicative function $f$ that is bounded on primes. However, an important restriction is that $f(p)<\kappa$ on average, where $\kappa$ is the sifting dimension. In this case the dimension is 1, whereas $f(p)=8$. So the sum in question, say $S$, does not satisfy a priori the claimed bound. In fact, in this case $S\gg(\log x/\log y)^8$:


If $P^+(n)=\max(p|n)$, then we have that
$$
S= \sum\_{n\le x}\frac{\nu(n)^2\tau(n)^3}{n} 
 \asymp \sum\_{P^+(n)\le x}\frac{\nu(n)^2\tau(n)^3}{n} 
$$
(this step is heuristic and employed for simplicity). If we let $\sigma\_m=\sum\_{[d\_1,d\_2]=m}\theta\_{d\_1}\theta\_{d\_2}$ and we open $\nu(m)^2$, we have that
$$
S \approx \sum\_{P^+(m)\le x} \sigma\_m \sum\_{P^+(n)\le x,\ m|n} \frac{\tau(n)^3}{n} 
 = P(x) \sum\_{P^+(m)\le x} \frac{\sigma\_m g(m)}{m},
$$
where $g(m)$ is a multiplicative function with $g(p)=8+O(1/p)$ and $P(x)=\prod\_{p\le x}(1+\tau(p)^3/p+\tau(p^2)^3/p^2+\cdots)\asymp(\log x)^8$. Hence
$$
S/P(x)\approx \sum\_{P^+(d\_1d\_2)\le x} \frac{\theta\_{d\_1}\theta\_{d\_2}g([d\_1,d\_2])}{[d\_1,d\_2]}
= \sum\_{P^+(d\_1d\_2)\le x} \frac{\theta\_{d\_1}\theta\_{d\_2}g(d\_1)g(d\_2)}{d\_1d\_2} \frac{(d\_1,d\_2)}{g((d\_1,d\_2))}.
$$
Writing $f(m)=\prod\_{p|m}(1-g(p)/p)$ so that $m/g(m)=\sum\_{n|m}f(n)n/g(n)$, we deduce that
$$
S/P(x)\approx \sum\_{P^+(n)\le x}\frac{f(n)n}{g(n)} \left( \sum\_{P^+(d)\le x,\ n|d} \frac{\theta\_{d}g(d)}{d}\right)^2.
$$
When $y/2 \lt n\le y$, we have that
$$
\sum\_{P^+(d)\le x,\ n|d} \frac{\theta\_{d}g(d)}{d}
 = \frac{\theta\_n g(n)}{n} = \frac{\mu(n)g(n)}{G} \sum\_{k\le y,\ (k,q)=1,\ n|k} \frac{\mu^2(k)}{\phi(k)}
 = \frac{\mu(n)g(n)}{G} \cdot \frac{\textbf{1}\_{(n,q)=1}}{\phi(n)}
$$
(note that there is an error in the definition of $\theta\_b$ in Iwaniec-Kowalski, as one has to restrict them on those $b$ which are coprime to $q$. In fact, $\theta\_b=(\mu(b)b/G) \sum\_{k\le y,\ (k,q)=1,\ b|k}\mu^2(k)/\phi(k)$). So
$$
S \gtrsim \frac{P(x)}{G^2} \sum\_{y/2 \lt n\le y,\ (n,q)=1} \frac{\mu^2(n) f(n)g(n)n}{\phi(n)^2}
 \gg\_q (\log x)^8(\log y)^5,
$$
by the Selberg-Delange method. This is certainly bigger than what we would need.


In order to remedy this deficiency, one would have to choose $\nu(n)$ in another way, as weights from a sieve of dimension 8 or higher. The easiest choice to work with is, as GH also points out, is to define $\nu$ via the relation $\nu(n)^2=(1\*\lambda)(n)$, where $(\lambda(d):d\le D)$ is a $\beta$ upper bound sieve of level $y$ and dimension 8, so that
$$
S = \sum\_{n\le x} \frac{(1\*\lambda)(n)\tau(n)^3}{n}.
$$
The point is that the sequence $(\lambda(d))\_{d\le D}$ satisfies the Fundamental Lemma (Lemma 6.3 in Iwaniec-Kowalski) in the following strong sense:


(1) $\lambda(d)$ is supported on square-free integers with $P^+(d)\le y$


(2) whenever $\{a(d)\}\_{d\ge1}$ is a sequence such that
$$
\bigg|\sum\_{P^+(d)\le z}\frac{\mu(d)a(dm)}{d}\bigg|
\le Ag(m)\prod\_{y\_0\le p\le z}(1-g(p)/p)
\quad\text{when}\ P^-(m)>z,
$$ 
where $A\ge0$ and $y\_0\ge1$ are some parameters and $g\ge0$ is multiplicative with 
$$
\prod\_{w\le p\le w'} (1-g(p)/p)^{-1} \le \left(\frac{\log w'}{\log w}\right)^8\left(1+\frac{K}{\log w}\right)\qquad(w'\ge w\ge y\_0),
$$
we have
$$
\sum\_{d\le D} \frac{\lambda(d)a(d)}{d} = \sum\_{P^+(d)\le y} \frac{\mu(d)a(d)}{d}
+ O\_K\left( Ae^{-u}\prod\_{y\_0\le p\le y}\left(1-\frac{g(p)}{p}\right) \right),
$$
where $u=\log D/\log y$. 


Remark: if $a=g$, then the condition on $a$ holds trivially with $A=y\_0=1$. Hence, the above statement is indeed a generalization of the usual Fundamental Lemma.


We have that
$$
S = \sum\_{d\le D} \frac{\lambda(d)a(d)}{d},
$$
where 
$$
a(d) = \sum\_{m\le x/d} \frac{\tau(dm)^3}{m}.
$$
If $P^-(m)>z$, then
\begin{align\*}
\sum\_{P^+(d)\le z} \frac{\mu(d)a(dm)}{d}
&= \sum\_{P^+(d)\le z} \frac{\mu(d)}{d}\sum\_{k\le x/(dm)}\frac{\tau(dkm)^3}{k} \\
&= \sum\_{n\le x/m} \frac{\tau(nm)^3}{n} \sum\_{dk=n,\,P^+(d)\le z}\mu(d).
\end{align\*}
By M\"obius inversion, we then conclude that
\begin{align\*}
\sum\_{P^+(d)\le z} \frac{\mu(d)\tau(d)^3a(dm)}{d}
&= \sum\_{n\le x/m,\,P^-(n)>z} \frac{\tau(nm)^3}{n} \\
&\ll \tau(m)^3 (\log x/\log z)^8 \\
&\asymp (\log x)^8\tau(m)^3\prod\_{11\le p\le z}(1-\tau(p)^3/p),
\end{align\*}
so that the second axiom holds for $a$ with $A\asymp(\log x)^8$, $y\_0=11$ and $g=\tau^3$. We thus conclude that
\begin{align\*}
S = \sum\_{d\le D} \frac{\lambda(d)a(d)}{d} 
&= \sum\_{P^+(d)\le y} \frac{\mu(d)a(d)}{d} 
+ O\left( e^{-\log x/\log y} \left(\frac{\log x}{\log y}\right)^8\right) \newline
&= \sum\_{n\le x,\ P^-(n)>y} \frac{\tau(n)^3 }{n} 
+ O\left( e^{-\log x/\log y} \left(\frac{\log x}{\log y}\right)^8\right) \newline
&\ll \left(\frac{\log x}{\log y}\right)^8.
\end{align\*}


A more general remark: Selberg's sieve is not as flexible as the $\beta$-sieve as far as ``preliminary sieving'' is concerned because it carries inside it the sieve problem it is applied to, in contrast to the $\beta$-sieve weights that only depend on the sifting dimension via the $\beta$ parameter.


EDIT: the monotonicity principle II described in page 49 of "Opera de Cribro" by Friedlander-Iwaniec is a way to use Selberg's sieve weights for preliminary sieving. See also Proposition 7.2 in the same book.


