Recognizing Algebraic Numbers using Lattice Basis Reduction (LLL)

Suppose you somehow compute a decimal approximation to some rational number and from this wish to recover . For concreteness, say

sage: v = continued_fraction(0.056555) sage: continued_fraction(0.056555) [0, 17, 1, 2, 6, 1, 23, 1, 1, 1, 1, 1, 2] sage: convergents([0, 17, 1, 2, 6, 1]) [0, 1/17, 1/18, 3/53, 19/336, 22/389]

Generalizing this, suppose next that somehow you numerically approximate an algebraic number, e.g., by evaluating a special function and get a decimal approximation to an algebraic number . For concreteness, suppose :

sage: N(1/3 + 3^(1/4), digits=50) 1.64940734628582579415255223513033238849340192353916Now suppose you very much want to find the (rescaled) minimal polynomial of just given this numerical approximation . This is of great value even without proof, since often in practice once you know a potential minimal polynomial you can verify that it is in fact right. Exactly this situation arises in the explicit construction of class fields (a more advanced topic in number theory) and in the construction of Heegner points on elliptic curves. As we will see, the LLL algorithm provides a polynomial time way to solve this problem, assuming has been computed to sufficient precision.