Computing points of bounded height in projective space over a number field

Krumm, David

doi:10.1090/mcom/2984

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