# 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<=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<=q_0} \sum_{a mod q: gcd(a,q)=1} |S(a/q)|^2 <= ((N + Q^2) N log N)/(\sum_{q<=Q squarefree: \gcd(q,P(q_0))=1} 1/phi(q)},

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

In practice, we would choose Q slightly smaller than sqrt(N), and obtain

\sum_{q<=q_0} \sum_{a mod q: gcd(a,q)=1} |S(a/q)|^2 <= (1+epsilon) 2 e^gamma N^2 log q_0,

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

Now, the 2 in the bound <= (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<=q_0} \sum_{a mod q: gcd(a,q)=1} |S(a/q)|^2 <= (1+epsilon) 2 N^2 log q_0 ?

Harald

-