|
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 , is related to the discriminant of via a quantity The larger is, the higher the asymptotic density of prime values for any quadratic polynomial of discriminant . A technique of Bach allows one to estimate accurately for any , given the class number of the imaginary quadratic order with discriminant , and for any given the class number and regulator of the real quadratic order with discriminant . The Manitoba Scalable Sieve Unit (MSSU) has shown us how to rapidly generate many discriminants for which is potentially large, and new methods for evaluating class numbers and regulators of quadratic orders allow us to compute accurate estimates of efficiently, even for values of with as many as decimal digits. Using these methods, we were able to find a number of discriminants for which, under the assumption of the Extended Riemann Hypothesis, 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
for real nonprincipal residue characters with prime modulus, J. Number Theory 2 (1970), 58-73. MR 40:4215 - 14.
- D.H. Lehmer, On the function
, 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
, 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
, 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
|