Brun–Titchmarsh theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In analytic number theory, the Brun–Titchmarsh theorem, named after Viggo Brun and Edward Charles Titchmarsh, is an upper bound on the distribution of prime numbers in arithmetic progression.

Statement[edit]

It states that, if \pi(x;q,a) counts the number of primes p congruent to a modulo q with p ≤ x, then

\pi(x;q,a) \le {2x \over \varphi(q)\log(x/q)}

for all q < x.

History[edit]

The result was proven by sieve methods by Montgomery and Vaughan; an earlier result of Brun and Titchmarsh obtained a weaker version of this inequality with an additional multiplicative factor of 1+o(1).

Improvements[edit]

If "q" is relatively small, e.g.,  q\le x^{9/20}, then there exists a better bound:

\pi(x;q,a)\le{(2+o(1))x\over\varphi(q)\ln(x/q^{3/8})}

This is due to Y. Motohashi (1973). He used a bilinear structure in the error term in the Selberg sieve, discovered by himself. Later this idea of exploiting structures in sieving errors developed into a major method in Analytic Number Theory, due to H. Iwaniec's extension to combinatorial sieve.

Comparison with Dirichlet's theorem[edit]

By contrast, Dirichlet's theorem on arithmetic progressions gives an asymptotic result, which may be expressed in the form

\pi(x;q,a) = \frac{x}{\varphi(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.


References[edit]