Large sieve

Last updated

The large sieve is a method (or family of methods and related ideas) in analytic number theory. It is a type of sieve where up to half of all residue classes of numbers are removed, as opposed to small sieves such as the Selberg sieve wherein only a few residue classes are removed. The method has been further heightened by the larger sieve which removes arbitrarily many residue classes. [1]

Contents

Name

Its name comes from its original application: given a set such that the elements of S are forbidden to lie in a set ApZ/pZ modulo every prime p, how large can S be? Here Ap 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.

History

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. It is also around that time that the connection with the duality principle became better understood. In the mid-1960s, the Bombieri–Vinogradov theorem was proved as a major application of large sieves using estimations of mean values of Dirichlet characters. In the late 1960s and early 1970s, many of the key ingredients and estimates were simplified by Patrick X. Gallagher. [2]

Development

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

Approximate Plancherel inequality

If a set S is ill-distributed modulo p (by virtue, for example, of being excluded from the congruence classes Ap) then the Fourier coefficients of the characteristic function fp of the set S mod p are in average large. These coefficients can be lifted to values of the Fourier transform of the characteristic function f of the set S (i.e.,

).

By bounding derivatives, we can see that must be large, on average, for all x near rational numbers of the form a/p. Large here means "a relatively large constant times |S|". Since

we get a contradiction with the Plancherel identity

unless |S| is small. (In practice, to optimise bounds, people nowadays modify the Plancherel identity into an equality rather than bound derivatives as above.)

Duality principle

One can prove a strong large-sieve result easily by noting the following basic fact from functional analysis: the norm of a linear operator (i.e.,

where A is an operator from a linear space V to a linear space W) equals the norm of its adjoint i.e.,

.

This principle itself has come to acquire the name "large sieve" in some of the mathematical literature.

It is also possible to derive the large sieve from majorants in the style of Selberg (see Selberg, Collected Works, vol II, Lectures on sieves).

See also

Related Research Articles

<span class="mw-page-title-main">Atle Selberg</span> Norwegian mathematician (1917–2007)

Atle Selberg was a Norwegian mathematician known for his work in analytic number theory and the theory of automorphic forms, and in particular for bringing them into relation with spectral theory. He was awarded the Fields Medal in 1950 and an honorary Abel Prize in 2002.

<span class="mw-page-title-main">Enrico Bombieri</span> Italian mathematician (born 1940)

Enrico Bombieri is an Italian mathematician, known for his work in analytic number theory, Diophantine geometry, complex analysis, and group theory. Bombieri is currently Professor Emeritus in the School of Mathematics at the Institute for Advanced Study in Princeton, New Jersey. Bombieri won the Fields Medal in 1974 for his contributions to large sieve mathematics, conceptualized by Linnick 1941, and its application to the distribution of prime numbers.

In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:

<span class="mw-page-title-main">Analytic number theory</span> Exploring properties of the integers with complex analysis

In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Peter Gustav Lejeune Dirichlet's 1837 introduction of Dirichlet L-functions to give the first proof of Dirichlet's theorem on arithmetic progressions. It is well known for its results on prime numbers and additive number theory.

In mathematics, an exponential sum may be a finite Fourier series, or other finite sum formed using the exponential function, usually expressed by means of the function

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 prototypical example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the prototypical example of a sieve is the sieve of Eratosthenes, or the more general Legendre sieve. The direct attack on prime numbers using these methods soon reaches apparently insuperable obstacles, in the way of the accumulation of error terms. In one of the major strands of number theory in the twentieth century, ways were found of avoiding some of the difficulties of a frontal attack with a naive idea of what sieving should be.

In number theory, the Elliott–Halberstam conjecture is a conjecture about the distribution of prime numbers in arithmetic progressions. It has many applications in sieve theory. It is named for Peter D. T. A. Elliott and Heini Halberstam, who stated the conjecture in 1968.

In mathematics, a character sum is a sum of values of a Dirichlet character χ moduloN, taken over a given range of values of n. Such sums are basic in a number of questions, for example in the distribution of quadratic residues, and in particular in the classical question of finding an upper bound for the least quadratic non-residue moduloN. Character sums are often closely linked to exponential sums by the Gauss sums.

In mathematics, a Kloosterman sum is a particular kind of exponential sum. They are named for the Dutch mathematician Hendrik Kloosterman, who introduced them in 1926 when he adapted the Hardy–Littlewood circle method to tackle a problem involving positive definite diagonal quadratic forms in four as opposed to five or more variables, which he had dealt with in his dissertation in 1924.

This is a glossary of arithmetic and diophantine geometry in mathematics, areas growing out of the traditional study of Diophantine equations to encompass large parts of number theory and algebraic geometry. Much of the theory is in the form of proposed conjectures, which can be related at various levels of generality.

In mathematics, the Bombieri–Vinogradov theorem is a major result of analytic number theory, obtained in the mid-1960s, concerning the distribution of primes in arithmetic progressions, averaged over a range of moduli. The first result of this kind was obtained by Mark Barban in 1961 and the Bombieri–Vinogradov theorem is a refinement of Barban's result. The Bombieri–Vinogradov theorem is named after Enrico Bombieri and A. I. Vinogradov, who published on a related topic, the density hypothesis, in 1965.

In algebraic number theory, a Gauss sum or Gaussian sum is a particular kind of finite sum of roots of unity, typically

Multiplicative number theory is a subfield of analytic number theory that deals with prime numbers and with factorization and divisors. The focus is usually on developing approximate formulas for counting these objects in various contexts. The prime number theorem is a key result in this subject. The Mathematics Subject Classification for multiplicative number theory is 11Nxx.

In analytic number theory, the Brun–Titchmarsh theorem, named after Viggo Brun and Edward Charles Titchmarsh, is an upper bound on the distribution of prime numbers in arithmetic progression.

<span class="mw-page-title-main">Selberg sieve</span>

In number theory, the Selberg sieve is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences. It was developed by Atle Selberg in the 1940s.

In number theory, the fundamental lemma of sieve theory is any of several results that systematize the process of applying sieve methods to particular problems. Halberstam & Richert write:

A curious feature of sieve literature is that while there is frequent use of Brun's method there are only a few attempts to formulate a general Brun theorem ; as a result there are surprisingly many papers which repeat in considerable detail the steps of Brun's argument.

The Jurkat–Richert theorem is a mathematical theorem in sieve theory. It is a key ingredient in proofs of Chen's theorem on Goldbach's conjecture. It was proved in 1965 by Wolfgang B. Jurkat and Hans-Egon Richert.

The Turán–Kubilius inequality is a mathematical theorem in probabilistic number theory. It is useful for proving results about the normal order of an arithmetic function. The theorem was proved in a special case in 1934 by Pál Turán and generalized in 1956 and 1964 by Jonas Kubilius.

In algebraic number theory, a supersingular prime for a given elliptic curve is a prime number with a certain relationship to that curve. If the curve E is defined over the rational numbers, then a prime p is supersingular for E if the reduction of E modulo p is a supersingular elliptic curve over the residue field Fp.

In number theory, the larger sieve is a sieve invented by Patrick X. Gallagher. The name denotes a heightening of the large sieve. Combinatorial sieves like the Selberg sieve are strongest, when only a few residue classes are removed, while the term large sieve means that this sieve can take advantage of the removal of a large number of up to half of all residue classes. The larger sieve can exploit the deletion of an arbitrary number of classes.

References

  1. Gallagher, Patrick (1971). "A larger sieve". Acta Arithmetica. 18: 77–81.
  2. Tenenbaum, Gérald (2015). Introduction to Analytic and Probabilistic Number Theory. Graduate Studies in Mathematics. Vol. 163. American Mathematical Society. pp. 102–104. ISBN   9780821898543.