Large sieve
From Wikipedia, the free encyclopedia
In mathematics, the large sieve is a method of analytic number theory. As the name implies, it was developed in sieve theory, (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.
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.
[edit] See also
[edit] References
- Alina Carmen Cojocaru; M. Ram Murty. An introduction to sieve methods and their applications. London Mathematical Society Student Texts. 66, Cambridge University Press. pp. 135-155. ISBN 0-521-61275-6.
- Harold Davenport (2000). Multiplicative Number Theory. Graduate Texts in Mathematics. 74 (3rd ed. ed.), Springer-Verlag. ISBN 0-387-95097-4.
- Christopher Hooley (1976). Applications of sieve methods to the theory of numbers, Cambridge University Press. pp. 17-20. ISBN 0-521-20915-3.
- Emmanuel Kowalski (2008). The Large Sieve and its Applications. Cambridge Tracts in Mathematics, Cambridge University Press. ISBN 9780521888516.
- Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics. 46, Cambridge University Press. pp. 62-73. ISBN 0-521-41261-7.
