Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Computing algebraic numbers of bounded height


Authors: John R. Doyle and David Krumm
Journal: Math. Comp. 84 (2015), 2867-2891
MSC (2010): Primary 11Y16; Secondary 11Y40
DOI: https://doi.org/10.1090/mcom/2954
Published electronically: April 1, 2015
MathSciNet review: 3378851
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We describe an algorithm which, given a number field $ K$ and a bound $ B$, finds all the elements of $ K$ having relative height at most $ B$. Two lists of numbers are computed: one consisting of elements $ x\in K$ for which it is known with certainty that $ H_K(x)\leq B$, and one containing elements $ x$ such that $ \vert H_K(x)-B\vert<\theta $ for a tolerance $ \theta $ chosen by the user. We show that every element of $ K$ whose height is at most $ B$ must appear in one of the two lists.


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

  • [1] Alexander Barvinok and James E. Pommersheim, An algorithmic theory of lattice points in polyhedra, New perspectives in algebraic combinatorics (Berkeley, CA, 1996-97), Math. Sci. Res. Inst. Publ., vol. 38, Cambridge Univ. Press, Cambridge, 1999, pp. 91-147. MR 1731815 (2000k:52014)
  • [2] Johannes Buchmann, A subexponential algorithm for the determination of class groups and regulators of algebraic number fields, Séminaire de Théorie des Nombres, Paris 1988-1989, Progr. Math., vol. 91, Birkhäuser Boston, Boston, MA, 1990, pp. 27-41. MR 1104698 (92g:11125)
  • [3] J. P. Buhler, H. W. Lenstra Jr., and Carl Pomerance, Factoring integers with the number field sieve, The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, Berlin, 1993, pp. 50-94. MR 1321221, https://doi.org/10.1007/BFb0091539
  • [4] A. L. Chistov, The complexity of the construction of the ring of integers of a global field, Dokl. Akad. Nauk SSSR 306 (1989), no. 5, 1063-1067 (Russian); English transl., Soviet Math. Dokl. 39 (1989), no. 3, 597-600. MR 1014763 (90g:11170)
  • [5] Henri Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206 (94i:11105)
  • [6] Jesús A. De Loera, Raymond Hemmecke, Jeremiah Tauzer, and Ruriko Yoshida, Effective lattice point counting in rational convex polytopes, J. Symbolic Comput. 38 (2004), no. 4, 1273-1302. MR 2094541 (2005i:52020), https://doi.org/10.1016/j.jsc.2003.04.003
  • [7] John R. Doyle, Xander Faber, and David Krumm, Preperiodic points for quadratic polynomials over quadratic fields, New York J. Math. 20 (2014), 507-605. MR 3218788
  • [8] U. Fincke and M. Pohst, A procedure for determining algebraic integers of given norm, Computer algebra (London, 1983) Lecture Notes in Comput. Sci., vol. 162, Springer, Berlin, 1983, pp. 194-202. MR 774811 (86k:11078), https://doi.org/10.1007/3-540-12868-9_103
  • [9] John Jones, Number fields, http://hobbes./a.qsu.edu/NFDB/.
  • [10] A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515-534. MR 682664 (84a:12002), https://doi.org/10.1007/BF01457454
  • [11] H. W. Lenstra Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. (N.S.) 26 (1992), no. 2, 211-244. MR 1129315 (93g:11131), https://doi.org/10.1090/S0273-0979-1992-00284-7
  • [12] M. Ram Murty and Jeanine Van Order, Counting integral ideals in a number field, Expo. Math. 25 (2007), no. 1, 53-66. MR 2286834 (2007j:11161), https://doi.org/10.1016/j.exmath.2006.08.001
  • [13] Victor Y. Pan, Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding, Computer algebra, J. Symbolic Comput. 33 (2002), no. 5, 701-733. (London, ON, 2001). MR 1919911 (2003f:13030), https://doi.org/10.1006/jsco.2002.0531
  • [14] A. Pethő and S. Schmitt, Elements with bounded height in number fields, Period. Math. Hungar. 43 (2001), no. 1-2, 31-41. MR 1830564 (2002h:11061), https://doi.org/10.1023/A:1015225430108
  • [15] M. Pohst and H. Zassenhaus, Algorithmic Algebraic Number Theory, Encyclopedia of Mathematics and its Applications, vol. 30, Cambridge University Press, Cambridge, 1997. Revised reprint of the 1989 original. MR 1483321 (98f:11111)
  • [16] Bjorn Poonen, The classification of rational preperiodic points of quadratic polynomials over $ {\bf Q}$: a refined conjecture, Math. Z. 228 (1998), no. 1, 11-29. MR 1617987 (99j:11076), https://doi.org/10.1007/PL00004405
  • [17] Walter Rudin, Principles of Mathematical Analysis, 3rd ed., McGraw-Hill Book Co., New York-Auckland-Düsseldorf, 1976. International Series in Pure and Applied Mathematics. MR 0385023 (52 #5893)
  • [18] Stephen Hoel Schanuel, Heights in number fields, Bull. Soc. Math. France 107 (1979), no. 4, 433-449 (English, with French summary). MR 557080 (81c:12025)
  • [19] Joseph H. Silverman, The Arithmetic of Dynamical Systems, Graduate Texts in Mathematics, vol. 241, Springer, New York, 2007. MR 2316407 (2008c:11002)
  • [20] W. A. Stein et al., Sage Mathematics Software (Version 5.9), The Sage Development Team, 2013, http://www.sagemath.org.
  • [21] Christoph Thiel, Short proofs using compact representations of algebraic integers, J. Complexity 11 (1995), no. 3, 310-329. MR 1349260 (96d:11142), https://doi.org/10.1006/jcom.1995.1014

Similar Articles

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

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


Additional Information

John R. Doyle
Affiliation: Department of Mathematics, University of Georgia, Athens, Georgia 30602
Email: jdoyle@math.uga.edu

David Krumm
Affiliation: Department of Mathematics, University of Georgia, Athens, Georgia 30602
Email: david.krumm@gmail.com

DOI: https://doi.org/10.1090/mcom/2954
Received by editor(s): November 18, 2011
Received by editor(s) in revised form: October 19, 2012, June 22, 2013, August 3, 2013, and February 25, 2014
Published electronically: April 1, 2015
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society