# 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

-

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.

-
Out of curiosity, would it be possible to explain the general picture to people with no background in number theory? E.g. I understand why Dirichlet characters enter the picture, but what happens next? –  Ilya Nikokoshev Oct 19 '09 at 20:43
Aha, I see. You are using the fact that sums \sum_{n<=N} chi(m n + b) are always small (for chi non-principal, m non-zero), whereas \sum_{n<=N} e((mn+b)a/q) is not small if q divides m. This makes bookkeeping during proofs easier. Still, I am a little bit wary of using majorants in this context, as, numerically speaking, they will always introduce error terms and/or a factor that should be 2 but is really slightly larger than 2. Initially, I had an upper-bound sieve in a completely different part of the argument, and I was quite glad when I got rid of it. –  H A Helfgott Oct 20 '09 at 17:34
The same wariness goes for an alternative to all of this - namely, using an explicit version of the results in the paper of Ben's and yours that you mention to bound the l_{2+epsilon} norm of S(alpha). Redoing your proof (or that in Bourgain's On Lambda(p)-subsets of squares, which seems essentially the same) without introducing spurious constant factors seems a little difficult. I will have to think through it. Brun-Titchmarsh is an example of something I am quite glad already exists - the cleanest versions hide a mess in their proofs (at least to judge from the proofs I've read)! –  H A Helfgott Oct 20 '09 at 17:37
Oh, and lastly, yes, I always smooth. And yes, I'll take this off-line now, since it's getting a little technical. –  H A Helfgott Oct 20 '09 at 17:38