Univariate polynomial base class#

AUTHORS:

  • William Stein: first version

  • Martin Albrecht: added singular coercion

  • Robert Bradshaw: moved Polynomial_generic_dense to Cython

  • Miguel Marco: implemented resultant in the case where PARI fails

  • Simon King: used a faster way of conversion from the base ring

  • Kwankyu Lee (2013-06-02): enhanced quo_rem()

  • Julian Rueth (2012-05-25,2014-05-09): fixed is_squarefree() for imperfect fields, fixed division without remainder over QQbar; added _cache_key for polynomials with unhashable coefficients

  • Simon King (2013-10): implemented copying of PolynomialBaseringInjection

  • Bruno Grenet (2014-07-13): enhanced quo_rem()

  • Kiran Kedlaya (2016-03): added root counting

  • Edgar Costa (2017-07): added rational reconstruction

  • Kiran Kedlaya (2017-09): added reciprocal transform, trace polynomial

  • David Zureick-Brown (2017-09): added is_weil_polynomial

  • Sebastian Oehms (2018-10): made roots() and factor() work over more cases of proper integral domains (see Issue #26421)

class sage.rings.polynomial.polynomial_element.ConstantPolynomialSection[source]#

Bases: Map

This class is used for conversion from a polynomial ring to its base ring.

Since Issue #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)
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)
<class 'sage.rings.polynomial.polynomial_element.ConstantPolynomialSection'>
sage: phi(P0.one())
1
sage: phi(y_1)
Traceback (most recent call last):
...
TypeError: y_1 is not a constant polynomial
>>> from sage.all import *
>>> P0 = GF(Integer(3))['y_1']; (y_1,) = P0._first_ngens(1)
>>> P1 = GF(Integer(3))['y_2, y_1, y_0']; (y_2, y_1, y_0,) = P1._first_ngens(3)
>>> P0(-y_1)
2*y_1

>>> phi = GF(Integer(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
>>> type(phi)
<class 'sage.rings.polynomial.polynomial_element.ConstantPolynomialSection'>
>>> phi(P0.one())
1
>>> phi(y_1)
Traceback (most recent call last):
...
TypeError: y_1 is not a constant polynomial
class sage.rings.polynomial.polynomial_element.Polynomial[source]#

Bases: CommutativePolynomial

A polynomial.

EXAMPLES:

sage: R.<y> = QQ['y']
sage: S.<x> = R['x']
sage: S
Univariate Polynomial Ring in x over Univariate Polynomial Ring in y
over Rational Field
sage: f = x*y; f
y*x
sage: type(f)
<class 'sage.rings.polynomial.polynomial_element.Polynomial_generic_dense'>
sage: p = (y+1)^10; p(1)
1024
>>> from sage.all import *
>>> R = QQ['y']; (y,) = R._first_ngens(1)
>>> S = R['x']; (x,) = S._first_ngens(1)
>>> S
Univariate Polynomial Ring in x over Univariate Polynomial Ring in y
over Rational Field
>>> f = x*y; f
y*x
>>> type(f)
<class 'sage.rings.polynomial.polynomial_element.Polynomial_generic_dense'>
>>> p = (y+Integer(1))**Integer(10); p(Integer(1))
1024
_add_(right)[source]#

Add two polynomials.

EXAMPLES:

sage: R = ZZ['x']
sage: p = R([1,2,3,4])
sage: q = R([4,-3,2,-1])
sage: p + q    # indirect doctest
3*x^3 + 5*x^2 - x + 5
>>> from sage.all import *
>>> R = ZZ['x']
>>> p = R([Integer(1),Integer(2),Integer(3),Integer(4)])
>>> q = R([Integer(4),-Integer(3),Integer(2),-Integer(1)])
>>> p + q    # indirect doctest
3*x^3 + 5*x^2 - x + 5
_sub_(other)[source]#

Default implementation of subtraction using addition and negation.

_lmul_(left)[source]#

Multiply self on the left by a scalar.

EXAMPLES:

sage: R.<x> = ZZ[]
sage: f = (x^3 + x + 5)
sage: f._lmul_(7)
7*x^3 + 7*x + 35
sage: 7*f
7*x^3 + 7*x + 35
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> f = (x**Integer(3) + x + Integer(5))
>>> f._lmul_(Integer(7))
7*x^3 + 7*x + 35
>>> Integer(7)*f
7*x^3 + 7*x + 35
_rmul_(right)[source]#

Multiply self on the right by a scalar.

EXAMPLES:

sage: R.<x> = ZZ[]
sage: f = (x^3 + x + 5)
sage: f._rmul_(7)
7*x^3 + 7*x + 35
sage: f*7
7*x^3 + 7*x + 35
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> f = (x**Integer(3) + x + Integer(5))
>>> f._rmul_(Integer(7))
7*x^3 + 7*x + 35
>>> f*Integer(7)
7*x^3 + 7*x + 35
_mul_(right)[source]#

EXAMPLES:

sage: R.<x> = ZZ[]
sage: (x - 4) * (x^2 - 8*x + 16)
x^3 - 12*x^2 + 48*x - 64
sage: C.<t> = PowerSeriesRing(ZZ)
sage: D.<s> = PolynomialRing(C)
sage: z = (1 + O(t)) + t*s^2
sage: z*z
t^2*s^4 + (2*t + O(t^2))*s^2 + 1 + O(t)

## More examples from trac 2943, added by Kiran S. Kedlaya 2 Dec 09
sage: C.<t> = PowerSeriesRing(Integers())
sage: D.<s> = PolynomialRing(C)
sage: z = 1 + (t + O(t^2))*s + (t^2 + O(t^3))*s^2
sage: z*z
(t^4 + O(t^5))*s^4 + (2*t^3 + O(t^4))*s^3 + (3*t^2 + O(t^3))*s^2 + (2*t + O(t^2))*s + 1
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> (x - Integer(4)) * (x**Integer(2) - Integer(8)*x + Integer(16))
x^3 - 12*x^2 + 48*x - 64
>>> C = PowerSeriesRing(ZZ, names=('t',)); (t,) = C._first_ngens(1)
>>> D = PolynomialRing(C, names=('s',)); (s,) = D._first_ngens(1)
>>> z = (Integer(1) + O(t)) + t*s**Integer(2)
>>> z*z
t^2*s^4 + (2*t + O(t^2))*s^2 + 1 + O(t)

## More examples from trac 2943, added by Kiran S. Kedlaya 2 Dec 09
>>> C = PowerSeriesRing(Integers(), names=('t',)); (t,) = C._first_ngens(1)
>>> D = PolynomialRing(C, names=('s',)); (s,) = D._first_ngens(1)
>>> z = Integer(1) + (t + O(t**Integer(2)))*s + (t**Integer(2) + O(t**Integer(3)))*s**Integer(2)
>>> z*z
(t^4 + O(t^5))*s^4 + (2*t^3 + O(t^4))*s^3 + (3*t^2 + O(t^3))*s^2 + (2*t + O(t^2))*s + 1
_mul_trunc_(right, n)[source]#

Return the truncated multiplication of two polynomials up to n.

This is the default implementation that does the multiplication and then truncate! There are custom implementations in several subclasses:

EXAMPLES:

sage: R = QQ['x']['y']
sage: y = R.gen()
sage: x = R.base_ring().gen()
sage: p1 = 1 - x*y + 2*y**3
sage: p2 = -1/3 + y**5
sage: p1._mul_trunc_(p2, 5)
-2/3*y^3 + 1/3*x*y - 1/3
>>> from sage.all import *
>>> R = QQ['x']['y']
>>> y = R.gen()
>>> x = R.base_ring().gen()
>>> p1 = Integer(1) - x*y + Integer(2)*y**Integer(3)
>>> p2 = -Integer(1)/Integer(3) + y**Integer(5)
>>> p1._mul_trunc_(p2, Integer(5))
-2/3*y^3 + 1/3*x*y - 1/3

Todo

implement a generic truncated Karatsuba and use it here.

adams_operator(*args, **kwds)[source]#

Deprecated: Use adams_operator_on_roots() instead. See Issue #36396 for details.

adams_operator_on_roots(n, monic=False)[source]#

Return the polynomial whose roots are the \(n\)-th powers of the roots of self.

INPUT:

  • \(n\) – an integer

  • monic – boolean (default False) if set to True, force the output to be monic

EXAMPLES:

sage: # needs sage.libs.pari sage.libs.singular
sage: f = cyclotomic_polynomial(30)
sage: f.adams_operator_on_roots(7) == f
True
sage: f.adams_operator_on_roots(6) == cyclotomic_polynomial(5)**2
True
sage: f.adams_operator_on_roots(10) == cyclotomic_polynomial(3)**4
True
sage: f.adams_operator_on_roots(15) == cyclotomic_polynomial(2)**8
True
sage: f.adams_operator_on_roots(30) == cyclotomic_polynomial(1)**8
True

sage: x = polygen(QQ)
sage: f = x^2 - 2*x + 2
sage: f.adams_operator_on_roots(10)                                                  # needs sage.libs.singular
x^2 + 1024
>>> from sage.all import *
>>> # needs sage.libs.pari sage.libs.singular
>>> f = cyclotomic_polynomial(Integer(30))
>>> f.adams_operator_on_roots(Integer(7)) == f
True
>>> f.adams_operator_on_roots(Integer(6)) == cyclotomic_polynomial(Integer(5))**Integer(2)
True
>>> f.adams_operator_on_roots(Integer(10)) == cyclotomic_polynomial(Integer(3))**Integer(4)
True
>>> f.adams_operator_on_roots(Integer(15)) == cyclotomic_polynomial(Integer(2))**Integer(8)
True
>>> f.adams_operator_on_roots(Integer(30)) == cyclotomic_polynomial(Integer(1))**Integer(8)
True

>>> x = polygen(QQ)
>>> f = x**Integer(2) - Integer(2)*x + Integer(2)
>>> f.adams_operator_on_roots(Integer(10))                                                  # needs sage.libs.singular
x^2 + 1024

When self is monic, the output will have leading coefficient \(\pm1\) depending on the degree, but we can force it to be monic:

sage: R.<a,b,c> = ZZ[]
sage: x = polygen(R)
sage: f = (x - a) * (x - b) * (x - c)
sage: f.adams_operator_on_roots(3).factor()                                          # needs sage.libs.singular
(-1) * (x - c^3) * (x - b^3) * (x - a^3)
sage: f.adams_operator_on_roots(3, monic=True).factor()                              # needs sage.libs.singular
(x - c^3) * (x - b^3) * (x - a^3)
>>> from sage.all import *
>>> R = ZZ['a, b, c']; (a, b, c,) = R._first_ngens(3)
>>> x = polygen(R)
>>> f = (x - a) * (x - b) * (x - c)
>>> f.adams_operator_on_roots(Integer(3)).factor()                                          # needs sage.libs.singular
(-1) * (x - c^3) * (x - b^3) * (x - a^3)
>>> f.adams_operator_on_roots(Integer(3), monic=True).factor()                              # needs sage.libs.singular
(x - c^3) * (x - b^3) * (x - a^3)
add_bigoh(prec)[source]#

Return the power series of precision at most prec got by adding \(O(q^\text{prec})\) 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
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> f = Integer(1) + Integer(4)*x + x**Integer(3)
>>> f.add_bigoh(Integer(7))
1 + 4*x + x^3 + O(x^7)
>>> f.add_bigoh(Integer(2))
1 + 4*x + O(x^2)
>>> f.add_bigoh(Integer(2)).parent()
Power Series Ring in x over Integer Ring
all_roots_in_interval(a=None, b=None)[source]#

Return True if the roots of this polynomial are all real and contained in the given interval.

EXAMPLES:

sage: # needs sage.libs.pari
sage: R.<x> = PolynomialRing(ZZ)
sage: pol = (x - 1)^2 * (x - 2)^2 * (x - 3)
sage: pol.all_roots_in_interval(1, 3)
True
sage: pol.all_roots_in_interval(1.01, 3)
False
sage: pol = chebyshev_T(5, x)
sage: pol.all_roots_in_interval(-1, 1)
True
sage: pol = chebyshev_T(5, x/2)
sage: pol.all_roots_in_interval(-1, 1)
False
sage: pol.all_roots_in_interval()
True
>>> from sage.all import *
>>> # needs sage.libs.pari
>>> R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> pol = (x - Integer(1))**Integer(2) * (x - Integer(2))**Integer(2) * (x - Integer(3))
>>> pol.all_roots_in_interval(Integer(1), Integer(3))
True
>>> pol.all_roots_in_interval(RealNumber('1.01'), Integer(3))
False
>>> pol = chebyshev_T(Integer(5), x)
>>> pol.all_roots_in_interval(-Integer(1), Integer(1))
True
>>> pol = chebyshev_T(Integer(5), x/Integer(2))
>>> pol.all_roots_in_interval(-Integer(1), Integer(1))
False
>>> pol.all_roots_in_interval()
True
any_irreducible_factor(degree=None, assume_squarefree=False, assume_equal_deg=False, ext_degree=None)[source]#

Return an irreducible factor of this polynomial.

INPUT:

  • degree (None or positive integer) – (default: None). Used for polynomials over finite fields. If None, returns the the first factor found (usually the smallest). Otherwise, attempts to return an irreducible factor of self of chosen degree degree.

  • assume_squarefree (boolean) – (default: False). Used for polynomials over finite fields. If True, this polynomial is assumed to be squarefree.

  • assume_equal_deg (boolean) – (default: False). Used for polynomials over finite fields. If True, this polynomial is assumed to be the product of irreducible polynomials of degree equal to degree.

  • ext_degree – positive integer or None (default); used for polynomials over finite fields. If not None only returns irreducible factors of self whose degree divides ext_degree.

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: F = GF(163)
sage: R.<x> = F[]
sage: f = (x + 40)^3 * (x^5 + 76*x^4 + 93*x^3 + 112*x^2 + 22*x + 27)^2 * (x^6 + 50*x^5 + 143*x^4 + 162*x^2 + 109*x + 140)
sage: f.any_irreducible_factor()
x + 40
sage: f.any_irreducible_factor(degree=5)
x^5 + 76*x^4 + 93*x^3 + 112*x^2 + 22*x + 27
>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> F = GF(Integer(163))
>>> R = F['x']; (x,) = R._first_ngens(1)
>>> f = (x + Integer(40))**Integer(3) * (x**Integer(5) + Integer(76)*x**Integer(4) + Integer(93)*x**Integer(3) + Integer(112)*x**Integer(2) + Integer(22)*x + Integer(27))**Integer(2) * (x**Integer(6) + Integer(50)*x**Integer(5) + Integer(143)*x**Integer(4) + Integer(162)*x**Integer(2) + Integer(109)*x + Integer(140))
>>> f.any_irreducible_factor()
x + 40
>>> f.any_irreducible_factor(degree=Integer(5))
x^5 + 76*x^4 + 93*x^3 + 112*x^2 + 22*x + 27

When the polynomial is known to be squarefree we can optimise the call by setting assume_squarefree to be True:

sage: # needs sage.rings.finite_rings
sage: F = GF(163)
sage: R.<x> = F[]
sage: g = (x - 1) * (x^3 + 7*x + 161)
sage: g.any_irreducible_factor(assume_squarefree=True)
x + 162
sage: g.any_irreducible_factor(degree=3, assume_squarefree=True)
x^3 + 7*x + 161
>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> F = GF(Integer(163))
>>> R = F['x']; (x,) = R._first_ngens(1)
>>> g = (x - Integer(1)) * (x**Integer(3) + Integer(7)*x + Integer(161))
>>> g.any_irreducible_factor(assume_squarefree=True)
x + 162
>>> g.any_irreducible_factor(degree=Integer(3), assume_squarefree=True)
x^3 + 7*x + 161

If we ask for an irreducible factor which does not exist, the function will throw a ValueError:

sage: # needs sage.rings.finite_rings
sage: F = GF(163)
sage: R.<x> = F[]
sage: g = (x - 1) * (x^3 + 7*x + 161)
sage: g.any_irreducible_factor(degree=2, assume_squarefree=True)
Traceback (most recent call last):
...
ValueError: no irreducible factor of degree 2 could be computed from x^4 + 162*x^3 + 7*x^2 + 154*x + 2
>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> F = GF(Integer(163))
>>> R = F['x']; (x,) = R._first_ngens(1)
>>> g = (x - Integer(1)) * (x**Integer(3) + Integer(7)*x + Integer(161))
>>> g.any_irreducible_factor(degree=Integer(2), assume_squarefree=True)
Traceback (most recent call last):
...
ValueError: no irreducible factor of degree 2 could be computed from x^4 + 162*x^3 + 7*x^2 + 154*x + 2

If we assume that the polynomial is product of irreducible polynomials of the same degree, we must also supply the degree:

sage: # needs sage.rings.finite_rings
sage: F = GF(163)
sage: R.<x> = F[]
sage: h = (x + 57) * (x + 98) * (x + 117) * (x + 145)
sage: h.any_irreducible_factor(degree=1, assume_equal_deg=True)   # random
x + 98
sage: h.any_irreducible_factor(assume_equal_deg=True)
Traceback (most recent call last):
...
ValueError: degree must be known if distinct degree factorisation is assumed
>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> F = GF(Integer(163))
>>> R = F['x']; (x,) = R._first_ngens(1)
>>> h = (x + Integer(57)) * (x + Integer(98)) * (x + Integer(117)) * (x + Integer(145))
>>> h.any_irreducible_factor(degree=Integer(1), assume_equal_deg=True)   # random
x + 98
>>> h.any_irreducible_factor(assume_equal_deg=True)
Traceback (most recent call last):
...
ValueError: degree must be known if distinct degree factorisation is assumed

Also works for extension fields and even characteristic:

sage: F.<z4> = GF(2^4)
sage: R.<x> = F[]
sage: f = (x + z4^3 + z4^2)^4 * (x^2 + z4*x + z4) * (x^2 + (z4^3 + z4^2 + z4)*x + z4^2 + z4 + 1)
sage: f.any_irreducible_factor()
x + z4^3 + z4^2
sage: f.any_irreducible_factor(degree=2)  # random
x^2 + (z4^3 + z4^2 + z4)*x + z4^2 + z4 + 1
>>> from sage.all import *
>>> F = GF(Integer(2)**Integer(4), names=('z4',)); (z4,) = F._first_ngens(1)
>>> R = F['x']; (x,) = R._first_ngens(1)
>>> f = (x + z4**Integer(3) + z4**Integer(2))**Integer(4) * (x**Integer(2) + z4*x + z4) * (x**Integer(2) + (z4**Integer(3) + z4**Integer(2) + z4)*x + z4**Integer(2) + z4 + Integer(1))
>>> f.any_irreducible_factor()
x + z4^3 + z4^2
>>> f.any_irreducible_factor(degree=Integer(2))  # random
x^2 + (z4^3 + z4^2 + z4)*x + z4^2 + z4 + 1

We can also use this function for polynomials which are not defined over finite fields, but this simply falls back to a slow method of factorisation:

sage: R.<x> = ZZ[]
sage: f = 3*x^4 + 2*x^3
sage: f.any_irreducible_factor()
3*x + 2
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> f = Integer(3)*x**Integer(4) + Integer(2)*x**Integer(3)
>>> f.any_irreducible_factor()
3*x + 2
any_root(ring=None, degree=None, assume_squarefree=False, assume_equal_deg=False)[source]#

Return a root of this polynomial in the given ring.

INPUT:

  • ring – The ring in which a root is sought. By default this is the coefficient ring.

  • degree (None or nonzero integer) – Used for polynomials over finite fields. Return a root of degree abs(degree) over the ground field. If negative, also assumes that all factors of this polynomial are of degree abs(degree). If None, returns a root of minimal degree contained within the given ring.

  • assume_squarefree (bool) – Used for polynomials over finite fields. If True, this polynomial is assumed to be squarefree.

  • assume_equal_deg (bool) – Used for polynomials over finite fields. If True, all factors of this polynomial are assumed to have degree degree. Note that degree must be set.

Warning

Negative degree input will be deprecated. Instead use assume_equal_deg.

Note

For finite fields, any_root() is non-deterministic when finding linear roots of a polynomial over the base ring. However, if degree is greater than one, or ring is an extension of the base ring, then the root computed is found by attempting to return a root after factorisation. Roots found in this way are deterministic. This may change in the future. For all other rings or fields, roots are found by first fully-factoring self and the output is deterministic.

EXAMPLES:

sage: # needs sage.rings.finite_rings
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: root = f.any_root(GF(11^6, 'a'))
sage: roots = sorted(f.roots(GF(11^6, 'a'), multiplicities=False))
sage: roots
[10*a^5 + 2*a^4 + 8*a^3 + 9*a^2 + a,
a^5 + a^4 + 7*a^3 + 2*a^2 + 10*a,
9*a^5 + 5*a^4 + 10*a^3 + 8*a^2 + 3*a + 1,
2*a^5 + 8*a^4 + 3*a^3 + 6*a + 2,
a^5 + 3*a^4 + 8*a^3 + 2*a^2 + 3*a + 4,
10*a^5 + 3*a^4 + 8*a^3 + a^2 + 10*a + 4]
sage: root in roots
True

sage: # needs sage.rings.finite_rings
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: root = g.any_root(ring=GF(11^10, 'b'), degree=2)
sage: roots = (x^2 + 3*x + 9).roots(ring=GF(11^10, 'b'), multiplicities=False)
sage: root in roots
True
sage: root = g.any_root(ring=GF(11^10, 'b'), degree=5)
sage: roots = (x^5 + 5*x^4 + 8*x^3 + 5*x^2 + 3*x + 5).roots(ring=GF(11^10, 'b'), multiplicities=False)
sage: root in roots
True
>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> R = GF(Integer(11))['x']; (x,) = R._first_ngens(1)
>>> f = Integer(7)*x**Integer(7) + Integer(8)*x**Integer(6) + Integer(4)*x**Integer(5) + x**Integer(4) + Integer(6)*x**Integer(3) + Integer(10)*x**Integer(2) + Integer(8)*x + Integer(5)
>>> f.any_root()
2
>>> f.factor()
(7) * (x + 9) * (x^6 + 10*x^4 + 6*x^3 + 5*x^2 + 2*x + 2)
>>> f = x**Integer(6) + Integer(10)*x**Integer(4) + Integer(6)*x**Integer(3) + Integer(5)*x**Integer(2) + Integer(2)*x + Integer(2)
>>> root = f.any_root(GF(Integer(11)**Integer(6), 'a'))
>>> roots = sorted(f.roots(GF(Integer(11)**Integer(6), 'a'), multiplicities=False))
>>> roots
[10*a^5 + 2*a^4 + 8*a^3 + 9*a^2 + a,
a^5 + a^4 + 7*a^3 + 2*a^2 + 10*a,
9*a^5 + 5*a^4 + 10*a^3 + 8*a^2 + 3*a + 1,
2*a^5 + 8*a^4 + 3*a^3 + 6*a + 2,
a^5 + 3*a^4 + 8*a^3 + 2*a^2 + 3*a + 4,
10*a^5 + 3*a^4 + 8*a^3 + a^2 + 10*a + 4]
>>> root in roots
True

>>> # needs sage.rings.finite_rings
>>> g = (x-Integer(1)) * (x**Integer(2) + Integer(3)*x + Integer(9)) * (x**Integer(5) + Integer(5)*x**Integer(4) + Integer(8)*x**Integer(3) + Integer(5)*x**Integer(2) + Integer(3)*x + Integer(5))
>>> g.any_root(ring=GF(Integer(11)**Integer(10), 'b'), degree=Integer(1))
1
>>> root = g.any_root(ring=GF(Integer(11)**Integer(10), 'b'), degree=Integer(2))
>>> roots = (x**Integer(2) + Integer(3)*x + Integer(9)).roots(ring=GF(Integer(11)**Integer(10), 'b'), multiplicities=False)
>>> root in roots
True
>>> root = g.any_root(ring=GF(Integer(11)**Integer(10), 'b'), degree=Integer(5))
>>> roots = (x**Integer(5) + Integer(5)*x**Integer(4) + Integer(8)*x**Integer(3) + Integer(5)*x**Integer(2) + Integer(3)*x + Integer(5)).roots(ring=GF(Integer(11)**Integer(10), 'b'), multiplicities=False)
>>> root in roots
True
args()[source]#

Return the generator of this polynomial ring, which is the (only) argument used when calling self.

EXAMPLES:

sage: R.<x> = QQ[]
sage: x.args()
(x,)
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> x.args()
(x,)

A constant polynomial has no variables, but still takes a single argument.

sage: R(2).args()
(x,)
>>> from sage.all import *
>>> R(Integer(2)).args()
(x,)
base_extend(R)[source]#

Return a copy of this polynomial but with coefficients in R, if there is a natural map from the 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
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(3) - Integer(17)*x + Integer(3)
>>> f.base_extend(GF(Integer(7)))
Traceback (most recent call last):
...
TypeError: no such base extension
>>> f.change_ring(GF(Integer(7)))
x^3 + 4*x + 3
base_ring()[source]#

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
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> x.base_ring()
Integer Ring
>>> (Integer(2)*x + Integer(3)).base_ring()
Integer Ring
change_ring(R)[source]#

Return a copy of this polynomial but with coefficients in R, if at all possible.

INPUT:

  • R – a ring or morphism.

EXAMPLES:

sage: K.<z> = CyclotomicField(3)                                            # needs sage.rings.number_field
sage: f = K.defining_polynomial()                                           # needs sage.rings.number_field
sage: f.change_ring(GF(7))                                                  # needs sage.rings.finite_rings sage.rings.number_field
x^2 + x + 1
>>> from sage.all import *
>>> K = CyclotomicField(Integer(3), names=('z',)); (z,) = K._first_ngens(1)# needs sage.rings.number_field
>>> f = K.defining_polynomial()                                           # needs sage.rings.number_field
>>> f.change_ring(GF(Integer(7)))                                                  # needs sage.rings.finite_rings sage.rings.number_field
x^2 + x + 1
sage: # needs sage.rings.number_field
sage: K.<z> = CyclotomicField(3)
sage: R.<x> = K[]
sage: f = x^2 + z
sage: f.change_ring(K.embeddings(CC)[1])                                    # needs sage.rings.real_mpfr
x^2 - 0.500000000000000 - 0.866025403784438*I
>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> K = CyclotomicField(Integer(3), names=('z',)); (z,) = K._first_ngens(1)
>>> R = K['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(2) + z
>>> f.change_ring(K.embeddings(CC)[Integer(1)])                                    # needs sage.rings.real_mpfr
x^2 - 0.500000000000000 - 0.866025403784438*I
sage: R.<x> = QQ[]
sage: f = x^2 + 1
sage: f.change_ring(QQ.embeddings(CC)[0])                                   # needs sage.rings.real_mpfr
x^2 + 1.00000000000000
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(2) + Integer(1)
>>> f.change_ring(QQ.embeddings(CC)[Integer(0)])                                   # needs sage.rings.real_mpfr
x^2 + 1.00000000000000
change_variable_name(var)[source]#

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
>>> from sage.all import *
>>> x = polygen(QQ,'x')
>>> f = -Integer(2)/Integer(7)*x**Integer(3) + (Integer(2)/Integer(3))*x - Integer(19)/Integer(993); f
-2/7*x^3 + 2/3*x - 19/993
>>> f.change_variable_name('theta')
-2/7*theta^3 + 2/3*theta - 19/993
coefficients(sparse=True)[source]#

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.) In either case, the coefficients are ordered by increasing degree.

EXAMPLES:

sage: _.<x> = PolynomialRing(ZZ)
sage: f = 3*x^4 + 2*x^2 + 1
sage: f.coefficients()
[1, 2, 3]
sage: f.coefficients(sparse=False)
[1, 0, 2, 0, 3]
>>> from sage.all import *
>>> _ = PolynomialRing(ZZ, names=('x',)); (x,) = _._first_ngens(1)
>>> f = Integer(3)*x**Integer(4) + Integer(2)*x**Integer(2) + Integer(1)
>>> f.coefficients()
[1, 2, 3]
>>> f.coefficients(sparse=False)
[1, 0, 2, 0, 3]
complex_roots()[source]#

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: # needs sage.libs.pari sage.rings.real_mpfr
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]
>>> from sage.all import *
>>> # needs sage.libs.pari sage.rings.real_mpfr
>>> x = polygen(ZZ)
>>> (x**Integer(3) - Integer(1)).complex_roots()   # note: low order bits slightly different on ppc.
[1.00000000000000,
 -0.500000000000000 - 0.86602540378443...*I,
 -0.500000000000000 + 0.86602540378443...*I]
compose_power(k, algorithm=None, monic=False)[source]#

Return the \(k\)-th iterate of the composed product of this polynomial with itself.

INPUT:

  • \(k\) – a non-negative integer

  • algorithmNone (default), "resultant" or "BFSS". See composed_op()

  • monicFalse (default) or True. See composed_op()

OUTPUT:

The polynomial of degree \(d^k\) where \(d\) is the degree, whose roots are all \(k\)-fold products of roots of this polynomial. That is, \(f*f*\dots*f\) where this is \(f\) and \(f*f=\) f.composed_op(f, operator.mul).

EXAMPLES:

sage: R.<a,b,c> = ZZ[]
sage: x = polygen(R)
sage: f = (x - a) * (x - b) * (x - c)
sage: f.compose_power(2).factor()                                           # needs sage.libs.singular sage.modules
(x - c^2) * (x - b^2) * (x - a^2) * (x - b*c)^2 * (x - a*c)^2 * (x - a*b)^2

sage: # needs sage.libs.singular sage.modules
sage: x = polygen(QQ)
sage: f = x^2 - 2*x + 2
sage: f2 = f.compose_power(2); f2
x^4 - 4*x^3 + 8*x^2 - 16*x + 16
sage: f2 == f.composed_op(f, operator.mul)
True
sage: f3 = f.compose_power(3); f3
x^8 - 8*x^7 + 32*x^6 - 64*x^5 + 128*x^4 - 512*x^3 + 2048*x^2 - 4096*x + 4096
sage: f3 == f2.composed_op(f, operator.mul)
True
sage: f4 = f.compose_power(4)
sage: f4 == f3.composed_op(f, operator.mul)
True
>>> from sage.all import *
>>> R = ZZ['a, b, c']; (a, b, c,) = R._first_ngens(3)
>>> x = polygen(R)
>>> f = (x - a) * (x - b) * (x - c)
>>> f.compose_power(Integer(2)).factor()                                           # needs sage.libs.singular sage.modules
(x - c^2) * (x - b^2) * (x - a^2) * (x - b*c)^2 * (x - a*c)^2 * (x - a*b)^2

>>> # needs sage.libs.singular sage.modules
>>> x = polygen(QQ)
>>> f = x**Integer(2) - Integer(2)*x + Integer(2)
>>> f2 = f.compose_power(Integer(2)); f2
x^4 - 4*x^3 + 8*x^2 - 16*x + 16
>>> f2 == f.composed_op(f, operator.mul)
True
>>> f3 = f.compose_power(Integer(3)); f3
x^8 - 8*x^7 + 32*x^6 - 64*x^5 + 128*x^4 - 512*x^3 + 2048*x^2 - 4096*x + 4096
>>> f3 == f2.composed_op(f, operator.mul)
True
>>> f4 = f.compose_power(Integer(4))
>>> f4 == f3.composed_op(f, operator.mul)
True
compose_trunc(other, n)[source]#

Return the composition of self and other, truncated to \(O(x^n)\).

This method currently works for some specific coefficient rings only.

EXAMPLES:

sage: Pol.<x> = CBF[]                                                       # needs sage.libs.flint
sage: (1 + x + x^2/2 + x^3/6 + x^4/24 + x^5/120).compose_trunc(1 + x, 2)    # needs sage.libs.flint
([2.708333333333333 +/- ...e-16])*x + [2.71666666666667 +/- ...e-15]

sage: Pol.<x> = QQ['y'][]
sage: (1 + x + x^2/2 + x^3/6 + x^4/24 + x^5/120).compose_trunc(1 + x, 2)
Traceback (most recent call last):
...
NotImplementedError: truncated composition is not implemented
for this subclass of polynomials
>>> from sage.all import *
>>> Pol = CBF['x']; (x,) = Pol._first_ngens(1)# needs sage.libs.flint
>>> (Integer(1) + x + x**Integer(2)/Integer(2) + x**Integer(3)/Integer(6) + x**Integer(4)/Integer(24) + x**Integer(5)/Integer(120)).compose_trunc(Integer(1) + x, Integer(2))    # needs sage.libs.flint
([2.708333333333333 +/- ...e-16])*x + [2.71666666666667 +/- ...e-15]

>>> Pol = QQ['y']['x']; (x,) = Pol._first_ngens(1)
>>> (Integer(1) + x + x**Integer(2)/Integer(2) + x**Integer(3)/Integer(6) + x**Integer(4)/Integer(24) + x**Integer(5)/Integer(120)).compose_trunc(Integer(1) + x, Integer(2))
Traceback (most recent call last):
...
NotImplementedError: truncated composition is not implemented
for this subclass of polynomials
composed_op(p1, p2, op, algorithm=None, monic=False)[source]#

Return the composed sum, difference, product or quotient of this polynomial with another one.

In the case of two monic polynomials \(p_1\) and \(p_2\) over an integral domain, the composed sum, difference, etc. are given by

\[\prod_{p_1(a)=p_2(b)=0}(x - (a \ast b)), \qquad \ast ∈ \{ +, -, ×, / \}\]

where the roots \(a\) and \(b\) are to be considered in the algebraic closure of the fraction field of the coefficients and counted with multiplicities. If the polynomials are not monic this quantity is multiplied by \(\alpha_1^{\deg(p_2)} \alpha_2^{\deg(p_1)}\) where \(\alpha_1\) and \(\alpha_2\) are the leading coefficients of \(p_1\) and \(p_2\) respectively.

INPUT:

  • p2 – univariate polynomial belonging to the same polynomial ring as this polynomial

  • opoperator.OP where OP=add or sub or mul or truediv.

  • algorithm – can be "resultant" or "BFSS"; by default the former is used when the polynomials have few nonzero coefficients and small degrees or if the base ring is not \(\ZZ\) or \(\QQ\). Otherwise the latter is used.

  • monic – whether to return a monic polynomial. If True the coefficients of the result belong to the fraction field of the coefficients.

ALGORITHM:

The computation is straightforward using resultants. Indeed for the composed sum it would be \(Res_y(p_1(x-y), p_2(y))\). However, the method from [BFSS2006] using series expansions is asymptotically much faster.

Note that the algorithm BFSS with polynomials with coefficients in \(\ZZ\) needs to perform operations over \(\QQ\).

Todo

  • The [BFSS2006] algorithm has been implemented here only in the case of polynomials over rationals. For other rings of zero characteristic (or if the characteristic is larger than the product of the degrees), one needs to implement a generic method _exp_series. In the general case of non-zero characteristic there is an alternative algorithm in the same paper.

  • The Newton series computation can be done much more efficiently! See [BFSS2006].

EXAMPLES:

sage: x = polygen(ZZ)
sage: p1 = x^2 - 1
sage: p2 = x^4 - 1
sage: p1.composed_op(p2, operator.add)                                      # needs sage.libs.singular
x^8 - 4*x^6 + 4*x^4 - 16*x^2
sage: p1.composed_op(p2, operator.mul)                                      # needs sage.libs.singular
x^8 - 2*x^4 + 1
sage: p1.composed_op(p2, operator.truediv)                                  # needs sage.libs.singular
x^8 - 2*x^4 + 1
>>> from sage.all import *
>>> x = polygen(ZZ)
>>> p1 = x**Integer(2) - Integer(1)
>>> p2 = x**Integer(4) - Integer(1)
>>> p1.composed_op(p2, operator.add)                                      # needs sage.libs.singular
x^8 - 4*x^6 + 4*x^4 - 16*x^2
>>> p1.composed_op(p2, operator.mul)                                      # needs sage.libs.singular
x^8 - 2*x^4 + 1
>>> p1.composed_op(p2, operator.truediv)                                  # needs sage.libs.singular
x^8 - 2*x^4 + 1

This function works over any field. However for base rings other than \(\ZZ\) and \(\QQ\) only the resultant algorithm is available:

sage: # needs sage.rings.number_field
sage: x = polygen(QQbar)
sage: p1 = x**2 - AA(2).sqrt()
sage: p2 = x**3 - AA(3).sqrt()
sage: r1 = p1.roots(multiplicities=False)
sage: r2 = p2.roots(multiplicities=False)
sage: p = p1.composed_op(p2, operator.add); p
x^6 - 4.242640687119285?*x^4 - 3.464101615137755?*x^3 + 6*x^2
 - 14.69693845669907?*x + 0.1715728752538099?
sage: all(p(x+y).is_zero() for x in r1 for y in r2)
True

sage: x = polygen(GF(2))
sage: p1 = x**2 + x - 1
sage: p2 = x**3 + x - 1
sage: p_add = p1.composed_op(p2, operator.add); p_add                       # needs sage.libs.singular
x^6 + x^5 + x^3 + x^2 + 1
sage: p_mul = p1.composed_op(p2, operator.mul); p_mul                       # needs sage.libs.singular
x^6 + x^4 + x^2 + x + 1
sage: p_div = p1.composed_op(p2, operator.truediv); p_div                   # needs sage.libs.singular
x^6 + x^5 + x^4 + x^2 + 1

sage: # needs sage.rings.finite_rings
sage: K = GF(2**6, 'a')
sage: r1 = p1.roots(K, multiplicities=False)
sage: r2 = p2.roots(K, multiplicities=False)
sage: all(p_add(x1+x2).is_zero() for x1 in r1 for x2 in r2)                 # needs sage.libs.singular
True
sage: all(p_mul(x1*x2).is_zero() for x1 in r1 for x2 in r2)                 # needs sage.libs.singular
True
sage: all(p_div(x1/x2).is_zero() for x1 in r1 for x2 in r2)                 # needs sage.libs.singular
True
>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> x = polygen(QQbar)
>>> p1 = x**Integer(2) - AA(Integer(2)).sqrt()
>>> p2 = x**Integer(3) - AA(Integer(3)).sqrt()
>>> r1 = p1.roots(multiplicities=False)
>>> r2 = p2.roots(multiplicities=False)
>>> p = p1.composed_op(p2, operator.add); p
x^6 - 4.242640687119285?*x^4 - 3.464101615137755?*x^3 + 6*x^2
 - 14.69693845669907?*x + 0.1715728752538099?
>>> all(p(x+y).is_zero() for x in r1 for y in r2)
True

>>> x = polygen(GF(Integer(2)))
>>> p1 = x**Integer(2) + x - Integer(1)
>>> p2 = x**Integer(3) + x - Integer(1)
>>> p_add = p1.composed_op(p2, operator.add); p_add                       # needs sage.libs.singular
x^6 + x^5 + x^3 + x^2 + 1
>>> p_mul = p1.composed_op(p2, operator.mul); p_mul                       # needs sage.libs.singular
x^6 + x^4 + x^2 + x + 1
>>> p_div = p1.composed_op(p2, operator.truediv); p_div                   # needs sage.libs.singular
x^6 + x^5 + x^4 + x^2 + 1

>>> # needs sage.rings.finite_rings
>>> K = GF(Integer(2)**Integer(6), 'a')
>>> r1 = p1.roots(K, multiplicities=False)
>>> r2 = p2.roots(K, multiplicities=False)
>>> all(p_add(x1+x2).is_zero() for x1 in r1 for x2 in r2)                 # needs sage.libs.singular
True
>>> all(p_mul(x1*x2).is_zero() for x1 in r1 for x2 in r2)                 # needs sage.libs.singular
True
>>> all(p_div(x1/x2).is_zero() for x1 in r1 for x2 in r2)                 # needs sage.libs.singular
True
constant_coefficient()[source]#

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
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = -Integer(2)*x**Integer(3) + Integer(2)*x - Integer(1)/Integer(3)
>>> f.constant_coefficient()
-1/3
content_ideal()[source]#

Return the content ideal of this polynomial, defined as the ideal generated by its coefficients.

EXAMPLES:

sage: R.<x> = IntegerModRing(4)[]
sage: f = x^4 + 3*x^2 + 2
sage: f.content_ideal()
Ideal (2, 3, 1) of Ring of integers modulo 4
>>> from sage.all import *
>>> R = IntegerModRing(Integer(4))['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(4) + Integer(3)*x**Integer(2) + Integer(2)
>>> f.content_ideal()
Ideal (2, 3, 1) of Ring of integers modulo 4

When the base ring is a gcd ring, the content as a ring element is the generator of the content ideal:

sage: R.<x> = ZZ[]
sage: f = 2*x^3 - 4*x^2 + 6*x - 10
sage: f.content_ideal().gen()
2
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> f = Integer(2)*x**Integer(3) - Integer(4)*x**Integer(2) + Integer(6)*x - Integer(10)
>>> f.content_ideal().gen()
2
cyclotomic_part()[source]#

Return the product of the irreducible factors of this polynomial which are cyclotomic polynomials.

The algorithm assumes that the polynomial has rational coefficients.

EXAMPLES:

sage: P.<x> = PolynomialRing(Integers())
sage: pol = 2*(x^4 + 1)
sage: pol.cyclotomic_part()
x^4 + 1
sage: pol = x^4 + 2
sage: pol.cyclotomic_part()
1
sage: pol = (x^4 + 1)^2 * (x^4 + 2)
sage: pol.cyclotomic_part()
x^8 + 2*x^4 + 1

sage: P.<x> = PolynomialRing(QQ)
sage: pol = (x^4 + 1)^2 * (x^4 + 2)
sage: pol.cyclotomic_part()
x^8 + 2*x^4 + 1

sage: pol = (x - 1) * x * (x + 2)
sage: pol.cyclotomic_part()
x - 1
>>> from sage.all import *
>>> P = PolynomialRing(Integers(), names=('x',)); (x,) = P._first_ngens(1)
>>> pol = Integer(2)*(x**Integer(4) + Integer(1))
>>> pol.cyclotomic_part()
x^4 + 1
>>> pol = x**Integer(4) + Integer(2)
>>> pol.cyclotomic_part()
1
>>> pol = (x**Integer(4) + Integer(1))**Integer(2) * (x**Integer(4) + Integer(2))
>>> pol.cyclotomic_part()
x^8 + 2*x^4 + 1

>>> P = PolynomialRing(QQ, names=('x',)); (x,) = P._first_ngens(1)
>>> pol = (x**Integer(4) + Integer(1))**Integer(2) * (x**Integer(4) + Integer(2))
>>> pol.cyclotomic_part()
x^8 + 2*x^4 + 1

>>> pol = (x - Integer(1)) * x * (x + Integer(2))
>>> pol.cyclotomic_part()
x - 1
degree(gen=None)[source]#

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
>>> from sage.all import *
>>> x = ZZ['x'].gen(0)
>>> f = x**Integer(93) + Integer(2)*x + Integer(1)
>>> f.degree()
93
>>> x = PolynomialRing(QQ, 'x', sparse=True).gen(0)
>>> f = x**Integer(100000)
>>> 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
>>> from sage.all import *
>>> x = QQ['x'].gen(0)
>>> f = Integer(2006)*x**Integer(2006) - x**Integer(2) + Integer(3)
>>> f.degree()
2006
>>> f = Integer(0)*x
>>> f.degree()
-1
>>> f = x + Integer(33)
>>> f.degree()
1

AUTHORS:

  • Naqi Jaffery (2006-01-24): examples

denominator()[source]#

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() method. 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
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(3) + Integer(17)*x + Integer(1)
>>> 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
>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> f = (Integer(1)/Integer(17))*x**Integer(19) - (Integer(2)/Integer(3))*x + Integer(1)/Integer(3); f
1/17*x^19 - 2/3*x + 1/3
>>> 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: # needs sage.rings.real_mpfr
sage: R.<x> = RR[]
sage: f = x + RR('0.3'); f
x + 0.300000000000000
sage: f.denominator()
1.00000000000000
>>> from sage.all import *
>>> # needs sage.rings.real_mpfr
>>> R = RR['x']; (x,) = R._first_ngens(1)
>>> f = x + RR('0.3'); f
x + 0.300000000000000
>>> f.denominator()
1.00000000000000

Check that the denominator is an element over the base whenever the base has no denominator() method. This closes Issue #9063.

sage: R.<a> = GF(5)[]
sage: x = R(0)
sage: x.denominator()
1
sage: type(x.denominator())
<class 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>
sage: isinstance(x.numerator() / x.denominator(), Polynomial)
True
sage: isinstance(x.numerator() / R(1), Polynomial)
False
>>> from sage.all import *
>>> R = GF(Integer(5))['a']; (a,) = R._first_ngens(1)
>>> x = R(Integer(0))
>>> x.denominator()
1
>>> type(x.denominator())
<class 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>
>>> isinstance(x.numerator() / x.denominator(), Polynomial)
True
>>> isinstance(x.numerator() / R(Integer(1)), Polynomial)
False
derivative(*args)[source]#

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
>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> g = -x**Integer(4) + x**Integer(2)/Integer(2) - x
>>> g.derivative()
-4*x^3 + x - 1
>>> g.derivative(x)
-4*x^3 + x - 1
>>> g.derivative(x, x)
-12*x^2 + 1
>>> g.derivative(x, Integer(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
>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('t',)); (t,) = R._first_ngens(1)
>>> S = PolynomialRing(R, names=('x',)); (x,) = S._first_ngens(1)
>>> f = t**Integer(3)*x**Integer(2) + t**Integer(4)*x**Integer(3)
>>> f.derivative()
3*t^4*x^2 + 2*t^3*x
>>> f.derivative(x)
3*t^4*x^2 + 2*t^3*x
>>> f.derivative(t)
4*t^3*x^3 + 3*t^2*x^2
dict()[source]#

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}
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(3) + -Integer(1)/Integer(7)*x + Integer(13)
>>> f.dict()
{0: 13, 1: -1/7, 3: 1}
diff(*args)[source]#

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
>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> g = -x**Integer(4) + x**Integer(2)/Integer(2) - x
>>> g.derivative()
-4*x^3 + x - 1
>>> g.derivative(x)
-4*x^3 + x - 1
>>> g.derivative(x, x)
-12*x^2 + 1
>>> g.derivative(x, Integer(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
>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('t',)); (t,) = R._first_ngens(1)
>>> S = PolynomialRing(R, names=('x',)); (x,) = S._first_ngens(1)
>>> f = t**Integer(3)*x**Integer(2) + t**Integer(4)*x**Integer(3)
>>> f.derivative()
3*t^4*x^2 + 2*t^3*x
>>> f.derivative(x)
3*t^4*x^2 + 2*t^3*x
>>> f.derivative(t)
4*t^3*x^3 + 3*t^2*x^2
differentiate(*args)[source]#

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
>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> g = -x**Integer(4) + x**Integer(2)/Integer(2) - x
>>> g.derivative()
-4*x^3 + x - 1
>>> g.derivative(x)
-4*x^3 + x - 1
>>> g.derivative(x, x)
-12*x^2 + 1
>>> g.derivative(x, Integer(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
>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('t',)); (t,) = R._first_ngens(1)
>>> S = PolynomialRing(R, names=('x',)); (x,) = S._first_ngens(1)
>>> f = t**Integer(3)*x**Integer(2) + t**Integer(4)*x**Integer(3)
>>> f.derivative()
3*t^4*x^2 + 2*t^3*x
>>> f.derivative(x)
3*t^4*x^2 + 2*t^3*x
>>> f.derivative(t)
4*t^3*x^3 + 3*t^2*x^2
discriminant()[source]#

Return the discriminant of self.

The discriminant is

\[R_n := a_n^{2 n-2} \prod_{1<i<j<n} (r_i-r_j)^2,\]

where \(n\) is the degree of self, \(a_n\) is the leading coefficient of self, and the roots of self are \(r_1, \ldots, r_n\).

OUTPUT: An element of the base ring of the polynomial ring.

ALGORITHM:

Uses the identity \(R_n(f) := (-1)^{n (n-1)/2} R(f, f') a_n^{n-k-2}\), where \(n\) is the degree of self, \(a_n\) is the leading coefficient of self, \(f'\) is the derivative of \(f\), and \(k\) is the degree of \(f'\). 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                                               # needs sage.libs.pari
-31
sage: d.parent() is QQ                                                      # needs sage.libs.pari
True
sage: EllipticCurve([1, 1]).discriminant()/16                               # needs sage.libs.pari sage.schemes
-31
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(3) + x + Integer(1)
>>> d = f.discriminant(); d                                               # needs sage.libs.pari
-31
>>> d.parent() is QQ                                                      # needs sage.libs.pari
True
>>> EllipticCurve([Integer(1), Integer(1)]).discriminant()/Integer(16)                               # needs sage.libs.pari sage.schemes
-31
sage: R.<x> = QQ[]
sage: f = 2*x^3 + x + 1
sage: d = f.discriminant(); d                                               # needs sage.libs.pari
-116
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = Integer(2)*x**Integer(3) + x + Integer(1)
>>> d = f.discriminant(); d                                               # needs sage.libs.pari
-116

We can compute discriminants over univariate and multivariate polynomial rings:

sage: R.<a> = QQ[]
sage: S.<x> = R[]
sage: f = a*x + x + a + 1
sage: d = f.discriminant(); d                                               # needs sage.libs.pari
1
sage: d.parent() is R                                                       # needs sage.libs.pari
True
>>> from sage.all import *
>>> R = QQ['a']; (a,) = R._first_ngens(1)
>>> S = R['x']; (x,) = S._first_ngens(1)
>>> f = a*x + x + a + Integer(1)
>>> d = f.discriminant(); d                                               # needs sage.libs.pari
1
>>> d.parent() is R                                                       # needs sage.libs.pari
True
sage: R.<a, b> = QQ[]
sage: S.<x> = R[]
sage: f = x^2 + a + b
sage: d = f.discriminant(); d                                               # needs sage.libs.pari
-4*a - 4*b
sage: d.parent() is R                                                       # needs sage.libs.pari
True
>>> from sage.all import *
>>> R = QQ['a, b']; (a, b,) = R._first_ngens(2)
>>> S = R['x']; (x,) = S._first_ngens(1)
>>> f = x**Integer(2) + a + b
>>> d = f.discriminant(); d                                               # needs sage.libs.pari
-4*a - 4*b
>>> d.parent() is R                                                       # needs sage.libs.pari
True
dispersion(other=None)[source]#

Compute the dispersion of a pair of polynomials.

The dispersion of \(f\) and \(g\) is the largest nonnegative integer \(n\) such that \(f(x + n)\) and \(g(x)\) have a nonconstant common factor.

When other is None, compute the auto-dispersion of self, i.e., its dispersion with itself.

See also

dispersion_set()

EXAMPLES:

sage: Pol.<x> = QQ[]
sage: x.dispersion(x + 1)                                                   # needs sage.libs.pari
1
sage: (x + 1).dispersion(x)                                                 # needs sage.libs.pari
-Infinity

sage: # needs sage.libs.pari sage.rings.number_field sage.symbolic
sage: Pol.<x> = QQbar[]
sage: pol = Pol([sqrt(5), 1, 3/2])
sage: pol.dispersion()
0
sage: (pol*pol(x+3)).dispersion()
3
>>> from sage.all import *
>>> Pol = QQ['x']; (x,) = Pol._first_ngens(1)
>>> x.dispersion(x + Integer(1))                                                   # needs sage.libs.pari
1
>>> (x + Integer(1)).dispersion(x)                                                 # needs sage.libs.pari
-Infinity

>>> # needs sage.libs.pari sage.rings.number_field sage.symbolic
>>> Pol = QQbar['x']; (x,) = Pol._first_ngens(1)
>>> pol = Pol([sqrt(Integer(5)), Integer(1), Integer(3)/Integer(2)])
>>> pol.dispersion()
0
>>> (pol*pol(x+Integer(3))).dispersion()
3
dispersion_set(other=None)[source]#

Compute the dispersion set of two polynomials.

The dispersion set of \(f\) and \(g\) is the set of nonnegative integers \(n\) such that \(f(x + n)\) and \(g(x)\) have a nonconstant common factor.

When other is None, compute the auto-dispersion set of self, i.e., its dispersion set with itself.

ALGORITHM:

See Section 4 of Man & Wright [MW1994].

See also

dispersion()

EXAMPLES:

sage: Pol.<x> = QQ[]
sage: x.dispersion_set(x + 1)                                               # needs sage.libs.pari
[1]
sage: (x + 1).dispersion_set(x)                                             # needs sage.libs.pari
[]

sage: pol = x^3 + x - 7
sage: (pol*pol(x+3)^2).dispersion_set()                                     # needs sage.libs.pari
[0, 3]
>>> from sage.all import *
>>> Pol = QQ['x']; (x,) = Pol._first_ngens(1)
>>> x.dispersion_set(x + Integer(1))                                               # needs sage.libs.pari
[1]
>>> (x + Integer(1)).dispersion_set(x)                                             # needs sage.libs.pari
[]

>>> pol = x**Integer(3) + x - Integer(7)
>>> (pol*pol(x+Integer(3))**Integer(2)).dispersion_set()                                     # needs sage.libs.pari
[0, 3]
divides(p)[source]#

Return True if this polynomial divides \(p\).

This method is only implemented for polynomials over an integral domain.

EXAMPLES:

sage: R.<x> = ZZ[]
sage: (2*x + 1).divides(4*x**2 - 1)
True
sage: (2*x + 1).divides(4*x**2 + 1)
False
sage: (2*x + 1).divides(R(0))
True
sage: R(0).divides(2*x + 1)
False
sage: R(0).divides(R(0))
True
sage: S.<y> = R[]
sage: p = x * y**2 + (2*x + 1) * y + x + 1
sage: q = (x + 1) * y + (3*x + 2)
sage: q.divides(p)
False
sage: q.divides(p * q)
True
sage: R.<x> = Zmod(6)[]
sage: p = 4*x + 3
sage: q = 5*x**2 + x + 2
sage: q.divides(p)
False
sage: p.divides(q)
False
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> (Integer(2)*x + Integer(1)).divides(Integer(4)*x**Integer(2) - Integer(1))
True
>>> (Integer(2)*x + Integer(1)).divides(Integer(4)*x**Integer(2) + Integer(1))
False
>>> (Integer(2)*x + Integer(1)).divides(R(Integer(0)))
True
>>> R(Integer(0)).divides(Integer(2)*x + Integer(1))
False
>>> R(Integer(0)).divides(R(Integer(0)))
True
>>> S = R['y']; (y,) = S._first_ngens(1)
>>> p = x * y**Integer(2) + (Integer(2)*x + Integer(1)) * y + x + Integer(1)
>>> q = (x + Integer(1)) * y + (Integer(3)*x + Integer(2))
>>> q.divides(p)
False
>>> q.divides(p * q)
True
>>> R = Zmod(Integer(6))['x']; (x,) = R._first_ngens(1)
>>> p = Integer(4)*x + Integer(3)
>>> q = Integer(5)*x**Integer(2) + x + Integer(2)
>>> q.divides(p)
False
>>> p.divides(q)
False
euclidean_degree()[source]#

Return the degree of this element as an element of an 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
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> x.euclidean_degree()
1
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> x.euclidean_degree()
Traceback (most recent call last):
...
NotImplementedError
exponents()[source]#

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]
>>> from sage.all import *
>>> _ = PolynomialRing(ZZ, names=('x',)); (x,) = _._first_ngens(1)
>>> f = x**Integer(4) + Integer(2)*x**Integer(2) + Integer(1)
>>> f.exponents()
[0, 2, 4]
factor(**kwargs)[source]#

Return the factorization of self over its base ring.

INPUT:

  • kwargs – any keyword arguments are passed to the method _factor_univariate_polynomial() of the base ring if it defines such a method.

OUTPUT:

A factorization of self over its parent into a unit and irreducible factors. If the parent is a polynomial ring over a field, these factors are monic.

EXAMPLES:

Factorization is implemented over various rings. Over \(\QQ\):

sage: x = QQ['x'].0
sage: f = (x^3 - 1)^2
sage: f.factor()                                                            # needs sage.libs.pari
(x - 1)^2 * (x^2 + x + 1)^2
>>> from sage.all import *
>>> x = QQ['x'].gen(0)
>>> f = (x**Integer(3) - Integer(1))**Integer(2)
>>> f.factor()                                                            # needs sage.libs.pari
(x - 1)^2 * (x^2 + x + 1)^2

Since \(\QQ\) is a field, the irreducible factors are monic:

sage: f = 10*x^5 - 1
sage: f.factor()                                                            # needs sage.libs.pari
(10) * (x^5 - 1/10)
sage: f = 10*x^5 - 10
sage: f.factor()                                                            # needs sage.libs.pari
(10) * (x - 1) * (x^4 + x^3 + x^2 + x + 1)
>>> from sage.all import *
>>> f = Integer(10)*x**Integer(5) - Integer(1)
>>> f.factor()                                                            # needs sage.libs.pari
(10) * (x^5 - 1/10)
>>> f = Integer(10)*x**Integer(5) - Integer(10)
>>> f.factor()                                                            # needs sage.libs.pari
(10) * (x - 1) * (x^4 + x^3 + x^2 + x + 1)

Over \(\ZZ\) the irreducible factors need not be monic:

sage: x = ZZ['x'].0
sage: f = 10*x^5 - 1
sage: f.factor()                                                            # needs sage.libs.pari
10*x^5 - 1
>>> from sage.all import *
>>> x = ZZ['x'].gen(0)
>>> f = Integer(10)*x**Integer(5) - Integer(1)
>>> f.factor()                                                            # needs sage.libs.pari
10*x^5 - 1

We factor a non-monic polynomial over a finite field of 25 elements:

sage: # needs sage.rings.finite_rings
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)
>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> k = GF(Integer(25), names=('a',)); (a,) = k._first_ngens(1)
>>> R = k['x']; (x,) = R._first_ngens(1)
>>> f = Integer(2)*x**Integer(10) + Integer(2)*x + Integer(2)*a
>>> 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 \(F\) back out:

sage: expand(F)                                                             # needs sage.rings.finite_rings sage.symbolic
2*x^10 + 2*x + 2*a
>>> from sage.all import *
>>> expand(F)                                                             # needs sage.rings.finite_rings sage.symbolic
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: # needs sage.libs.ntl
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: def my_factor(f):
....:     return f.change_ring(ZZ).factor()
sage: R.base_ring()._factor_univariate_polynomial = my_factor
sage: (x^2).factor()                                                       # needs sage.libs.pari
x^2
sage: del R.base_ring()._factor_univariate_polynomial  # clean up
>>> from sage.all import *
>>> # needs sage.libs.ntl
>>> R = PolynomialRing(IntegerModRing(Integer(4)), implementation="NTL", names=('x',)); (x,) = R._first_ngens(1)
>>> (x**Integer(2)).factor()
Traceback (most recent call last):
...
NotImplementedError: factorization of polynomials over rings with
composite characteristic is not implemented
>>> def my_factor(f):
...     return f.change_ring(ZZ).factor()
>>> R.base_ring()._factor_univariate_polynomial = my_factor
>>> (x**Integer(2)).factor()                                                       # needs sage.libs.pari
x^2
>>> del R.base_ring()._factor_univariate_polynomial  # clean up

Arbitrary precision real and complex factorization:

sage: # needs sage.libs.pari sage.rings.real_mpfr
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: # needs sage.libs.pari sage.rings.real_mpfr
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
>>> from sage.all import *
>>> # needs sage.libs.pari sage.rings.real_mpfr
>>> R = RealField(Integer(100))['x']; (x,) = R._first_ngens(1)
>>> F = factor(x**Integer(2) - Integer(3)); F
(x - 1.7320508075688772935274463415) * (x + 1.7320508075688772935274463415)
>>> expand(F)
x^2 - 3.0000000000000000000000000000
>>> factor(x**Integer(2) + Integer(1))
x^2 + 1.0000000000000000000000000000

>>> # needs sage.libs.pari sage.rings.real_mpfr
>>> R = ComplexField(Integer(100))['x']; (x,) = R._first_ngens(1)
>>> F = factor(x**Integer(2) + Integer(3)); F
(x - 1.7320508075688772935274463415*I) * (x + 1.7320508075688772935274463415*I)
>>> expand(F)
x^2 + 3.0000000000000000000000000000
>>> factor(x**Integer(2) + Integer(1))
(x - I) * (x + I)
>>> f = R(I) * (x**Integer(2) + Integer(1)) ; f
I*x^2 + I
>>> F = factor(f); F
(1.0000000000000000000000000000*I) * (x - I) * (x + I)
>>> expand(F)
I*x^2 + I

Over a number field:

sage: # needs sage.rings.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
>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> K = CyclotomicField(Integer(15), names=('z',)); (z,) = K._first_ngens(1)
>>> x = polygen(K)
>>> ((x**Integer(3) + z*x + Integer(1))**Integer(3) * (x - z)).factor()
(x - z) * (x^3 + z*x + 1)^3
>>> cyclotomic_polynomial(Integer(12)).change_ring(K).factor()
(x^2 - z^5 - 1) * (x^2 + z^5)
>>> ((x**Integer(3) + z*x + Integer(1))**Integer(3) * (x/(z+Integer(2)) - Integer(1)/Integer(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: # needs sage.rings.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)
>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> x = polygen(QQ)
>>> K = CyclotomicField(Integer(3), names=('z',)); (z,) = K._first_ngens(1)
>>> L = K.extension(x**Integer(3) - Integer(2), names=('a',)); (a,) = L._first_ngens(1)
>>> t = polygen(L, 't')
>>> f = (t**Integer(3) + t + a) * (t**Integer(5) + t + z); f
t^8 + t^6 + a*t^5 + t^4 + z*t^3 + t^2 + (a + z)*t + z*a
>>> f.factor()
(t^3 + t + a) * (t^5 + t + z)

Over the real double field:

sage: # needs numpy
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)
>>> from sage.all import *
>>> # needs numpy
>>> R = RDF['x']; (x,) = R._first_ngens(1)
>>> (-Integer(2)*x**Integer(2) - Integer(1)).factor()
(-2.0) * (x^2 + 0.5000000000000001)
>>> (-Integer(2)*x**Integer(2) - Integer(1)).factor().expand()
-2.0*x^2 - 1.0000000000000002
>>> f = (x - Integer(1))**Integer(3)
>>> 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                                             # needs numpy
[(1.0000065719436413, 1)]
>>> from sage.all import *
>>> f.roots()  # abs tol 2e-5                                             # needs numpy
[(1.0000065719436413, 1)]

Over the complex double field the factors are approximate and therefore occur with multiplicity 1:

sage: # needs numpy sage.rings.complex_double
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]
>>> from sage.all import *
>>> # needs numpy sage.rings.complex_double
>>> R = CDF['x']; (x,) = R._first_ngens(1)
>>> f = (x**Integer(2) + Integer(2)*R(I))**Integer(3)
>>> F = f.factor()
>>> 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)
>>> [f(t[Integer(0)][Integer(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 \(\ZZ/n\ZZ\) for composite \(n\) 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
>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(35)), names=('x',)); (x,) = R._first_ngens(1)
>>> f = (x**Integer(2) + Integer(2)*x + Integer(2)) * (x**Integer(2) + Integer(3)*x + Integer(9))
>>> 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 Issue #8544):

sage: R.<x> = QQbar[]                                                       # needs sage.rings.number_field
sage: (x^8 - 1).factor()                                                    # needs sage.rings.number_field
(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)
>>> from sage.all import *
>>> R = QQbar['x']; (x,) = R._first_ngens(1)# needs sage.rings.number_field
>>> (x**Integer(8) - Integer(1)).factor()                                                    # needs sage.rings.number_field
(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 Issue #8544):

sage: R.<x> = AA[]                                                          # needs sage.rings.number_field
sage: (x^8 + 1).factor()                                                    # needs sage.rings.number_field
(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?)
>>> from sage.all import *
>>> R = AA['x']; (x,) = R._first_ngens(1)# needs sage.rings.number_field
>>> (x**Integer(8) + Integer(1)).factor()                                                    # needs sage.rings.number_field
(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?)
gcd(other)[source]#

Return 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. If the base ring is a field, the return value is 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
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> (Integer(2)*x**Integer(2)).gcd(Integer(2)*x)
x
>>> R.zero().gcd(Integer(0))
0
>>> (Integer(2)*x).gcd(Integer(0))
x

One can easily add gcd functionality to new rings by providing a method _gcd_univariate_polynomial:

sage: # needs sage.rings.number_field sage.symbolic
sage: O = ZZ[-sqrt(5)]
sage: R.<x> = O[]
sage: a = O.1
sage: p = x + a
sage: q = x^2 - 5
sage: p.gcd(q)
Traceback (most recent call last):
...
NotImplementedError: Order of conductor 2 generated by a in Number
Field in a with defining polynomial x^2 - 5 with a = -2.236067977499790?
does not provide a gcd implementation for univariate polynomials
sage: S.<x> = O.number_field()[]
sage: O._gcd_univariate_polynomial = lambda f, g: R(S(f).gcd(S(g)))
sage: p.gcd(q)
x + a
sage: del O._gcd_univariate_polynomial
>>> from sage.all import *
>>> # needs sage.rings.number_field sage.symbolic
>>> O = ZZ[-sqrt(Integer(5))]
>>> R = O['x']; (x,) = R._first_ngens(1)
>>> a = O.gen(1)
>>> p = x + a
>>> q = x**Integer(2) - Integer(5)
>>> p.gcd(q)
Traceback (most recent call last):
...
NotImplementedError: Order of conductor 2 generated by a in Number
Field in a with defining polynomial x^2 - 5 with a = -2.236067977499790?
does not provide a gcd implementation for univariate polynomials
>>> S = O.number_field()['x']; (x,) = S._first_ngens(1)
>>> O._gcd_univariate_polynomial = lambda f, g: R(S(f).gcd(S(g)))
>>> p.gcd(q)
x + a
>>> del O._gcd_univariate_polynomial

Use multivariate implementation for polynomials over polynomials rings:

sage: R.<x> = ZZ[]
sage: S.<y> = R[]
sage: T.<z> = S[]
sage: r = 2*x*y + z
sage: p = r * (3*x*y*z - 1)
sage: q = r * (x + y + z - 2)
sage: p.gcd(q)                                                              # needs sage.libs.singular
z + 2*x*y

sage: R.<x> = QQ[]
sage: S.<y> = R[]
sage: r = 2*x*y + 1
sage: p = r * (x - 1/2 * y)
sage: q = r * (x*y^2 - x + 1/3)
sage: p.gcd(q)                                                              # needs sage.libs.singular
2*x*y + 1
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> S = R['y']; (y,) = S._first_ngens(1)
>>> T = S['z']; (z,) = T._first_ngens(1)
>>> r = Integer(2)*x*y + z
>>> p = r * (Integer(3)*x*y*z - Integer(1))
>>> q = r * (x + y + z - Integer(2))
>>> p.gcd(q)                                                              # needs sage.libs.singular
z + 2*x*y

>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> S = R['y']; (y,) = S._first_ngens(1)
>>> r = Integer(2)*x*y + Integer(1)
>>> p = r * (x - Integer(1)/Integer(2) * y)
>>> q = r * (x*y**Integer(2) - x + Integer(1)/Integer(3))
>>> p.gcd(q)                                                              # needs sage.libs.singular
2*x*y + 1
global_height(prec=None)[source]#

Return the (projective) global height of the polynomial.

This returns the absolute logarithmic height of the coefficients thought of as a projective point.

INPUT:

  • prec – desired floating point precision (default: default RealField precision).

OUTPUT: a real number.

EXAMPLES:

sage: R.<x> = PolynomialRing(QQ)
sage: f = 3*x^3 + 2*x^2 + x
sage: exp(f.global_height())                                                # needs sage.symbolic
3.00000000000000
>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> f = Integer(3)*x**Integer(3) + Integer(2)*x**Integer(2) + x
>>> exp(f.global_height())                                                # needs sage.symbolic
3.00000000000000

Scaling should not change the result:

sage: R.<x> = PolynomialRing(QQ)
sage: f = 1/25*x^2 + 25/3*x + 1
sage: f.global_height()                                                     # needs sage.symbolic
6.43775164973640
sage: g = 100 * f
sage: g.global_height()                                                     # needs sage.symbolic
6.43775164973640
>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> f = Integer(1)/Integer(25)*x**Integer(2) + Integer(25)/Integer(3)*x + Integer(1)
>>> f.global_height()                                                     # needs sage.symbolic
6.43775164973640
>>> g = Integer(100) * f
>>> g.global_height()                                                     # needs sage.symbolic
6.43775164973640
sage: R.<x> = PolynomialRing(QQbar)                                         # needs sage.rings.number_field
sage: f = QQbar(i)*x^2 + 3*x                                                # needs sage.rings.number_field
sage: f.global_height()                                                     # needs sage.rings.number_field
1.09861228866811
>>> from sage.all import *
>>> R = PolynomialRing(QQbar, names=('x',)); (x,) = R._first_ngens(1)# needs sage.rings.number_field
>>> f = QQbar(i)*x**Integer(2) + Integer(3)*x                                                # needs sage.rings.number_field
>>> f.global_height()                                                     # needs sage.rings.number_field
1.09861228866811
sage: # needs sage.rings.number_field
sage: R.<x> = PolynomialRing(QQ)
sage: K.<k> = NumberField(x^2 + 5)
sage: T.<t> = PolynomialRing(K)
sage: f = 1/1331 * t^2 + 5 * t + 7
sage: f.global_height()
9.13959596745043
>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> K = NumberField(x**Integer(2) + Integer(5), names=('k',)); (k,) = K._first_ngens(1)
>>> T = PolynomialRing(K, names=('t',)); (t,) = T._first_ngens(1)
>>> f = Integer(1)/Integer(1331) * t**Integer(2) + Integer(5) * t + Integer(7)
>>> f.global_height()
9.13959596745043
sage: R.<x> = QQ[]
sage: f = 1/123*x^2 + 12
sage: f.global_height(prec=2)                                               # needs sage.symbolic
8.0
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = Integer(1)/Integer(123)*x**Integer(2) + Integer(12)
>>> f.global_height(prec=Integer(2))                                               # needs sage.symbolic
8.0
sage: R.<x> = QQ[]
sage: f = 0*x
sage: f.global_height()                                                     # needs sage.rings.real_mpfr
0.000000000000000
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = Integer(0)*x
>>> f.global_height()                                                     # needs sage.rings.real_mpfr
0.000000000000000
gradient()[source]#

Return a list of the partial derivative of self with respect to the variable of this univariate polynomial.

There is only one partial derivative.

EXAMPLES:

sage: P.<x> = QQ[]
sage: f = x^2 + (2/3)*x + 1
sage: f.gradient()
[2*x + 2/3]
sage: f = P(1)
sage: f.gradient()
[0]
>>> from sage.all import *
>>> P = QQ['x']; (x,) = P._first_ngens(1)
>>> f = x**Integer(2) + (Integer(2)/Integer(3))*x + Integer(1)
>>> f.gradient()
[2*x + 2/3]
>>> f = P(Integer(1))
>>> f.gradient()
[0]
hamming_weight()[source]#

Return the number of non-zero coefficients of self.

Also called weight, Hamming weight or sparsity.

EXAMPLES:

sage: R.<x> = ZZ[]
sage: f = x^3 - x
sage: f.number_of_terms()
2
sage: R(0).number_of_terms()
0
sage: f = (x + 1)^100
sage: f.number_of_terms()
101
sage: S = GF(5)['y']
sage: S(f).number_of_terms()
5
sage: cyclotomic_polynomial(105).number_of_terms()
33
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(3) - x
>>> f.number_of_terms()
2
>>> R(Integer(0)).number_of_terms()
0
>>> f = (x + Integer(1))**Integer(100)
>>> f.number_of_terms()
101
>>> S = GF(Integer(5))['y']
>>> S(f).number_of_terms()
5
>>> cyclotomic_polynomial(Integer(105)).number_of_terms()
33

The method hamming_weight() is an alias:

sage: f.hamming_weight()
101
>>> from sage.all import *
>>> f.hamming_weight()
101
has_cyclotomic_factor()[source]#

Return True if the given polynomial has a nontrivial cyclotomic factor.

The algorithm assumes that the polynomial has rational coefficients.

If the polynomial is known to be irreducible, it may be slightly more efficient to call is_cyclotomic() instead.

EXAMPLES:

sage: pol.<x> = PolynomialRing(Rationals())
sage: u = x^5 - 1; u.has_cyclotomic_factor()
True
sage: u = x^5 - 2; u.has_cyclotomic_factor()
False
sage: u = pol(cyclotomic_polynomial(7)) * pol.random_element()  # random
sage: u.has_cyclotomic_factor()                                 # random
True
>>> from sage.all import *
>>> pol = PolynomialRing(Rationals(), names=('x',)); (x,) = pol._first_ngens(1)
>>> u = x**Integer(5) - Integer(1); u.has_cyclotomic_factor()
True
>>> u = x**Integer(5) - Integer(2); u.has_cyclotomic_factor()
False
>>> u = pol(cyclotomic_polynomial(Integer(7))) * pol.random_element()  # random
>>> u.has_cyclotomic_factor()                                 # random
True
homogenize(var='h')[source]#

Return the homogenization of this polynomial.

The polynomial itself is returned if it is homogeneous already. Otherwise, its monomials are multiplied with the smallest powers of var such that they all have the same total degree.

INPUT:

  • var – a variable in the polynomial ring (as a string, an element of the ring, or 0) or a name for a new variable (default: 'h')

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
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(2) + Integer(1)
>>> 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
>>> from sage.all import *
>>> g = f.homogenize('z'); g
x^2 + z^2
>>> 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
>>> from sage.all import *
>>> f = x**Integer(2)
>>> g = f.homogenize('z'); g
x^2
>>> 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
>>> from sage.all import *
>>> f = x**Integer(2) + x + Integer(1)
>>> f.homogenize('x')
3*x^2

In positive characteristic, the degree can drop in this case:

sage: R.<x> = GF(2)[]
sage: f = x + 1
sage: f.homogenize(x)
0
>>> from sage.all import *
>>> R = GF(Integer(2))['x']; (x,) = R._first_ngens(1)
>>> f = x + Integer(1)
>>> 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
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(2) + x + Integer(1)
>>> f.homogenize(Integer(0))
3*x^2
integral(var=None)[source]#

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 that the constant term is 0.

EXAMPLES:

sage: R.<x> = ZZ[]
sage: R(0).integral()
0
sage: f = R(2).integral(); f
2*x
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> R(Integer(0)).integral()
0
>>> f = R(Integer(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
>>> from sage.all import *
>>> f.parent()
Univariate Polynomial Ring in x over Rational Field
>>> R(Integer(0)).integral().parent()
Univariate Polynomial Ring in x over Rational Field

>>> f = x**Integer(3) + x - Integer(2)
>>> g = f.integral(); g
1/4*x^4 + 1/2*x^2 - 2*x
>>> g.parent()
Univariate Polynomial Ring in x over Rational Field

This shows that the issue at Issue #7711 is resolved:

sage: # needs sage.rings.finite_rings
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: # needs sage.rings.finite_rings
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
>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> P = PolynomialRing(GF(Integer(2147483647)), names=('x', 'z',)); (x, z,) = P._first_ngens(2)
>>> Q = PolynomialRing(P, names=('y',)); (y,) = Q._first_ngens(1)
>>> p = x + y + z
>>> p.integral()
-1073741823*y^2 + (x + z)*y

>>> # needs sage.rings.finite_rings
>>> P = PolynomialRing(GF(next_prime(Integer(2147483647))), names=('x', 'z',)); (x, z,) = P._first_ngens(2)
>>> Q = PolynomialRing(P, names=('y',)); (y,) = Q._first_ngens(1)
>>> p = x + y + z
>>> 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
>>> from sage.all import *
>>> A = PolynomialRing(ZZ, names=('a1', 'a2',)); (a1, a2,) = A._first_ngens(2)
>>> B = PolynomialRing(A, names=('b',)); (b,) = B._first_ngens(1)
>>> C = PowerSeriesRing(B, names=('c',)); (c,) = C._first_ngens(1)
>>> R = PolynomialRing(C, names=('x',)); (x,) = R._first_ngens(1)
>>> f = a2*x**Integer(2) + c*x - a1*b
>>> 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
>>> f.integral()
1/3*a2*x^3 + 1/2*c*x^2 - a1*b*x
>>> 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
>>> g = Integer(3)*a2*x**Integer(2) + Integer(2)*c*x - a1*b
>>> g.integral()
a2*x^3 + c*x^2 - a1*b*x
>>> 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
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> t = PolynomialRing(R,'t').gen()
>>> f = x*t + Integer(5)*t**Integer(2)
>>> f.integral(x)
5*x*t^2 + 1/2*x^2*t
inverse_mod(a, m)[source]#

Invert the polynomial a with respect to m, or raise 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).

See also

If you are only interested in the inverse modulo a monomial \(x^k\) then you might use the specialized method inverse_series_trunc() which is much faster.

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
>>> from sage.all import *
>>> S = QQ['t']; (t,) = S._first_ngens(1)
>>> f = inverse_mod(t**Integer(2) + Integer(1), t**Integer(3) + Integer(1)); f
-1/2*t^2 - 1/2*t + 1/2
>>> f * (t**Integer(2) + Integer(1)) % (t**Integer(3) + Integer(1))
1
>>> f = t.inverse_mod((t + Integer(1))**Integer(7)); f
-t^6 - 7*t^5 - 21*t^4 - 35*t^3 - 35*t^2 - 21*t - 7
>>> (f * t) + (t + Integer(1))**Integer(7)
1
>>> t.inverse_mod(S.ideal((t + Integer(1))**Integer(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: # needs scipy sage.modules
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  # abs tol 1e-14
....:               for c in poly.coefficients(sparse=False)])
1.0000000000000004
>>> from sage.all import *
>>> # needs scipy sage.modules
>>> R = RDF['x']; (x,) = R._first_ngens(1)
>>> epsilon = RDF(Integer(1)).ulp()*Integer(50)   # Allow an error of up to 50 ulp
>>> f = inverse_mod(x**Integer(2) + Integer(1), x**Integer(5) + x + Integer(1)); f  # abs tol 1e-14
0.4*x^4 - 0.2*x^3 - 0.4*x^2 + 0.2*x + 0.8
>>> poly = f * (x**Integer(2) + Integer(1)) % (x**Integer(5) + x + Integer(1))
>>> # Remove noisy zero terms:
>>> parent(poly)([RealNumber('0.0') if abs(c) <= epsilon else c
...               for c in poly.coefficients(sparse=False)])
1.0
>>> f = inverse_mod(x**Integer(3) - x + Integer(1), x - Integer(2)); f
0.14285714285714285
>>> f * (x**Integer(3) - x + Integer(1)) % (x - Integer(2))
1.0
>>> g = Integer(5)*x**Integer(3) + x - Integer(7); m = x**Integer(4) - Integer(12)*x + Integer(13); f = inverse_mod(g, m); f
-0.0319636125...*x^3 - 0.0383269759...*x^2 - 0.0463050900...*x + 0.346479687...
>>> poly = f*g % m
>>> # Remove noisy zero terms:
>>> parent(poly)([RealNumber('0.0') if abs(c) <= epsilon else c  # abs tol 1e-14
...               for c in poly.coefficients(sparse=False)])
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:

  • Robert Bradshaw (2007-05-31)

inverse_of_unit()[source]#

EXAMPLES:

sage: R.<x> = QQ[]
sage: f = x - 90283
sage: f.inverse_of_unit()
Traceback (most recent call last):
...
ArithmeticError: x - 90283 is not a unit
in Univariate Polynomial Ring in x over Rational Field
sage: f = R(-90283); g = f.inverse_of_unit(); g
-1/90283
sage: parent(g)
Univariate Polynomial Ring in x over Rational Field
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = x - Integer(90283)
>>> f.inverse_of_unit()
Traceback (most recent call last):
...
ArithmeticError: x - 90283 is not a unit
in Univariate Polynomial Ring in x over Rational Field
>>> f = R(-Integer(90283)); g = f.inverse_of_unit(); g
-1/90283
>>> parent(g)
Univariate Polynomial Ring in x over Rational Field
inverse_series_trunc(prec)[source]#

Return a polynomial approximation of precision prec of the inverse series of this polynomial.

See also

The method inverse_mod() allows more generally to invert this polynomial with respect to any ideal.

EXAMPLES:

sage: x = polygen(ZZ)
sage: s = (1 + x).inverse_series_trunc(5)
sage: s
x^4 - x^3 + x^2 - x + 1
sage: s * (1 + x)
x^5 + 1
>>> from sage.all import *
>>> x = polygen(ZZ)
>>> s = (Integer(1) + x).inverse_series_trunc(Integer(5))
>>> s
x^4 - x^3 + x^2 - x + 1
>>> s * (Integer(1) + x)
x^5 + 1

Note that the constant coefficient needs to be a unit:

sage: ZZx.<x> = ZZ[]
sage: ZZxy.<y> = ZZx[]
sage: (1+x + y**2).inverse_series_trunc(4)
Traceback (most recent call last):
...
ValueError: constant term x + 1 is not a unit
sage: (1+x + y**2).change_ring(ZZx.fraction_field()).inverse_series_trunc(4)
(-1/(x^2 + 2*x + 1))*y^2 + 1/(x + 1)
>>> from sage.all import *
>>> ZZx = ZZ['x']; (x,) = ZZx._first_ngens(1)
>>> ZZxy = ZZx['y']; (y,) = ZZxy._first_ngens(1)
>>> (Integer(1)+x + y**Integer(2)).inverse_series_trunc(Integer(4))
Traceback (most recent call last):
...
ValueError: constant term x + 1 is not a unit
>>> (Integer(1)+x + y**Integer(2)).change_ring(ZZx.fraction_field()).inverse_series_trunc(Integer(4))
(-1/(x^2 + 2*x + 1))*y^2 + 1/(x + 1)

The method works over any polynomial ring:

sage: R = Zmod(4)
sage: Rx.<x> = R[]
sage: Rxy.<y> = Rx[]

sage: p = 1 + (1+2*x)*y + x**2*y**4
sage: q = p.inverse_series_trunc(10)
sage: (p*q).truncate(11)
(2*x^4 + 3*x^2 + 3)*y^10 + 1
>>> from sage.all import *
>>> R = Zmod(Integer(4))
>>> Rx = R['x']; (x,) = Rx._first_ngens(1)
>>> Rxy = Rx['y']; (y,) = Rxy._first_ngens(1)

>>> p = Integer(1) + (Integer(1)+Integer(2)*x)*y + x**Integer(2)*y**Integer(4)
>>> q = p.inverse_series_trunc(Integer(10))
>>> (p*q).truncate(Integer(11))
(2*x^4 + 3*x^2 + 3)*y^10 + 1

Even noncommutative ones:

sage: # needs sage.modules
sage: M = MatrixSpace(ZZ, 2)
sage: x = polygen(M)
sage: p = M([1,2,3,4])*x^3 + M([-1,0,0,1])*x^2 + M([1,3,-1,0])*x + M.one()
sage: q = p.inverse_series_trunc(5)
sage: (p*q).truncate(5) == M.one()
True
sage: q = p.inverse_series_trunc(13)
sage: (p*q).truncate(13) == M.one()
True
>>> from sage.all import *
>>> # needs sage.modules
>>> M = MatrixSpace(ZZ, Integer(2))
>>> x = polygen(M)
>>> p = M([Integer(1),Integer(2),Integer(3),Integer(4)])*x**Integer(3) + M([-Integer(1),Integer(0),Integer(0),Integer(1)])*x**Integer(2) + M([Integer(1),Integer(3),-Integer(1),Integer(0)])*x + M.one()
>>> q = p.inverse_series_trunc(Integer(5))
>>> (p*q).truncate(Integer(5)) == M.one()
True
>>> q = p.inverse_series_trunc(Integer(13))
>>> (p*q).truncate(Integer(13)) == M.one()
True

AUTHORS:

  • David Harvey (2006-09-09): Newton’s method implementation for power series

  • Vincent Delecroix (2014-2015): move the implementation directly in polynomial

is_constant()[source]#

Return True if this is a constant polynomial.

OUTPUT:

  • boolTrue if and only if this polynomial is constant

EXAMPLES:

sage: R.<x> = ZZ[]
sage: x.is_constant()
False
sage: R(2).is_constant()
True
sage: R(0).is_constant()
True
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> x.is_constant()
False
>>> R(Integer(2)).is_constant()
True
>>> R(Integer(0)).is_constant()
True
is_cyclotomic(certificate=False, algorithm='pari')[source]#

Test if this polynomial is a cyclotomic polynomial.

A cyclotomic polynomial is a monic, irreducible polynomial such that all roots are roots of unity.

By default the answer is a boolean. But if certificate is True, the result is a non-negative integer: it is 0 if self is not cyclotomic, and a positive integer n if self is the \(n\)-th cyclotomic polynomial.

INPUT:

  • certificate – boolean, default to False. Only works with algorithm set to "pari".

  • algorithm – either "pari" or "sage" (default is "pari")

ALGORITHM:

The native algorithm implemented in Sage uses the first algorithm of [BD1989]. The algorithm in PARI (using pari:poliscyclo) is more subtle since it does compute the inverse of the Euler \(\phi\) function to determine the \(n\) such that the polynomial is the \(n\)-th cyclotomic polynomial.

EXAMPLES:

Quick tests:

sage: # needs sage.libs.pari
sage: P.<x> = ZZ['x']
sage: (x - 1).is_cyclotomic()
True
sage: (x + 1).is_cyclotomic()
True
sage: (x^2 - 1).is_cyclotomic()
False
sage: (x^2 + x + 1).is_cyclotomic(certificate=True)
3
sage: (x^2 + 2*x + 1).is_cyclotomic(certificate=True)
0
>>> from sage.all import *
>>> # needs sage.libs.pari
>>> P = ZZ['x']; (x,) = P._first_ngens(1)
>>> (x - Integer(1)).is_cyclotomic()
True
>>> (x + Integer(1)).is_cyclotomic()
True
>>> (x**Integer(2) - Integer(1)).is_cyclotomic()
False
>>> (x**Integer(2) + x + Integer(1)).is_cyclotomic(certificate=True)
3
>>> (x**Integer(2) + Integer(2)*x + Integer(1)).is_cyclotomic(certificate=True)
0

Test first 100 cyclotomic polynomials:

sage: all(cyclotomic_polynomial(i).is_cyclotomic() for i in range(1, 101))  # needs sage.libs.pari
True
>>> from sage.all import *
>>> all(cyclotomic_polynomial(i).is_cyclotomic() for i in range(Integer(1), Integer(101)))  # needs sage.libs.pari
True

Some more tests:

sage: # needs sage.libs.pari
sage: f = x^16 + x^14 - x^10 + x^8 - x^6 + x^2 + 1
sage: f.is_cyclotomic(algorithm="pari")
False
sage: f.is_cyclotomic(algorithm="sage")
False
sage: g = x^16 + x^14 - x^10 - x^8 - x^6 + x^2 + 1
sage: g.is_cyclotomic(algorithm="pari")
True
sage: g.is_cyclotomic(algorithm="sage")
True

sage: y = polygen(QQ)
sage: (y/2 - 1/2).is_cyclotomic()
False
sage: (2*(y/2 - 1/2)).is_cyclotomic()                                       # needs sage.libs.pari
True
>>> from sage.all import *
>>> # needs sage.libs.pari
>>> f = x**Integer(16) + x**Integer(14) - x**Integer(10) + x**Integer(8) - x**Integer(6) + x**Integer(2) + Integer(1)
>>> f.is_cyclotomic(algorithm="pari")
False
>>> f.is_cyclotomic(algorithm="sage")
False
>>> g = x**Integer(16) + x**Integer(14) - x**Integer(10) - x**Integer(8) - x**Integer(6) + x**Integer(2) + Integer(1)
>>> g.is_cyclotomic(algorithm="pari")
True
>>> g.is_cyclotomic(algorithm="sage")
True

>>> y = polygen(QQ)
>>> (y/Integer(2) - Integer(1)/Integer(2)).is_cyclotomic()
False
>>> (Integer(2)*(y/Integer(2) - Integer(1)/Integer(2))).is_cyclotomic()                                       # needs sage.libs.pari
True

Invalid arguments:

sage: (x - 3).is_cyclotomic(algorithm="sage", certificate=True)             # needs sage.libs.pari
Traceback (most recent call last):
...
ValueError: no implementation of the certificate within Sage
>>> from sage.all import *
>>> (x - Integer(3)).is_cyclotomic(algorithm="sage", certificate=True)             # needs sage.libs.pari
Traceback (most recent call last):
...
ValueError: no implementation of the certificate within Sage

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
>>> from sage.all import *
>>> z = polygen(GF(Integer(5)))
>>> (z - Integer(1)).is_cyclotomic()
Traceback (most recent call last):
...
NotImplementedError: not implemented in non-zero characteristic
is_cyclotomic_product()[source]#

Test whether this polynomial is a product of cyclotomic polynomials.

This method simply calls the function pari:poliscycloprod from the Pari library.

EXAMPLES:

sage: x = polygen(ZZ)
sage: (x^5 - 1).is_cyclotomic_product()                                     # needs sage.libs.pari
True
sage: (x^5 + x^4 - x^2 + 1).is_cyclotomic_product()                         # needs sage.libs.pari
False

sage: p = prod(cyclotomic_polynomial(i) for i in [2, 5, 7, 12])
sage: p.is_cyclotomic_product()                                             # needs sage.libs.pari
True

sage: (x^5 - 1/3).is_cyclotomic_product()
False

sage: x = polygen(Zmod(5))
sage: (x - 1).is_cyclotomic_product()
Traceback (most recent call last):
...
NotImplementedError: not implemented in non-zero characteristic
>>> from sage.all import *
>>> x = polygen(ZZ)
>>> (x**Integer(5) - Integer(1)).is_cyclotomic_product()                                     # needs sage.libs.pari
True
>>> (x**Integer(5) + x**Integer(4) - x**Integer(2) + Integer(1)).is_cyclotomic_product()                         # needs sage.libs.pari
False

>>> p = prod(cyclotomic_polynomial(i) for i in [Integer(2), Integer(5), Integer(7), Integer(12)])
>>> p.is_cyclotomic_product()                                             # needs sage.libs.pari
True

>>> (x**Integer(5) - Integer(1)/Integer(3)).is_cyclotomic_product()
False

>>> x = polygen(Zmod(Integer(5)))
>>> (x - Integer(1)).is_cyclotomic_product()
Traceback (most recent call last):
...
NotImplementedError: not implemented in non-zero characteristic
is_gen()[source]#

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
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> R(Integer(1)).is_gen()
False
>>> 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
>>> from sage.all import *
>>> f = R([Integer(0),Integer(1)]); f
x
>>> f.is_gen()
False
>>> f is x
False
>>> f == x
True
is_homogeneous()[source]#

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
>>> from sage.all import *
>>> P = PolynomialRing(QQ, names=('x',)); (x,) = P._first_ngens(1)
>>> x.is_homogeneous()
True
>>> P(Integer(0)).is_homogeneous()
True
>>> (x + Integer(1)).is_homogeneous()
False
is_irreducible()[source]#

Return whether this polynomial is irreducible.

EXAMPLES:

sage: R.<x> = ZZ[]
sage: (x^3 + 1).is_irreducible()                                            # needs sage.libs.pari
False
sage: (x^2 - 1).is_irreducible()                                            # needs sage.libs.pari
False
sage: (x^3 + 2).is_irreducible()                                            # needs sage.libs.pari
True
sage: R(0).is_irreducible()
False
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> (x**Integer(3) + Integer(1)).is_irreducible()                                            # needs sage.libs.pari
False
>>> (x**Integer(2) - Integer(1)).is_irreducible()                                            # needs sage.libs.pari
False
>>> (x**Integer(3) + Integer(2)).is_irreducible()                                            # needs sage.libs.pari
True
>>> R(Integer(0)).is_irreducible()
False

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()                                               # needs sage.libs.pari
False
sage: R.<x> = QQ[]
sage: R(2*x).is_irreducible()                                               # needs sage.libs.pari
True
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> R(Integer(2)*x).is_irreducible()                                               # needs sage.libs.pari
False
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> R(Integer(2)*x).is_irreducible()                                               # needs sage.libs.pari
True
is_lorentzian(explain=False)[source]#

Return True if this is a Lorentzian polynomial.

A univariate real polynomial is Lorentzian if and only if it is a monomial with positive coefficient, or zero. The definition is more involved for multivariate real polynomials.

INPUT:

  • explain – boolean (default: False); if True return a tuple whose first element is the boolean result of the test, and the second element is a string describing the reason the test failed, or None if the test succeeded

EXAMPLES:

sage: P.<x> = QQ[]
sage: p1 = x^2
sage: p1.is_lorentzian()
True
sage: p2 = 1 + x^2
sage: p2.is_lorentzian()
False
sage: p3 = P.zero()
sage: p3.is_lorentzian()
True
sage: p4 = -2*x^3
sage: p4.is_lorentzian()
False
>>> from sage.all import *
>>> P = QQ['x']; (x,) = P._first_ngens(1)
>>> p1 = x**Integer(2)
>>> p1.is_lorentzian()
True
>>> p2 = Integer(1) + x**Integer(2)
>>> p2.is_lorentzian()
False
>>> p3 = P.zero()
>>> p3.is_lorentzian()
True
>>> p4 = -Integer(2)*x**Integer(3)
>>> p4.is_lorentzian()
False

It is an error to check if a polynomial is Lorentzian if its base ring is not a subring of the real numbers, as the notion is not defined in this case:

sage: # needs sage.rings.real_mpfr
sage: Q.<y> = CC[]
sage: q = y^2
sage: q.is_lorentzian()
Traceback (most recent call last):
...
NotImplementedError: is_lorentzian only implemented for real polynomials
>>> from sage.all import *
>>> # needs sage.rings.real_mpfr
>>> Q = CC['y']; (y,) = Q._first_ngens(1)
>>> q = y**Integer(2)
>>> q.is_lorentzian()
Traceback (most recent call last):
...
NotImplementedError: is_lorentzian only implemented for real polynomials

The method can give a reason for a polynomial failing to be Lorentzian:

sage: p = x^2 + 2*x
sage: p.is_lorentzian(explain=True)
(False, 'inhomogeneous')
>>> from sage.all import *
>>> p = x**Integer(2) + Integer(2)*x
>>> p.is_lorentzian(explain=True)
(False, 'inhomogeneous')

REFERENCES:

For full definitions and related discussion, see [BrHu2019] and [HMMS2019].

is_monic()[source]#

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
>>> from sage.all import *
>>> x = QQ['x'].gen(0)
>>> f = x + Integer(33)
>>> f.is_monic()
True
>>> f = Integer(0)*x
>>> f.is_monic()
False
>>> f = Integer(3)*x**Integer(3) + x**Integer(4) + x**Integer(2)
>>> f.is_monic()
True
>>> f = Integer(2)*x**Integer(2) + x**Integer(3) + Integer(56)*x**Integer(5)
>>> f.is_monic()
False

AUTHORS:

  • Naqi Jaffery (2006-01-24): examples

is_monomial()[source]#

Return 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
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> x.is_monomial()
True
>>> (x + Integer(1)).is_monomial()
False
>>> (x**Integer(2)).is_monomial()
True
>>> R(Integer(1)).is_monomial()
True

The coefficient must be 1:

sage: (2*x^5).is_monomial()
False
>>> from sage.all import *
>>> (Integer(2)*x**Integer(5)).is_monomial()
False

To allow a non-1 leading coefficient, use is_term():

sage: (2*x^5).is_term()
True
>>> from sage.all import *
>>> (Integer(2)*x**Integer(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.

is_nilpotent()[source]#

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
>>> from sage.all import *
>>> R = Integers(Integer(12))
>>> S = R['x']; (x,) = S._first_ngens(1)
>>> f = Integer(5) + Integer(6)*x
>>> f.is_nilpotent()
False
>>> f = Integer(6) + Integer(6)*x**Integer(2)
>>> f.is_nilpotent()
True
>>> f**Integer(2)
0

EXERCISE (Atiyah-McDonald, Ch 1): Let \(A[x]\) be a polynomial ring in one variable. Then \(f=\sum a_i x^i \in A[x]\) is nilpotent if and only if every \(a_i\) is nilpotent.

is_one()[source]#

Test whether this polynomial is 1.

EXAMPLES:

sage: R.<x> = QQ[]
sage: (x - 3).is_one()
False
sage: R(1).is_one()
True

sage: R2.<y> = R[]
sage: R2(x).is_one()
False
sage: R2(1).is_one()
True
sage: R2(-1).is_one()
False
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> (x - Integer(3)).is_one()
False
>>> R(Integer(1)).is_one()
True

>>> R2 = R['y']; (y,) = R2._first_ngens(1)
>>> R2(x).is_one()
False
>>> R2(Integer(1)).is_one()
True
>>> R2(-Integer(1)).is_one()
False
is_primitive(n=None, n_prime_divs=None)[source]#

Return True if the polynomial is primitive.

The semantics of “primitive” depend on the polynomial coefficients.

  • (field theory) A polynomial of degree \(m\) over a finite field \(\GF{q}\) is primitive if it is irreducible and its root in \(\GF{q^m}\) generates the multiplicative group \(\GF{q^m}^*\).

  • (ring theory) A polynomial over a ring is primitive if its coefficients generate the unit ideal.

Calling is_primitive() 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).

INPUT:

  • n (default: None) – if provided, should equal \(q-1\) where self.parent() is the field with \(q\) 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: # needs sage.rings.finite_rings
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.
>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> R = GF(Integer(2))['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(4) + x**Integer(3) + x**Integer(2) + x + Integer(1)
>>> f.is_irreducible(), f.is_primitive()
(True, False)
>>> f = x**Integer(3) + x + Integer(1)
>>> f.is_irreducible(), f.is_primitive()
(True, True)
>>> R = GF(Integer(3))['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(3) - x + Integer(1)
>>> f.is_irreducible(), f.is_primitive()
(True, True)
>>> f = x**Integer(2) + Integer(1)
>>> f.is_irreducible(), f.is_primitive()
(True, False)
>>> R = GF(Integer(5))['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(2) + x + Integer(1)
>>> f.is_primitive()
False
>>> f = x**Integer(2) - x + Integer(2)
>>> f.is_primitive()
True
>>> x = polygen(QQ); f = x**Integer(2) + Integer(1)
>>> 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: # needs sage.rings.number_field
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
>>> from sage.all import *
>>> x = polygen(ZZ)
>>> f = Integer(5)*x**Integer(2) + Integer(2)
>>> f.is_primitive()
True
>>> f = Integer(5)*x**Integer(2) + Integer(5)
>>> f.is_primitive()
False

>>> # needs sage.rings.number_field
>>> K = NumberField(x**Integer(2) + Integer(5), 'a')
>>> R = K.ring_of_integers()
>>> a = R.gen(Integer(1))
>>> a**Integer(2)
-5
>>> f = a*x + Integer(2)
>>> f.is_primitive()
True
>>> f = (Integer(1)+a)*x + Integer(2)
>>> f.is_primitive()
False

>>> x = polygen(Integers(Integer(10)))
>>> f = Integer(5)*x**Integer(2) + Integer(2)
>>> #f.is_primitive()  #BUG:: elsewhere in Sage, should return True
>>> f = Integer(4)*x**Integer(2) + Integer(2)
>>> #f.is_primitive()  #BUG:: elsewhere in Sage, should return False
is_real_rooted()[source]#

Return True if the roots of this polynomial are all real.

EXAMPLES:

sage: # needs sage.libs.pari
sage: R.<x> = PolynomialRing(ZZ)
sage: pol = chebyshev_T(5, x)
sage: pol.is_real_rooted()
True
sage: pol = x^2 + 1
sage: pol.is_real_rooted()
False
>>> from sage.all import *
>>> # needs sage.libs.pari
>>> R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> pol = chebyshev_T(Integer(5), x)
>>> pol.is_real_rooted()
True
>>> pol = x**Integer(2) + Integer(1)
>>> pol.is_real_rooted()
False
is_square(root=False)[source]#

Return whether or not polynomial is square.

If the optional argument root is set to True, then also returns the square root (or None, if the polynomial is not square).

INPUT:

  • root – whether or not to also return a square root (default: False)

OUTPUT:

  • bool – whether or not a square

  • root – (optional) an actual square root if found, and None otherwise.

EXAMPLES:

sage: R.<x> = PolynomialRing(QQ)
sage: (x^2 + 2*x + 1).is_square()
True
sage: (x^4 + 2*x^3 - x^2 - 2*x + 1).is_square(root=True)
(True, x^2 + x - 1)

sage: f = 12 * (x + 1)^2 * (x + 3)^2
sage: f.is_square()
False
sage: f.is_square(root=True)
(False, None)

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)

sage: S.<y> = PolynomialRing(RR)
sage: g = 12 * (y + 1)^2 * (y + 3)^2

sage: g.is_square()
True
>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> (x**Integer(2) + Integer(2)*x + Integer(1)).is_square()
True
>>> (x**Integer(4) + Integer(2)*x**Integer(3) - x**Integer(2) - Integer(2)*x + Integer(1)).is_square(root=True)
(True, x^2 + x - 1)

>>> f = Integer(12) * (x + Integer(1))**Integer(2) * (x + Integer(3))**Integer(2)
>>> f.is_square()
False
>>> f.is_square(root=True)
(False, None)

>>> h = f/Integer(3); h
4*x^4 + 32*x^3 + 88*x^2 + 96*x + 36
>>> h.is_square(root=True)
(True, 2*x^2 + 8*x + 6)

>>> S = PolynomialRing(RR, names=('y',)); (y,) = S._first_ngens(1)
>>> g = Integer(12) * (y + Integer(1))**Integer(2) * (y + Integer(3))**Integer(2)

>>> g.is_square()
True
is_squarefree()[source]#

Return False if this polynomial is not square-free, i.e., if there is a non-unit \(g\) in the polynomial ring such that \(g^2\) 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
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = (x-Integer(1)) * (x-Integer(2)) * (x**Integer(2)-Integer(5)) * (x**Integer(17)-Integer(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
>>> f.is_squarefree()
True
>>> (f * (x**Integer(2)-Integer(5))).is_squarefree()
False

A generic implementation is available, which relies on gcd computations:

sage: # needs sage.libs.pari
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()
True
sage: (2*x*y^2).is_squarefree()
False
>>> from sage.all import *
>>> # needs sage.libs.pari
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> (Integer(2)*x).is_squarefree()
True
>>> (Integer(4)*x).is_squarefree()
False
>>> (Integer(2)*x**Integer(2)).is_squarefree()
False
>>> R(Integer(0)).is_squarefree()
False

>>> S = QQ['y']; (y,) = S._first_ngens(1)
>>> R = S['x']; (x,) = R._first_ngens(1)
>>> (Integer(2)*x*y).is_squarefree()
True
>>> (Integer(2)*x*y**Integer(2)).is_squarefree()
False

In 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()                                             # needs sage.libs.pari
False
sage: (x^3 + t).is_squarefree()                                             # needs sage.libs.pari
True
sage: (x^3 + t^3).is_squarefree()                                           # needs sage.libs.pari
False
>>> from sage.all import *
>>> K = FunctionField(GF(Integer(3)), names=('t',)); (t,) = K._first_ngens(1)
>>> R = K['x']; (x,) = R._first_ngens(1)
>>> (x**Integer(3) - x).is_squarefree()
True
>>> (x**Integer(3) - Integer(1)).is_squarefree()                                             # needs sage.libs.pari
False
>>> (x**Integer(3) + t).is_squarefree()                                             # needs sage.libs.pari
True
>>> (x**Integer(3) + t**Integer(3)).is_squarefree()                                           # needs sage.libs.pari
False

In the following example, \(t^2\) is a unit in the base field:

sage: R(t^2).is_squarefree()
True
>>> from sage.all import *
>>> R(t**Integer(2)).is_squarefree()
True

This method is not consistent with squarefree_decomposition():

sage: R.<x> = ZZ[]
sage: f = 4 * x
sage: f.is_squarefree()                                                     # needs sage.libs.pari
False
sage: f.squarefree_decomposition()                                          # needs sage.libs.pari
(4) * x
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> f = Integer(4) * x
>>> f.is_squarefree()                                                     # needs sage.libs.pari
False
>>> f.squarefree_decomposition()                                          # needs sage.libs.pari
(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()                                                 # needs sage.libs.pari
True
>>> from sage.all import *
>>> c = f.content()
>>> (f/c).is_squarefree()                                                 # needs sage.libs.pari
True

If the base ring is not an integral domain, the question is not mathematically well-defined:

sage: R.<x> = IntegerModRing(9)[]
sage: pol = (x + 3) * (x + 6); pol
x^2
sage: pol.is_squarefree()
Traceback (most recent call last):
...
TypeError: is_squarefree() is not defined for
polynomials over Ring of integers modulo 9
>>> from sage.all import *
>>> R = IntegerModRing(Integer(9))['x']; (x,) = R._first_ngens(1)
>>> pol = (x + Integer(3)) * (x + Integer(6)); pol
x^2
>>> pol.is_squarefree()
Traceback (most recent call last):
...
TypeError: is_squarefree() is not defined for
polynomials over Ring of integers modulo 9
is_term()[source]#

Return True if this polynomial is a nonzero element of the base ring times a power of the variable.

EXAMPLES:

sage: R.<x> = QQ[]
sage: x.is_term()
True
sage: R(0).is_term()
False
sage: R(1).is_term()
True
sage: (3*x^5).is_term()
True
sage: (1 + 3*x^5).is_term()
False
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> x.is_term()
True
>>> R(Integer(0)).is_term()
False
>>> R(Integer(1)).is_term()
True
>>> (Integer(3)*x**Integer(5)).is_term()
True
>>> (Integer(1) + Integer(3)*x**Integer(5)).is_term()
False

To require that the coefficient is 1, use is_monomial() instead:

sage: (3*x^5).is_monomial()
False
>>> from sage.all import *
>>> (Integer(3)*x**Integer(5)).is_monomial()
False
is_unit()[source]#

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: # needs sage.libs.pari
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
>>> from sage.all import *
>>> a = Integers(Integer(90384098234)**Integer(3))
>>> b = a(Integer(2)*Integer(191)*Integer(236607587))
>>> b.is_nilpotent()
True

>>> # needs sage.libs.pari
>>> R = a['x']; (x,) = R._first_ngens(1)
>>> f = Integer(3) + b*x + b**Integer(2)*x**Integer(2)
>>> f.is_unit()
True
>>> f = Integer(3) + b*x + b**Integer(2)*x**Integer(2) + Integer(17)*x**Integer(3)
>>> f.is_unit()
False

EXERCISE (Atiyah-McDonald, Ch 1): Let \(A[x]\) be a polynomial ring in one variable. Then \(f=\sum a_i x^i \in A[x]\) is a unit if and only if \(a_0\) is a unit and \(a_1,\ldots, a_n\) are nilpotent.

is_weil_polynomial(return_q=False)[source]#

Return True if this is a Weil polynomial.

This polynomial must have rational or integer coefficients.

INPUT:

  • self – polynomial with rational or integer coefficients

  • return_q – (default False) if True, return a second value \(q\) which is the prime power with respect to which this is \(q\)-Weil, or 0 if there is no such value.

EXAMPLES:

sage: polRing.<x> = PolynomialRing(Rationals())
sage: P0 = x^4 + 5*x^3 + 15*x^2 + 25*x + 25
sage: P1 = x^4 + 25*x^3 + 15*x^2 + 5*x + 25
sage: P2 = x^4 + 5*x^3 + 25*x^2 + 25*x + 25
sage: P0.is_weil_polynomial(return_q=True)                                  # needs sage.libs.pari
(True, 5)
sage: P0.is_weil_polynomial(return_q=False)                                 # needs sage.libs.pari
True
sage: P1.is_weil_polynomial(return_q=True)
(False, 0)
sage: P1.is_weil_polynomial(return_q=False)
False
sage: P2.is_weil_polynomial()                                               # needs sage.libs.pari
False
>>> from sage.all import *
>>> polRing = PolynomialRing(Rationals(), names=('x',)); (x,) = polRing._first_ngens(1)
>>> P0 = x**Integer(4) + Integer(5)*x**Integer(3) + Integer(15)*x**Integer(2) + Integer(25)*x + Integer(25)
>>> P1 = x**Integer(4) + Integer(25)*x**Integer(3) + Integer(15)*x**Integer(2) + Integer(5)*x + Integer(25)
>>> P2 = x**Integer(4) + Integer(5)*x**Integer(3) + Integer(25)*x**Integer(2) + Integer(25)*x + Integer(25)
>>> P0.is_weil_polynomial(return_q=True)                                  # needs sage.libs.pari
(True, 5)
>>> P0.is_weil_polynomial(return_q=False)                                 # needs sage.libs.pari
True
>>> P1.is_weil_polynomial(return_q=True)
(False, 0)
>>> P1.is_weil_polynomial(return_q=False)
False
>>> P2.is_weil_polynomial()                                               # needs sage.libs.pari
False

See also

Polynomial rings have a method weil_polynomials() to compute sets of Weil polynomials. This computation uses the iterator sage.rings.polynomial.weil.weil_polynomials.WeilPolynomials.

AUTHORS:

David Zureick-Brown (2017-10-01)

is_zero()[source]#

Test whether this polynomial is zero.

EXAMPLES:

sage: R = GF(2)['x']['y']
sage: R([0,1]).is_zero()
False
sage: R([0]).is_zero()
True
sage: R([-1]).is_zero()
False
>>> from sage.all import *
>>> R = GF(Integer(2))['x']['y']
>>> R([Integer(0),Integer(1)]).is_zero()
False
>>> R([Integer(0)]).is_zero()
True
>>> R([-Integer(1)]).is_zero()
False
lc()[source]#

Return the leading coefficient of this polynomial.

OUTPUT: element of the base ring

This method is the same as leading_coefficient().

EXAMPLES:

sage: R.<x> = QQ[]
sage: f = (-2/5)*x^3 + 2*x - 1/3
sage: f.lc()
-2/5
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = (-Integer(2)/Integer(5))*x**Integer(3) + Integer(2)*x - Integer(1)/Integer(3)
>>> f.lc()
-2/5
lcm(other)[source]#

Let \(f\) and \(g\) be two polynomials. Then this function returns the monic least common multiple of \(f\) and \(g\).

leading_coefficient()[source]#

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
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = (-Integer(2)/Integer(5))*x**Integer(3) + Integer(2)*x - Integer(1)/Integer(3)
>>> f.leading_coefficient()
-2/5
list(copy=True)[source]#

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]
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = (-Integer(2)/Integer(5))*x**Integer(3) + Integer(2)*x - Integer(1)/Integer(3)
>>> 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)
<... 'list'>
sage: v[0] = 5
sage: f.list()
[-1/3, 2, 0, -2/5]
>>> from sage.all import *
>>> type(v)
<... 'list'>
>>> v[Integer(0)] = Integer(5)
>>> 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)
<class '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]
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> S = R['y']; (y,) = S._first_ngens(1)
>>> f = y**Integer(3) + x*y - Integer(3)*x; f
y^3 + x*y - 3*x
>>> type(f)
<class 'sage.rings.polynomial.polynomial_element.Polynomial_generic_dense'>
>>> v = f.list(); v
[-3*x, x, 0, 1]
>>> v[Integer(0)] = Integer(10)
>>> f.list()
[-3*x, x, 0, 1]
lm()[source]#

Return the leading monomial of this polynomial.

EXAMPLES:

sage: R.<x> = QQ[]
sage: f = (-2/5)*x^3 + 2*x - 1/3
sage: f.lm()
x^3
sage: R(5).lm()
1
sage: R(0).lm()
0
sage: R(0).lm().parent() is R
True
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = (-Integer(2)/Integer(5))*x**Integer(3) + Integer(2)*x - Integer(1)/Integer(3)
>>> f.lm()
x^3
>>> R(Integer(5)).lm()
1
>>> R(Integer(0)).lm()
0
>>> R(Integer(0)).lm().parent() is R
True
local_height(v, prec=None)[source]#

Return the maximum of the local height of the coefficients of this polynomial.

INPUT:

  • v – a prime or prime ideal of the base ring.

  • prec – desired floating point precision (default: default RealField precision).

OUTPUT: a real number.

EXAMPLES:

sage: R.<x> = PolynomialRing(QQ)
sage: f = 1/1331*x^2 + 1/4000*x
sage: f.local_height(1331)                                                  # needs sage.rings.real_mpfr
7.19368581839511
>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> f = Integer(1)/Integer(1331)*x**Integer(2) + Integer(1)/Integer(4000)*x
>>> f.local_height(Integer(1331))                                                  # needs sage.rings.real_mpfr
7.19368581839511
sage: # needs sage.rings.number_field
sage: R.<x> = QQ[]
sage: K.<k> = NumberField(x^2 - 5)
sage: T.<t> = K[]
sage: I = K.ideal(3)
sage: f = 1/3*t^2 + 3
sage: f.local_height(I)
1.09861228866811
>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> K = NumberField(x**Integer(2) - Integer(5), names=('k',)); (k,) = K._first_ngens(1)
>>> T = K['t']; (t,) = T._first_ngens(1)
>>> I = K.ideal(Integer(3))
>>> f = Integer(1)/Integer(3)*t**Integer(2) + Integer(3)
>>> f.local_height(I)
1.09861228866811
sage: R.<x> = QQ[]
sage: f = 1/2*x^2 + 2
sage: f.local_height(2, prec=2)                                             # needs sage.rings.real_mpfr
0.75
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = Integer(1)/Integer(2)*x**Integer(2) + Integer(2)
>>> f.local_height(Integer(2), prec=Integer(2))                                             # needs sage.rings.real_mpfr
0.75
local_height_arch(i, prec=None)[source]#

Return the maximum of the local height at the i-th infinite place of the coefficients of this polynomial.

INPUT:

  • i – an integer.

  • prec – desired floating point precision (default: default RealField precision).

OUTPUT: a real number.

EXAMPLES:

sage: R.<x> = PolynomialRing(QQ)
sage: f = 210*x^2
sage: f.local_height_arch(0)                                                # needs sage.rings.real_mpfr
5.34710753071747
>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> f = Integer(210)*x**Integer(2)
>>> f.local_height_arch(Integer(0))                                                # needs sage.rings.real_mpfr
5.34710753071747
sage: # needs sage.rings.number_field
sage: R.<x> = QQ[]
sage: K.<k> = NumberField(x^2 - 5)
sage: T.<t> = K[]
sage: f = 1/2*t^2 + 3
sage: f.local_height_arch(1, prec=52)
1.09861228866811
>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> K = NumberField(x**Integer(2) - Integer(5), names=('k',)); (k,) = K._first_ngens(1)
>>> T = K['t']; (t,) = T._first_ngens(1)
>>> f = Integer(1)/Integer(2)*t**Integer(2) + Integer(3)
>>> f.local_height_arch(Integer(1), prec=Integer(52))
1.09861228866811
sage: R.<x> = QQ[]
sage: f = 1/2*x^2 + 3
sage: f.local_height_arch(0, prec=2)                                        # needs sage.rings.real_mpfr
1.0
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = Integer(1)/Integer(2)*x**Integer(2) + Integer(3)
>>> f.local_height_arch(Integer(0), prec=Integer(2))                                        # needs sage.rings.real_mpfr
1.0
lt()[source]#

Return the leading term of this polynomial.

EXAMPLES:

sage: R.<x> = QQ[]
sage: f = (-2/5)*x^3 + 2*x - 1/3
sage: f.lt()
-2/5*x^3
sage: R(5).lt()
5
sage: R(0).lt()
0
sage: R(0).lt().parent() is R
True
>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> f = (-Integer(2)/Integer(5))*x**Integer(3) + Integer(2)*x - Integer(1)/Integer(3)
>>> f.lt()
-2/5*x^3
>>> R(Integer(5)).lt()
5
>>> R(Integer(0)).lt()
0
>>> R(Integer(0)).lt().parent() is R
True
map_coefficients(f, new_base_ring=None)[source]#

Return 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:

  • f – a callable that will be applied to the coefficients of self.

  • new_base_ring (optional) – if given, the resulting polynomial will be defined over this ring.

EXAMPLES:

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(ZZ, sparse=True)
sage: f = x^(2^32) + 2
sage: f.map_coefficients(lambda a: a + 42)
43*x^4294967296 + 44

sage: # needs sage.symbolic
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> = 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
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(2) + Integer(2)
>>> f.map_coefficients(lambda a: a + Integer(42))
43*x^2 + 44
>>> R = PolynomialRing(ZZ, sparse=True, names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**(Integer(2)**Integer(32)) + Integer(2)
>>> f.map_coefficients(lambda a: a + Integer(42))
43*x^4294967296 + 44

>>> # needs sage.symbolic
>>> R = SR['x']; (x,) = R._first_ngens(1)
>>> f = (Integer(1)+I)*x**Integer(2) + Integer(3)*x - I
>>> f.map_coefficients(lambda z: z.conjugate())
(-I + 1)*x^2 + 3*x + I
>>> R = PolynomialRing(SR, sparse=True, names=('x',)); (x,) = R._first_ngens(1)
>>> f = (Integer(1)+I)*x**(Integer(2)**Integer(32)) - I
>>> f.map_coefficients(lambda z: z.conjugate())
(-I + 1)*x^4294967296 + I

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()                                                            # needs sage.libs.ntl
Univariate Polynomial Ring in x over Finite Field of size 2 (using GF2X)
sage: residue = k.coerce_map_from(ZZ)
sage: g = f.map_coefficients(residue); g
x + 1
sage: g.parent()                                                            # needs sage.libs.ntl
Univariate Polynomial Ring in x over Finite Field of size 2 (using GF2X)
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> k = GF(Integer(2))
>>> residue = lambda x: k(x)
>>> f = Integer(4)*x**Integer(2) + x + Integer(3)
>>> g = f.map_coefficients(residue); g
x + 1
>>> g.parent()
Univariate Polynomial Ring in x over Integer Ring
>>> g = f.map_coefficients(residue, new_base_ring=k); g
x + 1
>>> g.parent()                                                            # needs sage.libs.ntl
Univariate Polynomial Ring in x over Finite Field of size 2 (using GF2X)
>>> residue = k.coerce_map_from(ZZ)
>>> g = f.map_coefficients(residue); g
x + 1
>>> g.parent()                                                            # needs sage.libs.ntl
Univariate Polynomial Ring in x over Finite Field of size 2 (using GF2X)
mod(other)[source]#

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
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> x % (x+Integer(1))
-1
>>> (x**Integer(3) + x - Integer(1)) % (x**Integer(2) - Integer(1))
2*x - 1
monic()[source]#

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
>>> from sage.all import *
>>> x = QQ['x'].gen(0)
>>> f = Integer(2)*x**Integer(2) + x**Integer(3) + Integer(56)*x**Integer(5)
>>> f.monic()
x^5 + 1/56*x^3 + 1/28*x^2
>>> f = (Integer(1)/Integer(4))*x**Integer(2) + Integer(3)*x + Integer(1)
>>> f.monic()
x^2 + 12*x + 4

The following happens because \(f = 0\) cannot be made into a monic polynomial

sage: f = 0*x
sage: f.monic()
Traceback (most recent call last):
...
ZeroDivisionError: rational division by zero
>>> from sage.all import *
>>> f = Integer(0)*x
>>> 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
>>> from sage.all import *
>>> x = ZZ['x'].gen(0)
>>> f = Integer(3)*x**Integer(19) + x**Integer(2) - Integer(37)
>>> g = f.monic(); g
x^19 + 1/3*x^2 - 37/3
>>> g.parent()
Univariate Polynomial Ring in x over Rational Field

AUTHORS:

  • Naqi Jaffery (2006-01-24): examples

monomial_coefficient(m)[source]#

Return the coefficient in the base ring of the monomial m in self, where m must have the same parent as self.

INPUT:

  • m – a monomial

OUTPUT: Coefficient in base ring.

EXAMPLES:

sage: P.<x> = QQ[]
sage: f = 2 * x
sage: c = f.monomial_coefficient(x); c
2
sage: c.parent()
Rational Field

sage: f = x^9 - 1/2*x^2 + 7*x + 5/11
sage: f.monomial_coefficient(x^9)
1
sage: f.monomial_coefficient(x^2)
-1/2
sage: f.monomial_coefficient(x)
7
sage: f.monomial_coefficient(x^0)
5/11
sage: f.monomial_coefficient(x^3)
0
>>> from sage.all import *
>>> P = QQ['x']; (x,) = P._first_ngens(1)
>>> f = Integer(2) * x
>>> c = f.monomial_coefficient(x); c
2
>>> c.parent()
Rational Field

>>> f = x**Integer(9) - Integer(1)/Integer(2)*x**Integer(2) + Integer(7)*x + Integer(5)/Integer(11)
>>> f.monomial_coefficient(x**Integer(9))
1
>>> f.monomial_coefficient(x**Integer(2))
-1/2
>>> f.monomial_coefficient(x)
7
>>> f.monomial_coefficient(x**Integer(0))
5/11
>>> f.monomial_coefficient(x**Integer(3))
0
monomials()[source]#

Return the list of the monomials in self in a decreasing order of their degrees.

EXAMPLES:

sage: P.<x> = QQ[]
sage: f = x^2 + (2/3)*x + 1
sage: f.monomials()
[x^2, x, 1]
sage: f = P(3/2)
sage: f.monomials()
[1]
sage: f = P(0)
sage: f.monomials()
[]
sage: f = x
sage: f.monomials()
[x]
sage: f = - 1/2*x^2 + x^9 + 7*x + 5/11
sage: f.monomials()
[x^9, x^2, x, 1]

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<rho> = NumberField(x**2 + 1)
sage: R.<y> = QQ[]
sage: p = rho * y
sage: p.monomials()
[y]
>>> from sage.all import *
>>> P = QQ['x']; (x,) = P._first_ngens(1)
>>> f = x**Integer(2) + (Integer(2)/Integer(3))*x + Integer(1)
>>> f.monomials()
[x^2, x, 1]
>>> f = P(Integer(3)/Integer(2))
>>> f.monomials()
[1]
>>> f = P(Integer(0))
>>> f.monomials()
[]
>>> f = x
>>> f.monomials()
[x]
>>> f = - Integer(1)/Integer(2)*x**Integer(2) + x**Integer(9) + Integer(7)*x + Integer(5)/Integer(11)
>>> f.monomials()
[x^9, x^2, x, 1]

>>> # needs sage.rings.number_field
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(2) + Integer(1), names=('rho',)); (rho,) = K._first_ngens(1)
>>> R = QQ['y']; (y,) = R._first_ngens(1)
>>> p = rho * y
>>> p.monomials()
[y]
multiplication_trunc(other, n)[source]#

Truncated multiplication

EXAMPLES:

sage: R.<x> = ZZ[]
sage: (x^10 + 5*x^5 + x^2 - 3).multiplication_trunc(x^7 - 3*x^3 + 1, 11)
x^10 + x^9 - 15*x^8 - 3*x^7 + 2*x^5 + 9*x^3 + x^2 - 3
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> (x**Integer(10) + Integer(5)*x**Integer(5) + x**Integer(2) - Integer(3)).multiplication_trunc(x**Integer(7) - Integer(3)*x**Integer(3) + Integer(1), Integer(11))
x^10 + x^9 - 15*x^8 - 3*x^7 + 2*x^5 + 9*x^3 + x^2 - 3

Check that coercion is working:

sage: R2 = QQ['x']
sage: x2 = R2.gen()
sage: p1 = (x^3 + 1).multiplication_trunc(x2^3 - 2, 5); p1
-x^3 - 2
sage: p2 = (x2^3 + 1).multiplication_trunc(x^3 - 2, 5); p2
-x^3 - 2
sage: parent(p1) == parent(p2) == R2
True
>>> from sage.all import *
>>> R2 = QQ['x']
>>> x2 = R2.gen()
>>> p1 = (x**Integer(3) + Integer(1)).multiplication_trunc(x2**Integer(3) - Integer(2), Integer(5)); p1
-x^3 - 2
>>> p2 = (x2**Integer(3) + Integer(1)).multiplication_trunc(x**Integer(3) - Integer(2), Integer(5)); p2
-x^3 - 2
>>> parent(p1) == parent(p2) == R2
True
newton_raphson(n, x0)[source]#

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:

  • n – an integer (the number of iterations),

  • x0 – an initial guess \(x_0\).

OUTPUT: A list of numbers hopefully approximating a root of \(f(x)=0\).

If one of the iterates is a critical point of \(f\), a ZeroDivisionError exception is raised.

EXAMPLES:

sage: x = PolynomialRing(RealField(), 'x').gen()                            # needs sage.rings.real_mpfr
sage: f = x^2 - 2                                                           # needs sage.rings.real_mpfr
sage: f.newton_raphson(4, 1)                                                # needs sage.rings.real_mpfr
[1.50000000000000, 1.41666666666667, 1.41421568627451, 1.41421356237469]
>>> from sage.all import *
>>> x = PolynomialRing(RealField(), 'x').gen()                            # needs sage.rings.real_mpfr
>>> f = x**Integer(2) - Integer(2)                                                           # needs sage.rings.real_mpfr
>>> f.newton_raphson(Integer(4), Integer(1))                                                # needs sage.rings.real_mpfr
[1.50000000000000, 1.41666666666667, 1.41421568627451, 1.41421356237469]

AUTHORS:

  • David Joyner and William Stein (2005-11-28)

newton_slopes(p, lengths=False)[source]#

Return the \(p\)-adic slopes of the Newton polygon of self, when this makes sense.

OUTPUT:

If lengths is False, a list of rational numbers. If lengths is True, a list of couples \((s,l)\) where \(s\) is the slope and \(l\) the length of the corresponding segment in the Newton polygon.

EXAMPLES:

sage: x = QQ['x'].0
sage: f = x^3 + 2
sage: f.newton_slopes(2)                                                    # needs sage.libs.pari
[1/3, 1/3, 1/3]
sage: R.<x> = PolynomialRing(ZZ, sparse=True)
sage: p = x^5 + 6*x^2 + 4
sage: p.newton_slopes(2)                                                    # needs sage.libs.pari
[1/2, 1/2, 1/3, 1/3, 1/3]
sage: p.newton_slopes(2, lengths=True)
[(1/2, 2), (1/3, 3)]
sage: (x^2^100 + 27).newton_slopes(3, lengths=True)
[(3/1267650600228229401496703205376, 1267650600228229401496703205376)]
>>> from sage.all import *
>>> x = QQ['x'].gen(0)
>>> f = x**Integer(3) + Integer(2)
>>> f.newton_slopes(Integer(2))                                                    # needs sage.libs.pari
[1/3, 1/3, 1/3]
>>> R = PolynomialRing(ZZ, sparse=True, names=('x',)); (x,) = R._first_ngens(1)
>>> p = x**Integer(5) + Integer(6)*x**Integer(2) + Integer(4)
>>> p.newton_slopes(Integer(2))                                                    # needs sage.libs.pari
[1/2, 1/2, 1/3, 1/3, 1/3]
>>> p.newton_slopes(Integer(2), lengths=True)
[(1/2, 2), (1/3, 3)]
>>> (x**Integer(2)**Integer(100) + Integer(27)).newton_slopes(Integer(3), lengths=True)
[(3/1267650600228229401496703205376, 1267650600228229401496703205376)]

ALGORITHM: Uses PARI if lengths is False.

norm(p)[source]#

Return the \(p\)-norm of this polynomial.

DEFINITION: For integer \(p\), the \(p\)-norm of a polynomial is the \(p\)th root of the sum of the \(p\)th powers of the absolute values of the coefficients of the polynomial.

INPUT:

  • p – (positive integer or +infinity) the degree of the norm

EXAMPLES:

sage: # needs sage.rings.real_mpfr
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()                               # needs sage.symbolic
2.64575131106459
>>> from sage.all import *
>>> # needs sage.rings.real_mpfr
>>> R = RR['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(6) + x**Integer(2) + -x**Integer(4) - Integer(2)*x**Integer(3)
>>> f.norm(Integer(2))
2.64575131106459
>>> (sqrt(Integer(1)**Integer(2) + Integer(1)**Integer(2) + (-Integer(1))**Integer(2) + (-Integer(2))**Integer(2))).n()                               # needs sage.symbolic
2.64575131106459
sage: f.norm(1)                                                             # needs sage.rings.real_mpfr
5.00000000000000
sage: f.norm(infinity)                                                      # needs sage.rings.real_mpfr
2.00000000000000
>>> from sage.all import *
>>> f.norm(Integer(1))                                                             # needs sage.rings.real_mpfr
5.00000000000000
>>> f.norm(infinity)                                                      # needs sage.rings.real_mpfr
2.00000000000000
sage: f.norm(-1)                                                            # needs sage.rings.real_mpfr
Traceback (most recent call last):
...
ValueError: The degree of the norm must be positive
>>> from sage.all import *
>>> f.norm(-Integer(1))                                                            # needs sage.rings.real_mpfr
Traceback (most recent call last):
...
ValueError: The degree of the norm must be positive

AUTHORS:

  • Didier Deshommes

  • William Stein: fix bugs, add definition, etc.

nth_root(n)[source]#

Return a \(n\)-th root of this polynomial.

This is computed using Newton method in the ring of power series. This method works only when the base ring is an integral domain. Moreover, for polynomial whose coefficient of lower degree is different from 1, the elements of the base ring should have a method nth_root() implemented.

EXAMPLES:

sage: R.<x> = ZZ[]
sage: a = 27 * (x+3)**6 * (x+5)**3
sage: a.nth_root(3)
3*x^3 + 33*x^2 + 117*x + 135

sage: b = 25 * (x^2 + x + 1)
sage: b.nth_root(2)
Traceback (most recent call last):
...
ValueError: not a 2nd power
sage: R(0).nth_root(3)
0
sage: R.<x> = QQ[]
sage: a = 1/4 * (x/7 + 3/2)^2 * (x/2 + 5/3)^4
sage: a.nth_root(2)
1/56*x^3 + 103/336*x^2 + 365/252*x + 25/12

sage: # needs sage.rings.number_field
sage: K.<sqrt2> = QuadraticField(2)
sage: R.<x> = K[]
sage: a = (x + sqrt2)^3 * ((1+sqrt2)*x - 1/sqrt2)^6
sage: b = a.nth_root(3); b
(2*sqrt2 + 3)*x^3 + (2*sqrt2 + 2)*x^2 + (-2*sqrt2 - 3/2)*x + 1/2*sqrt2
sage: b^3 == a
True

sage: # needs sage.rings.number_field
sage: R.<x> = QQbar[]
sage: p = x**3 + QQbar(2).sqrt() * x - QQbar(3).sqrt()
sage: r = (p**5).nth_root(5)
sage: r * p[0] == p * r[0]
True
sage: p = (x+1)^20 + x^20
sage: p.nth_root(20)
Traceback (most recent call last):
...
ValueError: not a 20th power

sage: # needs sage.rings.finite_rings
sage: z = GF(4).gen()
sage: R.<x> = GF(4)[]
sage: p = z*x**4 + 2*x - 1
sage: r = (p**15).nth_root(15)
sage: r * p[0] == p * r[0]
True
sage: ((x+1)**2).nth_root(2)
x + 1
sage: ((x+1)**4).nth_root(4)
x + 1
sage: ((x+1)**12).nth_root(12)
x + 1
sage: (x^4 + x^3 + 1).nth_root(2)
Traceback (most recent call last):
...
ValueError: not a 2nd power
sage: p = (x+1)^17 + x^17
sage: r = p.nth_root(17)
Traceback (most recent call last):
...
ValueError: not a 17th power

sage: R1.<x> = QQ[]
sage: R2.<y> = R1[]
sage: R3.<z> = R2[]
sage: (((y**2+x)*z^2 + x*y*z + 2*x)**3).nth_root(3)
(y^2 + x)*z^2 + x*y*z + 2*x
sage: ((x+y+z)**5).nth_root(5)
z + y + x
>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> a = Integer(27) * (x+Integer(3))**Integer(6) * (x+Integer(5))**Integer(3)
>>> a.nth_root(Integer(3))
3*x^3 + 33*x^2 + 117*x + 135

>>> b = Integer(25) * (x**Integer(2) + x + Integer(1))
>>> b.nth_root(Integer(2))
Traceback (most recent call last):
...
ValueError: not a 2nd power
>>> R(Integer(0)).nth_root(Integer(3))
0
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> a = Integer(1)/Integer(4) * (x/Integer(7) + Integer(3)/Integer(2))**Integer(2) * (x/Integer(2) + Integer(5)/Integer(3))**Integer(4)
>>> a.nth_root(Integer(2))
1/56*x^3 + 103/336*x^2 + 365/252*x + 25/12

>>> # needs sage.rings.number_field
>>> K = QuadraticField(Integer(2), names=('sqrt2',)); (sqrt2,) = K._first_ngens(1)
>>> R = K['x']; (x,) = R._first_ngens(1)
>>> a = (x + sqrt2)**Integer(3) * ((Integer(1)+sqrt2)*x - Integer(1)/sqrt2)**Integer(6)
>>> b = a.nth_root(Integer(3)); b
(2*sqrt2 + 3)*x^3 + (2*sqrt2 + 2)*x^2 + (-2*sqrt2 - 3/2)*x + 1/2*sqrt2
>>> b**Integer(3) == a
True

>>> # needs sage.rings.number_field
>>> R = QQbar['x']; (x,) = R._first_ngens(1)
>>> p = x**Integer(3) + QQbar(Integer(2)).sqrt() * x - QQbar(Integer(3)).sqrt()
>>> r = (p**Integer(5)).nth_root(Integer(5))
>>> r * p[Integer(0)] == p * r[Integer(0)]
True
>>> p = (x+Integer(1))**Integer(20) + x**Integer(20)
>>> p.nth_root(Integer(20))
Traceback (most recent call last):
...
ValueError: not a 20th power

>>> # needs sage.rings.finite_rings
>>> z = GF(Integer(4)).gen()
>>> R = GF(Integer(4))['x']; (x,) = R._first_ngens(1)
>>> p = z*x**Integer(4) + Integer(2)*x - Integer(1)
>>> r = (p**Integer(15)).nth_root(Integer(15))
>>> r * p[Integer(0)] == p * r[Integer(0)]
True
>>> ((x+Integer(1))**Integer(2)).nth_root(Integer(2))
x + 1
>>> ((x+Integer(1))**Integer(4)).nth_root(Integer(4))
x + 1
>>> ((x+Integer(1))**Integer(12)).nth_root(Integer(12))
x + 1
>>> (x**Integer(4) + x**Integer(3) + Integer(1)).nth_root(Integer(2))
Traceback (most recent call last):
...
ValueError: not a 2nd power
>>> p = (x+Integer(1))**Integer(17) + x**Integer(17)
>>> r = p.nth_root(Integer(17))
Traceback (most recent call last):
...
ValueError: not a 17th power

>>> R1 = QQ['x']; (x,) = R1._first_ngens(1)
>>> R2 = R1['y']; (y,) = R2._first_ngens(1)
>>> R3 = R2['z']; (z,) = R3._first_ngens(1)
>>> (((y**Integer(2)+x)*z**Integer(2) + x*y*z + Integer(2)*x)**Integer(3)).nth_root(Integer(3))
(y^2 + x)*z^2 + x*y*z + 2*x
>>> ((x+y+z)**Integer(5)).nth_root(Integer(5))
z + y + x

Here we consider a base ring without nth_root method. The third example with a non-trivial coefficient of lowest degree raises an error:

sage: # needs sage.libs.pari
sage: R.<x> = QQ[]
sage: R2 = R.quotient(x**2 + 1)
sage: x = R2.gen()
sage: R3.<y> = R2[]
sage: (y**2 - 2*y + 1).nth_root(2)
-y + 1
sage: (y**3).nth_root(3)
y
sage: (y**2 + x).nth_root(2)
Traceback (most recent call last):
...
AttributeError: ... has no attribute 'nth_root'...
>>> from sage.all import *
>>> # needs sage.libs.pari
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> R2 = R.quotient(x**Integer(2) + Integer(1))
>>> x = R2.gen()
>>> R3 = R2['y']; (y,) = R3._first_ngens(1)
>>> (y**Integer(2) - Integer(2)*y + Integer(1)).nth_root(Integer(2))
-y + 1
>>> (y**Integer(3)).nth_root(Integer(3))
y
>>> (y**Integer(2) + x).nth_root(Integer(2))
Traceback (most recent call last):
...
AttributeError: ... has no attribute 'nth_root'...
number_of_real_roots()[source]#

Return the number of real roots of this polynomial, counted without multiplicity.

EXAMPLES:

sage: # needs sage.libs.pari
sage: R.<x> = PolynomialRing(ZZ)
sage: pol = (x - 1)^2 * (x - 2)^2 * (x - 3)
sage: pol.number_of_real_roots()
3
sage: pol = (x - 1) * (x - 2) * (x - 3)

sage: # needs sage.libs.pari sage.rings.real_mpfr
sage: pol2 = pol.change_ring(CC)
sage: pol2.number_of_real_roots()
3
sage: R.<x> = PolynomialRing(CC)
sage: pol = (x - 1) * (x - CC(I))
sage: pol.number_of_real_roots()
1
>>> from sage.all import *
>>> # needs sage.libs.pari
>>> R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> pol = (x - Integer(1))**Integer(2) * (x - Integer(2))**Integer(2) * (x - Integer(3))
>>> pol.number_of_real_roots()
3
>>> pol = (x - Integer(1)) * (x - Integer(2)) * (x - Integer(3))

>>> # needs sage.libs.pari sage.rings.real_mpfr
>>> pol2 = pol.change_ring(CC)
>>> pol2.number_of_real_roots()
3
>>> R = PolynomialRing(CC, names=('x',)); (x,) = R._first_ngens(1)
>>> pol = (x - Integer(1)) * (x - CC(I))
>>> pol.number_of_real_roots()
1
number_of_roots_in_interval(a=None, b=None)[source]#

Return the number of roots of this polynomial in the interval \([a,b]\), counted without multiplicity. The endpoints \(a\), \(b\) default to -Infinity, Infinity (which are also valid input values).

Calls the PARI routine pari:polsturm.

Note that as of version 2.8, PARI includes the left endpoint of the interval (and no longer uses Sturm’s algorithm on exact inputs). pari:polsturm requires a polynomial with real coefficients; in case PARI returns an error, we try again after taking the GCD of self with its complex conjugate.

EXAMPLES:

sage: # needs sage.libs.pari
sage: R.<x> = PolynomialRing(ZZ)
sage: pol = (x - 1)^2 * (x - 2)^2 * (x - 3)
sage: pol.number_of_roots_in_interval(1, 2)
2
sage: pol.number_of_roots_in_interval(1.01, 2)
1
sage: pol.number_of_roots_in_interval(None, 2)
2
sage: pol.number_of_roots_in_interval(1, Infinity)
3
sage: pol.number_of_roots_in_interval()
3
sage: pol = (x - 1) * (x - 2) * (x - 3)

sage: # needs sage.libs.pari sage.rings.real_mpfr
sage: pol2 = pol.change_ring(CC)
sage: pol2.number_of_roots_in_interval()
3
sage: R.<x> = PolynomialRing(CC)
sage: pol = (x - 1) * (x - CC(I))
sage: pol.number_of_roots_in_interval(0, 2)
1
>>> from sage.all import *
>>> # needs sage.libs.pari
>>> R