Subsections

11. Polynomial


11.1 Factorization

You can factor a polynomial using SAGE.

Using SAGE to factor a univariate polynomial is a matter of applying the method factor to the PolynomialRingElement object f. In fact, this method actually calls Pari, so the computation is fairly fast.

sage: x = PolynomialRing(RationalField()).gen()
sage: f = (x^3 - 1)^2-(x^2-1)^2
sage: f.factor()
      (x - 1)^2 * x^2 * (x^2 + 2*x + 2)

Using the Singular interface, SAGE also factors multivariate polynomials.

sage: x, y = MPolynomialRing(RationalField(), 2, ['x','y']).gens()
sage: f =  9*y^6 - 9*x^2*y^5 - 18*x^3*y^4 - 9*x^5*y^4 + 9*x^6*y^2 + 9*x^7*y^3 + 18*x^8*y^2 - 9*x^11
sage: f.factor()
(-9) * (-1*y^2 + x^5) * (y^4 - x^2*y^3 - 2*x^3*y^2 + x^6)

11.2 Polynomial GCD's

This example illustrates single variable polynomial GCD's:

sage: x = PolynomialRing(RationalField(), 'x').gen()
sage: f = 3*x**3 + x
sage: g = 9*x*(x+1)
sage: f.gcd(g)
x

This example illustrates multivariate polynomial GCD's:

sage: R = MPolynomialRing(RationalField(),3, ['x','y','z'], 'lex')
sage: x,y,z = MPolynomialRing(RationalField(),3, ['x','y','z'], 'lex').gens()
sage: f = 3*x**2*(x+y)
sage: g = 9*x*(y**2 - x**2)
sage: f.gcd(g)
x*y + x^2

Here's another way to do this:

sage: R2 = singular.ring(0, '(x,y,z)', 'lp')
sage: a = singular.new('3x2*(x+y)')
sage: b = singular.new('9x*(y2-x2)')
sage: g = a.gcd(b)
sage: g
x^2+x*y

This example illustrates univariate polynomial GCD's via the GAP interface.

sage: R = gap.PolynomialRing(gap.GF(2)); R
PolynomialRing(..., [ x_1 ])
sage: i = R.IndeterminatesOfPolynomialRing(); i
[ x_1 ]
sage: x_1 = i[1]
sage: f = (x_1**3 - x_1 + 1)*(x_1 + x_1**2); f
x_1^5+x_1^4+x_1^3+x_1
sage: g = (x_1**3 - x_1 + 1)*(x_1 + 1); g
x_1^4+x_1^3+x_1^2+Z(2)^0
sage: f.Gcd(g)
x_1^4+x_1^3+x_1^2+Z(2)^0
We can, of course, do the same computation in SAGE, which uses the NTL library (which does huge polynomial gcd's over finite fields very quickly).
sage: x = PolynomialRing(GF(2), 'x').gen()
sage: f = (x^3 - x + 1)*(x + x^2); f
x^5 + x^4 + x^3 + x
sage: g = (x^3 - x + 1)*(x + 1)
sage: f.gcd(g)
x^4 + x^3 + x^2 + 1


11.3 Roots of polynomials

SAGE can compute roots of a univariant polynomial.

sage: x = PolynomialRing(RationalField()).gen()
sage: f = x^3 - 1
sage: f.roots()
[(1, 1)]
sage: f = (x^3 - 1)^2
sage: f.roots()
[(1, 2)]
The first of the pair is the root, the second of the pair is its multiplicity.

Singular can solve multivariate polynomial equations in some situations (they assume that the solutions form a zero-dimensional variety).

There are some situations where GAP does find the roots of a polynomial but GAP does not do this generally. (The roots must generate either a finite field or a subfield of a cyclotomic field.) However, there is a package called RadiRoot which must be installed which does help to do this for polynomials with rational coefficients (radiroot itself requires other packages to be installed; please see the webpage for more details).

The Factors command actually has an option which allows you to increase the groundfield so that a factorization actually returns the roots. Please see the examples given in section 64.10 ``Polynomial Factorization" for more details.

Here is a second appoach. Using gap_console(), one can work directly on the GAP command line within SAGE.

sage: gap_console()
gap> p := 3; n := 4; F := GF(p^n); c := Random(F); r := 2;
3
4
GF(3^4)
Z(3^4)^79
2
gap>  x := X(F,1); f := x^r-c*x+c-1;
x_1
x_1^2+Z(3^4)^39*x_1+Z(3^4)^36
gap>  F_f := FieldExtension( F, f );
AsField( GF(3^4), GF(3^8) )
gap>  alpha := RootOfDefiningPolynomial(F_f);
Z(3^4)^36
gap> Value(f,[x],[alpha]);
0*Z(3)

Here is a third. First, enter the following program:

RootOfPolynomial := function(f,R)
 local F0,Ff,a;
 F0 := CoefficientsRing(R);
 Ff := FieldExtension(F0,f);
 a := RootOfDefiningPolynomial(Ff);
 return a;
end;

Here's how this can be used to find a root:

gap> F := Rationals;
Rationals
gap> x := X(F,1); f := x^2+x+1;
x_1
x_1^2+x_1+1
gap> R := PolynomialRing( F, [ x ]);
PolynomialRing(..., [ x_1 ])
gap> a := RootOfPolynomial(f,R);
E(3)
gap> # check:
gap> Value(f,[x],[a]);
0

11.4 Evaluation of multivariate functions

You can evaluate polynomials in SAGE as usual by substituting in points:

sage: x = MPolynomialRing(RationalField(), 3).gens()
sage: f = x[0] + x[1] - 2*x[1]*x[2]
sage: f
x1 - 2*x1*x2 + x0
sage: f(1,2,0)
3
sage: f(1,2,5)
-17

This also will work with rational functions:

sage: h = f /(x[1] + x[2])
sage: h
(x1 - 2*x1*x2 + x0)/(x2 + x1)
sage: h(1,2,3)
-9/5

Maxima will perform symbolic manipulation:

sage: f = maxima('(x + 3*y + x^2*y)^3')
sage: f.expand()
x^6*y^3 + 9*x^4*y^3 + 27*x^2*y^3 + 27*y^3 + 3*x^5*y^2 + 18*x^3*y^2 +
27*x*y^2 + 3*x^4*y + 9*x^2*y + x^3
sage: f.subst('x=5/z')
(5/z + 25*y/z^2 + 3*y)^3
sage: g = f.subst('x=5/z')
sage: h = g.ratsimp(); h
(27*y^3*z^6 + 135*y^2*z^5 + (675*y^3 + 225*y)*z^4 + (2250*y^2 + 125)*z^3 +
(5625*y^3 + 1875*y)*z^2 + 9375*y^2*z + 15625*y^3)/z^6


11.5 Gröbner bases

This computation uses Singular behind the scenes to compute Gröbner basis.

sage: R = PolynomialRing(QQ, 4, 'abcd', order='lp')
sage: a,b,c,d = R.gens()
sage: I = (a+b+c+d, a*b+a*d+b*c+c*d, a*b*c+a*b*d+a*c*d+b*c*d, a*b*c*d-1)*R; I
Ideal (-1 + a*b*c*d, d + c + b + a, c*d + b*c + a*d + a*b, b*c*d + a*c*d + a*b*d + a*b*c) of Polynomial Ring in a, b, c, d over Rational Field
sage: B = I.groebner_basis(); B
[1 - d^4 - c^2*d^2 + c^2*d^6,
 -1*d - c + c^2*d^3 + c^3*d^2,
 -1*d + d^5 - b + b*d^4,
 -1*d^2 - d^6 + c*d + c^2*d^4 - b*d^5 + b*c,
 d^2 + 2*b*d + b^2,
 d + c + b + a]

You can work with multiple rings without having to switch back and forth like in Singular. For example,

sage: a,b,c = QQ['a,b,c'].gens()
sage: X,Y = GF(7)['X,Y'].gens()
sage: I = ideal(a, b^2, b^3+c^3)
sage: J = ideal(X^10 + Y^10)

sage: I.minimal_associated_primes ()
[Ideal (c, b, a) of Polynomial Ring in a, b, c over Rational Field]

sage: J.minimal_associated_primes ()     # slightly random output
[Ideal (Y^4 + 3*X*Y^3 + 4*X^2*Y^2 + 4*X^3*Y + X^4) of Polynomial Ring in X, Y over Finite Field of size 7, 
 Ideal (Y^4 + 4*X*Y^3 + 4*X^2*Y^2 + 3*X^3*Y + X^4) of Polynomial Ring in X, Y over Finite Field of size 7, 
 Ideal (Y^2 + X^2) of Polynomial Ring in X, Y over Finite Field of size 7]
All the real work is done by Singular.

See About this document... for information on suggesting changes.