Algebraic - Maple Programming Help

Home : Support : Online Help : Mathematics : Algebra : Algebraic Numbers : Algebraic/PseudoDivision

Algebraic

 PseudoDivision
 pseudo-division of polynomials with algebraic number coefficients

 Calling Sequence PseudoDivision(a, b, x, options) PseudoDivision(a, b, x, m, q, options)

Parameters

 a,b - multivariate polynomials in x with algebraic number coefficients x - name m,q - (optional) unevaluated names options - (optional) equation(s) of the form keyword = value, where keyword is either 'symbolic', 'makeindependent', or 'characteristic'

Options

 • If the option 'symbolic' = true is given and a RootOf whose minimal polynomial factors nontrivially is detected, then it will be reduced to a RootOf of lower degree by picking one of the factors arbitrarily. This will eliminate the possibility of a "reducible RootOf detected" error. The default is 'symbolic'=false.
 • If the option 'characteristic' = p is given, where p is a non-negative integer, the pseudo-division is performed over an extension of the ring ${\mathrm{ℤ}}_{p}$ of integers modulo p. The default is 'characteristic'=0 and means that the pseudo-division is performed over an extension of the rational numbers.
 • If the option 'makeindependent'=true is given, then PseudoDivision will always try to find a field representation for algebraic numbers in the input, regardless of how many algebraic objects the input contains. If the input contains many RootOfs, then this can be a very expensive calculation. If 'makeindependent'=false is given, then no independence checking is performed. The default is 'makeindependent'=FAIL, in which case algebraic dependencies will only be checked for if there are $4$ or fewer algebraic objects in the input.

Description

 • The PseudoDivision command performs pseudo-division on multivariate polynomials a and b with respect to the variable x. It returns the pseudo-remainder r such that the relationship $ma=bq+r$ is satisfied, where m is the multiplier and q is the pseudo-quotient. r and q are polynomials in x, with degree(r,x) < degree(b,x). The multiplier m is defined as lcoeff(b, x) ^ (degree(a, x)-degree(b, x)+1) and is free of x.
 • If the optional arguments m and q are included, they will be assigned the values of the multiplier and pseudo-quotient respectively.
 • The inputs a and b may contain algebraic number coefficients. These may be represented by radicals or with the RootOf notation (see type,algnum, type,radnum). In general, algebraic numbers will be returned in the same representation as they were received in. Nested radicals and RootOfs are also supported.
 • The property $ma=bq+r$ will hold in the domain K[x], where K is an algebraic field generated over the rationals and any algebraic number coefficients occurring in a and b (unless the option 'characteristic' is given; see below).
 • Non-algebraic sub-expressions such as $\mathrm{sin}\left(x\right)$ that are neither variables, rational numbers, or algebraic objects are frozen and temporarily replaced by new local variables, which are not considered to be constant in what follows.
 • The arguments a and b must be polynomials in the variable x, but may contain other names, which are considered as elements of the coefficient field.
 • The x parameter can also be a function such as $\mathrm{sin}\left(x\right)$, in which case it will be frozen and treated as a variable. However, functions that are also of type AlgebraicObject such as $\mathrm{sin}\left(\frac{\mathrm{\pi }}{3}\right)$ will be converted to algebraic numbers before proceeding, so they cannot be treated as variables. Proceed with caution when using a function for x, as treating some functions as variables may produce mathematically unsound results.
 • The inputs a and b can be polynomials disguised as rational functions, in which case they are normalized first using Algebraic[Normal].
 • The output will be normalized as follows:
 – All non-constant factors are monic with respect to x.
 – There are at most two constant factors, and at most one of them is not a rational number.
 – All algebraic numbers occurring in the result are reduced modulo their minimal polynomial (see Reduce), and all arguments of functions, if any, are normalized recursively (see Normal).
 • If the set of radicals and RootOfs in the input cannot be embedded into a field algebraically, then PseudoDivision may not be able to perform the division. PseudoDivision will try to find a field representation if there are at most $4$ algebraic objects in the input (unless option 'makeindependent' is given; see below), and otherwise attempt to proceed anyway. If unsuccessful, a "reducible RootOf detected" error will be returned. (unless the option 'symbolic'=true is given; see below).
 • This function does not support input containing floats or radical functions such as $\sqrt{x}$.

Examples

 > with(Algebraic):

Introductory examples:

 > PseudoDivision(x^2+2,2*x+sqrt(2),x,'m1','q1');
 ${10}$ (1)
 > [m1,q1];
 $\left[{4}{,}{2}{}{x}{-}\sqrt{{2}}\right]$ (2)
 > expand(4*(x^2+2)-(2*x+sqrt(2))*(2*x-sqrt(2)));
 ${10}$ (3)
 > [PseudoDivision(x^3+y^3+5,I*x+I*y,x,'m2','q2'),m2,q2];
 $\left[{-}{5}{}{I}{,}{-I}{,}{-}{{x}}^{{2}}{+}{y}{}{x}{-}{{y}}^{{2}}\right]$ (4)
 > r1:=RootOf(_Z^2-_Z-1);
 ${\mathrm{r1}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{\mathrm{_Z}}{-}{1}\right)$ (5)
 > [PseudoDivision(x^2+1,r1*x,x,'m3','q3'),m3,q3];
 $\left[{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{\mathrm{_Z}}{-}{1}\right){+}{1}{,}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{\mathrm{_Z}}{-}{1}\right){+}{1}{,}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{\mathrm{_Z}}{-}{1}\right){}{x}\right]$ (6)

The input may contain both radicals and RootOfs, and PseudoDivision will embed the coefficients into an algebraic field, if possible:

 > [PseudoDivision(x*y*z,sqrt(2)*x-RootOf(_Z^2-8,index=1),x,'m4','q4'),m4,q4];
 $\left[{2}{}\sqrt{{2}}{}{z}{}{y}{,}\sqrt{{2}}{,}{z}{}{y}\right]$ (7)
 > [PseudoDivision(sqrt(2)*x,sqrt(3)*x-sqrt(6),x,'m5','q5'),m5,q5];
 $\left[{2}{}\sqrt{{3}}{,}\sqrt{{3}}{,}\sqrt{{2}}\right]$ (8)

Nested and mixed radicals and RootOfs are handled as well:

 > [PseudoDivision(x^2-4^(-2/3)+1,2*x+RootOf(_Z^3-2,index=1),x,'m6','q6'),m6,q6];
 $\left[{4}{,}{4}{,}{2}{}{x}{-}{{2}}^{{1}}{{3}}}\right]$ (9)
 > [PseudoDivision(sqrt(RootOf(_Z^2-3,index=1))*x,RootOf(_Z^2-RootOf(_Z^2-3,index=1),index=1),x,'m7','q7'),m7,q7];
 $\left[{0}{,}\sqrt{{3}}{,}\sqrt{{3}}{}{x}\right]$ (10)

Multivariate input is accepted, but pseudo-division will only be performed on the input with respect to the single variable given in the x parameter, with all other names being considered as elements of the coefficient field:

 > [PseudoDivision(x^2*y^2+7,x*y,x,'m8','q8'),m8,q8];
 $\left[{7}{}{{y}}^{{2}}{,}{{y}}^{{2}}{,}{{y}}^{{3}}{}{x}\right]$ (11)
 > [PseudoDivision(x^2*y^2+7,x*y,y,'m9','q9'),m9,q9];
 $\left[{7}{}{{x}}^{{2}}{,}{{x}}^{{2}}{,}{{x}}^{{3}}{}{y}\right]$ (12)
 > [PseudoDivision(x^2*y^2+7,x*y,z,'m10','q10'),m10,q10];
 $\left[{0}{,}{y}{}{x}{,}{{x}}^{{2}}{}{{y}}^{{2}}{+}{7}\right]$ (13)

If the degree of a is less than the degree of b, then the multiplier will be $1$ and the pseudo-quotient will be $0$:

 > [PseudoDivision(x^2,x^3,x,'m11','q11'),m11,q11];
 $\left[{{x}}^{{2}}{,}{1}{,}{0}\right]$ (14)

If b is a non-zero constant, the pseudo-remainder will always be zero:

 > [PseudoDivision(x^10,sqrt(2),x,'m11','q11'),m11,q11];
 $\left[{0}{,}{32}{}\sqrt{{2}}{,}{32}{}{{x}}^{{10}}\right]$ (15)

The output will always be fully reduced and normalized:

 > [PseudoDivision(x^2,RootOf(_Z^2-_Z-1),x,'m12','q12'),m12,q12];
 $\left[{0}{,}{2}{}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{\mathrm{_Z}}{-}{1}\right){+}{1}{,}{{x}}^{{2}}{}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{\mathrm{_Z}}{-}{1}\right){+}{{x}}^{{2}}\right]$ (16)
 > [PseudoDivision(x/RootOf(_Z^2+6*_Z-1)+7,2*x,x,'m13','q13'),m13,q13];
 $\left[{14}{,}{2}{,}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{+}{6}{}{\mathrm{_Z}}{-}{1}\right){+}{6}\right]$ (17)

Algebraic Objects will be converted to algebraic numbers, if possible:

 > [PseudoDivision(x+sin(Pi/4),sqrt(2)*x+exp(I*Pi),x,'m14','q14'),m14,q14];
 $\left[{2}{,}\sqrt{{2}}{,}{1}\right]$ (18)

Non-algebraic sub-expressions such as $\mathrm{sin}\left(x\right)$ will be frozen and temporarily replaced by new local variables:

 > [PseudoDivision(z^2+1,z*sin(x),z,'m15','q15'),m15,q15];
 $\left[{{\mathrm{sin}}{}\left({x}\right)}^{{2}}{,}{{\mathrm{sin}}{}\left({x}\right)}^{{2}}{,}{z}{}{\mathrm{sin}}{}\left({x}\right)\right]$ (19)

The x parameter can also be a function, as long as it is not an Algebraic Object:

 > [PseudoDivision(sin(x)+4,2*sin(x),sin(x),'m16','q16'),m16,q16];
 $\left[{8}{,}{2}{,}{1}\right]$ (20)
 > a:=Pi/4;
 ${a}{≔}\frac{{\mathrm{\pi }}}{{4}}$ (21)
 > PseudoDivision(sin(a)+4,2*sin(a),sin(a));

Arguments of functions in the input will be recursively normalized:

 > [PseudoDivision(tan((x^2-1)/(x+1))+exp(RootOf(_Z^2-_Z-1)^3),tan(x-sin(Pi/2)),tan(x-1),'m17','q17'),m17,q17];
 $\left[{{ⅇ}}^{{2}{}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{\mathrm{_Z}}{-}{1}\right){+}{1}}{,}{1}{,}{1}\right]$ (22)

Non-algebraic sub-expressions may become algebraic after recursive normalization occurs:

 > [PseudoDivision(sin((x^2-1)/(x-1)/(x+1)*Pi/4)*x,x+1,x,'m18','q18'),m18,q18];
 $\left[{-}\frac{\sqrt{{2}}}{{2}}{,}{1}{,}\frac{\sqrt{{2}}}{{2}}\right]$ (23)

Rational functions are not accepted:

 > PseudoDivision(1/x,1/x^2,x);

Floats are not accepted.

Algebraic functions such as $\sqrt{x}$ are not accepted:

 > PseudoDivision(x^2+2*x*sqrt(x)+x,x+sqrt(x),x);

When non-indexed RootOfs are given in the input, the pseudo-division can still be performed and the output expressed in terms of the non-indexed RootOfs:

 > [PseudoDivision(x^2-1+RootOf(_Z^2-3),2*x-RootOf(_Z^2-4),x,'m19','q19'),m19,q19];
 $\left[{4}{}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{3}\right){,}{4}{,}{2}{}{x}{+}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{4}\right)\right]$ (24)
 > [PseudoDivision(x+sqrt(2),2*x+RootOf(_Z^2-8),x,'m20','q20'),m20,q20];
 $\left[{-}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{8}\right){+}{2}{}\sqrt{{2}}{,}{2}{,}{1}\right]$ (25)

Even if the leading coefficients of the input contain zero divisors, PseudoDivision can still compute the pseudo-remainder, multiplier, and pseudo-quotient in terms of the input such that the identity $ma=bq+r$ is preserved:

 > [PseudoDivision(sqrt(2)*x,RootOf(_Z^2-2,index=1)*x+sqrt(2)*x+1,x,'m21','q21'),m21,q21];
 $\left[{-}\sqrt{{2}}{,}{2}{}\sqrt{{2}}{,}\sqrt{{2}}\right]$ (26)
 > [PseudoDivision(sqrt(2)*x,RootOf(_Z^2-2,index=2)*x+sqrt(2)*x+1,x,'m22','q22'),m22,q22];
 $\left[{0}{,}{1}{,}{x}{}\sqrt{{2}}\right]$ (27)
 > [PseudoDivision(sqrt(2)*x,RootOf(_Z^2-2)*x+sqrt(2)*x+1,x,'m23','q23'),m23,q23];
 $\left[{-}\sqrt{{2}}{,}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{2}\right){+}\sqrt{{2}}{,}\sqrt{{2}}\right]$ (28)

Also, if the second argument is a zero divisor, then the computation will be performed anyway and an answer will be returned such that the identity $ma=bq+r$ is preserved:

 > [PseudoDivision(x,sqrt(2)-RootOf(_Z^2-2),x,'m24','q24'),m24,q24];
 $\left[{0}{,}{-}{2}{}\sqrt{{2}}{}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{2}\right){+}{4}{,}{x}{}\sqrt{{2}}{-}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{2}\right){}{x}\right]$ (29)

Using option characteristic, pseudo-division can be performed over finite fields:

 > [PseudoDivision(x^2+2*x+2,2*x+1,x,'m25','q25','characteristic'=0),m25,q25];
 $\left[{5}{,}{4}{,}{2}{}{x}{+}{3}\right]$ (30)
 > [PseudoDivision(x^2+2*x+2,2*x+1,x,'m26','q26','characteristic'=3),m26,q26];
 $\left[{2}{,}{1}{,}{2}{}{x}\right]$ (31)
 > [PseudoDivision(x^2,I*x-sqrt(2),x,'m27','q27','characteristic'=7),m27,q27];
 $\left[{2}{,}{6}{,}{I}{}{x}{+}\sqrt{{2}}\right]$ (32)

If a RootOf with a non-invertible leading coefficient is detected, an error may be returned:

 > PseudoDivision(x,RootOf(RootOf(_Z^2-_Z)*_Z+1)*x+1,x);

In the second case, using option 'symbolic'=true will force PseudoDivision to select one of the factors and perform the computation. Here, it makes the substitution $\mathrm{RootOf}\left(\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-\mathrm{_Z}\right)\mathrm{_Z}+1\right)=-1$:

 > [PseudoDivision(x,RootOf(RootOf(_Z^2-_Z)*_Z+1)*x+1,x,'m29','q29','symbolic'=true),m29,q29];
 $\left[{-1}{,}{-1}{,}{1}\right]$ (33)

With option 'makeindependent'=true, the input will be checked for algebraic dependencies even if there are more than $4$ algebraic objects in the input:

 > CubeRootOf[-4]:=RootOf(_Z^3+4,index=1);
 ${{\mathrm{CubeRootOf}}}_{{-4}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{+}{4}{,}{\mathrm{index}}{=}{1}\right)$ (34)
 > CubeRootOf[-2]:=RootOf(_Z^3+2,index=1);
 ${{\mathrm{CubeRootOf}}}_{{-2}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{+}{2}{,}{\mathrm{index}}{=}{1}\right)$ (35)
 > CubeRootOf[2]:=RootOf(_Z^3-2,index=1);
 ${{\mathrm{CubeRootOf}}}_{{2}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{2}{,}{\mathrm{index}}{=}{1}\right)$ (36)
 > CubeRootOf[3]:=RootOf(_Z^3-3,index=1);
 ${{\mathrm{CubeRootOf}}}_{{3}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{3}{,}{\mathrm{index}}{=}{1}\right)$ (37)
 > CubeRootOf[4]:=RootOf(_Z^3-4,index=1);
 ${{\mathrm{CubeRootOf}}}_{{4}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{4}{,}{\mathrm{index}}{=}{1}\right)$ (38)
 > CubeRootOf[6]:=RootOf(_Z^3-6,index=1);
 ${{\mathrm{CubeRootOf}}}_{{6}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{6}{,}{\mathrm{index}}{=}{1}\right)$ (39)
 > [PseudoDivision(x+CubeRootOf[4]*CubeRootOf[-2]*CubeRootOf[3],x+CubeRootOf[-4]*CubeRootOf[6],x,'m30','q30'),m30,q30];
 $\left[{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{+}{2}{,}{\mathrm{index}}{=}{1}\right){}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{3}{,}{\mathrm{index}}{=}{1}\right){}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{4}{,}{\mathrm{index}}{=}{1}\right){-}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{+}{4}{,}{\mathrm{index}}{=}{1}\right){}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{6}{,}{\mathrm{index}}{=}{1}\right){,}{1}{,}{1}\right]$ (40)
 > [PseudoDivision(x+CubeRootOf[4]*CubeRootOf[-2]*CubeRootOf[3],x+CubeRootOf[-4]*CubeRootOf[6],x,'m31','q31','makeindependent'=true),m31,q31];
 $\left[{0}{,}{1}{,}{1}\right]$ (41)

With option 'makeindependent'=false, the input will never be checked for algebraic dependencies:

 > [PseudoDivision(x+CubeRootOf[2]*CubeRootOf[3],x+CubeRootOf[6],x,'m32','q32'),m32,q32];
 $\left[{0}{,}{1}{,}{1}\right]$ (42)
 > [PseudoDivision(x+CubeRootOf[2]*CubeRootOf[3],x+CubeRootOf[6],x,'m33','q33','makeindependent'=false),m33,q33];
 $\left[{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{3}{,}{\mathrm{index}}{=}{1}\right){-}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{6}{,}{\mathrm{index}}{=}{1}\right){,}{1}{,}{1}\right]$ (43)