Available in electronic format
Available in print format
Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
     

New quadratic polynomials with high densities of prime values

Author(s): Michael J. Jacobson Jr.; Hugh C. Williams.
Journal: Math. Comp. 72 (2003), 499-519.
MSC (2000): Primary 11R11, 11R29, 11Y40; Secondary 11Y16
Posted: May 2, 2002
Retrieve article in: PDF DVI PostScript

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:

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 http://www.informatik.tu-darmstadt.de/TI/LiDIA.

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
Email: jacobs@cs.umanitoba.ca

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

DOI: 10.1090/S0025-5718-02-01418-7
PII: S 0025-5718(02)01418-7
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
Posted: May 2, 2002
Copyright of article: Copyright 2002, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google