Namespaces
Variants
Actions

Difference between revisions of "Brun-Titchmarsh theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(→‎References: isbn link)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
For coprime integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b1109701.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b1109702.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b1109703.png" /> denote the number of primes not exceeding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b1109704.png" /> that are congruent to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b1109705.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b1109706.png" />. Using analytic methods of the theory of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b1109707.png" />-functions [[#References|[a8]]], one can show that the asymptotic formula
+
{{TEX|done}}
 +
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 [[#References|[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}$.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b1109708.png" /></td> </tr></table>
+
In contrast, a simple application of a [[sieve method]] [[#References|[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 [[#References|[a3]]], [[#References|[a5]]], [[#References|[a8]]]; it is known as the Brun–Titchmarsh theorem. By a sophisticated argument, [[#References|[a6]]], one finds that
 
+
$$
holds uniformly for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b1109709.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b11097010.png" /> is an arbitrary positive constant. It is desirable to extend the validity range for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b11097011.png" /> of this formula, in view of its applications to classical problems. The generalized Riemann hypothesis (cf. [[Riemann hypotheses|Riemann hypotheses]]) is not capable of providing any information for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b11097012.png" />.
+
\pi(x;a,q) \le \frac{2x}{\phi(q)\log(x/q)}
 
+
$$
In contrast, a simple application of a [[Sieve method|sieve method]] [[#References|[a8]]] leads to an upper bound which gives the correct order of magnitude of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b11097013.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b11097014.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b11097015.png" /> is an arbitrary positive constant. Because of its uniformity in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b11097016.png" />, an inequality of this type turns out to be very useful [[#References|[a3]]], [[#References|[a5]]], [[#References|[a8]]]; it is known as the Brun–Titchmarsh theorem. By a sophisticated argument, [[#References|[a6]]], one finds that
+
for all $q < x$. The constant $2$ possesses a significant meaning in the context of sieve methods [[#References|[a2]]], [[#References|[a7]]]. By adapting the Brun–Titchmarsh theorem [[#References|[a1]]], [[#References|[a4]]], if necessary, it is possible to sharpen the above bound in various ranges for $q$.
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b11097017.png" /></td> </tr></table>
 
 
 
for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b11097018.png" />. The constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b11097019.png" /> possesses a significant meaning in the context of sieve methods [[#References|[a2]]], [[#References|[a7]]]. By adapting the Brun–Titchmarsh theorem [[#References|[a1]]], [[#References|[a4]]], if necessary, it is possible to sharpen the above bound in various ranges for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110970/b11097020.png" />.
 
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> E. Fouvry,   "Théorème de Brun–Titchmarsh: application au théorème de Fermat"  ''Invent. Math.'' , '''79'''  (1985)  pp. 383–407</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> H. Halberstam,   H.E. Richert,  "Sieve methods" , Acad. Press  (1974)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> C. Hooley,   "Applications of sieve methods to the theory of numbers" , Cambridge Univ. Press  (1976)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> H. Iwaniec,   "On the Brun–Titchmarsh theorem"  ''J. Math. Soc. Japan'' , '''34'''  (1982)  pp. 95–123</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> Yu.V. Linnik,   "Dispersion method in binary additive problems" , Nauka  (1961)  (In Russian)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top"> H.L. Montgomery,   R.C. Vaughan,  "The large sieve"  ''Mathematika'' , '''20'''  (1973)  pp. 119–134</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top"> Y. Motohashi,   "Sieve methods and prime number theory" , Tata Institute and Springer  (1983)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top"> K. Prachar,   "Primzahlverteilung" , Springer  (1957)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top"> E. Fouvry, "Théorème de Brun–Titchmarsh: application au théorème de Fermat"  ''Invent. Math.'' , '''79'''  (1985)  pp. 383–407</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top"> H. Halberstam, H.E. Richert,  "Sieve methods" , Acad. Press  (1974)</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top"> C. Hooley, "Applications of sieve methods to the theory of numbers" , Cambridge Univ. Press  (1976) {{ISBN|0-521-20915-3}}</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top"> H. Iwaniec, "On the Brun–Titchmarsh theorem"  ''J. Math. Soc. Japan'' , '''34'''  (1982)  pp. 95–123</TD></TR>
 +
<TR><TD valign="top">[a5]</TD> <TD valign="top"> Yu.V. Linnik, "Dispersion method in binary additive problems" , Nauka  (1961)  (In Russian)</TD></TR>
 +
<TR><TD valign="top">[a6]</TD> <TD valign="top"> H.L. Montgomery, R.C. Vaughan,  "The large sieve"  ''Mathematika'' , '''20'''  (1973)  pp. 119–134</TD></TR>
 +
<TR><TD valign="top">[a7]</TD> <TD valign="top"> Y. Motohashi, "Sieve methods and prime number theory" , Tata Institute and Springer  (1983)</TD></TR>
 +
<TR><TD valign="top">[a8]</TD> <TD valign="top"> K. Prachar, "Primzahlverteilung" , Springer  (1957)</TD></TR>
 +
</table>

Latest revision as of 16:53, 23 November 2023

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://encyclopediaofmath.org/index.php?title=Brun-Titchmarsh_theorem&oldid=18569
This article was adapted from an original article by H. Mikawa (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article