## `polylib::minpoly` -- approximate minimal polynomial

#### Introduction

`polylib::minpoly``(a, n, x)` computes a univariate polynomial `f` in the variable `x` of degree `n` with integer coefficients such that `a` equals a root of `f` up to the precision given by `DIGITS`, and such that the sum of squares of its coefficients is minimal among all polynomials with this property.

#### Call(s)

`polylib::minpoly(a, n, x)`

#### Parameters

`a` | - | arithmetical expression that can be converted to a floating point number
`n` | - | positive integer
`x` | - | identifier

#### Returns

`polylib::minpoly` returns a polynomial in `x`. Its coefficient ring is `Expr`, all of its coefficients are integers.

#### Side Effects

`polylib::minpoly` is sensitive to the environment variable `DIGITS`.

#### Related Functions

`lllint`, `stats::linReg`, `numeric::lagrange`

#### Example 1

We compute a polynomial of degree 4 that has a root close to `PI` (up to 6 decimal digits) and small integer coefficients:

    >> DIGITS:=6: polylib::minpoly(PI, 4, x); delete DIGITS:

                             4       3       2
                     poly(7 x  - 16 x  - 16 x  - 6 x - 9, [x])

If the root has to be even closer to `PI`, bigger coefficients are needed:

    >> DIGITS:=20: polylib::minpoly(PI, 4, x); delete DIGITS

                           4         3        2
              poly(- 1951 x  + 6379 x  - 422 x  + 283 x - 4468, [x])

#### Background

- The problem reduces to finding a shortest integer vector in the lattice {ei + ai ·en+1 ; 0 ≤i ≤n }, where ei denotes the vector with ei[j] = δi,j (Kronecker symbol). This problem is solved using the algorithm of Lenstra/Lenstra/Lovasz. See Lenstra/Lenstra/Lovasz, Factoring polynomials with rational coefficients, Math. Ann. 261(1982), pp. 515-534.

#### Changes

- used to be called `numeric::minpoly`

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000