PolynomialTools - Maple Programming Help

Home : Support : Online Help : Mathematics : Optimization : PolynomialTools/MinimalPolynomial

PolynomialTools

 MinimalPolynomial
 find minimal polynomial for an exact or approximate root
 AnnihilatingPolynomial
 find an annihilating polynomial for an approximate root

 Calling Sequence MinimalPolynomial(r, x) MinimalPolynomial(r, x, n, acc) AnnihilatingPolynomial(r, x, n, acc)

Parameters

 r - exact or approximate root x - (optional) variable name n - an upperbound on the degree of the polynomial sought

Options

 • acc
 desired accuracy of the approximation
 • digits : posint
 A value for Digits to be used for all numerical computations.

Description

 • The MinimalPolynomial and AnnihilatingPolynomial functions find a polynomial with integer coefficients which has the algebraic number r as one of its roots.
 • If r is an exact algebraic number, and n and acc are not given, then MinimalPolynomial calls evala/Minpoly to compute an exact minimal polynomial of r.
 • Otherwise the AnnihilatingPolynomial and MinimalPolynomial functions, use a lattice-based algorithm to find a polynomial of degree n (or less) with small integer coefficients which has the given approximation r of an algebraic number as one of its roots.  They differ in that, the output of MinimalPolynomial is guaranteed to be an irreducible polynomial, while the output of AnnihilatingPolynomial is the raw output of the lattice algorithm.
 • If a name is not specified for the variable x, then $\mathrm{_X}$ is used.
 • The root r may be real or complex.  It may be input as a floating-point approximation to a root or as an exact algebraic number.  In the latter case, if an approximate algorithm is being used, r will first be evaluated in floating point at Digits precision using evalf.
 • The value $\mathrm{acc}\left|f\left(r\right)\right|$ is given the same weight as the coefficients in determining $f$, the minimal polynomial. If it is not specified, the default value for acc is $\frac{{10}^{\mathrm{Digits}-2}}{\mathrm{max}\left(1,\left|{r}^{n}\right|\right)}$.  Larger values indicate the desire for better approximations.
 • This function is part of the PolynomialTools package, and so it can be used in the form MinimalPolynomial(..) only after executing the command with(PolynomialTools). However, it can always be accessed through the long form of the command by using PolynomialTools[MinimalPolynomial](..).

Examples

 > $\mathrm{with}\left(\mathrm{PolynomialTools}\right):$
 > $\mathrm{rf}≔\mathrm{evalf}\left(1+\mathrm{sqrt}\left(2\right)\right)$
 ${\mathrm{rf}}{≔}{2.414213562}$ (1)
 > $\mathrm{MinimalPolynomial}\left(\mathrm{rf},x,2\right)$
 ${{x}}^{{2}}{-}{2}{}{x}{-}{1}$ (2)
 > $r≔1+\mathrm{sqrt}\left(2\right)$
 ${r}{≔}{1}{+}\sqrt{{2}}$ (3)

When r is exact, and no degree bound given, an exact method is used

 > $\mathrm{MinimalPolynomial}\left(\frac{r}{10},x\right)$
 ${100}{}{{x}}^{{2}}{-}{20}{}{x}{-}{1}$ (4)

Otherwise the lattice-based approximation is used

 > $\mathrm{MinimalPolynomial}\left(\frac{r}{10},x,25\right)$
 ${25}{}{{x}}^{{12}}{+}{8}{}{{x}}^{{11}}{-}{7}{}{{x}}^{{10}}{-}{21}{}{{x}}^{{9}}{+}{14}{}{{x}}^{{8}}{-}{2}{}{{x}}^{{7}}{+}{9}{}{{x}}^{{6}}{+}{14}{}{{x}}^{{5}}{+}{5}{}{{x}}^{{4}}{-}{4}{}{{x}}^{{3}}{+}{4}{}{{x}}^{{2}}{-}{5}{}{x}{+}{1}$ (5)

If r is less than 1, and the accuracy is set low by default, and the output of AnnihilatingPolynomial could be a simple monomial.

 > $\mathrm{AnnihilatingPolynomial}\left(\frac{r}{10},x,25,{10.}^{10}\right)$
 ${{x}}^{{16}}$ (6)

Setting the accuracy higher can help avoid such trivial output.

 > $\mathrm{AnnihilatingPolynomial}\left(\frac{r}{10},x,25,{10.}^{25}\right)$
 ${{x}}^{{21}}{-}{{x}}^{{19}}{+}{2}{}{{x}}^{{18}}{+}{2}{}{{x}}^{{17}}{+}{8}{}{{x}}^{{16}}{+}{4}{}{{x}}^{{15}}{-}{{x}}^{{14}}{+}{4}{}{{x}}^{{13}}{-}{3}{}{{x}}^{{12}}{-}{3}{}{{x}}^{{11}}{-}{6}{}{{x}}^{{10}}{-}{5}{}{{x}}^{{9}}{-}{4}{}{{x}}^{{8}}{+}{3}{}{{x}}^{{7}}{+}{{x}}^{{6}}{-}{8}{}{{x}}^{{5}}{+}{4}{}{{x}}^{{3}}{-}{5}{}{{x}}^{{2}}{+}{x}$ (7)
 > $\mathrm{MinimalPolynomial}\left(1.234,3\right)$
 ${22}{}{{\mathrm{_X}}}^{{3}}{-}{5}{}{{\mathrm{_X}}}^{{2}}{+}{61}{}{\mathrm{_X}}{-}{109}$ (8)
 > $\mathrm{fsolve}\left(,\mathrm{_X}\right)$
 ${1.234000001}$ (9)

Sometimes the exact and approximate algorithms will agree but it is not guaranteed. The approximate algorithm typically be faster.

 > $s≔\mathrm{sqrt}\left(2\right)+\mathrm{sqrt}\left(-3\right)$
 ${s}{≔}\sqrt{{2}}{+}{I}{}\sqrt{{3}}$ (10)
 > $\mathrm{MinimalPolynomial}\left(s,x\right)$
 ${{x}}^{{4}}{+}{2}{}{{x}}^{{2}}{+}{25}$ (11)
 > $\mathrm{MinimalPolynomial}\left(s,x,4\right)$
 ${{x}}^{{4}}{+}{2}{}{{x}}^{{2}}{+}{25}$ (12)
 > $t≔\mathrm{add}\left(\mathrm{sqrt}\left({\left(-1\right)}^{i+1}\mathrm{ithprime}\left(i\right)\right),i=1..3\right)$
 ${t}{≔}\sqrt{{2}}{+}{I}{}\sqrt{{3}}{+}\sqrt{{5}}$ (13)
 > $P≔\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{MinimalPolynomial}\left(t,x\right)\right)$
 memory used=13.07MiB, alloc change=8.00MiB, cpu time=62.00ms, real time=62.00ms, gc time=0ns
 ${P}{≔}{{x}}^{{8}}{-}{16}{}{{x}}^{{6}}{+}{184}{}{{x}}^{{4}}{+}{960}{}{{x}}^{{2}}{+}{3600}$ (14)

The numeric algorithm is faster, but does not get the exact answer unless the working precision is increased

 > $\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{MinimalPolynomial}\left(t,x,\mathrm{degree}\left(P,x\right)\right)\right)$
 memory used=1.24MiB, alloc change=0 bytes, cpu time=20.00ms, real time=19.00ms, gc time=0ns
 ${2}{}{{x}}^{{7}}{-}{15}{}{{x}}^{{6}}{+}{38}{}{{x}}^{{5}}{+}{6}{}{{x}}^{{4}}{-}{177}{}{{x}}^{{3}}{+}{453}{}{{x}}^{{2}}{+}{139}{}{x}{-}{146}$ (15)
 > $\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{MinimalPolynomial}\left(t,x,\mathrm{degree}\left(P,x\right),\mathrm{digits}=25\right)\right)$
 memory used=2.77MiB, alloc change=0 bytes, cpu time=23.00ms, real time=24.00ms, gc time=0ns
 ${{x}}^{{8}}{-}{16}{}{{x}}^{{6}}{+}{184}{}{{x}}^{{4}}{+}{960}{}{{x}}^{{2}}{+}{3600}$ (16)

Compatibility

 • The output of MinimalPolynomial(r, n, acc) prior to Maple 18 used the variable $x$.  As of Maple 18, the default variable used is $\mathrm{_X}$. You can change this using the x argument.
 • As of 2020, MinimalPolynomial(r, x) calls evala(Minpoly(r,x)) if r is an exact algebraic number. To force the previous behavior, r can be replaced with evalf(r) in the calling sequence or an explicit degree bound can be passed as a second or third argument.
 • The PolynomialTools[AnnihilatingPolynomial] command was introduced in Maple 18.
 • The PolynomialTools[MinimalPolynomial] command was updated in Maple 18.
 • The x parameter was introduced in Maple 18.