Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Computation of the Euclidean minimum of algebraic number fields

Author: Pierre Lezowski
Journal: Math. Comp. 83 (2014), 1397-1426
MSC (2010): Primary 11Y40; Secondary 11R04, 11A05, 13F07
Published electronically: July 19, 2013
MathSciNet review: 3167464
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. Eric S. Barnes and H. Peter F. Swinnerton-Dyer, The inhomogeneous minima of binary quadratic forms (II), Acta Mathematica 88 (1952), 279-316. MR 0054654 (14,956a)
  • 2. Eva Bayer-Fluckiger, Upper bounds for Euclidean minima of algebraic number fields, Journal of Number Theory 121 (2006), 305-323. MR 2274907 (2008a:11139)
  • 3. 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.
  • 4. Stefania Cavallar and Franz Lemmermeyer, The Euclidean algorithm in cubic number fields, Proceedings of Number Theory (Eger, 1996), Kálmán Gyõry, Attila Pethõ, and Vera T. Sos, eds., de Gruyter, 1998, pp. 123-146. MR 1628838 (99e:11137)
  • 5. Jean-Paul Cerri, Spectres euclidiens et inhomogènes des corps de nombres, Ph.D. thesis, Université Nancy 1, France, 2005.
  • 6. -, 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.
  • 7. -, Euclidean minima of totally real number fields. Algorithmic determination, Mathematics of Computation 76 (2007), 1547-1575. MR 2299788 (2008d:11143)
  • 8. Henri Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics, vol. 138, Springer, 1996. MR 1228206 (94i:11105)
  • 9. George E. Cooke, A weakening of the Euclidean property for integral domains and applications to algebraic number theory. I., Journal für die reine und angewandte Mathematik 282 (1976), 133-156. MR 0406973 (53 #10758a)
  • 10. Harold Davenport, Linear forms associated with an algebraic number field, Quarterly Journal of Mathematics 2 (1952), 32-41. MR 0047707 (13,918c)
  • 11. 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.
  • 12. David H. Johnson, Clifford S. Queen, and Alicia N. Sevilla, Euclidean real quadratic number fields, Archiv der Mathematik 44 (1985), 340-347. MR 0788948 (87g:11137)
  • 13. Franz Lemmermeyer, The Euclidean algorithm in algebraic number fields, Expositiones Mathematicae 13 (1995), 385-416; an updated version is available at MR 1362867 (96i:11115)
  • 14. Hendrik W. Lenstra, Jr., Euclidean number fields of large degree, Inventiones Mathematicae 38 (1976), no. 3, 237-254. MR 0429826 (55 #2836)
  • 15. -, Euclidean number fields 1, The Mathematical Intelligencer 2 (1979), no. 1, 6-15. MR 0558668 (81b:12002)
  • 16. Pierre Lezowski, euclid, version 1.0, 2012, available from
  • 17. Robert E. Tarjan, Depth-first search and linear graph algorithms, SIAM Journal on Computing 1 (1972), 146-160. MR 0304178 (46 #3313)
  • 18. The PARI Group, Bordeaux, PARI/GP, version 2.4.3, 2008, available from
  • 19. Franciscus Jozef van der Linden, Euclidean rings with two infinite primes, Ph.D. thesis, Centrum voor Wiskunde en Informatica, Amsterdam, Netherlands, 1984.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y40, 11R04, 11A05, 13F07

Retrieve articles in all journals with MSC (2010): 11Y40, 11R04, 11A05, 13F07

Additional Information

Pierre Lezowski
Affiliation: Université de Bordeaux, IMB, CNRS, UMR 5251, F-33400 Talence, France –and– INRIA, LFANT, F-33400 Talence, France

Keywords: Euclidean number fields, Euclidean minimum, inhomogeneous minimum
Received by editor(s): August 17, 2011
Received by editor(s) in revised form: May 2, 2012, and July 23, 2012
Published electronically: July 19, 2013
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society