# Brun-Titchmarsh theorem

(Redirected from Brun–Titchmarsh theorem)
Jump to: navigation, search

For coprime integers $q$ and $a$, let $\pi(x;a,q)$ denote the number of primes not exceeding $x$ that are congruent to $a \pmod q$. Using analytic methods of the theory of $L$-functions [a8], one can show that the asymptotic formula (Dirichlet's theorem on arithmetic progressions) $$\pi(x;a,q) = \frac{x}{\phi(q)\log(x)} \left({1 + O\left(\frac{1}{\log x}\right)}\right)$$ holds uniformly for $q < \log^A x$, where $A$ is an arbitrary positive constant: this is the Siegel-Walfisz theorem. It is desirable to extend the validity range for $q$ of this formula, in view of its applications to classical problems. The generalized Riemann hypothesis (cf. Riemann hypotheses) is not capable of providing any information for $q > x^{1/2}$.

In contrast, a simple application of a sieve method [a8] leads to an upper bound which gives the correct order of magnitude of $\pi(x;a,q)$ for all $q < x^{1-\epsilon}$, where $\epsilon$ is an arbitrary positive constant. Because of its uniformity in $q$, an inequality of this type turns out to be very useful [a3], [a5], [a8]; it is known as the Brun–Titchmarsh theorem. By a sophisticated argument, [a6], one finds that $$\pi(x;a,q) \le \frac{2x}{\phi(q)\log(x/q)}$$ for all $q < x$. The constant $2$ possesses a significant meaning in the context of sieve methods [a2], [a7]. By adapting the Brun–Titchmarsh theorem [a1], [a4], if necessary, it is possible to sharpen the above bound in various ranges for $q$.

#### References

 [a1] E. Fouvry, "Théorème de Brun–Titchmarsh: application au théorème de Fermat" Invent. Math. , 79 (1985) pp. 383–407 [a2] H. Halberstam, H.E. Richert, "Sieve methods" , Acad. Press (1974) [a3] C. Hooley, "Applications of sieve methods to the theory of numbers" , Cambridge Univ. Press (1976) ISBN 0-521-20915-3 [a4] H. Iwaniec, "On the Brun–Titchmarsh theorem" J. Math. Soc. Japan , 34 (1982) pp. 95–123 [a5] Yu.V. Linnik, "Dispersion method in binary additive problems" , Nauka (1961) (In Russian) [a6] H.L. Montgomery, R.C. Vaughan, "The large sieve" Mathematika , 20 (1973) pp. 119–134 [a7] Y. Motohashi, "Sieve methods and prime number theory" , Tata Institute and Springer (1983) [a8] K. Prachar, "Primzahlverteilung" , Springer (1957)
How to Cite This Entry:
Brun–Titchmarsh theorem. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Brun%E2%80%93Titchmarsh_theorem&oldid=35728