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.
Suppose that is a set of prime powers, N an integer, a set of integers in the interval [1, N], such that for there are at most residue classes modulo , which contain elements of .
Then we have
provided the denominator on the right is positive. [1]
A typical application is the following result, for which the large sieve fails (specifically for ), due to Gallagher: [2]
The number of integers , such that the order of modulo is for all primes is .
If the number of excluded residue classes modulo varies with , then the larger sieve is often combined with the large sieve. The larger sieve is applied with the set above defined to be the set of primes for which many residue classes are removed, while the large sieve is used to obtain information using the primes outside . [3]
In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function f(n) whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n".
In mathematics, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs. The theorem was proved independently by Jacques Hadamard and Charles Jean de la Vallée Poussin in 1896 using ideas introduced by Bernhard Riemann.
In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:
In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as or
The Liouville Lambda function, denoted by λ(n) and named after Joseph Liouville, is an important arithmetic function. Its value is +1 if n is the product of an even number of prime numbers, and −1 if it is the product of an odd number of primes.
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:
In mathematics, the Poisson summation formula is an equation that relates the Fourier series coefficients of the periodic summation of a function to values of the function's continuous Fourier transform. Consequently, the periodic summation of a function is completely defined by discrete samples of the original function's Fourier transform. And conversely, the periodic summation of a function's Fourier transform is completely defined by discrete samples of the original function. The Poisson summation formula was discovered by Siméon Denis Poisson and is sometimes called Poisson resummation.
In mathematical statistics, the Kullback–Leibler divergence, denoted , is a type of statistical distance: a measure of how one probability distribution P is different from a second, reference probability distribution Q. A simple interpretation of the KL divergence of P from Q is the expected excess surprise from using Q as a model when the actual distribution is P. While it is a distance, it is not a metric, the most familiar type of distance: it is not symmetric in the two distributions, and does not satisfy the triangle inequality. Instead, in terms of information geometry, it is a type of divergence, a generalization of squared distance, and for certain classes of distributions, it satisfies a generalized Pythagorean theorem.
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, the von Mangoldt function is an arithmetic function named after German mathematician Hans von Mangoldt. It is an example of an important arithmetic function that is neither multiplicative nor additive.
In mathematics, the fundamental theorem of Galois theory is a result that describes the structure of certain types of field extensions in relation to groups. It was proved by Évariste Galois in his development of Galois theory.
In number theory, Vinogradov's theorem is a result which implies that any sufficiently large odd integer can be written as a sum of three prime numbers. It is a weaker form of Goldbach's weak conjecture, which would imply the existence of such a representation for all odd integers greater than five. It is named after Ivan Matveyevich Vinogradov who proved it in the 1930s. Hardy and Littlewood had shown earlier that this result followed from the generalized Riemann hypothesis, and Vinogradov was able to remove this assumption. The full statement of Vinogradov's theorem gives asymptotic bounds on the number of representations of an odd integer as a sum of three primes. The notion of "sufficiently large" was ill-defined in Vinogradov's original work, but in 2002 it was shown that 101346 is sufficiently large. Additionally numbers up to 1020 had been checked via brute force methods, thus only a finite number of cases to check remained before the odd Goldbach conjecture would be proven or disproven. In 2013, Harald Helfgott proved Goldbach's weak conjecture for all cases.
Cubic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x3 ≡ p (mod q) is solvable; the word "reciprocity" comes from the form of the main theorem, which states that if p and q are primary numbers in the ring of Eisenstein integers, both coprime to 3, the congruence x3 ≡ p is solvable if and only if x3 ≡ q is solvable.
Discrepancy of hypergraphs is an area of discrepancy theory.
Quartic or biquadratic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x4 ≡ p is solvable; the word "reciprocity" comes from the form of some of these theorems, in that they relate the solvability of the congruence x4 ≡ p to that of x4 ≡ q.
Anatoly Alexeyevich Karatsuba was a Russian mathematician working in the field of analytic number theory, p-adic numbers and Dirichlet series.
In probability theory and statistics, the Poisson distribution is a discrete probability distribution that expresses the probability of a given number of events occurring in a fixed interval of time or space if these events occur with a known constant mean rate and independently of the time since the last event. It is named after French mathematician Siméon Denis Poisson. The Poisson distribution can also be used for the number of events in other specified interval types such as distance, area, or volume.
In mathematics, an algebraic number field is an extension field of the field of rational numbers such that the field extension has finite degree . Thus is a field that contains and has finite dimension when considered as a vector space over .
Roth's theorem on arithmetic progressions is a result in additive combinatorics concerning the existence of arithmetic progressions in subsets of the natural numbers. It was first proven by Klaus Roth in 1953. Roth's theorem is a special case of Szemerédi's theorem for the case .
The Goldston-Pintz-Yıldırım sieve is a sieve method and variant of the Selberg sieve with generalized, multidimensional sieve weights. The sieve led to a series of important breakthroughs in analytic number theory.
