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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi(x;a,q) \le 2x / \phi(q)\log(x/q)}

for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.