Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



New quadratic polynomials with high densities of prime values

Authors: Michael J. Jacobson Jr. and Hugh C. Williams
Journal: Math. Comp. 72 (2003), 499-519
MSC (2000): Primary 11R11, 11R29, 11Y40; Secondary 11Y16
Published electronically: May 2, 2002
MathSciNet review: 1933834
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Hardy and Littlewood's Conjecture F implies that the asymptotic density of prime values of the polynomials $f_A(x) = x^2 + x + A,$ $A \in \mathbb{Z}$, is related to the discriminant $\Delta = 1 - 4A$ of $f_A(x)$ via a quantity $C(\Delta).$ The larger $C(\Delta)$ is, the higher the asymptotic density of prime values for any quadratic polynomial of discriminant $\Delta$. A technique of Bach allows one to estimate $C(\Delta)$ accurately for any $\Delta < 0$, given the class number of the imaginary quadratic order with discriminant $\Delta$, and for any $\Delta > 0$ given the class number and regulator of the real quadratic order with discriminant $\Delta$. The Manitoba Scalable Sieve Unit (MSSU) has shown us how to rapidly generate many discriminants $\Delta$ for which $C(\Delta)$ is potentially large, and new methods for evaluating class numbers and regulators of quadratic orders allow us to compute accurate estimates of $C(\Delta)$ efficiently, even for values of $\Delta$ with as many as $70$decimal digits. Using these methods, we were able to find a number of discriminants for which, under the assumption of the Extended Riemann Hypothesis, $C(\Delta)$ is larger than any previously known examples.

References [Enhancements On Off] (What's this?)

  • 1. C.S. Abel, Ein Algorithmus zur Berechnung der Klassenzahl und des Regulators reellquadratischer Ordnungen, Ph.D. thesis, Universität des Saarlandes, Saarbrücken, Germany, 1994.
  • 2. E. Bach, Improved approximations for Euler products, Number Theory: CMS Proc., vol. 15, Amer. Math. Soc., Providence, RI, 1995, pp. 13-28. MR 96i:11124
  • 3. N.G.W.H. Beeger, Report on some calculations of prime numbers, Nieuw Archief voor Wiskunde (2) 20 (1939), 48-50. MR 1:65g
  • 4. J. Buchmann, A subexponential algorithm for the determination of class groups and regulators of algebraic number fields, Séminaire de Théorie des Nombres (Paris), 1988-89, Birkhäuser, Boston, 1990, pp. 27-41. MR 92g:11125
  • 5. H. Cohen, F. Diaz y Diaz, and M. Olivier, Calculs de nombres de classes et de régulateurs de corps quadratiques en temps sous-exponentiel, Séminaire de Théorie des Nombres (Paris), 1990-91, Birkhäser, Boston, 1993, pp. 35-46. MR 94m:11151
  • 6. S. Düllmann, Ein Algorithmus zur Bestimmung der Klassengruppe positiv definiter binärer quadratischer Formen, Ph.D. thesis, Universität des Saarlandes, Saarbrücken, Germany, 1991.
  • 7. G.W. Fung and H.C. Williams, Quadratic polynomials which have a high density of prime values, Math. Comp. 55 (1990), 345-353. MR 90j:11090
  • 8. The LiDIA Group, LiDIA: a c++ library for computational number theory, Software, Technische Universität Darmstadt, Germany, 1997, See
  • 9. J.L. Hafner and K.S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2 (1989), 837-850. MR 91f:11090
  • 10. G.H. Hardy and J.E. Littlewood, Partitio numerorum III: On the expression of a number as a sum of primes, Acta Math. 44 (1923), 1-70.
  • 11. M.J. Jacobson, Jr., Computational techniques in quadratic fields, Master's thesis, University of Manitoba, Winnipeg, Manitoba, 1995.
  • 12. -, Subexponential class group computation in quadratic orders, Ph.D. thesis, Technische Universität Darmstadt, Darmstadt, Germany, 1999.
  • 13. P.T. Joshi, The size of $L(1,\chi)$ for real nonprincipal residue characters $\chi$ with prime modulus, J. Number Theory 2 (1970), 58-73. MR 40:4215
  • 14. D.H. Lehmer, On the function $x^{2}+x+{A}$, Sphinx 6 (1937), 212-214, 1936 and 7:40.
  • 15. D.H. Lehmer, E. Lehmer, and D. Shanks, Integer sequences having prescribed quadratic character, Math. Comp. 24 (1970), no. 110, 433-451. MR 42:5889
  • 16. J.E. Littlewood, On the class number of the corpus ${P}(\surd - k)$, Proc. London Math. Soc. 27 (1928), 358-372.
  • 17. R.F. Lukes, A very fast electronic number sieve, Ph.D. thesis, University of Manitoba, Winnipeg, Manitoba, 1995.
  • 18. R.F. Lukes, C.D. Patterson, and H.C. Williams, Numerical sieving devices: Their history and some applications, Nieuw Archief voor Wiskunde (4) 13 (1995), 113-139. MR 96m:11082
  • 19. R.A. Mollin and H.C. Williams, Computation of the class number of a real quadratic field, Utilitas Mathematica 41 (1992), 259-308. MR 93d:11134
  • 20. S. Paulus, An algorithm of subexponential type computing the class group of quadratic orders over principal ideal domains, Algorithmic Number Theory - ANTS-II (Université Bordeaux I, Talence, France), Lecture Notes in Computer Science, vol. 1122, Springer-Verlag, Berlin, 1996, pp. 243-257. MR 98c:11143
  • 21. L. Poletti, Il contributo italiano alla tavola dei numeri primi, Rivista di Matematica della Università di Parma 2 (1951), 417-434. MR 14:121d
  • 22. M. Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), 757-780. MR 88d:11129
  • 23. D. Shanks, On the conjecture of Hardy and Littlewood concerning the number of primes of the form $n^{2}+a$, Math. Comp. 14 (1960), 320-332. MR 22:10960
  • 24. R.D. Silverman, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), 329-339. MR 88c:11079

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11R11, 11R29, 11Y40, 11Y16

Retrieve articles in all journals with MSC (2000): 11R11, 11R29, 11Y40, 11Y16

Additional Information

Michael J. Jacobson Jr.
Affiliation: Department of Computer Science, University of Manitoba, Winnipeg, Manitoba, Canada R3T 2N2

Hugh C. Williams
Affiliation: Department of Mathematics and Statistics, MS 360, 2500 University Drive N.W., University of Calgary, Calgary, Alberta, Canada T2N 1N4

Keywords: Prime-generating quadratic polynomial, quadratic order, class group
Received by editor(s): September 8, 1999
Received by editor(s) in revised form: February 28, 2001
Published electronically: May 2, 2002
Article copyright: © Copyright 2002 American Mathematical Society

American Mathematical Society