manipulating polynomials

manipulating polynomials

+ -- a binary operator

- -- a unary or binary operator, usually used for negation or subtraction

* -- a binary operator, usually used for multiplication

^ -- a binary operator, usually used for exponents

// -- a binary operator, usually used for quotient

% -- a binary operator, usually used for remainder

terms -- provide a list of terms of a polynomial

diff -- differentiate

homogenize -- homogenize with respect to a variable

Let's set up some polynomials.

i1 : R = ZZ/10007[a,b];

i2 : f = (2*a+3)^4 + 5



        4      3       2

o2 = 16a  + 96a  + 216a  + 216a + 86



o2 : R

i3 : g = (2*a+b+1)^3



       3      2        2    3      2             2

o3 = 8a  + 12a b + 6a*b  + b  + 12a  + 12a*b + 3b  + 6a + 3b + 1



o3 : R

The number of terms in a polynomial is obtained with size.

i4 : size f, size g



o4 = (5, 10)



o4 : Sequence

The degree of a polynomial is obtained with degree.

i5 : degree f



o5 = {4}



o5 : List

i6 : degree g



o6 = {3}



o6 : List

(Notice that the degree is a list containing one integer, rather than an integer. The degree is actually a vector of integers, represented as a list, with one component by default.)

The list of terms of a polynomial is obtained with terms.

i7 : terms g



        3     2       2   3     2           2

o7 = {8a , 12a b, 6a*b , b , 12a , 12a*b, 3b , 6a, 3b, 1}



o7 : List

We may combine that with select to select terms satisfying certain conditions. Here we select the terms of degree 2, subsequently summing them, keeping in mind that the degree of a polynomial is always a list of integers.

i8 : select(terms g, i -> degree i == {2})



         2           2

o8 = {12a , 12a*b, 3b }



o8 : List

i9 : sum oo



        2             2

o9 = 12a  + 12a*b + 3b



o9 : R

Of course, if the list of selected terms is empty, the sum would turn out to be the zero integer, rather than the zero element of the ring R. Fortunately, we have another way to select the elements of given degree or multi-degree (see RingElement _ ZZ).

i10 : g_0



o10 = 1



o10 : R

i11 : g_1



o11 = 6a + 3b



o11 : R

i12 : g_2



         2             2

o12 = 12a  + 12a*b + 3b



o12 : R

i13 : g_3



        3      2        2    3

o13 = 8a  + 12a b + 6a*b  + b



o13 : R

A string representing the polynomial, suitable for entry into other programs, can be obtained with toString.

i14 : toString f



o14 = 16*a^4+96*a^3+216*a^2+216*a+86

i15 : toString g



o15 = 8*a^3+12*a^2*b+6*a*b^2+b^3+12*a^2+12*a*b+3*b^2+6*a+3*b+1

The usual algebraic operations on polynomials are available, but there are some special remarks to make about division. The result of division depends on the ordering of monomials chosen when the ring is created, for division of f by g proceeds by locating monomials in f divisible by the leading monomial of g, and substituting for it the negation of the rest of g. The quotient is provided by the expression f//g, and the remainder is obtained with f%g.

i16 : quot = f//g



o16 = 2a - 3b + 9



o16 : R

i17 : rem = f%g



         2 2        3     4      2         2      2              2

o17 = 24a b  + 16a*b  + 3b  - 96a b - 24a*b  + 96a  - 96a*b - 18b  + 160a - 24b + 77



o17 : R

i18 : f == quot * g + rem



o18 = true

Notice that as in the example above, comparison of polynomials is done with the operator ==.

Polynomials can be homogenized with respect to one of the variables in the ring with homogenize.

i19 : homogenize(f,b)



         4      3        2 2         3      4

o19 = 16a  + 96a b + 216a b  + 216a*b  + 86b



o19 : R

The ring containing a ring element can be obtained with ring.

i20 : ring f



o20 = R



o20 : PolynomialRing

You can use this in a program to check whether two ring elements come from the same ring.

i21 : ring f === ring g



o21 = true

Notice that in the comparison above, the strict equality operator === is used.

The coefficient of a monomial in a polynomial can be obtained with _.

i22 : f_1



o22 = 216a



o22 : R

i23 : f_a



o23 = 216



        ZZ

o23 : -----

      10007

i24 : g_(a*b)



o24 = 12



        ZZ

o24 : -----

      10007

(Notice that the coefficients are elements of the coefficient ring.)

We may get parts of the leading term of a polynomial as follows.

i25 : leadTerm g



        3

o25 = 8a



o25 : R

i26 : leadCoefficient g



o26 = 8



        ZZ

o26 : -----

      10007

i27 : leadMonomial g



       3

o27 = a



o27 : [a, b]

Notice that the lead monomial is an element of a monoid whose name is [a,b]. Its exponents can be extracted with exponents.

i28 : exponents leadMonomial g



o28 = {3, 0}



o28 : List

We can get all of the coefficients at once, assembled a one-rowed matrix, along with a matrix containing the corresponding monomials.

i29 : coefficients f



o29 = {| a4 a3 a2 a 1 |, | 16 96 216 216 86 |}



o29 : List

i30 : coefficients g



o30 = {| a3 a2b ab2 b3 a2 ab b2 a b 1 |, | 8 12 6 1 12 12 3 6 3 1 |}



o30 : List

A list of lists of exponents appearing in a polynomial can be obtained with exponents.

i31 : exponents f



o31 = {{4, 0}, {3, 0}, {2, 0}, {1, 0}, {0, 0}}



o31 : List

i32 : exponents g



o32 = {{3, 0}, {2, 1}, {1, 2}, {0, 3}, {2, 0}, {1, 1}, {0, 2}, {1, 0}, {0, 1}, {0, 0}}



o32 : List

The entire structure of a polynomial can be provided in an accessible form based on lists with listForm.

i33 : listForm f



o33 = {({4, 0}, 16), ({3, 0}, 96), ({2, 0}, 216), ({1, 0}, 216), ({0, 0}, 86)}



o33 : List

i34 : S = listForm g



o34 = {({3, 0}, 8), ({2, 1}, 12), ({1, 2}, 6), ({0, 3}, 1), ({2, 0}, 12), ({1, 1}, 12), ({0, 2}, 3), ({1, 0}, 6), ({0, 1}, 3), ({0, 0}, 1)}



o34 : List

The lists above are lists of pairs, where the first member of each pair is a list of exponents in a monomial, and the second member is the corresponding coefficient. Standard list operations can be used to manipulate the result.

i35 : S / print;

({3, 0}, 8)

({2, 1}, 12)

({1, 2}, 6)

({0, 3}, 1)

({2, 0}, 12)

({1, 1}, 12)

({0, 2}, 3)

({1, 0}, 6)

({0, 1}, 3)

({0, 0}, 1)

The structure of a polynomial can also be provided in a form based on hash tables with standardForm.

i36 : S = standardForm f



o36 = HashTable{HashTable{} => 86       }

                HashTable{0 => 1} => 216

                HashTable{0 => 2} => 216

                HashTable{0 => 3} => 96

                HashTable{0 => 4} => 16



o36 : HashTable

i37 : standardForm g



o37 = HashTable{HashTable{} => 1       }

                HashTable{0 => 1} => 6

                HashTable{0 => 1} => 12

                          1 => 1

                HashTable{0 => 1} => 6

                          1 => 2

                HashTable{0 => 2} => 12

                HashTable{0 => 2} => 12

                          1 => 1

                HashTable{0 => 3} => 8

                HashTable{1 => 1} => 3

                HashTable{1 => 2} => 3

                HashTable{1 => 3} => 1



o37 : HashTable

The hash tables above present the same information, except that only nonzero exponents need to be provided. The information can be extracted with #.

i38 : S#(new HashTable from {0 => 2})



o38 = 216



        ZZ

o38 : -----

      10007

Monomials (monoid elements) have an accessible form that is implicitly used above.

i39 : listForm leadMonomial g



o39 = {3, 0}



o39 : List

i40 : standardForm leadMonomial g



o40 = HashTable{0 => 3}



o40 : HashTable

Comparison of polynomials is possible, and proceeds by simply examining the lead monomials and comparing them.

i41 : f < g



o41 = true

i42 : sort {b^2-1,a*b,a+1,a,b}



        2

o42 = {b  - 1, a*b, b, a, a + 1}



o42 : List

The comparison operator ? returns a symbol indicating how two polynomials, or rather, their lead monomials, stand with respect to each other in the monomial ordering.

i43 : f ? g



o43 = <



o43 : Symbol