Brun–Titchmarsh theorem

In analytic number theory, the Brun–Titchmarsh theorem is an upper bound on the distribution of primes in 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 over 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 + Oleft(frac{1}{log x} ight)} ight)

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

*
* springer|id=b/b110970
first=H.|last= Mikawa
*.