Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Density computations for real quadratic units

Authors: Wieb Bosma and Peter Stevenhagen
Journal: Math. Comp. 65 (1996), 1327-1337
MSC (1991): Primary 11R11, 11Y40, 11R45; Secondary 11E16
MathSciNet review: 1344607
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In order to study the density of the set of positive integers $d$ for which the negative Pell equation $x^{2}-dy^{2}=-1$ is solvable in integers, we compute the norm of the fundamental unit in certain well-chosen families of real quadratic orders. A fast algorithm that computes 2-class groups rather than units is used. It is random polynomial-time in $\log d$ as the factorization of $d$ is a natural part of the input for the values of $d$ we encounter. The data obtained provide convincing numerical evidence for the density heuristics for the negative Pell equation proposed by the second author. In particular, an irrational proportion $P=1-\prod _{j\ge 1 \text {\rm \ odd}} (1-2^{-j}) \approx .58$ of the real quadratic fields without discriminantal prime divisors congruent to 3 mod 4 should have a fundamental unit of norm $-1$.

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

  • 1. B. D. Beach and H. C. Williams, A numerical investigation of the Diophantine equation $x^{2}-dy^{2}=-1$, Proc. 3rd Southeastern Conf. on Combinatorics, Graph Theory and Computing, 1972, pp. 37--52. MR 50:231
  • 2. W. Bosma and P. Stevenhagen, On the computation of quadratic $2$-class groups, University of Amsterdam mathematical preprint series, report 95--04, 1995.
  • 3. H. Cohen, A course in computational algebraic number theory, Springer Graduate Texts in Math., vol. 138, Berlin and New York, 1993. MR 94i:11105
  • 4. C. F. Gauss, Disquisitiones Arithmeticae, Gerhard Fleischer, Leipzig, 1801.
  • 5. J. C. Lagarias, Worst-case complexity bounds for algorithms in the theory of integral quadratic forms, J. Algorithms 1 (1980), 142--186. MR 83e:90112
  • 6. J. C. Lagarias, On the computational complexity of determining the solvability or unsolvability of the equation $X^{2}-DY^{2}=-1$, Trans. Amer. Math. Soc. 260 (2) (1980), 485--508. MR 81g:10029
  • 7. P. Morton, On Rédei's theory of the Pell equation, J. Reine Angew. Math. 307/8 (1979), 373--398. MR 81f:12005
  • 8. T. Nagell, Über die Lösbarkeit der Gleichung $x^{2}-Dy^{2}=-1$, Arkiv för Mat., Astr., o. Fysik 23 (B/6) (1932), 1--5.
  • 9. L. Rédei, Über einige Mittelwertfragen im quadratischen Zahlkörper, J. Reine Angew. Math. 174 (1936), 131--148.
  • 10. G. J. Rieger, Über die Anzahl der als Summe von zwei Quadraten darstellbaren und in einer primen Restklasse gelegenen Zahlen unterhalb einer positiven Schranke. II, J. Reine Angew. Math. 217 (1965), 200--216. MR 30:4734
  • 11. P. Stevenhagen, The number of real quadratic fields having units of negative norm, Exp. Math. 2 (2) (1993), 121--136. MR 94k:11120
  • 12. P. Stevenhagen, A density conjecture for the negative Pell equation, Computational Algebra and Number Theory, Mathematics and its Applications, vol. 325, Kluwer Academic Publishers, 1995, pp. 187--200.

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11R11, 11Y40, 11R45, 11E16

Retrieve articles in all journals with MSC (1991): 11R11, 11Y40, 11R45, 11E16

Additional Information

Wieb Bosma
Affiliation: School of Mathematics and Statistics, University of Sydney, Sydney NSW 2006, Australia

Peter Stevenhagen
Affiliation: Faculteit Wiskunde en Informatica, Universiteit van Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, The Netherlands

Keywords: Real quadratic class groups, negative Pell equation, density theorems
Received by editor(s): February 24, 1995
Article copyright: © Copyright 1996 American Mathematical Society

American Mathematical Society