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

DOI10.1090/MCOM/2984MaRDI QIDQ3450044zbMATH OpenOpenAlexFDO

Authors David Krumm

Publication date 2 November 2015

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.6501

zbMATH Keywords

algorithmcomputing points of relative heightefficiency of algorithm

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to number theory (11-04) Lattice points in specified regions (11P21) Algebraic number theory computations (11Y40) Rational points (14G05)

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.

Recommendations

• Computing algebraic numbers of bounded height
• Elements with bounded height in number fields
• Counting points of bounded relative height
• Counting points of fixed degree and bounded height
• Computing canonical heights on the projective line with no factorization

Cites work

• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• A Rigorous Subexponential Algorithm For Computation of Class Groups
• Algorithms in Algebraic Number Theory
• An explicit theory of heights for hyperelliptic Jacobians of genus three
• An LLL algorithm with quadratic complexity
• Applying sieving to the computation of quadratic class groups
• Computing algebraic numbers of bounded height
• Counting primitive points of bounded height
• Effective lattice point counting in rational convex polytopes
• Elements with bounded height in number fields
• Examples of abelian surfaces with everywhere good reduction
• Factoring polynomials with rational coefficients
• Heights in number fields
• scientific article; zbMATH DE number 435565 (Why is no real title available?)
• scientific article; zbMATH DE number 3838204 (Why is no real title available?)
• scientific article; zbMATH DE number 3859248 (Why is no real title available?)
• scientific article; zbMATH DE number 4200333 (Why is no real title available?)
• scientific article; zbMATH DE number 611919 (Why is no real title available?)
• scientific article; zbMATH DE number 194764 (Why is no real title available?)
• scientific article; zbMATH DE number 1405493 (Why is no real title available?)
• Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
• Improvements in the computation of ideal class groups of imaginary quadratic number fields
• Lipschitz class, narrow class, and counting lattice points
• On the height constant for curves of genus two
• On the height constant for curves of genus two, II
• Preperiodic points for quadratic polynomials over quadratic fields
• The arithmetic of dynamical systems

Cited in

(3)

• Lattice point counting and height bounds over number fields and quaternion algebras
• Computing algebraic numbers of bounded height
• Elements with bounded height in number fields

Describes a project that uses

Uses Software

• SageMath
• LattE

This page was built for publication: Computing points of bounded height in projective space over a number field

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3450044)