Mathematics of Computation

Relative class number of imaginary Abelian fields of prime conductor below 10000

Author(s): M. A. Shokrollahi.
Journal: Math. Comp. 68 (1999), 1717-1728.
MSC (1991): Primary 11Y40, 11R18, 11R29
Posted: May 24, 1999
Retrieve article in: PDF DVI PostScript
This article is available free of charge

Abstract: In this paper we compute the relative class number of all imaginary Abelian fields of prime conductor below 10000. Our approach is based on a novel multiple evaluation technique, and, assuming the ERH, it has a running time of $O(p^2\log^2(p)\log\log(p))$ , where

is the conductor of the field.

1.: C. Batut, D. Bernardi, H. Cohen, and M. Olivier, User's Guide to PARI-GP, Université Bordeaux, 351 Cours de la Libération, May 1995. Obtainable via anonymous ftp from megrez.math.u-bordeaux.fr.
2.: L. I. Bluestein, A linear filtering approach to the computation of the discrete Fourier transform, IEEE Trans. Electroacoustics 18 (1970), 451-455.
3.: A. Borodin and R. Moenck, Fast modular transforms, J. Comput. System Sci., 8 (1974), 366-386. MR 51:7365
4.: J. Buhler, R. Crandall, R. Ernvall, T. Metsänkylä and M. A. Shokrollahi, Irregular primes below 8 million, J. Symbolic Comput. (submitted)
5.: P. Bürgisser, M. Clausen, and M. A. Shokrollahi, Algebraic complexity theory, Springer-Verlag, 1997. CMP 97:10
6.: L. Carlitz and F. R. Olson, Maillet's determinant, Proc. Amer. Math. Soc., 6 (1955), 265-269. MR 16:999d
7.: H. Cohen, A course in computational algebraic number theory, Springer-Verlag, 1993. MR 94i:11105
8.: G. E. Collins, M. Mignotte, and F. Winkler, Arithmetic in basic algebraic domains, Computer algebra, symbolic and algebraic computation, (B. Buchberger et al., eds.), 2nd ed., Springer-Verlag, Vienna, 1982, pp. 189-220. MR 87a:68024
9.: D. Davis, Computing the number of totally positive circular units which are squares, J. Number Theory 10 (1978), 1-9. MR 57:16254
10.: D. R. Estes, On the parity of the class number of the field of qth roots of unity, Rocky Mountain J. Math. 19 (1989), 675-682. MR 92b:11078
11.: G. Fung, A. Granville and H. C. Williams, Computation of the first factor of the class number of cyclotomic fields, J. Number Theory 42 (1992), 297-312. MR 93k:11097
12.: H. Hasse, Über die Klassenzahl abelscher Zahlkörper, Akademie-Verlag, Berlin, 1952; reprinted with an introduction by J. Martinet, Springer-Verlag, 1985. MR 14:141a; MR 87j:11122
13.: V. Jha, Faster computation of the first factor of the class number of $\mathbf{Q}(\zeta _p)$ , Math. Comp. 64 (1995), 1705-1710. MR 95m:11120
14.: E. E. Kummer, Mémoire sur la théorie des nombres complexes composés de racines de l'unité et des nombres entiers, J. Math. Pures Appl. 16 (1851), 377-498; reprinted in his Collected papers, Vol. I, Springer-Verlag, 1975, pp. 363-484. MR 57:5650
15.: C. G. Latimer, On the units in a cyclic field, Amer. J. Math. 56 (1934), 69-74.
16.: D. H. Lehmer and J. M. Masley, Table of cyclotomic class numbers and their factors for , Math. Comp. 32 (1978), 577-582. MR 58:16594
17.: H. W. Lenstra, Private communication, 1997.
18.: T. Lepistö, On the growth of the first factor of the class number of the prime cyclotomic field, Ann. Acad. Sci. Fenn. Ser. A I No. 577 (1974). MR 50:273
19.: S. Louboutin, Computation of relative class numbers of imaginary abelian fields, Expositiones Math. (to appear).
20.: T. Metsänkylä, Some divisibility results for the cyclotomic class number, Tatra Mt. Math. Publ. 11 (1997), 59-68. MR 98i:11093
21.: G. Miller, Riemann's hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), 300-317. MR 58:470
22.: M. Newman, A table of the first factor for prime cyclotomic fields, Math. Comp. 24 (1970), 215-219. MR 41:1684
23.: A. M. Odlyzko, On conductors and discriminants, Algebraic number fields (A. Fröhlich, ed.), Academic Press, London, 1977, pp. 377-407. MR 56:11961
24.: J. Oesterlé, Versions effectives du théorème de Chebotarev sous l'hypothèse de Riemann généralisée, Astérisque 61 (1979), 165-167. MR 80j:10003
25.: S. Pajunen, Computation of the growth of the first factor for prime cyclotomic fields, BIT, 16 (1976), 85-87. MR 53:5533
26.: D. Reischert, Private communication, 1995.
27.: A. Schönhage, Schnelle Berechnung von Kettenbruchentwicklungen, Acta Informatica 1 (1971), 139-144. MR 55:9604
28.: A. Schönhage, Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients, Computer Algebra EUROCAM '82 (J. Calmet, ed.), Lecture Nots in Computer Science 144 (1982), 3-15. MR 83m:68064
29.: A. Schönhage, A. Grotefeld, and E. Vetter, Fast algorithms, Bibliographisches Institut, Mannheim, 1994. MR 96c:68043
30.: A. Schönhage and V. Strassen, Schnelle Multiplikation großer Zahlen, Computing (Arch. Elektion. Rechnung) 7 (1971), 281-292.
31.: M. A. Shokrollahi, Computation of irregular primes up to eight million, Technical Report TR-96-002, International Computer Science Institute, 1995.
32.: M. A. Shokrollahi, Stickelberger codes, Designs, Codes and Cryptography, 9 (1996), 1-11.
33.: P. Stevenhagen, Class number parity for the pth cyclotomic field, Math. Comp. 69 (1994), 773-784. MR 95a:11099
34.: O. Taussky, Unimodular integral circulants, Math. Z., 63 (1955), 286-298. MR 17:347i
35.: G. Schrutka von Rechtenstamm, Tabelle der (Relativ)-klassenzahlen der Kreiskörper, deren Wurzelexponenten nicht größer als 256 sind, Abh. Deutsch. Akad. Wiss. Berlin Kl. Math. Phys. Tech., 2 (1964), 1-64. MR 29:4918
36.: L. C. Washington, Introduction to cyclotomic fields, 2nd ed., Springer-Verlag, 1997. MR 97h:11130
37.: K. Yoshino and M. Hirabayashi, On the relative class number of imaginary abelian number field. I, II Mem. Coll. Liberal Arts, Kanazawa Medical Univ., 9 (1981), 5-53; 10 (1982), 33-81.

Retrieve articles in Mathematics of Computation with MSC (1991): 11Y40, 11R18, 11R29

M. A. Shokrollahi
Affiliation: Bell Labs 2C-353, Lucent Technologies, 700 Mountain Avenue, Murray Hill, New Jersey 07974-0636
Email: amin@research.bell-labs.com

DOI: 10.1090/S0025-5718-99-01139-4
PII: S 0025-5718(99)01139-4
Received by editor(s): November 17, 1997
Posted: May 24, 1999
Copyright of article: Copyright 1999, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS