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.

Statement

Let \pi(x;q,a) count the number of primes p congruent to a modulo q with p ≤ x. Then for all q < x.

History

The result was proven by sieve methods by Montgomery and Vaughan; an earlier result of Brun and Titchmarsh obtained a weaker version of this inequality with an additional multiplicative factor of 1+o(1).

Improvements

If q is relatively small, e.g.,, then there exists a better bound: This is due to Y. Motohashi (1973). He used a bilinear structure in the error term in the Selberg sieve, discovered by himself. Later this idea of exploiting structures in sieving errors developed into a major method in Analytic Number Theory, due to H. Iwaniec's extension to combinatorial sieve.

Comparison with Dirichlet's theorem

By contrast, Dirichlet's theorem on arithmetic progressions gives an asymptotic result, which may be expressed in the form but this can only be proved to hold for the more restricted range q < (log x)c for constant c: this is the Siegel–Walfisz theorem.