Unconditional class group tabulation of imaginary quadratic fields to |Δ|<2⁴⁰

Mosunov, A.; M. J. Jacobson, Jr.

doi:10.1090/mcom3050

Unconditional class group tabulation of imaginary quadratic fields to $|\Delta | < 2^{40}$
HTML articles powered by AMS MathViewer

by A. S. Mosunov and Jr. M. J. Jacobson PDF

Math. Comp. 85 (2016), 1983-2009 Request permission

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 $|\Delta | < 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

Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355–380. MR 1023756, DOI 10.1090/S0025-5718-1990-1023756-8
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, DOI 10.1016/0009-2614(95)01161-4
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, DOI 10.1090/S0002-9904-1924-03891-9
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, DOI 10.1090/S0025-5718-97-00880-6
A. Borodin and R. Moenck, Fast modular transforms, J. Comput. System Sci. 8 (1974), 366–386. MR 371144, DOI 10.1016/S0022-0000(74)80029-2
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, DOI 10.1090/crmp/019/05
P. J. Cho, Sum of three squares and class numbers of imaginary quadratic fields, Proceedings of the Japan Academy 87, 2011, pp. 91–94.
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, DOI 10.1007/BFb0071539
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
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
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
Emil Grosswald, Representations of integers as sums of squares, Springer-Verlag, New York, 1985. MR 803155, DOI 10.1007/978-1-4613-8566-0
W. B. Hart, FLINT: Fast Library for Number Theory, version 2.4.1, http://www.flintlib.org, 2014.
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, DOI 10.1090/S0894-0347-1989-1002631-0
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, DOI 10.1007/978-3-642-14518-6_{1}7
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, DOI 10.1007/11792086_{7}
Ernst Kani, Idoneal numbers and some generalizations, Ann. Sci. Math. Québec 35 (2011), no. 2, 197–227 (English, with English and French summaries). MR 2917832
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.
E. Landau, Über die Klassenzahl imaginär-quadratischer Zahlkörper, Ges. Wiss. Göttingen, Math.-Phys., 1918, pp. 285–295.
J. E. Littlewood, On the class number of the corpus $P(\sqrt {-k})$, Proceedings of the London Mathematical Society 27, 1928, pp. 358–372.
The LMFDB Collaboration, The $L$-functions and Modular Forms Database, 2015.
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
Daniel C. Mayer, The second $p$-class group of a number field, Int. J. Number Theory 8 (2012), no. 2, 471–505. MR 2890488, DOI 10.1142/S179304211250025X
A. S. Mosunov, Unconditional class group tabulation to $2^{40}$, Master’s thesis, University of Calgary, Calgary, Alberta, 2014.
A. S. Mosunov, Class group tabulation program, https://github.com/amosunov, 2014.
The PARI Group, PARI/GP version 2.7.1, http://pari.math.u-bordeaux.fr, Bordeaux, 2014.
Olivier Ramaré, Approximate formulae for $L(1,\chi )$, Acta Arith. 100 (2001), no. 3, 245–266. MR 1865385, DOI 10.4064/aa100-3-2
S. Ramachandran, Class groups of quadratic fields, Master’s thesis, University of Calgary, Calgary, Alberta, 2006.
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.
M. Sayles, C libraries optarith and qform for fast binary quadratic form arithmetic, https://github.com/maxwellsayles, 2013.
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
Andrew V. Sutherland, Structure computation and discrete logarithms in finite abelian $p$-groups, Math. Comp. 80 (2011), no. 273, 477–500. MR 2728991, DOI 10.1090/S0025-5718-10-02356-2
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, DOI 10.1016/0097-3165(91)90016-A
G. N. Watson, Generating functions of class-numbers, Compositio Math. 1 (1935), 39–68. MR 1556875
P. J. Weinberger, Exponents of the class groups of complex quadratic fields, Acta Arith. 22 (1973), 117–124. MR 313221, DOI 10.4064/aa-22-2-117-124
Hungabee specification, https://www.westgrid.ca/support/systems/Hungabee, 2014.