Univariate Polynomials over domains and fields¶

AUTHORS:

William Stein: first version
Martin Albrecht: Added singular coercion.
David Harvey: split off polynomial_integer_dense_ntl.pyx (2007-09)
Robert Bradshaw: split off polynomial_modn_dense_ntl.pyx (2007-09)

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_cdv(parent, is_gen=False, construct=False)[source]¶

Bases: Polynomial_generic_domain

A generic class for polynomials over complete discrete valuation domains and fields.

AUTHOR:

Xavier Caruso (2013-03)

factor_of_slope(slope=None)[source]¶

INPUT:

slope – a rational number (default: the first slope in the Newton polygon of self)

OUTPUT:

The factor of self corresponding to the slope slope (i.e. the unique monic divisor of self whose slope is slope and degree is the length of slope in the Newton polygon).

EXAMPLES:

Sage

sage: # needs sage.geometry.polyhedron sage.rings.padics
sage: K = Qp(5)
sage: R.<x> = K[]
sage: K = Qp(5)
sage: R.<t> = K[]
sage: f = 5 + 3*t + t^4 + 25*t^10
sage: f.newton_slopes()
[1, 0, 0, 0, -1/3, -1/3, -1/3, -1/3, -1/3, -1/3]
sage: g = f.factor_of_slope(0)
sage: g.newton_slopes()
[0, 0, 0]
sage: (f % g).is_zero()
True
sage: h = f.factor_of_slope()
sage: h.newton_slopes()
[1]
sage: (f % h).is_zero()
True

Python

>>> from sage.all import *
>>> # needs sage.geometry.polyhedron sage.rings.padics
>>> K = Qp(Integer(5))
>>> R = K['x']; (x,) = R._first_ngens(1)
>>> K = Qp(Integer(5))
>>> R = K['t']; (t,) = R._first_ngens(1)
>>> f = Integer(5) + Integer(3)*t + t**Integer(4) + Integer(25)*t**Integer(10)
>>> f.newton_slopes()
[1, 0, 0, 0, -1/3, -1/3, -1/3, -1/3, -1/3, -1/3]
>>> g = f.factor_of_slope(Integer(0))
>>> g.newton_slopes()
[0, 0, 0]
>>> (f % g).is_zero()
True
>>> h = f.factor_of_slope()
>>> h.newton_slopes()
[1]
>>> (f % h).is_zero()
True

Sage Live

# needs sage.geometry.polyhedron sage.rings.padics
K = Qp(5)
R.<x> = K[]
K = Qp(5)
R.<t> = K[]
f = 5 + 3*t + t^4 + 25*t^10
f.newton_slopes()
g = f.factor_of_slope(0)
g.newton_slopes()
(f % g).is_zero()
h = f.factor_of_slope()
h.newton_slopes()
(f % h).is_zero()

If slope is not a slope of self, the corresponding factor is \(1\):

Sage

sage: f.factor_of_slope(-1)                                                 # needs sage.geometry.polyhedron sage.rings.padics
1 + O(5^20)

Python

>>> from sage.all import *
>>> f.factor_of_slope(-Integer(1))                                                 # needs sage.geometry.polyhedron sage.rings.padics
1 + O(5^20)

Sage Live

f.factor_of_slope(-1)                                                 # needs sage.geometry.polyhedron sage.rings.padics

AUTHOR:

Xavier Caruso (2013-03-20)

hensel_lift(a)[source]¶

Lift \(a\) to a root of this polynomial (using Newton iteration).

If \(a\) is not close enough to a root (so that Newton iteration does not converge), an error is raised.

EXAMPLES:

Sage

sage: # needs sage.rings.padics
sage: K = Qp(5, 10)
sage: P.<x> = PolynomialRing(K)
sage: f = x^2 + 1
sage: root = f.hensel_lift(2); root
2 + 5 + 2*5^2 + 5^3 + 3*5^4 + 4*5^5 + 2*5^6 + 3*5^7 + 3*5^9 + O(5^10)
sage: f(root)
O(5^10)

sage: g = (x^2 + 1) * (x - 7)                                               # needs sage.rings.padics
sage: g.hensel_lift(2)  # here, 2 is a multiple root modulo p               # needs sage.rings.padics
Traceback (most recent call last):
...
ValueError: a is not close enough to a root of this polynomial

Python

>>> from sage.all import *
>>> # needs sage.rings.padics
>>> K = Qp(Integer(5), Integer(10))
>>> P = PolynomialRing(K, names=('x',)); (x,) = P._first_ngens(1)
>>> f = x**Integer(2) + Integer(1)
>>> root = f.hensel_lift(Integer(2)); root
2 + 5 + 2*5^2 + 5^3 + 3*5^4 + 4*5^5 + 2*5^6 + 3*5^7 + 3*5^9 + O(5^10)
>>> f(root)
O(5^10)

>>> g = (x**Integer(2) + Integer(1)) * (x - Integer(7))                                               # needs sage.rings.padics
>>> g.hensel_lift(Integer(2))  # here, 2 is a multiple root modulo p               # needs sage.rings.padics
Traceback (most recent call last):
...
ValueError: a is not close enough to a root of this polynomial

Sage Live

# needs sage.rings.padics
K = Qp(5, 10)
P.<x> = PolynomialRing(K)
f = x^2 + 1
root = f.hensel_lift(2); root
f(root)
g = (x^2 + 1) * (x - 7)                                               # needs sage.rings.padics
g.hensel_lift(2)  # here, 2 is a multiple root modulo p               # needs sage.rings.padics

AUTHOR:

Xavier Caruso (2013-03-23)

newton_polygon()[source]¶

Return a list of vertices of the Newton polygon of this polynomial.

Note

If some coefficients have not enough precision an error is raised.

EXAMPLES:

Sage

sage: # needs sage.geometry.polyhedron sage.rings.padics
sage: K = Qp(5)
sage: R.<t> = K[]
sage: f = 5 + 3*t + t^4 + 25*t^10
sage: f.newton_polygon()
Finite Newton polygon with 4 vertices: (0, 1), (1, 0), (4, 0), (10, 2)
sage: g = f + K(0,0)*t^4; g
(5^2 + O(5^22))*t^10 + O(5^0)*t^4 + (3 + O(5^20))*t + 5 + O(5^21)
sage: g.newton_polygon()
Traceback (most recent call last):
...
PrecisionError: The coefficient of t^4 has not enough precision

Python

>>> from sage.all import *
>>> # needs sage.geometry.polyhedron sage.rings.padics
>>> K = Qp(Integer(5))
>>> R = K['t']; (t,) = R._first_ngens(1)
>>> f = Integer(5) + Integer(3)*t + t**Integer(4) + Integer(25)*t**Integer(10)
>>> f.newton_polygon()
Finite Newton polygon with 4 vertices: (0, 1), (1, 0), (4, 0), (10, 2)
>>> g = f + K(Integer(0),Integer(0))*t**Integer(4); g
(5^2 + O(5^22))*t^10 + O(5^0)*t^4 + (3 + O(5^20))*t + 5 + O(5^21)
>>> g.newton_polygon()
Traceback (most recent call last):
...
PrecisionError: The coefficient of t^4 has not enough precision

Sage Live

# needs sage.geometry.polyhedron sage.rings.padics
K = Qp(5)
R.<t> = K[]
f = 5 + 3*t + t^4 + 25*t^10
f.newton_polygon()
g = f + K(0,0)*t^4; g
g.newton_polygon()

AUTHOR:

Xavier Caruso (2013-03-20)

newton_slopes(repetition=True)[source]¶

Return a list of the Newton slopes of this polynomial.

These are the valuations of the roots of this polynomial.

If repetition is True, each slope is repeated a number of times equal to its multiplicity. Otherwise it appears only one time.

EXAMPLES:

Sage

sage: # needs sage.geometry.polyhedron sage.rings.padics
sage: K = Qp(5)
sage: R.<t> = K[]
sage: f = 5 + 3*t + t^4 + 25*t^10
sage: f.newton_polygon()
Finite Newton polygon with 4 vertices: (0, 1), (1, 0), (4, 0), (10, 2)
sage: f.newton_slopes()
[1, 0, 0, 0, -1/3, -1/3, -1/3, -1/3, -1/3, -1/3]
sage: f.newton_slopes(repetition=False)
[1, 0, -1/3]

Python

>>> from sage.all import *
>>> # needs sage.geometry.polyhedron sage.rings.padics
>>> K = Qp(Integer(5))
>>> R = K['t']; (t,) = R._first_ngens(1)
>>> f = Integer(5) + Integer(3)*t + t**Integer(4) + Integer(25)*t**Integer(10)
>>> f.newton_polygon()
Finite Newton polygon with 4 vertices: (0, 1), (1, 0), (4, 0), (10, 2)
>>> f.newton_slopes()
[1, 0, 0, 0, -1/3, -1/3, -1/3, -1/3, -1/3, -1/3]
>>> f.newton_slopes(repetition=False)
[1, 0, -1/3]

Sage Live

# needs sage.geometry.polyhedron sage.rings.padics
K = Qp(5)
R.<t> = K[]
f = 5 + 3*t + t^4 + 25*t^10
f.newton_polygon()
f.newton_slopes()
f.newton_slopes(repetition=False)

AUTHOR:

Xavier Caruso (2013-03-20)

slope_factorization()[source]¶

Return a factorization of self into a product of factors corresponding to each slope in the Newton polygon.

EXAMPLES:

Sage

sage: # needs sage.geometry.polyhedron sage.rings.padics
sage: K = Qp(5)
sage: R.<x> = K[]
sage: K = Qp(5)
sage: R.<t> = K[]
sage: f = 5 + 3*t + t^4 + 25*t^10
sage: f.newton_slopes()
[1, 0, 0, 0, -1/3, -1/3, -1/3, -1/3, -1/3, -1/3]
sage: F = f.slope_factorization()
sage: F.prod() == f
True
sage: for (f,_) in F:
....:     print(f.newton_slopes())
[-1/3, -1/3, -1/3, -1/3, -1/3, -1/3]
[0, 0, 0]
[1]

Python

>>> from sage.all import *
>>> # needs sage.geometry.polyhedron sage.rings.padics
>>> K = Qp(Integer(5))
>>> R = K['x']; (x,) = R._first_ngens(1)
>>> K = Qp(Integer(5))
>>> R = K['t']; (t,) = R._first_ngens(1)
>>> f = Integer(5) + Integer(3)*t + t**Integer(4) + Integer(25)*t**Integer(10)
>>> f.newton_slopes()
[1, 0, 0, 0, -1/3, -1/3, -1/3, -1/3, -1/3, -1/3]
>>> F = f.slope_factorization()
>>> F.prod() == f
True
>>> for (f,_) in F:
...     print(f.newton_slopes())
[-1/3, -1/3, -1/3, -1/3, -1/3, -1/3]
[0, 0, 0]
[1]

Sage Live

# needs sage.geometry.polyhedron sage.rings.padics
K = Qp(5)
R.<x> = K[]
K = Qp(5)
R.<t> = K[]
f = 5 + 3*t + t^4 + 25*t^10
f.newton_slopes()
F = f.slope_factorization()
F.prod() == f
for (f,_) in F:
    print(f.newton_slopes())

AUTHOR:

Xavier Caruso (2013-03-20)

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_cdvf(parent, is_gen=False, construct=False)[source]¶: Bases: Polynomial_generic_cdv, Polynomial_generic_field

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_cdvr(parent, is_gen=False, construct=False)[source]¶: Bases: Polynomial_generic_cdv

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_dense_cdv[source]¶: Bases: Polynomial_generic_dense_inexact, Polynomial_generic_cdv

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_dense_cdvf[source]¶: Bases: Polynomial_generic_dense_cdv, Polynomial_generic_cdvf

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_dense_cdvr[source]¶: Bases: Polynomial_generic_dense_cdv, Polynomial_generic_cdvr

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_dense_field(parent, x=None, check=True, is_gen=False, construct=False)[source]¶: Bases: Polynomial_generic_dense, Polynomial_generic_field

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_domain(parent, is_gen=False, construct=False)[source]¶

Bases: Polynomial, IntegralDomainElement

is_unit()[source]¶

Return True if this polynomial is a unit.

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.

EXAMPLES:

Sage

sage: R.<z> = PolynomialRing(ZZ, sparse=True)
sage: (2 + z^3).is_unit()
False
sage: f = -1 + 3*z^3; f
3*z^3 - 1
sage: f.is_unit()
False
sage: R(-3).is_unit()
False
sage: R(-1).is_unit()
True
sage: R(0).is_unit()
False

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, sparse=True, names=('z',)); (z,) = R._first_ngens(1)
>>> (Integer(2) + z**Integer(3)).is_unit()
False
>>> f = -Integer(1) + Integer(3)*z**Integer(3); f
3*z^3 - 1
>>> f.is_unit()
False
>>> R(-Integer(3)).is_unit()
False
>>> R(-Integer(1)).is_unit()
True
>>> R(Integer(0)).is_unit()
False

Sage Live

R.<z> = PolynomialRing(ZZ, sparse=True)
(2 + z^3).is_unit()
f = -1 + 3*z^3; f
f.is_unit()
R(-3).is_unit()
R(-1).is_unit()
R(0).is_unit()

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_field(parent, is_gen=False, construct=False)[source]¶

Bases: Polynomial_singular_repr, Polynomial_generic_domain, EuclideanDomainElement

quo_rem(other)[source]¶

Return a tuple (quotient, remainder) where self = quotient * other + remainder.

EXAMPLES:

Sage

sage: # needs sage.rings.number_field
sage: R.<y> = PolynomialRing(QQ)
sage: K.<t> = NumberField(y^2 - 2)
sage: P.<x> = PolynomialRing(K)
sage: x.quo_rem(K(1))
(x, 0)
sage: x.xgcd(K(1))
(1, 0, 1)

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> R = PolynomialRing(QQ, names=('y',)); (y,) = R._first_ngens(1)
>>> K = NumberField(y**Integer(2) - Integer(2), names=('t',)); (t,) = K._first_ngens(1)
>>> P = PolynomialRing(K, names=('x',)); (x,) = P._first_ngens(1)
>>> x.quo_rem(K(Integer(1)))
(x, 0)
>>> x.xgcd(K(Integer(1)))
(1, 0, 1)

Sage Live

# needs sage.rings.number_field
R.<y> = PolynomialRing(QQ)
K.<t> = NumberField(y^2 - 2)
P.<x> = PolynomialRing(K)
x.quo_rem(K(1))
x.xgcd(K(1))

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_sparse(parent, x=None, check=True, is_gen=False, construct=False)[source]¶

Bases: Polynomial

A generic sparse polynomial.

The Polynomial_generic_sparse class defines functionality for sparse polynomials over any base ring. A sparse polynomial is represented using a dictionary which maps each exponent to the corresponding coefficient. The coefficients must never be zero.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(PolynomialRing(QQ, 'y'), sparse=True)
sage: f = x^3 - x + 17
sage: type(f)
<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_integral_domain_with_category.element_class'>
sage: loads(f.dumps()) == f
True

Python

>>> from sage.all import *
>>> R = PolynomialRing(PolynomialRing(QQ, 'y'), sparse=True, names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(3) - x + Integer(17)
>>> type(f)
<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_integral_domain_with_category.element_class'>
>>> loads(f.dumps()) == f
True

Sage Live

R.<x> = PolynomialRing(PolynomialRing(QQ, 'y'), sparse=True)
f = x^3 - x + 17
type(f)
loads(f.dumps()) == f

A more extensive example:

Sage

sage: # needs sage.libs.pari
sage: A.<T> = PolynomialRing(Integers(5), sparse=True)
sage: f = T^2 + 1; B = A.quo(f)
sage: C.<s> = PolynomialRing(B)
sage: C
Univariate Polynomial Ring in s over Univariate Quotient Polynomial Ring in Tbar
 over Ring of integers modulo 5 with modulus T^2 + 1
sage: s + T
s + Tbar
sage: (s + T)**2
s^2 + 2*Tbar*s + 4

Python

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> A = PolynomialRing(Integers(Integer(5)), sparse=True, names=('T',)); (T,) = A._first_ngens(1)
>>> f = T**Integer(2) + Integer(1); B = A.quo(f)
>>> C = PolynomialRing(B, names=('s',)); (s,) = C._first_ngens(1)
>>> C
Univariate Polynomial Ring in s over Univariate Quotient Polynomial Ring in Tbar
 over Ring of integers modulo 5 with modulus T^2 + 1
>>> s + T
s + Tbar
>>> (s + T)**Integer(2)
s^2 + 2*Tbar*s + 4

Sage Live

# needs sage.libs.pari
A.<T> = PolynomialRing(Integers(5), sparse=True)
f = T^2 + 1; B = A.quo(f)
C.<s> = PolynomialRing(B)
C
s + T
(s + T)**2

coefficients(sparse=True)[source]¶

Return the coefficients of the monomials appearing in self.

EXAMPLES:

Sage

sage: R.<w> = PolynomialRing(Integers(8), sparse=True)
sage: f = 5 + w^1997 - w^10000; f
7*w^10000 + w^1997 + 5
sage: f.coefficients()
[5, 1, 7]

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(8)), sparse=True, names=('w',)); (w,) = R._first_ngens(1)
>>> f = Integer(5) + w**Integer(1997) - w**Integer(10000); f
7*w^10000 + w^1997 + 5
>>> f.coefficients()
[5, 1, 7]

Sage Live

R.<w> = PolynomialRing(Integers(8), sparse=True)
f = 5 + w^1997 - w^10000; f
f.coefficients()

degree(gen=None)[source]¶

Return the degree of this sparse polynomial.

EXAMPLES:

Sage

sage: R.<z> = PolynomialRing(ZZ, sparse=True)
sage: f = 13*z^50000 + 15*z^2 + 17*z
sage: f.degree()
50000

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, sparse=True, names=('z',)); (z,) = R._first_ngens(1)
>>> f = Integer(13)*z**Integer(50000) + Integer(15)*z**Integer(2) + Integer(17)*z
>>> f.degree()
50000

Sage Live

R.<z> = PolynomialRing(ZZ, sparse=True)
f = 13*z^50000 + 15*z^2 + 17*z
f.degree()

dict()[source]¶

Return a new copy of the dict of the underlying elements of self.

EXAMPLES:

Sage

sage: R.<w> = PolynomialRing(Integers(8), sparse=True)
sage: f = 5 + w^1997 - w^10000; f
7*w^10000 + w^1997 + 5
sage: d = f.monomial_coefficients(); d
{0: 5, 1997: 1, 10000: 7}
sage: d[0] = 10
sage: f.monomial_coefficients()
{0: 5, 1997: 1, 10000: 7}

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(8)), sparse=True, names=('w',)); (w,) = R._first_ngens(1)
>>> f = Integer(5) + w**Integer(1997) - w**Integer(10000); f
7*w^10000 + w^1997 + 5
>>> d = f.monomial_coefficients(); d
{0: 5, 1997: 1, 10000: 7}
>>> d[Integer(0)] = Integer(10)
>>> f.monomial_coefficients()
{0: 5, 1997: 1, 10000: 7}

Sage Live

R.<w> = PolynomialRing(Integers(8), sparse=True)
f = 5 + w^1997 - w^10000; f
d = f.monomial_coefficients(); d
d[0] = 10
f.monomial_coefficients()

dict is an alias:

Sage

sage: f.dict()
{0: 5, 1997: 1, 10000: 7}

Python

>>> from sage.all import *
>>> f.dict()
{0: 5, 1997: 1, 10000: 7}

Sage Live

f.dict()

exponents()[source]¶

Return the exponents of the monomials appearing in self.

EXAMPLES:

Sage

sage: R.<w> = PolynomialRing(Integers(8), sparse=True)
sage: f = 5 + w^1997 - w^10000; f
7*w^10000 + w^1997 + 5
sage: f.exponents()
[0, 1997, 10000]

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(8)), sparse=True, names=('w',)); (w,) = R._first_ngens(1)
>>> f = Integer(5) + w**Integer(1997) - w**Integer(10000); f
7*w^10000 + w^1997 + 5
>>> f.exponents()
[0, 1997, 10000]

Sage Live

R.<w> = PolynomialRing(Integers(8), sparse=True)
f = 5 + w^1997 - w^10000; f
f.exponents()

gcd(other, algorithm=None)[source]¶

Return the gcd of this polynomial and other.

INPUT:

other – a polynomial defined over the same ring as this polynomial

ALGORITHM:

Two algorithms are provided:

'generic' – uses the generic implementation, which depends on the base ring being a UFD or a field
'dense' – the polynomials are converted to the dense representation, their gcd is computed and is converted back to the sparse representation

Default is 'dense' for polynomials over \(\ZZ\) and 'generic' in the other cases.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ, sparse=True)
sage: p = x^6 + 7*x^5 + 8*x^4 + 6*x^3 + 2*x^2 + x + 2
sage: q = 2*x^4 - x^3 - 2*x^2 - 4*x - 1
sage: gcd(p, q)
x^2 + x + 1
sage: gcd(p, q, algorithm='dense')
x^2 + x + 1
sage: gcd(p, q, algorithm='generic')
x^2 + x + 1
sage: gcd(p, q, algorithm='foobar')
Traceback (most recent call last):
...
ValueError: Unknown algorithm 'foobar'

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, sparse=True, names=('x',)); (x,) = R._first_ngens(1)
>>> p = x**Integer(6) + Integer(7)*x**Integer(5) + Integer(8)*x**Integer(4) + Integer(6)*x**Integer(3) + Integer(2)*x**Integer(2) + x + Integer(2)
>>> q = Integer(2)*x**Integer(4) - x**Integer(3) - Integer(2)*x**Integer(2) - Integer(4)*x - Integer(1)
>>> gcd(p, q)
x^2 + x + 1
>>> gcd(p, q, algorithm='dense')
x^2 + x + 1
>>> gcd(p, q, algorithm='generic')
x^2 + x + 1
>>> gcd(p, q, algorithm='foobar')
Traceback (most recent call last):
...
ValueError: Unknown algorithm 'foobar'

Sage Live

R.<x> = PolynomialRing(ZZ, sparse=True)
p = x^6 + 7*x^5 + 8*x^4 + 6*x^3 + 2*x^2 + x + 2
q = 2*x^4 - x^3 - 2*x^2 - 4*x - 1
gcd(p, q)
gcd(p, q, algorithm='dense')
gcd(p, q, algorithm='generic')
gcd(p, q, algorithm='foobar')

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

sage: R.<x> = PolynomialRing(ZZ, sparse=True)
sage: (1 + 3*x^10 - 2*x^100).integral()
-2/101*x^101 + 3/11*x^11 + x

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, sparse=True, names=('x',)); (x,) = R._first_ngens(1)
>>> (Integer(1) + Integer(3)*x**Integer(10) - Integer(2)*x**Integer(100)).integral()
-2/101*x^101 + 3/11*x^11 + x

Sage Live

R.<x> = PolynomialRing(ZZ, sparse=True)
(1 + 3*x^10 - 2*x^100).integral()

list(copy=True)[source]¶

Return a new copy of the list of the underlying elements of self.

EXAMPLES:

Sage

sage: R.<z> = PolynomialRing(Integers(100), sparse=True)
sage: f = 13*z^5 + 15*z^2 + 17*z
sage: f.list()
[0, 17, 15, 0, 0, 13]

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(100)), sparse=True, names=('z',)); (z,) = R._first_ngens(1)
>>> f = Integer(13)*z**Integer(5) + Integer(15)*z**Integer(2) + Integer(17)*z
>>> f.list()
[0, 17, 15, 0, 0, 13]

Sage Live

R.<z> = PolynomialRing(Integers(100), sparse=True)
f = 13*z^5 + 15*z^2 + 17*z
f.list()

monomial_coefficients()[source]¶

Return a new copy of the dict of the underlying elements of self.

EXAMPLES:

Sage

sage: R.<w> = PolynomialRing(Integers(8), sparse=True)
sage: f = 5 + w^1997 - w^10000; f
7*w^10000 + w^1997 + 5
sage: d = f.monomial_coefficients(); d
{0: 5, 1997: 1, 10000: 7}
sage: d[0] = 10
sage: f.monomial_coefficients()
{0: 5, 1997: 1, 10000: 7}

Python

>>> from sage.all import *
>>> R = PolynomialRing(Integers(Integer(8)), sparse=True, names=('w',)); (w,) = R._first_ngens(1)
>>> f = Integer(5) + w**Integer(1997) - w**Integer(10000); f
7*w^10000 + w^1997 + 5
>>> d = f.monomial_coefficients(); d
{0: 5, 1997: 1, 10000: 7}
>>> d[Integer(0)] = Integer(10)
>>> f.monomial_coefficients()
{0: 5, 1997: 1, 10000: 7}

Sage Live

R.<w> = PolynomialRing(Integers(8), sparse=True)
f = 5 + w^1997 - w^10000; f
d = f.monomial_coefficients(); d
d[0] = 10
f.monomial_coefficients()

dict is an alias:

Sage

sage: f.dict()
{0: 5, 1997: 1, 10000: 7}

Python

>>> from sage.all import *
>>> f.dict()
{0: 5, 1997: 1, 10000: 7}

Sage Live

f.dict()

number_of_terms()[source]¶

Return the number of nonzero terms.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ, sparse=True)
sage: p = x^100 - 3*x^10 + 12
sage: p.number_of_terms()
3

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, sparse=True, names=('x',)); (x,) = R._first_ngens(1)
>>> p = x**Integer(100) - Integer(3)*x**Integer(10) + Integer(12)
>>> p.number_of_terms()
3

Sage Live

R.<x> = PolynomialRing(ZZ, sparse=True)
p = x^100 - 3*x^10 + 12
p.number_of_terms()

quo_rem(other)[source]¶

Return the quotient and remainder of the Euclidean division of self and other.

Raises ZeroDivisionError if other is zero.

Raises ArithmeticError if other has a nonunit leading coefficient and this causes the Euclidean division to fail.

EXAMPLES:

Sage

sage: P.<x> = PolynomialRing(ZZ, sparse=True)
sage: R.<y> = PolynomialRing(P, sparse=True)
sage: f = R.random_element(10)
sage: while x.divides(f.leading_coefficient()):
....:     f = R.random_element(10)
sage: g = y^5 + R.random_element(4)
sage: q, r = f.quo_rem(g)
sage: f == q*g + r and r.degree() < g.degree()
True
sage: g = x*y^5
sage: f.quo_rem(g)
Traceback (most recent call last):
...
ArithmeticError: Division non exact
(consider coercing to polynomials over the fraction field)
sage: g = 0
sage: f.quo_rem(g)
Traceback (most recent call last):
...
ZeroDivisionError: Division by zero polynomial

Python

>>> from sage.all import *
>>> P = PolynomialRing(ZZ, sparse=True, names=('x',)); (x,) = P._first_ngens(1)
>>> R = PolynomialRing(P, sparse=True, names=('y',)); (y,) = R._first_ngens(1)
>>> f = R.random_element(Integer(10))
>>> while x.divides(f.leading_coefficient()):
...     f = R.random_element(Integer(10))
>>> g = y**Integer(5) + R.random_element(Integer(4))
>>> q, r = f.quo_rem(g)
>>> f == q*g + r and r.degree() < g.degree()
True
>>> g = x*y**Integer(5)
>>> f.quo_rem(g)
Traceback (most recent call last):
...
ArithmeticError: Division non exact
(consider coercing to polynomials over the fraction field)
>>> g = Integer(0)
>>> f.quo_rem(g)
Traceback (most recent call last):
...
ZeroDivisionError: Division by zero polynomial

Sage Live

P.<x> = PolynomialRing(ZZ, sparse=True)
R.<y> = PolynomialRing(P, sparse=True)
f = R.random_element(10)
while x.divides(f.leading_coefficient()):
    f = R.random_element(10)
g = y^5 + R.random_element(4)
q, r = f.quo_rem(g)
f == q*g + r and r.degree() < g.degree()
g = x*y^5
f.quo_rem(g)
g = 0
f.quo_rem(g)

If the leading coefficient of other is not a unit, Euclidean division may still work:

Sage

sage: f = -x*y^10 + 2*x*y^7 + y^3 - 2*x^2*y^2 - y
sage: g = x*y^5
sage: f.quo_rem(g)
(-y^5 + 2*y^2, y^3 - 2*x^2*y^2 - y)

Python

>>> from sage.all import *
>>> f = -x*y**Integer(10) + Integer(2)*x*y**Integer(7) + y**Integer(3) - Integer(2)*x**Integer(2)*y**Integer(2) - y
>>> g = x*y**Integer(5)
>>> f.quo_rem(g)
(-y^5 + 2*y^2, y^3 - 2*x^2*y^2 - y)

Sage Live

f = -x*y^10 + 2*x*y^7 + y^3 - 2*x^2*y^2 - y
g = x*y^5
f.quo_rem(g)

Polynomials over noncommutative rings are also allowed:

Sage

sage: # needs sage.combinat sage.modules
sage: HH = QuaternionAlgebra(QQ, -1, -1)
sage: P.<x> = PolynomialRing(HH, sparse=True)
sage: f = P.random_element(5)
sage: g = P.random_element((0, 5))
sage: q, r = f.quo_rem(g)
sage: f == q*g + r
True

Python

>>> from sage.all import *
>>> # needs sage.combinat sage.modules
>>> HH = QuaternionAlgebra(QQ, -Integer(1), -Integer(1))
>>> P = PolynomialRing(HH, sparse=True, names=('x',)); (x,) = P._first_ngens(1)
>>> f = P.random_element(Integer(5))
>>> g = P.random_element((Integer(0), Integer(5)))
>>> q, r = f.quo_rem(g)
>>> f == q*g + r
True

Sage Live

# needs sage.combinat sage.modules
HH = QuaternionAlgebra(QQ, -1, -1)
P.<x> = PolynomialRing(HH, sparse=True)
f = P.random_element(5)
g = P.random_element((0, 5))
q, r = f.quo_rem(g)
f == q*g + r

AUTHORS:

Bruno Grenet (2014-07-09)

reverse(degree=None)[source]¶

Return this polynomial but with the coefficients reversed.

If an optional degree argument is given, the coefficient list will be truncated or zero padded as necessary and the reverse polynomial will have the specified degree.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ, sparse=True)
sage: p = x^4 + 2*x^2^100
sage: p.reverse()
x^1267650600228229401496703205372 + 2
sage: p.reverse(10)
x^6

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, sparse=True, names=('x',)); (x,) = R._first_ngens(1)
>>> p = x**Integer(4) + Integer(2)*x**Integer(2)**Integer(100)
>>> p.reverse()
x^1267650600228229401496703205372 + 2
>>> p.reverse(Integer(10))
x^6

Sage Live

R.<x> = PolynomialRing(ZZ, sparse=True)
p = x^4 + 2*x^2^100
p.reverse()
p.reverse(10)

shift(n)[source]¶

Return this polynomial multiplied by the power \(x^n\).

If \(n\) is negative, terms below \(x^n\) will be discarded. Does not change this polynomial.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ, sparse=True)
sage: p = x^100000 + 2*x + 4
sage: type(p)
<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_integral_domain_with_category.element_class'>
sage: p.shift(0)
 x^100000 + 2*x + 4
sage: p.shift(-1)
 x^99999 + 2
sage: p.shift(-100002)
 0
sage: p.shift(2)
 x^100002 + 2*x^3 + 4*x^2

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, sparse=True, names=('x',)); (x,) = R._first_ngens(1)
>>> p = x**Integer(100000) + Integer(2)*x + Integer(4)
>>> type(p)
<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_integral_domain_with_category.element_class'>
>>> p.shift(Integer(0))
 x^100000 + 2*x + 4
>>> p.shift(-Integer(1))
 x^99999 + 2
>>> p.shift(-Integer(100002))
 0
>>> p.shift(Integer(2))
 x^100002 + 2*x^3 + 4*x^2

Sage Live

R.<x> = PolynomialRing(ZZ, sparse=True)
p = x^100000 + 2*x + 4
type(p)
p.shift(0)
p.shift(-1)
p.shift(-100002)
p.shift(2)

AUTHOR: - David Harvey (2006-08-06)

truncate(n)[source]¶

Return the polynomial of degree \(< n\) equal to self modulo \(x^n\).

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ, sparse=True)
sage: (x^11 + x^10 + 1).truncate(11)
x^10 + 1
sage: (x^2^500 + x^2^100 + 1).truncate(2^101)
x^1267650600228229401496703205376 + 1

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, sparse=True, names=('x',)); (x,) = R._first_ngens(1)
>>> (x**Integer(11) + x**Integer(10) + Integer(1)).truncate(Integer(11))
x^10 + 1
>>> (x**Integer(2)**Integer(500) + x**Integer(2)**Integer(100) + Integer(1)).truncate(Integer(2)**Integer(101))
x^1267650600228229401496703205376 + 1

Sage Live

R.<x> = PolynomialRing(ZZ, sparse=True)
(x^11 + x^10 + 1).truncate(11)
(x^2^500 + x^2^100 + 1).truncate(2^101)

valuation(p=None)[source]¶

Return the valuation of self.

EXAMPLES:

Sage

sage: # needs sage.rings.finite_rings
sage: R.<w> = PolynomialRing(GF(9, 'a'), sparse=True)
sage: f = w^1997 - w^10000
sage: f.valuation()
1997
sage: R(19).valuation()
0
sage: R(0).valuation()
+Infinity

Python

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> R = PolynomialRing(GF(Integer(9), 'a'), sparse=True, names=('w',)); (w,) = R._first_ngens(1)
>>> f = w**Integer(1997) - w**Integer(10000)
>>> f.valuation()
1997
>>> R(Integer(19)).valuation()
0
>>> R(Integer(0)).valuation()
+Infinity

Sage Live

# needs sage.rings.finite_rings
R.<w> = PolynomialRing(GF(9, 'a'), sparse=True)
f = w^1997 - w^10000
f.valuation()
R(19).valuation()
R(0).valuation()

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_sparse_cdv(parent, x=None, check=True, is_gen=False, construct=False)[source]¶: Bases: Polynomial_generic_sparse, Polynomial_generic_cdv

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_sparse_cdvf(parent, x=None, check=True, is_gen=False, construct=False)[source]¶: Bases: Polynomial_generic_sparse_cdv, Polynomial_generic_cdvf

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_sparse_cdvr(parent, x=None, check=True, is_gen=False, construct=False)[source]¶: Bases: Polynomial_generic_sparse_cdv, Polynomial_generic_cdvr

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_sparse_field(parent, x=None, check=True, is_gen=False, construct=False)[source]¶

Bases: Polynomial_generic_sparse, Polynomial_generic_field

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(Frac(RR['t']), sparse=True)
sage: f = x^3 - x + 17
sage: type(f)
<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_field_with_category.element_class'>
sage: loads(f.dumps()) == f
True

Python

>>> from sage.all import *
>>> R = PolynomialRing(Frac(RR['t']), sparse=True, names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(3) - x + Integer(17)
>>> type(f)
<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_field_with_category.element_class'>
>>> loads(f.dumps()) == f
True

Sage Live

R.<x> = PolynomialRing(Frac(RR['t']), sparse=True)
f = x^3 - x + 17
type(f)
loads(f.dumps()) == f