A rapid method of evaluating the regulator and class number of a pure cubic field

Authors:
H. C. Williams, G. W. Dueck and B. K. Schmid

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

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let be the algebraic number field formed by adjoining to the rationals . Let *R* and *h* be, respectively, the regulator and class number of . Shanks has described a method of evaluating *R* for , 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 *n*th to the *m*th step, where *m* is approximately 2*n*, in the continued fraction expansion of . 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 , *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 operations. When *h* is small, this is an improvement over the operations required by Voronoi's algorithm to find *R*. For example, with , it required only 5 minutes for an AMDAHL 470/*V*7 computer to find that and . This same calculation would require about 8 days of computer time if it used only the standard Voronoi algorithm.

**[1]**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**0392913**, https://doi.org/10.1090/S0025-5718-1976-0392913-9**[2]**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.**[3]**W. E. H. Berwick, "The arithmetic of quadratic number fields,"*Math. Gazette*, v. 14, 1928, pp. 1-11.**[4]**J. W. S. Cassels,*The rational solutions of the diophantine equation 𝑌²=𝑋³-𝐷*, Acta Math.**82**(1950), 243–273. MR**0035782**, https://doi.org/10.1007/BF02398279**[5]**Gary Cornell and Lawrence C. Washington,*Class numbers of cyclotomic fields*, J. Number Theory**21**(1985), no. 3, 260–274. MR**814005**, https://doi.org/10.1016/0022-314X(85)90055-1**[6]**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****[7]**J. C. Lagarias and A. M. Odlyzko,*Effective versions of the Chebotarev density theorem*, Algebraic number fields: 𝐿-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR**0447191****[8]**E. Landau,*Vorlesungen über Zahlentheorie*, Vol. II, Chelsea, New York, 1955.**[9]**H. W. Lenstra, Jr.,*On the Calculation of Regulators and Class Numbers of Quadratic Fields*, Report 80-08, Mathematisch Instituut, Amsterdam, 1980.**[10]**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.**[11]**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**

R. J. Schoof,*Quadratic fields and factorization*, Computational methods in number theory, Part II, Math. Centre Tracts, vol. 155, Math. Centrum, Amsterdam, 1982, pp. 235–286. MR**702519****[12]**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****[13]**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), Utilitas Math., Winnipeg, Man., 1976, pp. 15–40. Congressus Numerantium, No. XVII. MR**0453691****[14]**G. F. Voronoi,*Concerning Algebraic Integers Derivable from a Root of an Equation of the Third Degree*, Master's Thesis, St. Petersburg, 1894. (Russian)**[15]**G. F. Voronoi,*On a Generalization of the Algorithm of Continued Fractions*, Doctoral Dissertation, Warsaw, 1896. (Russian)**[16]**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**, https://doi.org/10.1090/S0025-5718-1980-0583520-4**[17]**H. C. Williams,*Some results concerning Voronoĭ’s continued fraction over 𝑄(\root3\of{𝐷})*, Math. Comp.**36**(1981), no. 154, 631–652. MR**606521**, https://doi.org/10.1090/S0025-5718-1981-0606521-7**[18]**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**, https://doi.org/10.1090/S0025-5718-1980-0559205-7**[19]**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**, https://doi.org/10.1090/S0025-5718-1979-0537977-7

Retrieve articles in *Mathematics of Computation*
with MSC:
12A50,
12-04,
12A30,
12A45

Retrieve articles in all journals with MSC: 12A50, 12-04, 12A30, 12A45

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1983-0701638-2

Article copyright:
© Copyright 1983
American Mathematical Society