In mathematics, the large sieve is a method of analytic number theory. As the name implies, it was at least originally concerned, as a sieve method, with (for example) sifting from an integer sequence by means of congruence conditions modulo prime numbers, in which a relatively large number of residue classes for each modulus are excluded. That is, a large sieve, where a proportion of residue classes is sifted out, in principle is to be distinguished from a small sieve, in which perhaps only a single residue class for a given modulus is excluded from the sifted set. As is typical of sieve theory, this all will take place in a range of values for the parameters beyond the easy cases where the Chinese remainder theorem applies to give asymptotic estimates. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... Analytic number theory is the branch of number theory that uses methods from mathematical analysis. ... Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. ... The word modulo (Latin, with respect to a modulus of ___) is the Latin ablative of modulus which itself means a small measure. ... In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ... The word modulo is the Latin ablative of modulus. ... Several related results in number theory and abstract algebra are known under the name Chinese remainder theorem. ...

The early history of the large sieve traces back to work of Yu. B. Linnik, in 1941, working on the problem of the least quadratic non-residue. Subsequently Alfréd Rényi worked on it, using probability methods. It was only two decades later, after quite a number of contributions by others, that the large sieve was formulated in a way that was more definitive. This happened in the early 1960s, in independent work of Klaus Roth and Enrico Bombieri. The nature of the fundamental inequality was by then better understood: it relates to exponential sums evaluated at points on the unit circle that are in a sense well-spaced (measured by minimum distance), and the type of inequality is derived from the principle that the operator norm of a matrix of characters of the circle, evaluated at a finite set of points, is equal to the norm of the adjoint operator. In applications the set of points is often a Farey series of rational numbers, mapped onto the unit circle at roots of unity. Alfréd Rényi (March 20, 1921 – February 1, 1970) was a Hungarian mathematician who made contributions in combinatorics and graph theory but mostly in probability theory. ... Klaus Friedrich Roth (Roth is pronounced ROW-th) (29 October 1925) is a British mathematician known for work on diophantine approximation, the large sieve, and irregularities of distribution. ... Enrico Bombieri (born November 26, 1940) is a Italian mathematician, born in Milan. ... In mathematics, an exponential sum may be a finite Fourier series (i. ... Illustration of a unit circle. ... In mathematics, the operator norm is a means to measure the size of certain linear operators. ... In mathematics, a matrix (plural matrices) is a rectangular table of numbers or, more generally, a table consisting of abstract quantities that can be added and multiplied. ... In mathematics, the conjugate transpose or adjoint of an m-by-n matrix A with complex entries is the n-by-m matrix A* obtained from A by taking the transpose and then taking the complex conjugate of each entry. ... In mathematics, a Farey sequence of order n is the sequence of completely reduced fractions between 0 and 1 which, when in lowest terms, have denominators less than or equal to n, arranged in order of increasing size. ... In mathematics, the n-th roots of unity or de Moivre numbers, named after Abraham de Moivre (1667 - 1754), are complex numbers located on the unit circle. ...

See also

• Bombieri's theorem
• Sierpinski Sieving