# Least prime in an arithmetic progression and the Selberg sieve

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.

-
What is $\tau$ in the last formula? Is it the "number of divisors" function? –  i707107 May 9 '13 at 20:06
Yes, $\tau(n)$ is the number of divisors of $n$. –  GH from MO May 9 '13 at 20:13
GH, you should signal this to Iwaniec and Kowalski, in case they make a second edition of their book. –  Joël May 12 '13 at 16:23
@Joël: I agree, but I am not an expert in sieve theory to decide if this is a gap only (i.e. lack of detail), or an error to fix. The book is more of a monograph than a textbook, so naturally the arguments are sometimes dense or a bit sketchy. At any rate, Iwaniec-Kowalski do make a note to the extent that other upper sieves would work for the proof as well. –  GH from MO May 12 '13 at 17:34
@GH: The proof in Iwaniec-Kowalski is in fact wrong (see edited response below) but fixing it should be easy using the $\beta$ sieve, exactly in the way you mention. There is an approach using the Selberg sieve too (one would have to put $\theta_b=S^{-1}\cdot (\mu(b)b/\tau_8(b))\sum_{k\le y,\ b|k}\tau_8(k)/\prod_{p|k}(p-8)$, where $S$ is an appropriate normalizing factor) but I find that working with the Selberg sieve is more complicated in this case. –  Dimitris Koukoulopoulos May 13 '13 at 18:56

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). Opening $\nu(m)^2$ using GH's notation, 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$. Writing $\sigma_m=\sum_{[d_1,d_2]=m}\theta_{d_1}\theta_{d_2}$, we find that $$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}(p/g(p)-1)$ so that $m/g(m)=\sum_{n|m}f(n)$, we deduce that $$S/P(x)\approx \sum_{P^+(n)\le x}f(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} \textbf{1}_{(n,q)=1}$$ (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) h(n)g(n)^2}{\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) if $|a(d)|\le A$ for all $d\le D$ and $g(d)$ is multiplicative with $$\prod_{w\le p\le z} (1-g(p)/p)^{-1} \le \left(\frac{\log z}{\log w}\right)^8\left(1+\frac{K}{\log w}\right),$$ then $$\sum_{d\le D} \frac{\lambda(d)a(d)g(d)}{d} = \sum_{P^+(d)\le y} \frac{\mu(d) a(d) g(d)}{d} + O_K\left( Ae^{-u}\prod_{p\le y}\left(1-\frac{g(p)}{p}\right) \right),$$ where $u=\log D/\log y$.

We have that $$S = \sum_{d\le D} \frac{\lambda(d)\tau(d)^3 a(d)}{d},$$ where $$a(d) = \sum_{m\le x/d} \frac{\tau(dm)^3}{\tau(d)^3m} \ll(\log x)^8$$ for $d\le x$. So

\begin{align*} S = \sum_{d\le D} \frac{\lambda(d)\tau(d)^3 a(d)}{d} &= \sum_{P^+(d)\le y} \frac{\mu(d)\tau(d)^3 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*}

where the second equality follows by M\"obius inversion.

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.

-
@Dimitris: Thanks for your valuable response, but I think it does not answer my question if you read it carefully. The bounds (18.70) and (18.75) in Iwaniec-Kowalski are not about the sieve weights you talk about (e.g. Brun's), nor about a characteristic function of integers composed with primes $>y$, but about Selberg's sieve weights. The $\nu(n)$'s are defined in a very specific manner, and I would need a rigorous proof for them. On the other hand, the strong property you mention for the upper and lower $\beta$-sieves are very interesting, where can I read more about this (with proof)? –  GH from MO May 10 '13 at 23:34
@Dimitris: Please reflect on the "Added" section in my original post. Thank you! –  GH from MO May 11 '13 at 10:27
@GH: I don't know of any place that this strong statement appears. However, it's proof is only epsilon harder than the regular proof of the $\beta$ sieve. See, for example, Opera de Cribro or (for a simple, self-contained proof) the article "On Bombieri's asymptotic sieve" by Friedlander and Iwaniec (Lemma 3, p. 732, on this paper). –  Dimitris Koukoulopoulos May 13 '13 at 19:01
@GH: In fact, the proof given in Iwaniec-Kowalski is sufficient. The starting point is the observation that $\sum_{d\le D}\lambda(d)g(d)a(d)/d - \sum_{P^+(d)\le y}\lambda(d)g(d)a(d)/d \ll A \sum_{n\ge 1} V_n(z)$, where $V_n(z)$ are defined by (6.31) in IK. (the notation differs slightly: they use $g(d)$ for what is here $g(d)/d$). –  Dimitris Koukoulopoulos May 13 '13 at 19:51
@Dimitris: Thanks for all the work and insight you put into this post and comments. It will take me some time to digest all of it (I am no sieve expert), but I accept it right now as a very satisfactory answer. –  GH from MO May 14 '13 at 15:48