Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 
 

 

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


Author: David Krumm
Journal: Math. Comp. 85 (2016), 423-447
MSC (2010): Primary 11Y40
DOI: https://doi.org/10.1090/mcom/2984
Published electronically: June 9, 2015
MathSciNet review: 3404456
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

  • [1] V. Baldoni et al., A user's guide for LattE integrale v1.6, 2013, Available online at http://www.math.ucdavis.edu/~latte/.
  • [2] 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)
  • [3] 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 (96c:52026), https://doi.org/10.1287/moor.19.4.769
  • [4] 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 (2011e:11192), https://doi.org/10.3934/amc.2010.4.141
  • [5] 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)
  • [6] Henri Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206 (94i:11105)
  • [7] 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
  • [8] L. Dembélé and A. Kumar, Examples of abelian surfaces with everywhere good reduction, Preprint, http://arxiv.org/abs/1309.3821.
  • [9] J. R. Doyle, X. Faber, and D. Krumm, Preperiodic points for quadratic polynomials over quadratic fields, New York J. Math. 20 (2014), 507-605. MR 3218788
  • [10] J. R. Doyle and D. Krumm, Computing algebraic numbers of bounded height, Math. Comp. Published electronically, April 1, 2015.
  • [11] 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
  • [12] 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 (86e:11050), https://doi.org/10.2307/2007966
  • [13] 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 (91f:11090), https://doi.org/10.2307/1990896
  • [14] Michael J. Jacobson Jr., Applying sieving to the computation of quadratic class groups, Math. Comp. 68 (1999), no. 226, 859-867. MR 1604324 (99i:11120), https://doi.org/10.1090/S0025-5718-99-01003-0
  • [15] S. Lang, Fundamentals of Diophantine Geometry, Springer-Verlag, New York, 1983.
  • [16] Serge Lang, Algebraic Number Theory, 2nd ed., Graduate Texts in Mathematics, vol. 110, Springer-Verlag, New York, 1994. MR 1282723 (95f:11085)
  • [17] 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
  • [18] 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
  • [19] Phong Q. Nguyen and Damien Stehlé, An LLL algorithm with quadratic complexity, SIAM J. Comput. 39 (2009), no. 3, 874-903. MR 2538842 (2010i:11187), https://doi.org/10.1137/070705702
  • [20] 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
  • [21] 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)
  • [22] 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)
  • [23] Joseph H. Silverman, The Arithmetic of Dynamical Systems, Graduate Texts in Mathematics, vol. 241, Springer, New York, 2007. MR 2316407 (2008c:11002)
  • [24] W.A. Stein et al., Sage Mathematics Software (Version 5.9), The Sage Development Team, 2013, http://www.sagemath.org.
  • [25] M. Stoll, An explicit theory of heights for hyperelliptic jacobians of genus three, Preprint.
  • [26] Michael Stoll, On the height constant for curves of genus two, Acta Arith. 90 (1999), no. 2, 183-201. MR 1709054 (2000h:11069)
  • [27] Michael Stoll, On the height constant for curves of genus two. II, Acta Arith. 104 (2002), no. 2, 165-182. MR 1914251 (2003f:11093), https://doi.org/10.4064/aa104-2-6
  • [28] Martin Widmer, Counting primitive points of bounded height, Trans. Amer. Math. Soc. 362 (2010), no. 9, 4793-4829. MR 2645051 (2011i:11099), https://doi.org/10.1090/S0002-9947-10-05173-1
  • [29] Martin Widmer, Lipschitz class, narrow class, and counting lattice points, Proc. Amer. Math. Soc. 140 (2012), no. 2, 677-689. MR 2846337 (2012h:11140), https://doi.org/10.1090/S0002-9939-2011-10926-2

Similar Articles

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

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


Additional Information

David Krumm
Affiliation: Department of Mathematics, Claremont McKenna College, Claremont, California 91711
Email: dkrumm@cmc.edu

DOI: https://doi.org/10.1090/mcom/2984
Received by editor(s): April 10, 2014
Received by editor(s) in revised form: August 2, 2014
Published electronically: June 9, 2015
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society