Brun-Titchmarsh theorem

The Brun–Titchmarsh theorem in analytic number theory is an upper bound on the distribution on primes in an arithmetic progression. It states that, if $\pi (x;a,q)$ counts the number of primes p congruent to a modulo q with p ≤ x, then

$\pi (x;a,q)\leq 2x/\phi (q)\log(x/q)$

for all $q<x$. The result is proved by sieve methods. By contrast, Dirichlet's theorem on arithmetic progressions gives an asymptotic result, which may be expressed in the form

$\pi (x;a,q)={\frac {x}{\phi (q)\log(x)}}\left({1+O\left({\frac {1}{\log x}}\right)}\right)$

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.

The result is named for Viggo Brun and Edward Charles Titchmarsh.

References

• Michiel Hazewinkel (2002). Encyclopaedia of Mathematics: Supplement 3, 159. ISBN 0792347099. 
• Hugh L. Montgomery; Robert C. Vaughan (1973). "The large sieve". Mathematika 20: 119-134.