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](http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm#Applications) 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.]



Computing minimal polynomials using LLL
The theory of "layered lattices" is an attempt to deal
with these issues. The 2011 thesis of Lenstra's student 
Erwin Dassen is devoted to this subject:


<https://openaccess.leidenuniv.nl/handle/1887/18264>


