13
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ PARI-GP has a built-in function called algdep(x,d) that uses LLL to compute an integer polynomial of degree d with f(x) very small. I realize you didn't ask for a package, but the source code for PARI is public, so it should be possible to check how PARI uses LLL. And in particular, since Henri Cohen was quite active with PARI, it's likely that the implementation is a practical version of the comment you quote from his book. $\endgroup$ – Joe Silverman May 1 '15 at 13:07
  • $\begingroup$ Umm, what's the question? Do you want something more than what Cohen says? $\endgroup$ – Igor Rivin May 1 '15 at 13:07
  • $\begingroup$ @Igor: I guess I have two questions: 1) What exactly does Cohen mean by "subtle"? 2) Have there been any further developments in how to choose $N$ in the 20 years since Cohen's book? $\endgroup$ – Mark Bell May 1 '15 at 13:35
  • 1
    $\begingroup$ @JoeSilverman: Thanks for the suggestion. I've only had a brief chance to look at PARI but the relevant code appears to be "lindep2" in ./basemath/bibli1.c (the precision to work to (equiv. the choice of $N$) is chosen here not in algdep0). It appears that if the binary expansion of $a$ has $i$ bits before the decimal and $j$ bits afterwards then PARI uses $N = 10^{32+i}$ if $j = 0$ and $N = 10^{0.8 j}$ otherwise (or a user given precision). $\endgroup$ – Mark Bell May 1 '15 at 14:06
  • 1
    $\begingroup$ @MarkBell You're welcome. In principle, there can't be a "correct" polynomial, since you're using a decimal approximation $\alpha$ to your algebraic number. And $\alpha$ is the root of many polynomials with integer coefficients. Of course, one wants the coefficients to be small in an appropriate sense. Anyway, it sounds as if the way PARI chooses $N$ is fairly ad hoc. So could be an interesting research project to find/prove something more precise. $\endgroup$ – Joe Silverman May 1 '15 at 14:36
5
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.