1549380232-Automorphic_Forms_and_Applications__Sarnak_

LECTURE 3. LARGE SIEVE INEQUALITIES 231

3.3. Some applications of the large sieve

As we have seen in section 3.1.1, one of the main applications of the large sieve

inequalities is to provide nontrivial upper bounds for the cardinality of sets having

some arithmetic structure.

3.3.1. Linnik's theorem and its generalizations

Linnik's original motivation [Linl] was the classical problem:

Question. Given q a prime number, what is the size of the least prime pq ( q) (resp.

Pnq(q)) that is a quadratic (resp. a nonquadratic)-residue mod q?

It follows from GRH that

Pq(q), Pnq(q) « (logq)A

for some absolute constant A(= 2); unconditionally one has the much weaker up-

per bound from Burgess's Theorem 4.3 of the next lecture,

Pq(q), Pnq(q) «c: ql/4+c:_

By an additional sieving trick, Vinogradov improved this bound for the least non-

quadratic residue to

Pnq(q) «c: q1/(4Je")+c:.

As one of the first application of the large sieve, Linnik proved that for A sufficiently
large, almost all primes q have their least prime quadratic (resp. nonquadratic)-
residue smaller than (log q)A. More precisely, one has (in a slightly different form
than Linnik's original statement)

Theorem 3.6. For A, Q ~ 1, the number of primes q ~ Q such that

Pq(q), or Pnq(q) ~ (logq)A

is bounded by «A QB/A for some absolute constant B.

Proof. Let MA(Q) be the set of such primes q. By definition, for any q E MA(Q)
and any prime p < (logq)A one has(~) = -1 (resp. 1). For N ~ Q we let N be

the set of integers less than N, having all their prime factors < (log q) A; hence for

n EN and q > (logQ)A one has(~)= (-l)n(n) (resp. 1). We set an= (-l)n(n)

(resp. 1) if n EN and 0 otherwise and we apply2 (3.5), obtaining

and hence

IMA(Q)llNl^2 ~ L IL an(~)l^2 « (Q^2 + N)INI,

q(,_Q n(,_N q

q prime

IMA(Q)I « (Q^2 + N)/INI.

It is elementary to show (see [Te] IIl.5 Proof of Thm.2 for instance) that !NI »A
N^1 -l/A, and the result follows by taking N = Q^2. 0

The question about the size of the least non-quadratic residue can be gener-
alized to various contexts: for instance in the case of modular forms, one has the
following:

(^2) for instance, but a weaker inequality would be sufficient if one were not concerned with the size of B.