Computation of the Euclidean minimum of algebraic number fields

Lezowski, Pierre

doi:10.1090/S0025-5718-2013-02746-9

Computation of the Euclidean minimum of algebraic number fields
HTML articles powered by AMS MathViewer

by Pierre Lezowski PDF

Math. Comp. 83 (2014), 1397-1426 Request permission

Abstract:

We present an algorithm to compute the Euclidean minimum of an algebraic number field, which is a generalization of the algorithm restricted to the totally real case described by Cerri in 2007. With a practical implementation, we obtain unknown values of the Euclidean minima of algebraic number fields of degree up to $8$ in any signature, especially for cyclotomic fields, and many new examples of norm-Euclidean or non-norm-Euclidean algebraic number fields. Then, we show how to apply the algorithm to study extensions of norm-Euclideanity.

References

E. S. Barnes and H. P. F. Swinnerton-Dyer, The inhomogeneous minima of binary quadratic forms. II, Acta Math. 88 (1952), 279–316. MR 54654, DOI 10.1007/BF02392135
Eva Bayer Fluckiger, Upper bounds for Euclidean minima of algebraic number fields, J. Number Theory 121 (2006), no. 2, 305–323. MR 2274907, DOI 10.1016/j.jnt.2006.03.002
Hermann Behrbohm and László Rédei, Der Euklidische Algorithmus in quadratischen Zahlkörpern, Journal für die reine und angewandte Mathematik 174 (1936), 192–205.
Stefania Cavallar and Franz Lemmermeyer, The Euclidean algorithm in cubic number fields, Number theory (Eger, 1996) de Gruyter, Berlin, 1998, pp. 123–146. MR 1628838, DOI 10.1023/A:1008244007194
Jean-Paul Cerri, Spectres euclidiens et inhomogènes des corps de nombres, Ph.D. thesis, Université Nancy 1, France, 2005.
—, Euclidean and inhomogeneous spectra of number fields with unit rank strictly greater than 1, Journal für die reine und angewandte Mathematik 592 (2006), 49–62.
Jean-Paul Cerri, Euclidean minima of totally real number fields: algorithmic determination, Math. Comp. 76 (2007), no. 259, 1547–1575. MR 2299788, DOI 10.1090/S0025-5718-07-01932-1
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
George E. Cooke, A weakening of the Euclidean property for integral domains and applications to algebraic number theory. I, J. Reine Angew. Math. 282 (1976), 133–156. MR 406973, DOI 10.1515/crll.1976.282.133
H. Davenport, Linear forms associated with an algebriac number-field, Quart. J. Math. Oxford Ser. (2) 3 (1952), 32–41. MR 47707, DOI 10.1093/qmath/3.1.32
Veikko Ennola, On the first inhomogeneous minimum of indefinite binary quadratic forms and Euclid’s algorithm in real quadratic fields, Ph.D. thesis, University of Turku, Finland, 1958.
David H. Johnson, Clifford S. Queen, and Alicia N. Sevilla, Euclidean real quadratic number fields, Arch. Math. (Basel) 44 (1985), no. 4, 340–347. MR 788948, DOI 10.1007/BF01235777
Franz Lemmermeyer, The Euclidean algorithm in algebraic number fields, Exposition. Math. 13 (1995), no. 5, 385–416. MR 1362867
H. W. Lenstra Jr., Euclidean number fields of large degree, Invent. Math. 38 (1976/77), no. 3, 237–254. MR 429826, DOI 10.1007/BF01403131
Hendrik W. Lenstra Jr., Euclidean number fields. I, Math. Intelligencer 2 (1979/80), no. 1, 6–15. MR 558668, DOI 10.1007/BF03024378
Pierre Lezowski, euclid, version 1.0, 2012, available from http://www.math.u-bordeaux1.fr/~lezowski/euclid/.
Robert Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput. 1 (1972), no. 2, 146–160. MR 304178, DOI 10.1137/0201010
The PARI Group, Bordeaux, PARI/GP, version 2.4.3, 2008, available from http://pari.math.u-bordeaux.fr/.
Franciscus Jozef van der Linden, Euclidean rings with two infinite primes, Ph.D. thesis, Centrum voor Wiskunde en Informatica, Amsterdam, Netherlands, 1984.