Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Unconditional class group tabulation of imaginary quadratic fields to $ \Vert\Delta\Vert < 2^{40}$


Authors: A. S. Mosunov and M. J. Jacobson, Jr.
Journal: Math. Comp. 85 (2016), 1983-2009
MSC (2010): Primary 11R29; Secondary 11R11, 11Y40
DOI: https://doi.org/10.1090/mcom3050
Published electronically: November 3, 2015
MathSciNet review: 3471116
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present an improved algorithm for tabulating class groups of imaginary quadratic fields of bounded discriminant. Our method uses classical class number formulas involving theta-series to compute the group orders unconditionally for all $ \Delta \not \equiv 1 \pmod {8}.$ The group structure is resolved using the factorization of the group order. The $ 1 \bmod 8$ case was handled using the methods of Jacobson, Ramachandran, and Williams including the batch verification method based on the Eichler-Selberg trace formula to remove dependence on the Extended Riemann Hypothesis. Our new method enabled us to extend the previous bound of $ \vert\Delta \vert < 2 \cdot 10^{11}$ to $ 2^{40}$. Statistical data in support of a variety of conjectures is presented, along with new examples of class groups with exotic structures.


References [Enhancements On Off] (What's this?)

  • [1] Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355-380. MR 1023756 (91m:11096), https://doi.org/10.2307/2008811
  • [2] Eric Bach, Improved approximations for Euler products, Number theory (Halifax, NS, 1994) CMS Conf. Proc., vol. 15, Amer. Math. Soc., Providence, RI, 1995, pp. 13-28. MR 1353917 (96i:11124)
  • [3] E. T. Bell, The class number relations implicit in the Disquisitiones Arithmeticae, Bull. Amer. Math. Soc. 30 (1924), no. 5-6, 236-238. MR 1560883, https://doi.org/10.1090/S0002-9904-1924-03891-9
  • [4] Johannes Buchmann, Michael J. Jacobson Jr., and Edlyn Teske, On some computational problems in finite abelian groups, Math. Comp. 66 (1997), no. 220, 1663-1687. MR 1432126 (98a:11185), https://doi.org/10.1090/S0025-5718-97-00880-6
  • [5] A. Borodin and R. Moenck, Fast modular transforms, J. Comput. System Sci. 8 (1974), 366-386. Thirteenth Annual IEEE Symposium on Switching and Automata Theory (Univ. Maryland, College Park, Md., 1972). MR 0371144 (51 #7365)
  • [6] Duncan A. Buell, The last exhaustive computation of class groups of complex quadratic number fields, Number theory (Ottawa, ON, 1996) CRM Proc. Lecture Notes, vol. 19, Amer. Math. Soc., Providence, RI, 1999, pp. 35-53. MR 1684589 (2000d:11156)
  • [7] P. J. Cho, Sum of three squares and class numbers of imaginary quadratic fields, Proceedings of the Japan Academy 87, 2011, pp. 91-94.
  • [8] H. Cohen and H. W. Lenstra Jr., Heuristics on class groups, Number theory (New York, 1982) Lecture Notes in Math., vol. 1052, Springer, Berlin, 1984, pp. 26-36. MR 750661, https://doi.org/10.1007/BFb0071539
  • [9] Henri Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206 (94i:11105)
  • [10] Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757 (2004g:68202)
  • [11] Carl Friedrich Gauss, Disquisitiones arithmeticae, Springer-Verlag, New York, 1986. Translated and with a preface by Arthur A. Clarke; Revised by William C. Waterhouse, Cornelius Greither and A. W. Grootendorst and with a preface by Waterhouse. MR 837656 (87f:01105)
  • [12] Emil Grosswald, Representations of Integers as Sums of Squares, Springer-Verlag, New York, 1985. MR 803155 (87g:11002)
  • [13] W. B. Hart, FLINT: Fast Library for Number Theory, version 2.4.1, http://www.flintlib.org, 2014.
  • [14] James L. Hafner and Kevin S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2 (1989), no. 4, 837-850. MR 1002631 (91f:11090), https://doi.org/10.2307/1990896
  • [15] William B. Hart, Gonzalo Tornaría, and Mark Watkins, Congruent number theta coefficients to $ 10^{12}$, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 6197, Springer, Berlin, 2010, pp. 186-200. MR 2721421 (2011m:11063), https://doi.org/10.1007/978-3-642-14518-6_17
  • [16] Michael J. Jacobson Jr., Shantha Ramachandran, and Hugh C. Williams, Numerical results on class groups of imaginary quadratic fields, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 4076, Springer, Berlin, 2006, pp. 87-101. MR 2282917 (2007j:11178), https://doi.org/10.1007/11792086_7
  • [17] Ernst Kani, Idoneal numbers and some generalizations, Ann. Sci. Math. Québec 35 (2011), no. 2, 197-227. MR 2917832
  • [18] L. Kronecker, Über die Anzahl der verschiedenen classen quadratischer Formen von negativer Determinante, Journal für die reine und angewandte Mathematik 57 (4), 1860, pp. 248-255.
  • [19] E. Landau, Über die Klassenzahl imaginär-quadratischer Zahlkörper, Ges. Wiss. Göttingen, Math.-Phys., 1918, pp. 285-295.
  • [20] J. E. Littlewood, On the class number of the corpus $ P(\sqrt {-k})$, Proceedings of the London Mathematical Society 27, 1928, pp. 358-372.
  • [21] The LMFDB Collaboration, The $ L$-functions and Modular Forms Database, 2015.
  • [22] Kevin S. McCurley, Cryptographic key distribution and computation in class groups, Number theory and applications (Banff, AB, 1988) NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 265, Kluwer Acad. Publ., Dordrecht, 1989, pp. 459-479. MR 1123090 (92e:11149)
  • [23] Daniel C. Mayer, The second $ p$-class group of a number field, Int. J. Number Theory 8 (2012), no. 2, 471-505. MR 2890488, https://doi.org/10.1142/S179304211250025X
  • [24] A. S. Mosunov, Unconditional class group tabulation to $ 2^{40}$, Master's thesis, University of Calgary, Calgary, Alberta, 2014.
  • [25] A. S. Mosunov, Class group tabulation program, https://github.com/amosunov, 2014.
  • [26] The PARI Group, PARI/GP version 2.7.1, http://pari.math.u-bordeaux.fr, Bordeaux, 2014.
  • [27] Olivier Ramaré, Approximate formulae for $ L(1,\chi )$, Acta Arith. 100 (2001), no. 3, 245-266. MR 1865385 (2002k:11144), https://doi.org/10.4064/aa100-3-2
  • [28] S. Ramachandran, Class groups of quadratic fields, Master's thesis, University of Calgary, Calgary, Alberta, 2006.
  • [29] M. Sayles, Improved arithmetic in the ideal class group of imaginary quadratic fields with an application to integer factoring, Master's thesis, University of Calgary, Calgary, Alberta, 2013.
  • [30] M. Sayles, C libraries optarith and qform for fast binary quadratic form arithmetic, https://github.com/maxwellsayles, 2013.
  • [31] Daniel Shanks, Systematic examination of Littlewood's bounds on $ L(1,\,\chi )$, Analytic number theory (Proc. Sympos. Pure Math., Vol. XXIV, St. Louis Univ., St. Louis, Mo., 1972) Amer. Math. Soc., Providence, R.I., 1973, pp. 267-283. MR 0337827 (49 #2596)
  • [32] Andrew V. Sutherland, Structure computation and discrete logarithms in finite abelian $ p$-groups, Math. Comp. 80 (2011), no. 273, 477-500. MR 2728991 (2012d:20112), https://doi.org/10.1090/S0025-5718-10-02356-2
  • [33] René Schoof and Marcel van der Vlugt, Hecke operators and the weight distributions of certain codes, J. Combin. Theory Ser. A 57 (1991), no. 2, 163-186. MR 1111555 (92g:94017), https://doi.org/10.1016/0097-3165(91)90016-A
  • [34] G. N. Watson, Generating functions of class-numbers, Compositio Math. 1 (1935), 39-68. MR 1556875
  • [35] P. J. Weinberger, Exponents of the class groups of complex quadratic fields, Acta Arith. 22 (1973), 117-124. MR 0313221 (47 #1776)
  • [36] Hungabee specification, https://www.westgrid.ca/support/systems/Hungabee, 2014.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11R29, 11R11, 11Y40

Retrieve articles in all journals with MSC (2010): 11R29, 11R11, 11Y40


Additional Information

A. S. Mosunov
Affiliation: University of Waterloo, 200 University Avenue W, Waterloo, Ontario, Canada N2L 3G1
Email: amosunov@uwaterloo.ca

M. J. Jacobson, Jr.
Affiliation: University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4
Email: jacobs@cpsc.ucalgary.ca

DOI: https://doi.org/10.1090/mcom3050
Keywords: Binary quadratic form, class group, tabulation, out-of-core multiplication, Cohen-Lenstra heuristics
Received by editor(s): October 21, 2014
Received by editor(s) in revised form: February 12, 2015
Published electronically: November 3, 2015
Additional Notes: The first author’s research was supported by “Alberta Innovates Technology Futures”, Canada.
The second author’s research was supported by NSERC of Canada.
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society