Brun-Titchmarsh theorem

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)