Computing algebraic numbers of bounded height

Doyle, John; Krumm, David

doi:10.1090/mcom/2954

Computing algebraic numbers of bounded height
HTML articles powered by AMS MathViewer

by John R. Doyle and David Krumm PDF

Math. Comp. 84 (2015), 2867-2891 Request permission

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 $|H_K(x)-B|<\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

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
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
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, DOI 10.1007/BFb0091539
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
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
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, DOI 10.1016/j.jsc.2003.04.003
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
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, DOI 10.1007/3-540-12868-9_{1}03
John Jones, Number fields, http://hobbes./a.qsu.edu/NFDB/.
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, DOI 10.1007/BF01457454
H. W. Lenstra Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. (N.S.) 26 (1992), no. 2, 211–244. MR 1129315, DOI 10.1090/S0273-0979-1992-00284-7
M. Ram Murty and Jeanine Van Order, Counting integral ideals in a number field, Expo. Math. 25 (2007), no. 1, 53–66. MR 2286834, DOI 10.1016/j.exmath.2006.08.001
Victor Y. Pan, Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding, J. Symbolic Comput. 33 (2002), no. 5, 701–733. Computer algebra (London, ON, 2001). MR 1919911, DOI 10.1006/jsco.2002.0531
A. Pethő and S. Schmitt, Elements with bounded height in number fields, Period. Math. Hungar. 43 (2001), no. 1-2, 31–41. MR 1830564, DOI 10.1023/A:1015225430108
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
Bjorn Poonen, The classification of rational preperiodic points of quadratic polynomials over $\textbf {Q}$: a refined conjecture, Math. Z. 228 (1998), no. 1, 11–29. MR 1617987, DOI 10.1007/PL00004405
Walter Rudin, Principles of mathematical analysis, 3rd ed., International Series in Pure and Applied Mathematics, McGraw-Hill Book Co., New York-Auckland-Düsseldorf, 1976. MR 0385023
Stephen Hoel Schanuel, Heights in number fields, Bull. Soc. Math. France 107 (1979), no. 4, 433–449 (English, with French summary). MR 557080
Joseph H. Silverman, The arithmetic of dynamical systems, Graduate Texts in Mathematics, vol. 241, Springer, New York, 2007. MR 2316407, DOI 10.1007/978-0-387-69904-2
W. A. Stein et al., Sage Mathematics Software (Version 5.9), The Sage Development Team, 2013, http://www.sagemath.org.
Christoph Thiel, Short proofs using compact representations of algebraic integers, J. Complexity 11 (1995), no. 3, 310–329. MR 1349260, DOI 10.1006/jcom.1995.1014