# The large sieve for primes

Let $\Lambda(n)$ be the von Mangoldt function, i.e., $\Lambda(n) = \log p$ for $n$ a prime power $p^k$ and $\Lambda(n) = 0$ for all $n$ that not prime powers. Let

$$S(\alpha) = \sum_{n \leq N} \Lambda(n) e(\alpha n).$$

Now, using, say, Lemma 7.15 in Iwaniec-Kowalski (or the same result in Montgomery), we get

$$\sum_{q \leq q_0} \sum_{a \pmod{q}: \gcd(a,q)=1} \lvert S(a/q)\rvert^2 \leq \frac{(N + Q^2) N \log N}{\sum_{\substack{q\leq Q \text{ squarefree} \\ \gcd(q,P(q_0))=1}} \phi(q)^{-1}},$$

where $Q$ is arbitrary and $P(z):=\prod_{p \leq z} p$.

In practice, we would choose $Q$ slightly smaller than $\sqrt{N}$, and obtain

$$\sum_{q \leq q_0} \sum_{\substack{a \pmod{q} \\ \gcd(a,q)=1}} \lvert S(a/q) \rvert^2 \leq (1+\epsilon) 2 e^\gamma N^2 \log q_0,$$

where gamma is Euler's constant $0.577\cdots$ and $\epsilon$ is very small.

Now, the 2 in the bound $\leq (1+\epsilon) 2 e^\gamma N^2$ is due to the parity problem, and thus should be next to impossible to remove (except for very small $q_0$). However, the factor of $e^\gamma$ clearly has no right to exist. The true asymptotic should be simply $N^2 \log q_0$.

Can we remove that nasty $e^\gamma$? That is, can you prove a bound of type

$$\sum_{q \leq q_0} \sum_{\substack{a \pmod{q} \\ \gcd(a,q)=1}} \lvert S(a/q)\rvert^2 \leq (1+\epsilon) 2 N^2 \log q_0 ?$$

Harald

-