Computing points of bounded height in projective space over a number field
HTML articles powered by AMS MathViewer
- by David Krumm PDF
- Math. Comp. 85 (2016), 423-447 Request permission
Abstract:
We construct an algorithm for solving the following problem: given a number field $K$, a positive integer $N$, and a positive real number $B$, determine all points in $\mathbb {P}^N(K)$ having relative height at most $B$. A theoretical analysis of the efficiency of the algorithm is provided, as well as sample computations showing how the algorithm performs in practice. Two variants of the method are described, and examples are given to compare their running times. In the case $N=1$ we compare our method to an earlier algorithm for enumerating elements of bounded height in number fields.References
- V. Baldoni et al., A user’s guide for LattE integrale v1.6, 2013, Available online at http://www.math.ucdavis.edu/~latte/.
- 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
- Alexander I. Barvinok, A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Math. Oper. Res. 19 (1994), no. 4, 769–779. MR 1304623, DOI 10.1287/moor.19.4.769
- Jean-François Biasse, Improvements in the computation of ideal class groups of imaginary quadratic number fields, Adv. Math. Commun. 4 (2010), no. 2, 141–154. MR 2654130, DOI 10.3934/amc.2010.4.141
- 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
- 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
- L. Dembélé and A. Kumar, Examples of abelian surfaces with everywhere good reduction, Preprint, http://arxiv.org/abs/1309.3821.
- 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
- J. R. Doyle and D. Krumm, Computing algebraic numbers of bounded height, Math. Comp. Published electronically, April 1, 2015.
- 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
- U. Fincke and M. Pohst, Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comp. 44 (1985), no. 170, 463–471. MR 777278, DOI 10.1090/S0025-5718-1985-0777278-8
- 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
- Michael J. Jacobson Jr., Applying sieving to the computation of quadratic class groups, Math. Comp. 68 (1999), no. 226, 859–867. MR 1604324, DOI 10.1090/S0025-5718-99-01003-0
- S. Lang, Fundamentals of Diophantine Geometry, Springer-Verlag, New York, 1983.
- Serge Lang, Algebraic number theory, 2nd ed., Graduate Texts in Mathematics, vol. 110, Springer-Verlag, New York, 1994. MR 1282723, DOI 10.1007/978-1-4612-0853-2
- 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
- Phong Q. Nguyen and Damien Stehlé, An LLL algorithm with quadratic complexity, SIAM J. Comput. 39 (2009), no. 3, 874–903. MR 2538842, DOI 10.1137/070705702
- 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
- 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.
- M. Stoll, An explicit theory of heights for hyperelliptic jacobians of genus three, Preprint.
- Michael Stoll, On the height constant for curves of genus two, Acta Arith. 90 (1999), no. 2, 183–201. MR 1709054, DOI 10.4064/aa-90-2-183-201
- Michael Stoll, On the height constant for curves of genus two. II, Acta Arith. 104 (2002), no. 2, 165–182. MR 1914251, DOI 10.4064/aa104-2-6
- Martin Widmer, Counting primitive points of bounded height, Trans. Amer. Math. Soc. 362 (2010), no. 9, 4793–4829. MR 2645051, DOI 10.1090/S0002-9947-10-05173-1
- Martin Widmer, Lipschitz class, narrow class, and counting lattice points, Proc. Amer. Math. Soc. 140 (2012), no. 2, 677–689. MR 2846337, DOI 10.1090/S0002-9939-2011-10926-2
Additional Information
- David Krumm
- Affiliation: Department of Mathematics, Claremont McKenna College, Claremont, California 91711
- Email: dkrumm@cmc.edu
- Received by editor(s): April 10, 2014
- Received by editor(s) in revised form: August 2, 2014
- Published electronically: June 9, 2015
- © Copyright 2015 American Mathematical Society
- Journal: Math. Comp. 85 (2016), 423-447
- MSC (2010): Primary 11Y40
- DOI: https://doi.org/10.1090/mcom/2984
- MathSciNet review: 3404456