Recognizing Algebraic Numbers using Lattice Basis Reduction (LLL)

Suppose you somehow compute a decimal approximation $\alpha$ to some rational number $\beta \in \mathbf{Q}$ and from this wish to recover $\beta$. For concreteness, say

$$\beta= 22/389 = 0.05655526992287917737789203084832904884318766066838046\ldots$$

and you compute

$$\alpha = 0.056555.$$

Now suppose given only $\alpha$ that you would like to recover $\beta$. A standard technique is to use continued fractions, which yields a sequence of good rational approximations for $\alpha$; by truncating right before a surprisingly big partial quotient, we obtain $\beta$:

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 $\alpha \in \mathbf{C}$ to an algebraic number $\beta \in \overline{\mathbf{Q}}$. For concreteness, suppose $\beta = \frac{1}{3} + \sqrt[4]{3}$:

sage: N(1/3 + 3^(1/4), digits=50)
1.64940734628582579415255223513033238849340192353916

Now suppose you very much want to find the (rescaled) minimal polynomial $f(x) \in \mathbf{Z}[x]$ of $\beta$ just given this numerical approximation $\alpha$. 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 $\alpha$ has been computed to sufficient precision.