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 [math]\displaystyle{ \pi(x;a,q) }[/math] counts the number of primes p congruent to a modulo q with p ≤ x, then

[math]\displaystyle{ \pi(x;a,q) \le 2x / \phi(q)\log(x/q) }[/math]

for all [math]\displaystyle{ q \lt x }[/math]. 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

[math]\displaystyle{ \pi(x;a,q) = \frac{x}{\phi(q)\log(x)} \left({1 + O\left(\frac{1}{\log x}\right)}\right) }[/math]

but this can only be proved to hold for the more restricted range [math]\displaystyle{ q \lt (\log x)^c }[/math] 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 .