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



The large sieve for primes
Heh, I think I know why you are interested in this question, Harald, as Ben and I thought about essentially the same problem for what I suspect to be the same reason :-)


Anyway, we were able to get rid of the e^gamma factor. One way to proceed is to work not with the exponential sums, but rather the inner product of Lambda with Dirichlet characters. Using a Selberg sieve majorant (the same one used to prove, say, the Brun-Titschmarsh inequality) and the TT^\* method, one gets a nice l^2 bound on these inner products (losing only the 2 from the parity problem, or not even that if one deletes the principal character), and then one can do some Fourier analysis on finite groups to pass from Dirichlet characters back to exponentials. It helps a little bit to smooth the sum, but it's not too essential here. (See also my paper with Ben on the restriction theory of the Selberg sieve for some related results.)


Our argument isn't written up (or checked, for that matter) yet, but we can talk more if you want to know more details.


