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)

TESTS:

We test coercion in a particularly complicated situation:

sage: W.<w>=QQ['w']
sage: WZ.<z>=W['z']
sage: m = matrix(WZ,2,2,[1,z,z,z^2])
sage: a = m.charpoly()
sage: R.<x> = WZ[]
sage: R(a)
x^2 + (-z^2 - 1)*x
class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_dense_field(parent, x=None, check=True, is_gen=False, construct=False)

Bases: sage.rings.polynomial.polynomial_element.Polynomial_generic_dense, sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_field

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

Bases: sage.rings.polynomial.polynomial_element.Polynomial, sage.structure.element.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: sage.rings.polynomial.polynomial_singular_interface.Polynomial_singular_repr, sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_domain, sage.structure.element.EuclideanDomainElement

gcd(other)

Return the greatest common divisor of this polynomial and other, as a monic polynomial.

INPUT:

  • other – a polynomial defined over the same ring as self

EXAMPLES:

sage: R.<x> = QQbar[]
sage: (2*x).gcd(2*x^2)
x
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)
xgcd(other)

Extended gcd of self and polynomial other.

INPUT:

  • other – a polynomial defined over the same ring as self

OUTPUT:

Polynomials g, u, and v such that g = u * self + v * other.

EXAMPLES:

sage: P.<x> = QQ[]
sage: F = (x^2 + 2)*x^3; G = (x^2+2)*(x-3)
sage: g, u, v = F.xgcd(G)
sage: g, u, v
(x^2 + 2, 1/27, -1/27*x^2 - 1/9*x - 1/3)
sage: u*F + v*G
x^2 + 2
sage: g, u, v = x.xgcd(P(0)); g, u, v
(x, 1, 0)
sage: g == u*x + v*P(0)
True
sage: g, u, v = P(0).xgcd(x); g, u, v
(x, 0, 1)
sage: g == u*P(0) + v*x
True
class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_sparse(parent, x=None, check=True, is_gen=False, construct=False)

Bases: sage.rings.polynomial.polynomial_element.Polynomial

A generic sparse polynomial.

EXAMPLES:

sage: R.<x> = PolynomialRing(PolynomialRing(QQ, 'y'), sparse=True)
sage: f = x^3 - x + 17
sage: type(f)
<class 'sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_sparse'>
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()

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

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]
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.

EXAMPLES:

sage: P.<x> = PolynomialRing(ZZ,sparse=True)
sage: R.<y> = PolynomialRing(P,sparse=True)
sage: f = R.random_element(10)
sage: g = y^5+R.random_element(4)
sage: q,r = f.quo_rem(g)
sage: f == q*g + r and r.degree() < g.degree()
True
sage: g = x*y^5
sage: f.quo_rem(g)
Traceback (most recent call last):
...
ArithmeticError: Nonunit leading coefficient
sage: g = 0
sage: f.quo_rem(g)
Traceback (most recent call last):
...
ZeroDivisionError: Division by zero polynomial

TESTS:

sage: P.<x> = PolynomialRing(ZZ,sparse=True)
sage: f = x^10-4*x^6-5
sage: g = 17*x^22+x^15-3*x^5+1
sage: q,r = g.quo_rem(f)
sage: g == f*q + r and r.degree() < f.degree()
True
sage: zero = P(0)
sage: zero.quo_rem(f)
(0, 0)
sage: Q.<y> = IntegerModRing(14)[]
sage: f = y^10-4*y^6-5
sage: g = 17*y^22+y^15-3*y^5+1
sage: q,r = g.quo_rem(f)
sage: g == f*q + r and r.degree() < f.degree()
True
sage: f += 2*y^10 # 3 is invertible mod 14
sage: q,r = g.quo_rem(f)
sage: g == f*q + r and r.degree() < f.degree()
True

AUTHORS:

  • Bruno Grenet (2014-07-09)
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_element_generic.Polynomial_generic_sparse'>
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)

valuation()

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_field(parent, x=None, check=True, is_gen=False, construct=False)

Bases: sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_sparse, sage.rings.polynomial.polynomial_element_generic.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_element_generic.Polynomial_generic_sparse_field'>
sage: loads(f.dumps()) == f
True

Previous topic

Univariate Polynomial Base Class

Next topic

Univariate Polynomials over GF(2) via NTL’s GF2X.

This Page