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