Large sieve

The large sieve is a method (or family of methods and related ideas) in analytic number theory.

Its name comes from its original application: given a set ${\displaystyle S\subset \{1,\ldots ,N\}}$ such that the elements of S are forbidden to lie in a set A_p ⊂ Z/p Z modulo every prime p, how large can S be? Here A_p is thought of as being large, i.e., at least as large as a constant times p; if this is not the case, we speak of a small sieve. (The term "sieve" is seen as alluding to, say, sifting ore for gold: we "sift out" the integers falling in one of the forbidden congruence classes modulo p, and ask ourselves how much is left at the end.)

Large-sieve methods have been developed enough that they are applicable to small-sieve situations as well. By now, something is seen as related to the large sieve not necessarily in terms of whether it related to the kind situation outlined above, but, rather, if it involves one of the two methods of proof traditionally used to yield a large-sieve result:

If a set S is ill-distributed modulo p (by virtue, for example, of being excluded from the congruence classes A_p) then the Fourier coefficients ${\displaystyle {\widehat {f_{p}}}(a)}$ of the characteristic function f_p of the set S mod p are in average large. These coefficients can be lifted to values ${\displaystyle {\widehat {f}}(a/p)}$ of the Fourier transform ${\displaystyle {\widehat {f}}}$ of the characteristic function f of the set S (i.e.,

...
Wikipedia