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

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