Algebraic - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

Algebraic

  

Squarefree

  

Square-free factorization of polynomials over algebraic extensions

 

Calling Sequence

Parameters

Options

Description

Examples

Calling Sequence

Squarefree(p, v, options)

Parameters

p

-

any algebraic expression; typically a polynomial or rational function in one or more variables.

v

-

(optional) name, set of names, or list of names; most functions can also be included and treated as variables.

options

-

(optional) equation(s) of the form keyword = value, where keyword is one of 'symbolic', 'expanded', 'makeindependent', or 'characteristic'.

Options

• 

If the option 'symbolic'=true is given and a RootOf whose minimal polynomial factors nontrivially is detected, then Squarefree will reduce it 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 'expanded'=true is given, then all polynomials in the factorization with the same multiplicity will be combined and expanded, producing a single polynomial factor of higher degree, but the same multiplicity.  In this case, all ei's in the output will be distinct. The default is 'expanded'=false.

• 

If the option 'characteristic'=p is given, where p is a non-negative integer, the square-free factorization is computed over an extension of the ring p of integers modulo p. The default is 'characteristic'=0 and means that the square-free factorization is computed over an extension of the rational numbers.

• 

In positive characteristic, if the input contains a RootOf with a reducible minimal polynomial, then squarefree may not return the correct squarefree factorization or may raise an error.  As well, correctness of the result is not guaranteed if the algebraic numbers in the input do not form an independent set of extensions.

• 

Note that if p is positive but not a prime, then p is not a field, so Squarefree may not be able to compute a square-free factorization of the input.  If it does not succeed because it encounters an integer that has no inverse modulo p, it issues the error "zero divisor modulo p detected".

• 

If the option 'makeindependent'=true is given, then Squarefree 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 Squarefree function computes a square-free factorization of the multivariate polynomial or rational function p in the variable(s) v over an algebraic number field.

• 

The square-free factorization is returned as a nested list of the form u,f1,e1,...,fn,en such that p=uf1e1...fnen where fi is a monic and square-free polynomial in the variable(s) v. Formally, GreatestCommonDivisor fi,vfi=1 for all i and GreatestCommonDivisor fi,fj=1 for all ij.  The coefficient u is an element of the coefficients field of p and is free of v. The fi's are collected with respect to the variable(s) v.

• 

Algebraic numbers may be represented by radicals or with the RootOf notation.  Usually, they will be returned in the same representation as they were received. (see type,algnum, type,radnum).

• 

Non-algebraic sub-expressions such as sinx 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 argument p is considered as a polynomial or a rational function in the variable(s) v. Other names are considered as elements of the coefficient field. If the optional argument v is omitted, then all the names in p are used (including non-algebraic sub-expressions).

• 

Functions such as sinx can also be included in v and treated as variables of p.  However, functions that are also of type AlgebraicObject, such as sinπ3 will be converted to algebraic numbers before proceeding, so they cannot be included. Proceed with caution when including functions in v, as treating some functions as variables may produce mathematically unsound results.

• 

The ei's will always be integers.  If p is a polynomial in v, then they will all be positive integers.  If p is a rational function in v, then factors in the denominator that cannot be cancelled will be returned with negative corresponding ei's.

• 

By default, the ei's may not be distinct, because partial factorizations in the input are preserved.  If the option 'expanded'=true is specified (see below), then factorizations of polynomials with the same multiplicity are not preserved, so all ei's will be distinct. In any case, the ei's are returned sorted by non-decreasing value.

• 

Algebraic numbers occurring in the result are reduced modulo their minimal polynomial (see Reduce).

• 

If p contains functions, their arguments will be normalized recursively (see Normal).

• 

Terms will be sorted according to a block-lexicographic ordering of the variables, where all global variables are considered larger than all local ones. If all variables have different names, then this ordering is session-independent.

• 

If the set of radicals and RootOfs in the input cannot be embedded into a field algebraically, then Squarefree may not be able to compute a square-free factorization. Squarefree 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 x.

Examples

withAlgebraic:

Introductory examples:

Squarefree2x2+4sqrt2xy+4y2

2,2y+x,2

(1)

Squarefreex4y5z2

1,z,−2,x,4,y,5

(2)

Squarefreex22x+sqrt2xRootOf_Z22,index=12

1,x2,−1,x+2,2

(3)

Squarefreex+sqrt2x+RootOf_Z22,index=1

1,x+2,2

(4)

Squarefreex2+12Ix+2x+RootOf_Z2+1,index=1

2I,xI,2,x+I,2

(5)

All factors in the output will be monic polynomials, even if rationals must be introduced:

Squarefree4x2+4x+1

4,x+12,2

(6)

p1expandx2+RootOf_Z223x+22z+3

p12x2z+3x2+2RootOf_Z223xz+3RootOf_Z223x+4z+6

(7)

Squarefreep1

2,z+32,1,x+RootOf_Z22,2

(8)

The input will be factored over the variable(s) given by the optional v parameter.  Variables not included in v will be treated as constants:

p23x2y4+12xy4+12y4

p23x2y4+12xy4+12y4

(9)

Squarefreep2

3,x+2,2,y,4

(10)

Squarefreep2,x,y

3,x+2,2,y,4

(11)

Squarefreep2,x

3y4,x+2,2

(12)

Squarefreep2,y

3x+22,y,4

(13)

Squarefreep2,z

3x2y4+12xy4+12y4,

(14)

The output will not necessarily be factored into a product of irreducibles, but partial factorization in the input is preserved, so long as no factors have a GCD greater than 1:

Squarefreex2+3x+2

1,x2+3x+2,1

(15)

Squarefreex+1x+2

1,x+1,1,x+2,1

(16)

Squarefreex+1x+2sqrt2x+RootOf_Z28,index=1

2,x+1,1,x+2,2

(17)

However, with option 'expanded'=true, factors with the same multiplicity will be combined and expanded:

Squarefreex+1x+2,expanded=true

1,x2+3x+2,1

(18)

Squarefreex2y2z3,expanded=true

1,xy,2,z,3

(19)

Trigonometric and exponential functions will be converted to an algebraic form, if possible:

Squarefreex+tanπ8x+RootOfx22,index=11

1,x+21,2

(20)

Squarefreex2+1x+expπI2

1,xI,1,x+I,2

(21)

All algebraic numbers will be reduced modulo their minimal polynomials (see Reduce):

Squarefreex5sqrt5x+RootOfZ25,index=23

1,x55,2

(22)

Squarefreex3RootOf_Z2+_Z+23

RootOf_Z2+_Z+2+2,x,3

(23)

Non-algebraic sub-expressions such as sinx will be frozen and replaced by new variables which are not treated as constants if optional argument v is not included:

Squarefreexsinx+2sinx

1,sinx,1,x+2,1

(24)

Squarefreexsinx+2sinx,x

sinx,x+2,1

(25)

Such functions can also be included in v, but use caution, as some functions may produce strange results.  Constants such as sinπ3 cannot be included, as they will be converted to algebraic numbers whenever possible:

Squarefreexsinx+2sinx,sinx

x+2,sinx,1

(26)

Squarefreeexpx+expπI2expx2+cos0

1,ⅇxI,1,ⅇx+I,2

(27)

The arguments of functions in the input will be recursively normalized and simplified (see Normal):

Squarefreesinx21x1+2sinx+124

1,sinx+12,1,sinx+1+2,2

(28)

Squarefreesinx+π2cosx

1,cosx,2

(29)

Non-algebraic subexpressions may evaluate to something algebraic after being normalized:

Squarefreex2+cosπy+πy+1x+14,x

1,x12,2

(30)

Algebraic functions such as y are not accepted:

Squarefreex2+2xsqrty+y

Error, (in Algebraic:-Normal) ratpoly(s) with radalgnum coefficients expected

Floats are not accepted.

Squarefreex2x+0.25

Error, (in Algebraic:-Squarefree) ratpoly(s) with radalgnum coefficients expected

When a non-indexed RootOf is given in the input, sometimes the square-free factorization can still be computed:

Squarefreex2+RootOf_Z24x+1

1,x+RootOf_Z242,2

(31)

Squarefreex2+RootOf_Z24,index=2x+1

1,x1,2

(32)

However, in this case, to compute a factorization, Squarefree must know whether RootOf_Z23_Z+2 represents 1 or 2, in order to guarantee that the output is actually square free:

Squarefreex+1x+RootOf_Z23_Z+2,index=1

1,x+1,2

(33)

Squarefreex+1x+RootOf_Z23_Z+2,index=2

1,x+1,1,x+2,1

(34)

Squarefreex+1x+RootOf_Z23_Z+2

Error, (in Algebraic:-Squarefree) reducible RootOf detected. Substitutions are {RootOf(_Z^2-3*_Z+2) = 1, RootOf(_Z^2-3*_Z+2) = 2}

To force Squarefree to reduce this RootOf to one of lower degree by picking one of the substitutions arbitrarily, use option 'symbolic'=true. Here, it makes the substitution RootOf_Z23_Z+2 = 2:

Squarefreex+1x+RootOf_Z23_Z+2,symbolic=true

1,x+1,1,x+2,1

(35)

Squarefree can factor out un-indexed RootOfs as constants, as long as they don't contain zero divisors:

SquarefreeRootOf_Z23_Z+2x2+RootOf_Z23_Z+2x4

RootOf_Z23_Z+2,x2+1,1,x,2

(36)

SquarefreeRootOf_Z2_Zx2+RootOf_Z2_Zx4

Error, (in Algebraic:-Squarefree) reducible RootOf detected. Substitutions are {RootOf(_Z^2-_Z) = 0, RootOf(_Z^2-_Z) = 1}

In this case, option 'symbolic'=true will eliminate the zero divisor:

SquarefreeRootOf_Z2_Zx2+RootOf_Z2_Zx4,symbolic=true

1,x2+1,1,x,2

(37)

Using option 'characteristic', the squarefree factorization can per performed over finite fields:

Squarefreex2+1,characteristic=2

1,x+1,2

(38)

aExpandx+y32x+y5x2,characteristic=3

a2x10+2yx9+2y2x8+y6x4+y7x3+y8x2

(39)

Squarefreea,characteristic=3

2,x,2,x+y,3,x+2y,5

(40)

bReduceevala,y=RootOf_Z3+2_Z+1,characteristic=3

b2RootOf_Z3+2_Z+12x8+2RootOf_Z3+2_Z+1x9+2x10+x4RootOf_Z3+2_Z+12+x3RootOf_Z3+2_Z+12+x4RootOf_Z3+2_Z+1+2x2RootOf_Z3+2_Z+12+2x3RootOf_Z3+2_Z+1+x4+2x3+2x2

(41)

Squarefreeb,characteristic=3

2,x,2,x+RootOf_Z3+2_Z+1,3,x+2RootOf_Z3+2_Z+1,5

(42)

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

CubeRootOf4RootOf_Z3+4,index=1

CubeRootOf−4RootOf_Z3+4,index=1

(43)

CubeRootOf2RootOf_Z3+2,index=1

CubeRootOf−2RootOf_Z3+2,index=1

(44)

CubeRootOf2RootOf_Z32,index=1

CubeRootOf2RootOf_Z32,index=1

(45)

CubeRootOf3RootOf_Z33,index=1

CubeRootOf3RootOf_Z33,index=1

(46)

CubeRootOf4RootOf_Z34,index=1

CubeRootOf4RootOf_Z34,index=1

(47)

CubeRootOf6RootOf_Z36,index=1

CubeRootOf6RootOf_Z36,index=1

(48)

Squarefreex+CubeRootOf4CubeRootOf2CubeRootOf3CubeRootOf4CubeRootOf6,x

1,RootOf_Z3+2,index=1RootOf_Z33,index=1RootOf_Z34,index=1RootOf_Z3+4,index=1RootOf_Z36,index=1+x,1

(49)

Squarefreex+CubeRootOf4CubeRootOf2CubeRootOf3CubeRootOf4CubeRootOf6,x,makeindependent=true

1,x,1

(50)

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

Squarefreex+CubeRootOf2CubeRootOf3CubeRootOf6,x

1,x,1

(51)

Squarefreex+CubeRootOf2CubeRootOf3CubeRootOf6,x,makeindependent=false

1,RootOf_Z32,index=1RootOf_Z33,index=1+xRootOf_Z36,index=1,1

(52)

See Also

Algebraic

Algebraic[GreatestCommonDivisor]

Algebraic[Normal]

evala,Sqrfree

sqrfree