# 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)
class sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_domain(parent, is_gen=False, construct=False)
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)
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

sage: zero = R.zero()
sage: zero.gcd(2*x)
x
sage: (2*x).gcd(zero)
x
sage: zero.gcd(zero)
0

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


TESTS:

We check that the behavior of xgcd with zero elements is compatible with gcd (trac ticket #17671):

sage: R.<x> = QQbar[]
sage: zero = R.zero()
sage: zero.xgcd(2*x)
(x, 0, 1/2)
sage: (2*x).xgcd(zero)
(x, 1/2, 0)
sage: zero.xgcd(zero)
(0, 0, 0)

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

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

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

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