Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Explicit bounds for primes in residue classes

Authors: Eric Bach and Jonathan Sorenson
Journal: Math. Comp. 65 (1996), 1717-1735
MSC (1991): Primary 11N13, 11M26; Secondary 11R44, 11Y35
MathSciNet review: 1355006
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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/\Bbb 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.
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 [Enhancements On Off] (What's this?)

  • 1. M. Abramowitz and I. A. Stegun. Handbook of Mathematical Functions. Dover, 1970.
  • 2. 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.
  • 3. N. C. Ankeny. An improvement of an inequality of Minkowski. Proc. Nat. Acad. Sci. U.S.A., 37:711--716, 1951. MR 13:538b
  • 4. N. C. Ankeny. The least quadratic non residue. Ann. Math. 52:65--72, 1952. MR 13:538c
  • 5. E. Bach. Explicit bounds for primality testing and related problems. Math. Comp., 55:355--380, 1990. MR 91m:11096
  • 6. 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.
  • 7. E. Bach and J. Shallit. Factoring with cyclotomic polynomials. Math. Comp., 52:201--219, 1989. MR 89k:11127
  • 8. E. Bach and L. Huelsbergen. Statistical evidence for small generating sets. Math. Comp., 61(203):69--82, 1993. MR 93k:11089
  • 9. R. P. Brent and H. T. Kung. The area-time complexity of binary multiplication. J. ACM, 28:521--534, 1981. [Erratum: ibid, 29:904, 1982.] MR 82i:68027
  • 10. S. Chowla. On the least prime in an arithmetical progression. J. Indian Math. Soc., 2:1--3, 1934.
  • 11. N. Costa Pereira. Estimates for the Chebyshev function $\psi (x)-\theta (x)$. Math. Comp., 44:211--221, 1985. MR 86k:11005
  • 12. M. Deuring. Über den Tschebotareffschen Dichtigkeitssatz. Math. Ann., 110:414--415, 1935.
  • 13. P. G. Lejeune Dirichlet. Beweis eines Satzes über die arithmetische Progression. Bericht Ak. Wiss. Berlin, 108--110, 1837. Reprinted in Werke, 1:307--312.
  • 14. 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.
  • 15. E. S. Golod and I. R. Shafarevich. On class field towers. Izv. Akad. Nauk. SSSR, 28:261-272, 1964. MR 28:5056
  • 16. H. Hasse. Bericht über neuere Untersuchungen und Probleme aus der Theorie der algebraischen Zahlkörper. Third Edition, Physica-Verlag, Würzburg, 1970. MR 42:1795
  • 17. D. R. Heath-Brown. Zero-free regions for Dirichlet $L$-functions and the least prime in an arithmetic progression. Proc. London Math. Soc., 64:265-338, 1991. MR 93a:11075
  • 18. D. R. Heath-Brown. Almost-primes in arithmetic progressions and short intervals. Mathematical Proceedings of the Cambridge Philosophical Society, 83:357--375, 1978. MR 58:10789
  • 19. H. Heilbronn. Zeta-functions and L-functions. In Algebraic Number Theory, J. W. S. Cassels and A. Fröhlich, Eds. Academic Press, 1967. MR 36:1414
  • 20. D. Hilbert. Die Theorie der algebraischen Zahlkörper. Jahresber. Deutsch. Math.-Verein., 4:175--546, 1897.
  • 21. Ju. V. Linnik. On the least prime in an arithmetic progression, I. The basic theorem. Mat. Sbornik, 15:139-178, 1944. MR 6:260b
  • 22. J. Lagarias, H. Montgomery, and A. Odlyzko. A bound for the least prime ideal in the Chebotarev density theorem. Invent. Math., 54:271-296, 1979. MR 81b:12013
  • 23. J. Lagarias and A. Odlyzko. Effective versions of the Chebotarev density theorem. In A. Fröhlich, editor, Algebraic Number Fields, pages 409--464, Academic Press, London, 1977. MR 56:5506
  • 24. S. Lang. Algebraic Number Theory. Addison-Wesley, 1970. MR 44:181
  • 25. H. W. Lenstra Jr.. Miller's primality test. Inform. Process. Letters, 8(2):86--88, 1979. MR 80c:10008
  • 26. C. R. MacCluer. A reduction of the \v{C}ebotarev density theorem to the cyclic case. Acta Arith., 15:45--47, 1968. MR 38:2117
  • 27. P. McCullagh. A rapidly convergent series for computing $\psi (z)$ and its derivatives. Math. Comp., 36:247--248, 1981. MR 81m:65028
  • 28. A. Odlyzko. Bounds for discriminants and related estimates for class numbers, regulators and zeros of zeta functions: a survey of recent results. Sém Theor. Nombres Bordeaux, 2:119-141, 1990. MR 91i:11154
  • 29. 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.
  • 30. J. B. Rosser and L. Schoenfeld. Approximate formulas for some functions of prime numbers. Ill. J. Math., 6:64--94, 1962. MR 25:1139
  • 31. R. Rumely. Numerical computations concerning the ERH. Math. Comp., 61(203):415--440, 1993. MR 94b:11085
  • 32. V. Shoup. Searching for primitive roots in finite fields. Math. Comp., 58:369--380, 1992. MR 92e:11140
  • 33. N. Tchebotarev. Bestimmung der Dichtigkeit einer Menge von Primzahlen, welche zu einer gegebenen Substitutionsklasse gehören. Math. Ann., 95:191--228, 1926.
  • 34. E. Titchmarsh. A divisor problem. Rend. Circ. Mat. Palermo, 54:414--429, 1930.
  • 35. P. Turán. Über die Primzahlen der arithmetischen Progression. Acta Sci. Math., 8:226--235, 1936/37.
  • 36. S. S. Wagstaff, Jr. Greatest of the least primes in arithmetic progressions having a given modulus. Math. Comp., 33:1073--1080, 1979. MR 81e:10038
  • 37. Y. Wang, S.-K. Hsieh, and K.-J. Yu. Two results on the distribution of prime numbers. Zhongguo Kexue Jishu Daxue Xuebao, 1:32--38, 1965. In Chinese. MR 34:7482

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11N13, 11M26, 11R44, 11Y35

Retrieve articles in all journals with MSC (1991): 11N13, 11M26, 11R44, 11Y35

Additional Information

Eric Bach
Affiliation: Computer Sciences Department University of Wisconsin Madison, Wisconsin 53706

Jonathan Sorenson
Affiliation: Department of Mathematics and Computer Science Butler University Indianapolis, Indiana 46208

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
Article copyright: © Copyright 1996 American Mathematical Society

American Mathematical Society