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)\le 2x/\varphi (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}{\varphi (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

• Hazewinkel, Michiel (2002), Encyclopaedia of Mathematics: Supplement 3, p. 159, ISBN 0792347099, http://eom.springer.de/b/b110970.htm 
• Hooley, Christopher (1976), Applications of sieve methods to the theory of numbers, Cambridge University Press, p. 10, ISBN 0-521-20915-3 
• Montgomery, H.L.; Vaughan, R.C. (1973), "The large sieve", Mathematika 20: 119-134 .