Brun–Titchmarsh theorem

The Brun–Titchmarsh theorem bounds the number of primes at most x in a reduced residue class modulo q by 2x divided by φ(q) log(x/q), for x > q.

Brun sieve: A combinatorial sieve method that bounds integers avoiding specified prime divisors. The theorem’s upper bound is obtained through sieve methods of this kind.
Arithmetic progression: A sequence of numbers with a fixed difference between consecutive terms. The theorem counts prime terms in progressions with common difference q.
Siegel–Walfisz theorem: A uniform prime number theorem for arithmetic progressions with moduli bounded by powers of log x. It gives an asymptotic formula in a narrower modulus range, unlike this upper bound.
Viggo Brun: A Norwegian mathematician who developed foundational sieve methods in the early twentieth century. Brun’s sieve supplied a central method for proving the theorem.
Sifting function: A function counting integers that survive the removal of multiples of selected primes. Sieve estimates for surviving integers underlie the progression bound.
Reduced residue system: A set containing one representative of each residue class coprime to a given modulus. The theorem applies only to residue classes coprime to q.
Bombieri–Vinogradov theorem: A theorem giving average prime-distribution estimates across arithmetic progressions for moduli up to nearly x to the one-half power. It averages over moduli to obtain distribution information beyond a single-class upper bound.
T. H. (Henry) Chan: A mathematician who proved a refinement of the Brun–Titchmarsh inequality. Chan’s work sharpened the bound’s constant in a later setting.
Sieve dimension: A parameter describing the density and local structure of sieved sequences. The prime sequence in a reduced residue class has dimension one in the relevant sieve framework.
Euler's totient function: The function φ(q) counts integers from 1 through q that are coprime to q. It normalizes the bound by the number of eligible residue classes.

Linked from 2 pages