# Computing minimal polynomials using LLL

I would like to use the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL algorithm) to compute the minimal polynomial of a (real) algebraic number $\alpha$ from a decimal approximation $a$ (and bounds on its degree and height). A fairly standard idea for how to do this is to pick a large constant $N$ and apply the LLL algorithm to the lattice: \begin{eqnarray} &(1 \; 0 \; 0 \; \cdots \; 0 \; \lfloor N \rfloor),& \\ &(0 \; 1 \; 0 \; \cdots \; 0 \; \lfloor Na \rfloor),& \\ &(0 \; 0 \; 1 \; 0 \; \cdots \; 0 \; \lfloor Na^2 \rfloor),& \\ &\vdots& \\ &(0 \; \cdots \; 0 \; 1 \; \; \lfloor Na^d \rfloor)& \\ \end{eqnarray} The first vector of the basis returned by the LLL algorithm is $$\left(a_0 \; a_1 \; \cdots \; a_d \; N \sum a_i a^i \right)$$ As all of these entries are small, we obtain a small integer relation between $a^0, \ldots, a^d$. See wikipedia for an example of doing this to compute a quadratic that has a root close to $1.618034$ using $N = 10000$. However this process depends on the choice of $N$. Too small will result in underfitting while too large will result in overfitting.

Is there an explicit procedure for determining what value of $N$ to use (as a function of the bounds on the degree and height of $\alpha$)?

Most of the papers that I have looked which discuss this approach at appear to use a fairly ad-hoc method. The only place where I could find choosing $N$ being addressed is Cohen (A course in computational algebraic number theory, Section 2.7.2) where he says that:

The choice of the constant $N$ is subtle, and depends in part on what one knows about the problem. If the $|a^i|$ are not too far from 1 (meaning between $10^{-6}$ and $10^6$ , say), and are known with an absolute (or relative) precision $\epsilon$, then one should take $N$ between $1 / \epsilon$ and $1 / \epsilon^2$, but $\epsilon$ should also be taken quite small: if one expects the coefficients $a_i$; to be of to be of the order of $x$, then one might take $\epsilon = x^{1.5d}$, but in any case $\epsilon < x^{-d}$.''

[I've modified the variable names to match the previous section.]

• PARI-GP has a built-in function called algdep(x,d) that uses LLL to compute an integer polynomial of degree d with f(x) very small. I realize you didn't ask for a package, but the source code for PARI is public, so it should be possible to check how PARI uses LLL. And in particular, since Henri Cohen was quite active with PARI, it's likely that the implementation is a practical version of the comment you quote from his book. May 1 '15 at 13:07
• Umm, what's the question? Do you want something more than what Cohen says? May 1 '15 at 13:07
• @Igor: I guess I have two questions: 1) What exactly does Cohen mean by "subtle"? 2) Have there been any further developments in how to choose $N$ in the 20 years since Cohen's book? May 1 '15 at 13:35
• @JoeSilverman: Thanks for the suggestion. I've only had a brief chance to look at PARI but the relevant code appears to be "lindep2" in ./basemath/bibli1.c (the precision to work to (equiv. the choice of $N$) is chosen here not in algdep0). It appears that if the binary expansion of $a$ has $i$ bits before the decimal and $j$ bits afterwards then PARI uses $N = 10^{32+i}$ if $j = 0$ and $N = 10^{0.8 j}$ otherwise (or a user given precision). May 1 '15 at 14:06
• @MarkBell You're welcome. In principle, there can't be a "correct" polynomial, since you're using a decimal approximation $\alpha$ to your algebraic number. And $\alpha$ is the root of many polynomials with integer coefficients. Of course, one wants the coefficients to be small in an appropriate sense. Anyway, it sounds as if the way PARI chooses $N$ is fairly ad hoc. So could be an interesting research project to find/prove something more precise. May 1 '15 at 14:36

So it turns out that this question was also asked on the cstheory stackexchange. They reference chapter 9 of C. Yap's "Fundamental Problems in Algorithmic Algebra" where this exact problem is tackled. In this, he shows that taking $N = 2^{4 h^3}$ is sufficient where $h$ is the height of $\alpha$.
A funny instance. Let $r=3.14159265358979323846264338327950288419716939937510582097\cdots$ -the $120$ first significant digits of $\pi$-. With lll, we obtain polynomials (with integer coefficients) of degrees $19$ and $34$. Thus if we only know that $r$ is algebraic with degree $\leq 34$, then we cannot conclude without the knowledge of supplementary digits.