A rapid method of evaluating the regulator and class number of a pure cubic field
HTML articles powered by AMS MathViewer
- by H. C. Williams, G. W. Dueck and B. K. Schmid PDF
- Math. Comp. 41 (1983), 235-286 Request permission
Abstract:
Let $\mathcal {K} = \mathcal {Q}(\theta )$ be the algebraic number field formed by adjoining $\theta$ to the rationals $\mathcal {Q}$. Let R and h be, respectively, the regulator and class number of $\mathcal {K}$. Shanks has described a method of evaluating R for $\mathcal {Q}(\sqrt D )$, where D is a positive integer. His technique improved the speed of the usual continued fraction algorithm for finding R by allowing one to proceed almost directly from the nth to the mth step, where m is approximately 2n, in the continued fraction expansion of $\sqrt D$. This paper shows how Shanks’ idea can be extended to the Voronoi algorithm, which is used to find R in cubic fields of negative discriminant. It also discusses at length an algorithm for finding R and h for pure cubic fields $\mathcal {Q}(\sqrt [3]{D})$, D an integer. Under a certain generalized Riemann Hypothesis the ideas developed here will provide a new method which will find R and h in $O({D^{2/5 + \varepsilon }})$ operations. When h is small, this is an improvement over the $O(D/h)$ operations required by Voronoi’s algorithm to find R. For example, with $D = 200171999$, it required only 5 minutes for an AMDAHL 470/V7 computer to find that $R = 518594546.969083$ and $h = 1$. This same calculation would require about 8 days of computer time if it used only the standard Voronoi algorithm.References
- Pierre Barrucand, H. C. Williams, and L. Baniuk, A computational technique for determining the class number of a pure cubic field, Math. Comp. 30 (1976), no. 134, 312–323. MR 392913, DOI 10.1090/S0025-5718-1976-0392913-9 W. E. H. Berwick, "The classification of ideal numbers that depend on a cubic irrationality," Proc. London Math. Soc., v. 12, 1913, pp. 393-429. W. E. H. Berwick, "The arithmetic of quadratic number fields," Math. Gazette, v. 14, 1928, pp. 1-11.
- J. W. S. Cassels, The rational solutions of the diophantine equation $Y^2=X^3-D$, Acta Math. 82 (1950), 243–273. MR 35782, DOI 10.1007/BF02398279
- Gary Cornell and Lawrence C. Washington, Class numbers of cyclotomic fields, J. Number Theory 21 (1985), no. 3, 260–274. MR 814005, DOI 10.1016/0022-314X(85)90055-1
- B. N. Delone and D. K. Faddeev, The theory of irrationalities of the third degree, Translations of Mathematical Monographs, Vol. 10, American Mathematical Society, Providence, R.I., 1964. MR 0160744
- J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR 0447191 E. Landau, Vorlesungen über Zahlentheorie, Vol. II, Chelsea, New York, 1955. H. W. Lenstra, Jr., On the Calculation of Regulators and Class Numbers of Quadratic Fields, Report 80-08, Mathematisch Instituut, Amsterdam, 1980. J. Oesterlé, "Versions effectives du théorème de Chebotarev sous l’hypothése de Riemann généralisée," Astérisque, v. 61, 1979, pp. 165-167.
- H. Zantema, Class numbers and units, Computational methods in number theory, Part II, Math. Centre Tracts, vol. 155, Math. Centrum, Amsterdam, 1982, pp. 213–234. MR 702518
- Daniel Shanks, The infrastructure of a real quadratic field and its applications, Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, Colo., 1972) Univ. Colorado, Boulder, Colo., 1972, pp. 217–224. MR 0389842
- Daniel Shanks, A survey of quadratic, cubic and quartic algebraic number fields (from a computational point of view), Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Congressus Numerantium, No. XVII, Utilitas Math., Winnipeg, Man., 1976, pp. 15–40. MR 0453691 G. F. Voronoi, Concerning Algebraic Integers Derivable from a Root of an Equation of the Third Degree, Master’s Thesis, St. Petersburg, 1894. (Russian) G. F. Voronoi, On a Generalization of the Algorithm of Continued Fractions, Doctoral Dissertation, Warsaw, 1896. (Russian)
- H. C. Williams, Improving the speed of calculating the regulator of certain pure cubic fields, Math. Comp. 35 (1980), no. 152, 1423–1434. MR 583520, DOI 10.1090/S0025-5718-1980-0583520-4
- H. C. Williams, Some results concerning Voronoĭ’s continued fraction over $\textbf {Q}(\root 3\of {D})$, Math. Comp. 36 (1981), no. 154, 631–652. MR 606521, DOI 10.1090/S0025-5718-1981-0606521-7
- H. C. Williams, G. Cormack, and E. Seah, Calculation of the regulator of a pure cubic field, Math. Comp. 34 (1980), no. 150, 567–611. MR 559205, DOI 10.1090/S0025-5718-1980-0559205-7
- H. C. Williams and Daniel Shanks, A note on class-number one in pure cubic fields, Math. Comp. 33 (1979), no. 148, 1317–1320. MR 537977, DOI 10.1090/S0025-5718-1979-0537977-7
Additional Information
- © Copyright 1983 American Mathematical Society
- Journal: Math. Comp. 41 (1983), 235-286
- MSC: Primary 12A50; Secondary 12-04, 12A30, 12A45
- DOI: https://doi.org/10.1090/S0025-5718-1983-0701638-2
- MathSciNet review: 701638