next up previous
Next: Basis Perturbation Up: Integer Relation Algorithms Previous: The PSLQ Algorithm

   
Finding Minimal Polynomials

If $\alpha$ is a real number, then by definition $\alpha$ is algebraic exactly if, for some r, the vector

 \begin{displaymath}
(1,\alpha,\alpha^2,\ldots,\alpha^r)
\end{displaymath} (4)

has an integer relation. The integer coefficient polynomial of lowest degree, having $\alpha$ as a root, is determined uniquely up to a constant multiple; it is called the minimal polynomial for $\alpha$. Integer relation algorithms can be employed to look for minimal polynomials in a straightforward way by simply feeding them the vector (4) as their input. Some computer algebra systems have an LLL-based procedure for finding minimal polynomials but lack a general procedure for finding integral relations; based on the explanation in Section 2.1 the reader should be able to convert those minimal polynomial routines into general integral relation routines.



Agnes Szanto
2000-05-10