Density computations for real quadratic units
HTML articles powered by AMS MathViewer
- by Wieb Bosma and Peter Stevenhagen PDF
- Math. Comp. 65 (1996), 1327-1337 Request permission
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\; \mathrm {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
- B. D. Beach and H. C. Williams, A numerical investigation of the Diophantine equation $x^{2}-dy^{2}=-1$, Proceedings of the Third Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1972), Florida Atlantic Univ., Boca Raton, Fla., 1972, pp. 37–68. MR 0347729
- W. Bosma and P. Stevenhagen, On the computation of quadratic $2$-class groups, University of Amsterdam mathematical preprint series, report 95–04, 1995.
- Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
- C. F. Gauss, Disquisitiones Arithmeticae, Gerhard Fleischer, Leipzig, 1801.
- J. C. Lagarias, Worst-case complexity bounds for algorithms in the theory of integral quadratic forms, J. Algorithms 1 (1980), no. 2, 142–186. MR 604862, DOI 10.1016/0196-6774(80)90021-8
- 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 (1980), no. 2, 485–508. MR 574794, DOI 10.1090/S0002-9947-1980-0574794-0
- Patrick Morton, On Rédei’s theory of the Pell equation, J. Reine Angew. Math. 307(308) (1979), 373–398. MR 534233, DOI 10.1515/crll.1979.307-308.373
- 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.
- L. Rédei, Über einige Mittelwertfragen im quadratischen Zahlkörper, J. Reine Angew. Math. 174 (1936), 131–148.
- 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 (German). MR 174533, DOI 10.1515/crll.1965.217.200
- Peter Stevenhagen, The number of real quadratic fields having units of negative norm, Experiment. Math. 2 (1993), no. 2, 121–136. MR 1259426, DOI 10.1080/10586458.1993.10504272
- 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.
Additional Information
- Wieb Bosma
- Affiliation: School of Mathematics and Statistics, University of Sydney, Sydney NSW 2006, Australia
- Email: wieb@maths.su.oz.au
- Peter Stevenhagen
- Affiliation: Faculteit Wiskunde en Informatica, Universiteit van Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, The Netherlands
- MR Author ID: 167210
- Email: psh@fwi.uva.nl
- Received by editor(s): February 24, 1995
- © Copyright 1996 American Mathematical Society
- Journal: Math. Comp. 65 (1996), 1327-1337
- MSC (1991): Primary 11R11, 11Y40, 11R45; Secondary 11E16
- DOI: https://doi.org/10.1090/S0025-5718-96-00725-9
- MathSciNet review: 1344607