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
*.