Univariate Polynomial Base Class
AUTHORS:
TESTS:
sage: R.<x> = ZZ[]
sage: f = x^5 + 2*x^2 + (-1)
sage: f == loads(dumps(f))
True
Bases: sage.categories.map.Map
This class is used for conversion from a polynomial ring to its base ring.
Since trac ticket #9944, it calls the constant_coefficient method, which can be optimized for a particular polynomial type.
EXAMPLES:
sage: P0.<y_1> = GF(3)[]
sage: P1.<y_2,y_1,y_0> = GF(3)[]
sage: P0(-y_1) # indirect doctest
2*y_1
sage: phi = GF(3).convert_map_from(P0); phi
Generic map:
From: Univariate Polynomial Ring in y_1 over Finite Field of size 3
To: Finite Field of size 3
sage: type(phi)
<type 'sage.rings.polynomial.polynomial_element.ConstantPolynomialSection'>
sage: phi(P0.one_element())
1
sage: phi(y_1)
Traceback (most recent call last):
...
TypeError: not a constant polynomial
Bases: sage.structure.element.CommutativeAlgebraElement
A polynomial.
EXAMPLE:
sage: R.<y> = QQ['y']
sage: S.<x> = R['x']
sage: f = x*y; f
y*x
sage: type(f)
<type 'sage.rings.polynomial.polynomial_element.Polynomial_generic_dense'>
sage: p = (y+1)^10; p(1)
1024
Returns the power series of precision at most prec got by adding
to self, where q is its variable.
EXAMPLES:
sage: R.<x> = ZZ[]
sage: f = 1 + 4*x + x^3
sage: f.add_bigoh(7)
1 + 4*x + x^3 + O(x^7)
sage: f.add_bigoh(2)
1 + 4*x + O(x^2)
sage: f.add_bigoh(2).parent()
Power Series Ring in x over Integer Ring
Return a root of this polynomial in the given ring.
INPUT:
EXAMPLES:
sage: R.<x> = GF(11)[]
sage: f = 7*x^7 + 8*x^6 + 4*x^5 + x^4 + 6*x^3 + 10*x^2 + 8*x + 5
sage: f.any_root()
2
sage: f.factor()
(7) * (x + 9) * (x^6 + 10*x^4 + 6*x^3 + 5*x^2 + 2*x + 2)
sage: f = x^6 + 10*x^4 + 6*x^3 + 5*x^2 + 2*x + 2
sage: f.any_root(GF(11^6, 'a'))
a^5 + a^4 + 7*a^3 + 2*a^2 + 10*a
sage: sorted(f.roots(GF(11^6, 'a')))
[(10*a^5 + 2*a^4 + 8*a^3 + 9*a^2 + a, 1), (a^5 + a^4 + 7*a^3 + 2*a^2 + 10*a, 1), (9*a^5 + 5*a^4 + 10*a^3 + 8*a^2 + 3*a + 1, 1), (2*a^5 + 8*a^4 + 3*a^3 + 6*a + 2, 1), (a^5 + 3*a^4 + 8*a^3 + 2*a^2 + 3*a + 4, 1), (10*a^5 + 3*a^4 + 8*a^3 + a^2 + 10*a + 4, 1)]
sage: f.any_root(GF(11^6, 'a'))
a^5 + a^4 + 7*a^3 + 2*a^2 + 10*a
sage: g = (x-1)*(x^2 + 3*x + 9) * (x^5 + 5*x^4 + 8*x^3 + 5*x^2 + 3*x + 5)
sage: g.any_root(ring=GF(11^10, 'b'), degree=1)
1
sage: g.any_root(ring=GF(11^10, 'b'), degree=2)
5*b^9 + 4*b^7 + 4*b^6 + 8*b^5 + 10*b^2 + 10*b + 5
sage: g.any_root(ring=GF(11^10, 'b'), degree=5)
5*b^9 + b^8 + 3*b^7 + 2*b^6 + b^5 + 4*b^4 + 3*b^3 + 7*b^2 + 10*b
TESTS:
sage: R.<x> = GF(5)[]
sage: K.<a> = GF(5^12)
sage: for _ in range(40):
....: f = R.random_element(degree=4)
....: assert f(f.any_root(K)) == 0
Check that our Cantor-Zassenhaus implementation does not loop over finite fields of even characteristic (see trac ticket #16162):
sage: K.<a> = GF(2**8)
sage: x = polygen(K)
sage: (x**2+x+1).any_root() # used to loop
Traceback (most recent call last):
...
ValueError: no roots A 1
sage: (x**2+a+1).any_root()
a^7 + a^2
Also check that such computations can be interrupted:
sage: K.<a> = GF(2^8)
sage: x = polygen(K)
sage: pol = x^1000000 + x + a
sage: alarm(0.5); pol.any_root()
Traceback (most recent call last):
...
AlarmInterrupt
Check root computation over large finite fields:
sage: K.<a> = GF(2**50)
sage: x = polygen(K)
sage: (x**10+x+a).any_root()
a^49 + a^47 + a^44 + a^42 + a^41 + a^39 + a^38 + a^37 + a^36 + a^34 + a^33 + a^29 + a^27 + a^26 + a^25 + a^23 + a^18 + a^13 + a^7 + a^5 + a^4 + a^3 + a^2 + a
sage: K.<a> = GF(2**150)
sage: x = polygen(K)
sage: (x**10+x+a).any_root()
a^149 + a^148 + a^146 + a^144 + a^143 + a^140 + a^138 + a^136 + a^134 + a^132 + a^131 + a^130 + a^129 + a^127 + a^123 + a^120 + a^118 + a^114 + a^113 + a^112 + a^111 + a^108 + a^104 + a^103 + a^102 + a^99 + a^98 + a^94 + a^91 + a^90 + a^88 + a^79 + a^78 + a^75 + a^73 + a^72 + a^67 + a^65 + a^64 + a^63 + a^62 + a^61 + a^59 + a^57 + a^52 + a^50 + a^48 + a^47 + a^46 + a^45 + a^43 + a^41 + a^39 + a^37 + a^34 + a^31 + a^29 + a^27 + a^25 + a^23 + a^22 + a^20 + a^18 + a^16 + a^14 + a^11 + a^10 + a^8 + a^6 + a^5 + a^4 + a + 1
Returns the generator of this polynomial ring, which is the (only) argument used when calling self.
EXAMPLES:
sage: R.<x> = QQ[]
sage: x.args()
(x,)
A constant polynomial has no variables, but still takes a single argument.
sage: R(2).args()
(x,)
Return a copy of this polynomial but with coefficients in R, if there is a natural map from coefficient ring of self to R.
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x^3 - 17*x + 3
sage: f.base_extend(GF(7))
Traceback (most recent call last):
...
TypeError: no such base extension
sage: f.change_ring(GF(7))
x^3 + 4*x + 3
Return the base ring of the parent of self.
EXAMPLES:
sage: R.<x> = ZZ[]
sage: x.base_ring()
Integer Ring
sage: (2*x+3).base_ring()
Integer Ring
Return a copy of this polynomial but with coefficients in R, if at all possible.
EXAMPLES:
sage: K.<z> = CyclotomicField(3)
sage: f = K.defining_polynomial()
sage: f.change_ring(GF(7))
x^2 + x + 1
Return a new polynomial over the same base ring but in a different variable.
EXAMPLES:
sage: x = polygen(QQ,'x')
sage: f = -2/7*x^3 + (2/3)*x - 19/993; f
-2/7*x^3 + 2/3*x - 19/993
sage: f.change_variable_name('theta')
-2/7*theta^3 + 2/3*theta - 19/993
Return the coefficients of the monomials appearing in self. If sparse=True (the default), it returns only the non-zero coefficients. Otherwise, it returns the same value as self.list(). (In this case, it may be slightly faster to invoke self.list() directly.)
EXAMPLES:
sage: _.<x> = PolynomialRing(ZZ)
sage: f = x^4+2*x^2+1
sage: f.coefficients()
[1, 2, 1]
sage: f.coefficients(sparse=False)
[1, 0, 2, 0, 1]
Using coeffs() is now deprecated (trac ticket #17518). Returns self.list().
(It is potentially slightly faster to use self.list() directly.)
EXAMPLES:
sage: x = QQ['x'].0
sage: f = 10*x^3 + 5*x + 2/17
sage: f.coeffs()
doctest:...: DeprecationWarning: The use of coeffs() is now deprecated in favor of coefficients(sparse=False).
See http://trac.sagemath.org/17518 for details.
[2/17, 5, 0, 10]
Return the complex roots of this polynomial, without multiplicities.
Calls self.roots(ring=CC), unless this is a polynomial with floating-point coefficients, in which case it is uses the appropriate precision from the input coefficients.
EXAMPLES:
sage: x = polygen(ZZ)
sage: (x^3 - 1).complex_roots() # note: low order bits slightly different on ppc.
[1.00000000000000, -0.500000000000000 - 0.86602540378443...*I, -0.500000000000000 + 0.86602540378443...*I]
TESTS:
sage: x = polygen(RR)
sage: (x^3 - 1).complex_roots()[0].parent()
Complex Field with 53 bits of precision
sage: x = polygen(RDF)
sage: (x^3 - 1).complex_roots()[0].parent()
Complex Double Field
sage: x = polygen(RealField(200))
sage: (x^3 - 1).complex_roots()[0].parent()
Complex Field with 200 bits of precision
sage: x = polygen(CDF)
sage: (x^3 - 1).complex_roots()[0].parent()
Complex Double Field
sage: x = polygen(ComplexField(200))
sage: (x^3 - 1).complex_roots()[0].parent()
Complex Field with 200 bits of precision
sage: x=polygen(ZZ,'x'); v=(x^2-x-1).complex_roots()
sage: v[0].parent() is CC
True
Return the constant coefficient of this polynomial.
OUTPUT: element of base ring
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = -2*x^3 + 2*x - 1/3
sage: f.constant_coefficient()
-1/3
Return the content of self, which is the ideal generated by the coefficients of self.
EXAMPLES:
sage: R.<x> = IntegerModRing(4)[]
sage: f = x^4 + 3*x^2 + 2
sage: f.content()
Ideal (2, 3, 1) of Ring of integers modulo 4
Return the degree of this polynomial. The zero polynomial has degree -1.
EXAMPLES:
sage: x = ZZ['x'].0
sage: f = x^93 + 2*x + 1
sage: f.degree()
93
sage: x = PolynomialRing(QQ, 'x', sparse=True).0
sage: f = x^100000
sage: f.degree()
100000
sage: x = QQ['x'].0
sage: f = 2006*x^2006 - x^2 + 3
sage: f.degree()
2006
sage: f = 0*x
sage: f.degree()
-1
sage: f = x + 33
sage: f.degree()
1
AUTHORS:
Return a denominator of self.
First, the lcm of the denominators of the entries of self is computed and returned. If this computation fails, the unit of the parent of self is returned.
Note that some subclasses may implement their own denominator function. For example, see sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint
Warning
This is not the denominator of the rational function defined by self, which would always be 1 since self is a polynomial.
EXAMPLES:
First we compute the denominator of a polynomial with integer coefficients, which is of course 1.
sage: R.<x> = ZZ[]
sage: f = x^3 + 17*x + 1
sage: f.denominator()
1
Next we compute the denominator of a polynomial with rational coefficients.
sage: R.<x> = PolynomialRing(QQ)
sage: f = (1/17)*x^19 - (2/3)*x + 1/3; f
1/17*x^19 - 2/3*x + 1/3
sage: f.denominator()
51
Finally, we try to compute the denominator of a polynomial with coefficients in the real numbers, which is a ring whose elements do not have a denominator method.
sage: R.<x> = RR[]
sage: f = x + RR('0.3'); f
x + 0.300000000000000
sage: f.denominator()
1.00000000000000
Check that the denominator is an element over the base whenever the base has no denominator function. This closes #9063.
sage: R.<a> = GF(5)[]
sage: x = R(0)
sage: x.denominator()
1
sage: type(x.denominator())
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>
sage: isinstance(x.numerator() / x.denominator(), Polynomial)
True
sage: isinstance(x.numerator() / R(1), Polynomial)
False
The formal derivative of this polynomial, with respect to variables supplied in args.
Multiple variables and iteration counts may be supplied; see documentation for the global derivative() function for more details.
See also
_derivative()
EXAMPLES:
sage: R.<x> = PolynomialRing(QQ)
sage: g = -x^4 + x^2/2 - x
sage: g.derivative()
-4*x^3 + x - 1
sage: g.derivative(x)
-4*x^3 + x - 1
sage: g.derivative(x, x)
-12*x^2 + 1
sage: g.derivative(x, 2)
-12*x^2 + 1
sage: R.<t> = PolynomialRing(ZZ)
sage: S.<x> = PolynomialRing(R)
sage: f = t^3*x^2 + t^4*x^3
sage: f.derivative()
3*t^4*x^2 + 2*t^3*x
sage: f.derivative(x)
3*t^4*x^2 + 2*t^3*x
sage: f.derivative(t)
4*t^3*x^3 + 3*t^2*x^2
Return a sparse dictionary representation of this univariate polynomial.
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x^3 + -1/7*x + 13
sage: f.dict()
{0: 13, 1: -1/7, 3: 1}
The formal derivative of this polynomial, with respect to variables supplied in args.
Multiple variables and iteration counts may be supplied; see documentation for the global derivative() function for more details.
See also
_derivative()
EXAMPLES:
sage: R.<x> = PolynomialRing(QQ)
sage: g = -x^4 + x^2/2 - x
sage: g.derivative()
-4*x^3 + x - 1
sage: g.derivative(x)
-4*x^3 + x - 1
sage: g.derivative(x, x)
-12*x^2 + 1
sage: g.derivative(x, 2)
-12*x^2 + 1
sage: R.<t> = PolynomialRing(ZZ)
sage: S.<x> = PolynomialRing(R)
sage: f = t^3*x^2 + t^4*x^3
sage: f.derivative()
3*t^4*x^2 + 2*t^3*x
sage: f.derivative(x)
3*t^4*x^2 + 2*t^3*x
sage: f.derivative(t)
4*t^3*x^3 + 3*t^2*x^2
The formal derivative of this polynomial, with respect to variables supplied in args.
Multiple variables and iteration counts may be supplied; see documentation for the global derivative() function for more details.
See also
_derivative()
EXAMPLES:
sage: R.<x> = PolynomialRing(QQ)
sage: g = -x^4 + x^2/2 - x
sage: g.derivative()
-4*x^3 + x - 1
sage: g.derivative(x)
-4*x^3 + x - 1
sage: g.derivative(x, x)
-12*x^2 + 1
sage: g.derivative(x, 2)
-12*x^2 + 1
sage: R.<t> = PolynomialRing(ZZ)
sage: S.<x> = PolynomialRing(R)
sage: f = t^3*x^2 + t^4*x^3
sage: f.derivative()
3*t^4*x^2 + 2*t^3*x
sage: f.derivative(x)
3*t^4*x^2 + 2*t^3*x
sage: f.derivative(t)
4*t^3*x^3 + 3*t^2*x^2
Returns the discriminant of self.
The discriminant is
where is the degree of self,
is the
leading coefficient of self and the roots of self are
.
OUTPUT: An element of the base ring of the polynomial ring.
Note
Uses the identity , where
is the degree of self,
is the leading coefficient of self,
is the derivative of
, and
is the degree
of
. Calls resultant().
EXAMPLES:
In the case of elliptic curves in special form, the discriminant is easy to calculate:
sage: R.<x> = QQ[]
sage: f = x^3 + x + 1
sage: d = f.discriminant(); d
-31
sage: d.parent() is QQ
True
sage: EllipticCurve([1, 1]).discriminant()/16
-31
sage: R.<x> = QQ[]
sage: f = 2*x^3 + x + 1
sage: d = f.discriminant(); d
-116
We can also compute discriminants over univariate and multivariate polynomial rings, provided that PARI’s variable ordering requirements are respected. Usually, your discriminants will work if you always ask for them in the variable x:
sage: R.<a> = QQ[]
sage: S.<x> = R[]
sage: f = a*x + x + a + 1
sage: d = f.discriminant(); d
1
sage: d.parent() is R
True
sage: R.<a, b> = QQ[]
sage: S.<x> = R[]
sage: f = x^2 + a + b
sage: d = f.discriminant(); d
-4*a - 4*b
sage: d.parent() is R
True
Unfortunately Sage does not handle PARI’s variable ordering requirements gracefully, so the following has to be done through Singular:
sage: R.<x, y> = QQ[]
sage: S.<a> = R[]
sage: f = x^2 + a
sage: f.discriminant()
1
Check that trac ticket #13672 is fixed:
sage: R.<t> = GF(5)[]
sage: S.<x> = R[]
sage: f = x^10 + 2*x^6 + 2*x^5 + x + 2
sage: (f-t).discriminant()
4*t^5
The following examples show that trac ticket #11782 has been fixed:
sage: ZZ.quo(81)[x](3*x^2 + 3*x + 3).discriminant()
54
sage: ZZ.quo(9)[x](2*x^3 + x^2 + x).discriminant()
2
This was fixed by trac ticket #15422:
sage: R.<s> = PolynomialRing(Qp(2))
sage: (s^2).discriminant()
0
TESTS:
This was fixed by trac ticket #16014:
sage: PR.<b,t1,t2,x1,y1,x2,y2> = QQ[]
sage: PRmu.<mu> = PR[]
sage: E1 = diagonal_matrix(PR, [1, b^2, -b^2])
sage: M = matrix(PR, [[1,-t1,x1-t1*y1],[t1,1,y1+t1*x1],[0,0,1]])
sage: E1 = M.transpose()*E1*M
sage: E2 = E1.subs(t1=t2, x1=x2, y1=y2)
sage: det(mu*E1 + E2).discriminant().degrees()
(24, 12, 12, 8, 8, 8, 8)
This addresses an issue raised by trac ticket #15061:
sage: R.<T> = PowerSeriesRing(QQ)
sage: F = R([1,1],2)
sage: RP.<x> = PolynomialRing(R)
sage: P = x^2 - F
sage: P.discriminant()
4 + 4*T + O(T^2)
Return the degree of this element as an element of a euclidean domain.
If this polynomial is defined over a field, this is simply its degree().
EXAMPLES:
sage: R.<x> = QQ[]
sage: x.euclidean_degree()
1
sage: R.<x> = ZZ[]
sage: x.euclidean_degree()
Traceback (most recent call last):
...
NotImplementedError
Return the exponents of the monomials appearing in self.
EXAMPLES:
sage: _.<x> = PolynomialRing(ZZ)
sage: f = x^4+2*x^2+1
sage: f.exponents()
[0, 2, 4]
Return the factorization of self over its base ring.
INPUT:
OUTPUT:
EXAMPLES:
Factorization is implemented over various rings. Over :
sage: x = QQ['x'].0
sage: f = (x^3 - 1)^2
sage: f.factor()
(x - 1)^2 * (x^2 + x + 1)^2
Since is a field, the irreducible factors are monic:
sage: f = 10*x^5 - 1
sage: f.factor()
(10) * (x^5 - 1/10)
sage: f = 10*x^5 - 10
sage: f.factor()
(10) * (x - 1) * (x^4 + x^3 + x^2 + x + 1)
Over the irreducible factors need not be monic:
sage: x = ZZ['x'].0
sage: f = 10*x^5 - 1
sage: f.factor()
10*x^5 - 1
We factor a non-monic polynomial over a finite field of 25 elements:
sage: k.<a> = GF(25)
sage: R.<x> = k[]
sage: f = 2*x^10 + 2*x + 2*a
sage: F = f.factor(); F
(2) * (x + a + 2) * (x^2 + 3*x + 4*a + 4) * (x^2 + (a + 1)*x + a + 2) * (x^5 + (3*a + 4)*x^4 + (3*a + 3)*x^3 + 2*a*x^2 + (3*a + 1)*x + 3*a + 1)
Notice that the unit factor is included when we multiply
back out:
sage: expand(F)
2*x^10 + 2*x + 2*a
A new ring. In the example below, we set the special method _factor_univariate_polynomial() in the base ring which is called to factor univariate polynomials. This facility can be used to easily extend polynomial factorization to work over new rings you introduce:
sage: R.<x> = PolynomialRing(IntegerModRing(4),implementation="NTL")
sage: (x^2).factor()
Traceback (most recent call last):
...
NotImplementedError: factorization of polynomials over rings with composite characteristic is not implemented
sage: R.base_ring()._factor_univariate_polynomial = lambda f: f.change_ring(ZZ).factor()
sage: (x^2).factor()
x^2
sage: del R.base_ring()._factor_univariate_polynomial # clean up
Arbitrary precision real and complex factorization:
sage: R.<x> = RealField(100)[]
sage: F = factor(x^2-3); F
(x - 1.7320508075688772935274463415) * (x + 1.7320508075688772935274463415)
sage: expand(F)
x^2 - 3.0000000000000000000000000000
sage: factor(x^2 + 1)
x^2 + 1.0000000000000000000000000000
sage: R.<x> = ComplexField(100)[]
sage: F = factor(x^2+3); F
(x - 1.7320508075688772935274463415*I) * (x + 1.7320508075688772935274463415*I)
sage: expand(F)
x^2 + 3.0000000000000000000000000000
sage: factor(x^2+1)
(x - I) * (x + I)
sage: f = R(I) * (x^2 + 1) ; f
I*x^2 + I
sage: F = factor(f); F
(1.0000000000000000000000000000*I) * (x - I) * (x + I)
sage: expand(F)
I*x^2 + I
Over a number field:
sage: K.<z> = CyclotomicField(15)
sage: x = polygen(K)
sage: ((x^3 + z*x + 1)^3*(x - z)).factor()
(x - z) * (x^3 + z*x + 1)^3
sage: cyclotomic_polynomial(12).change_ring(K).factor()
(x^2 - z^5 - 1) * (x^2 + z^5)
sage: ((x^3 + z*x + 1)^3*(x/(z+2) - 1/3)).factor()
(-1/331*z^7 + 3/331*z^6 - 6/331*z^5 + 11/331*z^4 - 21/331*z^3 + 41/331*z^2 - 82/331*z + 165/331) * (x - 1/3*z - 2/3) * (x^3 + z*x + 1)^3
Over a relative number field:
sage: x = polygen(QQ)
sage: K.<z> = CyclotomicField(3)
sage: L.<a> = K.extension(x^3 - 2)
sage: t = polygen(L, 't')
sage: f = (t^3 + t + a)*(t^5 + t + z); f
t^8 + t^6 + a*t^5 + t^4 + z*t^3 + t^2 + (a + z)*t + z*a
sage: f.factor()
(t^3 + t + a) * (t^5 + t + z)
Over the real double field:
sage: R.<x> = RDF[]
sage: (-2*x^2 - 1).factor()
(-2.0) * (x^2 + 0.5000000000000001)
sage: (-2*x^2 - 1).factor().expand()
-2.0*x^2 - 1.0000000000000002
sage: f = (x - 1)^3
sage: f.factor() # abs tol 2e-5
(x - 1.0000065719436413) * (x^2 - 1.9999934280563585*x + 0.9999934280995487)
The above output is incorrect because it relies on the roots() method, which does not detect that all the roots are real:
sage: f.roots() # abs tol 2e-5
[(1.0000065719436413, 1)]
Over the complex double field the factors are approximate and therefore occur with multiplicity 1:
sage: R.<x> = CDF[]
sage: f = (x^2 + 2*R(I))^3
sage: F = f.factor()
sage: F # abs tol 3e-5
(x - 1.0000138879287663 + 1.0000013435286879*I) * (x - 0.9999942196864997 + 0.9999873009803959*I) * (x - 0.9999918923847313 + 1.0000113554909125*I) * (x + 0.9999908759550227 - 1.0000069659624138*I) * (x + 0.9999985293216753 - 0.9999886153831807*I) * (x + 1.0000105947233 - 1.0000044186544053*I)
sage: [f(t[0][0]).abs() for t in F] # abs tol 1e-13
[1.979365054e-14, 1.97936298566e-14, 1.97936990747e-14, 3.6812407475e-14, 3.65211563729e-14, 3.65220890052e-14]
Factoring polynomials over for
composite
is not implemented:
sage: R.<x> = PolynomialRing(Integers(35))
sage: f = (x^2+2*x+2)*(x^2+3*x+9)
sage: f.factor()
Traceback (most recent call last):
...
NotImplementedError: factorization of polynomials over rings with composite characteristic is not implemented
Factoring polynomials over the algebraic numbers (see trac ticket #8544):
sage: R.<x> = QQbar[]
sage: (x^8-1).factor()
(x - 1) * (x - 0.7071067811865475? - 0.7071067811865475?*I) * (x - 0.7071067811865475? + 0.7071067811865475?*I) * (x - I) * (x + I) * (x + 0.7071067811865475? - 0.7071067811865475?*I) * (x + 0.7071067811865475? + 0.7071067811865475?*I) * (x + 1)
Factoring polynomials over the algebraic reals (see trac ticket #8544):
sage: R.<x> = AA[]
sage: (x^8+1).factor()
(x^2 - 1.847759065022574?*x + 1.000000000000000?) * (x^2 - 0.7653668647301795?*x + 1.000000000000000?) * (x^2 + 0.7653668647301795?*x + 1.000000000000000?) * (x^2 + 1.847759065022574?*x + 1.000000000000000?)
TESTS:
This came up in ticket #7088:
sage: R.<x>=PolynomialRing(ZZ)
sage: f = 12*x^10 + x^9 + 432*x^3 + 9011
sage: g = 13*x^11 + 89*x^3 + 1
sage: F = f^2 * g^3
sage: F = f^2 * g^3; F.factor()
(12*x^10 + x^9 + 432*x^3 + 9011)^2 * (13*x^11 + 89*x^3 + 1)^3
sage: F = f^2 * g^3 * 7; F.factor()
7 * (12*x^10 + x^9 + 432*x^3 + 9011)^2 * (13*x^11 + 89*x^3 + 1)^3
This example came up in ticket #7097:
sage: x = polygen(QQ)
sage: f = 8*x^9 + 42*x^6 + 6*x^3 - 1
sage: g = x^24 - 12*x^23 + 72*x^22 - 286*x^21 + 849*x^20 - 2022*x^19 + 4034*x^18 - 6894*x^17 + 10182*x^16 - 13048*x^15 + 14532*x^14 - 13974*x^13 + 11365*x^12 - 7578*x^11 + 4038*x^10 - 1766*x^9 + 762*x^8 - 408*x^7 + 236*x^6 - 126*x^5 + 69*x^4 - 38*x^3 + 18*x^2 - 6*x + 1
sage: assert g.is_irreducible()
sage: K.<a> = NumberField(g)
sage: len(f.roots(K))
9
sage: f.factor()
(8) * (x^3 + 1/4) * (x^6 + 5*x^3 - 1/2)
sage: f.change_ring(K).factor()
(8) * (x - 3260097/3158212*a^22 + 35861067/3158212*a^21 - 197810817/3158212*a^20 + 722970825/3158212*a^19 - 1980508347/3158212*a^18 + 4374189477/3158212*a^17 - 4059860553/1579106*a^16 + 6442403031/1579106*a^15 - 17542341771/3158212*a^14 + 20537782665/3158212*a^13 - 20658463789/3158212*a^12 + 17502836649/3158212*a^11 - 11908953451/3158212*a^10 + 6086953981/3158212*a^9 - 559822335/789553*a^8 + 194545353/789553*a^7 - 505969453/3158212*a^6 + 338959407/3158212*a^5 - 155204647/3158212*a^4 + 79628015/3158212*a^3 - 57339525/3158212*a^2 + 26692783/3158212*a - 1636338/789553) * ...
sage: f = QQbar['x'](1)
sage: f.factor()
1
Factorization also works even if the variable of the finite field is nefariously labeled “x”:
sage: R.<x> = GF(3^2, 'x')[]
sage: f = x^10 +7*x -13
sage: G = f.factor(); G
(x + x) * (x + 2*x + 1) * (x^4 + (x + 2)*x^3 + (2*x + 2)*x + 2) * (x^4 + 2*x*x^3 + (x + 1)*x + 2)
sage: prod(G) == f
True
sage: R.<x0> = GF(9,'x')[] # purposely calling it x to test robustness
sage: f = x0^3 + x0 + 1
sage: f.factor()
(x0 + 2) * (x0 + x) * (x0 + 2*x + 1)
sage: f = 0*x0
sage: f.factor()
Traceback (most recent call last):
...
ValueError: factorization of 0 not defined
sage: f = x0^0
sage: f.factor()
1
Over a complicated number field:
sage: x = polygen(QQ, 'x')
sage: f = x^6 + 10/7*x^5 - 867/49*x^4 - 76/245*x^3 + 3148/35*x^2 - 25944/245*x + 48771/1225
sage: K.<a> = NumberField(f)
sage: S.<T> = K[]
sage: ff = S(f); ff
T^6 + 10/7*T^5 - 867/49*T^4 - 76/245*T^3 + 3148/35*T^2 - 25944/245*T + 48771/1225
sage: F = ff.factor()
sage: len(F)
4
sage: F[:2]
[(T - a, 1), (T - 40085763200/924556084127*a^5 - 145475769880/924556084127*a^4 + 527617096480/924556084127*a^3 + 1289745809920/924556084127*a^2 - 3227142391585/924556084127*a - 401502691578/924556084127, 1)]
sage: expand(F)
T^6 + 10/7*T^5 - 867/49*T^4 - 76/245*T^3 + 3148/35*T^2 - 25944/245*T + 48771/1225
sage: f = x^2 - 1/3
sage: K.<a> = NumberField(f)
sage: A.<T> = K[]
sage: A(x^2 - 1).factor()
(T - 1) * (T + 1)
sage: A(3*x^2 - 1).factor()
(3) * (T - a) * (T + a)
sage: A(x^2 - 1/3).factor()
(T - a) * (T + a)
Test that ticket #10279 is fixed:
sage: R.<t> = PolynomialRing(QQ)
sage: K.<a> = NumberField(t^4 - t^2 + 1)
sage: pol = t^3 + (-4*a^3 + 2*a)*t^2 - 11/3*a^2*t + 2/3*a^3 - 4/3*a
sage: pol.factor()
(t - 2*a^3 + a) * (t - 4/3*a^3 + 2/3*a) * (t - 2/3*a^3 + 1/3*a)
Test that this factorization really uses nffactor() internally:
sage: pari.default("debug", 3)
sage: F = pol.factor()
Entering nffactor:
...
sage: pari.default("debug", 0)
Test that ticket #10369 is fixed:
sage: x = polygen(QQ)
sage: K.<a> = NumberField(x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)
sage: R.<t> = PolynomialRing(K)
sage: pol = (-1/7*a^5 - 1/7*a^4 - 1/7*a^3 - 1/7*a^2 - 2/7*a - 1/7)*t^10 + (4/7*a^5 - 2/7*a^4 - 2/7*a^3 - 2/7*a^2 - 2/7*a - 6/7)*t^9 + (90/49*a^5 + 152/49*a^4 + 18/49*a^3 + 24/49*a^2 + 30/49*a + 36/49)*t^8 + (-10/49*a^5 + 10/7*a^4 + 198/49*a^3 - 102/49*a^2 - 60/49*a - 26/49)*t^7 + (40/49*a^5 + 45/49*a^4 + 60/49*a^3 + 277/49*a^2 - 204/49*a - 78/49)*t^6 + (90/49*a^5 + 110/49*a^4 + 2*a^3 + 80/49*a^2 + 46/7*a - 30/7)*t^5 + (30/7*a^5 + 260/49*a^4 + 250/49*a^3 + 232/49*a^2 + 32/7*a + 8)*t^4 + (-184/49*a^5 - 58/49*a^4 - 52/49*a^3 - 66/49*a^2 - 72/49*a - 72/49)*t^3 + (18/49*a^5 - 32/49*a^4 + 10/49*a^3 + 4/49*a^2)*t^2 + (2/49*a^4 - 4/49*a^3 + 2/49*a^2)*t
sage: pol.factor()
(-1/7*a^5 - 1/7*a^4 - 1/7*a^3 - 1/7*a^2 - 2/7*a - 1/7) * t * (t - a^5 - a^4 - a^3 - a^2 - a - 1)^4 * (t^5 + (-12/7*a^5 - 10/7*a^4 - 8/7*a^3 - 6/7*a^2 - 4/7*a - 2/7)*t^4 + (12/7*a^5 - 8/7*a^3 + 16/7*a^2 + 2/7*a + 20/7)*t^3 + (-20/7*a^5 - 20/7*a^3 - 20/7*a^2 + 4/7*a - 2)*t^2 + (12/7*a^5 + 12/7*a^3 + 2/7*a + 16/7)*t - 4/7*a^5 - 4/7*a^3 - 4/7*a - 2/7)
sage: pol = (1/7*a^2 - 1/7*a)*t^10 + (4/7*a - 6/7)*t^9 + (102/49*a^5 + 99/49*a^4 + 96/49*a^3 + 93/49*a^2 + 90/49*a + 150/49)*t^8 + (-160/49*a^5 - 36/49*a^4 - 48/49*a^3 - 8/7*a^2 - 60/49*a - 60/49)*t^7 + (30/49*a^5 - 55/49*a^4 + 20/49*a^3 + 5/49*a^2)*t^6 + (6/49*a^4 - 12/49*a^3 + 6/49*a^2)*t^5
sage: pol.factor()
(1/7*a^2 - 1/7*a) * t^5 * (t^5 + (-40/7*a^5 - 38/7*a^4 - 36/7*a^3 - 34/7*a^2 - 32/7*a - 30/7)*t^4 + (60/7*a^5 - 30/7*a^4 - 18/7*a^3 - 9/7*a^2 - 3/7*a)*t^3 + (60/7*a^4 - 40/7*a^3 - 16/7*a^2 - 4/7*a)*t^2 + (30/7*a^3 - 25/7*a^2 - 5/7*a)*t + 6/7*a^2 - 6/7*a)
sage: pol = x^10 + (4/7*a - 6/7)*x^9 + (9/49*a^2 - 3/7*a + 15/49)*x^8 + (8/343*a^3 - 32/343*a^2 + 40/343*a - 20/343)*x^7 + (5/2401*a^4 - 20/2401*a^3 + 40/2401*a^2 - 5/343*a + 15/2401)*x^6 + (-6/16807*a^4 + 12/16807*a^3 - 18/16807*a^2 + 12/16807*a - 6/16807)*x^5
sage: pol.factor()
x^5 * (x^5 + (4/7*a - 6/7)*x^4 + (9/49*a^2 - 3/7*a + 15/49)*x^3 + (8/343*a^3 - 32/343*a^2 + 40/343*a - 20/343)*x^2 + (5/2401*a^4 - 20/2401*a^3 + 40/2401*a^2 - 5/343*a + 15/2401)*x - 6/16807*a^4 + 12/16807*a^3 - 18/16807*a^2 + 12/16807*a - 6/16807)
Factoring over a number field over which we cannot factor the discriminant by trial division:
sage: x = polygen(QQ)
sage: K.<a> = NumberField(x^16 - x - 6)
sage: R.<x> = PolynomialRing(K)
sage: f = (x+a)^50 - (a-1)^50
sage: len(factor(f))
6
sage: pari(K.discriminant()).factor(limit=0)
[-1, 1; 3, 15; 23, 1; 887, 1; 12583, 1; 2354691439917211, 1]
sage: factor(K.discriminant())
-1 * 3^15 * 23 * 887 * 12583 * 6335047 * 371692813
Factoring over a number field over which we cannot factor the
discriminant and over which fails:
sage: p = next_prime(10^50); q = next_prime(10^51); n = p*q;
sage: K.<a> = QuadraticField(p*q)
sage: R.<x> = PolynomialRing(K)
sage: K.pari_polynomial('a').nffactor("x^2+1")
Mat([x^2 + 1, 1])
sage: factor(x^2 + 1)
x^2 + 1
sage: factor( (x - a) * (x + 2*a) )
(x - a) * (x + 2*a)
A test where nffactor used to fail without a nf structure:
sage: x = polygen(QQ)
sage: K = NumberField([x^2-1099511627777, x^3-3],'a')
sage: x = polygen(K)
sage: f = x^3 - 3
sage: factor(f)
(x - a1) * (x^2 + a1*x + a1^2)
We check that trac ticket #7554 is fixed:
sage: L.<q> = LaurentPolynomialRing(QQ)
sage: F = L.fraction_field()
sage: R.<x> = PolynomialRing(F)
sage: factor(x)
x
sage: factor(x^2 - q^2)
(-1) * (-x + q) * (x + q)
sage: factor(x^2 - q^-2)
(1/q^2) * (q*x - 1) * (q*x + 1)
sage: P.<a,b,c> = PolynomialRing(ZZ)
sage: R.<x> = PolynomialRing(FractionField(P))
sage: p = (x - a)*(b*x + c)*(a*b*x + a*c) / (a + 2)
sage: factor(p)
(a/(a + 2)) * (x - a) * (b*x + c)^2
Compute a greatest common divisor of this polynomial and other.
INPUT:
- other – a polynomial in the same ring as this polynomial
OUTPUT:
A greatest common divisor as a polynomial in the same ring as this polynomial. Over a field, the return value will be a monic polynomial.
Note
The actual algorithm for computing greatest common divisors depends on the base ring underlying the polynomial ring. If the base ring defines a method _gcd_univariate_polynomial, then this method will be called (see examples below).
EXAMPLES:
sage: R.<x> = QQ[]
sage: (2*x^2).gcd(2*x)
x
sage: R.zero().gcd(0)
0
sage: (2*x).gcd(0)
x
One can easily add gcd functionality to new rings by providing a
method ``_gcd_univariate_polynomial``::
sage: R.<x> = QQ[]
sage: S.<y> = R[]
sage: h1 = y*x
sage: h2 = y^2*x^2
sage: h1.gcd(h2)
Traceback (most recent call last):
...
NotImplementedError: Univariate Polynomial Ring in x over Rational Field does not provide a gcd implementation for univariate polynomials
sage: T.<x,y> = QQ[]
sage: R._gcd_univariate_polynomial = lambda f,g: S(T(f).gcd(g))
sage: h1.gcd(h2)
x*y
sage: del R._gcd_univariate_polynomial
Returns the number of non-zero coefficients of self.
EXAMPLES:
sage: R.<x> = ZZ[]
sage: f = x^3 - x
sage: f.hamming_weight()
2
sage: R(0).hamming_weight()
0
sage: f = (x+1)^100
sage: f.hamming_weight()
101
sage: S = GF(5)['y']
sage: S(f).hamming_weight()
5
sage: cyclotomic_polynomial(105).hamming_weight()
33
Return the homogenization of this polynomial.
The polynomial itself is returned if it homogeneous already. Otherwise, its monomials are multiplied with the smallest powers of var such that they all have the same total degree.
INPUT:
OUTPUT:
If var specifies the variable in the polynomial ring, then a homogeneous element in that ring is returned. Otherwise, a homogeneous element is returned in a polynomial ring with an extra last variable var.
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x^2 + 1
sage: f.homogenize()
x^2 + h^2
The parameter var can be used to specify the name of the variable:
sage: g = f.homogenize('z'); g
x^2 + z^2
sage: g.parent()
Multivariate Polynomial Ring in x, z over Rational Field
However, if the polynomial is homogeneous already, then that parameter is ignored and no extra variable is added to the polynomial ring:
sage: f = x^2
sage: g = f.homogenize('z'); g
x^2
sage: g.parent()
Univariate Polynomial Ring in x over Rational Field
For compatibility with the multivariate case, if var specifies the variable of the polynomial ring, then the monomials are multiplied with the smallest powers of var such that the result is homogeneous; in other words, we end up with a monomial whose leading coefficient is the sum of the coefficients of the polynomial:
sage: f = x^2 + x + 1
sage: f.homogenize('x')
3*x^2
In positive characterstic, the degree can drop in this case:
sage: R.<x> = GF(2)[]
sage: f = x + 1
sage: f.homogenize(x)
0
For compatibility with the multivariate case, the parameter var can also be 0 to specify the variable in the polynomial ring:
sage: R.<x> = QQ[]
sage: f = x^2 + x + 1
sage: f.homogenize(0)
3*x^2
Return the integral of this polynomial.
By default, the integration variable is the variable of the polynomial.
Otherwise, the integration variable is the optional parameter var
Note
The integral is always chosen so the constant term is 0.
EXAMPLES:
sage: R.<x> = ZZ[]
sage: R(0).integral()
0
sage: f = R(2).integral(); f
2*x
Note that the integral lives over the fraction field of the scalar coefficients:
sage: f.parent()
Univariate Polynomial Ring in x over Rational Field
sage: R(0).integral().parent()
Univariate Polynomial Ring in x over Rational Field
sage: f = x^3 + x - 2
sage: g = f.integral(); g
1/4*x^4 + 1/2*x^2 - 2*x
sage: g.parent()
Univariate Polynomial Ring in x over Rational Field
This shows that the issue at trac ticket #7711 is resolved:
sage: P.<x,z> = PolynomialRing(GF(2147483647))
sage: Q.<y> = PolynomialRing(P)
sage: p=x+y+z
sage: p.integral()
-1073741823*y^2 + (x + z)*y
sage: P.<x,z> = PolynomialRing(GF(next_prime(2147483647)))
sage: Q.<y> = PolynomialRing(P)
sage: p=x+y+z
sage: p.integral()
1073741830*y^2 + (x + z)*y
A truly convoluted example:
sage: A.<a1, a2> = PolynomialRing(ZZ)
sage: B.<b> = PolynomialRing(A)
sage: C.<c> = PowerSeriesRing(B)
sage: R.<x> = PolynomialRing(C)
sage: f = a2*x^2 + c*x - a1*b
sage: f.parent()
Univariate Polynomial Ring in x over Power Series Ring in c
over Univariate Polynomial Ring in b over Multivariate Polynomial
Ring in a1, a2 over Integer Ring
sage: f.integral()
1/3*a2*x^3 + 1/2*c*x^2 - a1*b*x
sage: f.integral().parent()
Univariate Polynomial Ring in x over Power Series Ring in c
over Univariate Polynomial Ring in b over Multivariate Polynomial
Ring in a1, a2 over Rational Field
sage: g = 3*a2*x^2 + 2*c*x - a1*b
sage: g.integral()
a2*x^3 + c*x^2 - a1*b*x
sage: g.integral().parent()
Univariate Polynomial Ring in x over Power Series Ring in c
over Univariate Polynomial Ring in b over Multivariate Polynomial
Ring in a1, a2 over Rational Field
Integration with respect to a variable in the base ring:
sage: R.<x> = QQ[]
sage: t = PolynomialRing(R,'t').gen()
sage: f = x*t +5*t^2
sage: f.integral(x)
5*x*t^2 + 1/2*x^2*t
Inverts the polynomial a with respect to m, or raises a ValueError if no such inverse exists. The parameter m may be either a single polynomial or an ideal (for consistency with inverse_mod in other rings).
EXAMPLES:
sage: S.<t> = QQ[]
sage: f = inverse_mod(t^2 + 1, t^3 + 1); f
-1/2*t^2 - 1/2*t + 1/2
sage: f * (t^2 + 1) % (t^3 + 1)
1
sage: f = t.inverse_mod((t+1)^7); f
-t^6 - 7*t^5 - 21*t^4 - 35*t^3 - 35*t^2 - 21*t - 7
sage: (f * t) + (t+1)^7
1
sage: t.inverse_mod(S.ideal((t + 1)^7)) == f
True
This also works over inexact rings, but note that due to rounding error the product may not always exactly equal the constant polynomial 1 and have extra terms with coefficients close to zero.
sage: R.<x> = RDF[]
sage: epsilon = RDF(1).ulp()*50 # Allow an error of up to 50 ulp
sage: f = inverse_mod(x^2 + 1, x^5 + x + 1); f # abs tol 1e-14
0.4*x^4 - 0.2*x^3 - 0.4*x^2 + 0.2*x + 0.8
sage: poly = f * (x^2 + 1) % (x^5 + x + 1)
sage: # Remove noisy zero terms:
sage: parent(poly)([ 0.0 if abs(c)<=epsilon else c for c in poly.coefficients(sparse=False) ])
1.0
sage: f = inverse_mod(x^3 - x + 1, x - 2); f
0.14285714285714285
sage: f * (x^3 - x + 1) % (x - 2)
1.0
sage: g = 5*x^3+x-7; m = x^4-12*x+13; f = inverse_mod(g, m); f
-0.0319636125...*x^3 - 0.0383269759...*x^2 - 0.0463050900...*x + 0.346479687...
sage: poly = f*g % m
sage: # Remove noisy zero terms:
sage: parent(poly)([ 0.0 if abs(c)<=epsilon else c for c in poly.coefficients(sparse=False) ]) # abs tol 1e-14
1.0000000000000004
ALGORITHM: Solve the system as + mt = 1, returning s as the inverse of a mod m.
Uses the Euclidean algorithm for exact rings, and solves a linear system for the coefficients of s and t for inexact rings (as the Euclidean algorithm may not converge in that case).
AUTHORS:
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x - 90283
sage: f.inverse_of_unit()
Traceback (most recent call last):
...
ValueError: self is not a unit.
sage: f = R(-90283); g = f.inverse_of_unit(); g
-1/90283
sage: parent(g)
Univariate Polynomial Ring in x over Rational Field
Return True if this is a constant polynomial.
OUTPUT:
EXAMPLES:
sage: R.<x> = ZZ[]
sage: x.is_constant()
False
sage: R(2).is_constant()
True
sage: R(0).is_constant()
True
Return True if self is a cyclotomic polynomial.
A cyclotomic polynomial is a monic, irreducible polynomial such that all roots are roots of unity.
ALGORITHM:
The first cyclotomic polynomial x-1 is treated apart, otherwise the first algorithm of [BD89] is used.
EXAMPLES:
Quick tests:
sage: P.<x> = ZZ['x']
sage: (x - 1).is_cyclotomic()
True
sage: (x + 1).is_cyclotomic()
True
sage: (x^2 - 1).is_cyclotomic()
False
Test first 100 cyclotomic polynomials:
sage: all(cyclotomic_polynomial(i).is_cyclotomic() for i in xrange(1,101))
True
Some more tests:
sage: (x^16 + x^14 - x^10 + x^8 - x^6 + x^2 + 1).is_cyclotomic()
False
sage: (x^16 + x^14 - x^10 - x^8 - x^6 + x^2 + 1).is_cyclotomic()
True
sage: y = polygen(QQ)
sage: (y/2 - 1/2).is_cyclotomic()
False
sage: (2*(y/2 - 1/2)).is_cyclotomic()
True
Test using other rings:
sage: z = polygen(GF(5))
sage: (z - 1).is_cyclotomic()
Traceback (most recent call last):
...
NotImplementedError: not implemented in non-zero characteristic
REFERENCES:
[BD89] | R. J. Bradford and J. H. Davenport, Effective tests for cyclotomic polynomials, Symbolic and Algebraic Computation (1989) pp. 244 – 251, doi:10.1007/3-540-51084-2_22 |
Return True if this polynomial is the distinguished generator of the parent polynomial ring.
EXAMPLES:
sage: R.<x> = QQ[]
sage: R(1).is_gen()
False
sage: R(x).is_gen()
True
Important - this function doesn’t return True if self equals the generator; it returns True if self is the generator.
sage: f = R([0,1]); f
x
sage: f.is_gen()
False
sage: f is x
False
sage: f == x
True
Return True if this polynomial is homogeneous.
EXAMPLES:
sage: P.<x> = PolynomialRing(QQ)
sage: x.is_homogeneous()
True
sage: P(0).is_homogeneous()
True
sage: (x+1).is_homogeneous()
False
Return True precisely if this polynomial is irreducible over its base ring.
Testing irreducibility over for composite
is not
implemented.
EXAMPLES:
sage: R.<x> = ZZ[]
sage: (x^3 + 1).is_irreducible()
False
sage: (x^2 - 1).is_irreducible()
False
sage: (x^3 + 2).is_irreducible()
True
sage: R(0).is_irreducible()
False
See trac ticket #5140,
sage: R(1).is_irreducible()
False
sage: R(4).is_irreducible()
False
sage: R(5).is_irreducible()
True
The base ring does matter: for example, 2x is irreducible as a polynomial in QQ[x], but not in ZZ[x],
sage: R.<x> = ZZ[]
sage: R(2*x).is_irreducible()
False
sage: R.<x> = QQ[]
sage: R(2*x).is_irreducible()
True
TESTS:
sage: F.<t> = NumberField(x^2-5)
sage: Fx.<xF> = PolynomialRing(F)
sage: f = Fx([2*t - 5, 5*t - 10, 3*t - 6, -t, -t + 2, 1])
sage: f.is_irreducible()
False
sage: f = Fx([2*t - 3, 5*t - 10, 3*t - 6, -t, -t + 2, 1])
sage: f.is_irreducible()
True
Returns True if this polynomial is monic. The zero polynomial is by definition not monic.
EXAMPLES:
sage: x = QQ['x'].0
sage: f = x + 33
sage: f.is_monic()
True
sage: f = 0*x
sage: f.is_monic()
False
sage: f = 3*x^3 + x^4 + x^2
sage: f.is_monic()
True
sage: f = 2*x^2 + x^3 + 56*x^5
sage: f.is_monic()
False
AUTHORS:
Returns True if self is a monomial, i.e., a power of the generator.
EXAMPLES:
sage: R.<x> = QQ[]
sage: x.is_monomial()
True
sage: (x+1).is_monomial()
False
sage: (x^2).is_monomial()
True
sage: R(1).is_monomial()
True
The coefficient must be 1:
sage: (2*x^5).is_monomial()
False
To allow a non-1 leading coefficient, use is_term():
sage: (2*x^5).is_term()
True
Warning
The definition of is_monomial in Sage up to 4.7.1 was the same as is_term, i.e., it allowed a coefficient not equal to 1.
Return True if this polynomial is nilpotent.
EXAMPLES:
sage: R = Integers(12)
sage: S.<x> = R[]
sage: f = 5 + 6*x
sage: f.is_nilpotent()
False
sage: f = 6 + 6*x^2
sage: f.is_nilpotent()
True
sage: f^2
0
EXERCISE (Atiyah-McDonald, Ch 1): Let be a
polynomial ring in one variable. Then
is nilpotent if and only if
every
is nilpotent.
Returns True if the polynomial is primitive. The semantics of “primitive” depend on the polynomial coefficients.
Calling on a polynomial over an infinite field will
raise an error.
The additional inputs to this function are to speed up computation for field semantics (see note).
INPUTS:
- n (default: None) - if provided, should equal
where self.parent() is the field with
elements; otherwise it will be computed.
- n_prime_divs (default: None) - if provided, should be a list of the prime divisors of n; otherwise it will be computed.
Note
Computation of the prime divisors of n can dominate the running time of this method, so performing this computation externally (e.g. pdivs=n.prime_divisors()) is a good idea for repeated calls to is_primitive for polynomials of the same degree.
Results may be incorrect if the wrong n and/or factorization are provided.
EXAMPLES:
Field semantics examples.
::
sage: R.<x> = GF(2)['x']
sage: f = x^4+x^3+x^2+x+1
sage: f.is_irreducible(), f.is_primitive()
(True, False)
sage: f = x^3+x+1
sage: f.is_irreducible(), f.is_primitive()
(True, True)
sage: R.<x> = GF(3)[]
sage: f = x^3-x+1
sage: f.is_irreducible(), f.is_primitive()
(True, True)
sage: f = x^2+1
sage: f.is_irreducible(), f.is_primitive()
(True, False)
sage: R.<x> = GF(5)[]
sage: f = x^2+x+1
sage: f.is_primitive()
False
sage: f = x^2-x+2
sage: f.is_primitive()
True
sage: x=polygen(QQ); f=x^2+1
sage: f.is_primitive()
Traceback (most recent call last):
...
NotImplementedError: is_primitive() not defined for polynomials over infinite fields.
Ring semantics examples.
::
sage: x=polygen(ZZ)
sage: f = 5*x^2+2
sage: f.is_primitive()
True
sage: f = 5*x^2+5
sage: f.is_primitive()
False
sage: K=NumberField(x^2+5,'a')
sage: R=K.ring_of_integers()
sage: a=R.gen(1)
sage: a^2
-5
sage: f=a*x+2
sage: f.is_primitive()
True
sage: f=(1+a)*x+2
sage: f.is_primitive()
False
sage: x=polygen(Integers(10));
sage: f=5*x^2+2
sage: #f.is_primitive() #BUG:: elsewhere in Sage, should return True
sage: f=4*x^2+2
sage: #f.is_primitive() #BUG:: elsewhere in Sage, should return False
TESTS:
sage: R.<x> = GF(2)['x']
sage: f = x^4+x^3+x^2+x+1
sage: f.is_primitive(15)
False
sage: f.is_primitive(15, [3,5])
False
sage: f.is_primitive(n_prime_divs=[3,5])
False
sage: f = x^3+x+1
sage: f.is_primitive(7, [7])
True
sage: R.<x> = GF(3)[]
sage: f = x^3-x+1
sage: f.is_primitive(26, [2,13])
True
sage: f = x^2+1
sage: f.is_primitive(8, [2])
False
sage: R.<x> = GF(5)[]
sage: f = x^2+x+1
sage: f.is_primitive(24, [2,3])
False
sage: f = x^2-x+2
sage: f.is_primitive(24, [2,3])
True
sage: x=polygen(Integers(103)); f=x^2+1
sage: f.is_primitive()
False
Returns whether or not polynomial is square. If the optional argument root is True, then also returns the square root (or None, if the polynomial is not square).
INPUT:
OUTPUT:
EXAMPLES:
sage: R.<x> = PolynomialRing(QQ)
sage: f = 12*(x+1)^2 * (x+3)^2
sage: S.<y> = PolynomialRing(RR)
sage: g = 12*(y+1)^2 * (y+3)^2
sage: f.is_square()
False
sage: f.is_square(root=True)
(False, None)
sage: g.is_square()
True
sage: h = f/3; h
4*x^4 + 32*x^3 + 88*x^2 + 96*x + 36
sage: h.is_square(root=True)
(True, 2*x^2 + 8*x + 6)
TESTS:
Make sure ticket #9093 is fixed:
sage: R(1).is_square()
True
sage: R(4/9).is_square()
True
sage: R(-1/3).is_square()
False
sage: R(0).is_square()
True
Return False if this polynomial is not square-free, i.e., if there is a
non-unit in the polynomial ring such that
divides self.
Warning
This method is not consistent with squarefree_decomposition() since the latter does not factor the content of a polynomial. See the examples below.
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = (x-1)*(x-2)*(x^2-5)*(x^17-3); f
x^21 - 3*x^20 - 3*x^19 + 15*x^18 - 10*x^17 - 3*x^4 + 9*x^3 + 9*x^2 - 45*x + 30
sage: f.is_squarefree()
True
sage: (f*(x^2-5)).is_squarefree()
False
A generic implementation is available for polynomials defined over principal ideal domains of characteristic 0; the algorithm relies on gcd computations:
sage: R.<x> = ZZ[]
sage: (2*x).is_squarefree()
True
sage: (4*x).is_squarefree()
False
sage: (2*x^2).is_squarefree()
False
sage: R(0).is_squarefree()
False
sage: S.<y> = QQ[]
sage: R.<x> = S[]
sage: (2*x*y).is_squarefree() # R does not provide a gcd implementation
Traceback (most recent call last):
...
NotImplementedError: Univariate Polynomial Ring in y over Rational Field does not provide a gcd implementation for univariate polynomials
sage: (2*x*y^2).is_squarefree()
False
Over principal ideal domains of positive characteristic, we compute the square-free decomposition or a full factorization depending on which is available:
sage: K.<t> = FunctionField(GF(3))
sage: R.<x> = K[]
sage: (x^3-x).is_squarefree()
True
sage: (x^3-1).is_squarefree()
False
sage: (x^3+t).is_squarefree()
True
sage: (x^3+t^3).is_squarefree()
False
In the following example, is a unit in the base field:
sage: R(t^2).is_squarefree()
True
This method is not consistent with squarefree_decomposition():
sage: R.<x> = ZZ[]
sage: f = 4 * x
sage: f.is_squarefree()
False
sage: f.squarefree_decomposition()
(4) * x
If you want this method equally not to consider the content, you can remove it as in the following example:
sage: c = f.content()
sage: (f/c).is_squarefree()
True
Return True if self is an element of the base ring times a power of the generator.
EXAMPLES:
sage: R.<x> = QQ[]
sage: x.is_term()
True
sage: R(1).is_term()
True
sage: (3*x^5).is_term()
True
sage: (1+3*x^5).is_term()
False
To require that the coefficient is 1, use is_monomial() instead:
sage: (3*x^5).is_monomial()
False
Return True if this polynomial is a unit.
EXAMPLES:
sage: a = Integers(90384098234^3)
sage: b = a(2*191*236607587)
sage: b.is_nilpotent()
True
sage: R.<x> = a[]
sage: f = 3 + b*x + b^2*x^2
sage: f.is_unit()
True
sage: f = 3 + b*x + b^2*x^2 + 17*x^3
sage: f.is_unit()
False
EXERCISE (Atiyah-McDonald, Ch 1): Let be a
polynomial ring in one variable. Then
is a unit if and only if
is a unit and
are
nilpotent.
Let f and g be two polynomials. Then this function returns the monic least common multiple of f and g.
Return the leading coefficient of this polynomial.
OUTPUT: element of the base ring
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = (-2/5)*x^3 + 2*x - 1/3
sage: f.leading_coefficient()
-2/5
Return a new copy of the list of the underlying elements of self.
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = (-2/5)*x^3 + 2*x - 1/3
sage: v = f.list(); v
[-1/3, 2, 0, -2/5]
Note that v is a list, it is mutable, and each call to the list method returns a new list:
sage: type(v)
<type 'list'>
sage: v[0] = 5
sage: f.list()
[-1/3, 2, 0, -2/5]
Here is an example with a generic polynomial ring:
sage: R.<x> = QQ[]
sage: S.<y> = R[]
sage: f = y^3 + x*y -3*x; f
y^3 + x*y - 3*x
sage: type(f)
<type 'sage.rings.polynomial.polynomial_element.Polynomial_generic_dense'>
sage: v = f.list(); v
[-3*x, x, 0, 1]
sage: v[0] = 10
sage: f.list()
[-3*x, x, 0, 1]
Returns the polynomial obtained by applying f to the non-zero coefficients of self.
If f is a sage.categories.map.Map, then the resulting polynomial will be defined over the codomain of f. Otherwise, the resulting polynomial will be over the same ring as self. Set new_base_ring to override this behaviour.
INPUT:
EXAMPLES:
sage: R.<x> = SR[]
sage: f = (1+I)*x^2 + 3*x - I
sage: f.map_coefficients(lambda z: z.conjugate())
(-I + 1)*x^2 + 3*x + I
sage: R.<x> = ZZ[]
sage: f = x^2 + 2
sage: f.map_coefficients(lambda a: a + 42)
43*x^2 + 44
sage: R.<x> = PolynomialRing(SR, sparse=True)
sage: f = (1+I)*x^(2^32) - I
sage: f.map_coefficients(lambda z: z.conjugate())
(-I + 1)*x^4294967296 + I
sage: R.<x> = PolynomialRing(ZZ, sparse=True)
sage: f = x^(2^32) + 2
sage: f.map_coefficients(lambda a: a + 42)
43*x^4294967296 + 44
Examples with different base ring:
sage: R.<x> = ZZ[]
sage: k = GF(2)
sage: residue = lambda x: k(x)
sage: f = 4*x^2+x+3
sage: g = f.map_coefficients(residue); g
x + 1
sage: g.parent()
Univariate Polynomial Ring in x over Integer Ring
sage: g = f.map_coefficients(residue, new_base_ring = k); g
x + 1
sage: g.parent()
Univariate Polynomial Ring in x over Finite Field of size 2 (using NTL)
sage: residue = k.coerce_map_from(ZZ)
sage: g = f.map_coefficients(residue); g
x + 1
sage: g.parent()
Univariate Polynomial Ring in x over Finite Field of size 2 (using NTL)
Remainder of division of self by other.
EXAMPLES:
sage: R.<x> = ZZ[]
sage: x % (x+1)
-1
sage: (x^3 + x - 1) % (x^2 - 1)
2*x - 1
Return this polynomial divided by its leading coefficient. Does not change this polynomial.
EXAMPLES:
sage: x = QQ['x'].0
sage: f = 2*x^2 + x^3 + 56*x^5
sage: f.monic()
x^5 + 1/56*x^3 + 1/28*x^2
sage: f = (1/4)*x^2 + 3*x + 1
sage: f.monic()
x^2 + 12*x + 4
The following happens because cannot be made into a
monic polynomial
sage: f = 0*x
sage: f.monic()
Traceback (most recent call last):
...
ZeroDivisionError: rational division by zero
Notice that the monic version of a polynomial over the integers is defined over the rationals.
sage: x = ZZ['x'].0
sage: f = 3*x^19 + x^2 - 37
sage: g = f.monic(); g
x^19 + 1/3*x^2 - 37/3
sage: g.parent()
Univariate Polynomial Ring in x over Rational Field
AUTHORS:
Return a list of n iterative approximations to a root of this polynomial, computed using the Newton-Raphson method.
The Newton-Raphson method is an iterative root-finding algorithm. For f(x) a polynomial, as is the case here, this is essentially the same as Horner’s method.
INPUT:
OUTPUT: A list of numbers hopefully approximating a root of f(x)=0.
If one of the iterates is a critical point of f then a ZeroDivisionError exception is raised.
EXAMPLES:
sage: x = PolynomialRing(RealField(), 'x').gen()
sage: f = x^2 - 2
sage: f.newton_raphson(4, 1)
[1.50000000000000, 1.41666666666667, 1.41421568627451, 1.41421356237469]
AUTHORS:
Return the -adic slopes of the Newton polygon of self,
when this makes sense.
OUTPUT: list of rational numbers
EXAMPLES:
sage: x = QQ['x'].0
sage: f = x^3 + 2
sage: f.newton_slopes(2)
[1/3, 1/3, 1/3]
ALGORITHM: Uses PARI.
Return the -norm of this polynomial.
DEFINITION: For integer , the
-norm of a
polynomial is the
th root of the sum of the
th powers of the absolute values of the coefficients of
the polynomial.
INPUT:
EXAMPLES:
sage: R.<x> = RR[]
sage: f = x^6 + x^2 + -x^4 - 2*x^3
sage: f.norm(2)
2.64575131106459
sage: (sqrt(1^2 + 1^2 + (-1)^2 + (-2)^2)).n()
2.64575131106459
sage: f.norm(1)
5.00000000000000
sage: f.norm(infinity)
2.00000000000000
sage: f.norm(-1)
Traceback (most recent call last):
...
ValueError: The degree of the norm must be positive
TESTS:
sage: R.<x> = RR[]
sage: f = x^6 + x^2 + -x^4 -x^3
sage: f.norm(int(2))
2.00000000000000
AUTHORS:
Return a numerator of self computed as self * self.denominator()
Note that some subclases may implement its own numerator function. For example, see sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint
Warning
This is not the numerator of the rational function defined by self, which would always be self since self is a polynomial.
EXAMPLES:
First we compute the numerator of a polynomial with integer coefficients, which is of course self.
sage: R.<x> = ZZ[]
sage: f = x^3 + 17*x + 1
sage: f.numerator()
x^3 + 17*x + 1
sage: f == f.numerator()
True
Next we compute the numerator of a polynomial with rational coefficients.
sage: R.<x> = PolynomialRing(QQ)
sage: f = (1/17)*x^19 - (2/3)*x + 1/3; f
1/17*x^19 - 2/3*x + 1/3
sage: f.numerator()
3*x^19 - 34*x + 17
sage: f == f.numerator()
False
We try to compute the denominator of a polynomial with coefficients in the real numbers, which is a ring whose elements do not have a denominator method.
sage: R.<x> = RR[]
sage: f = x + RR('0.3'); f
x + 0.300000000000000
sage: f.numerator()
x + 0.300000000000000
We check that the computation the numerator and denominator are valid
sage: K=NumberField(symbolic_expression('x^3+2'),'a')['s,t']['x']
sage: f=K.random_element()
sage: f.numerator() / f.denominator() == f
True
sage: R=RR['x']
sage: f=R.random_element()
sage: f.numerator() / f.denominator() == f
True
This is the same as the valuation of self at p. See the documentation for self.valuation.
EXAMPLES:
sage: P,x=PolynomialRing(ZZ,'x').objgen()
sage: (x^2+x).ord(x+1)
1
Return list of coefficients of self up to (but not including)
.
Includes 0’s in the list on the right so that the list has length
.
INPUT:
EXAMPLES:
sage: x = polygen(QQ)
sage: f = 1 + x^3 + 23*x^5
sage: f.padded_list()
[1, 0, 0, 1, 0, 23]
sage: f.padded_list(10)
[1, 0, 0, 1, 0, 23, 0, 0, 0, 0]
sage: len(f.padded_list(10))
10
sage: f.padded_list(3)
[1, 0, 0]
sage: f.padded_list(0)
[]
sage: f.padded_list(-1)
Traceback (most recent call last):
...
ValueError: n must be at least 0
Return a plot of this polynomial.
INPUT:
OUTPUT: returns a graphic object.
EXAMPLES:
sage: x = polygen(GF(389))
sage: plot(x^2 + 1, rgbcolor=(0,0,1))
Graphics object consisting of 1 graphics primitive
sage: x = polygen(QQ)
sage: plot(x^2 + 1, rgbcolor=(1,0,0))
Graphics object consisting of 1 graphics primitive
Let var be one of the variables of the parent of self. This returns self viewed as a univariate polynomial in var over the polynomial ring generated by all the other variables of the parent.
For univariate polynomials, if var is the generator of the parent ring, we return this polynomial, otherwise raise an error.
EXAMPLES:
sage: R.<x> = QQ[]
sage: (x+1).polynomial(x)
x + 1
TESTS:
sage: x.polynomial(1)
Traceback (most recent call last):
...
ValueError: given variable is not the generator of parent.
Return the precision of this polynomial. This is always infinity, since polynomials are of infinite precision by definition (there is no big-oh).
EXAMPLES:
sage: x = polygen(ZZ)
sage: (x^5 + x + 1).prec()
+Infinity
sage: x.prec()
+Infinity
Returns the radical of self; over a field, this is the product of the distinct irreducible factors of self. (This is also sometimes called the “square-free part” of self, but that term is ambiguous; it is sometimes used to mean the quotient of self by its maximal square factor.)
EXAMPLES:
sage: P.<x> = ZZ[]
sage: t = (x^2-x+1)^3 * (3*x-1)^2
sage: t.radical()
3*x^3 - 4*x^2 + 4*x - 1
sage: radical(12 * x^5)
6*x
If self has a factor of multiplicity divisible by the characteristic (see trac ticket #8736):
sage: P.<x> = GF(2)[]
sage: (x^3 + x^2).radical()
x^2 + x
Return the real roots of this polynomial, without multiplicities.
Calls self.roots(ring=RR), unless this is a polynomial with floating-point real coefficients, in which case it calls self.roots().
EXAMPLES:
sage: x = polygen(ZZ)
sage: (x^2 - x - 1).real_roots()
[-0.618033988749895, 1.61803398874989]
TESTS:
sage: x = polygen(RealField(100))
sage: (x^2 - x - 1).real_roots()[0].parent()
Real Field with 100 bits of precision
sage: x = polygen(RDF)
sage: (x^2 - x - 1).real_roots()[0].parent()
Real Double Field
sage: x=polygen(ZZ,'x'); v=(x^2-x-1).real_roots()
sage: v[0].parent() is RR
True
Returns the resultant of self and other.
INPUT:
OUTPUT: an element of the base ring of the polynomial ring
Note
Implemented using PARI’s polresultant function.
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x^3 + x + 1; g = x^3 - x - 1
sage: r = f.resultant(g); r
-8
sage: r.parent() is QQ
True
We can also compute resultants over univariate and multivariate polynomial rings, provided that PARI’s variable ordering requirements are respected. Usually, your resultants will work if you always ask for them in the variable x:
sage: R.<a> = QQ[]
sage: S.<x> = R[]
sage: f = x^2 + a; g = x^3 + a
sage: r = f.resultant(g); r
a^3 + a^2
sage: r.parent() is R
True
sage: R.<a, b> = QQ[]
sage: S.<x> = R[]
sage: f = x^2 + a; g = x^3 + b
sage: r = f.resultant(g); r
a^3 + b^2
sage: r.parent() is R
True
Unfortunately Sage does not handle PARI’s variable ordering requirements gracefully, so the following has to be done through Singular:
sage: R.<x, y> = QQ[]
sage: S.<a> = R[]
sage: f = x^2 + a; g = y^3 + a
sage: h = f.resultant(g); h
y^3 - x^2
sage: h.parent() is R
True
Check that trac ticket #13672 is fixed:
sage: R.<t> = GF(2)[]
sage: S.<x> = R[]
sage: f = (t^2 + t)*x + t^2 + t
sage: g = (t + 1)*x + t^2
sage: f.resultant(g)
t^4 + t
Check that trac ticket #15061 is fixed:
sage: R.<T> = PowerSeriesRing(QQ)
sage: F = R([1,1],2)
sage: RP.<x> = PolynomialRing(R)
sage: P = x^2 - F
sage: P.resultant(P.derivative())
-4 - 4*T + O(T^2)
Check that trac ticket #16360 is fixed:
sage: K.<x> = FunctionField(QQ)
sage: R.<y> = K[]
sage: y.resultant(y+x)
x
sage: K.<a> = FunctionField(QQ)
sage: R.<b> = K[]
sage: L.<b> = K.extension(b^2-a)
sage: R.<x> = L[]
sage: f=x^2-a
sage: g=x-b
sage: f.resultant(g)
0
Return polynomial but with the coefficients reversed.
If an optional degree argument is given the coefficient list will be truncated or zero padded as necessary and the reverse polynomial will have the specified degree.
EXAMPLES:
sage: R.<x> = ZZ[]; S.<y> = R[]
sage: f = y^3 + x*y -3*x; f
y^3 + x*y - 3*x
sage: f.reverse()
-3*x*y^3 + x*y^2 + 1
sage: f.reverse(degree=2)
-3*x*y^2 + x*y
sage: f.reverse(degree=5)
-3*x*y^5 + x*y^4 + y^2
TESTS:
sage: f.reverse(degree=1.5r)
Traceback (most recent call last):
...
ValueError: degree argument must be a non-negative integer, got 1.5
Return the field generated by the roots of the irreducible polynomial self. The output is either a number field, relative number field, a quotient of a polynomial ring over a field, or the fraction field of the base ring.
EXAMPLES:
sage: R.<x> = QQ['x']
sage: f = x^3 + x + 17
sage: f.root_field('a')
Number Field in a with defining polynomial x^3 + x + 17
sage: R.<x> = QQ['x']
sage: f = x - 3
sage: f.root_field('b')
Rational Field
sage: R.<x> = ZZ['x']
sage: f = x^3 + x + 17
sage: f.root_field('b')
Number Field in b with defining polynomial x^3 + x + 17
sage: y = QQ['x'].0
sage: L.<a> = NumberField(y^3-2)
sage: R.<x> = L['x']
sage: f = x^3 + x + 17
sage: f.root_field('c')
Number Field in c with defining polynomial x^3 + x + 17 over its base field
sage: R.<x> = PolynomialRing(GF(9,'a'))
sage: f = x^3 + x^2 + 8
sage: K.<alpha> = f.root_field(); K
Univariate Quotient Polynomial Ring in alpha over Finite Field in a of size 3^2 with modulus x^3 + x^2 + 2
sage: alpha^2 + 1
alpha^2 + 1
sage: alpha^3 + alpha^2
1
sage: R.<x> = QQ[]
sage: f = x^2
sage: K.<alpha> = f.root_field()
Traceback (most recent call last):
...
ValueError: polynomial must be irreducible
TESTS:
sage: (PolynomialRing(Integers(31),name='x').0+5).root_field('a')
Ring of integers modulo 31
Return the roots of this polynomial (by default, in the base ring of this polynomial).
INPUT:
By default, this finds all the roots that lie in the base ring of the polynomial. However, the ring parameter can be used to specify a ring to look for roots in.
If the polynomial and the output ring are both exact (integers, rationals, finite fields, etc.), then the output should always be correct (or raise an exception, if that case is not yet handled).
If the output ring is approximate (floating-point real or complex numbers), then the answer will be estimated numerically, using floating-point arithmetic of at least the precision of the output ring. If the polynomial is ill-conditioned, meaning that a small change in the coefficients of the polynomial will lead to a relatively large change in the location of the roots, this may give poor results. Distinct roots may be returned as multiple roots, multiple roots may be returned as distinct roots, real roots may be lost entirely (because the numerical estimate thinks they are complex roots). Note that polynomials with multiple roots are always ill-conditioned; there’s a footnote at the end of the docstring about this.
If the output ring is a RealIntervalField or ComplexIntervalField of a given precision, then the answer will always be correct (or an exception will be raised, if a case is not implemented). Each root will be contained in one of the returned intervals, and the intervals will be disjoint. (The returned intervals may be of higher precision than the specified output ring.)
At the end of this docstring (after the examples) is a description of all the cases implemented in this function, and the algorithms used. That section also describes the possibilities for “algorithm=”, for the cases where multiple algorithms exist.
EXAMPLES:
sage: x = QQ['x'].0
sage: f = x^3 - 1
sage: f.roots()
[(1, 1)]
sage: f.roots(ring=CC) # note -- low order bits slightly different on ppc.
[(1.00000000000000, 1), (-0.500000000000000 - 0.86602540378443...*I, 1), (-0.500000000000000 + 0.86602540378443...*I, 1)]
sage: f = (x^3 - 1)^2
sage: f.roots()
[(1, 2)]
sage: f = -19*x + 884736
sage: f.roots()
[(884736/19, 1)]
sage: (f^20).roots()
[(884736/19, 20)]
sage: K.<z> = CyclotomicField(3)
sage: f = K.defining_polynomial()
sage: f.roots(ring=GF(7))
[(4, 1), (2, 1)]
sage: g = f.change_ring(GF(7))
sage: g.roots()
[(4, 1), (2, 1)]
sage: g.roots(multiplicities=False)
[4, 2]
A new ring. In the example below, we add the special method _roots_univariate_polynomial to the base ring, and observe that this method is called instead to find roots of polynomials over this ring. This facility can be used to easily extend root finding to work over new rings you introduce:
sage: R.<x> = QQ[]
sage: (x^2 + 1).roots()
[]
sage: g = lambda f, *args, **kwds: f.change_ring(CDF).roots()
sage: QQ._roots_univariate_polynomial = g
sage: (x^2 + 1).roots() # abs tol 1e-14
[(2.7755575615628914e-17 - 1.0*I, 1), (0.9999999999999997*I, 1)]
sage: del QQ._roots_univariate_polynomial
An example over RR, which illustrates that only the roots in RR are returned:
sage: x = RR['x'].0
sage: f = x^3 -2
sage: f.roots()
[(1.25992104989487, 1)]
sage: f.factor()
(x - 1.25992104989487) * (x^2 + 1.25992104989487*x + 1.58740105196820)
sage: x = RealField(100)['x'].0
sage: f = x^3 -2
sage: f.roots()
[(1.2599210498948731647672106073, 1)]
sage: x = CC['x'].0
sage: f = x^3 -2
sage: f.roots()
[(1.25992104989487, 1), (-0.62996052494743... - 1.09112363597172*I, 1), (-0.62996052494743... + 1.09112363597172*I, 1)]
sage: f.roots(algorithm='pari')
[(1.25992104989487, 1), (-0.629960524947437 - 1.09112363597172*I, 1), (-0.629960524947437 + 1.09112363597172*I, 1)]
Another example showing that only roots in the base ring are returned:
sage: x = polygen(ZZ)
sage: f = (2*x-3) * (x-1) * (x+1)
sage: f.roots()
[(1, 1), (-1, 1)]
sage: f.roots(ring=QQ)
[(3/2, 1), (1, 1), (-1, 1)]
An example involving large numbers:
sage: x = RR['x'].0
sage: f = x^2 - 1e100
sage: f.roots()
[(-1.00000000000000e50, 1), (1.00000000000000e50, 1)]
sage: f = x^10 - 2*(5*x-1)^2
sage: f.roots(multiplicities=False)
[-1.6772670339941..., 0.19995479628..., 0.20004530611..., 1.5763035161844...]
sage: x = CC['x'].0
sage: i = CC.0
sage: f = (x - 1)*(x - i)
sage: f.roots(multiplicities=False)
[1.00000000000000, 1.00000000000000*I]
sage: g=(x-1.33+1.33*i)*(x-2.66-2.66*i)
sage: g.roots(multiplicities=False)
[1.33000000000000 - 1.33000000000000*I, 2.66000000000000 + 2.66000000000000*I]
Describing roots using radical expressions:
sage: x = QQ['x'].0
sage: f = x^2 + 2
sage: f.roots(SR)
[(-I*sqrt(2), 1), (I*sqrt(2), 1)]
sage: f.roots(SR, multiplicities=False)
[-I*sqrt(2), I*sqrt(2)]
The roots of some polynomials can’t be described using radical expressions:
sage: (x^5 - x + 1).roots(SR)
[]
For some other polynomials, no roots can be found at the moment due to the way roots are computed. trac ticket #17516 addresses these defecits. Until that gets implemented, one such example is the following:
sage: f = x^6-300*x^5+30361*x^4-1061610*x^3+1141893*x^2-915320*x+101724
sage: f.roots()
[]
A purely symbolic roots example:
sage: X = var('X')
sage: f = expand((X-1)*(X-I)^3*(X^2 - sqrt(2))); f
X^6 - (3*I + 1)*X^5 - sqrt(2)*X^4 + (3*I - 3)*X^4 + (3*I + 1)*sqrt(2)*X^3 + (I + 3)*X^3 - (3*I - 3)*sqrt(2)*X^2 - I*X^2 - (I + 3)*sqrt(2)*X + I*sqrt(2)
sage: f.roots()
[(I, 3), (-2^(1/4), 1), (2^(1/4), 1), (1, 1)]
The same operation, performed over a polynomial ring with symbolic coefficients:
sage: X = SR['X'].0
sage: f = (X-1)*(X-I)^3*(X^2 - sqrt(2)); f
X^6 + (-3*I - 1)*X^5 + (-sqrt(2) + 3*I - 3)*X^4 + ((3*I + 1)*sqrt(2) + I + 3)*X^3 + (-(3*I - 3)*sqrt(2) - I)*X^2 + (-(I + 3)*sqrt(2))*X + I*sqrt(2)
sage: f.roots()
[(I, 3), (-2^(1/4), 1), (2^(1/4), 1), (1, 1)]
sage: f.roots(multiplicities=False)
[I, -2^(1/4), 2^(1/4), 1]
A couple of examples where the base ring doesn’t have a factorization algorithm (yet). Note that this is currently done via naive enumeration, so could be very slow:
sage: R = Integers(6)
sage: S.<x> = R['x']
sage: p = x^2-1
sage: p.roots()
Traceback (most recent call last):
...
NotImplementedError: root finding with multiplicities for this polynomial not implemented (try the multiplicities=False option)
sage: p.roots(multiplicities=False)
[1, 5]
sage: R = Integers(9)
sage: A = PolynomialRing(R, 'y')
sage: y = A.gen()
sage: f = 10*y^2 - y^3 - 9
sage: f.roots(multiplicities=False)
[0, 1, 3, 6]
An example over the complex double field (where root finding is fast, thanks to NumPy):
sage: R.<x> = CDF[]
sage: f = R.cyclotomic_polynomial(5); f
x^4 + x^3 + x^2 + x + 1.0
sage: f.roots(multiplicities=False) # abs tol 1e-9
[-0.8090169943749469 - 0.5877852522924724*I, -0.8090169943749473 + 0.5877852522924724*I, 0.30901699437494773 - 0.951056516295154*I, 0.30901699437494756 + 0.9510565162951525*I]
sage: [z^5 for z in f.roots(multiplicities=False)] # abs tol 1e-14
[0.9999999999999957 - 1.2864981197413038e-15*I, 0.9999999999999976 + 3.062854959141552e-15*I, 1.0000000000000024 + 1.1331077795295987e-15*I, 0.9999999999999953 - 2.0212861992297117e-15*I]
sage: f = CDF['x']([1,2,3,4]); f
4.0*x^3 + 3.0*x^2 + 2.0*x + 1.0
sage: r = f.roots(multiplicities=False)
sage: [f(a).abs() for a in r] # abs tol 1e-14
[2.574630599127759e-15, 1.457101633618084e-15, 1.1443916996305594e-15]
Another example over RDF:
sage: x = RDF['x'].0
sage: ((x^3 -1)).roots() # abs tol 4e-16
[(1.0000000000000002, 1)]
sage: ((x^3 -1)).roots(multiplicities=False) # abs tol 4e-16
[1.0000000000000002]
More examples involving the complex double field:
sage: x = CDF['x'].0
sage: i = CDF.0
sage: f = x^3 + 2*i; f
x^3 + 2.0*I
sage: f.roots() # abs tol 1e-14
[(-1.0911236359717227 - 0.6299605249474374*I, 1), (3.885780586188048e-16 + 1.2599210498948734*I, 1), (1.0911236359717211 - 0.6299605249474363*I, 1)]
sage: f.roots(multiplicities=False) # abs tol 1e-14
[-1.0911236359717227 - 0.6299605249474374*I, 3.885780586188048e-16 + 1.2599210498948734*I, 1.0911236359717211 - 0.6299605249474363*I]
sage: [abs(f(z)) for z in f.roots(multiplicities=False)] # abs tol 1e-14
[8.95090418262362e-16, 8.728374398092689e-16, 1.0235750533041806e-15]
sage: f = i*x^3 + 2; f
I*x^3 + 2.0
sage: f.roots() # abs tol 1e-14
[(-1.0911236359717227 + 0.6299605249474374*I, 1), (3.885780586188048e-16 - 1.2599210498948734*I, 1), (1.0911236359717211 + 0.6299605249474363*I, 1)]
sage: f(f.roots()[0][0]) # abs tol 1e-13
3.3306690738754696e-15 + 1.3704315460216776e-15*I
Examples using real root isolation:
sage: x = polygen(ZZ)
sage: f = x^2 - x - 1
sage: f.roots()
[]
sage: f.roots(ring=RIF)
[(-0.6180339887498948482045868343657?, 1), (1.6180339887498948482045868343657?, 1)]
sage: f.roots(ring=RIF, multiplicities=False)
[-0.6180339887498948482045868343657?, 1.6180339887498948482045868343657?]
sage: f.roots(ring=RealIntervalField(150))
[(-0.6180339887498948482045868343656381177203091798057628621354486227?, 1), (1.618033988749894848204586834365638117720309179805762862135448623?, 1)]
sage: f.roots(ring=AA)
[(-0.618033988749895?, 1), (1.618033988749895?, 1)]
sage: f = f^2 * (x - 1)
sage: f.roots(ring=RIF)
[(-0.6180339887498948482045868343657?, 2), (1.0000000000000000000000000000000?, 1), (1.6180339887498948482045868343657?, 2)]
sage: f.roots(ring=RIF, multiplicities=False)
[-0.6180339887498948482045868343657?, 1.0000000000000000000000000000000?, 1.6180339887498948482045868343657?]
Examples using complex root isolation:
sage: x = polygen(ZZ)
sage: p = x^5 - x - 1
sage: p.roots()
[]
sage: p.roots(ring=CIF)
[(1.167303978261419?, 1), (-0.764884433600585? - 0.352471546031727?*I, 1), (-0.764884433600585? + 0.352471546031727?*I, 1), (0.181232444469876? - 1.083954101317711?*I, 1), (0.181232444469876? + 1.083954101317711?*I, 1)]
sage: p.roots(ring=ComplexIntervalField(200))
[(1.167303978261418684256045899854842180720560371525489039140082?, 1), (-0.76488443360058472602982318770854173032899665194736756700778? - 0.35247154603172624931794709140258105439420648082424733283770?*I, 1), (-0.76488443360058472602982318770854173032899665194736756700778? + 0.35247154603172624931794709140258105439420648082424733283770?*I, 1), (0.18123244446987538390180023778112063996871646618462304743774? - 1.08395410131771066843034449298076657427364024315511565430114?*I, 1), (0.18123244446987538390180023778112063996871646618462304743774? + 1.08395410131771066843034449298076657427364024315511565430114?*I, 1)]
sage: rts = p.roots(ring=QQbar); rts
[(1.167303978261419?, 1), (-0.7648844336005847? - 0.3524715460317263?*I, 1), (-0.7648844336005847? + 0.3524715460317263?*I, 1), (0.1812324444698754? - 1.083954101317711?*I, 1), (0.1812324444698754? + 1.083954101317711?*I, 1)]
sage: p.roots(ring=AA)
[(1.167303978261419?, 1)]
sage: p = (x - rts[4][0])^2 * (3*x^2 + x + 1)
sage: p.roots(ring=QQbar)
[(-0.1666666666666667? - 0.552770798392567?*I, 1), (-0.1666666666666667? + 0.552770798392567?*I, 1), (0.1812324444698754? + 1.083954101317711?*I, 2)]
sage: p.roots(ring=CIF)
[(-0.1666666666666667? - 0.552770798392567?*I, 1), (-0.1666666666666667? + 0.552770798392567?*I, 1), (0.1812324444698754? + 1.083954101317711?*I, 2)]
Note that coefficients in a number field with defining polynomial
are considered to be Gaussian rationals (with the
generator mapping to +I), if you ask for complex roots.
sage: K.<im> = NumberField(x^2 + 1)
sage: y = polygen(K)
sage: p = y^4 - 2 - im
sage: p.roots(ring=CC)
[(-1.2146389322441... - 0.14142505258239...*I, 1), (-0.14142505258239... + 1.2146389322441...*I, 1), (0.14142505258239... - 1.2146389322441...*I, 1), (1.2146389322441... + 0.14142505258239...*I, 1)]
sage: p = p^2 * (y^2 - 2)
sage: p.roots(ring=CIF)
[(-1.414213562373095?, 1), (1.414213562373095?, 1), (-1.214638932244183? - 0.141425052582394?*I, 2), (-0.141425052582394? + 1.214638932244183?*I, 2), (0.141425052582394? - 1.214638932244183?*I, 2), (1.214638932244183? + 0.141425052582394?*I, 2)]
Note that one should not use NumPy when wanting high precision output as it does not support any of the high precision types:
sage: R.<x> = RealField(200)[]
sage: f = x^2 - R(pi)
sage: f.roots()
[(-1.7724538509055160272981674833411451827975494561223871282138, 1), (1.7724538509055160272981674833411451827975494561223871282138, 1)]
sage: f.roots(algorithm='numpy')
doctest... UserWarning: NumPy does not support arbitrary precision arithmetic. The roots found will likely have less precision than you expect.
[(-1.77245385090551..., 1), (1.77245385090551..., 1)]
We can also find roots over number fields:
sage: K.<z> = CyclotomicField(15)
sage: R.<x> = PolynomialRing(K)
sage: (x^2 + x + 1).roots()
[(z^5, 1), (-z^5 - 1, 1)]
There are many combinations of floating-point input and output types that work. (Note that some of them are quite pointless like using algorithm='numpy' with high-precision types.)
sage: rflds = (RR, RDF, RealField(100))
sage: cflds = (CC, CDF, ComplexField(100))
sage: def cross(a, b):
....: return list(cartesian_product_iterator([a, b]))
sage: flds = cross(rflds, rflds) + cross(rflds, cflds) + cross(cflds, cflds)
sage: for (fld_in, fld_out) in flds:
....: x = polygen(fld_in)
....: f = x^3 - fld_in(2)
....: x2 = polygen(fld_out)
....: f2 = x2^3 - fld_out(2)
....: for algo in (None, 'pari', 'numpy'):
....: rts = f.roots(ring=fld_out, multiplicities=False)
....: if fld_in == fld_out and algo is None:
....: print fld_in, rts
....: for rt in rts:
....: assert(abs(f2(rt)) <= 1e-10)
....: assert(rt.parent() == fld_out)
Real Field with 53 bits of precision [1.25992104989487]
Real Double Field [1.25992104989...]
Real Field with 100 bits of precision [1.2599210498948731647672106073]
Complex Field with 53 bits of precision [1.25992104989487, -0.62996052494743... - 1.09112363597172*I, -0.62996052494743... + 1.09112363597172*I]
Complex Double Field [1.25992104989..., -0.629960524947... - 1.0911236359717...*I, -0.629960524947... + 1.0911236359717...*I]
Complex Field with 100 bits of precision [1.2599210498948731647672106073, -0.62996052494743658238360530364 - 1.0911236359717214035600726142*I, -0.62996052494743658238360530364 + 1.0911236359717214035600726142*I]
Note that we can find the roots of a polynomial with algebraic coefficients:
sage: rt2 = sqrt(AA(2))
sage: rt3 = sqrt(AA(3))
sage: x = polygen(AA)
sage: f = (x - rt2) * (x - rt3); f
x^2 - 3.146264369941973?*x + 2.449489742783178?
sage: rts = f.roots(); rts
[(1.414213562373095?, 1), (1.732050807568878?, 1)]
sage: rts[0][0] == rt2
True
sage: f.roots(ring=RealIntervalField(150))
[(1.414213562373095048801688724209698078569671875376948073176679738?, 1), (1.732050807568877293527446341505872366942805253810380628055806980?, 1)]
We can handle polynomials with huge coefficients.
This number doesn’t even fit in an IEEE double-precision float, but RR and CC allow a much larger range of floating-point numbers:
sage: bigc = 2^1500
sage: CDF(bigc)
+infinity
sage: CC(bigc)
3.50746621104340e451
Polynomials using such large coefficients can’t be handled by numpy, but pari can deal with them:
sage: x = polygen(QQ)
sage: p = x + bigc
sage: p.roots(ring=RR, algorithm='numpy')
Traceback (most recent call last):
...
LinAlgError: Array must not contain infs or NaNs
sage: p.roots(ring=RR, algorithm='pari')
[(-3.50746621104340e451, 1)]
sage: p.roots(ring=AA)
[(-3.5074662110434039?e451, 1)]
sage: p.roots(ring=QQbar)
[(-3.5074662110434039?e451, 1)]
sage: p = bigc*x + 1
sage: p.roots(ring=RR)
[(0.000000000000000, 1)]
sage: p.roots(ring=AA)
[(-2.8510609648967059?e-452, 1)]
sage: p.roots(ring=QQbar)
[(-2.8510609648967059?e-452, 1)]
sage: p = x^2 - bigc
sage: p.roots(ring=RR)
[(-5.92238652153286e225, 1), (5.92238652153286e225, 1)]
sage: p.roots(ring=QQbar)
[(-5.9223865215328558?e225, 1), (5.9223865215328558?e225, 1)]
Algorithms used:
For brevity, we will use RR to mean any RealField of any precision;
similarly for RIF, CC, and CIF. Since Sage has no specific
implementation of Gaussian rationals (or of number fields with
embedding, at all), when we refer to Gaussian rationals below we
will accept any number field with defining polynomial
, mapping the field generator to +I.
We call the base ring of the polynomial K, and the ring given by the ring= argument L. (If ring= is not specified, then L is the same as K.)
If K and L are floating-point (RDF, CDF, RR, or CC), then a floating-point root-finder is used. If L is RDF or CDF then we default to using NumPy’s roots(); otherwise, we use PARI’s polroots(). This choice can be overridden with algorithm=’pari’ or algorithm=’numpy’. If the algorithm is unspecified and NumPy’s roots() algorithm fails, then we fall back to pari (numpy will fail if some coefficient is infinite, for instance).
If L is SR, then the roots will be radical expressions, computed as the solutions of a symbolic polynomial expression. At the moment this delegates to sage.symbolic.expression.Expression.solve() which in turn uses Maxima to find radical solutions. Some solutions may be lost in this approach. Once trac ticket #17516 gets implemented, all possible radical solutions should become available.
If L is AA or RIF, and K is ZZ, QQ, or AA, then the root isolation algorithm sage.rings.polynomial.real_roots.real_roots() is used. (You can call real_roots() directly to get more control than this method gives.)
If L is QQbar or CIF, and K is ZZ, QQ, AA, QQbar, or the Gaussian rationals, then the root isolation algorithm sage.rings.polynomial.complex_roots.complex_roots() is used. (You can call complex_roots() directly to get more control than this method gives.)
If L is AA and K is QQbar or the Gaussian rationals, then complex_roots() is used (as above) to find roots in QQbar, then these roots are filtered to select only the real roots.
If L is floating-point and K is not, then we attempt to change the polynomial ring to L (using .change_ring()) (or, if L is complex and K is not, to the corresponding real field). Then we use either PARI or numpy as specified above.
For all other cases where K is different than L, we just use .change_ring(L) and proceed as below.
The next method, which is used if K is an integral domain, is to attempt to factor the polynomial. If this succeeds, then for every degree-one factor a*x+b, we add -b/a as a root (as long as this quotient is actually in the desired ring).
If factoring over K is not implemented (or K is not an integral domain), and K is finite, then we find the roots by enumerating all elements of K and checking whether the polynomial evaluates to zero at that value.
Note
We mentioned above that polynomials with multiple roots are always ill-conditioned; if your input is given to n bits of precision, you should not expect more than n/k good bits for a k-fold root. (You can get solutions that make the polynomial evaluate to a number very close to zero; basically the problem is that with a multiple root, there are many such numbers, and it’s difficult to choose between them.)
To see why this is true, consider the naive floating-point
error analysis model where you just pretend that all
floating-point numbers are somewhat imprecise - a little
‘fuzzy’, if you will. Then the graph of a floating-point
polynomial will be a fuzzy line. Consider the graph of
; this will be a fuzzy line with a
horizontal tangent at
,
. If the
fuzziness extends up and down by about j, then it will
extend left and right by about cube_root(j).
TESTS:
sage: K.<zeta> = CyclotomicField(2)
sage: R.<x> = K[]
sage: factor(x^3-1)
(x - 1) * (x^2 + x + 1)
This shows that the issue from trac ticket #6237 is fixed:
sage: R.<u> = QQ[]
sage: g = -27*u^14 - 32*u^9
sage: g.roots(CDF, multiplicities=False) # abs tol 2e-15
[-1.0345637159435719, 0.0, -0.3196977699902601 - 0.9839285635706636*I, -0.3196977699902601 + 0.9839285635706636*I, 0.8369796279620465 - 0.6081012947885318*I, 0.8369796279620465 + 0.6081012947885318*I]
sage: g.roots(CDF) # abs tol 2e-15
[(-1.0345637159435719, 1), (0.0, 9), (-0.3196977699902601 - 0.9839285635706636*I, 1), (-0.3196977699902601 + 0.9839285635706636*I, 1), (0.8369796279620465 - 0.6081012947885318*I, 1), (0.8369796279620465 + 0.6081012947885318*I, 1)]
This shows that the issue at trac ticket #2418 is fixed:
sage: x = polygen(QQ)
sage: p = (x^50/2^100 + x^10 + x + 1).change_ring(ComplexField(106))
sage: rts = (p/2^100).roots(multiplicities=False)
sage: eps = 2^(-50) # we test the roots numerically
sage: [abs(p(rt)) < eps for rt in rts] == [True]*50
True
This shows that the issue at trac ticket #10901 is fixed:
sage: a = var('a'); R.<x> = SR[]
sage: f = x - a
sage: f.roots(RR)
Traceback (most recent call last):
...
TypeError: Cannot evaluate symbolic expression to a numeric value.
sage: f.roots(CC)
Traceback (most recent call last):
...
TypeError: Cannot evaluate symbolic expression to a numeric value.
We can find roots of polynomials defined over or
over the
-adics, see trac ticket #15422:
sage: R.<x> = ZZ[]
sage: pol = (x - 1)^2
sage: pol.roots(Qp(3,5))
[(1 + O(3^5), 2)]
This doesn’t work if we first change coefficients to :
sage: pol.change_ring(Qp(3,5)).roots()
Traceback (most recent call last):
...
PrecisionError: p-adic factorization not well-defined since the discriminant is zero up to the requestion p-adic precision
sage: (pol - 3^6).roots(Qp(3,5))
[(1 + 2*3^3 + 2*3^4 + O(3^5), 1), (1 + 3^3 + O(3^5), 1)]
sage: r = pol.roots(Zp(3,5), multiplicities=False); r
[1 + O(3^5)]
sage: parent(r[0])
3-adic Ring with capped relative precision 5
Spurious crash with pari-2.5.5, see trac ticket #16165:
sage: f=(1+x+x^2)^3
sage: f.roots(ring=CC)
[(-0.500000000000000 - 0.866025403784439*I, 3),
(-0.500000000000000 + 0.866025403784439*I, 3)]
Returns this polynomial multiplied by the power . If
is negative, terms below
will be
discarded. Does not change this polynomial (since polynomials are
immutable).
EXAMPLES:
sage: R.<x> = QQ[]
sage: p = x^2 + 2*x + 4
sage: p.shift(0)
x^2 + 2*x + 4
sage: p.shift(-1)
x + 2
sage: p.shift(-5)
0
sage: p.shift(2)
x^4 + 2*x^3 + 4*x^2
One can also use the infix shift operator:
sage: f = x^3 + x
sage: f >> 2
x
sage: f << 2
x^5 + x^3
TESTS:
sage: p = R(0)
sage: p.shift(3).is_zero()
True
sage: p.shift(-3).is_zero()
True
AUTHORS:
Compute the absolute splitting field of a given polynomial.
INPUT:
OUTPUT:
If map is False, the splitting field as an absolute field. If map is True, a tuple (K, phi) where phi is an embedding of the base field of self in K.
EXAMPLES:
sage: R.<x> = PolynomialRing(ZZ)
sage: K.<a> = (x^3 + 2).splitting_field(); K
Number Field in a with defining polynomial x^6 + 3*x^5 + 6*x^4 + 11*x^3 + 12*x^2 - 3*x + 1
sage: K.<a> = (x^3 - 3*x + 1).splitting_field(); K
Number Field in a with defining polynomial x^3 - 3*x + 1
Relative situation:
sage: R.<x> = PolynomialRing(QQ)
sage: K.<a> = NumberField(x^3 + 2)
sage: S.<t> = PolynomialRing(K)
sage: L.<b> = (t^2 - a).splitting_field()
sage: L
Number Field in b with defining polynomial t^6 + 2
With map=True, we also get the embedding of the base field into the splitting field:
sage: L.<b>, phi = (t^2 - a).splitting_field(map=True)
sage: phi
Ring morphism:
From: Number Field in a with defining polynomial x^3 + 2
To: Number Field in b with defining polynomial t^6 + 2
Defn: a |--> b^2
An example over a finite field:
sage: P.<x> = PolynomialRing(GF(7))
sage: t = x^2 + 1
sage: t.splitting_field('b')
Finite Field in b of size 7^2
sage: P.<x> = PolynomialRing(GF(7^3, 'a'))
sage: t = x^2 + 1
sage: t.splitting_field('b', map=True)
(Finite Field in b of size 7^6,
Ring morphism:
From: Finite Field in a of size 7^3
To: Finite Field in b of size 7^6
Defn: a |--> 2*b^4 + 6*b^3 + 2*b^2 + 3*b + 2)
If the extension is trivial and the generators have the same name, the map will be the identity:
sage: t = 24*x^13 + 2*x^12 + 14
sage: t.splitting_field('a', map=True)
(Finite Field in a of size 7^3,
Identity endomorphism of Finite Field in a of size 7^3)
sage: t = x^56 - 14*x^3
sage: t.splitting_field('b', map=True)
(Finite Field in b of size 7^3,
Ring morphism:
From: Finite Field in a of size 7^3
To: Finite Field in b of size 7^3
Defn: a |--> b)
See also
sage.rings.number_field.splitting_field.splitting_field() for more examples over number fields
TESTS:
sage: K.<a,b> = x.splitting_field()
Traceback (most recent call last):
...
IndexError: the number of names must equal the number of generators
sage: polygen(RR).splitting_field('x')
Traceback (most recent call last):
...
NotImplementedError: splitting_field() is only implemented over number fields and finite fields
sage: P.<x> = PolynomialRing(GF(11^5, 'a'))
sage: t = x^2 + 1
sage: t.splitting_field('b')
Finite Field in b of size 11^10
sage: t = 24*x^13 + 2*x^12 + 14
sage: t.splitting_field('b')
Finite Field in b of size 11^30
sage: t = x^56 - 14*x^3
sage: t.splitting_field('b')
Finite Field in b of size 11^130
sage: P.<x> = PolynomialRing(GF(19^6, 'a'))
sage: t = -x^6 + x^2 + 1
sage: t.splitting_field('b')
Finite Field in b of size 19^6
sage: t = 24*x^13 + 2*x^12 + 14
sage: t.splitting_field('b')
Finite Field in b of size 19^18
sage: t = x^56 - 14*x^3
sage: t.splitting_field('b')
Finite Field in b of size 19^156
sage: P.<x> = PolynomialRing(GF(83^6, 'a'))
sage: t = 2*x^14 - 5 + 6*x
sage: t.splitting_field('b')
Finite Field in b of size 83^84
sage: t = 24*x^13 + 2*x^12 + 14
sage: t.splitting_field('b')
Finite Field in b of size 83^78
sage: t = x^56 - 14*x^3
sage: t.splitting_field('b')
Finite Field in b of size 83^12
sage: P.<x> = PolynomialRing(GF(401^13, 'a'))
sage: t = 2*x^14 - 5 + 6*x
sage: t.splitting_field('b')
Finite Field in b of size 401^104
sage: t = 24*x^13 + 2*x^12 + 14
sage: t.splitting_field('b')
Finite Field in b of size 401^156
sage: t = x^56 - 14*x^3
sage: t.splitting_field('b')
Finite Field in b of size 401^52
Returns the square of this polynomial.
TODO:
AUTHORS:
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x^3 + 1
sage: f.square()
x^6 + 2*x^3 + 1
sage: f*f
x^6 + 2*x^3 + 1
Return the square-free decomposition of this polynomial. This is a partial factorization into square-free, coprime polynomials.
EXAMPLES:
sage: x = polygen(QQ)
sage: p = 37 * (x-1)^3 * (x-2)^3 * (x-1/3)^7 * (x-3/7)
sage: p.squarefree_decomposition()
(37*x - 111/7) * (x^2 - 3*x + 2)^3 * (x - 1/3)^7
sage: p = 37 * (x-2/3)^2
sage: p.squarefree_decomposition()
(37) * (x - 2/3)^2
sage: x = polygen(GF(3))
sage: x.squarefree_decomposition()
x
sage: f = QQbar['x'](1)
sage: f.squarefree_decomposition()
1
Identical to self(*x).
See the docstring for self.__call__.
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x^3 + x - 3
sage: f.subs(x=5)
127
sage: f.subs(5)
127
sage: f.subs({x:2})
7
sage: f.subs({})
x^3 + x - 3
sage: f.subs({'x':2})
Traceback (most recent call last):
...
TypeError: keys do not match self's parent
Identical to self(*x).
See the docstring for self.__call__.
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x^3 + x - 3
sage: f.subs(x=5)
127
sage: f.subs(5)
127
sage: f.subs({x:2})
7
sage: f.subs({})
x^3 + x - 3
sage: f.subs({'x':2})
Traceback (most recent call last):
...
TypeError: keys do not match self's parent
Returns the Sylvester matrix of self and right.
Note that the Sylvester matrix is not defined if one of the polynomials is zero.
INPUT:
EXAMPLES:
sage: R.<x> = PolynomialRing(ZZ)
sage: f = (6*x + 47)*(7*x^2 - 2*x + 38)
sage: g = (6*x + 47)*(3*x^3 + 2*x + 1)
sage: M = f.sylvester_matrix(g)
sage: M
[ 42 317 134 1786 0 0 0]
[ 0 42 317 134 1786 0 0]
[ 0 0 42 317 134 1786 0]
[ 0 0 0 42 317 134 1786]
[ 18 141 12 100 47 0 0]
[ 0 18 141 12 100 47 0]
[ 0 0 18 141 12 100 47]
If the polynomials share a non-constant common factor then the determinant of the Sylvester matrix will be zero:
sage: M.determinant()
0
If self and right are polynomials of positive degree, the determinant of the Sylvester matrix is the resultant of the polynomials.:
sage: h1 = R.random_element()
sage: h2 = R.random_element()
sage: M1 = h1.sylvester_matrix(h2)
sage: M1.determinant() == h1.resultant(h2)
True
The rank of the Sylvester matrix is related to the degree of the gcd of self and right:
sage: f.gcd(g).degree() == f.degree() + g.degree() - M.rank()
True
sage: h1.gcd(h2).degree() == h1.degree() + h2.degree() - M1.rank()
True
TESTS:
The variable is optional, but must be the same in both rings:
sage: K.<x> = QQ['x']
sage: f = x+1
sage: g = QQ['y']([1, 0, 1])
sage: f.sylvester_matrix(f, x)
[1 1]
[1 1]
sage: f.sylvester_matrix(g, x)
Traceback (most recent call last):
...
TypeError: no common canonical parent for objects with parents: 'Univariate Polynomial Ring in x over Rational Field' and 'Univariate Polynomial Ring in y over Rational Field'
Polynomials must be defined over compatible base rings:
sage: f = QQ['x']([1, 0, 1])
sage: g = ZZ['x']([1, 0, 1])
sage: h = GF(25, 'a')['x']([1, 0, 1])
sage: f.sylvester_matrix(g)
[1 0 1 0]
[0 1 0 1]
[1 0 1 0]
[0 1 0 1]
sage: g.sylvester_matrix(h)
[1 0 1 0]
[0 1 0 1]
[1 0 1 0]
[0 1 0 1]
sage: f.sylvester_matrix(h)
Traceback (most recent call last):
...
TypeError: no common canonical parent for objects with parents: 'Univariate Polynomial Ring in x over Rational Field' and 'Univariate Polynomial Ring in x over Finite Field in a of size 5^2'
We can compute the sylvester matrix of a univariate and multivariate polynomial:
sage: K.<x,y> = QQ['x,y']
sage: g = K.random_element()
sage: f.sylvester_matrix(g) == K(f).sylvester_matrix(g,x)
True
Corner cases:
sage: K.<x>=QQ[]
sage: f = x^2+1
sage: g = K(0)
sage: f.sylvester_matrix(g)
Traceback (most recent call last):
...
ValueError: The Sylvester matrix is not defined for zero polynomials
sage: g.sylvester_matrix(f)
Traceback (most recent call last):
...
ValueError: The Sylvester matrix is not defined for zero polynomials
sage: g.sylvester_matrix(g)
Traceback (most recent call last):
...
ValueError: The Sylvester matrix is not defined for zero polynomials
sage: K(3).sylvester_matrix(x^2)
[3 0]
[0 3]
sage: K(3).sylvester_matrix(K(4))
[]
Returns the polynomial of degree ` < n` which is equivalent
to self modulo .
EXAMPLES:
sage: R.<x> = ZZ[]; S.<y> = PolynomialRing(R, sparse=True)
sage: f = y^3 + x*y -3*x; f
y^3 + x*y - 3*x
sage: f.truncate(2)
x*y - 3*x
sage: f.truncate(1)
-3*x
sage: f.truncate(0)
0
If , with
nonzero, then the valuation of
is
. The valuation of the zero polynomial is
.
If a prime (or non-prime) is given, then the valuation
is the largest power of
which divides self.
The valuation at is -self.degree().
EXAMPLES:
sage: P,x=PolynomialRing(ZZ,'x').objgen()
sage: (x^2+x).valuation()
1
sage: (x^2+x).valuation(x+1)
1
sage: (x^2+1).valuation()
0
sage: (x^3+1).valuation(infinity)
-3
sage: P(0).valuation()
+Infinity
Return name of variable used in this polynomial as a string.
OUTPUT: string
EXAMPLES:
sage: R.<t> = QQ[]
sage: f = t^3 + 3/2*t + 5
sage: f.variable_name()
't'
Returns the tuple of variables occurring in this polynomial.
EXAMPLES:
sage: R.<x> = QQ[]
sage: x.variables()
(x,)
A constant polynomial has no variables.
sage: R(2).variables()
()
Bases: sage.categories.morphism.Morphism
This class is used for conversion from a ring to a polynomial over that ring.
It calls the _new_constant_poly method on the generator, which should be optimized for a particular polynomial type.
Technically, it should be a method of the polynomial ring, but few polynomial rings are cython classes, and so, as a method of a cython polynomial class, it is faster.
EXAMPLES:
We demonstrate that most polynomial ring classes use polynomial base injection maps for coercion. They are supposed to be the fastest maps for that purpose. See trac ticket #9944.
sage: R.<x> = Qp(3)[]
sage: R.coerce_map_from(R.base_ring())
Polynomial base injection morphism:
From: 3-adic Field with capped relative precision 20
To: Univariate Polynomial Ring in x over 3-adic Field with capped relative precision 20
sage: R.<x,y> = Qp(3)[]
sage: R.coerce_map_from(R.base_ring())
Polynomial base injection morphism:
From: 3-adic Field with capped relative precision 20
To: Multivariate Polynomial Ring in x, y over 3-adic Field with capped relative precision 20
sage: R.<x,y> = QQ[]
sage: R.coerce_map_from(R.base_ring())
Polynomial base injection morphism:
From: Rational Field
To: Multivariate Polynomial Ring in x, y over Rational Field
sage: R.<x> = QQ[]
sage: R.coerce_map_from(R.base_ring())
Polynomial base injection morphism:
From: Rational Field
To: Univariate Polynomial Ring in x over Rational Field
By trac ticket #9944, there are now only very few exceptions:
sage: PolynomialRing(QQ,names=[]).coerce_map_from(QQ)
Generic morphism:
From: Rational Field
To: Multivariate Polynomial Ring in no variables over Rational Field
TESTS:
sage: from sage.rings.polynomial.polynomial_element import PolynomialBaseringInjection
sage: m = PolynomialBaseringInjection(RDF, RDF['x'])
sage: m.section()
Generic map:
From: Univariate Polynomial Ring in x over Real Double Field
To: Real Double Field
sage: type(m.section())
<type 'sage.rings.polynomial.polynomial_element.ConstantPolynomialSection'>
Bases: sage.rings.polynomial.polynomial_element.Polynomial
A generic dense polynomial.
EXAMPLES:
sage: R.<x> = PolynomialRing(PolynomialRing(QQ,'y'))
sage: f = x^3 - x + 17
sage: type(f)
<type 'sage.rings.polynomial.polynomial_element.Polynomial_generic_dense'>
sage: loads(f.dumps()) == f
True
Return the constant coefficient of this polynomial.
EXAMPLES:
sage: R.<x> = RDF[]
sage: f = (1+2*x^7)^5
sage: f.degree()
35
TESTS:
Check that trac ticket #12552 is fixed:
sage: type(f.degree())
<type 'sage.rings.integer.Integer'>
Return a new copy of the list of the underlying elements of self.
EXAMPLES:
sage: R.<x> = GF(17)[]
sage: f = (1+2*x)^3 + 3*x; f
8*x^3 + 12*x^2 + 9*x + 1
sage: f.list()
[1, 9, 12, 8]
Returns the quotient and remainder of the Euclidean division of self and other.
Raises ZerodivisionError if other is zero. Raises ArithmeticError if other has a nonunit leading coefficient.
EXAMPLES:
sage: P.<x> = QQ[]
sage: R.<y> = P[]
sage: f = R.random_element(10)
sage: g = y^5+R.random_element(4)
sage: q,r = f.quo_rem(g)
sage: f == q*g + r
True
sage: g = x*y^5
sage: f.quo_rem(g)
Traceback (most recent call last):
...
ArithmeticError: Nonunit leading coefficient
sage: g = 0
sage: f.quo_rem(g)
Traceback (most recent call last):
...
ZeroDivisionError: Division by zero polynomial
Returns this polynomial multiplied by the power . If
is negative, terms below
will be
discarded. Does not change this polynomial.
EXAMPLES:
sage: R.<x> = PolynomialRing(PolynomialRing(QQ,'y'), 'x')
sage: p = x^2 + 2*x + 4
sage: type(p)
<type 'sage.rings.polynomial.polynomial_element.Polynomial_generic_dense'>
sage: p.shift(0)
x^2 + 2*x + 4
sage: p.shift(-1)
x + 2
sage: p.shift(2)
x^4 + 2*x^3 + 4*x^2
TESTS:
sage: p = R(0)
sage: p.shift(3).is_zero()
True
sage: p.shift(-3).is_zero()
True
AUTHORS:
Returns the polynomial of degree ` < n` which is equivalent
to self modulo .
EXAMPLES:
sage: S.<q> = QQ['t']['q']
sage: f = (1+q^10+q^11+q^12).truncate(11); f
q^10 + 1
sage: f = (1+q^10+q^100).truncate(50); f
q^10 + 1
sage: f.degree()
10
sage: f = (1+q^10+q^100).truncate(500); f
q^100 + q^10 + 1
TESTS:
Make sure we’re not actually testing a specialized implementation.
sage: type(f)
<type 'sage.rings.polynomial.polynomial_element.Polynomial_generic_dense'>
Return True if f is of type univariate polynomial.
INPUT:
EXAMPLES:
sage: from sage.rings.polynomial.polynomial_element import is_Polynomial
sage: R.<x> = ZZ[]
sage: is_Polynomial(x^3 + x + 1)
True
sage: S.<y> = R[]
sage: f = y^3 + x*y -3*x; f
y^3 + x*y - 3*x
sage: is_Polynomial(f)
True
However this function does not return True for genuine multivariate polynomial type objects or symbolic polynomials, since those are not of the same data type as univariate polynomials:
sage: R.<x,y> = QQ[]
sage: f = y^3 + x*y -3*x; f
y^3 + x*y - 3*x
sage: is_Polynomial(f)
False
sage: var('x,y')
(x, y)
sage: f = y^3 + x*y -3*x; f
y^3 + x*y - 3*x
sage: is_Polynomial(f)
False
Return the discriminant of the ‘universal’ univariate polynomial
in
.
INPUT:
OUTPUT:
The discriminant as a polynomial in variables over
.
The result will be cached, so subsequent computations of
discriminants of the same degree will be faster.
EXAMPLES:
sage: from sage.rings.polynomial.polynomial_element import universal_discriminant
sage: universal_discriminant(1)
1
sage: universal_discriminant(2)
a1^2 - 4*a0*a2
sage: universal_discriminant(3)
a1^2*a2^2 - 4*a0*a2^3 - 4*a1^3*a3 + 18*a0*a1*a2*a3 - 27*a0^2*a3^2
sage: universal_discriminant(4).degrees()
(3, 4, 4, 4, 3)
See also