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.]

ad hoc. So could be an interesting research project to find/prove something more precise. $\endgroup$3more comments