# What is a sieve and why are sieves useful?

I have been trying to understand what is exactly a sieve and why sieves are useful. I have read Wikipedia articles about sieve theory but they don't provide a definition of what is a sieve or why they are useful.

Can someone explain what is a sieve in general terms and what properties of sieves make them so useful in attacking number theoretic problems? Are there general principles that one can use as a guideline to see if sieves are likely to be useful in attacking a problem?

I know this question might be a bit elementary for number theorists, but I wasn't able to find good and concise information at the level of a general mathematician. (The Wikipedia article links to Ben Green's notes about sieve theory but the link is not working anymore. I Googled a bit however I couldn't find a concise high-level but rigorous exposition, notes like this and this dive quickly into examples and applications without giving any general definition and discussion of sieves.)

-
The book to read is Opera de Cribro, by Friedlander and Iwaniec. – Andrés Caicedo Mar 17 '14 at 5:25
Thanks @Andres, the preface and the first chapters of the book look promising. – Kaveh Mar 17 '14 at 5:39
If you'll forgive the self-reference, I gave an expository talk about sieves. – mixedmath Mar 17 '14 at 6:09
See also the blog post by Terry Tao : terrytao.wordpress.com/2007/06/05/… – Lierre Mar 17 '14 at 8:54

There are many kind of sieves, even more books, and infinitely many papers on the sieve, but here is one that is very short yet the gentler introduction to sieve ideas I have seen: Jameson, Notes on the large sieve.

-
I should have said that this paper, as its title indicates clearly, is only on the "large sieve", a kind of outsider in the various theories of sieves. But still it gives plenty of striking applications (such as Brun-Titchmarch) which can also be obtained by other type of sieves, and the sieving aspect is made very clear in the text. Also that paper doesn't spend much time explaining in general "what is a sieve", but will develop one example and should convince you very fast that "sieves are useful". – Joël Mar 24 '14 at 13:57

You may also peruse the following books (I am somewhat fond of them...) :

"Sieve Methods", Halberstam and Richert, Academic Press, 1974,

"Lecture on Sieve Methods", H.E. Richert, Tata Institute, 1976,

"Sieves in Number Theory", George Greaves, Springer-Verlag, 2001,

"Le grand crible dans la theorie analytique des nombres", Bombieri, Astérisque, SMF, 1974.

-

The goal of sieve theory is to obtain upper and lower bounds on the cardinality of sets of the form $$S(A, \mathcal{P}, t) = \{ n \in A : \forall p \in \mathcal{P}\ (p|n \to p>t) \}$$ where $A$ is a finite subset of the natural numbers and $\mathcal{P}$ is a subset of the primes. These bounds are used to give information on problems in additive analytic number theory.

-