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
- 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 asself.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 byother
on the left.INPUT:
other
– an Ore polynomial in the same ring asself
OUTPUT:
Return
True
orFalse
.EXAMPLES:
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)) 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
ifself
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 byother
on the right.INPUT:
other
– an Ore polynomial in the same ring asself
OUTPUT:
Return
True
orFalse
.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
ifself
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, useis_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
ifself
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
dividesother
on the left.INPUT:
other
– an Ore polynomial in the same ring asself
OUTPUT:
Return
True
orFalse
.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
andother
.INPUT:
other
– an Ore polynomial in the same ring asself
monic
– boolean (default:True
); return whether the left gcd should be normalized to be monic
OUTPUT:
The left gcd of
self
andother
, 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 bothself
andother
. If monic isTrue
, \(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
andother
.INPUT:
other
– an Ore polynomial in the same ring asself
monic
– boolean (default:True
); return whether the left lcm should be normalized to be monic
OUTPUT:
The left lcm of
self
andother
, 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 bothself
andother
(right divisible byself
andother
). If monic isTrue
, \(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
byother
.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
byother
.INPUT:
other
– an Ore polynomial in the same ring asself
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
andother
along with the coefficients for the linear combination.If \(a\) is
self
and \(b\) isother
, 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 asself
monic
– boolean (default:True
); return whether the left gcd should be normalized to be monic
OUTPUT:
The left gcd of
self
andother
, 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 bothself
andother
. If monic isTrue
, \(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\) isother
.
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
andother
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
dividesother
on the right.INPUT:
other
– an Ore polynomial in the same ring asself
OUTPUT:
Return
True
orFalse
.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
andother
.INPUT:
other
– an Ore polynomial in the same ring asself
monic
– boolean (default:True
); return whether the right gcd should be normalized to be monic
OUTPUT:
The right gcd of
self
andother
, 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 bothself
andother
. If monic isTrue
, \(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
andother
.INPUT:
other
– an Ore polynomial in the same ring asself
monic
– boolean (default:True
); return whether the right lcm should be normalized to be monic
OUTPUT:
The right lcm of
self
andother
, 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 bothself
andother
(left divisible byself
andother
). If monic isTrue
, \(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
byother
.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
byother
.INPUT:
other
– an Ore polynomial in the same ring asself
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
andother
along with the coefficients for the linear combination.If \(a\) is
self
and \(b\) isother
, 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 asself
monic
– boolean (default:True
); return whether the right gcd should be normalized to be monic
OUTPUT:
The right gcd of
self
andother
, 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 bothself
andother
. If monic isTrue
, \(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\) isother
.
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
andother
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 asself
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.
See also
EXAMPLES:
sage: R.<t> = QQ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: S.coerce_map_from(S.base_ring()) #indirect doctest Ore Polynomial base injection morphism: From: Univariate Polynomial Ring in t over Rational Field To: Ore Polynomial Ring in x over Univariate Polynomial Ring in t over Rational Field twisted by t |--> t + 1
- an_element()#
Return an element of the codomain of the ring homomorphism.
EXAMPLES:
sage: # needs sage.rings.finite_rings sage: from sage.rings.polynomial.ore_polynomial_element import OrePolynomialBaseringInjection sage: k.<t> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x',Frob] sage: m = OrePolynomialBaseringInjection(k, k['x', Frob]) sage: m.an_element() x
- section()#
Return the canonical homomorphism from the constants of an Ore polynomial ring to the base ring according to
self
.
- class sage.rings.polynomial.ore_polynomial_element.OrePolynomial_generic_dense#
Bases:
OrePolynomial
Generic implementation of dense Ore polynomial supporting any valid base ring, twisting morphism and twisting derivation.
- 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 asself.list()
.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]
- 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
By convention, the degree of \(0\) is \(-1\):
sage: S(0).degree() -1
- dict()#
Return a dictionary representation of
self
.EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = x^2012 + t*x^1006 + t^3 + 2*t sage: a.dict() {0: t^3 + 2*t, 1006: t, 2012: 1}
- hilbert_shift(s, var=None)#
Return this Ore polynomial with variable shifted by \(s\), i.e. if this Ore polynomial is \(P(x)\), return \(P(x+s)\).
INPUT:
s
– an element in the base ringvar
– a string; the variable name
EXAMPLES:
sage: R.<t> = GF(7)[] sage: der = R.derivation() sage: A.<d> = R['d', der] sage: L = d^3 + t*d^2 sage: L.hilbert_shift(t) d^3 + 4*t*d^2 + (5*t^2 + 3)*d + 2*t^3 + 4*t sage: (d+t)^3 + t*(d+t)^2 d^3 + 4*t*d^2 + (5*t^2 + 3)*d + 2*t^3 + 4*t
One can specify another variable name:
sage: L.hilbert_shift(t, var='x') x^3 + 4*t*x^2 + (5*t^2 + 3)*x + 2*t^3 + 4*t
When the twisting morphism is not trivial, the output lies in a different Ore polynomial ring:
sage: # needs sage.rings.finite_rings sage: k.<a> = GF(5^3) sage: Frob = k.frobenius_endomorphism() sage: S.<x> = k['x', Frob] sage: P = x^2 + a*x + a^2 sage: Q = P.hilbert_shift(a); Q x^2 + (2*a^2 + a + 4)*x + a^2 + 3*a + 4 sage: Q.parent() Ore Polynomial Ring in x over Finite Field in a of size 5^3 twisted by a |--> a^5 and a*([a |--> a^5] - id) sage: Q.parent() is S False
This behavior ensures that the Hilbert shift by a fixed element defines an homomorphism of rings:
sage: # needs sage.rings.finite_rings sage: U = S.random_element(degree=5) sage: V = S.random_element(degree=5) sage: s = k.random_element() sage: (U+V).hilbert_shift(s) == U.hilbert_shift(s) + V.hilbert_shift(s) True sage: (U*V).hilbert_shift(s) == U.hilbert_shift(s) * V.hilbert_shift(s) True
We check that shifting by an element and then by its opposite gives back the initial Ore polynomial:
sage: # needs sage.rings.finite_rings sage: P = S.random_element(degree=10) sage: s = k.random_element() sage: P.hilbert_shift(s).hilbert_shift(-s) == P True
- list(copy=True)#
Return a list of the coefficients of
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: l = a.list(); l [t^2 + 1, 0, t + 1, 0, 1]
Note that \(l\) is a list, it is mutable, and each call to the list method returns a new list:
sage: type(l) <... 'list'> sage: l[0] = 5 sage: a.list() [t^2 + 1, 0, t + 1, 0, 1]
- truncate(n)#
Return the polynomial resulting from discarding all monomials of degree at least \(n\).
EXAMPLES:
sage: R.<t> = ZZ[] sage: sigma = R.hom([t+1]) sage: S.<x> = R['x',sigma] sage: a = t*x^3 + x^4 + (t+1)*x^2 sage: a.truncate(4) t*x^3 + (t + 1)*x^2 sage: a.truncate(3) (t + 1)*x^2
- valuation()#
Return the minimal degree of a non-zero monomial of
self
.By convention, the zero Ore polynomial has valuation \(+\infty\).
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 sage: a.valuation() 1
By convention, the valuation of \(0\) is \(+\infty\):
sage: S(0).valuation() +Infinity