Univariate Ore polynomials#

This module provides the OrePolynomial, which constructs a single univariate Ore polynomial over a commutative base equipped with an endomorphism and/or a derivation. It provides generic implementation of standard arithmetical operations on Ore polynomials as addition, multiplication, gcd, lcm, etc.

The generic implementation of dense Ore polynomials is OrePolynomial_generic_dense. The classes ConstantOrePolynomialSection and OrePolynomialBaseringInjection handle conversion from an Ore polynomial ring to its base ring and vice versa.

AUTHORS:

Xavier Caruso (2020-05)

class sage.rings.polynomial.ore_polynomial_element.ConstantOrePolynomialSection#

Bases: Map

Representation of the canonical homomorphism from the constants of an Ore polynomial ring to the base ring.

This class is necessary for automatic coercion from zero-degree Ore polynomial ring into the base ring.

EXAMPLES:

sage: from sage.rings.polynomial.ore_polynomial_element import ConstantOrePolynomialSection
sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: m = ConstantOrePolynomialSection(S, R); m
Generic map:
    From: Ore Polynomial Ring in x over Univariate Polynomial Ring in t
          over Rational Field twisted by t |--> t + 1
    To:   Univariate Polynomial Ring in t over Rational Field

class sage.rings.polynomial.ore_polynomial_element.OrePolynomial#

Bases: AlgebraElement

Abstract base class for Ore polynomials.

This class must be inherited from and have key methods overridden.

Definition

Let \(R\) be a commutative ring equipped with an automorphism \(\sigma\) and a \(\sigma\)-derivation \(\partial\).

An Ore polynomial is given by the equation:

\[F(X) = a_{n} X^{n} + \cdots + a_0,\]

where the coefficients \(a_i \in R\) and \(X\) is a formal variable.

Addition between two Ore polynomials is defined by the usual addition operation and the modified multiplication is defined by the rule \(X a = \sigma(a) X + \partial(a)\) for all \(a\) in \(R\). Ore polynomials are thus non-commutative and the degree of a product is equal to the sum of the degrees of the factors.

Let \(a\) and \(b\) be two Ore polynomials in the same ring \(S\). The right (resp. left) Euclidean division of \(a\) by \(b\) is a couple \((q,r)\) of elements in \(S\) such that

\(a = q b + r\) (resp. \(a = b q + r\))
the degree of \(r\) is less than the degree of \(b\)

\(q\) (resp. \(r\)) is called the quotient (resp. the remainder) of this Euclidean division.

Properties

Keeping the previous notation, if the leading coefficient of \(b\) is a unit (e.g. if \(b\) is monic) then the quotient and the remainder in the right Euclidean division exist and are unique.

The same result holds for the left Euclidean division if in addition the twisting morphism defining the Ore polynomial ring is invertible.

EXAMPLES:

We illustrate some functionalities implemented in this class.

We create the Ore polynomial ring (here the derivation is zero):

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]; S
Ore Polynomial Ring in x over Univariate Polynomial Ring in t over Integer Ring
 twisted by t |--> t + 1

and some elements in it:

sage: a = t + x + 1; a
x + t + 1
sage: b = S([t^2,t+1,1]); b
x^2 + (t + 1)*x + t^2
sage: c = S.random_element(degree=3,monic=True)
sage: c.parent() is S
True

Ring operations are supported:

sage: a + b
x^2 + (t + 2)*x + t^2 + t + 1
sage: a - b
-x^2 - t*x - t^2 + t + 1

sage: a * b
x^3 + (2*t + 3)*x^2 + (2*t^2 + 4*t + 2)*x + t^3 + t^2
sage: b * a
x^3 + (2*t + 4)*x^2 + (2*t^2 + 3*t + 2)*x + t^3 + t^2
sage: a * b == b * a
False

sage: b^2
x^4 + (2*t + 4)*x^3 + (3*t^2 + 7*t + 6)*x^2
 + (2*t^3 + 4*t^2 + 3*t + 1)*x + t^4
sage: b^2 == b*b
True

Sage also implements arithmetic over Ore polynomial rings. You will find below a short panorama:

sage: q,r = c.right_quo_rem(b)
sage: c == q*b + r
True

The operators // and % give respectively the quotient and the remainder of the right Euclidean division:

sage: q == c // b
True
sage: r == c % b
True

Here we can see the effect of the operator evaluation compared to the usual polynomial evaluation:

sage: a = x^2
sage: a(t)
doctest:...: FutureWarning: This class/method/function is marked as experimental.
It, its functionality or its interface might change without a formal deprecation.
See https://github.com/sagemath/sage/issues/13215 for details.
t + 2

Here is another example over a finite field:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x^4 + (4*t + 1)*x^3 + (t^2 + 3*t + 3)*x^2 + (3*t^2 + 2*t + 2)*x + (3*t^2 + 3*t + 1)
sage: b = (2*t^2 + 3)*x^2 + (3*t^2 + 1)*x + 4*t + 2
sage: q, r = a.left_quo_rem(b)
sage: q
(4*t^2 + t + 1)*x^2 + (2*t^2 + 2*t + 2)*x + 2*t^2 + 4*t + 3
sage: r
(t + 2)*x + 3*t^2 + 2*t + 4
sage: a == b*q + r
True

Once we have Euclidean divisions, we have for free gcd and lcm (at least if the base ring is a field):

sage: # needs sage.rings.finite_rings
sage: a = (x + t) * (x + t^2)^2
sage: b = (x + t) * (t*x + t + 1) * (x + t^2)
sage: a.right_gcd(b)
x + t^2
sage: a.left_gcd(b)
x + t

The left lcm has the following meaning: given Ore polynomials \(a\) and \(b\), their left lcm is the least degree polynomial \(c = ua = vb\) for some Ore polynomials \(u, v\). Such a \(c\) always exist if the base ring is a field:

sage: c = a.left_lcm(b); c                                                      # needs sage.rings.finite_rings
x^5 + (4*t^2 + t + 3)*x^4 + (3*t^2 + 4*t)*x^3 + 2*t^2*x^2 + (2*t^2 + t)*x + 4*t^2 + 4
sage: c.is_right_divisible_by(a)                                                # needs sage.rings.finite_rings
True
sage: c.is_right_divisible_by(b)                                                # needs sage.rings.finite_rings
True

The right lcm is defined similarly as the least degree polynomial \(c = au = bv\) for some \(u,v\):

sage: d = a.right_lcm(b); d                                                     # needs sage.rings.finite_rings
x^5 + (t^2 + 1)*x^4 + (3*t^2 + 3*t + 3)*x^3 + (3*t^2 + t + 2)*x^2 + (4*t^2 + 3*t)*x + 4*t + 4
sage: d.is_left_divisible_by(a)                                                 # needs sage.rings.finite_rings
True
sage: d.is_left_divisible_by(b)                                                 # needs sage.rings.finite_rings
True

See also

sage.rings.polynomial.ore_polynomial_ring

base_ring()#

Return the base ring of self.

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = S.random_element()
sage: a.base_ring()
Univariate Polynomial Ring in t over Integer Ring
sage: a.base_ring() is R
True

change_variable_name(var)#

Change the name of the variable of self.

This will create the Ore polynomial ring with the new name but same base ring, twisting morphism and twisting derivation. The returned Ore polynomial will be an element of that Ore polynomial ring.

INPUT:

var – the name of the new variable

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x', sigma]
sage: a = x^3 + (2*t + 1)*x  + t^2 + 3*t + 5
sage: b = a.change_variable_name('y'); b
y^3 + (2*t + 1)*y  + t^2 + 3*t + 5

Note that a new parent is created at the same time:

sage: b.parent()
Ore Polynomial Ring in y over Univariate Polynomial Ring in t over Integer Ring
 twisted by t |--> t + 1

coefficients(sparse=True)#

Return the coefficients of the monomials appearing in self.

If sparse=True (the default), return only the non-zero coefficients. Otherwise, return the same value as self.list().

Note

This should be overridden in subclasses.

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = 1 + x^4 + (t+1)*x^2 + t^2
sage: a.coefficients()
[t^2 + 1, t + 1, 1]
sage: a.coefficients(sparse=False)
[t^2 + 1, 0, t + 1, 0, 1]

constant_coefficient()#

Return the constant coefficient (i.e., the coefficient of term of degree \(0\)) of self.

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = x + t^2 + 2
sage: a.constant_coefficient()
t^2 + 2

degree()#

Return the degree of self.

By convention, the zero Ore polynomial has degree \(-1\).

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = x^2 + t*x^3 + t^2*x + 1
sage: a.degree()
3
sage: S.zero().degree()
-1
sage: S(5).degree()
0

exponents()#

Return the exponents of the monomials appearing in self.

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = 1 + x^4 + (t+1)*x^2 + t^2
sage: a.exponents()
[0, 2, 4]

hamming_weight()#

Return the number of non-zero coefficients of self.

This is also known as the weight, hamming weight or sparsity.

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = 1 + x^4 + (t+1)*x^2 + t^2
sage: a.number_of_terms()
3

This is also an alias for hamming_weight:

sage: a.hamming_weight()
3

is_constant()#

Return whether self is a constant polynomial.

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: R(2).is_constant()
True
sage: (x + 1).is_constant()
False

is_left_divisible_by(other)#

Check if self is divisible by other on the left.

INPUT:

other – an Ore polynomial in the same ring as self

OUTPUT:

Return True or False.

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x^2 + t*x + t^2 + 3
sage: b = x^3 + (t + 1)*x^2 + 1
sage: c = a*b
sage: c.is_left_divisible_by(a)
True
sage: c.is_left_divisible_by(b)
False

Divisibility by \(0\) does not make sense:

sage: c.is_left_divisible_by(S(0))                                          # needs sage.rings.finite_rings
Traceback (most recent call last):
...
ZeroDivisionError: division by zero is not valid

is_monic()#

Return True if this Ore polynomial is monic.

The zero polynomial is by definition not monic.

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = x + t
sage: a.is_monic()
True
sage: a = 0*x
sage: a.is_monic()
False
sage: a = t*x^3 + x^4 + (t+1)*x^2
sage: a.is_monic()
True
sage: a = (t^2 + 2*t)*x^2 + x^3 + t^10*x^5
sage: a.is_monic()
False

is_monomial()#

Return True if self is a monomial, i.e., a power of the generator.

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: x.is_monomial()
True
sage: (x+1).is_monomial()
False
sage: (x^2).is_monomial()
True
sage: S(1).is_monomial()
True

The coefficient must be 1:

sage: (2*x^5).is_monomial()
False
sage: S(t).is_monomial()
False

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

sage: (2*x^5).is_term()
True
sage: S(t).is_term()
True

is_nilpotent()#

Check if self is nilpotent.

Note

The paper “Nilpotents and units in skew polynomial rings over commutative rings” by M. Rimmer and K.R. Pearson describes a method to check whether a given skew polynomial is nilpotent. That method however, requires one to know the order of the automorphism which is not available in Sage. This method is thus not yet implemented.

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: x.is_nilpotent()
Traceback (most recent call last):
...
NotImplementedError

is_one()#

Test whether this polynomial is \(1\).

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: R(1).is_one()
True
sage: (x + 3).is_one()
False

is_right_divisible_by(other)#

Check if self is divisible by other on the right.

INPUT:

other – an Ore polynomial in the same ring as self

OUTPUT:

Return True or False.

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x^2 + t*x + t^2 + 3
sage: b = x^3 + (t + 1)*x^2 + 1
sage: c = a*b
sage: c.is_right_divisible_by(a)
False
sage: c.is_right_divisible_by(b)
True

Divisibility by \(0\) does not make sense:

sage: c.is_right_divisible_by(S(0))                                         # needs sage.rings.finite_rings
Traceback (most recent call last):
...
ZeroDivisionError: division by zero is not valid

This function does not work if the leading coefficient of the divisor is not a unit:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = x^2 + 2*x + t
sage: b = (t+1)*x + t^2
sage: c = a*b
sage: c.is_right_divisible_by(b)
Traceback (most recent call last):
...
NotImplementedError: the leading coefficient of the divisor is not invertible

is_term()#

Return True if self is an element of the base ring times a power of the generator.

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: x.is_term()
True
sage: R(1).is_term()
True
sage: (3*x^5).is_term()
True
sage: (1+3*x^5).is_term()
False

If you want to test that self also has leading coefficient 1, use is_monomial() instead:

sage: (3*x^5).is_monomial()
False

is_unit()#

Return True if this Ore polynomial is a unit.

When the base ring \(R\) is an integral domain, then an Ore polynomial \(f\) is a unit if and only if degree of \(f\) is \(0\) and \(f\) is then a unit in \(R\).

Note

The case when \(R\) is not an integral domain is not yet implemented.

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = x + (t+1)*x^5 + t^2*x^3 - x^5
sage: a.is_unit()
False

is_zero()#

Return True if self is the zero polynomial.

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = x + 1
sage: a.is_zero()
False
sage: b = S.zero()
sage: b.is_zero()
True

leading_coefficient()#

Return the coefficient of the highest-degree monomial of self.

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = (t+1)*x^5 + t^2*x^3 + x
sage: a.leading_coefficient()
t + 1

By convention, the leading coefficient to the zero polynomial is zero:

sage: S(0).leading_coefficient()
0

left_divides(other)#

Check if self divides other on the left.

INPUT:

other – an Ore polynomial in the same ring as self

OUTPUT:

Return True or False.

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x^2 + t*x + t^2 + 3
sage: b = x^3 + (t + 1)*x^2 + 1
sage: c = a * b
sage: a.left_divides(c)
True
sage: b.left_divides(c)
False

Divisibility by \(0\) does not make sense:

sage: S(0).left_divides(c)                                                  # needs sage.rings.finite_rings
Traceback (most recent call last):
...
ZeroDivisionError: division by zero is not valid

left_gcd(other, monic=True)#

Return the left gcd of self and other.

INPUT:

other – an Ore polynomial in the same ring as self
monic – boolean (default: True); return whether the left gcd should be normalized to be monic

OUTPUT:

The left gcd of self and other, that is an Ore polynomial \(g\) with the following property: any Ore polynomial is divisible on the left by \(g\) iff it is divisible on the left by both self and other. If monic is True, \(g\) is in addition monic. (With this extra condition, it is uniquely determined.)

Note

Works only if following two conditions are fulfilled (otherwise left gcd do not exist in general): 1) the base ring is a field and 2) the twisting morphism is bijective.

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = (x + t) * (x^2 + t*x + 1)
sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2)
sage: a.left_gcd(b)
x + t

Specifying monic=False, we can get a nonmonic gcd:

sage: a.left_gcd(b,monic=False)                                             # needs sage.rings.finite_rings
2*t*x + 4*t + 2

The base ring needs to be a field:

sage: # needs sage.rings.finite_rings
sage: R.<t> = QQ[]
sage: sigma = R.hom([t + 1])
sage: S.<x> = R['x',sigma]
sage: a = (x + t) * (x^2 + t*x + 1)
sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2)
sage: a.left_gcd(b)
Traceback (most recent call last):
...
TypeError: the base ring must be a field

And the twisting morphism needs to be bijective:

sage: # needs sage.rings.finite_rings
sage: FR = R.fraction_field()
sage: f = FR.hom([FR(t)^2])
sage: S.<x> = FR['x',f]
sage: a = (x + t) * (x^2 + t*x + 1)
sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2)
sage: a.left_gcd(b)
Traceback (most recent call last):
...
NotImplementedError: inversion of the twisting morphism Ring endomorphism
of Fraction Field of Univariate Polynomial Ring in t over Rational Field
    Defn: t |--> t^2

left_lcm(other, monic=True)#

Return the left lcm of self and other.

INPUT:

other – an Ore polynomial in the same ring as self
monic – boolean (default: True); return whether the left lcm should be normalized to be monic

OUTPUT:

The left lcm of self and other, that is an Ore polynomial \(l\) with the following property: any Ore polynomial is a left multiple of \(l\) (right divisible by \(l\)) iff it is a left multiple of both self and other (right divisible by self and other). If monic is True, \(l\) is in addition monic. (With this extra condition, it is uniquely determined.)

Note

Works only if the base ring is a field (otherwise left lcm do not exist in general).

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = (x + t^2) * (x + t)
sage: b = 2 * (x^2 + t + 1) * (x * t)
sage: c = a.left_lcm(b); c
x^5 + (2*t^2 + t + 4)*x^4 + (3*t^2 + 4)*x^3 + (3*t^2 + 3*t + 2)*x^2 + (t^2 + t + 2)*x
sage: c.is_right_divisible_by(a)
True
sage: c.is_right_divisible_by(b)
True
sage: a.degree() + b.degree() == c.degree() + a.right_gcd(b).degree()
True

Specifying monic=False, we can get a nonmonic lcm:

sage: a.left_lcm(b,monic=False)                                             # needs sage.rings.finite_rings
(t^2 + t)*x^5 + (4*t^2 + 4*t + 1)*x^4 + (t + 1)*x^3 + (t^2 + 2)*x^2 + (3*t + 4)*x

The base ring needs to be a field:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = (x + t^2) * (x + t)
sage: b = 2 * (x^2 + t + 1) * (x * t)
sage: a.left_lcm(b)
Traceback (most recent call last):
...
TypeError: the base ring must be a field

left_mod(other)#

Return the remainder of left division of self by other.

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = 1 + t*x^2
sage: b = x + 1
sage: a.left_mod(b)
2*t^2 + 4*t

left_monic()#

Return the unique monic Ore polynomial \(m\) which divides this polynomial on the left and has the same degree.

Given an Ore polynomial \(P\) of degree \(n\), its left monic is given by \(P \cdot \sigma^{-n}(1/k)\), where \(k\) is the leading coefficient of \(P\) and \(\sigma\) is the twisting morphism.

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = (3*t^2 + 3*t + 2)*x^3 + (2*t^2 + 3)*x^2 + (4*t^2 + t + 4)*x + 2*t^2 + 2
sage: b = a.left_monic(); b
x^3 + (4*t^2 + 3*t)*x^2 + (4*t + 2)*x + 2*t^2 + 4*t + 3

Check list:

sage: # needs sage.rings.finite_rings
sage: b.degree() == a.degree()
True
sage: a.is_left_divisible_by(b)
True
sage: twist = S.twisting_morphism(-a.degree())
sage: a == b * twist(a.leading_coefficient())
True

Note that \(b\) does not divide \(a\) on the right:

sage: a.is_right_divisible_by(b)                                            # needs sage.rings.finite_rings
False

This function does not work if the leading coefficient is not a unit:

sage: R.<t> = QQ[]
sage: der = R.derivation()
sage: S.<x> = R['x', der]
sage: a = t*x
sage: a.left_monic()
Traceback (most recent call last):
...
NotImplementedError: the leading coefficient is not a unit

left_quo_rem(other)#

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

INPUT:

other – an Ore polynomial in the same ring as self

OUTPUT:

the quotient and the remainder of the left Euclidean division of this Ore polynomial by other

Note

This will fail if the leading coefficient of other is not a unit or if Sage can’t invert the twisting morphism.

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = (3*t^2 + 3*t + 2)*x^3 + (2*t^2 + 3)*x^2 + (4*t^2 + t + 4)*x + 2*t^2 + 2
sage: b = (3*t^2 + 4*t + 2)*x^2 + (2*t^2 + 4*t + 3)*x + 2*t^2 + t + 1
sage: q,r = a.left_quo_rem(b)
sage: a == b*q + r
True

In the following example, Sage does not know the inverse of the twisting morphism:

sage: R.<t> = QQ[]
sage: K = R.fraction_field()
sage: sigma = K.hom([(t+1)/(t-1)])
sage: S.<x> = K['x',sigma]
sage: a = (-2*t^2 - t + 1)*x^3 + (-t^2 + t)*x^2 + (-12*t - 2)*x - t^2 - 95*t + 1
sage: b = x^2 + (5*t - 6)*x - 4*t^2 + 4*t - 1
sage: a.left_quo_rem(b)
Traceback (most recent call last):
...
NotImplementedError: inversion of the twisting morphism Ring endomorphism of Fraction Field of Univariate Polynomial Ring in t over Rational Field
  Defn: t |--> (t + 1)/(t - 1)

left_xgcd(other, monic=True)#

Return the left gcd of self and other along with the coefficients for the linear combination.

If \(a\) is self and \(b\) is other, then there are Ore polynomials \(u\) and \(v\) such that \(g = a u + b v\), where \(g\) is the left gcd of \(a\) and \(b\). This method returns \((g, u, v)\).

INPUT:

other – an Ore polynomial in the same ring as self
monic – boolean (default: True); return whether the left gcd should be normalized to be monic

OUTPUT:

The left gcd of self and other, that is an Ore polynomial \(g\) with the following property: any Ore polynomial is divisible on the left by \(g\) iff it is divisible on the left by both self and other. If monic is True, \(g\) is in addition monic. (With this extra condition, it is uniquely determined.)
Two Ore polynomials \(u\) and \(v\) such that:

\[g = a \cdot u + b \cdot v,\]

where \(s\) is self and \(b\) is other.

Note

Works only if following two conditions are fulfilled (otherwise left gcd do not exist in general): 1) the base ring is a field and 2) the twisting morphism is bijective.

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = (x + t) * (x^2 + t*x + 1)
sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2)
sage: g,u,v = a.left_xgcd(b); g
x + t
sage: a*u + b*v == g
True

Specifying monic=False, we can get a nonmonic gcd:

sage: g,u,v = a.left_xgcd(b, monic=False); g                                # needs sage.rings.finite_rings
2*t*x + 4*t + 2
sage: a*u + b*v == g                                                        # needs sage.rings.finite_rings
True

The base ring must be a field:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = (x + t) * (x^2 + t*x + 1)
sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2)
sage: a.left_xgcd(b)
Traceback (most recent call last):
...
TypeError: the base ring must be a field

And the twisting morphism must be bijective:

sage: FR = R.fraction_field()
sage: f = FR.hom([FR(t)^2])
sage: S.<x> = FR['x',f]
sage: a = (x + t) * (x^2 + t*x + 1)
sage: b = 2 * (x + t) * (x^3 + (t+1)*x^2 + t^2)
sage: a.left_xgcd(b)
Traceback (most recent call last):
...
NotImplementedError: inversion of the twisting morphism Ring endomorphism of Fraction Field of Univariate Polynomial Ring in t over Rational Field
    Defn: t |--> t^2

left_xlcm(other, monic=True)#

Return the left lcm \(L\) of self and other together with two Ore polynomials \(U\) and \(V\) such that

\[U \cdot \text{self} = V \cdot \text{other} = L.\]

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: P = (x + t^2) * (x + t)
sage: Q = 2 * (x^2 + t + 1) * (x * t)
sage: L, U, V = P.left_xlcm(Q)
sage: L
x^5 + (2*t^2 + t + 4)*x^4 + (3*t^2 + 4)*x^3 + (3*t^2 + 3*t + 2)*x^2 + (t^2 + t + 2)*x

sage: U * P == L                                                            # needs sage.rings.finite_rings
True
sage: V * Q == L                                                            # needs sage.rings.finite_rings
True

number_of_terms()#

Return the number of non-zero coefficients of self.

This is also known as the weight, hamming weight or sparsity.

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = 1 + x^4 + (t+1)*x^2 + t^2
sage: a.number_of_terms()
3

This is also an alias for hamming_weight:

sage: a.hamming_weight()
3

padded_list(n=None)#

Return list of coefficients of self up to (but not including) degree \(n\).

Includes \(0`s in the list on the right so that the list always has length exactly `n\).

INPUT:

n – (default: None); if given, an integer that is at least \(0\)

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = 1 + t*x^3 + t^2*x^5
sage: a.padded_list()
[1, 0, 0, t, 0, t^2]
sage: a.padded_list(10)
[1, 0, 0, t, 0, t^2, 0, 0, 0, 0]
sage: len(a.padded_list(10))
10
sage: a.padded_list(3)
[1, 0, 0]
sage: a.padded_list(0)
[]
sage: a.padded_list(-1)
Traceback (most recent call last):
...
ValueError: n must be at least 0

prec()#

Return the precision of self.

This is always infinity, since polynomials are of infinite precision by definition (there is no big-oh).

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: x.prec()
+Infinity

right_divides(other)#

Check if self divides other on the right.

INPUT:

other – an Ore polynomial in the same ring as self

OUTPUT:

Return True or False.

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x^2 + t*x + t^2 + 3
sage: b = x^3 + (t + 1)*x^2 + 1
sage: c = a * b
sage: a.right_divides(c)
False
sage: b.right_divides(c)
True

Divisibility by \(0\) does not make sense:

sage: S(0).right_divides(c)                                                 # needs sage.rings.finite_rings
Traceback (most recent call last):
...
ZeroDivisionError: division by zero is not valid

This function does not work if the leading coefficient of the divisor is not a unit:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = x^2 + 2*x + t
sage: b = (t+1)*x + t^2
sage: c = a*b
sage: b.right_divides(c)
Traceback (most recent call last):
...
NotImplementedError: the leading coefficient of the divisor is not invertible

right_gcd(other, monic=True)#

Return the right gcd of self and other.

INPUT:

other – an Ore polynomial in the same ring as self
monic – boolean (default: True); return whether the right gcd should be normalized to be monic

OUTPUT:

The right gcd of self and other, that is an Ore polynomial \(g\) with the following property: any Ore polynomial is divisible on the right by \(g\) iff it is divisible on the right by both self and other. If monic is True, \(g\) is in addition monic. (With this extra condition, it is uniquely determined.)

Note

Works only if the base ring is a field (otherwise right gcd do not exist in general).

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = (x^2 + t*x + 1) * (x + t)
sage: b = 2 * (x^3 + (t+1)*x^2 + t^2) * (x + t)
sage: a.right_gcd(b)
x + t

Specifying monic=False, we can get a nonmonic gcd:

sage: a.right_gcd(b,monic=False)                                            # needs sage.rings.finite_rings
(4*t^2 + 4*t + 1)*x + 4*t^2 + 4*t + 3

The base ring need to be a field:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = (x^2 + t*x + 1) * (x + t)
sage: b = 2 * (x^3 + (t+1)*x^2 + t^2) * (x + t)
sage: a.right_gcd(b)
Traceback (most recent call last):
...
TypeError: the base ring must be a field

right_lcm(other, monic=True)#

Return the right lcm of self and other.

INPUT:

other – an Ore polynomial in the same ring as self
monic – boolean (default: True); return whether the right lcm should be normalized to be monic

OUTPUT:

The right lcm of self and other, that is an Ore polynomial \(l\) with the following property: any Ore polynomial is a right multiple of \(g\) (left divisible by \(l\)) iff it is a right multiple of both self and other (left divisible by self and other). If monic is True, \(g\) is in addition monic. (With this extra condition, it is uniquely determined.)

Note

Works only if two following conditions are fulfilled (otherwise right lcm do not exist in general): 1) the base ring is a field and 2) the twisting morphism on this field is bijective.

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = (x + t) * (x + t^2)
sage: b = 2 * (x + t) * (x^2 + t + 1)
sage: c = a.right_lcm(b); c
x^4 + (2*t^2 + t + 2)*x^3 + (3*t^2 + 4*t + 1)*x^2 + (3*t^2 + 4*t + 1)*x + t^2 + 4
sage: c.is_left_divisible_by(a)
True
sage: c.is_left_divisible_by(b)
True
sage: a.degree() + b.degree() == c.degree() + a.left_gcd(b).degree()
True

Specifying monic=False, we can get a nonmonic gcd:

sage: a.right_lcm(b,monic=False)                                            # needs sage.rings.finite_rings
2*t*x^4 + (3*t + 1)*x^3 + (4*t^2 + 4*t + 3)*x^2
 + (3*t^2 + 4*t + 2)*x + 3*t^2 + 2*t + 3

The base ring needs to be a field:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = (x + t) * (x + t^2)
sage: b = 2 * (x + t) * (x^2 + t + 1)
sage: a.right_lcm(b)
Traceback (most recent call last):
...
TypeError: the base ring must be a field

And the twisting morphism needs to be bijective:

sage: FR = R.fraction_field()
sage: f = FR.hom([FR(t)^2])
sage: S.<x> = FR['x',f]
sage: a = (x + t) * (x + t^2)
sage: b = 2 * (x + t) * (x^2 + t + 1)
sage: a.right_lcm(b)
Traceback (most recent call last):
...
NotImplementedError: inversion of the twisting morphism Ring endomorphism of
Fraction Field of Univariate Polynomial Ring in t over Rational Field
    Defn: t |--> t^2

right_mod(other)#

Return the remainder of right division of self by other.

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = 1 + t*x^2
sage: b = x + 1
sage: a % b
t + 1
sage: (x^3 + x - 1).right_mod(x^2 - 1)
2*x - 1

right_monic()#

Return the unique monic Ore polynomial which divides this polynomial on the right and has the same degree.

Given an Ore polynomial \(P\) of degree \(n\), its right monic is given by \((1/k) \cdot P\), where \(k\) is the leading coefficient of \(P\).

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = (3*t^2 + 3*t + 2)*x^3 + (2*t^2 + 3)*x^2 + (4*t^2 + t + 4)*x + 2*t^2 + 2
sage: b = a.right_monic(); b
x^3 + (2*t^2 + 3*t + 4)*x^2 + (3*t^2 + 4*t + 1)*x + 2*t^2 + 4*t + 3

Check list:

sage: b.degree() == a.degree()                                              # needs sage.rings.finite_rings
True
sage: a.is_right_divisible_by(b)                                            # needs sage.rings.finite_rings
True
sage: a == a.leading_coefficient() * b                                      # needs sage.rings.finite_rings
True

Note that \(b\) does not divide \(a\) on the right:

sage: a.is_left_divisible_by(b)                                             # needs sage.rings.finite_rings
False

This function does not work if the leading coefficient is not a unit:

sage: R.<t> = QQ[]
sage: der = R.derivation()
sage: S.<x> = R['x', der]
sage: a = t*x
sage: a.right_monic()
Traceback (most recent call last):
...
NotImplementedError: the leading coefficient is not a unit

right_quo_rem(other)#

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

INPUT:

other – an Ore polynomial in the same ring as self

OUTPUT:

the quotient and the remainder of the right Euclidean division of this Ore polynomial by other

Note

This will fail if the leading coefficient of the divisor is not a unit.

EXAMPLES:

sage: R.<t> = ZZ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = S.random_element(degree=4)
sage: b = S.random_element(monic=True)
sage: q,r = a.right_quo_rem(b)
sage: a == q*b + r
True

The leading coefficient of the divisor need to be invertible:

sage: a.right_quo_rem(S(0))
Traceback (most recent call last):
...
ZeroDivisionError: division by zero is not valid
sage: c = S.random_element()
sage: while not c or c.leading_coefficient().is_unit():
....:     c = S.random_element()
sage: while a.degree() < c.degree():
....:     a = S.random_element(degree=4)
sage: a.right_quo_rem(c)
Traceback (most recent call last):
...
NotImplementedError: the leading coefficient of the divisor is not invertible

right_xgcd(other, monic=True)#

Return the right gcd of self and other along with the coefficients for the linear combination.

If \(a\) is self and \(b\) is other, then there are Ore polynomials \(u\) and \(v\) such that \(g = u a + v b\), where \(g\) is the right gcd of \(a\) and \(b\). This method returns \((g, u, v)\).

INPUT:

other – an Ore polynomial in the same ring as self
monic – boolean (default: True); return whether the right gcd should be normalized to be monic

OUTPUT:

The right gcd of self and other, that is an Ore polynomial \(g\) with the following property: any Ore polynomial is divisible on the right by \(g\) iff it is divisible on the right by both self and other. If monic is True, \(g\) is in addition monic. (With this extra condition, it is uniquely determined.)
Two Ore polynomials \(u\) and \(v\) such that:

\[g = u \cdot a + v \cdot b\]

where \(a\) is self and \(b\) is other.

Note

Works only if the base ring is a field (otherwise right gcd do not exist in general).

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = (x^2 + t*x + 1) * (x + t)
sage: b = 2 * (x^3 + (t+1)*x^2 + t^2) * (x + t)
sage: g,u,v = a.right_xgcd(b); g
x + t
sage: u*a + v*b == g
True

Specifying monic=False, we can get a nonmonic gcd:

sage: g,u,v = a.right_xgcd(b, monic=False); g                               # needs sage.rings.finite_rings
(4*t^2 + 4*t + 1)*x + 4*t^2 + 4*t + 3
sage: u*a + v*b == g                                                        # needs sage.rings.finite_rings
True

The base ring must be a field:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = (x^2 + t*x + 1) * (x + t)
sage: b = 2 * (x^3 + (t+1)*x^2 + t^2) * (x + t)
sage: a.right_xgcd(b)
Traceback (most recent call last):
...
TypeError: the base ring must be a field

right_xlcm(other, monic=True)#

Return the right lcm \(L\) of self and other together with two Ore polynomials \(U\) and \(V\) such that

\[\text{self} \cdot U = \text{other} \cdot V = L.\]

INPUT:

other – an Ore polynomial in the same ring as self
monic – a boolean (default: True); whether the right lcm should be normalized to be monic

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: P = (x + t) * (x + t^2)
sage: Q = 2 * (x + t) * (x^2 + t + 1)
sage: L, U, V = P.right_xlcm(Q)
sage: L
x^4 + (2*t^2 + t + 2)*x^3 + (3*t^2 + 4*t + 1)*x^2 + (3*t^2 + 4*t + 1)*x + t^2 + 4
sage: P * U == L
True
sage: Q * V == L
True

shift(n)#

Return self multiplied on the right by the power \(x^n\).

If \(n\) is negative, terms below \(x^n\) will be discarded.

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = x^5 + t^4*x^4 + t^2*x^2 + t^10
sage: a.shift(0)
x^5 + t^4*x^4 + t^2*x^2 + t^10
sage: a.shift(-1)
x^4 + t^4*x^3 + t^2*x
sage: a.shift(-5)
1
sage: a.shift(2)
x^7 + t^4*x^6 + t^2*x^4 + t^10*x^2

One can also use the infix shift operator:

sage: a >> 2
x^3 + t^4*x^2 + t^2
sage: a << 2
x^7 + t^4*x^6 + t^2*x^4 + t^10*x^2

square()#

Return the square of self.

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x', sigma]
sage: a = x + t; a
x + t
sage: a.square()
x^2 + (2*t + 1)*x + t^2
sage: a.square() == a*a
True

sage: der = R.derivation()
sage: A.<d> = R['d', der]
sage: (d + t).square()
d^2 + 2*t*d + t^2 + 1

variable_name()#

Return the string name of the variable used in self.

EXAMPLES:

sage: R.<t> = QQ[]
sage: sigma = R.hom([t+1])
sage: S.<x> = R['x',sigma]
sage: a = x + t
sage: a.variable_name()
'x'

class sage.rings.polynomial.ore_polynomial_element.OrePolynomialBaseringInjection#

Bases: Morphism

Representation of the canonical homomorphism from a ring \(R\) into an Ore polynomial ring over \(R\).

This class is necessary for automatic coercion from the base ring to the Ore polynomial ring.