Density computations for real quadratic units

Bosma, Wieb; Stevenhagen, Peter

doi:10.1090/S0025-5718-96-00725-9

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.