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.]
 A: 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
A: This does not quite answer the question as posed, but Xiaolin Qin, Yong Feng, Jingwei Chen, Jingzhong Zhang claim a better [than LLL] algorithm (with all the parameters specified) to find integer relations (and thus to find the miminal polynomial) in their 2010 paper. The paper is not written in the best English, but seems good otherwise.
A: 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: 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.
