Explicit bounds for primes in residue classes
HTML articles powered by AMS MathViewer
- by Eric Bach and Jonathan Sorenson PDF
- Math. Comp. 65 (1996), 1717-1735 Request permission
Abstract:
Let $E/K$ be an abelian extension of number fields, with $E \ne \Bbb Q$. Let $\Delta$ and $n$ denote the absolute discriminant and degree of $E$. Let $\sigma$ denote an element of the Galois group of $E/K$. We prove the following theorems, assuming the Extended Riemann Hypothesis:
-
There is a degree-$1$ prime ${\frak p}$ of $K$ such that $\left (\frac {\displaystyle \frak p}{E/K}\right ) =\sigma$, satisfying $N{\frak p}\le (1+o(1))(\log \Delta +2n)^2$.
-
There is a degree-$1$ prime $\frak p$ of $K$ such that $\left (\frac {\displaystyle \frak p}{E/K}\right )$ generates the same group as $\sigma$, satisfying $N{\frak p}\le (1+o(1))(\log \Delta )^2$.
-
For $K=\Bbb Q$, there is a prime $p$ such that $\left (\frac {\displaystyle \frak p}{E/\mathbb {Q}}\right )=\sigma$, satisfying $p\le (1+o(1))(\log \Delta )^2$.
In (1) and (2) we can in fact take $\frak p$ to be unramified in $K/\Bbb Q$. A special case of this result is the following.
-
[(4)] If $\gcd (m,q)=1$, the least prime $p\equiv m\pmod q$ satisfies $p\le (1+o(1))(\varphi (q)\log q)^2$.
It follows from our proof that (1)–(3) also hold for arbitrary Galois extensions, provided we replace $\sigma$ by its conjugacy class $\langle \sigma \rangle$. Our theorems lead to explicit versions of (1)–(4), including the following: the least prime $p \equiv m \pmod q$ is less than $2( q \log q )^2$.
References
- M. Abramowitz and I. A. Stegun. Handbook of Mathematical Functions. Dover, 1970.
- L. Adleman and H. W. Lenstra, Jr. Finding irreducible polynomials over finite fields. In Proc. 18th Ann. ACM Symp. Theory of Computing, pages 462–469, 1987.
- C. J. Everett Jr., Annihilator ideals and representation iteration for abstract rings, Duke Math. J. 5 (1939), 623–627. MR 13
- C. J. Everett Jr., Annihilator ideals and representation iteration for abstract rings, Duke Math. J. 5 (1939), 623–627. MR 13
- Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355–380. MR 1023756, DOI 10.1090/S0025-5718-1990-1023756-8
- E. Bach, M. Giesbrecht, and J. McInnes. The complexity of number-theoretic problems. Technical Report 247/91 (ITRC Lecture Series), Dept. of Computer Science, Univ. Toronto, 1991.
- Eric Bach and Jeffrey Shallit, Factoring with cyclotomic polynomials, Math. Comp. 52 (1989), no. 185, 201–219. MR 947467, DOI 10.1090/S0025-5718-1989-0947467-1
- Eric Bach and Lorenz Huelsbergen, Statistical evidence for small generating sets, Math. Comp. 61 (1993), no. 203, 69–82. MR 1195432, DOI 10.1090/S0025-5718-1993-1195432-5
- R. P. Brent and H. T. Kung, The area-time complexity of binary multiplication, J. Assoc. Comput. Mach. 28 (1981), no. 3, 521–534. MR 624731, DOI 10.1145/322261.322269
- S. Chowla. On the least prime in an arithmetical progression. J. Indian Math. Soc., 2:1–3, 1934.
- N. Costa Pereira, Estimates for the Chebyshev function $\psi (x)-\theta (x)$, Math. Comp. 44 (1985), no. 169, 211–221. MR 771046, DOI 10.1090/S0025-5718-1985-0771046-9
- M. Deuring. Über den Tschebotareffschen Dichtigkeitssatz. Math. Ann., 110:414–415, 1935.
- P. G. Lejeune Dirichlet. Beweis eines Satzes über die arithmetische Progression. Bericht Ak. Wiss. Berlin, 108–110, 1837. Reprinted in Werke, 1:307–312.
- P. G. Lejeune Dirichlet. Beweis des Satzes, daß jede unbegrenzte arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Factor sind, unendlich viele Primzahlen enthält. Abhand. Ak. Wiss. Berlin, 45–81, 1837–9. Reprinted in Werke, 1:313–342.
- E. S. Golod and I. R. Šafarevič, On the class field tower, Izv. Akad. Nauk SSSR Ser. Mat. 28 (1964), 261–272 (Russian). MR 0161852
- Helmut Hasse, Bericht über neuere Untersuchungen und Probleme aus der Theorie der algebraischen Zahlkörper. Teil I: Klassenkörpertheorie. Teil Ia: Beweise zu Teil I. Teil II: Reziprozitätsgesetz, Physica-Verlag, Würzburg-Vienna, 1970 (German). Dritte Auflage. MR 0266893
- D. R. Heath-Brown, Zero-free regions for Dirichlet $L$-functions, and the least prime in an arithmetic progression, Proc. London Math. Soc. (3) 64 (1992), no. 2, 265–338. MR 1143227, DOI 10.1112/plms/s3-64.2.265
- D. R. Heath-Brown, Almost-primes in arithmetic progressions and short intervals, Math. Proc. Cambridge Philos. Soc. 83 (1978), no. 3, 357–375. MR 491558, DOI 10.1017/S0305004100054657
- H. Heilbronn, Zeta-functions and $L$-functions, Algebraic Number Theory (Proc. Instructional Conf., Brighton, 1965), Thompson, Washington, D.C., 1967, pp. 204–230. MR 0218327
- D. Hilbert. Die Theorie der algebraischen Zahlkörper. Jahresber. Deutsch. Math.-Verein., 4:175–546, 1897.
- Albert Eagle, Series for all the roots of the equation $(z-a)^m=k(z-b)^n$, Amer. Math. Monthly 46 (1939), 425–428. MR 6, DOI 10.2307/2303037
- J. C. Lagarias, H. L. Montgomery, and A. M. Odlyzko, A bound for the least prime ideal in the Chebotarev density theorem, Invent. Math. 54 (1979), no. 3, 271–296. MR 553223, DOI 10.1007/BF01390234
- J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR 0447191
- Serge Lang, Algebraic number theory, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970. MR 0282947
- H. W. Lenstra Jr., Miller’s primality test, Inform. Process. Lett. 8 (1979), no. 2, 86–88. MR 520273, DOI 10.1016/0020-0190(79)90149-2
- C. R. MacCluer, A reduction of the Čebotarev density theorem to the cyclic case, Acta Arith. 15 (1968), 45–47. MR 233796, DOI 10.4064/aa-15-1-45-47
- Peter McCullagh, A rapidly convergent series for computing $\psi (z)$ and its derivatives, Math. Comp. 36 (1981), no. 153, 247–248. MR 595057, DOI 10.1090/S0025-5718-1981-0595057-8
- A. M. Odlyzko, Bounds for discriminants and related estimates for class numbers, regulators and zeros of zeta functions: a survey of recent results, Sém. Théor. Nombres Bordeaux (2) 2 (1990), no. 1, 119–141 (English, with French summary). MR 1061762
- J. Oesterlé. Versions effectives du théorème de Chebotarev sous l’hypothèse de Riemann generalisée. Soc. Math. France Astérisque, 61:165–167, 1979.
- J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
- Robert Rumely, Numerical computations concerning the ERH, Math. Comp. 61 (1993), no. 203, 415–440, S17–S23. MR 1195435, DOI 10.1090/S0025-5718-1993-1195435-0
- Victor Shoup, Searching for primitive roots in finite fields, Math. Comp. 58 (1992), no. 197, 369–380. MR 1106981, DOI 10.1090/S0025-5718-1992-1106981-9
- N. Tchebotarev. Bestimmung der Dichtigkeit einer Menge von Primzahlen, welche zu einer gegebenen Substitutionsklasse gehören. Math. Ann., 95:191–228, 1926.
- E. Titchmarsh. A divisor problem. Rend. Circ. Mat. Palermo, 54:414–429, 1930.
- P. Turán. Über die Primzahlen der arithmetischen Progression. Acta Sci. Math., 8:226–235, 1936/37.
- Samuel S. Wagstaff Jr., Greatest of the least primes in arithmetic progressions having a given modulus, Math. Comp. 33 (1979), no. 147, 1073–1080. MR 528061, DOI 10.1090/S0025-5718-1979-0528061-7
- Yuan Wang, Hsieh Sheng-kang, and Yu K’un-jui, Two results on the distribution of prime numbers, J. China Univ. Sci. Tech. 1 (1965), no. 1, 32–38 (Chinese). MR 207667
Additional Information
- Eric Bach
- Affiliation: Computer Sciences Department University of Wisconsin Madison, Wisconsin 53706
- Email: bach@cs.wisc.edu
- Jonathan Sorenson
- Affiliation: Department of Mathematics and Computer Science Butler University Indianapolis, Indiana 46208
- MR Author ID: 334195
- Email: sorenson@butler.edu
- Received by editor(s): October 4, 1994
- Received by editor(s) in revised form: September 5, 1995
- Additional Notes: This research was supported in part by NSF grants CCR-9208639 and CCR-9204414, a grant from the Wisconsin Alumni Research Foundation, and a Butler University Fellowship
An extended abstract appeared in the Proceedings of Symposia in Applied Mathematics: Mathematics of Computation 1943–1993: A Half-Century of Computational Mathematics, Mathematics of Computation 50th Anniversary Symposium, August 9–13, 1993, Vancouver, British Columbia, as part of the Lehmer Minisymposium on computational number theory, Walter Gautschi, Editor, PSAPM volume 48, published by the American Mathematical Society, pp. 535–539 - © Copyright 1996 American Mathematical Society
- Journal: Math. Comp. 65 (1996), 1717-1735
- MSC (1991): Primary 11N13, 11M26; Secondary 11R44, 11Y35
- DOI: https://doi.org/10.1090/S0025-5718-96-00763-6
- MathSciNet review: 1355006