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)

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)

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

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

sage: f.factor_of_slope(-1)
1 + O(5^20)

AUTHOR:

• Xavier Caruso (2013-03-20)

hensel_lift(a)

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: 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)
sage: g.hensel_lift(2)  # here, 2 is a multiple root modulo p
Traceback (most recent call last):
...
ValueError: a is not close enough to a root of this polynomial

AUTHOR:

• Xavier Caruso (2013-03-23)

newton_polygon()

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

AUTHOR:

• Xavier Caruso (2013-03-20)

newton_slopes(repetition=True)

Returns 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: 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]

AUTHOR:

• Xavier Caruso (2013-03-20)

slope_factorization()

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

EXAMPLES:

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]

AUTHOR:

• Xavier Caruso (2013-03-20)

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_cdvf(parent, is_gen=False, construct=False)

Bases: Polynomial_generic_cdv, Polynomial_generic_field

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_cdvr(parent, is_gen=False, construct=False)

Bases: Polynomial_generic_cdv

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_dense_cdv

Bases: Polynomial_generic_dense_inexact, Polynomial_generic_cdv

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_dense_cdvf

Bases: Polynomial_generic_dense_cdv, Polynomial_generic_cdvf

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_dense_cdvr

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)

Bases: Polynomial_generic_dense, Polynomial_generic_field

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_domain(parent, is_gen=False, construct=False)

Bases: Polynomial, IntegralDomainElement

is_unit()

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

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_field(parent, is_gen=False, construct=False)

Bases: Polynomial_singular_repr, Polynomial_generic_domain, EuclideanDomainElement

quo_rem(other)

Returns a tuple (quotient, remainder) where

self = quotient * other + remainder.

EXAMPLES:

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)

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

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

A more extensive example:

sage: A.<T> = PolynomialRing(Integers(5),sparse=True) ; 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

coefficients(sparse=True)

Return the coefficients of the monomials appearing in self.

EXAMPLES:

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]

degree(gen=None)

Return the degree of this sparse polynomial.

EXAMPLES:

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

dict()

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

EXAMPLES:

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.dict(); d
{0: 5, 1997: 1, 10000: 7}
sage: d[0] = 10
sage: f.dict()
{0: 5, 1997: 1, 10000: 7}

exponents()

Return the exponents of the monomials appearing in self.

EXAMPLES:

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]

gcd(other, algorithm=None)

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

integral(var=None)

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

list(copy=True)

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

EXAMPLES:

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]

number_of_terms()

Return the number of nonzero terms.

EXAMPLES:

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

quo_rem(other)

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

Raises ZerodivisionError if other is zero.

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

EXAMPLES:

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

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

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)

Polynomials over noncommutative rings are also allowed:

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

AUTHORS:

• Bruno Grenet (2014-07-09)

reverse(degree=None)

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

shift(n)

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

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

truncate(n)

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

EXAMPLES:

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

valuation(p=None)

Return the valuation of self.

EXAMPLES:

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

class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_sparse_cdv(parent, x=None, check=True, is_gen=False, construct=False)

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)

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)

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)

Bases: Polynomial_generic_sparse, Polynomial_generic_field

EXAMPLES:

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